9-1강. Memory Management 1

 메모리에 접근하기 위해서는 주소가 필요하다. 주소에는 Logical address ( or Virtual address)와 Physical address가 있다. 프로세스가 만들어지면 독자적인 주소 공간 (Address space)가 만들어진다고 했는데 그때 사용되는 것이 논리적 주소이다. 또한 각 프로세스마다 0번지부터 시작하며 CPU는 이 주소를 활용한다. 반면 물리적 주소는 말 그대로 Memory에서 물리적으로 접근할 수 있는 주소로 메모리에 실제 올라가는 위치를 뜻한다. 

 

 결국 프로세스가 실행되기 위해서는 메모리에 프로세스가 올라가야 하고, 논리적 주소가 물리적 주소로 바뀌어 처리되어야 하는데 이것을 '주소 변환'이라 하며 '주소 바인딩'이라고도 한다.

 

                                                                          * Symbolic Address *

 우리가 프로그래밍을 할 때 직접 메모리의 주소에 관여하지 않는다. 우리는 변수의 주소 혹은 변수로 데이터의 흐름을 제어할 뿐이다. 이때 사용되는 것이 Symbolic address이다. 이것이 컴파일이 되면 숫자로 된 주소, 즉, Logical address로 변환되고, 실행이 되려면 물리적 주소가 필요하기 때문에 이때 주소 변환이 이루어진다.

 

 

---

주소 바인딩(Address Binding) (주소 변환)

 

1. Compile time binding

 물리적 메모리 주소(Physical address)가 컴파일 시에 이루어지는 방법을 컴파일 타임 바인딩이라고 부른다.

 

2. Load time binding

 실행이 시작될 때 주소 변환이 이루어지는 것을 Load time binding이라 하고

 

3. Execution time binding ( =Run-time binding)

 실행을 하는 도중에도 주소 변환이 이루어질 수 있는 방법을 Execution time binding이라고 한다. 

 

예시를 들어보자.

 

Add A, B

Jump C

A: 100

B: 330

C: exit

 

 이 코드는 A의 위치에 있는 값과 B의 위치에 있는 값을 더해서 A에 더하고 C로 점프하라는 코드이다. 이게 컴파일이 되면 Symbolic address였던 A, B, C는 숫자로 된 주소(Logical address)로 바뀌게 된다. 프로세스마다 갖는 주소이기 때문에 0부터 시작하는 Logical address이다. 

 

 Compile time binding : 이제 이것이 실행이 되려면 메모리의 물리적인 주소로 올라가야 하고 이것을 주소 바인딩이라고 한다고 했다. 아까 전에 설명했던 Compile time binding은 앞서 논리적 주소라고 했던 숫자가 사실은 물리적 주소가 되는 것이다. 그렇기 때문에 컴파일러가 만들어 낸 코드는 절대 코드(absolute code)라고 불린다. 그래서 메모리에 올리고 싶은 위치를 바꾸고 싶으면 컴파일을 다시 해야 한다. 그러나 이 방법으로 주소 바인딩을 하는 것은, 뒤에 있는 주소들은 비었음에도 불구하고 0번지에 있는 주소부터 결정되기 때문에 비효율적인 방법이다. 옛날처럼 컴퓨터에서 하나의 프로그램만 실행할 수 있었던 경우에는 썼으나 최근 컴퓨터 시스템에서는 쓰지 않는다.

 

 

 Load time binding : 실행을 시작할 때 물리적 주소가 결정되는 방법이다. 메모리를 봤더니 500번지가 비어있으니 500번지에다가 논리적 주소 0번지부터 차례대로 올리라는 뜻이다. 컴파일러가 만들어낸 코드의 논리적 주소가 메모리 상황에 따라 바뀔 수 있기 때문에 컴파일러가 재배치 가능 코드(relocatable code)를 생성해야 한다. 

 

 Run time binding : Load time binding과 비슷하게 실행 시 물리적 주소가 결정된다. 그러나 이 프로세스가 메모리에서 쫓겨났다가 다시 들어올 수도 있기 때문에 주소들이 실행 도중 바뀔 수 있게 된다. 이것이 Run time binding이다. 따라서 이 방법을 사용하면 CPU가 해당 프로세스의 주소를 참조할 때마다 binding을 Address mapping table을 이용하여 점검해야 하며 이를 위해 하드웨어적인 지원이 필요하다. 이때 사용되는 것이 MMU(Memory Management Unit) 혹은 base and limit register이다. 

 

 

                                                                그림 1 : 주소 바인딩 예시

 

 

---

Memory Management Unit (MMU)

 좀 전에 Run time binding을 이야기할 때 나왔던 장치이다. MMU는 Logical address를 Physical address로 매핑해주는 Hadware device이다. 

 

 MMU에서 주소 변환을 하는 방법은 기본적으로 레지스터 2개를 이용한다. 다음 예시를 보자.

 

그림 2 : Dynamic Relocation 예시

 CPU가 논리 주소 346번지 지에 있는 내용을 읽어오라고 한다면 MMU에 있는 레지스터 Reloacation register ( = Base register)와 Limit register를 이용해서 주소 변환을 한다. Base register는 프로그램이 실제로 메모리에 올라가는 그 시작 위치를 저장하고 있다. 따라서 MMU에서는 Base register에다가 논리 주소를 더해서 14346 물리 주소를 얻는다. 그리고 Limit register에는 이 프로세스가 할당받은 최대 논리 주소 크기를 저장한다. 그 이유는, 만약 이 프로그램이 악의적으로 자신이 할당받은 범위를 벗어나는 공간에 접근하는 경우를 막기 위함이다. 따라서 해당 예시에서 P1은 14000~17000까지만 실제 메모리 주소로 할당받았으며 P1이 17000을 넘는 공간에 접근하려고 할 때 하지 못하게 막는 장치를 하는 것이 Limit register이다. 따라서 CPU가 논리적 주소를 받으면 가장 먼저 Limit register의 값과 비교하여 요청된 논리적 주소가 Limit 값보다 더 큰지 판단한다. 만약 크다면 Addressing error trap(Software Interrupt)을 발생시켜 CPU 제어권을 운영체제로 넘기게 된다. 

 

그림 3 : MMU Scheme

 

그림 4 : MMU explanation

 

 

---

---

Appendix : 용어 설명

* Dynamic Loading

 

 프로그램을 메모리로 올려야 실행이 될 것이다. Dynamic(동적으로) Loading(메모리로 올림)이란 프로그램을 전부 메모리에 올리는 것이 아니라 해당 루틴이 불려질 때마다 메모리로 올리는 것을 말한다. 여기서 말하는 동적 로딩과 OS에서 제공해주는 페이징과는 다른 개념인데 페이징에 대해서는 추후 설명하겠다. 원래 동적 로딩은 OS가 지원해주는 것이 안이고 프로그래머가 직접 동적 로딩을 하도록 만드는 것이다. 그 루틴들을 OS가 라이브러리 형태로 제공하여 프로그래머가 구현토록 한다. 그러나 요즘은 OS가 자체적으로 로딩을 제어하는 페이징 기법과 동적 로딩을 일종의 synonym으로 사용하기도 한다. 

 

* Overlays

 

 Overlay는 메모리에 프로세스 중에서 필요한 정보만을 올리는 것을 말한다. 이 내용만 봐서는 Dynamic Loading과 같다. 그러나 역사적으로 다르다. Overlay는 초창기 컴퓨터 시스템에서 워낙 메모리 크기가 작다 보니 프로그램 하나를 메모리에 올리는 것도 불가능했다. 따라서 프로그래머가 수작업으로 프로그램을 쪼개고, 이 부분이 필요하면 이 부분을 메모리에 올려놓고, 저 부분이 필요하면 저 부분을 메모리에 올려놓는 방식으로 구현하는 것을 Overlay라고 하며 Manual Overlay라고도 한다. 이것은 OS의 지원이 없고 사용자가 직접 모든 것을 구현해야 한다는 것이 Dynamic Loading과의 차이점이다.

 

* Swapping

 

메모리에 너무 많은 프로세스가 올라와 있으면 시스템이 비효율적이 되기 때문에 Swapping을 한다. 프로세스를 일시적으로 메모리에서 하드디스크의 Backing store로 쫓아내는 것을 말한다. Backing store는 Swap area라고도 부르며 많은 사용자 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간이다. 그래서 메모리에서 통째로 쫓겨나는 것을 Swap out이라고 하며, 쫓겨났던 프로세스가 메모리로 들어오는 것을 Swap in이라고 한다. 일반적으로 중기 스케줄러(초반에 배웠다. Swapper)에 의해 Swap out 시킬 프로세스를 결정한다. 주로 Priority-based CPU Scheduling Algorithm을 사용하기 때문에 priority가 낮은 프로세스를 Swap out 시키고 priority가 높은 프로세스를 Swap in 시킨다. 또한 Swap은 한 프로세스를 통째로 하드 디스크에 옮기는 것이기 때문에 방대한 양의 데이터가 이동된다. 따라서 Swap time은 당연하게도 하드 디스크에 접근하기 때문에 대부분이 transfer time(Swap 되는 양에 비례하는 시간)이다. 

 

 이 Swapping System이 지원되기 위해서는 앞서 살펴본 Binding과 연결하여 생각해야 한다. 만약 Compile time binding이나 Load time binding을 사용하고 있다면, Swapped out 당한 프로세스가 원래 위치로 Swapped in 될 때 반드시 정해진 주소로 올라가야 하기 때문에 Swapping과는 맞지 않는다. 따라서 Swapping이 효과적으로 작동하기 위해서는 Run time binding이 지원되어야 할 것이다.

그림 5 : Swapping

 참고적으로 알아 둘 것은 추후 배울 Paging에서는 프로세스의 모든 내용을 쫓아내는 것이 아니라 프로세스의 페이지 중 일부를 쫓아내고 다시 메모리에 로드하는 것도 Page Swap이라고 부르기도 한다. 

 

* Dynamic Linking

 

 Linking을 실행 시간(Execution time)까지 미루는 기법이다. 우리는 프로그램을 작성하고 컴파일을 하면 목적 파일이 생성된다. 링킹이란 여러 군데 존재하는 목적 파일들을 묶어서 하나의 실행 파일을 만드는 과정을 뜻한다. 이때 필요한 라이브러리들이 실행 파일에 전부 포함되어 만들어지는데 이것을 Static Linking이라고 한다. 즉, 라이브러리가 프로그램 실행 파일 코드에 포함되고 이에 따라 실행 파일 크기가 커진다. 그러나 이 경우 동일한 라이브러리를 각각의 프로세스 메모리에 전부 올리기 때문에 메모리 낭비가 심하다. iostream이나 stdio.h와 같은 필수적인 라이브러리들은 중복으로 올라가게 될 것이기 때문이다.

 

 반면 Dynamic Linking은 실행 파일에 라이브러리들을 포함시키는 것이 아니라 프로그램 실행 시에 라이브러리를 호출하는 곳에 도달했을 때 라이브러리를 연결하는 방법이다. 이때 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다. 일종의 pointer(?) 역할이다. 이때 라이브러리를 메모리에 올리게 되는데 만약 메모리에 해당 라이브러리가 이미 있다면 그 루틴의 주소로 가고, 메모리에 없다면 디스크에서 읽어오게 된다. 따라서 Dynamic Linking을 사용한다면 운영체제의 도움이 반드시 필요하다. 이 Dynamic Linking을 해주는 라이브러리를 Shared Library라고 부른다. 리눅스에서는 Shared Object, 윈도우에서는 dll이다.

 

---

---

Allocation of Physical Memory

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

 

 메모리에서 낮은 물리 주소에는 운영체제 커널이 상주하고 높은 주소 영역에는 사용자 프로세스 영역이 올라간다. 이 사용자 프로세스 영역을 할당하는 방법은 두 가지가 있다.

 

1. Contiguous allocation (연속 할당)

 

 각 프로세스가 메모리의 연속적인 공간에 통째로 적재되도록 하는 방법이다. 연속 할당에도 두 가지 방법이 있다.

 

 - Fixed partition allocation(고정 분할 방식)

 고정 분할 방식이란 프로그램이 들어갈 물리적인 메모리의 사용자 프로세스 영역을 미리 파티션으로 나누어 놓는 것이다. <그림 6>을 참조하기 바란다. 여기서는 사용자 프로세스가 올라갈 영역을 4개로 나누어 놓았다. 프로그램 A가 실행이 되고 마침 분할 1에 들어갈 수 있다면 거기에 로드하면 된다. 그런데 프로그램 B가 실행이 된다면 분할 2에는 들어갈 수 없기 때문에 분할 3에 들어간다. 그때 낭비되는 메모리 조각이 발생한다.

 

● External fragmentation (외부 조각)

프로그램 크기보다 분할의 크기가 작아서 다른 분할로 들어가야 할 때 분할 한 개가 통째로 비어버리는 상황이 발생할 수 있다. <그림 6>에서 분할 2에 해당한다. 이를 외부 조각이라고 한다.

 

● Internal fragmentation (내부 조각)

 프로그램 크기보다 분할의 크기가 큰 경우 생기는 조각을 말한다. <그림 6>에서 프로그램 B가 분할 3에 들어갔지만 분할 3 내부에 남은 조각이 있다. 이 부분을 내부 조각이라 한다. 

이렇든 고정 분할 방식에서는 프로그램 크기와 분할의 크기가 맞지 않은 경우에 생기는 문제(내부 조각) 혹은 분할의 크기가 작아서 생기는 문제(외부 조각)가 발생할 수 있다. 

 

- Variable partition allocation(가변 분할 방식)

 가변 분할 방식은 굳이 분할의 크기를 나누어 놓을 필요가 있겠는가 하는 의문에서 나왔다고 볼 수 있다. 따라서 가변 분할 방식은 프로그램이 실행될 때마다 메모리에 차곡차곡 로드하는 방법이다. 그런데 만약 밑의 예시에서 프로그램 B가 끝나고 프로그램 D가 수행되는데 B가 들어갔던 공간이 작기 때문에 그 공간에 들어가지 못하고 아래쪽에 들어가게 된다. 따라서 가변 분할 방식에서는 내부 조각 문제는 발생하지 않지만 고정 분할 방식과 비슷하게 외부 조각 문제는 발생할 수 있다. 

 

 

 

 

그림 6 : Contiguous allocation 예시

 

 따라서 이런 연속 할당에는 다음과 같이 Hole이 발생한다. Hole은 가용 메모리 공간을 뜻하는데 연속 할당 방법에서는 이 Hole들이 여러 곳에 흩어져 있게 된다. 따라서 이를 운영체제가 관리해야 하며 운영체제는 각 프로세스가 a) 할당된 공간과  b) 가용 공간(Hole)에 대한 정보를 저장하고 있어야 할 것이다.

 

그림 7 : Hole 

 

* Dynamic Storage-Allocation Problem *

 

 이 가변 분할 방식에서 생기는 Hole 결정 문제를 Dynamic Storage-Allocation Problem이라고 한다. 지금 들어와야 하는 프로세스 사이즈가 n인데 hole이 여러 개일 때 가장 적절한 hole을 찾는 문제이다.

 

1. First-fit

 Size가 n이상인 hole 중에 처음으로 찾아지는 hole에 집어넣는다.

 

2. Best-fit

 Size가 n이상인 hole 중 가장 작은 hole에 할당을 하는 것이다. 그러나 hole들의 리스트가 크기 순으로 정렬되지 않았다면 모든 hole을 다 탐색해야 하며 많은 수의 아주 작은 hole들이 생성될 수 있다.

 

3. Worst-fit

 Size가 n이상인 hole 중 가장 큰 hole에 할당하며 이 역시 모든 hole을 다 탐색해야 하고, Best-fit과는 반대로 상대적으로 큰 hole이 생성된다.

 

 

* Compaction 

 외부 조각으로 발생하는 Hole들의 발생을 막기 위해 프로세스를 한쪽으로 전부 밀어서 큰 Block을 만드는 방법이다. 그러나 매우 비용이 많이 들며 최소한의 메모리 이동으로 Compaction 하는 방법은 매우 복잡한 문제이다. 또한 Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다(Run time binding).

 

 

---

2. Noncontiguous allocation (불연속 할당)

 

 

 

To be continued.. 

 

본 글들은 이화여대 반효경 교수님 2017학년도 1학기 운영체제 강의를 기반으로 작성됩니다.

링크 : http://www.kocw.net/home/search/kemView.do?kemId=1046323