[운영체제] 9. 가상 메모리

9. 가상 메모리

Demand Paging

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

Valid / Invalid bit 사용
Invalid - 사용되지 않는 주소 영역 or 페이지가 물리적 메모리에 없는 경우
처음에는 모드 invalid로 초기화
page fault - 주소 변환 시 invalid bit이 set 되어 있음

Page Fault

invalid page에 접근하면 MMU가 trap 발생시킴

1. Invalid reference? → abort process
2. Get an empty page frame (없으면 뺏어옴)
3. page를 disk에서 memory로 이동
   1. disk I/O 끝날때까지 프로세스는 CPU 뺏김 (block)
   2. Disk read 끝나면 page tables entry 기록, valid
   3. ready queue에 프로세스 insert

Performance of Demand Paging

Page Fault Rate 0 ≤ p ≤ 1.0
page fault 없으면 메모리 접근 시간만 소요
page fault가 일어나면 disk에 접근해야 하기 때문에 시간이 오래 걸림

Free frame이 없는 경우

Page replacement
어떤 frame을 뺏어올지 결정
곧바로 사용되지 않을 page를 쫓아내는 것이 좋음

Page replacement Algorithm
page-fault rate를 최소화
주어진 page reference string에 대해 page fault를 얼마나 내는지 조사

Page replacement Algorithm

• Optimal Algorithm
  page reference string을 미리 알고 있다고 가정 - offline algorithm (실제 사용 불가)
  MIN (OPT): 가장 먼 미래에 참조되는 page를 replace
  다른 알고리즘의 성능에 대한 upper bound 제공
• FIFO (First In First Out) Algorithm
  FIFO - 먼저 들어온 것을 먼저 지움
  FIFO Anomaly - frame 수가 늘어나면 더 많은 page fault 발생
• LRU (Least Recently Used) Algorithm
  LRU - 가장 오래 전에 참조된 것을 지움
• LFU (Least Frequently Used) Algorithm
  LFU - 참조 횟수(referenced count)가 가장 적은 페이지를 지움
  최저 참조 횟수인 page 여럿 있는 경우 - 임의로 지움 / 오래 전에 참조된 page 지움

LRU와 LFU 알고리즘의 구현

• LRU
  linked list로 구현 - 가장 최근에 참조된 것을 list 마지막에 추가 → O(1)
• LFU
  linked list로 구현 - 하나하나 비교해서 자리를 찾은 후 추가 → O(n)
  heap으로 구현 - 자식 노드 2개와 비교 → O(log n)

다양한 캐슁 방법

캐슁 기법
한정된 빠른 공간(=캐쉬)에 요청된 데이터 저장 → 나중에 요청시 캐쉬로부터 직접 서비스
cache memory, buffer caching, web caching 등

캐쉬 운영의 시간 제약
지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 X

• Buffer caching, Web caching
  O(1)에서 O(log n) 정도까지 허용
• Paging system
  LRU, LFU 사용 불가능

Clock Algorithm

Second chance algorithm
NUR / NRU (Not Recently Used)

Reference bit
최근에 사용된 페이지 = 1, 최근에 사용되지 않은 페이지 = 0
0인 것을 찾을 때까지 포인터 이동 - 1 → 0으로 교체

Clock Algorithm의 개선
→ Reference bit과 modified bit을 함께 사용

Page Frame Allocation

한 loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함

• Equal allocation: 모든 프로세스에 같은 개수
• Proportional allocation: 프로세스 크기에 비례
• Priority allocation: 프로세스의 priority에 따라

Global vs Local Replacement

• Global replacement
  다른 process에 할당된 frame 빼앗을 수 있음
• Local replacement
  자신에게 할당된 frame 내에서만 replacement, process 별로 운영

Thrashing

메모리에 너무 많은 프로그램을 동시에 올려 놓아서 계속 page fault가 일어나는 상황
CPU utilization 낮아짐 → 또 다른 프로세스 추가됨 → low throughput

Working-Set Model

Locality set - 집중적으로 참조되는 page들의 집합

Working set - 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합

Working-Set Algorithm
특정 window size 안에 있는 page들을 working set으로 간주
working set에 속하지 않은 page 버림

working set이 보장되는 프로세스만 메모리에 올림

PFF (Page-Fault Frequency) Scheme

page-fault의 상한값과 하한값 지정

• Page fault rate 상한값 넘으면 frame 더 할당
• Page fault rate 하한값 이하이면 할당 frame 수 줄임

빈 frame이 없으면 일부 프로세스 swap out

Page Size 결정

Page size 감소

• 페이지 수 증가, 페이지 테이블 크기 증가
• Internal fragmentation 감소
• Disk transfer 효율성 감소

Larger page size 사용하는 추세