Shared variable-based synchronization
and communication
To understand the requirements for communication and
synchronisation based on shared variables we will discuss the
following items:
a) Busy waiting
b) Semaphores
c) Conditional critical regions
d) Monitors
e) Protected types and synchronized methods
Synchronisation and Communication
Inter-task communication is usually based on either:
1. Shared variables
* Shared variables are objects to which more than one process has access to communication
* Can therefore proceed by each process referencing the variables, when appropriate
2. Message passing
* Message passing involves explicit exchange of data between processes by means of messages
* The messages are transmitted from one task to another via some agency, example: Sockets
Shared variable communication
- Unrestricted use of shared variables is unreliable and unsafe due to
multiple update problems - Consider two tasks updating a shared variable, X, with the assignment:
X:= X + 1 - load the value of X into some register
- increment the value in the register by 1
- store the value in the register back to X
- The three operations are not indivisible
- two tasks simultaneously updating the variable could follow an
interleaving that would produce an incorrect result
Coordinated sections (readers-writers problem)
Readers can read concurrently, as they do not alter data; however, writers require mutual exclusion
over the data both from writers and from readers.
Avoiding Interference
- The parts of a task that access shared variables must be executed indivisibly
with respect to each other, these parts is called a critical section - The synchronization required to protect a critical section is known as
mutual exclusion
Assumptions of Approaches - Atomicity is assumed to be present at the memory level.
- If one task is executing X:= 5, simultaneously with another executing X:= 6, the result will
be either 5 or 6 - If two tasks are updating a structured object, this atomicity will only apply at the single word
element level
Coordinated sections (readers-writers problem)
fig 1 side 7
Busy waiting
Busy waiting
* A task sets the value of a flag (shared variable)
* Can be used for implementing condition synchronization
* No simple method for mutual exclusion exists
task T1; – pseudo code for waiting task
…
while flag == down do
null
end;
…
end T1
task T2; – signaling task
…
flag := up;
…
end T2
Busy waiting
- The loop while flag == down do: null is generally very inefficient
- A shared variable will have to be read each time, creating network traffic for a
multi-processor system - What if there are more than one process waiting on a condition?
- Called busy waiting, or spinning
- The flag is called a spin lock
Too error prone, consumes resources
Semaphores
Semaphores have the following benefits:
* They simplify the protocols for synchronization
* They remove the need for busy-wait loops
A Semaphore (S) is a non-negative integer variable than can only be acted on by:
1. wait(S) If S > 0 then decrement S by one, Otherwise delay until S > 0
2. Signal(S) - Increment the value of S by one.
10
Trivial example: Consider a variable A and a Boolean variable S. A is only accessed when S is
marked true. Thus, S is a semaphore for A. One can imagine a stoplight signal (S) just before
a train station (A). In this case, if the signal is green, then one can enter the train station. If it
is yellow or red (or any other color), the train station cannot be accessed.
Conditional critical regions (CCRs)
- Conditional critical regions — a section of code that is executed in mutual exclusion
- Shared variables are grouped together into named regions and are tagged as being resources
- Task are prohibited from entering a region in which another task is already active
- Condition synchronisation is provided by guards
- When a task wishes to enter a critical region it evaluates the guard (under mutual exclusion);
if the guard evaluates true it may enter, but if it is false the task is delayed
Semaphores
Importantly, the signal and wait operations are atomic.
– pseudo code for mutal execlution
mutex : semaphore;
task T1 :
loop
wait (mutex);
<critical>
signal (mutex)
<non-critical>
end
end T1
task T2 :
loop
wait (mutex);
<critical>
signal (mutex)
<non-critical>
end
end T2
</non-critical></critical></non-critical></critical>
Protected objects in Ada
- A protected object in Ada encapsulates data items and allows access to them only
with protected subprograms - The language guarantees that subprograms will be executed so that data is
updated under mutual exclusion - A barrier (condition) must be evaluated to true before data is accessed.
- The protected keyword is used for this purpose
Criticism of semaphores
- Semaphores are elegant, yet low-level, synchronization primitives
- Thus they are error-prone
- An omitted or misplaced call can make the entire program collapse
- Mutex may not be assured, deadlocks can occur
- They provide a means to program mutual exclusion
- High level approaches give mutual exclusion explicitly.
Monitors
- Monitors provide encapsulation, and efficient condition synchronization
- The critical regions are written as procedures and are encapsulated together into a single
module - All variables that must be accessed under mutual exclusion are hidden
- All procedure calls into the module are executed in mutually exclusive
- Only the operations are visible outside the monitor
Although monitors encapsulate all the entities concerned with a resource and provide the
important mutual exclusion, their internal structure may still be difficult to understand due
to the use of condition variables
Protected object example
protected type Shared Integer (init : Integer ) is
function Read return Integer ;
procedure Write (n : Integer) ;
procedure Increment (by : Integer) ;
private
data : Integer := init
end Shared Integer;
The encapsulated data can now only be accessed by the three subprograms:
Read, Write, and Increment.
Protected objects
- A protected procedure provides mutually exclusive read/write access to the
encapsulated data - A protected function provides concurrent read-only access to the encapsulated
data - However, protected functions are executed mutually exclusive with protected
procedures
The Readers and Writers Problem
In the readers-writers problem, many reader and many writer tasks are attempting to access the shared
data simultaneously.
* There are three commonly known solutions to this problem:
The first solution is to use a semaphore which locks the
data whenever a reader or writer accesses the data.
This solves the problem of readers attempting to access
data which are currently being altered by a writer, but it
does not allow multiple readers to access the data
concurrently.
(fig 1 for writer , fig 2 for reader)
writer:
wait (mutex)
write here
signal (mutex)
reader:
wait (mutex)
read here
signal (mutex)
The Readers and Writers Problem
The second solution adds a variable which
keeps track of how many readers currently
accessing the shared data. By doing that
we’re able to restrict the locking so that
only the first reader accessing the data
apply the lock, providing access to the
other readers without applying the lock.
writer:
wait (mutex)
write here
signal (mutex)
reader:
reader++
if(readers==1)
wait (wrmutex)
read here
readers–
if(readers==0)
signal(wrmutex)
The Readers and Writers Problem
- To overcome these difficulties the, the reading and writing are
viewed as coordinated sections, as seen in figure 11.2 - Protected Objects(PO) must be used to implement an access
control protocol for the read and write operations (Entry-and
Exit Protocol)
The Readers and Writers Problem
The problem with solution two is that now multiple
readers might try to alter the reader counter
simultaneously, but this is solved pretty easily in
solution three. To do this we add a semaphore to
the reader count variable so that it can only be
altered by one task at a time, and the others have
to wait until the task altering it unblocks when it’s
done incrementing/decrementing it.
writer:
wait (mutex)
write here
signal (mutex)
reader:
wait(mutex)
readers++
if(readers==1)
wait (wrmutex)
signal(mutex)
wait(mutex)
readers–
if(readers==0)
signal(wrmutex)
signal(wrmutex)
The Readers and Writers Problem
- Consider a file which needs mutual exclusion between writers and reader but not
between multiple readers - Protected Objects(PO) can implement the readers/writers algorithm if the read
operation is encoded as a function and the write as a procedure; however:
▪ The programmer cannot easily control the order of access to the protected object;
specifically, it is not possible to give preference to write operations over reads
▪ If the read or write operations are potentially blocking, then they cannot be made
from within a protected object
The Readers and Writers Problem
package body Readers_Writers is
procedure Read_File(I : out Item) is separate;
procedure Write_File(I : Item) is separate;
protected Control is
entry Start_Read;
procedure Stop_Read;
entry Start_Write;
procedure Stop_Write;
private
Readers : Natural := 0; – no. of current readers
Writers : Boolean := False; – Writers present
end Control;
The body of the package implements the entry and exit protocols.
Here, preference is given to write over read:
with Data_Items; use Data_Items;
package Readers_Writers is
– for some type Item
procedure Read (I : out Item);
procedure Write (I : Item);
end Readers_Writers;
The reading and writing operations are first
encapsulated in a package
The Readers and Writers Problem
procedure Read (I : out Item) is
begin
Control.Start_Read; – entry protocol
Read_File(I); – coordinated section
Control.Stop_Read; – exit protocol
end Read;
procedure Write (I : Item) is
begin
Control.Start_Write; – entry protocol
Write_File(I); – coordinated section
Control.Stop_Write; – exit protocol
end Write;
The procedures for read and write protected body Control is
end Control;
end Readers_Writers;
entry Start_Read when not Writers and
Start_Write’Count = 0 is
begin
Readers := Readers + 1;
end Start_Read;
procedure Stop_Read is
begin
Readers := Readers - 1;
end Stop_Read;
entry Start_Write when Readers = 0 and not Writers is
begin
Writers := True;
end Start_Write;
procedure Stop_Write is
begin
Writers := False;
end Stop_Write;
The entry protocol for a writer ensures that a writer can only begin writing if there is no writer currently and there are no current
readers. The exit protocol for both readers and writers is non-blocking call to announce the termination of that operation.
Summary
Critical section — code that must be executed under mutual exclusion
Producer-consumer system — two or more tasks exchanging data via a finite buffer
Busy waiting — a task continually checking a condition to see if it is now able to proceed
Livelock — an error condition in which one or more tasks are prohibited from progressing whilst
using up processing cycles
Deadlock — a collection of suspended tasks that cannot proceed
Indefinite postponement — a task being unable to proceed as resources are not made available
