《操作系统精髓与设计原理・第五版》习题答案

1第1章计算机系统概述1.1、图1.3中的理想机器还有两条I/O指令：0011=从I/O中载入AC0111=把AC保存到I/O中在这种情况下，12位地址标识一个特殊的外部设备。请给出以下程序的执行过程（按照图1.4的格式）：1.从设备5中载入AC。2.加上存储器单元940的内容。3.把AC保存到设备6中。假设从设备5中取到的下一个值为3940单元中的值为2。答案：存储器（16进制内容）：300：3005；301：5940；302：7006步骤1：3005－IR；步骤2：3－AC步骤3：5940－IR；步骤4：3＋2＝5－AC步骤5：7006－IR：步骤6：AC－设备61.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=64Kbytes；唯一的区别是8位存储器每次访问传输1个字节，而16位存储器每次访问可以传输一个字节或者一个16位的字。对于(c)情况，特殊的输入和输出指令是必要的，这些指令的执行体会产生特殊的“I/O信号”（有别于“存储器信号”，这些信号由存储器类型指令的执行体产生）；在最小状态下，一个附加的输出针脚将用来传输新的信号。对于(d)情况，它支持28=256个输入和28=256个输出字节端口和相同数目的16位I/O端口；在任一情况,一个输入和一个输出端口之间的区别是通过被执行的输入输出2指令所产生的不同信号来定义的。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，I/O每传送1个字需要CPU执行两条指令。请估计通过D的I/O数据传送的最大可能速度。b.如果使用DMA传送，请估计传送速度。3答案：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；i20；i++)for(j=0；j10；j++)a[i]=a[i]*ja.请举例说明代码中的空间局部性。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层存储器层以此类推。有：11niiiSniiCSCSTs的引用更复杂，我们从概率论入手：所期望的值1Pr[1]nixix，由此我们可以写出：1nsiiiTTH我们需要清楚如果一个字在M1（缓存）中，那么对它的读取非常快。如果这个字在M2而不在M1中，那么数据块需要从M2传输到M1中，然后才能读取。因此，T2=B1+T1进一步，T3=B2+T2=B1+B2+T1以此类推：111iijjTBT所以，11211()ninsjiiijiTBHTH但是，11niiH4最后，1121()nisiiijTBHT1.12、考虑一个存储器系统，它具有以下参数：Tc=100nsCc=0.01分/位Tm=1200nsCm=0.001分/位a.1MB的主存储器价格为多少？b.使用高速缓冲存储器技术，1MB的主存储器价格为多少？c.如果有效存取时间比高速缓冲存储器存取时间多10%，命中率H为多少？答案：a.价格=Cm×8×106=8×103￠=＄80b.价格=Cc×8×106=8×104￠=＄800c.由等式1.1知：1.1×T1=T1+(1-H)T2(0.1)(100)=(1-H)(1200)H=1190/12001.13、一台计算机包括包括高速缓冲存储器、主存储器和一个用做虚拟存储器的磁盘。如果要存取的字在高速缓冲存储器中，存取它需要20ns；如果该字在主存储器中而不在高速缓冲存储器中，把它载入高速缓冲存储器需要60ns（包括最初检查高速缓冲存储器的时间），然后再重新开始存取；如果该字不在主存储器中，从磁盘中取到内存需要12ms，接着复制到高速缓冲存储器中还需要60ns，再重新开始存取。高速缓冲存储器的命中率为0.9，主存储器的命中率为0.6，则该系统中存取一个字的平均存取时间是多少（单位为ns）？答案：有三种情况需要考虑：字所在的位置概率访问所需时间（ns）在缓存中0.920不在缓存，在主存中（0.1）（0.6）=0.0660+20=80不在缓存也不在主存中（0.1）（0.4）=0.0412ms+60+20=12,000,080所以平均访问时间是：Avg=(0.9)(20)+(0.06)(80)+(0.04)(12000080)=480026ns1.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处理器利用率=100﹪52.2I/O限制的程序是指如果单独运行，则花费在等待I/O上的时间比使用处理器的时间要多的程序。处理器限制的程序则相反。假设短期调度算法偏爱那些在近期石油处理器时间较少的算法，请解释为什么这个算法偏爱I/O限制的程序，但是并不是永远不受理处理器限制程序所需的处理器时间？受I/O限制的程序使用相对较少的处理器时间