Chapter 12

Concurrency

INTRODUCTION

· Concurrency can be divided into different levels

· Instruction level is the execution of two or more machine instructions simultaneously

· Statement level is the execution of two or more statements simultaneously

· Unit level is the execution of two or more subprogram units simultaneously

· Program level is the execution of two or more programs simultaneously

· Concurrent control methods increase programming flexibility

CATEGORIES OF CONCURRENCY

· There are two distinct categories of concurrent unit control, physical concurrency and logical concurrency.

· When physical concurrency happens when several program units from the same program literally execute simultaneously on more than one processor

· On the other hand, logical concurrency, happens when the execution of several programs takes place in an interleaving fashion on a single processor

MOTIVATION FOR STUDYING CONCURRENCY

· Provides a method of conceptualizing program solutions to problems

· The need for software to make effective use of the increasing popularity of the hardware capability to support multiple processor concurrency

INTRODUCTION TO SUBPROGRAM-LEVEL CONCURRENCY

FUNDAMENTAL CONCEPTS

· A task is a unit of a program that can be in concurrent execution with other units of the same program

· There are three characteristics that distinguish tasks from subprograms.

· Tasks may be implicitly started, whereas a subprogram must be explicitly called.

· When a program unit invokes a task, it need not wait for the task to complete its execution before continuing its own.

· When the execution of a task is completed, control may or may not return to the unit that started the execution.

· If a task does not communicate with or affect another task it is considered disjoint

· Synchronization is a mechanism that controls the order in which tasks execute.

· Cooperation synchronization is required between two tasks that when the second task must wait for the first task to finish executing before it may proceed.

· Competition synchronization is required between two tasks when both require the use of the same resource that cannot be simultaneously used.

· To provide competition synchronization, mutually exclusive access to the shared resource must be guaranteed.

· A program called a scheduler manages the sharing of processors among tasks.

· If two tasks have a resource that the other needs and neither releases the resource it possesses this guarantees that neither program will ever complete normally, they are said to be in deadlock.

LANGUAGE DESIGN FOR CONCURRENCY

· Languages, such as, PL/I, Ada 95, and Java have been designed to support concurrency.

· Design Issues

- How is cooperation synchronization provided?

- How is competition synchronization provided?

- How and when do tasks begin and end execution?

- Are tasks statically or dynamically created?

SEMAPHORES

· A very simple mechanism used to provide synchronization of tasks.

· A semaphore provides limited access to a data structure by placing guards around the code that accesses the structure.

· Using semaphores to provide corporation and competition synchronization creates an unsafe programming environment.

MONITORS

· Monitors are a better way to provide competition synchronization than semaphores.

· However, cooperation synchronization is subject to same problems as the semaphores.

MESSAGE PASSING

· Message passing can be synchronous or asynchronous.

· Cooperation and competition synchronization of tastes can be conveniently handled with message passing.