Process Scheduling
调度指标
- CPU 利用率
Processor Utilisation = (Execution Time) / (Total Time)
- 系统吞吐量
Throughput = Jobs per Unit time
- 等待时间
Waiting Time = Time doing nothing in a queue
- 响应时间
Response Time = (Time job is first scheduled on cpu) - (Time job was submitted)
- 突发时间
Burst Time
也称 CPU 执行时间，一个进程执行完毕所需的时间 (Time job finishes)
- 周转时间
Turnaround Time = (Time job finishes) - (Time job was submitted)
进程提交到完成所经历的总时间，包括执行时间和等待时间等。
调度算法
非抢占式
Non-preemptive
一旦一个进程获得 CPU 资源并开始执行，它将一直执行，直到完成或主动释放 CPU资源，其他就绪状态的进程才能获得执行机会。
先来先服务
FCFS : First Come First Served
只考虑进程进入就绪队列的先后，而不考虑下一个 CPU 周期的长短及其他因素。这种算法公平简单，但性能不大好。
短任务优先
SJF: Shortest Job First
在吞吐量、等待时间和响应性能方面被证明是最优 (optimal) 的调度算法，但不具备公平性。
SJF 倾向于优先调度短任务，长任务可能会无限期地推迟调度，即使它们在就绪队列中等待了相当长的时间。
- 当等待时间给进程推进和响应带来明显影响称为进程饥饿 (starvation)，当饥饿到一定程度的进程在等待到即使完成也无实际意义的时候称为饥饿死亡。
高响应比优先
HRN: Highest Response Ratio Next
到达时间5，现在6，所以实际等待了1
抢占式
Preemptive
系统通过中断机制等来强制终止正在运行的进程或线程，允许高优先级的任务可以打断正在执行的低优先级任务，将 CPU 资源分配给具有更高优先级的进程或线程，保证高优先级的任务及时响应并获得足够的 CPU 时间，而不会被低优先级的任务阻塞。
循环调度
RR: Round Robin：一种先来先服务的抢占式版本
- 每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N（内部服务器个数），然后重新开始循环。
- 它通过将一个固定的时间片 (quantum) 按照循环顺序分配给每个进程。一旦一个进程消耗完其整个 quantum，调度程序会中断它并切换到队列中的下一个进程，给它执行的机会。Quantum 的长度会影响系统的性能，因为较短的 quantum 可能会增加上下文切换和开销的数量，而较长的 quantum 可能会增加交互式进程的响应时间。因此，应根据系统的具体要求仔细选择 quantum 大小。
the order of execution using RR with a quantum of 1
优先权法
Priority Scheduling
进程被分配一个表示其调度优先级的数值。用户可以指定任务相对于其他任务的优先级。调度程序总是首先选择具有最高优先级的进程。
调度环境
Scheduling Environments
多处理器系统
Multiprocessor Systems
使用更多处理器似乎是提高整个系统吞吐量的一种明显方法，但是加倍处理器通常并不能使性能翻倍，反而调度问题更加复杂，总线争用、I/O、共享内存、操作系统代码和维护缓存一致性等因素可能导致性能滞后，并且没有适用于所有情况的单一最佳解决方案。
MMU：Memory Management Unit，存储器管理单元
队列理论
Queuing Theory
一种数学模型和分析工具，用于研究和分析在操作系统中出现的队列现象和性能问题。它用于评估和优化系统中的各种资源分配和调度策略。
- 到达模式 (Arrival Pattern)：描述任务是以何种模式到达系统
- 例如泊松分布常被用来描述任务到达系统的时间间隔和频率
- 队列策略 (Queuing Policy)：决定任务在系统中排队等待执行的方式，比如 FIFO、SJF 等
- 调度策略 (Dispatch Policy)：决定从队列中选择任务并将其分派给可用资源的方式
分布系统
Distributed System
由多台计算机系统组成，通过局域网连接在一起。分布式操作系统监控并分享或平衡每个处理节点上的负载。
- RPC (Remote Procedure Call) 是一种远程过程调用的通信协议和编程模型。它允许一个计算机程序（称为客户端）调用另一个计算机程序或服务（称为服务器）上的函数或方法。
实时系统
Real Time Systems，一种旨在处理具有时间约束任务的系统。
- 硬实时系统 (Hard Real-Time Systems)：比如飞行控制系统、医疗设备等。
- 软实时系统 (Soft Real-Time Systems)：对任务的截止时间要求相对较宽松。常见于多媒体应用、网络通信、实时数据处理等领域。
最早期限优先
EDF: Earliest Deadline First
基于任务的截止时间来确定任务的优先级顺序
最低松弛度优先
LLA: Least Laxity Algorithm
弹性程度是指任务剩余时间与截止时间之差，即弹性程度越小的任务具有更高的优先级。
- 如果一个进程需要 200msec 且需在 250msec 内完成，那么它的松弛度是 50msec。