《程序设计语言原理》由会员分享，可在线阅读，更多相关《程序设计语言原理（34页珍藏版）》请在金锄头文库上搜索。
1、程序设计语言原理Hubei University of Technology Hubei University of Technology School of Computer Science & EngineeringSchool of Computer Science & Engineering2006.22006.2主讲：熊才权湖北工业大学计算机学院湖北工业大学计算机学院7/24/20241返回返回返回返回第7章并发措施ADA语言中的任务第7章并发和任务并发概述7/24/20242返回返回返回返回7.1并发概念的重要性一、并行处理的重要性1、提高计算机的性能和计算机资源的有效利用。最早的
2、并行操作是计算机的CPU和外部设备能在同一时间工作，彼此能协调地完成各自的任务。接着的并行操作是多道程序设计。对CPU的时间进行分时，所执行的作业在宏观看是并行的，以微观上看是串行的。第7章7/24/20243返回返回返回返回2、从计算机系统结构的发展上看，宏观上并行处理成为可能：如多处理机系统、高速并行计算机系统（如陈列计算机、向量机、流水线部件等）、分布式系统。 要想充分利用这些硬件资源，需要执行能并行处理的程序。第7章7/24/20244返回返回返回返回3、潜在并行性的发现和表达的需要（从软件考虑）第7章分析并行性事实将其抽象为模型用并行算法表示模型用程序设计语言表示并行性（如果语言没有
3、并行机制，只能丢弃并行性）执行并行处理程序程序设计语言中并行性研究的问题：（1）算法中的并行性的发现和描述；（2）串行程序执行中存在的潜在并行性的源程序的转换；（3）潜在并行性成为现实并行性；（4）并发成分的研究和应用；（5）程序设计语言中潜在并行性的发现和实现技术的改进。7/24/20245例1:(潜在的并行问题采用串行控制）procedureREFLECTisCH1，CH2：character；beginloopifREADY(1)thanbeginREAD(1，CHl)；WRITE(1，CH2);endendififREADY(2)thenbeginREAD(1，CHl)；WRITE(1
4、，CH2);endendifendloopendREFLECT其中，READY(N)：布尔函数，测试在终端N上是否已压下一个键，READY(N)的值为true表示有一个键压下。例2(一个任务独立服务于一个终端，任务之间无关，并行执行，任务之间无通信和同步的要求)Taskterminall；taskbodyterminallisCH：character；beginloopREAD(1，CH)；WRITE(1，CH)jendloop；endterminall；Taskterminal2；Taskbodyterminal2isCH：characterbeginloopREAD(2，CH)；WRITE
5、(2，CH)jendloop；endterminall；第7章两个极端的例子：7/24/20246返回返回返回返回二、并行处理1、理解并行性的定义：（1）同时性：两个或多个事件在多个资源上同时进行。（2）并发性：两个或多个事件在同一资源上交替进行（微观上是串行的）（3）流水线：两个或多个事件发生在可能重叠的时间段内。第7章7/24/20247返回返回返回返回2、并行处理的颗粒度：并行事件大小的划分。粒度越小，并发度越大，但控制复杂；粒度越大，并发度越小，担控制简单。并发单位：进程、线程、任务3、并行处理中各事件之间的相关性：通信、共享、同步、互斥4、并行执行的流程控制方法。由系统实现；（比较困
6、难，但这应当是目标）由用户调度实现；（不合理，也不现实）由用户辅助让系统根据用户提供的信息来实现。第7章7/24/20248返回返回返回返回5、几个基本概念：（1）进程：把一个可以并行执行的顺序程序的动作序列称为进程。（2）进程通讯：指两个进程之间传递数据。（3）临界区：引用共享变量的语句段。（4）同步：控制进程执行顺序的一种机制（有共享数据或数据通讯要求）（5）互斥：同一时间只有一个进程进入临界区，其它要访问临界区的进程只能等待。第7章7/24/20249返回返回返回返回三、高级语言并发机制要解决的问题（1）并发执行代码段的描述方法进程、线程、任务（2）启动和初始化代码段的方法（3）共享数据
7、的表示，互斥使用共享数据的方法信号量、管程、临界区、保护类型、消息传递，入口项，入口调用（4）调度并发代码段的执行方法：如延迟、优先数、重排队列第7章描述一个并发系统最本质的内容：。组成并发系统的实体及其属性和行为；。实体间的通信；。实体间的交互作用（竞争与合作）7/24/202410返回返回返回返回7.2 高级语言中的并发措施、信号量和PV操作：1、基本概念：PV操作的对象是一个确定的二元组(s,q)。（1）信号量s（semaphores)：是一个二值变量（0，1）（被两个进程共享）以及扩充的二值变量（零，非零）（被多个进程共享）。由Dijkstra于1965年提出。 （2）进程序列q:等待
8、执行的进程序列，实现为队列(queue)。进程状态（正在执行，等待执行，阻塞在与某个信号量关联的队列中）。第7章介绍三种方法：一、信号量和PV操作二、管程三、消息传递7/24/202411返回返回返回返回2、对信号量施行的操作：Wait(s): P操作第7章wait(s):= if S=1 then S:=0 else 将进程P放入对列等待signd(s):= if queue不为empty then 从queue中取出一个进程安排它执行 else S=1;Signd(s): V操作7/24/202412返回返回返回返回扩充的二值变量：对被多进程共享的PV操作：Wait(s): P操作第7章w
9、ait(s):= S:=S-1; if S0 then 将当前进程挂起并放到队列中 else 当前进程继续执行signd(s):= S:=S+1; if S=0 then 从队列中取出一个进程，使之继续执行Signd(s): V操作7/24/202413返回返回返回返回例：(本例能否正常进行与信号量的初值有关，如果mutex初值为0则会出现错误）第7章Procedure WRITERBegin . waite(mutex) write the database/临界区 signal(mutex) . endPrcedure READER Begin wait(mutex) read the d
10、atabase/临界区 sigal(mutex) . end7/24/202414返回返回返回返回设初值:mutex=1第7章时间段READERWRITER1wait(mutex)s=02READER占有资源wait(mutex)3signal(mutex)WRITER进入队列4WRITER占有资源5signal(mutex)s=1时间段READERWRITER1wait(mutex)s=02READER占有资源3signal(mutex)s=14wait(mutex)s=05WRITER占有资源6signal(mutex)s=1第一种情况第二种情况（没有等待）7/24/202415返回返回返
11、回返回生产者消费者：（增加一个信号量，并设正确的初值可以保证生产者消费者交替进行） OK:=0; fin:=1;第7章procedure PRODUCERbeginwhile 还有数据输入 do wait (fin) 将数据存入缓冲区中 signal (ok)end-whileend;procedure CONSUMERbeginloop waite(ok) 从缓冲区取出数据 signal(fin)end loopend;7/24/202416返回返回返回返回二、管程：1、信号量的不足：（1）信号量过于简单，只适用于从不犯错的理想情况，不正确地使用信号量的后果是不堪设想的。 A、如果颠倒了wa
12、it和signal语句的顺序，就可能有多个进程进入临界区中。 B、如果错误地把该用signal的地方误用了wait，就可能发生死锁。 第7章一个出现死锁的例子：processPROCESS_1;beginwait(s1);wait(s2);endPROCESS_1;processPROCESS_2;beginwait(s2);wait(s1);.endPROCESS_2;7/24/202417返回返回返回返回（2）编译程序无法知道信号量的初始值是否正确，也无法判断共享变量是否在临界区外被访问。（3）使用信号量时，每每个个进进程程都都有有一一段段临临界界区区代代码码，这个 临 时 区 代 码 分
13、 散 在 不 同 的 进 程 中 ， 用 wait(s)和signal(s)括起来，程序员要掌握这些代码的出现和作用，不适应结构化程序设计。第7章7/24/202418返回返回返回返回2、管程的概念：modulamodula语言和语言和并发并发Pascal(concurrent pascal)Pascal(concurrent pascal)中用。 管程是把所有与共享数据访问有关的同步控机制和同步处理代码收集到一个模块中，并独立于各进程。（1）互斥性：任何时刻只能有一个进程访问管理中的一个过程。（2）封装性：一个管程内的过程只能访问局部于该管程的变量和过程，同时管程中的局部数据不能在管程之外访
14、问。（3）同步性：一个进程一旦允许访问一个管程，管程的共享资源归它所有。第7章7/24/202419返回返回返回返回3、管程的定义（说明）：如同抽象数据类型第7章monitor(名字)begin局部于管程的数据说明过程说明局部数据的初始化end（名字）4、调用：管程名过程名（实参数）在一个时刻只允许一个进程调用管程内的过程。并且在管程内一个过程的执行未结束之前，该管程内其他过程不得执行。管程内的过程只能存取管程内的局部数据对象、子程序以及外部进程调用它时所给予的实在参数。7/24/202420返回返回返回返回5、Concurrent Pascal的并行机制： 在Pascal基础上扩充而成（）定
15、义进程：例举进程：启动进程：用于为进程的局部数据对象分配空间并使该进程启动。第7章type= process()数据说明过程体endVar:进程类型名init 进程名（实参部分）7/24/202421返回返回返回返回（2）定义管程第7章type= monitor （形式参数部分） 共享变量说明 局部子程序说明 带入口子程序说明 begin 初始化语句序列end7/24/202422返回返回返回返回带入口子程序说明： 带入口的子程序可以被进程调用，不带入口的子程序是局部子程序，它只能在管程内使用。 例举管程：启动管程： 第7章procedure entry 过程名（形参部分）init 管程名字V
16、ar 管程标识符表：管程类型名7/24/202423返回返回返回返回第7章MODULA的管程（界面模块）：用于描述生产者消费者：7/24/202424返回返回返回返回type PRODUCER= /进程类型 process var IN:INTEGER; begin while not EOF do begin READ(IN); SPOOL(IN); end end; CONSUMER= /进程类型 process var OUT:INTEGER; begin repeat UNPOOL(OUT); /SPOOL与UNPOOL互斥执行 WRITE(OUT); until OUT=”-3276
17、8” end; BUFFERMONITOR= /管程类型 Monitor var BUFFER=array(1.100)of INTEGER; FRONT, REAR ,NUMBER: INTEGER;第7章procedure entry SPOOL(ITEM:INTEGER); begin if NUMBER=100 then delay; BUFFER(REAR):=ITEM; REAR:=REAR mod 100+1; NUMBER:=NUMBER+1; continue end;procedure entry UNPOOL (var ITEM:INTEGER); begin if NU
18、MBER=0 then delay; ITEM:=BUFFER(FRONT); FRONT:=FRONT mod100+1; NUMBER:=NUMBER-1; continue end;/蓝色部分是管程begin FRONT:=1; REAR:=1; NUMBER:=0;end;Var PROD: PRODUCER; CONS:CONSUMER; BUFFERMO: BUFFERMONITIOR;begin Init PROD,CONS,BUFFERMO /进程同时启动end;例：生产者消费者：7/24/202425返回返回返回返回三、消息传递机制1、管程的不足： 管程一般适合于运行环境为单
19、多理机或虽然为多处理机但共享同一公共内存的处理机的语言的并发控制机制。2、消息传递：两个进程间直接相互传递消息，实现通信、同步和互斥，适于分布式多处理机系统。第7章7/24/202426返回返回返回返回一般化：（1）发送语句：send(PROC, EXPR)把EXPR的值传送给进程PROC（2）接收语句receive (PROC ,ARGUMENT)从进程PROC接收一个值，并把它赋给ARGUMENT.第7章7/24/202427返回返回返回返回管程与消息传递对比：第7章7/24/202428返回返回返回返回3、CSP：Communicating Sequential Process通信顺序进
20、程 由C、A Hoare提出。 命令： Q！flay: perform所在进程向Q发生输出命令，输出值flag P?newflag:perform所在进程向P发出输入命令，接收值放入newflay. Perform为数据类型第7章7/24/202429返回返回返回返回特点：1、两个进程要相互了解。2、一个进程发出输出命令必须等到对方进程发出接收命令后才能并行进行；同样地一个进程发出输入命令后必须等到对方发出输出命令后才能并行执行。第7章7/24/202430返回返回返回返回4DP:Distribute Process 分布式进程语言进程间的通信采用远程过程调用。 在发送进程P中作用命令： Ca
21、ll Q.R(input # output)R是Q中的过程。所在进程调用Q进程，Q进程中的R过程被执行，input是P给出的输入消息，output是返回给P的输出消息。第7章7/24/202431返回返回返回返回特点：（1）发出命令的进程必须了解被调进程，但被调进程不一定了解发出命令的进程。（2）发出命令的进程要等到接收进程接到消息并执行完R后，两个进程才并行执行。Ada语言的会合rendezvous就是这种机制。第7章7/24/202432返回返回返回返回CSP与DP不同点：当调用进程执行达到输出（调用）命令并成功地传送（相当于调用成功）后，在CSP中两个进程将并行继续执行下去，而在DP中调用进程必须等待，直到被调用的程序（包含在被调进程中）执行完毕，两进程才并行继续执行下去。第7章7/24/202433返回返回返回返回作业：设有两个进程，它们都要访问某个公共变量X，一个进程给X赋值，一个进程引用X，规定任一时刻只能有一个进程访问X，对X只能先赋值后引用，赋值和引用交错进行。如果要达到上述要求，需要几个信号量？它们各有什么用途？试用信号量和Ada的任务机制分别编写满足上述要求的程序段。第7章7/24/202434
