소개
메모리 관리 배경
각각의 프로세스는 독립된 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있다. 단지, 운영체제만이 운영체제 메모리 영역과 사용자 메모리 영역에 접근을 제약을 받지 않는다.
페이징
하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 업애는 메모리 관리 방법이다. 외부 단편화와 압축 작업을 해소하기 위해 생긴 방법론으로, 물리 메모리는 Frame이라는 고정 크기로 분리되어 있고, 논리 메모리(프로세스가 점유하는)는 페이지라 불리는 고정 크기의 블록으로 분리 된다.
페이징 기법을 사용함으로써 논리 메모리를 물리 메모리에 저장될 때, 연속되어 저장될 필요가 없고 물리 메모리의 남는 프레임에 적절히 배치됨으로 외부 단편화를 해결할 수 있는 큰 장점이 있다.
하나의 프로세스가 사용하는 공간을 여러개의 페이지로 나뉘어서 관리되고(논리 메모리에서), 개별 페이지는 순서에 상관없이 물리 메모리에 있는 프레임에 mapping되어 저장 된다고 볼 수 있다.
요구 페이징(Demand Paging)
프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라 하며, 가상 메모리 시스템에서 많이 사용된다.
그리고 가상 메모리는 대게 페이지로 관리된다. 요구 페이징을 사용하는 가상 메모리에서는 실행과정에서 필요해질 때 페이지들이 적재된다. 한 번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.
프로세스 내 개별 페이지들은 페이저(pager)에 의해 관리된다. 페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리에 읽어 옴으로써, 사용되지 않을 페이지를 가져오는 시간 낭비와 메모리 낭비를 줄일 수 있다.
페이지 교체
요구 페이지에서 언급된대로 프로그램 실행시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재)가 발생하게 되면, 원하는 페이지를 보조저장장치로 가져오게 된다. 하지만, 만약 물리 메모리가 모두 사용중인 상황이라면, 페이지 교체가 이뤄줘야 한다. (또는 운영체제가 프로세스를 강제 종료하는 방법이 있다.)
페이지 교체 방법
물리 메모리가 모두 사용중인 상황에서 메모리 교체 흐름이다.
- 디스크에서 필요한 페이지의 위치를 찾는다.
- 빈 페이지 프레임을 찾는다.
페이지 교체 알고리즘을 통해 희생될 페이지를 고른다.- 희생될 페이지를 디스크에 기록하고, 관련된 테이블을 수정한다.
- 새롭게 비워진 페이지 테이블 내 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정한다.
- 사용자 프로세스 재시작
페이지 교체 알고리즘
- 운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다.
- 페이징 기법으로 메모리를 간리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시 (페이지 부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을
페이지 교체 알고리즘이라고 한다.
프레임 :
물리 메모리를 일정한 크기로 나눈 블록
페이지 :가상 메모리를 일정한 크기로 나눈 블록
| 알고리즘 | 설명 |
|---|---|
| OPT(Optimal) | 앞으로 가장 오랫동안 사용되지 않을 페이지 교체 |
| FIFO(First In First Out) | 먼저 들어온 페이지가 먼저 나가게 된다. |
| LRU(Least Recently Used) | 가장 오랫동안 사용되지 않은 페이지 교체 |
| LFU(Least Frequently Used) | 참조 횟수가 가장 작은 페이지 교체 |
1. OPR(Optimal Page Replacement)
Belady의 모순을 확인한 이후 최적 교체 알고리즘에 대한 탐구가 진행되었고, 모든 알고리즘 보다 낮은 부재율을 보이며 Belady의 모순이 발생하지 않는다.
이 알고리즘의 핵심은 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것이다. 주료 비교 연구 목적으로 사용 된다.
장점
- 알고리즘 중 가장 낮은 페이지 부재율을 보장한다.
단점
- 구현의 어려움이 있다. 모든 프로세스의 메모리 참조 계획을 미리 파악할 방법이 없다.
2. FIFO(First In First Out)
가장 간단한 페이지 교체 알고리즘으로 먼저 물리 메모리에 들어온 순서대로 페이지 교체 시점에 먼저 나가게 된다.
장점
- 이해하기 쉽고, 프로그램하기도 쉽다.
단점
- 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다. ( 초기 변수 등)
- 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 내 부재율을 높이는 부작용을 초래할 수 있다.
Belady의 모순: 페이지를 저장 할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순이 존재한다.
3. LRU(Least Recently Used)
가장 오랫동안 사용하지 않았던 데이터라면 앞으로도 사용할 확률이 적을 것이다. 라는 가정을 가지고 동작한다.
특징
- 국부성(locality)에 기반 : 어느 한순간에 특정 부분을 집중적으로 참조
- 시간 국부성 : 현재 참조된 기억장소는 가까운 미래에도 계속 참조될 가능성이 높음
- 공간 국부성 : 하나의 기억장소가 참조되면 근처의 기억 장소가 계속 참조될 가능성이 높음
장점
Belady의 모순이 발생하지 않음
단점
- 경험적 판단이 맞지 않는 상환도 존재
- 막대한 오버헤드 발생
4. LFU(Least Frequently Used)
참조 횟수가 가장 적은 페이지를 교체하는 방법이다. 활발하게 사용되는 페이지는 참조 횟수가 많아질 것이라는 가정에서 만들어진 알고리즘이다.
페이지가 참조 될 때마다 증가된 횟수를 기록하고 참조 횟수가 가장 적은 페이지를 교체 한다.
단점
- 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성이 높다.
- 초기에 매우 많이 사용된 후 더 이상 사용되지 않는 페이지는 교체 가능성이 낮다.