Q1:  About #6-d:  What '3' in the chart?  Are we switching the priorities of P3 and P4?

A1:  No.  This is a typo!  I'm very sorry.  It should say "Suppose that the '2' is changed to a '3' in the chart."  (An earlier version of the exam had a "3" there.)  It refers to the duration of process P4.  Please tell your friends.

Q2:  In question one can multiple processes be named in the send & receive instructions.

A2:  If you can rig a solution where sending a message to multiple processes (I guess what you want is atomicity regarding the sending of these messages to both processes) will achieve the goal, then I'll accept it.

Q3:  Also having a problem in the initialization of the processes.  How can any processes start if processes must block on receive(proc, msg) if there is no message since you must check for critical section entry of other processes.

A3:  You don't need to receive a message before entering your CS if no other process wants to enter its CS.  You can use shared variables to detect other process' interest in their CS's.

Same conditions: You may consult books, notes and the Internet, and you may work with other students to review class notes and discuss material in general.  But you may not consult any other person, student or otherwise, about the questions on this exam.  Please respect the spirit of this rule.  It will be good practice for the final, where you will be working alone.  Each problem is worth 12 points, with 4 free points because I want good teaching evaluations.

1.  As long as we have worked so hard explaining problem 6 on the first exam and what I was looking for in your solutions, I think I'll use the setup again:  There are three processes, P1, P2 and P3, each with a critical section, and only one of those processes may be in its critical section at any given time.  You want to guarantee the following behavior:  If while P3 is in its critical section, both P1 and P2 declare interest in entering their critical sections, then when P3 exits, P1 must be allowed into its critical section before P2.

Use message passing to guarantee this behavior.  Message passing is the only synchronization primitive you have available, and works as follows:
*  send_message(proc, message) sends message to process proc, and never blocks.
*  receive_message(proc, message) receives message from proc, and blocks if there is no message to receive
*  Messages are never lost.  That is, if a message is sent to proc and proc is not waiting for a message, then it will be saved for the next time proc tries to receive a message.  There is no bound to the number of messages that can be saved up for a process, and they are saved in a FIFO queue
*  The actual messages themselves are integers
 

2.  Use message passing as described above to achieve the following:

A certain bank dealing only in cash is conveniently open every day from 7:00 to 17:00, and during any given day the amount deposited by customers exactly equals the amount withdrawn by customers.  Inconveniently, however, the bank starts each day with $0 in cash, and ends the day with the same amount, but customers wishing to make withdrawals must wait until a sufficient amount has been deposited to cover the withdrawal.  At the end of the day the doors are closed and the day's transactions are reconciled.

Three processes are used here:

deposit	withdraw	reconcile
while(time <= 1700){    ...    get_money_from_cust(amount);    ... }	while(time <= 1700){    ...    get_request_from_cust(amount);    ...    give_money_to_customer(amount); }	if(time > 1700){    do_reconcile_routine(); }

Your job is to fill in the sections marked with "...".  Your solution should not use any shared variables such as "balance."
 

3.  A mailbox is an implementation of message passing where messages are passed to and from a mailbox object which is not a process.  The functions involved are:

create_mailbox(mbox);
send(mbox, message);
receive(mbox, message);
Again, assume all messages are integers.

On a system with mailboxes but without semaphores it is possible to write P and V routines to give the user semaphore capability.  Show how this can be done.  Make sure that you include details about how you would have the user declare and initialize the semaphores.

4.  Now suppose you have a system with semaphores but without mailboxes.  Show how you would give the user mailbox capability by writing the create_mailbox(), send() and receive() functions using semaphores.

5.  Suppose there are N processes running on a system, each blocked with probability 2/3 independent of all the other processes.  What fraction of the time will the CPU be working on processes if:
a.  N = 1
b.  N = 5
c.  N = 10
Now suppose we have 10 I/O-bound processes, 4 blocked with probability 9/10 and 6 blocked with probability 19/20, and one CPU-intensive process blocked with probability 1/3, again independent of one another.  What fraction of the time will the CPU be working on processes?

6.  An embedded system has four processes each with a period and a duration as shown below:  

Process	Duration	Period
P1	100	200
P2	20	80
P3	20	100
P4	2	40

For example, P1 must run every 200msec, and requires 100msec during every 200msec period to complete its task.  At time t=0, every process is ready, including P1.  Thereafter, P1 becomes ready at times 200, 400, 600, etc..., and becomes blocked once it has completed its 100msec worth of computation during any period.

A scheduling algorithm in this context makes scheduling decisions every time the set of ready processes changes, and uses some particular criterion to determine which process gets assigned to the CPU from among the ready processes.

For each of the following algorithms, schedule those processes until either some process misses its deadline or until we seem to be repeating ourselves, at which point you can declare that these processes will always schedule successfully.

a.  Highest priority first, where the priorities are highest=P1, P2, P3, P4=lowest.

b.  Shortest remaining time next, where the process with the shortest remaining time to completion (in that period) gets scheduled

c.  Earliest deadline first, where the process whose deadline is most imminent is scheduled

In each case, whenever you break a tie, please indicate that you broke a tie and how you broke it.  Please do your work on graph paper, in the format shown on the web version of this exam.

Here is a 200msec example of how these processes would schedule under the "shortest period first" policy:

And finally:

d.  Suppose that the "3" is changed to a "4" in the chart.  Prove that there is no way to schedule these processes so that deadlines are never missed.  Extra credit:  What is the longest you can schedule successfully before you get a deadline miss?  This will be graded as follows:  one point for each 100msec you manage to schedule successfully.
 

7.  This problem concerns batch scheduling, in which some fixed set of processes is given at time t=0, the scheduler is allowed to schedule the order in which the processes are put on the CPU, processes run to completion once put on the CPU, and the time that each process will require for completion is known in advance.  Suppose that processes P1, P2, ..., Pk take time T1, T2, ..., Tk respectively, with T1 <= T2, <= ..., <= Tk.  Show that the schedule that minimizes average turnaround time is P1-P2-...-Pk.  (The turnaround time of a process is the time at which that process completes, which is the sum of its completion time and the completion times of all processes that were scheduled before it.)

For this problem, please do not simply copy a solution from another source.  Make sure you digest the solution and then put it into your own words.  I'll grade this one fairly strictly.
 

8.  Suppose we have n processes in some system with one of them on the CPU at any given time and the rest in a round-robin queue waiting for scheduling.  (These processes never block or terminate; they just yield and then get put on the end of the queue.)  Suppose T is the average time that a process spends in the queue and R is the number of processes that the CPU services per second.  Find a simple mathematical relationship between n, R and T, and give a paragraph justifying your answer.