網站首頁 編程語言 正文
操作系統實驗
頁面置換算法（FIFO、LRU、OPT）
概念：
1.最佳置換算法（OPT）（理想置換算法）：從主存中移出永遠不再需要的頁面；如無這樣的頁面存在，則選擇最長時間不需要訪問的頁面。于所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時間內不再被訪問的頁面，這樣可以保證獲得最低的缺頁率。
2.先進先出置換算法（FIFO）：是最簡單的頁面置換算法。這種算法的基本思想是：當需要淘汰一個頁面時，總是選擇駐留主存時間最長的頁面進行淘汰，即先進入主存的頁面先淘汰。其理由是：最早調入主存的頁面不再被使用的可能性最大。
3．最近最久未使用（LRU）算法：這種算法的基本思想是：利用局部性原理，根據一個作業在執行過程中過去的頁面訪問歷史來推測未來的行為。它認為過去一段時間里不曾被訪問過的頁面，在最近的將來可能也不會再被訪問。所以，這種算法的實質是：當需要淘汰一個頁面時，總是選擇在最近一段時間內最久不用的頁面予以淘汰。
題目：
編寫一個程序，實現本章所述的FIFO、LRU和最優頁面置換算法。首先，生成一個隨機的頁面引用串，其中頁碼范圍為0-9.將這個隨機頁面引用串應用到每個算法，并記錄每個算法引起的缺頁錯誤的數量。實現置換算法，一遍頁面幀的數量可以從1~7。
代碼
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int numbers[20]={7,0,1,2,
0,3,0,4,
2,3,0,3,
2,1,2,0,
1,7,0,1};//本地數據，與課本一致，方便測試
int nums=0;//輸入棧的個數，為了方便使用，
int stack[20][7]={10};
void begin();
void randomnum();//用于產生隨機數
void init();//初始化
void FIFO();//FIFO算法
void LRU();//LRU算法
void OPT();//最優頁面置換算法（OPT）
void print();//輸出
int main() {
begin();
FIFO();
LRU();
OPT();
return 0;
}
void begin()//開始菜單界面
{
int i,j,k;
printf("請輸入頁面幀的數量(1-7)：");
scanf("%d",&nums);
for(k=0;;k++)
{
printf("是否使用隨機數產生輸入串（0：是，1：否）");
scanf("%d",&j);
if(j==0)
{
randomnum();
break;
}
else if(j==1)
{
break;
}
else
{
printf("請輸入正確的選擇！\n");
}
}
printf("頁面引用串為：\n");
for(i=0;i<20;i++)
{
printf("%d ",numbers[i]);
}
printf("\n");
init();
}
void randomnum()//如果需要使用隨機數生成輸入串，調用該函數
{
srand(time(0));//設置時間種子
for(int i = 0; i < 20; i++) {
numbers[i] = rand() % 10;//生成區間0`9的隨機頁面引用串
}
}
void init()//用于每次初始化頁面棧中內容，同時方便下面輸出的處理
{
int i,j;
for(i=0;i<20;i++)
for(j=0;j<nums;j++)
stack[i][j]=10;
}
void print()//輸出各個算法的棧的內容
{
int i,j;
for(i=0;i<nums;i++)
{
for(j=0;j<20;j++)
{
if(stack[j][i]==10)
printf("* ");
else
printf("%d ",stack[j][i]);
}
printf("\n");
}
}
void FIFO()//FIFO算法
{
init();
int i,j=1,n=20,k,f,m;
stack[0][0]=numbers[0];
for(i=1;i<20;i++)
{
f=0;
for(m=0;m<nums;m++)
{
stack[i][m]=stack[i-1][m];
}
for(k=0;k<nums;k++)
{
if(stack[i][k]==numbers[i])
{
n--;
f=1;
break;
}
}
if(f==0)
{
stack[i][j]=numbers[i];
j++;
}
if(j==nums)
j=0;
}
printf("\n");
printf("FIFO算法：\n");
print();
printf("缺頁錯誤數目為：%d\n",n);
}
void LRU()//LRU算法
{
int i,j,m,k,sum=1,f;
int sequence[7]={0};//記錄序列
init();
stack[0][0]=numbers[0];
sequence[0]=nums;
for(i=1;i<nums;i++)//前半部分，頁面空置的情況
{
for(j=0;j<nums;j++)
{
stack[i][j]=stack[i-1][j];
}
for(j=0;j<nums;j++) //判斷要插入的是否在棧中已經存在
{
f=0;
if(stack[i][j]==numbers[i])
{
f=1;
sum--;
sequence[j]=nums;
break;
}
}
for(j=0;j<nums;j++)
{
if(sequence[j]==0&&f==0)
{
stack[i][j]=numbers[i];
sequence[i]=nums;//最近使用的優先級列為最高
break;
}
}
for(j=0;j<i;j++)//將之前的優先級序列都減1
{
if(sequence[j]!=0)
sequence[j]--;
}
//sequence[i]=nums;
sum++;
}
for(i=nums;i<20;i++)//頁面不空，需要替換的情況
{
int f;
f=0;
for(j=0;j<nums;j++)
{
stack[i][j]=stack[i-1][j];
}
for(j=0;j<nums;j++)//判斷輸入串中的數字，是否已經在棧中
{
if(stack[i][j]==numbers[i])
{
f=1;
k=j;
break;
}
}
if(f==0)//如果頁面棧中沒有，不相同
{
for(j=0;j<nums;j++)//找優先序列中為0的
{
if(sequence[j]==0)
{
m=j;
break;
}
}
for(j=0;j<nums;j++)
{
sequence[j]--;
}
sequence[m]=nums-1;
stack[i][m]=numbers[i];
sum++;
}
else//如果頁面棧中有，替換優先級
{
if(sequence[k]==0)//優先級為最小優先序列的
{
for(j=0;j<nums;j++)
{
sequence[j]--;
}
sequence[k]=nums-1;
}
else if(sequence[k]==nums-1)//優先級為最大優先序列的
{
//無需操作
}
else//優先級為中間優先序列的
{
for(j=0;j<nums;j++)
{
if(sequence[k]<sequence[j])
{
sequence[j]--;
}
}
sequence[k]=nums-1;
}
}
}
printf("\n");
printf("LRU算法：\n");
print();
printf("缺頁錯誤數目為：%d\n",sum);
}
void OPT()//OPT算法
{
int i,j,k,sum=1,f,q,max;
int seq[7]={0};//記錄序列
init();
stack[0][0]=numbers[0];
seq[0]=nums-1;
for(i=1;i<nums;i++)//前半部分，頁面空置的情況
{
for(j=0;j<nums;j++)
{
stack[i][j]=stack[i-1][j];
}
for(j=0;j<nums;j++) //判斷要插入的是否在棧中已經存在
{
f=0;
if(stack[i][j]==numbers[i])
{
f=1;
sum--;
//b++;
seq[j]=nums;
break;
}
}
for(j=0;j<nums;j++)
{
if(seq[j]==0&&f==0)
{
stack[i][j]=numbers[i];
seq[j]=nums;//最近使用的優先級列為最高
break;
}
// else if(seq[j]==0&&f==1){
// b++;
// sum--;
// seq[j]=nums-1;
// break;
// }
}
for(j=0;j<nums;j++)//將之前的優先級序列都減1
{
if(seq[j]!=0)
seq[j]--;
}
sum++;
}
for(i=nums;i<20;i++)//后半部分，頁面棧中沒有空的時候情況
{
//k=nums-1;//最近的數字的優先級
for(j=0;j<nums;j++)//前面的頁面中內容賦值到新的新的頁面中
{
stack[i][j]=stack[i-1][j];
}
for(j=0;j<nums;j++)
{
f=0;
if(stack[i][j]==numbers[i])
{
f=1;
break;
}
}
if(f==0)//頁面中沒有，需要替換的情況
{
for(q=0;q<nums;q++)//優先級序列中最大的就是最久不會用的，有可能出現后面沒有在用過的情況
{
seq[q]=20;
}
for(j=0;j<nums;j++)//尋找新的優先級
{
for(q=i+1;q<20;q++)
{
if(stack[i][j]==numbers[q])
{
seq[j]=q-i;
break;
}
}
}
max=seq[0];
k=0;
for(q=0;q<nums;q++)
{
if(seq[q]>max)
{
max=seq[q];
k=q;
}
}
stack[i][k]=numbers[i];
sum++;
}
else
{
//頁面棧中有需要插入的數字，無需變化，替換的優先級也不需要變化
}
}
printf("\n");
printf("OPT算法：\n");
print();
printf("缺頁錯誤數目為：%d\n",sum);
}
運行結果截圖：
總結
原文鏈接：https://blog.csdn.net/braylon_zhang/article/details/111157443
相關推薦
- 2023-03-18 詳解Flutter中key的正確使用方式_Android
- 2023-03-18 C#?DataTable.Select()根據條件篩選數據問題_C#教程
- 2022-04-26 Python?Pandas學習之數據離散化與合并詳解_python
- 2023-02-01 特定用例下的Combine全面使用詳解_Swift
- 2022-05-15 Qt Linux獲取bios ID作為唯一標識
- 2022-10-09 玩轉Go命令行工具Cobra_Golang
- 2022-06-30 Redis三種常用的緩存讀寫策略步驟詳解_Redis
- 2023-07-09 Go語言new與make區別
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速