Ch09-OS9e.pdf

Operatin g Systems: Internals Chapter 9 and Uniprocessor Design Principle Scheduling...

Operatin g Systems: Internals Chapter 9 and Uniprocessor Design Principle Scheduling Ninth Edition s By William Stallings © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Table 9.1 Types of Scheduling Long-term scheduling The decision to add to the pool of processes to be executed Medium-term scheduling The decision to add to the number of processes that are partially or fully in main memory Short-term scheduling The decision as to which available process will be executed by the processor I/O scheduling The decision as to which process's pending I/O request shall be handled by an available I/O device © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. Processor Scheduling Aim is to assign processes to be executed by the processor in a way that meets system objectives, such as response time, throughput, and processor efficiency Broken down into three separate functions: Medium Long term Short term term scheduling scheduling scheduling © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  New Long-term Long-term scheduling scheduling Ready/ Suspend Ready Running Exit Medium-term Short-term scheduling scheduling Blocked/ Blocked Suspend Medium-term scheduling Figure 9.1 Scheduling and Process State Transitions © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. Long-Term Scheduler Determines which Creates processes programs are admitted to from the queue the system for processing when it can, but must decide: Controls the degree of multiprogramming The more processes that are created, the When the operating Which jobs to accept system can take on smaller the one or more and turn into processes percentage of time additional processes that each process can be executed May limit to provide satisfactory service Priority, expected to the current set of First come, first execution time, I/O processes served requirements © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Medium-Term Scheduling Part of the swapping function Swapping-in decisions are based on the need to manage the degree of multiprogramming Considers the memory requirements of the swapped-out processes © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Short-Term Scheduling Known as the dispatcher Executes most frequently Makes the fine-grained decision of which process to execute next Invoked when an event occurs that may lead to the blocking of the current process or that may provide an opportunity to preempt a currently running process in favor of another Examples: Clock interrupts I/O interrupts Operating system calls Signals (e.g., semaphores) © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Short Term Scheduling Criteria Main objective is to allocate processor time to optimize certain User-oriented criteria System-oriented aspects of Relate to the behavior of criteria system behavior the system as perceived Focus is on effective by the individual user or and efficient utilization A set of criteria is process (such as of the processor (rate at needed to response time in an which processes are evaluate the interactive system) completed) Important on virtually all Generally of minor scheduling policy systems importance on single- user systems © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Short-Term Scheduling Criteria: Performance Examples: Example: Response time Criteria can Predictability and throughput be classified into: Non-performance Performance-related related Easily Hard to Quantitative Qualitative measured measure © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  User Oriented, Performance Related Turnaround time This is the interval of time between the submission of a process and its completion. Includes actual execution time plus time spent waiting for resources, including the processor. This is an appropriate measure for a batch job. Response time For an interactive process, this is the time from the submission of a request until the response begins to be received. Often a process can begin producing some output to the user while Table 9.2 continuing to process the request. Thus, this is a better measure than turnaround time from the user's point of view. The scheduling discipline should attempt to achieve low response time and to maximize the number of interactive users receiving acceptable response time. Deadlines When process completion deadlines can be specified, the Scheduling Criteria scheduling discipline should subordinate other goals to that of maximizing the percentage of deadlines met. User Oriented, Other Predictability A given job should run in about the same amount of time and at about the same cost regardless of the load on the system. A wide variation in response time or turnaround time is distracting to users. It may signal a wide swing in system workloads or the need for system tuning to cure instabilities. System Oriented, Performance Related Throughput The scheduling policy should attempt to maximize the number of processes completed per unit of time. This is a measure of how much work is being performed. This clearly depends on the average length of a process but is also influenced by the scheduling policy, which may affect utilization. Processor utilization This is the percentage of time that the processor is busy. For an expensive shared system, this is a significant criterion. In single-user systems and in some other systems, such as real-time systems, this criterion is less important than some of the others. System Oriented, Other Fairness In the absence of guidance from the user or other system- supplied guidance, processes should be treated the same, and no process should suffer starvation. Enforcing priorities When processes are assigned priorities, the scheduling policy should favor higher-priority processes. (Table can be found on page 403 in textbook) Balancing resources The scheduling policy should keep the resources of the system busy. Processes that will underutilize stressed resources should be favored. This criterion also involves © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. medium-term and long-term scheduling.  RQ0 Release Dispatch Processor RQ1 Admit RQn Preemption Event Wait Event occurs Blocked Queue Figure 9.4 Priority Queuing © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Round FCFS SPN SRT HRRN Feedback robin Selection æ w + sö max[w] constant min[s] min[s – e] maxç ÷ (see text) function è s ø Decision Non- Preemptive (at time Non- Preemptive Non- Preemptive (at time Table 9.3 mode preemptive preemptive (at arrival) preemptive quantum) quantum) May be Through- low if Characteristics Not Not quantum High High High of Various Put emphasized is too emphasized small Scheduling May be Policies high, Provides Provides especially if good good Provides there is a Response response response good Provides good Not large time time for time for response response time emphasized variance in time short short process processes processes execution times Overhead Minimum Minimum Can be high Can be high Can be high Can be high Penalizes short Penalizes Penalizes May favor Effect on processes; Fair long long Good balance I/O bound processes penalizes treatment processes processes processes I/O bound (Table can be found processes on page 405 in Starvation No No Possible Possible No Possible textbook) © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Determines which process, among ready processes, is selected next for execution May be based on priority, resource requirements, or the execution characteristics of the process If based on execution characteristics, then important quantities are:  w = time spent in system so far, waiting  e = time spent in execution so far  s = total service time required by the process, including e; generally, this quantity must be estimated or supplied by the user © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.   Specifies the  Two categories: instants in time at  Nonpreemptive which the  Preemptive selection function is exercised © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Nonpreemptive Preemptive Currently running process may be Once a process is in the interrupted and moved to running state, it will ready state by the OS continue until it Decision to preempt may terminates or blocks itself be performed when a for I/O new process arrives, when an interrupt occurs that places a blocked process in the Ready state, or periodically, based on a clock © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. interrupt  Table 9.4 Process Scheduling Example © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  0 5 10 15 20 A First-Come-First B Served (FCFS) C D E A Round-Robin B (RR), q = 1 C D E A Round-Robin B (RR), q = 4 C D E A Shortest Process B Next (SPN) C D E A Shortest Remaining B Time (SRT) C D E A Highest Response B Ratio Next (HRRN) C D E A Feedback B q=1 C D E A Feedback B i q=2 C D E 0 5 10 15 20 Figure 9.5 A Comparison of Scheduling Policies © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Process A B C D E Arrival Time 0 2 4 6 8 Service Time (Ts) 3 6 4 5 2 Mean FCFS Finish Time 3 9 13 18 20 Turnaround Time (Tr) 3 7 9 12 12 8.60 Tr/Ts 1.00 1.17 2.25 2.40 6.00 2.56 Finish Time 4 RR q = 1 18 17 20 15 Table 9.5 Turnaround Time (Tr) 4 16 13 14 7 10.80 Tr/Ts 1.33 2.67 3.25 2.80 3.50 2.71 Finish Time 3 RR q = 4 17 11 20 19 A Comparison Turnaround Time (Tr) 3 15 7 14 11 10.00 Tr/Ts 1.00 2.5 1.75 2.80 5.50 2.71 of Scheduling SPN Finish Time Turnaround Time (Tr) 3 3 9 7 15 11 20 14 11 3 7.60 Policies Tr/Ts 1.00 1.17 2.75 2.80 1.50 1.84 SRT Finish Time 3 15 8 20 10 Turnaround Time (Tr) 3 13 4 14 2 7.20 Tr/Ts 1.00 2.17 1.00 2.80 1.00 1.59 HRRN Finish Time 3 9 13 20 15 Turnaround Time (Tr) 3 7 9 14 7 8.00 Tr/Ts 1.00 1.17 2.25 2.80 3.5 2.14 FB q = 1 Finish Time 4 20 16 19 11 Turnaround Time (Tr) 4 18 12 13 3 10.00 Tr/Ts 1.33 3.00 3.00 2.60 1.5 2.29 FB q = 2i Finish Time 4 17 18 20 14 Turnaround Time (Tr) 4 15 14 14 6 10.60 (Table is on page 408 in textbook) Tr/Ts 1.33 2.50 3.50 2.80 3.00 2.63 © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Simplest scheduling policy Performs much better for long Also known as first-in-first-out processes than short ones (FIFO) or a strict queuing scheme Tends to favor processor- bound processes over I/O- As each process becomes bound processes ready, it joins the ready queue When the currently running process ceases to execute, the process that has been in the ready queue the longest is selected for running © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Uses preemption based on a Particularly effective in a clock general-purpose time-sharing system or transaction Also known as time slicing processing system because each process is given a slice of time before being One drawback is its relative preempted treatment of processor-bound and I/O-bound processes Principal design issue is the length of the time quantum, or slice, to be used © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Time Process allocated Interaction time quantum complete Response time q-s s Quantum q (a) Time quantum greater than typical interaction Process allocated Process Process allocated Interaction time quantum preempted time quantum complete q Other processes run s (b) Time quantum less than typical interaction Figure 9.6 Effect of Size of Preemption Time Quantum © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Time-out Ready Queue Admit Dispatch Release Processor Auxiliary Queue I/O 1 I/O 1 Wait Occurs I/O 1 Queue I/O 2 I/O 2 Wait Occurs I/O 2 Queue I/O n I/O n Wait Occurs I/O n Queue Figure 9.7 Queuing Diagram for Virtual Round-Robin Scheduler © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Nonpreemptive policy in which One difficulty is the need to the process with the shortest know, or at least estimate, the expected processing time is required processing time of selected next each process A short process will jump to the If the programmer’s estimate is head of the queue substantially under the actual running time, the system may Possibility of starvation for longer abort the job processes © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Preemptive version of SPN Should give Scheduler always chooses the superior process that has the shortest turnaround time expected remaining processing performance to time SPN because a short job is given Risk of starvation of longer immediate processes preference to a running longer job © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Chooses next process While shorter jobs are with the greatest ratio favored, aging without service increases the Attractive because it ratio so that a longer accounts for the age of process will eventually the process get past competing shorter jobs © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  RQ0 Release Admit Processor RQ1 Release Processor RQn Release Processor Figure 9.10 Feedback Scheduling © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Performance Comparison Any scheduling discipline that chooses the next item to be served independent of service time obeys the relationship: © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Table 9.6 Formulas for Single- Server Queues with Two Priority Categories © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  100 FCFS Normalized turnaround time 10 HRRN FB RR (q = 1) SRT RR (q = 1) SPN SPN HRRN FB FCFS SRT 1 0 10 20 30 40 50 60 70 80 90 100 Percentile of time required Figure 9.14 Simulation Results for Normalized Turnaround Time © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  RR 10 (q = 1) FB SPN 9 8 HRRN 7 6 Wait time 5 FCFS 4 FCFS 3 RR (q = 1) 2 HRRN SPN 1 SRT FB 0 0 10 20 30 40 50 60 70 80 90 100 Percentile of time required Figure 9.15 Simulation Results for Waiting Time © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Fair-Share Scheduling Scheduling decisions based on the process sets Each user is assigned a share of the processor Objective is to monitor usage to give fewer resources to users who have had more than their fair share and more to those who have had less than their fair share © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Fair Share Scheduler (FFS) The following formulas apply for process j in group k : CPUj(i – 1) CPUj(i) = 2 GCPUk(i - 1) GCPUk(i) = 2 CPUj(i) GCPUk(i) Pj(i) = Basej + 2 + 4 x Wk where CPUj(i) = measure of processor utilization by process j through interval i, GCPUk(i) = measure of processor utilization of group k through interval i, Pj(i) = priority of process j at beginning of interval i; lower values equal higher priorities, Basej = base priority of process j, and Wk = weighting assigned to group k, with the constraint that and 0 < W k < 1 and ∑ W k = 1. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Traditional UNIX Scheduling Used in both SVR3 and 4.3 BSD UNIX These systems are primarily targeted at the time-sharing interactive environment Designed to provide good response time for interactive users while ensuring that low-priority background jobs do not starve Employs multilevel feedback using round robin within each of the priority queues Makes use of one-second preemption Priority is based on process type and execution history © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Scheduling Formula © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Bands Swapper Used to optimize access to block devices and to allow Block I/O the operating system to device control respond quickly to system calls File manipulation In decreasing order of priority, the bands are: Character I/O device control User processes © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved. © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.  Summary Types of processor Scheduling scheduling Long-term scheduling algorithms Medium-term Short-term scheduling scheduling criteria Short-term The use of priorities scheduling Alternative scheduling policies Traditional UNIX Performance scheduling comparison Fair-share scheduling © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.