OS - 메인 메모리

1. 배경 

 

메인 메모리는 현대 컴퓨터 시스템의 운영에 중심적인 역할을 한다. 메모리는 각각 주소가 할당된 일련의 바이트들로 구성된다. CPU는 PC(program counter)가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져오는데 그 명령어는 필요한 경우 추거적인 데이터를 더 가져올 수 있으며 반대로 데이터를 메모리로 내보낼 수도 있다.

 

메모리는 주소에 지시한 대로 읽기 쓰기만 할 뿐 이 주소들이 어떻게 생성되었는지 혹은 그 주소가 가리키는 내용이 무엇인지를 모른다. 따라서 주소가 프로그램에 의해서 어떻게 생성되었는지에 대한 세부 사항은 이 시점에서의 고려 대상이 아니다. 여기서는 프로그램에 의해서 생성되는 일련의 주소만 언급하기로 한다.

1.1 기본 하드웨어

메인 메모리와 각 처리 코어에 내장된 레지스터들은 CPU가 직접 접근할 수 있는 유일한 범용 저장장치이다. 기계 명령어들은 메모리 주소만을 인수로 취하고, 디스크의 주소를 인수로 취하지 않는다. 따라서 모든 실행되는 명령어와 데이터들은 CPU가 직접적으로 접근할 수 있는 메인 메모리와 레지스터에 있어야 한다. 만약 데이터가 메모리에 없다면 CPU가 그것들을 처리하기 전에 메모리로 이동시켜야 한다.

 

각 CPU 코어에 내장된 레지스터들은 일반적으로 CPU 클록(clock)의 1사이클(cycle) 내에 접근 가능하다. 그러나 메모리 버스를 통해 전송되는 메인 메모리의 경우는 앞에서 언급했던 상황과는 다르다. 

 

메인 메모리의 접근을 완료하기 위해서는 많은 CPU 클록 틱 사이클이 소요되며, 이 경우 CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고 지연되는 현상이 발생하게 된다. 이러한 상황은 메인 메모리의 접근이 빈번하게 일어나는 경우에는 용납이 될 수 없다. 

 

해결방법은 CPU와 메인 메모리 사이에 (통상 빠르게 접근할 수 있도록 CPU 안에) 빠른 속도의 메모리를 추가하는 것이다. 이것을 캐시 메모리라고 한다. 

 

물리 메모리의 상대적인 접근 속도의 차이를 고려하는 것에 추가로 올바른 동작을 보장해야만 한다.  시스템이 올바르게 동작하기 위해서는 사용자 프로그램으로부터 운영체제 영역을 보호해야 할 뿐만 아니라 사용자 프로그램 사이도 서로 보호해야 한다. 

 

운영체제가 CPU와 메모리 간의 접근 중에 개입하게 되면 성능이 떨어지기 때문에 이러한 보호 기법은 반드시 하드웨어가 지원하여야 한다. 

먼저 각각의 프로세스가 독립된 메모리 공간을 가지도록 보장해야 한다. 개별적인 프로세스별 메모리 공간은 서로를 보호하고 병행 실행을 위해 여러 프로세스가 메모리에 적재되게 하는 것이 필수적이다. 개별적인 메모리 공간을 분리하기 위해서 특정 프로세스만 접근할 수 있는 합법적인 메모리 주소 영역을 설정하고, 프로세스가 합법적인 영역만을 접근하도록 하는 것이 필요하다.

 

우리는 기준(base)와 상한(limit)이라고 불리는 두 개의 레지스터들을 사용하여 이러한 보호 기법을 제공한다. base 레지스터는 가장 작은 합법적인 물리 메모리 주소의 값을 저장하고, limit 레지스터는 주어진 영역의 크기를 저장한다. 

• base 레지스터 값이 300040이고, limit 레지스터 값이 120900이라면 프로그램은 30040에서 420940까지의 모든 주소를 접근할 수 있다.

메모리 공간의 보호는 CPU 하드웨어가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어진다. 사용자 모드에서 수행되는 프로그램이 운영체제의 메모리 공간이나 다른 사용자 프로그램의 메모리 공간에 접근하면 운영체제는 치명적인 오류로 간주하고 트랩(trap)을 발생시킨다. 이러한 기법은 사용자 프로그램이 운영체제나 다른 사용자 프로그램의 코드나 데이터 구조를 수정하는 것을 막는다.

 

base와 limit 레저스터는 여러 가지 특권 명령을 사용하는 운영체제에 의해서만 적재된다. 왜냐하면 특권 명령은 오직 커널 모드에서만 수행되고, 운영체제만 커널 모드에서 수행되기 때문이다. 이러한 기법은 운영체제만 레지스터들의 값을 변경할 수 있도록 허가해 줌으로써 사용자 프로그램이 레지스터의 내용을 변경하는 것을 막는다.

 

커널 모드에서 수행되는 운영체제는 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 어떠한 제약도 받지 않는다. 이러한 원칙 때문에 운영체제는 사용자 프로그램을 사용자 메모리 영역에 적재, 오류가 발생한 경우에 그 프로그램을 덤프(dump out), 시스템 콜의 매개변수를 변경, 사용자 메모리로부터의 입출력과 다른 많은 서비스를 제공할 수 있다. 

 

1.2 주소의 할당

 

프로그램은 원래 이진 실행 파일 형태로 디스크에 저장되어 있다. 실행하려면 프로그램을 메모리로 가져와서 프로세스 문맥내에 배치해야 한다. 이 시점에 가용한 CPU에서 실행할 수 있게 된다. 

 

대부분의 시스템은 사용자 프로세스가 메모리 내 어느 부분으로도 올라올 수 있도록 지원하고 있다. 사용자 프로세스의 주소가 00000번지부터 시작된다고 해서 이 프로그램이 메모리의 00000번지부터 올라와야 할 필요는 없다. 대부분의 경우 사용자 프로그램은 여러 단계를 거쳐 실행되기 때문에 이들 단계를거치는 동안 주소들은 여러 가지 다른 표현 방식을 거치게 된다. 

 

원시 프로그램에서 주소는 숫자가 아닌 심볼 형태로 표현된다. 컴파일러는 이 심볼 주소를 재배치 가능 주소로 바인딩 시키고, 다음에 링커나 로더가 재배치 가능 주소를 절대 주소(예를 들면 74014번지)로 바인딩시킨다. 각각의 바인딩 과정은 한 주소 공간에서 다른 주소 공간으로 맵핑하는 것이다. 

재배치 가능 코드(relocatable code)는 프로그램이 메모리의 특정 위치에 고정되지 않고, 메모리 어디에든 적재될 수 있도록 작성된 코드입니다. 즉, 프로그램이 실행될 때 어느 메모리 주소에 올라올지 미리 정해지지 않은 상태에서, 해당 메모리 주소에 맞춰서 필요한 부분을 동적으로 수정할 수 있는 코드를 말합니다.

 

전통적으로 메모리 주소 공간에서 명령어와 데이터의 바인딩은 그 바인딩이 이루어지는 시점에 따라 다음과 같이 구분된다.

• 컴파일 시간(compile time) 바인딩: 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다. 예를 들면 사용자 프로세스가 R번지로부터 시작한다는 것을 미리 알 수 있으면 컴파일러는 번역할 코드를 그 위치에서 시작해 나간다. 그러나 만일 이 위치가 변경되어야 한다면 이 코드는 다시 컴파일되어야 한다.
• 적재 시간(load time) 바인딩:  만일 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못하면 컴파일러는 일단 이진 코드를 재배치 가능 코드로 만들어여 한다. 이 경우에 심볼과 진짜 번지수와의 바인딩은 프로그램이 메인 메모리로 실제로 적재되는 시간에 이루어지게 된다. 이렇게 만들어진 재배치 가능 코드는 시작 주소가 변경되면 아무 때나 사용자 코드를 다시 적재하기만 하면 된다.
• 실행 시간(execution time) 바인딩: 만약 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면 우리는 바인딩이 실행 시간까지 허용되었다고 이야기한다. 이러한 것이 가능해지려면 특별한 하다웨어를 이용해야 한다.

이 장의 주요 요점은 컴퓨터 시스템에서 여러 가지 바인딩을 어떻게 효과적으로 구현할 수 있는가이며, 그를 위한 하드웨어 지원에 대해 언급하는 것이다.

 

1.3 논리 대 물리 주소 공간

 

CPU가 생성하는 주소를 일반적으로 논리 주소(logical address)라 하며, 반면에 메모리가 취급하게 되는 주소(즉, 메모리 주소 레지스터에 주어지는 주소)는 일반적으로 물리 주소(physical address)라 한다.

 

컴파일 또는 적재 시에 주소를 바인딩하면 논리 주소와 물리 주소가 같다. 그러나 실행 시간 바인딩 기법에서는 논리, 물리 주소가 다르다. 이러면 논리 주소를 가상 주소(virtual address)라 한다. 이 책에서는 논리 주소나 가상 주소나 같은 뜻으로 사용한다. 

 

프로그램에 의해 생성된 모든 논리 주소 집합을 논리 주소 공간(logical address space)이라 하며 이 논리 주소와 일치하는 모든 물리 주소 집합을 물리 주소 공간(physical addrss space)이라 한다. 

 

프로그램의 실행 중에는 이와 같은 가상 주소를 물리 주소로 바꾸어줘야 하는데 이 변환(mapping) 작업은 하드웨어 장치인 메모리 관리 장치(memory management unit, MMU)에 의해 실행된다. 

 

우선 여기에서는 base register기법을 일반화시킨 아주 단순한MMU 기법에 따른 변환을 설명할 것이다. 이제 base 레지스터를 재배치(relocation)레지스터라고 부른다. 재배치 레지스터 속에 들어있는 값은 주소가 메모리로 보내질 때마다 그 모든 주소에 더해진다. 예를 들어, 재배치 레지스터 값이 14000이라면 프로세스가 346번지에 엑세스할 때, 실은 메인 메모리의 14346번지에 엑세스하게 된다. 

 

사용자 프로그램은 346번지에 대한 포인터를 생성해서 그것에 대해 저장 연산, 다른 주소들과 비교하는 등 온갖 일을 할 수가 있다. 그러나 일단 그것이 주소로 갈 때는기준 레지스터에 대해 다시 바인딩 된다. 사용자 프로그램은 논리 주소를 사용한 것이고, 메모리 하드웨어는 논리 주소를 실제 주소로 바꾼 것이다. 따라서 참조된 메모리 주소의 실제 위치는 이 참조가 실제 실행 시간에 결정된다. 

 

이제는 두 가지 주소, 즉 논리 주소(0에서 max까지 범위)와 실제 주소(기준값 R에 대해 R+0에서 R+max까지 범위)가 있다는 사실에 유의하여야 한다. 사용자 프로세스는 단지 논리 주소만을 만들어낼 뿐이므로 주소가 메모리 위치 0에서 max위치까지만 있다고 생각할 것이다. 그러나 이들 논리 주소는 사용되기 전에 실제 물리 주소로 변환되어야만 한다. 

 

1.4 동적 적재

 

지금까지의 설명에서는 프로세스가 실행되기 위해 그 프로세스 전체가 미리 메모리에 올라와 있어야 했다. 이 경우 프로세스의 크기는 메모리의 크기보다 커서는 안 된다. 메모리 공간의 더 효율적 이용을 위해서는 동적 적재(dynamic loading)를 해야 한다. 동적 적재에서 각 루틴은 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기하고 있다. 먼저 main 프로그램이 메모리에 올라와 실행된다. 이 루틴이 다른 루틴을 호출하게 되면  호출된 루틴이 이미 메모리에 적재됐는지를 조사한다. 만약 적재되어 있지 않다면, 재배치 가능 연결 적재기(relocatable linking loader)가 불려 요구된 루틴을 메모리로 가져오고, 이러한 변화를 테이블에 기록해 둔다. 그 후 CPU 제어는 중단되었던 루틴으로 보내진다.

 

동적 적재의 장점은 루틴이 필요한 경우에만 적재된다는 것이다. 이러한 구조는 오류 처리 루틴과 같이 아주 간혹 발생하면서도 실행할 코드가 많은 경우에 특히 유용하다. 이러한 상황에서는 전체 프로그램 크기가 클 수 있지만 사용되는 부분이 훨씬 작을 수 있다.

 

동적 적재는 운영체제로부터 특별한 지원이 필요없다. 사용자 자신이 프로그램의 설계를 책임져야 한다. 운영체제는 동적 적재를 구현하는 라이브러리 루틴을 제공해 줄 수 있다.

 

1.5 동적 연결 및 공유 라이브러리

 

동적 연결 라이브러리(DLL)는 사용자 프로그램이 실행될 때, 사용자 프로그램에 연결되는 시스템 라이브러리이다. 어떤 운영체제는 정적 연결(static linking)만을 지원한다. 이러한 시스템에서는 라이브러리가 이 프로그램의 이진 프로그램 이미지(image)에 끼어 들어가게 된다. 반대로 동적 연결 개념은 동적 적재의 개념과 유사하다. 

 

동적 적재에서는 로딩(loading)이 실행 시까지 미루어졌었지만 동적 연결에서는 연결(linking)이 실행 시기까지 미루어지는 것이다. 동적 연결은 주로 표준 C 언어 라이브러이와 같은 시스템 라이브러리에 사용된다. 이 기능이 없으면 시스템의 각 프로그램은 실행 가능 이미지에 해당 언어 라이브러리의 사본을 포함해야 한다. 

 

DLL의 두 번째 장점은 이러한 라이브러리를 여러 프로세스 간에 공유할 수 있어 메인 메모리에 DDL 인스턴스가 하나만 있을 수 있다는 것이다. 이러한 이유로 DLL은 공유 라이브러리라고도 한다.

 

프로그램이 동적 라이브러리에 있는 루틴을 참조하면 로더는 DLL을 찾아 필요한 경우 메모리에 적재한다. 그런 다음 동적 라이브러리의 함수를 참조하는 주소를 DLL이 저장된 메모리의 위치로 조정한다. 

 

동적 적재와는 달리 동적 연결과 공유 라이브러리는 일반적으로 운영체제의 도움이 필요하다. 메모리에 있는 프로세스들이 각자의 공간은 자기만 엑세스할 수 있도록 보호된다면, 운영체제만이 기억 공간에 루틴이 있는지를 검사해 줄 수 있고 운영체제만이 여러 프로세스가 같은 메모리 주소를 공용할 수 있도록 해줄 수 있다.

 

2. 연속 메모리 할당

 

이 절에서는 초기 메모리 할당 방법의 하나인 연속 메모리 할당에 관해 설명한다.

 

메모리는 일반적으로 두 개의 부분으로 나누어지는데, 하나는 운영체제를 위한 것이며 다른 하나는 사용자 프로세스를 위한 것이다. 운영체제를 낮은 메모리 주소 또는 높은 메모리 주소에 배치할 수 있다. 이 결정은 인터럽트 백터의 위치와 같은 많은 요소에 따라 달라진다. 그러나 많은 운영체제는(Linux 및 Windows 포함) 운영체제를 높은 메모리에 배치하므로 그 경우만 논의한다.

 

일반적으로 여러 사용자 프로세스가 동시에 메모리에 상주하기를 원한다. 따라서 메모리에 적재되기를 기다리는 프로세스에 사용 가능한 메모리를 할당하는 방법을 고려해야 한다. 연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재된다. 그러나 이 메모리 할당 기법에 대해 더 논의하기 전에 메모리 보호 문제를 해결해야 한다.

 

2.1 메모리 보호

 

이전에 논의했던 두 아이디어를 결합하면 프로세스가 자신이 소유하지 않은 메모리를 접근할 수 없게 강제할 수 있다. 만일 시스템이 상한(limit) 레지스터와 재배치 레지스터를 가지고 있다면 이 목적을 달성할 수 있다. 재배치 레지스터는 가장 작은 물리 주소의 값을 저장하고, 상항 레지스터는 논리 주소의 범위 값을 지정한다. 각각의 논리 주소는 상한 레지스터가 지정한 범위 안에 존재해야 한다. MMU는 동적으로 논리 주소에 재배치 레지스터의 값을 더함으로써 주소를 반환하는 역할을 한다. 이렇게 변환된 주소는 메모리로 보내진다.

 

 

CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처는 문맥 교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재한다. CPU에 의해서 생성되는 모든 주소는 이 레지스터들의 값을 참조해서 확인 작업을 거치기 때문에, 우리는 운영체제와 다른 사용자 프로그램을 현재 수행 중인 사용자 프로그램의 접근으로부터 보호할 수 있다. 

 

여기서 재배치 레지스터를 사용함으로 해서 운영체제의 크기는 실행 중이라도 얼마든지 변경될 수 있음을 알 수 있다. 

 

2.2 메모리 할당

 

메모리를 할당하는 가장 간단한 방법 중 하나는 프로세스를 메모리의 가변 크기 파티션에 할당하는 것이다. 각 파티션에는 정확히 하나의 프로세스만 적재될 수 있다. 이 가변 파티션 기법에서 운영체제는 사용 가능한 메모리 부분과 사용 중인 부분을 나타내는 테이블을 유지한다. 처음에는 모든 메모리가 사용자 프로세스에 사용 가능하며, 하나의 큰 사용 가능한 메모리 블록인 hole로 간주한다. 

 

위 그림은 이 기법을 보여준다. 처음에는 프로세스 5,6,2가 적재되어 있고 메모리가 완전히 활용 중이다. 프로세스 8이 종료된 후 하나의 연속된 hole이 생긴다. 나중에 프로세스 9가 도착하고 메모리가 할당된다. 그후 프로세스 5가 종료되면 두 개의 연속되지 않은 hole이 생긴다. 

 

프로세스가 시스템에 들어오면, 운영체제는 각 프로세스가 메모리를 얼마나 요구하며, 또 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 공간을 할당한다. 프로세스가 공간을 할당받게 되면, 이후로는 CPU를 할당받기 위해 경쟁한다. 프로세스가 끝나면 메모리를 반납하고, 운영체제는 다른 프로세스에 이 공간을 할당할 수 있다.

 

도착 프로세스의 요구를 충족시키기에 메모리가 충분하지 않으면 어떻게 될까? 한 가지 옵션은 단순히 프로세스를 거부하고 적절한 오류 메시지를 제공하는 것이다. 또는 이러한 프로세스를 대기 큐에 넣을 수 있다. 메모리가 나중에 해제되면 운영체제는 대기 큐를 검사하여 대기 프로세스의 메모리 요구를 충족시킬지 여부를 결정한다.

 

언급한 것처럼 일반적으로 메모리에는 다양한 크기의 hole이 여기저기 산재하게 된다. 프로세스에 공간이 필요할 때 운영체제는 이 hole의 집합에서 적절한 것을 찾아내야한다. 만약 hole을 찾았는데 그것이 요청한 것보다 약간 크면 두 개로 나누어 한 조각은 프로세스에 할당하고, 나머지 하나는 hole집합으로 되돌아간다. 그 프로세스가 끝나면 그 공간은 hole의 집합으로 되돌아간다. 이 새로운 hole이 다른 hole과 인접해 있다면, 이 두개의 블록을 합쳐서 한 개의 큰 hole로 만든다.

 

이러한 기법은 동적 메모리 할당 문제(dynamic storage allocation problem)의 특별한 한 예이다. 이것은 일련의 가용 공간-리스트로부터 크기 n-바이트 블록을 요구하는 것을 어떻게 만족시켜 줄 것이냐를 결정하는 문제이다. 이러한 문제에 대한 해결책은 여러 개가 제시되어 있다. 최초 적합(first-fit), 최적 적합(best-fit), 최악 적합(worst-fit)은 가장 일반적인 기법들이다.

• 최초 적합: 첫 번째 사용 가능한 가용 공간을 할당한다. 검색은 집합의 시작에서부터 하거나 지난번 검색이 끝났던 곳에서 시작될 수 있다. 충분히 큰 가용 공간을 찾았을때 검색을 끝낼 수 있다.
• 최적 적합: 사용 가능한 공간 중에서 가장 작은 것을 택한다. 리스트가 크기 순으로 되어 있지 않다면 모든 리스트를 검색해야만 한다. 이 방법은 아주 작은 가용 공간을 만들어 낸다.
• 최악 적합: 가장 큰 가용 공간을 택한다. 이 방식에서 할당해 주고 남게 되는 가용 공간은 충분히 커서 다른 프로세스들을 위하여 유용하게 사용될 수 있다. 이때 가용 공간들이 크기 순으로 정렬되어 있지 않으면 모든 리스트를 다 검색해야만 한다.

모의실험을 통해서 연구해 보면 최초 적합과 최적 적합 모두가 시간과 메모리 이용 효율 측면에서 최악 적합보다 좋다는 것이 입증되었다. 최초 적합이나 최적적합이나 공간 효율성 측면에서는 어느 것이 항상 더 좋다고 말할 수 없지만 최초 적합이 일반적으로 속도가 더 빠르다.

 

2.3 단편화

 

최초 적합 전략과 최적 적합 전략 모두 외부 단편화로 인해 어려움을 겪는다. 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 어떤 가용 공간은 너무 작은 조각이 되어 버린다. 외부 단편화는 이처럼 유휴 공간들을 모두 함치면 충분한 공간이 되지만 그것들이 너무 작은 조각들로 여러 곳에 분산되어 있을 때 발생한다. 즉, 메모리는 너무 많은 수의 매우 작은 조각들로 단편화되어 있는 것이다. 이 단편화 문제는 매우 심각해질 수 있다. 최악의 경우에는 모든 프로세스 사이마다 못 쓰게 된 가용 공간을 가질 수 있다. 이 모든 가용 공간들을 합쳐 하나의 큰 가용 공간을 만들면 여기에 여러 개의 프로세스를 실행시킬 수 있을 것이다.

 

적합 또는 최적 적합 전략을 사용할 것인지 사용하지 않을 것인지에 대한 결정은 단편화의 크기에 영향을 받는다(어떤 시스템에서는 최초 적합이 우수하고, 다른 시스템에서는 최적 적합이 우수할 수 있다). 어느 쪽(위쪽에서부터 첫 번째 아니면 아래쪽에서부터 첫 번째) 가용 공간을 할당할 것인가도 고려해야 할 요소 중의 하나이다. 어떤 알고리즘을 사용하더라도 외부 단편화는 문제로 남는다. 

 

메모리의 전체 크기와 프로세스 크기들은 모두 외부 단편화에 따라 큰 영향을 미칠 수 있다. 예를 들어, 최초 적합의 경우 통계적인 분석을 해보면 N개의 블록이 할당되었을 때 0.5N개의 블록이 단편화 때문에 손실될 수 있다는 것을 알 수 있다. 즉, 메모리의 3분의 1이 쓸 수 없게 될 수 있다는 것이다. 이 현상은 50% 규칙으로 알려져 있다.

 

메모리 공간을 낭비하는 현상인 단편화는 내부적으로도 발생할 수 있다. 18,464B 크기의 가용 공간을 생각해 보자. 어느 한 프로세스가 18,462B를 요구한다고 가정하자. 요구된 블록을 정확히 할당하면 2B의 가용 공간(hole)이 남는다. 이러면 2B짜리 가용 공간을 놓치지 않기 위해 오히려 2B보다 더 큰 부다음을 시스템이 가지게 될 것이다. 따라서 일반적으로는 메모리를 먼저 아주 작은 공간들로 분할하고 프로세스가 요청하면 할당을 할상 이 분할된 크기의 정수배로만 해주는 것이 보통이다. 이 경우 할당된 공간은 요구된 공간보다 약간 더 클 수 있다. 이들 두 크기 사이의 남는 부분이 바로 내부 단편화이고, 이 내부 단편화 역시 사용이 못 되는 부분이다. 

 

외부 단편화 문제를 해결하는 다른 방법으로는 압축(compaction)이 있다. 이 방법은 메모리 모든 내용을 한군데로 몰고 모든 가용 공간을 다른 한군데로 몰아서 큰 블록을 만드는 것이다. 그러나 압축이 항상 가능한 것은 아니다. 재배치가 어셈블 또는 적재 시에 정적으로 행해진다면, 압축은 실행될 수 없다. 압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능하다. 주소가 동적으로 재배치할 수 있다면, 재배치 작업은 프로그램과 데이터를 새로운 위치로 옮기고 새 위치를 반영하기 위하여 기준 레지스터만 변경하면 완료된다.

압축이 가능하더라도 그 비용을 검토해 보아야 한다. 가장 간단한 압축 알고리즘은 단순히 모든 프로세스를 한쪽 끝으로 이동시켜 모든 가용 공간이 그 반대 방향으로 모이도록 하는 방법이지만 이 방법은 비용이 매우 많이 든다.

 

외부 단편화 문제를 해결할 수 있는 다른 방법은 한 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법이다. 이것은 컴퓨터 시스템에 가장 일반적인 메모리 관리 기법인 페이징에서 사용되는 전략이다. 

 

3. 페이징

 

이제 프로세스의 물리 주소 공간이 연속되지 않아도 되는 메모리 관리 기법인 페이징을 소개한다. 페이징은 연속 메모리 할당을 괴롭히는 두 가지 문제인 외부 단편화와 관련 압축의 필요성을 피한다. 

 

3.1 기본 방법

 

물리 메모리는 프레임(frame)이라 불리는 같은 크기 블록으로 나누어진다. 논리 메모리는 페이지(page)라 불리는 같은 크기의 블록으로 나누어진다. 프로세스가 실행될 때 그 프로세스의 페이지는 파일 시스템 또는 예비 저장장치로부터 가용한 메인 메모리 프레임으로 적재된다. 예비 저장장치는 메모리 프레임 혹은 프레임의 묶음인 클러스터와 동일한 크기의 고정 크기 블록으로 나누어진다. 

 

예를 들어 논리 주소 공간은 물리 주소 공간으로 부터 완전히 분리되었기 때문에 물리 메모리의 크기가 2^64바이트보다 적게 장착된 시스템에서도 프로세스는 64비트로 이루어진 논리 주소 공간을 사용할 수 있다.

 

CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 오프셋(d:offset) 두 개의 부분으로 나누어진다. 페이지 번호는 프로세스 페이지 테이블(page table)을 엑세스할 때 사용된다. 페이지 테이블은 물리 메모리의 각 프레임의 시작 주소를 저장하고 있으며 오프셋은 참조되는 프레임 안에서의 위치이다. 따라서, 프레임의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 된다. 

 

다음은 CPU에 의해 생성된 논리 주소를 물리 주소로 변환하기 위해 MMU가 취한 단계를 요약한 것이다.

1. 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용한다.
2. 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
3. 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다. 

오프셋 d는 변하지 않기 때문에 대체되지 않으며, 프레임 번호와 오프셋은 이제 물리 주소를 구성한다.

 

프레임 크기와 마찬가지로 페이지 크기는 하드웨어에 의해 정해진다. 페이지 크기는 2의 거듭제곱으로, 일반적으로 컴퓨터 아키텍처에 따라 페이지당 4KB와 1GB사이이다. 페이지 크기로 2의 거듭제곱을 선택하면 논리 주소를 페이지 번호 및 페이지 오프셋으로 쉽게 변환할 수 있다. 논리 주소 공간의 크기가 2^m이고 페이지 크기가 2^n 바이트인 경우 논리 주소의 상위 m - n 비트는 페이지 번호를 지정하고 n 하위 비트는 페이지 오프셋을 지정한다. 

• 페이지 번호 p = m - n
• 페이지 오프셋 d = n

구체적인 예로 그럼 9.10의 메모리를 생각해 보자. 이 예에서 논리 주소에서 n = 2, m = 4이다. 논리 주소 0은 페이지 0, 오프셋 0이다. 페이지 테이블을 색인으로 찾아서 페이지 0이 프레임 5에 있다는 것을 알아낸다. 그래서 논리 주소 0은 실제 주소 20[(5 * 4) + 0] 이 된다. 논리 주소 3(페이지 0, 오프셋 3)은 실제 주소 23[(54) +3]이 된다. 논리 주소 4는 페이지 테이블에 의해 페이지 1, 오프셋 0이고, 페이지 1은 프레임 6이 된다. 그래서 실제 주소 24[64 + 0]이 된다. 

 

페이징 자체는 일종의 동적 재배치라는 것을 알 수 있다. 모든 논리 주소는 페이징 하드웨어에 의해 실제 주소로 바인딩 된다. 페이징을 사용하는 것은 각 메모리 프레임마다 하나씩 기준 레지스터를 테이블로 유지하는 것과 유사하다. 

 

페이징 기법을 사용하면 외부 단편화가 발생하지 않는다. 모든 놀고 있는 프레임이 프로세스에 할당될 수 있기 때문이다. 그러나 이제는 내부 단편화가 발생한다. 할당은 항상 프레임의 정수배로 할당되기 때문이다. 만약 프로세스가 페이지 경계와 일치하지 않는 크기의 메모리를 요구한다면, 마지막 페이지 프레임은 전부 할당되지 않는다. 

 

예를 들어, 페이지 크기가 2048B이고 프레세스가 72766B를 요구한다면 35개의 페이지 프레임을 할당하고 1086B가 남는다. 36번째로 할당되는 페이지 프레임은 2048 - 1086 = 962B의 내부 단편화가 발생하게 된다. 최악의 경우 프로세스가 n개의 페이지와 추가로 1B를 요구할 수 있다. 그 결과 n+1 번째 프레임은 거의 모든 프레임이 내부 단편화가 된다.

 

프로세스의 크기가 페이지 크기와 무관하다면 평균적으로 프로세스당 반 페이지 정도의 내부 단편화가 예상된다. 이런 측면에서는 작은 페이지 크기가 바람직하다는 것을 알 수 있다. 그러나 페이지 크기가 작아지면 그게 반비례하여 페이지 테이블의 크기가 커지게 되고 이 테이블이 차지하는 공간은 낭비된다. 디스크의 입장에서는 페이지의 크기가 클수록 효율적이다. 일반적인 추세는 페이지 크기가 4KB 또는 8KB이다. 어떤 CPU나 OS커널은 여러 개의 페이지 크기도 혀용한다. 일반적으로 32비트 CPU에서는 페이지 테이블 항목의 크기는 4B이다. 그러나 이 크기도 바뀔 수 있다. 

 

한 프로세스가 실행되기 위해 도착하면 그 프로세스의 크기가 페이지 몇 개 분에 해당하는가를 조사한다. 각 사용자 페이지는 한 프레임씩이 필요하다. 즉, 프로세스가 n개 페이지를 요구하면 메모리에서 이용할 수 있는 프레임이 n개 있어야 한다. n개의 프레임을 사용할 수 있다면 이 프레임들은 이 프로세스에 할당된다. 그리고는 프로세스의 처음 페이지가 할당된 프레임 중. 하나에 적재되고, 그 프레임 번호가 페이지 테이블에 기록된다. 그다음 페이지는 또 다른 프레임에 적재되고, 또 그 프레임 번호가 페이지 테이블에 기록되며 이 과정이 반복된다.

 

페이징의 가장 중요한 특징은 메모리에 대한 프로그래머의 인식과 실제 내용이 서로 다르다는 것이다. 프로그래머는 메모리가 하나의 연속적인 공간이며, 메모리에는 이 프로그램만 있다고 생각한다. 그러나 실제로는 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 다른 프로그램이 올라와 있다. 

 

프로그래머가 생각하는 메모리와 실제 물리 메모리의 차이는 주소 변환 하드웨어에 의해 해소된다. 논리 주소는 물리 주소로 변환된다. 따라서 사용자 프로세스는 자기의 것이 아닌 메모리는 접근조차 할 수 없다. 페이지 테이블을 통하지 않고서는 다른공간에 접근할 길이 없으며 페이지 테이블은 그 프로세스가 소유하고 있는 페이지들만을 가리키고 있기 때문이다.

 

운영체제는 물리 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있어야 한다. 즉, 어느 프레임이 할당되어 있고, 어느 프레임이 사용 가능한지, 총 프레임은 몇 개나 되는지 등을 알아야 한다. 이런 정보는 일반적으로 프레임 테이블이라는 시스템에 하나밖에 없는 자료구조에 있다. 프레임 테이블은 각 프레임당 하나의 항목을 가지고 있으며, 프레임이 비어 있는지, 할당되었는지, 그리고 할당되었다면 어느 프로세스의 어느 페이지에 할당되었는지를 나타낸다. 

 

또한, 운영체제는 모든 프로세스의 주소들을 실제 주소로 사상할 수 있어야 한다. 만약 사용자가 시스템 콜을 호출하여 인자로 어떤 주소(예를 들어, 자신의 영역 내로 입력할 버퍼의 주소)를 주면, 제대로 사상하여 정확히 그 물리 주소를 찾아가야 한다. 운영체제는 명령 카운터와 레지스터의 사본을 유지하는 것처럼 각 프로세스의 페이지 테이블 사본을 유지한다. 이 사본은 운영체제가 논리 주소에 대응하는 물리 주소를 직접 사상해야 할 때마다 논리 주소를 물리 주소로 변환하는 데 사용된다. 또한 프로세스가 CPU에 할당될 때 CPU 디스패처가 하드웨어 디스패처 테이블을 설정하는 데 사용된다. 따라서 페이징은 문맥 교환 시간을 늘린다.

 

3.2 하드웨어 지원

 

페이지 테이블은 프로세스별 자료구조이므로 페이지 테이블에 대한 포인터는 각 프로세스의 프로세스 제어 블록에 다른 레지스터 값과 함께 저장된다.

 

CPU 스케줄러가 실행할 프로세스를 선택하면 사용자 레지스터를 다시 적재하고 저장된 사용자 페이지 테이블로부터 적절한 하드웨어 페이지 테이블값을 다시 적재해야 한다. 

 

페이지 테이블의 하드웨어 구현은 여러 가지 방법으로 수행할 수 있다. 가장 간단한 경우, 페이지 테이블은 전용 고속 하드웨어 레지스터 세트로 구현되므로 페이지 주소 변환이 매우 효율적이다. 그러나 이러한 접근 방식은 각각의 레지스터가 문맥 교환 중에 교체되어야 하므로 문맥 교환 시간을 증가시킨다.

 

페이지 테이블에 레지스터를 사용하는 것은 페이지 테이블이 작은 경우 적합하다. 그러나 대부분의 현대 CPU는 훨씬 큰 페이지 테이블을 지원한다. 이러한 컴퓨터들의 페이지 테이블을 구현학 ㅣ위해서 위에서처럼 빠른 레지스터를 사용하는 것은 부적절하다. 따라서, 대부분의 컴퓨터는 페이지 테이블을 메인 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR)로 하여금 페이지 테이블을 가리키도록 한다. 다른 페이지 테이블을 사용하려면 단지 이 레지스터만을 변화시키면 되고, 따라서 문맥 교환시간을 줄일 수 있다. 

 

Translation Look-Aside Buffer(TLB)

메인 메모리에 페이지 테이블을 저장하면 문맥 교환 속도가 빨라지지만 메모리 액세스 시간이 느려질 수도 있다. 메모리 i에 엑세스하려고 한다고 가정하자. 먼저 페이지 번호를 기준으로 PTBR 오프셋의 값을 사용하여 페이지 테이블의 항목을 찾는다. 이 작업에는 한 번의 메모리 액세스가 필요하다. 이렇게 얻은 프레임 번호와 페이지 오프셋을 결합하여 실제 주소를 생성한다. 그런 다음 메모리에서 원하는 위치에 엑세스 할 수 있다. 

 

이 기법을 사용하면 데이터에 액세스하려면 두 번의 메모리 액세스가 필요하다.(한 번은 페이지 테이블 항목, 한 번은 실제 데이터). 따라서 메모리 접근 시간은 2배로 느려지고 이는 대부분의 상황에서 허용될 수 없는 지연 시간이다.

 

이 문제에 대한 해결에는 TLB(translation look-aside buffers)라고 불리는 특수한 소형 하드웨어 캐시가 사용된다. TLB는 매우 빠른 연관 메모리(associative memory)로 구성된다. TLB내의 각 항목은 키와 값의 두 부분으로 구성된다. TLB에 페이지를 찾아달라고 요청이 들어오면 이 찾고자 하는 페이지를 동시에 여러 개의 내부 키(페이지 번호)와 비교한다. 페이지 번호가 같은 것이 발견되면 그에 대응하는 프레임 번호를 알려준다. 검색의 속도는 빠르고 현대 하드웨어에서의 TLB 검색은 명령어 파이프라인의 일부로 동작하며 성능에 추가적인 손해를 끼지치 않는다.

 

그러나 파이프라인 단계 동안 검색을 하기 위해서는 TLB의 크기는 작게 유지할 수밖에 없으며 통상 32개에서 1024개의 항목을 유지한다. 몇몇 CPU는 명령어와 데이터의 주소를 저장하기 위한 개별적인 TLB를 구현하기도 한다.

 

페이지 테이블과 함계 다음과 같이 사용된다. TLB는 페이지 테이블의 일부분만을 저장한다. CPU가 논리 주소를 생성하면 MMU는 해당 페이지 번호가 TLB에 있는지 확인한다. 페이지 번호가 발견되면 해당 프레임 번호를 즉시 알 수 있고 메모리를 접근 하는 데 사용된다. 앞서 언급한 것처럼 이러한 절차들은 CPU 내부에서 명령어 파이프라인의 일환으로 실행되기 때문에 페이징을 사용하지 않는 시스템과 비교하면 성능 저하는 전혀 없다.

 

페이지 번호가 TLB에 없으면(TLB 미스라고 함) 주소 변환을 위해 페이지 테이블에 대한 메모리 참조가 이루어져야 한다. 프레임 번호가 확보되면 이를 사용하여 메모리에 액세스 할 수 있다. 또한 페이지 번호와 프레임 번호를 TLB에 추가하여 다음 참조에서 빠르게 찾을 수 있도록 한다.

 

만약 TLB가 가득 차면, 기존 항목 중에서 교체될 항목을 선택해야 한다. 교체 정책은 LRU, 라운드 로빈, 무작위 등 다양한 정책이 사용된다. 몇몇 CPU는 자신이 직접 선택한다. 더욱이 몇몇 TLB는 특정 항목들을 TLB에 고정하는데, 이러한 항목들은 TLB에서 제거될 수 없다. 보통 중요 커널 코드를 TLB에 고정한다.

 

어떤 TLB는 각 항목에 ASIDs(addrss-space identifiers)를 저장하기도 한다. ASID는 그 TLB 항목이 어느 프로세스에 속한 것인지를 알려주며 그 프로세스의 정보를 보호하기 위해 사용된다. TLB에서 가상 주소를 변환할 때 현재 수행 중인 프로세스의 ASDI가 TLB항목에 있는 ASID와 같은지를 검사한다. ASID가 맞지 않으면 TLB miss로 처리한다. ASID 지원이 있으면 한 TLB안에 여러 프로세스의 정보를 동시에 함께 보관할 수 있다. ASID 지원이 없으면 새로운 페이지 테이블이 선택될 때마다(예를 들어, 새 프로세스가 문맥 교환을 해서 실행을 재개하는 경우) 다음 실행 프로세스가 잘 못 변환하지 않도록 하기 위해서 TLB는 전부 플러시가 되어야 한다. 그렇지 않으면 TLB에는 이전 프로세스가 사용하던 페이지 번호와 프레임 번호가 남아 무효가 된 주소를 공급해줄 수 있다.

 

접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율을 적중률(hit ratio)이라고 부른다. 예를 들어, 80% 적중률이란 TLB에서 원하는 번호를 발견할 횟수가 80%라는 것을 의미한다.

 

이전에 보았던 것처럼 현재의 CPU는 여러 단계의 TLB를 가지고 있다. 따라서 현대 CPU에서 메모리 접근 시간을 계산하는 것은 훨씬 복잡하다. 예를 들어, Intel Core i7 CPU는 128개의 항목을 가지는 L1 명령어 TLB와 64개의 항목을 가지는 L1데이터 TLB를 가지고 있다. L1에서 미스가 발생한 경우, 512개의 항목을 가지고 있는 L2 TLB를 검색하는 데 6 CPU 사이클이 필요하다. L2에서 미스가 발생했다는 것은 해당 프레임 주소를 얻기 위하여 CPU가 메모리에 존재하는 페이지 테이블 항목을 검색해야만 한다는 것을 의미하고 이 연산은 수백 사이클이 필요하다.

 

3.3 보호

 

페이징 환경에서 메모리 보호는 각 페이지에 붙어있는 보호 비트에 의해 구현된다. 이 비트들은 보통 페이지 테이블에 속해 있다.

 

각 비트는 이 페이지가 읽고 쓰기 또는 읽기 전용임을 각각 정의할 수 있다. 메모리에 대한 모든 접근은 페이지 테이블을 거치므로, 이때 주소 변환과 함께 이 페이지에 쓰기가 허용되는지 안 되는지와 같은 검사도 할 수가 있다. 읽기 전용 페이지에 관해 쓰기를 시도하면 운영체제가 하드웨어로 트랩을 걸어 준다.

 

페이지 테이블의 각 엔트리에는 유효/무효라는 하나의 비트가 더 있다. 이 비트가 유효로 설정되면 관련된 페이지가 프로세스의 합법적인 페이지임을 나타내며, 이 비트가 무효로 설정되면 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다. 운영체제는 이 비트를 이용해서 그 페이지에 대한 접근을 허용하든지 또는 허용하지 않든지 할 수 있다.

 

3.4 공유 페이지

 

페이징의 장점은 공통의 코드를 공유할 수 있다는 점이다. 여러 프로세스가 있는 환경에서 특히 중요하게 고려해야 할 점이다. 일반적은 Linux 시스템에서 대부분의 사용자 프로세스는 표준 C 라이브러리 libc가 필요하다. 한 가지 옵션은 각 프로세슥 자체 libc 사본을 해당 주소 공간에 적재하도록 하는 것이다. 시스템에 40개의 사용자 프로세스가 있고 libc 라이브러리가 2MB인 경우 80MB의 메모리가 필요하다.

 

그러나 코드가 재진입 코드인 경우 공유할 수 있다. 여기에 표준 C라이브러리 libc에 대한 페이지를 공유하는 세 가지 프로세스가 있다. 재진입 코드는 자체 수정을 할 수 없는 코드로서 실행 중에는 절대 변경되지 않는다. 따라서 두 개 이상의 프로세스가 동일한 코드를 동시에 실행할 수 있다. 각 프로세스는 자신의 실행을 위해 데이터를 보유하기 위한 자체 레지스터 사본과 데이터 저장영역이 있다. 물론 두 프로세스가 가진 데이터는 서로 다를 수 있다. 표준 C라이브러리는 물리 메모리에 하나의 사본만 저장하면 되고, 각 사용자 프로세스의 페이지 테이블은 동일한 물리적 사본으로 매핑시킨다. 따라서 40개의 프로세스를 지원하려면 라이브러리 사본이 하나만 필요하며 이제 필요한 총 공간은 80MB가 아니라 2MB로 크게 절약할 수 있다.

 

4. 페이지 테이블의 구조

4.1 계층적 페이징

 

많은 현대 컴퓨터는 매우 큰 주소 공간을 가진다. 이러한 환경에서는 페이지 테이블도 상당히 커진다. 예를 들어, 32비트 논리 주소 공간을 가진 시스템을 생각해 보자. 이 시스템에서 페이지의 크기가 4KB라면 페이지 테이블은 100만개 이상의 항목으로 구성될 것이다. 각 항목은 다시 4B로 구성되기 때문에 각 프로세스 페이지 테이블만을 위해서라도 4MB의 공간이 필요하게 될 것이다. 이러한 경우 모든 페이지 테이블을 메인 메모리에서 연속적으로 할당하기를 고집하지는 않을 것이다. 한 가지 방법은 페이지 테이블을 여러 개의 작은 조각으로 나누는 것인데 이것도 여러 가지 방법이 가능하다.

 

한 가지 방법은 2단계 페이징 기법으로서 페이지 테이블 자체가 다시 페이징되게 하는 것이다. 앞에서 4KB의 크기를 가진 32비트 기계의 예를 다시 들어보자.

 

5. 스와핑

 

프로세스가 실행되기 위해서는 프로세스의 명령어와 명령어가 접근하는 데이터가 메모리에 있어야 한다. 그러나 프로세스 또는 프로세스의 일부분은 실행 중에 임시로 백업 저장장치(backing store)로 내보내어 졌다가 실행을 계속하기 위해 다시 메모리로 되돌아 올 수 있다. 모든 프로세스의 물리 주소 공간 크기의 총합이 시스템의 실제 물리 메모리 크기보다 큰 경우에도 스와핑을 이용하면 동시에 실행하는 것이 가능하여 다중 프로그래밍 정도를 증가시킨다.

 

5.1 기본 스와핑

 

표준 스와핑에는 메인 메모리와 백업 저장장치 간에 전체 프로세스를 이동한다. 백업 저장장치는 일반적으로 빠른 보조저장장치다. 백업 저장장치는 저장 및 다시 접근해야 하는 프로세스의 크기에 상관없이 수용할 수 있을 만큼 커야 하며, 이러한 메모리 이미지에 직접 액세스 할 수 있어야 한다. 프로세스 또는 일부가 백업 저장장치로 스왑될 때 프로세스와 관련된 자료구조는 백업 저장장치에 기록되어야 한다. 다중 스레드 프로세스의 경우 모든 스레드당 데이터 구조도 스왑되어야 한다. 또한 운영체제는 스왑아웃된 프로세스에 대한 메타데이터를 유지해야 메모리로 다시 스왑인될 때 복원될 수 있다. 

 

표준 스와핑의 장점은 실제 물리 메모리보다 더 많은 프로세스를 수용할 수 있도록 물리 메모리가 초과 할당될 수 있다는 것이다. 유휴 또는 대부분의 시간을 유휴 상태로 보내는 프로세스가 스와핑에 적절한 후보이다. 이러한 비활성 프로세스가 다시 활성화되면 다시 스왑인 해야 한다. 

 

 5.2 페이징에서의 스와핑

표준 스와핑은 기존 UNIX 시스템에서 사용되었지만 메모리와 백업 저장장치 간에 프로세스 전체를 이동하는 데 걸리는 시간이 엄청나기 때문에 일반적으로 최신 운영체제에서는 더는 사용되지 않는다. 

Linux 및 Windows를 포함한 대부분의 시스템은 이제 프로세스 전체가 아닌 프로세스 페이지를 스왑할 수 있는 변형 스와핑을 사용한다. 이 전략은 여전히 물리 메모리를 초과 할당할 수 있지만 프로세스 전체를 스왑하는 비용은 발생하지 않는다. 단지 적은 수의 페이지만 스왑에 관여하기 때문이다. 실제로 스와핑이란 용어는 일반적으로 표준 스와핑을 말하며, 페이징은 페이징에서의 스와핑을 의미한다. 페이지 아웃 연산은 페이지를 메모리에서 백업 저장장치로 이동시킨다. 반대 방향의 연산을 페이지-인 이라고 한다.