要求

圖上應(yīng)為生成200個(gè)邏輯地址

創(chuàng)建文件代碼

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

#define PROC_NUM 12
#define PAGE_SIZE 256
#define PAGE_NUM 64

int main()
{
    char filename[]="a.txt";
    char buf[PAGE_SIZE];
    for(int i = 0; i < PAGE_SIZE; ++i)
        buf[i] = 'a';
    for(int id = 0; id < PROC_NUM; ++id)
    {
        filename[0] = 'a' + (char)id;
        FILE *f = fopen(filename, "w");
        for(int pageno = 0; pageno < PAGE_NUM; ++pageno)
        {
            buf[0] = id + 1;
            buf[1] = pageno;
            fwrite(buf, sizeof(char), PAGE_SIZE, f);
        }
        fclose(f);
    }
    return 0;
}

模擬運(yùn)行代碼

#include <stdio.h>
#include <stdlib.h>
#include <semaphore.h>
#include <pthread.h>
#include <time.h>
#include <unistd.h>

#define MEM_SIZE 16384
#define PAGE_SIZE 256
#define PAGE_NUM 64
#define PROC_PAGE 10
#define PROC_NUM 12

struct proc//進(jìn)程
{
    int id;//進(jìn)程號(hào)
    int pages[PROC_PAGE];//存放物理頁框號(hào) pages[0]存頁表
    int miss;//缺頁次數(shù)
    int p;//FIFO指針
    int counter;//LRU計(jì)數(shù)器
};

void *Process(void* i); //模擬進(jìn)程i
char Access(unsigned int addr, int id); //讀出物理地址上的內(nèi)容
int getPhyAddr(unsigned int virAddr, int id); //邏輯地址轉(zhuǎn)化為物理地址
void loadPage(unsigned int addr, int id); //把頁面載入內(nèi)存
int FIFO(unsigned int addr, int id); //頁面替換算法
int LRU(unsigned int addr, int id);

unsigned char mem[MEM_SIZE] = {0};//分配內(nèi)存
_Bool status[PAGE_NUM] = {0};//內(nèi)存占用情況恩静，即位示圖
struct proc jobs[PROC_NUM];
sem_t mutex;//分配和歸還頁框是原子操作
sem_t job_sem;//限制內(nèi)存64個(gè)頁框最多同時(shí)進(jìn)行6個(gè)進(jìn)程
sem_t mutex2;//訪問虛擬地址是原子操作

int main()
{
    //初始化進(jìn)程
    for (int i = 0; i < PROC_NUM; ++i)
    {
        jobs[i].id = i;
        jobs[i].miss = 0;
        jobs[i].p = 1;
        jobs[i].counter = 0;
    }
    //初始化信號(hào)量
    sem_init(&mutex, 0, 1);
    sem_init(&job_sem, 0, 6);
    sem_init(&mutex2, 0, 1);
    //創(chuàng)建12個(gè)進(jìn)程并等待結(jié)束
    pthread_t tid[PROC_NUM];
    int id[PROC_NUM] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    for (int i = 0; i < PROC_NUM; ++i)
    {
        pthread_attr_t attr;
        pthread_attr_init(&attr);
        pthread_create(&tid[i], &attr, Process, &id[i]);
    }
    for (int i = 0; i < PROC_NUM; ++i)
        pthread_join(tid[i], NULL);
    //打印缺頁中斷率
    for (int i = 0; i < PROC_NUM; ++i)
        printf("進(jìn)程%d缺頁中斷次數(shù)=%d\n", i + 1, jobs[i].miss);
    return 0;
}

void* Process(void* i)
{
    int id = *((int*)i);//傳入的進(jìn)程號(hào)
    sem_wait(&job_sem);
    sem_wait(&mutex);
    //分配頁框
    for (int i = 0; i < PROC_PAGE; ++i)
        for (int j = 0; j < PAGE_NUM; ++j)
            if (status[j] == 0)
            {
                status[j] = 1;
                jobs[id].pages[i] = j;
                break;
            }
    sem_post(&mutex);
    //訪問n個(gè)虛擬地址
    unsigned int addr;
    srand((unsigned)time(NULL));
    for (int i = 0; i < 200; ++i)
    {
        addr = rand() % MEM_SIZE;
        sem_wait(&mutex2);
        printf("進(jìn)程號(hào)%lu\n虛擬地址%04x\t", pthread_self(), addr);
        char c;
        //虛擬地址上的內(nèi)容
        char str[] = "a.txt";
        str[0] = ((char)id + 'a');
        FILE *f = fopen(str, "r");
        fseek(f, addr, 0);
        c = fgetc(f);
        fclose(f);
        printf("虛擬地址的內(nèi)容: %c\n", c);
        //讀出物理地址上的內(nèi)容（假設(shè)地址已在內(nèi)存）
        c = Access(addr, id);
        printf("物理地址的內(nèi)容: %c\n", c);
        sem_post(&mutex2);
        //sleep(0.01);//休眠
    }
    //清空頁框
    for (int i = 0; i < PROC_PAGE; ++i)
    {
        int phyPageAddr = jobs[id].pages[i] * PAGE_SIZE;
        for(int i = 0; i < PAGE_SIZE; ++i)
            mem[phyPageAddr+i] = 0;     
    }
    //歸還頁框
    sem_wait(&mutex);
    for (int i = 0; i < PROC_PAGE; ++i)
        status[jobs[id].pages[i]] = 0;
    sem_post(&mutex);
    sem_post(&job_sem);
    return 0;
}

char Access(unsigned int addr, int id)
{
    int phyAddr = getPhyAddr(addr, id);
    if (phyAddr != -1)
    {
        printf("物理地址%04x\t", phyAddr);
        return mem[phyAddr];
    }
    //缺頁
    jobs[id].miss++;//缺頁次數(shù)+1 
    loadPage(addr, id);
    return Access(addr, id);
}

//頁表項(xiàng)第四字節(jié)的第一位為有效位窗看，其余位為頁框號(hào);第一字節(jié)是time-of-use
int getPhyAddr(unsigned int virAddr, int id)
{
    //virAddr前6位為頁號(hào)，后8為為頁內(nèi)偏移
    int virPage = ((virAddr & 0x00003F00)>>8) & 0x0000003F;//頁號(hào)
    int tableAddr = jobs[id].pages[0] * PAGE_SIZE;//頁表地址
    int validbit = (mem[tableAddr + virPage * 4 + 3]>>7) & 0x00000001;//有效位
    if (validbit == 1)
    {
        jobs[id].counter++;
        mem[tableAddr + virPage * 4] = jobs[id].counter & 0x000000ff;//寫入time-of-use
        int phyAddr = ((mem[tableAddr + virPage * 4 + 3]&0x0000003f)<<8) | (virAddr&0x000000FF);
        return phyAddr;//返回物理地址
    }
    return -1;//報(bào)告缺頁
}

void loadPage(unsigned int addr, int id)
{
    //打開文件沙峻，光標(biāo)移到虛擬頁面地址
    char str[] = "a.txt";
    str[0] = ((char)id + 'a');
    FILE *f = fopen(str, "r");
    fseek(f, addr&0x00003F00, 0);
    //模擬將磁盤上的數(shù)據(jù)載入內(nèi)存
    int phyPageAddr = LRU(addr, id) * PAGE_SIZE;
    for (int i = 0; i < PAGE_SIZE; ++i)
        mem[phyPageAddr + i] = fgetc(f);
    fclose(f);
}

int FIFO(unsigned int addr, int id) 
//發(fā)生缺頁時(shí)循環(huán)載入內(nèi)存的第1~9頁面暖夭，并修改頁表項(xiàng)（清空被替換虛擬頁面的頁表項(xiàng)锹杈，虛擬頁號(hào)對(duì)應(yīng)的頁表項(xiàng)有效位為1撵孤，頁框號(hào)為相應(yīng)頁面的頁框號(hào)）
//返回內(nèi)存第p個(gè)頁面的頁框號(hào)
{
    int temp = jobs[id].p;
    int phyPage = jobs[id].pages[temp];
    //jobs[id].p = (jobs[id].p+1) % 9;//FIFO指針+1
    jobs[id].p = jobs[id].p%9 + 1;//FIFO指針+1
    int tableAddr = jobs[id].pages[0] * PAGE_SIZE;
    if (mem[phyPage * PAGE_SIZE] != 0)//需要頁面替換
    {
        int lastVirPage = mem[phyPage * PAGE_SIZE + 1] & 0x0000003f;//被替換頁面的頁號(hào)
        mem[tableAddr + lastVirPage * 4 + 3] = 0x00;
    }     
    int virPage = (addr & 0x00003F00) >> 8;    
    mem[tableAddr + virPage * 4 + 3] = 0x00000080 | phyPage;
    return phyPage;
}

int LRU(unsigned int addr, int id)//前9次無需替換
{
    int tableAddr = jobs[id].pages[0] * PAGE_SIZE;//頁表地址
    int phyPageAddr, virPage, tou, min_tou = 200, min_i = 1;
    _Bool replace = 1;
    for (int i = 1; i <= 9; ++i)
    {
        phyPageAddr = jobs[id].pages[i] * PAGE_SIZE;
        if (mem[phyPageAddr] == 0)//找到空頁面
        {
            min_i = i;
            replace = 0;//無需替換
            break;
        }
        virPage = mem[phyPageAddr+1];//頁面的第2字節(jié)存放虛擬頁號(hào)
        tou = mem[tableAddr + virPage * 4];//time-of-use
        if (tou < min_tou)
        {
            min_tou = tou;
            min_i = i;
        }
    }
    int phyPage = jobs[id].pages[min_i];
    if (replace)
    {
        int lastVirPage = mem[phyPage * PAGE_SIZE + 1];
        mem[tableAddr + lastVirPage * 4 + 3] = 0x00;
    }
    int virPage2 = (addr & 0x00003F00) >> 8;
    mem[tableAddr + virPage2 * 4 + 3] = 0x00000080 | phyPage;
    return phyPage;
}