가상 메모리(Virtual Memory) 이론 및 페이지교체 알고리즘

Virtual Memory

주기억장치의 부족한 physical memory를 보조기억장치를 이용해서 가상으로 늘려 준다.

 

 

Demand Paging

어떤 것을 하드에 두고 어떤 것을 실제 메모리에 올릴 것인가를 판단하는 기준이다. 여러가지가 있지만 일반적으로 사용되는것이 demand paging이므로 이에 대해서만 설명한다. demand paging은 말 그대로, 어떤 알고리즘에 따라서 미리 올려 두는 것이 아니라 실제 사용되려고 할때(demand 되었을때) 메모리에 올리는 방식을 말한다. 어떻게 보면 무척이나 당연한 이야기이다. 이 방식은 아래와 같은 장점이 있다.

• Less I/O needed
• Less memory needed
• Faster response
• More users

Virtual memory는 OS적으로 수행된다. (하드웨어의 도움을 받는 정도) 그래야 하드웨어들이 Virtual memory를 사용하지 않는 OS에서도 호환될 수 있다.

Demand paging를 수행하는 과정은 아래와 같다.

1. 어떤 명령을 수행하기 위해서 필요한 page로 엑세스를 시도한다.

2. 페이지가 invalid하다면

3. OS에선 페이지가 존재하지 않는 것인지, 아직 올라오지 않은 것인지 판단한다.

4. 아직 올라오지 않은 것이라면 하드에서 해당되는 페이지를 찾0는다.

5. 메모리로 올리고 다시 명령을 수행한다.

여기서 invalid한 page를 엑세스한 것은 page fault라고 부른다.

 

Page Replacement Algorithm

무거운 시스템에서는 demand가 생겼을때 page를 메모리에 올리려고 하면 대부분은 빈 공간이 없어서 메모리에 올라와 있는 어떤 페이지를 버려야(swap out, relpace) 한다. 이 page replacement를 잘 하는게 virtual memory의 핵심이다. 참 많은 page replacement 방식이 있다.

 

FIFO Algorithm

1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
1(0)	1(1)	1(2)	1(3)	1(4)	1(5)	5(0)	5(1)	5(2)	5(3)	5(4)	3(0)	3(1)	3(2)	3(3)	3(4)	1(0)	1(1)	1(2)	1(3)
	2(0)	2(1)	2(2)	2(3)	2(4)	2(5)	6(0)	6(1)	6(2)	6(3)	6(4)	7(0)	7(1)	7(2)	7(3)	7(4)	7(5)	3(0)	3(1)
		3(0)	3(1)	3(2)	3(3)	3(4)	3(5)	2(0)	2(1)	2(2)	2(3)	2(4)	6(0)	6(1)	6(2)	6(3)	6(4)	6(5)	6(6)
			4(0)	4(1)	4(2)	4(3)	4(4)	4(5)	1(0)	1(1)	1(2)	1(3)	1(4)	1(5)	2(0)	2(1)	2(2)	2(3)	2(4)

 

Belady's Anomaly = Frame수를 증가 시키니깐 오히려 fault수가 늘어나는 현상. 안좋은 알고리즘이라는 반증이다.

 

Belady's Algorithm(Optimal Algorithm)

1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
1	1	1	1(2)	1(1)	1(4)	1(3)	1(2)	1(1)	1(7)	1(6)	1(5)	2(3)	2(2)	2(1)	2(2)	2(1)	2(∞)	2(∞)	2(∞)
	2	2	2(1)	2(4)	2(3)	2(2)	2(1)	2(2)	2(1)	2(5)	2(4)	3(2)	3(1)	3(4)	3(3)	3(2)	3(1)	3(∞)	3(∞)
		3	3(8)	3(7)	3(6)	3(5)	3(5)	3(4)	3(3)	3(1)	3(3)	6(1)	6(6)	6(5)	6(4)	6(3)	6(2)	6(1)	6(∞)
			4(∞)	4(∞)	4(∞)	5(∞)	6(6)	6(5)	6(4)	6(3)	6(2)	7(∞)	7(∞)	7(∞)	7(∞)	1(∞)	1(∞)	1(∞)	1(∞)

 

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이론적으로 가장 효율적인 알고리즘이다. 하지만 앞으로 어떤 페이지가 사용될지 예상할 수 없으므로 실제로 구현은 불가능 할 것으로 예상되는, 다른 알고리즘과 비교하여 알고리즘의 효율성을 판단하는 기준으로 쓰이는 이상적 알고리즘이다.

 

LRU Algorithm

1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
1	1	1	1(4)	1(5)	1(1)	1(2)	1(3)	1(4)	1(1)	1(2)	1(3)	1(4)	2(4)	2(5)	2(1)	2(2)	2(1)	2(2)	2(3)
	2	2	2(3)	2(1)	2(2)	2(3)	2(4)	2(1)	2(2)	2(1)	2(2)	2(3)	3(3)	3(1)	3(2)	3(3)	3(4)	3(1)	3(2)
		3	3(2)	3(3)	3(4)	4(4)	5(2)	5(3)	5(4)	5(5)	6(5)	3(2)	7(2)	7(3)	7(4)	6(4)	6(5)	6(6)	6(1)
			4(1)	4(2)	4(3)	5(1)	6(1)	6(2)	6(3)	6(4)	3(1)	7(1)	6(1)	6(2)	6(3)	1(1)	1(2)	1(3)	1(4)

 

최근에 사용되지 않은 페이지를 제거한다. 프로그램의 Locality라는 특성을 이용한 것이다. 많은 프로그램이 내부적으로 반복문이 돌아가므로 최근에 실행되었던 부분이 또 실행될 확률이 높다.

이론적으로 완벽하진 않지만 실제로 좋은 결과를 내는 알고리즘이다. Counting방식을 사용하기도 하고 doubly linked list를 사용하기도 한다. 후자의 경우 연산이 무거워진다.

 

LRU Approximation (Second chance algorithm)

LRU의 개선판이다. 같은 방식이지만 자료구조를 개선한 것으로 실제로 가장 많이 사용된다. LRU를 아주 정확하게 검사하고 저장하여 수행하는 것이 아니라 '대충' 오래된것 같은 것을 검사하는 방식이다. 

페이지를 Circular Queue로 구성하고 각 페이지마다 reference bit를 0으로 초기화 한다. 그리고 어떤 페이지가 실제로 호출되어 사용되면 1로 바꾼다. page replace라고 할때 현재 포인터가 가리키고 있는 page가 0이라면 swap out한다. 반면 1이라면 0으로 바꾸고 다음 페이지를 확인한다. 이런식으로 하면 포인터가 한번 순회 할때마다 페이지가 최근에 사용 되었는지 아닌지 갱신이 되기 때문에 아직까지 0인 페이지는 최소한 일정 시간동안은 사용되지 않았다는 것이다. 그리고 지속적으로 사용되는 페이지는 계속 1로 갱신되기 때문에 쫓겨나지 않게된다.

 

LFU Algorithm

가장 적게 사용된 페이지를 쫓아낸다. 아주 예전에 많이 사용되고 현재는 사용되지 않는 페이지가 계속 남아있고, 최근에 자주 사용되기 시작한 페이지가 계속 쫓겨나는 상황이 생길 수 있다.

 

MFU Algorithm

가장 많이 사용된 페이지를 쫓아낸다. 가장 많이 사용됐으면 앞으로 사용될 확률이 적다고 예상 하는 것인데, LRU에서 봤듯이 실제로는 반대이다. 아무데서도 안쓴다.

 

 

Thrashing

Paging Replacement 오버헤드가 극대화된 경우. 시스템에서 아무것도 못하는 상태이다. Virtual Memory를 사용하지 않으면 thrashing이 발생 할 일이 없다. 그리고 메모리가 충분하면 또 Thrashing이 발생 할 일이 없다.

Locality를 다 합친 전체 size보다 total memory size가 더 크다면 Thrashing은 발생하지 않는다. 그렇지 않으면 Thrashing이 발생할 가능성이 생긴다. (무조건 발생 하는것은 아니다)

 

Working-set Model

이것을 이용한 Thrashing 해결법 중 하나가 working-set model이다. working-set 모델은 간단하게 말해서 locality를 근사하는 모델로, 자주 참조하는 페이지 집합들을 메모리에 상주시키는 것이다. 페이지 부제 및 페이지 교체 현상을 줄일수 있다.