模拟实现请求分页虚存页面替换算法

发表于 更新于 分类于 ， 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

请求分页虚存管理在地址映射过程中，若页表中发现所要访问的页不在主存，则产生缺页异常，操作系统接到此信号后，就调出缺页异常处理程序，根据页表中给出的磁盘地址，将该页面调入主存，是作业继续运行下去。如果主存中有空闲块，则分配一个页框，将新调入页面装入，并修改页表中相应页表项的驻留位及相应的主存块号；若此时主存中没有空闲块，则要淘汰某页面，若该页在此期间被修改过，要将其先写回磁盘，这个过程就是页面替换。

页面替换算法是虚拟存储管理实现的关键，好的算法能够减少和避免“颠簸”现象，本文在模拟实现 FIFO，LRU 和 OPT 几种经典页面替换算法的基础上，比较各种替换算法的效率及优缺点，从而了解虚拟存储实现的过程，理解内存页面调度的机制。

模拟实现请求分页虚存页面替换算法

数据结构设计

  1. 在请求分页虚存页面替换算法中，为实现从请求页到主存块的替换，需要在模拟程序中维护两个数据结构，即请求页面队列和主存块队列。
  2. 请求页面队列为进程所用，记录当前进程请求的页面块信息。
  3. 主存队列由系统维护，该队列保存当前系统中各主存块的状态（包括最后访问时间、闲忙状态等）。
  4. 以这两个数据结构为基础，实现各种替换算法，在系统中为用户请求寻找物理块。
  5. 本项目设计含有以下功能：
    • 接收用户输入参数，包括程序长度（页面数）、页框个数及页面访问序列。
    • 程序结果采用不同的标志区分命中、替换及直接加入空闲块。
    • 实现 OPT、FIFO、LRU 等替换算法，并显示算法对应替换页面的过程。
    • 计算各种页面替换算法的缺页中断率。

程序设计

页面替换算法基本思路

本程序并没有进入系统空间对实际进程页面进行控制，而是在用户空间用线性表的连续存储方式对进程页面替换进行模拟。

  1. 最佳页面替换算法（OPT）

    淘汰以后不再需要的或者最远的将来才会用到的页面。

  2. 先进先出页面替换算法（FIFO）

    淘汰最先调入主存的页面，或者说在主存中驻留时间最长的那一页。

  3. 最近最少使用页面替换算法（LRU）

    淘汰在最近一段时间里较久未被访问的页面。它是根据程序执行时所具有的局部性来考虑的，即那些刚被使用过的页面可能马上还要被使用，而那些在较长时间里未被使用的页面一般可能不会马上使用。

请求页面队列

1
2
3
4
5
6
7
8
9
10
11
typedef struct _Page { // 页面
    int pageID;     //页号
} Page;
typedef struct _PageQueue { //页面队列
    Page page;
    struct _PageQueue *next; //下一页面
} PageQueue;
typedef struct process { // 进程结构
    PageQueue pages; //页面
    unsigned int pageLength; // 页面数
} process;//进程

主存块队列

1
2
3
4
5
6
7
8
9
typedef struct _Block { //块记录结构
    Page *page; //页面
    long time; //最后访问时间
    int state; //页块是否空闲
} Block;
typedef struct _BlockQueue { //块队列
    Block block;
    struct _BlockQueue *next;
} BlockQueue;

进程

初始化进程以及进程需要访问的页面的序列，这里仅仅展示了进程接收输入序列作为页面访问序列的代码，本程序还提供了由系统自动生成的页面访问序列，可以指定访问页面的最大序号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
}

随机生成页面访问序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

主存

接收用户输入参数，作为初始化主存的块数，也即页框数，使用一个单向链表模拟实现主存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

主存队列的维护

这里只展示主存队列一些重要操作的代码。

1
2
3
4
5
6
7
8
9
10
11
12
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;
}
1
2
3
4
5
6
7
8
9
BlockQueue *SearchIdleBlock(BlockQueue *blockQueue) {
    //搜索空闲块
    BlockQueue *p = blockQueue;
    while (p != NULL) {
        if (p->block.state == IDLE) return p;
        else p = p->next;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}

OPT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

FIFO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
}

页面替换算法测试

测试页面访问序列（页框数为3）

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

main

OPT

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
---------------------------------------------------------
页框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%

运行结果部分截图

OPT-run-res

对比准确数据

OPT-accurate-res

FIFO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
---------------------------------------------------------
页框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%

运行结果部分截图

FIFO-run-res

对比准确数据

FIFO-accurate-res

LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
---------------------------------------------------------
页框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%

运行结果部分截图

LRU-run-res

对比准确数据

LRU-accurate-res

总结

分页虚拟存储管理既有优点又有缺点，优点是作业的程序和数据可按页分散存放在主存中，有效解决了碎片问题； 既有利于改进主存利用率，又有利于多道程序运行。缺点是要有硬件支持，要进行缺页中断处理，机器成本增加，系统开销加大。缺页中断率小是虚拟存储管理目标之一，而影响缺页中断率的因素主要有：主存页框数、页面大小、页面分配机制，替换算法、程序的局部性。好的页面替换算法能够降低缺页中断率。

完整源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
//
// 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");
    }
}