Virtual Memory

가상 메모리

메인 메모리의 크기는 한정되어 있다.

따라서 물리적인 메모리 크기보다 크기가 큰 프로세스는 실행시킬 수 없게 된다.

크기가 큰 프로세스를 실행시키기 위해서는 메인 메모리를 크게 키우는 방법이 있겠지만, 이것은 매우 비효율적이다. 따라서 나온 방법이 바로 가상 메모리(Virtual Memory)이다.

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
• I/O 양의 감소
• Memory 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용

극단적인 케이스로 프로세스를 실행할 때 어떠한 페이지도 메모리에 올리지 않고 시작할 수도 있다. 이를 Pure Demand Paging이라고 한다.

반대로 우선 필요할 것 같은 페이지를 메모리에 올려놓고 나중에 다른 페이지가 필요하면 다른 페이지를 메모리에 올리는 방법을 pre-paging이라고 한다.

필요한 페이지가 메모리에 존재할 수도 있고 Backing Store에 존재할 수도 있다.

이때 페이지가 메모리에 적재되어 있는지 판단할 방법이 필요하다. 여기서 이용하는 것이 Valid-Invalid Bit이다.

valid-invalid bit

• valid(1)
  • 페이지가 메모리에 존재한다는 뜻이고,
• invalid(0)
  • 페이지가 메모리에 존재하지 않는다는 뜻

페이지 테이블을 통해 논리주소에서 물리 주소로 접근할 때 valid(1)하다면 바로 해당 페이지를 접근하게 되고, 만약 invalid(0)하다면 Page Fault가 발생한다.

Page Fault 과정

1. 사용되지 않는 주소 영역에 속한 페이지 접근을 시도하거나 해당 페이지에 대한 접근 권한 위반 (ex. 읽기 전용 페이지에 쓰기 접근 시도)을 한 경우, 해당 프로세스를 종료
2. 빈 페이지 프레임을 가져온다. (없으면 뺏어온다 = replace)
3. 해당 페이지를 disk에서 memory로 읽어온다.
   • disk I/O가 끝날 때까지 이 프로세스는 CPU를 preempt 당한다.(프로세스의 상태는 block으로 만든다.)
   • disk read가 끝나면 page table entry에 기록한다.valid/invalid bit를 "valid"로 표시한다.
   • 준비 큐에 프로세스를 이동시킨다.
4. 이 프로세스가 CPU를 잡고 다시 running
5. 중단되었던 명령을 재개

페이지 교체

• Page Replacement
  • 빈 프레임이 없을 경우, 페이지를 쫓아내는 것을 의미한다.
  • 어떤 프레임을 빼앗아올지 결정해야 한다.
  • 곧바로 사용되지 않읗 페이지를 쫓아내는 것이 좋다.
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있다.
• Replacement Algorithm
  • Page-Fault Rate을 최소화하는 것이 목표
  • 주어진 page reference string에 대해 page fault를 얼마내 내는지 조사하는 방식으로 평가한다.

페이지 교체 알고리즘 (Page Replacement Algorithm)

최적 알고리즘

• Optimal : page fault를 가장 적게 만드는 알고리즘
• 가장 먼 미래에 참조되는 페이지를 replace한다.
• Belady’s Optimal Algorithm, MIN, OPT 등으로 불린다.

실제로는 어떤 페이지가 언제 참조될 지를 미리 알 수 없다.

이 알고리즘은 이를 미리 알 수 있다는 가정에 기반한다.

그래서 실제 시스템에서 온라인으로 사용할 수는 없으므로 Offline algorithm 이라고 한다.

다만 다른 알고리즘의 성능에 대한 upper bound를 제공하는 역할을 수행한다.

FIFO 알고리즘

First In First Out : 메모리에 먼저 들어온 페이지를 먼저 쫓아낸다.

FIFO Anomaly (Beladys Anomaly)

페이지 프레임의 수를 늘려주었을 때 오히려 page fault가 증가하는 상황

LRU 알고리즘

Least Recently Used : 가장 오래 전에 참조된 페이지를 쫓아낸다.

• 시간지역성 (temporal locality)
  • 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질
• 실제로 가장 많이 사용되는 알고리즘이다

LFU 알고리즘

Least Frequently Used : 가장 덜 빈번하게 사용된 페이지를 쫓아낸다.

• LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.

캐싱 기법

• 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스 하는 방식
• paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용

캐시 운영의 시간 제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
• Buffer caching이나 Web caching의 경우
  • O(1) 에서 O(long n) 정도까지 허용
• Paging system인 경우
  • Page fault인 경우에만 OS가 관여함
  • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
  • O(1)인 LRU의 list 조작조차 불가능

Clock 알고리즘

• LRU의 근사 알고리즘
• 다른 명칭
  • Second chance algorithm
  • NUR (Not Used Recently)
  • NRU (Not Recently Used)
• 운영체제는 가장 오래 전에 참조된 페이지를 알 수 없으므로, 대신 최근에 사용되지 않은 페이지를 쫓아낸다.
• reference bit을 사용해서 교체 대상 페이지를 선정한다.
• reference bit이 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.
• 포인터를 이동하는 중 reference bit 1은 모두 0으로 바꾼다.
• reference bit이 0인 것을 찾으면 그 페이지를 교체한다.

참고

• 반효경 교수님 운영체제 강의