LFU 알고리즘을 구현한 c소스

본문내용

#include
#include

struct PAGE{
int valid; /* valid=1, invalid=0 */
int page_location; /* frame number */
};
struct PAGE *page;

struct FRAME{
int page_num;
int ref_count;
int last_ref_time;
int heap_i; /* heap index */
};
struct FRAME *frame;

int max = 0; /* maximum page number */
int *ref_string;
int cache_size; /* number of FRAMEs */
int string_length;
int cache_miss = 0; /* number of cache misses */
int *heap;

FILE *input_file;

void init();
void LFU();

void heapDown(int newNode, int n);
void heapUp(int n);


int main(int argc, char *argv[]){
int i;
cache_size = atoi(argv[1]);


--->(1) 비쥬얼 스튜디오에서 컴파일한 후에,

Project -> Setting -> Debug 메뉴로 들어가서

Program arguments에 100 20000 input.txt 와 같이 넣어주고

실행하면 됩니다.


(2) 명령프롬프트를 사용하는 경우,

실행파일과 input.txt 파일을 같은 디렉토리에 넣고,

명령프롬프트 창에서 cd 디렉토리명 명령을 통해 해당 디렉토리까지 내려가서

실행파일명(파일명.exe) 100 20000 input.txt 와 같이 테스트 해 볼 수 있습니다.

input.txt파일은 따로 올렸습니다.


(2) void heapUp(int heap[], int n)

: heap[n]에 새로운 값이 insert된 경우, heap[n]을 올바른 위치로 끌어올려 min heap 재구성

예를 들어, heap의 최대 원소가 10개(i는 0~9)인데,

현재 heap 내에는 원소가 7개밖에 없다면, 즉, heap[6]까지만 채워져있다면,

새로운 원소가 heap에 들어올 때는 heap[7]에 넣어주게 될 것임.

heapUp(heap, 7)을 호출하면 => heap[7]이 heap[]내에서 제자리를 찾아 올라가 min heap이 재구성됨

키워드

LFU,   알고리즘,   C소스,   운영체제