首页 > 系统相关 >操作系统——进程同步互斥经典题目

操作系统——进程同步互斥经典题目

时间：2024-10-31 12:09:37浏览次数：1  
标签：P2 操作系统 进程同步 互斥 while mutex semaphore 缓冲区

操作系统——进程同步互斥经典题目

前言

这里是操作系统课程中老师布置的作业，主要是关于进程同步互斥的考研真题。

题目

题目一

有4个进程P1、P2、P3、P4。要求P1必须在P2、P3开始前完成，P2、P3必须在P4开始前完成，且P2和P3 不能并发执行。试写出这4个进程的同步互斥算法。

解答：

  1. 题目分析:

    • 同步关系有：

      • P1->P2
      • P1->P3
      • P2,P3 -> P4

    • 互斥关系有：

      • P2 - P3

    可以根据题目画出下面的前驱图

    ​

  2. 解答

    因此，我们设置四个信号量：S1、S2、S3。其中具体含义如下

    S1：初始为0，P1是否完成，同时充当P2和P3的互斥信号量

    S2：初始为0，P2是否完成

    S3：初始为0，P3是否完成

    Semaphore S1 = 0;
Semaphore S2 = 0;
Semaphore S3 = 0;

P1(){
	while(1){
		P1操作;
		V(S1);
	}
}

P2(){
	while(1){
		P(S1);
		P2操作;
		V(S1);
		V(S2);
	}
}

P3{
	while(1){
		P(S1);
		P3操作;
		V(S1);
		V(S3);
	}
}

P4{
	while(1){
		P(S2);
		P(S3);
		P4操作;
		V(S2);
		V(S3);
	}
}

  3. 扩展：假如P2和P3可以并行，应该如何写？

    略

‍

题目二

假设有一个路口，通行交通规则如下:只要没有机动车在通行，路口行人就可以通过，只有没有行人在通过路口且没有其他机动车在通过路口时该机动车才能通过。请用P、V操作描述行人和机动车通过路口的同步互斥过程。

  1. 首先对题目进行分析：

    这个题目类似于读者问题，行人可以存在多个，但机动车彼此之间只能存在一个。

    而且行人与机动车是互斥的。

    • 行人通过 与 机动车通过 属于 互斥关系

    • 机动车通过 与 （其他）机动车通过也属于互斥关系

    • 无同步关系

    行人之间是没有互斥关系，可以存在多个行人，所以不能单纯使用PV操作单个互斥向量管理行人进程

  2. 解答：

    int count = 0;          // 记录行人数量
Semaphore mutex = 1;    // 保护count更新
cross = 1; 				//机动车、行人的互斥

P_car(){
	while(1){
		P(cross);
		机动车通过路口();
		V(cross);
	}
}

P_passerby(){
	while(1){
		P(mutex);
		if(count==0){ 	//如果路口上没有行人，代表可能有机动车，需要进行检测
			P(cross);
		}
		count++;
		V(mutex);

		行人通过路口();

		P(mutex);
		count--;
		if(count == 0) {
			V(cross);
		}
		V(mutex);
	}
}

题目三

系统中有多个生产者进程和消费者进程，共享用一个可以存1000个产品的缓冲区（初始为空）。

  • 当缓冲区未满时，生产者进程可以放入1件其生产的产品，否则等待；
  • 当缓冲区不空时，消费者进程可以取走1件产品，否则等待。

要求1个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量P，V（或wait()、signal()）操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值。

  1. 分析：

    • 有多个生产者进程，互相并不互斥，但是其检查缓冲区剩余容量时需要互斥管理
    • 消费者进程必须要取出10件产品，才能释放资源，因此互相互斥
    • 生产者进程和消费者进程之间对缓冲区保持互斥，防止并发导致信息过期

  2. 解答：

    Semaphore mutex = 1;	//保护缓冲区访问
Semaphore full = 0;		//表示缓冲区中的产品数量
Semaphore empty = 1000;	//缓冲区空余位置
Semaphore consum = 1;	//消费者线程之间不取出10个之前保持互斥

producer(){
	while(1){
		生产一个产品();
		P(mutex);
		P(empty);
		将生产的产品存入缓冲区();
		V(full);
		V(mutex);
	}
}

consumer(){
	while(1){
		P(consum);
		for(int i=0;i<10;i++){ //取出10个产品
			P(mutex);
			P(full);
			取出产品();
			V(empty);
			V(mutex);
		}
		V(consum);
		使用产品();
	}
}

题目四

一组相互合作的进程P1、P2、P3、P4、P5、P6，其执行过程须满足如图所示的同步关系，请使用信号量机制对该组进程进行同步。
​​

Semaphore S1 = 0;
Semaphore S2 = 0;
Semaphore S3 = 0;
Semaphore S4 = 0;
Semaphore S5 = 0;

P1(){
	while(1){
		P1操作();
		V(S1);
		V(S2);
	}
}
P2(){
	while(1){
		P(S1);
		P2操作();
		V(S3);
	}
}
P3(){
	while(1){
		P(S2);
		P3操作;
		V(S4);
	}
}
P4(){
	while(1){
		P(S3);
		P4操作();
		V(S5);
	}
}
P5(){
	while(1){
		P(S4);
		P(S5);
		P5操作();
		V(S6);
	}
}
P6(){
	while(1){
		P(S6);
		P6操作();
	}
}

‍

题目五

两个进程 P1、P2 并发执行，并用信号量 M1，M2 分别实现对两个互斥共享的资源R1 和 R2 的互斥访问。这两个进程以什么次序执行会导致死锁?在不影响程序功能的情况下，请修改算法以防止死锁，同时尽可能保持较高的资源利用率。

var M1, M2: semaphore = 1, 1;

begin

parbegin

P1
begin:
    wait(M1);
    access R1;
    wait(M2);
    access R1 and R2;
    signal(M1);
    signal(M2);
end

P2
begin:
    wait(M2);
    access R2;
    wait(M1);
    access R1;
    signal(M1);
    signal(M2);
end

parend

解答：

导致死锁的顺序： P1获取到了R1资源，但还没有得到M2信号量的时候，P2使用了M2信号量。这时P1想获取M2，但M2被P2持有；P2想获取M1，但M1被P1持有。两者都不释放自己的资源，但又持有着对面想要的资源。

var M1, M2: semaphore = 1, 1;

begin

parbegin

P1
begin:
    wait(M1);
    access R1;
    wait(M2);
    access R1 and R2;
    signal(M1);
    signal(M2);
end

P2
begin:
	wait(M1);
	access R1;
    wait(M2);
    access R2;  
    signal(M1);
    signal(M2);
end

parend

题目六

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

semaphore bow = m; // 碗的信号量
semaphore chopstick[n] = 1; // 筷子的信号量

void philosopher(int i) {
    while (true) {
        think();
        P(bow); // 尝试获取一个碗
		if(i%2 == 0){
			P(chopstick[(i+1)%n]);//偶数哲学家先右后左
			P(chopstick[i]);
		}else{
			P(chopstick[i]);//奇数哲学家先左后右
			P(chopstick[(i+1)%n]);
		}
		eat();
        V(bow);
		V(chopstick[i]);
		V(chopstick[(i+1)%n]);
    }
}

题目七

现有 5 个操作 A、B、C、D 和 E。操作 C 必须在 A 和 B 完成后执行，操作 E 必须在C 和 D 完成后执行，请使用信号量的 P、V（或 wait()、signal()）操作描述上述操作之间的同步关系，并说明所用信号量及其初值。

semaphore A = 0; // 表示 A 是否已完成
semaphore B = 0; // 表示 A 是否已完成
semaphore C = 0; // 表示 A 是否已完成
semaphore D = 0; // 表示 A 是否已完成

void operationA() {
	while(1){
	    A操作();
		V(A); // 操作 A 完成
	}
}

void operationB() {
	while(1){
	    B操作();
    	V(B); // 操作 B 完成
	}
}

void operationC() {
	while(1){
	    P(A); // 等待 A 和 B 完成
		P(B);
	    C操作();
	    V(C); // 操作 C 完成
	}
}

void operationD() {
	while(1){
		D操作();
	    V(D); // 操作 D 完成
	}
}

void operationE() {
	while(1){
	    P(C);
		P(D);
		E操作();
		V(E);
	}
}

题目八

某展览馆举行现代画展，展览馆内可以同时接纳 2000 人参观，参观者分为学生票和普通票，要求

（1）0≤普通票-学生票≤400；

（2）展览馆出入口每次只有 1 人进或出。

请用P、V（或 wait()、signal()）操作描述持普通票和持学生票者进、出展览馆的同步互斥过程。

分析：
①不等式：展馆内普通票比学生票多，且最多多400
②若展馆内无学生票，普通票最多400，设初值为400；若无普通票，则也必然没有学生票，设学生票初值0。
③展馆内每多一张普通票，学生票就多一个入馆机会，普通票每出馆一人，学生票就少一个入馆机会。

semaphore Pticket = 400;//可使用普通票资源
semaphore Sticket = 0; //可使用学生票资源
semaphore empty = 2000; //可入馆人数
semaphore mutex = 1;//出入口
 
Ordinary()//普通票
{
  while(1)
 {
   p(Pticket); //获取普通票入馆资源
   p(mutex); //进出互斥
   p(empty);
   入馆;
   v(mutex);
   v(Sticket);//学生票多了一次入馆机会
   参观展馆;

   p(Sticket); //获取学术票入馆资源
   p(mutex); //进出互斥
   出馆;
   v(mutex);
   v(Pticket);
   v(empty);
 }
}

 
Student()
{
  while(1)
 {
   p(Sticket);
   p(empty);
   p(mutex);
   进馆；
   v(mutex);
   v(Pticket);
   参观展馆：

   p(Pticket);
   p(mutex);
   出馆;
   v(mutex);
   v(Sticket);
   v(empty);

 }
}

题目九

有 3 个进程 P1、P2和 P3协作解决文件打印问题。

P1将文件记录从磁盘读入内存的缓冲区 1，每执行一次读一个记录；

P2将缓冲区 1 中的内容复制到缓冲区 2 中，每执行一次复制一个记录；

P3将缓冲区 2 中的内容打印出来，每执行一次打印一个记录。

缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。

semaphore mutex1 = 1; //对于缓冲区1的访问互斥
semaphore full1 = 0; //缓冲区1的内容
semaphore mutex2 = 1; //对于缓冲区2的访问互斥
semaphore full2 = 0; //缓冲区2的内容

void P1(){
	while(true){
		P(mutex1);
		从文件记录读入缓冲区1();
		V(full1);
		V(mutex1);
	}
}

void P2(){
	while(true){
		P(full1)
		P(mutex1);
		读取缓冲区1();
		V(mutex1);

		P(mutex2);
		写入缓冲区2();
		V(full2);
		V(mutex2);
	}
}

void P3(){
	while(true){
		P(full2);
		P(mutex1);
		读取缓冲区2();
		V(mutex1);
		打印();
	}
}

题目十

桌上有个能盛得下 1 个水果的空盘子。爸爸不停地向盘中放苹果，妈妈不停地向盘中放桔子，儿子不停地从盘中取出桔子享用，女儿不停地从盘中取出苹果享用。试用信号量实现妈妈、爸爸、儿子和女儿循环进程之间的同步。

semaphore plate = 1; //对盘子是否为空
semaphore orange = 0; //橘子资源
semaphore apple = 0; //苹果资源

void dad(){
	while(1){
		P(plate);
		放入苹果();
		V(apple);
	}
}

void mom(){
	while(1){
		P(plate);
		放入橘子();
		V(orange);
	}
}

void son(){
	while(1){
		P(orange);
		V(plate);
		享用();
	}
}

void daughter(){
	while(1){
		P(apple);
		V(plate);
		享用();
	}
}

题目十一

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

代码与题目六一样。

semaphore bow = m; // 碗的信号量
semaphore chopstick[n] = 1; // 筷子的信号量

void philosopher(int i) {
    while (true) {
        think();
        P(bow); // 尝试获取一个碗
		if(i%2 == 0){
			P(chopstick[(i+1)%n]);//偶数哲学家先右后左
			P(chopstick[i]);
		}else{
			P(chopstick[i]);//奇数哲学家先左后右
			P(chopstick[(i+1)%n]);
		}
		eat();
        V(bow);
		V(chopstick[i]);
		V(chopstick[(i+1)%n]);
    }
}

题目十二

设公共汽车上，司机和售票员的活动分别是:司机活动:启动车辆、正常行车、到站停车；售票员活动:关车门、售票、开车门。

要求:当发车时间到，售票员关好车门后，司机才能启动车辆，售票员开始售票；当到站后，司机停车后，售票员才能打开车门，乘客下车，站牌乘客上车。

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系?用信号量和 P、V 操作实现他们的同步。

分析：

正常行车、到站停车->售票员打开车门->乘客下车，站牌乘客上车->售票员关好车门->启动车辆->回到起始点

semaphore door = 0;
semaphore stop = 0;

void conductor()
{
	while(true)
	{
		//乘客上下车
		//关门
		V(door);//售票员给司机关门的信号
		//此阶段为售票时间
		P(stop);//等待停车信号，一旦停车，则开门
		//开门
	}
}

void driver()
{
	while(true)
	{
		P(door);//司机等待关门信号，一旦获取信号，则启动车辆
		//此阶段为正常行车时间
		V(stop);//司机给售票员停车的信号
	}
}

题目十三

在一个只允许单向行驶的十字路口，分别有若干由东向西，由南向北的车辆在等待通过十字路口。为了安全，每次只允许一辆车通过(东→西或南→北)。当有车辆通过时其它车辆等待，当无车辆在路口行驶时则允许一辆车(东→西或南→北)进入。请用 P、V 操作实现能保证安全行驶的自动管理系统。

semaphore mutex = 1;

void car(){ //两种方向的车都一样
	while(1){
		P(mutex);
		通过();
	}
}

题目十四

设有一个具有 N 个信息元素的环形缓冲区，A 进程顺序地把信息写入缓冲区，B 进程依次地从缓冲区中读出信息。回答下列问题:（1）叙述 A、B 两个进程的相互制约关系。（2）用 P、V 操作表示 A、B 进程的同步算法。

分析：

A在写入信息时，B不能读信息；相反，B在读信息时，A不能写入信息。

当缓冲区满时，A不能写入信息。

当缓冲区为空时，B不能读出信息。

semaphore empty = N; //缓冲区剩余空间
semaphore full = 0; //缓冲区的信息数量
semaphore mutex = 1; //缓冲区的互斥访问

void A(){
	while(true){
		P(empty);
		P(mutex);
		写入信息();
		V(mutex);
		V(full);
	}
}

void B(){
	while(true){
		P(full);
		P(mutex);
		读取信息();
		V(mutex);
		V(empty);
	}
}

题目十五

某博物馆最多可容纳 500 人同时参观，有一个出入口，该出入口一次仅允许一个人通过。

参观者的活动描述如下:

Cobegin

参观者进程 i:
{
  …
  进门;
  …
  参观;
  …
  出门;
  …
}

Coend

请添加必要的信号量和 P、V(或 wait()、signal( ))操作，以实现上述操作过程中的互斥与同步。要求写出完整的过程，说明信号量含义并赋初值。

Cobegin

semaphore empty = 500;	//博物馆空位数
semaphore mutex = 0;	//一次只能一个人进出

参观者进程 i:
{
  P(empty);	//当博物馆还有空位的时才能进入博物馆
  P(mutex);
  进门;		//当博物馆还有空位的时才能进入博物馆
  V(mutex);
  参观;
  
  P(mutex);
  出门;		//当博物馆还有空位的时才能进入博物馆
  V(mutex);
  V(empty);	//出门后释放一个空位
}

Coend

标签：P2,操作系统,进程同步,互斥,while,mutex,semaphore,缓冲区
From： https://www.cnblogs.com/sodie/p/18517448

相关文章

  • 如何在麒麟操作系统上进行网络共享和文件传输
    在麒麟操作系统上进行网络共享和文件传输的步骤：一、设置共享文件夹；二、配置网络共享权限；三、使用网络传输工具。首先，我们需要创建一个共享文件夹，以便其他用户可以访问和下载其中的文件。一、设置共享文件夹首先，我们需要创建一个共享文件夹，以便其他用户可以访问和下载其中的文......
  • 18 操作系统
    操作系统，让计算机自动运转。节制其他程序之前只能一次给一个程序，现在可以一次给多个，运行完一个立刻自动运行下一个，这样不会浪费时间找下一个程序的纸卡，这就是批处理为了外部设备通用性，操作系统充当软件与硬件之间的媒介；操作系统提供api来驱动硬件；为了能同时运行多个程......
  • 【操作系统】1.进程和线程
    1.进程（Process）定义：进程是操作系统资源分配的基本单位，一个进程包含了程序的代码、数据、文件、内存等资源。每个进程之间都是独立的，拥有独立的地址空间。特性：独立性：每个进程之间是独立的，不能直接访问其他进程的内存空间。资源占用：进程会占用较多的系统资源，例如内存、文件描......
  • 【操作系统】2.并发控制
    并发控制（ConcurrencyControl）是指在多线程或多进程环境中，确保多个操作在共享资源上的访问不会发生冲突或产生不一致的情况。并发控制的核心目标是在允许并发操作的同时，保证系统的正确性、数据的一致性和完整性。在并发环境下，不同的线程或进程可能会同时访问共享资源（例如变量、文......
  • Linux系统基础-多线程超详细讲解(3)_线程互斥同步和条件变量
    个人主页：C++忠实粉丝欢迎点赞......
  • C系统编程——线程的互斥与同步
        一般每个程序都会有多个线程，也不能确定每个线程所需要的资源都是独立的，如果有两个线程需要同一个资源，且其中一个使用后却将其给释放掉了，那另一个就会得不到资源导致系统卡死，这也便是死锁，这是我们就新加了新的知识：互斥与同步来预防这类问题的发生。1.概念   ......
  • 操作系统(7) (POSIX--Linux线程编程---使用多线程计算平方pthread_t/create/join应用)
    1.代码目的我们希望创建一个程序：启动多个线程，每个线程计算一个数字的平方值。每个线程将计算结果返回给主线程。主线程接收每个线程的返回值，并将结果打印出来。在这个例子中，我们通过传递不同的参数给每个线程，来让每个线程计算不同数字的平方值。2.代码实现以下是代码的......
  • 【Linux操作系统】Linux配置OpenSSH服务器步骤记录
    1.安装OpenSSH服务器软件包用指令查询，已经全部安装。编辑/etc/ssh/sshd_config文件：#      $OpenBSD:sshd_config,v1.1032018/04/0920:41:22tjExp$#Thisisthesshdserversystem-wideconfigurationfile. See#sshd_config(5)formoreinformat......
  • 第二章：用户与操作系统的接口课后习题
    文章目录单项选择题填空题名词解释问答题单项选择题用户使用操作系统通常有3种手段，它们是终端命令、系统调用命令和。A.计算机高级指令B.作业控制语言C.宏命令D.汇编语言答案：B.作业控制语言解释：作业控制语言是用户用来控制作业执行的高级语言，而宏命令......
  • 麒麟操作系统中的磁盘分区和格式化如何进行
    ​为确保硬盘资源的最佳利用和数据安全性，麒麟系统下的磁盘操作过程步骤：一、了解麒麟操作系统的磁盘工具；二、如何进行磁盘分区；三、磁盘格式化的步骤；四、注意事项与推荐实践。在麒麟操作系统中进行磁盘分区和格式化是系统管理的基本操作。一、了解麒麟操作系统的磁盘工具麒麟操......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99