分布式操作系统1

1、分布式操作系统(高等操作系统)Distributed Operating System2005.8计算机与通信学院 胡峰松副教授课程序言 教师介绍 胡峰松，92年国防科大毕业，湖南大学硕士毕业，副教授，在读博士生。主讲了操作系统、计算机网络、微机原理、INTERNET基础等课程。分布式操作系统课程由我主讲。 8944489 课程介绍 分布式操作系统的前导课程-操作系统基础； 分布式操作系统课程先定义分布式操作系统，再较全面地介绍了分布式操作系统环境中的通信、同步、进程、文件系统和存储器管理等方面的概念与算法，并详细地给出了分布式操作系统设计实例。理论与实践结合，16章

2、讲叙原理，710章介绍4个分布式操作系统的实例。通过学习对分布式操作系统的原理和实现有一个完整的认识和了解，并能了解与跟踪当前的最新技术。 课程计划 分布式操作系统课程共计划48个课时，其中讲授 42 学时，自学6 学时. 第一章 分布式系统概述4课时 第二章 分布式系统的通信6课时 第三章 分布式系统的同步6课时 第四章 分布式系统的进程和处理机6课时 第五章 分布式文件系统6课时 第六章 分布式共享存储器6课时 第七章 分布式系统实例研究 4课时 上机实习 6课时 考前复习 4课时 教学与考核 1、采用多媒体教学，电子教案与传统板书相结合； 2、课堂点名、提问与实验，占期评成绩15% ；

3、3、布置作业与讲解，占期评成绩15% ； 4、找资料并写相关小论文，占期评成绩10% ； 5、期终考试采用闭卷笔试，占期评成绩60% ；参考资料1、中、英文版教材:Distributed Operating Systems Andrew S.Tanenbaum2、Doreen L. Galli:“分布式操作系统原理与实践” 机械工业出版社20033、William Stallings “操作系统：内核与设计原理”，电子工业出版社，20014、论文集：Procceedings of the n-th ACM Symposium on Operating Systems Principles;5、

4、论文集：Procceedings of the n-th International Conf. On Distributed Computing Systems ;6、期刊：ACM Transactions on Computer Systems7、期刊：Operation Systems Review8、 Operating Systems Conceptssixth edition Abraham Silberschatz 高等教育出版社第一章 分布式系统概述1.1 引言一、分布式发展的原因：4585 计算机庞大且很贵，只能独立运行；85今 计算机技术取得了惊人的进步： 1、功能更强的微

5、处理机的开发； 8163264位微处理机（CPU）开发与普及， 1000万美元 1条指令/秒 发展到 1000美元 1000万条指令/秒 性能价格比提高了10的11次方倍。2、高速计算机网络的出现与发展；LAN:10M100M 1000M(1G) 网络传输速度 WAN:64k1000M(1G)光纤网络硬件成熟：使大量CPU组成的计算机系统可以通过网络连接在一起；集中式系统Single processor systems(centralized systems)-分布式系统Distributed systems软件刚起步：分布式系统需要与集中式系统完全不同的软件；A Distributed Sy

6、stem二、定义 A distributed system is: A collection of independent computers that appears to its users as a single coherent system（a single computer）. 一个分布式系统是一些独立的计算机的集合，但对于这个系统的用户来说，系统就象一台完整计算机一样。分布式操作系统定义的含义：1、硬件每台计算机都是自主的；2、软件用户将整个系统看作是一台计算机；举例：1、LAN ,多cpu, 一个文件系统，cpu 分配优化、均衡。 2、工厂，机器人自主工作，程序一致性。 3、银

7、行，异地通存通兑。Definition of a Distributed System (2)A distributed system organized as middleware.Note that the middleware layer extends over multiple machines.1.11.2分布式系统的目标一、分布式系统与集成式系统相比较的优点1、经济的驱动微处理机提供了比大型主机更好的性能价格比；2、计算机处理速度分布式系统总的计算能力比单个大型主机更强；3、分布式系统固有的分布性一些应用涉及到空间上分散的机器，如连锁店；4、协同工作CSCW（Computer S

8、upported Cooperative Work） 一组距离较远的工作人员可以一起进行工作，CSCG（Computer Supported Cooperative Games）5、高可靠性一个机器崩溃，整个系统仍可以正常运转；6、渐增式的增长方式增加一些处理机，计算机能力可以逐渐增加；大量pc的存在和人们共同工作与信息共享的需要是分布式系统发展的主要驱动力。二、分布式系统与独立PC机相比较的优点1、数据共享分布式系统允许多个用户访问一个公共的数据库（共享数据）2、设备共享分布式系统允许多个用户共享昂贵的外围设备（共享资源）3、网络与通信使得人们之间的通信更加容易，增强了信息沟通，如：E-ma

9、il等4、灵活性用最有效的方式将工作负荷分配到可用的机器上，并不总是在自己的计算机上完成，即负载均衡。三、分布式系统的缺点1、在软件方面目前为分布式系统开发的软件还比较少，在设计、实现及使用分布式系统上都没有太经验，什么os.、program和application 适合这一系统？2、在通信网络方面 网络可能损失信息、信息过载饱和-引起网络替换或网络扩容等其他问题，抵消大部分优势。3、安全性方面共享数据、资源容易造成对保密数据的访问失控，无连接、孤立的计算机存储保密数据更为安全可靠。1.3 硬件概念分布式系统具有多种类型的硬件组织方法：体现在Cpu的互连方式和Cpu的通信方式上。有许多cpu计

10、算机系统分类方案，其中按照指令流的数量与数据流的数量进行划分：1、单指令流，单数据流（SISD）Single Instruction stream,Single data stream传统单处理机（单cpu的）计算机。2、单指令流，多数据流（SIMD）Single Instruction stream,Multiple data stream 具有处理器阵列结构,指令单元取出一条指令后，操纵许多数据单元并行地执行该指令，且数据单元都有自己的数据。3、多指令流，单数据流（MISD） Multiple Instruction stream, Single data stream 无此类计算机4、多

11、指令流，多数据流（MIMD） Multiple Instruction stream,Multiple data stream本质上是一组独立的计算机，各自有程序计数器、程序和数据。所有的分布式系统都是MIMD型。Hardware Concepts1.6Different basic organizations and memories in distributed computer systemsMIMD可以根据耦合程度细分：紧耦合： 多处理机/多处理器，具有共享存储器，共享统一的虚拟地址空间，信息传输延迟小，速度快，多用于并行系统松耦合： 多计算机，不具有共享存储器，信息传输延迟较大，速度

12、较慢，多用于分布式系统主要区别： multiprocessor具有共享存储器,如任一cpu将44写入地址1000中，随后任一cpu从地址1000中读出44。 multicomputer不具有共享存储器,无影响。如网络连接的个人计算机的集合。紧耦合多用于并行系统，松耦合多用于分布式系统有反例（分解因子）-p7MIMD还可以根据互连网络的体系结构细分：总线型（bus）：只通过单个网络、底版、总线、电缆或其他介质将所有计算机联结起来 。如有线电视网，交换型（switched）：机器之间有独立的线路, 信息沿着线路传输，每步都有路由选择。如公共电话系统。并行分布式计算机MIMD多处理机（共享存储器）多

13、计算机（私有存储器）总线型交换型交换型总线型图1-1 并行及分布式计算机系统分类法Sequent encoreSuper computerLan工作站超立方体一、基于总线的多处理机MemoryCPUCPUCPUCacheCacheCache总线图1-2 基于总线的多处理机P8 工作过程特点 : (p8)1、一个存储器，相关性（coherent），总线请求2、总线易过载，CPU数目有限(=64个)-增加cache memory3、使用高速缓存提高命中率,总线的通信量会下降，-但有不一致问题4、采用通写缓冲存储器（write-through cache），读命中不会，读失败和写会引起总线负载5、采

14、用监听缓冲存储器（snoopy cache）,发现memory有写，则更新或清掉缓冲存储器的相应地址的值。相关性（coherent）6、通信量大，通常需要高速背板总线二、基于交换型的多处理机图1-3 a) 交叉开关 b) omega网络p9特点：1：交叉开关当有n个CPU和n个存储器模块时，需要n2个交叉开关，实际中很少使用2： omega网络在有n个CPU和n个存储器模块时，需要log2n个交换开关级，每级n/2个交换开关，共(nlog2n)/2个交换开关； omega网络存在时延-NUMA(非一致存储访问 Non Uniform Memory Access)例：系统CPU数目为1024个，

15、CPU速度为100MIPS，采用omega网络进行CPU与存储器的连接，试计算所需要的交叉开关数目，以及在不影响CPU正常执行的情况下交叉开关的最大交换时间。结论：建立一个共享存储器的多处理机系统是可行的，但困难且价格贵。三、基于总线的多计算机总线CPUCPUCPU局部内存局部内存局部内存图1-4 局域网由多台工作站组成的多计算机系统特点： 1、cpu与cpu之间的通信量要少cpu与memory几个数量级2、数据传输速率较低3、操作时间不同步4、数据传输过程中存在数据丢失四、交叉型多计算机图1-5 a) Grid（网格） b) Hyper Cube（超立方体）特点：1、网格结构简单，被布置在印

16、刷电路板上， 适合于解决固有特性为两维问题。2、超立方体是n维立方体，包含N2 个节点，节点度数为n，直径为n。每个节点有一个n位的二进制地址。两个节点，当有且仅有一个位不同时，它们相互连接。结构复杂按cpu数量（N）的对数增加，存在时延只有最相邻的 cpu是互连的，信息到达终点要跳跃n次。n=log2N例：一个具有256个中央处理机的多计算机环境，若采用1616网格组织，一个消息最差的时延是多少？若采用超立方体结构呢？（时延以hops进行计算）1、n=16, 2n-2=30hops; 2、n=log2256=8, 8 hopsn1.4 软件概念操作系统软件分类: (p12) 松耦合: 如la

17、n 紧耦合: 如并行运行的下棋程序Software Concepts An overview of DOS (Distributed Operating Systems) NOS (Network Operating Systems) MiddlewareSystemDescriptionMain GoalDOSTightly-coupled operating system for multi-processors and multicomputersHide and manage hardware resourcesNOSLoosely-coupled operating system f

18、or heterogeneous multicomputers (LAN and WAN)Offer local services to remote clientsMiddlewareAdditional layer atop of NOS implementing general-purpose servicesProvide distribution transparencyUniprocessor Operating Systems Separating applications from operating system code through a microkernel.1.11

19、一、网络操作系统特点：1、机器高度自主2、每台机器的操作系统可以不一样3、主要通过共享文件进行通信4、命令通常在本地运行、系统范围的请求很少5、不同文件系统结构可能不一样6、对其他机器的访问用户是可见的p13网络操作系统为松耦合硬件上的松耦合软件 Depiction of typical LAN:网络操作系统的常用的运行环境(1) General structure of a network operating system.1-19网络操作系统的常用的运行环境(2) Two clients and a server in a network operating system.1-20网络操作

20、系统的常用的运行环境(3) Different clients may mount the servers in different places.1.21二、分布式操作系统特点：1、系统操作对用户透明，具有单系统映像2、所有机器运行相同的操作系统3、具有一个单一的、全局的进程间消息通信机制4、不同机器上的进程管理模式一致5、文件系统结构一致分布式操作系统为松耦合硬件上的紧耦合软件p14Multicomputer Operating Systems (1)General structure of a multicomputer operating system1.14Multicomputer

21、 Operating Systems (2)Alternatives for blocking and buffering in message passing.1.15Multicomputer Operating Systems (3) Relation between blocking, buffering, and reliable communications.Synchronization pointSend bufferReliable comm. guaranteed?Block sender until buffer not fullYesNot necessaryBlock

22、 sender until message sentNoNot necessaryBlock sender until message receivedNoNecessaryBlock sender until message deliveredNoNecessaryDistributed Shared Memory Systems (1)Pages of address space distributed among four machinesSituation after CPU 1 references page 10Situation if page 10 is read only a

23、nd replication is used False sharing of a page between two independent processes.1.18 False sharing of a page between two independent processes.三、多处理机分时系统特点：1、系统操作对用户透明，具有单系统映像2、只有一个操作系统3、存在唯一进程队列4、不同CPU共享存储器5、具有一个统一的块缓冲存储器的传统文件系统多处理机分时操作系统为紧耦合硬件上的紧耦合软件p15Multiprocessor Operating Systems (1) A monit

24、or to protect an integer against concurrent access.monitor Counter private: int count = 0;public: int value() return count; void incr () count = count + 1; void decr() count = count 1;Multiprocessor Operating Systems (2) A monitor to protect an integer against concurrent access, but blocking a proce

25、ss.monitor Counter private: int count = 0; int blocked_procs = 0; condition unblocked;public: int value () return count; void incr () if (blocked_procs = 0) count = count + 1; else signal (unblocked);void decr() if (count =0) blocked_procs = blocked_procs + 1; wait (unblocked); blocked_procs = block

26、ed_procs 1; else count = count 1; n个CPU的三种不同组织方式的比较Comparison between Systems A comparison between multiprocessor operating systems,multicomputer operating systems, network operatingsystems, and middleware based distributed systems.OpenOpenClosedClosedOpennessVariesYesModeratelyNoScalabilityPer node

27、Per nodeGlobal,distributedGlobal,centralResource managementModel specificFilesMessagesSharedmemoryBasis for communicationNNN1Number of copies of OSNoNoYesYesSame OS on all nodesHighLowHighVery HighDegree of transparencyMulticomp.Multiproc.Middleware-based OSNetworkOSDistributed OSItem1.5 设计中的问题1.5.1

28、 透明性（Transparency） 最重要的一个问题可能是如何实现单系统映像，即系统设计者如何使每个用户误以为一些机器的集合只是一个老式的分时系统？能达到这个目标的系统通常就被成为是透明的（transparent）。透明的概念适用与分布式操作系统的多个方面。 1.位置透明（位置透明（location transparency）：）： 是指在一个真正的分布式操作系统中，用户不知道硬、软件资源如CPU、打印机、文件和数据库的位置。资源的名字不应含有资源的位置信息。 例如：machinel:prog.c/或macchinel/prog.c之类的名字是不能接受的。 2.迁移透明（迁移透明（migra

29、tion transparency ）: 是指资源无须更名就可自由的从一地迁向另一地。 例如：服务器目录能够在客户目录分层结构中的任何地方装入，是因为路径并未指出服务器位置，所以系统是位置透明的。而远程登录属于网络O.S.，因此是不透明的。 3.复制透明（复制透明（replication transparency ）: 是指操作系统可以随意的为文件和其他资源进行附加拷贝而无须用户知道。用户不知道有多个拷贝存在. 一个逻辑上由N台服务器连成环形的集合。每台服务器都有一个完整的目录树结构，但它只存储全部文件的一个子集。为阅读一个文件，用户发送一个全路径名的消息给任一服务器。那个服务器如果没有该文件

30、，它就将这个要求传给该环形网中的下一个服务器，如此重复。由于这种方案允许系统对常用文件进行备份而无须用户知晓，所以该方案是复制透明的。 4.并发透明（并发透明（concurrency concurrency transparency） 分布式系统通常有多个独立的用户，当两个或多个用户同时访问相同资源时，任一用户不会发现其他用户的存在。 获得这种透明类型的机制是：一旦某个用户开始使用一个资源时，系统就自动锁定此资源，只到该用户使用完后再解锁。 5.5.并行透明（并行透明（parallelism parallelism transparency） 理论上分布式系统在用户面前的表现就象一个传统的单处

31、理机分时系统。系统活动可以在用户没有感觉的情况下并行发生.Transparency in a Distributed SystemDifferent forms of transparency in a distributed system.TransparencyDescriptionAccessHide differences in data representation and how a resource is accessedLocationHide where a resource is locatedMigration Hide that a resource may move

32、to another locationRelocationHide that a resource may be moved to another location while in useReplicationHide that a resource may be shared by several competitive usersConcurrencyHide that a resource may be shared by several competitive usersFailureHide the failure and recovery of a resourcePersist

33、enceHide whether a (software) resource is in memory or on disk1.5.2 灵活性(Flexibility) 设计中的第二个关键问题是灵活性。现在看来合理的设计思想也许以后将被证明是错误的。避免问题的最好方法是在设计过程中始终保持有很大的选择余地。 分布式系统结构主要有两种：单内核和微内核。 1、单内核，每台机器运行一个传统的内核，内核提供了大多数的服务。单内核基本上是目前的集中式操作系统，增加了网络功能和远程服务集合。 因为UNIX系统有巨大的内核 ，许多扩展或模仿UNIX系统的分布式系统都采用该方法。 2、微内核，内核尽可能少地提

34、供服务，大量的操作系统服务可从用户服务器上获得。微内核具有更好的灵活性。进程间通信机制；某些内存管理功能；少量的低进程管理和调度；低层输入/输出服务。 微内核与单内核不同，它不提供对文件系统、目录系统、整个进程管理，或许多系统调用的处理。其他的操作系统服务都作为用户服务器来实现，每个服务（服务器能理解的消息的集合）都有一个定义好的接口，每个服务程序对所有客户来说都是可以访问的，且和位置无关。 另外，该系统易于实现、安装和调试新的服务程序，因为它具有删除、添加和修改服务的功能使得微内核具有很高的灵活性。此外，用户如不满意一个通用的服务程序，也可以编写自己的服务程序来代替它。例：p201.5.3

35、可靠性(Reliability) 建立分布式系统的最初目的之一就是使系统比单处理机系统更可靠。当然这种说法是不能完全信以为真的，因为它依靠一些专用服务器的正常工作。系统中仍然有可改善的地方。 1、可以通过不要求大量关键部件同时起作用的设计来提高可用性。提高可用性的另一种方法是冗余，即给关键的硬件和软件提供备份，备份越多，可用性越好，但不一致的可能性却越大，这两点都得兼顾。 2、整体可靠性的另一方面是安全性。 必须保护文件和其他资源不被非法用户使用。在分布式系统中指令是哪个用户发出的还暂时无法判断。 3、与可靠性有关的另一个方面是容错。 分布式系统能设计成可以屏蔽错误，也就是对用户隐藏错误。一组

36、紧密协同工作的服务器构成的系统，若损失一两个服务器，用户只是感到一些性能上的降低，维护系统正常运行不会给该系统增加很大的开销。1.5.4 性能（Performance） 总是隐藏在系统内部的一个问题就是性能问题。如果你建立了一个透明、灵活和可靠的分布式系统，但是它的运行速度慢，那么，它是不会给你赢来任何奖赏的。 性能标准进行衡量之一是响应时间，还有吞吐量、系统的利用率和网络容量消耗程度。此外，任何基准程序的测试结果通常取决于该基准程序自身的性质（CPU量大，O/S量大）。 分布式系统的通信通常是很慢的，大部分时间用在两端不可避免的协议处理上，不是用在线路中传送数据位。获得性能的最佳方法是让许多活动在不同处理机中并行进行，而这样做就需要传送许多消息。涉及大计算量、低相互作用和小数据量的作业，粗粒度并行性可能会更适合些。 容错也要付出代价，通常做法是通过