[Operating Systems] Virtual Memory

Virtual Memory(가상 메모리) 기법은 사용자의 logical memory와 physical memory를 분리하기 위한 기술이다. 
이를 이용하여 Logical address space가 physical address space보다 커지는 것을 가능하도록 한다.
이러한 virtual memory는 Demand paging이라는 기법을 이용하여 구현된다.

Demand paging은 실제로 필요한 page만 메모리로 가져오는 것이다.
앞에서 언급했던 paging 기법에서는 프로세스의 메모리 공간을 다 할당해야 했기 때문에 사용되지 않는 부분까지 가져오는 불합리성이 있었는데 여기에서는 그 단점을 없앤다.
이것은 page table에 추가 엔트리를 부여하여 구현된다.
valid bit라는 것을 두고 실제로 해당 page가 physical memory에 있으면 valid로 set, 없으면 invalid로 clear한다.

페이지 접근을 요청하였는데 physical memory에 없는 상태, 즉 valid bit가 clear 되어있는 상황을 Page Fault라 하며 아래와 같은 처리 과정을 거친다.
1. 페이징 하드웨어는 page table entry를 보고 invalid인것을 확인한 후 OS에게 trap으로 알린다.
2. OS는 정말로 메모리에 없는 것인지 아니면 잘못된 접근인지 확인 한 후 잘못된 접근이었으면 종료시킨다.
3. empty frame을 얻는다.
4. page를 frame으로 swap한다.
5. 프로세스의 page table을 reset한다.
6. Page fault를 야기했던 인스트럭션부터 다시 수행한다.

 
이러한 Demand Paging을 가능하게 하는 것은 Locality의 개념이다.
Locality는 Computer Architecture에서도 나오는 개념으로 중요하니 확실히 숙지하자.

Temporal Locality는 시간적 지역성이라 하며 최근에 접근되었던 것이 다시 접근되는 것을 말하며,
Spatial Locality는 공간적 지역성이며 최근에 접근되었던 것에 가까운 것이 접근되는 것을 말한다.
예를 들어 1시에 서울에 비가 왔는데 2시에 서울에 비가 또 오는것은 시간적 지역성이고,
서울에 비가 왔는데 인천에도 비가 오는 것을 공간적 지역성이라고 한다.
즉 Locality에 의하면 접근되었던 것은 접근될 가능성이 크므로 메모리에 남아있게 되고 그것이 즉 Demand paging이 동작하게 되는 근본이 된다.

위의 Page Fault 처리 과정으로 돌아가서 3번 단계를 보면 empty frame을 얻는다고 되어 있다.
물론 empty frame이 있으면 그냥 얻으면 되겠지만 멀티프로세싱환경에서 실행하다 보면 메모리가 꽉 차있을 경우가 있을 것이다.
이 경우에는 어떠한 기준에 의해 페이지 하나를 swap out하고 그 프레임을 할당해야 할 것이다.

그러한 victim page를 정하는 알고리즘을 Page Replacement Algorithm이라 한다.

첫째로 FIFO(First in First out)알고리즘은 가장 오래된 페이지를 없애는 것이다. 공평하기는 하겠으나 locality가 적용되지 않은 방법이므로 비효율적이다.

다음으로 Optimal 알고리즘이다. 가장 오랫동안 사용되지 않을 것을 victim으로 선정하는것이 당연히도 가장 합리적이며 효율적이다. 따라서 그러한 기준에 의하여 빅팀을 선정한다. 하지만 가장 오랫동안 사용되지 않을 것을 정하는 것은 불가능하므로 이론적인 알고리즘이라 볼 수 있다.

그래서 OPT 알고리즘과 유사하지만 반대로 생각한 것이 LRU(Least Recently Used) 알고리즘인데, 가장 오랫동안 사용되지 않았던 것은 앞으로도 그럴 것이라는 가정하에 victim으로 선정한다.
이 LRU 방식은 첫째로 counter를 두어 구현할 수 있다. 카운터에 접근횟수를 기록하는 것이다.
둘째로 Stack 방식으로 구현할 수 있다.
더블 링크드 리스트의 스택으로 구현한 뒤 어떠한 페이지가 접근되면 그 페이지를 top으로 올린다. 그리고 만약 victim을 선정해야 하면 bottom에 있는 페이지를 victim으로 선정하게 된다.

하지만 이러한 방식을 쓰면 많은 페이지 엔트리가 존재하는 페이지 테이블에서는 연산이 많아지고 각 엔트리마다 두개의 링크만큼의 공간을 필요로 하므로 비효율적이다. 따라서 주로 True LRU는 캐쉬에서 많이 사용하고, Page Table에서는 LRU-approximation알고리즘을 사용한다. 이것은 하드웨어의 도움을 받아 reference bit를 두고 이용한다.
페이지들을 Circular queue형태로 나타내고 만약 reference가 일어나면 이 bit를 set한다. 그리고 victim 페이지를 선정할 때는 하나씩 접근하여 reference bit를 확인한다. 만약 bit가 clear하면 그 페이지를 victim으로 선정하며, set 되어 있으면 그 bit를 clear시키고 다음 페이지를 확인한다. 해당 페이지에 Second-chance를 주는 것이므로 Second-chance algorithm이라고도 한다.

그리고 카운팅을 기반으로 한 알고리즘으로 MFU, LFU알고리즘이 있다.

이런식으로 Virtual Memory를 사용하다 보면 실제 존재하는 물리적 메모리 공간보다 논리적 메모리 공간이 큰 것 처럼 사용될 수 있기 때문에 효율적이다. 그런데 효율적이라는 이유로 멀티프로세싱의 degree를 계속 늘리다 보면 실제 실행하는 시간보다 page replacement를 하는 시간이 더 많아지는 순간이 오며 CPU는 사용율이 떨어지게 된다. 그런데 CPU는 CPU사용률만 보고 이것을 올리기 위하여 멀티프로세싱의 degree는 더 증가하고 따라서 효율은 극악으로 나빠지게 되는데 실행 시간보다 페이지 교체 시간이 많아지는 현상을 Thrashing이라 한다. 

 

이 스래싱이 발생하는 이유는 locality의 크기의 합이 실제 메모리의 크기보다 커졌기 때문이다.

따라서 이 스래싱을 해결하기 위해 Working set model을 적용한다.
working set model은 locality를 approximate한 것으로 페이지 넘버로 관리한다.
그러다 working set의 크기가 실제 메모리보다 커지면 하나의 프로세스를 종료하는 방식으로 스래싱이 생기지 않도록 할 수 있다.

하지만 위 방법은 접근되는 페이지를 관리해야 하므로 불편한 감이 있다.
따라서 스래싱이 생겼다는 것은 즉 Page Fault가 많아졌다는 것이기 때문에 그것의 정도를 지정하고 Page Fault의 횟수가 어느 한계점을 넘어가면 프로세스를 종료하는 방식으로 구현한다.


Virtual Memory를 사용하게 되면 생기는 부가적인 장점으로 공유 메모리 사용, Copy on write 메커니즘, Memory mapped file이 있다. 
여러 프로세스간의 communication의 한 가지 방법으로 공유 메모리를 사용할 수 있는데 demand paging 기법을 사용할 경우 다른 프로세스의 각각의 페이지가 같은 프레임을 가리키도록 하면 공유 메모리를 사용할 수 있다.
또한 COW(Copy-On-Write) 메커니즘은 부모 프로세스를 clone하여 자식 프로세스를 생성하였을 때 처음에는 같은 메모리를 사용하도록 하다가 그곳에 Write가 발생하였을 때 메모리를 copy하는 것으로 이것 또한 공유 메모리처럼 같은 프레임을 가리키도록 하였다가 복사가 되었을때 새로운 프레임을 할당하면 된다.
그리고 Memory mapped file은 file을 접근하는 것을 메모리 접근하듯이 페이지를 할당하여 할 수 있도록 하는 것이며 메모리 접근 속도가 더 빠르므로 효율적이다.


Paging은 동일한 크기를 가지는 page  단위로 메모리를 나누는 것이라 하였다.
반면에 Segmentation은 가변 크기의 단위인 segment로 메모리 영역을 나눈다. 이것은 사용자가 바라보는 관점에서 메모리를 나눈 것이며 일반적인 사용자는 페이지 단위로 메모리를 바라보지 않고 큰 단위단위로 바라보게 된다.
따라서 최근의 컴퓨터는 세그멘테이션 기법과 페이징 기법을 동시에 적용하여 메모리를 접근하게 된다.