[OS] Chapter 9. 메모리 관리

Table of Contents

운영체제와 정보기술의 원리 강의를 듣고 공부한 노트입니다.

주소 바인딩 #

논리적 주소(Logical address) = Virtual address
- 프로세스마다 독립적으로 가지는 주소 공간이다.
- 각 프로세스마다 0번지부터 시작한다.
- CPU가 보는 주소는 이 논리적 주소이다.
물리적 주소(Physical address)
- 메모리에 실제로 올라가는 위치이다.
- 낮은 주소 영역에는 운영체제가 올라가고, 높은 주소 영역에는 사용자 프로세스들이 올라간다.

주소 바인딩
- CPU가 기계어 명령을 수행하려고 논리적 주소를 통해 메모리를 참조하면, 그 논리적 주소가 물리적 메모리의 어느 위치에 매핑되는지 확인해야 한다.
- 이렇게 논리적 주소를 물리적 주소로 연결시켜주는 것을 주소 바인딩이라고 한다.
주소 바인딩의 시점에 따라 그 종류가 나뉠 수 있겠다.
- Symbolic address → Logical address →(이 시점이 언제인가?) Physical address
- 여기서 Symbolic address는 프로그래머가 사용하는, 숫자가 아닌 심볼로 된 주소를 의미한다. 이것이 컴파일이 되면 숫자로 된 Logical address로 바뀌겠다.

주소 바인딩의 종류 #

컴파일 타임 바인딩(compile time binding)
- 물리적 메모리의 주소가 컴파일 시에 결정된다.
- 컴파일러가 절대 코드(absolute code) 를 생성하는 방식이다.
로드 타임 바인딩(load time bining)
- 물리적 메모리의 주소가 프로그램의 실행이 시작될 때 결정된다.
- 컴파일러가 재배치 가능 코드(relocatable code) 를 생성한 경우 가능하다.
런타임 바인딩(runtime binding = executione time binding)
- 프로그램을 시작한 후에도 물리적 메모리의 주소를 변경할 수 있는 방식이다.
- CPU가 주소를 참조할 때마다 주소 매핑 테이블(address mapping table) 을 이용해서 바인딩을 점검한다.
- 하드웨어적 지원이 필요하다.
  - MMU, 기준 레지스터, 한계 레지스터

런타임 바인딩을 위한 하드웨어적 지원 요소 #

Image Source

메모리 관리 유닛 (Memory Management Unit; MMU)
- 논리적 주소를 물리적 주소로 바인딩 해주는 하드웨어 장치이다.
- CPU가 사용자 프로세스의 논리적 주소를 가지고 참조하려고 할 때, 그 주소값에 기준 레지스터(base register)의 값을 더해서 물리적 주소값을 얻어낸다.
- 그래서 사용자 프로세스는 논리적 주소만 다루고, 실제 물리적 주소를 다루지 못하면 알 필요가 없다.
기준 레지스터 = 재배치 레지스터 (base register = relocation register)
- 해당 프로세스의 물리적 메모리 시작 주소를 가지고 있다.
- 따라서 논리적 주소는 일종의 오프셋(offset) 개념으로 생각할 수 있다.
한계 레지스터 (limit register)
- 논리적 주소값에 기준 레지스터 값을 더한 결과가 해당 프로세스의 주소 공간을 벗어나는 경우를 방지하기 위해서, 해당 프로세스의 논리적 주소의 최댓값(프로세스의 크기)을 가지고 있다.
- 만약 주소 공간을 벗어나는 경우에는 트랩을 발생시켜 해당 프로세스를 강제종료시킨다.

메모리 관리와 관련된 용어 #

동적로딩(Dynamic loading) #

의미
- 프로세스 주소 공간 전체를 메모리에 올리는 것이 아니라 해당 부분이 불릴 때, 그 일부분만을 메모리에 적재하는 방식이다.
목적
- 여러 프로그램이 메모리에 올라가는 다중 프로그래밍 방식에서 더 많은 프로세스를 동시에 올려놓기 위함이다.
- 사용되지도 않는 많은 양의 코드가 메모리에 올라가는 것을 막아서 메모리를 효율적으로 쓸 수 있게 한다.
사용 방법
- 운영체제의 특별한 지원 없이, 프로그램 자체에서 구현이 가능하다.
- 운영체제가 라이브러리를 통해 지원할 수도 있다.

중첩(Overlays) #

의미
- 동적로딩과 같다. 하지만 역사적인 목적이 다르다.
목적
- 단일 프로세스만을 메모리에 올려놓는 환경에서 메모리 용량보다 큰 프로세스를 실행하기 위한 어쩔 수 없는 선택이었다.
사용 방법
- 프로그래머가 수작업으로 구현해서 수작업 중첩(Manual Overlays)이라고도 불렸다.

동적연결(Dynamic linking) #

연결(linking)
- 소스 코드를 컴파일해서 생성된 목적 파일(object file)과, 이미 컴파일 된 라이브러리 파일(library file)들을 묶어서 하나의 실행 파일을 생성하는 과정을 말한다.

동적연결 의미
- 연결을 실행 시간까지 미루는 기법이다. 즉, 프로그램이 실행되고 라이브러리 함수를 호출해서야 라이브러리에 대한 연결이 이루어진다.
- 라이브러리 호출 부분에 라이브러리 위치를 찾기 위한 스텁(stub) 이라는 작은 코드를 둔다. 프로그램이 실행되고 라이브러리 함수를 호출하면, 스텁을 통해 해당 라이브러리가 메모리에 이미 존재하는 지 살펴본다. 라이브러리가 메모리에 있으면 불러오고,없으면, 디스크에서 동적 라이브러리 파일을 찾아 메모리로 적재한다.
목적
- 정적연결(Static linking) 와 비교된다.
  - 정적연결은 라이브러리가 프로그램의 실행 파일에 포함된다. (예: printf 함수의 라이브러리 코드) 따라서 실행 파일이 커진다.
  - 또한 동일한 라이브러리를 각각의 프로세스가 메모리에 올려서 메모리의 낭비가 있다.
- 동적연결의 경우 공통으로 사용하는 라이브러리를 한 번만 적재하므로 메모리 효율성을 높일 수 있다.
사용 방법
- 운영체제의 도움이 필요하다.

스와핑(Swapping) #

의미
- 프로세스의 주소 공간 전체를 메모리에서 디스크에 있는 스왑 영역(swap area)으로 쫒아내는 것이다.
- 스왑 영역은 백킹 스토어(backing store) 라고도 부르며, 디스크 안에 파일 시스템과는 별도로 존재하는 일정 영역을 말한다.
- 이것은 프로세스가 종료되어서가 아니라, 특정 이유로 수행 중인 프로세스의 주소 공간을 일시적으로 메모리에서 디스크로 내려놓는 것을 의미한다.
- 중기 스케줄러에 의해 스왑 아웃될 프로세스가 선정된다.
목적
- 메모리에 존재하는 프로세스의 수를 조절하기 위함이다.
바인딩과 연관해서 생각해보면…
- 컴파일, 로드 타임 바인딩 방식
  - 돌아올 때는 원래 있던 메모리 위치로 스왑 인해야한다.
- 런타임 바인딩 방식
  - 빈 메모리 아무 곳에나 프로세스를 올릴 수 있다.

물리적 메모리의 할당 방식 #

물리적 메모리의 낮은 주소 영역에는 운영 체제가 올라가고, 인터럽트 벡터, 운영체제 커널이 여기 위치한다.
물리적 메모리의 높은 주소 영역에는 여러가지 사용자 프로세스들이 올라간다.
여기서는 사용자 프로세스 영역의 관리 방법에 대해 살펴본다.

연속할당 방식 #

Contiguous allocation
각각의 프로세스를 물리적 메모리의 연속적인 공간에 올리는 방식이다.
물리적 메모리를 다수의 분할로 나누어서 하나의 분할에 하나의 프로세스가 적재되도록 한다.

(1) 고정 분할 방식 #

Fixed partition allocation
물리적 메모리를 주어진 개수만큼 영구적인 분할로 미리 나누어두는 방식이다.
분할의 크기는 모두 동일하게 할 수도 있고, 서로 다르게 할 수도 있다.
하나의 분할에는 하나의 프로그램만을 적재할 수 있다.

단점
- 동시에 메모리에 올릴 수 있는 프로그램 수가 고정되어 있으므로 융통성이 떨어진다.
- 외부 단편화와 내부 단편화가 발생할 수 있다.

외부 단편화(external fragmentation)
- 해당 분할이 비어 있지만 프로그램의 크기가 더 커서 할당할 수 없어 낭비되는 공간이 생긴 것이다.
내부 단편화(internal fragmentation)
- 할당된 분할이 프로그램 크기에 비해 더 커서 낭비되는 공간이 생긴 것이다.

(2) 가변 분할 방식 #

Variable partition allocation
물리적 메모리를 미리 나누어 두지 않고, 프로그램 크기에 따라서 동적으로 분할의 크기, 개수가 변하는 방식이다.

동적 메모리 할당 문제(dynamic storage-allocation problem)
- 주소 공간의 크기가 $n$인 프로세스를 메모리에 올릴 때, 물리적 메모리 내 가용 공간(hole) 중에 어떤 위치에 올릴 것인가?
- 방법1. 최초적합(first-fit)
  - 크기가 $n$이상인 가용 공간 중, 가장 먼저 찾아지는 곳에 프로세스를 할당한다.
- 방법2. 최적적합(best-fit)
  - 크기가 $n$이상인 가용 공간 중, 가장 작은 곳에 프로세스를 할당한다.
  - 많은 수의 작은 가용 공간들이 생성되겠다.
- 방법3. 최악적합(worts-fit)
  - 가용 공간 중에서 크기가 가장 큰 곳에 프로세스를 할당한다.
  - 상대적으로 큰 가용 공간들이 생성되겠다.

단점
- 외부 단편화가 발생할 수 있다.
해결 방법: 컴팩션(compaction)
- 사용 중인 메모리 영역을 한쪽으로 몰고, 가용 공간을 다른 한쪽으로 몰아서, 하나의 큰 가용 공간을 만드는 방법이다.
- 비용이 매우 많이 드는 작업이다.
- 물리적 메모리 위치를 옮겨야 하므로, 런타임 바인딩 방식에서만 사용 가능하다.

불연속할당 방식 #

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

(1) 페이징 기법 #

Paging
각 프로세스의 주소 공간을 동일한 크기의 페이지로 자르고, 물리적 메모리도 프레임(frame)으로 잘라서 적재시키는 방식이다.
논리적 메모리 주소를 가진 페이지를 물리적 메모리의 몇 번째 프레임에 있는지로 변환하기 위한 페이지 테이블(page table) 이 필요하다.
- 따라서 페이지의 개수만큼의 entry(항목; 페이지 테이블의 레코드)가 필요하다.
- 각 프로세스 마다 페이지 테이블이 존재한다.

주소 변환 기법 #

Image Source

논리적인 페이지 번호 p로 페이지 테이블에 접근한다. 거기에서 물리적인 프레임 번호 f를 얻는다.
프레임 내에서의 위치(오프셋 d)는 프레임 내에서의 주소로 그대로 사용된다. f + d로 물리적 메모리에 접근한다.

페이지 테이블의 구현 #

현재 CPU에서 실행 중인 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용한다.
- 페이지 테이블 기준 레지스터(page-table base register; PTBR)
  - 페이지 테이블은 메인 메모리에 상주하는데, PTBR은 이 물리적 메모리에서 페이지 테이블이 존재하는 시작 위치를 가리킨다.
- 페이지 테이블 길이 레지스터(page-table length register; PTLR)
  - 페이지 테이블의 크기를 보관한다.

모든 메모리 접근 연산에는 2번의 메모리 접근이 필요하다.
- 페이지 테이블 접근 1번, 실제 데이터 접근 1번.
따라서 메모리 접근 속도 향상을 위해, TLB(Translation Look-aside Buffer; 고속의 주소 변환용 하드웨어 캐시 메모리) 를 사용하기도 한다.
- 이것은 빈번히 참조되는 페이지에 대한 주소 변환 정보를 가지고 있다. 페이지 테이블을 참조하기 전에 이 캐시를 먼저 살펴보고 없으면 페이지 테이블을 참조한다.
- 페이지 테이블 처럼 모든 주소를 가지고 있는 게 아니라서, 저장되어 있는 순서에 따라 페이지 번호 p를 알 수 없다. 따라서 페이지 번호 p가 함께 프레임 번호 f가 쌍으로 저장되어 있다.
- 각 프로세스마다 주소 변환 정보가 다르기 때문에 페이지 테이블이 따로 존재하고, TLB도 마찬가지이다. 그래서 문맥교환 시에 TLB의 entry는 비워진다.
- TLB의 모든 entry를 다 찾아보는 오버헤드를 줄이기 위해서 일반적으로 병렬탐색(parallel search)이 가능한 연관 레지스터(associative register) 를 사용한다. 병렬탐색이란 TLB 내의 모든 entry를 동시에 탐색할 수 있는 기능을 말한다.

메모리 접근 시간(Effective Access Time; EAT)
- $ EAT = (1 + \epsilon)\alpha + (2 + \epsilon)(1 - \alpha)$
- $ EAT = 2 + \epsilon - \alpha $
- $1$ : 메모리 접근 시간
- $\epsilon$ : 연관 레지스터에 접근하는 시간
- $\alpha$ : 요청된 페이지에 대한 주소 변환 정보가 연관 레지스터에 존재할 확률 (Hit ratio)
- $ (1 + \epsilon)\alpha $ : hit. TLB에 존재하는 경우
- $ (2 + \epsilon)(1 - \alpha) $ : miss. TLB에 존재하지 않는 경우

계층적 페이징 #

Image Source

컴퓨터가 $32bit$ 주소 체계를 사용한다면, $2^{32}byte(4GB)$의 주소 공간을 갖는 프로그램을 지원할 수 있다.
- 페이지 하나의 크기가 $4KB$라고 한다면, $4GB / 4KB = 1M$ 개의 페이지 테이블 entry가 필요하다.
- 페이지 테이블 안에 한 entry의 크기가 $4byte$ 정도인데 그러면 총 $4byte \times 1M = 4MB$라는 공간이 필요하다. 프로세스 마다 $4MB$의 페이지 테이블을 모두 메모리에 집어 넣으면 공간 낭비가 심할 것이다.
- 실제로 프로그램이 사용하는 부분은 메모리의 지극히 일부분이므로, 2단계 페이징(two-level paging) 기법을 사용해서 메모리의 낭비를 줄인다.
2단계 페이징(two-level paging)
- 외부 페이지 테이블(outer page table) 과 내부 페이지 테이블(inner page table) 의 두 단계를 걸쳐 주소를 변환한다.
- 사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블의 entry를 NULL로 설정해서 내부 페이지 테이블을 생성하지 않는 것이다.
외부 페이지 테이블 번호 P1과 내부 페이지 테이블 번호 P2, 프레임 내에서의 오프셋 d로 주소를 변환한다.
- 페이지 하나의 크기가 $4KB(2^{12}byte)$이므로, 그 내부에서 오프셋을 결정하기 위해서 d는 $12bit$이어야 한다.
- 내부 페이지 테이블은 페이지화되어서 페이지 하나의 크기인 $4KB$의 공간을 차지한다. 여기서 각 entry는 $4byte$이므로 entry의 총 수는 $4KB / 4byte = 1K$ 개이다. 이것은 $2^{10}$개 이므로, 내부 페이지 테이블의 P2는 $10bit$가 된다.
- 그리고 전체 주소 크기 $32it$에서 $12bit$, $10bit$를 뺀 $10bit$가 P1의 크기가 된다.

공유 페이지 #

공유 코드(shared code) = 재진입 가능 코드(re-entrant code) = 순수 코드(pure code)
- 여러 프로세스에서 공통으로 사용될 수 있도록 작성된 코드이다.
- 읽기 전용(read-only) 의 특징을 가지고 있다.
공유 페이지(shread page)
- 공유 코드를 담고 있는 페이지이다.
- 여러 프로세스에 의해 공유되므로, 물리적 메모리에 하나만 적재되어 사용된다.
  - 예를 들어, 문서 편집기 프로그램을 공유 페이지를 사용해서 작성한 경우, 이 프로세스를 여러 개 수행시키더라도 공유 코드를 담은 페이지는 메모리에 하나만 올라가고 여러 프로세스가 코드를 공유해서 사용하게 된다.
- 이것을 사용하는 모든 프로세스의 논리적 주소 공간에서 동일한 페이지 번호를 갖고 있어야만 한다. 물리적 주소가 같은 것은 당연하다.

사유 페이지(private page)
- 공유 페이지와 반대로, 프로세스들이 독자적으로 사용하는 페이지이다.
- 사유 페이지는 해당 프로세스의 논리적 주소 공간 중 어떠한 위치에 있어도 무방하다.

메모리 보호 #

페이지 테이블의 각 entry에는 주소 변환 정보뿐만 아니라 메모리 보호를 위한 비트를 두고 있다.
- 보호비트(protection bit)
  - 각 페이지에 대한 접근 권한을 담고 있다.
  - 한 프로세스의 주소 공간은 다른 프로세스에 의해 접근될 수 없으므로 ‘누구’에 해당하는 접근 권한을 설정할 필요는 없다. 각 페이지에 ‘어떠한’ 접근을 허용하는지의 정보가 저장된다.
- 유효-무효 비트(valid-invalid bit)
  - valid는 해당 주소의 메모리에 그 페이지가 존재함을 뜻한다. 유효한 내용이 있으므로 접근을 허용한다.
  - invalid는 해당 주소의 메모리에 유효한 내용이 없음을 뜻한다. 유효한 내용이 없으므로 접근을 불허한다.
    - 프로세스가 그 주소 부분을 사용하지 않고 있거나, 해당 페이지가 메모리에 올라와 있지 않고 백킹스토어에 존재하는 경우이다.

역페이지 테이블 #

페이지 테이블에는 공간의 낭비가 발생한다.
- 모든 프로세스 별로 그 논리적 주소에 대응하는 모든 페이지에 대해 페이지 테이블 entry가 존재하기 때문이다.
- entry는 그 페이지가 물리적 메모리에 있든 없든간에 존재한다.
- 그래서 대안으로 역페이지 테이블이 등장했다.

역페이지 테이블(Inverted page table)
- 논리적 주소에 대해 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것이다.
- 그래서 물리적 주소의 페이지 프레임 하나당 페이지 테이블의 entry 하나를 둔다. 즉, 시스템 전체(system-wide)에 페이지 테이블을 하나만 두는 방법이다.
- entry에는 프로세스의 id와 논리적 페이지 번호(p)가 들어있다.
- 단점
  - 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 탐색해야 한다.
- 조치
  - 연관 레지스터를 사용해서 페이지 테이블 전체 entry를 병렬탐색 할 수 있게 한다.

(2) 세그먼테이션 #

Segmentation
프로그램의 주소 공간을 코드, 데이터, 스택 등 의미 있는 단위인 세그먼트로 나누어서 세그먼트 단위로 적재하는 방식이다.
- 논리적 단위(logical unit)로 나누었기 때문에 그 크기가 균일하지 않다.
- 세그먼트를 함수 단위로 정의할 수도 있다. (main(), function, global variables, stack, symbol table, arrays)

주소 변환 기법 #

Image Source

논리적인 세그먼트 번호 s는 해당 논리적 주소가 프로세스 주소 공간 내에서 몇 번째 세그먼트인지를 알려준다. 이것을 사용해서 세그먼트 테이블에 접근한다.
물리적 메모리의 세그먼트 내에서의 위치(오프셋 d)는 그대로 사용된다. base + d 로 물리적 메모리에 접근한다.
세그먼트 테이블의 각 entry는 기준점 base와 한계점 limit를 가지고 있다.
- base는 물리적 메모리에서 그 세그먼트의 시작 위치를 나타낸다.
- limit은 그 세그먼트의 길이를 나타낸다.
  - 페이징에서는 이것이 필요 없었다. 길이가 모두 일정하기 때문이다.

세그먼트 테이블 기준 레지스터(Segment-Table Base Register; STBR)
- 물리적 메모리에서 세그먼트 테이블이 존재하는 시작 위치를 가리킨다.
세그먼트 테이블 길이 레지스터(Segment-Table Length Register; STLR)
- 프로세스의 주소 공간이 총 몇 개의 세그먼트로 구성되는지, 즉 세그먼트의 개수를 나타낸다.

세그먼테이션 기법에서는 논리적 주소를 물리적 주소로 변환하기 전에 두 가지 사항을 먼저 확인한다.
- (1) 요청된 세그먼트 번호 s가 STLR에 저장된 세그먼트 길이 값보다 작은 값인가?
- (2) 오프셋 값 d가 세그먼트의 길이 limit보다 작은 값인가?

공유, 보호, 할당 #

공유, 보호
- 공유 세그먼트(shared segment) 개념을 지원한다.
- 세그먼테이션 기법에서도 페이징 기법과 마찬가지로 entry에 보호비트와 유효-무효 비트를 둔다.
- 페이징에 비해 공유와 보안 측면에서 효과적이다.
  - 페이지는 동일 크기로 무조건 자르기 때문에 한 페이지에 읽기 전용 접근 권한을 주더라도 코드영역과 데이터영역이 같이 들어가 있을 수 있다.
  - 하지만 세그먼트는 의미적인 단위로 나뉘므로, 공유나 보안 처럼 의미적인 단위에 대해 수행하는 업무에서는 훨씬 효과적이다.
할당
- 최초적합(first-fit), 최적적합(best-fit) 방식을 사용해서 세그먼트를 가용 공간에 할당할 수 있다.
- 세그먼트의 크기가 모두 균일하지 않으므로 외부 조각이 발생한다.

(3) 페이지드 세그먼테이션 #

Paged segmentation
페이징 기법과 세그먼테이션 기법의 장점만을 취하는 주소 변환 기법이다.
프로그램의 주소 공간을 의미 단위인 세그먼트로 나누되, 세그먼트를 임의의 길이가 아닌 동일한 크기의 페이지들의 집합으로 구성하는 방식이다.
따라서 하나의 세그먼트는 페이지 크기의 배수가 된다. 그리고 물리적 메모리에 적재하는 단위는 페이지 단위로 한다.
- 외부조각의 문제점을 해결하며, 의미 단위로 프로세스 간의 공유나 접근권한 보호가 이루어지도록 해서 각각의 단점을 보완한다.

주소 변환 기법 #

외부의 세그먼트 테이블과 내부의 페이지 테이블, 이렇게 두 단계의 테이블을 이용한다.
세그먼트 번호 s로 세그먼트 테이블에 접근해서, 세그먼트 길이 segment-length와 페이지 테이블의 시작 주소 page-table base를 얻는다.
오프셋 값 d가 세그먼트 길이값 segment-length보다 작은지 검사한다.
오프셋 값 d를 상위(p), 하위(d') 비트로 나눈다. 상위 비트로 페이지 테이블에 접근(page-table base + p)하고, 하위 비트로 물리적 메모리의 페이지 내 변위(f + d')로 사용한다.