OS习题课部分答案

操作系统练习课的一些答案内存管理2.系统采用请求分页管理。页面消除算法是LRU。每个作业占用15页，其中一页用于存储程序，每一页存储200个整数变量。考虑以下程序：20100，20100，I，j；对于(I=1；i=20(I)对于(j=1；j=100j)aIj=0；对于(I=1；i=20(I)对于(j=1；j=100j)bIj=aIj；假设数组ab存储在行中，程序已经转移到主内存，变量ij放在程序页中。这个程序会产生多少缺页中断？记忆中剩下的最后几页是什么？解决方案：数组A有2000个元素，总共占用10页，每行一页数组B有2000个元素，总共占用10页，每行一页在第一个周期中，I，j=0将把所有A矩阵转移到存储器中，并被分配0，导致10个缺页中断，留下4个块。在第二个周期中，首先读取A，然后写入B。剩余的4个空闲内存块可以放入阵列B的0-7行。此时，内存已满。如果A1用于表示由阵列A的行a0和1占据的页号，则阵列A的A0-A19和阵列B的B0-B3页(行b0b7)都被读入存储器。也就是说，Ij=Ij；LRU淘汰赛将在2008年的循环赛中从b线8开始进行.根据周期的特点，b线8=a线8b9=a9这两个循环的页面访问是A4B4A4B4，整个循环顺序是：A4b4a4b4，a5b5a5b5，a13b13a13b13可以被还原为a4b4、a5b5，a13b13A4B4A5B5A6B6A7B7A8B8A9B9A10B10A11B11A12B12A13B13A0B4B111B5B122B6B133B74A4A115A5A126A6A137A78A89B8b0A9b1B9b2A10b3B1014页故障中断总共发生了14.15=29次缺页中断，最后一页A7-A13和B7-B13在内存中3.请考虑以下步骤：100150，150200，100200，I，j，k；对于(I=1；i=100(I)对于(j=1；j=200j)对于(k=1；k=150k)cIj=cIjaIk* bkj；让A矩阵和B矩阵的初始值设定好，C矩阵的初始值为0，每个矩阵以页为单位连续存储。主存储器最初是空的，当请求分页时使用先进先出算法。问：当作业分配10页时，每页可以存储100个整数。缺了多少页？记忆中最后一页的abc矩阵占了多少页？解决方案：矩阵a100150总共需要150页，每行1.5页矩阵b150200总共需要300页，每行2页矩阵c100200总共需要200页，每行2页在程序的逻辑地址空间中，总共需要650页，试验编号为：a占1-150页；b占151-450；c占451-650。Cij=cij aik*bkj读a，读b，计算a*b，读c，计算c a*b，写c；与内存访问相关的操作可以简化为：读取A、读取B、读取C、写入C对于顺序访问的A、B和C矩阵，只要它们不跨页面分布，就不会出现分页。例如，每次访问一世和一世；然而，每次访问b .kj时，它必须跨页面传播，因为它是按列读取的。使用先进先出算法，页面调度过程如下：循环变量读写操作记忆页I，j，k12345678910缺页1，1，1阅读1缺乏读b1151缺乏读c写c1151451缺乏1，1，2阅读1151451读b1151451153缺乏读c写c11514511531，1，3阅读1151451153读b1151451153155缺乏读c写c1151451153155.缺页在每个循环中发生一次，为读取B而生成，并从151到165加载到内存中1，1，8阅读1151451153155157159161163读b1151451153155157159161163165缺乏读c写c1151451153155157159161163此时内存已满1，1，9阅读1151451153155157159161163165读b167151451153155157159161163165缺乏读c写c1671514511531551571591611631651，1，10阅读1671451153155157159161163165缺乏读b1671169153155157159161163165缺乏读c写c1671169451155157159161163165缺乏1，1，11阅读1671169451155157159161163165读b1671169451171157159161163165缺乏读c写c1671169451171157159161163165每个周期有一页缺失1，1，100阅读1331333335337339341343345347缺乏读b1349333335337339341343345347缺乏读c写c1349451335337339341343345347缺乏1，1，101阅读13494512a矩阵已经跨越了页面。337339341343345347缺乏读b13494512351339341343345347缺乏读c写c13494512351452c矩阵也分布在不同的页面。341343345347缺乏100，200，148阅读150428430432434436438440442444缺乏读b150446430432434436438440442444缺乏读c写c150446650432434436438440442444缺乏100，200，149阅读150446650432434436438440442444读b150446650448434436438440442444缺乏读c写c150446650448434436438440442444100，200，150阅读150446650448434436438440442444读b150446650448450436438440442444缺乏读c写c150446650448450436438440442444规则：当循环数为n * 9 1或n * 100 1时，读取a、b、c时会出现缺页；在其他情况下，当阅读B时，只有一页缺失；因此，在阅读B时，总共出现了100*200*150个分页符，而对于B和C:每个周期总共100*200*150=n*9 1次：/9=次n*100 1的出现次数是：/100=29999；然而，n*9 1和n*100 1的出现次数是/900=3333。这个数字是重复计算的，需要减去，因此丢失的总页数为：(100*200*150) (29999-3333)*2次，即缺一页中断。4.虚拟存储系统使用LRU算法。每个程序占用3页内存，其中一页存储程序和变量I、j(不用于其他目的)。每页可以容纳150个变量。程序甲和程序乙如下：答：150100，I，j；对于(I=0；i=150(I)对于(j=1；j=100j)cIj=0；B:国际150100；对于(j=1；j=100j)对于(I=1；i=150(I)cIj=0；数组C是按行存储的，问：(1)执行程序A和程序B后，缺了多少页？(2)C的哪一部分是记忆中的最后一部分？解决方案：(1)数组C总共需要占用100页。因为它是按行存储的，所以每读取一页，将读取1.5行数组C，如下所示：第1页第2页c11.c251.1100.c2150c21.c31.250.c350对于程序A和C，每150个行访问周期发生一次分页，因此总共发生100次分页。对于程序B，C是按列访问的，每3个周期将发生2次页面变化，并且在C 1 1，C 2 1，C 3 1中将出现2*15000/3=10000个页面间隙.(2)对于程序A，在过去300个周期中访问的C数组元素是存储在最后两页中的元素对于程序B，在最后三个周期中访问的C数组元素是存储在最后两页中的元素。1.南开大学与天津大学之间有一条路径，从南向东一次只允许一辆自