跳至主要內容

3.同步与互斥

𝓳𝓭𝔂𝓼𝔂𝓪大约 15 分钟

同步和互斥的基本概念

临界资源

一次仅允许一个进程使用的资源称为临界资源，访问临界资源的那段代码称为临界区

同步

互斥

实现临界区互斥的基本方法

2.3.2_1进程互斥的软件实现方法
00:02
2.3.2_1进程互斥的软件实现方法

软件实现方法

单标志法

该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号，即若turn=0,则允许P0P_{0}进程进入临界区，退出临界区的时候更改turn的值，交替进入临界区，违反空闲让进

双标志法先检查

该算法的基本思想是在每个进程访问临界区资源之前，先查看临界资源是否正被访问，若正被访问，该进程需等待，设置一个布尔型数组flag[]flag[]，记录进程PiP_{i}是否进入临界区，违反了忙则等待

双标志法后检查

违背了空闲让进和有限等待原则，会因各进程都长期无法访问临界资源而产生饥饿现象

Peterson算法

结合单标志和双标志法后检查，没有遵循让权等待

硬件方法实现

中断屏蔽方法

优缺点

优点：简单、高效

缺点：不适用于多处理机：只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

硬件指令方法

TestAndSet指令（TS或TSL），不允许被中断，一气呵成
Swap指令（exchange指令，XCHG）

实现简单，适合多处理机，但是不满足让权等待

信号量

【课件】2.3.4_1信号量机制

整形信号量

整型信号量被定义为一个用于表示资源数目的整型量SS，在整型信号量机制中的wait操作，只要信号量S≤0S\leq0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

记录型信号量

除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L,用于链接所有等待该资源的进程。
image.png

【课件】2.3.4_2用信号量实现进程互斥、同步、前驱关系
2.3.4_2用信号量实现进程互斥、同步、前驱关系
10:21

信号量实现同步

要让各并发进程按要求有序地推进

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

信号量实现互斥

  1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区)
  2. 设置互斥信号量mutex，初值为1，表示的是同时时刻只允许一个进程进入临界区
  3. 在进入区P(mutex)——申请资源
  4. 在退出区V(mutex)——释放资源

提示

对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。

管程

条件定义

管程是为了简化pv操作解决同步和互斥，管程实现起来更方便，其组成如下：

  • 管程的名称
  • 局部于管程内部的共享数据结构说明
  • 对该数据结构进行操作的一组过程（或函数）
  • 对局部于管程内部的共享数据设置初始值的语句
    基本特征：
  • 局部于管程的数据只能被局部于管程的过程所访问；
  • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据：
  • 每次仅允许一个进程在管程内执行某个内部过程。

条件变量

当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。为此，将阻塞原因定义为条件变量condition。条件变量只能进行两种操作，即wait和signal。

  • 当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程。
  • x对应的条件发生了变化，则调用x.signal,唤醒一个因x条件而阻塞的进程。

条件变量和信号量的比较

  • 相似点：条件变量的wait/signal操作类似于信号量的PV操作，可以实现进程的阻塞/唤醒。
  • 不同点：条件变量是“没有值”的，仅实现了“排队等待”功能；而信号量是“有值”的，
    信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

经典同步问题

生产者-消费者问题

2.3.6_1生产者-消费者问题
07:58

问题描述

一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区,只有缓沖区没满时,生产者才能把消息放入缓冲区,否则必须等待;只有缓冲区不空时,消费者才能从中取出消息,否则必领等待。由于缓冲区是临界资源;它只允许一个生产者放入消息,或一个消费者从中取出消息。

image.png
image.png

注意

实现互斥的p操作必须要在实现同步的p之后，不能颠倒，颠倒会导致死锁，v操作可以交换顺序

多生产者-多消费者

问题描述

桌子上有一个盘子,每次只能向其中放入一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等吃盘子中的橘子,女儿专等吃盘子中的苹果。只有盘子为空时, 爸爸或妈妈才可向盘子中放一个水果;仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出

image.png
image.png

提示

  • 即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象
  • 原因在于：本题中的缓冲区大小为1，在任何时刻，apple、 orange、 plate 三个同步信
    号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区
  • 如果缓冲区大小大于1，就必须专门设置一个互斥信号量 mutex 来保证互斥访问缓冲区

读者-写者问题

👉视频讲解-2.3.6_4读者-写者问题open in new window

问题描述

有读者和写者两组并发进程,共享一个文件,当两个或以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:

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

1.实现对共享文件的互斥访问

semaphore rw=1;

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

reader(){
	while(1){
		P(rw);
		读文件...
		V(rw);
	}
}

注意

会导致读者与读者之间不能同时共享文件

2.记录读者数量

int count = 0;

提示

  • 由第一个读进程负责读之前加锁
  • 由最后一个读进程读完解锁

可实现读者之间共享文件

reader(){
	while(1){
		if(count == 0)
			P(rw);
		count++;
		读文件...
		count--;
		if(count == 0)
			V(rw);
	}
}


 
 



 
 


注意

  • 若两个读者进程并发进行，则count=0时两个进程都满足加锁条件，则其中一个加锁后，第二个进程会被阻塞
  • 原因在于对count变量的检查和赋值无法一气呵成

3.对count变量的互斥访问

semaphore mutex = 1;

reader(){
	while(1){
		P(mutex)
		if(count == 0)
			P(rw);
		count++;
		V(mutex);
		读文件...
		P(mutex);
		count--;
		if(count == 0)
			V(rw);
		V(mutex);
	}
}


 



 

 



 


注意

只要读进程还在读，写进程就会一直阻塞等待，写进程饿死，这种算法中，读进程是优先的

4.实现写优先

semaphore w = 1;

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


 



 


reader(){
	while(1){
		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. 读者1->读者2
    • 读者1进行V(w)操作后，读者2便可进入，由于V(w)操作在读文件之前，故可以同时读文件
  2. 写者1->写者2
    • 由于V(w)操作在写文件之后，故可实现互斥访问，
  3. 写者1-＞读者1
    • 写完文件才能读文件
  4. 读者1->写者1->读者2
    • 读者1在 V(w)后紧接着写者1会进行P(w)，随之由于读者1还未进行V(rw)，写者1会阻塞在P(rw)，同时由于写者1进行P(w)，后面的读者2会被阻塞在P(w),从而可以保证顺序执行
  5. 写者1->读者1->写者2
    • 写者1写完读者1才能读，且读完写者2才能写

由第五种情况可以看出，在这种算法中，连续进入的多个读者可以同时读文件：写者和其他进程不能
同时访问文件：写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则
有的书上把这种算法称为“读写公平法”

哲学家进餐问题

👉视频讲解-2.3.6_5哲学家进餐问题open in new window

问题描述

一张圆桌边上坐着5名哲学家,每两名哲学家之问的桌上摆一根筷子,两根筷子中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿时, 才试图拿起左、右两根筷子(一根一根地拿起)。若筷子己在他人手上,则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐,进餐完毕后,放下筷子继续思考。

注意

为防止死锁发生,可对哲学家进程施加一些限制条件:

  • 比如至多允许4 名哲学家同时进餐;
  • 仅当一名哲学家左右两边的筷子都可用时,才允许他抓起筷子;
  • 对哲学家顺序编号,要求奇数号哲学家先拿左边的筷子,然后拿右边的筷子,而偶数号哲学家刚好相反。

假设采用第二种方法,当一名哲学家左右两边的筷子都可用时,才允许他抓起筷子[2]。

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1; //互斥地取筷子
Pi(){ //i号哲学家的进程
	while(1){
		P (mutex)
		P (chopstick[i]);
		P (chopstick[(i+1)%5]);
		V (mutex);
		吃饭...
		V (chopstick[i]); //放左
		V (chopstick[(i+1)%5]）//放右
		思考..
	}
}





 


 





吸烟者问题

问题描述

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草,第二个拥有纸,第三个拥有胶水。供应者进程无限地提供三种材料,供应者每次将两种材料放到桌子上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者一个信号告诉己完成,此时供应者就会将另外两种材料放到桌上,如此重复(让三个抽烟者轮流地抽烟)。

image.png
image.png

  1. 这个初值具体问题具体分析，就像生产者和消费者的同步信号量empty和full初值 ↩︎

  2. 并且这个操作是一气呵成的 ↩︎

默认页脚
Copyright © 2023 𝓳𝓭𝔂𝓼𝔂𝓪