操作系统第二章：进程与线程
进程
包含PCB，程序段，内存
包含五个状态：
- 创建态
- 就绪态：等待CPU
- 运行态
- 阻塞态：等待其他资源
- 结束态
进程控制
原语是特殊的程序，执行必须一气呵成，不可中断，通过原语实现进程控制
具有关中断和开中断指令，在这个范围内不会去看是否有中断指令
进程创建
原语内容：
- 申请空白PCB
- 为新进程分配所需资源
- 初始化PCB
- 将PCB插入就绪队列
进程撤销
原语内容：
- 从PCB集合中找到终止进程的PCB
- 若进程正在运行，立刻剥夺CPU，将CPU分配给其他进程
- 终止其所有子进程
- 将该进程拥有的所有资源归还给父进程或操作系统
- 删除PCB
进程的阻塞和唤醒
阻塞：
- 找到要阻塞进程的PCB
- 保护进程运行现场，将PCB状态信息设置为阻塞态，暂时停止进程运行
- 将PCB插入相应事件的等待队列
唤醒：
- 在事件等待队列种找到PCB
- 将PCB从等待队列移除，设置进程为就绪态
- 将PCB插入就绪队列，等待被调度
进程的切换
- 将运行环境信息存入PCB
- PCB移入相应队列
- 选择另一个进程执行，并更新其PCB
- 根据PCB恢复新进程所需的运行环境
进程通信
共享存储
申请共享存储区/数据结构，可以被其他进程所共享，但各个进程对共享空间的访问是互斥的，由进程本身的PV操作来实现。
分为基于存储区的共享和基于数据结构的共享
消息传递
进程间的数据交换以格式化的消息为单位，进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
消息由消息头和消息体构成，消息头包括发送进程ID、接受进程的ID、消息长度等格式化信息
分为直接通信方式和间接通信方式，间接通信方式即通过信箱进行传递
管道通信
管道是一个特殊的共享文件（pipe）,再内存中开辟了一个大小固定的内存缓冲区，是一个循环队列
单个管道只能单向传输，称为半双工通信，两个管道可实现双向通信，称为全双工通信
互斥由操作系统来进行，只要管道没写满就可以往里面写，只要没读完就可以继续读取，读取看作出队
信号
用于通知进程某个特定事件已经发生，进程收到一个新号后，对该信号进行处理
信号的发送与保存
信号处理时机
线程
是基本的CPU的执行单元，是程序执行流的最小单位
进程是资源分配的基本单位，线程是调度的基本单位
线程控制块TCB
线程的实现方式
只有内核级线程才是处理机的分配单位
用户级线程
应用程序创建线程库来管理各个线程，切换在用户态当中进行即可，不需要切换到内核态，不需要CPU变态，但是一个进程阻塞，其他线程也会被阻塞
内核级线程
一个被阻塞，其他的还能正常运行，多核的情况下可以将不同进程分派到不同核心进运行
线程切换需要操作系统来实现，先要用户->内核，再切换内核级线程，再从内核->用户，运行用户级线程切换成本高
多线程模型
- 一对一：一个用户级线程对应一个内核级线程，开销大，不会阻塞
- 多对一：多个用户级线程对应一个内核级线程，就相当于一个内核级线程管理线程库
- 多对多：将n个用户级线程映射到m个内核级线程，每个内核级线程有n个用户级线程，就是多对一的批量版，不会阻塞
线程状态转化
分为：就绪，阻塞，运行
线程控制块（TCB）
调度
三层调度
高级/作业调度：
中级/内存调度：
挂起可分为就绪挂起、阻塞挂起
低级/进程/处理机调度
进程调度时机
进程调度方式
- 非剥夺式调度/非抢占式调度，只允许进程主动放弃处理机
- 剥夺式调度/抢占式调度，可以强制停止正在执行的进程，将处理机分配给更重要紧迫的进程
包含选择一个进程和进程切换两个步骤
进程切换完成了
- 对原来运行进程各种数据的保存
- 对新的进程各种数据的恢复
调度指标
CPU利用率
CPU忙碌的时间，$利用率=\frac{忙碌时间}{总时间}$，其他设备的利用率也是如此
系统吞吐量
单位时间内完成作业的数量，$系统吞吐量=\frac{总共完成的作业数}{总共花费的时间}$
周转时间
作业被提交给系统开始，到作业完成的时间
具体包含
- 作业再外存等待作业调度的时间
- 进程再就绪队列上等待进程调度的时间，就绪
- 进程再CPU上执行的时间，运行
- 进程等待I/O操作完成的时间，阻塞
$平均周转时间=\frac{各作业周转时间之和}{作业数}$
$带权周转时间=\frac{作业周转时间}{作业实际运行时间}$
$平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}$
等待时间
进程/作业等待处理机状态时间之和，对进程来说就是一开始就绪队列等待的时间，对于作业来说还要加上在作业后备队列的等待时间
$平均等待时间=\frac{各作业/进程等待时间}{作业/进程数}$
响应时间
从用户提交到首次产生响应所用的时间
调度算法
先来先服务（FCFS）
按照作业/进程到达的先后顺序进行服务，作业按到达后备队列的顺序，进程按到达就绪队列的顺序
为非抢占式算法，公平，但是短作业的等待时间可能过长，不会导致饥饿（长期得不到服务）
短作业优先（SJF）
最短的作业和进程优先得到服务，用于进程调度时是短进程优先算法（SPF）
默认为非抢占式，也有抢占式的版本：最短剩余时间优先算法（SRTN）
“最短的”平均等待时间，，平均周转时间，平均带权周转时间，但是对长作业不利，可能导致饥饿现象
高响应比优先（HRRN）
同时考虑到等待和要求服务的时间，$响应比=\frac{等待时间+要求服务时间}{要求服务时间}$，计算当前时刻的响应比，让最大的上
非抢占式，整合了先来先服务和短作业优先的优点，适用于早期的批处理系统
若要求服务时间相同，则相当于先来先服务，若等待时间相同，就是短作业优先
时间片轮转调度算法（RR）
按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，分时系统用于进程调度
抢占式算法，公平，响应快，适用于分时系统，高频的切换有一定的开销且不区分任务紧急程度，不会导致饥饿
默认先到达的进程先插入就绪队列，然后再是又阻塞转为就绪的，或者运行转为就绪的
时间片要让千幻进程的开销占比不超过1%
在分时操作系统当中更注重于响应时间，而不是周转时间
优先级调度算法
调度时选择优先级最高的作业/进程，优先级是否发生改变可分为动态优先级和静态优先级
抢占式和非抢占式都有，可以灵活区分优先级，但是如果一直有高优先级进来会导致饥饿
多级反馈队列调度算法
- 设计多级就绪队列，各个队列时间片从小到大，从第一级开始处理
- 新进程到达后进入第一级队列队尾，按照先来先服务等待分配时间片，若一次未结束则进入下一级队列队尾，若已经在最后一级，则放到这一级的末尾
- 在运行当中有更高优先级的到达则会被抢占，被抢占的会放到本级队尾
用于进程调度，抢占式算法，一直有进程进来会导致饥饿
多级队列调度算法
设置多个队列，不同进程插入对应队列，可采取固定优先级或时间片划分
- 高优先级空时低优先级进程才能被调度
- 给不同队列的时间片划分不同
各个队列里可以采用不同的调度策略
多处理机调度
多处理机——多核CPU
负载均衡：尽可能让每一个CPU都同等忙碌
处理机亲和性：尽可能让一个进程调度到同一CPU上运行
通过公共就绪队列，私有就绪队列实现
公共就绪队列
所有CPU共享一个就绪进程队列（位于内核区）
每个CPU调度的时候从这个队列里取，调用后上锁保证互斥访问
天然实现负载均衡，但是各个进程频繁切换CPU运行
私有就绪队列
每个CPU都有一个私有就绪队列
推迁移策略：一个特定的系统程序周期性检查每个处理器的负载，负载不平衡时候从繁忙的队列调到空闲队列
拉迁移：每个CPU运行调度程序时，周期性检查自身负载与其他CPU负载，其他的忙，自己闲则会拉一些过来
同步与互斥
进程同步
进程互斥
对临界资源的互斥访问，可以再逻辑上分为如下四个部分：
- 进入区：检查是否可以进入临界区，可进入则设置正在访问临界资源的标志
- 临界区：访问临界资源的那段代码
- 退出区：负责接触正在访问临界资源的标志
- 剩余区：做其他处理
互斥原则：
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待：进程无法进入临界区时，应立即释放处理机，防止进程忙等待
进程互斥软件实现方式
单标志法
进程访问完临界区后会把临界区的权限转交给另一个进程，每个进入临界区的权限智能被另一个进程赋予
双标志先检查法
设置布尔型数组，记录各个进程是否要进入临界区，每个进程在进入临界区前先检查当前是否有其他进程想要进入，没有则把自身标记为True,开始访问临界区
双标志后检查法
相对于先检查法，采取先上锁后检查
Peterson算法
进程互斥硬件实现方法
- 中断屏蔽方法
利用“开/关中断指令”实现，在进程开始访问临界区到结束访问都不允许被中断
- TestAndSet/TSL指令
用硬件实现，在执行过程不允许被中断
- Swap/Exchange/XCHG指令
信号
信号量机制
整型信号量
记录型信号量
信号量机制实现进程互斥
信号量机制实现进程同步
同步互斥例题
生产者—消费者问题
多生产者—多消费者问题
读者—写者问题
哲学者进餐问题
管程
用于实现进程的互斥与同步，包含:
- 局部与管程的共享数据结构说明
- 对该数据结构进行一组操作的过程（函数）
- 对局部与管程的共享数据设置初始值的语句
- 管程的名字
类似于类
基本特征：
- 局部于管程的数据只能被局部于管程的过程所访问
- 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程
死锁
死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。
死循环：某进程执行过程中一直跳不出某个循环的现象
死锁产生的必要条件
互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
不剥夺条件：进程所获得的资源在未使用完之前，不能又其他进程强行夺走，只能主动释放
请求和保持条件：进程已经至少持有了一个资源，又申请新的资源，但是该资源被其他进程占有，此时请求进程被阻塞，但是对自己已有的资源保持不放
循环等待：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求
避免死锁
安全序列：系统按照银行家算法，每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。
如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁
死锁的检测
死锁的解除
- 资源剥夺法：挂起(暂时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。应防止被挂起的进程长时间得不到资源而饥饿。
- 撤销资源法：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。
- 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程3.的历史信息，设置还原点。