lru.c

TC, Win-TC 编译运行通过 最近最少用页面调度算法

/*
最近最少用页面调度算法
沈阳工业大学辽阳校区 邓威
*/
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
/* 主存可用块数 */
#define MAX_ELEMENT 3

typedef struct node
{
    int page; /* 内存块中当前的页面调度号 */
    struct node *next; /* 下一个内存块地址 */
} NODE;

/* 页面调度顺序 */
int pages[] = { 4,3,0,4,1,1,2,3,2 };
/* 当前处理的页面索引 */
int current_node;
/* 共缺多少页，因为第一个页面一定是内存块中没有的
   所以默认值是 1
*/
int LOST = 1;
/* 整个单链表的头指针 */
NODE *start = NULL;
/* 显示当前主存中的页面调度情况 */
void prin();
/* 创建一个页面值为 page 的内存块 即单链表中的节点 */
NODE *create(int page);
/* 搜索页面为 page 的内存块地址 */
NODE *search(int page);
/* 把地址为 moved 的内存块放到最前面 */
void first(NODE *moved);
/* 在链表头处插入一个页面值为 page 的内存块 */
void insert(int page);

void prin()
{
    NODE *temp;
    temp = start;
    printf("\nSTACK : ");
    while(temp != NULL) {
        printf("%d ",temp->page);
        temp = temp->next;
    }
    printf("\n\n");
    return;
}
NODE *create(int page)
{
    NODE *temp;
    temp = (NODE *)malloc(sizeof(NODE));
    temp->page = page;
    temp->next = NULL;
    return temp;
}
NODE *search(int page)
{
    NODE *temp;
    temp = start;
    while(temp != NULL) {
        if( temp->page == page ) return temp;
        temp = temp->next;
    }
    return NULL;
}
void first(NODE *moved)
{
    NODE *NEXT;
    NODE *temp;

    printf("%d in links, move first.\n",moved->page);
    if( moved == start ) return;
    temp = start;

    while( temp->next != moved ) temp = temp->next;

    NEXT = moved->next;
    temp->next = NEXT;

    moved->next = start;
    start = moved;
    return;
}
void insert(int page)
{
    NODE *temp;
    NODE *temp2;

    printf("%d not in links, insert.\n",page);
    temp = create(page);
    temp->next = start;

    start = temp;

    if( current_node >= MAX_ELEMENT ) {
        temp2 = temp;
        while( temp->next != NULL ) temp = temp->next;
        while( temp2->next != temp ) temp2 = temp2->next;
        temp2->next = NULL;
        free(temp);       
        printf("delete last node.\n");
    }
    else current_node++;
    LOST++;
    return;
}
void main()
{
    int total_pages = sizeof(pages)/sizeof(int);
    int point = 0;
    NODE *temp;

    printf("\n\n LRU \n\n");

    start = create( pages[point++] );
    current_node = 1;

    printf("total page:%d\n", total_pages);

    for(point=1;point<total_pages;point++) {
        prin();
        printf("process %d element : %d\n", point+1 , pages[point]);

        temp = search(pages[point]);
        if( temp == NULL )
            insert(pages[point]);
        else first(temp);
    }
    printf("\n\n Result : %d\n",LOST);
    getch();
    return;
}