[[文章索引]] [[操作系统系列]]

功能和时机

进程调度功能由操作系统的 进程调度程序 完成。

按照某种策略和算法 从就绪态进程中为当前空闲的 CPU 选择在其上运行的新进程

调度时机:

进程正常结束
进程阻塞
更高优先级
时间片用完
进程异常结束

调度算法

先来先服务
短进程优先
优先权
时间片轮转
多级队列
多级反馈队列

选择方式和准则

周转时间短

外存等待时间+就绪队列等待时间+执行时间+等待I/O操作完成
平均周转时间公式
带权平均周转时间(服务时间:一个作业在 CPU 上执行的总时间)

响应时间快

截止时间的保证

系统吞吐量高

处理机利用率好

周转时间=服务时间+等待时间

开始运行时间=进入系统时间+等待时间=上一个进程开始运行时间+上一个进程服务时间=上一个进程周转时间+上一个进程进入系统时间

FCFS

先来先服务调度算法。从就绪队列的队首 选择最先到达就绪队列的进程 , 为该进程分配 CPU

一个栗子

进程名进入系统时间开始运行时间服务时间等待时间周转时间
p10024024
p212432326
p322732528

系统平均周转时间

带权平均周转时间

SPF

短进程优先调度算法。从就绪队列中 选择估计运行时间最短的进程 , 为该进程分配 CPU。

一个栗子

进程名进入系统时间开始运行时间服务时间等待时间周转时间
p12624428
p213325
p300303

系统平均周转时间

带权平均周转时间

优点:与 FCFS 相比,有效降低进程的平均等待时间,提高了系统吞吐量
缺点:对长进程不利,不能保证紧迫进程的处理,长短由用户估计不一定准确

PSL

优先权调度算法。系统将 CPU 分配给就绪队列中 优先权最高的进程

分类:

非抢占式:运行期间有更高优先权的进程到来,不能剥夺 CPU
抢占式:运行期间有更高优先权的进程到来,可以抢占 CPU

优先权类型:

静态优先权:创建时确定,运行期间保持不变
动态优先权:创建时确定,随着进程推进或等待时间增加而改变

存在问题:无穷阻塞(饥饿问题)

解决方案:老化技术(增加等待时间很长的进程的优先权)

RR

时间片轮转调度算法。

系统将所有就绪进程按先来先服务的原则排成一个队列,每次调度时把 CPU 分给队首进程,并令其执行一个时间片。当时间片用完时,调度程序终止当前进程的执行,并将它送到就绪队列的队尾。

把 CPU 的1 s 执行时间划分为多个时间片,每个时间片大小 10-100 ms

现在的分时操作系统基本上都是使用以 RR 为基础结合 PSL 的调度算法。

Linux 2.4 的时间片大小是 50 ms

程序需要的时间 < 时间片大小 ,进程结束,调度。

程序需要的时间 > 时间片大小,时间片用完,执行态->就绪态,调度。

系统对响应时间的要求:响应时间要求越短,时间片越小。

就绪队列中进程的数目:进程数越多,时间片越小。

系统的处理能力:处理能力越小,时间片越小,并发越多。

性能评价

时间片很大,等同于 FCFS

时间片很小,增大了 CPU 对进程切换和调度的开销

多级队列调度算法

将就绪队列分成多个独立队列,每个队列有自己的调度算法。

多级反馈队列调度算法

建立多个优先权不同的就绪队列,每个队列有大小不同的时间片。

队列优先权越高,时间片越短。优先权越低,时间片越长。

实时系统中的调度

基本条件

提供必要的调度信息:就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级
系统处理能力强
采用抢占式调度机制
具有快速切换机制

常用实时调度算法

EDF -最早截止时间优先:开始截止时间越早,进程优先级越高,越优先获得 CPU
LLF - 最低松弛度优先:

进程切换

当前正在执行的进程成为被替换进程,让出其所使用的 CPU , 以运行被进程调度程序选中的新进程。

切换步骤

保存 包括程序计数器和其他寄存器在内的 CPU 上下文环境
更新 被替换进程的 进程控制块
修改进程状态 , 把执行态改为 就绪态或阻塞态
将被替换进程的进程控制块 移到就绪队列或阻塞队列
执行 通过进程调度程序选择的 新进程 ,并 更新 该进程的 进程控制块
更新内存管理 的数据结构
恢复 被调度程序选中的进程的 硬件上下文

多处理器调度 MPS

类型

紧密耦合:共享主存储器和 I/O 设备
松弛耦合:有各自的存储器和 I/O 设备
对称:处理单元功能和结构相同
静态分配:就绪队列的进程只能在与就绪队列对应的处理器上运行
动态分配:进程随机地被分配到当时处于空闲状态的某一处理器上执行
非对称:有多种类型的处理单元,一个主处理器,多个从处理器
主-从式分配: Master 调度 Slave 运行

进程(线程)调度方式

自调度
最常用最简单的方式。任何一个空闲处理器都可以从就绪队列中选取一个进程或线程运行。 FCFS
优点:易移植,有利于提高 CPU 利用率
缺点:瓶颈问题,低效性,线程切换频繁
成组调度
系统将一组相互合作的进程或线程同时分配到一组处理器上运行,进程或线程与处理器一一对应
优点:减少线程切换,减少调度开销
专用处理器分配
在程序执行期间,专门为该程序分配一组处理器,每线程一个
优点:加快程序运行速度,避免进程切换
缺点:处理器资源严重浪费

死锁

定义

多个进程竞争共享资源 而引起的 进程不能向前推进 的僵死状态。

产生的原因和必要条件

原因: 竞争 共享资源且分配资源的 顺序不当

必要条件:

互斥条件
请求和保持条件
不剥夺条件
环路等待条件

处理死锁的基本方法

预防:通过 破坏死锁的产生条件 来保证不发生死锁(至少破坏四个必要条件其中之一)
摒弃请求和保持条件:一次性请求全部资源、申请其他资源前释放已占用的资源
摒弃不剥夺条件:系统抢占被占用的资源分配给需要的进程(实现复杂、代价高)
摒弃环路等待条件:进程必须按规定的顺序申请资源(限制了新设配的增加、资源浪费、用户编程麻烦)
避免:通过 算法合理分配资源 来保证不发生死锁
找到一个进程的 执行序列 ,不会发生死锁,就是安全状态
不安全状态,可能会发生死锁(不是一定发生)
银行家算法:一个进程提出资源请求后,系统先进行资源的试分配,分配后检测系统是否安全
检测:检测当前系统是否出现死锁
充分条件:当且仅当目前状态的资源分配图是不可完全简化的
解除:检测到系统有死锁后进行解除
进程终止