Subject: Operating System

Topic: PROCESS COORDINATION

Difficulty: Medium

Concurrency is the interleaving of processes in time to give the appearance of simultaneous execution.

Thus it differs from parallelism, which offers genuine simultaneous execution. However the issues and difficulties raised by the two overlap to a large extent:

• Sharing global resources safely is difficult;

• Optimal allocation of resources is difficult;

• Locating programming errors can be difficult, because the contexts in which errors occur cannot always be reproduced easily.

Parallelism also introduces the issue that different processors may run at different speeds, but again this problem is mirrored in concurrency because different processes progress at different rates.

A Simple Example The fundamental problem in concurrency is processes interfering with each other while accessing a shared global resource.

This can be illustrated with a surprisingly simple example:

chin = getchar(); chout = chin; putchar(chout);

Imagine two processes P1 and P2 both executing this code at the “same” time, with the following interleaving due to multi-programming. i. P1 enters this code, but is interrupted after reading the character x into chin.

P2 enters this code, and runs it to completion, reading and displaying the character y.

P1 is resumed, but chin now contains the character y, so P1 displays the wrong character. The essence of the problem is the shared global variable chin. P1 sets chin, but this write is subsequently lost during the execution of P2.

The general solution is to allow only one process at a time to enter the code that accesses chin: such code is often called a critical section. When one process is inside a critical section of code, other processes must be prevented from entering that section.

This requirement is known as mutual exclusion.

Mutual Exclusion

Mutual exclusion is in many ways the fundamental issue in concurrency. It is the requirement that when a process P is accessing a shared resource R, no other process should be able to access R until P has finished with R.

Examples of such resources include files, I/O devices such as printers, and shared data structures.

There are essentially three approaches to implementing mutual exclusion. Leave the responsibility with the processes themselves: this is the basis of most software approaches.

These approaches are usually highly error-prone and carry high overheads. • Allow access to shared resources only through special-purpose machine instructions: i.e. a hardware approach. These approaches are faster but still do not offer a complete solution to the problem, e.g. they cannot guarantee the absence of deadlock and starvation. • Provide support through the operating system, or through the programming language.