12.6  练习

Exercises

12.1  请给出一个“温和”竞态条件的实例。也就是说，其效果将影响到程序的行为，但并不影响正确性。

12.2  按照我们的定义，线程包的就绪表里包含着所有可运行但当时没有在运行中的线程，另用一个变量标识当前正在运行的线程。能否更简单地定义就绪表包含所有可运行线程，当前表头的那个进程是否就是正在运行的？（提示：考虑多处理器的情况）。

12.3  请设想你正在写代码来管理一个散列表，这一散列表将由几个并发线程共享。假定对表的操作需要是原子的。你可以用一个互斥锁去保护整个表，或者也可以开发一种模式，用一个锁管理散列表的一个桶。哪种方式在哪种环境中可能工作得更好些？为什么？

12.4  典型的自旋锁里只保存一个字节的数据，但需要用一个完整的字做存储，因为硬件里只能原子地读、修改、写完整的字。但请考虑前面练习里的散列表例子。如果我们的选择是对散列表的每个桶用一个锁，请解释如何实现一种“两层”的锁模式，其中结合了一个针对整个散列表的常规自旋锁，以及对每个桶一个二进制位的锁定信息。请解释为什么这种模式可能正是我们所希望的，特别是对于有外部链的散列表。（提示：参看Stumm等的论文 [UKGS94]。）

12.5  在计算最密集的科学应用中有许多“老旧陈腐”的Fortran程序，它们通常都非常老也非常复杂。有时需要花数以年计的时间才能把一个老旧程序重新写成能在并行机上运行的程序。一种很有吸引力的想法是开发出一个编译器，使之能够自动把老程序“并行化”。请解释为什么这绝不是一项容易完成的工作。

12.6  12.3.1节的load_linked和store_conditional（LL/SC）指令很像早期的一种称为compare_and_swap（CAS）通用原子指令。CAS是IBM 370体系结构引进的，也出现在x68和Sparc V9指令集里。它取三个参数：需要修改的位置，期望该位置里包含的值，以及当（且仅当）在那里可以找到所期望的值时想要放进去的新值。与store_conditional类似，CAS也返回一个指示字说明操作是否成功。在例12.27中给出的用load_linked和store_conditional实现的原子性的加指令序列，用CAS写出是下面的样子：

请讨论LL/SC和CAS各自的比较优势。考虑如何在缓存一致性的多处理器系统上实现它们。是否存在一些情况，其中一组指令工作得好而另一组指令不行？（提示：请考虑一些算法，其中的线程需要触动多个存储器位置。再考虑一些算法，其中一个存储器位置的内容需要在改变之后保存。）

12.7  在大多数机器上，SC指令都可能因为几种原因之一而失败，包括在与之匹配的LL指令之后出现了中断。程序员必须采取什么步骤，才能保证算法在面对这种“不正确的”SC失败时也能正确工作？

12.8  从图12.10的test-and-test_and_set锁出发实现一种忙等待代码，它使读者能并发地访问数据结构，而写者将仍然需要把所有读者和其他写者锁在外边。你可以使用任何合理的原子指令（例如LL/SC）。请考虑公平性问题，特别是如果始终存在对访问数据结构有兴趣的读者时，你的算法应该保证写者不会被永远锁在外面。

12.9  在图12.12（第624页）中用于使调度器代码可重入的机制里，对应用程序的所有调度数据结构只使用了一个OS提供的锁。除其他情况外，这种机制将不允许其他处理器上的线程在毫不相关的信号量上执行P和V操作，即使这种操作根本不需要锁定。你可以为与调度器有关的操作设计另一种同步机制，使它能容许更高程度的并发性，而且同时仍然正确吗？

12.10 我们已经看到，能在多个OS进程上运行的线程包调度器，必须同时禁止时钟信号并获取一个自旋锁，该锁是保证就绪表和条件队列的完整性的安全卫。要在操作系统里实现进程，内核仍然要使用自旋锁，但这种自旋锁针对的是处理器而不是进程，是硬件中断而不是信号。不幸的是，内核禁止中断

绝不能超过很小的一段有限时间，否则许多设备可能就无法正确工作了。直接采用图12.12的代码是不够的，因为它可能企图在中断禁止期间去获取自旋锁（这是一个时间无界的操作）。类似的，内核也不能容忍先获取自旋锁之后再禁止中断，因为如果在这两个操作之间发生了中断，其他处理器就可能被迫自旋很长时间。请你考虑应该如何解决这一问题？（提示：请仔细观察位于reschedule中间的循环，考虑某种混合技术，使禁止中断和获取锁能成为一个操作。）

12.11 Rice大学的Mohit Aron和Peter Druschel提出了一种称为软计时器的机制 [AD00]。软计时器利用在许多现代处理器中可用的硬件周期计数器。这一计数器是一个特殊寄存器，非特权指令可以读，其内容以某种很高的频率自动更新，通常每微秒更新一次。除用于其他目的外，软计时器还能用于实现线程包的强占功能。在这里线程调度器并不要求OS内核在未来某个特定时刻发信号，而是自己做出安排，过一段时间去检查一下周期计数器，发现它超出某个预先计算出的值时就执行一次上下文切换。请比较软计时器与基于信号的计时器，讨论它们各自的长处和短处。

12.12 请说明如何把并发集合实现为一个排序的单链表。你的实现应该支持insert、find和remove操作，而且应该允许对表的不同部分的操作并发的发生（因此对整个表用一个锁就不够了）。（提示：你将需要考虑采用“行走锁”方法，其中的获取和释放操作并不是按LIFO顺序交错进行的。）

12.13 要使自旋锁能用于多道程序设计的多处理器系统，一种想法是保证没有进程能在临界区的中间被强占。得到这种性质的一个肯定安全的方式是在用户空间里自旋，因为持有锁的进程一定是在另外某个处理器上运行的，不会来强占或者需要当前这个处理器。请解释一下，为什么操作系统设计师可能不想给用户进程提供禁止强占的能力。（提示：考虑多用户和公平性。）你可以建议一种方法绕过这个问题吗？（在Kontothanassis、Wisniewski和Scott的论文 [KWS97] 里可以找到几种可能的解决办法。）

12.14 请说明如何借助于信号量实现n线程隔栏。

12.15 用负初始值声明信号量有意义吗？为什么？

12.16 请不要去看Hoare的解决办法，自己说明如何用信号量实现管程。

12.17 请说明如何用管程实现信号量。你的管程不变式是什么？

12.18 请说明如何用二值信号量实现一般信号量。

12.19 假定每个管程都有自己的互斥锁，因此不同线程可以在不同管程上并发运行，而且当一个线程在某个嵌套的调用上wait时，我们将同时释放外层和内层的互斥。当该线程被唤醒时，它将需要重新获得外层的那些锁。如何保证它具有这种能力？（提示：请考虑获取这些锁的顺序，并考虑放弃Hoare的语义。有关进一步的提示，可参考Wettstein的论文 [Wet78]。）

12.20 请说明如何用条件临界区域实现一般信号量，其中让所有线程都等待同一个条件，从而避免无意义唤醒带来的开销。

12.21 请利用Ada 95的受保护对象机制写出实现有界缓冲区的代码。

12.22 在Java里用synchronized语句或方法重做上一练习。请设法使你的解决方法尽可能简单并且概念清晰。你可能需要用到notifyAll。

12.23 请做出上一练习的另一个更高效的解，其中应避免使用notifyAll。（警告：人们经常会注意到缓冲区不可能同时为满而且为空，并因此假定等待的线程或者全为生产者，或者全为消费者。然而，事情未必是这样。如果缓冲区（即使是临时性地）变成了执行的瓶颈，就可能出现任意多个等待线程，其中可能既有生产者也有消费者。）

12.24 用Java的Lock变量重复上面练习。

12.25 请考虑在第492页简单提到的逃逸分析，解释它可能如何用于在Java里降低synchronised语句和方法的代价。

12.26 就餐的哲学家问题 [Dij72] 是同步的经典练习（见图12.25）。五位哲学家坐在一张圆桌周围，圆桌中间有一大盘共用的意大利面条。每位哲学家都反复思考一段时间然后吃一会，时间间隔由个人选择。圆桌上每对相邻哲学家之间有一把叉子。要想吃到面条，哲学家就需要与自己相邻的两把叉子，左边一把和右边一把。由于共享叉子，相邻的哲学家不可能同时吃面条。

    请为就餐哲学家问题写一个解，其中每位哲学家用一个进程表示，叉子用共享数据表示。对于叉子的同步访问用信号量、管程或条件临界区域表示。请提供尽可能高的并发性。

12.27 在前一练习中，你可能已经注意到就餐的哲学家很容易陷入死锁。必须关注的一种可能性是各位哲学家同时拿起了他们右手边的叉子，而后等着左边邻居吃完。

讨论你想到的处理这一死锁问题的各种可能策略。你能描述一种解法，其中可以证明不可能有任何哲学家永远饿着吗？你能描述一种解法，它在一种很强的意义上是公平的吗（也就是说，没有哲学家在很长的时间段里总能得到比别人更多吃的机会）？在Chandy和Misra的文章 [CM84] 里可以找到一个特别优美的解。

12.28 在某些并发程序设计系统里，全局变量由所有线程共享。在另一些系统里，每个新创建线程将得到全局变量的另一独立副本，通常用创建它的那个线程的全局变量的值进行初始化。在这种私用全局变量的方式中，所有共享数据都必须在一个特殊的堆里分配。还有另外一些程序设计系统，在其中程序员可以描述哪些全局变量是私用的，哪些是共享的。

请比较私用的和共享的全局变量之间的利弊。你希望可以用到哪种机制，用于哪种类型的程序？你怎么实现这两种东西？存在某些情况使一种机制比另一种更难实现吗？你的回答在怎样的程度上依赖于操作系统提供的进程的性质？

12.29 逻辑语言里的AND并行类似于函数式语言里（例如Multilisp）的参数并行求值。OR并行也存在类似的东西吗？（提示：考虑函数式语言里的特殊形式，10.4节。）你能建议一种方式，在Multilisp里得到OR并行的效果吗？

12.30 在12.3.6节里我们断言，AND并行和OR并行在Prolog里都是有问题的，因为它们与语言的语义所要求的确定性搜索顺序不符。请把这一断言说得更清楚一些，什么特殊情况下可能出错？

12.31 12.3.4节把管程看作一种同步访问共享存储器的机制，而且基于信号量描述了它们的实现。完全可以把管程看作一种用进程实现的模块，该进程可以接收来自其他进程的请求，执行适当的操作后回复。请给出与这一概念模型一致的管程实现，一定要注意包括条件变量。（提示：参看12.2.3节有关早回复的讨论，第611页。）

12.32 请说明怎样用共享存储器实现消息传递。特别的，请选择一套消息传递操作（例如，无等待发送和显式消息接收），并说明如何用你所喜欢的共享存储器记法实现。

12.33 在不可靠的消息上实现可靠消息时，发送方可以等待确认消息，如果在有界时间段内没有收到确认就重发。但接收方怎样知道它的确认消息已经被收到了呢？为什么发送方不必发出对于确认的确认（进而接收方发出确认的确认的确认）？（有关如何设计快速、可靠的规程的更多信息，读者可以查阅有关计算机网络的教科书，例如 [Tan02，PD03]。）

12.34 在Occam里，ALT语句的分支可以包含输入卫，即一种接收操作（?），只有当潜在的对方试图送来与之匹配的消息时，这个分支才可以被选。也可能设想允许写输出卫，即一个发送操作（!），只有在潜在通信对方试图接收与之匹配消息时，这个分支可以被选。Occam和CSP（按原始定义）都不允许输出卫。你能猜到是为什么吗？假定你希望支持这种功能，实现应该怎样工作？（提示：有关想法可以参考下面文章：Bernstein [Ber80]，Buckley和Silbershatz [BS83b]，Bagrodia [Bag86]，以及Ramesh [Ram87]。）

12.35 我们在12.4.3节描述了Ada的select语句里terminate分支的语义，当且仅当潜在的通信对方都已经终止，或者都停在带有terminate分支的select语句时，这一分支可能被选中。Occam和SR都没有提供这种功能，虽然原始的CSP建议中有。你考虑怎样在Ada里实现terminate？按照你的看法，为什么Occam和SR不要它？（提示：关于这方面的想法，请看Apt和Francez的文章 [Fra80，AF84]。）