CIS343|510                     Chapter 5B/6 Review

 

1. Which of these mutual exclusion implementations using messages is correct?

  a.  program mutual exclusion;                     b.  program mutual exclusion;

       const  n = . . . ; (num procs)                           const  n = . . . ; (num procs)

       procedure P(i: integer);                                   procedure P(i: integer);           

       var msg: message;                                          var msg: message;

       begin                                                              begin

            repeat                                                           repeat                                                         

            send(mutex,msg);                                             receive(mutex,msg);

            < CS >                                                             < CS >

            receive(mutex,msg);                                          send(mutex,msg);

            < remainder >                                                      < remainder >

      forever                                                                forever                                    

      begin (main program)                                          begin (main program)

        create_mailbox(mutex);                                            create_mailbox(mutex);

        send(mutex,null);                                                      send(mutex,null);

        parbegin . . parend                                                   parbegin . . parend

      end.                                                                    end.

 

2. For the correct version of the above, which of the combinations given below is assumed?

          a. blocking receive primitive                blocking send primitive

          b. blocking receive primitive                nonblocking send primitive

          c. nonblocking receive primitive          blocking send primitive

          d. nonblocking receive primitive          nonblocking send primitive

 

3. Which of these combinations is known as a rendezvous?

 

4. Which of these solutions to bounded buffer producer/consumer using messages is correct?

  a.  procedure producer;                                      procedure producer;        

       var pmsg: message;                                       var pmsg: message;

       begin                                                              begin

            while true do                                                 while true do

                begin                                                                begin

                        receive(mayproduce,pmesg)                           receive(mayconsume,pmesg)

                        pmsg = produce;                                            pmsg = produce;

                        send(mayconsume,pmesg)                              send(mayproduce,pmesg)

                 end                                                                   end

            end;                                                                  end;

 

      procedure consumer;                                      procedure consumer;        

       var cmsg: message;                                       var cmsg: message;

       begin                                                              begin

            while true do                                                 while true do

                begin                                                                begin

                        receive(mayconsume,cmesg)                           receive(mayconsume,cmesg)

                        consume(cmsg);                                               consume(cmsg);

                        send(mayproduce,null)                                     send(mayproduce,cmesg)

                 end                                                                   end

            end;                                                                  end;

 

      begin (parent)                                                    begin (parent)

        create_mailbox(mayproduce);                             create_mailbox(mayproduce);

        create_mailbox(mayconsume);                            create_mailbox(mayconsume);

        for i:=1 to capacity                                              for i:=1 to capacity

            send(mayproduce,null);                                      send(mayconsume,null);

        parbegin                                                             parbegin

            producer;                                                          producer;

            consumer;                                                         consumer;

       parend                                                                parend

      end.                                                                 end.

 

5. Which of these are conditions for that must be satisfied in the classic readers/writers problem?

            a. Only one reader at a time may read a file.

            b. Only one writer at a time may write to a file.

            c. Any number of writers may simultaneously write to a file.

            d. Any number of readers may simultaneously write to a file.

            e. If a writer is writing to a file, no reader may read it.

            f. If a reader is reading a file, no writer may write to it.

 

With respect to the readers/writers solution of Fig. 5.28 . . .

6. What is the purpose of semphore x?

 

7. What is the purpose of semphore wsem?

 

8. Is one class of processes given priority over another class?  Which one?

 

9. What are the implications of that?

 

 

With respect to the readers/writers solution of Fig. 5.29 . . .

10. What is the purpose of semphore rsem?

 

11. What is the purpose of semphore wsem?

 

12. What is the purpose of variable writecount?

 

13. What is the purpose of semaphore y?

 

14. What is the purpose of semaphore x?

 

15. What is the purpose of semaphore z?

 

16. Assume that the read/write file has no readers or writers.  Suppose in a burst (for all practical purposes, sumultaneously) the following arrived:

          R1 - W1 - R2 - W2- R3 - R4 - W3

Give the values of readcount & writecount and the contents of all the semaphore queues at the point in time that the first process accesses the file.  Also, give the order of access to the file, assuming FIFO implementation of semaphore queues.

 

17. Which of the following do you see as advantages of the solution in Fig. 5.30 over the one in Fig. 5.29?

          a. Readers in 5.30 have priority over writers, but not in 5.29

            b. Writers in 5.30 have priority over readers but not in 5.29

            c. 5.30 cannot have deadlock, but 5.29 can

            d. The difficult code is given to the controller, not the reader & writer

            e. 5.30 has lock step synchronization, but 5.29 does not

 

Chapter 6 Review

Identify these necessary conditions for deadlock:

18. A process may hold allocated resources while awaiting assignment of others.

 

19. A closed chain of processes exists.

 

20. Only one process may use a resource at a time.

 

21. No resource may be forcefully removed from a process holding it.

 

Identify the condition being prevented in these deadlock prevention strategies:

22. A process holding a resource must surrender it when denied a further request.

 

23. In general, this condition cannot be disallowed.

 

24. Resource types have a linear ordering.  Resource requests must be made in the specified order.

 

25. A process must make all its resource requests at one time.

 

26. A resource requested by one process may be taken from the process holding it.

 

Identify these deadlock avoidance strategies:

27. Grant a request only if the result of the grant is a safe state.

 

28. Start a process only if the maximum claims of all current processes plus those of the new process can be met.

 

29. Rank these in order, from most conservative to least.

            a. Deadlock detection & recovery

            b. Deadlock prevention

            c. Deadlock avoidance

 

Classify each of these in one of the categories listed immediately below:

            DP.             Deadlock prevention

            DA.             Deadlock avoidance

            DDR.             Deadlock detection & recovery

            IDS.             Integrated deadlock strategy

30. Do not start a process if its demands might lead to deadlock.

 

30. Deny the hold and wait condition

 

31. Successively preempt until deadlock no longer exists.

 

32. Group resources into classes,with linear ordering in each class.  Within any class use the algorithm most appropriate for that class.

 

33. Back up each deadlocked process to some previously defined checkpoint.  Restart all processes.

 

35. A process holding a resource must surrender it when denied a further request.

 

36. Do not grant a resource request if it could lead to deadlock.

 

37. Abort all deadlocked processes.

 

38. Processes must make all resource requests in a predefined order, regardless of the order of actual need by that process.

 

39. Define safe state, according to the Banker’s Algorithm.

 

40. Define unsafe state, according to the Banker’s Algorithm.

 

41. Since in a safe state, there are some sequences of execution that could lead to deadlock, why is it called safe?  I.e., what keeps deadlock from occurring?

 

42. What is the most commonly adopted solution to deadlock recovery?

 

43. Be able to recognize safe & unsafe states.