精华内容
下载资源
问答
  • 经典进程同步问题

    2020-10-21 18:37:58
    @[toc] 经典进程同步问题 1 生产者-消费者问题 问题 1 一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区,只有缓冲区没满时,生产者才能把消息放入缓冲区,否则必须等待;只有缓冲区不空时,消费...

    1 生产者-消费者问题

    问题 1

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

    分析:

    生产者和消费者对缓冲区的访问是互斥关系;同时它们之间又存在着同步关系,只有生产者生产之后消费者才能消费,而只有缓冲区未满(消费者一直消费)生产者才能生产产品。

    semaphore mutex = 1;	//用于实现对缓冲区的互斥访问
    semaphore empty = n;	//空闲缓冲区数量
    semaphore full = 0;		//非空闲缓冲区(产品)数量
    
    // 生产者进程
    producer(){
    	while(1){
    		生产一个消息;
    		p(empty);
    		p(mutex);
    		将一个消息放入缓冲区;
    		v(mutex);
    		v(full);
    	}
    }
    
    // 消费者进程
    producer(){
    	while(1){
    		p(full);
    		p(mutex);
    		从缓冲区取一个消息;
    		v(mutex);
    		v(empty);
    		消费消息;
    	}
    }
    

    问题 2

    桌上有一个盘子,每次只能向其中放入一个水果。爸爸只放苹果,妈妈只放橘子,女儿只拿苹果,儿子只拿橘子。只有盘子为空时,爸爸或妈妈才能向盘子中放水果,只有盘子不空时,儿子或女儿才能从盘子中拿水果

    分析:

    爸爸、妈妈都向盘子放水果,儿子、女儿都从盘子取水果,儿子取妈妈放的水果,女儿取爸爸放的水果。因此爸爸妈妈、儿子女儿各自之间为互斥关系;爸爸女儿、妈妈儿子各自之间为同步关系

    semaphore plate = 1, apple = 0, orange = 0;
    
    dad(){
    	while(1){
    		准备一个苹果;
    		p(plate);
    		放入一个苹果;
    		v(apple);
    	}
    }
    mom(){
    	while(1){
    		准备一个橘子;
    		p(plate);
    		放入一个橘子;
    		v(orange);
    	}
    }	
    
    son(){
    	while(1){
    		p(orange);
    		拿走一个橘子;
    		v(plate);
    		吃橘子;
    	}
    }
    daughter(){
    	while(1){
    		p(apple);
    		拿走一个苹果;
    		v(plate);
    		吃苹果;
    	}
    }
    

    2 读者-写者问题

    读者优先

    有读者和写者两组并发进程,共享一个文件,当两个或以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(写进程或读进程)同时访问共享数据时则可能导致数据不一致的情况发生。因此要求:

    • ①允许多个读者可以同时对文件执行读操作
    • ②只允许一个写者向文件写消息
    • ③任一写者完成写操作之前不允许其他读者或写者工作
    • ④写者执行写操作前,应让已有的读者和写者全部退出

    分析:

    允许一个或多个读者同时访问、只允许一个写者访问。因此读写互斥、写写互斥。总之,只要有写者,则必须互斥。

    设置互斥信号量 mutex,用于对数据区互斥访问,再设计数器 read_count,用于记录读者数量,当第一个读者到来时,对 mutex 进行p操作,只有最后一个读者离开时,才对 mutex 进行v操作,这样只要有读者,无论来多少个写者都会被阻塞,直到所有读者离开,释放 mutex 。如此便能实现读者优先

    int read_count = 0;  //用于记录读者数量
    semaphore rmutex = 1;//用于对read_count互斥访问
    semaphore mutex = 1; //用于对数据区互斥访问
    
    //写进程
    writer(){
    	while(1){
    		p(mutex);
    		写;
    		v(mutex);
    	}
    }
    
    //读进程
    reader(){
    	while(1){
    		p(rmutex);
    		if(read_count == 0)
    			p(mutex);
    		read_count++;
    		v(rmutex);
    		读;
    		p(rmutex);
    		read_count--;
    		if(read_count == 0)
    			v(mutex);
    		v(rmutex);
    	}
    }
    

    读写公平

    思考读者优先的方案:假设已有读进程正在对文件进行读取,后续又源源不断的有读进程到来,也有写进程到来。只要一直有读进程,则信号量 mutex 就一直得不到释放,则写进程就会一直被阻塞,尽管有的写进程比读进程到来的早。这就会造成写进程长时间被阻塞,甚至”饿死“。

    解决方案:若希望读进程、写进程公平访问文件,则需再设一个信号量 wmutex。当有读进程或写进程到来时,需要先对 wmutex 进行 p 操作,若写进程先到,则先p(wmutex),后续的读进程就会被阻塞;若读进程先到,则先p(wmutex),后续的写进程就会被阻塞。如此便能保证访问的公平性了。

    int read_count = 0;  //用于记录读者数量
    semaphore rmutex = 1;//用于对read_count互斥访问
    semaphore mutex = 1; //用于对数据区互斥访问
    semaphore wmutex = 1;//若已有写者到来,则阻塞后来的读者
    
    //写进程
    writer(){
    	while(1){
    		p(wmutex);
    		p(mutex);
    		写;
    		v(mutex);
    		v(wmutex);
    	}
    }
    
    //读进程
    reader(){
    	while(1){
    		p(wmutex);
    		p(rmutex);
    		if(read_count == 0)
    			p(mutex);
    		read_count++;
    		v(rmutex);
    		v(wmutex);
    		读;
    		p(rmutex);
    		read_count--;
    		if(read_count == 0)
    			v(mutex);
    		v(rmutex);
    	}
    }
    

    写者优先

    仿照读者优先的例子,添加一个互斥信号量readable,让写者对此信号量进行p操作,则只要有写者存在,此信号量由于没被写者释放,则读者一直被阻塞,从而实现写者优先

    semaphore mutex = 1;   //用于互斥访问数据区
    semaphore rmutex = 1;  //用于读者互斥访问read_count
    semaphore wmutex = 1;  //用于写者互斥访问write_count
    semaphore readable = 1;//用于表示当前是否有写者
    int read_count = 0, write_count = 0; //用于记录读者和写者数量
    
    reader(){
    	while(1){
    	    p(readable);
            p(rmutex);
            if(read_count == 0)
                p(mutex);
            read_count++;
            v(rmutex);
            v(readable);
            读;
            p(rmutex);
            read_count--;
            if(read_count == 0)
                v(mutex);
            v(rmutex);
    	}
    }
    
    writer(){
    	while(1){
    		p(wmutex);
    		if(write_count == 0)
    			p(readable);
    		v(wmutex);
    		
    		p(mutex);
    		写;
    		v(mutex);
    		
    		p(wmutex);
    		write_count--;
    		if(write_count == 0)
    			v(readable);
    		v(wmutex);
    	}
    }
    

    3 哲学家进餐问题

    一张圆桌边上坐着五名哲学家,没两名哲学家之间的桌上摆着一根筷子,两根筷子之间时一碗米饭,哲学家不是吃饭就是思考。只有哲学家饥饿时,才试图拿起左右两根筷子(一根一根的拿起)。若筷子已在他人手上,则需要等待。饥饿的哲学家只有同时拿起两根筷子才能进餐,进餐完毕后,放下筷子继续思考。

    初始方案

    定义信号量数组chopstick[5] = {1,1,1,1,1} ,用于对 5 根筷子进行互斥访问。哲学家按顺序编号为0~4,哲学家 i 左边筷子编号为 i ,右边筷子编号为 (i+1)%5 。

    semaphore chopstick[5] = {1,1,1,1,1};
    
    philosopher(){
    	while(1){
    		p(chopstick[i]);
             p(chopstick[(i+1)%5]);
    		吃饭;
    		v(chopstick[i]);
             v(chopstick[(i+1)%5]);		
             思考;
    	}
    }
    

    改进方案

    初始方案中,可能存在一种情况:若每名哲学家都拿起一根筷子时,由于没有人有两根筷子,于是谁也不能进餐,每个人都在等待,因此出现了死锁。

    为防止死锁,可对初始方案用以下三个方法解决

    • 方法一:至多允许 4 名哲学家同时进餐
    • 方法二:仅当一名哲学家左右两边的筷子都可用时,才允许他抓起筷子。这样必有一名哲学家可以拿起 2 根筷子
    • 方法三:对哲学家顺序编号,要求齐数号哲学家先拿起左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反

    方法一:至多允许 4 名哲学家同时进餐

    至多只允许四位哲学家同时去拿左筷子,最终能保证至少有一位哲学家能进餐,并在用完后释放两只筷子供他人使用。设置一个初值为 4 的信号量 num,只允许 4 个哲学家同时去拿左筷子,这样就能保证至少有一个哲学家可以就餐,不会出现饿死和死锁的现象

    semaphore chopstick[5] = {1,1,1,1,1};
    semaphore num = 4;
    
    philosopher(int i){
    	while(1){
    		p(num);					//请求进餐
    		p(chopstick[i]);		 //拿左筷子
             p(chopstick[(i+1)%5]);	  //拿右筷子
    		吃饭;
    		v(chopstick[i]);
             v(chopstick[(i+1)%5]);	
             v(num);
             思考;
    	}
    }
    

    方法二:仅当一名哲学家左右两边的筷子都可用时,才允许他抓起筷子

    将拿左右筷子的操作看成一个连贯的操作,在其周围加上pv操作,从而保证拿起筷子的过程不被打断,保证同时持有左右两根筷子

    semaphore chopstick[5] = {1,1,1,1,1};
    semaphore mutex = 1;
    
    philosopher(){
    	while(1){
    		p(mutex);
    		p(chopstick[i]);
             p(chopstick[(i+1)%5]);
             v(mutex);
    		吃饭;
    		v(chopstick[i]);
             v(chopstick[(i+1)%5]);		
             思考;
    	}
    }
    

    方法三:对哲学家顺序编号,要求齐数号哲学家先拿起左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反

    semaphore chopstick[5] = {1,1,1,1,1};
    
    philosopher(int i){
    	while(1){
    		if(i % 2 != 0) {			//若为奇数号哲学家
    			p(chopstick[i]);		//先拿左筷子
             	 p(chopstick[(i+1)%5]);   //后拿右筷子
             	 吃饭;
                 v(chopstick[i]);
                 v(chopstick[(i+1)%5]);	
                 思考;
    		} else {					//若为偶数号哲学家
    			p(chopstick[(i+1)%5]);    //先拿右筷子
    			p(chopstick[i]);		 //后拿左筷子
             	 吃饭;
                 v(chopstick[(i+1)%5]);
                 v(chopstick[i]);
                 思考;
    		}
    	}
    }
    

    4 吸烟者问题

    假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽掉它,但要卷起并抽掉一支烟,抽烟者需要三种材料:烟草、纸、胶水。三个抽烟者分别拥有烟草、纸、胶水。供应者无限提供三种材料,他每次将两种材料放到桌子上,拥有剩下那种材料的抽烟者卷起一根烟并抽掉,并给供应者一个信号告诉已完成,此时供应者会将两外两种材料放到桌子上,如此循环……。

    要求让三个抽烟者轮流抽烟

    int random;
    semaphore offer1 = 0; //对应纸和胶水的资源
    semaphore offer2 = 0; //对应烟草和胶水的资源
    semaphore offer3 = 0; //对应烟草和纸的资源
    semaphore finish = 0;
    
    //供应者进程
    process(){
    	random = 随意一个整数;
    	while(1){
    		flag = random % 3;
    		if(flag == 0)
    			v(offer1);
    		else if(flag == 1)
    			v(offer2);
    		else
    			v(offer3);
    		random++;
    		p(finish);
    	}
    }
    
    //抽烟者进程
    smoker_1(){
    	while(1){
    		p(offer1);
    		拿起纸和胶水,卷烟,抽掉;
    		v(finish);
    	}
    }
    smoker_2(){
    	while(1){
    		p(offer2);
    		拿起胶水和烟草,卷烟,抽掉;
    		v(finish);
    	}
    }
    smoker_3(){
    	while(1){
    		p(offer3);
    		拿起烟草和纸,卷烟,抽掉;
    		v(finish);
    	}
    }
    

    5 理发师问题

    理发店有一位理发师、一把理发椅、n 个供顾客等候用的凳子。若没有顾客,则理发师在理发椅上睡觉。当一位顾客到来时,顾客必须叫醒理发师;若理发师正在理发时又有顾客到来,若有空椅子可坐,则顾客坐下来等待,否则离开。

    分析:

    一把理发椅、n 个供顾客等候用的凳子,则理发店最多可容纳 n+1 人。根据对理发椅处理方法的不同,则有两种解决方法

    • 方法一:将理发椅和凳子看成两种不同的资源
    • 方法二:将理发椅和凳子看成一种资源

    方法一:将理发椅和凳子看成两种不同的资源

    int customer_count = 0;		//记录当前顾客人数
    semaphore mutex = 1;		//用于互斥访问wait_count
    semaphore baber_chair = 1;	//理发椅
    semaphore wait_chair = 1;	//凳子
    semaphore finish = 0;
    semaphore ready = 0;
    
    barber(){
    	while(1){
    		p(ready);	//等候为顾客理发,若无顾客,则睡觉
    		理发;
    		v(finish);	//理发完毕,可为下一位顾客理发
    	}
    }
    customer(){
    	p(mutex);			//互斥访问customers
    	if(customer_count <= n){//还有空位
    		customer_count++;	//进店坐下,空位减一
    		v(mutex);
    	} else {
    		v(mutex);		//没有空位,直接离开
    	}
    	
    	p(wait_chair);		//找一个空凳子坐下
    	p(barber_chair);	//等待坐上理发椅
    	v(wait_chair);		//离开凳子,去坐理发椅
    	v(ready);			//通知理发师理发。若理发师在睡觉,则唤醒之
    	p(finish);			//等待理发完成
    	v(barber_chair); 	//理发完成,离开理发椅
    	p(mutex);			//互斥访问customer_count
    	customer_count--;	//离开,空位加一
    	v(mutex);
    }
    

    方法二:将理发椅和凳子看成一种资源

    int chairs = n+1;
    semaphore ready = 0;
    semaphore finish = 1;
    semaphore mutex = 1;
    
    barber(){
    	while(1){
    		p(ready);	//等候为顾客理发,若无顾客,则睡觉
    		理发;
    		p(mutex);
    		chairs--;
    		v(mutex);
    		v(finish);	//理发完毕,可为下一位顾客理发
    	}
    }
    
    customer(){
    	p(mutex);
    	if(chairs > 0){	//有空位,进店
    		chairs--;
    		v(mutex);
    		v(ready);	//通知理发师理发。若理发师在睡觉,则唤醒之
    		p(finish);	//等待理发完成
    	} else {
    		v(mutex);	//无空位,离开
    	}
    }
    
    展开全文
  • [操作系统]经典进程同步问题题库.doc
  • 2.4经典进程同步问题 1.生产者——消费者问题 无论生产者、消费者使用缓冲池时应保证互斥使用(互斥信号量mutex ) 生产者和消费者间交叉有序: 有序的控制最根源在产品数量上。 设置两个信号量:分别针对生产者、...

    2.4经典进程同步问题


    1.生产者——消费者问题
    无论生产者、消费者使用缓冲池时应保证互斥使用(互斥信号量mutex )
    生产者和消费者间交叉有序:
    有序的控制最根源在产品数量上。
    设置两个信号量:分别针对生产者、消费者设置不同的信号量,empty和full分别表示缓冲池中空缓冲池和满缓冲池(即产品)的数量。
    变量和信号量

    buffer: array [ 0, …, n-1] of item;
    in, out: integer :=0, 0;
    //不使用Counter变量,而是用信号量
    Var  mutex, empty, full: semaphore :=1, n, 0;
    
    
    producer :
    repeat
    … 
    produce an item in nexp;
    …
    wait(empty);
    wait(mutex);
    buffer(in):=nexp;
    in:=(in+1) mod n;
    singal(mutex);
    singal(empty);
    until  false; 
    
    
    
    consumer :
    repeat
    wait(full);
    wait(mutex);
    nextc:=buffer(out);
    out:=(out+1) mod n;
    signal(mutex);
    signal(empty);
    consume the item in nexc; 
    until  false;  
    

    检查:
    每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现。
    控制顺序的信号量empty和full的wait和signal操作,成对地出现在不同的进程中,在每个程序中的多个wait操作顺序不能颠倒。且应先执行对资源信号量的wait操作,再执行对互斥信号量的wait操作,否则可能引起进程死锁。

    模拟交替执行过程,检查控制是否正确。
    2.哲学家进餐问题
    题目描述:
    五个哲学家共用一张圆桌,分别坐在周围的五张椅子上,在桌子上有五只碗和五只筷子,他们的生活方式是交替地进行思考和进餐。平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能进餐。进餐毕,放下筷子继续思考。
    可见:相邻两位不能同时进餐;最多只能有两人同时进餐。
    记录型信号量解决哲学家进餐问题

    Var chopstick: array [0, …, 4] of semaphore;
      
      //所有信号量均被初始化为1。
      //第i 位哲学家的活动可描述为:
    
    repeat
              wait(chopstick[ i ]);     
                    wait(chopstick[ ( i +1) mod 5] );
                     …
                  eat;
    		…
    		signal(chopstick[ i ]);
    		signal(chopstick[ ( i +1) mod 5] );
    		…
    		think;
    until  false;
    

    3.读者——写者问题
    情景:一个数据文件被多个进程共享。Reader进程只要求读文件,Writer进程要求写入内容。
    合理的同步关系是:
    多个读进程可同时读;
    Writer进程与任何其他进程(包括Reader进程或其他Writer进程)不允许同时访问文件。

    读者Reader:
    begin
    repeat
    wait(rmutex); 
    if Readcount=0 then
       wait(wmutex);
    Readcount :=Readcount +1;
     signal(rmutex);
       …  
     perform read operation; 
     …
    wait(rmutex);   
    Readcount :=Readcount -1;
    if Readcount=0 then
    signal(wmutex);
    signal(rmutex);
    until  false;
    end;
    
    展开全文
  • 经典进程同步问题 : 生产者—消费者问题(合作互斥) 是相互合作的进程关系的一种抽象,同时也包含着进程的互斥。 分析 : 空缓冲区不为空,生产者才能将生产的数据放入缓冲区中。 满缓冲区不为空,消费者才能从...

    1 )生产者—消费者问题(合作互斥)

    是相互合作的进程关系的一种抽象,同时也包含着进程的互斥。

    分析 :

    • 空缓冲区不为空,生产者才能将生产的数据放入缓冲区中。
    • 满缓冲区不为空,消费者才能从缓冲区中取数据。
    • 为了保证进程同步,生产者与消费者不可以同时访问缓冲区。

    1)利用记录型信号量解决

    in ;out;//生产者消费者指针
    mutex//缓冲池互斥信号量
    empty//缓冲池空缓冲区数量
    full//缓冲池满缓冲区数量
    /*buffer数组是用来表示缓冲区的,而empty和full是用来表示缓冲区
    的空闲和使用情况的*/
    
    //生产者
    int in=0, out=0;
    item buffer[n];
    semaphore mutex=1, empty=n, full=0;
    void proceducer() {
    	do {
    		producer an item nextp;//生产者生产的产品放入nextp中
    		...
    		wait(empty);//查看有无空闲的缓冲区
    		wait(mutex);//使进程互斥
    		buffer[in] =nextp;//把nextp中的产品送往buffer(in)
    		in :=(in+l) % n;//指针偏移
    		signal(mutex);//释放资源
    		signal(full);//满缓冲区加1
    	   }while(TRUE);
    }
    
    //消费者
    void consumer() {
    do {
    	wait(full);//查看缓冲区是否有数据
    	wait(mutex);//进程互斥
    	nextc= buffer[out];//从buffer(out)中取出产品放入nextc
    	out =(out+l) % n;//指针偏移
    	signal(mutex);//释放资源
    	signal(empty);//空缓冲区加1
    	consumer the item in nextc;//消费nextp中产品
    	}while(TRUE);
    }
    
    
    void main() {
    	cobegin
    	proceducer(); consumer();
    	coend
    }
    

    注意 :

    • 互斥的wait(mutex)和signal(mutex)必须成对地出现;
    • 对资源信号量empty和full的wait和signal操作,同样需要成对地出现,但它们分别处于不同的程序中。
    • 每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作,然后再执行对互斥信号量的wait操作,否则可能引起进程死锁。

    2)利用AND型信号量解决

    即同时实现wait(empty)与wait(mutex)操作,与实现signal(mutex)与signal(full)操作。

    • Swait(empty, mutex) 代替 wait(empty)和 wait(mutex);
    • Ssignal(mutex, full) 代替 signal(mutex)和 signal(full);
    • Swait(full, mutex) 代替 wait(full)和 wait(mutex)
    • Ssignal(mutex, empty) 代替Signal(mutex)和Signal(empty)

    代码如下 :

    int in=0, out=0;
    item buffer[n];
    semaphore mutex=1, empty=n, full=0;
    void proceducer() {
    	do {
    		producer an item nextp;
    		Swait(empty, mutex);
    		buffer[in] =nextp;
    		in :=(in+1) % n;
    		Ssignal(mutex, full);
    	}while(TRUE);
    }
    
    
    
    void consumer() {
    	do {
    		Swait(full, mutex);
    		nextc= buffer[out];
    		out =(out+l) % n;
    		Ssignal(mutex, empty);
    		consumer the item in nextc;
    	}while(TRUE);
    }
    

    2)哲学家进餐问题(资源耗尽,避免死锁)

    临界资源的使用,避免死锁状况的产生。

    解决方法 :

    • 记录型信号量:至多只允许有四位哲学家同时去拿左边的筷子, 最终能保证至少有一位哲学家能够进餐,并在用毕时能释放出他用过的两只筷子, 从而使更多的哲学家能够进餐。

    • AND型信号量: 仅当哲学家的左、 右两只筷子均可用时,才允许他拿起筷子进餐。

    • 数学方法:规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子;而偶数号哲学家则相反。按此规定,将是1、 2号哲学家竞争1号筷子; 3、 4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子, 获得后, 再去竞争偶数号筷子, 最后总会有一位哲学家能获得两只筷子而进餐。

    1)利用记录型信号量解决

    //以第i位哲学家举例
    semaphore chopstick[5]={ 1, 1, 1, 1, 1};
    do {
    	wait(chopstick[i]);
    	wait(chopstick[(i+1)%5]);
    	//eat
    	signal(chopstick[i]);
    	signal(chopstick[(i+l)%5]);
    	//think
    }while[TRUE];
    

    2)利用AND型信号量解决

    semaphore chopstick chopstick[5]={ 1, 1, 1, 1, 1);
    do {
    	...
    	//think
    	Sswait(chopstick[(i+1)%5], chopstick[i]);
    	//eat
    	Ssignal(chopstick[(i+1)%5], chopstick[i]);
    }while[TRUE];
    

    3)读者—写者问题(互斥问题)

    互斥进程的管理 :

    分析 :

    • 允许多个读者同时执行读操作
    • 不允许读者、写者同时操作
    • 不允许多个写者同时操作

    1)记录型信号量解决 (写者优先)

    读进程只要看到有其他读进程正在访问文件,就可以继续作读访问;写进程必须等待所有读进程都不访问时才能写文件,即使写进程可能比一些读进程更早提出申请。所以以上解法实际是 读者优先 的解法。

    wmutex//读写互斥
    readcount//读进程数目
    rmutex//读进程计数
    
    
    semaphore rmutex= 1, wmutex= 1;
    int readcount=0;
    
    //读进程
    void reader() {
    	do {
    		wait(rmutex);//申请读,对读数更改
    		if (readcount==0) wait(wmutex);/*第一个进入进行检验,防止正
    		在写的情况*/
    		readcount++;
    		signal(rmutex);//释放读
    		...
    		perform read operation;
    		...
    		wait(rmutex);//申请读,对读数更改
    		readcount--;//读者数减1
    		if (readcount==0) signal(wmutex);//最后一个离开,唤醒写进程
    		signal(rmutex);//释放读
    	}while(TRUE);
    }
    
    //写进程
    void writer()
    {
    	do {
    		wait(wmutex);//申请写互斥信号量
    		perform write operation;
    		signal(wmutex);//释放信号量
    	}while(TRUE);
    }
    
    
    void main(){
    	cobegin
    		reader(); writer();
    	coend
    }
    

    2)利用信号量集解决有限同时读

    • 允许RN个读者同时执行读操作
    • 不允许读者、写者同时操作
    • 不允许多个写者同时操作
    int RN;
    semaphore L=RN, mx=1;
    void reader() 
    {
    do {
    	Swait(L, 1, 1);//L,下限为1,需求量为1
    	Swait(mx, 1, 0);/*互斥信号量,下限为1,需求为0,当有写时mx为0,
    	读失败*/
    	...
    	perform read operation;
    	...
    	Ssignal(L, 1)//释放资源
    	}while(TRUE);
    }
    
    void writer()
    {
    	do {
    	Swait(mx, 1, 1; L, RN, 0);/*既无writer写(mx=1),也无
    	reader读(L=RN),writer进入临界区写*/
    	perform write operation;
    	Ssignal(mx, 1);
    	}while(TRUE);
    }
    

    3)读者—写者写操作优先:

    每个读进程最开始都要申请一下S信号量,之后在真正做读操作前即让出(使得写进程可以随时申请到 S)。而只有第一个写进程需要申请 S,之后就一直占着不放了,直到所有写进程都完成后才让出。等于只要有写进程提出申请就禁止读进程排队,变相提高了写进程的优先级。

    semaphore rmutex=1,wmutex= 1, S=1, w=1;
    int Readcount=0, Writecount=0;
    
    //读进程
    void reader() {
    	do {
         	wait(S);//对读进程加以限制
            wait(rmutex);//读计数
            if(Readcount=0)wait(wmutex);//在无读者的情况下检验是否在写
            Readcount++;//读者数加1
            signal(rmutex);//释放读计数
          	signal(S);//加以限制
          	...
    		perform read operation;
    		...
    		wait(rmutex);
            Readcount--;
            if(Readcount=0)signal(wmutex);//最后一个;离开唤醒写进程
          	signal(rmutex)
    	}while(TRUE);
    }
    
    
    void writer{
    	  do {
    	  wait(w);
          if(Writecount=0)wait(S);//此时新的读者无法再进入读
          Writecount++;
          siganl(w);
          wait(wmutex);//写进程被唤醒后进行写操作
          ...
          perform write operation;//此时一直占据着信号量S,写进程一旦进入则顺序执行
          ...
          signal(wmutex);
          wait(w);
          Writecount--;
          if(Writecount=0)signal(S);//当所有写进程完成才归还信号量,读者可以再次进入临界区
          siganl(w);
    }while(TRUE);
    }
    

    4)读者—写者问题公平竞争

    方法相同,读写排队,谁先到拿到S,谁先操作。

    void reader() {
    	do {
         	wait(S);//对读进程加以限制
            wait(rmutex);//读计数
            if(Readcount=0)wait(wmutex);//在无读者的情况下检验是否在写
            Readcount++;//读者数加1
            signal(rmutex);//释放读计数
          	signal(S);//加以限制
          	...
    		perform read operation;
    		...
    		wait(rmutex);
            Readcount--;
            if(Readcount=0)signal(wmutex);//最后一个;离开唤醒写进程
          	signal(rmutex)
    	}while(TRUE);
    }
    
    void writer(){
        while(1){
            wait(S);//读写同时排队,谁先来谁先用
            wait(wmutex);
            signal(S);
            ...
            perform write operation
            ...
            signal(wmutex);
        }
    }
    
    展开全文
  • 经典进程同步问题之生产者消费者问题 什么是生产者消费者问题 学术性描述:生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是:有一群生产者进程在生产产品,并将这些产品提供给消费者进程...

    经典进程同步问题之生产者消费者问题


    什么是生产者消费者问题

    学术性描述:生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是:有一群生产者进程在生产产品,并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行,在两者之间设置了一个具有n 个缓冲区的缓冲池,生产者进程将它所生产的产品放入一个缓冲区中;消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的,但它们之间必须保持同步,即不允许消费者进程到一个空缓冲区去取产品,也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。其大概结构图如下:
    生产者-消费者模型

    通俗描述:生产者-消费者问题在生活中实际上有许多例子,比如吃自助餐的过程,由于由于桌子上摆放食物的空间是有限的,因此当厨师用食物将桌子摆满之后就不能再放了,要等到有顾客来取走食物余出空间之后才能够继续摆放食物。而顾客在取食物的过程中也不是说可以无限去取的,当桌子上没有食物的时候,顾客显然是无法获得食物,此时他需要等待,等着厨师把食物放到桌子上之后,才能继续取。这整个过程其实就是一个生产者-消费者问题。

    代码实现

    semaphore mutex=1;                                         //临界区互斥信号量                      
    semaphore empty=n;                                         //空闲缓冲区
    semaphore full=0;                                          //缓冲区初始化为空
    producer() {                                               //生产者进程
        while (1) {
            produce an item in nextp;                          //生产数据
            P (empty); (要用什么, p 一下)                      //进入临界区                            
            P (mutex); (互斥夹紧)                              //将数据放入缓冲区
            add nextp to buffer; (行为) V (mutex); (互斥夹紧) //离开临界区,释放互斥信号量
            V (full); (提供什么,v 一下)                       //满缓冲区数加1
        }
    }
    consumer(){                                                //消费者进程
        while(1){  
            P(full);                                           //获取满缓冲区单元
            P(mutex);                                          //进入临界区
            remove an item from buffer;                        //从缓冲区中取出数据
            V(mutex);                                          //离开临界区,释放互斥信号量
            V(empty);                                          //空缓冲区数加1
            consume the item;                                  //消费数据
       }
    }
    
    展开全文
  • 实验4 经典进程同步问题的实现

    千次阅读 2017-12-21 21:47:13
    实验4 经典进程同步问题的实现 一、实验目的 1. 掌握信号通信机制 2. 使用信号量机制实现经典进程同步的生产者和消费者问题 二、实验工具与设备 装有Linux系统的计算机。 三、实验预备知识 1.创建多个线程,...
  • 操作系统经典进程同步问题之哲学家进餐问题 哲学家进餐问题 1.问题描述:有五位哲学家,它们的生活方式是交替的进行思考和进餐。哲学家门共用一张圆桌,分别坐在周围的五张椅子上。在圆桌上有五只碗和五根筷子,平时...
  • 关键词:进程同步;生产者-消费者问题;读者-写者问题;哲学家进餐问题 信号量机制可以实现互斥、同步、对一类系统资源的申请和释放。 一般来说,要实现互斥,可以设置初值为1的互斥信号量,在访问临界区之前,对这...
  • 三 :进程同步 为保证多个程序并发执行时,保留可再现性,在多道程序系统中,必须引入进程同步机制。 进程同步机制的主要任务,是对多个相关进程在执行次序上进行协作,使并发执行的诸进程之间能按照一定的规则(或...
  • 调度算法、进程同步问题调度算法FSFC(先来先服务)SJF(短作业优先)优先级队列算法响应比优先算法时间片轮转算法多级反馈队列算法经典进程同步问题生产者消费者问题读者-写者问题哲学家进餐问题吸烟者问题 ...
  • 吸烟者问题是为了解决“可以生产多个产品的单生产者”问题提供了一个思路。 问题描述:有三个抽烟者和一个供应者。每个抽烟者不停地卷烟抽,组成一根烟需要三...供应者与三个抽烟者分别是同步关系。供应着无法同时满足
  • 操作系统之经典进程同步问题

    千次阅读 2017-12-02 15:20:55
    这里介绍三中进程同步问题:  1.生产者-消费者问题  2.读者-写者问题  3.哲学家进餐问题 一、生产者-消费者问题  1.问题描述:生产者-消费者模型描述的是有一群生产者进程在生产产品,并将这些产品提供给消费...
  • 生产者-消费者问题是一个著名的进程同步问题。 它描述的是:有一群生产者进程在生产产品,并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行,在两者之间设置了一个具有n个缓冲区的缓冲池...
  • 问题描述:有读者和写者两组并发进程,共享一个文件,当两个或以上的读进程同时访问共享数据时不会产生副作用,但是如果某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,088
精华内容 435
关键字:

经典进程同步问题