Principles of Operating Systems - CPU Scheduling 1 ICS 143 - Principles of Operating Systems Lecture 5 - CPU Scheduling Prof. Dmitri V. Kalashnikov dvk (@) ics.uci.edu Slides © Prof. Nalini Venkatasubramanian.Principles of Operating Systems - CPU Scheduling 2 Outline ❚ Scheduling Objectives ❚ Levels of Scheduling ❚ Scheduling Criteria ❚ Scheduling Algorithms ❘ FCFS, Shortest Job First, Priority, Round Robin, Multilevel ❚ Multiple Processor Scheduling ❚ Real-time Scheduling ❚ Algorithm EvaluationPrinciples of Operating Systems - CPU Scheduling 3 Scheduling Objectives ❚ Enforcement of fairness • in allocating resources to processes ❚ Enforcement of priorities ❚ Make best use of available system resources ❚ Give preference to processes holding key resources. ❚ Give preference to processes exhibiting good behavior. ❚ Degrade gracefully under heavy loads.Principles of Operating Systems - CPU Scheduling 4 Program Behavior Issues ❚ I/O boundedness ❘ short burst of CPU before blocking for I/O ❚ CPU boundedness ❘ extensive use of CPU before blocking for I/O ❚ Urgency and Priorities ❚ Frequency of preemption ❚ Process execution time ❚ Time sharing ❘ amount of execution time process has already received.Principles of Operating Systems - CPU Scheduling 5 Basic Concepts ❚ Maximum CPU utilization obtained with multiprogramming. ❚ CPU-I/O Burst Cycle ❘ Process execution consists of a cycle of CPU execution and I/O wait.Principles of Operating Systems - CPU Scheduling 6 CPU Burst DistributionPrinciples of Operating Systems - CPU Scheduling 7 Levels of Scheduling ❚ High Level Scheduling or Job Scheduling ❘ Selects jobs allowed to compete for CPU and other system resources. ❚ Intermediate Level Scheduling or Medium Term Scheduling ❘ Selects which jobs to temporarily suspend/resume to smooth fluctuations in system load. ❚ Low Level (CPU) Scheduling or Dispatching ❘ Selects the ready process that will be assigned the CPU. ❘ Ready Queue contains PCBs of processes.Principles of Operating Systems - CPU Scheduling 8 Levels of Scheduling(cont.)Principles of Operating Systems - CPU Scheduling 9 CPU Scheduler ❚ Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them. ❙ Non-preemptive Scheduling ❘ Once CPU has been allocated to a process, the process keeps the CPU until • Process exits OR • Process switches to waiting state ❙ Preemptive Scheduling ❘ Process can be interrupted and must release the CPU. • Need to coordinate access to shared dataPrinciples of Operating Systems - CPU Scheduling 10 CPU Scheduling Decisions ❚ CPU scheduling decisions may take place when a process: • switches from running state to waiting state • switches from running state to ready state • switches from waiting to ready • terminates ❚ Scheduling under 1 and 4 is non-preemptive. ❚ All other scheduling is preemptive.Principles of Operating Systems - CPU Scheduling 11 CPU scheduling decisions new admitted interrupt I/O or event completion Scheduler dispatch I/O or event wait exit ready running terminated waitingPrinciples of Operating Systems - CPU Scheduling 12 Dispatcher ❚ Dispatcher module gives control of the CPU to the process selected by the short-term scheduler. This involves: • switching context • switching to user mode • jumping to the proper location in the user program to restart that program ❚ Dispatch Latency: ❘ time it takes for the dispatcher to stop one process and start another running. ❘ Dispatcher must be fast.Principles of Operating Systems - CPU Scheduling 13 Scheduling Criteria ❚ CPU Utilization ❘ Keep the CPU and other resources as busy as possible ❚ Throughput ❘ # of processes that complete their execution per time unit. ❚ Turnaround time ❘ amount of time to execute a particular process from its entry time.Principles of Operating Systems - CPU Scheduling 14 Scheduling Criteria (cont.) ❚ Waiting time ❘ amount of time a process has been waiting in the ready queue. ❚ Response Time (in a time-sharing environment) ❘ amount of time it takes from when a request was submitted until the first response is produced, NOT output.Principles of Operating Systems - CPU Scheduling 15 Optimization Criteria ❚ Max CPU Utilization ❚ Max Throughput ❚ Min Turnaround time ❚ Min Waiting time ❚ Min response timePrinciples of Operating Systems - CPU Scheduling 16 First Come First Serve (FCFS) Scheduling ❚ Policy: Process that requests the CPU FIRST is allocated the CPU FIRST. ❙ FCFS is a non-preemptive algorithm. ❚ Implementation - using FIFO queues • incoming process is added to the tail of the queue. • Process selected for execution is taken from head of queue. ❚ Performance metric - Average waiting time in queue. ❚ Gantt Charts are used to visualize schedules.Principles of Operating Systems - CPU Scheduling 17 First-Come, First-Served(FCFS) Scheduling ❚ Example Process Burst TimeP1 24P2 3P3 3❚ Suppose the arrival order for the processes is ❘ P1, P2, P3 ❚ Waiting time ❘ P1 = 0; ❘ P2 = 24; ❘ P3 = 27; ❚ Average waiting time ❘ (0+24+27)/3 = 17 0 24 27 30 P1 P2 P3 Gantt Chart for SchedulePrinciples of Operating Systems - CPU Scheduling 18 FCFS Scheduling (cont.) ❚ Example Process Burst TimeP1 24P2 3P3 3❚ Suppose the arrival order for the processes is ❘ P2, P3, P1 ❚ Waiting time ❘ P1 = 6; P2 = 0; P3 = 3; ❚ Average waiting time ❘ (6+0+3)/3 = 3 , better.. ❚ Convoy Effect: • short process behind long process, e.g. 1 CPU bound process, many I/O bound processes. 0 3 6 30 P1 P2 P3 Gantt Chart for SchedulePrinciples of Operating Systems - CPU Scheduling 19 Shortest-Job-First(SJF) Scheduling ❙ Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time. ❙ Two Schemes: ❘ Scheme 1: Non-preemptive • Once CPU is given to the process it cannot be preempted until it completes its CPU burst. ❘ Scheme 2: Preemptive • If a new CPU process arrives with CPU burst length less than remaining time of current executing