Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 331CPU SchedulingCPU SchedulingScheduling the processor among all ready processesThe goal is to achieve: High processor utilizationHigh throughputnumber of processes completed per of unit timeLow response timetime elapsed from the submission of a request until the first response is produced1Classification of Scheduling ActivityClassification of Scheduling ActivityLong-term: which process to admit?Medium-term: which process to swap in or out?Short-term: which ready process to execute next?1Queuing Diagram for SchedulingQueuing Diagram for Scheduling1Long-Term SchedulingLong-Term SchedulingDetermines which programs are admitted to the system for processingControls the degree of multiprogrammingAttempts to keep a balanced mix of processor-bound and I/O-bound processesCPU usageSystem performance1Medium-Term SchedulingMedium-Term SchedulingMakes swapping decisions based on the current degree of multiprogrammingControls which remains resident in memory and which jobs must be swapped out to reduce degree of multiprogramming1Short-Term SchedulingShort-Term SchedulingSelects from among ready processes in memory which one is to execute nextThe selected process is allocated the CPUIt is invoked on events that may lead to choose another process for execution:Clock interruptsI/O interruptsOperating system calls and trapsSignals1Characterization of Scheduling PoliciesCharacterization of Scheduling PoliciesThe selection function determines which ready process is selected next for executionThe decision mode specifies the instants in time the selection function is exercisedNonpreemptiveOnce a process is in the running state, it will continue until it terminates or blocks for an I/OPreemptiveCurrently running process may be interrupted and moved to the Ready state by the OSPrevents one process from monopolizing the processor1Short-Term SchedulerShort-Term SchedulerDispatcherDispatcherThe dispatcher is the module that gives control of the CPU to the process selected by the short-term schedulerThe functions of the dispatcher include:Switching contextSwitching to user modeJumping to the location in the user program to restart executionThe dispatch latency must be minimal1The CPU-I/O CycleThe CPU-I/O CycleProcesses require alternate use of processor and I/O in a repetitive fashionEach cycle consist of a CPU burst followed by an I/O burst A process terminates on a CPU burstCPU-bound processes have longer CPU bursts than I/O-bound processes1Short-Tem Scheduling CriteriaShort-Tem Scheduling CriteriaUser-oriented criteriaResponse Time: Elapsed time between the submission of a request and the receipt of a responseTurnaround Time: Elapsed time between the submission of a process to its completionSystem-oriented criteriaProcessor utilizationThroughput: number of process completed per unit timefairness1Scheduling AlgorithmsScheduling AlgorithmsFirst-Come, First-Served SchedulingShortest-Job-First SchedulingAlso referred to asShortest Process NextPriority SchedulingRound-Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling1Process Mix ExampleProcess Mix ExampleProcessArrivalTimeServiceTime123450246836452Service time = total processor time needed in one (CPU-I/O) cycleJobs with long service time are CPU-bound jobs and are referredto as “long jobs”1First Come First Served (FCFS)First Come First Served (FCFS)Selection function: the process that has been waiting the longest in the ready queue (hence, FCFS)Decision mode: non-preemptivea process runs until it blocks for an I/O1FCFS drawbacksFCFS drawbacksFavors CPU-bound processesA CPU-bound process monopolizes the processorI/O-bound processes have to wait until completion of CPU-bound process I/O-bound processes may have to wait even after their I/Os are completed (poor device utilization)Better I/O device utilization could be achieved if I/O bound processes had higher priority1Shortest Job First (Shortest Job First (Shortest Process NextShortest Process Next))Selection function: the process with the shortest expected CPU burst timeI/O-bound processes will be selected firstDecision mode: non-preemptiveThe required processing time, i.e., the CPU burst time, must be estimated for each process1SJF / SPN CritiqueSJF / SPN CritiquePossibility of starvation for longer processes Lack of preemption is not suitable in a time sharing environmentSJF/SPN implicitly incorporates prioritiesShortest jobs are given preferencesCPU bound process have lower priority, but a process doing no I/O could still monopolize the CPU if it is the first to enter the system1Is SJF/SPN optimal?Is SJF/SPN optimal?If the metric is turnaround time (response time), is SJF or FCFS better?For FCFS, resp_time=(3+9+13+18+20)/5 = ?Note that Rfcfs = 3+(3+6)+(3+6+4)+…. = ?For SJF, resp_time=(3+9+11+15+20)/5 = ?Note that Rfcfs = 3+(3+6)+(3+6+4)+…. = ?Which one is smaller? Is this always the case?1Is SJF/SPN optimal?Is SJF/SPN optimal?Take each scheduling discipline, they both choose the same subset of jobs (first k jobs).At some point, each discipline chooses a different job (FCFS chooses k1 SJF chooses k2)Rfcfs=nR1+(n-1)R2+…+(n-k1)Rk1+….+(n-k2) Rk2+….+RnRsjf=nR1+(n-1)R2+…+(n-k2)Rk2+….+(n-k1) Rk1+….+RnWhich one is smaller? Rfcfs or Rsjf?1PrioritiesPrioritiesImplemented by having multiple ready queues to represent each level of priorityScheduler the process of a higher priority over one of lower priorityLower-priority may suffer starvationTo alleviate starvation allow dynamic prioritiesThe priority of a process changes based on its age or execution history1Selection function: same as FCFSDecision mode: preemptivea process is allowed to run until the time slice period (quantum, typically from 10 to 100 ms) has expireda clock interrupt occurs and the running process is put on the ready queue Round-RobinRound-Robin1RR Time QuantumRR Time QuantumQuantum must be substantially larger than the time required to handle the clock interrupt
View Full Document