메모리 관리 | Operating System

배경

전형적인 명령어 실행 순서는 다음과 같다.

CPU는 PC(program counter)를 보고 메모리에서 해당 주소의 명령을 가져온다.
명령을 해독하고 메모리에서 피연산자를 가져온다.
명령 실행 결과를 메모리에 저장한다.

기본 하드웨어

CPU에 내장되어 있는 레지스터는 클록당 하나 이상의 명령을 수행할 수 있을 정도로 빠르다. 하지만 메모리는 물리적인 거리도 멀고 느리기 때문에 CPU가 메모리를 기다려야 하는 메모리 멈춤(memory stall) 현상이 발생한다. 그래서 캐싱에서 설명한 것처럼 CPU와 메모리 사이에 메모리보다 빠른 캐시를 두어 CPU가 기다리는 시간을 줄인다.

사용자는 커널 메모리 영역이나 다른 사용자의 메모리 영역을 침범해서는 안된다. 운영체제는 상대적으로 느리기 때문에 메모리 영역을 보호하는 것은 하드웨어적으로 지원해야 한다. 메모리에는 여러 프로세스가 올라가고, 프로세스들은 base와 limit 레지스터를 가진다. 예를 들어 base=10, limit=15인 프로세스가 있다면 해당 프로세스는 10~24까지의 메모리 주소에만 접근할 수 있다. CPU는 하드웨어적으로 레지스터를 비교하고 만약 침범했다면 운영체제에게 알려 트랩을 발생시킨다.

커널 영역에서는 메모리 영역에 제한을 받지 않는다. 이 방법은 운영체제만 덤프를 만들거나 입출력을 제공할 수 있도록 하고, 사용자의 접근을 막을 수 있다.

주소 할당

프로그램은 디스크에 저장되어 있다. 프로그램을 실행하면 디스크에 저장된 데이터는 메모리로 올라와 프로세스가 된다. 프로세스는 디스크와 메모리 사이를 오갈 수 있고, 디스크에서 메인 메모리로 올라오는 프로세스는 입력 큐에서 먼저 대기한다.

아래 그림은 실제 프로그램이 메모리에 적재되기까지의 과정이다.

소스 프로그램 : 주소는 숫자가 아닌 심볼(변수 이름)로 표현된다.
컴파일러 : 심볼을 재배치 가능 주소(이 모듈의 시작점으로부터 10~25바이트까지)로 바인딩한다.
링키지 편집기 / 적재기 : 재배치 가능 주소를 절대 주소(270번째 바이트)로 바인딩한다.

모듈에 어떻게 바인딩을 하는지 간단하게 보자.

컴파일 시간 바인딩 : 프로세스가 메모리에 들어갈 시작점을 안다면 컴파일러는 절대 코드를 생성할 수 있다. 대부분 모르기 때문에 소스 프로그램을 재배치 가능한 코드로만 바꿔서 넘긴다.
적재 시간 바인딩 : 재배치 가능한 코드를 절대 주소로 바꿔 실행한다.
실행 시간 바인딩 : 프로세스 실행 중 세그먼트가 쪼개졌을 때, 해당 절대 주소로 바인딩을 한다. 하드웨어가 지원해야 한다.

논리 vs 물리 주소 공간

CPU가 취급하는 주소를 논리 주소라 하고, 메모리가 취급하는 주소를 물리 주소 혹은 메모리 주소 레지스터(MAR)라고 한다. 또한 실행 시간 바인딩에서 여러 개로 쪼개진 세그먼트를 하나로 보이게 만들어 제공하는 논리 주소를 가상 주소라 한다. 프로그램이 만드는 물리 주소 공간은 물리 주소 공간에 대응된다.

가상 주소를 물리 주소로 바꾸는 작업은 메모리 관리기(MMU) 하드웨어가 한다. MMU 관리 기법은 나중에 자세히 배우고 여기서는 아주 단순화시켜보자. MMU는 기준 레지스터 혹은 재배치 레지스터를 가지고 있다. CPU가 123번 주소를 요청하면 MMU는 123에 재배치 레지스터를 더해 실제 물리 주소를 구한다. MMU가 중간에서 변환해주기 때문에 응용 프로그램은 절대 물리 주소를 알지 못 한다.

동적 적재

프로세스를 전부 메모리에 올리면 비효율적이다. 호출한 루틴만 메모리에 올리고 나머지는 재배치 가능한 상태로 디스크에 대기하는 것이 더 효율적이다. 이 방식을 동적 적재라 한다. CPU가 호출한 루틴이 메모리에 없으면 재배치 가능한 연결 적재기를 호출해 필요한 루틴을 메모리로 가져온다. 동적 적재는 운영체제의 지원을 굳이 필요로 하지 않는다. 운영체제의 라이브러리 루틴을 사용할 수는 있지만 사용자가 프로그램의 설계를 책임져야 한다.

동적 연결 & 공유 라이브러리

동적 연결은 여러 프로그램에 필요한 라이브러리를 런타임에 링킹하는 것이다. 이와 반대로 정적 연결은 컴파일 타임에 링킹을 하게 되는데, 이 경우 같은 라이브러리가 중복해서 메모리에 올라갈 수 있기 때문에 비효율적이다. 주로 시스템 라이브러리를 공유할 때 주로 쓰면 위 그림에서도 확인할 수 있다. 동적 연결에서는 프로그램마다 스텁이 생긴다. 스텁은 시스템 라이브러리의 위치를 아는 코드 조각으로, 프로그램이 호출을 하면 스텁을 통해 실제 시스템 라이브러리가 있는 곳을 찾아서 실행하게 된다. 만약 메모리에 없다면 디스크에서 가져오기도 한다.

이렇게 프로그램들이 같이 참조하며, 버전으로 관리되는 라이브러리를 공유 라이브러리라 한다.

스와핑

메모리를 최대한으로 쓰는 방법에는 두 가지가 있다.

프로세스의 크기를 최대한 줄인다. (동적 적재, 동적 연결)
메모리의 크기를 가상으로 늘린다. 디스크의 일부도 메모리처럼 써보자.

프로세스의 일부를 백업 장치에다 임시로 저장해놨다가 필요할 때 다시 메모리로 올리는 것을 스왑이라 한다. 이렇게 하면 실제 물리 메모리보다 더 크게 쓸 수 있고 다중 프로그래밍의 정도를 증가시킨다.

기본 스와핑

CPU가 준비 큐(ready queue)에서 다음 프로세스를 선택하면 디스패처를 호출한다. 디스패처는 프로세스가 메모리에 있는지 확인하고 없으면 디스크에서 메모리로 스왑 인한다. 만약 메모리 공간이 부족하면 안쓰는 프로세스 하나를 메모리에서 디스크로 스왑 아웃한다. 그러고 나서 메모리에서 선택된 프로세스를 CPU 레지스터에 적재하고 제어를 프로세스에게 넘긴다.

스와핑은 메모리와 디스크를 넘나들기 때문에 문맥 교환시간이 상당히 길다. 특히 디스크의 저장/로딩 시간이 매우 길기 때문에 최대한 효율적으로 스왑해야 한다. 이를 위해 동적인 메모리 시스템에서는 사용자가 운영체제에게 시스템 호출을 통해 메모리 요구사항을 알려준다.(requeset/release_memory)

스와핑은 완전히 아무것도 하지 않는 프로세스를 대상으로만 가능하다. 만약 block 상태인 프로세스를 스왑 아웃했다면, 입출력 시스템은 아무것도 모른채 원래 프로세스가 있었던 메모리 주소에서 입출력을 사용하려 할 것이다. 이 문제에 대한 해결책은,

입출력이 종료되지 않은 프로세스를 스왑하지 않거나,
입출력은 항상 프로세스로 직접하지 않고 운영체제의 버퍼와만 하도록 한다. 나중에 프로세스가 스왑 인이 되면 그때 버퍼의 값을 전달한다. 다만, 이 방식은 이중 버퍼링이기 때문에 오버헤드가 크다.

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

모바일 시스템의 스와핑

일반적으로 모바일 시스템은 스와핑을 지원하지 않는다. 이유는, 모바일은 디스크 대신 플래시 메모리를 주로 사용하는데 플래시 메모리에는 최대 쓰기 횟수가 정해져 있기 때문이다. 대신, iOS의 경우 프로그램 코드 같은 읽기 전용 데이터를 시스템에서 제거하고 나중에 다시 적재하는 방식으로 메모리를 사용한다. Android는 iOS와 비슷한 정책을 쓰는 것에 더해, 메모리가 부족해 프로세스를 종료할 때면 해당 프로세스의 상태를 플래시 메모리에 저장해 놓고 나중에 빠르게 복구하는 전략을 쓴다.

연속 메모리 할당

지연 시간 최소화 에서 설명한 ISR의 시작 주소를 인터럽트 벡터라 한다. 인터럽트 벡터는 보통 메인 메모리의 0번째 주소에 위치했었기 때문에 운영체제도 하위 메모리에 위치해 있었다. 따라서 운영체제가 하위 메모리에 있는 경우만을 설명한다. 실제로는 어디에 있든 상관없다.

입력 큐에 대기하고 있는 프로세스들에게 얼마만큼의 메모리를 할당할 것인가를 고민해봐야 한다. 연속 메모리 할당 시스템에서는 프로세스는 다음 프로세스의 영역 바로 다음에 연속해서 위치한다.

메모리 보호

기본 하드웨어 에서 limit 레지스터를, 논리 vs 물리 주소 공간 에서 재배치 레지스터를 배웠다. 이 둘을 연결하면 자신의 메모리 영역 외의 접근을 차단하면서 실제 물리 주소에 접근할 수 있게 된다.

디스패처는 limit 레지스터와 재배치 레지스터에 값을 싣고, CPU는 매번 위 과정을 거쳐서 안전한지 확인한다. 프로세스가 실행 중이더라도 재배치 레지스터를 변경할 수 있기 때문에 운영체제의 크기를 최대한 작게 가져갈 수 있다. 예를 들어, USB를 한동안 쓰지 않는다면 USB 관련 코드를 메모리에서 제거하는 것이 더 효율적이다. 이런 코드를 일시적 운영체제 코드라 한다.

메모리 할당

이 파트에서 프로세스는 하나의 메모리 덩어리에 담겨야 한다. 쪼개져서 담길 수 없다!

고정 분할 기법

메모리를 여러 구역으로 나눠보자. 가장 쉬운 방법은 고정된 크기의 파티션으로 분할하는 것이다. 각 파티션마다 하나의 프로세스가 들어가고, 파티션의 개수를 다중 프로그래밍 정도라고 부른다. 다중 프로그래밍의 정도는 장기 스케줄러 (잡 스케줄러)에서 설명했었다.

가변 분할 기법

운영체제는 메모리의 사용여부를 적어놓은 테이블을 만든다. 초기에는 하나의 큰 빈 구멍이 있겠지만 프로세스를 넣었다 뺐다 하면서 여러 개의 구멍으로 나뉘게 된다. 운영체제는 알고리즘에 따라 입력 큐의 프로세스를 적절한 구멍에다 넣는다. 만약 구멍의 공간이 너무 작다면 작은 공간에 알맞는 프로세스를 입력 큐에서 찾아 넣는다.

이 방법은 시간이 지나면 작은 구멍이 송송 뚫린 형태가 된다. 10MB 짜리 구멍에 4MB 프로세스를 넣는다면 6MB의 공간이 남는다. 만약 해당 프로세스를 메모리에서 없앤다면, 4MB 구멍과 6MB 구멍은 합쳐서 다시 10MB 짜리 구멍이 된다.

다음은 운영체제가 구멍을 선택하는 일반적인 알고리즘이다. First-fit이 일반적으로 속도가 빠르고, 다음은 Best-fit이다.

First-fit : 사용 가능한 구멍 중 가장 앞에 있거나 최근 할당한 구멍 바로 앞에 있는 구멍에 넣는다.
Best-fit : 최대한 프로세스의 크기와 딱 맞는 구멍에 넣는다.
Worst-fit : 최대한 남는 공간이 많은 구멍에 넣는다.

단편화 (Fragmentation)

외부 단편화 : 가변 분할 기법처럼 메모리에 작은 구멍이 송송 뚫려 아무 프로세스도 들어가지 못 하는 공간
내부 단편화 : 고정 분할 기법처럼 프로세스가 쓰지 않고 불필요하게 할당된 공간

외부 단편화를 해결하는 방법 중 하나로 압축(compaction)이 있다. 메모리를 한 쪽으로 몰아서 꾹꾹 눌러담는 방법이다. 재배치 작업은 프로그램과 데이터를 옮기고 base 레지스터의 값만 바꾸면 완료된다. 하지만 알고리즘에 따라 비용이 비쌀 수 있다.

또다른 방법으로는 한 프로세스를 여러 개로 쪼개 빈 곳에 채워넣는 방법이다. 여러 개로 쪼갠 위치를 알아야 하기 때문에 위치를 표시하는 테이블이 필요하다.

세그먼테이션

앞서 말한 한 프로세스를 여러 개로 쪼개 빈 곳에 넣는 방법이다.

기본 방법

하나의 프로세스는 기본적으로 5가지 영역으로 나눌 수 있다.

코드 영역
데이터 영역 (전역 변수, 정적 변수)
힙 영역 (사용자가 동적으로 할당하는 변수)
스택 영역 (지역 변수, 매개 변수)
표준 C 라이브러리

그러면 이걸 굳이 한 군데에 꾸역꾸역 몰아서 넣을 필요는 없지 않을까? 각각의 영역을 개별적으로 메모리에 할당하면 된다!

세그먼테이션(Segmentation)은 프로그래머가 생각하는 그대로 메모리를 관리하는 기법이다. 각 세그먼트는 세그먼트 고유번호와 오프셋을 갖는다. C 컴파일러의 경우 위의 다섯 영역을 세그먼트로 만들 것이다. 컴파일 타임에 링크되는 라이브러리는 별도의 세그먼트에 할당하고, 로더는 이런 세그먼트에 번호를 매긴다.

하드웨어

이제 CPU가 세그먼트 번호와 오프셋을 요청하면 하드웨어적인 과정을 거쳐 정확한 물리 메모리를 찾아 값을 가져와야 한다. 아래 그림처럼 세그먼트 테이블에 limit과 base를 저장해두고 실제 물리 메모리 위치를 찾아 간다.

페이징

페이징 기본 방법

물리 메모리를 같은 크기의 프레임으로 나누고, 논리 메모리는 같은 크기의 페이지로 나눈다. 프레임과 페이지의 크기는 무조건 2의 지수여야 한다. CPU는 페이지 번호와 오프셋을 요청하면 하드웨어적인 과정을 거쳐 정확한 물리 메모리 위치를 찾아 간다.

모든 페이지는 프레임에 딱딱 맞아 떨어진다. 그래서 외부 단편화가 전혀 발생하지 않는다. 하지만 내부 단편화는 발생한다. 내부 단편화를 최소화 하려면 페이지의 크기를 줄이면 되지만 그러면 페이지 테이블의 크기가 커지게 될 것이고 이것도 낭비다. 또한 페이지가 클 수록 디스크에 저장할 때 효율적이다(이유는 대용량 저장장치 구조 참조). 또한 논리 메모리는 물리 메모리보다 더 클 수 있다. 예를 들어 32 비트 CPU에서는 물리 메모리 크기가 어떻든 간에 논리 메모리는 $2^{32}$(4GB)까지 만들 수 있다.

처음 실행된 프로세스는 필요한 만큼 페이지를 요구하고 운영체제가 프레임을 할당해주면 PCB에 페이지 테이블을 만든다. 이 방법을 쓰면 프로그래머는 데이터가 실제 어떻게 저장되는지 상관없이 연속된 메모리 공간을 보게 된다. 이것이 세그먼테이션과 가장 큰 차이다. 프로그래머는 그냥 연속된 논리 메모리만 신경 쓰면 되고 나머지는 운영체제와 하드웨어가 다 알아서 해준다.

운영체제는 프레임을 관리해야 하기 때문에 프레임 테이블에 이러한 정보를 저장한다. 프레임 테이블에는 사용 가능한 프레임, 각 프레임별로 할당된 프로세스 등의 정보가 저장된다. 또 운영체제는 논리 주소와 물리 주소를 왔다갔다 할 수 있어야 한다. 프로세스가 시스템 호출을 하면 매개변수를 정확한 물리 주소에서 찾아야 하기 때문이다. 그래서 운영체제는 각 프로세스의 페이지 테이블 복사본을 가지고 있다.

논리 주소로 물리 주소를 알아내는 과정의 오버헤드기 때문에, 문맥 교환 시간이 증가하는 단점이 있다.

하드웨어 지원

레지스터로 만들기

페이지 주소 변환을 빠르게 하기 위해서 페이지 테이블을 레지스터에 싣는 방법이 있다. 하지만 문맥을 교환할 때 레지스터를 채워줘야 하기 때문에 오버헤드가 발생한다. 또 레지스터는 비싸기 때문에 페이지 테이블이 작은 경우에만 적합한 방법이다. 따라서 백 만 개 이상의 정보를 저장하는 대부분 운영체제에는 적합하지 않다.

페이지 테이블 기준 레지스터(PTBR)

그래서 페이지 테이블은 메모리에 저장하고 메모리의 주소만 레지스터에 저장하는 방법이 생겼다. 이 방법을 쓰면 레지스터를 하나만 쓰기 때문에 문맥 교환 시간이 준다. 하지만 이러면 메모리에 접근하기 위해 메모리에 접근하는 것이 된다. 두 배로 느린 이 방법은 부적합하다.

TLB(Translation Look-aside Buffers)

Key-value을 저장하기 위한 특수한 하드웨어 캐시이다. 해싱 알고리즘을 쓰기 때문에 전체 성능에 거의 영향을 미치지 않고, TLB를 겹쳐서 여러 층의 캐시로 사용할 수도 있다. TLB는 페이지 테이블의 일부만 저장한다. 만약 원하는 페이지 번호가 저장되어 있지 않으면(TLB 미스), 인터럽트를 걸고 메모리에서 값을 가져온다. TLB가 가득차면 알고리즘에 의해 몇몇 값들은 교체된다. LRU, RR 등 다양한 알고리즘을 쓸 수 있는데, 중요한 커널 코드의 경우 TLB에 고정시켜 교체되지 못 하게 할 수도 있다.

TLB 미스와 반대로 TLB에서 값을 찾는 것을 적중(hit)한다고 한다. 적중률(p)과 실제 메모리 접근 시간(t)을 고려하면 CPU에서 페이지 정보를 찾는데 걸리는 시간은 다음과 같다. 적중률이 보통 99%이므로 메모리에 접근하는 거보다 약 1% 정도만 더 소요된다.

$$ p \times t + (1-p) \times2t $$

TLB & ASID(Address-Space IDentier)

어떤 TLB는 각각의 값이 어느 프로세스에 속하는지를 알려주는 ASID를 저장하기도 한다. 페이지 테이블을 참조할 때 ASID와 프로세스의 정보가 맞지 않으면 TLB 미스로 처리한다. ASID가 없다면 문맥 교환을 해서 프로세스가 바뀔 때마다 TLB를 매번 비워야 한다. 그렇지 않으면 이전 프로세스의 정보와 중복이 될 수 있다.

보호

페이지를 보호가 위해 몇 가지 정보를 페이지 테이블에 추가할 수 있다.

보호 비트 : 페이지에 쓰기가 가능한지 여부를 표시한다. 읽기 전용 페이지에 쓰기를 시도하면 트랩을 날린다.
유효-무효 비트 : 프레임이 할당된 페이지를 표시해 엉뚱한 페이지에 접근하는 것을 방지한다.

이 외에 몇몇 시스템은 페이지 테이블 길이 레지스터(PTLR)를 둔다. 내부 단편화에 의해 만들어진 페이지 내의 빈 공간에 접근 하는 것을 막기 위해 페이지의 길이를 정확히 표시한다.

공유 페이지

프로그램의 재진입 가능 코드(순수 코드)는 변경되지 않으니 여러 프로세스가 같이 공유해도 상관 없다. 따라서 이 부분만 특정 프레임에 넣고 프로세스들는 이 프레임을 동시에 페이지에 넣을 수 있다. 물론 PC나 여타 레지스터, 데이터 부분은 각자 따로 저장한다. 이 방식은 공유 메모리 시스템 IPC의 메모리 공유 방식과 흡사하다.

페이지 테이블 구조

계층적 페이징

페이지 테이블의 크기가 점점 커지면서 메모리에 연속적으로 저장하기 부담스러워진다. 따라서 페이지 테이블을 쪼개서 여러 군데 나눠서 저장한다. 그리고 흩어진 페이지 테이블을 참조하고 있는 outer 페이지 테이블을 둔다. 그럼 페이지 테이블의 구조와 논리 주소는 아래 그림처럼 된다.

이 방식의 가장 큰 단점은 64비트 주소 공간을 감당할 경우 7 계층 정도를 만들어야 하기 때문에 한도 초과다.

해시 페이지 테이블

페이지 테이블의 각 항목을 링크드 리스트로 만들고 해싱값별로 페이지 정보를 주렁주렁 매단다.

논리 주소에서 페이지 번호를 해싱한다.
해싱 값으로 페이지 테이블의 항목을 찾는다.
링크드 리스트를 따라가면서 정확한 페이지 번호를 가진 원소를 찾는다.
해당 원소의 프레임 번호를 가지고 실제 메모리에 접근한다.

해시 페이지 테이블이 한 개의 페이지만 가리키는 것에 반해, 한 번에 여러 개의 페이지를 가리켜 페이지 테이블의 크기를 줄이는 클러스터 페이지 테이블 방식도 있다. 이 방식은 CPU가 메모리를 비연속적이면서 듬성듬성 접근할 때 특히 유용하다.

역 페이지 테이블

지금까지의 방법은 페이지당 하나의 항목이나 요소가 필요했기 때문에 테이블 크기가 매우 크다. 이와 반대로, 프레임을 기준으로 테이블을 만들면 어떨까?

역 페이지 테이블은 프레임 번호를 인덱스로 테이블을 만든다. 각 항목은 ASID처럼 프로세스 id와 페이지 번호가 들어있다. 논리 주소가 들어오면 테이블을 검색해 pid와 페이지 번호가 일치하는 항목의 인덱스를 가져와 실제 프레임 번호를 찾는다. 이 방법은 페이지 테이블의 크기는 작지만 검색하는데 시간이 오래 걸릴 수 있다. 최악의 경우 페이지 전부를 검색해야 할 수 있다. 앞 단에 해시 테이블을 둬 검색량을 줄일 수도 있지만, 메모리 참조를 더 많이 하게 되는 딜레마도 극복해야 한다. 또한 일반적인 방법으로는 메모리 공유가 불가능하다. 메모리 공유를 위해 페이지 폴트 시에만 참조하는 확장된 페이지 테이블이라는 개념이 있다.

Sunghun Son / Operating System / 메모리 관리

배경