第十八章
1.根据题中所给参数计算线性页表大小和不同情况下的变化
paging-linear-translate.py -P 1k -a 1m -p 512m -v -n 0
paging-linear-translate.py -P 1k -a 2m -p 512m -v -n 0
paging-linear-translate.py -P 1k -a 4m -p 512m -v -n 0
页大小为1kb,地址空间大小分别为1mb,2mb,4mb,物理地址空间大小为512mb,页表项应分别有1mb/1kb=1024,1mb/1kb=2048,1mb/1kb=4096。假设每个页表项需要4字节的空间,页表的大小分别为4kb,8kb,16kb。在页大小相同的情况下,地址空间增长,页表项随之增长,页表增大。
paging-linear-translate.py -P 1k -a 1m -p 512m -v -n 0
paging-linear-translate.py -P 2k -a 1m -p 512m -v -n 0
paging-linear-translate.py -P 4k -a 1m -p 512m -v -n 0
页大小分别为1kb,2kb,4kb,地址空间大小为1mb,物理地址空间大小为512mb,页表项分别有1mb/1kb=1024,1mb/2kb=512,1mb/4kb=256。假设每个页表项需要4字节的空间,页表的大小分别为4kb,2kb,1kb。在地址空间大小相同的情况下,页的大小增大,页表项减少,页表减小。
使用很大的页会导致页内部的空间可能存在大量浪费和内部碎片,因此不使用很大的页。
2. 使用题中标志paging-linear-translate.py -P 1k -a 16k -p 32k -v模拟,页的大小为1kb,地址空间16k,共16页,用4位表示虚拟页号,10位表示偏移量,并使用-u更改分配给地址空间的页数。
分配页数为0:
VA 0:invalid address
VA 1:invalid address
VA 2:invalid address
VA 3:invalid address
VA 4:invalid address
分配给地址空间的页数为0,因此没有有效的地址。
分配页数为25:
VA 1(11100110000110):VPN=14,invalid address
VA 2(10101111000110):VPN=10,PFN=19,OFFSET=966,PA=20422
VA 3(01111000110111):VPN=7,invalid address
VA 4(00011001110001):VPN=1,invalid address
VA 5(01101111001001):VPN=6,invalid address
分配页数为50:
VA 1(11001110000101):VPN=12,PFN=15,OFFSET=901,PA=16261
VA 2(10001100011101):VPN=8,invalid address
VA 3(00000011100110):VPN=0,PFN=24,OFFSET=230,PA=24806
VA 4(10111000001111):VPN=11,invalid address
VA 5(01100110000110):VPN=6,PFN=29,OFFSET=390,PA=30086
分配页数为75:
VA 1(10111000001111):VPN=11,PFN=19,OFFSET=527,PA=19983
VA 2(01100110000110):VPN=6,PFN=31,OFFSET=390,PA=32134
VA 3(11010011001010):VPN=13,PFN=27,OFFSET=202,PA=27850
VA 4(10101011000011):VPN=10,PFN=3,OFFSET=707,PA=3779
VA 5(00000000010010):VPN=0,PFN=24,OFFSET=18,PA=24594
分配页数为100:
与分配页数为75结果相同。
增加每个地址空间中的页的百分比,有效地址将更多。
3.按照题中所给参数运行
paging-linear-translate.py -P 8 -a 32 -p 1024 -v -s 1,页的大小为8,地址空间32,物理地址空间大小为1024,页数为4,2位表示页号,3位表示偏移量:
VA 1(01110):VPN=1,PFN=97,OFFSET=6,PA=782
VA 2(10100):VPN=2,invalid address
VA 3(11001):VPN=3,invalid address
VA 4(00011):VPN=0,invalid address
VA 5(00000):VPN=0,invalid address
这样的组合不合理,地址空间很小,一个地址空间只能存放4页。
paging-linear-translate.py -P 8k -a 32k -p 1m -v -s 2,页大小为8kb,地址空间大小为32kb,物理地址空间为1mb,页数为4,2位表示页号,13位表示偏移量:
VA 1(101010110111001):VPN=2,invalid address
VA 2(010011101110001):VPN=1,invalid address
VA 3(100110110001111):VPN=2,invalid address
VA 4(100110110101011):VPN=2,invalid address
VA 5(100101001100100):VPN=2,invalid address
该组合同样不合理,地址空间小。
paging-linear-translate.py -P 1m -a 256m -p 512m -v -s 3,页大小为1mb,地址空间大小为256mb,物理地址空间为512mb,页数为256,8位表示页号,20位表示偏移量:
VA 1(0011000010001011001001001101):
VPN=48,PTE=0x800001f6,PFN=502,OFFSET=569933,PA=526955085
VA 2(0100001000110101000111100110):
VPN=66,PTE= 0x00000000,invalid address
VA 3(0010111111101011011001111011):
VPN=47,PTE= 0x800000a9,PFN=169,OFFSET=964219,PA=178173563
VA 4(1011010001101001011101111101):
VPN=180,PTE= 0x00000000,invalid address
VA 5(1101101111001100111010110100):
VPN=219,PTE=0x800001f2,PFN=498,OFFSET=839348,PA=523030196
组合不合理,页和地址空间都很大,物理地址空间只能满足两个地址空间的大小。
第二十章
1.
对于二级页表,只需要一个寄存器找到页目录的位置,从页目录中找到存放页表的位置,从页表中就可以找到页表项。三级页表同样只需要一个寄存器找到页目录的位置,接下来就可以通过一级页目录找到二级页目录的位置,通过二级页目录找到页表的位置,最后找到页表项。
2.
首先查看文档中给出的条件,该模拟程序中,页的大小为32字节,地址空间中共有1024页(共32kb),物理地址空间共128页。128页需要7位表示页号,1位表示是否有效,因此一个页表项占用1个字节的空间,所有页表项占用1024字节的空间。将页表项放入32字节大小的页中,需要使用32页,使用5位在页目录中进行索引,5位在页表中索引,5位表示页内偏移,虚拟地址共15位,由页目录索引+页表索引+页内偏移构成。
种子0:
VA 0:
611C 110000100011100,页目录索引:11000(24),页表索引:01000(8),页内偏移:11100(28),页目录基址:108。
首先找到页目录项,在108页的25字节,为0xa1(10100001),最高位表明有效,后七位为页表所在的页:33。
页表索引为8,即33页的9字节,为0xb5(10110101),最高位表明有效,后七位为物理页帧0x35(53),则物理地址为PA=53*32+28=1724(0x6bc),找到35页的第29个字节即为最终找到的值:0x08。
其他地址的转换方式相同,具体情况如下表:
种子1:
计算方法相同,结果如下:
种子2:
结果如下:
3.
当初次访问内存中的某个位置时,会产生不命中,系统将访问页表,找到虚拟页所对应的物理页,并将这个映射保存到缓存中。利用时间局部性与空间局部性,接下来的访问很有可能导致大量的缓存命中,从而导致快速访问。在一些特定的情况下,程序短时间访问的页数大于缓存中的页数,也可能会产生大量的缓存不命中。
第二十二章
1.
使用题中所给参数-s 0 -n 10生成随机地址:
缓存大小为3页,采用不同策略,情况如下:
FIFO,命中率为10% LRU,命中率为20%
OPT,命中率为40%
使用参数-s 1 -n 10生成随机地址:
采用不同策略,情况如下:
FIFO,命中率20% LRU,命中率20%
OPT,命中率30%
使用参数-s 2 -n 10生成随机地址:
采用不同策略的情况如下:
FIFO,命中率40% LRU,命中率40%
OPT,命中率40%
2.
不同策略下的最差情况的地址引用序列
FIFO:1,2,3,4,5,6
LRU:1,2,3,4,5,6
MRU:1,2,3,4,5,6,5,6,5,6…
对于LRU和FIFO,只要缓存大小与序列大小相同就可以提高命中率,且除了冷启动不命中外均命中。对于MRU,如果缓存容量刚好已满,而有两页交替进行访问,只要缓存增大1就可以提高命中率,大幅提高性能。
3.
编写python程序,随机生成一个序列,进行100次地址访问,地址介于0-9之间。程序如下:
在这种情况下没有局部性,随机进行访问,预计除OPT外的策略效果基本相近。
使用paging-policy.py程序对产生的序列进行模拟,缓存大小为3,命中率如下:
FIFO:31%
LRU:28%
CLOCK:27%
RAND:29%
OPT:50%
结果符合预期。
4.
编写python程序,生成具有局部性的序列。访问地址仍为0-9,随机选择两页,在80%的时间访问这两页,20%的时间访问其他页。
使用paging-policy.py程序对产生的序列进行模拟,缓存大小为3,命中率如下:
FIFO:61%
LRU:70%
CLOCK:66%
RAND:61%
OPT:76%
LRU策略在几种策略中效果最好,RAND策略比LRU效果要差一些,CLOCK策略比RAND和FIFO策略较好,比LRU差。对于CLOCK策略,改变时钟位,结果如下
Clockbits 2:66%
Clockbits 1:61%
Clockbits 3:71%
Clockbits 4:71%
Clockbits 5:72%
Clockbits 7:73%
Clockbits 7:74%
Clockbits 8:74%
Clockbits 9:74%
Clockbits 10:73%文章来源:https://www.toymoban.com/news/detail-416190.html
可以观察到,在一定的范围内,随着时钟位的增加,CLOCK策略的效果逐步提升,命中率超过了LRU策略,甚至已经接近了OPT。文章来源地址https://www.toymoban.com/news/detail-416190.html
到了这里,关于操作系统作业 18-22章的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!