Address Binding
프로세스의 주소(Address)는 논리적 주소(Logical address)와 물리적 주소(Physical address)로 나뉜다.
- 논리적 주소 == 가상 주소(Virtual address)
CPU가 생성하는 주소
프로세스마다 독립적으로 가지는 주소 공간이기 때문에 프로세스의 내부에서 사용하고, 각 프로세스마다 0부터 시작함!- 물리적 주소
프로세스가 실행되기 위해 실제로 메모리(RAM)에 올라가는 위치
그렇다면,,
Address Binding란?
어떤 프로그램이 메모리의 어느 위치에, 즉 어떤 물리적 주소에 load 될지를 결정하는 과정
→ 이는 binding 하는 시점에 따라 분류됨
Compile Time
프로세스의 물리적 주소가 컴파일 때 정해진다. 프로세스가 메모리의 어느 위치에 들어갈지 미리 알고 있다면 컴파일러가 절대 주소(Absolute address), 즉 고정된 주소를 생성한다. 따라서 만약 위치가 변경된다면 재컴파일을 해주어야 한다.
컴파일 타임 주소 할당은 프로세스 내부에서 사용하는 논리적 주소와 물리적 주소가 동일하다.
컴파일 타임 주소 할당의 문제점은, 주소가 고정되어 있기 때문에 메모리 상에 빈 공간이 많이 발생할 수 있어 비효율적이고, 로드하려는 위치에 이미 다른 프로세스가 존재할 수 있다.
Load Time
프로세스가 메모리의 어느 위치에 들어갈지 미리 알 수 없다면 컴파일러는 Relocatable code를 생성해야 한다. Relocatable code는 메모리의 어느 위치에서나 수행될 수 있는 기계 언어 코드이다.
그리고 Loader가 프로세스를 메모리에 load 하는 시점에 물리적 주소를 결정한다.
따라서 로드 타임 주소 할당은 논리적 주소와 물리적 주소가 다르다.
하지만, 프로세스 내에 메모리를 참조하는 명령어들이 많아서 이들의 주소를 다 바꿔줘야 하기 때문에, 로딩할 때의 시간이 매우 커질 수 있다는 단점이 있다.
따라서 컴파일 타임과 로드 타임 주소 할당은 실제로 잘 쓰이지 않는다.
Execution Time (Run time)
프로세스가 수행이 시작된 이후에 프로세스가 실행될 때 메모리 주소를 바꾸는 방법이다. 즉, Runtime때 물리적 주소가 결정되며 실행 도중에 주소가 바뀔 수 있다. CPU가 주소를 참조할 때마다 address mapping table을 이용하여 binding을 점검한다.
런타임 주소 할당은 MMU(Memory Management Unit)라는 하드웨어 장치를 사용하여 논리적 주소를 물리적 주소로 바꿔준다. 프로세스가 CPU에서 수행되면서 생성해내는 모든 주소값에 대해서 base register의 값을 더해주어 물리적 주소를 생성하는 방식이다. base register는 하나이므로 프로세스끼리 공유한다.
Swapping
메모리는 크기가 크지 않기 때문에 프로세스를 임시로 디스크에 보냈다가 다시 메모리에 로드해야 하는 상황이 생긴다.
이때 디스크로 내보내는 것을 swap out
메모리로 들여보내는 것을 swap in이라고 한다.
일반적으로 중기 스케줄러에 의해 swap out 시킬 프로세스를 선정하며, 우선순위에 따라 어떤 프로세스를 swap in/out 할지 결정한다. 우선순위가 낮은 프로세스를 swap out 시키고, 높은 프로세스를 메모리에 올려놓는 방식이다.
만약 Compile time이나 Load time binding인 경우 원래 메모리 위치로 swap in 해야 하고, Execution time binding인 경우 추후 빈 메모리 영역 아무 곳에나 올릴 수 있다.
swap 하는데 걸리는 시간의 대부분은 디스크 전송 시간이다.
Contiguous Allocation
메모리는 일반적으로 커널 영역과 사용자 프로세스 영역으로 나뉘어서 사용된다.
그중 사용자 프로세스 영역의 할당 방법으로는 Contiguous Allocation(연속적 할당), Noncontiguous Allocation(비연속적 할당)으로 나뉜다.
사용자 프로세스 영역
Contiguous Allocation
말 그대로, 각 프로세스들이 연속적인 메모리 공간을 차지하게 되는 것
각 프로세스를 메모리에 담기 위해 메모리는 미리 공간을 분할해두는데, 고정된 크기로 나누는 고정 분할 방식과 프로세스의 크기를 고려해서 나누는 가변 분할 방식이 있다.
✅ 고정 분할(Fixed partition)
분할의 크기가 모두 동일하거나 혹은 서로 다를 수 있다. 분할 당 하나의 프로세스가 적재되기 때문에 동시에 메모리에 load 되는 프로세스의 수가 고정된다. 또 수행 가능한 프로세스의 최대 크기가 제한된다.
✅ 가변 분할(Variable partition)
프로세스의 크기를 고려해서 할당하기 때문에 분할의 크기나 개수가 동적으로 변한다. 이를 위해서는 기술적인 관리 기법이 필요하다.
Dynamic Storage-Allocation Problem
Contiguous Allocat ion에서 메모리를 분할하는 각 단위는 Block이고, 프로세스가 사용할 수 있는 Block을 Hole이라고 한다.
다양한 크기의 Hole들이 메모리 여러 곳에 흩어져 있고, 프로세스가 도착하면 수용 가능한 Hole을 할당시켜준다.
가변 분할 방식에서 크기가 n인 프로세스가 들어갈 가장 적절한 Hole을 찾는 문제를 Dynamic Storage-Allocation Problem이라고 하는데, 세 종류의 해결법이 있다.
- First-fit
크기가 n 이상인 Hole 중 최초로 발견한 Hole에 할당한다.
- Best-fit
크기가 n 이상인 가장 작은 Hole을 찾아 할당한다. Hole들이 크기순으로 정렬되지 않은 경우 모든 Hole을 탐색해야 한다. 항상 거의 딱 맞는 크기를 할당하기 때문에 할당 후에 아주 작은 Hole들이 많이 생성된다.
- Worst-fit
가장 큰 Hole에 할당한다. 마찬가지로 모든 Hole을 탐색해야 하고, 상대적으로 아주 큰 Hole들이 새로 생성된다.
First-fit과 Best-fit이 Worst-fit에 비해서는 속도나 공간 측면에서 효과적인 것으로 알려져 있으나, 전체적으로 효율이 좋지 않은 편이다.
Fragmentation
프로세스들이 메모리에 적재되고 제거되는 일이 반복되면 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼의 작은 공간들이 늘어나게 되는 현상
외부 단편화(External Fragmentation)와 내부 단편화(Internal Fragmentation)로 나뉜다.
외부 단편화
총공간을 계산했을 때 프로세스가 들어갈 수 있는 메모리가 있음에도 불구하고 공간들이 연속하지 않아 사용할 수 없는 경우
‼️ 외부 단편화 발생 가능
내부 단편화
프로세스가 사용하는 메모리 공간보다 분할된 공간이 더 커서 메모리가 남는 경우
ex. 1000 크기의 분할이 있고 990 크기의 프로세스가 들어갈 때, 10만큼의 공간이 남움
‼️ 외부 단편화와 내부 단편화 모두 발생 가능
해결방법 - Compaction
Compaction(압축)은 프로세스가 사용하는 공간들을 한쪽으로 몰아서 공간을 확보하는 방법
하지만 비용이 매우 많이 드는 작업이므로 효율이 좋지 않다.
Paging
- Noncontiguous Allocation 방식
- 외부 단편화의 압축 작업의 비효율성을 해결하기 위한 방법
- 메모리는 프레임(Frame), 프로세스는 페이지(Page)라 불리는 고정 크기의 블록(Block)으로 분리됨. 블록의 크기는 2의 거듭제곱
한 프로세스가 사용하는 공간은 여러 page로 나뉘어 관리되고, 각각의 page는 순서와 관계없이 메모리의 frame에 mapping 되어 저장된다.
프로세스가 순서대로 메모리에 저장되지 않기 때문에 프로세스를 실행하기 위해선 page가 어느 frame에 들어있는지를 알아야 한다. 이에 대한 정보가 page table이라는 테이블에 저장되어 있고, 이를 사용하여 논리적 주소를 물리적 주소로 변환한다.
장점
- page들이 연속할 필요가 없어 외부 단편화를 해결할 수 있다.
- 할당과 해제가 빠르다.
- swap out이 간단하다.
- 코드를 쉽게 공유할 수 있다(Shared pages). 코드가 pure code라면 공유가 가능하며 read-only로 프로세스 간에 하나의 코드만 메모리에
단점
- 내부 단편화를 해결하지 못한다.
- page table을 저장하기 위한 메모리가 추가로 소모된다.
- page table이 메모리에 상주하기 때문에 메모리에 접근하는 연산은 2번의 메모리 접근이 필요하게 되어 속도가 느리다.
(page table에 접근 + 실제 연산)
➡️ 따라서 속도 향상을 위해 Associative register 혹은 TLB(Translation Look-aside Buffer)라 불리는 고속의 하드웨어 캐시를 사용
CPU에 의해 만들어진 Logical address는 page number와 page offset 두 부분으로 나뉜다.
- page number
page table의 인덱스로써 page table에 접근할 때 사용된다. - page offset
물리적 주소를 얻을 때 사용됨
page table의 base address에 page offset을 더하면 물리적 주소를 구할 수 있음
page table은 프로세스마다 존재하며 메인 메모리에 상주한다. page table이 대부분 매우 크기 때문에 이를 구현하기 위해 비용이 비싼 register를 사용하는 것은 적절하지 않기 때문이다.
➡️ 따라서 page table은 메인 메모리에 저장하고, PTBR(Page-Table Base Register)라는 레지스터가 page table을 가리키도록 한다. 만약 Context Switch가 발생하는 경우 이 레지스터의 내용만 변경하면 된다.
page table의 각 엔트리(Entry)에는 정보를 담고 있는 bit가 포함되어 있다.
- Protection bit : page에 대한 접근 권한 (read / write / read-only)
- Valid-invalid bit : valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음. invalid는 없음(접근 불허)
메모리 할당이 contiguous 한 경우 Limit만 비교해도 메모리를 보호할 수 있었지만, paging은 contiguous하지 않기 때문에 valid-invalid bit을 이용하여 valid면 해당 page에 접근할 수 있도록 한다.
page의 크기가 작아질수록 내부 단편화가 감소하고 필요한 정보만 메모리에 있어서 메모리 이용에서 효율적이지만, page table의 크기가 증가하고 디스크 이동의 효율성이 감소한다. 따라서 요즘은 page의 크기를 키워주는 흐름이다.
Reference
