最优页面置换算法c语言代码

以下是最优页面置换算法（Optimal Page Replacement Algorithm）的 C 语言代码实现：

#include<stdio.h>
#include<stdlib.h>

int main(){
    int frames, pages, page_faults = 0, flag, reppage, i, j, k, max, count;
    printf("Enter number of frames: ");
    scanf("%d",&frames);
    printf("Enter number of pages: ");
    scanf("%d",&pages);
    int reference[pages], memlayout[frames];

    for(i = 0; i < frames; i++)
        memlayout[i] = -1;

    printf("Enter reference string: ");
    for(i = 0; i < pages; i++)
        scanf("%d",&reference[i]);

    for(i = 0; i < pages; i++){
        flag = 0;
        for(j = 0; j < frames; j++){
            if(memlayout[j] == reference[i]){
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            count = 0;
            for(j = 0; j < frames; j++){
                reppage = 0;
                for(k = i + 1; k < pages; k++){
                    if(memlayout[j] == reference[k])
                        break;
                    else
                        reppage++;
                }
                if(reppage > count){
                    count = reppage;
                    max = j;
                }
            }
            memlayout[max] = reference[i];
            page_faults++;
        }
        printf("\n");
        for(j = 0; j < frames; j++){
            printf("%d\t", memlayout[j]);
        }
    }
    printf("\nTotal number of page faults: %d\n", page_faults);
    return 0;
}

代码中，我们先输入页面帧数和页面数量，以及页面引用串（reference string）。然后，我们初始化一个长度为帧数的数组 memlayout，其中所有元素的值都是 -1，表示这些帧当前没有被占用。接下来，我们开始遍历页面引用串，检查每个页面是否已经在 memlayout 中出现过。如果已经出现过，我们就不需要进行任何操作。否则，我们需要将页面放入一个未被占用的帧中。

在找到未被占用的帧之后，我们需要检查当前页面之后还有多长时间才会再次被引用。我们遍历 memlayout 中的所有帧，找到其中距离当前页面最远的一个帧，将该帧替换成当前页面。这样做可以最大限度地减少页面置换的次数。最后，我们输出当前的 memlayout，并且更新 page_faults 的值。

该算法的时间复杂度为 O(n^2)，其中 n 是页面数量。因此，它通常只适用于页面数量比较小的情况。