운영체제 LRU (Least Recently Used) 알고리즘 구현 과제

소개

LRU (Least Recently Used) 알고리즘 구현 과제입니다.

전체 소스는 V. CODE(전체) 목차에서 보실 수 있습니다.

목차

1. 서론

2. Flow
1) Node 구조체 정의
2) List 구조체 정의
3) LRU
4) 시스템 시뮬레이션

3. Code (설명)

4. 실행 결과

5. Code (전체)

본문내용

- 해당 프로그램은 C로 작성됨
- 해당 프로그램은 Doubly linked list로 구현함
- 해당 프로그램의 메모리 페이지 개수를 상수로 정의함
- 해당 프로그램은 pagenum.txt 파일에서 참조된 페이지 번호를 읽어와 LRU를 구현함

II. Flow
1. Node 구조체 정의
data : txt파일에 존재하는 페이지 번호를 data로 받음
next : 다음 노드를 가리키는 포인터 변수
prev : 이전 노드를 가리키는 포인터 변수

2. List 구조체 정의
head : 연결 리스트의 시작 노드
tail : 연결 리스트의 끝 노드

3. LRU (Least Recently Used)
Page Fault 발생 시 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘
(Page fault : CPU가 필요로 하는 데이터가 메모리에 올라와 있지않은 현상)
1) 페이지를 새로 참조할 때마다 연결리스트의 맨 앞에 페이지 번호를 추가
2) 연결된 페이지의 리스트가 메모리의 최대 페이지 개수보다 많아지면, 가장 오래시간 참조되지 않은 페이지 삭제 후 참조할 페이지 번호 추가

참고자료

· 없음