Memory Management

메모리에는 Logical address와 Physical address가 있다.

 

Logical address (=virtual address) :

 - 프로세스마다 독립적으로 가지는 주소 공간

 - 각 프로세스마다 0번지부터 시작

 - CPU가 보는 주소는 logical address임

 

Physical address :

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

 

 

 

주소 바인딩 (Address binding) :

주소를 결정하는 것. Symbolic Address --> Logical Address --> Physical Address

주소 바인딩에는 3가지 종류가 있다.

 

1. Compile time binding

 - 물리적 메모리 주소(physical address)가 컴파일 시 알려짐

 - 시작 위치 변경 시 재 컴파일 필요 <-- 매우 비효율적

 - 컴파일러는 절대 코드(absolute code) 생성

 - 현대에 잘 사용하지 않는 방법

 

2. Load time binding

 - Loader의 책임하에 물리적 메모리 주소 부여

 - 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능

 

3. Execution time binding ( =Run time binding)

 - 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음

 - CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)

 - 하드웨어적인 지원이 필요  ( ex. base and limit registers, MMU )

 

아래 그림을 보면 쉽게 이해할 수 있다.

 

주소 바인딩을 위해서는 주소 변환을 해주는 하드웨어인 MMU가 필요하다.

 

MMU (Memory-Management Unit)

- logical address를 physical address로 매핑해 주는 Hardware device

- MMU scheme : 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocaion register)의 값을   더한다.

- user program은 logical address만을 다루며, 실제 physical address를 볼 수 없고, 알 필요도 없다.

 

MMU는 relocation register(base register), limit register를 사용하여 주소 바인딩을 해준다. 아래 그림을 보면 쉽게 이해할 수 있다.

relocation(base) register 는 실제 하드디스크에 해당 프로세스의 시작 주소(물리적)를 담고 있다. 즉 접근할 수 있는 물리적 메모리의 최소값이다.

limit register 는 해당 프로세스의 크기를 담고 있다. 해당 프로세스의 범위를 넘어서는 주소를 요청하면 이를 막기위해 존재한다. 즉 논리적 주소의 범위를 넘어서 요청하게 되면 trap이 걸려서 운영체제에게 주도권이 넘어가게 되고 운영체제는 trap의 원인을 찾는다.

즉 아래와 같은 논리적 과정을 거치는 것이다.

 

 

 

 

 

 

이제 메모리와 관련한 몇가지 용어를 알아보자. (Dynamic Loading, Overlays, Swappging, Dynamic Linking )

 

• Dynamic Loading

- 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것.

- memory utilization의 향상

- 가끔씩 사용되는 많은 양의 코드의 경우 유용 (ex. 오류 처리 루틴)

- 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(os는 라이브러리를 통해 지원 가능)

* loading : 메모리로 올리는 것

 

 

• Overlays

- 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림

- 프로세스의 크기가 메모리보다 클 때 유용

- 운영체제의 지원없이 사용자에 의해 구현

- 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현. (프로그래밍이 매우 복잡. Manual Overlay)

* Dynamic Loading과의 차이점은 Dynamic Loading은 OS가 라이브러리로 제공한다는 것이다.)

 

 

• Swappging

swapping : 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것.

 

backing store (=swap area) : 

- 디스크. 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간

 

Swap in / Swap out :

- 일반적으로 중기 스케쥴러(swapper)에 의해 swap out 시킬 프로세스 선정

- priority-based CPU scheduling algorithm

---- priority가 낮은 프로세스를 Swapped out 시킴

---- priority가 높은 프로세스를 메모리에 올려 놓음

- Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 함

- Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음

- swap time은 대부분 transfer time (swap되는 양에 비례하는 시간)임

스와핑은 런타임 바인딩이 지원되면 매우 좋다. 다른 바인딩들은 쫓겨난 이후에 그대로 같은 자리로만 와야하지만 런타임 바인딩은 지속적으로 주소가 바뀔 수 있기 때문.

 

 

• Dynamic Linking

Dynamic Linking : Linking을 실행 시간(execution time)까지 미루는 기법

Linking : 프로그램을 작성한 후, 컴파일과 링크를 해서 실행파일을 만들게 된다.  이때 여러 군데에 존재하던 컴파일된 파일들을 묶어서 하나의 실행파일로 만드는 과정을 Linking이라고 한다.

Linking에는 2가지 종류가 있다.

 

Static linking

 - 라이브러리가 프로그램의 실행 파일 코드에 포함됨

 - 실행 파일의 크기가 커짐

 - 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 (ex. printf 함수의 라이브러리 코드)

 

Dynamic Linking 

 - 라이브러리가 실행시 연결(link)됨

 - 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠

 - 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴

 - 운영체제의 도움이 필요

 

* 예시) 다이나믹 링킹을 하면 printf 라이브러리를 내 코드에 담아두는 것이 아니라 printf 라이브러리의 주소만을 저장해준다. (다이나믹 링킹을 하게 해주는 라이브러리를 shared library, shared object, dnl이라고도 한다.)

 

---

물리적 메모리를 어떻게 관리할 것인가?

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용한다.

 - OS 상주 영역. interrupt vector와 함께 낮은 주소 영역 사용

 - 사용자 프로세스 영역. 높은 주소 영역 사용

• 사용자 프로세스 영역의 할당방법에는 2가지 존재한다. 

 - Contiguous allocation : 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것.

 ---- Fixed partition allocation

 ---- Variable partition allocation

 - Noncontiguous allocation : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음

 ---- Paging

 ---- Segmentation

 ---- Paged Segmentation

 

 

먼저 Contiguous allocation에 대해 알아본다.

● Contiguous allocation

• 고정분할(Fixed partition) 방식

 - 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔 

 - 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재

 - 분할당 하나의 프로그램 적재

 - 융통성이 없음

 - 동시에 메모리에 load되는 프로그램의 수가 고정됨

 - 최대 수행 가능 프로그램 크기 제한

 - interal fragmentation, external fragmentation 발생

 

• 가변분할(Variable partition) 방식

 - 프로그램의 크기를 고려해서 할당

 - 분할의 크기, 개수가 동적을로 변함

 - 기술적 관리 기법 필요

 - External fragmentation 발생

고정 분할 방식은 미리 메모리들을 고정하여 분할해 두고, 거기에 프로그램들을 끼워넣는 방식이다. 위 그림을 보면 프로그램A는 분할1에 들어갈 수 있지만, 프로그램B는 그 크기가 분할2에 들어가기에는 크다. 해서 분할3에 들어간다. --> 이때 분할2는 외부 조각, 분할3의 여유 공간은 내부 조각이 된다.

 

가변 분할 방식은 프로그램들의 크기에 맞게 메모리의 크기를 할당한다. 해서 고정 분할 방식에 비해 효율적이다. 위의 그림을 보면 프로그램B가 끝나고 프로그램D가 들어가야 하는데, 프로그램B의 자리는 프로그램D가 들어가기에는 작다. 해서 이때 외부조각이 생기게 된다.

External fragmentation(외부 조각)
 - 프로그램 크기보다 분할의 크기가 작은 경우
 - 아무 프로글램에도 배정되지 않는 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할

Internal fragmentation(내부 조각)
 - 프로그램 크기보다 분할의 크기가 큰 경우
 - 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
 - 특정 프로그램에 배정되었지만 사용되지 않는 공간

 

* Hole

 - 가용 메모리 공간

 - 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음

 - 프로세스가 도착하면 수용가능한 hole을 할당

 - 운영체제는 다음의 정보를 유지 

    a) 할당 공간.    b) 가용 공간(hole)

위 그림에서 보이듯이 hole들이 많아지면 그만큼 낭비되는 메모리 공간이 많아지는 것이다. 해서 이러한 hole들을 찾아 매꾸는 알고리즘이 존재한다.

 

Dynamic Storage-Allocation Problem :

가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

 

• First-fit 

 - size가 n 이상인 것 중 최초로 찾아지는 hole에 할당

• Best-fit

 - size가 n 이상인 가장 작은 hole을 찾아서 할당

 - hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함

 - 많은 수의 아주 작은 hole들이 생성됨

• Worst-fit

 - 가장 큰 hole에 할당

 - 역시 모든 리스트를 탐색해야 함

 - 상대적으로 아주 큰 hole들이 생성됨

 

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

 

hole을 한 곳에 몰아서 재사용하는 방법을 compaction이라 한다.

compaction

 - external fragmentation 문제를 해결하는 한 가지 방법

 - 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것

 - 매우 비용이 많이 드는 방법임.

 - 최소한의 메모리 이동으로 compaction하는 방법(매우 복잡한 문제)

 - compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.

 

 

 

 

● Uncontiguous allocation

불연속 할당 방법은 크게 Paging, Segmentation 방식이 있다.

Paging : 프로그램을 구성하는 주소공간을 같은 크기의 페이지로 짜름, 해서 페이징단위로 프로그램을 올려두는 것이다. 물론 이 방법을 쓰면 주소변환이 복잡해진다. 즉 MMU가 주소변환을 페이지 단위로 해야한다.

 

Segmentation : 프로그램의 주소 공간을 같은 페이지 단위로 자르는 것이 아니라, 의미있는 단위로 자르는 것. 즉 프로그램의 코드, 데이터, 스택 세그먼트들을 잘라가지고 각각의 세그먼트들을 다른 물리적 위치에 올려둔다. 의미단위로 자른 것이기 때문에 크기가 동일하진 않다. —> 즉 hole이 발생할 수 있다.

 

 

 

 

 

 

---

출처 : 이화대학교 반효경 교수님의 운영체제 강의
http://www.kocw.net/home/search/kemView.do?kemId=1046323