高级操作系统

分布式系统概念：一个分布式系统是若干个独立的计算机的集合，但是对该系统的用户来说，感觉该系统就像一台计算机一样。

分布式操作系统：是对分布式系统提供资源管理的软件系统。通常表现为中间件形式。

一、分布式系统的关键目标。

分布式系统的4个关键目标：

1) 必须是资源共享的。要让用户方便地访问资源，并且以一种受控的方式与其他用户共享这些资源。

2) 必须是透明的。使分布式系统能够在用户和应用程序面前呈现为单个计算机系统。

3) 必须是开放的。它根据一系列准则来提供服务，这些准则描述了所提供服务的语法和语义。说明良好的接口定义允许需要某个接口的任意进程与提供该接口的进程进行通信。

同时它也允许独立的双方各自完成截然不同的接口实现，这样就会出现运行方式完全相同的两个独立的分布式系统。

4) 必须是可扩展的。可以通过三个方面来度量。首先，系统要能在规模上扩展，即可以方便地把更多的用户和资源加入到系统中去。

其次，如果系统中的用户和资源可以相隔极为遥远，这种系统就称为地域上可扩展的系统。最后，系统在管理上是可扩展的，也就是说，即使该分布式系统跨越多个独立的管理机构，仍然可以方便地对其进行管理。

二、中间件的特点。

中间件在体系结构中的位置：分布式系统由独立的计算机组成，但同时隐藏了其中单个计算机在系统里所承担任务的细节。即使分布式系统中某些部分可能暂时发生故障，但其整体在通常情况下总是保持可用。

用户和应用程序不会察觉到哪些部分正在进行替换和维修，以及加入了哪些新的部分来为更多的用户和应用程序提供服务。

为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“软件层”组织起来，该“软件层”在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的低层之间。

作为中单件组织的分布式系统。中间件层延伸到了。

多台机器上，且为每个应用程序提供了相同的接口。

中间件在应用程序和分布式平台之间形成了一个层，一个重要的目的是提供一定程序的透明性，也就是一定程序上向应用程序隐藏数据处理的控制的分布性。

在实践中常见的中间件系统实际上是遵循一定的体系结构风格的。

使中间件按照特定的体系结构整合到系统中，有利于使应用程序的设计变得更简单。

分布式系统的软件体系结构，主要以中间件为基础，是庞大则复杂的。在很大程度上，这种庞大和复杂性是来自于提供分布式透明性的要求的。同时，应用程序具有特定的额外功能要求，这与完全实现透明性是相冲突的。

这种通用性和特殊性需求之间的冲突，使得中间件应是调试灵活的。但是，付出的代价是复杂性。

三、远程过程调用（rpc）通信模型的基本原理及主要步骤。

rpc的目的在于将消息传递的大部分复杂性隐藏起来，它比较适用于客户-服务器应用程序。

客户存根程序：主程序端的子程序**。

服务器存根程序：子程序端的主程序**。

1) 客户过程以普通方式调用客户存根。

2) 客户存根建立消息并调用本地操作系统（激活内核陷阱）

3) 客户端操作系统将消息发送给远程操作系统（内核将消息发送到远程内核）

4) 远程操作系统（内核）将消息送到服务器存根。

5) 服务器存根取出消息中的参数后调用服务器的过程。

6) 服务器完成要求的操作后将结果返回至服务器存根。

7) 服务器存根将它打包成消息并调用本地操作系统（激活内核陷阱）

8) 服务器操作系统（远程内核）将含有结果的消息发送回客户端操作系统（客户内核）

9) 客户端操作系统（客户内核）将消息交给客户存根。

10) 客户存根从消息中取出结果返回给客户。

总的来说，将客户过程对客户存根发出的本地调用转换成对服务器过程的本地调用，而客户和服务器都不会意识到有中间步骤的存在。

四、lamport逻辑时钟算法基本原理。

c(a)表示事件a的时钟值。性质：

if a b;则c(a) a,b c(a) c(b)

c是递增的。

校正时间的操作是给时间加上一个正值，而不能是减掉一个正值。

校正算法。a b，if c(b)三个进程，各有自己的局部时钟，它们速率不同。

通过lamport算法，校正时钟。

实现lamport逻辑时钟，每个pi维护一个局部计数器ci。这些计数器按如下步骤进程更新：

pi在执行一个事件之前，pi执行ci←ci+1

pi在发送消息m给pj时，时间戳ts(m) ←ci

pj接受到消息m后，cj←max

举例：全序多播（一次将所有的消息以同样的顺序传递给每个接收的多播操作）

问题：两个进程分别对同一个复制数据库进行更新时，造成不一致状态。

原因：全局次序不一致。u1→u2; u2→u1

解决方案：全序多播。

发送进程多播发送消息m时，给m带上当前时间戳ts。当接收进程收到消息m后，存放其局部队列q，按时间戳排序接收进程向所有进程多播发送应答。当消息m被所有进程应答，且排在队列q队首后，方可处理。

定理：各个进程的局部队列的值最终都相同。

五、进程三态及转换关系。

1 – 进程a等待输入而暂停执行，进入阻塞队列。

2 – 时间片到，进程a暂停执行，进入就绪队列，调度器选择另一个就绪进程b

3 – 启动进程b运行。

4 – 当输入完成后，进程b进入就绪队列

六、选举算法（基于环的算法）基本原理。

所有进程按物理或逻辑顺序排序，形成一个环，那么每个进程就都知道它的后继者是谁了。

任何一个进程发现协调者失效后，就构造一个带有自己进程号的e消息，并将该消息发送给它的后继者。如果后继者崩溃了，发送者沿着此环跳过它的后继者发送给下一个进程，或者再下一个，直到找到一个正在运行的进程。在每一步中，发送者都将自己的进程号加到该消息列表中，以使自己成为协作者的候选人之一。

最终，消息返回到发起此次选举的进程。

七、进程迁移。

在迁移**的时候，我们常常需要在不影响进程对资源的绑定的条件下改变指向资源的引用。改变引用的具体方式取决于资源能否与**一起迁移到目标机器上去。更明确地说，需要就资源对机器的绑定方式进行考察，并区分为下列几种情况进行考虑。

未连接资源：可以方便地在机器之间移动，这种资源一般是与要迁移的程序相关的数据文件。

附着连接资源：也可以进行复制或者移动，但是开销相对来说比较大。

附着连接资源的例子包括本地数据库以及完整的web站点。虽然这种资源在理论上并不领带于当前的机器，但是将它们移动到另外的环境中去的做法通常并不可行。

最后还有一种坚固连接资源，这种资源紧密地绑定到特定的机器或者环境，无法进行移动。本地设备一般是坚固连接资源。本地通信端点是另一个坚固连接资源的例子。

将这三种类型的进程对资源的绑定与三种类型的资源对机器的绑定结合起来，就会产生9种组合形式，这些形式可供我们在考虑**迁移时采用。

进程对资源绑定。

gr创建一个系统范围的全局引用。

mv移动资源。

cp复制资源的值。

rb将进程重新绑定到本地可用资源。

在向另一台机器迁移**时，根据引用本地资源方式的不同所应该采取的不同做法。

八、顺序一致性。

顺序一致性是一种重要的以数据为中心的一致性模型。任何执行结果都是相同的，就好像所有进程对数据存储的读、写操作是按某种序列顺序执行的，并且每个进程的操作按照程序所制定的顺序出现在这个序列中。

规则：所有进程执行的结果，等同于它们的操作按某种顺序在数据仓上执行的结果。每个进程的操作都按照程序规定的顺序。

例：3个并行执行的进程。

90种正确的执行顺序。

九、写读一致性简单实现，数据存储要求及方式。

一个客户在对数据项x读操作之后对x的写操作，必须在x已读出的相同值或者更近的值之上进行。

例：bbs跟帖（读文章a,写文章b）

示例：符合写跟随读一致性。

不能保证写跟随读一致性。

十、拜占庭故障如何处理及思想。

拜占庭将军协定问题：假设通信是可靠的，但进程可能是不可靠的。

例：3个忠诚将军，1个叛变将军。

lamport递归算法。

共4步：(a)对外报告(b)收集向量(c)报告向量(d)生成结果向量：（1，2，未知，4）

若三个将军中，有两个忠诚将军，一个叛变将军，则不能判断出哪个将军叛变。

若要有m个进程出错的系统实现协同一致，最少要有2m＋1个正常进程。进程总数为3m+1。

需超过2/3多数，才能达成协定。

高级操作系统

高级操作系统

高级操作系统

高级操作系统

其他用户还读了