[운영체제] 메모리 관리 & 가상 메모리

Q) 연속할당과 불연속할당의 차이를 설명해주세요.
A) 메모리의 낮은 주소 영역엔 커널이 상주해있고 메모리의 높은 주소 영역엔 사용자 프로그램이 올라가게 됩니다. 이때 사용자 프로그램을 할당하는 방식에 따라 연속할당과 불연속할당으로 나눌 수 있습니다.
연속할당은 다시 고정 분할 방식과 가변 분할 방식으로 나뉩니다. 고정 분할 방식은 물리적메모리를 미리 몇 개의 분할로 나누어 그 곳에 프로그램을 적재하는 방식입니다. 이 방법은 내부, 외부 조각이 모두 발생할 수 있습니다. 가변 분할 방식은 프로그램 크기를 고려하여 분할의 크기와 개수가 동적으로 변하는 방식입니다. 이 방법은 외부조각이 발생할 수 있으며 프로그램을 어느 홀에 적재시킬지 결정하는 문제가 추가로 발생합니다.
불연속할당은 하나의 프로세스를 여러 물리적 메모리에 나누어 적재하는 방법이며 페이징, 세그먼테이션, 페이지드 세그먼테이션 기법 등이 있습니다.


Q) 페이징 기법은 무엇인가요?
A) 프로그램을 동일 크기의 페이지 단위로 나누고 물리적 메모리도 동일 크기의 프레임으로 나눈뒤 이 곳에 페이지를 적재합니다. 페이징 기법의 주소 변환에는 페이징 테이블이 사용됩니다. 페이징 테이블은 물리적 메모리에 위치해있으며 테이블에는 페이지 번호에 따른 물리적 주소의 시작 위치가 담겨져있습니다. 그래서 CPU는 페이지 번호와 페이지 오프셋을 사용하여 물리적 주소의 위치를 알아냅니다. 이때 속도 향상을 위해서 TLB라는 하드웨어를 활용하기도 합니다.
페이징 기법에서는 내부 조각 문제가 발생할 수 있습니다.
+) 페이지 테이블의 모든 항목을 고르게 사용하는 것이 아니기 때문에 페이지 테이블을 여러 단계로 나누어 사용하기도 합니다. 이때 외부 페이지테이블은 전체 페이지 개수만큼 만들어지지만 실제로 잘 사용하지 않는 주소에 대해서는 내부 페이지테이블을 만들어두지 않고 비워둠으로써 공간적 이득을 볼 수 있습니다.


Q) 세그먼테이션 기법은 어떻게 되나요?
A) 프로그램을 의미 단위의 세그먼트로 나눕니다. 주소 변환 기법은 페이징 기법과 유사하나 세그먼테이션 기법의 경우 세그먼트 크기가 각각 다르기 때문에 세그먼트 테이블에는 세그먼트 번호에 따른 리미트값과 베이스 정보가 담겨져 있다. 이때 오프셋이 리미트 값보다 작은 지를 확인해주어야 하며, 확인 이후 베이스 값과 오프셋 값을 사용하여 물리적 주소의 위치를 알아냅니다.
세그먼테이션 기법은 외부조각 문제가 발생할 수 있습니다.
+) 페이징 기법에서는 물리적 주소를 찾아갈 때 프레임 번호를 던져주면 되지만 세그먼테이션 기법의 경우 세그먼트 크기가 다양하기 때문에 베이스값에는 정확한 바이트 단위의 주소가 담겨져 있습니다.


Q) 요구 페이징(demand paging)란 무엇인가요?
A) 프로그램 전체를 메모리에 적재시키지 않고 필요한 페이지만을 메모리에 적재시킴으로써 공간적 이득을 볼 수 있는 기법입니다.


Q) 페이지 교체 알고리즘에는 무엇이 있나요?
A) 페이지 교체 알고리즘의 목표는 페이지 부재 발생율을 최대한 줄이는 것입니다. FIFO 알고리즘, Optimal 알고리즘, LRU 알고리즘, LFU 알고리즘 등이 존재합니다.
FIFO 알고리즘은 먼저 들어온 페이지를 먼저 내보내는 알고리즘입니다. 프레임 개수가 늘어날 때 오히려 페이지 부재가 더 많이 발생하는 FIFO Anomaly 문제가 발생합니다.
Optimal 알고리즘은 가장 먼 미래에 참조되는 페이지를 내보내는 알고리즘입니다. 이 알고리즘은 미래에 참조될 페이지를 모두 알고있다는 가정하에 가능한 알고리즘이라 수행에는 어려움이 있습니다. 이 알고리즘은 다른 알고리즘 성능의 상한선을 제공하는 역할을 합니다.
LRU 알고리즘은 가장 오래전에 참조한 페이지를 내보내는 것입니다. 단점은 참조 횟수를 고려하지 않습니다.
LFU 알고리즘은 가장 적게 참조된 페이지를 내보내는 것입니다. 단점은 참조 시점을 고려하지 않습니다.
+) LRU는 연결리스트로 O(1)에 구현할 수 있습니다. 현 시점에 참조된 페이지를 단순히 연결리스트의 가장 맨 끝으로 보내면 됩니다. LFU는 연결리스트로 O(n)으로 구현할 수 있습니다. 참조 횟수를 살피며 자기가 들어갈 위치를 찾아야 하기 때문입니다. 단, Heap 자료구조로는 O(logN)으로 구현할 수 있습니다. 본인의 참조횟수가 증가했을 때 자기 자식과만 비교하며 자리를 찾습니다.