OS #9. 메모리 관리(Memory Management) Part2

지난 포스팅에 이어서 메모리 관리에 대해서 이어서 설명해 보도록 한다.

페이지 테이블 관리

페이지 테이블 관리가 복잡한 이유는 시스템에 여러 개의 프로세스가 존재하고, 프로세스마다 페이지 테이블이 하나씩 있기 때문이다. 메모리 관리자는 특정 프로세스가 실행될 때 마다 해당 페이지 테이블을 참조하여 가상 주소를 물리 주소로 변환하는 작업을 반복한다. 페이지 테이블은 메모리 관리자가 자주 사용하는 자료 구조이므로 필요시 빨리 접근할 수 있어야 한다. 따라서 페이지 테이블은 물리 메모리 영역 중 운영체제 영역의 일부에 모아놓는다. 

페이지 테이블의 수가 늘어나거나 페이지 테이블의 크기가 늘어나면 운영체제 영역이 그만큼 늘어나 사용자 영역이 줄어든다. 물리 메모리의 크기가 작을 때는 프로세스만 스왑 영역으로 옮겨지는 것이 아니라 페이지 테이블의 일부도 스왑 영역으로 옮겨진다. 스왑에 대해서는 뒤에서 자세하게 설명한다.

물리 메모리 페이지 테이블의 구조

프로세스는 페이지 테이블에 빠르게 접근하기 위해 레지스터가 존재한다. 각 프로세스가 메모리에 접근하려고 할 때 메모리 관리자는 페이지 테이블의 위치를 빠르게 파악해야 할 필요가 있기에, 각 페이지 테이블의 시작 주소를 페이지 테이블 기준 레지스터(Page Table Base Register, PTBR)에 보관한다. 페이지 테이블 기준 레지스터는 각 프로세스의 프로세스 제어 블록에 저장되는 데이터로, 물리 메모리 내에 피이지 테이블의 시작 주소를 가지고 있다.

페이징 방법에서 데이터로의 접근이 항상 두 번의 메모리 접근을 거쳐야 한다. 페이지 테이블에서 한 번, 물리 메모리 내에서 한 번. 이는 메모리 접근 속도를 크게 떨어트린다. 이를 해결하기 위한 방법이 Transition Look-aside Buffer(TLB)이다. 페이지 테이블을 이용해 변환된 주소를 TLB에 저장해 두면, 다음 접근 시 TLB에 저장된 값을 이용하여 빠르게 변환된 주소를 얻을 수 있다.

시스템이 크고 복잡해짐에 따라 요구하는 가상 주소 공간의 크기도 늘어나게 되면서, 페이지 테이블의 크기도 커지고 이로 인해 페이징이 잘 일어나지 못하는 문제가 발생하였다. 32bit CPU를 예를 들어 설명해 보면, 이 시스템의 페이지 사이즈가 4KB(2^12)일 경우, PTE는 1M개(4GB/4KB)가 생기게 된다. 하나의 PTE가 4 bytes씩만 하더라도 총 4MB를 각각의 프로세스가 물리 메모리에서 페이지 테이블 자체를 위해 사용해야 하는 것이다.

페이지 테이블을 작게 쪼개야 할 필요성이 생겼고 따라서 다 단계 페이지 테이블이 생겨나게 되었다. 예를 들어 2-level page table의 경우 Outer page table을 하나 두어, 페이지 테이블들을 가리키도록 하는 것이다.



32bit 가상 주소의 모양도 다음과 같이 바꾼다. p1은 페이지 번호이고, p2는 페이지 주소로 할당한다.

이렇게 되면 주소 이동 방식은 다음과 같이 나타난다. 주소 이동은 Outer 에서 Inward 방향으로 일어난다. 다 단계 페이지 테이블의 단점은 table walk이 아래와 같이 발생하여 소요 시간이 증가한다는 점이다.

페이지 테이블의 크기가 너무 커지면 프로세스가 실제로 사용할 수 있는 메모리 영역의 크기가 줄어들고, 프로세스만 스왑 영역으로 옮겨지는 것이 아니라 페이지 테이블의 일부도 스왑 영역으로 옮겨진다. 따라서 페이지 테이블 전체를 메모리에서 관리하느냐, 일부를 스왑 영역에서 관리하느냐에 따라 가상 주소를 물리 주소로 변환하는 방법이 달라진다. 이와 관련해서 다양한 테이블 매핑 방식이 있는데 다음과 같다.

• 직접 매핑 : 페이지 테이블 전체가 물리 메모리의 운영 체제 영역에 존재하는 방식.

• 연관 매핑 : 페이지 테이블 전체를 스왑 영역에서 관리하는 방식. 물리 메모리의 여유 공간이 작을 때 사용하는 방식으로, 모든 페이지 테이블을 저장 장치의 스왑 영역에 저장하고 그 중 일부만 물리 메모리에 가지고 있음. 페이지의 일부만 무작위로 가져옴. 주소 변환시 물리 메모리 내의 페이지 테이블을 다 검색해야 해서 시간 낭비가 발생할 수 있음.

• 직접-연관 매핑 : 연관 매핑의 문제를 개선한 방식. 모든 페이지 테이블을 스왑 영역에서 관리하고 일부만 물리 메모리로 가져오는 것은 동일. 페이지 테이블을 일정한 집합으로 자르고, 자른 덩어리 단위로 물리 메모리에 가져와서 시간을 단축.

• 역매핑 : 앞의 방식들과 반대로 테이블을 구성. 앞의 매핑은 페이지 번호를 기준으로 테이블을 구성하지만, 역매핑은 물리 메모리의 프레임 번호를 기준으로 테이블을 구성. 프로세스의 수와 상관없이 테이블은 하나만 존재하고, 테이블의 크기가 작아진다는 것이 장점.

역매핑에 대해서 조금 보충설명을 하면, 다단계 페이지 테이블에서 같은 페이지 테이블의 용량 증가 문제를 해결하기 위해 고안된 방법이다. 아무리 가상 메모리 공간을 크게 만들어도 물리 메모리 공간에는 한계가 있고, 64bit 주소 공간에 모든 물리 메모리가 매핑되어 있지 않는 문제가 발생했다. 하지만 반대로 모든 물리 메모리는 가상 메모리 페이지에 매핑될 확률이 높다.

기존 방식이 page 번호를 통해 frame 번호를 찾은 것과 반대로 역매핑은 역 페이지 테이블을 만들어서 CPU에서 참조하는 주소와 PID 조합으로 Page ID를 만들어 페이지 테이블에서 Page ID를 검색한다. Page ID를 발견하면 해당 frame 번호를 논리 주소 공간으로 매핑한다.

시스템 전체에 하나의 페이지 테이블만 둔다. 페이지 테이블 인덱스는 프레임 번호이고, 페이지 테이블 내용은 프로세스 번호(Process ID)와 페이지 번호이다. 페이지 테이블은 훨씬 적은 용량을 차지하지만, 테이블을 검색하는데 시간이 오래 걸린다는 단점이 있다.

---

요구 페이징 (Demand paging)

요구 페이징은 프로세스의 실행을 위한 모든 페이지를 메모리에 올리지 않고, 필요한 페이지의 요청이 발생할 때 메모리에 올리는 페이징 기법을 말한다. 목적은 메모리를 효율적으로 관리하고, 응답 속도를 향상 시키기 위함이다. Paging 서비스를 통해 한 프로세스에 필요한 페이지를 메모리와 2차 저장소 간에 이동시키는 방법을 사용한다. (참고로 요구 페이징과 반대로 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식은 캐시(Cache)이다. 캐시는 앞으로 필요할 것이라고 예상되는 부분을 고속의 캐시 메모리에 가져다 놓으므로써 시스템의 성능을 향상한다.) 이와 같이 사용자가 요구할 때 메모리에 올리는 방식을 게으른 스와퍼(lazy swapper)라고 한다.

요구 페이징의 장점이 많아서 사용을 하지만 분명 단점도 존재한다. 만약 참조하려는 페이지가 invalid하다면, 참조하려는 페이지가 실제 물리 메모리에 없으므로 페이지 부재(Page fault)가 발생할 수 있다. 

페이지 부재 (Page Fault)

가상 메모리의 페이지 테이블에는 페이지가 물리 메모리에 있는지, 스왑 영역에 있는지 표시하는 유효 비트를 사용한다. 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 경우를 페이지 부재라고 한다.

페이지 부재가 발생한 경우 프레임을 새로 할당 받아야 한다. 그리고 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다. 그리고 페이지 테이블을 재구성 하고, 프로세스의 작업을 재시작한다. 이러한 작업은 Page Fault Handler에서 수행한다.

---

페이지 교체(Page Replacement)

프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재가 발생한다. 페이지 부재가 발생하면 스왑 영역에서 페이지를 메모리로 가져오는데, 만약 메모리가 꽉 찼다면(Over-allocating of memory) 메모리에 있는 페이지를 스왑 영역으로 내보내야 한다. 물리 메모리에 위치한 페이지를 디스크에 저장하고, 요구된 페이지가 해당 프레임을 할당 받도록 하는 방법을 페이지 교체라고 한다. 

페이지 부재에 페이지 교체를 추가하여 메모리 과다 할당 상태를 해결하는 순서는 다음과 같다.

1. 디스크에서 요구된 페이지를 찾음

2. 물리 메모리에서 Free frame을 찾음

   • Free frame이 있다면 사용

   • 없다면, 페이지 교체 알고리즘 사용하여 교체할 프레임 선택

   • 교체할 프레임을 디스크에 저장하고, 페이지 테이블, 프레임 테이블 변경

3. 요구된 페이지를 2에서 선택된 Free frame으로 읽어 들이고 해당 페이지를 테이블, 프레임 테이블을 적절하게 변경

4. 유저 프로세스 재시작

페이지 교체를 할 때 고려해야 할 사항들은 다음과 같은 것들이 있다. 페이지 교체 알고리즘은 모두 페이지 교체에 의한 I/O 작업 수행 횟수를 최대한 줄이려는 목적을 가지고 있다. 

• 각각의 유저 프로세스에게 어떻게 프레임을 분배해 줄 것인가?

• 페이지 교체가 필요할 때 어떻게 교체 페이지를 고를 것인가?

• 어떻게 하면 가장 낮는 page fault 발생 빈도를 가지게 할 수 있는가?

그러면 지금부터 페이지 교체 알고리즘을 하나씩 살펴보도록 하자.

최적 알고리즘(Optimal algorithm)

최적 알고리즘은 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다. 메모리가 앞으로 사용하지 않을 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정한다. 아래의 예제를 보면 4번째 메모리 접근 순서에서 2가 들어오는데, 이 때를 기준으로 0은 5번째에서, 1은 14번째에서 7은 18번째에서 사용되므로 7을 2로 바꾼다. 이는 모든 알고리즘 중 가장 낮은 page fault를 가지는 최적의 알고리즘이다. 하지만 앞으로 어떤 페이지가 사용될지는 미리 알 수가 없다. 따라서 실제로 구현할 수는 없다.

FIFO 알고리즘

선입선출(FIFO, First In First Out) 페이지 교체 알고리즘은 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상으로 선정하여 스왑 영역으로 쫓아낸다. 이 알고리즘은 큐로 구현된다. 메모리의 맨 위에 있는 페이지는 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래에 삽입된다. 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들이 위쪽으로 이동하며, 새로운 페이지가 남은 공간에 들어온다. 이 알고리즘은 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어진다는 단점이 있다.

SCR 알고리즘

SCR(Second Chance Replacement) 알고리즘은 FIFO의 단점을 보완하기 위해 고안되었다. 큐를 사용하는 점은 FIFO와 동일하나, 차이점이 있다면 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외한다는 점이다. 따라서 오랫동안 주 기억 장치에 존재하던 페이지들 중에서 자주 사용되는 페이지의 교체를 방지한다. 페이지는 참조 비트(Reference bit)를 통해서 관리한다.

시계 알고리즘

시계 알고리즘 역시 FIFO의 변형 알고리즘으로 SCR의 발전된 형태이다. 시계 알고리즘은 원형 큐를 사용한다. 여기서는 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 바닥으로 내려가면 다음번에는 다시 큐의 처음을 가리키게 된다. 이 알고리즘도 참조 비트를 사용한다. 참조 비트의 초기값은 0이고, 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경된다.

LFU 알고리즘

최소 빈도 사용(LFU, Least Frequently Used) 알고리즘은 사용 빈도가 가장 적은 페이지를 교체하는 알고리즘이다. 현재 프레임에 있는 페이지마다 그동안 사용했던 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다. 이 알고리즘의 단점은 페이지 접근 횟수를 표시하는데 추가적인 공간이 필요하므로 그만큼 메모리가 낭비된다는 점이다.

NRU 알고리즘

최근 미사용 (NRU, Not Recently Used) 페이지 교체 알고리즘은 최근에 사용하지 않은 페이지를 교체하는 알고리즘이다. 페이지마다 참조 비트와 변형 비트를 두어서 관리한다. 따라서 페이지마다 추가되는 메모리 공간이 2비트이다. 참조 비트는 PTE의 접근 비트를 가리키는데, 최초로 프레임에 로드 될 때와 페이지가 참조 되었을 때 마다 1로 세팅되며 일정 주기마다 0으로 리셋된다. 변형 비트는 PTE의 변경 비트를 가리키는데, 최초로 프레임에 로드될 때는 0이고 페이지의 내용이 바뀔 때 마다 1로 세팅이 된다.

LRU 알고리즘

최근 최소 사용(LRU, Least Recently Used) 페이지 교체 알고리즘은 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 넘긴다. 즉, 최근에 사용된 페이지는 놔두고, 가장 오래 전에 사용된 페이지를 대상 페이지로 선정한다는 의미이다. 페이지 접근 시간에 따라서 또는 카운터나 참조 비트를 사용하여 구현하는 방법 등이 있다.

---

스와핑(Swapping)

스와핑은 페이지 아웃으로도 메모리 부족을 해결하지 못할 경우에 필요한 기법이다. Swap out 대상이 된 프로세스 전체를 2차 저장소로 보낸다. 이렇게 페이지 아웃이나 스와핑에 사용되는 2차 저장소(secondary storage, backing store)를 swap 영역이라고 한다.

물리 메모리의 부족으로 스와핑이 일어나는 모습

---

스레싱(Thrashing)

여러 개의 프로그램을 한 번에 실행할 때, 하드디스크와의 입출력이 계속되어 프로그램이 정지한 것 같은 현상이 발생한다. 처음에는 프로그램이 정상적으로 메모리에 올라오지만 메모리가 꽉 찬 후에는 새로운 프로그램을 메모리에 올리기 위해 기존 프로그램을 스왑 영역으로 옮기는 횟수가 잦아지기 때문이다. 이와 같이 하드디스크에 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태를 스레싱이라고 한다. 

스레싱은 메모리가 일정할 경우 멀티 프로그램의 수와 밀접한 관계가 있다. 동시에 실행하는 프로그램의 수를 멀티프로그래밍 정도라고 하는데, 멀티프로그래밍 정도가 너무 높으면 스레싱이 발생한다. 아래 그래프에서 CPU 활용률이 증가하다 꺾이는 지점을 스레싱 발생 지점이라고 한다. 

스레싱은 각 프로세스에 프레임을 할당하는 문제와도 연관된다. 실행 중인 여러 프로세스에 프레임을 얼마나 나누어주느냐에 따라 시스템의 성능이 달라진다. 프로세스에 프레임을 할당하는 방식은 정적 할당과 동적 할당으로 나뉜다. 정적 할당은 프로세스의 실행 초기에 프레임을 나누어 준 후 그 크기를 고정하는 것으로 균등 할당과 비례 할당이 있다. 정적 할당 방식은 프로세스를 실행하는 동안 메모리 요구를 반영하지 못한다는 단점이 있어서 이렇게 시시각각 변하는 요청을 수용하는 방식이 동적 할당 방식이다.

---

참고자료

1. 고려대학교 유혁 교수님 운영체제(COSE341) 수업 자료
2. <Operating System Concepts> 9th ed. by A. Silberschatz
3. <쉽게 배우는 운영체제> 조성호 저, 한빛아카데미