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?