java实现操作系统中的最佳置换Optimal算法

java实现操作系统中的最佳置换Optimal算法

在学习操作系统这本书的时候，我们使用的是汤小丹老师的《计算机操作系统》接下来我将会使用java语言去实现内部代码。

Swap指令

最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法通常保证获取最低的缺页率。但人们目前还无法与之，一个线程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，因此该算法是无法实现的，但是可以利用该算法去评价其他算法。现在就说明如下。

假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：

7, 0, 1xYvIW, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

进程运行时，先将7，0，1三个页面装在内存，以后需要访问页面2时，将产生缺页中断。此时OS将根据最佳算法置换算法将选择页面7予以淘汰。这是因为页面0将作为第五个被访问的页面，页面1为第十四个被访问的页面，而页面7则是要在低18次访问才需要引入，以此类推。

以下是源代码实现部分：

package chapter02;

public class P175Optimal {

//查找数组中是否存在并且未存储元素的索引

public static int existEmpty(int[] place){

for (int i = 0; i < place.length; i++) {

if(place[i]==-1)

return i;

}

//不为空

return -1;

}

//查找元素是否在数组中存在

public static boohttp://lean paramExist(int[] place,int param){

for (int i = 0; i < place.length; i++) {

if(place[i]==param)

return true;

}

//不为空

return false;

}

//获取最大距离值

public static int getMaxIndexOfNeed(int[] place,int[] block,int start){

//最近需求定位

int minBlockIndex = -1;

int minPlaceIndex = -1;

for(int PlaceIndex = 0;PlaceIndex

for (int BlockIndex = start + 1; BlockIndex < block.length; BlockIndex++) {

if (block[BlockIndex] == place[PlaceIndex]) {

if (minBlockIndex < BlockIndex) {

minBlockIndex = BlockIndex;

minPlaceIndex = PlaceIndex;

}

break;

}

//这操作是查找获取最大距离值的时，发现内存中的元素以后永久不使用的元素时候

if(BlockIndex==block.length-1 && block[BlockIndex]!=place[PlaceIndex]){

return PlaceIndex;

}

}

}

return minPlaceIndex;

}

public static void main(String[] args) {

int[] block = new int[]{7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, http://1, 7, 0, 1};

int[] place = new int[]{-1, -1, -1};

for (int index = 0; index < block.length; index++) {

//假设元素存在则不需要进行任何操作

if(paramExist(place,block[index])){

continue;

}else {

int emptyIndex = existEmpty(place);

//当前已经元素满了

if(emptyIndex==-1){

int maxIndex = getMaxIndexOfNeed(place,block,index);

place[maxIndex] = block[index];

for (int param http://: place) {

System.out.print(param + " ");

}

System.out.println();

}else{

place[emptyIndex] = block[index];

}

}

}

}

}

实验结果：

"C:\Program Files\Java\jdk1.8.0_101\bin\java.exe"

2 0 1

2 0 3

2 4 3

2 0 3

2 0 1

7 0 1

实验结果与上结果一致。

for (int BlockIndex = start + 1; BlockIndex < block.length; BlockIndex++) {

if (block[BlockIndex] == place[PlaceIndex]) {

if (minBlockIndex < BlockIndex) {

minBlockIndex = BlockIndex;

minPlaceIndex = PlaceIndex;

}

break;

}

//这操作是查找获取最大距离值的时，发现内存中的元素以后永久不使用的元素时候

if(BlockIndex==block.length-1 && block[BlockIndex]!=place[PlaceIndex]){

return PlaceIndex;

}

}

}

return minPlaceIndex;

}

public static void main(String[] args) {

int[] block = new int[]{7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, http://1, 7, 0, 1};

int[] place = new int[]{-1, -1, -1};

for (int index = 0; index < block.length; index++) {

//假设元素存在则不需要进行任何操作

if(paramExist(place,block[index])){

continue;

}else {

int emptyIndex = existEmpty(place);

//当前已经元素满了

if(emptyIndex==-1){

int maxIndex = getMaxIndexOfNeed(place,block,index);

place[maxIndex] = block[index];

for (int param http://: place) {

System.out.print(param + " ");

}

System.out.println();

}else{

place[emptyIndex] = block[index];

}

}

}

}

}

实验结果：

"C:\Program Files\Java\jdk1.8.0_101\bin\java.exe"

2 0 1

2 0 3

2 4 3

2 0 3

2 0 1

7 0 1

实验结果与上结果一致。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。