인의예지 서버(Ubuntu 18.04.5 LTS)에서 개발 및 테스트했고 C언어로 구현하였습니다. Make 명령어로 컴파일한 뒤 argument 없이 $./proj3으로 실행시킬 수 있습니다. input.txt를 실행파일과 동일한 디렉토리에 위치시켜야 합니다.
input 형식은 다음과 같습니다
N M W K
r1 r2 r3 ··· rk
- N은 process가 갖는 page 개수
- M은 할당 page frame 개수
- W는 window size
- K는 page reference string 길이
- "r1 r2 r3 ··· rk"는 page reference string
- Page 번호는 0번부터 시작
- main.c
- input.txt를 읽고 각각의 기법을 실행하는 소스코드입니다.
- pgrplc.c
- 각각의 management 기법을 구현한 소스코드입니다.
- pgrplc.h
- Makefile
- input.txt
Project 3는 Virtual Memory Management 기법을 구현하는 것이 목표입니다.
구현하는 기법은 다음과 같습니다.
- MIN
- LRU
- LFU
- WS
현재 시각을 기준으로 가장 먼 미래까지 reference되지 않을 page를 선택합니다.
본 프로젝트에서는 tie-breaking으로 가장 page 번호가 낮은 page를 선택합니다.
현재 시각을 기준으로 가장 오랫동안 reference되지 않은 page를 선택합니다.
현재 시각까지 가장 reference된 횟수가 적은 page를 선택합니다.
Tie-breaking으로 LRU 기법을 사용합니다.
현재 시각까지 window size만큼의 시간 동안에서 사용된 page들을 메모리에 유지합니다.
Variable Allocation 기법의 일종이므로 메모리에 load된 page의 개수는 달라질 수 있습니다.
int page_num //프로세스가 갖는 page 개수를 저장하는 변수입니다
int frame_num //메모리에 있는 page frame의 개수를 저장하는 변수입니다
int window_size //Working Set 기법에서 필요한 window size를 저장하는 변수입니다
int refstr_size //Page reference string의 길이를 저장하는 변수입니다int *refstr //Page reference string을 저장하는 배열입니다
int *fault //언제 page fault가 발생했는지 저장하는 배열입니다(Page fault가 발생하면 1, 아니면 0)
int *ref_count //LFU 기법에서 각각의 page가 몇 번 reference됐는지 저장하는 배열입니다
int *rcnt_ref //LFU 기법에서 tie-breaking을 위해 각각의 page가 언제 가장 최근에 reference됐는지 저장하는 배열입니다
int *P //Working Set에 들어가는 page 번호를 저장하는 배열입니다
int *Q //Working Set에서 빠지는 page 번호를 저장하는 배열입니다
int *working_set //Working Set에 들어간 page 번호를 저장하는 배열입니다int **mem_state //Memory State를 시간과 frame number에 따라 2차원으로 저장하는 배열입니다void execute(int frame_num, int refstr_size, int *refstr, int method);-
method에 따라 해당 값이 0이면 MIN, 1이면 LRU, 2이면 LFU를 실행하는 함수입니다.
-
현재 reference하려는 page가 메모리에 있는지 확인합니다.
- 있다면 memory state를 변경하지 않습니다.
- 없다면 비어있는 page frame이 있는지 확인합니다.
- 있다면 비어있는 곳에 reference하려는 page를 넣습니다.
- 없다면 method의 기법을 통해 특정 page를 replace합니다.
-
실행결과를 출력합니다.
void execute_ws(int page_num, int window_size, int refstr_size, int *refstr);- Working Set 기법을 실행하는 함수입니다.
- 현재 reference하려는 page가 메모리에 없다면 추가합니다.
- Working Set 기법을 통해 메모리에서 제거해야할 page를 제거합니다.
- 실행결과를 출력합니다.
void check_input(int page_num, int frame_num, int window_size, int refstr_size, int *refstr);-
input.txt를 통해 받은 input이 유효한지 검사하는 함수입니다.
-
Input이 유효하지 않을 경우 에러메시지를 출력하고 프로그램을 종료합니다.
int **create_arr(int frame_num, int refstr_size);- Memory state를 나타내는 2차원 배열을 만들고 초기화하는 함수입니다.
- 모든 값을 -1로 초기화합니다.
- 2차원 배열의 포인터를 반환합니다.
int isempty(int **mem_state, int frame_num, int time);- 현재 비어있는 page frame이 있는지 확인하는 함수입니다.
- 비어있는 frame이 있으면 해당 frame number를, 없으면 -1을 반환합니다.
int ishit(int **mem_state, int frame_num, int time, int ref);- 현재 reference하려는 page가 메모리에 있는지 확인하는 함수입니다.
- 메모리에 있으면 1을, 없으면 0을 반환합니다.
int min(int refstr_size, int frame_num, int time, int *refstr, int **mem_state);- MIN 기법을 구현한 함수입니다.
- Replace할 page number를 반환합니다.
int lru(int refstr_size, int frame_num, int time, int *refstr, int **mem_state);- LRU 기법을 구현한 함수입니다.
- Replace할 page number를 반환합니다.
int lfu(int refstr_size, int frame_num, int time, int *refstr, int **mem_state);- LFU 기법을 구현한 함수입니다.
- Replace할 page number를 반환합니다.
int ws(int refstr_size, int window_size, int page_num, int time, int *refstr, int **mem_state);- Working Set 기법을 구현한 함수입니다.
- Replace할 page가 있다면 해당 page의 page number를, 없다면 -1을 반환합니다.
void print_result(int refstr_size, int frame_num, int *refstr, int *fault, int *P, int *Q, int **mem_state)- 각 기법의 실행 결과를 출력하는 함수입니다.
- P가 NULL일 경우 P, Q는 출력하지 않습니다.
- P, Q는 Working Set 기법에서만 출력합니다.
