分布式操作系统1

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分布式操作系统,(,高等操作系统,),Distributed Operating System,2005.8,计算机与通信学院 胡峰松副教授,课程序言,教师介绍,胡峰松，,92,年国防科大毕业，湖南大学硕士毕业，副教授，在读博士生。主讲了操作系统、计算机网络、微机原理、,INTERNET,基础等课程。分布式操作系统课程由我主讲。,fshu,13308488019, 8944489,课程介绍,分布式操作系统的前导课程,-,操作系统基础；,分布式操作系统课程先定义分布式操作系统，再较全面地介绍了分布式操作系统环境中的通信、同步、进程、文件系统和存储器管理等方面的概念与算法，并详细地给出了分布式操作系统设计实例。理论与实践结合，,16,章讲叙原理，,710,章介绍,4,个分布式操作系统的实例。通过学习对分布式操作系统的原理和实现有一个完整的认识和了解，并能了解与跟踪当前的最新技术。,课程计划,分布式操作系统课程共计划,48,个课时，其中讲授,42,学时，自学,6,学时,.,第一章 分布式系统概述,4,课时,第二章 分布式系统的通信,6,课时,第三章 分布式系统的同步,6,课时,第四章 分布式系统的进程和处理机,6,课时,第五章 分布式文件系统,6,课时,第六章 分布式共享存储器,6,课时,第七章 分布式系统实例研究,4,课时,上机实习,6,课时,考前复习,4,课时,教学与考核,1,、采用多媒体教学，电子教案与传统板书相结合；,2,、课堂点名、提问与实验，占期评成绩,15%,；,3,、布置作业与讲解，占期评成绩,15%,；,4,、找资料并写相关小论文，占期评成绩,10%,；,5,、期终考试采用闭卷笔试，占期评成绩,60%,；,参考资料,1,、中、英文版教材,:Distributed Operating Systems Andrew,S.Tanenbaum,2,、,Doreen L.,Galli,:“,分布式操作系统原理与实践” 机械工业出版社,2003,3,、,William Stallings “,操作系统：内核与设计原理”，电子工业出版社，,2001,4,、论文集：,Procceedings,of the,n-th,ACM Symposium on Operating Systems Principles;,5,、论文集：,Procceedings,of the,n-th,International Conf. On Distributed Computing Systems ;,6,、期刊：,ACM Transactions on Computer Systems,7,、期刊：,Operation Systems Review,8,、,Operating Systems,Conceptssixth,edition Abraham,Silberschatz,高等教育出版社,第一章 分布式系统概述,1.1,引言,一、分布式发展的原因,：,4585,计算机庞大且很贵，只能独立运行；,85,今 计算机技术取得了惊人的进步：,1,、功能更强的微处理机的开发；,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 System,二、定义,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,、银行，异地通存通兑。,Definition of a Distributed System (2),A distributed system organized as middleware.Note that the middleware layer extends over multiple machines.,1.1,1.2,分布式系统的目标,一、分布式系统与集成式系统相比较的优点,1,、经济的驱动,微处理机提供了比大型主机更好的性能价格比；,2,、计算机处理速度,分布式系统总的计算能力比单个大型主机更强；,3,、分布式系统固有的分布性,一些应用涉及到空间上分散的机器，如连锁店；,4,、协同工作,CSCW,（,Computer Supported Cooperative Work,）,一组距离较远的工作人员可以一起进行工作，,CSCG,（,Computer Supported Cooperative Games,）,5,、,高可靠性,一个机器崩溃，整个系统仍可以正常运转；,6,、渐增式的增长方式,增加一些处理机，计算机能力可以逐渐增加；,大量,pc,的存在和人们共同工作与信息共享的需要是,分布式系统发展的主要驱动力。,二、分布式系统与独立,PC,机相比较的优点,1,、数据共享,分布式系统允许多个用户访问一个公共的数据库（共享数据）,2,、设备共享,分布式系统允许多个用户共享昂贵的外围设备（共享资源）,3,、网络与通信,使得人们之间的通信更加容易，增强了信息沟通，如：,E-mail,等,4,、灵活性,用最有效的方式将工作负荷分配到可用的机器上，并不总是在自己的计算机上完成，即负载均衡。,三、分布式系统的缺点,1,、在软件方面,目前为分布式系统开发的软件还比较少，,在设计、实现及使用分布式系统上都没有太经验，,什么,os,.,、,program,和,application,适合这一系统？,2,、在通信网络方面,网络可能损失信息、信息过载饱和,-,引起网络替换或网络扩容等其他问题，抵消大部分优势。,3,、安全性方面,共享数据、资源容易造成对保密数据的访问失控，,无连接、孤立的计算机存储保密数据更为安全可靠。,1.3,硬件概念,分布式系统,具有多种类型的硬件组织方法：,体现在,Cpu,的互连方式和,Cpu,的通信方式上。,有许多,cpu,计算机系统分类方案，其中按照指令流的数量与数据流的数量进行划分,：,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,、多指令流，多数据流（,MIMD,）,Multiple Instruction stream,Multiple data stream,本质上是一组独立的计算机，各自有程序计数器、程序和数据。所有的分布式系统都是,MIMD,型。,Hardware Concepts,1.6,Different basic organizations and memories in distributed computer,systems,MIMD,可以根据耦合程度细分：,紧耦合：,多处理机,/,多处理器，具有共享存储器，共享统一的虚拟地址空间，信息传输延迟小，速度快，多用于并行系统,松耦合：,多计算机，不具有共享存储器，信息传输延迟较大，速度较慢，多用于分布式系统,主要区别：,multiprocessor,具有共享存储器,如任一,cpu,将,44,写入地址,1000,中，随后任一,cpu,从,地址,1000,中读出,44,。,multicomputer,不具有共享存储器,无影响。如网络连接的个人计算机的集合。,紧耦合多用于并行系统，松耦合多用于分布式系统有反例（分解因子）,-p7,MIMD,还可以根据互连网络的体系结构细分：,总线型（,bus,）：,只通过单个网络、底版、总线、电缆或其他介质将所有计算机联结起来 。,如有线电视网，,交换型（,switched,）：,机器之间有独立的线路,信息沿着线路传输，每步都有路由选择。,如公共电话系统,。,并行分布式计算机,MIMD,多处理机,（共享存储器）,多计算机,（私有存储器）,总线型,交换型,交换型,总线型,图,1-1,并行及分布式计算机系统分类法,Sequent encore,Super computer,Lan,工作站,超,立方体,一、基于总线的多处理机,Memory,CPU,CPU,CPU,Cache,Cache,Cache,总线,图,1-2,基于总线的多处理机,P8,工作过程,特点,: (p8),1,、,一个存储器，相关性（,coherent,），总线请求,2,、,总线易过载，,CPU,数目有限,(=64,个,)-,增加,cache memory,3,、,使用高速缓存提高命中率,总线的通信量会下降，,-,但有不一致问题,4,、采用通写缓冲存储器（,write-through cache,），,读命中不会，读失败和写会引起总线负载,5,、采用监听缓冲存储器（,snoopy cache,）,发现,memory,有写，则更新或清掉缓冲存储器的相应地址的值。相关性（,coherent,）,6,、,通信量大，通常需要高速背板总线,二、基于交换型的多处理机,图,1-3 a),交叉开关,b) omega,网络,p9,特点：,1,：交叉开关当有,n,个,CPU,和,n,个存储器模块时，需要,n,2,个交叉开关，实际中很少使用,2,：,omega,网络在有,n,个,CPU,和,n,个存储器模块时，需要,log,2,n,个交换开关级，每级,n/2,个交换开关，共,(nlog,2,n)/2,个交换开关,；,omega,网络存在时延,-NUMA(,非一致存储访问,Non Uniform Memory Access),例：,系统,CPU,数目为,1024,个，,CPU,速度为,100MIPS,，,采用,omega,网络进行,CPU,与存储器的连接，试计算所需要的交叉开关数目，以及在不影响,CPU,正常执行的情况下交叉开关的最大交换时间,。,结论：建立一个共享存储器的多处理机系统是可行的，但困难且价格贵。,三、基于总线的多计算机,总线,CPU,CPU,CPU,局部内存,局部内存,局部内存,图,1-4,局域网由多台工作站组成的多计算机系统,特点：,1,、,cpu,与,cpu,之间的通信量要少,cpu,与,memory,几个数量级,2,、数据传输速率较低,3,、操作时间不同步,4,、数据传输过程中存在数据丢失,四、交叉型多计算机,图,1-5 a),Grid,（,网格）,b),Hyper Cube,（,超立方体）,特点：,1,、网格结构简单，被布置在印刷电路板上，,适合于解决固有特性为两维问题。,2,、超立方体是,n,维立方体，,包含,N,2,个节点，节点度数为,n,，,直径为,n,。,每个节点有一个,n,位的二进制地址。两个节点，当有且仅有一个位不同时，它们相互连接。,结构复杂按,cpu,数量（,N,）,的对数增加，存在时延只有最相邻的,cpu,是互连的，信息到达终点要跳跃,n,次。,n=log,2,N,例：,一个具有,256,个中央处理机的多计算机环境，若采用,1616,网格组织，一个消息最差的时延是多少？若采用超立方体结构呢？（时延以,hops,进行计算）,1、n=16, 2n-2=30hops; 2、n=log,2,256=8, 8 hops,n,1.4,软件概念,操作系统软件分类,:,(p12),松耦合,:,如,lan,紧耦合,:,如并行运行的下棋程序,Software Concepts,An overview of,DOS (Distributed Operating Systems),NOS (Network Operating Systems),Middleware,System,Description,Main Goal,DOS,Tightly-coupled operating system for multi-processors and,multicomputers,Hide and manage hardware resources,NOS,Loosely-coupled operating system for heterogeneous multicomputers (LAN and WAN),Offer local services to remote clients,Middleware,Additional layer atop of NOS implementing general-purpose services,Provide distribution transparency,Uniprocessor Operating Systems,Separating applications from operating system code through,a microkernel.,1.11,一、网络操作系统,特点：,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,网络操作系统的常用的运行环境,(3),Different clients may mount the servers in different places.,1.21,二、分布式操作系统,特点：,1,、系统操作对用户透明，具有单系统映像,2,、所有机器运行相同的操作系统,3,、具有一个单一的、全局的进程间消息通信机制,4,、不同机器上的进程管理模式一致,5,、文件系统结构一致,分布式操作系统为松耦合硬件上的紧耦合软件,p14,Multicomputer Operating Systems (3),Relation between blocking, buffering, and reliable communications.,Synchronization point,Send buffer,Reliable comm. guaranteed?,Block sender until buffer not full,Yes,Not necessary,Block sender until message sent,No,Not necessary,Block sender until message received,No,Necessary,Block sender until message delivered,No,Necessary,Distributed Shared Memory Systems (1),Pages of address space distributed among four machines,Situation after CPU 1 references page 10,Situation if page 10 is read only and replication is used,Distributed Shared Memory Systems (2),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,、具有一个统一的块缓冲存储器的传统文件系统,多处理机分时操作系统为紧耦合硬件上的紧耦合软件,p15,Multiprocessor Operating Systems (1),A monitor 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 process.,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 = blocked_procs 1;,else,count = count 1;,n,个,CPU,的三种不同组织方式的比较,1.5,设计中的问题,1.5.1,透明性（,Transparency,）,最重要的一个问题可能是如何实现单系统映像，即系统设计者如何使每个用户误以为一些机器的集合只是一个老式的分时系统？能达到这个目标的系统通常就被成为是透明的（,transparent,）。,透明的概念适用与分布式操作系统的多个方面。,1.,位置透明（,location transparency,）：,是指在一个真正的分布式操作系统中，,用户不知道硬、软件资源如,CPU,、,打印机、文件和数据库的位置,。资源的名字不应含有资源的位置信息。,例如：,machinel:prog.c,/,或,macchinel/prog.c,之类的名字是不能接受的。,2.,迁移透明（,migration transparency,）,:,是指,资源无须更名就可自由的从一地迁向另一地,。,例如：服务器目录能够在客户目录分层结构中的任何地方装入，是因为路径并未指出服务器位置，所以系统是位置透明的。而远程登录属于网络,O.S.,，,因此是不透明的。,3.,复制透明（,replication transparency,）,:,是指操作系统可以随意的为文件和其他资源进行附加拷贝而无须用户知道。,用户不知道有多个拷贝存在,.,一个逻辑上由,N,台服务器连成环形的集合。每台服务器都有一个完整的目录树结构，但它只存储全部文件的一个子集。为阅读一个文件，用户发送一个全路径名的消息给任一服务器。那个服务器如果没有该文件，它就将这个要求传给该环形网中的下一个服务器，如此重复。由于这种方案允许系统对常用文件进行备份而无须用户知晓，所以该方案是复制透明的。,4.,并发透明（,concurrency,transparency,）,分布式系统通常有多个独立的用户，,当两个或多个用户同时访问相同资源时，任一用户不会发现其他用户的存在。,获得这种透明类型的机制是：一旦某个用户开始使用一个资源时，系统就自动锁定此资源，只到该用户使用完后再解锁。,5.,并行透明（,parallelism,transparency,）,理论上分布式系统在用户面前的表现就象一个传统的单处理机分时系统。,系统活动可以在用户没有感觉的情况下并行发生,.,Transparency in a Distributed System,Different forms of transparency in a distributed system.,Transparency,Description,Access,Hide differences in data representation and how a resource is accessed,Location,Hide where a resource is located,Migration,Hide that a resource may move to another location,Relocation,Hide that a resource may be moved to another location while in use,Replication,Hide that a resource may be shared by several competitive users,Concurrency,Hide that a resource may be shared by several competitive users,Failure,Hide the failure and recovery of a resource,Persistence,Hide whether a (software) resource is in memory or on disk,1.5.2,灵活性,(Flexibility),设计中的第二个关键问题是灵活性。现在看来合理的设计思想也许以后将被证明是错误的。避免问题的最好方法是在设计过程中始终保持有很大的选择余地。,分布式系统结构主要有两种：单内核和微内核。,1,、单内核，每台机器运行一个传统的内核，内核提供了大多数的服务。单内核基本上是目前的集中式操作系统，增加了网络功能和远程服务集合。,因为,UNIX,系统有巨大的内核 ，许多扩展或模仿,UNIX,系统的分布式系统都采用该方法。,2,、,微内核，内核尽可能少地提供服务，大量的操作系统服务可从用户服务器上获得。微内核具有更好的灵活性。,进程间通信机制；,某些内存管理功能；,少量的低进程管理和调度；,低层输入,/,输出服务。,微内核与单内核不同，它不提供对文件系统、目录系统、整个进程管理，或许多系统调用的处理。其他的操作系统服务都作为用户服务器来实现，每个服务（服务器能理解的消息的集合）都有一个定义好的接口，每个服务程序对所有客户来说都是可以访问的，且和位置无关。,另外，该系统易于实现、安装和调试新的服务程序，因为它具有删除、添加和修改服务的功能使得微内核具有很高的灵活性。此外，用户如不满意一个通用的服务程序，也可以编写自己的服务程序来代替它。,例：,p20,1.5.3,可靠性,(Reliability),建立分布式系统的最初目的之一就是使系统比单处理机系统更可靠。当然这种说法是不能完全信以为真的，因为它依靠一些专用服务器的正常工作。系统中仍然有可改善的地方。,1,、可以通过不要求大量关键部件同时起作用的设计来提高可用性。提高可用性的另一种方法是冗余，即给关键的硬件和软件提供备份，备份越多，可用性越好，但不一致的可能性却越大，这两点都得兼顾。,2,、整体可靠性的另一方面是安全性。,必须保护文件和其他资源不被非法用户使用。在分布式系统中指令是哪个用户发出的还暂时无法判断。,3,、与可靠性有关的另一个方面是容错。,分布式系统能设计成可以屏蔽错误，也就是对用户隐藏错误。一组紧密协同工作的服务器构成的系统，若损失一两个服务器，用户只是感到一些性能上的降低，维护系统正常运行不会给该系统增加很大的开销。,1.5.4,性能（,Performance,）,总是隐藏在系统内部的一个问题就是性能问题。如果你建立了一个透明、灵活和可靠的分布式系统，但是它的运行速度慢，那么，它是不会给你赢来任何奖赏的。,性能标准进行衡量之一是响应时间，还有吞吐量、系统的利用率和网络容量消耗程度。此外，任何基准程序的测试结果通常取决于该基准程序自身的性质（,CPU,量大，,O/S,量大）。,分布式系统的通信通常是很慢的，大部分时间用在两端不可避免的协议处理上，不是用在线路中传送数据位。获得性能的最佳方法是让许多活动在不同处理机中并行进行，而这样做就需要传送许多消息。涉及大计算量、低相互作用和小数据量的作业，粗粒度并行性可能会更适合些。,容错也要付出代价，通常做法是通过使一些服务器密切合作来处理同一个请求以获得高可靠性。,1.5.5,可伸缩性（,Scalability,）,分布式系统设计为有几百个,CPU,同时工作，将来系统中的,CPU,的数量可能会大几个数量级。,1,、 即使有足够高的,CPU,速度和足够大的存储容量，进出邮件服务器的网络通信容量必然会成为一个问题。系统也不允许出现错误。一次停电能使整个系统瘫痪。,2,、 集中式表和集中式组件一样不好。一个人怎样才能保存,5,千万人的电话号码和地址呢？,3,、集中式路由算法，先收集所有信息，用图论算法计算出所有的最优路线，再将这一消息立即传播到整个系统以便改进路由。分布式算法与集中式算法比较，其特点有,没有一台机器上存放着关于系统状态的全部信息；,机器只是基于本地信息作出决定；,一台机器出故障不会破坏算法；,不一定存在全局时钟。,Scalability Problems,Examples of scalability limitations.,Concept,Example,Centralized services,A single server for all users,Centralized data,A single on-line telephone book,Centralized algorithms,Doing routing based on complete information,Scaling Techniques (1),1.4,The difference between letting:,a server or check forms,a client check forms as they are being filled,Scaling Techniques (2),1.5,An example of dividing the DNS name space into zones.,1.6,小结,分布式系统有许多独立的,CPU,组成，它们在一起工作使得整个系统看上去象一台计算机。其优点是：好的性能,/,价格比、应用能力强、高可靠性和可扩展性等。其缺点是：软件较复杂、潜在的通信瓶颈和脆弱的安全性。,多,CPU,系统,多处理机和多计算机,基于总线和交换。,多,CPU,系统的软件大致分为三类。：,1,、网络操作系统允许用户在独立的工作站上通过一个共享的文件系统进行通信，否则就让每个用户只能操作自己的工作站；,2,、分布式操作系统将整个软硬件的集合变成一个单一的集成系统，它很象是传统的分时系统；,3,、共享存储器的多处理机也提供了一个单系统映像，但是因为它是通过把所有事情集中处理而建立的，所以实际上只是一个单系统。共享存储器的多处理机实际上并不是分布式系统。,关键问题是透明性,对用户，甚至应用程序隐藏所有的分布特性。另一问题是灵活性。微内核优于单内核。其他重要问题还有可靠性、性能和可伸缩性。,作业：书,p24,页（,4,）（,6,）（,10,）（,12,）（,17,）（,18,）,