r3系统删除工号提示人员计数器号已被计数是什么意思
点击联系发帖人
时间：2018-05-26 10:17
(window.slotbydup=window.slotbydup || []).push({
id: '2014386',
container: s,
size: '234,60',
display: 'inlay-fix'
&&|&&1次下载&&|&&总261页&&|
您的计算机尚未安装Flash，点击安装&
试读已结束，如果需要继续阅读或下载，请使用积分（）
下载：80积分
本文档由合作伙伴提供
0人评价4页
0人评价324页
0人评价7页
0人评价3页
0人评价266页
此文档归属以下专题
6人评价150个文档
8人评价197个文档
所需积分：（友情提示：大部分文档均可免费预览！下载之前请务必先预览阅读，以免误下载造成积分浪费！）
（多个标签用逗号分隔）
文不对题，内容与标题介绍不符
广告内容或内容过于简单
文档乱码或无法正常显示
文档内容侵权
已存在相同文档
不属于经济管理类文档
源文档损坏或加密
若此文档涉嫌侵害了您的权利，请参照说明。
我要评价：
价格：80积分VIP价：64积分您在慧聪网上采购商品属于商业贸易行为。以上所展示的信息由卖家自行提供，内容的真实性、准确性和合法性由发布卖家负责，请意识到互联网交易中的风险是客观存在的。推荐使用慧付宝资金保障服务，保障您的交易安全！
按字母分类 ：
让慧聪网撮合专家为您解决采购难题
您采购的产品：
请输入采购产品
您的手机号码：
请输入手机号码
*采购产品：
请输入采购产品
*采购数量/单位：
请输入采购数量
请选择单位
*采购截止日期：
请输入正确的手机号码
请输入验证码
*短信验证码：
<input id="valid_Code1" maxlength="6" placeholder="请输入验证码" name="VALIDCODE" class="codeInput" onkeyup="this.value=this.value.replace(/\D/g,'')" onkeypress="if(event.keyCode
57) event.returnValue =" type="text">
免费获取验证码
为了安全，请输入验证码，我们将优先处理您的需求！
请输入验证码
发送成功！
慧聪已收到您的需求，我们会尽快通知卖家联系您，同时会派出采购专员1对1为您提供服务，请您耐心等待！
电话：757- &&
联系人：刘瑞荣&销售部
公司名称：佛山市南海区大沥正特机电商行
#contact_inquiry_self()
每一份需求都会在24小时内得到行业多家优质供应商报价。
每一份需求的报价供应商工商信用资质都会经过专业人员检验，交易安全有保障。
免费咨询行业专家
免费咨询行业专家
服务主题：
筛选发货地
验证供应商真伪
提供其他优质供应商
采购数量：
用途描述：
卖家暂时不在线，留下联系方式，卖家会主动联系您
*我要采购：
我的姓名：
留言内容：当前位置： >>
《操作系统精髓与设计原理?第五版》练习题及答案
第1章计算机系统概述1.1、图 1.3 中的理想机器还有两条 I/O 指令： 0011 = 从 I/O 中载入 AC 0111 = 把 AC 保存到 I/O 中 在这种情况下，12 位地址标识一个特殊的外部设备。请给出以下程序的执行过程（按照图 1.4 的格式） ： 1. 从设备 5 中载入 AC。 2. 加上存储器单元 940 的内容。 3. 把 AC 保存到设备 6 中。 假设从设备 5 中取到的下一个值为 3940 单元中的值为 2。 答案：存储器（16 进制内容） ：300：：：7006 步骤 1：3005－&IR；步骤 2：3－&AC 步骤 3：5940－&IR；步骤 4：3＋2＝5－&AC 步骤 5：7006－&IR：步骤 6：AC－&设备 6 1.2、本章中用 6 步来描述图 1.4 中的程序执行情况，请使用 MAR 和 MBR 扩充这个描述。 答案：1. a. PC 中包含第一条指令的地址 300，该指令的内容被送入 MAR 中。 b. 地址为 300 的指令的内容（值为十六进制数 1940）被送入 MBR，并且 PC 增 1。这两个步骤 是并行完成的。 c. MBR 中的值被送入指令寄存器 IR 中。 2. a. 指令寄存器 IR 中的地址部分（940）被送入 MAR 中。 b. 地址 940 中的值被送入 MBR 中。 c. MBR 中的值被送入 AC 中。 3. a. PC 中的值（301）被送入 MAR 中。 b. 地址为 301 的指令的内容（值为十六进制数 5941）被送入 MBR，并且 PC 增 1。 c. MBR 中的值被送入指令寄存器 IR 中。 4. a. 指令寄存器 IR 中的地址部分（941）被送入 MAR 中。 b. 地址 941 中的值被送入 MBR 中。 c. AC 中以前的内容和地址为 941 的存储单元中的内容相加，结果保存到 AC 中。 5. a. PC 中的值（302）被送入 MAR 中。 b. 地址为 302 的指令的内容（值为十六进制数 2941）被送入 MBR，并且 PC 增 1。 c. MBR 中的值被送入指令寄存器 IR 中。 6. a. 指令寄存器 IR 中的地址部分（941）被送入 MAR 中。 b. AC 中的值被送入 MBR 中。 c. MBR 中的值被存储到地址为 941 的存储单元之中。 1.4、假设有一个微处理器产生一个 16 位的地址（例如，假设程序计数器和地址寄存器都是 16 位）并且具 有一个 16 位的数据总线。 a.如果连接到一个 16 位存储器上，处理器能够直接访问的最大存储器地址空间为多少？ b.如果连接到一个 8 位存储器上，处理器能够直接访问的最大存储器地址空间为多少？ c.处理访问一个独立的 I/O 空间需要哪些结构特征？ d.如果输入指令和输出指令可以表示 8 位 I/O 端口号，这个微处理器可以支持多少 8 位 I/O 端口？ 答案：对于(a)和(b)两种情况，微处理器可以直接访问的最大存储器地址空间为216 = 64K bytes；唯一的区 别是8位存储器每次访问传输1个字节，而16位存储器每次访问可以传输一个字节或者一个16位的 字。对于(c)情况，特殊的输入和输出指令是必要的，这些指令的执行体会产生特殊的“I/O信号” （有别于“存储器信号”，这些信号由存储器类型指令的执行体产生）；在最小状态下，一个附加 的输出针脚将用来传输新的信号。对于(d)情况，它支持28 = 256个输入和28 = 256个输出字节端口和 相同数目的16位I/O端口；在任一情况, 一个输入和一个输出端口之间的区别是通过被执行的输入1 输出指令所产生的不同信号来定义的。 1.5、考虑一个 32 位微处理器，它有一个 16 位外部数据总线，并由一个 8MHz 的输入时钟驱动。假设这个 微处理器有一个总线周期，其最大持续时间等于 4 个输入时钟周期。请问该微处理器可以支持的最大数据 传送速度为多少？外部数据总线增加到 21 位，或者外部时钟频率加倍，哪种措施可以更好地提高处理器 性能？请叙述你的设想并解释原因。 答案：时钟周期＝1/（8MHZ）＝125ns 总线周期＝4×125ns＝500ns 每 500ns 传输 2 比特；因此传输速度＝4MB/s 加倍频率可能意味着采用了新的芯片制造技术（假设每个指令都有相同的时钟周期数） ；加倍外部数 据总线，在芯片数据总线驱动/锁存、总线控制逻辑的修改等方面手段广泛（或许更新） 。在第一种方案中， 内存芯片的速度要提高一倍（大约） ，而不能降低微处理器的速度；第二种方案中，内存的字长必须加倍， 以便能发送/接受 32 位数量。 1.6、考虑一个计算机系统，它包含一个 I/O 模块，用以控制一台简单的键盘/打印机电传打字设备。CPU 中包含下列寄存器，这些寄存器直接连接到系统总线上： INPR：输入寄存器，8 位 OUTR：输出寄存器，8 位 FGI：输入标记，1 位 FGO：输出标记，1 位 IEN：中断允许，1 位 I/O 模块控制从打字机中输入击键，并输出到打印机中去。打字机可以把一个字母数字符号编码成一个 8 位字，也可以把一个 8 位字解码成一个字母数字符号。当 8 位字从打字机进入输入寄存器时，输入标记被 置位；当打印一个字时，输出标记被置位。 a. 描述 CPU 如何使用这 4 个寄存器实现与打字机间的输入/输出。 b. 描述通过使用 IEN，如何提高执行效率？ 答案：a.来源于打字机的输入储存在 INPR 中。只有当 FGI＝0 时，INPR 才会接收来自打字机的数据。当 数据接收后，被储存在 INPR 里面，同时 FGI 置为 1。CPU 定期检查 FGI。如果 FGI＝1，CPU 将把 INPR 里面的内容传送至 AC，并把 FGI 置为 0。 当 CPU 需要传送数据到打字机时，它会检查 FGO。如果 FGO＝0，CPU 处于等待。如果 FGO ＝1，CPU 将把 AC 的内容传送至 OUTER 并把 FGO 置为 0。当数字符号打印后，打字机将把 FGI 置为 1。 b.（A）描述的过程非常浪费。速度远高于打字机的 CPU 必须反复不断的检查 FGI 和 FGO。如果中 断被使用，当打字机准备接收或者发送数据时，可以向 CPU 发出一个中断请求。IEN 计数器可以由 CPU 设置（在程序员的控制下） 。 1.7、实际上在所有包括 DMA 模块的系统中，DMA 访问主存储器的优先级总是高于处理器访问主存储器 的优先级。这是为什么? 答案：如果一个处理器在尝试着读或者写存储器时被挂起, 通常除了一点轻微的时间损耗之外没有任何危 害。但是，DMA可能从或者向设备(例如磁盘或磁带)以数据流的方式接收或者传输数据并且这是不能 被打断的。否则，如果DMA设备被挂起（拒绝继续访问主存），数据可能会丢失。 1.9、一台计算机包括一个 CPU 和一台 I/O 设备 D，通过一条共享总线连接到主存储器 M，数据总线的宽 度为 1 个字。CPU 每秒最多可执行 106 条指令，平均每条指令需要 5 个机器周期，其中 3 个周期需要使用 存储器总线。存储器读/写操作使用 1 个机器周期。假设 CPU 正在连续不断地执行后台程序，并且需要保 证 95%的指令执行速度，但没有任何 I/O 指令。假设 1 个处理器周期等于 1 个总线周期，现在要在 M 和 D 之间传送大块数据。 a.若使用程序控制 I/O， 每传送 1 个字需要 CPU 执行两条指令。 I/O 请估计通过 D 的 I/O 数据传送的最大可 能速度。 b.如果使用 DMA 传送，请估计传送速度。2 答案：a.处理器只能分配 5％的时间给 I/O.所以最大的 I/O 指令传送速度是 10e6×0.05＝50000 条指令/秒。 因此 I/O 的传送速率是 25000 字/秒。 b.使用 DMA 控制时，可用的机器周期下的数量是 10e6（0.05×5＋0.95×2）＝2.15×10e6 如果我们假设 DMA 模块可以使用所有这些周期，并且忽略任何设置和状态检查时间，那么这个值 就是最大的 I/O 传输速率。 1.10、考虑以下代码： for ( i = 0；i & 20；i++) for (j = 0；j & 10；j++) a[i] = a[i]*j a. 请举例说明代码中的空间局部性。 b. 请举例说明代码中的时间局部性。 答案：a.读取第二条指令是紧跟着读取第一条指令的。 b.在很短的间歇时间内， a[i]在循环内部被访问了十次。 1.11、请将附录 1A 中的式（1.1）和式（1.2）推广到 n 级存储器层次中。 答案：定义： Ci = 存储器层次 i 上每一位的存储单元平均花销 Si = 存储器层次 i 的规模大小 Ti = 存储器层次 i 上访问一个字所需时间 Hi = 一个字在不高于层次 i 的存储器上的概率 Bi = 把一个数据块从层次 i+1 的存储器上传输到层次 i 的存储器上所需时间 高速缓冲存储器作为是存储器层次1；主存为存储器层次2；针对所有的N层存储器层以此类推。有：CS ??C Si ?1 n ini?Si ?1iTs的引用更复杂，我们从概率论入手：所期望的值 x ?? i Pr[ x ? 1] ，由此我们可以写出：i ?1nTs ? ? Ti H ii ?1n我们需要清楚如果一个字在M1（缓存）中，那么对它的读取非常快。如果这个字在M2而不在M1中，那么 数据块需要从M2传输到M1中，然后才能读取。因此，T2 = B1+T1 进一步，T3 = B2+T2 = B1+B2+T1 以此类推： Ti ?n?Bj ?1 i ?1 j ?1i ?1j? T1n所以， Ts ?n?i ?2i? ( B j H i ) ? T1 ? H ii ?1但是，?Hi ?1?13 最后， Ts ?? ? (B H ) ? Ti ?2 j ?1 i ini ?111.12、考虑一个存储器系统，它具有以下参数： Tc = 100 ns Cc = 0.01 分/位 Tm = 1200 ns Cm = 0.001 分/位 a.1MB 的主存储器价格为多少？ b.使用高速缓冲存储器技术，1MB 的主存储器价格为多少？ c.如果有效存取时间比高速缓冲存储器存取时间多 10% ，命中率 H 为多少？ 答案：a.价格 = Cm× 106 = 8× 3 ￠ = ＄80 8× 10 6 4 b.价格 = Cc× 10 = 8× 8× 10 ￠ = ＄800 c.由等式 1.1 知：1.1× 1 = T1+(1-H)T2 T (0.1)(100) = (1-H)(1200) H=.13、一台计算机包括包括高速缓冲存储器、主存储器和一个用做虚拟存储器的磁盘。如果要存取的字在 高速缓冲存储器中，存取它需要 20ns；如果该字在主存储器中而不在高速缓冲存储器中，把它载入高速缓 冲存储器需要 60ns（包括最初检查高速缓冲存储器的时间） ，然后再重新开始存取；如果该字不在主存储 器中，从磁盘中取到内存需要 12ms，接着复制到高速缓冲存储器中还需要 60ns，再重新开始存取。高速 缓冲存储器的命中率为 0.9，主存储器的命中率为 0.6，则该系统中存取一个字的平均存取时间是多少（单 位为 ns）？ 答案：有三种情况需要考虑： 字所在的位置 在缓存中 不在缓存，在主存中 不在缓存也不在主存中 概率 0.9 （0.1） （0.6）= 0.06 （0.1） （0.4）= 0.04 访问所需时间（ns） 20 60+20 = 80 12ms+60+20 = 12,000,080所以平均访问时间是：Avg = (0.9)(20) + (0.06)(80) + (0.04)() = 480026 ns 1.14、假设处理器使用一个栈来管理过程调用和返回。请问可以取消程序计数器而用栈指针代替吗？ 答案：如果栈只用于保存返回地址。或者如果栈也用于传递参数，这种方案只有当栈作为传递参数的控制 单元而非机器指令时才成立。这两种情况下可以取消程序计数器而用栈指针代替。在后者情况中， 处理器同时需要一个参数和指向栈顶部的程序计数器。第2章操作系统概述2.1 假设我们有一台多道程序的计算机，每个作业有相同的特征。在一个计算周期 T 中，一个作业有一半 时间花费在 I/O 上， 另一半用于处理器的活动。 每个作业一共运行 N 个周期。 假设使用简单的循环法调度， 并且 I/O 操作可以与处理器操作重叠。定义以下量： ?时间周期=完成任务的实际时间 ?吞吐量=每个时间周期 T 内平均完成的作业数目 ?处理器使用率=处理器活跃（不是处于等待）的时间的百分比 当周期 T 分别按下列方式分布时，对 1 个、2 个和 4 个同时发生的作业，请计算这些量： a. 前一般用于 I/O，后一半用于处理器。 b. 前四分之一和后四分之一用于 I/O，中间部分用于处理器。 答： （a）和（b）的答案相同。尽管处理器活动不能重叠，但 I/O 操作能。 一个作业 时间周期=NT 处理器利用率=50 两个作业 时间周期=NT 处理器利用率=100 四个作业 时间周期=（2N-1）NT 处理器利用率=1004 2.2 I/O 限制的程序是指如果单独运行，则花费在等待 I/O 上的时间比使用处理器的时间要多的程序。处理 器限制的程序则相反。假设短期调度算法偏爱那些在近期石油处理器时间较少的算法，请解释为什么这个 算法偏爱 I/O 限制的程序，但是并不是永远不受理处理器限制程序所需的处理器时间？ 受 I/O 限制的程序使用相对较少的处理器时间，因此更受算法的青睐。然而，受处理器限制的进程如 果在足够长的时间内得不到处理器时间，同一算法将允许处理器去处理此进程，因为它最近没有使用过处 理器。这样，一个处理器限制的进程不会永远得不到处理器。 2.3 请对优化分时系统的调度策略和用于优化多道程序批处理系统的调度策略进行比较。 分时系统关注的是轮转时间，时间限制策略更有效是因为它给所有进程一个较短的处理时间。批处理 系统关心的是吞吐量，更少的上下文转换和更多的进程处理时间。因此，最小的上下文转换最高效。 2.4 系统调用的目的是什么?如何实现与操作系统相关的的系统调用以及与双重模式 （内核模式和用户模式） 操作相关的系统调用？ 系统调用被应用程序用来调用一个由操作系统提供的函数。通常情况下，系统调用最终转换成在内核 模式下的系统程序。 2.5 在 IBM 的主机操作系统 OS/390 中，内核中的一个重要模块是系统资源管理程序（System Resource Manager,SRM） ，他负责地址空间（进程）之间的资源分配。SRM 是的 OS/390 在操作系统中具有特殊性， 没有任何其他的主机操作系统，当然没有任何其他类型的操作系统可以比得上 SRM 所实现的功能。资源 的概念包括处理器、实存和 I/O 通道，SRM 累计处理器、I/O 通道和各种重要数据结构的利用率，它的目 标是基于性能监视和分析提供最优的性能，其安装设置了以后的各种性能目标作为 SRM 的指南，这会基 于系统的利用率动态的修改安装和作业性能特点。 SRM 依次提供报告， 允许受过训练的操作员改进配置和 参数设置，以改善用户服务。 现在关注 SRM 活动的一个实例。实存被划分为成千上万个大小相等的块，称为帧。每个帧可以保留一块 称为页的虚存。SRM 每秒大约接受 20 次控制，并在互相之间以及每个页面之间进行检查。如果页未被引 用或被改变，计数器增 1。一段时间后，SRM 求这些数据的平均值，以确定系统中一个页面未曾被触及的 平均秒数。这样做的目的是什么？SRM 将采取什么动作？ 操作系统可以查看这些数据已确定系统的负荷，通过减少加在系统上的活跃作业来保持较高的平均利用 率。典型的平均时间应该是两分钟以上，这个平均时间看起来很长，其实并不长。第 3 章 进程描述和控制3.1. 给出操作系统进行进程管理时的五种主要活动，并简单描述为什么需要它们。 答：用户进程和系统进程创建及删除。系统中的进程可以为信息共享、运算加速、模块化和方便并 发地执行。而并发执行需要进程的创建和删除机制。当进程创建或者运行时分配给它需要的资源。 当进程终止时，操作系统需要收回任何可以重新利用的资源。 进程的暂停和继续执行。在进程调度中，当进程在等待某些资源时，操作系统需要将它的状态改变 为等待或就绪状态。当所需要的资源可用时，操作系统需要将它的状态变为运行态以使其继续执行。 提供进程的同步机制。合作的进程可能需要共享数据。对共享数据的并行访问可能会导致数据冲突。 操作系统必须提供进程的同步机制以使合作进程有序地执行，从而保证数据的一致性。 提供进程的通信机制。操作系统下执行的进程既可以是独立进程也可以是合作进程。合作进程之间 必须具有一定的方式进行通信。 提供进程的死锁解决机制。在多道程序环境中，多个进程可能会竞争有限的资源。如果发生死锁， 所有的等待进程都将永远不能由等待状态再变为运行态，资源将被浪费，工作永远不能完成。 3.2. 在[PINK89] 中为进程定义了以下状态：执行（运行）态、活跃（就绪）态、阻塞态和挂起态。当进 程正在等待允许使用某一资源时，它处于阻塞态；当进程正在等待它已经获得的某种资源上的操作 完成时，它处于挂起态。在许多操作系统中，这两种状态常常放在一起作为阻塞态，挂起态使用本 章中给出的定义。请比较这两组定义的优点。 答：[PINK89]中引用了以下例子来阐述其中阻塞和挂起的定义： 假设一个进程已经执行了一段时间，它需要一个额外的磁带设备来写出一个临时文件。在它开5 始写磁带之前，进程必须得到使用某一设备的许可。当它做出请求时，磁带设备可能并不可用， 这种情况下，该进程就处于阻塞态。假设操作系统在某一时刻将磁带设备分配给了该进程，这 时进程就重新变为活跃态。当进程重新变为执行态时要对新获得的磁带设备进行写操作。这时 进程变为挂起态，等待该磁带上当前所进行的写操作完成。 这种对等待某一设备的两种不同原因的区别，在操作系统组织其工作时是非常有用的。然而这并不 能表明那些进程是换入的，那些进程是换出的。后一种区别是必需的，而且应该在进程状态中以某 种形式表现出来。 3.3. 对于图 3.9（b）中给出的 7 状态进程模型，请仿照图 3.8（b）画出它的排队图。 答：图 9.3 给出了单个阻塞队列的结果。该图可以很容易的推广到多个阻塞队列的情形。 3.4. 考虑图 3.9（b）中的状态转换图。假设操作系统正在分派进程，有进程处于就绪态和就绪/挂起态，并 且至少有一个处于就绪/挂起态的进程比处于就绪态的所有进程的优先级都高。有两种极端的策略： （1）总是分派一个处于就绪态的进程，以减少交换； （2）总是把机会给具有最高优先级的进程，即 使会导致在不需要交换时进行交换。请给出一种能均衡考虑优先级和性能的中间策略。 答：对于一个就绪/挂起态的进程，降低一定数量（如一或两个）优先级，从而保证只有当一个就绪 /挂起态的进程比就绪态的进程的最高优先级还高出几个优先级时，它才会被选做下一个执行。 3.5. 表 3.13 给出了 VAX/VMS 操作系统的进程状态。 a. 请给出这么多种等待状态的理由。 b. 为什么以下状态没有驻留和换出方案：页错误等待、也冲突等待、公共事件等待、自由页等待和 资源等待。 c. 请画出状态转换图，并指出引发状态装换的原因。 答： a. 每一种等待状态都有一个单独的队列与其相关联。当影响某一等待进程的事件发生时，把等待进 程分成不同的队列就减少了定位这一等待进程所需的工作量。例如，当一个页错误完成时，调 度程序就可以在页错误等待队列中找到等待的进程。 b. 在这些状态下，允许进程被换出只会使效率更低。例如，当发生页错误等待时，进程正在等待换 入一个页从而使其可以执行，这是将进程换出是毫无意义的。 c. 可以由下面的进程状态转换表得到状态转换图。 当前状态 当前正在执 行 当前正在执 行 可计算（驻 留） 可计算（换 出） 各种等待状 态（驻留） 各种等待状 态（换出） 调度 换入 事件发生 事件发生 换出 可计算（驻 留） 重调度 换出 下一状态 可计算（换 出） 各种等待状 态（驻留） 等待 各种等待状 态（换出）3.6. VAM/VMS 操作系统采用了四种处理器访问模式，以促进系统资源在进程间的保护和共享。访问模式 确定： ? 指令执行特权：处理器将执行什么指令。 ? 内存访问特权：当前指令可能访问虚拟内存中的哪个单元。 四种模式如下：6 ? 内核模式：执行 VMS 操作系统的内核，包括内存管理、中断处理和 I/O 操作。 ? 执行模式：执行许多操作系统服务调用，包括文件（磁盘和磁带）和记录管理例程。 ? 管理模式：执行其他操作系统服务，如响应用户命令。 ? 用户模式：执行用户程序和诸如编译器、编辑器、链接程序、调试器之类的实用程序。 在较少特权模式执行的进程通常需要调用在较多特权模式下执行的过程，例如，一个用户程序需要 一个操作系统服务。这个调用通过使用一个改变模式（简称 CHM）指令来实现，该指令将引发一个 中断， 把控制转交给处于新的访问模式下的例程， 并通过执行 REI Return from Exception or Interrupt， （ 从异常或中断返回）指令返回。 a. 很多操作系统有两种模式，内核和用户，那么提供四种模式有什么优点和缺点？ b. 你可以举出一种有四种以上模式的情况吗？ 答： a. 四种模式的优点是对主存的访问控制更加灵活，能够为主存提供更好的保护。缺点是复杂和处理 的开销过大。例如，程序在每一种执行模式下都要有一个独立的堆栈。 b. 原则上，模式越多越灵活，但是四种以上的模式似乎很难实现。 3.7. 在前面习题中讨论的 VMS 方案常常称为环状保护结构，如图 3.18 所示。3.3 节所描述的简单的内核/ 用户方案是一种两环结构，[SILB04]指出了这种方法的问题：环状（层次）结构的主要缺点是它不 允许我们实施须知原理，特别地，如果一个对象必须在域 Dj 中可访问，但在域 Di 中不可访问，则必 须有就 j&i。这意味着在 Di 中可访问的每个段在 Dj 中都可以访问。 a. 请清楚地解释上面引文中提出的问题。 b. 请给出环状结构操作系统解决这个问题的一种方法。 答： a. 当 j&i 时，运行在 Di 中的进程被禁止访问 Dj 中的对象。因此，如果 Dj 中包含的信息比 Di 中的更 具有特权或者要求的安全性更高，那么这种限制就是合理的。然而，通过以下方法却可以绕过 这种安全策略。一个运行在 Dj 中的进程可以读取 Dj 中的数据，然后把数据复制到 Di 中。随后， Di 中的进程就可以访问这些信息了。 b. 有一种解决这一问题的方法叫做可信系统，我们将在 16 章中进行讨论。 3.8. 图 3.7（b）表明一个进程每次只能在一个事件队列中。 a. 是否能够允许进程同时等待一个或多个事件？请举例说明。 b. 在这种情况下，如何修改图中的排队结构以支持这个新特点？ 答： a. 一个进程可能正在处理从另一个进程收到的数据并将结果保存到磁盘上。如果当前在另一个进程 中正有数据在等待被取走，进程就可以继续获得数据并处理它。如果前一个写磁盘操作已经完 成，并且有处理好的数据在等待写出，那么进程就可以继续写磁盘。这样就可能存在某一时刻， 进程即在等待从输入进程获得数据，又在等待磁盘可用。 b. 有很多种方法解决这一问题。可以使用一种特殊的队列，或者将进程放入两个独立的队列中。不 论采用哪种方法，操作系统都必须处理好细节工作，使进程相继地关注两个事件的发生。 3.9. 在很多早期计算机中，中断导致寄存器值被保存在与给定的中断信息相关联的固定单元。在什么情况 下这是一种实用的技术？请解释为什么它通常是不方便的。 答：这种技术是基于被中断的进程 A 在中断响应之后继续执行的假设的。但是，在通常情况下，中 断可能会导致另一个进程 B 抢占了进程 A。这是就必须将进程 A 的执行状态从与中断相关的位置复 制到与 A 相关的进程描述中。然而机器却有可能仍将它们保存到前一位置。参考：[BRIN73]。 3.10. 3.4 节曾经讲述过，由于在内核模式下执行的进程是不能被抢占的，因此 UNIX 不适用于实时应用。 请阐述原因。 答：由于存在进程不能被抢占的情况（如在内核模式下执行的进程） ，操作系统不可能对实时需求给 予迅速的反应。7 第 4 章 线程、对称多处理和微内核4.1. 一个进程中的多个线程有以下两个优点： （1）在一个已有进程中创建一个新线程比创建一个新进程所 需的工作量少； （2）在同一个进程中的线程间的通信比较简单。请问同一个进程中的两个线程间的 模式切换与不同进程中的两个线程间的模式切换相比，所需的工作量是否要少？ 答：是的，因为两个进程间的模式切换要储存更多的状态信息。 4.2. 在比较用户级线程和内核级线程时曾指出用户级线程的一个缺点，即当一个用户级线程执行系统调用 时，不仅这个线程被阻塞，而且进程中的所有线程都被阻塞。请问这是为什么？ 答：因为对于用户级线程来说，一个进程的线程结构对操作系统是不可见的，而操作系统的调度是 以进程为单位的。 4.3. 在 OS/2 中，其他操作系统中通用的进程概念被分成了三个独立类型的实体：会话、进程和线程。一 个会话是一组与用户接口（键盘、显示器、鼠标）相关联的一个或多个进程。会话代表了一个交互 式的用户应用程序，如字处理程序或电子表格，这个概念使得 PC 用户可以打开一个以上的应用程 序，在屏幕上显示一个或更多个窗口。操作系统必须知道哪个窗口，即哪个会话是活跃的，从而把 键盘和鼠标的输入传递个相应的会话。在任何时刻，只有一个会话在前台模式，其他的会话都在后 台模式，键盘和鼠标的所有输入都发送给前台会话的一个进程。当一个会话在前台模式时，执行视 频输出的进程直接把它发送到硬件视频缓冲区。当一个会话在后台时，如果该会话的任何一个进程 的任何一个线程正在执行并产生屏幕输出，则这个输出被送到逻辑视频缓冲区；当这个会话返回前 台时，屏幕被更新，为新的前台会话反映出逻辑视频缓冲区中的当前内容。 有一种方法可以把 OS/2 中与进程相关的概念的数目从 3 个减少到 2 个。删去会话，把用户接口（键 盘、显示器、鼠标）和进程关联起来。这样，在某一时刻，只有一个进程处于前台模式。为了进一 步地进行构造，进程可以被划分成线程。 a. 使用这种方法会丧失什么优点？ b. 如果继续使用这种修改方法，应该在哪里分配资源（存储器、文件等） ：在进程级还是线程级？ 答： a. 会话的使用非常适合个人计算机和工作站对交互式图形接口的需求。它为明确图形输出和键盘/ 鼠标输入应该被关联到什么位置提供了一个统一的机制，减轻了操作系统的工作负担。 b. 应该和其他的进程/线程系统一样，在进程级分配地址空间和文件。 4.4. 考虑这样一个环境，用户级线程和内核级线程呈一对一的映射关系，并且允许进程中的一个或多个线 程产生会引发阻塞的系统调用，而其他线程可以继续运行。解释为什么这个模型可以使多线程程序 比在单处理器机器上的相应的单线程程序运行速度更快？ 答：问题在于机器会花费相当多的时间等待 I/O 操作的完成。在一个多线程程序中，可能一个内核 级线程会产生引发阻塞的系统调用，而其他内核级线程可以继续执行。而在单处理器机器上，进程 则必须阻塞知道所有的系统调用都可以继续运行。参考：[LEWI96] 4.5. 如果一个进程退出时，该进程的某些线程仍在运行，请问他们会继续运行吗？ 答：不会。当一个进程退出时，会带走它的所有东西――内核级线程，进程结构，存储空间――包 括线程。参考：[LEWI96] 4.6. OS/390 主机操作系统围绕着地址空间和任务的概念构造。 粗略说来， 一个地址空间对应于一个应用程 序，并且或多或少地对应于其他操作系统中的一个进程；在一个地址空间中，可以产生一组任务， 并且它们可以并发执行，这大致对应于多线程的概念。管理任务结构有两个主要的数据结构。地址 空间控制块（ASCB）含有 OS/390 所需要的关于一个地址空间的信息，而不论该地址空间是否在执 行。ASCB 中的信息包括分派优先级、分配给该地址空间的实存和虚存、该地址空间中就绪的任务 数以及是否每个都被换出。一个任务控制块（TCB）标识一个正在执行的用户程序，它含有在一个 地址空间中管理该任务所需要的信息，包括处理器状态信息、指向该任务所涉及到的程序的指针和 任务执行结构。ASCB 是在系统存储器中保存的全局结构，而 TCB 是保存在各自的地址空间中的局 部结构。请问把控制信息划分成全局和局部两部分有什么好处？8 答：关于一个地址空间的尽可能多的信息可以随地址空间被换出，从而节约了主存。 4.7. 一个多处理系统有 8 个处理器和 20 个附加磁带设备。现在有大量的作业提交给该系统，完成每个作 业最多需要 4 个磁带设备。假设每个作业开始运行时只需要 3 个磁带设备，并且在很长时间内都只 需要这 3 个设备，而只是在最后很短的一段时间内需要第 4 个设备以完成操作。同时还假设这类作 业源源不断。 a. 假设操作系统中的调度器只有当 4 个磁带设备都可用时才开始一个作业。当作业开始时，4 个设 备立即被分配给它，并且直到作业完成时才被释放。请问一次最多可以同时执行几个作业？采 用这种策略，最多有几个磁带设备可能是空闲的？最少有几个？ b. 给出另外一种策略，要求其可以提高磁带设备的利用率，并且同时可以避免系统死锁。分析最多 可以有几个作业同时执行，可能出现的空闲设备的范围是多少。 答： a. 采用一个保守的策略， 一次最多同时执行 20/4=5 个作业。 由于分配各一个任务的磁带设备最多同 时只有一个空闲，所以在同一时刻最多有 5 个磁带设备可能是空闲的。在最好的情况下没有磁 带设备空闲。 b. 为了更好的利用磁设备， 每个作业在最初只分配三个磁带设备。 第四个只有的需要的时候才分配。 在这种策略中，最多可以有 20/3=6 个作业同时执行。最少的空闲设备数量为 0，最多有 2 个。 参考：Advanced Computer Architectrue,K.Hwang,. 在描述 Solaris 用户级线程状态时，曾表明一个用户级线程可能让位于具有相同优先级的另一个线程。 请问，如果有一个可运行的、具有更高优先级的线程，让位函数是否还会导致让位于具有相同优先 级或更高优先级的线程？ 答：任何一个可能改变线程优先级或者使更高优先级的线程可运行的调用都会引起调度，它会依次 抢占低优先级的活跃线程。所以，永远都不会存在一个可运行的、具有更高优先级的线程。参考： [LEVI96]第5章并发性：互斥和同步5.1 答：b.协同程序 read 读卡片，将字符赋给一个只有一个字大小的缓冲区 rs 然后在赋给 squash 协同程。协 同程序 Read 在每副卡片图像的后面插入一个额外的空白。协同程序 squash 不需要知道任何关于输入的八 十个字符的结构， 它简单的查找成对出现的星号， 然后将更改够的字符串经由只有一个字符大小的缓冲 sp， 传递给协同程序 print。最后协同程序 print 简单的接受到来的字符串，并将他们打印在包含 125 个字符的 行中。 5.2．考虑一个并发程序，它有两个进程 p 和 q，定义如下。A.B.C.D 和 E 是任意的原子语句。假设住程序 执行两个进程的 parbegin Void p() void q() { A; { D; B; E; C; } } 答：ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCE; 5.3 考虑下面的程序 const int n=50; void total() { for(count =1;count &=n;count ++)9 {tally++; } } void main() { tally =0; parbegin(total(),total(); write(tally); } 答：a.随意一看,tally 值的范围好像是落在[50,100]这个区间里,因为当没有互斥时可以从 0 直接增加到 50. 这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得 tally 值还低的 一个最终 tally 值.但是考虑下面由这两进程按交替顺序执行载入,增加,存储的情况,同时变更这个共享变量 的取值: 1.进程 A 载入 tally 值,tally 值加到 1,在此时失去处理器(它已经增加寄存器的值到 1,但是还没有存储 这个值). 2.进程 B 载入 tally 值(仍然是 0),然后运行完成 49 次增加操作,在它已经将 49 这个值存储给共享变 量 tally 后,失去处理器控制权. 3.进程 A 重新获得处理器控制权去完成它的第一次存储操作(用 1 去代替先前的 49 这个 tally 值), 此时被迫立即放弃处理器. 4.进程 B 重新开始,将 1(当前的 tally 值)载入到它自己的寄存器中,但此时被迫放弃处理器(注意这是 B 的最后一次载入). 5.进程 A 被重新安排开始,但这次没有被中断,直到运行完成它剩余的 49 次载入,增加和存储操作,结 果是此时 tally 值已经是 50. 6.进程 B 在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至 2,同时存储这个值做 为这个共享变量的最终结果. 一些认为会出现低于 2 这个值的结果,这种情况不会出现.这样 tally 值的正确范围是[2,100]. b.对一般有 N 个进程的情况下,tally 值的最终范围是[2,N*50],因为对其他所有进程来说,从最初开始 运行到在第五步完成.但最后都被进程 B 破坏掉它们的最终结果. 5.4.忙等待是否总是比阻塞等待效率低（根据处理器的使用时间）？请解释。 答：就一般情况来说是对的,因为忙等待消耗无用的指令周期.然而,有一种特殊情况,当进程执行到程序的某 一点处,在此处要等待直到条件满足,而正好条件已满足,此时忙等待会立即有结果,然而阻塞等待会消耗操 作系统资源在换出与换入进程上. 5.5 考虑下面的程序 boolean blocked[2]; void P(int id) { While (true) { While(turn!=id); { While(blocked[1-!id] /*do nothing*/; Turn = } }10 Void main () { Blocked[0]= Blocked[1]= Turn=0; Parbegin(P(0),P(1)); } 这是【HYMA66】中提出的解决互斥问题的一种方法。请举出证明该方法不正确的一个反例。 答：考虑这种情况:此时 turn=0,进程 P(1)使布尔变量 blocked[1]的值为 true,在这时发现布尔变量 blocked[0] 的值为 false,然后 P(0)会将 true 值赋予 blocked[0] ,此时 turn=0,P(0)进入临界区,P(1)在将 1 赋值给 turn 后,也进入了临界区. 5.6 解决互斥的另一种软件方法是 lamport 的面包店（bakery）算法，之所以起这个名字，是因为它的思想 来自于面包店或其他商店中，每个顾客在到达时都得到一个有编号的票，并按票号依次得到服务，算法如 下： Boolean choosing[n]; Int number[n]; While (true) { Choosing[i]= Number[i]=1+getmax(number[],n)； Choosing[i]= For(int j=0;j&n;j++) { While (choosing[j]) {} While ((number[j]!=0)&&(number[j],j)&(number[i],i) {} } /*critical section*/ Number[i]=0; /*remainder*/; } 数组 choosing 和 number 分别被初始化成 false 和 0， 每个数组的第 i 个元素可以由进程 i 读或写， 但其他进 程只能读。符号（a，b）&（c，d）被定义成 （a，c）或（a=c 且 b&d） A． 用文字描述这个算法。 B． 说明这个算法避免了死锁。 C． 说明它实施了互斥。 答： a.当一个进程希望进入临界区时,它被分配一个票号.分配的票号是通过在目前那些等待进入临界区的进 程所持票号和已经在临界区的进程所持票号比较,所得最大票号再加 1 得到的.有最小票号的进程有最高的 优先级进入临界区.当有多个进程拥有同样的票号时,拥有最小数字号进入临界区.当一个进程退出临界区时, 重新设置它的票号为 0. b.如果每个进程被分配唯一的一个进程号,那么总会有一个唯一的,严格的进程顺序.因此,死锁可以 避免. c.为了说明互斥,我们首先需要证明下面的定理:如果 Pi 在它的临界区,Pk 已经计算出来它的 number[k],并试图进入临界区,此时就有下面的关系式: ( number[i], i ) & ( number[k], k ).为证明定理,定义下11 面一些时间量: Tw1:Pi 最后一次读 choosing[k], 当 j=k,在它的第一次等待时,因此我们在 Tw1 处有 choosing[k] = false. Tw2:Pi 开始它的最后执行, 当 j=k,在它的第二次 while 循环时,因此我们有 Tw1 & Tw2. Tk1:Pk 在开始 repeat 循环时;Tk2:Pk 完成 number[k]的计算; Tk3: Pk 设置 choosing[k]为 false 时.我们有 Tk1&Tk2&Tk3. 因为在 Tw1 处,choosing[k]=false,我们要么有 Tw1&Tk1,要么有 Tk3&Tw1.在第一种情况中,我们有 number[i]&number[k],因为 Pi 在 Pk 之前被分配号码;这个满足定理条件.在第二种情况中,我们有 Tk2 & Tk3 & Tw1 & Tw2,因此有 Tk2&Tw2.这意味着在 Tw2 时,Pi 已经读了当前 number[k]的值.而且,因为 Tw2 是当 j=k 第 二次 while 循环执行发生的时刻,我们有(number[i], i ) & ( number[k], k),这样完成了定理的证明.现在就很容 易说明实施了互斥.假定 Pi 在临界区,Pk 正试图进入临界区.Pk 将不能进入临界区,因为它会发现 number[i] 不等于 0,并且( number[i], i ) & ( number[k], k ). 5.7 当按图 5.2 的形式使用一个专门机器指令提供互斥时， 对进程在允许访问临界区之前必须等待多久没有 控制。设计一个使用 testset 指令的算法，且保证任何一个等待进入临界区的进程在 n-1 个 turn 内进入，n 是要求访问临界区的进程数，turn 是指一个进程离开临界区而另一个进程获准访问这个一个事件。 答：以下的程序由[SILB98]提供： var j: 0..n-1; key: repeat waiting[i] := key := while waiting[i] and key do key := testset(lock); waiting[i] := & critical section & j := i + 1 while (j ≠ i) and (not waiting[j]) do j := j + 1 if j = i then lock := false else waiting := & remainder section & Until 这个算法用最普通的数据结构：var waiting: array [0..n C 1] of boolean Lock：boolean 这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索 waiting 的循环队列 5.8 考虑下面关于信号量的定义： Void semWait(s) { If (s.count&0) { s.count--; } Else { Place this process in s. B } }12 Void semSignal(s) { If (there is at liast one process blocked on semaphore) { Remove a process P from s. Place process P } Else s.count++; } 比较这个定义和图 5.3 中的定义， 注意有这样的一个区别： 在前面的定义中， 信号量永远不会取负值。 当在程序中分别使用这两种定义时， 其效果有什么不同？也就是说， 是否可以在不改变程序意义的前提下， 用一个定义代替另一个？ 答：这两个定义是等价的，在图 5.3 的定义中，当信号量的值为负值时，它的值代表了有多少个进程 在等待；在此题中的定义中，虽然你没有关于这方面的信息，但是这两个版本的函数是一样的。 5.9 可以用二元信号量实现一般信号量。我们使用 semWaitB 操作和 semSignalB 操作以及两个二元信号 量 delay 和 mutex。考虑下面的代码 Void semWait(semaphor s) { semWaitB(mutex); s--; if (s&0) { semSignalB(mutex); semWaitB(delay); } Else Semsignalb(mutex) } Void semSignal(semaphore s); { semWaitB(mutex); s++; if(s&=0) semSignalB(delay); semSignalB(mutex); } 最初。S 被设置成期待的信号量值，每个 semwait 操作将信号量减 1，每个 semsignal 操作将信号量加 1. 二元信号量 mutex 被初始化成 1，确保在更新在更新 s 时保证互斥，二元信号量 delay 被初始化成 0，用 于挂起进程， 上面的程序有一个缺点，证明这个缺点，并提出解决方案。提示：假设两个进程，每个都在 s 初始化 为 0 时调用 semwait（s）,当第一个刚刚执行了 semsignalb（mutex）但还没有执行 semwaitb（delay）， 第二个调用 semwait（s）并到达同一点。现在需要做的就是移动程序的一行. 答：假设两个进程，每个都在 s 被初始化成 0 时调用 semWait（s），当第一个刚执行了 semSignalB （mutex） 但还没有执行 semWaitB （delay） 第二个调用 semWait s） 时， （ 并到达同一点。 因为 s=-2 mutex 没有锁定， 假如有另外两个进程同时成功的调用 semSignal s） 他们接着就会调用 semsignalb （ ， （delay） ，13 但是第二个 semsignalb 没有被定义。 解决方法就是移动 semWait 程序中 end 前的 else 一行到 semSignal 程序中最后一行之前。因此 semWait 中的最后一个 semSignalB(mutex)变成无条件的，semSignal 中的 semSignalb(mutex)变成了有 条件的。 5.10 1978 年，dijkstra 提出了一个推测，即使用有限数目的弱信号量，没有一种解决互斥的方案，使用于 数目未知但有限的进程且可以避免饥饿。1979 年，j.m.morris 提出 了一个使用三个弱信号量的算法，反 驳了这个推测。算法的行为可描述如下，如果一个或多个进程正在 semwait（s）操作上等待，另一个进 程正在执行 semsignal（s），则信号量 s 的值未被修改，一个等待进程被解除阻塞，并且这并不取决于 semwait（s）。除了这三个信号量外，算法使用两个非负整数变量，作为在算法特定区域的进程的计数器。 因此，信号量 A 和 B 被初始化为 1，而信号量 M 和计数器 NA，NM 被初始化成 0.一个试图进入临界区的 进程必须通过两个分别由信号量 A 和 M 表示路障，计数器 NA 和 NM 分别含有准备通过路障 A 以及通过 路障 A 但还没有通过路障 M 的进程数。在协议的第二部分，在 M 上阻塞的 NM 个进程将使用类似于第一 部分的串联技术，依次进入他们的临界区，定义一个算法实现上面的描述。 答：这个程序由[RAYN86]提供： var a, b, m: na, nm: 0 ? +∞; a := 1; b := 1; m := 0; na := 0; nm := 0; semWait(b); na ← na + 1; semSignal(b); semWait(a); nm ← nm + 1; semwait(b); na ← na C 1; if na = 0 then semSignal(b); semSignal(m) else semSignal(b); semSignal(a) semWait(m); nm ← nm C 1; &critical section&; if nm = 0 then semSignal(a) else semSignal(m) 5.11 下面的问题曾被用于一个测试中： 侏罗纪公园有一个恐龙博物馆和一个公园，有 m 个旅客和 n 辆车，每辆车只能容纳一名旅客。旅客在博物 馆逛了一会儿，然后派对乘坐旅客车。当一辆车可用时，它载入一名旅客，然后绕公园行驶任意长的时间。 如果 n 辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那 么这辆车等待。使用信号量同步 m 个旅客进程和 n 个进程。下面的代码框架是在教室的地板上发现的。忽 略语法错误和丢掉的变量声明，请判定它是否正确。注意，p 和 v 分别对应于 semwait 和 semsignal。 Resource Jurassic_Park() Sem car_avail:=0,car_taken:=0,car_fillde:=0.passenger_released:=0 Process passenger(i:=1 to num_passengers) Do true-&nap(int(random(1000*wander_time))) P(car avail);V(car_taken);P(car_filled) P(passenger_released) Od End passenger Process car(j:=1 to num_cars) Do true-&V(car_avail);P(car_taken);V(car_filled) Nap(int(random(1000*ride_time))) V(passenger_released)14 Od End car End Jurassic_Park 答： 这段代码有一个重要问题.在 process car 中的代码 V(passenger_released)能够解除下面一种旅 客的阻塞,被阻塞在 P(passenger_released)的这种旅客不是坐在执行 V()的车里的旅客. 5.12 在图 5.9 和 5.3 的注释中，有一句话是“仅把消费者临界区（由 s 控制）中的控制语句移出还是 不能解决问题，因为这将导致死锁”，请用类似于表 5.3 的表说明。 答： Producer 1 2 3 4 5 6 7 8 9 10 生产者和消费者都被阻塞。 5.13 考虑图 5.10 中定义的无限缓冲区生产者/消费者问题的解决方案。 假设生产者和消费者都以大致 相同的速度运行，运行情况如下： 生产者：semS???semSignal 消费者：semWsemW 生产者通常管理给换成区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个 空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量 的信号量调用，从而产生相当多的开销。 构造一个新程序使得能在这种情况下更加有效。 提示：允许 n 的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生 产者产生新数据。这个方案不需要使用图 5.10 中的局部变量 m。 答： 这个程序来自于[BEN82] prog var n: s: (*binary*) semaphore (:= 1); delay: (*binary*) semaphore (:= 0);
semWaitB(s); n := n + 1; if n=0 then semSignalB(delay); semWaitB(s) SemWaitB(S) n++ If(n==1) (semSignalB(delay)) semSignalB(s) semWaitB(delay) semWaitB(s) n-If(n==0) (semWaitB(delay)) Consumer s 1 0 0 0 1 1 0 n 0 0 1 1 1 1 1 0 delay 0 0 0 1 1 0 0 015 semSignalB(s) begin repeat semWaitB(s); n := n C 1; if n = -1 then begin semSignalB(s); semWaitB(delay); semWaitB(s) semSignalB(s) begin (*main program*) n := 0; consumer parend end. 5.14 考虑图 5.13.如果发生下面的交换，程序的意义是否会发生改变？ a.semWait(e);semWait(s) b.semSignal(s);semSignal(n) c.semWait(n);semWait(s) d.semSignal(s);semSignal(e) 答：只要交换顺序都会导致程序错误。信号量 s 控制进入临界区，你只想让临界区区域包括附加或采取功 能。 5.15 在讨论有限缓冲区（见图 5.12）生产者/消费者问题时，注意我们的定义允许缓冲区中最多有 n-1 个 入口？ a.这是为什么？ b.请修改程序，以不久这种低调？ 答：如果缓冲区可以容纳 n 个入口，问题在于如何从一个满的缓冲区中区分出一个空的缓冲区，考虑一个 有六个位置的缓冲区，且仅有一个入口，如下： A Out in 然后，当一个元素被移出，out=in。现在假设缓冲区仅有一个位置为空： D E A B C In out 这样，out=in+1.但是，当一个元素被添加，in 被加 1 后，out=in，当缓冲区为空时同理。 b．你可以使用一个可以随意增加和减少的辅助的变量，count。16 5.16 这个习题说明了使用信号量协调三类进程。圣诞老人在他北极的商店中睡眠，他只能被一下两种情况 之一唤醒： （1）所有九头驯鹿都从南太平洋的假期回来了，或者（2）某些小孩在制作玩具时遇到了困难。 为了让圣诞老人多睡会， 这些孩子只有在是那个人都遇到困难时才唤醒他。 当三个孩子的问题得到解决时， 其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等 待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦 iuxunlu 必须与其他 unlu 在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。 答：santa:圣诞老人 reindeer:驯鹿 elf:小孩子 sleigh:雪橇 toys:玩具5.17 通过一下步骤说明消息传递和信号量具有同等的功能： a.用信号量实现消息传递。提示：利用一个共享缓冲区保存信箱，每个信箱由一个消息槽数组成的。 b.用消息传递实现信号量。提示：引入一个独立的同步进程。 答：b.这个方法来自于[TANE97].同步进程维护了一个计数器和一个等待进程的清单。进程调用相关用于 向同步进程发送消息的生产者，wait 或 signal，来实现 WAITHUO SIGNAL.然后生产者执行 RECEIVE 来17 接受来自于同步进程的回复。 当消息到达时，同步进程检查计数器看需要的操作是否已经足够，SIGNALs 总是可以完成，但是假如信 号值为 0 时， WAITs 将会被阻塞。 假如操作被允许， 同步进程就发回一个空消息， 因此解除调用者的阻塞。 假如操作是 WAIT 并且信号量的值为 0 时，同步进程进入调用队列，并且不发送回复。结果是执行 WAIT 的进程被阻塞。当 SIGNAL 被执行，同步进程选择一个进程在信号量上阻塞，要不就以先进先出顺序，要 不以其他顺序，并且发送一个回复。跑步条件被允许因为同步进程一次只需要一个。第6章并发性：死锁和饥饿６.１写出图６.１（a）中死锁的四个条件。 解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。占有且等待：没有车可以倒退；在十字路口 的每辆车都要等待直到它前面的象限是空的。非抢占: 没有汽车被允许挤开其他车辆。 循环等待: 每辆 汽车都在等待一个此时已经被其他车占领的十字路口象限。 ６.２按照６.１节中对图６.２中路径的描述，给出对图６.３中６种路径的简单描述。 解：１.Q 获得 B 和Ａ, 然后释放 B 和 A. 当 P 重新开始执行的时候, 它将会能够获得两个资源。 2. Q 获得 B和Ａ， P 执行而且阻塞在对 A的请求上. Q释放 B 和Ａ。当 P 重新开始执行的时候，它将 会能够获得两个资源。 3. Q 获得 B ，然后 P 获得和释放 A. Q 获得Ａ然后释放 B 和 A. 当 P 重新开始行的时候，它将会能够获得 B。 4. P 获得Ａ然后 Q 获得 B. P 释放 A. Q 获得Ａ然后释放 B. P 获得 B 然后释放 B。 5. P 获得，然后释放 A. P 获得 B. Q 执行而且阻塞在对Ｂ的请求上。Ｐ释放Ｂ。当 Q 重新开始执行的 时候，, 它 r1 r2 r3 r4 r1 r2 r3 r4 r1 r2 r3 r4 将会能够 获得两个 资源。 6. P 获得 Ａ而且释 放Ａ然后获得并且释放 B. 当 Q 重新开始实行, 它将会能够获得两个资源。 ６.３图６.３反映的情况不会发生死锁，请证明。 证明：如果 Q 获得 B 和Ａ（在 P之前请求Ａ）, 那么 Q 能使用这些两类资源然后释放他们, 允许Ａ进 行。 如果 P在 Q之前请求Ａ获得Ａ, 然后Q 最多能执行到请求Ａ然后被阻塞。 然而,一旦 P 释放 A ， Q 能进行。 一旦 Q 释放 B, Ａ能进行。 ６.４考虑下面的一个系统，当前不存在未满足的请求。 2 1 0 0r1可用 r2 r3r4当前分配最大需求仍然需求18 0 2 0 2 00 0 0 3 31 0 3 5 32 0 4 4 20 2 6 4 00 7 6 3 61 5 5 5 52 0 6 6 2 a计算每个 进程仍然 可能需要 的资源，并 填入标为“仍然需要”的列中。 b系统当前是处于安全状态还是不安全状态，为什么。 c系统当前是否死锁？为什么？ d哪个进程（如果存在）是死锁的或可能变成死锁的？ e如果Ｐ３的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不 安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可 能变成死锁的？ 解： a. 0 0 0 0 0 7 5 0 6 6 2 2 2 0 0 2 0 3 2 0 b.系统当前处于安全状态， 因为至少有一个进程执行序列， 不会导致死锁， 运行顺序是p1, p4, p5, p2, p3. c.系统当前并没有死锁，因为 P1 进程当前分配与最大需求正好相等，P1 进程可以运行直至结束，接 下来运行其他进程 d.P2,P3,P4,P5 可能死锁 e.不可以，当进程 P1,P4,P5 执行完可用资源为（4，6，9，8） ，P2,P3 将死锁，所以不安全，完全不 可以立即同意系统剩下的全部请求。 ６.５ 请把６.４中的死锁检测算法应用于下面的数据，并给出结果。Available=(2100) 0 0 1 0 Allocation= 2 0 0 1 0 1 2 02 0 0 1 Request= 1 0 1 0 2 1 0 0 解： 1. 2. 3. 4. W = (2 1 Mark P3; Mark P2; Mark P1;0 0) W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0) W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1) no deadlock detected 没有死锁６.６一个假脱机系统包含一个输入进程Ｉ，用户进程进程Ｐ和一个输出进程Ｏ，它们之间用两个缓冲区 连接。进程以相等大小的块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在 磁盘上，并取决于进程的速度。所使用的通信原语确保满足下面的资源约束：i+o? ≤max 其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目， o表示磁盘中的输出块数目。19 I输入 缓冲区P输出 缓冲区o以下是关于进程的知识： １. 只要环境提供数据，进程Ｉ最终把它输入到磁盘上（只要磁盘空间可用）。 ２. 只要磁盘可以得到输入，进程Ｐ最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁 盘空间可用）。 ３. 只要磁盘可以得到输出，进程Ｏ最终消耗掉它。说明这个系统可能死锁。 解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理 数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。 ６.７给出在习题６.６中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程 的要求变化。 解：为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一 个界限。 资源限制现在变成 Ｉ + Ｏ ? ≤max Ｉ≤? max C reso 当0 & reso & max 如果程序 P 正在等候递送输出给磁盘, 程序 O 最后处理所有的早先输出而且产生至少reso页, 然后让 P 继续执行。 因此 P 不会因为 O 而延迟。 如果磁盘充满I/O，Ｉ能被延迟; 但是迟早, 所有的早先的 输入可以被Ｐ处理完，而且对应的输出将会被 O 处理, 因而可以让Ｉ继续执行。 ６.８在ＴＨＥ多道程序设计系统中，一个磁鼓（磁盘的先驱，用做辅存）被划分为输入缓冲区，处理和 输出缓冲区，它们的边界可以移动，这取决于所涉及的进程速度。磁鼓的当前状态可以用以下参数描述： ? max表示磁鼓中的最大页数， i示磁鼓中的输入页数， p示磁鼓中的处理页数， o示磁鼓中的输出页数， reso 出保留的最小页数，resp理保留的最小页数。 解： Ｉ + Ｏ + Ｐ≤? max C Ｉ + Ｏ≤? max C resp Ｉ + Ｐ ≤? max C reso Ｉ ≤? max C (reso + resp) ６．９在ＴＨＥ多道程序设计系统中，一页可以进行下列状态转换： １.空→输入缓冲区（输入生产） ２.输入缓冲区→处理区域（输入消耗） ３.处理区域→输出缓冲区（输出生产） ４.输出缓冲区→空（输出生产） ５.空→处理区域（输出消耗） ６.处理区域→空（过程调用） a根据Ｉ，Ｏ和Ｐ的量定义这些转换的结果。20 b如果维持习题６.６中关于输入进程，用户进程和输出进程的假设，它们中的任何一个转换是否会导致死 锁。 解： 1. i ←? i + 1 2. i←? i C 1; p ←? p + 1 3. p←? p C 1; o←? o + 1 4. o ←? o C 1 5. p←? p + 1 6. p ←? p C 1 b. 结合在对问题 6.7 的解决办法被列出的资源限制, 我们 能总结下列各项: 6. 过程返回能立刻发生因为他们只释放 资源。 5. 程序调用可能用尽磁盘片 (p= max C reso) 导致死锁。 4. 当有输出时输出消耗能立刻发生。 3. 输出生产能暂时被延迟直到所有的早先输出被消耗而且为下一步的输出至少可以产生reso页。 2. 只要有输入，输入消耗能立刻发生。 1. 输入生产被延迟直到所有先前输入和对应的输出已经被消耗。 此时, 当 i= o=0,如果消费进程还没有 占用完磁盘空间 ( p & max C reso)，可以产生输入。 结论: 分配给消费进程的不受控制的存储空间是 唯一可能引发死锁的因素。 ６.１０考虑一个共有１５０个存储器单元的系统，其单元如下分配三个进程： 进程 1 2 3 最大 70 60 60 占用 45 40 15使用银行家算法，以确定同意下面的任何一个请求是否安全。如果安全，说明能保证的终止序列；如果不 安全，给出结果分配简表。 a．第４个进程到达，最多需要６０个存储单元，最初需要２５个单元。 b第４个进程到达，最多需要６０个存储单元，最初需要３５个单元。 解： a.若同意第4个进程请求，则储存器单元共用去25＋15＋40＋45=125个单元，还有25个存储单元，则 可以安全执行全部进程。安全顺序是1－2－3－4 b.若同意第4个进程请求，则还有15个资源可以用，此时处于不安全状态，结果分配见表 进程 最大 占有 需要 空闲 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25 ６.１１评价独家算法在实际应用中是否有用。 解：不切实际的: 不能总是预先知道最大要求, 进程数目和资源数目可能随着时间改变 。大多数的操作 系统忽视死锁。 ６.１２有一个已经实现了的管道算法，使得进程Ｐ０产生的Ｔ类型的数据元素经进程序列Ｐ1Ｐ2?Ｐn-1, 并且按该顺序在元素上操作。 a.定义一个一般的消息缓冲区，包含所有部分消耗的数据元素，并按下面的格式为进程Ｐi(0≤i≤n-1)写 一个算法。 Repeat21 从前驱接收 消耗 给后续发送 Forever 假设Ｐ0收到Ｐn-1发送的空元素。该算法能够使进程直接在缓冲区中保存的消息上操作，而无需复制。 b.说明关于普通的缓冲区进程不会死锁。 解：ar buffer: array 0..max-1 of shared T; available: shared array 0..n-1 of 0.. &Initialization& var K: 1..n-1; region available do begin available(0) := for every k do available (k) := 0; end &Process i& var j: 0..max-1; succ: 0..n-1; begin j := 0; succ := (i+1) repeat region available do await available (i) & 0; region buffer(j) region available do begin available (i) := available(i) C 1; available (succ) := available (succ) + 1; end j := (j+1) forever end b.死锁可以被解决通过 P0 waits for Pn-1 AND P1 waits for P0 AND . . . . . Pn-1 waits for Pn-2 因为 (available (0) = 0) AND (available (1) = 0) AND . . . . . (available (n-1) = 0) 但是如果max & 0,这个条件不成立，因为临界域满足 claim(1)+ claim(2)+ ?+claim(n) & available(1)+available(2)+?+available(n) =max22 ６.１３ a.３个进程共享４个资源单元，一次只能保留或释放一个单元。每个进程最大需要２个单元。 说明不会死锁。 b.Ｎ个进程共享Ｍ个资源单元，一次只能保留或释放一个单元。每个进程最大需要单元数不超过Ｍ，并且 所有最大需求的总和小于Ｍ+Ｎ。说明不会发生死锁。 解：a.说明由于每个进程最多需要 2 个资源，最坏情况下，每个进程需要获得一个，系统还剩 1 个，这一 个资源，无论分给谁都能完成。完成进程释放资源后，使剩余进程也完成，故系统不会死锁。 b.假定每个进程最多申请 X 个资源， 最坏情况下， 每个进程都得到 X-1 个资源都在申请最后一个资源， 这时系统剩余资源数量为 M-N(X－1)，只要系统还有一个剩余资源，就可以使其中的一个进程获得所需要 的全部资源， 该进程运行结束以后释放资源， 就可以使其他进程得到全部资源的 满足， 因此， M-N(X-1)》 当 1 时系统不会发生死锁，解这个不等式 X《（M+N-1）,系统不会发生死锁，因此，当所有进程的需求总和 小于 M+N 时，系统是不会发生死锁的。 ６.１４考虑一个由四个进程和一个单独资源组成的系统，当前的声明和分配矩阵是 3 1 2 1 C = 9 A= 3 7 2 对于安全状态，需要的最小资源数目是多少？ 解：最小资源数是３个，总共有１０个资源。Ｐ２获得一个资源，完成后释放两个资源，Ｐ１获得三 个资源，完成后释放三个资源，接下来Ｐ４获得五个资源，释放完资源后，Ｐ３获得所需的６个资源后完 成。 ６.１５考虑下列处理死锁的方法：1 银行家算法，2 死锁检测并杀死线程，释放所有资源，３事先保 留所有资源，４如果线程需要等待，５资源排序，６重新执行检测死锁并退回线程的动作。 评价解释死锁的不同方法使用的一个标准是，哪种方法允许最大的并发。换言之，在没有死锁时，哪 种方法允许最多数目的线程无需要等待继续前进？对下面列出的６种处理死锁的方法，给出从１到６的一 个排序（１表示最大程序的并发），并解释你的排序。 另一个标准是效率；哪种方法需要最小的处理器开销？假设死锁很少发生，给出各种方法从１到６的 一个排序（１表示最有效），并解释这样排序的原因。如果死锁发生很频繁，你的顺序需要改变吗？ 解：a从最多并发事件到最少, 有一个大概的次序如下： 1. 死锁检测并杀死线程，释放所有资源 发现死锁并退回线程的动作， 如果线程需要等候那么重新开始线程而且释放所有的资源， 在死锁发生之前， 这些运算法则都不会限制并发, 因为他们仰赖运行时间检查而并非静态的限制。 他们的效果在死锁被发 现比较难以描述：他们仍然允许许多并发(在一些情形，他们增加它), 但是很难有准确的估计。 第三个 运算法则是最奇怪的, 因为如此后许多的它的并发将会是无用的重复; 因为线程竞争执行时间, 这一个 运算法则也影响运行速度。 因此在两者的极端,它以这顺序被列出两次。 2. 银行家的运算法则 资源排序 这些运算法则因为限制多种的可允许的计算，而相对早先两种法则会引起更多的不必要的等候。 银行家 的运算法则避免不安全的配置 和资源排序限制配置序列以便线程在他们是否一定等候的时候有较少的选 择。 3. 事先保留所有的资源 这一个运算法则相比前两个要允许更少的并发, 但是比最坏的那一种有更少的缺点。因为要预先保留所有 的资源,线程必须等候比较长的而且当他们工作的时候更有可能阻塞其他的线程,因此系统上来说具有更 多的线性。 4. 如果线程需要等待，则重新启动线程并且释放所有的资源23 如上所述, 这一个运算法则在区别最多和最少并发上有疑问,这具体要看并发的定义。 b从最高效率到最低，有如下大概的一个顺序： 1. 预先保留所有的资源 资源排序 因为他们没有包括运行时间经常开支，所以这些运算法则最有效率。 注意这是在相同的静态限制下的结果。 2. 银行家的运算法则 发现死锁而且杀死线程,释放它的资源 这些运算法则在概略的配置上包括运行时间检查 ; 银行家的运算法则运行搜寻查证复杂度在线程和配置的数字和死锁检测中是 O(n m)，死锁检测的复杂 度是 O(n)。资源-从属链被线程数目，资源数目和分配数目限制。 3. 发现死锁并退回线程的动作 这一个运算法则运行也需要运行上述的相同的时间检查。 在写内存上的复杂度为O(n) 。 4. 如果线程需要等待，则重新启动线程并释放所有的资源 这一个运算法则是非常无效率，有如下两个理由。 首先, 因为线程有重新开始的危险, 他们完成的可能 性低。其次，他们与其他重新开始线程竞争有限的执行时间, 因此整个系统运行的速度很慢。 ６.１６评价下面给出的就餐问题的解决方案。一位饥饿的哲学家首先拿起他左边的叉子，如果他右边的 叉子也是可用的，则拿起右边的叉子开始吃饭，否则他放下左边的叉子，并重复这个循环。 解： 如果哲学家们步调完全一致地拿起左边叉子又放下的话， 他们会重复这一过程， 导致饥饿情况的出现。 ６.１７假设有两种类型的哲学家。一类总是先拿起左边的叉子（左撇子），另一类总是先拿起右边的叉 子（右撇子）。左撇子的行为和图６.１２中定义的一致。右撇子的行为如下： wait(fork[(i+1)mod5]); wait(fork[i]); signal(fork[i]); signal(fork[(i+1)mod5]); 证明：a 如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁。 b如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿。 解：a假设存在死锁情况，设有 D个哲学家，他们每人都有一支叉子而且另一支叉子被邻居占有。不失一 般性，设Pj 是一个左撇子。 Pj 抓牢他的左边叉子而且没有他的右边叉子, 他的右边邻居 Pk 没有完成 就餐因此也是一个左撇子。 因此依次推理下去所有这Ｄ个哲学家都是左撇子。这与既有左撇子又有右撇 子的条件矛盾，假设不成立，不存在死锁。 b 假设左撇子 Pj 饥饿，也就是说，有一部分人在就餐而Pj从不吃。 假如 Pj 没有叉子。 这样 Pj 的左边 邻居 Pi 一定持续地占有叉子而始终不吃完。 因此Pi 是 右撇子， 抓住他的右边叉子, 但是从不得到他的左边叉子来完成就餐,也就是说 Pi 也饥饿。 现在 Pi 左边邻居也一定是持续占有右边叉子的右撇子。 向左进行这样的推理，得出所有哲学 家都是饥饿的右撇子，这同Pj是个左撇子矛盾。因此 Pj 一直拥有左边子而且在等待他的右边叉子,Pj 的 右边邻居 Pk 一直举着他的左边叉子而且从不完成一餐,也就是, Pk 是也饥饿的左撇子。 如果 Pk 不是24 一直拿着他的左边叉子， Pj 就可以就餐;因此 Pk 拿着他的左边叉子。向右推理可得所有哲学家都是饥 饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。 ６.１８图１.１７显示了另外一个使用管程解决哲学家就餐问题的方法。和图６.１４比较并阐述你的结 论。 解：图６.１４是等待可用的叉子，图６.１７是等待邻居吃完，在本质上逻辑是一样的，后者显得更加紧 凑。monitor dining_ 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]= /*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]= /*proceed if neither neighbor is eating*/ } void release_fork(int pid) { state[pid]= /*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] csignal(needFork[pid-1]); } void philosopher[k=0 to 4] /*the five philosopher clients*/ { while(true) { &think&; get_forks(k); /*client requests two forks via monitor*/ &eat spaghetti&; release_forks(k); /*client releases forks via the monitor*/ } }25 ６.１９在表６.１３中，Linux的一些原子操作不会涉及到对同一变量的两次访问。比如 atomic_read(atomic_t *v).简单的读操作在任何体系结构中都是原子的。为什么该操作增加到了原子操 作的指令表？ 解：原子操作是在原子数据类型上操作, 原子数据类型有他们自己的内在的 格式。 因此，不能用简单的阅读操作, 但是特别的阅读操作 对于原子数据类型来说是不可或缺的。 ６.２０考虑Linux系统中的如下代码片断： read_lock(&mr_rwlock); write_lock(&mr_rwlock); mr_rwlock是读者写者锁。这段代码的作用是什么？ 解：因为写者锁将会自旋，所以这段代码会导致死锁, 等待所有的 读者解锁, 包括唤醒这个线程。 ６.２１两个变量a和b分别有初始值１和２，对于Linux系统有如下代码： 线程 1 a = 3； mb( )； --线程 2 --c = b； rmb()； d = a；使用内在屏障是为了避免什么错误？ 解：没有使用内存屏障, 在一些处理器上可能 c接到b 的新值, 而d接到b 的旧值。 举例来说, c可以等 于 4(我们期待的), 然而 d 可能等于 1.(不是我们期待的)。 使用mb() 确保a 和 b 按合适的次序被写, 使用 rmb()确保 c 和d 按合适的次序被读。第 7 章 内存管理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。从平均意义上讲，平26 均查找长度是 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.d. 40M,20M,10M,的起始地址是 80M,230M,360M.7.7. 使用伙伴系统分配一个 1MB 的存储块。 a. 利用类似于图 7.6 的图来说明按下列顺序请求和返回的结果：请求 70；请求 35；请求 80；返回 A；请求 60；返回 B；返回 D；返回 C。 b. 给出返回 B 之后的二叉树表示。 答： a.27 b.7.8.考虑一个伙伴系统，在当前分配下的一个特定块地址为. a. 如果块大小为4，它的伙伴的二进制地址为多少？ b. 如果块大小为16，它的伙伴的二进制地址为多少？ 答： a.
k 7.9. 令 buddyk(x)为大小为 2 、地址为 x 的块的伙伴的地址，写出 buddyk(x)的通用表达式。 答：7.10. Fabonacci 序列定义如下： F0=0,F1=1,Fn+2=Fn+1+Fn,nR0 a. 这个序列可以用于建立伙伴系统吗？ b. 该伙伴系统与本章介绍的二叉伙伴系统相比，有什么优点？ 答： a. 是。字区大小可以确定 Fn = Fn-1 + Fn-2.。 b. 这种策略能够比二叉伙伴系统提供更多不同大小的块，因而具有减少内部碎片的可能性。但由于 创建了许多没用的小块，会造成更多的外部碎片。28 7.11. 在程序执行期间，每次取指令后处理器把指令寄存器的内容（程序计数器）增加一个字，但如果遇 到会导致在程序中其他地址继续执行的转跳或调用指令，处理器将修改这个寄存器的内容。现在考 虑图 7.8。关于指令地址有两种选择： ? 在指令寄存器中保存相对地址，并把指令寄存器作为输入进行动态地址转换。当遇到一次成功的 转跳或调用时，由这个转跳或调用产生的相对地址被装入到指令寄存器中。 ? 在指令寄存器中保存绝对地址。当遇到一次成功的转跳或调用时，采用动态地址转换，其结果保 存到指令寄存器中。 哪种方法更好？ 答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。因此，在指 令寄存器中保存相对地址似乎就更好一些。也可以选择在进程被换出主存时将指令寄存器中的地址 转换为相对地址。 32 10 16 7.12. 考虑一个简单分页系统，其物理存储器大小为 2 字节，页大小为 2 字节，逻辑地址空间为 2 个页。 a. 逻辑地址空间包含多少位？ b. 一个帧中包含多少字节？ c. 在物理地址中指定帧需要多少位？ d. 在页表中包含多少个页表项？ e. 在每个页表项中包含多少位？（假设每个页表项中包含一个有效/无效位） 答： 16 10 26 a. 物理地址空间的比特数是 2 *2 =2 10 b. 一个帧包含的字节跟一个页是一样的,2 比特. 32 10 22 c. 主存中帧的数量是 2 /2 =2 ,所以每个帧的定位要 22 个比特 16 d. 在物理地址空间,每个页都有一个页表项,所以有 2 项 e. 加上有效/无效位，每个页表项包含 23 位。 7.13. 分页系统中的虚地址 a 相当于一对（p，w） ，其中 p 是页号，w 是页中的字节号。令 z 是一页中的字 节总数，请给出 p 和 w 关于 z 和 a 的函数。 答：关系是：a = pz + w，其中 p = Na/z?, a/z 的整数部分。w = Rz(a) ，a 除以 z 的余数 7.14. 在一个简单分段系统中，包含如下段表： 起始地址 660
长度（字节） 248 442 198 604对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生： a. 0，198 b. 2，256 c. 1，530 d. 3，444 e. 0，222 答： a. 段 0 定位在 660,所以我们有物理地址 660+190=858. b. 222+156=378 c. 段 1 长度为 422,所以会发生错误 d. 996+444=1440 e. 660+222=882. 7.15. 在内存中，存在连续的段 S1,S2,?，Sn 按其创建顺序一次从一端放置到另一端，如下图所示： 当段 Sn+1 被创建时，尽管 S1,S2,?，Sn 中的某些段可能已经被删除，段 Sn+1 仍被立即放置在段 Sn 之后。29 当段（正在使用或已被删除）和洞之间的边界到达内存的另一端时，压缩正在使用的段。 a. 说明花费在压缩上的时间 F 遵循以下的不等式： FR(1-f)/1+kf), k=t/2s-1 其中，s 表示段的平均长度（以字为单位） 标识段的平均生命周期，按存储器访问；f 表示在 ；l 平衡条件下，未使用的内存部分。提示：计算边界在内存中移动的平均速度，并假设复制一个字 至少需要两次存储器访问。 b. 当 f=0.2，t=1000，s=50 时，计算 F。 答： a. 很明显,在一个周期 t 内一些段会产生而一些段会被删除.因为系统是公平的,一个新的段会在 t 内被插入,此外,边界会医 s/t 的速度移动.假设 t0 是边界到达空洞的时间,t0=fmr/s, m=内存的长 度,在对段进行压缩时会有(1-f)m 个数被移动,压缩时间 至少是 2(1-f)m.则花在压缩上的时间 F 为 F=1-t0/(t0+tc)。 b. K=(t/2s)-1=9;FR(1-0.2)/(1+1.8)=0.29第8章虚拟内存8.1 假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从 0 开始记数的，并且所有的地址都是内存字节地址。页尺寸为 1024 个字节。 虚拟页号 有效位 访问位 修改位 页帧号 0 1 1 0 4 1 1 1 1 7 2 0 0 0 ― 3 1 0 0 2 4 0 0 0 ― 5 1 0 1 0 a． 描述 CPU 产生的虚拟地址通常是如何转化成一个物理主存地址的。 b．下列虚拟地址对应于哪个物理地址（不用考略页错误）？ （i）1052 （ii）2221 （iii）5499 解答 a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到 物理地址 b:(i) 查表对应的页帧号是 7，因此物理地址为 7*6 (ii)4+173 此时出现页错误 (iii)4+379 对应的页帧号为 0 因此物理地址是 379 8.2 考虑一个使用 32 位的地址和 1KB 大小的页的分页虚拟内存系统。 每个页表项需要 32 位。 需要限制页表的大小为一个页。 a．页表一共需要使用几级？ b．每一级页表的大小是多少？提示：一个页表的大小比较小。 c．在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页？ 解答 a：虚拟内存可以分为 232/210= 222 页，所以需要 22 个 bit 来区别虚拟内存中的一页，每一个 页表可以包含 210/4=28 项，因此每个页表可以包含 22bit 中的 8 个 bit，所以需要三级索引。 b：第二级页表有 28 个页表项，第一级页表有 26 个页表项。30 c：如果顶层有 26 个页表项将会减少使用空间，在这种情况下，中间层页表有 26 个并且每个 都有 28 个页表项，底层有 214 个页并且每个都有 28 个页表项，因此共有 1+26+214 页=16,449 页。如果中间层有 26 个页表项，那么总的页数有 1+28+214 页=16,641 页。如果底层有 26 个 页表项，那么总的页表数是 1+28+216 页=65,973 页。 8.3 a：图 8.4 中的用户表需要多少内存空间？ b：假设需要设计一个哈希反向页表来实现与图 8.4 中相同的寻址机制，使用一个哈希函 数来将 20 位页号映射到 6 位哈希表。表项包含页号帧号和链指针。如果页表可以给每个哈 希表项分配最多 3 个溢出项的空间，则哈希反向页表需要占用多大的内存空间？ 解答 a：4Mbyte b：行数：26+2=128 项。每项包含：20（页号）+20（帧号）+8bits（链索引）=48bits=6bytes。 总共：128*6=768bytes 8.4 一个进程分配给 4 个页帧 （下面的所有数字均为十进制数， 每一项都是从 0 开始计数的） 。 上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页 号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之 间的时钟时间，而不是从事件发生到当前的时钟值） 。 虚拟页号 页帧 加载时间 访问时间 R位 M位 2 0 60 161 0 1 1 1 130 160 1 0 0 2 26 162 1 0 3 3 20 163 1 1 当虚拟页 4 发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。 a.FIFO（先进先出）算法 b.LRU（最近最少使用）算法 c.Clock 算法 d.最佳（使用下面的访问串）算法 e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列： 4,0,0,2,4,2,1,0,3,2 如果使用窗口大小为 4 的工作集策略来代替固定分配， 会发生多少页错误？每个页错误何时 发生？ 解答 a:页帧 3，在时间 20 加载，时间最长。 b:页帧 1，在时间 160 访问距现在时间最长。 c:清除页帧 3 的 R 位（最早加载） ，清除页帧 2 的 R 位， （次最早加载） ，换出的是页帧 0 因为 它的 R 位为 0。 d:换出的是页帧 3 中的虚拟页 3，因为它将最晚被访问到。 e:一共有 6 个错误，如下8.5 一个进程访问 5 页：A,B,C,D 和 E，访问顺序如下： A;B;C;D;A;B;E;A;B;C;D;E 假设置换算法为先进后出，该进程在主存中有三个页帧，开始时为空，请查找在这个访问顺31 序中传送的页号。对于 4 个页帧的情况，请重复上面的过程。 解答 分别有 9 次和 10 次页错误，这被称之为“Belady′s 现象” （&An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine,& by Belady et al, Communications of the ACM, June 1969.） 8.6 一个进程在磁盘上包含 8 个虚拟页，在主存中固定分配给 4 个页帧。发生如下顺序的页 访问： 1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3 a.如果使用 LRU 替换策略，给出相继驻留在这 4 个页帧中的页。计算主存的命中率。假设这 些帧最初是空的。 b.如果使用 FIFO 策略，重复问题（a） 。 c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用 FIFO 的效率接近于 LRU。 解答 a:LRU：命中率=16/33b:FIFO：命中率=16/33c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。 8.7 在 VAX 中，用户页表以系统空间的虚拟地址进行定位。让用户页表位于虚存而不是主存 中有什么好处？有什么缺点？ 解答 最主要的优点是在物理内存空间上的节省。这主要是两方面的原因： （1）一个用户页表可以 仅当使用时才取入内存。 （2）操作系统可以动态的分配用户页表，产生一个页表仅当程序被 创建时。 当然，也有一个缺点：地址转换需要多余的工作。 8.8 假设在主存中执行下列程序语句： for(i=1;i≤n;i++) a[i]=b[i]+c[i]; 页尺寸为 1000 个字。令 n=1000。使用一台具有所有寄存器指令并使用了索引寄存器的机器， 写出实现上述语句的一个假想程序，然后给出在执行过程中的页访问顺序。 解答 由机器语言编写的程序，在主存中地址 4000 处开始运行。运行情况如下： 4000 （R1）←1 建立索引记录 i 4001 （R1）←n 在 R2 中建立 n 4002 比较 R2，R1 检查 in 4003 如果大于则跳转到
（R3）←B（R1） 使用索引记录 R1 到达 B[i]32 4005 （R3）←（R3）+C（R1）使用索引记录 R1 加上 C[i] 4006 A（R1）←（R3）使用索引记录 R1 将总和存入 A[i]中 4007 （R1）←（R1）+1 i 加一 4008 跳到 ―6999 存储 A
存储 C 9000 存储 1 9001 存储 n 由这个循环产生的参考串为 ）1000 包括 11.000 个参考，但仅包括 5 个不寻常的页 8.9 IBM System/370 体系结构使用两级存储器结构， 并且分别把这两级称为段和页， 这里的分 段方法缺少本章所描述的关于段的许多特征。对于这个基本的 370 体系结构，页尺寸可以是 2KB 或 4KB，段大小固定为 64KB 或 1MB。这种方案缺少一般分段系统的那些优点？370 的 分段方法有什么好处？ 解答 S/370 分段系统是固定的且对程序员是不可见的， 因此没有一个分段系统的优点在 S/370 中实 现（无保护情况下）每一个段表项的 P 位提供整个段表的保护。 8.10 假设页尺寸为 4KB，页表项大小位 4 字节。如果要映射一个 64 位地址空间，并且最顶 层的页表对应于一页，则需要几级页表？ 解答 因为每个页表项有 4bytes，每个页表有 4Kbytes，所以每个页表可以映射
个页，标识 出 210×212=222bytes 的地址空间。然而，地址空间是 264bytes。增加一个二层页表，顶层页 表指向 210 个页表，标识出 232 个页表，将这个过程继续下去就得到： 深度 地址空间 1 222bytes 2 232bytes 3 242bytes 4 252bytes 5 262bytes 6 272bytes（264bytes） 我们可以看到 5 层是不够表示 64 位的地址空间，但是 6 层达到了要求。但是 6 层中只有 2 位 被使用，而不是全部的 10 位。所以不是使用 72 位的虚拟地址空间，而是将除了最低两位外 的其他位全部屏蔽忽略。这样将会得到一个 64 位地址空间，顶层页只有 4 个页表项。另外一 种方法是修改规则将顶层页做成一个单独的物理页并且让它适合 4 个页。这样将会节省一个 页。 8.11 考虑一个系统该系统采用基于页的内存映射， 并使用一级页表。 假设页表总是在主存中。 a.如果一次存储器访问需要 200ns，那么一次需要调页的存储器访问要多长时间？ b.现在增加一个 MMU，在命中或未命中时有 20ns 的开销。如果假设有 85%的存储器访问命 中都在 MMU TLB 中，那么哪些是有效的存储器访问时间？ c.解释 TLB 命中率如何影响有效的存储器访问时间。 解答 a.400ns。200ns 用来得到页表项，200ns 用来到达存储位置 b.这是一个常见的有效时间计算公式： （220×0.85）+（420×0.15）=25033 两种情况：第一种，TLB 中包含所需的页表项。在这种情况下在 200ns 外多了 20ns 的存储 访问时间。第二种，TLB 中不包含所需的页表项。这时我们会再多花 200ns 来把所需的页表 项取入 TLB。 c.TLB 命中率越高有效存储器访问时间就越短，因为额外的 200ns 来得到页表项的时间被节 省了。 8.12 考虑一个进程的页访问序列，工作集为 M 帧，最初都是空的。页访问串的长度为 P，包 含 N 个不同的页号。对任何一种页替换算法， a.页错误次数的下限是多少？ b.页错误次数的上限是多少？ 解答 a.N b.P 8.13 在论述一种页替换算法时，一位作者用一个在循环轨道上来回移动的雪犁机来模拟说 明：雪均匀地落在轨道上，雪犁机一恒定的速度在轨道上不断的循环，轨道上被扫落的雪从 系统}
id: '2014386',
container: s,
size: '234,60',
display: 'inlay-fix'
&&|&&1次下载&&|&&总261页&&|
您的计算机尚未安装Flash，点击安装&
试读已结束，如果需要继续阅读或下载，请使用积分（）
下载：80积分
本文档由合作伙伴提供
0人评价4页
0人评价324页
0人评价7页
0人评价3页
0人评价266页
此文档归属以下专题
6人评价150个文档
8人评价197个文档
所需积分：（友情提示：大部分文档均可免费预览！下载之前请务必先预览阅读，以免误下载造成积分浪费！）
（多个标签用逗号分隔）
文不对题，内容与标题介绍不符
广告内容或内容过于简单
文档乱码或无法正常显示
文档内容侵权
已存在相同文档
不属于经济管理类文档
源文档损坏或加密
若此文档涉嫌侵害了您的权利，请参照说明。
我要评价：
价格：80积分VIP价：64积分您在慧聪网上采购商品属于商业贸易行为。以上所展示的信息由卖家自行提供，内容的真实性、准确性和合法性由发布卖家负责，请意识到互联网交易中的风险是客观存在的。推荐使用慧付宝资金保障服务，保障您的交易安全！
按字母分类 ：
让慧聪网撮合专家为您解决采购难题
您采购的产品：
请输入采购产品
您的手机号码：
请输入手机号码
*采购产品：
请输入采购产品
*采购数量/单位：
请输入采购数量
请选择单位
*采购截止日期：
请输入正确的手机号码
请输入验证码
*短信验证码：
<input id="valid_Code1" maxlength="6" placeholder="请输入验证码" name="VALIDCODE" class="codeInput" onkeyup="this.value=this.value.replace(/\D/g,'')" onkeypress="if(event.keyCode
57) event.returnValue =" type="text">
免费获取验证码
为了安全，请输入验证码，我们将优先处理您的需求！
请输入验证码
发送成功！
慧聪已收到您的需求，我们会尽快通知卖家联系您，同时会派出采购专员1对1为您提供服务，请您耐心等待！
电话：757- &&
联系人：刘瑞荣&销售部
公司名称：佛山市南海区大沥正特机电商行
#contact_inquiry_self()
每一份需求都会在24小时内得到行业多家优质供应商报价。
每一份需求的报价供应商工商信用资质都会经过专业人员检验，交易安全有保障。
免费咨询行业专家
免费咨询行业专家
服务主题：
筛选发货地
验证供应商真伪
提供其他优质供应商
采购数量：
用途描述：
卖家暂时不在线，留下联系方式，卖家会主动联系您
*我要采购：
我的姓名：
留言内容：当前位置： >>
《操作系统精髓与设计原理?第五版》练习题及答案
第1章计算机系统概述1.1、图 1.3 中的理想机器还有两条 I/O 指令： 0011 = 从 I/O 中载入 AC 0111 = 把 AC 保存到 I/O 中 在这种情况下，12 位地址标识一个特殊的外部设备。请给出以下程序的执行过程（按照图 1.4 的格式） ： 1. 从设备 5 中载入 AC。 2. 加上存储器单元 940 的内容。 3. 把 AC 保存到设备 6 中。 假设从设备 5 中取到的下一个值为 3940 单元中的值为 2。 答案：存储器（16 进制内容） ：300：：：7006 步骤 1：3005－&IR；步骤 2：3－&AC 步骤 3：5940－&IR；步骤 4：3＋2＝5－&AC 步骤 5：7006－&IR：步骤 6：AC－&设备 6 1.2、本章中用 6 步来描述图 1.4 中的程序执行情况，请使用 MAR 和 MBR 扩充这个描述。 答案：1. a. PC 中包含第一条指令的地址 300，该指令的内容被送入 MAR 中。 b. 地址为 300 的指令的内容（值为十六进制数 1940）被送入 MBR，并且 PC 增 1。这两个步骤 是并行完成的。 c. MBR 中的值被送入指令寄存器 IR 中。 2. a. 指令寄存器 IR 中的地址部分（940）被送入 MAR 中。 b. 地址 940 中的值被送入 MBR 中。 c. MBR 中的值被送入 AC 中。 3. a. PC 中的值（301）被送入 MAR 中。 b. 地址为 301 的指令的内容（值为十六进制数 5941）被送入 MBR，并且 PC 增 1。 c. MBR 中的值被送入指令寄存器 IR 中。 4. a. 指令寄存器 IR 中的地址部分（941）被送入 MAR 中。 b. 地址 941 中的值被送入 MBR 中。 c. AC 中以前的内容和地址为 941 的存储单元中的内容相加，结果保存到 AC 中。 5. a. PC 中的值（302）被送入 MAR 中。 b. 地址为 302 的指令的内容（值为十六进制数 2941）被送入 MBR，并且 PC 增 1。 c. MBR 中的值被送入指令寄存器 IR 中。 6. a. 指令寄存器 IR 中的地址部分（941）被送入 MAR 中。 b. AC 中的值被送入 MBR 中。 c. MBR 中的值被存储到地址为 941 的存储单元之中。 1.4、假设有一个微处理器产生一个 16 位的地址（例如，假设程序计数器和地址寄存器都是 16 位）并且具 有一个 16 位的数据总线。 a.如果连接到一个 16 位存储器上，处理器能够直接访问的最大存储器地址空间为多少？ b.如果连接到一个 8 位存储器上，处理器能够直接访问的最大存储器地址空间为多少？ c.处理访问一个独立的 I/O 空间需要哪些结构特征？ d.如果输入指令和输出指令可以表示 8 位 I/O 端口号，这个微处理器可以支持多少 8 位 I/O 端口？ 答案：对于(a)和(b)两种情况，微处理器可以直接访问的最大存储器地址空间为216 = 64K bytes；唯一的区 别是8位存储器每次访问传输1个字节，而16位存储器每次访问可以传输一个字节或者一个16位的 字。对于(c)情况，特殊的输入和输出指令是必要的，这些指令的执行体会产生特殊的“I/O信号” （有别于“存储器信号”，这些信号由存储器类型指令的执行体产生）；在最小状态下，一个附加 的输出针脚将用来传输新的信号。对于(d)情况，它支持28 = 256个输入和28 = 256个输出字节端口和 相同数目的16位I/O端口；在任一情况, 一个输入和一个输出端口之间的区别是通过被执行的输入1 输出指令所产生的不同信号来定义的。 1.5、考虑一个 32 位微处理器，它有一个 16 位外部数据总线，并由一个 8MHz 的输入时钟驱动。假设这个 微处理器有一个总线周期，其最大持续时间等于 4 个输入时钟周期。请问该微处理器可以支持的最大数据 传送速度为多少？外部数据总线增加到 21 位，或者外部时钟频率加倍，哪种措施可以更好地提高处理器 性能？请叙述你的设想并解释原因。 答案：时钟周期＝1/（8MHZ）＝125ns 总线周期＝4×125ns＝500ns 每 500ns 传输 2 比特；因此传输速度＝4MB/s 加倍频率可能意味着采用了新的芯片制造技术（假设每个指令都有相同的时钟周期数） ；加倍外部数 据总线，在芯片数据总线驱动/锁存、总线控制逻辑的修改等方面手段广泛（或许更新） 。在第一种方案中， 内存芯片的速度要提高一倍（大约） ，而不能降低微处理器的速度；第二种方案中，内存的字长必须加倍， 以便能发送/接受 32 位数量。 1.6、考虑一个计算机系统，它包含一个 I/O 模块，用以控制一台简单的键盘/打印机电传打字设备。CPU 中包含下列寄存器，这些寄存器直接连接到系统总线上： INPR：输入寄存器，8 位 OUTR：输出寄存器，8 位 FGI：输入标记，1 位 FGO：输出标记，1 位 IEN：中断允许，1 位 I/O 模块控制从打字机中输入击键，并输出到打印机中去。打字机可以把一个字母数字符号编码成一个 8 位字，也可以把一个 8 位字解码成一个字母数字符号。当 8 位字从打字机进入输入寄存器时，输入标记被 置位；当打印一个字时，输出标记被置位。 a. 描述 CPU 如何使用这 4 个寄存器实现与打字机间的输入/输出。 b. 描述通过使用 IEN，如何提高执行效率？ 答案：a.来源于打字机的输入储存在 INPR 中。只有当 FGI＝0 时，INPR 才会接收来自打字机的数据。当 数据接收后，被储存在 INPR 里面，同时 FGI 置为 1。CPU 定期检查 FGI。如果 FGI＝1，CPU 将把 INPR 里面的内容传送至 AC，并把 FGI 置为 0。 当 CPU 需要传送数据到打字机时，它会检查 FGO。如果 FGO＝0，CPU 处于等待。如果 FGO ＝1，CPU 将把 AC 的内容传送至 OUTER 并把 FGO 置为 0。当数字符号打印后，打字机将把 FGI 置为 1。 b.（A）描述的过程非常浪费。速度远高于打字机的 CPU 必须反复不断的检查 FGI 和 FGO。如果中 断被使用，当打字机准备接收或者发送数据时，可以向 CPU 发出一个中断请求。IEN 计数器可以由 CPU 设置（在程序员的控制下） 。 1.7、实际上在所有包括 DMA 模块的系统中，DMA 访问主存储器的优先级总是高于处理器访问主存储器 的优先级。这是为什么? 答案：如果一个处理器在尝试着读或者写存储器时被挂起, 通常除了一点轻微的时间损耗之外没有任何危 害。但是，DMA可能从或者向设备(例如磁盘或磁带)以数据流的方式接收或者传输数据并且这是不能 被打断的。否则，如果DMA设备被挂起（拒绝继续访问主存），数据可能会丢失。 1.9、一台计算机包括一个 CPU 和一台 I/O 设备 D，通过一条共享总线连接到主存储器 M，数据总线的宽 度为 1 个字。CPU 每秒最多可执行 106 条指令，平均每条指令需要 5 个机器周期，其中 3 个周期需要使用 存储器总线。存储器读/写操作使用 1 个机器周期。假设 CPU 正在连续不断地执行后台程序，并且需要保 证 95%的指令执行速度，但没有任何 I/O 指令。假设 1 个处理器周期等于 1 个总线周期，现在要在 M 和 D 之间传送大块数据。 a.若使用程序控制 I/O， 每传送 1 个字需要 CPU 执行两条指令。 I/O 请估计通过 D 的 I/O 数据传送的最大可 能速度。 b.如果使用 DMA 传送，请估计传送速度。2 答案：a.处理器只能分配 5％的时间给 I/O.所以最大的 I/O 指令传送速度是 10e6×0.05＝50000 条指令/秒。 因此 I/O 的传送速率是 25000 字/秒。 b.使用 DMA 控制时，可用的机器周期下的数量是 10e6（0.05×5＋0.95×2）＝2.15×10e6 如果我们假设 DMA 模块可以使用所有这些周期，并且忽略任何设置和状态检查时间，那么这个值 就是最大的 I/O 传输速率。 1.10、考虑以下代码： for ( i = 0；i & 20；i++) for (j = 0；j & 10；j++) a[i] = a[i]*j a. 请举例说明代码中的空间局部性。 b. 请举例说明代码中的时间局部性。 答案：a.读取第二条指令是紧跟着读取第一条指令的。 b.在很短的间歇时间内， a[i]在循环内部被访问了十次。 1.11、请将附录 1A 中的式（1.1）和式（1.2）推广到 n 级存储器层次中。 答案：定义： Ci = 存储器层次 i 上每一位的存储单元平均花销 Si = 存储器层次 i 的规模大小 Ti = 存储器层次 i 上访问一个字所需时间 Hi = 一个字在不高于层次 i 的存储器上的概率 Bi = 把一个数据块从层次 i+1 的存储器上传输到层次 i 的存储器上所需时间 高速缓冲存储器作为是存储器层次1；主存为存储器层次2；针对所有的N层存储器层以此类推。有：CS ??C Si ?1 n ini?Si ?1iTs的引用更复杂，我们从概率论入手：所期望的值 x ?? i Pr[ x ? 1] ，由此我们可以写出：i ?1nTs ? ? Ti H ii ?1n我们需要清楚如果一个字在M1（缓存）中，那么对它的读取非常快。如果这个字在M2而不在M1中，那么 数据块需要从M2传输到M1中，然后才能读取。因此，T2 = B1+T1 进一步，T3 = B2+T2 = B1+B2+T1 以此类推： Ti ?n?Bj ?1 i ?1 j ?1i ?1j? T1n所以， Ts ?n?i ?2i? ( B j H i ) ? T1 ? H ii ?1但是，?Hi ?1?13 最后， Ts ?? ? (B H ) ? Ti ?2 j ?1 i ini ?111.12、考虑一个存储器系统，它具有以下参数： Tc = 100 ns Cc = 0.01 分/位 Tm = 1200 ns Cm = 0.001 分/位 a.1MB 的主存储器价格为多少？ b.使用高速缓冲存储器技术，1MB 的主存储器价格为多少？ c.如果有效存取时间比高速缓冲存储器存取时间多 10% ，命中率 H 为多少？ 答案：a.价格 = Cm× 106 = 8× 3 ￠ = ＄80 8× 10 6 4 b.价格 = Cc× 10 = 8× 8× 10 ￠ = ＄800 c.由等式 1.1 知：1.1× 1 = T1+(1-H)T2 T (0.1)(100) = (1-H)(1200) H=.13、一台计算机包括包括高速缓冲存储器、主存储器和一个用做虚拟存储器的磁盘。如果要存取的字在 高速缓冲存储器中，存取它需要 20ns；如果该字在主存储器中而不在高速缓冲存储器中，把它载入高速缓 冲存储器需要 60ns（包括最初检查高速缓冲存储器的时间） ，然后再重新开始存取；如果该字不在主存储 器中，从磁盘中取到内存需要 12ms，接着复制到高速缓冲存储器中还需要 60ns，再重新开始存取。高速 缓冲存储器的命中率为 0.9，主存储器的命中率为 0.6，则该系统中存取一个字的平均存取时间是多少（单 位为 ns）？ 答案：有三种情况需要考虑： 字所在的位置 在缓存中 不在缓存，在主存中 不在缓存也不在主存中 概率 0.9 （0.1） （0.6）= 0.06 （0.1） （0.4）= 0.04 访问所需时间（ns） 20 60+20 = 80 12ms+60+20 = 12,000,080所以平均访问时间是：Avg = (0.9)(20) + (0.06)(80) + (0.04)() = 480026 ns 1.14、假设处理器使用一个栈来管理过程调用和返回。请问可以取消程序计数器而用栈指针代替吗？ 答案：如果栈只用于保存返回地址。或者如果栈也用于传递参数，这种方案只有当栈作为传递参数的控制 单元而非机器指令时才成立。这两种情况下可以取消程序计数器而用栈指针代替。在后者情况中， 处理器同时需要一个参数和指向栈顶部的程序计数器。第2章操作系统概述2.1 假设我们有一台多道程序的计算机，每个作业有相同的特征。在一个计算周期 T 中，一个作业有一半 时间花费在 I/O 上， 另一半用于处理器的活动。 每个作业一共运行 N 个周期。 假设使用简单的循环法调度， 并且 I/O 操作可以与处理器操作重叠。定义以下量： ?时间周期=完成任务的实际时间 ?吞吐量=每个时间周期 T 内平均完成的作业数目 ?处理器使用率=处理器活跃（不是处于等待）的时间的百分比 当周期 T 分别按下列方式分布时，对 1 个、2 个和 4 个同时发生的作业，请计算这些量： a. 前一般用于 I/O，后一半用于处理器。 b. 前四分之一和后四分之一用于 I/O，中间部分用于处理器。 答： （a）和（b）的答案相同。尽管处理器活动不能重叠，但 I/O 操作能。 一个作业 时间周期=NT 处理器利用率=50 两个作业 时间周期=NT 处理器利用率=100 四个作业 时间周期=（2N-1）NT 处理器利用率=1004 2.2 I/O 限制的程序是指如果单独运行，则花费在等待 I/O 上的时间比使用处理器的时间要多的程序。处理 器限制的程序则相反。假设短期调度算法偏爱那些在近期石油处理器时间较少的算法，请解释为什么这个 算法偏爱 I/O 限制的程序，但是并不是永远不受理处理器限制程序所需的处理器时间？ 受 I/O 限制的程序使用相对较少的处理器时间，因此更受算法的青睐。然而，受处理器限制的进程如 果在足够长的时间内得不到处理器时间，同一算法将允许处理器去处理此进程，因为它最近没有使用过处 理器。这样，一个处理器限制的进程不会永远得不到处理器。 2.3 请对优化分时系统的调度策略和用于优化多道程序批处理系统的调度策略进行比较。 分时系统关注的是轮转时间，时间限制策略更有效是因为它给所有进程一个较短的处理时间。批处理 系统关心的是吞吐量，更少的上下文转换和更多的进程处理时间。因此，最小的上下文转换最高效。 2.4 系统调用的目的是什么?如何实现与操作系统相关的的系统调用以及与双重模式 （内核模式和用户模式） 操作相关的系统调用？ 系统调用被应用程序用来调用一个由操作系统提供的函数。通常情况下，系统调用最终转换成在内核 模式下的系统程序。 2.5 在 IBM 的主机操作系统 OS/390 中，内核中的一个重要模块是系统资源管理程序（System Resource Manager,SRM） ，他负责地址空间（进程）之间的资源分配。SRM 是的 OS/390 在操作系统中具有特殊性， 没有任何其他的主机操作系统，当然没有任何其他类型的操作系统可以比得上 SRM 所实现的功能。资源 的概念包括处理器、实存和 I/O 通道，SRM 累计处理器、I/O 通道和各种重要数据结构的利用率，它的目 标是基于性能监视和分析提供最优的性能，其安装设置了以后的各种性能目标作为 SRM 的指南，这会基 于系统的利用率动态的修改安装和作业性能特点。 SRM 依次提供报告， 允许受过训练的操作员改进配置和 参数设置，以改善用户服务。 现在关注 SRM 活动的一个实例。实存被划分为成千上万个大小相等的块，称为帧。每个帧可以保留一块 称为页的虚存。SRM 每秒大约接受 20 次控制，并在互相之间以及每个页面之间进行检查。如果页未被引 用或被改变，计数器增 1。一段时间后，SRM 求这些数据的平均值，以确定系统中一个页面未曾被触及的 平均秒数。这样做的目的是什么？SRM 将采取什么动作？ 操作系统可以查看这些数据已确定系统的负荷，通过减少加在系统上的活跃作业来保持较高的平均利用 率。典型的平均时间应该是两分钟以上，这个平均时间看起来很长，其实并不长。第 3 章 进程描述和控制3.1. 给出操作系统进行进程管理时的五种主要活动，并简单描述为什么需要它们。 答：用户进程和系统进程创建及删除。系统中的进程可以为信息共享、运算加速、模块化和方便并 发地执行。而并发执行需要进程的创建和删除机制。当进程创建或者运行时分配给它需要的资源。 当进程终止时，操作系统需要收回任何可以重新利用的资源。 进程的暂停和继续执行。在进程调度中，当进程在等待某些资源时，操作系统需要将它的状态改变 为等待或就绪状态。当所需要的资源可用时，操作系统需要将它的状态变为运行态以使其继续执行。 提供进程的同步机制。合作的进程可能需要共享数据。对共享数据的并行访问可能会导致数据冲突。 操作系统必须提供进程的同步机制以使合作进程有序地执行，从而保证数据的一致性。 提供进程的通信机制。操作系统下执行的进程既可以是独立进程也可以是合作进程。合作进程之间 必须具有一定的方式进行通信。 提供进程的死锁解决机制。在多道程序环境中，多个进程可能会竞争有限的资源。如果发生死锁， 所有的等待进程都将永远不能由等待状态再变为运行态，资源将被浪费，工作永远不能完成。 3.2. 在[PINK89] 中为进程定义了以下状态：执行（运行）态、活跃（就绪）态、阻塞态和挂起态。当进 程正在等待允许使用某一资源时，它处于阻塞态；当进程正在等待它已经获得的某种资源上的操作 完成时，它处于挂起态。在许多操作系统中，这两种状态常常放在一起作为阻塞态，挂起态使用本 章中给出的定义。请比较这两组定义的优点。 答：[PINK89]中引用了以下例子来阐述其中阻塞和挂起的定义： 假设一个进程已经执行了一段时间，它需要一个额外的磁带设备来写出一个临时文件。在它开5 始写磁带之前，进程必须得到使用某一设备的许可。当它做出请求时，磁带设备可能并不可用， 这种情况下，该进程就处于阻塞态。假设操作系统在某一时刻将磁带设备分配给了该进程，这 时进程就重新变为活跃态。当进程重新变为执行态时要对新获得的磁带设备进行写操作。这时 进程变为挂起态，等待该磁带上当前所进行的写操作完成。 这种对等待某一设备的两种不同原因的区别，在操作系统组织其工作时是非常有用的。然而这并不 能表明那些进程是换入的，那些进程是换出的。后一种区别是必需的，而且应该在进程状态中以某 种形式表现出来。 3.3. 对于图 3.9（b）中给出的 7 状态进程模型，请仿照图 3.8（b）画出它的排队图。 答：图 9.3 给出了单个阻塞队列的结果。该图可以很容易的推广到多个阻塞队列的情形。 3.4. 考虑图 3.9（b）中的状态转换图。假设操作系统正在分派进程，有进程处于就绪态和就绪/挂起态，并 且至少有一个处于就绪/挂起态的进程比处于就绪态的所有进程的优先级都高。有两种极端的策略： （1）总是分派一个处于就绪态的进程，以减少交换； （2）总是把机会给具有最高优先级的进程，即 使会导致在不需要交换时进行交换。请给出一种能均衡考虑优先级和性能的中间策略。 答：对于一个就绪/挂起态的进程，降低一定数量（如一或两个）优先级，从而保证只有当一个就绪 /挂起态的进程比就绪态的进程的最高优先级还高出几个优先级时，它才会被选做下一个执行。 3.5. 表 3.13 给出了 VAX/VMS 操作系统的进程状态。 a. 请给出这么多种等待状态的理由。 b. 为什么以下状态没有驻留和换出方案：页错误等待、也冲突等待、公共事件等待、自由页等待和 资源等待。 c. 请画出状态转换图，并指出引发状态装换的原因。 答： a. 每一种等待状态都有一个单独的队列与其相关联。当影响某一等待进程的事件发生时，把等待进 程分成不同的队列就减少了定位这一等待进程所需的工作量。例如，当一个页错误完成时，调 度程序就可以在页错误等待队列中找到等待的进程。 b. 在这些状态下，允许进程被换出只会使效率更低。例如，当发生页错误等待时，进程正在等待换 入一个页从而使其可以执行，这是将进程换出是毫无意义的。 c. 可以由下面的进程状态转换表得到状态转换图。 当前状态 当前正在执 行 当前正在执 行 可计算（驻 留） 可计算（换 出） 各种等待状 态（驻留） 各种等待状 态（换出） 调度 换入 事件发生 事件发生 换出 可计算（驻 留） 重调度 换出 下一状态 可计算（换 出） 各种等待状 态（驻留） 等待 各种等待状 态（换出）3.6. VAM/VMS 操作系统采用了四种处理器访问模式，以促进系统资源在进程间的保护和共享。访问模式 确定： ? 指令执行特权：处理器将执行什么指令。 ? 内存访问特权：当前指令可能访问虚拟内存中的哪个单元。 四种模式如下：6 ? 内核模式：执行 VMS 操作系统的内核，包括内存管理、中断处理和 I/O 操作。 ? 执行模式：执行许多操作系统服务调用，包括文件（磁盘和磁带）和记录管理例程。 ? 管理模式：执行其他操作系统服务，如响应用户命令。 ? 用户模式：执行用户程序和诸如编译器、编辑器、链接程序、调试器之类的实用程序。 在较少特权模式执行的进程通常需要调用在较多特权模式下执行的过程，例如，一个用户程序需要 一个操作系统服务。这个调用通过使用一个改变模式（简称 CHM）指令来实现，该指令将引发一个 中断， 把控制转交给处于新的访问模式下的例程， 并通过执行 REI Return from Exception or Interrupt， （ 从异常或中断返回）指令返回。 a. 很多操作系统有两种模式，内核和用户，那么提供四种模式有什么优点和缺点？ b. 你可以举出一种有四种以上模式的情况吗？ 答： a. 四种模式的优点是对主存的访问控制更加灵活，能够为主存提供更好的保护。缺点是复杂和处理 的开销过大。例如，程序在每一种执行模式下都要有一个独立的堆栈。 b. 原则上，模式越多越灵活，但是四种以上的模式似乎很难实现。 3.7. 在前面习题中讨论的 VMS 方案常常称为环状保护结构，如图 3.18 所示。3.3 节所描述的简单的内核/ 用户方案是一种两环结构，[SILB04]指出了这种方法的问题：环状（层次）结构的主要缺点是它不 允许我们实施须知原理，特别地，如果一个对象必须在域 Dj 中可访问，但在域 Di 中不可访问，则必 须有就 j&i。这意味着在 Di 中可访问的每个段在 Dj 中都可以访问。 a. 请清楚地解释上面引文中提出的问题。 b. 请给出环状结构操作系统解决这个问题的一种方法。 答： a. 当 j&i 时，运行在 Di 中的进程被禁止访问 Dj 中的对象。因此，如果 Dj 中包含的信息比 Di 中的更 具有特权或者要求的安全性更高，那么这种限制就是合理的。然而，通过以下方法却可以绕过 这种安全策略。一个运行在 Dj 中的进程可以读取 Dj 中的数据，然后把数据复制到 Di 中。随后， Di 中的进程就可以访问这些信息了。 b. 有一种解决这一问题的方法叫做可信系统，我们将在 16 章中进行讨论。 3.8. 图 3.7（b）表明一个进程每次只能在一个事件队列中。 a. 是否能够允许进程同时等待一个或多个事件？请举例说明。 b. 在这种情况下，如何修改图中的排队结构以支持这个新特点？ 答： a. 一个进程可能正在处理从另一个进程收到的数据并将结果保存到磁盘上。如果当前在另一个进程 中正有数据在等待被取走，进程就可以继续获得数据并处理它。如果前一个写磁盘操作已经完 成，并且有处理好的数据在等待写出，那么进程就可以继续写磁盘。这样就可能存在某一时刻， 进程即在等待从输入进程获得数据，又在等待磁盘可用。 b. 有很多种方法解决这一问题。可以使用一种特殊的队列，或者将进程放入两个独立的队列中。不 论采用哪种方法，操作系统都必须处理好细节工作，使进程相继地关注两个事件的发生。 3.9. 在很多早期计算机中，中断导致寄存器值被保存在与给定的中断信息相关联的固定单元。在什么情况 下这是一种实用的技术？请解释为什么它通常是不方便的。 答：这种技术是基于被中断的进程 A 在中断响应之后继续执行的假设的。但是，在通常情况下，中 断可能会导致另一个进程 B 抢占了进程 A。这是就必须将进程 A 的执行状态从与中断相关的位置复 制到与 A 相关的进程描述中。然而机器却有可能仍将它们保存到前一位置。参考：[BRIN73]。 3.10. 3.4 节曾经讲述过，由于在内核模式下执行的进程是不能被抢占的，因此 UNIX 不适用于实时应用。 请阐述原因。 答：由于存在进程不能被抢占的情况（如在内核模式下执行的进程） ，操作系统不可能对实时需求给 予迅速的反应。7 第 4 章 线程、对称多处理和微内核4.1. 一个进程中的多个线程有以下两个优点： （1）在一个已有进程中创建一个新线程比创建一个新进程所 需的工作量少； （2）在同一个进程中的线程间的通信比较简单。请问同一个进程中的两个线程间的 模式切换与不同进程中的两个线程间的模式切换相比，所需的工作量是否要少？ 答：是的，因为两个进程间的模式切换要储存更多的状态信息。 4.2. 在比较用户级线程和内核级线程时曾指出用户级线程的一个缺点，即当一个用户级线程执行系统调用 时，不仅这个线程被阻塞，而且进程中的所有线程都被阻塞。请问这是为什么？ 答：因为对于用户级线程来说，一个进程的线程结构对操作系统是不可见的，而操作系统的调度是 以进程为单位的。 4.3. 在 OS/2 中，其他操作系统中通用的进程概念被分成了三个独立类型的实体：会话、进程和线程。一 个会话是一组与用户接口（键盘、显示器、鼠标）相关联的一个或多个进程。会话代表了一个交互 式的用户应用程序，如字处理程序或电子表格，这个概念使得 PC 用户可以打开一个以上的应用程 序，在屏幕上显示一个或更多个窗口。操作系统必须知道哪个窗口，即哪个会话是活跃的，从而把 键盘和鼠标的输入传递个相应的会话。在任何时刻，只有一个会话在前台模式，其他的会话都在后 台模式，键盘和鼠标的所有输入都发送给前台会话的一个进程。当一个会话在前台模式时，执行视 频输出的进程直接把它发送到硬件视频缓冲区。当一个会话在后台时，如果该会话的任何一个进程 的任何一个线程正在执行并产生屏幕输出，则这个输出被送到逻辑视频缓冲区；当这个会话返回前 台时，屏幕被更新，为新的前台会话反映出逻辑视频缓冲区中的当前内容。 有一种方法可以把 OS/2 中与进程相关的概念的数目从 3 个减少到 2 个。删去会话，把用户接口（键 盘、显示器、鼠标）和进程关联起来。这样，在某一时刻，只有一个进程处于前台模式。为了进一 步地进行构造，进程可以被划分成线程。 a. 使用这种方法会丧失什么优点？ b. 如果继续使用这种修改方法，应该在哪里分配资源（存储器、文件等） ：在进程级还是线程级？ 答： a. 会话的使用非常适合个人计算机和工作站对交互式图形接口的需求。它为明确图形输出和键盘/ 鼠标输入应该被关联到什么位置提供了一个统一的机制，减轻了操作系统的工作负担。 b. 应该和其他的进程/线程系统一样，在进程级分配地址空间和文件。 4.4. 考虑这样一个环境，用户级线程和内核级线程呈一对一的映射关系，并且允许进程中的一个或多个线 程产生会引发阻塞的系统调用，而其他线程可以继续运行。解释为什么这个模型可以使多线程程序 比在单处理器机器上的相应的单线程程序运行速度更快？ 答：问题在于机器会花费相当多的时间等待 I/O 操作的完成。在一个多线程程序中，可能一个内核 级线程会产生引发阻塞的系统调用，而其他内核级线程可以继续执行。而在单处理器机器上，进程 则必须阻塞知道所有的系统调用都可以继续运行。参考：[LEWI96] 4.5. 如果一个进程退出时，该进程的某些线程仍在运行，请问他们会继续运行吗？ 答：不会。当一个进程退出时，会带走它的所有东西――内核级线程，进程结构，存储空间――包 括线程。参考：[LEWI96] 4.6. OS/390 主机操作系统围绕着地址空间和任务的概念构造。 粗略说来， 一个地址空间对应于一个应用程 序，并且或多或少地对应于其他操作系统中的一个进程；在一个地址空间中，可以产生一组任务， 并且它们可以并发执行，这大致对应于多线程的概念。管理任务结构有两个主要的数据结构。地址 空间控制块（ASCB）含有 OS/390 所需要的关于一个地址空间的信息，而不论该地址空间是否在执 行。ASCB 中的信息包括分派优先级、分配给该地址空间的实存和虚存、该地址空间中就绪的任务 数以及是否每个都被换出。一个任务控制块（TCB）标识一个正在执行的用户程序，它含有在一个 地址空间中管理该任务所需要的信息，包括处理器状态信息、指向该任务所涉及到的程序的指针和 任务执行结构。ASCB 是在系统存储器中保存的全局结构，而 TCB 是保存在各自的地址空间中的局 部结构。请问把控制信息划分成全局和局部两部分有什么好处？8 答：关于一个地址空间的尽可能多的信息可以随地址空间被换出，从而节约了主存。 4.7. 一个多处理系统有 8 个处理器和 20 个附加磁带设备。现在有大量的作业提交给该系统，完成每个作 业最多需要 4 个磁带设备。假设每个作业开始运行时只需要 3 个磁带设备，并且在很长时间内都只 需要这 3 个设备，而只是在最后很短的一段时间内需要第 4 个设备以完成操作。同时还假设这类作 业源源不断。 a. 假设操作系统中的调度器只有当 4 个磁带设备都可用时才开始一个作业。当作业开始时，4 个设 备立即被分配给它，并且直到作业完成时才被释放。请问一次最多可以同时执行几个作业？采 用这种策略，最多有几个磁带设备可能是空闲的？最少有几个？ b. 给出另外一种策略，要求其可以提高磁带设备的利用率，并且同时可以避免系统死锁。分析最多 可以有几个作业同时执行，可能出现的空闲设备的范围是多少。 答： a. 采用一个保守的策略， 一次最多同时执行 20/4=5 个作业。 由于分配各一个任务的磁带设备最多同 时只有一个空闲，所以在同一时刻最多有 5 个磁带设备可能是空闲的。在最好的情况下没有磁 带设备空闲。 b. 为了更好的利用磁设备， 每个作业在最初只分配三个磁带设备。 第四个只有的需要的时候才分配。 在这种策略中，最多可以有 20/3=6 个作业同时执行。最少的空闲设备数量为 0，最多有 2 个。 参考：Advanced Computer Architectrue,K.Hwang,. 在描述 Solaris 用户级线程状态时，曾表明一个用户级线程可能让位于具有相同优先级的另一个线程。 请问，如果有一个可运行的、具有更高优先级的线程，让位函数是否还会导致让位于具有相同优先 级或更高优先级的线程？ 答：任何一个可能改变线程优先级或者使更高优先级的线程可运行的调用都会引起调度，它会依次 抢占低优先级的活跃线程。所以，永远都不会存在一个可运行的、具有更高优先级的线程。参考： [LEVI96]第5章并发性：互斥和同步5.1 答：b.协同程序 read 读卡片，将字符赋给一个只有一个字大小的缓冲区 rs 然后在赋给 squash 协同程。协 同程序 Read 在每副卡片图像的后面插入一个额外的空白。协同程序 squash 不需要知道任何关于输入的八 十个字符的结构， 它简单的查找成对出现的星号， 然后将更改够的字符串经由只有一个字符大小的缓冲 sp， 传递给协同程序 print。最后协同程序 print 简单的接受到来的字符串，并将他们打印在包含 125 个字符的 行中。 5.2．考虑一个并发程序，它有两个进程 p 和 q，定义如下。A.B.C.D 和 E 是任意的原子语句。假设住程序 执行两个进程的 parbegin Void p() void q() { A; { D; B; E; C; } } 答：ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCE; 5.3 考虑下面的程序 const int n=50; void total() { for(count =1;count &=n;count ++)9 {tally++; } } void main() { tally =0; parbegin(total(),total(); write(tally); } 答：a.随意一看,tally 值的范围好像是落在[50,100]这个区间里,因为当没有互斥时可以从 0 直接增加到 50. 这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得 tally 值还低的 一个最终 tally 值.但是考虑下面由这两进程按交替顺序执行载入,增加,存储的情况,同时变更这个共享变量 的取值: 1.进程 A 载入 tally 值,tally 值加到 1,在此时失去处理器(它已经增加寄存器的值到 1,但是还没有存储 这个值). 2.进程 B 载入 tally 值(仍然是 0),然后运行完成 49 次增加操作,在它已经将 49 这个值存储给共享变 量 tally 后,失去处理器控制权. 3.进程 A 重新获得处理器控制权去完成它的第一次存储操作(用 1 去代替先前的 49 这个 tally 值), 此时被迫立即放弃处理器. 4.进程 B 重新开始,将 1(当前的 tally 值)载入到它自己的寄存器中,但此时被迫放弃处理器(注意这是 B 的最后一次载入). 5.进程 A 被重新安排开始,但这次没有被中断,直到运行完成它剩余的 49 次载入,增加和存储操作,结 果是此时 tally 值已经是 50. 6.进程 B 在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至 2,同时存储这个值做 为这个共享变量的最终结果. 一些认为会出现低于 2 这个值的结果,这种情况不会出现.这样 tally 值的正确范围是[2,100]. b.对一般有 N 个进程的情况下,tally 值的最终范围是[2,N*50],因为对其他所有进程来说,从最初开始 运行到在第五步完成.但最后都被进程 B 破坏掉它们的最终结果. 5.4.忙等待是否总是比阻塞等待效率低（根据处理器的使用时间）？请解释。 答：就一般情况来说是对的,因为忙等待消耗无用的指令周期.然而,有一种特殊情况,当进程执行到程序的某 一点处,在此处要等待直到条件满足,而正好条件已满足,此时忙等待会立即有结果,然而阻塞等待会消耗操 作系统资源在换出与换入进程上. 5.5 考虑下面的程序 boolean blocked[2]; void P(int id) { While (true) { While(turn!=id); { While(blocked[1-!id] /*do nothing*/; Turn = } }10 Void main () { Blocked[0]= Blocked[1]= Turn=0; Parbegin(P(0),P(1)); } 这是【HYMA66】中提出的解决互斥问题的一种方法。请举出证明该方法不正确的一个反例。 答：考虑这种情况:此时 turn=0,进程 P(1)使布尔变量 blocked[1]的值为 true,在这时发现布尔变量 blocked[0] 的值为 false,然后 P(0)会将 true 值赋予 blocked[0] ,此时 turn=0,P(0)进入临界区,P(1)在将 1 赋值给 turn 后,也进入了临界区. 5.6 解决互斥的另一种软件方法是 lamport 的面包店（bakery）算法，之所以起这个名字，是因为它的思想 来自于面包店或其他商店中，每个顾客在到达时都得到一个有编号的票，并按票号依次得到服务，算法如 下： Boolean choosing[n]; Int number[n]; While (true) { Choosing[i]= Number[i]=1+getmax(number[],n)； Choosing[i]= For(int j=0;j&n;j++) { While (choosing[j]) {} While ((number[j]!=0)&&(number[j],j)&(number[i],i) {} } /*critical section*/ Number[i]=0; /*remainder*/; } 数组 choosing 和 number 分别被初始化成 false 和 0， 每个数组的第 i 个元素可以由进程 i 读或写， 但其他进 程只能读。符号（a，b）&（c，d）被定义成 （a，c）或（a=c 且 b&d） A． 用文字描述这个算法。 B． 说明这个算法避免了死锁。 C． 说明它实施了互斥。 答： a.当一个进程希望进入临界区时,它被分配一个票号.分配的票号是通过在目前那些等待进入临界区的进 程所持票号和已经在临界区的进程所持票号比较,所得最大票号再加 1 得到的.有最小票号的进程有最高的 优先级进入临界区.当有多个进程拥有同样的票号时,拥有最小数字号进入临界区.当一个进程退出临界区时, 重新设置它的票号为 0. b.如果每个进程被分配唯一的一个进程号,那么总会有一个唯一的,严格的进程顺序.因此,死锁可以 避免. c.为了说明互斥,我们首先需要证明下面的定理:如果 Pi 在它的临界区,Pk 已经计算出来它的 number[k],并试图进入临界区,此时就有下面的关系式: ( number[i], i ) & ( number[k], k ).为证明定理,定义下11 面一些时间量: Tw1:Pi 最后一次读 choosing[k], 当 j=k,在它的第一次等待时,因此我们在 Tw1 处有 choosing[k] = false. Tw2:Pi 开始它的最后执行, 当 j=k,在它的第二次 while 循环时,因此我们有 Tw1 & Tw2. Tk1:Pk 在开始 repeat 循环时;Tk2:Pk 完成 number[k]的计算; Tk3: Pk 设置 choosing[k]为 false 时.我们有 Tk1&Tk2&Tk3. 因为在 Tw1 处,choosing[k]=false,我们要么有 Tw1&Tk1,要么有 Tk3&Tw1.在第一种情况中,我们有 number[i]&number[k],因为 Pi 在 Pk 之前被分配号码;这个满足定理条件.在第二种情况中,我们有 Tk2 & Tk3 & Tw1 & Tw2,因此有 Tk2&Tw2.这意味着在 Tw2 时,Pi 已经读了当前 number[k]的值.而且,因为 Tw2 是当 j=k 第 二次 while 循环执行发生的时刻,我们有(number[i], i ) & ( number[k], k),这样完成了定理的证明.现在就很容 易说明实施了互斥.假定 Pi 在临界区,Pk 正试图进入临界区.Pk 将不能进入临界区,因为它会发现 number[i] 不等于 0,并且( number[i], i ) & ( number[k], k ). 5.7 当按图 5.2 的形式使用一个专门机器指令提供互斥时， 对进程在允许访问临界区之前必须等待多久没有 控制。设计一个使用 testset 指令的算法，且保证任何一个等待进入临界区的进程在 n-1 个 turn 内进入，n 是要求访问临界区的进程数，turn 是指一个进程离开临界区而另一个进程获准访问这个一个事件。 答：以下的程序由[SILB98]提供： var j: 0..n-1; key: repeat waiting[i] := key := while waiting[i] and key do key := testset(lock); waiting[i] := & critical section & j := i + 1 while (j ≠ i) and (not waiting[j]) do j := j + 1 if j = i then lock := false else waiting := & remainder section & Until 这个算法用最普通的数据结构：var waiting: array [0..n C 1] of boolean Lock：boolean 这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索 waiting 的循环队列 5.8 考虑下面关于信号量的定义： Void semWait(s) { If (s.count&0) { s.count--; } Else { Place this process in s. B } }12 Void semSignal(s) { If (there is at liast one process blocked on semaphore) { Remove a process P from s. Place process P } Else s.count++; } 比较这个定义和图 5.3 中的定义， 注意有这样的一个区别： 在前面的定义中， 信号量永远不会取负值。 当在程序中分别使用这两种定义时， 其效果有什么不同？也就是说， 是否可以在不改变程序意义的前提下， 用一个定义代替另一个？ 答：这两个定义是等价的，在图 5.3 的定义中，当信号量的值为负值时，它的值代表了有多少个进程 在等待；在此题中的定义中，虽然你没有关于这方面的信息，但是这两个版本的函数是一样的。 5.9 可以用二元信号量实现一般信号量。我们使用 semWaitB 操作和 semSignalB 操作以及两个二元信号 量 delay 和 mutex。考虑下面的代码 Void semWait(semaphor s) { semWaitB(mutex); s--; if (s&0) { semSignalB(mutex); semWaitB(delay); } Else Semsignalb(mutex) } Void semSignal(semaphore s); { semWaitB(mutex); s++; if(s&=0) semSignalB(delay); semSignalB(mutex); } 最初。S 被设置成期待的信号量值，每个 semwait 操作将信号量减 1，每个 semsignal 操作将信号量加 1. 二元信号量 mutex 被初始化成 1，确保在更新在更新 s 时保证互斥，二元信号量 delay 被初始化成 0，用 于挂起进程， 上面的程序有一个缺点，证明这个缺点，并提出解决方案。提示：假设两个进程，每个都在 s 初始化 为 0 时调用 semwait（s）,当第一个刚刚执行了 semsignalb（mutex）但还没有执行 semwaitb（delay）， 第二个调用 semwait（s）并到达同一点。现在需要做的就是移动程序的一行. 答：假设两个进程，每个都在 s 被初始化成 0 时调用 semWait（s），当第一个刚执行了 semSignalB （mutex） 但还没有执行 semWaitB （delay） 第二个调用 semWait s） 时， （ 并到达同一点。 因为 s=-2 mutex 没有锁定， 假如有另外两个进程同时成功的调用 semSignal s） 他们接着就会调用 semsignalb （ ， （delay） ，13 但是第二个 semsignalb 没有被定义。 解决方法就是移动 semWait 程序中 end 前的 else 一行到 semSignal 程序中最后一行之前。因此 semWait 中的最后一个 semSignalB(mutex)变成无条件的，semSignal 中的 semSignalb(mutex)变成了有 条件的。 5.10 1978 年，dijkstra 提出了一个推测，即使用有限数目的弱信号量，没有一种解决互斥的方案，使用于 数目未知但有限的进程且可以避免饥饿。1979 年，j.m.morris 提出 了一个使用三个弱信号量的算法，反 驳了这个推测。算法的行为可描述如下，如果一个或多个进程正在 semwait（s）操作上等待，另一个进 程正在执行 semsignal（s），则信号量 s 的值未被修改，一个等待进程被解除阻塞，并且这并不取决于 semwait（s）。除了这三个信号量外，算法使用两个非负整数变量，作为在算法特定区域的进程的计数器。 因此，信号量 A 和 B 被初始化为 1，而信号量 M 和计数器 NA，NM 被初始化成 0.一个试图进入临界区的 进程必须通过两个分别由信号量 A 和 M 表示路障，计数器 NA 和 NM 分别含有准备通过路障 A 以及通过 路障 A 但还没有通过路障 M 的进程数。在协议的第二部分，在 M 上阻塞的 NM 个进程将使用类似于第一 部分的串联技术，依次进入他们的临界区，定义一个算法实现上面的描述。 答：这个程序由[RAYN86]提供： var a, b, m: na, nm: 0 ? +∞; a := 1; b := 1; m := 0; na := 0; nm := 0; semWait(b); na ← na + 1; semSignal(b); semWait(a); nm ← nm + 1; semwait(b); na ← na C 1; if na = 0 then semSignal(b); semSignal(m) else semSignal(b); semSignal(a) semWait(m); nm ← nm C 1; &critical section&; if nm = 0 then semSignal(a) else semSignal(m) 5.11 下面的问题曾被用于一个测试中： 侏罗纪公园有一个恐龙博物馆和一个公园，有 m 个旅客和 n 辆车，每辆车只能容纳一名旅客。旅客在博物 馆逛了一会儿，然后派对乘坐旅客车。当一辆车可用时，它载入一名旅客，然后绕公园行驶任意长的时间。 如果 n 辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那 么这辆车等待。使用信号量同步 m 个旅客进程和 n 个进程。下面的代码框架是在教室的地板上发现的。忽 略语法错误和丢掉的变量声明，请判定它是否正确。注意，p 和 v 分别对应于 semwait 和 semsignal。 Resource Jurassic_Park() Sem car_avail:=0,car_taken:=0,car_fillde:=0.passenger_released:=0 Process passenger(i:=1 to num_passengers) Do true-&nap(int(random(1000*wander_time))) P(car avail);V(car_taken);P(car_filled) P(passenger_released) Od End passenger Process car(j:=1 to num_cars) Do true-&V(car_avail);P(car_taken);V(car_filled) Nap(int(random(1000*ride_time))) V(passenger_released)14 Od End car End Jurassic_Park 答： 这段代码有一个重要问题.在 process car 中的代码 V(passenger_released)能够解除下面一种旅 客的阻塞,被阻塞在 P(passenger_released)的这种旅客不是坐在执行 V()的车里的旅客. 5.12 在图 5.9 和 5.3 的注释中，有一句话是“仅把消费者临界区（由 s 控制）中的控制语句移出还是 不能解决问题，因为这将导致死锁”，请用类似于表 5.3 的表说明。 答： Producer 1 2 3 4 5 6 7 8 9 10 生产者和消费者都被阻塞。 5.13 考虑图 5.10 中定义的无限缓冲区生产者/消费者问题的解决方案。 假设生产者和消费者都以大致 相同的速度运行，运行情况如下： 生产者：semS???semSignal 消费者：semWsemW 生产者通常管理给换成区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个 空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量 的信号量调用，从而产生相当多的开销。 构造一个新程序使得能在这种情况下更加有效。 提示：允许 n 的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生 产者产生新数据。这个方案不需要使用图 5.10 中的局部变量 m。 答： 这个程序来自于[BEN82] prog var n: s: (*binary*) semaphore (:= 1); delay: (*binary*) semaphore (:= 0);
semWaitB(s); n := n + 1; if n=0 then semSignalB(delay); semWaitB(s) SemWaitB(S) n++ If(n==1) (semSignalB(delay)) semSignalB(s) semWaitB(delay) semWaitB(s) n-If(n==0) (semWaitB(delay)) Consumer s 1 0 0 0 1 1 0 n 0 0 1 1 1 1 1 0 delay 0 0 0 1 1 0 0 015 semSignalB(s) begin repeat semWaitB(s); n := n C 1; if n = -1 then begin semSignalB(s); semWaitB(delay); semWaitB(s) semSignalB(s) begin (*main program*) n := 0; consumer parend end. 5.14 考虑图 5.13.如果发生下面的交换，程序的意义是否会发生改变？ a.semWait(e);semWait(s) b.semSignal(s);semSignal(n) c.semWait(n);semWait(s) d.semSignal(s);semSignal(e) 答：只要交换顺序都会导致程序错误。信号量 s 控制进入临界区，你只想让临界区区域包括附加或采取功 能。 5.15 在讨论有限缓冲区（见图 5.12）生产者/消费者问题时，注意我们的定义允许缓冲区中最多有 n-1 个 入口？ a.这是为什么？ b.请修改程序，以不久这种低调？ 答：如果缓冲区可以容纳 n 个入口，问题在于如何从一个满的缓冲区中区分出一个空的缓冲区，考虑一个 有六个位置的缓冲区，且仅有一个入口，如下： A Out in 然后，当一个元素被移出，out=in。现在假设缓冲区仅有一个位置为空： D E A B C In out 这样，out=in+1.但是，当一个元素被添加，in 被加 1 后，out=in，当缓冲区为空时同理。 b．你可以使用一个可以随意增加和减少的辅助的变量，count。16 5.16 这个习题说明了使用信号量协调三类进程。圣诞老人在他北极的商店中睡眠，他只能被一下两种情况 之一唤醒： （1）所有九头驯鹿都从南太平洋的假期回来了，或者（2）某些小孩在制作玩具时遇到了困难。 为了让圣诞老人多睡会， 这些孩子只有在是那个人都遇到困难时才唤醒他。 当三个孩子的问题得到解决时， 其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等 待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦 iuxunlu 必须与其他 unlu 在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。 答：santa:圣诞老人 reindeer:驯鹿 elf:小孩子 sleigh:雪橇 toys:玩具5.17 通过一下步骤说明消息传递和信号量具有同等的功能： a.用信号量实现消息传递。提示：利用一个共享缓冲区保存信箱，每个信箱由一个消息槽数组成的。 b.用消息传递实现信号量。提示：引入一个独立的同步进程。 答：b.这个方法来自于[TANE97].同步进程维护了一个计数器和一个等待进程的清单。进程调用相关用于 向同步进程发送消息的生产者，wait 或 signal，来实现 WAITHUO SIGNAL.然后生产者执行 RECEIVE 来17 接受来自于同步进程的回复。 当消息到达时，同步进程检查计数器看需要的操作是否已经足够，SIGNALs 总是可以完成，但是假如信 号值为 0 时， WAITs 将会被阻塞。 假如操作被允许， 同步进程就发回一个空消息， 因此解除调用者的阻塞。 假如操作是 WAIT 并且信号量的值为 0 时，同步进程进入调用队列，并且不发送回复。结果是执行 WAIT 的进程被阻塞。当 SIGNAL 被执行，同步进程选择一个进程在信号量上阻塞，要不就以先进先出顺序，要 不以其他顺序，并且发送一个回复。跑步条件被允许因为同步进程一次只需要一个。第6章并发性：死锁和饥饿６.１写出图６.１（a）中死锁的四个条件。 解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。占有且等待：没有车可以倒退；在十字路口 的每辆车都要等待直到它前面的象限是空的。非抢占: 没有汽车被允许挤开其他车辆。 循环等待: 每辆 汽车都在等待一个此时已经被其他车占领的十字路口象限。 ６.２按照６.１节中对图６.２中路径的描述，给出对图６.３中６种路径的简单描述。 解：１.Q 获得 B 和Ａ, 然后释放 B 和 A. 当 P 重新开始执行的时候, 它将会能够获得两个资源。 2. Q 获得 B和Ａ， P 执行而且阻塞在对 A的请求上. Q释放 B 和Ａ。当 P 重新开始执行的时候，它将 会能够获得两个资源。 3. Q 获得 B ，然后 P 获得和释放 A. Q 获得Ａ然后释放 B 和 A. 当 P 重新开始行的时候，它将会能够获得 B。 4. P 获得Ａ然后 Q 获得 B. P 释放 A. Q 获得Ａ然后释放 B. P 获得 B 然后释放 B。 5. P 获得，然后释放 A. P 获得 B. Q 执行而且阻塞在对Ｂ的请求上。Ｐ释放Ｂ。当 Q 重新开始执行的 时候，, 它 r1 r2 r3 r4 r1 r2 r3 r4 r1 r2 r3 r4 将会能够 获得两个 资源。 6. P 获得 Ａ而且释 放Ａ然后获得并且释放 B. 当 Q 重新开始实行, 它将会能够获得两个资源。 ６.３图６.３反映的情况不会发生死锁，请证明。 证明：如果 Q 获得 B 和Ａ（在 P之前请求Ａ）, 那么 Q 能使用这些两类资源然后释放他们, 允许Ａ进 行。 如果 P在 Q之前请求Ａ获得Ａ, 然后Q 最多能执行到请求Ａ然后被阻塞。 然而,一旦 P 释放 A ， Q 能进行。 一旦 Q 释放 B, Ａ能进行。 ６.４考虑下面的一个系统，当前不存在未满足的请求。 2 1 0 0r1可用 r2 r3r4当前分配最大需求仍然需求18 0 2 0 2 00 0 0 3 31 0 3 5 32 0 4 4 20 2 6 4 00 7 6 3 61 5 5 5 52 0 6 6 2 a计算每个 进程仍然 可能需要 的资源，并 填入标为“仍然需要”的列中。 b系统当前是处于安全状态还是不安全状态，为什么。 c系统当前是否死锁？为什么？ d哪个进程（如果存在）是死锁的或可能变成死锁的？ e如果Ｐ３的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不 安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可 能变成死锁的？ 解： a. 0 0 0 0 0 7 5 0 6 6 2 2 2 0 0 2 0 3 2 0 b.系统当前处于安全状态， 因为至少有一个进程执行序列， 不会导致死锁， 运行顺序是p1, p4, p5, p2, p3. c.系统当前并没有死锁，因为 P1 进程当前分配与最大需求正好相等，P1 进程可以运行直至结束，接 下来运行其他进程 d.P2,P3,P4,P5 可能死锁 e.不可以，当进程 P1,P4,P5 执行完可用资源为（4，6，9，8） ，P2,P3 将死锁，所以不安全，完全不 可以立即同意系统剩下的全部请求。 ６.５ 请把６.４中的死锁检测算法应用于下面的数据，并给出结果。Available=(2100) 0 0 1 0 Allocation= 2 0 0 1 0 1 2 02 0 0 1 Request= 1 0 1 0 2 1 0 0 解： 1. 2. 3. 4. W = (2 1 Mark P3; Mark P2; Mark P1;0 0) W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0) W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1) no deadlock detected 没有死锁６.６一个假脱机系统包含一个输入进程Ｉ，用户进程进程Ｐ和一个输出进程Ｏ，它们之间用两个缓冲区 连接。进程以相等大小的块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在 磁盘上，并取决于进程的速度。所使用的通信原语确保满足下面的资源约束：i+o? ≤max 其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目， o表示磁盘中的输出块数目。19 I输入 缓冲区P输出 缓冲区o以下是关于进程的知识： １. 只要环境提供数据，进程Ｉ最终把它输入到磁盘上（只要磁盘空间可用）。 ２. 只要磁盘可以得到输入，进程Ｐ最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁 盘空间可用）。 ３. 只要磁盘可以得到输出，进程Ｏ最终消耗掉它。说明这个系统可能死锁。 解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理 数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。 ６.７给出在习题６.６中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程 的要求变化。 解：为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一 个界限。 资源限制现在变成 Ｉ + Ｏ ? ≤max Ｉ≤? max C reso 当0 & reso & max 如果程序 P 正在等候递送输出给磁盘, 程序 O 最后处理所有的早先输出而且产生至少reso页, 然后让 P 继续执行。 因此 P 不会因为 O 而延迟。 如果磁盘充满I/O，Ｉ能被延迟; 但是迟早, 所有的早先的 输入可以被Ｐ处理完，而且对应的输出将会被 O 处理, 因而可以让Ｉ继续执行。 ６.８在ＴＨＥ多道程序设计系统中，一个磁鼓（磁盘的先驱，用做辅存）被划分为输入缓冲区，处理和 输出缓冲区，它们的边界可以移动，这取决于所涉及的进程速度。磁鼓的当前状态可以用以下参数描述： ? max表示磁鼓中的最大页数， i示磁鼓中的输入页数， p示磁鼓中的处理页数， o示磁鼓中的输出页数， reso 出保留的最小页数，resp理保留的最小页数。 解： Ｉ + Ｏ + Ｐ≤? max C Ｉ + Ｏ≤? max C resp Ｉ + Ｐ ≤? max C reso Ｉ ≤? max C (reso + resp) ６．９在ＴＨＥ多道程序设计系统中，一页可以进行下列状态转换： １.空→输入缓冲区（输入生产） ２.输入缓冲区→处理区域（输入消耗） ３.处理区域→输出缓冲区（输出生产） ４.输出缓冲区→空（输出生产） ５.空→处理区域（输出消耗） ６.处理区域→空（过程调用） a根据Ｉ，Ｏ和Ｐ的量定义这些转换的结果。20 b如果维持习题６.６中关于输入进程，用户进程和输出进程的假设，它们中的任何一个转换是否会导致死 锁。 解： 1. i ←? i + 1 2. i←? i C 1; p ←? p + 1 3. p←? p C 1; o←? o + 1 4. o ←? o C 1 5. p←? p + 1 6. p ←? p C 1 b. 结合在对问题 6.7 的解决办法被列出的资源限制, 我们 能总结下列各项: 6. 过程返回能立刻发生因为他们只释放 资源。 5. 程序调用可能用尽磁盘片 (p= max C reso) 导致死锁。 4. 当有输出时输出消耗能立刻发生。 3. 输出生产能暂时被延迟直到所有的早先输出被消耗而且为下一步的输出至少可以产生reso页。 2. 只要有输入，输入消耗能立刻发生。 1. 输入生产被延迟直到所有先前输入和对应的输出已经被消耗。 此时, 当 i= o=0,如果消费进程还没有 占用完磁盘空间 ( p & max C reso)，可以产生输入。 结论: 分配给消费进程的不受控制的存储空间是 唯一可能引发死锁的因素。 ６.１０考虑一个共有１５０个存储器单元的系统，其单元如下分配三个进程： 进程 1 2 3 最大 70 60 60 占用 45 40 15使用银行家算法，以确定同意下面的任何一个请求是否安全。如果安全，说明能保证的终止序列；如果不 安全，给出结果分配简表。 a．第４个进程到达，最多需要６０个存储单元，最初需要２５个单元。 b第４个进程到达，最多需要６０个存储单元，最初需要３５个单元。 解： a.若同意第4个进程请求，则储存器单元共用去25＋15＋40＋45=125个单元，还有25个存储单元，则 可以安全执行全部进程。安全顺序是1－2－3－4 b.若同意第4个进程请求，则还有15个资源可以用，此时处于不安全状态，结果分配见表 进程 最大 占有 需要 空闲 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25 ６.１１评价独家算法在实际应用中是否有用。 解：不切实际的: 不能总是预先知道最大要求, 进程数目和资源数目可能随着时间改变 。大多数的操作 系统忽视死锁。 ６.１２有一个已经实现了的管道算法，使得进程Ｐ０产生的Ｔ类型的数据元素经进程序列Ｐ1Ｐ2?Ｐn-1, 并且按该顺序在元素上操作。 a.定义一个一般的消息缓冲区，包含所有部分消耗的数据元素，并按下面的格式为进程Ｐi(0≤i≤n-1)写 一个算法。 Repeat21 从前驱接收 消耗 给后续发送 Forever 假设Ｐ0收到Ｐn-1发送的空元素。该算法能够使进程直接在缓冲区中保存的消息上操作，而无需复制。 b.说明关于普通的缓冲区进程不会死锁。 解：ar buffer: array 0..max-1 of shared T; available: shared array 0..n-1 of 0.. &Initialization& var K: 1..n-1; region available do begin available(0) := for every k do available (k) := 0; end &Process i& var j: 0..max-1; succ: 0..n-1; begin j := 0; succ := (i+1) repeat region available do await available (i) & 0; region buffer(j) region available do begin available (i) := available(i) C 1; available (succ) := available (succ) + 1; end j := (j+1) forever end b.死锁可以被解决通过 P0 waits for Pn-1 AND P1 waits for P0 AND . . . . . Pn-1 waits for Pn-2 因为 (available (0) = 0) AND (available (1) = 0) AND . . . . . (available (n-1) = 0) 但是如果max & 0,这个条件不成立，因为临界域满足 claim(1)+ claim(2)+ ?+claim(n) & available(1)+available(2)+?+available(n) =max22 ６.１３ a.３个进程共享４个资源单元，一次只能保留或释放一个单元。每个进程最大需要２个单元。 说明不会死锁。 b.Ｎ个进程共享Ｍ个资源单元，一次只能保留或释放一个单元。每个进程最大需要单元数不超过Ｍ，并且 所有最大需求的总和小于Ｍ+Ｎ。说明不会发生死锁。 解：a.说明由于每个进程最多需要 2 个资源，最坏情况下，每个进程需要获得一个，系统还剩 1 个，这一 个资源，无论分给谁都能完成。完成进程释放资源后，使剩余进程也完成，故系统不会死锁。 b.假定每个进程最多申请 X 个资源， 最坏情况下， 每个进程都得到 X-1 个资源都在申请最后一个资源， 这时系统剩余资源数量为 M-N(X－1)，只要系统还有一个剩余资源，就可以使其中的一个进程获得所需要 的全部资源， 该进程运行结束以后释放资源， 就可以使其他进程得到全部资源的 满足， 因此， M-N(X-1)》 当 1 时系统不会发生死锁，解这个不等式 X《（M+N-1）,系统不会发生死锁，因此，当所有进程的需求总和 小于 M+N 时，系统是不会发生死锁的。 ６.１４考虑一个由四个进程和一个单独资源组成的系统，当前的声明和分配矩阵是 3 1 2 1 C = 9 A= 3 7 2 对于安全状态，需要的最小资源数目是多少？ 解：最小资源数是３个，总共有１０个资源。Ｐ２获得一个资源，完成后释放两个资源，Ｐ１获得三 个资源，完成后释放三个资源，接下来Ｐ４获得五个资源，释放完资源后，Ｐ３获得所需的６个资源后完 成。 ６.１５考虑下列处理死锁的方法：1 银行家算法，2 死锁检测并杀死线程，释放所有资源，３事先保 留所有资源，４如果线程需要等待，５资源排序，６重新执行检测死锁并退回线程的动作。 评价解释死锁的不同方法使用的一个标准是，哪种方法允许最大的并发。换言之，在没有死锁时，哪 种方法允许最多数目的线程无需要等待继续前进？对下面列出的６种处理死锁的方法，给出从１到６的一 个排序（１表示最大程序的并发），并解释你的排序。 另一个标准是效率；哪种方法需要最小的处理器开销？假设死锁很少发生，给出各种方法从１到６的 一个排序（１表示最有效），并解释这样排序的原因。如果死锁发生很频繁，你的顺序需要改变吗？ 解：a从最多并发事件到最少, 有一个大概的次序如下： 1. 死锁检测并杀死线程，释放所有资源 发现死锁并退回线程的动作， 如果线程需要等候那么重新开始线程而且释放所有的资源， 在死锁发生之前， 这些运算法则都不会限制并发, 因为他们仰赖运行时间检查而并非静态的限制。 他们的效果在死锁被发 现比较难以描述：他们仍然允许许多并发(在一些情形，他们增加它), 但是很难有准确的估计。 第三个 运算法则是最奇怪的, 因为如此后许多的它的并发将会是无用的重复; 因为线程竞争执行时间, 这一个 运算法则也影响运行速度。 因此在两者的极端,它以这顺序被列出两次。 2. 银行家的运算法则 资源排序 这些运算法则因为限制多种的可允许的计算，而相对早先两种法则会引起更多的不必要的等候。 银行家 的运算法则避免不安全的配置 和资源排序限制配置序列以便线程在他们是否一定等候的时候有较少的选 择。 3. 事先保留所有的资源 这一个运算法则相比前两个要允许更少的并发, 但是比最坏的那一种有更少的缺点。因为要预先保留所有 的资源,线程必须等候比较长的而且当他们工作的时候更有可能阻塞其他的线程,因此系统上来说具有更 多的线性。 4. 如果线程需要等待，则重新启动线程并且释放所有的资源23 如上所述, 这一个运算法则在区别最多和最少并发上有疑问,这具体要看并发的定义。 b从最高效率到最低，有如下大概的一个顺序： 1. 预先保留所有的资源 资源排序 因为他们没有包括运行时间经常开支，所以这些运算法则最有效率。 注意这是在相同的静态限制下的结果。 2. 银行家的运算法则 发现死锁而且杀死线程,释放它的资源 这些运算法则在概略的配置上包括运行时间检查 ; 银行家的运算法则运行搜寻查证复杂度在线程和配置的数字和死锁检测中是 O(n m)，死锁检测的复杂 度是 O(n)。资源-从属链被线程数目，资源数目和分配数目限制。 3. 发现死锁并退回线程的动作 这一个运算法则运行也需要运行上述的相同的时间检查。 在写内存上的复杂度为O(n) 。 4. 如果线程需要等待，则重新启动线程并释放所有的资源 这一个运算法则是非常无效率，有如下两个理由。 首先, 因为线程有重新开始的危险, 他们完成的可能 性低。其次，他们与其他重新开始线程竞争有限的执行时间, 因此整个系统运行的速度很慢。 ６.１６评价下面给出的就餐问题的解决方案。一位饥饿的哲学家首先拿起他左边的叉子，如果他右边的 叉子也是可用的，则拿起右边的叉子开始吃饭，否则他放下左边的叉子，并重复这个循环。 解： 如果哲学家们步调完全一致地拿起左边叉子又放下的话， 他们会重复这一过程， 导致饥饿情况的出现。 ６.１７假设有两种类型的哲学家。一类总是先拿起左边的叉子（左撇子），另一类总是先拿起右边的叉 子（右撇子）。左撇子的行为和图６.１２中定义的一致。右撇子的行为如下： wait(fork[(i+1)mod5]); wait(fork[i]); signal(fork[i]); signal(fork[(i+1)mod5]); 证明：a 如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁。 b如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿。 解：a假设存在死锁情况，设有 D个哲学家，他们每人都有一支叉子而且另一支叉子被邻居占有。不失一 般性，设Pj 是一个左撇子。 Pj 抓牢他的左边叉子而且没有他的右边叉子, 他的右边邻居 Pk 没有完成 就餐因此也是一个左撇子。 因此依次推理下去所有这Ｄ个哲学家都是左撇子。这与既有左撇子又有右撇 子的条件矛盾，假设不成立，不存在死锁。 b 假设左撇子 Pj 饥饿，也就是说，有一部分人在就餐而Pj从不吃。 假如 Pj 没有叉子。 这样 Pj 的左边 邻居 Pi 一定持续地占有叉子而始终不吃完。 因此Pi 是 右撇子， 抓住他的右边叉子, 但是从不得到他的左边叉子来完成就餐,也就是说 Pi 也饥饿。 现在 Pi 左边邻居也一定是持续占有右边叉子的右撇子。 向左进行这样的推理，得出所有哲学 家都是饥饿的右撇子，这同Pj是个左撇子矛盾。因此 Pj 一直拥有左边子而且在等待他的右边叉子,Pj 的 右边邻居 Pk 一直举着他的左边叉子而且从不完成一餐,也就是, Pk 是也饥饿的左撇子。 如果 Pk 不是24 一直拿着他的左边叉子， Pj 就可以就餐;因此 Pk 拿着他的左边叉子。向右推理可得所有哲学家都是饥 饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。 ６.１８图１.１７显示了另外一个使用管程解决哲学家就餐问题的方法。和图６.１４比较并阐述你的结 论。 解：图６.１４是等待可用的叉子，图６.１７是等待邻居吃完，在本质上逻辑是一样的，后者显得更加紧 凑。monitor dining_ 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]= /*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]= /*proceed if neither neighbor is eating*/ } void release_fork(int pid) { state[pid]= /*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] csignal(needFork[pid-1]); } void philosopher[k=0 to 4] /*the five philosopher clients*/ { while(true) { &think&; get_forks(k); /*client requests two forks via monitor*/ &eat spaghetti&; release_forks(k); /*client releases forks via the monitor*/ } }25 ６.１９在表６.１３中，Linux的一些原子操作不会涉及到对同一变量的两次访问。比如 atomic_read(atomic_t *v).简单的读操作在任何体系结构中都是原子的。为什么该操作增加到了原子操 作的指令表？ 解：原子操作是在原子数据类型上操作, 原子数据类型有他们自己的内在的 格式。 因此，不能用简单的阅读操作, 但是特别的阅读操作 对于原子数据类型来说是不可或缺的。 ６.２０考虑Linux系统中的如下代码片断： read_lock(&mr_rwlock); write_lock(&mr_rwlock); mr_rwlock是读者写者锁。这段代码的作用是什么？ 解：因为写者锁将会自旋，所以这段代码会导致死锁, 等待所有的 读者解锁, 包括唤醒这个线程。 ６.２１两个变量a和b分别有初始值１和２，对于Linux系统有如下代码： 线程 1 a = 3； mb( )； --线程 2 --c = b； rmb()； d = a；使用内在屏障是为了避免什么错误？ 解：没有使用内存屏障, 在一些处理器上可能 c接到b 的新值, 而d接到b 的旧值。 举例来说, c可以等 于 4(我们期待的), 然而 d 可能等于 1.(不是我们期待的)。 使用mb() 确保a 和 b 按合适的次序被写, 使用 rmb()确保 c 和d 按合适的次序被读。第 7 章 内存管理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。从平均意义上讲，平26 均查找长度是 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.d. 40M,20M,10M,的起始地址是 80M,230M,360M.7.7. 使用伙伴系统分配一个 1MB 的存储块。 a. 利用类似于图 7.6 的图来说明按下列顺序请求和返回的结果：请求 70；请求 35；请求 80；返回 A；请求 60；返回 B；返回 D；返回 C。 b. 给出返回 B 之后的二叉树表示。 答： a.27 b.7.8.考虑一个伙伴系统，在当前分配下的一个特定块地址为. a. 如果块大小为4，它的伙伴的二进制地址为多少？ b. 如果块大小为16，它的伙伴的二进制地址为多少？ 答： a.
k 7.9. 令 buddyk(x)为大小为 2 、地址为 x 的块的伙伴的地址，写出 buddyk(x)的通用表达式。 答：7.10. Fabonacci 序列定义如下： F0=0,F1=1,Fn+2=Fn+1+Fn,nR0 a. 这个序列可以用于建立伙伴系统吗？ b. 该伙伴系统与本章介绍的二叉伙伴系统相比，有什么优点？ 答： a. 是。字区大小可以确定 Fn = Fn-1 + Fn-2.。 b. 这种策略能够比二叉伙伴系统提供更多不同大小的块，因而具有减少内部碎片的可能性。但由于 创建了许多没用的小块，会造成更多的外部碎片。28 7.11. 在程序执行期间，每次取指令后处理器把指令寄存器的内容（程序计数器）增加一个字，但如果遇 到会导致在程序中其他地址继续执行的转跳或调用指令，处理器将修改这个寄存器的内容。现在考 虑图 7.8。关于指令地址有两种选择： ? 在指令寄存器中保存相对地址，并把指令寄存器作为输入进行动态地址转换。当遇到一次成功的 转跳或调用时，由这个转跳或调用产生的相对地址被装入到指令寄存器中。 ? 在指令寄存器中保存绝对地址。当遇到一次成功的转跳或调用时，采用动态地址转换，其结果保 存到指令寄存器中。 哪种方法更好？ 答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。因此，在指 令寄存器中保存相对地址似乎就更好一些。也可以选择在进程被换出主存时将指令寄存器中的地址 转换为相对地址。 32 10 16 7.12. 考虑一个简单分页系统，其物理存储器大小为 2 字节，页大小为 2 字节，逻辑地址空间为 2 个页。 a. 逻辑地址空间包含多少位？ b. 一个帧中包含多少字节？ c. 在物理地址中指定帧需要多少位？ d. 在页表中包含多少个页表项？ e. 在每个页表项中包含多少位？（假设每个页表项中包含一个有效/无效位） 答： 16 10 26 a. 物理地址空间的比特数是 2 *2 =2 10 b. 一个帧包含的字节跟一个页是一样的,2 比特. 32 10 22 c. 主存中帧的数量是 2 /2 =2 ,所以每个帧的定位要 22 个比特 16 d. 在物理地址空间,每个页都有一个页表项,所以有 2 项 e. 加上有效/无效位，每个页表项包含 23 位。 7.13. 分页系统中的虚地址 a 相当于一对（p，w） ，其中 p 是页号，w 是页中的字节号。令 z 是一页中的字 节总数，请给出 p 和 w 关于 z 和 a 的函数。 答：关系是：a = pz + w，其中 p = Na/z?, a/z 的整数部分。w = Rz(a) ，a 除以 z 的余数 7.14. 在一个简单分段系统中，包含如下段表： 起始地址 660
长度（字节） 248 442 198 604对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生： a. 0，198 b. 2，256 c. 1，530 d. 3，444 e. 0，222 答： a. 段 0 定位在 660,所以我们有物理地址 660+190=858. b. 222+156=378 c. 段 1 长度为 422,所以会发生错误 d. 996+444=1440 e. 660+222=882. 7.15. 在内存中，存在连续的段 S1,S2,?，Sn 按其创建顺序一次从一端放置到另一端，如下图所示： 当段 Sn+1 被创建时，尽管 S1,S2,?，Sn 中的某些段可能已经被删除，段 Sn+1 仍被立即放置在段 Sn 之后。29 当段（正在使用或已被删除）和洞之间的边界到达内存的另一端时，压缩正在使用的段。 a. 说明花费在压缩上的时间 F 遵循以下的不等式： FR(1-f)/1+kf), k=t/2s-1 其中，s 表示段的平均长度（以字为单位） 标识段的平均生命周期，按存储器访问；f 表示在 ；l 平衡条件下，未使用的内存部分。提示：计算边界在内存中移动的平均速度，并假设复制一个字 至少需要两次存储器访问。 b. 当 f=0.2，t=1000，s=50 时，计算 F。 答： a. 很明显,在一个周期 t 内一些段会产生而一些段会被删除.因为系统是公平的,一个新的段会在 t 内被插入,此外,边界会医 s/t 的速度移动.假设 t0 是边界到达空洞的时间,t0=fmr/s, m=内存的长 度,在对段进行压缩时会有(1-f)m 个数被移动,压缩时间 至少是 2(1-f)m.则花在压缩上的时间 F 为 F=1-t0/(t0+tc)。 b. K=(t/2s)-1=9;FR(1-0.2)/(1+1.8)=0.29第8章虚拟内存8.1 假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从 0 开始记数的，并且所有的地址都是内存字节地址。页尺寸为 1024 个字节。 虚拟页号 有效位 访问位 修改位 页帧号 0 1 1 0 4 1 1 1 1 7 2 0 0 0 ― 3 1 0 0 2 4 0 0 0 ― 5 1 0 1 0 a． 描述 CPU 产生的虚拟地址通常是如何转化成一个物理主存地址的。 b．下列虚拟地址对应于哪个物理地址（不用考略页错误）？ （i）1052 （ii）2221 （iii）5499 解答 a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到 物理地址 b:(i) 查表对应的页帧号是 7，因此物理地址为 7*6 (ii)4+173 此时出现页错误 (iii)4+379 对应的页帧号为 0 因此物理地址是 379 8.2 考虑一个使用 32 位的地址和 1KB 大小的页的分页虚拟内存系统。 每个页表项需要 32 位。 需要限制页表的大小为一个页。 a．页表一共需要使用几级？ b．每一级页表的大小是多少？提示：一个页表的大小比较小。 c．在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页？ 解答 a：虚拟内存可以分为 232/210= 222 页，所以需要 22 个 bit 来区别虚拟内存中的一页，每一个 页表可以包含 210/4=28 项，因此每个页表可以包含 22bit 中的 8 个 bit，所以需要三级索引。 b：第二级页表有 28 个页表项，第一级页表有 26 个页表项。30 c：如果顶层有 26 个页表项将会减少使用空间，在这种情况下，中间层页表有 26 个并且每个 都有 28 个页表项，底层有 214 个页并且每个都有 28 个页表项，因此共有 1+26+214 页=16,449 页。如果中间层有 26 个页表项，那么总的页数有 1+28+214 页=16,641 页。如果底层有 26 个 页表项，那么总的页表数是 1+28+216 页=65,973 页。 8.3 a：图 8.4 中的用户表需要多少内存空间？ b：假设需要设计一个哈希反向页表来实现与图 8.4 中相同的寻址机制，使用一个哈希函 数来将 20 位页号映射到 6 位哈希表。表项包含页号帧号和链指针。如果页表可以给每个哈 希表项分配最多 3 个溢出项的空间，则哈希反向页表需要占用多大的内存空间？ 解答 a：4Mbyte b：行数：26+2=128 项。每项包含：20（页号）+20（帧号）+8bits（链索引）=48bits=6bytes。 总共：128*6=768bytes 8.4 一个进程分配给 4 个页帧 （下面的所有数字均为十进制数， 每一项都是从 0 开始计数的） 。 上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页 号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之 间的时钟时间，而不是从事件发生到当前的时钟值） 。 虚拟页号 页帧 加载时间 访问时间 R位 M位 2 0 60 161 0 1 1 1 130 160 1 0 0 2 26 162 1 0 3 3 20 163 1 1 当虚拟页 4 发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。 a.FIFO（先进先出）算法 b.LRU（最近最少使用）算法 c.Clock 算法 d.最佳（使用下面的访问串）算法 e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列： 4,0,0,2,4,2,1,0,3,2 如果使用窗口大小为 4 的工作集策略来代替固定分配， 会发生多少页错误？每个页错误何时 发生？ 解答 a:页帧 3，在时间 20 加载，时间最长。 b:页帧 1，在时间 160 访问距现在时间最长。 c:清除页帧 3 的 R 位（最早加载） ，清除页帧 2 的 R 位， （次最早加载） ，换出的是页帧 0 因为 它的 R 位为 0。 d:换出的是页帧 3 中的虚拟页 3，因为它将最晚被访问到。 e:一共有 6 个错误，如下8.5 一个进程访问 5 页：A,B,C,D 和 E，访问顺序如下： A;B;C;D;A;B;E;A;B;C;D;E 假设置换算法为先进后出，该进程在主存中有三个页帧，开始时为空，请查找在这个访问顺31 序中传送的页号。对于 4 个页帧的情况，请重复上面的过程。 解答 分别有 9 次和 10 次页错误，这被称之为“Belady′s 现象” （&An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine,& by Belady et al, Communications of the ACM, June 1969.） 8.6 一个进程在磁盘上包含 8 个虚拟页，在主存中固定分配给 4 个页帧。发生如下顺序的页 访问： 1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3 a.如果使用 LRU 替换策略，给出相继驻留在这 4 个页帧中的页。计算主存的命中率。假设这 些帧最初是空的。 b.如果使用 FIFO 策略，重复问题（a） 。 c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用 FIFO 的效率接近于 LRU。 解答 a:LRU：命中率=16/33b:FIFO：命中率=16/33c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。 8.7 在 VAX 中，用户页表以系统空间的虚拟地址进行定位。让用户页表位于虚存而不是主存 中有什么好处？有什么缺点？ 解答 最主要的优点是在物理内存空间上的节省。这主要是两方面的原因： （1）一个用户页表可以 仅当使用时才取入内存。 （2）操作系统可以动态的分配用户页表，产生一个页表仅当程序被 创建时。 当然，也有一个缺点：地址转换需要多余的工作。 8.8 假设在主存中执行下列程序语句： for(i=1;i≤n;i++) a[i]=b[i]+c[i]; 页尺寸为 1000 个字。令 n=1000。使用一台具有所有寄存器指令并使用了索引寄存器的机器， 写出实现上述语句的一个假想程序，然后给出在执行过程中的页访问顺序。 解答 由机器语言编写的程序，在主存中地址 4000 处开始运行。运行情况如下： 4000 （R1）←1 建立索引记录 i 4001 （R1）←n 在 R2 中建立 n 4002 比较 R2，R1 检查 in 4003 如果大于则跳转到
（R3）←B（R1） 使用索引记录 R1 到达 B[i]32 4005 （R3）←（R3）+C（R1）使用索引记录 R1 加上 C[i] 4006 A（R1）←（R3）使用索引记录 R1 将总和存入 A[i]中 4007 （R1）←（R1）+1 i 加一 4008 跳到 ―6999 存储 A
存储 C 9000 存储 1 9001 存储 n 由这个循环产生的参考串为 ）1000 包括 11.000 个参考，但仅包括 5 个不寻常的页 8.9 IBM System/370 体系结构使用两级存储器结构， 并且分别把这两级称为段和页， 这里的分 段方法缺少本章所描述的关于段的许多特征。对于这个基本的 370 体系结构，页尺寸可以是 2KB 或 4KB，段大小固定为 64KB 或 1MB。这种方案缺少一般分段系统的那些优点？370 的 分段方法有什么好处？ 解答 S/370 分段系统是固定的且对程序员是不可见的， 因此没有一个分段系统的优点在 S/370 中实 现（无保护情况下）每一个段表项的 P 位提供整个段表的保护。 8.10 假设页尺寸为 4KB，页表项大小位 4 字节。如果要映射一个 64 位地址空间，并且最顶 层的页表对应于一页，则需要几级页表？ 解答 因为每个页表项有 4bytes，每个页表有 4Kbytes，所以每个页表可以映射
个页，标识 出 210×212=222bytes 的地址空间。然而，地址空间是 264bytes。增加一个二层页表，顶层页 表指向 210 个页表，标识出 232 个页表，将这个过程继续下去就得到： 深度 地址空间 1 222bytes 2 232bytes 3 242bytes 4 252bytes 5 262bytes 6 272bytes（264bytes） 我们可以看到 5 层是不够表示 64 位的地址空间，但是 6 层达到了要求。但是 6 层中只有 2 位 被使用，而不是全部的 10 位。所以不是使用 72 位的虚拟地址空间，而是将除了最低两位外 的其他位全部屏蔽忽略。这样将会得到一个 64 位地址空间，顶层页只有 4 个页表项。另外一 种方法是修改规则将顶层页做成一个单独的物理页并且让它适合 4 个页。这样将会节省一个 页。 8.11 考虑一个系统该系统采用基于页的内存映射， 并使用一级页表。 假设页表总是在主存中。 a.如果一次存储器访问需要 200ns，那么一次需要调页的存储器访问要多长时间？ b.现在增加一个 MMU，在命中或未命中时有 20ns 的开销。如果假设有 85%的存储器访问命 中都在 MMU TLB 中，那么哪些是有效的存储器访问时间？ c.解释 TLB 命中率如何影响有效的存储器访问时间。 解答 a.400ns。200ns 用来得到页表项，200ns 用来到达存储位置 b.这是一个常见的有效时间计算公式： （220×0.85）+（420×0.15）=25033 两种情况：第一种，TLB 中包含所需的页表项。在这种情况下在 200ns 外多了 20ns 的存储 访问时间。第二种，TLB 中不包含所需的页表项。这时我们会再多花 200ns 来把所需的页表 项取入 TLB。 c.TLB 命中率越高有效存储器访问时间就越短，因为额外的 200ns 来得到页表项的时间被节 省了。 8.12 考虑一个进程的页访问序列，工作集为 M 帧，最初都是空的。页访问串的长度为 P，包 含 N 个不同的页号。对任何一种页替换算法， a.页错误次数的下限是多少？ b.页错误次数的上限是多少？ 解答 a.N b.P 8.13 在论述一种页替换算法时，一位作者用一个在循环轨道上来回移动的雪犁机来模拟说 明：雪均匀地落在轨道上，雪犁机一恒定的速度在轨道上不断的循环，轨道上被扫落的雪从 系统}
我要回帖
更多关于 特种设备作业人员证r3 的文章
更多推荐
- ·高考要求口语的专业口语考什么？
- ·福建南平八中是怎样的学校第四届学生会主席选举
- ·框架每平米建筑面积填充1立方砌块砌墙多少平方多少方？
- ·对于大学文科生有什么专业毕业生找工作难的问题，北京积云教育的新媒体影视课程如何？
- ·景德镇陶瓷市场哪个好大学的定制公交车现在还有吗？
- ·小米5小米8内核调校校如何使用
- ·〖很轻狠快〗小米 年轻人的第一5和乐视pro3如何选择
- ·又看到了惠普笔记本6510b这笔记本，现在才知道是集显的笔记本，这笔记本能换显卡的吗？
- ·华为p20的安全性网盘安全性
- ·MCU引脚输出模式中推挽输出与开漏输出和推挽输出电路原理区别
- ·我吹空调吹的感冒鼻子不透气气，怎么办
- ·荣耀畅玩6a16g7手机3g+16g多少钱
- ·成趣教育是什么学校养成教育内容呀？
- ·做好高层楼宇消防安全评估机构管理工作的几点看法
- ·华南地区北方常见乔木的乔木有哪些
- ·Linux安装软件正版化工作总结总结
- ·浅谈班主任如何对孩子进行孩子的心理疏导导
- ·告诉你，如何远离负面情绪远离幸福感以及获得幸
- ·“互联网+苗木花卉产业发展意见产业” 到底如何“+”
- ·人生必管理者具备的三种技能重要的能力，你具备吗
- ·r3系统删除工号提示人员计数器号已被计数是什么意思
- ·当用两个大小相等的共点力力F作用于两质量相等的小球时，问之后两球的位置
- ·Our presents are there are still manymany.这句话对吗？
- ·如何对付吃不着的葡萄是酸的葡萄说葡萄酸的人
- ·关于字母的脑筋急转弯弯三分钟周游全国打二个字
- ·政府在职人员在外开办无证开办补习班补习班上哪举报
- ·有人跟我说存一万一天50网安可信存证云吗
- ·霸气侧漏的头像女生动物
- ·浙江杭州2018届高考体育培训生什么原因不能确认
- ·成趣学校管理软件怎么样呀？
- ·求《我能治什么病好他的病》这本书的百度云资源
- ·QQqq被冻结多次申诉失败视频
- ·进出口仓库管理配送员进出货买电脑怎么挑
- ·粪敬严什么意思
- ·根据“面红耳赤，心悦诚服造句，波澜起伏”这三个词语进行合理想象，写一篇记叙文。要求：用上这三个词语（出
