Demand Paging
실제로 필요할 때 page를 메모리에 올리는 것
- I/O 양의 감소
- 빈번히 사용되는 코드는 제한적
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid / Invalid bit의 사용
- Invalid의 의미
- 사용되지 않는 주소 영역인 경우
- 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 page entry가 invalid로 초기화
- address translation 시에 invalid bit이 set되어 있으면 => "page fault"
- 6번 7번은 사용하지 않는 비트
- page fault가 나면 운영체제에 넘어간다. 소프트웨어 인터럽트 발생
Page Fault
- 페이지 폴트는 프로세스가 메모리에 없는 페이지를 접근하려고 할 때 발생.
- 예를 들어, 잘못된 메모리 주소(bad address)에 접근하거나 권한이 없는 메모리에 접근(protection violation)할 경우 발생.
- invalid page를 접근하면 MMU가 trap을 발생시킨다. (page fault trap)
- Kernel mode로 들어가서 page fault handler가 invoke 된다
- 운영 체제가 페이지 폴트 핸들러를 호출하여 그에 대한 처리를 시작한다.
- 다음과 같은 순서로 page fault를 처리
- Invalid reference? (eg. bad address, protection violation) => abort process(프로세스 종료)
- Get an empty page frame. (없으면 뺏어온다 : replace = 쫓아내고 디스크에서 가져옴)
- 해당 페이지를 disk에서 memory로 읽어온다.
- 디스크 I/O가 끝나기까지 이 프로세스는 CPU를 preempt(선점) 당함(block)
- 디스크 read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
- ready queue에 process를 insert -> dispatch later
- 이 프로세스가 CPU를 잡고 다시 running
- 아까 중단되었던 instruction 재개
1. 접근
2. invalid 확인 page fault trap 발생 = cpu가 운영체제에 넘어간다.
3,4. 운영체제는 backing store(디스크)에 있는 페이지를 물리적인 메모리로 올려 놓는다.
5. page table에 해당 내용을 넣고 valid로 변환
6. 명령어 재실행
- 대부분의 경우는 page fault가 발생하지 않는다. (p가 0.02 정도)
- 1-p : 페이지 폴트가 안나는 경우의 시간
- +p (.....) : 페이지 폴트가 났을 때, 오버헤드가 큰 것을 볼 수 있음
- 어떤 걸 쫓아낼지 결정
- 교체 대상이 되는 페이지를 `victim` 페이지라 칭한다.
Optimal Algorithm
- 미래에 어떤 페이지가 들어올지 알고 있을 때
- MIN (OPT) : 가장 먼 미래에 참조되는 page를 replace
- 하지만 우리는 미래를 모른다. 다른 알고리즘의 성능에 대한 upper bound를 제공하기 위해 사용
- 위에 그림의 예시에서는 page faults는 6번이 최소로 나올 수 있는 경우다.
FIFO(First in First Out) Algorithm
메모리 크기를 늘려주면 성능이 좋아져야하는데 FIFO는 성능이 더 나빠짐.
LRU(Least Recently Used)
가장 오래 전에 사용된 것을 쫓아내는 알고리즘
LFU(Least Frequently Used)
- 가장 덜 빈번하게 사용된 것을 쫓아낸다.
- 참조 횟수(reference count)가 가장 적은 페이지를 지운다.
- 최저 참조 횟수인 page가 여럿 있는 경우
- LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다.
- 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다.
- 장단점
- LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
- 참조 시점의 최근성을 반영하지 못함
- LRU보다 구현이 복잡
- 최저 참조 횟수인 page가 여럿 있는 경우
LRU, LFU 예제
LRU : 1번 PAGE 삭제
- Page를 실행순서를 최신화 했을 때 page1이 가장 오래전에 사용
- 단점 : 과거에 얼마나 많이 사용했나 참조하지 않음
LFU : 4번 PAGE 삭제
- Page를 빈도수로 최신화 했을 때 page4가 가장 적음
- 단점 : 이제 막 참조가 많이 시작될 애인데 삭제해버릴 수 있음 (뜨는 신인 삭제해버리기)
LRU는 linked list 형태로 꼬리 짜르기 하면 O(1)임, LFU는 사용횟수를 다 돌아봐야하기 때문에 최소힙을 사용 O(log n)
메모리가 꽉 찼을 때 쫓아내는(replace) 알고리즘들을 본 것이다.
FIFO, LRU, LFU
근데 LRU, LFU는 실제 페이징 시스템에서는 사용이 불가능하다..
캐시 기법
- 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
- paging system 외에도 cache memory, buffer caching, Web caching등 다양한 분야에서 사용
- 캐시 운영의 시간 제약
- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
- buffer caching(파일 시스템에서 사용)이나 web caching의 경우
- O(1)~O(log n) 정도까지 허용
- Paging system인 경우
- page fault인 경우에만 OS가 관여
- 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
- O(1)인 LRU의 list 조작조차 불가능
- 속도의 차이를 극복하기 위한 기법이다. (메모리는 빠르고 디스크는 느리다)
Clock Algorithm
LRU는 시간 복잡도와 하드웨어적인 제한 때문에 구현하기 어렵고 LFU는 공간 복잡도와 오래된 데이터가 과도하게 보호되는 문제로 인해 실용적이지 않다. 대신, 운영체제에서는 Clock 알고리즘과 같은 근사 LRU 방식을 사용한다.
Clock algorithm
- LRU의 근사(approximation) 알고리즘
- 여러 명칭으로 불림
- 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인 것을 찾으면 그 페이지를 교체
- 한 바퀴 되돌아와서도(=second chance) 0이면 그 때에는 replace 당한다.
- 자주 사용되는 페이지라면 second chance가 올 때 1
- Clock 알고리즘 개선
- reference bit(access bit)과 modified bit (dirty bit)을 함께 사용
- reference bit = 1: 최근에 참조된 페이지
- modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지)
- `읽기`가 발생 했을 때는 reference bit만 1로 바꿔주고, `쓰기`가 발생 했을 때는 reference bit, modified bit 둘 다 1로 올려준다.
- modified bit(dirty bit) 사용 이유!
- 쫓아낼 때 변경된 내용이 있다면 수정된 내용 디스크에 써주고 쫓아내야 한다.
- 쫓아낼 때 0이면 수정한게 없으니 그냥 쫓아내면 된다.
- 쫓아내다 = 메모리에서 걍 제거(dirty bit가 0일 때) or 메모리에서 디스크로 수정된 내용 swap out(dirty bit가 1일 때)
MMU는 페이지에 접근할 때마다 그 페이지의 reference bit를 1로 설정한다.
운영체제는 원형(링크드 리스트가 원형으로 구현)으로 돌면서 1인 비트를 0으로 바꿔주고 0인 비트는 replace를 해준다.
modified bit(dirty bit)는 수정된 내용이 있었는가 확인하고 없으면 제거하고, 있었으면 swap out 될 때 수정된 것을 디스크에 넣어줘야 한다.
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(CPU)에 따라 다르게 할당
- Global
- 프로세스 별로 자유롭게 많이 사용하는 것은 많이 차지하는 등 자유롭게 할당되는 장점이 있지만, 특정 프로세스가 독식할 수 있음
- 무한 경쟁
- Local
- 각 프로세스마다 동일하게 부여하고 그 안에서 경쟁
Thrashing 쓰레싱
- x축 : 메모리에 올라가 있는 프로그램 갯수
- y축 : cpu 이용률
- 일반적으로 메모리에 여러개의 프로그램을 올려놓으면 cpu가 놀지 않고 실행하고 있음
- 근데 갑자기 뚝떨어지는 이유?
- 쓰레싱이 일어났다!!
- 메모리에 너무많은 프로그램을 올려놔서 프로그램들이 각각 너무 작은 메모리양을 할당 받아서 페이지 폴트가 계속 나는 현상. 페이지 폴트 처리하느라 정신없는 상태
쓰레싱을 막기 위한 방법
최소한의 메모리는 할당해주자!!
working set을 보장해주자 !!!
Working-set model은 프로세스가 일정 시간 동안 실제로 사용하는 페이지(working set)를 추적하여, 메모리에 불필요한 페이지들을 제거하고 필요한 페이지만 유지함으로써 메모리 관리 효율을 높인다. 이 방식은 주기적으로 사용하지 않는 페이지를 스왑아웃하여, 메모리 공간을 확보 및 절약하고 다른 프로세스들이 필요한 페이지를 더 쉽게 확보할 수 있도록 한다. 또한, 페이지 교체 시 자주 사용되는 페이지를 우선적으로 남겨두어 페이지 폴트를 줄여 시스템 성능을 향상시킨다.
예를 들어 window size = 10 (과거 10개를 본다) 일 때
처음에 WS(t1) 은 5개가 실행되었다. , 이후 WS(t2) 는 2개만 실행되었다. => 속하지 않은 것은 버리면서 working set을 보장하는 것
그 때 그 때마다 필요한만큼
- 각 프로세스의 Page-Fault 비율을 그 때 그 때 봐가면서 페이지를 더줄지 말지 결정
- 위에 그래프는 메모리를 얼마나 할당느냐에 따라 페이지 폴트가 얼마나 날지의 비율을 나타낸다.
- PFF는 lower bound와 upper bound 사이로 조절
최소한의 메모리를 할당 받기 위해서 사용하는 알고리즘에서는 대부분 내가 page fault 날 바에 swap out을 해서 메모리를 반환한다.
- page size가 감소하면 페이지 수가 증가하기 때문에 페이지 테이블의 크기가 증가한다.
- 페이지를 작게 쓰기 때문에 내부단편화가 줄어들어 메모리를 효율적으로 사용할 수 있다.
- 페이지가 작으면 Disk transfer 효율이 감소 : 디스크를 자주 읽는다 = page fault가 자주 일어난다.