操作系统课后题-课后作业-第三次作业

7.6.如果使用动态分区方案，下图所示为在某个给定的时间点的内存配置：阴影部分为已经被分配的块；空白部分为空闲块。接下来的三个内存需求分别为40MB，20MB和10MB。分别使用如下几种放置算法，指出给这三个需求分配的块的起始地址。a.首次适配b.最佳适配c.临近适配（假设最近添加的块位于内存的开始）d.最坏适配答：a.40M的块放入第2个洞中,起始地址是80M.20M的块放入第一个洞中.起始地址是20M.10M的块的起始地址是120M。b.40M,20N,10M的起始地址分别为230M,20M和160M.c.40M,20M,10M的起始地址是80M,120160M.d.40M,20M,10M,的起始地址是80M,230M,360M.7.8.考虑一个伙伴系统，在当前分配下的一个特定块地址为011011110000.a.如果块大小为4，它的伙伴的二进制地址为多少？b.如果块大小为16，它的伙伴的二进制地址为多少？答：a.011011110100b.0110111000007.14.在一个简单分段系统中，包含如下段表：起始地址长度（字节）6602481752442222198996604对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生：a.0，198b.2，256c.1，530d.3，444e.0，222答：a.段0定位在660,所以我们有物理地址660+190=858.b.222+156=378c.段1长度为422,所以会发生错误d.996+444=1440e.660+222=882.8.1假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从0开始记数的，并且所有的地址都是内存字节地址。页尺寸为1024个字节。虚拟页号有效位访问位修改位页帧号01104111172000—310024000—51010a．描述CPU产生的虚拟地址通常是如何转化成一个物理主存地址的。b．下列虚拟地址对应于哪个物理地址（不用考略页错误）？（i）1052（ii）2221（iii）5499解答a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到物理地址b:(i)1052=1024+28查表对应的页帧号是7，因此物理地址为7*1024+28=7196(ii)2221=2*1024+173此时出现页错误(iii)5499=5*1024+379对应的页帧号为0因此物理地址是3798.2考虑一个使用32位的地址和1KB大小的页的分页虚拟内存系统。每个页表项需要32位。需要限制页表的大小为一个页。a．页表一共需要使用几级？b．每一级页表的大小是多少？提示：一个页表的大小比较小。c．在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页？解答a：虚拟内存可以分为232/210=222页，所以需要22个bit来区别虚拟内存中的一页，每一个页表可以包含210/4=28项，因此每个页表可以包含22bit中的8个bit，所以需要三级索引。b：第二级页表有28个页表项，第一级页表有26个页表项。c：如果顶层有26个页表项将会减少使用空间，在这种情况下，中间层页表有26个并且每个都有28个页表项，底层有214个页并且每个都有28个页表项，因此共有1+26+214页=16,449页。如果中间层有26个页表项，那么总的页数有1+28+214页=16,641页。如果底层有26个页表项，那么总的页表数是1+28+216页=65,973页。8.4一个进程分配给4个页帧（下面的所有数字均为十进制数，每一项都是从0开始计数的）。上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟时间，而不是从事件发生到当前的时钟值）。虚拟页号页帧加载时间访问时间R位M位2060161011113016010022616210332016311当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。a.FIFO（先进先出）算法b.LRU（最近最少使用）算法c.Clock算法d.最佳（使用下面的访问串）算法e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列：4,0,0,2,4,2,1,0,3,2如果使用窗口大小为4的工作集策略来代替固定分配，会发生多少页错误？每个页错误何时发生？解答a:页帧3，在时间20加载，时间最长。b:页帧1，在时间160访问距现在时间最长。c:清除页帧3的R位（最早加载），清除页帧2的R位，（次最早加载），换出的是页帧0因为它的R位为0。d:换出的是页帧3中的虚拟页3，因为它将最晚被访问到。e:一共有6个错误，如下8.6一个进程在磁盘上包含8个虚拟页，在主存中固定分配给4个页帧。发生如下顺序的页访问：1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3a.如果使用LRU替换策略，给出相继驻留在这4个页帧中的页。计算主存的命中率。假设这些帧最初是空的。b.如果使用FIFO策略，重复问题（a）。c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用FIFO的效率接近于LRU。解答a:LRU：命中率=16/33b:FIFO：命中率=16/33c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。8.17假设一个任务被划分为4个大小相等的段，并且系统为每个段建立了一个有8项的页描述符表。因此，该系统是分段与分页的组合。假设页尺寸为2KB。a.每段的最大尺寸为多少？b.该任务的逻辑地址空间最大为多少？c.假设该任务访问到物理单元00021ABC中的一个元素，那么为它产生的逻辑地址的格式是什么？该系统的物理地址最大为多少？解答a.8×2K=16kb.16K×4=64Kc.232=4GBytes9.1考虑下面的进程集合：进程名到达时间处理时间A03B15C32D95E125对这个集合，给出类似于表9.5和图9.5的分析。每格代表一个时间单位，方框中的数表示当前运行的进程AAABBBBBCCDDDDDEEEEEABABCABCBDBDEDEDEDEEAAABBBBCCBDDEDEEEEDEAAACCBBBBBDDDDDEEEEEAAACCBBBBBDDDDDEEEEEAAABBBBBCCDDDDDEEEEEABACBCABBDBDEDEDEDEEABAACBBCBBDDDDDEEDEE第一到第八行依次是FCFSRR,q=1RR,q=4SPNSRTHRRNFeedback,q=1Feedback,q=2(i)ABCDETa013912Ts35255FCFSTf38101520Tr3.007.007.006.008.006.20Tr/Ts1.001.403.501.201.601.74RRq=1Tf6.0011.008.0018.0020.00Tr6.0010.005.009.008.007.60Tr/Ts2.002.002.501.801.601.98RRq=4Tf3.0010.009.0019.0020.00Tr3.009.006.0010.008.007.20Tr/Ts1.001.803.002.001.601.88SPNTf3.0010.005.0015.0020.00Tr3.009.002.006.008.005.60Tr/Ts1.001.801.001.201.601.32SRTTf3.0010.005.0015.0020.00Tr3.009.002.006.008.005.60Tr/Ts1.001.801.001.201.601.32HRRNTf3.008.0010.0015.0020.00Tr3.007.007.006.008.006.20Tr/Ts1.001.403.501.201.601.74FBq=1Tf7.0011.006.0018.0020.00Tr7.0010.003.009.008.007.40Tr/Ts2.332.001.501.801.601.85FBTf4.0010.008.0018.0020.00q=2iTr4.009.005.009.008.007.00Tr/Ts1.331.802.501.801.601.819.165个批作业，从A到E，同时到达计算机中心。它们的估计运行时间分别为15，9，3，6和12分钟，它们的优先级（外部定义）分别为6，3，7，9和4（值越小，表示的优先级越高）。对下面的每种调度算法，确定每个进程的周转时间和所有作业的平均周转时间（忽略进程切换的开销），并解释是如何得到这个结果的。对于最后三种情况，假设一次只有一个作业运行直到它结束，并且所有作业都完全是受处理器限制的。a．时间片为1分钟的轮转法。b．优先级调度c．FCFS（按15，9，3，6和12顺序运行）。d．最短作业优先a:时间片为1分钟的轮转法：12345ElapsedtimeABCDE5ABCDE10ABCDE15ABDE19ABDE23ABDE27ABE30ABE33ABE36AE38AE40AE42A43A45每个进程的周转时间A=45min,B=35min,C=13min,D=26min,E=42min平均周转时间是(45+35+14+26+42)/5=32.2minb.PriorityJobTurnaroundTime3B94E9+12=216A21+15=367C36+3=399D39+6=45平均周转时间是(9+21+36+39+45)/5=30minc.JobTurnaroundTimeA15B15+9=24C24+3=27D27+6=33E33+12=45平均周转时间是(15+24+27+33+45)/5=28.8mind.RunningJobTurnaroundTimeTime3C36D3+6=99B9+9=1812E18+12=3015A30+15=45平均周转时间是:(3+9+18+30+45)/5=21min10.1考虑一组周期任务（3个），表10.5给了它们的执行简表。按照类似与图10.5的形式，给出关于这组任务的调度图。表10.5习题10.1的执行简表进程到达时间执行时间完成最后期限A(1)01020A(2)201040............B(1)01050B(2)5010100............C(1)01550C(2)5015100....答：对于固定的优先级来说，我们以优先级是ABC来考虑这道题。每一方格代表五个时钟单元，方格里的字母是指现在正在运行的进程。第一行是固定的优先级；第二行表示的是使用完成最后期限的最早最后期限调度。表格如下：对于固定优先级调度来说，进程C总是错过它的最后期限。10.2考虑一组非周期性任务（5个），表10.6给出了它们的执行简表。按照类似于图10.6的形式给出关于这组任务的调度图。表10.6习题10.2的执行简表进程到达时间执行时间启动最后期限A1020100B202030C402060D502080E602070答：每一方格代表10个时间单元。10.3这个习题用于说明对于速率单调调度，式（10.2）是成功调度的充分条件，但它并不是必要条件[也就是说，有些时候，尽管不满足式（10.2）也可能成功调度]。AABBAACCAABBAACCAAAABBACCACAABBAACCCAA最早期限AACCEEDD有自愿空闲时间的最早期限BBCCEEDDAA先来先服AACCDDa.考虑一个任务集，它包括以下独立的周期任务：任务P1：C1=20;T1=100任务P2:C2=30;T2=145使用速率单调调度，这些任务可以成功地调度吗？b.现在再往集合里增加以下任务：任务P3:C3=68;T3=150式（10.2）可以满足吗？C．假设前述的三个任务的第一个实例在t=0是到达，并假设每个任务的第一个最后期限如下：D1=100;D2=145;D3=150如果使用速率单调调度，请问这三个最后期限都能得到满