操作系统课件(第四章)

操作系统

OperatingSystems

操作系统课程组南京邮电大学WINDOWSUNIXLINUXOS2VxWorksMacOS教材：《操作系统教程》，人民邮电出版社

，2009年出版第三章并发进程

4.1并发进程4.2临界区管理4.3信号量与P、V操作4.4进程间通信4.5死锁4.6管程4.1并发进程4.1.1顺序程序与并发进程4.1.2与时间有关的错误4.1.3进程间的联系4.1.1顺序程序与并发进程1、顺序程序顺序程序：指令或语句序列，体现了某种算法，所有程序是顺序的顺序环境：在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响4.1.1顺序程序与并发进程1、顺序程序的特征：顺序性执行封闭性，独占资源确定性，即可再现性4.1.1顺序程序与并发进程2、并发进程并发环境：

在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的BAABBAAB4.1.1顺序程序与并发进程2、并发进程的特征：间断性执行，执行--停--执行资源共享，多个进程共享使用系统资源不可再现性，执行结果不确定独立性和制约性程序和进程不再一一对应4.1并发进程4.1.1顺序程序与并发进程4.1.2与时间有关的错误4.1.3进程间的联系4.1.2与时间有关的错误1、并发进程交替使用共享资源时可能出现的错误：例如：P1和P2是两个并发进程P1:①R1=C; ②R1=R1+1; ③C=R1;P2:④R2=C; ⑤R2=R2+1; ⑥C=R2;P1全部执行完毕后再执行P2，则C增加2若P2中的④在P1中的③之前执行，则C增加1原因是没有正确地控制对共享变量C的访问4.1.2与时间有关的错误2、飞机订票问题：P1和P2是两个并发的终端订票进程，x=10P1:①Read(x); ②ifx>=1thenx:=x-1; ③write(x);P2:④Read(x); ⑤ifx>=1thenx:=x-1; ⑥write(x);

P1全部执行完毕后再执行P2，则x=8若P2中的④在P1中的③之前执行，则x=9出现了1张票卖给2个客户的情况，原因是没有正确地控制对共享变量x的访问4.1.2与时间有关的错误3、缓冲区读写问题：get、copy、put是3个并发进程getcopyputfstg4.1并发进程4.1.1顺序程序与并发进程4.1.2与时间有关的错误4.1.3进程间的联系4.1.3进程间的联系1、间接式与直接式制约：直接式制约：一程序段等待另一程序段的执行结果间接式制约：并发程序段竞争同一资源2、相交进程与无关进程：相交进程：并发进程在逻辑上有某种联系无关进程：逻辑上无任何联系的并发进程直接作用只发生在相交进程之间；间接作用可以发生在相交进程之间，也可发生在无关进程之间4.1.3进程间的联系3、进程的同步与互斥：进程同步（直接作用）：根据一定的时序关系合作完成一项任务并发进程因直接制约而互相等待，彼此相互发送消息进行合作，使得各进程按一定的速度执行进程互斥（间接作用）：各进程竞争使用临界资源临界资源：一次只允许一个进程使用的系统资源进程互斥是进程同步的一种特殊情况第三章并发进程

4.1并发进程4.2临界区管理4.3信号量与P、V操作4.4进程间通信4.5死锁4.6管程4.2临界区管理4.2.1临界区及其使用原则4.2.2实现临界区管理的软件方法4.2.3实现临界区管理的硬件方法4.2.1临界区及其使用原则临界区：进程中涉及临近资源的程序段为临界区/互斥区，多个进程的临界区为相关临界区临界区的使用原则：有空让进 无空等待多中择一有限等待让权等待解决进程互斥的两种做法：由竞争各方平等协商解决，包括硬件、软件两类方法。引入进程管理者来协调竞争各方对互斥资源的使用

4.2临界区管理4.2.1临界区及其使用原则4.2.2实现临界区管理的软件方法4.2.3实现临界区管理的硬件方法4.2.2实现临界区管理的软件方法1、两个失败的尝试（1）boolinside1=false;boolinside2=false;cobeginprocessP1 processP2 while(inside2)do while(inside1)do beginend; beginend; inside1:=true; inside2:=true;

临界区； 临界区; inside1=false; inside2=false;} }coend4.2.2实现临界区管理的软件方法1、两个失败的尝试（2）boolinside1:=false;boolinside2:=false;cobeginprocessP1 processP2begin begin inside1:=true; inside2=true; while(inside2)do while(inside1)do beginend; beginend;

临界区； 临界区; inside1:=false; inside2:=false;end endcoend4.2.2实现临界区管理的软件方法2、成功解决方法（Dekker算法）varinside:array[1..2]ofBoolean;inside[1]=false;inside[2]=false;turn:integer;turn:=1or2;cobeginprocessP1 begininside[1]:=true;whileinside[2]doifturn=2thenbegininside[1]:=false;whileturn=2dobeginend;inside[1]:=true;end

临界区;turn:=2；

inside[1]:=false;end;coendprocessP2 begininside[2]:=true;whileinside[1]doifturn=1thenbegininside[2]:=false;whileturn=1dobeginend;inside[2]:=true;end

临界区;turn:=1；

inside[2]:=false;end;4.2临界区管理4.2.1临界区及其使用原则4.2.2实现临界区管理的软件方法4.2.3实现临界区管理的硬件方法4.2.3实现临界区管理的硬件方法通过专门提供的硬件指令管理临界区1、测试并建立指令TS s代表临界资源状态，由TS指令控制s:boolean; s:=true;processPi/*i=1,2,…,n*/pi:boolean;beginrepeatpi:=TS(s)untilpi；临界区;s:=true；end;

4.2.3实现临界区管理的硬件方法2、交换指令SWAP

交换指令将交换两个字的内容。公共变量lock表临界区是否上锁，每个进程的私有变量key用于与lock交换。voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}key=true;do{SWAP(&lock,key);}while(key);临界区lock:=false;4.2.3实现临界区管理的硬件方法3、开关中断指令进入临界区前执行“关中断”指令；离开临界区后，执行“开中断”指令，从而控制进程互斥进入临界区硬件方法解决临界区的管理较为简单有效，其缺点主要在于会导致“忙等待”会导致“饥饿”中断屏蔽方法代价较高，不适应多处理器第三章并发进程

4.1并发进程4.2临界区管理4.3信号量与P、V操作4.4进程间通信4.5死锁4.6管程4.3信号量与P、V操作4.3.1信号量定义4.3.2P、V操作定义4.3.3信号量的使用4.3.4信号量及P、V操作讨论4.3.5信号量与P、V操作经典问题4.3.6POSIX信号量4.3.7Linux中的信号量机制4.3.1信号量定义1、信号量的提出1965年荷兰学者Dijkstra提出信号量（semaphore）与P、V操作机制，这一机制是系统用于管理公有资源的有效手段信号量是一个数据结构，负责协调各个进程，以保证它们能够正确、合理的使用公共资源2、信号量定义Structsemaphore{intvalue; //信号量的值

pointerPCBqueue; //信号量队列指针

}信号量说明：semaphores4.3.1信号量定义3、信号量的特性信号量代表对某种公共资源的管理（如停车场的看门人），其值是一个非负整数（如停车场内的车位数）要使用资源的进程（如要进入停车场的车）需通过信号量，有资源时顺利通过（有车位时，看门人打开车栏）；若没有资源可用（如空车位为0），则所有进程都将进入对应信号量的等待队列（如车子在看门人看守的车栏外排队等待）当一个进程归还资源（如车开出停车场）时，此时若信号量队列有等待进程则释放一个（如让一辆车进入停车场）4.3信号量与P、V操作4.3.1信号量定义4.3.2P、V操作定义4.3.3信号量的使用4.3.4信号量及P、V操作讨论4.3.5信号量与P、V操作经典问题4.3.6POSIX信号量4.3.7Linux中的信号量机制4.3.2P、V操作定义1、什么是P、V操作P、V操作是能对信号量进行处理的唯一两个操作，是不可分割的一段程序，为原语操作（执行过程中不允许被中断）P操作用于申请信号量管理的资源（如停车场一例中需要进入停车场使用车位的车就应执行P操作）V操作用于释放资源（如停车场一例中需要开出停车场归还车位的车就应执行V操作）4.3.2P、V操作定义2、P操作P(s){

s.value=s.value－－; //s.value减1if(s.value<0) //该进程被阻塞，进入相应队列，然后转进程调度

{

该进程状态置为等待状态;

将该进程的PCB插入相应的等待队列s.queue的末尾;} //若s.value减1后仍大于或等于零，则进程继续执行

}

4.3.2P、V操作定义3、V操作V(s){

s.value=s.value++; //s.value加1if(s.value<=0)//从队列中唤醒一等待进程，然后继续执行或转进程调度

{

唤醒相应等待队列s.queue中等待的一个进程;

改变其状态为就绪态，并将其插入就绪队列;}//若相加结果大于零，则进程继续执行}4.3信号量与P、V操作4.3.1信号量定义4.3.2P、V操作定义4.3.3信号量的使用4.3.4信号量及P、V操作讨论4.3.5信号量与P、V操作经典问题4.3.6POSIX信号量4.3.7Linux中的信号量机制4.3.3信号量的使用1、使用注意事项：必须置一次且只能置一次初值，且初值不能为负数；只能执行P、V操作

2、用信号量及P、V操作解决进程间互斥问题

mutex:semaphore;mutex:=1;cobegin

processPibegin…

P(mutex);临界区；V(mutex);…end;coend;4.3.3信号量的使用用信号量及P、V操作解决机票问题varA:ARRAY[1..m]OFinteger;mutex:semaphore;mutex:=1;cobegin

processPi

varXi:integer;begin

L1:

按旅客要求找到A[j];

P(mutex)Xi:=A[j];Coend

ifXi>=1thenbeginXi:=Xi-1;A[j]:=Xi;

V(mutex);输出一张票;end;elsebegin

V(mutex);输出票已售完;end;

gotoL1;end;

4.3.3信号量的使用3、用信号量及P、V操作解决进程间同步问题

生产者-消费者问题问题描述：生产者往缓冲区中放产品，消费者从缓冲区中取产品，如下图所示生产者P进程不能往“满”的缓冲区中放产品，设置信号量为S1，初值为1，代表缓冲区有1个空闲空间消费者Q进程不能从“空”的缓冲区中取产品，设置信号量S2

，初值为0，代表缓冲区有0个产品4.3.3信号量的使用3、用信号量及P、V操作解决进程间同并不斥问题P //生产者进程while(true){

生产一个产品;

P(s1); //初值为1

送产品到缓冲区;

V(s2);};C //消费者进程while(true){

P(s2); //初值为0

从缓冲区取产品;

V(s1);

消费产品;};4.3信号量与P、V操作4.3.1信号量定义4.3.2P、V操作定义4.3.3信号量的使用4.3.4信号量及P、V操作讨论4.3.5信号量与P、V操作经典问题4.3.6POSIX信号量4.3.7Linux中的信号量机制4.3.4信号量及P、V操作讨论1、信号量及P、V操作的物理含义①

S>0表示有S个资源可用②S=0表示无资源可用③S<0则|S|表示S等待队列中的进程个数④P(S)表示申请一个资源⑤V(S)表示释放一个资源4.3.4信号量及P、V操作讨论2、P、V操作必须成对出现，有一个P操作就一定有一个V操作①当为互斥操作时，它们处于同一进程②当为同步操作时，则不在同一进程中出现③如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要，一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前，而两个V操作无关紧要4.3.4信号量及P、V操作讨论3、信号量及P、V的优缺点①优点：简单且表达能力强，用P、V操作可解决任何同步、互斥问题②缺点：不够安全，P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂4.3信号量与P、V操作4.3.1信号量定义4.3.2P、V操作定义4.3.3信号量的使用4.3.4信号量及P、V操作讨论4.3.5信号量与P、V操作经典问题4.3.6POSIX信号量4.3.7Linux中的信号量机制4.3.5信号量与P、V操作经典问题1、哲学家吃通心面问题问题描述：5个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。每个哲学家必须直接从自己左边和右边同时获得两把叉子才能吃面解决思路：5位哲学家看作5个进程，需要互斥使用5把叉子，这5把叉子是共享资源，用5个信号量表示4.3.5信号量与P、V操作经典问题varfork[I]:array[0..4]ofsemaphore;fork[i]:=1;cobegin

processPi//i=0,1,2,3,4,beginL1:思考；

P(fork[i]);//叉子逆时针编号，先拿左边叉子

P(fork[(i+1)mod5]);//再拿右边叉子吃通心面;

V(fork[i]); //归还左边叉子

V(fork[(i+1)mod5]); //归还右边叉子

gotoL1;end;coend

4.3.5信号量与P、V操作经典问题上述解法保证了对叉子的互斥使用，但可能出现每位哲学家均拿起左边叉子而同时又等待拿右边叉子的情况，发生死锁，可通过下列几种办法避免死锁：至多允许4个哲学家同时吃奇数号先取左手边的叉子，偶数号先取右手边的叉子每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取

4.3.5信号量与P、V操作经典问题2、生产者消费者问题问题描述：若干进程通过K个有限共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出。任何时刻只能有一个进程可对共享缓冲区进行操作。且满足条件：①消费者想接收数据时，有界缓冲区中至少有一个单元是满的；②生产者想发送数据时，有界缓冲区中至少有一个单元是空的解决思路：设置3个信号量full表示“满”数目，即产品数，初值为0

empty表示“空”数目，初值为K；full+empty==K

mutex用于访问缓冲区时的互斥，初值是1

4.3.5信号量与P、V操作经典问题varB:array[0..k-1]ofitem;in,out:integer:=0;//缓冲区读写指针empty,full,mutex:semaphore;empty:=k;full:=0;mutex:=1;cobegin

processproducer_ibeginL1:produceaproduct;

P(empty);P(mutex);

B[in]:=product;In:=(in+1)modk;

V(mutex);V(full);

GotoL1;end;

coend

processconsumer_j

beginL2:P(full);P(mutex);Product:=B[out];out:=(out+1)modk;

V(mutex);V(empty);Consumeaproduct;

GotoL2;end;

4.3.5信号量与P、V操作经典问题varB:array[0..k-1]ofitem;in,out:integer:=0;//缓冲区读写指针empty,full,mutex:semaphore;empty:=k;full:=0;mutex:=1;cobegin

processproducer_ibeginL1:produceaproduct;

P(mutex);P(empty);?

B[in]:=product;In:=(in+1)modk;

V(mutex);V(full);

GotoL1;end;

coend

processconsumer_j

beginL2:P(full);P(mutex);?Product:=B[out];out:=(out+1)modk;

V(mutex);V(empty);Consumeaproduct;

GotoL2;end;

4.3.5信号量与P、V操作经典问题3、苹果桔子问题问题描述：桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果（apple），妈妈专向盘子中放桔于（orange）；一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果解决思路：生产者消费者问题的变形，有两类生产者和两类消费者，仍然设置3个信号量sp表示盘子能放的水果数目，初值为1sg1表示盘子里有无桔子，初值为0Sg2表示盘子里有无苹果，初值为0

4.3.5信号量与P、V操作经典问题sp,sg1,sg2:semaphore;sp:=1;sg1,:=0;sg2:=0;cobegin

processfatherbeginL1:削一个苹果；

P(sp);放苹果; V(sg2);gotoL1;end;processmotherbeginL2:剥一个桔子；

P(sp);放桔子；

V(sg1);gotoL2;end;coend

processdaughterbeginL4:P(sg2);取苹果；

V(sp);吃苹果；

gotoL4;end;processsonbeginL3:P(sg1);取桔子；

V(sp);吃桔子；

gotoL3;end;4.3.5信号量与P、V操作经典问题4、读者和写者问题问题描述：读者和写者两组并发进程共享一个文件F，要求允许多个读者同时执行读操作，任一写者在完成写操作之前不允许其他读者或写者工作，写者执行写操作前，应让已有的写者和读者全部退出

解决思路：设置2个信号量W和R，1个控制变量rcW控制读写进程对文件的互斥访问，初值为1R控制各个读进程对rc的互斥访问，初值为1rc记录正在读文件的进程数，初值为04.3.5信号量与P、V操作经典问题varrc:integer;rc:=0;W，R:semaphore;W:=1;R:=1;cobegin

procedureread;begin

P(R);

rc:=rc+1;

ifrc=1thenP(W)；

V(R);

读文件；

P(R);

rc:=rc-1;

ifrc=0thenV(W)；

V(R);end;coend

procedurewrite;begin

P(W);

写文件;

V(W);end;

4.3.5信号量与P、V操作经典问题5、理发师问题问题描述：理发店有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。没顾客时理发师在理发椅上睡觉，顾客来时必须叫醒理发师，如果其正在理发则坐下来等待，没有空椅子坐就离开解决思路：设置1个控制变量waiting和3个信号量waiting记录等候理发的顾客数，初值为0customers表等候理发的顾客数，可阻塞理发师进程，初值为0barbers表正在等候顾客的理发师数，可阻塞顾客进程，初值为0mutex用于互斥修改waiting，初值为14.3信号量与P、V操作4.3.1信号量定义4.3.2P、V操作定义4.3.3信号量的使用4.3.4信号量及P、V操作讨论4.3.5信号量与P、V操作经典问题4.3.6POSIX信号量4.3.7Linux中的信号量机制4.3.6POSIX信号量1、POSIX有两种信号量的实现机制：无名信号量：可以用在共享内存的情况下，如实现进程中各个线程之间的互斥和同步命名信号量：通常用于不共享内存的情况下，如不共享内存的进程之间本节所介绍的函数和数据结构需要引用头文件semaphore.h

4.3.6POSIX信号量2、POSIX无名信号量sem_init

函数：初始化指定的信号量int

sem_init(sem_t*sem,int

pshared,unsignedvalue);sem

指向要初始化的信号量value为信号量的初始值pshared

用于说明信号量的共享范围如果成功，sem_init

返回0，如果不成功，sem_init

返回-1并设置errno

4.3.6POSIX信号量sem_destroy函数：销毁一个指定的信号量intsem_destroy(sem_t*sem);sem：指向要销毁的信号量的指针如果成功sem_destroy

返回0，如果不成功返回-1并设置errno

。如果*sem

不是有效的信号量，sem_destroy

就将errno

置为EINVALsem_post

函数：实现对指定信号量的signal操作int

sem_post(sem_t*sem);如果成功sem_post

返回0。如果不成功

返回-1并设置errno

。如果*sem

不是有效的信号量，sem_post

就将errno

置为EINVAL4.3.6POSIX信号量sem_wait

函数：实现对指定信号量的wait操作int

sem_wait(sem_t*sem);sem_trywait

函数与sem_wait

类似，只是在试图对一个为零的信号量进行操作时，它不会阻塞调用线程，而是立即返回int

sem_trywait(sem_t*sem);如果成功这两个函数返回0，如果不成功这些函数返回-1并设置errno

sem_post、sem_wait

和sem_trywait

同样可用于命名信号量

4.3.6POSIX信号量3、POSIX命名信号量命名信号量有一个名字、一个用户ID、一个组ID和权限，它们是提供给那些不共享内存进程的使用接口命名信号量的名字是一个遵守路径名构造规则的字符串sem_open

函数：创建或打开一个命名信号量sem_t*sem_open(constchar*name,int

oflag);name是一个标识信号量的字符串oflag

用来确定是创建信号量还是连接已有信号量。如设置了oflag

的O_CREAT比特位，则会创建一个新的信号量4.3.6POSIX信号量sem_close

函数：关闭命名信号量int

sem_close(sem_t*sem);sem指向要关闭的信号量的指针成功返回0，不成功返回-1并设置errno单个程序可以用sem_close

函数关闭命名信号量，但是这样做并不能将信号量从系统中删除，因为命名信号量在单个程序的执行之外是具有持久性的当进程调用_exit、exit、exec或从main返回时，进程打开的命名信号量同样会被关闭4.3.6POSIX信号量sem_unlink

函数：在所有进程关闭了命名信号量之后，将信号量从系统中删除int

sem_unlink(constchar*name);name为要删除的命名信号量的名字如果成功，sem_unlink返回0，如果不成功，sem_unlink返回-1并设置errno4.3信号量与P、V操作4.3.1信号量定义4.3.2P、V操作定义4.3.3信号量的使用4.3.4信号量及P、V操作讨论4.3.5信号量与P、V操作经典问题4.3.6POSIX信号量4.3.7Linux中的信号量机制4.3.7Linux中的信号量机制1、Linux中的基本信号量机制Linux内核的信号量在概念和原理上和用户态的SystemV的IPC机制信号量相同，但它绝不可能在内核外使用只有一个持有者的信号量叫二值信号量或互斥信号量允许有多个持有者的信号量叫计数信号量，在初始化时要说明最多允许有多少个持有者（Count值）当任务访问完被信号量保护的共享资源后，必须释放信号量，释放信号量通过把信号量的值加1实现，假如信号量的值为非正数，表明有任务等待当前信号量，因此它也唤醒任何等待该信号量的任务4.3.7Linux中的信号量机制2、信号量声明StaticDECLARE_SEMAPHORE_GENERIC(name,count);声明互斥信号量的快捷方法：

StaticDECLARE_MUTEX(name);DECLARE_MUTEX(name)：该宏声明一个信号量name并初始化它的值为0，即声明一个互斥锁DECLARE_MUTEX_LOCKED(name)：该宏声明一个互斥锁name，但其初始值配置为0，即锁在创建时就处在已锁状态。因此对于这种锁，一般是先释放后获得4.3.7Linux中的信号量机制3、信号量初始化voidsema_init(structsemaphore*sem,int

val);将信号量sem初始值配置为valvoidinit_MUTEX(structsemaphore*sem);初始化一个互斥锁，将信号量sem的值配置为1voidinit_MUTEX_LOCKED(structsemaphore*sem);也用于初始化一个互斥锁，但将信号量sem的值配置为0，即一开始就处在已锁状态

4.3.7Linux中的信号量机制4、信号量获取voiddown(structsemaphore*sem);会导致睡眠，不能在中断上下文使用。该函数将把sem的值减1，非负就直接返回，否则挂起调用者，等待别的任务释放该信号量int

down_interruptable(structsemaphore*sem);可能被信号打断，可通过有返回值来区分是正常返回（返回0）还是被信号中断（返回-EINTR）int

down_trylock(structsemaphore*sem);尝试获得信号量sem，假如能够立即获得，它就获得该信号量并返回0，否则，返回值为非0值。它不会导致调用者睡眠，能够在中断上下文使用

4.3.7Linux中的信号量机制5、信号量释放voidup(structsemaphore*sem);释放信号量sem，即把sem的值加1，假如sem的值为非正数，表明有任务等待该信号量，则将唤醒这些等待者4.3.7Linux中的信号量机制6、SystemV信号量的几个主要函数key_t

ftok(char*pathname，charproj);根据pathname和proj来创建一个关键字

int

semget(key_tkey，int

nsems，int

semflg);创建一个信号量。成功时返回返回信号量句柄（信号的ID），失败则返回-1key是一个关键字，可以是用ftok创建的也可以是IPC_PRIVATE表明由系统选用一个关键字nsems表明创建的信号个数semflg是创建的权限标志，和创建一个文件的标志相同4.3.7Linux中的信号量机制int

semctl(int

semid，int

semnum，int

cmd，unionsemun

arg);对信号量进行一系列的控制semid是要操作的信号标志semnum是信号的个数cmd是操作的命令int

semop(int

semid，struct

sembuf*spos，int

nspos);对信号进行操作semid是信号标志spos是一个操作数组表明要进行什么操作。struct

sembuf{shortsem_num;/*使用哪一个信号*/shortsem_op;/*进行什么操作*/shortsem_flg;/*操作的标志*/};

nspos表明数组个数第三章并发进程

4.1并发进程4.2临界区管理4.3信号量与P、V操作4.4进程间通信4.5死锁4.6管程4.4进程间通信4.4.1进程间通信概念4.4.2进程间通信方式4.4.3Linux中的进程间通信机制4.4.1进程间通信概念1、进程间通信（Inter-ProcessCommunication/IPC）：进程之间互相交换信息的工作。进程间的通信根据通信的内容可以划分为两种控制信息的传送：只传递简单的信号，不能传递交换大量信息，如信号量机制及P、V操作（低级通信原语）控制的进程同步和互斥大批量数据传送：用Send/Receive原语（高级通信原语）4.4进程间通信4.4.1进程间通信概念4.4.2进程间通信方式4.4.3Linux中的进程间通信机制4.4.2进程间通信方式1、主从式（Master-Servant）通信：主进程-从进程主进程可自由地使用从进程的资源或数据从进程的动作受主进程的控制主进程和从进程关系固定典型例子是终端控制进程和终端进程4.4.2进程间通信方式2、会话式（Dialogue）通信：使用进程-服务进程使用进程调用服务进程提供的服务使用进程在使用服务进程所提供的服务之前，必须得到服务进程的许可服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成使用进程和服务进程在进行通信时有固定连接关系4.4.2进程间通信方式3、消息队列或邮箱（MessageQueueorMailbox）：发送进程-接收进程消息用于表示所交换的数据，传递大量信息之外，还意味着两个互相通信的进程地位平等缓冲区或邮箱专门存放被传送消息只要存在空缓冲区或邮箱，无论接收进程是否已准备好接收消息，发送进程都将把所要发送的消息送入缓冲区队列或邮箱发送进程相接收进程之间无直接连接关系4.4.2进程间通信方式4、共享存储区(SharedMemory):读进程-写进程两个需要互相交换信息的进程通过对同一共享数据区的操作来达到互相通信的目的不要求数据移动4.4.2进程间通信方式5、上述方式可以分为如下两类：直接通信：信息直接传递给接收方在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播式地址在接收时，允许接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址接收方可接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址4.4.2进程间通信方式5、上述方式可以分为如下两类：间接通信：借助于收发双方进程之外的共享数据结构作为通信中转如消息队列或是信箱接收方和发送方的数目可以是任意的4.4.2进程间通信方式6、通信过程中的其他特征通信链路特征链路是点对点还是广播链路通信链路是否带缓冲区链路是单向还是双向等4.4.2进程间通信方式数据格式字节流格式：接收方不保留各次发送之间的分界报文格式：接收方保留各次发送之间的分界。报文方式还可进一步分成定长报文/不定长报文和可靠报文/不可靠报文收发操作的同步方式阻塞操作：指操作方要等待操作结束不阻塞操作：指操作提交后立即返回4.4进程间通信4.4.1进程间通信概念4.4.2进程间通信方式4.4.3Linux中的进程间通信机制4.4.3Linux中的进程间通信机制1、信号通信机制每个信号都对应一个正整数常量（即信号编号

signalnumber），代表同一用户的诸进程之间传送事先约定的信息的类型，用于通知某进程发生了某异常事件每个进程在运行时，都要通过信号机制来检查是否有信号到达。若有，便中断正在执行的程序，转向与该信号相对应的处理程序；处理结束后再返回到原来的断点继续执行信号机制是对中断机制的一种模拟，又称为软中断

4.4.3Linux中的进程间通信机制信号与中断的相似点主要包括：①相同异步通信方式②检测出有信号或中断请求时，都暂停正在执行的程序而转去执行相应的处理程序③处理完毕后返回到原来的断点④对信号或中断都可进行屏蔽4.4.3Linux中的进程间通信机制信号与中断的区别主要包括：①信号没有优先级，所有的信号都平等；而中断有优先级②信号处理程序在用户态下运行；而中断处理程序是在核心态下运行；③信号响应通常都有较大的时间延迟；而中断响应是及时的4.4.3Linux中的进程间通信机制信号机制的基本功能发送信号：由发送进程把信号送到指定进程的信号域的某一位上预置对信号的处理方式，一般有忽略、退出、执行预知程序三种方式收受信号的进程按事先的规定完成对相应事件的处理4.4.3Linux中的进程间通信机制2、共享存储区机制通信速度最高的一种通信机制共享存储区为内存中的某一个区域，映射在若干需通过该区域通信的进程的虚地址空间中一个进程的虚地址空间中可以连接多个共享存储区4.4.3Linux中的进程间通信机制进程间欲利用共享存储区进行通信时，必须先在内存中建立一共享存储区，然后将它附接到自己的虚地址空间上。此后，进程对该区的访问操作，与对其虚地址空间的其他部分的操作完全相同，通过对共享存储区中数据的读、写来进行直接通信共享存储区机制并未提供对该区进行互斥访问及进程同步的措施。因而当用户需要使用该机制时，必须自己设置同步和互斥措施才能保证实现正确的通信4.4.3Linux中的进程间通信机制共享存储区涉及的系统调用#include<sys/types.h>#include<sys/ipc.h>#include<sys/shm.h>shmget()创建、获得一个共享存储区：shmid=shmget(key,size,flag)shmat()从逻辑上将一个共享存储区附接到进程的虚拟地址空间上：virtaddr=shmat(shmid,addr,flag)shmdt()

把一个共享存储区从指定进程的虚地址空间断开：shmdt(addr)shmctl()

对其状态信息进行读取和修改：shmctl(shmid,cmd,buf)4.4.3Linux中的进程间通信机制3、消息通信机制消息是一个格式化的可变长的信息单元消息通信机制允许由一个进程给其他任意的进程发送一个消息当一个进程收到多个消息时，可将它们排成一个消息队列每一个消息队列都有一个称为关键字（key）的名字，即消息队列描述符，由用户指定，其作用与用户文件描述符一样，是为了方便用户和系统对消息队列的访问4.4.3Linux中的进程间通信机制相关数据结构消息首部：记录与消息有关的信息，如消息的类型、大小、指向消息数据区的指针、消息队列的链接指针等消息队列头表：消息队列头表每一个表项作为一个消息队列的消息头，记录消息队列的有关信息，如指向消息队列中第一个消息和指向最后一个消息的指针、队列中消息的数目、队列中消息数据的总字节数、队列所允许消息数据的最大字节总数，还有最近一次执行发送操作的进程标识符和时间、最近一次执行接收操作的进程标识符和时间等4.4.3Linux中的进程间通信机制消息通信涉及系统调用需引用头文件#include<sys/types.h>#include<sys/ipc.h>#include<sys/msg.h>msgget()：创建一个消息，获得一个消息的描述符调用格式msgqid=msgget(key,flag);key：用户指定的消息队列的名字flag：用户设置的标志和访问方式msgqid

：该系统调用返回的描述符，失败则返回-1主要工作：搜索消息队列头表查看是否有指定名字的消息队列，有则检查许可权并返回；无则分配新消息队列头并初始化，然后向用户返回消息队列描述符4.4.3Linux中的进程间通信机制msgsnd()：向指定的消息队列发送一个消息，并将该消息链接到该消息队列的尾部

调用格式msgsnd(msgqid,msgp,size,flag);msgqid：返回消息队列的描述符msgp：指向用户消息缓冲区的一个结构体指针，包括消息类型（长整型）和消息正文

（字符数组）size：msgp指向结构体中字符数组的长度，即消息长度flag：规定当核心用尽内部缓冲空间时应执行的动作：等待或立即返回4.4.3Linux中的进程间通信机制主要工作：对消息队列的描述符和许可权及消息长度等进行检查，不合法则返回；否则为消息分配消息数据区，将用户消息缓冲区中的消息正文，拷贝到消息数据区；分配消息首部，并将它链入消息队列的末尾，在消息首部中须填写消息类型、消息大小和指向消息数据区的指针等数据；修改消息队列头中的数据，如队列中的消息数、字节总数等；最后，唤醒等待消息的进程

4.4.3Linux中的进程间通信机制msgrcv()：从指定消息队列中接收指定类型的消息

调用格式msgrcv(msgqid,msgp,size,type,flag);msgqid,msgp,size与msgsnd中的对应参数相似type：规定要读的消息类型flag：规定倘若该队列无消息，核心应作的操作主要工作：对消息队列的描述符和许可权等进行检查，不合法则返回；否则①type=0，接收该队列的第一个消息；②type>0，接收类型type的第一个消息；③type<0，接收小于等于type绝对值的最低类型的第一个消息。当所返回消息大小等于或小于用户的请求时，将消息正文拷贝到用户区，并从消息队列中删除此消息，然后唤醒睡眠的发送进程。但如果消息长度比用户要求的大时，则作出错返回

4.4.3Linux中的进程间通信机制msgctl()：读取消息队列的状态信息并进行修改，如查询消息队列描述符、修改它的许可权及删除该队列等调用格式msgctl(msgqid,cmd,buf);buf：用户缓冲区地址，供用户存放控制参数和查询结果cmd：规定的命令，分3类函数调用成功时返回0，不成功则返回-14.4.3Linux中的进程间通信机制共享存储区和消息通信机制的比较①建立：消息队列的建立消耗资源更少，它只是一个软件上设定的问题；而共享区需要对硬件操作，实现内存的映像，控制起来更复杂。如果每次都重新进行队列或共享的建立，共享区的设立没有什么优势②使用：共享区的数据传输受到系统硬件的支持，不耗费多余的资源。而消息传递由软件进行控制和实现，需要消耗一定的cpu的资源。从这个意义上讲，共享区更适合频繁和大量的数据传输③同步：消息的传递自身就带有同步控制。而共享队列如果不借助其他机制进行同步，接收数据的一方必须进行不断地查询，浪费CPU资源。可见消息方式的使用更加灵活4.4.3Linux中的进程间通信机制4、管道通信机制管道：能够连接一个写进程和一个读进程的、并允许它们以生产者—消费者方式进行通信的一个共享文件，又称为pipe文件由写进程从管道的写入端（句柄1）将数据写入管道，而读进程则从管道的读出端（句柄0）读出数据

4.4.3Linux中的进程间通信机制管道类型有名管道：一个可以在文件系统中长期存在的、具有路径名的文件，用系统调用mknod()建立。其他进程可以知道它的存在并利用路径名来访问该文件。对有名管道的访问与访问其他文件一样，需先用open()打开无名管道：一个利用pipe()建立起来临时的无名文件（无路径名）。只用该系统调用所返回的文件描述符来标识该文件，故只有调用pipe()的进程及其子孙进程才能识别此文件描述符并利用该文件（管道）进行通信4.4.3Linux中的进程间通信机制管道通信的互斥问题各进程应互斥地访问pipe文件索引结点中的直接地址项，每次进程在访问pipe文件前都需检查该索引文件是否已被上锁。若是，进程便睡眠等待，否则，将其上锁，进行读/写。操作结束后解锁，并唤醒因该索引结点上锁而睡眠的进程管道通信涉及系统调用#include<unistd.h>#inlcude<signal.h>#include<stdio.h>4.4.3Linux中的进程间通信机制pipe()

：调用格式pipe(filedes);建立一无名管道，为管道文件分配磁盘和内存索引结点、为读进程分配文件表项、为写进程分配文件表项、分配用户文件描述符。read()

：调用格式read(fd,buf,nbyte);从fd指示的文件中读出nbyte个字节的数据，并将它们送至由指针buf所指示的缓冲区中。如该文件被加锁，等待，直到锁打开为止write()：调用格式write(fd,buf,nbyte);把nbyte

个字节的数据，从buf所指向的缓冲区写到由fd所指向的文件中。如文件加锁，暂停写入，直至开锁第三章并发进程

4.1并发进程4.2临界区管理4.3信号量与P、V操作4.4进程间通信4.5死锁4.6管程4.5死锁4.5.1死锁的基本概念4.5.2死锁的预防——解决死锁的静态方法4.5.3死锁的避免——解决死锁的动态方法4.5.4死锁的检测及解除

4.5.1死锁的基本概念1、死锁的定义操作系统中多道进程的并发执行可以改善系统的资源利用率，但也可能出现若干进程都相互等待对方释放资源才能继续运行，否则就阻塞的情况死锁：系统中两个或者多个进程无限期地等待永远不会发生的条件，系统处于停滞状态，这种现象称为进程死锁，这一组进程就称为死锁进程4.5.1死锁的基本概念2、死锁产生的例子申请不同类资源P1： P2：… …申请打印机 申请扫描仪申请扫描仪 申请打印机使用 使用释放打印机 释放打印机释放扫描仪 释放扫描仪… …申请同类资源内存资源有m个分配单位，n个进程共享，每个进程依次只能申请一个单位，满足总量才能使用，使用完后一次性释放4.5.1死锁的基本概念3、死锁产生的原因因为系统资源不足：如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁进程运行推进的顺序不合适：如上面打印机和扫描仪申请一例资源分配不当：如上面内存分配一例4.5.1死锁的基本概念4、产生死锁的4个必要条件：①互斥使用（资源独占）：一个资源每次只能给一个进程使用②不可强占（不可剥夺）：资源申请者不能强行地从资源占有者手中夺取资源，资源只能由占有者自愿释放③请求和保持（部分分配，占有申请）：一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）④循环等待：存在一个进程等待队列{P1,P2,…,Pn}，其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路

4.5死锁4.5.1死锁的基本概念4.5.2死锁的预防——解决死锁的静态方法4.5.3死锁的避免——解决死锁的动态方法4.5.4死锁的检测及解除

4.5.2死锁的预防

——解决死锁的静态方法1、基本策略在系统设计时确定资源分配算法，保证不发生死锁通过破坏产生死锁的4个必要条件之一来实现由于系统存在很多独占资源，破坏“互斥使用”这一必要条件不太现实，重点探讨破坏后3种必要条件的方法4.5.2死锁的预防

——解决死锁的静态方法2、破坏“不可剥夺”条件在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请3、破坏“请求和保持”条件要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配4.5.2死锁的预防

——解决死锁的静态方法4、破坏“循环等待”条件采用资源有序分配法，把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配例如，有资源1，2，3，…，m，现有n个进程来竞争这些资源，则须按下图所示递增顺序申请资源4.5死锁4.5.1死锁的基本概念4.5.2死锁的预防——解决死锁的静态方法4.5.3死锁的避免——解决死锁的动态方法4.5.4死锁的检测及解除

4.5.3死锁的避免

——解决死锁的动态方法1、基本策略在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配关键在于区分安全状态与不安全状态，安全状态一定没有死锁发生，因而对进程的申请进行试分配，分配后系统状态为安全状态则满足，否则不满足4.5.3死锁的避免

——解决死锁的动态方法2、一个典型的死锁避免算法：银行家算法①银行家拥有一笔周转资金②客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款③银行家应谨慎地贷款，防止出现坏账④银行家采用的具体方法是看他是否有足够的剩余资金满足某一个需求的客户，如此反复下去⑤如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准4.5.3死锁的避免

——解决死锁的动态方法3、银行家算法思想在单种资源情况下的应用对进程的每个针对该资源的申请进行检查，若会导致不安全状态，则不满足该申请；否则便满足安全状态的具体定义：安全序列：如果对一个进程序列P1，…，Pn中的每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和，则该序列为安全序列安全状态：如果系统中的所有进程能够排成一个安全序列，则系统处于安全状态4.5.3死锁的避免

——解决死锁的动态方法例1：一个共有150个存储单元的系统，分配给3个进程，P1最大需求70，己占有25；P2最大需求60,己占有40；P3最大需求60，己占有45资源申请：P4进程到达，最大需求60，最初请求25个试分配：由于系统目前还有150-25-40-45=40个单元，P4进程到达，若满足其申请，则系统还余15个单元分析此时系统状态（寻找安全序列）：可以将15个单元分给P3，它执行完后会释放60个单元，可供P1（还要45个单元），P2（还要20个单元），P4（还要35个单元）任何一个执行。存在P3P1P2P4等6种安全序列决定是否满足申请：预分配后系统仍处于安全状态，因而可以满足P4的资源申请4.5.3死锁的避免

——解决死锁的动态方法例2：一个共有150个存储单元的系统，分配给3个进程，P1最大需求70，己占有25；P2最大需求60,己占有40；P3最大需求60，己占有45资源申请：P4进程到达，最大需求60，最初请求35试分配：由于系统目前还有150-25-40-45=40个单元，P4进程到达，若满足其申请，则系统还余5个单元分析此时系统状态（寻找安全序列）：不能满足任何一个进程需求，找不到安全序列决定是否满足申请：预分配后系统进入不安全状态，因而不能满足P4的资源申请4.5.3死锁的避免

——解决死锁的动态方法4、银行家算法思想在多种资源情况下的应用系统有n个进程和m种不同类型的资源，相关定义如下各类资源总数向量——Resource=(R1,R2,…,Rm)，其中Ri表示第i类资源总数各类资源未分配数向量——Available=(V1,V2,…,Vm)最大需求矩阵——Cij表示进程Pi对Rj类资源的最大需求量分配矩阵——Aij表示进程Pi已分到Rj类资源的个数4.5.3死锁的避免

——解决死锁的动态方法下列关系式确保成立Ri=Vi+∑Aki，对i=1,..,m,k=1,..,n，表示所有资源要么已被分配、要么尚可分配Cki≤Ri，对i=1,...,m,k=1,..,n，表示进程申请资源数不能超过系统拥有的资源总数。

Aki≤Cki，对i=1,...,m,k=1,..,n，表示进程申请任何类资源数不能超过声明的最大资源需求数4.5.3死锁的避免

——解决死锁的动态方法系统安全性定义在时刻T0系统是安全的，仅当存在一个进程序列P1,...,Pn，对进程Pk(k=1,...,n)满足公式：则该序列称安全序列公式左边表示进程Pk尚缺少的各类资源Vi是T0时刻系统尚可用于分配且为Pk所想要的那类资源数；∑Aji表示排在进程Pk之前的所有进程占用的Pk所需要的资源的总数

4.5.3死锁的避免

——解决死锁的动态方法算法基本思想①系统中所有进程进入进程集合；在安全状态下系统收到进程的资源请求后进行试分配（修改Available）②将系统剩余资源和进程集合中其他进程还需要的资源数作比较，找出能满足最大需求量的进程Pi（即(Ci1,…Cim)-(Ai1,…Aim)≤Available），找不到则转④③把进程Pi从集合中去掉，将其占用资源归还给系统（即Available+=(Ai1,…Aim)）；集合为空转④，否则转②④检查进程集合，若为空表明本次申请执行后系统仍处于安全状态，可实施分配；否则说明该申请将导致系统处于不安全状态，则暂不实施分配，让申请进程等待

4.5.3死锁的避免

——解决死锁的动态方法例：系统状态如下图所示，给出了剩余资源Available、最大需求矩阵C、分配矩阵A的情况，试处理进程P1发出的资源请求(1,0,0,0)4.5.3死锁的避免

——解决死锁的动态方法例：试分配后，Available=(0,6,2,2)0012075023560652065620000012075023560652065620004.5.3死锁的避免

——解决死锁的动态方法例：P0符合条件，归还资源后，Available=(0,6,2,2)+(0,0,3,2)=(0,6,5,4)0012075023