Busy Waiting - Exercise 4
The fourth attempt mutex4
is safe but still suffers from livelock.
While Dekker's algorithm resolves livelock arising from everyone
trying to simultaneously enter their critical section it does
not cure everything.
In particular the livelock/crashing discussed in the first attempt
is still not resolved by Dekker.
The exercise is to take
mutex1 and
use the following algorithm to lessen the potential problems
of the baton holder livelocking or crashing in its critical section.
The algorithm is not intended to resolve the problem but just
help a bit.
Each baton holding process is now to have a fixed amount of time to
complete its critical section and surrender the baton.
If it does not then it is assumed to have `died' and will never
again be assigned the baton.
Clearly safety could be jeopardised if a dormant baton holder
became active after a prolonged pause, but we are making the
simplifying assumption that no process could possibly take more than
a fixed amount of time to complete its critical section.
Note that this algorithm is making a tradeoff between safety and
livelock/crashing.
See what you can do with it.