复习题_问答题部分New(2).

1、第二早1已知一个求值公式（3A+2B）/（A+5B2+C），若A、B、C已赋值，试画出该公式 求值过程的前趋图。解：令 S1： X1 = 3A;S2: X2 = 2B;S3: X3 = X1+X2;S4： X4 = 5B2;S5: X5 = A+X4+C;S6: X6 = X3/X5则求值过程的前趋图为：SIS2 IS42、已知一个求值公式（B2+AB）/（5B+A），若A、B已赋值，试画出该公式求值过 程的前趋图。解：令 S1： X1 = B2 ；S2： X2 = AB ；S3: X3 = X1 + X2 ；S4： X4 = 5B ；S5: X5 = X4 + A ；S6: X6 = X3

2、/ X5。则求值过程的前趋图为：（自己画出）3、写出实现两个进程单向同步问题的伪码。（参考讲义）3、写出通过信号量实现生产进程和消费进程（单缓冲区）双向同步的伪码。 （参考讲义）解：定义信号量：var生产进程伪码：Process P:beg inwhile(true) dobeg in生产一个产品；P操作，等待可以生产的信号量 将产品放入缓冲区。其他操作sin gal(s2); /V操作，发送可以消费的信号量 endend消费进程伪码：Process C:beg inwhile(true) dobeg in/P操作，等待可以消费的信号量 从缓冲区中取出产品进行消费。/其他操作sin gal(s

3、1); /V操作，发送可以生产的信号量endend4、写出通过信号量实现进程1和进程2互斥访问共享资源(临界资源)的伪 码。(参考讲义)解：定义信号量：访问资源进程1伪码：Process P1:beg in while(true) dobeg in/P操作，申请访问资源权限的的信号量临界区代码；其他访问资源操作/V操作，释放访问资源权限的信号量endend访问资源进程2伪码：(同P1类似)Process P2:beg inwhile(true) dobeg inwait(s); /P操作，申请访问资源权限的的信号量临界区代码；其他访问资源操作sin gal(s); /V操作，释放访问资源权限的

4、信号量endend5、写出具有缓冲池（n个缓冲区）的生产者-消费者问题的伪码。（参考讲义、 教材）6、 写出公共汽车司机和售票员同步问题的伪码。（参考讲义）解：信号量定义var s1,s2:semaphore:=0,0;s1为控制能否行车的信号量s2为控制能否开门的信号量司机进程：Process Driver:beg inwhile（true） dobeg inwait（s1）;加油行车；到站停车；sin gal（s2）;endend售票员进程：Process Con ductor:beg inwhile（true） do beg in关车门；singal（s1）;售票；wait（s2）;开车

5、门；end end7、读者-写者同步问题（参考讲义和教材）第三章1、系统有5个进程，其就绪时刻（指在该时刻已经在就绪队列中就绪）、服务时间 如下表所示。当分别采用先来先服务（FCFS）和短进程优先（SPF）算法时，画出调度 过程，并计算平均周转时间和平均带权周转时间。 （进程就绪时刻服务时间P】02P225P343P466P581iMHUIH始拉汁时闸周料时同幫寂周转时阖pi0*02j1P2rVp35iPS471062P46b10lbw50PSi16IT*期平均周转时间=平均带权周转时间=就绪时剧瞰务时阿HR龙成时闸周转时屈时何PI020221P225751Pi47106EM66HH11/6亦

6、&jH)113进程列达时刻运行时间Pl05p:11Pj22P431巴43平均周转时间=平均带权周转时间=解：进程执行过程如下：P1P2P3P4P5时间：平均周转时间：(11+1+6+2+8)/5 = 5.6平均带权周转时间：(11/5+1/1+6/2+2/1+8 /52.173、系统中有5个进程，每个进程的运行时间、优先级和到达时刻如下表所示。若米用抢占式优先级调度算法(优先级越大越优先执行)进程到达时刻运行时间优先级Pl154p2116222P433斗35进程量大需求已分配P1105P242P3924、假定系统中有三个进程 P1、P2和P3,共有12台磁带机。进程P1总共要求 10台磁带机，

7、P2和P3分别要求4台和9台。假设在TO时刻，进程P1、P2和P3 已分别获得5台、2台和2台磁带机，如下表所示：(1) 该状态是否是安全状态？请说明理由。解：TO时刻，系统是处于安全状态，因为此时的空闲磁带机资源为3,存在一个安全序列P2、P1、P3,即只要系统按此进程序列分配磁带机资源，就能够使三 个进程都顺利完成。（为什么？）（2）若到达一新进程P4，请求1台磁带机，其最大需求为4台，是否可以分配？ 请说明理由。（参考P108）解：可以进行资源分配。因为将1台磁带机分配给P4后，尚有2台空闲磁带 机，存在一个安全序列P2、P4、P1、P3，即只有系统按此进程序列分配磁带机 资源，就能够使

8、四个进程都顺利完成。（为什么？）5、设系统中有人资淞謚求址已汕配幻源敗董冉CAc卩592i23种类型的资源（A，B，C）和5个进程P1、P2、P3、P4、P5, A资源的数量为17, B资源的数量为5, C资源的数量为20,在T0时刻系统状态如下表所示。系 统米用银行家算法实施死锁避免策略。（参考P110）53b40Ti4UIII4U5Pl4A54Pi4I3114罰余番踊AHCj313（1）T0时刻是否为安全状态？若是，请给出安全序列;最大资源需求量己分配瓷源数量、哉M资源需求量A；cABCABcPl559hi1234sPj5364UJ 134 |4V114U500 6p442520422ri

9、tei424314Io |剰余瓷Alic源数233T0时刻是安全状态。存在安全序列P4、P2、P3、P5、P1（为什么？能否找出其他安全序列？）若在T0时刻进程P2请求资源（0, 3, 4）,是否能实施资源分配？为什么？解：若在TO时刻进程P2请求资源(0, 3, 4),不能实施资源分配。因为请求资源数(0, 3, 4)可用资源数(2, 3, 3)不成立，没有足够资源。在(1)的基础上，若进程P4请求资源(2, 0, 1)，Meed IS薄需求虽ABcABcBchS59器1工p.536402p*40114050典4254H5O14A1141QA0y7是否能实施资源解：可以实施分配，因为分配后有

10、安全序列：(为什么？能否找出其他安全序列？),即分配后的状态是安全的。6、假定系统中有三个进程 P1、P2和P3,共有12台磁带机。进程P1总共要求 10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3 已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：(参考 教材P108)进程最大需求已分配可用r pi 11()53P24P391(1) T0时刻是否为安全状态？若是，请给出安全序列；在T0时刻P3申请一台磁带机，请问能否实施资源分配，为什么? 解：参考教材7、理解FCFS和SJF作业调度算法思想。业闊艮、进IV耕ACE均列达时阿0134435迄4F

11、CFS(a)41214IN隔转时河46In11E419帯权网转时Ml125,53.52.8SJF尢诫时问49洛6134H163V;ET均01234时M /广、IM符时側43s24U n1210iII174jr= |112y8IJ11.633? 24125UlKR id - JL知k柏;帀i i17i61&10139.1S3-152M9、通过上课所讲示例理解 EDF （最早截止时间优先）算法和 LLF（最低松弛度优 先）算法思想。第四章1某系统采用动态分区分配方式管理内存，内存空间为640KB，高端40KB用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请 求序列：作业1申

12、请130KB，作业2申请60KB，作业3申请100KB，作业2释 放60KB，作业4申请200KB，作业3释放100KB，作业1释放130KB，作业5 申请140KB，作业6申请60KB，作业7申请50KB，作业6释放60KB，请分别 画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后，内存的实 际使用情况。（参考教材和讲义）解：参考教材、讲义和下题方法2.某操作系统采用分区存储管理技术。操作系统在低地址占用了100KB的空间,用户区主存从100KB处开始占用512KB。初始时，用户区全部为空闲，分配时 截取空闲分区的低地址部分作为已分配区。在执行以下申请、释放操作序列后：请求300

13、KB;请求100KB;释放300KB;请求150KB;请求50KB;请求 90KB，进行以下回答：（1）分别采用首次适应算法和最佳适应算法时，主存的实际使用情况如何？分别 画出主存分布图，并指出空闲分区的首地址和大小；（2）若随后又要请求80KB，针对上述两种情况产生什么后果？说明了什么问题？ （参考教材和讲义）（1）采用首次适应算法时，主存分布图如下图ISCIKB(已井 HO90KB(已分配EKB；询|KJGKBre 分的lUKBf空闲)空闲区1:首地址390KB，大小10KB ;空闲区2:首地址500KB，大小112KB;(2) 采用最佳适应算法时，主存分布图如下图空闲区1:首地址340K

14、B，大小60KB ；空闲区2:首地址550KB，大小62KB ；(3) 若随后又要请求分配80KB，首次适应算法可顺利分配，而最佳适应算法不 能。说明首次适应算法可在高址端保留大分区。3、某分页系统的逻辑地址为16位，其中高6位为页号，低10位为页内偏移量，则在这样的地址结构中：(1) 一页有多少个字节？(2) 逻辑地址可有多少页？(3) 一个进程最大的逻辑地址空间是多少 KB ?(参考P130)解：210 = 1024因此一页有1024字节26 = 64因此逻辑地址可有64页216 = 64KB因此一个进程最大的逻辑地址空间是64KB4、 某系统采用页式存储管理策略，拥有逻辑空间32页，每页

15、为2KB，拥有物理 空间1MB。(1) 写出逻辑地址的格式。解：11位页内地址，5位页号(2) 若不考虑访冋权限等，进程的页表最多有多少项？每项至少有多少位？解：因为有32个逻辑页面，所以页表有32项。因为有1M/2K= 2的9次方物理 块，所以每个页表项至少有 9位(3) 如果物理空间减少一半，页表结构应相应作怎样的改变？解：32项，每项至少需要8位5、 对于如下表所示的段表，请将逻辑地址(0,137), (1,4000), (2,3600),段号内存始址段艮050K10KB160K3KB270K5KB3120K8KB4150K4KB解：(0,137)对应的物理地址为：50K+137 = 5

16、0*1024+137 = 51337;(1,4000)的段内偏移地址越界，是一个不合法逻辑地址；(2,3600)对应的物理地址为：70K+3600 = 75280(5,230)的段号越界，是一个不合法逻辑地址。6、在一个请求分页系统中，假如一个作业的页面走向为4, 3, 2，1, 4, 3, 5,4，3, 2, l, 5, 目前它还没有任何页装入内存，当分配给该作业的物理块数目M分别为3和4时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时访问过 程中所发生的缺页次数和缺页率，并比较所得的结果。解：请参照讲义画出调页过程，7、系统为某进程分配了三个物理块，页面访问顺序为：7, 0, 1,

17、 2, 0, 3, 0,4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1,试问采用 OPT、FIFO、LRU 置换算 法时会产生多少次缺页中断？（假定初始时所有页面均未装入内存；请画出置换过 程）解：参照讲义8在某个分页管理系统中，某一个进程有 4个页面，被分别装入到主存的第 3、 4、6、8块中，假定页面和块大小均为1024字节，当进程在CPU上运行时，执 行到一条传送指令：MOV 2100, 3100请计算出MOV指令中两个操作数（逻辑地址）的物理地址。解：2100 / 1024 = 2第 2页放在第6块中2100 % 1024 = 526X1024 + 52 =

18、 6196因此第一个操作数的物理地址为 6196。3100 / 1024 = 3第3页放在第8块中3100 % 1024 =288X1024 + 28 = 8220因此第二个操作数的物理地址为 8220。9、已知某分页系统，主存容量为 64KB，页面大小为1KB。对于一个4页大的作 业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地 址1023、2500、3500、4500转换成物理地址。（参考讲义）解：逻辑地址1023的页号和页内偏移地址分别为：1023/1024 = 0, 1023%1024 = 1023所以其的物理地址为：2*1024+1023 = 3041逻辑

19、地址2500的页号和页内偏移地址分别为：2500/1024 = 2, 2500%1024 = 452所以其的物理地址为：6*1024+452 = 6596逻辑地址45004*1024-1,所以不是一个合法地址。第五章1、试说明spooling系统的组成和工作原理。（参考讲义和教材）2、磁盘请求以15、32、25、5、60、10、48磁道的序列到达磁盘驱动器。寻道 时移动一个磁道需要8ms,当分别采用FCFS算法、最短寻道时间优先算法、SCAN算法、CSCAN算法时，磁道的访问顺序是怎样的？平均寻道时间是多 少？假设磁头的起始位置位于磁道 18,朝大磁道号方向移动。（参考讲义）从18号磁道开始磁

20、道访问顺序移动距离(磁道数)1533217257520605510504838平均寻道时间为：(3+17+7+20+55+50+38)/7*8二?从18号磁逍开始磁道访问顺序移动距离(磁道数)15310555251032748126012平均寻道时间为：(3+5+5+10+7+12+12)/7*8二?:从18号磁道开始磁道访问顺序移动距离（磁道数）25732748126012154510555从18号磁道开始施道访问顺序移动距离（磁道数）257327平均寻道时间为：（7+7+12+12+45+5+）/7*8= ?48126012555105155平均寻道时间为：（7+7+12+12+55+5+

21、）/7*8= ?3、磁盘请求以20、44、40、4、80、12、76磁道的序列到达磁盘驱动器。寻道 时移动一个磁道需要3ms,当采用SCAN算法时，磁道的访问顺序是怎样的？平 均寻道时间是多少？假设磁头的起始位置位于磁道 40,磁头向小磁道方向移动。（参考讲义）4、磁盘请求以20、44、40、4、80、12、76磁道的序列到达磁盘驱动器。寻道 时移动一个磁道需要3ms，当采用CSCAN算法时，磁道的访问顺序是怎样的？ 平均寻道时间是多少？假设磁臂的起始位置位于磁道 40,磁头向大磁道方向移 动。（参考讲义）5、假设磁盘访问序列:98, 183, 37, 122, 14, 124, 65, 67读写头起始位置：53（1）安排磁头服务序列（2）计算磁头移动总距离（道数）（参考讲义） 第六章1、 存放在某个磁盘上的文件系统采用混合索引分配方式，其FCB中共有13个地址项，第09个地址项为直接地址，第10个地址项为一次间接地址，第11个地 址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为 512字节，若盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址，则该文件系统允许文件的最大长度是多少？（参考教材和下题）2、有某操作系统对外存分配采用混合索引分配方式，在索引节点中包含文件的 物理结构数组iaddr13，其中前10项