第4章并行性：互斥和同步

1、第第4 4章章 并行性：互斥和同步并行性：互斥和同步 主讲：房道伟主讲：房道伟Daowei_操作系统原理操作系统原理主要内容n顺序程序设计和并行程序设计顺序程序设计和并行程序设计n进程间的同步与互斥进程间的同步与互斥n信号量信号量 (P，V操作操作)n同步机构应用同步机构应用n进程间的通讯进程间的通讯 在多道环境下，系统具有了许多比单道环在多道环境下，系统具有了许多比单道环境下更为复杂的情况。我们把多道环境下的程境下更为复杂的情况。我们把多道环境下的程序设计叫做并行程序设计，因为它主要是以各序设计叫做并行程序设计，因为它主要是以各程序程序(进程进程)间的并行运行为其特点。把传统的程间的并行运行

2、为其特点。把传统的程序设计方法叫做顺序程序设计。序设计方法叫做顺序程序设计。4.1 顺序程序设计和并行程序设计顺序程序设计和并行程序设计一、顺序程序设计一、顺序程序设计1. 顺序程序顺序程序 (冯诺伊曼冯诺伊曼) 匈牙利数学家匈牙利数学家 Vonnevman 46年年(a) 计算 对某一有限数据的集合所施行的，目的在于解决某一问题的一组有限操作的集合。程序是算法的形式化描述，一个程序的执行过程即一个“ 计算”，即算法的实现。(b) 顺序执行：I1C1O1I2C2O2job1job2图4.1 顺序处理模式计算中的各个操作有一定顺序，否则无法正确执行。(c) 顺序程序的特点：(i) 顺序性：顺序性

3、： 处理机的操作严格按程序规定的顺序执行。即每一操作都必须在下一操作开始之前结束。(ii) 封闭性：封闭性： 程序一旦开始执行，计算结果不受外界影响初始条件给定，各资源状态仅能由程序改变。 资源独占 与执行速度无关(iii) 可再现性：可再现性：只要给了相同的外界条件，结果亦相同。二、并行程序设计二、并行程序设计1. 为了提高系统的利用率和处理能力：为了提高系统的利用率和处理能力：采用：(1) 硬件 并行操作 (2) 软件 程序段在执行时间上有重叠(不一定全部重叠)。并行性：是指在同一时间间隔内或同一时刻完成两种或两种以上性质相同或不同的工作，只要时间上互相重迭，都存在并行性。多道程序的特点：

4、首先是并行。多个程序在并行执行 AB多个设备在并行操作 I/O AI/O B若顺序执行3分钟 ( job1， job2， job3 )并行执行5/3分钟 ( job1， job2， job3 )I1I2I3C1C2C3O1O2O3t并行的2. 程序并行性的表示程序并行性的表示(1) 图示：在一个程序的诸操作间，往往只要求部分有序，既有并行执行部分，又有串行执行部分。SFP1P2P3a. 串行FSP1P2P3P4P5b. 并行SFc. 串、并行P1P2P3P4Fd. 一般的P1SP2P3P4P5P6P7例：(a+b) (c+d) (e/f)t1 = a + bt2 = c + dt3 = e /

5、 ft4 = t1 t2t5 = t4 t3St1t2t3t4t5F/+ab cdef(2) 并行语言：Diskstra 于1965年提出类Pascal的并行语句。COBEGINs1；s2；snCOENDSs1 snFCOBEGIN / COEND相当于一个括号，表示其中的所有语句s1, s2, sn是可并行执行的，COBEGIN / COEND 可以嵌套，而语句s1, s2, sn可为任何简单语句、复合语和并行语句。例： BEGIN COBEGIN t3; BEGIN COBEGIN t1; t2 COEND; t4 END COEND t5 END3. 并行程序设计的特点：并行程序设计的特

6、点：(1) 并行性：(2) 共享性： 在系统中存在的各进程不但共享硬资源：主存、CPU、外设，而且共享软资源：程序副本和数据集。 顺序运行的模式被打破，各进程可并行地、异步地在系统内运行，并以不同速度向前推进。因为并行执行 (共享资源)使得：(在不做处理条件下)(i) 失去封闭和现场的可再现性：例：设夫妻两人的共同存款保存在count(共享资源)变量中，为此，他们编写了一个增加款项的程序如下：begin covnt, N, M: integer cobegin PA: begin N: = count; N: = N+100; count: = N; endPB: begin M: = cou

7、nt ; M: = M+200 ; count: = M ; endcoundend速度：设原count = 300$，A 100，B 200时间：t0 A: N = count; N: = N+100 N = 400$t1 B: M = count; M: = M+200; count = M, count = 500$t2 A: count: = N count = 400$+与执行速度有关 (我们不能保证它们每次执行时间相同，进展速度一致)。(ii) 程序与计算不再一一对应：程序 静态的，是指令的有序集合。计算 执行过程，动态。并行执行 程序可对应多个计算。 (例如一个编译程序可为2个作

8、业服务，每个作业调用一次，就执行一次，即这个编译程序对应两个“ 计算”)。顺序执行 程序与计算一一对应。(iii) 程序并发执行时相互制约： 并行程序设计所带来的这些新问题，都最后归结为能否正确处理好进程间的同步与互斥关系问题。下面我们通过进程间的同步与互斥关系来进一步剖析并行程序设计中的问题。4.2 进程间的同步与互斥进程间的同步与互斥一、概念一、概念 进程并行运行时相互制约 (进程发消息限制另一进程运行)，而制约关系归结为互斥和同步：同步 指两个事件的发生有着某种时序上的关系(先，后)。互斥 资源的使用要排它使用，防止竞争冲突(不同时使用，但无先后次序)。 (作为一种特殊同步)二、临界段问

9、题二、临界段问题1. 只能排它使用的资源称为临界资源。只能排它使用的资源称为临界资源。(各进程要共享资源)。临界资源打印机、磁带机。 (因时因地不同)只能排它使用的变量、表格、队列。非临界资源：磁盘临界区(段) 将访问临界资源的那段程序从概念上分离出来称为临界。(对临界区的访问必须是互斥的)cs例：二人合作存款 (上例：)cobeginPA: N: = count N: = N+100 count: = N;PB: M: = count M: = M+200由 count: = Mcoendcs1cs2cs1cs2countcs临界区临界资源上例中讲过执行速度的不同，导致结果不唯一。(1) 因

10、为count是一个互斥性使用的变量 (有排它性)。R W不许打断count (变量)在(2) 若仅读(R)或仅写(W)，count不具有排它性。2. 怎么才能保证诸进程间互斥地执行临界区(段)以访问共享变量呢？(即解决了临界区对临界资源的访问，就解决了互斥问题)。原则：有空让进、忙则等待、有限等待、让权等待、原则：有空让进、忙则等待、有限等待、让权等待、多种选一多种选一为此，Diskstra于65年提出临界段设计原则；(i) 每次至多只允许一个进程处于临界段之中；(ii) 如果有多个进程同时要求进入临界区，应在有限时间内使其之一进入；(iii) 进程只能在临界区中逗留有限时间。临界区 几个进程

11、P1P2P3AB3. 禁止中断实现互斥（关中断）：禁止中断实现互斥（关中断）： 即当某一进程进入临界区后，屏蔽所有中断，进程退出临界区后，再重新开放所有中断。 由于CPU在进程间的转换是时钟或其它中断所导致的直接结果，所以关中断后，其它进程不可能获得运行的机会，自然也不可能执行其它程序而进入临界区。缺点：(1) 关闭中断为特权指令，给用户使用可能导致严重后果，如忘记开中断了，则使系统无法运行。 (2) 仅适合单 CPU系统，而在多 CPU系统中，其它CPU上的进程仍可能进入CS段，而导致竞争状态的出现。4. 软件方法：软件方法： 使用软件解决临界段互斥执行，将临界区用信号隔离开来，若要进入，先

12、测信号：flag = 1，已有进程进入0，无进程进入软件一般结构：cobegin P1: 入口代码 临界区CS 退出代码 非临界区NCS COEND例：cobegin PA：begin L：if flag = 1 then goto L else flag: = 1; N: = count; N: = N+1; count: = N; flag: = O NCS endcsPB：begin X：if flag = 1 then goto X else flag: = 1; M: = count; M: = M+1; count: = M; flag: = O end coendcs注：1. 该

13、程序解决了问题吗？没有！多了个互斥变量flag； 2. 关键在于程序可被分割：(当flag = O时) (由于执行速度不一致，执行时间不一定相同，则因临界资源互斥变量flag)5. 硬件指令：硬件指令：前述 . 原语 执行时不可分割的那些系统调用，被称为原语。 当执行一组指令时，从第一条起，除非自愿放CPU，否则它要一直完成该组指令才放弃CPU，这种特性称“ 原语的不可分割性”。利用原语的不可分割性，将前述测试语句定为原语，置于内核中。原语的不可分割性：Lock (w) L: if w = 1 then goto L else w: = 1 unlock (w) 开锁 w: = 0；上锁例：f

14、lag: integer cobegin PA: begin Lock (flag); csA; unlock (flag) endPB: begin Lock (flag); csB; unlock (flag) end;coend;进程A或进程B上锁原语进入临界区csA或csB上锁原语进程使用临界资源的操作 许多大型机和微型计算机中都提供了专门的硬件指令，这些指令都允许对一个字中的内容进行检测和修正，或交换两个字的内容。 现在我们用一条指令来完成检测和修改两 个功能，这样中断和插入另一处理机的存储周期均不可能，所以不会影响此公用变量数据的完整性。实现这种功能的硬件指令有两种：(1) TS

15、(Test-and-Set) 指令。又称检测和设置指令，该指令的功能可用PASCAL语言描述如下：function Test-and-Set (var flag : boolean) : boolean begin Test-and-Set : = flag ; flag : = true ; end这条指令在微型计算机Z-8000中称为TEST指令，在IBM 370中称为TS指令。(2) Swap指令。又称交换指令，该指令的功能是交换两个字的内容，它可用PASCAL语言描述如下：procedure Swap (var a ,b : boolean) var temp : boolean ;

16、begintemp : = a; a : = b ;b : = temp ; end在微型计算机 Intel 8086或8088中，该指令称为 XCHG 指令。 用这些硬件指令可以简单而有效地实现互斥。其方法是为每个临界段或其它互斥资源设置一个布尔变量，例如称为 lock，当其值为 false 则临界段未被使用，反之则说明正有进程在临界段中执行。于是某进程用TS指令实现互斥的程序结构为（设为无限循环进程）：repeat while TS (lock) do Skip ;进程的临界段代码 CS ;lock : = false ;进程的其它代码 ;forever或者用 Swap 指令来实现互斥，则

17、repeat key : = true repeat Swap (lock, key) ; until key = false ; 进程的临界段代码 CS ; lock : = false ; 进程的其它代码 ;forever注记：(i) 忙等待： 浪费时间。 用上述硬件指令虽然可以有效地保证进程间互斥，但有一个缺点，就是当进程正在临界段中执行时，其它想进入临界段的进程必须不断地测试布尔变量lock的值，这就造成了处理机机时的浪费，我们常称这种情况为“ 忙等待”。4.3 信号量信号量 (P，V操作操作)1. 信号量是荷兰的计算机科学家信号量是荷兰的计算机科学家Dijkstra65年提出年提出的

18、，也是最早的同步方法。的，也是最早的同步方法。所谓信号量：是一个仅能由同步原语对其进行操作的整型变量。Dijkstra将这两个同步原语命名为“ P操作”，“ V操作”。发信号等待(看字母) 荷兰语信号量二元信号量：允许取值为“ 0”与“ 1”，主要用作互斥变量。一般信号量：允许取值为非负整数，主要用于进程间的一般同步问题。2. P，V操作操作P，V操作是对信号量进行的原语操作。Dijkstra对这两个原语操作定义如下：P(S)：当信号量S大于0时，将S值减1，否则进程等待，直到其它进程对S进行V操作V(S)。V(S)：将信号量S的值加1。P，V操作的功能描述见下图： 入口 S1 S S0 入信

19、号量等待队列 置“ 等待”状态 转进程调度 0 P，V操作可用软件(或固件)和硬件来执行。无论P操作和V操作，它们的执行都必须是一个 不可被中断的整体。注：(1) 物理意义：S 0时，S为可用资源量；S = 0时，可用资源量正好用完；S 0 立即可得S 0 要排队(2) P(S) Lock (S)S为二元信号量V(S)unlock (S)对应V(S)：表示释放资源本书原来使用P、V操作来称呼此两操作，但由于信号量和信号量上的同步原语以及后面要讨论的管程均已成为并行程序语言的组成部分，所以改用程序语言中的习惯称呼，以及国际上较流行的称呼为Wait和Signal操作。3. 当进程必须在信号量当进程

20、必须在信号量S上等待时，就将该进程的状态上等待时，就将该进程的状态变为等待状态变为等待状态(或活动阻塞状态或活动阻塞状态)，并将该进程插入与，并将该进程插入与此信号量有关的等待队列中，而后让出处理机给其此信号量有关的等待队列中，而后让出处理机给其它就绪进程。它就绪进程。“ 阻塞等待”方式下的wait和signal操作：(1) 一般信号量上的同步原语： 等待进程放入与此信号量S有关的阻塞队列，需要有该队列的头指针，因此要把信号量定义进一步进行扩充，扩充成为记录形式：type Semaphore = record value : integer; L: pointer to PCB endwait

21、(s): S.value: = S. value 1; if S. value 0 (说明 S原 0或0 “ 计算下一数，进入缓冲区” V(SA); 已有结果，可置标志，SA=SA+1forever PP: repeat P(SA); 已放入结果否？ “ 从缓冲区中取数” receive V(SB): 置空标志，让CP释放下一数 打印该数据 output forever coendend注记：(a) 与P，V互斥比较(i) 互斥一次进一个入cs，但谁先谁后无关系，而同步，先后次序有关。 (ii) 互斥：Lock，unlock 同步：P，V，互发信号(b) 信号量的个数SA 数据 SB 空 Bu

22、ff(c) 初值：变化则程序也变化，取代上面CP程序段若SB: = 0; CP: repeat “ 放入Buff ” V(SA); P(SB);forever进程互斥：进程互斥：在OS中，当某一进程正在访问cs时，就不允许其它进程来读写(访问)，否则就会发生后果无法估计的错误，进程之间的这种相互制约关系为进程互斥。进程同步：进程同步：并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息，称为进程同步。进程同步与互斥关系：进程同步与互斥关系：都反映了在异步环境下并发进程间的相互制约关系。可归于同步范畴，但互斥是同步问题的一个特例，互斥解决临界区的使用，同步是并发进程在一

23、些关键点上需互相等待互发消息。例3. 生产者 消费者问题：(producer Consumer Problem)问题：n个生产者(如计算进程)P1，P2Pn m个消费者(如打印) C1，C2Cm 通过环形有界缓冲区联系，缓冲区存放产品。(缓冲区为共享资源)。c满空P1P2(i) Pi, Ci i = 1, 2, , m, n 并行 (ii) 缓冲区多个：指针的修改属互斥操作。 avail: 可用缓冲区数(剩余)，初值i。 full 已占用缓冲区数(产品数)，初值为0。 mutex 临界区互斥信号量，初值为“ 1”。begin mutex: =1; avail: = i; full: =0 co

24、begin producteres (诸多生产者进程)，以下以一为例 repeat “ 生产下一产品” P(avail); P(mutex); “ 送入缓冲区，调查指针”cs V(mutex); 注：送取数据可放 V(full); forever consumeres (诸多消费者进程) repeat P(full); P(mutex); “ 从缓冲区中取数，调整指针”cs V(mutex); 注：送取取取数据可放 V(avail); “ 消耗产品” coend foreverend若仅一个生产者，消费者则可删去。4.5 进程间的通讯进程间的通讯一、概念一、概念1. 进程之间的信息交换称为进程

25、通讯进程之间的信息交换称为进程通讯 (各进程为各进程为了保持联系而换信息了保持联系而换信息)。目前两种基本的进程通讯方法：(1) 共享存储器 (shared memory)(2) 消息系统 (message system)2. 共享存储器方法的主要思想是：进程之间通过共享共享存储器方法的主要思想是：进程之间通过共享变量实现信息传送。变量实现信息传送。例如：信号量机构就属于这类通讯方法 前述的互斥，同步实际上均可看作是进程间通讯的一种方式，只不过交换的信息量较少，用户使用也不方便。我们称这类为低级通讯原语。(P，V操作)3. 消息系统的主要思想是：系统提供发送消息消息系统的主要思想是：系统提供发

26、送消息Send(message)与接收消息与接收消息Receive(message) 两个操两个操作，进程间则通过使用这两个操作进行通讯，无需作，进程间则通过使用这两个操作进行通讯，无需共享任何变量。共享任何变量。我们称这种由操作系统实现的通讯方法为高级通讯原语(Send, Receive)。高级通讯方法直接通讯 消息缓冲间接通讯 邮箱法所谓“ 信息”通常由消息头和消息正文构成type Msg = record msgsender 消息发送者 msgnext 下一个信息，链指针 msgsize 整个消息的字节数 msgtext 消息正文 end消息头消息正文 直接通讯 一个进程直接发送一个消息

27、给接收者进程。一个进程可发信息给多个进程，也可接收多个进程的信息(把发送给它的消息组成消息队列)。用链式队列方法表示：PCB信息信息(信息链的头指针放在每个接受消息进程的PCB 中conmunication-information项)用Msgnext将各个消息链接起来AB 间接通讯 进程不把消息直接发给接收者进程，而把消息放在某个双方共知的信箱中。邮箱法：发送邮箱接收P1P24. 通讯原语：通讯原语：Send (P1, MSG) 向进程P1发送一个信息Receive (P2, MSG) 接收来自进程P2的一个消息直接通讯Send (A, MSG), 发送一个消息到信箱AReceive (A,

28、MSG), 从信箱A接收一个消息 A P1P2 消息通信与消息队列在许多操作系统和软件开发环境 (如Windows NT)中得到广泛的应用。4.1 顺序程序和并行程序4.2 进程同步与互斥一、概念二、临界段问题1. 临界段，临界资源。2. 怎样解决互斥问题。3. 软件方法 测试与设置flay。4. 硬件技术 临界区原语操作 Lock, unlock。三、信号量 解决同步问题 (P，V操作)4.7 作业讲评及复习作业讲评及复习同步 进程有着时序上关系。互斥 排它使用的资源，是同步的一种特殊情况，一种特殊的同步。指CS上有特殊时序，每次仅有一个进程进入CS。并发执行实例 誊抄 (复写)用卡片输入机

29、，尽快地把一个文本复写到行式打印机上。 卡片输入机 行式打印机 一、一个循环顺序程序的誊抄方案一、一个循环顺序程序的誊抄方案program transcribelbegin flag: = False; while flag = false do begin input; 从读卡机输入记录 output; 输出到行打机上 endend该程序功能：每次从读卡机输入一个纪录，并把它输出到行打机上，直到布尔量flay变真为止。这一方案的特点是简单、正确，然而这一解法是低效的。假定读卡机速度为：1000卡/分钟，打印机速度为：600行/分钟，那么，最高的传输速度仅为375行/分。原因：没有充分利用读卡

30、机和行打机的并行操作能力，系统的设备利用率不高。二、两个并发程序的誊抄方案二、两个并发程序的誊抄方案 这一方案需设置一个缓冲区(假设大小为一个记录信息)，另外，将方案分成两部分：一部分负责将读卡机的信息送buffer；另一部分负责从buffer取出信息并打印，这样可使誊抄速度提高到600行/分钟，即达到最慢的那个设备的传输速率。 卡片输入机 行打机 缓冲区输入程序输出程序program transcribe2begin flagin: = false; flagout: = false; cogegin while flagin = false do begin Input; 从读卡机输入纪录

31、 send; 发送到缓冲区 end while flagout = false do begin Receive; 从缓冲区接收信息 output; 输出到行打机 end coendendP1输入程序P2输出程序注：输入程序不断地从读卡机读入信息送buffer，而输出程序不断地从buffer中取出信息送行打机。但由于两者速度不一样，若对这两个程序的执行不加任何限制，则会出现下列问题。(这两个程序是并发执行的)。(1) 若打印速度高于输入速度，导致要打印的内容还没有送入buffer，打印的并不是所需的(有可能是前次的)。(2) 反之，则打印机还未打印的内容可能被新输入的覆盖，这样，打印结果，一部

32、分正确，一部分为以后的信息，还有一些应打印的信息却丢失了。总之，在这种方案下，打印的结果是不正确的，虽然提高了设备的利用率，但不能保证正确的誊抄。这是不可取的。原因：共用一个buffer，两设备的速度不相匹配。三、三、 三个并发程序的誊抄方案三个并发程序的誊抄方案 卡片输入机 行打机 B1输入输出 B2复制f (输入序列)输入buffer输出bufferg (输出序列) 输入Input：Get (B1, f)；从输入序列 f 得到一个记录B1； 输出 output：put (B2, g)；将记录从B2放到输出序列g上。 复制 copy： B2 = B1；把记录从B1复制到B2； program

33、 transcribe3;var B1, B2: T; flag: booleanbegin if not Empty (f) then begin flag: = false; get (B1, f) repeat B2 = B1; cobegin put (B1, g); if empty (f) then flag: = true else get (B1, f ); coend until flag;end上述程序中的repeat含有三个分语句，改写为： 复制语句 copy “ B2: = B1”； 输入语句 get “ if empty (f) then flag: = true e

34、lse get (B1, f)”。 输出语句 put “ put (B2, g)”；程序改写成：repeat copy; 复制 cobegin put; 输入、输出 get; 并行运行 coend until flag;对比顺序处理时，工作模式为：G1C1G2P1C2G3P2C3P3使得输入、输出的两设备可并行工作，提高了设备利用率。若程序员把“ repeat until”重复语句写成 Get repeatbegin copy put Getenduntil三个并发进程假定运行第一次为：B1=R2, B2=R1, f=(R3, R4, Rm) g=(R1)，则运行第二次后，copy, put,

35、 get穿插执行六种方案： copy, put, get put, copy, get copy, get, put导致 G=(R1, R2) 正确复制在输入、出前完成 put, get, copy get, copy, put 导致 G=(R1, R3) 错，把R2冲了。导致 G=(R1, R1) 错，put在copy前前一个记录再度输出 get, put, copy由上可知：结果不确定，出现了三种可能的结果。 如果我们要复制一个具有1000个记录的序列，那么将会有31000个结果，即可再现现场几乎不可能，只有1/31000这个就叫做结果的不确定性(也可称为与执行时间和速度有关)，使我们难以

36、找到错误的所在。主要原因：由于并行程序的共享性和并行性。解：共享资源为S，T设4个信号量SA，SB，TA，TB分别表示：SA：buffer1中是否有信息；SB：buffer1中信息是否取走；TB：buffer2中信息是否取走；TA：buffer1中是否有信息；用信号量实现同步begin SA: = SB = TA = TB = 0; repeat cobegin P1: begin get; V(SA); P(SB); endP2: begin P(SA); copy V(SB); V(TA) P(TB) endP3: begin P(TA); put; V(TB); end coend fo

37、rever;end1. 为什么说PCB是进程存在的唯一标志？答：因为PCB包含了进程的描述信息和控制信息，是进程的动态特征的集中反映，系统在建立进程的同时就建立该进程的PCB，在撤消一个进程时也就撤消其PCB，系统根据PCB而感知某一进程的存在，所以PCB是进程存在的唯一标志。作业作业22. 下述哪些情况是对的？(1) 进程由自己创建；(2) 进程由自己阻塞；(3) 进程由自己挂起；(4) 进程由自己解除挂起；(5) 进程由自己唤醒；(6) 进程由自己撤消。答：(2)、(3) 是对的。(1) 进程由父进程建立；(4) 解除挂起又能由其它进程发生；(5) 进程只能由其它进程唤醒；(6) 进程撤消

38、一般由其父进程或祖先发出，不会自己撤消自己。3. 为什么要引入线程的概念，有什么利和弊？答：进程式的过程中免不了在运行中要提出访问管理程序的要求。例如提出I/O要求，也可能由于时钟中断而打断了当前进程的运行，而调度其他就绪进程运行，也就是经常会有进程开关的问题，另外还有两个模式开关的开销，所有这些开销的总和在一定程度上降低了并发进程带来的利益，除此之外，进程概念还有两个严重的局限性。首先许多应用想并发执行彼此之间的独立的任务，但又必须要共享一个公共的地址空间和其他资源，这些进程本质上是并行的，但传统进程概念对它们以上的要求难以支持，往往把这些应用中的独立的任务串行化，效率很低。其次传统的进程不

39、能很好地利用多处理机系统，因为一个进程在某个时刻只能使用一个处理器，一个应用固然可以创建多个进程，并把它们分别分到多个处理器上执行，但如何做到使用相同的地址空间和资源？这些都促使人们引入线程机制。4. 进程和线程的关系是什么？线程是由进程建立的，是吗？线程对实现并行性比进程机制有何好处？答：进程和线程的关系是：线程是进程内的一个相对独立的可调度的执行单元。进程在创建时，系统至少需要同时为该进程创建一个线程，即进程中至少要有一个或一个以上的线程，否则进程无法被调度执行。进程是被分给并拥有资源的基本单元，同一进程内的多个线程共享该资源，但线程并不拥有该资源只是使用它们。线程不是由进程建立的，因为需

40、要时线程可以创建其他线程。线程对实现并行性比进程机制的好处是：(1) 首先用于创建和撤消线程的开销比创建和撤消进程的系统开销(CPU时间)要少得多。(2) CPU在线程之间开关时的开销也远比进程之间开关的开销小。线程的执行效率比并发进程执行要有效得多。(3) 线程机制也增加了通讯的有效性。线程间通讯是在同一进程的地址空间内，共享主存和文件，所以非常简单，无需内核参与。(4) 方便和简化了用户的程序结构工作。5. 使用COBGIN/COEND改写下面的表达式以获得最大程度的并行性。(3AB+4) / (C+D) (EF)解：令t1 = AB, t2 = 3t1, t3 = 4+t2, t4 =

41、C+D, t5 = EF, t6 = t4t5, t7 = t3/ t6 /+4+3ABCD EFt7t6t4t5t3t2t1begin cobegin begin cobegin t4; t5 coend t6 end begin t1; t2; t3; end coend t7;endSFt1t2t3t7t4t5t66. 下面是两个并发执行的程序它们能正确执行吗？若不能正确执行请举例说明并改正之(X是公共变量)cobeginvar x: integer;procecc p1 (进程p1)var y, z: integer;beginx: =1;y: =0;if x=1 then y:=y+

42、1z:=yendprocecc p2var t, u: integer;beginx:=0;t:=0;if x=1 then y:=y+1z:=ysignal (mutex);endprocecc p2var t, u: integer;beginwait (mutex);x:=0;t:=0;if x1 then t:=t+zu:=t;signal (mutex);endcoend7. 设有n个进程共享一互斥段对如下两种情况1) 每次只允许一个进程进入互斥段；2) 最多允许M个进程(MN)同时进入互斥段；所采用信号量是否相同？信号量值的变化范围如何？答：所采用的信号量相同，为mutex。第一种情况mutex初值为1，变化范围为0mutex1的整数，第二种情况mutex初值为M，变化范