课件分布式系统dos ch3proc

第3章分布式进程管理东北大学信息学院张天成谷峪2014年9月2主要内容3.1进程和线程管理3.2虚拟化技术3.3客户进程的设计3.4服务器进程的设计3.5代码迁移3.6*软件代理3.7*分布式处理机管理3.8*实时分布式系统33.1进程和线程管理进程：运行中的程序例：4个程序组成的多道程序逻辑上，4个独立的、顺序的进程的概念模型物理上，任意时刻只有一个是活动的4进程的状态举例：1–

进程a等待输入而暂停执行，进入阻塞队列2–

时间片到，进程a暂停执行，进入就绪队列，调度器选择另一个就绪进程b3–启动进程b运行4–当输入完成后,进程a进入就绪队列

5操作系统的进程结构调度器：处理中断(分时,IO)进行调度6进程的实现—进程表(PCB)进程管理内存管理文件管理RegistersProgramcounterProgramstatuswordStackpointerProcessstatePrioritySchedulingparametersPointertotextsegmentPointertodatasegmentPointertostacksegmentRootdirectoryWorkingdirectoryFiledescriptorsUserIDGroupIDProcessIDParentprocessProcessgroupSignalsStartingtimeCPUtimeusedChildren’sCPUtimeTimeofnextalarm7中断处理和调度将当前程序指针压栈（硬件）从中断向量取出新的程序指针（硬件）保存当前寄存器（汇编，中断处理）设置新的栈指针（汇编，中断处理）执行中断服务程序（C语言，中断处理）调度器决定下一个运行的进程（C语言，调度器）加载寄存器和内存映像（汇编，调度器）启动新的进程（汇编，调度器）8线程的概念进程：相关的运行资源的管理单位内存空间打开的文件子进程、信号处理、记账信息等资源分组线程(线索)：在CPU上执行的脉络程序计数器、寄存器、栈执行9线程模型多线程进程：一个线程被阻塞时，可运行同一进程中的另一线程（阻塞就绪运行）线程进程；进程处理机；10线程模型每个线程可共享所属进程的资源每个进程的项目每个线程的项目地址空间全局变量打开的文件子进程挂起警报信号和信号处理器计费信息程序计数器堆栈寄存器状态11线程模型每个线程拥有自己的栈局部变量、返回地址12大型应用程序需要进程间通信进程间通信IPC中的上下文切换缺点：切换开销大解决方案：线程切换线程的用途-进程间通信（IPC）S2:从进程A到进程B

切换上下文S1:从用户空间到内核空间切换上下文S3:从内核空间到用户空间切换上下文13线程的用途-多线程客户程序举例：包含3个线程的字处理器录入存储编辑14线程的用途--多线程服务器举例:多线程的Web服务器15多线程服务器的组织方式（a）分派者/工作者模型（b）团队模型（c）管道模型16多线程示例代码(a):分派者线程（dispatcher）源代码

(b):工作者线程（worker）源代码17服务器组织的比较模式并行

非阻塞式系统调用性能

编程容易程度单线程进程低√多线程进程√高√有限状态机√√高18多线程的实现方式（1）用户空间切换效率高专门的调度算法优点性能高灵活19多线程的实现方式（2）内核空间：由内核管理优点实现简单20多线程的实现方式（3）混合方式-轻量级进程（LWP）将用户级线程多路转接到内核LWP上LWP执行线程调度算法21多线程的实现方式（4）调度器激活方法目标：既有用户进程的优点(高性能、灵活),又有内核进程的优点（实现简单）。方案：避免不必要的“用户/内核”间的切换实现：Upcall机制：下层内核可调用上层用户运行系统22Unix中的线程API调用23Windows中的进程管理基本概念名称描述作业（Job）一组共享定额和限制的进程进程（Process）拥有资源的容器线程（Thread）被内核的调度实体纤程（Fiber）完全在用户空间管理的轻量线程24Job、Process、Thread的相互关系25Win32的API调用263.2虚拟化技术虚拟化在分布式系统中的作用支持遗留软件（legacysoftware）减少软件平台和机器类型的数量高移植性和灵活性虚拟化系统结构(a)程序、接口、和系统之间的通用结构(b)在系统B之上的虚拟化系统A的通用结构274321虚拟化系统提供4种接口硬件虚拟化（通用指令）硬件虚拟化（特权指令）操作系统（OS）虚拟化编程虚拟化28虚拟化系统提供4种接口硬件虚拟化：由机器指令组成的硬件和软件间接口可被任何程序调用硬件虚拟化：由机器指令组成的硬件和软件间接口只可被特权程序（如OS内核）调用OS虚拟化：由系统调用（如OS提供）组成的接口编程虚拟化：由子程序库调用组成的接口通常构成应用程序接口(API).很多情况下，上述系统调用隐藏在API中29虚拟机体系结构两种虚拟化方式构建一个运行时系统，如Java运行环境，或者，进程虚拟机完全屏蔽硬件，提供另一种机器指令界面，称为虚拟监控器（VMM），如VMware系统,Xen系统(可提供给不同的程序，多操作系统并发)30虚拟化技术的比较虚拟化技术优点缺点硬件虚拟化每个虚拟机都构成一个独立完整的计算环境。虚拟机的性能高、安全性好、隔离性好。不同的处理器需采用不同的虚拟软件。软件成本高、很难实现真正的物理级兼容性操作系统虚拟化每台计算机只虚拟一种操作系统。管理简单、性能较高，安全性中等。只能支持同一操作系统下的不同应用。主操作系统决定虚拟操作系统的安全性虚拟化PC每台PC机可提供2个操作系统的虚拟组合，在X86体系结构上应用比较成功。性能取决于PC机的硬件配置硬件兼容性不全面，性能和安全性较差。编程虚拟化兼容性取决于JVM。支持跨平台应用，大幅度减少应用程序移植的工作量。大并发程序执行的性能、可靠性、安全性存在风险313.3客户进程的设计客户程序：用户接口32网络化用户接口带专用协议的网络化应用程序支持访问远程应用程序的通用方案33网络化用户接口举例：X-Window图形接口系统X-kernel：Windowsmanager34高级用户接口复合文档：各种文档（文本，图像，电子表等）的聚集功能：即拖即丢(drag-and-drop)就地编辑(in-placeediting)特点：与用户接口无缝集成。不同的应用程序处理文档的不同部分。如，WindowsOLE(ObjectLinkingandEmbedding)技术35客户程序对分布透明性的支持存取透明性客户存根程序(stub)：代理程序隐藏客户和服务器主机之间的硬件差异和通信位置透明性、迁移透明性、重定位透明性命名系统：全局逻辑名字重新绑定机制：当服务器改变位置后，通知客户重新自动绑定clientstubserver36客户端与分布透明性举例：使用客户端解决服务器复制透明性的方案37客户程序对分布透明性的支持复制透明性客户代理(proxy)，转发到来的请求38客户程序对分布透明性的支持失败透明性重新连接：通信失败时，重试本地数据缓存：例，脱机方式并发透明性、持久透明性需要客户软件的支持很少并发透明性：事务监控器（中介服务器）实现并发控制和恢复持久透明性一般完全由服务器处理393.4服务器进程的设计服务器:

为一组客户提供专门服务的进程。服务器的两种组织迭代（Iterative）型服务器：自己处理请求并发（concurrent）型服务器：交给进（线）程处理服务器端点（endpoint）例1：FTP:21例2：HTTP:8040服务器设计（1）Client-to-Server两种绑定策略：(a)静态:由daemon进程负责(如，DCE)(b)动态:由superserver进程负责(如,Unixinetd)41服务器设计（2）client中断服务器执行的策略：客户重启：中断连接客户发送out-of-band命令发送方法：利用单独另外的控制端点，或者，利用同一链路，如，TCP中发送urgentdata42服务器设计（3）Client-to-Server两种连接方式无状态服务器：服务器不保存客户程序的状态例如，Web服务器有状态服务器：保存客户程序的状态例如，NFS文件服务器文件使用表（客户，文件，可更新否）服务器重启时：恢复故障前状态43服务器设计（4）用无状态服务器实现有状态服务仿真方式：例：Read文件Open,Read,CloseCookie:客户的标识数据在Web服务器中记录客户的行为历史信息，利用Cookie机制进行管理对用户是透明的。如保存用户的登录信息缺点：违反隐私权，有安全性隐患（仿冒ID）44服务器集群服务器集群：一组由网络连接的机器，每台机器上运行一个或多个服务器进程45服务器集群系统结构逻辑上由三层组成46服务器集群TCP转发原理负载平衡策略轮转法内容感知的请求分布47分布式服务器配置可动态变化的机器群访问点也可以变化实现技术MIPv6支持移动节点的机制移动节点原籍网络（homenetwork）原籍地址（homeaddress）：稳定、不变化原籍代理（homeagent）：特别的路由器暂住地址（careofaddress）：临时的网络地址48分布式服务器路由优化49服务器机群管理通用方法在普通节点上通过远程登录监控、安装、改变组件在管理机操作收集信息、升级组件、增减节点50例：PlanetLab-协作型分布式系统VMM–

虚拟机监控器Vserver–

虚拟服务器（程序库、通信）（VMM）51例：PlanetLab-协作型分布式系统节点管理器：管理工具节点拥有者：提供资源切片授权者：子资源管理管理授权者：节点管理服务提供者：使用者52例：PlanetLab-协作型分布式系统实体间的管理关系节点拥有者把它的节点加入到管理授权者的范围下，以适当地限制使用管理授权者提供必要的软件，在PlanetLab系统中增加节点服务提供者向管理授权者注册，对后者提供的节点表示信任服务提供者联系切片授权者，请求在一组节点上创建一个切片切片授权者需要对服务提供者进行授权认证节点拥有者为切片授权者提供切片创建服务。实质上是向切片授权者委托资源管理管理授权者向切片授权者委托切片创建533.5代码迁移操作传送（operationshipping）代码迁移（codemigration）进程迁移（processmigration）目的:改进性能负载平衡，例：网格计算减少通信量，例，queryshipping并行性，例，并行搜索Web灵活性动态配置分布式程序攻击54代码迁移的原因实现客户与服务器通信的动态配置原理客户首先取得必需的软件，然后调用服务器55代码迁移模型进程的组成代码段：指令集资源段：外部资源引用，文件、打印机、设备等执行段：状态，私有数据、SP,PC等移动方式弱移动性：只移动代码段强移动性：移动代码段、执行段发起方式发送者发起：上载程序接收者发起：下载程序发送者接收者56代码迁移模型代码迁移的分类57局部资源当代码段迁移到另一台机器后，需要考虑资源段中对资源引用的变化进程-资源之间的绑定关系by-identifier：通过标识符，引用特定的资源by-value：引用资源的值by-type：引用某个类型的资源资源-机器之间的绑定关系Unattached：独立于机器，可以移动。例：数据文件fastened：与机器有关联，难以移动，例：局部数据库fixed：与机器密切绑定，不能移动。例：局部通信端口58局部资源（2）解决对局部资源引用的方法GR：建立全局引用。例，URLMV：移动资源CP：拷贝资源的值RB：重新绑定局部可用资源。UnattachedFastenedFixedByidentifierMV(orGR)GR(orMV)GRByvalueCP(orMV,GR)GR(orCP)GRBytypeRB(orGR,CP)RB(orGR,CP)RB(orGR)资源-机器绑定方式进程-资源绑定方式59异构系统中的代码迁移（1）异构系统：不同的硬件和操作系统弱移动性：重新编译源代码，生成新的代码段强移动性：避免执行段中有平台相关的数据例：迁移栈（migration）方法迁移只能发生在固定点：子程序调用程序栈保存在迁移栈中在迁移时，全局数据和迁移栈内容发给目标机器虚拟机方法。在虚拟机上执行源代码或中间代码，支持可移植语言60异构系统中的代码迁移（2）迁移栈方法的工作原理61D‘Agents中的代码迁移(1)D'Agent，也称为AgentTcl支持代码迁移的中间件平台系统sender发起的弱迁移性进程迁移执行的强迁移性进程克隆执行的强迁移性Agent:可在不同机器上迁移的程序解释型语言：Tcl,Java,等脚本（Script）:指令序列62D‘Agents中的代码迁移(2)

举例：独立进程执行的弱迁移向远程机器交付一个脚本procfactorialn{#计算n的阶乘n!if($n1){return1;} #fac(1)=1

expr$n*[factorial[expr$n–1]]#fac(n)=n*fac(n–1)}setnumber… #tellswhichfactorialtocomputesetmachine… #identifythetargetmachineagent_submit$machine–procsfactorial–varsnumber–script{factorial$number}agent_receive… #receivetheresults(leftunspecifiedforsimplicity)63D‘Agents中的代码迁移(3)

举例：sender发起的强迁移tclAgent迁移到另一台机器上执行UNIXwho

命令all_users$machinesprocall_usersmachines{

setlist"" #Createaninitiallyemptylist

foreachm$machines{ #Considerallhostsinthesetofgivenmachines

agent_jump$m #Jumptoeachhost

setusers[execwho] #Executethewhocommand

appendlist$users}

#Appendtheresultstothelist

return$list #Returnthecompletelistwhendone

}setmachines… #Initializethesetofmachinestojumpto

setthis_machine #Settothehostthatstartstheagent#Createamigratingagentbysubmittingthescripttothismachine,fromwhere

#itwilljumptoalltheothersin$machines.agent_submit$this_machine–procsall_users-varsmachinesscript{all_users$machines}agent_receive… #receivetheresults(leftunspecifiedforsimplicity)64实现技术(1)D‘Agents系统体系结构服务器：agent管理，授权，通信管理RTS内核：agent模型，启动和结束agent，迁移操作，agent间通信解释器：解释器组件，安全性模块，内核接口，代理运行状态65实现技术(2)D‘Agents中代理的状态构成4张表：纪录数据状态2个栈：记录执行命令状态描述全局解释器变量表agent解释器需要的变量全局系统变量表返回代码，错误代码，错误消息串等全局程序变量表程序中用户定义的全局变量过程定义表Agent执行的脚本定义命令栈当前执行命令的命令栈调用祯栈激活记录栈，每条命令一个66*3.6软件代理软件代理（softwareagent）能够执行任务的自主进程基本性质自主性：独立自主地动作感知性：感知周围环境反应性：对外界的刺激有动作协作性：与其他代理合作67软件代理的分类协作代理(collaborativeagent)通过多个代理的合作达到共同目标，如CSCW移动代理（mobileagent）可在不同机器之间移动，如Crawler搜索接口代理（interfaceagent）帮助最终用户使用多个应用。如MyYaoo推荐信息代理（informationagent）管理来自不同数据源的信息。如e-mail过滤68分布式系统中的软件代理区分不同种类代理的重要性质性质所有代理都具有?描述自主性(Autonomous)是可独立地动作反应性(Reactive)是可及时地对环境变化做出响应先发性(Proactive)是可启动影响其所在环境的动作交流性(Communicative)是可与用户和其他代理交换信息连续性(Continuous)No具有相当长的生命周期移动性(Mobile)No可从一个场地迁移到另一个场地自适应性(Adaptive)No能够学习69代理技术FIPA（智能物理代理基金会）-代理平台多代理系统的基本服务创建、删除、定位、代理间通信70代理平台的通用模型代理管理系统创建/删除代理查找代理的端点。名称服务局部目录服务查找该平台上的代理-黄页方法可被远程代理访问代理通信通道（ACC）提供平台之间可靠的、有序的点到点消息通信服从IIOP协议71代理通信语言FIPAACL通信语言ACL消息=(消息头，内容)消息头=(目的，发送者，接受者，语言，本体论)目的：请求、响应、协商等语言：消息内容所采用的语言本体论：符号与其含义之间的标准映射72FIPAACL消息类型举例消息目的Description消息内容INFORM告知给定的命题为真命题QUERY-IF查询一个命题是否为真命题QUERY-REF查询一个对象表达式CFP请求一个提议提议PROPOSE提供一个提议提议ACCEPT-PROPOSAL告诉给定的提议被接受提议IDREJECT-PROPOSAL告诉给定的提议被拒绝提议IDREQUEST请求执行一个动作动作定义SUBSCRIBE订阅一个信息源信息源的引用73ACL消息举例两个代理之间的FIPAACL消息：使用Prolog语句表达族谱（

genealogy）信息字段值PurposeINFORMSendermax@Receiverelke@iiop://royalty-watcher.uk:5623LanguagePrologOntologygenealogyContentfemale(beatrix),parent(beatrix,juliana,bernhard)74*3.7分布式处理机管理工作站模型无盘工作站有盘工作站75工作站上磁盘的作用使用情况优点缺点无磁盘费用低，灵活，易于软硬件维护网络负载重，文件服务器为瓶颈换页，保存临时文件网络负载小磁盘成本高换页，保存临时文件和执行文件网络负载更小磁盘成本更高，执行文件的更新复杂换页，保存临时文件和执行文件，文件缓存。网络负载更更小，减少文件服务器负载成本高，缓存一致性维护复杂完全的本地文件系统几乎无网络负载，不需要文件服务器失去透明型76空闲处理机远程执行：rshmachinecommand

基于注册表算法77工作站管理处理机池模型78工作站管理排队模型平均响应时间T=1/(λ–μ)n台处理机平均响应时间T1=T/n计算机完成工作用户用户每秒共产生μ个请求系统每秒能处理γ个请求79工作站管理混合模型：前台交互式任务：个人工作站后台任务：处理机池80处理机分配管理分配模型非迁移型迁移型分配目标最大CPU利用率最快响应时间响应比：实际运行时间/实际需要时间负载平衡81处理机分配分配方案1：处理机1运行进程A，处理机运行进程B，

平均响应时间

=（10＋8）/2＝9分配方案2：处理机1运行进程B，处理机运行进程A，

平均响应时间

=（30＋6）/2＝18处理机1

10MIPS处理机2

100MIPS没有队列5秒队列进程A(1亿条指令)B(3亿条指令)10秒30秒6秒8秒82处理机分配设计确定性vs启发式（试探性）集中式vs分布式最优vs较优局部的vs全局的发送者发起的vs接收者发起的

83急切型启发式算法转发法：随机选择一台机器A，向它发送新进程。如果A已经过载，A也同样随机选择另一台机器B，向B发送进程。查询法：随机选择一台机器A，向它发送一个负载情况询问。如果欠载，A就会得到这个进程；否则，将重新选择一台机器。比较法：询问k台机器，确定它们的确切负载情况。将新过程传送到负载最小的那台机器上。84基于图的确定性算法例：3个处理机，9个进程方案A:通信量=(3＋2＋4＋4)＋(2＋8＋5＋2)＝30方案B:通信量=(3＋2＋4＋4)＋(3＋5＋5＋2)＝2885集中的启发式的up-down算法目标：工作站公平地享用系统的计算能力使用情况表：〉0表示使用资源；<0表示需要系统资源，0为初始值时间P1到达P1分配到处理器P2到达P2分配到处理器P1完成P2完成使用情况表积分86层次式的算法

主任委员会部门领导工作人员87发送者/接收者算法请求帮助请执行一个进程吧请完成一个工作吧此机器负担太重了求助机器判定它的负担太重（a）今晚我空闲我无事可作机器宣告它可被使用我厌烦了需要CPU周期？需要帮助？（b）88处理机的分配协同调度（co-scheduling）将一组协同进程安排在不同处理机的同一时间片内以产生最小的时间延迟。ACBDACBDACBD0101234501012345243567（a）简单轮转（b）分组调度处理器处理器时间片时间片89*3.8实时分布式系统实时系统当某个激励出现时，系统必须以一定的方式在限定的时间内（截止期，deadline）响应它。如果超时，即使结果正确，也认为是系统失效实时事件类型周期性：有规则地出现，如每隔ΔT秒非周期性：不规则地重现突发性：无法预测地出现90实时事件流例：3个事件流+1个突发事件时间ABCABCABCABCABACBACBAACBX无法预料的事件A的周期B的周期C的周期工作负荷空闲91分布式实时计算机系统结构DevCDevCDevCDevCDevCDevCC外部设备计算机网络执行机构传感器专用计算机：嵌入式微控制器，独立计算机传感器：接收设备信号执行器：向设备发信号92实时模型实时系统类型软实时系统(soft)：错过截止期后，价值降低硬实时系统(hard)：严格不允许，如飞机导航固实时系统(fixed)：错过截止期后，价值为0DTimeValueDTimeValue93分布式实时系统设计事件触发系统当一个重要的外部事件触发时，它被传感器察觉到，并导致与传感器相连的CPU得到一个中断请求。通常是中断驱动的。主要问题当事件风暴（eventshower）发生时，在过载（overload）情况下会失效。94分布式实时系统设计时间触发系统每⊿T毫秒产生一次时钟中断。在每一次时钟滴答时，对（选定的）传感器进行采样，并且驱动（特定的）执行机构。中断仅在时钟滴答时发生。⊿T的选择必须非常小心地选择。若⊿T太小，系统将产生许多时钟中断，将浪费大量的时间来响应它们95分布式实时调度硬实时与软实时硬实时：保证所有截止期都要满足软实时：best-effort抢占式(preemptive)与非抢占式允许在高优先级的任务到来时挂起当前的任务动态型(dynamic)与静态型在运行期间进行调度集中式与分散式(decentrlized)

分散式：各个处理机可以独立做出决定

96分布式实时调度可调度性设一个周期性分布式实时系统拥有N个处理机，m个运行任务1,2,...m任务i所需CPU时间Ci，周期为Pi系统利用率μ例：Pi=20ms,Ci=10ms,m=5，则=3

97典型的动态调度算法1.比率单调算法(ratemontonic)

无互斥约束的周期性任务每个任务分配一个与其执行频率相等的优先级动态抢占式调度可调度条件98典型的动态调度算法2.最早截至期优先法EDF（earliestdeadlinefirst）等待队列根据这些任务的截止期排序

3.最小松弛度法(leastlaxity)

松弛度(laxity,slack)：截止期的剩余时间优先调度具有最小松弛度的任务上述三种方法在分布式环境中，都不是最优的，可作为启发式规则99静态调度算法已知所有任务的列表及它们各自的运行时间

最优方法的复杂性为任务个数的指数数量级启发式方法。非抢占式静态调度

3A1254678910B激励响应1234561352467891078910ABAB激励激励响应响应时间时间（a）调度方