c语言实现通过随机数产生一个地址序列，共产生 400 条。其中 50%的地址访问是顺序执行的， 另外 50%就是非顺序执行。且地址在前半部地址空间和后半部地址空间均匀分布。具体产 生方法如下： 1) 在前半部地址空间，即[0，199]中随机选一数 m，记录到地址流数组中（这是 非顺序执行）； 2) 接着“顺序执行一条指令”，即执行地址为 m+1 的指令，把 m+1 记录下来； 3) 在后半部地址空间，[200，399]中随机选一数 m’，作为新指令地址； 4) 顺序执行一条指令，其地址为 m’+1； 5) 重复步骤 1~4，直到产生 400 个指令地址。 3、将指令地址流变换成页地址（页号）流，简化假设为： 1) 页面大小为 1K（这里 K 只是表示一个单位，不必是 1024B）； 2) 用户虚存容量为 40K；3) 用户内存容量为 4 个页框到 40 个页框； 4) 用户虚存中，每 K 存放 10 条指令，4、循环运行，使用户内存容量从 4 页框到 40 页框。计算每个内存容量下不同页面置换 算法的命中率，命中率=1-缺页率

首先，我们需要实现随机数产生地址序列的代码。可以按照题目要求，先在前半部地址空间中随机选一个数，然后再顺序执行一条指令，记录下来下一条指令的地址；接着在后半部地址空间中随机选一个数作为新指令地址，再顺序执行一条指令，记录下来下一条指令的地址。重复这个过程，直到产生 400 个指令地址。

下面是代码示例：

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

#define MAX_ADDR 400
#define HALF_ADDR_SPACE 200
#define PAGE_SIZE 1024
#define USER_VIRTUAL_SIZE 40*1024
#define USER_PHYSICAL_MIN 4
#define USER_PHYSICAL_MAX 40

int main() {
    int addr_stream[MAX_ADDR];
    int i, m, m_prime, next_addr;
    int page_num, page_table[USER_VIRTUAL_SIZE/PAGE_SIZE];
    int physical_mem_size, frame_num, frame_queue[USER_PHYSICAL_MAX];
    int hit_count = 0, miss_count = 0;
    float hit_rate, miss_rate;

    srand((unsigned)time(NULL)); // 初始化随机数生成器

    // 生成随机地址序列
    for (i = 0; i < MAX_ADDR; i++) {
        if (rand() % 2 == 0) { // 前半部地址空间
            m = rand() % HALF_ADDR_SPACE;
            addr_stream[i] = m;
            next_addr = m + 1;
        } else { // 后半部地址空间
            m_prime = rand() % HALF_ADDR_SPACE + HALF_ADDR_SPACE;
            addr_stream[i] = m_prime;
            next_addr = m_prime + 1;
        }
        if (next_addr >= USER_VIRTUAL_SIZE) { // 地址越界
            i--; // 重新生成地址
        } else {
            i++;
            addr_stream[i] = next_addr;
        }
    }

    // 初始化页表
    for (i = 0; i < USER_VIRTUAL_SIZE/PAGE_SIZE; i++) {
        page_table[i] = -1; // -1 表示该页不在内存中
    }

    // 循环执行，内存容量从 4 页框到 40 页框
    for (physical_mem_size = USER_PHYSICAL_MIN; physical_mem_size <= USER_PHYSICAL_MAX; physical_mem_size++) {
        frame_num = 0; // 已分配的物理帧数
        hit_count = 0;
        miss_count = 0;

        // 初始化物理帧队列
        for (i = 0; i < physical_mem_size; i++) {
            frame_queue[i] = -1; // -1 表示该物理帧未被占用
        }

        // 执行地址序列，计算命中率
        for (i = 0; i < MAX_ADDR; i++) {
            page_num = addr_stream[i] / PAGE_SIZE;
            if (page_table[page_num] == -1) { // 缺页
                miss_count++;
                if (frame_num < physical_mem_size) { // 内存还有空闲物理帧
                    page_table[page_num] = frame_num; // 将该页放入一个空闲物理帧中
                    frame_queue[frame_num] = page_num; // 将该物理帧放入物理帧队列尾部
                    frame_num++;
                } else { // 内存已满，需要进行页面置换
                    int replace_page, replace_frame;
                    switch (physical_mem_size) {
                        case 4: // FIFO 置换算法
                            replace_page = frame_queue[0];
                            replace_frame = page_table[replace_page];
                            for (int j = 0; j < frame_num - 1; j++) {
                                frame_queue[j] = frame_queue[j+1]; // 物理帧队列前移
                            }
                            frame_queue[frame_num-1] = -1; // 将原队列尾部的物理帧标记为未占用
                            break;
                        case 8: // LRU 置换算法
                            replace_frame = 0;
                            for (int j = 1; j < frame_num; j++) {
                                if (frame_queue[j] < frame_queue[replace_frame]) {
                                    replace_frame = j; // 找到最近最少使用的物理帧
                                }
                            }
                            replace_page = frame_queue[replace_frame];
                            for (int j = replace_frame; j < frame_num - 1; j++) {
                                frame_queue[j] = frame_queue[j+1]; // 物理帧队列前移
                            }
                            frame_queue[frame_num-1] = -1; // 将原队列尾部的物理帧标记为未占用
                            break;
                        case 16: // CLOCK 置换算法
                            replace_frame = 0;
                            while (1) {
                                if (page_table[frame_queue[replace_frame]] == -1) { // 物理帧中没有页
                                    replace_page = frame_queue[replace_frame];
                                    break;
                                } else { // 物理帧中有页
                                    int page = frame_queue[replace_frame];
                                    int referenced = (page_table[page] & 0x80000000) >> 31; // 取出访问位
                                    if (referenced == 0) { // 如果访问位为0，说明该页很久没有被访问过
                                        replace_page = page;
                                        break;
                                    } else { // 如果访问位为1，将访问位置为0，并将该页移到物理帧队列尾部
                                        page_table[page] &= 0x7fffffff;
                                        replace_frame = (replace_frame + 1) % physical_mem_size;
                                    }
                                }
                            }
                            break;
                        case 32: // OPTIMAL 置换算法
                            replace_page = -1;
                            int max_dist = -1;
                            for (int j = 0; j < physical_mem_size; j++) {
                                int k = i + 1;
                                while (k < MAX_ADDR && addr_stream[k]/PAGE_SIZE != frame_queue[j]) {
                                    k++;
                                }
                                if (k >= MAX_ADDR) { // 未来不会再被访问的页
                                    replace_page = frame_queue[j];
                                    break;
                                } else {
                                    int dist = k - i;
                                    if (dist > max_dist) {
                                        max_dist = dist;
                                        replace_page = frame_queue[j];
                                    }
                                }
                            }
                            break;
                        default:
                            break;
                    }
                    // 将被替换的页从物理帧和页表中移除
                    page_table[replace_page] = -1;
                    for (int j = 0; j < physical_mem_size; j++) {
                        if (frame_queue[j] == replace_page) {
                            frame_queue[j] = -1;
                            break;
                        }
                    }
                    // 将新页放入被替换的物理帧中
                    page_table[page_num] = page_table[replace_page];
                    frame_queue[page_table[replace_page]] = page_num;
                }
            } else { // 命中
                hit_count++;
                switch (physical_mem_size) {
                    case 32: // OPTIMAL 置换算法需要更新被访问的页的距离
                        for (int j = i + 1; j < MAX_ADDR; j++) {
                            if (addr_stream[j]/PAGE_SIZE == page_num) {
                                int dist = j - i;
                                if (dist > page_table[page_num]) {
                                    page_table[page_num] |= (dist << 1);
                                }
                                break;
                            }
                        }
                        break;
                    default:
                        break;
                }
            }
        }

        // 计算命中率和缺页率
        hit_rate = (float)hit_count / MAX_ADDR;
        miss_rate = 1 - hit_rate;
        printf("Physical memory size: %d frames\n", physical_mem_size);
        printf("Hit rate: %.2f%%\n", hit_rate * 100);
        printf("Miss rate: %.2f%%\n", miss_rate * 100);
        printf("\n");
    }

    return 0;
}

上面的代码中实现了四种页面置换算法：FIFO、LRU、CLOCK 和 OPTIMAL。其中，CLOCK 算法需要使用一个访问位来记录每个物理帧中的页最近是否被访问过；OPTIMAL 算法需要预测每个页在未来最远的访问距离，并选择距离最远的页进行置换。

在模拟执行地址序列的过程中，对于每个缺失页，需要根据当前内存中的物理帧数以及所采用的页面置换算法选择一个页进行置换。如果内存中还有空闲物理帧，则将该页放入一个空闲物理帧中；否则，需要根据所采用的页面置换算法选择一个物理帧进行替换。替换时，需要将被替换的页从物理帧和页表中移除，并将新页放入被替换的物理帧中。

最后，根据命中次数和缺失次数计算命中率和缺页率，输出结果。循环执行，可以得到不同内存容量下不同页面置换算法的命中率和缺页率。