高级操作系统课件-第三章分布式进程管理

《高级操作系统课件-第三章分布式进程管理》由会员分享，可在线阅读，更多相关《高级操作系统课件-第三章分布式进程管理（79页珍藏版）》请在金锄头文库上搜索。

1、第三章 分布式进程管理,线程 代码迁移 处理器任务分配 软件代理,进 程,定义：执行中的程序 进程控制块（PCB）,进程的状态,线 程,未引入线程前的进程：资源分配单位（存储器、文件）和CPU调度（分配）单位。 线程：成为CPU调度单位，而进程只作为其他资源分配单位。 线程只拥有必不可少的资源，如：线程状态、寄存器上下文和栈 同样具有就绪、阻塞和执行三种基本状态 所有线程必须同时挂起，进程的终止导致它包含的所有线程的终止 线程的优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。 线程的创建时间比进程短； 线程的终止时间比进程短； 同进程

2、内的线程切换时间比进程短； 由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信；,进程与线程的关系,进程和线程的比较,地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享该进程地址空间和其他资源某进程内的线程在其他进程不可见 通信：进程间通信通过IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信需要进程同步和互斥手段的辅助，以保证数据的一致性 调度：线程上下文切换比进程上下文切换要快得多； 结论： 多线程能提高性能 线程不像进程那样彼此隔离，并受到系统自动提供的保护，因此多线程应用程序开发需要付出更多努力,非分布式系统中线程的使用,使用多线程的优点：

3、 在某线程阻塞时，其他线程可以继续工作 利用多处理器，并行工作 缩短IPC通信的时间 出于软件工程的考虑:字处理程序(用户输入、拼写检查、语法检查、文档布局),非分布式系统中线程的使用,IPC导致的进程上下文切换,线程实现,用户级线程 内核级线程 组合的方法,用户级线程,有关线程管理的所有工作由应用程序通过线程库完成，内核不知道线程的存在 应用程序和它的线程被分配给内核管理下的进程,优点： 创建和销毁线程的开销很小 线程切换不需要内核模式特权，节省切换开销 调度策略可以是应用程序特定的 用户级线程可以在任何操作系统中运行，不需要对底层内核进行修改以支持用户级线程 缺点： 一个线程被阻塞时，进程

4、中所有线程都被阻塞 一个多线程应用程序不能利用多处理技术，内核一次只把一个进程分配给一个处理机,内核级线程,W2K, Linux, OS/2采用 有关线程管理的所有工作由内核完成 优点： 同一进程内线程可被分配到不同处理器上 一线程被阻塞，可切换到另一线程 缺点： 系统开销大,组合的方法,Solaris（最成功、应用最广泛的商业UNIX版本）操作系统采用 结合前两种线程优点，同时减少其缺点 线程创建完全在用户空间完成，线程调度和同步在应用程序内进行 n个用户级线程被映射到一些（少于n个）内核级线程上，程序员可为应用程序和机器调整内核级线程数目，以达到最佳效果,组合的方法,分布式系统中线程的使用

5、,多线程客户：Web浏览器 多线程服务器,多线程服务器,以分发器/工作者组织的多线程服务器,代码迁移,定义：将程序（或执行中的程序）传递到其它计算机 迁移动机： 实现负载均衡 将进程从负载重的系统迁移到负载轻的系统，从而改善整体性能 改善通信性能 交互密集的进程可迁移到同一个节点执行以减少通信开销 当进程要处理的数据量较大时，最好将进程迁移到数据所在的节点,可用性 需长期运行的进程可能因为当前运行机器要关闭而需要迁移 使用特殊功能 可以充分利用特定节点上独有的硬件或软件功能,代码迁移,客户首先获取必需的软件，然后调用服务器,代码迁移-灵活性,代码迁移模型,代码迁移的不同方法 进程组成： 代码段

6、：正在运行的程序的所有指令 资源段：包含进程需要的外部资源的指针 执行段：存储进程的当前执行状态量：私有数据、堆栈和程序计数器 弱可移动性与强可移动性 弱可移动性：只能传输代码段以及某些初始化数据，程序以初始状态重新执行，简单 强可移动性：还可以传输执行段，较难实现 发送者启动与接收者启动 发送者启动：计算服务器，客户需要访问服务器资源，客户端需要注册验证 接收者启动：可以是匿名的，Java applet，提高客户端性能,迁移与本地资源,MV：移动资源 GR：建立全局系统范围内引用 CP：复制资源的值 RB：将进程重新绑定到本地同类型资源,资源对机器绑定,进程对 资源绑定,进程对资源绑定: 按

7、标志符（URL）、按值和按类型 资源对机器绑定：未连接（数据文件）、附着连接（数据库）和紧固连接（本地设备）,迁移代码时，根据引用本地资源方式不同所采取的不同做法,处理器任务分配,分配算法的设计原则 分配算法的实现问题 分配算法实例,分配算法的设计原则,分配算法的设计原则： 确定性算法和启发性算法 集中式算法和分布式算法 最优化算法和次优化算法 局部性算法和全局性算法 发送者启动算法和接收者启动算法,局部性算法和全局性算法,第四个设计问题与迁移策略有关。 当一个新进程被创建时，系统需要决定它是否在创建它的机器上运行。若该机器繁忙，那这个新进程就必须迁移到其它机器上去运行。 对于是根据本机局部信

8、息还是全局信息来决定新进程是否迁移，目前存在着两种学派。1）一种学派主张简单的局部算法：若机器的负载低于某个阀值，那么新进程就在本地机器上运行；否则，就不允许该进程在本地上运行。 2）另一种学派认为局部算法太武断了。最好在决定新进程是否在本地机器上执行之前，先收集其它一些机器上的负载信息。 比较： 局部算法简单，但远远达不到最优； 而全局算法需要可能付出巨大的代价来换取一个性能稍微好一点的结果。,发送者启动算法和接收者启动算法,最后一个设计问题与定位策略有关。 一旦决定不允许一个进程在本地机器上运行，那么，迁移算法就必须决定将该进程应该迁移到哪台目的机器上。 显然，迁移算法不能是本地的。它需要

9、通过获得其它机器上的负载信息来决定迁移的目的机器。这些负载信息可以通过两种途径来获得。 一种是过载者启动的 另一种是欠载者启动的,过载者启动：由过载者来寻找迁移的目的机器 如图：一个机器超载时，它向其它机器发送求助请求，希望将自己的一些新进程迁移到其它机器上运行。 欠载者启动： 当一个机器处于空闲状态即欠载状态时，由这台欠载机器来宣布自己可以接收外来的工作。其目的就是寻找一台可以给自己增加一些额外工作的机器,分配算法的实现问题,负载的度量 额外消耗 复杂性 稳定性,实现问题1：负载的度量,基本上，所有的算法都假定每一台机器都知道它自己的负载，也就是说，它可以判断自己是超载还是欠载，并且能够告诉

10、其它机器自己的负载。 然而，度量一台机器是否超载并不象它看上去那样简单。,负载的度量：方法1,度量方法1：以机器上的进程数量作为机器的负载 优点：简单 原因：只需要计算机器上的进程数量 缺点：用进程数量的多少来表示机器的负载是不确切的。 原因：即使在一台空闲机器上，仍然会有一些后台监视进程在运行，例如，邮件、新闻、守护进程、窗口管理程序以及其它一些进程。,负载的度量：方法2,对度量方法1进行如下改进： 只计算正在运行或已经就绪进程的数量。 原因： 每一个正在运行或处于就绪状态的进程都会给系统增加一定的负载，即便它是一个后台进程。存在的问题： 许多后台守护进程只是定时被唤醒，检查所感兴趣的事件是

11、否发生，如果没有，则重新进入睡眠状态。因此，这类进程只给系统带来很小的负载。,负载的度量：方法3,直接使用处理机利用率： 就是处理机繁忙时间在全部时间中（繁忙时间+空闲时间）所占的比例。一个利用率为20%的处理机负载要比利用率为10%的处理机大 优点：比较合理 原因：兼顾了用户进程和守护进程,实现问题2：额外开销,许多理论上的处理机分配算法都忽略了收集负载信息以及传送进程的额外开销。 若一个算法将一个新创建的进程传送到远程机器上运行仅使系统性能提高10%左右，那它最好不要这样做，原因是传送进程的开销足以抵消所提高的性能。 一个好的算法应该考虑算法本身所消耗的处理机时间、内存使用、以及网络带宽等

12、。但很少有算法能做到这一点，因为它太难了。,实现问题3：复杂性,在处理机分配算法实现中还必须考虑复杂性。 事实上，所有的研究者只分析、模拟或计算处理机的利用率、网络的使用情况以及响应时间，以此来衡量他们所提出算法的好坏。 很少有人考虑软件的复杂性对系统的性能、正确性和健壮性所产生的影响。算法性能有可能只是比现有的算法稍好一点，却在实现上却复杂得多。,处理机分配算法的实现问题,然而，Eager 等人在1986年所做的研究使追求复杂和最优算法的人们看到了希望。 他们研究了三个算法，在这三个算法中，所有的机器都测量自己的负载以判断它是否超载。 当一个新进程创建时，创建该进程的机器就会检查自己是否超载

13、，如果是，则它就寻找一台欠载的远程机器去运行该进程。这三个算法的不同之处在于寻找远程机器的方法。,处理机分配算法的实现问题,算法1 随机地选择一台机器，并把新创建的进程传送到该机器上。 如果该接收机器本身也超载，它也同样随机地选择一台机器并把该进程传送过去。 这个过程一直持续到有一台欠载的机器接收它为止，或者指定计数器溢出停止该进程的传送,处理机分配算法的实现问题,算法2 随机地选择一台机器，然后发送一个信息给该机器询问该机器是超载还是欠载。 如果该机器欠载，它就接收新创建的进程；否则，新进程的创建机器继续随机地选择一台机器并向其发送一个询问消息。 这个过程一直持续到找到一台欠载机器为止，或超

14、过了一定的询问次数，如果找不到欠载机器，该新创建的进程就只好留在本地机器上运行。,处理机分配算法的实现问题,算法3 给k台机器发送询问消息，接收这k台回送的负载消息。这个新进程将发送给负载最小的机器，并在它上面运行。 显然，如果我们不考虑所有发送询问负载消息和传送进程的额外开销，那么，人们会认为算法3的性能最好，事实上也确实如此。 尽管算法3的性能只比算法2的性能稍好一点，但其复杂性以及额外开销却比算法2要大的多。 Eager等人认为，如果一个简单算法只比复杂算法在性能上略低一点的话，那么，最好使用简单算法。,实现问题4：稳定性,最后一个实现问题就是稳定性。由于不同的机器都在异步地运行各自的计

15、算，所以，整个系统的负载很少能够达到平衡。 因此，有时候会发生这样一种情况：在某个时刻，机器A得到的信息是机器B的负载较轻，因而，它就将新创建的进程传送给机器B。机器B在收到该进程之前负载又增加了，所以，收到该进程后，它发现机器A的负载较轻，于是，它就将该进程又传送给机器A。这样造成了某个可怜的进程被来回传送的情况。 原因是:每一个机器上的负载每时每刻都在变化。,分配算法实例 1. 图论确定算法,假定：每个进程都知道1）所需的处理机 2）所要求的内存 3）系统中任意一对进程间的平均通信量 若系统中处理机的数目k比进程数少，那么系统中的一些处理机就必须被分配多个进程 基于图论的确定性算法 保证在

16、系统网络通信量最小的条件下对处理机进行分配。,系统的带权图表示,系统可以被表示图G(V,E)， V中的每个节点表示一个进程 E中的每条边表示两个进程需要通信，边上面的数字表示两个进程之间的通信量。 从数学角度看，处理机分配问题已经被简化为： 在一定的约束条件下（例如，每一个子图总的处理机和内存需求量不超过某一个阀值）将图分割成k个不相连的子图。 算法的目标就是在满足所有限制条件下，找到一个分割方法，使得分割后各子图之间的通信量之和最小。,分割举例,下图表示了一个图的两种不同的分割方法，并得到了两个不同的通信量。,CPU1,CPU2,CPU3,CPU1,CPU2,CPU3,分割举例,a中，系统图被分割为： A,E,G在处理机1上 B,F,H在处理机2上 C,D,I在处理机3上整个网络通信量 =被虚线分割开的边上 的权值之和 =30,3+2+4+4=13,2+8+5+2=17,分割举例,b中显示的分割得到的通信量之和为28 如果它满足所有对内存和处理机的限制，那它就是一个比较好的分割，因为它要求的 网络通信量之和较小。,3+2+4+4=13,3+5+5+2=15,2. 集中式算法,