操作系统内存

文章自看。

Address Spaces

一个程序在内存中占用的空间叫 address space。例如下面:

image-20210427135230566

这个 address space 被简化过了。包含了 program code (固定大小),heap(动态申请的空间,例如 malloc() 函数申请的)和 stack(函数内的局部变量)。

每个程序都认为自己是从内存地址 0 开始的(virtual address),而且它们的 address space 都有32位或64位的长度。但实际物理内存上肯定不会这样。

Dynamic (Hardware-based) Relocation

CPU 提供了一个 base 和 bound 寄存器。(也叫 Memory Management Unit)(MMU)

physical address = virtual address + base

然后 bound 检查内存有没有超出边界。

这一过程叫 address translation

OS must save and restore the base-and-bounds pair when it switches between processes. Base-bounds 的值通常可以放在 PCB 里面(process control block)。

但是简单的这种方法还是有缺点:

image-20210427144434832

按照上面的图,一个应用这样分配内存,即使 heap 和 stack 中间有一大部分空间没有被用到,然后这部分空间也不能为其他线程使用(internal fragmentation)。所以我们要划分的更细(segmentation),比如把一个应用的 code,heap,stack 分开来存,这样就能省空间了,不会站着茅坑不拉屎。

Segmentation

Segmentation 就是下面这个图,把 stack,code,heap 分开放。

image-20210427145932355

这种时候,就需要 1组的 base 和 bound 来记录一个程序的内存偏移,如下:

image-20210427150206730

Which segment are we referring to?

假设我们是 14-bit 的 virtual address。我们用前面两位标记我们使用的是哪一个 segment。

image-20210427153518543

比如前面两位为 00,代表是 code segment。01 为 heap segment。10 为 stack segment。

假设我们访问一个 virtual address(4200),translate it。

image-20210427153645089

可以看到前面 segment 为 01,代表我们访问的是 heap。后面 offset 代码我们访问的地址是 heap 中偏移量为此的地址。

image-20210427153820893

因为我们是 14-bit 的 address space。这里我们 SEG_MASK 为 0x3000,SEG_SHIFT 为 12,OFFSET_MASK 为 0xFFF。

你也许注意到,我们前面用 2bit 标记使用哪一个 segment,但是 2bit 能表示 4中 segment,这里我们只表示了 3 种 segment,浪费了一个。因为我们只能用后面 12bit 来标记空间,使得 maximum size 只有 4KB 了,而原本 14bit 能标记 16KB。

Stack growth

因为 stack 内存增长是从高地址向低地址增长,所以我们可以再拿一个寄存器来标记此 segment 内存增长的方式。

image-20210427155211660

比如我们访问内存地址:11 1100 0000 0000,前面两位为 11,对应 stack segment。后面 offset 为 3KB。根据 bit 位数知道,最大支持 4KB 的空间。所以计算 offset = 3KB-4KB = -1KB。然后在 base register 上面 -1KB 获得地址。同时用 bound register 检查范围是否合法。

Support for Sharing

当然你可以再拿几位的空间浪费下,加点功能,例如 sharing。

image-20210427155811095

Fine-grained VS Coarse-grained Segmentation

Coarse-grained segmentation 就和上面一样,粗糙的将 address space 划分为 3 个 segment。

Fine-grained segmentatioon 就划分的更加细致,可能将一个 address space 划分为上千个 segment。这么多 segment,用一个 segment table 管理。

Free Space Management

Tracking The Size Of Allocated Regions

在 C 语言中使用 free(*ptr) 函数,不需要传入内存的大小,只需要一个起始的地址,它是这么做到的:

image-20210427193804659

每一个申请的内存还会附带一个 header,这里 header 包含了申请内存的大小和 magic number(可以理解为校验码)。

所以你申请一个 N bytes 的内存时,实际搜索 free space size = N bytes + header size。

Memory allocation strategies

Best Fit:

遍历整个 free list,找到空闲空间仅仅大于要求空间一点点的空间。

缺点:必须要遍历整个 free list 才能知道。Exhaustive search。

Worst Fit:

找到最大的空间来存放。

缺点:Exhaustive search。大多数论文证明,它只会引起更加严重的 fragmentation。

First Fit:

找到第一个符合要求的 block。不需要 exhaustive search。

缺点:Sometimes pollutes the beginning of the free list with small objects.

Next Fit:

Next Fit algorithm keeps an extra pointer to the location within the list where one was looking last.

能够分散 search 在整个 free list。避免一直 split free list 的开头。

性能和 First Fit 差不多。

Segregated Lists:

多个 free list。其中一条为 general list,来存放普通的 object。其他的为 specialized list,专门存放指定大小的 object。比如 inode,lock 这种常用,但是 size 一样的 object。

Slab Allocator 就采用这种思想。It allocates a number of object caches for kernel objects that are likely to be requested frequently (such as locks, file-system inodes, etc.) 当 specialized list 空间不够时,它会申请 slabs of memory from a more genernal memory allocator。当然当 OS 需要更多的 memory 时,它可以从 specialized list 中回收部分空间。

此外,Slab Allocator 还做了额外的改进。因为创建销毁 object 消耗大量的系统资源。它会把 free 过的 object 以 pre-initialized state 的形式存放在一个 list 里面,这样要回来用时候就能很快的用起来。

Buddy Allocation:

因为 coalescing 对于 allocator 很关键,所以 binary buddy allocator 能极大的简化内存合并这一过程。

buddy allocation 就是不断递归二分内存,以此找到合适的空间。如下:在 64KB 的内存中寻找一个 7KB 的空间

image-20210427211510127

Paging

一个 process address 划分出多个 fixed-sized units, 每一个 unit 叫 page。(虚拟内存)

物理内存上面固定尺寸的 unit 叫 page frames。(物理内存)

image-20210428134155304
image-20210428134211697

如上图,有一个 64-bytes 的 address space,同时物理内存有 128 bytes。每一个 page 大小为 16 bytes。

每一个 process 为了追踪自己 address space 中每一个 page 对应的是物理内存中哪一个 page,其在内部会有一个 page table。例如上面这个 process 中的 page table 为 <virtual page 0 -> physical frame 3>, <VP 1 -> PF 7>, <VP 2 -> PF 5>, <VP 3 -> PF 2>

为了 translate virtual address,我们将一个 virtual address 划分为两部分,分别为 virtual page number (VPN) 和在 page 中的 offset 。因为这里例子中的 address space 为 64 bytes。然后每一个 page 为 16 bytes,也就是最多我们会有 4 个 page(2 bit 表示),一个 page 中最大的 offset 为 16(4 bit 表示)。如下图:其中 Va5 为 highest-order bit of virtual address。Va0 为 lowest-order bit。

image-20210428134949494

这里假设,我们访问地址为 21 的 virtual address。,转换为 binary 为 01-0101:

image-20210428135243466

我们得到 virtual page number 为 1,从该 process 中的 page table 查找到对应的 physical page number 为 7 (111)(上面图上面有)。

image-20210428135404952

所以我们只要访问 PFN 为 111 的 page,page 中的 offset 为 0101 。

Where Are Page Tables Stored?

假设一个 32bit 的 address space,4kb 的 page。Virtual address 划分为 20bit 的 VPN 和 12bit 的 offset(10bit would be needed for a 1KB page size)。20 bit 的VPN 代表有 $2^{20}$ 个 page table entry (PTE) ,假设一个 PTE 要用 4 bytes,那么光是 page table 就要占用 4MB,这还只是一个 process。如果有 100 个 process 同时运行,那么 page table 就要 400MB,太耗空间了。更何况如果我们是 64bit 的 address space 呢,不可想象。

What’s Actually In The Page Table?

image-20210428145315220

Valid: 判断该 page 是否在 physical memory 分配过。毕竟一个应用可能只需要用那几个 page,如果 physical memory 提前把一个 address space 所有的 page 都分配过了,就会大大浪费空间。

P: present bit 表示 page 是在 physical memory 还是在 disk 里面。

R/W:决定该 page 的 write 是否允许。

U/S:user/supervisor bit 决定 user-mode processes can access the page。

PWT, PCD, PAT and G: determine how hardware caching works for these pages。

A: access bit。

D: dirty bit。

Paging: Also Too Slow

过程太多,访问慢。

image-20210428152719086

Paging: Faster Translations (TLBs)

为了加速 address translation 的过程,人们在 CPU 的 MMU 模块添加了一个 translation-lookup buffer (TLB) ,也可以叫 address-translation-cache。

image-20210428233635341

总的来说,就是当需要 translate virtual address 时,首先去 TLB 中查找,如果查找到,则直接返回。否则在该 process 中的 page table 查找,找到后放入 TLB 中。然后再执行一遍查找流程(这时候肯定能够命中缓存 hit cache)。

TLB 通过 spatial locality(你访问的这个,你随后大概率会访问其附近的 entry)temporal locality(你访问这个,随后你大概率还会再访问它) 两种特性,极大的提升了 translation 的速度。

Who handles the TLB miss

主要就两种设计,一种基于 hardware,一种基于 software。

可以采用类似 trap 的设计,当 miss cache 了,然后找到 OS 提供的指定 trap handler,进行处理。

TLB contents

TLB 查找很快,硬件层面上叫 fully-associative,the hardware searches the entries in parallel to see if there is a match.

image-20210429000018974

VPN: virtual page number

PFN: page frame number

Valid: 是否有效,TLB 默认初始化后,所有 valid 为 0,然后用一个,设置为 1。当不需要某一个 cache 时,设置为 0 即可,不需要清空整个 entry。

Prot: protection,权限管理。

ASID:address space identifier,也可以叫 process identifier (PID)。主要用于解决 context switch 时,不同 process 的 page table 对应的不一样,所以 ASID 标明这个缓存属于哪一个 process 的。

Replacement policy

LRU:least-recently-used,没啥好说的了。缺点是,面对那种循环 n 次的,然后每一个缓存最后都会被丢掉,还不如 random 好用。

Random:随机删除一个 entry。没有利用 cache 性质,可能缓存命中率不高。但是实现简单,不需要额外的开销存储 LRU。

Random policy is useful due to its simplicity and ability to avoid corner-case behaviors; for example, a “reasonable” policy such as LRU behaves quite unreasonably when a program loops over n + 1 pages with a TLB of size n; in this case, LRU misses upon every access, whereas random does much better.

Smaller Page Tables

假设一个 32bit 的 address space,每一个 page 为 4KB,差不多会存在 100 万个 page-table entry,而且别忘了这只是一个 process,可想而知如此大的 page table 显然是不现实的。

Simple Solution:Bigger Pages

我们让 page 大一点,这样 page table 不就小了。但是过大的 page,会造成 internal fragmentation 更加严重。

Hybrid Approach:Paging and Segments

image-20210429141127324
image-20210429141141820

可以看到,我们 page table 中很多 entry 压根就没用到,这浪费了很多空间。

我们采用一种方法,把一个 page table 划分为多个 page table。例如这里,我们把一个 page table 分成 3 个 page table,分别对应 Code、Heap 和 Stack。然后每一个 page table 一个对属于他们自己的 base + bound register。Base 表示该 segment 的 page table 在物理内存的起始地址,bound 代表该 segment 所含最大 page 数量。

因为考虑到我们增加了 segment,所以把 32bit 的 virtual address 前面两位用作标记 segment。假设 00 为 unused segment,01 for code, 10 for heap, 11 for stack。

image-20210429145903120
image-20210429145719175

SN 为 segment number。VPN 为 virtual page number。PTE 为 page table entry。

使用这种方法,我们能有效避免上面 code、stack、heap 之间未利用空间还占用着 page table entry 的问题。

However, as you might notice, this approach is not without problems. First, it still requires us to use segmentation; as we discussed before, segmentation is not quite as flexible as we would like, as it assumes a certain usage pattern of the address space; if we have a large but sparsely-used heap, for example, we can still end up with a lot of page table waste. Second, this hybrid causes external fragmentation to arise again. While most of memory is managed in page-sized units, page tables now can be of arbitrary size (in multiples of PTEs). Thus, finding free space for them in memory is more complicated. For these reasons, people continued to look for better ways to implement smaller page tables.

Multi-level Page Tables

这种方法和 segment + page 混合方法一样,同时为了消除那些 page table 中 invalid 的 entry。

把 page table 按照 page-size 的大小划分为多个单元,如果该 page 所对应的 page table entry 均为 invalid,那就在 page table 中不分配。

他们搞了一个新结构,叫 page directory。

image-20210502201802927

例如上图,左边是 linear page table,一个 page 能存放 4 个 page table entry。(看右边的图)所以按照 page-size 划分,左边划分为 4 个单元。然后按照 page directory 的设计,中间两个空的就不分配了。有点类似于(indirect inode)。

page directory entry(PDE) 至少拥有 valid bitpage frame number(PFN)。如果 PDE 是 valid,那么代表其指向的 page 中至少包含一个 valid 的 page table entry。

优点:

  • 节省空间,不用的 page 就直接不分配空间。Generally compact and supports sparse address spaces.
  • 分配空间方便,不需要像 linear page table 一样要求内存连续。

缺点:

  • 在 TLB miss 的时候,一次 translation 需要从内存中读取两次,一次为了 page directory entry,另外一次为了 page table entry。
  • 复杂,肯定比 linear page table 麻烦。

假设我们 address space size = 16KB,一个 page 为 64-bytes。因此我们拥有 14-bit virtual address space,8-bit 为 VPN,6-bit 为 offset。一个 linear page table 会有 $2^8=256$ 个 entry。

image-20210502204227603

0,1 为 code。4,5 为 heap。254,255 为 stack。其余均未使用。假设一个 page table entry 为 4 bytes。所以 linear page table 为 1KB(256 x 4 bytes)。

如果我们采用 page directory,1KB page table 划分为 16 64-byte page 的 PTE。1KB page table 有 16个 PTE。

image-20210502204921455

从 VPN 中提取 page-directory index(PDIndex),利用这个寻找 page-directory entry
$$
PDEAddr=PageDirBase + (PDIndex \cdot sizeof(PDE))
$$

找到这个 PDE,如果合法,开始下一步:

image-20210502211126742

锁定 page table index(PTIndex)。
$$
PTEAddr=(PDE.PFN<<SHIFT)+(PTIndex \cdot sizeof(PTE))
$$
上面这个图用 page directory 完整的表示如下:

image-20210502211440786

More Than Two Levels

单层结构其实是远远不够的,假设在 64-bit address space,及时使用了上面的 page directory 方法,PDE 也会占用很大的空间,所以我们可以多套几层。

image-20210502211529938

Inverted Page Tables

相比于一个 process 拥有一个 page table,我们为何不颠倒一下。整个系统只有一个全局的 page table,然后每一个 page table entry 都会标明我属于哪一个 process。这样可以避免每一个 process 公用空间的浪费。当然我们需要额外一个 HashMap 来方便 process 快速找到属于他的 page table entry。

Swap

当 page table entry 对应的 page 不存在时,就会产生 page fault,然后 OS 会处理此 page fault。

image-20210503152815928

当发生 PAGE FAULT 的 exception 时,执行读取磁盘 page 的流程:

image-20210503153117310

Swap: Page Replacement Policies

好的 replacement policy 只有一个目的,尽可能的提高 cache 的命中率,防止从磁盘查找 page 消耗的大量时间。这里使用 average memory access time(AMAT) 进行衡量。
$$
AMAT=T_M+(P_{miss} \cdot T_D)
$$
$T_M$ 为访问内存消耗的时间,$T_D$ 为访问磁盘消耗的时间,$P_{miss}$ 为 cache miss rate。

Optimal 算法为最优算法,当时是不可能实现的。通常是用于参照对照,来看看你的算法效果如何。

Optimal:最次置换,都把最远会使用的 page 先置换出去。但是我们不是先知,不知道哪个会被最远使用。

通常现代操作系统使用 clock algorithm(Approximating LRU)。

具体如下:

https://www.cnblogs.com/wingsless/p/12295246.html
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇