[운영체제] Virtual Memory (1)

• 가상 메모리는 공간 사용의 효율성을 높이기 위해 등장

Background

• 이론적으로는 모든 프로세스의 주소 공간이 메모리에 올라와있어야 하지만(폰 노이만 머신의 기본 원칙), 실질적으로는 그럴 필요가 없음
• 현재 접근하는 부분만 메모리에 있으면 프로그램 실행에는 문제 없음
• 실제로 CPU가 접근하는 부분만 메모리에 올려 보자 -> 메모리 절약, 동시에 실행되는 프로세스의 개수 증가(프로세스의 일부만 메모리에 올라오니까)
• 그러면 원칙이 깨져버림 -> 원칙은 지키자
• CPU한테는 프로세스의 주소 공간이 전부 올라 와있다고 사기 치고, 혹시나 안 올라와있는 부분에 CPU가 접근하면 OS가 재빨리 올려줘(페이지 교체)
• logical memory와 physical memory의 완벽한 분리

Virtual Memory

• physical memory보다 커도 동작 가능
  • logical이 동적 할당 등으로 엄청나게 커져도 virtual memory 사용하면 현재 사용되는 페이지만 physical로 올라가면 되니까
  • virtual memory 없으면 logical 메모리가 모두 physical에 올라가야 되고, 못 올라가면 못 쓰게 됨
• Demand Paging
  • CPU가 페이지에 접근할 때 메모리로 페이지를 올리겠다
  • 접근하는 놈만 I/O가 발생해서 메모리로 올라가기 때문에 I/O의 총량 감소
  • 프로세스 시작 시점 빨라짐; faster response
  • CPU가 접근했을 때 페이지가 메모리에 올라와있는지 확인하기 위해 bit를 하나 설정
    • valid/invalid
    • 올라와있으면 valid, 아니면 invalid
    • 합법적인 접근인지 판단 여부로도 사용
  • Lazy swapper: suspend된 프로세스가 하드 디스크로 밀려 내려갔을 때 suspend 해제되면 원래는 프로세스의 주소 공간 전체가 메모리로 올라와야 하는데, 이제는 지금 당장 접근되는 부분만 올리면 됨
• Valid-Invalid Bit
  • illegal: 메모리에 올라와있지만 잘못된 경우 
    • logical 주소가 프로세스의 사이즈보다 크면 완전히 잘못된 거
      • 프로세스는 10개의 페이지인데 11번 페이지로 접근하면 잘못된 주소 체계
    • 얘는 주소를 완전 잘못 접근해서 그렇게 중요하지 않음
  • not-in-memory: 메모리에 올라와있지 않는 경우
  • obsolete: 메모리에 올라와있고, 합법적인 주소체계지만 메모리에 올라와있는 페이지가 누군가에 의해 업데이트된 경우
  • not-in-memory, obsolete의 경우 메모리에 다시 올려줘야 함
  • 페이지 테이블에서 invalid로 표시돼있어서 처리해주는 놈 page fault handler
• Page Fault
  • invalid page 가 있으면 page fault trap 발생 -> trap handler(==page fault handler) 호출
  • illegal refenrence인지, 잘못된 주소 접근 확인 -> abort process
  • not in memory -> 다시 올려야지
  • 비어있는 page frame 찾기(올려야되니까) -> 없으면 기존의 것 쫓아내고 replace (페이지 교체 알고리즘도 중요)
  • 하드 디스크로부터 해당 페이지 메모리로 올림
    • 디스크 I/O 끝날 때까지 프로세스를 wait 상태로 보냄
    • I/O 끝나면 page table entries 업데이트 (frame 번호(실제로는 frame 시작 주소), valid bit 설정)
    • 프로세스 Ready queue로 집어넣음
  • instruction 재시작

• Page fault 구현의 어려움
  • 최악의 경우: 두번째 페이지에서 page fault 나면 명령어 수행 도중에 중단됨 -> 프로세스 재시작시 명령어 재수행됨
    • 완전히 수행 전으로 되돌려서 다시 시작해야 됨

• Demand Paging 성능
  • Page Fault Rate(발생률) 0 <= p <= 1
  • Effective Access Time(EAT) 평균 접근 시간

                 -> swap 하는 애들 I/O overhead가 엄청 큼

• Locality of reference
  • 초반 명령어에 쓰이는 페이지는 프로세스 시작 시 미리 가져온다든가 하는 건 그렇게 큰 성능 향상을 보이지 않음
  • Locality 보존 중요; 인기 있는 데이터, instruction 이 있는 페이지가 올라오면 교체되지 않아야 함
  • 프로그램이 가지는 locality를 지원해주는 페이지 교체 알고리즘이 중요함

Page Replacement

• free frame이 없으면 victim page(쫓아낼 놈, 희생자) 선정하는 게 페이지 교체 알고리즘의 핵심
• 프로그램의 locality를 최대한 보전하는 방식으로 이뤄져야 함, 즉 사용되지 않는 페이지를 쫓아내는 게 중요
• 페이지가 메모리에 올라온 뒤 수정되었으면(dirty) swap out으로 디스크에 써주고, 수정되지 않았으면(clean) 그냥 덮어씀
• page-fault rate를 최소화시키는 것이 목표

> 페이지 교체 과정

1. 디스크에서 불러올 페이지 찾기
2. 비어있는 프레임(free frame) 찾기
   • 없으면 victim frame 찾아서 쫓아내기
3. dirty면 디스크에 써주고, 새로운 페이지 메모리에 탑재
4. 프로세스 재시작

 Page Replacement Algorithms

• reference string(메모리 참조 순서)을 정해두고 page fault 일어나는 횟수 시뮬레이션해봐서 성능 평가
• 상식적으로 공간이 늘어나면 page fault 횟수가 줄어든다고 가정

First-In-First-Out(FIFO) Algorithm

-> frame 수가 늘어났는데로 fault가 증가하는 현상이 생겨버림

-> victim으로 선정된 페이지가 그 다음에 바로 접근이 되면 가차없이 fault 가 발생해 버림

 

Optimal Algorithm

-> 곧 다시 접근될 페이지는 victim으로 선정하지 말아보자

-> 미래를 알아야되는데? 모르니까 못 만들지만 가장 이상적인 최적의 알고리즘임

 

Least Recently Used (LRU) Algorithm

-> 미래를 알진 못하지만 과거의 정보로 예측해보자

• 최근에 사용되지 않은 놈을 victim으로 선정하자

• 구현하려면 언제 접근되었는지에 대한 timestamp가 다 있어야 함
• page table이라는 자료구조에 column을 추가해서 timestamp 남겨줌 -> space overhead
• page fault 가 일어나면 min 값을 찾는 O(N) 알고리즘을 돌려야 함 -> time overhead overhead 장난 아님
• LRU를 정확하게 그대로 구현하긴 어려우니까 근사하게 만들자

LRU Implementation Algorithms

 

1. Counter Implementation
   • timestamp를 찍는 건 timer라는 디바이스한테 요청해서 시간을 받아와서 timestamp에 넣는 과정 -> I/O니까 overhead 큼
   • 굳이 정확한 시간은 필요없지 않냐 -> logical clock을 쓰자
   • CPU counter: CPU가 메모리에 접근할 때마다 1씩 증가하는 변수
   • counter 값을 timestamp에 적으면 상대적인 순서 파악 가능
2. Stack Implementation
   • 각 페이지를 double linked list로 묶기
   • linked list의 제일 위쪽에 최근에 접근한 페이지가 올라감 -> 스택처럼 보임
   • 접근한지 제일 오래된 놈은 밑바닥에 있는 것 -> O(1)으로 victim 선정 가능
   • 자료 구조를 유지하기 위한 overhead가 큼

 

=> 온갖 생각을 다 해봤지만 overhead를 줄이려면 LRU의 성능을 약간 희생할 수 밖에 없겠구나

 

LRU Approximation Algorithms

1. Reference bit

• 메모리에 처음 올라오면 0
• 페이지가 다시 한 번 참조되면 1로 바꿔
• reference bit 주기적으로 0으로 reset
• reference bit이 여전히 0인 놈은 reset 이후에 접근이 안 됐다는 거니까 victim으로 선정
• (-) 0인 놈들 중에서 누가 최근에 접근됐는지를 모르니까 성능이 그렇게 좋지 않음

2. Additional-Reference-Bits Algorithm

• reference bit의 history를 나타내기 위한 추가적인 8 bits 사용
• 주기적으로 0으로 리셋되면서 additional bits에 과거를 남겨놓음
• Ex> 00000000 - 한번도 참조되지 않은 것/10101010 - 매 2번의 주기마다 접근된 것
• (-) 성능은 좋아지지만 추가적인 공간 사용하게 됨
• (-) 최솟값을 찾는 알고리즘이 돌아갈 수밖에 없음 -> overhead

3. Second chance(clock) algorithm

• reference bit 하나 사용
• 모든 페이지를 circular queue로 관리
• 다음 번에 victim으로 선정되는 놈은 이거야 하는 pointer
• pointer가 가리키는 페이지의 reference bit이 0이면 그대로 victim
• pointer가 가리키는 페이지의 reference bit이 1이면 그 페이지 bit 0으로 만들고 pointer 전진
  • reference bit이 0인 놈을 만날 때까지 pointer 전진
• pointer가 한 바퀴 돌아와서 0이면 한 바퀴 돌 동안 참조가 안 됐다는 거니까 victim 되는 거임
• pointer가 이동하는 순서가 있으니까 접근 순서 파악 가능

4. Counting Algorithms

• 접근 시점도 중요하지만 접근 빈도도 중요하지 않냐
• 접근 횟수 counter로 저장
• LFU(Least Frequently Used) Algorithm; 접근 수가 제일 적은 놈을 버리자
  • 사용은 잘 안됨 <- 접근 시점이 중요하다는 다년간의 경험이 있기에
• MFU(Most Frequently Used) Algorithm; 접근 수가 제일 많은 놈을 버리자
  • 갓 올라온 놈은 앞으로 사용이 많이 되지 않겠냐
  • 이미 많이 쓰인 놈은 앞으로 덜 쓰이지 않겠냐

 

=> 대부분의 애플리케이션에서는, 범용 OS에서는 LRU가 좋다

 

한양대학교 강수용 교수님 운영체제 강의 내용 정리