操作系统 习题与答案

1、高等计算机系统结构习题计算机系 CAD所 王晓娟 0080451 解释存储器有关概念和术语：1）：虚拟地址空间虚地址是在编译过程中由处理机生成的，在UNIX系统中，每个进程的建立都给定一个虚地址空间，这个空间包含了由编译器生成的全部虚地址。2）：物理地址空间：物理存储器中的每个字都是用唯一的物理地址标识的。主存储器中的所有存储字 构成物理地址空间。3）：地址映象设V是处理机运行程序所生成的一组虚拟地址，M是为运行该程序而分配的一组物理地址。虚拟存储器需要一种自动的机制实现以下映象：: VM¢ 即虚拟地址到物理地址之间的转换。2 什麽是命中率、缺页、多级页表？命中率：当在存储器Mi中找

2、到一个信息项时，我们称之为命中，命中率hi则是信息项在Mi中找到的概率。缺页：表示所访问的页面没有驻留在主存储器中。多级页表：为扩展存储器空间并能在存储器层次结构的不同层次上提供更多的页面访问保护，对直接页面映象用多级页表扩充。3：简述Cache管理中直接地址映象法和全相联映象法。（1） 直接映象：它将主存按Cache容量大小分块，每块又分成页，页面大小同Cache 页面。规定每块中的相应页面与Cache中的相应页面对应。这种映象方法容易实现，但不灵活，页面冲突率较高，命中率低。（2） 全相联映象：它是指主存中任何一页都可以映象到Cache中任何一页的位置上。这种方法灵活，页面冲突率较小，命中

3、率高，但速度慢，代价高，不易实现。4简述组相联映象法。组相联映象法是介于直接地址映象法和全相联映象法之间的一种方案。它将Cache分成大小相等的组，每组内又分页。主存按Cache大小分块，块内分组，组内分页。使主存的组与Cache的组大小相等，主存的页与Cache的页大小一致。它的特点是组与组之间采用直接映象，组内各页采用全相联映象。组内页面数多，灵活性大，命中率高，但地址变换电路复杂。5什麽是散列函数，倒置页表，存储器替换策略。（1） 散列函数：散列是一种简单的计算机技术，它可以用较少位数把长页号转换为短页号。散列函数应将虚拟页号随机化并产生唯一的散列号用做指针。同余函数使散列形成链表。（2

4、） 倒置页表：虚拟空间地址非常大时，需要大的PT或多级直接分页，这种地址转换映象可以用倒置映象来实现。已分配给用户的每个页面框架都可以建立一张倒置页表。（3） 存储器替换策略:它包括为活动进程分配和再分配存储器页面以及储器页面的替换。页面的替换是指主存储器内的常驻页面被从磁盘传送来的新页面所替换的过程。目的是将缺页的数量降到最小，减少存储器有效存储时间。6在Cache管理中，新的主存页需要调Cache时，有几种替换算法？各有何特点？那种算法命中率高？在Cache管理中，当新的主存页需要调Cache时，常用的有先进先出（FIFO）算法和LRU算法。前者是把一组中最先调入的Cache的页面替换出去

5、，它不需要随时记录隔夜的使用情况，所以容易实现，且开销小；后者是把一组中近期最少使用的页面替换出去，这种方法需要随时记录Cache中各页的使用情况，以便确定哪个也是近期最少使用的页。LRU算法比FIFO命中率高。7为什麽多体交叉存储器可提高存储器速度？多体交叉存储器是将存储器分成若干个（m）个独立的模块，设m=1 、2、4、8、个模块的容量和存储周期均相等，且它们可以独立的进行读写操作。这样，不同的请求源同时访问不同的模块，便可提高存储器速度。8提高存储器速度可采用哪些措施？简要说明。提高存储器速度可采用三种措施：1） 采用高速器件，选用存储周期小的芯片，整个存储器的速度便可提高。2） 采用C

6、ache，CPU将最近期要用的信息先调入Cache,而Cache的速度比贮存快的多，这样CPU每次只需从快速缓存中取出或存入信息，从而缩短了访问时间，提高了存取速度。3） 可采用多体交叉存储器。特点见第7题。9什麽是快速缓冲存储器，它与贮存的关系是什麽？快速缓冲存储器是为了提高访存速度，在CPU和主存之间增设的一种高速存储器，它对用可以达到访问主存的目的，从而提高了方寸速度。主存的信息调入缓存要根据一定的算法，由CPU自动完成。凡是主存和缓存已建立了对应关系的存储单元内容必须保持一致，故凡是写入缓存的信息也必须挟至于缓存单元对应的主存单元中。10什麽是程序访问局部性？存储系统哪一级采用了程序访

7、问的访问局部性？所谓程序访问局部性即程序执行是对存储器的访问是不均匀的，也就是说它的地址分布不是随机的，而是相对簇集，它所用的数据也是相对地簇集。存储系统的Cache-主存级和主存-辅存级都要用到程序的局部性原理。对Cache-主存级而言，把CPU最近起执行的程序放在容量较小、速度较高的Cache中。对主存-辅存级而言，把程序中访问频率高、比较活跃的部分放在主存中。这样既提高了存储器的速度又扩大了存储器的容量。11设有一个两层的存储器结构：M1和M2。M1的命中率用h表示，并分别令c1和c2为每千字节的成本，s1和s2位存储器容量，t1和t2为存取时间。（1）在什麽条件下整个存储器系统的平均成

8、本会接近于c2？（2）该层次结构的存储器有效存取时间ta是多少？（3）另两层存储器的速度比r= t2 /t1, 并令E= t1/ta 为存储系统的存储效率。试以速度比r和命中率h来表示E。（4）如果r =100, 为使 E>0.95, 要求的命中率h是多少？解：（1）平均成本c=( c1 s1+c2 s2)/( s1+s2)当s2 >> s1, c2 s2 >> c1 s1时, c c2（2） ta=ht1+(1-h)t2（3）r= t2 /t1 E= t1/taE = t1/( ht1+(1-h)t2)=1/(h+(1-h)r)（4）r =100, E>0

9、.95,1/（h+(1-h)r）=E>0.95 = h0.9912试比较多计算机系统的私用虚拟存储器和全局共享存储器的优缺点。私用虚拟存储器优点：（1）处理机所用地址空间较少；(2)保护在美意野火每个进程上进行以及采用不要锁定的私用存储器映象。缺点：（1） 在同义性问题，记在不同或相同虚拟空间里的不同虚拟地址会指向同一物理页面。（2） 在不同虚拟空间里的同一虚拟地址可能指向主存储器不同页面。全局共享存储器优点：（1） 所有的地址都唯一;（2） 不存在同义性问题。缺点：(1) 页表可以共享存取。需要用互斥来实施保护；(2) 分段建立在分页系统的顶部，以便把每个进程限制在它自己的地址空间(段

10、)里。(3) 全局共享存储器使地址转换过程变得更长。13试说明多层存储器层次结构的包含性和存储器一致性要求。多层存储器层次结构的包含性可用M1M2M3.Mn 来描述。建立包含关系意味着所有的信息项最初是放在最外层Mn的。在处理过程中，Mn的子集复制到Mn-1。同样Mn-1的子集复制到Mn-2，以此类推。存储器一致性要求同一个信息相遇后继存储器层次上的副本是一致的。如果在高速缓存仲的一个字被修改过，那麽在所有更高层上该字的副本也必须立即或最后加以修改。层次结构必须有这样的保护。为了尽量减少存储器层次结构的有效存取时间，频繁使用的信息通常是在较低层次中可以找到的。14什麽是写直达和写回。写直达：即

11、如果在Mi中修改了一个字，则在Mi+1中需要立即修改。写回： 即在Mi+1中修改延迟到Mi中正在修改的字被替换或从Mi中消除后才进行。15说明分页与分段在层次结构中管理物理与虚拟存储器的基本概念。分页是一种把物理存储器和虚拟存储器都划分为固定大小页面的技术。它们之间的信息交换是在页面一级进行的。页表用于页面和页面框架之间的映象，它们是应用程序创建用户进程时在主存储器内实现的。由于许多用户进程可能是动态创建的的，因此在主存储器中要保存的PT数量会更大。分段是将虚拟存储器地址空间分散的页面连在一起形成一个段，段是用户定义的虚拟地址空间的一部分。在段式存储器系统中，用户程序可以逻辑地按段来构造，各段

12、可以相互调用。段的长度是可以改变的，但它的管理由于段的大小不等而更为复杂。16试说明在存储器层次结构中与程序/数据存取有关的时间局部性、空间局部性和顺序局部性。 时间局部性：最近的访问项（指令和数据）很可能在不久的将来再次被访问。这种情况一般是由于特殊的程序结构诸如迭代循环、进程堆栈、暂时变量或子程序引起的。一旦进入循环或调入了子程序，一个短代码段兼备重复访问许多次。因此，时间局部性会引起对最近使用区域的集中访问。空间局部性：表示一种趋势，指的是一个进程访问的各项地址彼此很紧。例如，表操作或数据操作就会对地址空间中某一区域集中进行访问。程序段，如子程序和宏，往往会访问在存储器空间的同一领域。顺

13、序局部性：在典型的程序中，除非转移指令产生不按次序的转移外，指令都是顺序（或程序顺序）执行的。按序执行和不按序执行的比例在普通程序中大致是51。此外对大型数据的访问也是顺序进行的。17存储器设计的含义是什麽。程序行为的顺序性是造成空间局部性的原因之一，因为顺序编码的指令和数组元素通常存放在相邻单元内。各种类型的局部性影响存储器层次结构设计。时间局部性会导致近期最少使用的LRU替换算法的流行。空间局部性将帮助我们确定相邻存储器层次间数据传送单位的大小，时间局部性有助于确定相继层次存储器的容量。顺序局部性会影响实现最佳调度时粒度（粒度组合）的确定，并对预取技术也有重要影响。局部性原理将指导我们去设

14、计高速缓存、主存储器以及虚拟存储器组织。18工作集及灵敏度的含义是什麽？在软件或程序进程的存储器访问模式中，作为时间的函数，虚拟地址空间（用页面号标识）由于访问的局部性而集中在一定区域，Denning 将给定的时间窗口（t, t+t）范围内被访问的地址（或）页面子集称为工作集。在程序执行过程中，工作集会缓慢变化并维持一定程度的连续性，这意味着工作机场尝试在存储器层次结构的最内层，如高速缓存上积累起来的。这是因为存储器最低层次的命中率较高，因而可减少存储器的有效存取时间。时间窗口t是由OS内核设置的一个关键参数，它将影响工作集的大小，以及所需高速缓存的容量。19设有一个存储器层次结构M1和M2，

15、存取时间、每个字的成本和容量分别是t1和t2，c1和c2，s1和s2。在第一层，高速缓存的命中率h1=0.95（注意：t2是CPU和M2之间的存取时间，而不是M1和M2之间的存取时间）。(1) 推倒表示该存储器有效存取时间teff的公式。(2) 推倒表示该存储器总成本的公式。解：（1）存储器有效存取时间teff= h1 t1+（1-h1）t2=0.95t1+0.05t2(2) 存储器总成本C= c1 s1+ c2 s220在上题中，假设t1=20ns，t2是未知数，s1=512K字节，s2是未知数，c1=0.01美元/字节，c2=0.0005美元/字节.高速缓存和主存储器总成本的上限是1500

16、0美元。(1) 在不超过预算限制的范围内，可能得到的M2的容量由多大？(2) 在上述命中率假设的条件下，为使整个存储器系统的有效存取时间teff=40ns，主存储器应该有多快？解：（1）c1=0.01美元/字节，c2=0.0005美元/字节，s1=512K字节，C15000美元C= c1 s1+ c2 s2=0.01*512*103+0.0005* s215000s2(15600-5120)/0.0005s219.8M字节(2) teff= h1 t1+（1-h1）t2=0.95t1+0.05t2=40nst2=(40ns-0.95*20ns)/0.05=420ns21.解释写时间和写周期。写

17、时间：是从CPU给出有效地址后，将数据线上的信息写入被选单元中所需的时间;写周期：是存储器进行两次连续写操作的最小时间间隔。写周期大于写时间。22解释度周期和读时间。读时间：是从CPU给出地址有效信号到被选单元的内容读到数据线上的这段时间；读周期：使存储器进行两次连续读操作的最小时间间隔。读周期大于读时间。23解释存储周期、存取时间、存储容量。存储周期：是存储器进行两次连续独立的操作（读或写）之间所需的最短时间。存取时间：分为读时间和写时间。读时间：是从CPU给出地址有效信号到被选单元的内容读到数据线上的这段时间；写时间：是从CPU给出有效地址后，将数据线上的信息写入被选单元中所需的时间。存储

18、容量：是存储器存放二进制信息的总数量。24存储器的主要功能是什麽？如何衡量存储器的性能？为什麽把存储器系统分成若干不同的层次？主要由那些层次？存储器的主要功能是存放程序和各类数据；通常用存储容量和存取周期两项指标来衡量存储的性能。为了扩大存储器的容量和提高访存速度，将存储器系统分成若干不同的层次，有Cache-主存层次和主存-辅存层次。前者是为使存储器与CPU速度匹配，在CPU和主存之间增设Cache高速缓冲存储器，其容量比主存小，速度比主存快，用来存放CPU最近期要用的信息，CPU可直接从Cache中取到信息，从而提高了访存速度。后者为扩大存储器容量，把主存和辅存统一成一个整体，从整体上看，

19、速度取决于主存，容量取决于辅存，称为虚存。CPU只与主存交换信息，但程序员可用指令地址码进行编程，其位数与虚存的地址空间相对应。25什麽是组联想高速缓存？其优点是什麽？组联想高速缓存：是直接映象和全联想高速缓存设计的折衷。在k路联想高速缓存中，dm 个高速缓存块框被分成v=m/k组，每组k块。各组可用一个d位的组号来识别，这里2=v .这样高速缓存块标记就减少到s-d位。组联想高速缓存优点：(1) 块替换算法考虑的对象只是在同一组中的少数几个块。因此，与全相连高速缓存相比，替换策略的选择比较有限，因而可更加经济地实现。(2) k路联想检索实现起来比较容易。(3) 可以考虑许多设计上的这种方案，

20、以便获得更高的高速缓存命中率。26下表表示使用页表的虚实地址转换条件，页表存放在相联存储器中，其容量为8个存储单元，(1) 当CPU按虚拟地址1去访问主存时，主存的实际地码是多少？(2) 当CPU按虚拟地址2去访问主存时，主存的实际地码是多少？(3) 当CPU按虚拟地址2去访问主存时，主存的实际地码是多少？解：(1) 当CPU按虚拟地址1去访问主存时,它的页号为15，虚拟页内地址为0324，按页号在主存中检索，在主存中页号为15的起始地址码是80000，所以它的实际码是80000+0324=80324。(2) 当CPU按虚拟地址2去访问主存时,它的页号为7，虚拟页内地址为0128，按页好在主存

21、中检索，在主存中页号为7的起始地址码是96000，所以它的实际码是96000+0128=96128。(4) 当CPU按虚拟地址2去访问主存时,它的页号为48，当用48作检索相在块表中检索时，没有检索到页号为48的页面，此时操作系统暂停用户作业程序的执行，装去执行查页表程序。如该页在主存中，则将该页号及该页在主存的起始地址写入快表；如该页不在主存内，则操作系统需将该页从外存调入主存，然后将页号及其在主存中的起始地址写入快表。27某小型计算机字长16位，常规的存储空间为64K字，若将存储空间扩充到256K字，请提出一种可能的方案，并说明在使用时应注意什麽问题？解：可采用多体交叉存取方案，即将主存分

22、成4个相互独立、容量相同的模块M0、M1、M2、M3,每个模块容量为64K*16位，它们个具备一套地址寄存器、数据缓冲寄存器，各自以同等的方式与CPU传递信息。CPU访问4个存储模块可采用两种方式：一种是在一个存取周期内，同时访问4个存储模块，由存储器控制器控制它们分时使用总线进行信息传递；另一种方式是在存取周期内，分是访问每个体，即每经过1/4存取周期就访问一个模块。这样，对每个模块而言，存取周期未变，而对CPU而言，它可以在一个存取周期内访问4个体，获得16位*4=64位信息，每个体的读写过程是并行进行的。28.简述主存的读写过程。存储器的读出过程是：CPU先给出有效地址，然后给出片选（通

23、常受CPU访存信号控制）信号和读命令，这样就可将被选中的存储单元内的各位信息读至储芯片的数据总线上，王成了读操作。存储器的写入过程是：CPU先给出有效地址，然后给出片选（通常受CPU访存信号控制）信号和写命令，并将欲写入的信息送至存储器的数据线上，这样信息就可写入到被选中的存储单元。29按字成本、容量和存取时间画出存储器层次结构。30.存储器顺序一致性和弱一致性模型有那些不同点.（1）由于用了更复杂的硬件/软件支持并需要程序员更多地知道对模型施加的限制，弱一致性模型的性能优于顺序一致性模型。(2) 存储器弱一致性模型可以克服由于强存储次序使处理机/高速缓存的等待时间的增加、并发行降低等问题。(

24、3)在存储器顺序一致性对所有共享存储器访问的强排序使所有处理机的程序次序难以保证。31说明多体交叉存储器的组成原理。多体交叉存储器主要由存储体，存储器控制器和总线控制三部分组成。存储器控制器用于多体并行工作，实现分时读出的工作方式，管理信息流动次序和流动方向。当CPU或通过IOP的外设向主存系统重叠发出访问要求时，存储器控制器首先对这些访问源进行排队，设计人员事先已经根据所有访问源性质区分轻重缓急、排出优先级别。存储器控制器选择其中优先级别最高的先访问，并向它所访问的分体发出启动信号以及访问地址。如果它所访问的那个存储分体正处于工作状态，无法接受访问，则暂时取消该访问源排队资格，让给优先级别稍

25、低的访问源访问其他存储器。每个存储分体不但有自己的读写控制线路、数据缓存设备、而且各具忙闲状态触发器。多体交叉存储器组成如下图所示:多体交叉存储器组成32简述存储器层次结构技术。存储设备，如寄存器、高速缓存、主存储器、磁盘设备和磁带技术都是按一定的层次组织的。在每一层上，存储器技术和存储组织可用五个参数来表征：存取时间，存储器容量、每字节成本、传输带宽和传输单位。较低层存储设备与较高层存储设备的相比，其存取速度快、容量较小、每字节成本高、带宽较宽、传输单位较小。33使用说明多用户、页式管理的虚拟存储器工作过程。(1) 由指令中的字段求得逻辑地址，继续地址，包含用户号、虚页号、页内地制。(2)

26、如果不明中则查页表。(3) 如果也表仍不命中，说明该也尚未进入主存，需要查外表页，求得辅存实地址。(4) 查主页使用情况，如果主页中尚有空间区，则可将所查到的也通过I/O接口调入主存；如果主业已满，则访问替换部件，根据替换算法，替换主存内容。(5) 在进行主存替换时，如果该页在运行过程中没有修改过，则不必送回；如果修改过，则立即送回辅存。34什麽是存储器弱一致性？存储器弱一致性：Dubois,Scheurich和Briggs通过建立主存储器与程序同步点的关系，提出了一种弱一致性存储器模型。它可以用下列三个条件来描述：(1) 一台处理机必须执行完所有的同步访问之后，才能允许任何其他处理机执行取或

27、存访问。(2) 一台处理机必须执行完所有的取或存访问之后，才能允许任何其他处理机执行同步访问。(3) 同步访问之间相互是顺序一致的。35试用图表示一个四体交叉存储器的分时工作原理。多体交叉存储器主存与CPU交换信息的通道只有一字的宽度，为了在一个存储周期里访问n个信息字，在多体并行主存系统中采用了分时工作的方法。四体交叉存储器由四个分体组成，每个存储体一次只读写意个字，分体分时启动，即每隔1/4存储周期启动一个分体。M0M1M2M31/4 2/4 3/4 1 2 （TM）四体交叉存储器并行分时工作36使用图示法说明虚拟存储器地址转换机制。进程要求把虚拟地址转换成物理地址。转换需要使用转换映象。

28、虚拟地址转换方案如图所示：(ATC) 一级PT 多级PT 联想的PT 倒置的PT37简要回答存储器的基本概念级组成。存储器是存放程序与数据的部件，它具有可靠地存储二进制信息的能力。信息存放后，可以稳定存储，不易丢失、不易改变，同时应能方便地存入和取出，一次保证计算机具有良好的记忆功能。存储器组成主要包括以下四部分：（1）存储体。积存二进制信息的物理实体，又半导体单元电路（如触发器）或磁性物质实现。可以并行存取的二进制信息组成一个存储单元，大量的存储单元组成存储体。隔存储单元由地址码。（2）地址部件。其功能是按照指定的地址码来控制一个存储单元的存取。（3）数据部件。其功能是暂存取出和写入的数据，

29、以使存储器的信息在时间上和形式上都能满足其他部件的要求。（4）控制部件。根据要求产生主存工作所需的控制信号。38顺序一致性的定义以及共享存储器访问时顺序一致性的条件是什麽？顺序一致性模型的定义（Lamport定义）：如果任意一次执行的结果都象所有处理机的操作是以某种顺序的次序执行所得到的一样，而且救灾这个序列中，各处理机的操作都是按照它的程序所指定的次序出现，那麽这样的多处理及时顺序一致性系统。共享存储器访问时顺序一致性的条件是：（1）：在对其他任何一台处理机执行完一次存取之前，必须全局地执行完成在此之前的所有存取访问，而且在此之前对所有处理机的所有存访问也必须完成。(2):在对其他任何一台处理机执行完成一次存之前，必须全局地完成在此之前所有的取访问，而且在此之前对所有处理机的所有取访问也必须执行完成。39说明在高速缓存中块的大小对命中率的影响。高速缓存的命中率将以不同的方式受到高速缓存容量愉快大小的影响。通常，命中率是随着高速缓存容量的增加而