What is concurrent programing?
-Simply described, it’s when
you are doing more than
one thing at the same
time.
-Not to be confused with
parallelism, concurrency is
when multiple sequences
of operations are run in
overlapping periods of
time.
Concurrent Programming
There are three main motivations for wanting to write concurrent programs:
1. To model parallelism in the real world – Real-time and embedded programs have to
control and interface with real world entities ( robots, conveyor belt…) that are
inherently parallel
2. To fully utilize the processor – modern processors run at speeds far in excess of the
input and output devices in which they must interact, a sequential program that is
waiting for I/O, is unable to do any other operation.
3. To allow more than one processor to solve a problem – a sequential program can
only be executed by one processor. Modern hardware platforms consist of multiple
processors to obtain more powerful execution environments
Processes and Threads
- All operating systems provide processes
- Processes execute in their own virtual machine (VM) to avoid interference from other
processes - Recent OSs provide mechanisms for creating threads/tasks within the same virtual
machine; threads are sometimes provided transparently to the OS - Threads have unrestricted access to their VM
- The programmer and the language must provide the protection from interference
Processes, threads and tasks
fig (1)
The life of a task
fig (1)
Concurrent Programming constructs
Although constructs for concurrent programming vary from language to another. There
are three fundamental facilities that must be provided:
1. The expression of concurrent activities (threads, tasks or processes)
2. The provision of synchronisation mechanism between concurrent activities
3. Primitives that support of communication between concurrent activities
Concurrent execution
- There are considerable variations in the models of concurrency adopted, concerning
threads or tasks, these variations appertain to: - Structure
- Level
- Granularity
- Initialization
- Termination
- Representation
Concurrent execution
Structure
- Static, number of processes known at compile-time
- Dynamic, processes created at run-time
Level
- Flat: Processes defined at the outermost level of the program (Top level tasks)
- Nested: Processes might be defined at any level of the program (Multilevel processes defined within
other processes)
Granularity
- A coarse grained program contains relatively few processes
- A fine grained program contains many processes, some only existing for a few instructions
Initialization
- Information may be passed (with or without parameters) to a new process as part of creation, or
communicated explicitly afterwards
Representation
- Fork and join
- Cobegin
- Explicit task representation
Concurrent execution (languages)
fig (1)
Concurrent execution
Termination
The task termination can be accomplished in a variety of ways, the circumstances under which tasks
are allowed to terminate can be summarised as follows:
1. Completion of execution of the task’s body
2. Suicide by execution of a ’self-terminate’ statement
3. Abortion, through the explicit action of another task
4. Unhandled error, occurrence of an entrapped error condition
5. Never: tasks are assumed to execute non-terminating loops
6. When no longer needed
Nested Tasks
- Hierarchies of tasks can be created
- Relationships
i. Creation: Parent/Child - the parent may be delayed while the child is being created and initialized
ii. Termination: Guardian/Dependant - a task may be dependent on the guardian task itself or on an
inner block of the guardian
iii. The guardian is not allowed to exit from a block until all dependent tasks of that block have
terminated
Nested Tasks
- A guardian cannot terminate until all its dependents have terminated
- A program cannot terminate until all its tasks have terminated
- A parent of a task may also be its guardian (e.g. with languages that allow only static task
structures) - With dynamic nested task structures, the parent and the guardian may or may not be identical
State diagram for a Task
fig 1
tasks and Objects
- An active object undertakes actions and enables computation
- A reactive object only performs actions when invoked by an active object
- The implementation of resources requires some form of control agent
- The resources are said to be protected or synchronized.
- A server implements its own protection
Tasks and Objects
From an object-oriented programming perspective four types of objects can be
identified:
* Passive object - a reactive entity with no synchronization constraints (needs
external thread control)
* Protected object - a reactive entity with synchronization constraints (typically
shared between many tasks)
* Active object - an object with an explicit or implicit internal task
* Server object – an active object with synchronization constraints (typically shared
between many tasks)
Tasks representation
- Fork and Join
- Cobegin
- Explicit Task Declaration
Fork and join
* Between the execution of the fork and the join,
procedure P and function F will be executing
concurrently.
* At the point of join, the procedure will wait until
the function has finished (figure 10.4)
Fork and join
Fork specifies a routine that should start executing concurrently with the invoker
* Join allows the invoker to wait for the completion of the invoked routine
function F return … is
begin
…
end f:
procedure P is
begin
…
C:= fork F;
…
J:= join C;
…
end P;
Fork and join
Cobegin
- Cobegin can be found in early concurrent programming
languages, but like fork and join’ it has fallen from favour
in modern real-time languages
Cobegin
The cobegin (or parbegin or par) is a structured way of denoting the concurrent execution
of a collection of statements:
cobegin
S1;
S2;
S3;
.
.
Sn
Coend
- This causes the statements S1 … Sn and so on to be executed concurrently
- The cobegin statement terminates when all the concurrent statements have terminated
Hallstein A. Hansen DSAS-3101:
Cobegin
Explicit Task Declaration
- Although sequential routines may be executed concurrently by
means of the cobegin or fork the structure of a concurrent
program can be made much clearer if the routines themselves
state whether they will be executed concurrently - Note that this does not say when they will execute
task body Thread is
begin
. . .
end; - Languages that support explicit task declaration may have explicit
or implicit process/task creation and has become the standard
way of expressing concurrency in concurrent Real-time languages.
22
Tasks and Ada
- The unit of concurrency is called a task
- Tasks must be explicitly declared at any program level
- They are created implicitly upon entry to the scope of their
declaration or via the action of an allocator.
Tasks may communicate and synchronize via:
– rendezvous (a form of synchronized message passing)
– protected units (a form of monitor/conditional critical region)
– shared variables
Task Types and Task Objects in Ada
- A task can be declared as a type or as a single instance
(anonymous type) - A task type consists of a specification and a body
- The specification contains
▪ the type name
▪ an optional discriminant part which defines the parameters that can be
passed to instances of the task type at their creation time
▪ a visible part which defines any entries and representation clauses
▪ a private part which defines any hidden entries and representation
clauses
Example Task Structure (Ada)
task type Server (Init : Parameter) is
entry Service;
end Server;
(specification (.ads))
task body Server is
begin
…
accept Service do
– Sequence of statements;
end Service;
…
end Server; (body (.adb))
