목차
- 가상 메모리란?
- 가상 메모리 구현 방법 : Demand Paging
- 페이지 교체 알고리즘
- FIFO 알고리즘
- Optimal 알고리즘
- LRU 알고리즘
- LFU 알고리즘
- Second-Change 알고리즘 (= Clock 알고리즘)
- 스레싱이란?
- 스레싱 해결 방법
1. 가상 메모리란?
가상 메모리는 메모리보다 크기가 큰 프로세스를 실행시킬 수 있기 위해 나온 기술이다. 프로세스를 실행할 때 실행에 필요한 코드나 데이터만 메모리에 로드하고, 나머지는 디스크에 저장해 두어 작업한다. 이로써 프로그램 전체가 메모리에 로드되어 수행하는 것처럼 만들고, 메모리가 훨씬 더 큰 용량을 가진 것처럼 보이게 한다.
2. Demand Paging
가상 메모리 구현 방법 중 하나인 Demand Paging은 실행에 필요한 페이지 영역만 메모리에 올려 동작하도록 한다. 프로세스를 디스크에서 메모리로 이동시키는 작업을 swap-in, 메모리에서 디스크로 프로세스를 이동시키는 작업을 swap-out이라고 하는데, Demand Paging은 프로세스가 아닌 페이징을 이동시킨다.
프로세스가 실행되면 MMU는 실시간으로 페이지 테이블을 확인해, 필요한 페이지가 메모리에 올라가 있는지 확인한다. 이때 valid bit가 v라면 해당 페이지가 메모리에 올라가 있는 상태이고, i라면 메모리에 올라가 있지 않는 상태인 것이다. valid bit가 i일 경우, 즉 메모리에 페이지가 올라와있지 않았다면 Page Fault Exception을 발생시킨다.
- valid bit = v (valid) : 페이지가 메모리에 적재되어 있음
- valid bit = i (invalid) : 페이지가 메모리에 적재되어 있지 않음
3. 페이지 교체 알고리즘
Page Fault Exception이 발생하면 CPU가 TLB를 탐색하고, 메모리에서 페이지 주소를 가지고 오고, 메모리에 페이지를 로드하는 과정을 거치기 때문에, 오버헤드가 발생한다. 따라서 메모리에 어떤 페이지를 올려둘 것인가는 성능에 아주 큰 영향을 끼치게 된다. 그럼 Page Fault 발생을 줄일 수 있는 알고리즘은 무엇일까?
1) FIFO Algorithm
First In First Out의 약자로, 가장 오래된 페이지를 교체하는 방식이다. FIFO 방식은 가장 최근에 참조된 페이지를 고려하지 않기 때문에, 프레임 개수를 늘려도 오히려 Page Fault가 늘어나는 Belady's anomaly(벨라디의 모순)이 발생한다.
2) Optimal Algorithm
앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방식이다. Page Fault 발생 가능성이 가장 낮은 알고리즘이다. 하지만 CPU가 추후에 어떤 페이지를 요청할지 알 수 없기 때문에, 굉장히 이상적이며 구현이 불가능하다.
3) LRU Algorithm
Least Recent Used의 약자로, 가장 오랫동안 사용되지 않는 페이지를 교체하는 방식이다. 참조된 시간을 저장하기 위해 counter나 stack을 두어야 하며, 페이지 교체가 이뤄질 때마다 모든 counter와 stack을 탐색해야 하므로 오버헤드가 발생한다. 또한, 구현이 어렵고 발생 빈도를 고려하지 않는 단점을 가진다.
4) LFU Algorithm
Lastest Frequently Used의 약자로, 가장 적게 교체된 페이지를 교체하는 방식이다. 페이지 접근 빈도를 카운팅해야 하기 때문에 LRU 알고리즘과 마찬가지로 메모리가 낭비된다는 단점을 가진다.
4) Second-Chance Algorithm (Clock Algorhtm)
LRU 알고리즘에서 오버헤드를 개선한 FIFO 기반의 알고리즘이다. counter나 stack을 사용하지 않고, 한 개의 참조 비트를 통해 참조되는 페이지의 비트를 1로 설정한다. 시계처럼 한 바퀴씩 포인터를 이동하면서 참조 비트가 0인 것을 찾으면 페이지를 교체시키는 방식이다.
4. 스레싱이란
스레싱이란 Page Fault가 자주 발생하여 CPU 실행 시간보다 페이지 교체를 위한 I/O 처리하는 시간이 더 많아지는 것을 의미한다. 가상 메모리는 실제 메모리의 용량보다 더 많은 용량을 사용할 수 있는 것처럼 보이며 효율적이다.
하지만 CPU가 많은 일을 처리할 수 있도록 점점 많은 프로세스가 메모리에 올라간다면, 프로세스 당 할당받는 프레임의 크기는 줄어들게 된다. 메모리 공간을 조금만 할당받아 디스크에서 데이터를 검색해야 하는 Page Fault가 증가하게 되고, 스와핑 과정이 증가하게 되면서 CPU 효율은 떨어지게 된다.
즉, 메모리에 올라간 프로세스 수가 점점 많아짐 -> 메모리 내 여유 공간이 줄어들어 프로세스 당 할당받은 프레임 크기가 줄어듦 -> 디스크 검색인 Page Fault 증가 -> 스와핑 과정 증가 -> CPU 효율 저하 과정이 일어나는 것이다.
5. 스레싱 해결 방법
스레싱 문제를 해결하기보다는 스레싱 발생 자체를 방지해야 한다. 메모리에 올라가는 프로세스의 수를 제한해 메모리의 여유 공간을 확보할 수 있도록 도와주는 알고리즘이 2가지 존재한다. 설명에 앞서 관련 용어부터 정리하고 들어가자.
1) Working-Set Model
: 프로세스가 일정 기간 동안 원활히 수행되기 위해 한번에 올라가야 하는 페이지들의 집합을 Working Set이라고 한다. Working-Set Model은 Working Set을 포함할 수 있는 충분한 프레임을 할당받았을 때 작업이 수행되고, 아닐 경우 모든 프레임을 모두 반납해 메모리에서 디스크로 swap-out 한다.
2) Page-Fault Frequency Scheme
: Page Fault의 상한 값과 하한 값을 두고, 상한 값을 넘기면 프로세스 당 할당되는 프레임의 수를 늘리고, 하한 값보다 낮아지면 프로세스 당 할당되는 프레임의 수를 줄인다.
댓글