The basic idea behind the implementation of Dekker’s algorithm is that a process
enters the critical section—further (CS) straight away when the other process is not
competing for CS.
When both processes are simultaneously interested in accessing CS, the tie is
broken by allowing the process which accessed CS least recently to succeed.
The algorithm uses three binary variables, cl, c2, and turn.
For better readability, we rename the first two variables, respectively, as state [l]
and state [2].
Also, we define turn as “other”, that may take value either 1 or 2, while status
out as 0, and status of competing as 1.
The status bits are initialized to “out”. The formal, pseudocode of mutual
exclusion is presented in Fig. 12.7. Another few hundreds of versions of the similar
code are everywhere starting from Wikipedia and ending every second Ph.D. on the
subject in the world and, therefore there is no need to refer to any authorship here—
this is public domain knowledge.
mutual exclusion must be implemented - only one process must be permitted
to be within critical section;
conflict resolution for simultaneous requests, with one process to go through
into the critical section; also called liveliness - if several processes request
and entry one of them get access
independence from processes demand from outside critical section
deadlock free - no process to block each other
starvation free - bounding - system does not let a process to wait forever;
each process will get its time in critical section
Fig. 12.4 Synchronization rules
efficient; in other words do not consume substantial resources from the system
or processes to arrange a process of waiting
progress: no process is forced to wait for an available resource -- otherwise
very wasteful at a time;
do not implement busy wait - i.e. endless knocking the closed door is
forbidden;
Fig. 12.5 Synchronization rules—desirable
184
12 Proposed Runtime System Structure …
enters the critical section—further (CS) straight away when the other process is not
competing for CS.
When both processes are simultaneously interested in accessing CS, the tie is
broken by allowing the process which accessed CS least recently to succeed.
The algorithm uses three binary variables, cl, c2, and turn.
For better readability, we rename the first two variables, respectively, as state [l]
and state [2].
Also, we define turn as “other”, that may take value either 1 or 2, while status
out as 0, and status of competing as 1.
The status bits are initialized to “out”. The formal, pseudocode of mutual
exclusion is presented in Fig. 12.7. Another few hundreds of versions of the similar
code are everywhere starting from Wikipedia and ending every second Ph.D. on the
subject in the world and, therefore there is no need to refer to any authorship here—
this is public domain knowledge.
mutual exclusion must be implemented - only one process must be permitted
to be within critical section;
conflict resolution for simultaneous requests, with one process to go through
into the critical section; also called liveliness - if several processes request
and entry one of them get access
independence from processes demand from outside critical section
deadlock free - no process to block each other
starvation free - bounding - system does not let a process to wait forever;
each process will get its time in critical section
Fig. 12.4 Synchronization rules
efficient; in other words do not consume substantial resources from the system
or processes to arrange a process of waiting
progress: no process is forced to wait for an available resource -- otherwise
very wasteful at a time;
do not implement busy wait - i.e. endless knocking the closed door is
forbidden;
Fig. 12.5 Synchronization rules—desirable
184
12 Proposed Runtime System Structure …