Virtual Memory에 대해서 알아보자

* 본 내용은 운영체제를 공부하며 추후 복습하기 위해 포스팅하는 게시물입니다.

 

현대의 운영체제는 메모리와 프로세스를 Page 단위로 분할하는 Paging 기법을 사용한다.

이해가지 않는다면 이전 포스팅 참고 → javairus.tistory.com/53?category=973522

Memory Management에 관해서 알아보자

CPU가 명령어를 실행할 때 필요한 Page만 메모리에 할당하는 방식을 Demand Page라 한다. 즉, 프로그램이 실행될 때 프로그램의 모든 Page를 메모리에 할당하지 않고 메모리에 여러 프로그램을 할당함으로써(degree of Multiprogramming) 메모리를 효율적으로 사용할 수 있다.

ex) JVM 런타임 로딩 등

 

CPU가 프로세스를 실행할 때 Logical Address를 통해 메모리에 접근하기 위해 Page 엔트리를 참고한다.

이 때, 엔트리의 Valid/Invalid bit를 통해 해당 Page가 현재 메모리에 올라왔는지 아니면 사용되지 않는 Page인지 알 수 있다.  Valid로 표시되어 있다면 메모리에 할당받아 메모리에 존재하는 상태인 반면에 Invalid로 표시되어 메모리에 존재하지 않음을 의미한다.

 

그렇다면 Invalid 표시가 되어있을 때 Page를 메모리에 어떻게 할당하는지 알아보자 

 

 

1) 디스크로부터 메모리에 Page를 할당받아야(Invalid) 한다면 Page Fault를 발생시켜 CPU의 제어권을 OS에게 할당한다.

2) Page 테이블의 엔트리가 접근할 수 있는 Page인지, Page number가 offset의 범위에 벗어나진 않았는지 체크한다.

3) 2)의 결과에서 접근 가능하며 offset의 범위도 벗어나지 않았다면, 메모리에서 비어있는 Page Frame를 찾는다.

4) 만약 비어있는 Page Frame이 존재하지 않는다면 Replacement Algorithm으로 디스크로 이동시킬 Page를 선택하여 이동시킨다. (이 때, Page 엔트리 Invalid bit를 Invalid로 수정)

5) OS는 디스크로부터 메모리에 할당하기 위해 I/O를 한다.(Page Fault가 발생한 프로세스는 BLOCK 처리)

6) I/O를 대기할 동안 다른 프로세스에게 CPU를 할당한다.

7) I/O가 완료되면 인터럽트를 발생시켜 OS에게 CPU를 할당한다.

8) OS는 Page를 메모리에 할당하고, 엔트리의 Valid bit를 수정하며 BLOCK 처리된 프로세스를 READY 상태로 변경한다. (READY 큐에 대기한 후 Dispatcher에 의해 CPU 할당)

 

Replacement Algorithm

- 메모리에 존재하는 Page Frame 중 어떤 Page를 디스크로 Swap out 할 것인지 결정하는 Algorithm이다.

- 최적의 알고리즘을 Optimal Algorithm이라하며, 프로세스가 Page의 사용순서를 알고 있다는 전제하에 가장 늦게 사용할 Page를 선택하여 Swap out 하는 방식이다.

- Optimal 알고리즘을 구현하는 문제로는 BOJ - 멀티탭 스케줄링 문제가 있다.

www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 - 프로세스를 실행할 때 미래의 어떤 Page를 사용할지 알 수 없기 때문에 Optimal Algorithm은 사용할 수 없으며 다른 Algorithm의 지표가 된다.

 - Replacement Algorithm의 시간복잡도는 O(1) 이나 O(logn)을 지향해야한다.(O(n)은 너무 느려서 사용할 수 없다)

 - LRU(Least Recently Used), LFU(Least Frequently Used), Clock Algorithm이 존재한다.

 

1) LRU(Least Recently Used)

• 사용된지 가장 오래된 Page를 선택(오래된 날짜를 선택)
• Double LinkedList로 구현가능하며 시간복잡도는 O(1)
• 구현이 상대적으로 쉽다.

2) LFU(Least Frequently Used)

• 참조된 횟수가 가장 적은 Page를 선택
• Min Heap으로 구현가능하며 시간복잡도는 O(logn)
• 참조횟수가 가장 작은 Page가 여러 개 존재한다면 여러 Page 중 LRU를 통해 선택할 수 도 있음

3) Clock

• 실제로 LRU와 LFU Algorithm은 사용할 수 없어 사용하는 Algorithm (메모리 Page Frame에 접근할 때 OS가 관여하지 않고 MMU가 관여하기 때문에 오래된 정보나 참조된 횟수를 저장할 수 없음)
• Page 엔트리의 reference bit와 modified bit를 이용
• MMU가 Page가 참조할때 reference bit를 0 -> 1로 변경하며 Page가 메모리에 할당된 후 write 연산이 한번이라도 수행되었다면 modified bit를 1로 변경한다.
• 교체할 Page를 고르기 위해 reference bit를 확인하는데 reference bit가 1이면 0으로 변경하고 넘어가며 0이면 해당 Page를 디스크로 Swap out하는 방식(modified bit가 1일경우 수정된 부분을 디스크에 저장해야하므로 modified bit가 0인 Page를 찾는 경우 저장하는 연산을 하지않아 효율적이다.)

* Page를 Replace를 하기 위해 Global과 Local 2가지 전략이 존재

* Global : 프로그램에게 Page Frame을 할당하지 않고 Replacement Algorithm을 적용하는 방식

* Local : 프로그램에게 일정한 Page Frame을 할당하여 프로그램에 할당된 Page Frame 내에서만 Replacement Algorithm을 적용하는 방식으로 프로그램에 Page Frame을 동등하게 혹은 프로그램 크기에 비례하게, 우선순위에 비례하게 할당하는 방법이 존재하다. 

 

Thrashing

Page Falut가 발생하면 CPU의 제어권이 OS에게 넘어가며 사용자 프로세스에서 OS로 Context Switch와 I/O가 발생한다. 그래서 적정량의 Page Frame을 프로그램에 할당하지 않는다면 빈번하게 Page Falut가 발생한다.  Page Fault가 빈번히 발생하면 CPU의 사용률이 저하되며 OS는 CPU 사용률을 보고 메모리에 더 많은 프로그램을 할당한다. 위의 과정이 되다보면 CPU가 프로그램을 실행할 때마다 Page Fault가 발생하여 CPU를 더 이상 사용할 수 없는 상태가 되는데 이를 Thrashing이라 한다.

 

Thrashing을 방지하기 위한 Working Set, FPP Algorithm이 존재한다.

Allocation Algorithm

1) Working Set

 - 특정시간(델타)동안 사용된 Page 수를 Working Set으로 지정(Working Set은 가변적)

 - 지정된 Working Set보다 할당받을 수 있는 Page Frame이 작을 시 모든 Page를 반납한 후 Swap out 한다.(suspend)

 - Swap out을 통해 Thrashing을 방지한다.

 

2) PFF(Page Fault Frequency)

 - 실제 Page Fault rate의 상한과 하한을 정하여 상한을 넘을 시 Page Frame을 더 할당하며 하한보다 적을 시 할당되었던 Page Frame을 빼앗는다

 - 프로세스가 상한이 넘어 Page Frame을 할당받을 때 가용 Page Frame이 없을경우 해당 프로세스를 Swap out 한다.(suspend)