模版

《分布式操作系统》教学大纲

一、课程基本信息

课程编号	Y2101001	开课学期	秋季一学期
课程名称	分布式操作系统	英文名称	Distributed Operating System
开课院系	计算机学院	适用学生	全日制学硕■ 全日制专硕■ 非全日制专硕■
总学时/学分	48/3	学时学分分配方案	讲课 32/2	实践16/1
考核方式	考试■考察□	考核方法	试卷■ 论文□ 报告■ 设计方案□ 其它□
先修课程	无	课程性质	公共基础课□ 专业基础课■ 专业必修课□ 专业选修课□ 公共选修课□

二、本门课程的教学目标和要求

通过本课程的学习，使学生深入理解设计和构造分布式系统的基本原理、算法和实现技术，了解分布式系统的发展趋势。在硕士论文阶段和以后的实际工作中，能综合利用所学过的分布式系统知识，完成相关的研究工作和工程工作。要求学生能及时完成布置的作业，能用Java或C++编程语言实现部分算法，有能力的同学可查找更多的资料与老师和同学讨论。

三、教学重点与难点

   1.分布式设计中的问题：透明性、灵活性、可靠性、性能、开放性及技术、可伸缩性及技术；

   2.客户-服务器模式：基本思想、三种寻址方法、阻塞与非阻塞原语、有缓冲和无缓冲原语、可靠和非可靠原语、客户机-服务器模式的实现；

   3.远程过程调用：基本RPC操作、参数传递、动态捆绑、失败情况下的RPC语义、实现问题；

4.系统体系结构：集中的体系结构（分层C/S）、非集中的体系结构结构（结构化P2P、非结构化P2P）；

  5.时钟同步算法、互斥算法、选举算法；并发控制算法、分布式死锁检测、死锁预防；

  6.处理机分配算法、主动复制容错、主机后背容错、容错系统中的协同一致；

  7. 分布式文件系统的实现：高速缓存（一致性算法）、文件复制（复制方法及更新方法）；

  8. 基于总线的多处理机一致性协议、基于环的多处理机一致性协议、交换式多处理机一致性协议；

四、教学内容及基本要求

 第一章  分布式系统概述(6学时)

教学目标和要求:了解分布式系统的目标、硬件概念、软件概念，掌握分布式系统的设计问题。

教学重点和难点：分布式设计中的问题：透明性、灵活性、可靠性、性能、开放性及技术、可伸缩性及技术。

教学方式：（课堂讲授6学时）.

教学内容：

1．分布式系统目标：分布式系统概念、分布式系统相对于集中式系统的优点 ，分布式系统与独立PC机比较的优点、分布式系统的缺点；（1学时）

2.硬件概念：分类、基于总线的多处理机、交换型多处理机、基于总线的多计算机、交换型多计算机；（1学时）

3.软件概念：网络操作系统、真正的分布式系统、多处理机分时系统；（1学时）

4.设计中的问题：透明性、灵活性、可靠性、性能、开放性及技术、可伸缩性及技术。（3学时）

复习与思考题:

1.分布式系统的目标是给用户一种错觉，就像使用单一计算机一样，这需要透明性支持，说明分布式系统支持的各种类型的透明性。

2.详细分析影响分布式系统规模（Size）可伸缩性的三个因素，即集中式的服务、数据和算法。试举例说明分布和复制技术是如何提高可伸缩性的。

3.在分布式操作系统中，说明单内核的含义，并说明为什么采用微内核技术，通常微内核提供应提供哪些服务？

第二章  分布式系统的通信及体系结构( 12学时 )

教学目标和要求: 掌握客户-服务器模式的基本思想、设计和实现问题；掌握RPC操作及组通信。

教学重点和难点：1.客户-服务器模式：基本思想、三种寻址方法、阻塞与非阻塞原语、有缓冲和无缓冲原语、可靠和非可靠原语、客户机-服务器模式的实现；2.远程过程调用：基本RPC操作、参数传递、动态捆绑、失败情况下的RPC语义、实现问题；3. 非集中的体系结构结构（结构化P2P、非结构化P2P）、混合体系结构。

教学方式：（课堂讲授12学时）

教学内容：

1.客户-服务器模式：基本思想、三种寻址方法、阻塞与非阻塞原语、有缓冲和无缓冲原语、可靠和非可靠原语、客户机-服务器模式的实现；（3学时）

2.远程过程调用：基本RPC操作、参数传递、动态捆绑、失败情况下的RPC语义、实现问题；（3学时）

3.组通信：组通信的概念与性质、设计问题；（2学时）

4.软件体系结构：四种体系结构式样；（1学时）

5.系统体系结构：集中的体系结构（分层C/S）、非集中的体系结构结构（结构化P2P、非结构化P2P）、混合体系结构。（3学时）

复习与思考题:

1.组通信系统中，原子性的含义是什么，举例说明为什么要保证原子性。在保证原子性的同时还要保证消息顺序，举例说明保证消息顺序的必要性。

2. 说明RPC的主要步骤，在形式说明书中输入参数、输出参数、输入、输出参数的含义是什么，为什么要这样规定。如果服务器是无状态的，为什么读一个文件的过程需要给出position参数。

3.说明RPC的主要思想。在客户发出请求后，客户机正常，但未收到应答，应该是那些原因造成的。并说明在服务器崩溃的情况下，可采用哪些方法处理。

4.说明客户/服务器模式的主要思想，并说明在采用了阻塞的、有缓存的、可靠的发送和接收原语的情况下，系统是如何工作的。

5.说明在客户/服务器模式中实现可靠通信原语的三种方法，如果以应答作为对请求的确认会带来什么好处，会带来什么问题，怎样解决这个问题。

6.说明无缓冲的receive原语，会带来什么问题，怎样解决这些问题。

7. 客户为了发送消息给服务器，它必须知道服务器的地址，给出三种寻址机制的基本原理，并说明三种机制存在的问题。

8.在实现客户机-服务器协议时，需要哪些基本类型的包，说明每种包的源、目的地以及作用。

9在分布式系统中，软件体系结构是一个非常重要的概念，涉及如何组织软件成分及如何交互等，详细说明四种Architectural Style。

10.客户机服务器应用可以将软件成分分为三层，说明每一层的作用，并说明Internet搜索引擎是如何按三层结构组织软件成分的。

11.说明在基于DHT的结构化P2P系统中如何组织节点和数据，如何查找数据，如何进行成员管理。

12.在非结构化的P2P系统中如何构建网络拓扑，如果使用Superpeer，如何选择Superpeer，它的作用是什么。

13.为什么BitTorrent系统是集中与分布相结合的体系结构？说明BitTorrent系统的主要构成成分，并说明其工作原理。

第三章  分布式系统的同步(12学时 )

教学目标和要求: 了解分布式系统同步的概念，掌握分布式系统常用的同步算法。

教学重点和难点：时钟同步算法、互斥算法、选举算法；并发控制算法、分布式死锁检测、死锁预防。

教学方式：（课堂讲授12学时）。

教学内容：

1.时钟同步：逻辑时钟同步、物理时钟同步、时钟同步应用；（4学时）

2.互斥：集中式算法、分布式算法、令牌环算法；（2学时）

3.选举算法：欺负算法、环算法；（*）（1学时）

4.分布式事务：原子事务概念及性质、两阶段加锁、两阶段提交、乐观并发控制方法、时间戳并发控制方法。（3学时）

5.分布式系统中的死锁：死锁检测（集中和分布算法）、死锁预防；（2学时）

复习与思考题:

1. 在机器0上进程0在等待机器0上进程1所拥有的资源，进程1在等待机器1上进程2所拥有的资源，进程2在等待进程机器1上3，4所拥有的资源，进程3在等待机器2上进程5所拥有的资源，机器2上的进程5在等待机器0上进程0所拥有的资源，画出简化的资源图并说明用Chandy-Misra-Hass提出的分布式死锁检测算法如何检测死锁，并打破死锁。

2.在分布式系统事务提交操作可能需要不同机器上的多个进程的协作，举一个实际例子，并说明实现原子性提交的两阶段提交协议的基本思想。

3.说明基于时间戳的乐观并发控制算法的基本原理，并举例说明。

4.假定A和B是相互独立的两个临界区，进程0申请进入临界区A的时间戳为8，申请进入B的时间戳为15，进程1申请进入临界区A的时间戳为12，申请进入临界区B的时间戳为14，进程2已经在临界区A，但不想进入临界区B,进程3不想进入任何临界区，说明RICART和AGRAWALE分布式互斥算法是如何实现互斥访问的。

5.在分布式系统中，许多算法都需要一个进程充当协调者，因此需要协调者选举算法。试说明欺负算法的主要思想，并说明在8个进程的情况下号码为3的进程发现协调者崩溃后的选举过程。

6.在分布式系统中获得互斥的方法之一是采用集中式的算法，如果有四个进程P0，P 1，P2，P3，P0首先申请资源S，之后P 1，P2，P3 随后申请资源S，试说明采用集中式的算法是如何实现互斥的，并说明该算法可能存在的问题。

7.有三个进程分别运行在不同的机器上，每个机器都有自己的时钟并以不同且不变的速率工作（进程1的时钟嘀嗒了6下时，进程2的时钟嘀嗒了8下，而进程3的时钟嘀嗒了10下），举例说明进程之间消息传递中违反先发生关系的情况，并说明如何用Lamport方法解决。

8.在很多分布式系统应用中，需要物理时钟同步，举一个例子，并说明物理时钟同步的三种算法，Cristian 算法、Berkeley算法及平均值算法。说明为什么在时钟同步算法中，时钟不能倒退，也就是当机器时间大于需要调整的时间钟时，需要渐渐地调整，如何调整。

9.说明物理时钟与逻辑时钟的区别，并说明如何在时钟同步的系统中使用时间保证最多一次消息传送。

第四章  分布式系统中的进程和处理机(14学时 )

教学目标和要求: 掌握线程的概念，并能编程；掌握处理机分配算法；掌握容错及协同一直算法；掌握代码迁移模型。

教学重点和难点：处理机分配算法、主动复制容错、主机后背容错、容错系统中的协同一致。

教学方式：（课堂讲授14学时）。

教学内容：

1.线程：概念、模型（派遣者、团队、管道）、实现（用户空间、内核空间）；（2学时）

2.系统模型：工作站模型、处理机池模型、混合模型；（2学时）

3.处理机分配：分配模型、设计问题、分配算法（图论确定性算法、上下算法、层次式的算法、发送者发起的分布式启发性算法、接收者发起的分布式启发性算法、投标算法）；（3学时）

4.容错性：概念、主动复制容错、主机后背容错、容错系统中的协同一致；（3学时）

5.实时分布式系统：什么是实时系统、设计问题、实时通信、实时调度；（2学时）

6.代码迁移的目的及代码迁移的模型。（2学时）

复习与思考题:

1. 分布式协同一致算法的目标是使所有无故障处理机对待某些问题的意见达到一致，在3个正常处理机，2个出错处理机的情况下，用Lamport算法能否达成一致，给出算法的具体步骤。

2.在实时分布式系统中，事件触发和时间触发系统的含义是什么，给出一个例子，并说明为什么动态调度适合于事件触发系统，给出三种动态调度算法。

3.主动复制容错的典型例子是三模冗余容错，说明某组成部件出错和某表决器出错时，是如何容错的。如果在某一级上同时有两个表决器出错，其它所有部件和表决器均正常，能否屏蔽错误，为什么？如果服务器采用主动复制的方法会存在什么问题，如何解决？

4.使用主机后备容错方法容错的主要思想是：在任何一个时刻都有一台服务器是主机，若主机失效了，后备的服务器将承担其任务。试说明主机后备方法的工作原理及存在的问题，及解决办法。

5.一个典型的集中的、启发式的处理机分配算法，即上-下算法。说明该算法的目标，并说明该算法的主要原理。

6. 在支持多线程的系统中，可采用三种模型来组织多线程，详细说明这三种模型。如果在不支持多线程系统中实现文件服务，如何构造文件服务器。

7.说明虚拟化的含义，为了实现虚拟化，计算机系统通常提供四种类型的接口，说明这四种接口，并说明两种实现方式。

8.在分布式系统中，为什么需要代码迁移？代码迁移可以分为Sender-initiated和Receiver-initiated，解释其中的含义，并举例说明。

第五章  分布式文件系统( 4学时 )

教学目标和要求: 了解命名的概念并掌握名字解析的基本方法；了解文件服务器接口、目录服务器接口和文件共享的语义；掌握高速缓存和文件复制的相关方法。

教学重点和难点：分布式文件系统的实现：高速缓存（一致性算法）、文件复制（复制方法及更新方法）；

教学方式：（课堂讲授6学时）

教学内容：

1.命名相关概念及平命名解析；（2学时）

2.分布式文件系统设计：文件服务器接口、目录服务器接口、文件共享的语义、文件系统结构；（2学时）

3.分布式文件系统的实现：高速缓存（一致性算法）、文件复制（复制方法及更新方法）；（2学时）

复习与思考题:

1.在分布式系统，为了获得文件读写的效率，可以在客户和服务器端设置缓存，说明如何设置缓存及目的。并说明解决一致性问题的四种算法及各种算法存在的问题。

2.给出实现文件复制的三种方法，并举例说明更新复制文件的Gifford算法，并说明某些服务器崩溃时，应该采取什么措施。

3. 试说明举例什么是有状态服务器，什么是无状态服务器，并对有状态和无状态服务器进行详细的比较。

4. 在分布式系统中，可支持上载/下载文件模式或远程访问模式，说明这两种模式并进行比较。

5.为了支持大规模网络中的移动实体可以采用Home-Based方法，说明其工作原理，并说明存在的问题及可能的解决办法。

6.在DHT-based系统中可以采用finger　table提高查找效率，说明其工作原理，并举例说明。

参考文献：

1. (荷)Andrew S.Tanenbaum，分布式操作系统（英文版），机械工业出版社，2006年7月

2．(荷)Andrew S.Tanenbaum，分布式系统 原理与范型，清华大学出版社，2004年9月

3．（美）Doreen L.Galli，分布式操作系统原理与实践，机械工业出版社，2005年7月

执笔人: ###             审核人：###               批准人：###