2022秋学期 高级操作系统课件后习题

C0 引言

本文内容来自于对高级操作系统课程PPT后习题的整理与解答，部分章节课件后没有习题，且答案不一定完全准确，敬请批评指正；

本文所涉及的课程指东北某沿海高校，计算机学院硕士生必修课“高级操作系统”，课程资料包括课程PPT、教材《分布式系统原理与范型 第二版》1、《Distributed Systems Principles and Paradigms 2nd edition》2，以及网络资料。

1. 《分布式系统原理与范型 第二版》 作者: （美）特尼博姆 出版社: 清华大学出版社 原作名: Distributed Systems: Principles and Paradigms 译者: 辛春生 :出版年: 2008-6-1 页数: 490 ISBN: 978730217279 ↩
2. 《Distributed Systems Principles and Paradigms 2nd edition》:作者: Tanenbaum, Andrew S. / Steen, Maarten van 出版社: Pearson 出版年: 2001-9-1 页数: 803 ISBN: 9780131217867 ↩

C2 体系结构

  • (C2Q4)考虑一个进程链，该进程（链）由进程$P_1,P_2,\dots P_n$构成，实现了一个多层客户-服务器体系结构。进程$P_i$是$P_{i+1}$的客户，只有$P_i$得到$P_{i+1}$的应答之后，才能向$P_{i-1}$发出应答。如果考虑到进程$P_{1}$的请求-应答性能，这种组织结构主要存在什么问题？

    答：当n很大时性能可能会很差。两个连续层的通信可能会在不同的机器上，这样P1和P2的交互性能就取决于其他 n-2 层之间的交互性能。且，若进程链中的某台机器性能较差或者暂时无法联系，进程链的性能将显著下降。

    image-20230208165630557

C3 分布式进程管理

  • （C3Q1）比较在单处理器系统中，使用单线程文件服务器和使用多线程文件服务器读取文件有什么区别。假定需要的数据存放在内存的缓存中（概率为2/3），将花费30ms来接收请求、调度该请求并且完成其他必须的处理工作。否则需要磁盘操作，就需要额外多花90ms，在磁盘操作的过程中线程处于等待状态。

    • 如果服务器采用单线程，每秒能处理多少个请求？
    • 如果服务器采用多线程呢？

    答：

    • 对于单线程：

      也就是每秒50/3个

    • 对于多线程：磁盘操作涉及的等待状态可以交给其他线程，因此每个请求所需的时间就是接收请求与调度的30ms

      也就是每秒100/3个

    image-20230208165647579

  • （C3Q2）对服务器进程中的线程数目进行限制是否有意义？

    答：显然有，主要有两个原因：

    • 线程需要内存空间来设置私有堆栈，过多的线程可能会占据过多的内存使服务器无法正常工作
    • 对于操作系统来说，独立的线程往往以混乱的方式运行。在虚拟内存系统中构造一个相对稳定的工作集时很困难的，导致了许多页错误以及相应的I/O操作。过多的线程可能因为页错误而使得性能下降。甚至在那些内存正常的情况下，我们可能很容易看到内存的访问是按照混乱的模式进行的，从而导致缓存毫无用处。这可能会导致性能甚至不如单线程。

    image-20230208165540030

  • （C3Q10）列举通过生成进程来构建并发服务器与使用多线程服务器的优点和缺点。

    答：一个重要的有点是独立的进程时相互保护的，这是很有必要的，例如在超级服务器上处理独立的服务。另一方面，进程的产生是的代价是相对较高的，这些代价在多线程服务器中可以被节省。此外，如果进程间需要通信，使用线程的代价相对低得多，因为在许多情况下我们可以避免使用内核通信。

    image-20230208171234167

C5 命名系统

  • （C5Q12）假设某个移动实体几乎不会离开域D，即使离开也很快返回。如何利用该信息在分层定位服务中加快查询操作的速度？

    答：只需要在实体的标识符中对域D进行编码，该标识符被用于查询查询实体的操作。这样查询操作就可以立即被转发到目录节点dir（D）中，并从这里开始继续搜索。

    image-20230208173634947

  • （C5Q14）假设一个实体从位置A转移到位置B，期间经过了几个中间位置（停留时间都很短），最终到达B。在分层定位服务中更改地址可能花费较长时间，因此在经过中间位置时，应避免更改地址没那么经过中间位置时应该如何查找该实体？

    答：将分层定位于与转发指针相结合。当实体开始移动时，在A出留下一个转发指针指向其下一个（中转）位置。每次移动时，都在移动开始处留下一个转发指针。直到到达B，将实体的新位置插入到分层定位服务中。转发指针链随后被清理，而A的原位置被删除。

    image-20230208173714431

  • （C5Q13）在深度为k的分层定位服务中，当移动实体改变它的位置时，最少需要更新多少条位置记录？最多需要多少条位置记录？

    答：改变位置可以被描述为一次插入与一次删除操作的结合。一次插入操作最多要求改变k+1条记录。同样的，一次删除操作最多要求修改k+1条记录。而根节点的记录修改可以被两个操作所共享，也就是仅需要修改一次根节点的记录。因此最多需要修改2k+1条记录。

    显然，修改记录最少时，要求k=1，此时，最少需要修改3条记录。

    image-20230208173728455

C6 同步

  • （C6Q11）分布式互斥算法中，建议所有的请求都被应答（同意或否定），这样可以检测出崩溃的进程，但是否还有其它问题？

    答：假定某进程P拒绝了请求随后崩溃了。这样请求进程认为P仍然运行，但授权永远不会到来。一个解决办法是让请求进程不阻塞，而是在休眠一个固定时间后，轮询所有之前拒绝过的进程，看它们是否仍在运行。

    image-20230208175108658

  • （C6Q8）许多分布式算法需要协调者，与集中式协调者相比，分布性体现在哪里？

    答：在集中式算法中，通常由一个固定的进程作为协调者。分布式的情况下，不同的进程在不同的机器上运行。在分布式算法中，有不固定的协调者。协调者是由构成算法的一部分进程举（分布式的方式）产生的。这样的协调者并没有让算法的分布程度降低。

    image-20230208175122437

C7 一致性和复制

  • （C7Q20）一个文件被复制在10个服务器上，列出基于法定数目的协议允许的所有读团体和写团体。

    答：允许的读团体和写团体有（读团体，写团体）：（1，10），（2，9），（3，8），（4，7），（5，6），（6，5），（7，4），（8，3），（9，2），（10，1）。

    image-20230208180043401

C8 容错性

  • （C8Q7）下面情况下，最少一次语义合适还是最多一次语义合适？

    • 从文件服务器读写文件
    • 编译一个程序
    • 远程银行

    答：对于从文件读写文件、编译一个程序来说，可以使用最少一次语义，因为多次并没有问题。对于远程银行来说，使用最多一次语义，因为如果失败，用户必须干预并清理上一次的残留。

    image-20230208181619861

    image-20230208181628495

  • （C8Q14）下图中，FIFO和全序结合情况下。可能的消息发送顺序？

    image-20230208154811269

    答：可能的发送顺序有：

    • m1, m2, m3, m4
    • m1, m3, m2, m4
    • m1, m3, m4, m2
    • m3, m1, m4, m2
    • m3, m4, m1, m2
    • m3, m1, m2, m4

    image-20230208181504870

    image-20230208181537586

    image-20230208181555028

C9 分布式安全

  • (C9Q10) Assume Alice wants to send a message m to Bob. Instead of encrypting m with Bob’s public key $K_B^+$, she generates a session key $K_{a,b}$ and then sends $[K_{A,B}(m),K^+_B(K_{A,B})]$.Why is this scheme generally better? (Hint: consider performance issues.)

    答：因为会话密钥（session key），具有短且固定的长度，而消息m的长度是任意的。这样的特性导致组合使用会话密钥与公钥加密短消息能够得到更好的性能，而只使用公钥对长信息加密的性能相对较差。

    image-20230208184510431

  • (C9Q19) The Diffie-Hellman key-exchange protocol can also be used to establish a shared secret key between three parties. Explain how.

    答：假定Alice、Bob、Chunk想要基于两个公开的大素数$n$和$g$建立共享密钥。Alice拥有一个不公开的大数$x$，Bob拥有不公开的大数$y$，Chunk拥有不公开的大数$z$。Alice将$g^x \mod n$发送给Bob；Bob将$g^y\mod n$发送给Chunk；Chunk将$g^z\mod n$发送给Alice。接下来，Alice计算$g^{xz}\mod n$，并将计算的结果发送给Bob；这样，Bob可以计算$g^{xyz}\mod n$；同时，在Bob接收到Alice发送的$g^x \mod n$后，可以计算$g^{xy}\mod n$，并将计算的结果发送给Chunk；这样，Chunk可以计算$g^{xyz}\mod n$；同时，在Chunk接收到Bob发送的$g^y \mod n$后，可以计算$g^{yz}\mod n$，并将计算的结果发送给Alice；这样，Alice也可以计算$g^{xyz} \mod n$。通过上述操作就建立了一个三方之间的共享密钥。

    image-20230208184330184

  • (C9Q20) There is no authentication in the Diffie-Hellman key-exchange protocol. By exploiting this property, a malicious third party, Chunk, can easily break into the key exchange taking place between Alice and Bob, and subsequently ruin the security. Explain how this would work.

    答：假定Alice和Bob使用公开的n和g，当Alice发送$g^x\mod n$给Bob时，Chunk只需拦截该信息，返回其自己的信息$g^z\mod n$给Alice，这样可以让Alice相信她正在与Bob交谈。类似的，在Chunk拦截Alice的信息后，他可以发送$g^z\mod n$给Bob，并等待Bob返回$g^y\mod n$作为应答。Chunk现在作为中间人了

    image-20230208183812568

赏

Learn and Live