操作系统3--进程的同步

大家可以看下我使用幕布软件画的思维导图，如果大家想使用幕布可以通过我的邀请链接注册，可免费获得一个月高级会员https://mubu.com/inv/477598

3.1 进程同步

3.1.1 同步概念

3.1.1.1 进程同步的概念

进程同步机制的主要任务就是对多个相关进程在执行次序上进行协调，使并发执行的进程之间能按照一定的规则共享系统资源，并能很好的配合工作，从而使程序的执行具有可再现性。

3.1.1.2 制约关系

对于处于同一个系统中的多个进程，由于他们共享着系统的资源，或者为了完成同一个任务而相互合作，所以他们之间可能存在下面两种制约关系：

1. 间接相互制约关系
   系统中的进程难免会调用像打印机、CPU等这样的临界资源。如果想这些资源正常调用，必须保证多个进程之间互斥地访问这些资源，进而就在这些进程间形成了间接相互制约关系。
   为了保证这些进程能有序的进行，对于系统中的这类资源，必须由系统实施统一分配，即用户在使用之前必须先提出申请，绝不允许用户直接使用。
2. 直接相互制约关系
   在系统中也会存在一些进程，他们为了完成同一个目标而相互配合合作工作，这种就是直接互相制约关系。
   进程间的直接制约关系就是源于他们之间的相互合作。

3.1.1.3 临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，如果变量、数据等都可以被若干进程共享，也属于临界资源。

3.1.1.4 临界区

人们把在每个进程中访问临界资源的那段代码称为临界区。若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。
为此，每个进程在进入临界区之前，应先对要访问的临界区进程检查：如果临界区正在被访问，则进程不能进入临界区；如果临界区没有被访问，那进程就可进入临界区，并将临界区正在被访问的标志置为正被访问。
所以，我们可以将访问临界资源的线程的循环代码分为如下部分：

• 访问临界区之前用于上述判断的代码区称为进入区
• 在访问完临界区之后用于将临界区正被访问的标志恢复为未被访问的标志的代码区称为退出区
• 除了进入去、临界区、退出区代码之外的其它代码称为剩余区

while (true) {
    进入区
    临界区
    退出区
    剩余区
}

3.1.1.5 同步机制应遵循的规则

1. 空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效的利用临界资源
2. 忙则等待：当已有进程进入临界区，表明临界资源正在被访问，因而其它视图进入临界区的进程必须等待，以保证对临界资源的互斥访问
3. 有限等待：对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死等”状态
4. 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态

3.1.2 同步机制

3.2.2.1 信号量机制

1. 什么是信号量

信号量的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程，值则与相应的资源的使用情况有关：

• 当他的值大于0时，表示当前可用资源的数量
• 当他的值小于0时，其绝对值表示等待使用该资源的进程个数

2. 什么是信号量机制

信号量机制即利用pv操作对信号量进行处理。而且信号量只能由pv操作进程处理。
当S>0时，S表示可用资源的数量。执行一次P操作意味着分配一个单位资源，因此S值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，他才能运行下去。而执行一个V操作以为着释放一个单位资源，因此S的值加1；当S>0，表示有某些资源正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

3.2.2.2 PV操作

1. P操作

申请一个单位资源，进程进入临界区

wait (S) {
    while (s <= 0) ;// 如果没有资源则循环等待
    S--;
}

1. 将信号量S的值减1，即S=S-1；
2. 如果S<=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

2. V操作

释放一个单位资源，进程从临界区出来

signal (S) {
    S++;
}

1. 将信号量S的值加1，即S=S+1；
2. 如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

3. PV操作的意义

用PV操作来实现进程的同步和互斥

3.2.3 管程机制

尽管信号量机制很方又高效，但是每个要访问临界资源的进程都必须必备同步操作，这就使得大量的同步操作分散在各个进程中。这不仅给系统的管理带来麻烦，还会因同步操作不当而产生死锁。为了解决上述问题，变产生了一种新的同步工具——管程。

1. 管程的定义

系统中各种硬件资源和软件资源均可用数据结构抽象地描述其资源特征，即用少量信息和对该资源所执行的操作来表征该资源。所以就出现了管程。
管程可以看成一个软件模块，它是将共享的变量和对于这些共享变量的操作封装起来，形成一个具有一定接口的功能模块，进程可以调用管程来实现进程级别的并发控制。
在管程入口处的等待队列称为入口等待队列，由于进程会执行唤醒操作，因此可能有多个等待使用管程的队列，这样的队列称为紧急队列，它的优先级高于等待队列。

2. 管程的特征

1. 模块化
   管程是一个基本的软件模块，可以单独编译
2. 抽象数据类型
   管程中封装了数据及对于数据的操作
3. 信息隐藏
   管程外的进程或其他软件模块只能通过管程对外的接口来访问管程提供的操作，管程内部的实现细节对外界是透明的
4. 使用的互斥性
   任何一个时刻，管程只能由一个进程使用。进入管程时的互斥由编译器负责完成

3. 条件变量

一个进程被阻塞或挂起的条件（原因）有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问只能在管程中进行。
管程中每个条件变量都需予以说明，形式为：condition x。对其的操作只有wait和signal，其含义是：

1. x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，知道x条件发生变化。此时其它进程可以使用该管程。
2. x.signal： 正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程，如果存在多个这样的进程，则选择其中的一个，如果没有，继续执行原进程，不产生任何结果。（与信号量的signal不同，没有s=s+1的操作）

3.2 进程同步的经典问题

3.2.1 生产者-消费者问题

1. 问题描述

有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个大小为n的缓冲区，生产者进程将其所产生的产品放入缓冲区中；消费者可从缓冲区中取走产品去消费。他们之间必须保持同步，也就是既不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

2. 问题分析

需要注意的几点：

• 在缓冲区为空时，消费者不能再进行消费
• 在缓冲区已满时，生产者不能再进行生产
• 当一个线程进行生产或消费时，其余线程不能再进行生产或消费

3. 伪代码

var items = 0, space = 10, mutex = 1;
var in = 0, out = 0;
item buf[10] = { NULL };

producer {
    while( true ) {
        wait( space );  // 等待缓冲区有空闲位置， 在使用PV操作时，条件变量需要在互斥锁之前
        wait( mutex );  // 保证在product时不会有其他线程访问缓冲区

        // product
        buf.push( item, in );  // 将新资源放到buf[in]位置 
        in = ( in + 1 ) % 10;

        signal( mutex );  // 唤醒的顺序可以不同
        signal( items );  // 通知consumer缓冲区有资源可以取走
    }
}

consumer {
    while( true ) {
        wait( items );  // 等待缓冲区有资源可以使用
        wait( mutex );  // 保证在consume时不会有其他线程访问缓冲区

        // consume
        buf.pop( out );  // 将buf[out]位置的的资源取走
        out = ( out + 1 ) % 10;

        signal( mutex );  // 唤醒的顺序可以不同
        signal( space );  // 通知缓冲区有空闲位置
    }
}

不能将线程里两个wait的顺序调换否则会出现死锁。例如(调换后)，将consumer的两个wait调换，在producer发出signal信号后，如果producer线程此时再次获得运行机会，执行完了wait(space)，此时，另一个consumer线程获得运行机会，执行了wait(mutex)，如果此时缓冲区为空，那么consumer将会阻塞在wait(items)，而producer也会因为无法获得锁的所有权所以阻塞在wait(mutex)，这样两个线程都在阻塞，也就造成了死锁。

3.2.2 哲学家进餐问题

1. 问题描述

有五位哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子。他们的生活的方式是交替的进行思考和进餐：平时，一个哲学家进行思考，饥饿时便视图取其左右离他最近的筷子，只有在他拿到两只筷子时才能进餐，进餐完毕，放下筷子继续思考。

2. 问题分析

• 只有拿到两只筷子时，哲学家才能吃饭。
• 如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。
• 任一哲学家在自己未拿到两只筷子吃完饭前，不会放下手中已经拿到的筷子

3. 伪代码

至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。定义信号量count，只允许4个哲学家同时进餐，这样就能保证至少有一个哲学家可以就餐。

semaphore chopstick[5]={1,1,1,1,1};
semaphore count=4; // 设置一个count，最多有四个哲学家可以进来
void philosopher(int i)
{
	while(true)
	{
		think();
		wait(count); //请求进入房间进餐 当count为0时 不能允许哲学家再进来了
		wait(chopstick[i]); //请求左手边的筷子
		wait(chopstick[(i+1)%5]); //请求右手边的筷子
		eat();
		signal(chopstick[i]); //释放左手边的筷子
		signal(chopstick[(i+1)%5]); //释放右手边的筷子
		signal(count); //离开饭桌释放信号量
	}
}

3.2.3 读者-写者问题

1. 问题描述

一个数据文件或记录可被多个进程共享，我们把只要求读该文件的进程称为“Reader进程”，其它进程则称为“Writer进程”。允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个Writer进程和其它Reader进程或Writer进程同时访问共享对象，这样很有可能造成共享数据混乱。

2. 问题分析

• 允许多个Reader进程同时操作一个共享对象
• 不允许Writer进程和其它进程同时操作一个共享对象

3. 伪代码

semaphore rmutex = 1,wmutex = 1;
int readcount = 0;
void reader(){
	do{
		wait(rmutex);
		if(readcount==0) wait(wmutex);
		readcount++;
		signal(rmutex);
		···
		perform read operation;
		···
		wait（rmutex）；
		if(readcount==0) signal(wmutex);
		readcount--;
		signal(rmutex);
	}while(TRUE);
}

void writer(){
	do{
		wait(wmutex);
		perfrom write operation;
		signal(wmutex); 
	}while(TRUE);
}