篇一:《计算机组成原理题(附答案)》
计算机组成原理题解指南
第一部分:简答题
第一章 计算机系统概论
1.说明计算机系统的层次结构。
计算机系统可分为:微程序机器级,一般机器级(或称机器语言级),操作系统级,汇编语言级,高级语言级。
第四章 主存储器
1.主存储器的性能指标有哪些?含义是什么?
存储器的性能指标主要是存储容量. 存储时间、存储周期和存储器带宽。
在一个存储器中可以容纳的存储单元总数通常称为该存储器的存储容量。
存取时间又称存储访问时间,是指从启动一次存储器操作到完成该操作所经历的时间。
存储周期是指连续两次独立的存储器操作(如连续两次读操作)所需间隔的最小时间。
存储器带宽是指存储器在单位时间中的数据传输速率。
2.DRAM存储器为什么要刷新?DRAM存储器采用何种方式刷新?有哪几种常用的刷新方式?
DRAM存储元是通过栅极电容存储电荷来暂存信息。由于存储的信息电荷终究是有泄漏的,电荷数又不能像SRAM存储元那样由电源经负载管来补充,时间一长,信息就会丢失。为此必须设法由外界按一定规律给栅极充电,按需要补给栅极电容的信息电荷,此过程叫“刷新”。
DRAM采用读出方式进行刷新。因为读出过程中恢复了存储单元的MOS栅极电容电荷,并保持原单元的内容,所以读出过程就是再生过程。
常用的刷新方式由三种:集中式、分散式、异步式。
3.什么是闪速存储器?它有哪些特点?
闪速存储器是高密度、 非易失性的读/写半导体存储器。从原理上看,它属于ROM型存储器,但是它又可随机改写信息;从功能上看,它又相当于RAM,所以传统ROM与RAM的定义和划分已失去意义。因而它是一种全新的存储器技术。
闪速存储器的特点:(1)固有的非易失性,(2)廉价的高密度,(3)可直接执行,(4)固态性能。
4.请说明SRAM的组成结构,与SRAM相比,DRAM在电路组成上有什么不同之处?
SRAM存储器由存储体、读写电路、地址译码电路、控制电路组成,DRAM还需要有动态刷新电路。
第五章 指令系统
1.在寄存器—寄存器型,寄存器—存储器型和存储器—存储器型三类指令中,哪类指令的执行时间最长?哪类指令的执行时间最短?为什么?
寄存器-寄存器型执行速度最快,存储器-存储器型执行速度最慢。因为前者操作数在寄存器中,后者操作数在存储器中,而访问一次存储器所需的时间一般比访问一次寄存器所需时间长。
2.一个较完整的指令系统应包括哪几类指令?
包括:数据传送指令、算术运算指令、逻辑运算指令、程序控制指令、输入输出指令、堆栈指令、字符串指令、特权指令等。
3.什么叫指令?什么叫指令系统?
指令就是要计算机执行某种操作的命令
一台计算机中所有机器指令的集合,称为这台计算机的指令系统。
第六章 中央处理部件CPU
1.指令和数据均存放在内存中,计算机如何从时间和空间上区分它们是指令还是数据。
时间上讲,取指令事件发生在“取指周期”,取数据事件发生在“执行周期”。从空间上讲,从内存读出的指令流流向控制器(指令寄存器)。从内存读出的数据流流向运算器(通用寄存器)。
2.简述CPU的主要功能。
CPU主要有以下四方面的功能:(1)指令控制 程序的顺序控制,称为指令控制。
(2)操作控制 CPU管理并产生由内存取出的每条指令的操作信号,把各种操作信号送往相应部件,从而控制这些部件按指令的要求进行动作。
(3)时间控制 对各种操作实施时间上的控制,称为时间控制。
(4)数据加工 对数据进行算术运算和逻辑运算处理,完成数据的加工处理。
3.举出CPU中6个主要寄存器的名称及功能。
CPU有以下寄存器:
(1)指令寄存器(IR):用来保存当前正在执行的一条指令。
(2)程序计数器(PC):用来确定下一条指令的地址。
(3)地址寄存器(AR):用来保存当前CPU所访问的内存单元的地址。
(4)缓冲寄存器(DR):
<1>作为CPU和内存、外部设备之间信息传送的中转站。
<2>补偿CPU和内存、外围设备之间在操作速度上的差别。
<3>在单累加器结构的运算器中,缓冲寄存器还可兼作为操作数寄存器。
(5)通用寄存器(AC):当运算器的算术逻辑单元(ALU)执行全部算术和逻辑运算时,为ALU提供一个工作区。
(6)状态条件寄存器:保存由算术指令和逻辑指令运行或测试的结果建立的各种条件码内容。除此之外,还保存中断和系统工作状态等信息,以便使CPU和系统能及时了解机器运行状态和程序运行状态。
4.比较水平微指令与垂直微指令的优缺点。
(1)水平型微指令并行操作能力强、效率高、灵活性强,垂直型微指令则较差。
(2)水平型微指令执行一条指令的时间短,垂直型微指令执行时间长。
(3)由水平型微指令解释指令的微程序,具有微指令字比较长,但微程序短的特点,而垂直型微指令正好相反。
(4)水平型微指令用户难以掌握,而垂直型微指令与指令比较相似,相对来说比较容易掌握
5.什么是指令周期?什么是机器周期?什么是时钟周期?三者之间的关系如何?
指令周期是完成一条指令所需的时间。包括取指令、分析指令和执行指令所需的全部时间。
机器周期也称为CPU周期,是指被确定为指令执行过程中的归一化基准时间,通常等于取指时间(或访存时间)
时钟周期是时钟频率的倒数,也可称为节拍脉冲或T周期,是处理操作的最基本单位。
一个指令周期由若干个机器周期组成,每个机器周期又由若干个时钟周期组成。
6.什么是RISC?RISC指令系统的特点是什么?
RISC是精简指令系统计算机,它有以下特点:
(1)选取使用频率最高的一些简单指令,以及很有用但不复杂的指令。
(2)指令长度固定,指令格式种类少,寻址方式种类少。
(3)只有取数/存数指令访问存储器,其余指令的操作都在寄存器之间进行。
(4)大部分指令在一个机器周期内完成。
(5)CPU中通用寄存器数量相当多。
(6)以硬布线控制为主,不用或少用微指令码控制。
(7)一般用高级语言编程,特别重视编译优化工作,以减少程序执行时间。
7.什么是CISC?CISC指令系统的特点是什么?
CISC是复杂指令系统计算机的英文缩写。其特点是:
(1)指令系统复杂庞大,指令数目一般多达2、3百条。 (2)寻址方式多
(3)指令格式多 (4)指令字长不固定
(5)可访存指令不加限制 (6)各种指令使用频率相差很大
(7)各种指令执行时间相差很大 (8)大多数采用微程序控制器
8.什么叫指令?什么叫微指令?二者有什么关系?
指令,即指机器指令。每一条指令可以完成一个独立的算术运算或逻辑运算操作。
控制部件通过控制线向执行部件发出各种控制命令,通常把这种控制命令叫做微命令,而一组实现一定操作功能的微命令的组合,构成一条微指令。许多条微指令组成的序列构成了微程序,微程序则完成对指令的解释执行。
第七章 存储系统
1.什么是存储保护?通常采用什么方法?
当多个用户共享主存时,为使系统能正常工作,应防止由于一个用户程序出错而破坏其它用户的程序和系统软件,还要防止一个用户程序不合法的访问不是分给它的主存区域。为此,系统提供存储保护。通常采
用的方法是:存储区域保护和访问方式保护。
第九章 输入输出(I/O)设备
1.何谓CRT的显示分辨率、灰度级?
分辨率是指显示器所能表示的像素个数。像素越密,分辨率越高,图像越清晰。分辨率取决于显像管荧光粉的粒度、荧光屏的尺寸和CRT电子束的聚焦能力。同时刷新存储器要有与显示像素数相对应的存储空间,用来存储每个像素的信息。
灰度级是指黑白显示器中所显示的像素点的亮暗差别,在彩色显示器中则表现为颜色的不同。灰度级越多,图像层次越清楚逼真。
2.什么是刷新存储器?其存储容量与什么因素有关?
为了不断提供刷新图像的信号,必须把一帧图像信息存储在刷新存储器,也叫视频存储器。其存储容量由图像灰度级决定。分辨率越高,灰度级越多,刷新存储器容量越大。
第十章 输入输出(I/O)系统
1.外围设备的I/O控制方式分哪几类?各具什么特点?
外围设备的I/O控制方式分类及特点:
(1)程序查询方式:CPU的操作和外围设备的操作能够同步,而且硬件结构比较简单
(2)程序中断方式:一般适用于随机出现的服务,且一旦提出要求应立即进行,节省了CPU的时间,但硬件结构相对复杂一些。
(3)直接内存访问(DMA)方式:数据传输速度很高,传输速率仅受内存访问时间的限制。需更多硬件,适用于内存和高速外设之间大批交换数据的场合。
(4)通道方式:可以实现对外设的统一管理和外设与内存之间的数据传送,大大提高了CPU的工作效率。
(5)外围处理机方式:通道方式的进一步发展,基本上独立于主机工作,结果更接近一般处理机。
2.总线的一次信息传送过程大致分哪几个阶段?
分五个阶段:请求总线、总线仲裁、寻址(目的地址)、信息传送、状态返回(或错误报告)。
3.一个计算机系统中的总线,大致分为哪几类?
一个计算机系统中的总线分为三类:
(1)同一部件如CPU内部连接各寄存器及运算部件之间的总线,称为内部总线。
(2)同一台计算机系统的各部件,如CPU、内存、通道和各类I/O接口间互相连接的总线,称为系统
总线。
(3)多台处理机之间互相连接的总线,称为多机系统总线。
4.说明总线结构对计算机系统性能的影响。
(1)最大存储容量
单总线系统中,最大内存容量必须小于由计算机字长所决定的可能的地址总线。
双总线系统中,存储容量不会受到外围设备数量的影响
(2)指令系统
双总线系统,必须有专门的I/O指令系统
单总线系统,访问内存和I/O使用相同指令
(3)吞吐量
总线数量越多,吞吐能力越大
5.中断处理过程包括哪些操作步骤?
中断处理过程如下:
(1)设备提出中断请求
(2)当一条指令执行结束时CPU响应中断
(3)CPU设置“中断屏蔽”标志,不再响应其它中断请求
(4)保存程序断点(PC)
(5)硬件识别中断源(转移到中断服务子程序入口地址)
(6)用软件方法保存CPU现场
(7)为设备服务
(8)恢复CPU现场
(9)“中断屏蔽”标志复位,以便接收其它设备中断请求
(10)返回主程序
6.画出中断处理过程的流程图。
解:图如下:
7.中断接口中有哪些标志触发器?功能是什么?
中断接口中有四个标志触发器:
(1)准备就绪的标志(RD):一旦设备做好一次数据的接受或发送,便发出一个设备动作完毕信号,使RD标志置“1”。在中断方式中,该标志用作为中断源触发器,简称中断触发器。
(2)允许中断触发器(EI):可以用程序指令来置位。EI为“1”时,某设备可以向CPU发出中断请求;EI为“0”时,不能向CPU发出中断请求,这意味着某中断源的中断请求被禁止。设置EI标志的目的,就是通过软件来控制是否允许某设备发出中断请求。
(3)中断请求触发器(IR):它暂存中断请求线上由设备发出的中断请求信号。当IR标志为“1”时,表示设备发出了中断请求。
(4)中断屏蔽触发器(IM):是CPU是否受理中断或批准中断的标志。IM标志为“0”时,CPU可以受理外
界的中断请求,反之,IM标志为“1”时,CPU不受理外界的中断。
还有一个称为工作触发器:(BS):设备“忙”的标志,表示设备正在工作。{对,,,,,的一次访问}.
8.CPU响应中断应具备哪些条件?
(1)在CPU内部设置的中断允许触发器必须是开放的。
(2)外设有中断请求时,中断请求触发器必须处于“1”状态,保持中断请求信号。
(3)外设(接口)中断允许触发器必须为“1”,这样才能把外设中断请求送至CPU。
(4)当上述三个条件具备时,CPU在现行指令结束的最后一个状态周期响应中断。
9.请说明程序查询方式与中断方式各自的特点。
程序查询方式,数据在CPU和外围设备之间的传送完全靠计算机程序控制,优点是硬件结构比较简单,缺点是CPU效率低,中断方式是外围设备用来“主动”通知CPU,准备输入输出的一种方法,它节省了CPU时间,但硬件结构相对复杂一些。
10.简要描述外设进行DMA操作的过程及DMA方式的主要优点。
(1)外设发出DMA请求
(2)CPU响应请求,DMA控制器从CPU接管总线的控制
(3)由DMA控制器执行数据传送操作
(4)向CPU报告DMA操作结束
(5)主要优点是数据传送速度快
第二部分:其他题型
一、选择题:
1、完整的计算机系统应包括 。
A、运算器、存储器、控制器 B、外部设备和主机
C、主机和实用程序 D、配套的硬件设备和软件系统
2、计算机系统中的存储器系统是指 。
A、RAM存储器 B、ROM存储器
C、主存储器 D、主存储器和外存储器
3、至今为止,计算机中的所有信息仍以二进制方式表示的理由是 。
A、节约元件 B、运算速度快 C、物理器件性能所致 D、信息处理方便
4、冯·诺依曼机工作方式的基本特点是 。
A、多指令流单数据流 B、按地址访问并顺序执行指令
C、堆栈操作 D、存储器按内部选择地址
5、某寄存器中的值有时是地址,因此只有计算机的 才能识别它。
A、译码器 B、判断程序 C、指令 D、时序信号
6、50年代,为了发挥 的效率,提出了 技术,从而发展了操作系统,通过它对 进行管理和调度。
A、计算机,操作系统,计算机 B、计算,并行,算法
C、硬设备,多道程序,硬软资源 D、硬设备,晶体管,计算机
7、计算机硬件能直接执行的只有 。
A、符号语言 B、机器语言 C、机器语言和汇编语言 D、汇编语言
8、在机器数中, 的零的表示形式是唯一的。
A、原码 B、补码 C、反码 D、原码和反码
9、针对8位二进制数,下列说法中正确的是 。
A、-127的补码为10000000 B-127的反码等于0的移码
C、+1的移码等于-127的反码 D、0的补码等于-1的反码
10、计算机系统中采用补码运算的目的是为了 。
A、与手工运算方式保持一致 B、提高运算速度
C、简化计算机的设计 D、提高运算的精度
篇二:《操作系统大题答案》
操作系统原理复 习题一
1、 试对分时系统和实时系统进行比较。
可以从多路性、独立性、及时性、交互性和可靠性5个方面对分时系统和实时系统进行比
较。
(1)多路性。系统按分时原则为多个终端用户服务;而对实时控制系统,其多路性则
主要表现在经常对多路的现场信息进行采集以及对多个对象或多个执行机构进行控制。(2)独立性。都有独立性。每个终端用户在向实时系统提出服务请求时,是彼此独立的操作,互不干扰;而在实时控制系统中信息的采集和对对象的控制,也彼此互不干扰。(3)及时性。实时信息系统对实时性的要求与分时系统类似,都是以人所能接受的等待时间来确定;而实时控制系统的及时性,则是以控制对象所要求的开始截止时间或完成截止时间来确定的(4)交互性。实时信息处理系统具有交互性,而分时系统能向终端用户提供数据处理服务、资源共享等服务。(5)可靠性。分时系统要求系统可靠,相比之下,实时系统则要求系统高度可靠。
2、有一个仓库,可以存放A和B两种产品,但要求:
(1)、每次只能存放一种产品(A或B);
(2)、-N < A产品数量- B产品数量< M。
其中,N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。
解:在本题中,我们可以设置两个信号量来控制A、B产品的存放数量,sa表示当前允许A产品比B产品多入库的数量,即在当前库存量和B产品不入库的情况下,还可以允许sa个A产品人库;sb表示当前允许B产品比A产品多入库的数量,即在当前库存量和A产品不入库的情况下,还可以允许sb个B产品入库。初始时,sa为M-1,sb为N-1。当往库中存放入一个A产品时,则允许存入B产品的数量也增加1:当往库中存放入一个B产品时,则允许存入A产品的数量也增加1。
产品A、B的入库过程描述如下:
mutex=1; /* 互斥信号量 */
sa=M-1; sb=N-1;
Process_A() Process_B()
{ {
while(1) while(1)
{ {
取一个产品; p(sb);
p(sa); p(mutex);
p(mutex); B产品入库;
A产品入库; v(mutex);
v(mutex); v(sa);
v(sb); }
} }
}
3、有一页式系统,其页表存放在内存中。
(1)、如果对内存的一次存取需要1.5微秒,问实现一次页面访问的存取时间是多少?
(2)、如果系统增加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,问此时的存取时间为多少?
答:a.在分页存储管理中,当访问一条指令或数据时需要访问内存至少两次。一次是访问存
放在内存中的页表PMT,实现地址变换; 另一次是访问所需的数据,3微妙。
b.若快表的命中率是85%,则有效存取时间为:0.85×1.5 (1-0.85)×3=1.725μs
4、在一个请求分页系统中,假定系统分配给一个作业的物理块数为3,并且此作业的页面走向为2、3、2、1、5、2、4、5、3、2、5、2。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页率。
5、I/O控制可用哪几种方式实现?各有何优缺点?
I/O控制过程可用三种方式实现:作为请求I/O操作的进程实现;作为当前进程的一部分
实现;由专门的系统进程——I/O进程完成。第一种方式请求对应I/O操作的进程能很快占据处理机但要求系统和I/O操作的进程应具有良好的实时性。第二种方式不要求系统具有高的实时性,但I/O控制过程要由当前进程负责。第三种方式增加了一个额外的进程开销,但用户不用关心I/O控制过程。
7、使用文件系统时,通常要显式地进行OPEN和CLOSE进行操作。试问
(1) 这样做的目的是什么?
答:显式的OPEN操作完成文件的打开功能。它将待访问文件的目录信息读入内存活动文件表中,建立起用户进程与文件的联系。显式的CLOSE操作完成文件的关闭操作。该命令撤消主存中有关文件的目录信息,切断用户与该文件的联系;或在文件打开期间,该文件作过某种修改,还应将其写顺回辅存。
(2) 若取消显式的OPEN,CLOSE操作,应如何做?
答:可以取消显式的OPEN与CLOSE操作。如果取消了显式OPEN与CLOSE操作,系统在进行文件操作之前需判断文件是否已打开,则应自动完成文件的打开功能,以建立用户与文件间的联系。同时,在系统结束时,还应自动关闭所有打开文件。
(3) 取消显示的OPEN,CLOES有什么不利?
答:取消显式的OPEN与CLOSE操作得文件的读写的系统开销增加。因为在每次读写前都需要判断文件是否已被打开。系统在结束时也要做一些额外的工作,以完成CLOSE命令
的功能。当用户进程已使用完一个文件但尚未执行完成时,因无显式的CLOSE命令也无法关闭文件,从而不利于系统资源的回收。
四、证明题
1、 考虑由n个进程共享的具有m个同类资源的系统,证明:如果对i=1,2,…,n,有 0 < Need(i)≤ m而且所有进程最大需求量之和小于m n,那么该系统是死锁无关的。
证明:令每个进程请求共享资源的最大量相等,且为x,(0<x≤m),那么在最坏的情况下每个进程都占有(x-1)个共享资源,并各自最多再申请一个资源就可以运行完毕,进而释放它们所占有的全部资源。
此刻,系统剩余的可用资源数为:m - n*(x-1)。当m – n*(x-1)≥1时,即x ≤ (m n-1)/n时,系统不会出现死锁的。因此得出,系统中所有进程的最大需求量之和n×x ≤ (m n-1) 时,系统是不会发生死锁的。所以,n个进程的最大需求量之和小于m n时,系统与死锁无关。
2、 若系统中有作业1、2、3几乎同时到达,已知它们的运行时间依次为a、b、c,且满足关系式a<b<c,试证明采用短作业优先调度算法能获得最小平均周转时间。
证明:采用短作业优先算法调度时,三个作业的总周转时间为:Tl = = a ( a b ) ( a b c ) = 3a 2b c 若不按短作业优先算法调度,不失一般性,设调度次序为:J2 、J1 、J3 。则三个作业的总周转时间为:T2=b+(b+a ) +(b+a c ) = 3b 2a c 则令②-① 式得到:T2 - Tl = b- a> 0 可见,采用短作业优先算法调度才能获得最小平均作业周转时间。
操作系统原理复 习题二
三、综合题
1、什么是操作系统?它有什么基本特征?
答:操作系统(Operating System,简称OS)是一个管理计算机系统资源,控制程序运行的系统软件,它为用户提供了一个方便、安全、可靠的工作环境和界面。它有4个基本特征。 并发性:指两个或多个事件在同一时间间隔内发生; 共享性:指系统中的资源可供内存中多个并发执行的进程共同使用; 虚拟性:指通过某种技术把一个物理实体变成若干个逻辑上的对应物; 异步性:即不确定性。在多道程序设计中,各个程序之间存在着直接或间接的联系,程序的推进速度受它的运行环境的影响。这时同一程序和数据的多次运行可能得到不同的结果;程序的运行时间、运行顺序也具有不确定性;外部输入的请求、运行故障发生的时间难以预测。这些都是不确定性的表现。
2、进程与线程的主要区别是什么?
答:进程是指运行中的应用程序,每一个进程都有自己独立的内存空间。一个应用程序可以同时启动多个进程。例如对于IE浏览器程序,每打开一个IE浏览器窗口,就启动了一个新的进程。同样,每次执行JDK的java.exe程序,就启动了一个独立的Java虚拟机进程,该进程的任务是解析并执行Java程序代码。
线程是指进程中的一个执行流程,有时也称为执行情景。一个进程可以由多个线程组成,即在一个进程中可以同时运行多个不同的线程,它们分别执行不同的任务。当进程内的多个线程同时运行时,这种运行方式称为并发运行。许多服务器程序,如数据库服务器和Web服务器,都支持并发运行,这些服务器能同时响应来自不同客户的请求。
进程和线程的主要区别在于:每个进程都需要操作系统为其分配独立的内存地址空间,而同一进程中的所有线程在同一块地址空间中工作,这些线程可以共享同一块内存和系统资源,比如共享一个对象或者共享已经打开的一个文件。
3、用P、V操作实现下述问题的解。桌上有一个盘子,可以存放一个水果。父亲总是放苹果到盘子中,而母亲总是放香蕉到盘子中;一个儿子专等吃盘子中的香蕉,而一个女儿专
等吃盘中的苹果。
定义信号量:dish:表明盘子中是否为空,初值为1;
Apple:表明盘子中是否有苹果,初值为0;
Orange:表明盘子中是否有桔子,初值为0;
main () „
{cobegin V(orange);
father (); }
mother (); son ()
son (); { P(orange);
daughter (); „
coend 取香蕉
} „
father () V(dish);
{ P(dish); }
„ daughter()
放苹果 { P(apple);
„ „
V(apple);
} 取苹果
mother() „
{ P(dish); V(dish);
„ }
放香蕉
4、设公共汽车上,司机和售票员的活动分别是:司机的活动:启动车辆;正常行车;到站停车。
售票员的活动:关车门;售票;开车门。在汽车不断地到站、停站、行驶过程中,这两个活动有什么同步关系?用信号量和P、V操作实现它们的同步。
第一步:确定进程间的关系。售票员关车门后,要向司机发开车信号,司机接到开车信号后才能启动车辆。在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开车门,让乘客上下车。因此司机启动车辆的动作必须与售票员的动作取得同步;售票员开车门的动作也必须同司机停车取得同步。第二步:确定信号量及其值。由于司机与售票员之间要互通消息,司机进程设置一个私有信号量run,用于判断是否关车门,司机能否启动车辆,初值为1。售票员进程设置一个私有信号量stop,用于判断是否停车,售票员是否能够开车门,初值为0
第三步: 确定P(wait)、V(signal)操作的位置司机操作中,是否关门?没关则等待,这是一个P操作,P(run);司机操作中,设立停车标志,这是一个V操作,V(stop);售票员操作中,是否停车?没停则等待,这是一个P操作,P(stop);售票员操作中,设立关门标志,这是一个V 操作,V(run)
lstop ,run:semaphore L1: P(run);
run:=1; //是否关车门 启动车辆;
stop:=0; //是否停车 正常行车;
Driver:begin cobegin 到站停车;
driver: begin V(stop);
goto L1; P(stop);
end; 开车门;
Conductor:begin 下乘客;
L2:上乘客; goto L2;
关车门; end;
V(run); coend;
售票; end;
5、某寺庙,有小、老和尚若干,有一水缸,有小和尚提水入缸供老和尚饮用。水缸可容10桶水,水取自同一井中。水井径窄,每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶,且不可同时进行。试给出取水、入水的算法描述。
设置5个信号量:互斥信号量mutex1,用于实现对水井的互斥使用,其初值为1;互斥信号量mutex2,用于实现对水缸的互斥使用,其初值为1;信号量empty,用于记录水缸中还可以装入水的桶数,其初值为10;信号量full,用于记录水缸中已装入水的桶数,其初值为0;信号量count,用于记录可用水桶数目,其初值为3。
Semaphore mutex1=1; P(mutex2);
Semaphore mutex2=1; 将水倒入水缸;
Semaphore empty=10; V(mutex2);
Semaphore full=0; V(count);
Semaphore count=3; V(full);
Main( ) }
{ cobegin }
Get(); Use( )
Use(); { while (ture)
Coend { P(full);{对,,,,,的一次访问}.
} P(count);
Get( ) P(mutex2);
{ while(ture) 从缸中取水;
{ p(empty); V(mutex2);
P(count); V(empty);
P(mutex1); V(count);
从井中取水; }
V(mutex1); }
6、按序分配是防止死锁的一种策略。什么是按序分配?为什么按序分配可以防止死锁? 答:按序分配是把系统中所有资源排一个顺序,每一个资源给一个确定的编号,规定任何一个进答:程申请两个以上资源时,总是先申请编号小的资源,再申请编号大的资源。按序分配可以防止死锁,证明如下:假设存在一组循环等待的进程记为(P0,P1,„,Pn),其中Pi拥有资源ri,编号为F(ri);根据按序分配原则,有F(r0)﹤F(r1)﹤„﹤F(rn),因存在循环等待,所以Pn申请的下一个资源就为P0所占的rn,,若Pn能正常运行,必须依据资源顺序分配原则,即下次申请资源标号应比其所占有的资源标号大,于是有F(rn)﹤F(r0),这与前面的不等式有矛盾,故不能存在。
7、假设有一台计算机,它有1M内存,操作系统占用200K,每个用户进程也占用200K。
篇三:《第五章课后习题答案》
5.10 假设对指令Cache的访问占全部访问的75%;而对数据Cache的访问占全部访问的
25%。Cache的命中时间为1个时钟周期,失效开销为50 个时钟周期,在混合Cache中一
次load或store操作访问Cache的命中时间都要增加一个时钟周期,32KB的指令Cache的
失效率为0.39%,32KB的数据Cache的失效率为4.82%,64KB的混合Cache的失效率为
1.35%。又假设采用写直达策略,且有一个写缓冲器,并且忽略写缓冲器引起的等待。试问
指令Cache和数据Cache容量均为32KB的分离Cache和容量为64KB的混合Cache相比,
哪种Cache的失效率更低?两种情况下平均访存时间各是多少?
解:(1)根据题意,约75%的访存为取指令。
因此,分离Cache的总体失效率为:(75%×0.15%)+(25%×3.77%)=1.055%;
容量为128KB的混合Cache的失效率略低一些,只有0.95%。
(2)平均访存时间公式可以分为指令访问和数据访问两部分:
平均访存时间=指令所占的百分比×(读命中时间+读失效率×失效开销)+ 数据所占的百分比×(数据命中时间+数据失效率×失效开销)
所以,两种结构的平均访存时间分别为:
分离Cache的平均访存时间=75%×(1+0.15%×50)+25%×(1+3.77%×50)
=(75%×1.075)+(25%×2.885)=1.5275
混合Cache的平均访存时间=75%×(1+0.95%×50)+25%×(1+1+0.95%×50)
=(75%×1.475)+(25%×2.475)=1.725
因此,尽管分离Cache的实际失效率比混合Cache的高,但其平均访存时间反而较低。
分离Cache提供了两个端口,消除了结构相关。
5.11 给定以下的假设,试计算直接映象Cache和两路组相联Cache的平均访问时间以
及CPU的性能。由计算结果能得出什么结论?
(1) 理想Cache情况下的CPI为2.0,时钟周期为2ns,平均每条指令访存1.2次;
(2) 两者Cache容量均为64KB,块大小都是32字节;
(3) 组相联Cache中的多路选择器使CPU的时钟周期增加了10%;
(4) 这两种Cache的失效开销都是80ns;
(5) 命中时间为1个时钟周期;
(6) 64KB直接映象Cache的失效率为1.4%,64KB两路组相联Cache的失效率为
1.0%。
解: 平均访问时间=命中时间+失效率×失效开销
平均访问时间1-路=2.0 1.4% *80=3.12ns
平均访问时间2-路=2.0*(1 10%) 1.0% *80=3.0ns
两路组相联的平均访问时间比较低
CPUtime=(CPU执行 存储等待周期)*时钟周期
CPU time=IC(CPI执行 总失效次数/指令总数*失效开销) *时钟周期
=IC((CPI执行*时钟周期) (每条指令的访存次数*失效率*失效开销*时钟周期))
CPU time 1-way=IC(2.0*2 1.2*0.014*80)=5.344IC
CPU time 2-way=IC(2.2*2 1.2*0.01*80)=5.36IC 相对性能比:CPUtime2way
CPUtime1way5.36/5.344=1.003
直接映象cache的访问速度比两路组相联cache要快1.04倍,而两路组相联Cache的平
均性能比直接映象cache要高1.003倍。因此这里选择两路组相联。
5.12 假设一台计算机具有以下特性:
(1) 95%的访存在Cache中命中;
(2) 块大小为两个字,且失效时整个块被调入;
(3) CPU发出访存请求的速率为109字/s;
(4) 25%的访存为写访问;
(5) 存储器的最大流量为109字/s(包括读和写);
(6) 主存每次只能读或写一个字;
(7) 在任何时候,Cache中有30%的块被修改过;
(8) 写失效时,Cache采用按写分配法。
现欲给该计算机增添一台外设,为此首先想知道主存的频带已用了多少。试对于以下两种情况计算主存频带的平均使用比例。
(1) 写直达Cache;
(2) 写回法Cache。
解:采用按写分配
(1)写直达cache访问命中,有两种情况:
读命中,不访问主存;
写命中,更新cache和主存,访问主存一次。
访问失效,有两种情况:
读失效,将主存中的块调入cache中,访问主存两次;
写失效,将要写的块调入cache,访问主存两次,再将修改的数据写入cache
一次访存请求最后真正的平均访存次数=(71.3%*0) (23.8%*1) (3.8%*2) (1.3%*3)=0.35
已用带宽=0.35×109/10 9 =35.0%
(2)写回法cache访问命中,有两种情况:
读命中,不访问主存;
写命中,不访问主存。采用写回法,只有当修改的cache块被换出时,才写
入主存;
访问失效,有一个块将被换出,这也有两种情况:
如果被替换的块没有修改过,将主存中的块调入cache块中,访问主存两次;
如果被替换的块修改过,则首先将修改的块写入主存,需要访问主存两次;然后将主存中的块调入cache块中,需要访问主存两次,共四次访问主存。
所以:
一次访存请求最后真正的平均访存次数=66.5%*0+28.5%*0 3.5%*2 1.5%*4=0.13
已用带宽=0.13×10 9/10 9=13%
5.12
(1)写直达法:
有5%的访存操作直接访问主存,其中75%为读主存,写直达法无需替换,所以读操作引起的存储器流量为:
5%×75%×2×109=0.075×109(字/s)
有5%的访存操作直接访问主存,其中25%为写主存,写直达法无需替换,所以写操作引起的存储器流量为:
5%×25%×2×109=0.025×109(字/s)
95%的访存操作直接访问cache,读命中无需访问主存,其中25%写操作直接对应主存。所以写操作引起的存储器流量为:
95%×25%×109=0.2375×109 (字/s)
主存频带的利用率为(0.075+0.025+0.2375)=0.3375
(2)写回法:
有5%的访存操作直接访问主存,其中75%为读主存,写回法30%需替换,所以读操作引起的存储器流量为:
5%×75%×(1+30%)×2×109=0.0975×109(字/s)
有5%的访存操作直接访问主存,其中25%为写主存,写回法30%需替换,所以写操作引起的存储器流量为:
5%×25%×(1+30%)×2×109=0.0325×109(字/s)
95%的访存操作直接访问cache,读命中和写命中均无需访问主存。
主存频带的利用率为(0.0975+0.0325)=0.13
5.13 在伪相联中,假设在直接映象位置没有发现匹配,而在另一个位置才找到数据(伪命中)时,不对这两个位置的数据进行交换。这时只需要1个额外的周期。假设失效开销为50个时钟周期,2KB直接映象Cache的失效率为9.8%,2路组相联的失效率为7.6%;128KB直接映象Cache的失效率为1.0%,2路组相联的失效率为0.7%。
(1) 推导出平均访存时间的公式。
(2) 利用(1)中得到的公式,对于2KBCache和128KBCache,计算伪相联的平均访
存时间。
解:
不管作了何种改进,失效开销相同。不管是否交换内容,在同一“伪相联”组中的两块都是用同一个索引得到的,因此失效率相同,即:失效率伪相联=失效率2路。
伪相联cache的命中时间等于直接映象cache的命中时间加上伪相联查找过程中的命中时间*该命中所需的额外开销。
命中时间伪相联=命中时间1路+伪命中率伪相联×1
交换或不交换内容,伪相联的命中率都是由于在第一次失效时,将地址取反,再在第二
次查找带来的。
因此 伪命中率伪相联=命中率2路-命中率1路=(1-失效率2路)-(1-失效率1路)
=失效率1路-失效率2路。交换内容需要增加伪相联的额外开销。
平均访存时间伪相联=命中时间1路+(失效率1路-失效率2路)×1
+失效率2路×失效开销1路
将题设中的数据带入计算,得到:
平均访存时间2Kb=1 (0.098-0.076)*1 (0.076 *50 ) =4.822
平均访存时间128Kb=1 (0.010-0.007)*1 (0.007 *50 ) =1.353
显然是128KB的伪相联Cache要快一些。
5.14 假设采用理想存储器系统时的基本CPI是1.5,主存延迟是40个时钟周期;传输速率为4字节/时钟周期,且Cache中50%的块是修改过的。每个块中有32字节,20%的指令是数据传送指令。并假设没有写缓存,在TLB失效的情况下需要20时钟周期,TLB不会降低Cache命中率。CPU产生指令地址或Cache失效时产生的地址有0.2%没有在TLB中找到。
(1) 在理想TLB情况下,计算均采用写回法16KB直接映象统一Cache、16KB两路组
相联统一Cache和32KB直接映象统一Cache机器的实际CPI;
(2) 在实际TLB情况下,用(1)的结果,计算均采用写回法16KB直接映象统一Cache、
16KB两路组相联统一Cache和32KB直接映象统一Cache机器的实际CPI;
其中假设16KB直接映象统一Cache、16KB两路组相联统一Cache和32KB直接映象统一Cache的失效率分别为2.9%、2.2%和2.0%;25%的访存为写访问。
解: CPI=CPI 执行 存储停顿周期数/指令数
存储停顿由下列原因引起: