DOS-CH3-Proc-v14-16

第3章分布式进程管理,东北大学信息学院张天成谷峪2016年10月,2,主要内容,3.1进程和线程管理3.2虚拟化技术3.3客户进程的设计3.4服务器进程的设计3.5代码迁移3.6*软件代理3.7*分布式处理机管理3.8*实时分布式系统,基础知识-计算机体系结构,2020/4/25,CH3-分布式进程管理,3,C程序存储模型,2020/4/25,CH3-分布式进程管理,4,inta=0;（）char*p1;（）main()（)inta,b;（）chars=“abc”;（）char*p2;（）char*p3=“123456”;（）（）staticintc=0；（）p1=(char*)malloc(10);()strcpy(p1,123456);Foo(a,b);Foo(intp1,intp2)intx,y;staticintz;,机器代码,2020/4/25,CH3-分布式进程管理,5,voidmain()intb;inti=0,j=0;while(i0表示使用资源；0表示需要系统资源，0为初始值.处理机分配给score最小的用户Score：+1(up)，使用；-1(down),不使用。,117,分层算法,集中式算法中，中央节点是瓶颈，可伸缩性差每个负责人，管理R个职员一个用户可请求S个资源（职员）如何在R个资源分配S个请求，是个复杂问题多个用户请求之间存在有竞争问题、死锁问题,2012-9-19东北大学软件所于戈,118,发送者/接收者算法,2012-9-19东北大学软件所于戈,119,处理机的分配,协同调度（co-scheduling）协同进程组，包含需要相互通信的进程，如A,D将一组协同进程安排在不同处理机的同一时间片内以产生最小的时间延迟。,A,C,B,D,A,C,B,D,A,C,B,D,0,1,0,1,2,3,4,5,0,1,0,1,2,3,4,5,2,4,3,5,6,7,（a）简单轮转,（b）分组调度,处理器,处理器,时间,片,时间,片,2012-9-19东北大学软件所于戈,120,*3.8实时分布式系统,实时系统当某个激励出现时，系统必须以一定的方式在限定的时间内（截止期，deadline）响应它。如果超时，即使结果正确，也认为是系统失效实时事件类型周期性：有规则地出现，如每隔T秒非周期性：不规则地重现突发性：无法预测地出现,2012-9-19东北大学软件所于戈,121,实时事件流,例：3个事件流+1个突发事件,2012-9-19东北大学软件所于戈,122,分布式实时计算机系统结构,专用计算机：嵌入式微控制器，独立计算机传感器：接收设备信号执行器：向设备发信号,2012-9-19东北大学软件所于戈,123,实时模型,实时系统类型软实时系统(soft)：错过截止期后，价值降低硬实时系统(hard)：严格不允许，如飞机导航固实时系统(fixed)：错过截止期后，价值为0,DTime,Value,2012-9-19东北大学软件所于戈,124,分布式实时系统设计,事件触发系统当一个重要的外部事件触发时，它被传感器察觉到，并导致与传感器相连的CPU得到一个中断请求。通常是中断驱动的。主要问题当事件风暴（eventshower）发生时，在过载（overload）情况下会失效。,2012-9-19东北大学软件所于戈,125,分布式实时系统设计,时间触发系统每T毫秒产生一次时钟中断。在每一次时钟滴答时，对（选定的）传感器进行采样，并且驱动（特定的）执行机构。中断仅在时钟滴答时发生。T的选择必须非常小心地选择。若T太小，系统将产生许多时钟中断，将浪费大量的时间来响应它们,2012-9-19东北大学软件所于戈,126,分布式实时调度,硬实时与软实时硬实时：保证所有截止期都要满足软实时：best-effort抢占式(preemptive)与非抢占式允许在高优先级的任务到来时挂起当前的任务动态型(dynamic)与静态型在运行期间进行调度集中式与分散式(decentrlized)分散式：各个处理机可以独立做出决定,2012-9-19东北大学软件所于戈,127,分布式实时调度,可调度性设一个周期性分布式实时系统拥有N个处理机，m个运行任务1,2,.m任务i所需CPU时间Ci，周期为Pi系统利用率例：Pi=20ms,Ci=10ms,m=5，则=3,2012-9-19东北大学软件所于戈,128,典型的动态调度算法,1.比率单调算法(ratemontonic)无互斥约束的周期性任务每个任务分配一个与其执行频率相等的优先级动态抢占式调度可调度条件,2012-9-19东北大学软件所于戈,129,典型的动态调度算法,2.最早截至期优先法EDF（earliestdeadlinefirst）等待队列根据这些任务的截止期排序3.最小松弛度法(leastlaxity)松弛度(laxity,slack)：截止期的剩余时间优先调度具有最小松弛度的任务上述三种方法在分布式环境中，都不是最优的，可作为启发式规则,2012-9-19东北大学软件所于戈,130,静态调度算法,已知所有任务的列表及它们各自的运行时间最优方法的复杂性为任务个数的指数数量级启发式方法。非抢占式静态调度,（a）调度方案1,（b）调度方案2,2012-9-19东北大学软件所于戈,131,动态算法与静态算法的比较,任务类型动态算法适合于事件驱动设计静态算法适合于事件驱动设计算法设计静态算法需要事先细致的规划，考虑各种最坏情况资源利用动态算法潜在地更好利用系统资源优化算法给定足够的计算能力，静态系统可实现最优的，或较优的调度一些系统采用静态与动态的混合方法,2012-9-19东北大学软件所于戈,132,小结,线程-提高处理的效率客户程序的设计服务器程序的设计对象服务器的设计代码迁移-提供性能和灵活性软件代理-支持自主和协同计算分布式处理的负载平衡分布式实时调度算法：RM,EDF等,2012-9-19东北大学软件所于戈,133,习题（1）,有一个文件服务器，当所需的数据放在缓存中时，接受、分派或处理一个请求需要花费15ms；但在1/3的情形下，还要做磁盘操作，需要75ms，线程在这时处于睡眠状态。如果使用单线程，每秒能处理多少请求？而如果使用多线程呢？假设完全在用户空间实现线程，运行系统每隔1秒得到1个时钟中断。如果发生时钟中断时，某个线程正在运行系统中执行。这时会出现什么问题？给出一种解决方案。设计一种简单的线程实现方式，其中的轻量进程的个数与可运行的线程一样多。,2012-9-19东北大学软件所于戈,134,习题（2）,设计一种支持多通信协议的多线程服务器。它与底层操作系统的传输层接口采用socket。设计支持持久对象的对象适配器时，需考虑哪些问题？修改示例对象适配器中的thread_per_object过程，使得该适配器控制的所有对象都用一个单一的线程处理。在一个Web服务器中，维护有一个映射表，描述客户的IP地址与最近访问的网页的映射关系。当一个客户连接该服务器时，服务器在表中查找该客户，如果找到，则返回登记的网页。这种服务器，是有状态的，还是无状态的。,2012-9-19东北大学软件所于戈,135,*习题（3）,每个DAgent代理作为独立的进程实现。代理之间可通过共享文件和消息传递方式进行通信。而文件不能在不同主机间传递。则按照移动性框架，资源段由哪部分代理的状态构成。比较DAgent系统和FIPA代理平台在系统结构方面的异同点。ACL属于OSI参考模型中的那一层？有什么优点？为什么需要在ACL消息中制定本体论？,2012-9-19东北大学软件所于戈,136,*习题（4）,up-down算法是一种公平分配处理机的集中式算法。设计一种算法，虽然不公平，但能均匀地分布负载。当一个分布式系统过载时，它尝试m次去找到一个空闲的工作站。一个工作站拥有k个工作的泊松分布概率为：P(k)=(ke-)/k!这里为每个工作站的平均工作个数。给出一个过载工作站在m次内找到一个空闲工作站（即k=0）