[운영체제] 가상 메모리

가상 메모리란?

다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야 한다. 가상메모리는 프로세스 전체가 메모리 내에 올라오지 않더라고 실행이 가능하도록 하는 기법이며, 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다.

 

가상 메모리 개발 배경

실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 메모리 용량보다 큰 프로그램은 실행시킬 수 없었다. 또한, 여러 프로그램을 동시에 메모리에 올리기에는 용량의 한계와 페이지 교체 등의 성능 이슈가 발생하게 된다. 또한, 가끔만 사용되는 코드가 차지하는 메모리들을 확인할 수 있다는 점에서, 불필요하게 전체의 프로그램이 메모리에 올라와 있어야 하는 게 아니라는 것을 알 수 있다.

프로그램의 일부분만 메모리에 올릴 수 있다면

• 물리 메모리 크기에 제약받지 않게 된다.
• 더 많은 프로그램을 동시에 실행할 수 있게 된다. 이에 따라 응답시간은 유지되고, CPU 이용률과 처리율은 높아진다.
• swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행된다.

 

가상 메모리의 역할

가상 메모리는 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것이라 정리할 수 있다. 이로써 작은 메모리를 가지고도 얼마든지 큰 가상 메모리 공간을 프로그래머에게 제공할 수 있다.

 

가상 메모리의 기능

• 메모리 관리의 단순화 : 각 프로세스마다 가상메모리의 통일된 주소 공간을 배정할 수 있으므로 메모리 관리가 단순해진다.
• 메모리 용량 및 안정성 보장 : 한정된 공간의 램이 아닌 거의 무한한 가상메모리 공간을 배정함으로써 프로세스들끼리 메모리 침범이 일어날 여지를 크게 줄인다.

 

가상 주소 공간

• 한 프로세스가 메모리에 저장되는 논리적인 모습을 가상메모리에 구현한 공간이다. 프로세스가 요구하는 메모리 공간을 가상메모리에서 제공함으로써 현재 직접적으로 필요치 않은 메모리 공간은 실제 메모리에 올리지 않는 것으로 물리 메모리를 정햑할 수 있다.
• 예를 등어, 한 프로그램이 실행되며 논리 메모리로 100KB가 요구되었다며 하자. 하지만 실행까지의 필요한 메모리 공간(Heap 영역, Stack 영역, 코드, 데이터)의 합이 40KB라면, 실제 메모리에는 40KB만 올라가 있고, 나머지 60KB 만큼은 필요시에 물리 메모리에 요구한다고 이해할 수 있다.

 

프로세스간의 페이지 공유

• 가상메모리는 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 한다. 각 프로세스들은 공유 라이브러리를 자신의 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가 있는 물리 메모리 페이지들은 모든 프로세스에 공유되고 있다.
• 가상메모리는 프로세스들이 메모리를 공유하는 것을 가능하게 하고, 프로세스들은 공유 메모리로 통해 통신할 수 있다. 이 또한, 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있다.
• 가상메모리는 fork()를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 한다.

 

Demand Paging (요구 페이징)

프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라 하며, 가상 메모리 시스템에서 많이 사용된다. 그리고 가상 메모리는 대게 페이지로 관리된다. 요구 페이징을 사용하는 가상 메모리에서는 실행과정에서 필요해질 때 페이지들이 적재된다. 한 번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.

프로세스 내 개별 페이지들은 페이저(pager)에 의해 관리된다. 페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리에 읽어 옴으로써, 사용되지 않을 페이지를 가져오는 시간 낭비와 메모리 낭비를 줄일 수 있다.

 

페이지 교체

요구 페이징에서 언급된대로 프로그램 실행시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재)가 발생하게 되면, 원하는 페이지를 보조저장장치에서 가져오게 된다. 하지만, 만약 물리 메모리가 모두 사용중인 상황이라면, 페이지 교체가 이뤄줘야 한다. (또는 운영체제가 프로세스를 강제 종료하는 방법이 있다.)

기본적인 방법

물리 메모리가 모두 사용중인 상황에서의 메모리 교체 흐름이다.

1. 디스크에서 필요한 페이지의 위치를 찾는다.
2. 빈 페이지 프레임을 찾는다.
   • 페이지 교체 알고리즘을 통해 희생될(victim)페이지를 고른다.
   • 희생될 페이지를 디스크에 기록하고, 관련된 테이블을 수정한다.
3. 새롭게 비워진 페이지 테이블 내 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정한다.
4. 사용자 프로세스 재시작

페이지 교체 알고리즘

page reference string = "1 2 3 4 1 2 5 1 2 3 4 5" 라고 가정하자.  

 

1. OPT(Optimal Algorithm)

 

Optimal Algorithm은 가장 먼 미래에 참조되는 page를 대체하는 방법이다. 이 방법은 항상 최적의 결과를 갖는다.

다만, 미래의 참조를 모두 알고 있어야 하므로 실제로 사용하기는 어렵고, 다른 알고리즘의 성능에 대한 upper bound를 제공하는 역할을 한다.

Belady's optimal algorithm, OPT, MIN 등으로 불린다. 

 

ex) 4 frames 

빨간색은 page fault가 발생한 경우이고, 분홍색은 frame에 이미 존재해서 page fault가 발생하지 않은 경우이다. 

OPT는 항상 최적이므로 위와 같은 reference string이 주어진 경우 6번 미만의 page fault가 발생하는 방법은 존재하지 않는다. 

 

 

2. FIFO(First In First Out) Algorithm

 

FIFO 알고리즘은 제일 먼저 들어온 것을 먼저 내쫓는 방법이다. 미래를 모르는 경우에도 사용할 수 있다. 

모든 page가 평등하게 frame에 거주하며, 구현하기 쉽다는 장점이 있다. 다만, 어떤 page는 항상 필요할 수 있는데, 그런 경우에도 replace를 시킨다는 단점이 있다. 

 

그리고 FIFO는 frame이 늘어나도 page fault가 감소하지 않고 오히려 늘어나는 경우가 존재하는 Belady's anomaly 현상이 발생할 수 있다.

 

이처럼 일반적으로는 frame이 증가할수록 page fault가 감소하지만 특정 구간에서 오히려 증가하는 경우가 발생한다. 아래의 예시를 통해 이해해보자. 

 

3. LRU (Least Recently Used) Algorithm

 

LRU 알고리즘은 가장 오래전에 참조된 것을 지우는 방법이다.

Optimal에 근접한 방법이며, Belady's anomaly가 발생하지 않는다. 다만, 구현하기가 어렵고 접근되는 빈도를 고려하지 않는다는 단점이 있다. 

연결 리스트로 LRU를 구현하면 O(1)만에 page를 찾고 삽입할 수 있다. 제일 최근에 참조된 page를 가장 앞으로 옮기는 방식으로 연결 리스트를 구현하면 replace가 일어날 때 가장 뒤에 있는 page를 바꿔주면 된다. 

 

 

4. LFU(Least Frequently Used) Algorithm

 

LFU 알고리즘은 참조 횟수가 가장 적은 page를 지우는 방법이다.

LRU에 비해 장기적인 시간 규모를 보기 때문에 page의 인기도를 조금 더 정확히 반영할 수 있다. 하지만 최근성은 반영하지 못한다. 

최저 참조 횟수인 page가 2개 이상인 경우에는 LFU 알고리즘 자체에서는 임의로 page를 선정하는데, 성능 향상을 위해 가장 오래전에 참조된 page를 지우는 식으로 구현할 수도 있다. 

 

LFU를 LRU처럼 연결 리스트를 이용해서 구현하면 replace 될 page를 찾는데 O(n)의 시간이 걸리게 되어 느리다. 따라서 힙(heap)을 사용하면 최소 빈도를 갖는 page를 찾거나 삽입, 삭제하는데 O(logn)의 시간이 걸리게 되므로 훨씬 효율적이다. 

 

 

5. Second Chance Algorithm (Clock Algorithm)

 

LRU와 LFU 알고리즘이 실제로 paging system에서 사용 가능할까? 그렇지 않다.

LRU와 LFU의 알고리즘 구현에서 운영체제가 자료구조를 변경하고 유지하는 작업을 수행해야 하는데, 이미 메모리에 page가 올라가 있는 경우에는 CPU가 운영체제에 넘어가지 않는다. page fault가 발생해야 CPU가 운영체제에 넘어가고, 디스크에서 메모리로 page를 로드할 때 해당 page에 대한 정보를 얻고 갱신할 수 있다. 

따라서 운영체제가 참조한 지 오래되거나 참조 횟수가 적은 페이지를 정확하게 알 수 없다. 

 

이에 대한 해결법으로 Second Chance Algorithm을 사용한다. Clock Algorithm이라고도 불린다. 

 

Second Chance Algorithm은 LRU의 근사(approximation) 알고리즘으로, 최근에 참조되었는지 여부를 나타내는 Reference bit이라는 정보를 사용한다. 

 

Reference bit가 0인 것을 찾을 때까지 시계처럼 한 바퀴씩 포인터를 이동하다가 0인 것을 찾으면 해당 page를 교체하는 방식이다. 

만약 Reference bit가 1인 page를 만나면 0으로 바꿔주고, 한 바퀴 되돌아와서도(Second Chance) 여전히 0이면 해당 page를 교체한다. 다시 bit가 1로 바뀌어있다면 그만큼 자주 사용되는 page라는 의미인 것이다. 

 

 

이를 조금 더 개선한 방식으로 Enhanced Second Chance Algorithm이 있는데, 최근에 해당 page가 변경이 되었는지를 나타내는 Modified bit(dirty bit)가 추가된 것이다.

 

Modified bit가 1이라면 page가 변경되었기 때문에 교체를 하면 디스크에 해당 내용을 반영해야 한다. 즉, I/O 작업이 동반되므로 시간이 오래 걸린다.

따라서 "Reference bit == 0? → Modified bit == 0?" 순서로 우선순위를 가진다. 

 

 

참조 링크 :

https://rebro.kr/179

[운영체제(OS)] 9. 가상 메모리(Virtual Memory)