Multitasking; Process control in Unix
1. What is an operating system process? How is it different from a program? Why do we need the concept of a process, rather than simply talk about programs running in memory?
2. Describe the differences between foreground and background processing. What advantage does background processing provide?
3. Develop a C program under the Unix environment which clearly demonstrates to a user running it the concept of multitasking, even on a single CPU architecture. The output should clearly show the separate identities of parent and child processes, and the isolation of data between the two processes.
Identifying parallelism
4. A formal way to identify parallelism in an activity is to draw a taskdependence graphin a directed graph in which each vertex represents a task to be completed. An edge from vertex u to vertex means that task u must be completed before task v begins, so that task v "depends on" u. If there is no path from u to v, then the tasks are independent and may be performed concurrently.
Consider the following problem: Alice is the leader of a crew of workers who maintain a large estate. There are four principal tasks: mowing the lawns, pruning the trees and hedges, repairing the fences, and inspecting the work to ensure it has all been done satisfactorily. Mowing must be completed before the work is inspected, as must the pruning and fence repair. The estate has a security system which must be switched off before work commences (i.e. before Alice and her team arrives), and switched on again after the team leaves.
a) Draw the dependence graph corresponding to the above problem, showing all the tasks involved. (In a project management plan, this scheme is often referred to as a "work breakdown structure").
b) Alice has 8 people in her crew, including herself. (The crew members are: Alice, Bert, Cressida, Dominic, Edgar, Frank, Gus and Harriet). Alice will be solely responsible for inspecting the work, but decides that she herself and three other people (Bert, Dominic and Gus) will mow the estate's four lawns (referred to as north, south, west and east lawns, each of which are of equal area), two other people (Cressida and Frank) will prune the trees, whilst Edgar and Harriet will repair the fences. Redraw the graph to show the allocation of the crew to particular tasks. (Hint: a single task in the original graph may be come multiple tasks in the revised version, each of which is performed by a particular person).
c) Alice is a fast worker, and can mow any of the lawns in one hour, as can Dominic. Frank and Gus can complete any of the manual tasks in two hours. Bert, Cressida, Edgar and Harriet take three hours to do their work. If the manual work starts at 10:00 a.m. in the morning, at what time can Alice inspect the work? In your answer, refer to the dependence graph showing the allocation of crew to tasks.
5. Discuss the concepts of task decomposition and data decomposition within the context of parallel programming.
[5 marks]
Data races, critical sections, processor loading
6. Research the phenomenon of data races. Give an example of how an unprotected data race can give rise to data inconsistency.How do OpenMP and Cilk resolve this problem?
7. Present your own fully documented and tested programming example illustrating the prevention of a data race in a parallelised program.
8. What is meant by the phrase ‘thread-safe'?.
9. Present your own fully documented and tested programming example illustrating the use of locks to govern access to critical sections.
10. Present your own fully documented and tested programming example illustrating the problem of unbalanced loads. Describe the use of OpenMP's scheduler as a means of mitigating this problem.
Write down all above questions in single word document with including total 2500-3000 words count, Write down explained answer for all questions.