|
| |
HOMEWORK1 - Scheduling and Synchronization
---------------------------------------------
1) Question 22 in Tanenbaum chapter 2. For the Round Robin assume
time-quantum of 1 sec.
2) Question 5.7 in Silberschats (note to us - also in last year exam).
Add the following questions:
is there a "starvation" problem in a) in b) or in c)? explain
Can you think about an expression which determines priorities
and takes into account both Running time (preference to short)
and waiting time (preference to long).
3) Assume 3 processes with the following behaviour:
a. 1 sec cpu, 2 secs I/O, 1 sec cpu
b. 2 secs cpu, 2 secs i/o
c. 3 secs cpu, 3 secs i/o
Find the minimum total time for this set. (all arrive at time 0).
Prove that its minimal
Find two DIFFERENT schedules with this minimum total time with two
DIFFERENT Average Turn Around Times!
You may use any scheduling policy but time quantum NOT less than 1sec!
compute the CPU utilization in each case!
4) Prove formally the 3 conditions for the Bakery algorithm (slide 8)
a) Mutual exclusion
b) Progress
c) Bounded waiting
5) Explain why figure 2.16 in tanenbaum can cause a problem
in the Producer/consumer problem
and why the class solution solves it correctly
6) Show how to implement Semaphores with Message passing
7) On p. 165 Silberschats introduces the Swap command.
Solve the N-processes problem with this command
8) A store has n SERVERS and n slots for customers to be
in while waiting. The SERVERS block when there is no
customer. Every customer entering the store PICKS UP A
UNIQUE SLOT in the waiting queue (array). Whenever a SERVER is
free it finds out the next slot to be served and serves
the suitable customer. Write two procedures:
Customer(int nClient) and Server()
You can use the following semaphores:
Queue = 0 - the number of waiting customers
In = 1 - a mutex for manipulating Last and First
pointers to the customers in the array
ServedCustomer[n] - the customer whose turn it is to be
awakened
Servers = m - the number of available SERVERS
There are two more operations that are assumed to be
implemented and you can use their names in the code. CustomerAction()
and ServerAction(Served_Num). The first one is the last function
called inside the procedure Customer(int nClient) and it represents
the operations that a customer does BEFORE it releases the SERVER.
The operation ServerAction(Served_Num) is the last call inside
the procedure Server(), BEFORE it increments the semaphore
Servers, to let other customers wake-up to get service.
|