물리적 메모리의 주소변환은 운영체제가 관여하지 않지만,
Virtual Memory 기법은 전적으로 운영체제가 관여한다.
Demand Paging
실제로 필요할 때 page를 메모리에 올리는 것
예를 들면, 방어적인 코드는 일반적인 상황에서 요청이 이루어지지 않아 메모리에 미리 올라가 있을 필요가 없다. 예외 상황이 발생했을 때, 즉 예외 상황이 발생하여 방어적인 코드가 필요할 때 메모리를 차지하면 된다.
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid / Invalid bit의 사용
- Invalid의 의미
- 사용되지 않은 주소 영역인 경우
- 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 page entry가 invalid로 초기화
- address translation 시에 invalid bit이 set되어 있으면 => "page fault"
Page Fault
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로 읽어온다.
1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)
2. Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
3. ready queue에 process를 insert -> dispatch later
- 이 프로세스가 CPU를 잡고 다시 running
- 아까 중단되었던 instruction을 재개
Page fault를 처리하는 과정
- virtual memory reference에서 주소 변한을 하기 위해 page table을 봄.
- page table에 invalid로 되어있는 것 확인 후, trap이 걸려서 CPU가 운영체제에 넘어간다.
- 운영체제는 backing store에 있는 페이지를 물리적인 메모리로 올려놓는다. (free frame이 없다면 쫓아내고 무언가를 올려놓는다. => reaplce)
- 올려놓는 작업이 끝나면 해당하는 프레임 번호를 entry에 적어놓는다.
- invalid를 valid로 바꾼다.
- CPU를 얻어 주소 변환을 다시 하게 된다.
Free Frame이 없는 경우
Page replacement
- 어떤 frame을 빼앗아올지 결정해야 함
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
Replacement Algorithm
page-fault rate을 최소화하는 것이 목표- 알고리즘 평가
- 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사 - reference string의 예
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. (page)
- victim이 선정되면, physical memory에서 삭제한다. victim page에 wirte가 일어났을 경우에는 backing store에 저장을 해야한다.
- change to invalid
- 새로운 page를 올려놓는다.
- frame번호를 entry에 적어둔 뒤, valid로 변경해준다.
가장 많이 사용되는 알고리즘
LRU Algorithm
LFU Algorithm
LFU: 참조횟수(refernece count)가 가장 적은 페이지를 지움
- 최저 참조 횟수인 page가 여럿 있는 경우
- LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다.
- 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다.
장점:
- LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다.
단점:
- 참조 시점의 최근성을 반영하지 못한다.
- LRU보다 구현이 복잡하다.
LRU와 LFU 알고리즘 예제
LRU 알고리즘은 가장 나중에 참조되었던 것을 기준으로 하기 때문에, 얼마나 많이 참조되었는지를 고려하지 않는다. 반면에LFU 알고리즘은 참조 횟수를 기준으로 하기 때문에 이제 막 참조가 시작될 수 있는 상황에서도 가장 적게 참조된 page를 삭제한다.
LRU와 LFU 알고리즘 구현
LRU 알고리즘
- memory 안에 있는 page들은 참조 시간 순서에 따라 한 줄로 줄을 세운다. 위에 있을 수록 가장 참조가 오래된 page, 아래에 있을 수록 가장 최근에 참조된 page로 구분된다.
- 링크드 리스트 형태로 운영체제가 참조 시간 순서를 관리한다.
어떤 page가 메모리에 들어오거나, 메모리 안에서 다시 참조가 된다면 그 page는 참조 시간이 가장 최근이다. 그렇기 때문에 시간 복잡도는 O(1)
LFU 알고리즘
- LRU처럼 한 줄로 비교를 할 수 없기 때문에 heap을 이용해서 이진트리 형태로 구현을 해서 자식들과의 비교만으로 참조 횟수를 비교하여 해당하는 경로로만 내려간다. O(log n)으로 구현이 가능하다.
paging system에서 실제로 LRU, LFU와 같은 알고리즘을 사용할 수 없다.
실제로 paging system은 clock algorithm을 사용하고 있다.
bit가 1이라는 것은 최근에 사용된 페이지라는 뜻, 0은 최근에 사용이 되지 않은 페이지라는 뜻.
즉, 0으로 되어있는 페이지는 교체 대상이 된다. (replacement)
Clock Algorithm
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 change가 올 때 1
Clock algorithm의 개선
- reference bit(access bit)과 modified bit(dirty bit)을 함께 사용
- reference bit = 1: 최근에 참조된 페이지
- modified bit = 1: 최근에 변경된 페이지 (I/O를 동반하는 페이지)
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 vs. Local Replacement
Global replacement
- Replace시 다른 process에 할당된 frame을 빼앗아 올 수 있다.
- Process별 할당량을 조절하는 또 다른 방법임
FIFO,LRU,LFU등의 알고리즘을global replacement로 사용시에 해당- Working set, PFF 알고리즘 사용
Local replacement
- 자신에게 할당된 frame 내에서만 replacement
FIFO,LRU,LFU등의 알고리즘을 process 별로 운영시
Thrashing
메모리의 수에 따른 CPU 이용률
CPU 이용이 떨어지는 순간을 thrashing이라고 한다.
각각의 프로그램이 메모리를 너무 적게 가지고 있기 때문에, CPU를 주더라도 page fault가 일어난다.
- 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
Page fault rate이 매우 높아짐CPU utilization이 낮아짐- OS는
MPD (Multiprogramming degree)를 높여야 한다고 판단 - 또 다른 프로세스가 시스템에 추가됨 (
higher MPD) - 프로세스당 할당된
frame의 수가 더욱 감소 - 프로세스는 page의
swap in/swap out으로 매우 바쁨 - 대부분의 시간에 CPU는 한가함
low throughput
Working-Set Model
Locality of reference
- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
- 집중적으로 참조되는 해당 page들의 집합을
locality set이라 한다.
Working-Set Model
- Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을
Working Set이라 정의한다. - Working Set모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후
swap out(suspend) - Thrashing을 방지함
- Multiprogramming degree를 결정함
