"KOCW - 반효경 교수님의 운영체제" 를 듣고 정리한 내용입니다.
Virtual Memory
Demand Paging
- 페이지가 요청됐을 때 메모리에 올리는 것
- I/O 양의 감소
- 메모리 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
- Valid / Invalid bit 사용
- invalid
- 사용되지 않는 주소 영역인 경우
- 페이지가 메모리에 올라와있지 않고 backing store에 있는 경우
- 처음에는 모든 페이지 엔트리가 invalid로 초기화
- page fault
- 요청한 페이지가 메모리에 없는 경우 = 페이지 테이블에 invalid로 세팅되어 있는 경우
- CPU가 운영체제에게 넘어감 (일종의 SW interrupt)
Page Fault
- invalid page를 접근하면
MMU가 trap을 발생시킴 (page fault trap)
- 커널 모드로 들어가 page fault handler 실행
- sequence
- 해당 페이지에 대한 접근이 적합한지 체크
- get an empty page frame (빈 공간이 없다면 쫓아냄, replacement)
- 해당 페이지를 디스크에서 메모리로 읽어옴
- disk I/O가 끝나기까지 이 프로세스는 CPU를 선점당함 (
blocked)
- disk read가 끝나면 페이지 테이블 엔트리 기록 (valid-invalid bit = "valid")
- 프로세스를 ready queue에 배치
- 이 프로세스가 CPU를 잡고 다시 running
- 이전에 중단되었던 instruction 재개
Free frame이 없는 경우
- Page replacement
- 어떤 프레임을 빼앗아올지 결정해야 함
- 바로 사용되지 않을 페이지를 쫓아내는 것이 좋음
- Replacement Algorithm
- 목표 : page-fault rate 최소화
- 알고리즘 평가
- 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
Offline Optimal Algorithm
- MIN (OPT) : 가장 먼 미래에 참조되는 페이지를 교체
- 사실 미래에 어떤 페이지가 참조될 지 아는 것은 불가능하다. 실제 시스템에서 사용될 수는 없고, 단지 미래에 참조되는 페이지를 전부 알고 있다고 가정한다.
(사진 출처 - KOCW 운영체제 강의)
LRU 알고리즘은 연결리스트로 구현한다. 참조 시간 순서로 줄을 세워 아래로 갈수록 최근에 참조된 페이지라고 보면 된다. 새로운 페이지를 참조할 경우 맨 아래로 보내면 되고, 프레임이 꽉 차 페이지 하나를 빼야할 경우 맨 위 (가장 오래 전에 참조된) 페이지를 제거하면 된다. 따라서 시간복잡도는 O(1) 이다.
LFU 알고리즘도 연결리스트로 구현할 수 있다. 하지만 참조 횟수 순서로 줄을 세울 경우 새로운 페이지를 참조했을 때 맨 아래로 보내는 것이 아닌 다음 노드와의 횟수를 계속 비교해야 한다. 이와 같이 구현하면 O(n) 의 시간복잡도를 갖기 때문에 LFU 알고리즘은 힙으로 구현한다. 이로써 시간복잡도를 O(log n) 까지 줄일 수 있다.
다양한 캐싱 환경
- 캐싱 기법
cache (한정된 빠른 공간)에 데이터를 저장해 두었다가 나중에 같은 데이터에 대한 요청이 왔을 때 느린 저장 장치까지 가지 않고 캐시로부터 바로 서비스하는 방식- paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용
- 캐시 운영의 시간 제약
- 페이지 교체 알고리즘에서 삭제할 항목을 결정하는 일에 너무 많은 시간이 걸리면 실제 시스템에서 사용할 수 없음
- buffer caching / web caching
- paging system
운영체제는 page fault인 경우에만 관여한다. 즉, 페이지가 이미 메모리에 존재하는 경우 페이지 참조 시각이나 페이지 참조 횟수 등의 정보를 운영체제가 알 수 없다. 따라서 LRU나 LFU와 같은 알고리즘을 페이징 시스템에서 사용할 수 없다.
Clock Algorithm
결국 페이징 시스템에서는 LRU, LFU 알고리즘을 사용할 수 없고, LRU의 근사 알고리즘인 clock algorithm을 사용한다.
- 여러 명칭으로 불림
- Second chance algorithm
- NRU (Not Recently Used) 또는 NUR (Not Used Recently)
- reference bit을 사용해서 교체 대상 페이지 선정 (circular list)
- reference bit = 0 인 것을 찾을 때까지 포인터를 하나씩 이동
- 포인터 이동 중에 reference bit이 1인 값은 모두 0으로 바꿈
- reference bit이 0이라는 것은 페이지에 대한 참조가 없었다는 의미
- reference bit이 0인 페이지를 찾으면 해당 페이지를 교체
- 한 바퀴 되돌아와도 (= second chance) 0이면 replace
(사진 출처 - 티스토리)
LRU와 완전히 같지는 않지만 시계 방향으로 한 바퀴 도는 동안 참조되지 않는 페이지를 내쫓는 것이기 때문에 최근에 참조되지 않은 페이지를 교체한다고 볼 수 있다.
- Clock algorithm의 개선
- reference bit과 modified bit (dirty bit) 함께 사용
- reference bit = 1 : 최근에 참조된 페이지
- modified bit = 1 : 최근에 변경된 페이지
- 해당 페이지는 메모리에 올라온 이후 적어도 한 번은 CPU에 의해 write 가 발생한 것이므로 backing store에 수정된 내용을 반영해야 함
따라서 가능한 modified bit이 0인 값을 쫓아낸다.
Page Frame의 Allocation
- Allocation problem
- 각 프로세스에 얼마만큼의 페이지 프레임을 할당할 것인가 ?
- Allocation 필요성
- 메모리 참조 명령어 수행 시 intruction, data 등 여러 페이지 동시 참조
- 명령어 수행을 위해 최소한 할당되어야 하는 프레임 수가 있음
- loop 를 구성하는 페이지들은 한꺼번에 할당되는 것이 유리
- 최소한의 allocation이 없으면 매 반복마다 page fault
- Allocation Shceme
- Equal allocation
- Proportional allocation
- Priority allocation
Global Replacement vs Local Replacement
- Global Replacement
- replace 시 다른 프로세스에 할당된 프레임을 빼앗아 올 수 있음
- FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용하는 경우
- working set, PFF 알고리즘 사용
- Local Replacement
- 자신에게 할당된 프레임 내에서만 replacement
- FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영하는 경우
Thrashing
