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, as 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 singleboolean 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 next 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.
Squad Locks
A squad lock allows a special task (the squad leader) to monitor the progress of a herd or group of worker tasks. When all (or a sufficient number) of the worker tasks are done with some aspect of their work, and the leader is ready to proceed, the entire set of tasks is allowed to pass a barrier and continue with the next sequence of their activities. The purpose is to allow tasks to execute asynchronously, yet coordinate their progress through a complex set of activities.
package Barriers is
protected type Barrier(Trigger : Positive) is
entry Wait_For_Leader;
entry Wait_For_Herd;
procedure Leader_Done;
private
Done : Boolean := False;
end Barrier;
protected type Autobarrier(Trigger : Positive) is
entry Wait_For_Leader;
entry Wait_For_Herd;
private
Done : Boolean := False;
end Autobarrier;
end Barriers;
This package shows two kinds of squad lock. The Barrier protected type demonstrates a basic squad lock. The herd calls Wait_For_Leader and the leader calls Wait_For_Herd and then Leader_Done. The Autobarrier demonstrates a simpler interface. The herd calls Wait_For_Leader and the leader calls Wait_For_Herd. The Trigger parameter is used when creating an instance of either type of barrier. It sets the minimum number of herd tasks the leader must wait for before it can proceed.
package body Barriers is
protected body Barrier is
entry Wait_For_Herd when Wait_For_Leader'Count >= Trigger is
begin
null;
end Wait_For_Herd;
entry Wait_For_Leader when Done is
begin
if Wait_For_Leader'Count = 0 then
Done := False;
end if;
end Wait_For_Leader;
procedure Leader_Done is
begin
Done := True;
end Leader_Done;
end Barrier;
protected body Autobarrier is
entry Wait_For_Herd when Wait_For_Leader'Count >= Trigger is
begin
Done := True;
end Wait_For_Herd;
entry Wait_For_Leader when Done is
begin
if Wait_For_Leader'Count = 0 then
Done := False;
end if;
end Wait_For_Leader;
end Autobarrier;
end Barriers;
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 de-allocated 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 because you can run out of memory if the Put operations occur more often than the Get operations.
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 refreshed 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 booleanvalues, 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 de-allocation 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;