퇴근 후 운영체제 시리즈 - 가상 메모리
운영체제 스터디 기록
해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다
- 가상 메모리는 전적으로 OS가 관여한다!
- Demand Paging
- Page Fault
- 다양한 caching 기법
- 왜 LRU / LFU를 실제로 사용할 수 없는가?
- Clock Algorithm(LRU 근사 알고리즘)
- Page Frame의 Allocation
- Thrashing (쓰레싱)
- Working-set
- Page Fault Frequency scheme
- Page Size의 결정
가상 메모리는 전적으로 OS가 관여한다!
존재 이유 : 사용자 프로그램이 물리 메모리보다 크기 때문
Demand Paging
🌄 실제로 필요할 때 page를 메모리에 올리는 것 → 한정된 메모리에서의 효율성
- I/O 양의 감소
- 메모리 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid / Invalid bit의 사용
- invalid?
- 사용되지 않는 주소 영역인 경우
- 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 page entry가 invalid로 초기화
- 주소 변환 시에 invalid bit으로 설정→ “page fault”
- cpu는 자동적으로 os에게 운영권을 넘김 ⇒ page fault trap
- 운영체제는 page fault에 대한 루틴이 설정되있음
Copy on Write
fork() 시스템 콜 호출 시 자식 프로세스는 부모 프로세스의 주소 공간을 복사해주어 동일한 주소 공간을 제공 → exec() 바로 부를거면 낭비
- 다 복제해오는 대신 쓰기 시 복사를 사용
- 자식 프로세스가 시작될 때 부모의 페이지를 같이 쓰기로 함
- 둘 중 한 프로세스가 공유 중인 페이지에 쓸 때 그 페이지의 복사본이 만들어진다.
Page Fault
- invalid page를 접근하면 MMU(하드웨어)가 trap을 발생시킴
- 커널 모드로 들어가서 page fault handler가 불러짐
- 다음과 같은 순서로 page fault 처리
- invalid reference? (잘못된 주소인가?, 보호처리해야되는가?) ⇒ abort 처리
- 정상이다 → 빈 페이지 프레임을 가져옴 (없으면 뺏어옴 : replace)
- 해당 페이지를 disk에서 메모리로 읽어옴
- disk I/O가 끝나기까지 이 프로세스는 cpu를 선점 당함 (disk가 너무 느리기에 block)
- disk read가 끝나면 인터럽트 → page tables entry 기록, valid / invalid bit → “valid”
- ready queue에 프로세스를 넣음 → 나중에 디스패치
- 이 프로세스가 cpu를 잡고 다시 running
- 아까 중단되었던 명령어를 재개
Performance of Demand Paging
🪐 Disk에서 무언가를 처리하는 건 너무 오래 걸리는 일
- Page Fault Rate : 0≤ p ≤ 1
Effective Access Time
= (1-p) x memory access
- p (os & hw page fault 오버헤드
- 스왑 페이지 아웃
- 스왑 페이지 인
- os & hw 재개 오버헤드
Free Frame 이 없는 경우
Page Replacement
- 어떤 프레임을 빼앗아올지 결정해야 함
- 곧바로 사용되지 않은 페이지를 쫓아내는 것이 좋음
- 단 쫓아낼 때, 해당 프레임이 변경 사항이 있다면 write 하고 처리해야됨
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
Replacement Algorithm
- page-fault rate을 최소화하는 것이 목표
- 알고리즘의 평가
- 주어진 page referecne string에 대해 page fault를 얼마나 내는지 조사
- reference string의 예
- 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4,
Optimal Algorithm
- MIN(OPT) : 가장 먼 미래에 참조되는 page를 교체
- 미래의 참조를 어떻게 아는가?
- Offline algorithm
- 미리 알고잇다는 가정하에 운영하는 것
- 다른 알고리즘의 성능에 대한 upper bound 제공
FIFO Algorithm
FIFO 알고리즘에서는 프레임 수를 늘려줬음에도 page fault 가 더 늘어나는 경우도 있다!
LRU(Least Recently Used) Algorithm
🏸 가장 오래 전에 참조된 것을 지움
- 마지막 참조 시점만 보기에 그 이전 행동들은 고려 안함
- 많이 참조되었지만 마지막 참조 시점만 멀다고 victim으로 선정됨
LFU (Least Frequently Used) Algorithm
🔑 참조 횟수가 가장 적은 페이지를 지움
✔︎ 최저 참조 횟수인 page가 여럿 있는 경우
- LFU 알고리즘 자체에서는 여러 page 중 임의로 선정
- 성능 향상을 위해 가장 오래 전에 참조된 Page 를 지우게 구현할 수도 있음
✔︎ 장단점
- LRU 처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
- 참조 시점의 최근성을 반영하지 못함
- 이제 막 참조를 많이 할려하는데 선정될 수 있음
- LRU보다 구현 복잡
LRU / LFU 구현 방법
LRU
- Doubly 링크드리스트를 통해서 구현 가능
- 즉 가장 head에 있는 놈을 삭제하면 됨
- O(1) TC
- vicitim 을 선정하는데 걸리는 시간복잡도
- hashmap 을 활용하여 O(1)을 유지함
LFU
- 이진트리를 구성하여 참조 횟수를 업데이트하는 방식
- O(logn)으로 가능
- 탐색을 통해 counter + 1
- 없다면 노드 추가
다양한 caching 기법
paging system 외에도 cache memory, 버퍼 caching,
web caching(LFU, 이미 받아놓은 내용을 하드에 저장해두면 web server까지 안가도 되는~, 물리적 거리의 완화) 등 다양한 분야에 사용
✓ 캐쉬 운영의 시간 제약
- 고체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
- Buffer Caching이나 web caching의 경우
- O(1)에서 O(logn)정도까지 허용
- Paging System인 경우
- page fault인 경우에만 OS가 관여함
- 페이지가 이미 메모리에 존재하는 경우 참조시각등의 정보를 OS가 알 수 없음
- O(1)인 LRU list 조작조차 불가능
⇒ LRU / LFU 알고리즘은 페이지 시스템에서 사용할 수 없다!!
왜 LRU / LFU를 실제로 사용할 수 없는가?
- 이미 메모리에 올라와있는 페이지라면 OS가 관여될 타이밍 없음
- 주소 변환은 하드웨어에 의해 일어나는 일이고 그렇기에 참조 시간 또한 OS가 알 길이 없음
- 메모리에 없다면 어떻게 될까?
- 이때는 Page Fault가 나면서 운영체제에게 CPU운영권이 넘어감
- 이때는 time stamp만을 알 수 있긴함
⇒ 따라서 운영체제의 개입이 드문드문 있기에 알고리즘 적용이 안됨
Clock Algorithm(LRU 근사 알고리즘)
🔑 실제 페이징 시스템이 사용하는 알고리즘!
- 각 페이지마다 Reference bit(access bit)가 있음
- 하드웨어가 이를 처리함 → 사용할 때마다
- 비트가 1이라면 최근에 사용됐다 / 0이면 사용 안됐다.
- 따라서 0으로 표시된 페이지를 victim으로 선정함
- 이때 0이라고 해서 LRU 는 아니지만 사용 안된거 맞기에 근사 알고리즘
Clock 작용 원리
- 지금 가르키고 있는 페이지가 1이라면 0으로 바꾸고 다음 칸으로 옮김
- 현재 칸이 0이라면 해당 페이지를 선정
- 적어도 한바퀴 돌고 내쫓기 때문에 Second Chance 알고리즘
Clock algorithm의 개선
- reference bit(읽기 전용) 과 modified bit(쓰기)을 사용
- 메모리에 올라온 뒤로 modified bit이 1이라면 디스크에 따로 쓰고 처리한다는 뜻
Page Frame의 Allocation
🎳 각 프로세스에 얼마만큼의 page frame을 할당할 것인가?
Allocation의 필요성
- 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지 동시 참조
- 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
- Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함
- 최소한의 allocation이 없으면 매 loop 마다 page fault
Allocation scheme
- 균등 할당 : 모든 프로세스에 똑같은 개수 할당
- 비례 할당 : 프로세스 크기에 비례하여 할당
- 우선순위 할당 : 프로세스의 우선순위에 따라 다르게 할당
Global vs. Local Replacement
Global Replacement (페이지 별 무한경쟁)
- Replace 시 다른 프로세스에 할당된 프레임을 빼앗아 올 수 있다.
- 프로세스별 할당량을 조절하는 또 다른 방법
- FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
- Working set, PFF 알고리즘 사용
Local Replacement (프로세스 안에서 경쟁)
- 자신에게 할당된 frame 내에서만 replacement
- FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영시
Thrashing (쓰레싱)
많은 수의 프로그램을 올려놓아 프로그램한테 CPU를 줘도 각자 조금씩밖에
메모리를 할당 받아 Page Fault가 급격히 많아져 CPU 사용량이 뚝 떨어지는 현상
- Page Fault Rate가 매우 높아짐
- OS는 MPD를 더욱 높여야 된다고 생각해서 더 많은 프로세스를 받음
- 프로세스 당 할당된 frame의 수가 더욱 감소
- 프로세스는 page의 swap in / out 하느라 더 바빠짐
- 대부분의 CPU는 한가해지는 상태
Working-set
🎳 Locality of reference (지역성의 원리)를 활용!
- 프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조
- 집중적으로 참조되는 해당 페이지들의 집합을 locality set이라 함
✓ locality 에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합은 Working set이라 정의
✓ Working set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame 을 반납한 후 swap out(suspend)
✓ Thrashing 방지 및 MPD 결정
Working set algorithm
🥉 Working set의 결정 → 과거를 통해 알아내자
- working set window를 통해 알아냄
- window size가 \(\delta\) 인 경우
- 시각 t_i에서의 working set WS(t_i)
- time interval[t-\(\delta\), t_i] 사이에 참조된 서로 다른 페이지들의 집합
- working set에 속한 페이지는 메모리에 유지, 속하지 않는 것은 버림
(즉 참조된 후 \(\delta\) 시간 동안 해당 페이지를 메모리에 유지한 후 버림)
- 시각 t_i에서의 working set WS(t_i)
Page Fault Frequency scheme
🥉 page fault rate의 상한값과 하한값을 두자!
- page fault rate이 상한값을 넘으면 frame 을 더 할당한다.
- page fault rate이 하한값 이하이면 할당 frame 수를 줄인다.
빈 frame이 없으면 일부 프로세스를 swap out!
Page Size의 결정
🎄 주소 체계에 따라 page는 얼만큼으로 상정해야 하는가?
Page size를 감소시키면
- 페이지 수 증가
- 페이지 테이블 크기 증가
- 내부 단편화 감소
- disk 전송의 효율성 감소 (지역성의 원리가 깨져서)
- seek / roation vs. transfer
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
- locality의 활용 측면에서는 좋지 않음
⇒ 트렌드는 큰 페이지 사이즈!
OS 정리가 이로써 마무리됐다. 다시 정리하면서 많이 이해하고 머릿속으로 차곡차곡 쌓아간 것 같다. OS 준비하는 사람들 모두 화이팅~
