分布式系统中的负载分配.ppt

基本概念 所谓负载是指处理机上的用户进程尚未完成的工作量。主要包括进程的计算开销和通信开销。在多处理机系统中，对节点机上系统资源的负载度量，称为负载指标。以向量形式表示的某一节点机的各项负载指标，称为负载向量，它描述的是某一节点机的负载情况。以矩阵形式表示的各节点机负载向量的集合，称为负载矩阵，用以描述整个系统的负载情况。 负载向量所描述的内容，是任务分配的依据，其定义必须准确、完备和有效。负载向量可以包括多种负载指标，例如：节点机就绪队列的长度，局部存储器空闲空间的容量，单位时间内进行系统功能调用的次数，单位时间内存储器页面的调入／调出次数，单位时间内CPU被占用的百分比，单位时间内磁盘的读／写次数等。大多数任务分配算法采用单个负载指标作为负载向量，其中选择节点机就绪队列长度的颇多。 负载平衡 为了描述节点机上负载的轻重程度，我们使用负载阀值进行衡量。负载阀值是节点机负载的界限值，其下界为T1，上界为T2，且T1≤T2。我们有如下的定义。 轻载：当节点机的负载小于T1时，该节点机为轻载； 重载：当节点机的负载大于T2时，该节点机为重载； 适载：当节点机负载大于T1而小于T2时，该节点机为适载； 空载：当节点机负载为0时，该节点机为空载。 负载平衡：是指系统中的所有处理机均处于适载状态。这是一种严格意义下的负载平衡。更广泛意义下的负载平衡应是系统中每个节点机都不是空载，或者当某个节点机为空载时，其它节点机均为空载或轻载。 动态负载平衡 负载分配算法可以分为静态负载分配算法和动态负载分配算法。静态负载分配算法是指在系统中进行任务分配时，根据各节点的负载情况决定给任务分配处理机。动态负载分配算法通过交换系统的状态信息来决定系统负载的分配。动态负载分配算法能适应系统负载的变化，比静态负载分配算法更灵活、更有效，但它以一定的系统开销为代价。 所谓动态负载平衡，是指系统根据其负载变化和进程的执行情况，自动实现进程从重载节点机到轻载节点机的迁移。重载节点机提供迁出进程，轻载节点机要求迁入进程。 在分布存储器结构多处理机系统中，各节点处理机缺乏对全局信息的了解，处理机间需要经常交换进程状态信息。这种交换可以按同步方式进行，也可以按异步方式进行。同步方式简单，控制方便，但同步时间间隔难以确定。若间隔偏小，则节点之间信息交换频繁，通信开销大，因此可能会抵销负载平衡所带来的并行处理效益，若间隔偏大，则达不到动态平衡负载的目的，在异步方式下，系统只有在某一事件触发下才能引起节点处理机间的信息交换。这里的触发事件较典型的有两种：某节点机负载过重和某节点机负载过轻。 动态负载平衡的几个策略（1） 动态负载平衡算法由以下四个策略组成： (1)迁移策略。当一个新任务在一个节点上产生时，如果它所在的节点机的负载超过了负载阀值的上界，则该节点机就是一个发送者，另一方面，一个节点机上的负载降到了阀值Tl(T2)以下，那么该节点就被认为是一个接收者。 (2)选择策略。一旦迁移策略确定了发送者和接收者之后，选择策略将用于从发送者那里选择哪些任务作为迁移对象。最简单的选择策略就是选择一个必威体育精装版产生的任务，在它未执行之前就迁移到接收者那里。选择一个迁移任务时，应考虑到由迁移所产生的开销要小，被迁移的任务应具有较长的生命期，否则迁移的开销将抵消性能的提高。被迁移的任务可以是未被启动执行的任务，也可以是正在运行的任务。 动态负载平衡的几个策略（2） (3)定位策略。一旦确定了一个节点机是发送者(或接收者)之后，定位策略负责为其寻找合适的搭档节点机。定位策略可有分布式和集中式两种。分布式定位策略采用轮询(Polling)方式寻找一个搭档机，也可以采用广播查询方式有哪些信誉好的足球投注网站任何可以进行分载的节点机。在集中式定位策略中，任何节点机都可向一个称为管理者的特殊节点机发出请求，由管理者确定一个进行分载的合适的节点机。 动态负载平衡的几个策略（3） (4)信息策略。它用于决定什么时候(When)，从什么地方(Where)搜集系统中其它节点机有关状态的什么(What)信息，即W3策略。信息策略有三种类型： 需求策略。仅当一个节点机成为一个发送者或接收者时，才去搜集其它节点机的状态信息。 周期策略。周期性地搜集各节点机的状态信息。 状态变化驱动策略。一旦一个节点机状态发生了一定程度的变化，它就把自身的状态信息广播出去。在集中式策略中，所有节点都向一个管理者发送状态信息；而在分布式策略中，各节点机向其它节点机广播自己的状态信息。 动态负载平衡算法的分类（1） ※典型的动态负载平衡算法有以下四类。 (1)发送者启动算法。 该算法由发送者来触发负载分配。当一个节点机成为一个发送者时，它主动寻找接收者来接收