[OS] 페이징 알고리즘에 대해 알아보자

 이번년도에 꼭 취업에 성공하려는 취준생으로서 OS 공부를 다시 해야한다고 생각했어요. 주변 지인들과 이미 취업한 친구들로부터 엄청나게 들리는 OS 의 중요성...!

 

대학교 3학년데 OS 과목을 수강했지만 재미와 흥미가 떨어져서 그런지 머리속에 남는 게 많이 없었어요. 4학년 1학기 시스템 성능 분석 과목에서 페이징 알고리즘에 대해 발표를 할 기회가 있어서 이 기회에 다시 정리해보려고 합니다.

 

 

 

 

 

 

 

<용어 정리>

 

- 페이지 부재(Page fault)란? : 메모리에 적재된 페이지 중에 사용 페이지가 없을 때를 가리킨다. 시스템의 종류에 따라 약간 다를 수 있으나, 대체로는 빈 페이지가 하나도 없거나, 미리 정한 수보다 적을 때 발생한다.

 

- 지역성(Locality)란? : 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론이다.

 

- 전역 교체 vs 지역 교체 (Global vs Local)

 

	Global 교체	Local 교체
교체 프레임 대상	다른 프로세스에 속한 프레임을 포함한 모든 프레임이 대상	각 프로세스가 자기에게 할당된 프레임들 중에서만 교체될 희생자 선택
프레임 수 변화	변하지 않음	변할 수 있음
문제점	한 프로세스가 자신의 페이지 부재율을  완전히 조절 못함   (외부 환경에 의해 다르게 실행 될 수 있음)	잘 사용되지 않는 프레임이 있다면 낭비되는 현상이 발생함
종류	FIFO / LRU / Random / LFU 등	Working-Set / Page Fault Frequency 등

 

 

 

- 벨레이디의 모순(Belady's Anomaly)  : 프레임 수를 증가시켰는데도 불구하고 페이지 부재(Page fault) 가 증가하는 현상.

 

 

 

 

 

 

1. 페이지, 페이징(Page, Paging)

 

- 페이징 기법(Paging) 은 컴퓨터가 메인 메모리에서 사용하기 위해 2차 기억장치로부터 데이터를 저장하고 검색하는 메모리 관리 기법이다. 즉, 가상기억장치를 모두 같은 크기의 블록으로 편성하여 운용하는 기법이다.

 

- 이때의 일정한 크기를 가진 블록을 페이지(Page)라고 한다. 주소공간을 페이지 단위로 나누고 실제기억공간은 페이지 크기와 같은 프레임으로 나누어 사용한다.

 

 

 

 

***** 가상 메모리의 정의 *****

 

 가상 메모리 또는 가상 기억 장치는 RAM을 관리하는 방법의 하나로, 각 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식을 말한다

 

(1) 메인 메모리의 효율적 관리

- 메인 메모리를 캐시로 설정하여, 당장 사용하는 영역만 유지하고 쓰지 않는 데이터는 하드 디스크로 옮긴 뒤, 필요할 때만 데이터를 불러와 올리고 사용하지 않으면 내린다.

 

(2) 메모리 관리의 단순화

- 각 프로세스마다 가상메모리의 통일된 주소 공간을 배정할 수 있으므로 메모리 관리가 단순.

 

(3) 메모리 보장

- 한정된 램이 아닌 거의 무한정 가상메모리 공간을 배정함으로써 프로세스들끼리 메모리 침범이 일어날 여지를 제거.

 

********************************

 

 

2. 페이지 교체란?(Page replacement Algorithm)

 

- 페이지 교체 알고리즘은 메모리를 관리하는 운영체제에서 페이지 부재(Page Fault)가 발생했을 때 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다

 

- 페이지 교체 알고리즘에는 FIFO, Optimal, LRU, NUR, Second-Chance, Random 등이 있다.

 

 

==========================================================================================

 

저는 여기서 Random, FIFO, LRU, LFU 알고리즘을 소개하도록 하겠습니다.

 

 

 

 

3. 페이지 교체 알고리즘

 

 

① Random Algorithm

 

- Random 알고리즘은 어느 페이지도 교체될 수 있음을 의미하고 최악의 경우 바로 뒤에 호출될 페이지까지 교체될 수 있다.

- Random 알고리즘은 페이지 교체 결정을 신속히 내릴 수 있다는 장점이 있다.

- 말 그대로 무작정 하는 방식이라 거의 쓰이지 않는다.

 

< Belady의 모순 현상 발생 >

< Locality 가 없는 RS >

< Locality 가 있는 RS >

 

 

 결론 : 일반적으로 프레임 수가 늘어날수록 페이지 부재수는 줄어들지만 프레임수가 증가할 때 페이지 부재수도 증가하는 벨레이디의 모순 현상이 나타날 수도 있기 때문에 프레임 수가 늘어난다고 해서 항상 페이지 부재 수가 줄어드는 것은 아니다.

 

 

 

 

 

 

 

② FIFO(First-In First-out) Algorithm

 

- 가장 간단한 페이지 교체 알고리즘으로 가장 오랫동안 메인 메모리에 있었던 페이지를 교체

- 일반적인 경우에서 프레임수가 늘어날수록 페이지 부재수가 줄어든다.

- 프레임 수가 증가할 때 페이지 부재수도 증가하는 벨래디의 변이 현상이 나타날 수 있기 때문에 프레임 수가 늘어난다고 항상 페이지 부재 수가 줄어드는 것은 아니다.

- RS (Reference String) 에 지역성이 있다면 그렇지 않은 경우보다 상대적으로 페이지 부재 수가 줄어든다.

 

 

<FIFO 예시>

 

< 벨레이디의 모순 현상 >

 

< Locality 가 없는 RS >

 

< Locality 가 있는 RS >

 

 

 

 

 

③ LRU (Least Recently Used) Algorithm

 

- LRU 알고리즘은 교체할 페이지로서 가장 오랫동안 사용되지 않은 페이지를 선택한다.

- 최근의 상황이 가까운 미래에 대한 좋은 척도라는 직관적인 사실에 의존함.

- 각 페이지들이 호출될 때마다 그때의 시간을 테이블에 기억시킨다.

- 이 작업은 막대한 오버헤드를 초래하지만 이 부분을 개선한 LRU 알고리즘이 있어서 가장 많이 쓰이는 페이징 알고리즘이다.

 

 

< LRU 예시 >

< 벨레이디의 모순 현상이 발생하지 않는 LRU >

 

< Locality가 없는 RS >

 

< Locality가 있는 RS>

 

 

 

 

④ LFU (Least Frequently Used) Algorithm

 

- 각 페이지들이 얼마나 많이 사용되었는 지 확인하고 호출된 횟수가 가장 적은 페이지가 교체된다.

- 각 페이지마다 참조횟수 카운터가 있으며, 카운터 수가 가장 작은 페이지를 교체한다.

 

< 벨레이디의 모순 현상이 발생하지 않는 LFU >

 

< Locality 가 없는 RS >

 

< Locality 가 있는 RS >

 

 

 

4. 페이지 교체 알고리즘 비교

 

 

< 벨레이디의 모순이 나타나도록 RS를 구성 했을때 >

 

결론 : LRU 와 LFU 알고리즘에서는 벨레이디의 모순 현상이 나타나지 않았음을 알 수 있다.

 

< RS 를 랜덤한 수로 구성했을 때 -> 지역성 제거>

 

결론 : FIFO와 LRU 알고리즘은 페이지 부재율이 높지만 LFU 알고리즘이 상대적으로 페이지 부재율이 낮은 것을 확인할 수 있었다.

 

< RS가 지역성을 가지도록 한 경우>

 

결론 : LRU, FIFO 알고리즘이 상대적으로 페이지 부재 수가 적은 것을 알 수 있다.

 

 

 

 

5. 고찰

-  Random 을 제외한 페이지 교체 알고리즘에서는 일반적인 경우 프레임 수가 늘어날 수록 페이지 부재수는 줄어든다.

- FIFO, Random 알고리즘에서는 프레임 크기가 증가할 때 페이지부재 수도 증가하는 변이 현상이 나타났다.

- RS에 지역성이 있을 때에는 그렇지 않을 때보다 전체적으로 페이지 부재수가 더 낮은 것을 확인할 수 있었다.

- 변이 현상을 나타내는 FIFO, Random 알고리즘의 사용은 가급적 피하고 LRU, LFU 알고리즘의 사용이 효율적이다. 가장 많이 쓰는 알고리즘은 LRU 알고리즘이다.

 

 

 

 

 

 

 

P.S. 자료 참조를 허락해준 이준용, 김한솔 정말 고마워요!