先进先出淘汰算法

// C语言实现操作系统最佳淘汰算法
#include <stdio.h>
#include <stdlib.h>

#define length 20//定义数组长度
int bwoList[length];//淘汰序列
void initList(int arr[]) {//生成随机访问序列
    for (int i = 0; i < length; ++i) {
        int randNumber = rand() % 9 + 1;
        arr[i] = randNumber;
        if (i < length - 1)
            printf("%d ", arr[i]);
        else
            printf("%d\n", arr[i]);
    }
}


int BWO(int init[], int arr[]) {//最佳淘汰算法核心
    int countLoss = 0;//统计缺页次数
//    int arr1 = length, arr2 = length, arr3 = length;//初始化所在位置，若访问序列有 则迭代更新
    int count = 0;
    for (int i = 3; i < length; ++i) {
        int index = -1;//标记需要替换的待访问序列
        int flag = 0;//设定是否含有待访问标志
        for (int j = 0; j < 3; ++j) {
            if (arr[i] == init[j]) {
                flag = 1;
                count++;
                break;
            }
        }
        if (flag == 0) {//待访问序列不含有所需数字
            countLoss++;//缺页次数更新
            for (int j = i - 3 - count; j < length; ++j) {
                int temFlag = 0;
                for (int k = 0; k < 3; ++k) {
                    if (init[k] == arr[j]) {
                        index = k;
                        temFlag = 1;
                        break;
                    }
                }
                if (temFlag == 1)break;
            }
            init[index] = arr[i - 3 - count];//替换掉最先进来的
            bwoList[i - 3 - count] = arr[i - 3 - count]; //统计淘汰的页面

        }
    }
    return countLoss;
}


int main() {
    printf("\t欢迎来到先进先出淘汰算法\n");
    printf("随机生成的访问序列为：");
    int arr[length] = {7, -1, 1, 2, -1, 3, -1, 4, 2, 3, -1, 3, 2, 1, 2, -1, 1, 7, -1, 1};//存储随机访问序列
//    initList(arr);

    int init[3] = {7, -1, 1};//存储预先装入序列
    int countLoss;//计算缺页次数
//    for (int i = 0; i < 3; ++i) {
//        init[i] = arr[i];
//        arr[i] = 0;//表示该序列已访问
//    }
    countLoss = BWO(init, arr);
    printf("--淘汰序列为：");
    int size = sizeof(bwoList) / sizeof(int);
    for (int i = 0; i < size; ++i) {
        if (i < size - 1 && bwoList[i] != 0) {
            printf("%d ", bwoList[i]);
        }
    }
    printf("\n");
    printf("--缺页率为：%.2lf%%", (1.0 * countLoss / length) * 100);
}