CU-BCA-SEM-III-System software and operating system-Second draft

CPU whenever it is available next. In case there is a tie, FCFS scheme is employed to break the tie. As an example, consider the following set of processes, with the length of the CPU burst time given in milliseconds: Process: P1 P2 P3 P4 Burst time: 6 8 7 3 Using SJF, the schedule is depicted by the following Gantt chart: P4 P1 P3 P2 Turnaround3time for process P91 = 3 + 6 = 9 16 24 Turnaround time for process P2 = 16 + 8 = 24 Turnaround time for process P3 = 9 + 7 = 16 Turnaround time for process P4 = 3 Average turnaround time = (3 + 9 + 16 + 24)/4 = 13 milliseconds. Wait time for process P1 = 0 + 3 = 3 Wait time for process P2 = 9 + 7 = 16 Wait time for process P3 = 3 + 6 = 9 Wait time for process P4 = 0 Average wait time = (0 + 3 + 9 + 16)/4 = 7 milliseconds. As is obvious, there is an improvement both in average turnaround time and average waiting time as compared to FCFS. Shortest Remaining Time Scheduling (SRT) The Shortest Remaining Time (SRT) scheduling system is a more intelligent version of SPN that allows shorter processes to skip ahead as they appear, instead of only processing the shortest process at the time that CPU time becomes available. This method also falls prey to the halting problem, and is also susceptible to live lock. 151 CU IDOL SELF LEARNING MATERIAL (SLM)

There is no way to determine which process is going to run in the least amount of time unless you allow all processes to run and record their execution times or take input from the user. The individual with the least number of items is allowed to skip to the front of the line regardless of how long everyone else has been waiting. SRT tends to be the most optimal scheduling system if we are hoping to run as many processes as possible in a given time, but requires exact knowledge of how long a process will take. This is usually input by the user or calculated from previous runs of the process. Priority Scheduling (PS) Priority can be defined either internally or externally. Internally defined priorities use some measurable quantities or qualities to compute priority of a process. Examples of internal priorities are: 7. Time limits. Memory requirements. File requirements, for example, number of open files. CPU vs I/O requirements. Externally defined priorities are set by criteria that are external to operating system such as: 8. The importance of process. Type or amount of funds being paid for computer use. The department sponsoring the work. Politics. Priority scheduling can be either preemptive or non-preemptive: 9. A preemptive priority algorithm will preemptive the CPU if the priority of the newly arrival process is higher than the priority of the currently running process. A non-preemptive priority algorithm will simply put the new process at the head of the ready queue. A major problem with priority scheduling is indefinite blocking or starvation. A solution to the problem of indefinite blockage of the low-priority process is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long period of time. 152 CU IDOL SELF LEARNING MATERIAL (SLM)

It is a more general schedule algorithm of which both FCFS and SJF is priority scheduling. This algorithm associates a priority with each process on some pre-determined basis. The CPU is allocated to the process having highest priority. If the priorities associated to processes are equal, then the algorithm reduces to FCFS. SJF is a special case of priority scheduling with priorities associated according to the number of CPU burst required by the processes, the process with the smallest CPU burst requirement having highest priority. Round Robin Scheduling (RR) One of the oldest, simplest, fairest and most widely used algorithms is round robin (RR). In the round robin scheduling, processes are dispatched in a FIFO manner but are given a limited amount of CPU time called a time-slice or a quantum. If a process does not complete before its CPU-time expires, the CPU is pre-empted and given to the next process waiting in a queue. The pre-empted process is then placed at the back of the ready list. Round Robin Scheduling is preemptive (at the end of time-slice) therefore it is effective in time-sharing environments in which the system needs to guarantee reasonable response times for interactive users. The only interesting issue with round robin scheme is the length of the quantum. Setting the quantum too short causes too many context switches and lower the CPU efficiency. On the other hand, setting the quantum too long may cause poor response time and approximates FCFS. In any event, the average waiting time under round robin scheduling is often quite long. This algorithm is based on the principle that CPU must be shared between each ready process. For this purpose, CPU time is divided into time-quantum or time-slice. The ready processes are queued up in a circular queue. CPU is allocated to a process at the head of the queue. A context switching takes place whenever either the running process exhausts its allocated time- quantum or finishes its execution. At this time the running process is queued up at the tail of the queue if it has not yet finished execution. The next process at the head of the ready queue is allocated the CPU next. 153 CU IDOL SELF LEARNING MATERIAL (SLM)

The average wait time in the RR scheduling may be often quite long. Consider the following set of processes that arrive at time 0, with the required CPU-time in milliseconds given as under: Queue: 1st 2nd 3rd Process: P1 P2 P3 Burst time: 24 3 3 Assuming that the CPU time-slice is 4 milliseconds, the scheduling takes place as explained next. The first process P1 is allocated the CPU. It runs for 4 milliseconds when a context switching takes place and P1 is placed in the end of the queue with required CPU burst-time (24 - 4 =20) milliseconds. The schedule is shown as below: P1 P2 P3 P1 P1 P1 P1 P1 04 7 26 Process P2, however, completes its execution before the time-slice expires and then P3 is allocated the CPU. Turnaround time for process P1 = 30 Turnaround time for process P2 = 7 Turnaround time for process P3 = 10 Average turnaround time = (30 + 7 + 10)/3 = 15.6 milliseconds. Wait time for process P1 = 0 + 10 = 10 Wait time for process P2 = 4 Wait time for process P3 = 7 Average wait time = (10 + 4 + 7)/3 = 7 milliseconds. 7.3.3 Multi-level Feedback Queues (MLF) Multilevel feedback queue is a scheduling algorithm. It allows a process to move between queues. It uses many ready queues and associates a different priority with each queue. 154 CU IDOL SELF LEARNING MATERIAL (SLM)

The Algorithm chooses to process with highest priority from the occupied queue and run that process either pre-emptively or unperceptively. If the process uses too much CPU time it will moved to a lower-priority queue. Similarly, a process that wait too long in the lower-priority queue may be moved to a higher-priority queue may be moved to a highest-priority queue. Note that this form of aging prevents starvation. Multilevel feedback scheduling is intended to meet the following design requirements for multimode systems: 1. Give preference to short jobs. 2. Give preference to I/O bound processes. 3. Quickly establish the nature of a process and schedule the process accordingly. Multiple FIFO queues are used and the operation is as follows: 1. A new process is positioned at the end of the top-level FIFO queue. 2. At some stage the process reaches the head of the queue and is assigned the CPU. 3. If the process is completed it leaves the system. If the process voluntarily relinquishes control, it leaves the queuing network, and when the process becomes ready again it enters the system on the same queue level. If the process uses all the quantum time, it is pre-empted and positioned at the end of the next lower-level queue. This will continue until the process completes or it reaches the base level queue. At the base level queue, the processes circulate in round robin fashion until they complete and leave the system. Optionally, if a process blocks for I/O, it is ‘promoted’ one level, and placed at the end of the next-highest queue. This allows I/O bound processes to be favoured by the scheduler and allows processes to ‘escape’ the base level queue. In the multilevel feedback queue, a process is given just one chance to complete at a given queue level before it is forced down to a lower-level queue. 155 CU IDOL SELF LEARNING MATERIAL (SLM)

Multilevel Queue Scheduling Another class of scheduling algorithm has been created for situations in which processes are easily classified into different groups. For example, a common division is made between foreground (interactive) processes and background (batch) processes. These two types of processes have different response-time requirements, and so might have different scheduling needs. In addition, foreground processes may have priority (externally defined) over background processes. A multilevel queue-scheduling algorithm partitions the ready queue into several separate queues. The processes are permanently assigned to one queue, generally based on some property of the process, such as memory size, process priority or process type. Each queue has its own scheduling algorithm. For example, separate queues might be used for foreground and background processes. The foreground queue might be scheduled by an RR algorithm. Let us look at an example of a multilevel queue scheduling algorithm with five queues: 1. System processes queue 2. Interactive processes queue 3. Interactive editing processes queue 4. Batch processes queue 5. Student processes queue Each queue has absolute priority over lower-priority queues. No process in the batch queue, for example, could run unless the queues for system processes, interactive processes, and interactive editing processes were all empty. If an interactive editing process entered the ready queue while a batch process was running, the batch process would be pre-empted. Another possibility is to time slice between the queues. Each queue gets a certain portion of the CPU time, which it can then schedule among the various processes in its queue. For instance, in the foreground-background queue, the foreground queue can be given 80% of the CPU time for RR scheduling among its processes, whereas the background queue receives 20% of the CPU to give to its processes in an FCFS manner. Multilevel Feedback Queue Scheduling 156 CU IDOL SELF LEARNING MATERIAL (SLM)

Normally, in a multilevel queue-scheduling algorithm, processes are permanently assigned to a queue on entry to the system. Processes do not move between queues. If there are separate queues for foreground and background processes, for example, processes do not move from one queue to the other, since processes do not change their foreground or background nature. This setup has the advantage of low scheduling overhead, but is inflexible. Multilevel feedback queue scheduling, however, allows a process to move between queues. The idea is to separate processes with different CPU-burst characteristics. If a process uses Quantum = 8 Quantum = 16 FCFS Figure 7.3: Multilevel Feedback Queue Scheduling In addition, there must be scheduling between the queues, which is commonly implemented as a fixed-priority preemptive scheduling. For example, the foreground queue may have absolute priority over the background queue. If a process uses too much CPU time, it will be moved to a lower-priority queue. This scheme leaves l/O-bound and interactive processes in the higher-priority queues. Similarly, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation (no allocation ever). For example, consider a multilevel feedback queue scheduler with three queues, numbered from 0 to 2. The scheduler first executes all processes in queue 0. Only when queue 0 is empty, will it execute processes in queue 1. Similarly, processes in queue 2 will only be executed if queues 0 and 1 are empty. A process that arrives for queue 1 will pre-empt a process in queue 2. A process in queue 1 will, in turn, be pre-empted by a process arriving for queue 0. A process entering the ready queue is put in queue 0. A process in queue 0 is given a time quantum of 8 milliseconds. If it does not finish within this time, it is moved to the tail of queue 1. If queue 0 is empty, the process at the head of queue 1 is given a quantum of 16 157 CU IDOL SELF LEARNING MATERIAL (SLM)

milliseconds. If it does not complete, it is pre-empted and is put into queue 2. Processes in queue 2 are run on an FCFS basis, only when queues 0 and 1 are empty. 7.4 MULTIPLE PROCESSOR SCHEDULING Our discussion so far has focused on the problems of scheduling the CPU in a system with a single processor. If multiple CPUs are available, the scheduling problem is correspondingly more complex. Many possibilities have been tried, and, as we saw with single-processor PU scheduling, there is no one best solution. In the following, we discuss briefly some of the issues concerning multiprocessor scheduling (a complete coverage is beyond the scope of this text.) We concentrate on systems where the processors are identical (homogeneous) in terms of their functionality. Any available processor can then be used to run any processes in the queue; only programs compiled for a given processor's instruction set could be run on that processor. Even within homogeneous multiprocessor, there are sometimes limitations on scheduling. Consider a system with an I/O device attached to a private bus of one processor. Processes wishing to use that device must be scheduled to run on that processor; otherwise, the device would not be available. If several identical processors are available, then load sharing can occur. It would be possible to provide a separate queue for each processor. In this case, however, one processor could be idle, with an empty queue, while another processor was very busy. To prevent this situation, we use a common ready queue. All processes go into one queue and are scheduled onto any available processor. In such a scheme, one of two scheduling approaches may be used. In one approach, each processor is self-scheduling. Each processor examines the common ready queue and selects a process to execute. We must ensure that two processors do not choose the same process, and that processes are not lost from the queue. The other approach avoids this problem by appointing one processor as scheduler for the other processors, thus creating master-slave structure. Some systems carry this structure one step further, by having all scheduling decisions, I/O processing, and other system activities handled by one single processor – the master server. The other processors only execute user code. This asymmetric multiprocessing is far simpler 158 CU IDOL SELF LEARNING MATERIAL (SLM)

than symmetric multiprocessing, because only one processor accesses the system data structures, alleviating the need for data sharing. 7.5 SUMMARY  Process scheduling is an essential part of a Multiprogramming operating systems. Such operating systems allow more than one process to be loaded into the executable memory at a time and the loaded process shares the CPU using time multiplexing.CPU scheduling is the basics of multiprogramming.  Schedulers are special system software which handle process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run.  A context switch is the mechanism to store and restore the state or context of a CPU in Process Control block so that a process execution can be resumed from the same point at a later time. Using this technique, a context switcher enables multiple processes to share a single CPU. Context switching is an essential part of a multitasking operating system features.  The main task of CPU scheduling is to make sure that whenever the CPU remains idle, the OS at least select one of the processes available in the ready queue for execution. The selection process will be carried out by the CPU scheduler. It selects one of the processes in memory that are ready for execution. 7.6 KEYWORDS  Processor: The processor, also known as the CPU, provides the instructions and processing power the computer needs to do its work. The more powerful and updated your processor, the faster your computer can complete its tasks.  Schedulers: Special system software which handle process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run.  Queue: An input queue is a collection of processes in storage that are waiting to be brought into memory to run a program. Input queues are mainly used in Operating System Scheduling which is a technique for distributing resources among processes.  CPU utilization: CPU must be as busy as possible in performing different tasks. CPU utilization is more important in real-time system and multi-programmed systems. 159 CU IDOL SELF LEARNING MATERIAL (SLM)

 Throughput: The number of processes executed in a specified time period is called throughput. The throughput increases for short processes. It decreases if the size of processes is huge. 7.7 LEARNING ACTIVITY 1. Original versions of Apple’s mobile iOS operating system provided no means of concurrent processing. Discuss three major complications that concurrent processing adds to an operating system. ___________________________________________________________________________ ____________________________________________________________________ 7.8 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What resources are used when a thread created? How do they differ from those when a process is created? 2. What are the different process states? What is the state of the processor, when a process is waiting for some event to occur? 3. Write a brief description on process state transition. 4. What is PCB? What is the function of PCB? 5. Explain context switching. Long Questions 1. Explain the CPU Scheduling criteria. 2. Do you think a process migrates between the various scheduling queues throughout its lifetime? 3. What is the difference between response time and waiting time? 4. Describe how processes help achieve multiprogramming. 5. Compare between non-preemptive scheduling and preemptive scheduling. 160 CU IDOL SELF LEARNING MATERIAL (SLM)

B. Multiple Choice Questions 1. Which of the following scheduling algorithms is non-preemptive? a. Round robin b. First in first out c. Multilevel queue scheduling d. Multilevel Queue Scheduling with Feedback 2. The most optimal scheduling algorithm is: a. Round robin b. First in first out c. Multilevel queue scheduling d. None of these 3. Which scheduling algorithm allocates the CPU first to the process that requests the CPU first? a. first-come, first-served scheduling b. shortest job scheduling c. priority scheduling d. None of these 4. Scheduling is done so as to ____________ 161 a. increase CPU utilization b. decrease CPU utilization c. keep the CPU more idle CU IDOL SELF LEARNING MATERIAL (SLM)

d. None of these 5. Which of the following is not an optimization criterion in the design of a CPU scheduling algorithm? a. Minimum CPU utilization b. Maximum throughput c. Minimum turnaround time d. Minimum waiting time 6. Time quantum is defined in a. shortest job scheduling algorithm b. round robin scheduling algorithm c. priority scheduling algorithm d. multilevel queue scheduling algorithm 7. Which of the following statements is not true for Multi-Level Feedback Queue processor scheduling algorithm? a. Queues have different priorities b. Each queue may have different scheduling algorithm c. Processes are permanently assigned to a queue d. This algorithm can be configured to match a specific system under design 8. A process is selected from the ______ queue by the ________ scheduler, to be executed. a. blocked, short term b. wait, long term 162 CU IDOL SELF LEARNING MATERIAL (SLM)

c. ready, short term d. ready, long term 9. In a multi-user operating system, 30 requests are made to use a particular resource per hour, on an average. The probability that no requests are made in 40 minutes, when arrival pattern is a poisson distribution, is _________. a. e-15 b. 1 - e-15 c. 1 - e-20 d. e-20 10. CPU scheduling is the basis of ___________ a. multiprocessor systems b. multiprogramming operating systems c. larger memory sized systems d. None of these Answers 1 a,2 d, 3 b,4 a, 5 a,6 b, 7 c, 8 c, 9 a, 10 b 7.9 REFERENCES  A. Silberschatz P.B. Galvin, Gange (2002). Operating System Concepts, 6th Ed., Addison Wesley Publishing Co., Boston.  H.M. Deitel (1990). An Introduction to Operating Systems, Addison Wesley Publishing Co., Boston.  D.M. Dhamdhare (2002). Operating System. Tata McGraw Hill, New Delhi. 163 CU IDOL SELF LEARNING MATERIAL (SLM)

 A.S. Tanenbaum (2000). Operating Systems: Design and Implementation, Prentice Hall of India, New Delhi.  Nutt (2005). Operating Systems, 3rd Edition, Pearson Education, Delhi. 164 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 8: SCHEDULING ALGORITHMS 165 Structure 8.0 Learning Objectives 8.1 Introduction 8.2 Pre-emptive and Non-Pre-emptive 8.3 First-Come-First-Serve 8.4 Shortest Job First 8.5 Round Robin 8.6 Multiprocessor scheduling 8.7 Performance evaluation of the scheduling 8.8 Summary 8.9 Keywords 8.10 Learning Activity 8.11 Unit End Questions 8.12 References 8.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Explain scheduling algorithms  Define preemptive scheduling  Perform non-preemptive scheduling  Exercise various scheduling algorithms  Outline multiple processor scheduling CU IDOL SELF LEARNING MATERIAL (SLM)

8.1 INTRODUCTION A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms. There are six popular process scheduling algorithms which we are going to discuss in this chapter −  First-Come, First-Served (FCFS) Scheduling  Shortest-Job-Next (SJN) Scheduling  Priority Scheduling  Shortest Remaining Time  Round Robin(RR) Scheduling  Multiple-Level Queues Scheduling These algorithms are either non-preemptive or preemptive. 8.2 PREEMPTIVE AND NON-PREEMPTIVE Preemptive Scheduling is a CPU scheduling technique that works by dividing time slots of CPU to a given process. The time slot given might be able to complete the whole process or might not be able to it. When the burst time of the process is greater than CPU cycle, it is placed back into the ready queue and will execute in the next chance. This scheduling is used when the process switch to ready state. Algorithms that are backed by preemptive Scheduling are round-robin (RR), priority, SRTF (shortest remaining time first). Non-preemptive Scheduling is a CPU scheduling technique the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state. No process is interrupted until it is completed, and after that processor switches to another process. Algorithms that are based on non-preemptive Scheduling are non-preemptive priority, and shortest Job first. 166 CU IDOL SELF LEARNING MATERIAL (SLM)

Preemptive Vs Non-Preemptive Scheduling Preemptive Scheduling Non-Preemptive Scheduling Resources are allocated according to the Resources are used and then held by the cycles for a limited time. process until it gets terminated. The process can be interrupted, even before The process is not interrupted until its life the completion. cycle is complete. Starvation may be caused, due to the Starvation can occur when a process with insertion of priority process in the queue. large burst time occupies the system. Maintaining queue and remaining time No such overheads are required needs storage overhead. 8.3 FIRST-COME-FIRST-SERVE  Jobs are executed on first come, first serve basis.  It is a non-pre-emptive, pre-emptive scheduling algorithm.  Easy to understand and implement.  Its implementation is based on FIFO queue.  Poor in performance as average wait time is high. 167 CU IDOL SELF LEARNING MATERIAL (SLM)

Wait time of each process is as follows − Process Wait Time: Service Time - Arrival Time P0 0 - 0 = 0 P1 5 - 1 = 4 P2 8 - 2 = 6 P3 16 - 3 = 13 Average Wait Time: (0+4+6+13) / 4 = 5.75 8.4 SHORTEST JOB FIRST  This is also known as shortest job first, or SJF  This is a non-pre-emptive, pre-emptive scheduling algorithm.  Best approach to minimize waiting time.  Easy to implement in Batch systems where required CPU time is known in advance.  Impossible to implement in interactive systems where required CPU time is not known.  The processer should know in advance how much time process will take. Given: Table of processes, and their Arrival time, Execution time Process Arrival Time Execution Time Service Time P0 0 5 0 P1 1 3 5 P2 2 8 14 168 CU IDOL SELF LEARNING MATERIAL (SLM)

P3 3 6 8 Waiting time of each process is as follows – Process Waiting Time P0 0 - 0 = 0 P1 5 - 1 = 4 P2 14 - 2 = 12 P3 8 - 3 = 5 Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25 Shortest Remaining Time  Shortest remaining time (SRT) is the pre-emptive version of the SJN algorithm.  The processor is allocated to the job closest to completion but it can be pre-empted by a newer ready job with shorter time to completion.  Impossible to implement in interactive systems where required CPU time is not known.  It is often used in batch environments where short jobs need to give preference. 8.5 ROUND ROBIN  Round Robin is the pre-emptive process scheduling algorithm.  Each process is provided a fix time to execute, it is called a quantum.  Once a process is executed for a given time period, it is pre-empted and other process executes for a given time period.  Context switching is used to save states of pre-empted processes. 169 CU IDOL SELF LEARNING MATERIAL (SLM)

Wait time of each process is as follows − Process Wait Time: Service Time - Arrival Time P0 (0 - 0) + (12 - 3) = 9 P1 (3 - 1) = 2 P2 (6 - 2) + (14 - 9) + (20 - 17) = 12 P3 (9 - 3) + (17 - 12) = 11 Average Wait Time: (9+2+12+11) / 4 = 8.5 Multiple-Level Queues Scheduling Multiple-level queues are not an independent scheduling algorithm. They make use of other existing algorithms to group and schedule jobs with common characteristics.  Multiple queues are maintained for processes with common characteristics.  Each queue can have its own scheduling algorithms.  Priorities are assigned to each queue. For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs in another queue. The Process Scheduler then alternately selects jobs from each queue and assigns them to the CPU based on the algorithm assigned to the queue. 170 CU IDOL SELF LEARNING MATERIAL (SLM)

8.6 MULTIPROCESSOR SCHEDULING In multiple-processor scheduling multiple CPUs are available and hence Load Sharing becomes possible. However multiple processor scheduling is more complex as compared to single processor scheduling. In multiple processor scheduling there are cases when the processors are identical i.e., HOMOGENEOUS, in terms of their functionality, we can use any processor available to run any process in the queue. Approaches to Multiple-Processor Scheduling One approach is when all the scheduling decisions and I/O processing are handled by a single processor which is called the Master Server and the other processors executes only the user code. This is simple and reduces the need of data sharing. This entire scenario is called Asymmetric Multiprocessing. A second approach uses Symmetric Multiprocessing where each processor is self-scheduling. All processes may be in a common ready queue or each processor may have its own private queue for ready processes. The scheduling proceeds further by having the scheduler for each processor examine the ready queue and select a process to execute. Processor Affinity Processor Affinity means a process has an affinity for the processor on which it is currently running. When a process runs on a specific processor there are certain effects on the cache memory. The data most recently accessed by the process populate the cache for the processor and as a result successive memory access by the process is often satisfied in the cache memory. Now if the process migrates to another processor, the contents of the cache memory must be invalidated for the first processor and the cache for the second processor must be repopulated. Because of the high cost of invalidating and repopulating caches, most of the SMP (symmetric multiprocessing) systems try to avoid migration of processes from one processor to another and try to keep a process running on the same processor. There are two types of processor affinity: 1. Soft Affinity – When an operating system has a policy of attempting to keep a process running on the same processor but not guaranteeing it will do so, this situation is called soft affinity. 171 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Hard Affinity – Hard Affinity allows a process to specify a subset of processors on which it may run. Some systems such as Linux implements soft affinity but also provide some system calls like sched_setaffinity () that supports hard affinity. Load Balancing Load Balancing is the phenomena which keeps the workload evenly distributed across all processors in an SMP system. Load balancing is necessary only on systems where each processor has its own private queue of process which is eligible to execute. Load balancing is unnecessary because once a processor becomes idle it immediately extracts a runnable process from the common run queue. On SMP (symmetric multiprocessing), it is important to keep the workload balanced among all processors to fully utilize the benefits of having more than one processor else one or more processor will sit idle while other processors have high workloads along with lists of processors awaiting the CPU. There are two general approaches to load balancing: 1. Push Migration – In push migration a task routinely checks the load on each processor and if it finds an imbalance then it evenly distributes load on each processor by moving the processes from overloaded to idle or less busy processors. 2. Pull Migration – Pull Migration occurs when an idle processor pulls a waiting task from a busy processor for its execution. Multicore Processors In multicore processors multiple processor cores are places on the same physical chip. Each core has a register set to maintain its architectural state and thus appears to the operating system as a separate physical processor. SMP systems that use multicore processors are faster and consume less power than systems in which each processor has its own physical chip. However multicore processors may complicate the scheduling problems. When processor accesses memory then it spends a significant amount of time waiting for the data to become available. This situation is called memory stall. It occurs for various reasons such as cache miss, which is accessing the data that is not in the cache memory. In such cases the processor can spend up to fifty percent of its time waiting for data to become available from the memory. To solve this problem recent hardware designs have implemented multithreaded processor cores in which two or more hardware threads are assigned to each core. Therefore, if one thread stalls while waiting for the memory, core can switch to another thread. 172 CU IDOL SELF LEARNING MATERIAL (SLM)

There are two ways to multithread a processor: 1. Coarse-Grained Multithreading – In coarse grained multithreading a thread executes on a processor until a long latency event such as a memory stall occurs, because of the delay caused by the long latency event, the processor must switch to another thread to begin execution. The cost of switching between threads is high as the instruction pipeline must be terminated before the other thread can begin execution on the processor core. Once this new thread begins execution it begins filling the pipeline with its instructions. 2. Fine-Grained Multithreading – This multithreading switch between threads at a much finer level mainly at the boundary of an instruction cycle. The architectural design of fine-grained systems include logic for thread switching and as a result the cost of switching between threads is small. Virtualization and Threading In this type of multiple-processor scheduling even a single CPU system acts like a multiple- processor system. In a system with Virtualization, the virtualization presents one or more virtual CPU to each of virtual machines running on the system and then schedules the use of physical CPU among the virtual machines. Most virtualized environments have one host operating system and many guest operating systems. The host operating system creates and manages the virtual machines. Each virtual machine has a guest operating system installed and applications run within that guest. Each guest operating system may be assigned for specific use cases, applications or users including time sharing or even real-time operation. Any guest operating-system scheduling algorithm that assumes a certain amount of progress in a given amount of time will be negatively impacted by the virtualization. A time-sharing operating system tries to allot 100 milliseconds to each time slice to give users a reasonable response time. A given 100 millisecond time slices may take much more than 100 milliseconds of virtual CPU time. Depending on how busy the system is, the time slice may take a second or more which results in a very poor response time for users logged into that virtual machine. The net effect of such scheduling layering is that individual virtualized operating systems receive only a portion of the available CPU cycles, even though they believe they are receiving all cycles and that they are scheduling all of those cycles. Commonly, the time-of- 173 CU IDOL SELF LEARNING MATERIAL (SLM)

day clocks in virtual machines are incorrect because timers take no longer to trigger than they would on dedicated CPU’s. 8.7 PERFORMANCE EVALUATION OF THE SCHEDULING The first thing we need to decide is how we will evaluate the algorithms. To do this we need to decide on the relative importance of the factors we listed above (Fairness, Efficiency, Response Times, Turnaround and Throughput). Only once we have decided on our evaluation method can we carry out the evaluation. Deterministic Modelling This evaluation method takes a predetermined workload and evaluates each algorithm using that workload. Assume we are presented with the following processes, which all arrive at time zero. Process Burst Time P1 9 P2 33 P3 2 P4 5 P5 14 Which of the following algorithms will perform best on this workload? First Come First Served (FCFS), Non-Pre-emptive Shortest Job First (SJF) and Round Robin (RR). Assume a quantum of 8 milliseconds. For FCFS the process would be executed in the following order, with the following wait times Process Burst Time Wait Time P1 9 0 174 CU IDOL SELF LEARNING MATERIAL (SLM)

P2 33 9 P3 2 42 P4 5 44 P5 14 49 Therefore, the average waiting time is ((0 + 9 + 42 + 44 + 49) / 5) = 28.80 milliseconds For SJF (non-pre-empted) the processes would run as follows Process Burst Time Wait Time P3 2 0 P4 5 2 P1 9 7 P5 14 16 P2 33 30 The average waiting time is ((0 + 2 + 7 + 16 + 30) / 5) = 11 milliseconds For RR the jobs would execute as follows Process CPU Time P1 8 P2 8 P3 2 175 CU IDOL SELF LEARNING MATERIAL (SLM)

P4 5 P5 8 P1 1 P2 8 P5 6 P2 8 P2 8 P2 1 The waiting time for each process is as follows P1: 0 + 23 = 23 P2: 8 + 16 + 6 = 30 P3: 16 P4: 18 P5: 23 + 9 = 32 Therefore, the average waiting time is ((23 + 30 + 16 + 18 + 32) / 5) = 23.80 The advantage of deterministic modelling is that it is exact and fast to compute. The disadvantage is that it is only applicable to the workload that you use to test. As an example, use the above workload but assume P1 only has a burst time of 8 milliseconds. What does this do to the average waiting time? Of course, the workload might be typical and scale up but generally deterministic modelling is too specific and requires too much knowledge about the workload. Queuing Models Another method of evaluating scheduling algorithms is to use queuing theory. Using data from real processes we can arrive at a probability distribution for the length of a burst time 176 CU IDOL SELF LEARNING MATERIAL (SLM)

and the I/O times for a process. We can now generate these times with a certain distribution. We can also generate arrival times for processes. If we define a queue for the CPU and a queue for each I/O device we can test the various scheduling algorithms using queuing theory. Knowing the arrival rates and the service rates we can calculate various figures such as average queue length, average wait time, CPU utilization etc. One useful formula is Little's Formula. n = λw Where  n is the average queue length  λ is the average arrival rate for new processes (e.g., five a second)  w is the average waiting time in the queue Knowing two of these values we can, obviously, calculate the third. For example, if we know that eight processes arrive every second and there are normally sixteen processes in the queue, we can compute that the average waiting time per process is two seconds. The main disadvantage of using queuing models is that it is not always easy to define realistic distribution times and we have to make assumptions. This results in the model only being an approximation of what actually happens. Simulations Rather than using queuing models we simulate a computer. A Variable, representing a clock is incremented. At each increment the state of the simulation is updated. Statistics are gathered at each clock tick so that the system performance can be analysed. The data to drive the simulation can be generated in the same way as the queuing model, although this leads to similar problems. Alternatively, we can use trace data. This is data collected from real processes on real machines and is fed into the simulation. This can often provide good results and good comparisons over a range of scheduling algorithms. However, simulations can take a long time to run, can take a long time to implement and the trace data may be difficult to collect and require large amounts of storage. 177 CU IDOL SELF LEARNING MATERIAL (SLM)

Implementation The best way to compare algorithms is to implement them on real machines. This will give the best results but does have a number of disadvantages.  It is expensive as the algorithm has to be written and then implemented on real hardware.  If typical workloads are to be monitored, the scheduling algorithm must be used in a live situation. Users may not be happy with an environment that is constantly changing.  If we find a scheduling algorithm that performs well there is no guarantee that this state will continue if the workload or environment changes. 8.8 SUMMARY  Preemptive Scheduling is a CPU scheduling technique that works by dividing time slots of CPU to a given process. Non-preemptive Scheduling is a CPU scheduling technique the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state.  First come first serve (FCFS) scheduling algorithm simply schedules the jobs according to their arrival time. The job which comes first in the ready queue will get the CPU first. The lesser the arrival time of the job, the sooner will the job get the CPU. FCFS scheduling may cause the problem of starvation if the burst time of the first process is the longest among all the jobs.  In SJF scheduling, the process with the lowest burst time, among the list of available processes in the ready queue, is going to be scheduled next. However, it is very difficult to predict the burst time needed for a process hence this algorithm is very difficult to implement in the system.  Round Robin scheduling algorithm is one of the most popular scheduling algorithms which can actually be implemented in most of the operating systems. This is the preemptive version of first come first serve scheduling. The Algorithm focuses on Time Sharing. In this algorithm, every process gets executed in a cyclic way. A certain time slice is defined in the system which is called time quantum. Each process present in the ready queue is assigned the CPU for that time quantum, if the execution of the process is completed during that time, then the process will terminate else the 178 CU IDOL SELF LEARNING MATERIAL (SLM)

process will go back to the ready queue and waits for the next turn to complete the execution.  Round Robin scheduling algorithm is one of the most popular scheduling algorithms which can actually be implemented in most of the operating systems. This is the preemptive version of first come first serve scheduling. The Algorithm focuses on Time Sharing. In this algorithm, every process gets executed in a cyclic way. A certain time slice is defined in the system which is called time quantum. Each process present in the ready queue is assigned the CPU for that time quantum, if the execution of the process is completed during that time, then the process will terminate else the process will go back to the ready queue and waits for the next turn to complete the execution. 8.9 KEYWORDS  Non-preemptive: Algorithms are designed so that once a process enters the running state, it cannot be pre-empted until it completes its allotted time.  Preemptive: Scheduling is based on priority where a scheduler may pre-empt a low priority running process anytime when a high priority process enters into a ready state.  Quantum: Each process is provided a fix time to execute, it is called a quantum.  Response Time: A scheduler should minimize the response time for interactive user.  Turnaround: A scheduler should minimize the time for which users must wait for an output.  Throughput: A scheduler should maximize the number of jobs processed per unit time. 8.10 LEARNING ACTIVITY 1. A system with two dual-core processors has four processors available for scheduling. A CPU-intensive application is running on this system. All input is performed at program start-up, when a single file must be opened. Similarly, all output is performed just before the program terminates, when the program results must be written to a single file. Between start up and termination, the program is entirely CPU bound. Your task is to improve the performance of this application by multithreading it. The application runs on 179 CU IDOL SELF LEARNING MATERIAL (SLM)

a system that uses the one-to-one threading model (each user thread maps to a kernel thread).  How many threads will you create to perform the input and output? Explain.  How many threads will you create for the CPU-intensive portion of the application? Explain. ___________________________________________________________________________ ____________________________________________________________________ 8.11 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Differentiate between Pre-emptive and Non-Pre-emptive scheduling algorithms. 2. Define CPU Scheduling. 3. What are the various scheduling criteria for CPU scheduling? 4. What are the 3 different types of scheduling queues? 5. Define schedulers? Long Questions 1. Write about the various CPU scheduling algorithms. 2. Distinguish among short-term, medium-term and long-term scheduling with suitable example. 3. Consider the following five processes, with the length of the CPU burst time given in milliseconds. Process Burst time P1 10 P2 29 P3 3 P4 7 P5 12 Consider the First come First serve (FCFS), Non-Preemptive Shortest Job First (SJF), Round Robin (RR) (quantum=10ms) scheduling algorithms. Illustrate the scheduling using Gantt chart. 4. Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes: RR, Multilevel Feedback Queues. 5. Write notes about multiple-processor scheduling and real-time scheduling. 180 CU IDOL SELF LEARNING MATERIAL (SLM)

B. Multiple Choice Questions 1. Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2-, 4- and 8-time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turnaround time is: a. 13 units b. 14 units c. 15 units d. 16 units 2. Consider three CPU-intensive processes, which require 10-, 20- and 30-time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end. a. 1 b. 2 c. 3 d. 5 3. Which of the following process scheduling algorithm may lead to starvation? a. FIFO b. Round robin c. Shortest Job First d. None of these 181 CU IDOL SELF LEARNING MATERIAL (SLM)

4. Consider the following table of arrival time and burst time for three processes P0, P1 and P2. Process Arrival time Burst Time P0 0 ms 9 ms P1 1 ms 4 ms P2 2 ms 9 ms The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes? a. 5.0 ms b. 4.33 ms c. 6.33 ms d. 7.33 ms 5. Which of the following statements are true? I. Shortest remaining time first scheduling may cause starvation II. Preemptive scheduling may cause starvation III. Round robin is better than FCFS in terms of response time a. I only b. I and III only c. II and III only d. I, II and III 182 CU IDOL SELF LEARNING MATERIAL (SLM)

6. Consider a set of n tasks with known runtimes r1, r2 ... rn to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput? a. Round robin b. SJF c. Highest-Response-Ratio-Next d. First-Come-First-Served 7. An operating system uses shortest remaining time first scheduling algorithm for pre- emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): Process Arrival Time Burst Time P1 0 12 P2 2 4 P3 3 6 P4 8 5 The average waiting time (in milliseconds) of the processes is _________. a. 4.5 b. 5.5 c. 6.5 d. 4.8 183 CU IDOL SELF LEARNING MATERIAL (SLM)

8. Consider a uniprocessor system executing three tasks T1, T2 and T3, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period and the available tasks are scheduled in order of priority, with the highest priority task scheduled first. Each instance of T1, T2 and T3 requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1st milliseconds and task preemptions are allowed, the first instance of T3 completes its execution at the end of ______________ milliseconds. a. 5 b. 10 c. 12 d. 15 9. The maximum number of processes that can be in Ready state for a computer system with n CPUs is a. n b. n2 c. 2n d. Independent on n 10. Which of the following is FALSE about SJF (Shortest Job First Scheduling)? 184 S1: It causes minimum average waiting time S2: It can cause starvation a. Only S1 b. Only S2 c. Both S1 and S2 CU IDOL SELF LEARNING MATERIAL (SLM)

d. Neither S1 nor S2 Answers 1 a, 2 b, 3 c, 4 a, 5 d, 6 b, 7 b, 8 c, 9 d, 10 d 8.12 REFERENCES  A. Silberschatz P.B. Galvin, Gange (2002). Operating System Concepts, 6th Ed., Addison Wesley Publishing Co., Boston.  H.M. Deitel (1990). An Introduction to Operating Systems, Addison Wesley Publishing Co., Boston.  D.M. Dhamdhare (2002). Operating System. Tata McGraw Hill, New Delhi.  A.S. Tanenbaum (2000). Operating Systems: Design and Implementation, Prentice Hall of India, New Delhi.  Nutt (2005). Operating Systems, 3rd Edition, Pearson Education, Delhi. 185 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 9: PROCESS SYNCHRONIZATION 186 Structure 9.0 Learning Objectives 9.1 Introduction 9.2 Concepts of Process Synchronization 9.3 Critical Section Problems 9.3.1 Mutual Exclusion Principle 9.3.2 Peterson’s Algorithm 9.3.3 Lamport’s Bakery Algorithm 9.4 Synchronization Hardware 9.4.1 Test-and-Set 9.4.2 Compare-and-Swap 9.5 Semaphores 9.6 Classical Problems of Synchronization 9.6.1 The Producer–Consumer Problem 9.6.2 The Readers–Writers Problem 9.6.3 The Dining Philosophers Problem 9.7 Summary 9.8 Keywords 9.9 Learning Activity 9.10 Unit End Questions 9.11 References 9.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Describe process synchronization CU IDOL SELF LEARNING MATERIAL (SLM)

 Analyze critical section  Define synchronization hardware  Discuss the use of semaphores  Outline various Classical Problems of Synchronization 9.1 INTRODUCTION In addition to process scheduling, another important responsibility of the operating system is process synchronization. When concurrently executing processes communicate among themselves or use shared resources, they can obviously influence each other. This influence can lead to errors that only exhibit themselves in certain scenarios of concurrent execution. Such errors are called race conditions. Race conditions are notoriously difficult to discover. Process synchronization provides means of avoiding race conditions by controlling or limiting the concurrency when executing code where race conditions can occur. This code is typically denoted as critical sections. Synchronization is increasingly used and being an important issue with the development of operating systems which improve the possibility for processes to cooperate with each other. In this lesson we will discuss about the concept of process synchronization and different methods of it. 9.2 CONCEPTS OF PROCESS SYNCHRONIZATION Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or commit to a certain sequence of action. Synchronization involves the orderly sharing of system resources by processes. 187 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 9.1: Railway-road Intersection To illustrate the process synchronization, consider the above railway intersection diagram. We can think of this intersection as a system resource that is shared by two processes: the car process and the train process. If only one process is active, then no resource conflict exists. But what happens when both processes are active and they both arrive at the intersection simultaneously? In this case, the shared resource becomes a problem. They cannot both use the resource at the same time or a collision will occur. Similarly, processes sharing resources on a computer must be properly managed in order to avoid “collisions.” Consider a machine with a single printer running a time-sharing operation system. If a process needs to print its results, it must request that the operating system give it access to the printer’s device driver. At this point, the operating system must decide whether to grant this request, depending upon whether the printer is already being used by another process. If it is not, the operating system should grant the request and allow the process to continue; otherwise, the operating system should deny the request and perhaps classify the process as a waiting process until the printer becomes available. Indeed, if two processes were given simultaneous access to the machine’s printer, the results would be worthless to both. Now that the problem of synchronization is properly stated, consider the following related definitions: 1. Critical Resource: A resource shared with constraints on its use (e.g., memory, files, printers, etc.) 2. Critical Section: Code that accesses a critical resource. 3. Mutual Exclusion: At most one process may be executing a critical section with respect to a particular critical resource simultaneously. In the example given above, the printer is the critical resource. Let’s suppose that the processes which are sharing this resource are called process A and process B. The critical sections of process A and process B are the sections of the code which issue the print command. In order to ensure that both processes do not attempt to use the printer at the same, they must be granted mutually exclusive access to the printer driver. We can illustrate the idea of mutual exclusion with our railroad intersection by adding a semaphore to the picture. 188 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 9.2: Railway-road Intersection with Signal Semaphores are used in software systems in much the same way as they are in railway systems. Corresponding to the section of track that can contain only one train at a time is a sequence of instructions that can be executed by only one process at a time. Such a sequence of instructions is called a critical section. 9.3 CRITICAL SECTION PROBLEMS Handling concurrent processes in a system is complex and challenging phenomenon. When multiple cooperating concurrent processes attempt to access a shared resource in such a way that they one has an effect on the other, concurrency problem occurs. The overlap of access to shared resource by more than one process is referred to as critical section. Consider the following two processes P1 and P2 modifying the global variable i. Global int i = 0; P1: Read i Increment i by 1 Store the result into i P2: Read i Increment i by 2 Store the result into i The global variable i is being accessed by both P1 and P2 hence this is a critical section problem. Critical sections must be considered a potential threat to the accuracy and correctness of a system’s functioning. As such, this problem has been given due attention 189 CU IDOL SELF LEARNING MATERIAL (SLM)

while designing an operating system. Some of the simple solutions are mentioned in the following sections. 9.3.1 Mutual Exclusion Principle The critical section problem can be solved employing a principle called mutual exclusion which simply stated means that only one of the processes is allowed to execute its critical section at a time. That is no two critical sections can be under execution simultaneously. Execution of one critical section excludes the possibility of execution of another critical section. Putting it more formally, if a process P is executing in its critical section, then no other i process P (where i > j) is allowed to enter its critical section. This is known as the principle j of mutual exclusion. While mutual exclusion does effectively ensure that the result of concurrent process will be correct, it does not ensure, however, that a process will eventually execute its critical section at all – a condition called deadlock (to be covered later) provided the following conditions are satisfied all through the execution. 1. Progress: A process operating outside of its critical section cannot prevent other processes from entering theirs; processes attempting to enter their critical sections simultaneously must decide which process enters eventually. 2. Bounded Waiting: A process attempting to enter its critical region will be able to do so eventually. Some simple implementations of the principle of mutual exclusion for two processes P0 and P1 are presented below. int i = 0; /* shared variable to enforce mutual exclusion*/ P0: while (i != 1) ; /* busy wait */ CriticalSection0; 190 CU IDOL SELF LEARNING MATERIAL (SLM)

i = 1 - i; P1: while (i != 0) ; /* busy wait */ CriticalSection1; i = 1 - i; This implementation guarantees mutual exclusion. However, it does not guarantee progress. Moreover, here bounded waiting condition is violated when one process terminates while it is its turn. Consider the following implementation with some improvement over the previous one. Remove strict alternation requirement int flag[2] = {FALSE, FALSE} /* flag[i] indicates that Pi is in its critical section */ P0: while (flag[1-i]); /* busy ..wait*/ flag[0] = TRUE; CriticalSection0; flag[0] = FALSE; P1: while (flag[1-i]); /* busy ..wait*/ flag[1] = TRUE; CriticalSection1; flag[1] = FALSE; This implementation violates mutual exclusion principle. However, the processes do progress in their respective execution and there is no bounded wait either. 191 CU IDOL SELF LEARNING MATERIAL (SLM)

9.3.2 Peterson’s Algorithm An algorithm due to Peterson offers a solution that satisfies all the conditions stated above. The same is presented below: int flag[2] = {FALSE, FALSE} /* flag[i] indicates that Pi wants to enter its critical section; i = 0 or 1 */ int j = 0; /* j indicates which process has priority in entering its critical section*/ P0: flag[0] = TRUE; j = 1; while (flag[1] && j == 1); CriticalSection0; flag[0] = FALSE; P1: flag[1] = TRUE; j = 0; while (flag[0] && j == 0); CriticalSection1; flag[1] = FALSE; This implementation satisfies all solution requirements. 9.3.3 Lamport’s Bakery Algorithm This algorithm is generalization of the solution for two processes. The following pseudocode lists the essence of this algorithm. int selecting[PROC_N] = {FALSE} int number[PROC_N] = {0} selecting[i] = TRUE; number[i] = max(number) + 1; 192 CU IDOL SELF LEARNING MATERIAL (SLM)

selecting[i] = FALSE; for (j = 0; j < PROC_N; j++) { while (selecting[j]); while (number[j] != 0 && (number[j] < number[i] || number[j] == number[i] && j < i) ); } CriticalSection(i); number[i] = 0; 9.4 SYNCHRONIZATION HARDWARE Many processors offer atomic operations such as test-and-set or compare-and-swap to prevent the process synchronization. The atomic instructions are unnecessary in uniprocessor systems, because the atomicity of any sequence of instructions can be achieved by disabling interrupts while executing it. However, often disabling interrupts is too expensive to be practical, so even programs only intended to run on uniprocessor machines will benefit by using them, as in the case of Linux’s futexes. In multiprocessor systems, it is impossible and undesirable to disable interrupts on all processors at the same time. Even with interrupts disabled, two or more processors could be attempting to access the same semaphore’s memory at the same time. The compare-and-swap instruction allows any processor to atomically test and modify a memory location, preventing such multiple processor collisions. 9.4.1 Test-and-Set It is possible implement synchronization primitives like semaphores and mutexes by using the test-and-set instruction. It is a more reasonable method of hardware assistance. The test- and-set instruction is an instruction used to both test and (conditionally) write to a memory location as part of a single atomic (i.e. non-interruptible) operation. This means setting a 193 CU IDOL SELF LEARNING MATERIAL (SLM)

value, but first performing some test (such as, the value is equal to another given value). If the test fails, the value is not set. If multiple processes may access the same memory and if a process is currently performing a test-and-set, no other process may begin another test-and-set until the first process is done. CPUs may use test-and-set instructions offered by other electronic components, such as Dual- Port RAM (DPRAM); CPUs may also offer a test-and-set instruction themselves. In the test-and-set instruction a flag is tested and resets it is value. The given memory location is set to the new value and its old value returned in a register without the opportunity for a context switch. This allows a critical section to be coded as: int flag; void enter_region(int process) { int my_flag = test_and_set(flag); while ( my_flag == 1 ) my_flag = test_and_set(flag); } void leave_region(int process) { flag = 0; } 9.4.2 Compare-and-Swap Compare-and-swap is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms. Maurice Herlihy (1991) proved that compare-and-swap can implement more of these algorithms than atomic read, write, and fetch-and-add, and that, assuming a fairly large amount of memory, it can implement all of them. The compare-and-swap CPU instruction (“CAS”) (or the CMPXCHG instruction in the x86 and Itanium architectures) is a special instruction that atomically compares the contents of a 194 CU IDOL SELF LEARNING MATERIAL (SLM)

memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple Boolean response (this variant is often called compare-and-set), or by returning the value read from the memory location (not the value written to it). 9.5 SEMAPHORES Semaphore is a software concurrency control tool. It bears analogy to old Roman system of message transmission using flags. It enforces synchronization among communicating processes and does not require busy waiting. One way to implement semaphores in computers is to use a flag (i.e. a bit of memory) that can be tested and set to either 0 or 1 in a single machine operation. Because both the test and set actions occur in the same machine instruction, this operation is indivisible and cannot be interrupted by another process which is running on the machine. By placing test-and-set operations around the critical section of a program, programmers can guarantee mutually exclusive access to the critical resource. Another way to implement a semaphore is to use a count rather than just two values. Such semaphores are called counting semaphores in contrast to the binary semaphore presented above. Counting semaphores are used to solve synchronization problems such as the Bounded Buffer problem. Technically a semaphore is an integral variable (say S) with two operations defined on it: Wait() Signal() One implementation of these functions is presented below. Wait (S) { while S <= 0; /* no-operation ..wait*/ S—; } Signal (S) 195 CU IDOL SELF LEARNING MATERIAL (SLM)

{ S++; } There are two varieties of semaphores: 1. Counting semaphore where integer value (S) can range over an unrestricted domain 2. Binary semaphore where integer value (S) can range only between 0 and 1 Incidentally they are also called mutexlocks. It provides mutual exclusion with busy waiting as shown below. S=1; /* initialized to 1 */ Wait (S); Critical Section Signal (S); Note that it must guarantee that no two processes can execute wait () and signal () on the same semaphore at the same time. Thus, implementation becomes the critical section problem where the wait and signal code are placed in the critical section. It could now have busy waiting in critical section implementation. Implementation code is short. When applications spend lots of time in critical sections this does not form a very good solution. Semaphores can be implemented without busy waiting if each semaphore is associated with a waiting queue. Each entry in a waiting queue has two data items: value (of type integer) and a pointer to next record in the list. Besides, it also contains two operations: 1. Block – to place the process invoking the operation on the appropriate waiting queue 2. Wakeup – to remove one of processes in the waiting queue and place it in the ready queue. The corresponding implementations of the same are presented below. Wait (S) { 196 CU IDOL SELF LEARNING MATERIAL (SLM)

value—; if (value < 0) { /*add this process to waiting queue*/ block(); } } Signal (S) { value++; if (value <= 0) { /*remove a this process (say P) from the waiting queue*/ wakeup(P); } } 9.6 CLASSICAL PROBLEMS OF SYNCHRONIZATION 9.6.1 The Producer–Consumer Problem In this problem, two processes, one called the producer and the other called the consumer, run concurrently and share a common buffer. The producer generates items that it must pass to the consumer, who is to consume them. The producer passes items to the consumer through the buffer. However, the producer must be certain that it does not deposit an item into the buffer when the buffer is full, and the consumer must not extract an item from an empty buffer. The two processes also must not access the buffer at the same time, for if the consumer tries to extract an item from the slot into which the producer is depositing an item, the consumer might get only part of the item. Any solution to this problem must ensure none of the above three events occur. 197 CU IDOL SELF LEARNING MATERIAL (SLM)

A practical example of this problem is electronic mail. The process you use to send the mail must not insert the letter into a full mailbox (otherwise the recipient will never see it); similarly, the recipient must not read a letter from an empty mailbox (or he might obtain something meaningless but that looks like a letter). Also, the sender (producer) must not deposit a letter in the mailbox at the same time the recipient extracts a letter from the mailbox; otherwise, the state of the mailbox will be uncertain. Because the buffer has a maximum size, this problem is often called the bounded buffer problem. A (less common) variant of it is the unbounded buffer problem, which assumes the buffer is infinite. This eliminates the problem of the producer having to worry about the buffer filling up, but the other two concerns must be dealt with. Figure 9.3: Producer-Consumer Problem 9.6.2 The Readers–Writers Problem In this problem, a number of concurrent processes require access to some object (such as a file.) Some processes extract information from the object and are called readers; others change or insert information in the object and are called writers. The Bernstein conditions state that many readers may access the object concurrently, but if a writer is accessing the object, no other processes (readers or writers) may access the object. There are two possible policies for doing this: 198 CU IDOL SELF LEARNING MATERIAL (SLM)

First Readers-Writers Problem: Readers have priority over writers; that is, unless a writer has permission to access the object, any reader requesting access to the object will get it. Note this may result in a writer waiting indefinitely to access the object. Second Readers-Writers Problem: Writers have priority over readers; that is, when a writer wishes to access the object, only readers which have already obtained permission to access the object are allowed to complete their access; any readers that request access after the writer has done so must wait until the writer is done. Note this may result in readers waiting indefinitely to access the object. So there are two concerns: first, enforce the Bernstein conditions among the processes, and secondly, enforcing the appropriate policy of whether the readers or the writers have priority. A typical example of this occurs with databases, when several processes are accessing data; some will want only to read the data, others to change it. The database must implement some mechanism that solves the readers–writers’ problem. Figure 9.4: Readers Writers Problem 9.6.3 The Dining Philosophers Problem In this problem, five philosophers sit around a circular table eating spaghetti and thinking. In front of each philosopher is a plate and to the left of each plate is a fork (so there are five forks, one to the right and one to the left of each philosopher’s plate; see the figure). When a philosopher wishes to eat, he picks up the forks to the right and to the left of his plate. When done, he puts both forks back on the table. The problem is to ensure that no philosopher will be allowed to starve because he cannot ever pick up both forks. 199 CU IDOL SELF LEARNING MATERIAL (SLM)

There are two issues here: first, deadlock (where each philosopher picks up one fork so none can get the second) must never occur; and second, no set of philosophers should be able to act to prevent another philosopher from ever eating. A solution must prevent both. Figure 9.5: The Dining Philosopher’s Table 9.7 SUMMARY  Race condition is a flaw in a system of processes whereby the output of the process is unexpectedly and critically dependent on the sequence of other processes. It may arise in multi-process environment, especially when communicating between separate processes or threads of execution. Mutual exclusion means that only one of the processes is allowed to execute its critical section at a time. Mutex, semaphores and motors are some of the process synchronization tools. Mutex is a software tool used in concurrency control. It is short form of mutual exclusion.  A mutex is a program element that allows multiple program processes to share the same resource but not simultaneously. Semaphore is a software concurrency control tool. It bears analogy to old Roman system of message transmission using flags. It enforces synchronization among communicating processes and does not require busy waiting. In counting semaphore, the integer value can range over an unrestricted domain. In binary semaphore the integer value can range only between 0 and 1.  Bounded Buffer Problem, readers and writer’s problem, sleeping barber problem, and dining philosopher problem are some of the classical synchronization problems taken from real life situations. 200 CU IDOL SELF LEARNING MATERIAL (SLM)