分布式系统的进程和处理机.ppt

《分布式系统的进程和处理机.ppt》由会员分享，可在线阅读，更多相关《分布式系统的进程和处理机.ppt（82页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第4 4章章 分布式系统中的进程和处理机分布式系统中的进程和处理机 线程线程 系统模型系统模型 处理机分配处理机分配 分布式系统的调度分布式系统的调度 容错容错 实时分布式系统实时分布式系统 线程线程4.1.1 线程简介线程简介进程与线程进程与线程w 进进程程是是程程序序在在一一个个数数据据集集合合上上运运行行的的过过程程，使使系系统统进进行行资资源源分分配配和和调调度度的的一一个个独独立立单单位位。引引入入进进程程的的目目的的是是为为了了使使多多个个程程序并发执行，以提高资源利用率和系统吞吐量。序并发执行，以提高资源利用率和系统吞吐量。w 线线程程：能能够够独独立立运运行行的的基基本本单单

2、位位，轻轻量量级级的的进进程程，一一个个进进程程可可以以创创建建多多个个线线程程，有有统统一一的的地地址址空空间间。引引入入线线程程的的目目的的是是为为了减少程序在并发执行时所付出的时空开销。了减少程序在并发执行时所付出的时空开销。进程进程线程线程程序计数器程序计数器计算机计算机计算机计算机 线程线程4.1.1 线程简介线程简介进程与线程进程与线程w 线程线程有有运行、阻塞、就绪、结束状态。每个线程有自己的程运行、阻塞、就绪、结束状态。每个线程有自己的程序计数器和堆栈。像进程一样共享处理机。序计数器和堆栈。像进程一样共享处理机。w 同一进程中的线程不像不同进程之间完全是独立的，所有线同一进程中

3、的线程不像不同进程之间完全是独立的，所有线程有同一地址空间。线程共享进程所有拥有的资源。程有同一地址空间。线程共享进程所有拥有的资源。每个线程的项目每个线程的项目 程序计数器程序计数器 堆栈堆栈 寄存器组寄存器组 子线程子线程 状态状态 每个进程的项目每个进程的项目 地址空间地址空间 全局变量全局变量 打开的文件打开的文件 子进程子进程 计时器计时器 标志标志 信号量信号量 计算信息计算信息 线程线程4.1.2 线程的用途线程的用途派遣者派遣者/工作者模型工作者模型w 某某一一个个线线程程作作为为派派遣遣者者，它它从从系系统统邮邮箱箱内内读读出出输输入入请请求求，然然后后检检查查请请求求，选选

4、择择一一个个空空闲闲的的工工作作者者线线程程去去处处理理它它。然然后后派派遣遣者唤醒睡眠的工作者。者唤醒睡眠的工作者。w 工工作作者者被被唤唤醒醒后后，它它检检查查共共享享块块缓缓冲冲区区是是否否可可以以满满足足这这个个请请求求。如如不不能能满满足足，给给磁磁盘盘发发送送消消息息，要要求求所所需需的的数数据据块块。且且进进入休眠状态等待磁盘操作的完成。入休眠状态等待磁盘操作的完成。文件服务器进文件服务器进程程派遣者线程派遣者线程工作者线程工作者线程共享块共享块 cache cache工作请求到达工作请求到达邮箱邮箱 线程线程4.1.2 线程的用途线程的用途团队模型团队模型w 所所有有线线程程都

5、都是是批批平平等等的的，每每个个都都获获得得和和处处理理自自己己的的请请求求。没没有派遣者。有派遣者。w 如如果果工工作作来来了了不不能能处处理理，尤尤其其是是如如果果每每个个线线程程用用来来处处理理一一种种特特殊殊的的工工作作，可可以以维维护护一一个个队队列列，挂挂起起的的作作业业保保存存在在作作业业队队列列中。线程在察看系统信箱前先察看作业队列。中。线程在察看系统信箱前先察看作业队列。邮箱邮箱 线程线程4.1.2 线程的用途线程的用途管道线模型管道线模型w 这这种种模模型型中中第第一一个个线线程程产产生生一一些些数数据据传传给给下下一一个个线线程程去去处处理理。数数据据持持续续从从一一个个

6、线线程程传传到到另另一一个个线线程程，经经过过的的每每一一个个线线程程都都进进行处理。（生产者行处理。（生产者-消费者问题）消费者问题）邮箱邮箱内核内核 线程线程4.1.3 线程包的设计问题线程包的设计问题线程包设计线程包设计w 与线程相关的用户可得的原语集叫作线程包。与线程相关的用户可得的原语集叫作线程包。w 线程管理：线程管理：静静态态多多线线程程：当当程程序序编编写写或或被被编编译译时时就就要要决决定定选选择择多多少少个个线线程程。每每个个线线程程分分配配一一个个固固定定堆堆栈栈。这这种种方方法法简简单单，但但不灵活。不灵活。动动态态多多线线程程：允允许许线线程程在在运运行行过过程程中中

7、动动态态的的创创建建和和回回收收。这这种种模模型型中中进进程程以以一一个个线线程程开开始始运运行行，但但能能根根据据需需要要创创建建多个线程，该线程完成后可以退出。多个线程，该线程完成后可以退出。w 线线程程结结束束：当当一一个个线线程程完完成成它它自自己己的的工工作作时时，可可以以自自己己退退出出，或者被外界中止。或者被外界中止。线程线程4.1.3 线程包的设计问题线程包的设计问题线程包设计线程包设计w 共享问题共享问题互斥体互斥体 互互斥斥体体也也是是一一种种消消耗耗信信号号量量。互互斥斥体体总总是是处处于于两两种种状状态态：打打开开和和锁住。互斥体定义了两种操作锁住。互斥体定义了两种操作

8、:一种是加锁操作，一种是开锁操作。一种是加锁操作，一种是开锁操作。如如果果互互斥斥体体处处于于打打开开状状态态，它它将将仅仅仅仅用用一一个个原原子子操操作作锁锁住住互互斥斥体体。如果一个线程要给一个已经锁住的互斥体加锁则它将被阻塞。如果一个线程要给一个已经锁住的互斥体加锁则它将被阻塞。开开锁锁操操作作是是打打开开互互斥斥体体。如如果果一一个个或或多多个个线线程程由由于于互互斥斥体体被被锁锁住住而等待，实际上只有一个被开锁，其余的继续等待。而等待，实际上只有一个被开锁，其余的继续等待。试试锁锁（trylocktrylock）：尝尝试试锁锁住住互互斥斥体体，如如果果互互斥斥体体是是打打开开的的，则

9、则返返回回成成功功的的状状态态标标识识码码。反反之之，试试锁锁不不会会阻阻塞塞线线程程，而而是是返返回回失失败败状态的标识码。状态的标识码。线程线程4.1.3 线程包的设计问题线程包的设计问题线程包设计线程包设计w 共享问题共享问题条件变量条件变量 每每一一条条条条件件变变量量通通常常在在创创建建时时与与一一个个互互斥斥体体相相关关联联。互互斥斥体体与与条条件件变变量量的的区区别别在在于于互互斥斥体体用用于于短短期期加加锁锁，以以监监视视进进入入临界区。而条件变量是用于长时间等待直到资源可用为止。临界区。而条件变量是用于长时间等待直到资源可用为止。lock mutex;lock mutex C

10、heck data structures mark resourse as free While(resourse busy)unlock mutex;Wait(condition variable);wakeup(condition variable);Mark resourse as busy;unlock mutex;wakeup唤唤醒醒在在特特定定条条件件变变量量上上等等待待的的一一个个或或所所有有的的线线程。程。线程线程4.1.3 线程包的设计问题线程包的设计问题线程包设计线程包设计w 共享问题共享问题全局变量全局变量 使用全局变量线程之间的冲突使用全局变量线程之间的冲突（例子）（例

11、子）访问访问打开打开errno集集errno被检查被检查errno被覆盖被覆盖时间时间线程线程1线程线程2 线程线程4.1.3 线程包的设计问题线程包的设计问题线程包设计线程包设计w 共享问题共享问题全局变量全局变量 使用全局变量线程之间的冲突使用全局变量线程之间的冲突解决方案解决方案v 禁止使用全局变量禁止使用全局变量 v 给每个线程分配它自己的私有全局变量给每个线程分配它自己的私有全局变量线程线程1的代码的代码线程线程2的代码的代码线程线程1的堆栈的堆栈线程线程2的堆栈的堆栈线程线程1的全局变量的全局变量线程线程2的全局变量的全局变量 线程线程4.1.3 线程包的设计问题线程包的设计问题线

12、程包设计线程包设计w 共享问题共享问题全局变量全局变量 存取私有全局变量存取私有全局变量v 分分配配一一大大块块内内存存给给全全局局变变量量并并将将它它作作为为一一个个额额外外的的参参数传递给线程中的每一个过程。数传递给线程中的每一个过程。v 引引入入新新的的库库例例程程来来创创建建、设设置置和和读读取取这这些些线线程程全全局局变变量。量。create_global(“bufptrcreate_global(“bufptr”);”);set_global(“bufptr”,&bufset_global(“bufptr”,&buf););buftrbuftr=read_global(“bufpt

13、rread_global(“bufptr”);”);线程线程4.1.4 实现一个线程包实现一个线程包在用户空间中实现线程在用户空间中实现线程w 用户级线程包用户级线程包 结构结构运行期系统运行期系统内核内核用户空间用户空间内核空间内核空间线线程程0线线程程1线线程程2线线程程3线线程程4线线程程5 线程线程4.1.4 实现一个线程包实现一个线程包在用户空间中实现线程在用户空间中实现线程w 用户级线程包用户级线程包优点优点 在在不不支支持持线线程程的的操操作作系系统统中中实实现现；线线程程切切换换比比使使用用内内核核陷陷阱阱快快一一个个数数量量级级；允允许许每每个个进进程程有有自自己己定定制制的

14、的调调度度算算法。法。缺点缺点 阻塞调用怎样实现？阻塞调用怎样实现？系统调用改为非阻塞，使用系统调用改为非阻塞，使用SELECTSELECT 如何实现调度？如何实现调度？旋转锁，时钟信号中断；旋转锁，时钟信号中断；线程线程4.1.4 实现一个线程包实现一个线程包在内核中实现线程在内核中实现线程w 由内核管理的线程包由内核管理的线程包 结构结构内核内核用户空间用户空间内核空间内核空间线线程程0线线程程1线线程程2线线程程3线线程程4线线程程5 线程线程4.1.4 实现一个线程包实现一个线程包在内核中实现线程在内核中实现线程w 由内核管理的线程包由内核管理的线程包 当当一一个个线线程程想想去去创创

15、建建一一个个新新线线程程或或撤撤销销已已存存在在的的线线程程时时，它发出一个内核调用，由它完成创建和回收工作。它发出一个内核调用，由它完成创建和回收工作。内内核核中中每每个个进进程程都都有有一一张张包包含含线线程程信信息息（线线程程的的寄寄存存器器、状优先权等）的表。状优先权等）的表。优点：容易实现调度。优点：容易实现调度。缺点：系统开销大。缺点：系统开销大。w 共性问题共性问题 可重入问题可重入问题 线程线程4.1.4 实现一个线程包实现一个线程包调度者行为调度者行为w AndersonAnderson等等人人设设计计的的一一种种结结合合用用户户线线程程和和内内核核线线程程的的长长处处的的一

16、一种方法，称为调度者行为。种方法，称为调度者行为。目目标标：模模拟拟内内核核线线程程的的功功能能，像像用用户户空空间间内内实实现现的的线线程程包包一一样样有有更更好好的的性性能能和和有有更更大大的的灵灵活活性性。通通过过避避免免在在用用户户空空间间和内核空间之间不必要的转换来实现高效率。和内核空间之间不必要的转换来实现高效率。重重要要思思想想：内内核核分分配配一一定定数数量量的的虚虚拟拟处处理理机机给给每每个个进进程程，并且让（用户空间）运行期系统将线程分配给处理机。并且让（用户空间）运行期系统将线程分配给处理机。优优点点：效效率率，很很好好地地解解决决了了控控制制权权有有阻阻塞塞线线程程传传

17、递递给给非非阻阻塞线程。塞线程。缺点：可能产生死锁，与分层系统的内在结构相违背。缺点：可能产生死锁，与分层系统的内在结构相违背。线程线程4.1.5 线程和远程过程调用（线程和远程过程调用（RPC）主要思想主要思想w 当当服服务务器器线线程程S S启启动动时时，输输出出它它的的接接口口告告诉诉内内核核，这这个个接接口口定定了了哪哪一一个个过程可调用，调用的参数等。过程可调用，调用的参数等。w 当客户端线程当客户端线程C C启动时，从内核输入该接口，获得用于调用的特殊标识。启动时，从内核输入该接口，获得用于调用的特殊标识。w 在在客客户户端端使使用用内内存存映映像像，同同一一台台机机器器上上的的R

18、PCRPC能能很很快快完完成成。在在服服务务器器，使用弹出线程，不会因等待新任务而阻塞。使用弹出线程，不会因等待新任务而阻塞。M 将进入的消息映射到将进入的消息映射到线程的地址空间线程的地址空间 当消息到达时创建一当消息到达时创建一个新线程处理它个新线程处理它进入消息进入消息网络网络 系统模型系统模型讨论的问题讨论的问题w 分分布布式式系系统统中中处处理理机机的的组组织织方方式式。介介绍绍两两种种主主要要的的模模型型：工工作作站模型和处理机池模型以及混合模型。站模型和处理机池模型以及混合模型。工作站模型工作站模型w 系系统统是是由由分分布布在在建建筑筑物物中中或或校校园园中中并并由由高高速速局

19、局域域网网连连接接起起来来的的工作站（高性能终端个人计算机）构成的。工作站（高性能终端个人计算机）构成的。系统模型系统模型 工作站模型工作站模型无盘工作站：系统中工作站没有本地磁盘，称为无盘工作站。如无盘工作站：系统中工作站没有本地磁盘，称为无盘工作站。如果工作站是无盘的，文件系统必须由一个或多个远程文件服务器果工作站是无盘的，文件系统必须由一个或多个远程文件服务器实现。无盘工作站流行的原因：实现。无盘工作站流行的原因：w价价格格：买买大大量量的的带带有有低低速速小小容容量量磁磁盘盘的的工工作作站站比比买买一一台台或或两两台台配配置置有有高高速速、海海量量磁磁盘盘并并可可通通过过LAN访访问问

20、的的文文件件服服务务器器昂昂贵的多。贵的多。w容容易易维维护护：系系统统管管理理员员很很容容易易将将某某个个新新版版软软件件安安装装在在机机房房中中很少的几台文件服务器上。很少的几台文件服务器上。w磁盘有机风扇并产生噪音磁盘有机风扇并产生噪音w对对称称性性和和灵灵活活性性：由由于于所所有有的的文文件件都都在在文文件件服服务务器器上上，各各个个无盘工作站其实是一样的。无盘工作站其实是一样的。系统模型系统模型 工作站模型工作站模型有盘工作站：系统中工作站有本地磁盘，称为有盘工作站。当工有盘工作站：系统中工作站有本地磁盘，称为有盘工作站。当工作站有私人磁盘时，这些磁盘至少能以下列四种方式使用：作站有

21、私人磁盘时，这些磁盘至少能以下列四种方式使用：w分页和临时文件：用于分页和存储临时的、不能共享的、并分页和临时文件：用于分页和存储临时的、不能共享的、并在登陆会话结束后丢弃文件在登陆会话结束后丢弃文件w分页，临时文件和系统二进制文件：可以保存二进制程序分页，临时文件和系统二进制文件：可以保存二进制程序（编译程序、文本编辑程序等），当调用某一程序时，从本（编译程序、文本编辑程序等），当调用某一程序时，从本地加载，减少网络负载。地加载，减少网络负载。w分页，临时文件，系统二进制文件和文件缓存：用户能从文分页，临时文件，系统二进制文件和文件缓存：用户能从文件服务器下载文件到本地磁盘上，在本地读写这些

22、文件，然件服务器下载文件到本地磁盘上，在本地读写这些文件，然后在登陆会话结束之前上载修改后的文件。后在登陆会话结束之前上载修改后的文件。w完整的局部文件系统：每个机器都能有自己独立完备的文件完整的局部文件系统：每个机器都能有自己独立完备的文件系统。系统。系统模型系统模型 工作站模型工作站模型w 无盘模型和四种有盘工作站模型的比较无盘模型和四种有盘工作站模型的比较对对文文件件服服务务器器的的依依赖赖程程度度4.2 系统模型系统模型4.2.2 使用空闲工作站使用空闲工作站rsh程序：程序：Berkeley UNIX中的中的rsh程序，这个程序的调用方式是：程序，这个程序的调用方式是：rsh mac

23、hine command 机器名命令名机器名命令名w用户必须告诉使用哪台机器，将跟踪空闲机器的任务完全交用户必须告诉使用哪台机器，将跟踪空闲机器的任务完全交给了用户；给了用户；w程序在远程机器的环境中执行，而这种环境通常不同于本地程序在远程机器的环境中执行，而这种环境通常不同于本地机器的环境；机器的环境；w如果某用户登陆到一个有远程进程正在运行的机器上，要么如果某用户登陆到一个有远程进程正在运行的机器上，要么忍受低性能，要么使用另一台机器。忍受低性能，要么使用另一台机器。rsh程序存在的缺陷：程序存在的缺陷：4.2 系统模型系统模型4.2.2 使用空闲工作站使用空闲工作站空闲工作站的研究集中解

24、决的问题空闲工作站的研究集中解决的问题w 怎么样找出一台空闲机器？怎么样找出一台空闲机器？v 服服务务器器驱驱动动：当当一一台台工工作作站站空空闲闲时时，向向注注册册文文件件注注册册声声明明其可用性。（单注册表或多注册表）其可用性。（单注册表或多注册表）4.2 系统模型系统模型4.2.2 使用空闲工作站使用空闲工作站空闲工作站的研究集中解决的问题空闲工作站的研究集中解决的问题w 怎么样找出一台空闲机器？怎么样找出一台空闲机器？v 客客户户端端驱驱动动：当当调调用用remoteremote时时，向向空空闲闲机机器器发发请请求求消消息息。当返回应答时，当返回应答时，remoteremote调用从中

25、选择一台并启动它。调用从中选择一台并启动它。v 优优化化方方法法：令令“空空闲闲”工工作作站站延延迟迟它它们们的的回回答答，并并使使这这些些延延迟迟与与工工作作站站当当前前的的负负载载呈呈正正比比。于于是是，负负载载最最轻轻的的工工作作站站的应答最先返回并被选择。的应答最先返回并被选择。4.2 系统模型系统模型4.2.2 使用空闲工作站使用空闲工作站空闲工作站的研究集中解决的问题空闲工作站的研究集中解决的问题w 远程进程怎么样透明的运行？远程进程怎么样透明的运行？v 设设置置环环境境：设设置置远远程程进进程程使使它它有有与与本本地地工工作作站站一一样样的的环环境境，如同样的文件系统，同样的工作

26、目录和同样的条件变量等等。如同样的文件系统，同样的工作目录和同样的条件变量等等。v 考考虑虑与与其其它它机机器器或或宿宿主主机机的的交交互互 ：如如程程序序在在运运行行后后执执行行系系统统调调用用readread。如如果果是是无无硬硬盘盘的的，则则向向相相应应的的文文件件服服务务器器发发送送请请求求；如如果果是是系系统统有有本本地地磁磁盘盘，且且每每一一个个都都有有完完整整的的系系统统，请求必须返回到宿主机上执行。请求必须返回到宿主机上执行。v 与时间相关的调用。与时间相关的调用。4.2 系统模型系统模型4.2.2 使用空闲工作站使用空闲工作站空闲工作站的研究集中解决的问题空闲工作站的研究集中

27、解决的问题w 如果（空闲）机器的主人回来重新使用它怎么办？如果（空闲）机器的主人回来重新使用它怎么办？v 什么也不做什么也不做v 杀杀掉掉正正在在进进入入的的进进程程。缺缺点点是是所所有有的的工工作作信信息息会会丢丢失失，并并且且可可能能造造成成文文件件系系统统的的混混乱乱状状态态。较较好好的的方方法法是是给给出出一一个个适适当的当的“警告警告”。v 将将这这个个进进程程移移植植到到另另一一台台机机器器上上去去（本本机机或或者者另另一一台台空空闲闲工工作作站站）。这这种种方方法法在在实实践践中中很很少少使使用用，因因为为实实际际的的机机制制相相当复杂。当复杂。4.2 系统模型系统模型4.2.3

28、 处理机池模型处理机池模型当可以提供相当于用户十倍至百倍数量的当可以提供相当于用户十倍至百倍数量的CPUCPU时，如何处理。时，如何处理。建造处理机池（建造处理机池（processor poolprocessor pool）在在机机柜柜中中放放满满CPUCPU，可可以以根根据据需需要要动动态态地地分分配配给给用用户户。处处理理机机池模型如下图所示：池模型如下图所示：4.2 系统模型系统模型4.2.3 处理机池模型处理机池模型基本思想：基本思想：将所有的计算能力转变为能够动态访问的将所有的计算能力转变为能够动态访问的“空闲工作站空闲工作站”，用户，用户可以在短时间内分配到它们所需要数量的可以在短

29、时间内分配到它们所需要数量的CPUCPU。用户使用完毕后，用户使用完毕后，释放这些释放这些CPUCPU返回处理机池中供其它用户使用。返回处理机池中供其它用户使用。根据：根据：排队论：用一个是小系统功能排队论：用一个是小系统功能n n倍的大系统来代替倍的大系统来代替n n个独立的小系个独立的小系统的资源可以把平均响应时间减少为原来的统的资源可以把平均响应时间减少为原来的1/1/n n。计算机计算机完成工作完成工作输入队列输入队列 系统每秒能处理系统每秒能处理个请求个请求 用户每秒共产生用户每秒共产生个请求个请求4.2 系统模型系统模型4.2.4 混合模型混合模型基本思想：基本思想：提供给每个用户

30、一个私有工作站并附加有处理机池。提供给每个用户一个私有工作站并附加有处理机池。该方法的开销比单纯的工作站模型或单纯的处理机池模型更加昂该方法的开销比单纯的工作站模型或单纯的处理机池模型更加昂贵，但是综合了两者的优点。贵，但是综合了两者的优点。为了保证响应时间，交互式的工作在工作站上运行。所有非交互为了保证响应时间，交互式的工作在工作站上运行。所有非交互式进程运行在处理机池中。式进程运行在处理机池中。优点：快速的交互响应、有效的资源利用和简单的设计。优点：快速的交互响应、有效的资源利用和简单的设计。处理机分配处理机分配4.3.1 分配模型分配模型两个假设两个假设 所有的处理机都是一样的：所有的处

31、理机都是一样的：几乎所有的模型都假设所有的计算几乎所有的模型都假设所有的计算机都是一样的，或至少是代码兼容的，至多在速度上有所不同。机都是一样的，或至少是代码兼容的，至多在速度上有所不同。系统是完全连接的：即每台处理机都能与其它的任何一台处理系统是完全连接的：即每台处理机都能与其它的任何一台处理机进行通信。机进行通信。处理机分配策略的种类处理机分配策略的种类 不可迁移的：当创建一个进程时，系统就决定为该进程分配哪不可迁移的：当创建一个进程时，系统就决定为该进程分配哪台处理机。一旦分配完毕，进程将一直在这个处理机上运行，直台处理机。一旦分配完毕，进程将一直在这个处理机上运行，直到结束。到结束。可

32、迁移的：已经开始运行的进程可迁移到别的处理机上继续运可迁移的：已经开始运行的进程可迁移到别的处理机上继续运行。提供了更好的负载均衡。行。提供了更好的负载均衡。处理机分配处理机分配4.3.1 分配模型分配模型处理机分配算法优化处理机分配算法优化 CPUCPU的利用率最大化：尽可能减少的利用率最大化：尽可能减少CPUCPU的空闲时间的空闲时间 平均响应时间最小化平均响应时间最小化5秒队列秒队列没有没有队列队列 处理机处理机1 10MIPS 处理机处理机2 100MIPSA（1亿条指令）亿条指令）B（3亿条指令）亿条指令）10 秒秒30 秒秒6 秒秒8 秒秒每个进程在每个处理机上的响应时间每个进程在

33、每个处理机上的响应时间w处处理理机机1运运行行进进程程A，处处理理机机2运运行行进进程程B的的平平 均均 响响 应应 时时 间间 为为（10+8）/2=9秒秒w处处理理机机处处理理机机1运运行行进进程程B，处处理理机机2运运行行进进程程A的的平平均均响响应应时时间间为为（30+6）/2=18秒秒 处理机分配处理机分配4.3.1 分配模型分配模型处理机分配算法优化处理机分配算法优化 最小化响应率最小化响应率 w响应率是在一台机器上运行一个进程的时间除以这个进程在响应率是在一台机器上运行一个进程的时间除以这个进程在一个无负载的标准处理机上运行时应该花的时间。一个无负载的标准处理机上运行时应该花的时

34、间。w响应率是一个比响应时间更加有效的参数，它考虑了大作业响应率是一个比响应时间更加有效的参数，它考虑了大作业会比小作业花更多的时间。会比小作业花更多的时间。例子：一个例子：一个1 1秒的任务花了秒的任务花了5 5秒时间完成，秒时间完成，1 1个一分钟的任务花个一分钟的任务花 了了7070秒完成。秒完成。显然，按响应时间前者好；按响应率后者好些！显然，按响应时间前者好；按响应率后者好些！处理机分配处理机分配4.3.2 处理机分配算法的设计问题处理机分配算法的设计问题处理机分配算法设计者要考虑的问题包括以下五个方面：处理机分配算法设计者要考虑的问题包括以下五个方面：确定性与启发性（试探性）算法确

35、定性与启发性（试探性）算法w 确确定定性性算算法法适适用用于于当当进进程程的的所所有有行行为为都都是是事事先先知知道道的的情情况况。或者是可以得到一个合理的近似，如银行、航空定票系统。或者是可以得到一个合理的近似，如银行、航空定票系统。w 如如果果系系统统的的负负载载是是完完全全不不可可预预测测的的，处处理理机机分分配配算算法法不不能能用用数数学学的的、确确定定性性的的算算法法来来实实现现，而而只只能能使使用用特特别别的的启启发发性性（试探性）算法。（试探性）算法。集中式与分布式算法集中式与分布式算法w 把把所所有有的的信信息息集集中中到到一一个个地地点点便便于于作作出出更更好好的的决决定定，

36、但但是是中心机器负载过重。倾向于采用分布式算法。中心机器负载过重。倾向于采用分布式算法。处理机分配处理机分配4.3.2 处理机分配算法的设计问题处理机分配算法的设计问题处理机分配算法设计者要考虑的问题包括以下五个方面：处理机分配算法设计者要考虑的问题包括以下五个方面：最优与次优算法最优与次优算法w 得得到到最最优优解解比比次次优优解解付付出出的的代代价价大大很很多多。因因为为要要搜搜集集更更多多的的信息，并进行全面的处理。信息，并进行全面的处理。w 大大多多数数分分布布式式系系统统目目标标定定位位在在启启发发性性的的、分分布布式式的的、次次优优的的解决方案上。解决方案上。本地与全局算法本地与全

37、局算法w 是是否否根根据据本本地地信信息息决决定定转转移移策策略略。本本地地算算法法认认为为如如果果机机器器的的负载低于某个值就让该进程在这台机器上运行，否则迁移。负载低于某个值就让该进程在这台机器上运行，否则迁移。w 全全局局算算法法认认为为收收集集全全局局信信息息，看看看看其其它它机机器器的的负负载载后后再再决决定定是否在本机上运行该进程。是否在本机上运行该进程。处理机分配处理机分配4.3.2 处理机分配算法的设计问题处理机分配算法的设计问题处理机分配算法设计者要考虑的问题包括以下五个方面：处理机分配算法设计者要考虑的问题包括以下五个方面：发送者发起与接收者发起算法发送者发起与接收者发起算

38、法w 当当定定位位策策略略需需要要别别处处的的负负载载信信息息来来对对进进程程传传输输到到何何处处做做出出决决定定时时，这这个个信信息息可可以以通通过过两两种种方方法法传传递递：发发送送者者发发起起和和接接收收者者启动。启动。需要需要CPU周周期期？需要帮助？需要帮助？机器判定它的负担太重机器判定它的负担太重机器宣告它可被使用机器宣告它可被使用请求帮助请求帮助 请执行一个进请执行一个进程吧程吧 请完成一个工请完成一个工作吧作吧 此机器负担太此机器负担太重了重了我厌烦我厌烦了了 我无事我无事可做可做 今晚我空今晚我空闲闲求助求助 处理机分配处理机分配4.3.3 处理机分配算法的实现问题处理机分配

39、算法的实现问题处理机分配算法实现方面要考虑的问题处理机分配算法实现方面要考虑的问题 如何计算负载如何计算负载w 计计算算每每台台机机器器上上的的进进程程数数，并并将将它它作作为为负负载载情情况况；只只对对处处于于运行或就绪状态的进程计数。运行或就绪状态的进程计数。w 测量测量CPUCPU的利用率的利用率 如何处理额外开销如何处理额外开销w 许许多多理理论论上上的的处处理理机机分分配配算算法法都都忽忽略略了了测测量量处处理理机机搜搜集集信信息息和转移进程的额外开销。和转移进程的额外开销。w 一一个个好好的的算算法法应应考考虑虑算算法法本本身身所所占占用用的的CPUCPU时时间间、内内存存的的使使

40、用及网络带宽等等。用及网络带宽等等。处理机分配处理机分配4.3.3 处理机分配算法的实现问题处理机分配算法的实现问题处理机分配算法实现方面要考虑的问题处理机分配算法实现方面要考虑的问题 复杂性复杂性w 应应考考虑虑软软件件的的复复杂杂性性对对系系统统的的性性能能、正正确确性性和和健健壮壮性性产产生生的的影响。影响。例例如如：EagerEager等等人人的的三三个个算算法法（如如何何定定位位远远程程机机器器以以进进行行进进程程转移）转移）算算法法1 1：随随机机选选择择，如如果果选选择择的的机机器器仍仍然然过过载载，继继续续随随机机选选择，直到找到轻载机器或者计数器溢出。择，直到找到轻载机器或者

41、计数器溢出。算法算法2 2：随机选择一台机器，然后向它发出询问。：随机选择一台机器，然后向它发出询问。算算法法3 3：询询问问K K台台机机器器，确确定定它它们们的的确确切切负负载载情情况况。将将新新进进程程传送到负载最小的那台机器上。传送到负载最小的那台机器上。处理机分配处理机分配4.3.3 处理机分配算法的实现问题处理机分配算法的实现问题处理机分配算法实现方面要考虑的问题处理机分配算法实现方面要考虑的问题 复杂性复杂性w 结结论论：如如果果使使用用一一个个简简单单的的算算法法获获益益接接近近于于使使用用昂昂贵贵并并复复杂杂得多的算法所带来的收益，那么应采用简单的算法。得多的算法所带来的收益

42、，那么应采用简单的算法。稳定性稳定性w 由由于于不不同同的的机机器器都都在在异异步步的的运运行行它它们们的的算算法法，所所以以整整个个系系统统很少是平衡的。很少是平衡的。w 系统信息不全面。非平衡的系统环境造成了不稳定问题。系统信息不全面。非平衡的系统环境造成了不稳定问题。处理机分配处理机分配4.3.4 处理机分配算法举例处理机分配算法举例图论确定性算法图论确定性算法 算法要求进程知道它所要求的算法要求进程知道它所要求的CPUCPU和内存要求，并且知道系统中和内存要求，并且知道系统中每对进程之间要求的平均通信量。每对进程之间要求的平均通信量。如果系统的如果系统的CPUCPU数量数量k k小于进

43、程数，则将多个进程指派到同一个小于进程数，则将多个进程指派到同一个CPUCPU上。算法的思想是使这种指派能够使网络的通信量最小化。上。算法的思想是使这种指派能够使网络的通信量最小化。寻找紧耦合的聚寻找紧耦合的聚集，这些聚集之间很集，这些聚集之间很少相互作用少相互作用 处理机分配处理机分配4.3.4 处理机分配算法举例处理机分配算法举例一个集中式的算法一个集中式的算法 算法中有一个协调者，保存一张使用情况表。每个工作站在表中算法中有一个协调者，保存一张使用情况表。每个工作站在表中都有一个条目，初始值为都有一个条目，初始值为0 0。使用情况表中的记录值可以是正数、使用情况表中的记录值可以是正数、0

44、 0或是负数。正数表示用户或是负数。正数表示用户纯粹在使用系统资源。负数表示用户需要系统资源，纯粹在使用系统资源。负数表示用户需要系统资源，0 0 介于中间。介于中间。处理机分配处理机分配4.3.4 处理机分配算法举例处理机分配算法举例层次式的算法（适应大型系统）层次式的算法（适应大型系统）将所有的处理机以一种与物理网络结构无关的方式组织成一个逻将所有的处理机以一种与物理网络结构无关的方式组织成一个逻辑分层结构。一些机器是工作者，一些是管理者。辑分层结构。一些机器是工作者，一些是管理者。算法具有自我修复能力，能够经受无论是工作者还是管理者的突算法具有自我修复能力，能够经受无论是工作者还是管理者

45、的突发崩溃，而不会造成长期影响。发崩溃，而不会造成长期影响。处理机分配处理机分配4.3.4 处理机分配算法举例处理机分配算法举例发送者发起的分布式启发性算法发送者发起的分布式启发性算法 当当创创建建进进程程时时，创创建建进进程程的的机机器器将将对对一一个个随随机机选选取取的的机机器器发发送送询询问问其其负负载载是是否否低低于于某某个个阈阈值值。如如果果是是，则则发发送送进进程程。否否则则，选选择择另另一台机器继续询问。一台机器继续询问。如如果果在在N N次次询询问问内内还还没没有有找找到到合合适适的的机机器器，算算法法将将停停止止。新新进进程程将在创建它的机器上运行。将在创建它的机器上运行。在

46、在负负载载非非常常重重的的情情况况下下，所所有有机机器器都都会会不不停停的的毫毫无无意意义义的的向向其其它它机器发送询问。没有进程会减轻负载。引起系统大的额外开销。机器发送询问。没有进程会减轻负载。引起系统大的额外开销。处理机分配处理机分配4.3.4 处理机分配算法举例处理机分配算法举例接收者发起的分布式启发性算法接收者发起的分布式启发性算法 当当一一个个进进程程结结束束时时，系系统统将将检检查查自自己己是是否否有有足足够够的的工工作作可可做做。如如果果不不是是，将将随随机机向向一一台台机机器器申申请请工工作作。如如果果那那台台机机器器没没有有要要给给予予的的工作，系统将继续询问第二、三台机器

47、。工作，系统将继续询问第二、三台机器。如如果果连连续续N N次次都都没没有有申申请请到到工工作作，系系统统将将暂暂时时停停止止申申请请，开开始始处处理理系系统统队队列列中中一一个个等等待待的的进进程程。当当这这个个进进程程结结束束后后，开开始始下下一一轮轮的的申请。申请。该算法不会在系统非常繁忙的时候给系统增加额外的负载。该算法不会在系统非常繁忙的时候给系统增加额外的负载。处理机分配处理机分配4.3.4 处理机分配算法举例处理机分配算法举例投标算法投标算法 算算法法的的核核心心参参与与者者是是进进程程，为为了了完完成成工工作作，进进程程必必须须购购买买CPUCPU时时间，而间，而CPUCPU则

48、拍卖他的处理机周期给出价最高的买主。则拍卖他的处理机周期给出价最高的买主。每每个个处处理理机机在在一一个个公公共共可可读读文文件件中中公公布布它它们们的的近近似似价价格格。（根根据据处理机速度、内存容量、浮点运算能力等）处理机速度、内存容量、浮点运算能力等）进进程程通通过过计计算算从从处处理理机机集集中中选选择择一一个个可可以以支支付付的的起起的的，向向它它发发送送出价。出价。处处理理机机收收集集所所有有出出价价，然然后后作作出出决决定定，然然后后通通知知选选中中和和未未选选中中的的进程，并开始执行被选中的进程。进程，并开始执行被选中的进程。分布式系统的调度分布式系统的调度问题背景及解决方案问

49、题背景及解决方案 如如何何解解决决相相互互影影响响很很强强的的进进程程在在不不同同的的处处理理机机上上运运行行的的问问题题。看下面的例子：看下面的例子：容错容错4.5.1 组成部件错误组成部件错误由由于于一一些些部部件件错错误误导导致致计计算算机机系系统统失失效效，如如处处理理机机、存存储储器器、I/OI/O设设备、电缆或者软件等。错误分为三类：备、电缆或者软件等。错误分为三类：暂暂时时性性：暂暂时时性性错错误误发发生生一一次次就就消消失失，若若重重复复那那个个操操作作，错错误误就就会消失。会消失。间断性：间断性错误出现后，自动消失，然后再出现，如此反复。间断性：间断性错误出现后，自动消失，然

50、后再出现，如此反复。永久性：永久性错误会在错误部件修理好之前一直存在。永久性：永久性错误会在错误部件修理好之前一直存在。设计和构造容错系统的目标设计和构造容错系统的目标 即使在错误发生的情况下，整个系统也能保持正常运行。即使在错误发生的情况下，整个系统也能保持正常运行。容错容错4.5.2 系统失效系统失效在在重重要要的的分分布布式式系系统统中中，常常需需要要对对处处理理机机出出错错时时仍仍能能正正常常工工作作。有有两种处理机错误：两种处理机错误：Fail-silent错误错误 Byzantine错误错误对于对于Fail-silent错误，失效的处理机只是停止运行，对接下来的输入错误，失效的处理