的危险, 他们完成的可能性低。其次，他们与其他重新开始线程竞争有限的执行时间, 因此整个系统运行的速度很慢。
6.16评价下面给出的就餐问题的解决方案。一位饥饿的哲学家首先拿起他左边的叉子，如果他右边的叉子也是可用的，则拿起右边的叉子开始吃饭，否则他放下左边的叉子，并重复这个循环。 解：如果哲学家们步调完全一致地拿起左边叉子又放下的话，他们会重复这一过程，导致饥饿情况的出现。
6.17假设有两种类型的哲学家。一类总是先拿起左边的叉子（左撇子），另一类总是先拿起右边的叉子（右撇子）。左撇子的行为和图6.12中定义的一致。右撇子的行为如下： begin repeat
think;
wait(fork[(i+1)mod5]); wait(fork[i]); eat;
signal(fork[i]);
signal(fork[(i+1)mod5]);
forever; end;
证明：a如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁。
b如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿。
解：a假设存在死锁情况，设有 D个哲学家，他们每人都有一支叉子而且另一
支叉子被邻居占有。不失一般性，设Pj 是一个左撇子。 Pj 抓牢他的左边叉子而且没有他的右边叉子, 他的右边邻居 Pk 没有完成就餐因此也是一个左撇子。 因此依次推理下去所有这Ｄ个哲学家都是左撇子。这与既有左撇子又有右撇子的条件矛盾，假设不成立，不存在死锁。 b
假设左撇子 Pj 饥饿，也就是说，有一部分人在就餐而Pj从不吃。 假如 Pj 没有叉子。 这样 Pj 的左边邻居 Pi 一定持续地占有叉子而始终不吃完。 因此Pi 是 右撇子，
抓住他的右边叉子, 但是从不得到他的左边叉子来完成就餐,也就是说 Pi 也饥饿。 现在 Pi 左边邻居也一定是持续占有右边叉子的右撇子。 向左进行这样的推理，得出所有哲学家都是饥饿的右撇子，这同Pj是个左撇子矛盾。因此 Pj 一直拥有左边子而且在等待他的右边叉子,Pj 的右边邻居 Pk 一直举着他的左边叉子而且从不完成一餐,也就是, Pk 是也饥饿的左撇子。 如果 Pk 不是一直拿着他的左边叉子， Pj 就可以就餐;因此 Pk 拿着他的左边叉子。向右推理可得所有哲学家都是饥饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。
6.18图1.17显示了另外一个使用管程解决哲学家就餐问题的方法。和图6.14比较并阐述你的结论。 解：图6.14是等待可用的叉子，图6.17是等待邻居吃完，在本质上逻辑是一样的，后者显得更加紧凑。
monitor dining_controller; enum states{thinking,hungry,eating} state[5]; cond needFork[5] /*condition variable*/ void get_forks(int pid) /*pid is the philosopher id number*/ { start[pid]=hungry; /*announce that I am hungry*/ if(state[(pid+1)%5]= =eating ||(state[(pid-1)%5]= =eating cwait(needFork[pid]); /*wait if either neighbor is eating*/ state[pid]=eating; /*proceed if neither neighbor is eating*/ } void release_fork(int pid) { state[pid]=thinking; /*give right(higher)neighbor a chance to eat*/ if(state[(pid+1)%5])= =hungry) &(state[(pid+2)%5])!=eating) csignal(needFork[pid+1]); /*give left(lower)neighbor a chance to eat*/ else if(state[(pid-1)%5]= =hungry) ||(state[(pid-2)%5!=eating]
void philosopher[k=0 to 4] /*the five philosopher clients*/ { while(true) {
6.19在表6.13中，Linux的一些原子操作不会涉及到对同一变量的两次访问。比如atomic_read(atomic_t *v).简单的读操作在任何体系结构中都是原子的。为什么该操作增加到了原子操作的指令表？
解：原子操作是在原子数据类型上操作, 原子数据类型有他们自己的内在的 格式。 因此，不能用简单的阅读操作, 但是特别的阅读操作 对于原子数据类型来说是不可或缺的。
6.2０考虑Linux系统中的如下代码片断： read_lock(&mr_rwlock); write_lock(&mr_rwlock);
mr_rwlock是读者写者锁。这段代码的作用是什么？
解：因为写者锁将会自旋，所以这段代码会导致死锁, 等待所有的 读者解锁, 包括唤醒这个线程。
6.21两个变量a和b分别有初始值1和2，对于Linux系统有如下代码：
线程1 线程2 a = 3； -- mb( )； -- -- c = b； -- rmb()； d = a；
使用内在屏障是为了避免什么错误？
解：没有使用内存屏障, 在一些处理器上可能 c接到b 的新值, 而d接到b 的旧
值。 举例来说, c可以等于 4(我们期待的), 然而 d 可能等于 1.(不是我们期待的)。 使用mb() 确保a 和 b 按合适的次序被写, 使用 rmb()确保 c 和d 按合适的次序被读。
第7章 内存管理
复习题：
7.1. 内存管理需要满足哪些需求？
答：重定位、保护、共享、逻辑组织和物理组织。 7.2. 为什么需要重定位进程的能力？
答：通常情况下，并不能事先知道在某个程序执行期间会有哪个程序驻留在主存中。此外还希望通过提供一个巨大的就绪进程池，能够把活动进程换入和换出主存，以便使处理器的利用率最大化。在这两种情况下，进程在主存中的确切位置是不可预知的。 7.3. 为什么不可能在编译时实施内存保护？
答：由于程序在主存中的位置是不可预测的，因而在编译时不可能检查绝对地址来确保保护。并且，大多数程序设计语言允许在运行时进行地址的动态计算（例如，通过计算数组下标或数据结构中的指针）。因此，必须在运行时检查进程产生的所有存储器访问，以便确保它们只访问了分配给该进程的存储空间。 7.4. 允许两个或多个进程访问进程的某一特定区域的原因是什么？
答：如果许多进程正在执行同一程序，则允许每个进程访问该程序的同一个副本要比让每个进程有自己单独的副本更有优势。同样，合作完成同一任务的进程可能需要共享访问同一个数据结构。
7.5. 在固定分区方案中，使用大小不等的分区有什么好处？
答：通过使用大小不等的固定分区：1.可以在提供很多分区的同时提供一到两个非常大的分区。大的分区允许将很大的进程全部载入主存中。2.由于小的进程可以被放入小的分区中，从而减少了内部碎片。 7.6. 内部碎片和外部碎片有什么区别？
答：内部碎片是指由于被装入的数据块小于分区大小而导致的分区内部所浪费的空间。外部碎片是与动态分区相关的一种现象，它是指在所有分区外的存储空间会变成越来越多的碎片的。
7.7. 逻辑地址、相对地址和物理地址间有什么区别？
答：逻辑地址是指与当前数据在内存中的物理分配地址无关的访问地址，在执行对内存的访问之前必须把它转化成物理地址。相对地址是逻辑地址的一个特例，是相对于某些已知点（通常是程序的开始处）的存储单元。物理地址或绝对地址是数据在主存中的实际位置。
7.8. 页和帧之间有什么区别？
答：在分页系统中，进程和磁盘上存储的数据被分成大小固定相等的小块，叫做页。而主存被分成了同样大小的小块，叫做帧。一页恰好可以被装入一帧中。 7.9. 页和段之间有什么区别？
答：分段是细分用户程序的另一种可选方案。采用分段技术，程序和相关的数据被划分成一组段。尽管有一个最大段长度，但并不需要所有的程序的所有段的长度都相等。
习题：
7.1. 2.3节中列出了内存管理的5个目标，7.1节中列出了5中需求。请说明它们是一致
的。
答: 重定位≈支持模块化程序设计; 保护≈保护和访问控制以及进程隔离; 共享≈保护和访问控制;
逻辑组织≈支持模块化程序设计;
物理组织≈长期存储及自动分配和管理.
7.2. 考虑使用大小相等分区的固定分区方案。分区大小为2e16字节，贮存的大小为2e24
字节。使用一个进程表来包含每一个进程对应的分区。这个指针需要多少位？ 答:分区的数量等于主存的字节数除以每个分区的字节数：224/216 = 28. 需要8个比特来确定一个分区大小为28中的某一个位置。
7.3. 考虑动态分区方案，说明平均内存中空洞的数量是段数量的一半。
答: 设n和h为断数量和空洞数量的个数.在主存中,每划分一个断产生一个空洞的概率是0.5,因为删除一个断和添加一个断的概率是一样的.假设s是内存中断的个数那么空洞的平均个数一定等于s/2.而导致空洞的个数一定小余断的数量的直接原因是相邻的两个断在删除是一定会产生一个空洞. 7.4. 在实现动态分区中的各种放置算法（见7.2节），内存中必须保留一个空闲块列表。
分别讨论最佳适配、首次适配、临近适配三种方法的平均查找长度。
答:通过上题我们知道，假设s是驻留段的个数，那么空洞的平均个数是s/2。从平均意义上讲，平均查找长度是s/4。
7.5. 动态分区的另一种放置算法是最坏适配，在这种情况下，当调入一个进程时，使用最
大的空闲存储块。该方法与最佳适配、首次适配、邻近适配相比，优点和缺点各是什么？它的平均查找长度是多少？
答：一种对最佳适配算法的评价即是为固定分配一个组块后和剩余空间是如此小以至于实际上已经没有什么用处。最坏适配算法最大化了在一次分配之后，剩余空间的大小仍足够满足另一需求的机率，同时最小化了压缩的概率。这种方法的缺点是最大存储块最早被分配，因此大空间的要求可能无法满足。
7.6. 如果使用动态分区方案，下图所示为在某个给定的时间点的内存配置：
阴影部分为已经被分配的块；空白部分为空闲块。接下来的三个内存需求分别为40MB，20MB和10MB。分别使用如下几种放置算法，指出给这三个需求分配的块的起始地址。 a. 首次适配 b. 最佳适配
c. 临近适配（假设最近添加的块位于内存的开始） d. 最坏适配 答：
a. 40M的块放入第2个洞中,起始地址是80M. 20M的块放入第一个洞中.起始地址是20M. 10M的块的起始地址是120M。
b. 40M,20N,10M的起始地址分别为230M,20M和160M.
c. 40M,20M,10M的起始地址是80M,120160M.