CS 정리 | OS | 8. 가상 메모리 | kocw 반효경 교수님

물리적인 메모리의 주소 변환은 OS가 관리하지 않는다 (HW가 관리) 그러나 virtual memeory 기법은 전적으로 운영체제가 관리한다 ! 🕵🏼‍♀️💭

Demand Paging

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

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

• Valid / Invalid bit의 사용
  

  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우 (그림에서는 논리적 주소 6, 7에 해당)
    • 페이지가 물리적 메모리에 없는 경우 (그림에서는 논리적 주소 1, 3, 4에 해당)
  • 처음에는 모든 page entry가 invalid로 초기화
  • address translation 시에 invalid bit가 set되어 있으면 page fault
    • 디스크에 접근해야하므로 OS에게 CPU 제어권이 넘어감

  Page Fault

  

• invalid page를 접근하면 MMU(주소 변환 기능을 하는 HW)가 trap을 발생시킴 (page fault trap)

• kernel mode로 들어가서 page fault handler가 invoke됨

• 아래의 순서대로 page fault를 처리한다.

  1. Invalid referance? (ex. bad address, protection violation) => abort
  2. Get an empty page frame (없으면 뺏어온다 : replace)
  3. 해당 페이지를 disk에서 memory로 읽어온다
     1. disk IO가 끝나기까지는 이 프로세스는 CPU를 preempt 당함 (block)
     2. disk read가 끝나면 page tables entry에 기록함 (valid/invalid bit = 'valid')
     3. ready queue에 precess를 insert -> dispatch later
  4. 이 프로세스가 CPU를 잡고 다시 running
  5. 아까 중단되었던 instruction을 재개

Performance of Demand Paging

page fault로 인해 디스크를 접근하는 것은 오래 걸리는 작업 이다.

Free frame이 없는 경우 (메모리가 가득 찬 경우)

• Page replacement
  
  • 어떤 frame을 빼앗아올지 결정해야 함
  • 곧바로 사용되지 않을 page를 쫒아내는 것이 좋음
  • 동일한 페이지가 여러 번 메모리에서 쫒겨났다가 다시 들어올 수 있음 -> 성능이 나빠짐
• Replacement Algorithm
  • page-fault rate를 최소화하는 것이 목표
  • 알고리즘의 평가
    • 주어진 page reference string에 대해 page fault를 얼마나 내는 지 조사
    • reference string의 예
      • 1,2,3,4,1,2,5,1,2,3,4,5

optimal Algorithm

• page fault를 가장 적게 하는 알고리즘
• 미래에 참조되는 페이지들을 이미 알고있다고 가정하여 알고리즘이 수행
• MIN (opt) : 가장 먼 미래에 참조되는 page를 replace
  
  • 빨간 부분이 page fault가 일어난 시점. 즉, 6번의 page fault가 발생하며, 이보다 적게 발생할 리 없음
• 미래의 참조를 어떻게 아는가?
  • offline algorithm (현실적으로 불가능)
• 다른 알고리즘의 성능에 대한 upper bound 제공
  • Belady's optimal algorithm, MIN, OPT 등으로 불림

FIFO Algorithm

• 먼저 들어온 것을 먼저 내쫓음
  
• FIFO Anomaly (Belady's Anomaly)
  • 더 많은 프레임이 제공된다고 해서 더 적은 page fault를 발생시키진 않는다

LRU & LFU Algorithm

• LRU (Least Recently Used)
  • 가장 오래 전에 참조된 것을 지움
    <- 이거 그림 LRU 방식이 아닌듯..?
• LFU (Least Frequently Used)
  • 참조 횟수(reference count)가 가장 적은 페이지를 지움
  • 최저 참고 횟수인 page가 여럿 있는 경우
    • LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다
    • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다
  • 장단점
    • LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음 (+)
    • 참조 시점의 최근성을 반영하지 못함 (-)
    • LRU보다 구현이 복잡함

LRU와 LFU 알고리즘의 구현

• LRU는 연결리스트 형태로 구현하며 O(1)의 시간복잡도를 가짐
• LFU는 힙 형태로 구현하며 O(logN)의 시간복잡도를 가짐
  • 참고로 힙 형태로 구현하기 않고 LRU와 같이 연결리스트 형태로 구현한다면 O(N)의 시간복잡도를 가지게 됨

다양한 캐싱 환경

• 페이징 기법에서는 메모리를 캐시라고 간주함
• 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식
• paging system외에도 cache memeory, buffer caching, web caching 등 다양한 분야에서 사용
• 캐시 운영의 시간 제약
  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 (O(n)) 실제 시스템에서 사용할 수 없음
  • Buffer caching 이나 Web caching의 경우
    • O(1)에서 O(logn) 정도까지 허용

Paging System에서 LRU, LFU 가능한가?

• 이미 메모리에 존재하는 page는 디스크 접근할 일이 없으므로 (= OS가 관여할 일이 없으므로) OS가 reference string의 모든 페이지의 참조(실제 메모리 적재) 여부를 알 수가 없다.
• 반대로 생각하면, page fault가 발생한 페이지만 관리할 수 있다.
• 결론적으론, LRU와 LFU는 paging System에서 사용 불가능한 기법이다 😡

Clock Algorithm

• LRU 근사 알고리즘
• 여러 명칭으로 불림
  • Second chance algorithm
  • NUR (Not Used Recently) 또는 NRU (Not Recently Used)
• reference bit을 사용해서 교체 대상 페이지를 선정한다 (circular list)
• 동작 과정
  • reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동시킨다.
  • 포인터 이동 중에 reference bit 1은 모두 0으로 바꾼다.
  • reference bit가 0인 것을 찾으면 그 페이지가 victim이 되어 교체한다.
  • 한 바퀴를 되돌아와서도 (=second chance) 0이면 그때에는 replace 당한다
  • 자주 사용되는 페이지라면 second chance가 올 때 1이 write되어있을 것이다.
• clock algorithmd의 개선
  • reference bit(access bit)과 modified bit(dirty bit)을 함께 사용한다
  • reference bit == 1 : 최근에 참조된 페이지를 의미한다.
  • modified bit == 1 : 최근에 변경된 페이지를 의미한다. (IO를 동반하는 페이지)
• reference bit을 1로 만드는 것은 HW가 진하고, 0으로 바꾸는 것은 OS가 진행한다.

Page Frame의 Allocation

지금까지의 페이지 교체 기법들은 프로세스와 연관이 없었다. 특정 조건에 맞춰 각 Process 마다 page frame을 할당해볼 수도 있지 않을까?

• Allocation problem : 각 process에 얼마만큼의 page frame을 할당할 것인가?

• Allocation 의 필요성

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

• Allocation Scheme

  • Equal allocation : 모든 프로세스에 똑같은 개수를 할당
  • Proportinal allocation : 프로세스 크기에 비례하여 할당
  • Priority allocation : 프로세스의 priority에 따라 다르게 할당

Global vs Local Replacement

• Global replacement
  • replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다.
  • process 별 할당량을 조절하는 또 다른 방법이다.
  • FIFO, LRU, LFU 등의 알고리즘을 glocal replcament로 사용 시에 해당
  • Working set, PFF 알고리즘 (아래에서 설명) 사용
• Local replacement
  • 자신에게 할당된 frame 내에서만 replacement
  • FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영

Thrashing

• x축은 프로세스 개수, Y축은 CPU 이용률을 나타냄

🙋🏻‍♀️ 프로세스가 1개 있으면 얘가 CPU를 모두 사용할 수 있으니까 CPU utilization이 높아야하는 것 아닌가요 ?
🙅‍♂️ CPU를 사용하다 IO를 하러가게 되면 CPU는 이용되지 않으므로 (프로세스가 1개 있는 경우에 CPU 이용률이) 높지 않습니다

• 프로세스의 원할한 수행에 필요한 최소한의 page frame 수를 할당 받지 못하는 경우 발생함
• 각각의 프로그램이 메모리를 너무 조금 갖고 있어 실행 조차 되지 않는 경우임. 예를 들어 특정 프로세스는 a,b,c 3개의 페이지를 갖고 있어야 비로소 실행 가능한데 그러지 못해서 page fault만 계속 처리하는 경우라고 볼 수 있음
• Page fault rate이 매우 높아짐
• CPU utilization이 낮아짐
• 그러나 OS는 이 상황에서 역으로 MPD(multiprogramming degree)를 높여야 한다고 판단
  • 💻(OS) : ' 아무도 CPU를 안쓰네? 그럼 프로세스를 더 데려와야겠다! '
  • 악순환의 반복
    • 또 다른 프로세스가 시스템에 추가됨 (high MPD)
    • 프로세스 당 할당된 frame의 수가 더욱 감소함 (-)
    • 프로세스는 page의 swap in / swap out 으로 매우 바쁨
    • 대부분의 시간에 CPU는 한가함
    • Low throughput

Working-Set Model

• Locality of refernece
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다
  • 집중적으로 참조되는 해당 page들의 집합을 locality set이라고 함
• Working-set Model
  • Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 page들의 집합을 Working Set이라고 정의함
  • Working Set 모델에서는 Process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend)
  • Thrashing을 방지할 수 있다 👍🏻
  • Multiprogramming degree를 결정한다

Working-Set Algorithm

• working set의 결정
  • working set window를 통해 알아냄
    
• process들의 working set size의 합이 page frame의 수보다 큰 경우
  • 일부 process를 swap out시켜 남은 process의 working set을 우선적으로 충족시켜준다 (MPD를 줄임)
• Working set을 다 할당하고도 page frame이 남는 경우
  • swap out 되었던 프로세스에게 working set을 할당 (MPD를 키움)
• window size
  • working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
    • 너무 작으면 locality set을 모두 수용하지 못할 우려가 생김
    • 너무 크면 여러 큐모의 locality set을 수용
    • 값이 무한대이면 전체 프로그램을 구성하는 page를 working set으로 간주

PFF(Page-Fault Frequency) Scheme

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

Page Size의 결정

• Page size를 감소시키면
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • Internal fragmentation 감소
  • Disk transfer의 효율성 감소
    • Seek/rotation vs transfer
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • Locality의 활용 측면에서는 좋지 않음
• Trend
  • Larger page size