本文为《现代操作系统》的读书笔记

目录

• 进程 (process)
• • 多道程序设计模型
  • 程序顺序执行与并发执行
  • • 前驱图和程序执行
    • 并发执行
  • 进程模型
  • 进程控制
  • • 创建进程
    • • 进程是何时被创建的？
      • 进程创建过程
    • 终止进程
    • • 进程何时终止？
      • 进程终止过程
    • 进程的状态
    • • 运行态, 就绪态, 阻塞态
      • 新建状态, 完成状态
      • 挂起状态
  • 进程的层次结构
  • 进程的实现
  • • 进程表 (process table)
    • 进程控制块 PCB
  • 进程控制 Win32 API
• 中断
• • 中断类型
  • 中断处理
  • 中断与进程状态转换
• 进程调度
• • 高级、中级和低级调度
  • 进程调度方式
  • • 非抢占方式
    • 抢占方式
  • 调度算法
  • • 评价调度算法的指标
    • 先来先服务 (FCFS / FIFO)
    • 短作业优先 (SJF）
    • 最高响应比 (HRP)
    • 最短剩余时间 (SRT)
    • 轮转 (RR）
    • 优先级法 (HPF)
    • 多级队列（MQ)
  • 调度时机
  • 实时调度
• 进程同步
• • 进程同步概念
  • 解决进程同步的思路与方法
  • • 忙等待
    • 睡眠与唤醒
    • 信号量
    • 管程
    • 进程通信
  • 经典的进程同步问题
  • • 生产者—消费者问题
    • 读者—写者问题
    • 哲学家进餐
  • 管程 (monitor)
  • • 管程的概念
    • 生产者—消费者问题
    • 哲学家进餐问题
  • 进程通信
  • • 管道
    • 共享内存
    • 剪贴板方法
    • 套接字方法
• 线程
• • 线程的使用
  • 线程的实现
  • 线程的状态
  • 线程同步
  • • 临界区 (Critical Section)
    • 互斥量 (Mutex)
    • 事件
    • 信号量
    • 总结

为简单起见，下面我们假设只有一个 CPU

进程 (process)

多道程序设计模型

• 采用多道程序设计可以提高 CPU 的利用率。假设一个进程等待 I/O 操作的时间与其停留在内存中时间的比为 p p p。当内存中同时有 n n n 个进程时， 则所有 n n n 个进程都在等待 I/O (此时 CPU 空转）的概率是 p n p^n pn, 因此
  C P U 利 用 率 = 1 − p n CPU利用率= 1-p^n CPU利用率=1−pn n n n 称为多道程序设计的道数
  

• 虽然图 2-6 的模型很简单、很粗略， 它依然对预测 CPU 的性能很有效
  • 例如， 假设计算机有 8GB 内存， 操作系统及相关表格占用 2GB, 每个用户程序也占用 2GB。这些内存空间允许 3 个用户程序同时驻留在内存中。若 80% 的时间用于 I/O 等待， 则 CPU 的利用率（忽略操作系统开销）大约是 49%。在增加 8GB 字节的内存后， 可从 3 道程序设计提高到 7 道程序设计， 因而 CPU 利用率提高到 79%。换言之， 第二个 8GB 内存提高了 30% 的吞吐量。增加第三个 8GB 内存只能将 CPU 利用率从 79% 提高到 91%, 吞吐最的提高仅为 12%。通过这一模型，计算机用户可以确定， 第一次增加内存是一个划算的投资， 而第二个则不是

• 多道下内存和处理机利用率得到显著提高，但内存中存放程序数量并不是越多越好。程序道数过多对处理机的竞争更加激烈，可能会
  • 影响系统的响应速度
  • 产生过多的系统开销

• 多道程序设计是操作系统最基本的思想，然而程序的概念却无法刻画系统中的并发特性。于是就提出了进程来描述计算机程序的执行过程和作为资源分配的基本单位
  • 程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念. 程序可以作为一种软件资料长期存在, 是永久的
  • 进程是程序在处理机上的一次执行过程，它是一个动态的概念. 进程是有一定生命期的，是暂时的

程序顺序执行与并发执行

这一部分是课上讲的，书上没有；需要掌握的是画前驱图以及判断程序是否可以并发执行

前驱图和程序执行

• 前驱图是一个有向无环图，记为 DAG (Directed Acyclic Graph), 可用于描述进程之间执行的前后关系 (无循环关系可实现顺序执行)
  
  • 结点：一个程序段、进程或一条语句
  • 有向边：两个结点之间的前趋关系
  • 重量：结点所含有的程序量或执行时间
  • 直接前驱、直接后继、开始结点、终止结点
• 以上前趋图，存在的前趋关系：
  P = { ( P 1 , P 2 ) , ( P 1 , P 3 ) , ( P 1 , P 4 ) , ( P 2 , P 5 ) , ( P 3 , P 5 ) , ( P 4 , P 6 ) , ( P 4 , P 7 ) , ( P 5 , P 8 ) , ( P 6 , P 8 ) , ( P 7 , P 9 ) , ( P 8 , P 9 ) } P=\{(P_1,P_2),(P_1,P_3),(P_1,P_4),(P_2,P_5),(P_3,P_5),(P_4,P_6),(P_4,P_7),(P_5,P_8),(P_6,P_8),(P_7,P_9),(P_8,P_9)\} P={(P1​,P2​),(P1​,P3​),(P1​,P4​),(P2​,P5​),(P3​,P5​),(P4​,P6​),(P4​,P7​),(P5​,P8​),(P6​,P8​),(P7​,P9​),(P8​,P9​)}

• 程序的顺序执行: 程序是指令（或语句）的集合，指令之间是顺序关系，是一个静态的概念. 我们把具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行
  • 假定用 I I I、 C C C 和 P P P 分别表示输入、计算和输出操作（也可以为语句），可以有图 5.3 的前驱图
    
  • 三个语句表示的前驱图 (S1: a = 10; S2: b = a + 8; S3: print(b))
    
• 程序顺序执行具有如下 3 个特点
  • 顺序性；顺序执行行过程可看作一系列严格按程序规定的状态转移过程
  • 封闭性；程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响
  • 可再现性；只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。

并发执行

多道程序系统中程序执行环境的变化

• 独立性；每道程序都是逻辑上独立的。
• 随机性；多道程序环境下，特别是多用户环境下，程序和数据输入与执行开始时间都是随机的。
• 资源共享；资源共享将导致对程序执行速度的制约

进程间并行

• 对于任意程序，存在着 I i → C i → P i I_i→C_i→P_i Ii​→Ci​→Pi​ 这样的前驱关系，因而对一个用户程序的输入、计算和打印这三个操作，必须顺序执行. 在多道环境下，存在 I i → I i + 1 ； C i → C i + 1 ; P i → P i + 1 I_i→I_{i+1}；C_i→C_{i+1}; P_{i}→P_{i+1} Ii​→Ii+1​；Ci​→Ci+1​;Pi​→Pi+1​; 表明系统资源竞争带来顺序性前驱关系, 但 I i 、 C j I_i、C_j Ii​、Cj​ 和 P k P_k Pk​（ i ≠ j ≠ k i≠j≠k i​=j​=k）之间并不存在前驱关系，因而在对一批程序处理时，可使它们并发执行。这就产生了并发操作 （并发执行是一个程序的开始是在另一个程序结束之前）
  

指令间并行

• 程序内部各程序段间是否具备并发执行是由它们之间依赖关系所决定
  

程序的并发执行

• 间断性；程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系 (程序的顺序性演变成间断性)
• 失去封闭性；程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。当处理机资源被其它程序占用时，有条件运行的任何程序都必须等待
• 不可再现性；程序在并发执行时，由于失去了封闭性，也导致失去了可再现性

程序并发执行的条件

• 程序的并发执行使得执行结果不再具有封闭性和可再现性，且可能造成出现错误（执行结果受执行速度影响的结果)。为了使在并发执行时不出现错误结果，必须采取某些措施来制约、控制各并发程序段执行速度
• 为保持可再现性，就需要考察程序并发执行条件
  • 相邻语句 S 1 S_1 S1​， S 2 S_2 S2​ 可以并发执行的条件：语句 S i S_i Si​ 划分为两个变量集合 R ( S i ) R(S_i) R(Si​) 和 W ( S i ) W(S_i) W(Si​)；分别为 S i S_i Si​ 在执行期间对其进行参考的变量集合 (读集) 和 对其进行访问的变量集合 (写集)
  • 如果对于语句 S 1 S_1 S1​ 和 S 2 S_2 S2​，有
    • (1) R ( S 1 ) ∩ W ( S 2 ) = ϕ R(S_1)∩ W(S_2)=\phi R(S1​)∩W(S2​)=ϕ，即 S 1 S_1 S1​ 读变量不是 S 2 S_2 S2​ 修改的变量
    • (2) W ( S 1 ) ∩ R ( S 2 ) = ϕ W(S_1)∩ R(S_2)=\phi W(S1​)∩R(S2​)=ϕ，即 S 2 S_2 S2​ 读变量不是 S 1 S_1 S1​ 修改的变量
    • (3) W ( S 1 ) ∩ W ( S 2 ) = ϕ W(S_1)∩ W(S_2)=\phi W(S1​)∩W(S2​)=ϕ，即双方都不修改相同的变量
    • 例如语句 c＝a－b 和 w ＝c＋1，其 “读集”和“写集”分别为：
      R ( c ＝ a － b ) ＝ { a ， b } ;       W ( c ＝ a － b ) ＝ { c } R ( w ＝ c ＋ 1 ) ＝ { c } ;       W ( w ＝ c ＋ 1 ) ＝ { w } R ( w ＝ c ＋ 1 ) ∩ W ( c ＝ a － b ) ＝ { c } R(c＝a－b)＝\{ a，b \}; \ \ \ \ \ W(c＝a－b)＝\{ c \}\\ R(w＝c＋1)＝\{ c \};\ \ \ \ \ W(w＝c＋1)＝\{ w \}\\ R(w＝c＋1)∩W(c＝a－b)＝\{ c \} R(c＝a－b)＝{a，b};     W(c＝a－b)＝{c}R(w＝c＋1)＝{c};     W(w＝c＋1)＝{w}R(w＝c＋1)∩W(c＝a－b)＝{c}所以两条语句不能并发执行
• 如果并发执行的各程序段中语句或指令满足上述三个条件，则认为并发执行不会对执行结果的封闭性和可再现性产生影响。但在一般情况下，这个条件对于软件设计（模块化）过于苛刻，系统要判定并发执行的各程序段是否满足 Bernstein 条件是相当困难的。从而，如果并发执行的程序段不按照特定的规则和方法进行资源共享和竞争，则其执行结果将不可避免地失去封闭性和可再现性
• 从上述讨论可以看出，由于程序的顺序性、静态性以及孤立性，用程序段作为描述其执行过程和共享资源的基本单位既增加操作系统设计和实现的复杂性，也无法反映操作系统所应该具有的程序段执行的并发性、用户随机性，以及资源共享等特征。需要有一个能描述程序的执行过程且能用来共享资源的基本单位。这个基本单位被称为进程

进程模型

• 在进程模型中，计算机上所有可运行的软件， 通常也包括操作系统， 被组织成若干顺序进程 (sequential process) , 简称进程(process)
  
  • 一个进程就是一个正在执行程序的实例，包括程序、数据和进程控制块 (PCB)。从概念上说，每个进程拥有它自己的虚拟 CPU。当然，实际上真正的 CPU 在各进程之间来回切换 (伪并行)。这种快速的切换称作多道程序设计
    • 值得注意的是，如果一个程序运行了两遍， 则算作两个进程. 操作系统能够使它们共享代码， 因此只有一个副本放在内存中
  • 单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务
    • 例如，在图 2-1a 中可以看到，在一台多道程序计算机的内存中有 4 道程序
    • 在图 2-1b 中，这 4 道程序被抽象为 4 个各自拥有自己控制流程（即每个程序自己的逻辑程序计数器）的进程，并且每个程序都独立地运行。当然，实际上只有一个物理程序计数器，所以在每个程序运行时，它的逻辑程序计数器被装入实际的程序计数器中。当该程序执行结束（或暂停执行）时，物理程序计数器被保存在内存中该进程的逻辑程序计数器中
    • 在图 2-1c 中可以看到，在观察足够长的一段时间后，所有的进程都运行了， 但在任何一个给定的瞬间仅有一个进程真正在运行
      

进程特征

• 独立性：独立运行的基本单位，独立获得资源和调度的基本单位
• 异步性：各进程按各自独立的不可预知的速度向前推进
  • 由于CPU在各进程之间来回快速切换，所以每个进程执行其运算的速度是不确定的。而且当同一进程再次运行时，其运算速度通常也不可再现。所以，在对进程编程时决不能对时序做任何想当然的假设。当一个进程具有严格的实时要求时，那么必须采取特殊措施以保证它们一定在这段时间中发生
    • 例如，考虑一个 l/O 进程， 它用流式磁带机恢复备份的文件， 它执行一个 10000 次的空循环以等待磁带机达到正常速度， 然后发出命令读取第一个记录。如果 CPU 决定在空循环期间切换到其他进程， 则磁带机进程可能在第一条记录通过磁头之后还未被再次运行

进程控制

• 进程控制指对系统中的所有进程实施管理，一般由 OS 的内核来实现
  • 创建进程、终止进程、进程运行中状态的转换

创建进程

进程是何时被创建的？

• 新进程都是由于一个已存在的进程执行了一个用于创建进程的系统调用而创建的：这个进程可以是一个运行的用户进程、一个由键盘或鼠标启动的系统进程或者一个批处理管理进程。这个进程所做的工作是， 执行一个用来创建新进程的系统调用。这个系统调用通知操作系统创建一个新进程， 并且直接或间接地指定在该进程中运行的程序
  • (1) 启动操作系统时， 通常会创建若干个进程
    • 其中有些是前台进程， 也就是同用户交互井且替他们完成工作的那些进程
    • 其他的是后台进程， 这些进程与特定的用户没有关系， 相反， 却具有某些专门的功能。停留在后台处理诸如电子邮件、Web页面、新闻、打印之类活动的进程称为守护进程 (daemon)
  • (2) 一个正在运行的进程经常发出系统调用，以便创建一个或多个新进程协助其工作
  • (3) 在交互式系统中， 键入一个命令就可以开始一个新的进程
  • (4) 最后一种创建进程的情形仅在大型机的批处理系统中应用。用户在这种系统中（可能是远程地）提交批处理作业。在操作系统认为有资源可运行另一个作业时， 它创建一个新的进程， 并运行其输入队列中的下一个作业

进程创建过程

1. 申请空白 PCB
2. 为新进程分配资源；如内存
3. 初始化 PCB
4. 将新进程插入就绪队列

终止进程

进程何时终止？

• (1) 正常退出（自愿的）
  • 例如，当编译器完成了所给定程序的编译之后， 编译器执行一个系统调用， 通知操作系统它的工作已经完成。在 UNIX 中该调用是 exit
• (2) 出错退出（自愿的）。通常是由于程序中的错误所致
  • 例如， 执行了一条非法指令、引用不存在的内存， 或除数是零等。有些系统中（如 UNIX), 进程可以通知操作系统， 它希望自行处理某些类型的错误， 在这类错误中， 进程会收到信号（被中断）， 而不是在这类错误出现时终止
• (3) 严重错误（非自愿）
  • 例如，参数错误，试图访问不存在的文件
• (4) 被其他进程杀死（非自愿）
  • 某个进程执行一个系统调用通知操作系统杀死某个其他进程。在 UNIX 中， 这个系统调用是 kill

进程终止过程

1. 根据被终止进程的标识符，从 PCB 集合中检索出该进程的 PCB；
2. 若被终止进程处于执行状态，应立即终止执行，并置调度标志为真，调度其他进程；
3. 结束该进程所有子孙进程的执行，以防止成为不可控进程；
4. 将进程所拥有的资源交给父进程或系统进程；
5. 释放 PCB

进程的状态

• 尽管每个进程是一个独立的实体， 有其自己的程序计数器和内部状态， 但是， 进程之间经常需要相互作用，例如
  • 当一个进程在逻辑上不能继续运行时， 它就会被阻塞 (等待输入…)；又或者一个概念上能够运行的进程被迫停止， 因为操作系统调度另一个进程占用了 CPU
  • 例如如下命令中， 可能发生这种情况： grep 准备就绪可以运行， 但输入还没有完成。于是必须阻塞 grep, 直到输入到来. 在 UNIX, 当一个进程从管道或设备文件 读取数据时， 如果没有有效的输入存在， 则进程会被自动阻塞，无需使用系统调用

cat chapter1 chapter2 chapter3 | grep tree

运行态, 就绪态, 阻塞态

• 在下图中可以看到显示进程的三种状态的状态图， 这三种状态是：
  • (1) 运行态（该时刻进程实际占用 CPU)
    • 单处理机系统 只有一个进程处于该状态；多处理机系统有多个进程处于运行状态
  • (2) 就绪态（可运行， 但因为其他进程正在运行而暂时停止）
    • 就绪队列：处于就绪状态的进程按一定的策略排队，同一时刻可有多个就绪队列
  • (3) 阻塞态（除非某种外部事件发生，否则进程不能运行）
    • 阻塞队列：根据阻塞原因可以设置多个队列
    • 进程阻塞是进程自身的一种主动行为。但处于阻塞状态的进程是绝不可能叫醒它自己的，必须由它的合作进程用唤醒原语唤醒它
• 前两种状态在逻辑上是类似的。处于这两种状态的进程都可以运行， 只是对于第二种状态暂时没有 CPU 分配给它。第三种状态与前两种状态不同， 处于该状态的进程即使 CPU 空闲也不能运行
  

就绪→运行；从就绪队列选择一个进程占用处理机, 将就绪态改为运行态
阻塞→就绪；系统内发生事件时，根据事件原因查找阻塞队列中的进程，查到，将阻塞态转换为就绪态

新建状态, 完成状态

• 运行、就绪、阻塞是进程的三个基本状态，而操作系统的规模和设计目的不同，在有些系统中，还增加了两个基本状态，新建状态、完成状态，这两个状态对进程管理是非常有用的
  • 新建状态；对应于刚刚定义的进程，还未进入就绪队列的状态，此时系统未将进程全部工作完成（如内存尚待分配等）。如果一个新用户试图登陆到分时系统，新的批处理作业被选中准备投入内存；只有进程代码和数据进入内存，才进入就绪队列
  • 完成状态；指进程正常，或非正常结束而终止的状态。处于该状态的进程还未从系统中消失，可能由于一些善后工作尚未完成（如记帐，未完成的输出等）。但处于这种状态的进程以后不再被调度执行
    

挂起状态

• 三个基本状态提供了构造进程活动和模型的系统方法，并指导操作系统设计与实现。但这种系统不充分:
  • 一方面，处理机、内存等系统硬件资源的利用率得不到充分发挥
  • 另一方面，处在活动空间进程可能由于某原因暂时静止下来，不处于活动，但也不从系统中彻底退出，这就导致三种状态模型扩充，引入挂起状态

• 活动阻塞→静止阻塞；若当前系统中没有就绪态进程，就将处于阻塞态进程至少挂起一个，而进入静止阻塞状态，为没有被阻塞的进程让出主存空间
• 静止阻塞 → 活动阻塞；这种情况较少发生。如果一个进程处于阻塞，又不在主存, 调入它进入主存似乎意义不大。但运行进程执行完，发现静止阻塞队列存在优先级较高者时可能发生
• 静止阻塞→静止就绪；同基本状态转换一样，如果等待的事件发生了，则将处于静止阻塞的进程修改为静止就绪状态
• 活动就绪→静止就绪；通常，操作系统倾向挂起阻塞态进程。但有两种情况需要这种转换；一是得到主存更大空间唯一方法是挂起一个就绪进程；二是如果能够确定处于高优先级阻塞状态进程可以很快进入就绪状态
  • e.g. 内存清理软件其实就是申请一块很大的内存，然后 CPU 就会挂起很多进程，这样当内存清理进程完成后，内存空间就都空出来了
• 静止就绪 → 活动就绪；若主存中没有就绪进程，一般操作系统需要调入一个进程。而当处于静止就绪状态的进程的优先级高于就绪进程的优先级时，操作系统则往往将处于静止就绪进程通过激活而将其转换为就绪状态
• 新建→静止就绪；创建一个新进程可以进入静止就绪队列。系统初始执行期间，操作系统倾向建立更多就绪进程维护大量未被阻塞进程。这样使以后新进程由于主存空间不足而无法进入，这时就使用新建 → 静止就绪
• 各种状态→完成；在正常情况下，一个运行进程正常，或非正常结束，都进入完成状态。但如果父进程终止，则一个进程可以在任何状态下终止而进入完成状态

进程的层次结构

• 某些系统中， 当进程创建了另一个进程后， 父进程和子进程就以某种形式继续保持关联。子进程自身可以创建更多的进程， 组成一个进程的层次结构
  • 在 UNIX 中， 进程和它的所有子进程以及后裔共同组成一个进程组。当用户从键盘发出一个信号时，该信号被送给当前与键盘相关的进程组中的所有成员（它们通常是在当前窗口创建的所有活动进程）。每个进程可以分别捕获该信号、忽略该信号或采取默认的动作， 即被该信号杀死
    • 例如， 考虑 UNIX 在启动时如何初始化自己。一个称为 init 的特殊进程出现在启动映像中。当它开始运行时， 读入一个说明终端数量的文件。接着， 为每个终端创建一个新进程。这些进程等待用户登录。如果有一个用户登录成功， 该登录进程就执行一个 shell 准备接收命令。所接收的这些命令会启动更多的进程， 以此类推。这样， 在整个系统中， 所有的进程都属于以 init 为根的一棵树
  • 相反， Windows 中没有进程层次的概念， 所有的进程都是地位相同的。唯一类似于进程层次的暗示是在创建进程的时候， 父进程得到一个特别的令牌（称为句柄）， 该句柄可以用来控制子进程。但是，它有权把这个令牌传送给某个其他进程， 这样就不存在进程层次了
    

进程的实现

进程表 (process table)

• 为了实现进程模型，操作系统维护着一张表格（一个结构数组）， 即进程表 (process table)

进程控制块 PCB

• 每个进程占用一个 进程表项 / 进程控制块 (PCB) (进程与 PCB 一一对应); PCB 随进程创建而建立，随进程结束而回收。PCB 应常驻内存
• PCB 是为了描述一个进程和其它进程以及系统资源的关系，并刻画一个进程在各个不同时期所处的状态；OS 利用 PCB 来对并发执行的进程进行控制和管理， PCB 是 OS 感知进程存在的唯一标志
  • 该表项包含了进程状态的重要信息， 包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息， 以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的信息， 从而保证该进程随后能再次启动，就像从未被中断过一样
    

PCB 的内容

• 进程描述信息：
  • 进程标识符 PID (process ID)：唯一，通常是一个整数
  • 进程名：通常基于可执行文件名（不唯一）
  • 用户标识符 (user ID)：进程组关系
• 进程控制信息：
  • 当前状态: 运行统计信息（执行时间、页面调度), 进程间同步和通信, 阻塞原因, 进程的队列指针, 进程的消息队列指针
  • 优先级 (priority)
  • 代码执行入口地址
  • 程序的外存地址
• 所拥有的资源和使用情况：
  • 虚拟地址空间的现状
  • 打开文件列表
• CPU 现场保护信息：
  • 寄存器值（通用、程序计数器 PC、状态字 PSW，栈指针）
  • 指向赋予该进程的段/页表的指针

进程控制 Win32 API

原语 (Primitive)

• 原语：由多条指令组成，是一种特殊的系统功能调用，它可以完成一个特定的功能
• 原语的特点：执行时不可中断、不可并发、在管态下执行，常驻内存

常用的进程控制原语

• 创建原语 Create、终止原语 Destroy、阻塞原语 Block、唤醒原语 Wakeup、挂起原语 Suspend、激活原语 Active

课上分了三种 API 进行介绍 (5.2 节)，这里先略去，等我需要用到的时候再补上

• 创建进程
• 枚举系统进程
• 终止进程

中断

• 中断是实现多道程序设计与并发执行的基础和必要条件。中断使操作系统能获得系统的控制权，并将处理机（也作为一种资源）分派给不同的进程而实现并发执行

中断类型

• 强迫性中断: 时钟中断、I/O 中断、控制台中断 (系统操作员通过控制台发出命令)、硬件故障中断、程序性中断 (地址越界、数据溢出…)
  • 时钟中断可用于 (1) 进程管理：用于时间片轮转处理机调度算法的系统中，记录进程已占用处理机时间等; (2) 作业管理：记录作业在输入井中等待的时间等；(3) 资源管理：动态统计运行进程占有和使用处理机等资源的时间等；(4) 事件处理：实时系统中定时向被控制的对象发送控制信号；(5) 系统维护：定时运行死锁检测程序等，定时运行系统记帐程序等；(6) 实现软件时钟：利用硬件间隔时钟和一个存储单元可以实现软件时钟。例如，假设硬件间隔时钟每隔 10ms 产生一次中断，某一程序每隔 1000ms 执行一次，则可以这样确定该程序的执行时刻
• 自愿性中断: 程序事先有意识安排的；通常执行访管指令（系统调用）而引起的，其目的要求系统提供某种服务

中断处理

• 与每一 I/O 类关联的是一个称作中断向量 (interrupt vector) 的位置。它包含中断服务程序的入口地址。假设当一个磁盘中断发生时， 用户进程 3 正在运行， 则中断硬件将程序计数器、程序状态字、有时还有一个或多个寄存器 压入堆栈， 计算机随即跳转到中断向量所指示的地址。这些是硬件完成的所有操作， 然后软件， 特别是中断服务例程就接管一切剩余的工作
• 所有的中断都从保存寄存器开始，对于当前进程而言，通常是保存在进程表项中。随后， 会从堆栈中删除由中断硬件机制存入堆栈的那部分信息， 并将堆栈指针指向一个由进程处理程序所使用的临时堆栈。一些诸如保存寄存器值和设置堆栈指针等操作，无法用C语言这一类高级语言描述，所以这些操作通过一个短小的汇编语言例程来完成， 通常该例程可以供所有的中断使用
• 当该例程结束后， 它调用一个C过程处理某个特定的中断类型剩下的工作。在完成有关工作之后， 大概就会使某些进程就绪， 接着调用调度程序， 决定随后该运行哪个进程。随后将控制转给一段汇编语言代码，为当前的进程装入寄存器值以及内存映射并启动该进程运行
  

中断与进程状态转换

• 申请 I/O 服务 (运行态 → \rightarrow → 阻塞态, 就绪态 → \rightarrow → 运行态)：运行中进程需要在某处执行有关 I/O 指令以进行数据输入输出。此时用户利用的指令要么是访管指令，要么是某种系统调用，无论那种形式，都属于自愿性中断而进入中断处理；也可能由于没有所要求空闲 I/O 设备而进入阻塞状态，进入由于等待某类 I/O 的阻塞队列，同时系统从就绪队列中选择一个就绪态进程投入运行而转换成运行态
• I/O 完成 (阻塞态 → \rightarrow → 就绪态)：I/O 外设数据传输完成产生一个 I/O 完成中断信号而进入 I/O 中断处理。当前进程状态信息被保存后，系统分析中断原因，检查是否有等待此次 I/O 完成的在阻塞队列中的进程，如果有，则通过某种算法从阻塞队列中摘出一个相关的进程而进入就绪队列
• 时间片到 / 抢占 (运行态 → \rightarrow → 就绪态)：由于系统定时间隔时钟中断所引起的当前进程的一个时间片用完而从运行状态转移到就绪状态

进程状态变迁是由于中断，但中断不一定产生进程切换

进程调度

高级、中级和低级调度

• 进程调度活动分成三个层次：
  • 高级调度 (作业调度)：在创建新进程时，决定是否把进程添加到当前活跃的进程集合中
  • 中级调度：属于交换功能的一部分，它需要决定（部分）进程是否不再处于活动空间中
  • 低级调度 (处理机调度, CPU scheduling)：真正决定下一次执行哪一个就绪进程
    

进程调度方式

非抢占方式

• 进程被选中就一直运行下去（不会因为时钟中断而被迫让出 CPU），直至完成工作、自愿放弃 CPU、或因某事件而被阻塞才把 CPU 让出给其它进程

抢占方式

• 抢占方式发生的情况可为：新进程到达、出现中断且将阻塞进程转变为就绪进程、以及用完规定的时间片等
  • 为进程提供更好的服务，防止一个进程长期占有 CPU ，但开销大

调度算法

评价调度算法的指标

• 调度算法: 从就绪队列中选择一个进程进入运行态；需要考虑 5 个指标 (面向用户和系统)：
  • (1) CPU 利用率
  • (2) 吞吐率
  • (3) 周转时间: 作业等待进入内存、进程在就绪队列中等待、进程在 CPU 上执行和完成有关 I/O 操作所花费的时间总和
    • 对于个作业 i i i，其周转时间为: T i = t c i − t s i T_{i}=t_{ci}-t_{si} Ti​=tci​−tsi​ ( t c i t_{ci} tci​ 为完成时间； t s i t_{si} tsi​ 为到达系统时间); 周转时间不具有区分实际运行时间长短的性质
    • n n n 个作业平均周转时间为： T ˉ = 1 n ∑ i = 1 n T i \bar T=\frac{1}{n}\sum_{i=1}^nT_i Tˉ=n1​∑i=1n​Ti​; 平均周转时间可以衡量不同调度算法对相同任务流的调度性能
    • 带权周转时间： W = T R W=\frac{T}{R} W=RT​（ T T T 为周转时间； R R R 为实际运行时间） ; 带权周转时间衡量长短任务的差别
    • 平均带权周转时间： W ˉ = 1 n ∑ i = 1 n T i R i \bar W=\frac{1}{n}\sum_{i=1}^n\frac{T_i}{R_i} Wˉ=n1​∑i=1n​Ri​Ti​​
  • (4) 响应时间: 从任务就绪到处理开始的时间
    • 在交互式系统中，周转时间不可能是最好的评价准则。因为不断请求与不断输出在同时发生
    • 通常，响应时间一般用于分时系统性能评价，指用户通过键盘或终端提出一个请求开始到系统给出相应的响应结果的时间
  • (5) 系统开销: 系统调度的时/空代价

先来先服务 (FCFS / FIFO)

First come first served

• 对于作业调度 (批处理系统)，该算法就是从后备作业队列中（按进入的时间顺序排队）选择队首一个或几个作业，调入内存，创建进程，放入就绪队列
• 对于进程调度，该算法就是从就绪队列中选择一个最先进入队列的进程，将 CPU 分配于它
  

优缺点

• 有利于长作业（进程）而不利于短作业（进程）
• 有利于 CPU 繁忙型作业（进程）而不利于 I/O 繁忙型作业（进程）

短作业优先 (SJF）

Shortest job first

• 短作业优先算法: 从就绪队列中选出下一个 “CPU 执行期最短” 的进程，将 CPU 分配于它
  

A → B → E → C → D A\rightarrow B\rightarrow E\rightarrow C\rightarrow D A→B→E→C→D

优缺点

• SJF 对短作业有利，但需要事先知道或至少需要估计每个作业所需的处理机时间
• 只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”
• 不利于分时系统（由于不可抢占性）

最高响应比 (HRP)

• FCFS 强调的在系统的等待时间; SJF 强调运行的时间；由此，考虑下面比值：
  R = 响 应 时 间 + 运 行 时 间 运 行 时 间 R =\frac{响应时间+ 运行时间}{运行时间} R=运行时间响应时间+运行时间​式子 R R R 既考虑了在系统的等待时间 (分子)，又考虑了作业自身所需的运行时间 (分母)，综合了 FCFS 与 SJP 各自特点。在进行进程调度时，从中选择响应比高者的进程投入运行
  • A → B → C → E → D A→B →C→E→D A→B→C→E→D; 例如 t = 9 t=9 t=9 时， B B B 运行完，需要比较 C , D , E C,D,E C,D,E 三个任务的响应比，其中 R C = ( 9 − 4 ) + 4 4 = 2.25 , R D = ( 9 − 6 ) + 5 5 = 1.6 , R E = ( 9 − 8 ) + 2 2 = 1.5 R_C=\frac{(9-4)+4}{4}=2.25,R_D=\frac{(9-6)+5}{5}=1.6,R_E=\frac{(9-8)+2}{2}=1.5 RC​=4(9−4)+4​=2.25,RD​=5(9−6)+5​=1.6,RE​=2(9−8)+2​=1.5，因此选择运行任务 C C C
    

最短剩余时间 (SRT)

Shortest remaining time

• SRT 是针对 SJF 增加了抢占机制的一种调度算法，它总是选择预期剩余时间最短的进程。只要新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程
  • SRT 不像 FCFS 偏向长进程，也不像轮转法产生额外的中断，从而减少了开销
  • 必须记录过去的服务时间，从而增加了开销
  • 从周转时间来看，SRT 比 SJF 有更好的性能

例

• A → B → C → E → B → D A→B→C→E→B→D A→B→C→E→B→D
  

轮转 (RR）

Round Robin

• 轮转法是一种基于时钟的抢占策略，以一个周期性间隔产生的时钟中断依次进行各个进程的调度。当时钟中断发生时，当前正在运行的进程被置于就绪队列中，然后再基于 FCFS 策略选择下一个就绪进程运行
• 轮转法设计的问题是时间片的长度。时间片设得太短会导致过多的进程切换，降低了 CPU 效率，而设得太长又可能引起对短的交互请求的响应时间变长；一般有：
  T = q × n { T  为系统响应时间  q   为时间片  n  为就绪队列中进程数目 T=q \times n\left\{\begin{array}{l} T \text { 为系统响应时间 } \\ q\ \text { 为时间片 }\\ n\ \text{为就绪队列中进程数目} \end{array}\right. T=q×n⎩⎨⎧​T 为系统响应时间 q  为时间片 n 为就绪队列中进程数目​也可以直接将时间片设为 20 m s 20ms 20ms~ 50 m s 50 ms 50ms

优先级法 (HPF)

优先级调度

• 轮转调度做了一个隐含的假设，即所有的进程同等重要，而拥有和操作多用户计算机系统的人对此常有不同的看法。这就导致了优先级调度。其基本思想很清楚：每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行
• 有两种确定进程优先级的方法：
  • 静态优先级: 进入系统时赋予一个优先级，在整个生命周期中一直固定不变 (可能不公平)
  • 动态优先级: 创建时赋予一个优先级，可以动态改变。如处于就绪状态时，进程的优先级应随着等待时间的增长而增高
    • 优点可使资源利用率得以提高，公平性比较好
    • 缺点是系统开销大，实现比较复杂

优先级法 (HPF)

• 将一组进程按优先级分成若干类，并且在各类之间采用优先级调度，而在各类进程的内部采用轮转调度。
  • 例如，下图给出了一个有 4 类优先级的系统，其调度算法如下：只要存在优先级为第 4 类的可运行进程，就按照轮转法为每个进程运行一个时间片，此时不理会较低优先级的进程。若第 4 类进程为空，则按照轮转法运行第 3 类进程。若第 4 类和第 3 类均为空，则按轮转法运行第 2 类进程
  • 如果不偶尔对优先级进行调整，则低优先级进程很可能会产生饥饿现象
    

多级队列（MQ)

Multilevel Queue

• 可根据进程某些特性，如优先级、类型等分成几个单独队列；每个队列可有各自调度算法。例如，前台进程利用 RR ，后台进程利用 FCFS 等

调度时机

• 何时有可能调用到处理机调度程序呢？前提条件是必须进入操作系统，即处于系统态 (处于用户态运行的用户程序不可能直接调用操作系统中的任何模块 (系统调用的例行服务程序除外)
• 一般在以下事件发生后要执行进程调度：
  • 创建进程
  • 进程终止时必须进行调度。如果没有就绪进程，系统通常会启动一个空转进程 (休闲进程) 等待 (硬/软) 中断的发生
  • 等待事件；进程由于等待 I/O、信号量或其它原因而放弃 CPU，这样就必须选择另外一个进程
  • 中断发生；当发生 I/O 中断，原先等待 I/O 的进程就从阻塞态转变成就绪态，是否可抢占
  • 运行到时；在分时系统中，当前进程用完给定的时间片，时钟中断使该进程让出 CPU 进入调度

实时调度

• 实时系统是一种时间起着主导作用的系统。在这些系统中，正确的但是迟到的应答往往比没有还要糟糕
  • e.g. 自动驾驶系统; 在 CD 播放器中的计算机获得从驱动器而来的位流，然后必须在非常短的时间间隔内将位流转换为音乐。如果计算时间过长，那么音乐就会听起来有异常
• 实时系统通常可以分为硬实时和软实时，前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍
  • 在这两种情形中，实时性能都是通过把程序划分为一组进程而实现的，其中每个进程的行为是可预测和提前掌握的。这些进程一般寿命较短，并且极快地就运行完成
  • 在检测到一个外部信号时，调度程序的任务就是按照满足所有截止时间的要求调度进程
• 实时系统的调度算法
  • 静态调度算法: 在系统开始运行之前作出调度决策
  • 动态调度算法: 在运行过程中进行调度决策
  • 只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才能工作。而动态调度算法不需要这些限制

进程同步

进程同步概念

进程间两种形式的制约关系

• 直接制约关系：进程间的相互联系是有意识的安排的
  • 一般来说，一个进程相对另一个进程的运行速度是不确定的。也就是说，进程之间是在异步环境下运行的，每个进程都以各自独立的、不可预知的速度向运行的终点推进。但是， 相互合作的几个进程需要在某些确定点上协调其工作。一个进程到达了这些点后，除非另一进程已完成了某些操作，否则就不得不停下来等待这些操作的结束
  • 进程同步: 多个相互合作的进程，在一些关键点上可能需要互相等待或互相交换信息，这种相互制约关系称为进程同步
• 间接制约关系：进程间要通过某种中介发生联系，是无意识安排的
  • 进程互斥: 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。其实互斥是进程同步的一种特殊情况，互斥也是为了达到让进程之间协调推进的目的

进程互斥

• 临界资源 (critical resource) / 互斥资源 / 共享变量: 系统中一次只允许一个进程使用的资源
• 临界区 / 互斥区 (critical section): 在进程中涉及到临界资源的程序段叫临界区; 多个进程的临界区称为相关临界区
  • 例如：
    
• 实现各进程互斥进入临界区: 进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区 (entry section)。在临界区后面加上一段称为退出区 (exit section) 的代码
  • 空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入
  • 忙则等待：不允许两个以上的进程同时进入互斥区
  • 有限等待：任何进入互斥区的要求应在有限的时间内得到满足
  • 让权等待：处于等待状态的进程应放弃占用 CPU，以使其他进程有机会得到CPU的使用权
    

while (1)
{
	进入区代码;
	临界区代码;
	退出区代码;
}

解决进程同步的思路与方法

忙等待

• 当一个进程在临界区中更新共享内存时，其他进程进行等待，不会进入其临界区
  • 硬件方法：中断禁用
  • 软件方法：锁变量的方法、严格轮换法、Peterson 方法

中断禁用

• 可以通过系统内核为启用中断和禁用中断定义的原语实现中断禁用

while (true)
{
	禁用中断; 
	临界区; 
	启用中断;
}

• 这个方案并不好，因为把屏蔽中断的权力交给用户进程是不明智的。设想一下，若一个进程屏蔽中断后不再打开中断，其结果将会如何？整个系统可能会因此终止。而且，如果系统是多处理器，则屏蔽中断仅仅对执行 disable 指令的那个 CPU 有效。其他 CPU 仍将继续运行，并可以访问共享内存

软件方法

• 问题描述：有两个进程 P 0 P_0 P0​ 和 P 1 P_1 P1​，互斥地共享某个资源。 P 0 P_0 P0​ 和 P 1 P_1 P1​ 是循环进程，它们执行一个无限循环程序，每次使用资源一个有限的时间间隔

锁变量的方法

• 设置一个公用整型变量 lock，用来指示临界区内是否有进程在运行。0 表示空闲，没有进程。1 表示忙，有进程。进程进入临界区前，检查 lock,若为 0，进入临界区，同时把 lock 置为 1。若 lock 为 1，进程等待直到 lock 值变为 0。两个进程的程序结构如下：

int lock = 0;

P0: {
	do{
		while(lock != 0) {}
		lock = 1;
		进入 P0 的临界区代码 CS0; 
		lock = 0;
		...
	}while(true);
}

P1: {
	do{
		while(lock != 0) {}
		lock = 1;
		进入 P1 的临界区代码 CS1; 
		lock = 0;
		...
	}while(true);
}

• 问题：假设 P 0 P_0 P0​ 进程读出锁变量的值发现它为 0， 而恰好在它将其值设置为 1 之前， P 1 P_1 P1​ 进程被调度运行，发现它为 0，将该锁变量设置为 1， P 1 P_1 P1​ 进入临界区。当 P 0 P_0 P0​ 进程进程再次能运行时，它继续将该锁设置为 1，并进入临界区。两个进程同时进入临界区，违背了临界区的访问规则 “忙则等待”

严格轮换法

• 设置一个公用整型变量 turn，用来指示允许进入临界区的进程标识。若 turn 为 0，则允许进程 P 0 P_0 P0​ 进入临界区；否则循环检查该变量，直到 turn 变为本进程标识；在退出区，修改允许进入进程的标识 turn 为 1。进程 P 1 P_1 P1​ 的算法与此类似。两个进程的程序结构如下：

int turn = 0;

P0: {
	do {
		while (turn != 0) {}
		进入 P0 的临界区代码 CS0; 
		turn = 1;
		...
	}while (true);
}

P1: {
	do {
		while (turn != 1) {}
		进入 P1 的临界区代码 CS1; 
		turn = 0;
		...
	}while (true);
}

• 问题：此方法可保证互斥访问临界资源，但存在问题是强制两个进程交替进入临界区，造成资源浪费; 例如，当进程 P 0 P_0 P0​ 退出临界区后将 turn 置为 1，以便允许进程 P 1 P_1 P1​ 进入临界区。但如果进程 P 1 P_1 P1​ 暂时并未要求访问该临界资源，而 P 0 P_0 P0​ 又想再次访问临界资源，则它将无法进入临界区; 可见，此算法不能保证实现“空闲让进”准则

改进交替问题

• 设置标志数组 flag[] 表示进程是否在临界区中执行，初值均为假。在每个进程访问该临界资源之前，先检查另一个进程是否在临界区中，若不在则修改本进程的临界区标志为真并进入临界区，在退出区修改本进程临界区标志为假。两进程的程序结构如下：

bool flag[2] = {false,false};

P0: {
	do{
		while (flag[1]) {}
		flag[0] = true;
		进程 P0 的临界区代码 CS0; 
		flag[0] = false;
		...
	}while (true);
}

P1: {
	do{
		while (flag[0]) {}
		flag[1] = true;
		进程 P1 的临界区代码 CS1; 
		flag[1] = false;
		...
	}while (true);
}

• 问题：此算法解决了“空闲让进” 的问题，但又出现了新问题。当两个进程都未进入临界区时，它们各自的访问标志都为 false，若此时刚好两个进程同时都想进入临界区，并且都发现对方的标志值为 false， 于是两个进程同时进入了各自的临界区。违背了“忙则等待”

继续改进

• 算法仍然设置标志数组 flag[], 但标志用来表示进程是否希望进入临界区，在每个进程访问临界资源之前，先将自己的标志设置为真，表示进程希望进入临界区，然后检查另一个进程的标志。若另一个进程的标志为真，则进程等待；否则进入临界区。两进程的程序结构如下：

bool flag[2] = {false,false};

P0: {
	do{
		flag[0] = true;
		while (flag[1]) {} // flag[1] 为真, 表示 P1 希望访问临界区，P0 等待
		进程 P0 的临界区代码 CS0;
		flag[0] = false;
		...
	}while (true);
}

P1: {
	do{
		flag[1] = true;
		while (flag[0]) {} 
		进程 P1 的临界区代码 CS1;
		flag[1] = false;
		...
	}while (true);
}

• 问题：此算法可以有效地防止两进程同时进入临界区，但存在两个进程都进不了临界区的问题。即当两个进程同时想进入临界区时，它们分别将自己的标志位设置为 true，并且同时去检查对方的状态，发现对方也要进入临界区，于是对方互相谦让，结果都无法进入临界区， 造成“死等”现象。违背了“有限等待”的准则

Peterson 方法

• 标志数组 flag[] 表示进程是否希望进入临界区或是否在临界区中执行。此外，还设置了一个 turn 变量，用于指示允许进入临界区的进程标识。两进程的程序结构如下：

bool flag[2] = {false,false}; 
int turn;

P0: {
	do{
		flag[0] = true;
		turn = 1; // 此时 P0 未进入临界区， 仍然允许 P1 进入临界区
		// flag[1] 为真表示 P1 希望访问临界区
		// turn 为 1 表示 P1 可以进入临界区，因此 P0 等待
		while(flag[1] && turn == 1) {}
		进程 P0 的临界区代码 CS0; 
		flag[0] = false;	// 表示 P0 退出访问临界区
		...
	}while(true)
}

P1: {
	do{
		flag[1] = true;
		turn = 0; // 此时 P1 未进入临界区， 仍然允许 P0 进入临界区
		// flag[0] 为真表示 P0 希望访问临界区
		// turn 为 0 表示 P0 可以进入临界区，因此 P1 等待
		while(flag[0] && turn == 0) {}
		进程 P1 的临界区代码 CS1; 
		flag[1] = false;	// 表示 P1 退出访问临界区
		...
	}while(true)
}

• 至此，软件方法可以正确地解决上述同步问题
  • 一开始，没有任何进程处于临界区中，现在 P 0 P_0 P0​ 进程执行。它通过设置其数组元素和将 turn 置为 1, 并进入临界区执行。如果 P 1 P_1 P1​ 现在执行， P 1 P_1 P1​ 将在此处挂起直到 flag[0] 变成 false，该事件只有在 P 0 P_0 P0​ 退出临界区时才会发生
  • 现在考虑两个进程几乎同时要进入临界区的情况。 P 0 P_0 P0​ 将 turn 置为 1， P 1 P_1 P1​ 将 turn 置为 0。但只有后被保存进去的值才有效，前一个因被重写而丢失。假设 P 1 P_1 P1​ 是后存入的，则 turn 为 0。当两个进程都运行到 while 语句时， P 0 P_0 P0​ 将进入临界区，而 P 1 P_1 P1​ 则将不停地循环且不能进入临界区，直到 P 0 P_0 P0​ 退出临界区为止
• 缺点：并不完美; 上述解法是正确的，但它们都有忙等待的缺点。这些解法在本质上是这样的：“当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止”; 这种方法不仅浪费了 CPU 时间，而且还可能引起预想不到的结果
  • 考虑一台计算机有两个进程， H H H 优先级较高， L L L 优先级较低。调度规则规定，只要 H H H 处于就绪态它就可以运行。在某一时刻， L L L 处于临界区中，此时 H H H 变到就绪态，准备运行。现在 H H H 开始忙等待，但由于当 H H H 就绪时 L L L 不会被调度，也就无法离开临界区，所以 H H H 将永远忙等待下去。这种情况有时被称作优先级反转问题

睡眠与唤醒

• 现在来考察几条进程间通信原语，它们在无法进入临界区时将阻塞，而不是忙等待。最简单的是 sleep 和 wakeup
  • sleep 是一个将引起调用进程阻塞的系统调用，即被挂起，直到另外一个进程将其唤醒
  • wakeup 调用有一个参数，即要被唤醒的进程

生产者-消费者问题 / 有界缓冲区问题

• 两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息 (也可以把这个问题一般化为 m m m 个生产者和 n n n 个消费者问题)
• 同步问题: 生产进程不能往“满”的缓冲区中放产品; 消费进程不能从“空”的缓冲区中取产品

• 当缓冲区已满，而此时生产者还想向其中放入一个新的数据项时。其解决办法是让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样地，当消费者试图从缓冲区中 取数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其唤醒
• 为了跟踪缓冲区中的数据项数，我们需要一个变量 count。如果缓冲区最多存放 N N N 个数据项，则生产者代码将首先检查 count 是否达到 N N N，若是，则生产者睡眠；否则生产者向缓冲区中放入一个数据项并增量 count 的值。消费者的代码与此类似：首先测试 count 是否为 0，若是，则睡眠；否则从中取走一个数据项并递减 count 的值。每个进程同时也检测另一个进程是否应被唤醒，若是则唤醒之。生产者和消费者的代码如下所示:

#defind N 100		// 缓冲区中的槽数目
int count = 0;		// 缓冲区中的数据项数目

void producer(void)
{
    int item;

    while (true) {
	    item = produce_item();
	    if (count == N) 
	    	sleep();
	    insert_item(item);
	    count = count + 1;
	    if (count == 1)   
	    	wakeup(consumer);
    }
}


void consumer(void)
{
    int item;

    while (true) {
       	if (count == 0) 
       		sleep();
       	item = remove_item();
       	count = count - 1;
       	if (count == N - 1) 
       		wakeup(producer);
       	consume_item(item);
    }
}

• 问题：这里有可能会出现竞争条件，其原因是对 count 的访问未加限制。可能出现以下情况：缓冲区为空，消费者刚刚读取 count 的值发现它为 0。此时调度程序决定暂停消费者并启动运行生产者。生产者向缓冲区中加入一个数据项，count 加 1。现在 count 的值变成了 1。它推断认为于 count 刚才为0，所以消费者此时一定在睡眠，于是生产者调用 wakeup 来唤醒消费者。但是，消费者此时在逻辑上并未睡眠，所以 wakeup 信号丢失。当消费者下次运行时，它将测试先前读到的 count 值，发现它为 0，于是睡眠。生产者迟早会填满整个缓冲区，然后睡眠。这样一来，两个进程都将永远睡眠下去。问题的实质在于发给一个（尚）未睡眠进程的 wakeup 信号丢失了
  • 一种快速的弥补方法是修改规则，加上一个唤醒等待位。当一个 wakeup 信号发送给一个清醒的进程信号时，将该位置 1。随后，当该进程要睡眠时，如果唤醒等待位为 1，则将该位清除，而该进程仍然保持清醒。但尽管在这个简单例子中用唤醒等待位的方法解决了问题，但是我们很容易就可以构造出一些例子，其中有三个或更多的进程，这时一个唤醒等待位就不够使用了。于是我们可以再打一个补丁，加入第 2 个唤醒等待位，甚至是 8 个、 32 个等，但原则上讲，这并没有从根本上解决问题

信号量

信号量 PV 机制

• 信号量：一个累计唤醒次数的整型变量，取值可以为 0（表示没有保存下来的唤醒操作）或者为正值（表示有一个或多个唤醒操作）
• P、V 操作是原语。信号量的值除初始化外，只能由 P、V 原语修改 (wait、signal)
  • 对一信号量执行 P (down) 操作，是检查其值是否大于 0。若该值大于 0，则将其值减 1（即用掉一个保存的唤醒信号）并继续；若该值为 0，则进程将睡眠，而且此时 down 操作并未结束
  • 检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。保证一旦一个信号量操作开始，则在该操作完成或阻塞之前，其他进程均不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是绝对必要的。所谓原子操作，是指一组相关联的操作要么都不间断地执行，要么都不执行
  • V (up) 操作对信号量的值增 1。如果一个或多个进程在该信号量上睡眠，无法完成一个先前的 down 操作，则由系统选择其中的一个进程（如随机挑选）并允许该进程完成它的 down 操作。于是，对一个有进程在其上睡眠的信号量执行一次 up 操作之后，该信号量的值仍旧是 0，但在其上睡眠的进程却少了一个。信号量的值增 1 和唤醒一个进程同样也是不可分割的。不会有某个进程因执行 V 而阻塞

整型信号量

• 定义为一个整型量，由两个标准原子操作 wait(S) (P 操作) 和 signal (S) (V 操作) 来访问

P(S): {
	while (S ≤ 0) 
		do no-op;
	S := S - 1;
}

V(S): {
	S := S + 1;
}

信号量的应用

• 同步: 利用信号量实现前驱关系
  • P 1 → P 2 P_1\rightarrow P_2 P1​→P2​ (先执行 P 1 P_1 P1​，再执行 P 2 P_2 P2​): 设置一个信号量 S S S，其初值为 0
    
  • 实现以下前驱关系：设 5 个信号量 semaphore f1 = f2 = f3 = f4 = f5 = 0; 分别表示进程 S 1 S_1 S1​、 S 2 S_2 S2​、 S 3 S_3 S3​、 S 4 S_4 S4​、 S 5 S_5 S5​ 是否执行完成
    
• 利用信号量实现进程互斥：mutex 初值为 1
  
• 司机售票员同步问题：售票员将车门关闭开始售票后，司机才可以开车。司机将车停下后，售票员才可以开门，让乘客下车

semaphore Door = 0, Stop = 0;

void Driver()
{
	while(true) {
	    P(Door);
	    启动车辆
		正常驾驶
		到站停车
	    V(Stop);
  	}
}
void Ticketseller()
{
    while(true) {
		关门
		V(Door);
		售票
		P(Stop);
		开门
    }
}

信号量分类

• 整型信号量: 定义为一个整型量，由两个标准原子操作 P(S) 和 V(S) 来访问

P(S): {
	while (S ≤ 0)
		do no-op;
	S := S - 1;
}

V(S): {
	S := S + 1;
}

• 记录型信号量: 在整型信号量机制中的 wait 操作，只要是信号量 S ≤ 0 S\leq0 S≤0, 就会不断测试。因此，该机制并未遵循“让权等待”准则，而是使进程处于“忙等”状态。记录型信号量机制则是一种不存在 “忙等” 的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一个临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量 value (初值为资源信号量的数目) 外，还增加一个进程链表指针 L，用于链接上述的所有等待进程
  
  • 当 value < 0 时，它的绝对值表示在该信号量链表中已阻塞进程的数目
  • 当 value > 0 时，它表示系统中可利用的资源数量
  • 当 value = 0 时，它表示资源恰好分配完毕

P(s)
{
	s.value = s.value - 1;
	// 当 s.value < 0 时，表示该类资源已分配完毕，因此进程应调用 block 原语，
	// 进行自我阻塞，放弃处理机，并插入到信号量链表 S.L 中
    if (s.value < 0)
    {
	    该进程状态置为等待状态
        将该进程的 PCB 插入相应的等待队列末尾 s.queue;
    }
}

V(s)
{
    s.value = s.value + 1;
    if (s.value <= 0)
    {
        唤醒相应等待队列 s.queue 中等待的一个进程
        改变其状态为就绪状态, 并将其插入就绪队列
    }
}

• AND 型信号量：在一些应用场合，是一个进程需要先获得两个或者更多的共享资源后方能执行其任务。假定现在有两个进程 A A A 和 B B B，他们都要求访问共享数据 D D D 和 E E E。当然，共享数据都应该作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量 Dmutex 和 Emutex，并令他们的初值都是 1。相应的，在两个进程中都要包含两个对 Dmutex 和 Emutex 的操作，即：
  
  • 显然，当进程同时要求的共享资源愈多时，发生进程死锁的可能性就越大
  • AND 同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部的分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配给进程，要么一个也不分配。这样就可以避免上述死锁情况发生。为此，在 P 操作中，增加一个 “AND” 条件

P(S1, S2, …, Sn): {
     if  S1 ≥ 1 and … and Sn ≥ 1 then
         for i := 1 to n do
            Si := Si - 1;
         endfor
     else
           该进程状态置为等待状态
     endif
}

V(S1, S2, …, Sn): {
     for i := 1 to n do
          Si := Si + 1;
          将与 Si 相关的所有等待进程移出到就绪队列
     endfor
}

• 信号量集: 一次需要 N N N 个某类临界资源时，就要进行 N N N 次 P 操作——低效又可能死锁。信号量集是指同时需要多种资源、每种占用的数目不同，且可分配的资源还存在一个临界值时的信号量处理。一般信号量集的基本思路是：在 AND 型信号量的基础上进行扩充，在一次原语操作中完成所有的资源申请
  • 进程对信号量 S i S_i Si​ 的测试值为 t i t_i ti​ (表示信号量的判断条件，要求 S i ≥ t i S_i \geq t_i Si​≥ti​；占用值为 d i d_i di​（表示资源的申请量，即 S i = S i − d i S_i=S_i-d_i Si​=Si​−di​)

P(S1, t1, d1, …, Sn, tn, dn): {
	if S1 ≥ t1 and … and Sn ≥ tn then
	    for i := 1 to n do
	        Si := Si - di;
	    endfor
	else
	      当发现有 Si < ti 时，该进程状态置为等待状态
	endif
}

V(S1, d1,…, Sn, dn): {
    for i := 1 to n do
         Si := Si + di;
         将与 Si 相关的所有等待进程移出到就绪队列                      
    endfor    
}

管程

• 见后面的小节

进程通信

• 见后面的小节

经典的进程同步问题

PV 操作实现进程互斥

• (1) 每个程序中用户实现互斥的 P、V 操作必须成对出现，先做 P 操作，进临界区，后做 V 操作，出临界区。若有多个分支，要认真检查其成对性
• (2) P、V 操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环
• (3) 互斥信号量的初值一般为 1
  

PV 操作实现进程同步

• 一般模型是：用一个信号量与一个消息联系起来，当信号量的值为 0 时，表示期望的消息尚未产生；当信号量的值非 0 时，表示期望的消息已经存在。用 PV 操作实现进程同步时，调用 P 操作测试消息是否到达，调用 V 操作发送消息
• 使用 PV 操作实现进程同步时应该注意：
  • (1) 分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量
  • (2) 信号量的初值与相应资源的数量有关，也与 P、V 操作在程序代码中出现的位置有关
  • (3) 同一信号量的 P、V 操作要成对出现，但它们分别在不同的进程代码中

生产者—消费者问题

#define N 100			// 缓冲区中的槽数目
typedef int semaphore;

semaphore mutex = 1;	// 控制对临界区的访问
semaphore empty = N;	// 计数缓冲区的空槽数目
semaphore full = 0;		// 计数缓冲区的满槽数目

void producer(void)
{
    int item;

    while (true) {
           item = produce_item();
           p(empty);	// 注意：这里 p(empty) 和 p(mutex) 绝对不能换位置！
           				// 如果换位置，则可能死锁 (生产者对 mutex 进行 P 操作后，
           				// 恰好 empty == 0，生产者等待；但之后消费者却无法再次进入
           				// 临界区 (mutex == 0)，使得消费者和生产者均等待)
           p(mutex);
           insert_item(item);
           v(mutex);
           v(full);
    }
}

void consumer(void)
{
    int item;

    while (true) {
           p(full);
           p(mutex);
           item = remove_item();
           v(mutex);
           v(empty);
           consume_item(item);
    }
}

• 各进程须先检查自己对应的资源数，确信有可用资源后再申请对整个缓冲区的互斥操作；否则，先申请对整个缓冲区的互斥操作 (p(mutex))，后申请自己对应的缓冲块资源(p(empty))，就可能死锁。出现死锁的条件是，申请到对整个缓冲区的互斥操作后，才发现自己对应的缓冲块没有可用资源，导致挂起，这时已不能放弃对缓冲区的占用，于是导致死锁
• 如果 P(S1) 和 P(S2) 两个操作在一起，那么 P 操作的顺序至关重要，一个同步 P 操作与一个互斥 P 操作在一起时，同步 P 操作在互斥 P 操作前

读者—写者问题

• 有两组并发进程: 读者和写者，共享一组数据区；要求：
  • 允许多个读者同时执行读操作
  • 不允许读者、写者同时操作
  • 不允许多个写者同时操作

为数据库访问建立了一个模型

• (1) 构筑读者进程和写者进程间的临界区: 设置信号量 wrt ，用来在读者和写者程序中构成如图所示的临界区
  这种安排在某读者进入临界区使用数据时，其他读者都不能使用该数据，这不符合题目要求
• (2) 判定是否是第 1 个读者; 希望在读者进程里，有一个办法能判定请求进入临界区
  的是否是第 1 个读者。如果是第 1 个读者，就对信号量 wrt 做 P 操作，以取得和写者的互斥；如果是后继读者，就不再对 wrt 做 P 操作。为此，设变量 first (它不是信号量) 初值为 0。用它来标识到来的进程是否是第一个进程。任何一个读者进程运行时，都先检查 first 是否为 0，若是 0，则做 P(wrt)，否则不做；与此同时，不能让每个读者退出临界区时都对信号量 wrt 做 V 操作，而是要判断它是否是最后一个读者。只有对最后一个读者，才会对信号量 wrt 做 V 操作，以便能够让写者有机会进入临界区
  
• (3) 但解法仍然有问题，first 是所有读者共享的公共变量，每个读者在使用它时，应该互斥才对。所以，必须再设置一个初值为 1 的互斥信号量 mutex，由它保证读者不会同时去测试和操作变量 first
  

// 用到两个互斥信号量：mutex 和 wrt
Reader()			/*读者进程程序*/
{
	P(mutex)		/*请求进入 first 访问临界区*/
	if (first == 0)	/*是第一个读者*/
	   P(wrt)		/*请求进入数据读写临界区*/
	first = first + 1
	V(mutex)		/*退出 first 访问临界区*/
	读取所需数据
	P(mutex)		/*请求进入 first 访问临界区*/
	first = first - 1
	if (first == 0)	/*是最后一个读者*/
	    V(wrt)		/*退出数据读写临界区*/
	V(mutxt)		/*退出 first 访问临界区*/
	使用读取到的数据
}

哲学家进餐

• 5 个哲学家围坐在圆桌旁，每人面前有一只空盘子，每 2 人之间放一只筷子，如图所示。为了就餐，每个哲学家必须拿到两只筷子，并且只能直接从自己的左边或右边去取筷子
• 哲学家就餐问题对于互斥访问有限资源的竞争问题（如 I/O 设备）一类的建模过程十分有用
  

void philosopher(int i)    /*i：哲学家编号，从 0 到 4*/ 
{ 
	while (true) 
	{ 
		think(); 		         /*哲学家正在思考*/ 
		take_fork(i);            /*取左侧的叉子*/ 
		take_fork((i+1) % N);    /*取右侧叉子*/ 
		eat();                   /*吃饭*/ 
		put_fork(i);             /*把左侧叉子放回桌子*/ 
		put_fork((i+1) % N);     /*把右侧叉子放回桌子*/ 
	} 
} 

• 如果 5 人同时拿起左边筷子，再企图拿起右边的筷子时，就会死锁！

算法改善 1

• “如果哲学家在拿不到右边叉子时等待一段随机时间，而不是等待相同的时间，这样发生互锁的可能性就很小了，事情就可以继续了。” 这种想法是对的，而且在几乎所有的应用程序中，稍后再试的办法并不会演化成为一个问题。例如，在流行的局域网以太网中，如果两台计算机同时发送包，那么每台计算机等待一段随机时间之后再尝试。在实践中，该方案工作良好
• 但是，在少数的应用中，人们希望有一种能够始终工作的方案，它不能因为一串不可靠的随机数字而导致失败（想象一下核电站中的安全控制系统）

算法改善 2

• 使用一个信号量 mutex 对调用 think 之后的五个语句进行互斥保护。在开始拿叉子之前，哲学家先对互斥量 mutex 执行 P 操作。在放回叉子后，他再对 mutex 执行 V 操作。但这种方法在任何一时刻只能有一位哲学家进餐。而五把叉子实际上可以允许两位哲学家同时进餐

semaphore mutex = 1;

void philosopher(int i)    /*i：哲学家编号，从 0 到 4*/ 
{ 
	while (true) 
	{ 
		think(); 		         /*哲学家正在思考*/ 
		p(mutex);
		take_fork(i);            /*取左侧的叉子*/ 
		take_fork((i+1) % N);    /*取右侧叉子*/ 
		eat();                   /*吃饭*/ 
		put_fork(i);             /*把左侧叉子放回桌子*/ 
		put_fork((i+1) % N);     /*把右侧叉子放回桌子*/ 
		v(mutex);
	} 
} 

算法改善 3

• 至多只允许四个哲学家同时进餐, 以保证至少有一个哲学家能够进餐。最终他总会释放出所使用过的两支叉子, 从而可使更多的哲学家进餐; 但这仍然有性能损失：始终有一位哲学家被关在门外，并行化程度不高

semaphore fork[5] = {1, 1, 1, 1, 1}; 
semaphore room = 4; 

void philosopher(int i)    /*i：哲学家编号，从 0 到 4*/ 
{ 
	while (true) 
	{ 
		think(); 		         /*哲学家正在思考*/ 
		p(room);  
		p(fork[i]);            	/*取左侧的叉子*/ 
		p(fork[(i+1) % N]);    	/*取右侧叉子*/ 
		eat();                 	/*吃饭*/ 
		v(fork[(i+1) % N]);   	/*把右侧叉子放回桌子*/ 
		v(fork[i]);             /*把左侧叉子放回桌子*/ 
		v(room);
	} 
} 

算法改善 4

• 像下图一样为叉子编号。每个哲学家都先拿他盘子周围编号最小的叉子，然后再拿编号最高的叉子。这样坐在图中最上方的哲学家会先拿起左手边的叉子，然后是右边的叉子，而其他的哲学家则先拿起右手边的叉子。因为有两个哲学家试着去拿叉子 1，而只有一位会成功，所以只有 4 位哲学家抢 5 把叉子。至少这 4 位中的一位肯定能拿到两把叉子，这样就能开始就餐了
  
• 这种为资源编号并按照编号顺序获取资源的通用技术在防止死锁上经常使用。但是很容易就能想象出一个事件序列来产生这种结果：虽然大家都在挨饿，但是一次只有一名哲学家就餐:
  • (1) P 1 P_1 P1​ 拿起叉子 1，阻止 P 2 P_2 P2​ 拿起叉子. (2) P 3 P_3 P3​ 拿起叉子 2. (3) P 4 P_4 P4​ 拿起叉子 3. (4) P 5 P_5 P5​ 拿起叉子 4. (5) P 5 P_5 P5​ 拿起叉子 5，开始就餐. (6) P 5 P_5 P5​ 放下叉子 4 和 5. (7) P 4 P_4 P4​ 拿起叉子 4，开始就餐
• 同时，资源分级的策略并不总是实用的，特别是当所需资源的列表并不是事先知道的时候 ；其次，对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高
  • 例如，假设一个工作单元拿着资源 3 和 5，并决定需要资源 2，则必须先要释放 5，之后释放 3，才能得到 2，之后必须重新按顺序获取 3 和 5

算法改善 5

• 不是对每只叉子设置信号量，而是对每个哲学家设置信号量。任意位哲学家都能获得最大的并行度。为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿
  

#define N			5					// 哲学家数量
#define LEFT		(i + N - 1) % N
#define RIGHT		(i + 1) % N
#define THINKING	0
#define HUNGRY		1
#define EATING		2

typedef int semaphore;
int state[N];			// 记录哲学家的不同状态 (思考，饥饿，进食)
semaphore mutex = 1;	// 保证各哲学家在测试左右相邻哲学家状态和设置新状态时，能够互斥进行
semaphore s[N];			// 信号量数组，初值都为 0，每个对应一个哲学家
						// 在拿不到筷子就餐时，用它来与占用筷子的有关哲学家取得同步

void philosopher(int i)	// i: 哲学家编号
{
   while (true){
     think(); 
     take_forks(i); 
     eat(); 
     put_forks(i); 
  }
}

void take_forks(int i) 
{ 
    P(mutex); 			// 进入临界区
    state[i] = HUNGRY; 	// 记录哲学家 i 处于饥饿的状态
    test(i); 			// 尝试获取 2 把叉子
    V(mutex); 			// 离开临界区
    P(s[i]); 			// 如果得不到需要的叉子则阻塞
} 

void put_forks(int i) 
{ 
	P(mutex); 			// 进入临界区
	state[i] = THINKING;// 哲学家已经就餐完毕
	test(LEFT(i)); 		// 检查左边的邻居现在可以吃吗 (唤醒)
	test(RIGHT(i));		// 检查右边的邻居现在可以吃吗
	V(mutex); 			// 离开临界区
} 

// 如果当前处理的哲学家处于饥饿状态且两侧哲学家不在吃饭状态，
// 则当前哲学家通过 test() 函数试图进入吃饭状态
void test(int i) 
{
	if (state[i] == HUNGRY && state[LEFT(i)] != EATING 
		&& state[RIGHT(i)] != EATING) 
	{
		state[i] = EATING; 
		V(s[i]);
	}
} 

管程 (monitor)

管程的概念

• 有了信号量和互斥量之后，进程间通信看来就很容易了，但使用信号量时要非常小心，稍有不慎就有可能死锁或其他一些不可预测和不可再现的行为 (例如之前生产者-消费者问题中，交换两个 P 操作的位置就有可能产生死锁)
• 信号量机制的缺点：
  • (1) 易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序
  • (2) 不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局
  • (3) 正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的
• 为了更易于编写正确的程序 ，提出了一种高级同步原语: 管程

• 一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程之外声明的过程中直接访问管程内的数据结构
  
• 任一时刻管程中只能有一个活跃进程，这一特性使管程能有效地完成互斥
  • 管程是编程语言的组成部分，编译器知道它们的特殊性，因此可以采用与其他过程调用不同的方法来处理对管程的调用。典型的处理方法是，当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程。如果有，调用进程将被挂起，直到另一个进程离开管程将其唤醒。如果没有活跃进程在使用管程，则该调用进程可以进入
• 管程提供了一种实现互斥的简便途径，但这还不够。我们还需要一种办法使得进程在无法继续运行时被阻塞。在生产者-消费者问题中很容易将针对缓冲区满和缓冲区空的测试放到管程过程中，但是生产者在发现缓冲区满的时候如何阻塞呢？
  • 解决的方法是引入条件变量以及相关的两个操作：wait 和 signal。当一个管程过程发现它无法继续运行时（例如，生产者发现缓冲区满），它会在某个条件变量上（如 full）执行 wait 操作。该操作导致调用进程自身阻塞，并且还将另一个以前等在管程之外的进程调入管程。另一个进程，比如消费者，可以唤醒正在睡眠的伙伴进程，即对其伙伴正在等待的一个条件变量执行 signal

条件变量

• 为了区别各种不同等待原因，在管程内设置若干条件变量 VAR C: condition;，局限于管程，并仅能从管程内进行访问； 对于条件型变量，可以执行 wait 和 signal 操作：
  • wait(c): 释放管程的互斥权，本进程进入 c 变量的等待队列链
  • signal(c)：如果 c 链为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，本进程的 PCB 进入等待队列的尾部

生产者—消费者问题

monitor ProducerConsumer
	condition full, empty;
	integer count;
	
	procedure insert(item:integer)
	begin
		if count = N then 
			wait(full);
		insert_item(item);
		count := count + 1;
		if count = 1 then 
			signal(empty);
	end;
	
	function remove:integer;
	begin
		if count = 0 then 
			wait(empty);
		remove = remove_item;
		count := count - 1;
		if count = N - 1 then 
			signal(full);
	end;
	count := 0;
end monitor;


procedure producer();
begin
	while true do
	begin
		item = procedure_item;
		ProducerConsumer.insert(item);
	end           
end;

procedure consumer();
begin
	while true do
	begin
		item = ProducerConsumer.remove;
		consume_item(item);
	end           
end;

• 大家可能会觉得 wait 和 signal 操作看起来像前面提到的 sleep 和 wakeup。它们确实很像，但是有个很关键的区别：sleep 和 wakeup 之所以失败是因为一个进程想睡然后被调度了，另一个进程这时发唤醒信号，于是信号丢失; 使用管程则不会发生这种情况。对管程过程的自动互斥保证了这一点

哲学家进餐问题

• 管程中设置了两个数组：
  • state[5]: 表示哲学家处于三种不同的状态：进餐、饥饿和思考
  • condition self[5]: 条件变量，当哲学家饥饿，而又不能获得进餐所需的筷子时，可以通过执行 self[i].wait 操作，来推迟自己的进餐。
• 管程中设置了三个函数：
  • pickup(i) (外部函数)。如哲学家处于饥饿状态，且左、右两位哲学家都未进餐，允许这位哲学家进餐；但只要其左、右两位哲学家中有一位正在进餐，将执行 self[i].wait 操作来推迟进餐
  • putdown(i) 函数(外部函数)。当哲学家进餐毕，通过该函数放下其手中的筷子
  • test(i) (内部函数)。测试哲学家是否已具备用餐条件，若为真，允许该哲学家进餐，否则，哲学家等待。该函数只能被本管程内的两个外部函数 pickup 和 putdown 调用，不能由进程直接调用

// 建立一个管程
Monitor Dining-Philosophers;
	共享变量定义;
	{
  		for(i = 0; i <= 4; i++)                /* 管程初始化 */
     		state[i] = thinking;
	}
	
	void Entry  pickup (int i)
	{  
		state[i] = hungry;
		test(i);
		if state[i] != eating  
			self[i].wait;
	}
	
	void Entry putdown (int i)
	{ 
		state[i] = thinking;
	  	test((i + 4) % 5);
	  	test((i + 1l) % 5);
	}
	
	void test (int k)
	{
	  	if (state[(k + 4) % 5] != eating) && (state[k] == hungry)
	  		&& (state[(k + 1) % 5 ] != eating)
	   	{
	     	state[k] = eating;
	     	self[k].signal;
	   	}
	}
end monitor;

// 哲学家进程
void philosopher (int i)
{ 
	while (true)
   	{  
   		thinking;
      	Dining-Philosophers.pickup(i);
      	eating;
      	Dining-Philosophers.putdown(i);
   }
}

进程通信

• 进程通信：并发进程之间相互交换信息，这种信息交换的量可大可小
  • 例如，进程间数据传输、共享数据：多个进程想要操作共享数据，一个进程对共享数据的修改，别的进程应该立刻看到、通知事件：一个进程需要向另一个或一组进程发送消息，通知它（它们）发生了某种事件（如进程终止时要通知父进程）、资源共享：多个进程之间共享同样的资源。为了作到这一点，需要内核提供锁和同步机制、进程控制：有些进程希望完全控制另一个进程的执行（如 Debug 进程），此时控制进程希望能够拦截另一个进程的所有陷入和异常，并能够及时知道它的状态改变

管道

• 可以使用管道在进程间、同一进程内进行数据交换
  • 匿名管道：没有名字，在使用它们时不需要知道其名字。主要目的是作为父进程与子进程、子进程之间通讯的联结通路 (允许进程与另一个与其有共同祖先的进程之间通信)
    • e.g. 重定向子进程的标准输入和标准输出。父进程可以是一个控制台或者是图形程序，而子进程必须是控制台应用程序
      • 控制台应用程序有三个用于输入输出的标准句柄，它们是标准输入、标准输出和标准错误句柄，控制台应用程序可以通过调用函数 GetStdHandle 来获得这三个句柄
      • 若要重定向输入输出，就得用指向管道一端的句柄来替换这个标准句柄。控制台应用程序不会知道我们使用了指向管道任一端的句柄，它会把这个句柄作为标准句柄来看待
  • 有名管道：在使用前必须知道其名字。可以用于任何两个进程之间通信

匿名管道

BOOL CreatePipe( PHANDLE hReadPipe, PHANDLE hWritePipe, 
				PSECURITY_ATTRIBUTES lpPipeAttributes, DWORD nSize );

• pReadPipe 双字指针变量，指向管道读端的句柄
• pWritePipe 双字指针变量，指向管道写端的句柄
• pPipeAttributes 双字指针变量，指向 SECURITY_ATTRIBUTES 结构，其用于决定读写句柄是否可以被子进程继承
• nSize 建议管道留给用户使用的缓冲区的大小，这仅仅是个建议值，可以用 NULL 来使用缺省值
• 如果函数调用成功返回值为非零，否则为零。成功调用之后，就会得到两个句柄，一个指向管道的读出端，另一个指向管道的写入端

有名管道

HANDLE CreateNamedPipe(LPCTSTR lpName, DWORD dwOpenMode, DWORD dwPipeMode, 
		DWORD nMaxInstances, DWORD nOutBufferSize, DWORD nInBufferSize, 
		DWORD nDefaultTimeOut, LPSECURITY_ATTRIBUTES lpSecurityAttributes);

• 如果函数调用成功返回值为管道句柄

共享内存

• 共享内存区域是被多个进程共享的一部分物理内存。如果多个进程都把该内存区域映射到自己的虚拟地址空间，则这些进程就都可以直接访问该共享内存区域，从而可以通过该区域进行通信
  • 共享内存是进程间共享数据的一种最快的方法，一个进程向共享内存区域写入了数据，共享这个内存区域的所有进程就可以立刻看到其中的内容

Windows 共享内存

HANDLE CreateFileMapping(
  HANDLE hFile,                       // *物理文件句柄
  LPSECURITY_ATTRIBUTES lpAttributes, // 安全设置
  DWORD flProtect,                    // 保护设置
  DWORD dwMaximumSizeHigh,            // 高位文件大小
  DWORD dwMaximumSizeLow,             // 低位文件大小
  LPCTSTR lpName                      // *共享内存名称
);

// 此函数映射文件视图到调用进程的地址空间
LPVOID MapViewOfFile(
	HANDLE hFileMappingObject,   // *物理文件句柄
	DWORD dwDesiredAccess,       // *访问模式
	DWORD dwFileOffsetHigh,      // 开始映射文件偏移量的高位
	DWORD dwFileOffsetLow,       // 开始映射文件偏移量的低位
	SIZE_T dwNumberOfBytesToMap  // 需要映射的文件的字节数量 
);

剪贴板方法

• 剪贴板是一种比较简单同时也是开销比较小的进程间通信机制。基本机制是由系统预留的一块全局共享内存，用来暂存各个进程间进行交换的数据
  • 提供数据的进程创建一个全局内存块，并将要传送的数据移到或复制到该内存块；而接受数据的进程（也可以是提供数据的进程本身）获取此内存块的句柄，并完成对该内存块数据的读取
    • 例如 Microsoft Word 中，组合键 Ctrl+C 用于文字的复制、组合键 Ctrl+X 用于对文字的剪切、组合键 Ctrl+V 用于对文字的粘贴。使用这些命令可以很方便地对所选择字符串进行复制和移动

Windows 剪贴板

OpenClipboard();	// 打开剪贴板
CloseClipboard();	// 关闭剪贴板 
SetClipboardData(UINT uFormat,  HANDLE hMem);		// 设置剪贴板数据 
GetClipboardData(UINT uFormat);		// 获取指定剪贴板数据 

套接字方法

线程

• 在传统操作系统中， 每个进程有一个地址空间和一个控制线程
• 不过， 经常存在在同一个地址空间中准并行运行多个控制线程的情形， 这些线程就像分离的进程（共享地址空间除外），是进程内一个相对独立、可调度的执行单元 (线程可以创建线程 (线程族系))
  • 进程是拥有资源的基本单位，多线程共享进程资源
  • 线程是操作系统的基本调度单元，一个进程至少有一个线程

单处理器系统的并行形式称为并发

线程的使用

为什么需要多线程？

• (1) 主要原因是， 在许多应用中同时发生着多种活动。其中某些活动随着时间的推移会被阻塞。通过将这些应用程序分解成可以准并行运行的多个顺序线程， 程序设计模型会变得更简单
  • 并行实体拥有共享同一个地址空间和所有可用数据的能力，增加了通信的有效性，方便和简化了用户程序结构工作
• (2) 由于线程比进程更轻量级， 所以它们比进程更容易（即更快）创建， 也更容易撤销，降低了系统开销。在许多系统中， 创建一个线程较创建一个进程要快 10~100 倍
• (3) 若多个线程都是 CPU 密集型的， 那么并不能获得性能上的增强， 但是如果存在着大量的计算和大批的 I/O 处理， 拥有多个线程允许这些活动彼此重叠进行，从而会加快应用程序执行的速度
  • 一个小例子: 考虑一个字处理软件。字处理软件通常按照出现在打印页上的格式在屏幕上精确显示文档， 这样在需要时用户可以检查和修改文档。现在如果有一个用户突然在一个有800页的文件的第一页上删掉了一个语句之后， 打算接着在第600页上进行另一个修改，并键入一条命令通知字处理软件转到该页面。于是字处理软件被强制对整本书的前600页重新进行格式处理， 这是因为在排列该页前面的所有页面之前， 字处理软件并不知道第600页的第一行应该在哪里。而在第600页的页面可以真正在屏幕上显示出来之前， 计算机可能要拖延相当一段时间， 从而令用户不甚满意。而许多字处理软件都有每隔若干分钟自动在磁盘上保存整个文件的特点，如果程序是单线程的， 那么在进行磁盘备份时， 来自键盘和鼠标的命令就会被忽略， 直到备份工作完成为止。用户当然会认为性能很差。多线程在这里可以发挥作用
    • 假设字处理软件被编写成含有两个线程的程序。一个线程与用户交互，而另一个在后台重新进行格式处理。一旦在第1页中的语句被删除掉， 交互线程就立即通知格式化线程对整本书重新进行处理。同时， 交互线程继续监控键盘和鼠标， 并响应诸如滚动第1页之类的简单命令。如果有点运气的话， 重新格式化会在用户请求查看第600页之前完成， 这样， 第600页页面就立即可以在屏幕上显示出来。第三个线程用于处理磁盘备份， 而不必干扰其他两个线程
    • 很显然，在这里用三个不同的进程是不能工作的，这是由于多个线程可以共享公共内存，这使得它们可以访问同一个正在编辑的文件

线程 vs. 进程

• 线程继承进程并发性而具有进程状态及转换
• 调度: 同一进程线程切换不会引起进程切换; 不同进程中线程切换才发生进程切换
• 并发性: 进程之间可以并发执行; 进程内多个线程同样可以并发执行
• 系统资源: 进程是资源分配单位（资源拥有者）; 线程共享进程所拥有的全部资源
• 系统开销: 进程创建和撤消开销大于线程; 进程切换开销大于同一进程内线程

线程的实现

• 线程分为内核级线程和用户级线程
  

用户级线程

• 用户级线程：早期的线程都是用户级的，为了对用户级线程进行控制和管理，操作系统提供一个在用户空间执行的线程库。线程库是一组供所有应用程序所共享的应用级软件包。该线程库提供创建、调度、撤销线程功能，并在用户态完成。进程中的线程对内核是透明的，操作系统内核只对进程进行管理
• 当一个线程被派生时，线程库为其生成相应的线程控制块 TCB 等数据结构，其处理过程与进程创建过程大致相似，不同的是：
  • 用户级线程的调度算法只进行线程上下文切换，不涉及处理机的状态。因为用户级线程的上下文切换与内核无关，所以当一个进程由于 I/O 中断等原因使该进程阻塞 / 某个进程时间片用尽切换为就绪态，属于该进程的执行中线程仍处于执行状态
• 用户级线程优点：
  • 进程内线程切换避免了：由用户模式→内核模式、再由内核模式→用户模式两种模式之间进行切换，减少系统开销
  • 线程之间切换算法可由应用确定 (简单轮转算法，或优先数算法)。线程切换不会干扰内核调度
  • 用户级线程可以在任何操作系统中运行，不需要对低层内核进行修改以支持用户级线程的实现

核心级线程

• 核心级线程由操作系统内核进行管理，线程的控制块 TCB 放在操作系统空间。线程的状态转换由操作系统完成。操作系统内核给应用程序提供相应的系统调用和应用程序接口，以使用户程序可以创建、执行、撤消线程
• 与用户线程不同，核心级线程既可以被调度到一个处理机上并发执行，也可以被调度到不同的处理机上并行执行。操作系统内核既负责进程的调度，也负责进程内不同线程的调度工作。因此，核心级线程不会出现进程处于阻塞或等待状态，而线程处于执行状态的情况
• 与用户级线程相比，核心级线程上下文切换时间要大于用户级线程上下文切换时间。核心级线程模型见下图 ( b ) (b) (b)
• 用户级线程相对于内核级线程有两个明显的缺点：
  • 在典型的操作系统中，许多系统调用都会引起用户执行流的阻塞。因此，当用户级线程执行一个系统调用时，不仅这个线程被阻塞，整个进程的所有线程都被阻塞了
  • 在纯粹的用户级线程策略中，由于内核是按进程作为调度单位的，因此一个多线程用户应用程序不能利用多处理技术。内核一次只将一个进程分配给一个处理机，也就只能有一个线程可以执行

混合线程 (了解)

• 有些操作系统将用户线程与核心线程这两种方式结合起来，组成了混合线程，发挥各自的优势。在组合方式中，核心只知道核心线程，也只对它们实施调度。某些核心线程对应多个用户级线程，因此，产生了多对 1，多对多的模型，如图（c）和（d）所示。
  

线程的状态

线程的三个基本状态

• 就绪状态：线程已具备运行条件，等待分配 CPU
• 运行状态：线程在 CPU 上运行
• 等待状态（阻塞状态）：线程正在等待事件发生

与进程状态的区别

• 线程不需要挂起，因线程不需要让出主存；
• 一个线程阻塞，进程及其他线程不因此而阻塞；
• 多线程进程的状态：笼统分为活动和非活动状态

线程同步

• 操作系统随机调度线程，程序员不能预知线程的执行顺序；下面两种情况下，线程间需要同步:
  • (1) 互斥: 当有多个线程访问共享资源而不希望共享资源遭到破坏
  • (2) 同步: 当一个线程需要将某个任务已经完成的情况通知另外一个或多个线程时
• Windows 线程同步方法主要有临界区、事件、互斥量、信号量

临界区 (Critical Section)

• 临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问
  • 确保在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。假如有多个线程试图同时访问临界区，那么在有一个线程进入后其他任何试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程能够继续抢占，并以此达到用原子方式操作共享资源的目的
  • 虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程
• 多个线程访问同一个临界区的原则：
  • 一次最多只能一个线程停留在临界区内
  • 不能让一个线程无限地停留在临界区内，否则其它线程将不能进入该临界区

相关 Winsows API 函数

• (1) 定义一个临界区对象（通常为全局变量）

CRITICAL_SECTION cs

• (2) 临界区对象初始化

InitializeCriticalSection(&cs)

• (3) 进入 / 离开临界区

// 执行完 EnterCriticalSection 必须要执行匹配的 LeaveCriticalSection，
// 否则临界区保护的共享资源将永远不会被释放
EnterCriticalSection(&cs)	
LeaveCriticalSection(&cs)

• (4) 释放临界区对象

DeleteCriticalSection(&cs)

互斥量 (Mutex)

• 互斥量跟临界区很相似，只有拥有互斥对象的线程才具备访问资源的权限，由于互斥对象只有一个，因此每次只能有一个线程获得互斥量，任何情况下此共享资源都不会同时被多个线程所访问
  • 线程结束时，线程所获得的 Mutex 会自动释放
  • 互斥量比临界区复杂。因为使用互斥不但能够在同一进程不同线程中实现资源的安全共享，而且能够在不同进程的线程之间实现对资源的安全共享
    • 经常用于保护多个线程访问的内存块、控制对共享资源的访问

相关 Winsows API 函数

两个重要的同步等待函数

• WaitForSingleObject: 使线程进入等待状态,直到一个对象变为已通知状态
  • hHandle 参数表示等待到句柄标识的进程终止运行为止
  • dwMilliseconds 参数表示调用线程愿意等待的时间，如果在等待的时候规定的时间到了，那么该函数无论如何都会返回；0 表示该函数立即返回；INFINITE (-1) 表示线程被挂起，直到 hHandle 所指向的对象变为已通知状态；当然，传递 INFINITE 有些危险。如果对象永远不变为已通知状态，那么调用线程永远不会被唤醒，它将永远处于死锁状态， 不过，它不会浪费宝贵的 CPU 时间
  • 返回值能够指明调用线程为什么再次变为可调度状态。如果线程等待的对象变为已通知状态，那么返回值是 WAIT_OBJECT_0。如果设置的超时已经到期，则返回值是 WAIT_TIMEOUT。如果将一个错误的值（如一个无效句柄）传递给 WaitForSingleObject，那么返回值将是 WAIT_FAILED
• WaitForMultipleObjects: 允许调用线程同时查看若干个内核对象的已通知状态
  • dwCount 参数用于指明想要让函数查看的内核对象的数量。这个值必须在 1 与 MAXIMUM_WAIT_OBJECTS（在 Windows 头文件中定义为 64）之间
  • phHandle 参数是指向内核对象句柄的数组的指针
  • fWaitAll 参数允许以两种不同的方式来使用 WaitForMultipleObjects 函数
    • FALSE 表示让线程进入等待状态，直到指定内核对象中的任何一个变为已通知状态
    • TRUE 表示让线程进入等待状态，直到所有指定的内核对象都变为已通知状态
  • 函数返回值告诉调用线程，为什么它会被重新调度。除了 WAIT_FAILED 和 WAIT_TIMEOUT 外
    • 如果 fWaitAll 参数传递 TRUE，同时所有对象均变为已通知状态，那么返回值是 WAIT_OBJECT_0
    • 如果为 fWaitAll 传递 FALSE，那么一旦任何一个对象变为已通知状态，该函数便返回。这种情况下，可能想要知道哪个对象变为已通知状态。返回值是 WAIT_OBJECT_0 与（WAIT_OBJECT_0 + dwCount - 1）之间的一个值。换句话说，如果返回值不是 WAIT_TIMEOUT，也不是 WAIT_FAILED，那么应该从返回值中减去 WAIT_OBJECT_0。产生的数字是作为第二个参数传递给 WaitForMultipleObjects 的句柄数组中的索引。该索引说明哪个对象变为已通知状态

DWORD WaitForSingleObject( 
	HANDLE hHandle, 
	DWORD dwMilliseconds
	); 
	
DWORD WaitForMultipleObject(
	DWORD  dwCount,
	CONST  HANDLE* phHandle,
	BOOL  fWaitAll,
	DWORD dwMilliseconds 
	);

互斥量 API

• 互斥量的创建，返回句柄

HANDLE CreateMutex(
	PSECURITY_ATTRIBUTES psa, 	// 安全属性的指针
	BOOL bInitialOwner, 		// 初始化互斥对象的所有者
	// True 代表主线程拥有互斥对象 但是主线程没有释放该对象
	// False 代表当前没有线程拥有这个互斥对象
	PCTSTR pszName				// 指向互斥对象名的指针 
	// 给互斥量取名->句柄只能在同一进程可见，但名字可以实现多进程之间的互斥访问
);

• 为现有的一个已命名互斥对象创建一个新句柄
  • MUTEX_ALL_ACCESS 请求对互斥对象的完全访问
  • MUTEX_MODIFY_STATE 允许使用 ReleaseMutex 函数
  • SYNCHRONIZE 允许使用互斥对象同步

HANDLE OpenMutex(
	DWORD fdwAccess, 		// access
	BOOL bInheritHandle, 	// inheritance option 
	PCTSTR pszName			// object name
);

• 释放互斥量

HANDLE ReleaseMutex(
	HANDLE hMutex
);

• 等待互斥量

DWORD WaitForSingleObject(
	HANDLE hHandle, 
	DWORD dwMilliseconds 
);

事件

• 事件对象也能够通过通知操作的方式来保持线程的同步，主要用途是标志事件的发生，并以此协调线程的执行顺序。事件能够实现不同进程中的线程同步操作，并且能够方便的实现多个线程的优先比较等待操作，例如写多个 WaitForSingleObject 来代替 WaitForMultipleObjects，从而使编程更加灵活

相关 Winsows API 函数

• 创建事件内核对象，返回句柄

HANDLE CreateEvent(
	PSECURITY_ATTRIBUTES psa, 	// 安全属性
	BOOL fManualReset,			// 复位方式
	BOOL fInitialState, 		// 指定事件对象的初始状态
								// True: 初始状态为有信号状态；
								// False: 初始状态为无信号状态
	PCTSTR pszName				// 对象名称
);

信号量

• 信号量对象对线程的同步方式和前面几种方法不同，信号允许多个线程同时使用共享资源，这和 PV 操作相同。他允许多个线程在同一时刻访问同一资源，但是需要限制同一时刻访问此资源的线程数目

总结

• 互斥量、事件、信号量都是内核对象，可用于进程间的线程同步；而临界区是进程内对象只能用于进程内的线程同步。虽然在同一个进程内同步时，互斥量和临界区的功能相似，但在性能上临界区要优于互斥量
• 事件和其他几个同步方法的不同在于事件的主要作用不是保护共享的资源，而是用于等待某个事件和在特定的事件发生时发送信号，以协调线程之间的动作
• 信号量与其他同步方法的区别在于它允许一个以上的线程同时访问共享资源，而其他线程同步方法都保证同时只能有一个线程访问共享的资源。信号量的主要功能是用于资源计数