▶▶▶完整代码在最后！！！
FIFO算法：先进先出调度算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
LRU算法：最近最少使用算法，根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。选择最近最久未使用的页面予以淘汰。
OPT算法：最佳淘汰算法，选择永不使用或在未来最长时间内不再被访问的页面予以替换。
CLOCK算法：根据页面内存是否被访问来决定是否置换该页面。
改进版CLOCK算法：在之前的CLOCK算法上面除了使用位，还增加了一个修改位，进行判断。
LFU算法：最近最少使用算法，如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰，也就是每次淘汰那些使用次数最少的数据。
系统最后的界面图：
系统设计流程图：
FIFO算法流程图：
LRU算法流程图：
OPT算法流程图：
CLOCK算法流程图：
改进版CLOCK算法流程图：
LFU算法流程图：
算法分析(举例)：
页面顺序为0 1 5 4 1 7 3 2 6 7
FIFO算法分析过程：
LRU算法分析过程：
OPT算法分析过程：
CLOCK算法分析过程：
改进版CLOCK算法分析过程：（修改位是随机产生的）
LFU算法分析过程：
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <memory.h>
#define MAX_SEQ_LEN 50 /*页面序列的最大长度*/
int blockNum; /*分配给进程的内存块数量*/
int pageNum; /*进程页面数,决定随机生成的页面序列中页面号的最大值*/
int pageSequenceLen; /*实际页面序列长度*/
int pageSequence[MAX_SEQ_LEN]; /*页面序列数组*/
int *memBlocks; /*为进程分配的内存块，动态数组，存放页号*/
int *isPageLoaded; /*页面状态数组，动态数组，1表示已经在内存块中,0表示不在内存块中*/
int *useSite; /*CLOCK算法的使用位，标记页号的状态*/
int *reviseSite; /*改进CLOCK算法的修改位*/
int oldPageIndex=0; /*被置换的页索引*/
int pageFaultTimes=0; /*缺页次数统计*/
float effectiveTime=0; /*有效访问时间 有效访问时间=(1-pageFaultTimes)*内存访问时间+pageFaultTimes*页错误处理时间 /本例中 内存访问时间=100ns ； 页错误处理时间=20ms */
char choice1; /*用来存储是否开始(y/n)*/
int choice2=-1;/*用来存储选择的排序到序号*/
void FIFO(){
printf("---------------------FIFO Replacement---------------------\n");
int i,j,k, n;
oldPageIndex = 0;
pageFaultTimes = 0;
effectiveTime=0;
memBlocks = (int *)malloc(blockNum * sizeof(int)); //初始化内存块中的页面号,全部初始化设置为-1
memset(memBlocks, -1, blockNum*sizeof(int)); //-1表示该内存块未装入任何页面
isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
memset(isPageLoaded, 0, pageNum*sizeof(int));
printf("页\t\t物理块\n");
for (i=0; i<pageSequenceLen; i++) {
printf("%2d\t-->\t", pageSequence[i]);
if (0 == isPageLoaded[pageSequence[i]]) {
pageFaultTimes++;
for (j=0; j<blockNum; j++) { //找空闲块
if (memBlocks[j]==-1) break;
}
if (j<blockNum) { //有空闲块
memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
}
else { //没有空闲块，页面置换
isPageLoaded[memBlocks[oldPageIndex]] = 0; //将被置换出去的页面状态修改为未装入
memBlocks[oldPageIndex] = pageSequence[i]; //将当前页号写入内存块
oldPageIndex = (oldPageIndex + 1) % blockNum; //将最先进入的索引修改为下一个索引
isPageLoaded[pageSequence[i]] = 1; //将当前页面状态修改为1
}
for (j=0; j<blockNum; j++) //显示内存块数组中的页号
if (memBlocks[j] != -1)
printf("%d ", memBlocks[j]);
printf("\n");
}
else printf("\n");
}
srand((unsigned)time(NULL));
effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
printf("缺页次数为：%d，缺页率为：%.3f，有效访问时间：%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
}
void LRU(){
printf("---------------------LRU Replacement---------------------\n");
int i,j,k, n,m,h;
oldPageIndex = 0;
pageFaultTimes = 0;
memBlocks = (int *)malloc(blockNum * sizeof(int)); //初始化内存块中的页面号,全部初始化设置为-1
memset(memBlocks, -1, blockNum*sizeof(int)); //-1表示该内存块未装入任何页面
isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
memset(isPageLoaded, 0, pageNum*sizeof(int));
printf("页\t\t物理块\n");
for (i=0; i<pageSequenceLen; i++) {
h=0;
printf("%2d\t-->\t", pageSequence[i]);
if (isPageLoaded[pageSequence[i]] == 0){
pageFaultTimes++;
for (j=0; j<blockNum; j++) { //找空闲块
if (memBlocks[j]==-1) break;
}
if (j<blockNum) { //有空闲块
memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
}
else {
int a[blockNum],p;
for(p=0;p<blockNum;p++)
a[p]=0;
for(k=i-1;k>=0;k--){
for(m=0;m<j;m++)
if(pageSequence[k]==memBlocks[m] && a[m]==0){
h=m;
a[m]=1;
}
}
isPageLoaded[memBlocks[h]] = 0;
memBlocks[h] = pageSequence[i];
isPageLoaded[pageSequence[i]] = 1;
}
for (j=0; j<blockNum; j++) //显示内存块数组中的页号
if (memBlocks[j] != -1)
printf("%d ", memBlocks[j]);
printf("\n");
}
else printf("\n");
}
srand((unsigned)time(NULL));
effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
printf("缺页次数为：%d，缺页率为：%.3f，有效访问时间：%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
}
void OPT(){
printf("---------------------OPT Replacement---------------------\n");
int i,j,k, n,m,h;
oldPageIndex = 0;
pageFaultTimes = 0;
effectiveTime=0;
memBlocks = (int *)malloc(blockNum * sizeof(int)); //初始化内存块中的页面号,全部初始化设置为-1
memset(memBlocks, -1, blockNum*sizeof(int)); //-1表示该内存块未装入任何页面
isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
memset(isPageLoaded, 0, pageNum*sizeof(int));
printf("页\t\t物理块\n");
for (i=0; i<pageSequenceLen; i++) {
h=0;
int count=0;
printf("%2d\t-->\t", pageSequence[i]);
if (isPageLoaded[pageSequence[i]] == 0){
pageFaultTimes++;
for (j=0; j<blockNum; j++) { //找空闲块
if (memBlocks[j]==-1) break;
}
if (j<blockNum) { //有空闲块
memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
}
else {
int a[blockNum],p;
for(p=0;p<blockNum;p++)
a[p]=0;
for(k=i+1;k<pageSequenceLen;k++){
for(m=0;m<j;m++)
if(pageSequence[k]==memBlocks[m] && a[m]==0){
h=m;
a[m]=1;
count++;
}
}
if(count<blockNum)
for(p=0;p<blockNum;p++){
if(a[p]==0){
h=p;
break;
}
}
isPageLoaded[memBlocks[h]] = 0;
memBlocks[h] = pageSequence[i];
isPageLoaded[pageSequence[i]] = 1;
}
for (j=0; j<blockNum; j++) //显示内存块数组中的页号
if (memBlocks[j] != -1)
printf("%d ", memBlocks[j]);
printf("\n");
}
else printf("\n");
}
srand((unsigned)time(NULL));
effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
printf("缺页次数为：%d，缺页率为：%.3f，有效访问时间：%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
}
void CLOCK(){
printf("---------------------CLOCK Replacement---------------------\n");
int i,j,k, n,m,h;
oldPageIndex = 0;
pageFaultTimes = 0;
memBlocks = (int *)malloc(blockNum * sizeof(int)); //初始化内存块中的页面号,全部初始化设置为-1
memset(memBlocks, -1, blockNum*sizeof(int)); //-1表示该内存块未装入任何页面
isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
memset(isPageLoaded, 0, pageNum*sizeof(int));
useSite = (int *)malloc(blockNum * sizeof(int));//初始化页面使用位数组,初始化未装入
memset(useSite, 0, blockNum*sizeof(int));
int *pageSite;//标记页号在内存块中的位置
pageSite = (int *)malloc(pageNum * sizeof(int));//初始化页面使用位数组,初始化未装入
memset(pageSite, 0, pageNum*sizeof(int));
printf("页\t\t物理块\n");
for (i=0; i<pageSequenceLen; i++) {
printf("%2d\t-->\t", pageSequence[i]);
if (isPageLoaded[pageSequence[i]] == 0){
pageFaultTimes++;
for (j=0; j<blockNum; j++) { //找空闲块
if (memBlocks[j]==-1) break;
}
if (j<blockNum) { //有空闲块
memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
useSite[j] = 1;
pageSite[pageSequence[i]] = j;
}
else {
int flag=0;
while(flag==0){
if(useSite[oldPageIndex] == 0){
isPageLoaded[memBlocks[oldPageIndex]] = 0; //将被置换出去的页面状态修改为未装入
memBlocks[oldPageIndex] = pageSequence[i]; //将当前页号写入内存块
pageSite[pageSequence[i]] = oldPageIndex;
useSite[oldPageIndex] = 1;
oldPageIndex = (oldPageIndex + 1) % blockNum; //将最先进入的索引修改为下一个索引
isPageLoaded[pageSequence[i]] = 1; //将当前页面状态修改为1
flag=1;
}
else{
useSite[oldPageIndex] = 0;
oldPageIndex = (oldPageIndex + 1) % blockNum;
}
}
}
for (j=0; j<blockNum; j++) //显示内存块数组中的页号
if (memBlocks[j] != -1)
printf("%d ", memBlocks[j]);
printf("\n");
}
else{
useSite[pageSite[pageSequence[i]]] = 1;
printf("\n");
}
}
srand((unsigned)time(NULL));
effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
printf("缺页次数为：%d，缺页率为：%.3f，有效访问时间：%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
}
void improvedCLOCK(){
printf("---------------------改进版CLOCK Replacement---------------------\n");
int i,j,k, n,m,h;
oldPageIndex = 0;
pageFaultTimes = 0;
memBlocks = (int *)malloc(blockNum * sizeof(int)); //初始化内存块中的页面号,全部初始化设置为-1
memset(memBlocks, -1, blockNum*sizeof(int)); //-1表示该内存块未装入任何页面
isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
memset(isPageLoaded, 0, pageNum*sizeof(int));
useSite = (int *)malloc(blockNum * sizeof(int));//初始化页面使用位数组,初始化未装入
memset(useSite, 0, blockNum*sizeof(int));
reviseSite = (int *)malloc(pageSequenceLen * sizeof(int));//初始化页面使用位数组,初始化未装入
memset(reviseSite, 0, pageSequenceLen*sizeof(int));
int *reviseSites;//内存块中的修改位
reviseSites = (int *)malloc(blockNum * sizeof(int));//
memset(reviseSites, 0, blockNum*sizeof(int));
int *pageSite;//标记页号在内存块中的位置
pageSite = (int *)malloc(pageNum * sizeof(int));
memset(pageSite, 0, pageNum*sizeof(int));
for (i=0; i<pageSequenceLen; i++) {
printf("%d ", pageSequence[i]);
}
printf("\n");
n=2;
for (i=0; i<pageSequenceLen; i++) {
reviseSite[i] = rand()%n;
printf("%d ", reviseSite[i]);
}
printf("\n");
printf("页\t\t物理块\n");
for (i=0; i<pageSequenceLen; i++) {
printf("%2d\t-->\t", pageSequence[i]);
if (isPageLoaded[pageSequence[i]] == 0){
pageFaultTimes++;
for (j=0; j<blockNum; j++) { //找空闲块
if (memBlocks[j]==-1) break;
}
if (j<blockNum) { //有空闲块
memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
useSite[j] = 1;
reviseSites[j] = reviseSite[i];
pageSite[pageSequence[i]] = j;
}
else {
int flag=0;
while(flag==0){
int count=0;
while((useSite[oldPageIndex]!=0 || reviseSites[oldPageIndex]!=0) && count<blockNum){
count++;
oldPageIndex = (oldPageIndex + 1) % blockNum;
}
if(count<blockNum){
isPageLoaded[memBlocks[oldPageIndex]] = 0;
memBlocks[oldPageIndex] = pageSequence[i];
reviseSites[oldPageIndex] = reviseSite[i];
useSite[oldPageIndex] = 1;
pageSite[pageSequence[i]] = oldPageIndex;
oldPageIndex = (oldPageIndex + 1) % blockNum;
isPageLoaded[pageSequence[i]] = 1;
flag=1;
}
else{
int count1=0;
while((useSite[oldPageIndex]!=0 || reviseSites[oldPageIndex]!=1) && count1<blockNum){
count1++;
useSite[oldPageIndex] = 0;
oldPageIndex = (oldPageIndex + 1) % blockNum;
}
if(count1<blockNum){
isPageLoaded[memBlocks[oldPageIndex]] = 0;
memBlocks[oldPageIndex] = pageSequence[i];
reviseSites[oldPageIndex] = reviseSite[i];
useSite[oldPageIndex] = 1;
pageSite[pageSequence[i]] = oldPageIndex;
oldPageIndex = (oldPageIndex + 1) % blockNum;
isPageLoaded[pageSequence[i]] = 1;
flag=1;
}
}
}
}
for (j=0; j<blockNum; j++) //显示内存块数组中的页号
if (memBlocks[j] != -1)
printf("%d ", memBlocks[j]);
printf("\n");
}
else{
useSite[pageSite[pageSequence[i]]] = 1;
reviseSites[pageSite[pageSequence[i]]] = reviseSite[i];
printf("\n");
}
}
srand((unsigned)time(NULL));
effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
printf("缺页次数为：%d，缺页率为：%.3f，有效访问时间：%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
}
void LFU(){
printf("---------------------LFU Replacement---------------------\n");
int i,j,k, n;
oldPageIndex = 0;
pageFaultTimes = 0;
effectiveTime=0;
memBlocks = (int *)malloc(blockNum * sizeof(int)); //初始化内存块中的页面号,全部初始化设置为-1
memset(memBlocks, -1, blockNum*sizeof(int)); //-1表示该内存块未装入任何页面
isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
memset(isPageLoaded, 0, pageNum*sizeof(int));
int *pagenumber;//各个页面出现的次数统计
pagenumber = (int *)malloc(pageNum * sizeof(int));
memset(pagenumber, 0, pageNum*sizeof(int));
int *blocktime;//标记各个页面出现的先后顺序
blocktime = (int *)malloc(blockNum * sizeof(int));
memset(blocktime, 0, blockNum*sizeof(int));
printf("页\t\t物理块\n");
for (i=0; i<pageSequenceLen; i++) {
printf("%2d\t-->\t", pageSequence[i]);
if (isPageLoaded[pageSequence[i]] == 0) {
pageFaultTimes++;
for (j=0; j<blockNum; j++) { //找空闲块
if (memBlocks[j]==-1) break;
}
if (j<blockNum) { //有空闲块
memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
pagenumber[pageSequence[i]]++;
blocktime[j] = j;
}
else { //没有空闲块，页面置换
oldPageIndex = 0;
for(j=1;j<blockNum;j++){
if(pagenumber[memBlocks[oldPageIndex]]>pagenumber[memBlocks[j]])
oldPageIndex=j;
else if(pagenumber[memBlocks[oldPageIndex]] == pagenumber[memBlocks[j]] && blocktime[oldPageIndex]<blocktime[j])
oldPageIndex = j;
}
isPageLoaded[memBlocks[oldPageIndex]] = 0; //将被置换出去的页面状态修改为未装入
memBlocks[oldPageIndex] = pageSequence[i]; //将当前页号写入内存块
isPageLoaded[pageSequence[i]] = 1; //将当前页面状态修改为1
pagenumber[pageSequence[i]]++;
for(j=0;j<blockNum;j++){
if(blocktime[j]>blocktime[oldPageIndex])
blocktime[j]--;
}
blocktime[oldPageIndex] = blockNum-1;
}
for (j=0; j<blockNum; j++) //显示内存块数组中的页号
if (memBlocks[j] != -1)
printf("%d ", memBlocks[j]);
printf("\n");
}
else{
pagenumber[pageSequence[i]]++;
printf("\n");
}
}
srand((unsigned)time(NULL));
effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
printf("缺页次数为：%d，缺页率为：%.3f，有效访问时间：%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
}
int main(int argc,char **argv)
{
printf("本例中 内存访问时间=100ns 页错误处理时间=20ms\n");
int i,n;
printf("Begin? (Y or N): ");
choice1 = getchar();
while (choice1=='Y' || choice1=='y') {
printf("输入分配给该进程的内存块数：");
scanf("%d", &blockNum);
printf("输入该进程的页面总数：");
scanf("%d", &pageNum);
printf("输入该进程访问的页面序列长度：");
scanf("%d", &pageSequenceLen);
getchar();
//srand((int)time(0));
// pageSequence[0]=0;pageSequence[1]=1;pageSequence[2]=5;pageSequence[3]=4;pageSequence[4]=1;
// pageSequence[5]=7;pageSequence[6]=3;pageSequence[7]=2;pageSequence[8]=6;pageSequence[9]=7;
for (i=0; i<pageSequenceLen; i++) { //随机生成页面序列
n=rand()%pageNum;
pageSequence[i] = n;
printf("%d ", pageSequence[i]);
}
printf("\n请选择需要使用到算法：\n");
printf("1.FIFO\n2.LRU\n3.OPT\n4.CLOCK\n5.改进版CLOCK\n6.LFU\n0.exit\n");
printf("选择算法序号：");
scanf("%d",&choice2);
while(choice2){
switch(choice2){
case 1: FIFO(); break;
case 2: LRU(); break;
case 3: OPT(); break;
case 4: CLOCK(); break;
case 5: improvedCLOCK(); break;
case 6: LFU(); break;
defalut: break;
}
printf("请选择需要使用到算法：\n");
printf("1.FIFO\n2.LRU\n3.OPT\n4.CLOCK\n5.改进版CLOCK\n6.LFU\n0.exit\n");
printf("选择算法序号：");
scanf("%d",&choice2);
}
printf("Begin? (Y or N): ");
getchar();
choice1 = getchar();
}
}