1. Overview

Concurrent processing became a field of study because of operating systems. Specifically, a computer system has many (OS and user) processes that run concurrently and interact via shared devices and shared data structures (process tables, file system tables, etc.). But concurrent processing arises in many other areas, including networking, databases, user interfaces, parallel hardware, etc. We first look at concurrent programs in a general context, and only later related them to Operating Systems.

Some common problems to solve in concurrent processing are

• Mutual exclusion. Several process have access to a shared data structure (e.g., file, memory addresses, registers, etc.). Processes should interact so that at any time at most one process is accessing the structure.

• Bounded-buffer producer-consumer. One process produces items and places it in a buffer, another process removes items and consumes them, and the processes need to ensure among other things that there is no underflow or overflow of the buffers. An example is when a user process produces print requests, which are consumed by a printer server that produces raster-maps, which are consumed by a printer device.

• Readers writers. Several processes that can read from and write into a shared data structure Processes should interact so that when a write is ongoing no other write or read is ongoing, but multiple reads can be ongoing at the same time.

2. Concurrent Programs versus Sequential Programs

One obvious difference is that a concurrent program has constructs for creating processes, terminating processes, and for processes to communicate with each other (IPC). These constructs may be provided within the programming language (e.g., thread constructors in Java, cobegin and coend in Concurrent Pascal) or as library calls to the OS (e.g., fork and join in Unix, Posix threads).

Concurrent programs are harder than sequential programs to get right because the behavior of a concurrent program depends on the variations in speed of the processes. Each speed variation gives rise to a different execution (starting from the same initial state). Thus a concurrent program can have a great many possible executions. We need to ensure that every one of these executions is correct.

To make sense of a sequential program, one needs to know what each statement in the program does. To make sense of a concurrent program, one needs to know three more attributes:

• Atomicity: What statements of the program are executed atomically? "Statement S is atomically executed" means that once the execution of S starts, the environment cannot influence the execution of S and cannot observe intermediate states within the execution. Consequently, for any process in the environment, S has either not been executed or has been executed.

• Control: Which statements of the program does the process control (i.e., initiate execution). Statements not controlled by the process are controlled by (some process in) the environment.

• Progress: What can we say about the speed of a process? The following is the weakest but still useful condition we can place on the process speed.
  • For a non-blocking statement S controlled by the process, we say the process executes S with weak fairness to mean that if the process is at S then it EVENTUALLY executes S.

  • For a blocking statement S (e.g., receive, semaphore wait, etc.) controlled by the process, we say the process executes S with weak fairness to mean that if the process is at S and if after some point in time S is CONTINUOUSLY unblocked, then S is eventually executed.

  • We say a process has weak fairness to mean that it executes all statements it controls with weak fairness.

3. Some Comments

• The atomicity provided by the underlying architecture can range from fine-grained (e.g., reads and writes of individual bits) to coarse-grained (e.g., reads, writes, read-modify-writes of memory pages). Synchronization primitives, such as locks, allow users to choose arbitrary levels of granularity.

• Atomicity introduces a trade-off between programming ease and performance. In general, the larger the granularity of atomicity employed, the easier it becomes to design programs but the less efficiently they run, and this is because it restricts the amount of concurrency (the number of processes actually executing) at any time.

• Weak fairness is easy to implement. All that is needed is a scheduling discipline in which a ready process eventually gets to run for some nonzero duration, e.g., fifo.