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

《分布式系统的进程和处理机.ppt》由会员分享，可在线阅读，更多相关《分布式系统的进程和处理机.ppt（82页珍藏版）》请在三一办公上搜索。

1、第4章 分布式系统中的进程和处理机,4.1 线程,4.1.1 线程简介,进程与线程 进程是程序在一个数据集合上运行的过程，使系统进行资源分配和调度的一个独立单位。引入进程的目的是为了使多个程序并发执行，以提高资源利用率和系统吞吐量。线程：能够独立运行的基本单位，轻量级的进程，一个进程可以创建多个线程，有统一的地址空间。引入线程的目的是为了减少程序在并发执行时所付出的时空开销。,进程,线程,程序计数器,计算机,计算机,4.1 线程,4.1.1 线程简介,进程与线程 线程有运行、阻塞、就绪、结束状态。每个线程有自己的程序计数器和堆栈。像进程一样共享处理机。同一进程中的线程不像不同进程之间完全是独立

2、的，所有线程有同一地址空间。线程共享进程所有拥有的资源。,每个线程的项目 程序计数器 堆栈 寄存器组 子线程 状态,每个进程的项目 地址空间 全局变量 打开的文件 子进程 计时器 标志 信号量 计算信息,4.1 线程,4.1.2 线程的用途,派遣者/工作者模型 某一个线程作为派遣者，它从系统邮箱内读出输入请求，然后检查请求，选择一个空闲的工作者线程去处理它。然后派遣者唤醒睡眠的工作者。工作者被唤醒后，它检查共享块缓冲区是否可以满足这个请求。如不能满足，给磁盘发送消息，要求所需的数据块。且进入休眠状态等待磁盘操作的完成。,4.1 线程,4.1.2 线程的用途,团队模型 所有线程都是批平等的，每个

3、都获得和处理自己的请求。没有派遣者。如果工作来了不能处理，尤其是如果每个线程用来处理一种特殊的工作，可以维护一个队列，挂起的作业保存在作业队列中。线程在察看系统信箱前先察看作业队列。,4.1 线程,4.1.2 线程的用途,管道线模型 这种模型中第一个线程产生一些数据传给下一个线程去处理。数据持续从一个线程传到另一个线程，经过的每一个线程都进行处理。（生产者-消费者问题）,邮箱,内核,4.1 线程,4.1.3 线程包的设计问题,线程包设计 与线程相关的用户可得的原语集叫作线程包。线程管理：静态多线程：当程序编写或被编译时就要决定选择多少个线程。每个线程分配一个固定堆栈。这种方法简单，但不灵活。动

4、态多线程：允许线程在运行过程中动态的创建和回收。这种模型中进程以一个线程开始运行，但能根据需要创建多个线程，该线程完成后可以退出。线程结束：当一个线程完成它自己的工作时，可以自己退出，或者被外界中止。,4.1 线程,4.1.3 线程包的设计问题,线程包设计 共享问题互斥体 互斥体也是一种消耗信号量。互斥体总是处于两种状态：打开和锁住。互斥体定义了两种操作:一种是加锁操作，一种是开锁操作。如果互斥体处于打开状态，它将仅仅用一个原子操作锁住互斥体。如果一个线程要给一个已经锁住的互斥体加锁则它将被阻塞。开锁操作是打开互斥体。如果一个或多个线程由于互斥体被锁住而等待，实际上只有一个被开锁，其余的继续等

5、待。试锁（trylock）：尝试锁住互斥体，如果互斥体是打开的，则返回成功的状态标识码。反之，试锁不会阻塞线程，而是返回失败状态的标识码。,4.1 线程,4.1.3 线程包的设计问题,线程包设计 共享问题条件变量 每一条条件变量通常在创建时与一个互斥体相关联。互斥体与条件变量的区别在于互斥体用于短期加锁，以监视进入临界区。而条件变量是用于长时间等待直到资源可用为止。,lock mutex;lock mutex Check data structures mark resourse as free While(resourse busy)unlock mutex;Wait(condition v

6、ariable);wakeup(condition variable);Mark resourse as busy;unlock mutex;,wakeup唤醒在特定条件变量上等待的一个或所有的线程。,4.1 线程,4.1.3 线程包的设计问题,线程包设计 共享问题全局变量 使用全局变量线程之间的冲突（例子）,4.1 线程,4.1.3 线程包的设计问题,线程包设计 共享问题全局变量 使用全局变量线程之间的冲突解决方案 禁止使用全局变量 给每个线程分配它自己的私有全局变量,4.1 线程,4.1.3 线程包的设计问题,线程包设计 共享问题全局变量 存取私有全局变量 分配一大块内存给全局变量并将它作

7、为一个额外的参数传递给线程中的每一个过程。引入新的库例程来创建、设置和读取这些线程全局变量。create_global(“bufptr”);set_global(“bufptr”,4.1 线程,4.1.4 实现一个线程包,在用户空间中实现线程 用户级线程包 结构,4.1 线程,4.1.4 实现一个线程包,在用户空间中实现线程 用户级线程包优点 在不支持线程的操作系统中实现；线程切换比使用内核陷阱快一个数量级；允许每个进程有自己定制的调度算法。缺点 阻塞调用怎样实现？系统调用改为非阻塞，使用SELECT 如何实现调度？旋转锁，时钟信号中断；,4.1 线程,4.1.4 实现一个线程包,在内核中实现

8、线程 由内核管理的线程包 结构,4.1 线程,4.1.4 实现一个线程包,在内核中实现线程 由内核管理的线程包 当一个线程想去创建一个新线程或撤销已存在的线程时，它发出一个内核调用，由它完成创建和回收工作。内核中每个进程都有一张包含线程信息（线程的寄存器、状优先权等）的表。优点：容易实现调度。缺点：系统开销大。共性问题 可重入问题,4.1 线程,4.1.4 实现一个线程包,调度者行为 Anderson等人设计的一种结合用户线程和内核线程的长处的一种方法，称为调度者行为。目标：模拟内核线程的功能，像用户空间内实现的线程包一样有更好的性能和有更大的灵活性。通过避免在用户空间和内核空间之间不必要的转

9、换来实现高效率。重要思想：内核分配一定数量的虚拟处理机给每个进程，并且让（用户空间）运行期系统将线程分配给处理机。优点：效率，很好地解决了控制权有阻塞线程传递给非阻塞线程。缺点：可能产生死锁，与分层系统的内在结构相违背。,4.1 线程,4.1.5 线程和远程过程调用（RPC）,主要思想 当服务器线程S启动时，输出它的接口告诉内核，这个接口定了哪一个过程可调用，调用的参数等。当客户端线程C启动时，从内核输入该接口，获得用于调用的特殊标识。在客户端使用内存映像，同一台机器上的RPC能很快完成。在服务器，使用弹出线程，不会因等待新任务而阻塞。,4.2 系统模型,讨论的问题 分布式系统中处理机的组织方

10、式。介绍两种主要的模型：工作站模型和处理机池模型以及混合模型。工作站模型 系统是由分布在建筑物中或校园中并由高速局域网连接起来的工作站（高性能终端个人计算机）构成的。,4.2 系统模型,工作站模型,无盘工作站：系统中工作站没有本地磁盘，称为无盘工作站。如果工作站是无盘的，文件系统必须由一个或多个远程文件服务器实现。无盘工作站流行的原因：,价格：买大量的带有低速小容量磁盘的工作站比买一台或两台配置有高速、海量磁盘并可通过LAN访问的文件服务器昂贵的多。容易维护：系统管理员很容易将某个新版软件安装在机房中很少的几台文件服务器上。磁盘有机风扇并产生噪音对称性和灵活性：由于所有的文件都在文件服务器上，

11、各个无盘工作站其实是一样的。,4.2 系统模型,工作站模型,有盘工作站：系统中工作站有本地磁盘，称为有盘工作站。当工作站有私人磁盘时，这些磁盘至少能以下列四种方式使用：,分页和临时文件：用于分页和存储临时的、不能共享的、并在登陆会话结束后丢弃文件分页，临时文件和系统二进制文件：可以保存二进制程序（编译程序、文本编辑程序等），当调用某一程序时，从本地加载，减少网络负载。分页，临时文件，系统二进制文件和文件缓存：用户能从文件服务器下载文件到本地磁盘上，在本地读写这些文件，然后在登陆会话结束之前上载修改后的文件。完整的局部文件系统：每个机器都能有自己独立完备的文件系统。,4.2 系统模型,工作站模型

12、 无盘模型和四种有盘工作站模型的比较,对文件服务器的依赖程度,4.2 系统模型,4.2.2 使用空闲工作站,rsh程序：Berkeley UNIX中的rsh程序，这个程序的调用方式是：rsh machine mand 机器名命令名,用户必须告诉使用哪台机器，将跟踪空闲机器的任务完全交给了用户；程序在远程机器的环境中执行，而这种环境通常不同于本地机器的环境；如果某用户登陆到一个有远程进程正在运行的机器上，要么忍受低性能，要么使用另一台机器。,rsh程序存在的缺陷：,4.2 系统模型,4.2.2 使用空闲工作站,空闲工作站的研究集中解决的问题 怎么样找出一台空闲机器？服务器驱动：当一台工作站空闲时

13、，向注册文件注册声明其可用性。（单注册表或多注册表）,4.2 系统模型,4.2.2 使用空闲工作站,空闲工作站的研究集中解决的问题 怎么样找出一台空闲机器？客户端驱动：当调用remote时，向空闲机器发请求消息。当返回应答时，remote调用从中选择一台并启动它。优化方法：令“空闲”工作站延迟它们的回答，并使这些延迟与工作站当前的负载呈正比。于是，负载最轻的工作站的应答最先返回并被选择。,4.2 系统模型,4.2.2 使用空闲工作站,空闲工作站的研究集中解决的问题 远程进程怎么样透明的运行？设置环境：设置远程进程使它有与本地工作站一样的环境，如同样的文件系统，同样的工作目录和同样的条件变量等等

14、。考虑与其它机器或宿主机的交互：如程序在运行后执行系统调用read。如果是无硬盘的，则向相应的文件服务器发送请求；如果是系统有本地磁盘，且每一个都有完整的系统，请求必须返回到宿主机上执行。与时间相关的调用。,4.2 系统模型,4.2.2 使用空闲工作站,空闲工作站的研究集中解决的问题 如果（空闲）机器的主人回来重新使用它怎么办？什么也不做 杀掉正在进入的进程。缺点是所有的工作信息会丢失，并且可能造成文件系统的混乱状态。较好的方法是给出一个适当的“警告”。将这个进程移植到另一台机器上去（本机或者另一台空闲工作站）。这种方法在实践中很少使用，因为实际的机制相当复杂。,4.2 系统模型,4.2.3

15、处理机池模型,当可以提供相当于用户十倍至百倍数量的CPU时，如何处理。建造处理机池（processor pool）在机柜中放满CPU，可以根据需要动态地分配给用户。处理机池模型如下图所示：,4.2 系统模型,4.2.3 处理机池模型,基本思想：将所有的计算能力转变为能够动态访问的“空闲工作站”，用户可以在短时间内分配到它们所需要数量的CPU。用户使用完毕后，释放这些CPU返回处理机池中供其它用户使用。根据：排队论：用一个是小系统功能n倍的大系统来代替n个独立的小系统的资源可以把平均响应时间减少为原来的1/n。,4.2 系统模型,4.2.4 混合模型,基本思想：提供给每个用户一个私有工作站并附加

16、有处理机池。该方法的开销比单纯的工作站模型或单纯的处理机池模型更加昂贵，但是综合了两者的优点。为了保证响应时间，交互式的工作在工作站上运行。所有非交互式进程运行在处理机池中。优点：快速的交互响应、有效的资源利用和简单的设计。,4.3 处理机分配,4.3.1 分配模型,两个假设 所有的处理机都是一样的：几乎所有的模型都假设所有的计算机都是一样的，或至少是代码兼容的，至多在速度上有所不同。系统是完全连接的：即每台处理机都能与其它的任何一台处理机进行通信。处理机分配策略的种类 不可迁移的：当创建一个进程时，系统就决定为该进程分配哪台处理机。一旦分配完毕，进程将一直在这个处理机上运行，直到结束。可迁移

17、的：已经开始运行的进程可迁移到别的处理机上继续运行。提供了更好的负载均衡。,4.3 处理机分配,4.3.1 分配模型,处理机分配算法优化 CPU的利用率最大化：尽可能减少CPU的空闲时间 平均响应时间最小化,处理机1运行进程A，处理机2运行进程B的平均响应时间为（10+8）/2=9秒处理机处理机1运行进程B，处理机2运行进程A的平均响应时间为（30+6）/2=18秒,4.3 处理机分配,4.3.1 分配模型,处理机分配算法优化 最小化响应率,响应率是在一台机器上运行一个进程的时间除以这个进程在一个无负载的标准处理机上运行时应该花的时间。响应率是一个比响应时间更加有效的参数，它考虑了大作业会比小

18、作业花更多的时间。例子：一个1秒的任务花了5秒时间完成，1个一分钟的任务花 了70秒完成。显然，按响应时间前者好；按响应率后者好些！,4.3 处理机分配,4.3.2 处理机分配算法的设计问题,处理机分配算法设计者要考虑的问题包括以下五个方面：确定性与启发性（试探性）算法 确定性算法适用于当进程的所有行为都是事先知道的情况。或者是可以得到一个合理的近似，如银行、航空定票系统。如果系统的负载是完全不可预测的，处理机分配算法不能用数学的、确定性的算法来实现，而只能使用特别的启发性（试探性）算法。集中式与分布式算法 把所有的信息集中到一个地点便于作出更好的决定，但是中心机器负载过重。倾向于采用分布式算

19、法。,4.3 处理机分配,4.3.2 处理机分配算法的设计问题,处理机分配算法设计者要考虑的问题包括以下五个方面：最优与次优算法 得到最优解比次优解付出的代价大很多。因为要搜集更多的信息，并进行全面的处理。大多数分布式系统目标定位在启发性的、分布式的、次优的解决方案上。本地与全局算法 是否根据本地信息决定转移策略。本地算法认为如果机器的负载低于某个值就让该进程在这台机器上运行，否则迁移。全局算法认为收集全局信息，看看其它机器的负载后再决定是否在本机上运行该进程。,4.3 处理机分配,4.3.2 处理机分配算法的设计问题,处理机分配算法设计者要考虑的问题包括以下五个方面：发送者发起与接收者发起算

20、法 当定位策略需要别处的负载信息来对进程传输到何处做出决定时，这个信息可以通过两种方法传递：发送者发起和接收者启动。,4.3 处理机分配,4.3.3 处理机分配算法的实现问题,处理机分配算法实现方面要考虑的问题 如何计算负载 计算每台机器上的进程数，并将它作为负载情况；只对处于运行或就绪状态的进程计数。测量CPU的利用率 如何处理额外开销 许多理论上的处理机分配算法都忽略了测量处理机搜集信息和转移进程的额外开销。一个好的算法应考虑算法本身所占用的CPU时间、内存的使用及网络带宽等等。,4.3 处理机分配,4.3.3 处理机分配算法的实现问题,处理机分配算法实现方面要考虑的问题 复杂性 应考虑软

21、件的复杂性对系统的性能、正确性和健壮性产生的影响。例如：Eager等人的三个算法（如何定位远程机器以进行进程转移）算法1：随机选择，如果选择的机器仍然过载，继续随机选择，直到找到轻载机器或者计数器溢出。算法2：随机选择一台机器，然后向它发出询问。算法3：询问K台机器，确定它们的确切负载情况。将新进程传送到负载最小的那台机器上。,4.3 处理机分配,4.3.3 处理机分配算法的实现问题,处理机分配算法实现方面要考虑的问题 复杂性 结论：如果使用一个简单的算法获益接近于使用昂贵并复杂得多的算法所带来的收益，那么应采用简单的算法。稳定性 由于不同的机器都在异步的运行它们的算法，所以整个系统很少是平衡

22、的。系统信息不全面。非平衡的系统环境造成了不稳定问题。,4.3 处理机分配,4.3.4 处理机分配算法举例,图论确定性算法 算法要求进程知道它所要求的CPU和内存要求，并且知道系统中每对进程之间要求的平均通信量。如果系统的CPU数量k小于进程数，则将多个进程指派到同一个CPU上。算法的思想是使这种指派能够使网络的通信量最小化。,寻找紧耦合的聚集，这些聚集之间很少相互作用,4.3 处理机分配,4.3.4 处理机分配算法举例,一个集中式的算法 算法中有一个协调者，保存一张使用情况表。每个工作站在表中都有一个条目，初始值为0。使用情况表中的记录值可以是正数、0或是负数。正数表示用户纯粹在使用系统资源

23、。负数表示用户需要系统资源，0 介于中间。,4.3 处理机分配,4.3.4 处理机分配算法举例,层次式的算法（适应大型系统）将所有的处理机以一种与物理网络结构无关的方式组织成一个逻辑分层结构。一些机器是工作者，一些是管理者。算法具有自我修复能力，能够经受无论是工作者还是管理者的突发崩溃，而不会造成长期影响。,4.3 处理机分配,4.3.4 处理机分配算法举例,发送者发起的分布式启发性算法 当创建进程时，创建进程的机器将对一个随机选取的机器发送询问其负载是否低于某个阈值。如果是，则发送进程。否则，选择另一台机器继续询问。如果在N次询问内还没有找到合适的机器，算法将停止。新进程将在创建它的机器上运

24、行。在负载非常重的情况下，所有机器都会不停的毫无意义的向其它机器发送询问。没有进程会减轻负载。引起系统大的额外开销。,4.3 处理机分配,4.3.4 处理机分配算法举例,接收者发起的分布式启发性算法 当一个进程结束时，系统将检查自己是否有足够的工作可做。如果不是，将随机向一台机器申请工作。如果那台机器没有要给予的工作，系统将继续询问第二、三台机器。如果连续N次都没有申请到工作，系统将暂时停止申请，开始处理系统队列中一个等待的进程。当这个进程结束后，开始下一轮的申请。该算法不会在系统非常繁忙的时候给系统增加额外的负载。,4.3 处理机分配,4.3.4 处理机分配算法举例,投标算法 算法的核心参与

25、者是进程，为了完成工作，进程必须购买CPU时间，而CPU则拍卖他的处理机周期给出价最高的买主。每个处理机在一个公共可读文件中公布它们的近似价格。（根据处理机速度、内存容量、浮点运算能力等）进程通过计算从处理机集中选择一个可以支付的起的，向它发送出价。处理机收集所有出价，然后作出决定，然后通知选中和未选中的进程，并开始执行被选中的进程。,4.4 分布式系统的调度,问题背景及解决方案 如何解决相互影响很强的进程在不同的处理机上运行的问题。看下面的例子：,4.5 容错,4.5.1 组成部件错误,由于一些部件错误导致计算机系统失效，如处理机、存储器、I/O设备、电缆或者软件等。错误分为三类：暂时性：暂

26、时性错误发生一次就消失，若重复那个操作，错误就会消失。间断性：间断性错误出现后，自动消失，然后再出现，如此反复。永久性：永久性错误会在错误部件修理好之前一直存在。设计和构造容错系统的目标 即使在错误发生的情况下，整个系统也能保持正常运行。,4.5 容错,4.5.2 系统失效,在重要的分布式系统中，常需要对处理机出错时仍能正常工作。有两种处理机错误：Fail-silent错误 Byzantine错误对于Fail-silent错误，失效的处理机只是停止运行，对接下来的输入不作反应也不产生进一步的输出。Fail-stop错误对于Byzantine 错误，出错的处理机继续运行，产生问题的错误答案，并可

27、能和其它的出错的处理机一起“恶意”地工作，给人一种正常工作的假象。,4.5 容错,4.5.3 同步系统与异步系统,在容错系统的研究领域，若系统工作时总能在一个已知的限定时间内对一条消息进行响应，称之为同步。否则称之为异步。如果一个处理机发送消息，并知道若在限定时间T内没有回答表示接收者失效，他就能够采取正确的措施。如果不知道响应发生时间的上限，那么要判断接受者是否失效会成为一个问题。,4.5 容错,4.5.4 使用冗余,三类冗余技术：信息冗余：增加额外的数据位以使出错的数据完全恢复。时间冗余：动作执行后，必要时可再次执行。物理冗余：使用额外部件以使整个系统能容许一些部件的损失或失效。两种组织冗

28、余处理机的方法：主动复制和主机后备。两种方法都有如下的问题：需要复制的程度 没有错误时，平均情况和最坏情况下的性能 发生错误时，平均情况和最坏情况下的性能,4.5 容错,4.5.4 使用主动复制方法的容错,主动复制是使用物理冗余来提供容错的一种著名的技术。这种方法多年来也应用于电子电路的容错。,每个设备复制三次，每级电路都设置三个表决器，每个表决器都有三个输入和一个输出。若两个或三个输入相同，输出则等于输入。,4.5 容错,4.5.5 使用主动复制方法的容错,如果系统在k个部件出错时仍能达到系统的设计要求而正常工作，那么这个系统称为是k容错的。如果出错属于fail-slient型，那么有k+1

29、个这样的部件足以满足k容错的要求。若错误是Byzantine型的，至少需要2k+1个处理机才能达到k容错。原子广播问题：所有请求到达所有服务器的顺序都相同。对所有请求编号 Lamport逻辑时钟，为每条消息编上时间标签。,4.5 容错,4.5.6 使用主机后备的容错,基本思想：在任一时刻都有一台服务器是主机，它完成所有的工作。若这个主服务器失效了，后备的服务器将承担其任务。与主动复制相比，主机后备有两个主要优点：消息只发往一个服务器，不存在消息排序问题。实际应用中需要的机器少。任何时候只需一台主机和一台后备的机器即可。缺点是无法处理Byzantine错误,4.5 容错,4.5.6 使用主机后备

30、的容错,在RPC过程中，主机崩溃后产生情况如下：如果主机在执行任务前崩溃，则没有损失。客户端会超时重发直到连上后备机，任务只被执行一次。如果主机在执行任务后向后备机发送更新消息前崩溃，此时后备机接管，请求消息再次到来，则任务被执行2次。如果主机在后备机执行任务后自己发送响应消息前崩溃，则任务共被执行三次。一次主机完成，一次后备机完成，一次后备机接管时完成。如果请求消息带有序号，则可以减少任务执行次数。,4.5 容错,4.5.7 容错系统中的协同一致,处理机正常但通信线路可能丢失消息的情况：例子：两军问题：红军有5000人，驻扎于山谷。两队蓝军各3000人，驻扎于周围的山上。两队蓝军若能协同攻击

31、红色军队，将会获胜。若仅一支出击，将被屠杀。蓝军的目的是实现协同出击。问题：通过派遣信差。但是信差可能被红军俘虏！蓝一军：“我有一个计划，明天黎明一起出击！”蓝二军：“好主意，明天黎明见！”结论：对于无故障的处理机，在不可靠通信的情况下，达成协同一致是不可能的。可设某个协议使其在有限步内终止其达成一致。,4.5 容错,4.5.7 容错系统中的协同一致,通信正常但处理机出错的情况：例子：两军问题：红军驻扎在山谷，但附近山头上有n个蓝军，通信是安全的。但是蓝军中有m个叛徒，他们通过提供忠诚将军错误的消息来阻止忠诚将军们达成协同一致。忠诚的蓝军能达成协同一致吗？,4.5 容错,4.5.7 容错系统中

32、的协同一致,两军问题的Lamport解决方案：算法的工作条件是：n=4,m=1,1.每个将军发送消息给其它将军，声明自己真实的军队人数。将军1：1K 将军2：2K 将军3：x y z 将军4：4K,4.5 容错,4.5.7 容错系统中的协同一致,两军问题的Lamport解决方案：算法的工作条件是：n=4,m=1,2.把第一步声明的结果收集组成向量的形式。将军1:(1，2，x,4)将军2:(1，2，y,4)将军3:(1，2，3,4)将军4:(1，2，z,4),4.5 容错,4.5.7 容错系统中的协同一致,两军问题的Lamport解决方案：算法的工作条件是：n=4,m=1,3.每个将军将各自的向

33、量传递给其它每个将军。将军1：(1,2,y,4)将军：(1,2,x,4)(a,b,c,d)(e,f,g,h)(1,2,z,4)(1,2,z,4)将军4:(1,2,x,4)(1,2,y,4)(i,j,k,l),4.5 容错,4.5.7 容错系统中的协同一致,两军问题的Lamport解决方案：算法的工作条件是：n=4,m=1,4.每个将军检查所有接收向量的第i个元素。若某个值占多数，放入结果向量中，否则，标记为UNKNOWN,1.2.4 得到协同一致向量：（1，2，UNKNOWN，4），背叛者不能得偿所愿。,4.5 容错,4.5.7 容错系统中的协同一致,两个忠诚将军，一个叛变将军的情况：m=3，

34、n=1的情况：,将军1:(1,2,x)将军1 将军2 将军2:(1,2,y)(1,2,y)(1,2,x)将军3:(1,2,3)(a,b.c)(d,e,f),4.5 容错,4.5.7 容错系统中的协同一致,结论：在通信不正常的情况下，即使两个进程达成协同一致也是不可能的。在通信正常的情况下，由m个处理机出错的系统中，有2m+1个正常处理机时才可能。,4.6 实时分布式系统,4.6.1 什么是实时系统,当某个激励出现时，系统必须以一定的方式在限定的时间内响应它。若返回结果正确，但已经超时，系统也认为是失效的。例子：声音CD播放器包含一个CPU，它读出磁盘上的数据，并进行处理产生音乐。若使用相当于原

35、CPU 1/3速度的CPU，如果它以1/3的速度播放，声音将难以忍受！对时间的要求本质上是正确性要求的一个特定部分！激励可以是周期的、非周期的和突发的。,4.6 实时分布式系统,4.6.1 什么是实时系统,例子：三个周期性事件流和一个突发性事件的情况：,问题：对CPU而言，错过了事件B。因为当B发生时，它仍在处理A。解决方案：在每个实时设备前放置一个专用的微处理机。从而引发 了一个分布式实时系统。,4.6 实时分布式系统,4.6.1 什么是实时系统,分布式实时计算机系统,分布式实时计算机系统是一个由网络连接起来的一些计算机。其中一部分计算机与外部设备相连。这些计算机都有接收来自设备信号的传感器

36、和向它们发送信号的执行机构。,4.6 实时分布式系统,4.6.1 什么是实时系统,实时系统分类,根据时限的严格程度和超过限制时间的后果的严重性，通常将实时系统分成两类：,软实时系统 软实时系统意味着可以偶尔错过时限。例如电话交换机允许在超载情况下，每100000次中可有一次丢失或断线。硬实时系统 在硬实时系统中，不允许任何实时请求超过时限。介于中间 当超过时限时，必须结束当前的处理，但是其结果并不是致命的。,4.6 实时分布式系统,4.6.1 什么是实时系统,实时系统的三个误解,误解之一：实时系统就是用汇编代码来编写的驱动程序。在20世纪70年代对于一个只连接了少数几个设备的小型机的实时系统或

37、许正确，但现在的实时系统非常复杂，利用汇编语言编写驱动程序已不能胜任。误解之二：实时计算是快速计算 不是必要的。例如：天文望远镜。更关心的是精确性。误解之三：高速的计算机将使实时系统过时无用。高速的计算机只会激励人们构造在以前的发展水平之上的实时系统。,4.6 实时分布式系统,4.6.2 设计问题,时钟同步,在多计算机情况下，每台计算机都有自己的本地时钟，保持时间同步是一个关键的问题。（第3章）,事件触发系统与时间触发系统,事件触发系统 事件触发系统是中断驱动的。当一个重要的外部事件触发时，被传感器察觉到，并导致与传感器相连的CPU得到一个中断请求。存在的问题：当许多事件一次性发生时，在重载情

38、况下会失效。即难以处理事件风暴！,4.6 实时分布式系统,4.6.2 设计问题,事件触发系统与时间触发系统,时间触发系统 在这类系统中，每T毫秒产生一次时钟中断。在每一次时钟嘀答时，对选定的传感器进行采样，并且驱动特定的执行机构。即中断仅在时钟滴答时发生。存在的问题：T 难以选择。若T太小，系统将产生许多时钟中断，浪费大量的时间来响应他们。若T太大，严重的事件可能未被注意到。,4.6 实时分布式系统,4.6.2 设计问题,事件触发系统与时间触发系统区别,例子：电梯在60层楼，有人在1楼按下按钮。在100ms之后，另一人在100层上按下按钮。在事件触发系统，第一次按钮产生一次中断，电梯启动下行。

39、当第二个按下按钮的事件到来时，第二个事件被记录下来，电梯继续下行。在时间触发系统中，若它每500ms采样一次，若两次按下按钮事件都在一次采样周期中实现，控制器根据某个原则作出决定（如最近用户优先原则），电梯上行。不同点 事件触发的设计使得在低负载时会更快的响应，在高负载时会更加过载。时间触发相反，并且仅适用于相对静态环境。,4.6 实时分布式系统,4.6.2 设计问题,预知性,设计时应该清楚系统能够满足的所有时限，甚至是最大负载时限。,容错性,能同时处理最大量设备失效和最大量负载的情况。处理最大量设备失效：不能因为三个部件同时出错的可能性很小而忽略它，失效不总是独立的！处理最大量负载：系统最大

40、负载经常发生在系统中最大量设备失效时。因为系统通信量中许多是与报告失效有关的。可安全停机的系统：系统严重出错时，强制停止运行，不会产生危险。,4.6 实时分布式系统,4.6.2 设计问题,语言支持,虽然许多实时系统都是用像C一样的通用语言编写的，但专用的实时程序设计语言可能更有用。易于将一个工作作为一些短任务的集合。编译时能计算出每个任务的最大执行时间。（不允许while递归）处理自己时间的方法 有表达最小延迟和最大延迟的方法。能表示当期待的事件在限定时间内未发生时该做什么的方法 有处理周期性事件的方法 every(25msec),4.6 实时分布式系统,4.6.3 实时通信,实时分布式系统中

41、的通信,实时分布式系统中的通信与其它的分布式系统中的通信不同，预知性与确定性是实时系统成功的真正关键。处理机之间的通信是可预知的。以太网不能满足需求。令牌环LAN可以满足需求。假定环网中的k个机器每个在捕获令牌时最多可发送含n个字节的信包。这能保证一个紧急信包可在nk字节传送周期内到达系统的任何地方。这种上限正是实时分布式系统所需要的。令牌环也能处理多优先级系统的情况。即保证高优先级信包等待发送时，它将在它临近的任意低优先级的信包之前发送。,4.6 实时分布式系统,4.6.3 实时通信,实时分布式系统中的通信,时多路协议（TDMA）通信以固定大小的组织，每个祯含n个时限，每个时限被分配给一个处

42、理机。当一个处理机的时限到来时，它可进行发送信包。,4.6 实时分布式系统,4.6.3 实时通信,实时分布式系统中的通信,广域网上的实时分布式系统 系统中的通信是面向连接的，远距离机器之间建立一个实时连接。标准协议处理信包丢失的方法是设置一个定时器。如果定时器在信包确认消息收到之前走完，就重发信包。发送者的一个简单的解决办法是总是传输信包两次（或多次），如果可能的话最好是通过相互独立的连接。时间触发协议（TTP）TTP应用在 MARS实时系统中。,4.6 实时分布式系统,4.6.4 实时调度,实时系统任务调度,任务的特点：短任务、每个短任务有明确的功能和有限的运行时间，对某个激励的响应时间可能

43、需要多个任务来运行。并通常对他们有执行顺序上的限制。实时调度算法的特征 硬实时与软实时 硬实时算法必须保证所有时限都满足；软实时算法可忍受一种最大近似的方法。,4.6 实时分布式系统,4.6.4 实时调度,实时系统任务调度,实时调度算法的特征 抢占的与非抢占的 抢占式调度允许在更高优先级的任务到来时暂时挂起当前的任务，以后在没有更高优先级的任务要运行时恢复处理。非抢占式调度运行每个任务直至完成，即一旦一个任务启动后，它将占有处理机直到结束。动态的与静态的 动态算法是在运行期间进行调度。静态的调度算法是在运行前事先就调度好的。集中的与分散的,4.6 实时分布式系统,4.6.4 实时调度,动态调度

44、,比率单调算法 设计用来抢占式调度一个单一处理机上的没有顺序和互斥限制的周期性任务的。设计思想：事先给每个任务分配一个与其执行频率相等的优先级。运行时，调度程序选择优先级最高的任务运行。最早时限优先法 每当检测到一事件时，调度程序就将其加入等待任务队列中。这个等待队列根据这些任务的时限排序。调度程序从列表中选择第一个任务调度。,4.6 实时分布式系统,4.6.4 实时调度,动态调度,最小余度法 先计算出每个任务的剩余时间量，称为余度。即选择有最小余度的任务。上述算法常作为启发式算法。没有考虑到顺序和互斥的限制。这使得它们在理论上很有用，在实践中不那么有效。当事先可掌握有足够的信息时，通常使用静

45、态调度算法。,4.6 实时分布式系统,4.6.4 实时调度,静态调度,算法的输入包含了所有任务的列表以及它们各自的运行时间，目标是将任务分配到各个处理机，并对每一处理机给出所要运行任务的静态运行顺序。,4.6 实时分布式系统,4.6.4 实时调度,静态调度,两种可能的调度方法：不同处理机上的任务间的消息用箭头表示。同一机器上的任务间的消息在机器内部处理，没有标出。,1,2,3,4,5,6,7,8,9,10,响应,时间,激励,1,3,5,2,4,6,7,8,9,10,响应,时间,激励,A,A,B,B,（a）,（b）,4.6 实时分布式系统,4.6.4 实时调度,动态调度与静态调度的对比,静态适合时间触发系统的设计，动态调度适合事件触发系统的设计。在资源利用方面，动态调度比静态调度具有更大的潜力若给定足够的处理能力，静态系统可事先获得一个最优或次优的调度策略。,