操作系统-处理机管理

1、调度的性能准则:
– （平均）周转时间：作业从提交到完成的时间（用户角度）
周转时间：Ti=Tc-Ts
Tc作业完成时刻；
Ts作业进入系统时刻

平均周转时间：（T1+T2+…+Tn)/n

– （平均）带权周转时间：周转时间 / CPU运行时间（用户角度）
带权周转时间:

平均带权周转时间：

– 吞吐量：单位时间内所完成的作业数
– 处理机利用率：CPU运行时间 / 总时间
– 各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙的作业搭配

调度的类型:
– 作业：又称为”宏观调度”、”高级调度”。从用户工作流程的角度，一次提交的若干个流程。
– 内外存交换：又称为”中级调度”。从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。
– 进程：又称为”微观调度”
、
“低级调度”。从CPU资源
的角度，执行的单位。时间上通常是毫秒。因为执行频
繁，要求在实现时达到高效率

2、处理机调度算法
2.1 先 来 先 服 务（非抢占方式）
按先后顺序进行调度

2.2 短 作 业 优 先（非抢占方式）
又称为“短进程优先”SPN(Shortest Process
Next)；这是对FCFS算法的改进，其目标是减少平均周
转时间

– 优点：
• 比FCFS改善平均周转时间和平均带权周转时间，缩短作业
的等待时间；
• 提高系统的吞吐量；
– 缺点：
• 对长作业非常不利，可能长时间得不到执行；
• 未能依据作业的紧迫程度来划分执行的优先级；
• 难以准确估计作业（进程）的执行时间，从而影响调度性
能

2.3 最短剩余时间优先（抢占式）
允许比当前进程剩余时间更短的进程来抢占

2.4 最高响应比优先（非抢占方式）
• 响应比R = (等待时间 + 要求执行时间) / 要求执行时间
• 是FCFS和SJF的折衷

2.5 时间片轮转(Round Robin)算法
本算法主要用于微观调度，说明怎样并发运行，即切换的方式；设计目标是提高资源利用率。
其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率；

2.6 多级队列算法(Multiple-level Queue)
各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等

2.7 优先级算法(Priority Scheduling)（可分成抢先式和非抢先式）
1）静态优先级
– 创建进程时就确定，直到进程终止前都不改变。通常是一个整数

2）动态优先级
在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；
– 进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU

注意：
I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。
– 计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。