进程和线程

2.1_1 进程的概念

进程的定义

程序：静态，是存放在磁盘里的可执行文件，就是一系列的指令集合

进程：动态，是程序的一次执行过程。（同一程序多次执行会对应多个进程

进程的定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程的组成

一个进程实体（进程映像）由PCB、程序段和数据段组成。

进程是动态的，进程实体是静态的，反映了进程在某一时刻的状态

PCB是给操作系统使用的，程序段和数据段是给进程自己使用的

PCB是进程存在的唯一标志

PCB

程序在新建一个进程时，会分配一个唯一的不重复的进程ID（PID）

操作系统需要记录UID（进程所属用户）PID，分配的资源，进程运行情况。这些都被保存在一个数据结构进程控制块（PCB）中

但凡管理进程所需要的信息，都会被放在PCB中

PCB是进程存在的唯一标志，进程被创建时，操作系统会为其创建PCB，进程结束时，回收其PCB

程序段

程序的代码（指令序列，可被调度到CPU执行

程序段可被多个进程共享

数据段

运行过程中产生的各种数据

进程的特征

1. 动态性：最基本的特征，进程是程序的一次执行过程，动态产生、变化、消亡
2. 并发性：内存中有多个进程实体，可以并发执行
3. 独立性：进程是可以独立运行，独立获得资源，独立接受调度的基本单位
4. 异步性：各进程按照各自独立的不可预知的速度向前推进，操作系统需要提供“进程同步机制”来解决异步问题
5. 结构性：每个进程都会配置一个PCB，结构上看进程由程序段、数据段和PCB组成

2.1_2 进程的状态与转换

进程的状态

1. 创建态：进程刚被创建时处于“创建态”，操作系统为进程分配资源、初始化PCB
2. 就绪态：进程创建完成后进入“就绪态”，此时进程已经具备运行条件，但由于没有空闲CPU，暂时不能运行
3. 运行态：正在CPU上运行的进程
4. 阻塞态：进程运行的过程中可能请求某个事件发生（例如请求系统资源分配或者其他进程响应，在这个事件发生之前，进程无法继续执行，此时操作系统会让这个进程下CPU，进入“阻塞态”
5. 终止态：操作系统让进程下CPU，回收内存空间等资源，回收PCB

从运行态变为阻塞态是主动行为；从阻塞态变为就绪态是被动行为

进程状态的转换

在PCB中，有一个变量state表示进程当前状态

进程的组织

链式

索引方式

2.1_3 进程控制

进程控制的主要功能是对系统中所有进程实施有效管理，包括创建新进程、撤销已有进程、实现进程状态转换等功能

实现进程控制

进程控制使用原语实现

原语的执行具有原子性，执行期间不允许被中断
可以用“关中断指令”（不再检查中断信号）和“开中断指令”两个特权指令实现原子性
原语运行在核心态

进程控制相关的原语

• 进程的创建（创建态->就绪态

1. 创建原语
   1. 申请空白PCB（申请失败则创建失败
   2. 为新进程分配资源
   3. 初始化PCB
   4. 将PCB插入就绪队列
2. 引起进程创建的事件
   1. 用户登陆：分时系统中，用户登陆成功，系统会为其创建一个新进程
   2. 作业调度：多道批处理系统中，新的作业放入内存，会为其创建一个新进程
   3. 提供服务：用户想操作系统醍粗某些请求
   4. 应用请求：用户进程请求创建资格子进程

• 进程的终止（就绪/阻塞/运行态 -> 终止态 -> 无

1. 撤销原语
   1. 从PCB集合中找到PCB
   2. 若进程在运行，立刻剥夺CPU，分配给其他进程
   3. 终止其所有子进程
   4. 归还资源给父进程或os
   5. 删除PCB
2. 引起进程终止的时间
   1. 正常结束
   2. 异常结束
   3. 外界干预

• 进程的阻塞（运行态 -> 阻塞态

1. 阻塞原语（Block
   1. 找到要阻塞的进程对应的PCB
   2. 保护进程运行现场，PCB状态信息设置为阻塞态，暂时停止进程运行
   3. PCB插入相应事件的等待队列
2. 引起进程阻塞的事件
   1. 需要等待系统分配资源
   2. 等待其他相互合作的进程完成工作

• 进程的唤醒（阻塞态 -> 就绪态

1. 唤醒原语（Wakeup）
   1. 在事件等待队列中找到PCB
   2. PCB设置为就绪态，移除等待队列
   3. PCB插入就绪队列，等待被调度
2. 引起进程唤醒的事件
   1. 等待的事件发生：**进程因为什么事件被阻塞，就应该由什么事件唤醒

• 进程的切换（一个进程 运行态->就绪态；另一个进程 就绪态->运行态

1. 切换原语
   1. 运行环境存入PCB
   2. PCB移入相应队列
   3. 选择另一个进程执行，更新PCB
   4. 根据PCB恢复新进程运行环境
2. 引起进程切换的事件
   1. 当前进程时间片到
   2. 更高优先级的进程到达
   3. 当前进程主动阻塞
   4. 当前进程终止

2.1_4 进程通信

进程通信是指进程之间的信息交换

每个进程拥有各自的内存地址空间。为了保证安全，一个进程不能直接访问另一个进程的地址空间

共享存储

设置一个共享空间，两个进程对共享空间的访问是互斥的（互斥访问通过os提供的工具实现

• 基于数据结构的共享：例如共享空间内只放一个长度为10的数组，这种共享方式速度慢，限制多，是低级通信方式
• 基于存储区的共享：在内存中划出一块共享存储区，由进程控制（而不是os），这种方式速度快，是高级通信方式

管道通信

管道是指用于连接读写进程的一个共享文件（pine文件），实质是在内存中开辟一个固定大小的缓冲区

1. 管道只能半双工通信
2. 各个进程要互斥访问管道
3. 管道写满时，写进程的系统调用被阻塞；管道空时，读进程的系统调用被阻塞
4. 管道没写满，不允许读；管道没读空，不允许写
5. 数据一旦被读出，就离开管道，这意味着读进程最多只能有一个

消息传递

数据以格式化的消息为单位，进程通过os提供的原语进行数据交换

• 直接通信方式：发送进程直接把消息发送给接受进程，挂在接受进程消息缓冲队列上，接受进程从消息缓冲队列中取得消息
• 间接通信方式：发送进程将消息发送到某个中间实体（称为信箱），接受进程从信箱取得消息

2.1_5 线程的概念

引入线程可以增加并发度。

一个进程中可以包含多个线程

引入线程后带来的改变

1. 资源分配、调度
   1. 进程成为资源分配的基本单位，线程是调度的基本单位
2. 并发性
   1. 传统进程机制中只能进程间并发；引入线程后，各个线程之间也能并发，提高了并发度
3. 系统开销
   1. 传统进程间并发需要切换进程的运行环境，系统开销大
   2. 线程间并发，如果是同一个进程内的线程切换，就不需要奇幻进程环境，系统开销小
   3. 引入线程后，并发带来的系统开销减少

线程的属性

1. 线程是处理机调度的单位，线程可以并发执行；多CPU计算机中，各个线程可以占有不同CPU
2. 线程几乎没有系统资源，拥有一个唯一的标识符（线程ID）和一个线程控制块（TCB），TCB记录寄存器等信息
3. 不同用户调用同一个程序时会创建多个线程
4. 同一进程内各个线程共享该进程的系统资源，因此其中线程内通信甚至可以无需系统干预
5. 同一进程中的线程切换不会引起进程切换，系统开销小；反之反之
6. 线程同样拥有：就绪、运行、阻塞三种状态

2.1_6 线程的实现和多线程模型

线程的实现

分为用户级线程（User-Level Thread, ULT）和内核级线程（Kernel-Level Thread）

用户级线程 ULT

ULT中，有关线程管理的所有工作都由应用程序在用户空间中完成，内核意识不到线程的存在。

应用程序可以使用线程库设计成多线程程序

1. 用户级线程管理工作由应用程序通过线程库实现
2. 用户级线程切换不需要CPU从用户态转变为内核态
3. 操作系统无法意识到ULT存在
4. 优缺点
   1. 线程切换不需要切换CPU状态，开销减少
   2. 线程被阻塞时，同一进程内的所有线程都被阻塞
   3. 内核每次分配给一个进程一个CPU，进程内只有一个线程可以执行，不能发挥多处理机的优势

内核级线程 KLT

1. KLT管理工作由操作系统内核完成
2. KLT的切换需要在内核态才能完成
3. 操作系统为每个KLT建立相应的TCB，通过TCB对KLT进行管理，因此时可以看到的
4. 优缺点：
   1. 一个线程被阻塞，其他的还可以继续执行，并发能力强
   2. 可以在多核处理机上运行
   3. 线程管理成本高，开销大

多线程模型

某些系统同时支持ULT和KLT，由链接方式的不同可以分为

一对一模型

多对一模型

多对多模型

错题区：
1. 线程包含CPU线程，可以独立执行程序
2. 线程没有独立的地址空间（进程有
3. 单处理器系统中，并非任何时刻都只有一个进程处于运行态。例如：死锁时都阻塞，无任务时CPU空闲
4. 并发进程失去封闭性：并发进程共享变量（系统资源），执行结果与速度有关
5. 用户进程被建立后，随着进程运行的正常和不正常结束而撤销
6. 在引入线程的系统中，进程仍是资源分配的单位，但不再是调度的单位
7. 若就绪队列不为空，就绪的进程数目越多，处理器的效率不变
8. 降低进程优先级的合理时机：进程时间片用完
9. 进程中的线程共享进程的资源，但某个线程的栈指针对于其他线程而言是透明的
10. 一个进程的读磁盘操作（IO操作，此前为阻塞态）完成后，操作系统针对该进程必做的是：修改进程状态为就绪态

2.2_1 处理机调度的概念、层次

调度的基本概念

调度处理的是：指定某种规则来处理任务顺序，这些任务由于资源受限无法同时处理

调度有三个层次：高级调度、中级调度、低级调度

高级调度（作业调度

作业：一个具体的任务

高级调度：按照一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次（创建PCB），调出一次（撤销PCB

低级调度（进程/处理机 调度

按照某种策略，从就绪队列中选取一个进程，将处理机分配给它

进程调度是操作系统最基本的一种调度，进程调度的频率很高

中级调度（内存调度

挂起：当内存不足时，可将某些进程的数据调出外存，等内存空闲或进程需要运行时再重新调入内存。暂时调到外存等待的进程状态为挂起状态，PCB会被组织成挂起队列

Tips：挂起态又可以分为就绪挂起和阻塞挂起状态

中级调度：按照某种策略决定将哪个处于挂起状态的进程重新调入内存

一个进程可能会被多次调出、调入内存，因此中级调度的频率比高级调度更高

2.2_2 进程调度的时机、切换、过程与方式

进程调度的时机

调度程序是操作系统内核程序，请求调度的事件发生后才可能运行调度程序，调度新的就绪程序后才会引起进程切换

1. 需要进行进程调度与切换
   1. 当前运行的进程主动放弃处理机
      1. 进程正常终止
      2. 进程过程发生异常而终止
      3. 进程主动请求阻塞（例如等待IO
   2. 当前运行的进程被动放弃处理机
      1. 时间片用完
      2. 有更紧急的事件需要处理（例如IO中断
      3. 更高优先级的进程进入就绪队列
2. 不能进行进程调度与切换
   1. 处理中断时
   2. 进程位于操作系统内核程序临界区中
   3. 原子操作过程（原语）中

临界资源：一个时间段只允许一个进程使用的资源，各个进程需要互斥地访问临界资源
临界区：访问临界资源的代码
内核程序临界区：用于访问某种内核数据结构，例如进程的就绪队列

进程调度的方式

1. 非剥夺调度方式、又称非抢占方式。只允许进程主动放弃处理机
2. 剥夺调度方式，又称抢占方式。允许剥夺处理机

进程的切换与过程

狭义的进程调度：从就绪队列中选出一个要运行的进程

进程切换：一个进程让出处理机，另一个进程占用处理机

广义的进程调度：包括选择一个进程和进程切换两个步骤

进程切换需要付出时间代价，因此不是越频繁越好

闲逛进程：进程切换时如果没有就绪进程，就会调度闲逛进程运行。闲逛进程优先级最低，只要有就绪进程，就会立即让出处理机。闲逛进程不需要CPU之外的资源，不会被阻塞

上下文切换：切换CPU到另一个进程需要保存当前进程的状态并恢复另一个进程的状态，这个任务称为上下文切换。上下文切换一定发生在内核态

模式切换：用户态和内核态之间的切换。模式切换时可能没有发生进程切换

2.2_3 调度算法的评价指标

包括：CPU利用率、系统吞吐量、周转时间、等待时间和响应时间

CPU利用率

CPU忙碌的时间占总时间的比例

系统吞吐量

单位时间内完成的作业的数量

周转时间

作业从被提交给系统开始，到作业完成为止的时间间隔
平均周转时间：各作业周转时间之和 / 作业数
带权周转时间：作业周转时间 / 作业实际运行的时间
平均带权周转时间：各作业带权周转时间之和 / 作业数

等待时间

进程/作业 处于等待处理机状态时间之和

响应时间

用户从提交请求到首次得到响应所需的时间

2.2_4 调度算法

调度算法包括：

• 先来先服务（FCFS）、短作业优先（SJF）和高响应比优先（HRRN）（交互性差）
• 时间片轮转调度算法（RR）、优先级调度算法、多级反馈队列调度算法

饥饿：某个进程/作业长期得不到服务

先来先服务（FCFS, First Come First Serve

1. 按照作业/进程到达的心后顺序进行服务
2. 对于作业调度：考虑哪个作业先到达后备队列；对于进程调度，考虑哪个进程先到达就绪队列
3. 非抢占式
4. 对长作业有利，对短作业不利
5. 不会导致饥饿

短作业优先（SJF, Shortest Job First

1. 追求最少的平均等待时间、平均周转时间、平均带权周转时间
2. 服务时间最短的作业/进程优先得到服务
3. SJF和SPF是非抢占式的算法，但也有抢占式的版本——最短剩余时间优先算法：SRTN（未说明的话，默认非抢占式
4. 对短作业有利，对长作业不利；并不一定能做到真正的短作业优先
5. 未考虑作业的紧迫程度
6. 可能导致长作业饥饿，甚至饿死

高响应比优先（HRRN, Highest Response Ratio Next

1. 综合考虑作业/进程的等待时间和要求服务的时间
2. 在每次调度时计算作业/进程的响应比，选择最高的一个
   1. 响应比 = （等待时间 + 要求服务时间） / 要求服务时间
3. 非抢占式
4. 综合了SJF和FCFS的优点，避免了长作业饥饿的问题

时间片轮转（RR, Round-Robin

适用于分时操作系统

1. 按照各个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，如果未在一个时间片内执行完，则剥夺处理机，进程放到就绪队列队尾重新排队
2. 用于进程调度，只有作业放入内存建立相应进程后，才能被分配处理机时间片
3. 是抢占式的算法，由时钟装置发出时钟中断来通知CPU时间片到
4. 如果时间片太大，则RR退化为FCFS算法；如果时间片太小，会导致进程切换太频繁，导致较大开销
5. 不区分任务的紧急程度
6. 不会导致饥饿

优先级调度算法

1. 每个作业/进程有各自优先级，调度时选择优先级最高的作业/进程
2. 可用于作业调度、进程调度（甚至可以用于IO调度
3. 抢占式、非抢占式都有
4. 可以灵活的调整优先级，适用于实时操作系统
5. 如果源源不断地有高优先级进程到来，可能发生饥饿

• 静态优先级：创建进程时确定，之后一直不变
• 动态优先级：创建进程时有初始值，之后根据情况动态地调整

通常

1. 系统进程优先级高于用户进程
2. 前台进程优先级高于后台进程
3. 操作系统更偏好I/O型进程（又称I/O繁忙型进程）（与I/O型进程相对的是计算型进程，又称CPU繁忙型进程）
   1. 原因：IO设备和CPU可以并行工作，偏好IO型进程可以尽早让IO设备投入工作，提高资源利用率、系统吞吐量
4. 如果进程在就绪队列中等待了很长时间，可以适当提升其优先级；如果进程占用处理机运行了很长时间，可以适当降低优先级

多级反馈队列调度算法

1. 用于进程调度
2. 抢占式的算法，也有非抢占式
3. 会导致饥饿

错题区：
1. 作业以用户任务为单位，进程以操作系统控制为单位
2. 分时系统时间片固定，因此用户数越多，响应时间越长
3. UNIX系统属于分时操作系统
4. 中断发生时，由硬件保护并更新PC而不是软件完成，主要是为了提高处理速度
5. 中断向量本身是用于存放中断服务例行程序的入口地址，因此中断向量地址就是存放该入口地址的地址

2.3_1 进程同步、进程互斥

进程同步：同步也称作直接制约关系，是指为了完成某种任务而建立的两个或多个进程，因为在需要某些位置上协调他们的工作次序而产生的制约关系
进程互斥：当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。
互斥：也称间接制约关系。当一个进程进入临界区时，另一个想进入的进程必须等待，直到占用临界资源的进程退出，才可以去访问
临界资源：一个时间段内只允许一个进程使用的资源。例如打印机等物理设备、一些共享的变量、数据等

---

对临界资源的互斥访问，在逻辑上可以分为四个部分

1. 进入区：检查是否可以进入临界区，若可进入，则设置“正在访问临界资源”的标志，（相当于上锁）阻止其他进程同时进入临界区
2. 临界区：访问临界资源的代码段，又称临界段
3. 退出区：解除“正在访问临界资源”的标志（相当于解锁）
4. 剩余区：做其他处理

临界区是进程中访问临界资源的代码段，进入区和退出区是负责实现互斥的代码段

---

为了实现对临界资源的互斥访问，同时保证整体性能，需要遵循以下原则

1. 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2. 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
3. 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿
4. 让权等待：进程不能进入临界区时，应立即释放处理机，防止进程忙等待

2.3_2 进程互斥的软件实现方法

单标志法

每个进程进入临界区的权限只能被另一个进程赋予

设置一个变量turn，表示允许访问临界区的进程

// P0进程
while(turn != 0){...};  // 进入区，turn不为0时被困在循环内
critical section;       // 临界区
turn = 1;               // 退出区
remainder section;      // 剩余区
// P1进程
while(turn != 1){...};  // 进入区
critical section;       // 临界区
turn = 0;               // 退出区
remainder section;      // 剩余区

该算法可以实现同一时刻只有一个进程访问临界资源

问题：如果当前进程P允许访问临界区，但他就是不访问，就会使得临界区空闲，但并不允许其他进程访问。这违反了“空闲让进”的原则

双标志先检查法

设置一个数组flag，标记各个进程是否想要进入临界区。每个进程在进入临界区之前，先检查当前是否有其他进程想进入临界区，如果没有，则自身标志设置为true然后开始访问

// P0进程
while(flag[1]){...}
flag[0] = true;
critical section;
flag[0] = false;
remainder section;

// P1进程
while(flag[0]){...}
flag[1] = true;
critical section;
flag[1] = false;
remainder section;

存在的问题：如果进程P1确定将访问临界区，但还没置flag，此时进程切换P2，P2也将可以访问临界区。违反了“忙则等待”的原则

改进——双标志后检查法

先上锁，再检查

// P0进程
flag[0] = true;
while(flag[1]){...}
critical section;
flag[0] = false;
remainder section;

// P1进程
flag[1] = true;
while(flag[0]){...}
critical section;
flag[1] = false;
remainder section;

虽然解决了“忙则等待”的问题，但又违反了“空闲让进”和“有限等待”的原则，可能会出现饥饿现象

Peterson算法

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

// P0 进程
// 进入区
flag[0] = true;
turn = 1;
while(turn == 1 && flag[1]){...}
// 临界区
// 退出区
flag[0] = false;
// 剩余区

// P1 进程
// 进入区
flag[1] = true;
turn = 0;
while(turn == 0 && flag[0]){...}
// 临界区
// 退出区
flag[1] = false;
// 剩余区

问题：没有遵循”让权等待“的原则

2.3_3 进程互斥的硬件实现方法

计算机提供特殊的硬件指令，允许对一个字中的内容进行修正等。通过硬件支持实现临界段问题的方法称为低级方法，或称元方法

中断屏蔽方法

思想：利用“开/关中断指令”实现，不允许中断也就意味着不能发生进程切换，也就不可能发生同时访问临界区的情况

• 优点：简单高效
• 缺点：不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程

TestAndSet指令

简称TS指令，又称TSL指令（TestAndSetLock）

TS指令用硬件实现，执行的过程不允许被中断

// lock表示临界区是否被锁
// 检查并上锁
bool TestAndSet(bool *lock){
    bool old = *lock;
    *lock = true;
    return old;
}
// TSL实现互斥
while(TestAndSet(&lock)){...};
// 临界区
lock = false;
剩余区

Swap指令

又称Exchange指令、XCHG指令。用硬件实现，不允许被中断

Swap(bool* a, bool* b){
    bool temp = *a;
    *a = *b;
    *b = temp;
}
// 实现互斥
// lock表示临界区是否上锁
bool old = true;
while(old)  swap(&lock, &old);
// 临界区
lock = false;
// 剩余区

互斥锁（mutex lock

一个进程在进入临界区时获得锁（acquire，在退出临界区时释放锁（release

每个互斥锁有一个bool变量，表明锁是否可用，进程试图获取不可用的锁时会被阻塞，直到锁被释放

acquire(){
    while(!available){...}
    available = false;
}
release(){
    available = true;
}

互斥锁的缺点是没有遵循忙等待，浪费CPU周期

2.3_4 信号量机制

信号量：一个变量，表示系统中某种资源的数量

用户可以通过操作系统提供的一对原语（wait和signal）来对信号量进行操作，从而方便地实现进程互斥和进程同步

wait原语和signal原语简称为P、V操作。（P(S)、V(S)

对信号量的操作只有三种：初始化、P操作（请求资源）、V操作（释放资源）

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

例如某计算机系统中有一台打印机

int S = 1;  // 初始化整型信号量S，表示当前系统中可用的打印机资源数

void wait(int S){   // wait 相当于进入区
    while(S <= 0){...}
    S = S-1;
}

void signal(int S){ // signal 相当于退出区
    S = S+1;
}

// P0进程
wait(S);
// 临界区
signal(S);

整型信号量存在的问题：不满足“让权等待”的原则，会发生忙等

记录型信号量

// 记录型信号量的定义
typedef struct{
    int value;  // 剩余资源数
    struct process *L;  // 等待队列
}semaphore;

// wait
void wait(semaphor S){
    -- S.value;
    if(S.value < 0){
        该进程加入等待队列;
        block(S.L); // 如果资源数不够，使用block原语使进程从运行态进入阻塞态，并挂到信号量S的等待队列（即阻塞队列）中
    }
}

// signal
void signal(semaphore S){
    ++ S.value;
    if(S.value <= 0){
        该进程移出等待队列;
        wakeup(S.L);    // 释放资源后如果还有别的进程在等待资源，则使用wakeup原语，从等待队列中唤醒一个进程，从阻塞态变为就绪态
    }
}

优点：遵循了“让权等待”的原则，不会出现”忙等“现象

tips：默认S为记录型信号量

2.3_5 用信号量机制实现进程互斥、同步、前驱关系

实现进程互斥

1. 划定临界区
2. 设置互斥信号量mutex，初始值为1
3. 在进入区 P(mutex)
4. 在退出区 V(mutex)
5. 注意
   1. 对不同的临界资源需要设置不同的互斥信号量
   2. PV操作必须成对出现。缺少P就不能保证临界资源的互斥访问；缺少V会导致资源永不被释放，等待进程永不被唤醒

// 记录型信号量
typedef struct{
    int value;
    struct process *L;
}semaphore;
// 进程P1
P1(){
    ...
    P(mutex);
    ... // 临界区
    V(mutex);
    ...
}
// 进程P2
P2(){
    ...
    P(mutex);
    ... // 临界区
    V(mutex);
    ...
}

实现进程同步

进程同步：目的是让各个并发进程有序推进

1. 分析需要实现“同步关系”的位置
2. 设置同步信号量S，初始值为0
3. 前V后P：在前边的操作后执行V操作；在后边的操作前面执行P操作

例如P2进程的代码4需要在P1进程的代码2之后执行

semaphore S = 0;    // 同步信号量

P1(){
    code1;
    code2;
    V(S)
    code3;
}

P2(){
    P(S);
    code4;
    code5;
    code6;
}

实现前驱关系

每一对前驱关系都是一个进程同步问题（需要保证一前一后的关系，设置多个信号量

2.3_6 生产者——消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区取出一个产品使用（产品理解为一种数据
生产者和消费者共享一个初始为空，大小为n的缓冲区
只有缓冲区没有满，生产者才能把产品放入缓冲区，否则必须等待
缓冲区不空时，消费者才能从中取出产品，否则必须等待
缓冲区是临界资源，进程必须互斥访问

semaphore mutex = 1;    // 互斥信号量
semaphore empty = n;    // 同步信号量，表示空闲缓冲区的数量
semaphore full = 0;     // 同步信号量，表示产品的数量

producer(){
    while(1){
        生产一个产品;
        P(empty);
        P(mutex);
        产品放入缓冲区;
        V(mutex);
        V(full);
    }
}

consumer(){
    while(1){
        P(full);
        P(mutex);
        从缓冲区使用取出一个产品;
        V(mutex);
        V(empty);
        使用产品;
    }
}

• 实现互斥的P操作一定要在实现同步的P操作之后，否则会发生死锁（两个进程互相等待被对方唤醒
• V操作不会导致进程堵塞，因此可以交换顺序

2.3_7 多生产者——多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸只放苹果，妈妈只放橘子；儿子只吃橘子，女儿只吃苹果。
盘子空时，爸妈才能向盘子中放水果；盘子中有自己想吃的水果时，儿女才能从盘子中取出水果

1. 互斥关系：对缓冲区（盘子）的访问必须互斥进行
2. 同步关系：父亲将苹果放入盘子后，女儿才能取出苹果
3. 同步关系：母亲将橘子放入盘子后，儿子才能取出橘子
4. 同步关系：盘子为空时，父亲或母亲才能放入水果

semaphore mutex = 1;    // 互斥
semaphore apple = 0;    // 苹果
semaphore orange = 0;   // 橘子
semaphore plate = 1;    // 盘子

dad(){
    while(1){
        准备一个苹果;
        P(plate);
        P(mutex);
        苹果放入盘子;
        V(mutex);
        V(apple);
    }
}

mom(){
    while(1){
        准备一个橘子;
        P(plate);
        P(mutex);
        橘子放入盘子;
        V(mutex);
        V(orange);
    }
}

daughter(){
    while(1){
        P(apple);
        P(mutex);
        从盘中取出苹果;
        V(mutex);
        V(plate);
        吃掉苹果;
    }
}

son(){
    while(1){
        P(orange);
        P(mutex);
        从盘中取出橘子;
        V(mutex);
        V(plate);
        吃掉橘子;
    }
}

• 这里，即使不设置专门的互斥信号量mutex，也不会出现多个进程同时访问盘子的现象，因为本题的缓冲区大小为1，任意时刻三个同步信号量中最多只有一个是1，只有一个进程的P操作不会被阻塞
• 实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起死锁

2.3_8 吸烟者问题

一个系统有三个抽烟者进程和一个供应者进程
每个抽烟者需要用三种材料卷烟并抽掉。第一个拥有烟草，第二个拥有纸，第三个拥有胶水
供应者无限地供应三种材料，每次将两种材料放在桌子上，拥有第三种材料的抽烟者就会使用它们卷烟并抽掉，然后给供应者一个信号告诉完成了，供应者就会放另外两种材料，这个过程一直重复（让三个抽烟者轮流抽烟

1. 这道题本质上也是消费者——生产者问题
2. 互斥关系：桌子抽象为缓冲区，容量为1（所以可以不设置互斥量
3. 同步关系：三种组合才能发生对应的抽烟
4. 同步关系：抽烟者发出完成信号->供应者将下一个组合放到桌子上

semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore finish = 0;
int i = 0;  // 用于实现三个抽烟者轮流抽烟

provider(){
    while(1){
        if(i == 0){
            组合1放在桌子上;
            V(offer1);
        }else if(i == 1){
            组合2放在桌子上;
            V(offer2);
        }else{
            组合3放在桌子上
            V(offer3);
        }
        i = (i+1)%3;
        P(finish);
    }
}

smoker1(){
    while(1){
        P(offer1);
        拿走组合1，卷烟抽掉;
        V(finish);
    }
}

smoker2(){
    while(1){
        P(offer2);
        拿走组合2，卷烟抽掉;
        V(finish);
    }
}

smoker3(){
    while(1){
        P(offer3);
        拿走组合3，卷烟抽掉;
        V(finish);
    }
}

2.3_9 读者——写者问题

有读者和写者两组并发进程，共享一个文件，要求如下：

1. 允许多个读者同时对文件执行读操作
2. 只允许一个写者往文件中写信息
3. 任意写者在完成写操作之前不允许其他读者或写者工作
4. 写者执行写操作前，必须让已有的读者和写者全部退出

1. 互斥关系：写进程之间互斥，读进程之间没有互斥关系

semaphore rw = 1;   // 实现读写互斥
int count = 0;      // 记录当前有几个读进程在访问文件
semaphore mutex = 1;// 保证对count变量的互斥访问    
// semaphore w = 1; // 实现写优先

writer(){
    while(1){
        // P(w);
        P(rw);
        写文件;
        V(rw);
        // V(w);
    }
}

reader(){
    // P(w);
    P(mutex);
    if(count == 0)  // 第一个读进程来上锁
        P(rw);
    ++ count;
    V(mutex);
    // V(w);
    读文件;
    P(mutex);
    -- count;
    if(count == 0)  // 最后一个读进程来解锁
        V(rw);
    V(mutex);
}

1. 潜在问题：可能导致写进程饿死
2. 解决方法：增加一个w信号量，实现写优先
3. 精髓在于计数器count

2.3_10 哲学家进餐问题

一张圆桌上有五名哲学家，每两个哲学家之间的桌子上摆一根筷子，桌子中间是食物
哲学家思考时，不影响其他人。哲学家饥饿时，会试图拿起左右两根筷子（一根一根拿起），如果筷子在其他人手上，则需要等待。饥饿的哲学家只有同时拿着两根筷子才可以开始进餐。进餐完毕后，放下筷子继续思考

1. 五位哲学家与左右邻居对其间筷子的访问是互斥关系
2. 设置信号量数组，编号0-4，左边的筷子是i，右边的筷子是(i+1)%5
3. 如何预防死锁？
   1. 添加一些限制，比如最多只允许四个哲学家同时进餐，可以保证至少有一个哲学家可以拿到左右两只筷子
   2. 要求奇数编号哲学家先拿左边筷子，偶数哲学家则相反
   3. 仅当一个哲学家左右两边都有筷子，才允许吃饭

2.3_11 管程

为什么引入管程

1. 信号量机制存在问题：编写程序困难，容易出错
2. 需要设计一种机制，让程序员写程序无需关注复杂的PV操作

管程的定义和基本特征

管程是一种特殊的软件模块（有点像类），由以下部分组成

1. 局部于管程的共享数据结构说明
2. 对该数据结构进行操作的一组过程（函数
3. 对局部于管程的共享数据设置初始值的语句
4. 管程有一个名字

管程的基本特征：

1. 局部于管程的数据只可以被局部于管程的过程访问
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3. 每次只允许一个进程在管程内执行某个内部过程（互斥
4. 管程有很多“入口”，但每次只能开放其中一个入口，并且只有一个进程或线程可以进入。这种互斥特性是由编译器负责实现的
5. 可以在管程中设置条件变量及等待/唤醒操作来解决同步问题

错题区：
1. 操作系统中，要对并发进程进行同步的原因是：并发进程是异步的
2. PV操作是一种：低级进程通信原语，是由两个不可被中断的过程组成的
3. 一个进程映像由程序、数据以及PCB组成，其中，共享程序段必须以可重入编码编写
4. 一个系统中共有五个并发进程涉及同一个变量A，变量A的相关临界区是由（5）个临界区构成的
5. 管程的signal操作针对某个条件变量，与信号量机制中的V操作不同，V操作一定使信号量S++

2.4_1 死锁的概念

在并发环境下，各进程竞争资源导致的一种互相等待对方手中的资源，导致各个进程都被阻塞，都无法向前推进的现象
如果没有外力推动，进程将无法向前推进

死锁产生的条件

1. 互斥条件：对互斥资源进行争抢才会导致死锁
2. 不剥夺条件：进程获得的资源在没使用完之前不能被强行夺走，只能主动释放
3. 请求和保持条件：进程获得了至少一个资源，但提出新的资源请求，而该资源又被其他进程占有，此时进程被阻塞，但又对自己已有的资源不放
4. 循环等待条件：存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被下一个进程请求

发生死锁的情况

1. 对系统资源的竞争
2. 进程推进顺序非法
3. 信号量使用不当，例如实现互斥的P操作在实现同步的P操作之前

死锁的处理策略

1. 预防死锁，破坏四个产生条件的一个或几个
2. 避免死锁，用某种方法防止系统进入不安全状态（银行家算法
3. 死锁的检测和解除，允许死锁发生，但操作系统负责监测处死锁的发生，然后解除死锁

2.4_2 预防死锁

破坏导致死锁的必要条件

1. 破坏互斥条件
   1. 将资源改造为允许共享使用。例如SPOOLing技术
   2. 缺点：很多时候系统必须保护资源的互斥性
2. 破坏不剥夺条件
   1. 当某个进程请求新资源无法满足时，必须释放保持的所有资源，需要时再重新申请
   2. 可以由操作系统协助，强行剥夺。这种方式一般需要考虑进程优先级
   3. 缺点：实现起来复杂；释放资源可能造成前一阶段工作失效；反复申请释放资源会增加系统开销；可能导致饥饿
3. 破坏请求和保持条件
   1. 进程在运行前一次性申请完他所需要的所有资源。在资源未满足不会投入运行
   2. 缺点：资源利用率低；可能导致饥饿
4. 破坏循环等待条件
   1. 采用顺序资源分配法。给系统中的资源编号，规定每个进程必须按照编号递增的顺序请求资源
   2. 缺点：不方便增加新设备；进程使用资源的顺序可能不是递增，导致资源浪费；用户编程麻烦

2.3_3 避免死锁

避免死锁属于事先预防策略

安全序列：如果系统按照这种序列分配资源，可以满足每个进程对资源的最大需求，则每个进程都可以顺利完成
只要找出一个安全序列，系统就是安全状态。安全序列可能会有多个
系统处于安全状态时，一定不会发生死锁；进入不安全状态，有可能发生死锁；发生了死锁一定在不安全状态

银行家算法核心思想：在进程提出资源申请时，先预判这次分配是否会导致系统进入不安全状态，如果会，则暂时阻塞该进程

2.4_4 死锁的检测和解除

死锁的检测（死锁定理

1. 用某种数据结构保存资源的请求和分配信息
   1. 进程节点、资源节点：圆圈表示进程，矩形框表示资源
   2. 请求边、分配边
2. 提供算法检测是否进入死锁

解除死锁

1. 资源剥夺法：挂起某些死锁进程，抢占资源
2. 撤销进程法：强制撤销部分死锁进程
3. 进程回退法：需要系统记录进程进程的历史信息，设置还原点

1. 若系统中有n个进程，每个进程需要使用某种临界资源m个，则不会发生死锁的该类资源的总数至少为：m+(n-1)(m-1)
2. 区分死锁预防和死锁避免
3. 产生死锁的根本原因在于系统资源分配不足和进程推进顺序非法

赏

谢谢你请我吃糖果

支付宝

微信