用P,V操作解决进程同步问题的解题步骤(优化版)

蓝颜色是格外注意的

在这里插入图片描述

在这里插入图片描述
还有读读共享，读写互斥问题。
要背会四个模式，套用模式

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

例题讲解


1）生产者-消费者问题
一般意义的“生产者—消费者”问题：N个buffer，多个生产者，多个消费者，循环存取buffer。这就是一般意义的“生产者—消费者”问题。利用记录型信号量解决一般意义的“生产者—消费者”问题算法描述，请看教材。
说明：
（1）由于buffer有N个，而且buffer又是临界资源，因此，需要增加一个信号量mutex来实现对buffer的互斥访问，其初始值为1。需要特别强调的是，这种情况下，mutex不能省略。
（2）这种情况下，只要保证为不同的进程分配不同buffer，putdata和getdata操作是可以同时进行的，因此，对buffer的互斥访问不是发生在对buffer的存取操作上，而是发生在对buffer的分配上。








2）“哲学家进餐”问题
教材中解决哲学家进餐问题的算法有可能发生死锁，为避免死锁，可以采用以下三种策略：
策略一原理：至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。定义信号量count，只允许4个哲学家同时进餐，这样就能保证至少有一个哲学家可以就餐。
semaphore chopstick[5]={1，1，1，1，1};
semaphore count=4;
void philosopher(int i){
	while(true){
		think();
		wait(count); //请求进入房间进餐
		wait(chopstick[i]); //请求左手边的筷子
		wait(chopstick[(i+1)%5]); //请求右手边的筷子
		eat();
		signal(chopstick[(i+1)%5]); //释放右手边的筷子
		signal(chopstick[i]); //释放左手边的筷子
		signal(count); //退出房间释放信号量
	}
}



策略二原理：仅当哲学家的左右两支筷子都可用时，才允许他拿起筷子进餐。可以利用AND 型信号量机制实现，也可以利用信号量的保护机制实现。利用信号量的保护机制实现的思想是通过记录型信号量mutex对取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。描述如下：
semaphore mutex = 1 ;
semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int i){
	while(true){
		think();
		wait(mutex);
		wait(chopstick[(i+1)%5]);
		wait(chopstick[i]);
		signal(mutex);
		eat();
		signal(chopstick[(i+1)%5]);
		signal(chopstick[i]);
	}
}



策略三原理：规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号的哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子。即五个哲学家都竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。
semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int i){
	while(true){
		think();
		if(i%2 == 0){ //偶数哲学家，先右后左。
			wait (chopstick[(i + 1)%5]) ;
			wait (chopstick[i]) ;
			eat();
			signal (chopstick[(i + 1)%5]) ;
			signal (chopstick[i]) ;
		}
		else{ //奇数哲学家，先左后右。
			wait (chopstick[i]) ;
			wait (chopstick[(i + 1)%5]) ;
			eat();
			signal (chopstick[i]) ;
			signal (chopstick[(i + 1)%5]) ;
		}
	}
}









3）“读者—写者”问题的演变
从本质上讲，读者—写者问题要解决：读、读共享；写、写互斥；写、读互斥。有两种解决模式：
模式一，读者优先的“读者—写者”问题解决模式（算法描述请参考教材）：
①定义互斥信号量wmutex，实现写、写互斥和写、读互斥。
②定义整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程写，因此仅当Readcount=0，即无Reader进程在读时，Reader才需要执行Wait(wmutex)操作。若Wait(wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才需执行signal(wmutex)操作，以便让Write进程写。
③由于Readcount为多个读进程共享（修改），因此需要以互斥方式访问，为此，需要定义互斥信号量rmutex，保证读进程间互斥访问Readcount。
说明：在读者—写者问题中，实现“读、读共享”是有一定难度的，请掌握该模式（由②和③构成）。
模式二，写者优先的“读者—写者”问题解决模式，算法描述如下：
设3个信号量：
rmutex --- 读互斥信号量，初值为1；
wmutex --- 写互斥信号量，初值为1；
s --- 用于在写进程到达后封锁后续的读者，初值为1；
count --- 共享变量，用于记录当前正在读文件的读者数目，初值为0；
semaphore rmutex=1, wmutex=1, s=1;
int count=0;
main() 
{
	Cobegin
	Reader();
	Writer();
	Coend
}
	Reader(){
		While(1){
			P(s);  
			P(rmutex);
			If (count==0) P(wmutex);  /*当第1个读者读文件时，阻止写者写*/
			count++
			V(rmutex);
			V(s);
			读文件；
			P(rmutex);
			count--;
			If (count==0) V(wmutex);  /*当最后1个读者读完文件时，允许写者写*/
			V(rmutex);
		}
	}
	Writer(){
		While(1){
			P(s);
			P(wmutex);
			写文件；
			V(wmutex);
			V(s);
		}
	}
}





例题解析
【例1】 桌上有1空盘，允许存放1个水果。爸爸向盘中放苹果，也可以向盘中放桔子。儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放1个水果供吃者取用。请用Wait()、Signal()原语实现爸爸、儿子、女儿三个并发进程的同步。
【南京大学2000】
【分析】这是复杂情况的“生产者—消费者”问题，既有同步又有互斥。爸爸进程与儿子进程、女儿进程需要同步，儿子进程与女儿进程需要互斥。设置4个信号量S（盘子是否为空，初值为1）、So（盘中是否有桔子，初值为0）、Sa（盘中是否有苹果，初值为0）和mutex（用于对盘子的互斥访问，初值为1）。由于只有一个盘子（相当于只有一个buffer），对盘子的互斥访问发生在对盘子的存取操作上，S、So和Sa就可以保证对盘子的互斥操作了，故mutex也可以省略。
解：设三个信号量：
S --- 盘子是否为空，初值为1；
So --- 盘中是否有桔子，初值为0；
Sa --- 盘中是否有苹果，初值为0；

Semaphore S=1, So=0, Sa=0;
Main() {
	Cobegin
	Father();
	Son();
	Daughter();
	Coend
}
Father() {
	While(1)  {
	Wait(S);   将水果放入盘中；
	If  (放入的是桔子)  Signal(So);
	Else   Signal(Sa);
	}
}
Son() {
	While(1)  {
	Wait(So);   从盘中取出桔子；Signal(S); 吃桔子；
	}
}
Daughter() {
	While(1)  {
	Wait(Sa);   从盘中取出苹果；Signal(S); 吃苹果；
	}
}



【例2】 如图1所示，有多个PUT操作同时向Buff1放数据，有一个MOVE操作不断地将Buff1的数据移到Buff2，有多个GET操作不断地从Buff2中将数据取走。Buff1的容量为m，Buff2的容量是n，PUT、MOVE、GET每次操作一个数据，在操作的过程中要保证数据不丢失。试用P、V原语协调PUT、MOVE的操作，并说明每个信号量的含义和初值。
 
图1  进程操作图
【分析】这里存在两个一般意义的“生产者—消费者”问题，PUT（生产者）与MOVE（消费者）之间，需要设置三个信号量；MOVE（生产者）与GET（消费者）之间，需要设置三个信号量。PUT进程套用生产者进程即可，MOVE进程只有在Buff1有新数据且Buff2有空闲区的时候才移动数据，GET进程套用消费者进程即可。
答案：设置6个信号量full1、empty1、B-M1、full2、empty2、B-M2，它们的含义和初值如下：
1)	full1表示Buff1是否有数据，初值为0；
2)	empty1表示Buff1有空间，初值为m；
3)	B-M1表示Buff1是否可操作，初值为1；
4)	Full2表示Buff2是否有数据，初值为0；
5)	Empty2表示Buff2有空间，初值为n；
6)	B-M2表示Buff2是否可操作，初值为1；
<PUT类进程>
 {
	repeat
	P(empty1)；  /*判断Buff1是否有空间，没有则等待 */     
	P(B-M1)；   /*是否可操作Buff1*/
	PUT；                 
	V(B-M1)；   /*设置Buff1可操作标志 */               
	V(full1)；    /*设置Buff1有数据的标志 */ 
	until false 
}
<MOVE类进程>
 {
	repeat
	P(full1)；    /*判断Buff1是否有数据，没有则等待*/
	P(empty2)；  /*判断Buff2是否有空间，没有则等待*/      
	P(B-M1)；   /*是否可操作Buff1  */
	P(B-M2)；   /*是否可操作Buff2  */
	MOVE；                 
	V(B-M1)；   /*设置Buff1可操作标志*/  
	V(B-M2)；   /*设置Buff2可操作标志*/  
	V(empty1)；  /*设置Buff1有空间标志*/             
	V(full2)；    /*设置Buff2有数据标志*/ 
	until false 
}

<GET类进程>
           {
repeat
P(full2)；  /*判断Buff2是否有数据，没有则等待 */     
P(B-M2)；   /*是否可操作Buff2*/
GET；                 
V(B-M2)；   /*设置Buff2可操作标志 */               
V(empty2)；    /*设置Buff2有空间的标志 */ 
until false
 
【例3】（8分）某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用，当营业员空闲时，通过叫号选取1位顾客，并为其服务。顾客和营业员的活动过程描述如下：
cobegin
{
   process 顾客i
   {
      从取号机获得一个号码；
      等待叫号；
      获得服务；
   }

   process 营业员
   {
      while （TRUE）
         {
            叫号；
            为顾客服务；
         }
   }
} coend

请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程中的护持与同步。要求写出完整的过程，说明信号量的含义并赋初值。               【全国统考 2011】

解：
semaphore  emptySeats:=10       //空闲座位数
semaphore  fullSeats:=0          //已占座位数
semaphore  mutex:=1            //顾客使用取号机互斥信号量

cobegin
{
   	process 顾客i
   	{
   		wait(emptySeats);        //获取一个座位
      	wait(mutex);             //占用取号机取号
		从取号机获得一个号码；
		signal(mutex)            //释放取号机
      	signal(fullSeats)         //座位上增加一个顾客
		等待叫号；
		signal(emptySeats);      //释放一个座位
      获得服务；
      
   	}

   process 营业员
   {
      while （TRUE）
         {
            wait(fullSeats);        //座位上减少一个顾客
            叫号；
            为顾客服务；
         }
   }
} coend
讲评：此题为生产者-消费者问题的翻版。课本上的哲学家进餐问题、生产者–消费者问题、读者–写者问题为基础性的进程同步问题，需要认真真正掌握，以此为基础用于解决其他进程同步问题。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/96390.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

js删除字符串中的指定字符串

js删除字符串中的指定字符串

1. 使用 replace() 方法 replace() 将字符串中的指定子字符串替换为新的字符串。 如果删除指定的子字符串&#xff0c;可以将它替换为空字符串。 var str "Hello, World!";var substringToRemove "World";var newStr str.replace(substringToRemove, &q…
阅读更多...
Ansible学习笔记8

Ansible学习笔记8

group模块&#xff1a; 创建一个group组&#xff1a; [rootlocalhost ~]# ansible group1 -m group -a "nameaaa gid5000" 192.168.17.105 | CHANGED > {"ansible_facts": {"discovered_interpreter_python": "/usr/bin/python"}…
阅读更多...
亚马逊云科技 云技能孵化营——我的云技能之旅

亚马逊云科技 云技能孵化营——我的云技能之旅

文章目录 每日一句正能量前言活动流程后记 每日一句正能量 不能在已经获得足够多的成功时&#xff0c;还对自己的能力保持怀疑&#xff0c;露出自信的微笑&#xff0c;走出自信的步伐&#xff0c;做一个自信的人&#xff01; 前言 亚马逊云科技 (Amazon Web Services) 是全球云…
阅读更多...
【论文笔记】最近看的时空数据挖掘综述整理8.27

【论文笔记】最近看的时空数据挖掘综述整理8.27

Deep Learning for Spatio-Temporal Data Mining: A Survey 被引用次数&#xff1a;392 [Submitted on 11 Jun 2019 (v1), last revised 24 Jun 2019 (this version, v2)] 主要内容&#xff1a; 该论文是一篇关于深度学习在时空数据挖掘中的应用的综述。论文首先介绍了时空数…
阅读更多...
从传统软件开发到云原生转型：大数据和AI如何引领软件开发的新趋势

从传统软件开发到云原生转型：大数据和AI如何引领软件开发的新趋势

文章目录 **1. 数据驱动的开发&#xff1a;****2. 智能化的用户体验&#xff1a;****3. 云原生的可扩展性&#xff1a;****4. 实时处理和决策&#xff1a;****5. 自动化和效率提升&#xff1a;****6. 持续集成和交付的加速&#xff1a;****7. 数据安全和隐私&#xff1a;****8.…
阅读更多...
1427205-93-3|Fmoc-Ser(Ac4Manα1-2Ac3Manα1-2Ac3Manα)-OH是指糖类与氨基酸通过糖苷键连接而成的化合物

1427205-93-3|Fmoc-Ser(Ac4Manα1-2Ac3Manα1-2Ac3Manα)-OH是指糖类与氨基酸通过糖苷键连接而成的化合物

糖基化氨基酸是指糖类与氨基酸通过糖苷键连接而成的化合物。这种糖苷键的形成是由于糖类的末端羟基与氨基酸的氨基之间发生脱水缩合反应糖。基化氨基酸具有多种生物学功能&#xff0c;如作为酶、激素和抗体的成分&#xff0c;参与细胞识别和信息传递等。 在生物体内&#xff0c…
阅读更多...
【C++小项目】实现一个日期计算器

【C++小项目】实现一个日期计算器

目录 Ⅰ. 引入 Ⅱ. 列轮廓 Ⅲ. 功能的实现 构造函数 Print 判断是否相等 | ! ➡️: ➡️!: 判断大小 > | > | < | < ➡️>&#xff1a; ➡️<&#xff1a; ➡️>&#xff1a; ➡️<&#xff1a; 加减天数 | | - | - ➡️&#xff1a;…
阅读更多...
Java CompletableFuture 详细使用教程与实践

Java CompletableFuture 详细使用教程与实践

一、Java CompletableFuture 详细使用教程 Java 8引入了一种强大的异步编程工具&#xff1a;CompletableFuture。它提供了一种处理异步计算的方式&#xff0c;使得你可以在计算完成时获取结果&#xff0c;或者将一个或多个 CompletableFuture 的结果组合在一起。本部分将详细解…
阅读更多...
ABeam×Startup | 德硕管理咨询（深圳）创新研究团队拜访微漾创客空间

ABeam×Startup | 德硕管理咨询（深圳）创新研究团队拜访微漾创客空间

近日&#xff0c;德硕管理咨询&#xff08;深圳&#xff09;&#xff08;以下简称&#xff1a;“ABeam-SZ”&#xff09;创新研究团队前往微漾创客空间&#xff08;以下简称&#xff1a;微漾&#xff09;拜访参观&#xff0c;并展开合作交流。会议上&#xff0c;双方相互介绍了…
阅读更多...
C语言 - 结构体、结构体数组、结构体指针和结构体嵌套

C语言 - 结构体、结构体数组、结构体指针和结构体嵌套

结构体的意义 问题&#xff1a;学籍管理需要每个学生的下列数据&#xff1a;学号、姓名、性别、年龄、分数&#xff0c;请用 C 语言程序存储并处理一组学生的学籍。 单个学生学籍的数据结构&#xff1a; 学号&#xff08;num&#xff09;&#xff1a; int 型姓名&#xff08;…
阅读更多...
Dimensions网站——一个链接研究知识系统

Dimensions网站——一个链接研究知识系统

Dimensions网站——一个链接研究知识系统 一、Dimensions网站简介 Dimensions 是一个链接的研究知识系统&#xff0c;它重新构想了发现和研究的获取。Dimensions 由 Digital Science 与全球 100 多个领先研究组织合作开发&#xff0c;汇集了资助、出版物、引文、替代指标、临…
阅读更多...
如何在不使用任何软件的情况下将 PDF 转换为 Excel

如何在不使用任何软件的情况下将 PDF 转换为 Excel

通常&#xff0c;您可能会遇到这样的情况&#xff1a;您需要的数据不在 Excel 工作表中&#xff0c;而是以数据表形式出现在 PDF 文件中。为了将此数据放入 Excel 工作表中&#xff0c;如果您尝试将数字复制并粘贴到电子表格中&#xff0c;则列/行将无法正确复制和对齐。因此&a…
阅读更多...
【数据结构】如何用栈实现队列？图文解析（LeetCode）

【数据结构】如何用栈实现队列？图文解析（LeetCode）

LeetCode链接&#xff1a;232. 用栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 注&#xff1a;本文默认读者已掌握栈与队列的基本操作 可以看这篇文章熟悉知识点&#xff1a;【数据结构】栈与队列_字节连结的博客-CSDN博客 目录 做题思路 代码实现 1. MyQueue 2. …
阅读更多...
选择排序：用C语言打造高效的排序算法

选择排序：用C语言打造高效的排序算法

本篇博客会讲解如何使用C语言实现选择排序。 下面我来画图讲解选择排序的思路。 假设有一个数组&#xff0c;其初始状态如下&#xff0c;我们想把这个数组排成升序。 首先我们标明范围&#xff0c;即[begin, end]&#xff0c;一开始begin(b)和end(e)分别表示数组的第一个位置…
阅读更多...
运维Shell脚本小试牛刀(一)

运维Shell脚本小试牛刀(一)

运维Shell脚本小试牛刀(一) 运维Shell脚本小试牛刀(二) 运维Shell脚本小试牛刀(三)::$(cd $(dirname $0)&#xff1b; pwd)命令详解 一: Shell中循环剖析 for 循环....... #!/bin/bash - # # # # FILE: countloop.sh # …
阅读更多...
【ES】笔记-集合介绍与API

【ES】笔记-集合介绍与API

集合是一种不允许值重复的顺序数据结构。 通过集合我们可以进行并集、交集、差集等数学运算&#xff0c; 还会更深入的理解如何使用 ECMAScript 2015(ES2015)原生的 Set 类。 构建数据集合 集合是由一组无序且唯一(即不能重复)的项组成的。该数据结构使用了与有限集合相同的数…
阅读更多...
文件修改时间能改吗？怎么改？

文件修改时间能改吗？怎么改？

文件修改时间能改吗&#xff1f;怎么改&#xff1f;修改时间是每个电脑文件具备的一个属性&#xff0c;它代表了这个电脑文件最后一次的修改时间&#xff0c;是电脑系统自动赋予文件的&#xff0c;相信大家都应该知道。我们右击鼠标某个文件&#xff0c;然后点击弹出菜单里面的…
阅读更多...
ELK安装、部署、调试（一）设计规划及准备

ELK安装、部署、调试（一）设计规划及准备

一、整体规划如图&#xff1a; 【filebeat】 需要收集日志的服务器&#xff0c;安装filebeat软件&#xff0c;用于收集日志。logstash也可以收集日志&#xff0c;但是占用的系统资源过大&#xff0c;所以使用了filebeat来收集日志。 【kafka】 接收filebeat的日志&#xff…
阅读更多...
【Java笔记】分布式id生成-雪花算法

【Java笔记】分布式id生成-雪花算法

随着业务的增长&#xff0c;有些表可能要占用很大的物理存储空间&#xff0c;为了解决该问题&#xff0c;后期使用数据库分片技术。将一个数据库进行拆分&#xff0c;通过数据库中间件连接。如果数据库中该表选用ID自增策略&#xff0c;则可能产生重复的ID&#xff0c;此时应该…
阅读更多...
【硬件设计】硬件学习笔记一--元器件的介绍与选型

【硬件设计】硬件学习笔记一--元器件的介绍与选型

硬件学习笔记一--元器件的选型 一、电阻1.1 电阻的分类1.2 电阻的选型 二、电容2.1 陶瓷电容2.2 钽电容2.3 铝电解电容2.4 电容选型 三、电感3.1 定义与介绍3.2 电感的分类3.3 电感的参数 四、磁珠4.1 磁珠的介绍4.2 磁珠的参数 五、二极管5.1 定义5.2 稳压管5.3 肖特基二极管5…
阅读更多...
最新文章

Copyright @ 2022~2023