Memory Management

• 메모리 관리의 배경

멀티 프로그래밍 : 다수의 프로세스가 한번에 메모리에 접근함

-> 한 프로세스가 사용가능한 주소를 제약해줘야함 (Protection)

-> 메모리 하드웨어의 업데이트를 빠르게 해야함 (protection과 translation)

• 메모리 관리의 정의

OS와 하드웨어에서 다수의 프로세스가 메인 메모리에 수용되도록 실행하는 작업

• 메모리 관리의 목표

1. 프로세스간의 분리를 제공하기 위해.
2. 최소의 오버헤드로 성능을 최대화하기 위해서 경쟁하는 프로세스간의 부족한 메모리 자원을 할당하기 위해.

• 메모리 관리의 쟁점

1. 다수의 프로세스 지원

- 각각의 프로세스는 논리적으로 연속된 공간을 가져야함.

- 각각의 공간의 크기는 가변적임.

1. 프로세스가 할당된 메모리보다 더 크게 사용할 수 있게 함.

- 모든 메모리 공간이 동시에 사용되어지지 않음.

- 메모리 참조는 공간적이고 일시적인 locality를 보임.

1. 프로세스 마다 다수의 영역 지원 (세그먼트)

1. Protection과 sharing
2. 성능

• 주소 공간

1. 물리적 주소 공간

하드웨어에서 지원됨.

절대적 주소라고도 불림.

0에서 시작해서 MAXsys 까지 할당됨

1. 논리적 주소 공간

한 프로세스의 자신의 메모리에 대한 관점

0에서 시작해서 MAXprog 까지 할당됨

상대적 주소가 논리적 주소 공간의 한 예시며, 이는 프로그램에서 알고있는 지점에 상대적인 공간으로 표현됨.

• 유저 프로그램은 논리적 주소 공간을 다룬다.

물리적 주소를 절대 보여주지 않는다.

cpu에서 수행되는 명령의 경우 논리적 주소 문제가 야기된다.

• 주소 생성

Compilation -> Assembly -> Linking -> Loading

• 하드웨어의 주소 변환

요구사항

충분한 성능을 위해서는 상대적 주소에서 물리적 주소로 변환하는 것은 하드웨어에서 수행되어야함.

프로그램은 실행 시간에 동적으로 재할당된다.

Base(Relocation) Register + Limit Register

• Linking이 뭔데?

코드와 데이터의 다양한 조각들을 하나의 메모리에 로드될 수 있고, 실행될 수 있는 파일로 수집하고 합치는 프로세스.

• Linker의 역할

Symbol resolution

목표 파일의 각각의 전역 심볼은 고유의 정의에 제한된다.

(ex. 외부 참조를 적당한 주소에 할당하는 것)

Relocation

각 심볼의 근본적인 메모리 주소가 결정되고, 이 오브젝트들을 참조하는 곳이 변경된다.

• Linking Time

Compile time : 소스 코드가 오브젝트 코드로 변경될 시점(정적 linker에 의해)

Load time : 프로그램이 메모리에서부터 로드될 시점(동적 linker에 의해)/공유 라이브러리를 링크하기 위해 동적 링커 호출

Run time : 프로그램이 실행될 시점 (동적 linker에 의해)

• Static Linking

객체 모듈은 바이너리 프로그램 이미지에 정적으로 결합됨.

linkage editor에 의해 수행됨.

• Dynamic Linking

실행 시간까지 연기된 linking (로드 모듈이 생성될 때까지 일부 외부 모듈의 연결을 지연함)

부재한 모듈을 호출하게되면, OS는 모듈을 찾아 로드하고 호출하는 모듈에 연결함.

언어 라이브러리에 유용함(중복된 사본이 없음)

• Swapping은 뭔데?

일시적으로 메모리에서 스왑되어 백업 저장소로 돌아간 다음 계속 실행하기 위해 다시 메모리로 가져올 수 있는 프로세스.

* 효율성 : 스왑 시간의 대부분이 전송 시간임. 총 전송 시간은 스왑된 메모리 양에 직접 비례함.

• backing store?(백업 저장소)

빠른 디스크와 모든 사용자를 위한 모든 메모리 이미지의 사본을 수용할 만큼 충분히 큼.

이러한 메모리 이미지에 직접 액세스할 수 있어야 함.

• Simple memory management는 뭔데

가상 메모리가 없는 간단한 관리법임.

실행하는 프로세스는 메인 메모리에 전체적으로 로드되있어야 함.

Fixed partitioning, dynamic partitioning, simple paging, simple segmentation의 방법들이 있음.

• 현대 최신식 OS에서는 사용되지 않지만, 가상 메모리에 대한 적절한 논의의 토대를 마려함.
• 일반적으로 마이크로프로세서 펌웨어 프로그래밍에 사용됨.

• Fixed partitioning

메카니즘

메인 메모리를 파티션이라고 부르는 안겹치는 영역으로 분할함. 파티션은 같거나 다른 사이즈 일 수 있음.

원리

파티션의 크기보다 작거나 같은 크기의 프로세스는 파티션에 할당된다.

모든 파티션이 가득찼을 경우, OS는 한 프로세스를 파티션밖으로 스왑할 수 있다.

한 파티션에 맞추기에 프로그램이 너무 클 수 있는데, 프로그래머는 오버레이를 포함하여 설계해야함.

-> 모듈이 필요한 것이 부재할 때, 유저 프로그램은 그 프로그램의 파티션에 해당 모듈을 프로그램이나 데이터가 있 더라도 오버레잉해서 반드시 로드해야한다.

장단점

메인 메모리 사용이 비효율적. 프로그램이 얼마나 작든간에 모든 프로그램이 전체 파티션을 차지하게 된다. 이 것을 internal fragmentation이라고 부른다.

unequal-size 파티션은 이러한 문제를 줄이지만, 여전히 남아있다.

- equal-size 파티션의 배치 알고리즘

1. 가용한 파티션이 있다면, 프로세스는 그 파티션에 로드된다.

-> 모든 파티션이 동등한 사이즈이므로, 어느 파티션이 사용되는지는 중요치않다.

1. 모든 파티션이 차단된 프로세스에 의해 점유되면, 스왑할 한 프로세스를 선택해서 새 프로세스를 위한 공간을 만든다.

• unequal-size 파티션의 배치 알고리즘

다수의 큐를 사용

1. 각 프로세스를 맞는 사이즈 중 가장 작은 파티션에 할당한다.
2. 각각 파티션 크기에 하나의 큐가 있음.
3. internal fragmentation을 최소화하는 방향으로 시도한다.
4. 문제점: 해당하는 사이즈 범위에 있는 프로세스가 존재치않을때, 몇몇의 큐가 비어있게 된다.
5. 한 프로세스를 메인 메모리에 로드할 시점에서 프로세스를 홀드할 가장 작은 가용 파티션이 선택된다.
6. internal fragmentation을 부담하면서 멀티프로그램의 수준을 높인다.

• Dynamic Partitioning이 뭔데?

원리

파티션이 변화가능한 길이나 수로 이루어짐.

각 프로세스는 정확히 필요한만큼 메모리를 할당받음.

결국 메인 메모리에 구멍들이 만들어지는데, 이를 external fragmentation이라고 함.

프로세스가 인접하고 모든 여유 메모리가 하나의 블록에 있도록 프로세스를 이동하려면 압축을 사용해야함.

IBM의 OS/MVT에 사용됨

배치 알고리즘

어느 여유 블락에 프로세스를 할당할지 결정할 때 사용됨.

목표 : 압축 사용빈도를 줄이기 위해(시간 소모)

가능한 알고리즘

best-fit : 만족하는 것 중, 가장 작은 구멍을 선택

first-fit : 만족하는 것 중, 첫 구멍을 선택

next-fit : 마지막 배치의 다음부터 만족하는 것 중, 첫 구멍을 선택

worst-fit : 가장 큰 구멍을 선택

• Fragmentation

External

총 메모리 공간이 요청을 만족하기 위해서 존재함, 하지만 연속적이진 않음.

Internal

요청된 메모리보다 약간 더 크게 메모리가 할당됨.

이 크기의 차이는 파티션 안의 메모리고, 사용되지는 않음.

• Compaction

external fragmentation 문제의 해결책

구멍들을 합치기 위해 프로그램들을 재할당함.

재배치가 동적이고, 실행 시간에 행해질 때만 사용 가능함.

• Buddy system

원리

fixed와 dynamic 파티셔닝의 단점을 극복하기 위한 합리적인 절충안

메모리 블락은 2^K, L <= K <= U ( L : 할당가능 블락 최소 크기, U : 할당가능 블락 최대 크기)

• 버디 시스템이 효율적이긴 하지만, 현재 OS에서 사용되는 페이징과 세그멘테이션 기반의 가상 메모리가 버디 시스템보다 더 성능이 좋다.