Mutual Exclusion and Synchronisation

 Allowing multiple processes access to the same resources in a time sliced manner or potentially consecutively in the case of multiprocessor systems can cause many problems. This is due to the need to maintain data consistency, maintain true temporal dependencies and to ensure that each thread will properly release the resource as required when it has completed its action.

 Concurrent processes in multitasking and / or multiprocessing operating systems must deal with a number of potential problems

 

Process starvation or indefinite postponement A low priority process never gets access to the processor due to the higher effective processor access of other processes. Solution is to cause processes to 'age' or decline in priority as they use up CPU quanta.
Process deadlock Two or more processes are competing for resources, each blocking the other.
Race Conditions The processing result depends on when and how fast two or more processes complete their tasks.
 

The data consistency and race condition problems may be addressed by the implementation of Mutual Exclusion and Synchronisation rules between processes whereas starvation is a function of the scheduler.

There are a number of synchronisation primitives :

 

Events A thread may wait for events such as the setting of a flag, integer, signal or presence of an object. Until that event occurs the thread will be blocked and will be removed from the run queue. 
Critical Sections These are areas of code which can only be accessed by a single thread at any one time.
Mutual Exclusions mutexes are objects that ensure that only a single thread has access to a protected variable or code at any one time.
Semaphores These are similar to mutual exclusions but may include counters allowing only a specified number of threads access to a protected variable or code at any one time.
Atomic operations This mechanism ensures that an non decomposable transaction is completed by a thread before access to the same atomic operation is granted to another thread. The thread may have non-interruptable access to the CPU until the operation is completed.
 

Deadlock is a permanent blocking of a set of processes that either compute for system resources or communicate with each other [MAEK87]. Deadlock may be addressed by mutual exclusion or by deadlock avoidance. Mutual exclusion prevents two threads accessing the same resource simultaneously. Deadlock avoidance can include initiation denial or allocation denial, both of which serve to eliminate the state required for deadlock before it arises.

 Both Linux and Windows NT solve these problems in different ways. Windows NT has functions which equate to all of the above instances. Both implement multiprocessor mutual exclusion mechanisms called spin locks which effectively stall the processor until a lock is achieved for a critical section.