|
學生：Murphy Chen Chapter 6Exercise 6.3& The first known correct software solution to the critical-section problem for two processes was developed by Dekker. The two processes, P0 and P1, share the following variables: The structure of process Pi(i=0 or 1), with Pj(j=1 or 0) being the other process, is shown below. Prove that the algorithm satisfies all three requirements for the critical-section problem.
until false;
! We need to show that:
To prove property 1, we note that each Pi enters its critical section only if flag[j]:=false. Also note that, if both processes can be executing in their critical sections at the same time, then flag[0]=flag[1]=true. And then, both Pi and Pj will wait in the while loop (ie. while flag[j]), because flag[0]=flag[1]=true. And one of Pi or Pj will execute the do if statement (ie. do if turn=j), but not both, since the value of turn can be either 0 or 1. Assume Pi execute the do if statement (ie. assume turn=j ), then it will first set flag[i] to false. And now Pj can leave its while loop, and enter its critical section. Now Pi will wait in the second while loop (ie. while turn=j do no-op;) until Pj has finished its job in the critical section and set turn to i, and flag[j] to false. Now since turn=i, Pi can leave its second while loop (ie. while turn=j do no-op), and it will set flag[i] to true so that Pj can not enter the critical section. And since now the value of flag[j] is false, Pi can enter its critical section now. Whenever one process is in the critical section, the other process must wait in the while loop. So, mutual exclusion is preserved.
To prove property 2 & 3, we note that a process Pi can be prevented from entering the critical section only if it is stuck in the while loop with the condition flag[j]=true. If Pj is not ready to enter the critical section, then flag[j]=false, and Pi can enter its critical section. If Pj has set flag[j]=true and is also executing in its while statement, then either turn=i or turn=j. If turn=i, then Pj will set flag[j] to false and wait until turn=j, at this time Pi can enter its critical section. After Pi leave its critical section, it will set turn to j, flag[i] to false, so that Pj can now enter its critical section. If turn=j, then Pi will set flag[i] to false and wait until turn=i, at this time Pj can enter its critical section. After Pj leave its critical section, it will set turn to i, flag[j] to false, so that Pi can now enter its critical section. Thus Pi will enter the critical section (progress) after at most one entry by Pj (bounded-waiting).
Exercise 6.4& The first known correct software solution to the critical-section problem for n processes with a lower bound on waiting of n-1 turns, was presented by Eisenberg and McGuire. The processes share the following variables: All the elements of flag are initially idle; the initial value of turn is immaterial (between 0 and n-1). The structure of process Pi is shown below. Prove that the algorithm satisfies all three requirements for the critical-section problem.
until false;
! To prove that the mutual-exclusion requirement is met, we note that process Pi can enter its critical section only if (j³ n) and (turn=i or flag[turn]=idle). Note that j³ n implies that flag[0],flag[1],...,flag[n-1] , except flag[i], is not equal to in-cs. This implies that P0,P1,...,Pn-1, except Pi, is not currently in the critical section. After Pi has successfully entered its critical section, it has set flag[i] to in-cs, so other processes will not be able to increase thier j until j=n, preventing them from enter their critical sections.
To prove the progress requirement, we note that a process Pi can be prevented from entering the critical section only if it is stuck in the repeat-until loop with the condition j³ n and (turn=i or flag[turn]=idle). Note that when there is no process executing in the critical section, we can have j=n. Also note that since a process Pk exiting the critical section set turn to some value correspoing the processes which are waiting to enter the critical section and set flag[k] to idle. This allows processes which are waiting to enter the critical section to proceed.
To prove bounded waiting, we note that, when a process Pk exiting the critical section will set turn to the next process which is not idle in the cyclic ordering (k+1, k+2, .., n-1, 0, ..., k), and set flag[k] to idle. It designates the first process in this ordering that is in the entry section as the next one to enter the critical section. Any process waiting to enter its critical section will thus do so within n-1 turns, maintaining the bounded waiting requirement.
Exercise 6.9& Demonstrate that monitors, conditional critical regions, and semaphores are all equivalent, insofar as the same types of synchronization problems can be implemented with them.
!
The mutex semaphore provides mutual exclusion for accesses to the buffer pool and is initialized to the value 1. The empty and full semaphores count the number of empty and full buffers, respectively. The semaphore empty is initialized to the value n; the semaphore full is initialized to the value 0. The code for the producer process is shown below:
repeat ... produce an item in nextp ... wait(empty); wait(mutex); ... add nextp to buffer ... signal(mutex); signal(full); until false; The code for the consumer process is shown below:
repeat wait(full); wait(mutex); ... remove an item from buffer to nextc ... signal(mutex); signal(empty); ... consume the item in nextc ... until false;
The buffer space and its pointers are encapsulated in var buffer: shared record pool : array[0..n-1] of item; count, in, out : integer; end; The producer process inserts a new item nextp into the shared buffer by executing region buffer when count < n do begin pool[in] := nextp; in := in+1 mod n; count := count + 1; end; The consumer process removes an item from the shared buffer and puts it in nextc by executing region buffer when count > 0 do begin nextc := pool[out]; out := out+1 mod n; count := count - 1; end;
type buffer = monitor var pool : array[0..n-1] of item;
count := count + 1; pool[in] := nextp; end;
count := count - 1; if count < 0 then empty.wait; end;
in := 0; end.
Producer processes must invoke the operation produce on instance buff of the buffer monitor to produce an item nextp in the buffer pool:
Consumer processes must invoke the operation consume on instance buff of the buffer monitor to consume an item nextc from the buffer pool:
In the first readers-writers problem, it is required that no reader will be kept waiting unless a writer has already obtained permission to use the shared object. In other words, no reader should wait for other readers to finish simply because a writer is waiting.
The reader processes share the following data structures: var mutex, wrt : semaphore; readcount : integer; The semaphores mutex and wrt are initialized to 1; readcount is initialized to 0. The semaphore wrt is common to both the reader and writer processes. The mutex semaphore is used to ensure mutual exclusion when the variable readcount is updated. Readcount keeps track of how many processes are currently reading the object. The semaphore wrt functions as a mutual exclusion semaphore for writers. It also is used by the first or last reader that enters or exits the critical section. The code for a writer process is shown below:
wait(wrt); ... writing is performed ... signal(wrt);
The code for a reader process is shown below:
wait(mutex); readcount := readcount + 1; if readcount = 1 then wait(wrt); signal(mutex); ... reading is performed ... wait(mutex); readcount := readcount - 1; if readcount = 0 then signal(wrt); signal(mutex);
The reader and writer processes share the following data structures: var file : shared record data : item; wrt : boolean; readcount : integer; end; The boolean variable wrt is initialized to false; readcount is initialized to 0. The code for a writer process is shown below: region file when wrt = false do begin wrt = true; ... write data into disk ... wrt = false; end; The code for a reader process is shown below: region file when wrt = false or readcount > 0 do begin readcount = readcount + 1; if readcount = 1 then wrt = true; end; ... read data from disk ... region file when wrt = false or readcount > 0 do begin readcount = readcount - 1; if readcount = 0 then wrt = false; end;
The synchronization between reader processes and writer processes are controlled by the monitor shown below:
Type file = monitor var readcount : integer;
mutex.wait; readcount := readcount + 1; if readcount = 1 then wrt.wait; readcount := readcount - 1; if readcount = 0 then wrt.signal; wrt.wait; begin
The shared data are shown below:
The variable state[0..4] are initalized to thinking; self[0..4] and mutex are all initialized to 1.
wait(mutex); state[i] := hungry; end else
wait(mutex); state[i] := thinking;
if state[k+4 mod 5] ¹ eating
Philosopher i must invoke the operations pickup and putdown in the following sequence:
The shared data are shown below: The variable state[0..4] are initalized to thinking.
region dp when true do begin end;
region dp when true do begin end;
if state[k+4 mod 5] ¹ eating
Philosopher i must invoke the operations pickup and putdown in the following sequence:
3. Using monitors.
The distribution of the chopsticks is controlled by the monitor shown below:
type dining-philosophers = monitor
state[i] := hungry;
state[i] := thinking;
if state[k+4 mod 5] ¹ eating
for i := 0 to 4
Philosopher i must invoke the operations pickup and putdown on an instance dp of the dining-philosophers monitor in the following sequence:
Exercise 6.21& Show that the two-phase locking protocol ensures conflict serializability.
! In the growing phase, a transaction locks whatever data items it will manipulate, if at the same time, other transactions want to manipulate the same data items, they will not be able to do so, because the data items have been locked by the first transaction. Only after the first transaction finish manipulating all its data items, and go into the shrinking phase to unlock all the data items it has locked, can other transactions start to manipulate their data items. So, in this way, the two-phase lock protocol ensures conflict serializability.
Chapter 7Exercise 7.6& In a real computer system, neither the resources available nor the demands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, new resources are bought and added to the system. If deadlock is controlled by the banker’s algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances?
! Increasing Available, decreasing Max for one process, and decreasing the number of processes would all be safe when the system has been already in the safe state.
Decreasing Available, increasing Max for one process, and increasing the number of processes would be safe only if after making those changes the system will be still in the safe state.
Exercise 7.11& Consider the following snapshot of a system:
Answer the following questions using the banker’s algorithm:
& a. What is the content of the matrix Need ?
!
& b. Is the system in a safe state ?
! Yes. Using the safety algorithm, we will find that the sequence <P0,P3,P2,P1,P4> satisfies the safety criteria.
& c. If a request from process P1 arrives for (0,4,2,0) can the request be granted immediately ?
! To decide whether this request can be immediately granted, we first check that Request1 £ Available (that is, (0,4,2,0) £ (1,5,2,0)), which is true. We then pretend that this request has been fulfilled, and we arrive at the following new state:
We must determine whether this new system state is safe. To do so, we execute our safety algorithm and find that the sequence <P0,P2,P1,P3,P4> satisfies our safety requirement. Hence, we can immediately grant the request of process P1.
Exercise 7.15& Suppose that you have coded the deadlock-avoidance safety algorithm and now wish to implement the deadlock-detection algorithm. Can you do so by simply using the safety algorithm code and redefining Maxi = Waitingi + Allocationi , where Waitingi is a vector specifying the resources process i is waiting for, and Allocationi is as defined in Section 7.5 ? Explain your answer.
! No. Because the first line of the deadlock-avoidance safety algorithm is somewhat different from that of the deadlock-detection algorithm. In the first line of the safety algorithm, Finish[i] := false for i=1,2,...,n. This means the safety algorithm will check every process in the system to see if there exists a safety state. But in the first line of the deadlock-detection algorithm, for i=1,2,...,n, if Allocation¹ 0, then Finish[i]:=false; otherwise, Finish[i]:=true. This means the deadlock-detection algorithm will check only the processes that have been allocated resources to detect whether the system is in a deadlocked state.
From the second line to the last line of the safety algorithm and the deadlock-detection algorithm, they are both equivalent, we only need to replace Needi in the safety algorithm and Requesti in the deadlock-detection algorithm with Waitingi.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
