메인 메모리 (Main Memory)

공룡책(10판) Chapter 9 요약

드디어 프로세스 파트를 빠져나왔다.! 어우 길어

배경 _ Background

메모리는 주소가 있는 바이트의 배열로 구성되어있다. CPU는 프로그램 카운터가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져와 실행한다.

- 기본 하드웨어 _ Basic Hardware

메인 메모리 : CPU가 접근할 수 있는 유일한 범용 저장장치

기계 명령어들은 메모리 주소만 인수로 취하고 디스크의 주소를 인수로 취하지 않는다. 따라서 실행되는 모든 명령어와 데이터는 CPU가 접근할 수 있는 메인 메모리와 레지스터에 있어야 한다. CPU코어에 내장된 레지스터들은 일반적으로 CPU clock 1 cycle 내에 접근이 가능하다. 메인 메모리에 접근을 하기 위해서는 많은 CPU clock tick cycle이 소요된다.

• stall : CPU에 필요한 데이터가 없어서 명령어를 수행하지 못하고 지연되는 현상
• Cache : CPU와 메인 메모리 사이에 빠른 속도의 메모리인 캐시를 구축, stall 해결안

하드웨어는 물리 메모리의 상대적 접근 속도의 차이를 고려, 추가로 올바른 동작을 보장해야하며, 이를 위해 사용자 프로그램으로부터 운영체제 영역을 보호, 더불어 사용자 프로그램 사이도 보호한다.

각각의 프로세스가 독립된 메모리 공간을 가지도록 보장

방법으로는 두 가지 레지스터를 이용, 합법적 영역을 설정하여 접근하도록 한다. base ~ base+limit

• base register 기준 레지스터 : 가장 작은 합법적인 물리 메모리 주소의 값을 저장
• limit register 상한 레지스터 : 주어진 영역의 크기를 저장

이를 벗어날 경우 trap을 일으켜 interrupt 발생시키게 된다.

- 주소 할당 _ Address Binding

프로그램은 디스크에 이진 실행 파일 형태로 저장되어 있으며, 실행하려면 프로그램을 메모리로 가져와 프로세스 문맥 내에 배치해야 한다.

사용자 프로그램은 컴파일러-링커-로더 단계를 거쳐 실행된다.

1
2
3
4
5
6
7
8
9
10
11
12
13

(소스 프로그램)
     |                            -+-
  [컴파일러]                   컴파일 시간
     |                            _+_
(오브젝트 파일)
     |
  [링커] (+ 다른 오브젝트 파일)   -+-
     |                             |
(실행 파일)                     적재 시간           
     |                             |
  [로더]                          -+-
     |
(메모리의 프로그램) (+ 동적 링크 라이브러리)  실행 시간(런타임)

1. 원시 프로그램에서 주소는 숫자가 아닌 심볼 형태로 표현되는데,
2. 컴파일러는 이 심볼 주소를 잽재치 가능 주소로 바인딩시키고
3. 다음에 링커와 로더가 재배치 가능 주소를 절대 주소로 바인딩시킨다.

메모리 주소 공간에서 명령어와 데이터의 바인딩은 시점에 따라 구분된다.

• 컴파일 시간 바인딩: 메모리 내에 들어갈 위치를 컴파일 시간 내에 미리 알 수 있다면 절대 주소 코드를 생성한다. 위치가 변경되면 코드는 다시 컴파일되어야 한다.
• 적재 시간 바인딩: 일단 이진 코드를 재배치 가능 코드를 만들고, 바인딩은 프로그램이 메인 메모리로 실제로 적재되는 시간에 이루어진다.
• 실행 시간 바인딩: 실행 중 메모리 내의 한 세그먼틑로부터 다른 세그먼트로 옮겨질 수 있다면 바인딩이 실행 시간동안 허용되었다고 말한다. 특별한 하드웨어의 지원이 필요하다.

- 논리 대 물리 주소 공간 logical vs physical address space

CPU가 생성하는 주소를 논리 주소, 메모리에 올라간 주소를 물리 주소라 한다. 컴파일, 적재 시에 주소를 바인딩하면 둘은 같으나, 실행시간 바인딩 기법에서는 둘이 다르다. 이 경우 논리 주소를 가상 주소라고 한다.

프로그램 실행 중에는 가상 주소를 물리 주소로 바꾸어주어야 하는데 이 변환 작업은 하드웨어 장치인 메모리 관리 장치 (Memory Management Unit, MMU)에 의해 실행된다. 여기서는 기준 레지스터를 재배치 레지스터라 부른다.사용자 프로그램은 실제 물리 주소에 접근하지 않는다. base 위치를 0으로 치환한 형태라 생각하면 될 듯 싶다.

- 동적 적재 _ Dynamic loading

지금까지는 프로세스가 실행되기 위해 프로세스 전체가 미리 메모리에 올라와 있어야 했으나, 메모리의 효율적 이용을 위해서는 동적 적재를 해야 한다.

프로그램 루틴은 호출되기 전까지는 메모리에 올라오지 않고 필요할 때마다 올라올 수 있도록 재배치 가능한 상태로 대기한다. main 프로그램만 우선 메모리에 적재되어 실행됨. 재배치 가능 연결 적재기가 요청된 루틴을 메모리로 가져와 테이블에 기록한다.

- 동적 연결 및 공유 라이브러리 _ Dynamic Linking & Shared Libraries

• DLL (dynamically linked library): 사용자 프로그램이 실행될 때 사용자 프로그램에 연결되는 시스템 라이브러리이다.

• 정적 연결: 라이브러리가 프로그램의 이진 프로그램 이미지에 끼어 들어간다.

• 동적 연결: 로딩이 실행될 때까지 미루어진다.

  • 실행 가능 이미지의 크기를 감소하고 메인 메모리의 낭비를 줄인다.
  • 라이브러리를 여러 프로세스 간에 공유할 수 있어 DLL 인스턴스가 하나만 있어도 된다.

프로그램이 동적 라이브러리에 있는 루틴을 참조하면 DLL을 찾아 필요한 메모리에 적재한다. 다음, 동적 라이브러리의 함수를 참조하는 주소를 DLL이 저장된 메모리의 위치로 조정한다.

새로운 버전으로 교체될 수도 있기에, 이 경우 새로운 라이브러리를 이용하기 위해 새로 링크되어야 하므로 버전 정보가 프로그램, 라이브러리에 포함되어야 한다.

동적 연결 vs 동적 적재: 동적 적재와는 달리 동적 연결은 운영체제의 도움이 필요하다. 메모리의 프로세스들이 각자의 공간은 자기만 엑세스할 수 있도록 보호된다면 운영체제만이 기억 공간에 루틴이 있는지 검사해 줄 수 있다.

연속 메모리 할당 _ Contiguous memory Allocation

메모리는 일반적으로 두개의 부분으로 나누어진다; 운영체제, 사용자 프로세스

일반적으로 여러 사용자 프로세스가 동시에 메모리에 상주하기를 원하며, 연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재된다.

- 메모리 보호 _ Memory Protection

여기서 고려해야할 것이 메모리 보호 문제이다. 프로세스가 자신이 소유하지 않은 메모리를 접근할 수 없게 강제해야 한다.

1. 재배치 레지스터는 가장 작은 물리 주소의 값을 저장하고, 상한 레지스터는 가능한 최대 논리 주소 값을 저장한다.
2. 각각의 논리 주소는 상한 레지스터가 지정한 범위 안에 존재해야 한다. 3.MMU는 동적으로 논리 주소에 재배치 레지스터의 값을 더함으로써 주소를 변환하는 역할을 수행한다.

CPU 스케줄러가 다음 수행 프로세스를 선택할 때, 디스패처는 문맥 교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재한다. CPU에 의해 생성되는 모든 주소는 이 레지스터들의 값을 참조해 확인 작업을 거치므로 운영체제와 사용자 프로그램을 현재 수행 중 사용자 프로그램의 접근으로부터 보호할 수 있다.

…뭔가 포켓몬 글리치가 떠오르는 부분이군

- 메모리 할당 _ Memory Allocation

메모리를 할당하는 가장 간단한 방법 중 하나는 가변 크기 파티션에 할당하는 것. 각 파티션에는 하나의 프로세스만 적재될 수 있다. 프로세스의 할당 해제가 반복되면 다양한 크기의 hole이 발생한다.

• 동적 메모리 할당 문제 : 저장공간에 동적으로 메모리를 할당할 때 여러 hole들 중에 n 바이트 블록을 어떻게 넣을 것이냐에 대한 문제로 다음과 같은 기법이 있다.
  • First-Fit (최초 적합): 검색은 집합의 시작부터, 가장 먼저 사용 가능한 가용 공간을 할당한다.
  • Best-Fit (최적 적합): 사용 가능한 공간 중 가장 작은 것을 택한다. 리스트가 크기 순이 아니라면 전 리스트를 검색한다.
  • Worst-Fit (최악 적합): 사용 가능한 가장 큰 공간에 할당한다. 남는 가용 공간을 다른 프로세스가 활용할 수도 있다.

- 단편화 _ Fragmentation

• 외부 단편화(external fragmentation): 최초 적합, 최적 적합 모두 외부 단편화(external fragmentation)의 문제를 겪는다. 자투리 공간을 최소로 맞추려다 보니 그 조각들이 할당받을 곳이 없는 것.

• 50% 규칙: 최초 적합의 경우 통계적으로 분석하면 N개의 블록 할당 시 0.5N개의 블록이 단편화 때문에 손실될 수 있다고 한다. 즉, 메모리의 1/3이 못쓰게 된다는 것.

• 내부 단편화(internal fragmentation): 메모리를 먼저 작은 공간으로 분할하고 프로세스가 요청하면 이 분할된 크기의 정수배로 해주는 것이 보통인데, 할당된 공간이 요구된 공간보다 약간 더 클 때 남는 부분이 내부 단편화이다.

• 해결 방안

  1. 압축: 메모리 모든 내용을 한군데로 몰고 모든 가용 공간을 다른 한군데로 모아서 큰 블록을 만든다. 재배치가 어셈블 또는 적재 시에 정적으로 행해진다면 압축은 불가하다. 재배치가 실행시간에 동적으로 이루어지는 경우에만 가능하다.
  2. 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법이다. (페이징)

세그맨테이션 (Segmentation): 페이징은 프로세스를 물리적으로 일정한 크기로 나누었다면 세그맨테이션은 논리적으로 나누는 것. code, data, stack 영역으로 나누는 것도 세그맨테이션이라고 한다. 세그먼트 테이블을 가지고 각 테이블에 limit를 가진다.

페이징 _ Paging

지금까지의 메모리 관리는 프로세스의 물리 주소 공간이 연속적이어야 했는데, 그러지 않아도 되는 메모리 관리 기법으로 페이징(Paging)을 알아본다. 페이징은 연속 메모리 할당 (Contiguous Memory Allocation)의 다음 두 가지 문제를 완화시킨다.

• 외부 단편화 (external fragmentaion) 완화
• 관련 압축 (the associated need for compaction)의 필요성 회피

- 기본 방법 _ Basic Method

논리적 메모리와 물리적 메모리의 결합을 끊어서 구현한다, 매핑은 운영체제가 해주는 듯

• 프레임 (frame): 물리적 메모리를 같은 크기 블록으로 나눈 단위
• 페이지 (page): 논리적 메모리를 같은 크기 블록으로 나눈 단위

CPU에서 나오는 모든 주소는 페이지 번호 (p) 와 페이지 오프셋 (d: offset) 두 개의 부분으로 나누어진다.

• p : page number (0부터 시작)
• d : page offset

페이지 번호는 페이지 테이블 (page table)을 액세스할 때 사용된다. 페이지 테이블은 물리 메모리 각 프레임의 시작 주소를 저장하고 있으며 오프셋은 참조되는 프레임 안에서의 위치이다. 프레임의 시작주소에서 오프셋만큼 더하여 물리주소로 변환한다.

1. 페이지 테이블에서 페이지 번호 (p)에 해당하는 페이지를 찾는다.
2. 페이지 테이블에서 해당 프레임 번호 (f)를 찾는다.
3. 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.
4. 프레임번호 f와 오프셋 d로 물리 주소를 구성한다.

페이지 크기도 프레임 크기와 마찬가지로 하드웨어에 의해 설정된다. 페이지 사이즈는 2의 거듭제곱으로 일반적으로 4KB와 1GB 사이이다.

논리 주소 공간의 2^m, 페이지 크기가 2ⁿ일 때

• 논리 주소 상위(high-order) m-n bits는 페이지 번호 (page number)를 지정하고
• 하위(low-order) n bits는 페이지 오프셋 (page offset)이 된다.

n = 2, m = 4 이고 32bits 의 물리 메모리를 사용하는 예로 찾아보면

• n = 2 일 때 2² = 4 → 페이지 하나의 크기가 4 bits
• m = 4 일 때 2⁴ = 16 → 논리적 주소 공간의 크기가 16 bits

그림으로 나타내면 다음과 같이 나타낼 수 있다.

페이징 자체는 일종의 동적 재배치이고 모든 논리 주소는 페이징 파드웨어에 의해 실제 주소로 바인딩된다. 페이징 기법을 사용하면 모든 놀고 있는 프레임이 프로세스에 할당될 수 있기에 외부 단편화가 발생하지 않는다. 그러나 할당은 프레임의 정수배로 이뤄지기에 내부 단편화가 발생한다. 페이지 경계와 일치하지 않는 크기의 메모리를 프로세스가 요구하면 마지막 페이지 프레임은 전부 할당되지 않는다.

ex) n개의 페이지와 추가로 1B를 요구하였을 때, n+1번째 프레임은 내부 단편화

- 하드웨어 지원 _ Hardware Support

페이지 테이블은 프로세스별 자료구조이기에 페이지 테이블에 대한 포인터는 PCB에 다른 레지스터 값과 함께 저장된다. CPU 스케줄러가 실행할 프로세스를 선택하면 사용자 레지스터를 다시 적재하고(context switching) 저장된 사용자 테이블로부터 하드웨어 페이지 테이블값을 다시 적재한다.(reload) 페이지 테이블의 하드웨어 구현은 전용 고속 하드웨어 레지스터 세트로 구현되어 페이지 주소 변환이 효율적이나 각각의 레지스터가 문맥 교환 중에 교체되어야 하므로 문맥 교환 시간을 증가시킨다.

페이지 테이블에 레지스터를 사용하는 것은 페이지 테이블이 작은 경우 적합하나 큰 페이지 테이블을 지원하는 요즘의 컴퓨터에서는 페이지 테이블을 메모리에 저장하고 페이지 테이블 기준 레지스터 PTBR (page-table base register)로 하여금 페이지 테이블을 가리키도록 한다. 그렇게 되면 이 레지스터만 변화시키면 되어서 문맥 교환 시간을 줄일 수 있다.

페이지 테이블 자체는 메인 메모리에서 관리, 문맥 교환이 빠르지만, 메모리 접근 시 상대적으로 느리고 두 번의 메모리 접근 (페이지 테이블 항목, 실제 데이터) 이 필요하다. 그래서 느릴수도..

- Translation Look-Aside Buffer (TLB)

이 문제의 해결을 위해서 중간에 소형 하드웨어 캐시라는 버퍼를 두는데 그것이 TLB이다. TLB는 매우 빠른 연관 메모리(associative memory)로 구성되고 TLB 내의 각 항목은 key와 value 두 부분으로 구성된다.

1. TLB에 페이지를 찾아달라고 요청이 들어오면 내부 키(페이지 번호)와 비교
2. 페이지 번호에 대응하는 프레임 번호를 알려준다.

TLB는 페이지 테이블의 일부분을 저장하며, 찾는 페이지 번호가 TLB에 있을 경우(TLB hit) 검색의 속도가 빠르고 TLB 검색은 명령어 파이프라인의 일부로 동작하여 성능에 손해를 끼치지 않는다. 만약 TLB에 없으면(TLB miss) 페이지 테이블에 대한 메모리 참조가 이루어진다. 접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율을 적중률(hit ratio) 이라 하며, 효율적인지 판단하는 기준이 된다.

실질 메모리 접근 시간(Effective Memory Access Time)을 계산하는 법

80%의 적중률, 메인 메모리 접근하는데 10ns라면 실질 접근 시간 = 0.80 * 10 + 0.20 * 20 = 12ns 가 된다.

적중률이 99%라면 실질 접근 시간 = 0.99 * 10 + 0.01 * 20 = 10.1ns

여기서 20은 메모리 엑세스를 두번 해서 그렇다.

- 보호 _ Protection

Contiguous Memory Allocation에서는 유효한 주소 범위에 있는지 아닌지 base와 limit으로 legal/illegal을 판단하였으나 페이징이 도입되면 valid-invalid bit를 사용한 prodction bits 를 사용해야 한다. 페이지 테이블의 각 엔트리에 하나의 비트가 추가된다. illegal address 의 경우 트랩을 발생시킨다.

- 공유 페이지 _ Shared Pages

페이징을 통해 공통의 코드를 동시에 공유할 수 있다. 예를 들어, C 언어의 libc와 같은 라이브러리는 실행 중 코드가 변경될 일이 없기에printf()와 같은 메서드를 여러 코드에서 공유할 수 있다.

페이지 테이블의 구조 _ Structure of the Page Table

논리적 메모리 공간이 너무 커져서, 아래와 같은 방법을 사용한다.

- 계층적 페이징 _ Hierarchical Paging

페이지 테이블을 다시 페이징되게 하는 2단계 페이징 기법이 있고, 2단계 바깥 테이블 자체를 페이징하는 4단계 페이징 기법이 있다. 단계가 많아지면 각 논리 주소를 사상하기 위해 많은 메모리 접근을 필요로 한다. 바깥 페이지 테이블을 나누는 방식은 32비트까지는 효율성과 유연성을 향상하기 위해 사용되었지만, 일반적인 64비트 구조에서는 메모리 접근 문제로 계층적 페이지 테이블이 부적합하다.

- 해시 페이지 테이블 _ Hashed Page Tables

주소 공간이 32비트보다 커질 때 많이 사용한다. 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있고, 충돌을 일으켜 모두 이곳으로 해시되는 원소들이 매달린다. 각 원소는

• 가상 페이지 번호
• 사상되는 페이지 프레임 번호
• 연결 리스트 상의 다음 원소 포인터

의 필드를 가진다.

1. 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱,
2. 해시 페이지 테이블에서 연결 리스트를 따라가며 첫째 원소와 가상 페이지 번호를 비교한다.
   1. 일치되면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.
   2. 일치되지 않으면 연결 리스트의 다음 원소로 일을 반복한다.

64비트에서는 해시 테이블과 비슷한 클러스터 페이지 테이블을 사용한다. 해시의 경우는 항목이 한 개의 페이지지만 클러스터 페이지 테이블은 여러 (ex. 16개) 페이지를 가리킨다. 메모리 액세스가 비연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우에 유용하다.

- 역 페이지 테이블 _ Inverted Page Table

기존의 페이지 테이블은 가상 주소를 오름차순으로 정렬하여, 원하는 물리 페이지가 있는지 계산하여 메모리에 엑세스하는데, 이러한 테이블은 물리 메모리의 사용을 추적하기 위해 많은 물리 메모리를 소비한다. 역 페이지 테이블은 반대로 물리 메모리 프레임마다 하나의 항목을 할당하는데, 각 항목은 프레임에 올라와 있는 페이지 주소, 페이지를 소유하는 프로세스의 PID를 표시한다. 엔트리는 process-id, page-number의 쌍으로 이루어져 있다.

이 방법은 논리 페이지마다 항목을 가지는 대신 물리 프레임에 대응되는 항목만 테이블에 저장하기에 메모리에 훨씬 작은 공간을 점유한다.

다만 주소변환 시간이 오래 걸릴 수도 있고, 하나의 물리 프레임 당 하나의 가상 페이지를 가리키는 역 페이지 테이블의 특성상 여러 가상 주소를 동일한 물리 주소에 매핑할 수 없으므로 공유 메모리를 사용할 수 없다는 단점이 있다.

스와핑 _ Swapping

실제 물리적 메모리보다 용량이 큰 프로그램을 사용할 때 이용한다. 프로세스가 실행되기 위해서는 프로세스의 명령어와 데이터가 메모리에 적재되어야 한다. 그러나 프로세스 혹은 프로세스의 일부분은 실행 중에 임시로 백업 저장장치(backing store, ex. 디스크)로 내보내 졌다가 실행을 계속하기 위해 다시 메모리로 되돌아올 수 있는데, 이를 스와핑이라고 부른다.

스와핑을 통해 모든 프로세스의 물리 주소 공간 크기의 총합이 시스템에 설치된 실제 물리 메모리 공간보다 크더라도 동시에 실행을 가능케 하여 다중 프로그래밍 정도를 증가시킨다.

- 기본 스와핑 _ Standard Swapping

표준 스와핑은 전체 프로세스를 메인 메모리와 디스크 사이에서 이동시킨다. 백업 저장장치는 프로세스를 수용하기 위해 당연하지만 커야 하고, 메모리 이미지에 직접 액세스 할 수 있어야 한다. 프로세스와 관련된 자료구조는 백업 저장장치에 기록되어야 하며, 다중 스레드 프로세스의 경우 모든 스레드당 데이터 구조도 스왑되어야 한다. 운영체제는 스왑 아웃된 프로세스에 대한 메타데이터를 유지해야 메모리로 다시 스왑인될 때 복원될 수 있다.

- 페이징에서의 스와핑 _ Swapping with Paging

표준 스와핑은 프로세스 전체를 메모리-백업 저장장치간 이동하는데 시간이 많이 걸려 더는 사용되지 않는다. 대부분의 시스템은 전체가 아닌 페이지 단위의 스와핑을 사용한다. 실제로 스와핑이라는 용어는 표준 스와핑을, 페이징에서의 스와핑은 그냥 페이징이라 하는 모양이다.

(위에서 실컷 페이징 따로 설명해놓고 헷갈리게.. 왜? … 그러려니 하자.)

• page-out 연산: 메모리-> 백업 저장장치
• page-in 연산: 그 반대

페이징에서의 스와핑은 가상 메모리와 함께 잘 작동하는데, 이는 10장에서 알아볼 수 있을 듯 하다.