배경
1.
기본 하드웨어
•
CPU 코어에 내장된 레지스터들은 일반적으로 CPU 클록(clock) 1사이클 내에 접근 가능하지만, 메모리 버스를 통해 접근하는 메인 메모리는 많은 CPU 틱(clock tick)이 소요된다. 이런 경우 CPU가 필요한 데이터가 없어서 지연되는(stall) 현상이 발생하는데, 캐시를 통해 이를 해결한다.
•
이러한 물리 메모리의 상대적인 속도 차이를 고려하고 올바른 동작을 보장하기 위해 운영체제가 CPU와 메모리 간의 접근에 개입하면 성능이 떨어지기 때문에 반드시 하드웨어가 이를 지원해야한다.
•
각각의 프로세스가 독립된 메모리 공간을 가지도록 기준(base) 레지스터와 상한(limit) 레지스터라는 두 개의 레지스터를 사용해 보호한다.
•
기준 레지스터는 가장 낮은 물리 메모리의 주소값을 저장하고, 상한 레지스터는 할당된 메모리의 크기를 저장한다.
•
기준 레지스터와 상한 레지스터는 특권 명령을 통해서만 로드되는데, 운영체제에서만 레지스터들의 값을 변경할 수 있도록 하여 사용자 프로그램이 레지스터의 내용을 변경하는 것을 막기 위함이다.
2.
주소의 할당
•
운영체제가 프로세스를 실제 물리 메모리에 로드하는 방법은 다음과 같다.
◦
원시 프로그램에서는 주소를 숫자가 아닌 심볼 형태로 표현되는데, 컴파일러에서 원시 프로그램의 심볼 주소를 재배치 가능 주소로 바인딩 시킨다.
◦
링커나 로더가 재배치 가능 주소를 절대 주소로 바인딩 시킨다.
•
메모리 주소 공간에서 명령어와 데이터의 바인딩은 바인딩이 이루어지는 시점에 따라 3가지로 구분된다.
◦
컴파일 시간(compile time)
◦
적재 시간(load time)
◦
실행 시간(execution time)
3.
논리 주소 공간 vs 물리 주소 공간
•
CPU가 생성하는 주소를 일반적으로 논리 주소(logical address)라 하며, 메모리가 취급하는 주소(메모리 주소 레지스터에 주어지는 주소)를 물리 주소(physical address)라 한다.
•
컴파일 시간 바인딩이나 적재 시간 바인딩은 논리 주소와 물리 주소가 같지만, 실행 시간 바인딩은 논리 주소와 물리 주소가 다른다. 이렇게 물리 주소와 다른 논리 주소를 가상 주소(virtual address)라 한다.
•
프로그램 실행 중에는 이런 가상 주소를 물리 주소로 바꾸어주기 위해 메모리 관리 장치(MMU, Memory Management Unit)이라는 하드웨어 장치가 사용된다.
•
기준(base) 레지스터 기법을 일반화 시킨 단순한 MMU를 재배치(relocation) 레지스터라 부르는데, 주소가 메모리로 보내질 때마다 재배치 레지스터 속에 들어있는 값을 더해 물리 주소로 변환하는 방식이다.
4.
동적 적재
•
동적 적재(dynamic loading)는 각 루틴이 호출되기 전까지 메모리에 올라가지 않고 재배치 가능한 상태로 대기하고 있다가 해당 루틴이 호출되면 메모리에 올라오는 방식이다.
•
프로세스가 실행되기 위해 해당 프로세스 전체가 메모리에 로드되는 방식에서, 메모리의 공간을 더 효율적으로 이용하기 위해 동적 적재 방식을 사용한다.
•
먼저 main 프로그램이 메모리에 올라와 실행되고, 다른 루틴을 호출하게 되면 해당 루틴이 메모리에 올라와 있는지 조사한다. 적재 되어있지 않다면 재배치 가능 연결 적재기(relocatable linking loader)가 불려 해당 루틴을 메모리에 가져오고 테이블에 변화를 기록한다.
5.
동적 연결 및 공유 라이브러리
•
동적 연결 라이브러리(DLL, Dynamic Linking Library)는 사용자 프로그램이 실행될 때 사용자 프로그램에 연결되는 시스템 라이브러리이다.
•
동적 연결은 동적 적재와 유사한데, 동적 적재에서는 로딩(loading)이 실행 시까지 미루어지지만 동적 연결은 연결(linking)이 실행 시까지 미루어진다.
•
라이브러리가 프로그램의 이진 이미지(image)에 끼어들어가는 정적 연결(static linking)에 비해, 실행 시까지 라이브러리의 연결을 미루는 동적 연결은 실행 이미지를 줄일 수 있고 메인 메모리의 낭비를 막을 수 있다.
•
또한 DLL은 라이브러리를 여러 프로세스 간에 공유할 수 있어 메인 메모리에 DLL 인스턴스가 하나만 존재해 메모리를 아낄 수 있다는 것이다. 이런 이유로 DLL은 공유 라이브러리라고도 불린다.
연속 메모리 할당
1.
메모리 보호
•
재배치 레지스터는 기준 레지스터와 상한 레지스터를 통해 프로세스의 논리 주소 범위를 저장한다. 이를 통해 프로세스가 자신이 소유하지 않는 메모리에 접근할 수 없게 강제할 수 있다.
2.
메모리 할당
•
메모리를 할당하는 가장 간단한 방법 중 하나는 프로세스를 메모리의 가변 크기의 파티션에 할당하는 것이다. 이 방법을 가변 파티션 기법이라 하는데, 각 파티션에는 하나의 프로세스만 적재될 수 있다.
•
가변 파티션 기법에서 운영체제는 사용 가능한 메모리 부분과 사용 중인 부분을 알려주는 테이블을 가지고 있다. 사용 가능한 부분의 메모리 블록을 hole이라 부르는데, 프로그램을 실행시키다보면 다양한 크기의 hole이 생기게 된다.
•
프로세스가 들어오면 운영체제는 각 프로세스가 메모리를 얼마나 필요로 하는지, 사용 가능한 메모리 공간이 어디에 얼만큼 있는지 확인 후 메모리 공간을 프로세스에 할당한다. 프로세스가 끝나면 할당 받은 메모리를 반납하고 운영체제는 다른 프로세스에 해당 공간을 할당할 수 있다.
•
위 그림처럼 프로그램을 실행시키다보면 메모리에 다양한 크기의 hole이 여기저기에 생기게 되는데, 운영체제는 이런 hole 중에 적합한 크기에 프로세스를 할당해야한다.
•
이런 문제를 동적 메모리 할당 문제(dynamic sotrage allocation problem)이라 하는데, 해결 방법은 3가지가 있다.
◦
최초 적합
▪
hole 집합의 시작부터 검색하거나 이전 검색에 이어서 검색하여, 첫 번째 사용 가능한 가용 공간을 할당하는 방법이다.
◦
최적 적합
▪
사용 가능한 공간 중 가장 작은 것을 선택하는 방법으로, hole 집합이 크기 순으로 정렬되어 있지 않다면 전체를 검색해보아야 한다.
◦
최악 적합
▪
가장 큰 가용 공간을 선택하는 방법으로, 이 역시 hole 집합이 크기 순으로 정렬되어 있지 않다면 전체를 검색해보아야 한다.
3.
단편화
•
외부 단편화(external fragmentation)는 프로세스들이 메모리에 적재되고 제거되는 일이 반복되어, 너무 작은 가용 공간들이 많이 발생하여 이를 전부 합치면 충분한 공간이 되지만 분산되어 있어 사용하지 못하는 문제이다.
•
최초 적합과 최적 적합 전략 모두 외부 단편화 문제가 발생한다. 최초 적합의 경우 N개의 블록이 할당되면 0.5N개의 블록이 단편화 때문에 손실될 수 있다는 50% 규칙이 있다.
•
내부 단편화(internal fragmentation)는 메모리를 블럭 단위로 할당을 할 때, 블럭의 최소 단위로 인해 남는 메모리 조각이 발생하는 문제이다.
•
외부 단편화 문제는 가용 공간을 한 곳으로 모으는 압축(compaction)을 통해 해결할 수 있지만, 컴파일 시간이나 적재 시간에 정적으로 메모리 할당이 이루어지는 경우에는 압축을 할 수 없고 압축을 하더라도 그로 인한 오버헤드가 발생한다.
•
외부 단편화 문제의 또 다른 해결책은 페이징 기법이 있다.
페이징(Paging)
1.
기본 방법
•
물리 메모리는 프레임(frame)이라 불리는 같은 크기의 블록으로 나누어지는데, 논리 메모리는 페이지(page)라 불리는 블록으로 나누어져 있다. 프로세스가 실행 될 때 해당 프로세스의 페이지를 메인 메모리 프레임으로 로드하는데, 메모리 프레임의 묶음을 페이지와 동일한 크기의 블록으로 나누어 저장하는 방법이다.
•
CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 오프셋(d) 두 개의 부분으로 나누어진다. 페이지 번호는 프로세스 페이지 테이블(page table)에 접근할 때 사용되며, 페이지 테이블은 물리 메모리의 각 프레임 시작 주소를 가지고 있다. 오프셋은 참조되는 프레임 안에서의 위치로, 프레임의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 된다.
•
페이징 자체는 일종의 동적 재배치로, 모든 논리 주소를 페이징 하드웨어에 의해 실제 주소로 바인딩한다.
•
페이징 기법을 사용하면 외부 단편화 문제가 발생하지 않지만, 내부 단편화 문제가 발생한다.
•
페이징 기법을 사용하기 위해서는 어느 프레임이 할당되어 있고 어느 프레임이 사용 가능한지 프레임 테이블(frame table)을 통해 확인한다.
2.
하드웨어 지원
•
페이지 테이블은 프로세스별 자료구조이므로, 각 프로세스의 프로세스 제어 블록에 다른 레지스터 값과 함께 저장된다.
•
페이지 테이블은 전용 고속 하드웨어 레지스터 집합으로 구현되어 페이지 주소 변환에 효율적이다. 하지만 이 방법은 큰 페이지 테이블을 가지는 경우 적절하지 못하기 때문에, 최신의 대부분의 컴퓨터는 페이지 테이블을 메인 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR, page-table base register)로 페이지 테이블을 가리키도록 한다.
•
메인 메모리에 페이지 테이블을 저장하는 방식은 문맥 교환 속도가 빨라지지만 CPU가 메모리에서 데이터를 2번 읽어가야 하는 과정이 추가되어 느려진다. 이를 해결하기 위해 TLB(Translation look-aside buffers)라는 소형 하드웨어 캐시가 사용된다.
•
TLB는 key와 value로 구성되어 있는데, 페이지를 검색하면 key(페이지 번호)를 비교하여 매우 빠르게 검색한다. 페이지 번호가 TLB에 없다면(TLB miss), TLB에 페이지 번호(key)와 프레임 번호(value)를 새로 저장한다.
•
TLB가 가득차면 교체 정책에 따라 기존 항목 중 하나를 제거하고 저장한다. 이에 특정 항목들에 대해 고정을 지원하는 TLB가 있는데, 고정된 항목은 제거될 수 없다.
•
어떤 TLB는 각 항목에 ASIDs(address-space identifiers)를 저장하는데, 해당 TLB 항목이 어느 프로세스에 속하는 것인지 나타낸다. 이는 TLB에서 가상 주소를 변환할 때 ASID와 프로세스의 ASID가 맞는지 확인하여 프로세스를 보호하기 위해 사용한다.
3.
보호
•
페이지 테이블에서 페이지마다 붙어있는 보호 비트(protection bits)를 통해 read-only와 read-write 모드를 확인하여 허용하는 접근인지 아닌지를 검사한다. 읽기 전용 페이지에 대해 쓰려 한다면 운영체제가 트랩(memory protection violation)을 걸어준다.
•
페이지 테이블의 각 엔트리에는 유효(valid)/무효(invalid)를 나타내는 비트가 존재하는데, 유효인 경우 페이지가 논리 주소에 잘 매핑되어 있음을 나타내며 무효인 경우 해당 페이지가 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
•
일부 시스템에서는 페이지 테이블의 크기를 나타내는 페이지 테이블 길이 레지스터(PTLR, page table length register)을 제공하여, 프로세스가 제시한 주소가 유효한 범위 내에 있는지 비교한다.
4.
공유 페이지
•
페이지 기법의 장점은 공통되는 코드를 공유할 수 있다는 점이다. 실행시간 라이브러리 외에도 컴파일러와 데이터 베이스 시스템 등 많이 사용되는 다른 프로그램들도 공유할 수 있다.
•
메모리 공유는 프로세스 간의 상호 통신(IPC)를 통해서 공유되는데, 어떤 운영체제에서는 페이지 공유를 통해서 이를 구현하기도 한다.
페이지 테이블의 구조
1.
계층적 페이징
•
최신의 컴퓨터는 매우 큰 주소 공간을 가지기 때문에 페이지 테이블도 상당히 커야한다. 예를 들면, 32비트 시스템에서는 페이지의 크기가 4KB라면 페이지 테이블은 100만개 이상의 항목으로 구성되고 페이지 테이블만으로도 4MB의 공간을 차지하게 된다. 이렇게 페이지 테이블이 매우 큰 경우 페이지 테이블을 여러 개의 작은 조각으로 나누어 저장한다.
•
2단계 페이징 기법(tow-level paging schema)는 페이지 테이블 자체를 다시 페이징하여 2단계로 페이징을 하는 방법이다. 2단계 페이징 기법은 2개의 페이지 번호와 오프셋을 가지는데, 주소 변환이 바깥 페이지 테이블에서 시작하여 안쪽으로 들어오기 때문에 forward-mapped 페이지 테이블이라고도 부른다.
•
64비트 시스템에서는 이러한 2단계 페이징 기법을 적용하더라도 바깥 페이지 테이블은 16GB의 크기가 필요하다. 그런 이유로 일반적인 64비트 구조에서는 페이지 테이블이 부적합하다.
2.
해시 페이지 테이블
•
해시 페이지 테이블(hashed page tables)은 가상 주소 공간의 페이지 번호를 해싱하여 해시 페이지 테이블에 저장하는 방식이다. 테이블에서 충돌이 발생하는 부분은 연결 리스트를 통해 추가하고, 페이지를 검색할 때는 해당 연결 리스트를 순회하며 일치하는 가상 페이지 번호를 찾아 반환한다.
•
더 효율적으로 사용하기 위해 해시 페이지 테이블을 변형한 클러스터 페이지 테이블도 있다. 클러스터 페이지 테이블은 페이지 테이블에 하나의 페이지가 아니라 여러 페이지를 가리킨다. 클러스터 페이지 테이블은 성긴 주소 공간에 유용하게 사용된다.
3.
역 페이지 테이블
•
페이지 테이블 항목이 매우 많아지는 것과 그로 인해 물리 메모리 사용을 추적하기 위해 많은 비용이 든다는 점을 개선하는 또 다른 방법은 역 페이지 테이블(inverted page table)이다.
•
역 페이지 테이블은 페이지 테이블의 구조를 반전시켜, 실제 페이지 프레임과 해당 프레임을 사용하는 프로세스를 매핑한 매핑 정보를 저장한다. 각 프로세스마다 엔트리를 가지고 있어, 엔트리에 해당 프로세스의 가상 주소 공간에서 페이지와 실제 주소 공간에서 페이지 프레임 간의 매핑을 저장하고 있다.
•
역 페이지 테이블은 프로세스 ID, 페이지 번호, 페이지 오프셋으로 구성되어 있으며, 프로세스 ID와 페이지 번호를 받아 역 페이지 테이블에서 일치하는 게 있는지 확인한다.
•
역 페이지 테이블은 논리 페이지마다 항목을 가지는 대신 물리 프레임에 대응되는 항목만 테이블에 저장하기 때문에 훨씬 적은 메모리 공간을 사용한다.
스와핑
1.
기본 스와핑
•
기본 스와핑은 실제 물리 메모리보다 더 많은 프로세스를 수용할 수 있다는 장점이 있다.
•
기본 스와핑은 메인 메모리와 백업 저장장치 간에 전체 프로세스를 이동시키며, 백업 저장 장치는 프로세스의 크기에 영향을 받지 않을만큼 충분히 커야한다.
•
다중 스레드 프로세스와 같이 프로세스가 백업 저장장치로 스왑 될 때, 스레드 데이터 자료구조와 같은 프로세스와 관련된 모든 자료구조도 스왑 되어야 한다.
2.
페이징에서의 스와핑
•
표준 스와핑은 메모리와 백업 저장장치 간에 프로세스 전체를 이동하는데 시간이 매우 많이 소요되기 때문에 잘 사용되지 않는다. 최신의 운영체제에서는 프로세스 전체가 아니라 프로세스 페이지를 스왑할 수 있는 변형 스와핑을 사용한다.
•
페이지-아웃 연산은 메모리에서 백업 저장장치로 페이지를 이동시키고, 페이지-인 연산은 백업 저장장치에서 메모리로 페이지를 이동시킨다.
3.
모바일 시스템에서의 스와핑
•
일반적으로 모바일 장치들은 하드디스크보다 플래시 메모리를 사용하기 때문에, 스와핑은 저장 공간을 줄인다는 이유로 잘 사용되지 않는다.