운영체제 요약 - 8. 메모리 관리 전략

February 1, 2021

8.1. 배경(Background)

메모리는 각각 주소가 할당된 일련의 바이트들로 구성된다. CPU는 PC 레지스터가 가르키는 메모리 주소로부터 다음에 수행할 명령어를 가져온다. 이후 명령어를 해독하고 메모리에서 피연산자를 가져와 명령어를 실행한다.

8.1.1. 기본 하드웨어

CPU가 직접 접근할 수 있는 유일한 범용 저장장치는 주 메모리와 프로세서 자체에 내장되어 있는 레지스터들이다. 따라서 모든 명령어와 데이터들은 주 메모리와 레지스터에 있어야 한다.

CPU에 내장되어 있는 레지스터들은 CPU 클록(clock) 1사이클(cycle)내에 접근이 가능하다. 그러나 메모리 버스를 통해 전송되는 주 메모리의 경우는 많은 CPU 클록 틱(clock tick) 사이클이 소요된다. 이렇게 지연되는 현상을 해결하기 위해, CPU와 주 메모리 사이에 빠른 속도의 캐시 메모리를 추가한다.

물리 메모리 접근 속도 차이를 고려하는 것에 추가로 올바른 동작을 보장해야 한다. 사용자 프로그램이 다른 사용자의 프로그램이나 운영체제의 접근하는 것을 막아야 한다. 운영체제가 메모리에 CPU와 메모리 간의 접근에 개입하면 성능이 떨어지기 때문에 하드웨어를 통해 해결한다.

프로세스마다 기준(base), 상한(limit) 레지스터를 사용해 메모리 주소의 기준과 상한를 둔다. 기준 + 상한의 주소를 넘는 메모리 접근은 제한되며, 트랩(trap)을 발생시킨다.

8.1.2. 주소의 할당(Address Binding)

프로그램은 이진 실행 파일 형태로 디스크에 저장되어 있다. 이 프로그램이 실행되기 위해서는 주 메모리로 올라와서 “프로세스”가 되어야 한다.

프로그램은 여러 단계를 거쳐 실행되고, 단계를 거치는 동안 주소들은 여러가지 다른 표현 방식을 거치게 된다. 원시 프로그램에서 주소는 (변수 count와 같이)심볼 형태로 표현된다.

컴파일러는 이 심볼 주소를 (모듈의 시작으로부터 14바이트와 같이)재배치 가능 주소로 바인딩시킨다. 링커(linkage editor)나 로더(loader)는 재배치 가능 주소를 (74014번지 같이)절대 주소로 바인딩시킨다. 각각의 바인딩 과정은 한 주소 공간에서 다른 주소 공간으로 맵핑하는 것이다.

일반적으로 명령어와 데이터를 메모리 주소로 바인딩하는 시점은 다음과 같이 구분된다.

컴파일 시간(complie time) 바인딩
- 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 알 수 있다면 컴파일러는 절대 코드를 생성할 수 있다.
적재 시간(load time) 바인딩
- 프로세스가 메모리 어느 위치에 있을 지 컴파일 시점에 알지 못하면, 컴파일러는 이진 코드를 재배치 가능 코드로 만든다.
- 이 경우 메모리에 적재되는 시간까지 바인딩이 미뤄진다.
실행 시간(execution time) 바인딩
- 프로세스가 실행 중 메모리의 한 세그먼트에서 다른 세그먼트로 옮겨질 수 있다면 실행 시간까지 바인딩이 미뤄진다.
- 특별한 하드웨어가 필요하다.

8.1.3. 논리 대 물리 주소공간(Logical-Versus Physical-Address Space)

CPU가 생성하는 주소는 논리 주소(logical address)라 불리며, 메모리가 취급하게 되는 주소(메모리 주소 레지스터(MAR)에 있는 주소)는 물리 주소(physical address)라 한다.

컴파일, 적재 시 바인딩의 경우에는 논리주소와 물리주소가 같다. 그러나 실행 시간 바인딩에서는 둘이 다르다. 이런 경우 논리 주소를 가상 주소(virtual address)라 한다.

프로그램 실행 중에는 가상 주소를 물리 주소로 바꿔줘야 한다. 이에는 하드웨어인 메모리 관리기(MMU, Memory Management Unity)가 사용된다.

또한 기준 레지스터(재배치; relocation)도 사용된다. 메모리 주소로 프로세스가 생성한 논리 주소가 보내질 때, 재배치 레지스터의 값을 더해 물리 주소로 만든다.

8.1.4. 동적 적재(Dynamic Loading)

동적 적재에서는 프로세스 실행을 위해 프로세스 전체가 메모리에 올라와 있을 필요가 없다. 프로세스의 각 루틴은 호출 전까지 재배치 가능한 상태로 디스크에서 대기한다.

한 루틴이 다른 루틴을 호출할 경우, 먼저 호출된 루틴이 메모리에 있는지 확인한다. 없다면 재배치가능 링커(relocatable linking loader)가 호출된 루틴을 메모리에 올리고 프로그램의 주소 테이블을 갱신한다.

동적 적재의 장점은 루틴이 필요한 경우에만 적재된다는 것이다. 이러한 구조는 오류 처리 루틴과 같이 간혹 발생하면서도 많은 양의 코드를 필요로 하는 경우에 특히 유용하다.

동적 적재는 운영체제로부터 특별한 지원을 필요로 하지 않는다. 프로그래머가 프로그램의 설계를 책임져야 한다.

8.1.5. 동적 연결 및 공유 라이브러리(Dynamic Linking & Shared Libraries)

동적 연결 라이브러리는 프로그램이 실행될 때, 프로그램에 연결되는 시스템 라이브러리이다. 동적 적재에서는 로딩(loading)이 실행 시까지 미루어졌지만, 동적 연결에서는 연결(linking)이 실행 시까지 미루어진다.

동적 연결에서는 라이브러리를 부르는 곳마다 스텁(stub)이 생긴다. 이 스텁은 라이브러리를 어떻게 찾을 것인가를 알려주는 작은 코드 조각이다.

스텁이 실행될 때 자신을 루틴의 주소로 대체하는데, 라이브러리가 메모리에 없으면 디스크에서 가져온다. 즉, 10개의 프로세스가 prinf()와 같은 라이브러리를 사용한다고 하더라도 라이브러리 코드는 메모리에 한번만 올라간다.

프로그램이 다른 라이브러리 버전을 수행하는 것을 방지하기 위해, 버전에 대한 정보가 프로그램과 라이브러리 내에 포함되어야 한다. 이러한 시스템을 공유 라이브러리(shared library)라고 한다.

동적 적재와는 달리, 동적 연결과 공유 라이브러리는 운영체제의 도움이 필요하다. 프로세스들이 각자의 공간을 자신만 접근할 수 있다면, 운영체제만이 루틴이 어디에 있는지 알 수 있으며, 프로세스들에게 같은 메모리 주소를 접근할 수 있게 한다.

8.2. 스와핑(Swapping)

프로세스가 실행되기 위해서는 메모리에 있어야 하지만, 실행 중 임시로 예비 저장장치(backup store)로 이동했다가 돌아올 수 있다. 모든 프로세스의 물리 주소 크기의 총합이 시스템의 실제 물리 메모리 크기보다 큰 경우에도 스와핑을 통해 동시에 실행하는 것이 가능하다.

8.2.1. 기본 스와핑(Standard Swapping)

디스패처(dispatcher)는 준비 완료 큐(ready queue)에 있는 프로세스를 호출할 때, 메모리에 있는지 확인한다. 만약 없다면 디스크에서 불러들여야 한다.

하지만 디스크 전송 시간때문에 문맥 교환 시간이 상당히 오래 걸린다. 그렇기에 실제로 사용하는 부분만 스왑해야한다. 따라서 동적인 메모리를 요구하는 시스템에서는 운영체제에게 메모리 요구사항의 변화를 알려줄 수 있는 시스템 호출이 필요하다.

스와핑은 입출력 대기 중인 프로세스를 대상으로 할 때 두 가지 해결 방법이 있다. 입출력 내용이 엉망이 되기 때문에 프로세스를 스왑하지 않거나, 입출력을 프로세스로 직접 하지 말고 운영체제의 버퍼와 하는 것이다. 하지만 운영체제의 버퍼를 사용하면 커널 메모리에서 사용자 메모리로 다시 한번 복사되어야 한다.

현대 운영체제는 기본 스와핑을 사용하지 않는다.

8.2.2. 모바일 시스템에서의 스와핑

iOS와 Android 에서는 대부분 스와핑보다는 페이징(8.5절)을 사용한다.

8.3. 연속 메모리 할당(Contiguous Memory Allocation)

초기 메모리 할당 방법 중 하나인 연속 메모리 할당 시스템에서, 각 프로세스가 담긴 영역은 다음 프로세스의 메모리 영역에 인접해 있다.

8.3.1. 메모리 보호(Memory Protection)

논리 주소는 재배치 레지스터의 값과 더해져 물리 주소가 된다. 물리 주소로 변환되기 전에, 논리 주소가 상한 레지스터의 값보다 작음을 확인함으로써 메모리를 보호할 수 있다.

8.3.2. 메모리 할당(Memory Allocation)

가장 간단한 메모리 공간 할당 방법은 메모리를 고정 크기로 분할하는 것이다. 각 분할에 한 프로세스가 들어가게 되지만, 현재는 사용되지 않는다.

가변 분할 기법에서는 메모리에 다양한 크기의 자유 공간들이 존재한다. 자유 공간을 할당, 회수, 그리고 인접한 자유 공간들을 하나로 합칠 수 있다.

자유 공간들에 n-바이트 블록을 할당하는 일반적인 방법은 다음과 같다.

최초 적합
- 첫 번째 사용 가능한 자유 공간을 할당한다.
최적 적합
- 모든 자유 공간을 탐색해 프로세스가 들어갈 수 있는 가장 작은 자유 공간을 할당
최악 적합
- 모든 자유 공간을 탐색해 가장 큰 자유 공간을 할당, 쓰지 않는다.

8.3.3. 단편화(Fragmentation)

가변 분할 기법에서는 자유 공간 중 일부가 사용 못하게 되는 경우가 생긴다.

외부 단편화(external fragmentation)는 자유 공간이 분산된 채로 너무 작아졌을 때 발생한다. 프로세스를 올릴만한 충분한 자유 공간이 생기지 않는다.

내부 단편화(internal fragmentation)는 할당된 자유 공간이 프로세스가 요구한 블록의 크기보다 클 때, 남은 공간이 사용되지 못하는 것이다. 일반적으로 메모리를 작은 공간으로 분할하고, 분할된 크기의 정수 배로 할당하기 때문에 생긴다.

외부 단편화의 한 해결 방법은 압축(compaction)이다. 프로세스들의 재배치가 실행 시간에 동적으로 가능할 때 가능하다. 프로세스들의 기준 레지스터 값을 변경하여 모든 프로세스를 메모리의 한쪽 끝으로 이동시켜 분산된 자유 공간을 합친다.

8.4. 세그먼테이션(Segmentation)

8.4.1. 기본 방법

프로그램을 여러 세그먼트(함수, 스택, 심볼 테이블 등)으로 나누어 관리한다. 따라서 프로세스가 적재되는 물리 주소 공간이 연속적이지 않아도 된다.

각 세그먼트내의 요소들은 세그먼트 시작 주소로부터 몇 번째 바이트로 관리된다. 구현을 쉽게 하기 위해서 세그먼트 이름 대신에 세그먼트 번호가 시스템에 의해 매겨진다. 따라서 논리 주소는 <segment-number, offset>으로 구성된다.

8.4.2. 하드웨어

segment-number와 offset으로 구성된 2차원 논리 주소는 1차원의 물리 주소로 바뀌어야 한다. 이에 기준/한계 레지스터의 쌍으로 이루어진 세그먼트 테이블이 사용된다.

먼저 테이블에서 segment-number에 해당하는 기준/한계 값을 가져온다. offset이 한계 값보다 크면 트랩을 발생시키고, 아니라면 기준 값과 더해 물리 주소를 생성한다.

8.5. 페이징(Paging)

페이징은 세그먼테이션의 장점에 더해 외부 단편화를 방지한다. 또한 스왑 아웃되는 다양한 크기의 세그먼트를 예비 저장장치에 저장해야할 필요도 없다.

8.5.1. 기본 방법

물리 메모리는 프레임(frame)이라 불리는 같은 크기의 블록으로 나누어진다. 논리 메모리는 페이지(page)라 불리는 같은 크기의 블록으로 나누어진다. 예비 저장장치는 메모리 프레임 혹은 프레임의 묶음인 클러스터와 동일한 크기의 블록으로 나누어진다.

논리 주소에는 페이지 번호와 페이지 변위(offset)가 있다. 페이지 번호로 페이지 테이블에 접근하여 물리 메모리 주소를 얻어온다. 이것과 페이지 변위를 더해 원하는 물리 주소를 계산한다.

모든 프레임이 프로세스에게 할당될 수 있기 때문에 외부 단편화는 해결된다. 하지만, 할당이 항상 프레임의 정수 배로 되기 때문에 내부 단편화는 남아있다.

프로세스가 실행되기 위해 도착하면 그 프로세스의 크기가 페이지 몇 개 분에 해당하는지를 조사한다. 그리고는 프로세스의 페이지를 차례대로 프레임에 적재하고 페이지 테이블에 기록한다.

논리 주소에서 물리 주소로의 변환은 하드웨어와 운영체제의 의해 조정된다. 따라서 사용자 프로세스는 자기의 것이 아닌 메모리는 접근조차 할 수 없다.

운영체제가 메모리를 관리하기 위해서 프레임 테이블이라는 자료구조를 사용한다. 여기에는 어느 프레임이 할당되어 있고, 어느 프레임이 사용 가능한지, 총 프레임은 몇개인지가 기록되어있다.

운영체제는 프로세스마다 페이지 테이블의 복사본을 유지한다. 이는 프로세스가 CPU에 할당될 때마다, 디스패처가 하드웨어 페이지 테이블을 결정할 때 사용한다. 따라서 페이징은 문맥 교환 시간을 증가시킨다.

8.5.2. 하드웨어 지원

페이지 테이블의 하드웨어 구현 중 가장 간단한 방법은 레지스터의 집합을 사용하는 것이다. 하지만 대부분 레지스터는 작고, 페이지 테이블이 수백만을 넘을 만큼 커서 불가능하다.

따라서 페이지 테이블을 주 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR, Page-Table Base Register)로 페이지 테이블을 가르킨다. 다른 페이지 테이블을 사용하려면 이 레지스터 값만 변화시키면 되므로 문맥 교환 시간을 줄일 수 있다. 그러나 이 방식에서는 메모리에 있는 페이지 테이블 접근(1), 계산한 주소로 메모리 접근(2), 2번의 메모리 접근이 필요해 너무 느리다.

이 문제에 대한 해결에는 TLB(Translation Look-aside Buffers)라고 불리는 특수한 소형 하드웨어 캐시가 사용된다. TLB는 매우 빠른 연관 메모리(associative memory)로 구성된다. TLB의 각 항목은 키(key)와 값(value)로 구성된다.

페이지 번호가 TLB에 있으면 바로 메모리 참조가 가능하고, 없으면(TLB miss) 메모리에서 페이지 번호를 가져온다. TLB가 가득 차 교체할 항목을 정할 때는 LRU, 라운드 로빈 등 다양한 정책이 사용된다.

어떤 TLB에는 ASIDs(address-space identifiers)를 저장하기도 한다. ASID는 TLB의 항목이 어느 프로세스에 속한 것인지를 알려주며, 이는 프로세스를 보호하는데 사용된다.

TLB를 통해 가상 주소를 변환할 때, 현재 프로세스의 ASID가 TLB 항목의 ASID와 동일한지 검사한다. ASID가 맞지 않는다면 TLB miss로 처리한다.

또한 ASID 지원이 있으면 한 TLB 안에 여러 프로세스들의 정보를 동시에 저장할 수 있다. ASID가 없으면 새로운 페이지 테이블이 선택될 때마다 TLB를 전부 플러시(flush)해야 한다. 이전 프로세스가 사용하던 페이지 번호가 TLB에 남아있을 수 있기 때문이다.

8.5.3. 보호

메모리 보호는 프레임과 연관된 보호 비트(protection bits)로 수행하며, 일반적으로 페이지 테이블에 있다. 각 비트는 페이지가 읽기-쓰기 혹은 읽기 전용임을 정의할 수 있다.

페이지 테이블에는 유효/무효(valid/invalid)비트도 있다. 이 비트가 유효하면 그 페이지는 프로세스의 논리 주소 공간에 속하기에 사용 가능하다.

몇몇 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(PTLR, Page Table Length Register)를 제공한다. 프로세스가 제시한 주소가 유효한 범위 내에 있는지 확인하기 위해 PTLR 값과 비교된다.

8.5.4. 공유 페이지(Shared Pages)

페이징의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 점이다. 프로세스들의 페이지 테이블이 재진입 가능 코드(reentrant code 또는 pure code)를 가르키면 된다.

재진입 가능 코드는 수행하는 동안 절대로 변하지 않는다. 따라서 여러 프로세서들이 동시에 같은 코드를 수행하여도 항상 같은 실행 결과를 얻을 수 있다.

공유가 가능한 프로그램에는 컴파일러, 윈도우 시스템, 실시간 라이브러리 등이 있다. 공유 코드는 읽기 전용 특징과 운영체제를 통해 보호한다.

8.6. 페이지 테이블의 구조

8.6.1. 계측적 페이징(Hierarchical Paging)

현대 컴퓨터는 매우 큰 주소 공간(2³²~2⁶⁴)을 가진다. 페이지 크기가 4KB(2¹²)라면 페이지 테이블은 100만(2³²/2¹²)개의 항목을 가진다. 각 항목이 4byte 라면 4MB 공간이 필요하게 된다. 즉, 모든 페이지 테이블을 주 메모리에서 연속적으로 할당하긴 힘들다.

한 방법은 2단계 페이징 기법(two-level paging scheme)으로서 페이지 테이블 자체가 다시 페이지화 되는 것이다. 이 경우 논리 주소는 <바깥 페이지 번호, 안쪽 페이지 번호, 페이지 변위>가 된다. 이 방법으로 페이지 테이블을 나눔으로써, 운영체제는 프로세스가 이 분할들을 실제로 필요할 때까지 사용하지 않은 채로 남겨둘 수 있다.

하지만 64비트 주소 공간에서는 여전히 페이지 테이블 크기가 크다. 7단계 페이징 기법을 사용할 수도 있지만, 메모리 접근이 너무 많아지기 때문에 쓰지 않는다.

8.6.2. 해시 페이지 테이블(Hashed Page Tables)

주소 공간이 32비트보다 커지면 가상 주소를 해시하는 해시 페이지 테이블을 많이 쓴다. 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있다. 같은 해시 값을 가지는 주소들이 연결되어 있으며, 각 원소는 <페이지 번호, 프레임 번호, 다음 원소 포인터>로 이루어진다.

논리 주소의 페이지 번호를 해싱하여 해시 페이지 테이블에 접근한다. 해당 해시에 속하는 연결 리스트를 따라가면서, 일치되는 경우 프레임 번호를 가져와 물리 주소를 생성한다.

클러스터 페이지 테이블이란 변형 기법도 있다. 해시 페이지 테이블의 각 항목은 한개의 페이지만 가르키지만, 클러스터 페이지 테이블의 각 항목은 여러 페이지를 가르킬 수 있다.

8.6.3. 역 페이지 테이블(Inverted Page Table)

보통 프로세스마다 페이지 테이블을 가지고 있다. 따라서 많은 메모리 공간이 필요하다. 이 문제를 해결하는 한 방법이 역 페이지 테이블이다.

이는 메모리 프레임마다 한 항목씩을 할당한다. 각 항목에는 <프로세스 ID, 페이지 번호, 페이지 변위>가 있다. 물리 프레임에 대응되는 항목만 테이블을 저장하기 때문에 적은 메모리 공간을 사용한다.

역 페이지 테이블은 물리 주소에 따라 정렬되어 있고, 탐색은 가상 주소를 기준으로 하기 때문에 탐색이 오래 걸릴수 있다. 따라서 속도 개선을 위해 해시 테이블, TLB 등이 추가적으로 활용된다.

역 페이지 테이블의 단점 중 하나는 메모리 공유가 어렵다는 점이다. 보통 메모리 공유에서는 여러 개의 가상 주소가 하나의 물리 주소를 가르킨다. 그러나 역 페이지 테이블은 하나의 물리 주소에 대해 하나의 가상 주소만을 가지기에 물리 주소가 공유될 수 없다.

8.6.4. Oracle SPARC Solaris

Solaris는 여러 단계의 페이지 테이블을 사용하며, 물리 메모리를 많이 쓰지 않기 위해 두 개의 해시 테이블을 사용하였다. 하나는 커널용이고, 다른 하나는 사용자 프로세스용이다.

그리고 페이지 테이블의 각 항목은 페이지 하나가 아닌 연속된 가상 메모리 영역을 나타낸다. 즉, 각 항목은 기준 주소와 이 항목이 나타내는 페이지의 개수를 나타내는 범위를 가진다.

해시 테이블을 탐색하는 것은 시간이 많이 걸리기 때문에 하드웨어의 도움이 필요하다. 변환 테이블 항목(TTE, Translation Table Entries)를 가지고 있는 TLB를 사용한다. TTE의 캐시는 변환 저장 버퍼(TSB, Translation Storage Buffer)에 있으며, 최근에 접근된 페이지의 항목을 저장한다.

가상 주소 참조가 발생하면 TLB에서 검색하며, 발견되지 않으면 TSB에서 찾는다. TSB에서 발견되면 TLB로 복사하고 메모리 주소 변환이 끝난다. TSB에서도 찾지 못하면 해시 테이블을 탐색하고 TTE, TSB에 저장한다.