CPU Scheduling and Types of Schedulers

A) CPU scheduling CPU scheduling is a process which allows one process to use the CPU while the execution of another process is on hold(in waiting state) due to unavailability of any resource like I/O etc, thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient, fast and fair. Why do we need scheduling? A typical process involves both I/O time and CPU time. In a uniprogramming system like MS-DOS, time spent waiting for I/O is wasted and CPU is free during this time. In multiprogramming systems, one process can use CPU while another is waiting for I/O. This is possible only with process scheduling. The process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process on the basis of a particular strategy. 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.

Types of Schedulers 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. Schedulers are of three types Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler

1) Long Term Scheduler It is also called a job scheduler. A long-term scheduler determines which programs are admitted to the system for processing. It selects processes from the queue and loads them into memory for execution. Process loads into the memory for CPU scheduling. The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and processor bound. It also controls the degree of multiprogramming. 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. On some systems, the long-term scheduler may not be available or minimal. Time-sharing operating systems have no long term scheduler. When a process changes the state from new to ready, then there is use of long-term scheduler.

2) Short Term Scheduler It is also called as CPU scheduler. Its main objective is to increase system performance in accordance with the chosen set of criteria. It is the change of ready state to running state of the process. CPU scheduler selects a process among the processes that are ready to execute and allocates CPU to one of them. Short-term schedulers, also known as dispatchers, make the decision of which process to execute next. Short-term schedulers are faster than long-term schedulers.

3) Medium Term Scheduler :- Medium-term scheduling is a part of swapping. It removes the processes from the memory. It reduces the degree of multiprogramming. The medium-term scheduler is in-charge of handling the swapped out-processes. A running process may become suspended if it makes an I/O request. A suspended processes cannot make any progress towards completion. In this condition, to remove the process from memory and make space for other processes, the suspended process is moved to the secondary storage. This process is called swapping, and the process is said to be swapped out or rolled out. Swapping may be necessary to improve the process mix.

critical section a critical section is group of instructions/statements or region of code that need to be executed atomically (read this post for atomicity), such as accessing a resource (file, input or output port, global data, etc.). In concurrent programming, if one thread tries to change the value of shared data at the same time as another thread tries to read the value (i.e. data race across threads), the result is unpredictable. The access to such shared variable (shared memory, shared files, shared port, etc ) to be synchronized. Few programming languages have built in support for synchronization. It is critical to understand the importance of race condition while writing kernel mode programming (a device driver, kernel thread, etc.). since the programmer can directly access and modifying kernel data structures.

A Critical Section is a code segment that accesses shared variables and has to be executed as an atomic action. It means that in a group of cooperating processes, at a given point of time, only one process must be executing its critical section. If any other process also wants to execute its critical section, it must wait until the first one finishes.

Scheduling Criteria There are many different criterias to check when considering the "best" scheduling algorithm, they are: CPU Utilization :- To make out the best use of CPU and not to waste any CPU cycle, CPU would be working most of the time(Ideally 100% of the time). Considering a real system, CPU usage should range from 40% (lightly loaded) to 90% (heavily loaded.) Throughput :- It is the total number of processes completed per unit time or rather say total amount of work done in a unit of time. This may range from 10/second to 1/hour depending on the specific processes. Turnaround Time :- It is the amount of time taken to execute a particular process, i.e. The interval from time of submission of the process to the time of completion of the process(Wall clock time). Waiting Time :- The sum of the periods spent waiting in the ready queue amount of time a process has been waiting in the ready queue to acquire get control on the CPU. Load Average :- It is the average number of processes residing in the ready queue waiting for their turn to get into the CPU. Response Time :Amount of time it takes from when a request was submitted until the first response is produced. Remember, it is the time till the first response and not the completion of process execution(final response). In general CPU utilization and Throughput are maximized and other factors are reduced for proper optimization.

Scheduling Algorithms 1. First Come First Serve(FCFS) Scheduling 2. Shortest-Job-First(SJF) Scheduling 3. Shortest remaining time 4. Priority Scheduling 5. Round Robin(RR) Scheduling

1. First Come First Serve (FCFS) Jobs are executed on first come, first serve basis. It is a non-preemptive, 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. Average Wait Time: (0+4+6+13) / 4 = 5.75 Process Wait Time : Service Time - Arrival Time P0 0 - 0 = 0 P1 5 - 1 = 4 P2 8 - 2 = 6 P3 16 - 3 = 13

2. Shortest Job Next (SJN) This is also known as shortest job first, or SJF This is a non-preemptive, 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. Gantt Chart Average Wait Time: (3+12+5) / 4 = 5 Process Arrival Time Execute Time Service Time Process Wait Time : Service Time - Arrival Time P0 0 5 3 P0 3 - 0 = 3 P1 0 P1 1 3 0 P2 14 - 2 = 12 P2 2 8 14 P3 8 - 3 = 5 P3 3 6 8

3. Priority Based Scheduling Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems. Each process is assigned a priority. Process with highest priority is to be executed first and so on. Processes with same priority are executed on first come first served basis. Priority can be decided based on memory requirements, time requirements or any other resource requirement. Average Wait Time: (9+5+12+0) / 4 = 6.5 Proce ss Wait Time : Service Time - Arrival Time P0 9 - 0 = 9 P1 6 - 1 = 5 P2 14 - 2 = 12 P3 0 - 0 = 0

Shortest Remaining Time Shortest remaining time, also known as shortest remaining time first (SRTF), is a scheduling method that is a preemptive version of shortest job next scheduling. In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Shortest remaining time (SRT) is the preemptive version of the SJN algorithm. The processor is allocated to the job closest to completion but it can be preempted 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. Advantages of SRTF Scheduling (i) Many processes execute in less amount of time. So, throughput is increased. (ii) Processes which have short burst time run fast. Disadvantages of SRTF Scheduling (i) Practically it is not possible to predict the burst time. (ii) Processes which have long burst time will have to wait for long time for execution.

4. Round Robin Scheduling Round Robin is the preemptive 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 preempted and other process executes for a given time period. Context switching is used to save states of preempted processes. Average Wait Time: (9+2+12+11) / 4 = 8.5 Proce ss 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

5. 5. Multilevel Queue Scheduling Multilevel Queue Scheduling: Multilevel Queue Scheduling based on response time requirements. Some process required a quick response by the processor; some processes can wait. Processes can be classifieds -Foreground process and background process. Based on memory size, priority and process type ready queue is assigned to processes. Separate queues used for foreground and background processes. Both processes are scheduled by the different scheduling algorithm. Foreground process used RR algorithm, and background process used FCFS algorithm. Lets us discuss an example of Multilevel Queue Scheduling with five queues having a different priority level. 1. System Processes 2. Interactive Processes 3. Interactive Editing processes 4. Batch Processes 5. Student Processes Each queue has a different level of priority. If an interactive editing process entered in ready queue and Student process was running. Then student process preempted and interactive editing process first execute.

B) Process Synchronization Concurrent access to shared data is handled thereby minimizing the chance of inconsistent data. Maintaining data consistency demands mechanisms to ensure synchronized execution of cooperating processes. Process Synchronization was introduced to handle problems that arose while multiple process executions. Process Synchronization means sharing system resources by processes in a such a way that, Critical Section Problem as an atomic action. It means that in a group of cooperating processes, at a given point of time, only one process must be executing its critical section. If any other process also wants to execute its critical section, it must wait until the first one finishes. A Critical Section is a code segment that accesses shared variables and has to be executed

Solution to Critical Section Problem 1. Mutual Exclusion If a process is executing in its critical section, then no other process is allowed to execute in the critical section Out of a group of cooperating processes, only one process can be in its critical section at a given point of time. It states that no other process is allowed to execute in the critical section if a process is executing in critical section. 2. Progress critical section. If no process is in its critical section, and if one or more threads want to execute their critical section then any one of these threads must be allowed to get into its critical section. When no process is in the critical section, then any process from outside that request for execution can enter in the critical section without any delay. Only those process can enter that have requested and have finite time to enter the process. If no process is in the critical section, then no other process from outside can block it from entering the 3. Bounded Waiting A bound must exist 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. After a process makes a request for getting into its critical section, there is a limit for how many other processes can get into their critical section, before this process's request is granted. So after the limit is reached, system must grant the process permission to get into its critical section. An upper bound must exist on the number of times a process enters so 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.

Process Synchronization are handled by two approaches: 1. Software Synchronization In Software , Some specific Algorithm approach is used to maintain synchronization of the data. Like in Approach One or Approach Two, for a number of two process, a temporary variable like (turn) or Boolean variable (flag) value is used to store the data. When the condition is True then the process in waiting State, known as Busy Waiting State. This does not satisfy all the Critical Section requirements. Another Software approach known as Peterson s Solution is best for Synchronization. It uses two variables in the Entry Section so as to maintain consistency, like Flag (Boolean variable) and Turn variable(storing the process states). It satisfy all the three Critical Section requirements.

2. Synchronization Hardware Many systems provide hardware support for critical section code. The critical section problem could be solved easily in a single-processor environment if we could disallow interrupts to occur while a shared variable or resource is being modified. In this manner, we could be sure that the current sequence of instructions would be allowed to execute in order without pre-emption. Unfortunately, this solution is not feasible in a multiprocessor environment. Disabling interrupt on a multiprocessor environment can be time consuming as the message is passed to all the processors. This message transmission lag, delays entry of threads into critical section and the system efficiency decreases. The Hardware Approach of synchronization can be done through Lock & Unlock technique. Locking part is done in the Entry Section, so that only one process is allowed to enter into the Critical Section, after it complete its execution, the process is moved to the Exit Section, where Unlock Operation is done so that another process in the Lock Section can repeat this process of Execution. This process is designed in such a way that all the three conditions of the Critical Sections are satisfied. Mutex Locks As the synchronization hardware solution is not easy to implement for everyone, a strict software approach called Mutex Locks was introduced. In this approach, in the entry section of code, a LOCK is acquired over the critical resources modified and used inside critical section, and in the exit section that LOCK is released. As the resource is locked while a process executes its critical section hence no other process can access it.

SEMAPHORE Semaphore is a simply a variable. This variable is used to solve critical section problem and to achieve process synchronization in the multi processing environment. The value of a simple integer variable to synchronize the progress of interacting processes. This integer variable is called semaphore. So it is basically a synchronizing tool and is accessed only through two low standard atomic operations, wait and signal designated by P(S) and V(S) respectively. 1. Wait: Decrements the value of its argument S, as soon as it would become non-negative(greater than or equal to 1). The wait operation decrements the value of its argument S, if it is positive. If S is negative or zero, then no operation is performed. wait(S) { while (S<=0); S--; } 2. Signal: Increments the value of its argument S, as there is no more process blocked on the queue. signal(S) { S++; }

Types of Semaphores Semaphores are mainly of two types: 1.Binary Semaphore: It is a special form of semaphore used for implementing mutual exclusion, hence it is often called a Mutex. A binary semaphore is initialized to 1 and only takes the values 0 and 1 during execution of a program. Binary semaphore can take the value 0 & 1 only. Counting semaphore can take nonnegative integer values. 2.Counting Semaphores: These are used to implement bounded concurrency. These semaphores are used to coordinate the resource access, where the semaphore count is the number of available resources. If the resources are added, semaphore count automatically incremented and if the resources are removed, the count is decremented.

Advantages of Semaphores Semaphores allow only one process into the critical section. They follow the mutual exclusion principle strictly and are much more efficient than some other methods of synchronization. There is no resource wastage because of busy waiting in semaphores as processor time is not wasted unnecessarily to check if a condition is fulfilled to allow a process to access the critical section. Semaphores are implemented in the machine independent code of the microkernel. So they are machine independent. Disadvantages of Semaphores Semaphores are complicated so the wait and signal operations must be implemented in the correct order to prevent deadlocks. Semaphores are impractical for last scale use as their use leads to loss of modularity. This happens because the wait and signal operations prevent the creation of a structured layout for the system. Semaphores may lead to a priority inversion where low priority processes may access the critical section first and high priority processes later.

MONITORS Monitor is one of the ways to achieve Process synchronization. Monitor is supported by programming languages to achieve mutual exclusion between processes. For example Java Synchronized methods. Java provides wait() and notify() constructs. A monitor is a set of multiple routines which are protected by a mutual exclusion lock. None of the routines in the monitor can be executed by a thread until that thread acquires the lock. This means that only ONE thread can execute within the monitor at a time. Any other threads must wait for the thread that s currently executing to give up control of the lock. Monitors are supposed to be used in a multithreaded or multiproces environment in which multiple threads/processes may call the monitor procedures at the same time asking for service. Thus, a monitor guarantees that at any moment at most one thread can be executing in a monitor! If a thread calls a monitor procedure, this thread will be blocked if there is another thread executing in the monitor. Those threads that were not granted the entering permission will be queued to a monitor entry queue outside of the monitor. When the monitor becomes empty (i.e., no thread is executing in it), one of the threads in the entry queue will be released and granted the permission to execute the called monitor procedure.

A monitor has four components Initialization contains the code that is used exactly once when the monitor is created . The private data section contains all private data, including private procedures, that can only be used within the monitor. Thus, these private items are not visible from outside of the monitor. The monitor procedures are procedures that can be called from outside of the monitor. The monitor entry queue contains all threads that called monitor procedures but have not been granted permissions.

Problem of Synchronization : 1. Bounded Buffer (Producer-Consumer) Problem :- This problem is generalized in terms of the Producer Consumer problem, where a finite buffer pool is used to exchange messages between producer and consumer processes. Because the buffer pool has a maximum size, this problem is often called the Bounded buffer problem. Solution to this problem is, creating two counting semaphores "full" and "empty" to keep track of the current number of full and empty buffers respectively. 2. The Readers Writers Problem :- n this problem there are some processes(called readers) that only read the shared data, and never change it, and there are other processes(called writers) who may change the data in addition to reading, or instead of reading it. There are various type of readers-writers problem, most centered on relative priorities of readers and writers. 3. Dining Philosophers Problem :- The dining philosopher's problem involves the allocation of limited resources to a group of processes in a deadlock-free and starvation-free manner. There are five philosophers sitting around a table, in which there are five chopsticks/forks kept beside them and a bowl of rice in the centre, When a philosopher wants to eat, he uses two chopsticks - one from their left and one from their right. When a philosopher wants to think, he keeps down both chopsticks at their original place.

What is a Deadlock? Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. deadlock refers to a specific condition when two or more processes are each waiting for another to release a resource, or more than two processes are waiting for resources in a circular chain (see Necessary conditions). A deadlock is a situation in which two computer programs sharing the same resource are effectively preventing each other from accessing the resource, resulting in both programs ceasing to function. The earliest computer operating systems ran only one program at a time. BRIDGE

the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1.

AVOID DEADLOCKS The four conditions : 1. Mutual Exclusion :- Resources shared such as read-only files do not lead to deadlocks but resources, such as printers and tape drives, requires exclusive access by a single process. There should be a resource that can only be held by one process at a time. In the diagram below, there is a single instance of Resource 1 and it is held by Process 1 only.

2. Hold and Wait :- In this condition processes must be prevented from holding one or more resources while simultaneously waiting for one or more others. A process can hold multiple resources and still request more resources from other processes which are holding them. In the diagram given below, Process 2 holds Resource 2 and Resource 3 and is requesting the Resource 1 which is held by Process 1.

3. No Preemption :- Preemption of process resource allocations can avoid the condition of deadlocks, where ever possible. A resource cannot be preempted from a process by force. A process can only release a resource voluntarily. In the diagram below, Process 2 cannot preempt Resource 1 from Process 1. It will only be released when Process 1 relinquishes it voluntarily after its execution is complete.

4. Circular Wait :- Circular wait can be avoided if we number all resources, and require that processes request resources only in strictly increasing(or decreasing) order. A process is waiting for the resource held by the second process, which is waiting for the resource held by the third process and so on, till the last process is waiting for a resource held by the first process. This forms a circular chain. For example: Process 1 is allocated Resource2 and it is requesting Resource 1. Similarly, Process 2 is allocated Resource 1 and it is requesting Resource 2. This forms a circular wait loop.

methods for handling deadlocks. Deadlock Detection A deadlock can be detected by a resource scheduler as it keeps track of all the resources that are allocated to different processes. After a deadlock is detected, it can be resolved. All the processes that are involved in the deadlock are terminated. This is not a good approach as all the progress made by the processes is destroyed. Resources can be preempted from some processes and given to others till the deadlock is resolved. Deadlock Prevention It is very important to prevent a deadlock before it can occur. So, the system checks each transaction before it is executed to make sure it does not lead to deadlock. If there is even a slight chance that a transaction may lead to deadlock in the future, it is never allowed to execute. Deadlock Avoidance It is better to avoid a deadlock rather than take measures after the deadlock has occurred. The wait for graph can be used for deadlock avoidance. This is however only useful for smaller databases as it can get quite complex in larger databases. Deadlock Recovery Detect deadlock and, when it occurs, take steps to recover.

https://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htmhttps://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htm http://ecomputernotes.com/fundamental/disk-operating-system/cpu-scheduling-algorithms https://www.geeksforgeeks.org/semaphores-operating-system/ https://www.studytonight.com/operating-system/introduction-to-semaphores https://www.geeksforgeeks.org/monitors/ https://www.studytonight.com/operating-system/process-synchronization https://www.geeksforgeeks.org/operating-system-process-synchronization/