作業系統之程序排程——優先權法和輪轉法（附上樣例講解）作業系統之銀行家算法—詳解流程及案例資料作業系統之多線程程式設計—讀者優先/寫者優先詳解作業系統之存儲管理——FIFO算法和LRU算法作業系統之磁盤排程——SCAN執行個體講解
要求
一、實驗目的存儲管理的主要功能之一是合理地配置設定空間。請求頁式管理是一種常用的虛拟存儲管理技術。本實驗的目的是通過請求頁式管理中頁面置換算法模拟設計，了解虛拟存儲技術的特點，掌握請求頁式存儲管理的頁面置換算法。二、實驗内容（1）通過計算不同算法的命中率比較算法的優劣。同時也考慮了使用者記憶體容量對命中率的影響。頁面失效次數為每次通路相應指令時，該指令所對應的頁不在記憶體中的次數。在本實驗中，假定頁面大小為1k，使用者虛存容量為32k，使用者記憶體容量為4頁到32頁。（2）produce_addstream通過随機數産生一個指令序列，共320條指令。A、指令的位址按下述原則生成：1）50%的指令是順序執行的2）25%的指令是均勻分布在前位址部分3）25%的指令是均勻分布在後位址部分B、具體的實施方法是：1）在[0，319]的指令位址之間随機選取一起點m；2）順序執行一條指令，即執行位址為m 1的指令；3）在前位址[0，m 1]中随機選取一條指令并執行，該指令的位址為m’；4）順序執行一條指令，位址為m’ 1的指令5）在後位址[m’ 2，319]中随機選取一條指令并執行；6）重複上述步驟1）~5），直到執行320次指令C、将指令序列變換稱為頁位址流在使用者虛存中，按每k存放10條指令排列虛存位址，即320條指令在虛存中的存放方式為：第0條~第9條指令為第0頁（對應虛存位址為[0，9]）；第10條~第19條指令為第1頁（對應虛存位址為[10，19]）；。。。。。。第310條~第319條指令為第31頁（對應虛存位址為[310，319]）；按以上方式，使用者指令可組成32頁。（3）計算并輸出下屬算法在不同記憶體容量下的命中率。1）先進先出的算法（FIFO）；2）最近最少使用算法（LRU）；3）最佳淘汰算法（OPT）；4）最少通路頁面算法（LFR）；其中3）和4）為選擇内容三、系統框圖一、運作結果 a、運作程式：終端先顯示： Start memory management. Producing address flow, wait for while, please. b、位址流、位址頁号流生成後，終端顯示： There are algorithms in the program 1、Optimization algorithm 2、Least recently used algorithm 3、First in first out algorithm 4、Least frequently used algorithm Select an algorithm number, please. 使用者輸入适當淘汰算法的号碼，并按回車，若是第一次選擇，輸出相應的位址頁号流。然後輸出該算法分别計算的使用者記憶體
作業系統之存儲管理——FIFO算法和LRU算法 從2k ~ 32k時的命中率，若輸入的号碼不再1~4中，則顯示： there is not the algorithm in the program,并重複b。 c、輸出結果後，終端顯示 “do you try again with anther algorithm(y/n)”。若鍵入y則重複b,否則結束。（一般講四種算法都用過後結束，以便比較）。 二、運作結果讨論 1、比較各種算法的命中率 2、分析當使用者記憶體容量增加是對命中率的影響
分析
上面就是實驗要求，因為時間關系，隻寫了fifo和lru兩種，但是這兩個會了，剩下的了解算法原理就很容易實作。
對于兩種算法的了解和實作為：
先進先出算法算法（Fifo）：
這個算法原理沒有算法，就是先進先出。對于這個結構最好采用的就算隊列了，對于java而言，我用的是list集合，每次添加資料的時候添加到第0位置，而如果移除的時候移除末尾的頁數。在這個過程中，每執行一條指令的時候，如果這個指令對應的位址（指令/10）在list中，那麼就命中，否則就是缺頁，需要移除尾，在0位置添加元素。
舉個例子，頁面記憶體為3，（隻能存三頁），要執行指令位址頁面對應為：4 2 3 4 1 2 1 5 6 3
那麼流程順序為：（4）缺頁—>(2,4)缺頁—>(3,2,4)缺頁—>4命中—>（1,3,2）缺頁4被置換—>2命中—>1命中—>（5,1,3）缺頁2被替換—>(6,5,1)缺頁2被替換—>（3,6,5）缺頁1被替換。
最近最少使用算法（LRU）：
這個算法跟fifo其實還是挺像的，但是有一點差別，最近最少使用。也就是說在一個正常序列的時候如果命中的化，就會把這個位址的頁号移動到首位（或者連結清單首位）。而如果缺頁的時候，要把這個連結清單的末尾位置移除，因為末尾的元素是最近用的最少的（很久前才有的）。對于資料結構，我依然選擇Arraylist。每次遇到指令位址的時候我隻需要特殊判斷下就可以了。我隻為了實驗的目的，沒有考慮性能，因為檢查是否存在位址的時候我用了list.contains（）方法，這是線性查詢複雜度O（n）,如果資料量大可以list map組合使用，将查詢降低到O(logn).還可以開一個boolean數組标記讓查詢複雜度降低到O（1），（但是這樣的化增大空間），還好資料量不大，影響不大。
如果
頁面記憶體為3，（隻能存三頁），要執行指令位址頁面對應為：4 2 3 4 1 2 1 5 6 3
那麼流程順序為（4)—>(2,4)—>(3,2,4)—>(4,3,2)命中—>(1,4,3)缺頁2被替換—>(2,1,4)缺頁—>(1,2,4)命中—>(5,1,2)缺頁—>(6,5,1)缺頁—>(3,6,5)缺頁
代碼
大緻流程就是這樣，有一點差別。
下面附上我的ac代碼。有的解釋會在注釋中：
package 實驗;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class storemanage {
static int mingzhong;
static int lenyeliu=320;
static int errortime;//失效次數
static int random[]=new int[330];//随機指令
static Scanner sc=new Scanner(System.in);
static void init()//初始随機數
{
int index=0;
while(index<320)
{
int m=(int) (Math.random()*320);
random[index++]=m;//順序指令
int m1=(int) (Math.random()*(m+1));
if(m1==320) {continue;}//跳出問本次
random[index++]=m1;//前位址部分 最大317
if(m1+1==320) {continue;}//跳出問本次
random[index++]=m1+1;//順序指令
int m2=(int) (Math.random()*(319-(m1+2))+m1+2);
if(m2==320) {continue;}//跳出問本次
random[index++]=m2;//後位址
if(index>320)
{
break;
}
}
}
private static void lur()
{
for(int memory=2;memory<=32;memory++)
{
mingzhong=0;errortime=0;
Queue<Integer>q1=new ArrayDeque<>();
int index=0;
while(index<320)
{
if(q1.size()<memory)
{
if(q1.contains(random[index]/10))
{
q1.remove(random[index]/10);
mingzhong++;
q1.add(random[index]/10);
}
else
{
q1.add(random[index]/10);
errortime++;
}
}
else
{
if(q1.contains(random[index]/10))
{
q1.remove(index);
mingzhong++;
}
else
{
q1.poll();//抛出
q1.add(random[index]/10);
errortime++;
}
}
index++;
}
double minz=1-(double)(errortime/(double)(320));//mingzhong/320一樣
String minzhon=String.format("%.4f", minz);
System.out.println("lur :memory:"+memory+" 缺失個數："+errortime+" 命中個數"+mingzhong+" 命中率："+minzhon);
}
System.out.println("書否繼續Y/N");
String team=sc.next();
if(team.equals("Y"))
{
System.out.println("請輸入編号");
int index=sc.nextInt();
if(index==1) {fifo();}
else
{
lur();
}
}
}
private static void fifo() {
// TODO 自動生成的方法存根
for(int memory=2;memory<=32;memory++)
{
mingzhong=0;errortime=0;
List<Integer>list=new ArrayList<>();
int index=0;
while(index<320)
{
if(list.size()<memory)//小于記憶體
{
if(list.contains(random[index]/10)) {mingzhong++;}
else
{
list.add(random[index]/10);
errortime++;
}
}
else//記憶體慢了
{
if(list.contains(random[index]/10)) {mingzhong++;}
else
{
list.remove(0);//移除第一個
list.add(random[index]/10);
errortime++;
}
}
index++;
// System.out.println(index);
}
double minz=1-(double)(errortime/(double)(320));//mingzhong/320一樣
String minzhon=String.format("%.4f", minz);
System.out.println("fifo :memory:"+memory+" 缺失個數："+errortime+" 命中個數"+mingzhong+" 命中率："+minzhon);
}
System.out.println("書否繼續Y/N");
String team=sc.next();
if(team.equals("Y"))
{
System.out.println("請輸入編号");
int index=sc.nextInt();
if(index==1) {fifo();}
else
{
lur();
}
}
}
public static void main(String[] args) {
init();
System.out.println("随機數為");
for(int i=0;i<320;i++)
{
System.out.print(String.format("%5d", random[i]));
if((i+1)%20==0)System.out.println();
}
System.out.println("輸入選擇算法的計算方式序号\n1:先進先出的算法（FIFO）；\n" +
"2:最近最少使用算法（LRU）；\n" +
"3:最佳淘汰算法（OPT）；\n" +
"4:最少通路頁面算法（LFR）；");
int index=sc.nextInt();
if(index==1) {
fifo();
}
else if(index==2)
{
lur();
}
}
} 執行結果
fifo
lur