Operating System 10 - Memory Management 1

 Memory Management
메모리는 byte의 array로 구성되어 있고, 각각의 address를 가지고 있다. CPU는 PC가 가리키고 있는 memory의 instruction을 fetch하여 실행한다.

Terms
Frame : main memory의 fixed length block (하드웨어 적으로 고정된 것)
Page : frame 크기와 동일. secondary에서 사용.
Segment : 위와 달리 요구되는 크기 만큼 다양하게 할당할 수 있다. secondary storage에서 사용.

Requirements
- Relocation : multiprogramming 환경에서는 interleaving을 하며 main memory가 여러 프로세스들에게 공유된다. (swap in, swap out) 따라서 swap 되었을 때 이전에 사용되던 공간이 아니라 새로운 메모리 공간에 할당되도록 재배치를 할 수 있어야 한다.
메모리 할당 공간은 symbolic variable count에 저장되어 있다. 이것을 컴파일러가 적절한 offset을 주고 linker나 loader가 해당 값을 따라 count에서 offset만큼 떨어진 곳에 프로세스를 위치 시킨다.
*relocation 하는 mechanism은 protection과 sharing 역시 서포트 한다.

- Protection : 각 프로세스는 자신의 메모리 영역을 보호받아야 한다. 이는 OS보다 하드웨어적으로 해줘야 한다. (by register) base register와 limit register가 존재하여 해당 프로세스가 사용할 수 있는 메모리 주소의 boundary를 설정해준다. 따라서 각 프로세스는 두 레지스터 사이의 공간만 사용할 수 있다. (base ~ base+limits 사이를 접근 가능)

- Sharing : 같은 프로그램의 여러 프로세스가 있을 때 이를 따로 실행하면 메모리 공간이 낭비된다. 따라서 이 경우, separate copy를 하지 않고 하나의 copy를 참조하도록 하는 것이 좋다. (코드를 작성할 때 library를 include 할 때 각각을 다 따로 만들지 않고, 하나의 장소에서 각각 참조 하면 된다.)

- Logical organization : module 형태로 존재하는 프로그램들을 하드웨어적으로 존재하는 메인 메모리의 선형 메모리 공간에 잘 배치해야 한다. 이는 segmentation으로 가능하다.

- Physical Organization : 일반적으로 메모리는 main과 secondary의 두 계층으로 구성된다. 그러나 현대 메모리 레이아웃에서는 프로그래머가 메모리의 정확한 위치를 알 수 없다. (가상 메모리 등이 사용되므로) 따라서 이는 OS가 알아서 처리해준다.
*과거에는 프로그래머가 일정 메모리 공간을 할당 받아 프로그램을 넣었다 뺏다 하며 실행할 수 있었다. (Overlaying)

Memory partitioning
실제 사용되는 virtual memory 기법보다 간단한 방법.

- Fixed Partitioning
메인메모리를 일정한 크기 혹은 가변 크기로 분리하고, 각 프로세스는 자신과 같거나 큰 partition에 load될 수 있다.

같은 크기로 나누면 쉽고 간단하며 overhead가 적다. 그러나 프로그램이 너무 클 경우 overlay를 사용하여 해결해야 한다. (share로 지정하고 swap)
반대로 프로그램이 partition 크기보다 작다면, 할당 받았음에도 사용되지 않고 낭비되는 공간이 발생한다. 이를 내부 단편화라 한다. 또한 전체 메모리를 일정한 크기로 나누므로 동시에 수행될 수 있는 프로세스의 최대 개수가 정해져있다.

가변 크기로 나눈다면 프로세스 크기와 가장 비슷한 partition을 할당하여 내부 단편화를 최소화 하고 overlay를 적용하지 않아도 된다는 장점이 있다.
각 크기 partition별로 큐가 존재하여 내부 단편화를 최소화 할 수 있는 곳에서 기다리게 된다.  그러나 이방법을 사용하면 전체적인 시스템에서 크기가 작은 것이 더 많으므로 큰 곳이 비었음에도 낭비될 수 있다. 따라서 single queue를 두어 가용 가능한 것 중에 가장 작은 것을 할당하는 방식으로 개선될 수 있다.
또한 앞서와 마찬가지로 동시에 수행될 수 있는 전체 프로세스의 수는 고정되어 있으며 크기가 작은 프로세스가 많아질 수록 내부 단편화가 심해질 수 있다.

- Dynamic partitioning
내부 단편화의 발생을 막기 위해 각 프로세스가 필요한 만큼 계산하여 할당해준다. 그러나 외부 단편화가 발생하게 된다. 이는 사용 가능한 메모리의 주소가 불연속적으로 쪼개져 빈 공간은 충분하지만 연속적이지 않아 프로세스를 실행할 수 없게 되는 상황을 의미한다. 외부 단편화된 공간들을 활용하기 위해서는 compaction(압축)을 사용하여 실행되고 있는 프로세스를 밀어서 붙이는 방식을 사용한다. 이 과정을 실행하면 실행이 멈춰지고 오버헤드가 발생한다.

First-fit algorithm : 자신이 들어갈 수 있는 공간을 처음부터 스캔하고, 처음 발견한 곳에 바로 들어감. 가장 빠르고 성능이 좋다. 이 방법은 메모리 주소가 높은 곳에 외부 단편화가 심해지고 낮은 메모리에서는 큰 공간이 남을 수 있다.
Next-fit algorithm : 이 방법은 마지막에 할당된 곳 부터 아래로 스캔하여 빈공간에 놓는 방식이다. 그러나 이 방법은 오히려 전체에서 외부 단편화가 심해지므로 압축의 비용이 더 커진다.
Best-fit algorithm : 전체를 다 스캔하여 자신과 가장 비슷한 공간에 들어가는 것이다. 이는 반드시 최적이므로 외부 단편화를 줄일 수 있다. 그러나 전체 메모리 공간을 스캔해야 하므로 시간이 더 오래 걸린다.
Worst-fit algorithm : 위와 반대로 전체를 다 스캔한 후 가장 큰 공간에 들어가는 것이다. 일반적으로 가장 성능이 좋지 않다.

정리하면 fixed는 내부 단편화가 발생, dynamic은 외부 단편화가 발생.

Buddy system(UNIX에서 사용됨)
2의 n승으로 메모리 공간을 나누어 할당해주고, 해당 프로세스가 다 사용하고 반납할 경우, 빈 공간을 다시 합쳐 큰 메모리 공간으로 가지고 있는 방법이다. (항상 같은 사이즈의 버디를 가지고, 같은 사이즈인 버디 끼리만 합칠 수 있다)
예를 들어 100k를 요청할 경우, 1M가 있다면, 512, 256, 128, 64까지 쪼개고, 64<100<128이므로 128 단위로 쪼개어 해당 파트를 할당해준다. 그리고 다 사용되고 반납된다면, 해당 메모리를 다시 합쳐 256, 512, 1024로 가지고 있는 방법이다.
이는 외부 단편화를 최소화할 수 있다.

Paging
메인 메모리가 같은 사이즈의 프레임으로 나누어져 있다. 그리고 각 프로세스도 같은 사이즈의 페이지로 나누어 놓는다. 따라서 각 프로세스마다 필요한 페이지 만큼 사용할 수 있는 공간에 올리게 된다. 이 경우 연속적일 필요가 없으므로 외부 단편화가 없어진다. (불연속적인 공간에 해당 프로세스의 페이지를 모두 로드 하여 사용 -> page table에서 찾으면 된다) 그러나 모든 프로세스가 반드시 frame의 n배의 크기를 가지지 않으므로 마지막 페이지에서 약간의 내부 단편화가 남아있게 된다. 그렇지만 페이지 단위가 앞서 메모리 분리한 단위보다는 매우 작기 때문에(4kb 등) 내부 단편화도 최소화 되고 가장 효율적이다.

Page table
각 프로세스의 페이지들이 실제 메인 메모리의 어느 물리적 주소에 있는지를 저장하고 있는 표. 따라서 logical address(Page number, offset)을 physical address(frame number, offset)으로 번역하는 역할을 한다.

Segmentation
프로그램을 구성하고 있는 모듈 단위로 분리한다. 그리고 각 부분을 segmentation이라 한다. 이는 dynamic partitioning과 비슷하며 따라서 이전과 달리 내부 단편화는 발생하지 않지만(각 모듈 크기로 분리하므로) 외부 단편화가 발생한다.
이 방법도 segment table을 보고 logical address를 physical address로 변환하여 찾아간다.

swapping
page 단위로 메인메모리에 존재하는 프로세스의 부분들이 secondary storage에 swap in / out 된다.