导图社区 408操作系统---第2章 进程与线程
基于王道课程，进程是动态的，进程是程序的一次执行过程，进程对应的程序处理的原始数据或执行过程中产生的中间、最终结果。
基于王道课程，I/O设备、/O控制器（设备控制器）、I/O控制方式、I/O软件层次结构、应用程序接口、设备驱动程序接口。
408操作系统---第4章 文件管理，文件是以硬盘为载体，存储在计算机上的信息集合，用户进行输入输出时以文件为基本单位。
基于王道课程，内容有操作系统、操作系统的特征、操作系统发展和分类、操作系统运行机制、中断和异常、系统调用、操作系统结构、操作系统引导、虚拟机。
社区模板帮助中心，点此进入>>
安全教育的重要性
个人日常活动安排思维导图
西游记主要人物性格分析
17种头脑风暴法
马克思主义原理
如何令自己更快乐
头脑风暴法四个原则
思维导图
考研数学重点考点知识总结归纳！
数据结构
进程与线程
进程
进程概念
进程是动态的
进程是程序的一次执行过程
程序是静态的
进程的组成
进程控制块(PCB)
进程描述信息
进程标识符PID
用户标识符UID
进程控制和管理信息
CPU、磁盘、网络流量
进程当前状态：就绪态/阻塞态/运行态
资源分配清单
正在使用哪些文件
正在使用哪些内存区域
正在使用哪些I/O设备
处理机相关信息
如PSW、PC等各种寄存器的值，实现进程切换
程序段
程序的代码(指令序列)
数据段
进程对应的程序处理的原始数据或执行过程中产生的中间、最终结果
进程的特征
动态性
进程是程序一次执行过程(最基本特性)
并发性
内存中有多个进程实体，各进程可并发执行
独立性
进程是一个独立运行、获得资源的单位
异步性
进程按照各自独立、不可预知的速度向前推进
结构性
PCB、程序段、数据段
进程的状态
创建态(新建态)
进程正在创建、分配资源、初始化PCB
就绪态
获得了除处理机之外所有资源
运行态
正在处理机上运行
阻塞态(等待态)
进程正在等待某一时间而暂停运行
终止态(结束态)
进程运行结束或遇到不可修复的错误
进程状态转换
就绪态→运行态
处于就绪态的进程获得处理机资源
运行态→就绪态
处于运行态的进程时间片用完，让出处理机
运行态→阻塞态
进程请求某一资源或等待某一事件发生
阻塞态→就绪态
进程等待的事件到来
进程的组织
链式方式
按照进程状态，将PCB分成多个队列
操作系统持有指向各个队列的指针
索引方式
根据进程状态，建立多个索引表
操作系统持有指向各个索引表的指针
进程控制
基本概念
进程控制就是实现进程状态的转换
进程控制使用原语
原语用开/关中断实现
原语是一种特殊的程序
原语必须一气呵成执行，不可中断
进程的创建
创建原语
申请PCB
分配资源
初始化PCB
就绪队列
引起进程创建的事件
进程的终止
终止原语
读状态
终止进程
归还资源
删除PCB
引起进程终止的事件
进程的阻塞
阻塞原语
找PCB
阻塞
等待队列
引起进程阻塞的事件
进程的唤醒(阻塞态→就绪态)
唤醒原语
找到PCB
移出队列
插入就绪队列
引起进程唤醒的事件
进程的切换
切换原语
引起进程切换的事件
进程的通信
进程之间的信息交换
高级通信方法
共享存储
存在一块可直接访问的共享空间，可进行写/读操作，实现进程之间的数据交换
基于存储区的共享(高级方式)
灵活性高，速度快
可以根据需求使用共享区
基于数据结构的共享方式(低级方式)
灵活性低，速度慢
按照规定的数据结构使用共享区(例如：int)
消息传递
传递结构化消息(消息头/消息体)
直接通信方式
发送进程→接收进程(消息缓冲队列)
间接通信方式(信箱通信方式)
发送进程→中间实体→接收进程
管道通信
进程借用管道文件，进程之间按照一端写、一端读，实现进程间通信
读空→读进程阻塞
写满→写进程堵塞
线程
目的：引入进程是为了提高操作系统的并发能力
通俗解释：一个进程有时需要在一段时间完成多个功能，传统进程只能串行执行程序，引入线程提高进程的并发度
一个基本的CPU执行单元，也是程序流的最小单元，独立调度的最小单位
特征
一个进程的多个线程之间共享地址空间和资源
同属于一个进程的线程切换开销小，不同进程的线程间开销大(进程切换)
进程中线程可分配到多个处理机上运行
进程是拥有资源的基本单位
线程是程序执行流的最小单位
线程与进程的比较
调度
传统的操作系统
进程是调度的基本单位
每次调度的开销大
引入线程的操作系统
线程的调度的基本单位
同一进程的线程之间调度，开销小
并发
同一进程的线程之间可以并发执行
拥有资源
进程是拥有资源的最小单位
独立
不同进程间独立，同一进程的线程共享地址空间和资源
系统开销
创建进程的开销大于创建线程的开销
线程的实现方式
用户级线程
应用程序使用线程库设计成多线程程序
从用户视角看到的线程，操作系统感知不到
优点：不需要切换至核心态，线程管理开销小
缺点：其中一个线程被阻塞，其他线程也被阻塞，并发能力弱
内核级线程
操作系统支持的线程
操作系统完成线程的操作，需要在核心态下切换线程
优点：线程之间并发能力强
缺点：一个进程占用多个内核级线程，线程切换由操作系统内核完成，线程管理成本高
多线程模型
上述两种方式的组合
一对一
一个内核级线程映射到一个用户级线程
多对一
多个用户级线程映射到一个内核级线程
多对多
n个用户级线程，映射到m个内核级线程
线程的状态转换
运行
就绪
线程的组织与控制
线程控制块(TCB)
线程表(多个TCB组成)
线程的创建
线程的终止
一堆任务要执行时，资源有限，需要通过某种规则来确定任务的顺序
进程调度
处理机资源有限，通过调度规则来确定进程执行的顺序
调度的三个层次
高级调度(作业调度)
启动一个作业
通俗理解：好几个程序需要启动，先启动哪个
外存→内存
低级调度(进程调度/处理机调度)
按照某种调度规则，从就绪队列中选取一个进程，把处理机分配给他
内存→CPU
中级调度(内存调度)
定义：按照调度策略，决定将哪个处于挂起状态的进程调入内存
内存不够时，将进程的数据调到外存
挂起状态：调到外存等待的进程
挂起队列：被挂起的进程PCB组成
进程调度时机
需要进行进程调度的情况
进程主动放弃
进程正常执行完
运行过程中发生异常
进程主动请求阻塞
进程被迫放弃
分给进程的时间片用完
有更紧急的任务需要处理(I/O中断)
有更高优先级的进程进入就绪队列
不能进行进程调度的情况
在处理中断的过程中
进程在操作系统内核临界区时
在原子操作中
进程调度方式
非剥夺调度方式(非抢占式)
只允许进程主动放弃
剥夺调度方式(抢占式)
优先级更高的进程抢占正在执行的进程资源
调度算法评价指标
CPU利用率=忙碌时间/总时间
系统吞吐量
单位时间完成的作业量
=总共完成了多少道作业/总共花了多少时间
周转时间
作业提交给系统，到完成作业的，时间间隔
平均周转时间=各作业的周转时间之和/作业数
带权周转时间=作业周转时间/作业实际运行时间
平均带权周转时间=带权周转时间/作业数
等待时间
作业处于等待处理机状态的时间之和
响应时间
用户提交请求到首次产生响应所用的时间
调度算法
先来先服务调度算法(FCFS)→非占用式
最先进入队列
短作业优先调度算法(SJF)
追求最少的平均等待时间
抢占式的短作业优先算法(最短剩余时间优先算法SRTN)
高响应比优先调度算法(HRRN)→非占用式
选择响应比最高的作用/进程，为其服务
响应比=(等待时间+要求服务时间)/要求服务时间
时间片轮转调度算法(RR)→抢占式
按照各进程进入就绪队列的顺序，轮流让各进程执行一个时间片(分时操作系统)
如果时间片太大，会退化为先来先服务算法
时间片太小，进程会切换频繁
优先级调度算法(抢占和非抢占)
优先级用于描述作业的紧迫程度
系统优先级高于用户进程
前台进程高于后台优先级
静态优先级：确定之后不会改变
动态优先级：会根据实际情况改变
如果某进程等待时间过长，可适当提高优先级
如果某进程占用处理机较长时间，可适当降低其优先级
多级反馈队列调度算法(抢占式)
设置多个队列，每个队列设置不同的时间片
子主题
多级队列优先算法
设置多个就绪队列，不同类型的进程分配到不同的就绪队列，每个队列实施不同的调度算法
同步与互斥
进程同步
用于解决进程异步的问题
临界资源
一段时间内只允许一个进程使用的资源
临界区
访问临界资源的代码段
进入区
退出区
剩余区
进程互斥
准则
空闲让进
临界区空闲，可以允许一个请求进入临界区
忙则等待
已经有进程进入临界区，其他想要进入临界区的进程需等待
有限等待
请求访问的进程有限的等待，保证不会饥饿
让权等待
进程不能进入临界区，应立即释放处理机
实现临界区互斥
软件实现方法
单标志法
每个进程进入临界区的权限被另一个程序赋予
存在问题：违反“空闲让进”
双标志先检查
设置一个数组，数组元素用来标记各进程进入临界区的意愿
违反“忙则等待”
双标志后检查
导致双方都进入不了临界区，导致“饥饿”
Peterson算法
违反“让权等待”
进入不了临界区，应该立即释放处理机
如果双方都想争着进入临界区，谦让
硬件实现方法
中断屏蔽方法
关中断、开中断指令
缺点：不适合多处理机，多处理机都需要使用某个临界区
硬件指令方法
TestAndSet指令
Swap指令
功能：交换两个字的内容
信号量机制(实现互斥/同步)
信号量
一个变量，可以用来表示系统中某种资源的数量
原语
一种特殊的程序段，其执行只能一起呵成，不可以被中断
由关中断和开中断指令实现
分类
整型信号量(出现忙等)
用于表示资源数目的整型量S
会出现忙等
记录型信号量(阻塞进程，避免忙等)
不存在忙等的进程同步机制，一个代表资源数目的整型变量value、再增加一个进程列表→链接所有等待该资源的进程
wait()→P操作、signal()→V操作
S.value＜0，运行态转换阻塞态，让出处理机→满足让权等待
信号量实现互斥
使用P、V操作
P操作：wait()
相当于进入区，信号量-1
V操作：signal ()
相当于退出区，信号量+1
信号量实现同步
进程同步：要让各并发进程按照要求有有序地推进
信号量实现前驱关系
经典同步互斥问题
生产者-消费者问题
同步信号量full、同步信号量empty、互斥信号量mutex
问题描述：生产者生成与消费者消费互斥
多生产者-多消费者问题
同步信号量plate、同步信号量apple、同步信号量orange、互斥信号量mutex
读者-写者问题
吸烟问题
哲学家进餐问题
每个进程需要2个或2个以上的临界资源
解决方法
一次只允许4个哲学家同时进餐
奇数位哲学家先拿左边筷子，再拿右边，偶数位哲学家相反(避免都拿左边进入死锁)
当哲学家两只筷子都在时，才允许他用筷子
管程
另一种进程同步工具(实现进程互斥和同步)
管程应用了封装的思想，将进程中复杂的同步互斥问题，隐藏在管程定义的函数之内，对外提供简单易用的接口
需要在管程中定义共享数据(例如：生产者-消费者的缓冲区)
需要在管程内部定义访问这些共享数据的“入口”(类似于函数)
只用通过特定的“入口”才能访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
死锁
概念
多个进程因竞争资源而造成互相等待，各进程无法向前推进(哲学家进餐中的死锁)
饥饿
长期得不到想要的资源，使得进程无法向前推进的情况
死循环
某进程在执行过程中一直跳不出某个循环
死锁产生的必要条件(同时满足4个)
互斥条件
只有对必须互斥使用的资源争抢才会导致死锁
不剥夺条件
进程资源未使用完，不能被其他进程强行夺走，只能主动释放
请求并保持条件
进程已经保持了至少一个资源，但又提出新的资源请求，而该资源已经被其他进程占有，此时被阻塞
循环等待条件
存在一种资源循环等待链(哲学家进餐-都选左手边筷子)
循环等待未必死锁，死锁一定循环等待
死锁产生的原因
系统资源竞争
进程推进顺序非法
进程1申请资源R1，进程2申请资源R2，进程1又申请资源R2，进程2申请资源R1(死锁)
死锁的处理策略
死锁预防(静态策略)
破坏死锁的4个必要条件中的一个或多个
破坏 互斥条件
把互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态
使用SPOOLing技术
破坏 不剥夺条件
方案一：一个进程如果请求新的资源但得不到满足时，它必须立即释放保持的所有资源(求而不得，主动释放)
方案二：当某个进程需要的资源被其他进程占用，强行剥夺其他进程的资源(欲求，则强行剥夺)
破坏 请求并保持条件
静态分配方法：一次申请完所需要的全部资源，资源未满足前，不让他运行；投入运行后资源一直归他
破坏 循环等待条件
顺序资源分配法：给系统资源编号，进程必须按照编号递增的顺序请求资源
缺点：新增设备，需要重新编号
避免死锁(动态策略)
用某种方法避免系统进入不安全的状态(银行家算法)
银行家算法
检查此次申请是否超过之前声明的最大需求
系统安全状态
系统按照某种进程推进顺序，为每个进程分配到所需资源，直到满足每个进程对资源的最大需求，使每个进程都可顺序完成
不安全状态不一定是死锁状态，不安全状态后，可能进入死锁状态
安全序列：使系统处于安全状态的进程推进顺序
安全性算法
安全序列
死锁的检测及解除
允许死锁发生，操作系统检查并解除
死锁的检测
资源分配图(数据结构)
两种结点
进程结点：对应一个进程
○
资源结点：对应一类资源，可能有多个
□
两种边
进程结点→资源结点(请求边)：表示进程想申请几个资源
资源结点→进程结点(分配边)：表示已经为进程分配了几个资源
死锁检测算法
死锁的解除
资源剥夺法
挂起某些死锁进程，抢占它的资源
撤销进程法
进程回退法
让一个或多个回退到可以避免死锁的地步
需要设置回退点，历史记录
进程唯一标识
