【操作系统】3.进程管理_操作系统pcd

1. 进程和线程

1.1 进程的概念

进程是资源分配的基本单位。

概念：进程是指一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。

进程的特点

a) 动态性，可动态创建和结束进程
b) 并发性，进程可以被独立调度并占用CPU运行
c) 独立性，不同进程之间互相不影响
d) 制约性，因访问共享数据/资源或进程间同步产生制约

进程的组成

• PCB(进程控制块)
• 程序段
• 数据段
• 通用寄存器
• 状态寄存器

总之，进程包含了正在运行的一个程序的所有状态信息。

进程与程序的联系

程序是进程的基础，进程是程序功能的体现。

进程与程序的区别

1. 程序静态，进程动态。

• 程序是有序代码的集合；
• 进程是程序的执行，执行中可以是核心态/用户态

2. 进程是暂时的，是状态变化的过程，程序是永久的；
3. 组成不同，进程包括程序，数据，进程控制块；

1.2进程控制块(PCB)

进程控制块是操作系统管理控制进程运行所用的信息集合，它描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

操作系统使用PCB来描述进程的基本情况以及运行变化的过程。且PCB是进程存在的唯一标志，每个进程都在操作系统中有一个对应的PCB。

PCB的创建和回收

进程创建时生成该进程的PCB，进程终止时回收它的PCB，它的生命周期和进程的生命周期一样。

进程的组织管理：通过对PCB的组织管理来实现进程控制

进程控制块的内容：

1. 进程标识信息
2. 处理器现场保存
3. 进程控制信息
   1. 调度和状态信息，进程和处理机使用情况调度
   2. 进程间通信信息，进程间通信相关的各种标识
   3. 存储管理信息，指向进程映像存储空间数据结构
   4. 进程所用资源，进程使用的系统资源，如打开文件等
   5. 有关数据结构连接信息，如PCB相关的进程队列

关于进程控制块的描述正确的是（ABCD）

A.操作系统用进程控制块来描述进程的基本情况以及运行变化的过程
B.进程控制块是进程存在的唯一标志
C.每个进程都在操作系统中有一个对应的进程控制块
D.操作系统管理控制进程运行所用的信息集合是进程控制块

1.3 进程生命周期

进程的生命周期如下：进程创建，进程执行，进程等待，进程抢占，进程唤醒，进程结束.

进程创建

创建完成进程会进入就绪队列中，等待进程执行

进程执行

内核选择一个就绪的进程，让它占用处理机并执行进程，如何选择进程（处理机调度算法）

进程等待

进程进入等待（阻塞）状态的情况：

• 请求并等待系统服务，无法马上完成；
• 启动某种操作，无法马上完成
• 需要的数据没有到达；
• 内部原因导致进程等待。

进程抢占

• 高优先级的进程就绪；
• 进程执行当前时间用完。

进程唤醒

• 被阻塞进程需要的资源可被满足；
• 被阻塞进程等待的事件到达。
• 进程只能被别的进程或者操作系统唤醒。

进程结束

需要退还系统资源。

• 正常退出（自愿）
• 错误退出（自愿）
• 致命错误（强制性）
• 被其他进程杀死（强制性）

1.4 进程状态变化模型

进程的三种基本状态：

• 就绪状态(ready)：当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行时的状态；
• 运行状态(running)：当一个进程正在处理机上运行时；
• 等待状态(或阻塞状态blocked)：一个进程正在等待某一事件而暂停运行时的状态，如等待资源，等待I/O完成，请求缓存空间。

进程还有其它的基本状态：

• 创建状态(new)，一个进程正在被创建，还没被转到就绪状态之前的状态。
• 结束状态(exit)，一个进程正在从系统中消失时的状态，这是因为进程结束或由于其它原因所导致。

1.5 进程挂起

在不少系统中进程只有上述三种状态，但在另一些系统中又增加了一些新状态。

处于挂起状态的进程映像在磁盘上，目的是减少进程占用内存（进程存储在外存中）。

新增加了两个挂起状态：
等待挂起状态，进程在外存并等待某事件的出现。

就绪挂起状态，进程在外存，只要进入内存即可运行。

挂起：把一个进程从内存中转到外存中。

引入挂起状态的原因：

1）终端用户的请求      当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时使自己的程序静止下来。亦即，使正在执行的进程暂停执行；若用户进程正处于就绪状态而未执行，则该进程暂不接受调度，以便用户研究其执行情况或对程序进行修改。这种静止状态称为挂起状态。

2）父进程请求     有时父进程希望挂起自己的某个子进程，以便考查和修改该子进程，或者协调各子进程间的活动。

3）负荷调节的需要     当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。

4）操作系统的需要     操作系统有时希望挂起某些进程，以便检查运行中德资源使用情况或进行记账。

由操作系统来维护一组队列，表示系统中所有进程的当前状态，不同队列表示不同状态，根据进程状态不同，进程PCB加入相应队列。进程状态变化时，它所在的PCB会从一个队列换到另一个队列。

1.6 线程的概念

线程是独立调度的基本单位。

引入线程可以提高进程内部的并发性。多进程并发比较复杂，在进程内部引入多线程机制会提高进程内部的并发性。

多进程的实现系统之间的通信和数据共享复杂（要经过内核共享数据）且系统的开销较大，因此在进程内部增加一类实体，实体之间可以并发执行，且实体之间共享相同的地址空间，因此引入线程的概念。

线程的概念：线程是进程的一部分，描述指令流执行状态，他是进程中的指令执行流的最小单元，是CPU调度的基本单位。

进程的作用变成了资源分配，进程由一组相关资源构成，包括地址空间（代码段、数据段）打开文件等各种资源。线程作为处理机调度角色，线程描述在进程资源环境中的指令流执行状态。（线程是程序执行的最小单元）。

线程的特点：

1. 一个进程可以同时存在多个线程
2. 各个线程之间可以并发的执行
3. 各个线程之间可以共享地址空间和文件等资源
4. 缺点：一个线程崩溃，会导致其他所属进程的所有线程崩溃。

1.7 用户线程与内核线程

用户线程：

• 由一种用户级别的线程库函数来完成线程的管理包括线程的创建、终止、同步和调度。
• 不依赖于操作系统的内核，内核不了解用户线程的存在，可用于不支持线程的多进程操作系统；在用户空间实现的线程机制，每个进程有私有的线程控制块列表。
• 同一进程内的用户线程切换速度快，无需用户态／核心态切换。允许每个进程拥有自己的线程调度算法。
• 不足之处：线程发起系统调用而阻塞时，则整个进程进入等待；不支持基于线程的处理机抢占，只能按照进程分配CPU时间，多个线程进程中，每个线程的时间片较少。

内核线程

• 由内核通过系统调用实现的线程机制，由内核完成线程的创建、终止和管理。
• 特征如下：由内核维护PCB和TCB；线程执行系统调用而被阻塞不影响其他线程。
• 线程的创建、终止和切换相对较大

线程和进程的区别

• 资源：进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
• 调度：线程是CPU调度单位，在同一进程中，线程的切换并不会引起进程切换。
• 系统开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，线程切换时只需保存和设置少量寄存器内容，开销很小。（线程要保存少量的寄存器内容）
• 通信方面：线程间可以直接通过读写同一进程中的数据进行通信，但进程通信需要借助IPC。

2. 进程控制

2.1 进程切换

进程切换主要涉及资源保存与恢复。

使用进程控制块PCD保存内核的进程状态记录。内核将相同状态的进程的PCB放置在同一个队列当中。

进程切换暂停当前运行进程，从运行状态变成其他状态。
要调度另一个进程从就绪状态变成运行状态。
要保存进程生命周期的信息（寄存器（PC，SP．．．）CPU状态，内存地址空间。

2.2 进程创建

操作系统系统调用供用户创建进程。

a) Windows进程创建API：　CreateProcess（filename）

b) Unix或者Linux进程创建系统调用：　fork／exec 重点掌握fork

1. fork（）把一个进程复制成两个进程fork后子进程和父进程除PID不同外其他相同。
2. exec（）用新程序来重写当前进程，重写进程写入新进程的执行函数

c) fork()创建一个继承的子进程的步骤

1. 复制父进程的所有变量和内存
2. 复制父进程的所有CPU寄存器（有一个寄存器例外）（fork进程父进程和子进程的PID不同）
3. Fork()返回值可方便后续使用，子进程可使用getpid()获取PID。对于父进程fork()返回的是child PID，对于子进程返回值为0，由此可以区分父进程和子进程。
4. 程序加载与执行：系统调用exec（）加载新程序取代当前运行程序exec_status = exec(“calc”, argc, argv0, argv1, …)修改复制进程的参数

Copy on Write（COW）技术：在Linux程序中，fork（）会产生一个和父进程完全相同的子进程，把父进程的内容复制一份 但子进程在此后多会exec系统调用再把父进程内容覆盖，出于效率考虑，linux中引入了“写时复制“技术，也就是只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程。
https://www.cnblogs.com/wuchanming/p/4495479.html

2.3 进程加载

用户应用程序通过系统调用exec（）加载执行可执行文件。

a) 程序加载和执行系统调用exec（），允许进程“加载”一个完全不同的程序，并从main开始执行
b) 允许进程加载时指定启动参数（argc, argv）．
c) exec调用成功时，它是相同的进程，和加载之前原进程的PID参数相同但运行了不同的程序。
d) 代码、堆、栈的数据被完全重写。

2.4 进程等待与退出

进程等待与退出是父子进程之间的交互。

wait()函数：系统调用函数，用于父进程等待子进程的结束。

• 子进程结束时通过exit（）向父进程返回一个值
• 父进程通过wait（）接受并处理返回值

那么就会涉及到exit和wait的执行顺序问题。

父进程先wait，子进程再exit：

• 有子进程存活时，父进程进入等待状态，等待子进程的返回结果；当某子进程调用exit（）时，唤醒父进程，将exit（）返回值作为父进程中wait的返回值
• 有僵尸子进程等待时，wait（）立即返回其中一个值
• 无子进程存活时，wait（）立刻返回。

进程的有序终止：子进程先exit，然后父进程wait。

1. 将调用参数作为进程的“结果”
2. 关闭所有打开的文件等占用资源
3. 释放内存
4. 释放大部分进程相关的内核数据结构
5. 检查是否父进程是存活着的
   a) 如果存活，保留结果的值直到父进程需要它，进入僵死状态
   b) 如果没有，它释放所有的数据结构，进程结果。
6. 清理所有等待的僵死进程

3. CPU调度

通过进程调度算法从进程就绪队列中选择一个进程占用处理机，不同环境下的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

3.1 CPU调度概念

从就绪队列中挑选下一个占用CPU运行的进程。

调度程序：是指挑选就绪进程的内核函数。

要解决的问题：
i. 调度策略，依据什么原则挑选进程和线程。
ii. 调度时机，什么时候进行调度。

调度时机

• 进程从运行状态切换到等待状态。
• 进程被终结了
• 非抢占系统：当前进程主动放弃CPU
• 可抢占系统：中断请求被服务例程响应完成时；当前进程被抢占，进程时间片用完，进程从等待切换到就绪。

若当前进程因时间片用完而让出处理机时，该进程应转变为就绪状态。

3.2 调度准则

调度策略要解决的问题是挑选就绪队列中的哪一个进程。

调度算法性能指标：

• CPU使用率，CPU处于忙状态的时间百分比
• 吞吐量，单位时间内完成的进程数量
• 周转时间，进程从初始化到结束的总时间
• 等待时间，进程在就绪队列中的总时间
• 响应时间，从提交请求到产生响应的时间

希望“更快”的服务：高吞吐量和低延迟。

3.3 就绪队列调度算法

批处理系统没有太多的用户操作，在该系统中，调度算法的目标是保证吞吐量和周转时间。

先来先服务算法（FCFS，First　Come　First　Served）

依据进程进入就绪状态的先后顺序排列。

进程进入等待或结束状态时，就绪队列中的下一个进程占用CPU。

特点

• 平均等待时间波动较大。如果短进程排在长进程后面会导致周转时间较长。
• I/O资源和CPU资源的利用率较低；例如一个CPU密集型进程长时间占用CPU时间长，会导致I／O设备闲置时，I/O密集型进程也等待。

短进程优先算法SPN

既然在先来先服务算法中，把短进程排在前面可以减少周转时间，那么可以一直选择就绪队列中执行时间最短进程占用CPU进入运行状态，就是短进程优先算法。

就绪队列按预期的执行时间来排序，具有最优平均周转时间。

如果有一个进程正在运行，突然出现另一个时间更短的进程，此时允许更短的进行抢占。

缺点：

1. 可能导致饥饿，连续的短进程会使长进程无法获得CPU资源。
2. 需要预知未来预估下一个CPU计算的持续时间。

最高响应比优先算法HRRN

在短进程优先算法中长进程会发生饥饿，改进：选择就绪队列中响应比R值最高的进程。

R＝（ｗ＋ｓ）／ｓ；　ｗ：等待时间，ｓ：执行时间。
1

特点：

• 不可抢占
• 关注进程的等待时间
• 防止无限期推迟　避免饥饿。
• 有利于短作业又兼顾到长作业。

时间片轮转算法RR（Round　Robin）

时间片：处理机分配资源的基本时间单元

算法思路：时间片结束时，按照FCFS先来先服务算法切换到下一个就绪进程，长度为ｎ个的就绪队列每隔（n-１）个时间片进程执行一个时间片。

RR算法开销

存在额外的上下文切换（进程现场保护）资源切换 开销大

时间片长度

• 时间片太大：等待时间过长，极限情况下会退化成FCFS(先来先服务)
• 时间片太小：反映迅速但产生大量的上下文切换，大量的上下文切换影响到系统吞吐量。
• 时间片长度选择一般根据经验规则，维持上下文切换开销处于１％以内。

兼顾就绪队列排队和时间片划分的组合算法，也是现实操作系统使用的算法

多级反馈队列算法MLFQ

多级反馈队列调度算法是一种根据先来先服务原则给就绪队列排序，为就绪队列赋予不同的优先级数，不同的时间片，按照优先级抢占CPU的调度算法。

就绪队列被划分成多个独立的子队列，每个队列拥有自己的调度策略。

在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。

该算法为不同列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片愈小。

公平共享调度算法FSS（Fair Share Scheduling）

FSS控制用户对系统资源的访问。

可能出现一些用户组比其他用户组更重要，为了保证不重要的组无法垄断资源，可以将未使用的资源按比例分配，没有达到资源使用率目标的组获得更高的优先级。

传统调度算法总结

• 先来先服务算法：简单，不公平，平均等待时间波动很大
• 短进程优先算法：
  • 不公平，平均周转时间较小
  • 需要精确预测计算时间
  • 可能导致饥饿（耗时的进程得不到调度机会）
• 最高响应比算法：基于SPN调度， 不可抢占
• 时间片轮转算法：公平，但平均等待时间较差
• 多级反馈队列： 多种算法的综合
• 公共共享算法： 公平是第一要素

3.4 实时操作系统

实时操作系统：正确性依赖于其时间和功能两方面的操作系统。实时性最重要。

• 实时操作系统的性能指标
  • 时间约束的及时性(deadlines)
  • 速度和平均性能相对不重要
• 实时操作系统的特性
  • 时间约束的可预测性

实时操作系统分类

• 强实时操作系统：要求在指定时间内必须完成重要的任务
• 弱实时操作系统
  重要进程有高优先级，但并非必须完成

实时任务：规定时间完成一次任务所需要的资源

周期性实时任务：一系列相似的任务有规律性地重复执行。

硬时限：错过任务时限会导致灾难性的后果，必须进行验证，保证最坏情况下能够满足时限。硬时限可以保证系统的确定性。

可调度:表示一个实时操作系统能够满足任务时限要求。

软时限：通常能满足任务时限，若不满足则降低要求。尽力满足任务时限

可调度表示一个实时操作系统能够满足任务时限要求。

优先级反置

操作系统中高优先级进程长时间等待低优先级进程所占用资源的现象。基于优先级的可抢占调度算法均可出现优先级反置。

4.同步互斥

独立进程不和其他进程共享资源或状态，结果具备确定性和可重现性，调度顺序不重要。并发进程在多个进程间有资源共享，进程运行可能存在不确定性和不可重现。并发进程执行过程是不确定性和不可重现的，程序错误可能是间歇性发生的。然而需要进程之间的资源共享，并发执行可以加速实现进程间的协作。

原子操作是指一次不存在任何中断或失败的操作，要么成功要么失败，执行的结果没有暂态。

操作系统需要利用同步机制在并发执行的同时，保证一些操作是原子操作。

4.1 实际中的问题

两人买面包问题：

正确方式：
利用两个原子操作实现一个锁（lock），处理过程不会被打断

Lock.Acquire()

• 在锁被释放前一直等待，然后获得锁
• 如果两个线程都在等待同一个锁，并且同时发现锁被释放了，那么只有一个能够获得锁

Lock.Release()

• 解锁并唤醒任何等待中的进程

breadlock.Acquire(); // 进入临界区
if(noBread) {
  buy bread;
}
breadlock.Release(); // 退出临界区
1
2
3
4
5

进程的交叉关系

关系：

1. 互斥（mutual exclusion）一个进程占用资源，其他进程不能使用
2. 死锁（deadlock）多个进程占用部分资源，形成循环等待
3. 饥饿（starvation） 其他进程可能轮流占用资源，一个进程一直得不到资源

4.2 临界区和禁用硬件中断同步方法

临界区

对临界区资源进行访问的那段代码称为临界区。临界区每次进入都需要进行条件检查。

为了互斥访问临界资源，每个进程在进入临界之前，需要先进行检查。

• 进入区，临界区之前存在进入区，进入区负责检查可否进入临界区的一段代码，如果可以进入，设置相应“正在访问临界区”标志。
• 退出区，清除“正在访问临界区”标志。

临界区的访问规则

• 空闲则入
  • 没有进程在临界区时，任何进程可进入
• 忙则等待
  • 有进程在临界区时，其他进程均不可以进入临界区
• 有限等待
  • 等待进入临界区不能无限期等待。
• 让权等待（可选）
  • 不能进入临界区的进程，应释放CPU（不可一直查询临界区是否可访问）

临界区的实现方法：禁用中断 软件方法 更高级的抽象方法

• 禁用硬件中断，没有中断，没有上下文切换，因此没有并发。（很少使用，不得不用时才使用，适用于单处理机）
  • 硬件将中断处理延迟到中断被启用之后
  • 现代计算机体系结构都提供指令来实现禁用中断
  • 缺点：禁用中断后，进程无法被停止；可能导致其他进程处于饥饿状态；临界区可能很长，无法确定响应中断所需要的时间。
• 软件同步：多个线程可以通过共享一些变量来同步它们的行为。
  • 该算法复杂，需要两个进程间的共享数据项。
  • 算法需要忙等待，浪费CPU时间。
• 高级抽象的同步方法
  • 锁
    • 一个抽象的数据结构
    • 一个二进制变量(锁定/解锁)
    • Lock::Acquire()锁被释放前一直等待，然后得到锁
    • Lock::Release()释放锁，唤醒任何等待的进程

原子操作指令锁特征

• 优点
  • 适用于单处理机或者共享内存的多处理机中任意数量的进程同步(禁用中断只适用于单处理机 多处理机的情况下 禁止单个处理机的中断 其他处理机仍然能够响应中断)
  • 简单且容易证明
  • 支持多临界区
• 缺点
  • 忙等待锁会消耗处理机时间
  • 可能导致饥饿,进程离开临界区时有多个等待进程的情况(并没有按照先来后到的顺序)
• 死锁
  • 拥有临界区的低优先级进程，但请求访问临界区的高优先级进程获得处理机并等待临界区(低优先级等CPU,高优先级等临界区)

临界区同步方法总结：

• 锁是一种高级的同步抽象方法，互斥可以使用锁来实现，但需要硬件支持（原子操作）
• 禁用中断（仅限于单处理器）
• 软件方法（复杂）
• 原子操作指令（单处理器和多处理器均可，且支持任意数量的线程同步）需硬件支持。

5.信号量与管城

多线程或者多进程并发会导致资源竞争。需要对多线程和多进程进行同步，协调多线程对共享数据的访问，且在任何时候只能有一个线程执行临界区代码。

此外，确保同步正确的方法有底层硬件支持（TS指令 原子操作）和高层次的编程抽象。信号量和管道为高层次的编程抽象方法。

自旋锁为什么无法按先来先服务方式使用资源？
原因：自旋锁是由TS指令实现的临界区申请操作，第一个检测到临界区空闲的申请者而不是第一个开始检测的申请者进入。也就是说，访问顺序是由硬件随机决定的。如果要实现FIFO方式，一般都需要一个队列。

5.1 信号量

信号量是操作系统提供的一种协调共享资源访问的方法。

软件同步是平等线程间的一种同步协商机制，而操作系统是管理者，由操作系统仲裁谁来使用资源，其地位高于进程，因此信号量高于软禁同步。

信号量用来表示系统资源的数量。

信号量与软件同步区别：

• 软件同步是平等线程间的一种同步协商机制；
• 信号量是由地位高于进程的管理者OS协调的同步机制

信号量的组成

由一个整形（sem）变量和两个原子操作组成。sem表征资源的数量。
P()：sem减1，增加一个线程
若sem < 0, 进入等待，否则继续
V()：sem加1，释放一个线程
sem <= 0，唤醒一个等待进程

信号量的特性

信号量是被保护的整数变量

• 初始化完成后，只能通过P()和V() 操作修改
• 由操作系统保证PV操作是原子操作
• P() 可能阻塞(没有资源，处于等待状态)
• V() 不会阻塞(释放资源，唤醒等待状态的进程)

例题：如果有5个进程共享同一程序段，每次允许3个进程进入该程序段，若用PV操作作为同步机制则信号量S为-1时表示有三个进程进入了程序段，有一个进程在等待。

通常假定信号量是公平的

• 线程不会被无限期阻塞在 P() 操作（实际系统中有一个最长时限的参数，超时之后错误返回）
• 假定信号量等待先进先出（但是在实际系统中公平有所偏差）

信号量的分类

• 二进制信号量，资源数目为 0 或 1
• 资源信号量，可为任何非负值。

两者等价，基于一个可以实现另一个。

5.2 信号量的使用

互斥访问

临界区的互斥访问控制。

mutex = new Semaphore(1);
1

每类资源设置一个信号量，初值为 1。

mutex->P();
Critical Section;
mutex->V();
1
2
3

不申请直接释放，会导致多个线程进入缓冲区。只申请不释放，会导致缓冲区无线程，但谁也进不去。

• P() 保证互斥访问临界资源
• V() 在使用后释放临界资源
• PV操作不能次序错误、重复 、遗漏

条件同步

condition = new Semaphore(0);
1

条件同步设置一个信号量，初值为 0

线程a执行P操作后信号量为负值，进入等待状态，线程B执行V操作后，信号量又回到0，此时线程a可以继续往下执行，通过这种方式实现条件同步。

总结：什么是信号量？它与软件同步方法的区别在什么地方？

信号量是由操作系统提供的一种协调共享资源访问的方法。信号量是一种抽象数据类，由一个被保护的整形变量（sem）和P()、V()两个原子操作组成，表示系统资源的数量。

区别：

• 软件同步是平等线程间的一种同步协商机制；
• 信号量是由地位高于进程的管理者OS协调的同步机制。

生产者-消费者问题

生产者在生成数据后放在一个缓冲区里，消费者从缓冲区取出数据处理，任何时刻只能有一个生产者或消费者可访问缓冲区。

解决方式：

a)	任何时刻只能有一个线程操作缓冲区（互斥访问） 二进制信号量mutex
b)	缓冲区为空时，消费者必须等待生产者（条件同步）资源信号量fullBuffers
c)	缓冲区满时，生产者必须等待消费者（条件同步） 资源信号量emptyBuffers
1
2
3

使用信号量存在的问题：

1. 容易出错，使用的信号量已经被另一个线程占用，或者忘记释放信号量；
2. 信号量不可以解决线程死锁的问题。

5.3 管程

为了解决信号量出现的一些问题，例如在生产者-消费者中，PV操作是在两个不同的进程中，很容易出现多写漏写的情况。

管程将共享资源相关的PV操作集中到一起从而简化进程之间的同步控制。

管程在信号量的基础上提供条件同步，使用更容易，所以 Java 采用的是管程技术。synchronized 关键字及 wait()、notify()、notifyAll() 这三个方法都是管程的组成部分。

管程是一种用于多线程互斥访问共享资源的程序结构。

• 采用面向对象方法，简化了线程间的同步控制；
• 任一时刻最多只有一个线程执行管程代码；
• 正在管程中的线程可临时放弃管程的互斥访问等待时间出现恢复
• 管程在对象/模块中，收集相关共享数据，定义访问共享数据的方法。

可以假定管程为赛车跑道，为了安全任意一个时刻只能有一辆车在跑道疾驰，过程中会暂停更换零件，这时允许其他赛车进入跑道。

管程与临界区有什么异同？
相同点：在任一时刻最多只有一个线程执行管程代码或临界区代码；

不同：正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复；而临界区不支持临时退出；

管程和信号量的比较：

1. 信号量可以并发，并发量是取决于s的初始值，而管程则是在任意时刻都是只能有一个。
2. 信号量的P操作在操作之前不知道是否会被阻塞，而管程的wait操作则是一定会被阻塞。
3. 管程的进程如果执行csignal后，但是没有在这个条件变量上等待的任务的话，则丢弃这个信号。进程在发出信号后会将自己置于紧急队列之中，因为他已经执行了部分代码，所以应该优先于入口队列中的新进入的进程执行。
4. 当前进程对一个信号量加1后，会唤醒另一个进程，被唤醒进程程与当前进程并发执行

管程组成

一个锁 + 0或者多个条件变量；锁是控制管程代码的互斥访问(入口)，条件变量用来管理共享数据的并发访问

特点：

• 局部数据变量只能被管程的过程访问
• 一个进程通过调用管程的一个过程进入管程
• 在任何时候，只能有一个进程在管程中执行

条件变量

条件变量为管程内的等待机制：进入管程的线程因资源被占用而进入等待状态，每个条件变量表示一种等待原因，对应一个等待队列。

• Wait()操作
  • 将自己阻塞在等待队列中
  • 唤醒一个等待者或释放管程的互斥访问
• Signal()操作
  • 将等待队列中的一个线程唤醒
  • 如果等待队列为空则等同于空操作

信号量和条件变量是并发问题的两种处理模型。

• 信号量将并发的问题抽象为有限的资源，用计数器表示，资源足够时往下走，不够时等待。
• 条件变量则将并发的问题抽象为事件，当满足某种事件的时候，往下走，不满足某种事件的时候暂时放弃锁。

5.4 哲学家就餐问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XyLL54Ld-1592980170374)(https://i.loli.net/2019/07/29/5d3e507177ae590470.png)]

方案一:
信号量法，两次P操作拿左边和右边刀叉 吃完放弃 两次V操作。

#define N 5 // 哲学家个数
semaphore fork[5]; // 互斥操作，信号量初值为1
void philosopher(int i) { 
    // 哲学家编号：0 － 4
    while (ture) {
        think();
        P(fork[i]); // 拿左边的叉子
        P(fork[(i + 1) % N]); // 拿右边的叉子
        eat();
        V(fork[i]); // 放下左边的叉子
        V(fork[(i + 1) % N]); // 放下右边的叉子
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

有可能5个人同时拿左边叉子，都拿不到右边叉子，形成死锁。

方案二:添加一个互斥信号量，将就餐变成一个近似临界区，每次只能有一个人就餐。

#define N 5 // 哲学家个数
semaphore fork[5]; // 信号量初值为1
semaphore mutex; // 互斥信号量，初值1
void philosopher(int i)
// 哲学家编号：0 － 4
    while(TRUE) {
        think();
        P(mutex); // 进入临界区	 只有一个哲学家能就餐

        P(fork[i]); // 去拿左边的叉子
        P(fork[(i + 1) % N]);// 去拿右边的叉子
        eat();	
        V(fork[i]); // 放下左边的叉子
        V(fork[(i + 1) % N]); // 放下右边的叉子

        V(mutex); // 退出临界区	
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

任何时间只有一个哲学家就餐，性能差。

方案三

• 和方案1一样，使用5个信号量表示筷子
• 哲学家根据编号不同，拿取筷子的顺序不同,从而避免都拿到左边刀叉而等待右边刀叉形成循环等待的情况
• 此时没有死锁，且允许两个人同时就餐

#define N 5 // 哲学家个数
semaphore fork[5]; // 信号量初值为1
void philosopher(int i) // 哲学家编号：0 － 4
    while(TRUE) {
        think();

        if (i % 2 == 0) { 
            // 偶数 先拿左 后拿右 奇数 先拿右 后拿左
            P(fork[i]); // 去拿左边的叉子
            P(fork[(i + 1) % N]); // 去拿右边的叉子
        } else {
            P(fork[(i + 1) % N]); // 去拿右边的叉子
            P(fork[i]); // 去拿左边的叉子 
        }
        eat();

        V(fork[i]); // 放下左边的叉子
        V(fork[(i + 1) % N]); // 放下右边的叉子
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

若系统中有五台打印机，有多个进程均需要使用两台，规定每个进程一次仅允许申请一台，则在不发生死锁的情况下至多允许多少个进程参与竞争。

哲学家就餐问题：当5个进程的时候如果都同时申请到了1台，就发生死锁了。如果是4个进程，那必然有一个能申请到2台。

5.5 读者-写者问题

问题描述：读者只读取数据，不修改，且运行多个读者并发读取。写者可以读取和修改数据，读写互斥且写写互斥，不可并发写数据。

信号量解决读者写者问题

• 信号量WriteMutex：控制读写操作互斥，初始化为 1
• 读者计数Rcount：正在进行读操作的读者数目，初始化为 0
• 信号量CountMutex，控制对读者计数的互斥修改(保护读者计数)，初始化为 1

writer

P(WriteMutex);
    write();
V(WriteMutex);
1
2
3

reader

P(CountMutex); // 保护 Rcount
if (Rcount == 0)
    P(WriteMutex); 
//若为当前第一个读者，开启读写互斥
++Rcount; 
V(CountMutex);
read();
P(CountMutex);
--Rcount;
//若为当前最后一个读者，释放互斥访问权限
if (Rcount == 0)
    V(WriteMutex); 
V(CountMutex);
1
2
3
4
5
6
7
8
9
10
11
12
13

读者写者问题的优先策略：

• 读者优先策略
  • 只要有读者正在读状态，后来的读者都能直接进入
  • 若读者持续不断进入，则写者就处于饥饿
• 写者优先策略
  • 只要有写者就绪，写者应尽快执行写操作
  • 若写者持续不断就绪，则读者就处于饥饿

管程解决读者写者问题

管程的状态变量

AR = 0; // 正在读的读者
AW = 0; // 正在写的写者
WR = 0; // 等待读的读者
WW = 0; // 等待写的写者
Lock lock;
Condition okToRead;
Condition okToWrite;
1
2
3
4
5
6
7

reader

Database::Read() {
    // Wait until no writers;
    StartRead(); 
    read database;
    // check out – wake up waiting writers; 
    DoneRead();
}
Database::StartRead() {
    lock.Acquire();
    while ((AW+WW) > 0) { 
    //写者优先，只要有写者就等待
        WR++;
        okToRead.wait(&lock);
        WR--;
    }
    AR++;
    lock.Release();
}
Database::DoneRead() {
    lock.Acquire();
    AR--;
    if (AR == 0 && WW > 0) { 
    // 当前没有读者并有等待写的写者 则唤醒写者
        okToWrite.signal();
    }
    lock.Release();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

writer

Database::Write() {
    // Wait until no readers/writers;

    StartWrite(); 
    write database;
    // check out-wake up waiting readers/writers; 
    DoneWrite(); 
}
Database::StartWrite() {
    lock.Acquire();
    while ((AW+AR) > 0) {
    //写者优先，有正在写的写着或正在读的读者则等待
        WW++;
        okToWrite.wait(&lock);
        WW--;
    }
    AW++;
    lock.Release();
}
Database::DoneWrite() {
    lock.Acquire();
    AW--;
    if (WW > 0) {
    // 优先唤醒等待写的写者
        okToWrite.signal();
    }
    else if (WR > 0) {
    // 如果没有等待写的写者 才唤醒等待读的读者
        okToRead.broadcast();
    }
    lock.Release();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

while中的判断条件可根据优先策略进行调整，例子采取了写者优先策略。
以上管程在读/写操作时并没有申请互斥信号量，因为在之前申请互斥信号量时将正在/等待读/写的计数等设置完成，此时可确保读写正常进行。

6.死锁和进程通信

6.1 死锁

什么是死锁

死锁是由于竞争资源或者通信关系，两个或更多的并发进程各自占有某种资源而又都等待别的进程释放它们所占有的资源的现象。

进程访问资源的流程

1. 请求/获取 申请空闲资源
2. 使用/占用 进程占用资源
3. 释放 资源状态由占用变成空闲

资源分类

• 可重用资源(Resuable Resource)
  • 资源不能被删除且在任何时刻只能有一个进程使用
  • 进程释放资源后 其他进程可重用
  • 比如：处理器 I/O通道 存储器 设备 文件(进程访问过程中不能被删除) 数据库 信号量
  • 可能出现死锁(每个进程占用一部分资源并请求其它资源)
• 消耗资源(Consumable Resource)
  • 资源创建和消耗
  • 例如：在I/O缓冲区的中断 信号 消息
  • 可能出现死锁(进程间相互等待接受对方的消息)

资源分配图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-se48uhkY-1592980170376)(https://i.loli.net/2019/07/29/5d3e674039de655749.png)]

出现死锁的四个必要条件：

1. 互斥，在任何时候只能有一个进程使用一个资源实例
2. 持有并等待，进程保持至少一个资源，并正在等待获取其他进程持有的资源。
3. 非抢占，资源只有在进程使用后自愿释放
4. 循环等待， 存在等待进程集合 大家相互等待对方占用的资源

死锁处理办法

• 死锁预防(Deadlock Prevention)
  • 确保系统永远不会进入死锁状态(资源利用效率低)，限制并发进程对资源的请求，使系统任何时刻都不满足死锁的必要条件。
• 死锁避免(Deadlock Avoidance)
  • 在使用前进行判断 只允许不会出现死锁的进程请求资源
• 死锁检测和恢复(Deadlock Detection & Recovery)
  • 在检测到系统进入死锁状态后，进行恢复
• 由应用进程处理死锁：通常操作系统忽略死锁(鸵鸟算法)

死锁预防，破坏四个必要条件之一：

• 互斥
  • 把互斥的共享资源封装成可同时访问(缓冲区内部协调)
• 持有并等待
  • 进程请求资源时 要求它不持有任何其他资源（动态）
  • 仅允许进程在开始执行时，一次请求所有需要的资源（静态）
  • (特点)资源利用率低
• 非抢占
  • 如进程请求不能立即分配的资源则释放已占有资源(主动放弃)
  • 只在能够同时获得所有需要资源时 才执行分配操作
• 循环等待
  • 对资源排序，要求进程按顺序请求资源
  • 资源利用率低

死锁避免

• 在使用前进行判断，只允许不会出现死锁的进程请求资源。
• 要求进程声明需要资源的最大数目
• 限定提供与分配的资源数量,确保满足进程的最大需求(类似于银行贷款)
• 动态检查资源分配状态 确保不会出现环形等待

使用银行家算法避免死锁。

银行家算法

是一个避免死锁产生的算法。以银行借贷分配策略为基础，判断并保证系统处于安全状态。

规则

线程在第一次申请资源的时候声明所需最大资源量，在操作系统满足所有资源要求并完成任务后及时释放资源。

同时在线程申请资源不超过操作系统拥有资源最大值时，操作系统应尽量满足线程的需求。

数据结构

n = 线程数量 m = 资源类型数量
最大需求矩阵：Max(总需求量) ：n x m 矩阵，表示线程Ti最多请求类型Rj的资源Max[i, j]个实例
可利用资源向量：Available(剩余空闲量) 长度为 m 的向量，表示当前有Available[i]个类型Rj的资源可用
分配矩阵：Allocation(已分配量) = n x m 矩阵，表示当前分配了Allocation[i, j]个资源实例
需求矩阵：Need(未来需要量) = n x m 矩阵，表示未来需要Need[i, j]个资源实例
Need[i, j] = Max[i, j] - Allocation[i, j]
1
2
3
4
5
6

安全状态判断
安全状态判断是银行家算法的核心部分。其基本思想是判断当前的剩余资源可以满足某一个线程的未来需要，并且迭代到最后可以满足所有线程的序列生成一个安全序列。

1. Work 和 Finish 分别是长度为 m 和 n 的向量，初始化二者
   寻找线程Ti:

Work = Available // 当前资源剩余空闲量
Finish[i] = false for i : 1, 2, ..., n // 线程i没结束
1
2

2. 接下来找出Need比Work小的进程Ti，
   • Need[i] <= Work
   • Finish[i] = false
     没有找到满足条件的线程，转4
3. 存在满足条件的线程，线程Ti可以正常运行，结束后其占用资源可以回收

Work = Work + Allocation[i] //线程i的需求量小于当前剩余空闲资源量，所以分配给他之后再回收
Finish[i] = true 
1
2

转 2
4. 若所有线程Ti满足 Finish[i] == true,则为安全状态

银行家算法流程

初始化: Requesti 线程Ti的资源请求向量
      Requesti[j] 线程Ti请求资源Rj的实例
循环:
1.如果 Requesti ≤ Need[i], 转到步骤2。否则, 拒绝资源申请, 因为线程已经超过了其最大要求
2.如果 Requesti ≤ Available, 转到步骤3。否则, Ti 必须等待, 因为资源不可用
3.通过安全状态判断来确定是否分配资源给Ti: 生成一个需要判断状态是否安全的资源分配环境
Available = Available - Requesti;
Allocation[i] = Allocation[i] + Requesti;
Need[i]= Need[i] – Requesti;
若安全 则分配资源给Ti
若不安全 则拒绝Ti的资源请求
1
2
3
4
5
6
7
8
9
10
11

银行家算法示例

按照序列 T2->T1->T3->T4 运行不存在死锁。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0mxAJFyn-1592980170380)(https://i.loli.net/2019/07/29/5d3e8d5db415e75776.png)]

T2只需要一个R3资源，满足要求，先分配给T2线程，然后T2线程释放全部资源。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KmIbRLF2-1592980170383)(https://i.loli.net/2019/07/29/5d3e8d7ed6ac850896.png)]

接下来可用资源可以满足剩下三个资源中的任意一个，若银行家算法存在多个满足条件的线程，则多个线程之间的先后顺序并不重要，因为这些进程的资源最后都会释放，之后可以满足需求更大的线程资源请求。

死锁检测

允许系统进入死锁状态，定期调用死锁检测算法来搜索图中是否存在死锁。出现死锁时，用死锁恢复机制进行恢复。

死锁检测算法数据结构

与银行家算法相比，没有最大资源请求判断。

• Available(剩余空闲量)：长度为m的向量，当前有Available[i]个类型Rj的资源可用
• Allocation(已分配量)：n * m矩阵，当前每个进程已分配了Allocation[i, j]个资源实例

步骤：

1. 初始化 Work 和 Finish:

• Work = Available // work为当前资源剩余量
• Allocation[i] > 0时 Finish[i] = false 否则为 true //

2. 线程是否完成，寻找线程Ti满足:

• Finish[i] = false // 线程没有结束 且 此线程需要的资源量小于剩余资源量
• Requesti <= Work
• 若没有找到这样的i，转到4

3. 将找到的线程拥有的资源释放回当前空闲资源

• Work = Work + Allocation[i]
• Finish[i] = true
• 转到2

4. 没有资源可用，检查所有线程的 Finish 若有一个为 false ，系统处于死锁状态

死锁恢复

死锁恢复有进程终止和资源抢占两种方法.

进程终止

可以选择终止所有死锁的进程，也可以一次只终止一个进程直到死锁消除.

终止进程的顺序应该是

• 进程的优先级(选最低的)
• 进程已运行时间以及还需运行时间(运行时间越长越考虑留下，占用系统资源时间久)
• 进程已占用资源
• 进程完成需要的资源
• 终止进程数目(越少越好)
• 进程是交互还是批处理(让交互进程继续执行)

资源抢占

• 选择被抢占进程(成本最小的)
• 进程回退 返回到一些安全状态 重启进程到安全状态
• 可能出现饥饿 同一进程可能一直被选作抢占者

6.2 进程通信(IPC)

概述

进程通信（IPC，Inter-Process Communication）是进程进行通信和同步的机制。

IPC提供两个基本操作：发送操作（send message），接收操作 (receive message)。

• 进程通信流程

1. 在通信进程间建立通信链路
2. 通过 send/receive 交换信息

进程间通讯的实现方式大致可以分成两种：间接通信和直接通信。

直接通信

进程必须正确命名对方

• 通信链路的属性
  • 自动建立链路
  • 一条链路恰好对应一对通信进程
  • 每对进程之间只有一个链路存在
  • 链路可以为单向，但通常为双向

两个进程必须同时存在时，直接通信才可以进行。

间接通信

间接通信，通过操作系统维护的消息队列实现进程间的消息接收和发送。

每个消息队列都有一个唯一的标识，只有共享了相同消息队列的进程，才能够通信。

• 通信链路属性
  • 只有共享了相同消息队列的进程 才建立连接
  • 连接可以为单向也能为双向
  • 消息队列可以与多个进程相关联
• 间接通信流程
  • 创建一个新的消息队列
  • 通过消息队列发送和接受消息(只关注消息队列信息，与进程无关)
  • 销毁消息队列

阻塞（同步）与非阻塞通信(非同步)

通信链路缓冲
进程发送的消息在链路上可能有三种缓冲方式：

• 0 容量(缓存区没有容量)
  • 发送方必须等待接收方(必须有接收方)
• 有限容量
  • 通信链路缓冲队列满时 发送方必须等待
• 无限容量
  • 发送方不需要等待

进程通信的五种方式

管道、信号(量)、消息队列、共享内存

管道

管道：进程间基于内存文件(或内存缓冲区)的通信机制，一个进程可以通过管道把数据传递给另外一个进程。前者向管道中写入数据，后者从管道中读出数据。是一种简介通信机制。

创建管道时并不关心通信的另一端，可能从键盘、文件、程序读取，也可能写入到终端、文件、程序。

管道的两种操作：读管道和写管道。

• 读管道：read(fd, buffer, nbytes), scanf()是基于它实现的
• 写管道：write(fd, buffer, nbytes) printf()是基于它实现的
• 创建管道：pipe(rgfd); rgfd是2个文件描述符组成的数组， rgfd[0]是读文件描述符， rgfd[1]是写文件描述符。

信号

信号的作用是为了通知进程某个时间已经发生，是进程间的软件中断通知和处理机制 （如 ctrl-C 中断程序执行）

信号的接收处理方式：

• 捕获catch：执行进程指定的信号处理函数被调用
• 忽略Ignore: 执行操作系统指定的缺省处理，如进程终止，进程挂起等
• 屏蔽Mask：禁止进程接收和处理信号，可能是暂时的
• 不足：传送的信息量小，只有一个信号类型（处理快速的响应机制）

信号机制其实是在软件层次上对中断机制的一种模拟，一个进程收到信号和收到中断请求可以说是一样的；

中断和信号的区别是，前者运行在核心态（系统），后者运行在用户态，中断的响应比较及时，而信号的相应一般会有延迟；

消息队列

消息队列是由操作系统维护的以字节序为基本单位的间接通信机制。

每个消息是一个字节序列，相同标识的消息按着先进先出顺序组成一个消息队列（Message Queues）

共享内存

共享内存是把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制。

• 进程，每个进程都有私有内存地址空间，需明确设置共享内存段
• 线程，同一进程中的线程总是共享相同的内存地址空间
• 可快速、方便的共享数据
• 缺点是，必须用额外的同步机制来协调数据访问。