Please enable JavaScript.
Coggle requires JavaScript to display documents.
ch6 假期进程调度 - Coggle Diagram
ch6 假期进程调度
进程的生命周期
执行
等待
就绪
终止
新的
进程调度即让尽可能多的进程进入运行状态，其被称为短时调度或者CPU调度
调度发生
一个进程终止：CPU被释放了，调度者需选择另一个进程工作
一个进程开始等待：调度者需选择另一个进程工作
一个新的进程被创建：fork()时调度者选择父进程或者子进程工作
进程终止了等待：若有必要，中断处理程序会发出请求
调度策略和调度算法
决定进入运行状态的进程
非抢占式调度
抢占式调度
适合于强调互动性的系统
不适用于强调完成任务的时间的系统
性能因素
吞吐量：单位时间完成的任务数
轮转时间：从提交时间到完成时间的间隔
CPU利用率
等待时间
响应时间：从提交时间到第一次被相应的时间：用于强调互动性的系统中
调度算法
Round-Robin(RR)
给定每个进程时间片，循环执行至时间片耗尽
专为分时系统设计，在这一算法下进程的响应性是非常好的
原则：时间片应该允许80%的进程执行完毕
实现了进程调度的公平性
优先级调度
看清楚是大数字的优先级较高还是小数字的优先级较高
问题：可能会导致无止尽的等待：解决：老化：逐步提高等待进程的优先级
实现了进程的强制执行
SJF(Shortest-job-first)
使用更多的上下文切换换取了更短的轮转时间和等待时间
可抢占与不可抢占分类讨论
困难：如何事先得知进程需要占用CPU的时间，解决方法：进行预测
多级队列调度
不同优先级的进程采取不同的调度策略
高优先级的进程一般的寿命较短但是非常重要
问题
固定优先权
无止尽的等待
解决方法：允许进程在不同的优先级队列进行切换：例如根据进程的CPU执行情况来区分不同进程所在队列
先进先出算法
对于输入很敏感
不去调度已经阻塞的进程实现了CPU/IO的均衡
不同系统的算法分析
在实际的系统或者特定的系统中设计调度
SMP(对称多处理）以及非对称多处理
处理器亲和性：大多数SMP系统试图避免进程从一个处理器移到另一个处理器而是试图让一个进程运行在同一个处理器上
软亲和性：试图保持进程运行在同一处理器上
硬亲和性：提供系统调用从而允许某个进程运行在某个处理器子集上
NUMA：CPU调度算法和内存分配算法一起工作
负载平衡
推迁移：将进程从超载处理器推到较空闲处理器（周期性检查每个处理器的负载，当发现负载不平衡时）
拉迁移：将进程从一个忙的处理器上拉一个等待任务
二者不互相排斥而是并行实现
实时的CPU调度算法
单调速率调度：根据速率分配优先级，但是不能保证一系列的进程都能顺利得到调度
EDF(Eariest Deadline First served):根据进程的DLL动态调整进程的优先级
不要求每个进程都有恒定的时钟周期，也不要求每个进程有固定的CPU执行时间
调度
由于CPU的资源是有限的，且进程具有多个状态，当占用CPU的进程在等待时如果不通过调度利用CPU则浪费了这一大部分的资源，因为进程的CPU执行时间通常都是大量的短CPU执行和少量长CPU执行
上下文切换
让已经就绪的进程进入运行状态
调度前必须备份程序的所有寄存器的值
调度程序将新进程的寄存器值以及主存加载到CPU上，这就是上下文切换
上下文切换的成本很高，所以尽量减少切换有助于提升性能