[공룡책 강의 내용 정리] - 9. Main Memory

Jaeyoung Seon·2022년 1월 13일

목록 보기

4/4

메인 메모리
9.1. 배경
9.2. 연속 메모리 할당 (contiguous memory allocation)
9.3. 페이징
9.4. 페이지 테이블의 구조
9.5. 스와핑

Chapter 9. Main Memory

9.1. 배경

프로세스는 실행 중인 프로그램을 말하는데, 여기서 "실행 중"이라는 말은 메인 메모리에 올라갔다는 뜻임.
메모리 (memory)는 거대한 바이트의 배열이며, 각 바이트에는 주소 (address)가 저장됨. CPU는 프로그램 카운터가 지정한 주소에서 명령을 가져와 실행함. 명령어에서 load나 store 같이 메모리에 접근하는 연산을 수행할 수도 있음.

멀티프로그래밍 및 멀티프로세서 환경에서는 각 프로세스가 자신들의 메모리 공간을 사용하고 있다는 점이 중요한데, 이를 위해 베이스 레지스터 (base register), 한계 레지스터 (limit register)가 필요함.
특정 메모리 주소에 접근하고자 할 때 그 주소가 base와 limit 사이에 존재하는 합법적인 주소 접근일 때에만 접근이 가능하고, 잘못된 접근인 경우 세그멘테이션 오류 (segmentation fault)가 발생하여 프로그램이 중단됨.

메모리 공간 보호를 위해 CPU가 base보다 크고, base + limit보다 작은 범위 내의 주소에만 접근할 수 있도록 함. (아닌 경우 인터럽트를 발생시켜 잘못된 접근임을 알림)

주소 바인딩 (address binding)
프로그래밍에서 변수를 선언하면 컴파일러가 변수를 메모리에 올리기 때문에 정확한 주소가 무엇인지 알 수 없는 것처럼, 프로그램은 실행되기 전까지 단지 디스크에 저장되어있는 이진 실행파일에 불과함. 실행을 위해 메인 메모리에 올라가는 순간 비로소 프로세스가 되는 것.
프로세스의 주소는 OS 커널에서 지정하기 때문에 00000000부터 시작하지 않음.

컴파일러는 프로그래머가 symbolic하게 작성한 (int a; 등) 소스코드 내의 주소를 재배치 가능한 (relocatable) 주소에 바인딩함. (컴파일할 때 주소가 결정되기 때문에 주소는 바뀔 수 있음)

링커를 통해 논리적인 주소를 만들고, 로더를 실행할 때 다시금 절대 (absolute) 주소에 바인딩하는 과정이 일어남.

소스코드 단계에서는 symbolic한 코드였던 것이 컴파일러를 거치면서 재배치 가능한 주소로 변환되고, 링커를 거쳐 논리적 주소로 변환되어 로더를 통해 실제 physical한 주소로 변환됨. (각 단계마다 다른 주소 바인딩이 이루어짐)

논리적 주소 공간 vs 물리적 주소 공간

논리 주소 (logical address): 사용자 프로세스에서 사용하기 위해 CPU에서 생성된 주소.
물리 주소 (physical address): 실제 하드웨어 상의 주소. 논리 주소와는 아무런 관계가 없어야 하며, 메모리 주소 레지스터 (memory-address register)에 저장되는 주소.

논리 주소를 물리 주소에 매핑하기 위해서는 논리적 주소 공간 (logical address space)와 물리적 주소 공간 (physical address space)이 분리되어야 함.

메모리 관리 장치 (memory management unit, MMU)

논리 주소를 물리 주소로 매핑하기 위한 하드웨어 장치.

MMU에는 재배치 레지스터 (relocation register)가 존재하여 베이스 레지스터의 역할을 함. CPU가 전달한 논리 주소를 규칙에 맞춰 물리 주소에 매핑함.

동적 로딩 (dynamic loading)
메모리 공간을 효율적으로 사용하기 위해 프로그램, 루틴을 한꺼번에 로딩하지 않고 필요할 때마다 로딩하는 방식. 재배치 가능한 링킹 로더는 필요할 때마다 호출되어 주소 테이블 (address table)을 업데이트할 수 있음.

동적 링킹 (dynamic linking) & 공유 라이브러리 (shared library)

DLL (dynamically linked library): 프로그램 실행 중간에 사용자 프로그램에 링킹되어 사용할 수 있는 시스템 라이브러리. 실행 시 한꺼번에 링킹되지 않고 라이브러리만 로딩된 상태에서 필요할 때 링킹됨.
정적 링킹 (static linking): 시스템 라이브러리가 다른 오브젝트 모듈처럼 한꺼번에 로더에 의해 이진 프로그램 코드로 합쳐짐.
동적 링킹 (dynamic linking): 동적 로딩과 비슷하게 링킹 작업을 실행 시간 (execution time)에 수행하는 것.

이 때문에 DLL을 공유 라이브러리 (shared library)로 부르기도 함.

9.2. 연속 메모리 할당 (contiguous memory allocation)

OS와 사용자 프로세스가 메모리가 사용할 수 있음. 여러 사용자 프로세스가 동시에 메모리에 있을 수 있어야 하기 때문에 사용 가능한 메모리를 어떻게 할당할지 결정해야 함. 연속 메모리 할당은 프로세스를 단일 구역 (single section)에 할당하는 방식으로, 여러 곳에 나눠서 할당되어있지 않고 한 구역에 할당되어있으므로 연속적임.

이때 메모리 보호는 재배치 레지스터 (relocation register)와 한계 레지스터 (limit register)를 통해 이루어짐. (단일 구역 내에 접근할 수 있도록)

프로세스의 크기가 제각각이기 때문에 어떤 프로세스를 어떻게 할당할 것인지가 중요해짐.

이처럼 프로세스의 할당 & 해제를 반복하다보면 빈 공간이 생기는데, 이를 구멍 (hole)이라고 부름. 이 구멍을 잘 관리하는 것이 하나의 이슈가 됨.

저장 공간에 동적으로 메모리를 할당할 때 여러 구멍들 중에 크기 n만큼의 메모리를 어느 구멍에 할당할지에 대한 문제가 발생함.

3가지 해결 방법

최초 적합 (first-fit): 구멍들을 탐색하다가 할당할 수 있는 가장 첫 번째 구멍에 할당하는 것. (크기만 맞으면 일단 할당해~)
최적 적합 (best-fit): 할당할 수 있는 가장 작은 구멍에 할당하는 것. (이를 위해 구멍들의 리스트를 우선순위 큐로 구현할 수 있음)
최악 적합 (worst-fit): 할당할 수 있는 가장 큰 구멍에 할당하는 것.

예시

200MB의 메모리 할당 요청이 들어온다면?
1) 최초 적합 -> 205MB짜리 공간에 할당하게 되고, 5MB가 free frame으로 남음.
2) 최적 적합 -> 작은 공간부터 확인하다가 205MB짜리 공간에 할당함.
3) 최악 적합 -> 큰 공간부터 확인하여 300MB짜리에 할당함. 100MB가 남음.

단편화 문제 (fragmentation)

외부 단편화 (external fragmentation): 메모리 공간이 조각조각 나눠져 있어 메모리 할당 요청을 받을 수 없는 상태 (100MB 할당 가능한데 2MB짜리로 다 나눠져 있어 3MB짜리를 할당할 수 없음)
내부 단편화 (internal fragmentation): 빈 공간에 메모리를 할당하고 난 뒤 공간이 남아 다른 메모리를 할당할 수 없는 상태

페이징을 하면 내부 단편화 문제가, 연속 메모리 할당을 하면 외부 단편화 문제가 발생함.

9.3. 페이징

프로세스의 물리적 주소 공간을 불연속적 (non-contiguous)으로 쪼개서 관리하는 것. 외부 단편화 문제를 해결할 수 있으며, 여러 곳에 나눠져 있는 공간을 압축할 필요도 없음. 메모리 할당과 관련된 부분이기 때문에 OS와 하드웨어의 도움을 받아 구현해야 함.

페이징의 기본적인 방법은 메모리를 동일한 크기로 쪼개는 것임.
물리 메모리를 고정 크기의 블록으로 나눈 것을 프레임 (frame)이라고 하며, 논리 메모리를 같은 크기로 나눈 것을 페이지 (page)라고 함. 논리 메모리에 있는 프로그램을 물리 메모리에 올릴 때 연속 할당처럼 프로그램 하나를 통째로 올릴 필요 없이 조각 조각을 물리 메모리의 위치에 맞게 올리기만 하면 됨.
논리 주소 공간과 물리 주소 공간이 완벽하게 분리되기 때문에 물리 주소를 고려하지 않고 프로그래밍할 수 있음.

주소를 넘겨줄 때 페이지 번호 (p) & 오프셋 (d)만 넘겨주면 됨. "p 페이지에 있는 d번째 메모리에 할당해 줘"
논리 주소의 값은 페이지 번호가 몇 개 있는지, 오프셋이 얼마나 되는지에 따라 결정됨.

프로세스마다 페이지의 개수가 다르기 때문에 페이지 테이블 (page table)을 통해 관리해 주어야 함.

CPU는 논리 주소로부터 페이지 번호 (p)를 얻어 이에 해당하는 프레임 번호 (f)로 변환함. 그 결과 논리 주소가 물리 주소로 매핑되는 것.

페이지 (프레임)의 크기를 적절하게 정하는 것도 중요함. -> 이는 하드웨어에 의해 정의됨.

일반적으로 페이지 크기는 4KB ~ 1GB 사이의 2의 배수로 지정함.

논리 주소 공간의 크기가 $2^m$ 이고 페이지 크기가 $2^n$ 인 경우 페이지의 개수는 $m-n$ , 오프셋 크기는 $n$ 임.

할당되지 않은 프레임들을 연결 리스트로 관리하다가 새로운 프로세스 요청이 들어오면 순서대로 페이지를 메모리 할당해줌. (14 -> 13 -> 18 -> 20)

페이지 테이블의 경우 프로그램의 크기가 다양하고 커지면서 더이상 하드웨어만으로 페이지 테이블을 관리하는 것이 어려워졌음. 이 때문에 PTBR (page-table base register)을 따로 만들어서 페이지 테이블의 시작 주소를 가리키게끔 함. (페이지 테이블은 메인 메모리에 존재함)
문맥교환에 걸리는 시간은 줄어들지만 여전히 메모리 접근 시간은 오래 걸림. (PTBR에 저장된 주소로 메인 메모리에 접근하고, 페이지 테이블 내부에 있는 실제 데이터에 접근하여 총 2번 메모리에 접근함)

CPU에서 페이지 테이블에 바로 접근하기보다는 TLB (translation look-aside buffer)를 중간에 거쳐서 접근함. TLB가 캐시 메모리이기 때문에 매우 빠른 속도로 메모리에 접근할 수 있으며, "TLB hit"가 발생한 경우 하드웨어적으로 빠르게 물리 주소로 변환할 수 있고, "TLB miss"가 발생한 경우 페이지 테이블에서 실제 값을 찾아 물리 주소로 변환할 수 있음.

TLB hit: 찾고자 하는 페이지 번호가 TLB에 있는 경우
TLB miss: 페이지 번호가 TLB에 없는 경우
결국 TLB hit가 얼마나 발생했는지에 따른 hit ratio에 따라 유효 메모리 접근 시간 (effective memory-access time. EAT)이 달라짐.
ex) 어떤 시스템의 메모리 접근 시간이 10 ns일 때,

hit ratio가 80% -> EAT = $0.80 \times 10 + 0.20 \times 20$ = 12 ns (TLB miss인 경우 hit의 2배만큼 시간이 걸림)

페이징을 사용할 경우 보호 비트 (protection bit)를 통해 메모리를 보호해야 함. 하드웨어적으로 유효-무효 비트 (valid-invalid bit)를 각 프레임에 추가하여 메모리 접근이 유효한 접근인지 아닌지 확인할 수 있음.
어떤 비트가 유효 (valid)한 비트이면 이에 해당하는 페이지가 프로세스의 논리 주소 공간에 포함되어있다는 뜻이므로 합법 (legal)한 페이지임. 반대로 무효 (invalid)한 비트라면 논리 주소 공간에 없으므로 불법 (illegal)한 페이지임.
불법 주소가 들어오면 유효-무효 비트를 통해 트랩 (인터럽트)를 걸어버림.

0 ~ 5번까지는 valid한 영역이고 나머지 6, 7번은 invalid한 영역임. 이 invalid한 영역에 접근하고자 할 때에는 illegal한 접근으로 판단하여 트랩을 검.

공유 페이지 (shared page)를 사용하면 dll과 같이 공동으로 사용하는 코드를 공유할 수 있음. 이는 멀티프로그래밍 환경에서 중요한 점임.
C언어에는 libc라는 표준 라이브러리가 존재하는데, 모든 프로세스가 이 라이브러리를 각각 복사해서 사용한다면 매우 비효율적임. 따라서 코드가 재진입 가능한 코드 (reentrant code)라면 프로세스끼리 공유하는 것이 좋음.

재진입 가능한 코드: 실행 중에 스스로 수정될 일이 없는 코드

프로세스는 $P_1, P_2, P_3$ 3개가 존재하지만, 이들은 모두 하나의 물리 메모리를 공유함. 따라서 모두 같은 페이지 테이블을 사용함.

9.4. 페이지 테이블의 구조

현대적인 시스템의 경우 논리 주소 공간이 매우 크기 때문에 페이지 테이블 또한 매우 커짐. 따라서 페이지 테이블을 구조화하는 것이 필요함.

계층적 페이징 (hierarchical paging)
페이지 테이블의 페이지 테이블을 만들어 관리하는 것. 페이지 테이블 자체가 너무 커질 때 묶어서 관리하는 방법.

해시 페이지 테이블 (hashed page table)
해싱 자료구조가 O(1)의 시간 복잡도를 갖기 때문에 효율적임. 해싱을 하드웨어적으로 구현한 것이 해시 페이지 테이블.
논리 주소의 p, d 값을 해시 함수를 통해 해시 값을 생성한 뒤, 이 값을 물리 주소의 값으로 사용하여 매핑함.
주소 공간의 크기가 32 bit를 넘어갈 때 자주 사용하는 방법.

역 페이지 테이블 (inverted page table)
프로세스의 주소를 통해 페이지 테이블에 접근하는 방식을 역으로 적용함. pid (process identifier)를 추가하여 해당 pid의 페이지를 역으로 저장함.

9.5. 스와핑

스와핑을 통해 실제 물리 주소 공간의 크기보다 훨씬 큰 프로세스도 문제 없이 실행할 수 있음.
극단적으로 보면 프로세스마다 하나의 페이지만 메모리에 올라가면 되므로 여러 프로세스를 동시에 실행하는 것이 가능해짐. 이는 멀티프로그래밍 차수의 증가로 이어짐. (동시에 돌릴 수 있는 프로세스가 늘어남)
프로세스가 사용하는 명령어와 데이터들은 메모리에 올라와 있어야 사용 가능하기 때문에, 필요한 경우 스왑 (swap in)해서 메모리에 올리고, 다른 작업을 수행해야 하는 경우 잠시 메모리 바깥으로 (out of memory. swap out) 보냄. 이후 다시 필요할 때 메모리에 다시 올릴 수 있음.

표준 스와핑 (standard swapping)
프로세스 전체를 메인 메모리와 보조 기억장치 (backing store) 사이에서 이동시키는 것.
메인 메모리 -> backing store로 이동시키는 것을 swap out, backing store -> 메인 메모리로 이동시키는 것을 swap in이라고 함.

but 프로세스 전체를 이동시키는 것은 부담이 큰 작업임.

페이징을 통한 스와핑

프로세스를 페이지 단위로 스왑하는 것.
이 방식을 사용하면 물리 메모리와 논리 메모리를 분리할 수 있을 뿐더러 아주 작은 단위의 페이지를 스왑할 수 있음.
따라서 최근에는 페이징이라는 말이 페이징을 통한 스와핑을 의미하고, swap in, swap out이라는 말 대신 page in, page out이라는 용어를 사용함. (페이지 단위)

페이징은 Chapter 10에 나오는 가상 메모리와 매우 잘 맞음.

Jaeyoung Seon

재밌는 인생을 살자!

이전 포스트