操作系统之页面置换算法-OPT，FIFO，LRU，CLOCK

写在前面

在进程运行过程中，若其所要访问的页面不在内存，而需要把他们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或者数据送到磁盘对换区中。但应将那个页面调出，必须根据一定的算法来确定。我们通常把这类算法称为页面置换算法（Page-Repleacement Algorithms）。置换算法的好坏直接影响系统的性能。

1.最佳置换算法(OPT)

最佳置换算法由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长时间内不再被访问的页面。但由于无法预知一个进程在内存中的若干个页面中，哪个是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其他算法。

optiaml.c

/*
 * 页面置换算法之最佳置换算法
 * Michael Jiang
 * Fri 04 Oct 2019 10:54:02 PM CST
 */
 
void optimal()
{
	// 无法实现
}
 

2.先进先出置换算法(FIFO)

FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的的页面予以淘汰。该算法实现简单(但是需要一个队列)

queue.h

#ifndef _QUEUE_H
#define _QUEUE_H
 
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>

typedef struct Node{
	int data;
	struct Node *next;
}Node;

typedef struct LinkQueue{
	Node *front;
	Node *rear;
	uint8_t size;
}LinkQueue;

void queue_init(LinkQueue **queue);
bool queue_push(LinkQueue **queue,int data);
bool queue_pop(LinkQueue **queue);
int queue_front(LinkQueue **queue);
uint8_t queue_size(LinkQueue **queue);
#endif

queue.c

#include "queue.h"

void queue_init(LinkQueue **queue)
{
	(*queue)->front = (*queue)->rear = NULL;
	(*queue)->size = 0;
}

bool queue_push(LinkQueue **queue,int data)
{
	Node *node = (Node *)malloc(sizeof(Node));
	node->data = data;
	node->next = NULL;
	
	if((*queue)->front == NULL){
		(*queue)->front = node;
		(*queue)->rear = node;
	}else{
		(*queue)->rear->next = node;
		(*queue)->rear = node;
	}
	(*queue)->size++;
	return true;
}

uint8_t queue_size(LinkQueue **queue)
{
	return (*queue)->size;
}

bool queue_pop(LinkQueue **queue)
{
	if((*queue)->front == NULL){
		return false;
	}
	Node *p = (*queue)->front;
	(*queue)->front = (*queue)->front->next;
	
	free(p);
	return true;
}

int queue_front(LinkQueue **queue)
{
	return (*queue)->front->data;
}

FIFO.c

/*
 * 页面置换算法之先进先出页面置换算法
 * Michael Jiang
 * Fri 04 Oct 2019 10:54:02 PM CST
 */

#include <stdio.h>
#include "queue.h"
bool current_in_block(int *block, int current)
{
	for(size_t i = 0; i < 3; i++){
		if(current == block[i]){
			return true;
		}
	}
	return false;
}

/* FIFO 页面置换算法
 * @param page_index:进程使用的页面序列
 * @param block:进程分配到的物理块
 */
void FIFO(int *page_index, int *block)
{
	// 撸个队列出来
	LinkQueue *queue = (LinkQueue *)malloc(sizeof(LinkQueue));
	queue_init(&queue);
	
	// 页面替换次数
	uint8_t r_times = 0;
	
	// 先将三个物理块填满
	for(size_t i = 0; i < 3; i++){
		block[i] = page_index[i];
		queue_push(&queue, page_index[i]);
		for(size_t t = 0; t < 3; t++){
			printf("%d ",block[t]);
		}
		printf("\n");
		
	}
	
	// 执行置换
	
	for(size_t i = 3; i < 20; i++){
		for(size_t t = 0; t < 3; t++){
			if(block[t] == queue_front(&queue) && !current_in_block(block,page_index[i])){
				block[t] = page_index[i];
				queue_pop(&queue);
				queue_push(&queue, page_index[i]);
				r_times++;
				break;
			}
		}

		
		for(size_t t = 0; t < 3; t++){
			printf("%d ",block[t]);
		}
		printf("\n");
	}
	
	printf("r_times=%d\n",r_times);
}



int main(int argc, char **argv)
{

	// 假设系统为某进程分配三个物理块，并考虑有以下打页面引用顺序
	int page_index[20] = {
		7,0,1,2,0,3,0,4,2,3,\
		0,3,2,1,2,0,1,7,0,1 \
	};
	
	// 系统为该进程分配了三个物理块
	int block[3] ={-1,-1,-1};
	
	// 使用FIFO算法进行页面置换
	FIFO(page_index,block);
	
	
	return 0;
}

执行结果：

root@SENCOM:~/Code/OS/Page_Replacement_Algorithms# gcc queue.c FIFO.c && ./a.out
7 -1 -1 
7 0 -1 
7 0 1 
2 0 1 
2 0 1 
2 3 1 
2 3 0 
4 3 0 
4 2 0 
4 2 3 
0 2 3 
0 2 3 
0 2 3 
0 1 3 
0 1 2 
0 1 2 
0 1 2 
7 1 2 
7 0 2 
7 0 1 
r_times=12

本测试用例在OPT算法下需要进行6次页面置换，而在FIFO算法下需要12次。

当我们增加Block大小后，FIFO算法下本用例的页面置换次数并不一定会降低，我们称这种现象叫做Belady异常。

3.最近最少使用置换算法(LRU)

FIFO算法的性能之所以差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）的页面置换算法是根据页面调入内存后的使用情况做出决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法选择的是最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰即可。

LRU.c

/*
 * 页面置换算法之最近最久未使用页面置换算法
 * Michael Jiang
 * Sun 06 Oct 2019 08:58:30 AM CST
 */

#include <stdint.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct Page{
	int id;
	int time;
}Page;

bool current_in_block(int *block, int current)
{
	for(size_t i = 0; i < 3; i++){
		if(current == block[i]){
			return true;
		}
	}
	return false;
}

void print_blok(int *block)
{
	printf("当前Block：");
	for(size_t i = 0; i < 3; i++){
		printf("%d ",block[i]);
	}
	printf("\n");
}

// 自增方法，使在block中的page time全部自增1
void auto_increment(Page *page,int *block)
{
	for(size_t i = 0; i < 3; i++){
		if(block[i] != -1){
			page[block[i]].time++;
		}
	}
}

/* LRU 页面置换算法
 * @param page_index:进程使用的页面序列
 * @param block:进程分配到的物理块
 */
void LRU(int now_page, int *block,Page *page)
{
	printf("time:%d %d %d\n",page[block[0]].time,page[block[1]].time,page[block[2]].time);
	// 找出time值最大的页
	int max_time = page[block[0]].time;
	int max_page = block[0];
	int max_index = 0;
	for(size_t i = 1; i < 3; i++){
		if(page[block[i]].time > max_time){
			max_time = page[block[i]].time;
			max_page = block[i];
			max_index = i;
		}
	}
	printf("新页%d换出旧页%d\n",now_page,max_page);
	// 换出 time 最大的页
	block[max_index] = now_page;
	
	// 重置time
	page[max_page].time = 0;
}


int main(int argc, char ** argv)
{
	Page page[20];
	
	// 初始化page
	for(size_t i = 0; i < 20; i++){
		page[i].id = i;
		page[i].time = 0;
	}
	
	// 假设系统为某进程分配三个物理块，并考虑有以下打页面引用顺序
	int page_index[20] = {
		7,0,1,2,0,3,0,4,2,3,\
		0,3,2,1,2,0,1,7,0,1 \
	};
	
	// 系统为该进程分配了三个物理块
	int block[3] ={-1,-1,-1};
	
	// 先将前三个页调入Block
	for(size_t i = 0; i < 3; i++){
		block[i] = page_index[i];
		auto_increment(page,block);
		print_blok(block);
	}
	
	
	// 执行后续页
	for(size_t i = 3; i < 20; i++){
		// 打印当前block中的页编号
		print_blok(block);
		if(current_in_block(block,page_index[i])){
			// 如果接下来的页在Block中的话我们就修改一下time
			page[page_index[i]].time = 0;
			printf("页%d存在于Block中，无需执行页面替换\n",page_index[i]);
		}else{
			// 如果不再当前进程的Block中就需要调用LRU进行页面替换
			LRU(page_index[i],block,page);
		}
		auto_increment(page,block);
		printf("\n");
	}
	return 0;
}

编译和执行结果：

root@SENCOM:~/Code/OS/Page_Replacement_Algorithms# gcc LRU.c && ./a.out 
当前Block：7 -1 -1 
当前Block：7 0 -1 
当前Block：7 0 1 
当前Block：7 0 1 
time:3 2 1
新页2换出旧页7

当前Block：2 0 1 
页0存在于Block中，无需执行页面替换

当前Block：2 0 1 
time:2 1 3
新页3换出旧页1

当前Block：2 0 3 
页0存在于Block中，无需执行页面替换

当前Block：2 0 3 
time:4 1 2
新页4换出旧页2

当前Block：4 0 3 
time:1 2 3
新页2换出旧页3

当前Block：4 0 2 
time:2 3 1
新页3换出旧页0

当前Block：4 3 2 
time:3 1 2
新页0换出旧页4

当前Block：0 3 2 
页3存在于Block中，无需执行页面替换

当前Block：0 3 2 
页2存在于Block中，无需执行页面替换

当前Block：0 3 2 
time:3 2 1
新页1换出旧页0

当前Block：1 3 2 
页2存在于Block中，无需执行页面替换

当前Block：1 3 2 
time:2 4 1
新页0换出旧页3

当前Block：1 0 2 
页1存在于Block中，无需执行页面替换

当前Block：1 0 2 
time:1 2 3
新页7换出旧页2

当前Block：1 0 7 
页0存在于Block中，无需执行页面替换

当前Block：1 0 7 
页1存在于Block中，无需执行页面替换

4.时钟置换算法(CLOCK)

虽然LRU是一种较好的算法，但由于它要求较多的硬件支持，使得其实现所需的成本过高，故在实际应用中，大多采用LRU的类似算法。Clock算法就是用的较多的一种LRU近似算法。

首先介绍一下简单Clock算法，只需要为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查访问位。如果是0，就选择该页换出，若为1，则重新将它置0，暂不换出，给予第二次驻留机会。再按照FIFO算法检查下一个页面。当检查到队列的最后一个页面时若其访问位仍为1，则返回队首去检查的一个页面。所以最坏的情况下要进行两轮扫描才能找到合适的淘汰页面。

clock.c

/*
 * 页面置换算法之简单Clock页面置换算法
 * Michael Jiang
 * Sat 05 Oct 2019 10:32:10 AM CST
 */
#include <stdio.h>
#include <stdbool.h>

// 页的数据结构
typedef struct Page{
	int id;		// 页面编号
	bool access;// 该页是否被访问
	struct Page *next;
}Page;

bool current_in_block(int *block, int current)
{
	for(size_t i = 0; i < 3; i++){
		if(current == block[i]){
			return true;
		}
	}
	return false;
}

void print_blok(int *block)
{
	printf("当前Block：");
	for(size_t i = 0; i < 3; i++){
		printf("%d ",block[i]);
	}
	printf("\n");
}

/*
 * 简单的 Clock 置换算法
 * @param page_index:进程使用的页面序列
 * @param block:进程分配到的物理块
 * @param page:Page数据结构
 */
void clock(int new_page, int *block, Page **current, Page *page)
{
	// 找出合适的换出页
	while((*current)->access != 0){
		(*current)->access = 0;
		(*current) = (*current)->next;
	}
	printf("读入新页编号%d;换出的页编号:%d\n",new_page,(*current)->id);
	// 将current指向的页面换出
	for(size_t i = 0; i < 3; i++){
		if(block[i] == (*current)->id){
			block[i] = new_page; //换上新页
			
			// 修改循环队列
			page[new_page].access = 1;
			page[new_page].id = new_page;
			
			// 找到current的前节点
			Page *p = (*current);
			int step = 2;
			while(step--){
				p = p->next;
			}
			page[new_page].next = (*current)->next;
			(*current) = &page[new_page];
			p->next = (*current);
			break;
		}
	}
	
}

int main(int argc, char **argv)
{
	// 假设系统为某进程分配三个物理块，并考虑有以下的页面引用顺序
	int page_index[20] = {
		7,0,1,2,0,3,0,4,2,3,\
		0,3,2,1,2,0,1,7,0,1 \
	};
	
	Page page[20];
	Page *current;
	Page *p;
	// 系统为该进程分配了三个物理块
	int block[3] ={-1,-1,-1};
	
	// 首先将前三个页放到Block中
	for(size_t i = 0; i < 3; i++){
		block[i] = page_index[i];
		page[page_index[i]].access = true;
		page[page_index[i]].id = page_index[i];
		if(i == 0){
			current = &page[page_index[i]];
			p = &page[page_index[i]];
		}else{
			p->next=&page[page_index[i]];
			p = &page[page_index[i]];
		}
	}
	p->next = current;// 形成循环队列，current指向队头
	
	
	// 使用简单clock算法进行页面置换
	for(size_t i = 3; i < 20; i++){			
		// 打印当前block中的页编号
		print_blok(block);
		// 首先判断接下来的页面是否在Block中
		if(current_in_block(block,page_index[i])){
			// 如果接下来的页在Block中的话我们就修改一下访问位就OK
			page[page_index[i]].access = true;
			printf("页%d存在于Block中，无需执行页面替换\n",page_index[i]);
		}else{
			// 如果不再当前进程的Block中就需要调用clock进行页面替换
			clock(page_index[i],block,&current, page);
		}
		printf("\n");
	}
	
	return 0;
}

编译和执行结果：

root@SENCOM:~/Code/OS/Page_Replacement_Algorithms# gcc clock.c && ./a.out 
当前Block：7 0 1 
读入新页编号2;换出的页编号:7

当前Block：2 0 1 
页0存在于Block中，无需执行页面替换

当前Block：2 0 1 
读入新页编号3;换出的页编号:1

当前Block：2 0 3 
页0存在于Block中，无需执行页面替换

当前Block：2 0 3 
读入新页编号4;换出的页编号:2

当前Block：4 0 3 
读入新页编号2;换出的页编号:3

当前Block：4 0 2 
读入新页编号3;换出的页编号:4

当前Block：3 0 2 
页0存在于Block中，无需执行页面替换

当前Block：3 0 2 
页3存在于Block中，无需执行页面替换

当前Block：3 0 2 
页2存在于Block中，无需执行页面替换

当前Block：3 0 2 
读入新页编号1;换出的页编号:3

当前Block：1 0 2 
页2存在于Block中，无需执行页面替换

当前Block：1 0 2 
页0存在于Block中，无需执行页面替换

当前Block：1 0 2 
页1存在于Block中，无需执行页面替换

当前Block：1 0 2 
读入新页编号7;换出的页编号:1

当前Block：7 0 2 
页0存在于Block中，无需执行页面替换

当前Block：7 0 2 
读入新页编号1;换出的页编号:2

最后提一下改进型Clock置换算法，将一个页面换出时，如果该页面已被修改过，便必须将该页重新写回到磁盘上;但如果该页未被修改过，则不必将它拷回磁盘。换言之，对于修改过的页面，在换出时所付出的开销比未修改的页面大。在改进型的Clock算法中，除须考虑页面的使用情况外，还需增加一个因素——置换代价。由访问位A和修改位M可以组合成下面四种类型的页面：

1类(A=0,M=0)：表示该页面最近既未被访问，又未被修改，是最佳淘汰页。

2类(A=0,M=1)：表示该页面最近未被访问，但已被修改，并不是很好的淘汰页。

3类(A=1,M=0)：表示该页最近已被访问，但未被修改，该页可能再次被访问。

4类(A=1,B=1)：表示最近已被访问且被修该，该页可能再被访问。

在内存中的每一页，都必定是这四类页之一。在进行页面置换时，可采用与简单Clock算法类似的算法，其差别在于该算法必须同时检查访问位和修改位，以确定该页属于四类叶中的哪一种。其执行步骤可分成一下三步：

（一）从指针所指示的当前位置开始，扫描循环队列，寻找A=0,M=0的第一类页面，将所有遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

（二）如果第一步失败，即查找一轮后未遇到第一类页面，则开始第二轮扫描，寻找A=0，M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有的扫描过的页面的访问位都置0。

（三）如果第二步失败，亦即未找到第二类页面，则旧将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，即寻找A=0，M=0的第一类页面，如果仍失败，必要时重复第二步。寻找A=0,M=1的第二类页面，此时就一定能够找到被淘汰的页。

该算法与简单Clock算法比较，可减少磁盘的I/O操作次数，但为了找到一个可置换的页，可能须经过几轮扫描。换言之，实现该算法本身的开销将有所增加。

改进型Clcok算法只需在原Clock算法的基础上进行简单修改即可，这里就不给出该算法的实现了。