目录
操作系统概述已经更新，传送门：电子科技大学操作系统期末复习笔记（一）：操作系统概述
本复习笔记基于电子科技大学计算机操作系统-教学大纲（2022）中的课程模块部分，分为五大章节，分别是：
- CM1：操作系统概念。操作系统基本功能、操作系统发展历史及趋势、操作系统主流架构、常见操作系统特点、操作系统安全机制。
- CM2：进程管理。进程概念、线程概念、进程生命周期、进程调度算法、进程同步互斥、进程间通信和死锁。
- CM3：内存管理。内存空间的概念、连续分配、离散分配（分页管理、分段管理、段页式管理）、虚拟存储管理和页面置换算法。
- CM4：设备管理。I/O 系统结构、缓冲管理、磁盘结构和磁盘调度算法。
- CM5：文件管理。文件系统的作用、逻辑结构、物理结构、目录、文件共享和文件系统的一致性。
本节要点在CM2，大致内容如下：
第二章 进程与并发控制（20 学时，多媒体课件结合板书面授）CM21、主要内容程序顺序执行、程序并发执行、进程的定义与特征、进程的基本状态、进程的挂起状态、进程控制块、进程的创建、进程的终止、进程的阻塞与唤醒、进程的挂起与激活。临界资源、临界区、利用软件和硬件解决进程互斥问题、整型信号量机制、记录型信号量机制、信号量集机制、生产者－消费者问题、读者和写者问题、哲学家进餐问题、管程机制、进程通信的类型、直接通信和间接通信方式、消息传递系统中的几个问题、消息缓冲队列通信机制。调度的类型、调度队列模型、调度方式和各种调度算法、产生死锁的原因和必要条件、处理死锁的基本方法、死锁的预防和避免、死锁的检测与解除。进程调度算法。满足实时系统要求时，应选择适合实时系统中的调度算法。线程的概念、线程间的同步和通信、用户线程和内核支持线程的概念。2、应达到的要求记忆：进程的分配方式、管程机制。理解：进程的并发执行与控制；实时系统的类型及实时调度算法。线程的概念、线程间的同步和通信、用户线程和内核支持线程的概念。应用：程序的执行、进程的定义与特征、进程的基本状态、进程控制块、操作系统内核、进程的创建、进程的终止、进程的阻塞与唤醒、进程的挂起与激活、线程与进程、进程调度算法。 临界资源、临界区、进程互斥问题、信号量的应用。分析：进程调度和死锁、处理死锁的基本方法。进程（线程）的调度算法、生产者/消费者问题、读者和写者问题、哲学家进餐问题。
可以看到内容还是很多的，这部分也是重点内容，涉及到7个PPT那就分7个标题吧。
程序执行有固定的时序
特征：顺序性、封闭性、可再现性
- 有向无循环图
- 表示方式：
- p1→p2
- →={(p1,p2)| p1 必须在p2开始前完成}
- 节点表示：一条语句，一个程序段，一个进程
特征：间断性、失去封闭性（主要由共享资源引起）、不可再现性（并发程序可能对共享资源做不同的修改）
例子：
A在B之前，则N分别为 n+1, n+1, 0
A在B之后，则N分别为 n, 0, 1
A在B中间，则N分别为 n, n+1, 0
资源共享：系统中资源被多个程序使用
独立性和制约性：独立的相对速度、起始时间，程序之间相互作用/制约
程序与程序的执行不再一一对应
引入并发的目的：提高资源利用率和系统效率
例子：
定义：一个具有独立功能的程序在一个数据集合上的一次动态执行的过程。
多进程可以i提高对硬件资源的利用率，但会增加额外的时间空间开销，增加OS的复杂性。
特征：动态性、独立性、并发性、异步性、结构化
进程=代码段+数据段+PCB（进程控制块）
一个程序可以对应多个进程（进程：程序=n：1）
进程是资源申请和系统调度的基本单位
| 进程 | 程序 |
| 动态的 | 静态的 |
| 程序的执行 | 代码的集合 |
| 暂时的 | 永久的 |
| 状态变化过程 | 可以长久保存 |
| 真实地描述并发 | 不能真实地描述 |
| 可以创建其他进程 | 不可创建其他程序 |
进程的三种基本状态：就绪、执行、等待/阻塞
进程状态图：
一些与硬件紧密相关的模块、运行频率较高的模块、共用基本操作模块等常驻内存的且便于提高操作系统运行效能的软件，称为操作系统内核。
- 进程管理：创建；撤销；调度；控制
- 存储管理：分配/回收空间；虚拟存储管理
- I/O设备管理：设备、通道的分配/回收；设备的管理；虚拟设备的实现
- 中断处理：操作系统的重要活动都依赖于中断
- 定义：由若干机器指令构成以完成一段特定功能，且在执行过程中不可分割。
- 原子操作：一个操作中的所有动作，要么全做，要么不做（All-or-None）
- 单机系统（屏蔽中断）
- 单条指令
- 以屏蔽中断的方式来保证操作的原子性
- 多核系统（内存栅障）
- 一个CPU核执行原子操作时，其他CPU核必须不对指定的内存进行操作，避免数据竞争问题
操作系统管理计算机资源常用：
- 表格：（或数据结构）记载各资源信息
- 代码：对资源管理、维护、更新等
PCB：Process Control Block，是一个数据结构。
- 是进程存在的唯一标志，且常驻内存
PCB的组织方式
- 链接方式
- 把具有同一状态的PCB用其中的链接指针链接成一个队列
- 索引方式
- 系统根据所有进程的状态建立几张索引表
描述了进程的家族关系
- 子进程可继承父进程的资源
- 父进程的撤销会撤销全部子进程
- 根进程：init，launched，pid=1
- 孤儿进程直接托管给根进程
创建场景：用户登录/作业调度/提供服务/应用请求
创建过程：申请空白PCB，分配资源，初始化PCB，插入就绪队列
大多数程序中，系统调用的fork和exec是结合在一起使用的：父进程生成一个子进程，再通过调用exec覆盖该子进程。
fork()：创建新进程
- 调用格式：pid = fork()
- 调用fork后，父子进程均在下一条语句上继续运行
- 父子进程fork返回值不同
- 失败返回-1
- 在子进程中返回时，pid为0
- 在父进程返回时，为其创建的子进程pid
fork()：两个关键点
- 运行顺序：父子进程运行无关，运行顺序也不固定。（若要运行顺序一定，需要用到进程间通信）
- 数据共享：除子进程标识符和PCB特性参数不同外，子进程是父进程的精确复制
例子：
exec()：执行一个文件的调用
- 子进程可以通过exec()调用加载新的程序文件
- 子进程可以拥有自己的可执行代码，用新进程覆盖调用进程
- 调用参数：文件+命令行参数。成功：不返回；失败：返回-1
exec指的是一组函数，一共有6个，分别是
#include <unistd.h> int execl(const char *path, const char *arg, ...); int execlp(const char *file, const char *arg, ...); int execle(const char *path, const char *arg, ..., char *const envp[]); int execv(const char *path, char *const argv[]); int execvp(const char *file, char *const argv[]); int execve(const char *path, char *const argv[], char *const envp[]);与一般情况不同，exec函数族的函数执行成功后不会返回，因为调用进程的实体，包括代码段，数据段和堆栈等都已经被新的内容取代，只留下进程ID等一些表面上的信息仍保持原样。
只有调用失败了，它们才会返回一个-1，从原程序的调用点接着往下执行。
例子:
中止情况：正常结束/异常结束/外界干预
- 正常结束：exit/halt/logoff
- 异常结束：无可用存储器/越界/保护错误/算术错误/IO失败/无效指令/特权指令
- 外界干预：kill进程/父进程中止
中止过程：
- 检索PCB检查进程状态→执行态改为中止→检查有无子孙需要中止→归还资源给父进程或系统→从PCB队列中移除
- 系统调用exit(int ret)，返回ret到父进程，释放所有资源，父进程通过wait()等待子进程结束。（wait(pid, status)，ret）
例子：
Process A: void main(){ printf("Hello World!"); } Process B: void main(){ if((child=fork())<0){ printf("Fork Failed!"); } else if(child==0){ if(execv(A)<0){ printf("Execv Failed!"); } else{ printf("Bye!") } } }
- 阻塞/唤醒，时间片
- 保存现场/恢复现场
系统调用：会引起从用户态进入核心态
进程：线程=1：n
- 减少并发执行时的时空开销（进程的开销较大）
- 线程是系统独立调度的基本单位
- 基本不用有系统资源，只有少量资源，共享其所属进程所拥有的全部资源
【回顾】
进程是拥有资源和独立运行的基本单位，线程是系统独立调度的基本单位！！！
- 单线程进程，包括进程控制块和用户地址空间，以及用户栈和内核栈。
- 多线程环境中，有一个与进程相关联的进程控制块和用户地址空间，每个线程都有一个独立的栈和独立的控制块，包含寄存器值、优先级和其他与线程相关的状态信息。
- 进程中的所有线程共享该进程的资源，驻留在同一块地址空间中，并且可以访问到相同的数据。
- 线程阻塞不一定会引起进程阻塞。
- 执行状态、阻塞状态、就绪状态等
- 阻塞：当线程需要等待一个事件时，它将阻塞，此时处理器执行另一个就绪线程
- 线程切换时保存的线程信息：
- 一个执行栈
- 每个线程静态存储局部变量
- 对存储器和其进程资源的访问
- 派生：产生一个新进程时，同时为其派生一个线程，随后还可以派生另一个线程，新线程被放置在就绪队列中
- 结束：线程完成时，其寄存器信息和栈都被释放
- 内核级线程：每个线程在内核看来都是一个进程
- 用户级线程：内核无法感知，用户自己控制
不同点：
- 调度开销
- 内核级线程切换类似于进程切换，开销较大
- 用户级线程切换在同一用户级进程中，无需进入内核，更快
- 执行时间
- 用户级线程以进程为单位平均分配时间，对线程间并发不利（单CPU）
- 内核级线程以线程为单位分配时间（多CPU）
- 并发效率
- 用户线程：线程阻塞导致进程阻塞（内核不知道线程的存在）
- 内核线程：线程阻塞，其他进程/线程仍可运行
分配处理机的任务由进程调度程序完成
处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于进程调度性能的好坏
- 面向用户的原则
- 周转时间：作业提交到完成的时间
- 平均周转时间：
- 平均带权：
越接近1越好，越大越差
：周转时间
：实际运行时间
- 响应时间：（交互式作业）提交请求到首次响应的时间
- 截止时间：开始/完成截止时间
- 优先级：需要抢占/剥夺调度
- 面向系统的原则
- 吞吐量：单位时间完成作业数
- 利用率
- 公平性
- 优先级
先来先服务：FCFS
简单来说，它就是按顺序执行。
评价
- 非抢占调度
- 对长进程有利，不利于短进程
- 适合CPU繁忙型进程，不适合I/O繁忙型进程（系统角度）
- 不能直接用于分时系统
- 往往与其它调度算法综合使用
例子：
进程名
产生时刻
服务时间
P1
0
2
P2
1
6
P3
2
1
P4
3
5
平均周转时间：((2-0)+(8-1)+(9-2)+(14-3))/4 = 6.75
平均等待时间：(0+1+6+6)/4 = 3.25 (注意区分，可能会出审题性错误)
短作业优先：SPF/SJF
执行时间短的先执行
评价
- 有利于短进程，提高了平均周转时间
- 长进程可能被饿死（starvation）
- 需要知道或估计每个进程的处理时间。
例子：
平均周转时间：(2+13+1+5)/4 = 5.25
平均等待时间：(0+7+0+0)/4 = 1.75
时间片轮转调度：TSRR
每过固定时间就换下一个进程（按FSCS）
专门为分时系统设计（FCFS的优化）
- 时间片长度变化的影响
- 过长：退化为FCFS，进程在一个时间片内执行完
- 过短：用户的一次请求需要多个时间片才能处理完，上下文切换次数增加
- 评价
- 相对公平
- 偏向于CPU型的进程
- 中断开销
例子：
q指的是时间片长度
平均周转时间：(4+16+12+13+5)/5 = 10
平均等待时间：(1+10+9+9+5)/5 = 6.8
平均周转时间：(3+15+7+14+11)/5 = 10
平均等待时间：(0+9+3+9+9)/5 = 6
最短剩余时间调度：SRT
对SJF加入剥夺机制：当新进程进入时，可能比当前运行的进程具有更短的剩余时间
- 优点
- 不偏爱长进程，也不像RR产生额外中断，减少了开销。
- 周转时间方面，比SJF好，短作业可以立即被选择执行。
- 问题
- 需要知道或估计每个进程所需处理时间；
- 若持续有短进程存在，长进程可能被饿死；
- 记录过去的服务时间（以便计算剩余时间）→ 增加了开销。
基于优先权/优先级的调度算法
就是先运行优先级高的
- 优先级
- 每个进程设有一个优先级，调度程序选择具有较高优先级的进程。
- 静态优先级(static)
- 优先数在进程创建时分配，生存期内不变。
- 响应速度慢，开销小。
- 适合批处理进程
- 动态优先级(dynamic)
- 进程创建时继承优先级，生存期内可以修改。
- 响应速度快，开销大。
- 问题
- 低优先级的进程可能会饿死（无穷阻塞）
- 改进
- 一个进程的优先级随着它的时间或执行历史而变化——老化策略(aging)。
- 执行过程中不断调整其优先级 （如：优先级随执行时间增加而下降，随等待时间增加而升高。）
- 优点：长短兼顾
高响应比优先算法：HRRN
响应比R = 周转时间/服务时间 = (w+s)/s
(w: 等待时间 ；s: 服务时间)
就是先运行响应比高的（综合考虑等待时间和作业长度）
- 评价
- FCFS和SJF的结合，克服了两种算法的缺点
- 公平，吞吐率大
- 需要估计服务时间，增加了计算，增加了开销
多级队列调度算法
将就绪队列分成多个独立队列，进程所属的队列固定。通过对各队列的区别对待，达到一个综合的调度目标。
- 策略
- 不同队列可有不同的调度策略 （如前台队列用RR，后台队列用FCFS。）
- 队列之间的区别：采用固定优先级、可抢占调度来实现 （如前台队列优先级高于后台队列优先级。 ）
- 只有优先级高的队列中没有进程时，才可以调度优先级低的队列中的进程
多级反馈队列调度：MFQ
多级反馈队列算法是多级队列和动态优先级算法的综合和发展。
按时间片、等待时间，使用动态优先级机制；调度基于剥夺原则。
- 策略
- 不同队列可有不同的调度策略 （如前台队列用RR，后台队列用FCFS。）
- 多个就绪队列，进程所属队列可变，即进程可以在不同的就绪队列之间移动
- 多个就绪队列分别赋予不同的优先级
- 队列优先级逐级降低，而时间片长度逐级递增
调度过程
- 新进程进入后，先放入队列0的末尾，按RR顺序调度；
- 若执行过程中阻塞，则离开队列，被唤醒后，放入同一优先级队列尾部；
- 若在规定时间片未能执行完，则降低优先级投入队列1的末尾，同样按RR算法调度；如此下去，直到最后的队列；
- 若只有1个进程，则不降级；
- 可有效应对I/O繁忙进程。
- 最后队列按FCFS或者RR（但不再降级）调度直到完成；
- 若在最后队列等待时间过长，提升优先级；
- 仅当较高优先级的队列为空，才调度较低优先级的进程执行；
- 当前进程一旦开始执行，时间片结束前不被抢占；
- 若按优先级调度的进程为上一个被抢占的进程，则忽略之，调度下一个候选；
假定系统中有m个周期性的实时任务，它们的处理时间为Ci，周期为Pi，则在单/多处理机情况下，可调度的必要条件：
- 紧密耦合
- 共享RAM和I/O
- 高速总线和交叉开关连接
- 松弛耦合
- 独立RAM和I/O
- 通道和通信线路连接
- 对称多处理器系统 SMP：Symmetric Multiprocessing
- 非对称多处理器系统 AMP：Asymmetric Multiprocessing
- SMP中进程分配方式
- 静态分配
- 动态分配：可防止系统中多个处理器忙闲不均
- 非SMP中进程分配方式
- 进程调度在主处理器上执行
- 有潜在的不可靠性
各个处理机自行在就绪队列中取任务（先纵向看，再横向看）。
优点：简单，分布式调度，多个CPU利用率都好
缺点：瓶颈问题（单队列→共享资源→锁） 低效性：cache affinity （下图为改进）
每个CPU一个队列：没有SQMS的问题，但是可能负载不均衡，导致资源分配不合理。
- 优点：
- 对相互合作的进（线）程组调度，可以减小切换，减小系统开销。
- 每次分配一组CPU，减少了调度频率。
- 分配时间
- 面向程序
- 面向线程：使处理机利用率更高。
- 特点：每个进（线）程专用处理机，使其切换小，提高效率。
- 主要用于大型计算，实时系统
- Sony PlayStation 3 (PPU/SPU) → CELL
- 神威太湖之光：众核（4+256)
进程/线程是计算机中的独立个体：异步性（并发性）
资源是计算机中的稀缺个体：独占性（不可复用性）
进程/线程协作完成任务（协作）
并发控制：进程/线程在推进时的相互制约关系
并发执行进程能有效地共享资源和相互合作，并按一定顺序执行。
- 进程间的制约关系
- 间接制约：资源共享→互斥
- 直接制约：进程合作→同步
- 临界资源（Critical Resource）
- 一次仅允许一个进程访问的资源
- 临界区（Critical Section）
- 进程中访问临界资源的代码段
- 忙等、饥饿、死锁
- 活锁
- 两个或多个进程不断更改其状态以响应其他进程的更改而不执行任何有用工作的情况。
- 同步原则
进程通过执行相应的程序指令，实现与其他进程的互斥与同步
- 屏蔽中断：确保互斥执行
- 缺点：
- 系统无法响应外部请求
- 无法接受异常，处理系统故障
- 无法切换进程→性能下降
- 不支持多处理机
- 机器指令
- 原子性：all-or-nothing
- 单处理器：一个周期内完成的指令
- 多处理器：LOCK总线
- Test & Set
- 测试某个变量的值，如果为0，则置1，并返回当前值
- Exchange
- 原子性地交换寄存器和内存的值
- 优点：
- 支持多处理机
- 简单易证明
- 支持多临界区
- 缺点：
- 忙等现象
- 饥饿现象
- 死锁现象
- 原理：
- 多进程通过信号传递协调工作，根据信号指示停止执行（阻塞等待）或者向前推进（唤醒）。
- 信号：信号量s
- +：资源数量
- -：排队数量
- 原语：
- wait(s)：等待信号，并占有资源 ——>P操作
- signal(s)：释放资源，并激发信号 ——>V操作
- 分类
- 整数型信号量
- 记录型信号量
- AND型信号量
- 将进程在整个运行过程中需要的所有资源，一次性全都地分配给进程，待进程使用完后再一起释放。
- 只要有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给它
- 原子操作
- 要么全部分配到进程，要么全不分配
- 在wait操作中，增加一个AND条件，故称为AND同步，或称为同时wait操作
- 信号量正负的含义
- s.value ≥ 0：是可以在不挂起的情况下执行等待的进程数。
- s.value < 0：s.value 的大小是 s.queue 中挂起的进程数。
- 信号量集
- 采用信号量集来控制，可以分配多个资源
- swait(S1, t1, d1, …, Sn, tn, dn） ti：资源下限； di：需求量
管程的组成
- 局部于该管程的共享数据，这些数据表示了相应资源的状态；
- 针对上述数据的一组过程；
- 对局部于该管程的数据的初始化。
管程的特点
- 模块化（Modularization）
- 管程是一个基本程序单位，可以单独编译;
- 抽象数据类型（Abstraction)
- 管程中不仅有数据，而且有对数据的操作;
- 信息隐藏（Encapsulation）
- 管程外可以调用管程内部定义的函数，但函数具体实现外部不可见;
- 局部数据变量只能被管程的过程访问，任何外部过程都不能访问。
管程的同步
- 进程通过调用管程的一个过程进入管程；
- 在任何时候，只能有一个进程在管程中执行；调用管程的任何其他进程都被挂起，以等待管程变成可用。
- 条件变量提供同步支持（非默认锁）。条件变量包含在管程中，并且只有在管程中才能被访问：
- cwait(x)：调用进程的执行在条件x上挂起，管程现在可被另一进程使用。
- csignal(x)：恢复阻塞在x上的进程。
展示一些信号量实例，也是重点考察的地方
观察者和报告者是两个并发执行的进程。 观察者不断观察并对通过的卡车计数； 报告者不停地将观察者的计数打印，并归零。 请用P、V原语进行正确描述。
图书馆有N个座位，一张登记表，要求： 读者进入时需先登记，取得座位号； 出来时注销 用P、V原语描述读者的使用过程。
司机启动车辆的动作必须于售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。
生产者/消费者模型：
生产者：满则等待，空则填充
消费者：空则等待，有则获取
不允许同时进入缓冲区
无限缓冲：
有限循环/环形缓冲区：
有3个进程PA，PB和PC合作解决文件打印问题：
PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录;
PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；
PC将缓冲区2的内容打印出来，每执行一次打印一个记录。
缓冲区的大小等于一个记录大小。
请用P，V操作来保证文件的正确打印。
信号量：empty1，empty2：分别表示缓冲区1及缓冲区2是否为空，初值为1。
full1，full2：分别表示缓冲区1及缓冲区2是否有记录可供处理，初值为0。
mutex1，mutex2：分别表示缓冲区1及缓冲区2的访问控制，初值为1。
- 资源数量：资源信号量
- 资源访问：互斥信号量
- 先申请资源，再申请访问权
- 资源信号量P、V操作分布在不同进程
- 互斥信号量P、V操作出现在同一进程
三个角色：一个共享的数据区； Reader: 只读取这个数据区的进程； Writer: 只往数据区中写数据的进程；
三个条件：多个Reader可同时读数据区； 一次只有一个Writer可以往数据区写； 数据区不允许同时读写。（“读－写” 互斥；“写－写” 互斥；“读－读” 允许）
一旦有读者正在读数据，则允许随后的读者进入读数据；只有当全部读者退出，才允许写者进入写数据；导致写者饥饿
信号量设置：
wsem：互斥信号量，用于Writers间互斥，Writers和Readers互斥
readcount：统计同时读数据的Readers个数
mutex：对变量readcount互斥算术操作
int readcount=0；
semaphore mutex = 1, wsem=1;
void reader() {
while (1) {
P(mutex);
readcount++;
if (readcount==1) P(wsem);
V(mutex);
READ;
P(mutex);
readcount--;
if (readcount==0) V(wsem);
V(mutex);
}
}
void writer() {
while (1) {
P(wsem);
WRITE;
V(wsem);
}
}当至少有一个写者声明想写数据时，则不再允许新的读者进入读数据。例如：队列：（尾)WWRRW(头)，让三个W进程能优先于R进程写数据。解决了写者饥饿问题，但降低了并发程度，系统的并发性能较差。
信号量设置:
wsem：互斥信号量，用于Writers间互斥，Reader互斥Writers
rsem：互斥信号量，当至少有一个写者申请写数据时互斥新的读者进入读数据。第一个写者受rsem影响，一旦有第一个写者，后续写者不受rsem其影响。但是读者需要在rsem上排队。
mwc：用于控制writecount互斥算术操作
mrc：用于控制readcount互斥算术操作
z: 对读者进行控制，防止在rsem上出现读进程的长队列，否则写进程不能跳过这个队列
int readcount, writecount;
semaphore mrc=l, mwc=1, z=1, wsem=1, rsem=l;
void reader( ) {
while (1) {
P(z);
P(rsem);
P(mrc);
readcount++;
if (readcount == 1) P(wsem);
V(mrc);
V(rsem)；
V(z);
READ;
P(mrc);
readcount--;
if (readcount == 0) V(wsem);
V(mrc);
}
}
void writer( ) {
while (1) {
P(mwc);
writecount++;
if (writecount == 1) P(rsem);
V(mwc);
P(wsem);
WRITE;
V(wsem);
P(mwc);
writecount--;
if (writecount == 0) V(rsem);
V(mwc);
}
}
写过程中，若其它读者、写者到来，则按到达顺序处理
信号量设置：
w：互斥信号量，用于Writers间互斥，Reader互斥Writers
readcount：统计同时读数据的Readers个数
mrc：对变量readcount互斥算术操作
r：互斥信号量，确定Writer 、Reader请求顺序
在读者优先中，wsem只对第一个读者起阻塞作用，后续读者不受其影响。为了保证按照到达顺序处理，故公平优先方式设置wrsem,读者／写者按到达顺序在wrsem上排队。
int readcount = 0;
semaphore mrc = 1, r = 1, w = 1;
READER {
P(r);
P(mrc);
readcount++;
if (readcount == 1) P(w);
V(mrc);
V(r);
Read();
P(mrc);
readcount--;
if (readcount == 0) V(w);
V(mrc);
}
WRITER {
P(r);
P(w);
Write();
V(w);
V(r);
}
角色和资源：一个理发师 一个理发椅 一排座位 随机到来的客户
场景：理发师：有客干活，无客睡觉；客户：唤醒理发师，有位等待，无位离开
此问题无死锁，有饥饿（以排队方式解决饥饿问题）
/* # of customers waiting */
semaphore customers = 0;
/* barber status */
semaphore barbers = 0;
/* mutual exclusion to access seats */
semaphore mutex = 1;
/* # of available seats. */
int nas = N;
void barber(void) {
while (TRUE) {
P(customers);
P(mutex);
nas++;
V(barbers);
V(mutex);
cut_hair();
}
}
void customer(void) {
P(mutex);
if (nas > 0) {
nas--;
V(customers);
V(mutex);
P(barbers);
get_haircut();
} else {
V(mutex);
leave_shop();
}
}
哲学家就餐问题可以用来解释死锁和资源耗尽。
描述：5个哲学家围坐一张餐桌；5只餐叉（筷子）间隔摆放；思考或进餐；进餐时必须同时拿到两边的餐叉；思考时将餐叉放回原处。
#define N 5
#define LEFT (i-1+N)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
int state[N] = {0, 0, 0, 0, 0};
semaphore mutex = 1;
semaphore s[N]={0,0,0,0,0};
void philosopher(int i){
while (TRUE) {
think();
take_forks(i);
eat();
put_forks(i);
}
}
void take_forks(int i)
{
P(mutex);
state[i] = HUNGRY;
test(i);
V(mutex);
P(s[i]);
}
void put_forks(i)
{
P(mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
V(mutex);
}
void test(int i)
{
if (state[i] == HUNGRY &&
state[LEFT] != EATING &&
state[RIGHT] != EATING) {
state[i] = EATING;
V(s[i]);
}
}
桌子上有一只盘子，最多可以放入N（N>0）个水果
爸爸随机向盘中放入苹果或桔子； 儿子只吃盘中的桔子； 女儿只吃盘中的苹果； 只有盘子中水果数目小于N时，爸爸才可以向盘子中放水果； 仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出相应的水果； 每次只能放入或取出一个水果，不允许多人同时使用盘子。
用P、V操作实现爸爸、儿子和女儿之间的同步与互斥活动。
semaphore mutex = 1; //盘子操作互斥信号量 semaphore apple = 0, orange = 0; //苹果、桔子放入、取出的资源信号量 semaphore empty = N; //盘子中可放入的水果数目 dad() { while (true) { result= prepare _fruit(); //准备水果，result为水果类型 P(empty); //盘子中可放入的水果数目减1 P(mutex); //互斥访问盘子 put a fruit on the plate; //将一个水果放入盘子 V(mutex); //恢复访问盘子 if (result == fruit_apple) //准备的水果为苹果 V(apple); //允许女儿取苹果 else //准备的水果为桔子 V(orange); //允许儿子取桔子 } } son() { while (true) { P(orange); //互斥取桔子 P(mutex); //互斥访问盘子 get an orage from plate(); //取桔子 V(mutex); //恢复访问盘子 V(empty); //盘子中可放入的水果数目加1 } } daughter() { while (true) { P(apple); //互斥取水果 P(mutex); //互斥访问盘子 get an apple from plate(); //取苹果 V(mutex); //恢复访问盘子 V(empty); //盘子中可放入的水果数目加1 } }
桌子上有一只盘子，只能放一只水果
爸爸负责向盘中放苹果，妈妈负责向盘中放桔子。 儿子只吃盘中的桔子，女儿只吃盘中的苹果。 只有盘子为空时，爸爸或妈妈才可以向盘子中放入一个水果。 仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出相应的水果。 同一时刻只能有一个人操作盘子
请用信号量机制实现爸爸、妈妈、儿子和女儿之间的同步与互斥活动。
semaphore plate = 1; //盘子是否有空间 semaphore mutex = 1; semaphore apple = 0, orange = 0; //盘子中是否有苹果、桔子 dad() { while (true) { prepare an apple; P(plate); P(mutex) put the apple on the plate; V(mutex) V(apple); } } mom() { while (true) { prepare an orange; P(plate); P(mutex); put the orange on the plate; V(mutex) V(orange); } } son() { while (true) { P(orange); P(mutex); get an orange; V(mutex); V(plate); } } daughter() { while (true) { P(apple); P(mutex); get an apple; V(mutex); V(plate); } }因为缓冲区大小就为1，所以可以省略mutex信号量。
桌子上有一只盘子 最多可以放入2个水果。
爸爸负责向盘中放苹果，妈妈负责向盘中放桔子，女儿负责取出并消费水果。 当且仅当盘子中同时存在苹果和桔子时，女儿才从盘子中取出并消费水果。 不允多人同时使用盘子
请用信号量机制实现爸爸、妈妈和女儿之间的同步与互斥活动。
semaphore apple = 0, orange = 0; //盘子中是否有苹果、桔子 semaphore empty_apple = 1, empty_orange = 1; //盘子是否可放入苹果、桔子 semaphore mutex = 1; dad(){ while (true) { prepare an apple; P(empty_apple); P(mutex); put an apple on the plate; V(mutex); V(apple); } } mom(){ while (true) { prepare an orange; P(empty_orange); P(mutex); put an orange on the plate; V(mutex); V(orange); } } daughter() { while (true) { P(apple); P(orange); P(mutex); get an apple and an orange from plate; //取水果 V(mutex); V(empty_apple); V(empty_orange); } }这里的mutex不可以省略，缓冲区的大小不为1，资源信号量无法兼顾互斥信号量的工作。
女儿画画，爸爸、妈妈欣赏。
女儿在白板上画完一幅画后，请爸爸、妈妈均欣赏过一遍后，再创作新画。
请用信号量机制实现女儿、爸爸和妈妈之间的同步与互斥活动。
//爸爸、妈妈是否已看过女画的新画 semaphore empty_dad = 1, empty_mom = 1; //是否存在可供爸爸、妈妈看的新画 semaphore full_dad = 0, full_mom = 0; daughter(){ while (true) { P(empty_dad); //爸爸是否看过 P(empty_mom); //妈妈是否看过 draw a new picture on the whiteboard; //画一幅新画 V(full_dad); //爸爸可以看了 V(full_mom); //妈妈可以看了 } } dad() { while (true) { P(full_dad); //白板上是否存在没有看过的画 enjoy the picture on the whiteboard; //看画 V(empty_dad); //爸爸已看过新画 } } mom() { while (true) { P(full_mom); //白板上是否存在没有看过的画 enjoy the picture on the whiteboard; //看画 V(empty_mom); //妈妈已看过新画 } }
有一座东西方向的独木桥，每次只能有一人通过，且不允许行人在桥上停留。东、西两端各有若干行人在等待过桥。请用P、V操作来实现东西两端行人过桥问题。
semaphore mutex = 1; //互斥信号量 void east_west( ) { while (true) { P(mutex); //互斥其他人过桥 walk across the bridge from east to west;//行人从东向西过桥 V(mutex); //允许其他人过桥 } } void west_east( ) { while (true) { P(mutex); //互斥其他人过桥 walk across the bridge from west to east;//行人从西向东过桥 V(mutex); //允许其他人过桥 } }
有一座东西方向的独木桥
同一方向的行人可连续过桥。当某一方向有行人过桥时，另一方向行人必须等待，直到对方全部通过。 桥上没有行人过桥时，任何一端的行人均可上桥。
请用P、V操作来实现东西两端人过桥问题。
int countA=0, countB=0； semaphore mutex=1, muteA=1, mutexB=1; void east_west() { while (1) { P(mutexA); countA++; if (countA==1) P(mutex); V(mutexA); walk across the bridge from east to west; P(mutexA); countA--; if (countA==0) V(mutex); V(mutexA); } } void west_east() { while (1) { P(mutexB); countB++; if (countB==1) P(mutex); V(mutexB); walk across the bridge from west to east; P(mutexB); countB--; if (countB==0) V(mutex); V(mutexB); } }
有一座东西方向的独木桥， 同一方向的行人可连续过桥。
当某一方向有行人过桥时，另一方向行人必须等待。 桥上没有行人时，任何一端的行人均可上桥。 出于安全考虑，独木桥的最大承重为4人，即同时位于桥上的行人数目不能超过4。
请用P、V操作来实现东西两端人过桥问题。
int countA=0, countB=0； semaphore mutex=1, muteA=1, mutexB=1,count=4; void east_west() { while (1) { P(mutexA); countA++; if (countA==1) P(mutex); V(mutexA); P(count); walk across the bridge from east to west; V(count); P(mutexA); countA--; if (countA==0) V(mutex); V(mutexA); } } void west_east() { while (1) { P(mutexB); countB++; if (countB==1) P(mutex); V(mutexB); P(count); walk across the bridge from west to east; V(count); P(mutexB); countB--; if (countB==0) V(mutex); V(mutexB); } }
某寺庙有小和尚和老和尚各若干人，水缸一只，由小和尚提水入缸给老和尚饮用。水缸可容水m桶，水取自同一口水井中。水井径窄，每次仅能容一只水桶取水，水桶总数为n个。若每次提水、取水仅为1桶，试用P, V操作描述小和尚和老和尚提水、取水的活动过程
semaphore mutex1=1, mutex2=1; semaphore empty=m, full=0; semaphore count=n; process 小和尚(i) (i=1，2，…) begin repeat P(empty); //水缸满否? P(count); //取得水桶 P(mutex1); //互斥从井中取水 从井中取水; V(mutex1); P(mutex2); //互斥使用水缸 倒水入缸; V(mutex2); V(count); //归还水桶 V(full); //多了一桶水 until false; end process 老和尚(取水)j(j=1，2，…) begin repeat P(full); //有水吗? P(count); //申请水桶 P(mutex2); //互斥取水 从缸中取水; V(mutex2); V(count); //归还水桶 V(empty); //水缸中少了一桶水 until false; end
N个生产者进程和M个消费者进程共享大小为K的缓冲区，遵循规则如下： 进程之间必须以互斥方式访问缓冲区； 对每1条放入缓冲区的数据，所有消费者都必须接收1次； 缓冲区满时，生产者必须阻塞； 缓冲区空时，消费者必须阻塞。 请用P、V操作实现其同步过程，须说明信号量含义。
Inter Process Communication: IPC 是指进程之间的信息交换
进程通信分为两类：
- 低级通信：以信号量作为通信工具，交换的信息量少。
- 高级通信：操作系统所提供的一组通信命令，高效地传送大量数据。
- 共享存储（Shared Memory）
- 消息传递/消息队列（Message Passing/Message Queue）
- 管道（Pipe）
- 套接字（Socket）
- 文件（File）
- 信号（Signal）
- 内存映射文件（Memory Mapped File）
共享存储：
- 数据交换以格式化的消息为单位；直接利用系统提供的一组通信命令（原语）进行通信。
- 间接通信方式 （Indirect Communication）
- 中介：信箱。
- 发送进程发送给目标进程的消息存放信箱； 接收进程则从该信箱中，取出发送给自己的消息；
- 消息在信箱中安全地保存，只允许核准的用户读取。
- 系统为信箱通信提供了若干条原语，分别用于信箱的创建、撤消和消息的发送、接收等。
- 直接通信方式（Direct Communication）
- 直接把消息发送给目标进程。
- 跨节点的进程间通信
- 套接字（socket）
用于连接一个读进程和一个写进程以实现他们之间通信的共享文件，又名pipe文件。
多个进程在运行过程中因争夺资源而造成的一种僵局（Deadly- Embrace），当进程处于这种僵持状态时，若无外力作用，它们都将无法向前推进。
- 资源不足导致的资源竞争：多个进程所共享的资源不足，引起它们对资源的竞争而产生死锁。
- 并发执行的顺序不当：进程运行过程中，请求和释放资源的顺序不当，而导致进程死锁。
- 资源（R1, R2, . . ., Rm）
- CPU, memory, I/O devices
- 资源Ri拥有的实例数 Wi（instance）
- 进程使用资源的方式
- 请求（request）
- 占用/使用（use）
- 释放（release）
- 重用型资源（Reusable Resource）
- 一次只能供一个进程使用，不会由于使用而耗尽
- 例: CPU、 I/O通道、主存和辅存、 设备、文件、数据库、信号量等数据结构
- 消费型资源（Consumable Resource）
- 可以创建并且可以销毁的资源 数目没有限制，当一个进程得到一个可消费资源后，这个资源就不再存在了
- 例: 中断、信号、 消息、 I/O缓冲区中的信息
RAG: Resource-Allocation Graph
进程：P = {P1, P2, …, Pn}
资源：R = {R1, R2, …, Rm}
资源请求边（request）： Pi → Rj
资源分配边（assignment ）：Rj → Pi
互斥条件
进程对所分配到的资源进行排它性使用。如果此时还有其它进程申请该资源，则只能阻塞，直至占有该资源的进程释放。
占有且等待（请求和保持条件）
进程已经占有了至少一个资源，又提出了新的资源要求，而该资源已被其它进程占有，此时请求进程阻塞，且对已经获得的其它资源保持不放。
非抢占（非剥夺）条件
进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
循环等待条件
在发生死锁时，存在一个进程—资源的封闭的环形链。
以上四条缺一不可。
通过限制申请资源的方法来破坏产生死锁的条件（四个方面）
互斥条件
由资源的固有特性所决定，不能被破坏。
打破“占有和等待”
进程开始运行前一次性地申请全部资源，启动后不再申请。
优点: 简单、易于实现、安全
缺点: 无法预知所需资源的全集；进程可能被阻塞很长时间，等待资源，发生饥饿；资源严重浪费（某个资源可能只用极短时间）
打破“非抢占”
资源拥有者拒绝其它请求后释放资源，或从被申请资源拥有者处抢占
适用条件：资源的状态可保存和恢复，如CPU寄存器、内存空间；不适用于打印机、磁带机
缺点：实现复杂，代价大，反复申请/释放资源，周转时间长，系统吞吐量低；undo、redo
打破“环路等待”
系统把所有资源按类型进行线性排队；所有进程对资源的请求必须严格按资源序号递增的顺序提出，保证任何时刻的资源分配图不出现环路。即：如果一个进程已经分配了R类型的资源，它接下来请求的资源只能是排在R类型之后的资源。
摒弃“环路等待” 方法的问题：资源变化：资源序号要稳定； 资源浪费： 只用第一个和最后一个资源； 使用顺序和申请顺序不一致； 程序设计：考虑申请顺序，编写困难
不需事先破坏产生死锁的条件
在系统运行过程中，对进程发出的每一个资源申请进行检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配（阻塞），否则予以分配。
防止系统进入不安全状态, 从而避免发生死锁。
安全状态：存在安全序列的系统状态
安全序列：一个进程序列{P1，…，Pn}是安全的：如果对于每一个进程Pi(1≤i≤n），它尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
安全状态时一定没有死锁（当前状态非死锁，并不保证未来）
死锁一定是不安全状态，但不安全状态下不一定会死锁
总结
- 优点
- 比死锁预防限制少
- 无死锁检测方法中的资源剥夺，进程重启
- 缺点
- 必须事先声明每个进程请求的最大资源
- 进程必须是无关的：没有任何同步要求的限制
- 进程数量保持不变，分配的资源数目必须是固定的
- 在占有资源时，进程不能退出
- 保守的分配方案（设置条件严格）
银行家算法
当用户申请资源时，系统判断如果把这些资源分出去，系统是否还处于安全状态。
若是，就可以分配这些资源； 否则，暂时不分配，阻塞进程。
安全性算法
- 设Work和Finish分别是长度为m和n的向量，按如下方式进行初始化:
- Work = Available
- Finish[i] = false for i = 1,2, …, n.
- 查找这样的i使其满足:
- Finish[i] = false
- Need[i] <= Work
- 如果未找到，转第4步.
- Work = Work + Allocation[i]; Finish[i] = True；返回第2步
- 如果对所有的i, Finish[i]==True，那么处于安全状态，否则不安全状态。
资源分配算法
- Requesti为进程Pi的请求向量。如果Requesti [j] = k 那么进程Pi 所需要的资源类型Rj的实例数量为k。当进程Pi做出资源请求时，执行：
- 若Requesti <=Needi 转1.2；否则，出错退出；
- 若Requesti <=Available 转2； 否则 Pi阻塞；
- 假定系统可以分配给进程Pi所请求的资源，并按如下方式修改状态:
- Available = Available - Requesti;
- Allocationi = Allocationi + Requesti;
- Needi = Needi – Requesti;
- 系统执行安全性算法
- 如果处于安全状态，那么Pi可分配到其所需资源;
- 如果新状态不安全，那么进程Pi必须等待，并恢复到原先资源分配状态
实例
如果一个系统既不采用死锁预防算法也不采用死锁避免算法，那么可能会出现死锁。因此，系统应该提供：用来检查系统状态是否出现死锁的检测算法、从死锁状态中恢复的方法。
- 死锁检测
- 没有任何预先限制措施
- 资源分配时不检查系统是否会进入不安全状态，被请求的资源都被授予给进程
- 系统可能出现死锁
- 周期性检测是否出现死锁（执行检测算法）
- 检测时机
- 在每个资源请求时都进行
- 定时检测
- 系统资源利用率下降时检测死锁
- 简化资源分配图
- 简化规则：若已分配和申请能满足需求，则删除边，使其成为孤立点→运行完毕后资源释放；
- 在经过一系列的简化后，若能消去图中的所有边，使所有的进程都成为孤立结点，则称该图是可完全简化的；反之的是不可完全简化的。
- 死锁定理：死锁状态的充要条件：资源分配图不可完全简化
- 死锁定理与不安全状态的关系
- 死锁定理：当前请求（request）
- 不安全状态：所有剩余请求（need）
- 撤销进程
- 终止所有的死锁进程
- 一次终止一个进程直到取消死锁循环→基于某种最小代价原则
- 选择原则
- 已消耗CPU时间最少
- 到目前为止产生的输出量最少
- 预计剩余的时间最长
- 目前为止分配的资源总量最少
- 优先级最低
- 资源剥夺：逐步从进程中抢占资源给其它进程，直到死锁环被打破为止 。
- 选择一个牺牲品：抢占哪些资源和哪个进程，确定抢占顺序以使代价最小。
- 饥饿：确保资源不会总是从同一个进程中被抢占
- 进程回退：把每个死锁进程备份到前面定义的某些检查点，并且重新启动所有进程－需要系统构造重新运行和重新启动机制
通常实际中采用的方式...摆烂的成本最低。
终于写完这一部分了，是真的多，整整20课时的内容啊！
