프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라 하며, 가상 메모리 시스템에서 많이 사용된다. 그리고 가상 메모리는 대개 페이지로 관리된다. 요구 페이징을 사용하는 가상 메모리에서는 실행과정에서 필요해질 때 페이지들이 적재된다. 한 번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.
프로세스 내의 개별 페이지들은 페이저(pager)에 의해 관리된다. 페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어옮으로써, 사용되지 않을 페이지를 가져오는 시간낭비와 메모리 낭비를 줄일 수 있다.
요구 페이징에서 언급된 대로 프로그램 실행시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재)가 발생하게 되면, 원하는 페이지를 보조저장장치에서 가져오게 된다. 하지만, 만약 물리 메모리가 모두 사용중인 상황이라면, 페이지 교체가 이뤄져야 한다(또는 운영체제가 프로세스를 강제 종료하는 방법이 있다)
물리 메모리가 모두 사용중인 상황에서의 메모리 교체 흐름이다
- 디스크에서 필요한 페이지의 위치를 찾는다
- 빈 페이지 프레임을 찾는다
- 페이지 교체 알고리즘을 통해 희생될(victim) 페이지를 고른다
- 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블을 수정한다
- 새롭게 비워진 페이지 테이블 내 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정한다
- 사용자 프로세스 재시작
- 가상 메모리는 요구 페이징 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다
- 하지만, 필요한 페이지만 올리더라도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다
- 메모리가 가득차면 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고 해당 공간에 현재 필요한 페이지를 in 시켜야 한다
- 수정이 되지 않는 페이지를 선택해야 좋다. 만약, 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정해야 하므로 시간이 오래걸린다
- 이러한 상황에서 적절한 페이지 교체를 위해 페이지 교체 알고리즘이 존재한다
- 운영체제는 모든 프로그램에게 같은 크기의 메모리를 할당하지 않고 몇몇 프로그램에게 집중적으로 메모리를 할당한 후, 시간이 흐르면 이들에게서 메모리를 회수하여 다른 프로그램들에게 다시 집중적으로 할당하는 방식을 사용한다
- CPU를 할당받아 당장 수행해야 할 부분만 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 사용한다. 이를 통해 프로그램이 자기 자신만 메모리를 사용하는 것과 같은 효과를 낸다.
- 가상 메모리는 프로세스마다 각각 0번지부터 시작하는 자기 자신만의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑 영역에 적재된다 -> 요구 페이징 기법
- 가상 메모리는 요구 페이징 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다
- 특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재하며, 한번도 접근되지 않는 페이지는 물리적 메모리에 적재되지 않는다
- 이를 통해 메모리 사용량이 감소하고 프로세스 전체를 메모리에 올리는데 들었던 입출력 오버헤드가 감소하며 응답시간이 단축된다
- 유효, 무효 비트를 두어 각 페이지가 메모리에 존재하는지 표시한다
- 유효 : 페이지가 메모리에 적재됨
- 무효 : 페이지가 현재 메모리에 없는 경우이거나 그 페이지가 속한 주소 영역을 프로세스가 사용하지 않는 경우
- CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 무효로 세팅되어 있는 경우를 '페이지 부재'가 일어났다고 한다
- 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다
- 이 경우, 메모리에 올라와있는 페이지 중 하나를 디스크로 쫓아내고 메모리에 빈 공간을 확보하는 작업이 필요하다. 이를 페이지 교체라고 한다
- 페이지 교체를 할 때, 어떤 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 페이지 교체 알고리즘이라 하며, 목표는 페이지 부재율을 최소화하는 것이다
페이지 부재 발생 -> 새로운 페이지를 할당해야 한다 -> 현재 할당된 페이지(메모리에 올라와있는 페이지) 중 어떤 것을 교체할지 결정하는 방법
- FIFO(First in First out)알고리즘
- 페이지 교체시 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
- 가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법이다.
- 단점
- 페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기 때문에 비효율적인 상황이 발생할 수 있다
- 빌레이디의 모순 현상이 발생할 수 있다(페이지 프레임 수가 많으면(메모리 증가) 페이지 부재수가 줄어드는 것이 일반적이지만, 페이지 프레임 수를 증가시켰음에도 페이지 부재가 더 많이 일어나는 현상)
- 최적 페이지 교체 알고리즘(Optimal Page Replacement)
- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방법
- 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전제하에 알고리즘을 운영하므로 현실적인 구현이 어렵다
- 페이지 부재율이 가장 낮은 효율적인 알고리즘이다
- LRU(Least Recently Used)
- 최근에 사용하지 않은 페이지를 가장 먼저 내보내는 방법
- 최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나왔다
- OPT의 경우 미래 예측이지만, LRU의 경우 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘(실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다)
- OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나이다
- LFU 알고리즘(Least Frequently Used)
- 페이지의 참조 횟수로 교체할 페이지를 결정하는 방법
- 즉, 물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적었던 페이지를 내쫓고 그 자리에 새로 참조될 페이지를 적재한다
- 단점
- 시간에 따른 페이지 참조의 변화를 반영하지 못하고 LRU보다 구현이 복잡하다
- LRU, LFU 알고리즘은 페이지의 최근 참조 시각 및 참조 횟수를 소프트웨어적으로 유지해야 하므로 알고리즘의 운영에 오버헤드가 발생한다
- 클럭 알고리즘(NRU : Not Recently Used, NUR : Not Used Recently)
-
하드웨어적인 지원을 받아 LRU와 LFU 알고리즘에서 발생한 시간적인 오버헤드를 줄인 방식이다
-
LRU를 근사시킨 알고리즘이라고 하며, 오랫동안 사용하지 않은 페이지 중 하나를 교체한다
-
최근에 참조되지 않은 페이지를 교체 대상으로 선정하는 측면에서 LRU와 비슷하지만 교체되는 페이지의 참조 시점이 가장 오래됐다는 것을 보장하지 못한다
-
참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)를 사용한다
- 참조 비트
- 페이지가 참조될 때, 1로 자동 세팅된다
- 페이지가 참조되지 않았을 때는 0이 되며 페이지는 교체된다
- 변형 비트
- 페이지 내용이 변경되었을 때, 1로 지정한다
- 페이지 내용이 변경되지 않았을 때는 0으로 지정한다
- 참조 비트
-
이 알고리즘은 하드웨어의 자원으로 동작하기 때문에 LRU에 비해 교체 페이지의 선정이 훨씬 빠르게 결정된다
-
따라서 대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다
-
다시 설명하자면, 주기적으로 0으로 재설정하지 않는 시스템을 가정하며, 주기억장치에 적재된 페이지들을 환형리스트로 보고 각 페이지를 시계 방향으로 움직이는 포인터를 사용하여 교체될 페이지를 선정한다. 원칙은 다음과 같다
-
- 현재 포인터가 가리키는 페이지의 참조 비트 검사
-
- 해당 페이지가 리스트에 있고 참조 비트가 0이라면 1로 재설정. 이 때 포인터는 움직이지 않음
-
- 그 값이 0이면 해당 페이지를 교체하고 포인터를 시계 방향으로 한 단계 진행 후 선정 과정 종료
-
- 그 값이 1이면 해당 페이지의 참조비트를 0으로 재설정하고 포인터를 한 단계 진행 후 단계 1부터 반복
-
- Global 교체
- 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
- Local 교체
- 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식
다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음
따라서, 다양한 프로세스의 페이지가 메모리에 존재함
페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이
-> 실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 한다. 자기 프로세스 페이지에서만 교체하면 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적이다.