操作系统第5次实验-14281147-王飞

1、操作系统实验五 页面置换算法1. 实验目的设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法；通过页面访问序列随机发生器实现对上述算法的测试及性能比较。2. 实验基础知识及背景说明（1） 请求分页虚拟内存管理请求分页虚拟内存管理是建立在基本分页基础上的，为了能支持虚拟存储器功能，而增加了请求调页功能和置换功能。（2） 工作集多数程序都显示出高度的局部性，也就是说，在一个时间段内，一组页面被反复引用。这组被反复引用的页面随着时间的推移，其成员也会发生变化。有时这种变化是剧烈的，有时这种变化则是渐进的。我们把这组页面的集合称为工作集（3） 缺页率缺页中断次数/总的页

2、面访问次数3. 实验前提说明（1） 页表用整数数组或结构数组来表示（2） 页面访问序列串是一个整数序列，整数的取值范围为0到N - 1。页面访问序列串中的每个元素p表示对页面p的一次访问（3） 符合局部访问特性的随机生成算法a. 确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和1之间的值tb. 生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中c. 生成一个随机数r，0 r 1d. 如果r < t，则为p生成一个新值，否则p = (p + 1) mod Ne. 如果想继续加大页面

3、访问序列串的长度，请返回第2步，否则结束4. 实验算法介绍（1） 最佳置换算法最佳置换算法的主要思想是，在发生页面替换时，被替换的对象应该满足，在以后的页面访问中，该对象不会再次被访问或者较晚被访问。是一种理想化算法，具有最好性能（对于固定分配页面方式，本法可保证获得最低的缺页率），但实际上却难于实现，故主要用于算法评价参照（2） 先进先出置换算法先进先出置换算法的主要思想是，在发生页面替换时，被替换的对象应该是最早进入内存的。（3） 最近最久未使用置换算法最近最久未使用置换算法的主要思想是，在发生页面替换时，被替换的页面应该满足，在之前的访问队列中，该对象截止目前未被访问的时间最长（4） 改

4、进型Clock置换算法改进型Clock置换算法的主要思想是，在每次页面替换时，总是尽可能地先替换掉既未被访问又未被修改的页面。（5） 页面缓冲算法设立空闲页面链表和已修改页面链表采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾,空闲页面链表同时用于物理块分配,当已修改页面链表达到一定长度如Z个页面时，一起将所有已修改页面写回磁盘，故可显著减少磁盘I/O操作次数5. 相关数据结构设计根据各个算法的特点，程序实现的过程中用到的数据结构主要有以下两种（1） 数组：定义的时候利用指针定义，然后根据全局变量block设定的

5、给进程分配的物理内存的块数动态分配内存。一旦完成内存分配，不再改变数组的大小。用到数组结构来实现的算法程序有：最佳置换算法，先进先出置换算法，最近最久未使用置换算法，改进型置换算法。（2） 队列：为单向队列，队列长度仍然由全局变量指定。用到队列的算法程序有：先进先出置换算法。队列结点元素的结构体如下typedef struct node int num;/页号 node* next;/下一个结点页面 Node, *pNode;typedef struct queue int n;/总的结点数 pNode front;/队首指针 pNode rear; /队尾指针 Queue, *pQueue;

6、（3） 链表：主要是将装入内存的页块串联起来。用到链表的算法程序：页面缓冲算法。链表结点元素的结构体如下struct LNode int data;/页号 int flag;/访问位 int modify;/修改位 LNode* next;struct Link int num;/当前链表上的结点数 LNode* next;6. 主要函数功能说明（1） 全局共享函数void initMemo();/初始化存储空间，主要是设置分配空间的大小void generate();/生成访问序列bool isInMemo (int n); /指定页号是否已经在内存中（2） 最佳置换算法void optim

7、al (int n); /访问一个页面，执行一次最佳置换算法void testOptimal();/算法实现函数（3） 先进先出置换算法void initQueue (pQueue q);/初始化队列void push (pQueue q, int num);/队列中加入新的页面结点void pop (pQueue q);/将页面移出内存void destroy (pQueue q);/销毁队列bool findInQueue (pQueue q, int num);/查找页面是否已经调入内存void generate();/生成访问序列void fifoTest();/每访问一个页面，执行一

8、次算法void fifo (pQueue q, int num);/先进先出置换算法实现函数（4） 最近最久未使用置换算法void LRU (int n);/每访问一个新的页面，执行一次LRU算法void testLRU();/LRU算法实现函数（5） 改进型clock置换算法void updated_Clock (int n);/改进型clock算法实现函数void test_Clock();/每访问一个新的页面，执行一次算法（6） 页面缓冲算法bool isInNodes (int n); /页面是否已经在链表中void addToLink (int data, int type);/页面

9、添加到已修改页面链表和空闲链表上void emptyIdle();/将空闲链表上的所有页面送出内存void emptyModi();/将已修改页面链表上所有的链表送出内存void PBA (int n);/PBA算法实现函数7. 程序运行每个算法实现的代码量不同，以及不同算法使用的数据结构有差别，为了不至于程序过于臃肿庞大，所以所有的算法总共是在三个程序实现的（具体代码如8附录所示）.其中，最佳置换算法，LRU算法，改进型clock置换算法是在experiment5.cpp中实现的，先进先出置换算法是在FIFO.cpp中实现的，页面缓冲置换算法是在PBA.cpp中实现的。为了便于对比，程序中会

10、先用genenrate（）函数产生大小为32的访问序列，然后在每种算法下运行。测试过程如下：（1） 利用generate函数产生访问序列如下access32= 2, 3, 3, 7, 2, 8, 3, 7, 9, 7, 10, 8, 12, 11, 8, 8, 61, 61, 3, 61, 62, 60, 2,60, 3,62,62, 3, 3, 4, 2, 62 （2） 各算法执行结果如下a.最佳置换算法（局部）可以看到，32个页面，有12个页面发生了缺页，缺页率为0.375b.先进先出算法可以看到，32个页面，有15个页面发生了缺页，缺页率为0.46875c.最近最久未使用置换（LRU）算

11、法可以看到，32个页面，有18个页面发生了缺页，缺页率为0.5625d.改进型clock置换算法可以看到，32个页面，有14个页面发生了缺页，缺页率为0.4375e.页面缓冲置换算法 可以看到，32个页面，有15个页面发生了缺页，缺页率为0.46875（3） 利用genenrate()函数再生成几个访问序列，记录每个序列下，每种算法的缺页情况，最终整理得到如下统计表格：注：访问序列的长度始终为32，默认初始分配给每种算法的内存空间块数为3置换算法最佳置换算法先进先出置换算法最近最久未使用算法改进型clock置换算法页面缓冲置换算法测试序列1缺页数1215181415缺页率0.3750.4687

12、50.56250.43750.46875测试序列2缺页数1014151311缺页率0.31250.43750.468750.406250.34375测试序列3缺页数1316151614缺页率0.406250.50.468750.50.4375使用同样的访问序列，改变分配给每种算法的的内存空间块数为5，得到实验结果如下置换算法最佳置换算法先进先出置换算法最近最久未使用算法改进型clock置换算法页面缓冲置换算法测试序列1缺页数7119109缺页率0.218750.34750.281250.31250.28125测试序列2缺页数7991011缺页率0.218750.281250.281250.31

13、250.34375测试序列3缺页数912111111缺页率0.281250.3750.343750.343750.34375从上图表观察可以得到如下结论：（1） 同一种算法，对于不同的访问序列，其缺页率是不同，会有所变化。（2） 总的来看，最佳置换算法的缺页率是最低的，这一点是毋庸置疑的。剩下的集中算法中，页面缓冲算法的缺页率要低于其他置换算法。改进型clock算法稍微好于先进先出算法和最近最久未使用算法。先进先出算法和最近最久未使用算法性能相近。总的来看，性能（缺页率）如下。最佳置换算法>页面缓冲置换算法>改进型clock置换算法>最近最久未使用算法>=先进先出置换算

14、法。（3） 对比内存块数为3和内存块数为5两种情况下的同一序列下的同一，可以发现，算法的缺页率还跟分配的内存块数有关系，分配的内存块数越多，缺页率越低。这与直观感受是一致的，即导入内存的块数越多，发生缺页的可能性就越小。8. 附录（程序代码）PBA.cpp#include "stdafx.h"#include "stdio.h"#include"stdlib.h"#include"time.h"#define M 32 /物理内存块数#define N 64 /虚拟内存块数struct LNode int data

15、; int flag;/访问位 int modify;/修改位 LNode* next;struct Link int num;/当前链表上的结点数 LNode* next;void generate();/生成访问序列bool isInNodes (int n); /void addToLink (int data, int type);void emptyIdle();void emptyModi();void PBA (int n);int size = 3;int p;/工作集的起始位置int table32;/物理内存，每一个元素代表一个页面int access32; /访问序列in

16、t memo3 = -1, -1, -1 ;int lost = 0;/没找到的页面数int index = 0;/指示当前下标LNode* nodes;/改进型Clock置换算法用到的数据结构Link idle;Link modified;int _tmain (int argc, _TCHAR* argv) int i = 0, j = 0; generate(); printf ("页面缓冲置换算法(PBA)n"); idle.num = 0; idle.next = NULL; modified.num = 0; modified.next = NULL; node

17、s = (LNode*) malloc (size * sizeof (LNode); for (i = 0; i < size; i+) nodesi.data = -1; nodesi.flag = 0; nodesi.modify = 0; nodesi.next = NULL; for (i = 0; i < 32; i+) PBA (i); for (j = 0; j < size; j+) printf ("%d ", nodesj.data); printf ("n"); printf ("页面缓冲置换算法（PB

18、A）缺页率：%f %dn", lost / 32.0, lost); getchar(); getchar(); return 0;void generate() srand ( (unsigned) time (NULL); /用时间做种，每次产生随机数不一样 p = rand() % 64; int m = 8, e = 8; int i, j; double t; t = rand() % 10 / 10.0; for (i = 0; i < 4; i+) for (j = i * m; j < (i + 1) *m; j+) accessj = (p + rand

19、() % e) % 64; double r = (rand() % 10) / 10.0; if (r < t) p = rand() % 64; else p = (p + 1) % 64; bool isInNodes (int n) int i; for (i = 0; i < 3; i+) if (nodesi.data = accessn) return true; return false;LNode* isinLinks (int n) LNode*p, *q; p = idle.next; q = NULL; while (p) if (p->data =

20、accessn) if (q != NULL) q->next = p->next; p->next = NULL; idle.num-; break; else idle.next = NULL; q = p; p = p->next; if (p = NULL) p = modified.next; while (p != NULL) if (p->data = accessn) if (p = modified.next) modified.next = p->next; else q->next = p->next; p->next

21、 = NULL; modified.num-; if (modified.num = 0) modified.next = NULL; break; q = p; p = p->next; return p;void PBA (int n) if (isInNodes (n) printf ("已装入内存n"); else if (index = size) LNode *p; if ( (p = isinLinks (n) != NULL) nodes = (LNode*) realloc (nodes, (size + 1) * sizeof (LNode); n

22、odessize .data = p->data; nodessize.flag = p->flag; nodessize.modify = p->modify; nodessize.next = p->next; free (p); size+; index+; else lost+;/缺页 if (nodesn % 3.modify = 1) addToLink (nodesn % 3.data, 1); else addToLink (nodesn % 3.data, 0); nodesn % 3.data = accessn; nodesn % 3.flag =

23、 1; nodesn % 3.next = NULL; if (rand() % 10 < 4) nodesn % 3.modify = 0; else nodesn % 3.modify = 1; else nodesindex.data = accessn; nodesindex.flag = 1; nodesindex.next = NULL; if (rand() % 10 < 4) nodesindex.modify = 1; else nodesindex.modify = 0; index+; void addToLink (int data, int type) L

24、Node* p; LNode* q; q = (LNode*) malloc (sizeof (LNode); q->data = data; q->flag = 1; if (type = 1) q->modify = 1; p = modified.next; else q->modify = 0; p = idle.next; q->next = NULL; if (p = NULL) if (type = 0) idle.next = q; else modified.next = q; else while (p) if (p->next = NU

25、LL) p->next = q; break; else p = p->next; if (type = 0) idle.num += 1; if (idle.num = 10) emptyIdle(); else modified.num += 1; if (modified.num = 10) emptyModi(); void emptyIdle () LNode* p; p = idle.next; while (p) idle.next = p->next; free (p); p = idle.next; idle.num = 0;void emptyModi()

26、 LNode* p; p = modified.next; while (p) modified.next = p->next; free (p); p = modified.next; modified.num = 0;FIFO.cpp/ FIFO.cpp : 定义控制台应用程序的入口点。#include "stdafx.h"#include"stdio.h"#include"stdlib.h"#include"time.h"typedef struct node int num; node* next;

27、Node, *pNode;typedef struct queue int n; pNode front; pNode rear; Queue, *pQueue;void initQueue (pQueue q);void push (pQueue q, int num);void pop (pQueue q);void destroy (pQueue q);bool findInQueue (pQueue q, int num);void generate();void fifoTest();void fifo (pQueue q, int num);int access32;/访问序列in

28、t size = 3;/给进程分配的内存的大小int lost = 0;/缺页数int _tmain (int argc, _TCHAR* argv) /generate(); fifoTest(); getchar(); getchar(); return 0;void initQueue (pQueue q) q->rear = (pNode) malloc (sizeof (Node); if (q->rear = NULL) printf ("failedn"); else q->front = q->rear; q->rear->

29、;next = NULL; q->front->next = NULL; q->n = 0; void push (pQueue q, int num) pNode p = (pNode) malloc (sizeof (Node); if (p = NULL) printf ("failed"); else p->next = NULL; p->num = num; if (q->front = q->rear) q->front->next = p; q->rear = p; else q->rear-&

30、gt;next = p; q->rear = p; q->n+; void pop (pQueue q) pNode p; if (q->front != q->rear) p = q->front->next; q->front->next = p->next; if (p = q->rear) q->front = q->rear; q->n-; free (p); void destroy (pQueue q) while (q->front != q->rear) pop (q); bool fi

31、ndInQueue (pQueue q, int num) pNode p; if (q->front != q->rear) p = q->front->next; while (p) if (p->num = num) return true; else p = p->next; return false;/*生成具有局部访问特点的访问序列*/void generate() srand ( (unsigned) time (NULL); /用时间做种，每次产生随机数不一样 int p = rand() % 64; int m = 8, e = 8; in

32、t i, j; double t; t = rand() % 10 / 10.0; for (i = 0; i < 4; i+) for (j = i * m; j < (i + 1) *m; j+) accessj = (p + rand() % e) % 64; double r = (rand() % 10) / 10.0; if (r < t) p = rand() % 64; else p = (p + 1) % 64; void fifoTest() Queue q; pNode p; initQueue (&q); int i = 0; printf (

33、"先进先出置换算法n"); for (; i < 32; i+) fifo (&q, accessi); p = q.front->next; while (p) printf ("%d ", p->num); p = p->next; printf ("n"); printf ("先进先出算法缺页率：%f %dn", lost / 32.0, lost); destroy (&q);void fifo (pQueue q, int num) if (findInQueue

34、(q, num) printf ("已装入内存n"); else if (q->n = size) pop (q); push (q, num); lost+; else push (q, num); experiment5.cpp#include "stdafx.h"#include "stdio.h"#include"stdlib.h"#include"time.h"#define R 32 /物理内存块数#define V 64 /虚拟内存块数struct LNode int dat

35、a; int flag;/访问位 int modify;/修改位;void initMemo();void generate();/生成访问序列bool isInMemo (int n); /void optimal (int n); /void testOptimal();void LRU (int n);void testLRU();void updated_Clock (int n);void test_Clock();int block = 3;int access32; /访问序列int* memo;int lost = 0;/没找到的页面数int index = 0;/指示当前下标

36、LNode* nodes;/改进型Clock置换算法用到的数据结构int _tmain (int argc, _TCHAR* argv) generate(); testOptimal(); testLRU(); test_Clock(); int i = 0; for (; i < 32; i+) printf ("%d, ", accessi); getchar(); getchar(); return 0;void generate() srand ( (unsigned) time (NULL); /用时间做种，每次产生随机数不一样 int p = rand(

37、) % 64; int m = 8, e = 8; int i, j; double t; t = rand() % 10 / 10.0; for (i = 0; i < 4; i+) for (j = i * m; j < (i + 1) *m; j+) accessj = (p + rand() % e) % 64; double r = (rand() % 10) / 10.0; if (r < t) p = rand() % 64; else p = (p + 1) % 64; void initMemo() memo = (int*) malloc (block *

38、 sizeof (int); int i = 0; for (; i < block; i+) memoi = -1; return;void testOptimal() initMemo(); int i = 0; printf ("最佳置换算法：n"); for (; i < 32; i+) optimal (i); printf ("%d %d %dn", memo0, memo1, memo2); printf ("最佳置换算法缺页率： %2f %dn", lost / 32.0, lost); lost = 0; free (mem