EECS 482 W03 Homework Set #1 ----------------------------- 1. (Problem 2.21 in Tanenbaum) Does Peterson's solution to the mutual exclusion problem shown in Fig. 2-21 work when process scheduling is preemptive? How about when it is not preemptive? 2. Races Consider the pseudo-code for a function total(). Consider what can happen when 2 threads (in the same process) are both started to run the same function--total(). Assume that context-switching between threads can occur at any time between machine instructions. Assume that the following operators are atomic: comparison operators, assignment, and addition. By considering all possible interleavings between the two threads, determine the proper lower bound and the upper bound on the final value of the shared variable "tally". Case A: Variable global to all threads: -------------------------------- int tally; Thread code: ----------- void total () { int count; // local variable to a thread tally = tally + 1; } CASE B: Variables global to all threads: -------------------------------- int n = 20; int tally; Thread code: ----------- void total () { int count; // local variable to a thread for (count = 0; count < n; count++) tally = tally + 1; } Monitors 3. Using Monitors (lock, unlock, wait, signal, broadcast) You have been hired by an airline company and asked to design a Monitor solution to handle seat reservations on a flight. The flight has MAX seats, initially all available. There are multiple threads in the system executing on the behalf of the users. Each thread can call the following monitor procedures that you will write: - void reserve(int n): to make a reservation of n seats. This call must block if fewer than n seats are available. It must return after n seats are reserved. - void cancel(int n): to free up n seats. Assume that the calls are used correctly by threads, i.e. cancel() is eventually called to free up any previously reserved seats and only for that purpose. Do not worry about keeping track of identity of seats assigned to each individual thread. Also, the order in which requesting threads get seats does not matter. The important rule is that sum of all reserved seats do not exceed MAX and threads are not unnecessarily blocked when sufficient number of seats are available. Semaphores 4. Using semaphores (up, down) Use semaphores to implment ONE Monitor. That is, implement the functions lock(), unlock(), wait(), and signal() using as many semaphores as necessary. Assume that there is only ONE lock and ONE condition variable. Remember that if there are no waiting threads when signal is called, the signal is lost (not remembered). List any global (shared data) and any semaphores and their initial values (eg. mutex_sem=1, int num_waiting = 0).