虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。
从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。
内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。
一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。
下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 （110 000000000100）。
在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。(word)
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。
此时需要注意的是，就是在置换算法或者策略的时候要注意减少抖动，此时就需要用到如下的几种置换算法了，根据算法的特性和程序的特性来选择合适的替换算法。
- 算法本身（LRU或者FIFO算法）
- 程序本身（goto无条件跳转，避免动态程序）
缺页率 = (页面置换次数+分配给该进程的物理块数)/要访问的页面总数
计算公式： $$ 缺页率(F) = \frac{(页面置换次数+分配给该进程的物理块数)}{要访问的页面总数} $$
- 块size大小 ：块越大，F越小==（但是程序会退化到原来的分区管理）==
- 增加分配给该进程的块数==（但是程序会退化到页式管理）==
- 算法
OPT, Optimal replacement algorithm
所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。
是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。
举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。
LRU, Least Recently Used
虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。
为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
比如说按照组成原理来讲，一个指令如果指令周期是3个周期（例如LAD取数指令，是RS型指令）
那么还需要访问页表甚至是硬盘，最少就需要五个周期。
4，7，0，7，1，0，1，2，1，2，6
NRU, Not Recently Used
每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：
- R=0，M=0
- R=0，M=1
- R=1，M=0
- R=1，M=1
当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。
NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
FIFO, First In First Out
选择换出的页面是最先进入的页面。
该算法会将那些经常被访问的页面换出，导致缺页率升高。
FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
Clock
第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。
虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。
下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。
分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。
程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
-
对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
-
地址空间的维度：分页是一维地址空间，分段是二维的。
-
大小是否可以改变：页的大小不可变，段的大小可以动态改变。
-
出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
计算并输出下述各种算法在内存容量为3块、4块下的缺页率。
如上图示，实现 fifo算法 的缓存架构图：
fifo 算法是淘汰缓存中最早添加的记录,即一个数据最先进入缓存，那么也应该最先被删除掉(队列先进先出)。 算法的实现比较简单：创建一个队列（一般通过双链表实现），新增记录添加到队首，淘汰队尾记录
-
map 用来存储键值对。这是实现缓存最简单直接的数据结构，因为它的查找记录和增加记录时间复杂度都是 O(1)
-
list.List 是go标准库提供的双链表。
通过这个双链表存放具体的值，移动任意记录到队首的时间复杂度都是 O(1)， 在队首增加记录的时间复杂度是 O(1)，删除任意一条记录的时间复杂度是 O(1)
FIFO代码实现如下：
需要用到go_package中的list包，介绍：
LISt概述¶
包列表实现了一个双向链表。
遍历一个列表（其中 l 是一个 *List）：
if e := l.Front(); e != nil e = e.Next() {
// 用 e.Value 做一些事情
}还用到了runtime包，包的介绍：
Package runtime contains operations that interact with Go's runtime system, such as functions to control goroutines. It also includes the low-level type information used by the reflect package; see reflect's documentation for the programmable interface to the run-time type system.
包运行时包含与Go运行时系统交互的操作，比如控制goroutines的函数。它还包括反射包使用的低级类型信息;有关运行时类型系统的可编程接口，请参阅reflect的文档。
runtime 调度器是个非常有用的东西，关于 runtime 包几个方法:
- **NumCPU：**返回当前系统的 CPU 核数量
- **GOMAXPROCS：**设置最大的可同时使用的 CPU 核数 通过runtime.GOMAXPROCS函数，应用程序何以在运行期间设置运行时系统中得P最大数量。但这会引起“Stop the World”。所以，应在应用程序最早的调用。并且最好是在运行Go程序之前设置好操作程序的环境变量GOMAXPROCS，而不是在程序中调用runtime.GOMAXPROCS函数。 无论我们传递给函数的整数值是什么值，运行时系统的P最大值总会在1~256之间。
go1.8后，默认让程序运行在多个核上,可以不用设置了 go1.8前，还是要设置一下，可以更高效的利益cpu
- **Gosched：**让当前线程让出 cpu 以让其它线程运行,它不会挂起当前线程，因此当前线程未来会继续执行 这个函数的作用是让当前 goroutine 让出 CPU，当一个 goroutine 发生阻塞，Go 会自动地把与该 goroutine 处于同一系统线程的其他 goroutine 转移到另一个系统线程上去，以使这些 goroutine 不阻塞。
- **Goexit：**退出当前 goroutine(但是defer语句会照常执行)
- **NumGoroutine：**返回正在执行和排队的任务总数 runtime.NumGoroutine函数在被调用后，会返回系统中的处于特定状态的Goroutine的数量。这里的特指是指Grunnable\Gruning\Gsyscall\Gwaition。处于这些状态的Groutine即被看做是活跃的或者说正在被调度。 注意：垃圾回收所在Groutine的状态也处于这个范围内的话，也会被纳入该计数器。
- **GOOS：**目标操作系统
- **runtime.GC：**会让运行时系统进行一次强制性的垃圾收集 1.强制的垃圾回收：不管怎样，都要进行的垃圾回收。2.非强制的垃圾回收：只会在一定条件下进行的垃圾回收（即运行时，系统自上次垃圾回收之后新申请的堆内存的单元（也成为单元增量）达到指定的数值）。
- **GOROOT：**获取goroot目录
- GOOS : 查看目标操作系统 很多时候，我们会根据平台的不同实现不同的操作，就而已用GOOS了
为我们创建一个FIFO的队列有一个很好的帮助
// TODO: 定义cache接口
type Cache interface {
// 设置/添加一个缓存，如果key存在，则用新值覆盖旧值
Set(key string, value interface{})
// 通过key获取一个缓存值
Get(key string) interface{}
// 通过key删除一个缓存值
Del(key string)
// 删除 '最无用' 的一个缓存值
DelOldest()
// 获取缓存已存在的元素个数
Len() int
// 缓存中 元素 已经所占用内存的大小
UseBytes() int
}
// TODO: 结构体，数组，切片，map,要求实现 Value 接口，该接口只有1个 Len 方法，返回占用内存的字节数
type Value interface {
Len() int
}
// TODO: 定义fifo结构体
type fifo struct {
// 缓存最大容量，单位字节
// groupCache 使用的是最大存放 entry个数
maxBytes int
// 已使用的字节数，只包括值， key不算
usedBytes int
// 双链表
ll *list.List
// map的key是字符串，value是双链表中对应节点的指针
cache map[string]*list.Element
}
// TODO: 定义key,value 结构
type entry struct {
key string
value interface{}
}
// TODO: 计算出元素占用内存字节数
func (e *entry) Len() int {
return CalcLen(e.value)
}
// TODO: 计算value占用内存大小
func CalcLen(value interface{}) int {
var n int
switch v := value.(type) {
case Value: // 结构体，数组，切片，map,要求实现 Value 接口，该接口只有1个 Len 方法，返回占用的内存字节数，如果没有实现该接口，则panic
n = v.Len()
case string:
if runtime.GOARCH == "amd64" {
n = 16 + len(v)
} else {
n = 8 + len(v)
}
case bool, int8, uint8:
n = 1
case int16, uint16:
n = 2
case int32, uint32, float32:
n = 4
case int64, uint64, float64:
n = 8
case int, uint:
if runtime.GOARCH == "amd64" {
n = 8
} else {
n = 4
}
case complex64:
n = 8
case complex128:
n = 16
default:
panic(fmt.Sprintf("%T is not implement cache.value", value))
}
return n
}
// TODO: 构造函数，创建一个新 Cache，如果 maxBytes 是0，则表示没有容量限制
func NewFifoCache(maxBytes int) Cache {
return &fifo{
maxBytes: maxBytes,
ll: list.New(),
cache: make(map[string]*list.Element),
}
}
// TODO: 通过 Set 方法往 Cache 头部增加一个元素（如果已经存在，则移到头部，并修改值）
func (f *fifo) Set(key string, value interface{}) {
if element, ok := f.cache[key]; ok {
f.ll.MoveToFront(element)
eVal := element.Value.(*entry)
f.usedBytes = f.usedBytes - CalcLen(eVal.value) + CalcLen(value) // 更新占用内存大小
element.Value = value
} else {
element := &entry{key, value}
e := f.ll.PushFront(element) // 头部插入一个元素并返回该元素
f.cache[key] = e
f.usedBytes += element.Len()
}
// 如果超出内存长度，则删除队首的节点
for f.maxBytes > 0 && f.maxBytes < f.usedBytes {
f.DelOldest()
}
}
// TODO: 获取指定元素
func (f *fifo) Get(key string) interface{} {
if e, ok := f.cache[key]; ok {
return e.Value.(*entry).value
}
return nil
}
// TODO: 删除指定元素
func (f *fifo) Del(key string) {
if e, ok := f.cache[key]; ok {
f.removeElement(e)
}
}
// TODO: 删除最 '无用' 元素
func (f *fifo) DelOldest() {
f.removeElement(f.ll.Back())
}
// TODO: 删除元素并更新内存占用大小
func (f *fifo) removeElement(e *list.Element) {
if e == nil {
return
}
f.ll.Remove(e)
en := e.Value.(*entry)
f.usedBytes -= en.Len()
delete(f.cache, en.key)
}
// TODO: 缓存中元素个数
func (f *fifo) Len() int {
return f.ll.Len()
}
// TODO: 缓存池占用内存大小
func (f *fifo) UseBytes() int {
return f.usedBytes
}测试
测试：
func TestFifoCache(t *testing.T) {
cache := NewFifoCache(512)
key := "k1"
cache.Set(key, 1)
fmt.Printf("cache 元素个数：%d, 占用内存 %d 字节\n\n", cache.Len(), cache.UseBytes())
val := cache.Get(key)
fmt.Println(cmp.Equal(val, 1))
cache.DelOldest()
fmt.Printf("cache 元素个数：%d, 占用内存 %d 字节\n\n", cache.Len(), cache.UseBytes())
}
----------------------------------------------------------------------------------------------------------
结果：
=== RUN TestFifoCache
cache 元素个数：1, 占用内存 8 字节
true
cache 元素个数：0, 占用内存 0 字节
--- PASS: TestFifoCache (0.00s)
PASS