[운영체제] 15. 메모리 관리

Memory & Process

프로그래머가 원하는 이상적인 메모리는 용량도 크고, 입출력도 빠르고, 저장된 데이터도 망가지지 않는 메모리일 것이다.

하지만 현실적으로 입출력이 빠른 메모리는 용량당 비용이 점점 높아지다보니, 용도에 맞춰 다양한 특징을 가진 메모리를 계층구조로 설계한다.

 

먼저 용량은 작지만 입출력이 빠르고 비싼 메모리는 cache 로 계층 상단에 두고

중간 용량과 속도, 중간 가격대를 가진 메모리는 main memory 로 중간에 두고

큰 용량과 낮은 속도, 싼 가격대를 가진 저장장치는 디스크 저장공간으로 제일 하단에 둔다.

 

메모리를 관리하는 memory manager 는 운영체제의 일부로서 메모리 계층 구조를 관리한다.

또한 어떤 메모리의 어떤 부분이 사용되고 있고, 사용되지 않고 있는지 추적하며, 프로세스에게 메모리를 할당하고 회수한다.

만약 메인 메모리 공간이 모든 프로세스를 다 올리기에 부족하다면 디스크와 메인 메모리 사이의 swapping을 관리한다.

 

 

Monoprogramming

monoprogramming 은 한번에 하나의 유저 프로세스만 실행하는 것을 말한다.

모노 프로그래밍 방식에서 메모리 구조는 다음과 같이 크게 3가지 방법이 있다.

 

 

(a) 방법은 메모리 (RAM) 낮은 주소에 운영체제를 두고, 그 위에 유저 프로그램을 실행하는 방법이다.

과거 메인 프레임이나 미니 컴퓨터에서 사용하던 방식이다.

 

(b) 방법은 운영체제를 RAM이 아닌 ROM에 두고, 유저 프로그램은 RAM에서 실행한다.

(ROM = Read-Only Memory, 고정기억장치로 지워지지 않는다.)

palmtop computer 또는 임베디드에서 주로 사용한다.

 

(c) 방법은 PC가 등장한 이후에 주로 사용하는 방법으로, 메모리 낮은 주소에 OS를 두고, 그 위에서 유저 프로그램을 실행한다.

그리고 ROM 에는 운영체제의 일부라고 볼 수 있는 Device Driver 소프트웨어가 들어있다.

 

 

Multiprogramming

멀티 프로그래밍(하나의 컴퓨터에서 여러개의 프로세스를 동시에 실행하는 것)에서는 메모리에 여러 프로세스가 동시에 존재한다.

멀티 프로그래밍에서 메모리를 관리하는 기본적인 방법은 고정된 크기로 메모리 공간을 분할하는 것이다.

이를 가리켜 Fixed Parititions 이라고 부른다.

 

 

 

먼저 (a) 방법은 다양한 고정된 크기의 파티션을 미리 나눠두고, 각각의 파티션마다 큐를 둔다.

운영체제는 어떤 job이 들어오면 그 job이 들어갈 수 있는 파티션 중 제일 작은 크기의 파티션 큐에 job을 추가한다.

 

그런데 만약 크기가 작은 job만 들어온다면, 크기가 큰 파티션이 비어있음에도 계속 크기가 작은 파티션에만 줄을 서므로 메모리 공간이 낭비되는 문제가 있다.

 

그래서 (b) 방법과 같이 각각의 큐를 통합한 하나의 큐로 처리하도록 개선하였다.

이 방법은 현재 큐에서 꺼낸 job이 들어갈 수 있는 파티션을 찾아 그 위치에 넣어주므로, 크기가 작은 job들만 들어오더라도 큰 공간에 파티션에도 할당할 수 있어 이전의 문제를 해결할 수 있다.

(하나의 파티션에는 하나의 job만 들어갈 수 있을까? 아니면 여러 job이 들어갈 수 있을까? 큐에 들어가는 건 왜 프로세스가 아니라 job 이라고 할까?)

 

 

Relocation & Protection

멀티 프로그래밍 방식에서는 relocation, protection 개념이 필요해진다.

 

Protection은 하나의 파티션에서 실행 중인 프로그램이 다른 파티션을 침범하면 안된다는 개념이다.

프로텍션을 구현하기 위해서 과거 IBM은 Protection Code를 사용했다.

먼저 메모리를 2K 또는 4K 단위의 조각으로 쪼개고, 각 조각마다 protection code를 할당한다.

 

CPU가 프로세스를 실행할 때, PSW (Program State Word) 라는 레지스터에 protection key 가 할당된 채로 수행한다.

이 프로세스가 메모리에 접근할 때마다 PSW의 protection key 와 접근하려는 공간의 protection code를 비교해서 그 값이 같다면 접근을 허용하고, 다르다면 접근을 거부하는 방법으로 protection 을 구현하였다.

 

Relocation은 메모리에 접근하는 주소를 바꾸는 것을 말한다.

프로그래머가 프로그램을 작성하고 컴파일할 때, 특정 변수의 메모리 주소, 함수의 호출 주소와 같은 정보는 컴파일 시점에서 알 수 없다. 프로그램이 어떤 파티션에 적재될 지 미리 알 수가 없기 때문이다.

따라서 컴파일러는 프로그램의 시작점을 0으로 두고 상대 주소로 메모리 주소와 함수의 호출 주소를 기술한다.

그리고 운영체제가 실제로 프로그램을 메모리에 적재해서 실행할 때는 프로그램이 올라간 메모리의 위치를 base 주소로 해서 실제로 접근할 메모리 주소를 계산한다.

 

이를 구현하는 방법은 2가지가 있다.

 

첫 번째는 링커가 컴파일된 결과물을 합쳐서 하나의 실행파일을 만들 때, 실행파일 안에 주소값의 재조정이 필요한 변수, 프로시저 등을 명시한 테이블을 만든다. 그리고 운영체제가 이 실행파일을 실행할 때 테이블의 내용을 보고 모든 상대 주소를 실제 주소로 바꿔서 실행하는 방식이다.

이 방법은 모든 변수의 주소를 절대 주소로 바꿔야 하므로 프로그램을 로딩하는데 시간이 조금 걸리는 문제가 있다.

 

두 번째는 베이스 레지스터와 리미트 레지스터를 사용한다.

베이스 레지스터는 프로세스가 들어간 파티션의 시작주소 값을 갖고 있으며, 실행파일을 만들 때는 상대주소 그대로 실행파일을 만들어 실행한 뒤, 실제 메모리에 접근할 주소는 베이스 레지스터의 값과 상대주소값을 더해서 메모리에 접근할 물리주소를 계산하는 방식이다.

여기에 리미트 레지스터를 사용하면 Protection 문제도 함께 해결할 수 있다.

리미트 레지스터에는 파티션의 크기 값이 들어있다. 만약 상대 주소값이 파티션의 크기를 넘어간다면 다른 영역을 침범하게 되므로 이때는 Access Violation 에러를 내서 다른 파티션을 침범하지 못하도록 막는다.

 

이 방법은 프로그램 로딩이 빠르지만, 메모리에 접근할 때마다 베이스 레지스터와 리미트 레지스터를 고려하는 연산을 수행해야 하므로 실행 시간이 상대적으로 오래걸리는 단점이 있다.

 

 

---

Memory Management

프로세스를 메모리에 실행할 때는 크게 스와핑과 가상 메모리 2가지 방법이 있다.

이제 각각의 방법을 자세히 정리해보자.

 

Swapping

스왑핑은 각각의 프로세스를 메모리에 통째로 가져와서 수행하고, 다시 디스크에 돌려두는 것을 말한다.

 

 

위 그림은 멀티프로그래밍 방식에서 가변 파티션을 사용하는 모습을 보여준다.

왼쪽부터 오른쪽으로 갈 수록 시간에 따라 프로세스가 변하는 모습을 보여준다.

먼저 프로세스 A를 실행하면 제일 낮은 주소에서부터 실행하며, B, C 도 차근차근 쌓아서 실행한다.

 

다음으로 D가 실행될 차례가 됐다. 그런데 실행될 공간이 없다.

따라서 A를 빼고 빈 공간에 D를 적재한다. (왜 A가 나올까? 제일 오래돼서?)

그 다음으로 다시 A가 실행되어야 하므로 B가 나가고 A가 들어온다.

 

이렇게 A, B, C, D가 통으로 들어갔다가 나오면서 실행되는 것이 스와핑 방식이다.

스와핑은 프로세스가 메모리로 들어오고 나갈 때  메모리 할당 현황이 바뀐다.

 

이때 빗금친 부분 영역을 하나로 모아서 커다란 빈 공간을 만들면 더 효율적이라는 아이디어는 어렵지 않게 떠올릴 수 있다.

이 기법을 가리켜 Memory Compaction (메모리 압축) 이라고 부른다.

 

 

프로세스를 메모리에 적재할 때는 (a) 와 같이, 실제로 사용하는 영역의 크기에 더해 추가적으로 사용할 수 있는 여분 공간을 함께 할당한다.

UNIX 시스템에서는 더 정교하게 (b) 와 같이 할당한다.

하나의 프로세스는 그 내부에 코어 이미지를 갖고 있다. (프로세스에 대해 정리했던 글 참고)

코어 이미지는 크게 프로그램 세그먼트, 데이터 세그먼트, 스택 세그먼트로 나뉘며, 프로그램(텍스트) 세그먼트의 크기는 고정되어있고, 데이터 세그먼트와 스택 세그먼트의 크기는 변할 수 있다.

 

(a)는 data 세그먼트에 대해서만 추가 공간을 할당하고, (b) 는 스택과 데이터 세그먼트에 대해 할당한 것?

 

이제 스와핑을 실제로 어떻게 구현하는지 대표젹인 2가지 방법을 살펴보자.

 

Bit Map

 

 

위 그림은 물리 메모리 (a) 에 할당된 프로세스를 Bit Map 으로 관리하는 모습 (b), 연결 리스트로 관리하는 모습 (c) 을 함께 보여주고 있다.

 

현재 메모리에는 5개의 프로세스가 존재하며, 3개의 hole이 있다고 해보자. (사용하지 않는 메모리 공간)

이때 메모리에 보이는 각각의 작은 눈금은 메모리에 프로세스를 할당하는 단위라고 생각하자.

그러면 A는 5개 유닛의 크기를 차지하여 할당된 상태고, B는 6개 유닛의 크기를 차지하여 할당된 상태를 가리킨다.

 

비트맵 방식에는 이 각각의 눈금에 대해 프로세스가 할당되어있으면 1, 아니면 0을 저장하는 방법으로 메모리에 프로세스가 할당된 현황을 관리한다.

 

비트맵 방식에서는 할당 단위 (allocation unit) 의 크기가 비트맵에 영향을 준다.

만약 할당 단위가 크다면, 전체 비트 맵의 크기는 작아지지만 (표현하는데 필요한 비트 수가 줄어드므로) 항상 그 유닛의 크기만큼 할당해야하다보니 메모리 낭비가 비교적 커지고,

만약 할당 단위가 작다면, 전체 비트 맵의 크기가 커지는 대신, 프로세스가 요구하는 사이즈에 최대한 맞춰서 할당할 수 있게 되므로 메모리 낭비가 줄어들게 된다.

 

비트맵 방식으로 메모리를 관리하면, 새로운 프로세스가 할당된 공간을 찾는데 시간이 오래 걸리는 단점이 생긴다.

만약 10개 할당 유닛을 요구하는 프로세스가 있다면, 비트맵을 순회하면서 연속된 10개의 0을 찾아야 하기 때문이다.

 

 

Free Lists (Linked List)

또 다른 메모리 관리 방법은 연결 리스트를 활용한 관리 방법이다.

먼저 연결 리스트의 각 노드는 4가지 데이터를 저장한다.

 

(이 노드가 프로세스인지 / 홀 인지 , 시작 allocation unit 번호, 크기, 다음 노드의 포인터)

 

첫 번째 노드는 (P, 0, 5, x) 형태로 되어있는데, 이는 0번 할당 유닛에서 시작하는 곳에 5개 크기의 프로세스가 메모리를 차지하고 있음을 가리킨다.

이 노드와 연결된 두 번째 노드는 (H, 5, 3, x) 형태로 되어있는데, 이는 5번 할당 유닛에서 시작하는 곳부터 3개 크기의 공간은 아무것도 들어있지 않은 hole 임을 나타낸다.

 

그리고 이렇게 연결하면 링크드 리스트는 자연스럽게 메모리 주소 순으로 정렬되어 연결된다.

 

 

연결 리스트를 구성하는 노드 숫자의 변화는 크게 위와 같이 4가지가 존재한다.

(a) 에서는 P - P - P 형태였다가 X 가 종료되면 P - H - P 가 되므로 노드의 개수가 변하지 않는다.

(b) 에서는 P - P - H 형태였다가 X 가 종료되면 P - H 로 노드의 개수가 1개 감소한다.

(c) 에서는 H - P - P 형태였다가 X 가 종료되면 H - P 로 노드의 개수가 1개 감소한다.

(d) 에서는 H - P - H 형태였다가 X 가 종료되면 H 로 노드의 개수가 2개 감소한다.

 

그렇다면 새로운 프로세스에게 메모리를 할당할 때는 어떻게 할당할 수 있을까?

일단 기본적으로 낮은 주소부터 시작해서 전체 노드를 훑으면서 해당 프로세스가 요구하는 크기 이상의 H 에 할당하는 것은 자명하다.

이때 선택가능한 H 중에서 적절한 H를 고르는 기준은 다음과 같이 3가지가 있다.

 

1. First Fit : 가장 먼저 만나는 적절한 H 에 할당

2. Best Fit : 전체 리스트를 순회하고, 적절한 H 중 가장 작은 크기의 H 에 할당 

3. Worst Fit : 전체 리스트를 순회하고, 적절한 H 중 가장 큰 크기의 H 에 할당

 

얼핏보면 3번 방식은 왜 쓰는지 의문이 든다.

먼저 2번 방식을 사용하다보면 프로세스가 요구하는 크기보다 조금씩 더 큰 홀에 할당하다보니 자투리 홀이 많이 생길 수 있다.

그러다보니 그러면 차라리 제일 큰 홀에 할당하고, 자투리를 크게 만들어서 작은 크기를 요구하는 프로세스가 등장했을 때 할당할 수 있도록 하자는 아이디어에서 3번 방법이 등장하였다.

 

Virtual Memory

프로그램이 너무 커서 메모리에 한번에 담을 수 없을 때, 프로그램의 일부만 메인 메모리에 올라와있더라도 실행을 허용한다.

이를 구현하는 방법은 크게 Overlay 와 Virtual Memory 가 있다.

 

Overlay 방법은 간단하다. 큰 프로그램을 여러 단위로 쪼개고, 각 조각을 Overlay 라고 부른다.

그리고 마치 기존에 프로세스를 통으로 스와핑하듯이 오버레이를 스와핑해가면서 실행하는 것이다.

(첫 번째 오버레이를 실행하고, 오버레이의 실행이 끝나면 다른 오버레이를 호출)

이 방법은 프로그래머가 직접 오버레이를 어떻게 나눌 지 설계해야 하므로 어려움이 있다.

 

Virtual Memory 방식은 이를 컴퓨터가 대신 하도록 한 방법이다.

Virtual Memory 를 구현할 때 대표적으로 Paging 을 사용한다.

 

위에서 Multiprogramming 방식은 여러 프로세스가 존재하므로 프로그램 안에 기술한 메모리 주소는 프로그램이 로딩되는 위치를 기준으로 한 상대주소로 기술한 뒤, 나중에 물리 주소로 변환하는 relocation 이 발생한다고 하였다.

 

이와 비슷하게, 가상 메모리 방식에서도, 그 내부적으로 사용하는 Virtual Address 가 필요하다.

먼저 프로그램에 등장하는 상대 주소를 가상 메모리 방식에서는 Virtual Address, 가상 주소라고 부른다.

(강의록에서는 Program generated address 라고도 표현한다.)

 

그리고 이렇게 가상주소 체계로 표현되는 가상의 공간을 Virtual Address Space 라고 부른다.

가상 공간은 말 그대로 '가상의 공간' 이기 때문에 크기에 제한이 없어서 일반적으로는 실제 메모리가 갖는 공간보다 더 큰 크기를 갖는다.

이제 이 가상의 공간과 실제 메모리 공간을 매핑 시키기 위해서, 가상 공간을 일정한 단위로 쪼개야 한다.

이 단위를 가리켜 '페이지 (page)' 또는 virtual page 라고 한다.

 

그리고 가상공간에서의 단위를 실제 메모리 공간에서 그대로 맞추기 위해, 실제 메모리 역시 동일한 단위로 쪼개야 한다.

실제 메모리에서 쪼개는 단위는 page frame 이라고 부른다.

따라서 디스크에 존재하는 프로그램을 메모리로 가져와서 실행할 때는 페이지 단위로 데이터를 가져와서 실행한다.

 

 

그렇다면 가상주소와 실제 주소간의 변환은 어떻게 할 수 있을까?

프로그램의 일부만 가져온다면 위에서 기술한 relocation 기법을 단순하게 적용할 수는 없다.

 

이를 위해 등장한 것이 MMU (Memory Management Unit) 이다.

MMU는 CPU 패키지 내부에 CPU와 함께 존재한다.

CPU가 명령어를 실행할 때는 MMU에 가장 주소를 보내서 이 주소에 대해 메모리 I/O 를 지시한다.

그러면 MMU는 CPU가 보낸 주소를 물리 주소로 변환한 뒤, 실제 메모리에는 변환된 주소로 접근한다.

 

 

위 그림은 virtual address space(가상 주소 공간)와 실제 메모리 사이의 관계를 보여준다.

가상 주소 공간은 그림에 나와있듯 일반적으로 실제 메모리 공간보다 더 큰 크기를 갖는다.

 

위 그림에서는 두 공간을 모두 동일하게 4K 바이트 단위로 쪼갰고,

가상 주소 공간에서 단위의 이름은 Virtual Page 실제 메모리 공간에서 단위의 이름은 Page Frame 이다.

 

왼쪽에는 16개의 virtual page가 존재하므로 가상 주소 공간의 크기는 4K * 16 = 64K byte 이고, 실제 메모리 공간은 8개의 page frame이 존재하므로 32K byte 이다.

 

OS가 virtual page와 page frame을 매핑할 때는, Page Table에 매핑 정보를 저장한다.

page frame 을 밑에서부터 인덱스를 매기고, virtual page 가 어떤 인덱스의 page frame과 매핑되어 있는지를 기술한다.

 

일반적으로 virtual address space의 크기가 더 크기 때문에, virtual page 중에는 매핑되지 않은 페이지가 존재한다.

만약 MMU가 변환 과정에서 매핑되지 않은 virtual page 에 대해 변환하려고 하는 경우에는 CPU가 OS로 trap을 발생시키도록 한다.

(이를 가리켜 page fault가 발생했다고 표현한다.)

그러면 OS는 기존에 메모리에 올라온 페이지 프레임 중 하나를 골라 내보내면서 페이지 내용을 디스크에 쓰고, 매핑되지 않았던 페이지를 메모리에 올려 매핑시킨다. 그리고 trap된 명령어를 다시 실행시켜서 정상적으로 주소를 변환하여 명령어 기능을 수행한다.

 

이때 내보낼 페이지 프레임은 가장 오랫동안 사용되지 않은 페이지 프레임을 골라 내보내는 것이 일반적이다.

페이지 교체 알고리즘은 나중에 자세히 정리한다.

 

 

Page Table

 

위 그림은 MMU에서 주소를 변환하는 과정을 보여준다.

(수업 중에 MMU 내에 페이지 테이블이 존재한다고 하셨는데, 컴구에서는 프로세스마다 페이지 테이블이 존재한다고 한다.

프로세스마다 존재해야 맞는 것 같은데, 왜일까? MMU 내부적으로 프로세스마다 갖고 있는 페이지 테이블 내용을 복사해서 쓰나?

=> 뒤에 설명이 나왔다. 프로세스마다 페이지 테이블을 갖는 게 맞고, 실행할 땐 MMU 내부에 있는 페이지 테이블에 복사한다.)

 

하나의 페이지 크기가 4KB 였으므로, 12bit 를 사용해야 그 공간을 표현할 수 있다.

이때 앞서 본 예제에서 virtual page 의 개수가 16개였으므로, 12bit 공간이 16개 있으므로 virtual page를 구분하는데 4개 bit가 필요하다.

따라서 총 가상 주소의 길이는 12 + 4 = 16bit 이며, 상위 4비트는 이 주소가 어떤 virtual page에 속하는지 식별하는데 사용되고, 하위 12bit 는 그 페이지 내에서 어디에 존재하는지 offset을 나타낸다.

 

반면 실제 메모리 주소는 앞서 본 것처럼 8개 page frame 으로 구성되어 있었기 때문에 3개 bit 로 page frame을 식별한다.

따라서 그 주소의 길이는 12 + 3 = 15 bit 이다.

 

virtual page와 page frame 크기는 같으므로, 하나의 페이지 내에서 offset 값은 그대로 복사되어 들어간다.

그러면 결국 virtual address 의 상위 4bit를 실제 메모리의 적절한 상위 3bit로 변환만 하면되는데, 여기에 사용되는 것이 바로 Page Table이다.

 

 

이제 구체적인 예시를 살펴보자.

변환하고자 하는 가상 주소가 8196 이다.

이 주소값을 16bit로 표현하면 0010 / 000000000100 이다. (일부러 상위 4비트와 하위 12비트를 구분하였다.)

하위 12bit 는 그대로 복사되어 offset으로서 들어가고, 상위 4bit 를 실제 메모리의 상위 3bit로 변환한다.

 

상위비트 0010 은 십진수로 2를 의미하므로, Page Table에서 2번 인덱스가 가리키는 값을 확인한다.

2번 인덱스에는 110 이라는 3비트 값이 있고, 이 값이 유효하다는 비트가 1로 설정되어있으므로 (그림에서는 present / absent bit)

현재 0010 이라는 4bit 상위 주소가  110 이라는 3비트 상위 주소로 매핑되어있다는 것을 알 수 있다.

따라서 실제 물리 메모리 주소를 110 / 000000000100 으로 계산할 수 있게 된다. (십진수로 24580)

 

(자세한 내용은 컴퓨터 구조 정리 글을 참고하자.)

 

 

페이지 테이블을 설계할 때는 크게 2가지 고려할 점이 존재한다.

 

1. 페이지 테이블은 allocation unit 개수에 따라 그 크기가 매우 커질 수 있다.

만약 32bit 주소 체계를 사용한다면, 메모리는 최대 4GB가 될 수 있고, 만약 page frame의 크기가 4KB 라면 백만개의 4KB 페이지로 구성될 것이기에, 페이지 테이블은 백만개의 entry를 갖고 있어야 한다.

 

2. 매핑 속도가 빨라야 한다.

virtual-to-physical 매핑이 메모리에 접근할 때마다 발생하므로, 그 매핑 속도는 매우 빨라야 한다.

(어셈블리와 컴퓨터 구조에서 공부했듯, 메모리에 접근하는 연산은 수시로 발생한다.)

 

그리고 이를 고려할 때, 해시 테이블을 설계할 수 있는 방법은 아래와 같이 2가지가 있다.

 

1. MMU에 Page Table 구성하기

앞서 본 그림이 이 방식으로 설계된 페이지 테이블이다.

하나의 Page Table을 MMU 내에 빠른 하드웨어 레지스터 배열로 구성된 하나의 배열로 만들어 사용한다.

페이지 테이블이 CPU 패키지 내에 있는 MMU에 있으므로 읽고 쓰는 속도가 매우 빠르다.

하지만 이렇게 구성하는 경우, 프로세스 스위칭 (context switching) 이 발생할 때마다 그 프로세스가 갖고 있는 페이지 테이블 내용 전체를 MMU 페이지 테이블에 로딩해야 하는데, 이 비용이 비싸다는 문제가 있다. (메모리에서 CPU 안으로 전체 페이지 테이블 데이터를 옮기므로)

 

2. 메모리에 Page Table 구성하기

MMU에 페이지 테이블을 두지 않고, 프로세스를 메모리로 불러올 때 프로세스가 가진 페이지 테이블도 같이 로딩한다.

그리고 페이지 테이블의 메모리 상 시작 주소를 레지스터에 저장하여 주소를 변환할 때 메모리에 접근해서 페이지 테이블의 값을 읽어 변환한다.

 

컨텍스트 스위칭이 발생할 때마다 레지스터에 저장된 페이지 테이블의 시작주소만 바꾸면 되므로, 페이지 테이블을 빠르게 교체할 수 있다.

하지만 주소를 변환할 때마다 메모리에 들어있는 페이지 테이블 값을 읽어야하므로, 이전에 비해 더 많은 시간이 든다.

(CPU 내 MMU에서 값을 읽어 변환하는 것과 메모리에서 값을 읽어 변환하는 것의 차이)

 

그래서 이 문제를 해결하기 위해 TLB (Translatioin Lookaside Buffer) 를 두는 방법으로 구현한다.

(TLB의 자세한 내용은 뒤에서 정리한다. 컴퓨터 구조 정리 글에도 있음)

 

 

Multi Level Page Table

위 그림에서 두번째 화살표는 회색 영역이 아니라 1번 엔트리에서 뻗어 나와야 한다.

 

페이지 테이블의 크기는 메모리의 크기와 페이지 크기에 따라서 그 수가 매우 많이 커질 수 있다.

32bit 주소 체계를 갖는 가상 주소 공간에 대해 페이지 테이블을 구성한다고 해보자.

페이지 하나의 크기가 4KB 라면 하위 12bit 가 offset이 된다.

이제 남은 20bit 에 대해 가상 주소와 실제 메모리 주소 사이 변환이 이루어져야 하는데, 만약 하나의 페이지 테이블을 쓴다면 2^20 = 100만개의 엔트리를 가진 페이지 테이블이 필요하다.

 

그래서 엔트리 수를 줄이기 위해 페이지 테이블을 계층으로 나눠 사용하는 아이디어가 등장했다.

먼저 상위 20bit 를 10bit 씩 쪼갠다.

 

그리고 앞 10bit 에 대해서 Top-Level Page Table을 확인한다.

상위 10bit의 10진수 값이 가리키는 인덱스는 하위 10bit 에 대한 Second-Level Page Table의 시작 주소를 가리키고 있다.

이제 실제 page frame의 상위 비트로 변환할 때는 Second-Level Page Table 에서 하위 10bit를 10진수로 변환한 인덱스가 가리키는 값을 읽어서 변환하면 된다.

 

이렇게 구성하면 메모리에 100만개 엔트리리를 모두 올려둘 필요 없이, 상위 10bit에 대한 페이지 테이블과, 그 엔트리 하나에 대해 하위 10bit로 식별할 페이지 테이블만 가져오면 되므로 2048개 엔트리만 메모리에 두면 된다.

 

만약 어떤 프로세스의 텍스트 세그먼트 / 데이터 세그먼트 / 스택 세그먼트 크기가 각각 4MB 라고 할 때, 각각 1024개 엔트리를 가진 페이지 테이블로 표현하게 되면 Top-Level 1024개 엔트리를 공통으로 두는 것을 포함하여 총 4096개 엔트리로 하나의 프로세스를 표현할 수 있다. 이는 각 세그먼트가 4MB 일 때를 가정한 것이고, 만약 세그먼트의 크기가 늘어나면 더 많은 세컨 레벨 페이지 테이블이 필요할 수 있다.

(스택 / 데이터 세그먼트의 경우 크기가 가변적인데 어떻게 4MB로 고정할 수 있는지 궁금해서 질문을 드렸다.

운영체제에서 지원하는 여부에 따라 다르겠지만, 지원한다면 활성화되지 않은 페이지 테이블 엔트리를 추가적으로 활성화해서 영역을 늘리는 것을 구현할 수 있다고 하셨다. 그런데 스택은 높은 주소에서 감소하는 방식으로, 데이터 영역은 낮은 곳에서 증가하는 방식으로 할당이 될텐데, 그러면 데이터 영역이 4MB, 스택 영역이 4MB로 해서 페이지 Top Level 페이지 테이블 엔트리 3개를 할당했다고 해보자. 데이터가 실제로는 1MB만 사용하고 있었고 스택만 계속 증가한다면 스택이 데이터 세그먼트쪽으로 넘어가 최대 7MB를 할당받아 사용하는 것이 가능할까? 이렇게 페이지 엔트리를 너는 스택 거, 너는 데이터 세그먼트 거라고 나눠두면 이렇게 침범하는 것이 불가능하지 않을까 하는 의문이 아직 남아있다.. 일단 스택 세그먼트가 할당받은 세컨더리 페이지 테이블 4MB 영역 내에서는 높은 곳에서 낮은 곳으로 증가하는 방향으로 엔트리를 점차 활성화 시켜 나가는 쪽으로 이해하였다.)

 

=> 완전히 이해하였다. 하나의 메모리에 여러개의 프로세스가 들어오는 상황을 생각하다보니 헷갈렸는데, 일단 프로세스 하나 입장에서 페이지 테이블로 표현할 가상주소는 오롯이 그 프로세스 하나만의 것이므로 512개의 Top-Level 페이지 엔트리가 있다면 512개가 모두 하나의 프로세스에 대한 엔트리이다. 이때 511은 스택 영역의 엔트리로, 0은 텍스트 영역, 256는 데이터 세그먼트 영역으로 건너 건너 지정할 수 있다. 이렇게 건너 건너 지정한 상태에서 0~255 엔트리는 텍스트 세그먼트 영역으로서 고정되어있고, 256에서 데이터 세그먼트 영역이 인덱스가 증가하는 방향으로 추가 할당될 수 있고, 스택영역은 511에서 감소하는 방향으로 할당될 수 있다.

 

나는 511과 256 사이가 비어있다면, 이 공간에 다른 프로세스가 적재되어버릴 수 없을까? 그러면 저렇게 띄워두는 게 아니라 0 = 텍스트 세그먼트, 1 = 데이터 세그먼트, 2 = 스택 세그먼트, 3~ 비워둠. 이렇게 할당해야 하지 않을까? 생각했었다. GPT야 고마워~)

 

즉, 실제 물리 메모리의 크기가 4GB라고 하더라도, 4GB 전체로 변환될 수 있는게 아니라, 프로세스가 4GB 안에서 할당받은 영역, 그 안에서만 변환이 되는 것이다. (페이지 크기가 4KB 라면 4GB 메모리를 100만개 조각으로 쪼갤 수 있다. 만약 프로세스가 할당받은 영역이 낮은 주소부터 1GB 만큼이라면 가상주소가 몇 비트든 페이지 테이블을 통해 변환되는 실제 주소의 범위는 0~25만번 엔트리까지만 변환될 수 있는 것)

 

 

위 그림은 페이지 테이블을 구성하는 엔트리가 어떻게 구성되어 있는지를 보여준다.

제일 오른쪽에는 변환할 page frame number 값이 존재한다.

 

Present / Absent bit : 1이면 이 엔트리 값에 page frame number가 매핑이 되어있는 것, 0이면 매핑이 안 되어있는 것

 

Protection bit : 이 엔트리에 연결된 페이지에 대해 read-only 또는 읽고 쓰기를 모두 허용할 지를 나타낸다.

활성화되어 있으면 (비트가 1이면) read-only 만 가능하다.

 

Modified bit : dirty bit 라고도 한다. 참조하는 페이지에 수정사항이 생겼다면 활성화된다.

 

예를 들어, 이 엔트리가 가리키는 page frame이 데이터 세그먼트에 대한 page frame 이었다고 해보자.

데이터 세그먼트 공간에 저장된 변수의 값이 바뀐다면 이 페이지에 대해 변화가 발생했으므로 dirty bit 가 활성화된다.

 

Reference bit : 이 엔트리가 가리키는 페이지가 참조된 적이 있다면 (read 또는 write 발생) 활성화된다.

(페이지 교체 알고리즘에서 활용하기 위해 사용하는 듯하다.)

 

(Caching disabled 는 일단 넘어가심)

 

---

TLB (Translation Lookaside Buffer)

페이지 테이블을 MMU 에 직접 넣기에는 매번 프로세스의 페이지 테이블을 복사해서 넣는 비용이 발생하기 때문에 부담스러워서 메모리에 두고 사용하는 방법을 채택하였다.

그러나 이 방법은 주소를 변환할 때마다 메모리에 존재하는 페이지 테이블 데이터를 읽고 쓰기 해야 하므로 비용이 많이 드는 단점이 있었다.

 

이 문제를 해결하기 위해 TLB 를 두는 방법을 채택할 수 있다.

TLB (또는 Associative Memory) 는 MMU 안에 존재하여 읽고 쓰는 속도가 빠르다.

(Associative Memory 는 한번에 하나씩 탐색하는게 아니라, 동시에 여러개씩 탐색하므로 탐색 속도가 빠르다.)

 

TLB를 도입하게 된 배경 중 하나는, 페이지 테이블에서 참조하는 페이지를 보니 소수의 페이지에 대해 많은 참조가 발생한다는 사실이다.

즉, 페이지를 참조하는 많은 기능이 거의 같은 페이지를 읽어올 때가 많다는 것이다.

그러면 그 페이지를 읽어올 때마다 메모리에서 가져오지 말고, 자주 가져오는 페이지에 대한 페이지 테이블 엔트리를 MMU 안에 캐싱해두자는 아이디어를 떠올릴 수 있다. 바로 이 기능을 위해 존재하는 저장 공간이 TLB 이다. (강의록에서 hardware device 라고 표현)

 

TLB를 이용하면 페이지 테이블을 직접 참조하지 않아도 바로 page frame에 대해 주소를 변환하여 접근할 수 있다.

그리고 TLB의 엔트리 개수는 (당연히) 페이지 테이블보다 적은 개수의 엔트리로 구성되어 있다.

 

 

TLB를 사용할 때 주소 변환 과정은 다음과 같다.

 

1. MMU로 주소 변환 요청이 들어온다. (가상 주소 입력)

2. MMU는 가상 주소에서 offset을 제외한 상위 bit를 뽑고 (virtual page number), 이 값이 TLB에 존재하는지 확인한다.

3. TLB에 존재하면 바로 변환된 물리 주소로 접근한다. 이때 protection bit 의 설정과 현재 접근해서 수행하려는 동작 사이의 충돌이 발생하면 안된다. protection bit 가 설정되어있는데 접근하는 이유가 데이터를 쓰기 위함이라면 TLB에서 매핑 값을 보내주지 않는다.

4. 만약 TLB에 존재하지 않으면 이를 가리켜 'Miss' 라고 판단한다. MMU는 miss를 발견했을 때,  페이지 테이블에서 변환될 page frame의 번호를 읽어온다. 그리고 TLB가 가득찼다면 엔트리를 하나 쫓아내고, 방금 읽어온 페이지 테이블 엔트리를 쫓아낸 자리에 넣어둔다.  엔트리를 쫓아낼 때는, 그 엔트리에 설정된 modified bit 를 복사해서 메모리에도 반영해준다. (이 값은 변경되었을 수 있기 때문이다.)

 

즉, TLB는 페이지 테이블에 대한 일종의 CPU 레벨 캐시처럼 생각할 수 있다.

 

 

위 그림은 TLB 의 모습을 나타낸 예시이다.

기본적으로는 virtual page number 에 대해 page frame 번호를 매핑할 수 있도록 데이터가 들어있고,

valid bit, modified bit, protection bit 정보가 들어있다.

 

valid bit 는 현재 TLB의 엔트리가 유효한지를 나타낸다.

처음부터 TLB가 가득 차있지는 않았을테니, 처음에는 valid bit 가 0일 것이고, 페이지 테이블에서 엔트리를 읽어와 할당하면 그때 valid 비트가 활성화된다.

 

protection bit는 좀 더 세분화해서 R, W, X 3가지 정보를 나타낸다.

읽을 수 있고, 쓸 수 있고, 실행할 수 있는지 여부를 나눠서 3bit 로 표현한다.

RX 가 활성화 된 경우는, 해당 페이지가 텍스트 세그먼트를 나타낼 가능성이 높음을 의미한다.

RW가 활성화 된 경우에는, 해당 페이지가 스택 또는 데이터 세그먼트를 나타낼 가능성이 높음을 의미한다.

 

 

Inverted Page Table

 

만약 프로그램의 주소 체계가 64bit 라고 해보자.

그러면 가상 주소 공간의 크기는 2^64 일 것이다.

이때 페이지의 크기가 4KB 라면 64bit 중 12bit 를 제외한 52bit 가 virtual page number 이다.

 

실제 메모리의 크기가 256MB 라고 하면, 같은 크기의 페이지로 분할했을 때 2^16개의 page frame이 존재한다.

 

하나의 페이지 테이블을 사용한다면 2^52 개의 페이지 엔트리가 들어있으므로 매우 무거운 테이블이 될 것이다.

Inverted Page Table은 이 문제를 해결하는 또 다른 방법을 제공한다.

 

먼저 Inverted Page Table의 엔트리 개수는 Physical Memory의 엔트리 개수와 동일하게 맞춘다.

따라서 위 예시에서는 Inverted Page Table의 엔트리 개수도 2^16개 이다.

 

매핑을 할 때는 virtual page number 가 주어질 때, 이 '값'이 들어있는 인덱스를 거꾸로 찾는다.

그러면 그 인덱스가 page frame number 가 되는 방식이다.

 

기존에는 virtual page number 를 인덱스로 보고 페이지 테이블에서 찾았다면, inverted page table에서는 virtual page number를 값으로 보고, 이 값이 들어있는 인덱스를 거꾸로 찾아, 그 인덱스를 page frame number로 취하는 방식인 것이다.

 

예를 들어, virtual page number 1000에 해당하는 페이지를 읽어서 메모리에 올렸다고 해보자.

그때 올라간 page frame number가 3이라면, Inverted Page Tables 의 3번 인덱스에 virtual page number 1000을 저장한다.

그러면 나중에 virtual page number 1000으로부터 물리 주소를 계산할 때는 Inverted Page Tables 에서 1000이라는 값이 들어있는 엔트리를 찾고, 그 엔트리의 인덱스를 page frame number로 사용하여 변환한다.

 

이때 virtual page number는 각각의 프로세스 기준에서 생각하는 상대적인 인덱스이므로, 같은 virtual page number 1000 이라고 해도 프로세스 3번도 1000을 inverted page table에 저장하고, 프로세스 5번도 1000을 inverted page table에 저장할 수 있다.

따라서 1000만 저장하면 이 1000이 어떤 프로세스의 1000인지 알 수 없으므로, (pid, vpn) 쌍을 함께 저장한다.

 

(이미지에는 Indexed by hash on virtual page라고 해서 해시 테이블로 저장하는 내용으로 소개 되어있는데, 이 부분은 스킵하셨다. 블로그 내용을 찾아보니 리니어하게 찾으면 시간이 오래걸리니까 해시 테이블로 저장해서 찾는다고 한다.)