프로세스 로드

프로그램은 운영체제가 프로세스를 구동하는데 사용되는 executable 한 파일이다. 프로그램들은 메모리에 로드되어 프로세스가 된다. 프로그램은 로더에 의해 메모리에 적재된다.

• 메모리는 어디에 어떻게 적재하는가?
• 프로그램의 크기가 매우 커 물리 메모리가 감당하기 어렵다면?
• 컨택스트 스위칭이 suspend에 걸쳐 이루어진다면?

프로세스

시스템은 프로세스를 관리하기 위해 프로세스마다 PCB(Process Control Block; 프로세스 제어 블록)을 생성한다. PCB는 프로세스의 상태, 프로세스의 메모리 주소, 프로세스의 레지스터 값, 프로세스의 스케줄링 정보 등을 담고 있다. PCB가 있다면 PCB가 나타내는 대상은 프로세스라고 할 수 있다.

프로세스는 다양한 단위로 설명할 수 있다.

• 비동기적 행위를 일으키는 주체
• CPU가 할당되는 대상
• 운영체제과 관리하는 최소 단위 프로그램
• 메모리에 주소공간을 갖는 대상(프로그램은 메모리에 주소공간을 갖지 못함)

또한 실행파일이 메모리에 올라가는 과정을 로딩, 이 과정을 수행하는 프로그램을 로더라고 할 수 있다.

운영체제는 프로세스가 동작할 메모리 공간을 확보하고, 프로세스가 의존성을 갖는 라이브러리를 먼저 링크한다. 프로그램은 일반적으로 사용할 메모리 정보를 상대 주소로 가지고 있으므로, 이것을 확보한 메모리 공간에 맞게 변환 후 프로그램을 메모리에 적재한다. 이 과정에서 프로그램은 프로세스가 된다.

하지만 항상 프로그램의 메모리가 재배치되는 것은 아니다. 시스템의 목적이 단일하며 제한적이고, 예외적으로 사용될 가능성이 없으며, 프로그램이 항상 같은 메모리 공간에서 동작하도록 설계되었다면, 프로그램은 재배치 없이도 메모리에 적재될 수 있다. 이때의 로더를 절대 로더(absolute loader)라고 한다.

프로세스의 메모리 공간

메모리는 항상 제한된 자원이므로 여러 프로세스가 나누어 사용하여야 한다. 하지만 한 프로그램 차원에서 다른 프로그램의 메모리 사용을 고려하면서 자기 자신의 메모리 사용 정책을 세우는 것은 매우 위험하고¹ 어렵다².

¹ 각자의 프로그램에게 전체 메모리 관리를 맡기면, 프로그램이 다른 프로그램이 메모리를 사용하지 못하게 할 수도 있고, 예외적인 동작을 보일 수도 있다. 최소한 선의의 프로그램에서도 그러하고, 악의적인 프로그램은 더 많은 문제를 야기할 수 있다.

² 사공이 많으면 배가 산으로 간다: 하나의 컴퓨터 위에서 동작하는 프로세스의 양을 고려했을 때, 이들 프로세스가 모두 메모리 관리에 관여한다면, 모든 프로세스의 메모리 관리 로직이 최고 퀄리티로 작성되었다고 하더라도 시스템은 매우 복잡해지고 자주 실패할 것이다.

그래서 프로세스의 메모리 공간은 운영체제에서 관리하고, 운영체제는 프로세스에게 CPU 주소 공간 전체를 독점적으로 할당하는 것처럼 보이게 한다. 프로세스는 자신이 독점적으로 할당받은 CPU 주소 공간을 사용하고, 운영체제는 프로세스가 사용하는 CPU 주소 공간을 물리 메모리의 일부에 매핑한다.

이렇게 독점적인 메모리 공간을 프로세스에게 보여주는 것을 가상 메모리라고 한다. 이렇게 하여 프로세스의 메모리 사용 동작은 운영체제에게는 예측 가능하게 되고, 개별 프로그램을 작성하는 개발자 입장에서는 다른 프로그램의 메모리 사용을 고려하지 않고도 프로그램을 작성할 수 있다.

이것은 각 프로세스들의 메모리가 격리되는 효과로도 생각할 수 있다. 따라서 악의적인 프로세스가 다른 프로세스의 메모리를 의도적으로 침범하는 것도 다소 어렵게 할 수 있다.

또한 물리 메모리는 한정되어도 가상 메모리는 더 큰 공간을 전제하고 설계될 수 있으므로, 메모리의 일부를 디스크에 임시로 저장(swap)하는 등 다양한 메모리 관리 기법을 사용할 수 있다.

메모리 할당

• 프로세스 파티셔닝
  • 연속 파티셔닝
  • 불연속 파티셔닝
• 메모리 파티셔닝
  • 가변 파티셔닝
  • 고정 파티셔닝

연속 메모리 할당 (Contiguous Memory Allocation)

각 프로세스의 영역을 연속된 메모리 공간에 배치한다.

메모리를 한 개 이상의 파티션으로 분할하고 파티션을 할당하는데, 한 프로세스는 한 파티션으로 할당한다.

• 고정 크기 할당 방법: MFT; Multiple Programming with a Fixed number of Tasks
  • 메모리 전체를 고정 크기의 $N$ 개 파티션으로 분할하고 프로세스마다 하나씩 할당한다. 이렇게 하면 수용 가능한 프로세스 수는 $N$ 개로 고정된다.
• 가변 크기 할당 방법: MVT; Multiple Programming with a Variable number of Tasks
  • 프로세스의 크기에 따라 파티션의 크기를 동적으로 할당한다.
  • 수용 가능한 프로세스 수도 가변한다.

연속 메모리 할당의 구현에는 여러 가지 방법이 동시에 사용된다.

하드웨어에서는 base register와 limit register를 사용하여 프로세스의 메모리 접근을 제한하고, addr register를 사용하여 프로세스의 메모리 접근을 제어, MMU(Memory Management Unit)를 사용하여 프로세스의 메모리 주소를 물리 메모리 주소로 변환한다.

운영체제 측에서는 모든 프로세스에 대해, 프로세스마다 ‘물리 메모리의 시작 주소’와 ‘프로세스의 크기’를 관리한다. 비어있는 메모리 영역을 관리하면서, 새 프로세스를 스케줄링해 시작할 때마다 물리 메모리 주소와 크기 정보를 CPU 내부의 레지스터에 적재한다.

연속 메모리 할당 방법은 논리 주소를 물리 주소로 변환하는 과정이 단순하고, 빠르게 메모리 액세스할 수 있다. 또한 운영체제가 관리할 정보량이 적으므로 부담이 적다.

하지만 메모리 할당의 유연성이 떨어지고 외부 단편화가 발생한다.

연속 메모리 할당에서의 메모리 배치

운영체제는 메모리 할당 상황을 확인하기 위해, 할당된 파티션에 관한 정보(할당 위치, 크기, 비어있는지 여부)를 관리한다.

메모리 할당 요청이 발생할 때 운영체제는 비어있는 파티션 중에서 적절한 파티션을 찾아 프로세스를 할당한다.

• first-fit: 비어있는 파티션 중 제일 먼저 쿼리되는 파티션에 할당한다.
• best-fit: 비어있는 파티션 중 프로세스 크기와 가장 근접한 크기의 파티션에 할당한다.
• worst-fit: 비어있는 파티션 중 프로세스 크기와 가장 먼 크기의 파티션에 할당한다.

* worst-fit은 이론적인 논의를 위해 도입된 시나리오로, 실제로는 best-fit을 목표할 것이다.
** first-fit과 best-fit도 이론적인 논의에 가깝다. first-fit으로 빠른 시간 안에 할당하고, 오래지 않아 실행-종료한다면 best-fit으로 전체 메모리 공간을 훑는것보다 효율적일 수 있다. 따라서 실제 실험에서는 best-fit이 항상 더 나은 결과를 가져오지는 않는다.

단편화

이렇게 메모리 공간을 할당하면, 합치면 분명히 비어있는 공간이 존재함에도 불구하고, 프로세스의 크기와 맞지 않아 할당할 수 없는 경우가 발생한다.

단편화는 두 가지 유형으로 발생한다.

• 외부 단편화: 할당된 메모리 공간 사이에 사용할 수 없는 공간이 형성
• 내부 단편화: 할당된 메모리 공간 내에 사용되지 않는 공간이 형성

조각모음

단편화는 조각모음(defragmentation, 혹은 압축: compaction)으로 해결할 수 있다.

이 작업에서는 이미 배치된 프로세스의 메모리 데이터를 옮기고, 변경된 주소를 모두 갱신해야 한다. 때문에 프로세스의 동작을 잠시 중단해야 하고, 프로세스 주소를 모두 갱신하는 작업 역시 비용이 크다. 단편화가 발생했을 때마다 조각모음을 수행하는 것은 비효율적이다.

버디 시스템

그래서 보완적인 방법으로 버디 시스템(Buddy System)이 제안되었다. 이것은 메모리 할당에서의 binary search처럼 생각할 수 있다.

1. 메모리 공간을 2의 제곱수 크기로 고려한다.
2. 가용한 가장 큰 메모리에서, 절반씩 쪼개면서 프로세스에 가장 잘 맞는 메모리 공간을 찾는다.
   • $2^{k - 1} < \text{size} \leq 2^k \Rightarrow \text{allocate } 2^k$
3. 프로세스 종료 후, 같은 부모를 갖는 두 개의 메모리 공간이 모두 비어있다면, 두 공간을 합쳐서 부모 공간으로 만든다.

버디 시스템은 메모리가 프로세스 크기에 인접하게 나뉠 수 있고, 조각모음과 유사한 merge 동작을 적은 비용으로도 수행할 수 있다.

하지만 고정 분할 방식처럼 하나의 구역에 다른 프로세스가 들어올 수 없으므로 내부 단편화가 발생한다.

분할 메모리 할당 (Non-Contiguous Memory Allocation)

좌측은 세그멘테이션, 우측은 페이징

세그멘테이션

세그멘테이션은 프로세스를 가변 크기의 세그멘트로 나누어 메모리에 할당하는 방법이다. 세그멘트는 개발자 관점에서의 프로그램의 구성 단위인데, 코드 세그멘트, 데이터 세그멘트, 스택 세그멘트, 힙 세그멘트 등으로 구분한다. 이들 세그멘트는 목적과 사용처에 따라 크기가 다르므로, 이들 세그멘트마다 다른 크기의 물리 메모리 공간을 할당한다.

프로세스의 주소 공간은 여러 개의 논리 세그멘트로 나누어 각 물리 세그멘트에 매핑한다. 운영체제에서는 전체 세그멘트 매핑 테이블을 두고, 논리 주소를 물리 주소로 변환한다.

이 방법에서는 메모리를 일관된 단위로 나누지 않고, 프로세스마다 서로 다른 크기의 세그멘트를 메모리에 할당하기 때문에, 시스템의 러닝 타임이 길어질수록 외부 단편화가 심화된다.

페이징

다루는 대상의 단위를 표준화하여 공간을 효율적으로 사용하는 사례는 이후에 다른 분야에서도 자주 찾을 수 있다: (큐브샛), (주식 시장의 매매 단위 표준화)

페이징은 관리할 메모리 단위를 표준화해서 메모리 공간을 쉽게 관리할 수 있게 하는 할당 방법이다. 프로세스의 주소공간을 동일한 크기의 페이지로 분할하고, 물리 메모리도 동일한 크기의 프레임으로 분할한다.

• 페이지(Page): 프로세스의 주소 공간을 나누는 단위
• 프레임(Frame): 물리 메모리의 주소 공간을 나누는 단위

페이지와 프레임의 크기는 동일하다. 이어서 페이지와 프레임을 1:1로 매핑(이것을 페이지 테이블이라고 한다.)하여, 프로세스의 페이지를 물리 메모리의 프레임에 할당한다.

페이징을 사용하면 표준화로부터 발생하는 장점을 얻을 수 있다.

• 높은 이식성
  • 페이지 크기가 표준화되어 있으므로, 프로세스가 다른 시스템으로 이식될 때에도 페이지 단위로 쉽게 매핑할 수 있다.
• 높은 융통성
  • 시스템에 따라 페이지 크기를 다르게 설정할 수 있다. 페이지 크기가 작으면, 프로세스의 메모리 요구량이 작을 때에도 메모리를 효율적으로 사용할 수 있다. 페이지 크기가 크면, 페이지 테이블의 크기를 줄일 수 있다.

또한 구현 상에서도 장점이 있다.

• 용이한 구현
  • 메모리를 고정 크기로 단순 분할하므로 구현이 복잡하지 않다.
• 오버헤드
  • 외부 단편화가 없고, 내부 단편화는 페이지 크기를 초과해 발생하지 않는다.