지금까지 프로세스들을 관리할 때, CPU 할당에 대해 중점적으로 살펴보았다.
CPU 스케줄링을 통해 CPU 이용률과 프로세스 응답 속도를 모두 향상할 수 있다.
그러나 이러한 성능 향상을 실현하려면, 많은 프로세스를 메모리에 유지해야 한다.
오늘은 메모리를 관리하는 방법들에 대해서 알아보자.
메인 메모리
메모리는 각각 주소가 할당된 일련의 바이트들로 구성된다.
CPU는 PC(Program Counter)가 가리키는 메모리로부터 다음 수행할 명령어를 가져오는데, 그 명령어는 필요한 경우 추가 데이터를 더 가져올 수 있으며, 반대로 데이터를 메모리로 내보낼 수도 있다.
일반적인 명령어 실행 과정은
- 메모리로부터 한 명령어를 가져온다.
- 명령어를 해독한다.
- 메모리에서 피연산자(Operand)를 가져온다.
- 피연산자에 대해 명령어를 실행한다.
- 계산 결과를 메모리에 다시 저장한다.
메모리는 주소에 읽기, 쓰기만 할 뿐 주소들이 어떻게 생성되었는지, 이 주소가 가리키는 내용이 무엇인지는 모른다.
운영체제가 메모리 관리를 어떻게 하는지 알아보자.
기본 하드웨어
하드웨어 관점에서 생각해보자.
CPU가 직접 접근할 수 있는 저장장치는, 메인 메모리 또는 CPU 코어의 레지스터이다.
따라서, 모든 실행되는 명령어와 데이터들은 메인 메모리와 레지스터에 있어야 한다.
만약, 데이터가 메모리에 없다면 CPU가 그것들을 처리하기 전에 메모리로 이동시켜야 한다.
각 CPU 코어에 내장된 레지스터들은 일반적으로 CPU 클록(clock)의 1사이클 내에 접근이 가능하다.
일부 CPU는 레지스터에 있는 명령어 해독과 연산을 클록 틱(clock tick)당 하나 또는 그 이상의 속도로 처리한다.
메인 메모리에 접근하는 경우는 다르다.
메인 메모리의 접근을 완료하기 위해서는 많은 CPU 클록 틱 사이클이 소요되며, CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고 지연(Stall)되는 현상이 발생한다.
이런 현상을 방지하기 위해 CPU와 메인 메모리 사이에 "캐시 메모리"를 추가 한다.
CPU 캐시를 관리하여 운영체제 도움 없이 메모리 접근 속도를 향상한다.
메모리 접근 속도 외에도, 메모리 영역에 대한 고려도 해야한다.
운영체제 영역 뿐만 아니라 사용자 프로그램 사이도 서로 보호해야 한다.
운영체제가 CPU와 메모리 간 접근 중에 개입하는 경우 성능이 떨어지기 때문에 이러한 보호 기법은 반드시 하드웨어가 지원해야 한다.
먼저 각각의 프로세스가 독립된 메모리 공간을 가지도록 보장해야 한다.
그림에서 보다시피, 각 프로세스의 메모리 공간은 서로를 보호하며 메모리에 적재된다.
특정 프로세스의 영역을 지정하기 위해 기준(base) 레지스터와 상한(limit) 레지스터를 사용한다.
- 기준 레지스터
- 프로세스의 가장 작은 메모리 주소 저장.
- 상한 레지스터
- 프로세스의 메모리 영역 크기 저장.
예를 들어 기준 레지스터가 100이고, 상한 레지스터가 50인 경우, 프로그램은 100에서 150까지의 메모리 주소를 접근할 수 있다.
메모리 공간의 보호는 CPU가 접근하려는 프로세스의 메모리 주소와 레지스터를 비교함으로써 이루어진다.
사용자 프로그램이 운영체제의 메모리 공간이나, 다른 사용자 프로그램의 메모리 공간에 접근하면 운영체제는 치명적인 오류로 간주하고 트랩(trap)을 발생시킨다. (Segmentation fault ...)
이를 통해 메모리 영역을 보호한다.
주소의 할당
대부분의 운영체제는 사용자 프로세스가 메모리 어느 부분으로도 적재될 수 있도록 지원한다.
사용자 프로그램은 여러 단계를 거쳐 실행되기 때문에, 이 단계를 거치는 동안 주소들은 여러 가지 표현 방식을 거치게 된다.
소스 프로그램에서 주소는 변수(int count)와 같은 "심볼" 형태로 표현된다.
컴파일러는 이 심볼 주소를 "재배치 가능 주소"로 바인딩 시키고, 그 다음 링커나 로더가 이를 "절대 주소"로 바인딩시킨다.
메모리 주소 공간에서의 바인딩은 아래 시점에 따라 구분된다.
- 컴파일 시간(Compile time)
- 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 알 수 있으면 "절대 코드"를 생성할 수 있다.
- 적재 시간(Load time)
- 만일 프로세스가 메모리 어디로 올라오게 될지를 컴파일 시점에 알지 못하면 컴파일러는 일단 재배치 가능 코드로 만든다.
- 이 경우에 심볼과 실제 메모리 주소의 바인딩은 프로그램이 메인 메모리로 적재되는 시간에 이루어지게 된다.
- 실행 시간(Run time)
- 만약 프로세스가 실행 중 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면, 실행 시간까지 바인딩이 허용되었다고 얘기한다.
- 이를 위해 특별한 하드웨어가 필요하다.
논리, 물리 주소 공간
CPU가 생성하는 주소를 "논리 주소(Logical address)"라고 하며, 메모리가 취급하는 주소를 "물리 주소(Physical address)"라고 한다.
컴파일 또는 적재시에 주소를 바인딩하면, 논리 주소와 물리 주소가 같다.
그러나 실행 시간에 바인딩하면, 논리 주소와 물리 주소가 다르다.
이 논리 주소를 "가상 주소" 라고 한다.
프로그램의 실행 중에는 이와 같은 가상 주소를 물리 주소로 바꾸어준다.
이 변환 작업은 "메모리 관리 장치(MMU)" 하드웨어에 의해 수행된다.
사용자 프로그램은 논리 주소를 사용하며, CPU가 해당 논리 주소를 참고하여 메모리 주소에 접근할 때, MMU가 해당 논리 주소를 실제 물리 주소로 바꿔준다.
그렇게 변환된 실제 물리 주소를 CPU 레지스터에 저장하고 해당 주소로 접근하게 된다.
동적 적재
지금까지 설명은 프로세스 전체가 미리 메모리에 적재되어 있어야 했다.
이 경우 프로세스의 크기는 메모리의 크기보다 작아야 한다.
메모리 공간을 더 효율적으로 사용하려면, 동적 적재를 해야 한다.
동적 적재에서는 프로그램의 루틴(함수)이 실제 호출되기 전까지 재배치 가능한 상태로 디스크에 대기하고 있다.
먼저 main 프로그램이 메모리에 올라와 실행된다.
이 루틴이 다른 루틴을 호출하게 되면 호출된 루틴이 메모리에 이미 적재되어 있는지 확인한다.
적재되어 있지 않은 경우, 요구된 루틴을 메모리로 가져온 뒤 호출한다.
동적 적재를 사용하면, 프로그램 크기가 메모리 크기보다 커도, 사용되는 부분만 적재되기 때문에 효율적이다.
동적 연결 및 공유 라이브러리
"동적 연결 라이브러리(Dynamic Linking Library)"는 사용자 프로그램이 실행될 때, 사용자 프로그램에 연결되는 시스템 라이브러리이다.
동적 연결에서는 연결(linking)이 런타임까지 미루어지는 것이다.
이 기능이 없으면 모든 프로그램에 해당 라이브러리의 사본을 포함해야 한다.
이는 프로그램 크기 증가와 메인 메모리 낭비로 이어질 수 있다.
DLL은 또한 해당 라이브러리를 여러 프로세스 간에 공유할 수 있어, 메인 메모리에 DLL이 하나만 있을 수 있다는 것이다.
이러한 이유로 DLL은 "공유 라이브러리"라고도 부르며 Windows, Linux에서 많이 사용된다.
프로그램이 동적 라이브러리의 루틴을 참조하면, 로더는 DLL을 찾아서 메모리에 적재한다.
그런 다음 해당 루틴을 참조하는 주소를 DLL이 저장된 메모리 주소로 조정한다.
프로그램이 다른 라이브러리 버전을 수행하는 것을 방지하기 위해, 버전의 정보를 프로그램과 라이브러리 각각에 포함해야 한다.
프로그램은 라이브러리의 어느 버전을 사용할지 가려내기 위해 버전 정보를 이용해야 한다.
동적 연결과 공유 라이브러리는 운영체제의 도움이 필요하다.
사용자 프로그램은 다른 메모리를 접근할 수 없기 때문에, 운영체제에게 요청하여 메모리 주소를 조정할 수 있도록 해야 한다.
연속 메모리 할당
초기 메모리 할당 방식이다.
각 프로세스는 다음 프로세스가 적재된 영역과 인접한 메모리 영역에 적재된다.
메모리 보호
연속 메모리 할당을 위해 메모리 보호 문제를 해결해야 한다.
이전에 설명했던 기준 레지스터와 상한 레지스터를 가지고 있다면 메모리 보호를 할 수 있다.
메모리 할당
메모리 할당의 가장 간단한 방법은 하나의 프로세스를 하나의 "가변 파티션"에 할당하는 것이다.
가변 파티션에는 정확히 하나의 프로세스만 적재될 수 있다.
위 그림은 프로세스 2, 5, 8이 적재되어 있다가 프로세스 8이 메모리를 반납하고, 프로세스 9가 적재되고, 프로세스5가 반납되는 것을 보여준다.
이때, 파란색 공간을 hole 이라고 부르며, 이 hole로 인해 "단편화" 문제가 발생한다.
단편화(Fragmentation)
프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 가용 공간은 너무 작은 조각이 되어 버린다.
이 가용 공간을 모두 합치면 충분한 공간이 되지만, 그것들이 작은 단위로 여러 곳에 분산되어 있을 때 "외부 단편화" 문제가 발생 한다.
메모리가 너무 작은 조각들로 단편화 되어 있으면, 최악의 경우 모든 프로세스 사이마다 못 쓰는 가용 공간을 가질 수 있다.
즉, 가용 공간을 다 합치면 해당 공간에 프로세스 적재가 가능한데, 여러 곳으로 단편화 되어 있기 때문에 못 쓰는 상태가 될 수 있다.
페이징(Paging)
외부 단편화 문제를 해결하기 위한 메모리 관리 기법이다.
지금까지 설명한 메모리 관리는 프로세스의 물리 주소가 연속적이였지만,
페이징 기법을 사용하면 연속적이지 않아도 된다.
페이징은 연속 메모리 할당의 문제인 외부 단편화와 압축과 같은 문제들을 해결하고, 많은 이점을 제공하기 때문에 대부분의 운영체제에서 페이징이 사용된다.
기본 동작 방식
페이징에서 물리 메모리는 "프레임(Frame)" 이라는 같은 크기의 블록으로 나누어진다.
논리 메모리는 "페이지(Page)"라는 같은 크기의 블록으로 나누어진다.
프로세스가 실행되면, 프로세스의 페이지가 메인 메모리의 프레임으로 적재된다.
CPU에서 페이지에 접근할 때 주소 형식은 "페이지 번호"와 "페이지 오프셋" 두 개의 부분으로 나누어진다.
페이지 번호는 프로세스의 "페이지 테이블(Page Table)"을 접근할 때 사용된다.
페이지 테이블은 각각의 페이지에 대한 프레임의 시작 주소를 저장하고 있으며, 오프셋은 해당 프레임에서 얼만큼 떨어져 있는지를 나타내는 값이다.
따라서, 프레임의 시작 주소와 오프셋이 결합되어 물리 메모리 주소가 된다.
아래는 CPU가 접근하려는 논리 주소를 물리 주소로 변환하기 위한 MMU의 동작 단계를 요약한 것이다.
- 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용한다.
- 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
- 논리 주소의 페이지 번호 p를 프레임 번호 f로 변경한다.
프레임과 페이지의 크기는 하드웨어에 의해 정해지며, 대부분 2의 거듭제곱의 값이다.
현재는 보통 4 KB 또는 8 KB이다.
어떤 CPU나 OS 커널은 여러 개의 페이지 크기도 허용한다.
페이징 기법에서 외부 단편화는 발생하지 않는다.
프로세스들의 페이지와 프레임이 사용 가능한 메모리에 동일한 크기로 적재되기 때문이다.
하지만, 내부 단편화는 발생한다.
예를 들어 페이지 크기가 16 Bytes이고, 프로세스가 70 Bytes라면, 4개의 페이지, 프레임을 할당하고 6 Bytes가 남는다.
즉, 6 bytes의 내부 단편화가 발생한다.
그래도 내부 단편화는 외부 단편화에 비해 크기가 작다.
운영체제는 프로세스가 실행되면, 그 프로세스의 크기가 페이지 몇 개 분에 해당하는지 검사한다.
페이지 당 하나의 프레임이 필요하다.
n개의 페이지가 필요하면, n개의 프레임이 필요하다.
n개의 프레임을 사용할 수 있다면, 이 프레임들은 이 프로세스에 할당되고, 할당된 프레임 순서부터 각 페이지가 매핑된다.
운영체제는 물리 메모리 관리를 위해 "프레임 테이블"을 사용한다.
프레임 테이블은 각 프레임당 하나의 항목을 가지고 있으며, 프레임이 비어 있는지, 어느 프로세스의 어느 페이지에 할당되었는지 와 같은 정보를 가지고 있다.
하드웨어 지원
대부분의 컴퓨터는 페이지 테이블을 메인 메모리에 저장하고, "페이지 테이블 기준 레지스터(PTBR)"를 사용하여 페이지 테이블을 가리키도록 한다.
다른 페이지 테이블을 사용하기 위해 이 레지스터 값만 바꾸면 되서 문맥 교환 시간을 줄일 수 있다.
TLB(Translation Look-Aside Buffer)
PTBR을 사용하여 메모리에 접근하는 경우, 두 번의 메모리 접근이 필요하다.
한 번은 PTBR을 통해 페이지 테이블을 찾는 접근, 다른 한 번은 페이지 테이블에 의해 만들어진 실제 주소로 접근하는 것이다.
따라서, 메모리 접근 시간은 2배가 되고 이는 대부분의 상황에서 허용할 수 없는 지연 시간이다.
이런 문제 해결을 위해 TLB라는 특수한 소형 하드웨어 캐시 메모리가 사용된다.
TLB는 매우 빠른 연관 메모리(Associative Memory)로 구성된다.
TLB의 각 항목은 키(key)와 값(value)으로 구성된다.
TLB에 페이지를 찾아달라는 요청이 들어오면, 찾고자 하는 페이지를 동시에 여러 개의 키(페이지 번호)와 비교한다.
찾고자 하는 페이지 번호가 있으면, 그에 맞는 프레임 번호를 알려준다.
페이지 번호가 TLB에 없으면(TLB 미스라고 함), 기존처럼 두 번의 메모리 접근을 통해 메모리에 접근한다.
또한, 페이지 번호와 프레임 번호를 TLB에 추가한다.
TLB의 크기는 작으며, 통상 32개에서 1024개의 항목을 유지한다.
보호
보호 비트
페이징 환경에서 메모리 보호는 각 페이지에 붙어 있는 "보호 비트"에 의해 구현된다.
각 비트는 이 페이지가 읽기, 쓰기, 읽기 전용(read only)임을 나타낸다.
메모리 접근을 위해서 페이지 테이블을 거치므로, 이때 주소 변환과 함께 이 페이지에 쓰기가 가능한지 검사할 수 있다.
읽기 전용 페이지에 쓰기를 시도하면, 운영체제가 하드웨어로 트랩을 걸어 준다.
유효 비트
프로세스의 페이지가 유효한지를 나타낸다.
비트가 무효(invalid)로 설정되면, 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
운영체제는 이 비트롤 통해 그 페이지에 대한 접근을 허용 또는 허용하지 않을 수 있다.
공유 페이지
페이징의 장점은 공통의 코드를 공유할 수 있다는 점이다.
리눅스의 표준 c 라이브러리인 libc를 사용하는 상황을 생각해보자.
libc 를 물리 메모리에 하나의 사본만 저장하고, 다른 프로세스의 페이지 테이블은 해당 사본으로 매핑 시켜서 공유한다.
대신, 해당 코드가 "재진입 코드" 여야 한다.
재진입 코드란, 여러 프로세스가 호출했을 때에도 안전하게 사용 가능한 코드를 말한다.
공유 페이지를 사용하면, 메모리 공간을 절약할 수 있다.
페이지 테이블의 구조
계층적 페이징
현대 컴퓨터는 매우 큰 주소 공간(2^32 ~ 2^64)을 가진다.
이러한 환경에서는 페이지 테이블도 상당히 커진다.
32비트 환경에서, 각 프로세스는 페이지 테이블만을 위해서도 4 MB의 공간이 필요하다.
페이지 테이블의 크기를 줄이기 위해 여러 가지 방법을 사용한다.
2단계 페이징 기법
페이지 테이블 자체를 페이징 시키는 것이다.
이러한 방식을 사용하면, 페이지 접근 형식도 바뀐다.
바깥 페이지 테이블과 안쪽 페이지 테이블의 페이지 번호를 각각 넣어주어야 한다.
결과적으로, 페이지 테이블을 통해 물리 주소를 변환하는 과정은 아래와 같다.
해시 페이지 테이블
주소 공간이 32비트보다 커지면, 가상 주소를 해시로 사용하는 "해시 페이지 테이블"을 많이 쓴다.
해시 페이지의 각 항목은 연결 리스트로 구현되어 있다.
연결 리스트의 각 노드는 가상 페이지 번호, 매핑되는 프레임 번호, 다음 노드 포인터를 가지고 있다.
페이지 번호가 오면 그것을 해싱한다.
해싱 값을 가지고 해시 페이지 테이블에서 연결 리스트를 순회하며 가상 페이지 번호를 비교해본다.
일치하면 매핑되는 프레임 번호를 가져와 물리 주소를 얻는다.
일치되지 않으면, 다음 노드로 동일한 과정을 반복한다.
64비트 시스템에서 유용하도록 변형된 해시 테이블 페이지인 클러스터 페이지 테이블이 있다.
해시 페이지 테이블의 각 항목이 한 개의 페이지만 가리키지만, 클러스터 페이지 테이블의 각 항목은 여러 개의 페이지를 가리킨다.
따라서, 한 개의 페이지 테이블 항목이 여러 프레임에 대한 변환 정보를 지닐 수 있다.
스와핑(Swapping)
프로세스의 페이지 일부분을 임시로 보조기억장치에 내보내거나, 다시 메모리로 적재하는 것을 말한다.
실행에 필요한 페이지만 메모리에 적재할 수 있기 때문에, 메인 메모리보다 큰 용량의 여러 프로세스를 동시에 실행하는 것이 가능하다.
페이지-아웃 연산은 페이지를 메모리에서 저장장치로 이동시킨다.
페이지-인 연산은 페이지를 저장장치에서 메모리로 적재한다.
참고로, 모바일 시스템에서는 스와핑을 지원하지 않는게 일반적이다.
일반적으로 모바일 장치는 하드디스크보다 플래시 메모리를 사용하기 때문에, 저장 공간이 적고, 또한 플래시 메모리는 사용 가능 횟수가 정해져 있다.
스와핑 대신에, 사용 가능한 메모리가 적어지면 Apple의 iOS나 Android의 경우 앱에게 자발적으로 메모리를 반환하도록 요청한다.
코드 같은 읽기 전용 데이터는 반환되고 다시 적재될 수 있으나, 스택과 같은 데이터는 절대 제거될 수 없다.
현대 OS에서의 페이징 방식은?
대부분 계층적 페이징 방식을 사용한다.
32비트 또는 64비트와 같이 시스템의 크기에 따라 단계가 추가되는 방식으로 사용된다.
공룡책 10판 417쪽 참고
