文章目录
模拟实现请求分页虚存页面替换算法
1. 需求分析
请求分页虚存管理在地址映射过程中，若页表中发现所要访问的页不在主存，则产生缺页异常，操作系统接到此信号后，就调出缺页异常处理程序，根据页表中给出的磁盘地址，将该页面调入主存，是作业继续运行下去。如果主存中有空闲块，则分配一个页框，将新调入页面装入，并修改页表中相应页表项的驻留位及相应的主存块号；若此时主存中没有空闲块，则要淘汰某页面，若该页在此期间被修改过，要将其先写回磁盘，这个过程就是页面替换。
页面替换算法是虚拟存储管理实现的关键，好的算法能够减少和避免“颠簸”现象，本程序在模拟实现FIFO，LRU和OPT几种经典页面替换算法的基础上，比较各种替换算法的效率及优缺点，从而了解虚拟存储实现的过程，理解内存页面调度的机制。
2. 数据结构设计
- 在请求分页虚存页面替换算法中，为实现从请求页到主存块的替换，需要在模拟程序中维护两个数据结构，即请求页面队列和主存块队列。
- 请求页面队列为进程所用，记录当前进程请求的页面块信息。
- 主存队列由系统维护，该队列保存当前系统中各主存块的状态（包括最后访问时间、闲忙状态等）。
- 以这两个数据结构为基础，实现各种替换算法，在系统中为用户请求寻找物理块。
- 本程序设计含有以下功能：
- 接收用户输入参数，包括程序长度（页面数）、页框个数及页面访问序列。
- 程序结果采用不同的标志区分命中、替换及直接加入空闲块。
- 实现OPT、FIFO、LRU等替换算法，并显示算法对应替换页面的过程
- 计算各种页面替换算法的缺页中断率。
3. 程序设计
3.1 页面替换算法基本思路
本程序并没有进入系统空间对实际进程页面进行控制，而是在用户空间用线性表的连续存储方式对进程页面替换进行模拟。
-
最佳页面替换算法（OPT）
淘汰以后不再需要的或者最远的将来才会用到的页面。
-
先进先出页面替换算法（FIFO）
淘汰最先调入主存的页面，或者说在主存中驻留时间最长的那一页。
-
最近最少使用页面替换算法（LRU）
淘汰在最近一段时间里较久未被访问的页面。它是根据程序执行时所具有的局部性来考虑的，即那些刚被使用过的页面可能马上还要被使用，而那些在较长时间里未被使用的页面一般可能不会马上使用。
3.2 请求页面队列
typedef struct _Page { // 页面
int pageID; //页号
} Page;
typedef struct _PageQueue { //页面队列
Page page;
struct _PageQueue *next; //下一页面
} PageQueue;
typedef struct process { // 进程结构
PageQueue pages; //页面
unsigned int pageLength; // 页面数
} process;//进程
3.3 主存块队列
typedef struct _Block { //块记录结构
Page *page; //页面
long time; //最后访问时间
int state; //页块是否空闲
} Block;
typedef struct _BlockQueue { //块队列
Block block;
struct _BlockQueue *next;
} BlockQueue;
3.4 进程
初始化进程以及进程需要访问的页面的序列，这里仅仅展示了进程接收输入序列作为页面访问序列的代码，本程序还提供了由系统自动生成的页面访问序列，可以指定访问页面的最大序号。
PageQueue *InitializePageQueueWithInput(unsigned int pageLength) {
//初始化页面，把首地址返回。如果分配失败，返回NULL
PageQueue *head = NULL, *p = NULL, *q = NULL;
for (int i = 0; i < pageLength; i++) {
p = (PageQueue *) malloc(sizeof(PageQueue));
p->page.pageID = pages[i];
p->next = NULL;
printf("%d ", p->page.pageID);
if (head == NULL) head = p;
else q->next = p;
q = p;
}
printf("\n");
return head;
}
void InitializeProcessWithInput(process *proc, unsigned int pageSize) {
//初始化进程，接收手动输入的页面访问序列
printf("进程初始化：\n");
proc->pageLength = pageSize;
proc->pages.next = InitializePageQueueWithInput(pageSize);
}
随机生成页面访问序列
PageQueue *InitializePageQueue(unsigned int pageLength, int maxPageID) {
//初始化页面，把首地址返回。如果分配失败，返回NULL
srand(100);
PageQueue *head = NULL, *p = NULL, *q = NULL;
for (int i = 0; i < pageLength; i++) {
p = (PageQueue *) malloc(sizeof(PageQueue));
p->page.pageID = rand() % (maxPageID + 1);
p->next = NULL;
printf("%d ", p->page.pageID);
if (head == NULL) head = p;
else q->next = p;
q = p;
}
printf("\n");
return head;
}
3.5 主存
接收用户输入参数，作为初始化主存的块数，也即页框数，使用一个单向链表模拟实现主存。
BlockQueue *InitializeBlockQueue(unsigned int size) {
//初始化主存块，把首地址返回，如果分配失败返回NULL
BlockQueue *block = NULL, *p = NULL, *q = NULL;
for (int i = 0; i < size; i++) {
p = (BlockQueue *) malloc(sizeof(BlockQueue));
p->block.time = 0;
p->block.state = 0;
p->block.page = NULL;
p->next = NULL;
if (block == NULL) block = p;
else q->next = p;
q = p;
}
return block;
}
3.6 主存队列的维护
这里只展示主存队列一些重要操作的代码。
BlockQueue *SearchPage(BlockQueue *blockQueue, Page page) {
//搜索特定页面,根据页面ID进行匹配
BlockQueue *p = blockQueue;
while (p != NULL) {
if (p->block.page != NULL) {
if (p->block.page->pageID == page.pageID)
return p;
}
p = p->next;
}
return NULL;
}
BlockQueue *SearchIdleBlock(BlockQueue *blockQueue) {
//搜索空闲块
BlockQueue *p = blockQueue;
while (p != NULL) {
if (p->block.state == IDLE) return p;
else p = p->next;
}
return NULL;
}
BlockQueue *GetOldestBlock(BlockQueue *blockQueue) {
//取得主存中停留最久的页面，返回它的地址
BlockQueue *p = blockQueue, *oldestAddr;
if (p == NULL) return p;
long oldest = p->block.time;
oldestAddr = p;
while (p != NULL) {
if (p->block.time < oldest) {
oldest = p->block.time;
oldestAddr = p;
}
p = p->next;
}
return oldestAddr;
}
BlockQueue *GetLongestWithoutAccess(BlockQueue *blockQueue, PageQueue *currentPage){
//获取主存中最长时间将不会被访问的页面，返回其地址
BlockQueue *p = blockQueue, *longestAddr;
PageQueue *q = currentPage->next;
if (p == NULL) return p;
longestAddr = p;
int max_count = 0;
while (p != NULL){
int count = 0;
while(q != NULL){
count++;
if(p->block.page->pageID == q->page.pageID) break;
q = q->next;
}
if(count > max_count){
max_count = count;
longestAddr = p;
}
q = currentPage->next;
p = p->next;
}
return longestAddr;
}
3.7 OPT
void OPT(BlockQueue *blockQueue,process *proc){
//最佳页面替换算法
PageQueue *currentPage = proc->pages.next;
while (currentPage != NULL) {
if (SearchPage(blockQueue, currentPage->page) != NULL) {
PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
} else {
BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
if (idleBlock != NULL) {
idleBlock->block.state = BUSY;
idleBlock->block.time = Time++;
idleBlock->block.page = (Page *) malloc(sizeof(Page));
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_IDLE);
} else {
idleBlock = GetLongestWithoutAccess(blockQueue,currentPage);
idleBlock->block.time = Time++;
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_NoIDLE);
}
}
currentPage = currentPage->next;
}
}
3.8 FIFO
void FIFO(BlockQueue *blockQueue, process *proc) {
//先进先出算法
PageQueue *currentPage = proc->pages.next;
while (currentPage != NULL) {
if (SearchPage(blockQueue, currentPage->page) != NULL) {
PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
} else {
BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
if (idleBlock != NULL) {
idleBlock->block.state = BUSY;
idleBlock->block.time = Time++;
idleBlock->block.page = (Page *) malloc(sizeof(Page));
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_IDLE);
} else {
idleBlock = GetOldestBlock(blockQueue);
idleBlock->block.time = Time++;
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_NoIDLE);
}
}
currentPage = currentPage->next;
}
}
3.9 LRU
void LRU(BlockQueue *blockQueue, process *proc) {
//最近最少使用
PageQueue *currentPage = proc->pages.next;
while (currentPage != NULL) {
BlockQueue *searchedBlock = SearchPage(blockQueue, currentPage->page);
if (searchedBlock != NULL) {
searchedBlock->block.time = Time++;
PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
} else {
BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
if (idleBlock != NULL) {
idleBlock->block.state = BUSY;
idleBlock->block.time = Time++;
idleBlock->block.page = (Page *) malloc(sizeof(Page));
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_IDLE);
} else {
idleBlock = GetOldestBlock(blockQueue);
idleBlock->block.time = Time++;
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_NoIDLE);
}
}
currentPage = currentPage->next;
}
}
4. 页面替换算法测试
测试页面访问序列（页框数为3）
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
4.1 OPT
运行结果
---------------------------------------------------------
页框1 | 7 | 缺页! 主存不存在该页面，载入空闲页框1
页框2 | |
页框3 | |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 | 缺页! 主存不存在该页面，载入空闲页框2
页框3 | |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 |
页框3 | 1 | 缺页! 主存不存在该页面，载入空闲页框3
---------------------------------------------------------
页框1 | 2 | 缺页! 主存不存在该页面，替换页框1
页框2 | 0 |
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 | 命中! 主存已存在该页面，位于页框2
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 |
页框3 | 3 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 | 命中! 主存已存在该页面，位于页框2
页框3 | 3 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 4 | 缺页! 主存不存在该页面，替换页框2
页框3 | 3 |
---------------------------------------------------------
页框1 | 2 | 命中! 主存已存在该页面，位于页框1
页框2 | 4 |
页框3 | 3 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 4 |
页框3 | 3 | 命中! 主存已存在该页面，位于页框3
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 | 缺页! 主存不存在该页面，替换页框2
页框3 | 3 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 |
页框3 | 3 | 命中! 主存已存在该页面，位于页框3
---------------------------------------------------------
页框1 | 2 | 命中! 主存已存在该页面，位于页框1
页框2 | 0 |
页框3 | 3 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 |
页框3 | 1 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
页框1 | 2 | 命中! 主存已存在该页面，位于页框1
页框2 | 0 |
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 | 命中! 主存已存在该页面，位于页框2
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 |
页框3 | 1 | 命中! 主存已存在该页面，位于页框3
---------------------------------------------------------
页框1 | 7 | 缺页! 主存不存在该页面，替换页框1
页框2 | 0 |
页框3 | 1 |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 | 命中! 主存已存在该页面，位于页框2
页框3 | 1 |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 |
页框3 | 1 | 命中! 主存已存在该页面，位于页框3
---------------------------------------------------------
缺页中断率为：45.00%
运行结果部分截图
对比准确数据
4.2 FIFO
---------------------------------------------------------
页框1 | 7 | 缺页! 主存不存在该页面，载入空闲页框1
页框2 | |
页框3 | |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 | 缺页! 主存不存在该页面，载入空闲页框2
页框3 | |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 |
页框3 | 1 | 缺页! 主存不存在该页面，载入空闲页框3
---------------------------------------------------------
页框1 | 2 | 缺页! 主存不存在该页面，替换页框1
页框2 | 0 |
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 | 命中! 主存已存在该页面，位于页框2
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 3 | 缺页! 主存不存在该页面，替换页框2
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 3 |
页框3 | 0 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
页框1 | 4 | 缺页! 主存不存在该页面，替换页框1
页框2 | 3 |
页框3 | 0 |
---------------------------------------------------------
页框1 | 4 |
页框2 | 2 | 缺页! 主存不存在该页面，替换页框2
页框3 | 0 |
---------------------------------------------------------
页框1 | 4 |
页框2 | 2 |
页框3 | 3 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
页框1 | 0 | 缺页! 主存不存在该页面，替换页框1
页框2 | 2 |
页框3 | 3 |
---------------------------------------------------------
页框1 | 0 |
页框2 | 2 |
页框3 | 3 | 命中! 主存已存在该页面，位于页框3
---------------------------------------------------------
页框1 | 0 |
页框2 | 2 | 命中! 主存已存在该页面，位于页框2
页框3 | 3 |
---------------------------------------------------------
页框1 | 0 |
页框2 | 1 | 缺页! 主存不存在该页面，替换页框2
页框3 | 3 |
---------------------------------------------------------
页框1 | 0 |
页框2 | 1 |
页框3 | 2 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
页框1 | 0 | 命中! 主存已存在该页面，位于页框1
页框2 | 1 |
页框3 | 2 |
---------------------------------------------------------
页框1 | 0 |
页框2 | 1 | 命中! 主存已存在该页面，位于页框2
页框3 | 2 |
---------------------------------------------------------
页框1 | 7 | 缺页! 主存不存在该页面，替换页框1
页框2 | 1 |
页框3 | 2 |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 | 缺页! 主存不存在该页面，替换页框2
页框3 | 2 |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 |
页框3 | 1 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
缺页中断率为：75.00%
运行结果部分截图
对比准确数据
4.3 LRU
---------------------------------------------------------
页框1 | 7 | 缺页! 主存不存在该页面，载入空闲页框1
页框2 | |
页框3 | |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 | 缺页! 主存不存在该页面，载入空闲页框2
页框3 | |
---------------------------------------------------------
页框1 | 7 |
页框2 | 0 |
页框3 | 1 | 缺页! 主存不存在该页面，载入空闲页框3
---------------------------------------------------------
页框1 | 2 | 缺页! 主存不存在该页面，替换页框1
页框2 | 0 |
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 | 命中! 主存已存在该页面，位于页框2
页框3 | 1 |
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 |
页框3 | 3 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
页框1 | 2 |
页框2 | 0 | 命中! 主存已存在该页面，位于页框2
页框3 | 3 |
---------------------------------------------------------
页框1 | 4 | 缺页! 主存不存在该页面，替换页框1
页框2 | 0 |
页框3 | 3 |
---------------------------------------------------------
页框1 | 4 |
页框2 | 0 |
页框3 | 2 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
页框1 | 4 |
页框2 | 3 | 缺页! 主存不存在该页面，替换页框2
页框3 | 2 |
---------------------------------------------------------
页框1 | 0 | 缺页! 主存不存在该页面，替换页框1
页框2 | 3 |
页框3 | 2 |
---------------------------------------------------------
页框1 | 0 |
页框2 | 3 | 命中! 主存已存在该页面，位于页框2
页框3 | 2 |
---------------------------------------------------------
页框1 | 0 |
页框2 | 3 |
页框3 | 2 | 命中! 主存已存在该页面，位于页框3
---------------------------------------------------------
页框1 | 1 | 缺页! 主存不存在该页面，替换页框1
页框2 | 3 |
页框3 | 2 |
---------------------------------------------------------
页框1 | 1 |
页框2 | 3 |
页框3 | 2 | 命中! 主存已存在该页面，位于页框3
---------------------------------------------------------
页框1 | 1 |
页框2 | 0 | 缺页! 主存不存在该页面，替换页框2
页框3 | 2 |
---------------------------------------------------------
页框1 | 1 | 命中! 主存已存在该页面，位于页框1
页框2 | 0 |
页框3 | 2 |
---------------------------------------------------------
页框1 | 1 |
页框2 | 0 |
页框3 | 7 | 缺页! 主存不存在该页面，替换页框3
---------------------------------------------------------
页框1 | 1 |
页框2 | 0 | 命中! 主存已存在该页面，位于页框2
页框3 | 7 |
---------------------------------------------------------
页框1 | 1 | 命中! 主存已存在该页面，位于页框1
页框2 | 0 |
页框3 | 7 |
---------------------------------------------------------
缺页中断率为：60.00%
运行结果部分截图
对比准确数据
5. 总结
分页虚拟存储管理既有优点又有缺点，优点是作业的程序和数据可按页分散存放在主存中，有效解决了碎片问题； 既有利于改进主存利用率，又有利于多道程序运行。缺点是要有硬件支持，要进行缺页中断处理，机器成本增加，系统开销加大。缺页中断率小是虚拟存储管理目标之一，而影响缺页中断率的因素主要有：主存页框数、页面大小、页面分配机制，替换算法、程序的局部性。好的页面替换算法能够降低缺页中断率。
6. 完整源码
//
// Created by wylu on 2018/1/6.
//
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<sys/time.h>
#include<unistd.h>
#include<stdlib.h>
#define BUSY 1
#define IDLE 0
#define COLOR_Exist 0
#define COLOR_NotExist_IDLE 1
#define COLOR_NotExist_NoIDLE 2
double hitCount = 0;
int pages[100];
typedef struct _Page { // 页面
int pageID; //页号
} Page;
typedef struct _PageQueue { //页面队列
Page page;
struct _PageQueue *next; //下一页面
} PageQueue;
typedef struct _Block { //块记录结构
Page *page; //页面
long time; //最后访问时间
int state; //页块是否空闲
} Block;
typedef struct _BlockQueue { //块队列
Block block;
struct _BlockQueue *next;
} BlockQueue;
typedef struct process { // 进程结构
PageQueue pages; //页面
unsigned int pageLength; // 页面数
} process;//进程
int Time = 0;
long GetSystemUtime() {
//获取系统当前时间的微秒数
struct timeval nowit;
gettimeofday(&nowit, NULL);
return 1000000 * nowit.tv_sec + nowit.tv_usec;;
}
BlockQueue *InitializeBlockQueue(unsigned int size) {
//初始化主存块，把首地址返回，如果分配失败返回NULL
BlockQueue *block = NULL, *p = NULL, *q = NULL;
for (int i = 0; i < size; i++) {
p = (BlockQueue *) malloc(sizeof(BlockQueue));
p->block.time = 0;
p->block.state = 0;
p->block.page = NULL;
p->next = NULL;
if (block == NULL) block = p;
else q->next = p;
q = p;
}
return block;
}
int GetBlockQueueSize(BlockQueue *blockQueue) {
//获取块长度
BlockQueue *presentBlock = blockQueue;
int blockQueueSize = 0;
while (presentBlock != NULL) {
blockQueueSize++;
presentBlock = presentBlock->next;
}
return blockQueueSize;
}
void ResetBlockQueue(BlockQueue *blockQueue) {
//清空块内容
BlockQueue *presentBlock = blockQueue;
while (presentBlock != NULL) {
presentBlock->block.page = NULL;
presentBlock->block.state = IDLE;
presentBlock->block.time = 0;
presentBlock = presentBlock->next;
}
}
PageQueue *InitializePageQueue(unsigned int pageLength, int maxPageID) {
//初始化页面，把首地址返回。如果分配失败，返回NULL
srand(100);
PageQueue *head = NULL, *p = NULL, *q = NULL;
for (int i = 0; i < pageLength; i++) {
p = (PageQueue *) malloc(sizeof(PageQueue));
p->page.pageID = rand() % (maxPageID + 1);
p->next = NULL;
printf("%d ", p->page.pageID);
if (head == NULL) head = p;
else q->next = p;
q = p;
}
printf("\n");
return head;
}
PageQueue *InitializePageQueueWithInput(unsigned int pageLength) {
//初始化页面，把首地址返回。如果分配失败，返回NULL
PageQueue *head = NULL, *p = NULL, *q = NULL;
for (int i = 0; i < pageLength; i++) {
p = (PageQueue *) malloc(sizeof(PageQueue));
p->page.pageID = pages[i];
p->next = NULL;
printf("%d ", p->page.pageID);
if (head == NULL) head = p;
else q->next = p;
q = p;
}
printf("\n");
return head;
}
void InitializeProcess(process *proc, unsigned int pageSize, unsigned int maxPageID) {
//初始化进程，随机生成进程页面访问序列
printf("进程初始化：\n");
proc->pageLength = pageSize;
proc->pages.next = InitializePageQueue(pageSize, maxPageID);
}
void InitializeProcessWithInput(process *proc, unsigned int pageSize) {
//初始化进程，接收手动输入的页面访问序列
printf("进程初始化：\n");
proc->pageLength = pageSize;
proc->pages.next = InitializePageQueueWithInput(pageSize);
}
BlockQueue *SearchPage(BlockQueue *blockQueue, Page page) {
//搜索特定页面
BlockQueue *p = blockQueue;
while (p != NULL) {
if (p->block.page != NULL) {
if (p->block.page->pageID == page.pageID)
return p;
}
p = p->next;
}
return NULL;
}
BlockQueue *SearchIdleBlock(BlockQueue *blockQueue) {
//搜索空闲块
BlockQueue *p = blockQueue;
while (p != NULL) {
if (p->block.state == IDLE) return p;
else p = p->next;
}
return NULL;
}
int GetBlockLable(BlockQueue *blockQueue, BlockQueue *goalBlock) {
//返回块号，编号从1开始
BlockQueue *p = blockQueue;
int count = 1;
while (p != goalBlock) {
p = p->next;
count++;
}
return count;
}
BlockQueue *GetOldestBlock(BlockQueue *blockQueue) {
//取得主存中停留最久的页面，返回它的地址
BlockQueue *p = blockQueue, *oldestAddr;
if (p == NULL) return p;
long oldest = p->block.time;
oldestAddr = p;
while (p != NULL) {
if (p->block.time < oldest) {
oldest = p->block.time;
oldestAddr = p;
}
p = p->next;
}
return oldestAddr;
}
BlockQueue *GetLongestWithoutAccess(BlockQueue *blockQueue, PageQueue *currentPage){
//获取主存中最长时间将不会被访问的页面，返回其地址
BlockQueue *p = blockQueue, *longestAddr;
PageQueue *q = currentPage->next;
if (p == NULL) return p;
longestAddr = p;
int max_count = 0;
while (p != NULL){
int count = 0;
while(q != NULL){
count++;
if(p->block.page->pageID == q->page.pageID) break;
q = q->next;
}
if(count > max_count){
max_count = count;
longestAddr = p;
}
q = currentPage->next;
p = p->next;
}
return longestAddr;
}
void PrintBlockList(BlockQueue *blockQueue, int pageID, int color) {
//打印块信息
BlockQueue *presentBlock = blockQueue;
for (int i = 0; i < GetBlockQueueSize(blockQueue); i++) {
if (presentBlock == NULL) break;
printf("页框%d ", i + 1);
if (presentBlock->block.state == IDLE) {
printf("| |\n");
} else {
if (presentBlock->block.page->pageID != pageID) {
printf("| %d |\n", presentBlock->block.page->pageID);
} else {
switch (color) {
case COLOR_Exist:
printf("| %d | 命中! 主存已存在该页面，位于页框%d\n",
pageID, GetBlockLable(blockQueue, presentBlock));
hitCount++;
break;
case COLOR_NotExist_IDLE:
printf("| %d | 缺页! 主存不存在该页面，载入空闲页框%d\n",
pageID, GetBlockLable(blockQueue, presentBlock));
break;
case COLOR_NotExist_NoIDLE:
printf("| %d | 缺页! 主存不存在该页面，替换页框%d\n",
pageID, GetBlockLable(blockQueue, presentBlock));
break;
default:
break;
}
}
}
presentBlock = presentBlock->next;
}
printf("---------------------------------------------------------\n");
}
void FIFO(BlockQueue *blockQueue, process *proc) {
//先进先出算法
PageQueue *currentPage = proc->pages.next;
while (currentPage != NULL) {
if (SearchPage(blockQueue, currentPage->page) != NULL) {
PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
} else {
BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
if (idleBlock != NULL) {
idleBlock->block.state = BUSY;
idleBlock->block.time = Time++;
idleBlock->block.page = (Page *) malloc(sizeof(Page));
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_IDLE);
} else {
idleBlock = GetOldestBlock(blockQueue);
idleBlock->block.time = Time++;
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_NoIDLE);
}
}
currentPage = currentPage->next;
}
}
void LRU(BlockQueue *blockQueue, process *proc) {
//最近最少使用
PageQueue *currentPage = proc->pages.next;
while (currentPage != NULL) {
BlockQueue *searchedBlock = SearchPage(blockQueue, currentPage->page);
if (searchedBlock != NULL) {
searchedBlock->block.time = Time++;
PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
} else {
BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
if (idleBlock != NULL) {
idleBlock->block.state = BUSY;
idleBlock->block.time = Time++;
idleBlock->block.page = (Page *) malloc(sizeof(Page));
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_IDLE);
} else {
idleBlock = GetOldestBlock(blockQueue);
idleBlock->block.time = Time++;
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_NoIDLE);
}
}
currentPage = currentPage->next;
}
}
void OPT(BlockQueue *blockQueue, process *proc){
//最佳页面替换算法
PageQueue *currentPage = proc->pages.next;
while (currentPage != NULL) {
if (SearchPage(blockQueue, currentPage->page) != NULL) {
PrintBlockList(blockQueue, currentPage->page.pageID, COLOR_Exist);
} else {
BlockQueue *idleBlock = SearchIdleBlock(blockQueue);
if (idleBlock != NULL) {
idleBlock->block.state = BUSY;
idleBlock->block.time = Time++;
idleBlock->block.page = (Page *) malloc(sizeof(Page));
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_IDLE);
} else {
idleBlock = GetLongestWithoutAccess(blockQueue,currentPage);
idleBlock->block.time = Time++;
idleBlock->block.page->pageID = currentPage->page.pageID;
PrintBlockList(blockQueue,
currentPage->page.pageID, COLOR_NotExist_NoIDLE);
}
}
currentPage = currentPage->next;
}
}
void SelectAlgorithm(){
printf("\n========================================================\n");
printf("\t1.OPT\t2.FIFO\t3.LRU\t0.exit\n");
printf("========================================================\n");
}
int main() {
bool isGoOn = true;
while (isGoOn){
//主存块数，即页框数
unsigned int blockNumber;
//进程页面数
unsigned int pageNumber;
printf("请输入主存块数(即页框数)：");
scanf("%u", &blockNumber);
printf("请输入进程页面数：");
scanf("%u", &pageNumber);
printf("========================================================\n");
printf("\t主存页框数: %u, 进程页面数: %u\n", blockNumber, pageNumber);
printf("========================================================\n");
BlockQueue *blocks;
process proc;
printf("是否手动输入访问序列? y/n\n");
getchar();
if (getchar() == 'y'){
printf("请输入访问序列：");
for (int i = 0; i < pageNumber; ++i) {
scanf("%d",&pages[i]);
}
InitializeProcessWithInput(&proc,pageNumber);
} else{
InitializeProcess(&proc, pageNumber, 10);
}
blocks = InitializeBlockQueue(blockNumber);
SelectAlgorithm();
int oper;
while (scanf("%d",&oper)){
int flag = 0;
printf("\n---------------------------------------------------------\n");
hitCount = 0;
switch (oper){
case 1:
OPT(blocks, &proc);
break;
case 2:
FIFO(blocks, &proc);
break;
case 3:
LRU(blocks, &proc);
break;
case 0:
flag = 1;
break;
default:
SelectAlgorithm();
printf("非法输入!请重新输入：");
break;
}
if (flag == 1) break;
printf("缺页中断率为：%.2lf%%\n",(1-(hitCount/pageNumber))*100);
ResetBlockQueue(blocks);
SelectAlgorithm();
}
printf("是否重新输入访问序列? y/n\n");
getchar();
if(getchar() != 'y') isGoOn = false;
system("cls");
}
}