图解
三级调度的联系
作业调度为进程的活动做准备,例如启动时mainThread的各种初始化加载； 中级调度将暂时用能运行的进程挂起,中级调度处于之间,所有有个中字
作业调度次数少,中级调度次数多,进程调度频率对高(进程多了阻塞,就绪挂起态,状态多了切换也就频繁了)
进程调度时最基本的，不可缺少
调度时机,切换与过程
以下几种情况不能处理进程切换
在处理中断的过程中,中断操作处于核心态比较重要,原语操作,不能切换
进程在操作系统内核的临界区: 进入临界区需要枷锁占有共享数据,为了更快的释放所,不应该切换
其他需要完全屏蔽中断的饿原子操作过程,如加锁,解锁,中断现场保护,恢复
应该进行调度的情况
发生引起调度条件(如CPU时间片时间到了),当前进程无法继续执行下去
中断处理结束或自陷处理结束后，返回被中断进程的用户程序执行现场信息,恢复被调度进程的现场信息。
调度的方式
剥夺式,又称抢占式,处理机分配给任务更为紧迫和重要的进程
非剥夺式,均衡执行
对比: 采用剥夺时调用,有助于提高系统整体的吞吐量和响应效率,但必须遵守一定的原则,如优先权,短进程优先和时间片原则
## 调度的基本准则
不同的调度算法具有不同的特性,在选择调度算法式，必须要考量调度算法的特性,
CPU利用率，尽可能让CPU处于忙碌状态
系统吞吐量: 单位时间内CPU完成的作业数量
周转时间: 作业从提交到完成锁经历的十斤啊,是作业等待, 在就绪队列,在处理机以及输入/输出操作锁花费的总时间之河
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = (作业1完成时间 + 作业2完成时间 + ... 作业n完成时间)/n
带权周转时间 = 作业周转时间/作业实际运行时间
等待时间: 进程处于等待处理机状态的时间
响应时间: 用户从提交请求到首次系统产生响应所用的时间
典型的调度算法:
FCFS: 先来先服务, 作业时间公平,不可剥夺算法，先来先服务,对长作业有利,对长CPU繁忙型作业有利,不利于I/O繁忙型作业
SJF: 短作业优先算法, 对长作业不友好,没有考虑优先级,容易导致饥饿
优先级调度算法:
剥夺式，非剥夺式
静态优先级, 动态修仙记
系统进程>用户进程
交互型进程> 非交互型进程(前台>后台)
I/O进程优先于CPU进程(I/O)比较慢，先执行,让I/O设备更早工作
高响应比优先算法(HRRN):
响应时间 = （等待时间 + 要求服务时间）/ 要求服务时间
作业等待时间相同时,要求服务的时间越短,响应比越高
在要求服务时间相同时,作业的响应比由他的服务时间决定,因此他实现的是先来先服务
时间片轮转调度算法: 如果时间片足够大,所有进程的任务都能在一个时间片中完成,则退化为先来先服务;如果时间片小,则系统需要频繁的切换进程,处理机开销大,时间片的长短通常由系统响应时间,就绪对垒中进程树木和系统处理能力决定
多级反馈队列
设置多个就绪队列,每个队列都设置不同的优先级
赋予各队列中各进程执行的时间片大小各不相同,队列优先级越高则时间片越短
一个新的进程进入内存后它首先放入1级队列的末尾,如果他在一个时间片未执行完则放入到2级对列
仅当前以及的调度队列为空的时候才去执行下一级别的调度队列
特点:
终端作业型用户，短作业优先， 这就意味着如果一直插入一级队列的短作业则会饿死
短批处理作业用户,周转时间短
长批处理作业用户,经过前面几个步骤的分布执行,不会长期得不到处理
进程同步为甚么引入进程同步: 在多道处理机下面，进程是并发执行的，不同的进程之间存在着不同的相互制约的关系,为了协调进程之间相互制约的关系引入了进程同步概念。
进程同步的几种实现机制：
临界资源: 受限制资源,一次只能允许一个进程使用的资源，通过互斥访问实现
do {
entry section; //进入区 进入时执行 wait源语
critical section //临界区
exit section: //退出区, 退出时执行signal源语
}
同步: 进程协调完成某种任务,部分任务需要控制其先后
互斥:
空闲让进
忙着等待
有限等待
让权等待
临界区互斥软件实现
单一标志法, trun = 0,多线程同时串改的风险，违背空闲让进
双标志法 flag[n] = true; 同样存在多线程同时串改的风险,违背忙着等待
双标志检查法: 会再检测时让权,过 （书本解释有歧义,实际能work,不是最优解）
Perternson‘Algorithm: 正向标记,反向标记
flag[i] = true, turn = j;
while(flag[j] && trun ==j );
...
硬件实现:
中断屏蔽法: 关中断 -> 临界区 -> 开中断 (CUP无法进行进程切换,所以不会有问题),不能对突发事件处理
硬件指令法:
TestAndSet, 原子指令操作 对 *lock树枝控制
swap: 对 *a和 *b数据互换实现中断
信号量
基于系统的原语， signal和wait实现， 可以实现同步，互斥,前驱关系(多个进程按照一定的顺序执行)
进程同步互斥的处理方式
关系梳理， 同步,互斥 设置pv的个数和放置顺序
资源确定: 设置信号量
管程作用: 简化pv操作,管理进程
结构:
名称
共享数据结构说明
对数据结构进行操作的一组过程
对局部管程内部的共享数据设置初始值的语句
本质就是对数据的插入和获取进行 源语 wait和signal的管理
经典例子生产者消费者问题
吃苹果和橘子
吸烟者问题
读者学者
哲学家进餐问题
定义: 进程资源互享等待无法继续向前推进
原因:
系统资源竞争
进程推进顺序非法,程序猿bug,信号量设置错误
产生条件
进程对所分配的资源独占,其他进程无法访问
不可剥夺,其他进程无法剥夺它的资源
请求和保持条件,进程保持了至少一个资源,又提出了新的资源请求
循环等待条件: 每个进程获得资源的同时被下一个进程所请求，存在一个闭环的等待集合 { p1, p2, ..pn, p1}
处理策略
预防死锁
破坏互斥条件，如允许资源共享使用, 但对于资源少的无法满足，如打印机,而且有些场合需要保持这种互斥性