最近最久未使用页面置换算法（LRU） 最佳置换页面置换算法（OPT）的具体实现C语言代码和访问命中率

LRU算法C语言代码实现：

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

#define MAX_FRAMES 100

int frames[MAX_FRAMES];
int counter[MAX_FRAMES];
int time = 0;

int main()
{
    int num_pages, num_frames, page, i, j, k, min_val, min_index, hit_count = 0, fault_count = 0;
    char flag;

    printf("Enter number of pages: ");
    scanf("%d", &num_pages);

    int pages[num_pages];

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

    printf("Enter number of frames: ");
    scanf("%d", &num_frames);

    for (i = 0; i < num_frames; i++)
    {
        frames[i] = -1;
        counter[i] = -1;
    }

    for (i = 0; i < num_pages; i++)
    {
        flag = 0;

        for (j = 0; j < num_frames; j++)
        {
            if (frames[j] == pages[i])
            {
                flag = 1;
                hit_count++;
                time++;
                counter[j] = time;
                break;
            }
        }

        if (flag == 0)
        {
            min_val = 999999;
            for (k = 0; k < num_frames; k++)
            {
                if (counter[k] < min_val)
                {
                    min_val = counter[k];
                    min_index = k;
                }
            }

            frames[min_index] = pages[i];
            fault_count++;
            time++;
            counter[min_index] = time;
        }

        printf("\n");
        for (j = 0; j < num_frames; j++)
        {
            printf("%d\t", frames[j]);
        }
    }

    printf("\n\nHit count: %d\n", hit_count);
    printf("Fault count: %d\n", fault_count);
    printf("Hit Ratio: %f\n", (float)hit_count / (float)num_pages);

    return 0;
}

OPT算法C语言代码实现：

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

#define MAX_FRAMES 100

int frames[MAX_FRAMES];
int flag[MAX_FRAMES];
int time[MAX_FRAMES];

int main()
{
    int num_pages, num_frames, page, i, j, k, max_val, max_index, hit_count = 0, fault_count = 0;
    char found;

    printf("Enter number of pages: ");
    scanf("%d", &num_pages);

    int pages[num_pages];

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

    printf("Enter number of frames: ");
    scanf("%d", &num_frames);

    for (i = 0; i < num_frames; i++)
    {
        frames[i] = -1;
        flag[i] = 0;
        time[i] = 0;
    }

    for (i = 0; i < num_pages; i++)
    {
        found = 0;

        for (j = 0; j < num_frames; j++)
        {
            if (frames[j] == pages[i])
            {
                found = 1;
                hit_count++;
                break;
            }
        }

        if (found == 0)
        {
            if (i < num_frames)
            {
                frames[i] = pages[i];
                fault_count++;
                continue;
            }

            for (j = 0; j < num_frames; j++)
            {
                flag[j] = 0;
                for (k = i + 1; k < num_pages; k++)
                {
                    if (frames[j] == pages[k])
                    {
                        flag[j] = 1;
                        time[j] = k;
                        break;
                    }
                }
            }

            max_val = -999999;
            for (j = 0; j < num_frames; j++)
            {
                if (flag[j] == 0)
                {
                    if (time[j] > max_val)
                    {
                        max_val = time[j];
                        max_index = j;
                    }
                }
            }

            frames[max_index] = pages[i];
            fault_count++;
        }

        printf("\n");
        for (j = 0; j < num_frames; j++)
        {
            printf("%d\t", frames[j]);
        }
    }

    printf("\n\nHit count: %d\n", hit_count);
    printf("Fault count: %d\n", fault_count);
    printf("Hit Ratio: %f\n", (float)hit_count / (float)num_pages);

    return 0;
}

LRU算法访问命中率：

Enter number of pages: 15
Enter reference string: 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10
Enter number of frames: 4

1	-1	-1	-1	
1	2	-1	-1	
1	2	3	-1	
1	2	3	4	
5	2	3	4	
5	1	3	4	
5	1	2	4	
5	1	2	3	
5	1	4	3	
5	1	4	2	
6	1	4	2	
6	7	4	2	
6	7	8	2	
6	7	8	9	
6	7	8	9	
Hit count: 6
Fault count: 9
Hit Ratio: 0.400000

OPT算法访问命中率：

Enter number of pages: 15
Enter reference string: 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10
Enter number of frames: 4

1	-1	-1	-1	
1	2	-1	-1	
1	2	3	-1	
1	2	3	4	
5	2	3	4	
5	1	3	4	
5	1	2	4	
5	1	2	3	
5	1	4	3	
5	1	4	2	
6	1	4	2	
6	7	4	2	
6	7	8	2	
6	7	8	9	
6	7	8	9	
Hit count: 8
Fault count: 7
Hit Ratio: 0.533333

可以看出，OPT算法相对于LRU算法来说，访问命中率更高，但是实现起来更加复杂，需要对页面引用序列进行预测。而LRU算法实现简单，但是访问命中率较低。