|
by Jim Rogers
Summary
Many applications are constructed of groups of cooperating threads of execution.
Historically this has frequently been accomplished by creating a group of
cooperating processes. Those processes would cooperate by sharing data. At
first, only files were used to share data. File sharing presents some interesting
problems. If one process is writing to the file while another process reads
from the file you will frequently encounter data corruption because the reading
process may attempt to read data before the writing process has completely
written the information. The solution used for this was to create file locks,
so that only one process at a time could open the file. Unix introduced the
concept of a Pipe, which is effectively a queue of data. One process can
write to a pipe while another reads from the pipe. The operating system treats
data in a pipe as a series of bytes. It does not let the reading process
access a particular byte of data until the writing process has completed its
operation on the data.
Various operating systems also introduced other mechanisms allowing processes
to share data. Examples include message queues, sockets, and shared memory.
There were also special features to help programmers control access to data,
such as semaphores. When operating systems introduced the ability for a single
process to operate multiple threads of execution, also known as lightweight
threads, or just threads, they also had to provide corresponding locking
mechanisms for shared data.
Experience shows that, while the variety of possible designs for shared
data is quite large, there are a few very common design patterns that frequently
emerge. Specifically, there are a few variations on a lock or semaphore,
s well as a few variations on data buffering. This paper explores the locking
and buffering design patterns for threads in the context of a monitor.
Although monitors can be implemented in many languages, all examples in this
paper are presented using Ada protected types. Ada protected types are a very
thorough implementation of a monitor.
Monitors
There are several theoretical approaches to creating and controlling shared
memory. One of the most flexible and robust is the monitor as first described
by C.A.R. Hoare. A monitor is a data object with three different kinds of
operations.
Procedures are used to change the state or values contained by the monitor.
When a thread calls a monitor procedure that thread must have exclusive access
to the monitor to prevent other threads from encountering corrupted or partially
written data.
Entries, like procedures, are used to change the state or values contained
by the monitor, but an entry also specifies a boundary condition. The entry
may only be executed when the boundary condition is true. Threads
that call an entry when the boundary condition is false are placed
in a queue until the boundary condition becomes true. Entries are used,
for example, to allow a thread to read from a shared buffer. The reading thread
is not allowed to read the data until the buffer actually contains some data.
The boundary condition would be that the buffer must not be empty. Entries,
like procedures, must have exclusive access to the monitor's data.
Functions are used to report the state of a monitor. Since functions only
report state, and do not change state, they do not need exclusive access
to the monitor's data. Many threads may simultaneously access the same monitor
through functions without danger of data corruption.
The concept of a monitor is extremely powerful. It can also be extremely
efficient. Monitors provide all the capabilities needed to design efficient
and robust shared data structures for threaded systems.
Although monitors are powerful, they do have some limitations. The operations
performed on a monitor should be very fast, with no chance of making a thread
block. If those operations should block the monitor will become a road block
instead of a communication tool. All the threads awaiting access to the monitor
will be blocked as long as the monitor operation is blocked. For this reason,
some people choose not to use monitors. There are design patterns for monitors
that can actually be used to work around these problems. Those design patterns
are grouped together as locking patterns.
Locking Patterns
This paper explores three locking patterns, binary semaphores, counting
semaphores, and burst locks.
Binary Semaphore
Binary semaphores are used to provide exclusive locking for a thread on
a resource. Only one thread at a time may "hold" the semaphore. All others
must wait until their turn with the semaphore. If you want to lock access
to a potentially blocking resource, you should acquire a semaphore for that
resource just before accessing it. and release the semaphore upon completing
your access to the resource. The following code block defines the interface
to a monitor implementing a binary semaphore.
protected type Binary_Semaphore is
entry Acquire;
procedure Release;
private
Locked : Boolean := False;
end Binary_Semaphore;
This monitor has two operations defined. The entry Acquire allows
a thread (or task as they are called in Ada) to acquire the semaphore
if no other task currently holds the semaphore. The procedure Release
unconditionally releases the semaphore. The private data for this monitor
is a single boolean value, Locked, which is initialized to False.
The actual workings of the monitor are specified in the body of
the protected type.
protected body Binary_Semaphore is
entry Acquire when not Locked is
begin
Locked := True;
end Acquire;
procedure Release is
begin
Locked := False;
end Release;
end Binary_Semaphore;
Note that you can only acquire the binary semaphore when it is not already
locked. Acquiring the semaphore causes it to be locked. The Release
procedure simply unlocks the semaphore.
Counting Semaphore
Sometimes you want to access a resource with the ability to handle a limited
number of simultaneous accesses. In this case, you will want to use a counting
semaphore. This variation on the semaphore allows up to a predetermined maximum
number of threads or tasks to hold the semaphore simultaneously. The interface
for a counting semaphore looks a lot like the interface for a binary semaphore.
protected type Counting_Semaphore(Max : Positive) is
entry Acquire;
procedure Release;
private
Count : Natural := 0;
end Counting_Semaphore;
In this case, when the semaphore is created you must specify the maximum
number of tasks you want to simultaneously hold this semaphore. The private
data for this semaphore is a simple integer value, counting the current number
of tasks currently holding the semaphore. In the case of a counting semaphore,
the boundary condition for the Acquire entry is that the Count
cannot exceed the value of Max. The implementation of the counting
semaphore simply manipulates the Count.
protected body Counting_Semaphore is
entry Acquire when Count < Max is
begin
Count := Count + 1;
end Acquire;
procedure Release is
begin
if Count > 0 then
Count := Count - 1;
end if;
end Release;
end Counting_Semaphore;
Note that the Release procedure uses a conditional to ensure that
Count is never assigned a negative value.
Burst Lock
The final locking pattern we will explore is the burst lock. This pattern
allows some specified number of tasks simultaneous access to a resource.
Access to the resource is granted based upon the number of tasks waiting to
access the resource. This pattern is good for short duration resource accesses
when there is a limited bandwidth for communication to the resource. You
can use this pattern to optimize the number of simultaneous accesses to the
resource.
protected type Burst(Sample_Size : Positive) is
entry Request_Access;
procedure Grant_Access;
private
Release : Boolean := False;
end Burst;
You specify the number of tasks in a burst when you create an instance
of this type. Note that there is an entry Request_Access and a procedure
Grant_Access. The entry queues up requests until Sample_Size
tasks are waiting to access the resource. The procedure Grant_Access
is used to send a burst through when fewer than Sample_Size tasks
are waiting.
protected body Burst is
entry Request_Access
when Request_Access'Count = Sample_Size
or Release is
begin
if Request_Access'Count > 0 then
Release := True;
else
Release := False;
end if;
end Request_Access;
procedure Grant_Access is
begin
Release := True;
end Grant_Access;
end Burst;
The Request_Access entry does all the interesting work in this pattern.
The expression Request_Access'Count evaluates to the number of tasks
queued up to wait for this entry. The boundary condition is true when
the number of waiting tasks equals Sample_Size or Release
is true. When the boundary condition becomes true, the entry sets Release
to True until no more tasks are queued. At that point Release is
set to False so that access to the resource will once again be blocked.
Buffer Patterns
Buffer patterns are used when you want the monitor to control data shared
by two or more tasks. The kind of buffer you use will vary with your needs.
If all the data produced by one thread must be read by the another thread,
then you want to use a buffer containing one or more data elements. Buffers
containing only one data element cause the reading and writing tasks to become
synchronized around the read and write operations. Buffers containing many
data elements allow greater asynchronous operation of the reading and writing
tasks. Multi-element buffers can either be bounded, with a fixed maximum
size, or unbounded, being dynamically allocated and deallocated as needed.
Bounded buffers offer fixed amount of memory usage. Unbounded buffers offer
less blocking due to the buffer being full.
Additional patterns are available when the reading task only needs a time
based sample of the data from the writing task, or when the reading task
only needs to be sure it is not reading duplicate data points.
Bounded Buffer
The bounded buffer holds a limited collection of data items. Any task
reading from the bounded buffer can only read data when the buffer contains
data. Any task writing to the bounded buffer can only write data when the
buffer is not full. You could make a variation of the bounded buffer having
the write operation be a procedure. When the buffer is full it will overwrite
the oldest data item in the buffer. The example below demonstrates the former
version, where the writing task suspends when the buffer is full.
type Element_Array is array(Natural range <>)
of Element_Type;
protected type Bounded_Buffer(Max : Positive) is
entry Put(Item : in Element_Type);
entry Get(Item : out Element_Type);
function Size return Natural;
private
Elements : Element_Array(0..Max);
Put_Index : Natural := 0;
Get_Index : Natural := 0;
Count : Natural := 0;
end Bounded_Buffer;
The internal array Elements is treated as a circular queue of data.
When the queue is full the Put entry blocks. When the queue is empty
the Get entry blocks. The implementation of the bounded buffer is
very simple.
protected body Bounded_Buffer is
entry Put(Item : in Element_Type)
when Size < Elements'Length is
begin
Elements(Put_Index) := Item;
Put_Index := (Put_Index + 1) mod Elements'Length;
Count := Count + 1;
end Put;
entry Get(Item : out Element_Type) when Size > 0 is
begin
Item := Elements(Get_Index);
Get_Index := (Get_Index + 1) mod Elements'Length;
Count := Count - 1;
end Get;
function Size return Natural is
begin
return Count;
end Size;
end Bounded_Buffer;
The Put entry barrier is true as long as the Elements array
is not full. The Get entry barrier is true as long as the Elements
array is not empty. This design pattern conserves memory while ensuring
that all data produced by the writing task will be available to the reading
task.
Unbounded Buffer
The unbounded buffer uses varying amounts of memory, but also tends to
minimize blocking for the writing task. One danger of this pattern is that
you can run out of memory on your system if the writing task is consistently
faster than the reading task for an extended period of time. For this reason,
it is best to use unbounded buffers only when, on average, the writing task
is no faster than the reading task.
type Node;
type Node_Access is access Node;
type Node is record
Value : Element_Type;
Next : Node_Access := null;
end record;
protected type Unbounded_Buffer is
procedure Put(Item : in Element_Type);
entry Get(Item : out Element_Type);
function Size return Natural;
private
Head : Node_Access := null;
Tail : Node_Access := null;
Count : Natural := 0;
end Unbounded_Buffer;
The unbounded buffer maintains a simple linked list of data elements. The
Get entry is still limited by the boundary condition that the buffer
cannot be empty when you get a data item.
protected body Unbounded_Buffer is
procedure Put(Item : in Element_Type) is
Temp_Node : Node_Access := new Node;
begin
Temp_Node.Value := Item;
if Tail = null then
Head := Temp_Node;
Tail := Temp_Node;
else
Tail.Next := Temp_Node;
Tail := Tail.Next;
end if;
Count := Count + 1;
end Put;
entry Get(Item : out Element_Type) when Head /= null is
procedure Free is new
Ada.Unchecked_Deallocation(Object => Node,
Name => Node_Access);
Temp : Node_Access;
begin
Item := Head.Value;
Temp := Head;
Head := Head.Next;
if Head = null then
Tail := null;
end if;
Free(Temp);
Count := Count - 1;
end Get;
function Size return Natural is
begin
return Count;
end Size;
end Unbounded_Buffer;
This implementation adds to the tail of the linked list and reads (and
deletes) from the head of the linked list. Every Put allocates a new
node while every Get deallocates an existing node. These operations
can be much slower than the corresponding bounded buffer operations due to
the need to dynamically manage the data. In general, for long running applications,
it is safer to use the bounded buffer than the unbounded buffer.
Single Element Buffers
There are a variety of single element buffer design patterns. I will deal
with three of them.
Unconditional Buffer
A single element buffer without any access barrier is used when the reading
task only needs to sample data from the writing task. If the reading task
executes faster than the writing task, the reading task will read the same
value more than once. If the writing task executes faster than the reading
task some values will be skipped. Unconditional buffers are often used when
sampling sensor data. Sensor data may be delivered to a program at a rate
many times faster than it can be analyzed. The unconditional buffer simplifies
the communication between the task reading from the sensor and the task
analyzing the sensor data.
protected type Read_Any_Buffer is
procedure Put(Item : in Element_Type);
function Get return Element_Type;
function Initialized return Boolean;
private
Value : Element_Type;
Is_Valid : Boolean := False;
end Read_Any_Buffer;
One issue with an unconditional buffer is determining if it contains valid
data. It is unreasonable for the reading task to read uninitialized data.
The function initialized can be polled to determine when the unconditional
buffer has been initialized. After that happens the reading task merely
calls the Get function whenever it wants access to the current value
in the buffer.
protected body Read_Any_Buffer is
procedure Put(Item : in Element_Type) is
begin
Value := Item;
Is_Valid := True;
end Put;
function Get return Element_Type is
begin
if not Is_Valid then
raise Uninitialized_Data;
end if;
return Value;
end Get;
function Initialized return Boolean is
begin
return Is_Valid;
end Initialized;
end Read_Any_Buffer;
This example has the Get function raise the exception Uninitialized_Data
if the function is called before data is initialized. The exception logic
was placed in this function for safety only. It is much more efficient to
poll the Initialized function than to iteratively handle exceptions.
Conditional Read Buffer
Sometimes you want the reading task to only read data it has not seen
before. The conditional read buffer handles this by allowing a conditional
read. If the reading task is faster than the writing task this buffer will
cause both tasks to synchronize around the write to the buffer.
protected type Read_New_Buffer is
procedure Put(Item : in Element_Type);
entry Get(Item : out Element_Type);
private
Value : Element_Type;
Is_New : Boolean := False;
end Read_New_Buffer;
Instead of an initialization flag I have provided an Is_New flag.
Logically, once the reading task reads a data point that data becomes invalid.
Another read cannot occur until the data is refresehed by the writing task.
protected body Read_New_Buffer is
procedure Put(Item : in Element_Type) is
begin
Value := Item;
Is_New := True;
end Put;
entry Get(Item : out Element_Type) when Is_New is
begin
Item := Value;
Is_New := False;
end Get;
end Read_New_Buffer;
The act of reading the buffer causes the data in the buffer to become
invalid for another read. This pattern works for a system with a single reader
task. If you have multiple reader tasks you must get more creative. One solution
is to replace the Is_New boolean value with an array of boolean values,
one for each reader. Another is to accompany the data value with a serial
number. The reading task must keep track of the serial number of the last
read data and reject the data if the serial number is unchanged.
Conditional Read Write Buffer
The conditional read write buffer is used when you want the reading task
to read every value produced by the writing task. This buffer pattern causes
the reading and writing tasks to always synchronize around the buffer reads
and writes. If you really need this guarantee of data delivery you should
carefully consider using the Unbounded Buffer pattern. The unbounded
buffer allows a little more variation is speed between the reading and writing
tasks. However, if one of the tasks is always faster than the other, the
conditional read write buffer will perform faster than the unbounded buffer.
protected type Read_Write_New_Buffer is
entry Put(Item : in Element_Type);
entry Get(Item : out Element_Type);
private
Value : Element_Type;
Is_New : Boolean := False;
end Read_Write_New_Buffer;
Note that both the Put and the Get operations are conditional.
Only one boolean value is needed to control both operations.
protected body Read_Write_New_Buffer is
entry Put(Item : in Element_Type) when not Is_New is
begin
Value := Item;
Is_New := True;
end Put;
entry Get(Item : out Element_Type) when Is_New is
begin
Item := Value;
Is_New := False;
end Get;
end Read_Write_New_Buffer;
The writing task can only write to the buffer when the data is not new.
The reading task can only read from the buffer when the data is new. This
pattern is faster than the bounded or unbounded buffer patterns because
there is no collection manipulation. The bounded buffer requires calculations
of put and get indices. The unbounded buffer requires memory allocation
for every put and deallocation for every get.
Whenever possible I suggest you use the single element buffers instead
of the bounded or unbounded buffers. Most of the time one of your tasks
will always be faster than the other in a read/write pair. In those cases
you can avoid extra overhead, and maximize data throughput by using the single
element buffers. The single element buffers also have the virtue of using
less memory, which may be a concern in an embedded real time system.
Complete Ada Packages for Examples
Locks
package Locks is
protected type Burst(Sample_Size : Positive) is
entry Request_Access;
procedure Grant_Access;
private
Release : Boolean := False;
end Burst;
protected type Counting_Semaphore(Max : Positive) is
entry Acquire;
procedure Release;
private
Count : Natural := 0;
end Counting_Semaphore;
protected type Binary_Semaphore is
entry Acquire;
procedure Release;
private
Locked : Boolean := False;
end Binary_Semaphore;
end Locks;
package body Locks is
protected body Burst is
entry Request_Access
when Request_Access'Count = Sample_Size
or Release is
begin
if Request_Access'Count > 0 then
Release := True;
else
Release := False;
end if;
end Request_Access;
procedure Grant_Access is
begin
Release := True;
end Grant_Access;
end Burst;
protected body Counting_Semaphore is
entry Acquire when Count < Max is
begin
Count := Count + 1;
end Acquire;
procedure Release is
begin
if Count > 0 then
Count := Count - 1;
end if;
end Release;
end Counting_Semaphore;
protected body Binary_Semaphore is
entry Acquire when not Locked is
begin
Locked := True;
end Acquire;
procedure Release is
begin
Locked := False;
end Release;
end Binary_Semaphore;
end Locks;
Buffers
generic
type Element_Type is private;
package Buffers is
type Element_Array is array(Natural range <>)
of Element_Type;
protected type Bounded_Buffer(Max : Positive) is
entry Put(Item : in Element_Type);
entry Get(Item : out Element_Type);
function Size return Natural;
private
Elements : Element_Array(0..Max);
Put_Index : Natural := 0;
Get_Index : Natural := 0;
Count : Natural := 0;
end Bounded_Buffer;
type Node;
type Node_Access is access Node;
type Node is record
Value : Element_Type;
Next : Node_Access := null;
end record;
protected type Unbounded_Buffer is
procedure Put(Item : in Element_Type);
entry Get(Item : out Element_Type);
function Size return Natural;
private
Head : Node_Access := null;
Tail : Node_Access := null;
Count : Natural := 0;
end Unbounded_Buffer;
Uninitialized_Data : exception;
protected type Read_Any_Buffer is
procedure Put(Item : in Element_Type);
function Get return Element_Type;
function Initialized return Boolean;
private
Value : Element_Type;
Is_Valid : Boolean := False;
end Read_Any_Buffer;
protected type Read_New_Buffer is
procedure Put(Item : in Element_Type);
entry Get(Item : out Element_Type);
private
Value : Element_Type;
Is_New : Boolean := False;
end Read_New_Buffer;
protected type Read_Write_New_Buffer is
entry Put(Item : in Element_Type);
entry Get(Item : out Element_Type);
private
Value : Element_Type;
Is_New : Boolean := False;
end Read_Write_New_Buffer;
end Buffers;
with Ada.Unchecked_Deallocation;
package body Buffers is
protected body Bounded_Buffer is
entry Put(Item : in Element_Type)
when Size < Elements'Length is
begin
Elements(Put_Index) := Item;
Put_Index := (Put_Index + 1) mod Elements'Length;
Count := Count + 1;
end Put;
entry Get(Item : out Element_Type) when Size > 0 is
begin
Item := Elements(Get_Index);
Get_Index := (Get_Index + 1) mod Elements'Length;
Count := Count - 1;
end Get;
function Size return Natural is
begin
return Count;
end Size;
end Bounded_Buffer;
protected body Unbounded_Buffer is
procedure Put(Item : in Element_Type) is
Temp_Node : Node_Access := new Node;
begin
Temp_Node.Value := Item;
if Tail = null then
Head := Temp_Node;
Tail := Temp_Node;
else
Tail.Next := Temp_Node;
Tail := Tail.Next;
end if;
Count := Count + 1;
end Put;
entry Get(Item : out Element_Type) when Head /= null is
procedure Free is new
Ada.Unchecked_Deallocation(Object => Node,
Name => Node_Access);
Temp : Node_Access;
begin
Item := Head.Value;
Temp := Head;
Head := Head.Next;
if Head = null then
Tail := null;
end if;
Free(Temp);
Count := Count - 1;
end Get;
function Size return Natural is
begin
return Count;
end Size;
end Unbounded_Buffer;
protected body Read_Any_Buffer is
procedure Put(Item : in Element_Type) is
begin
Value := Item;
Is_Valid := True;
end Put;
function Get return Element_Type is
begin
if not Is_Valid then
raise Uninitialized_Data;
end if;
return Value;
end Get;
function Initialized return Boolean is
begin
return Is_Valid;
end Initialized;
end Read_Any_Buffer;
protected body Read_New_Buffer is
procedure Put(Item : in Element_Type) is
begin
Value := Item;
Is_New := True;
end Put;
entry Get(Item : out Element_Type) when Is_New is
begin
Item := Value;
Is_New := False;
end Get;
end Read_New_Buffer;
protected body Read_Write_New_Buffer is
entry Put(Item : in Element_Type) when not Is_New is
begin
Value := Item;
Is_New := True;
end Put;
entry Get(Item : out Element_Type) when Is_New is
begin
Item := Value;
Is_New := False;
end Get;
end Read_Write_New_Buffer;
end Buffers;
| 
