Due: In class, Monday April 12
1. Two programs A and B have the same behavior: (
3 CPU; 2 IO) ¥ 3
(class notation)
Both programs are ready at time 0. Assume a single CPU and one
IO device, and that the CPU and IO can run concurrently. Compute
the CPU and IO device utilization, average turnaround time, and throughput
under
(a) purely sequential execution of A followed by B.
(b) time-shared execution of both programs, with maximal parallelism
and round-robin scheduling every clock tick, as in the class handout.
2. Write a two-way merge-sort procedure, using fork, join,
and quit operations to dynamically generate and synchronize parallel
threads that perform the merge-sort. The statement
p := fork Proc_Id(params);
will create and start a new thread, store its identifier in p, and
execute the procedure given by Proc_Id. The operation
join p;
will cause the executing thread, say q, to wait until the thread
p terminates; q then continues its execution. quit terminates the calling
thread. Assume that the array to be sorted, say A, is defined globally
and that you are given a procedure
merge(low,high);
that takes a sorted section of A, from A[low] to A[mid], and merges
it with the sorted contiguous section, A[mid+1] to A[high], where mid=(low+high)/2.
3. Consider the two-process solution to the critical section problem (Peterson's solution, Algorithm 3, Figure 6.4, p. 161, text). Suppose that the line "turn := j;" is changed to "turn := i;". Does this change result in a program that satisfies the mutual exclusion, progress, and bounded waiting requirements? Argue for the correctness of your answer.
4. Suppose that a machine has an atomic (indivisible) compare-and-swap
instruction CAS(a,b) that compares and interchanges its operands as follows:
R := (a=b) ; if not(a=b) then swap(a,b);
where R is a distinguished, program-accessible, internal register of
the machine. CAS can be viewed as a function that returns (a=b).
Using the CAS instruction, give a busy wait (spin lock) solution to the
n-process critical section problem.