进程之间的同步和互斥

同步，是指一个某一步的执行必须需要等待其他操作完成之后

互斥，是指一个进程的某一块只能有一个进程访问

6.经典进程同步问题

6.1 生产者-消费者问题 (既有同步又有互斥)

问题描述

生产者往缓冲区写数据，满了的话就不能写了

消费者从缓冲区取数据，空的话就不能取了

一次只能有一个生产者或消费者取读数据

问题分析

核心解决

（1）不能向满的缓存区写数据，否则的话必须等待（同步关系）

（2）不能向空的缓存区取数据，否则的话必须等待（同步关系）

（3）任何时刻，仅允许一个1个生成者或1个消费者访问

意味着消费者之间互斥，生成者之间互斥，消费者和生产者之间互斥，总结来说就是任意两个进程之间对缓冲区操作的时候，其他进程不能操作（互斥关系）

full：记录缓冲区中非空的槽数，初始值=0

empty：记录缓冲区中空的槽数，初始值=N

mutex：确保进程不同时访问缓冲区，初始值=1

解决（1）（2）

void producer(void){
	while (True) {
        produce(); //生产1项
        P(empty); //申请1个空槽
        P(mutex); //请求进入临界区
        append(); //加入缓冲区
        V(mutex); //离开临界区
        V(full); //递增非空槽
    }
}

void consumer(void){
    while (TRUE) {
        P(full); //申请1个非空槽
        P(mutex); //申请进入临界区
        remove(); //从缓冲区移出1项
        V(mutex); //离开临界区
        V(empty); //递增空槽数
        consume(); //消费数据
    }
}

6.2 读者-写者问题

问题描述

多个Reader进程，多个Writer进程，共享文件F
要求：
允许多个Reader进程同时读文件
不允许任何一个Writer进程与其他进程同时访问（读或写）文件

问题分析

写者之间要互斥

读者和写者之间互斥

读者之间不互斥

所以核心是我们要在第一个读者进来的时候，进行判断是否有写者正在写

标答

write

WriteMutex = 0 读写操作的互斥访问
Rcount = 0 正在读操作的读者数目
CountMutex = 0 读者计数的互斥访问

void reader(void){
	while (True) {
		P(CountMutex);
  		if (Rcount == 0)
     		P(WriteMutex);
     		++Rcount;
		V(CountMutex);
     	read;
		P(CountMutex);
 		--Rcount;
      	if (Rcount == 0)
     		V(WriteMutex);
		V(CountMutex);

       
    }
}

void writer(void){
    while (True) {
    	P(WriteMutex);
        write;
    	V(WriteMutex);

    }
}

6.3 哲学家进餐问题

问题描述

有5个哲学家围坐在一张圆桌周围，每个哲学家面前有1碗饭，左右各1把叉子。
哲学家有两种活动：思考和吃饭。
只有拿到左右两把叉子才能吃饭。
吃饭后，放下叉子，继续思考。

//5个信号量，分别用于对5个叉子互斥
#define TRUE  1
#define  N  5 //哲学家数
Semaphore_t  fork[] = {1, 1, 1, 1, 1}; 
void philosopher (int i) //i是哲学家编号：0~N-1  
{
    while (TRUE)  {
        think(); 
        P(fork[i]); 
        P(fork[(i+1) % N]); 
        eat(); 
        V(fork[i]); 
        V(fork[(i+1) % N]); 
    }
}

7. 进程之间通信

P,V操作实现的是进程之间的低级通信，所以P,V操作是低级通讯原语，即不能传递大量的信息

所以我们引入进程间高级通讯方式

7.1 共享存储区

相互通信的进程间设有公共的内存区，每个进程既可向该公共内存中写，也可从公共内存中读，通过这种方式实现进程间的信息交换。
把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制

7.2 消息传递

源进程发送消息，目的进程接受消息。所谓消息，就是一组数据。

（1）消息队列（message Queue）或消息缓冲
发送者发消息到一个消息队列中；
接收者从相应的消息队列中取消息。
消息队列所占的空间从系统的公用缓冲区中申请得到。
（2）邮箱（mailbox）
发送者发消息到邮箱，接收者从邮箱取消息。
邮箱是一种中间实体，一般用于非实时通信。

7.3 管道

首创于Unix。用于连接一个读进程、一个写进程，以实现它们之间通信的共享文件，称为pipe文件。

管道分为下列2种：
有名管道
无名管道

8.线程

为什么引入线程

线程是进程的１条执行路径。方便进程内部的同步操作，线程之间共享内存

比如，一个文字输入软件，其内部可以有三个线程，一个用来加载视频、一个用来播放视频，一个用来备份。因为进程之间不共享内存，所以不能用多个进程来实现这时就用多线程可以解决。线程之间共享内存，所以从一个线程切换到另一个线程不需要陷入内核，也不需要切换上下文，线程之间的切换比进程切换快捷。

　1个进程可以有多个线程，其中至少有1个主线程（primary thread）。

　1个进程内的多个线程在同一个地址空间内（共享该进程的地址空间）。

每个线程有自己的线程控制块TCB（Thread Control Block），包含自己的堆栈和状态信息。TCB比PCB小得多。

8.1 线程的实现机制

用户级线程

由在用户空间执行的线程库来实现，OS对此一无所知。　
线程库提供线程创建、撤消、上下文切换、通信、调度等功能。

用户级线程是自己实现的线程创建，删除

但是这样的话操作系统分配的是进程为单位的，容易阻塞

但是性能高，无需陷入内核

核心级线程

用户级线程是自己实现的线程创建，删除

但是这样的话操作系统分配的是线程为单位的

但是性能低，需要陷入内核

9 进程调度

为什么进程调度

多个进程就绪时候，OS决定先执行哪一个

我们进程调度要达到的目的

CPU利用率高，吞吐量大，周转时间少，等待时间短，公平

很多时候都是在权衡！很多时候很难兼顾所有的目的

什么时候会切换进程呢？

硬件中断，进程异常，或者该进程请求IO，这些都会让CPU闲下来，我们就要给CPU找活干了

一些概念

周转时间 = 作业完成时刻 - 作业到达时刻
带权周转时间 = 周转时间 / 服务时间
平均周转时间 = 作业周转总时间 / 作业个数
平均带权周转时间 = 带权周转总时间 / 作业个数

9.1 调度方式

非抢占方式

一旦某进程被调度，直到完成或因某事件而阻塞，才会切换到其他进程

抢占方式

允许暂停正在运行的进程，切换到其他进程

抢占原则：

时间片原则：时间片到时抢占

优先级原则：优先级高者到时抢占

9.2 常见算法

9.2.1 先来先服务 FCFS

方法

按照进程就绪的先后次序来调度进程，非抢占式方式

优点：实现简单

缺点:
（1）平均等待时间波动很大
短进程、长进程到达时间是随机的
（2）有利于CPU繁忙型进程，不利于I/O繁忙型进程
（3）有利于长进程，不利于短进程

9.2.2 短进程优先 SPN

方法：

选择估计运行时间最短的进程运行。
短进程优先算法具有最优平均周转时间

优点：

平均等待时间较短

缺点

对长进程（作业）不利。
极端情况下，会使长进程（作业）得不到调度。

所以在这个上面的改进提出最高响应比算法

9.2.3 最高相应比优先算法

方法

选择就绪队列中相应比R值最高的进程
R = （W + S）/ S
W: 等待时间（waiting time）
S: 执行时间（service time）

短进程优先算法：长进程等待的时间而出现饥饿
对于最高响应优先算法，如果等待时间越长，则R会越大，在一定程度上避免了长进程出现饥饿的情况

但上面的两种方法都得估计进程运行的时间，这个预测未来比较难

另外计算开销比较大，所以应用比较少

9.2.4 时间片轮转 RR

方法

将所有的就绪进程按FCFS原则排成一个队列，
规定一个时间片为进程每次使用CPU的最长时间，
每次选择队首进程运行，
当时间片到时，剥夺该进程的运行，将其排在队尾

9.2.5 基于优先级的调度

方法

每个进程一个优先级；
总是选择就绪队列中优先级最高的进程投入运行；
可以是抢占式，或非抢占式。

9.2.6 多级反馈队列

方法

(1) 按优先级设置n(n>1)个就绪队列，每个队列赋予不同优先级。如第一级队列到最后一级队列，优先级依次降低。
(2) 优先级越高队列，分配的时间片越小。
(3) 每个队列按照先来先服务原则排队。
(4) 一个新进程就绪后进入第一级（或相应优先级）队尾。
(5) 调度方法
每次选择优先级最高队列的队首进程运行；
若被调度进程的时间片到，则放入下一级队列的队尾；
最后一级队列采用时间片轮转；
当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来队列的末尾。

该算法综合了前面几种算法的优点。
既考虑了先来先服务，又照顾了长进程；
既考虑了优先级，又讲求公平。

10 进程死锁

10.1 基本概念

第一个概念死锁

死锁

什么是死锁呢？

一个进程集合中的每个进程都在等待只能由该集合中的其它进程才能引发的事件，这种状态称作死锁。一组竞争系统资源的进程由于相互等待而出现“永久”阻塞。

例如，2个进程A、B，都需要资源R1、R2

若A：拥有R1，申请R2

若B：拥有R2，申请R1

如何？

第二个概念资源的基本分类

资源分类

可重用资源

资源不能被删除且在任何时刻只能有一个进程使用

进程释放资源后，其他进程可重用

例如：处理器，I/O通道等等

可能出现的死锁

每个进程占用一部分资源并请求其他资源

消耗资源

资源创建和销毁过程

例如：在I/O缓冲区的中断、信号和消息等

可能出现的死锁

进程间相互等待接收对方的消息

10.2 什么情况产生死锁

四个必要条件

1）互斥条件
每个资源要么被分配给了1个进程，要么空闲
2）占有及等待（部分分配）条件
已经得到了资源的进程要申请新的资源
3）不可剥夺条件
已经分配给一个进程的资源不能被剥夺，只能由占有者显式释放
4）环路等待条件
存在由2个或多个进程组成的一条环路，
该环路中的每个进程都在等待相邻进程占有的资源

10.3 死锁前—检测死锁

一由OS处理

1 检测死锁并恢复

2 分配资源时避免死锁

3 假装没看见（鸵鸟策略）：多数OS对待死锁的策略，那死锁了怎么办，开机重启

二由应用程序本身预防死锁

实际中检测死锁恢复是可能的，但是代价太大

10.3.1 死锁检测

方法一资源分配图

看看有没有环，有环的话有没有无法释放的情况

方法二矩阵

10.3.2 何时检测

1）每当有资源请求时；

2）周期性检测；

3）每当CPU的使用率降到某一阈值时。

死锁检测会占用大量的CPU时间

10.4 死锁前—死锁避免

银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态。如果是，则不满足该请求；否则，便满足。

使得死锁四个条件有一个不成立

1 破坏互斥条件对资源统一管理，如SPOOLing技术

2 破坏不可剥夺条件当进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源。

3 破坏占有及等待条件原子性地获得所需全部资源。

4 破坏环路等待条件把系统中所有资源按类型不同进行线性排队，并编号

10.5 死锁后—恢复死锁

如何从死锁中恢复？

1 剥夺法恢复
将某一资源从一个进程抢占过来给另一个进程使用
不能影响原进程的最终执行结果
取决于资源的特性

2 回退法恢复
从各进程最近的检查点（check point）逐次重新启动

3 杀死进程来恢复
最好杀死可重复执行、不会产生副作用的进程

Qodicat's World

Try something new and interesting

6.经典进程同步问题

6.1 生产者-消费者问题 (既有同步又有互斥)

6.2 读者-写者问题

6.3 哲学家进餐问题

7. 进程之间通信

7.1 共享存储区

7.2 消息传递

7.3 管道

8.线程

8.1 线程的实现机制

9 进程调度

9.1 调度方式

9.2 常见算法

9.2.1 先来先服务 FCFS

9.2.2 短进程优先 SPN

9.2.3 最高相应比优先算法

9.2.4 时间片轮转 RR

9.2.5 基于优先级的调度

9.2.6 多级反馈队列

10 进程死锁

10.1 基本概念

10.2 什么情况产生死锁

10.3 死锁前—检测死锁

10.3.1 死锁检测

10.3.2 何时检测

10.4 死锁前—死锁避免

10.5 死锁后—恢复死锁

谢谢你给我买一个棒棒糖