CPU Scheduling: Algorithms, Criteria, and Evaluation

Chapter 5 CPU Scheduling Multiprogramming Objective Maximize CPU Utilization Maximize I/O Resource Utilization Fairly Allocate Memory Usage CPU-I/O Burst Cycle CPU-Bound Program o Long CPU Bursts o Few, Short I/O Bursts I/O-Bound Program o Few, Short CPU Bursts o Many I/O Bursts CPU Scheduler Short-Term Scheduler STS: selects PCB, i.e., process for assignment to the CPU, i.e., change of state Ready Queue  CPU Ready Queue contains the PCB’s of the Processes All PCB’s in the Ready Queue represent Processes waiting to run on the CPU Queues may be implemented as FIFO Queues Priority Queues Unordered Link Lists Any other Data Structure required by the operational criteria PCB’s normally reside in Memory but may be swapped out to disk by the Medium-Term Scheduler Preemptive Scheduling Scheduling Decisions Process Changes State as follows 1. Running State  Wait State I/O Request Invocation of wait( ) 2. Running State  Ready State Interrupt Occurs 3. Wait State  Ready State Completion of I/O 4. Running State  Termination Preemptive Scheduling Non-Preemptive Scheduling Allows only the following changes of state 1. Running State  Wait State I/O Request Invocation of wait( ) 2. Running State  Termination I.e., once the process gets the CPU, it keeps until the process requests a wait state or terminates Preemptive Scheduling Impacts Shared Data o Process A is updating data o Process A is preempted by Process B o Process B uses data which is in an inconsistent state Kernel o Is busy on behalf of Process A, e.g., changing kernel data for Process A, e.g., modifying I/O Queues o Process A is preempted by Device Driver o Device Driver uses inconsistent data due to corrupted I/O Queue data Unix before initiating a Context Switch o Waits for a System Call to Complete o An I/O block to Occur Not a good solution for real-time systems nor multiprocessing systems Interrupts can occur at any time cannot be ignored by the kernel must be guarded from simultaneous usage Interrupt Processing Routine Disable Interrupt Stream, i.e., Place subsequent “Disabled” Interrupts on a Stack or in a Queue Process the Current Interrupt Enable Interrupt Stream, i.e., check the Interrupt Data Structure for Suspended Interrupt Notifications Continue Processing Interrrupts Dispatcher Effects the change of state from Ready to Running, i.e., Ready Queue  CPU Performs Context Switch o In Kernel Mode  Copy Running Process Information  PCB  Copy Selected Process PCB Information  CPU o In User Mode  Starts Selected Program Running Dispatch Latency o Time Interval required to perform Context Switch Scheduling Criteria CPU Utilization o 40% - 90% Throughput o number of processes that reach completion during a unit of time Turnaround Time o time interval from submission time to completion time Wait Time o total time waiting in the ready queue Response Time o time interval from job submission until the job first starts responding Goal o Maximize  CPU Utilization  Throughput o Minimize  Turnaround Time  Wait Time  Response Time Implementation o Optimize Average Measure o Optimize Maximum or Minimum Values o Minimize the Maximum Response Time o Minimize the Variance in the Response Time (interactive systems) Scheduling Algorithms First-Come, First-Served (FCFS) Scheduling Non-Preemptive Scheduling Algorithm Ready Queue – FIFO queue Linked List of PCB Blocks Average Waiting Time – not minimal, varies considerable – depends upon arrival times e.g., one CPU-Bound Process & many I/O Bound Processes  Convoy effect o CPU-Bound Process issues I/O Request  sits in IO Device (Wait) Queue I/O-Bound processes quickly finish I/O Requests  I/O-Bound processes move to Ready Queue  CPU sets idle CPU-Bound Process finally completes I/O Request  CPU-Bound Process moves to Ready Queue, placed in queue after all the I/O-Bound Processes I/O-Bound processes quickly finish I/O Requests  I/O-Bound processes move to Ready Queue CPU-Bound Process regains control of the CPU  I/O-Bound Process sit in Ready Queue  I/O Devices sit idle CPU-Bound Process o Long CPU Bursts o Short I/O Bursts I/O-Bound Processes o Short CPU Bursts o Long I/O Bursts Shortest Job First Scheduling or Shortest-Next-CPU-Burst Algorithm the process with the shortest length of the next CPU Burst is chosen from the Ready Queue optimal scheduling algorithm  minimum average waiting time batch processing – user estimate of length of job-completion time low estimate  faster completion time too low an estimate  time-limit-completion interrupt and job termination penalty short-term scheduler has no way to estimate the length of the next CPU Burst predicting the shortest next CPU Burst o exponential average of previous (recorded) CPU Bursts o : length of the nth CPU burst o : predicted value of the next CPU burst o for o represents the most recent factual information o stores the accumulated past history o controls the relative weight of recent and past history o If ( ) then hence recent history has no effect o If ( ) then hence only the most recent CPU burst matters o ( )  recent history and past history are equally valued, i.e., weighted o Initial value defined as a constant or an overall system average o yields a weighted average with a exponentially decaying history, i.e., more recent events are given greater weight than more distant events, i.e., where = 1 or heuristic estimation of past CPU bursts i.e., Preemptive SJF – Shortest-Remaining-Time-First Scheduling o new job has shorter next CPU burst estimate than the remainder of the current job’s current CPU burst Non-preemptive SJF o currently running process finishes it’s CPU burst regardless of the next CPU burst estimate of the new job See Silberschatz Slides & Textbook for a discussion of Priority Scheduling Round-Robin Scheduling Multilevel Queue Scheduling Multilevel Feedback Queue Scheduling Thread Scheduling Multiprocessor Scheduling Interactive o time slicing quantum o dynamically alter priorities o 60 priority levels o multilevel feedback queue o quantum length depends upon the queue  higher priority  smaller time slice  lower priority  larger priority o CPU-bound processes  lower priorities o I/O-bound processes  higher priorities o processes using a Window utility are given a high priority Time-Sharing ▬ the default class for a process o time slicing quantum o dynamically alter priorities o 60 priority levels o multilevel feedback queue o quantum length depends upon the queue  higher priority  smaller time slice  lower priority  larger priority o CPU-bound processes  lower priorities o I/O-bound processes  higher priorities See Silberfschatz text page 207 for a fragment of the table. Algorithm for promoting and demoting process threads via priorities and timequantum lengths; priorities and timequantum lengths have an inverse relationship; thread uses its entire time-quantum  priority is lowered thread returning from a wait queue  priority raised to between 50-59 Fair-Share CPU-bound o uses CPU Shares to make scheduling decisions o CPU Shares indicate an entitlement to available CPU resources process threads  low priority o CPU Shares are allocated to a set of processes, i.e., a project I/O-bound System process threads o kernel threads, e.g., scheduler, page daemon  high priority o priority of a system thread does not change o user threads running in kernel mode are not in the system class Real-Time o real-time threads have a guaranteed response w/in a bounded time period Interrupt Threads – 10 threads reserved for interrupt processing Highest Priority Highest Priority Fixed-Priority o 60 priority levels o priorities are not dynamically altered Dispatch Table used by both the Interactive and the Time-Sharing Classes Scheduler converts class-specific priorities into global priorities selects thread with highest global priority to run Selected thread runs until it blocks uses its time slice is preempted by a higher priority thread terminates If there are multiple threads with the same global priority the scheduler uses a round-robin queue Highest Priority Lowest Priority Solaris Scheduling Priority-based Thread Scheduling ▬ each process belongs to one of the following classes: Windows XP Scheduling uses a priority-based, preemptive scheduling algorithm which schedules threads kernel unit called the dispatcher performs the scheduling activities Selected thread runs until it blocks uses its time slice is preempted by a higher priority thread terminates 32 priority levels, divided into two classes o Variable Class – priorities between 1-15 o Real-Time Class – priorities between 16-31 o priority 0 thread – memory management 32 queues – one for each priority level dispatcher traverses the queues (highlow) until it locates an executable thread no thread is ready to execute  dispatcher launches a special idle thread priority of a thread belonging Win32 API Priority Classes base priorities to this class does not change REALTIME_PRIORITY_CLASS 24 HIGH_PRIORITY_CLASS 13 Variable-Priority Classes ABOVE_NORMAL_PRIORITY_CLASS 10 priority of a thread belonging any of these NORMAL_PRIORITY_CLASS 8 classes can change; it depends upon the priority class to which a tread belongs BELOW_NORMAL_PRIORITY_CLASS 6 relative priority within that class IDLE_PRIORITY_CLASS 4 Win32 API Relative Priorities TIME_CRITICAL HIGHEST ABOVE_NORMAL NORMAL BELOW_NORMAL LOWEST IDLE Processes typically are members of the NORMAL_PRIORITY_CLASS unless parent of process was a member of the IDLE_PRIORITY_CLASS process was assigned to another class upon creation The initial priority of a thread is typically the base priority of the process to which it belongs Priority Classes RealTime 31 High Normal 15 AboveNormal 15 Highest 26 15 12 Above-Normal Normal 25 14 24 13 Below-Normal 23 Lowest Idle Time-Critical Relative Priorities 15 BelowNormal 15 IdlePriority 15 10 8 6 11 9 7 5 10 8 6 4 12 9 7 5 3 22 11 8 6 4 2 16 1 1 1 1 1 variable-class thread exhausts time-quantum  priority is lowered; limited by base priority variable-priority thread released from wait queue  priority is raised o amount of boost depends upon type of wait queue  wait for keyboard I/O  big boost  wait for disk I/O  small boost Window threads receive an additional boost to enhance response time Results 1. yields good response time for windows & mice 2. enables I/O-bound threads to keep the I/O devices busy 3. CPU-bound threads have their CPU consumption limited, but they are permitted to use the spare CPU cycles in the background used by many O/S, Unix, et. al. NORMAL_PRIORITY_CLASS Special Subclasses Foreground Process -- selected on the screen Background Process – currently not selected on the screen Special Scheduling Rule Process is selected to be in the foreground  increase time-quantum by some factor, e.g., three, which allows the process to run three times longer before the time-sharing preemption occurs Linux Scheduling Traditional Unix Scheduling Algorithm Deficiencies o does not provide adequate support for Symmetric Multiprocessing Systems (SMP) o does not scale well as the task load (number of tasks) increases Version 2.5 Scheduler o runs in O(1) time, i.e., constant amount of time regardless of the task o provides increased support for SMP  Processor Affinity  Load Balancing o provides support for Interactive tasks, e.g., fairness o preemptive, priority-based system  priority ranges real-time range & nice range map  Real-Time Range 0-99 into a global priority range  Nice Range – nice value 100-140  lower values  higher priorities  higher priorities  larger time-quanta, i.e., quantum’s  lower priorities  smaller time-quanta See Silberschatz page 212, figure 5.15 o Runqueue Data Structure – list of all runable tasks (maintained by the kernel)  Active Priority Queue – list of all tasks with time remaining in their time-slices  Expired Priority Queue – list of all tasks that have exhausted their time-slices  hence, not eligible to run until all other tasks have exhausted their time-slices  both queues independently maintain a list of tasks indexed by priority  tasks with equal priority in either queue are maintained as a linked list, First-Come, First-Served o Scheduler selects a task with highest priority from the Active Priority Queue o Active Priority Queue == Empty  the two queues undergo a name switch, i.e.,  Active Priority Queue becomes the Expired Priority Queue  Expired Priority Queue becomes the Active Priority Queue o SMP Architecture – each processor  maintains its own Runqueue Structure and schedules itself independently  schedules the highest priority task from its own Runqueue Structures o Real-Time Scheduling – Pthreads (POSIX.1b)  tasks are assigned static priorities o Nice Scheduling  dynamic priorities are based on the nice value 5  length of sleep (waiting) time determines the dynamic priority adjustment  increased sleep time  increase in priority, i.e., -1 to -5  decreased sleep time  CPU-bound  decrease in priority, i.e., +1 to +5 Algorithm Evaluation Establishing algorithm criteria o maximize CPU utilization under a constrained maximum response time o maximizing throughput such that the turnaround time is linearly proportional to the total execution time o &/or other criteria relevant to the performance of the projected O/S Analytic Evaluation – mathematical modeling o Deterministic Modeling  Predetermined Workload  Determine the performance of each candidate algorithm against the workload  Gantt Charts – time distribution of events  In situations where the workload is constant over time, and where the workloads tested are realistic, this analysis yields a first good view of the algorithms performance o Queueing Models  Workload varies over time there is no static set of processes or times to use for deterministic modeling Queueing-Network Analysis Computer System  Network of Servers Each server has a queue of waiting processes CPU server with ready queue I/O Devices with the device queues etc Determine the distribution of CPU-bursts and I/O-bursts Measure Approximate Estimate Yields Exponential distribution, i.e., probability, of a particular CPU-burst Distribution of the arrival times, i.e., when processes arrive in the system Arrival Rates & Service Rates are used to compute the Average Throughput Utilization Waiting times Average Queue Lenghts etc for most scheduling algorithms Quit often leads to intractable mathematics and thus is not often used in practice Arrival Rates & Service Rates  Compute utilization, average queue length, average waiting time o Simulations  Model of an O/S (implemented to run on a computer)  Data Sources  Random Numbers  Mathematical Distributions  Uniform  Exponential  Poisson  Empirically  Trace tapes – monitor a real system, record the sequence of actual events  Major expenditure to undertake an empirical study, e.g., equipment, people o Implementation  Cost  Users Adverse Adjustments to a system under modification  beta-versions  gamma-versions