"One Example of a Hardware Solution to the Critical Section Problem Is"

Return to Contents

Solutions to the Critical Section Problem

Assumption

• assume that a variable (memory location) tin just have ane value; never ``between values''
• if processes A and B write a value to the same memory location at the ``same fourth dimension,'' either the value from A or the value from B will be written rather than some scrambling of bits

Peterson'due south Algorithm

• a simple algorithm that can be run past two processes to ensure mutual exclusion for one resource (say one variable or data structure)
• does not require any special hardware
• it uses busy waiting (a spinlock)

Peterson's Algorithm
Shared variables are created and initialized before either procedure starts. The shared variables flag[0] and flag[1] are initialized to False because neither process is yet interested in the critical section. The shared variable turn is set to either 0 or 1 randomly (or it tin can always exist set to say 0).

var flag: array [0..1] of boolean;

plow: 0..1;
%flag[k] means that process[k] is interested in the disquisitional section

flag[0] := FALSE;

flag[ane] := Simulated;
turn := random(0..1)

After initialization, each process, which is called process i in the code (the other process is procedure j), runs the following code:

echo

flag[i] := TRUE;
plow := j;
while (flag[j] and turn=j) do no-op;
CRITICAL Section
flag[i] := Fake;
REMAINDER SECTION
until FALSE;

Information common to both processes:
turn = 0
flag[0] = FALSE
flag[1] = Simulated

EXAMPLE 1
Process 0	Process ane
i = 0, j = 1	i = 1, j = 0
flag[0] := True turn := 1 check (flag[1] = TRUE and turn = 1) - Status is imitation because flag[1] = FALSE - Since condition is imitation, no waiting in while loop - Enter the critical section - Process 0 happens to lose the processor
	flag[1] := TRUE turn := 0 check (flag[0] = TRUE and turn = 0) - Since status is true, it keeps busy waiting until it loses the processor
- Process 0 resumes and continues until it finishes in the critical section - Leave critical section flag[0] := Simulated - Start executing the remainder (annihilation else a process does too using the critical department) - Process 0 happens to lose the processor
	bank check (flag[0] = TRUE and turn = 0) - This status fails because flag[0] = False - No more busy waiting - Enter the critical section

EXAMPLE 2
Process 0	Process 1
i=0, j=1	i=1, j=0
flag[0] = TRUE plow = 1 - Lose processor here
	flag[ane] := True turn := 0 check (flag[0] = TRUE and turn = 0) - Status is true and then Process 1 decorated waits until it loses the processor
bank check (flag[1] = True and turn = one) - This condition is false because turn = 0 - No waiting in loop - Enters critical section

EXAMPLE 3
Process 0	Process 1
i=0, j=1	i=ane, j=0
flag[0] = True - Lose processor here
	flag[1] = Truthful turn = 0 check (flag[0] = True and plough = 0) - Condition is true then, Process 1 decorated waits until it loses the processor
turn := one bank check (flag[1] = Truthful and turn = 1) - Condition is truthful so Procedure 0 busy waits until it loses the processor
	bank check (flag[0] = TRUE and plow = 0) - The condition is false and so, Procedure 1 enters the critical section

Summary of Techniques for Critical Section Problem
Software

1. Peterson'south Algorithm: based on decorated waiting
2. Semaphores: general facility provided by operating system (eastward.yard., Bone/2)
• based on low-level techniques such as busy waiting or hardware assistance
• described in more detail below
3. Monitors: programming language technique
• see S&Thou, pp. 190--197 for more than details

Hardware

1. Exclusive access to retentivity location
• ever assumed
2. Interrupts that tin be turned off
• must have just ane processor for common exclusion
3. Exam-and-Set: special automobile-level instruction
• described in more particular below
4. Swap: atomically swaps contents of two words
• encounter S&1000, pp. 173--174 for more details
• for example, the Exchange instruction is available in the machine language used on Intel processors.

Test-and-Set

• hardware assistance for process synchronization
• a special hardware pedagogy that does two operations atomically
• i.east., both operations are executed or neither is
• sets the result to current value
• changes current value to true
• when describing auto language (CPU) operations, the verb 'set' means 'set to true'

Exam-and-Set Solution to the Disquisitional Department Trouble

echo

disquisitional section

residue section

until faux

Test-and-Gear up(target)

result := target
target := TRUE
return result

Information mutual to both processes:
target = Imitation

• Read Southward&G, Section 6.4

Bandy

• another type of hardware assistance for process synchronization
• a special hardware instruction that does a consummate swap (normally three operations) atomically
• i.e., the complete swap is executed or no function of information technology is
• given laissez passer-by-reference parameters A and B, it swaps their values

Swap Solution to the Critical Department Trouble

• uses two variables called lock and cardinal
• intuition: if lock is faux, then a process can enter the critical section, and otherwise information technology can't
• initially, lock is false

echo

var = true
while (var == true) swap(lock, var);
critical section
lock = false;
residual section

until imitation

Semaphores

• originally, semaphores were flags for signalling between ships
• a variable used for signalling between processes

· operations possible on a semaphore:

o initialization

• done before individual processes try to operate on the semaphore

o two main operations:

• wait (or acquire)
• point (or release)

o the wait and indicate operations are diminutive operations (eastward.g., the examination-and-set at the superlative of the loop of look is done before losing the processor)

o due east.one thousand., a resource such as a shared data structure is protected by a semaphore. Yous must acquire the semaphore before using the resource and release the semaphore when you lot are done with the shared resources.

wait(S):

while S 0 do

no-op;

S.value := S.value - 1;

signal(S):

S := S + 1;

In either case, the initial value for South:

1. equals one if only one process is allowed in the critical section (binary semaphore)
2. equals n if at most n processes are immune in the critical section

Semaphore Solution to the Critical Choice Problem
echo

critical section

residuum section
until faux;

Culling Implementation of Wait and Signal look(S): this lawmaking is executed atomically

S.value := S.value - 1;
if S.value < 0
so brainstorm

add this process to S.L;
suspend this process;

end;

actual waiting is done by the suspended process point(S):

S.value := Southward.value + one;
if South.value 0
then begin

remove a process P from Southward.50;
wakeup(P);

stop;

mutex: a binary semaphore used to enforce mutual exclusion (i.due east., solve the disquisitional section trouble)

Implementing Semaphores
To ensure the atomic holding, the OS implementation must either:

• turn off interrupts
• use busy waiting: to make certain only one process does a await operation at once
• Peterson'southward Algorithm
• Exam-and-Set
• Swap

Bounded Buffer Problem (Producer/Consumer Trouble)
for example, in UNIX a pipe between two processes is implemented as a 4Kb buffer between the ii processes

Producer

• creates data and adds to the buffer
• exercise not want to overflow the buffer

Consumer

• removes data from buffer (consumes information technology)
• does not want to get ahead of producer

Information common to both processes:
empty := n
full := 0
mutex := ane
Producer Process
repeat

produce an item in nextp wait(empty);
look(mutex); add nextp to buffer indicate(mutex);
signal(full);

until false;

Consumer Process
repeat

await(full);
wait(mutex); remove an item from buffer to nextc signal(mutex);
signal(empty); consume the item in nextc

until false;

mutex: (semaphore) initialized to 1
empty: count of empty locations in the buffer
initialized to n, the buffer size
full: count of total locations in the buffer
initialized to 0

The empty and full semaphores are used for process synchronization. The mutex semaphore is used to ensure mutually exclusive access to the buffer.
if we were to change the code in the consumer process from:

wait(full)

wait(mutex)
to

await(mutex)

wait(total) ,
then we could attain a deadlock where Process one is waiting for Process ii and Procedure 2 is waiting for Procedure i.

Return to Contents

Share this post