본 게시글은 이화여대 반효경 교수님의 2014년 KOCW <운영체제> 강의(http://www.kocw.net/home/search/kemView.do?kemId=1046323)를 수강한 후 정리한 것임을 밝힙니다.
Logical Address(논리적 주소) vs. Physical Address(물리적 주소)
논리 주소는 가상 주소(virtual address)라고도 하며, 프로세스마다 독립적으로 가지는 주소 공간을 말한다.
논리 주소가 필요한 이유는 각 프로세스의 독립성을 보장하고 안전하게 메모리를 관리하기 위해서이다.
만약 프로세스를 항상 물리 주소(실제 메모리에 올라간 위치)만으로 다룬다면,
멀티 프로세스 환경에서 동시에 돌아가고 있는 수많은 프로세스에 대해 물리 주소를 할당하기 어려워질 뿐만 아니라
메모리 주소가 겹치면 프로그램 정보가 훼손되는 심각한 에러가 발생할 수도 있기 때문이다.
다시 말해서 논리 주소는 운영체제가 프로세스를 효과적으로 관리하기 위한 하나의 추상화 접근 방식이다.
이제 논리 주소의 특징을 하나씩 살펴보자.
논리 주소는 각 프로세스마다 0번지부터 시작한다.
굳이 비유하자면, 우리가 할 일(=프로세스)마다 메모를 하기 위해 텍스트 파일(=논리 주소)을 만들면각 텍스트 파일의 내용은 당연히 1번째 줄부터 시작하는 것과 비슷한 이치다.
CPU 입장에서 요구하는 주소는 physical address가 아니라 logical address이다.
CPU는 물리적인 하드웨어이니까 프로세스의 physical address를 요구할 것 같지만,
사실 CPU가 바라보는 주소는 모두 논리 주소이다.
여기서 이제 의문이 들 수 있다.
어쨌든 프로세스가 저장된 실제 메모리 위치(=물리 메모리)가 있을 텐데,
어떻게 하면 논리 메모리 주소를 가지고 올바른 실제 메모리 위치에 접근할 수 있을까?
Address Binding(주소 바인딩)
프로세스가 가지고 있는 논리 주소를 물리 주소(실제 메모리에 올라간 위치)로 적절히 매핑하는 걸 주소 바인딩이라고 한다.
주소 변환의 흐름은 symoblic address -> logical address -> physical address으로 나눌 수 있다.
첫번째 symbolic(=기호) address는 변수명이라고 생각하면 된다.
우리가 흔히 보는 변수 a, b, c, tmp, num과 같이 문자를 사용하는 게 다 symbolic address를 말한다.
반면에 논리 주소는 몽땅 숫자로 이루어져 있다.
주소 바인딩은 진행 시점을 기준으로 또 세 가지로 나눌 수 있다.
- 프로그램을 컴파일할 때 => Compile Time Binding
- 프로그램을 실행 시작할 때 => Load Time Binding
- 프로그램을 실행하는 도중 => Run Time Binding
Compile Time Binding
- 물리 메모리 주소 값을 이미 컴파일할 때 결정한다.
- 그렇기 때문에 메모리의 시작 위치를 변경하면 다시 컴파일해야 한다.
- Compile time binding 방식으로 동작하는 컴파일러는 절대 코드(absolute code)를 생성한다.
절대 코드란 한번 컴파일하고 나면 바꿀 수 없는 코드를 말한다.
그렇기 때문에 컴파일하고 나서 바인딩할 물리 주소를 바꾸고 싶다면 아예 처음부터 다시 컴파일을 해야 한다.
이와 반대되는 개념이 relocatable code이다.
Load Time Binding
- 실행 시작할 때 주소 변환이 이루어지면 load time binding이라고 한다.
- Loader의 책임 하에 물리 메모리 주소를 부여한다.
- 컴파일러가 재배치 가능한 코드(relocatable code)를 생성한 경우에 가능하다.
Execution Time Binding (=Run Time Binding)
- 프로그램 실행 시작 이후에도 프로세스의 메모리 상 위치를 옮길 수 있다.
- CPU가 주소를 참조할 때마다 binding을 점검한다. (address mapping table)
- 하드웨어의 지원이 필요하다. (예를 들어 base and limit registers, MMU 등)
오늘날의 컴퓨터 시스템은 런타임 바인딩 방식을 사용한다.
각 주소 바인딩 방식을 그림과 함께 비교해보자
그림 맨 위 그림은 compile time binding을 의미한다. 컴파일 시점에 이미 물리적인 주소를 결정짓는다.
그림을 보면 항상 0번째 물리 주소에 프로그램을 할당하는 걸 볼 수 있다.
당연히 오늘날 컴퓨터 시스템에서는 compile time binding 방식을 사용하지 않는다.
너무 비효율적이기 때문이다. 하지만 컴퓨터가 등장하던 초기에는 시스템에 프로그램이 단 하나만 존재했기 때문에 이 방식이 유효했다.
두번째는 실행할 때 주소 변환을 하는 방식(load time binding)이다.
이번엔 물리 주소가 0번이 아니라 500번이다.
컴퓨터 입장에선 '실행하려고 보니 물리 주소에 500번부터 비어있네? 그럼 여기에 주소를 할당해야겠다'
하고 좀 더 유연하게 대처할 수 있다.
세번째 방식은 run time binding으로, 실행할 때 주소 변환을 하는 건 load time binding과 동일하다.
그런데 이 주소가 실행 도중에 바뀔 수 있고, run time binding은 실행 도중에도 주소 변환을 지원한다.
그림을 보면 실행 시작할 때 물리 메모리 주소 300번에 바인딩을 했는데 실행 중에 물리 메모리 주소 700번으로 옮겼다.
당연히 오늘날 시스템은 run time binding을 지원한다.
CPU는 메모리 주소를 요청할 때마다 주소 바인딩을 점검해야 한다.
그래서 별도의 하드웨어 지원이 필요한데 이때 관여하는 하드웨어가 MMU이다.
MMU, 주소 변환용 하드웨어
logical address를 physical address로 매핑해주는 하드웨어(소프트웨어 아님)를 말한다.
MMU scheme(작동 방식)은 간단하다.
- CPU가 사용자 프로세스를 수행하면서 생성해내는 주소 값을 받는다.
- 이 주소 값에 base register(=relocation register)의 값을 더한다.
- CPU가 요청한다: "논리 주소 346번지에 있는 메모리를 가져오세요."
- MMU가 register 두 개로 주소 변환을 한다. 한 레지스터는 relocation register(=base register), 다른 하나는 limit register이다.
- 좌측 하단은 프로그램 중 프로세스 p1이 CPU에서 실행되고 있는 상황을 나타낸 것이다.
프로그램 시작 부분은 논리 주소 기준으로 0번째 번지에 저장되어 있다.
그리고 (프로그램의 일부인) 현재 프로세스 p1은 0번으로부터 346만큼 떨어진 346번째 번지에 저장되어 있다.
그러면 프로세스 p1의 물리 주소를 구하려면,
프로그램의 물리 주소 시작 위치(14000번지) + 현재 프로세스의 논리 주소(346번지)
를 해주면 된다.
Limit Register의 역할
모든 프로그램마다 할당할 수 있는 메모리의 최대 크기가 있다.
이 예시에서는 3000이라고 주어져 있다.
Limit register는 해당 프로그램이 참조할 수 있는 메모리의 최대 크기를 저장해서
할당된 영역보다 더 큰 메모리 주소를 접근하는 불상사가 일어나지 않게 한다.
어떤 악의적인 프로그램이 있다고 상상해보자.
분명 프로그램의 최대 크기는 3000인데, 논리 주소에 4000을 요구해서 프로그램에 할당된 메모리의 바깥 영역을 접근하려고 한다.
이때 잘못된 메모리로 접근했다고 기준을 제시하는 게 limit register의 역할이다.
방금 설명한 예시처럼 CPU가 요청한 logical address(=4000)가
limit register에 저장된 값(프로그램의 최대 크기, 3000)보다 작지 않으면(no) trap에 걸리게 된다.
그래서 CPU 제어권이 프로그램에서 OS에 넘어가게 되고, OS는 trap에 왜 걸렸는지 따져보게 된다.
그럼 OS는 addressing error가 발생했다는 걸 알고 프로그램을 '응징'(종료)할 것이다.
Dynamic Loading(동적 로딩)
직역하면 프로그램을 메모리에 동적으로 올린다는 뜻이다.
그때 그때 필요할 때만, 즉 해당 루틴이 호출될 때마다 메모리에 올린다.
프로세스 전체를 메모리에 미리 다 올리는 게 아니다.
static loading보다는 효율적이니 memory utilization을 향상시킨다.
프로그램 중에서 상당 부분은 거의 사용되지 않는 오류 처리 루틴이 있는 반면, 프로그램 실행에 자주 사용되는 부분은 한정적이다.
그래서 동적 로딩은 자주 사용되는 부분만 필요할 때마다 올려서 효율성을 높인다.
참고로 Paging 기법과 dynamic loading은 엄밀히 말해 다르다.
Paging 기법은 OS가 관리하고, dynamic loading은 프로그래머가 구현한다.
운영체제의 특별한 지원 없이 프로그램 자체에서 구현이 가능하다.
프로그래머가 언제 loading할지 직접 구현할 수 있다는 뜻이다.
그렇다고 프로그래머가 일일이 수작업으로 구현한다는 건 아니고,
dynamic loading 작업을 편리하게 해주는 라이브러리가 있다.
Overlay
프로세스의 부분 중 실제 필요한 부분만 메모리에 올린다는 뜻이다.
그렇다면 dynamic loading과 overlay는 무슨 차이가 있는가?
초창기 컴퓨터 시스템은 메모리가 워낙 작았기 때문에 프로그램 하나 전체를 메모리에 올리는 것도 힘들었다.
그렇기 때문에 프로그래머가 프로그램을 쪼개서 메모리에 그때그때마다 올릴 수 있도록 수작업 코딩을 했다.
그래서 "Manual(=수동, 수작업) Overlay"라고도 하는 것이다.
Overlay는 라이브러리를 통해 진행하는 dynamic loading과는 다르다고 할 수 있다.
Swapping
프로세스를 일시적으로 메모리에서 backing store(하드 디스크)로 쫓아내는 걸 swapping이라고 한다.
Backing store(=swap area)은 디스크에 해당한다.
많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장공간이어야 한다.
swap in / swap out: 일반적으로 중기 스케줄러(swapper)에 의해 swap out할 프로세스를 선정한다.
그렇다면 어떤 프로세스를 쫓아내는 걸까?
우선순위를 정해서 우선순위가 낮은 프로세스부터 swap out하면 된다.
이게 priority-based CPU scheduling algorithm이다.
반면에 우선순위가 높은 프로세스는 메모리에 올려놓아야(swap in) 한다.
그렇다면 여기서 말하는 우선순위는 어떻게 정하는 걸까? 이 내용은 강의에서 본격적으로 다루지 않아서 다음에 차차 설명하게 될 것 같다.
Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 한다.
하지만 swap in할 시점엔 메모리 상황이 바뀌어있을 수도 있으니
원래 위치를 고수하기보다는 그때 그때마다 비어있는 자리로 가는 게 더 효율적이지 않을까?
그래서 run time (execution time) binding이 더 효율적이다.
swap time은 transfer time(데이터 전송량)에 비례한다
swap time은 많은 양을 한꺼번에 이동시키는 것이기 때문에 파일 입출력보다 훨씬 오래 걸린다.
하드 디스크에서 뒤에서 더 자세하게 다루겠지만,
하드 디스크에서 메모리를 읽어오는 시간은 대부분 seek time(헤드가 목표 위치로 이동하는 시간)이 차지한다.
반면에 transfer time은 seek time에 비해 미미하다.
하지만 swap은 훨씬 큰 용량을 다루기 때문에 transfer time(데이터를 전송하는 시간)이 더 영향을 미치게 된다.
그래서 swap time은 대부분 디스크에 접근하는 시간, transfer time, 즉 swap되는 양에 비례한다고 볼 수 있다.
Dynamic Linking
Linking은 컴파일된 파일들을 묶어서 하나의 실행 파일로 만드는 작업을 의미한다.
라이브러리나 헤더 파일을 내 소스코드 안에 포함을 시키는 것이다.
Static Linking
라이브러리를 프로그램의 실행 파일 코드에 포함하기 때문에 실행 파일의 크기가 커진다.
동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비가 발생한다.
예를 들어 printf 함수를 사용해서 프로그램을 짰는데 이런 프로그램을 한 100개쯤 작성했다고 하자.
같은 함수이지만 별개의 프로그램이기 때문에 printf 함수의 라이브러리 코드 복사본을 100개씩 따로 만들어두어야 한다.
그러니까 메모리 낭비가 발생할 수밖에 없다.
Dynamic Linking
Linking을 실행 시간(execution)까지 미루는 기법이다.
컴파일할 때가 아니라, 프로그램을 실행하는 시점에 라이브러리를 '연결'한다.
그럼 어떻게 라이브러리를 연결할까?
우선 내 프로그램 실행 파일 코드에는 라이브러리가 직접 들어가있지 않다.
대신 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다.
stub은 라이브러리를 가리키는 일종의 "포인터"이기 때문에 라이브러리 자체는 내 코드에 포함을 시키지 않는다.
실행 시점에 라이브러리를 찾아서 필요하면 디스크에서 읽어와 메모리에 올리고,
또는 이미 메모리에 있으면 그 루틴의 주소로 가면 된다.
다시 100개의 프로그램을 실행했다고 가정해보자.
printf 함수의 라이브러리가 메모리에 이미 올라와있으면
100개의 프로그램이 이 메모리에 참조해서 가져다 쓰면 되니까 printf의 라이브러리 복사본을 100개씩 따로 만들 필요가 없다.
즉 메모리를 공유하는 개념이다.
그래서 dynamic linking을 가능하게 하는 라이브러리를 shared library라고도 부른다.
리눅스 같은 환경에는 shared object, windows에서는 DLL이라고 한다.
물리 메모리의 할당
물리적인 메모리 영역의 낮은 부분에는 항상 OS kernel이 있고, 그 위에 사용자 프로세스 영역이 있다.
여기선 사용자 프로세스 영역을 관리(메모리 할당)하는 법을 배운다.
크게 두 가지로 나뉜다.
- Contiguous allocation: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
- Non-contiguous allocation: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있다.
2번은 프로그램 일부를 쪼개서 메모리에 올리는 방식이다. 당연히 오늘날 기법은 1번이 아니라 2번에 해당한다.
Contiguous Allocation
연속 할당은 또 두 가지 방식으로 나뉜다. 고정 분할과 가변 분할 방식이다.
고정 분할 방식: 그림 상에서 이미 분할(fragmentation)을 1,2,3,4로 나누었다.
프로그램 B의 크기는 분명 분할 2보다 크다.
따라서 분할 2에 들어갈 수 없고 분할 3에 들어가야 한다.
이때 외부 조각, 내부 조각이라는 말이 무슨 뜻인지 알아보자.
1) 외부 조각(external fragmentation)은 프로그램 크기보다 분할의 크기가 작은 경우 발생한다. 프로그램이 올라갈 수 없는 작은 분할이다. 그렇기 때문에 아무 프로그램에도 배정되지 않은 빈 곳, 낭비하는 분할이 된다.
2) 내부 조각(internal fragmentation)은 프로그램 크기보다 분할의 크기가 큰 경우에 발생한다. 분할 내부에 있는 조각이어서 내부 조각이다. 분할 자체가 프로그램에 배정되는 것이기 때문에 내부 조각도 특정 프로그램에 배정되었다고 할 수는 있지만 사용하지 않는 공간인 건 외부 조각과 마찬가지다.
근데 사실 엄밀히 구분하기는 어렵다. 그때그때 상황을 해석할 때마다 외부 조각인지, 내부 조각인지가 달라지기 때문이다.
애초에 고정 분할 방식에선 이미 분할 크기를 프로그램 크기에 상관없이 고정하고 시작하기 때문에 이런 문제가 발생한다.
외부 조각이나 내부 조각이 생기는 이유는 결국 분할의 크기가 프로그램의 크기와 맞지 않기 때문이다.
그럼 여기서 드는 생각. 처음부터 프로그램의 크기에 맞게 분할을 할당하면 되지 않을까?
그래서 등장한 게 가변 분할 방식이다.
가변 분할 방식
다시 그림으로 돌아가서 해석해보자.
- 프로그램 A, B, C를 차곡차곡 메모리에 올려놓는다.
- 실행 순서는 A -> B -> C이다.
- 프로그램 D도 있는데, D는 B가 끝나야만 수행이 된다.
- 프로그램 B가 종료되면 B가 있던 메모리 공간은 비게 된다.
- B가 종료되었으니 다음에 프로그램 D가 실행이 되어야 한다. 그러나 B가 있던 공간에 D를 올릴 수 없다. 프로그램 D의 크기가 B의 공간보다 크기 때문
- 따라서 B가 차지하던 메모리 공간은 외부 조각이 된다.
가변분할 방식에 대해 다시 한번 정리해보면,
- 프로그램의 크기를 고려해서 할당한다.
- 분할의 크기, 개수가 동적으로 변한다.
- 기술적 관리 기법이 필요하다.
- External fragmentation이 발생한다.
Hole
Hole이란 비어있는 메모리 공간, 즉 (아직 사용하지 않아서) 사용이 가능한 메모리 공간이다.
다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있다.
프로세스가 메모리에 도착하면 수용 가능한 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보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려져 있다. (실험적인 결과)
Compaction
hole들을 한 군데로 밀어넣어서 큰 hole로 만드는 것.
사용 중인 메모리 영역을 한 군데로 몰고, hole들을 다른 한 곳으로 몰아 큰 block을 만드는 방법이다.
근데 메모리를 건드리는 것이기 때문에 그렇게 호락호락하지 않다.
비용이 매우 많이 든다.
또 메모리 영역을 한 군데로 몰아넣는다는 건, 프로그램 하나만을 건드리는 게 아니라 여러 개를 고려해야 한다는 뜻이다.
최소한의 메모리 이동으로 compaction하는 방법이 존재하지만 이것 또한 매우 복잡한 문제다.
Compaction은, 프로세스 주소를 실행 시간에 동적으로 재배치할 수 있을 때만 수행할 수 있다.
그러나 오늘날 사용하는 컴퓨터 시스템은 다 noncontiguous allocation(불연속 할당) 방식을 쓴다.
Non-contiguous allocation
Paging
Paging이란 프로그램을 구성하는 주소 공간을 page라는 고정된 크기의 단위로 잘라서 loading하는 방식을 말한다.
Paging 기법을 쓰면 hole들의 크기가 균일하지 않아서 어디에 집어넣을지,
hole들을 어떻게 하면 한 군데로 뭉쳐넣을지 등등의 문제에 대해 고민할 필요가 없어진다.
왜냐면 어차피 물리적인 메모리에서 비어있는 위치가 있다면
page frame만큼 비어있기 때문에 어떤 프로그램의 page든 그 비어있는 위치에 올릴 수 있기 때문이다.
대신 불연속 할당 방식에선 주소 변환 과정이 복잡해진다. 주소 변환을 page별로 수행해야 한다.
페이징 기법에 대해 다시 정리해보자.
- Process의 virtual memory를 동일한 사이즈의 page라는 단위로 나눈다.
- Virtual memory의 내용이 page 단위로 불연속적(noncontiguous)으로 저장된다.
- 일부는 backing storage에, 일부는 physical memory에 저장된다.
- Physical memory를 동일한 크기의 frame으로 나눈다.
- Logical memory를 동일한 크기의 page로 나눈다. (frame과 같은 크기)
- 모든 가용 frame들을 관리한다.
- Page table을 사용해서 logical address를 physical address로 변환한다.
- External fragmentation이 발생하지 않는다.
- Internal fragmentation이 발생할 수 있다.
마지막에 paging에서도 내부 조각(internal fragmentation)이 발생할 수 있는 이유는 왜일까?
프로그램의 크기가 반드시 page의 배수 단위일 이유가 없기 때문이다.
page 안에 포함되지만 프로그램이 사용하지 않는 빈 메모리 공간이 발생할 수 있다.
Segmentation
Page처럼 고정된 크기의 단위로 자르는 게 아니라 의미있는 부분(코드의 함수별로 자르거나, 데이터/코드/스택으로 구분해서 등등)
으로 자르는 것을 말한다.
이 부분은 다음에 좀 더 보충 설명을 해야 할 것 같다.
