이 글은 반효경 교수님의 운영체제 강의 및 교재를 참고합니다.
1. Memory Management
Logical vs. Physical Address
Logical address(=virtual address)
- 프로세스마다 독립적으로 가지는 주소 공간
- 각 프로세스마다 0번지부터 시작
- CPU가 보는 주소는 logical address임
Physical address
- 메모리에 실제 올라가는 위치
- HW DRAM의 주소
주소 바인딩
- 주소를 결정하는 것
- Symbolic Address -> Logical Address -> Physical address
- Compile time binding
- 물리적 메모리 주소(physical address)가 컴파일 시 알려짐
- 시작 위치 변경 시 재컴파일
- 컴파일러는 절대코드(absolute code) 생성
- Load time binding
- 실행이 시작될 때 주소 변환이 이루어짐
- Lodader의 책임 하에 물리적 메모리 주소 부여(한 번 올라가면 안바뀜)
- 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능
- Run time binding(= Run-time biding)
- 실행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
- CPU가 주소를 참조할 때마다 binding을 점검(address mapping table)
- 하드웨어적인 지원이 필요(base and limit registers, MMU)
(1) 가상 메모리란?
-
왜 필요한가?
가상 메모리를 사용하면 사용자 프로그램이 물리적 메모리보다 커져도 실행이 가능하기 때문이다. 즉, 사용자가 메모리 크기에 관련한 문제를 염려하지 않아도 된다. 운영체제는 가상 메모리 기법을 사용하여 프로그램의 논리적 주소 영역에서 필요한 부분만 물리적 메모리에 적재하고, 직접적으로 필요하지 않은 메모리 공간은 디스크에 저장하게 된다.그러면 필요한 부분만 어떻게 물리적 메모리에 적재할까? => Demand Paging! -
하는 일
프로세스가 사용하는 메모리 공간의 범위를 가상 세계로 제한시켜, 애플리케이션이 죽어도 OS에는 이상이 없도록 한다. (시스템 안정성) -
구현 방식
프로세스가 생성될 때 독자적인 주소 공간이 만들어지며, 각 프로세스마다 0번지부터 시작한다. 이 개별적인 논리적 주소를주소 바인딩하여 물리적 주소로 바꾸어 처리한다.
(2) 메모리 단편화란?
메모리 관리 기법은 크게 연속 메모리 관리와 불연속 메모리 관리로 나뉜다.
불연속 메모리 관리 방식은 프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 방식을 말한다.
연속 메모리 관리 방식은 프로그램 전체가 메모리에 연속적으로 할당되어야 하는 방식을 뜻한다. 두 가지로 다시 나눠볼 수 있다.
-
고정 분할 기법 : 메모리가 고정된 파티션(길이)으로 분할됨
-
고정된 파티션보다 적은 메모리를 할당할 때 남는 공간이 낭비된다.
-
-> 내부 단편화 발생
-
동적 분할 기법 : 파티션들이 동적 생성, 자신의 크기와 같은 파티션에 적재됨
-
메모리 적재, 해제 반복하면서 틈(낭비 메모리)이 발생한다.
-
-> 외부 단편화 발생
2. Demang Paging
실제로 필요할 때 page를 메모리에 올리는 것
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
(1) Demand Paging
필요한 부분만 물리적 메모리에 page 단위로 적재하는 방법을 요구 페이징이라고 한다. 요구 페이징 기법에서는 특정 page에 대해 CPU 요청이 들어오면, 해당 page를 메모리에 적재한다. 이렇게 당장 필요한 page만을 메모리에 적재하기 때문에, 메모리 사용량이 줄어들고 프로세스 전체를 메모리에 적재하는 입출력 오버헤드도 줄어든다.
요구 페이징 기법에서는 valid/invalid bit를 두어 각 page가 메모리에 존재하는지 표시한다.
valid bit: 메모리에 있음/invalid bit: 메모리에 없음
처음에는 모든 page entry가 invalid로 초기화
-> address translation 시에 invalid bit이 set되어 있으면:page fault
(2) Page Fault
CPU가 invalid page에 액세스하는 상황을 Page fault라고 한다.
- Page Fault 처리 방법
1) CPU가 특정 페이지에 접근, Page Table에서 valid 여부를 조사
2) Page가 invalid 할 경우, MMU에서 Page Fault Trap 발생
3) 디스크에서 해당 페이지를 빈 프레임에 적재, Page Table 업데이트(invalid->valid)
4) Trap에 의해 중단되었던 명령 다시 수행
-> MMU: virtual memory address를 physical memory address로 변환하는 HW 장치
(3) Page Replacement Algorithm
Page Fault가 발생하면, 요청된 페이지를 디스크에서 메모리로 가져온다.
이 때, 물리적 메모리 공간이 부족한 상황이 발생할 수 있다.즉, 메모리에 올라와 있는 페이지를 디스크로 다시 옮겨서 메모리 공간을 확보해야 한다.
-> 페이지 교체
어떤 페이지가 교체 대상인지는 페이지 교체 알고리즘에 따라 달라진다.
-> 교체 알고리즘은 당연히 page fault가 적게 일어나도록 하는 것이 좋은 알고리즘이다. 따라서, 앞으로 사용될 일이 적은 페이지를 선택하여 교체하는 것이 성능을 향상시킬 수 있다.
OPT(Optimal) Algorithm
앞으로 가장 오랫동안 사용하지 않을 페이지를 찾아 교체한다.
하지만! 미래의 일을 모두 다 알고 있는 경우가 얼마나 있을까?실제로 구현하기에는 불가능한 알고리즘이다.
FIFO(First In First Out) Algorithm
먼저 들어온 것을 먼저 내쫓음
다만, 일반적으로는 page frame을 늘리면 성능이 좋아져야 하는데 이 경우에는 오히려 더 많은 Page Faults가 발생할 수도 있다. 이를 FIFO Anomaly(Belady's Anomaly)라고 부른다.
-> FIFO Anomaly (Belady’s Anomaly): more frames ≠ less page faults
LRU(Least Recently Used) Algorithm
가장 오래 전에 참조된 것을 내쫓음(과거를 가지고 어떤 것을 쫓아낼지 판단함)
최근에 참조된 페이지가 다시 참조될 가능성이 높다는 것에 기인한 알고리즘이다.
LFU(Least Frequently Used) Algorithm
참조 횟수(reference count)가 가장 적은 페이지를 쫓아냄
최저 참조 횟수인 page가 여러 개인 경우에는 어찌하는가?
- LFU 알고리즘 자체에서는 임의 선정 방식을 채택
- 하지만 성능 향상을 위해 가장 오래 전에 참조된 page를 지우도록 구현할 수도 있음
장점: LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 보다 정확히 반영할 수 있다.
단점: 참조 시점의 최근성을 반영하지 못하며, LRU보다 구현이 복잡하다.
LRU vs LFU
LRU는 예전에 인기있었던 page를 선별하지 못하고, LFU는 최근에 인기 있어지기 시작한 page를 선별하지 못한다.
LRU는 어떤 페이지가 한 번만 참조되어도 그 노드의 우선순위가 가장 높아진다. 따라서 이중 연결 리스트를 활용하여 메모리 참조와 preemption을 O(1) 시간 복잡도로 처리할 수 있다.
그러나 LFU는 어떤 페이지가 참조가 되더라도 MFU로 바로 내려갈 수 없고 하나씩 비교하면서 내려가야 한다. 따라서 최악의 경우 메모리 참조와 preemption을 O(N) 시간 복잡도로 처리하게 된다.
그래서?
LFU의 경우에는 완전 이진 트리인 heap을 이용하여 구현하면 시간 복잡도가 O(logN)이 되어 performance가 크게 개선된다.
