Basic Concepts
CPU –I/O Burst Cycle
• Process execution consists of acycleof CPU execution and I/O wait. • Process execution begins with aCPU burst, followed by anI/O burst, then another CPU burst ... etc• The duration of these CPU bursts has been measured.
• An I/O-bound program would typically have many short CPU bursts, A CPU-bound program might have a few very long CPU bursts
• this can help to select an appropriate CPU-scheduling algorithm.
Types of Processes
I/O bound
• Has small bursts of CPU activity and then waits for I/O (eg. Word processor)• Affects user interaction (we want these processes to have the highest priority)CPU bound
• Hardly any I/O, mostly CPU activity (eg. gcc, scientific modeling, 3D rendering, etc.) • Useful to have long CPU bursts • Could do with lower prioritiesCPU Scheduler
The CPU scheduleris the mechanism to select which process has to be executed next and allocates the CPU to that process. Schedulers are responsible for transferring a process from one state to the other.3 types of schedulers(recall L1):Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler When timer interrupt occurs or when running process is blocked on I/O,scheduler runScheduler picks another process from the ready queue Performs a context switchPreemptive scheduling
抢占式调度The system may stop the execution of the running process and after that, the context switch may provide the processor to another process. The interrupted process is put back into the ready queue and will be scheduled sometime in future, according to the scheduling policy.
Non-preemptive scheduling
When a process is assigned to the processor, it is allowed to execute to its completion, that is, a system cannot take away the processor from the process until it exits. Any other process which enters the queue has to wait until the current finishes its CPU cycle.
典型process的状态图
Schedulers
-Decide which process should run next
CPU scheduling takes place on 4 circumstances:
1. When the process changes state fromRunningtoReadyex: when an interrupt occurs . 2. Changes state fromRunningtoWaitingex: as result of I/O request orwait().3. Changes state fromWaitingtoReadyex: at completion of I/O. 4. ProcessTerminates.• Scheduling under 2 and 4 isnonpreemptive -a new process must be selected • Other scheduling ispreemptive-either continue running the current process or select a different one
Dispatcher
Dispatcher modulegives 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 programDispatch latency（调度延时）– time it takes for the dispatcher to stop one process and start another running. Dispatcher is invoked during every process switch; hence it should be as fast as possibleScheduling Criteria
•Max CPU utilization– keep the CPU as busy as possible
•Max Throughput（吞吐量）– complete as many processes as possible per unit time •Fairness- give each process a fair share of CPU •Min Waiting time– process should not wait long in the ready queue •Min Response time– CPU should respond immediately
Scheduling Algorithms
术语
Arrival Time (AT):Time at which the process arrives in the ready queue.Completion Time:Time at which process completes its execution.Burst Time:Time required by a process for CPU execution.Turnaround Time (TT):the total amount of time spent by the process from coming in the ready state for the first time to its completion.Turnaround time = Exit time - Arrival timeWaiting Time (WT):The total time spent by the process/thread in the ready state waiting for CPU.Waiting Time = Turnaround Time – Burst TimeResponse time:Time at which the process gets the CPU for the first time.
First-Come, First-Served (FCFS) Scheduling
Processes are executed on first come, first servebasis.
Poor in performance as average wait time is high Waiting time forP1= 0;P2= 24;P3= 27Average waiting time: (0 + 24 + 27)/3 = 17
Shortest-Job-First (SJF) Scheduling
Schedule process with the shortest burst time without preemption •Advantages– Minimizes average wait time and average response time •Disadvantages–Not practical: difficult to predict burst time • Learning to predict future – May starve long jobsAverage waiting time= (0+3+9+16) / 4 = 7
Thereal difficulty:knowing the length of the next CPU request - withshort-term scheduling, there isno way to know the length of the next CPU burst. SJF cannot be implemented at the level of the short-term CPU scheduling
Determining Length of Next CPU Burst
Estimate it using lengths of past bursts: next = average of all past bursts.
Exponential averaging: next = average of (past estimate + past actual) Lettn= actual length of thenthburst;Tn+1= predicted value for the next CPU burst;a= weighing factor,0 ≤a≤ 1The estimate of the next CPU burst period is:
Commonly,aset to½
- Ifa=0, thenrecent history has no effffect- Ifa=1, then only themost recent CPU bursts matter
Shortest Remaining Time First (SRTF) Scheduling
Average waiting time= [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 26/4 = 6.5 msec
Priority Scheduling
Each process is assigned apriority(just a number) The CPU is allocated to the process with the highest priority (smallest integer) Priorities may be:Internal prioritiesbased on criteria within OS.Ex: memory needs.External prioritiesbased on criteria outside OS.Ex: assigned byadministratorsPROBLEM:Starvation– low priority processes may never executeSOLUTION:Aging– as time progresses increase the priority of the process Example: do priority = priority – 1 every 15 minutesAverage waiting time= = (0 + 1 + 6 + 16 + 18) / 5 = 8.2
Round Robin(RR) Scheduling
Each process gets a small unit of CPU time (time quantumortime-slice), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queueReady queue is treated as a circularqueueIf there arenprocesses in the ready queue and the time quantum isq, then each process gets1/nof the CPU time in chunks of at mostqtime units at once. No process waits more than(n-1)qtime units.Performanceq large RR scheduling = FCFS schedulingq small q must be large with respect to context switch, otherwise overhead is too highe.g.
Multiple-Level Queues Scheduling
• Ready queue is partitioned into separate queues; e.g., two queues containing oforeground(interactive)processes. May have externally defined priority over background processes obackground(batch)processesProcess permanently associated to a given queue;no move to a different queueThere are two types of scheduling in multi-level queue scheduling: • Scheduling among the queues. • Scheduling between the processes of the selected queue. Must schedule among the queues too (not just processes):Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.Time slice– each queue gets a certain amount of CPU time which it can schedule amongst its processes; 80% to foreground in RR, and 20% to background in FCFS The various categories of processes can be: • Interactive processes • Non-interactive processes • CPU-bound processes • I/O-bound processes • Foreground processes • Background processesMultilevel Feedback Queue Scheduling
•Multilevel feedback queues-automatically place processes into priority levelsbased on their CPU burst behavior.• I/O-intensive processes will end up onhigher priority queuesand CPU-intensive processes will end up onlow priority queues. A processcan move between the various queues- aging can be implemented this way. Amultilevel feedback queueusestwo basic rules: 1. A new process gets placed in the highest priority queue. 2. If a process does not finish its quantum, then it will stay at the same priority level otherwise it moves to the next lower priority level Multilevel-feedback-queue scheduler defined by the following parameters:– number of queues – scheduling algorithms for each queue – method used to determine when to upgrade a process – method used to determine when to demote a process – method used to determine which queue a process will enter when that process needs service Three queues:Q0– RR with time quantum 8 milliseconds▪ Highest priority. Preempts Q1 and Q2 proc’sQ1– RR time quantum 16 milliseconds▪ Medium priority. Preempts processes in Q2Q2– FCFS▪ Lowest priority A new job enters queue Q0 -> If it does not finish in 8 milliseconds, job is moved to queue Q1 and receives 16 additional milliseconds -> If it still does not complete, it is preempted and moved to queue Q2如果觉得《CPT104操作系统笔记（scheduling I）》对你有帮助，请点赞、收藏，并留下你的观点哦！
