操作系统期末复习大题---经典进程的同步问题

目录

一、经典进程的同步问题

1. 利用记录型信号量解决生产者—消费者问题

执行流程：

”生产者-消费者”问题模型代码框架如下： 

 注意：

小结：

复习典型例题：

解答：

2. 利用AND信号量解决生产者——消费者问题

代码框架：

生产者消费者模型举例

例一、

例二、 

例3：父亲-母亲-儿子-女儿两个苹果或桔子

例4

练一练（2009年考研真题）

题目：

分析：考虑题目中的互斥和同步问题

答案：

 例题：

分析：

解答

练一练（2014年真题）

2.5.2哲学家进餐问题

 学以致用（2019真题）

2.5.3  读者-写者问题

 补充：吸烟者问题

一、经典进程的同步问题

重点内容：

•掌握“生产者-消费者”问题模型
•掌握“哲学家进餐”问题模型
•掌握“读者-写者”问题模型

1. 利用记录型信号量解决生产者—消费者问题

执行流程：

”生产者-消费者”问题模型代码框架如下： 
semaphone mutex=1,empty=n,full=0;
item buffer[n];
int in=0, out = 0;
main(){cobegin{ producer{  produce an item nextp;wait(empty);wait(mutex);buffer(in)=nextp;in=(in+1) % n;signal(mutex);   //释放使用权signal(full);    //唤醒消费者}consumer{wait(full);wait(mutex);nextc=buffer(out);out= (out+1) % n;signal(mutex);    //释放使用权signal(empty);    //唤醒生产者consume the item in nextc;}}coend
}
 注意：

在有多个信号量同时存在的情况下，WAIT操作往往是不能颠倒顺序的，必须先对资源信号量进行WAIT操作，再对互斥信号量进行WAIT操作，这样可以在占用共享资源的访问权时保证有资源可用，不然会导致产生占用使用权而无资源可用的“死等”现象。

小结：

复习典型例题：

解答：

2. 利用AND信号量解决生产者——消费者问题

代码框架：
semaphone mutex=1,empty=n,full=0;
item buffer[n];
int in=0, out = 0;
main(){cobegin{ producer{  produce an item nextp;wait(empty,mutex);buffer(in)=nextp;in=(in+1) % n;signal(mutex,full);}consumer{wait(full,mutex);nextc=buffer(out);out= (out+1) % n;signal(mutex,empty); consume the item in nextc;}}coend
}

问题推广：

                  一组生产者，一组消费者，公用 n个环形缓冲区

思考：如何高效的存取，生产者之间公用一个in指针，消费者之间公用一个out指针，如何设置信号量？

empty：表示缓冲区是否为空，初值为n;      full:表示缓冲区是否为满，初值为0。

mutex1：生产者之间的互斥信号量，初值为1;mutex2：消费者之间的互斥信号量，初值为1。

设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。

第三种情况，可以理解成有多间牛奶生产厂家，如蒙牛，达能，光明等，消费者也不只小明一人，有许许多多消费者。不同的牛奶生产厂家生产的商品可以放在不同的零售分店中销售，而不同的消费者可以去不同的分店中购买。当某一分店已放满某个厂家的商品时，下一个厂家只能把商品放在下一间分店。所以在这种情况中，生产者与消费者存在同步关系，而且各个生产者之间、各个消费者之间存在互斥关系,他们必须互斥地访问缓冲区。

生产者消费者模型举例

例一、

分析：爸爸和儿子两个进程相互制约，爸爸进程执行完即往盘中放入苹果后，儿子进程才能执行即吃苹果。因此该问题为进程间的同步问题。 

 

例二、 

例2. 桌上有一空盘，允许存放一只水果，爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用。

   请用Wait/Signal原语实现爸爸、儿子、女儿三个并发进程的同步。

设置三个信号量：

Semaphore S=1;   //S 表示盘子是否为空；
Semaphore S1=0; //S1表示盘中是否有苹果；
Semaphore S2=0; //S2表示盘中是否有桔子；

此问题还可继续推广：父亲-母亲-儿子-女儿一个苹果或桔子 问题；父亲-母亲-儿子-女儿两个苹果或桔子 问题；

例3：父亲-母亲-儿子-女儿两个苹果或桔子

分析：盘子为互斥资源，因可以放2个水果，empty初值为2； 且需设置互斥信号量mutex=1

还可进一步推广：两个儿子，两个女儿的情况！

semaphore：s=2(可用位置);  s1=0(苹果数);  s2=0(桔子数);mutex=1;

爸爸：wait(s); wait(mutex);放苹果; signal(mutex); signal(s1);

妈妈：wait(s); wait(mutex); 放桔子; signal(mutex); signal(s2);

儿子：wait(s2); wait(mutex); 取桔子; signal(mutex); signal(s);

女儿：wait(s1); wait(mutex); 取苹果; signal(mutex); signal(s);

例4

例4：某幼儿园举行趣味活动，每两个小朋友一组。重复做如下活动：一个小朋友负责用一个小桶在A沙堆取沙子，然后倒入一大盆中，另一小朋友负责用一个小桶从大盆中取沙子倒入B沙堆。大盆最多能装10桶沙子，且在大盆中取沙子和倒沙子不能同时进行。试用信号量操作描述这两个小朋友的同步过程。

empty：表示大盆是否为空，初值为10。

full    ：表示大盆是否为满，初值为0。

mutex:  表示可否对大盆进行操作，初值为1.

解答：

练一练（2009年考研真题）

题目：

        三个进程P1、P2、P3互斥使用一个包含N个单元的缓冲区。P1每次用produe()产生一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步和互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。

分析：考虑题目中的互斥和同步问题
• 互斥问题：缓冲区只能互斥，设置互斥信号量 mutex ;
• 同步问题 :  P1 、 P2 因为奇数的放置和取用同步，设置信号量 odd ； P1 、 P3 因为偶数的放置与取用取得同步，设置同步信号量 even ； P1 、 P2 、 P3 因为共享缓冲区，设置同步信号量 empty.

信号量定义：

semaphore mutex=1;//缓冲区操作互斥信号量
semaphore odd=0,even=0;//奇数偶数同步信号量
semaphore empty=N;//空缓冲区个数

答案：

 例题：

某寺庙有小和尚、老和尚若干。

• 有一个水缸，由小和尚打水入缸供老和尚饮用。 水缸可容纳 10 桶水 。
• 水取自同一井中。 每次只能容纳一个桶取水 。 水桶总数为 3 个 。每次入、取水仅为一桶， 且不可同时进行 。
• 给出有关取水、入水的算法描述。

分析：

semaphore empty=10;// 表示缸中目前还能装多少桶水，初始时能装10桶水

semaphore full=0;// 表示缸中有多少桶水，初始时缸中没有水

semaphore buckets=3;// 表示有多少只空桶可用， 初值为3

semaphore mutex_well=1;// 用于实现对井的互斥操作

semaphore mutex_bigjar=1; // 用于实现对缸的互斥操作

解答

练一练（2014年真题）

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

分析：

semaphore empty=1000;//空缓冲区的个数
semaphore full=0;//缓冲区的产品数
semaphore mutex1=1;//控制消费者进程一个周期内互斥访问
semaphore muter2=1;//进程单次互斥访问临界区

解答：

2.5.2哲学家进餐问题

前面描述了多个进程竞争一个临界资源的情况及通用模板，那么，对于多个进程竞争多个临界资源的情况，又该如何描述呢？哲学家就餐问题就是对这类问题的一个抽象！

思考：如果同时拿起左筷子？

死锁解决方法：

 解决方法1：

 

解决方法2：

解决方法3：

 学以致用（2019真题）

有n（n>=3)位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有m（m>=1）个碗，每两位哲学家之间有1根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P、V操作(wait()、signal()操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义

   信号量bowl用于协调哲学家对碗的使用， bowl<n，确保不死锁，

即至少保证有一个人拿不到碗，那么就能保证至少有一个人能拿到左右的筷子。

     semaphone bowl=min(n-1,m);

  信号量chopsticks用于协调哲学家对筷子的使用，两个哲学家之间的筷子数量为1

    semaphone chopsticks[n]={1,1,...,1};

2.5.3  读者-写者问题

对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个。

  • “读－写”互斥，
  • “写－写”互斥，
  • "读－读"允许

 补充：吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉完成了，供应者就会放另外两种材料在桌上，这种过程一直重复（三个抽烟者轮流地抽烟）

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【React系列】Hook（二）高级使用

【React系列】Hook（二）高级使用

本文来自#React系列教程&#xff1a;https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) 一. Hook高级使用 1.1. useReducer 很多人看到useReducer的第一反应应该是redux的某个替代品&#xff0c;其实并不是…
阅读更多...
git rebase(变基)应用场景

git rebase(变基)应用场景

文章目录 git rebase(变基)应用场景1.git rebase -i HEAD~3 git rebase(变基)应用场景 使得提交记录变得简洁 现在我们模拟我们有多次提交记录&#xff0c;本地仓库有三条提交 整合成一条提交记录 1.git rebase -i HEAD~3 提交记录合并 HEAD~3合并三条记录 执行之后 然后把…
阅读更多...
.NET Standard 支持的 .NET Framework 和 .NET Core

.NET Standard 支持的 .NET Framework 和 .NET Core

.NET Standard 是针对多个 .NET 实现推出的一套正式的 .NET API 规范。 推出 .NET Standard 的背后动机是要提高 .NET 生态系统中的一致性。 .NET 5 及更高版本采用不同的方法来建立一致性&#xff0c;这种方法在大多数情况下都不需要 .NET Standard。 但如果要在 .NET Framewo…
阅读更多...
SAP设置修改删除自动JOB

SAP设置修改删除自动JOB

一、设置JOB 方法一 一个不需要单独记事务码的方式 如果FS要求开发做了程序的话&#xff0c;直接执行事务码&#xff0c;点击左上角 程序-后台执行 输出设备选择LP01 打勾&#xff0c;有可能还有一个对话框&#xff0c;也打勾 打勾后设置周期值 系统预设的会有小时、天、周…
阅读更多...
创新性文生视频模型，南洋理工开源FreeInit

创新性文生视频模型，南洋理工开源FreeInit

文本领域的ChatGPT&#xff0c;画图领域的Midjourney都展现出了大模型强大的一面&#xff0c;虽然视频领域有Gen-2这样的领导者&#xff0c;但现有的视频扩散模型在生成的效果中仍然存在时间一致性不足和不自然的动态效果。 南洋理工大学S实验室的研究人员发现&#xff0c;扩散…
阅读更多...
Spring Cloud Gateway + Nacos 灰度发布

Spring Cloud Gateway + Nacos 灰度发布

前言 本文将会使用 SpringCloud Gateway 网关组件配合 Nacos 实现灰度发布&#xff08;金丝雀发布&#xff09; 环境搭建 创建子模块服务提供者 provider&#xff0c;网关模块 gateway 父项目 pom.xml 配置 <?xml version"1.0" encoding"UTF-8"?…
阅读更多...
【Spring实战】22 Spring Actuator 入门

【Spring实战】22 Spring Actuator 入门

文章目录 1. 定义2. 功能3. 依赖4. 配置5. 常用的应用场景1&#xff09;环境监控2&#xff09;运维管理3&#xff09;性能优化 结论 Spring Actuator 是 Spring 框架的一个模块&#xff0c;为开发人员提供了一套强大的监控和管理功能。本文将深入探讨 Spring Actuator 的定义、…
阅读更多...
【HTML5】第1章 HTML5入门

【HTML5】第1章 HTML5入门

学习目标 了解网页基本概念&#xff0c;能够说出网页的构成以及网页相关名词的含义 熟悉Web标准&#xff0c;能够归纳Web标准的构成。 了解浏览器&#xff0c;能够说出各主流浏览器的特点。 了解HTML5技术&#xff0c;能够知道HTML5发展历程、优势以及浏览器对HTML5的支持情…
阅读更多...
【QT】QStandardItemModel类的应用介绍

【QT】QStandardItemModel类的应用介绍

目录 1 概述 2 常用方法 3 QStandardItemModel的使用 3.1 界面设计与主窗口类定义 3.2 系统初始化 3.3 从文本文件导入数据 3.4 数据修改 3.5 单元格格式设置 3.6 数据另存为文件 1 概述 QStandardItemModel是标准的以项数据&#xff08;itemdata&#xff09;为基础的…
阅读更多...
FPGA项目（14）——基于FPGA的数字秒表设计

FPGA项目（14）——基于FPGA的数字秒表设计

1.功能设计 设计内容及要求: 1.秒表最大计时范围为99分59. 99秒 2.6位数码管显示&#xff0c;分辨率为0.01秒 3.具有清零、启动计时、暂停及继续计时等功能 4.控制操作按键不超过二个。 2.设计思路 所采用的时钟为50M&#xff0c;先对时钟进行分频&#xff0c;得到100HZ频率…
阅读更多...
CSS 放大翻转动画

CSS 放大翻转动画

<template><div class="container" @mouseenter="startAnimation" @mouseleave="stopAnimation"><!-- 旋方块 --><div class="box" :class="{ rotate-scale-up-hor: isAnimating }"><!-- 元素内…
阅读更多...
macosx编译qgroundcontrol源码(Qt6.7)

macosx编译qgroundcontrol源码(Qt6.7)

1.克隆源码: clone --recursive http://github.com/mavlink/qgroundcontrol.git 克隆成功 3.编译 编译环境要求: 编译方法: 使用QtCreator编译 使用命令行编译 打开QGroundControl.pro并编译IOS版本 旧版本使用Qt 5.15.2 run qmake 新版本使用Qt 6.6或者更高 IOS工程输出要…
阅读更多...
mysql5.7安装-windows安装版本

mysql5.7安装-windows安装版本

下载地址 官网地址:https://www.mysql.com/官网下载地址:https://dev.mysql.com/downloads/mysql/阿里云镜像站下载:https://mirrors.aliyun.com/mysql/华为云镜像站地址:https://mirrors.huaweicloud.com/home华为云镜像站下载:https://mirrors.huaweicloud.com/mysql/Downlo…
阅读更多...
英飞凌TC3xx之一起认识GTM（九）GTM相关知识简述（CMU,CCM,TBU,MON）

英飞凌TC3xx之一起认识GTM（九）GTM相关知识简述（CMU,CCM,TBU,MON）

英飞凌TC3xx之一起认识GTM（九）GTM相关知识简述（CMU,CCM,TBU,MON） 1 时钟管理单元（CMU）2 集群配置模块（CCM）3 时基单元（TBU）4 监控单元（MON）5 总结由前文的各篇内容，开发者已经知道如何使用GTM的大部分功能，在这些功能中，都需要一个信息就是fGTM 的数据，我们在前…
阅读更多...
技术查漏补缺（1）Logback

技术查漏补缺（1）Logback

一、下定义&#xff1a;Logback是一个开源的日志组件 二、Logback的maven <!--这个依赖直接包含了 logback-core 以及 slf4j-api的依赖--> <dependency><groupId>ch.qos.logback</groupId><artifactId>logback-classic</artifactId><v…
阅读更多...
excel统计分析——两因素无重复方差分析

excel统计分析——两因素无重复方差分析

参考资料&#xff1a;生物统计学 从严格意义上讲&#xff0c;两因素试验都应当设置重复观测值&#xff0c;以便检验交互作用是否真实存在&#xff0c;对试验误差有更准确的估计&#xff0c;从而提高检验效率。但根据专业知识或先前的试验已经证明两个因素不存在交互作用时&…
阅读更多...
算法每日一题： 被列覆盖的最多行数 | 二进制 - 状态压缩

算法每日一题： 被列覆盖的最多行数 | 二进制 - 状态压缩

大家好&#xff0c;我是星恒 今天的题目又是一道有关二进制的题目&#xff0c;有我们之前做的那道 参加考试的最大学生数的 感觉&#xff0c;哈哈&#xff0c;当然&#xff0c;比那道题简单多了&#xff0c;这道题感觉主要的考点就是二进制&#xff0c;大家可以好好总结一下这道…
阅读更多...
JVM加载class文件的原理机制

JVM加载class文件的原理机制

1、JVM 简介 JVM 是我们Javaer 的最基本功底了&#xff0c;刚开始学Java 的时候&#xff0c;一般都是从“Hello World ”开始的&#xff0c;然后会写个复杂点class &#xff0c;然后再找一些开源框架&#xff0c;比如Spring &#xff0c;Hibernate 等等&#xff0c;再然后就开发…
阅读更多...
【数值分析】非线性方程求根，牛顿法，牛顿下山法，matlab实现

【数值分析】非线性方程求根，牛顿法，牛顿下山法，matlab实现

4. 牛顿法 收敛时牛顿法的收敛速度是二阶的&#xff0c;不低于二阶。如果函数有重根&#xff0c;牛顿法一般不是二阶收敛的。 x k 1 x k − f ( x k ) f ′ ( x k ) x_{k1}x_k- \frac{f(x_k)}{f(x_k)} xk1​xk​−f′(xk​)f(xk​)​ matlab实现 %% 牛顿迭代例子 f (x) x…
阅读更多...
JRTClient打开谷歌

JRTClient打开谷歌

网站默认已经启动https访问&#xff0c;这时候JRTClient发布wss需要浏览器信任证书才能访问打印。为此在JRTClient内部发布了HTTPS服务&#xff0c;有时候浏览器信任的证书会丢失或者被清理掉&#xff0c;这时候需要手工信任下&#xff0c;当然用JRTBrowser就不用信任证书&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023