virtual memory

Virtual memory

局部性原理

cache

CPU核心首先从 cache 中寻找数据，当数据不存在时再访问内存，并且将该内存的内容拷贝一份放入缓存。
缓存的长相形如上图黄色部分，每次向缓存读入数据的单位是缓存行，一个缓存行中有8个格子，每个格子大小为 8Byte，故：一个缓存行大小为 64Byte。当缓存中没有指定内容，需要到内存中访问数据时，会将该内存以及后 63Byte，一同拷贝到一个缓存行中

那些数据应该放入缓存中

由大量的实验表明，在进程中，大量被引用的代码和数据常常位于进程地址空间中的某一局部地址，这被称为局部性原理。由于存在局部性原理，使得缓存的命中率变得非常的高

局部性原理

  • 时间局部性(Temporal locality)：如果某个信息这次被访问，那它有可能在不久的未来被多次访问。
  • 空间局部性(Spatial locality)：如果某个位置的信息被访问，那和它相邻的信息也很有可能被访问到。
  • 内存局部性(Memory locality)：访问内存时，大概率会访问连续的块，而不是单一的内存地址，其实就是空 间局部性在内存上的体现。
  • 分支局部性(Branch locality)：计算机中大部分指令是顺序执行，顺序执行和非顺序执行的比例大致是5:1。
  • 等距局部性(Equidistant locality)：等距局部性是指如果某个位置被访问，那和它相邻等距离的连续地址极有可 能会被访问到。

修改缓存

两种方案（保持数据的一致性）：

  • write through：修改缓存数据的同时修改内存数据（效率低下，不仅修改了内存还修改了缓存，不如直接该内存）
  • write back：只修改缓存数据，直到该数据要被清除出 缓存再修改内存中的数据，我们称缓存中被修改的数据为dirty data(脏数据)

缓存数据的淘汰

缓存的容量很小，当缓存满的时候，就需要将缓存中的部分数据淘汰，装入新的数据。 这就需要淘汰算法

  • 淘汰命中次数最少的
  • 淘汰第一个CacheLine 或 最后一个CacheLine

虚拟内存

部分装入和部分对换

  • 部分装入
    • 进程运行时仅加载部分进入内存，而不必全部装入
    • 其余部分暂时放在swap space(交换空间)
  • 部分对换
    • 可以将进程部分对换出内存，用以腾出内存空间
    • 对换出的部分暂时放在swap space

swap space位于磁盘，当进程会将一部分暂时不需要的内容存放在swap space中，当swap space中的内容被需要时将会加载到内存中，这个过程被称为 swap in ， 进程不需要的内容会被存放在swap space中，这个过程被称为 swap out。由于swap in 和 swap out 的存在，导致内存好像变得无限大，这个swap space就被称为虚拟内存

virtual memory

  • Virtual memory is a technique that allows the execution of processes that are not completely(完全地) in memory.(部分装入)
  • One major(主要的) advantage of this scheme(安排) is that programs can be larger than physical memory.
  • Further(此外), virtual memory abstracts(抽象) main memory into an extremely(极度地) large, uniform(统一) array of storage, separating(独立的) logical memory as viewed by the user from physical memory.
  • This technique frees programmers(程序员) from the concerns(关注) of memory-storage limitations(限制).

demand paging 请求调页

linux采用分页机制管理内存，请求调页时基于分页机制的

demand paging

  • With demand-paged virtual memory , pages are loaded only when they are demanded during program execution.
    在需求分页的虚拟内存中，只有在程序执行过程中需要的时候才会加载页面。
  • Pages that are never accessed(访问) are thus never loaded into physical memory.

如图：一个进程被分为7个页面(ABCDEFGH)，只有ACF被装载到内存中（我们称之为内存驻留），其余页面位于虚拟内存中。此时page table内只记录内存驻留的页面，当需要虚拟内存中数据时，当发起请求，成功则执行调页并记录在page table内

请求调页步骤

当逻辑地址 M 被引用时，首先在页表中查询，对应invalue，即此页面没有加载到内存中，将发出缺页中断，将在内核模式下完成调页，将在虚拟内存中找到所要加载的页面，在页框中找到空闲的页框，将其载入，后在页表中记录

请求调页的性能

  • 假设访问内存时间为ma，处理一次缺页中断的时间 记作page fault time，令p为缺页中断的出现几率， 则有效访问时间的计算公式为：

    effective access time = (1 − p) × ma + p × page fault time

  • 若ma=200ns，page fault time=8ms，p=0.001，则

    effective access time = 8200ns

    比直接访问内存慢了40倍

  • 缺页中断率p对性能影响重大

页面置换算法

  • 当进程在执行过程中发生了缺页，在请求调页的时候发现内存已经没有空闲页框可用，操作系统在此时会做出一个处理：页面置换。

  1. 在内存中选取一个页框为victim(牺牲者)，将它放在swap page中保存
  2. 将页表中对应的页框置为invalid
  3. 将所要加载的页面加载到空出的页框中
  4. 将页表中对应页框标记为valid

对于victim的选择就由很大的讲究了，若选的不好，这将大大增加缺页的概率，导致执行时间延长

FIFO

  • 总是淘汰最先进入内存的页面，因为它在内存中待的时间最久。

OPIMAL 最优

  • 总是淘汰未来最长时间不会再使用的页面。

虽然是最优算法，但是不可能实现，因为操作系统不能知道每个页面将应该在何时被使用

LRU（LEAST RECENT UNUSED）

  • 总是淘汰最近最少使用的页面

系统抖动

  • If the process does not have the number of frames it needs to support pages in active use, it will quickly pagefault. At this point, it must replace some page. However, since all its pages are in active use, it must replace a page that will be needed again right away. Consequently, it quickly faults again, and again, and again, replacing pages that it must bring back in immediately.
    如果进程没有它所需要的页框数量来支持正在使用的页面，它将很快出现pagefault。在这一点上，它必须替换一些页面。然而，因为它的所有页面都在使用中，所以它必须替换一个马上就需要的页面 它必须替换一个马上就会再次需要的页面。因此，它迅速地再犯错，再犯错，再犯错，替换那些必须立即恢复的页面。它必须立即恢复。
  • This high paging activity is called thrashing. A process is thrashing if it is spending more time paging than executing.
    这种高分页活动被称为 “抖动”。一个进程如果一个进程花在分页上的时间多于执行的时间。

抖动的原因

开始时，COU利用率随着多道程序的增加而增加，当多道程序持续增多，CPU利用率陡然下降（page faul 出现增多），产出了抖动

  • 并发进程数量过多
  • 进程页框分配不合理

PAGE FAULT FREQUENCY（频率）

  • PFF称作页面故障(频)率，基于这个数据可以实施一个 防止抖动的策略：动态调节分配给进程的页框数量。

使一个进程的 page fault frequency 动态调节位于 upper bound 和 lower bound 之间，这样既不会造成资源的浪费也不会发生过多的缺页

CONCLUDING REMARKS

  • Practically speaking, thrashing and the resulting swapping have a disagreeably large impact on performance.
  • The current best practice in implementing a computer facility is to include enough physical memory, whenever possible, to avoid thrashing and swapping.
  • From smartphones through mainframes, providing enough memory to keep all working sets in memory concurrently, except under extreme conditions, gives the best user experience.