Unit III Process Coordination PDF

Unit III Process Coordination BY PROF. VISHAL NAYAKWADI Contents Synchronization: Principles of Concurrency, Requirements for Mutual Exclusion, Mutual Exclusion: Hardware Support, Operating System Support (Semaphores and Mutex), Programming Language Support (Monitors). Classical synchronization pr...

Unit III Process Coordination BY PROF. VISHAL NAYAKWADI Contents Synchronization: Principles of Concurrency, Requirements for Mutual Exclusion, Mutual Exclusion: Hardware Support, Operating System Support (Semaphores and Mutex), Programming Language Support (Monitors). Classical synchronization problems: Readers/Writers Problem, Producer and Consumer problem, Inter-process communication (Pipes, shared memory: system V) Deadlock: Deadlock Characterization, Methods for Handling Deadlocks, Deadlock Prevention, Deadlock Avoidance, Deadlock Detection, Recovery from Deadlock Synchronization Process Synchronization is the coordination of execution of multiple processes in a multi- process system to ensure that they access shared resources in a controlled and predictable manner. It aims to resolve the problem of race conditions and other synchronization issues in a concurrent system. The main objective of process synchronization is to ensure that multiple processes access shared resources without interfering with each other and to prevent the possibility of inconsistent data due to concurrent access. To achieve this, various synchronization techniques such as semaphores, monitors, and critical sections are used. In a multi-process system, synchronization is necessary to ensure data consistency and integrity, and to avoid the risk of deadlocks and other synchronization problems. Process synchronization is an important aspect of modern operating systems, and it plays a crucial role in ensuring the correct and efficient functioning of multi-process systems. Principles of Concurrency Both interleaved and overlapped processes can be viewed as examples of concurrent processes, they both present the same problems. The relative speed of execution cannot be predicted. It depends on the following: The activities of other processes The way operating system handles interrupts The scheduling policies of the operating system Problems in Concurrency Sharing global resources: Sharing of global resources safely is difficult. If two processes both make use of a global variable and both perform read and write on that variable, then the order in which various read and write are executed is critical. Optimal allocation of resources: It is difficult for the operating system to manage the allocation of resources optimally. Locating programming errors: It is very difficult to locate a programming error because reports are usually not reproducible. Locking the channel: It may be inefficient for the operating system to simply lock the channel and prevents its use by other processes. Race Condition Occurs when multiple processes or threads read and write data items The final result depends on the order of execution the “loser” of the race is the process that updates last and will determine the final value of the variable Operating System Concerns Design and management issues raised by the existence of concurrency: The OS must: be able to keep track of various processes allocate and de-allocate resources for each active process protect the data and physical resources of each process against interference by other processes ensure that the processes and outputs are independent of the processing speed Mutual Exclusion Mutual Exclusion is a property of process synchronization that states that “no two processes can exist in the critical section at any given point of time“. The term was first coined by Dijkstra. Mutual exclusion methods are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. The requirement of mutual exclusion is that when process P1 is accessing a shared resource R1, another process should not be able to access resource R1 until process P1 has finished its operation with resource R1. Examples of such resources include files, I/O devices such as printers, and shared data structures. Requirements for Mutual Exclusion Must be enforced A process that halts must do so without interfering with other processes No deadlock or starvation. A process must not be denied access to a critical section when there is no other process using it. No assumptions are made about relative process speeds or number of processes A process remains inside its critical section for a finite time only Mutual Exclusion: Hardware Support Interrupt Disabling  In a uniprocessor system, concurrent processes cannot have overlapped execution; they can only be interleaved.  To guarantee mutual exclusion, it is sufficient to prevent a process from being interrupted.  This capability can be provided in the form of primitives defined by the OS kernel for disabling and enabling interrupts.  Disadvantages  the efficiency of execution could be noticeably degraded  this approach will not work in a multiprocessor architecture Special Machine Instructions  During execution of the instruction, access to the memory location is blocked for any other instruction referencing that location.  Two of the most commonly implemented instructions are,  Compare & Swap Instruction  Exchange Instruction Compare & Swap Instruction The compare&swap instruction, also called a compare and exchange instruction, can be defined as follows: int compare_and_swap (int *word, int testval, int newval) { int oldval; oldval = *word if (oldval == testval) *word = newval; return oldval; } Exchange Instruction The exchange instruction can be defined as follows: void exchange (int register, int memory) { int temp; temp = memory; memory = register; register = temp; } The instruction exchanges the contents of a register with that of a memory location. Special Machine Instructions Advantages Applicable to any number of processes on either a single processor or multiple processors sharing main memory Simple and easy to verify It can be used to support multiple critical sections; each critical section can be defined by its own variable Disadvantages Busy-waiting is employed, thus while a process is waiting for access to a critical section it continues to consume processor time Starvation is possible when a process leaves a critical section and more than one process is waiting Deadlock is possible Operating System Support Semaphores We can view the semaphore as a variable that has an integer value upon which only three operations are defined:  A semaphore may be initialized to a nonnegative integer value.  The semWait operation decrements the semaphore value. If the value becomes negative, then the process executing the semWait is blocked. Otherwise, the process continues execution.  The semSignal operation increments the semaphore value. If the resulting value is less than or equal to zero, then a process blocked by a semWait operation, if any, is unblocked. Types of Semaphores  Binary Semaphore: This is also known as a mutex lock. It can have only two values – 0 and 1. Its value is initialized to 1. It is used to implement the solution of critical section problems with multiple processes.  Counting Semaphore: Its value can range over an unrestricted domain. It is used to control access to a resource that has multiple instances. Consequences There is no way to know which There is no way You don’t know process will to know before a whether another continue process process is waiting immediately on a decrements a so the number of uniprocessor semaphore unblocked system when two whether it will processes may be processes are block or not zero or one running concurrently Strong Semaphores the process that has been blocked the longest is released from the queue first (FIFO) Weak Semaphores the order in which processes are removed from the queue is not specified Mutex A concept related to the binary semaphore is the mutex. A key difference between the two is that the process that locks the mutex (sets the value to zero) must be the one to unlock it (sets the value to 1). In contrast, it is possible for one process to lock a binary semaphore and for another to unlock it. Programming Language Support (Monitors) Programming language construct that provides equivalent functionality to that of semaphores and is easier to control Implemented in a number of programming languages including Concurrent Pascal, Pascal-Plus, Modula-2, Modula-3, and Java Has also been implemented as a program library Software module consisting of one or more procedures, an initialization sequence, and local data Monitor Local data Characteristics variables are accessible only by the monitor’s Only one procedures and process may be not by any executing in the external monitor at a procedure time Process enters monitor by invoking one of its procedures Achieved by the use of condition variables that are contained within the monitor and accessible only within the monitor Condition variables are operated on by two functions: cwait(c): suspend execution of the calling process on condition c csignal(c): resume execution of some process blocked after a cwait on the same condition Classical synchronization problems Readers/Writers Problem Producer and Consumer problem Dining-Philosophers Problem Readers/Writers Problem A data area is shared among many processes some processes only read the data area, (readers) and some only write to the data area (writers) Conditions that must be satisfied: One set of data is shared among a number of processes. Once a writer is ready, it performs its write. Only one writer may write at a time. If a process is writing, no other process can read it. If at least one reader is reading, no other process can write. Readers may not write and only read. Producer and Consumer problem General Situation: The Problem: ensure that the one or more producer can’t producers are add data into generating data and full buffer and placing these in a buffer consumer can’t a single consumer is remove data from an empty taking items out of the buffer one at time buffer only one producer or consumer may access the buffer at any one Solution to Producer-Consumer Problem To solve the Producer-Consumer problem three semaphores variable are used: Full  The full variable is used to track the space filled in the buffer by the Producer process. It is initialized to 0 initially as initially no space is filled by the Producer process. Empty  The Empty variable is used to track the empty space in the buffer. The Empty variable is initially initialized to the BUFFER-SIZE as initially, the whole buffer is empty. Mutex  Mutex is used to achieve mutual exclusion. mutex ensures that at any particular time only the producer or the consumer is accessing the buffer.  Mutex - mutex is a binary semaphore variable that has a value of 0 or 1.  We will use the Signal() and wait() operation in the above-mentioned semaphores to arrive at a solution to the Producer-Consumer problem.  Signal() - The signal function increases the semaphore value by 1. Wait() - The wait operation decreases the semaphore value by 1. Dining-Philosophers Problem The Dining Philosopher Problem states that K philosophers seated around a circular table with one chopstick between each pair of philosophers. There is one chopstick between each philosopher. A philosopher may eat if he can pickup the two chopsticks adjacent to him. One chopstick may be picked up by any one of its adjacent followers but not both. This problem involves the allocation of limited resources to a group of processes in a deadlock-free and starvation-free manner. Inter-process communication There are several methods for communication within a single machine. These methods are known as Interprocess Communication (IPC) and allow different processes to communicate with each other. Some common methods of IPC include Pipes, Named Pipes, Message Queues, Shared Memory, Remote Procedure Calls (RPC), Semaphores and Sockets. Pipes A pipe acts as a conduit allowing two processes to communicate. Pipes were one of the first IPC mechanisms in early UNIX systems. They typically provide one of the simpler ways for processes to communicate with one another, although they also have some limitations. There are two types of pipes: Ordinary pipes Named pipes. Ordinary pipes Ordinary pipes allow two processes to communicate in standard producer– consumer fashion: the producer writes to one end of the pipe (the write end) and the consumer reads from the other end (the read end). As a result, ordinary pipes are unidirectional, allowing only one-way communication. If two-way communication is required, two pipes must be used, with each pipe sending data in a different direction. Ordinary pipes on Windows systems are termed anonymous pipes. Named pipes Communication can be bidirectional, and no parent–child relationship is required. Once a named pipe is established, several processes can use it for communication. In fact, in a typical scenario, a named pipe has several writers. Additionally, named pipes continue to exist after communicating processes have finished. Both UNIX and Windows systems support named pipes, although the details of implementation differ greatly. Next, we explore named pipes in each of these systems. Named pipes are referred to as FIFOs in UNIX systems. Once created, they appear as typical files in the file system. Named pipes are a type of pipe that has a unique name, and can be accessed by multiple processes. Named pipes can be used for communication between processes running on the same host or between processes running on different hosts over a network. Shared memory: system V Shared memory is one of the three inter process communication (IPC) mechanisms available under Linux and other Unix-like systems. The other two IPC mechanisms are the message queues and semaphores. In case of shared memory, a shared memory segment is created by the kernel and mapped to the data segment of the address space of a requesting process. A process can use the shared memory just like any other global variable in its address space. System V Shared Memory Calls shmget: Creates a shared memory segment or obtains an existing one. It returns an identifier that's similar to a file identifier. shmat: Makes the shared memory segment a virtual segment of the process memory. shmdt: Detaches memory segments. shmctl: Deallocates the shared memory segment. How does IPC Using Shared Memory work? A process creates a shared memory segment using shmget(). The original owner of a shared memory segment can assign ownership to another user with shmctl(). It can also revoke this assignment. Other processes with proper permission can perform various control functions on the shared memory segment using shmctl(). Once created, a shared segment can be attached to a process address space using shmat(). It can be detached using shmdt(). The attaching process must have the appropriate permissions for shmat(). Once attached, the process can read or write to the segment, as the permission requested in the attach operation allows. A shared segment can be attached multiple times by the same process. Deadlock Deadlock is a situation in computing where two or more processes are unable to proceed because each is waiting for the other to release resources. Key concepts include mutual exclusion, resource holding, circular wait, and no preemption. Consider an example when two trains are coming toward each other on the same track and there is only one track, none of the trains can move once they are in front of each other. Examples of Deadlock  There are several examples of deadlock. Some of them are mentioned below.  The system has 2 tape drives. P0 and P1 each hold one tape drive and each needs another one.  Semaphores A and B, initialized to 1, P0, and P1 are in deadlock as follows:  P0 executes wait(A) and preempts.  P1 executes wait(B).  Now P0 and P1 enter in deadlock. How Does Deadlock occur in the Operating System? Before going into detail about how deadlock occurs in the Operating System, let’s first discuss how the Operating System uses the resources present. A process in an operating system uses resources in the following way. Requests a resource Use the resource Releases the resource A situation occurs in operating systems when there are two or more processes that hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1. Deadlock Characterization Mutual exclusion.  At least one resource must be held in a non-sharable mode; that is, only one thread at a time can use the resource. If another thread requests that resource, the requesting thread must be delayed until the resource has been released. Hold and wait.  A thread must be holding at least one resource and waiting to acquire additional resources that are currently being held by other threads. No preemption.  Resources cannot be preempted; that is, a resource can be released only voluntarily by the thread holding it, after that thread has completed its task. Circular wait.  A closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain  Resource Allocation Graphs The resource allocation graph is a directed graph that depicts a state of the system of resources and processes, with each process and each resource represented by a node. A graph edge directed from a process to a resource indicates a resource that has been requested by the process but not yet granted (Figure 6.5a). Within a resource node, a dot is shown for each instance of that resource. Examples of resource types that may have multiple instances are I/O devices that are allocated by a resource management module in the OS. A graph edge directed from a reusable resource node dot to a process indicates a request that has been granted (Figure 6.5b); that is, the process has been assigned one unit of that resource. A graph edge directed from a consumable resource node dot to a process indicates that the process is the producer of that resource. Figure 6.5c shows an example deadlock. There is only one unit each of resources Ra and Rb. Process P1 holds Rb and requests Ra, while P2 holds Ra but requests Rb. Figure 6.5d has the same topology as Figure 6.5c, but there is no deadlock because multiple units of each resource are available. Methods for Handling Deadlocks We can deal with the deadlock problem in one of three ways: We can ignore the problem altogether and pretend that deadlocks never occur in the system. We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocked state. We can allow the system to enter a deadlocked state, detect it, and recover. Deadlock Prevention Mutual Exclusion  In general, the first of the four listed conditions cannot be disallowed.  If access to a resource requires mutual exclusion, then mutual exclusion must be supported by the OS.  Some resources, such as files, may allow multiple accesses for reads but only exclusive access for writes.  Even in this case, deadlock can occur if more than one process requires write permission. Hold and Wait  The hold-and-wait condition can be prevented by requiring that a process request all of its required resources at one time and blocking the process until all requests can be granted simultaneously. This approach is inefficient in two ways.  First, a process may be held up for a long time waiting for all of its resource requests to be filled, when in fact it could have proceeded with only some of the resources.  Second, resources allocated to a process may remain unused for a considerable period, during which time they are denied to other processes.  Another problem is that a process may not know in advance all of the resources that it will require. No Preemption  This condition can be prevented in several ways. First, if a process holding certain resources is denied a further request, that process must release its original resources and, if necessary, request them again together with the additional resource.  Alternatively, if a process requests a resource that is currently held by another process, the OS may preempt the second process and require it to release its resources. Circular Wait  The circular-wait condition can be prevented by defining a linear ordering of resource types.  If a process has been allocated resources of type R, then it may subsequently request only those resources of types following R in the ordering.  To see that this strategy works, let us associate an index with each resource type.  Then resource Ri precedes Rj in the ordering if i < j. Now suppose that two processes, A and B, are deadlocked because A has acquired Ri and requested Rj, and B has acquired Rj and requested Ri.  This condition is impossible because it implies i " j and j " i.  As with hold-and-wait prevention, circular-wait prevention may be inefficient, slowing down processes and denying resource access unnecessarily. Deadlock Avoidance A deadlock avoidance policy grants a resource request only if it can establish that granting the request cannot lead to a deadlock either immediately or in the future. The kernal lacks detailed knowledge about future behavior of processes, so it cannot accurately predict deadlocks. To facilitate deadlock avoidance under these conditions, it uses the following conservative approach: Each process declares the maximum number of resource units of each class that it may require. The kernal permits a process to request these resource units in stages- i.e. a few resource units at a time- subject to the maximum number declared by it and uses a worst-case analysis technique to check for the possibility of future deadlocks. A request is granted only if there is no possibility of deadlocks; otherwise, it remains pending until it can be granted. This approach is conservative because a process may complete its operation without requiring the maximum number of units declared by it. Deadlock Avoidance Techniques Safe State and Unsafe State Resource-Allocation Graph Algorithm Banker’s Algorithm Safe State and Unsafe State Banker’s Algorithm The banker's algorithm is a deadlock avoidance algorithm used in operating systems. It was proposed by Edsger Dijkstra in 1965. The banker's algorithm works on the principle of ensuring that the system has enough resources to allocate to each process so that the system never enters a deadlock state. It works by keeping track of the total number of resources available in the system and the number of resources allocated to each process. The algorithm is used to prevent deadlocks that can occur when multiple processes are competing for a finite set of resources. The resources can be of different types such as memory, CPU cycles, or I/O devices. It works by first analysing the current state of the system and determining if granting a resource request from a process will result in a safe state. Initialize the system  Define the number of processes and resource types.  Define the total number of available resources for each resource type.  Create a matrix called the "allocation matrix" to represent the current resource allocation for each process.  Create a matrix called the "need matrix" to represent the remaining resource needs for each process. Define a request  A process requests a certain number of resources of a particular type. Check if the request can be granted  Check if the requested resources are available.  If the requested resources are not available, the process must wait.  If the requested resources are available, go to the next step. Check if the system is in a safe state Simulate the allocation of the requested resources to the process. Check if this allocation results in a safe state, meaning there is a sequence of allocations that can satisfy all processes without leading to a deadlock. If the state is safe, grant the request by updating the allocation matrix and the need matrix. If the state is not safe, do not grant the request and let the process wait. Release the Resources When a process has finished its execution, releases its allocated resources by updating the allocation matrix and the need matrix. Deadlock Detection A check for deadlock can be made as frequently as each resource request or, less frequently, depending on how likely it is for a deadlock to occur. Checking at each resource request has two advantages: it leads to early detection, and the algorithm is relatively simple because it is based on incremental changes to the state of the system. On the other hand, such frequent checks consume considerable processor time. In addition, a request matrix Q is defined such that Qij represents the amount of resources of type j requested by process i. The algorithm proceeds by marking processes that are not deadlocked. Initially, all processes are unmarked. Then the following steps are performed: Mark each process that has a row in the Allocation matrix of all zeros. Initialize a temporary vector W to equal the Available vector. Find an index i such that process i is currently unmarked and the ith row of Q is less than or equal to W. That is, Qik ≤ Wk, for 1 ≤ k ≤ m. If no such row is found, terminate the algorithm. If such a row is found, mark process i and add the corresponding row of the allocation matrix to W. That is, set Wk = Wk + Aik, for 1 ≤ k ≤ m. Return to step 3. A deadlock exists if and only if there are unmarked processes at the end of the algorithm. Each unmarked process is deadlocked. Recovery from Deadlock When a detection algorithm determines that a deadlock exists, several alternatives are available. One possibility is to inform the operator that a deadlock has occurred and to let the operator deal with the deadlock manually. Another possibility is to let the system recover from the deadlock automatically. There are two options for breaking a deadlock. One is simply to abort one or more threads to break the circular wait. The other is to preempt some resources from one or more of the deadlocked threads. Process and Thread Termination To eliminate deadlocks by aborting a process or thread, we use one of two methods. In both methods, the system reclaims all resources allocated to the terminated processes. Abort all deadlocked processes.  This method clearly will break the deadlock cycle, but at great expense. The deadlocked processes may have computed for a long time, and the results of these partial computations must be discarded and probably will have to be recomputed later. Abort one process at a time until the deadlock cycle is eliminated.  This method incurs considerable overhead, since after each process is aborted, a deadlock-detection algorithm must be invoked to determine whether any processes are still deadlocked. Resource Preemption If preemption is required to deal with deadlocks, then three issues need to be addressed: Selecting a victim.  Which resources and which processes are to be preempted?  As in process termination, we must determine the order of pre-emption to minimize cost. Cost factors may include such parameters as the number of resources a deadlocked process is holding and the amount of time the process has thus far consumed. Rollback.  If we preempt a resource from a process, what should be done with that process?  Clearly, it cannot continue with its normal execution; it is missing some needed resource. We must roll back the process to some safe state and restart it from that state.  Since, in general, it is difficult to determine what a safe state is, the simplest solution is a total rollback: abort the process and then restart it.  Although it is more effective to roll back the process only as far as necessary to break the deadlock, this method requires the system to keep more information about the state of all running processes. Starvation.  How do we ensure that starvation will not occur? That is, how can we guarantee that resources will not always be preempted from the same process?