搜索
并行程序设计语言第13，14章•多CPU•网络ConcurrentDeclarativeImperativeConcurrentDeterministic更关注如何描述问题本身更关注描述冯诺依曼机如何执行冯诺依曼单机网络环境小规模软件大规模软件不同的软件开发方法主要内容：•并发程序设计的基本概念•并发程序带来的问题•需要解决的基本问题•程序语言示例并行与并发并发（concurrency）和并行（parallelism）的概念•并发性指一大类程序的一组特性，在这类程序里，两个或更多的执行上下文同时处于活动状态。并行指并发程序里的一种特性，在其中的多个上下文里正在同时实际处于执行中•真正的并行性需要并行硬件。从语义观点看，在并行与强占式并发系统里（系统会在不可预期的时刻在不同执行环境之间切换）的“准并行”之间没有根本区别，两种情况需要同样的程序设计技术另一种理解：•并行强调的是多个执行活动同时处于运行状态之中，强调其相互独立性。这里关心并行算法、并行系统、并行体系结构等等•并发强调的是多个执行活动之间的关系和相互作用，这里关心的是互斥、同步、通讯、资源的共享和竞争等等基本概念•并行程序设计语言•并行程序设计模型•并行计算的硬件环境•程序与进程，线程与进程•原子动作•进程交互基本概念•并行程序设计语言要具有描述程序并行性的能力。针对并行系统,一般而言,程序并行性分为控制并行性和数据并行性。•控制并行性是指两个不同操作可同时进行,数据并行性是指对不同的数据同时执行同一操作。基本概念•并行程序的基本计算单位是进程,它与有关代码段执行的操作相对应。进程的粒度在不同的程序设计模型和应用程序中是不一样的。基本概念•并行程序设计的模型：–1.共享变量模型–2.消息传递模型–3.数据并行模型–4.面向对象模型是目前最灵活，最常用的模型新的并行模型基本概念•1.共享变量模型共享变量模型用限定作用范围和访问权限的办法,对进程寻址空间实行共享或限制,即利用共享变量实现并行进程间的通信。为了保证能有序地进行IPC(Inter-ProcessCommunication),可利用互斥特性保证数据一致性与同步。基本概念•共享变量模型与传统的顺序程序设计有许多相似之处。程序员只需关心程序中的可并行进程,而无需关心进程间的数据交换问题。共享变量的数据一致性、临界区的保护性访问由编译器与并行系统来维护。•共享变量模型具有编程简单、易于控制的特点,但若在多处理机、机群系统上实现时则会导致系统开销增大,因此共享变量模型常常用于共享存储多处理机,而不用于多处理机、机群系统。基本概念•2.消息传递模型消息传递模型是指程序中不同进程之间通过显式方法(如函数调用、运算符等)传递消息来相互通信,实现进程之间的数据交换、同步控制等。消息包括指令、数据、同步信号等。基本概念•程序员不仅要关心程序中可并行成分的划分,而且还需关心进程间的数据交换。消息的发送、接收处理将增加并行程序开发的复杂度。但是它适用于多种并行系统,如多处理机、可扩展机群系统等,且具有灵活、高效的特点。基本概念•3.数据并行模型数据并行模型是指将数据分布于不同的处理单元,这些处理单元对分布数据执行相同的操作。数据并行程序使用预先分布好的数据集。运算操作之间进行数据交换操作。基本概念•数据并行操作的同步是在编译而不是在运行时完成的。数据并行模型中的SIMD模型可用于向量机、多处理机等并行计算机,而SPMD模型则可用于多处理机、机群系统,但相对而言它缺乏灵活性。基本概念•4.面向对象模型面向对象模型是近几年随着面向对象技术的发展而提出的。它基于消息传递,但并行处理单位却是对象。在这种模型中,对象是动态建立和控制的。处理是通过对象间发送和接收消息来完成。面向对象模型具有简洁灵活的特点,适合多种平台,但系统开销较大。基本概念•并行程序设计语言就是在这些并行程序设计模型的基础上,提出对并行性的描述方法、并行单元间协同的描述方法,以及该语言适用的并行计算环境。基本概念•无论是哪种模型，那个语言，都需要解决两个问题：进程管理和通讯。•事实上，模型之间的区别主要体现在对通讯实现方式的不一样上。•硬件环境–单机/多机：并行/并发–根据Flynn的分类法:•SISD：一组可执行代码装入一个机器内存后,以一个CPU,一组数据执行一次。它属于SISD执行模式(即单指令流单数据流的简写)。物理上对应为单处理器的顺序程序。•SIMD：一组可执行代码装入后,可以依次执行多个进程,它属于SIMD,单指令流多数据流。对应为单机多处理器的主机或单CPU的分时系统、阵列机组。•MISD：在多机或多处理器上各有自己的可执行代码。协同完成一组数据的计算,是MISD多指令流单数据流系统。对应为分布数据流机。•MIMD：MIMD则为多指令流多数据流系统,对应为一般分布式系统(有多个不同的处理机,运行各不相同的进程)。局域网和广域网就属于此列。如果网上协同运行一个程序作业,则为以MIMD系统实现的并发程序。基本概念并行处理器谱系并行处理器SIMDMIMD共享存储（紧耦合）分布式存储（松耦合）•共享存储多用于同类多CPU的单机上，所有CPU处理的进程都共享公共的数据.•分布式存储是松耦合的计算机群体,它对应为多计算机的簇（cluster）,和一组计算机的集合不同之处在于：它们各自的存储是被大家共享的,它们互连,每个计算机只是”整个”计算机中的一个节点,是今后高性能、可伸缩、高可靠性计算机的发展方向.基本概念•并行程序设计语言都要解决：–并行进程的描述与管理–进程间数据分布、传递的描述与管理–以及进程间同步协同的描述与管理问题。基本概念•一个程序的一次执行叫做一个进程(process)基本概念进程执行控制流外部中断内部中断中断处理器原语例程调度器基本概念线程是共享资源的轻量级进程（lightweightprocess）,它也有线程执行状态，也有其静态存储和局部变量。基本概念•传统的OS支持单线程的计算模式。单用户的MS-DOS和多用户的UNIX就是例子，即使UNIX是多线程交互，每一进程之中只有一线程。MS-DOSJavaUNIXWindowsNTSolarisMachOS/2右侧上图，一个进程多个线程对应为Java虚机的计算模式。而当今所有OS均发展为右下角的多进程和多线程的计算模式。基本概念原子动作是一次“立即”执行完的“顺序”动作。至于是否真正不再分就不一定了。原子动作一般定义在语句级的事件(event)上事件是本程序表示的状态有了变化例：PL/1的多任务PL/1的并发进程是任务TASK,它可以定义语句级的事件。P是一个进程,它并行执行Q进程,则P进程的正文可以写:DECLAREXEVENT:CALLQ(APT)TASK(X)//激活Q进程交互(1)独立进程两进程并行但不相关设进程为事件序列,若有C,K两并行进程,可表达为C‖K.其中:C={C1,C2…Cn}K={K1,K2,…Km}独立进程是两进程内任何事件Ci,Kj的执行都不依赖对方(2)竞争进程两进程竞争同一资源临界段(Criticalsection)：据有并加工资源的代码段竞争进程一般形式是:C:loopK:loop入口协议入口协议临界段临界段出口协议出口协议非临界段非临界段endloopendloop入口协议一般是按所设共享变量判断能否进入,出口协议则改置正确值.为确保进程的确定性,利用共享变量“通信”协调(3)通信进程两进程有协议的信息交换设C,K定义如前,Ci必须先于Kj(Kj要用到Ci的结果)的执行,即其它事件先后无所谓,一定要保证Ci,Kj的执行顺序.•同步(synchronous)通信指两进程进度各不相同,但必须同步到达通信点.若一方未到,另一方等待,直至完成信息交换.交换后各自执行各自进程则为单向同步通信.如果交换后,发送方一直等待接受方执行的结果,拿回结果后再各自执行自己的进程为双向同步通信。•异步(asynchronous)通信一般要借助相当大的邮箱.两进程以各自速度执行,发送方有了信息投入邮箱,并继续执行自己进程.接受方在认为合适时从邮箱获取信息.一般不竞争邮箱且为单向通信,当然也可做成双向的。•定向/广播式通信所谓定向是发送方指明接受方.而广播式通信发送方只向公共信道发送信息,任何共享该信道的成员均可接受,所以是异步通信、单向的.主要内容•并发程序设计的基本概念•并发程序带来的问题•需要解决的基本问题•程序语言示例带来的问题(1)速度依赖(2)输入值依赖(3)不确定性(4)死锁(5)死等带来的问题(1)速度依赖并发程序执行结果,取决于顺序成分进程执行的相对速度.对于并发且有实时(realtime)要求的程序,执行结果还取决于绝对速度.并发程序调整相对速度的办法是延迟快进程.把进程挂起来(进入悬置态)待到指定条件满足才唤醒该进程.其基本原语是:await表达式do语句｜进程带来的问题(2)输入值依赖同一并发程序两组数据输入可能会有很大差别带来的问题(3)不确定性顺序程序两次同样值的测试,一般情况下都是一致的.即所说的再现.并发程序因上述原因往往没有确定的结果值.对于有副作用的函数或表达式这种先后次序的差异影响则更大带来的问题(4)死锁（deadlock）是一种状态,由于进程对资源有互不相兼容的要求而使进程无法进展.表现为:受到排斥进程永远访问不到所需资源循环等待进程资源分配链形成一封闭回路无占先(nopreemption)进程无法放弃所占的、其它进程需要的资源.所谓占先,只要所据资源的进程未处于使用状态,另一优先级高的进程有了要求,则此资源被后者占去把持(waitandhold)相互以占有对方资源为放弃已占资源的先决条件带来的问题•解决死锁的方法:–利用工具作静态死锁检测,可以避免或减少死锁出现的可能–或事前,让进程同时提出所有需要的资源,消除把持条件,或强行给资源排序,按此顺序满足要求,消除循环等待条件–或事前,为调度程序声明最大的资源需求–一旦出现,最笨的办法是重新启动,试换数据,找出原因改正之。事后重试解决–一旦出现,找出死锁地点,夭折某些事件或进程或设置检测点带来的问题(5)死等（starvation）相互竞争的进程如果都满足进入某一资源条件,一般采用排队的先来先服务原则。相对最公平,但有的进程占用一种资源时间过长,致使其它资源长期闲置。适当地让它等待可以解放很多占时少而重要的进程,这样更公平。于是,除了先来先服务而外,在调度例程中约定或在条件中加入优先级表来达到此目的。调度程序则按此优先级和先来后到统一调度。如果优先级不当就会造成某些进程永远处于阻塞态,死等(但不是死锁)。死等是不公平调度引起的。解决的办法是在改变某些进程的优先级,在公平性和合理性上作某种折衷主要内容：•并发程序设计的基本概念•并发程序带来的问题•需要解决的基本问题•程序语言示例并行语言需要解决的基本问题•安全性(safety)是程序在执行期间不会出现异常的结果.对于顺序程序指其最终状态是正确的.对于并发程序指保证共享变量的互斥访问和无死锁出现•活性(liveness)是程序能按预期完成它的工作.对于顺序程序指程序能正常终止.对于并发程序指每个进程能得到它所要求的服务;或进程总能进入临界段;或送出的消息总能到达目的进程,活性深深受到执行机构调度策略的影响•公平性(fairness)指在有限进展的假设下没有一个进程处于死等状态.–无条件公平性:调度策略如能保证每个无条件的原子功能均能执行–弱公平性:在具有条件原子动作时,若条件原子动作能执行并依然保持无条件公平性,则为弱公平性–强公平性:条件原子动作一定能执行,则为强公平性并行语言需要解决的基本问题•进程管理：创建；起动（或恢复）执行；阻塞(或叫冻结)；停止执行；阻塞父进程创建子进程；撤销进程等六种操作。•通讯机制（信息交流和同步）：基于共享变量的；基于消息传递的难点一、忙等待(busywait)设我们把指示变量叫做lock(锁),每次测试临界段是否锁定。竞争进程以测定进入条件(锁)保持协调地进入临界段,我们说它在语义上保证了条件同步