NameSSNNetID
Midterm, cs1550, Oct 8, 2001. Work individually, choose 50 points out of the total 60 (if you choose to write more answers, your exam will be graded accordingly; for example, if you write answers for questions totaling 70 points, your grade will be out of 70 points). Grades will be available through courseweb.
1. [5 pts] Let several processes with the same source code, competing for a resource. Each process is represented by the following program. The calls to P(s) and V(s) are calls to operate on semaphore S, which is initialized to 1, and the P/V procedures are implemented by the monitor below.
NameSSNNetID
Process::
P(s);
Critical_sect;
V(s);
Monitor::
int s = 1;
condition c;
procedure p(s)
{
if (--s < 0)
c.wait;
}
procedure v(s)
{
s++;
c.signal;
}
end
If the two lines of procedure V were accidentally switched in the implementation, mark all answers that best describe what would happen. Assume that a process in the urgent queue has priority over a process waiting to enter the monitor.
Assuming that upon a “csignal(c)” action, a monitor suspends the current process (i.e., adds it to the urgent queue), and resumes a process waiting in “c.queue” due to a “c.wait”:
i)This new code could cause a deadlock
ii)This new code would perform the same tasks as the old code
iii)This new code would cause starvation
iv)This new code would cause a violation of critical section mutual exclusion requirements
v)None of the above
NameSSNNetID
SOLUTION: there is no problem. It’s all the same. A process may send a signal and get suspended (goto urgentQ); when the process doing a P exits the monitor (thus entering the CS), the urgent process enters the monitor and increases the variable s. no other process has touched this variable between the 2 processes.
2. Processes
a)[5 pts] Draw the complete state diagram, including the ALL the states in which processes may be waiting for resources. Name 4 transitions and give a 1-line description of what happens in that transition.
b)[5 pts] What do threads inside a process share?
c)[5 pts] What are the unique components that each thread has and does not share with other threads and/or processes?
For official use only; grades will be added and tallied here. Void where prohibited, must be 18 or older to play; HJ residents add sales taxes.
question / 1 / 2a 2b 3c / 3a 3b 3c / 4 / 5a 5b / 6 / totalmax points / 5 / 5 5 5 / 5 5 5 / 5 / 5 5 / 10
score
3. SchedulingDuring its lifetime a process alternates between CPU bursts, and I/O bursts. During the CPU bursts the process executes on the CPU without performing I/O operations. During the I/O bursts the process waits for I/O completions without using the CPU. We propose the following scheduling policy. The scheduler maintains an (effectively) infinite number of queues, Q[0], Q[1], ..., Q[infinity]. We assume that Q[k] has an associated quantum of 2k milliseconds. When a job requests the CPU, it is placed on queue Q[0]. Whenever the CPU becomes free, a job is dequeued from the lowest non-empty queue and run for that queue's quantum. If the job finishes its CPU burst before the quantum expires, (i.e., voluntarily releasing the CPU, then it is placed back on queue Q[0] when it requests the CPU again, at the start of its next CPU burst. Otherwise, the CPU is preempted and the job is reenqueued on the next higher queue. Each such context switch (preempting the CPU and reenqueuing the job) takes one millisecond.
a) [5pts]Is this algorithm subject to starvation? If not, explain why, and if so, suggest a fix.
SOLUTION
Yes, small jobs keep coming in starving large jobs
b) [5pts] Define convoy effect as a long CPU burst that causes jobs with a short CPU burst to queue up for a long time. Does this scheduling algorithm cause the so called convoy effect). If not, explain why, and if so, suggest a fix.
SOLUTION
A process can suffer from the convoy effect, since the queues with larger k values will much longer quanta, therefore causing convoy effect.
c) [5pts] Give a simple closed-form expression (that is, a formula), either exact or approximate, for the time spent in context switches by a process that executes k CPU bursts of n milliseconds, each followed by an I/O burst of m milliseconds (i.e., total k CPU bursts and k IO bursts, interweaved). A burstis the amount of time the process uses. Hint: start with figuring out the context switch time for a single CPU burst.
SOLUTION
This is not exact, but you get the spirit of the thing: Each job will execute for sum (1..i) 2**i <= n. That means that the number of preemptions is i-1 for each CPU burst. Since there are k of these…
4. [5pts] Answer this question in about a sentence or two. You will be penalized for overly long answers.
We have discussed a number of techniques for enforcing mutual exclusion, on top of which we have built more sophisticated synchronization primitives (such as semaphores and monitors). List and give a 1-line explanation oftwo hardware or software solutions, above which one can build semaphores.
SOLUTION
enable/disable interrupts
atomic test and set instruction
n-process mutual exclusion algorithms (e.g., bakery)
5. For the following set of processes:
P1:: P2: P3:
P(mutex1) P(mutex1) P(mutex2)
P(mutex2)P(mutex2) P(mutex1)
V(mutex1)V(mutex2) V(mutex1)
V(mutex2)V(mutex1) V(mutex2)
a)[5pts] Describe a situation when there is a deadlock. List what processes are in this deadlock.
SOLUTION: an example with just P1 (or P2) and P3 would be sufficient.
b)[5pts] If only processes P1 and P2 existed, would there be a deadlock? Why or why not?
SOLUTION: a problem with just P1 and P2 would not lead to deadlocks, since the resources are ordered (first mutex1 and then mutex2), therefore a form of deadlock prevention.
6. [10pts] There is a bridge across a crocodile-infested river. Halfway across is a platform with a pile of gold bricks on it. The only way to reach the gold is to go through a gate, walk onto the bridge, collect one gold brick, and return to the gate. The gate is initially open, but if a person walks onto the bridge without first ensuring that another person is holding the gate open, then the gate will slam shut, and the person on the bridge will starve. Also, if two or more people are on the bridge at the same time, the bridge will break, and the crocodiles will NOT starve! After a person takes the last gold brick, no other people should walk on the bridge. You have available the following atomic functions (that is, you do not have to write these functions):
start_holding_gate (), stop_holding_gate (), and cross_bridge_and_get_gold ()
A person is considered to be holding the gate if and only if s/he has called start_holding_gate and has not subsequently called stop_holding_gate . The cross_bridge_and_get_gold function returns TRUE if and only if there is still more gold. HINT: You do not have to keep track of how many bricks there are, just trust that the function returns the correct value for you.
A number of people will come to get gold. You must write a function for each person to call. It must be ensured that everyone who arrives (except the last) will get one gold brick. Also, your function should ensure that if enough people come, nobody will be left waiting forever. You must use semaphores. You can initialize the semaphores to any values you like, and you may make assumptions about the scheduling of processes waiting on semaphores. These assumptions must be clearly stated. No busy-waiting allowed.
SOLUTION:
semaphores: bridge = 1; gate = -1.
each person will do:
{
start_holding_gate();
V(gate);
P(gate);
stop_holding_gate();
P(bridge);
cross_and_get_gold();
V(bridge);
}