1、西安理工大学2006年第五章第五章 并发进程及死锁问题并发进程及死锁问题 进程间的联系进程间的联系 进程的同步机制进程的同步机制信号量及信号量及P.VP.V操作操作（解决进程同步互斥问题）（解决进程同步互斥问题）西安理工大学2006年5.1 5.1 进程间的制约关系进程间的制约关系相交进程与无关进程相交进程与无关进程相交进程：指多个并发进程在逻辑上有某相交进程：指多个并发进程在逻辑上有某种联系种联系无关进程（不相交进程）：在逻辑上无任无关进程（不相交进程）：在逻辑上无任何联系的进程何联系的进程西安理工大学2006年直接作用和间接作用直接作用和间接作用直接作用：直接作用：进程间的相互联系是有意识
2、的安排的，进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间直接作用只发生在相交进程间间接作用：间接作用：进程间要通过某种中介发生联系，是无进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，意识安排的，可发生在相交进程之间，也可发生在无关进程之间也可发生在无关进程之间西安理工大学2006年相互感知程度相互感知程度 交互关系交互关系 一个进程对其他进一个进程对其他进程程的影响的影响 相互不感知相互不感知(完全不完全不了解其它进程的存了解其它进程的存在在)竞争竞争(competition)一个进程的操作对一个进程的操作对其他进程的结果无其他进程的结果无影响影响 间接感知
3、间接感知(双方都与双方都与第三方交互，如共第三方交互，如共享资源享资源)通过共享进行协作通过共享进行协作 一个进程的结果依一个进程的结果依赖于从其他进程获赖于从其他进程获得的信息得的信息 直接感知直接感知(双方直接双方直接交互，如通信交互，如通信)通过通信进行协作通过通信进行协作 一个进程的结果依一个进程的结果依赖于从其他进程获赖于从其他进程获得的信息得的信息 西安理工大学2006年进程的同步（直接作用）进程的同步（直接作用）进程的同步：进程的同步：synchronism指系统中多个进程中发生的事件存在某指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成种时序关系，需要相互合
4、作，共同完成一项任务。一项任务。具体说，一个进程运行到某具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态态，获得消息后被唤醒进入就绪态西安理工大学2006年例例:司机司机 P1 售票员售票员 P2 while(true)while(true)启动车辆；启动车辆；关门；关门；正常运行；正常运行；售票；售票；到站停车；到站停车；开门；开门；西安理工大学2006年进程的互斥（间接作用）进程的互斥（间接作用）mutual exclusion 由于各进程要求共
5、享资源，而有些资源需由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥资源，进程的这种关系为进程的互斥临界资源：临界资源：critical resource 系统中某些资源一次只允许一个进程使系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源用，称这样的资源为临界资源或互斥资源或共享变量或共享变量西安理工大学2006年临界区（互斥区）：临界区（互斥区）：critical section一个程序片段的集合，这些程序片段分一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据
6、散在不同的进程中，对某个共享的数据结构（共享资源）进行操作结构（共享资源）进行操作 在进程中涉及到临界资源的程序段叫在进程中涉及到临界资源的程序段叫临临界区界区 多个进程的临界区称为多个进程的临界区称为相关临界区相关临界区西安理工大学2006年a:=a-1 print(a)a:=a+1 print(a)P1互斥互斥P2互斥互斥If a 0then a:=a+1else a:=a-1P3互斥互斥 进程的互斥进程的互斥（间接作用）（间接作用）西安理工大学2006年程 序 段1程 序 段2程 序 段n共 享 变 量西安理工大学2006年使用互斥区的原则：使用互斥区的原则：有空让进有空让进：当无进程在
7、互斥区时，任何有权使用当无进程在互斥区时，任何有权使用互斥区的进程可进入互斥区的进程可进入无空等待无空等待：不允许两个以上的进程同时进入互斥不允许两个以上的进程同时进入互斥区区多中择一多中择一：当没有进程在临界区，而同时有多个当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待界区，其他进程必须等待有限等待有限等待：任何进入互斥区的要求应在有限的时任何进入互斥区的要求应在有限的时间内得到满足间内得到满足让权等待让权等待：处于等待状态的进程应放弃占用处于等待状态的进程应放弃占用CPUCPU，以使其他进程有机会得到以
8、使其他进程有机会得到CPUCPU的使用权的使用权西安理工大学2006年使用互斥区的原则：使用互斥区的原则：前提：任何进程无权停止其它进程的运行前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程之间相对运行速度无硬性规定进程互斥的解决有两种做法进程互斥的解决有两种做法:由竞争各方平等协商由竞争各方平等协商 引入进程管理者，由管理者来协调竞争各方对互斥引入进程管理者，由管理者来协调竞争各方对互斥资源的使用资源的使用具体方法：具体方法：硬件（当一个进程进入临界区硬件（当一个进程进入临界区,就屏蔽所有中断，就屏蔽所有中断，但成本高）但成本高）软件（用编程解决，但常常忙等待软件（用
9、编程解决，但常常忙等待 ）西安理工大学2006年进程互斥的软件方法进程互斥的软件方法 通过平等协商方式实现进程互斥的最初通过平等协商方式实现进程互斥的最初方法是软件方法方法是软件方法 其基本思路是在进入区检查和设置一些其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区入区通过循环检查进行等待；在退出区修改标志修改标志 其中的主要问题是设置什么标志和如何其中的主要问题是设置什么标志和如何检查标志检查标志西安理工大学2006年软件解法软件解法 (1)(1)free:free:表示临界区标志表示临界区标志 true
10、:true:有进程在临界区有进程在临界区 false:false:无进程在临界区无进程在临界区(初值初值).while(free);while(free);free=true;free=true;临界区临界区 free=false;free=false;西安理工大学2006年软件解法软件解法 (2)(2)turn:true turn:true P P进入临界区进入临界区 false false Q Q进入临界区进入临界区 .P:while(not turn);P:while(not turn);临界区临界区 turn=false;turn=false;Q:while(turn);Q:while
11、(turn);临界区临界区 turn=true;turn=true;西安理工大学2006年软件解法的缺点：软件解法的缺点：1.1.忙等待忙等待 2.2.实现过于复杂，需要高的编程技巧实现过于复杂，需要高的编程技巧西安理工大学2006年硬件解法硬件解法 (1)(1)“测试并设置测试并设置”指令指令 boolean TS(boolean boolean TS(boolean *lock)lock)boolean boolean old;old;old=old=*lock;lock;*lock=true;lock=true;while TS(&lock);while TS(&lock);临界区临界区
12、 lock=false;lock=false;西安理工大学2006年硬件解法硬件解法 (2)(2)“交换交换”指令指令void SWAP(int*a,int*b)int temp;temp=*a;*a=*b;*b=temp;key=true;key=true;do do SWAP(&lock,key);SWAP(&lock,key);while(key);while(key);临界区临界区 lock:=false;lock:=false;西安理工大学2006年硬件解法硬件解法 (3)(3)“开关中断开关中断”指令指令进入临界区前执行：进入临界区前执行：执行执行“关中断关中断”指令指令离开临界区
13、后执行：离开临界区后执行：执行执行“开中断开中断”指令指令西安理工大学2006年5.2 5.2 进程的同步机制进程的同步机制信号量及信号量及P.VP.V操作（解决进程同步与互斥）操作（解决进程同步与互斥）5.2.15.2.1概念概念同步机制：同步机制：信号量及信号量及P P、V V操作；管程；条件临界操作；管程；条件临界域；路径表达式等（用于集中式系统中）域；路径表达式等（用于集中式系统中）会合；通信顺序进程；分布进程；远会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）程过程调用等（适用于分布式系统中）西安理工大学2006年信号量分类信号量分类公用信号量公用信号量私用信号量私
14、用信号量二元信号量二元信号量一般信号量一般信号量西安理工大学2006年同步机制应满足的基本要求：同步机制应满足的基本要求：*描述能力描述能力*可以实现可以实现*效率高效率高*使用方便使用方便西安理工大学2006年信号量：信号量：semaphoresemaphore 是一个数据结构是一个数据结构 定义如下：定义如下：strucstruc semaphore semaphore intint value;value;pointer_PCB queue;pointer_PCB queue;信号量说明：信号量说明：semaphore s;semaphore s;西安理工大学2006年P P、V V操作
15、操作P(s)P(s)s.value=s.value-;s.value=s.value-;if(s.value 0)if(s.value 0)该进程状态置为等待状态该进程状态置为等待状态 将该进程的将该进程的PCBPCB插入相应的等待队列末尾插入相应的等待队列末尾s.queue;s.queue;西安理工大学2006年P P、V V操作操作V(s)V(s)s.value=s.value+;s.value=s.value+;if(s.value =0)if(s.value 0表示有表示有S个资源可用个资源可用S=0表示无资源可用表示无资源可用S=1&S2=1&Sn=1)/满足资源要求时的处理；满足资
16、源要求时的处理；for(i=1;i=n;+i)-Si;/注：与注：与P的处理不同，这里是在确信可满足的处理不同，这里是在确信可满足 /资源要求时，才进行减资源要求时，才进行减1操作；操作；break;else /某些资源不够时的处理；某些资源不够时的处理；调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.queue;阻塞调用进程阻塞调用进程;西安理工大学2006年Ssignal(S1,S2,Sn)for(i=1;i=ti；即当资源数量低于；即当资源数量低于ti时，便不予时，便不予分配）分配）占用值为占用值为di（表示资源的申请量，即（表示资源的申请量，即Si=
17、Si-di）对应的对应的P、V原语格式为：原语格式为：Swait(S1,t1,d1;.;Sn,tn,dn);Ssignal(S1,d1;.;Sn,dn);西安理工大学2006年一般一般“信号量集信号量集”可以用于各种情况可以用于各种情况的资源分配和释放，几种特殊情况：的资源分配和释放，几种特殊情况：Swait(S,d,d)表示每次申请表示每次申请d个资源，当个资源，当少于少于d个时，便不分配个时，便不分配 Swait(S,1,1)表示互斥信号量表示互斥信号量 Swait(S,1,0)可作为一个可控开关（当可作为一个可控开关（当S 1时，允许多个进程进入临界区；当时，允许多个进程进入临界区；当S
18、=0时，禁止任何进程进入临界区）时，禁止任何进程进入临界区）西安理工大学2006年【思考题【思考题】1.用用P.V操作解决下图之同步问题操作解决下图之同步问题:getcopyputfstg西安理工大学2006年用用P.V操作解决司机与售票员的问题操作解决司机与售票员的问题司机进程：司机进程：while while(true)(true)启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车 售票员进程：售票员进程：while while(true)(true)关门关门售票售票开门开门 西安理工大学2006年5.2.2 IPC5.2.2 IPC经典问题经典问题1.1.读者写者问题读者写者问题 有两组并
19、发进程有两组并发进程:读者和写者读者和写者,共享一组数据区共享一组数据区 要求：要求：允许多个读者同时执行读操作允许多个读者同时执行读操作 不允许读者、写者同时操作不允许读者、写者同时操作 不允许多个写者同时操作不允许多个写者同时操作西安理工大学2006年第一类：读者优先第一类：读者优先如果读者来：如果读者来：1 1）无读者、写者，新读者可以读）无读者、写者，新读者可以读2 2）有写者等，但有其它读者正在读，则新）有写者等，但有其它读者正在读，则新读者也可以读读者也可以读3 3）有写者写，新读者等）有写者写，新读者等如果写者来：如果写者来：1 1）无读者，新写者可以写）无读者，新写者可以写2
20、2）有读者，新写者等待）有读者，新写者等待3 3）有其它写者，新写者等待）有其它写者，新写者等待西安理工大学2006年第一类读者写者问题的解法第一类读者写者问题的解法读者：读者：while(true)P(mutex);readcount+;if(readcount=1)P(w);V(mutex);读读 P(mutex);readcount-;if(readcount=0)V(w);V(mutex);写者：写者：while(true)P(w);写写 V(w);西安理工大学2006年第一类读者写者问题的解法第一类读者写者问题的解法（一般信号量集）（一般信号量集）读者：读者：swait(wmutex
21、,1,1;rcount,R,0);写；写；ssignal(wmutex,1);写者：写者：swait(rcount,1,1;wmutex,1,0);写；写；ssignal(rcount,1);西安理工大学2006年2.2.哲学家就餐问题哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后每个哲学家的行为是思考，感到饥饿，然后吃通心粉吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷为了吃通心粉，每个哲学家必须拿到两只筷
22、子，并且每个人只能直接从自己的左边或右子，并且每个人只能直接从自己的左边或右边去取筷子边去取筷子西安理工大学2006年#define N 5 void philosopher(int i)while(true)思考；思考；取取forki;取取fork(i+1)%5；进食；进食；放放forki;放放fork(i+1)%5；西安理工大学2006年为防止死锁发生可采取的措施：为防止死锁发生可采取的措施：最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（才允许他拿筷子（）给所有哲学家编号，
23、奇数号的哲学家必须给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反首先拿左边的筷子，偶数号的哲学家则反之之 为了避免死锁，把哲学家分为三种状态，思为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，考，饥饿，进食，并且一次拿到两只筷子，否则不拿否则不拿西安理工大学2006年哲学家就餐问题解法（哲学家就餐问题解法（1 1）#define N 5 void philosopher(int i)while(true)思考；思考；取取forki;取取fork(i+1)%5；进食；进食；放放forki;放放fork(i+1)%5；西安理工大学2006年哲学
24、家就餐问题解法（哲学家就餐问题解法（2 2）#define N 5#define N 5#define THINKING 0#define THINKING 0#define HUNGRY 1#define HUNGRY 1#define EATING 2#define EATING 2#typedef int#typedef int semaphore;semaphore;intint stateN;stateN;semaphore mutexsemaphore mutex=1;=1;semaphore sN;semaphore sN;西安理工大学2006年void test(int i)i
25、f(state i =HUNGRY)&(state (i-1)%5!=EATING)&(state (i+1)%5!=EATING)state i =EATING;V(&s i);西安理工大学2006年void philosopher(int i)while(true)思考思考;P(&mutex);statei=HUNGRY;test(i);V(&mutex);P(&si);拿左筷子；拿左筷子；拿右筷子；拿右筷子；进食；进食；放左筷子；放左筷子；放右筷子放右筷子；P(&mutex)state i =THINKING；test(i-1%5);test(i+1%5);V(&mutex);state
26、 i =THINKINGs i =0西安理工大学2006年【作业【作业】1.1.推广例子中的消息缓冲问题。推广例子中的消息缓冲问题。消息缓冲区为消息缓冲区为k k个，有个，有1 1个发送进程，个发送进程，n n个接收进程，每个接收进程对发送个接收进程，每个接收进程对发送来的消息都必须取一次来的消息都必须取一次 若有若有m m个发送进程呢？个发送进程呢？西安理工大学2006年2.2.第二类读者写者问题：第二类读者写者问题：写者优先写者优先条件：条件：1 1）多个读者可以同时进行读）多个读者可以同时进行读2 2）写者必须互斥（只允许一个写者写，也）写者必须互斥（只允许一个写者写，也不能读者写者同时
27、进行）不能读者写者同时进行）3 3）写者优先于读者（一旦有写者，则后续）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）读者必须等待，唤醒时优先考虑写者）西安理工大学2006年3.3.有一个系统，定义有一个系统，定义P P、V V操作如下：操作如下：P(s):P(s):s:=s-1;s:=s-1;if s0 then if s0 then 将本进程插入相应队列末尾等待；将本进程插入相应队列末尾等待；V(s)V(s)：s:=s+1;s:=s+1;if s=0 then if s=0 then 从相应等待队列队尾唤醒一个进从相应等待队列队尾唤醒一个进程，将其插入就绪队列；程，将
28、其插入就绪队列；西安理工大学2006年 问题：问题：1 1）这样定义）这样定义P P、V V操作是否有问题？操作是否有问题？2 2）用这样的）用这样的P P、V V操作实现操作实现N N个进程竞争使个进程竞争使用某一共享变量的互斥机制。用某一共享变量的互斥机制。3 3）对于）对于2 2）的解法，有无效率更高的方法。）的解法，有无效率更高的方法。如有，试问降低了多少复杂性？如有，试问降低了多少复杂性？西安理工大学2006年4.4.理发师睡觉问题理发师睡觉问题 理发店里有一位理发师，一把理发椅和理发店里有一位理发师，一把理发椅和N N把供等候理发的顾客坐的椅子把供等候理发的顾客坐的椅子 如果没有顾
29、客如果没有顾客,则理发师便在理发椅上睡则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先唤醒觉。当一个顾客到来时，他必须先唤醒理发师理发师如果顾客到来时理发师正在理发，则如如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开果有空椅子，可坐下来等；否则离开西安理工大学2006年5.3 5.3 进程通信进程通信概述概述消息缓冲通信方式消息缓冲通信方式西安理工大学2006年5.3.1 5.3.1 概述概述P.VP.V操作实现的是进程之间的低级通讯，操作实现的是进程之间的低级通讯，所以所以P.VP.V为低级通讯原语。它只能传递简为低级通讯原语。它只能传递简单的信号，不能传递交换大量信
30、息单的信号，不能传递交换大量信息如果要在进程间传递大量信息则要用如果要在进程间传递大量信息则要用Send/ReceiveSend/Receive原语（高级通讯原语）原语（高级通讯原语）西安理工大学2006年进程通信的方式进程通信的方式共享内存共享内存：相互通信的进程间设有公共内存，一组进相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进共内存中读，通过这种方式实现两组进程间的信息交换程间的信息交换这种通信模式需要解决两个问题？这种通信模式需要解决两个问题？西安理工大学2006年消息传递消息传递：系统为进程提
31、供了两个高级通讯原系统为进程提供了两个高级通讯原语语sendsend和和receivereceive send send：当要进行消息传递时执行当要进行消息传递时执行sendsend receive receive：当接收者要接收消息时执行当接收者要接收消息时执行receivereceive西安理工大学2006年共享文件模式共享文件模式：管道通信管道通信西安理工大学2006年消息传递模式消息传递模式 消息缓冲消息缓冲 在内存中开设缓冲区，发送进程将在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传消息送入缓冲区，接收进程接收传递来的缓冲区递来的缓冲区 信箱通信信箱通信西安理工大学20
32、06年直接方式直接方式：发送进程发消息时要指定接收进程的名字，发送进程发消息时要指定接收进程的名字，反过来，接收时要指明发送进程的名字反过来，接收时要指明发送进程的名字 Send(receiver,message)Send(receiver,message)Receiver(sender,message)Receiver(sender,message)*对称形式：一对一对称形式：一对一*非对称形式：多对一非对称形式：多对一 （顾客（顾客/服务员）服务员）有缓冲（有界，无界），无缓冲有缓冲（有界，无界），无缓冲西安理工大学2006年间接方式间接方式：发送进程发消息时不指定接收进程的名发送进程发消
33、息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信进程间通过信箱实现通信 发送原语：发送原语：send(MB,Message)send(MB,Message)接收原语接收原语：receive(MB,Message)receive(MB,Message)西安理工大学2006年5.3.2 5.3.2 消息缓冲消息缓冲（有界缓冲区原理）：（有界缓冲区原理）：在操作系统空间设置一组缓冲区，当发送在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行进程需要发送消息时，执行sendsend系统调用，系统调用，产生自愿性中断，进入操作系统
34、，操作系产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程发送的消息从发送进程copycopy到缓冲区中，到缓冲区中，然后将该载有消息的缓冲区连接到接收进然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行发送进程返回到用户态继续执行西安理工大学2006年5.3.2 5.3.2 消息缓冲（续消息缓冲（续1 1）（有界缓冲区原理）：（有界缓冲区原理）：在以后某个时刻，当接收进程执行到在以后某个时刻，当接收进程执行到receivere
35、ceive接收原语时，也产生自愿性中断接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容缓冲区从消息链中取出，并把消息内容copycopy到接收进程空间，之后收回缓冲区，到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回如此就完成了消息的接收，接收进程返回到用户态继续进行到用户态继续进行西安理工大学2006年PCBPCB.Send(R,M)Send(R,M).SIZE:SIZE:消息长度消息长度TEXT:TEXT:消息正文消息正文.消息链指针消息链指针.Receive(pidReceive(p
36、id,N),N).SIZE:SIZE:消息长度消息长度TEXT:TEXT:消息正文消息正文.M:M:N:N:接受进程接受进程 R R发送进程发送进程 S S消息消息消息消息消息消息.西安理工大学2006年消息缓冲区结构：消息缓冲区结构：消息长度消息长度 消息正文消息正文 发送者发送者 消息队列指针消息队列指针西安理工大学2006年用用P.VP.V操作来实现操作来实现SendSend原语原语:SendSend（R R，M M）P(m-mutexP(m-mutex););Begin Begin 把缓冲区挂到接收进程把缓冲区挂到接收进程 根据根据R R找接收进程，找接收进程，的消息链链尾的消息链链尾
37、;如果没找到出错返回如果没找到出错返回;V(m-mutex;V(m-mutex););申请空缓冲区申请空缓冲区P P（s-bs-b）；）；V(s-m);V(s-m);P(b-mutex P(b-mutex);END);END 摘空缓冲区摘空缓冲区;V(b-mutex V(b-mutex););把消息从把消息从M M处处copycopy到空缓冲区到空缓冲区;其中其中s-bs-b初值初值:n;s-m:n;s-m初值初值:0:0西安理工大学2006年5.3.3 5.3.3 信箱通信信箱通信信箱组成信箱组成信箱说明信箱说明 与与 信箱体信箱体可存放信件数，已存放信件数，指针可存放信件数，已存放信件数，
38、指针信箱使用规则信箱使用规则1.若发送信件时信箱已满，则发送进程被置为若发送信件时信箱已满，则发送进程被置为“等信箱等信箱”状态，直到信箱有空时才被释放状态，直到信箱有空时才被释放2.若取信件时信箱中无信，则接收进程被置为若取信件时信箱中无信，则接收进程被置为“等信件等信件”状态，直到有信件时才被释放状态，直到有信件时才被释放西安理工大学2006年5.3.3 5.3.3 信箱通信（续信箱通信（续1 1）Send实现实现send（N，M）：把信件）：把信件M送到指定的信箱送到指定的信箱N中中步骤：步骤：查找指定信箱查找指定信箱N；若信箱未满，则把信件若信箱未满，则把信件M送入信箱且释放送入信箱且
39、释放“等信件等信件”者；者；若信箱已满置发送信件进程为若信箱已满置发送信件进程为“等信箱等信箱”状态；状态；西安理工大学2006年5.3.3 5.3.3 信箱通信（续信箱通信（续2 2）Receive实现实现receive（N，X）：从指定信箱）：从指定信箱N中取出一封信，存中取出一封信，存放到指定的地址放到指定的地址X中中步骤：步骤：查找指定信箱查找指定信箱N；若信箱中有信，则取出一封信存于若信箱中有信，则取出一封信存于X中且释放中且释放“等等信箱信箱”者；者；若信箱中无信件则置接收信件进程若信箱中无信件则置接收信件进程“等信件等信件”状态；状态；西安理工大学2006年5.3.3 5.3.3
40、 信箱通信（续信箱通信（续3 3）应用实例应用实例磁盘管理进程：从信箱中收取信件，处理，启动磁盘管理进程：从信箱中收取信件，处理，启动磁盘工作磁盘工作 其他进程：要求访问磁盘，向磁盘管理进程发其他进程：要求访问磁盘，向磁盘管理进程发一封信一封信作业：作业：用进程通信的办法解决生产者消费者问题用进程通信的办法解决生产者消费者问题 西安理工大学2006年5.3.5.3.4 4 管道通信方式管道通信方式 Pipe 也称共享文件方式，基于文件系统，也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质通信的进程，文件作为缓冲
41、传输介质发送进程发送进程接收进程接收进程字符流方式写入读出字符流方式写入读出先进先出顺序先进先出顺序西安理工大学2006年5.4 5.4 线程的基本概念线程的基本概念 线程的引入线程的引入 线程与进程的对比线程与进程的对比 线程的实现线程的实现 实例：实例：SolarisSolaris西安理工大学2006年5.4.1 5.4.1 线程的引入线程的引入进程的两个基本属性：进程的两个基本属性：资源的拥有者：资源的拥有者：给每个进程分配一虚拟地址空间，保存进给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，程映像，控制一些资源（文件，I/OI/O设设备），有状态、优先级、调度备），有状
42、态、优先级、调度 调度单位：调度单位：进程是一个执行轨迹进程是一个执行轨迹 以上两个属性构成进程并发执行的基础以上两个属性构成进程并发执行的基础西安理工大学2006年5.4.1 5.4.1 线程的引入（续线程的引入（续1 1）系统必须完成的操作：系统必须完成的操作：创建进程创建进程 撤消进程撤消进程 进程切换进程切换缺点：缺点：时间空间开销大，限制并发度的提高时间空间开销大，限制并发度的提高西安理工大学2006年5.4.1 5.4.1 线程的引入（续线程的引入（续2 2）在操作系统中，进程的引入提高了计算在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进机资源的利用效率。但在
43、进一步提高进程的并发性时，人们发现进程切换开销程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的占的比重越来越大，同时进程间通信的效率也受到限制效率也受到限制 线程的引入正是为了简化进程间的通信，线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度以小的开销来提高进程内的并发程度西安理工大学2006年5.4.1 5.4.1 线程的引入（续线程的引入（续3 3）线程：线程：有时称轻量级进程有时称轻量级进程 进程中的一个运行实体进程中的一个运行实体 是一个是一个CPUCPU调度单位调度单位 资源的拥有者还是进程或称任务资源的拥有者还是进程或称任务将原来进程的两个属
44、性分开处理将原来进程的两个属性分开处理西安理工大学2006年5.4.1 5.4.1 线程的引入（续线程的引入（续4 4）线程：线程：有执行状态（状态转换）有执行状态（状态转换）不运行时保存上下文不运行时保存上下文 有一个执行栈有一个执行栈 有一些局部变量的静态存储有一些局部变量的静态存储 可存取所在进程的内存和其他资源可存取所在进程的内存和其他资源 可以创建、撤消另一个线可以创建、撤消另一个线程程西安理工大学2006年线程和进程：线程和进程：单进程、单线程单进程、单线程单进程、多线程单进程、多线程多进程、一个进程一个线程多进程、一个进程一个线程多进程、一个进程多个线程多进程、一个进程多个线程西
45、安理工大学2006年P C B用用户户栈栈单线程进程模型单线程进程模型用户地址空间用户地址空间核核心心栈栈线程控制块：线程控制块：包含了寄存器映像，线程优先数和线程状态信息包含了寄存器映像，线程优先数和线程状态信息西安理工大学2006年P C B多线程进程模型多线程进程模型用户用户地址地址空间空间用用户户栈栈核核心心栈栈线程线程控制块控制块用用户户栈栈核核心心栈栈线程线程控制块控制块用用户户栈栈核核心心栈栈线程线程控制块控制块西安理工大学2006年引入线程的好处：引入线程的好处：创建一个新线程花费时间少（结束亦如此）创建一个新线程花费时间少（结束亦如此）两个线程的切换花费时间少两个线程的切换花
46、费时间少 （如果机器设有（如果机器设有“存储存储 恢复恢复 所有寄存器所有寄存器”指令，则整个切换过程用几条指令即可完指令，则整个切换过程用几条指令即可完成）成）因为同一进程内的线程共享内存和文件，因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核因此它们之间相互通信无须调用内核 适合多处理机系统适合多处理机系统西安理工大学2006年例子例子1 1：LANLAN中的一个文件服务器，在一段时间内需中的一个文件服务器，在一段时间内需要处理几个文件请求要处理几个文件请求因此有效的方法是：为每一个请求创建一个因此有效的方法是：为每一个请求创建一个线程线程在一个在一个SMPSMP机器上
47、：多个线程可以同时在不机器上：多个线程可以同时在不同的处理器上运行同的处理器上运行西安理工大学2006年例子例子2 2：一个线程显示菜单，并读入用户输入；一个线程显示菜单，并读入用户输入；另一个线程执行用户命令另一个线程执行用户命令考虑一个应用：由几个独立部分组成，这考虑一个应用：由几个独立部分组成，这几个部分不需要顺序执行，则每个部分几个部分不需要顺序执行，则每个部分可以以线程方式实现可以以线程方式实现当一个线程因当一个线程因I/OI/O阻塞时，可以切换到同一阻塞时，可以切换到同一应用的另一个线程应用的另一个线程西安理工大学2006年5.4.2 5.4.2 线程与进程的比较线程与进程的比较
48、调度调度 并发性并发性 拥有资源拥有资源 系统开销系统开销西安理工大学2006年5.4.3 5.4.3 线程的实现机制线程的实现机制 用户级线程用户级线程 核心级线程核心级线程 两者结合方法两者结合方法西安理工大学2006年一、用户级线程（一、用户级线程（User Level ThreadUser Level Thread）由应用程序完成所有线程的管理由应用程序完成所有线程的管理 通过线程库通过线程库(用户空间用户空间)一组管理线程的过程一组管理线程的过程 核心不知道线程的存在核心不知道线程的存在 线程切换不需要核心态特权线程切换不需要核心态特权 调度是应用特定的调度是应用特定的西安理工大学2
49、006年线程库线程库 创建、撤消线程创建、撤消线程 在线程之间传递消息和数据在线程之间传递消息和数据 调度线程执行调度线程执行 保护和恢复线程上下文保护和恢复线程上下文西安理工大学2006年对用户级线程的核心活动对用户级线程的核心活动 核心不知道线程的活动，但仍然管理线程核心不知道线程的活动，但仍然管理线程的进程的活动的进程的活动 当线程调用系统调用时，整个进程阻塞当线程调用系统调用时，整个进程阻塞 但对线程库来说，线程仍然是运行状态但对线程库来说，线程仍然是运行状态 即线程状态是与进程状态独立的即线程状态是与进程状态独立的西安理工大学2006年用户级线程的优点和缺点用户级线程的优点和缺点优点
50、：优点：线程切换不调用核心线程切换不调用核心 调度是应用程序特定的：可以选择最好的算法调度是应用程序特定的：可以选择最好的算法 ULTULT可运行在任何操作系统上（只需要线程库）可运行在任何操作系统上（只需要线程库）缺点：缺点：大多数系统调用是阻塞的，因此核心阻塞进程，大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞故进程中所有线程将被阻塞 核心只将处理器分配给进程，同一进程中的两个核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上线程不能同时运行于两个处理器上西安理工大学2006年二、核心级线程（二、核心级线程（KLTKLT）所有线程管理由核心完成所有
