CIS343 Quiz :: Chapter 5 w/ Answers

Place all answers on answer sheet provided.

1. One of the hardware approaches to the problem of mutual exclusion is to disable interrupts while the process is in its critical section. With this approach, for the uniprocessor . . .

mutual exclusion is guaranteed, but at a high price.

2. But for the multiprocessor . . .

mutual exclusion is not guaranteed

Place all answers on answer sheet provided.

3. Which is the correct definition of test and set?

A. boolean testset (int i)

{

if (i < 0)

{

i = 1;

return false;

}

else

return true;

}

B. boolean testset (int i)

{

if (i = = 0)

{

i = 1;

return true;

}

else

return false;

}

B

4-5. Which of these mutual exclusion implementations are correct?

A. /* program mutualexclusion */ B. /* program mutualexclusion*/

const int n = /*number of processes*/ int const n = /*number of processes*/

int bolt; int bolt;

void P(int i) void P(int i)

{ {

while (true) int keyi;

{ while (true)

while (!testset (bolt)) {

/*do nothing*/: keyi = 0;

/* critical section*/; while (keyi, bolt);

bolt = 0; /* critical section */;

/* remainder */ exchange (keyi, bolt);

} /* remainder */

} }

}

void main ( ) void main ( )

{ {

bolt = 0; bolt = 0;

parbegin (P(1), P(2), . . . , P(n)); parbegin (P(1),P(2), . . . , P(n));

} }

C. /* program mutualexclusion */ D. /* program mutualexclusion*/

const int n = /*number of processes*/ int const n = /*number of processes*/

int bolt; int bolt;

void P(int i) void P(int i)

{ {

while (true) int keyi;

{ while (true)

while (!testset (bolt)) {

/*critical section*/: keyi = 1;

/*do nothing */; while (keyi != 0)

bolt = 1; exchange (keyi, bolt);

/* remainder */ /* critical section */

} exchange (keyi, bolt);

} /* remainder */

}

}

void main ( ) void main ( )

{ {

bolt = 0; bolt = 0;

parbegin (P(1), P(2), . . . , P(n)); parbegin (P(1),P(2), . . . , P(n));

} }

A & D

Below are 6 attempts at a software solution to the mutual exclusion problem. They are referenced in questions xx-yy. Note: Only the code for process P0 is given, as the code for P1 is exactly parallel.

A. /* Process 0 */

. . .

flag[0] = true;

while (flag[1])

/* do nothing */ ;

/* critical section */ ;

flag[0] = false;

. . .

Third Attempt

B. /* Process 0 */

. . .

flag[0] = true;

turn = 1;

while (flag[1]) && turn = = 1) /* do nothing */;

/* critical section */ ;

flag[0] = false;

. . .

Peterson’s Alg

C. /* Process 0 */

. . .

while (turn != 0)

/* do nothing */ ;

/* critical section */ ;

turn = 1;

. . .

First Attempt

D. /* Process 0 */

. . .

flag[0] = true;

while (flag[1])

if (turn = = 1)

{

flag[0] = false;

while (turn = = 1) /* do nothing */;

flag[0] = true;

}

/* critical section */ ;

turn = 1;

flag[0] = false;

. . .

Dekker’s Alg

E. /* Process 0 */

. . .

while (flag[1])

/* do nothing */ ;

flag[0] = true;

/* critical section */ ;

flag[0] = false;

. . .

Second Attempt

F. /* Process 0 */

. . .

flag[0] = true;

while (flag[1])

{

flag[0] = false;

/* delay */

flag[0] = true;

}

/* critical section */ ;

flag[0] = false;

. . .

Fourth Attempt

6. Which of the above programs guarantees mutual exclusion?

1st, 3rd, 4th, Dekker’s & Peterson’s

C, A, F, D, & B

A, B, C, D & F (all except E)

7. Which has busy waiting?

All of them

8. Which has lock step synchronization?

1st one only

C only

9. Which has deadlock (due to mutual rudeness)?

3rd one only

A only

10. Which has livelock (due to excessive mutual courtesy)?

4th one only

F only

11. Which locks out the other process if a process fails outside its critical section?

1st one only

C only

12. Which locks out the other process if a process fails inside its critical section?

All of them

13. Which is Dekker’s Algorithm?

D

14. Which is Peterson’s Algorithm?

B

15-17. What are the 3 types of relationships that can occur between/among concurrent processes?

competition

cooperation by sharing

cooperation by communication

17-20. What are the 3 basic semaphore operations?

initialize

wait(s)

signal(s)