进程同步与互斥

进程具有异步性：

异步性是指进程以不可预知的速度向前推进。内存中的每个进程何时执行,何时暂停,以怎样的速度向前推进,每道程序总共需要多少时间才能完成等,都是不可预知的。

进程同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

举一个生活中的例子：

例如有两个进程，

你肚子饿了想要吃饭，你叫妈妈早点做菜，妈妈听到后就开始做菜，但是在妈妈没有做完饭之前，你必须阻塞等待，等妈妈做完饭后，自然会通知你，接着你吃饭的事情就可以进行了。

image-20220911100026665

进程互斥

  • 临界资源：一个时间段内只允许一个进程使用的资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
  • 临界区：访问临界资源的代码片段，一定不能给多线程同时执行。

对临界资源的访问，必须互斥地进行。

互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

【也就说保证一个线程在临界区执行时，其他线程应该被阻止进入临界区】

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

1
2
3
4
5
6
do{
    entry section;	//进入区  负责检查是否可进入临界区，若可以，则设置【正在访问临界资源的标志】(上锁)，阻止其他进程访问。
    critical section;		//临界区  访问临界资源的代码
    exit section;			//退出区	负责解除【正在访问临界资源的标志】(解锁)
    remainder section;		//剩余区   其他处理
}while(true)

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

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

注意，同步与互斥是两种不同的概念：

  • 同步就好比：「操作 A 应在操作 B 之前执行」，「操作 C 必须在操作 A 和操作 B 都完成之后才能执行」等；
  • 互斥就好比：「操作 A 和操作 B 不能在同一时刻执行」

进程互斥的软件实现方法

单标志法

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

用伪代码表示如下：

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

image-20220911102116198

分析：

  1. 初始时，turn = 0表示只允许0号进程使用临界资源。
  2. 当P0进程到来时，while(turn!=0)循环不成立，就会进入临界区。当P1进程到来时，while(turn!=1)循环成立，就会一直循环，一直等待。
  3. P0临界区出来以后，进入退出区，turn = 1【表示允许1号进程使用临界资源】，P1的while(turn!=1)循环不成立，跳出循环。进入临界区。
  4. P0临界区出来以后，进入退出区，turn = 0【表示允许0号进程使用临界资源】，等0号需要使用的时候，就可以直接使用了。

缺点：

  • 对于临界区来说，一定是按P0 –> P1 –> P0 –> P1 … 这样轮流访问的。
  • 如果turn=0时，P1进程到来，但P0却迟迟不到来，P1就会占用CPU 一直等待

存在的问题是：虽然实现了进程互斥访问，但是违背空闲让进原则。

双标志先检查法

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

比如：“flag[0]=ture”意味着0号进程P0现在想要进入临界区。

每个进程在进入临界区之前：

  1. 先检查当前有没有别的进程想进入临界区
  2. 如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。
  3. 如果有，则一直等待

初始：

1
2
3
bool flag[2];		//表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;	//刚开始设置为两个进程都不想进入临界区

image-20220911103620796

由于是软件的实现，这两个进程是并发执行的

分析：

  • 如果执行顺序是 ①② ⑤ ③④ ⑥⑦⑧

    • flag[1] = flase;所以①循环不成立，执行②，设flag[0]=true。
    • 执行到⑤时，while(flag[0])就会一直循环，一直等待。
    • 直到执行完③【临界区】,在执行④时，flag[0]=false【P0退出临界区】，⑤就会断开循环，然后就可以进入到临界区【P1进入临界区】

    此时就实现了P0,P1互斥访问，当然⑤⑥ ① ⑦⑧ ②③④ 也可以实现互斥访问。

  • 如果执行顺序是 ① ⑤ ② ⑥ ….P0 和 P1就会同时进入临界区

    • 初始的时候，flag[0] = false;flag[1] = false;
      • 执行 ①循环不成立，进程P0不会循环等待。
      • 执行 ⑤循环不成立，进程P1不会循环等待。
    • ②⑥ 分别设置 flag[0]=true;flag[1]=true分别不让对方进。但此时，对方都已经进入了。

    然后P0，P1都进入了临界区。一个时间段内，P0和P1同时访问临界资源。

由此可以看出，存在的问题是违背忙则等待原则。这是非常危险的

双标志后检查法

与双标志先检查不同的是：

  • 双标志先检查法是：先检查 后上锁
  • 双标志后检查法是：先上锁后检查
1
2
3
bool flag[2];		//表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;	//刚开始设置为两个进程都不想进入临界区

image-20220911110116187

分析：

互斥就不分析了，和双标志先检查差不多。我们来分析一下问题所在

如果执行顺序是 ① ⑤ ② ⑥ ….P0 和 P1就会都进不去临界区

  • 执行 ① 和 ⑤ flag[0]=true;flag[1]=true分别不让对方进。
  • 执行② ，循环成立，进程P0一直等待。
  • 执行⑥，循环成立，进程P1一直等待。

因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

双标志后检查法 和 双标志先检查法 问题所在 的根本原因是：

检查和上锁不是一气呵成的。

进程双方的检查和上锁，可能会交替执行。这就是导致问题所在

image-20220911110913902

Peterson算法

双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

Gary L.Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。

初始

1
2
bool flag[2];	//表示进入临界区意愿的数组,初始值都是false
int turn = 0;	//turn表示优先让哪个进程进入临界区

P0进程：

1
2
3
4
5
6
flag[0] = true;					//表示P0自己想进入临界区
turn = 1;						//但如果P1想进，愿意让P1先进
while (flag[1] && turn==1); 	//如果P1想进入临界区 且 最终让给了1 就一直循环等待
critical section;
flag[0] = false;
remainder section;

P1进程：

1
2
3
4
5
6
flag[1] = true;					//表示P1自己想进入临界区
turn = 0;						//但如果P0想进，愿意让P0先进
while (flag[0] && turn==0);		//对方想进，且最后一次是自己“让梨"，那自己就循环等待
critical section;
flag[1] = false;				//访问完临界区，表示自己已经不想访问临界区了
remainder section;

我们可以推理验证，各个操作按照不同顺序穿插执行是可以实现互斥的

可以用举一个生活的例子：

A 和 B 都想上厕所，但只能一个人进入。

  • A：A想用马桶，但B可以先用。【flag[A]=true;turn = B】
  • B：B想用马桶，但A可以先用。【flag[B] = true;turn = A】
  • 最终 turn=A ，flag都为true。
  • A 的while (flag[A] && turn==A);循环等待
  • B 的while (flag[B] && turn==B); 则放行。B使用了马桶。

我们可以看到，最终谁能进入，取决于谁是最后一次被让梨的

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

因为等待的过程中，一直处于while循环过程中。

①②③ 是进入区、④是临界区、⑤是退出区。

进程互斥的硬件实现方法

中断屏蔽法

利用”开关中断指令“实现。

1
2
3
4
5
...
关中断;
临界区;
开中断;
...

与原语的实现思想相同，

在某进程开始访问临界区到结束访问为止都不允许被中断

不能发生中断 —> 不能发生进程切换 —> 不可能发生两个同时访问临界区的情况

  • 优点：简单高效
  • 缺点：
    • 只适用于单核CPU，不适合多核CPU
      • 在CPU的一个核里开关中断，这个核不能进行进程切换，也就达到了互斥
      • 如果，多个核，其他核的进程照样能同时访问临界资源。
    • 只适合操作系统内核进程，不适合用户进程【开/关中断指令只能运行在内核态】

TestAndSet

简称TS指令，也有地方称 TestAndSetLock指令，或TSL指令

TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

用C语言表述如下：

1
2
3
4
5
6
bool TestAndSet(bool *lock){
    bool old;
    old = *lock;	// old用来存放lock原来的值
    *lock = true;	//无论之前是否已加锁，都将lock设为true
    return old;		//返回lock原来的值
}

布尔型共享变量lock表示当前临界区是否被加锁

  • true表示已加锁
  • false表示未加锁

TSL指令实现的 进程互斥的代码逻辑如下：

1
2
3
4
while(TestAndSet(&lock));  	//检查 并 “上锁”
临界区代码段...
lock = false;				//“解锁”
剩余区代码段...

相比软件实现方法，

软件实现的问题所在就是 “上锁” 和 “检查” 不是一气呵成的，是有可能进程间穿插执行的。

TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

  • 优点：
    • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
    • 适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。【等待的过程还占用CPU】

TestAndSet 指令，顾名思义，就是 检查并上锁 的指令。

无论临界资源有没有上锁，都会有一个上锁操作。

Swap指令

Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

用C语言描述如下：

1
2
3
4
5
6
Swap(bool *a,bool *b){
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

Swap指令的作用是交换两个变量的值

用Swap指令实现互斥的算法逻辑如下：

1
2
3
4
5
6
bool old = true;
while(old == true)
    Swap(&lock,&old);
临界区代码段...
lock = false;
剩余区代码段...

逻辑上来看Swap和TSL并无太大区别

  1. 都是先记录下此时临界区是否已经被上锁（记录在 old变量上)
  2. 再将上锁标记lock设置为true，最后检查old，
  3. 如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点和缺点和TSL指令一样。

信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量),

可以用一个信号量来表示系统中某种资源的数量【比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。】

一对原语： wait(S)原语和signal(S)原语

可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量s其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、v操作。因此，常把wait(S)、signal(S)两个操作分别写为P(S)、v(S)

有两种信号量机制：

  • 整型信号量
  • 记录型信号量

我们重点说一下记录型信号量

记录型信号量：用记录型数据结构表示的信号量。

用C语言表示如下：

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

某进程需要使用资源时，通过wait原语申请。

wait原语C语言表示如下：

1
2
3
4
5
6
void wait (semaphore s) {
    s.value--;  	// 该 临界资源数量-1
	if (S.value < 0 ) {  	//如果 临界区资源数量为负  则表示  没有资源可分配了
        block (S.L);		//将进程挂到 该临界资源的等待队列。
    }
}

如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把该进程挂到信号量S的等待队列（即阻塞队列）中

进程使用资源后，通过 signal 原语释放

1
2
3
4
5
6
void signal (semaphore s) {
    s.value++;
    if (s.value <= 0) {
        wakeup(S.L);
    }
}

释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态

互斥例子演示

某计算机系统中有2台打印机…，

则可在初始化信号量s时

  • S.value的值设为2
  • 队列s.L设置为空
image-20220911205654143

你可以把这个 记录型信号量 类比为 我们平时写代码时的 全局变量。

P0~P3进程。

image-20220911205815433

刚开始的时候CPU为P0进程服务，执行wait(s)原语。S.value– 。此时S.value = 1 > 0。P0进程进入临界区，打印机1分配给P0进程。

image-20220911210934023
S.value = 1,S.L = null

然后CPU为P1进程服务，执行wait(s)原语。S.value– 。此时 S.value = 0 == 0。P1进程进入临界区，打印机2分配给P1进程。

image-20220911211935614
S.value = 0,S.L = null【资源恰好分配完】

CPU为P2进程服务时，执行wait(s)原语。S.value– 。此时 S.value = -1 < 0。该进程被阻塞，由运行态转为阻塞态，然后挂载到信号量S的等待队列中

image-20220911212245388
S.value = -1,S.L = [P2]【有一个进程等待】

CPU为P3进程服务时，执行wait(s)原语。S.value– 。此时 S.value = -2 < 0。该进程被阻塞，由运行态转为阻塞态，然后挂载到信号量S的等待队列中

image-20220911212402389
S.value = -2,S.L = [P2,P3]【有两个进程等待】

P0在打印机完后，执行signal(S)原语，S.value++。此时 S.value = -1 <= 0。说明有进程正在等待临界资源。

将信号量的队头取出一个进程【P2】，将刚刚释放的打印机1资源分配给P2。

image-20220911212844961
S.value = -1,S.L = [P3]【有一个进程等待】

CPU为P2服务，P2就可以使用打印机资源了。

使用完成后执行signal(S)原语，S.value++。此时 S.value = 0 <= 0。说明有进程正在等待临界资源。

将信号量的队头取出一个进程【P4】，将刚刚释放的打印机1资源分配给P4。

image-20220911213517242

S.value = 0,S.L = null

核心的差不多说完了，后面的就不说了

  • 对信号量s的一次Р操作意味着进程请求一个单位的该类资源，

    需要执行S.value–，表示资源数减1，当S.value <0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞（当前运行的进程从运行态→阻塞态），主动放弃处理机，并插入该类资源的等待队列s.L中。可见，该机制遵循了“让权等待”原则,不会出现“忙等”现象。

  • 对信号量s的一次V操作意味着进程释放一个单位的该类资源

    需要执行S.value++，表示资源数加1，若加1后仍是S.value <=o，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态→就绪态）。

用信号量机制实现进程互斥与同步

进程互斥

  1. 分析并发进程的关键活动，划定临界区
  2. 设置互斥信号量 mutex,初始值为 1
  3. 在临界区之前执行P(mutex)
  4. 在临界区之后执行V(mutex)

初始化信号量

1
semaphore mutex = 1; //信号量的简写形式

实际上是

1
2
3
4
typedef struct {
    int value = 1;//剩余资源数
	struct process *L;//等待队列
}semaphore;
image-20220911220140702

P、V操作必须成对出现。

  • 缺少P(mutex)就不能保证临界资源的互斥访问
  • 缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

注意：对不同的临界资源需要设置不同的互斥信号量。

进程同步

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

比如，P1、P2并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。

image-20220911220728425

若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行。

那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。

步骤：

  1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码)
  2. 设置同步信号量s,初始为0
  3. 在“前操作”之后执行V(S)
  4. 在“后操作”之前执行P(S)

初始化信号量

1
semaphore mutex = 0; //信号量的简写形式

image-20220911221041233

代码4 要在 代码 2之后执行。

代码4之前 P操作，代码2之后V操作。

注意，初始信号量为0。

  • 如果代码2没有执行完，就不会执行V(S)操作。当要执行代码4之前，必定执行P(S)，s.value– ,s.value<0，P2进程阻塞。

    然后执行到代码2之后的V(S)操作，s.value++。s.value=0;s.value<=0，就会唤醒P2，然后就可以执行代码4了。

  • 如果代码2执行结束，然后执行V(S)操作，s.value++。s.value = 1当要执行代码4之前，必定执行P(S)，s.value– ,s.value = 0;s.value>=0，进程不会阻塞，然后就可以执行代码4了。

信号量机制实现前驱关系

进程P1中有句代码S1，P2中有句代码S2 ..P3…P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行:

image-20220911221928035

每一对前驱关系都是一个进程同步问题。

  1. 要为每一对前驱关系各设置一个同步变量
  2. 在“前操作”之后对相应的同步变量执行v操作
  3. 在“后操作”之前对相应的同步变量执行Р操作
image-20220911222213226

【不完整，可以根据a 、b依次类推】

经典问题

生产者消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注:这里的“产品”理解为某种数据)

image-20220912151936366

生产者、消费者共享一个初始为空、大小为n的缓存区。

  • 缓冲区没满时，生产者进程才能把产品放入缓冲区。【同步问题】
    • 缓冲区由非满 变为 满时，要阻塞生产者进程。【运行态 ——> 阻塞态】
    • 缓冲区由满 变为 非满，要唤醒生产者进程。【阻塞态 ——> 就绪态】
  • 缓冲区非空时，消费者才能从缓冲区中取走一个产品。【同步问题】
    • 缓冲区从 非空 变为 空，要阻塞消费者进程。【运行态 ——> 阻塞态】
    • 缓冲区从空 变为非空，要唤醒消费者进程。【阻塞态 ——> 就绪态】
  • 某一时刻，缓冲区只能由一个进程使用。缓冲区属于临界资源。【互斥问题】

如何用信号量机制（P、V操作）实现生产者、消费者进程的这些功能呢？

先回顾一下P、V操作

1
2
3
4
5
6
7
8
9
10
11
12
void P(semaphore s) {
    s.value--;  	
	if (S.value < 0 ) {  	
        block (S.L);		
    }
}
void V(semaphore s) {
    s.value++;
    if (s.value <= 0) {
        wakeup(S.L);
    }
}

每P一下，就要消耗一个临界区资源。

每V一下就要释放一个临界区资源。

分析：

  • 空闲位置无之前，生产者进程才能放入。生产者每次要消耗一个空闲位置（P），并生产一个产品（V）
    • 生产者进程要在 空闲位置 无之前运行，所以是同步问题。
  • 产品数量无之前，消费者进程才能取出。消费者每次要消耗一个产品（P），并释放一个空闲位置（V）
    • 消费者进程要在产品数量 无之前运行，所以是同步问题。
  • 往缓冲区放入/取走产品需要互斥。

注意 红色的是一对P、V操作。蓝色的是一对P、V操作。

初始化信号量

1
2
3
semaphore mutex = 1;			//互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;			//同步信号量,表示空闲缓冲区的数量
semaphore full = 0;				//同步信号量,表示产品的数量,也即非空缓冲区的数量

mutex=1是互斥信号量。缓冲区只有一个

消费者进程在消费一个产品之前，要检查此时缓冲区中，产品数量是否为0。所以要设置信号量full = 0，初始时产品数量为0。

生产者进程在生产一个产品之前，要检查此时缓冲区中，空闲位置释放为0。所以要设置信号量empty = n，初始时空闲位置为0。

用伪代码表示生产者进程如下：

1
2
3
4
5
6
7
8
9
10
producer(){
    while(1){
        生产一个产品;
        P(empty);	//消耗一个空闲位置
        P(mutex);	//消耗一个缓冲区资源
        将产品放入缓冲区;				//临界区
        V(mutex);	//释放一个缓冲区资源
        V(full);	//增加一个产品
    }
}

用伪代码表示消费者进程如下：

1
2
3
4
5
6
7
8
9
10
11
consumter(){
    while(1){
        P(full);			//消耗一个产品
        P(mutex);			//消耗一个缓冲区资源
        从缓冲区取出一个产品;
        V(mutex);			//释放一个缓冲区资源
        V(empty);			//释放一个空闲位置
        使用产品;
        
    }
}

我们发现，我们连续使用了两个P操作。

image-20220912160505346
  • 第一个P操作是用来实现同步的
  • 第二个P操作是用来实现互斥的

那这两个P操作可不可以颠倒位置呢？

image-20220912161202433

答案是不能的！

假如，此时缓冲区已满，即empty = 0，full = n;

生产者进程 执行 ①，mutex–，mutex = 0，缓冲区临界资源被上锁。

生产者进程 执行②，empty–，empty<0，生产者进程被阻塞，挂载到了empty信号量的等待队列上。

消费者进程 执行③，mutex–，mutex<0,说明此时缓冲区每有空闲的，因此消费者进程也被阻塞了，挂载到了mutex信号量的等待队列上

这就产生了死锁现象。

即，生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒。

V操作不会导致进程阻塞，因此两个v操作顺序可以交换。

如果不实现互斥，两个生产者进程“同时”访问缓冲区，可能会发生数据覆盖问题。

多生产者多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。

爸爸专向盘子中放苹果，妈妈专向盘子中放橘子。

儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。

只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

image-20220912173800328

盘子可以看成 大小为1，初始为空的缓冲区。

  • 互斥关系：

    • 对缓冲区（盘子）的访问要互斥进行。

  • 同步关系：

    • 父亲将苹果放入盘子后，女儿才能取苹果
    • 母亲将橘子放入盘子后，儿子才能取橘子
    • 只有盘子为空时，父亲或母亲才能放入水果【“盘子为空”的事件可以由儿子或者女儿触发】

    所以需要 四对PV操作。

    image-20220912174333174

    初始化信号量

    1
    2
    3
    4
    semaphore mutex = 1;		//实现互斥访问盘子（缓冲区)
    semaphore apple = 0;		//盘子中有几个苹果
    semaphore orange = 0;		//盘子中有几个橘子
    semaphore plate = 1;		//盘子中还可以放多少个水果

    用伪代码表示如下：

    image-20220912174958114

    实际上

    由于盘子缓冲区大小为1，所以其实可以不用mutex互斥信号量也可以实现互斥。

    但如果缓冲区大小大于1，则必须 使用信号量mutex 来实现互斥！

在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。

读者-写者问题

「读者-写者」，它为数据库访问建立了一个模型。

问题描述：

有读者和写者两组并发进程，共享一个文件。

当两个或两个以上的读进程同时访问共享数据时不会产生副作用。

但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

因此要求：

  • 「读-读」允许：同一时刻，允许多个读者同时读
  • 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
  • 「写-写」互斥：没有其他写者时，写者才能写
image-20220912201334546

两类进程：读进程、写进程。

互斥关系：写进程 - 写进程、写进程 - 读进程。【读进程 - 读进程 不互斥】

方法一

只设置一个信号量 rw=1。

1
semaphore rw = 1;

写者进程和任何进程都互斥，在写者访问共享文件前后分别执行P、v操作。

读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对rw执行P、v操作。

但这样，也会使【读者 - 读者互斥】，但我们要求 读者 - 读者 要允许共享。

方法二

P(rw)和V(rw)其实就是对共享文件的“加锁”和“解锁”。

既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问。

可以设置一个整数变量count来记录当前有几个读进程在访问文件。

第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。

初始化信号量和变量

1
2
semaphore rw = 1;
int count = 0;

读者和写者的实现

image-20220912210020502

出现的问题：

如果有两个读进程；两个读进程并发执行。

读进程1：执行 if(count==0)成立。

读进程2：执行if(count==0)成立。

读进程1：执行P(rw)，共享文件被上锁。

读进程2：执行P(rw)，读进程2被阻塞。

原因：count变量的检查和赋值无法一气呵成！

image-20220912210843435

方法三

由于count变量的检查和赋值无法一气呵成！ 于是我们可以设置一个新的互斥变量 rCountMutex，用于保证对count变量的互斥访问

初始化信号量和变量

1
2
3
semaphore rw = 1;
int count = 0;
semaphore rCountMutex = 1;

读者和写者的实现

image-20220912211652420

哲学家就餐问题

__END__