Homework 6

0. Dining Philosophers due Monday 11/6 at beginning of class
The handout shows 4 ways to try to solve the dining philosophers problem. For each of them, figure out if it results in success, violation of mutual exclusion, deadlock or starvation. On what instruction can it get stuck or violate mutual exclusion?

1. Using Semaphores
   In the year 2002, the number of CS majors will grow to 100 and thus our department will convert to online web courses for all subjects. Students may take as many or as few courses in one semester as they can complete. You are to write synchronization code to coordinate students taking three of these courses: MATH 171, 172, and 363. The pre-reqs to MATH 363 are 171 and 172. In addition, the department web server can only handle 20 students in each class at any one time. Augment the code fragments below to enforce the pre-reqs AND limit the class sizes to 20 in MATH 171, 172, and 363. You should define semaphores and insert them in the appropriate places. Be sure you specify the purpose of each semaphore and its initial value. (Maybe reading over the "basic synchronizing problem" on p. 197 gives you some ideas.)
   Each student has three processes: You are to write the entry and exit code for each of these.
   

   P1:  [entry code]  take MATH 171;  [exit code]  do other cool stuff;
   P2:  [entry code]  take MATH 172;  [exit code]  do other cool stuff;
   P3:  [entry code]  take MATH 363;  [exit code]  do other cool stuff;
   

   
   
   
2. Implementation of Semaphores
   Before you start generating solutions, discuss the implementation of semaphores discussed in class and in our textbook p. 203. Thoroughly understand it! Consider the following two hardware instructions that are useful for synchronization. They are atomic.
   

   SOBGEQ  SEM, LOC	subtract one from SEM and branch
   			to LOC if greater than or equal to zero.
   AOBLEQ  SEM, LOC	add one to SEM and branch to LOC
   			if less than or equal to zero.
   

   Use these hardware instructions to implement P and V without busywaiting. The value of the semaphore is allowed to take on negative values if necessary. You can assume the existence of two routines:
   

   BLOCK	blocks the process that calls it by adding its PCB to tail of
           Wait_Queue.
   UNBLOCK selects blocked process from head of the Wait_QUEUE and appends
   	it to tail of the Ready_Queue.
   

   You can use real or pseudo assembly code. Be sure to comment each line of code. The answer is very short!