1.10n某计算机有个四阶段的管线。每个阶段完成其工作时间都是一样的，即1 nsec。该计算机每秒钟可以处理多少条指令？ 答：从管道中每纳秒出现一条指令。意味着该机器每秒执行109条指令。它和管道有多少个阶段没有关系。即使是10-阶段管道，每阶段1 nsec，也将是每秒执行109条指令。1.20n某文件的描述符为fd，包含如下的字节：3,1,4,1,5,9,2,6,执行下列系统调用lseek(fd,3,SEEK_SET);read(fd,&buffer,4);其中lseek定位到文件的字节3，则当read完成后，buffer中包含什么内容？答：包含1,5,9,21.26下面单位转换的练习：n一微年是多少秒？ 31.536sngigamicron是多长？1000mn1TB存储器中有多少字节？240Bn地球质量6000yottagram，换算成kilogram是多少？6*1024kg 2.1n图2-2所示为进程的三种状态和四种状态间转换，另两种转换是否可以想象答：从阻塞到运行的转换是可以想象的，如某进程在I/O上阻塞，若I/O结束时，CPU空闲，则此进程可以从阻塞态直接到运行态；而从就绪态到阻塞态是不可想象的，因为就绪态进程是不会做任何能引起阻塞的事情的，只有运行进程才可能被阻塞。2.22答：enter_region:MOVE REG, #1ECHG REG,LOCKCMP REG, #0JNE enter_regionRET2.38n2.38答：CPU利用率是：有用CPU时间/整个CPU时间n(a)和(b)：Q=T，进程运行T，然后切换S，利用率是：T/(T+S)n(c)：进程每运行T，需进行T/Q次切换，共需切换时间是S*(T/Q)，因此利用率为：T/(T+S*(T/Q)，即Q/(Q+S)n(d):同上，Q/(Q+S)，以S代替Q，即50%n(e):同上，Q/(Q+S)，Q趋于0，利用率趋近于02.40 进程调度进程： A、B、C、D、E运行时间：10、6、2、4、8优先级：3、5、2、1、4n轮转法：n在10分钟里，每个进程占用2分钟，第10分钟C结束，即C的周转时间是10n接下来的8分钟，每个进程占用2分，第18分钟D结束，即D的周转时间是18n接下来的6分钟，每个进程占用2分，第24分钟B结束，即B的周转时间是24n接下来的4分钟，每个进程占用2分，第28分钟E结束，即E的周转时间是28n最后A再运行2分钟结束，即A的周转时间是30平均周转时间是：（10+18+24+28+30）/5=222.40 进程调度n优先级法按照B、E、A、C、D顺序执行，则nB在第6分结束，周转时间是6nE在第6+8分结束，周转时间是14nA在第6+8+10分结束，周转时间是24nC在第6+8+10+2分结束，周转时间是26nD在第6+8+10+2+4分结束，周转时间是30平均周转时间是：(6+14+24+26+30)/5=202.40 进程调度n先来先服务按照A、B、C、D、E顺序执行，则nA在第10分结束，周转时间是10nB在10+6分结束，周转时间是16nC在10+6+2分结束，周转时间是18nD在第10+6+2+4分结束，周转时间是22nE在第10+6+2+4+8分结束，周转时间是30平均周转时间是：(10+16+18+22+30)/5=19.22.40 进程调度n最短作业优先按照C、D、 B、 E、 A顺序执行，则nC在第2分结束，周转时间是2nD在2+4分结束，周转时间是6nB在2+4+6分结束，周转时间是12nE在第2+4+6+8分结束，周转时间是20nA在第2+4+6+8+10分结束，周转时间是30平均周转时间是：(2+6+12+20+30)/5=142.41n在CTSS系统中，若某进程需运行30个时间片，那它将需要多少次换入（包括第一次）答：CTSS系统中，每个进程在换入时将依此获得1、2、4、8、16。个时间片。因此，此进程将依此获得1、2、4、8、16(15)个时间片，需要经过5次交换2.43n老化算法下一次预测时间是：(40/2+20/2)/2+40/2)/2+15/2=40/8+20/8+40/4+15/2=252.44n某个软实时系统有4个周期性事件，它们周期分别是50ms,100ms,200ms, 250ms，占用CPU时间分别是35，20，10，x ms，则使得系统可调度的最大x是多少？答：实时系统可调度的条件是：(35/50+20/100+10/200+x/250)=1，即x=12.5ms2.50/正在浴室或准备进入浴室的女生数int woman_num=0; /正在浴室或准备进入浴室的男生数int man_num=0;/控制对woman_num的访问semaphore wn_mutex=1;/控制对man_num的访问semaphore mn_mutex=1;semaphore bath=1; /控制对浴室的使用2.50void woman_want_to_enter()down(&wn_mutex);woman_num+;if(woman_num=1) down(&bath);up(&wn_mutex);void woman_leaves()down(&wn_mutex);woman_num-;if(woman_num=0) up(&bath);up(&wn_mutex);2.50void man_want_to_enter()down(&mn_mutex);man_num+;if(man_num=1) down(&bath);up(&mn_mutex);void man_leaves()down(&mn_mutex);man_num-;if(man_num=0) up(&bath);up(&mn_mutex);3.13(1)原状态:若D请求1个单元，状态变为： 已有 最大A16A16B15B15C24C24D47D57 剩余2剩余1（由此状态出发检查是否存在一个分配序列使得所有进程都能完成）因为此状态只剩余1个资源，不能满足A、B、C、D任何一个进程的需要，所有进程都不能完成，系统将会死锁。所以若D多请求1个单元，会引起不安全状态。3.13(2)原状态:若C请求1个单元，状态变为： 已有 最大A16A16B15B15C24C34D47D47 剩余2剩余1（由此状态出发检查是否存在一个分配序列使得所有进程都能完成）3.13(2)A 16A 16A 16A 16B 15B 15B 15B 15C 34C 44C 0-C 0-D 47D 47D 47D 77 剩余1 剩余0剩余4 剩余1A 16A 16A 16A 66B 15B 55B 0-B 0-C 0-C 0-C 0-C 0-D 0-D 0-D 0-D 0- 剩余8 剩余4剩余9 剩余4 因为从此状态出发，存在一个分配序列C、D、B、A，使所有进程都能完成，因此C多请求1个单元会引起安全状态。3.17若A请求最后1台磁带驱动器，则状态变为分配矩阵C申请矩阵R AvailableA 4 0 1 1 0 1 0 0 0 0 2 0B 0 1 0 0 0 1 1 2 C 1 1 1 0 3 1 0 0D 1 1 0 1 0 0 1 0E 0 0 0 0 2 1 1 0分析从此状态出发是否存在一个分配序列使所有进程都可以完成。 3.17根据银行家算法分析：1.找到RD(0 0 1 0)A(0 0 2 0)，标记D，并把CD加到A上，即A=(0 0 2 0)+(1 1 0 1)=(1 1 2 1)（表示先分配给D所需要的A=A-RD，D完成后释放其全部资源A=A+(RD+CD)）2.找到RA(0 1 0 0)A(1 1 2 1)，标记A，并把CA加到A上，即A=(1 1 2 1)+(4 0 1 1)=(5 1 3 2)3.找到RB(0 1 1 2)A(5 1 3 2)，标记B，并把CB加到A上，即A=(5 1 3 2)+(0 1 0 0)=(5 2 3 2)4.找到RC(3 1 0 0)A(5 2 3 2)，标记C，并把CC加到A上，即A=(5 2 3 2)+(1 1 1 0)=(6 3 4 2)5.找到RE(2 1 1 0)=P*1+1 即P=P*2+1即P=p*(m-1)+13.20n已分配矩阵： 需求矩阵A 1 0 2 1 10 1 0 0 2B 2 0 1 1 10 2 1 0 0 剩余向量C 1 1 0 1 01 0 3 0 0 0 0 x 1 1D 1 1 1 1 00 0 1 1 1答：可以看出，x=1时，D可以完成，剩余向量变为1 1 2 2 1；此时将死锁。如果x=2, 则剩余向量为1 1 3 2 1，C可以完成，剩余向量变为2 2 3 3 1；然后可以满足B后，剩余向量变为4 2 4 4 2又可以满足A，所有进程可满足，是安全状态。即要求x=23.22n两个进程A 和B，每个都需要某个数据库中的3 个记录1，2 和3。如果A 按照1, 2, 3的次序请求，而B 按相同的顺序请求，是不会死锁的。然而，如果B 按3, 2, 1 的次序请求，那么就可能死锁。对于3 个资源，每个进程请求资源都有6 种可能的组合。哪些组合可以保证不出现死锁?答：假设进程A 要求按1, 2, 3 申请记录。如果进程B 同样先请求1，其中某个进程将得到它，而另一个将被阻塞。这种情形不会造成死锁，因为，获得记录1 的进程现在没有干扰而运行结束。在其余几种组合中，某些可能导致死锁而某些不会死锁。6 种情况如下进程A进程B1 2 31 2 3不会死锁1 2 31 3 2不会死锁1 2 32 1 3可能死锁1 2 32 3 1可能死锁1 2 33 1 2可能死锁1 2 33 2 1可能死锁因为6 种组合中有4 个可能导致死锁，因此有1/3 机会避免死锁，2/3 机会可能死锁。4.2n图4-21 中，例示了多个作业可以并行运行，而且比顺序运行更快完成。假设有2 个作业同时开始，每个都需要10 分钟CPU 时间。如果顺序运行，最后一个需要多久才能完成? 如果是并行需要多久?假设I/O 等待时间为50%。答：答：n如果每个作业都有50%的I/O 等待，那么没有竞争的情况下，需要花费20 分钟完成。如果顺序运行，第二个将在第40 分钟完成。n对于2 个作业并行运行，CPU 近似利用率为1 0.52=0.75。因此，每一分钟每个作业获得0.75/2=0.375 分钟CPU 时间。为了获得10 分钟CPU 时间，每个作业必须运行10/0.375 分钟，大约为26.67 分钟。所以并行在26.67 分钟之后两个作业都完成。4.4n比较使用位映像和使用链表来记录空闲内存之间的区别。128-MB（227B） 内存被划分成n 字节的单元。对于链表，假定内存由64KB（216B）大小的碎片和空洞交替组成。同时假定链表中每个节点需要一个32 位的内存地址，16 位的长度，以及16 位的next 域。那么每种方法各需要多少字节? 哪一种更好?4.4答:n位映像每个分配单元需要1 位。对于227/n 个分配单元，需要227/n 比特= 224/n字节。n链表总共有227/216= 211 个节点，每个节点占用(32+16+16)位共8 字节，也就是总共211*8=214 字节。n当224/n 214时(即n210)，链表较好。当224/n210) ，位映像较好。n 为1 K 时，两者相等。 4.5按地址排列的空闲区大小依次是10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。对于连续的段请求12KB，10KB，9KB答:n首次适配算法：20KB、10KB、18KBn下次适配算法：20KB、18KB、9KBn最佳适配算法：12KB、10KB、9KBn最差适配算法：20KB、18KB、15KB 4.7n20000n4KB页面: （二进制和十进制两种方法）n20000：100 111000100000页号：100； 页内偏移：111000100000n20000/4096页号(商)： 4； 页内偏移（余数）：3616n8KB页面 n页号：10； 页内偏移：111000100000n页号：2；页内偏移：36164.7n32768n4KB页面: （二进制和十进制两种方法）n32768：1000 000000000000页号：1000； 页内偏移：0 n32768/4096页号(商)： 8； 页内偏移（余数）：0n8KB页面 n页号：100； 页内偏移：0n页号：4；页内偏移：04.7n60000n4KB页面: （二进制和十进制两种方法）n60000：1110 101001100000页号：1110； 页内偏移：101001100000 n60000/4096页号(商)：14；页内偏移（余数）：2656n8KB页面 n页号：111； 页内偏移：101001100000n页号：7；页内偏移：26564.8 指出对应于下列虚拟地址的物理地址n20n(20)10=(0000|000000010100)2虚页号：0 查找页表 映射到页框2页内偏移：000000010100物理地址：页框号+页内偏移，即 (0010 000000010100)2或(8212)10n20/4K 即20/4096 商：0虚页号 查找页表 映射到页框2余数：20页内偏移物理地址：2*4K+20=2*4096+20=(8212)104.8 指出对应于下列虚拟地址的物理地址n4100n(4100)10=(0001|000000000100)2虚页号：1 查找页表 映射到页框1页内偏移：000000000100物理地址：页框号+页内偏移，即 (0001 000000000100)2或(4100)10n4100/4K 即4100/4096 商：1虚页号 查找页表 映射到页框1余数：4页内偏移物理地址：1*4K+20=1*4096+4=(4100)104.8 指出对应于下列虚拟地址的物理地址n8300n(8300)10=(0010|000001101100)2虚页号：2 查找页表 映射到页框6页内偏移：000001101100物理地址：页框号+页内偏移，即 (0110 000001101100)2或(24684)10n8300/4K 即8300/4096 商：2虚页号 查找页表 映射到页框6余数：108页内偏移物理地址：6*4K+108=6*4096+108=(24684)104.11n如果一条指令需10nsec，而一个缺页还需另加n nsec，假设每k 条指令发生一次缺页，给出计算有效指令时间的公式。答:每k 条指令发生一次缺页，即需另加n nsec，因此每执行K条指令所需时间为:(10k+n) nsec，即平均的指令时间为(10k+n)/k=(10 + n/k) nsec。 4.12n某机器有32-位的地址空间和8-KB (213B)的页。页表完全在硬件中，当一个进程开始时，该页表从内存复制到硬件中，复制每页表项需100 nsec。如果每个进程运行100 msec(包括载入页表的时间)，那么CPU花费在载入页表的时间为多少?答:该页表包含232/213=219 项。装载该页表需219*100ns=52ms。如果某进程运行100ms，其中载入页表为52 ms，实际运行时间为48 msec。因此，52%的CPU时间用于载入页表。4.23页面访问顺序 0 1 7 2 3 2 7 1 0 3 0000333333111111100777777772222222FIFO算法6次缺页 LRU7次缺页000033330011111111177777777 22222234.23页面访问顺序 0 1 7 2 3 2 7 1 0 3 2 3 4 5 5 017232710301723271001773271 0111327000032LRU算法6次缺页 4.25n第一个时钟周期时每页的R位是页0123R位 0111计数器0: 00000000计数器1: 10000000计数器2: 10000000计数器3: 100000004.25n第二个时钟周期时每页的R位是页0123R位 1011计数器0: 10000000计数器1: 01000000计数器2: 11000000计数器3: 110000004.25n第三个时钟周期时每页的R位是页0123R位 1010计数器0: 11000000计数器1: 00100000计数器2: 11100000计数器3: 011000004.25n第四个时钟周期时每页的R位是页0123R位 1101计数器0: 11100000计数器1: 10010000计数器2: 01110000计数器3: 101100004.25n第五个时钟周期时每页的R位是页0123R位 0010计数器0: 01110000计数器1: 01001000计数器2: 10111000计数器3: 010110004.25n第六个时钟周期时每页的R位是页0123R位 1010计数器0: 10111000计数器1: 00100100计数器2: 11011100计数器3: 001011004.25n第七个时钟周期时每页的R位是页0123R位 1100计数器0: 11011100计数器1: 10010010计数器2: 01101110计数器3: 000101104.25n第八个时钟周期时每页的R位是页0123R位 0001计数器0: 01101110计数器1: 01001001计数器2: 00110111计数器3: 100010114.29页 装入时间 上次访问时间 R M0126280 1 01230265 0 12140270 0 03110285 1 1nNRU将替换页2（因为RM=00,编号最小，表示页2最近未被访问且未被修改）nFIFO将替换页3（因为装入时间最早）nLRU将替换页1（因为上次访问时间最早，即最久未访问）n第二次机会将替换页0按装入时间排序的链表：3 R=10 R=12 R=01 R=0检查表头页面，若R=1，则：0 R=12 R=01 R=0 3 R=0继续检查表头页面，直至R=0，所以选择页24.31n某计算机给每个过程提供65,536 个字节的地址空间，每页4096 字节。某程序正文为32,768 字节，数据大小为16,386 字节以及15,870 字节的堆栈。该程序可以放入该地址中吗?如果页大小为512 字节呢? （一页不可能包含两个不同段的部分。）答:进程地址空间65536/4096=16页。而此程序正文需32768/4096=8 页，数据需16386/4096 =5页 ，堆栈需15870/4096 =4 页，共需17页，该程序无法放入。而对于512-字节的页，进程地址空间65536/512=128页。此程序正文64 页，数据33 页，而堆栈31 页，总共128 页，刚好。4.37n解释内部碎片和外部碎片之间的区别。哪一种在分页系统中发生? 哪一种在纯分段的系统中发生?答:当最后的分配单元不满时，就产生了内部碎片。而外部碎片是指两个分配单元之间被浪费的空间。在分页系统中，最后一页丢失的空间为内部碎片。在纯分段系统中，段之间的某些空间是不可用的，这是外部碎片。5.9n什么是“设备无关性”?答:设备无关性是指以相同的方法访问文件和设备，而与其物理特性无关。如果系统采用一组调用写文件，而使用另一组调用写控制台(终端)，那么就不具有设备无关性。5.10n下列操作分别在4 个I/O 软件层的哪一层完成：n为一个磁盘读操作计算磁道、扇区和磁头设备驱动程序n向设备寄存器写入命令设备驱动程序n检查用户是否有权允许使用设备与设备无关的操作系统软件n二进制整数转换为ASCII 码以便打印用户层软件5.14n对于7200-rpm 的磁盘，相邻寻道时间为1 ms，其柱面倾斜为多少? 设该磁盘每个磁道有200 个扇区。答:l该磁盘旋转速率为7200rpm，因此每旋转一周时间T1=60*1000/7200=100/12 ms。n磁盘每道200 个扇区，则每个扇区在磁头下通过时间T2=T1/200 = 100/(12*200)= 1/24 ms。n寻道时间T3=1ms，则在寻道期间将有T3/T2=24个扇区通过，因此柱面倾斜应该为24。5.24nFCFS服务顺序：(20)102220240638磁臂移动的柱面数：1012218383432 146寻道时间：146*6=876msnSSF服务顺序：(20)202210623840磁臂移动的柱面数：021244362 60寻道时间：60*6=360msn电梯算法服务顺序(初始向上)：(20)202238401062磁臂移动的柱面数：021623044 58寻道时间：58*6=348ms5.27n某计算机的中断处理程序每个时钟计时需2ms (包括进程切换的耗时)。若时钟频率为60Hz，则该CPU 用于时钟处理的比率为多少?答:每秒发生60次中断，共占用CPU时间60*2= 120ms，则CPU用于时钟处理的比率为120ms/1000ms=12%6.11n当前工作目录是/usr/jim，则相对路径是./ast/x的文件的绝对路径是什么?答:/usr/ast/x6.12n文件的连续分配会导致磁盘碎片，而当一个文件的长度不等于块的整数倍时，文件中的最后一个磁盘块中的空间会浪费掉。请问这是内碎片还是外碎片?答:连续分配导致的是外碎片，类似于交换系统中的外碎片；而文件中最后一个磁盘块中浪费的空间属于内碎片，类似于分页系统中的页内碎片。6.21设磁盘地址D位，一个磁盘有B块，其中F块空闲，在什么条件下，空闲表采用空间少于位图？n 空闲表需要的空间：F*D比特 位图需要的空间：B比特所以，当FDB时，适合于使用空闲表n 空闲磁盘比应是F/B。由FDB (F/B)(1/D)，即空闲磁盘比应小于1/16（6.25%）6.22n磁盘分区在格式化之后，磁盘空间的位映像的开始部分为：1000000000000000(第一块用于根目录)。系统总是从头开始搜索空闲块，那么在写入长度为6块的文件A 之后，位映像为：1111111000000000。那么在下列操作之后，每次的位映像是什么：n(a) 写入5个块的文件Bn(b) 删除文件An(c) 写入8个块的文件Cn(d) 删除文件B答: 位映像为：na) 写入文件B 后：1111 1111 1111 0000nb) 删除文件A 后：1000 0001 1111 0000nc) 写入文件C 后：1111 1111 1111 1100nd) 删除文件B 后：1111 1110 0000 11006.31n磁盘的平均寻道时间为8毫秒，旋转速率为15000rpm，每条磁道为262144字节。那么对于1KB，2 KB 和4KB 的块大小，其数据速率分别为多少?答: 对于15000rpm，每旋转一周需60s /15000=4 ms。那么，读取k 字节的平均存取时间为8(寻道时间) + 2(旋转半周的时间) + (k/262144) * 4(读取k 字节的时间) ms。n对于1 KB，访问时间为8+2+1K/262144*4=10.015625 ms，其数据速率为1KB/10.015625ms=102240 B/sec=8.2*105bpsn对于2 KB，访问时间为8+2+2K/262144*4=10.03125 ms，其数据速率为2KB/10.03125ms=204162 B/sec=1.6*106bpsn4 KB 的块，访问时间为8+2+4K/262144*4=10.0625 ms，其数据速率为4KB/10.0625ms=407056 B/sec=3.3*106bps6.37n读取文件/usr/ast/courses/os/handout.t 的i-节点需要多少次磁盘操作?假设根目录的i-节点在内存中，不过其他节点都不在。同时还假设所有目录都在一个磁盘块中。答: 需要下列的磁盘操作：读根目录读/usr 的i-节点读/usr 的目录读/usr/ast 的i-节点读/usr/ast 的目录读/usr/ast/courses 的i-节点读/usr/ast/courses 的目录读/usr/ast/courses/os 的i-节点读/usr/ast/courses/os 的目录读/usr/ast/courses/os/handout.t 的i-节点总共10 个磁盘读操作。_