页面置换算法-LRU,FIFO,LFU---golang实现

页面置换算法

什么是Cache？狭义的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache， 内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。

前提的数据结构

不管是在fifo,lru,lfu的cache中,其底层数据结构都是双向链表加hashmap实现的

go语言实现双向链表数据结构

package DoubleLinked

import (
	"fmt"
	"strings"
)

type Node struct {
	key interface{}
	value interface{}
	prev,next *Node
}

// 实现打印方法
func (this Node) String() string {
	builder := strings.Builder{}
	fmt.Fprintf(&builder,"{%v : %v}",this.key,this.value)
	return builder.String()
}

func InitNode(key,value interface{}) *Node {
	return &Node{
		key:key,
		value:value,
	}
}

type List struct {
	capacity int
	head *Node
	tail *Node
	size int
}
// 列表的初始化方法
func InitList(capcity int) *List {
	return &List{
		capacity:capcity,
		size:0,
	}
}
// 在双向链表中的头结点后添加节点
func (this *List) addHead (node *Node) *Node {
	if this.head == nil {
		this.head = node
		this.tail = node
		this.head.prev = nil
		this.tail.next = nil
	} else {
		node.next = this.head
		this.head.prev = node
		this.head = node
		this.head.prev = nil
	}
	this.size++
	return node
}
// 在双向链表中的尾节点前添加节点
func (this *List)addTail(node *Node) *Node {
	if this.tail == nil {
		this.tail = node
		this.head = node
		this.head.prev = nil
		this.tail.next = nil
	} else {
		this.tail.next = node
		node.prev = this.tail
		this.tail = node
		this.tail.next = nil
	}
	this.size++
	return node
}
// 删除尾节点
func (this *List) removeTail() *Node {
	if this.tail == nil {
		return nil
	}
	node := this.tail
	if node.prev != nil {
		this.tail = node.prev
		this.tail.next = nil
	} else {
		this.tail = nil
		this.head = nil
	}
	this.size--
	return node
}
// 删除头结点
func (this *List) removeHead() *Node {
	if this.head == nil {
		return nil
	}
	node := this.head
	if node.next != nil {
		this.head = node.next
		this.head.prev = nil
	} else {
		this.tail = nil
		this.head = nil
	}
	this.size--
	return node
}
// 删除某一个双向链表中的节点
func (this *List)remove(node *Node) *Node {
	// 如果node==nil,默认删除尾节点
	if node == nil {
		node = this.tail
	}
	if node == this.tail {
		this.removeTail()
	} else if node == this.head {
		this.removeHead()
	} else {
		node.next.prev = node.prev
		node.prev.next = node.next
		this.size--
	}
	return node
}
// 弹出头结点
func (this *List)Pop() *Node {
	return this.removeHead()
}

// 添加节点,默认添加到尾部
func (this *List)Append(node *Node) *Node {
	return this.addTail(node)
}
func (this *List)AppendToHead(node *Node) *Node {
	return this.addHead(node)
}

func (this *List)Remove(node *Node) *Node {
	return this.remove(node)
}

func (this *List)String() string {
	p := this.head
	builder := strings.Builder{}
	for p != nil {
		fmt.Fprintf(&builder,"%s",p)
		p = p.next
		if p != nil {
			fmt.Fprintf(&builder,"=>")
		}
	}
	return builder.String()
}

FIFOCache

FIFO（First in First out），先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想，比如作业调度（先来先服务），为什么这个原则在很多地方都会用到呢？因为这个原则简单、且符合人们的惯性思维，具备公平性，并且实现起来简单，直接使用数据结构中的队列即可实现。

在FIFO Cache设计中，核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。在FIFO Cache中应该支持以下操作;

Get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；

Put(key,value)：如果Cache中存在该key，则重置value值；如果不存在该key，则将该key插入到到Cache中，若Cache已满，则淘汰最早进入Cache的数据。

FIFOCache实现代码

package DoubleLinked

import "fmt"

type FIFOCache struct {
	capacity int
	size int
	list *List
	find map[interface{}]*Node
	k int
	// count记录缺页中断的次数
	count int
}

func InitFIFO(capacity int) *FIFOCache {
	return &FIFOCache{
		capacity:capacity,
		find: map[interface{}]*Node{},
		list:InitList(capacity),
	}
}

func (this *FIFOCache)GetCount() int {
	return this.count
}

func (this *FIFOCache)Get(key interface{}) interface{} {
	if value,ok := this.find[key];!ok{
		this.k = this.k%this.capacity
		node := this.list.head
		for i:=0;i<this.k;i++ {
			node = node.next
		}
		fmt.Println("发生了一次缺页中断")
		delete(this.find,node.key)
		node.key = key
		this.find[key] = node
		this.k++
		this.count++
		return -1
	} else {
		node := value
		return node.value
	}
}

func (this *FIFOCache)Put(key,value interface{})  {
	if this.capacity == 0 {
		return
	}
	if v,ok := this.find[key];ok {
		node := v
		this.list.Remove(node)
		node.value = value
		this.list.Append(node)
	} else {
		if this.size == this.capacity {
			node := this.list.Pop()
			delete(this.find,node.key)
			this.size--
		}
		node := InitNode(key,value)
		this.list.Append(node)
		this.find[key] = node
		this.size++
	}
}

func (this *FIFOCache)String() string {
	return this.list.String()
}

测试数据和测试代码

实现过程：假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：7, 0, 1, 2, 0, 3, 0,4,2,3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。釆用FIFO算法进行页面置换，进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。由下图可以看出，利用FIFO算法时进行了12次页面置换。

访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0
物理块1	7	7	7	2		2	2	4	4	4	0			0	0			7	7
物理块2		0	0	0		3	3	3	2	2	2			1	1			1	0
物理块3			1	1		1	0	0	0	3	3			3	2			2	2
缺页否	√	√	√	√		√	√	√	√	√	√			√	√			√	√

package DoubleLinked

import (
	"fmt"
	"math/rand"
	"os"
	"testing"
)

func TestFIFO(t *testing.T)  {

	var (
		file *os.File
		err error
	)
	if file, err = os.Open("test.txt"); err != nil {
		return
	}
	defer file.Close()
	Fifo := InitFIFO(3)
	for i:=0;i<3;i++ {
		var key int
		fmt.Fscanf(file,"%d",&key)
		Fifo.Put(key,rand.Intn(100))
	}
	t.Log(Fifo)
	for {
		var key int
		if _,err = fmt.Fscanf(file,"%d",&key);err!=nil{
			break
		} else {
			Fifo.Get(key)
		}
		t.Log(Fifo)
	}
	t.Log("程序正常退出,一共发生",Fifo.count,"次缺页中断")
}

测试结果

什么是LRU Cache

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。

Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

数据结构

LRU的典型实现是hash map + doubly linked list， 双向链表用于存储数据结点，并且它是按照结点最近被使用的时间来存储的。 **如果一个结点被访问了， 我们有理由相信它在接下来的一段时间被访问的概率要大于其它结点。**于是， 我们把它放到双向链表的头部。当我们往双向链表里插入一个结点， 我们也有可能很快就会使用到它，同样把它插入到头部。 我们使用这种方式不断地调整着双向链表，链表尾部的结点自然也就是最近一段时间， 最久没有使用到的结点。那么，当我们的Cache满了， 需要替换掉的就是双向链表中最后的尾节点(如果你使用的双向链表有虚拟头尾节点,那么这里就是尾节点的前驱节点.)

哈希表的作用是什么呢？如果没有哈希表，我们要访问某个结点，就需要顺序地一个个找， 时间复杂度是O(n)。使用哈希表可以让我们在O(1)的时间找到想要访问的结点， 或者返回未找到。

代码实现

package DoubleLinked

import "fmt"

type LRUCache struct {
	capacity int
	find map[interface{}]*Node
	list *List
	k int
	count int
}

func InitLRU(capacity int) *LRUCache {
	return &LRUCache{
		capacity:capacity,
		list:InitList(capacity),
		find:make(map[interface{}]*Node),
	}
}

func (this *LRUCache)Get(key interface{}) interface{} {
	if value,ok := this.find[key];ok{
		node := value
		this.list.Remove(node)
		this.list.AppendToHead(node)
		return node.value
	} else {
		node := this.list.removeTail()
		fmt.Println("发生了一次缺页中断")
		delete(this.find,node.key)
		node.key = key
		this.find[key] = node
		this.list.AppendToHead(node)
		this.count++
		return -1
	}
}

func (this *LRUCache)Put(key,value interface{})  {
	if v,ok := this.find[key];ok {
		node := v
		this.list.Remove(node)
		node.value = value
		this.list.AppendToHead(node)
	} else {
		node := InitNode(key,value)
		// 缓存已经满了
		if this.list.size >= this.list.capacity {
			oldNode := this.list.Remove(nil)
			delete(this.find,oldNode.value)
		}
		this.list.AppendToHead(node)
		this.find[key] = node
	}
}

func (this *LRUCache)String() string {
	return this.list.String()
}

测试数据和FIFOCache相同,测试结果如下

LFUCache

LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。
注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。举个简单的例子：
假设缓存大小为3，数据访问序列为set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4),则在set(4,4)时对于LFU算法应该淘汰(3,3)，而LRU应该淘汰(1,1)。

为了能够淘汰最少使用的数据，因此LFU算法的一种设计思路就是利用一个双向链表存储数据项，用一个hashmap存储这个key和对应的双向链表中的Node的地址，当数据项被命中时，访问频次自增，用另一个hashmap记录对应频次和这个频次所对应的双向链表,在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，最低频次所对应的双向链表删除掉头结点,同时把新节点放置到频率为1的双向链表中,时间复杂度也是O(1)。

实现代码

package DoubleLinked

import (
	"fmt"
	"math"
	"strings"
)

type LFUNode struct {
	freq int
	node *Node
}

func InitLFUNode(key,value interface{}) *LFUNode {
	return &LFUNode{
		freq:0,
		node:InitNode(key,value),
	}
}

type LFUCache struct {
	capacity int
	find map[interface{}]*LFUNode
	freq_map map[int]*List
	size int
	count int
}

func InitLFUCahe(capacity int) *LFUCache {
	return &LFUCache{
		capacity:capacity,
		find: map[interface{}]*LFUNode{},
		freq_map: map[int]*List{},
	}
}
// 更新节点的频率
func (this *LFUCache)updateFreq(node *LFUNode)  {
	freq := node.freq
	// 删除
	node.node = this.freq_map[freq].Remove(node.node)
	if this.freq_map[freq].size == 0 {
		delete(this.freq_map,freq)
	}

	freq++
	node.freq = freq
	if _,ok := this.freq_map[freq]; !ok {
		this.freq_map[freq] = InitList(10)
	}
	this.freq_map[freq].Append(node.node)
}
func findMinNum (fmp map[int]*List) int {
	min := math.MaxInt32
	for key,_ := range fmp {
		min = func(a,b int) int {
			if a > b {
				return b
			}
			return a
		}(min,key)
	}
	return min
}
func (this *LFUCache)Get(key interface{}) interface{} {
	if _,ok := this.find[key]; !ok {
		min_freq := findMinNum(this.freq_map)
		list := this.freq_map[min_freq]
		node := list.head
		fmt.Println("发生了一次缺页中断")
		// 先取到这个节点的地址
		newNode := this.find[node.key]
		// 从节点的映射中删掉这个节点
		delete(this.find,node.key)
		// 赋值新的key
		newNode.node.key = key
		this.find[key] = newNode
		// 在链表中真正的删除这个节点,并且删除后如果链表的长度为0,在频率映射表中吧这个链表删掉
		list.Remove(newNode.node)
		if list.size == 0{
			delete(this.freq_map,newNode.freq)
		}
		newNode.freq = 0
		if _,ok := this.freq_map[0]; !ok {
			this.freq_map[0] = InitList(10)
		}
		this.freq_map[0].Append(newNode.node)
		this.updateFreq(newNode)
		this.count++
		return -1
	}
	node := this.find[key]
	this.updateFreq(node)
	return node.node.value
}

func (this *LFUCache) Put (key,value interface{})  {
	if this.capacity == 0 {
		return
	}
	// 命中缓存
	if _,ok := this.find[key] ; ok {
		node := this.find[key]
		node.node.value = value
		this.updateFreq(node)
	} else {
		if this.capacity == this.size {
			// 找到一个最小的频率
			min_freq := findMinNum(this.freq_map)
			node := this.freq_map[min_freq].Pop()
			lfuNode := &LFUNode{
				node:node,
				freq:1,
			}
			this.find[key] = lfuNode
			delete(this.find,node.key)
			this.size--
		}
		node := InitLFUNode(key,value)
		node.freq = 1
		this.find[key] = node
		if _,ok := this.freq_map[node.freq]; !ok {
			this.freq_map[node.freq] = InitList(math.MaxInt32)
		}
		node.node = this.freq_map[node.freq].Append(node.node)
		this.size++
	}
}

func (this *LFUCache)String() string {
	builder := strings.Builder{}
	fmt.Fprintln(&builder,"*******************")
	for k,v := range this.freq_map {
		fmt.Fprintf(&builder,"Freq = %d\n",k)
		fmt.Fprintln(&builder,v.String())
	}
	fmt.Fprintln(&builder,"*******************")
	return builder.String()
}

测试代码和测试结果

package DoubleLinked

import (
	"fmt"
	"math/rand"
	"os"
	"testing"
)

func TestInitLFUCahe(t *testing.T) {
	var (
		file *os.File
		err error
	)
	if file, err = os.Open("test.txt"); err != nil {
		return
	}
	defer file.Close()
	LFU := InitLFUCahe(3)
	for i:=0;i<3;i++ {
		var key int
		fmt.Fscanf(file,"%d",&key)
		LFU.Put(key,rand.Intn(100))
	}
	t.Log(LFU)
	for {
		var key int
		if _,err = fmt.Fscanf(file,"%d",&key);err!=nil{
			break
		} else {
			t.Log(LFU.Get(key))
		}
		t.Log(LFU)
	}
	t.Log("程序正常退出,一共发生",LFU.count,"次缺页中断")
}

--- PASS: TestInitLFUCahe (0.01s)
    LFU_test.go:25: *******************
        Freq = 1
        {7 : 81}=>{0 : 87}=>{1 : 47}
        *******************
        
    LFU_test.go:31: -1
    LFU_test.go:33: *******************
        Freq = 1
        {0 : 87}=>{1 : 47}=>{2 : 81}
        *******************
        
    LFU_test.go:31: 87
    LFU_test.go:33: *******************
        Freq = 1
        {1 : 47}=>{2 : 81}
        Freq = 2
        {0 : 87}
        *******************
        
    LFU_test.go:31: -1
    LFU_test.go:33: *******************
        Freq = 2
        {0 : 87}
        Freq = 1
        {2 : 81}=>{3 : 47}
        *******************
        
    LFU_test.go:31: 87
    LFU_test.go:33: *******************
        Freq = 1
        {2 : 81}=>{3 : 47}
        Freq = 3
        {0 : 87}
        *******************
        
    LFU_test.go:31: -1
    LFU_test.go:33: *******************
        Freq = 1
        {3 : 47}=>{4 : 81}
        Freq = 3
        {0 : 87}
        *******************
        
    LFU_test.go:31: -1
    LFU_test.go:33: *******************
        Freq = 1
        {4 : 81}=>{2 : 47}
        Freq = 3
        {0 : 87}
        *******************
        
    LFU_test.go:31: -1
    LFU_test.go:33: *******************
        Freq = 1
        {2 : 47}=>{3 : 81}
        Freq = 3
        {0 : 87}
        *******************
        
    LFU_test.go:31: 87
    LFU_test.go:33: *******************
        Freq = 1
        {2 : 47}=>{3 : 81}
        Freq = 4
        {0 : 87}
        *******************
        
    LFU_test.go:31: 81
    LFU_test.go:33: *******************
        Freq = 1
        {2 : 47}
        Freq = 4
        {0 : 87}
        Freq = 2
        {3 : 81}
        *******************
        
    LFU_test.go:31: 47
    LFU_test.go:33: *******************
        Freq = 4
        {0 : 87}
        Freq = 2
        {3 : 81}=>{2 : 47}
        *******************
        
    LFU_test.go:31: -1
    LFU_test.go:33: *******************
        Freq = 1
        {1 : 81}
        Freq = 4
        {0 : 87}
        Freq = 2
        {2 : 47}
        *******************
        
    LFU_test.go:31: 47
    LFU_test.go:33: *******************
        Freq = 3
        {2 : 47}
        Freq = 1
        {1 : 81}
        Freq = 4
        {0 : 87}
        *******************
        
    LFU_test.go:31: 87
    LFU_test.go:33: *******************
        Freq = 1
        {1 : 81}
        Freq = 5
        {0 : 87}
        Freq = 3
        {2 : 47}
        *******************
        
    LFU_test.go:31: 81
    LFU_test.go:33: *******************
        Freq = 2
        {1 : 81}
        Freq = 5
        {0 : 87}
        Freq = 3
        {2 : 47}
        *******************
        
    LFU_test.go:31: -1
    LFU_test.go:33: *******************
        Freq = 1
        {7 : 81}
        Freq = 5
        {0 : 87}
        Freq = 3
        {2 : 47}
        *******************
        
    LFU_test.go:31: 87
    LFU_test.go:33: *******************
        Freq = 1
        {7 : 81}
        Freq = 6
        {0 : 87}
        Freq = 3
        {2 : 47}
        *******************
        
    LFU_test.go:31: -1
    LFU_test.go:33: *******************
        Freq = 1
        {1 : 81}
        Freq = 6
        {0 : 87}
        Freq = 3
        {2 : 47}
        *******************
        
    LFU_test.go:35: 程序正常退出,一共发生 8 次缺页中断
PASS