第1章 分布式系统基础知识

分布式处理与计算科学出版社主讲：陈志刚曾锋李登教学内容Icsu1分布式系统基础知识2MPI程序设计3基于对象的分布式系统4基于Web的分布式系统5网格计算和资源管理6基于覆盖网的P2P计算第一章分布式系统基础知识Icsu1分布式系统基础知识2MPI程序设计3基于对象的分布式系统4基于Web的分布式系统5网格计算和资源管理6基于覆盖网的P2P计算1.1分布式系统概念1.2进程间通信1.3命名与保护1.4死锁问题1.5容错技术1.6数据共享1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.1分布式系统的定义

1.为什么需要分布式系统？促进分布计算系统发展的两大技术计算机硬件技术和软件技术的发展；计算机网路技术的发展。两大技术改变了人们使用计算机的方式50年代，预约上机，占用全部资源；60年代，批处理技术；70年代，分时系统，多用户同时使用一台计算机；80年代，个人计算机，每个用户有专用计算机；90年代至今，通过计算机网络使用多台计算机。第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.1分布式系统的定义

1.为什么需要分布式系统？多计算机系统环境带来的新问题在使用上，用户必须知道本地对象和远程对象的区别；在管理上，管理人员不能四处奔走进行文件备份等操作。解决上述新问题的方法是实现分布式操作系统在分布式计算系统中，多台计算机构成一个完整的系统，其行为类似一个单机系统。分布式操作系统是实现分布式计算系统的核心。第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.1分布式系统的定义2.分布式系统

分布式系统是指由多个相互连接的处理资源组成的计算机系统，计算机之间通过消息传递进行通信和动作协调，从用户角度来说，它如同一个集中的单机系统。

对定义作如下说明：1.分布式系统是由多个处理器或者计算机系统组成，这些计算资源可以是物理上相邻的，也可以是地理上分散的。2.分布式系统中的计算机是一个整体，对用户是透明的，用户在使用资源时无须知道这些资源在哪里。3.程序可以分散到各个计算资源上运行，在程序需要协作是，它们通过交换消息来协调彼此的动作。4.不存在集中的控制环节，各个计算系统之间是平等的。第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.1分布式系统的定义

3.分布式系统与集中式系统相比较而言的优势。使用分布式系统可以潜在的得到比单个的大型集中式系统好得多的性价比Grosch定理：CPU的计算机能力与它的价格的平方成正比；随着微处理机技术的发展，Grosch定理不再适用，因为几百美元就能买到每秒钟执行的指令比20世纪80年代最大的大型机每秒所执行的指令还多。有些应用本身是分布式的，需要建立分布式系统来解决问题利于超级市场有很多连锁店，每个商店都有独立的采购，数据管理等功能。同集中式系统相比较，分布式系统的另一个潜在的优势是它的高可靠性通过把工作负载分散到众多的机器上，单个芯片故障最多只会影响一台机器。第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.1分布式系统的定义

3.分布式系统存在的问题。分布式系统最棘手的问题就是软件就目前的最新技术发展水平，在设计、实现及使用分布式系统上都没有太多的经验；通信网络由于它会损失信息，所以就需要专门的软件进行恢复。同时，网络还会产生过载，当网络负载过于饱和是，必须对它进行改造替换或加入另外一个网络扩容。安全性数据易于共享具有两面性。总结：尽管存在这么些潜在的问题，普遍认为分布式系统在未来几年中会越来越重要。第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.1分布式系统的特征

1.透明性访问透明性。用相同的操作访问本地和远程的资源，用户无须区分本地资源和远程资源；位置透明性。不需要知道资源的位置就能够访问它们。当资源在系统中移动时，在资源名字保持变的情况下，原有的程序都可正常运行；并发透明。多个进程能并发的对共享资源进行操作而互不干扰和破坏；复制透明性，允许资源的多个副本同时在系统中存在以增加可靠性和性能，而用户和应用程序员无须了解副本的存在；故障透明性。屏蔽错误，无论是硬件故障还是软件组件故障，整个系统都不会失效，允许用户和应用程序完成它们的任务；伸缩透明性。在不影响用户或程序的操作的前提下，允许系统和应用扩展。第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.1分布式系统的特征

1.透明性移动透明性。在不影响用户或程序的操作的前提下，允许资源和客户在系统内移动；性能透明性。当负载变化时，允许系统重构以提高性能。

2.资源共享3.并发性分布式系统中的每个节点既独立工作，又与所有其他节点并行工作。4.异构性系统中包含的节点可以由不同的计算与通信硬件组成。5.容错性第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.1分布式系统的特征

6.安全性分布式系统维护的众多信息源对用户具有很高的内在价值，因此它们的安全性相当重要。

7.开放性大部分分布式系统是可扩展的，因为在系统运行期间，可以添加或改变节点、组件和应用程序。开放性要求每个组件遵守一组最起码的策略、惯例和协议，以确保更新或增加的组件之间具有互操作性。8.分散控制单独的计算机无须对整个系统的配置、管理或策略控制担负责任。分布式系统则是通过自主主体协议连接的域，而这些自主主体为提供聚合功能要达成足够的共同策略。

第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信1.3命名与保护

1.6数据共享1.1.2分布式系统的架构

第一章分布式系统基础知识Icsu

1.4死锁问题1.5容错技术1.1分布式系统概述

1.2进程间通信1.3命名与保护

1.6数据共享1.1.2分布式系统的架构1.相关组件概述OS服务。直接利用网络操作系统提供的服务编制的应用程序很难具有很高的透明度。

中间件服务。中间件的一个重要目标是为应用程序隐匿底层平台的异构性。许多中间件系统提供某种程度的全局服务集成，并且只为用户或应用程序提供使用这些服务的接口。

2.

中间件模型将任何资源作为文件来对待。如在Plan9中，所有的资源，包括键盘、鼠标、硬盘、网络接口等等这些I/O设备都被当作文件看待。无论一个文件是远程的还是本地的，在本质上是没有区别的。因为一个文件能够被几个进程共享，进程通信可以简化到对同一个文件访问的问题。

第一章分布式系统基础知识Icsu

1.4死锁问题1.5容错技术1.1分布式系统概述

1.2进程间通信1.3命名与保护

1.6数据共享1.1.2分布式系统的架构2.

中间件模型将任何资源作为文件来对待。如在Plan9中，所有的资源，包括键盘、鼠标、硬盘、网络接口等等这些I/O设备都被当作文件看待。无论一个文件是远程的还是本地的，在本质上是没有区别的。因为一个文件能够被几个进程共享，进程通信可以简化到对同一个文件访问的问题。以分布式文件系统(DFS—DistributedFileSystems)为中心的中间件模型。这种模型类似于第一种模型，但并不像Plan9那样严格。在许多情况下，这种中间件实际上只在支持传统文件的分布透明性方面比网络操作系统前进了一步。基于远程过程调用(RPC—RemoteProcedureCall)的中间件模型。这种模型主要集中在隐匿网络通信，隐匿网络通信的方式是允许一个进程调用在一个远程机器上实现的过程。这个过程调用似乎就发生在本地，调用进程不必关心发生网络通信。第一章分布式系统基础知识Icsu

1.4死锁问题1.5容错技术1.1分布式系统概述

1.2进程间通信1.3命名与保护

1.6数据共享1.1.2分布式系统的架构2.

中间件模型基于分布式对象(DistributedObjects)的中间件模型。一个分布式对象往往是在拥有该对象的一个机器上实现，而它的接口在许多其他的机器上可用。当一个进程引用一个方法时，进程所在机器上的接口将此引用转换成一个报文传送给对应的对象，该对象执行所请求的方法并回送结果。同RPC的情况一样，进程完全可以不关心网络通信的细节。基于分布式文档(DistributedDocuments)的中间件模型。如在Web模型中，信息被组织成文档，每个文档透明地存放在某个机器上，文档里包含有一些指向其他文档的链接(link)。通过一个链接，这个链接所指定的文档会被从它存放的位置取到用户的机器上并显示到用户的显示器上。第一章分布式系统基础知识Icsu

1.4死锁问题1.5容错技术1.1分布式系统概述

1.2进程间通信1.3命名与保护

1.6数据共享1.1.3网格计算1.网格计算的定义网络计算（NetworkComputing）是指以网络为中心的计算，或者是基于网络的计算。网络计算将功能和负荷合理的分布到联网的计算机上

网络计算的核心：有效聚合、全面共享、充分释放分布式系统包括：分布式操作系统、分布式数据库系统、分布式计算系统等

2.网格计算产生的背景物质基础：计算机网络已经成为当今流行的计算环境社会需求：计算环境从集中走向分布，系统的分布性、可扩展性和异构性等要求使分布计算面临新的挑战技术条件：分布对象技术和构建技术的发展，使分布式计算的解决方案多样化

第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信1.3命名与保护

1.6数据共享1.1.3网格计算3.并行与高性能计算并行是实现计算能力突破的根本手段高性能计算（HPC—HighPerformanceComputing）称为“国家挑战”高性能计算的发展趋势：(1)面向高端用户，追求细粒度、超高速的并行计算机系列(2)基于网络的并行计算环境4.网格计算的优势网络计算结合了客户/服务计算的健壮性、Internet的易用性和分布式对象的灵活性网络计算的发展趋势：Client/Server-->Client/Network-->Client/VirtualEnvironment所谓3C世界：计算机、通信与消费类电器（Computer,Communication&Consume）

第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护1.6数据共享1.1.3网络计算5.网络计算的发展阶段网络计算时代：所有设备均需与网络连接，网络的可靠性与速度是人们的关注重点，特征是信息向用户的及时提交与获取上下文相关计算时代：当用户在不同地点与环境之间移动时计算任务与计算活动可连续进行，上下文相关计算将会把数字领域延伸到更广阔的存取点自然计算时代：允许用户在需要信息的任何时间地点对它实时存取，需要低开销、普遍可存取的无线能力6.网络计算的分类ClusterComputing.&.GridComputing（按物理结构分）DeepComputing.&.PervasiveComputing（从计算技术角度分）网内分布计算.&.网间分布计算（从内网外网分）网络计算机制：RPC(RemoteProcedureCall),ORB(ObjiectRequestBroker),DCOM(DistributeComponentObjectModel)

第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享1.1.3网格计算7.具体含义集群计算（或者簇群计算）：采用高速网络连接一组工作站或者微机组成一个机器集群，或者在通用网络上寻找一组空闲的处理机形成一个动态的虚拟集群，使之在中间件的控制下提供具有很高性价比的高性能网格计算：将广域范围的计算资源、数据资源和其他设备统一组织，形成一个可相互利用、相互合作的高性能计算网，用户看起来好像在使用一台巨型机一样。网格计算实际上是一种“无缝的集成和协同计算环境”需要解决3个问题：异构性、扩展性、动态自适用性网格计算环境的构架：网格结点、中间件、开发环境与工具、应用层要求：不影响各结点本地管理和自主性，不改变原有操作系统、网络协议和服务，保证用户和远程结点的安全性，允许远程结点加入与退出，提供兼容性与退出机制深度计算：提高计算机系统与网络的性能，突破高速与高性能上限，提高知识处理层次普适计算（广度计算）：扩大信息处理范畴，将计算分布到更广的范围

第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.1.4分布式系统调度1.相关概念负载：分布式系统中各处理机结点所承担的“任务量”。超载、轻载负载均衡：设法对已经分配给各处理机结点的任务进行重新分配，并通过进程迁移（又称为任务迁移）使各节点的负载大致相等负载共享：共享资源、完成任务

2.负载均衡与负载共享共同点：都属于负载分配技术，都在节点之间分派任务，实现“并行”负载共享：属于比较低层次的负载分配技术。目的是使用户能够使用本地所缺少的系统资源，把超载或者低性能节点上的负载加载到轻载或者高性能节点上去执行，不支持任务的动态迁移负载均衡：属于高层次的负载分配策略。支持并行应用，支持动态任务迁移

第一章分布式系统基础知识Icsu1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享

1.4死锁问题

1.5容错技术1.1.4分布式系统调度3.负载均衡负载不均衡总是存在的分类方式很多，如静态与动态负载均衡；局部与全局最优静态负载均衡：在编译的时候决定，根据先验知识作决策，运行的时候不再动态调整调度问题是NP完全问题，即使对计算开销和通信开销做某种假设，依然是NP完全问题4.任务划分粒度：任务划分时影响通信开销的所有单元的平均尺度细粒度：划分的单元小，有利于并行，但切换和通信开销大粗粒度：划分的单元大，不利于并行，但切换和通信开销小中粒度：介于中间

第一章分布式系统基础知识Icsu1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享

1.4死锁问题

1.5容错技术1.1.5分布式系统的发展与挑战1.固有的复杂度源于分布式系统基础原理的挑战。例如，分布式系统的组件通常驻留在不同节点的独立地址空间中，因此与集中式系统不同，分布式系统节点间通信需要采用不同的机制、策略以及协议。

2.附加的复杂度源于分布式系统基础原理的挑战。例如，分布式系统的组件通常驻留在不同节点的独立地址空间中，因此与集中式系统不同，分布式系统节点间通信需要采用不同的机制、策略以及协议。3.方法和技术上的不足流行的软件分析方法和设计技术主要关注与构建那些“尽力而为”满足QoS需求的单进程、单线程应用。4.对核心概念和技术持续的重新创建和重新发现为已解决的问题重新创建完全不兼容的解决方案。

第一章分布式系统基础知识Icsu1.1分布式系统概述

1.2进程间通信

1.3命名与保护

1.6数据共享

1.4死锁问题

1.5容错技术1.2进程间通信

1.1分布式系统概述

1.3命名与保护1.6数据共享1.2.1同一个节点上的进程间通信

传统的UNIX通信方式主要有：信号、管道、消息队列、信号灯、共享内存和内存映像等。1.管道分为未命名管道和命名管道。未命名管道只只用于具有关联的进程，命名管道扩展了未命名管道的功能。2.消息队列消息队列就是一个消息的链表，消息具有特定的格式以及特定的优先级。3.共享内存

共享内存允许两个或多个进程共享一个给定的存储区，因为数据不需要来回复制，所以是最快的一种进程间通信机制。

第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术进程间通信1.2.2不同节点上的进程间通信

1.Socket通信不仅可以实现单机内的进程通信，还可以实现不同计算机上的进程之间的通信。Socket编程中几个重要的系统调用如下：(1).socket()->创建Socket对象(2).bind()->绑定地址(3).connect()->请求建立连接(4).accept()->接受连接请求(5).recvfrom(),recvmsg(),sendto(),sengmsg()->用于通信的系统调用(6).close()->关闭Socket2.PVM和MPIPVM:并行虚拟机；MPI：消息传递接口，在第二章会详细介绍其编程

第一章分布式系统基础知识Icsu1.2进程间通信

1.1分布式系统概述

1.3命名与保护1.6数据共享

1.4死锁问题

1.5容错技术1.2.2不同节点上的进程间通信

3.中间件模式通信

采用中间件模式可使高层应用独立于局部的操作系统，常用的中间件模型有远程过程调用(RPC)，远程方法调用(RMI)等。4.基于Web服务的通信Web服务技术是解决异构平台系统的集成及互操作问题的主流技术。它使用SOAP协议封装请求和响应。SOAP协议是基于XML格式的，所以Web服务技术是与平台无关的。

第一章分布式系统基础知识Icsu1.2进程间通信

1.1分布式系统概述

1.3命名与保护1.6数据共享

1.4死锁问题

1.5容错技术1.2.3组通信

1.组通信是指参与协同工作的多台计算机直接进行通信，区别于点到点通信。

组通信对于分布式系统非常重要。组通信可以分为三种情况：(1).一到多(one-to-many)通信。如果一个服务或是为了提供容错能力或是为了提高可用性而实现为在多台不同计算机上的多个不同的进程，那么就会有一个进程到一个进程组的通信。一个消息只有一个发送者，却有多个接收者，这种通信方式就是组播，组播在分布式系统中的应用包括如下几个：基于复制服务的容错。一个复制的服务由一组服务器组成，客户请求被组播到组的所有成员，每一个都完成相同的操作，即使一些成员出了故障，仍能为客户提供服务；

第一章分布式系统基础知识Icsu1.2进程间通信

1.1分布式系统概述

1.3命名与保护1.6数据共享

1.4死锁问题

1.5容错技术1.2.3组通信

(1).一到多(one-to-many)通信。一个消息只有一个发送者，却有多个接收者，这种通信方式就是组播，组播在分布式系统中的应用包括如下几个：在自发网络中找到发现服务器。客户和服务器能使用组播消息定位可用的发现服务，以便在分布式系统中注册服务接口或查找其他服务的接口；通过复制的数据获得更好的性能。数据复制能增加服务的性能，在某些情况下，数据的副本放在用户的计算机上。每次数据改变，新的值被组播到管理副本数据的各个进程。事件通知的传播。组播到一个组可用于在发生某些事情时通知有关进程。(2).多到一(many-to-one)通信。这种情况有多个消息发送者，但是只有一个接收者。唯一的接收者从一组发送者中的几个或者所有的发送者中接收消息。

第一章分布式系统基础知识Icsu1.2进程间通信

1.1分布式系统概述

1.3命名与保护1.6数据共享

1.4死锁问题

1.5容错技术1.2.3组通信

(3).多到多(many-to-many)通信。有多个消息发送者和接收者。在这种通信方式中，对消息的排序比较困难。(2).组通信系统实例——ISIS系统。ISIS系统的结构目标是基于进程组的可靠性分布式计算。ISIS是一个建立分布式应用的工具包，它的主要思想是“同步”，它的主要通信原语是形式各异的原子广播。三种同步类型同步系统：消息将瞬间到达所有的目的地；弱同步系统：它的每个事件需要一个有限的时间，但是从任何一方来看，所有时间顺序都是一样的；虚拟同步系统：放宽了包的同步顺序。

第一章分布式系统基础知识Icsu1.2进程间通信

1.1分布式系统概述

1.3命名与保护1.6数据共享

1.4死锁问题

1.5容错技术1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享1.3.1命名

1.名字、地址、标识符及其他属性(1).命名就是要给计算机系统中的各项资源赋以名称。通过命名，客户进程可以根据名字获取资源和对象的地址等属性。被命名的实体可以是多种类型，并且可以由不同的服务管理。(2).在分布式系统中，名字用于指称计算机、服务、远程对象、文件以及用户等广泛的资源。名字方便通信与资源共享。(3).名字的两种形式：地址和标识符。(4).地址是特殊类型的名字，它表示的是对象的位置而不是对象本身。(5).标识符是一个符号串，用于确定或访问某一个对象。

第一章分布式系统基础知识Icsu

1.4死锁问题

1.5容错技术1.3.1命名

标识符的性质

(a).一个标识符最多引用一个实体。

(b).每个实体最多由一个标识符引用。(c).一个标识符始终引用同一个实体。对标识符的要求和设计基本原则：

(a).标识符可以用于多种目的。

(b).在系统结构的各层次上，标识符以不同的方式出现。

(c).一个标识符系统由三部分组成：字母表、规则、映射表。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

(6).解析：一个名字被翻译成被命名的资源或者对象的数据时，称一个名字被解析。(a).目的：通常是为了在对象上调用一个动作。(b).名称与对象之间的关系成为绑定。(c).名字被绑定到被命名对象的属性，而不是对象本身的实现。(d).属性是对象特性的值，与分布式系统相关的一个重要属性就是对象的地址。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名分布式系统中的名字名字应该能有效地支持系统的面向事务处理和面向对话这两类服务和应用。应允许在系统中以分散的方式产生全局唯一的名字，以提高效率和可靠性。命名是实现分布计算系统透明性的关键部分，要达到名字透明和位置透明。命名机制应支持对本地或远程资源的访问，命名应与系统拓扑结构或具体的物理连接方式无关，尽可能隐匿各部分的边界。为了支持资源的迁移，命名系统应至少支持两种形式的名字，即标识符和地址，并且可动态地结合(binding)。同一对象可以有用户定义的多个局部名字，需要一种机制把局部名字和全局标识符结合起来。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名名字的结构。名字按结构可分成绝对名字和相对名字两种：绝对名字和给出名字的“上下文”无关，也就是和发出此名字的地点、用户、应用程序无关，它总是代表同一对象，有利于资源共享，因为可以使用整个系统共用的名字指出对象；相对名字和给出名字的上下文有关，例如和网络有关的邮箱名，以及UNIX操作系统中的文件名。地址结构也有两种，即平面地址和分层地址：分层地址由若干段组成，这些段反映了网络的层次结构；平面地址与物理位置或任何其他层次没有任何关系，可以想象平面地址的分配可以使用一个单一的全系统范围的计数器进行，任何时候需要一个新地址时读此计数器并且将计数器加1，这样，地址是唯一的，但和位置无关。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名名字的结构两种地址结构的优缺点：分层地址的优点，分层地址使得路由选择容易；容易创建新的地址，即可在每一个网络内单独决定主机号码；自动给出高位号码，即在主机内不用给出它所属的网络号，正如在城市内拨电话时不必拨国家和地区号码一样，分层地址缺点：当一个进程迁移到另一个机器上时不能使用原来的地址。平面地址的优点：当进程迁移时仍可使用原来的地址；平面地址的缺点：路由选择比较困难，因为每个路由选择节点必须保持一个能对所有可能的地址进行变换的路由选择表，地址的赋值也比较复杂，必须确信每个地址是唯一的。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

2.命名空间(1).命名空间就是一系列名字的集合。(2).通常用一个带标号的有向图来表示，包含两类节点，叶节点和目录节点。一个叶节点代表一个命名的实体，叶节点没有输出弧，只有输入弧。叶节点一般用来保存一个实体所表示的信息。目录节点不仅有输入弧，还有一条或者多条输出弧，每个输出弧被一个名字所标识，如图所示。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

2.命名空间(3).叶节点一般用来存放一个实体所表示的信息。(4).每个目录节点保存了一个表，表中的一项代表了一条输出弧，每条输出弧由(弧标号、节点标识符)表示，这样的一个表被称为目录表。(5).有一个特殊的节点，只有输出弧，没有输入弧，该节点被称为根节点。(6).路径：一个路径是由一串弧的标号组成的，例如：N:<label-1,label-2,…,label-n>，这里N表示这个路径中的第一个节点，这样一个标号串称为路径名。如果路径名中的第一个节点是命名图中的根，则这个路径名被称为绝对路径名，否则称为相对路径名。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

3.命名空间的实现(1).命名空间被分为三层：全局层、组织层、管理层。(2).全局层由最上层的一些节点组成，这些节点包括根节点和它的一些子目录节点组成。用来代表一些机构，这些机构的名字保存在名字空间中。(3).组织层由一个机构内的所有目录节点组成，这些目录节点被某个机构管理。(4).管理层由那些可能经常变动的节点组成，由系统管理员和用户共同完成。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

Unix文件系统命名图的实现通过一个逻辑磁盘上相邻的一些块完成的，这些块被分为引导块(bootblock)、超级块(superblock)、一系列的索引节点(indexnodes—inodes)和文件数据块(filedatablocks)。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

Unix文件系统命名图的实现(1).引导块是一个特殊的块，当系统启动时该块中的数据和指令自动地被装入到内存中，通过该块中指令的执行将操作系统装入到内存中。(2).超级块保存着整个文件系统的有关信息，这些信息包括文件系统的大小、磁盘中哪些块还未被分配、哪些索引节点未被使用等等。(3).每个inode除了包含它所对应的文件的数据可以在磁盘中什么地方找到的确切信息外，还包含它的属主、产生的时间、最后一次修改的时间和保护等信息。每个目录都有一个带唯一索引号的inode，所以，命名图中的每个节点的标识符是它的inode索引号。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

DNS的部分命名空间

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

DNS的部分命名空间

(1).

DNS的名字空间：DNS的名字空间被一个树形图组织成分层结构。弧的标号是由数字和字母组成的字符串，标号的最大长度为63个字符。一个路径名的最大长度为255个字符，一个路径名是由一串标号组成的，起始的标号在路径名的最右边，标号之间由点(“.”)分隔，根节点也用点“.”表示。例如一个路径名root:<cn,edu,jlu,ftp>在DNS中表示为.，最右边的点“.”代表根节点，但是在使用中常将最右边的点“.”省略。

(2).域(domain)：DNS名字空间中的一个子树称为一个域(domain)，到达这个子树的根节点的路径名称为这个域的域名(domainname)。正如路径名有绝对路径名和相对路径名一样，域名也可以是绝对域名和相对域名。

(3).

DNS的名字空间被划分为不重叠的部分，这些部分被称为分区(zone)，一个分区是名字空间的一部分，由一个独立的名字服务员来实现。

(4).资源记录(resourcerecords)。DNS名字空间中节点所包含的内容由一些资源记录所组成，资源记录有不同的类型。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

4.名字解析(1).名字解析通常是一个迭代的过程，通过该过程，名字被反复地送到命名上下文中。(2).在解析一个名字时，该名字首先被送到某个初始命名上下文中；随着更深的命名上下文以及派生名的输出，解析过程不断进行。(3).解析过程的另一个迭代特性是别名的使用。(4).解决解析过程不终止的办法：一旦到达解析的阈值就停止解析；管理员禁止任何会带来循环的别名。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

4.名字解析

在名字空间中，根据节点的路径名，就可以寻找到这个节点所存储的任何信息，这个查找的过程就称为名字解析

名字解析过程：N:<label-1,label-2,…,label-n>：这个路径名的解析是从命名图中节点N开始的，首先在节点N的目录表中查找名字label-1，得到label-1所代表的节点的标识符；然后在label-1所代表的节点的目录表中查找名字label-2，得到label-2所代表的节点的标识符；此过程一直进行下去，如果N:<label-1,label-2,…,label-n>在命名图中是实际存在的，就能够得到label-n所代表的节点的标识符，从而得到该节点的内容。

名字解析的每个过程都分为两步完成：第一步是找到对应节点的标识符，第二步是通过该标识符找到对应节点的内容。例如一个UNIX文件系统，如果一个节点是一个目录，首先我们要找到节点的inode号，通过inode号我们知道实际的目录表存放在磁盘的什么位置；如果一个节点是一个文件，首先我们要找到节点的inode号，通过inode号我们知道实际的文件数据存放在磁盘的什么位置。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

4.名字解析

名字空间进行合并的机制有两种：安装(mount)机制；设置一个新的根节点。在分布计算系统中，要安装一个外部名字空间至少需要如下信息：访问协议名字，服务员名字，外部名字空间中被安装点的名字外部名字空间中被安装点的名字，如nfs:////home/xu，nfs是访问协议名字，是服务员名字，/home/xu是外部名字空间中被安装点的名字；

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

4.名字解析

设置新的根节点：设置一个新的根节点，现有的各名字空间的根节点变成此新的根节点的子节点；原先的绝对路径名使用时改为相对路径名，每个机器包含一个隐含节点标示符，此节点添加到绝对路径名前，变成相对路径名名。如下图：/home/xu/keys→n0:/home/xu/keys

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.1命名

4.名字解析

分布式系统中的名字空间的实现：大规模分布计算系统中名字空间的组织方式。

全局层由最上层的一些节点组成，这些节点包括根节点和它的一些子目录节点组成。用来代表一些机构，这些机构的名字保存在名字空间中；

组织层由一个机构内的所有目录节点组成，这些目录节点被某个机构管理；

管理层由那些可能经常变动的节点组成。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.2加密

分布式系统中，保障安全的两种方式：一个是加密技术，包括对数据及通信系统的加密；另一个是访问控制。(1).数据加密主要研究对数据加密的算法、算法实现的效率等问题(2).计算机网络的安全保密：计算机网络的目的是资源共享，同时也是分布计算系统、网格系统的基础平台，但网络容易产生不安全和失密问题。方便并且行之有效的方法是采用加密技术，实现用户到用户之间的加密，确保数据在网络传输过程中(特别是通信系统中)不丢失和被窜改(3).访问控制：像多用户单机系统那样，规定什么人可以访问系统的什么数据，得到何种服务，并对用户进行身份鉴别，对他们的访问权限加以限制(授权)。上述三个问题归并成两个：加密技术，访问控制

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.2加密

加密的概念。(1).加密和解密：加密意味着发送者将信息从最初的格式改变为另一种格式，将最终不可阅读的消息通过网络发送出去。解密是加密的相反过程，它将消息变换回原来的格式

(2).加密和解密的过程：(3).加密和解密的方法分为两种类型：传统方法和公开密钥方法。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术加密算法解密算法网络发送者接收者KeKd1.3.2加密

位置交换法实例密钥MEGABUCK明文：pleasegivemethebooks,whenyoucomeupnext.

密文：abhcnsmoeoeketlveupeewgtsy.pih,oueeonmx

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.2加密

2.共享密钥加密方法(对称式加密)(1).在信息的加密和解密上使用同一个密钥，也称为对称密钥或者单密钥。(2).DES(dataencryptionstandard)就是一种典型的对称式加密法。(3).实际应用中，为提高安全性，常采用多重加密解密技术，如三重DES。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.2加密

DES加密(1).算法使用64比特的原文和56比特的密钥，原文经过19个不同而复杂的过程来产生一个64比特的密文。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.2加密

3.公开密钥加密方法(非对称式加密)(1).在信息的加密和解密上使用不同的密钥，通常有两个密钥，称为公钥和私钥。(2).加密算法和解密算法公开，加密密钥不保密，解密密钥保密。(3).实用的公开密钥方案都使用大数的陷门函数产生密钥。(4).典型代表是RSA

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.2加密

RSA加密(1).加密算法(a).选择两个素数，p和q。(b).计算n=p×q和z=(p-1)×(q-1)。(c).选择一个与z互质的数d。(d).找出e，使得e×d=1modz。确定公开密钥和保密密钥：公开密钥由(e,n)构成，保密密钥由(d,n)构成。(2).加密过程设X是明文，计算Y=Xe(modn)，则Y就是密文。(3).解密过程设Y是密文，计算X=Yd(modn)，则X就是明文。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.2加密

RSA加密实例对明文“SUZANNE”进行加密。在此例子中我们只考虑英文大写字母的加密，我们可以对英文字母A~Z按顺序编码为1~26。在该例子中，我们选择p=3，q=11，得到n=33，z=(p-1)×(q-1)=2×10=20。由于7和20互为质数，故可以设d=7。对于所选的d=7，解方程7e=1(mod20)，可以得到e=3。

加密结果

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.2加密

RSA加密实例对明文“SUZANNE”进行加密。在此例子中我们只考虑英文大写字母的加密，我们可以对英文字母A~Z按顺序编码为1~26。在该例子中，我们选择p=3，q=11，得到n=33，z=(p-1)×(q-1)=2×10=20。由于7和20互为质数，故可以设d=7。对于所选的d=7，解方程7e=1(mod20)，可以得到e=3。

加密结果

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

1.非法用户通过非授权访问，产生的威胁大概分为以下几类：

(1).泄露，未经授权的接收方获得了信息。

(2).篡改，未经授权就对信息进行改动。

(3).恶意破坏干扰系统的正确操作，对破坏者本身无益。2.保护的目标和要求(1).保护的目标：保护机构阻止非法用户偷用磁盘空间、文件系统、处理机，读其他人的文件，修改别人的数据库及干扰别人的计算。保护机构还有其他作用，帮助检测程序中的差错，防止用户错误操作以及用于项目管理等(2).保护机构要解决以下几个基本问题:保密性：用户必须能秘密地保存数据，不被其他用户看见;专用性：必须保证用户给出的信息仅用于达到预想的目的;真实性：提供给用户的数据必须是真实的，也就是说，如果某些数据声称来自X，则该用户必须能够验证此数据确实是由X送来的;完整性：存放在系统中的数据不会被系统或未被授权的用户破坏。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

按照通道被误用的方式，攻击的方法分为以下几类：

(1).窃听，获取未经授权的消息副本。(2).伪装，未经授权而使用其他主体的身份收发消息。(3).消息篡改，在消息传往接收者之前，截获并修改其中的内容。(4).存储截获的信息，并在以后发送它们。这种攻击对已认证的消息和加密消息可能都有效。(5).拒绝服务，用大量的消息淹没通道或者其他资源(如缓冲区)，使得其他访问被拒绝。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

公开密钥加密技术实现数字签名：

(1).实现数字签名，要解决两个问题：第一，接收者能验证所要求的发送者的身份；第二，发送者在发送已经签名的报文后不能否认。

(2).公开密钥加密技术实现数字签名要求加密函数E和解密函数D满足下列条件--就是E和D可以互换：E(D(P))=P，当然同时还有D(E(P))=P。

(3).公开密钥加密技术实现数字签名的过程:

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

单密钥加密技术实现数字签名：

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

使用报文摘要实现数字签名：

(1).报文摘要：使用单向散列(hash)函数可以从一段很长的明文中计算出固定长度的比特串。这个比特串通常被称为该报文的摘要(messagedigest)。

(2).报文摘要具有三个重要的属性：给出报文P就很容易计算出其报文摘要MD(P)；只给出MD(P)，几乎无法推导出P；无法生成这样的两条报文，它们具有同样的报文摘要。

(3).报文摘要实现数字签名的过程:A首先计算P的报文摘要MD(P);A用自己的保密密钥对MD(P)进行加密以达到签名的目的;A将报文摘要的签名形式DA(MD(P))连同明文P一起发送给B;B用A的公开密钥解密DA(MD(P))，从而得到MD(P)，验证是否是A发送的;B通过明文P重新计算MD(P)，发现是否有非法用户修改报文P。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

权能的保护：

(1).访问矩阵：矩阵中的项Aij含有用户j对对象i的一些访问权限，它由一些数值代表对一个文件的读、写，或一个程序的执行，或对一个终端的连接，或改变权限等。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

权能的保护：

(2).权能：因为这个矩阵的很多项都是空的。有两种主要方法在实际系统中使用，实现访问控制：按行或按列列表。访问矩阵中对应Oi那一列说明可以访问对象Oi的所有的域，叫做关于Oi的访问控制表。另一种存储访问矩阵的方法是取一行列表，叫做权能(capability)表，它对应于一个域Dj，而不是对应某个对象。权能表的每一项叫做一个权能，由对象名和一套对此对象操作的权利组成。

(3).使用单密钥加密技术保护权能:

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

权能的保护：

(3).使用公开密钥加密技术保护权能:

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

分布系统中访问位置的控制：

(1).向终端和主机传送对话密钥:

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

分布系统中访问位置的控制：

(1).向用户和主机进程传送对话密钥:其他具有访问终端的密钥的用户不能伪装成用户U，主机上知道主机密钥Kh的其他进程也不能伪装成目的进程P

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

1.访问控制

(1).自主访问控制模型(DAC)(a).允许资源的拥有者显式地指定其他用户是否可以访问该资源。(b).一般采用访问控制矩阵和访问控制列表来存放各个主体之间的访问控制信息，限制各个主体的访问权限。

(c).具有灵活性，广泛应用。(d).缺点：在大型系统中，访问矩阵或访问列表非常庞大，且空元素多，造成资源浪费；客体的拥有者能否授予或者取消对客体的访问权限，造成管理困难；无法实现多级安全策略。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

1.访问控制

(2).强制访问控制模型(MAC)(a).系统强制各个主体遵守系统制定的访问控制策略。(b).在执行访问控制时，系统对主体和访问资源的安全级别进行比较，再决定是否可以访问。

(c).缺点：用户均可以写访问系统中安全级别最低的资源；对无等级关系的信息没有相应的处理模型。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

1.访问控制

(3).基于角色的访问控制模型(RBAC)(a).将访问权限与角色相关联。(b).把现实和计算机访问控制策略更好地结合起来，易于实现复杂、动态的访问控制策略。

(c).缺点：对没有角色区别的机构不适合。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

2.数字签名

(1).定义两种互补运算，一个用于签名，一个用于验证。(2).签名时用私钥，验证时用公钥。(3).公钥必须向接收者信任的人注册。

(c).缺点：对没有角色区别的机构不适合。

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通信

1.6数据共享

1.4死锁问题

1.5容错技术1.3.3保护

2.数字签名使用数字签名的原因：(1).身份认证(2).数据完整性(3).数据保密性(4).不可否认性

第一章分布式系统基础知识Icsu1.3命名与保护

1.1分布式系统概述

1.2进程间通