Process Scheduling PDF

IT2105 Scheduling of the ready state to the running state of the process. The dispatcher Process Scheduling executes more frequently compared to the job s...

IT2105 Scheduling of the ready state to the running state of the process. The dispatcher Process Scheduling executes more frequently compared to the job scheduler, and makes the Scheduling or process scheduling is the act of selecting a job or a task that fine-grained decisions of which process to execute next. The primary is to be dispatched. In some operating systems, other units of work, such as objective of the dispatcher is to increase the system performance in the input/output (I/O) operations, may also be scheduled (Stallings, 2018). This accordance with the chosen set of criteria. particular activity of the process manager handles the removal of a running Medium-term scheduling – This is a part of the swapping function. The process from the central processing unit (CPU), followed by the selection of medium-term scheduler is in charge of handling the swapped-out another process on the basis of a particular strategy or algorithm. The processes. On the other hand, the swapping-in decision is based on the operating system (OS) maintains the following important process scheduling need to manage the degree of multiprogramming. This actually reduces queues (Tutorialspoint, n.d.): the degree of multiprogramming. Job queue – This queue contains all the processes in the system. o Swapping: A running process becomes suspended if it makes an I/O Ready queue – This queue keeps a set of all processes residing in the request, wherein it cannot make any progress towards completion. In main memory, ready and waiting to execute. A new process is always order to remove the process from the memory and make space for added to this queue. other processes, the suspended process is moved to the secondary Device queue – This queue contains processes waiting for a device to storage. Hence, the process of swapping. become available. Note that there are unique queues available for each I/O device. Generally, a set of criteria is established against various scheduling policies that may be evaluated. Note that it is impossible to optimize all scheduling Process scheduling is an essential part of a multiprogramming operating criteria simultaneously. The following are the key scheduling criteria that are system. The basic intent of process scheduling is to divide CPU time among usually encountered in operating systems (Stallings, 2018): active processes and threads and maintain a notion of priority in order to Turnaround time: The interval of time between the submission of a execute a more important job or task sooner. The scheduling of processes on process and its completion. This involves the time spent waiting in the processors and individual CPUs are performed by the scheduler, a key ready queue, plus the actual execution time, plus the time spent waiting component of the OS kernel (Gregg, 2021). for resources, including the processor. Formula: Turnaround Time = Finish Time – Arrival Time Process scheduling assigns processes to be executed in a way that meets Response time: The time from the submission of a request until the system objectives, such as response time and throughput. The scheduling response begins to be received. In most cases, a process begins activity can be broken down into three (3) separate functions below. The producing some output to the user while continuing to process the request. names suggest the relative time scales with which these functions are Thus, this criteria is a better measure than the turnaround time from the performed (Stallings, 2018). user's point of view. In addition, the scheduling discipline should attempt Long-term scheduling – This involves a long-term scheduler, also known to achieve low response time and maximize the number of users receiving as a job scheduler, that determines which programs are admitted to the the acceptable response time. system for processing. Thus, it controls the degree of multiprogramming. Burst time: The amount of time required for a process to be executed by If the degree of multiprogramming is stable, then the average rate of the CPU. This criterion is also called the execution time or running time process creation must be equal to the average departure rate of processes (Ishaque, n.d.). of the system. The primary objective of the job scheduler is to provide a Waiting time: The scheduling algorithm also affects the amount of time balanced mix of jobs. that a process spends waiting in the ready queue. This is the sum of the Short-term scheduling – This involves a short-term scheduler, also periods spent waiting in the ready queue (Silberschatz, Galvin, & Gagne, known as the dispatcher, that is invoked whenever an event that may 2018). Formula: Waiting Time = Turnaround Time – Burst Time lead to the blocking of the current process occurs. It is actually the change 06 Handout 1 *Property of STI  [email protected] Page 1 of 4  IT2105 Throughput: The scheduling algorithm should attempt to maximize the Preemptive: The currently running processes may be interrupted and number of processes completed per unit of time. This is the measure of moved to the Ready State by the OS. The decision to preempt may be how much work is being performed by the processor. performed during the following circumstances: Processor utilization: The percentage of time that the processor is busy. o A new process arrives For exclusive shared systems, this criterion is significant. In other systems, o An interrupt occurs that places a blocked process in the Ready State including single-user systems, this criterion is less important. Conceptually, processor utilization can range from 0 to 100 percent. In a First-Come First-Serve (FCFS) real system, it should range from 40% (lightly loaded) to 90% (heavily In this algorithm, all incoming processes join the ready queue. Then, if the loaded). currently running process ceases to execute, the process that has been in the Priority: The process priority can be modified dynamically by the ready queue the longest is selected for running. FCFS performs better for long scheduler to improve the performance of certain workloads. Note that processes. It is not an appealing alternative on its own for a uniprocessor when processes are assigned with specific priorities, the scheduling system. However, it is often combined with a priority scheme to provide an algorithm should favor higher-priority processes. effective scheduler (Stallings, 2018). Fairness: In the absence of guidance from the user or other system- It is a non-preemptive algorithm. supplied guidance, processes should be treated the same, and no process It is easy to understand and implement. should suffer from starvation. It is also identified as a strict queuing scheme. Resource balancing: The scheduling algorithm should keep the All jobs are executed on a first-come first-serve basis. resources of the system busy. Processes that will underutilize stressed The performance of this algorithm is poor since the average waiting time resources should be favored. This criterion also involves is high. In operating systems, workloads can be categorized as either of the following FCFS Example: (Gregg, 2021): Process A B C D E CPU-bound – This includes applications that perform heavy compute Arrival Time 0 2 4 6 8 operations, such as scientific and mathematical analysis, which are Bust Time (Ts) 3 6 4 5 2 expected to have long runtimes. I/O-bound – This includes applications that perform input/output Finish Time 3 9 13 18 20 Turnaround operations, such as web servers, file servers, and interactive shells, where 3 7 9 12 12 Time (Tr) low-latency responses are desirable. Waiting Time 0 1 5 7 10 Tr/Ts 1.00 1.17 2.25 2.40 6.00 Process Scheduling Algorithms In process scheduling, each algorithm encompasses a specific selection function that determines which process among the ready processes is selected next for execution, and a decision mode that specifies the instants in time at which the selection function is exercised. The decision mode of an algorithm can either be (Stallings, 2018): Non-preemptive: Once a process is in the Running State, it continues to execute until it terminates or it blocks itself to wait for an I/O operation or to request some OS service. Average Turnaround Time: 43 / 5 = 8.60 Average Waiting Time: 23 / 5 = 4.60 Average Tr/Ts: 12.82 / 5 = 2.56 06 Handout 1 *Property of STI  [email protected] Page 2 of 4  IT2105 Shortest Job First (SJF) The scheduler always chooses and executes the process that has the This algorithm is easy to implement in batch systems, where the required CPU shortest expected remaining processing time. time is known in advance. On the other hand, this algorithm is impossible to This does not have the bias in favor of long processes found in a first- implement in interactive systems where the required CPU time is unknown. It come first-serve setup. is the best approach to minimize the waiting time (Tutorialspoint, n.d.). There are no additional interrupts generated, reducing the overhead. It is a non-preemptive algorithm. The elapsed service time can be recorded, contributing to the overhead. It is also called the shortest job next or shortest process next. This algorithm selects and executes the process with the shortest SRTF Example: expected or estimated processing time. Thus, the processing time must Process A B C D E be known in advance by the processor. Arrival Time 0 2 4 6 8 Bust Time (Ts) 3 6 4 5 2 SJF Example: Process A B C D E Finish Time 3 15 8 20 10 Arrival Time 0 2 4 6 8 Turnaround Time (Tr) 3 13 4 14 2 Bust Time (Ts) 3 6 4 5 2 Waiting Time 0 7 0 9 0 Tr/Ts 1.00 2.17 1.00 2.80 1.00 Finish Time 3 9 15 20 11 Turnaround Time (Tr) 3 7 11 14 3 Waiting Time 0 1 7 9 1 Tr/Ts 1.00 1.17 2.75 2.80 1.50 Average Turnaround Time: 36 / 5 = 7.20 Average Waiting Time: 16 / 5 = 3.20 Average Tr/Ts: 7.97 / 5 = 1.59 Average Turnaround Time: 38 / 5 = 7.60 Round Robin (RR) Average Waiting Time: 18 / 5 = 3.60 This algorithm involves the generation of a clock interrupt at periodic intervals. Average Tr/Ts: 9.22 / 5 = 1.84 When the interrupt occurs, the currently running process is placed in the ready queue, and the next ready job is selected on a first-come first-serve basis. This Shortest Remaining Time First (SRTF) technique is known as time slicing, because each process is given a slice of In this algorithm, when a new process with a shorter remaining time joins the time before being preempted (Stallings, 2018). ready queue, the scheduler may preempt the currently running process and It is a preemptive algorithm. execute the new one. The scheduler must have an estimate of the processing Each process is provided with a fixed time to execute, called the quantum. time to perform the selection function. In addition, the risk of starvation of long Once a process has consumed all its allotted execution time, it is processes exists (Stallings, 2018). automatically preempted and another process executes for a given period It is a preemptive version of the SJF algorithm. of time. 06 Handout 1 *Property of STI  [email protected] Page 3 of 4  IT2105 RR Example: NPP Example: Process A B C D E Process A B C D E Arrival Time 0 2 4 6 8 Arrival Time 0 0 6 11 12 Bust Time (Ts) 3 6 4 5 2 Bust Time (Ts) 4 3 7 4 2 Finish Time 3 17 11 20 19 Finish Time 4 7 14 20 16 Turnaround Turnaround Time (Tr) 3 15 7 14 11 Time (Tr) 4 7 8 9 4 Waiting Time 0 9 3 9 9 Waiting Time 0 4 1 5 2 Tr/Ts 1.00 2.50 1.75 2.80 5.50 Quantum = 4 Average Turnaround Time: 32 / 5 = 6.40 Average Waiting Time: 12 / 5 = 2.40 Average Turnaround Time: 50 / 5 = 10.00 Average Waiting Time: 30 / 5 = 6.00 References: Average Tr/Ts: 13.55 / 5 = 2.71 Gregg, B. (2021). System performance: Enterprise and Cloud (2 nd ed.). Pearson Education, Inc. Ishaque, S. (n.d.). Arrival, burst, completion, turnaround, waiting, & response time. Retrieved on November 15, 2021 from https://www.educative.io/edpresso/arrival-burst-completion-turnaround-waiting-response-time Non-Preemptive Priority (NPP) Scheduling Silberschatz, A., Galvin, P. & Gagne, G. (2018). Operating systems concepts (10 th ed.). John Wiley & Sons, Inc. In general, each system process is assigned with a corresponding priority, and Stallings, W. (2018). Operating systems: Internal and design principles (9 th ed.). Pearson Education Limited Tutorialspoint. (n.d.). Operating system scheduling algorithm. Retrieved on November 15, 2021 from the scheduler will always choose a process of higher priority. A particular https://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htm challenge exists in implementing a pure priority-based scheduling, and that is: Tutorialspoint. (n.d.). Operating Systems – Process Scheduling. Retrieved on November 15, 2021 from https://www.tutorialspoint.com/operating_system/os_process_scheduling.htm lower priority processes may suffer starvation. This can possibly occur if there is a constant and steady supply of higher-priority processes. On the other hand, the priority of a process can still change based on its age or execution history (Stallings, 2018). It is a non-preemptive algorithm. It is the most common scheduling algorithm in batch systems. Each process is assigned with a priority and the process with the highest priority will always be executed first. Processes with the same priority level are executed on a first-come first- serve basis. The priority of a process can be based on memory requirements, time requirements, or any other resource requirements. 06 Handout 1 *Property of STI  [email protected] Page 4 of 4