Concurrency

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

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  (approaches are discussed later)    

Task Execution States

•New - created but not yet started

•Ready - ready to run but not currently running (no available processor)

 •Running

•Blocked - has been running, but cannot now continue (usually waiting for some event to occur)

•Dead - no longer active in any sense

Semaphores 

•Dijkstra - 1965

•A semaphore is a data structure consisting of a counter and a queue for storing task descriptors

–A task descriptor is a data structure that stores all of the relevant information about the execution state of the task

•Semaphores can be used to implement guards on the code that accesses shared data structures

•Semaphores have only two operations, wait and release (originally called P and V by Dijkstra)

•Semaphores can be used to provide both competition and cooperation synchronization