운영체제(6)-메모리 관리

책 <운영체제와 정보기술의 원리>, 반효경 을 읽고 정리한 내용입니다

운영체제(1) - 개요

운영체제(2) - 컴퓨터 시스템의 동작 원리

운영체제(3) - 인터럽트의 원리

운영체제(4) - 프로세스 관리

운영체제(5) - CPU스케줄링

주소(address)란 서로 다른 위치를 구분하기 위해 사용하는 일련의 숫자이다.

컴퓨터에서는 Byte단위로 메모리 주소를 부여한다. 따라서 32비트 주소 체계를 사용하면 $2^{32}$만큼의 메모리 공간에 서로 다른 주소를 할당할 수 있다.

보통 4KB(=$2^{12}$) 단위로 묶어서 페이지라는 하나의 행정 구역을 만들게 된다. 페이지 하나의 크기가 $2^{12}$바이트이므로 페이지 내에서의 바이트별 위치 구분을 위해서는 12비트가 필요하다(페이지 간 구별을 위해서는 $2^{32} / 2^{12} = 2^{20}$, 20비트가 필요)

주소 바인딩

프로그램이 실행을 위해 메모리에 적재되면 그 프로세스를 위한 독자적인 주소 공간이 생성된다. 이 주소를 논리적 주소 혹은 가상 주소라고 부른다.

논리적 주소는 각 프로세스마다 독립적으로 할당되며 0번지부터 시작된다.

반면, 물리적 주소는 물리적 주소에 실제로 올라가는 위치를 말한다.

프로세스의 논리적 주소를 물리적 주소로 매핑하는 작업을 주소 바인딩이라고 한다.

주소 바인딩의 방식

1. 컴파일 타임 바인딩

   • 물리적 메모리 주소가 프로그램을 컴파일할 때 결정되는 주소 바인딩 방식
   • 프로그램이 적재된 물리 메모리의 위치를 바꾸려면 컴파일을 다시 해야 한다.

2. 로드 타임 바인딩

   • 프로그램의 실행이 시작될 때 물리 메모리 주소가 결정되는 방식
   • Loader에 의해 물리 메모리의 위치가 결정된다.
     • 로더 : 프로그램을 메모리에 적재시키는 프로그램
   • 컴파일러가 재배치 가능 코드를 생성한 경우에 가능

3. 실행 시간 바인딩

   • 프로그램이 시작한 후에도 적재된 물리 메모리 상의 주소가 변경될 수 있는 방식 - CPU가 주소를 참조할 때마다 주소 매핑 테이블을 이용해 바인딩을 점검해야 한다
   • 기준 레지스터, 한계 레지스터와 *[MMU] : Memory Management Unit 라는 하드웨어 지원이 가능해야 한다.

MMU는 논리적 주소를 물리적 주소로 매핑해주는 하드웨어 장치이다.

MMU기법

• 논리적 주소값에 base register의 값을 더해 물리적 주소를 얻어낸다.
• 기준 레지스터는 해당 프로세스의 메모리 시작 주소를 가지고 있다.
• 프로그램의 주소 공간이 물리적 메모리의 한 장소에 연속적으로 적재되는 것으로 가정한다.
• 문맥 교환으로 CPU에서 수행중인 프로세스가 바뀔 때마다 재배치 레지스터의 값을 해당 프로세스에 해당하는 값으로 재설정

한계 레지스터를 사용해 프로세스가 자신의 주소 공간을 넘어서는 메모리 참조하려는지를 확인한다.

메모리 관리 관련 용어

동적 로딩

프로세스가 시작될 때 주소 공간 전체를 메모리에 적재하지 않고 해당 루틴이 불려질 때 그 루틴만을 메모리에 적재하는 방식

메모리를 효율적으로 사용할 수 있도록 한다.

동적 연결

연결(linking) : 소스 코드를 컴파일하여 생성된 목적 파일(object file)과 이미 컴파일된 라이브러리 파일들을 하나로 묶어 하나의 실행 파일을 생성하는 과정

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

정적 연결에서는 작성한 코드와 라이브러리 코드가 합쳐져서 실행 파일이 생성된다.

• 동일한 라이브러리를 각 프로세스가 개별적으로 메모리에 적재해야 함
• 메모리 낭비

동적 연결에서는 실행 파일에 라이브러리 코드가 포함되지 않으며, 프로그램이 실행되면서 라이브러리 함수를 호출할 때가 되어서야 라이브러리에 대한 연결이 이루어진다.

• 라이브러리가 적재되 있을 경우 해당 메모리에서 직접 참조
• 그렇지 않으면 라이브러리 파일을 적재 후 실행
• 라이브러리를 한 번만 적재한다.
• 메모리 효율성이 높아진다.

중첩

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

동적 로딩과 개념적으로 비슷하나, 사용 이유는 다르다.

단일 프로세스만을 메모리에 적재하는 환경에서 메모리 용량보다 큰 프로세스를 실행하기 위한 어쩔 수 없는 선택.

스와핑

메모리에 적재된 프로세스의 주소 공간 전체를 스왑 영역(swap area)에 일시적으로 내려놓는 것.

중기 스케줄러에 의해 스왑 아웃할 프로세스를 선정한다.

스와핑을 통해 다중 프로그래밍의 정도를 조절할 수 있다.

컴파일 타임 바인딩 / 로드 타임 바인딩 방식에서는 스왑 아웃된 프로세스가 다시 스왑 인 될 때 원래 존재하던 메모리 위치로 다시 적재되어야 한다.

반면, 런타임 바인딩 기법에서는 추후 빈 메모리 영역 아무 곳에나 프로세스를 적재할 수 있다.

물리적 메모리의 할당 방식

물리적 메모리는 OS영역과 user process 영역으로 나뉘어 사용된다.

사용자 프로세스 영역의 관리 방법

• 연속 할당 방식
  • 물리적 메모리의 연속적인 공간에 프로세스를 적재하는 방식
  • 고정 분할 방식
    • 물리적 메모리를 고정 크기의 분할로 나누어 두는 방식
  • 가변 분할 방식
    • 프로그램 실행, 종료 순서에 따라 분할을 관리하는 방식
• 불연속 할당 방식
  • 하나의 프로세스를 물리적 메모리의 여러 영역에 분산 적재하는 방식
  • 페이징 기법
    • 프로세스의 주소공간을 동일한 크기의 페이지로 잘라서 메모리에 페이지 단위로 적재시키는 기법
  • 세그멘테이션 기법
    • 주소 공간을 의미 있는 단위로 나누어 세그먼트 단위로 적재하는 기법
  • 페이지드 세그멘테이션 기법
    • 세그먼트 하나를 다수의 페이지로 구성하는 기법

연속 할당 방식

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

고정 분할 방식

물리 메모리를 주어진 개수만큼의 영구적 분할로 나누어 각 분할에 하나의 프로세스를 적재해 실행시킬 수 있게 한다.

하나의 분할에는 하나의 프로그램만을 적재할 수 있다.

• 동시에 메모리에 적재할 수 있는 프로그램의 수가 고정되어 있다
• 수행 가능한 프로그램의 최대 크기가 제한된다.

외부 단편화 / 내부 단편화가 발생할 수 있다.

외부 단편화 : 프로그램의 크기보다 파티션의 크기가 작은 경우 적재하지 못해서 발생하는 메모리 공간

내부 단편화 : 프로그램의 크기보다 파티션의 크기가 큰 경우 파티션에 적재하고 남는 메모리 공간

• 내부 단편화보다 작은 크기의 프로그램이 있어도 적재되지 못한다. 메모리 낭비

가변 분할 방식

메모리에 적재되는 프로그램의 크기에 따라 파티션의 크기와 개수가 동적으로 변하는 방식

내부 단편화는 발생하지 않는다. 외부 단편화는 발생할 수 있다.

동적 메모리 할당 문제

• 물리적 메모리 내의 가용 공간 중 어떤 위치에 적재할 것인가?
• 프로세스의 주소 공간 전체를 담을 수 있는 가용 공간을 찾아야 한다.

해결 방법

1. 최초 적합 방법 first-fit

   프로세스의 크기보다 큰 가용 공간 중 가장 먼저 찾아지는 곳에 할당하는 방법

   • 시간적 측면에서 효율적

2. 최적 적합 방법 best-fit

   프로세스의 크기보다 큰 가용 공간 중 가장 작은 가용 공간을 찾아 할당하는 방법

   • 시간적 오버헤드 발생
   • 다수의 매우 작은 가용 공간이 생성됨
   • 공간적 측면에서 효율적

3. 최악 적합 방법 worst-fit

   가용 공간 중 가장 큰 곳에 프로세스를 할당하는 방법

   • 시간적 오버헤드
   • 큰 가용 공간의 소비

Compaction

• 프로세스에 의한 사용중인 메모리 영역을 한쪽으로 몰고, 가용 공간들을 다른 한쪽으로 모아서 하나의 큰 가용 공간을 만드는 방법
• 외부 단편화의 해결 방법
• 메모리 위치 이동시켜야 하므로 비용이 매우 많이 든다.
• 실행 시간 바인딩 방식에서만 수행 가능
  • 물리적 메모리 위치를 옮겨야 하므로!

불연속 할당 방식

페이징 기법

프로세스의 주소 공간을 동일한 사이즈의 페이지 단위로 나누어 물리적 메모리에 불연속적으로 저장하는 방식

각 프로세스의 주소 공간 전체를 물리적 메모리에 한꺼번에 올릴 필요가 없으며 일부는 backing store에, 일부는 물리적 메모리에 혼재시키는 것이 가능하다.

물리 메모리를 페이지 크기와 동일한 크기의 frame으로 미리 나누어 둔다.

• 빈 프레임이 있으면 어떤 위치든 사용될 수 있다.

동적 메모리 할당 문제가 발생하지 않는다.

• 외부 단편화는 발생하지 않는다.
• 내부 단편화는 발생할 수 있다.
  • 프로그램의 크기는 페이지 크기의 배수가 안 될 수도 있다.

논리적 주소를 물리적 주소로 변환하는 작업이 페이지 단위로 이루어지기 때문에 주소 변환 절차가 복잡하다.

• 모든 프로세스가 각각 페이지 테이블을 가진다
• 페이지 테이블은 프로세스가 가질 수 있는 페이지의 수만큼 주소 변환 엔트리를 갖는다.

주소 변환 기법

페이징 기법에서는 CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(q)로 나누어 주소 변환에 사용한다.

• 페이지 번호는 페이지 테이블의 인덱스
  • 해당 인덱스의 엔트리에는 해당 페이지의 물리 메모리 상의 base address가 저장된다.
• 페이지 오프셋은 하나의 페이지 내에서의 변위
  • base address에 더함으로써 논리적 주소에 대응하는 물리 주소를 얻는다.

*[PTBR] : Page Table Base Register

페이지 테이블의 구현

페이지 테이블은 물리적 메모리에 위치한다.

페이지 테이블 기준 레지스터는 메모리 내에서의 페이지 테이블의 시작 위치를 가리킨다.

페이지 테이블 길이 레지스터는 페이지 테이블의 크기를 보관한다.

페이징 기법에서 메모리에 접근하려면 주소 변환을 위한 테이블 접근과 변환된 주소에서 실제 데이터를 접근하는 두 번의 메모리 접근을 필요로 한다.

접근 오버헤드를 줄이고 메모리 접근 속도를 향상시키기 위해 TLB[^Translation Look-aside Buffer] 캐쉬를 사용하기도 한다.

• 빈번히 참조되는 페이지에 대한 주소 변환 정보만을 가지고 있다.
• 페이지 정보가 TLB에 존재하는 경우 물리 메모리의 프레임 번호를 바로 얻을 수 있다.
  • 존재하지 않으면 페이지 테이블로부터 알아내야 함
• 문맥 교환시 이전 프로세스의 주소 변환 정보를 가지고 있던 TLB는 모두 지워야 한다.

주소 변환 정보가 TLB에 있는지를 확인하기 위해 TLB의 모든 엔트리를 일일이 찾아봐야 하는 오버헤드가 발생한다.

• 병렬 탐색이 가능한 연관 레지스터를 사용한다.

평균적인 메모리 접근 시간[^Effective memory Access Time] (alpha는 TLB hit 확률) \(EAT = (1+\epsilon)\alpha + (2+\epsilon)(1-\alpha) = 2 + \epsilon - \alpha\)

계층적 페이징

수행중인 프로세스의 수가 증가함에 따라 메모리의 상당 부분이 페이지 테이블에 할애되어 사용 가능한 메모리 공간이 줄어들게 된다. 심각한 공간 낭비

공간 낭비를 줄이기 위해 2단계 페이징 기법을 사용한다.

외부 페이지 테이블과 내부 페이지 테이블의 두 단계에 걸친 페이지 테이블을 사용한다.

• 사용되지 않는 주소 공간은 외부 페이지 테이블 항목을 NULL로 설정하고, 대응하는 내부 페이지 테이블을 생성하지 않는다.

접근해야 하는 페이지 테이블 수가 증가하여 시간적 손해가 따른다.

• 32비트 논리 주소 공간에서 페이지 크기가 4KB이면
  • 최하위 12비트는 오프셋 d
  • 내부 페이지 테이블 10비트($2^{12} / 4KB$)
    • 내부 페이지 테이블 자체를 하나의 프레임에 보관하게 된다.
  • 외부 페이지 테이블은 남는 10 비트

다층 페이지 테이블을 사용하면 메모리 공간 소모는 줄어들지만, 메모리 접근 횟수가 많아져서 접근 시간이 크게 늘어난다.

이를 해결하기 위해서 TLB를 사용한다.

• 4단계 페이지 테이블 / 메모리 접근 시간 100ns / TLB 접근 시간 20ns / 주소 변환 정보 TLB 존재 확률 98% 이면 \(EAT = 0.98 *120 + 0.02 * 520 = 128ns\)

역 페이지 테이블

모든 프로세스별로 페이지에 대해 페이지 테이블을 구성해서 공간 낭비가 심했다.

• 역 페이지 테이블은 메모리에 고정 테이블 하나만 둘 수 있다.

역 페이지 테이블은 논리적 주소가 아닌 물리적 주소에 대해 페이지 테이블을 만드는 것

• 프로세스 번호(pid)와 그 프로세스 내의 논리적 페이지 번호(P)를 담고 있다.

일반적으로 연관 레지스터에 보관해서 시간적 효율성을 증가시킨다.

공유 페이지

공유 코드 : 메모리 공간의 효율을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드

• 읽기 전용

공유 페이지는 공유 코드를 담고 있는 페이지다.

• 물리 메모리에 하나만 적재된다.
• 읽기 전용이어야 한다
• 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 가져야 한다.

사유 페이지

• 프로세스들이 독자적으로 사용하는 페이지

메모리 보호

페이지 테이블은 주소 변환 정보뿐 아니라

보호 비트

• 각 페이지에 대한 접근 권한의 내용을 담고 있다.
• 읽기 / 쓰기 / 읽기전용 등

유효-무효 비트

• 해당 페이지의 내용이 유효한지에 대한 정보

세그먼테이션

주소 공간은 일반적으로 Code, Stack, Data로 나뉜다.

프로세스의 주소 공간을 의미 단위로 나누어 물리적 메모리에 적재한다.

크기가 균일하지 않은 세그먼트들을 메모리에 적재하는 부가적인 메모리 관리 오버헤드가 있다.

논리 주소가 세그먼트 번호(s)와 오프셋(d)로 나누어 사용된다

세그먼트 길이가 균일하지 않으므로 세그먼트 테이블의 각 엔트리에는 base와 함께 limit를 가지고 있다.

물리 주소로 변환 전에 두 가지를 확인한다

1. 요청된 세그먼트 번호가 세그먼트의 개수[^STBR]보다 작아야 한다.
2. 논리 주소의 오프셋 값이 그 세그먼트의 길이보다 작아야 한다.

페이징과 마찬가지로 보호 비트와 유효 비트를 둔다.

공유 세그먼트를 지원한다

• 공유 세그먼트는 공유하는 프로세스들의 주소 공간에서 동일한 논리 주소에 위치해야 한다.
• 공유, 보안 측면에서 페이징 기법에 비해 훨씬 효과적이다.

세그먼테이션은 물리 메모리에서 외부 단편화가 발생한다.

페이지드 세그먼테이션

프로그램을 의미 단위의 세그먼트로 나눈 뒤, 물리 메모리에는 페이지 단위로 적재한다.

하나의 세그먼트 크기를 페이지 크기의 배수로 함으로써 외부 단편화 문제를 해결하며, 동시에 세그먼트 단위로 프로세스 간 공유나 접근 권한 보호를 가능하게 한다.

외부의 세그먼트 테이블과 내부의 페이지 테이블의 두 단계의 테이블을 이용한다.

• 2단계 페이지 테이블과 유사