C 程序中的 FIFO 算法

Question

这段代码有什么错误？程序运行但输出结果似乎不正确。

#include <stdio.h>

int main() {
    int frameno, pageno, pHits = 0, pFaults = 0;

    printf("\nEnter Page Frame: ");
    scanf("%d", &frameno);

    printf("\nEnter Pages: ");
    scanf("%d", &pageno);

    printf("Enter string: ");

    int p, n, i;
    char temp[frameno], pageref[pageno];

    for (p = 0; p < pageno; p++) {
        scanf(" %c", &pageref[p]);
    }

    printf("\nPage Requested \t ");
    for (n = 0; n < frameno; n++) {
        printf("Page Frame %d \t", n + 1);
        temp[n] = '-'; // Initialize with a character that doesn't conflict with pages
    }

    for (p = 0; p < pageno; p++) {
        int pageFound = 0;

        for (i = 0; i < frameno; i++) {
            if (pageref[p] == temp[i]) {
                pHits++;
                pageFound = 1;
                break;
            }
        }

        pFaults++;
        if (!pageFound) {
            if (pFaults <= frameno && pHits == 0) {
                temp[p] = pageref[p];
            } else {
                temp[(pFaults - 1) % frameno] = pageref[p];
            }
        }

        printf("\n%c\t", pageref[p]);
        for (i = 0; i < frameno; i++) {
            if (temp[i] != '-') {
                printf("\t\t %c", temp[i]);
            } else {
                printf(" \t\t");
            }
        }
    }

    printf("\nPage Faults: %d\t", pFaults);
    printf("\nPage Hits: %d\t", pHits);

    return 0;
}

输出结果是这样的，页框1中应该有5个。

Enter Page Frame: 3

Enter Pages: 5
Enter string: 41245

FIFO
Page Requested   Page Frame 1   Page Frame 2    Page Frame 3
4                        4
1                        4               1
2                        4               1               2
4                        4               1               2
5                        4               1               2
Page Faults: 5
Page Hits: 1

Answer 1

我假设您想要驱逐最旧的页面，不一定是帧[0]中的页面，尽管帧[0]将是第一个被弹出的帧。如果你只从frame[0]中驱逐，那么frames[1]和frames[2]在加载了一些东西之后就永远不会改变。

我们将引入一个额外的数组：

int insertTimes[frameno] = {0};

代表每个页面插入到

temp

数组中的“时间”。然后我们将引入一个时钟，它只是一个整数，每次出现页面错误时都会加 1。

此外，当我们这样做时，我们将修复代码中的错误，该错误也会将 pPageFaults 加 1，无论是否存在。

供您考虑：

int main() {
    int frameno, pageno, pHits = 0, pFaults = 0;

    printf("\nEnter Page Frame: ");
    scanf("%d", &frameno);

    printf("\nEnter Pages: ");
    scanf("%d", &pageno);

    printf("Enter string: ");

    int p, n, i;
    char temp[frameno] = {0};     // ={0} to initially zero the array out
    char pageref[pageno+1] = {0}; // +1 so it's easy to debug
    inti insertionTimes[frameno];  // insertionTimes[i] has the insertion time of the page inside temp[i]

    int inserttime = 1; // our clock

    for (p = 0; p < pageno; p++) {
        scanf(" %c", &pageref[p]);
    }

    printf("\nPage Requested \t ");
    for (n = 0; n < frameno; n++) {
        printf("Page Frame %d \t", n + 1);
        temp[n] = '-'; // Initialize with a character that doesn't conflict with pages
    }

    for (p = 0; p < pageno; p++) {
        int pageFound = 0;

        for (i = 0; i < frameno; i++) {
            if (pageref[p] == temp[i]) {
                pHits++;
                pageFound = 1;
                break;
            }
        }

        if (!pageFound) {
            pFaults++;
            // find the frame with the earliest insert time and replace it with the page requested
            int best = 0;
            for (int i = 0; i < frameno; i++) {
                if (insertionTimes[i] < insertionTimes[best]) {
                    best = i;
                }
            }

            // evict the page at temp[best] and replace it with the one requested
            temp[best] = pageref[p];
            insertionTimes[best] = inserttime++;
        }

        printf("\n%c\t", pageref[p]);
        for (i = 0; i < frameno; i++) {
            if (temp[i] != '-') {
                printf("\t\t %c", temp[i]);
            }
            else {
                printf(" \t\t");
            }
        }
    }

    printf("\nPage Faults: %d\t", pFaults);
    printf("\nPage Hits: %d\t", pHits);

    return 0;
}

示例运行：

Enter Page Frame: 3

Enter Pages: 5
Enter string: 41245

Page Requested   Page Frame 1   Page Frame 2    Page Frame 3
4                        4
1                        4               1
2                        4               1               2
4                        4               1               2
5                        5               1               2
Page Faults: 4
Page Hits: 1