计算机操作系统(二)进程

2进程与同步

2.1进程

2.1.1/2进程的概念、组成、特征

进程的概念

程序：静态的，磁盘中的文件
进程：动态的，内存中的映像

进程创建时，OS分配唯一、不重复的PID(进程ID)
进程信息都保存在数据结构的PCB(进程控制块)中

PCB：进程存在的唯一标志，进程结束时会回收

**进程实体(进程映像)**：程序段、数据段、PCB三部分组成

进程是进程实体的运行过程，是OS进行资源分配和调度的一个独立单位

进程的特征

• 动态性(最基本特征)：动态产生消亡
• 并发性：内存中多个实体可并发执行
• 独立性：可独立运行、获得资源、调度的基本单位
• 异步性：各个进程独自推进
• 结构性：每个进程都有个PCB，结构上：程序段、数据段、PCB

2.1.3进程的状态与转换

进程的状态：创建态、就绪态

创建态：OS分配资源、初始化PCB
就绪态：具备运行条件，但没有空闲CPU
运行态：被调度执行
阻塞态：系统调用，等待资源、事件等阻塞
终止态：正在销毁，回收资源

不能阻塞->运行
也不能就绪->阻塞

PCB中有变量state表示进程状态

2.1.4进程控制

实现进程的状态转换

如何实现进程控制

使用原语实现
执行具有原子性，必须一次完成不能中断

可以用关中断指令 和 开中断指令，两个特权指令实现原子性

关中断后，就不会例行检查中断信号了，直到开中断
内核程序，运行在核心态

进程控制相关原语

进程创建

• 创建原语：创建态->就绪态
  • 申请空白PCB
  • 为进程分配所需资源
  • 初始化PCB
  • 将PCB插入就绪队列
• 引起进程创建的事件
  • 用户登录
  • 作业调度
  • 提供服务
  • 应用请求

进程终止

• 撤消原语
  • 从PCB集合中找到终止进程的PCB
  • 若程序正在运行，夺取CPU，分配给其他进程
  • 终止所有子进程
  • 将该进程拥有的资源归还父进程/操作系统
  • 删除PCB

进程的阻塞和唤醒

• 进程阻塞
  • 阻塞原语
    • 找到阻塞进程对应的PCB
    • 保护进程运行现场，PCB状态切换为阻塞态，暂停程序运行
    • PCB插入相应事件的等待队列
• 进程唤醒
  • 唤醒原语
    • 等待事件队列中找到PCB
    • 将PCB从等待队列中移除，设置进程为就绪态
    • 将PCB插入就绪队列，等待被调度

进程切换

• 切换原语
  • 将运行环境信息存入PCB
  • PCB移入相应队列
  • 选择另一个进程执行，并更新PCB
  • 根据PCB恢复进程运行所需环境

进程控制原语做的事情无非三类：

• 更新PCB信息
• 将PCB插入合适的队列
• 分配/回收资源

2.1.5进程通信

进程间通信IPC：两个进程之间产生数据交互

进程是分配系统资源的单位，各个进程拥有的内存地址空间相互独立

为保证安全，不同进程不能访问同一地址空间

共享存储

基于存储区的共享
OS在内存中划分一块共享存储区
数据形式，存放位置自由，灵活速度快，高级通信方式
基于数据结构的共享
数据结构固定
速度慢，限制多，低级通信方式

各个进程队共享空间的访问应该是互斥的

消息传递

数据交换以格式化的消息为单位
OS提供收发消息的原语以进行数据交换

• 直接通信方式
  • 指明接收进程的ID
• 间接通信方式
  • 通过信箱间接通信

管道通信

管道：特殊的共享文件pipe
在内存中开辟的大小固定的缓冲区

管道，半双工通信
如果要双向同时通信，需要两个管道
各进程互斥的昂文管道
管道写满时，写进程将阻塞
管道读空时，读进程将阻塞

管道中的数据一旦读出，就彻底消失
多进程从管道读数据，防止错乱的解决方案

• 一个管道允许多个写进程，一个读进程
• 多个写进程，多个读进程，OS让读进程轮流读取(Linux)

2.1.5(2)信号

用于通知进程某个特定事件已经发生
进程收到一个信号后，对该信号进行处理

信号的发送与保存

PCB中

• 待处理信号向量(类似bitset) pending
• 被阻塞信号向量blocked(信号掩码)

用户进程间可以发送信号(但有限制)
内核进程可以给用户进程发送信号

信号的处理

何时处理：
当进程从内核态转为用户态时，例行检查是否有待处理信号
若有，则处理信号

如何处理：
信号有默认的信号处理程序

• 也可以设置自定义的信号处理程序
• 有些信号不能自定义处理函数，也不能被阻塞
  信号处理程序运行结束后，返回
  处理完信号后，将pending位重置为0
  若重复收到同类信号，则将被简单丢弃
  通常先处理最小的信号

信号与异常的关系

信号可作为异常的配套机制，让进程对操作系统的异常处理进行补充

有些异常无法由内核完成全部处理，可能还需要用户进程配合

2.1.6线程

2.1.6.1线程概念与特点

传统的进程是程序执行流的最小单位

线程是一个基本的CPU执行单元，是程序执行流的最小单位

引入线程后，各个线程间也可以并发，进一步提高了系统并发度
进程只作为除CPU外的系统资源的分配单元

线程：轻量级进程，切换线程开销更小

线程的属性

• 处理调度的单位
• 各个线程可占用不同的CPU
• 每个线程都有线程ID，线程控制块TCB
• 有就绪、阻塞、运行三种基本状态
• 几乎不拥有系统资源
• 同一进程的不同线程共享进程的资源
• 共享内存地址空间，同进程内线程通信无需系统干预
• 同进程内线程切换不会引起进程切换
• 不同进程中线程切换，会引起进程切换
• 切换同进程内线程，系统开销很小
• 切换进程，系统开销很大

2.1.6.2线程的实现方式与多线程模型

线程的实现方式

用户级线程ULT
OS只支持进程，线程由线程库实现

• 所有线程管理工作都由应用程序负责
• 线程切换可在用户态下即可完成
• 优点：用户级线程切换在用户空间即可完成，开销小，效率高
• 缺点：一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，线程不能在多核处理机上并发运行

内核级线程KLT

• 线程切换由内核完成
• 切换必须在核心态完成
• 优点：一个线程阻塞，其他线程可以继续执行，并发能力强
• 缺点：一个用户进程占用多个内核级线程，线程管理成本高，开销大

多线程模型

一对一模型：一个用户级线程映射一个内核级线程

• 优点：并发能力强
• 缺点：管理成本高，开销大

多对一模型：多用户，一内核

• 优点：开销小
• 缺点：并发能力低

内核级线程才是处理机分配的单位

多对多模型：多用户，多内核

2.1.6.3线程的状态与转换

• 就绪
• 运行
• 阻塞

组织与控制

TCB线程控制块

• 线程标识符TID
• 程序计数器PC
• 其他寄存器
• 堆栈指针
• 线程运行状态
• 优先级

线程表：

• 多个TCB

2.2调度

2.2.1调度的概念，层次

调度的基本概念

多个任务，有限的资源，用某种规则来决定处理这些任务的顺序

高级调度(作业调度)
按照一定原则从外存选取作业
每个作业只调入一次，调出一次

低级调度(进程调度/处理机调度)
按某种策略从就绪队列中选取一个进程，分配处理机
最基本的调度，频率很高

中级调度(内存调度)
内存不足时，可将某些数据调出内存，等内存空闲后再重新调入
按某种策略将挂起的进程重新调入内存
暂存到外存等待的进程：挂起状态
进程PCB组织称挂起队列
频率比高级更频繁

七状态模型
创建态
就绪态
运行态
阻塞态
终止态
就绪挂起
阻塞挂起

2.2.2.1进程调度时机、切换与过程、方式

需要进程调度：

• 主动放弃
• 被调放弃
  不能进程调度：
• 处理中断的过程中
• 操作系统内核程序的临界区中
• 原子操作过程中

进程调度的方式

非剥夺调度方式：非抢占式
实现简单，开销小，不及时

剥夺调度方式：抢占方式
可优先处理更紧急的进程，也可以时间片轮换

进程的切换与过程

进程切换主要过程：

• 对原来运行进程各种数据的保存
• 对新进程的各种数据的恢复

进程切换有代价：过于频繁会导致整个系统效率降低

2.2.2.2调度器和闲逛进程

调度时机

• 创建新进程
• 进程退出
• 运行进程阻塞
• I/O中断发生
  非抢占式调度策略：运行进程阻塞/退出才调度
  抢占式调度策略：每个时钟中断或k个时钟中断会触发调度

闲逛进程：若没有其他就绪程序运行，运行闲逛进程idle
特性：

• 优先级最低
• 可以是0地址指令，占一个完整的指令周期(末尾执行中断检查)
• 能耗低

2.2.3调度算法的评价指标

CPU利用率

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

利用率=忙碌时间/总时间

系统吞吐量

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

系统吞吐量=总共完成了多少道作业/总共花了多少时间

几道作业/秒

周转时间

作业被提交给系统开始，到作业完成为止的时间间隔

(作业)周转时间=作业完成时间-作业提交时间

平均周转时间=各作业周转时间之和/作业数

周转时间相同的情况下，运行时间长短不同，感受也不同

带权周转时间=作业周转时间/作业实际运行的时间
=(作业完成时间-作业提交时间)/作业实际运行时间

带权周转时间更小，用户满意度更高

带权周转时间必然>=1
带权周转时间和周转时间都是越小越好

平均带权周转时间=各作业带权周转时间之和/作业数

等待事件

作业处于等待处理机状态时间之和
等待时间越长，用户满意度越低

平均等待时间，等待时间的平均值

相应时间

用户提交请求到首次产生相应所用的时间

2.2.4调度算法

• 算法思想
• 算法规则
• 用于作业调度还是进程调度(有没有交互)
• 抢占式/非抢占式
• 优缺点
• 是否会饥饿

先来先服务FCFS

• 算法思想
  • 公平
• 算法规则
  • 按照作业/进程到达的先后顺序进行服务
• 用于作业/进程调度
  • 用于作业调度时：考虑是哪个作业先到达后备队列
  • 用于进程调度时：考虑是哪个进程先到达就绪队列
• 是否可抢占
  • 非抢占式算法
• 优缺点
  • 优点
    • 公平、算法实现简单
  • 缺点：
    • 在长作业后的短作业等待时间很长，带权周转时间很大
  • 对长作业有利，对短作业不利
• 是否会导致饥饿
  • 不会

短作业优先SJF

• 算法思想：
  • 追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
• 算法规则：
  • 最短的作业/进程先得到服务(要求被服务的时间)
• 用于作业/进程调度
  • 都可以，用于进程调度时称为短进程优先算法SPF
• 是否可抢占
  • 非抢占式
  • 也有抢占式版本：最短剩余时间优先算法SRTN
• 优缺点
  • 优点：”最短”平均等待时间、平均周转时间
  • 缺点：不公平，对短作业有利，对长作业不利，可能会产生饥饿
• 是否会导致饥饿
  • 会

非抢占式SJF
每次调度时，选择当前已到达且运行时间最短的作业/进程

抢占式SRTN：最短剩余时间优先算法
每当有进程加入就绪队列改变时就调度
新到达的进程剩余时间比当前运行的进程剩余时间更短，则新进程抢占处理机
当一个进程完成时也需要调度

若未说明，则默认非抢占

在所有进程同时可运行时
SJF调度算法的平均等待时间、平均周转时间最少
否则，抢占式短进程优先调度算法(如SRNT)的平均等待时间、平均周转时间最少

高响应比优先算法HRRN

• 算法思想：
  • 综合考虑作业/进程的等待事件和要求服务的时间
• 算法规则
  • 每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程服务
  • 相应比=(等待时间+要求服务时间)/要求服务时间
  • 响应比>=1
• 用于作业/进程调度：都可以
• 优缺点：
  • 综合考虑了等待时间和运行时间
  • 等待时间相同，要求服务时间短的优先(SJF优点)
  • 要求服务时间相同时，等待时间长的优先(FCFS优点)
  • 对于长作业，等待时间越久，响应比越大，避免了长作业饥饿问题
• 是否饥饿
  • 否
    高响应比优先算法：非抢占式

时间片轮转RR

• 算法思想：
  • 公平、轮流的为各个进程服务
• 算法规则：
  • 按照就绪队列顺序，轮流让各个进程执行一个时间片
  • 若一个时间片内未执行完，则抢占，将进程重新放到就绪队列尾部重新排队
• 用于作业/进程调度
  • 用于进程调度
  • (只有作业放入内存建立进程后，才能被分配处理器时间片)
• 是否可抢占：是
  • 由时钟装置发出时钟中断来通知CPU时间片到达
• 优缺点
  • 优点：公平，响应快，适用分时操作系统
  • 缺点：高频率进程切换会有一定开销，不区分任务紧急程度
• 是否饥饿
  • 不
    常用于时分操作系统，更注重响应时间
    一般不计算周转时间

若时间片太大，使得每个进程都可以在一个时间片内就完成
则时间片轮转调度算法退化为先来先服务调度算法
并且会增大进程响应时间，因此时间片不能太大

若时间片太小，会导致进程切换过于频繁
导致实际进程执行的时间比例减少，因此时间片也不能太小

优先级调度算法

• 算法思想
  • 需要根据任务的紧急程度来决定处理顺序
• 算法规则
  • 每个作业/进程有各自的优先级
  • 调度时选择优先级最高的作业/进程
• 用于作业/进程调度：都可以
• 是否可抢占
  • 都有，非抢占只需要主动挂起处理机时调度
  • 抢占式需要在队列变化时检查是否发生抢占
• 优缺点
  • 优点：用优先级区分紧急程度、重要程度，适合实时操作系统
    • 可灵活调整对于作业/进程的偏好程度
  • 缺点：若有源源不断的高优先级进程到来，可能导致饥饿
• 是否会导致饥饿
  • 会

就绪队列未必只有一个
可以按照不同优先级来组织
也可以吧优先级高的进程放在靠近队头的位置

根据优先级是否可以动态改变
可分为：静态优先级、动态优先级

系统进程>用户进程
前台进程>后台进程
操作系统更偏向于I/O密集型进程
会让IO设备尽早投入工作，资源利用率、系统吞吐量都会得到提升

多级反馈队列调度算法

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

新进程到达先进入1级队列
按FCFS原则排队等待分配时间片
若用完时间片进程还未结束
则进入下一级队列尾部
若已经在最下级队列
则重新放回最下级队列尾部

只有第k级队列为空时，才会为k+1级队头进程分配时间片

被抢占处理机的进程重新放回原队列尾部

• 算法思想：其他调度算法的折中权衡
• 用于进程调度
• 抢占式算法
• 优缺点：
  • 优点：公平(FCFS)、相应快(RR)、短进程使用时间少(SPF)、不必实现估计进程运行实际(避免用户作假)、可灵活调整偏好
• 会导致饥饿

2.2.5多处理机调度

考虑让哪个就绪进程优先上处理机
考虑上哪个处理机运行

追求目标：

• 负载均衡：尽可能让每个CPU都同等忙碌
• 处理机亲和性：尽量让一个进程调度到同一个CPU上进行，以发挥CPU中的缓存作用(cache)

方案一：公共就绪队列

• 所有CPU共享同一个就绪进程队列
• 每个CPU运行调度程序，从公共就绪队列中选择一个进程运行
• 每个CPU访问队列时，要上锁

优点：可以天然的实现负载均衡
缺点：各个进程频繁切换CPU运行，亲和性不好

如何提升处理机亲和性

• 软亲和：由进程调度程序尽量保证亲和性
• 硬亲和：由用户进程通过系统调用，主动要求OS分配固定的CPU，确定亲和性

方案二：私有就绪队列

• 每个CPU都有一个私有就绪队列
• CPU空闲时运行调度程序，从私有就绪队列中选择一个进程运行

如何实现负载均衡：
推迁移策略：
特定的系统程序周期性检查每个处理器负载
如果负载不平均，则忙pop 闲push
拉迁移策略
每个CPU运行调度程序时，周期性检查自身负载与其他CPU负载
当前CPU闲，则忙pop 当前闲CPUpush

如何提升处理机亲和性

• 私有就绪队列天然的实现了处理机亲和性

2.3同步与互斥

2.3.1同步与互斥的基本概念

同步：直接制约关系，在某些位置上协调多个进程的工作次序而产生的制约关系
源于进程间的相互合作

进程互斥
进程并发，资源共享

两种资源共享方式

• 互斥共享方式
  • 可分配给多个进程，但一个时间段只允许一个进程访问该资源
  • 临界资源
• 同时共享方式
  • 允许一个时间段内由多个进程同时对资源进行访问

对于临界资源的互斥访问步骤

• 进入区：检查是否可进入临界区，设置标志
• 临界区：访问临界资源的代码段
• 退出区：解除正在访问临界区资源的标志
• 剩余区：做其他处理

为保证系统整体性能：

• 空闲则让进入
• 忙则等待
• 有限等待：保证在有限时间内进入临界区(保证不会饥饿)
• 让权等待：当前进程不能进入临界区，应立即释放处理机，防止进程忙等待

2.3.2进程互斥的实现方法

2.3.2.1进程互斥的软件实现方法

• 算法的思想、原理
• 在进入区、退出区都做了什么
• 缺陷

单标志法

两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程
每个进程进入临界区的权限只能被另一个进程赋予

int turn = 0;//表示允许进入临界区的进程号

while (turn != 0);//进入区
critical section;//临界区
turn = 1;//退出区
remainder section;//剩余区

while (turn != 1);//进入区
critical section;//临界区
turn = 0;//退出区
remainder section;//剩余区

该算法可以实现 同一时刻最多只允许一个进程访问临界区
“谦让”

双标志先检查法

设置一个布尔型数组flag[]
数组中各个元素用来标记各进程想进入临界区的意愿

• 每个进程进入临界区前：检查有没有别的进程想进入临界区
• 若没有，则把自身对应flag[]标志设置为true，之后访问临界区
  “表达意愿”

主要问题：违反忙则等待原则
原因：进入区的检查和上锁，不是原子的

双标志后检查法

上一个：先检查后上锁
这个：先上锁后检查

虽然解决了忙则等待问题，但违背了空闲让进 和 有限等待原则
会让进程都长期无法访问临界资源 产生饥饿

Peterson算法

结合双标志、单标志思想
如果双方都争着进入临界区，可以让进程试图谦让

bool flag[2];
int turn = 0;

p0进程：
flag[0] = true;
trun = 1;
while (flag[1] && trun == 1);
// 临界区
critical section;
//
flag[0] = false;
remainder section;

p1进程：
flag[1] = true;
trun = 0;
while (flag[0] && trun == 0);
// 临界区
critical section;
//
flag[1] = false;
remainder section;

主动争取
主动谦让
检查对方是否也想用，且自己不是后谦让的
若自己后谦让，则已经谦让一次了，所以等待

遵循空闲让进、忙则等待、有限等待
但未遵循让权等待原则

2.3.2.2进程互斥的硬件实现方法

中断屏蔽方法

利用开/关中断指令实现

优点：简单高效
缺点：不适用于多处理机，只能用于内核进程，不适用于用户进程

TestAndSet指令

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

用代码描述TSL的逻辑：

bool TestAndSet(bool *lock)
{
	bool old;
	old = *lock;
	*lock = ture;
	return old;
}

TSL的使用

while (TestAndSet(&lock));
临界区代码段
lock = false;//解锁
剩余代码段

优点：实现简单，适合多处理机环境
缺点：不满足让权等待，无法进入临界区会占用CPU资源，忙等待

Swap指令

Exchange指令 或XCHG指令
用硬件实现那的，过程不许被中断

用代码描述swap的逻辑：

Swap(bool *a, bool *b) {
	bool temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

实现互斥的算法逻辑

bool old = true;
while (old == true)
	Swap(&lock, &old);
临界区代码
lock - false;
剩余代码

优点：实现简单，适用于多处理机环境
缺点：不满足让权等待原则，会导致忙等待

2.3.3互斥锁

解决临界区最简单的工具
acquire()获得锁
release()释放锁

acquire() {
	while (!available)
		;//忙等待
	available = false;//获得锁
}

release() {
	available = true;//释放锁
}

缺点：忙等待
需要忙等待的互斥锁都可称为：自旋锁

特性

• 忙等，违反让权等待
• 优点：等待期间不用切换进程上下文，若上锁时间很短，则代价很低
• 常用于多处理器系统，一个忙等待，其他核正常工作并快速释放临界区
• 不太适用于但处理机系统，忙等待过程中不可能解锁

2.3.4信号量

2.3.4.1信号量机制

无法一气呵成、无法让权等待，于是产生了信号量机制

通过一对原语对信号量进行操作，方便的实现进程互斥、同步

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

原语：一气呵成，不可被中断

一对原语：wait(S) 原语和signal(S) 原语
S：信号量

wait、signal原语常简称为P、V操作

整型信号量

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

对信号量只有三种操作：初始化、P操作、V操作

int S = 1;

void wait(int S) {
	while (S <= 0);
	S = S - 1;
}

void signal (int S) {
	S = S + 1;
}

存在的问题：不满足让权等待，忙等

记录型信号量

记录型信号量定义：

typedef struct {
	int value;//剩余资源数
	struct process *L;//等待队列
} semaphore;

需要使用资源时，通过wait原语申请

void wait(semaphore 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原语
		// 唤醒等待队列中的一个进程
		// 该进程从阻塞态转为就绪态
	}
}

可用于实现系统资源的申请和释放

S.value初值：系统中某种资源的数目

调用block会进行自我阻塞，遵循让权等待
调用wakeup会唤醒等待队列中规定第一个进程

2.3.4.2用信号量实现进程互斥

信号量的值：这种资源的剩余数量
若小于0，有进程在等待这种资源
P(S)：申请一个资源S，如果资源不够就阻塞等待
V(S)：释放一个资源S，如果有进程在等待，则唤醒一个进程

信号量机制实现进程互斥

1.划定临界区
2.设置互斥信号量mutex，初值为1
3.在进入区P(mutex)：申请资源
4.在退出区V(mutex)：释放资源

对不同的临界资源要设置不同的互斥信号量
PV操作必须成对出现

记录型信号量不会忙等

信号量机制实现进程同步

进程同步：让各并发进程按要求有序的推进

1.分析什么地方需要实现同步关系
2.设置同步信号量S，初始为0
3.在前操作后执行V(S)
4.在后操作前执行P(S)

先V后P

信号量机制实现前驱关系

本质上是多级同步问题
1.为每一对前驱关系各设置一个同步信号量
2.在前操作之后对相应的同步信号量执行V操作
3.在后操作之前对相应的同步信号量执行P操作

2.3.5生产者-消费者问题

2.3.5.1生产者-消费者问题

生产者，消费者，大小为n的缓冲区(初始为空)
同步关系：

• 缓冲区没满(V)–full->生产者生产(P)
• 缓冲区没空(P)–empty->消费者消费(V)
• 互斥访问缓冲区

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操作不会导致阻塞，因此两个V操作顺序可以交换

2.3.5.2多生产者-多消费者问题

生产者1，生产者2，消费者1(只要1生产者生产的)，消费者2(只要2生产者生产的)，大小为1的缓冲区

互斥关系：

• 互斥访问缓冲区

同步关系：

• 生产者1–>消费者1
• 生产者2–>消费者2
• 缓冲区空时，生产者才能放入缓冲区

此问题中，因为缓冲区大小为1，所以相当于互斥信号量
所以可以充当互斥锁保护缓冲区(省去一个锁了)
缓冲区大小大于1的话，就得加锁了

应该从事件的角度来考虑，抽象为事件的先后关系

2.3.5.3读者写者问题

读者进程，写者进程，共享一个文件

• 多个读者可以同时读
• 只允许一个读者写
• 写完成前不许其他读/写
• 写之前，读/写应该全部退出

读者与消费者不同，不会清空缓冲区中的数据

读者优先

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

writer () {
	while (1) {
		p(rw);
		写文件
		v(rw);
	}
}

reader () {
	while (1) {
		p(mutex);// 读者互斥访问count
		if (count == 0)// 第一个读进程负责读之前加锁
			p(rw);
		count++;// 读进程数+1
		v(mutex);
		读文件
		p(mutex);
		count--;
		if (count == 0)
			v(rw);
		v(mutex);
	}
}

写进程必须等所有读进程读完，会导致饥饿

写者优先

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 () {
	while (1) {
		p(w);
		
			p(mutex);// 读者互斥访问count
			if (count == 0)// 第一个读进程负责读之前加锁
				p(rw);
			count++;// 读进程数+1
			v(mutex);
		
		v(w);
		
		读文件
		p(mutex);
		count--;
		if (count == 0)
			v(rw);
		v(mutex);
	}
}

写者不会饥饿，但也不是真正的写优先
而是相对公平的先来先服务原则
或者叫读写公平法

2.3.5.4哲学家吃饭问题

五个哲学家，五个筷子，必须同时举起左右两根筷子才能进餐，吃完放下两个筷子

哲学家有进餐和思考两种状态

精髓：如何避免临界资源分配不当导致的死锁现象

1.对哲学家加以限制，如最多允许四个哲学家同时进餐
这样至少有一个哲学家可以拿到左右两只筷子

2.要求奇数哲学家拿左边筷子，然后拿右边筷子
而偶数哲学家刚好相反
可以避免占有一支后等待另一支的情况

3.仅当一个哲学家左右两只筷子都可用时才允许抓起筷子

2.3.6管程

为什么要引入管程

信号量机制存在的问题：编写程序困难，易出错

管程的定义和基本特征

管程是一种特殊的软件模块：

• 局部于管程的共享数据结构说明
• 对该数据结构进程操作的一组过程
• 对局部于管程的共享数据设置初始值的语句
• 管程有个名字

基本特征：

• 管程中的数据只能被管程的过程(方法)访问
• 一个进程只能通过管程的方法才能访问管程的数据
• 每次仅允许一个进程在管程内执行某个内部过程

各进程必须互斥访问管程的特性由编译器实现
可在管程中设置条件变量及等待/唤醒操作以解决同步问题

2.4死锁

2.4.1死锁的概念

并发环境下，互相等待对方手中的资源，导致各个进程都阻塞，都无法向前推进的现象

死锁：互相等待对方手里的资源，多个进程都无法向前推进
饥饿：长期得不到想要的资源，某个进程无法向前推进
死循环：一直跳不出某个循环的现象

都是进程无法顺利向前推进的现象

死锁发生的必要条件

• 互斥条件：必须互斥使用的资源的争抢
• 不剥夺条件：获得的资源不能由其他进程强行夺走，只能主动释放
• 请求和保持条件：已经保持了至少一个资源，又请求新的资源，但保持已有的资源不放
• 循环等待条件：存在进程资源的循环等待链

发生死锁一定有循环等待，但循环等待时未必死锁
若同类资源数大于1，则即使有循环等待也未必死锁，反之必然

何时发生死锁

• 对系统资源的竞争
• 进程推进顺序非法，请求和释放资源顺序不当
• 信号量使用不当
  总之：对不可剥夺的资源的不合理分配，可能导致死锁

死锁的处理策略

• 预防死锁
  • 破坏死锁产生的必要条件中的一个或几个
• 避免死锁
  • 用某种方法防止系统进入不安全状态
• 死锁的检测和解除
  • 允许死锁发生，但操作系统会负责检测，并采取某种措施解除死锁

2.4.2死锁的处理策略：预防死锁

破坏互斥条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁

如把只能互斥使用的资源改造成允许共享使用：如SPOOLing技术

缺点：并不是所有的资源都可以改造成可共享使用的资源
很多时候都无法破坏互斥条件

破坏不剥夺条件

方案一：当某个进程请求的资源得不到满足时，必须释放所有保持的资源，以后再重新申请

方案二：某个进程需要的资源被其他进程所占有时，可以由操作系统协助，强行剥夺想要获取的资源
一般需要考虑系统优先级

缺点

• 实现起来比较复杂
• 释放已获得的资源可能导致前一阶段的工作失效
  • 一般只适用于易于保存和恢复状态的资源：如CPU
• 反复的请求释放资源会增加系统开销，降低系统吞吐量
• 方案一会导致进程饥饿

破坏请求和保持条件

静态分配方法：在运行前一次申请完所需的全部资源，尚未满足前不投入运行，投入后一直为他所有

简单

缺点

• 有些资源可能只需要使用很短的事件，会造成严重的资源浪费，资源利用率极低
• 可能导致某些进程饥饿

破坏循环等待条件

顺序资源分配法：给系统中的资源编号，每个进程必须按照编号递增的顺序请求资源
同类资源(编号相同的)一次性申请完

缺点

• 不方便增加新的设备
  • 可能需要重新分配所有编号
• 进程实际使用资源的顺序可能和编号递增顺序不一致
  • 会导致资源浪费
• 必须按照规定次序申请资源，用户编程麻烦

2.4.3死锁的处理策略：避免死锁

安全序列：系统按照这种序列分配资源，则每个进程都能顺利完成
系统就是安全状态
安全序列可能有多个

如果分配资源后，找不出安全序列，则系统进入不安全状态
可能所有进程都无法顺利执行下去
如果有进程提前归还了一些资源，则系统也可能重新回到安全状态

安全状态，一定不会发生死锁
不安全状态，可能会发生死锁

可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求

• 银行家算法的核心思想

银行家算法

把单维数组拓展为多维向量(维度=资源种类)

进程	最大需求	已分配	最多还需要
p0	(7, 5, 3)	(0, 1, 0)	(7, 4, 3)
p1	(3, 2, 2)	(2, 0, 0)	(1, 2, 2)
p2	(9, 0, 2)	(3, 0, 2)	(6, 0, 0)
p3	(2, 2, 2)	(2, 1, 1)	(0, 1, 1)
p4	(4, 3, 3)	(0, 0, 2)	(4, 3, 1)
	最大需求矩阵Max	分配矩阵Allocation	Need矩阵
资源总数(10, 5, 7)
总共分配了(7, 2, 5)
还剩余(3, 3, 2)：可用资源矩阵Available
n个进程，m种资源
Pi进程向系统申请资源：Request数组(长度为m)表示本次申请的资源量

• 寻找最多需要<还剩余的进程
  • 这个进程可以满足
• 还剩余+已分配
  • 回收这个进程的资源
• 去掉这个进程，寻找下一个进程
  • 循环

直到所有进程都加入安全序列，此时系统处于安全状态
暂时不可能发生死锁

可用银行家算法预判本次分配是否会导致系统进入不安全状态

• 1.如果Request[j]<=Need[i, j](0<=j<=m)，转向2
  • 否则所需资源数已超出所宣布的最大值，出错
• 2.如果Request[j]<=Available[j](0<=j<=m)转向3
  • 否则表示尚无足够资源，pi必须等待
• 3.系统试探把资源分配给进程Pi
• 4.OS执行安全性算法，检查此次资源分配后，系统是否处于安全状态
  • 若安全，才正式分配
  • 否则，恢复相应数据，让进程阻塞等待

1.检查申请是否超出之前声明的最大需求数
2.检查系统剩余资源是否能满足请求
3.试探分配，更改数据结构
4.安全性算法，检查是否会导致进入不安全状态

安全性算法：

• 若能满足，则加入安全序列
• 回收资源
• 重复，看看是否所有进程都能加入安全序列

2.4.4死锁的处理策略：检测和解除

死锁的检测

为对系统是否发生死锁进行检测：

• 用某种数据结构保存资源的请求和分配信息
• 提供一个算法，利用上述信息检测是否死锁

数据结构：
资源分配图

• 两种节点：
  • 进程节点(圆圈)：对应一个进程
  • 资源节点(方块)：对应一类资源，可能有多个(里面画多个小圆圈)
• 两种边
  • 进程节点->资源节点：表示进程想申请几个资源(一条边表示一个)
  • 资源节点->进程节点：表示已经为进程分配了几个资源(每条边代表一个)

对于一个进程：资源数-当前资源的分配边>=对当前资源的请求边
则满足，消去这个进程的所有边
判断其他进程

如果最终能消除所有边，则是可完全化简的，此时一定没发生死锁
(相当于找到了一个安全序列)

反正，发生死锁

死锁的解除

一旦检测出死锁的发生，立即解除死锁

注：不是所有进程都是死锁，化简后还连着边的进程就是死锁进程

解除死锁的主要方法：

• 资源剥夺法：挂起死锁进程，抢占资源分配给其他死锁进程
  • 可能导致饥饿
• 撤销进程法：强行终止部分、甚至全部死锁进程，并剥夺资源
  • 简单，但是代价很大
• 进程回退法：选择一些进程，回退到足以避免死锁的地步
  • 需要系统记录进程的历史信息，设置还原点

对谁动手

• 进程优先级
• 已执行多长时间
• 还需多久完成
• 已经使用多少资源
• 进程是交互式还是批处理式