크게 3가지 Contiguous allocation, Discontiguous allocation, Virtual memory로 나뉘는 메모리 관리기법에 대해서 알아보자.
1. Contiguous Memory Allocation
실행파일을 메모리에 가져갈때 처음부터 끝까지 전체를 메모리에 연속으로 배치시켜두고 실행시키는 기법이다.
메모리 관리를 위해 다음 3가지를 신경써야한다.
- 메모리에 로딩되는 프로세스의 개수 : multiprogramming degree (#P's in the system or #P's memory allocated)에 영향을 미친다.
- 각 프로세스에게 메모리공간을 얼마나 할당할 지
- 메모리 분할 방식
- FPM (fixed partition multiprogramming)
- VPM (variable partition multiprogramming)
Uniprogramming
밑의 그림처럼 메모리에 단 1개의 프로세스만 있는 경우다. 메모리 관리가 간단하지만 몇가지 이슈가 있다.
Issue-1 : Program size > memory-size
이런 경우 프로그램을 mutual exclusive하게 여러개의 section으로 분리해서 로드해야한다.Issue-2 : Kernel protection
위 그림에서 User program이 커널영역에 접근할 수 없게 해야한다. 커널영역은 반드시 system call로 접근해야하기 떄문에,boundary register로 접근을 막는다.Issue-3
프로세스가 하나기 때문에 그 프로세스가 사용하고 있지 않은 자원은 놀고 있는 상태이기 떄문에, resource utilization도 낮고 system performance도 좋지않다.
이를 해결하기 위해서 Multiprogramming 기법인 FPM, VPM을 사용해야한다.
FPM
메모리 공간을 여러개의 고정된 파티션으로 분할한다.
-
한 프로세스는 하나의 파티션을 사용할 수 있다.
-
한 파티션에는 하나의 프로세스에 의해서만 사용될 수 있다.
-
partition의 개수 == maximum multiprogramming degree
이렇게 파티션이 분할되고, 파티션의 크기나 위치는 변하지 않는다. 즉 각 파티션에 대한 정보를 저장해야하고, 다음과 같이 data structure로 정보를 저장해둔다.
만약 partitionB에 있는 프로세스가 swap out된 후 다시 partition B로 돌아오려는 상황을 가정해보자. 나가 있는 사이에 다른 프로세스가 partitionB에 들어와있을 수 있다. 그럼 다른 partition으로 들어가야하고, partition에 다시 로드 될때 시작 주소가 바뀌어야만 하기 때문에 load-time, run-time binding기법을 사용해야만 한다. -
Protection method 1
프로세스가 커널에 접근하는 것도 막아야하지만, 다른 파티션에 접근하는 것도 막아야한다.
partition마다 boundary register를 둬서 확인한다. -
Protection method 2
run-time binding의 경우,
프로세스의 크기 정보를 담고 있는 Limit register와 Relocation register를 확인해 다른 파티션의 접근을 막는다.
FPM기법은 storage를 낭비한다.
- Internal fragmentation : 한 파티션엔 한 프로세스만 들어갈 수 있기 때문에, 프로세스가 파티션 크기보다 작으면 남는 공간이 발생한다.
- External fragmentation : 큰 크기의 프로세스가 들어오고싶은데 작은 파티션만 남아있을 때, 프로세스가 들어오지 못해서 통째로 그 파티션들이 놀게된다.
VPM
partition의 상태가 계속 바뀌는 기법. 처음엔 메모리를 single large block으로 만들어놓고 프로세스가 들어가고 나갈때 dynamic하게 파티션을 바꾼다. internal fragmentation을 없애주고, 계속 살펴보고 있는 contiguous allocation이다.
바로 예제를 보자.
초기 메모리 space는 120MB이고, (a) -> (h) 순서로 프로세스가 로딩되는 예시다.
A가 들어오면서 파티션이 두 개로 늘어났다.
D프로세스까지 차곡차곡 들어온 후 B가 나가게 되면, 해당 파티션에서 그냥 프로세스를 지워준다.
그 다음 E는 10MB자리는 용량이 부족해 들어올 수 없고, 45MB인 5번 파티션에 들어오게 된다. 이렇게 프로세스크기만큼 동적으로 메모리 사이즈를 할당받기 때문에 internal fragmentation을 예방할 수 있다.
하지만 여기서 E의 크기가 5MB라면 2번 파티션에 들어가야 할까 5번 파티션에 들어가야 할까? 이걸 결정하기 위해 VPM기법은 4가지의 placements strategies를 사용한다.
Placement strategies
비어있는 파티션을 찾는 순서를 결정하는 방식에따라 나뉜다.
- First-Fit
- 첫 파티션부터 순서대로 찾는다.
- Simple and low overhead
- Best-Fit
- 비어있는 파티션을 모두 찾은 후 들어갈 수 있는 제일 작은 파티션을 찾는다.
- Long search time
- 작은 빈 공간이 많이 생기기 떄문에 external fragmentation이 발생한다.
- Worst-Fit
- best-fit의 반대로 파티션을 모두 찾은 후 제일 큰 곳에 넣는 방법이다.
- Next-fit
- first-fit과 비슷하게 search하지만, 직전 search가 끝난 지점부터 각 search를 시작한다.
- Low overhead
정답은 없지만, 가급적 빠른시간에 검색이 되고 합당한 결과를 주는 First-Fit, Next-Fit이 좋은 선택일 수 있다.
Coalescing holes
두 개의 free partition을 합쳐주는 것으로 간단한 작업으로, overhead도 별로 발생하지 않는다. 테이블 조작만으로 가능하기 때문에 당연히 해야하는 작업이다.
Storage compaction
흩어져있는 free partition을 모아서 합쳐준다. partition 위치를 이동시켜야 하기때문에 overhead가 크게 발생한다.
2. Discontiguous Memory Allocation
프로세스이미지를 일단 조각낸 후 모든 조각들이 메모리에 흩어져서 배치하는 기법이다.
Paging
한 프로세스가 배치된 후의 physical address가 noncontiguous해도 상관 없는 기법으로, hardware와 OS가 closely integrate해서 구현된다.
logical image가 메모리 상에 어디에 실제로 배치됐는지 모르기 떄문에 Page table을 통해 mapping해준다.
- Page : 같은 크기로 logical memory를 단위다. 보통 4KB ~ 8KB.
- Frames (page frames) : 실제로 배치될 phycial memory를 고정 사이즈로 나눈 단위.
- Logical address
- Address mapping
- Logical address -> physical address
- Hidden from the user and controlled by the OS
- 각 프로세스마다 page table 사용
- Page table
- 전용 CPU register를 사용하거나
- 빠르게 search할 수 있는 기억장치인 TLB에 저장한다.
CPU가 2번page의 808 offset에 접근하고 싶다고 요청하면, page table을 참조해 physical memory에는 f번 frame에 있다는 것을 알게된다. 여기에 offset을 합쳐 physical memory를 확인하면 원하는 데이터에 접근할 수 있다.
이런 과정을 통해 메모리가 할당되기 때문에 run-time binding을 해야한다.
Segmentation
Paging과는 다르게 text,data,heap,stack등 logical하게 나누기 때문에 조각들의 크기가 다르다.
paging의 page table과 비슷하게 segmentation은 segment table을 이용해 mapping한다.
paging과 비슷하지만 segmentation의 크기인 limit 값보다 offset인 d가 더 크면 segment overflow를 발생시킨다.
Summary
Contiguous memory allocation
- Uniprogramming
- Multiprogramming
- FPM
- VPM
Discontiguous memory allocation
- Paging
- Segmentation
Contiguous memory allocation, Discontiguous memory allocation에 대해서 알아봤다.
