[운영체제] 09 Virtual Memory

내용 출처

KOCW 반효경 교수님 <운영체제> 강의
책 <운영체제와 정보기술의 원리>

반효경 교수님의 <운영체제> 강의 내용을 기반으로 정리했으며,

교수님의 저서 <운영체제와 정보기술의 원리>에서 추가할 만한 내용을 이와 같은 인용문 형식으로 추가함.

이 포스팅의 모든 이미지는 <운영체제> 강의에서 가져왔습니다.

---

Demand Paging

(이 챕터부터는 메모리 관리 기법 중 페이징 기법을 사용하는 것으로 가정한다.)

• 실제로 필요할 때 page를 메모리에 올리는 방식

  • I/O 양의 감소
  • 메모리 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용

• Valid / Invalid bit의 사용

  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry가 invalid로 초기화되어 있다.
  • 주소 변환 시에 invalid bit이 set되어 있으면
    => page fault (CPU는 운영체제로 넘어간다.)

오른쪽 원통 : backing store

G, H는 사용되지 않는 페이지이므로, 페이지 테이블의 6, 7번은 invalid로 표시한다. 1, 3, 4번 페이지는 프로그램에 의해 사용되지만, 이 페이지들이 물리적 메모리에 올라와 있지 않고 swap area에 내려가 있으므로 invalid로 표시한다.

Page Fault

• invalid page를 접근하면 MMU가 page fault trap을 발생시킨다.

• 커널 모드로 들어가서 page fault handler가 invoke된다.

• 다음의 순서로 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 Fault Rate가 p일 때,

Effective Access Time = (1 - p) x memory access + p

페이지 교체

• Page Replacement

  • 빈 프레임이 없을 경우, 페이지를 쫓아내는 것을 의미한다.
  • 어떤 프레임을 빼앗아올지 결정해야 한다.
  • 곧바로 사용되지 않읗 페이지를 쫓아내는 것이 좋다.
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있다.

• Replacement Algorithm

  • Page-Fault Rate을 최소화하는 것이 목표
  • 주어진 page reference string에 대해 page fault를 얼마내 내는지 조사하는 방식으로 평가한다.
  • reference string의 예
    1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1) 쫓겨난 페이지에 대한
2) 테이블 엔트리의 bit를 invalid로 바꾸고
3) 메모리에 새로 올라온 페이지에 대해서는
4) 그 프레임 번호를 테이블 entry에 적어주고 bit를 valid로 바꿔준다.

최적 알고리즘

Optimal : page fault를 가장 적게 만드는 알고리즘
가장 먼 미래에 참조되는 페이지를 replace한다.

Belady’s Optimal Algorithm, MIN, OPT 등으로 불린다.

빨간색 : page fault / 연보라색 : 메모리에서 직접 참조

하지만 실제로는 어떤 페이지가 언제 참조될 지를 미리 알 수 없다. 이 알고리즘은 이를 미리 알 수 있다는 가정에 기반한다. 그래서 실제 시스템에서 온라인으로 사용할 수는 없으므로 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 : 가장 덜 빈번하게 사용된 페이지를 쫓아낸다.

• 최저 참조 횟수 page가 여럿 있는 경우

  • LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다.
  • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수 있다.

• 장단점

  • LRU 처럼 직전 참조 시점만 보는 것이 아니라 장기적으로 시간 규모를 보기 때문에 Page의 인기도를 좀 더 정확히 반영할 수 있다.
  • 참조 시점의 최근성을 반영하지 못한다.
  • LRU보다 구현이 복잡하다.

페이지 참조 횟수를 계산하는 2가지 방식

1. Incache-LFU

• 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트하는 방식
• 페이지가 메모리에서 쫓겨났다가 다시 들어온 경우 참조 횟수는 1부터 다시 시작한다.

2. Perfect-LFU

• 메모리에 올라와 있는지의 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트하는 방식
• 페이지의 참조 횟수를 정확히 반영할 수 있지만, 메모리에서 쫓겨난 페이지의 참조 기록까지 보관해야 하므로 오버헤드가 크다.

LRU와 LFU의 구현

LRU : 연결 리스트로 구현한다. 참조 시간 순서로 한 줄로 줄세운다. 아래로 갈수록 최근에 참조된 페이지다. 새로운 페이지를 참조할 경우 맨 아래로 보내면 되므로 시간복잡도는 O(1)이다.

LFU : 아래로 갈수록 가장 많이 참조된 페이지가 되도록 연결 리스트로 구현할 수 있다. 그런데 이 경우 새로운 페이지를 참조할 때, 페이지 참조 횟수를 일일이 비교해야 하므로, 시간복잡도는 O(n)가 된다. 그래서 보통 LFU 알고리즘은 힙으로 구현하며, 이때 시간복잡도는 O(log n)이 된다.

다양한 캐싱 환경

• 캐싱 기법
  한정된 빠른 공간(캐쉬)에 요청된 데이터를 저장해 두었다가, 후속 요청시 캐쉬로부터 직접 서비스하는 방식

  • paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용된다.
    (cache memory, buffer caching 등은 단일 시스템에서 저장 매체들 간의 속도 차이 때문에 캐싱을 한 것이다. 반면 웹 캐싱의 경우 지리적으로 멀리 떨어진 정보를 웹 서버로부터 불러오는 데 시간이 걸리므로, 이 정보를 저장해서 같은 정보가 필요할 때 저장한 정보를 사용하는 방식이다.)

• 캐쉬 운영의 시간 제약

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

[paging system인 경우] 부분 설명

주소 변환 시 해당 페이지가 이미 물리적 메모리에 올라와 있는 경우, 직접 그 내용을 읽어서 CPU로 가져온다. 이러한 주소 변환에서 운영체제가 하는 역할은 없다.

반면 주소 변환 시 물리적 메모리에 해당 주소가 없는 경우, page fault가 발생한다. 이때는 디스크 접근을 필요로 하는데, 프로세스는 디스크에 직접 접근할 수 없다. 따라서 page fault trap이 발생하고, CPU 제어권이 운영체제로 넘어간다. 그러면 운영체제가 디스크에 있는 페이지를 읽어서 물리적 메모리에 올려놓고, 그 과정에서 필요시 이미 올려진 페이지 중 하나를 쫓아내야 한다.

결국 운영체제는 프로세스가 요청한 페이지가 메모리에 올라와 있지 않은 경우에만, 해당 페이지의 참조를 확인할 수 있다. 이미 메모리에 올라온 페이지가 다시 참조되는 경우에는 페이지가 참조되었다는 사실을 알 수 없다. 따라서 운영체제는 어떤 페이지가 가장 최근에 참조되었는지, 혹은 어떤 페이지의 참조 빈도가 높은지를 알 수 없다. 그래서 paging system에서는 LRU나 LFU 알고리즘을 사용할 수 없다. (단, 버퍼 캐싱이나 웹 캐싱에서는 사용 가능하다.)

그래서 사용되는 알고리즘이 바로 Clock Algorithm이다.

Clock 알고리즘

• Clock algorithm

  • LRU의 근사 알고리즘

  • 다른 명칭

    • Second chance algorithm
    • NUR (Not Used Recently)
    • NRU (Not Recently Used)

  • 운영체제는 가장 오래 전에 참조된 페이지를 알 수 없으므로, 대신 최근에 사용되지 않은 페이지를 쫓아낸다.

  • reference bit을 사용해서 교체 대상 페이지를 선정한다.

  • reference bit이 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.

  • 포인터를 이동하는 중 reference bit 1은 모두 0으로 바꾼다.

  • reference bit이 0인 것을 찾으면 그 페이지를 교체한다.

reference bit이 0이라는 것은 시계 바늘이 한 바퀴 돌아오는 동안 그 페이지에 대한 참조가 없었다는 것을 의미한다.

reference bit이 1이라는 것은 시계 바늘이 한 바퀴 돌아오는 동안 그 페이지에 대한 참조가 적어도 한번은 있었다는 것을 의미한다.

• Clock algorithm의 개선
  • reference bit와 modified bit (dirty bit)을 함께 사용한다.
  • reference bit = 1 : 최근에 참조된 페이지
  • modified Bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지)

페이지가 read가 아닌 write로 참조되는 경우, 하드웨어가 modified bit을 1로 세팅한다.

어떤 페이지를 쫓아낼 때 그 페이지의 modified bit이 0이라면, 그 페이지는 backing store에서 물리적 메모리로 올라온 이후로 write가 발생하지 않은 것이다. 그래서 이 경우 이미 같은 copy가 backing store에 있으므로 그냥 쫓아내기만 하면 된다.

반면 쫓아내고자 하는 페이지의 modified bit이 1이라면, 그 페이지는 물리적 메모리로 올라온 이후로 적어도 한 번은 CPU에서 write를 한 것이다. 이 페이지는 내용이 수정되었으므로, 쫓아낼 때 backing store에 수정된 내용을 반영한 후에 쫓아내야 한다.

페이지 프레임의 할당

• Allocation Problem

  • 각 프로세스에 얼마만큼의 페이지 프레임을 할당할 것인가?

• Allocation의 필요성

  • 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시에 참조한다.
    • 명령어 수행을 위해 최소한 할당되어야 하는 프레임의 수가 있다.
  • loop를 구성하는 페이지들은 한꺼번에 할당되는 것이 유리하다.
    • 최소한의 allocation이 없으면 loop마다 page fault가 발생한다.

• Allocation Scheme

  • Equal allocation : 모든 프로세스에 똑같은 개수로 할당
  • Proportional allocation : 프로세스의 크기에 비례하여 할당
  • Priority allocation : 프로세스의 우선순위에 따라 다르게 할당

전역 교체 vs 지역 교체

• Global replacement
  • Working Set, PFF 알고리즘 등을 사용하면 그때그때 프로세스별로 메모리 할당량이 자동으로 조절되므로, 미리 할당하지 않는다.
  • replace 시 다른 프로세스에 할당된 프레임을 빼앗아 올 수 있다.
  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당한다.

이는 프로세스별 프레임 할당량을 조절하는 또 다른 방법이 될 수 있다. 전체 시스템 차원에서 더 자주 참조되는 페이지가 메모리에 올라가기 때문에 프로세스의 프레임 할당량이 스스로 조절될 수 있는 것이다.

• Local replacement
  • 프로그램에 미리 할당을 해놓은 다음, replacement가 필요할 때 자신에게 할당된 페이지를 쫓아낸다.
  • 자신에게 할당된 프레임 내에서만 replacement
  • FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영하는 경우

스레싱

• Thrashing (스레싱)

  • 프로세스의 원활한 수행에 필요한 최소한의 페이지 프레임 수를 할당 받지 못한 경우 발생한다.
  • 메모리에 너무 많은 프로그램이 동시에 올라가면, 각 프로그램이 가지고 있는 메모리 용량이 매우 작아진다. 이러한 경우 page fault가 빈번하게 발생하므로, CPU 이용률이 낮아진다.
  • 그런데 OS는 CPU 이용률이 낮아졌으므로, MPD(Multiprogramming degree)를 높여야 한다고 판단한다.
  • 그래서 또 다른 프로세스가 시스템에 추가되어, MPD가 더욱 높아진다.
  • 따라서 프로세스 당 할당된 프레임의 수가 더욱 감소한다. 이는 더 높은 page fault rate로 이어지게 된다.
  • 대부분의 CPU는 한가하며, 프로세스는 페이지를 swap in / swap out하느라 매우 바빠진다.
  • low throughput

스레싱을 방지하기 위해서는, 동시에 메모리에 올라가 있는 프로세스의 개수를 조절해야 한다. 이를 가능하게 해주는 알고리즘이 Working-Set 알고리즘과 PFF 알고리즘이다.

Working-Set 알고리즘

• Locality of reference (참조 지역성)

  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
  • 집중적으로 참조되는 해당 페이지들의 집합을 locality set이라고 한다. Working-Set 알고리즘에서는 이러한 set을 working-set이라고 한다.

• Working-Set Model

  • Working Set : Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 페이지들의 집합
  • Working Set 모델에서는 프로세스의 Working Set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 프레임을 반납한 후 swap out한다.
  • mulitprogramming degree를 조절하여, 스레싱을 방지한다.

• Working set의 결정
  • Working set window를 통해 알아낸다.
  • window size가 Δ인 경우 (위 그림에서는 10)
    • 시각 $t_j$에서의 working set WS ($t_j$)
      • time interval [$t_j$ - Δ, $t_j$] 사이에 참조된 서로 다른 페이지들의 집합
      • working set에 속한 페이지는 메모리에 유지하고, 속하지 않은 것은 버린다.
        (즉, 참조된 후 Δ 시간 동안 해당 페이지를 메모리에 유지한 후 버린다.)

• 프로세스들의 working set size의 합이 페이지 프레임의 수보다 큰 경우

  • 일부 프로세스를 swap out시켜 남은 프로세스의 working set을 우선적으로 충족시켜 준다.

• working set을 다 할당하고도 페이지 프레임이 남는 경우

  • swap out되었던 프로세스에게 working set을 할당한다.

PFF 알고리즘

Page-Fault Frequency

직접 현재 시점의 page fault를 계산하고, page-fault를 많이 일으키는 프로그램에 더 많은 페이지를 부여한다.

• page-fault rate의 상한값과 하한값을 둔다.
  • page-fault rate가 상한값을 넘으면 프레임을 더 할당한다.
  • page-fault rate가 하한값 이하이면 할당 프레임 수를 줄인다.
• 빈 프레임이 없으면 일부 프로세스를 swap out한다.

Page size의 결정

• Page size를 감소시키면
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • 내부 조각 감소
  • disk transfer의 효율성 감소
    • 디스크는 디스크 헤드가 이동하면서 seek를 하는데, 이 시간이 오래 걸린다. 그래서 가능하면 디스크 헤드가 한 번 이동해서 많은 정보를 읽어서 메모리에 올리는 것이 좋다.
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • locality의 활용 측면에서는 좋지 않다.