Homework 2

Out: Friday Jan 19
Due: Mon Jan 29

1. Suppose that the following processes arrive for execution at the
   times indicated. Each process will run with a single burst of
   CPU activity (i.e., no I/O) which lasts for the listed amount
   of time.

      process  arrival time  CPU burst time  priority
      -------  ------------  --------------  --------
         p1         0ms           25ms          3
         p2         1ms            9ms          1
         p3        20ms           14ms          4
         p4        32ms            4ms          2

a. What is the job throughput, average waiting time and average
turnaround time for these processes with non-preemptive, FCFS
scheduling?

b. With preemptive RR (quantum = 10ms) scheduling?  (Different
strategies might be used to add a newly submitted process to the ready
queue.  Explain what strategy you're using.)

c. With non-preemptive priority scheduling (given the above priorities)?

---

2. Consider the Sleeping-Barber Problem (p202, question 6.7 in the
   textbook,) with the modification that there are k barbers and k
   barber chairs in the barber room, intead of just one.  Write a
   program to coordinate the barbers and the customers using Java, C,
   or pseudo-code.  You can use either semaphores or monitors.

   (Hint: there are many solutions that will work, some of which
   that will perform better than others.  Don't worry about performance,
   just correctness; of course, deadlock performs poorly, and is
   also **incorrect** behavior.  My only performance requirement is
   that barbers must be able to work in parallel, so it's probably
   a bad idea for a barber to be in a mutex while cutting hair).

---

3. Consider the following C++-style pseudo-code.  We have a producer
   thread and a consumer thread running concurrently.  Both threads
   have access to the shared data.  Will they function correctly
   (i.e. each produced item will be consumed)?  Why or why not?

 1   // shared data
 2   Semaphore sstack = 0;
 3   BinarySemaphore bindex = 1;
 4   BinarySemaphore bmorespace = 1;
 5   int i = 0;
 6   #define STACK_SIZE 256
 7   item stack[STACK_SIZE];
 8
 9   ///////////////////////////
10   // producer thread
11   {
12       int j;
13
14       while (1) {
15           Item nextp;
16           ...
17           produce an item in nextp;
18           ...
19
20           bmorespace.wait(); // assume that we won't have more space later
21           bindex.wait();
22           j = i++;
23           if (i < STACK_SIZE)
24               bmorespace.signal(); // we still have space for more item(s)
25           bindex.signal();
26
27           stack[j] = nextp;
28           sstack.signal();
29       }
30   }
31
32   ...
33
34   ///////////////////////////
35   // consumer thread
36   {
37       int j;
38
39       while (1) {
40           sstack.wait();
41
42           bindex.wait();
43           j = --i;
44           if (j == STACK_SIZE - 1)
45               bmorespace.signal(); // the stack was full but now has one more space
46           bindex.signal();
47
48           Item nextc = stack[j];
49
50           ...
51           consume the item in nextc;
52           ...
53       }
54   }
   
---

4. (bonus question, strictly optional) 

  Use Java, C, or pseudo-code to implement:

     - monitors using semaphores  (hint: read Silberschatz section 6.7)
     - semaphores using monitors

   Your solutions may *not* busy-wait.

---

5. (bonus question, strictly optional)

   Use Java, C, or pseudo-code to implement:

     - semaphores using locks
     - locks using semaphores

   Is it possible to produce a solution that doesn't busywait?