2016年辽宁大学分布式操作系统习题整理资源-CSDN文库

需积分: 13 140 浏览量 2016-06-27 10:47:49 上传评论 3 收藏 15.12MB DOC 举报

资源推荐

资源详情

资源评论

2016 整理 JXY

2016 辽宁大学分布式操作系统思考题

（6）1 在交换式 Dash 多处理机系统中，为了保持缓存一致性，采用了 Dash 协议，某一簇

中的一 CPU 写一未缓存的数据块，之后另外一簇的另外一 CPU 读该数据块。试详细说明

写操作和读操作是如何进行的。

答：写操作：写数据块的 CPU 先在本地总线发送请求察看邻近 CPU 的缓存中

是否有该数据块。如果有，执行缓冲区到缓冲区的传送，如果块状态为干净宿

主所在簇的其他拷贝必须被置为无效。若邻近 CPU 的缓存中没有该数据块，本

次查找失败，数据块在其他地方，CPU 发送信包到其宿主所在簇。如果块为未

缓存，标记为脏并发送给请求者；如果块为干净，所有拷贝置为无效，标记为

脏并发送给请求者；如果块为脏，请求传送到拥有该数据块拷贝的远程簇，该

簇将自己的拷贝置为无效并满足写操作。

读操作：读数据块的 CPU 首先检查自己的缓存，若缓存中无此字，则在本地簇

中发出请求，询问本地簇的其他 CPU 缓存中是否有此字。如果有，该数据块从

该缓存传送到发出申请的 CPU 缓存中。若该块的状态是干净，拷贝此数据块。

若为脏，其目录将此块标记为干净，使之共享。如果数据块不在任何簇的缓存

中，CPU 发一请求信包给该块的宿主所在簇。宿主所在簇的目录管理硬件检查

它的表以确定其状态。若为未缓存或者干净，硬件从全局存储器中取出块，将

其发送到请求簇，该簇更新其目录，表明该块已在缓冲区中。若此处状态为

DIRTY，目录硬件查找拥有该块的簇的标志，该簇相应请求。拥有 DIRTY 块的

簇将数据块发送给请求簇，并因为数据已共享，将其状态改为 CLEAN，它还要

给宿主所在簇发回一个拷贝以更新存储器，此时块的状态置为 CLEAN。

（6）1-1 在基于环的多处理机系统 Memnet 中，通过令牌环进行通信，并且没有集中式全

局存储器，详细说明如何实现读写操作。

答：读操作：当 CPU 要从共享存储器中读一个字时，该存储器地址传送给

Memnet 设备，Memnet 设备检查表项以确定该块是否存在。若存在，读请求立

即得到满足。否则，Memnet 设备等待直到俘获循环的令牌，将请求信包送入环

中，并挂起 CPU。请求信包包含目标地址和 32 字节哑域。信包在环中传递的过

程中，每个 Memnet 设备 double 检查自己是否有所需的块，若有责将块置入哑

域，修改信包头使下一个机器不再重复此工作。若块中的互斥位置位，则清除

它。因为某数据块一定位于系统某处，因此当信包返回发送点时，一定包含了

所需的块。CPU 发出请求并存储块，满足请求以后释放 CPU。

写操作：若包含要写字的块存在于本地并且是系统中的唯一拷贝，字就在本地

写入。若所需块在本地存在但不是系统中的唯一拷贝，CPU 将在环中发出置无

效信包，强制其他机器抛弃此块的拷贝。当置无效信包返回时，将该块的互斥

位置位，字在本地写入。若本地不存在所需块，CPU 则发出包含读请求和置无

效请求的信包。第一个有此数据块的机器将该块拷入信包，同时抛弃自己的拷

贝。其余的机器仅从自己的缓存中抛弃该数据块。当信包返回到发送者时，本

地储存该数据块并执行写操作。

（6）2 在基于总线的多处理机系统中，遵循 write once 协议，假设有 C1，C2，C3，C4 四

个 CPU，一操作序列如下：C1 读一字 W1（只存在于共享存储器中）、C1 继续读该字、

2016 整理 JXY

会产生一致性问题。

（2）在客户端磁盘设高速缓存，用途是可以使用大量的数据，减少了网络延迟。

（3）在客户端主存中设置缓存，有三种选择来确定缓存的位置。

① 在每个用户进程自己的地址空间直接进行文件高速缓存。高速缓存由系统调用库管理。

当打开、关闭、读和写文件时，该库只是保存最常用的文件当进程退出时，所有被修改过

的文件都写回到服务器中②在内核中设置高速缓存，在任何情况下都需要内核调用。③高

速缓存管理作为一个用户进程，保持了内核独立于文件系统编码。易于编程，更加灵活。

解决一致性问题的四种算法：

1 直接写算法：（WRITE-THRONG 算法）当修改一个高速缓存项（文件或

块）时，新的值保存在高速缓存中并立即写到服务器。

2 延迟写：延迟写操作使得语义变得不清楚。当另一个进程读此文件时，它所

得结果取决于时间选择。延迟写只好在运行效率和清晰的语义之间权衡。

3 关闭时写：仅当文件关闭后才将文件写到服务器，与对话语义相配；

4 集中控制算法：当打开一个文件时，打开该文件的机器向服务器发送一条消

息。服务器保存谁打开了哪个文件以及打开是为了读还是写或者两者兼有。如

果文件是为读而打开，允许其他进程为读而打开，避免为写而打开。如果某个

进程为写而打开一个文件，必须禁止所有其他访问。当关闭文件时，必须报告，

以便服务器更新。

四种算法存在的问题：

直接写：有效，但不影响写流量。进程可能会读到过期值；高速缓存向任何客

户提供文件时，须先和服务器进行核对，这要付出一些时间代价。对写来说，

网络传输是相同的，就像根本没有高速缓存一样。

延迟写：效率较高，但可能语义不清。当另一个进程读此文件时，它所得结果取决

于时间选择。延迟写只好在运行效率和清晰的语义之间权衡。

关闭时写：与会话语义相配。如果两个已放入高速缓存的文件被依次回写，第

二个会覆盖第一个。解决此问题的唯一方法是注意它是否比第一次出现时已好

得很多了。当两个或多个客户同时进行高速缓存和修改同一文件，若各个文件连续关闭，

将它们的值送到服务器上，最后的结果取决于哪个文件最后关闭。

集中控制：UNIX 语义，但不健壮，不能规模化。尽管发送自发消息是肯定可

行的，但却非常生硬，必须要小心。

（5）4 给出实现文件复制的三种方法，并举例说明更新复制文件的 Gifford 算

法，并说明某些服务器崩溃时，应该采取什么措施。

答：文件复制的三种方法：

显式文件复制，是为编程人员控制整个进程而用。当进程产生一个文件时，可

以在其他服务器上生成另外的拷贝。如果目录服务存在允许一个文件有多个拷

贝，所有拷贝的网络地址都可以和这个文件名联系起来。

懒惰复制，只要在某个服务器上建立每个文件的一个拷贝，服务器自己在其他

的服务器上也可自动生成副本。

用组复制文件，所有的写系统调用同时传送到所有的服务器。于是，其他的拷

贝在原文件产生时就产生了。

Giord 算法基本思想是：要求客户在读或写一个复制的数据项之前向多个服务器提

出请求，并获得它们同意。读一个已有 N 个复制存在的文件时，客户需要获得一个读法定

数 Nr ，修改一个文件需要一个写法定数 Nw ， Nr 和 Nw 的值必须满足约束条件

Nr+Nw>N。即只有在适当数目的服务器参与时，文件才能被读或写。

2016 整理 JXY

举例：下面举一简单的例子来说明该算法是如何工作的：

当读一个已有拷贝的文件时，客户必须和超过半数的服务器联系，并请求

它们发送与该文件相联系的版本号。如果所有版本号相一致，则说明这是最新

的版本，如果企图只更新剩余服务器，会因为数目不足而失败。例如，有 5 个

服务器，客户已确定它们中的三个有版本号 8，则其他两个的版本号不可能是

9。因为任何从版本号 8 到版本号 9 的成功更新需要三个服务器同意，而不是两

个。

假设一共 12 个服务器，最近的写法定数由从 C 到 L 的 10 个服务器组成，

所有这些服务器得到了新版本和新版本号，任何随后的由 3 个服务器组成的读

法定数中将至少包含一个该集合中的成员。当客户查看版本号时，它将知道哪

一个是最新的并得到它。

解决办法：虚像表决通过为每个已经崩溃的服务器建立一个没有存储器的虚拟

服务器解决了这个问题。虚设者不允许出现在读法定数中 (毕竟它没有任何文

件)，但它可以加入写法定数中，在这种情况下，它只须去掉写入的文件即可。

只要有一个真实的服务器存在，写操作就能成功。当一个崩溃的服务器重新启

动时，它必须获得一个读法定数来找到最新的版本。在它开始正常工作之前，

它将为自己拷贝一份该拷贝。

（5）3-1 当两个或更多的用户共享相同的文件时，必须定义读和写的语义以避

免产生问题。说明分布式系统中处理文件共享的四种语义。

答：（1）UNIX 语义：在 READ 操作紧跟在 WRITE 操作后执行时，READ 操

作返回刚刚写入的值。同样，当一个 READ 操作跟在两个相连发生的 WRITE

操作后执行时，读入的值就是后一个写操作写入的值。

（ 2

）

解

决

办

法

—

对

话

语义

立即将高速缓存文件的所有修改回写到服务器上。简单、效率低。

规则：对一个打开文件的修改仅对修改该文件的进程是初始可见的，仅当文件

关闭时，其修改才对其他进程可见。（对话语义）

当两个或多个客户同时进行高速缓存和修改同一文件，若各个文件连续关闭，

将它们的值送到服务器上，最后的结果取决于哪个文件最后关闭。

（3）不可更改文件：对文件不能进行更改，只是简单的共享和复制。文件不能

被更新，但是目录可以更新。

（4）事务：

为了存取一个文件或一组文件，进程首先执行某种类型的开始事务处理原语，

以指示跟在其后的操作是不可分的。

2016 整理 JXY

然后通过系统调用来读写一个或多个文件

工作完成后，执行结束事务处理原语。

关键特性：保证了包含于事务处理中的所有调用都将按顺序完成，不能有其他

任何同时存在的事务处理的干扰

（5）5 试说明举例什么是有状态服务器，什么是无状态服务器，并对有状态和

无状态服务器进行详细的比较。

答：有状态服务器：服务器应该保存两个请求之间的客户的状态信息。毕竟，

集中式操作系统保存了关于活动进程的状态信息。

无状态服务器：当客户发送一个请求给服务器时，服务器完成请求，发送一个

应答，然后从内部表中移出该请求的所有信息。在请求之间，服务器不保存具

体客户的信息。

为了更好地理解这个差别，我们考虑拥有打开、读、写和关闭文件通用命令的

文件服务器。文件打开之后，服务器必须保存哪个客户打开了哪个文件的信息。

典型地，当一个文件打开时，客户将获得一个文件描述符或其他用于后续调用

的编号，以便识别这个文件。当有请求到来时，服务器就使用.文件描述符来确

定需要哪个文件。将文件描述符变换成文件本身的表就是状态信息。

对于不保留状态信息的服务器，每一个请求必须是独立的。为了使服务器能够

工作，它必须包含全文件名和文件中的偏移址。此信息增加了消息的长度。

研究状态信息的另一种方法是:如果服务器坏了并且它的所有表都永久性丢失了，

将会发生什么情况，当服务器重新启动时，它已不能再知道哪些客户打开了哪

些文件。以后对已打开文件进行读与写操作就会失败，而且如果有可能的话，

将完全由客户决定恢复。其结果是，不保留状态的服务器比保留状态的服务器

有助于更好地容错。这是赞成前者的理由之一。

正如我们已提到的那样，无状态服务器在本质上有更多的容错。不需要 OPEN

和 CLOSE 调用，这就减少了消息编号，特别对于那些整个文件用一次就可读

出的普通情况，服务器不用浪费空间来存放表。使用表时，如果太多的客户一

次打开太多的文件，则将表填满，从而不能打开新的文件。最后对于状态服务

器，如在文件们一开始客户出了故障，服务器就会处于困境中。如果它对此束

手无策，它的表最终将充满垃圾。如果它超时了还未打开文件，那么客户因两

个请求之间等待时间太长将被拒绝服务，而校正程序就会失去校正功能。无状

态服务就不存在这些问题。

有状态服务器也可以对这些问题进行处理。由于 READ 和 WRITE 消息并不是

必须包含文件名，所以他可以以更短些。这样就可使用更小的网络带宽。由于

关于打开文件(在 UNIX 项中，i 节点)的信息在文件关闭之前都可保存在主存储

剩余31页未读，继续阅读

评论收藏

内容反馈

jujuezaiai1992

粉丝: 0
资源: 2

2016年辽宁大学分布式操作系统习题整理

东北大学分布式操作系统课件

分布式操作系统（陆丽娜版）课后习题

东北大学博士分布式操作系统2007入学试题及答案

分布式操作系统 原理与实践 pdf

辽宁大学分布式操作系统22、23期末试题加答案（王龙主讲）

武汉大学硕士生分布式操作系统ppt课件

2007年东北大学博士入学考试试题-分布式操作系统

浅析分布式操作系统

分布式操作系统课件

分布式操作系统课件1

2021电子科技大学分布式系统最全整理.zip

分布式操作系统的课件

分布式操作系统算法Demo

分布式操作系统 分布式操作系统

分布式系统：概念与设计 练习题答案

分布式操作系统.rar

2021-2016电子科技大学分布式系统期末考试回忆版.pdf

2021电子科技大学分布式系统重点整理及20年回忆版试题

小米妙享3.3.0.652免认证安装

计算机组成原理 白中英 第六版 课后习题答案

2023-飞机免费社工机器人最新合集

DirectX修复工具V4.0增强版

王道408 计算机组成原理课件 2024新版ppt课件

玩客云刷机功能包（全套资料） 真·包教包会！！！ 玩客云刷机软件+玩客云刷机固件+固件刷写软件+openwrt固件+手把手教学

STEP7-MicroWIN-SMART-V2.8安装包

Fiddler下载，版本：5.0.20211.51073，2023年1月亲测win11可用

诺威达K2201刷机包，10.0版本，解决蓝牙不连接，放音乐一会就断

SolidWorks GB型材库.zip

最新资源

分布式操作系统原理与实践 pdf

分布式操作系统分布式操作系统

分布式系统：概念与设计练习题答案

计算机组成原理白中英第六版课后习题答案

玩客云刷机功能包（全套资料）真·包教包会！！！玩客云刷机软件+玩客云刷机固件+固件刷写软件+openwrt固件+手把手教学