Chapter 9 Scheduling(Uniprocessor)
这些调度表明了执行这些功能的相对时间比例
- Long-term Scheduling： 决定是否把进程添加到the pool of processes to be executed
- Medium-term Scheduling: 决定是否把进程添加到the number of processes that are partially or fully in main memory
- Short-term Scheduling: 决定下次执行那个就绪进程（ available process)
- I/O Scheduling
Short-Term Scheduling
dispatcher
导致当前进程阻塞或抢占当前运行进程的事件发生时，调用Short-Term Scheduling
•Clock interrupts
•I/O interrupts
•Operating system calls
•Signals (e.g., semaphores)
标准:performance
Selection Function
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
Decision Mode
preemptive/non-preemptive
•Turnaround Time (Tr) is service time + wait time
•Normalized Turnaround Time (Tr / Ts) – ratio to actual service time
–1.0 means no waiting
–2.0 means waiting as long as it took to execute
–Bigger values indicate additional wait time with respect to execution time
FCFS
非抢占
first come first served
•When the current process finishes, the longest waiting process in the Ready queue is selected
•Performs much better for long processes than short ones
•Tends to favor processor-bound processes over I/O-bound processes
Round Robin
抢占
Uses preemption based on a clock
SPN
Shortest Process Next
非抢占
下次选择预计处理时间最短的进程， 短进程会跳过长作业，跳到队列头
风险：只要持续不断提供更短的进程，长进程就会饥饿
SRT
Shortest Remaining Time
抢占
•Preemptive version of SPN
选择预期剩余时间最短的进程
性能比SPN好，相对于正在进行的长作业，短作业可被立即选择并运行
HRRN
非抢占
Highest Response Ratio Next
•Chooses next process with the greatest ratio
feedback
