빽 투더 기본기 [OS 8편]. 가상 메모리 관리

1. 가상 메모리 개념

1.1. 등장 배경

• 프로그램을 실행하는 동안, 우리는 프로그램이 필요로 하는 모든 메모리를 동시에 사용하지 않는다.
• 즉, 현재 프로세스가 필요로 하는 메모리만, 메인 메모리에 로드하고, 추후 실행될 영역은 보조 메모리에 저장해둔다.
  필요할 때만 Swapping (메인 메모리 <-> 보조 메모리) 하면 되는 셈.
• 이렇게 하면, 메인 메모리보다 큰 프로그램을 실행시킬 수 있다.
• 이렇게, 보조 메모리를 활용한 메모리 시스템을 가상 메모리 시스템이라고 한다.

1.2. Demand Paging

1) 개념

• 요구 페이징(Demand Paging) 은 페이징 시스템에 Swapping을 결합한 것.
  위에서 설명한 것과 같다.
• Swapping 을 요구 될 때만 하기 때문에, lazy swapper 라고도 부르고, 페이징 시스템에서는 pager 라고도 함.

2) Valid-Invalid Bit

• 해당 페이지가 메인 메모리에 적재 되어있는지 아닌지를 나타내주는 비트
  적재되어있으면 1, 아니면 0이다.
• 페이지 테이블에 각 페이지 별로 이 비트를 가지고 있다.
• 만약 현재 명령어로 넘어온 페이지 넘버의 Valid-Invalid Bit 가 0이면 CPU 에 인터럽트를 준다. 이를 Page fault 라고한다.

3) Page Fault

• Page Fault 의 신호는 크게 2 종류로 나뉜다.
  • 메인 메모리에 없어서, 이를 가상 메모리에서 메인 메모리로 적재하라는 신호
  • 유효하지 않은 페이지 넘버 접근 신호. 이 신호는 그냥 무시해버린다.
• Page Fault 가 발생한 경우, 해당 프레임을 메인 메모리에 올린 뒤,
  페이지 테이블에서 해당 페이지의 Valid-Invalid Bit 를 1로 설정해준다.

• Page Fault 로 인한 I/O 작업은 CPU 의 효율성을 낮추는데, 이 때 평균 메모리 접근시간은 다음과 같이 계산될 수 있다.
  • p : Page Fault Rate
  • EAT = (1-p) * (메모리 접근시간) + p * (page fault overhead + swap in-out + restart overhead)
• 메인 메모리가 꽉 차 있고, 여기에 없는 페이지가 참조되는 경우 Page Fault 는 반드시 일어나게 된다. 그럼 기존의 메인 메모리에 올라간 페이지를 Swap-out 시켜야 하는데, 이 때 어떤 페이지를 Out 시켜야 할까?
  • Page fault 가 최대한 안 일어나게, Out 시킬 페이지를 '잘' 골라야 한다.
  • 따라서, 이제 이슈는 이를 잘 고를 수 있는 알고리즘, Page Replacement 가 된다.

---

2. Page Replacement

기본적으로 가상 메모리 시스템 전제 하에, 메인 메모리에 모든 프레임이 할당되어있는 상황에서 발생한다.

Page Replacement 알고리즘의 주요 목표는, Page fault 가 덜 일어나도록 Swap out 할 페이지를 고르는 것이다. 이렇게 Swap out 할 페이지를 담고있는 프레임을 Victim frame 이라고 한다.

여러 Page Replacement 알고리즘들을 소개하기 앞서, 먼저 이 알고리즘들의 성능 평가 하기 위한 Page Reference String이라는 개념을 먼저 알아야 한다.
그림으로 설명하는게 더 빠를듯 하다.

출처 : http://contents.kocw.or.kr/KOCW/document/2013/kyungsung/yangheejae/os05.pdf

즉, 위 프로세스 실행에서 참조한 페이지는 순서대로 1, 4, 6, 1, 6 이다. 이를 Page reference string 이라고 한다. 앞으로 주소 단위가 아닌 이 String 기준으로 인풋을 받아 알고리즘을 비교한다.

 

2.1. FIFO (First In First Out)

말 그대로, 메인 메모리가 꽉 찼을 경우 가장 처음에 들어온 페이지가 Victim 페이지가 되는 알고리즘이다.

직관적이지만, 당연히 제일 안좋다.
프레임의 수가 많아지면 당연히 Page fault 의 수가 줄어들어야 하는데, 이 알고리즘은 그렇지 않은 어떤 지점을 가지고 있다. 이를 Belady's Anomaly 문제라고 한다.

 

2.2. OPT (OPTimal)

가장 오랫동안 사용되지 않을 페이지를 Victim 페이지로 둔다.

출처 : http://faculty.salina.k-state.edu/tim/ossg/Memory/virt_mem/page_replace.html

이상적이고 제일 좋긴하지만, 현재 메인 메모리에 올라온 페이지 중 어떤 페이지가 제일 오랫동안 사용되지 않을지 예측해야한다. 이게 매우 어렵다.
따라서, 다소 이상적이고 이론적인 알고리즘이다.

 

2.3. LRU (Least Recently Used)

현재 메인 메모리에 올라온 페이지 중, 사용한지 가장 오래된 페이지를 Victim 페이지로 둔다.
가장 널리 사용되는 방법이다.

출처 : http://faculty.salina.k-state.edu/tim/ossg/Memory/virt_mem/page_replace.html

이를 구현하는 방법은 다음과 같다.

1) 하드웨어 지원이 있는 경우

• Counter-based
  • 말그대로, 페이지가 메인 메모리에 적재된 시간을 담아둔다.
  • 이 시간은 Page reference stream 을 읽을 때마다 1씩 증가한다.
  • Page replacement 가 일어날 때, Victim 페이지는 이 Count 가 제일 큰 페이지가 된다.
• Stack-based
  • 스택의 Bottom 이 항상 Victim 페이지가 되고, Top 은 항상 가장 최근에 사용한 페이지가 된다.
  • 카운터 기반은 제일 큰 Count 를 위한 리스트 탐색이 필요하지만, 스택 기반은 탐색이 필요없다.
  • 다만, 매번 스택을 업데이트 해줘야하는 비용이 든다.

2) 하드웨어 지원이 없는 경우

• Additional Reference Bit 알고리즘
  • 페이지 테이블 엔트리의 각 페이지마다 8개의 참조비트를 둔다. 모두 0으로 초기화 한다.
  • 일정한 시간 간격으로, 페이지 테이블에서 어떤 페이지들이 메인 메모리에 올라갔는지 본다. (Valid-Invalid bit 참고)
  • 올라가있는 페이지는 8개의 참조비트 중 최상단 비트를 1로 만든다.
  • 그리고 오른쪽으로 Shift 한다. 다시 일정한 시간 뒤에, 두 번째 과정을 반복한다.
  • Victim 페이지는 이 참조비트를 10진수화 하였을 때, 가장 작은 페이지가 된다.
  • 즉 일정한 시간 간격동안, 가장 참조가 안된 페이지는 이 비트수가 가장 작을 것이다.
  • 메모리에 올라온 페이지마다 8비트씩 할당해줘야 하므로, 기존보다 메모리를 많이 쓴다.

• Second Chance 알고리즘
  • FIFO와 Reference bit 를 기반으로, 말 그대로 한 번의 기회를 더 주는 알고리즘이다.
  • 순환 큐로 페이지들을 구성하고, 모든 Reference bit 는 메모리에 올라온 페이지별로 1로 초기화한다.
  • 큐를 순회하는 하나의 포인터가 있는데, 이 포인터가 가리키는 페이지가 Victim 페이지의 후보가 된다.
  • Page replacement 상황이 발샐하면, 현재 포인터가 큐를 순회한다.
  • 포인터가 가리키는 페이지의 Reference bit 가 1이면 0으로 바꾼다.
    포인터가 가리키는 페이지의 Reference bit 가 0이면 해당 페이지가 Victim 이 된다.
  • 즉 1일 때, 0으로 바꿔주어 한 번 더 기회를 주는 것이다.
    만약 모든 Reference bit 가 1이었다면, 모든 페이지의 bit 는 0 이 되고, 결국 가장 처음에 들어온 페이지가 Victim 이 될 것이다.

• Enhanced Second Chance 알고리즘
  • 기존 Reference bit 에 Modify bit 를 추가해 총 2 bit 를 사용한다.
  • 즉 (0, 0), (0, 1), (1, 0), (1, 1) 의 4개의 경우가 있다.
  • 오른쪽으로 갈수록 Victim 이 될 우선순위가 낮다.
  • Modifiy bit 를 통해, 우선 순위를 더 세분화 하긴 했지만, 그만큼 탐색 시간이 더 든다.

 

2.4. Counting Based

현재 메모리에 올라와있는 페이지들이 이전에 얼마나 참조(이용) 되었는지 그 수를 카운팅해둔다. 이 후에는 다음과 같은 2가지 알고리즘이 있다.

• LFU (Least Frequently used) 알고리즘
  • 가장 적게 사용된 페이지를 Victim 으로 둔다.
  • 즉, 지금까지 가장 적게 사용된 페이지는 앞으로도 사용할 일이 적을 것이라고 보는 것
  • 문제는 다음과 같다.
    • 초기에 많이 사용되었지만 이후 사용되지 않는 코드가 계속 메인 메모리에 상주하게 된다는 점
    • 처음으로 교체되어 들어온 페이지가 바로 교체될 수 있다는 점
• MFU (Most Frequently used) 알고리즘
  • 가장 많이 사용된 페이지를 Victim 으로 둔다.
  • LFU 와 반대로, 가장 많이 사용된 페이지는 앞으로 사용할 일이 적을 것이라고 보는 것

근데 둘 다 거의 사용되지 않는다고 한다.

---

3. Allocation of Frames

프로세스마다, 프레임을 기본적으로 얼마씩 할당해줘야 할까? 에 대한 이슈다.
만약, 프로세스마다 실제로 필요한 프레임보다 너무 적게주면, Page fault 가 자주 일어날 것이고, 많이 주면, 다른 프로세스에서 Page fault 가 자주 일어날 것이다.
즉, 물리 메모리 공간은 한정적인데, 이를 어떻게 프로세스마다 잘 분배할 수 있을까?

3.1. 할당 방법

• 균등 할당
  • 그냥 모든 프로세스에 현재 가용한 물리 메모리를 균등하게 할당하는 방법
  • 예를 들어, 가용한 100개의 프레임과, 4개의 프로세스가 있을 때, 각 프로세스당 25개의 프레임을 할당하는 것.
• 비례 할당
  • 각 프로세스 크기에 비례하여 할당하는 방법
  • 예를 들어, 가용한 100개의 프레임과, 50개 페이지로 구성된 프로세스 A, 150 페이지로 구성된 프로세스 B가 있을 경우,
    프로세스 A 에는 25개, 프로세스 B 에는 75개의 프레임을 할당하는 것.
• 우선순위 기반 할당
  • 우선순위를 별도로 두어, 우선 순위가 높은 프로세스에 더 많은 프레임을 할당하는 방법
  • 해당 프로세스는 Page fault 가 덜 일어나, 빠르게 수행된다.

 

3.2. Global vs Local replacement

• Global replacement
  • Page replacement 가 일어날 때, 현재 프로세스 페이지 외, 다른 프로세스의 페이지가 Victim 이 될 수 있다.
  • 우선 순위가 높은 프로세스에게 작은 프로세스를 희생하면서 할당된 프레임 수를 늘려줄 수 있다.
  • 즉, 프로세스의 성능이 외부 상황에 따라 변한다.
• Local replacement
  • Page replacement 가 일어날 때, 현재 프로세스 페이지 내에서만 Victim 페이지가 선택된다.

현재는 대부분 Global Replacement 를 사용한다.

---

4. Thrashing

4.1. 개념

Thrashing 은 계속하여 Page fault 가 일어나는 현상으로, CPU excute 시간 보다 Page fault를 처리하는 I/O 시간이 더 많아질 경우를 말한다.

지금까지의 내용을 정리하며, Thrashing 을 정의하면 다음과 같다.

한정된 자원 안에서 운영체제는 CPU의 효율성을 높이기 위해 보다 많은 프로세스를 동시에 실행시키기 위해 메모리에 많은 프로세스를 올리게 됩니다.

이로써 CPU 효율성은 높아지게 됩니다. 하지만 동시에 실행 중인 프로세스의 수가 많아질수록 하나의 프로세스가 할당받는 자원의 양은 점점 적어지게 됩니다.

그렇게 된다면 할당받는 Frame의 수도 적어지게 되는데 이렇게 Frame의 수가 줄어들게 되면 그만큼 Page Fault가 많이 발생하게 되고 그렇다면 자원의 활용보다는 I/O 작업에 시간을 더욱 소비하게 됩니다. 이렇게 되면 프로그램의 진행속도는 굉장히 느려지고 CPU의 효율성 역시 굉장히 떨어지게 됩니다.

하지만 여기서 문제점은, 운영체제는 이러한 CPU 효율성의 저하를 극복하기 위해 메모리에 프로세스를 더욱 올리게 됩니다.

이런 악순환으로 CPU 효율성은 기하급수적으로 떨어지게 되고 결국에는 프로그램의 비정상적인 종료로 이어지게 되고

이러한 현상을 Thrashing이라고 합니다.

출처 : https://richong.tistory.com/63?category=711152

 

4.2. 원인

쓰레싱이 발생하는 원인을 다시 정리하면 다음과 같다.

• 멀티 프로그래밍 환경
• 해당 프로세스가 필요로 하는 최소 프레임 개수 > 제공된 프레임 개수

특히 2번째 원인은 우리가 어느정도 해결가능한 부분이므로, 이제 이 부분을 집중적으로 다룬다.
즉 이제 이슈는 '해당 프로세스에 최소 몇 개의 프레임을 주어야 하는가?' 가 된다.

이를 해결하기 위해, Locality Model 이 등장한다.

Locality Model

프로세스는 페이지들 마다 지역성을 가진다고 생각하는 아이디어다.
Locality는 특정한 해당 시점에서 실행되기 위해 필요한 Page들의 집합이다.
즉, 그 Locality만큼을 담을 수 있는 Frame의 양을 할당해주면 Thrashing 현상을 막을 수 있다고 보는 것이다.

 

4.3. Working Set Model

1) 개념

• Locality Model을 기반으로 가장 많이 사용하는 페이지를 미리 저장해둔 것
• 먼저 Working set window 의 크기를 정해줘야 한다.
• 현 프로세스의 해당 시점으로부터, 과거의 Working set window 크기만큼의 instructions 를 보고, 얼마만큼의 페이지가 들어가있는지 확인한다.
  이 페이지들의 집합을 Working set (WS)이라 하고, 이 크기를 Working set size (WSS)라고 한다.
• 이 모델대로라면, (모든 프로세스의 WSS의 합) > (실제 사용가능한 프레임 수) 일 경우에 Thrashing 이 일어나는 것이다.

2) Thrashing 해결 방법

• OS 는 프로세스들의 WS 를 모니터하며, WS 를 충분히 수용할 수 있는 프레임을 할당한다. (즉 할당되는 프레임 수는 매번 가변적일 수 있다.)
• 새 프로세스를 수용할 수 있을 만큼의 빈 프레임이 존재하면, 새 프로세스를 실행시킨다.
• 반대로, (모든 프로세스의 WSS의 합) > (실제 사용가능한 프레임 수) 일 경우, 하나의 프로세스를 일시 중단한다.

3) 정리

지역성을 표현하는 Working set을 메모리에 유지함으로써 스레싱을 방지하겠다는 것이다.
크기에 변동이 있으므로 Working set이 작아지면 프레임을 회수하고, 커지게 되면 그만큼 프레임을 더 할당해 주는 가변 할당이 필요하다는 것이다.