假设有10个页面，n个页框。页面的访问顺序为0, 9, 8, 4, 4, 3, 6, 5, 1, 5, 0, 2, 1, 1, 1, 1, 8, 8, 5,

3, 9, 8, 9, 9, 6, 1, 8, 4, 6, 4, 3, 7, 1, 3, 2, 9, 8, 6, 2, 9, 2, 7, 2, 7, 8, 4, 2, 3, 0, 1, 9, 4,

7, 1, 5, 9, 1, 7, 3, 4, 3, 7, 1, 0, 3, 5, 9, 9, 4, 9, 6, 1, 7, 5, 9, 4, 9, 7, 3, 6, 7, 7, 4, 5, 3, 5, 3, 1, 5, 6, 1, 1, 9, 6, 6, 4, 0, 9, 4, 3。

当n在[1,10]中取值时，请编写程序实现OPT、LRU、FIFO页面置换算法，并根据页面访问顺序模拟执行，分别计算缺页数量。

1.1思路:

• FIFO:采用队列存储,队列最大容量可变,设为n.

访问->未找到(缺页数++)->尝试将缺页加入队列->容量够则加入队尾,否则出队首元素,并将新元素加入队尾（即顺序前移）.

• LRU:链表法实现,链表最大长度为n

访问:1.未找到(缺页数++)->尝试将缺页加入链表->容量够则加入链表头,否则淘汰链表尾,并加入链表头部

2.找到->将对应链表节点提到头节点.

• OPT:未来最久不被使用的页面

访问->未找到(缺页数++)->尝试将缺页加入页框->容量够则加入(数组),否则,计算当前时刻页框中所有页面距离下一次使用的时间,取最大的淘汰,并加入新的.

1.2代码实现：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define tot 100
int schedule[tot] = {0, 9, 8, 4, 4, 3, 6, 5, 1, 5, 0, 2, 1, 1, 1, 1, 8, 8, 5, 

3, 9, 8, 9, 9, 6, 1, 8, 4, 6, 4, 3, 7, 1, 3, 2, 9, 8, 6, 2, 9, 2, 7, 2, 7, 8, 4, 2, 3, 0, 1, 9, 4,

7, 1, 5, 9, 1, 7, 3, 4, 3, 7, 1, 0, 3, 5, 9, 9, 4, 9, 6, 1, 7, 5, 9, 4, 9, 7, 3, 6, 7, 7, 4, 5, 3, 5, 3, 1, 5, 6, 1, 

1, 9, 6, 6, 4, 0, 9, 4, 3};
int FIFO(int n) {
    int table[n];//队列
    int head = 0;//队首 
    int tail = 0;//队尾 
    int sum = 0;//缺页数 
    int i, j, k;
    int flag = 0;
    
    for (i = 0; i < tot; i++) {
        int tar = schedule[i];
        flag = 0;
        for (j = head; j < tail; j++) {
            if (tar == table[j]) {
                //找到
                flag = 1;
                break;
            }
        }
        if (!flag) {
            //没找到
            sum++; 
            if (tail < n) {
                //未满，加入队尾 
                table[tail++] = tar;
            } else {
                for (k = head; k+1 < tail; k++) {
                    table[k] = table[k+1];
                    //顺序前移 
                }
                table[tail-1] = tar;
            }
        }
    }
    return sum;
}

typedef struct Node{
    int order;
    struct Node * next;
}Node, *NPT;
int LRU(int n) {
    Node node[n];
    NPT head = NULL, p, r;
    int i, j, k, cnt = 0;
    int sum = 0;
    int flag = 0;
    
    for (i = 0; i < tot; i++) {
        flag  = 0; 
        int tar = schedule[i];
        r = NULL;
        p = head;
        while (p != NULL) {
            if (p->order == tar) {
                //找到
                flag = 1;
                break; 
            } 
            r = p;
            p = p->next;
        } 
        if (flag) {
            //找到 
            if (r == NULL) {
                //就在头节点，无需操作 
            } else {
                r->next = p->next;
                p->next = head;
                head = p;
            } 
        } else {
            sum++;
            p = (NPT) malloc(sizeof(Node));
            p->order = tar;
            p->next = NULL;
            if (cnt == n) {
                //容量限制
                r = head;
                if (r->next == NULL) {
                    head = p;
                } else {
                    while (r->next->next != NULL) {
                        r = r->next;
                    }
                    r->next = NULL;
                    p->next = head;
                    head = p;
                } 
            } else {
                p->next = head;
                head = p;
                cnt++;
            }
        } 
    }
    return sum;
}

int OPT(int n) {
    int table[n];
    int cnt = 0, sum = 0;
    int i, j, k, flag = 0;
    for (i = 0; i < tot; i++) {
        int tar = schedule[i];
        flag = 0;
        for (j = 0; j < cnt; j++) {
            if (table[j] == tar) {
                flag = 1;
                break;
            }
        }
        if (flag) {
            //找到
             
        } else {
            sum++;
            if (cnt == n) {
                //容量满了
                int max = 0;
                int index = -1;
                int temp = 0;
                for (j = 0; j < cnt; j++) {
                    temp = 0;
                    for (k = i + 1; k < tot; k++) {
                        if (table[j] == schedule[k]) {
                            temp++;
                            break;
                        } else temp++;
                    }
                    if (k == tot) {
                        temp = 1000;
                    }
                    if (temp > max) {
                        max = temp;
                        index = j;
                    }
                } 
                table[index] = tar;
            } else {
                table[cnt++] = tar;
            }
        }
    }
    return sum;
}

int main(){
    int i;
    for (i = 1; i <= 10; i++) {
        printf("OPT= %d, FIFO = %d, lru = %d\n",OPT(i), FIFO(i), LRU(i));
    }
    return 0;
}