Introduction
Concurrency can occur at four levels:
  • Machine instruction level
  • High-level language statement level
  • Unit level
  • Program level
Because there are no language issues in instruction- and program-level concurrency, they are not addressed here
 
Introduction to Subprogram-Level Concurrency
•A task or process or thread is a program unit that can be in concurrent execution with other program units
•Tasks differ from ordinary subprograms in that:
– A task may be implicitly started
– When a program unit starts the execution of a task, it is not necessarily suspended
– When a task’s execution is completed, control may not return to the caller
•Tasks usually work together
 
Two General Categories of Tasks
  • Heavyweight tasks execute in their own address space
  • Lightweight tasks all run in the same address space – more efficient
A task is disjoint if it does not communicate with or affect the execution of any other task in the program in any way
 
Task Synchronization
•A mechanism that controls the order in which tasks execute
•Two kinds of synchronization
– Cooperation synchronization
– Competition synchronization
•Task communication is necessary for synchronization, provided by: – Shared nonlocal variables – Parameters – Message passing
 
Kinds of synchronization
  • Cooperation: Task A must wait for task B to complete some specific activity before task A can continue its execution, e.g., the producer-consumer problem
  • Competition: Two or more tasks must use some resource that cannot be simultaneously used, e.g., a shared counter
Competition is usually provided by mutually exclusive access.
 
Need for Competition Synchronization
 
Scheduler
  • Providing synchronization requires a mechanism for delaying task execution
  • Task execution control is maintained by a program called the scheduler, which maps task execution onto available processors
Task Execution States
  1. New – created but not yet started
  2. Ready – ready to run but not currently running (no available processor)
  3. Running
  4. Blocked – has been running, but cannot now continue (usually waiting for some event to occur)
  5. Dead – no longer active in any sense
Liveness and Deadlock
•Liveness is a characteristic that a program unit may or may not have – In sequential code, it means the unit will eventually complete its execution
•In a concurrent environment, a task can easily lose its liveness
•If all tasks in a concurrent environment lose their liveness, it is called deadlock
 
Methods of Providing Synchronization
  • Semaphores
  • Monitors
  • Message Passing
Competition Synchronization with Semaphores
  • A third semaphore, named access, is used to control access (competition synchronization)
– The counter of access will only have the values 0 and 1
– Such a semaphore is called a binary semaphore
  • Note that wait and release must be atomic!
Competition Synchronization
  • Shared data is resident in the monitor (rather than in the client units)
  • All access resident in the monitor
–Monitor implementation guarantee synchronized access by allowing only one access at a time
–Calls to monitor procedures are implicitly queued if the monitor is busy at the time of the call
 
Cooperation Synchronization
Cooperation between processes is still a programming task
As a Programmer must guarantee that a shared buffer does not experience underflow or overflow
Message Passing
•Message passing is a general model for concurrency
– It can model both semaphores and monitors
– It is not just for competition synchronization
•Central idea: task communication is like seeing a doctor–most of the time she waits for you or you wait for her, but when you are both ready, you get together, or rendezvous
 
Rendezvous Time Lines
 
 
Message Passing: Server/Actor Tasks
•A task that has accept clauses, but no other code is called a server task (the example above is a server task)
•A task without accept clauses is called an actor task
– An actor task can send messages to other tasks
– Note: A sender must know the entry name of the receiver, but not vice versa (asymmetric)
 
Graphical Representation of a Rendezvous
 
 
Multiple Entry Points
Tasks can have more than one entry point
– The specification task has an entry clause for each
– The task body has an accept clause for each entry clause, placed in a select clause, which is in a loop
 
Cooperation Synchronization with Message Passing
Provided by Guarded accept clauses
 
An accept clause with a with a when clause is either open or closed –A clause whose guard is true is called open –A clause whose guard is false is called closed –A clause without a guard is always open