운영체제 Page replacement (페이지 대체) 알고리즘이란?

2019. 5. 13. 21:46

안녕하세요? 허니입니다. 오늘은 운영체제에서 페이지 대체 알고리즘이 무엇이 있는지 그리고 그것과 관련하여 알아야 할 개념들에 대해 포스팅 하겠습니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

Page replacement (페이지 대체) 알고리즘

FIFO

Optimal

LRU (Least Recently Used)

Random

Page window

Thrashing

Inverted Page Table

Segmentation

어떤 기준으로 page out의 순서를 정하게 될까?

Page replacement (페이지 대체)
과거 메모리 용량이 적었을 때에는 페이지대체를 위해 많은 수고가 필요했지만 과거에 비해 실제메모리용량이 상당히 커진 지금에는 간단한 알고리즘으로 해결이 가능하다.

1) FIFO
FIFO는 먼저 쓰였던 페이지프레임을 먼저 page out 시키는 방법이다. 이 방법의 가장 큰 장점은 구현하기가 간단하다는 것이었으나 Locality(지역성)의 개념이 등장한 이후 환영받지 못했다. 현재 쓰이고 있는 페이지프레임은 당분간 계속해 쓰인다는 Locality(지역성)의 개념과는 FIFO가 반대되는 개념이었기 때문이다. 그러나 최근 멀티미디어는 또 다시 Locality(지역성)의 개념을 제외시키고 있다. 동영상지원이 가장 큰 관건인 멀티미디어는 영상이 지원되는 동안 한번 접근한 페이지프레임은 다시 접근하지 않기 때문이다. 계속해서 새로운 페이지 프레임을 접근하여 동영상을 완성해나가기 때문이다.

그림 50 FIFO

아이러니하게도 시스템이 발전해나가는 것은 항상 새로운 것을 받아들이는 것이 아니다. 과거에 쓸모없다고 버림받았던 개념들이 또다시 받아들여져 발전해 나가기도 한다. 그렇기에 우리는 현재 쓰이지 조차 않은 개념들을 배우는 게 아닐까. 여러분에 손에 의해 새롭게 환영받을 모습으로 태어날 그 날을 고대하며....

2) Optimal
이 방법은 앞으로 안 쓰일 페이지프레임을 page out 시키는 것이다. 그러나 이 방법은 이론상으로 존재할 뿐 실제로 적용되기는 불가능하다. 어떤 페이지프레임이 앞으로 쓰이지 않을지는 아무도 모르기 때문이다.

3) LRU (Least Recently Used)
LRU의 방법은 가장 오랫동안 사용되지 않았던 페이지 프레임을 page out 시키는 방법으로 Locality(지역성)를 전제로 현재 안 쓰이는 페이지프레임은 계속 안 쓰일 것이라는 생각을 바탕에 둔 것이다. 그렇다면 가장 최근에 안 쓰인 페이지프레임을 어떻게 확인할 것인가. LRU가 가능하기 위해선 이러한 문제가 해결되어야 한다. 가장 쉽게 생각할 수 있는 방법은 페이지프레임마다 시간을 기록하는 것이다.그러나 페이지프레임마다 최근 참조 시각을 기록하고 점검해 재정리하는 등의 작업을 하는데는 상당히 많은 시간이 필요하다. 초당 백 만 번 이상의 페이지프레임참조가 발생하는데 페이지프레임에 타임스태프를 찍어주는데 몇 천 분에 1초(ms)가 걸린다면 한마디로 배보다 배꼽이 더 큰 격이다. 이렇듯 페이지 프레임마다 시각을 찍는데 너무 많은 시간이 소요되는 것을 염려하던 시스템 설계자들은 리스트를 만드는 방법을 개발해 내었다. 바로 페이지 프레임마다 시각을 찍는 대신 리스트를 만들어 sorting을 함으로 최근 쓰인 페이지 프레임과 쓰이지 않은 페이지 프레임을 구분해 내는 것이다. 이러한 방법의 단점은 overhead가 발생한다는 것인데 최근 쓰였던 페이지 프레임을 빼내어 뒤로 올리는데 그리고 하나의 페이지 프레임이 빠진 앞뒤의 페이지 프레임을 붙이는 데에 대한 포인터 변화를 저장하기 위해 overhead가 쓰이는 것이다. 바로 포인터 갱신을 위한 overhead가 매우 심각하다는 것이 이 방법의 가장 큰 단점이다.

그림 51 LRU

4) Random
Locality(지역성)이 존재하지 않은 채, 전혀 예측할 수 없이 불규칙적으로 수행되는 프로그램의 경우 페이지프레임을 아무런 규칙없이 page out 시키는 것을 말한다.

하드웨어를 사용한 page out

앞서 page out 시킬 페이지 프레임을 검색하는 데는 많은 어려움이 존재하는 것을 배웠다. 바로 이러한 어려움의 해결을 하드웨어의 도움을 얻음으로써 더 이상 시간과 메모리를 낭비하지 않을 방법이 고안되었다. 하드웨어를 사용해 page out 시킬 때는 앞서 배운 PTE에 참조비트(reference bit)와 수정비트(modify bit)를 셋팅해 bit 값의 변화를 관찰해 page out이 실행되게 된다. 참조비트가 0이라는 것은 해당 페이지 프레임이 참조되지 않았다는 것을, 또한 참조비트가 1이라는 것은 해당 페이지프레임이 참조되었다는 것을 의미한다. 바로 PTE에 이러한 참조비트를 두고 MMU가 페이지프레임을 참조할 때마다 0인 참조비트를 1로 셋팅 시키는 것이다. 참조비트를 통해 해당 페이지프레임이 최근 사용되었는지 사용되지 않았는지에 관한 정보가 제공되므로 page out daemon은 PTE를 검사해 참조비트가 0인 페이지프레임을 page out 시키게 되는 것이다. page out daemon을 통해 계속해 페이지들을 돌며 레퍼런스가 0인 페이지를 스왑으로 내보내게 되는 것이다. 그렇다면 수정비트(dirty bit)가 의미하는 것은 무엇일까. 만약 수정비트가 0일 경우는 해당 페이지프레임의 내용이 수정된 적이 없음을 의미하고 또한 수정비트가 1일 경우 이것은 해당 페이지 프레임의 내용이 수정된 적이 있음을 의미한다. 참조비트가 0인 두 개의 페이지프레임이 존재할 때는 수정비트를 확인하여 수정비트가 0인 페이지프레임을 먼저 page out 하게 되는 것이다. 그 이유는 수정된 페이지프레임을 대체 시키려면 수정된 내용을 다시 저장해야하는 번거로움이 있기 때문이다. 정리해보면 참조비트 0, 수정비트 0인 페이지 프레임이 page out 1순위가 되고 그 다음은 참조비트 0, 수정비트 1인 페이지프레임, 그리고 참조비트 1, 수정비트 0인 페이지프레임의 순서로 page out이 되는 것이다. 참조비트 1, 수정비트 1인 페이지프레임은 최후의 순간까지 남게 되는 것이다.

Page window

그렇다면 과연 page out daemon은 실제 메모리 안에 페이지프레임들을 전부 다 검사하는 걸까. 그렇지는 않다. 바로 Page window의 범위 내에 존재하는 페이지 프레임을 검사하게 되는 것이다. 현재 사용중인 PTE가 차곡차곡 모이게 되면 page out daemon은 Page window 영역 내에 PTE을 스캔하게 되는 것이다.

Thrashing

만약 페이지 공간이 부족해 페이지프레임상에 A프로그램을 page out 시켰는데 바로 그 A프로그램을 다시 접근해야 하는 상황이 발생됐다고 생각해보자. 그래서 A프로그램을 page in 시키기 위해 또 다른 B프로그램을 page out 시켰는데 안타깝게도 B프로그램을 다시 접근해야 한다면 어떨까. 말로 표현하기도 복잡한 이런 상황이 발생하면 프로그램을 처리해야 하는 CPU는 자신의 본분을 다하지 못하고 page out, page in만을 시키다 말게 된다. 다시 말해 컴퓨터 시스템 성능에 심각한 저하를 가져오게 되는 것이다. 이렇듯 페이지 교환이 너무 자주 일어나는 상황을 Thrashing이라고 한다.

그림 52 Thrashing

Thrashing이 발생하는 원인은 메모리 부족과 swap space의 부족을 들 수 있다. 이렇듯 페이지교체전략이 효율적이지 못할 때는 Working set을 수정하여 page in이 발생하는 페이지들을 메모리에 유지될 수 있도록 해야 한다. 이러한 Thrashing을 방지하기 위해선 프로그램을 실행을 위한 메모리용량을 확보할 때 swap space도 함께 잡아주는 것이다. 보통 메모리 용량의 2-3배를 잡아 놓으면 swap space의 부족으로 시스템이 돌아가지 않는 어려움이 방지될 수 있다. 일반적인 경우 CPU의 이용률은 50%를 넘기가 어렵다. 그런데 컴퓨터 시스템상의 어느 부문에선가 병목 현상이 발생했다면 Thrashing을 점검해볼 필요가 있다. 메모리용량에 비해 사용자가 많을 때 메모리를 늘리거나 디스크를 늘리거나 스왑을 높이거나 사용자의 수를 줄이는 등의 판단도 이제부턴 여러분의 몫인 것이다.

Segmentation

우리는 앞서 메모리를 페이징 방식으로 나누는 것에 대하여 상세히 공부해 보았다. 기계적으로 페이지를 나누었던 것에 비해 세그먼테이션은 이미 프로그램이 논리적으로 나뉘어져 있는 3개의 Stack, Data segment, Text segment의 영역을 기본으로 메모리를 할당하는 것이다. 그렇게 되면 가상주소는 세그먼테이션과 내부주소(offset)을 통해 실제주소와 매핑되게 된다. 그러나 이런 방법이 크게 환영받지 못한 이유는 페이징방식에 비해 단편화가 크고 세그먼트가 지원되는 시스템에서만 사용이 가능하다는 점이었다. 또한 세그먼테이션과 페이징 방식의 혼합은 각각의 세그먼트를 4Kbyte의 페이지로 나누어 사용하게 된다. 보통 하나의 세그먼트가 64Kbyte의 크기를 갖게 되므로 16개의 페이지가
생기게 되는 것이다. 그러나 이 방법 또한 페이징방식에 비해 별다른 효과가 없는 것으로 알려지고 있다.

요점정리

Page replacement의 방법
1) FIFO: FIFO는 먼저 쓰였던 페이지프레임을 먼저 page out 시키는 방법이다.
2) Optimal: 이 방법은 앞으로 안 쓰일 페이지프레임을 page out 시키는 것을 말한다.
3) LRU (Least Recently Used): LRU의 방법은 가장 오랫동안 사용되지 않았던 페이지 프레임을 page out 시키는 방법으로 Locality(지역성)를 전제로 현재 안 쓰이는 페이지프레임은 계속 안 쓰일 것이라는 생각을 바탕에 둔 것이다.
4) Random: Locality(지역성)이 존재하지 않은 채 전혀 예측할 수 없이 불규칙적으로 수행되는 프로그램의 경우 아무런 규칙없이 page out 시키는 것을 말한다.

하드웨어를 사용한 page out
PTE에 참조비트를 두고 MMU가 페이지 프레임을 참조할 때마다 참조비트를 셋팅 시킨 후 page out daemon이 PTE를 검사해서 참조비트가 0인 페이지프레임을 page out 시키게 되는 것이다.

Thrashing이란
페이지 공간이 부족해 A프로그램을 page out 시켰는데 바로 그 A프로그램을 다시 접근해야 하는 상황이 발생했다. 그래서 A프로그램을 page in 시키기 위해 또 다른 B 프로그램을 page out 시켰는데 B프로그램에 다시 접근해야 하는 상황을 말한다.

목 차

운영체제를 시작하는 분들을 위해

운영체제의 역사와 구체적으로 어떤 일들을 수행하나요?

운영체제의 목표와 역할이 미래에도 계속 증대될까요?

운영체제를 이해하기 위해 필요한 기본 개념들은 무엇인가요?

운영체제 프로세스 생애주기(Process Lifecycle)는 무엇인가요?

운영체제 프로세스 관리(Process Management)는 어떻게 하나요?

운영체제 프로세스(Process)의 처리 속도는 어떻게 높일까?

운영체제 스레드(Thread)는 무엇인가요?

운영체제 스케줄링 (Scheduling)은 어떻게 하나요?

운영체제 스케줄링 알고리즘의 비교 기준이 있나요?

운영체제 프로세스 동기화가 무엇인가요?

운영체제에서 세마포어(Semaphore)란?