请求分页存储管理

实验 3 请求分页存储管理实验目的（1）熟悉主存的分配与回收；（2）了解虚拟存储技术的特点；（3）掌握请求页式存储管理的页面置换算法；实验内容与步骤1、实验准备知识（1）通过随机数产生一个指令序列（2）将指令序列变换成为页地址流设：（3）计算并输出下述各种算法在不同内存容量下的命中率a）先进先出的算法（FIFO）；b）最近最少使用算法（LRU）；c）最佳淘汰算法（OPT）；（4）所涉及的算法1） FIFO 算法定义变量 ptr。一开始先预调页填满内存。在这一部分，ptr指向下一个要存放的位置。 之后继续执行剩下的指令。此时， ptr 表示队列最前面的位置，即最先进来的位 置，也就是下一个要被替换的位置。ptr用循环加，即模拟循环队列。2）LRU 算法定义数组ltu,即last_time_use来记录该页最近被使用的时间。定义变量 ti 模拟时间的变化，每执行一次加一。 这个算法，我没有预调页，而是直接执行所有指令。若当前需要的页没在内存里，就寻找最近最少使用的页，也就是ltu最小的页， 即最近一次使用时间离现在最久的页，然后替换掉它。或者在内存还未满时，直 接写入，这个我以初始化内存里所有页为-1 来实现。若已经在内存里了，则只遍历内存内的页，把当前页的最近使用时间改一下即可。3）OPT算法定义数组 ntu, 即 next_time_use 来记录下一次被使用的时间，即将来最快使用 时间。初始化为-1.开始时预调页填满内存里的页。同样利用变量 ptr 来表示下一个要存放的位 置从而控制预调页的过程。接着初始化 ntu 数组为-1。然后求出每一页下一次被使用的指令号，以此代 替使用时间。如果所有剩下的序列都没有用该页时，则还是 -1.这种值为-1 的页 显然是最佳替换对象。然后执行所有剩下的指令。当该页不在内存里时，遍历ntu数组，遇到-1的 直接使用该页，没有则用ntu值最大的，也就是最晚使用的。无论该页在不在内存里，因为这一次已经被使用了，所以都应该更新这个页 的ntu,只需往前看要执行的页流，记录下第一个遇到的该页即可。如果没有 找到同样添-1 即可。2、实验步骤(1) 首先，初始化数据(2) 测试地址转换机构参考代码如下：private void AddressTransform(string functionName)/该数组用来存储调用页面号的序列int numbers = _pageNumbers;/调用页面列表的副本，用于循环调用列表时的操作ListPageTableEntry copylnvokeTable = new ListPageTableEntry()；/初始化调用页表和快表for (in t i = 0; i 0，跳出循 环结束页面调度if (_mark 0)break;Swi tchTx tToShow(func tionName, rn 当前调度的页面号为：+ite m.PageNumber.ToS tr ing();/页号页表长度？if (it em.PageNumber _pageTable.Leng th)Swit chTx tToShow(func ti onName,越界中断)；else/查询快表for (in t i = 0; i = _memoryPages.Leng th)Swi tchTx tToShow(func tionName, rn 内存已满，选择+ func tionName + 算法进行页面调度和置换)；/选择一页换出，置换算法 switch (functionName)case Optimal:Opti mal(invokePage);break;case FIFO:FIFO(invokePage);break;case LRU:Lis tintpn = numbers.ToLis t(); LRU(invokePage, pn);break;elseSwi tchTx tToShow(func tionName, rn 内存未满，将该页调入 内存)；for (in t m = 0; m _memoryPages.Leng th; m+)if (_memoryPagesm = null)_isMemoryFull+;_memoryPagesm = new PageTableEntry PageNumber =it em.PageNumber, BlockNumber = it em.BlockNumber ;break;/将该页调入内存后，调用的页表减一if (invokePage != null)/操作invokePage-1，因为在foreach中如果循环的是 invokePage本体，则在这里修改了 invokePage的值之后，下一次循环无法调用，会出现异常，所以定 义了一个copylnvokePage副本专门用来循环invokePage.Remo ve(item);Swi tchTx tToShow(func tionName, rn 当前内存页面为：);ShowMemory(functionName);break;elseSwi tchTx tToShow(func tionName, rn 该调度页面不在快表中，查 询页表)；/访问页表for (in t p = 0; p = _memoryPages.Leng th)Swi tchTx tToShow(func tionName, rn 内存已满，选择+ func tionName + 算法进行页面调度和置换)；/选择一页换出，置换算法switch (functionName)case Optimal:Opti mal(invokePage);break;case FIFO:FIFO(invokePage);break;case LRU:Lis tintpn = numbers.ToLis t();LRU(invokePage, pn);break;elseSwit chTx tToShowfunc ti onName, rn 内存未 满，将该页调入内存)；for (in t m = 0; m = _memoryPages.Leng th)Swi tchTx tToShowfunc tionName, rn 内存已 满，选择+ func tionName + 算法进行页面调度和置换)；/选择一页换出，置换算法 switch (functionName)case Optimal:Opti mal(invokePage); break;case FIFO: FIFO(invokePage); break;case LRU:Lis tintpn = numbers.ToLis t(); LRU(invokePage, pn);break;else/换入内存，修改页表 pl.IsInMemory = tr ue; _pageTablep = p1;if (_isMemoryFull = _memoryPages.Length)Swit chTx tToShow(func ti onName, rn 内存 已满，选择+ func tionName + 算法进行页面调度和置换)；/选择一页换出，置换算法 switch (functionName)case Optimal:Opti mal(invokePage); break;case FIFO: FIFO(invokePage); break;case LRU:Lis tintpn = numbers.ToLis t(); LRU(invokePage, pn);break;elseSwit chTx tToShow(func ti onName, rn 内存 未满，调入该页，当前内存页面为：)；for (in t m = 0; m _memoryPages.Leng th;m+)if (_memoryPagesm = null)_isMemoryFull+;_memoryPagesm = p1; break;/调用的页表减一if (invokePage != null)invokePage.Remo ve(item); ShowMemory(functionName);break;break;(3 )测试先进先出算法FIFO,并计算缺页率，参考代码如下:private void FIFO(List invokePageFifo)/标志位，只要这个算法有被执行， mark 自增一次_mark+;/内存页面的下标，从 0开始，从第一个开始替换int memoryNumber = 0;/统计当前调用页面和内存中各个页面的不相等数int unEquar = 0;/开始循环调用页面列表txtFIFOShow.Text += rn 调 入 页 invokePageFifoi.PageNumber.ToString();/ 循环判断内存总的页面和该调用页面是否相等foreach (var item in _memoryPages)if (item.PageNumber != invokePageFifoi.PageNumber) unEquar+;/ 只要内存中有一个页面和该调用页面不相等if (unEquar = _minBlockNumber)/ 进行页面置换invokePageFifoi.IsInMemory = true; _memoryPagesmemoryNumber = invokePageFifoi;/ 内存下标自增，表示下一次将要置换的页面的下标 memoryNumber+;if (memoryNumber = _minBlockNumber)memoryNumber = 0;/ 统计的变量自增_replaceTimes+;_lacePageNumber+;/ 显示当前内存信息txtFIFOShow.Text += rn 当前内存页面为： ;ShowMemory(FIFO);else txtFIFOShow.Text += rn 当前内存页面为： ;ShowMemory(FIFO);unEquar = 0;txtFIFOShow.Text += rn 调度结束 ;/ 将一些数据恢复默认_lacePageChance = _lacePageNumber / 20.00;_isMemoryFull = 0;_pageNumbers = new int20 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 ;ShowResult(FIFO);(4 )测试最佳置换算法Optimal，参考代码如下：private void Optimal(List invokePageOptimal)_mark+;int unEquar = 0;/记录内存中页面 在页号数组中出现的 最大的 下标，也就是 该下标就是调用页表中 最晚才会被用到的页面，是要替换出去的页面/ 该集合中存储的是 未被 调用的页面号，已经被调用的页面号不作存储var numbers = new List();/ 初始化页号数组for (int i = 0; i invokePageOptimal.Count; i+)numbers.Add(invokePageOptimali.PageNumber);/循环置换页面for (int i = 0; i = _minBlockNumber)/ 循环页号数组，判断内存中的页面号是否和页号数组中的页号是否相等for (int a = 0; a _memoryPages.Length; a+)/ 循环内存中的页面，页号数组和内存页面的页面号作对比for (int n = 0; n = location)location = n;break;/ 如果内存中的该页面在页号数组中没有找到， isFullError 自增 elseisFullError+;/ 当 isFullError 大于或者等于页号数组的数量时，说明该内存页面 在页号数组中不存在，记录该内存页面的下标，准备将其置换出if (isFullError = numbers.Count)fullErrorLocation = a; break;if (isFullError = numbers.Count)break;elseisFullError = 0;/location 表示内存页面中，谁在调用页表中最靠后的位置 的下标/ 拿到内存中要置换出去的页面号if (isFullError = numbers.Count)_memoryPagesfullErrorLocation = invokePageOptimali;_replaceTimes+;_lacePageNumber+;txtOptimalShow.Text += rn 当前内存页面为： ;ShowMemory(Optimal);elseint pageNum = numberslocation;/ 将该内存页面换出txtOptimalShow.Text += rn 当前内存页面为： ; for (int p = 0; p _memoryPages.Length; p+) if (_memoryPagesp.PageNumber = pageNum) _memoryPagesp = invokePageOptimali; _replaceTimes+;_lacePageNumber+;break;ShowMemory(Optimal);/ 将已经调用完的页面号从页号数组中移除 numbers.RemoveAt(0);/跳出本循环，将页号列表的第一个数移除elsetxtOptimalShow.Text += rn 当前内存页面为： ;ShowMemory(Optimal);numbers.RemoveAt(0);unEquar = 0;txtOptimalShow.Text += rn 调度结束 ;_lacePageChance = _lacePageNumber / 20.00;_isMemoryFull = 0;_pageNumbers = new int20 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 ;ShowResult(Optimal);(5 )测试最近最久未使用算法LRU,参考代码如下：private void LRU(List invokePageLru, List pageNumbersLru)_mark+;int unEquar = 0;/初始化前部调用页表号的数组,已经调用的页号才被存储List partPageNumbers = new List();for (int i = 0; i _minBlockNumber; i+)partPageNumbers.Add(pageNumbersLrui);/循环调用页表for (int i = 0; i = _minBlockNumber)txtLRUShow.Text += rn 调 入 页 面 + invokePageLrui.PageNumber.ToString();/ 计算内存中每个页面在前部页表数组中最后出现的位置int l = 0;/ 位置标识/ 循环前部调用页表数组for (int m = 0; m _memoryPages.Length; m+)/ 判断内存中每个页面在该数组中出现的位置，并与上一个位置比较，将 比较小的存储for (int p = 0; p l)l = p;/ 用 VisitTimes 记录下该内存页面在前部页号数组中的位置 _memoryPagesm.VisitTimes = p;/得到的内存页表中，每一个页面在前部页表数组中中最后出现的位置都已经记录好/ 循环内存中的页面，找出在前部页表数组中第一个出现的一个并将其替换/ 默认替换的页面时内存中的第一个页面PageTableEntry lastPage = _memoryPages0;for (int j = 1; j _memoryPagesj.VisitTimes)lastPage = _memoryPagesj;/ 得到最后出现的页面后，将其置换for (int j = 0; j _memoryPages.Length; j+)if (_memoryPagesj.PageNumber = lastPage.PageNumber)_memoryPagesj = invokePageLrui;_replaceTimes+;_lacePageNumber+; partPageNumbers.Add(invokePagei.PageNumber); txtLRUShow.Text += rn 当前内存页面为： ;ShowMemory(LRU);break; elsetxtLRUShow.Text += rn 调 用 页 面 + invokePageLrui.PageNumber.ToString();txtLRUShow.Text += rn 当前内存页面为： ;ShowMemory(LRU);/ 将已经调用完的页面号加入前部页面数组中partPageNumbers.Add(invokePageLrui.PageNumber);unEquar = 0;txtLRUShow.Text += rn 调度结束 ;_lacePageChance = _lacePageNumber / 20.00;_isMemoryFull = 0;_pageNumbers = new int20 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0,1, 7, 0, 1 ;ShowResult(LRU);