呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

《操作系统》实验之虚拟存储管理

实验内容:

<一> 

   第一部分:模拟请求分页虚拟存储管理技术中的硬件地址变换和缺页中断的过程

   提示:

1、             请求分页虚拟存储管理技术是把作业地址空间的全部信息存放在磁盘上,当作业被选中运行时,先把作业的开始几页装入主存并启动运行.为此,在为作业建立页表时,应说明哪些页已在内存,哪些页不在内存.

 

 

        页表的格式如下:

 

页号

标志

主存块号

外存地址

 

 

 

 

 

 

 

 

 

 

 

 

 

    其中,”标志”表示对应页是否已装入主存

                        0:表示对应页已装入主存

                        1:表示对应页未装入主存

         “主存块号”表示该页对应的主存块的块号

         “外存地址”表示该页所在的外存物理

2、             作业在执行时,指令中的逻辑地址指出参加运算操作数(或指令)地址中的页号和页内偏移量.硬件地址转换机构按页号查页表.

      若该页的标志为”1”,则表示该页已在主存,从而找到该页对应的内存块号,根据关系式:

        绝对地址=块号*块的长度+页内偏移量

     计算出欲访问的内存地址.由于页长为2的整次幂,所以只要将块号与页内偏移量相拼接,放入地址寄存器即可按照该地址取指令或取操作数,完成指定的操作.

   若对应的页不在内存(即标志为0),则硬件产生缺页中断,转操作系统处理系统.根据页表中的”外存地址”,找到该页.再查内存分块表,找一个空闲块装入该页,修改页表和内存分块表,继续执行被中断的指令.

3、             设计一个”地址变换”程序,模拟硬件地址变换过程:

   当访问的页在内存时,则形成绝对地址后,不去模拟指令的执行,而是输出被转换的地址;当访问的页不在内存时,则输出*该页(页号)不在内存,以表示产生了一次缺页中断;若地址非法,显示地址非法,并终止程序的运行.

 

 

   假定内存的每块长度为128字节,现有一个只有七页的作业,其中第0页至第3页已经装入内存.该作业的页表如下:

 页号

  标志

 内存块号

 外存地址

  修改值

   0

   1

    5

   011

     1

   1

   1

    8

   012

     1

   2

   1

    9

   013

     0

   3

   1

    1

   021

     0

   4

   0

 

   022

 

   5

   0

 

   023

 

   6

   0

 

   121

 

 

 

 

   作业执行的指令序列如下表:

操作

页号

单元号(八进制)

操作

页号

单元号(八进制)

 +

  0

    070

移位

 4

    053

 +

  1

    050

 +

 5

    023

 *

  2

    015

 存

 1

    037

 存

  3

    021

 取

 2

    076

 取

  0

    057

 +

 4

    001

 -

  6

    040

 取

 6

    084

 

   运行你设计的地址变换程序,显示或打印运行结果.因为只是模拟地址变换,并不模拟指令的执行,故不考虑上述指令的操作结果.

   第二部分:采用先进先出(或LRU)算法,实现分页管理的缺页调度.

   提示:

1、             在分页虚拟存储系统中,当硬件发出缺页中断时,若内存中已无空闲块,当采用FIFO算法时,则淘汰最先进入内存的页,若该页修改过,还要存入磁盘,然后,再把当前要访问的页装入该块,并修改表中的对应标志.

2、             当采用LRU算法时,则淘汰最近很少访问的页.

两算法均可采用一个数组或链表记录内存中页号的排序,每次将链首页淘汰.数组或链表中只包含页的虚页号─项信息,其它信息通过查页表得到.

 

实现:

实现的算法是LRU算法,模拟了硬件地址变换和缺页中断过程。

运行结果:

源代码:

  1 /*
  2  * 该程序使用了位图LRU置换算法
  3  */
  4 
  5 #include <iostream>
  6 #include <string.h>
  7 #include <stdio.h>
  8 using namespace std;
  9 
 10 //宏定义
 11 #define PAGE_TABLE_SIZE 10    //页表大小
 12 #define BITMAP_SIZE    10    //位图大小。块大小为128B,则内存大小:10*128B = 1280B
 13 #define BLOCK_SIZE 128    //块大小为128B
 14 
 15 //结构体
 16 struct Page{    //
 17     bool flag;                //标志,是否存入内存
 18     unsigned short blockNo;    //主存块号
 19     unsigned short addr;    //外村地址
 20     bool isMod;                //修改位
 21 };
 22 
 23 struct JobWork{    //作业指令
 24     char operation[5];    //操作名称
 25     unsigned short PageNo;    //页号
 26     unsigned short UnitNo;    //单元号
 27 };
 28 
 29 struct LRUNode{    //LRU链表节点
 30     unsigned short PageNo;    //页号
 31     LRUNode *next;        //指向下一个节点的指针
 32 };
 33 
 34 //局部变量
 35 Page PageTable[PAGE_TABLE_SIZE];    //定义页表
 36 bool BitMap[BITMAP_SIZE];    //定义内存位图
 37 JobWork work[20];    //作业执行的指令序列
 38 
 39 int PageTableNum;    //当前页表大小
 40 int workNum;        //当前作业指令集大小 
 41 
 42 LRUNode *LRUqueue;    //LRU(最近最久未使用算法)队列
 43 
 44 //局部函数
 45 void Init();    //初始化,页表,位图等
 46 unsigned short GetAddr(unsigned short curPage,unsigned short UnitNo);    //输入 页号和页内偏移,得到绝对地址
 47 void Insert(unsigned short page);    //将最近使用的页插入到LRU队列中 或 在LRU队列中调整位置,使其始终保持最近最久未使用的页表节点在前面
 48 int FindFreeBlock();        //在内存中查找空闲块
 49 void DropLRUHead();            //丢弃掉LRU队列的第一个结点
 50 void DisplayPageTable();    //打印页表
 51 void DisplayLRUQueue();        //打印LRU队列
 52 
 53 //主函数
 54 int main()
 55 {
 56     int i;
 57     Init();    //初始化
 58 
 59     printf("初始页表:\n");
 60     DisplayPageTable();
 61     printf("\n");
 62     printf("初始LRU队列:\n");
 63     DisplayLRUQueue();
 64     printf("\n");
 65 
 66     for(i=0;i<workNum;i++){    //模拟取指令 
 67         printf("-------------------- 第%d条指令:%s -----------------------\n",i+1,work[i].operation);
 68         printf("取指令\n");
 69 
 70         unsigned short curPage = work[i].PageNo;    //取该指令页号
 71         printf("取出页号:%d\n",curPage);
 72 
 73         //判断地址是否非法
 74         if(curPage<0 || curPage>PageTableNum){    //页号非法
 75             printf(" 访问地址非法\n");
 76             return 0;
 77         }
 78         if(work[i].UnitNo<0 || work[i].UnitNo>=BLOCK_SIZE){    //页内偏移地址非法
 79             printf(" 访问地址非法\n");
 80             return 0;
 81         }
 82 
 83         //判断该页是否在内存
 84         while( PageTable[curPage].flag!=1 ){
 85             printf(" 该页不在内存\n");
 86             printf(" 发出缺页中断\n");
 87             int freeBlock = -1;
 88             if( (freeBlock = FindFreeBlock())==-1 ){    //找内存中的空闲块。
 89                 printf(" 没有在内存中找到空闲块,调用LRU页面置换算法\n");
 90 
 91                 unsigned short dropPage = LRUqueue->next->PageNo;    //被淘汰的页号
 92                 printf("  获得被淘汰的页号(%d)\n",dropPage);
 93 
 94                 if( PageTable[dropPage].isMod==1 ){    //该页修改过
 95                     printf("   该页修改过,将该页调到磁盘");
 96                     PageTable[dropPage].isMod = 0;
 97                 }
 98 
 99                 printf("  丢弃该页\n");
100                 PageTable[dropPage].flag = 0;
101                 DropLRUHead();    //丢弃掉LRU队列的第一个结点
102                 unsigned short dropBlock = PageTable[dropPage].blockNo;
103                 PageTable[dropPage].blockNo = -1;
104 
105                 printf("  调进页(%d)到内存\n",curPage);
106                 Insert(curPage);
107                 PageTable[curPage].flag = 1;
108                 PageTable[curPage].blockNo = dropBlock;
109             }
110             else{    //找到空闲块
111                 //在页表中找到页号对应的页,修改标志位,赋给它内存块号
112 
113                 printf("  在内存中找到空闲块,赋给给相应的页\n");
114                 PageTable[curPage].blockNo = freeBlock;
115                 PageTable[curPage].flag = 1;
116                 BitMap[freeBlock] = 1;
117                 Insert(curPage);
118             }
119             
120         }
121         //该页在内存,形成并输出绝对地址
122         printf(" 该页在内存中\n");
123         unsigned short absAddr = GetAddr(curPage,work[i].UnitNo);    //输入 页号和页内偏移,得到绝对地址
124         Insert(curPage);    //调整内存页排序表(LRU队列)
125 
126         if( strcmp(work[i].operation,"")==0 ){
127             //如果是存指令
128             printf("  是存指令,置该页的修改位为 1\n");
129             PageTable[curPage].isMod = 1;
130         }
131 
132         printf("绝对地址为:0x%04X\n",absAddr);
133         printf("\n");
134         printf("当前页表:\n");
135         DisplayPageTable();
136         printf("\n");
137         printf("当前LRU队列:\n");
138         DisplayLRUQueue();
139         printf("-----------------------------------------------------------\n");
140         printf("\n");
141 
142     }
143     return 0;
144 }
145 
146 //函数实现
147 void Insert(unsigned short page)    //将最近使用的页插入到LRU队列中 或 在LRU队列中调整位置,使其始终保持最近最久未使用的页表节点在前面
148 {
149     //查找链表,如果找到page,将代表该page的节点移到链表最后,说明刚刚使用过该页
150     LRUNode *p = LRUqueue;
151     while(p->next!=NULL){
152         if(p->next->PageNo==page){
153             //找到该节点,将其移动到LRU链表最后
154             LRUNode *t = p->next;
155             p->next = t->next;
156             while(p->next!=NULL){
157                 p = p->next;
158             }
159             p->next = t;
160             t->next = NULL;
161             return ;
162         }
163         p = p->next;
164     }    
165     //如果没有找到page,则创建一个代表该page的节点,加入到LRU链表最后
166     if(p->PageNo!=page){
167         LRUNode* t = new LRUNode;    //创建节点
168         t->PageNo = page;
169         t->next = NULL;
170         p->next = t;
171     }
172     //最后一个节点是page的情况不用考虑,因为它本身就在最后,不用移位
173     return ;
174 }
175 
176 void Init()    //初始化,页表,位图等
177 {
178     memset(PageTable,0,sizeof(PageTable));
179     memset(BitMap,0,sizeof(BitMap));
180     PageTableNum = 0;
181     workNum = 0;
182     LRUqueue = new LRUNode;
183     LRUqueue->next = NULL;
184 
185     //初始化页表
186     PageTable[0].flag = 1;
187     PageTable[0].blockNo = 5;
188     PageTable[0].addr = 0x0011;
189     PageTable[0].isMod = 1;
190     Insert(0);
191     PageTableNum++;
192 
193     PageTable[1].flag = 1;
194     PageTable[1].blockNo = 8;
195     PageTable[1].addr = 0x0012;
196     PageTable[1].isMod = 1;
197     Insert(1);
198     PageTableNum++;
199 
200     PageTable[2].flag = 1;
201     PageTable[2].blockNo = 9;
202     PageTable[2].addr = 0x0013;
203     PageTable[2].isMod = 0;
204     Insert(2);
205     PageTableNum++;
206 
207     PageTable[3].flag = 1;
208     PageTable[3].blockNo = 1;
209     PageTable[3].addr = 0x0021;
210     PageTable[3].isMod = 0;
211     Insert(3);
212     PageTableNum++;
213 
214     PageTable[4].flag = 0;
215     PageTable[4].blockNo = -1;
216     PageTable[4].addr = 0x0022;
217     PageTable[4].isMod = 0;
218     PageTableNum++;
219 
220     PageTable[5].flag = 0;
221     PageTable[5].blockNo = -1;
222     PageTable[5].addr = 0x0023;
223     PageTable[5].isMod = 0;
224     PageTableNum++;
225 
226     PageTable[6].flag = 0;
227     PageTable[6].blockNo = -1;
228     PageTable[6].addr = 0x0121;
229     PageTable[6].isMod = 0;
230     PageTableNum++;
231 
232     //初始化作业
233     strcpy(work[0].operation,"+");
234     work[0].PageNo = 0;
235     work[0].UnitNo = 070;
236     workNum++;
237 
238     strcpy(work[1].operation,"+");
239     work[1].PageNo = 1;
240     work[1].UnitNo = 050;
241     workNum++;
242 
243     strcpy(work[2].operation,"*");
244     work[2].PageNo = 2;
245     work[2].UnitNo = 015;
246     workNum++;
247 
248     strcpy(work[3].operation,"");
249     work[3].PageNo = 3;
250     work[3].UnitNo = 021;
251     workNum++;
252 
253     strcpy(work[4].operation,"");
254     work[4].PageNo = 0;
255     work[4].UnitNo = 057;
256     workNum++;
257 
258     strcpy(work[5].operation,"-");
259     work[5].PageNo = 6;
260     work[5].UnitNo = 040;
261     workNum++;
262 
263     strcpy(work[6].operation,"移位");
264     work[6].PageNo = 4;
265     work[6].UnitNo = 053;
266     workNum++;
267 
268     strcpy(work[7].operation,"+");
269     work[7].PageNo = 5;
270     work[7].UnitNo = 023;
271     workNum++;
272     
273     strcpy(work[8].operation,"");
274     work[8].PageNo = 1;
275     work[8].UnitNo = 037;
276     workNum++;
277     
278     strcpy(work[9].operation,"");
279     work[9].PageNo = 2;
280     work[9].UnitNo = 076;
281     workNum++;
282     
283     strcpy(work[10].operation,"+");
284     work[10].PageNo = 4;
285     work[10].UnitNo = 001;
286     workNum++;
287 
288     strcpy(work[11].operation,"");
289     work[11].PageNo = 6;
290     work[11].UnitNo = 074;
291     workNum++;
292 
293     //将剩余的内存置为非空,即预先设定内存没有空闲位
294     int i;
295     for(i=0;i<BITMAP_SIZE;i++){
296         if(!BitMap[i])
297             BitMap[i] = 1;
298     }
299 
300     return ;
301 }
302 
303 unsigned short GetAddr(unsigned short curPage,unsigned short UnitNo)    //输入 页号和页内偏移,得到绝对地址
304 {
305     unsigned short absAddr = 0;    //结果
306 
307     unsigned short curBlock = PageTable[curPage].blockNo;    //取块号
308     absAddr = curBlock*BLOCK_SIZE + UnitNo;
309 
310     return absAddr;
311 }
312 
313 int FindFreeBlock()        //在内存中查找空闲块
314 {
315     int i;
316     for(i=0;i<BITMAP_SIZE;i++){
317         if(BitMap[i]==0){    //找到空闲块,返回块号
318             return i;
319         }
320     }
321     return -1;    //没找到
322 }
323 
324 void DropLRUHead()                    //丢弃掉LRU队列的第一个结点
325 {
326     LRUNode *t = LRUqueue->next;
327     LRUqueue->next = t->next;
328     free(t);
329 }
330 
331 void DisplayPageTable()    //打印页表
332 {
333     int i;
334     printf("页号\t标志\t内存块号\t外存地址\t修改值\n");
335     for(i=0;i<PageTableNum;i++){
336         printf("%d\t",i);
337         printf("%d\t",PageTable[i].flag);
338         if(PageTable[i].blockNo==65535){
339             printf("-\t\t");
340         }
341         else{
342             printf("%d\t\t",PageTable[i].blockNo);
343         }
344         printf("0x%03x\t\t",PageTable[i].addr);
345         printf("%d\n",PageTable[i].isMod);
346     }
347     return ;
348 }
349 
350 
351 void DisplayLRUQueue()        //打印LRU队列
352 {
353     LRUNode *q = LRUqueue->next;
354     while(q!=NULL){
355         if(q->next==NULL)
356             printf("%d\n",q->PageNo);
357         else
358             printf("%d->",q->PageNo);
359         q = q->next;
360     }
361 }

 原创声明

Freecode# : www.cnblogs.com/yym2013

 

##原创声明 **转载请注明:[呓语](http://www.yangyingming.com) » [《操作系统》实验之虚拟存储管理](http://www.yangyingming.com/article/33)**