首页 操作系统

# 操作系统 PV 代码题速记

进程 P 向 m 个进程 Q1、Q2、Q3…Qm 发送消息，进程 P 发消息到缓冲区，只有所有的 Q 进程都接收到消息后，进程 P 才能继续向缓冲区放消息，请写出 PV 操作逻辑。

semaphore mutex=1, T[i]=0, notHave=1;
//mutex 是缓冲区互斥锁，T [i] 是 Qi 进程完成数组，是一个自阻塞数组
//notHave 是缓冲区是否为空，1 就是空，初始没有信息
int R=0;
//R 是一个计数器
Process_P(){
    while(1){
        P(notHave);
        P(mutex);
        放入缓冲区;
        for(int i=1;i<=m;i++){
            P(T[i]);
        }
        R=0;
        V(mutex);
    }
}
Process_Qi(){
    while(1){
        P(T[i]);
        P(mutex);
        取消息;
        R=R+1;
        if(R==m){
            V(notHave);
        }
        V(mutex);
    }
}

# 单生产者 - 单消费者

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

semaphore full = 0;	// 已生产
semaphore empty = n;// 总可用空间
semaphore mutex = 1;// 互斥锁
procuder(){
    while(1){
        生产商品;
        P(empty);	// 假取空间
        P(mutex);	// 加锁
        放入缓冲区;	
        V(mutex);	// 解锁
        V(full);	// 告知以生产
    }
}
consumer(){
    while(1){
        P(full);
        P(mutex);
        从缓冲区取;
        V(mutex);
        V(empty);
        消费商品;
    }
}

# 多生产者 - 多消费者

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

semaphore mutex = 1;	// 盘子锁
semaphore apple = 0;
semaphore orange = 0;
dad(){
    while(1){
        准备苹果;
        P(mutex);
        放苹果;
        V(apple);
    }
}
mom(){
    while(1){
        准备橘子;
        P(mutex);
        放橘子;
        V(orange);
    }
}
son(){
    while(1){
        P(orange);
        拿苹果;
        V(mutex);
        吃苹果;
    }
}
daughter(){
    while(1){
        P(apple);
        拿苹果;
        V(mutex);
        吃苹果;
    }
}
# 读者写者问题（读优先）


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


因此要求:


    

  1. 允许多个读者可以同时对文件执行读操作。
    2. 

  2. 只中许一个写者往文件中写信息。
    3. 

  3. 任一写者在完成写操作之前不允许其他读者或写者工作。
    4. 

  4. 写者执行写操作前，应让已有的读者和写者全部退出。
    5. 



semaphore rw = 1;	//r-w 读者在读时，不容许其他写者加入。写者在写时，不容许其他读者写者加入。
int count = 0;		// 记录已加入的读者的数量，如果不为 0，那么其中必有读者，那么其他读者随便加入。
semaphore count_mutex = 1;
writer(){
    while(1){
        P(rw);
        写文件;
        V(rw);
    }
}
reader(){
    while(1){
        P(count_mutex);
        if(count == 0){	// 如果不为 0，那么其中必有读者，那么其他读者随便加入。
            P(rw);	// 读者为排除其他写者
        }
        count++;	// 在线加 1
        V(count_mutex);
        读文件;
        P(count_mutex);
        count--;	// 在线减 1
        if(count == 0){
            V(rw);
        }
        V(count_mutex);
        
    }
}
有可能造成写饥饿


# 读者写者问题（写优先）


semaphore rw = 1;
int count = 0;
semaphore w = 1;	// 写进程霸占
semaphore count_mutex = 1;
writer(){
    while(1){
        P(w);	// 写进程启用霸占
        P(rw);
        写文件;
        V(rw);
        V(w);
    }
}
reader(){
    while(1){
        P(w);	// 写进程阻碍读进程进入
        P(count_mutex);
        if(count == 0){
            P(rw);
        }
        count++;
        V(count_mutex);
        V(w);
        读文件;
        P(count_mutex);
        count--;
        if(count == 0){
            V(rw);
        }
        V(count_mutex);
        
    }
}
# 吸烟者问题


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


semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore isFinish = 1;
int i = 0;
provider(){
    while(1){
        P(isFinish);
    	if(i%3 == 0){
        	V(offer1);
    	}else if(i%3 == 1){
        	V(offer2);
    	}else{
        	V(offer3);
    	}
    }
    
}
somker1(){
    while(1){
        P(offer1);
    	制作香烟;
    	吸烟;
        V(isFinish);
    } 
}
somker2(){
    while(1){
        P(offer2);
    	制作香烟;
    	吸烟;
        V(isFinish);
    } 
}
somker3(){
    while(1){
        P(offer3);
    	制作香烟;
    	吸烟;
        V(isFinish);
    } 
}
# PV 审题流程


    

  1. 看有几个进程
    2. 

  2. 进程内部的步骤
    3. 

  3. 是否需要 while（1）
    4. 

  4. 哪里有 P？有 P 必有 V
    5. 

  5. 连续 P 是否会死锁
    6. 

  6. 定义信号量，写注释
    7. 



# 题目实操


# 2020 统考真题


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


semaphore ac = 0;
semaphore bc = 0;
semaphore ce = 0;
semaphore ce = 0;
A(){
    执行任务;
    V(ac);
}
B(){
    执行任务;
    V(bc);
}
C(){
    P(ac);
    P(bc);
    执行任务;
    V(ce);
}
D(){
    执行任务;
    V(de);
}
C(){
    P(ce);
    P(de);
    执行任务;
}
【2009 统考真题】三个进程 P1,P2,P3, 互斥使用一个包含 N (N>0) 个单元的缓冲区。


    

  1. P1 每次用 produce () 生成一个正整数并用 put () 送入缓冲区某一空单元；
    2. 

  2. P2 每次用 getodd () 从该缓冲区中取出一个奇数并用 countodd () 统计奇数个数；
    3. 

  3. P3 每次用 geteven () 从该缓冲区中取出一个偶数并用 counteven () 统计偶数个数。
    4. 



请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义 (要求用伪代码描述)。


semaphore mutex = 1;
semaphore odd = 0;
semaphore even = 0;
P1(){
    while(1){
        int num = produce();
        if(num%2 == 0){
            P(mutex);
            put();
            V(mutex);
            V(even);
        }else{
            P(mutex);
            put();
            V(mutex);
            V(odd);
        }
    }
}
P2(){
    while(1){
        P(odd);
        P(mutex);
        getodd();
        V(mutex);
        countodd()
    }
}
P2(){
    while(1){
        P(even);
        P(mutex);
        geteven();
        V(mutex);
        counteven()
    }
}
# 2011 统考真题


【2011 统考真题】某银行提供 1 个服务窗口和 10 个供顾客等待的座位。顾客到达银行时若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。


semaphore count = 10;
semaphore mutex = 1;
semaphore server = 1;
semaphore full = 0;
customer(){
    while(1){
        P(count);
        P(mutex);
    	从取号机取号;
    	V(mutex);
    	V(full);
    	等待叫号;
    	P(server);
    	获取服务;
    }
    
}
clerk(){
    while(1){
        P(full);
        叫号;
        V(server);
        服务;
        V(count);
    }    
}
# 809-24 年 真题


崂山有一景点称作上清宫，游客在上清宫游玩后可以在宫门口免费搭乘轿车游览其他景区，游览后再返回宫门口。已知风景区游览轿车总量有 M 量，游客总数为 N，约定:


    

  1. 每辆轿车限乘一位游客；
    2. 

  2. 如果有空闲的轿车，应当允许想游览的游客乘坐；
    3. 

  3. 无空闲轿车时，游客只能排队等待；
    4. 

  4. 若没有想游览的游客，空闲的轿车也要等待。
    5. 



试利用 P、V 操作实现在上清宫门口乘车点：N 个游客进程和 M 辆轿车进程的同步操作过程。


semaphore mutex = 1;
semaphore car = 0; 		// 空闲车辆数量
semaphore customer = 0; // 等待乘车的游客数量
//M 个车辆进程
car(){
    while(1){
        等待游客;
        P(customer);	// 等待有游客请求乘车
        P(mutex);		// 进入临界区
        V(car);			// 提供一辆空闲轿车
        V(mutex);		// 离开临界区
        接待游览;
        释放游客;
    }
}
//N 个游客进程
customer(){
    while(1){
        等待车辆;
        P(car);			// 等待空闲轿车
       	P(mutex);		// 进入临界区
        V(customer)		// 通知有游客请求乘车
        V(mutex);		// 离开临界区
        上车游览;
        离开;
    }
}
# 典例 和尚打水


某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容 10 桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为 3 个。每次入缸取水仅为 1 桶水，且不可同时进行，试给出有关从缸取水、入水的算法描述。


semaphore total_empty = 10;
semaphore total_full = 0;
semaphore mutex_jing = 1;
semaphore mutex_gang = 1;
demaphore bucket = 3;
Old (){
    P(total_full);
    P(bucket);
    P(mutex_gang);
    从缸里取水;
    V(total_empty);
    V(mutex_gang);
	喝水;
    V(bucket);
}
Young(){
    P(total_empty);
    P(bucket)
    P(mutex_jing);
    从水井取水;
    V(mutex_jing);
    P(mutex_gang);
	倒进缸里;
    V(total_full);
    V(mutex_gang);
    V(bucket);
    
}
# 典例 公交车售票


设公共汽车上，司机和售票员的活动分别是：


    

  1. 司机的活动：启动车辆；正常行车；到站停车；
    2. 

  2. 售票员的活动：关车门；售票；开车门；
    3. 



请用记录型信号量机制实现上述问题的同步。


semaphore door_mutex = 1;
semaphore start_mutex = 0;
driver(){
    while(1){
        P(start_mutex);
        启动车辆;
        正常行车;
        到站停车;
        V(door_mutex);
    }
}
busman(){
    while(1){
        P(door_mutex);
        开车门;
        售票;
        关车门;
        V(start_mutex);
    }
}
# 典例 独木桥问题


请用信号量解决以下的 “过独木桥” 问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。


semaphore isOK = 1;
int toACount = 0;
int toBCount = 0;
semaphore toACount_mutex = 1;
semaphore toBCount_mutex = 1;
toA(){
    P(toACount_mutex);
    if(toACount == 0){
        P(isOK);
    }
    toACount++;
    V(toACount_mutex);
    上桥走向A;
    P(toACount_mutex);
    toACount--;
    if(toACount == 0){
        V(isOK);
    }
    V(toACount_mutex);
}
toB(){
    P(toBCount_mutex);
    if(toBCount == 0){
        P(isOK);
    }
    toBCount++;
	V(toBCount_mutex);
    上桥走向B;
    P(toBCount_mutex);
    toBCount--;
    if(toBCount == 0){
        V(isOK);
    }
	V(toBCount_mutex);
}
# 典例 阅览室问题


有一阅览室，共有 100 个座位。为了很好利用它，读者进入时必须先在登记表上进行登记。该表表目设有座位号和读者姓名；离开时再将其登记项摈除。试问：


    

  1. 为描述读者的动作，应设哪几个进程？它们之间的关系是什么？
    2. 

  2. 试用 P、V 操作描述进程之间的同步或算法。
    3. 



答：要设读者进入进程和离开进程，总计两个进程。他们是互斥关系。


semaphore seats = 100;
semaphore readers = 0;
semaphore table_mutex = 1;
getIn(){
    while(1){
        P(seats);
        P(table_mutex);
        登记;
        V(table_mutex);
        V(readers);
    }
}
getOut(){
    while(1){
        P(readers);
        P(table_mutex);
        移除登记;
        V(table_mutex);
        V(seats);
    }
}
# 典例 考试问题


《操作系统》课程的期末考试即将举行，假设把学生和监考老师都看作进程，学生有 N 人，教师 1 人。考场门口每次只能进出一个人，进考场的原则是先来先进。当 N 个学生都进入了考场后，教师才能发卷子。学生交卷后即可离开考场，而教师要等收上来全部卷子并封装卷子后才能离开考场。


(1) 问共需设置几个进程？


(2) 请用 P、V 操作解决上述问题中的同步和互斥关系。


答：共设置 N+1 个进程，一个教师进程，N 个学生进程


int studentCount = 0;
int onPageCount = 0;
semaphore door_mutex = 1;
semaphore startTest = 0;
semaphore endTest = 0;
semaphore readyToTest = 0;
semaphore onPageCount_mutex = 1;
semaphore allStudentsOK = 0;
teacher(){
    P(door_mutex);
    进门;
    V(door_mutex);
    P(readyToTest);
    发卷子;
    V(startTest);
    监考;
    P(allStudentsOK);
    整理试卷;
    P(door_mutex);
    出门;
    V(door_mutex);
}
students(){
    P(door_mutex);
    进门;
    studentCount++;
    if(studentCont == N){
        V(readyToTest);
    }
    V(door_mutex);
    P(startTest);
    开始答题;
    P(onPageCount_mutex);
    交卷;
    onPageCount++;
    if(onPageCount == N){
        V(allStudentsOK);
    }
    V(onPageCount_mutex);
    P(door_mutex);
    出门;
    studentCount--;
    V(door_mutex);
}

          

          hunter_wyh CSDN 博客
          
部分题目出自此博客

          

      

          
      

  


   


    

  
    
      
    
    更新于
    
  
  
      
        
      
      阅读次数
      
      次
  



      


  
  
请我喝[茶]~(￣▽￣)~*

  

      
      

        KarryLiu 微信支付
        
微信支付

      

      
      

        KarryLiu 支付宝
        
支付宝