Virtual Memory

이연중·2022년 2월 22일

OS

목록 보기

9/9

물리적인 메모리의 주소변환은 운영체제가 관여하지 않지만,
virtual memory 기법은 운영체제가 전적으로 관여함

Demand Paging(paging 기법을 사용하는 것으로 가정)

실제로 필요할 때 page를 메모리에 올림(요청이 있으면 페이지를 메모리에 올림. 모든 페이지를 메모리에 올리는 것이 아닌)
- I/O 양 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid/Invalid 비트 사용
- Invalid의 의미: 사용되지 않는 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 page entry가 invalid로 초기화(demand paging 기법이기에 처음에는 모든 페이지가 물리적 메모리에 로드되어 있지 않음)
- 주소 변환을 하려는 페이지가 page table에서 i로 되어있다면 물리적 메모리에 로드되어있지 않다는 뜻(MMU가 trap 발생시킴)
  - page fault(요청한 페이지가 메모리에 없음)
  - 해당 페이지를 디스크에서 메모리로 올려야 함(I/O 작업. CPU 제어권이 OS로 넘어감)
    - OS에서 잘못된 요청이 아닌지 확인(페이지 번호가 유효하지 않거나 접근 권한 문제)
    - 메모리내에서 빈 페이지 불러옴(없으면 하나 쫓아냄)
    - 해당 페이지를 디스크에서 메모리로 읽어옴
      - 페이지 주소 변환을 요청한 프로세스를 block시키고, 다른 프로세스에 CPU 제어권 넘김
      - 디스크 I/O가 끝나면, OS가 page table entry에 해당 페이지에 대한 처리 결과 기록(i -> v)
      - 해당 프로세스를 ready queue로 옮김
    - CPU 제어권을 얻으면 작업 재개
Performance of Demand Paging
page fault rate(0<=p<=1.0)
- if 0 = no page fault
- if 1 = every reference is a fault
메모리 접근 시간
- (1-p) * memory access (no page fault)
- p(OS로 CPU가 넘어가고 HW적으로 page fault 처리 + 메모리에서 page 쫓아냄 + 메모리에 page 로드 + OS 읽어온 page entry 작성, restart) (page fault occur)

빈 페이지가 없는 경우(메모리에 로드 된 페이지 중 하나 쫓아냄)

OS가 하는 일

Page Replacement
- 어떤 frame을 내릴지 결정
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 돌아올 수 있음
Replacement Algorithm
- page-fault rate를 최소화하는 것이 목표
- 알고리즘 평가
  - 주어진 page references string에 대해 page fault를 얼마나 내는지 조사
    - references string? 1,2,3,4,1,2,5,1,2,3,4,5
- 가장 좋은 알고리즘
  - 가장 먼 미래에 참조되는 page를 replace
  - Optimal Algorithm(page fault를 가장 적게하는 alg)
  - 실제 시스템은 미래에 대한 참조를 하기가 어려움
  - 이 알고리즘은 미래에 대한 참조를 할 수 있다 가정
  - 실제 시스템에서 구현하기 어려움(offline optimal algorithm)
  - 다른 알고리즘의 성능에 대한 upper bound 제공(이 alg보다 더 좋을 수는 없음. 다른 alg의 성능을 평가하는 기준이 됨)

Page Replacement Algorithm

미래에 대한 참조를 할 수 없으니 과거 이력을 이용하자!

FIFO: 먼저 들어온 것을 먼저 내쫓음
- 메모리 크기를 늘리면 보통 성능이 좋아져야 하는데, 이 알고리즘의 경우에는 성능이 더 안좋아지는 상황(Belady's Anomaly)
LRU(Least Recently Used): 가장 오래 전에 참조된 것을 내쫓음
- 참조 횟수에 대한 고려를 하지 않는 문제
- 구현
  
  가장 최근에 참조된 페이지가 맨 밑(linked list로 구현)
  최근에 참조가 되면 맨 밑으로 내림
  맨 위에 페이지를 쫓아냄
  시간 복잡도 : O(1) 쫓아내기 위한 비교가 필요 없음
LFU(Least Frequently Used): 참조 횟수가 가장 적은 페이지를 지움
- 최저 참조 횟수가 여럿 있는 경우
  - 알고리즘 자체적으로 규정하고 있는 것은 없지만, 성능 향상을 위해 마지막 참조 시점이 더 오래된 page를 내쫓는게 좋다
- 가장 최근에 참조된 page를 내쫓는 문제
- 구현
  
  참조 횟수가 가장 적은 페이지는 맨 위
  참조 횟수가 가장 많은 페이지는 맨 밑
  페이지끼리 참조횟수를 비교해야 함
  시간 복잡도 : O(n)
  -> Heap 자료구조 이용
  
  맨 위에는 참조횟수가 가장 적은 페이지
  맨 위에 있는 페이지 쫓아내고 트리 재구성
  참조횟수가 늘어나면 자리바꿈(트리의 크기만큼 비교)
  시간 복잡도 : O(logn)

다양한 캐싱 환경

캐싱: 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식(느린 저장 장치까지 가지 않음)
- paging 시스템 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용
캐시 운영의 시간 제약
- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
- Buffer caching이나 Web Caching의 경우 O(1)에서 O(logn) 정도까지만 허용
- Paging system인 경우
  - page fault인 경우에만 OS가 관여
    - 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음(참조된지 오래되었거나 참조횟수가 얼마나 되는지에 대해 OS는 모름)
    - LRU나 LFU 알고리즘을 Paging 기법에 적용못함(Buffer Caching이나 Web Caching에는 적용가능)
    - O(1)인 LRU의 list 조작도 불가능

Clock Algorithm

LRU나 LFU는 Paging System에 적용할 수 없는 알고리즘이다.
그렇다면 Paging System을 위한 알고리즘은 무엇이 있을까? 바로 Clock Algorithm이다.

LRU의 근사 알고리즘
여러 명칭으로 불림(Second chance algorithm, Not Used Recently, Not Recently Used)
Reference bit(메모리에 로드된 페이지가 참조되면 하드웨어가 reference bit을 1로 세팅해줌)를 사용해 교체 대상 페이지 선정(circular list)
Reference bit가 0인 것을 찾을 때가지 포인터를 하나씩 앞으로 이동
포인터 이동중에 Reference bit 1은 모두 0으로 교체
Reference bit가 0인 것을 찾으면 해당 페이지 교체
한 바퀴 돌아와도(=second chance) 0이면 그때는 replace 당함(한 바퀴 돌아도 0이라는 소리는 한 바퀴 돌때 동안 해당 페이지가 참조가 안됐다는 것을 의미)
자주 사용되는 페이지라면 second chance가 올 때 1
Clock Algorithm의 개선
- 만약 변경 사항이 있는 페이지를 쫓을 경우 변경 사항이 반영 안된채로 지워버림(Backing Store에는 변경 전에 내용이 저장되어 있음)
- reference bit과 modified bit(dirty bit)을 함께 사용
- reference bit = 1 : 최근에 참조된 페이지
- modified bit = 1 : 최근에 변경된 페이지(I/O를 동반하는 페이지)
- modified bit을 이용해 1이 세팅되어 있다면, 변경 사항을 Swap Area(Backing Stage)에 반영하고 해당 페이지를 메모리에서 지움
- 변경 사항을 반영하는 작업을 I/O 작업이기때문에 시간이 걸림
- 그렇기 때문에 modified bit이 1인 페이지는 놔두고, 0인 페이지를 우선적으로 지워줌

Page Frame의 Allocation

여태까지 물리적 메모리에 로드된 페이지들을 내쫓고 로드하는 작업이(알고리즘을 통한) 특정 프로세스에 국한된 것이 아닌, 아무 페이지에 대해서 이루어졌다.
그러나 프로그램이 원활하게 수행되기 위해서는 일련의 페이지들이 메모리에 같이 로드되어 있어야 한다.
즉, 프로세스별로 page를 적절하게 allocation 해주어야 한다.

Allocation Problem: 각 프로세스에 얼만큼의 page frame을 할당할 것인가
Allocation의 필요성
- 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조
  - 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
- Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함
  - 최소한의 allocation이 없으면 매 loop마다 page fault 발생
Allocation Scheme(할당 방법)
- Equal allocation: 모든 프로세스에 똑같은 갯수 할당
- Proportional allocation: 프로세스 크기에 비례해 할당
- Priority allocation: 프로세스의 priority에 따라 다르게 할당
Global Replacement
- 미리 할당을 하지 않고 replacement algorithm을 사용하면 알아서 프로세스별로 메모리 할당량이 조절됨
- LRU, LFU같은 알고리즘은 프로그램에 페이지를 할당하는 효과는 없음, Working set, PFF 알고리즘은 이러한 효과가 있음
Local Replacement
- 프로그램들에게 frame 할당
- 자신에게 할당된 frame내에서만 replacement
- FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시

Thrashing

프로세스가 적당한 frame을 할당받지 못해 page fault가 자주 발생하는 현상

프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
page fault rate이 매우 높아짐
CPU 이용률이 낮아짐
OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
또 다른 프로세스가 시스템에 추가됨(higher MPD)
프로세스 당 할당된 frame의 수가 더욱 감소
프로세스는 page의 swap in/ swap out으로 매우 바쁨
대부분의 시간에 CPU는 한가함
low throughput
이를 방지하기 위해서는 Multiprogramming Degree를 조절해줘야 함(이를 해주는 알고리즘이 Worgin set, PFF)

Working-Set

Locality of reference
- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조
- 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함
Working-set Model
- Locality에 기반해 프로세스가 일정 시간 동안 월활하게 수행되기 위해 한꺼번에 메모리에 로드되어야 있어야 하는 page들의 집합을 Working Set이라 정의
- Working set 모델에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out
- Thrashing 방지
- Multiprogramming degree 결정
Working-Set Algorithm
- Working set의 결정
  - Working set window를 알아냄
  - window size(현재 시점에서 window size 시간 전까지 참조한 페이지들)
- Working set page들은 메모리에 로드
- 프로세스들의 working set size의 합이 page frame의 수보다 큰 경우, 일부 프로세스를 swap out 시켜 남은 프로세스의 working set을 우선적으로 충족시켜 줌
- working set을 다 할당하고도 page frame이 남는 경우, swap out 되었던 프로세스에 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를 감소시키면
- 페이지 수 증가
- 페이지 테이블 크기 증가
- 내부 단편화 감소
- disk transfer의 효율성 감소(페이지 크기가 작으면, 찾아야 하는 데이터 수는 늘어나고, 디스크에서 탐색하는데 시간이 오래걸림)
  - seek/rotation VS transfer
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
  - Locality의 활용 측면에서는 좋지 않음
Trend
- 큰 사이즈의 페이지