导图社区 操作系统之进程调度
聚焦考研复习：操作系统的最难一章《进程调度》！本思维导图归纳总结了进程概述，进程的状态与转换，进程控制，进程通信、线程、多线程模型，处理机调度概念、层次、进程调度的时机、切换与过程、调度方式等25块知识点。很细致，欢迎采纳，一起学习吧！
数据结构与算法 数据结构是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了相应操作的数据元素集合。
操作系统是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。
计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统。
社区模板帮助中心，点此进入>>
《影响力》思维导图
互联网9大思维
安全教育的重要性
组织架构-单商户商城webAPP 思维导图。
个人日常活动安排思维导图
域控上线
西游记主要人物性格分析
17种头脑风暴法
python思维导图
css
进程管理
1. 进程概述
定义
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
组成
PCB
进程描述信息
进程控制和管理信息
资源分配清单
处理机相关信息
程序段
存放要执行的程序代码
数据段
存放程序运行过程中处理的各种数据
组织形式
链接方式
按进程状态将PCB分为多个队列
索引方式
按照进程状态建立几张索引表，各表项指向一个PCB
特征
动态性
进程的最基本特征
并发性
独立性
进程是系统进行资源分配、调度的独立单位
异步性
各进程以不可预知的速度向前推进，可能导致运行结果的不确定性
结构性
2. 进程的状态与转换
状态
运行状态
有CPU 有其他所需资源
就绪状态
无CPU 有其他所需资源
阻塞状态
无CPU 无其他所需资源
创建状态
操作系统为新进程分配资源，创建PCB
终止状态
操作系统回收进程的资源、撤销PCB
进程状态间的转换
就绪态到》运行态
进程被调度
运行态》就绪态
时间片到，或CPU被其他更高优先级的进程抢占
运行态》阻塞态
等待系统资源分配，或等待某事件发生（主动行为）
阻塞态》就绪态
资源分配到位，等待的事件发生（被动行为）
创建态》就绪态
系统完成创建进程相关的工作
运行态》终止态
进程运行结束，或运行过程中遇到不可修复的错误
3. 进程控制
基本概念
进程控制就是要实现进程状态之间的转换
进程控制用原语来实现
原语用关/开中断来实现
原语是一种特殊的程序
原语的执行必须一气呵成，不可中断
相关原语
进程的创建
进程的终止
进程的阻塞
进程的唤醒
阻塞和唤醒要成对出现
进程的切换
4. 进程通信
共享存储
设置一个共享空间
要互斥的访问共享空间
两种方式
基于数据结构（低级
基于存储区的共享（高级
管道通信
设置一个特殊的共享文件（管道），其实就是一个缓冲区
一个管道只能实现半双工通信
实现双向同时通信要建立两个管道
各进程要互斥的访问管理
写满时，不能在写。读空时，不能再读
没写满，不能读。没读空，不能写
消息传递
传递结构化的消息（消息头/消息体）
系统提供“发送/接受原语”
直接通信方式
消息直接挂到接收方的消息队列里
间接（信箱）通信方式
消息先发送到中间体（信箱）
5. 线程、多线程模型
什么是线程，为什么要引入线程？
可理解为“轻量级进程”
可增加并发度，减少并发带来的开销
引入线程机制后，有什么变化？
资源分配、处理机调度
（实现并发的）系统开销
线程有哪些重要的属性
线程是处理机调度的单位，进程是资源分配的单位
同一进程的各线程共享进程拥有的资源
同一进程内的线程切换不会导致进程切换
线程的实现方式
用户级线程
从用户视角看的线程
内核级线程
从操作系统视角看的进程（内核级线程才是处理机分配的单位）
组合方式
上述两种方式的组合
多线程模型
多对一模型
进程管理开销小效率高
一个线程阻塞会导致整个进程都被阻塞（并发度低）
一对一
进程管理开销大
各个线程可分配到多核处理机并行执行，并发度高
多对多
取二者之所长
6. 处理机调度概念、层次
按某种算法选择一个进程将处理机分配给它
三个层次
高级调度（作业调度）
按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
中级调度（内存调度）
按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
低级调度（进程调度）
按照某种规则，从就绪队列中选择一个进程为其分配处理机
三层调度的联系、对比
高级调度
外存》内存（面向作业）
发生频率：最低
中级调度
外存》内存（面向进程）
发生频率：中等
低级调度
内存》CPU
发生频率：最高
补充
为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为挂起态
七状态模型：在五状态模型的基础上加入了 就绪挂起 和 阻塞挂起 两种状态
7. 进程调度的时机 切换与过程 调度方式
时机
什么时候需要进程调度
主动放弃
进程正常终止
运行过程中发生异常而终止
主动阻塞（如等待I/O）
被动放弃
分给进程的时间片用完
有更紧急的事情需要处理（如I/O）中断
有更高优先级的进程进入就绪队列
什么时候不能进行进程调度
在处理机中断的过程中
进程在操作系统内核程序临界区中
原子操作过程中（原语）
切换与过程
狭义的调度和切换的区别
切换过程
对原来运行进程各种数据的保存
对新的进程各种数据的恢复
重要理论：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高
方式
非剥夺调度方式（非抢占式
只能由当前运行的进程主动放弃CPU
剥夺调度方式（抢占式）
可由操作系统剥夺当前进程的CPU使用权
8. 调度算法的评价指标
CPU利用率
也有题目会让我们计算某设备的利用率
利用率=忙碌的时间/总时间
系统吞吐量
系统吞吐量=总共完成了多少道作业/总共花了多少时间
周转时间
周转时间=作业完成时间-作业提交时间
平均周转时间=各作业周转时间之和/作业数
带权周转时间=作业周转时间/作业实际运行的时间
平均带权周转时间=各作业带权周转时间之和/作业数
等待时间
进程/作业 等待被服务的时间之和
平均等待时间即各个进程/作业 等待时间的平均值
响应时间
从用户提交请求到首次产生响应所用的时间
9. 调度算法
先来先服务 FCFS
主要从公平的角度考虑
按照作业/进程到达的先后顺序进行服务
用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑是哪个进程先进入就绪队列
非抢占式的算法
公平、算法实现简单
排在长作业后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。对场作业有利，对短作业不利
不会饥饿
短作业优先 SJF
追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
最短的作业/进程优先得到服务
即可用于作业调度，也可用于进程调度，用于进程调度时称为段进成优先算法
SJF 和 SPF是非抢占式的算法，但也有抢占式的版本--最短剩余时间优先算法 SRTN
最短的平均等待时间、平均周转时间
不公平，对短作业有利，对长作业不利。可能产生饥饿现象。另外，运行时间是用户提供的，并不一定真实，不一定做到真正的短作业优先
会饥饿。如果一直得不到服务，则称为饿死
高响应比优先 HRRN
要综合考虑作业/进程的等待时间和要求服务的时间
在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
响应比=（等待时间+要求服务时间）/要求服务时间
既可用于作业调度，又可进程调度
非抢占式。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
综合考虑了等待时间和运行时间。等待时间相同时，要求服务时间短的优先，要求服务时间相同时，等待时间长的优先
10. 调度算法2
时间片轮转调度RR
公平的、轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
用于进程调度（只有作业放入内存建立了相应的进程后，才能分配处理机时间片
若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法，由时钟装置发出时钟中断来通知CPU时间片已到
公平 响应快 适用于分时操作系统
由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度
时间片太大或太小分别有什么影响
优先级调度算法
随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
每个进程/作业都有自己的优先级，调度时选择优先级最高的作业/进程
既可用于作业调度，也可用于进程调度。甚至，还会在之后会学习的I/O调度中
抢占式、非抢占式都有。非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占
在优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活的调整对各种作业/进程的偏好程度
若源源不断的有高优先级进程到来，则可能导致饥饿
会饥饿
多级反馈队列调度算法
对其他调度算法的折中权衡
规则
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
新进程到达时先进入第一级队列，按FCFS原则排队等地啊被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时已经是在最下级的队列，则重新放回该队列队尾
只有第k级队列为空时迷彩灰为k+1级队头的进程分配时间片
用于进程调度
抢占式。在k级队列的进程运行过程中，若更上级的队列（1-k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾
对各类进程相对公平
11. 进程同步 进程互斥
进程同步
并发性带来了异步性，有时需要通过进程同步解决这种异步问题
有的进程之间需要相互配合的完成工作，各进程的工作推进需要遵循一定的先后顺序
进程互斥
对临界区的访问，需要互斥的进行，即统一时间段内只能允许一个进程访问该资源
四个部分
进入区
检查是否可进入临界区，若可进入，需要上锁
临界区
访问临界资源的那段代码
退出区
负责解锁
剩余区
其余代码部分
需要遵循的原则
空闲让进
临界区空闲时，应允许一个进程访问
忙则等待
临界区正在被访问时，其他试图访问的进程需要等待
有限等待
要在有限时间内进入临界区，保证不会饥饿
让权等待
进入了临界区的进程，要释放处理机，防止忙等
12. 进程互斥的软件实现方法
单标志法
在进入区只做检查，不上锁
在退出区把临界区的使用权转交给另一个进程，相当于在退出区既给另一进程解锁，又给自己上锁
主要问题
不遵循空闲让进原则
双标志先检查
在进入区先检查后上锁，退出区解锁
不遵循忙则等待
双标志后检查
在进入区先加锁后检查，退出区解锁
不遵循空闲让进、优先等待。可能导致饥饿
Peterson算法
在进入区主动争取-主动谦让-检查对方是否想进、己方是否谦让
不遵循让权等待原则，会发生忙等
13. 进程互斥的硬件实现方法
中断屏蔽方法
使用开关中断指令实现
简单高效
只适用于单处理机，只适用于操作系统内核进程
TestSndSet (TS指令/TSL指令）
old记录是否已被上锁
再将lock设为true
检查临界区是否已被上锁
若已上锁，则循环重复前几步
实现简单；适用于多处理机环境
不满足让权等待
Swap指令（XCJG指令）
14. 信号量机制
整型信号量
用一个整数型变量作为信号量，数值表示某种资源数
整型信号量与普通整型变量的区别：对信号量只能执行初始化 P V 三种操作
整型信号量存在的问题：不满足让权等待原则
记录型信号量
大题、小题超高频出题点
S.value表示某种资源数，S.L指向等待该资源的队列
P操作中，一定是先S.value--，之后可能需要执行block原语
V操作中，一定是先S.value++，之后可能需要执行wakeup原语
注意：要能够自己推断在什么条件下需要执行block或wakeup
可以用记录型信号量实现系统资源的申请和释放
可以用记录型信号量实现进程互斥、进程同步
15. 用信号量机制实现进程互斥、通步、前驱关系
除了互斥、同步问题之外，还会考察有多少个资源的问题，有多少资源就把信号量初值设为多少，申请资源时进行P操作，释放资源时进行V操作即可
实现进程互斥
互斥问题，信号量初值为1
分析问题，确定临界区
设置互斥信号量，初值为1
临界区之前对信号量执行P操作
临界区之后对信号量执行V操作
实现进程同步
同步问题，信号量初值为0
分析问题，找出哪里需要实现 一前一后 的同步关系
设置同步信号量，初始值为0
在前操作之后执行V操作
在后操作之前执行P操作
实现进程的前驱关系
前驱关系问题，本质上就是更复杂的同步问题
分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
为每一对前驱关系设置同步信号量，初值为0
在每个前操作之后执行V操作
在每个后操作之前执行P操作
16. 生产者消费者问题
17. 多生产者多消费者问题
18. 吸烟者问题
19. 读者-写者问题
20. 哲学家进餐问题
21. 管程
为什么要引入管程
解决信号量机制编程麻烦、易出错的问题
共享数据结构
对数据结构初始化的语句
一组用来访问数据结构的过程（函数）
基本特征
各外部进程\线程只能通过管程提供的特定“入口”才能访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
各进程必须互斥的访问管程的特性是由编译器实现的
可在管程中设置条件变量及等待/唤醒操作以解决同步问题
22. 死锁的概念
什么是死锁
各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
死锁 饥饿 死循环的区别
死锁：至少是两个进程一起死锁，死锁进程处于阻塞态
饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
死循环：可能只有一个进程发生死循环，死循环的进程可上处理机
死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的
死锁产生的必要条件
互斥条件
对必须互斥使用的资源的争抢才会导致死锁
不剥夺条件
进程保持的资源只能主动释放，不可强行剥夺
请求和保持条件
保持着某些资源不放的同时，请求别的资源
循环等待条件
存在一种进程资源的循环等待链
循环等待未必死锁，死锁一定有循环等待
什么时候会发生死锁
对不可剥夺资源的不合理分配，可能导致死锁
死锁的处理策略
预防死锁
破坏死锁产生的四个必要条件
避免死锁
避免系统进入不安全状态（银行家算法）
死锁的检测和解除
允许死锁发生，系统负责检测出死锁并解锁
23. 死锁的处理-预防死锁
破坏互斥条件
将临界资源改造为可共享使用的资源（如SPOOLing技术）
缺点：可行性不高，很多时候无法破坏互斥条件
破坏不剥夺条件
方案一，申请的资源得不到满足时，立即释放拥有的资源
方案二，申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）
缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿
破坏请求和保持条件
运行前分配好所需要的资源，之后一直保持
缺点：资源利用率低，可能导致饥饿
破坏循环等待条件
给资源编号，必须按编号从小到大的顺序申请资源
缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦
24. 死锁的处理-避免死锁
什么是安全序列
什么是系统的不安全状态，与死锁有何联系
如何避免系统进入不安全状态-银行家算法
25. 死锁的处理-检测和解除
死锁的检测
数据结构：资源分配图
两种节点
进程节点
资源节点
两种边
进程结点》资源节点（请求边）
资源节点》进程结点（分配边）
死锁检测算法
依次消除与不阻塞进程相连的边，知道无边可消
注：所谓不阻塞进程是指其申请的资源数还足够的进程
死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
题中一般会给出资源分配图，不过也要小心与数据结构结合来考察
死锁的解除
资源剥夺法
撤销进程法（终止进程法）
进程回退法
