가상 메모리는 프로세스의 전체가 메모리에 적재되어 있지 않아도 실행이 가능하도록 하는 기법입니다.
요구 페이징(demand paging)은 프로그램 전체를 메모리에 올리는것이 아닌 필요한 페이지만 메인 메모리에 적재하는 기법입니다. 프로세스가 메모리에 올라와 있지 않은 페이지에 접근 하려고 하면 (보호 비트가 Invalid 하면) 페이지 폴트 트랩을 발생시킵니다. 아래는 페이지 폴트 트랩을 처리하는 과정입니다.
1. 프로세스에 대한 내부 테이블을 검사해서 그 메모리 참조가 유호한지 무효한지 알아냅니다.
2. 메모리 참조가 무효라면 잘못된 주소로의 접근이기 때문에 프로세스는 중단됩니다. 만약 유요한 참조일 경우 아직 메모리에 올라와 있지 않기 때문에 보조저장장치로부터 가져와야 합니다.
3. 메인 메모리에 빈 공간, 즉 가용 프레임(free frame)을 찾습니다.
4. 보조기억창지로부터 찾아낸 가용 프레임으로 페이지를 읽어 들이도록 요청합니다.
5. 읽기가 끝나면, 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며, 프로세스가 유지하고 있는 내부 테이블을 수정합니다.
6. 트랩에 의해 중단된었던 명령어를 다시 수행합니다.
페이지 교체 알고리즘은 컴퓨터의 가상 메모리 관리에서 메인 메모리가 가득 차서 새로운 페이지를 불러올 수 없을 때, 어떤 페이지를 내보내고 교체할지를 결정하는 방법입니다.
FIFO 페이지 교체 알고리즘(First-In, First-Out)
FIFO 알고리즘은 가장 먼저 메모리에 들어온 페이지를 가장 먼저 교체하는 방식입니다. 큐(Queue) 자료구조를 사용하여 페이지를 관리하며, 페이지가 메모리에 들어온 순서대로 교체됩니다.
- 장점: 구현이 간단함
- 단점: 오래된 페이지가 반드시 덜 사용된다는 보장이 없어 효율성이 떨어질 수 있음
Optimal 페이지 교체 알고리즘 (OPT)
OPT(최적) 알고리즘은 이론적으로 가장 이상적인 알고리즘입니다. 미래의 메모리 참조를 미리 알고 있다고 가정하고, 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다.
- 동작 원리:
- 모든 페이지 참조를 미리 알고 있다고 가정.
- 새로운 페이지를 넣기 위해 메모리가 꽉 찼을 때, 앞으로 가장 오랫동안 사용되지 않을 페이지를 제거.
- 장점: 이론적으로 최적의 성능을 제공함.
- 단점: 미래의 메모리 참조를 예측할 수 없어 실제 시스템에서는 구현 불가.
LRU 페이지 교체 알고리즘 (Least Recently Used)
LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체합니다. 최근에 사용된 페이지는 앞으로도 사용될 가능성이 높다는 가정에 기반합니다.
- 동작 원리:
- 페이지가 사용될 때마다 현재 시간으로 해당 페이지의 사용 시간을 갱신.
- 새로운 페이지를 넣기 위해 메모리가 꽉 찼을 때 가장 오랫동안 사용되지 않은 페이지를 제거.
- 장점: 실제 사용 패턴과 잘 맞아 성능이 좋음.
- 단점: 구현이 복잡하며, 페이지의 사용 순서를 추적하는 데 많은 자원이 필요함.
- 구현 방법:
- 스택을 이용한 구현: 모든 페이지 접근 시마다 페이지를 스택의 맨 위로 이동시키고, 페이지 교체 시 스택의 맨 아래 페이지를 교체.
- 카운터를 이용한 구현: 각 페이지에 대한 시간 스탬프를 유지하고, 페이지 교체 시 가장 오래된 시간 스탬프를 가진 페이지를 교체.
프레임 할당은 가용 프레임을 어떻게(몇 개) 프로세스마다 할당해 줄 것인지 결정하는 방법입니다.
균등 할당 (Equal Allocation)
모든 프로세스에 동일한 수의 프레임을 할당합니다. 예를 들어, 총 100개의 프레임이 있고 5개의 프로세스가 있다면, 각 프로세스는 20개의 프레임을 할당받습니다.
- 장점: 구현이 간단하고 공평합니다.
- 단점: 각 프로세스의 실제 메모리 요구를 반영하지 않기 때문에 비효율적일 수 있습니다.
비례 할당 (Proportional Allocation)
각 프로세스의 크기(페이지 수)에 비례하여 프레임을 할당합니다. 예를 들어, 총 100개의 프레임이 있고, 프로세스 A가 200KB, 프로세스 B가 300KB의 메모리를 요구하는 경우, 프레임을 각 프로세스의 크기에 비례하여 할당합니다.
- 장점: 각 프로세스의 메모리 요구를 반영하여 효율적입니다.
- 단점: 여전히 각 프로세스의 동적인 메모리 요구를 반영하지 못합니다.
글로벌 할당 (Global Allocation)
프레임을 시스템 전체에서 공유하여 필요할 때마다 각 프로세스에 할당합니다. 프로세스가 페이지 폴트를 일으키면 다른 프로세스에서 프레임을 가져와 할당할 수 있습니다.
- 장점: 시스템 전체의 메모리 사용을 최적화할 수 있습니다.
- 단점: 한 프로세스가 많은 프레임을 차지하면 다른 프로세스가 프레임을 충분히 할당받지 못할 수 있습니다.
지역 할당 (Local Allocation)
각 프로세스에 할당된 프레임 집합 내에서만 프레임을 교체합니다. 즉, 프로세스가 페이지 폴트를 일으킬 때 다른 프로세스의 프레임을 사용할 수 없습니다.
- 장점: 각 프로세스의 메모리 요구를 독립적으로 관리할 수 있습니다.
- 단점: 전체 시스템의 메모리 사용 최적화가 어려울 수 있습니다.