先入先出(FIFO)置換アルゴリズム
2840 ワード
定義
これは最初に出現した置換アルゴリズムである.このアルゴリズムは常に最初にメモリに入るページを淘汰し、つまりメモリの中で最も長いページを選択して淘汰します.このアルゴリズムは簡単に実現され、一つのプロセスをメモリのページに転送し、前後の順序で一つの列にリンクし、一つのポインタをセットして、代替ポインタと呼び、常に古いページを指すようにします.しかし、このアルゴリズムは実際に実行されるプロセスの規則に適合していません.プロセスにおいては、グローバル変数、常用関数、ルーチンなどを含むページが頻繁にアクセスされるため、FIFOアルゴリズムはこれらのページが淘汰されないことを保証できません.
ここでは、先進的な列を作って、先に列を出ればいいです.最初にメモリに入るページは最初に変換されます.
例えば、システムがあるプロセスに3つの物理ブロックを割り当てたと仮定し、次のページ番号参照列が考えられる.
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
結果:
7 7 0 7 0 1 0 1 2 1 2 0 2 0 3 2 3 0 3 0 4 0 4 2 4 2 3 2 3 0 2 0 3 0 3 2 3 2 1 3 1 2 1 2 0 2 0 1 0 1 7 1 7 0 7 0 1
先入先出(FIFO)置換アルゴリズムシミュレーションソースコード
これは最初に出現した置換アルゴリズムである.このアルゴリズムは常に最初にメモリに入るページを淘汰し、つまりメモリの中で最も長いページを選択して淘汰します.このアルゴリズムは簡単に実現され、一つのプロセスをメモリのページに転送し、前後の順序で一つの列にリンクし、一つのポインタをセットして、代替ポインタと呼び、常に古いページを指すようにします.しかし、このアルゴリズムは実際に実行されるプロセスの規則に適合していません.プロセスにおいては、グローバル変数、常用関数、ルーチンなどを含むページが頻繁にアクセスされるため、FIFOアルゴリズムはこれらのページが淘汰されないことを保証できません.
ここでは、先進的な列を作って、先に列を出ればいいです.最初にメモリに入るページは最初に変換されます.
例えば、システムがあるプロセスに3つの物理ブロックを割り当てたと仮定し、次のページ番号参照列が考えられる.
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
結果:
7 7 0 7 0 1 0 1 2 1 2 0 2 0 3 2 3 0 3 0 4 0 4 2 4 2 3 2 3 0 2 0 3 0 3 2 3 2 1 3 1 2 1 2 0 2 0 1 0 1 7 1 7 0 7 0 1
先入先出(FIFO)置換アルゴリズムシミュレーションソースコード
/**
*
* @author Administrator
*
*/
public class FIFO {
/**
*
*/
public static final int N = 3;
/**
*
*/
Object[] array = new Object[N];
private int size;
/**
*
* @return
*/
public boolean isEmpty() {
if(0 == size)
return true;
else
return false;
}
public/**
*
* @return
*/ boolean isFulled() {
if(size >= N)
return true;
else
return false;
}
/**
* ( )
* @return
*/
public int size() {
return size;
}
/**
* o
* @param o
* @return
*/
public int indexOfElement(Object o) {
for(int i=0; i<N; i++) {
if(o == array[i]) {
return i;
}
}
return -1;
}
/*public void push(Object o) {
Node p = new Node(o);
//Node p2 = head;
p.next = head;
head = p;
}*/
/**
*
* @param obj
*/
public Object trans(Object obj){
Object e = null;
int t = 0;
if(indexOfElement(obj) != -1) {
t = indexOfElement(obj);
for(int i=t; i<size-1; i++) {
array[i] = array[i+1];
}
array[size-1] = obj;
} else {
if(!isFulled()){
array[size] = obj;
size ++;
} else {
for(int i=0; i<size-1; i++) {
array[i] = array[i+1];
}
array[size-1] = obj;
}
}
if( -1 == t) {
return null;
} else {
return array[t];
}
}
/**
*
*/
public void showMemoryBlock() {
for(int i=0; i<size; i++) {
System.out.print(array[i] + " ");
}
}
/**
* ( )
*/
public void clear(){
}
/**
* @param args
*/
public static void main(String[] args) {
Integer iter[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
FIFO fifo = new FIFO();
for(int i=0; i<iter.length; i++) {
fifo.trans(iter[i]);
fifo.showMemoryBlock();
System.out.println();
}
}
}