[운영체제] 7. 메모리 관리

반효경 교수님의 "운영체제와 정보기술의 원리" 책을 학습하고 정리한 글입니다.

 

0. 개요

메모리는 주소를 통해 접근하는 저장장치로, 주소(address)란 서로 다른 위치를 구분하기 위해 사용하는 일련의 숫자로 구성된다.

 

컴퓨터는 이진수를 사용하므로 메모리 주소는 이진수로 매기며, 32비트 혹은 64비트 주소 체계를 사용하고 있다. 컴퓨터는 바이트 단위로 메모리 주소를 부여하기 때문에 32비트 주소 체계는 2^32바이트 만큼의 메모리 공간에 서로 다른 주소를 할당할 수 있다. 컴퓨터 상의 주소는 32비트를 그대로 사용하지 않고, 효율적인 운영을 위해 연속된 일련의 영역을 행정구역처럼 묶어서 사용한다. 보통 4KB(=2^12byte) 크기로 묶어서 페이지(page) 단위를 사용한다.

 

1. 주소 바인딩

📌 논리적 주소 (Logical address) / 가상 주소 (Virtual address)

프로그램 실행을 위해 메모리에 적재하는 독자적인 주소 공간

• 논리적 주소는 각 프로세스마다 독립적으로 할당되며, 논리적 주소에 근거해 명령을 실행한다.

📌 물리적 주소 (Physical address)

물리적 메모리에 실제로 올라가는 위치

• 물리적 메모리의 낮은 주소 영역에는 운영체제가 올라가고, 높은 주소 영역에는 사용자 프로세스가 올라간다.

📌 주소 바인딩 (address binding)

프로세스의 논리적 주소를 물리적 주소로 연결시켜주는 작업

 

✍🏻 물리적 메모리 주소가 결정되는 시기에 따른 주소 바인딩 방식 분류

1. 컴파일 타임 바인딩 (Compile time binding)

물리적 메모리 주소가 프로그램을 컴파일할 때 결정하는 주소 바인딩 방식

• 컴파일 하는 시점에 해당 프로그램이 물리적 메모리의 몇 번ㄴ지에 위치하라 것인지를 결정한다.
• 프로그램이 절대주소에 적재된다는 뜻에서 절대코드(absolute code) 생성 바인딩 방식이라고도 한다.
• 물리적 주소를 변경하고 싶다면 컴파일을 다시 하는 수고가 필요하여 비현실적이고, 시분할 환경에서 부적합하다.

 

2. 로드 타임 바인딩 (Load time binding)

프로그램 실행을 시작할 때 물리적 메모리 주소를 결정하는 주소 바인딩 방식

• 로더(loader)의 책임 하에 물리적 메모리 주소를 부여하고 프로그램이 종료될 때까지 위치를 고정한다.
• 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우에 가능한 방식이다.
  • 로더 (loader) : 사용자 프로그램을 메모리에 적재하는 프로그램

 

3. 실행시간 바인딩 (execution time binding / runtime binding)

프로그램 실행을 시작한 후에도 물리적 주소를 변경할 수 있는 주소 바인딩 방식

• 주소 매핑 테이블 (address mapping table)을 이용해 CPU가 주소를 참조할 때마다 물리적 메모리 위치를 확인
• 기준 레지스터, 한계 레지스터, MMU라는 하드웨어 지원이 뒷받침되어야 한다.
• 📌 MMU (Memory Management Unit, 메모리 관리 유닛)
  논리적 주소를 물리적 주소로 매핑해주는 하드웨어 장치

 

✍🏻 MMU 기법

CPU가 특정 프로세스의 참조하는 논리적 주소 값에 기준 레지스터 값을 더해 물리적 주소 값을 찾는 방법

• 이때, 기준 레지스터는 재배치 레지스터(relocation register)라고도 부르며, 프로세스의 물리적 시작 주소를 가지고 있다.
• MMU 기법은 프로그램의 주소 공간이 물리적 메모리의 한 장소에 연속적으로 적재되는 것을 가정한다.
• 따라서, 그 프로그램을 적재한 물리적 시작 주소만 알면 주소 변환을 쉽게 할 수 있다.

• 프로세스의 논리적 주소 값이 같아도, 프로세스마다 서로 다른 내용을 담고 있게 된다.
• CPU가 논리적 주소 100번지를 참조한다고 할 때 수행하는 프로세스에 따라 가리키는 내용은 상이해진다.

 

✍🏻 한계 레지스터 등장 배경

다중 프로그래밍 환경에서 물리적 메모리 안에는 여러 프로세스가 동시에 올라가 있는 경우가 대부분이다. MMU 기법은 논리적 주소 값과 재배치 레지스터 값을 더한 결과가 해당 프로세스의 주소 공간을 벗어나는 경우가 발생할 수 있다. 이에 따라 메모리 보안(memory protection)이 일어나지 않아 다른 프로그램 영역을 침범하거나, 운영체제 메모리 영역을 변경해 시스템에 치명적인 결과를 초래할 수 있다. 이를 방지하기 위해 한계 레지스터(limit register)를 사용하게 되었다.

한계 레지스터는 현재 프로세스의 논리적 주소의 최댓값, 즉 프로세스의 크기를 담고 있다.

CPU가 메모리 참조 요청을 했을 때 한계 레지스터 값보다 큰지 확인하여 메모리 보안을 유지하게 된다.

 

 

2. 메모리 관련 용어

2-1. 동적로딩 (dynamic loading)

프로세스 주소 공간 전체를 메모리에 다 올리지 않고, 필요한 메모리 주소 공간 만을 메모리에 적재하는 방식

• 다중 프로그래밍 환경에서 메모리 사용의 효율성을 높이기 위해 사용하는 기법
• 자주 사용하지 않는 코드를 메모리에 올리는 것을 막아 메모리 이용 효율성을 향상시킴
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현이 가능하며,운영체제 라이브러리를 통해 지원할 수도 있다.

 

2-2. 동적연결

📌 연결 (linking)

목적 파일과 라이브러리 파일들을 묶어 하나의 실행파일을 생성하는 과정

• 목적 파일 (Object file) : 소스 코드를 컴파일하여 생성한 파일
• 라이브러리 파일 (Library file) : 이미 컴파일된 파일

 

📌 동적연결 (Dynamic linking)

목적 파일과 라이브러리 파일 사이의 연결을 프로그램 실행 시점까지 지연시키는 기법

• 정적연결(static linking)은 목적 파일과 라이브러리 파일을 모두 합쳐 실행 파일을 생성한다. 따라서, 실행 파일의 크기가 상대적으로 크며, 각 프로세스가 동일한 라이브러리를 개별적으로 메모리에 적재하여 낭비하는 단점이 있다.
• 동적연결은 라이브러리가 실행 시점에 연결되어, 라이브러리 함수 호출이 발생해야 라이브러리 연결이 이루어진다.
• 동적연결을 위해 실행파일의 라이브러리 호출 부분에 해당 위치를 찾기 위한 작은 스텁(stub) 코드를 둔다. 스텁을 통해 해당 라이브러리가 메모리에 이미 존재하는지 확인하고, 필요시 적재하여 수행한다.
• 다수의 프로그램이 공통으로 사용하는 라이브러리를 메모리에 한 번만 적재하므로, 메모리 사용 효율성을 높인다.
• 동적연결 기법은 운영체제의 지원을 필요로 한다.

 

2-3. 중첩 (overlays)

프로세스의 주소 공간을 분할해 실제 필요한 부분만을 메모리에 적재하는 기법

• 동적로딩과 개념적으로 유사하지만, 사용 목적이 다르다.
• 중첩은 과거 컴퓨터 시스템의 물리적 메모리 크기 제약으로 인해 하나의 프로세스를 메모리에 한 번에 올릴 수 없어, 프로세스의 주소 공간을 분할해 당장 필요한 일부분을 메모리에 올려 실행하고, 해당 부분의 실행이 끝난 후에 나머지 부분을 올려 실행하는 기법이다.
• 즉, 동적로딩은 메모리에 더 많은 프로세스를 동시에 올려놓고 실행하기 위한 용도인 반면, 중첩은 단일 프로세스의 메모리 용량보다 큰 프로세스를 실행하기 위한 용도이다.
• 운영체제의 지원 없이 프로그래머에 의해 직접 구현하며 수작업 중첩(manual overlays)라고도 부른다.

 

2-4. 스와핑 (swapping)

메모리에 올라온 프로세스 주소 공간 전체를 디스크의 스왑 영역(swap area)에 일시적으로 내려놓는 작업

• 스왑 영역은 백킹스토어(backing store)라고도 불리며, 디스크 내 파일 시스템과 별도로 존재하는 일정 영역을 의미한다.
• 스왑 영역은 프로세스가 수행 중인 동안만 디스크에 일시적으로 저장하는 공간이므로, 저장기간이 상대적으로 짧은 저장공간이라고 할 수 있다.
• 스와핑은 프로세스가 종료되어 그 주소 공간을 디스크로 내쫓는 것이 아니라, 특정 이유로 수행 중인 프로세스의 주소 공간을 일시적으로 메모리에서 디스크로 내려놓는 것을 의미한다.
• 스와핑이 일어나는 작업 방향에 따라 스왑 인(Swap in), 스왑 아웃(Swap out)으로 부른다.

 

✍🏻 스와핑 과정

1. 스와퍼(swapper)라고 불리는 중기 스케줄러(medium-term scheduler)에 의해 스왑 아웃시킬 프로세스를 선정한다.
2. 해당 프로세스는 현재 메모리에 올라가 있는 주소 공간의 내용을 통째로 스왑 아웃시킨다.

 

스와핑의 가장 중요한 역할은 메모리에 존재하는 프로세스의 수를 조절하는 것이다.

즉, 스와핑을 통해 다중 프로그래밍의 정도(degree of multiprogramming)를 조절할 수 있다.

 

컴파일 타임 바인딩 방식과 로드 타임 바인딩 방식은 스왑 인을 할 때 원래 존재하던 메모리 위치로 다시 올라가야 한다. 반면, 실행시간 바인딩 기법은 추후 빈 메모리 영역 아무 곳이나 프로세스를 올릴 수 있다.

스와핑에서 보통 디스크 내의 스왑 영역에 프로세스의 주소 공간이 순차적으로 저장되기 때문에 스와핑에 소요되는 시간은 디스크의 탐색시간(seek time)이나 회전지연시간(rotational latency) 보다는 디스크 섹터에서 실제 데이터를 읽고 쓰는 전송시간(transfer time)이 대부분을 차지한다.

 

3. 물리적 메모리의 할당 방식

물리적 메모리는 운영체제 상주 영역과 사용자 프로세스 영역으로 나누어 사용한다.

• 운영체제 상주 영역은 인터럽트 벡터와 함께 물리적 메모리의 낮은 주소 영역을 사용하고, 커널이 이곳에 위치하게 된다.
• 사용자 프로세스 영역은 물리적 메모리의 높은 주소 영역을 사용하며, 여러 프로세스들을 적재하여 실행한다.

 

✍🏻 프로세스를 메모리에 올리는 방식에 따른 사용자 프로세스 영역 관리 방법

📌 연속 할당 (Contiguous allocation)

각각의 프로세스를 물리적 메모리의 연속적인 공간에 올리는 방식

• 물리적 메모리를 다수의 분할로 나누어 하나의 분할에 하나의 프로세스를 적재한다.
• 이때 분할을 관리하는 방식에 따라 고정분할 방식과 가변분할 방식으로 나누어 볼 수 있다.
  • 고정분할(fixed partition allocation) 방식
    물리적 메모리를 고정된 크기의 분할로 미리 나누어두는 방식
  • 가변분할(variable partition allocation) 방식
    분할을 미리 나누어놓지 않은 채 프로그램이 실행되고 종료되는 순서에 따라 분할을 관리하는 방식

📌 불연속 할당 (Noncontiguous allocation)

하나의 프로세스를 물리적 메모리의 여러 영역에 분산해 적재하는 방식

• 페이징 기법 (paging)
  각 프로세스의 주소 공간을 동일한 크기의 페이지로 잘라 메모리에 페이지 단위로 적재하는 방법
• 세그먼테이션 기법 (segmentation)
  프로그램 주소 공간을 코드, 데이터, 스택 등 의미있는 단위인 세그먼트 단위로 적재하는 방법
• 페이지드 세그먼테이션 기법 (paged segmentation)
  세그먼트 하나를 다수의 페이지로 구성하는 방법

 

3-1. 연속 할당 방식

연속할당 방식은 프로세스를 메모리에 올릴 때 주소 공간을 여러 개로 분할하지 않고, 물리적 메모리의 한 곳에 연속적으로 적재하는 방식이다. 이 방식은 물리적 메모리를 고정된 크기의 분할로 미리 나누어 놓는지, 그렇지 않는지에 따라 고정분할 방식과 가변분할 방식으로 나뉜다.

1. 고정분할 방식

물리적 메모리를 주어진 개수만큼의 영구적인 분할(partition)로 미리 나누어 놓고, 각 분할에 하나의 프로세스를 적재하여 실행하는 방식이다.

• 분할의 크기는 모두 동일하게 할 수 있고, 서로 다르게 할 수도 있다.
• 하지만 두 방식 모두 하나의 분할에는 하나의 프로그램만을 적재할 수 있다.
• 따라서, 동시에 메모리에 올릴 수 있는 프로그램의 수가 고정되어 있고, 수행 가능 프로그램의 최대 크기가 제한되어 가변분할 방식에 비해 융통성이 떨어진다.
• 또한, 외부 단편화와 내부 단편화가 발생할 수 있다.

 

📌 외부 단편화 (external fragmentation)

프로그램의 크기보다 분할의 크기가 작은 경우 해당 분할이 비어있어도 프로그램을 적재하지 못해 발생하는 메모리 공간

• 어떠한 프로그램에게도 배정되지 않은 빈 공간임에도 현재 상태에서 사용할 수 없는 작은 분할을 의미한다.
• 만약 이 외부 단편화의 크기보다 작은 크기의 프로그램이 도착하면 그 프로그램을 외부 단편화에 적재시킬 수 있다.

📌 내부 단편화 (internal fragmentation)

프로그램의 크기보다 분할의 크기가 큰 경우 해당 분할에 프로그램을 적재하고 남는 메모리 공간

• 하나의 분할 내부에서 발생하는 사용하지 않는 메모리 조각을 의미한다.
• 특정 프로그램에 이미 배당된 공간으로 볼 수 있어 내부 단편화에 수용할 수 있는 충분히 작은 크기의 프로그램이 있어도 공간을 활용할 수 없어 메모리를 낭비하게 된다.

 

2. 가변분할 방식

메모리에 적재하는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식을 말한다.

• 프로그램의 크기를 고려하여 메모리를 할당하고 기술적으로 관리할 수 있는 기법을 필요로 한다.
• 분할의 크기를 프로그램의 크기보다 일부러 크게 할당하지 않기 때문에 내부 단편화는 발생하지 않는다.
• 하지만 프로그램이 종료될 경우 중간에 빈 공간이 발생하게 되어, 이 공간이 프로그램의 크기보다 작을 경우 외부 단편화가 발생할 가능성이 있다.

 

✍🏻 동적 메모리 할당 문제 (dynamic storage-allocation problem)

프로세스를 메모리에 올릴 때 물리적 메모리 내 가용 공간 중 어떤 위치에 올릴 것인지 결정하는 문제

• 가용 공간이란 사용되지 않는 메모리 공간으로서 메모리 내의 여러 곳에 산발적으로 존재할 수 있다.
• 물리적 메모리 내에서는 다양한 크기의 가용 공간들이 여러 곳에 흩어져 있어, 효율적으로 관리하기 위해 운영체제는 이미 사용 중인 메모리 공간과 사용하고 있지 않은 가용 공간에 대한 정보를 각각 유지하고 있다.

 

🤔 동적 메모리 할당 문제 해결 방법

1. 최초적합 방법 (first-fit)

크기가 n 이상인 가용 공간 중 가장 먼저 찾아지는 곳에 프로세스를 할당하는 방법

• 가용 공간을 차례대로 살펴보며 프로그램의 크기보다 작으면 건너뛰고, 그렇지 않은 가용 공간을 최초 발견하면 프로그램을 할당하여 가용 공간을 모두 탐색하지 않아 시간적인 측면에서 효율적이다.

2. 최적적합 방법 (best-fit)

크기가 n 이상인 가장 작은 가용 공간을 찾아 그곳에 새로운 프로그램을 할당하는 방법

• 가용 공간 리스트가 크기 순으로 정렬되어 있지 않은 경우, 모든 가용 공간을 탐색해야 하므로 시간적 오버헤드가 발생한다.
• 다수의 매우 작은 가용 공간들이 생성될 수 있는 단점이 있지만, 공간적인 측면에서 효율적이다.

3. 최악적합 방법 (worst-fit)

가용 공간 중에서 가장 크기가 큰 곳에 새로운 프로그램을 할당하는 방법

• 최적적합 방법과 동일하게 모든 가용 공간 리스트를 탐색해야 하는 오버헤드가 발생한다.
• 상대적으로 더 큰 프로그램을 담을 수 있는 가용 공간을 빨리 소진한다는 단점이 존재한다.

⇒ 최초적합 방식과 최적적합 방식이 최악적합 방식에 비해 속도와 공간 이용률 측면에서 효과적

 

🤔 외부 단편화 문제를 해결하기 위한 방법

📌 컴팩션 (Compaction)

물리적 메모리 중에 사용 중인 메모리 영역과 가용 공간들을 각각 한 쪽으로 모아 하나의 큰 가용 공간을 만드는 방법

• 현재 수행 중인 프로세스의 메모리 위치를 상당 부분 이동시켜야 하여 비용이 매우 많이 드는 작업
• 이에 따라, 중간에 일부 가용 공간이 발생하더라도 가급적 적은 수의 메모리 이동으로 효율적인 컴팩션을 수행하는 방법이 필요한데 이는 이론적으로도 매우 복잡한 문제다. 또한, 수행 중인 프로세스의 물리적 메모리 위치를 옮겨야 하므로, 프로그램의 실행 도중에 프로세스의 주소가 동적으로 바뀔 수 있는 실행시간 바인딩 방식이 지원되는 환경에서만 수행할 수 있다.

 

3-2. 불연속 할당 기법

하나의 프로세스가 물리적 메모리의 여러 위치에 분산되어 올라갈 수 있는 메모리 할당 기법을 말한다.

• 페이징 기법 : 하나의 프로그램을 분할하는 기준에 따라 동일한 크기로 나누어 메모리에 올리는 기법
• 세그먼테이션 기법 : 크기는 일정하지 않지만 의미 단위로 메모리에 올리는 기법
• 페이지드 세그먼테이션 기법 : 세그먼테이션을 기본으로 하되, 이를 다시 동일 크기 페이지로 나누어 메모리에 올리는 기법

 

4. 페이징 기법 (paging)

프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식을 말한다.

• 각 프로세스의 주소 공간 전체를 물리적 메모리에 한꺼번에 올릴 필요가 없음
• 일부는 백킹스토어(스왑 영역), 일부는 물리적 메모리에 혼재시키는 것이 가능
• 물리적 메모리를 페이지와 동일한 크기의 프레임(frame)으로 미리 나누어두어, 빈 프레임이 있으면 어떤 위치든 사용할 수 있다. 따라서, 앞서 연속할당에서 발생했던 동적 메모리 할당 문제가 발생하지 않는다는 장점을 가지고 있다.

 

✍🏻 페이징 기법의 복잡한 주소 변환 절차

• 하나의 프로세스라 하더라도 페이지 단위로 물리적 메모리에 올리는 위치가 상이하며,
• 논리적 주소를 물리적 주소로 변환하는 작업이 페이지 단위로 이루어져야 한다.
• 따라서, 모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블(page table)을 가지며, 프로세스가 가질 수 있는 페이지의 개수만큼 주소 변환 엔트리를 가지고 있게 된다.

 

🤔 페이징 기법의 장점과 단점

• 프로세스의 주소 공간과 물리적 메모리가 모두 같은 크기의 페이지 단위로 나누어, 빈 공간은 어느 곳이든 활용할 수 있다.
• 따라서 메모리 상의 가용 공간의 크기가 작아서 빈 공간임에도 활용하지 못하는 외부 단편화 문제가 발생하지 않는다.
• 하지만 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없어, 프로세스 주소 공간 마지막 페이지는 내부 단편화가 발생할 가능성이 있다.

 

4-1. 주소 변환 기법

CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)으로 나누어 주소 변환(address translation)에 사용한다.

• 페이지 번호(p) : 각 페이지별 주소 변환 정보를 담고 있는 페이지 테이블 접근 시 인덱스(index)로 사용
• 인덱스 항목(entry) : 그 페이지의 물리적 메모리 상의 기준 주소(base address), 즉 시작 위치가 저장
• 특정 프로세스의 p번째 페이지가 위치한 물리적 메모리의 시작 위치를 알고 싶다면, 해당 프로세스의 페이지 테이블에서 p번째 항목을 찾아보면 된다.
• 페이지 오프셋(d) : 하나의 페이지 내에서의 변위(displacement)를 알려주며, 기준 주소 값에 변위를 더함으로써 요청된 논리적 주소에 대응하는 물리적 주소를 얻을 수 있다.

 

4-2. 페이지 테이블의 구현

페이지 테이블은 페이징 기법에서 주소 변환을 하기 위한 자료구조로, 물리적 메모리에 위치하게 된다. 현재 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 페이지 테이블 기준 레지스터와 페이지 테이블 길이 레지스터를 사용한다.

• 페이지 테이블 기준 레지스터 (page-table base register) : 메모리 내에서의 페이지 테이블의 시작 위치
• 페이지 테이블 길이 레지스터 (page-table length register) : 페이지 테이블의 크기

 

페이징 기법에서 메모리 접근 연산은

(1) 주소 변환을 위해 페이지 테이블에 접근하는 것,

(2) 변환된 주소에서 실제 데이터에 접근하는 것

두 번의 메모리 접근을 필요로 하여 매번 메모리에 두 번 접근해야 하는 오버헤드가 발생하게 된다.

이와 같은 페이지 테이블 접근 오버헤드를 줄이고 메모리 접근 속도를 향상시키기 위해 TLB(Translation Look-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시가 사용되기도 한다.

 

4-3. 계층적 페이징

페이지 테이블에 사용되는 메모리 공간의 낭비를 줄이기 위해 2단계 페이징(two-level paging) 기법을 사용한다.

🤔 주소 공간이 매우 큰 프로그램 페이징으로 인한 메모리 낭비

예를 들어 32비트 주소 체계를 사용하는 컴퓨터는 2^32byte(=4GB)의 주소 공간을 갖는 프로그램을 지원할 수 있다. 이러한 환경에서 페이지 크기가 4KB라면 4GB/4KB, 즉 1M개의 페이지 테이블 항목이 필요하게 된다.

 

각 페이지 테이블 항목이 4byte가 필요하다면 한 프로세스당 페이지 테이블을 위해 1M * 4byte = 4MB 메모리 공간을 낭비하게 된다. 수행 중인 프로세스 수가 증가함에 따라 전체 메모리의 상당 부분이 주소 변환을 위한 페이지 테이블에 할애되어 실제로 사용 가능한 메모리 공간이 낭비되게 된다.

 

✍🏻 2단계 페이징 기법

사용하지 않는 주소 공간에 대해서는 외부 페이지 테이블(outer page table)의 항목을 NULL로 설정하며, 여기에 대응하는 내부 페이지 테이블(inner page table)을 생성하지 않는다.

• 1단계 페이징 기법에 비해 메모리 낭비를 크게 줄여 공간적인 이득을 볼 수 있다.
• 주소 변환을 위해 접근해야 하는 페이지 테이블의 수가 증가하므로 시간적인 손해가 발생한다.
• 메모리 접근 시간 오버헤드를 줄이기 위해서는 TLB를 사용하는 것이 효과적이다.

 

🤔 2단계 페이징 기법의 주소 변환 과정

2단계 페이징 기법은 프로세스의 논리적 주소를 두 종류의 페이지 번호(P1, P2)와 페이지 오프셋(d)으로 구분한다. P1은 외부 페이지 테이블의 인덱스, P2는 내부 페이지 테이블의 인덱스로 논리적 주소를 <P1, P2, d> 형태로 표시할 수 있다.

 

예를 들어, 32비트 주소 체계를 갖는 시스템에서 페이지 하나의 크기를 4KB, 페이지 테이블 항목의 크기를 4byte라고 가정하자.

1. 페이지의 크기가 4KB(=2^12byte)이므로 하나의 페이지 내에서 바이트 오프셋을 결정하기 위해 12비트가 필요하다.
   ⇒ 총 32비트 중에서 최하위 12비트가 오프셋 d로 사용한다.
2. 내부 페이지 테이블 자체를 하나의 프레임에 보관하기 때문에, 4KB의 내부 페이지 테이블은 4byte의 페이지 테이블 항목에 따라 4KB/4byte, 즉 1K(=2^10)개의 항목을 가지게 되고 2^10개의 항목을 구분하기 위해서는 10비트가 필요하다.
   ⇒ 따라서 내부 페이지 테이블의 인덱스로 사용되는 P2에 10비트를 사용한다.
3. 외부 페이지 테이블의 인덱스인 P1은 총 32비트 중 P2와 d에 사용하는 10비트, 12비트를 제외한 10비트를 할당하게 된다.

 

4-4. 역페이지 테이블

페이지 테이블로 인한 메모리 낭비가 심한 이유는 모든 프로세스의 모든 페이지에 대해 페이지 테이블 항목을 다 구성해야 하기 때문이다. 이러한 문제를 해결하기 위한 방법으로 역페이지 테이블 기법이 사용될 수 있다.

 

📌 역페이지 테이블 기법 (inverted page table)

물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 두는 방식

 

논리적 주소에 대해 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것이다. 즉, 각 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체(system-wide)에 페이지 테이블을 하나만 두는 방법이다. 페이지 테이블의 각 항목은 어느 프로세스의 어느 페이지가 이 프레임에 저장되었는지의 정보를 보관하고 있다. 즉 페이지 테이블의 각 항목은 프로세스 번호(pid)와 그 프로세스 내의 논리적 페이지 번호(p)를 담고 있게 된다.

• 역페이지 테이블은 물리적 주소로부터 논리적 주소를 얻기 수월한 구조로 되어 있다.
• 역페이지 테이블에 주소 변환 요청이 들어오면, 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 다 탐색해야 하는 어려움이 있어, 상당한 시간적 비효율을 가져오게 된다.
• 따라서 역페이지 테이블은 일반적으로 메모리에 유지하는 대신 연관 레지스터(associative register)에 보관해 테이블 전체 항목에 대한 병렬탐색(parallel search)을 가능하게 함으로써 시간적 효율성을 꾀하게 된다.

 

4-5. 공유 페이지

📌 공유 코드 (shared code)

메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용할 수 있도록 작성한 코드

• 재진입 가능 코드(re-entrant code) 또는 순수 코드(pure code)라고도 불리며, 읽기전용(read-only) 특성을 가지고 있다.
• 공유 페이지(shared page)는 여러 프로세스에 의해 공유되는 페이지로, 물리적 메모리에 하나만 적재되어 메모리를 좀 더 효율적으로 사용할 수 있게 한다.
• 공유 코드는 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 존재해야 하는 제약점이 있다.
• 즉, 공유 페이지는 그 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 가져야 한다.
• 사유 페이지(private page)는 프로세스들이 공유하지 않고 프로세스별로 독자적으로 사용하는 페이지를 말한다.

 

4-6. 메모리 보호

페이지 테이블의 각 항목에는 메모리 보호를 위한 보호비트와 유효-무효 비트를 두고 있다.

• 보호비트(protection bit)는 각 페이지에 대한 접근 권한의 내용을 담고 있다. 한 프로세스의 주소 공간은 다른 프로세스에 의해 접근될 수 없으므로 '누구'에 해당하는 접근 권한을 설정하지 않고, 각 페이지에 대해 '어떠한' 접근을 허용하는지의 정보가 저장된다.
• 유효-무효 비트(valid-invalid bit)는 해당 페이지의 내용이 유효한지에 대한 내용을 담고 있다. 유효-무효 비트가 '유효'로 세팅되어 있으면 해당 메모리 프레임에 그 페이지가 존재함을 의미하며, 접근이 허용된다. '무효'로 세팅되어 있으면 프로세스가 그 주소 부분을 사용하지 않거나, 해당 페이지가 물리적 메모리에 올라와 있지 않고 백킹스토어에 존재해 해당 메모리 프레임에 유효한 접근 권한이 없다는 의미를 가진다.

 

5. 세그먼테이션 (segmentation)

프로세스의 주소 공간을 의미 단위의 세그먼트(Segment)로 나누어 물리적 메모리에 올리는 기법

• 세그먼트(Segment)는 코드(code), 데이터(data), 스택(stack), 힙(heap) 등의 기능 단위 또는 의미 단위로 나눈 것을 말한다.
• 프로세스의 주소 공간 전체를 크게는 하나의 세그먼트로 볼 수 있고, 일반적으로는 코드, 데이터, 스택, 힙 등의 기능 단위로 정의한다.
• 많게는 프로그램을 구성하는 함수 하나하나를 각각 세그먼트로 정의할 수 있다.
• 중요한 점은 세그먼트가 의미를 가질 수 있는 논리적인 단위(logical unit)로 나눈 것이기 때문에 크기가 균일하지 않다.
• 크기가 균일하지 않은 세그먼트 단위로 나누어 관리하여, 메모리에 적재하는 부가적인 오버헤드가 발생한다.
• 세그먼트 번호는 해당 논리적 주소가 프로세스 주소 공간에서 몇 번째 세그먼트에 속하는지를 나타낸다.
• 오프셋은 그 세그먼트 내에서 얼마만큼 떨어져 있는지에 대한 정보를 나타낸다.

 

✍🏻 주소 변환을 위한 세그먼트 테이블

세그먼트 테이블의 각 항목은 기준점과 한계점을 가지고 있다.

• 기준점(base) : 물리적 메모리에서 그 세그먼트의 시작 위치
• 한계점(limit) : 그 세그먼트의 길이

세그먼트의 길이가 균일하지 않으므로, 세그먼트 위치 정보 뿐 아니라 길이 정보를 함께 보관하고 있는 것이다.

 

📌 세그먼트 테이블 기준 레지스터 (Segment-Table Base Register, STBR)

현재 CPU에서 실행 중인 프로세스의 세그먼트 테이블이 메모리의 어느 위치에 있는지 그 시작 주소를 담고 있다.

📌 세그먼트 테이블 길이 레지스터 (Segment-Table Length Register, STLR)

그 프로세스의 주소 공간이 총 몇 개의 세그먼트로 구성되는지, 즉 세그먼트 개수를 담고 있다.

 

✍🏻 세그멘테이션 기법의 주소 변환 준비 과정

1. 요청된 세그먼트 번호가 STLR에 저장된 값보다 작은 값인지 확인한다.
   • 만약 그렇지 않다면 존재하지 않는 세그먼트에 대한 접근 시도로, 예외 상황을 발생시켜 메모리 접근을 봉쇄해야 한다.
2. 논리적 주소의 오프셋 값이 그 세그먼트의 길이보다 작은 값인지 확인한다.
   • 세그먼트 테이블의 해당 항목에 있는 한계점과, 요청된 논리적 주소의 오프셋 값을 비교해 확인하게 된다.
   • 만약 세그먼트 길이를 넘어서는 오프셋 위치에 대한 접근 시도라면, 역시 예외 상황을 발생시켜 해당 메모리 위치에 대한 접근을 봉쇄하게 된다.

⇒ 위 두 가지 사항을 모두 만족하는 경우에 한해서 유효한 메모리 접근 요청을 판단해 주소 변환 작업이 이루어 진다.

 

✍🏻 세그먼트 테이블의 보호비트와 유효비트

• 보호비트는 각 세그먼트에 대해 읽기/쓰기/실행 권한을 나타낸다.
• 유효비트는 각 세그먼트의 주소 변환 정보가 유효한지, 해당 세그먼트가 현재 물리적 메모리에 적재되어 있는지를 나타낸다.
• 공유 세그먼트는 여러 프로세스가 특정 세그먼트를 공유해 사용하는 개념으로, 이 세그먼트를 공유하는 모든 프로세스의 주소 공간에서 동일한 논리적 주소에 위치해야 한다.

 

🤔 세그멘테이션 기법의 장단점

• 의미 단위로 나누어져 있어, 공유와 보안 측면에서 페이징 기법에 비해 훨씬 효과적이다. 주소 공간의 일부를 공유하거나 접근 권한 제어를 하고자 할 경우, 어떤 의미 단위로 이루어지지 단순히 크기 단위로 수행되지 않기 때문이다.
• 프로그램을 의미 단위로 나누어 세그먼트의 길이가 균일하지 않다. 따라서, 물리적 메모리 관리에서 외부 단편화가 발생하게 되며, 세그먼트를 어느 가용 공간에 할당할 것인지 결정하는 동적 메모리 할당 문제가 발생한다. 세그먼트 가용 공간 할당 방식은 해당 세그먼트 크기보다 크거나 같은 첫 번째 가용 공간에 할당하는 최초적합(first fit) 방식과, 세그먼트의 크기보다 크거나 같은 가용 공간 중 가장 작은 공간에 할당하는 최적적합(base fit) 방식이 있다.

 

6. 페이지드 세그먼테이션

페이징 기법과 세그먼테이션 기법의 장점만을 취하는 주소 변환 기법으로 생각할 수 있다.

• 프로그램을 의미 단위의 세그먼트로 나눈다. 단 세그먼트가 임의의 길이를 가질 수 있는 것이 아니라 반드시 동일한 크기 페이지들의 집합으로 구성되어야 한다.
• 물리적 메모리에 적재하는 단위는 페이지 단위로 한다. 하나의 세그먼트 크기를 페이지 크기의 배수가 되도록 하여 세그먼테이션 기법에서 발생하는 외부 단편화 문제를 해결하며, 세그먼트 단위로 프로세스 간의 공유나 프로세스 내의 접근 권한 보호가 이루어지도록 하여 페이징 기법의 약점을 해소한다.
• 주소 변환을 위해 외부의 세그먼트 테이블과, 내부의 페이지 테이블, 이렇게 두 단계의 테이블을 이용한다. 하나의 세그먼트가 여러 개의 페이지로 구성되므로 각 세그먼트마다 페이지 테이블을 가지게 되어, 2단계 페이지 테이블과 유사한 구조라고 할 수 있다.

 

✍🏻 <세그먼트 번호, 오프셋> 주소 변환 과정

1. 논리적 주소의 상위 비트인 세그먼트 번호를 통해 세그먼트 테이블의 해당 항목에 접근한다. 세그먼트 항목에는 세그먼트 길이와 그 세그먼트의 페이지 테이블 시작 주소가 적혀 있다.
2. 세그먼트 길이를 넘어서는 메모리 접근 시도인지 확인하기 위해 세그먼트 길이 값과, 논리적 주소 중 하위 비트인 오프셋 값을 비교한다. 오프셋이 더 크다면 유효하지 않은 위치에 대한 접근 시도이므로 트랩을 발생시킨다. 그렇지 않으면 오프셋 값을 다시 상위/하위 비트로 나누어 상위 비트는 그 세그먼트 내에서의 페이지 번호로 사용하고, 하위 비트는 페이지 내에서의 변위로 사용한다.
3. 세그먼트 테이블의 항목을 통해 해당 세그먼트를 위한 페이지 테이블의 시작 위치를 얻었으므로, 그 위치에서 페이지 번호만큼 떨어진 페이지 테이블 항목으로부터 물리적 메모리 페이지 프레임 위치를 획득하게 된다. 이 위치에서 오프셋의 하위 비트 값인 페이지 내 변위만큼 떨어진 곳이 원하는 물리적 주소가 되는 것이다.

 

참고자료

• 📚 운영체제와 정보기술의 원리 (반효경, 2020년 5월)