[OS] 정리6 : 메모리 관리

프로그램이 실행되려면 메모리로 가져와야 한다.

Input queue(job queue) : 프로그램을 실행하기 위해 메모리로 가져오는 것을 기다리는 프로세스 집합 - Long-term 스케줄러의 역할.

유저 프로그램은 실행되기 전에 다음 과정을 거친다. 자세한 내용은 나중에 적어두어야겠다.

- Instruction Fetch : 명령어를 메모리로부터 가져온다. 메모리 -> CPU Cache

- Instruction Decode : 가져온 명령어에서 PC가 가리키는 주소값을 읽고 다음 명령어가 있는 곳으로 PC값(가상 메모리 주소)을 갱신한다.

- Operand Fetch : 명령어에서 사용되는 피연산자를 읽는다.

- Instruction 실행 : 명령어를 실행한다.

- 명령 실행 결과를 메모리에 저장

메모리 접근 속도

- 메인 메모리와 Register는 CPU에서 직접적으로 엑세스할 수 있다.

- Register에 엑세스하는 것은 CPU Clock의 1 cycle 또는 그 이하의 속도다.

- 메인 메모리 엑세스는 그보단 많은 사이클을 요한다. 그렇기 때문에 이전에 언급한 Memory Stall 현상(Memory에서 Bus를 통해 CPU로 오기까지의 대기시간 발생)이 발생한다.

- Cache는 메인 메모리와 CPU Register 사이에 존재한다. 일반적으로 CPU 칩에 있다.

메모리 보호 HW

- 올바른 작동을 보장하기 위한 메모리 보호

- base / limit 레지스터는 논리 주소 공간을 정의한다.

Logical Address : 프로세스마다 독립적으로 가지는 주소 공간(Virtual Address이다). 0번지부터 시작한다. CPU가 인식하는 주소 체계가 이것이다.

Physical Address : 물리적인 메모리 주소로, 실제 하드웨어의 메모리 주소.

Symbolic Address : 프로그래머가 변수 이름을 선언하고 이 변수 이름을 통해 주소에 접근하는 것.

주소 바인딩

- Instruction 및 Data를 메모리 주소에 바인딩하는 것

- Ex) Symbolic 주소를 실제 주소로 바인딩해 주는 것.

 주소 바인딩은 다음 세 단계로 이루어진다.

- Compile Time

- 주소 변환이 컴파일 시에 이루어진다.

- 물리 메모리가 충분히 비었어도 이미 주소가 결정되어 변경할 수 없다.(비효율적)

- 주소 변환을 하려면 다시 컴파일해야 한다.

- 이를 Absolute Code라고 한다.

- Load Time

- 컴파일 시 메모리 위치를 알 수 없는 경우, 일단 Relocatable code(재배치 가능한 코드)로 생성해야 한다.

- Symbol과 실제 주소의 바인딩은 프로그램이 메인 메모리로 적재될 때 이루어진다.

-Execution Time

- 바인딩이 런타임 이후에도 진행된다.

- CPU가 주소를 참조할 때마다 바인딩 상태를 점검해야 한다.

- MMU이라는 하드웨어 지원이 필요하다.

- MMU(Memory Management Unit) : 논리 주소를 물리 주소로 매핑해 주는 하드웨어이며, relocation register와 limit register를 이용하여 매핑을 수행한다.

- 유저 프로그램은 논리 주소를 다루며, 실제 물리 주소를 고려하지 않는다.

- relocation register : 물리 메모리 주소의 최소값

- limit register : 논리 주소의 범위

- CPU가 사용한 값에 relocation register의 값을 주소에 더해줌으로써 실제 물리 메모리 주소값으로 변환한다.

- 범위를 넘어간다면 Trap(Software interrupt)을 통해 오류를 알린다.

- 대부분의 운영체제가 사용하는 방법.

Dynamic relocation

컴파일부터 프로그램 실행까지의 과정

1. Compile : 각각의 소스코드를 컴파일하면 Object(*.o) 파일이 생성된다.

2. Link : Object 파일을 하나의 Object 파일로 묶어주는 것. 이것을 Executable File이라고 한다(ex *.exe파일).

3. Loader

- Executable File을 읽음

- 메인 메모리에 적재

- 프로세스 생성

- OS의 기능

Dynamic Loading VS Dynamic Linking

- Dynamic Loading

- 루틴이 호출되는 시점에 로드하는 방식

- 메모리 공간 사용 효율 증대 : 사용되지 않는 루틴은 로드되지 않는다.

- 사용 빈도가 낮은데 코드량이 많은 루틴이 필요할 때 유용.

- 운영체제가 이런 기능을 지원하지는 않고, 프로그래머에 의해 구현된다. (Program API: dlopen(), dlsym(), dlclose() etc.)

- Dynamic Linking(Ex DLL 파일 사용)

- 실제로 실행될 때까지 Linking이 지연된다(Dynamic loading + Auto linking).

- 컴파일을 통해 생성된 파일과 라이브러리 사이의 Linking을 실제로 수행되기 전까지 지연시킨다.

- 프로그램 실행 중에 라이브러리를 링크할 필요가 있을 때 사용된다.

- Stub이 포함되는데, 메모리에 존재하는 라이브러리 루틴을 찾는 데 사용되는 적은 양의 코드다. Stub은 자신을 루틴의 주소로 변경하고 실행한다.

- OS에서 지원하며, OS는 해당 루틴이 프로세스의 메모리 공간에 있는지 확인해야 한다.

- Shared Library에 유용 : 라이브러리 루틴을 여러 프로그램에 공유된다.

Swapping

- 프로세스는 일시적으로 메모리에서 디스크로 스왑되었다가 실행이 재게될 때 다시 메모리로 가져오게 될 수 있다.

- 반드시 보조메모리가 필요. 보통 디스크가 사용된다.

- CPU는 ready_queue에서 프로세스를 가져와 CPU를 할당하고, CPU 스케줄러는 다음 프로세스를 선택할 때 Dispatcher를 호출하며, Dispatcher는 다음에 실행할 프로세스가 ready_queue에 존재하는지 확인하고 없다면 디스크에서 가져온다.

- Swap 수행시간의 대부분은 메모리 전송 시간이다. 스왑에서 전송되는 메모리의 양에 비례한다.

- Roll out, Roll in

- 우선 순위 스케줄링에서 사용하는 방식

- 낮은 우선순위를 가진 프로세스가 스왑아웃되고, 높은 우선순위를 가진 프로세스가 로드되고 실행될 수 있도록 한다.

Memory Allocation

- Contiguous Allocation

- Multiple Partition Allocation

- 고정 크기 분할

- 가변 크기 분할

- Non-Contiguous Allocation

- Paging

- Segmentation

Contiguous Allocation

- 메인 메모리는 2개의 파티션으로 나뉘어진다.

- OS는 인터럽트 벡터와 함께 낮은 메모리 주소에 올라간다.

- 유저 프로세스들은 높은 메모리 주소에 올라간다.

- relocation register에 들어 있는 시작 주소 및 limit register에 들어 있는 메모리 범위를 이용해 프로세스들이 서로의 영역을 침범하지 못하도록 막는다.

- Multiple-Partition Allocation (고정 크기)

- 메모리를 고정된 크기의 파티션으로 분할한다.

- 각 파티션은 하나의 프로세스를 가진다.

- 파티션의 수에 따라 멀티프로그래밍의 정도가 결정된다.

- IBM OS/360에서 사용되었지만 이제 사용되지 않는다.

- Multiple-Partition Allocation (가변 크기)

- Hole : Hole이라는 개념이 있는데, 사용 가능한 메모리 블럭을 의미한다. 다양한 크기의 Hole이 메모리 전체에 흩어져 있다.

- 프로세스가 도착하면 프로세스가 할당될 수 있는 충분한 크기의 Hole을 찾아 할당한다.

- OS는 Allocated-Partition과 Free-Partition(Hole)에 대한 정보를 유지한다.

Dynamic Storage Allocation Problem

- Hole list로부터 N 바이트 블록 요청을 어떻게 응답해줄 수 있는지를 결정하는 문제. 해결 방안 3가지 존재한다.

1. First-Fit : 요청을 만족시키는 충분히 큰 첫 번째 Hole을 할당해 준다.

2. Best-Fit : 요청을 만족시키는 충분히 큰 공간들 중에서 제일 작은 Hole을 할당해 준다.

3. Worst-Fit : 가장 큰 Hole을 할당해 준다.

당연히, 1, 2번은 3번보다 속도 및 메모리 사용 효율이 훨씬 낫다.

- 50% rule : N개의 메모리 블록이 존재할 때, 0.5N개의 메모리 블록은 Fragmentation으로 인해 손실된다.

Fragmentation(단편화)

- External Fragmentation(외부 단편화)

- 메모리의 전체적인 공간을 계산해 보면 분명히 프로세스가 할당될 크기의 빈 메모리 공간이 존재하지만, 연속적이지 않기 때문에 프로세스를 할당할 수 없는 경우.

- Compaction

- Compaction(비어 있는 Hole들을 하나로 합쳐 하나의 큰 Hole로 만들어주면서 단편화 영역을 한 쪽으로 몰아 옮겨 주는 작업.)을 진행해서 외부 단편화를 줄일 수 있다.

- 시스템은 Compaction 진행 중에 다른 작업을 할 수 없다.

- Compaction을 Garbage Collection이라고도 한다. 

- Compaction은 각 프로세스의 주소들을 동적으로 relocation해야 하기 때문에 실행 부하가 있다.

- Interal Fragmentation(내부 단편화)

- 할당된 메모리 영역이 프로세스 크기보다 약간 큰 경우, 프로세스에서 사용할 수 없지만 할당된 메모리 공간이 존재하게 된다. 이를 내부 단편화라고 한다.

Paging

- 프로세스의 가상 주소 및 물리 주소 공간은 Non-Contiguous일 수 있다.

- Page라는 블록을 사용하여 메모리 할당을 하는 방법.

- 물리 메모리를 고정된 크기의 블록으로 나누는데, 이를 Frame이라고 한다. 크기는 2의 승수이며, 512(2^9) bytes와 8192(2^13) bytes

- 가상 주소 메모리를 같은 크기의 블록으로 나누는데, 이를 Page라고 부른다.

- 크기가 N 페이지인 프로그램을 실행한다면, N Free Frame을 찾고, 프로그램을 로드한다.

- 가상 주소를 물리 주소로 변경하기 위해 Page Table을 사용한다.

- 정해진 크기의 가상 주소와 물리 주소를 사용하며, 페이지 테이블을 사용한다. 이는 연속된 물리 메모리를 다루는 것이 아니기 때문에 때문에 외부 단편화 문제는 해결되지만 내부 단편화 문제는 여전히 존재하게 된다.

- 페이지 테이블은 32비트 기준 4GB에 해당하는 페이지 수를 가진다.

주소 변환

- 가상 주소(CPU가 인식하는 주소)는 다음으로 나눠진다.

- Page 번호 (p)

- 페이지 테이블에서 페이지의 index로 사용됨. 

- 각 페이지 별로 프레임(물리 메모리)의 시작 주소를 가지고 있다.

- Page Offset (d) : 시작 주소와 이 값을 합치면 물리 메모리 주소가 된다.

페이지 크기가 2^n이고 가상 주소 공간이 2^m일 때, 가상 주소의 내용은 다음과 같다.

1. 가상메모리르 4GB 사용. [2^32] => m = 32

2. 페이지 크기가 4KB. [4KB = 2^12] => n = 12

따라서 p = m - n = 32 - 12 = 20, 상위 20bit는 페이지 번호를, 하위 12bit는 offset을 나타낸다.

- 페이지 수는 4GB / 4KB로, 2^20개이다. 그러니 2^20개의 번호가 존재하게 된다.

- 페이지 내의 변위를 offset에 담는다. 한 페이지가 2^12이므로 0 ~ 2^12-1의 수가 들어갈 것.

다음 그림을 보면 이해가 될 것이다.

가상 메모리 -> 물리 메모리 변환 과정

1. 가상 메모리 주소에서 Page 번호 및 Offset 추출.

2. Page 번호로 Page Table에서 해당 페이지를 찾아 프레임의 주소로 변환.

3. 프레임 주소 + Offset을 해서 실제 해당 물리 주소 조회

페이징

페이지 - 프레임 관계

Page Table 구현

- 페이지 테이블은 크기가 크기 때문에 레지스터에 저장되지 못하고 메인 메모리에 유지되며, 다음 레지스터들로 페이지 테이블을 다루도록 한다.

- PTBR(Page Table Base Register)로 페이지 테이블을 가리킴.

- PTLR(Page Table Length Register)로 페이지 테이블의 크기를 나타냄.

- 이 방식은, 물리 메모리 엑세스를 2번 거쳐야 한다. 

1. 메인 메모리의 PCB에 존재하는 페이지 테이블 자체에 엑세스.

2. 1번을 통해 물리 메모리 주소를 추출하고 해당 물리 메모리 엑세스

이 과정이 느리기 때문에 이것을 해결하기 위해 TLB(Translation Look-Aside Buffers)라고 하는 소형 하드웨어 캐시가 사용된다.

TLB

- CPU와 CPU 캐시 사이, CPU 캐시와 메인 메모리 사이 등에 존재.

- Key / Value 형태의 Entry로 테이블이 구성됨

- Key에는 Page 번호, Value에는 Frame 번호가 저장됨.

- 하드웨어 성능상 페이지 테이블의 일부만 저장해둘 수 있어서, 페이지 교체 알고리즘이 적용된다.

- TLB를 거치면 TLB 1번 메인 메모리에 1번 접근하는 것으로 끝난다.

Memory Protection

- protection bit

- 페이지에 대해 접근 권한 제어

- code 영역 : 수정을 막기 위해 read only 부여

- data / stack 영역 : 수정 가능하도록 read / write 권한 부여

- 페이지 테이블 엔트리에는 각각 Valid-Invalid bit를 붙인다.

- Valid :  페이지가 프로세스의 가상 주소 공간에 있음을 나타낸다.

- Invalid : 페이지가 프로세스의 가상 주소 공간에 없음을 나타낸다.

페이지 테이블의 구조

- Hierarchical Paging

- 가상 주소 공간을 N개의 페이지 테이블로 나눈다.

- Example : 2-Level 페이지 테이블

- 가상 주소(32bit machine / 4KB page size)를 다음과 같이 분류한다.

- 페이지 번호 : 20bits

- 페이지 offset : 12bits

- 페이지 테이블의 크기가 크기 때문에, 테이블을 하나 더 둔다.

- 2^20을 둘로 나눠서 2^10 / 2^10으로, 하나는 outter page table, 하나는 page table이다.

- 이렇게 나눠서, 실제로 해당 페이지가 사용될 때마다 나눠진 구역을 사용하기 때문에 사용되지 않은 부분의 페이지 테이블은 생성되지 않는다.

- Hashed Page Table

- 페이지 테이블을 Chaining 방식의 Hash table로 구현한 것.

- 32bit보다 큰 주소 체계에서 사용됨.

- 페이지 번호가 hash 함수를 거쳐 페이지 테이블에 매핑됨. 

- Chaining 방식이기 때문에, 데이터가 중복되어 들어오면 linked list에 추가된다.

- 페이지 번호는 이 list에서 비교하며 검색한다. 해당 페이지 번호에 해당하는 엔트리를 찾으면 물리 메모리를 추출한다.

Segmentation

- 페이징에서는 같은 크기의 블록으로 나누었지만, 세그멘테이션은 가상 메모리를 서로 다른 크기로 나누는 기법이다.

- 크기가 서로 다르기 때문에, 페이징을 할 때처럼 메모리를 미리 분할해 둘 수 없다.

- 하나의 프로그램은 세그먼트의 집합이다. 세그먼트는 다음과 같은 논리적 요소이다.

- main program

- procedure

- function

- object

- local variables, global variables

- common block

- stack

- arrays

세그먼테이션 구조

- 가상 주소는 <세그먼트 번호, offset> 이렇게 두 개 데이터의 튜플로 구성됨.

- Segment table : 세그먼트의 base address와 limit address를 담고 있다.

- Offset 단위로 관리된다. 시작 주소와 Offset으로 실제 물리 메모리 주소를 추출할 수 있다.

- Segment-Table Base Register (STBR) : 세그먼트 테이블의 메모리 주소를 가리킴

- Segment-Table Length Register (STLR) : 프로그램에서 사용하는 세그먼트들의 수를 나타냄

세그먼트 번호 s는 s < STLR일 때 유효하다.

세그먼테이션 설계

- Relocation

- dynamic

- by segment table

- 공유

- 엔트리에서 같은 세그먼트 주소값을 가지도록 하는 것으로 간단하게 공유가 가능하다.

- Allocation

- First fit / Best fit

- External Fragmentation(외부 단편화)

- Protection

- 세그먼트 테이블의 각 엔트리가 연결된다.

- validation bit = 0이면 유효하지 않은 세그먼트다.

- read / write / execute 권한 부여 가능

하지만 Hole 설명에서처럼 Dynamic-Storage-Allocation 문제가 발생한다.

장점 : 세그멘테이션을 이용하면 프로세스의 Code / Data / Stack 등을 종류별로 분류하여 저장하므로, 공유 및 보호가 간단하다.

단점 : 메모리 크기가 고르지 않으므로 외부 단편화가 발생할 수 있다.

결론적으로 페이징을 쓰면 내부 단편화 발생,

세그먼테이션을 쓰면 외부 단편화가 발생한다.

이를 해결하기 위해 Intel386에서는 Segmentation과 Paging을 결합한 방식의 CPU가 개발되었다.

- 세그먼트 각각이 페이지 테이블을 가지고 있음.

- 세그먼트 테이블의 엔트리의 base가 페이지 테이블을, limit이 페이지 수를 나타냄

이렇게 하면 메모리 사용 효율은 올라가지만 결국 물리 메모리를 3번 참조해야 함

1. 세그먼트 테이블 참조

2. 페이지 테이블 참조

3. 추출된 물리메모리 참조

그래서 속도가 느려진다.