가상메모리

Minseok-Choi·2022년 4월 5일

OS Study

목록 보기

10/12

운영체제 2017 반효경 교수님 강의 및 운영체제 공룡책을 참고하였습니다.

Demand Paging

실제로 필요할 때 page를 메모리에 올리는 것
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자(프로그램) 수용
Valid/ Invalid bit
- Invalid의 경우 사용되지 않는 주소영역인 경우와 페이지가 물리적 메모리에 없는 경우에 해당한다.
- 처음에는 모든 page entry가 invalid로 초기화 되어있다.
- 주소 변환 시에 invalid이면 page fault가 발생한다.

Page Fault

Invalid page(비트가 invalid 상태)에 주소 변환을 위해서 접근하게 되면 MMU가 trap을 발생시킨다.(page fault trap)
Kernel mode로 들어가서 page fault handler가 invoke된다.

Page fault 처리 순서

Invalid reference(잘못된 주소, protection violation(권한위반)) -> abort process
빈 page frame을 가져온다. 빈 프레임이 없다면 교체한다.
요청하는 페이지를 disk에서 memory로 읽어온다.
Disk I/O가 끝나기전까지 해당 프로세스는 block 상태가 된다.
Disk read가 끝나면 page tables entry에 기록하고, valid/invalid bit를 valid로 바꾼다.
ready queue에 process를 위치시킨다.

빈 frame이 없다면?

page replacement
- 어떤 frame을 빼앗아올지(교체시키질지) 결정해야한다.
- 곧바로 사용되지 않을 page를 교체시키는 것이 효율적이다.
- 동일한 페이지가 여러번 교체되는 상황이 생길 수 있다.
순서
1. Victim(교체될 페이지)를 swap out(교체시킨다.)
2. page table에 해당하는 page의 bit을 invalid로 바꾼다.
3. 원하는 page를 frame에 swap in(넣는다.)
4. page table에 해당하는 frame위치와 bit를 valid로 교체한다.

Replace Algorithm

Page-fault rate를 최소화하는 것이 목표다.
Page 참조 순서(Page reference string)에 대해서 page fault가 얼마나 발생하는지 조사하는 것으로 알고리즘을 평가한다.

Optimal Algorithm

MIN (OPT) : 가장 먼 미래에 참조되는 page를 replace
미래의 참조를 알고있다고 가정(실제로는 알 수 없음) = Offline algorithm
- 다른 알고리즘의 성능에 대한 upper bound를 제공한다.
- page fault가 가장 적게 일어난다.

FIFO Algorithm

먼저 들어온 것을 먼저 내쫓음
- more frames != less page faults
- 프레임이 증가한다해도 page fault가 줄어드는 것은 아니다.

LRU (Least Recently Used) Algorithm

LRU : 가장 오래 전에 참조된 것을 교체하는 알고리즘

LFU (Least Frequently Used) Algorithm

LFU : 참조 횟수가 가장 적은 페이지를 지움
- 최조 참조 횟수인 page가 여럿 있는 경우
- LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다.
- 성능 향상을 위해 가장 오래 전에 참조된 page를 교체할 수 있다.
장단점
- LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모로 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다.
- 참조 시점의 최근성을 반영하지 못한다.
- LRU보다 구현이 복잡하다.

LRU와 LFU 알고리즘의 구현

LRU의 경우 새로운 참조가 생겼을 때, O(1) complexity를 가진다.
- Linked LIst로 구현
LFU의 경우 새로운 참조가 생겼을 때, O(log n) complexity를 가진다.
- heap으로 구현

다양한 캐싱 환경

캐싱 기법
- 한정된 빠른 공간(=cache)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식
- page system외에도 cache memory, buffer caching, Web caching등 다양한 분야에서 사용한다.
케시 운영의 시간 제약
- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다.
- Buffer caching이나 web caching의 경우 O(1) ~ O(log n) 정도까지 허용한다.
Paging system
- page fault인 경우에만 OS가 관여함
  - page fault가 아닌 경우 주소 변환 과정에 전혀 관여하지않음 (참조 시간, 횟수를 기록, 관리할 수 없다.)
- 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없다.
- O(1)인 LRU의 list조작조차 불가능하다.

Clock Algorithm

LRU의 근사 알고리즘
Second chance algorithm
NUR(Not Used Recently) 또는 NRU(Not Recently Used)
Reference bit(access bit)을 사용해서 교체 대상 페이지를 선정한다. (circular list)
주소 변환 과정에서 참조된 페이지를 하드웨어가 reference bit를 1로 바꾼다. (하드웨어적 지원을 받는다)
page fault 발생시 OS가 Reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
포인터가 이동하는 중에는 page의 reference bit 1을 0으로 모두 바꾼다.
Reference bit이 0인 페이지를 만나면 그 페이지를 교체한다.
한 바퀴를 되돌아와서도 0이면 그때에는 replace 당한다.
자주 사용되는 페이지라면 second chance가 올 때 1이 된다.
개선
- reference bit과 modified bit (dirty bit)을 함께 사용한다.
- reference bit = 1 -> 최근에 참조된 페이지 (read와 write의 경우 모두)
- Modified bit = 1 -> 최근에 변경된 페이지 (I/O를 동반하는 페이지)
  - write, 즉 page에 수정이 발생되었을 때, page가 교체될때, 디스크에 수정을 기록해야하는 하는 것을 표시하는 bit

Page Frame의 Allocation

Allocation problem

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

Allocation의 필요성

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

Allocation Scheme

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

Global replacement

Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다.
- 특정 process가 메모리를 독식하는 경우가 발생할 수 있다.
process별 할당량을 조절하는 또 다른 방법이다.
FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당한다.
Working set, PFF 알고리즘 사용

Local replacement

자신에게 할당된 frame 내에서만 replacement
FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영

Thrashing Diagram

Degree of Multiprogramming이 높아지면, (메모리에 너무 많은 프로세스가 올라와 있다면) 어느 순간 CPU 사용률이 뚝 떨어진다

Thrashing

프로세스의 원활한 수행에 필요한 최소한의 page frame을 할당 받지 못한 경우에 발생한다.
page fault rate가 매우 높아진 상태
CPU 사용률이 낮아짐
1. OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단하게 됨
2. 또 다른 프로세스가 시스템에 추가됨
3. 프로세스 당 할당된 frame 수가 더 감소한다.
4. 프로세스는 page swap 횟수가 더 증가
5. 대부분의 시간에 CPU가 한가해짐
6. low throughput

Working set model

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

Working set Algorithm

Working set의 결정
- working set window를 통해 알아냄
- Window size가 delta인 경우
- delta만큼의 page들 중 서로 다른 페이지들의 집합을 working set으로 보고 frame을 할당함

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
- 큰 페이지 사이즈