src/sicp/ex3_46.rkt

   1 #lang racket
   2
   3 (define (test-and-set! cell)
   4   (if (car cell)
   5       true
   6       (begin (set-car! cell true)
   7              false)))
   8 #|
   9
  10 If there are two concurrent processes doing the above test-and-set! function,
  11 there could be many things that can happen.
  12
  13 Assume that the cell is having a #f value initially. Process 1 tests the
  14 value and finds that it is false. At the same instant, Process 2 also tests
  15 the cell and finds that it is false and both of them set the cell to true at
  16 the same instant. Both the processes get a false value from test-and-set!
  17 and think that they are holding the mutex.
  18
  19 Another scenario is when the Process 1 does the test and then finds that the
  20 cell is false. Next Process 2's test is executed and it also finds that the
  21 cell is false. Now, both of them proceed to do a set and so both gets the
  22 mutex.
  23
  24 In reality, only one of the processes should hold a mutex (Mutual exclusion).
  25 So, that assumption is violated in this case. As footnote 47 indicate, if the
  26 instruction that atomically implement test-and-set! is executed at the same
  27 cycle by two separate concurrent processes, a hardware arbiter resolves who
  28 gets the chance to execute it.
  29
  30 |#