가상 기억장치란?
보조기억장치(하드디스크)의 일부를 주기억장치(ROM&RAM)처럼 사용하는 것으로, 용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법.
=> 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식
ex) 내가 실행하고자 하는 프로그램의 용량이 5GB인데, 메모리는 4GB이다. 어떻게 실행할까?
올리는 것도 문제이지만, 올린다고 하더라도 해당 프로그램이 실행될 때는 다른 작업은 아무것도 하지 못하게 된다. 이럴 때 사용하는 기술이 바로 가상 메모리이다.
가상 메모리는 각 프로세스당 메인 메모리와 동일한 크기(페이징)로 하나씩 할당된다. 그 공간은 보조기억장치 공간을 이용한다. 프로세스의 일부만 메모리에 로드하고 나머지는 보조기억장치에 두는 형태이다.
이렇게 할당되면 메모리 관리 장치(MMU)에 의해 물리 주소로 변환되어 사용자가 메모리 맵핑이 어떻게 되는지 의식할 필요 없이 알아서 가상 메모리를 활용하여 작업한다.
또한, 가상기억장치를 사용함으로 주기억장치의 이용률과 다중 프로그래밍의 효율을 높일 수 있다.
페이징(Paging)
가상기억장치에 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 나눠진 프로그램(페이지)을 동일하게 나눠진 주기억장치의 영역(페이지 프레임)에 적재시켜 실행하는 기법.
-
페이지(Page) :가상메모리의 주소 데이터들을 일정한 크기의 블록으로 쪼게 놓은 것.
-
프레임(Frame) : 물리메모리(RAM)의 주소 데이터들을 일정한 크기의 블록으로 쪼게 놓은 것.
-
외부 단편화는 발생하지 않으나 내부 단편화는 발생할 수 있다.
-
주소 변환을 위해서 페이지의 위치 정보를 가지고 있는 페이지 맵 테이블(Page Map Table)이 필요하다.
-
페이지 맵 테이블 사용으로 비용이 증가되고, 처리 속도가 감소된다.
페이지 교체 알고리즘
페이지 교체 알고리즘은 *페이지 부재가 발생했을 때 가상기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데, 이때 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법.
페이지 부재 : CPU가 액세스한 가상 페이지가 주기억장치에 없는 경우를 말한다. 페이지 부재가 발생하면 해당 페이지를 디스크에서 주기억장치로 가져와야 한다.
FIFO(First in First out)
- 페이지 교체시 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘.
- 가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법이다.
- 단점
- 페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫒을 대상을 선정하기 때문에 비효율적인 상황이 발생할 수 있다.
- 빌레이디의 모순 현상이 발생할 수 있다. (페이지 프레임 수가 많으면(메모리 증가) 페이지 부재수가 줄어드는 것이 일반적이지만, 페이지 프레임 수를 증가시켰음에도 페이지 부재가 더 많이 발생하는 현상을 의미)
OPT(OPTimal replacement) 최적교체
- 앞으로 가장 오랫동안 사용하지 않은 페이지를 교체하는 방법
- 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전제하에 알고리즘을 운영하므로 현실적으로 구현이 어렵다.
- 페이지 부재율이 가장 낮은 효율적인 알고리즘이다.
LRU 알고리즘(Least Recently Used)
- 최근에 사용하지 않은 페이지를 가장 먼저 내보내는 방법
- 최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나왔다.
- OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘 (실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다.)
- OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나이다
LFU 알고리즘(Least Frequently Used)
-
페이지의 참조 횟수로 교체할 페이지를 결정하는 방법
-
즉, 물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적었던 페이지를 내쫓고 그 자리에 새로 참조될 페이지를 적재한다.
-
단점
- 시간에 따른 페이지 참조의 변화를 반영하지 못하고 LRU보다 구현이 복잡하다.
-
LRU, LFU 알고리즘은 페이지의 최근 참조 시각 및 참조 횟수를 소프트웨어적으로 유지해야 하므로 알고리즘의 운영에 오버헤드가 발생한다.
NUR(Not Used Recently)
-
하드웨어적인 지원을 받아 LRU와 LFU 알고리즘에서 발생한 시간적인 오버헤드를 줄인 방식이다.
-
LRU를 근사시킨 알고리즘이라고 하며, 오랫동안 사용하지 않은 페이지 중 하나를 교체한다.
-
최근에 참조되지 않은 페이지를 교체 대상으로 선정하는 측면에서 LRU와 비슷하지만 교체되는 페이지의 참조 시점이 가장 오래됐다는 것을 보장하지 못한다.
-
참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)를 사용한다.
- 참조 비트
- 페이지가 참조될 때, 1로 자동 세팅된다.
- 페이지가 참조되지 않았을 때는 0이 되며 페이지는 교체한다.
- 페이지가 참조될 때, 1로 자동 세팅된다.
- 변형 비트
- 페이지 내용이 변경되었을 때, 1로 지정한다.
- 페이지 내용이 변경되지 않았을 때는 0으로 지정한다.
- 페이지 내용이 변경되었을 때, 1로 지정한다.
- 참조 비트
-
이 알고리즘은 하드웨어의 자원으로 동작하기 때문에 LRU에 비해 교체 페이지의 선정이 훨씬 빠르게 결정된다.
-
따라서 대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다.
