Operating System——Classic Process Synchronization Problem

Posted by Sakura on June 23, 2018

操作系统————经典进程的同步问题

前言

操作系统原理是武汉大学计算机学院软件工程专业大二下半学期所学习的一门专业课,教材为西安电子科技大学出版社的计算机操作系统第4版,这个专题的博客为该课程的学习笔记,该博客主要介绍一些经典的进程同步的问题


生产者-消费者问题

生产者-消费者问题描述: 一组生产者进程向一组消费者进程提供产品,它们共享一个有界缓冲池。缓冲池中的每个缓冲区可以存放一个产品,生产者进程不断生产产品并将产品放入缓冲池中,消费者进程不断从缓冲池内取出产品并消费。

同步关系:当缓冲池满时生产者进程需等待,当缓冲池空时消费者进程需等待。诸进程应互斥使用缓冲池。

用记录型信号量解决该问题

设置两个同步信号量empty、full,分别表示空缓冲区的数量和满缓冲区的数量,empty 初值为n,full初值为0。

有界缓冲池是一个临界资源,还需要设置一个互斥信号量mutex,其初值为1。

生产者-消费者问题的同步描述如下:

描述

注意:

  • 在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现
  • 对资源信号量empty和full的wait和signal操作同样需要成对地出现,但它们处在不同的程序中
  • 无论在生产者进程还是在消费者进程中,wait操作的次序都不能颠倒,否则将可能造成死锁。应先执行对资源信号量的wait操作,再执行对互斥信号量的wait操作。

用AND信号量解决该问题

描述


哲学家进餐问题

有五个哲学家,他们的生活方式是交替地进行思考和进餐。

哲学家们共用一张圆桌,分别坐在周围的五张椅子上,在圆桌上有五个碗和五支筷子。

平时哲学家进行思考,饥饿时便试图取其左、右最靠近他的筷子,只有在他拿到两支筷子时才能进餐。

进餐完毕,放下筷子又继续思考。

用记录型信号量解决该问题

用五支筷子的信号量构成信号量数组,其中所有信号量初值为1 :

var chopstick: array[0,…,4] of semaphore ;

其中第i个哲学家的活动算法描述:

wait(chopstick[i]);   //拿左边筷子
wait(chopstick[(i+1) mod 5]); //拿右边筷子
进餐;
signal(chopstick[i]); //放下左边筷子
signal(chopstick[(i+1) mod 5]);//放下右边筷子
思考;

上述算法有可能引起死锁——当五个哲学家同时感觉饥饿,且同时拿起自己左边的筷子…

对于这样的死锁问题有如下办法解决:

(1)至多允许四个哲学家去拿左边的筷子,最终能保证至少有一位哲学家能够进餐

(2)仅当左、右两支筷子均可用时,才允许拿起筷子进餐。

(3)奇数号哲学家先拿左边筷子再拿右边筷子,偶数号哲学家相反。

用AND信号量解决该问题

每个哲学家要先获得两个临界资源(筷子)后方能进餐,用AND信号量机制可获得最简洁的解法。算法流程如下:

Swait(chopstick[i], chopstick[(i+1) mod 5); 
进餐;
Ssignal(chopstick[i],chopstick[(i+1) mod 5]);
思考;

读者-写者问题

一个数据对象(如文件或记录)可以被多个并发进程所共享。

其中有些进程只要求读数据对象的内容(称为读者),而另一些进程则要求修改或写数据对象的内容(称为写者)。

允许多个读者同时读此数据对象,但是一个写者不能与其他进程(不管是写者还是读者)同时访问此数据对象。

解决思路:写者是比较简单的,它和任何进程互斥,用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂,它必须实现与写者互斥的同时还要实现与其他读者的同步,因此,仅仅简单的一对P操作、V操作是无法解决的。那么,在这里用到了一个计数器,用它来判断当前是否有读者读文件。当有读者的时候写者是无法写文件的,此时读者会一直占用文件,当没有读者的时候写者才可以写文件。同时这里不同读者对计数器的访问也应该是互斥的。

为解决读者写者问题,应设置两个信号量和一个共享变量:

共享整型变量readcount,用于记录当前正在读数据的读者数目,初值为0;

信号量rmutex,用于使读者互斥地访问共享变量readcount,其初值为1;

信号量wmutex,用于实现写者与读者的互斥以及写者与写者的互斥,其初值为1;

读者描述:

wait(rmutex);
if (readcount=0) then wait(wmutex);          	    
readcount:=readcount+1;            
signal(rmutex);
读数据;
wait(rmutex) ;
readcount:=readcount-1 ;
if (readcount=0) then signal(wmutex);
signal(rmutex);

写者描述:

wait(wmutex);
写数据;
signal(wmutex);

注意:如果有一个写者在临界区内,且n个读者处于等待,那么一个读者在wmutex上排队,而n-1个读者在rmutex上排队。


总结

总结wait和signal操作的优缺点

  • 优点
    • 简单
    • 表达能力强
    • 用wait、signal操作可解决任何同步互斥问题)
  • 缺点:
    • wait、signal操作使用不当会出现死锁;
    • 遇到复杂同步互斥问题时实现复杂。

附:第二章部分题目总结

1.试比较程序和进程的异同

①每个进程实体中包含了程序段和数据段两部分,因此说进程和程序是紧密相关的。但从结构上看,进程实体还必须包含一个数据结构,即PCB

②进程是程序的一次执行过程,是动态的。由创建而产生、由调度而执行、由撤销而消亡,具有一定生命期。程序是静态的。

③多个进程实体可同时存放在内存中并发执行。而程序的并发执行具有不可再现性,因此程序不能正确地并发执行。

④进程与程序不一一对应。同一个程序的多次运行将形成多个不同的进程,同一个程序的一次执行也可以产生多个进程,一个进程在其生命期的不同时候可以执行不同的程序。

2.绝对不可能发生的状态转换是就绪->阻塞,一般不会发生的状态转换是阻塞->执行

3.进程的就绪、阻塞、执行等基本状态和保存在堆栈中的函数参数、函数返回地址都不属于CPU现场信息

4.在分时系统中导致进程创建的典型事件是用户登录,在批处理系统中导致进程创建的典型事件是作业调度

5.用信号量S实现对系统中4台打印机的互斥使用,S.value的初值应设置为4. 若S.value的当前值为-1,则表示S.L队列中有1个等待进程。

6.设有10个进程共享一个互斥段,如果最多允许有一个进程进入互斥段,则所采用的互斥信号量初值应设置为1,而该信号量的取值范围为-9~1 ;如果最多允许有3个进程同时进入互斥段,则所采用的互斥信号量初值应设置为3

7.使用mail命令的信箱通信属于非实时通信,因为信息是被发送到接收方的信箱中;使用write命令实现的是实时通信,因为信息是被送到收方的屏幕。使用共享文件进行通信的方式属于管道通信

8.信号量的初值不能为负数