[운영체제] 물리적 메모리 할당 방식

Allocation of Physical Memory

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

• 운영체제 상주 영역 : 인터럽트 벡터와 함께 낮은 주소 영역
• 사용자 프로세스 영역 : 높은 주소 영역

이 때, 사용자 프로세스 영역의 메모리 할당 방식에는 두 가지가 있습니다.

[1] Contiguous allocation (연속 할당)

• 각각의 프로세스가 메모리의 연속적인 공간에 적재
• Fixed partition allocation과 Variable partition allocation 존재

[2] Noncontiguous allocation (불연속 할당)

• 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가는 것
• Paging, Segmentation, Paged Segmentation 등

이 두 가지 방식에 대해 알아보도록 하겠습니다.

01. 연속 할당

각 프로세스를 메모리의 연속적인 공간에 적재하는 방식입니다.

01-1. Fixed partition allocation (고정 분할 방식)

물리적 메모리를 몇 개의 영구적인 파티션으로 나누는 기법입니다.

분할의 크기가 동일하게 나누는 방식과, 서로 다르게 나누는 방식이 있습니다.

• 분할된 메모리 당 하나의 프로그램을 적재시킵니다.
• 동시에 메모리에 load되는 프로그램의 수가 고정되고, 최대로 수행 가능한 프로그램의 크기가 제한이 됩니다.
• Internal fragmentation(내부 단편화)과 External fragmentation(외부 단편화)이 발생합니다

Internal fragmentation
프로그램의 크기보다 파티션의 크기가 큰 경우, 해당 파티션에 프로그램을 적재하고 남는 공간
External fragmentation
프로그램의 크기보다 파티션의 크기가 작은 경우, 해당 파티션이 비어있는데도 프로그램을 적재하지 못하는 경우에 생기는 메모리 공간

01-2. Variable partition allocation (가변 분할 방식)

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

• 고정 분할 방식과 다르게 미리 메모리 영역을 나누지 않습니다.
• 기술적 관리 기법이 필요합니다.
• External fragmentation이 발생합니다.
  → 중간에 프로그램이 종료되어 메모리에서 빠져나가고, 그 공간에 새로운 프로그램이 메모리에 할당될경우 발생할 수 있습니다.

01-2-1. Hole

가용 공간을 의미합니다. (사용되지 않은 메모리 공간)

• 프로세스가 도착하면 수용 가능한 hole 을 할당해야 합니다.
• 운영체제는 이미 사용중인 메모리 공간인 할당 공간과 사용하고 있지 않은 가용 공간에 대한 정보를 유지하고 있습니다.

01-2-2. 동적 메모리 할당 문제

가변 분할 방식에서 주소 공간의 크기가 n인 프로세스를 메모리에 올릴 때,
물리적 메모리 내의 가용 공간 중 어느 위치에 올릴 것인지 결정하는 문제입니다.

[1] First fit (최초 적합)</sapn>

• 크기가 n 이상인 것 중 최초로 찾아지는 hole 에 할당

[2] Best fit (최적 적합)

• 크기가 n 이상인 가장 작은 hole을 찾아 할당합니다.
• hole들의 리스트가 크기 순으로 정렬되지 않은 경우, 모든 hole을 탐색해야 합니다.
• 많은, 작은 hole이 생성될 수 있습니다.

[3] Worst-fit (최악 적합)

• 가장 큰 hole에 할당합니다.
• Best fit과 동일하게 모든 hole을 탐색할 수 있습니다.
• 상대적으로 적고 아주 큰 hole이 생성됩니다.

First-fit, Best-fit이 Worst-fit보다 속도와 메모리 공간 이용률 측면에서 효율적입니다.

01-2-3. Compaction (압축)

External fragmentation 문제를 해결하는 기법 중 하나로

물리적 메모리 중에서 프로세스에 의해 사용 중인 메모리 영역을 한 쪽으로 몰고,
가용 공간들을 다른 한쪽으로 몰아서 하나의 큰 가용 공간을 만드는 기법입니다.

• 비용이 많이 드는 기법입니다.
• 프로세스의 주소가 실행 시간에 동적으로 재배치가 가능한 Runtime binding 방식을 지원하는 경우에만 사용 가능합니다.
• 최소한의 메모리 이동으로 압축하는 방법은 매우 복잡한 문제입니다.

02. 불연속 할당

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가는 방식입니다.

02-1. Paging

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

• 각 프로세스의 주소 공간 전체를 물리적 메모리에 한번에 올릴 필요는 없고,
  일부는 backing storage, 일부는 물리적 메모리에 나눠 올리는 것이 가능합니다.
• 물리적 메모리를 페이지와 같은 동일한 크기의 프레임으로 미리 나눠둡니다.
• 메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로,
  External fragmentation이 발생하지 않고, 동적 메모리 할당 문제도 고려하지 않아도 됩니다.
• Page table을 사용해서 논리적 주소 → 물리적 주소로 변환하는 작업이 필요합니다.
• 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없으므로.
  프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 internal fragmentation이 발생할 수 있습니다.

논리적 메모리는 페이지 단위로 분할
물리적 메모리는 프레임 단위로 분할이 되어 서로 매칭
논리적 → 물리적 주소로 변환하기 위해 페이지 테이블 사용

02-1-1. Address Translation Architecture

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

• 페이지 번호(p)는 각 페이지별 주소 변환 정보를 담고 있는 페이지 테이블 접근 시 인덱스로 사용됩니다.
  해당 인덱스의 항목에는 페이지의 물리적 메모리 상의 시작 위치 (기준 주소)가 저장됩니다.
• 페이지 오프셋(d)은 하나의 페이지 내에서의 변위를 알려줍니다.
  따라서 기준 주소 + 변위를 더함으로써 물리적 주소를 얻을 수 있습니다.
• f + d = 물리적 주소

02-1-2. 페이지 테이블의 구현

페이지 테이블은 페이징 기법에서 주소 변환을 하기 위한 자료 구조로, 메인 메모리에 상주합니다.

페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용합니다.

[1] 페이지 테이블 기준 레지스터(page-table base register)

• 메모리 내에서의 페이지 테이블 시작 위치 저장

[2] 페이지 테이블 길이 레지스터(page-table length register)

• 페이지 테이블의 크기 보관

페이징 기법에서 모든 메모리 접근 연산은 총 2번씩 필요합니다.

1. 주소 변환을 위해 페이지 테이블 접근
2. 변환된 주소에서 실제 데이터 접근

오버헤드를 줄이고 메모리의 접근 속도를 향상하기 위해 TLB(Translation Lock-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시를 사용합니다.

02-1-3. Paging Hardware with TLB

TLB는 대부분 메인 메모리에 있는 Page table의 접근 속도 향상을 위해 사용하는 캐시입니다.

1. TLB는 가격이 비싸기 때문에 빈번히 참조되는 페이지에 대한 주소 변환 정보만 담습니다.
2. 요청된 페이지 번호가 TLB에 존재하면 대응하는 물리적 메모리의 프레임 번호를 얻어오지만
   존재하지 않는 경우에는 메인 메모리의 페이지 테이블에 접근해서 프레임 번호를 알아옵니다.
3. TLB는 페이지 번호와 프레임 번호 쌍을 가지고 있기 때문에, 특정 페이지 번호가 있는지 TLB 전체를 스캔해야 합니다.
   → 이때 풀 스캔 시간이 오래 걸리므로, 병렬적으로 탐색이 가능한 연관 레지스터를 사용합니다.
4. TLB는 context switch시, 이전 프로세스의 주소 변환 정보를 담고있는 내용이 전부 지워집니다.

02-1-4. Effective access time

메모리 접근 시간 1, 연관 레지스터에 접근하는 시간 ε (이때 ε 는 1보다 충분히 작은 값)

요청된 페이지에 대한 주소 변환 정보가 연관 레지스터에 존재할 확률 a 라고 할때

평균적인 메모리 접근 시간은 EAT = (1+ε)a + (2+ε)(1-a) = 2 + ε - a 입니다.

(1+ε)a 항은 요청된 페이지의 주소 변환 정보가 TLB에 존재하는 경우

(2+ε)(1-a) 항은 요청된 페이지에 대한 주소 변환 정보가 TLB에 존재하지 않는 경우

02-2. 계층적 페이징

현대의 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원합니다.

예를 들어, 32비트 주소 체계를 사용하는 컴퓨터에서는 4GB의 주소 공간을 갖는 프로그램을 지원합니다.
페이지 사이즈가 4K라면, 한 프로세스당 페이지 테이블을 위해 1M 크기의 페이지 테이블 메모리 공간이 필요합니다.
그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로, 페이지 테이블 공간의 낭비가 심하게 됩니다.

이러한 문제를 해결하기 위해 계층적 페이징 기법을 사용합니다.

02-2-1. 2단계 페이징 기법

• 주소 변환을 위해 외부 페이지 테이블과 내부 페이지 테이블 두 단계에 걸친 페이지 테이블을 사용합니다.
• 사용하지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정하며, 여기에 대응하는 내부 페이지 테이블을 생성하지 않습니다.
• 페이지 테이블을 위해 사용하는 메모리 공간을 줄이지만 페이지 테이블의 수가 증가하므로 시간적인 손해가 뒤따릅니다.

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

프로세스의 논리적 주소를 두 종류의 페이지 번호 (P1, P2)와 페이지 오프셋(d)로 구분합니다.

P1 : 외부 페이지 테이블의 인덱스 P2 : 내부 페이지 테이블의 인덱스

1. 외부 페이지 테이블로부터 P1만큼 떨어진 위치에서 내부 페이지 테이블의 주소를 얻고
2. 내부 페이지 테이블로부터 P2만큼 떨어진 위치에서 요청된 페이지가 존재하는 프레임의 위치를 얻은 후
3. 해당 프레임으로부터 d만큼 떨어진 곳이 물리적 주소입니다.

💡 예시 32비트 주소 체계를 갖는 시스템에서 페이지 하나의 크기를 4KB라 하고 페이지 테이블 항목의 크기를 4byte라 할때, 32비트의 논리적 주소 중 페이지 번호와 페이지 오프셋을 위해 각각 몇비트씩 할당해야 할까?

• 먼저 페이지의 크기가 4KB이므로 하나의 페이지 내에서의 byte 오프셋을 결정하기 위해 12비트가 필요하다.
  
• 2단계 페이징 기법에서는 내부 페이지 테이블 자체를 하나의 프레임에 보관하게 되므로 내부 페이지 테이블의 크기 역시 4KB가 된다.
  페이지 테이블 항목의 크기가 4byte이므로 내부 페이지 테이블은 4KB/4byte, 즉 1K개의 항목을 가지게 된다.
  1K 항목을 구분하기 위해서는 10비트가 필요하다.
• P1은 (32 - 12- 10)을 취하여 10비트가 할당된다.

02-2-2. 다단계 페이징 기법

주소 공간이 커지면 커질수록 2단계가 아닌 다단계 페이징 기법이 할 수 있습니다.

다단계 페이지 테이블을 사용하면, 페이지 테이블을 위해 사용되는 메모리 공간의 소모를 줄일 수 있지만, 접근 시간이 늘어납니다.

TLB를 통해 접근 시간을 줄일 수 있습니다.

02-3. 역페이지 기법

페이징 기법을 사용할 시, 모든 프로세스의 모든 페이지에 대한 페이지 테이블 항목을 구성해야 합니다.

페이지 테이블로 인한 메모리 공간의 낭비가 심한 문제를 해결하기 위해 역페이지 기법을 사용할 수 있습니다.

• 물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 둔다.
• 논리적 주소에 대해 페이지 테이블을 만드는 것이 아닌, 물리적 주소에 대해 페이지 테이블을 만든다.
• 시스템 전체에 페이지 테이블을 하나만 둔다.
• 페이지 테이블의 각 항목은, 어느 프로세스의 어느 페이지가 이 프레임에 저장되었는지의 정보를 가진다.
  -> 프로세스 번호(pid)와 그 프로세스 내의 논리적 페이지 번호(p)
• 페이지 전체를 탐색해야 한다.
  -> 따라서 연관 레지스터로 병렬 탐색을 수행한다.

02-3-1. 공유 페이지

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

공유 코드

• 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통적으로 될 수 있도록 작성된 코드.
• 읽기 전용 모드
• 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 있어야 한다.

02-4. 페이지 테이블의 메모리 보호

페이지 테이블의 각 항목에는 주소 변환 정보 외에, 메모리 보호를 위한 보호 비트와 유효-무효 비트가 존재합니다.

[1] 보호 비트: 각 페이지에 대해 읽기-쓰기/읽기 전용 등의 접근 권한 설정

[2] 유효-무효 비트 : 해당 페이지의 내용이 유효한지의 대한 내용

• 유효 : 해당 메모리 프레임에 해당 페이지가 존재 → 접근 허용
• 무효 : 해당 페이지가 물리적 메모리에 올라와 있지 않고,backing store 에 존재 → 접근 불가

02-5. segmentation

프로그램은 의미 단위인 여러개의 segmentation으로 구성될 수 있습니다.

• 작게는 프로그램을 구성하는 하나 하나 = segment
• 크게는 프로그램 전체 = segment
• 일반적으로는 code, data, stack 부분이 하나씩의 segment

그렇다면 segmentation 기법은 무엇일까요?

[1] 논리적 주소는 세그먼트 번호(s), 오프셋(d)로 나뉘어 사용됩니다.

• 세그먼트 번호 : 해당 논리적 주소가 프로세스 주소 공간 내에서 몇 번째 세그먼트에 속하는 지
• 오프셋 : 해당 세그먼트 내에서 얼마만큼 떨어져 있는 지

[2] 세그먼테이션 테이블을 사용합니다.

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

[3] 세그먼트 테이블 기준 레지스터(STBR)와 세그먼트 테이블 길이 레지스터(STLR)을 사용합니다.

• 세그먼트 테이블 기준 레지스터 : 현재 CPU에서 실행 중인 프로세스의 세그먼트 테이블이 메모리의 어느 위치에 있는지 시작 주소를 담고 있음
• 세그먼트 테이블 길이 레지스터 : 프로세스의 주소 공간이 총 몇개의 세그먼트로 구성되는지. 즉 세그먼트의 개수

02-5-1. segmentation hardware

논리적 주소를 물리적 주소로 변환하기 전에 두 가지 사항을 확인합니다.

• 요청된 세그먼트 번호(s)가 STLR에 저장된 값보다 작은 값인가?
• 논리적 주소의 오프셋 값(d)이 세그먼트의 길이(limit)보다 작은 값인가?

두 가지 사항 중 한 가지라도 해당되지 않다면, 예외가 발생합니다.

02-5-2. 공유 세그먼트

어떤 프로세스가 특정 세그먼트를 공유해서 사용하는 개념입니다.

• 공유 세그먼트는 이 세그먼트를 공유하는 모든 프로세스의 주소 공간에서 동일한 논리적 주소에 위치해야 합니다.

02-6. 세그먼트 테이블의 메모리 보호

• 각 세그먼트 별로 보호 비트를 가집니다.
• 각 세그먼트 별로 유효 비트를 가집니다.

페이지 테이블의 메모리 보호와 비슷합니다.

02-7. segmentation 장점/단점

[1] 장점

• 세그먼트는 의미 단위로 나누어져 있기 때문에, 공유와 보안의 측면에서 Paging 기법에 비해 훨씬 효과적입니다.

[2] 단점

• 세그먼테이션 기법에서는 프로그램을 의미 단위로 나누기 때문에 길이가 균일하지 않습니다.
• 따라서 물리적 메모리 관리에서 external fragmentation이 발생하게 되며,
  연속 할당 메모리 관리의 Variable partition 방식에서의 동일한 문제점이 발생합니다.

02-8. Segmentation with Paging

간단하게 말해서, 세그먼트 하나가 여러개의 페이지로 구성되는 기법입니다.

• 프로그램을 의미 단위의 세그먼트로 나누되, 세그먼트가 동일한 크기 페이지의 집합으로 구성됩니다.
  -> 즉 위 기법에서는 하나의 세그먼트 크기를 페이지 크기의 배수가 되도록 함으로써,
  세그먼테이션 기법에서 발생하는 external fragmentation의 문제를 해결합니다.
  -> 세그먼트 단위로 프로세스 간의 공유나 프로세스 내의 접근 권한 보호가 이루어지도록 함으로써 페이징 기법의 약점을 해소합니다.
• 주소 변환을 위해 외부의 세그먼트 테이블과 내부의 세그먼트 테이블을 이용합니다.
  -> 하나의 세그먼트가 여러개의 페이지로 구성되므로, 각 세그먼트 마다 페이지 테이블을 가집니다.
  -> 2단계 페이지 테이블과 유사한 구조를 갖습니다.

💡 예시
‘<세그먼트 번호(s), 오프셋(d)>’으로 구성된 논리적 구조를 물리적 구조로 변환하고자 합니다.

• 논리적 구조의 상위 비트인 세그먼트 번호(s)를 통해 세그먼트 테이블의 해당 항목에 접근합니다.
  (세그먼트 항목 : 세그먼트 길이, 페이지 테이블 시작 주소)
• 오프셋 값(d)를 세그먼트 내에서의 페이지 번호(p), 페이지 내에서의 변위(d’)로 사용하도록 쪼갭니다.
• p와 d’를 이용하여 물리적 메모리에 접근합니다.

reference

---

운영체제와 정보 기술의 원리 - 반효경

https://studyandwrite.tistory.com/17

https://dheldh77.tistory.com/entry/운영체제메모리-관리-전략Memory-Management-Strategy