《进程并发互斥》由会员分享，可在线阅读，更多相关《进程并发互斥（107页珍藏版）》请在金锄头文库上搜索。
1、3.5 进程并发与互斥3.5.1互斥算法3.5.2信号量(semaphore)3.5.3同步算法3.5.4经典的进程互斥同步问题13.5.1 互斥算法3.5.1.1临界资源3.5.1.2临界区的访问过程3.5.1.3同步机制应遵循的准则23.5.1.1 临界资源进程间资源访问冲突共享变量的修改冲突（空间）操作顺序冲突（时间）在多道程序环境下在多道程序环境下各进程之间存在资源共享，各进程之间存在资源共享，进程的运行时间和空间将会受影响进程的运行时间和空间将会受影响进程间的制约关系间接制约：进行竞争独占分配到的部分或全部共享资源，“互斥”直接制约：进行协作等待来自其他进程的信息，“同步”3共享变量
2、的修改冲突共享变量的修改冲突4操作顺序冲突操作顺序冲突有3个进程：get,copy和put，它们对4个存储区域f、s、t和g进行操作。5有有6种可能的操作顺序，只有一种结果是正确的。种可能的操作顺序，只有一种结果是正确的。6互斥：指多个进程不能同时使用同一个资源互斥：指多个进程不能同时使用同一个资源 为保证系统正常工作，多个并发进程在对共享的硬件或软为保证系统正常工作，多个并发进程在对共享的硬件或软件（如外设、共享代码段、共享数据结构）进行访问时（关键件（如外设、共享代码段、共享数据结构）进行访问时（关键是进行写入或修改），必须互斥地进行。是进行写入或修改），必须互斥地进行。 有些共享资源可以
3、同时访问，如只读数据。有些共享资源可以同时访问，如只读数据。v系统资源中每次只允许一个进程使用，而不能由多个进系统资源中每次只允许一个进程使用，而不能由多个进程同时共享的资源称为程同时共享的资源称为临界资源。临界资源。73.5.1.2 临界区的访问过程临界区临界区 临界资源临界资源（CriticalResources）：一种一次只能为一个进程服务的资源。 临界区临界区（CriticalSection）：进程中访问临界资源的程序。每个使用该资源的进程都要包含一个临界区。8临界区(criticalsection)：进程中访问临界资源的一段代码。进入区(entrysection)：在进入临界区之前，
4、检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志退出区(exitsection)：用于将“正在访问临界区”标志清除。剩余区(remaindersection)：代码中的其余部分。9。v两个进程不能同时进入访问同一临两个进程不能同时进入访问同一临界资源的临界区，这称为界资源的临界区，这称为进程互斥进程互斥。103.5.1.3 互斥机制应遵循的准则空闲则进空闲则进：当没有进程在临界区时，任何需要进入临界区的进程都允许立即进入。忙则等待：忙则等待：在共享同一对象的所有进程中，一次只能有一个进程进入临界区。其它要求进入临界区的进程只能等待。 有限等待：有限等待：任何
5、一个进程经有限时间等待后都能进入临界区，不允许出现进程“死等” 的情况。 让权等待：让权等待：当一个进程不能进入临界区时要立即阻塞自己，释放处理机让其它进程使用，避免“忙等”。 111、进程互斥的软件方法算法算法:加锁法加锁法设立一个公用整型变量key：描述允许进入临界区的标志进程在进入区循环检查是否允许进入临界区：key为1时，进程P可进入（否则是无限等待）；加锁（置key为0)，进入临界区；进程P退出临界区时解锁，在退出区修改允许进入标识key为1；缺点：多个进程可能同时进入临界区。12算法如下：ProcessP(1) ProcessP(2)Begin beginWhile(key=0)d
6、oskip;While(key=0)doskip;key=0;key=0;Criticalsection;Criticalsection;key=1;key=1;end.end.132、进程互斥的硬件方法为保证第一步和第二步执行不可分离。有些机器在硬件中设置了“测试与设置”指令，Test-and-Set指令（指令（TS指令）指令）该指令读出标志后设置为TRUEboolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old;lock表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲14互斥算法互斥
7、算法（TS指令）指令）利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；15Swap指令指令（或（或Exchange指令）指令）交换两个字（字节）的内容void SWAP(int *a, int *b) int temp; temp = *a; *a = *b; *b = temp;16互斥算法（互斥算法（Swap指令指令）利用Swap实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量keykey = TRUE;do SWAP(&
8、lock, &key); while (key) do skip;lock = FALSE;critical sectionremainder section17优点优点适用于任意数目的进程，在单处理器或多处理器上更显其优越简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量缺点缺点等待要耗费CPU时间，即“忙等”，不能实现“让权等待”可能产生“饿死”现象：有的进程可能永远执行不了18试考虑以下进程试考虑以下进程PA和和PB反复使用临界区的情况：反复使用临界区的情况：PAA：lock(key) unlock(key)Goto APBB：lock(key )unl
9、ock(key )Goto B193.5.2 信号量(semaphore)3.5.2.1信号量和P、V原语3.5.2.2利用信号量实现互斥多数互斥算法缺乏公平性，只有获得处理机的进程才可进行进入临界区的测试，且测试结果具有偶然性。需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。信号量代表可用资源实体的数量。203.5.2.1 信号量和P、V原语为了实现进程的互斥和同步，操作系统中引进了信号量(Semaphore)的概念。信号量具有以下特性：( 1) 信号量是一个整形变量。信
10、号量是一个整形变量。 2) 每一个信号量表示一种系统资源的状况，其值表示该资源每一个信号量表示一种系统资源的状况，其值表示该资源当前可用的数量，初值为非零。当前可用的数量，初值为非零。( 3) 每一个信号量都对应一个空或非空的等待队列。该队列就每一个信号量都对应一个空或非空的等待队列。该队列就是信号量所代表的资源的等待队列。是信号量所代表的资源的等待队列。 4) 对信号量只能实施对信号量只能实施P、V操作，只有操作，只有P、V操作原语才能改操作原语才能改变其值。变其值。21信号量只能通过初始化初始化和两个标准的原语两个标准的原语来访问作为OS核心代码执行，不受进程调度的打断初始化初始化资源信号
11、量为指定一个非负整数值，表示空闲资源总数空闲资源总数若为非负值表示当前的空闲当前的空闲资源数资源数，若为负值其绝对值表示当前等待临界区当前等待临界区的进程数的进程数221P操作原语操作原语 procedure P(var s:semaphore) begin s:=s-1; if s0 then W(s); end23qw(s)表示将调用表示将调用P操作原语的进程操作原语的进程置成等待信号量置成等待信号量s的状态。的状态。q进程执行进程执行P操作时，首先将信号量操作时，首先将信号量s减减1，其结果若其结果若so，则该进程继则该进程继续运行；若结果续运行；若结果so，则该进程继续执则该进程继续执
12、行。如果行。如果s0则释放则释放s信号量等待信号量等待队列中队首的进程，解除其阻塞状队列中队首的进程，解除其阻塞状态。调用态。调用V操作的当前进程继续执操作的当前进程继续执行。行。26P、V操作的物理意义：操作的物理意义：执行执行P操作：操作：s:=s-1意味着把意味着把s对应对应的一个资源分的一个资源分配给调用配给调用P操作的进程，资源的数量操作的进程，资源的数量减少一个。减少一个。若若s减一后其值为减一后其值为0，表示此类资源，表示此类资源已全部分配给各个进程了。已全部分配给各个进程了。27在此之后若又有进程请求该资源，在此之后若又有进程请求该资源，在该进程调用在该进程调用P操作时，操作时
13、，s减减1后成后成为负值，则执行为负值，则执行W(s)，该进程将转该进程将转换为阻塞态并进入信号量换为阻塞态并进入信号量s对应的等对应的等待队列中。待队列中。当信号量当信号量s为负值时，它的绝对值表为负值时，它的绝对值表示在该信号量等待队列中的进程数示在该信号量等待队列中的进程数目。目。28执行执行V操作时：操作时：s:=s+1意味着调用意味着调用V操作的进程释操作的进程释放了一个信号量放了一个信号量s对应的资源。对应的资源。s加一后，若加一后，若s为负值，表明为负值，表明s对应对应的等待队列中仍有等待该资源的阻的等待队列中仍有等待该资源的阻塞进程，则调用塞进程，则调用R(s)释放等待队列释放
14、等待队列中的一个进程。中的一个进程。29v被释放的进程是在执行被释放的进程是在执行P操作时因操作时因资源不足而进入阻塞态的，由于资源不足而进入阻塞态的，由于V操作释放了它所需的资源，它就转操作释放了它所需的资源，它就转换为就绪态可以继续执行。换为就绪态可以继续执行。30 记录型信号量每个信号量s 除一个整数整数值值s.count（计数）外，还有一个进程等待队列进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识311. P 原语wait(s)-s.count;/表示申请一个资源;if (s.count 0)/表示没有空闲资源; 调用进程进入等待队列 s.queue; 阻塞调用进程;
15、322. V 原语signal(s)+s.count;/表示释放一个资源；if (s.count 383.5.3进程同步1、同步概念直接制约一组并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程消息(事件）进程互相给对方进程发送执行条件已经具备的信号同步一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步39PC（计算进程）:A:计算得到计算结果Buf计算结果Goto APP（打印进程）:B:打印Buf中的数据清除Buf中的数据Goto B40 一般来说，可以把各进程之间发送的消息作为一般来说，可以把各进程之间
16、发送的消息作为信号量看待。与进程互斥时不同的是，这里的信号信号量看待。与进程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关而不是与整组并量只与制约进程及被制约进程有关而不是与整组并发进程有关。因此，称该信号量为发进程有关。因此，称该信号量为私用信号量私用信号量（Private Semaphvre）。）。412、同步的实现方法利用信号量来描述前趋关系前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个信号量S12，其初值为042 s1,s2:semaphore; s1=1,s2=0; cobegin repeat T1; repe
17、at T2; coend; 设定两个信号量s1和s2，s1的初值为1，s2的初值为0。 如上例，有两个进程如上例，有两个进程T1和和T2，要求要求T1和和T2同步运行，则同步运行，则43procedure T1: procedure T2: begin begin P(s1); P(s2);m1; m2;V(s2); V(s1); end; end;44只能由一个进程对其实施P操作的信号量称为该进程的私有信号量。s1是T1的私有信号量，s2是T2的私有信号量。在两个进程相互推进的运行过程中，哪个进程的私有信号量为1，就表示它可以向前推进。453.5.4 经典互斥同步问题 生产者消费者问题生产者
18、消费者问题(the producer-consumer problem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一一个个进程可对共享缓冲区进行操作。46生产者进程不断生产产品并把它们放入缓冲区内，消费者进程不断从缓冲区中取走产品进行消费。当缓冲区中产品已经放满时，表示生产速度高于消费而出现了供过于求。这时，生产者进程不能再生产而必须等待产品被消费。当缓冲区取空时，表示消费速度高于生产而出现了供不应求。这时，消费者进程不能再消费而必须等待产品的生产。生产和消费的进程必须达到同步运行，才能使供需平衡。
19、47缓冲区是一个临界资源，两个进程访问缓冲区必须互斥地执行。设一个公用信号量mutex，其初值为1。设生产者进程的私有信号量为empty，表示缓冲区中空闲位置的数目，即可以容纳产品的数目，初值为n。设消费者进程的私有信号量为full，表示缓冲区内已有产品的数目，其初值为0。48 mutex,empty,full:semaphore; mutex:=1;empty:=n;full=0; cobegin producer: begin L1: produce a product; P(empty); P(mutex); Add to buffer; V(full); V(mutex); goto
20、L1; end;49 consumer: begin L2: P(full); P(mutex); take one from buffer;V(empty);V(mutex);consume product;goto L2; end; coend;50采用信号量机制：full是“满”数目，初值为0，empty是“空”数目，初值为N。实际上，full和empty是同一个作用，始终有full+empty=Nmutex用于访问缓冲区时的互斥，初值是1每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁(为什么？)51v无论是生产者进程还是消费者进程，无论是生产者进程还是消
21、费者进程，其中其中V操作的次序是无关紧要的，操作的次序是无关紧要的，但但P操作的次序不能颠倒。操作的次序不能颠倒。52 读者写者问题读者写者问题(the readers-writers problem)问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读写”互斥，“写写”互斥，“读读”允许53采用信号量机制：mutex互斥信号量:实现读者与写者、写者与写者之间的互斥，初值是1。Rcount读者共享的变量:表示“正在读”的进程数，初值是0；Rmutex表示对Rcount的互斥操作，初值是1。P(Rmutex);if (Rcount = 0)then P(mut
22、ex);+Rcount;V(Rmutex);read;P(Rmutex);-Rcount;if (Rcount = 0)thenV(mutex);V(Rmutex);ReaderP(mutex); write;V(mutex);Writer54哲学家用餐问题哲学家用餐问题 在该问题中设想有5位哲学家，他们共同坐在一张餐桌前用餐，用餐过后开始思考问题。他们的生活方式可描述为一个单调的循环：思考-饥饿-用餐-再思考。已知餐桌上摆的是面条，每个人必须左右手各拿到一把叉子才可以开始进餐。而餐桌上只有5把叉子，任两个哲学家之间有一把，见图所示。55第i位哲学家的行为过程可描述为下面的形式。Process
23、Philosopher(i)BeginWhile(true)BeginThinking();P(mutexi);/请求左叉子P(mutexi+1mod5);/请求右叉子Eating();/用餐过程V(mutexi);/释放左叉子V(mutexi+1mod5);/释放右叉子End;End;56附：信号量集一段处理代码需要同时获取两个或多个临界资源可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait(SimultaneousWait)。在Swait时，各个信号量的次序并
24、不重要，虽然会影响进程归入哪个阻塞队列，但是由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。信号量集用于同时需要多个资源时的信号量操作信号量集用于同时需要多个资源时的信号量操作1.AND型信号量集AND型信号量集用于同时需要多种资源且每种占用一个时的信号量操作；57Swait(S1, S2, , Sn)/P原语；while(TRUE)if(S1=1&S2=1&Sn=1)/满足资源要求时的处理；for(i=1;i=n;+i)-Si;/注：与wait的处理不同，这里是在确信可满足/资源要求时，才进行减1操作；break;else/某些资源不够时的处理；调用
25、进程进入第一个小于1信号量的等待队列Sj.queue;阻塞调用进程;58Ssignal(S1, S2, , Sn)for(i=1;i=n;+i)+Si;/释放占用的资源；for(eachprocessPwaitinginSi.queue)/检查每种资源的等待队列的所有进程；从等待队列Si.queue中取出进程P;if(判断进程P是否通过Swait中的测试)/注：与signal不同，这里要进行重新判断；/通过检查（资源够用）时的处理；进程P进入就绪队列;else/未通过检查（资源不够用）时的处理；进程P进入某等待队列；592. 一般“信号量集”一次需要N个某类临界资源时，就要进行N次wait操作
26、低效又可能死锁基本思想：在AND型信号量集的基础上进行扩充：进程对信号量Si 的测试值为ti（用于信号量的判断，即Si=1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区；一般“信号量集”未必成对使用Swait和Ssignal如：一起申请，但不一起释放；61独木桥问题:某一条河上有一座独木桥，有人从北向南过桥，有人自南向北过桥，由于独木桥一次只能承载一人，所以请用信号量设计一种算法，让南北双方都能合理通行。公共汽车问题：在公共汽车上，售票员和司机需要合理配合才能保证运行。设售票员必须等汽车停止才能开门、上客、关门、售票；而司机必须等门关好了才能开车、行驶、到站、停车。现在请你用P
27、V原语操作来同步司机和售票员的工作。思考题62假定一个阅览室最多可同时容纳100个人阅读，读者进入和离开阅览室时，都必须在阅览室门口的一个登记表上登记。假定每次只允许一个人登记和去掉登记，设阅览室内有100个座位。请用P,V原语编写读者进程的同步算法。63附：附： 管程(monitor)用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保管程是管理进程间同步的机制，它保证进程互斥地访问共享资源，并方便地阻塞和证进程互斥地访问共享资源，并方便地阻塞和唤醒进程唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。64 信号
28、量同步的缺点同步操作分散：同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；不利于修改和维护：不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；65管程的引入管程的引入 这是一种具有面向对象程序设计思想的同步机制。它提供了与信号量机制相同的功能。管程（Monitor）概念是著名学者Hore于1974年提出
29、的，并在很多系统中得到实现，诸如Pascal、Java、Modula-3等。 管程是由局部数据结构、多个处理过程和一套初始化代码组成的模块。 管程的特征为：管程的特征为： （1）管程内的数据结构只能被管程内的过程访问，任何外部访问都是不允许的； （2）进程可通过调用管程的一个过程进入管程； （3）任何时间只允许一个进程进入管程，其他要求进入管程的进程统统被阻塞到等待管程的队列上。 66下图是管程的一个结构模型67lP（c）：当遇到同步约束，就将进程阻塞在条件变量c关联的等待队列上。lV（c）：从条件变量c关联的等待队列上唤醒一个进程，让它恢复运行。若队列上没有进程在等待，就什么也不做。管程的语
30、言结构可描述为下属形式：管程的语言结构可描述为下属形式：Type管程名=MonitorBegin 数据结构定义； 局部变量定义； 条件变量定义；Porcedure过程名（形式参数） Begin/过程体End;End;68模块化：模块化：一个管程是一个基本程序单位，可以单独编译复合数据类型：复合数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装：信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的 管程的主要特性69管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来
31、间接地访问管程中的共享变量为了保证管程共享变量的数据完整性，规定管程互斥进入管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作管程的实现要素70TypePC=MonitorBeginVarChar:bufferN;VarInteger:counter,in,out;VarCondition:notfull,notempty;PorcedurePUT（varchar:item）Beginifcount=NthenP(notfull);Bufferin:=item;in:=(in+1)modN;Count:=count+1;V(notempty);End;Porce
32、dureGET（char:item）Beginifcount=0thenP(notempty);item:=Bufferout;out:=(out+1)modN;Count:=count-1;V(notfull);End;Begincount,in,out=0,0,0;End;End;利用管程PC解决生产者-消费者问题71ProcedureConsumer()BeginVarchar:x;While(true)BeginGET(x);Consume_the_item_in_x();EndEnd;应用程序算法如下。ProcedureProducer()BeginVarchar:x;While(t
33、rue)BeginProduce_an_item_in_x();PUT(x);End;End;72管程的优点管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。733.6 进程间通信(IPC, INTER-PROCESS COMMUNICATION)3.6.1进程间通信的类型
34、3.6.2共享存储器系统3.6.3管道(pipe)3.6.4消息传递741. 低级通信和高级通信低级通信和高级通信低级通信：低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量。优点：速度快。缺点：传送信息量小。效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。主要用于控制进程执行速度的作用。用户直接实现通信的细节，编程复杂，容易出错。高级通信：高级通信：能够传送任意数量的数据，目的主要是用于交换信息。3.6.1 进程间通信的类型752.进程的通信方式共享存储区方式不要求数据移动，可以任意读写和使用任意数据结构，需要进程互斥和同步的辅助来确保数据一致性
35、管道方式消息或邮箱机制消息的发送不需要接收方准备好，随时可发送763.6.2 3.6.2 共享存储器系统共享存储器系统 这种通信需要在内存中开辟一个共享的存储空间，供进程之间进行数据传递。比如计算进程将所得的结果送入内存共享区的缓冲区环中，打印进程从中将结果取出来，就是一个利用共享存储器进行通信的例子。这种通信方式在UNIX、Linux、Windows及OS/2等系统中都有具体的实现。 共享存储器系统中，共享的空间一般应当是需要互斥访问的临界资源。诸多进程为了避免丢失数据或重复取数，需要执行特定的同步协议。 在利用共享存储器进行通信之前，信息的发送者和接收者都要将共享空间纳入到自己的虚地址空间
36、中，让它们都能访问该区域。存储器管理模块将共享空间映射成实际的内存空间。77（1）创建或删除共享存储区（2）共享存储区的附接与断接 （3）共享存储区状态查询 （4）共享存储区管理共享存储器系统的特点：利用共享存储器系统进行通信的效率特别高，适用于通信速度要求特别高的场合。这种同步与互斥机制的实现一般要由程序员来承担，系统仅仅提供一个共享内存空间的管理机制。78Linux的共享存储区创建或打开共享存储区(shmget)：依据用户给出的整数值key，创建新区或打开现有区，返回一个共享存储区ID。连接共享存储区(shmat)：连接共享存储区到本进程的地址空间，可以指定虚拟地址或由系统分配，返回共享存
37、储区首地址。父进程已连接的共享存储区可被fork创建的子进程继承。拆除共享存储区连接(shmdt)：拆除共享存储区与本进程地址空间的连接。共享存储区控制(shmctl)：对共享存储区进行控制。如：共享存储区的删除需要显式调用shmctl(shmid,IPC_RMID,0)；793.6.3 管道通信 管道（Pipe）是可供进程共享的一种外存文件，主要用于连接一个写入进程和一个读出进程，以实现它们之间的数据通信。写入进程按字符流的形式将数据写入管道文件中，让读出进程从中获得数据。由于管道机制特别适用于大容量数据的通信，因此在许多操作系统中被采用。 管道通信机制分为无名管道和有名管道 80进程通信实
38、例管道(pipe)UNIX最早的消息传递机制是管道，管道是一条在进程间以字节流方式传送的通信通道。管道逻辑是被看作是管道文件，物理上则是由文件系统的高级缓冲区（通常几十KB）来实现，是单向的。在使用管道前要建立相应的管道，然后才可使用。利用利用UNIX提供的系统调用提供的系统调用pipe，可建立一条同步通信管道。可建立一条同步通信管道。其格式为：其格式为：pipe(fd) intfd2；这里，这里，fd1 为写入端，为写入端，fd0为读出端。为读出端。81示例例：用C语言编写一个程序，建立一个pipe，同时父进程生成一个子进程，子进程向pipe中写入一字符串，父进程从pipe中读出该字符串。解
39、：程序如下：#includestdio.hmain()intx，fd2；charbuf30，s30；pipe(fd)；/*创建管道*/while(x=fork()=-1)；/*创建子进程失败时，循环*/if(x=0)82sprintf(buf，Thisisanexamplen)；write(fd1，buf，30)；/*把buf中字符写入管道*/exit(0)；else/*父进程返回*/wait(0)；read(fd0，s，30)；/*父进程读管道中字符*/printf(%s，s)；831. Linux 管道通过pipe系统调用创建无名管道，得到两个文件描述符，分别用于写和读。intpipe(i
40、ntfildes2);文件描述符fildes0为读端，fildes1为写端；通过系统调用write和read进行管道的写和读；进程间双向通信，通常需要两个管道；只适用于父子进程之间或父进程安排的各个子进程之间；Linux中的命名管道，可通过mknod系统调用建立：指定mode为S_IFIFOintmknod(constchar*path,mode_tmode,dev_tdev);842. Windows NT 管道无名管道：类似于Linux管道，CreatePipe可创建无名管道，得到两个读写句柄；利用ReadFile和WriteFile可进行无名管道的读写；BOOLCreatePipe(PH
41、ANDLEhReadPipe,/addressofvariableforreadhandlePHANDLEhWritePipe,/addressofvariableforwritehandleLPSECURITY_ATTRIBUTESlpPipeAttributes,/pointertosecurityattributesDWORDnSize/numberofbytesreservedforpipe);85 系统中的进程在交互传送数据时，涉及到对数据结构的互斥使用问题。为实施互斥，进程之间需要同步。提供这些功能的一个好方法是消息传递。还有一个优点是，消息传递可较容易地在单处理机系统、分布式系统
42、、共享存储器的多处理机系统中实现。 消息传递中的管理机制由操作系统提供，主要体现为以下两个原语。 发发送送原原语语：send(destination,message)，其中，destination为消息的目的地（接收进程名）。该原语表示发送消息到进程destination。 接接收收原原语语：receive(source,message)，其中，source是消息发出地（发送进程名）。该原语表示从进程source接收消息。3.6.4 3.6.4 消息传递消息传递86 在这种方式中要解决的关键问题仍然是同步问题：仅当一条消息从某个进程发送后，其他进程才可能接收到消息。那么，消息发送者通过send
43、原语发出一条消息后，应当如何处理呢？有两种选择：要么将发送进程阻塞起来，直到消息被接收为止，再把它唤醒；要么不阻塞发送进程。 同样地，消息接收者通过receive原语要接收一条消息时，如果能立即收到，可继续运行。如果消息尚未发出的话，也有两种选择：要么阻塞进程等待消息；要么不阻塞进程，放弃接收。 这样一来，系统可选择的处理有以下几种： 会合（会合（renezvousrenezvous）方式方式 宽松同步方式宽松同步方式 不阻塞发送者，只阻塞接收者方式不阻塞发送者，只阻塞接收者方式 一、实现同步的方法一、实现同步的方法 87 在消息传递中，发送者需要明确消息发往哪里，接收者需要指明消息的来源。通
44、常，按send和receive原语的实现方式可分为直接寻址和间接寻址两类。 1. 1. 直接寻址（直接寻址（Direct AddressingDirect Addressing） 实现直接寻址的一个较为简单的方案是，让send原语明确指出接收者的进程号，receive原语明确指出发送者的进程号，系统根据这两个原语实现直接通信。这种一对一的通信，用来处理并发进程之间的合作是相当有效的。 2. 2. 间接寻址（间接寻址（Indirect AddressingIndirect Addressing） 在间接寻址方式中，消息并不直接从发送进程传到接收进程，而是要经过一个中间介质临时保存消息的队列，通常
45、称为“信箱”。因此，两个通信进程的操作是，一个进程将消息发到信箱中，另一个从信箱中取消息。二、直接通信和间接通信二、直接通信和间接通信 883.7 线程(THREAD)3.7.1线程的引入3.7.2进程和线程的比较3.7.3线程的执行3.7.4线程的分类引入线程的目的是以小的系统开销来提高进程内的并发程引入线程的目的是以小的系统开销来提高进程内的并发程度。度。893.7.1 线程的引入 为提高进程内各个功能模块的并发性为提高进程内各个功能模块的并发性传统传统os：为：为进程创建一些子孙进程进程创建一些子孙进程进程：进程：资源分配单位（存储器、文件）和CPU调度（分派）单位，由PCB和进程间上下
46、文确定。由于进程是资源的拥有者，故其在创建、撤销及状态转换时，系统要付出较大的时间和空间开销，从而使得系统中的进程不宜过多，切换频率不宜太高，因此限制了并发程度的提高。为了减少程序并发所付出的时间和空间开销，使os具有更好的并发性，把进程的两个基本属性分开。90现代现代os：一个进程可以创建多个线程一个进程可以创建多个线程线程：线程： “轻量级进程（LightweightProcess）”，是进程的一个实体，使被独立调度和分派的基本单位，表示进程中的一个控制点（执行体），执行一系列指令。91进程进程只作为其他资源分配单位线程线程作为CPU调度单位只拥有必不可少的资源，如：线程状态、寄存器上下文
47、和栈同样具有就绪、阻塞和执行三种基本状态线程的优点：线程的优点：减小并发执行时的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。线程的创建时间比进程短线程的终止时间比进程短同进程内的线程切换时间比进程短由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信92进程与线程的关系进程与线程的关系93 线程结构线程结构任一线程有一个独立的栈和一个线程控制块（TCB）。TCB的内容包括：线程标识、优先数，及线程状态、寄存器值、堆栈指针等信息。其中： l线程状态保存线程的当前状态： 运行/阻塞/就绪。 l寄存器值保存线程寄存器的上下文。 l堆栈指针保存线
48、程的栈指针。94下图是多线程环境中的一个进程及其3个线程的模式95线程和进程96多线程与进程之间的关系97线程的使用字处理程序字处理程序与用户交互后台排版自动保存数据处理程序数据处理程序输入线程处理线程输出线程983.7.2 进程和线程的比较地址空间和其他资源（如打开文件）：地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享调度：调度：线程上下文由于其小而创建、撤销及切换时间比进程上下文切换要快得多并发性：并发性：不仅进程之间可并发执行，一个进程中的多个线程之间也可并发执行，从而os具有更好的并发行。切换：切换：同一进程中，线程的切换不会引起进程的切换，只有从一进程中的线
49、程切换到另一进程中的线程时，才会引起进程的切换。993.7.3线程的执行线程的状态与操作 线程有 3 个基本状态 , 即执行、就绪和阻塞。100 五种基本操作是 : (1)派生 (spawn): 线程在进程内派生出来 , 它即可由进程派生 , 也可由线程派生。thread_create(2)阻塞(Block):如果一个线程在执行过程中需要等待某个事件发生,则被阻塞。thread_wait；thread_yield(3)激活(unblock):如果阻塞线程的事件发生,则该线程被激活并进入就绪队列。(4)调度(schedule):选择一个就绪线程进入执行状态。(5)结束(Finish):如果一个线
50、程执行结束,它的寄存器上下文以及堆栈内容等将被释放。thread_exit1013.7.4 线程的分类OS OS 对线程的实现方式对线程的实现方式102由内核来维护进程和线程的上下文信息；线程的切换由内核来完成；时间片等额分配给内核线程，所以多内核线程的进程获得更多的CPU时间。内核线程内核线程(kernel-level thread)依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。WindowsNT和OS/2支持内核线程；好处：一个内核线程发起系统调用而阻塞，不会影响其他线程的运行。103用户线程用户线程(user-level thread)用户线程的维护由应用进程完
51、成内核不了解用户线程的存在用户线程切换不需要内核特权用户线程调度算法可针对应用优化采用不依赖于OS核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个用户线程发起系统调用而阻塞，则其所在的整个进程就在等待。由于时间片等额分配给进程，若进程是多线程则每个线程就慢。104采用用户级线程的好处是：管理线程的数据结构都在用户地址空间中，线程的切换不需要内核访问特权。从而减少了在两种模式之间切换的开销。 各个应用程序可采用适合自己的专用线程调度算法，比如有的可能采用高优先级调度，而有的可能是简单的循环调度。这些算法仅适应应用程序而不会对内核中的进程调度产生影响。 用户级线程可以在各种操作系统中运行，只要装有一个可共享的应用级上的实用程序库线程库就可以了。105核心级线程的上下文切换时间要大于用户级线程的上下文切换时间。实现用户级线程不需要操作系统内核的特殊支持，只要有一个能提供线程创建、调度、执行、撤销，以及通信等功能的线程库就行了。106作业三(2)什么是线程？试述线程与进程的区别。107
