each: acquire() and release(). You can assume that the application calls lock.acquire()
before entering a critical section and lock.release() after exiting the critical section. For the
implementations that require a tid (i.e., thread id), you can assume that the tid of each thread is
either 0 or 1.
class LockA { private int turn = 0; public void acquire(int tid) { while (turn == (1 - tid)); } public void release(int tid) { turn = (1 - tid); } } | class LockB { public void acquire() { disableInterrupts(); } public void release() { enableInterrupts(); } } |
For each lock, answer the following three questions. Be sure that your answers clearly indicate
whether you are referring to LockA or LockB.
(a) Does the code guarantee mutual exclusion? (Simply answer yes or no)
(b) Does the code guarantee progress? (Simply answer yes or no)
(c) List all other limitations that exist for each implementation. Issues you might consider
include (but are not limited to) the following: generality, efficiency, and fairness. (Note: You
can skip this part of the quetion when the implementation fails to provide mutual exclusion
or progress.)
Answer
LockA (a) Yes, guarantees mutual exclusion; only the thread with tid matching turn is able to
acquire the lock. (b) No, does not guarantee progress; if thread 0 never tries to acquire the lock
(it is executing other code), thread 1 will not be able to acquire the lock. (c) Limitations (Not
required): Only works with two processes, uses busy waiting.
LockB (a) Guarantees mutual exclusion on a uniprocessor, but not on a multiprocessor. On a
uniprocessor, once the timer interrupt is disabled, the scheduler won’t be able to switch to another
process (assuming the scheduled process doesn’t voluntarily relinquish the CPU). However, on
a multiprocessor, it is possible for the other CPU to be running a process that also acquires the
lock. (b) Yes, guarantees progress; once a process is scheduled, it is able to acquire the lock without
incident. (c) Limitations: Only works on uniprocessors; allows user processes to disable interrupts
for an arbitrary long period; cannot service other important interrupts during critical section (e.g.,
I/O); cannot schedule any other processes when lock is held, even those not contending for the
lock.
Also answer the following general question: Locks are often implemented by maintaining a list of processes (or threads) that are waiting to acquire the lock. What are all of the advantages of this approach (compared to a correct implementation of a lock that does not use a list)?
fairness and efficiency. Fairness comes from the fact that the queue can provide the lock to the
processes in the order they request it. Efficiency comes from the elimination of the spin lock, and
reliance on a notification mechanism to wake-up a process.
_______________________________________________________________
Suppose two processes compete for access to a critical section using simple spin locks. Prior to entering the critical section, the process executes the following:
while (TAS(t)); and after exiting the critical section it executes t=1.
(a) Suppose a priority scheduler where high priority processes always execute before any
lower priority processes. Can the described scheme lead to deadlock? If no, why not. If yes,
describe a case.
Yes, deadlock is possible. If a low priority process acquires the lock. Then a high priority
process starts, gets the processor and requests the lock. The high priority process will keep
the processor, spinning on the lock that the low priority process is holding. Because the low
priority process cannot get the processor, it cannot release the lock, and we have a deadlock
scenario.
(b) Suppose a round robin scheduler. Can the described scheme lead to deadlock? If no, why not. If yes, describe a case.
No, deadlock is not possible. A round robin, preemptive scheduler will alternate among
processes, so every process will have a chance to execute, and eventually the holding process
will release the lock.
_______________________________________________________________
Fix the following code to avoid the possible deadlock:
| acquire(L1) acquire(L2) release(L2) release(L1) | acquire(L2) acquire(L1) release(L1) release(L2) |
You could have changed this many ways. One possibility is to remove circular wait and
make both processes acquire the resources in the same order. Another possibility is to remove
hold-and-wait and have the processes release the first resource before they acquire another.
Although this changes the semantics of the program, I accepted it as a solution.
----------------------------------------------------------------------------------------------------------
Suppose a program has three threads Thread1, Thread2, and Thread3, and a
shared counter, count, as shown below:
int count = 10;
Semaphore Lock = 1; // initial value is 1
| Thread1(...) { // do something Lock.Wait(); count++; Lock.Signal(); } | Thread2(...) { // do something Lock.Wait(); count−−; Lock.Signal(); } | Thread3(...) { // do something Lock.Wait(); printf(‘‘$d’’, count); Lock.Signal(); } |
9, 10, 11
_______________________________________________________________________________________________
Consider a system with two preemptively scheduled threads. One thread executes the WriteA function
shown below. The other executes the WriteB function, also shown below. Both functions use kprintf
to produce console output. The random function called by WriteA returns a randomly-generated nonnegative
integer. WriteA and WriteB are synchronized using two semaphores, Sa and Sb. The intial
value of both semaphores is zero. Assume that the individual calls to kprintf are atomic.
| WriteA() { unsigned int n,i; while(1) { n = random(); for(i=0;i<n;i++){ kprintf(‘‘A’’); } for(i=0;i<n;i++) { V(Sb); } for(i=0;i<n;i++) { P(Sa); } } | WriteB() { while(1) { P(Sb); kprintf(‘‘B’’); V(Sa); } } |
a.
Consider the following 10-character console output prefixes. (Each prefix shows the first 10 characters
printed to the console.) Which of these prefixes could possibly be generated by the two
threads running in this system? Write “YES” next to the output prefix if it could be generated,
otherwise write “NO”.
• ABABABABAB YES
• BABABABABA NO
• AAAAAAAAAA YES
• AAABABABAB NO
• AAABBBBAAB NO
• AAAAAABBBB YES
• AAABBBAABB YES
• BBBBBAAAAB NO
b.
Suppose that the initial value of semaphore Sb is 1, rather than 0. Show a 10-character console
output prefix that could be generated in that case, and that could not be generated if the initial
value of Sb were 0.
Some examples:
• BABABABABA
• ABABBABABAB
• AAABBBABABB
__________________________________________________________________
Below is an attempted solution for producer- consumer problem. What problems can arise using this solution?
Buffer size = N
int count = 0;
| consumer: while(true){ if(count==0) sleep( ); //remove from buffer count--; if(count ==N-1) wakeup(producer); consume(item) } | producer: while(true){ produce(item); if(count==N) sleep( ); //produce into buffer count++; if(count ==1) wakeup(consumer); consume(item) } |
Answer:
- Consumer checks count==0
- before going to sleep consumer is preempted
- Producer increments count to 1
- producer wakes up consumer.
- since consumer is not sleeping yet, wakeup call is lost.
- Producer fills the buffers until count == N and goes to sleep
- Both processes are deadlocked.
___________________________________________________________________________________
Consider three concurrently executing threads in the same process using two semaphores
s1 and s2. Assume s1 has been initialized to 1, while s2 has been initialized to 0.
What are the possible values of the global variable x, initialized to 0, after all three threads have terminated?
/* thread A */ P(&s2); P(&s1); x = x*2; V(&s1); | /* thread B */ P(&s1); x = x*x; V(&s1); | /* thread C */ P(&s1); x = x+3; V(&s2); V(&s1); |
The possible sequences are B,C,A (x = 6) or C,A,B (x = 36) or C,B,A (x = 18).
________________________________________________________________
We explore the so-called barbershop problem. A barbershop consists of a n waiting chairs
and the barber chair. If there are no customers, the barber waits. If a customer enters,
and all the waiting chairs are occupied, then the customer leaves the shop. If the barber
is busy, but waiting chairs are available, then the customer sits in one of the free chairs.
Here is the skeleton of the code, without synchronization.
extern int N; /* initialized elsewhere to value > 0 */
int customers = 0;
void* customer() {
if (customers > N) {
return NULL;
}
customers += 1;
getHairCut();
customers -= 1;
return NULL;
}
void* barber() {
while(1) {
cutHair();
}
}
13
For the solution, we use three binary semaphores:
• mutex to control access to the global variable customers.
• customer to signal a customer is in the shop.
• barber to signal the barber is busy.
1. (5 points) Indicate the initial values for the three semaphores.
• mutex
• customer
• barber
2. (15 points) Complete the code above filling in as many copies of the following commands
as you need, but no other code.
P(&mutex);
V(&mutex);
P(&customer);
V(&customer);
P(&barber);
V(&barber);
Solution: Initial values are mutex = 1 (variable customers may
be accessed), customer = 0 (no customers) and barber = 0 (barber is not busy).
void* customer() {
P(&mutex);
if (customers > N) {
V(&mutex);
return NULL;
}
customers += 1;
V(&mutex);
V(&customer);
P(&barber);
getHairCut();
P(&mutex);
customers -= 1;
V(&mutex);
return NULL;
}
void* barber() {
while(1) {
P(&customer);
V(&barber);
cutHair();
}
}
________________________________________________________________
No comments:
Post a Comment