Tutorial #4 971003 =========== --------------------------------------------------------------------- Topics ------ (1) Explain available operations on priority condition variables (2) Format of Assignment 1 solutions (3) Answer questions about A1 (4) Section 9.6: Exercises 1 & 4 (5) Section 8.6: Exercise 3 *** extra topic from gsg: (6) Check out http://java.sun.com/docs/books/tutorial/java/threads/deadlock.html --------------------------------------------------------------------- Announcements ------------- - Within the next couple of days, you will find information about the submission requirements for A1 in the include directory: /u/csc468h/include/a1/HandIn --------------------------------------------------------------------- (1) Explain available operations on priority condition variables [Make sure you don't tell them which question requires the use of a priority condition variable.] - There were some e-mail questions about minrank(c), so we'll spend some time discussing priority queue variables. - If c is a priority condition variable, then you can think of it as an ordered queue, where each process that is waiting on this variable has some priority value associated with it. The queue is ordered from lowest priority value to highest priority value. var c : priority condition % Declare an OOT priority condition variable wait c,priority % Wait on condition variable c, with a % particular priority value. signal c % Resumes a process that is waiting on c % and removes it from c. The process at % the head of the queue (lowest priority % value is resumed first. empty (c) % Returns TRUE is c has no processes waiting % on it; returns FALSE otherwise. Returns % a boolean value. minrank (c) % Return the priority value of the process % that is at the front of the condition queue % for c. This is the lowest priority value % in the queue. Returns an integer. % This function does not exist in OOT! (2) Format of Assignment 1 solutions - This will be available shortly in the include directory /u/csc468h/include/a1/HandIn - You will be handing in a printout of each question, and this assignment will be submitted electronically as well. - Because minrank(c) is not part of OOT, you will not be able to compile and run any program that you write that uses this function. - Your solutions should be written in the OOT language. They should compile except for cases were you use priority queue operations that are unknown to OOT. (3) Answer questions about A1 - Ask if they have any questions about A1. (4) Exercises from Section 9.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. Write a code fragment (similar to those in the figure in this chapter) to illustrate how the processes can use monitors to coordinate access to V1, V1, and V2 so that the critical section problem does not occur. ++++++++++++++++ Some additional notes... * The "enter(0),enter(2),access V0, access V2" block of code: - This is used because we're assuming that the process requires exclusive access to V0 and V2 at the same time. * AND Synchronization: - In the text book in Section 9.1.1 (pg. 222) it talks about AND Synchronization. This is a software solution to this problem of having to nest calls to P on two different semaphores. This is similar to what we have had to do with the "enter(0),enter(2),access V0, access V2" block of code. This software solution would allow you to simply use Psimultaneous(s0,s2) to wait until both s0 and s2 became available. * Order of "enter(0),enter(2)" matters: - If another process was to also request exclusive access to the same two variables, we must make sure that that process uses the calls to "enter(0),enter(2)" in the same order. If process A had: And process B had: enter(0); enter(2); enter(2); enter(0); Then if both processes executed their first enter statement, then neither could execute their second enter statement ... this would be a deadlock! - But if we were to use an AND Synchronization software solution, we wouldn't have to worry about such things as the order of the calls to "enter" (or to P on semaphore). 4. The Sleepy Barber Problem. A barbershop is designed so that there is a private room that contains the barber chair and an adjoining waiting room with a sliding door that contains N chairs (see the diagram in Problem 11 in Chapter 8). If the barber is busy, the door to the private room is closed and arriving customers sit in one of the available chairs. If a customer enters the barbershop and all chairs are occupied, the customer leaves the shop without a haircut. If there are no customers to be served, the barber goes to sleep in the barber chair with the door to the waiting room open. If the barber is asleep, the customer wakes the barber and obtains a haircut. Write a monitor to coordinate the barber and the customers. ++++++++++++++++ First, a look at the monitor condition variables and procedures that would be needed to design a solution to this problem... A monitor with 2 condition variables: sleepy --> used to signal barber when a customer arrives. --> barber waits on this when no customers require haircuts. haircut --> customers wait on this for haircuts. --> barber signals this variable to release a customer waiting for a haircut. A monitor with 2 procedures: request_haircut --> an arriving customer calls this procedure when this customer would like a haircut. take_customer --> when the barber finishes with the previous customer, he calls this to give the next customer a haircut. (5) Exercise from Section 8.6: 3. The following solution is alleged to be a solution to the critical section problem. Argue for its correctness or show a case in which it fails. shared int turn; // Keeps track of whose turn it is shared boolean flag[2]; // If TRUE, indicates that a process // would like to enter its c.s. proc (int i) { while (TRUE) { compute; // Attempt to enter the critical section try: flag[i] = TRUE; // An atomic operation // While the other process's flag is TRUE while (flag[(i+1) mod 2]) { // An atomic operation if (turn == i) continue; flag[i] = FALSE; // Reset to let other process go while (turn != i); // Wait till it's my turn goto try; } // Okay to enter the critical section ; // Leaving the critical section turn = (i+1) mod 2; // Set turn to other process flag[i] = FALSE; // Indicate no desire to enter my c.s. } } turn = 0; // Process 0 wins tie for 1st turn flag[0] = flag[1] = FALSE; // Initialize flags before starting fork (proc, 1, 0); // Create process to run proc(0) fork (proc, 1, 1); // Create process to run proc(1) 3b. And here's an extra topic from Andria... :-) Does this solution cause strict alternation between the two processes? Suppose process 1 is in its "compute;" section for an extremely long period of time, such that process 0 has time to execute its critical section several times. Will process 0 have to wait for process 1? Show why or why not. ++++++++++++++++ The answer is that process 0 will not have to wait for process 1. It can execute its critical section several times while process 1 is in its "compute;" section. Assume turn is 0 to begin with. If process 1 is in its compute section, we know that flag[1] is FALSE. Process 0 attempts to enter its critical section, so it sets flag[0] to TRUE. Since flag[1] isn't FALSE, it doesn't enter the while loop. It executes its critical section, and then sets turn to 1 and flag[1] to FALSE. Process 0 then returns to the top of the while(TRUE) loop and computes. Then it attempts to enter its critical section (Process 1 is still computing). Process 0 sets flag[0] to TRUE, and again it does not enter the while loop, but moves directly to its critical section code. Although the turn variable was set to 0 (which indicates that it is the other process's turn, it did not enter the while loop, so it didn't have to test turn==i (which would have failed).