參考書籍：《Linux操作系統(tǒng)實驗教材》——主編：費翔林

FIFO 喊儡、 LRU 、OPT

#include<stdio.h>  
#include<stdlib.h>  
#include<ctype.h>  
#include<sys/time.h>  
#include<unistd.h>  
#define BUSY 1  
#define IDLE 0  
#define blockNumber 3  
#define n 10  
int Time = 0;
typedef struct _Page{ // 頁面  
    int pageID;     //頁號  
}Page;  
typedef struct _PageQueue{ //頁面隊列  
    Page page;  
    struct _PageQueue* next; //下一頁面  
}PageQueue;  
typedef struct _Block{ //塊記錄結(jié)構(gòu)  
    Page *page; //頁面  
    long time; //最后訪問時間  
    int state; //頁塊是否空閑  
}Block;  
typedef struct _BlockQueue{ //塊隊列  
    Block block;  
    struct _BlockQueue *next;  
}BlockQueue;  
typedef struct process{ // 進程結(jié)構(gòu)  
    PageQueue pages; //頁面  
    unsigned int pageLength; // 頁面數(shù)  
}process;//進程

//初始化主存塊，把首地址返回欠雌，如果分配失敗返回NULL 
BlockQueue* InitializeBlockQueue(unsigned int size){
    BlockQueue *p1, *p2;  
    BlockQueue *block;  
    block = NULL;
    int i;
    for(i = 0; i < size; ++i){  
        p1 = (BlockQueue*)malloc(sizeof(BlockQueue));  
        p1->block.time = 0;  
        p1->block.state = 0;  
        p1->block.page = NULL;  
        p1->next = NULL;  
        if(block == NULL) block = p1;  
        else p2->next = p1;  
        p2 = p1;  
    }  
    return block;  
}

//獲取塊長度
int GetBlockQueueSize(BlockQueue *blockQueue){  
    BlockQueue *presentBlock;  
    presentBlock = blockQueue;  
    int blockQueueSize = 0;  
    while(presentBlock != NULL){  
        blockQueueSize++;  
        presentBlock = presentBlock->next;  
    }  
    return blockQueueSize;  
}

//清空塊內(nèi)容
void ResetBlockQueue(BlockQueue *blockQueue){
    BlockQueue *presentBlock;  
    presentBlock = blockQueue;  
    while(presentBlock != NULL){  
        presentBlock->block.page = NULL;  
        presentBlock->block.state = IDLE;  
        presentBlock->block.time = 0;  
        presentBlock = presentBlock->next;  
    }  
}

//打印塊信息
void PrintBlockList(BlockQueue *blockQueue, int pageID, int color){  
    BlockQueue *presentBlock;  
    char strl[5], *str2;  
    presentBlock = blockQueue;  
    while(presentBlock != NULL){  
        if(presentBlock->block.state == IDLE)  
            printf("|    |\n");  
        else{  
            printf("| %d  |\n", presentBlock->block.page->pageID);  
        }  
        presentBlock = presentBlock->next;  
    }  
    printf("\n");  
}

//初始化頁面
PageQueue* InitializePageQueue(unsigned int pageLength, int maxPageID){  
    srand((unsigned)time(NULL)); // 隨機數(shù)種子 
//  srand(101);  // 偽隨機像棘，用于調(diào)試 
    PageQueue *head;  
    head = NULL;  
    PageQueue *p, *q;
    int i;
    for(i = 0; i < pageLength; ++i){  
        p = (PageQueue*)malloc(sizeof(PageQueue));  
        p->page.pageID = (int)(rand() % (maxPageID));  
        printf("%d ", p->page.pageID);  
        p->next = NULL;  
        if(head == NULL) head = p;  
        else q->next = p;  
        q = p;  
    }  
    printf("\n");  
    return head;  
}  

//初始化進程 
void InitializeProcess(process *proc, unsigned int pageSize, unsigned int maxPageID){
    printf("進程初始化：\n");  
    proc->pageLength = pageSize;  
    proc->pages.next = InitializePageQueue(pageSize, maxPageID);  
}

//搜索特定頁面  
BlockQueue* SearchPage(BlockQueue *blockQueue, Page page){  

    BlockQueue *p;  
    int blockSize;  
    p = blockQueue;  
    while(p != NULL){  
        if(p->block.page != NULL){  
            if(p->block.page->pageID == page.pageID)  
                return p;  
        }  
    }  
    return NULL;  
}

//搜索空閑塊
BlockQueue* SearchIdleBlock(BlockQueue *blockQueue){  
    BlockQueue *p;  
    p = blockQueue;  
    while(p != NULL){  
        if(p->block.state == IDLE)  
            return p;  
        else p = p->next;  
    }  
    return NULL;  
}

//取得主存中停留最久的頁面稽亏，返回它的地址
BlockQueue* GetOldestBlock(BlockQueue *blockQueue){  
    BlockQueue *p;  
    p = blockQueue;
    BlockQueue *q; // 輔助標記最小time的block的指針 
    q = p;
    if (p->next != NULL){
        while(p->next!=NULL){  //輪循 比較，求最小的time的block并返回 
            if (q->block.time > p->next->block.time){
                q = p->next;
            };
            p = p->next;
        };
        return q;
    }else {
        return p;
    }
}

// 取得最近最久未使用的Block缕题，原理與 GetOldestBlock相同
// 查找time最小的 time的block
// 不同的處理再LRU函數(shù)中可見 
BlockQueue* GetLastestNoUseBlock(BlockQueue *blockQueue){
    return GetOldestBlock(blockQueue); 
}

BlockQueue* GetLongTimeNoUseBlock(BlockQueue *blockQueue, PageQueue *cur, int Time){
    BlockQueue *p;  
    p = blockQueue;
    PageQueue *c;
    c = cur;
    BlockQueue *q; // 輔助標記要返回的block的指針截歉，time=0則立即返回，否則返回time最大的烟零。 
    q = p;
    int ti = Time;
    
    while(p != NULL) {
        while(c!= NULL){
            ti++;
            if (p->block.page->pageID == c->page.pageID){
                p->block.time = ti;
                break; 
            }
            c = c->next;
        };
        ti = Time; // 恢復(fù) 
        p = p->next;
    };
    p = q;
    if (p->next != NULL){
        while(p->next!=NULL){  //輪循 比較瘪松，求time為0， 若無為0則求最大的time的block并返回 
            if (p->block.time == 0){
                return p;
            }
            if (q->block.time < p->next->block.time){
                q = p->next;
            };
            p = p->next;
        };
        return q;
    }else {
        return p;
    }
     
} 



//先進先出算法
void FIFO(BlockQueue *blockQueue, process *proc){  
    int blockQueueSize = GetBlockQueueSize(blockQueue);  
    PageQueue *currentPage;  
    currentPage = proc->pages.next;  
    BlockQueue *p;  
    p = blockQueue;  
    int count = 0, cnt = 0;
    Time = 0; 
    printf("\nFIFO算法:\n");
    while(currentPage != NULL){  
        int ok = 0;  
        p = blockQueue;  
        Time++; // 用于輔助 記錄每個塊的page進入的時間
        while(p != NULL){ // 判斷當前頁面是否已在塊（內(nèi)存）中 
            if(p->block.page !=NULL && p->block.page->pageID == currentPage->page.pageID){  
                ok = 1;  
                break;  
            }  
            p = p->next;  
        }  
        if(ok){ // 若當前頁面已在內(nèi)存中
            PrintBlockList(blockQueue, currentPage->page.pageID, 0);
        }  
        else{ // 若當前頁面不在內(nèi)存中 锨阿，調(diào)度
            BlockQueue *block;  
            block = SearchIdleBlock(blockQueue);  
            if(block != NULL){ // 內(nèi)存中有空閑塊宵睦，不需要把已有的塊置換出去 
                block->block.state = BUSY;  
                block->block.time = Time;
                block->block.page = (Page*)malloc(sizeof(Page));  
                block->block.page->pageID = currentPage->page.pageID;  
                PrintBlockList(blockQueue, currentPage->page.pageID, 1);  
            }  
            else{  // 內(nèi)存沒有空閑塊
                BlockQueue *block;  
                block = GetOldestBlock(blockQueue); // 獲得塊隊列中最先進入的塊 
                block->block.time = Time;
                block->block.page->pageID = currentPage->page.pageID;  
                PrintBlockList(blockQueue, currentPage->page.pageID, 2);  
            };
            count++; 
        }  
        currentPage = currentPage->next;  
        cnt++;  
    }  
    printf("FIFO\n缺頁次數(shù) = %d\n總數(shù) = %d\n缺頁率 = %.4lf", count, cnt, (double)count/(double)cnt); 
}

// 最近最少使用算法 
void LRU(BlockQueue *blockQueue, process *proc){  
    int blockQueueSize = GetBlockQueueSize(blockQueue);  
    PageQueue *currentPage;  
    currentPage = proc->pages.next;  
    BlockQueue *p;  
    p = blockQueue;  
    int count = 0, cnt = 0;
    Time = 0;
    printf("\nLRU算法:\n");
    while(currentPage != NULL){  
        int ok = 0;  
        p = blockQueue;  
        Time++; // 用于輔助 記錄每個塊的page進入的時間
        while(p != NULL){ // 判斷當前頁面是否已在塊（內(nèi)存）中 
            if(p->block.page !=NULL && p->block.page->pageID == currentPage->page.pageID){
                // 與FIFO的唯一區(qū)別：即使沒有調(diào)度，但是有使用墅诡，需要更新time
                p->block.time = Time; 
                
                ok = 1;  
                break;  
            }  
            p = p->next;  
        }  
        if(ok){ // 若當前頁面已在內(nèi)存中
            PrintBlockList(blockQueue, currentPage->page.pageID, 0);
        }  
        else{ // 若當前頁面不在內(nèi)存中 壳嚎，調(diào)度
            BlockQueue *block;  
            block = SearchIdleBlock(blockQueue);  
            if(block != NULL){ // 內(nèi)存中有空閑塊，不需要把已有的塊置換出去 
                block->block.state = BUSY;  
                block->block.time = Time;
                block->block.page = (Page*)malloc(sizeof(Page));  
                block->block.page->pageID = currentPage->page.pageID;  
                PrintBlockList(blockQueue, currentPage->page.pageID, 1);  
            }  
            else{  // 內(nèi)存沒有空閑塊
                BlockQueue *block;  
                block = GetLastestNoUseBlock(blockQueue); // 獲得塊隊列中最近未使用的block 
                block->block.time = Time;
                block->block.page->pageID = currentPage->page.pageID;  
                PrintBlockList(blockQueue, currentPage->page.pageID, 2);  
            };
            count++; 
        }  
        currentPage = currentPage->next;  
        cnt++;  
    }  
    printf("LRU\n缺頁次數(shù) = %d\n總數(shù) = %d\n缺頁率 = %.4lf", count, cnt, (double)count/(double)cnt); 
}

// 最佳算法末早，理想狀態(tài)
// block.time不再用來記錄最后進入時間烟馅，而用來記錄未來最先到達之間，未來不出現(xiàn)為0 
void OPT(BlockQueue *blockQueue, process *proc){  
    int blockQueueSize = GetBlockQueueSize(blockQueue);  
    PageQueue *currentPage;  
    currentPage = proc->pages.next;  
    BlockQueue *p;  
    p = blockQueue;  
    int count = 0, cnt = 0;
    Time = 0;  // 初始化 
    printf("\nOPT算法:\n");
    while(currentPage != NULL){  
        int ok = 0;  
        p = blockQueue;  
        Time++; // 用于輔助 記錄每個塊的page進入的時間
        while(p != NULL){ // 判斷當前頁面是否已在塊（內(nèi)存）中 
            if(p->block.page !=NULL && p->block.page->pageID == currentPage->page.pageID){  
                ok = 1;  
                break;  
            }  
            p = p->next;  
        }  
        if(ok){ // 若當前頁面已在內(nèi)存中
            PrintBlockList(blockQueue, currentPage->page.pageID, 0);
        }  
        else{ // 若當前頁面不在內(nèi)存中 然磷，調(diào)度
            BlockQueue *block;  
            block = SearchIdleBlock(blockQueue);  
            if(block != NULL){ // 內(nèi)存中有空閑塊焙糟，不需要把已有的塊置換出去 
                block->block.state = BUSY;  
                block->block.time = 0;
                block->block.page = (Page*)malloc(sizeof(Page));  
                block->block.page->pageID = currentPage->page.pageID;  
                PrintBlockList(blockQueue, currentPage->page.pageID, 1);  
            }  
            else{  // 內(nèi)存沒有空閑塊，需要把已有的塊置換出去  
                BlockQueue *block;  
                block = GetLongTimeNoUseBlock(blockQueue, currentPage, Time); // 獲得未來最久未使用或不使用的page對應(yīng)的block 
                block->block.time = 0;
                block->block.page->pageID = currentPage->page.pageID;  
                PrintBlockList(blockQueue, currentPage->page.pageID, 2);  
            };
            count++; 
        }  
        currentPage = currentPage->next;  
        cnt++;  
    }  
    printf("OPT\n缺頁次數(shù) = %d\n總數(shù) = %d\n缺頁率 = %.4lf", count, cnt, (double)count/(double)cnt); 
}

int main(){  
    int pageNumber;
    printf("輸入page number = \n");
    scanf("%d", &pageNumber);  
    printf("Block Number : %d, Page Number : %d\n\n", blockNumber, pageNumber);  
    BlockQueue *blocks;
    process proc;  
    InitializeProcess(&proc, pageNumber, n);
    blocks = InitializeBlockQueue(blockNumber);
    printf("\n--------------------\n");
    // FIFO算法 
    FIFO(blocks, &proc);
    ResetBlockQueue(blocks); 
    
    printf("\n--------------------\n");
    // LRU算法
    LRU(blocks, &proc);
    ResetBlockQueue(blocks); 
    
    printf("\n--------------------\n");
    // OPT算法 
    OPT(blocks, &proc);
    ResetBlockQueue(blocks);  
    
    return 0;  
}  

貼效果圖：

輸入.png

FIFO

LRU

OPT

建議理解自己敲样屠，并沒想象中那么難穿撮。