[操作系统]第四课

小鱼儿 2022-04-23 06:28 224阅读 0赞

> 课程来源《操作系统\_清华大学(向勇、陈渝)》

还参考文章：[https://blog.csdn.net/github\_36487770/article/details/54933265][https_blog.csdn.net_github_36487770_article_details_54933265]

上节课是介绍连续内存，这节课介绍非连续内存。

**1.非连续内存分配：分段**

为什么需要非连续内存分配？  
连续内存分配有碎片、内存利用率低、分配给一个程序的物理内存是连续的缺点，对应非连续的优点：更好的内存利用和管理，允许共享代码和数据（共享库。。），支持动态加载和动态链接。

最大的问题在于管理的开销。在虚拟地址和物理地址之间的转换，如果用软件来实现，开销巨大。因此要考虑用硬件来协同解决。

非连续内存分配两种硬件管理方法？  
1.分段，  
2.分页机制，更好的分离和共享 （以及分页中的一个重要数据结构：页表）

分段机制：  
1.程序的分段地址空间设计，  
2.寻址方案。

分段：更好的分离和共享（把连续的逻辑地址空间分段到不连续的物理地址空间）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]  
把逻辑地址空间分散到多个物理地址空间，堆-→堆，运行栈-→运行栈，程序数据-→数据，运行exe—>代码和库

分段寻址方案（逻辑地址空间和分段的物理地址空间对应）：

一维连续逻辑地址，把一个段看成一个内存块。程序访问内存地址分为两部分，段的寻址（段号segment number）+ 段内偏移的寻址（addr）

段寄存器+地址寄存器实现方案（x86）  
单地址实现方案（s+addr合在一起）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]

**2.非连续内存分配：分页**

分页：分页地址空间、页寻址方案

分页也是实现机制和寻址，也需要页号和偏移

类似，区别在于页帧的size不变。

划分物理内存至固定大小的帧frame(物理页)，逻辑地址空间也要到相同大小的页（page，逻辑页）。两者大小要相等，为2的幂数，如512，4096，8192.。。

建立方案，change pages to frames，需要页表和MMU/TLB（快表，完成对MMU的缓存）。

**Frame的概念：**

物理内存被分割成大小相等的帧，一个内存物理地址是一个二元组（frame number, offset）。  
f—帧号，F位，共有2F个帧；  
o—帧内偏移，S位，每一帧有2S字节。  
物理地址=2S \* f + o  
![在这里插入图片描述][20190127145925701.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 3]  
示例：  
对16bit的地址空间，9bit大小的页帧，物理地址（3，6）  
F=16-9=7 存帧号 未用到  
S=9 帧内的位数  
And f=3 frame number,o=6  
代入=1542

**Page的概念：**

page的计算方式与之类似，区别在于页号大小的size和帧号的大小可能不一致，但offset都是一样的。二元组（p，o）  
虚拟地址=2S \* p+ o

页寻址机制，其中OS建立的页表page table保存了逻辑地址—物理地址之间的映射关系。由页号查帧号。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 5]

页寻址机制：  
1.页映射到帧  
2.页是连续的虚拟地址  
3.帧是非连续的物理内存  
4.不是所有的页都有对应的帧

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 6]

特点：页内偏移大小一定，不需要考虑不同段大小不一致，硬件更易管理；PAGE的地址空间大小和FRAME的地址空间大小是不同的，一般前者更大，页是虚拟内存，连续，帧是不连续的物理内存，不是所有的页都有对应的帧，装不下时会用虚拟内存（以后会讲）。有助于减少碎片。

**3.非连续内存分配：页表-概述、TLB**

页表：页表概述、转换后备缓冲区（TLB）、二级/多级 页表、反向页表

页表结构：  
大数组，索引是page number，内容frame number  
每个运行的程序都有一个页表，属于程序运行状态，会动态变化，PTBR(页表基址寄存器)。  
页表项中除了frame number 还有标志位flags检查是否存在地址, including dirty bit, resident bit （是否存在该对应的物理地址）and clock/reference bit.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 8]

确定物理地址：  
1.由逻辑地址的页号去页表中查找对应的物理内存的页号  
2.通过物理页号加上偏移量得到实际物理地址  
例子：已知每页为1024byte（即逻辑页表和实际内存分页的大小都是1024byte）那么（3，1024）对应的物理地址时？  
查页表可知逻辑页3号对应物理内存4号。故物理地址=4\*1024+1023

性能问题：  
1.问题：访问一个内存单元需要2次内存访问（依次用于获取页表项；一次用于访问数据）  
2.页表可能非常大（64位机器如果每页1024字节，那么一个页表的大学是多少？1024字节是指1024byte，1byte=8bit）  
时间开销：页表太大不能放到CPU中，只能放内存，每次寻址一个内存单元需要2次内存访问，获取页表项和访问数据

空间开销：  
○1页表可能非常大，64位机器，寻址空间是2的64次幂，一个页size如果只有1024 1k，要建立一个极大的页表=254，存不下。  
○2n个程序对应n个页表，页表个数非常大。

两种解决方法：缓存（caching）和间接（indrection）访问  
在cpu的MMU中，存在一个cache叫TLB translation look-aside Buffer ，缓存近期访问的页帧转换表项。首先CPU根据逻辑地址查快表TLB（key=p, value=f，由于使用关联内存（associate memory）实现，具备快速访问性能，很少超过64个表项，每个对应一个页面的相关信息。）如果命中，FRAME很快被获取，如果未命中MISS，则去查页表并更新对应的表项到TLB中。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 9]

TLB的缺失不会很大，32位一个页4K，访问4K次miss一次，可以接受。写程序时注意具有局部性，把频繁的访问集中在一个区域。以避免对内存的访问。另外，还需要注意，miss后，更新是硬件完成（x86），还是OS完成（现代机器，MIPS, SPARC, HP PA）。

**4.非连续内存分配：页表-二级，多级页表**

空间上怎么压缩页表？多级页表（参见数据结构中的多级索引表）

将大的PAGE的page number分为两部分P1&P2，OFFSET不变  
多次访问，存俩表，开销大，怎么节省的呢？  
通过省去P2中（p1 不存在映射关系，驻留位（resident bit==0）是0的页表项）对应的page table来省空间。应用程序适合这种方式。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 10]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 11]

推广→把页号分为k个部分，建立页表树。  
64位通常是5级页表，以时间换空间，再用TLB来缓解时间上的开销

**5.非连续内存分配：页表-反向页表**

页表：页表概述、快表（TLB）、二级/多级页表、反向页表

由于2个问题（大地址空间问题）：  
○1大地址空间（64-bits）使前向映射页表繁琐（5级），  
○2不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应，虚拟地址空间增长速度快于物理地址空间

因此，前向页表与逻辑空间地址的大小相关→反向页表则是与物理地址空间的大小相对应。

反向页表基于页寄存器，page registers, using frame as index while the content is occupier (page numbers)，residence bit (是否被占用), protection bits.  
优点：空间开销少。映射表的大小相对于物理内存很小，且与逻辑地址空间的大小无关。  
E.G: 物理内存4K*4K=16M，页面大小是4KB，则页帧数为4K。  
If 8 bytes per page register, then room for page registers is 8*4K=32KB  
The extra cost of page registers is only 32K/16M=0.2%

问题在于怎么用页号找帧号？  
关联内存 associate memory  
类似TLB，并行查找，KEY是页号，value是帧号  
但关联存储器用到的硬件逻辑很复杂，开销很大，本身size做不了多大，还需要放到CPU否则要二次访问。大的关联存储器也会造成时间开销大。

反向页表整体搜索机制  
如果帧数少，放到关联内存中，在关联内存中查找逻辑页号，成功则提取帧号，失败抛出page fault。限制因素在于大量的关联内存很昂贵，难以在单个时钟周期内完成且耗电。

折中方案——-哈希表  
用硬件加速，建立哈希表来实现反向页表。  
对页号做哈希计算，页i放在表中funchash(i)的位置，求得f(i)作为页寄存器表的索引获取对应的页寄存器再检查标签是否有i。

问题：

会有碰撞，多个页帧号到底对应哪个，加入参数PID==ID of running program来缓解冲突；  
哈希表在内存中，要访问内存，内存的时间开销还是很大  
优点：本身物理存址小省空间，不再是每个应用程序都要page table了，整个系统只用一个。  
缺点：需求高，有高效哈希函数和解决冲突的机制，要硬件软件配合

[https_blog.csdn.net_github_36487770_article_details_54933265]: https://blog.csdn.net/github_36487770/article/details/54933265
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]: /images/20220323/68f58c77f8364f90bf29dd4b5c4f3aa0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]: /images/20220323/513cfd8b430e4eb4896b77add283ca0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]: /images/20220323/f251cd6d25c54b9e88af468ba5d94031.png
[20190127145925701.png]: /images/20220323/490aeafa7b2d4bdfae0e0a60254b2a2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 3]: /images/20220323/c137010dbc58437e9148d8977acda0eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 4]: /images/20220323/62aa3fb724bf4624ac0c8257276cadce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 5]: /images/20220323/607b0af7442e46b2af7713eea26356dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 6]: /images/20220323/7f1f294963614fdb951d064ea1a346f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 7]: /images/20220323/433dbd37c1a847b7ae844370ff0974ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 8]: /images/20220323/2a159d5a21774f08bc2079011c42e74d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 9]: /images/20220323/edfb403a717d4516a57dbbcd47abd8b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 10]: /images/20220323/d842e232e4a444e2812700932c3dee3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 11]: /images/20220323/112cd3c51dda4ac1b56af47f15878dd4.png