分布式操作系统讲稿

分布式操作系统讲稿计算机09级陈欣冉概要内容时间导入关于分布式操作系统，可能我们之前有过了解，也知道一些关于分布式系统的知识，今天我们一起系统的学习一下分布式操作系统。今天的内容主要分为三大块，分别是分布式的相关概念，进程管理，资源管理。1分钟一、1、相关概念我们可以简单的认为，分布式计算机系统就是由几台计算机连成网络形成的那个整体。管理这些计算机的那个系统叫做分布式操作系统。与传统的集中式操作系统相比较，他们最大的区别就是，集中式操作系统管理的是一台计算机，而分布式操作系统管理的是一组计算机。分布式操作系统中一台计算机称为一个站点或一个结点。2、分布式操作系统的特征1、分布式操作系统的特征：（1）、分布性：至少有四类部件在物理上可能是分布的，包括硬件或处理的逻辑单元、数据、处理本身及控制。（2）、自治性：所有部件或资源都是高度自治的，它们具有独立执行任务的能力。（3）、透明性：分布式计算机系统要让用户使用起来像是一个“单计算机系统”，实现分布式系统以达到这一目标的技术称透明性，它是指用户只需要描述它要得到什么服务，而不必指明由哪些物理设备或逻辑部件提供这些服务，用户不必知道服务过程实现的细节，因此非常方便。比如在某个机器上的用户想要存取另一台机器上的资源，那用户不需要知道资源到底在哪台机器上，这也是分布式操作系统和网络操作系统最大的区别。（4）、统一性：各部件有自治性，但作为一个完整的分布式操作系统，在用户面前要有统一性。1分钟3、分布式操作系统的基本功能进程通信和资源共享可以保证整个分布式系统是一个整体；并行运算是分布式操作系统的一大优势；网络管理就像我们刚才说的，对用户具有透明性。2分钟二、进程管理1、处理器的分配（1）分配策略：不可迁移的：创建进程时，系统决定为该进程分配哪台处理机，一旦分配完毕，进程将一直在这台处理机上运行，直到结束。可迁移的：可以将已经运行的进程迁移到别的处理器上继续执行。金曦讲的计算模型，里面那些作业、进程、线程都是可迁移的。说明：可迁移策略能提供更好的负载平衡，但同时也增加了系统的复杂性，对系统的设计有很大的影响。（2）评价进程处理器分配算法：CPU利用率最大化是指尽可能的减少CPU的空闲时间，让每个CPU都在运行；响应时间是每个进程的等待时间加上运行时间；响应率是指一台机器上运行一个进程的时间除以这个进程在一个无负载的标准处理机上运行时应该花的时间。（3）目前的分配算法有：图论确定性分配算法、集中式分配算法、层次是分配算法、发布者/接收者发起的分布式启发性算法等等。2、进程的同步和互斥分布式系统中各计算机没有共享的内存区，导致进程间无法通过传统的公共变量，如信号量来进行通信。分布式进程同步比集中式进程同步复杂。由于进程分散在不同的计算机结点上，进程只能根据本地可用信息做出决策，并通过网络联系；由于系统中没有公共的时钟，进程间通过网络通信也会有延迟，不能保证资源管理者收到资源申请的顺序就是申请者请求资源的顺序。而所谓的进程同步与互斥，实质上是要求各个进程按照一定顺序使用资源或要求各进程按照一定的顺序执行。所以，分布式进程同步2分钟与互斥首先要解决对不同计算机中的事件的排序，然后再设计出性能优越的分布式同步算法。（首先要确定不同计算机中发生事件的先后顺序）集中式系统：系统中有统一的公共存储器和公共时钟，分布式系统中没有，所以很难确定。于是在1978年，有人提出，不使用物理时钟确定分布式系统中事件先后顺序。他认为如果两个进程无关，则其时钟根本不需要同步，而对于相关进程，也没有必要找到他们的绝对执行时间，只要能够确定他们执行的先后顺序就行。（1）、事件排序a.定义一个时间关系，即前超关系，也称“先发生”关系，b.时间戳刚才都讲过，我们直接看算法。1分钟（2）、分布式同步互斥算法比较著名的有：……这三种。Lamport算法：最早提出的分布式同步算法，它要求访问临界资源的所有事件进行排序，然后按照先来先服务原则进行处理。我们课本给出的是Ricart-Agrawla.（3）、....Ricart算法a、进程Pi想要进入临界区，产生一个时间戳Ti，发送消息request(Pi,Ti)给所有其他进程。b、进程Pj接收到request消息后，可能立即回复，也可能延迟回复。如果Pj当前在临界区中，延迟回复。如果Pj不想进入临界区，立即回复。如果Pj想进入但未进入临界区，则比较二者的事件戳。若TiTj，立即回复，否则，延迟回复。c、当进程Pi接收到所有进程回复的reply消息后，便可进入到临界区。d、当进程Pi离开临界区后，给所有延迟回复的进程发送reply消息。例：假如有三个进程P1，P2，P3，进程P1和进程P3想进5分钟板书入同一临界区，P1发送request(1，15)消息给P2和P3，P3发送request(3，6)消息给P1和P2。P2收到请求后，立即回答。P1接收到P3的请求后也立即回答，因为P1的时间戳大于P3。P3收到来自P1的请求后延迟回答。当P3收到来自P1和P2的回答后，进入临界区，P1则等待P3回答。当P3退出临界区后，向P1发送回答消息，于是P1进入临界区。算法缺点3、死锁的预防和检测上面讲的是进程的同步和互斥，下面我们来看死锁。我们在集中式操作系统中学习了死锁发生的四个必要条件，它们是：资源独占、不可剥夺、保持申请、循环等待，只要破坏这四个条件其中的一个，死锁就不会发生。那在分布式中其实也可以这样破坏死锁产生的必要条件来预防死锁的发生。比如可以采用静态分配资源策略，就是说在进程运行前，一次性申请它运行所需要的全部资源，若系统具有足够的空闲资源时，就一次性的把进程运行需要的资源全部分给它，这样进程在运行时就不会再申请；否则（系统资源不够），就一个资源都不分给进程，让它等待。这样就破坏了保持申请的条件。2分钟（1）、死锁的预防我们今天讲的是基于时间戳定序的死锁预防，方法是通过剥夺必要的资源以防止循环等待条件的发生。为了控制剥夺，在每个进程创建时赋予一个唯一的时间戳作为优先数。具体的死锁预防有两种方案。第一种：基于非剥夺式的，称为等待死亡法。如果T2T1，则阻塞A2，否则杀死A2，然后重启A2。即如果事件A2在事件A1之前开始，那么A2等待A1结束；否则分布式3分钟操作系统杀死A2，并在一段时间后重启A2（具有相同的时间戳T2）。第二种：基于剥夺式的，称为受伤等待法。如果T2T1，则杀死A1；否则停止A2执行。即如果事件A2在事件A1之前开始，则杀死A1；如果事件A1开始的比较早，那么分布式操作系统就会停止A2执行。（2）、死锁的检测A、集中式死锁的检测算法：模仿非分布式的算法B、分布式的死锁检测：典型的：Chandy_Misra_Haas算法。该算法允许进程一次请求多个资源而不是一次只申请一个。通过允许多个请求同时进行，使得进程的推进速度加快。该模型的这种变换使得一个进程可以同时等待两个或多个进程。板书5分钟三、资源管理资源管理和调度是操作系统的主要任务。分布式操作系统中资源管理可以采用集中式、分布式和层次式。1、集中式资源管理有一个中央资源管理者，负责系统中所有任务的分配。为便于管理，还有一个与资源分配情况有关的数据结构，成为系统资源表，记载着系统中所有资源的有关信息。比如：资源类型、数量、物理单位、物理特性、分配状态等等。（比如，整个学院都归院长一个人管，优点就是，院长可以合理的分配各种事项，运筹帷幄；办事容易，直接找院长，借教室，领粉笔，统统找院长，其他的老师就比较轻松；减少了资源管理算法的开销，减少了你找各个老师的时间。当然这样的算法，缺点也很明显，比如院长哪天不小心把09级的学生信息弄没了，那可能就需要重新录入，很费事；毕竟院长一个人的精力有限，学院的一些事情可能会受到限制；整个系统失去自治性。）5分钟2、分布式资源管理每个站点有一个局部资源表，用于记载属于该站点的局部资源。当用户申请局部资源时，可由本地得到；当它申请全局资源时，它向其他站点发送申请，其他站点根据情况做出分配决策。2分钟3、层次式资源管理对上两者的综合。共29+1=30分钟