Post

操作系统--内存管理

Posted
By SmallC
19 min read
操作系统--内存管理

为什么要使用虚拟内存的技术 abstract memory？

允许系统允许多道程序并且不会相互影响

Static Relocation

  • 优点： 不需要硬件支持
  • 缺点：
    • 加载慢
    • 一旦加载，程序的代码或数据就不能移动到内存中，除非进行进一步的重新定位。
    • 加载程序需要一些方法来判断什么是地址，什么是常量。

Address Space

地址空间是一组地址，程序可以用来访问内存。

relocation：将程序指令和数据的地址转换为物理地址的过程。

Dynamic Relocation

  • 每个程序的地址空间映射到不同的memory上
  • 需要base和limit两个寄存器，用来存放地址空间的起始地址和size，size是虚拟地址的最大地址。

优点：

  • OS可以轻松的移动程序在执行的时候
  • OS允许程序的内存占用随时间的增长而扩张
  • 简单，快速的硬件

缺点：

  • slow everything
  • 不可以在进程之间共享地址
  • 进程会被物理内存的size所限制
  • 复杂的内存管理

Swapping 交换

因为大部分的程序的大小都超过总内存

Swapping：把整个进程装进内存，运行一段时间放回disk

Virtual memory：允许进程部分装进内存运行

Swapping中会产生很多的extern fraction碎片，需要compaction压缩。

solution：memory manage

  • bitmap
  • linked list：把hole用link连接起来

Storage Placement Strategies

如何从list of hole满足请求大小为n的内存

  • First Fit：使用第一个大小合适的hole
  • Next Fit：找到最后一个合适的hole
  • Best Fit：Use the hole whose size is equal to the need, or if none is equal, the hole that is larger but closest in size.
  • Worst Fit：使用最大的hole
  • Quick Fit：
    • maintains separate lists for some of the more common sizes requested.
    • When a request comes for placement it finds the closest fit.
    • This is a very fast scheme, but a merge is expensive.

Overlaying 覆盖

  • overlaying：把程序分成小片，称为overlays
  • 允许内存中存在一个或几个片，允许不同的overlays使用同一个地址空间
  • overlays的swapping in和swapping out 由OS完成，但切片有程序员完成

Virtual Memory

虚拟内存：重点：把用户的logic memory和physical memory分离开来

  • 提供用户需要的所有内存
  • 虚拟内存存在disk上
  • 只用一部分程序放在内存运行
  • 运行大量的进程创建

Principle of Locality 局部性原则

在操作系统的内存管理中，”局部性原理”（Locality of Reference）指的是在执行过程中，进程只会访问其全部页面中的一小部分。这意味着在任何给定的时间点，进程不需要将所有的页面都加载到物理内存中。这种现象有两种主要形式：

时间局部性（Temporal Locality）：如果一个数据项被访问，那么它很可能在不久的将来再次被访问。例如，循环中使用的变量就展现了时间局部性。

空间局部性（Spatial Locality）：如果一个数据项被访问，那么与它相邻的数据项很可能很快也会被访问。例如，顺序访问数组元素就展现了空间局部性。

虚拟内存的实现

Paging

page frame：物理内存的对应单元

MMU：内存管理单元，负责虚拟地址和物理地址的转化

virtual address：虚拟地址是进程用来访问自己的地址空间的内存地址

Present/Absent bit：追踪当前页是否被映射，也就是是不是合法页

使用没有映射的页会使得CPU陷入内存，这种trap称为page fault，说明当前虚页没有被加载进内存，MMU会选择一个使用过的page，将其和disk中需要的page进行交换。选择算法和page fault的识别是后面的内容。

page table：虚拟地址和物理地址的映射关系。

Paging：映射过程

虚拟地址：page number + offset

page number ：page table的index

offset：page中的偏移量

物理地址：frame number + offset

page table的目的是把virtual page map into page frame

page table

作用：map VPN into PFN 表项entity：PTE 指向的VPN 或者 PFN

page table放在寄存器：简单但是cost

page table放在memory：页表切换很简单，但是多次访问内存

Solution：cache active part of page table

  • TLBs，也称为associative memory

把常用的entry缓存起来

Bits in a TLB Entry

同样是应用了局部性原则

  • Virtual page Number
  • Physical page number
  • Valid
  • Access bit：kernel and user

进行paging的时候，优先根据virtual page number对TLB进行搜索查看有没有被缓存

如何查到是valid的，直接实现翻译，不用再访问page table；

如果是not valid的，进行普通的page table映射，然后把这个TLB表项替代成当前找到的page table entry。

TLB hit ratio

Hardware-Controlled TLB On a TLB miss

  • Hardware loads the PTE (Page Table Entry) into the TLB
    • Need to write back if there is no free entry
  • Generate a fault if the page containing the PTE is invalid
  • VM software performs fault handling
  • Restart the CPU

On a TLB hit, hardware checks the valid bit

  • If valid, pointer to page frame in memory
  • If invalid, the hardware generates a page fault
    • Perform page fault handling
    • Restart the faulting instruction

Software-Controlled TLB

On a miss in TLB, generate a TLB fault, then trap to OS (software)

  • Check if the page containing the PTE is in memory
  • If no, perform page fault handling
  • Write back if there is no free entry, then load the PTE into the TLB
  • Restart the faulting instruction

On a hit in TLB, the hardware checks valid bit

  • If valid, pointer to page frame in memory
  • If invalid, the hardware generates a page fault
    • Perform page fault handling
    • Restart the faulting instruction

Multilevel Page Table 多级页表

通过层次化的多张页表来负责地址转换

  • 减小页表的大小
  • 不用加载不需要的页表进入内存

Inverted Page Tables

一个physical page frame对应一张PTE。

物理page number是这张表的index

Vpage+pid hash到 Ppagenumber

Linear Inverted Page Tables

整个物理内存只有一张表，且一个physical page frame对应一张PTE。

表项为 process + virtual page

The physical page number is used as an index into the table

使用方法：就是对整张表进行搜索，查看哪个表项和提供的pid和virtualpagenum一致，该index就是对应的Ppagenumber

Lookup is difficult

Hashed Inverted Page Tables

在page table前添加一个hash表，The process ID and virtual page number are hashed to get an entry in the hash table，When hashing with hash table, there may be conflicts, which can be solved by using chain address method，Add the next field in the inverted page table items to form a linked list (the index of the header is in the hash table)

不用线性搜索了

  • 管理hash链消耗

Memory Management

Fetch Strategies：Demand Fetching

只有在需要的时候才把页表写进内存。什么时候知道该页表被需要呢？

  • 发生Page fault的时候
  • 检查发现虚存地址非法
  • 如果地址合法，检查是否在内存中有缓存
  • 如果没有，在内存中找到一张free的page frame
  • 把地址map到disk block，fetch disk block到page frame，阻塞用户进程
  • 等待disk read 完成，添加vm mapping for page frame
  • 重启进程

page fault发生时，把需要的page和相邻的page装进memory

Page Replacement

当发生page fault但没有多余的free page frame时 需要replace

Page Replacement Algorithm

Reference string：一个序列，用来模拟或记录一个程序执行时访问内存地址的顺序，可以用来评估页面置换算法，计算按照引用串访问带来的page fault次数。

1 The Optimal Algorithm

最优页面置换算法（Optimal Page Replacement Algorithm）是一种理论上的页面置换策略，用于决定当发生页面错误（page fault）且没有空闲页面帧时，应该替换哪个页面。该算法的目标是最小化页面错误的总数。

最优算法的工作原理是：当需要替换一个页面时，它会选择那个在未来最长时间内不会被访问的页面进行替换。因为这种算法需要知道未来的页面访问序列，所以在实际操作系统中是不可实现的。然而，它在理论研究中非常有用，因为它提供了其他页面置换算法性能的上限（即最好情况）。

简而言之，最优页面置换算法可以告诉我们在给定的引用串下，页面错误的最小可能数量是多少，但由于它需要未来的知识，因此不能在实际的操作系统中实现。

2 FIFO 页面置换算法

  1. 维护一个队列，记录所有加载到内存中的页面的顺序。
  2. 当一个新页面需要被加载到内存中，而内存已满时，算法会选择队列中最早进入的页面进行替换。
  3. 被替换的页面会从队列中移除，新加载的页面加入队列的末尾。

优点：实现简单

缺点：最旧的页面可能会经常使用

Belady‘s anomaly

Belady的异常是指在使用某些页面置换算法（尤其是FIFO算法）时，系统为进程分配的物理内存帧数量增加，反而导致页面错误率增加的现象。这一异常直观上违反了常识，因为我们通常期望可用内存增加时，页面错误会减少，程序运行效率会提高。

paging system的三大组成：

  • reference string
  • page replacement 算法
  • 内存中可用的page frames

3 Second Chance Page Replacement 算法

二次机会页面置换算法（Second Chance Page Replacement Algorithm），也称为时钟算法（Clock Algorithm），是一种改进的FIFO页面置换算法。它试图克服FIFO算法的主要缺点，即盲目地按照页面进入内存的顺序进行置换，而不考虑页面的使用情况。二次机会算法通过给每个页面一个“二次机会”来避免将频繁使用的页面置换出去

Inspect R bit

算法过程如下：

初始化：维护一个循环队列，每个页面项包含一个访问位（Inspect R bit），初始时所有页面的访问位都设置为0。 页面访问：当一个页面被访问时，其对应的访问位设置为1。 页面置换： 当需要置换一个页面时，算法从当前指针位置开始扫描循环队列。 如果遇到的第一个页面的访问位为1，则将其设置为0，并给这个页面一个“二次机会”，然后移动到下一个页面。 如果遇到的页面访问位为0，则选择这个页面进行置换，并将新页面插入其位置。 这个过程像时钟的指针一样循环进行，因此得名“时钟算法”。

4 Clock Page Replacement Algorithm

3的另一个实现

5 Not Recently Used Replacement 算法

Each page has Reference bit(R) and Modified bit(M).

  • bits are set when page is referenced (read or written recently), modified (written to)
  • when a process starts, both bits R and M are set to 0 for all pages.
  • periodically, (on each clock interval (20msec) ), the R bit is cleared. (i.e. R=0).

page会被定义成四个状态：

  • Class 0: not referenced, not modified
  • Class 1: not referenced, modified
  • Class 2: referenced, not modified
  • Class 3: referenced, modified

数字越小，替代的优先级越大

NFU (Not Frequently Used) is implemented in software.

  • At each clock interrupt, the R bit is added to the counter associated with each page. When a page fault occurs, the page with the lowest counter is replaced.
  • Problem: NFU never forgets, so a page referenced frequency long ago may have the highest counter.

Modified NFU = NFU with Aging - at each clock interrupt:

  • the counters are shifted right one bit, and
  • the R bits are added to the leftmost bit.
  • In this way, we can give higher priority to recent R values

6 Least Recently Used

throw out page that has been unused for longest time

实现：

  • 软件：维持一个linked list of pages，被使用过的放在前面，其余的放后面，cost！
  • 硬件：
    • a 64 bit counter
      • 这个计数器会不断增长，调用内存后，再页表项中添加当前的counter的值
      • replace的时候选择counter value最小的值。
      • 周期性的清空counter，不然装不下
    • a nXn bits 的矩阵（n个page）
      • When page frame K is referenced:
        1. Set row K to all 1s.
        2. Set column K to all 0s.
      • The row whose binary value is smallest is the LRU page.

7 The Working Set Page Replacement 算法

The working set is the set of pages used by the k most recent memory references

w(k,t) is the size of the working set at time t

算法思想：

当page fault 发生时，选择一个不子啊工作集中的page替换他

同样是局部性原理的体现！

进程开始执行后，随着访问新页面逐步建立较稳定的工作集。 当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定； 局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。

对所有的page进行span，如果R==1，set time of last use to current virtual time，如果R==0且age>t则remove page，如果age< t remember the smallest time

如果没有age>t的，就选择age最大的

8 WSClock Page Replacement 算法

Page Size

overhead = se/p + p/2

Segmentation

segmentation：为机器提供多个独立的 地址空间。

segmented memory 允许 each table 生长

A program is a collection of segments. A segment is a logical unit such as Main program Procedure Function Symbol table Stack

Segmentation Architecture

Logical address consists of two parts: < virtual segment-number, offset >

Segment table

Maps two-dimensional user-defined addresses into one-dimensional physical addresses

The virtual segment number is used as an index to the segment table

Segmentation with paging

  • Segmentation in virtual memory, paging in physical memory
  • A segment is composed of pages
  • An address has three components：segmentNumber+pageNumber+offset
操作系统
This post is licensed under CC BY 4.0 by the author.