2.处理机调度
2017-01-12 14:47:23 0 举报AI智能生成
处理机调度是操作系统中的一个重要环节，它负责管理和分配计算机的处理资源。其主要任务是根据进程的优先级、资源需求等因素，决定哪个进程应该获得处理机的时间片，以及在何时进行切换。处理机调度的目标是最大化系统的整体效率和吞吐量，同时保证公平性和响应时间。常见的处理机调度算法有先来先服务、短进程优先、轮转法等。处理机调度不仅需要考虑单个进程的需求，还需要考虑多个进程之间的竞争关系和系统的整体状态。因此，处理机调度是一个复杂而重要的问题，需要综合考虑多种因素，以达到最优的调度效果。
作者其他创作
大纲/内容
处理机调度
级别
高级调度（作业调度）
中级调度（交换调度）
低级调度（进程调度）
方式
剥夺方式
分时/实时系统
非剥夺方式
批处理系统
时机
现运行进程执行完成或异常结束（撤销原语）
现运行进程提出I/O请求，等待I/O完成（运行态→阻塞态）
时间片用完
被更高优先级进程抢先（运行态→就绪态）
唤醒原语、阻塞原语
调度准则
CPU利用率高
吞吐量大
（平均）周转时间短
（平均）等待时间短
响应时间短
调度算法
先来先服务（FCFS）调度
非剥夺
有利于长作业（进程）
简单，但效率不高
最短作业优先（SJF）调度
非剥夺
剥夺
最短剩余时间优先（SRTF）
有利于短作业（进程）
最优
饥饿
高响应比优先调度
兼顾长短作业
响应比 = 1 + 作业等待时间/作业估计运行时间
优先级调度
剥夺
分时系统
非剥夺
批处理系统
优先级
影响因素
进程类型
进程对资源的需求
用户要求
类型
静态优先级
动态优先级
优先数
时间片轮转调度
剥夺
分时系统
多级队列调度
多个就绪队列
每个进程在固定的队列
多级反馈队列调度
多个就绪队列
进程可以在队列之间移动
进程通信
类型
互斥
资源共享
间接制约
同步
协作完成同一个任务
直接制约
方式
共享内存
消息传递
临界资源
定义
一次仅允许一个进程使用的资源
临界区
每个进程访问临界资源时必须互斥执行的程序
访问原则
互斥使用
硬件方法
关中断
原理
CPU只有在发生中断时才会进行进程切换
测试和设置指令
原理
为临界资源设置锁位变量w
软件方法
共享整型变量
为进程分别设置布尔变量
Dekker算法
有空让进
让权等待
有限等待
信号量
物理含义
表示资源的物理实体
结构
value
表示该类资源的当前可用数量
>0 可用
负数的绝对值 等待进程数
L
等待使用该类资源的阻塞队列的队首指针
操作
P操作
申请资源
V操作
释放资源
分类
公用信号量
互斥
私用信号量
同步
简单同步-互斥模型
互斥
互斥信号量mutex，初值为1
P(mutex) → 进入临界区 → V(mutex) → 唤醒队首进程
同步
计算与打印进程
信号量empty = 1，full = 0
计算→P(empty)→数字加入缓冲区→V(full)
P(full)→打印→V(empty)→缓冲区置空
经典进程同步问题
生产者-消费者
信号量：mutex = 1，empty = 空缓冲区的数量，full = 0
生产者
生产 → P(empty) → P(mutex) → 插入缓冲区 → V(mutex) → V(full)
消费者
P(full) → P(mutex) → 移出缓冲区 → V(mutex) → V(empty) → 消费
读者-写者
信号量
读写互斥信号量db=1
读计数互斥信号量mutex=1
计数器变量rc=0
读者
P(mutex) → rc++ → if(rc==1)P(db) → V(mutex) → 读
→ P(mutex) → rc-- → if(rc==0) V(db) → V(mutex)
写者
P(db) → 写 → V(db)
管程
引入原因
各个进程自备P(S)和V(S)的操作，加重了用户负担
大量同步操作分散在各进程中，系统管理复杂
易产生死锁
定义
管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块
结构
管程名
局部于管程的共享变量说明
对该数据结构进行操作的一组过程
对局部于过程的数据设置初始值的语句
特点
局部于管程的数据结构只能被局部于管程的过程访问
局部于管程的过程只能服务管程内的数据结构
一次只有一个进程能在管程内活动
同步机制
条件变量c
同步原语wait(c)
同步原语signal(c)
消息传递
直接/间接通信
直接通信
消息发送原语
请求分配一个消息缓冲区
将消息正文传入消息缓冲区，并填入有关参数
将消息缓冲区挂在接收进程的消息链上
接收消息原语
检查消息链上是否有消息
有，则将消息接收到接收区
无，则阻塞等待
间接通信（信箱通信）
消息同步
发送进程与接收进程状态
阻塞
非阻塞
消息同步方式
非阻塞发送，非阻塞接收
阻塞发送，非阻塞接收
非阻塞发送，阻塞接收
阻塞发送，阻塞接收
进程
引入
描述程序的执行过程
程序是静态的
CPU的执行过程是动态的
单道程序
程序顺序执行
程序执行的连续性
程序环境的封闭性
程序结果的可再现性
多道程序
程序并发执行
程序执行的间断性
相互制约
间接制约
共享资源
直接制约
协同完成任务
失去了程序环境的封闭性
资源共享
程序结果的不可再现性
特点
动态性
进程状态切换
创建态
就绪态
除CPU外其他全部资源
运行态
CPU+其他全部资源
阻塞态
除CPU外其他部分资源
终止态
独立性
资源分配
处理机调度
并发性
异步性
结构性
程序
数据
进程控制块PCB
进程存在的唯一标识
进程动态性的集中体现
包含进程需要的全部信息
组织
线性表
优点
简单，节省存储空间
缺点
系统开销大，查找一个执行的PCB较费时
链接方式
索引方式
控制原语
原语
执行过程不可分割
创建原语
时机
系统内核创建
应用程序创建
功能
申请空白PCB
为新进程分配资源
初始化PCB
将新进程插入就绪队列
注意
父子进程
资源共享
数据
地址空间
进程执行
撤销原语
时机
进程已完成任务，正常结束
由于故障不能继续执行，异常结束
外界干预
功能
根据被终止进程标识符查找PCB
终止该进程，重新调度
终止该进程的全部子进程
回收资源
释放PCB
注意
是否撤销该进程的子进程
阻塞原语
时机
处于运行状态的进程等待某一事件的发生
功能
处于运行态的进程中断CPU，将其运行现场保存在PCB的CPU现场保护区
将状态改为阻塞态，并插入等待队列
转进程调度，选择一个就绪进程投入运行
注意
阻塞原语由进程自己执行
唤醒原语
时机
进程期待的时机到来
功能
等待输入输出完成
硬件提出中断，CPU响应中断，暂停当前进程，转入中断处理
检查有无等待输入输出完成的进程
有则将进程的状态改为就绪态，插入就绪队列，结束中断处理
返回被中断进程，或者进行进程调度
等待某进程发送消息
发送进程将等待进程唤醒
把进程状态改为就绪态，插入就绪队列
线程
引入
提高响应速度
资源共享
共享进程资源
降低系统开销
特点
独立调度
并发性
动态性
线程的状态
就绪态
运行态
阻塞态
结构性
线程控制块TCB
线程的标识
线程状态
执行堆栈
程序计数器
寄存器集
类型
内核级
所有线程（用户+系统）由内核管理
实现
创建进程时分配任务数据区空间
用户级
用户线程，用户空间管理，内核不知道
实现
运行时系统
内核控制线程（轻型进程LWP）
调度
用户级线程
由线程库管理
在CPU上运行时，必须映射到相应的内核级线程
进程竞争范围PCS
内核级线程
由操作系统调度到物理CPU上
系统竞争范围SCS
进程与线程的对比
资源
进程拥有独立的资源
线程共享进程的所有资源，自己拥有的资源很少
调度
进程调度需要进行上下文切换，开销大
同一进程内的线程切换，仅交换线程拥有的一小部分资源，效率高
不同进程内的线程切换，将引起进程调度
并发性
引入线程后，系统并发执行程度更高
安全性
同一个进程的多个线程共享资源，一个线程可以改变另一个线程的数据
死锁
1个概念
2个产生原因
竞争资源（资源数量不足）
资源类型
可抢占资源
主存、CPU
不可抢占资源
慢速设备、共享变量
进程推进顺序非法
请求和释放资源的顺序不当
4个必要条件
互斥
保持和等待
不可剥夺
循环等待
资源分配图
组成
节点
进程节点P
圆圈
资源节点R
方块
边
请求边
有向边 P→R
分配边
有向边 R→P
结论
图中有环路
每类资源只有一个实例
有死锁
每类资源有多个实例
可能有死锁
图中无环路
无死锁
5个解决办法
鸵鸟算法
假定死锁从不发生
原因
死锁在计算机中很少发生
预防死锁的代价太高
UNIX、WINDOWS
死锁预防
静态分配资源
破坏死锁产生的必要条件
互斥
把独占设备改造为共享设备
保持和等待
进程在开始运行前必须获得需要的全部资源
优点
简单，易于实现，安全
缺点
资源利用率低，容易产生饥饿
不可剥夺
已经占有资源的进程提出新的申请而得不到满足时，必须释放全部资源
缺点
保护进程放弃资源时的现场及之后的恢复现场，系统要付出很大代价
增加了进程周转时间
循环等待
进程对资源的请求必须按照资源的递增或递减顺序序号申请
缺点
很难找到能满足所有进程需要的资源编号
限制新类型设备的增加
死锁避免
动态分配资源
资源分配之前，先计算资源分配的安全性，保证系统永远不进入不安全状态
安全状态/不安全状态
安全序列
银行家算法
数据结构
可用资源向量Available
最大需求矩阵Max
分配矩阵Allocation
需求矩阵Need
Need[i,j] = Max[i,j] - Allocation[i,j]
算法
设进程Pi的请求向量为Requesti[j] = k
若Requesti[j] <= Need[i,j]，继续；否则出错
若Requesti[j] <= Available[i,j]，继续；否则等待
将资源分配给Pi，修改数据结构
Available[j] = Available[j] - Requesti[j]
Allocation[i,j] = Allocation[i,j] + Requesti[j]
Need[i,j] = Need[i,j] - Requesti[j]
执行安全性算法
系统处于安全状态
资源分配给进程Pi
系统处于不安全状态
Pi等待，恢复原来的资源分配状态
安全性算法
1.设置工作向量Work = Available
2.设置向量Finish，初始值为Finish[i] = false
3.找到Finish[i] = false, Need[i,j] <= Work[i]的进程；若存在，转4；否则，转5
4.令Finish[i] = true, Work[j] = Work[j] + Allocation[i,j]；转3
5.若所有进程均满足Finish[i] == true，则处于安全状态；否则，处于不安全状态
死锁检测
资源分配之后，计算分配的安全性
此次分配导致系统死锁，则采取措施恢复
否则，继续
对进程资源分配图进行检测
包含一个或多个循环
存在死锁
不包含循环
不存在死锁
检测时机
每次资源请求时检测
间隔一段时间检测
检测算法
每个资源一个单位数量
每类资源多个
如果一个资源只有射出箭头，擦除所有与其相关的箭头
如果一个进程只有指向它的箭头，擦除所有与其相关的箭头
如果一个进程有射出的箭头，且每个请求箭头都有一个可用资源，擦除所有与其相关的箭头
当且仅当没有箭头剩余，系统处于非死锁状态
死锁恢复
通过剥夺资源
通过剥夺一些进程的资源
最小代价
通过滚回一些进程
将一个或多个死锁进程滚回
饥饿问题
通过撤销进程
撤销死锁进程，断开环路
撤销不在环路中的非死锁进程
进程状态的转换
0 条评论
下一页
