资源
可抢占性资源和不可抢占性资源
-
可抢占性资源指可以从拥有资源的进程中抢占而不会造成影响的资源，如存储器(内存交换)等
-
不可抢占性资源指无法在不引起失败的情况下，将资源从其他进程中抢占过来，如刻录机等
调度层次
高级调度
高级调度的调度对象是作业，决定将哪个作业从外存调入内存并赋予资源
低级调度
低级调度的调度对象是进程，决定哪个进程将获得处理机
中级调度
中级调度负责进程在内存与外存之间的调换
作业调度算法
作业指命令、程序、数据与作业说明书
先来先服务
系统按照作业到达的先后次序进行调度
短作业优先
以作业的长短，即作业要求的运行时间作为作业的优先级，作业越短则优先级越高
每次有作业结束时，判断当前到达的所有作业谁更短
优先级调度算法
基于作业的紧迫程度，赋予作业不同的优先级，每次调度时，将等待队列中优先级最高者调入内存
高响应比优先调度算法
高响应比优先算法不仅考虑作业的运行时间，还考虑作业的等待时间，等待时间越长的作业优先级不断增加
每次有作业结束时，计算响应比$R_p$，高者优先
\[R_p={等待时间+要求服务时间 \over 要求服务时间}\]
最短剩余时间调度算法
进程调度算法
非抢占式调度算法
当系统判断需要阻塞时，并不中断当前进程，直至当前进程停止
抢占式调度算法
操作系统在需要执行另一优先级更高的进程时，直接中断当前进程，执行需要执行的进程
轮转调度算法
当时间片未用完而进程结束时，删除完成的进程，启动新的时间片； 时间片用完而进程未结束时，将该进程置于就绪队列的尾部
优先级调度算法
静态优先级预先根据进程的类型、需求和用户决定进程的运行顺序
动态优先级根据等待时间和运行状况更改进程的优先级
实时调度算法
最早截止时间优先(EDF)
根据进程最晚开始执行时间的先后顺序决定优先级
在有新进程到达或有进程结束时调度进程
最低松弛度算法(LLF)
松弛度=任务必须完成时间-进程剩余运行时间-当前时间
在有进程执行完成或有进程的松弛度为0时调度进程
优先级倒置及解决方法
若优先级高的进程与优先级低的进程存在临界资源的争夺，而低优先度进程先进入临界区
则高优先级进程必须等待优先级介于两者之间的进程运行结束，然后才能等待临界区的释放
为了解决优先级倒置问题，可以使得高优先级进程被低优先级的进程阻塞时赋予低优先级进程同等的优先级，使之先执行
死锁
死锁条件
-
互斥:资源要么已经分配给某进程,要么就是可用的
-
占用和等待条件:已经得到某资源的进程可以再请求新的资源
-
不可抢占条件:无法在未被释放的条件下抢占资源
-
环路等待:若死锁发生,则系统中必有一环路
死锁的预防
-
要求进程一次性申请所有需要的资源
-
进程可以先申请一部分资源，然后全部释放后方可继续申请
-
使资源可以被抢占
-
将资源编号，只允许进程按序申请
死锁的避免(银行家算法)
银行家算法需要：
- Available:当前可利用资源的数量
- Max：进程对某资源的最大需求
- Allocation：当前进程占用的资源数量
- Need:进程仍需要的资源数量
- Finish:判断是否有足够的资源
当某进程提出资源请求Request时，执行银行家算法
执行流程：
- 判断Request<=Need 申请资源须在声明范围内
- 判断Request<=Aviailable 申请资源须在总资源范围内
- 修改：Available-=Request
- 修改：Allocation+=Request
- 修改：Need-=Request
- 设置Work=Available；Finish=false
- 判断是否存在Need<=Work,若是，转8
- 修改：Work+=Allocation;Finish=true;转7
- 当所有进程的Finish变量值为true时，系统安全，可以分配资源给请求进程
死锁的检测
资源分配图
将所有资源按分配边分配给进程，再让剩余的资源按请求边逐一满足进程请求
本文共2182字符