CIS343|510                     Chapter Five Review

 

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

  a.  function testset (var i: integer) : boolean;

       begin

          if i = 0 then

             begin

                i := i - 1;

                testset := false

             end

          else testset := true

       end.

 

  b.  function testset (var i: integer) : boolean;

       begin

          if i = 0 then

             begin

                i := 1;

                testset := true

             end

          else testset := false

       end.

 

2. Which of these mutual exclusion implementations are correct?

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

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

       var  bolt: integer;                                          var  bolt: integer;            

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

       begin                                                              var keyi: integer;

            repeat                                                        begin

               testset(bolt);                                                repeat

               < CS >                                                       keyi := 1;

               <remainder>                                                  repeat

               bolt := 0;                                                           exchange(keyi,bolt) until keyi = 0;

             forever                                                                < CS >

                                                                                        exchange(keyi,bolt);

                                                                                       <remainder>

                                                                               forever

 

 

  c.  program mutual exclusion;                     d.  program mutual exclusion;

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

       var  bolt: integer;                                          var  bolt: integer;            

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

       begin                                                              var keyi: integer;

            repeat                                                        begin

               repeat {nothing} until testset(bolt);            repeat

               < CS >                                                       keyi := 1;

               bolt := 0;                                                     exchange(keyi,bolt);

               <remainder>                                               < CS >

             forever                                                         repeat

                                                                                     exchange(keyi,bolt) until keyi = 0;

                                                                                 <remainder>

                                                                               forever

 

3. Which of these solutions to the infinite buffer producer/consumer problem using binary semaphores is correct?

  a.  procedure producer;                                 b.  procedure producer;

       begin                                                              begin

            repeat                                                           repeat

               produce;                                                        produce;

               waitB(s);                                                        waitB(s);

               append;                                                         append;

               n := n + 1;                                                      n := n + 1;

               if n=1 then signalB(delay);                              if n=1 then signalB(delay);

               signalB(s)                                                      signalB(s);

             forever                                                        forever                        

        end;                                                               end;

        procedure consumer;                                      procedure consumer;

        begin                                                             begin

            waitB(delay);                                                waitB(delay);

            repeat                                                            repeat

               waitB(s);                                                        waitB(s);

               take;                                                              take;

               n := n - 1;                                                       n:= n - 1;

               signalB(s);                                                      m := n;

               consume;                                                        signalB(s);

               if n=0 then waitB(delay)                                 consume;

            forever                                                              if m=0, then waitB(delay)

         end;                                                                  forever

                                                                               end;

 

4. What problem can occur in the incorrect solution?

 

5. Which of these solutions to the infinite buffer producer/consumer problem using semaphores is correct?

  a.  program producerconsumer;                 b.  program producerconsumer;    

       var  n: semaphore (:= 0);                                    var  n: semaphore (:= 0);

              s:  semaphore (:= 1);                                           s: semaphore (:= 1);

       procedure producer;                                      procedure producer;

       begin                                                              begin

            repeat                                                           repeat

               produce;                                                           produce;

               wait(s);                                                             wait(s);

               append;                                                            append;

               signal(s);                                                           signal(s);

               signal(n);                                                           signal(n);

            forever                                                          forever

         end;                                                               end;

       procedure consumer;                                      procedure consumer;

       begin                                                              begin

            repeat                                                           repeat

               wait(s);                                                         wait(n);

               wait(n);                                                         wait(s);

               take;                                                             take;

               signal(s);                                                       signal(s);

               consume;                                                      consume;

            forever                                                          forever

         end;                                                               end;

 

6. What problem can occur in the incorrect solution?

 

7. Which of these implementations of sempahores involve busy waiting?

          a. Dekker’s algorithm               b. Peterson’s algorithm

          c. Test and set                     d. Inhibiting interrupts

 

8. Which of these solutions to the bounded buffer producer/consumer problem using monitors is correct?

  a.  program producerconsumer;                 b.  program producerconsumer;    

       monitor boundedbuffer;                              monitor boundedbuffer;

       buffer: array [0..N] of char;                        buffer: array [0..N] of char;

       nextin, nextout: integer;                                nextin, nextout: integer;

       count: integer;                                             count: integer;

       full, empty: condition;                                   notfull, notempty: condition;

       procedure append(x:char);                           procedure append(x:char);

       begin                                                            begin               

            if count=N then cwait(empty);                    if count=N then cwait(notfull);

            buffer[nextin] := x;                                      buffer[nextin] := x;

            nextin := nextin + 1 mod N;                        nextin := nextin + 1 mod N;

            count := count + 1;                                     count := count + 1;

            csignal(full);                                                csignal(notempty);

        end;                                                             end;

       procedure take(x:char);                                    procedure take(x:char);

       begin                                                                begin               

            if count=0 then cwait(full);                                if count=0 then cwait(notempty);

            x := buffer[nextout]                                          x := buffer[nextout]

            nextout := nextout + 1 mod N;                         nextout := nextout + 1 mod N;

            count := count - 1;                                           count := count - 1;

            csignal(empty);                                                csignal(notfull);

        end;                                                                  end;

        begin                                                                begin

            nextin := 0; nextout := 0; count := 0;                nextin := 0; nextout := 0; count := 0;

        end;                                                                  end;

 

9. Do binary semaphore have the same expressive power as general semaphores?