1. Solution 1.
COMP 2432 Operating Systems Tutorial 12
Consider the first solution of the shared railway section problem for . The solution could be translated into a concurrent program with 2 processes as below. Show a possible sequence of events (with statement number) that have happened to cause these incidents: (a) a train being blocked forever, (b) collision of the trains. Note that there are many possible answers.
Initially, flag = false
Copyright By PowCoder代写 加微信 powcoder
(a) Time PBolivia PPeru 0
(b) Time 0
PBolivia PPeru flag false
while (true) do {
1: while (flag) do;
2: flag = true;
3: < critical section > 4: flag = false;
5: < remainder section > }
while (true) do {
1: while (flag) do;
2: flag = true;
3: < critical section > 4: flag = false;
5: < remainder section > }
1111 22 true 2 313 44 55 66 77 88 99
2. Solution 2.
Consider the second solution proposed by the PolyU student. Express it as a concurrent program. Show a sequence of possible events in the context of your program that have occurred in a scenario that the Peruvian train has to wait for the Bolvian train to pass before it can take a second turn to pass the shared track.
Initially, flag = false
PBolivia PPeru
while (true) do {
while (true) do {
flag Time false 10 11 12 13 14 15 16 17 18 19
Time PBolivia 20
PPeru flag
Solution 3.
Consider the third solution using two bowls. Complete the concurrent program for the Peruvian train. Show a sequence of possible events on (a) how the Peruvian train can run twice a day and the Bolvian train can run once a day, (b) how a livelock has occurred that both trains are blocked.
Initially, flag[0] = false and flag[1] = false
while (true) do {
while (true) do {
flag[0] = true;
if (flag[1] == false) then
else flag[0] = false;
< critical section >
flag[0] = false;
< remainder section >
while (true) do {
Time PBolivia PPeru 0
flag[0] flag[1] false false
(b) Time 0
flag[0] false
flag[1] false
111 22 33 44 55 66 77 88 99
4. Critical Section Problem.
Consider McDull¡¯s modification to Peterson¡¯s algorithm to the critical section problem for two processes P1 and P2, by making processes more ¡°selfish¡±. Initially, both flag[1] and flag[2] are false and turn = 1.
Program for P1 Program for P2
McMug points out that the new solution proposed by McDull is incorrect with respect to mutual exclusion and bounded waiting, but correct with respect to progress. Give a scenario with a sequence of events to show how the mutual exclusion property is violated. Give another scenario with a sequence of events to show how the bounded waiting property is violated. Give a final sequence of events as examples that the progress property still holds.
ME Time P1 P2 flag[1] flag[2] turn Time P1 P2 flag[1] flag[2] turn 0 false false 1 8 19
3 11 4 12 5 13 6 14 7 15
PG Time P1 P2 flag[1] flag[2] turn Time P1 P2 flag[1] flag[2] turn
while (true) do {
1: flag[1] = true;
while (true) do {
1: flag[2] = true;
2: turn = 1;
2: turn = 2;
3: while (flag[2] and turn==2) do { };
4: < critical section >
5: flag[1] = false;
6: < remainder section >
3: while (flag[1] and turn==1) do { };
4: < critical section >
5: flag[2] = false;
6: < remainder section >
1 13 14 15 16 17 18 19 20 21 22 23 24 25
BW Time P1 P2 flag[1] flag[2] turn Time P1 P2 flag[1] flag[2] turn
1 10 14 15 16 17 18 19 20 21 22 23 24 25
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com