LRU 구현하기

LRU

메모리 관리에 사용되는 페이징 시스템에서 사용되는 알고리즘 입니다.

 

여기서 잠깐! 페이징 시스템이란?

비연속적인 메모리 할당 정책을 이용하는 메모리 관리 이론입니다.

여기서 잠깐! 비연속적인 메모리 할당 정책 이란?

프로그램이 실행이 되고 프로세스에게 실행에 필요한 메모리가 아래와 같이 꼭 할당되어야 합니다.

효율적으로 메모리를 할당하기 위한 방법은 연속적인 메모리 할당 정책과 비연속적인 메모리 할당 정책이 있습니다.

페이징 시스템은 실제 저장되는 메모리 주소를 저장하고 있는 테이블을 만들어 관리하는 방식으로 아래 logical address을 따라 page에 접근하고 page에 저장된 실제 physical adress를 통해 실제 메모리에 접근할 수 있게 됩니다.

ㅗㄹ

따라서 비연속적인 메모리 할당 정책에 속합니다. 

 

아무튼 여차저차 자세한 것은 나중에 다루고 프로세스가 참조하려는 페이지가 메모리 안에 없다면

페이지 폴트라는 것을 발생 시켜서 해당 부분을 유효하게 만들어주어야 합니다.

이 페이지 폴트가 자주 발생되면 성능이 저하되기 때문에 이 것을 감소시키는 알고리즘이 필요합니다.

그 중에 많이 사용되는 LRU를 알아보도록 하겠습니다.

 

reference string은 요청하는 page의 번호이며 page frames은 페이지에 신속히 접근하기 위한 캐쉬입니다.

프로세스가 특정 메모리에 접근하기 위해 페이지를 요청했을 때 빈 page frames에 페이지를 저장합니다.

만일 요청한 페이지가 캐쉬에 있다면 바로 불러올 수 있습니다. 없다면 직접 디스크에서 읽어와야 합니다.

그리고 위 예시는 3개의 캐쉬로 이루어져 있는데 캐쉬가 꽉 차 있을 때 캐쉬에 없는 페이지를 참조한다면

가장 오랫동안 참조하지 않은 페이지를 삭제하고 참조한 페이지를 저장해줍니다.

 

구현

이중 연결 리스트를 이용한 큐로 구현을 해보도록 하겠다.

 

이중 연결리스트 큐를 이용한 시나리오를 그려보았다.

러프하게 구현할 것을 적어보았다.

 

필요한 헤더 파일과 상수 큐의 길이와 페이지의 길이를 정의.

 

구현에 사용할 구조체이다.

Node는 이중 연결리스트이며 이전 노드와 다음 노드를 가르키는 포인터 변수와 페이지 번호를 담는 변수를 가지고 있습니다.

Queue는 현재 가지고 있는 노드의 개수를 담는 count, queueMaxlen, 가장 최근에 큐에 들어온 것을 노드를 가르키는 rear, 그리고 첫번째 노드를 의미하는 first. 그리고 검색에 이용할 변수 temp를 만들어 주었다. 

 

메인 함수이다.

우선 텍스트 파일로 입력을 받는다.

텍스트 파일은 위와 같이 입력이 되어 있다.

그리고 미리 상수로 정해둔 큐의 길이와 페이지의 길이를 입력 받는 함수를 각각 실행한다.

우선 createQueue는 

큐 타입 변수를 동적할당하고 멤버 변수들을 초기화한 뒤 해당 변수를 리턴하는 함수이다.

createPage도 비슷하다.

Page 타입 변수를 동적할당하고 멤버 변수들을 초기화 해준다.

그 다음 등장하는 함수가 ReferencePage이다. 해당 큐와 페이지, 그리고 참조할 페이지 번호를 패러미터로 받는다.

우선 특정 페이지의 변수가 있는지 확인합니다. NULL이라면 해당 페이지가 큐에 없음을 의미합니다.

그렇다면 해당 페이지의 노드를 만드는 함수 EnQueue를 실행합니다.

Enqueue 함수를 잠시 설명하고 마저 설명하겠습니다.

우선 큐가 가득차있는지 확인합니다. 큐가 가득차있다면 first 노드를 제거해줍니다. 해당 노드를 매개변수로 받는 deQueue 함수를 실행합니다.

deQueue 함수를 잠시 설명하고 다시 돌아와서 설명하겠습니다.

큐가 비어있다면 제거할 필요가 없으니 함수를 종료시킵니다.

q의 rear와 first가 같다면 1에 노드가 하나밖에 없기 때문에 rear를 NULL로 만들어줍니다.

항상 q의 first를 제거하기 때문에 제거하기 전에 first의 이전 노드를 first로 만들어 주고

해당 노드가 삭제 될 것이기 때문에 q의 first의 next 변수를 null로 초기화해주고 temp를 free로 동적할당을 해제해줍니다.

 

다시 Enqueue로 돌아와서 새로운 노드 temp를 만들어준 뒤 다음노드로 rear로 지정합니다.

만일 큐가 비어있었다면 노드가 하나 밖에 없는 상황이기 때문에 first와 rear에 temp를 저장합니다.

만일 두개 이상이라면 rear를 temp로 만들어줍니다. 이상입니다.

 

다시 ReferencePage로 돌아와서 추가하려는 페이지가 큐에 있다면!

또한 추가하려는 특정 페이지가 이미 rear이라면 따로 순서를 바꿔줄 필요가 없기 때문에 rear가 아닌 경우에만 순서를 조정해줍니다. 순서를 조정해줍니다. 요청한 특정 페이지 노드의 이전 노드와 다음노드를 연결해줍니다.

만일 first 라면 이전 노드를 first로 만들어주고 이전 노드의 다음 노드를 NULL로 만들어 줍니다.

요청한  특정 페이지를 가장 앞으로 만들어주고 rear변수에 저장합니다.

 

그러면 LRU 알고리즘 완성!

 

#include <stdio.h>
#include <stdlib.h>
#define QueueLen 3
#define Pagelen 10

typedef struct Node {
    struct Node* prev, * next;
    unsigned pageNumber; 
} Node;
    

typedef struct Queue {
    unsigned count; 
    unsigned queueMaxlen; 
    Node* rear, * first;
    Node* temp;
} Queue;


typedef struct Page {
    int capacity; 
    Node** array;
} Page;


Node* newNode(unsigned pageNumber)
{

    Node* temp = (Node*)malloc(sizeof(Node));
    temp->pageNumber = pageNumber;

    temp->prev = temp->next = NULL;

    return temp;
}

Queue* createQueue(int queueMaxlen)
{
    Queue* queue = (Queue*)malloc(sizeof(Queue));

    queue->count = 0;
    queue->rear = queue->first = queue->temp =  NULL;


    queue->queueMaxlen = queueMaxlen;

    return queue;
}

Page* createPage(int capacity)
{

    Page* page = (Page*)malloc(sizeof(Page));
    page->capacity = capacity;


    page->array = (Node**)malloc(page->capacity * sizeof(Node*));


    int i;
    for (i = 0; i < page->capacity; ++i)
        page->array[i] = NULL;

    return page;
}

int IsQueueFull(Queue* queue)
{
    return queue->count == queue->queueMaxlen;
}


int isQueueEmpty(Queue* queue)
{
    return queue->first == NULL;
}


void deQueue(Queue* queue)
{
    if (isQueueEmpty(queue))
        return;

    
    if (queue->rear == queue->first)
        queue->rear = NULL;
    queue->temp = queue->rear;

    
    Node* temp = queue->first;
    queue->first = queue->first->prev;

    if (queue->first)
        queue->first->next = NULL;

    free(temp);

    
    queue->count--;
}


void Enqueue(Queue* queue, Page* page, unsigned pageNumber)
{
    
    if (IsQueueFull(queue)) {
        
        page->array[queue->first->pageNumber] = NULL;
        deQueue(queue);
    }

    
    Node* temp = newNode(pageNumber);
    temp->next = queue->rear;


    if (isQueueEmpty(queue))
        queue->first = queue->rear = temp;
    else 
    {
        queue->rear->prev = temp;
        queue->rear = temp;
    }


    page->array[pageNumber] = temp;
    queue->temp = queue->rear;
    queue->count++;
}

void ReferencePage(Queue* queue, Page* page, unsigned pageNumber)
{
    Node* reqPage = page->array[pageNumber];

    if (reqPage == NULL) {
        Enqueue(queue, page, pageNumber);
        printf("[Miss] ");
    }
    else if (reqPage != queue->rear) {
     
        reqPage->prev->next = reqPage->next;
        if (reqPage->next)
            reqPage->next->prev = reqPage->prev;

     
        if (reqPage == queue->first) {
            queue->first = reqPage->prev;
            queue->first->next = NULL;
        }

     
        reqPage->next = queue->rear;
        reqPage->prev = NULL;

        reqPage->next->prev = reqPage;

        queue->rear = reqPage;
        printf("[Hit ]");
    }
    else {
        printf("[Hit ]");
    }
}

void printQueue(Node* temp) {

    printf("%d ", temp->pageNumber);
    if (temp->next) {
        temp = temp->next;
        printQueue(temp);
    }
    
}


int main()
{   
    char txt[30] = {0,};
    FILE* fp;
    fopen_s(&fp,"C:\\Users\\jangyunsik\\Desktop\\LRU.txt", "r");
    fread(txt, 1, sizeof(txt), fp);
    fclose(fp);

    printf("%s \n", txt);

    Queue* q = createQueue(QueueLen);

    Page* page = createPage(Pagelen);


    
    for (int i = 0; txt[i]; i++) {
        if (txt[i] == '\0') {
            break;
        }
        int n;
        n = txt[i] - '0';

        printf("[put %d] ", n);
        ReferencePage(q, page, n);
        printQueue(q->rear);
        printf("\n");

    }


    return 0;
}​

실행 결과 :