研究生课程_程序语言设计原理教程_第13章.ppt
《研究生课程_程序语言设计原理教程_第13章.ppt》由会员分享,可在线阅读,更多相关《研究生课程_程序语言设计原理教程_第13章.ppt(27页珍藏版)》请在三一文库上搜索。
1、第13章 程序的并发性和进程交互原语,13.1 基本概念 程序与进程 一个程序的一次执行叫做一个进程(process) 就绪ready 可执行代码装入内存立即可运行 运行running 执行进程 阻塞blocked 停止本进程执行, 随时可恢复执行 终止terminated 停止, 且不可恢复执行 激活:创建一个进程并使之进入就绪或立即运行状态 触发:使就绪或阻塞状态转入运行态 中断:使运行的进程转入阻塞或终止态 原语:程序语言中定义的例程名 线程:创建子进程不另分配资源 子进程:一个进程执行中再次创建的进程,线程与进程计算模式及分类 线程是共享资源的轻量级进程(lightweight pro
2、cess),它也有线程执行状态,也有其静态存储和局部变量。,MS-DOS,Java,UNIX,Windows NT Solaris Mach OS/2,原子动作,原子动作是一次“立即”执行完的“顺序”动作。至于是否真正不再分就不一定了。原子动作一般定义在语句级的事件(event)上 事件是本程序表示的状态有了变化 例: PL/1的多任务 PL/1的并发进程是任务TASK, 它可以定义语句级的事件。 P是一个进程, 它并行执行Q进程, 则P进程的正文可以写: DECLARE X EVENT : CALL Q(APT) TASK (X) /激活Q,进程交互 (1) 独立进程 两进程并行但不相关 设
3、进程为事件序列, 若有C,K两并行进程, 可表达为CK.其中: C=C1, C2Cn K=K1,K2,Km 独立进程是两进程内任何事件Ci, Kj的执行都不依赖对方 (2) 竞争进程 两进程竞争同一资源 临界段(Critical section):据有并加工资源的代码段 竞争进程一般形式是: C : loop K : loop 入口协议 入口协议 临界段 临界段 出口协议 出口协议 非临界段 非临界段 end loop end loop 入口协议一般是按所设共享变量判断能否进入,出口协议则改置 正确值.为确保进程的确定性,利用共享变量“通信”协调,(3) 通信进程 两进程有协议的信息交换 设C
4、,K定义如前, Ci必须先于Kj(Kj要用到Ci的结果)的执行, 即其它事件先后无所谓, 一定要保证Ci, Kj的执行顺序. 同步(synchronous)通信 指两进程进度各不相同, 但必须同步到达通信点.若一方未到,另一方等待,直至完成信息交换.交换后各自执行各自进程则为单向同步通信.如果交换后,发送方一直等待接受方执行的结果,拿回结果后再各自执行自己的进程为双向同步通信。 异步(asynchronous)通信 一般要借助相当大的邮箱.两进程以各自速度执行,发送方有了信息投入邮箱,并继续执行自己进程.接受方在认为合适时从邮箱获取信息.一般不竞争邮箱且为单向通信, 当然也可做成双向的。 定向
5、/广播式通信 所谓定向是发送方指明接受方.而广播式通信发送方只向公共信道发送信息,任何共享该信道的成员均可接受, 所以是异步通信、单向的.,13.2 并发程序带来的问题 (1) 速度依赖 并发程序执行结果,取决于顺序成分进程执行的相对速度.对于并发且有实时(real time)要求的程序,执行结果还取决于绝对速度. 并发程序调整相对速度的办法是延迟快进程.把进程挂起来(进入悬置态)待到指定条件满足才唤醒该进程.其基本原语是: await do (2) 输入值依赖 同一并发程序两组数据输入可能会有很大差别 (3) 不确定性 顺序程序两次同样值的测试,一般情况下都是一致的.即所说的再现.并发程序因
6、上述原因往往没有确定的结果值.对于有副作用的函数或表达式这种先后次序的差异影响则更大,(4) 死锁(deadlock)是一种状态,由于进程对资源有互不相兼容的要求而使进程无法进展.表现为: 受到排斥 进程永远访问不到所需资源 循环等待 进程资源分配链形成一封闭回路 无占先(no preemption) 进程无法放弃所占的、其它进程需要的资源.所谓占先,只要所据资源的进程未处于使用状态,另一优先级高的进程有了要求,则此资源被后者占去 把持(wait and hold) 相互以占有对方资源为放弃已占资源的先决条件 解决死锁的方法: 利用工具作静态死锁检测,可以避免或减少死锁出现的可能 或事前,让进
7、程同时提出所有需要的资源, 消除把持条件, 或强行给资源排序, 按此顺序满足要求, 消除循环等待条件 或事前,为调度程序声明最大的资源需求 一旦出现, 最笨的 办法是重新启动, 试换数据, 找出原因改正之。事后重试解决 一旦出现, 找出死锁地点, 夭折某些事件或进程或设置检测点,(5) 死等(starvation) 相互竞争的进程如果都满足进入某一资源条件, 一般采用排队的先来先服务原则。相对最公平, 但有的进程占用一种资源时间过长, 致使其它资源长期闲置。 适当地让它等待可以解放很多占时少而重要的进程, 这样更公平。于是, 除了先来先服务而外, 在调度例程中约定或在条件中加入优先级表来达到此
8、目的。调度程序则按此优先级和先来后到统一调度。如果优先级不当就会造成某些进程永远处于阻塞态, 死等(但不是死锁)。死等是不公平调度引起的。解决的办法是在改变某些进程的优先级, 在公平性和合理性上作某种折衷,13.3 并发程序的性质 安全性(safety)是程序在执行期间不会出现异常的结果.对于顺序程序指其最终状态是正确的.对于并发程序指保证共享变量的互斥访问和无死锁出现 活性(liveness)是程序能按预期完成它的工作.对于顺序程序指程序能正常终止.对于并发程序指每个进程能得到它所要求的服务; 或进程总能进入临界段; 或送出的消息总能到达目的进程, 活性深深受到执行机构调度策略的影响 公平性
9、(fairness)指在有限进展的假设下没有一个进程处于死等状态. 无条件公平性:调度策略如能保证每个无条件的原子功能均能执行 弱公平性:在具有条件原子动作时, 若条件原子动作能执行并依然 保持无条件公平性, 则为弱公平性 强公平性:条件原子动作一定能执行, 则为强公平性,13.4 低级并发机制和并发原语 无论程序设计语言上层采取何种机制实现程序的并发, 最底层不外乎创建进程(装入内存、初始化使之就绪);起动(或恢复)执行;阻塞(或叫冻结);停止执行;阻塞父进程创建子进程;撤销进程等六种操作。这六种操作更低层的实现是机器指令 原语(premitive)是包含这些底层指令的例程。由于支持上层不同
10、的并发机制,原语为了表述方便不同语言原语的差别在于所选组合指令的不同,fork/multifork 分股创建多个子进程并执行 quit/join 合股新创进程回到原进程 wait(e) 等待e为真执行本进程 signal(e) 示信e为真可切换至下一进程 sleep (value) 若value表达式满足,使所在进程阻塞 wakeup(value) 若value表达式满足,使所在进程唤醒(恢复执行) cobegin s1s2sn coend 开始多个进程s1sn并发执行 coroutine N 指定协例程N resumeM 转入协例程M send(Exp) to 将表达式值送至进程 recei
11、ved(V) from 接受来自进程的消息, 值由变量V传入,例如:,基于共享变量的同步机制 (1) 忙等待(busy wait) 设我们把指示变量叫做lock(锁),每次测试临界段是否锁定。竞争进程以测定进入条件(锁)保持协调地进入临界段, 我们说它在语义上保证了条件同步。 锁就是条件, 协调就是同步 请注意, 此时未设同步原语。 程度员也无法阻塞停止某个进程。如果有多个进程竞争进入临界段, 则每个进程都要轮流测试锁。这就是著名的自旋锁 (spin lock), 其算法如下:,program SPINLOCK: var Lock := false; process P1: loop when
12、 not lock do 条件同步 lock := true; 入口协议 临界段; lock := false; 出口协议 P1的非临界段; end do; end loop; end p1; process pn : end SPINLOCK,process P2: loop when not lock do lock := true; 临界段; look := false; P2的非临界段; end do; end loop; end P2;,上述算法如果在多处理器的条件下, 进程严格同时到达, 对资源的竞争变成对指示变量查询和更改的竞争,要取决于操作系统对公用主存储器的存取访问的排序。如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 研究生课程 程序语言 设计 原理 教程 13
链接地址:https://www.31doc.com/p-5029906.html