widget q[N] q-size = 0 head = tail = 0
and the two functions
| 
 | 
 | 
p() and c() in separate threads.
  
| p()andc()have interfering access toq-size.
 | get ri, @q-size get ri, @q-size sub ri, 1 put ri, @q-size add ri, 1 put ri, @q-size get ri, @q-size sub ri, 1 get ri, @q-size add ri, 1 put ri, @q-size put ri, @q-size | 
| \(\vdots\) | 
widget q[N] q-size = 0 head = tail = 0 turn = 'p'
| 
 | 
 | 
widget q[N] q-size = 0 head = tail = 0
| 
 | 
 | 
| 
 | 
 | 
| 
 | 
 | 
| 
 | 
 | 
int turn = 1
boolean involved[2] = { false, false }
involved[i] iff ti is
  waiting to enter or in cs.  
  turn = i means “in case of a tie,
  ti enters the cs.”
  i does (j represents the other thread,
  j = (i + 1) mod 2).
involved[i] = true;
turn = j
while involved[j] && turn ≡ j { }
i does
involved[i] = false;
while involved[j] && turn ≡ j { }
until it falls out.
test-and-set instruction.
    test-and-set is a non-interruptable, non-privileged instruction in
  modern architectures.
    ldstub instruction.
    test-and-settest-and-set is
bool test-and-set(bool * bowl)
bool b = *bowl *bowl = false return b 
test-and-set returns true and the bowl
  is empty.
    test-and-set returns false. 
    test-and-set critical section:
bool bowl-csi = true
enter csi
  while !test-and-set(bowl-csi) { }
exit csi
  bowl-csi = true
bowl is usually called lock.
  | This page last modified on 2014 October 9. |