入临界区域的进程。在每次迭代中，进程在 cs 中设置的序号值将变得更加接近轮次，最后我们得出以下结论：只有进程 k 在 cs 中设置它的标识，而其他哪些序号在轮次和 k 之间不能在 cs 中设置它们的标识。这个进程仅能进入临界区域。
c.有限等待：有限等待需要满足以下事实：当进程 k 在打算进入临界区域时，它的标识不再置为空闲。任何序号不在轮次和 k 之间的进程不能进入临界区域。与此同时，所有序号落在轮次和 k 之间且又想要进入临界区域的进程能够进入临界区域（这是基于系统一直在进步的事实），这个轮次值变得越来越接近 k。最后，要么轮次变为 k，要么没有哪些序号在轮次和 k 之间的进程，这样进程 k 就进入临界区域了。
6.3 忙等待的含义是什么？在操作系统中还有哪些其他形式的等待？忙等待能完全避免吗？给出你的答案。
答：忙等待意味着一个进程正在等待满足一个没有闲置处理器的严格循环的条件。或者，一个进程通过放弃处理器来等待，在这种情况下的块等待在将来某个适当的时间被唤醒。忙等待能够避免，但是承担这种开销与让一个进程处于沉睡状态，当相应程序的状态达到的时候进程又被唤醒有关。
6.4 解释为什么自旋锁不适合在单处理器系统，而经常在多处理器系统下使用？答：自旋锁不适合在单处理器系统是因为从自旋锁中打破一个进程的条件只有在执行一个不同的进程时才能获得。如果这个进程没有闲置处理器，其他进程不能够得到这个机会去设定一个第一个进程进展需要的程序条件。在一个多处理器系统中，其他进程在其他处理器上执行，从而为了让第一个进程从自旋锁中释放修改程序状态。
6.5 如果一个同步元是在一个用户级程序中使用的，解释在一个单处理器系统中为什么通过停止中断去实现这个同步元是不适合的？答：如果一个用户级程序具有停止中断的能力，那么它能够停止计时器中断，防止上下文切换的发生，从而允许它使用处理器而不让其他进程执行。
6.6 解释为什么在一个多处理器系统中中断不适合同步元？答：由于只有在防止其他进程在一个中断不能实现的处理器上执行来停止中断，中断在多处理器系统中是不够的。在对于进程能在其他处理器上执行是没有心智的，所以进程停止中断不能保证互斥进入程序状态。 6.7
6.8 服务器能够设计成限制打开连接的数量。比如，一台服务器可以在任何时候有 n 个插座连接。这 n 个连接一形成，服务器就不能接收再有进来的连接直到一个现有的连线释放。解释为什么信号量能够通过服务器限制当前连线的数量而被使用。
答：信号量初始化为允许开放式的插座连接的数量。当一个连接被接受，收购方法调用。当连接释放时，释放方法调用。如果系统道道了允许开放式的插座连接的数量，相继调用收购方法将受阻直到一个现有的连线终止，释放方法调用。
6.9 证明如果获得和释放的信号量操作没有动态地执行，那么互斥会受干扰。
答：收购操作自动递减和信号量有关的值。如果两个收购操作在信号量的值为 1 的信号量上执行，而且这两种操作不是自动执行的，那么这两个操作在进展中会递减信号量的值，从而干扰互斥。
6.10(程序，不用翻)（6.13）
6.12 证明管程和信号量是相当于它们能在执行相同类型的同步问题时使用答：在用下列方法使用信号量时，管程可以实施。每个条件变量是由一个队列中的线程等待条件组成的。每个线程有一个和它的队列进入有关的信号量。当线程表现出等待操作时，它创造一个心得信号量（初始化为 0），附加信号量到和条件变量有关的队列中，在新创造的信号量上执行阻塞信号递减操作。
6.15 讨论在读者-作者问题中的公平和吞吐量的权衡问题。提出一种解决读者-作者问题而不引起饥饿的方法答：在读者-作者问题中吞吐量是由利益多的读者增加的，而不是让一个作家独占式地获得共同的价值观。另一个方面，有利于读者可能会导致饥饿的作者。在读者-作者问题中的借能够通过保持和等待进程有关的时间戳来避免。当作者完成他的任务，那么唤醒那些已经等了最长期限的进程。当读者到达和注意到另一个读者正在访问数据库，那么它只有在没有等待的作者时才能进入临界区域。这些限制保证公平。 6.16
管程的signal操作和信号量的signal操作有什么不同？
管程的signal操作在以下情况下是不能继续进行的：当执行signal操作并且无等待线程时，那么系统会忽略signal操作，认为signal操作没有发生过。如果随后执行wait操作，那么相关的线程就会被阻塞。然后在信号量中，即使没有等待线程，每个signal操作都会是相应的信号量值增加。接下来的等待操作因为之前的信号量值的增加而马上成功进行。 6.17
假设signal语句只能作为一个管程中的最后一条语句出现，可以怎样简化6.7 节所描述的实现？
如果signal语句作为最后一条语句出现，那么锁会使发出信号的进程转化成接受信号的进程。否则，发出信号的进程将解锁，并且接受信号的进程则需要和其他进程共同操作获得锁从而使操作继续下去。 6.21
假设将管程中的wait和signal操作替换成一个单一的构件await（B），这里B 是一个普通的布尔表达式，进程执行直到B变成真 a. 用这种方法写一个管程实现读者—作者问题。 b. 解释为什么一般来说这种结构实现的效率不高。
c. 要使这种实现达到高效率需要对await语句加上哪些限制？（提示，限制B 的一般性，参见Kessels[1977].）
a. 读者—作者问题可以进行以下修改，修改中产生了 await 声明：读者可以执行
“await(active writers == 0 && waiting writers == 0)”来确保在进入临界区域时没有就绪的作者和等待的作者。作者可以执行“await(active writers == 0 && active readers == 0)”来确保互斥。
b. 在signal操作后，系统检查满足等待条件满足的等待线程，检查其中被唤醒的等待线
程。这个要求相当复杂，并且可能需要用到交互的编译器来评估在不同时间点下的条件。可以通过限制布尔条件，使布尔变量和其他部分分开作为独立的程序变量（仅仅用
来检查是否相等的一个静态值）。在这种情况下，布尔条件可以传达给运行时系统，该系统可以执行检查每一个它所需要的时间，以确定哪些线程被唤醒。 6.23
为什么Solaris、Linux和Windows2000都使用自旋锁作为多处理器系统的同步机制而不作为单处理器系统的同步机制？
Solaris，Linux和Windows 2000中只有在多处理器系统才能使用自旋锁作为一个同步机制。自旋锁不适合单处理器的系统，因为打破了这一进程的自旋锁只有通过执行不同的进程才可以得到。如果这一进程不会放弃此处理器，其他进程就无法设置第一个进程所要求的程序条件，从而不能继续操作。在一个多处理器系统，其他进程执行其他处理器，从而修改程序状态从自旋锁中释放第一个进程。 6.24
在基于日志的系统中可以给事务提供支持，在相应日志记录写到稳定存储之前不能允许真正地更新数据项。为什么这个限制是必需的？
如果事务需要放弃，那么更新的数据项的值应该要恢复到原来的值。这就需要原来值的数据在进行操作之前完成更新。 6.25
证明两段锁协议能确保冲突的串行执行。
调度是指一个或多个事务的执行顺序。一个串行调度是指每个事务执行的原子调度。如果一个调度由两个不同的事务组成，通过连续的操作从这两个事务中获得相同的数据，并至少有一个write 操作，然后有所谓的冲突。如果一个调度可以通过一系列非冲突操作的交换而转化成串行调度，那么这个调度为是冲突可串行化。 这两阶段加锁协议确保冲突串行化，因为独占锁（这是用于写操作）必须连续收购，不释放任何锁在获取（增长）的阶段。其他事务希望获得同样的锁必须等待第一个事务开始释放锁。通过要求任何锁必须首先释放所有锁，从来避免潜在的冲突。 6.26
分配一个新时间戳给已经恢复到原值的事务有什么影响？对于新进入系统进程的事务，其所赋予的时间戳是如何大于原先事务的时间戳的？
在原先事务的访问变量改变后执行事务，那么相应的事务也恢复到原先的值。如果他们没有执行此项操作（也就是说没有重复的原先事务的访问变量值），那么这些操作在适当的时候就不会受到约束。 6.27
假设数目有限的资源中的一个单一的资源型必须加以管理。进程需要一定数量的这种资源，一旦用完将释放它们。例如，许多商业软件包提供了一定数量的许可证，这表明一些应用程序可以同时运行.当应用程序启动时，许可证的计数递减。当申请终止，许可证计数递增。如果所有的许可证都在使用，那么要求启动该应用程序的申请被剥夺了。只有当现有的许可证持有人终止申请并切许可证已经返还，那么这种申请将被授予.下列程序段是用来管理一个数目有限的 情况下的可用资源。最多的资源数量和一些可用的资源数量如下所示：
#define MAX RESOURCES 5
int available resources = MAX RESOURCES;
When a process wishes to obtain a number of resources, it invokes the decrease count()function:
/* decrease available resources by count resources */ /* return 0 if sufficient resources available, */ /* otherwise return -1 */ int decrease count(int count) { if (available resources < count) return -1; else { available resources -= count; return 0; } }
When a process wants to return a number of resources, it calls the de- crease count()function:
/* increase available resources by count */ int increase count(int count) { available resources += count; return 0; }
前面的程序段将会产生一个竞争的条件。如下： a. 确定数据参与竞争
b. 当竞争的条件发生时，确定代码段的位置（或是区域）
c. 利用Java同步，确定竞争的条件，同时修改decrease Count（ ）以使一个线程在没有足够的现有的资源下阻塞。 a. 确定数据参与竞争：可以利用的变量资
源
b. 当竞争的条件发生时，确定代码段的位置（或是区域）：代码使现有的资源递减和代码现
有资源递增的声明可以放在竞争的条件。 c. 使用信号量，确定竞争条件:使用信号量表示当前可用资源变量，并且用信号量递增和信
号量递减的操作代替递增和递减的操作。
7.1
假设有如图7.1所示的交通死锁。
a. 证明这个例子中实际上包括了死锁的四个必要条件。 b. 给出一个简单的规则用来在这个系统中避免死锁。
a. 死锁的四个必要条件: (1)互斥；（2）占有并等待；（3）非抢占；（4）循环等待。 互斥的条件是只有一辆车占据道路上的一个空间位置。占有并等待表示一辆车占据道路上的位置并且等待前进。一辆车不能从道路上当前的位置移动开（就是非抢占）。最后就是循环等待，因为每个车正等待着随后的汽车向前发展。循环等待的条件也很容易从图形中观察到。
b. 一个简单的避免这种的交通死锁的规则是，汽车不得进入一个十字路口如果明确地规
定，这样就不会产生相交。 7.2
考虑如下的死锁可能发生在哲学家进餐中，哲学家在同个时间获得筷子。讨论此种情况下死锁的四个必要条件的设置。讨论如何在消除其中任一条件来避免死锁的发生。
死锁是可能的，因为哲学家进餐问题是以以下的方式满足四个必要条件：1）相斥所需的筷子， 2 ）哲学家守住的筷子在手，而他们等待其他筷子， 3 ）没有非抢占的筷子，一个筷子分配给一个哲学家不能被强行拿走，4 ）有可能循环等待。死锁可避免克服的条件方式如下：1 ）允许同时分享筷子，2 ）有哲学家放弃第一双筷子如果他们无法获得其他筷子，3 ）允许筷子被强行拿走如果筷子已经被一位哲学家了占有了很长一段时间4 ）实施编号筷子，总是获得较低编号的筷子，之后才能获得较高的编号的筷子。 7.3
一种可能以防止死锁的解决办法是要有一个单一的，优先于任何其他资源的资源。例如，如果多个线程试图访问同步对象A??E，那么就可能发生死锁。（这种同步对象可能包括互斥体，信号量，条件变量等），我们可以通过增加第六个对象来防止死锁。每当一个线程希望获得同步锁定给对象A? ? ?E，它必须首先获得对象F的锁.该解决方案被称为遏制：对象A? ? ?E的锁内载对象F的锁。 对比此方案的循环等待和Section7.4.4的循环等待。
这很可能不是一个好的解决办法，因为它产生过大的范围。尽可能在狭隘的范围内定义死锁政策会更好。
7.4
对下列问题对比循环等待方法和死锁避免方法(例如银行家算法)： a.运行费用
b.系统的吞吐量死锁避免方法往往会因为追踪当前资源分配的成本从来增加了运行费用。然而死锁避免方法比静态地防止死锁的形成方法允许更多地并发使用资源。从这个意义上说，死锁避免方案可以增加系统的吞吐量。 7.5
操作系统概念第七版习题答案（中文版）完整版
