請求調(diào)頁存儲管理方式的模擬

1、實驗3請求調(diào)頁存儲管理方式的模擬1實驗?zāi)康耐ㄟ^對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實現(xiàn)過程的理解。2實驗內(nèi)容（1）假設(shè)每個頁面中可存放10條指令，分配給一作業(yè)的內(nèi)存塊數(shù)為4。（2）模擬一作業(yè)的執(zhí)行過程。該作業(yè)共有320條指令，即它的地址空間為32頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果所訪問的指令已經(jīng)在內(nèi)存中，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時需記錄缺頁的次數(shù)，并將相應(yīng)頁調(diào)入內(nèi)存。如果4個內(nèi)存塊中均已裝入該作業(yè)，則需進行頁面置換。最后顯示其物理地址，并轉(zhuǎn)下一條指令。在所有320條指令執(zhí)行完畢后，請計算并

2、顯示作業(yè)運行過程中發(fā)生的缺頁率。（3）置換算法：請分別考慮OPT、FIFO和LRU算法。（4）作業(yè)中指令的訪問次序按下述原則生成：50%的指令是順序執(zhí)行的。25%的指令是均勻分布在前地址部分。25%的指令時均勻分布在后地址部分。代碼：package mainDart;import java.util.ArrayList;import java.util.List;import java.util.Random;public class FIFO private static int times=0;/記錄置換內(nèi)存頁面的次數(shù)/* * 隨機產(chǎn)生0319之間的數(shù) * 產(chǎn)生320條指令 * * ret

3、urn 包含320條指令的數(shù)組 */public static int productNumber()int order = new int320;/數(shù)組存儲的數(shù)字表示指令Random rand = new Random();for(int i=0;i<320;i+) if(i%4=0) orderi=rand.nextInt(319); /0<=order<319 else if(i%4=1) orderi=orderi-1+1;/1<=order<320 else if(i%4=2) orderi= rand.nextInt(orderi-1); else i

4、f(i%4=3) orderi=orderi-1+rand.nextInt(320-orderi-1); return order;/* * 打印鏈表 * param list */public static void printList(List<Integer> list)for(int temt:list)System.out.print(temt+"t");System.out.println();/* * 先進先出算法 * 總是淘汰最先進入內(nèi)存的頁面 * 在實現(xiàn)的時候，記錄上一次所替換的頁面在內(nèi)存的下標，則本次要替換的位置就是上次下標+1的位置，并且下

5、標是03循環(huán)的 * param memoryNum * param page */public static void FIFOChangePage(List<Integer> memoryNum,int page)int index = FIFOChangePage(memoryNum,page,+times);memoryNum.remove(index);memoryNum.add(index, page);/* * 返回本次替換的頁面在內(nèi)存中的位置 * param memoryNum * param page * param times記錄替換頁面的次數(shù)，第一次替換的是內(nèi)存

6、第0個單元 * return */public static int FIFOChangePage(List<Integer> memoryNum,int page,int times)if(times=1)return 0;int index = (FIFOChangePage(memoryNum,page,times-1)+1)%4;return index;public static void main(String args) int order = productNumber();System.out.println("320條隨機指令數(shù)：");for

7、(int i =0;i<order.length;i+)System.out.print(orderi+"t");if(i+1)%10=0)System.out.println();List<Integer> memoryNum= new ArrayList<Integer>(4);/內(nèi)存塊存儲的頁面int count=0;/記錄缺頁次數(shù)for(int i=0;i<320;i+)int page = orderi/10;if(memoryNum.contains(page) /若該指令所在頁面已經(jīng)在內(nèi)存，輸出該頁面所在內(nèi)存塊的號else/

8、沒在內(nèi)存，發(fā)生缺頁，需要判斷內(nèi)存塊是否存滿，if(memoryNum.size()<4) /內(nèi)存沒滿，直接將所需頁面調(diào)入內(nèi)存memoryNum.add(page);else/內(nèi)存存滿，需要調(diào)用頁面置換算法，進行頁面置換FIFOChangePage(memoryNum,page);/先進先出算法count+;/記錄缺頁次數(shù)printList(memoryNum);/打印內(nèi)存所調(diào)入頁面的情況System.out.println("缺頁率："+(double)count/320);package mainDart;import java.util.ArrayList;imp

9、ort java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Random;public class LRU /* * 隨機產(chǎn)生0319之間的數(shù) * 產(chǎn)生320條指令 * * return 包含320條指令的數(shù)組 */public static int productNumber()int order = new int320;/數(shù)組存儲的數(shù)字表示指令Random rand = new Random();for(int i=0;i<320;i+) if(i%4=0) orderi=ran

10、d.nextInt(319); /0<=order<319 else if(i%4=1) orderi=orderi-1+1;/1<=order<320 else if(i%4=2) orderi= rand.nextInt(orderi-1); else if(i%4=3) orderi=orderi-1+rand.nextInt(320-orderi-1); return order;/* * 打印鏈表 * param list */public static void printList(List<Integer> list)for(int temt:

11、list)System.out.print(temt+"t");System.out.println();/* * 最近最久未使用算法 * param order */public static void LRUChangePage(int order)List<Integer> memoryNum = new ArrayList<Integer>(4);/內(nèi)存塊int timeFlag =new int-1,-1,-1,-1; /用來記錄內(nèi)存當中各單元未被訪問的時間值int count=0;/記錄缺頁次數(shù)for(int i=0;i<320;i

12、+)int page = orderi/10;if(memoryNum.contains(page) /若該指令所在頁面已經(jīng)在內(nèi)存int index = memoryNum.indexOf(page);timeFlagindex=0;/將時間變?yōu)?else/沒在內(nèi)存，發(fā)生缺頁，需要判斷內(nèi)存塊是否存滿，if(memoryNum.size()<4) /內(nèi)存沒滿，直接將所需頁面調(diào)入內(nèi)存/將沒有命中的所有頁面的時間加一for(int in=0;in<4;in+)if(timeFlagin!=-1)timeFlagin+=1;/將page加入內(nèi)存并將時間置為0memoryNum.add(pa

13、ge);timeFlagmemoryNum.indexOf(page)=0;else/內(nèi)存存滿，需要調(diào)用頁面置換算法，進行頁面置換int maxIn=-1;/記錄擁有最大時間值的標記的下標int maxT=-1;/記錄最大的時間值for(int in=0;in<4;in+)/找出內(nèi)存中時間值最大的進行替換if(timeFlagin>maxT)maxT=timeFlagin;maxIn=in;memoryNum.remove(maxIn);memoryNum.add(maxIn,page);timeFlagmaxIn=0;/將沒有命中的所有頁面的時間加一for(int in=0;in

14、<4;in+)if(in!=maxIn)timeFlagin+=1;count+;/記錄缺頁次數(shù)printList(memoryNum);/打印內(nèi)存所調(diào)入頁面的情況System.out.println("缺頁率："+(double)count/320);public static void main(String args) int order = productNumber();System.out.println("320條隨機指令數(shù)：");for(int i =0;i<order.length;i+)System.out.print(o

15、rderi+"t");if(i+1)%10=0)System.out.println();LRUChangePage(order);package mainDart;import java.util.ArrayList;import java.util.List;import java.util.Random;public class Optimal /* * 隨機產(chǎn)生0319之間的數(shù) * 產(chǎn)生320條指令 * * return 包含320條指令的數(shù)組 */public static int productNumber()int order = new int320;/數(shù)組

16、存儲的數(shù)字表示指令Random rand = new Random();for(int i=0;i<320;i+) if(i%4=0) orderi=rand.nextInt(319); /0<=order<319 else if(i%4=1) orderi=orderi-1+1;/1<=order<320 else if(i%4=2) orderi= rand.nextInt(orderi-1); else if(i%4=3) orderi=orderi-1+rand.nextInt(320-orderi-1); return order;/* * * para

17、m order320條指令數(shù)組 * return 返回一個鏈表，依次保存著320條指令每條指令所在的頁面 */public static List<Integer> pageSeq(int order)List<Integer> pageSeq = new ArrayList<Integer>();for(int temp:order)pageSeq.add(temp/10);return pageSeq;/* * 打印鏈表 * param list */public static void printList(List<Integer> lis

18、t)for(int temt:list)System.out.print(temt+"t");System.out.println();/* * 最佳置換算法 * 根據(jù)當前已經(jīng)在內(nèi)存中的頁面在之后被需要的先后進行置換 * * param pageSeq 整個320條指令，從頭到尾所需要的頁面 * param memoryNum 已滿的內(nèi)存空間 * param page等待被調(diào)入內(nèi)存的頁面 */public static void OptimalChangePage(List<Integer> pageSeq,int start,List<Integer&g

19、t; memoryNum,int page)int maxSeq=-1,index=0;for(int pageNum:memoryNum) /遍歷內(nèi)存for(int i=start;i<pageSeq.size();i+)if(pageNum=pageSeq.get(i)if(i>maxSeq)maxSeq=i;break;if(maxSeq>-1)/maxSeq=-1說明內(nèi)存當中的四個頁面在將來都不會再被使用，這時默認將內(nèi)存塊中的第一個頁面置換出index = memoryNum.indexOf(pageSeq.get(maxSeq);/記錄將要被置換的那個頁面所在內(nèi)存位

20、置 memoryNum.remove(index);/將內(nèi)存中將來最久被使用的頁面刪除memoryNum.add(index, page);/將需要調(diào)入的頁面加入內(nèi)存public static void main(String args) int order = productNumber();System.out.println("320條隨機指令數(shù)：");for(int i =0;i<order.length;i+)System.out.print(orderi+"t");if(i+1)%10=0)System.out.println();List<Integer> pageSeq = pageSeq(order); /依次存放著指令所在的頁面號List<Integer> memoryNum= new ArrayList<Integer>(4);/內(nèi)存塊存儲的頁面int count=