Wrong CS solution

 

Process[i]

 

 

 

flag[i] := true;

while flag[j] do no-op

  CS

 

flag[i] := false;

 

------------------------------------------------

Right CS Solution (Peterson)

 

 

Process[i]

 

flag[i] := true;

turn := j;

while (flag[j] and turn = j) do no-op;

 

   CS

 

 

flag[i] := false

 

Bakery Algorithm

 

choosing[i] := true;

  num[i]:=max(num[0],num[1]...num[n-1])+1;

choosing[i] := false;

 

for j:= 0 to n-1 do  begin

    while choosing[j] do no-op;

    while (num[j]<>0  and

            (num[j],j)<(num[i],i) do no-op;

    end;

 

CS

 

 

num[i] := 0;

 

 

-------------------------------------------

N-process MUTEX solution – pseudo code (Real code in book, end of chapter)

 

 

  flag[i] = want-in;

  from j = turn to i

     scan for not idle processes

     and wait if found.

 

  flag = in-cs;

  from j=0 to n-1

     find a process that is "in-cs"

 

until (NO process found above.)

 

 

---------------------------------------------

 

Hardware solution with Test and Set (TSET instruction)

 

initialization: 

       lock := 0;  // lock := false;

 

 

   A:  TSET lock // test and set lock

       BRNZ A:   // if true, goto A:

       CS

 

      lock := 0;

 

 

-----------------------------------------------------

 

Hardware solution with Bounded Waiting, using TSET (N Process)

GLOBAL: waiting[N],

LOCAL j;

 

   waiting[i] := true

A: if (waiting[i]) do TSET lock

                      BRNZ  A:

   waiting[i] := false

       CS

 

   j := (i+1) mod N;

   while (j<>i) and (not waiting[j]) do

            j := (j+1) mod N

   if i=j then lock := false 

       else waiting[j] := false;

 

----------------------------------------------

 

 

SEMAPHORE DEFINITIONS

 

InitSem (sem, i) ->

               sem := i;

 

Note: Blue, Underline = ATOMIC

 

 

P(sem) ->

 

       A: if sem > 0 then

             sem := sem - 1;     

          else  goto A:

 

 

 

V(sem) ->   sem := sem + 1;

 

 

------------------------------------------

 

Producer-Consumer Skeleton

 

Producer:

  repeat

      produce an item;

       buffer[in] := item;

       in:=(in+1)mod N;

  until false;

 

 

 

Consumer:

  repeat

     item :=buffer[out];

     out:=(out+1)mod N;

     consume the item;

  until false;

 

-------------------------------------------------

Producer-Consumer – Solution

 

 

Producer:

repeat

   produce
   an item;

   P(empty);
   P(mutex)

      add item
      to buffer;

   V(mutex);
   V(full);

  until false;

 

 

Consumer:

repeat

   P(full);
   P(mutex)

      get item
      from buffer;

   V(mutex);   
   V(empty);

   consume the
   item;

until false ;

 

------------------------------------------------

 

Semaphore – Blocking Implementation

type semaphore = record

              value : integer;

              Q : list of processes;

           end;

 

 

 

P(

sem) : ->

  sem.value := sem.value - 1;

  if sem.value < 0 then

          begin

            add this process to sem.Q;

            block; 

          end;

 

V(sem) : ->

  sem.value := sem.value + 1;

  if sem.value <= 0 then

    begin

       remove a process from sem.Q and

       place it in the ready Q.
   end;