Virtual Memory - 虚拟记忆体

前言：

程式码（program code）储存在硬碟（Hard Disk Memory），当启动执行档执行命令的时候，执行档在随机存取记忆体（RAM）形成一个进程（process），当 CPU 需要时，呼叫各个命令（instruction）完成指令。进程(process)是指一个正在执行的程式，当程式要求被执行时，就会被载入到记忆体中，形成一个进程。在进程中，包括了程式码、资料和堆叠等。

可能的问题

当Process总大小超过RAM时

在一个系统中，RAM的大小是有限的，而program code的大小是不限的。当process的大小超过RAM的大小时，或是多个process同时需要被执行，就会出现系统会因为无法分配更多的 RAM 而无法执行程式

记忆体碎片化导致没有完整的区段可以执行指令的时候

因为记忆体碎片化（Memory Fragmentation）导致没有完整的区段可以执行指令，这样 CPU 在执行指令时，就会因为找不到足够的记忆体而停止执行。

Virtual Memory实现

为了解决记忆体碎片化的问题，现在的系统都会做记忆体虚拟化（Memory Virtualization），也就是给每一个进程（Process）一个完整的虚拟记忆体（Virtual Memory），需要载下来时再对应到实体记忆体（Physical Memory）。
Virtual Memory 可以将碎片化的区块结合成完整的一片给进程（Process）使用，让每一个进程（Process）在执行时都以为得到的是一整块完整的记忆体区块，但实际上可能是碎片化的。

此外，Virtual Memory 的实现需要使用硬碟记忆体（Hard Disk Memory）作为暂存的地方。

功用

允许程式大小大于实体记忆体（Physical Memory），因为 Virtual Memory 可以将整个程式都载入，只有被 CPU 叫到的功能才会被送到 RAM 执行，所以看到的 Virtual Memory 往往会大于实际记忆体用量多很多。每一次的 I/O transfer time 可以下降，因为不用将整个程式的所有 page 载入（然而载入整个程式很耗费 I/O transfer time，因为总传输次数变多）。

实现

Demand Paging（Lazy Loading）

Demand Paging 策略中，程式执行之初不将全部的 pages 载入 memory，而是仅载入执行所需的 pages。如要处理 page fault 问题，由作业系统另行处理。例如，整个系统被载入 Virtual Memory，但需要执行某个 function 时，这个 function 才会从 Virtual Memory 载入到 Physical Memory。

page fault（分页错误）当有些 pages 不在 main memory 时，os必须执行page replacement。先找到一个victim page，并将其swap out到disk来空出一个free frame，再将需求page swap in 到这个frame

Copy-on-Write

在 Copy-on-Write 策略中，如果有多个呼叫者同时要求相同资源（如记忆体或磁碟上的资料储存），则他们会共同取得相同的指标指向相同的资源，直到某个呼叫者试图修改资源的内容时，系统才会真正複製一份专用副本（private copy）给该呼叫者，而其他呼叫者所见到的最初的资源仍然保持不变。因为没有修改就不会产生副本，所以多用来读多写少的开发场景。

Page Replacement Algorithm

Page Replacement Algorithm 是一种分页处理的演算法，用于处理 Virtual Memory 中 page 的选择和置换。若Memory内没有frame可以用时，可以跑可以找一个暂时不用的page，将其清除，供目前需求page使用。

常见的 Page Replacement Algorithm 包括：FIFO（First In First Out）、OPT（Optimal Algorithm）、LRU（Least Recently Used）、LFU（Least Frequently Used）等。

FIFO

当要替换一页page时，系统就去选择记忆体内最久的一个page，也就是最早被载入记忆体的page，将它换成需求的page。可透过FIFO queue来掌握记忆体内的所有分页。

一共发生12次page fault
但是可能会Belady’s Anomaly问题

OPT （最佳演算法）

将长期没用到的page换成需求page，把未来长时间不会用到的page替换掉。（首先要有预知未来的技术）

LRU

把最近不常使用的page替换掉，用过去推测未来。但需要特殊的硬体支援，很少系统能完整的实作。

Counter：利用Counter做一个logical timer，参考page的the last reference time栏位，将来挑 the last reference time 最小的 page (离现在最久)的作为victim pageStack：最近的page会至于stack的top端，bottom端为离先在最久的page，会最先作为victim page换掉

LFU

最不经常使用的 (least frequently used, LFU)演算法让次数最少的那一页被替换掉。