가상 메모리: Paging과 Segmentation, TLB

가상 메모리

가상 메모리(Virtual Memory)는 각 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식이며, 비연속 할당(non-continuous allocation)으로 구현한다.

• 사용자 프로그램을 여러 개의 block으로 분할한다.
• 실행 시 필요한 block만 메모리에 적재하고, 나머지는 swap device에 둔다.

block을 나누는 방식에 따라 Paging, Segmentation, Hybrid paging/segmentation으로 구분한다.

가상 메모리를 사용할 수 있는 이유는 두 가지다. MMU가 가상 주소를 물리 주소로 변환해 주고, 매핑 테이블에 각 block의 메모리 적재 여부가 표시되어 있기 때문이다.

Address Mapping

가상 주소(virtual address)를 실제 주소(real address)로 변환하는 과정이다.

• Virtual address (logical address): 연속된 메모리 할당을 가정한 주소
• Real address: 실제 메모리에 적재된 주소

프로세스는 프로그램 전체가 메모리에 연속적으로 적재되어 있다고 가정하고 실행한다. 변환은 MMU(Memory Management Unit) 가 맡는다. MMU는 CPU의 메모리 접근을 관리하는 하드웨어로, 주소 변환과 함께 메모리 보호 등의 역할을 담당한다.

Block Mapping

프로그램을 block 단위로 분할하고, block마다 주소 매핑 정보를 유지한다. 가상 주소는 v = (b, d)로 표현한다.

• b: block number
• d: block 안에서의 변위(displacement, offset)

매핑 정보는 BMT(Block Map Table)가 관리하며, 커널 공간에 프로세스마다 하나씩 존재한다.

residence bit는 해당 block이 메모리에 적재되어 있는지를 나타낸다.

매핑은 다음 순서로 진행된다.

1. 프로세스의 BMT에 접근한다.
2. BMT에서 block b의 항목(entry)을 찾는다.
3. residence bit를 검사한다. 0이면 swap device에서 메모리로 가져오고, 1이면 b의 실제 주소 a를 확인한다.
4. 실제 주소 r = a + d를 계산한다.
5. r로 메모리에 접근한다.

Paging System

프로그램을 같은 크기의 block으로 분할한다.

• Page: 가상 메모리(프로그램)를 일정한 크기로 나눈 block
• Page frame: 물리 메모리를 page와 같은 크기로 나눈 영역

특징은 다음과 같다.

• 논리적 분할이 아닌 크기에 따른 분할이다.
• 단순하고 효율적이다.
• 외부 단편화가 없다. page가 연속되어 저장될 필요 없이 남는 frame에 배치되기 때문이다. 다만 마지막 page가 frame을 다 채우지 못하는 내부 단편화는 발생할 수 있다. (외부 단편화가 생기지 않는 이유)
• page sharing과 protection이 복잡하다.

Direct Mapping

가상 주소는 v = (p, d)이고, 매핑 정보는 PMT(Page Map Table)에 저장한다.

1. PMT가 저장된 주소 b에 접근한다.
2. PMT에서 page p의 entry를 찾는다. (entry 위치 = b + p * entrySize)
3. entry의 residence bit를 검사한다.
4. page frame 번호 p’과 변위 d로 실제 주소를 만든다. (r = p' * pageSize + d)
5. r로 주기억장치에 접근한다.

Direct Mapping에는 두 가지 단점이 있다.

• PMT에 한 번, 실제 주소에 한 번 접근하므로 메모리 접근 횟수가 2배다.
• PMT를 저장할 메모리 공간이 필요하다.

Associative Mapping (TLB)

위 단점을 하드웨어로 해결한다. PMT를 TLB(Translation Look-aside Buffer)라는 전용 고속 연관 메모리에 적재하면, 주소 계산 없이 병렬로 탐색할 수 있어 빠르다. 오버헤드가 낮고 속도가 빠르지만 캐시 메모리 형태라 가격이 비싸다.

Hybrid Direct/Associative Mapping

두 방식의 장점을 취하기 위해 PMT의 일부만 TLB에 두는 방식이다. 이때 TLB는 가상 주소를 실제 주소로 매핑한 적이 있는 정보를 저장하는 캐시 역할을 한다. 한 번 변환한 주소는 TLB에 남아 있으므로 다시 변환하지 않아도 되어 빠르다.

1. 찾으려는 PMT entry가 TLB에 적재되어 있는지 확인한다.
2. 적재되어 있으면 residence bit를 검사하고 page frame 번호를 확인한다.
3. 적재되어 있지 않으면 Direct Mapping으로 page frame 번호를 확인하고, 해당 entry를 TLB에 적재한다.

Page Sharing과 Protection

비연속 할당이므로 여러 프로세스가 특정 page를 공유할 수 있다. 메인 메모리에 하나만 올려 두고 함께 쓰는 것이다. 공유할 수 있는 page는 다음과 같다.

• Procedure page (함수 코드 등)
• Read-only data page
• Read-write data page: 세마포, 모니터 같은 병행성 제어 기법의 관리 아래에서만 가능하다.

주의할 점은, 프로세스마다 page의 주소가 다르면 공유 코드 안에서 다른 함수를 호출할 때 엉뚱한 곳으로 이동할 수 있다는 것이다. 접근 권한은 PMT의 protection bit로 관리한다.

페이지 크기의 Trade-off

• 페이지를 크게 나누면 프로세스가 페이지를 모두 채우지 못하는 내부 단편화가 커진다.
• 페이지를 작게 나누면 페이지 수가 늘어나고, 이를 관리할 페이지 테이블이 커진다.

32비트 주소 공간에서 페이지 크기가 1KB라면 페이지 테이블은 얼마나 커질까? 주소 공간은 4GB(2^32)이고 페이지 크기는 1KB(2^10)이므로, 페이지 테이블의 entry는 최대 2^32 / 2^10 = 2^22, 약 400만 개다.

페이지 크기가 커지면 페이지 폴트가 더 많이 발생할까?

• 페이지 크기가 커지면 페이지 폴트 발생률도 커진다.
• 그러다 어느 지점을 넘으면 페이지 폴트 비율이 줄어든다. 페이지 하나에 프로세스에 필요한 내용이 다 들어가기 때문이다.

페이지 폴트가 발생했을 때의 처리는 페이지 교체 알고리즘과 Thrashing에서 다룬다.

Segmentation System

Paging처럼 고정된 크기로 나누지 않고 프로그램을 논리적 block으로 분할한다. 따라서 block마다 크기가 다를 수 있다.

• 메모리를 미리 분할하지 않는다. 연속 할당의 가변 분할과 유사하다.
• segment sharing과 protection(권한 관리)이 용이하다. 프로그램의 중요한 부분과 그렇지 않은 부분을 분리해 저장할 수 있고, 같은 코드 영역은 하나만 저장해 공유할 수 있다.
• 주소 매핑과 메모리 관리의 오버헤드가 크다.
• 내부 단편화는 없지만 외부 단편화가 발생할 수 있다.

Address Mapping

가상 주소는 v = (s, d)이다. s는 segment number, d는 segment 안에서의 변위다. 매핑 정보는 SMT(Segment Map Table)에 저장하는데, segment마다 크기가 다르므로 segment length 필드가 있다.

1. 프로세스의 SMT가 저장된 주소 b에 접근한다.
2. SMT에서 segment s의 entry를 찾는다. (entry 위치 = b + s * entrySize)
3. entry를 검사한다.
   • residence bit를 검사한다.
   • 변위 d가 segment 길이 l보다 크면 segment overflow exception이 발생한다.
   • protection bit를 검사해 허가되지 않은 연산이면 segment protection exception이 발생한다.
4. 실제 주소 r = a + d를 계산한다.
5. r로 메모리에 접근한다.

Paging과 Segmentation 비교

구분	Paging	Segmentation
분할 기준	고정 크기 (논리적 개념 없음)	논리 단위
관리 오버헤드	낮음 (크기 계산 불필요)	높음 (segment마다 크기를 관리)
공유·보호	복잡함	단순하고 쉬움
단편화	내부 단편화	외부 단편화

단편화의 의미를 다시 정리하면 다음과 같다.

• 외부 단편화: 남은 공간의 합은 프로세스를 적재할 만큼 충분하지만, 서로 떨어진 block에 흩어져 있어 올리지 못하는 경우
• 내부 단편화: 프로세스를 적재하고 block 안에 남는 공간이 생기는 경우

Hybrid Paging/Segmentation

두 방식의 장점을 결합한 기법이다.

1. 프로그램을 논리 단위의 segment로 분할한다.
2. 각 segment를 고정된 크기의 page로 다시 분할한다.

메모리에는 page 단위로 적재한다.

가상 주소는 v = (s, p, d)이다. s는 segment number, p는 page number, d는 page 안에서의 offset이다. SMT와 PMT를 모두 사용하며, segment마다 여러 page로 나뉘므로 프로세스 하나에 PMT가 여러 개 존재한다.

주소 변환은 SMT에서 segment의 PMT를 찾고, 그 PMT에서 page frame을 찾는 순서로 진행된다.

정리하면 다음과 같다.

• page sharing과 protection이 쉽다.
• 메모리 할당과 관리의 오버헤드가 작다.
• 외부 단편화가 없다.
• 테이블 수가 늘어 메모리 소모가 크고, 주소 매핑 과정이 복잡하다.
• Direct Mapping의 경우 메모리 접근이 3배가 되어 성능이 저하될 수 있다.

참고

• 운영체제: 그림으로 배우는 구조와 원리 (한빛아카데미)