주 메모리에는 여러개의 프로세스가 적재되어 있고, 운영체제는 이러한 프로세스를 효율적으로 처리하기 위해 메모리를 효율적으로 관리해야할 필요가 생겼습니다. 이를 위해 두가지 알고리즘인 페이징과 세그먼트 를 다루겠습니다. 최근 디자인이 하드웨어와 운영체제를 밀접하게 통합하고 있지만 본 장에서 설명하는 알고리즘은 대부분 하드웨어 지원을 필요로 합니다.
메모리의 기본 개념
기본적인 하드웨어 구조
메모리는 각각 주소가 할당된 일련의 워드 또는 바이트들로 구성되며 CPU는 PC(Program Counter)가 지시하는 대로 메모리로부터 다음 실행할 명령어를 가져오고, 필요한 경우 추가적인 데이터를 더 가져오거나 데이터를 메모리로 내보냅니다.
전형적인 명령 실행은 먼저 메모리로부터 한 명령어를 가져오는 데서부터 시작되어, 그 다음 명령어를 해독하고 메모리에서 피연산자를 가져와 피연산자에 대해 명령어를 실행합니다.
CPU가 주 메모리에 접근하기 위해서는 많은 CPU 클록 틱 사이클이 소요되며, 이 때문에 CPU가 명령어를 실행하지 못하고 대기하는 시간이 길어집니다. 이러한 상호아은 주 메모리 접근이 빈번하게 일어나는 경우에는 큰 문제가 되며 이를 해결하기 위해 캐기 라고 부르는 메모리 버퍼를 사용합니다.
메모리에 많은 프로세스들이 적재되어 있는데 각각의 프로세스가 다른 프로세스가 사용하는 메모리 영역을 침범하면 큰 문제가 생길 것 입니다. 즉, 각각의 프로세스는 독립된 메모리 공간을 가지고 특정 프로세스만 접근할 수 있는 메모리 영역을 하드웨어 단에서 정해주어야 할 필요가 있습니다. 이 문제는 기준(base)과 상한(limit)이라고 불리는 두개의 레지스터들을 사용 하여 해결합니다. 기준 레지스터 는 가장 작은 합법적인 물리 메모리 주소의 값을 저장하고, 상한 레지스터 는 주어진 영역을 크기를 저장합니다. 이러한 기준과 상한 레지스터는 여러가지 특권 명령을 사용하는 운영체제에 의해서만 적재됩니다.
하지만, 커널 모드 에서 실행되는 운영체제는 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 어떠한 제한도 받지 않는다.
프로세스는 실행되기 위해 디스크에서 메모리로 이동되고, 디스크에서 메모리로 들어오기를 기다리고 있는 프로세스 들은 입력 큐(input que) 를 형성합니다. 이 큐에서 하나의 프로세스를 선택하여 메모리로 적재한 후 실행합니다.
논리 주소와 물리 주소
CPU는 오로지 논리 주소 만을 사용하여 작동하는 반면 메모리가 취급하는 주소는 물리주소 입니다. 따라서 프로그램이 실행되기 위해서는 CPU가 다루는 논리주소가 물리주소로 변환이 되어야 하며 이것은 메모리 관리기(Memory Management Unit) 에 의해 처리됩니다.
이렇게 모든 논리주소와 물리주소 사이의 변환은 MMU에서 처리하며 CPU는 물리주소에 전혀 관심을 두지 않습니다. 즉, 사용자 프로그램은 실제적인 물리주소를 결코 알 수 없습니다.
동적 적재
일반적으로 CPU가 프로세스를 실행하기 위해서는 프로세스 전체가 메모리에 적재되어야 했다. 하지만 동적 적재 는 프로세스의 부분만이 메모리에 적재해도 프로세스를 실행 할 수 있도록 해 준다. 동적 적재에서 각 루틴은 실제로 호출되기 전까지는 메모리에 적재되지 않고 재배치 가능한 상태로 디스크에서 대기하고 있다. 이러한 동적 적재의 장점은 사용되지 않는 루틴들의 경우 절대로 미리 적재되지 않는다는 것이다.
이러한 동적 적재는 공유 라이브러리 를 사용하는 데에 사용될 수 있으며, 주로 시스템 라이브러리에 사용된다. 만일 이 방식이 없다면 모든 프로그램들은 그들의 이진 프로그램 이미지 내에 시스템 라이브러리의 복사본 또는 적어도 참조되는 루틴의 복사본을 가지고 있어야 할 것이다. 하지만 이러한 동적 연결에서는 라이브러리를 호출하는 곳 마다 스텁(stub) 이 생기게 되고, 이 스텁은 메모리에 적재하는 라이브러리를 찾는 방법 또는 메모리에 없을 경우 라이브러리에 적재하는 방법을 알려주는 작은 코드 조각이다. 스텁 은 필요한 라이브러리 루틴이 이미 메모리에 존재하는 지를 검사하고 없으면 루틴을 메모리로 적재한다.
동적 연결 이 없었다면 새로운 라이브러리를 사용하기 위해 모든 프로그램이 새로 연결되어야 한다.
이러한 시스템을 공유 라이브러리 라 한다.
스와핑
프로세스가 메모리에서 실행되기 위해서는 메모리에 적재되어 있어야 하며 이렇게 디스크에서 메모리에 프로세스를 적재하는 것은 스와핑 이라고 한다. 스와핑 은 반드시 보조 메모리가 필요하며 보통 디스크를 사용한다. CPU는 준비완료 큐 에서 프로세스를 가져와 CPU를 할당해 주며, CPU 스케줄러는 다음 프로세스를 고를 때 디스패처 를 호출한다. 디스패처 는 이 큐에 있는 다음 프로세스가 메모리에 적재되어 있는지를 확인하여 없다면 디스크에서 불러들이도록 하여야 한다.
연속 메모리 할당
주 메모리는 여러 사용자 프로세스를 수용해야 하며, 일반적인 메모리 할당방법 중의 하나인 연속 메모리 할당 에 대해 배워보도록 하겠습니다.
메모리는 일반적으로 두 개로 나누어집니다. 하나는 운영체제를 위한 것 이고 다른 하나는 사용자 프로세스를 위한 것 입니다. 운영체제는 메모리의 어느 쪽 끝에도 위치할 수 있으며, 이 결정에 영향을 미치는 중요한 요인은 인터럽트 벡터입니다.
보통 여러개의 프로세스가 메모리에 적재되어야 하며, 입력 큐 에서 대기 중인 프로세스들에게 메모리를 어떻게 할당하는 것이 좋은가를 생각할 필요가 있습니다.
이번에 배울 연속 메모리 할당 에서는 프로세스는 연속된 메모리 공간을 차지하게 됩니다.
연속 메모리 할당에서는 여기 메모리 저기 산재해 있는 여러 크기의 자유 공간 중에서 적절한 것을 찾아 할당하게 됩니다. 만약 자유공간의 크기가 크면 두 개로 나누어 하나는 프로세스에게 할당하고 나머지 하나는 다시 자유공간으로 되돌려 줍니다. 만약 되돌려 준 자유공간이 주변의 공간과 인접해 있다면, 이 두개의 블록을 합쳐서 한개의 큰 자유 공간 블록으로 만들어 줍니다.
이러한 기법은 동적 메모리 할당 문제 은 특별한 예이며, 자유 공간 리스트로부터 크기 n-바이트 블록 요청을 어떻게 만족시켜 줄 수 있는지를 결정하는 문제입니다. 해결방안에는 크게 3가지 정도가 있는데, 최초 적합 기법은 요청을 만족시키는 충분히 큰 첫 번째 가용공간을 할당해 주는 것이며, 최적 적합 은 요청을 만족시키는 충분히 큰 공간들 중에서 제일 작은 자유 공간을 활도해 줍니다. 최악 적합 은 가장 큰 가용 공간을 선택합니다.
단편화
위의 예처럼 자유 공간을 임의의 조각으로 나누어 할당하는 방법은 두가지 형태의 단편화 를 만들어 냅니다. 단변화의 종류에는 내부 단편화 와 외부 단편화 가 있습니다. 먼저, 외부 단편화 는 다음과 같이 설명할 수 있습니다. 가령 계속해서 자유 공간을 할당해 주다 보면 남은 자유공간들이 너무 작은 조각들로 여러 군대에 산재되어 있는 현상이 있을 수 있습니다. 이 모든 조각을 다 모으면 큰 자유공간이 되지만 너무 잘게 쪼게어져 있기 때문에 사용하지 못하는 공간이 되어 버립니다. 이를 해결하는 방법은 압출 을 하는 것입니다. 압축 이란 이런 작은 자유 공간 조각들을 하나의 큰 조각으로 합치는 것으로 사이 사이의 프로세스가 차지하는 공간을 한쪽으로 몰아 재배치 하는 것입니다. 때문에 이 경우에는 프로세스내의 모든 주소들이 동적으로 재배치 되어야 하기 때문에 실행시간이 길어집니다. 다음으로는 내부 단편화 가 있습니다. 보통 자유 공간을 할당해 줄 때는 메모리가 분할된 크기의 정수 배로만 해주는 것이 보통이며 때문에 할당된 메모리 중 프로세스가 사용하지 않는 공간이 생길 수 있으며 이를 내부 단편화 라고 할 수 있습니다. 이러한 내부 단편화 를 줄이기 위해서는 할당해주는 메모리 조각을 최대한 작게 해 주는 것이 좋습니다.
이러한 다양한 단편화를 줄이기 위한 방법으로는 한 프로세스의 주소 공간을 여러 개의 동떨어진 공간으로 배정하는 것입니다. 그 대표적인 예로는 페이징과 세그먼테이션 이 있습니다.
페이징
페이징의 기본적인 개념은 바로 논리주소 공간이 연속된 하나의 공간에 모두 모여 있어야 한다는 제약을 없애는 것입니다.
물리 메모리는 프레임 이라고 불리는 고정 크기의 블록으로 나누어져 있으며, 논리 메모리는 페이지 라고 불리는 고정 크기의 블록으로 나뉘어져 있습니다.
CPU 는 논리 메모리를 기준으로 프로그램을 처리하며 이러한 논리 주소는 페이징 하드웨어의 페이지 테이블 에 의해 물리 주소로 변환된다. 또, 모든 물리 주소는 핻아 논리 주소로 사상될 수 있다. CPU에서 나오는 모든 주소는 논리 주소로써 페이지 번호와 페이지 변위 두 개의 부분으로 나누어 진다. 페이지 번호 는 페이지 테이블 에 접근할 때 사용되며, 해당 페이지 번호에 해당하는 주 메모리 내의 페이지의 기준 주소를 찾기 위해 사용되며, 페이지 변위 는 해당 프레임 내에서의 변위 를 나타낸다. 페이지 주소 에 페이지 변위 를 더하면 메모리 장치로 전송될 물리 주소가 된다.
프레임의 크기와 마찬가지로 페이지의 크기 도 하드웨어에 의해 결정된다. 만약 논리주소 공간의 크기가 2^n 이고 페이지의 크기가 2^m이면 논리 주소의 상위 m-n 비트는 페이지 번호를 나타내며, 하위 m 비트는 페이지 변위를 나타낸다.
페이징은 기본적으로 메모리를 정해진 페이지 사이즈로 잘라서 사용하기 때문에 외부 단편화가 발생하지 않는 대신 통산 페이지 사이즈의 반 정도의 내부 단편화 가 생기게 된다.
페이징의 가장 중요한 특징은 메모리에 대한 사용자가 생각하는 메모리와 실제 물리 메모리를 명확하게 분리한다는 사실이다. 그러나 실제로 프로그램은 물리 메모리 여러 곳에 프레임 단위로 산재되어 있고, 이 물리 메모리는 다양한 프로그램을 적재하고 있다. 사용자가 생각하는 메모리와 실제 메모리의 차이는 주소 변환 하드웨어에 의해 가려진다.
대부분의 운영체제는 프로세스마다 하나의 페이지 테이블을 할당합니다. 페이지 테이블을 가르키는 포인터는 다른 레지스터 값과 함께 프로세스 제어 블록(Process Control Block) 에 저장된다. 디스패처가 어떤 프로세스를 시작할 때 이 레지스터들을 다시 적재하면 페이지 테이블도 함께 사용할 수 있게 됩니다.
이러한 페이지 테이블 은 대부분의 경우 매우 크기 때문에 레지스터에 저장되지 못하고 주 메모리에 저장된 후 페이지 테이블 기준 레지스터(PTBR: Page Table Base Register) 로 하여금 페이지 테이블을 가르키도록 합니다. 하지만 이 경우에는 특정 정보에 접근하기 위해 두번의 메모리 접근이 필요합니다. 페이지 테이블에 접근하기 위해 한번 주 메모리에 접근하고, 얻은 주소를 통해 주 메모리에서 정보에 접근하기 위해 또 한번 접근하게 됩니다. 그래서 메모리 접근은 두 배로 느려 지며 이를 해결하기 위한 표준 방법으로 TLB(Translation Look-aside Buffers) 라고 불리는 특수한 소형 하드웨어 캐시가 사용됩니다. TLB의 각 항목은 키와 값 의 두 부분으로 구성됩니다. TLB에 페이지를 찾아달라는 요청이 들어오면 찾고자 하는 페이지를 동시에 모든 내부 키(페이지 번호)와 비교하여 해당하는 페이지 번호에 해당하는 프레임 번호를 알려줍니다. 하지만 이러한 TLB 하드웨어는 가격이 매우 비싸므로 페이지 테이블 의 일부분 밖에 들고있을 수가 없습니다. TLB에서 찾아진 페이지 번호와 프레임 번호는 TLB에 추가되어 다음 참조 시 매우 빠르게 처리할 수 있습니다. 이러한 페이지 번호는 수시로 교체되며 LRU 부터 무작위 교체까지 다양한 정책이 사용됩니다.
어떤 TLB는 각 항목에 ASID(Address Space IDentifiers) 를 저장하기도 하며, 이 ASID는 그 TLB 항목이 어느 프로세스에 속한 것인지를 알려주며, 이러한 ASID를 통해 TLB 안에 여러 프로세스들의 정보를 동시에 보관할 수 있게 됩니다. 여기서 페이지 번호가 TLB 에서 발견되는 확률을 적중률(hit ratio) 라고 합니다.
페이지 테이블의 다양한 구조
각 프로세스가 필요한 페이지들은 매우 크므로 해당 프로세스의 페이지 테이블 또한 매우 커지게 됩니다. 이를 막기 위해 다양한 페이지 테이블 구조가 있는데 대표적인 테이블 구조인 계층적 페이징, 해시된 페이지 테이블, 역 페이지 테이블 에 대해 알아보겠습니다.
계층적 페이징
계층적 페이징이란 페이지 테이블이 계층적으로 나타나는 것 입니다.
즉, 페이지 테이블이 두개로 나뉘어 하나의 페이지 테이블은 다음 페이지 테이블에 대한 포인터를 가지고 있게 됩니다. 이러한 계층적 페이지의 구조를 전방 사상 페이지 테이블(forward mapped page table) 이라고 합니다.
해시된 페이지 테이블
페이지 테이블을 사이즈를 줄이기 위해서 해시된 페이지 테이블 이 도입될 수도 있습니다. 주소 공간이 32bit 보다 커지는 경우 가상 주소를 해시 값으로 사용하는 해시 페이지 테이블 을 많이 사용합니다.
역 페이지 테이블
역 페이지 테이블은 일반 테이블 페이지 처럼 메모리 페이지 값에 대한 물리 페이지를 가지는 것이 아니라 특정, 물리 페이지에 대한 논리 페이지 값을 가지는 테이블 입니다. 이렇게 되면 시스템에는 단 하나의 페이지 테이블 만 존재하게 되며, 모든 물리 페이지는 특정 논리 페이지를 가르키게 됩니다. 이 경우에는 물리 프레임에 해당한느 항목만 테이블에 저장하면 되기 때문에 메모리에서 훨씬 작은 공간을 차지하게 되지만, 주소변환 시간은 더 오래 걸릴 수 있습니다.
세그먼테이션
페이지 테이블의 가장 큰 문제는 사용자가 사용하는 메모리 공간과 실제 물리 메모리 공간이 분리되어 헷갈린 다는 점입니다.
세그먼테이션 이란 이와 같이 메모리를 바라보는 사용자 관점을 그대로 반영합니다. 세그먼테이션에서 논리 구조 공간 은 세그먼트 들의 집합이며, 물리 메모리도 같은 원리로 세그먼테이션이 이루어집니다.
Comments