[운영체제] 18.Memory Management (1)

Logical vs Physical Address

1. Logical Address (= Virtual Address)

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작 
• CPU가 보는 주소는 logical address 이다. 

2. Physical Address

• 메모리에 실제 올라가는 위치 

3. 주소 바인딩 : 주소를 결정하는 과정 어떤 프로그램이 물리적 메모리 어느 곳에 올라갈지를 결정한다. 

Symbolic Address -> Logical Address -> Physical Address

*Symbolic Address : 프로그래머들이 특정 이름을 통해 변수를 지정하고 값을 저장할 때, 변수의 이름을 통해 값에 접근하게 된다. 즉 우리가 흔히 사용하는 포인터이다. 

주소 바인딩 (Address Binding)

1. Compile Time Binding 

• 물리적 메모리 주소가 컴파일 시점에 정해짐. -> 지금의 컴퓨터 시스템에서는 비효율적이므로 사용하지 않는다. 
• 시작 위치 변경 시 재컴파일 
• 컴파일러는 절대 코드 (absolute code) 를 생성함. 

2. Load Time Binding 

• 프로그램이 시작되서 메모리에 올라갈 때 (Load) 물리적인 메모리 주소가 결정됨. 
• Loader의 책임하에 물리적 메모리 주소 부여 
• 컴파일러가 재배치 가능 코드 (relocatable code) 를 생성한 경우 가능 

3. Execution Time Binding (Run Time Binding)

• 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음 
• 그림에서 300번대 주소로 바인딩이 되어 있었으나 프로그램이 실행되다가 700번대 주소로 옮겨갔음. 
• CPU가 주소를 참조할 때마다 binding 을 점검 (address mapping table)
• 하드웨어적인 자원이 필요 -> MMU라는 하드웨어가 주소 변경을 지원해주어야 가능하다. 

CPU는 logical address를 바라보며, 프로그램에서 연산을 수행할 때 logical address와 바인딩 되어있는 physical address를 통해 실제 저장장치에 있는 데이터를 가지고 연산하게 된다. 

MMU (Memory-Management Unit)

1. MMU

• 주소 변환을 지원해주는 하드웨어 장치이다. 
• logical address를 physical address로 매핑한다. 

2. MMU Scheme 

• base register (=relocation register) 에 시작 위치 (14000번지) 가 저장되어 있다.
• Relocation Register : 접근할 수 있는 물리적 메모리 주소의 최소값
• Limit Register : 논리적 주소의 범위
• 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (=relocation register)의 값을 더한다. 

3. User Program 

• logical address 만을 다룬다. 
• 실제 physical address를 볼 수 없으며 알 필요가 없다. 

Dynamic Loading 

• Dynamic, 즉 동적이라는 의미에 집중 ! -> 필요할 때 마다 메모리에 Load 한다. 
• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 동적으로 load 한다. 
• memory utilization 가 향상된다.  
• 가끔씩 사용되는 많은 양의 코드의 경우 유용 (ex. 오류 처리 루틴)
• 운영체제의 특별한 지원없이 프로그램 자체에서 구현 가능
• Loading : Memory에 올리는 것 

Overlays (Manual Overlay)

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림 
• 프로세스의 크기가 메모리보다 클 때 유용 
• 운영체제의 지원없이 사용자에 의해 구현 
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현 
• Dynamic Loading 과는 컨셉이 유사하나 등장한 배경이 다르다. 

Swapping 

1. Swapping 

• 프로세스를 일시적으로 메모리에서 backing store(=swap area) 로 쫓아내는 것 
• backing store : 디스크. 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간 

2. Swap In / Swap Out 

중기 스케줄러 (swapper) 에 의해 swap out 시킬 프로세스 선정 

• priority based CPU scheduling program 
  - priority 가 낮은 프로세스를 swap out 시킴.
  - priority 가 높은 프로세스를 swap in, 메모리에 올려 놓음 
• compile time 혹은 load time binding 에서는 원래 메모리 위치로 swap in 해야 함. 
• 효율적으로 swapping 이 일어날 수 있도록 run time binding 이 지원되는 것이 유리함. 빈 메모리 영역 아무곳에나 올릴 수 있음. 
• swap time 은 대부분 transfer time에 비례함. 
• 원래의 의미는 프로그램 주소 공간 전체가 쫓겨난다는 것을 의미하며, paging 에서는 일부 page가 쫓겨난다는 의미로도 swap out 이라고 사용된다. 

Dynamic Linking 

• Linking 을 실행 시간까지 미루는 기법.
• Linking : 여러 군데 존재하던 컴파일된 파일을 하나의 실행 파일로 만드는 과정

1. Static Linking 

• 라이브러리가 프로그램의 실행 파일 코드에 포함됨 
• 실행 파일 크기가 커짐 
• 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 (ex. printf 함수의 라이브러리 코드)

2. Dynamic Linking 

• 라이브러리가 실행시 linking 됨
• 라이브러리가 별도의 파일로 존재하다가 라이브러리가 호출되면 라이브러리 루틴의 위치를 찾을 수 있는 stub 이라는 작은 코드를 둠
• 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴 
• 운영체제의 도움이 필요 -> shared library 파일

Allocation of Physical Memory 

1. 메모리의 영역 

• OS 커널 상주 영역 (낮은 주소 영역)
• 사용자 프로세스 영역 (높은 주소 영역)

2. 사용자 프로세스 영역의 할당 방법 

Continuous Allocation, 연속 할당 

• 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것 
• Fixed partition allocation(고정 분할 방식), Variable Partition Allocation (가변 분할 방식)

Noncontinuous Allocation, 불연속 할당 -> [현대의 OS에서 사용되는 방식]

• 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음 
• Paging, Segmentation, Paged Segmentation 

연속 할당 방법 

1. 고정 분할 방식 

• 물리적 메모리를 몇 개의 영구적 분할 (partition) 으로 나눈다. 
• 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재한다. 
• 분할 당 하나의 프로그램을 적재한다. 
• 동시에 메모리에 load 되는 프로그램의 수가 고정되며, 최대 수행 가능한 프로그램의 크기가 제한된다. -> 융통성이 없다. 
• 공간이 너무 작아서 사용이 안된 경우 -> 외부 조각 (External Fragmentation)
• 프로그램의 크기가 분할된 공간보다는 작아서, 그 안에서 남는 메모리 조각이 있는 경우 -> 내부 조각 (Internal fragmentation)

2. 가변 분할 방식 

• 프로그램들을 메모리에 차곡차곡 순서대로 올리는 방식으로, 한 프로그램이 끝나면 빈공간이 되어 다른 프로그램이 실행된다. 
• 프로그램의 크기를 고려해서 할당한다. 
• 분할의 크기, 개수가 동적으로 변한다. 
• 기술적 관리 기법이 필요하다. 
• External Fragmentation 발생 (프로그램이 실행되다가 종료되면 Hole 이 생긴다)

Hole

Hole

• 가용 메모리 공간.
• 다양한 크기의 hole  들이 메모리의 여러 곳에 흩어져 있다. 
• 프로세스가 도착하면 수용가능한 hole을 할당 
• 운영체제는 a) 할당 공간 b) 가용 공간 == hole 에 대한 정보를 유지한다. 

Dynamic Storage Allocation Problem

: 가변 분할 방식에서 size가 N 인 요청을 만족하는 가장 적절한 hole 을 찾는 문제 -> 적어도 N 이상의 크기이어야 함!

First-fit 

• Size가 N이상인 것 중 최초로 찾아지는 hole 에 할당 

Best-fit

• Size가 N 이상인 가장 작은 hole을 찾아서 할당 
• Hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole 의 리스트를 탐색해야 함 
• 많은 수의 아주 작은 hole들이 생성됨 

Worst-fit

• 가장 큰 hole에 할당 
• 모든 리스트를 탐색해야 함 -> 시간 복잡도 소요
• 상대적으로 아주 큰 hole 들이 생성됨 

* first-fit 과 best-fit이 worst-fit 보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐 

Compaction 

• 외부 단편화 현상을 해결하는 방법중 하나 
• 사용중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아서 큰 block 으로 만든다. 
• 비용이 매우 많이 드는 방법이다. (전체 프로그램의 바인딩과 관련되기 때문!)
• 프로세스의 주소가 실행시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다. (Runtime Binding 지원 필수!)
• 전체를 다 이동시키는 것보다 작은 이동만으로 compaction 을 하는 것이 효율적일 수도 있다