Notes: Concurrency | Operating System - Computer Science Engineering (CSE) PDF Download

A sequential program has a single thread of control. Its execution is called a process. A concurrent program has multiple threads of control. They may be executed as parallel processes. This lesson presents main principles of concurrent programming. A concurrent program can be executed by

• Multiprogramming: processes share one or more processors
• Multiprocessing: each process runs on its own processor but with shared memory
• Distributed processing: each process runs on its own processor connected by a network to others

Properties of Concurrent Processes

Concurrent programs are governed by two key principles. These are the principles of "safety" and "liveness".

• The "safety" principle states "nothing bad can happen".
• The "liveness" principle states "eventually, something good happens".

 Safety

• Safety in general means that only one thread can access the data at a time, and ensures that the data remain in a consistent state during and after the operation. Supopose, functions "A" and "B" below run concurrently. What is a resultant value of "x"? var x = 0; function A() {x = x + 1;} function B() {x = x + 2;}

• x = 3 if operations x = x + 1 and x = x + 2 are atomic, i.e. cannot be interrupted.
• x = 1,2 or 3 if operations x = x + 1 and x = x + 2 can interrupt one another.

If we read/modify/write a file and allow operations to interrupt one another, the file might be easily corrupted. Safety is ensured by implementing

1. "mutual exclusion" and
2. "condition synchronization"

• When operating on shared data. "Mutual exclusion" means that that only one thread can access the data at a time, and ensures that the data remain in a consistent state during and after the operation.
•  (atomic update). "Condition synchronization" means that operations may be delayed if shared resources are in the wrong state (e.g., read from empty buffer).

 Liveness

• Mutual exclusion solves many safety issues, but gives rise to other problems, in particular deadlock and starvation. The problem of deadlock arises when a thread holds a lock on one object and blocks attempting to gain a lock on another object, because the second object is already locked by a different thread, which is blocked by the lock the original thread currently holds.

• Both threads settle down to wait for the other to release the necessary lock, but neither thread will ever release their own lock because they are both blocked waiting for the other lock to be released first. Stated like this, it may seem an unlikely occurrence, but in fact, deadlock is one of the most common concurrent programming bugs. 
• The trouble is that deadlock spreads out through more than two threads and can involve complex interdependencies. Deadlock is an extreme form of starvation. Starvation occurs when a thread cannot proceed because it cannot gain access to a resource it requires.

The problems of deadlock and starvation bring us to the next big topic in concurrent programming − liveness. Concurrent programs are also described as having a ‘liveness’ property if there are:

• No Deadlock: some process can always access a shared resource
• No Starvation: all processes can eventually access shared resources

• The liveness property states that eventually something good happens. Deadlocked programs don’t meet this requirement. Liveness is gradational. Programs can be ‘nearly’ dead or ‘not very’ live. Every time you use a synchronized method, you force sequential access to an object.
•  If you have a lot of threads calling a lot of synchronized methods on the same object, your program will slow down a lot. A programming language must provide mechanisms for Expressing Concurrency:

• Process creation how do you specify concurrent processes?
• Communication: how do processes exchange information?
• Synchronization: how do processes maintain consistency?

Process creation

• Co-routines how do you specify concurrent processes?
• Fork and Join: how do processes exchange information?
• Cobegin/coend: how do processes maintain consistency?

Co-routines are only pseudo-concurrent and require explicit transfers of control:

Co-routines can be used to implement most higher-level concurrent mechanisms. Fork can be used to create any number of processes:

Join waits for another process to terminate. Fork and join are unstructured, so require care and discipline. Cobegin/coend blocks are better structured, but they can only create a fixed number of processes.

The caller continues when all of the co-blocks have terminated.