UNIT 2 OS PDF

UNIT – II : Process and Threads Syllabus: - Introduction to Process – Scheduling – Operations – Inter-process Communication. Synchronization: Critical Section – Hardware - Mutex - Semaphore – Monitors. Threads: Multithreading Models Thread Library- Issues Introducti...

UNIT – II : Process and Threads Syllabus: - Introduction to Process – Scheduling – Operations – Inter-process Communication. Synchronization: Critical Section – Hardware - Mutex - Semaphore – Monitors. Threads: Multithreading Models Thread Library- Issues Introduction to Process 1. The Process One impediment to our discussion of operating systems is the question of what to call all the CPU activities. A batch system executes jobs, whereas a on a single- user system and timeshared system has user programs, or tasks. Even if the user can execute only one program at a time, the operating system may need to support its own internal programmed activities, such as memory management. In many respects, all these activities are similar, so we call all of them processes. The terms job and process are used almost interchangeably. The term process, much of operating-system theory and terminology was developed during a time when the major activity of operating systems was job processing. A process is a program in execution. A process is more than the program code, which is sometimes known as the text section. It also includes the current activity, as represented by the value of the program counter and the contents of the processor's registers. A process will need certain resources-such as CPU time, memory, files, and I/O devices-to accomplish its task. In addition, a process generally includes the process stack, which contains temporary data (such as method parameters, return addresses, and local variables), and a data section, which contains global variables. These resources are allocated to the process either when it is created or while it is executing. A process is the unit of work in most systems. Such a system consists of a collection of processes: Operating-system processes execute system code, and user processes execute user code. All these processes may execute concurrently. Although two processes may be associated with the same program, they are nevertheless considered two separate execution sequences. 2. Process State Figure 1 Diagram of process state As a process executes, it changes state. The state of a process is defined in part by the current activity of that process. Each process may be in one of the following states: i. New: The process is being created. ii. Running: Instructions are being executed. iii. W aiting: The process is waiting for some event to occur (such as an I/O completion or reception of a signal). iv. Ready: The process is waiting to be assigned to a processor. Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 1  v. Terminated: The process has finished execution. These state names are arbitrary, and they vary across operating systems. The states that they represent are found on all systems. Certain operating systems more finely delineate process states. Only one process can be running on any processor at any instant, although many processes may be ready and waiting. The state diagram corresponding to these states is presented in Figure 1. 3. Process Control Blocks (PCB) Each process is represented in the operating system by a process control block (PCB)-also called a task control block. A PCB is shown in Figure 2. It contains many pieces of information associated with a specific process, including these: Figure 2 Process control block (PCB). I. Process state: The state may be new, ready, running, waiting, halted, and SO on. II. Program counter: The counter indicates the address of the next instruction to be executed for this process. III. CPU registers: The registers vary in number and type, depending on the computer architecture. They include accumulators, index registers, stack pointers, and general-purpose registers, plus any condition-code information. Along with the program counter, this state information must be saved when an interrupt occurs, to allow the process to be continued correctly afterward. IV. CPU-scheduling information: This information includes a process priority, pointers to scheduling queues, and any other scheduling parameters. V. M emory-management information: This information may include such information as the value of the base and limit registers, the page tables, or the segment tables, depending on the memory system used by the operating system. VI. Accounting information: This information includes the amount of CPU and real time used, time limits, account numbers, job or process numbers, and so on. VII. Status information: The information includes the list of I/O devices allocated to this process, a list of open files, and so on. The PCB simply serves as the repository for any information that may vary from process to process. Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 2  Process Scheduling The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization. The objective of time sharing is to switch the CPU among processes so frequently that users can interact with each program while it is running. To meet these objectives, the process scheduler selects an available process (possibly from a set of several available processes) for program execution on the CPU. For a single-processor system, there will never be more than one running process. If there are more processes, the rest will have to wait until the CPU is free and can be rescheduled. 1. Scheduling Queues As processes enter the system, they are put into a job queue. This queue consists of all processes in the system. The processes that are residing in main memory and are ready and waiting to execute are kept on a list called the ready queue. This queue is generally stored as a linked list. A ready-queue header contains pointers to the first and final PCBs in the list. We extend each PCB to include a pointer field that points to the next PCB in the ready queue. The operating system also has other queues. When a process is allocated the CPU, it executes for a while and eventually quits, is interrupted, or waits for the occurrence of a particular event, such as the completion of an I/O request. Since the system has many processes, the disk may be busy with the I/O request of some other process. The process therefore may have to wait for the disk. The list of processes waiting for a particular I/O device is called a device queue. Each device has its own device queue. Figure 3 The ready queue and various I/O device queues. A common representation of process scheduling is a queueing diagram, such as that in Figure 4. Each rectangular box represents a queue. Two types of queues are present: the ready queue and a set of device queues. The circles represent Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 3  the resources that serve the queues, and the arrows indicate the flow of processes in the system. A new process is initially put in the ready queue. It waits in the ready queue until it is selected for execution (or dispatched). Once the process is assigned to the CPU and is executing, one of several events could occur: The process could issue an I/O request, and then be placed in an I/O queue. The process could create a new sub process and wait for its termination. The process could be removed forcibly from the CPU, as a result of an interrupt, and be put back in the ready queue. The process eventually switches from the waiting state to the ready state, and is then put back in the ready queue. A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB and resources deallocated. Figure 4 Queueing-diagram representation of process scheduling 2. Schedulers A process migrates between the various scheduling queues throughout its lifetime. The operating system must select, for scheduling purposes, processes from these queues in some fashion. The selection process is carried out by the appropriate scheduler. In a batch system, often more processes are submitted than can be executed immediately. These processes are spooled to a mass- storage device, where they are kept for later execution. The long-term scheduler, or job scheduler, selects processes from this pool and loads them into memory for execution. The short-term scheduler, or CPU scheduler, selects from among the processes that are ready to execute, and allocates the CPU to one of them. The primary distinction between these two schedulers is the frequency of their execution. The short-term scheduler must select a new process for the CPU frequently. A process may execute for only a few milliseconds before waiting for an I/O request. Often, the short-term scheduler executes at least once every 100 milliseconds. Because of the brief time between executions, the short-term scheduler must be fast. The long-term scheduler, on the other hand, executes much less frequently. The long-term scheduler controls the degree of multiprogramming the number of processes in memory. If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system. Thus, the long-term scheduler may need to be invoked only when a process leaves the system. Because of the longer interval between executions, the long-term scheduler can afford to take more time to select a process for execution. The long-term scheduler must make a careful Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 4  selection. In general, most processes can be described as either I/O bound or CPU bound. An I/O-bound process spends more of its time doing I/O than it spends doing computations. A CPU-bound process, on the other hand, generates I/O requests infrequently, using more of its time doing computation than an I/O- bound process uses. The long-term scheduler should select a good process mix of I/O-bound and CPU-bound processes. If all processes are I/O bound, the ready queue will almost always be empty, and the short-term scheduler will have little to do. If all processes are CPU bound, the I/O waiting queue will almost always be empty, devices will go unused, and again the system will be unbalanced. The system with the best performance will have a combination of CPU-bound and I/O-bound processes. Some operating systems, such as time-sharing systems, may introduce an additional, intermediate level of scheduling. This medium-term scheduler, diagrammed in Figure 4, removes processes from memory and thus reduces the degree of multiprogramming. At some later time, the process can be reintroduced into memory and its execution can be continued where it left off. This scheme is called swapping. The process is swapped out, and is later swapped in, by the medium-term scheduler. Swapping may be necessary to improve the process mix, or because a change in memory requirements has overcommitted available memory, requiring memory to be freed up. Figure 5 Addition of medium-term scheduling to the queueing diagram 3. Context Switch Figure 6 Diagram showing CPU switch from process to process. Switching the CPU to another process requires saving the state of the old process and loading the saved state for the new process. This task is known as a context switch. The context of a process is represented in the PCB of a process; it includes the value of the CPU registers, the process state, and memory- management information. When a context switch occurs, the kernel saves the context of the old process in its PCB an d loads the saved context of the new process scheduled to run. Context-switch time is pure Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 5  overhead, because the system does no useful work while switching. Its speed varies from machine to machine, depending on the memory speed, the number of registers that must be copied, and the existence of special instructions. Typical speeds range from 1 to 1000 microseconds. Context-switch times are highly dependent on hardware support. 4. CPU-I/O Burst Cycle The success of CPU scheduling depends on the following observed property of processes: Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, then another CPU burst, then another I/O burst, and so on. Eventually, the last CPU burst will end with a system request to terminate execution, rather than with another I/O burst (Figure 7). The durations of these CPU bursts have been extensively measured. Although they vary greatly by process and by computer, an I/O-bound program would typically have many very short CPU bursts. A CPU-bound program might have a few very long CPU bursts. This distribution can help us select an appropriate CPU-scheduling algorithm. Figure 7 Alternating sequence of CPU and I/O bursts. Process Operations The processes in most systems can execute concurrently, and they may be created and deleted dynamically. Process Creation A process may create several new processes, via a create-process system call, during the course of execution. The creating process is called a parent process, and the new processes are called the children of that process. Each of these new processes may in turn create other processes, forming a tree of processes. Most operating systems (including UNIX and the Windows family of operating systems) identify processes according to a unique process identifier (or pid), which is typically an integer number. In general, a process will need certain resources (CPU time, memory, files, I/O devices) to accomplish its task. When a process creates a sub-process, that sub-process may be able to obtain its resources directly from the operating system, or it may be constrained to a subset of the resources of the parent process. The parent may have to partition its resources among its children, or it may be able to share some resources (such as memory or files) among several of its children. Restricting a child process to a subset of Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 6  the parent's resources prevents any process from overloading the system by creating too many sub-processes. In addition to the various physical and logical resources that a process obtains when it is created, initialization data (input) may be passed along by the parent process to the child process. When a process creates a new process, two possibilities exist in terms of execution: 1. The parent continues to execute concurrently with its children. 2. The parent waits until some or all of its children have terminated. There are also two possibilities in terms of the address space of the new process: 1. The child process is a duplicate of the parent process (it has the same program and data as the parent). 2. The child process has a new program loaded into it. The new process consists of a copy of the address space of the original process. This mechanism allows the parent process to communicate easily with its child process. Both processes (the parent and the child) continue execution at the instruction after the fork(), with one difference: The return code for the fork() is zero for the new (child) process, whereas the (nonzero) process identifier of the child is returned to the parent. the exec() system call is used after a fork() system call by one of the two processes to replace the process's memory space with a new program. Process Termination A process terminates when it finishes executing its final statement and asks the operating system to delete it by using the exit () system call. At that point, the process may return a status value (typically an integer) to its parent process (via the wait() system call). All the resources of the process—including physical and virtual memory, open files, and I/O buffers—are deallocated by the operating system. Termination can occur in other circumstances as well. A process can cause the termination of another process via an appropriate system call. A parent may terminate the execution of one of its children for a variety of reasons, such as these: 1. The child has exceeded its usage of some of the resources that it has been allocated. (To determine whether this has occurred, the parent must have a mechanism to inspect the state of its children.) 2. The task assigned to the child is no longer required. 3. The parent is exiting, and the operating system does not allow a child to continue if its parent terminates. Inter-process Communication Cooperating processes can communicate in a shared-memory environment. The scheme requires that these processes share a common buffer pool, and that the code for implementing the buffer be written explicitly by the application Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 7  programmer. Another way to achieve the same effect is for the operating system to provide the means for cooperating processes to communicate with each other via an interprocess communication (IPC) facility. IPC provides a mechanism to allow processes to communicate and to synchronize their actions without sharing the same address space. IPC is particularly useful in a distributed environment where the communicating processes may reside on different computers connected with a network. An example is a chat program used on the World Wide Web. 1. M essage-Passing System The function of a message system is to allow processes to communicate with one another without the need to resort to shared data. In this scheme, services are provided as ordinary user processes. That is, the services operate outside of the kernel. Communication among the user processes is accomplished through the passing of messages. An IPC facility provides at least the two operations: send(message) and receive(message). M essages sent by a process can be of either fixed or variable size. If only fixed-sized messages can be sent, the system-level implementation is straightforward. This restriction makes the task of programming more difficult. On the other hand, variable-sized messages require a more complex system-level implementation, but the programming task becomes simpler. If processes P and Q want to communicate, they must send messages to and receive messages from each other; a communication link must exist between them. This link can be implemented in a variety of ways. It can be done through several methods, for logically implementing a link and the send/receive operations:  Direct or indirect communication  Symmetric or asymmetric communication  Automatic or explicit buffering  Send by copy or send by reference  Fixed-sized or variable-sized messages 2. Naming Processes that want to communicate must have a way to refer to each other. They can use either direct or indirect communication. i. Direct Communication: With direct communication, each process that wants to communicate must explicitly name the recipient or sender of the communication. In this scheme, the send and receive primitives are defined as: Send (P, message) – send message to process P. Receive (Q, message) – receive a message from process Q A communication link in this scheme has the following properties: 1. A link is established automatically between every pair of processes that want to communicate. The processes need to know only each other's identity to communicate. 2. A link is associated with exactly two processes. Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 8  3. Exactly one link exists between each pair of processes. This scheme exhibits symmetry in addressing; that is, both the sender and the receiver processes must name the other to communicate. A variant of this scheme employs asymmetry in addressing. Only the sender names the recipient; the recipient is not required to name the sender. In this scheme, the send and receive primitives are defined as follows: Send (P, message) – send message to process P. Receive (id, message) – receive a message from any process; the variable id is set to the name of the process with which communication has taken place. The disadvantage in both symmetric and asymmetric schemes is the limited modularity of the resulting process definitions. Changing the name of a process may necessitate examining all other process definitions. ii. Indirect Communication: With indirect communication, the messages are sent to and received from mailboxes, or ports. A mailbox can be viewed abstractly as an object into which messages can be placed by processes and from which messages can be removed. Each mailbox has a unique identification. In this scheme, a process can communicate with some other process via a number of different mailboxes. Two processes can communicate only if they share a mailbox. The send and receive primitives are defined as follows: send (A, message) - Send a message to mailbox A. receive (A, message) -Receive a message from mailbox A. In this scheme, a communication link has the following properties: 1. A link is established between a pair of processes only if both members of the pair have a shared mailbox. 2. A link may be associated with more than two processes. 3. A number of different links may exist between each pair of communicating processes, with each link corresponding to one mailbox. Now suppose that processes P1, P2, and P3 all share mailbox A. Process P1 sends a message to A, while P2 and P3 each execute a receive from A. Which process will receive the message sent by P1? The answer depends on the scheme that we choose: 1. Allow a link to be associated with at most two processes. 2. Allow at most one process at a time to execute a receive operation. 3. Allow the system to select arbitrarily which process will receive the message (that is, either P2 or P3, but not both, will receive the message). The system may identify the receiver to the sender. A mailbox may be owned either by a process or by the operating system. If the mailbox is owned by a process (that is, the mailbox is part of the address space of the process), then we distinguish between the owner (who can only receive messages through this mailbox) and the user (who can only send messages to the mailbox). Since each mailbox has a unique owner, there can be no confusion about who should receive a message sent to this mailbox. When a process that owns a mailbox terminates, the mailbox disappears. Any process that Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 9  subsequently sends a message to this mailbox must be notified that the mailbox no longer exists. On the other hand, a mailbox owned by the operating system is independent and is not attached to any particular process. The operating system then must provide a mechanism that allows a process to do the following: 1. Create a new mailbox. 2. Send and receive messages through the mailbox. 3. Delete a mailbox. 3. Synchronization Communication between processes takes place by calls to send and receive primitives. There are different design options for implementing each primitive. Message passing may be either blocking or non-blocking also known as synchronous and asynchronous. 1. Blocking send: The sending process is blocked until the message is rece ived by the receiving process or by the mailbox. 2. Nonblocking send: The sending process sends the message and resumes operation. 3. Blocking receive: The receiver blocks until a message is available. 4. Nonblocking receive: The receiver retrieves either a valid message or a null. Different combinations of send and receive are possible. 4. Buffering Whether the communication is direct or indirect, messages exchanged by communicating processes reside in a temporary queue. Basically, such a queue can be implemented in three ways: Zero capacity: The queue has maximum length 0; thus, the link cannot have any messages waiting in it. In this case, the sender must block until the recipient receives the message. The zero-capacity case is sometimes referred to as a message system with no buffering; the other cases are referred to as automatic buffering. Bounded capacity: The queue has finite length n; thus, at most n messages can reside in it. If the queue is not full when a new message is sent, the latter is placed in the queue and the sender can continue execution without waiting. The link has a finite capacity, however. If the link is full, the sender must block until space is available in the queue. Unbounded capacity: The queue has potentially infinite length; thus, any number of messages can wait in it. The sender never blocks. Process Synchronization: A cooperating process is one that can affect or be affected by other processes executing in the system. Cooperating processes may either directly share a logical address space (that is, both code and data), or be allowed to share data Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 10  only through files. The former case is achieved through the use of lightweight processes or threads. Concurrent access to shared data may result in data inconsistency. Models were developed for system consisting of a number of cooperating sequential processes, all running asynchronously and possibly sharing data. A situation like this, where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place, is called a race condition. To guard against the race condition, we need to ensure that only one process at a time can be manipulating the variable counter. To make such a guarantee, we require some form of synchronization of the processes. Such situations occur frequently in operating systems as different parts of the system manipulate resources and we want the changes not to interfere with one another. A major concerned is with the issue of process synchronization and coordination. Critical Section A system consisting of n processes {Po,P1,..., Pn-1}. Each process has a segment of code, called a critical section, in which the process may be changing common variables, updating a table, writing a file, and so on. The important feature of the system is that, when one process is executing in its critical section, no other process is to be allowed to execute in its critical section. Thus, the execution of critical sections by the processes is mutually exclusive in time. The critical- section problem is to design a protocol that the processes can use to cooperate. Each process must request permission to enter its critical section. The section of code implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the remainder section. do { Entry Section critical section Exit Section reminder section } while (1); Figure 8 General structure of a typical process Pi. A solution to the critical-section problem must satisfy the following three requirements: 1. M utual Exclusion: If process Pi is executing in its critical section, then no other processes can be executing in their critical sections. 2. Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely. Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 11  3. Bounded W aiting: There exists a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. Assume that each process is executing at a nonzero speed. However, we can make no assumption concerning the relative speed of the n processes. Solutions to the critical-section problem that satisfy these three requirements do not rely on any assumptions concerning the hardware instructions or the number of processors that the hardware supports. The basic machine language instructions such as load, store, and test are executed atomically. That is, if two such instructions are executed concurrently, the result is equivalent to their sequential execution in some unknown order. Thus, if a load and a store are executed concurrently, the load will get either the old value or the new value, but not some combination of the two. When presenting an algorithm, we define only the variables used for synchronization purposes, and describe only a typical process Pi whose general structure is shown in Figure 9. The entry section and exit section are enclosed in boxes to highlight these important segments of code. 1. Two-Process Solutions In this solution, we put our attention to algorithms that are applicable to only two processes at a time. The processes are numbered P0 and P1 or vice versa. For convenience, when presenting Pi, we use Pj to denote the other process; that is, j == 1 – I or vice versa. a. Algorithm 1 turn = 1 ( here i = 1 & j = 0 ) turn = 0 do { do { while (turn!=i) while (turn!=j) critical section critical section turn = j; turn = i; reminder section reminder section } while (1); } while (0); Figure 9 The structure of process Pi in algorithm 1. Where turn = 0 or 1 Approach first is, let the processes share a common integer variable turn initialized to 0 or 1. If turn == i, then process Pi is allowed to execute in its critical section. The structure of process Pi is shown in Figure 9. This solution ensures that only one process at a time can be in its critical section. However, it does not satisfy the progress requirement, since it requires strict alternation of processes in the execution of the critical section. For example, if turn == 0 and P1 is ready to enter its critical section, P1 cannot do so, even though P0 may be in its remainder section. Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 12  b. Algorithm 2 The problem with algorithm 1 is that it does not retain sufficient information about the state of each process; it remembers only which process is allowed to enter its critical section. To remedy this problem, we can replace the variable turn with the following array: Boolean flag ; The elements of the array are initialized to false. If flag [i] is true, this value indicates that Pi is ready to enter the critical section. The structure of process Pi is shown in Figure 10. do { Pi flag[ i ] = P0 flag [ 0 ] = true = Pi - if it is ready it will go else Pj will go Pj flag[ j ] = P1 flag [ 1 ] = true = Pj - if it is ready it will go else Pi will go Flag [ i ] = true ; While (flag [ j ]) ; critical section When P j is not ready P j = false When P i is not ready P i = false T hen P i is ready P i = T rue and T hen P j is ready P j = true and P i is executing P j is executing Flag [ i ] = false ; OR Flag [ j ] = false ; When comes out make P i flag false When comes out make P j flag false So P j can go in So P i can go in reminder section } while (1); Figure 10 The structure of process Pi in algorithm 2 In this algorithm, process Pi first sets flag [i] to be true, signaling that it is ready to enter its critical section. Then, Pi checks to verify that process Pj is not also ready to enter its critical section. If Pj were ready, then Pi would wait until Pj had indicated that it no longer needed to be in the critical section (that is, until flag [j] was false). At this point, Pi would enter the critical section. On exiting the critical section, Pi would set flag [i] to be false, allowing the other process (if it is waiting) to enter its critical section. In this solution, the mutual-exclusion requirement is satisfied. Unfortunately, the progress requirement is not met. This algorithm is crucially dependent on the exact timing of the two processes. The sequence could have been derived in an environment where there are several processors executing concurrently, or where an interrupt occurs immediately after step to is executed, and the CPU is switched from one process to another. c. Algorithm 3 known as Peterson's solution By combining the key ideas of algorithm 1 and algorithm 2, we obtain a correct solution to the critical-section problem known as Peterson's solution, where all three requirements are met. The processes share two variables: boolean flag ; Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 13  int turn; Initially flag = flag = false, and the value of turn is of no importance (it is either 0 or 1). The structure of process Pi is shown in Figure 11. To enter the critical section, process Pi first sets flag [i] to be true and then sets turn to the value j, thereby asserting that if the other process wishes to enter the critical section it can do so. If both processes try to enter at the same time, turn will be set to both i and j at roughly the same time. Only one of these assignments will last; the other will occur, but will be overwritten immediately. The eventual value of turn decides which of the two processes is allowed to enter its critical section first. To prove that given solution is correct. We need: 1. Mutual exclusion is preserved, 2. The progress requirement is satisfied, 3. The bounded-waiting requirement is met. Turn = 1 (here i=0, j=1 ) do { P0 flag [ 0 ] = true = Pi P1 flag [ 1 ] = true = Pj Flag [i] = true ; turn = j ; While (flag [ j ] && turn == j) ; critical section w hen i is executing w hen j is executing Flag [ i ] = false ; Flag [ j ] = false ; When comes out make P i flag false When comes out make P j flag false So P j can go in So P i can go in reminder section } while (1); Figure 11 The structure of process Pi in algorithm 3. To prove property 1, we note that each Pi, enters its critical section only if either flag [j] == false or turn == i. Also note that, if both processes can be executing in their critical sections at the same time, then flag == flag [l] == true. These two observations imply that P0 and P1 could not have successfully executed their while statements at about the same time, since the value of turn can be either 0 or 1, but cannot be both. Hence, one of the processes say Pj must have successfully executed the while statement, whereas Pi had to execute at least one additional statement ("turn == j"). To prove properties 2 and 3, we note that a process Pi can be prevented from entering the critical section only if it is stuck in the while loop with the condition flag [j] == true and turn == j; this loop is the only one. If Pj is not ready to enter Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 14  the critical section, then flag [j] == false and Pi can enter its critical section. If Pj has set flag [j] to true and is also executing in its while statement, then either turn == i or turn == j. If turn == i, then Pi will enter the critical section. If turn == j, then Pj will enter the critical section. However, once Pj exits its critical section, it will reset flag [j] to false, allowing Pi to enter its critical section. If Pj resets flag [j] to true, it must also set turn to i. Thus, since Pi does not change the value of the variable turn while executing the while statement, Pi will enter the critical section (progress) after at most one entry by Pi (bounded waiting). 2. M ultiple-Process Solutions known as bakery algorithm As algorithm 3 solves the critical-section problem for two processes. Now let us develop an algorithm for solving the critical-section problem for n processes. This algorithm is known as the bakery algorithm, and it is based on a scheduling algorithm commonly used in bakeries, ice-cream stores, motor-vehicle registries, and other locations where order must be made out of chaos. This algorithm was developed for a distributed environment. do { choosing [i] = true ; num [i] = max ( num , num ,.......num [n-1] )+1; choosing [i] = false ; for ( j = 0; j < n; j++ ) { While ( choosing [ j ] ) ; While (( num [ j ] != 0 ) && ( num [ j, j ] < num [ i, i ] ) } critical section Number [ i ] = 0; reminder section } while (1); Figure 12 The structure of process Pi in the bakery algorithm. On entering the store, each customer receives a number. The customer with the lowest number is served next. Unfortunately, the bakery algorithm cannot guarantee that two processes (customers) do not receive the same number. In the case of a tie, the process with the lowest name is served first. That is, if Pi and Pj receive the same number and if i < j, then Pi is served first. Since process names are unique and totally ordered, our algorithm is completely deterministic, the common data structures are boolean choosing [n] ; int number [n] ; Initially, these data structures are initialized to false and 0, respectively. For convenience, we define the following notation: (a, b) < (c, d) if a < c or if a == c and b < d. M ax (a0 ,..., an-l ) is a number, k, such that k >= ai for i = 0,..., n - 1. Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 15  The structure of process Pi, used in the bakery algorithm, is shown in Figure 12. To prove that the bakery algorithm is correct, we need first to show that, if Pi is in its critical section and Pk (k != i) has already chosen its number k != 0, then (number [i], i) < (number [k], k). Given this result, it is now simple to show that mutual exclusion is observed. Indeed, consider Pi in its critical section and Pk trying to enter the Pk critical section. When process Pk executes the second while statement for j == i, it finds that Number [i] != 0 (number [i] , i) < (number [k] , k). Thus, it continues looping in the while statement until Pi leaves the Pi critical section. If we wish to show that the progress and bounded-waiting requirements are preserved, and that the algorithm ensures fairness, it is sufficient to observe that the processes enter their critical section on a first-come, first-served basis. Synchronization Hardware We have described software-based solution to the critical-section problem. As mentioned, software-based solutions are not guaranteed to work on modern computer architectures. Instead, we can generally state that any solution to the critical- section problem requires a simple tool-a lock. Race conditions are prevented by requiring that critical regions be protected by locks. That is, a process must acquire a lock before entering a critical section; it releases the lock when it exits the critical section. This is illustrated in Figure 13. Some simple hardware instructions that are available on many systems and showing how they can be used effectively in solving the critical-section problem. Hardware features can make any programming task easier and improve system efficiency. The critical-section problem could be solved simply in a uniprocessor environment if we could prevent interrupts from occurring while a shared variable was being modified. In this manner, we could be sure that the current sequence of instructions would be allowed to execute in order without preemption. No other instructions would be run, so no unexpected modifications could be made to the shared variable. This is often the approach taken by non-preemptive kernels. Unfortunately, this solution is not as feasible in a multiprocessor environment. Disabling interrupts on a multiprocessor can be time consuming, as the message is passed to all the processors. This message passing delays entry into each critical section, and system efficiency decreases. boolean TestAndSet (boolean *target) { boolean rv = *target; *target = TRUE; return rv; } Figure 13. The definition of the Test And Set ( ) instruction. do Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 16  { while (TestAndSet(&lock)) ; critical section lock = FALSE; remainder section } while (TRUE); Figure 14. Mutual-exclusion implementation with Test And Set( ). void Swap(boolean *a, boolean *b) { boolean temp = *a; *a *b; *b = temp; } Figure 15. The definition of the Swap () instruction Many modern computer systems therefore provide special hardware instructions that allow us either to test and modify the content of a word or to swap the contents of two words atomically that is, as one uninterruptible unit. We can use these special instructions to solve the critical-section problem in a relatively simple manner. Rather than discussing one specific instruction for one specific machine, we abstract the main concepts behind these types of instructions by describing the TestAndSet () and Swap() instructions. The TestAndSet( ) instruction can be defined as shown in Figure 6. The important characteristic of this instruction is that it is executed atomically. Thus, if two TestAndSet( ) instructions are executed simultaneously, they will be executed sequentially in some arbitrary order. If the machine supports the TestAndSet( ) instruction, then we can implement mutual exclusion by declaring a Boolean variable lock, initialized to false. The structure of process P; is shown in Figure 7. The Swap( ) instruction, in contrast to the TestAndSet( ) instruction, operates on the contents of two words; it is defined as shown in Figure 8. Like the TestAndSet( ) instruction, it is executed atomically. If the machine supports the Swap() instruction, then mutual exclusion can be provided as follows. A global Boolean variable lock is declared and is initialized to false. In addition, each process has a local Boolean variable key. The structure of process P; is shown in Figure 9. Although these algorithms satisfy the mutual-exclusion requirement, they do not satisfy the bounded-waiting requirement. We present another algorithm using the TestAndSet( ) instruction that satisfies all the critical-section requirements. The common data structures are boolean waiting[n]; boolean lock; These data structures are initialized to false. To prove that the mutual exclusion requirement is met, we note that process P; can enter its critical section only if either waiting [i] == false or key == false. The value of key can become false only Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 17  if the TestAndSet( ) is executed. The first process to execute the TestAndSet( ) will find key== false; all others must wait. The variable waiting [i] can become false only if another process leaves its critical section; only one waiting [i] is set to false, maintaining the mutual-exclusion requirement. do { key = TRUE; while (key == TRUE) Swap(&lock, &key); critical section lock = FALSE; remainder section } while (TRUE); Figure 16. Mutual-exclusion implementation with the Swap() instruction. To prove that the progress requirement is met, we note that the arguments presented for mutual exclusion also apply here, since a process exiting the critical section either sets lock to false or sets waiting[j] to false. Both allow a process that is waiting to enter its critical section to proceed. To prove that the bounded-waiting requirement is met, we note that, when a process leaves its critical section, it scans the array waiting in the cyclic ordering (i+1, i+2,... , n-1, 0,... , i-1). It designates the first process in this ordering that is in the entry section (waiting[j] ==true) as the next one to enter the critical section. Any process waiting to enter its critical section will thus do so within n - 1 turns. Mutex M utexes and Semaphores are kernel resources that provide synchronization services (also known as synchronization primitives). Synchronization is required when multiple processes are executing concurrently, to avoid conflicts between processes using shared resources. Mutex is a specific kind of binary semaphore that is used to provide a locking mechanism. It stands for M utual Exclusion Object. Mutex is mainly used to provide mutual exclusion to a specific portion of the code so that the process can execute and work with a particular section of the code at a particular time. Mutex uses a priority inheritance mechanism to avoid priority inversion issues. The priority inheritance mechanism keeps higher-priority processes in the blocked state for the minimum possible time. However, this cannot avoid the priority inversion problem, but it can reduce its effect up to an extent. Advantages of M utex  No race condition arises, as only one process is in the critical section at a time. Prepared By: Prof. Dheresh Soni – VIT Bhopal University Page 18   Data remains consistent and it helps in maintaining integrity.  It’s a simple locking mechanism that can be obtained by a process before entering into a critical section and released while leaving the critical section. Disadvantages of M utex  If after entering into the critical section, the thread sleeps or gets preempted by a high-priority process, no other thread can enter into the critical section. This can lead to starvation.  When the previous thread leaves the critical section, then only other processes can enter into it, there is no other mechanism to lock or unlock the critical section.  Implementation of mutex can lead to busy waiting that leads to the wastage of the CPU cycle. Using M utex The producer-consumer problem: Consider the standard producer-consumer problem. Assume, we have a buffer of 4096-byte length. A producer thread collects the data and writes it to the buffer. A consumer thread processes the collected data from the buffer. The objective is, both the threads should not run at the same time. Solution- A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by the producer, the consumer needs to wait, and vice versa. At any point in time, only one thread can work with the entire buffer. The concept can be generalized using semaphore. Semaphore The solutions to the critical-section problem presented in above are not easy to generalize to more complex problems. To overcome this difficulty, we can use a synchronization tool called a semaphore. A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait and signal. These operations were originally termed P (for wait; from the Dutch proberen, to test) and V (for signal; from verhogen, to increment). The classical definition of wait in pseudocode is W ait (S) { W hile (S