[OS] Memory Management

- 레지스터는 일반적으로 CPU 클록 1 사이클 내에 접근 가능

- 메인 메모리의 경우 많은 CPU 클록 사이클 소요, CPU가 필요한 데이터가 없어 명령어 수행 못하는 stall 현상 발생 가능

- 이를 해결하기 위해 CPU와 메인 메모리 사이에 빠른 속도의 메모리(캐시)를 추가

 

Base Register, Limit Register

- Base Register: 가장 작은 합법적인 물리 메모리 주소의 값 저장

- Limit Register: 주어진 영역의 크기 저장

→ Base register, Limit register는 논리 주소 공간을 정의함

 

Hardware Address Protection 메모리 공간 보호

- 운영체제의 메모리 공간이나, 다른 사용자 프로그램의 메모리 공간의 접근이 일어나면 운영체제는 오류로 간주하여 트랩 발생시킴

- 이를 통해, 사용자 프로그램이 운영체제나 다른 사용자 프로그램의 코드나 데이터 구조를 수정하는 것을 막음

 

Address Binding (Binding of Instructions and Data to Memory)

- 대부분의 시스템은 사용자 프로세스가 메모리 내 어느 부분으로도 올라올 수 있도록 지원 (00000~)

- 사용자 프로그램은 여러 단계에 거쳐 실행되어, 단계를 거치는 동안 주소들은 여러 표현 방식을 거침

- 원시 프로그램(숫자가 아닌 심볼 형태 주소) → 컴파일러(재배치 가능 주소로 바인딩) → 연결편집기 또는 적재기(절대 주소로 바인딩)

- 메모리 주소 공간에서 명령어, 데이터의 바인딩은 바인딩이 이루어지는 시점에 따라 구분됨

1) Compile time binding

프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알면, 컴파일러는 절대 코드 생성 가능

2) Load time binding

프로세스가 메모리 내에 들어갈 위치를 컴파일 시점에 알지 못하면, 컴파일러는 우선 재배치 가능 코드를 생성

심볼과 진짜 번지수와의 바인딩은 프로그램이 메모리로 실제로 적재될 때 이루어짐

3) Execution time binding

프로세스 실행 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면, 바인딩이 run time까지 지연

이것이 가능하려면 특별한 하드웨어를 이용해야 함

 

Logical vs Physical Address Space (논리 주소 공간 vs 물리 주소 공간)

- Logical address 논리주소: CPU가 생성하는 주소

- Physical address 물리주소: 메모리가 취급하게 되는 주소

- 컴파일 시 바인딩, 적재 시 바인딩을 하면 logical address와 physical address가 같음

- 실행시간 바인딩을 하면 logical address와 physical address가 다름, 이때 logical address를 virtual address라 함

- Logical address space: 프로그램에 의해 생성된 모든 logical address 집합

- Physical address space: 프로그램에 의해 생성된 모든 physical address 집합

- 프로그램 실행 중에는 logical address를 physical address로 바꿔줘야 하는데, 이를 메모리 관리기(MMU)가 함

 

Dynamic Relocation (Dynamic Loading)

- Logical address를 physical address로 변환하기 위한 기법 중 MMU 기법에 대한 내용

- 여기서는 base register를 relocation register라고 부름

- ex) relocation register 값이 14000이고 프로세스가 346번지를 액세스하면, 실제론 메인 메모리의 14346번지를 액세스하게 됨

         이때 사용자 프로그램은 실제적인 물리 주소(14346)를 알 수 없어야 함

- 이전까지는 프로세스가 실행되기 위해 프로세스 전체가 미리 메모리에 올라와 있어야 했음 (프로세스 크기 ≤ 메모리 크기)

- 메모리 공간을 효율적으로 사용하기 위해 dynamic loading 사용

- 각 routine은 호출되기 전까지 메모리에 올라오지 않고, reload 가능한 상태로 디스크에서 대기

- 실행되고 있는 routine이 다른 routine 호출하면 해당 routine이 이미 메모리에 적재되어 있는지 조사

 

Dynamic Linking (Shared Library)

- Static Linking: loader에 의해 binary program image로 결합된 시스템 라이브러리와 프로그램 코드

- Dynamic Linking: execution time까지 linking 지연

- Stub: 해당 라이브러리를 어떻게 찾을 것인지 알려주는 작은 코드 조각

- Dynamic linking에서는 라이브러리를 부르는 곳마다 stub이 생김

- Stub이 실행될 때, 필요한 라이브러리 루틴이 이미 메모리에 존재하는지 검사하고 없으면 디스크에서 가져옴, 자신을 그 루틴의 번지로 대체

- 이후에 해당 부분이 불리면 또 dynamic linking을 할 필요 없이 직접 그곳의 라이브러리 루틴 수행하면 됨

- 라이브러리는 어느 때나 새 버전으로 교체될 수 있고, 해당 라이브러리 사용하는 모든 프로그램은 자동적으로 새 라이브러리 버전 사용하게 됨

 

Swapping

- 프로세스는 실행 중에 임시로 backup store에 스왑되었다가 실행을 계속하기 위해 다시 메모리로 되돌아 올 수 있음

- 모든 프로세스의 물리주소 공간 크기의 총합이 시스템의 실제 물리주소 크기보다 커도, 스와핑 이용하면 동시에 실행하는 것이 가능

- Backing store: 모든 메모리 이미지 복사본 수용할 수 있을 정도로 크고 빠른 디스크. 여기에 직접 액세스 할 수 있어야 함

- Roll out/Roll in: priority-based scheduling 기법에 사용되는 swapping. (우선순위 낮은 프로세스 swap-out 됨)

- Swap time의 주요 부분은 transfer time이며, 이는 swap 된 메모리의 크기에 정비례

- 시스템은 디스크에 메모리 이미지가 있는 실행 준비된 프로세스들의 ready queue를 유지함

 

Multiple-Partition Allocation

- 가장 간단한 공간 할당 방법은 메모리를 똑같은 고정된 크기로 분할(partition)하는 것

- 각 분할마다 한 프로세스를 가지고, 이때 분할의 개수를 multiprogramming degree라고 부름

- 가변 분할 기법: 메모리의 어떤 부분이 사용되고 있고(allocated partition), 어떤 부분이 사용되고 있지 않는지 파악(free partition, hole)

- Hole: 프로세스가 도착하면 프로세스를 수용할 수 있을 만큼 충분히 큰 hole에 프로세스를 할당

- OS는 allocated partition과 free partition에 대한 정보를 유지해야 함

 

Dynamic Storage-Allocation Problem

1. First-fit 최초적합

- 첫 번째로 사용 가능한 가용 공간(hole)을 할당

- 검색은 집합의 시작에서부터 하거나, 이전에 검색이 끝났던 곳에서 시작

2. Best-fit 최적적합

- 사용 가능한 공간(hole) 중 가장 작은 것을 선택

- 세 방법 중 할당 후 작은 가용 공간 만들어냄

- 자유 공간이 크기순으로 정렬되어 있지 않으면 전 리스트 다 검색

3. Worst-fit 최악적합

- 사용 가능한 공간(hole) 중 가장 큰 것을 선택

- 세 방법 중 할당 후 가장 큰 가용 공간을 만들어냄 (충분히 커서 다른 프로세스에게 쓰일 수 있음)

- 자유 공간이 크기순으로 정렬되어 있지 않으면 전 리스트 다 검색

- 이 외에도 frequency 낮은 것 선택, priority 낮은 것 선택 등 여러 알고리즘 존재

 

Fragmentation 단편화

- External Fragmentation

메모리에 적재하고 제거하는 것이 반복되면 가용 공간들이 너무 작은 조각들로 분산되어 있음

모두 합치면 충분한 공간이 되지만 분산되어 있어서 사용 불가능함

→ Compaction(밀집)로 해결: 메모리 모든 내용 한 군데로 몰고 자유 공간 한 군데로 몰아 큰 블록 만드는 것 (항상 가능한 것 X)

- Internal Fragmentation: 

메모리를 먼저 아주 작은 공간들로 분할하고, 프로세스가 요청하면 분할된 크기의 정수배만큼 할당해주는 것

할당된 공간이 요구된 공간보다 약간 더 클 수 있는데, 이 부분이 internal fragmentation임

 

Paging

- 프로세스가 적재된 물리주소는 연속적이지 않을 수 있음 → external fragmentation을 피해야 함

- 물리주소를 고정된 크기의 블록인 frame으로 나눔 (크기는 2의 제곱, 512bytes ~ 16Mbytes)

- 논리주소를 고정된 크기의 블록인 page로 나눔

- Page number(p): 페이지 테이블을 액세스 할 때 사용 (페이지 테이블은 각 페이지가 점유하는 주소 가짐)

- Page offset(d): 페이지 주소에 이값을 더하면 원하는 물리주소가 됨