操作系统之经典同步问题(司机售票员、文件打印、多个生产者消费者、放水果吃水果、读者优先、写者优先、哲学家死锁问题)

本文主要是介绍操作系统之经典同步问题(司机售票员、文件打印、多个生产者消费者、放水果吃水果、读者优先、写者优先、哲学家死锁问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

d10de045a834436e893f83586f10d193.png

🔥博客主页:真的睡不醒

🚀系列专栏:深度学习环境搭建、环境配置问题解决、自然语言处理、语音信号处理、项目开发

💘每日语录:闲看花开,静待花落,冷暖自知,干净如始

🎉感谢大家点赞👍收藏⭐指正✍️

32d40f81c51e4cbfa72ea9bd6b556623.png

目录

一、司机与售票员进程同步问题

二、PA、PB、PC合作解决文件打印问题

三、多个生产者和多个消费者问题

四、放水果吃水果问题

五、读者写者问题

六、哲学家吃饭问题


一、司机与售票员进程同步问题

问题描述:在公共汽车上,司机和售票员的工作流程如图所示。为保证乘客的安全,司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。

065c0c7b224f4a65a925d2dc5fcb781b.png

问题分析:

        1、在该问题中,司机和售票员不存在资源的争夺

        2、司机和售票员为同步关系

        3、司机启动车辆前需要收到已经关门的信号

        4、售票员开车门前需要收到车已经到站的信号

所以需要设置关门信号量door=0,停车信号量stop=0。

具体代码如下:

Semaphore door=0;
Semaphore stop=0;
Void driver(){while(1){wait(door);     // 等待关门信号启动车辆;正常行车;到站停车;        signal(stop);    // 停车信号}
}Void conductor(){while(1){关车门;signal(door);    // 关门信号售票;wait(stop);      // 等待停车信号开车门;}
}

二、PA、PB、PC合作解决文件打印问题

问题描述:有三个进程PA、PB和PC协作解决文件打印问题。PA将文件记录从磁盘读入内存的缓冲区1,每执行一次读一个记录;PB将缓冲区1的内容复制到缓冲区2中,每执行一次复制一个记录:PC将缓冲区2的内容打印出来,每执行一次打印一个记录。缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。

问题分析:

        1、有两个临界资源,分别是缓冲区1和缓冲区2

        2、PA和PB互斥访问缓冲区1

        3、PB和PC互斥访问缓冲区2

        4、PA将文件记录从磁盘读入缓冲区1后,如果PB没有拿走这个记录,那么PA则不能再

             执行读入操作,PB和PC也是如此。

所以需要设置四个互斥信号量:

        1、empty1、empty2,分别代表缓冲区1和缓冲区2是否为空,初值为1,代表空。

        2、full1、full2,分别代表缓冲区1和缓冲区2是否有文件记录,初值为0,代表没有。

代码如下:

Semaphore emptyA = 1;
Semaphore emptyB = 1;
Semaphore fullA = 0;
Semaphore fullB = 0;
PA(){while(1){读取磁盘一个记录; wait(emptyA);	// 缓冲区1是否为空 将记录存入缓冲区1;signal(fullA); 	// 将缓冲区1标记为有数据 }
}PB(){while(1){wait(fullA);	读出缓冲区1的记录;signal(emptyA);	// 将缓冲区1标记为空 wait(emptyB);	// 缓冲区2是否空 将记录存入缓冲区2;signal(fullB); 	// 缓冲区2有数据 }
}
PC(){while(1){wait(fullB);	// 缓冲区2是否有数据 读出缓冲区2的记录;signal(emptyB);  // 将缓冲区2标记为空 打印; }
}main(){cobegin();PA();PB();PC();coend();
}

三、多个生产者和多个消费者问题

系统中有多个生产者进程和多个消费者进程,共享一个能存放1000件产品的环形缓冲区(初始为空),当缓冲区未满时,生产者进程可以放入其生产的一件产品,否则等待;当缓冲区未空时,消费者进程可以从缓冲区取走一件产品,否则等待。要求一个消费者进程从缓冲区连续取出10件产品后,其他消费者进程才可以取产品。请使用信号量P,V(wait(),signal())操作实现进程间的互斥与同步,要求写出完整的过程,并说明所用信号量的含义和初值。

问题分析:

        1、典型的生产者消费者问题,只需要在模型上加上一个信号量,来保证一个消费者能

             够连续取10件产品。

        2、设置四个变量mutex1,mutex2,empty,full。

             mutex1控制一个消费者进程在一个周期内(10次)对缓冲区的访问;

             mutex2控制生产者和消费者互斥对缓冲区的访问;

             empty表缓冲区空位数,初值1000;

             full表缓冲区产品数。

代码如下:

Semaphore mutex1 = 1;
Semaphore mutex2 = 1;
Semaphore empty = 1000;
Semaphore full = 0;
producer(){while(1){生产一个产品;P(empty); // 缓冲区是否还有空位P(mutex2);  // 互斥访问缓冲区将产品放入缓冲区;V(mutex2);V(full); }
} 
consumer(){while(1){P(mutex1) // 连续拿走10次for(int i=0; i<10; i++){P(full);P(mutex2); // 互斥访问取走一个产品;V(mutex2); V(empty);	// 缓冲区空间+1	} }
}

四、放水果吃水果问题

问题描述:桌子上有一只盘子,每次只能向其中放一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等吃盘子中的橘子,女儿专等吃盘子中的苹果。只有盘子为空时,爸爸或妈妈就可向盘子中放一个水果;仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出。请使用信号量P,V(wait(),signal())操作实现进程间的互斥与同步,要求写出完整的过程,并说明所用信号量的含义和初值。

问题分析:

        1、由每次只能放一个水果可知,爸爸和妈妈是互斥关系

        2、爸爸和女儿、妈妈和儿子是同步关系,且这两对进程必须连起来

        3、儿子和女儿之间没有同步互斥关系,不能并发执行

代码如下:

Semaphore plate = 1; 
Semaphore orange = 0;
Semaphore apple = 0;
father(){while(1){P(plate);放苹果;V(apple); // 可以吃苹果 }
}
mother(){while(1){P(plate);放橘子;V(orange);  // 可以吃橘子 }
}
daughter(){while(1){P(apple);吃苹果;V(plate); // 可以放水果 }
} 
son(){while(1){P(orange);吃橘子;V(plate); // 可以放水果 }
} 

五、读者写者问题

读者优先

问题分析:

        1、写者在进行写操作之前,应让已有的读者和写者全部退出;

        2、写者的写操作未完成前,不允许其他读者和写者进行操作;

        3、可以多个读者同时进行读操作;

        4、只允许一个写者进行写操作;

        关键:读者必须实现和写者互斥的同时和其他读者同步

       

信号量设置:

        1、count 用来记录当前读者的人数,同时需要用mutex来实现对count的互斥访问,

             count 初值为0,mutex初值为1;

        2、同时需要设置 rw 来实现读者写者对文件的互斥访问。

代码如下:

Semaphore rw=1;
Semaphore  mutex=1;
Semaphore  count=0;
writer(){while(1){P(rw);write;V(rw);}
}
reader(){while(1){P(mutex);if(count == 0){P(rw);}count++;V(mutex);read;p(mutex);count--;if(count == 0){V(rw);V(mutex);}}
}

写者优先

问题描述:经典的读者-写者问题通常采用读者优先原则实现读者和写者进程之间对文件的互斥访问,这样会导致写者处于较长时间的“饥饿”状态,请采用写者优先原则实现,即当读者和写者进程并发访问文件时能按照读者和写者先来先访问的原则运行。

问题分析:

        1、读进程在读共享文件时,如果有写进程的访问,则应禁止后续读者访问进程的请

             求,等到当前读者阅读完毕,立刻让写进程执行,只有无写进程执行时,才允许

             读进程继续执行;

        2、要想实现写者优先,只需要在原代码的基础上,读者和写者再加一个互斥变量w,

             来实现写者优先;

        3、写者在进行写之前需要确保当前没有写者在写文件,并且没有读者在读文件。

信号量设置:

        1、互斥变量w,实现写者优先;

        2、count 用来记录当前读者的数量;

        3、mutex用来实现对count的互斥访问;

        4、rw用来实现读者写者对文件的互斥访问。

Semaphore rw=1;
Semaphore mutex=1;
Semaphore count=0;
Semaphore W=1;
writer(){while(1){P(W);P(rw);write;V(rw);v(W);}
}
reader(){while(1){P(W);P(mutex);if(count == 0){P(rw);}count++;V(mutex);V(W);read;p(mutex);count--;if(count == 0){V(rw);V(mutex);}}
}

六、哲学家吃饭问题

试用记录型信号量写出一个不会死锁的哲学家进餐问题的算法。

问题分析:为防止死锁发生,可以增加一些限制条件。

如当一名哲学家左右两边的筷子都可用,时才允许他抓筷子。

信号量设置:

        1、chopsticks[5] = {1, 1, 1, 1, 1};

        2、mutex = 1,确保左右都有筷子;

代码如下:

Semaphore chopsticks[5] = {1, 1, 1, 1, 1};
Semaphore mutex = 1;
P(){do{P(mutex);P(chopsticks[i]);P(chopsticks[(i+1)%5]);V(mutex);吃饭;V(chopsticks[i]);V(chopsticks[(i+1)%5]);思考;}while(1)
}

a40e8f62caeb48779e90c900e5ca68ca.png

这篇关于操作系统之经典同步问题(司机售票员、文件打印、多个生产者消费者、放水果吃水果、读者优先、写者优先、哲学家死锁问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/481335

相关文章

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s