Tutorial #3 970926 =========== Topics ------ (1) Assignment 1, Question 1: Explain fair access to resources (2) Assignment 1, Question 2: Explain CLook disk scheduling (3) Exercises from Section 8.6: - Exercise 1 - Exercise 4 - Exercise 5 - Exercise 10 Announcements ------------- - Assignment 1 is now available in /u/csc468h/include/a1/a1.ps - Minotaur documentation available in /u/csc468h/include/documents/... ------------------------------------------------------------------------- (1) Assignment 1, Question 1: Fair access to resources Consider the possible semaphore definitions that were given in the Assignment 1 description. These definitions are for a monitor that has procedures "P" and "V," an integer "s" variable initialized to 1, and a condition "sem" variable. P might look like: V might look like: if (s==0) s := s + 1; wait (sem); signal (sem); s := s - 1; In this implementation of a semaphore, it appears that processes can complete P() in the order in which they are called. Condition variable queues are FIFO queues in the absence of priority wait statements. Consequently, delayed processes are certainly awakened in the order in which they waited. However, since signal is not preemptive, before an awakened process gets a chance to execute, some other process could call P, find s!=0, and thus complete P before the awakened process. This is the situation that your SNOOT monitor should prevent. In the assignment description, it explains unfair signaling semantics using three processes as an example. We will explain this again and show a diagram to make sure that this is clear. - Process A signals in procedure V and steps out of the monitor. - Process B that waited in procedure P is made runnable (not running, but runnable) and competes to enter the monitor along with the other processes that have not yet entered the monitor. - In this case, it is possible for a new process C to enter the monitor before B and use the guarded resource, even though A presumably wanted B to take advantage of its signal. In the SNOOT implementation, we want to prevent process C from entering before process B (because process B called procedure P first). (2) Assignment 1, Question 2: CLook disk scheduling It is possible for several different users to attempt to use the disk at the same time. Only one disk request, however, can be serviced at a given time; it is up to the disk scheduler to keep track of and to schedule requests for the disk. It must ensure that only one disk request is serviced at a time. If a series of disk requests are in the same physical vicinity on a disk, it will take less time to service these requests than it would if they were scattered on cylinders of the disk that were not physically close to each other. A smart disk scheduler should attempt to service requests in the current vicinity of the disk head, while ensuring that no requests experience starvation. With the Circular Look (CLook) disk scheduling discipline, requests are serviced in only one direction (e.g., from low cylinders up to high cylinders). In particular, there is only one search direction, and the request closest to the current head position in that direction is selected. After the disk head services the request with the highest cylinder number, the search starts back at the lowest cylinder number that has a request. For example, suppose we have a disk with cylinders from 0 to 100. If the disk head was at position 50, and requests for cylinders 73, 14, 63, 27, and 86 were received, they would be serviced in this order: 50, 63, 73, 86, 14, 27 (3) The remainder of this file contains the descriptions for Exercises 1, 4, 5, and 10 in Chapter 8. Exercises from Section 8.6: 1. Suppose processes p0 and p1 share variable V2, processes p1 and p2 share variable V0, and processes p2 and p3 share variable V1. A. Show how the processes can use enable and disable to coordinate access to V0, V1, and V2 so that the critical section problem does not occur. B. Show how the processes can use semaphores to coordinate access to V0, V1, and V2 so that the critical section problem does not occur. 4. Dijkstra posed each of the following solutions as a potential software solution to the critical section problem and then explained why they failed [Dijkstra, 1968]. Explain why they failed. A. int turn = 1; proc (int i) { while (TRUE) { compute; while (turn != i); // Wait until it's my turn critical_section; turn = (i+1) mod 2; // Toggle turn (between 0 and 1) } } fork (proc, 1, 0); fork (proc, 1, 1); B. boolean flag[2]; // flag[i] is TRUE when proc i in C.S. proc (int i) { while (TRUE) { compute; while (flag[(i+1) mod 2]); // Wait till flag[other_process] is FALSE flag[i] = TRUE; // process i starting C.S. critical_section; flag[i] = FALSE; // process i finished C.S. } } flag[0] = flag[1] = FALSE; fork (proc, 1, 0); fork (proc, 1, 1); C. boolean flag[2]; // flag[i] is TRUE when proc i in C.S. proc (int i) { while (TRUE) { compute; flag[i] = TRUE; while (flag[(i+1) mod 2]); // Wait till flag[other_process] is FALSE critical_section; flag[i] = FALSE; } } flag[0] = flag[1] = FALSE; fork (proc, 1, 0); fork (proc, 1, 1); 5. In the solution to the bounded buffer problem provided in Figure 8.14, it was argued that the order of the P(full) and the P(mutex) instructions was important. Does the same argument hold for the order of the V(mutex) and the V(full) instructions at the end of the loop? Figure 8.14: Bounded Buffer Problem: producer() { consumer() { buf_type *next, *here; buf_type *next, *here; while (TRUE) { while (TRUE) { produce_item(next); // Claim a full buffer // Claim an empty buffer P(full); P(empty); // Manipulate the pool // Manipulate the pool P(mutex); P(mutex); here = obtain(full); here = obtain(empty); V(mutex); V(mutex); copy_buffer(here,next); copy_buffer(next,here); // Manipulate the pool // Manipulate the pool P(mutex); P(mutex); release(here,emptyPool); release(here,fullPool); V(mutex); V(mutex); // Signal an empty buffer // Signal a full buffer V(empty); V(full); consume_item(next); } } } } semaphore mutex=1; semaphore full=0; semaphore empty=N; buf_type buffer[N]; fork (producer, 0); fork (consumer, 0); 10. The Dining Philosophers Problem. Suppose five philosophers are seated around a table on which are placed five plates of pasta and five forks [Dijkstra, 1968]. While the philosophers think, they ignore the pasta and do not require a fork. When a philosopher decides to eat, he or she must obtain two forks, one from the left of the plate and one from the right of the plate. To make the analogy fit the behaviour of sequential processes, assume a philosopher can pick up only a single fork at one time. After consuming food, the philosopher replaces the forks and resumes thinking. A philosopher to the left or right of a dining philosopher cannot eat while the dining philosopher is eating, since forks are a shared resource. The following code segment was posed as a scheme for synchronizing the actions of the philosophers. Argue for its correctness or provide a scenario in which it fails. semaphore fork[5]; philosopher (int i) { while (TRUE) { // Think // Eat P(fork[i]); // Wait for my left fork P(fork[(i+1) mod 5]); // Wait for my right fork eat(); V(fork[(i+1) mod 5]); // Release my right fork V(fork[i]); // Release my left fork } } fork[0] = fork[1] = fork[2] = fork[3] = fork[4] = 1; fork (philosopher, 1, 0); fork (philosopher, 1, 1); fork (philosopher, 1, 2); fork (philosopher, 1, 3); fork (philosopher, 1, 4);