[운영체제] 가상기억장치 구현 기법 / 페이지 교체 알고리즘(FIFO, LRU 외 ... )

가상기억장치

: 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것으로, 용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법

• 프로그램을 여러 개의 작은 블록(보조기억장치와 주기억장치 간에 전송되는 데이터의 최소 단위) 단위로 나누어서 가상기억장치에 보관해 놓고, 프로그램 실행 시 요구되는 블록만(페이지 or 세그먼트) 주기억장치에 불연속적으로 할당하여 처리한다.
• 주기억장치의 용량보다 큰 프로그램을 실행하기 위해 사용한다.
• 주기억장치의 이용률과 다중 프로그래밍의 효율을 높일 수 있다.
• 가상기억장치에 저장된 프로그램을 실행하려면 가상기억장치의 주소를 주기억장치의 주소로 바꾸는 주소 변환 작업이 필요하다.

주소 변환 작업? 
가상기억장치에 있는 프로그램이 주기억장치에 적재되어 실행될 때 논리적인 가상주소를 물리적인 실기억주소로 변환하는것. 
주소 사상 / 주소 매핑 이라고도 한다. 
이 때 연속적인 가상 주소가 반드시 연속적인 실기억주소로 변환되지 않아도 된다.

• 블록 단위로 나누어 사용하므로 연속 할당 방식에서 발생할 수 있는 단편화를 해결할 수 있다.
• 가상기억장치의 일반적인 구현 방법에는 블록의 종류에 따라 페이지 기법과 세그먼테이션 기법으로 나눌 수 있다. 현재 대부분은 페이지를 사용한다.

---

페이징

: 가상기억장치에 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 나눠진 페이지를 페이지 프레임에 적재시켜 실행하는 기법이다. 요구되는 페이지만 메모리에 올린다는 의미에서 요구페이징이라고 한다.

페이지 : 프로그램을 일정한 크기로 나눈 단위
페이지 프레임 : 페이지 크기로 일정하게 나누어진 주기억장치의 단위

• 외부 단편화는 발생하지 않으나 내부 단편화는 발생할 수 있다.
• 주소 변환을 위해서 페이지의 위치 정보를 가지고 있는 페이지 맵 테이블이 필요하다.
• 페이지 맵 테이블 사용으로 비용이 증가되고, 처리 속도가 감소된다.

단편화 : 주기억장치의 분할된 영역에 프로그램이나 데이터를 할당할 경우, 
분할된 영역이 프로그램이나 데이터보다 작거나 커서 생기는 빈 기억 공간

내부 단편화 : 분할된 영역이 할당될 프로그램의 크기보다 크기 때문에 
프로그램이 할당된 후 사용되지 않고 남아 있는 빈 공간

외부 단편화 : 분할된 영역이 할당될  프로그램의 크기보다 작기 때문에 
프로그램이 할당될 수 없어 사용되지 않고 빈 공간으로 남아 있는 분할된 전체 영역

---

세그먼테이션

• 세그먼트 크기가 다 다르기 때문에 미리 분할할 수 없고, 메모리에 적재될 때 빈 공간을 찾아 할당한다.
• 기억장치의 사용자 관점을 보존하는 기억장치 관리 기법이다.
• 기억공간을 절약하기 위해서 세그먼테이션을 사용한다.
• 주소 변환을 위해서 세그먼트가 존재하는 위치 정보를 가지고 있는 세그먼트 맵 테이블이 필요하다.
• 세그먼트가 주기억장치에 적재될 때 다른 세그먼트에게 할당된 영역을 침범할 수 없으며, 이를 위해 기억장치 보호키가 필요하다.
• 내부 단편화는 발생하지 않으나 외부 단편화는 발생할 수 있다.

---

페이징 교체 알고리즘

: 페이지 부재(Page Fault)가 발생했을 때 가상기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데, 이 때 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법이다.

페이지 교체 알고리즘에는 OPT, FIFO, LRU, LFU, NUR, SCR 등이 있다.

Page Fault ? 
CPU가 액세스한 가상 페이지가 주기억장치에 없는 경우.
페이지 부재가 발생하면 해당 페이지를 디스크에서 주기억장치로 가져와야 한다.

 

1. OPT(OPTimal replacement, 최적 교체)

• OPT는 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법이다.
• 벨리이디가 제안한 것으로, 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘이다.
• 현실적으로 미래에 어떤 페이지를 사용할 지 알 수 없으므로 불가능한 방법이다.

 

2.FIFO(First In First Out)

• 각 페이지가 주기억장치에 적재될 때마다 그 때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법이다.
• 이해하기 쉽고, 프로그래밍 및 설계가 간단하다.

3. LRU(Least Recently Used)

• LRU는 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법이다.
• 각 페이지마다 counter 혹은 스택을 두어 현 시점에서 가장 오랫동안 사용하지 않은 페이지를 교체한다.
• 실제로 구현하는 데 비용이 많이 든다.

4. LFU(Least Frequently Used)

• 사용빈도가 가장 적은 페이지를 교체하는 기법이다.
• 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용된다.

 

5. NUR(Not Used Recently)

• LRU와 비슷한 알고리즘으로, 최근에 사용되지 않은 페이지를 교체하는 기법이다.
• 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로, LRU에서 나타나는 시간적인 오버헤드를 줄일 수 있다.
• 최근의 사용 여부를 확인하기 위해서 각 페이지마다 두 개의 비트, 즉 참조 비트와 변형 비트가 사용된다.

참조 비트 : 페이지가 호출되지 않았을 때 0, 페이지가 호출되었을 때 1
변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1

• 다음과 같이 참조 비트와 변형 비트의 값에 따라 교체될 페이지의 순서가 결정된다.

 

6. SCR(Second Chance Replacement, 2차 기회 교체)

: 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 기법의 단점을 보완하는 기법이다.

• FIFO + LRU 라고 생각하면 편하다.
• 페이지를 circular queue 형태로 두고 참조 비트를 두어 참조한 페이지의 비트를 1로 변경한다.
• 가장 오랫동안 사용하지 않았으면서 참조 비트가 0인 페이지를 교체하는 방식이다.