OS丛话(计算篇)
2022-12-18 08:54:58 Author: www.freebuf.com(查看原文) 阅读量:8 收藏

理论铺垫

宏观上来讲,内存管理可以分为连续和非连续两种形式。从连续讲起,远古时期的单一连续分配(无需内存保护,原因很简单,内存中只有一个程序),那么随着多道系统的出现,又发展出了固定分区分配和动态分区分配。顾名思义,这个固定分区分配可以理解为我们网安上提的静态,就是来一个进程,看有没有合适的空闲空间,有就直接分配给他。简单粗暴,没有什么多余的判断。这就好比高中做题的时候,暴力应算求解和分析特点后的求解相比,灵活性太差。分多了浪费,或者对于大一点的进程根本就不够用。无论是单一连续,还是固定分区,都会产生内部碎片,而没有外部碎片

为了解决灵活性问题,发展出了动态分区分配,加入了一些思考(算法)。比如最好最坏首次和邻近,有点因地制宜的意思。解决了内部碎片的问题,又引入了外部碎片,尤其是最佳分配,最容易产生外部碎片。

那么按照剧情的发展,下一步自然就是要解决碎片问题。于是非连续分配闪亮登场,代表性人物分页,把一个进程解体(页,页面),内存分块(页框,页帧),然后将进程以块为单位装入内存,极大的减少了空间浪费。管理的核心是逻辑地址到物理地址的转化,这就是页表的作用了。后来人们发现传统的页表有点慢,基于局部性原理,提出了TLB的概念。但是页表需要连续存储,需要分配大量的连续地址空间,既然进程可以离散存储,WHY NOT 页表,于是呢,多级页表应运而生(说白了就是按照块的大小划分页表,页表的大小和块的大小相等,最后有多少页表页目录表中就要有多少页表项)。

分段存储,怎么说呢,就是面向程序员的内存管理方式(可以按照用户的需求划分为相应的逻辑段,而分页是为操作系统所感知的),段表项的构成为段号+段长+段内偏移,地址结构为一维(这个一维仍然是相对程序员来说的)。

总的来说,分段的优点是可以实现逻辑分块,便于管理和内存保护,缺点是可能会申请较大的连续内存空间或产生较多的外部碎片。而分页的优点是几乎不会产生碎片,但缺点是难于管理。那么对于这两种非连续管理方式,如何综合利用其优点呢,答得好,段+页==段页式呗,先分段,再对段进行分页。

实操一把

1670398393_639041b9ca88d7d825cb2.png!small?1670398394653

1670398408_639041c867228b2c7d189.png!small?1670398409407

首先明确逻辑地址和物理地址:

逻辑地址为页号+偏移量;物理地址为块号+偏移量;联系逻辑地址和物理地址的桥梁为页表,页表的组成单位为页表项(页号+块号)。所以首先将题目中给定的逻辑地址展开为二进制(因为页面大小为1KB,所以低10位为偏移量,用户编程空间为32个页面,所以高5位为页号,所以逻辑地址共有15位),同理物理地址为14位,最后就是对应了,缺页的要进行缺页中断处理。

二级页表也是同样的道理,注意偏移量即是页/页面或者页框(帧)的大小

1670400045_6390482dd946ba939ece0.png!small?1670400046744

再看这一题,上来第一步就是明确地址空间结构:看到页的大小为1KB,则页面偏移(页、页面、页框、页帧)大小均为10位,又因为逻辑和物理地址空间均为64KB(16位),则表示页(块)号的位数为(16-10=10位),求逻辑地址对应的页号,直接取前6位,为5,计算物理地址将页号改为要换出的页号,对于CLOCK算法,我在OS丛话中都写到了。

最后再来分析一个稍微难一点的问题:

1670402284_639050ec0b89399fc00c4.png!small?1670402284944

数组按行优先存储,每个数组为4B,看到页内偏移量为12位,所以页大小为12位,(因为按字节编址,所以为2^12B),一页可以存放1024个元素,正好为该数组的一行,也就是一页存一行。起始虚拟地址的虚拟页号为10800,a[1]的页号为10800+1=10801,a[1][2]的虚拟地址为10801000+4*2=10801008H.

对应的页目录号为:042H,页号为001H,又因为进程的页目录其实物理地址为0020 1000H,所以对应的页目录项的物理地址为0020 1000H+4*42H=0020 1108H.

同理,对应页表项的物理地址为:00301000H+4*001H=00301004H.

记住,计算地址的时候要乘以每一项占的大小。好了,总结一下,对于这一类问题,核心就是明确地址结构,做好对应关系。

对于快表问题:只需把握一个核心 :若信息在快表中,仅需访问一次主存(可以直接得到物理地址并进行访问);若信息不在快表中,需要访问2次主存(第一次访问得到物理地址,第二次访问得到所需数据),主要用于计算有效存取时间,思想类似于系统安全中用相乘法计算风险值。

1671020656_6399c070a28ffc33e24d2.png!small?1671020657974

还有就是二级页表的问题的问题:

1671022445_6399c76db74fe0eb90789.png!small?1671022446760

假设页表项和页目录项均占4个字节,计算页表和页目录共占多少页;小白可能看答案有些迷糊,(2^10*4+2^20*4)/2^12,首先第一个2的10次乘以4为页目录占的字节;第二个为页表占的字节,为什么要乘以2的20次方呢,因为在没有划分二级页表之前有2的20次方个页,具体可以参考页表的物理结构,有多少页就有多少页表项:

1671022333_6399c6fd35d06609e316d.png!small?1671022334476

后记

本文主要对段页式相关计算进行了简单讨论,权当作抛砖引玉,主流考法还包括:对周转时间的相关计算;以及对磁盘存储的相关计算,大家可以自行探索,也欢迎向本专辑投稿。


文章来源: https://www.freebuf.com/articles/neopoints/352813.html
如有侵权请联系:admin#unsafe.sh