가상 메모리 프로그램이 실행될 때 물리적 메모리(RAM)보다 큰 메모리 공간을 사용하도록 하는 기술 (물리적 메모리 크기의 한계를 극복)
기존에는 프로세스가 실행되는 코드 전체를 메모리에 로드해야 했고, 메모리 용량보다 더 큰 프로그램은 실행할 수 없었음
하지만 실제로는 코드의 일부에서만 대부분의 시간을 사용하고,
프로세스는 특정 순간에는 항상 작은 양의 주소 공간을 사용하기 때문에 이러한 방식은 매우 비효율적
가상 메모리(Virtual Memory)는 이러한 물리적 메모리 크기의 한계를 극복하기 위해 나온 기술
프로세스를 실행할 때 실행에 필요한 일부만 메모리에 로드하고 나머지는 디스크에 둠 (대게 page로 관리)
프로세스 전체가 물리적 메모리에 있는 것 '처럼' 수행, 즉 물리적 메모리가 훨씬 많이 있는 것처럼 보임
결과적으로 더 작은 양의 주소 공간으로 프로세스를 수행할 수 있고, 그에 따라 더 많은 프로그램을 동시에 실행할 수 있음
Demand Paging
실제로 필요할 때 page를 메모리에 올리는 것
CPU 이용률과 처리율이 높아지고, 더 많은 사용자를 수용할 수 있음
page table에서 해당 page가 메모리에 있는지를 나타내는 valid-invalid bit를 사용
주소 변환 과정 1. 하드웨어가 TLB(Translation Lookaside Buffer)를 확인 2. TLB hit인 경우 곧바로 주소를 변환하고, TLB miss인 경우 page table을 확인 (③) 3. page table의 valid-invalid bit가 valid로 되어 있다면 주소를 변환하고 TLB에 page를 올림 invalid라면 page fault가 발생(④) 4. page fault가 발생하면 MMU가 운영체제에 Trap을 걸고 커널 모드로 들어가서 page fault handler가 invoke 5. 유효하지 않은 참조인 경우 프로세스를 종료시키고, 그렇지 않다면 빈 page frame을 얻음 빈 frame이 없다면 메모리에서 victim page를 선택하여 대체 6. 운영체제는 참조된 page를 디스크에서 메모리로 로드(I/O)하고, disk I/O가 끝날 때까지 이 프로세스는 CPU를 빼앗김 7. disk I/O가 끝나면 page table이 업데이트되고 valid-invalid bit가 valid로 바뀌고, ready queue에 프로세스를 넣어줌 8. 프로세스가 CPU를 잡게 되면 다시 이어서 수행
Effective Access Time = (1-p) × memory access + p × (OS&HW page fault overhead + [swap page out if needed] + swap page in + OS&HW restart overhead)
( p = 0 이면, no page fault )
프로세스가 page fault를 발생시켰을 때 대체될 frame의 그룹에 따라 ,
Global Replacement : Replace 할 때 다른 프로세스에 할당된 frame을 빼앗아올 수 있음 - 프로세스별로 frame 할당량을 조절하는 또 다른 방법이 될 수 있지만, 자신의 page fault rate를 조절할 수 없음 * 메모리 내의 모든 페이지를 대상으로 선정하기 때문에, 어떤 페이지가 자주 사용되더라도 교체될 수 있음 - 일반적으로 더 좋은 처리량을 가지므로 가장 흔하게 사용되는 방법
Local Replacement : 자신에게 할당된 frame 내에서만 교체하는 방법 - 알고리즘을 프로세스마다 독자적으로 운영하는 경우 가능 - 쉬고 있는 메모리를 사용할 수 없기 때문에 비교적 비효율적
Page Replacement Algorithm (페이지 교체 알고리즘)
프로그램 실행 시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재)가 발생하면, 원하는 페이지를 보조저장장치에서 가져와야 하는데, 이때 만약 물리 메모리가 모두 사용 중이라면, 페이지 교체가 이뤄져야 한다!!! (또는, 운영체제가 프로세스를 강제 종료하는 방법도 있음)
OPT (Optimal Algorithm)
가장 먼 미래에 참조되는 페이지를 교체하는 방법
항상 최적의 결과를 갖지만, 앞으로의 실행 방향을 알고 있어야 하므로 실제 사용은 어려움 (upper bound 제공)
빨간색 - page fault가 발생한 경우 , 분홍색 - frame에 이미 존재해서 page fault가 발생하지 않은 경우
FIFO (First In First Out) Algorithm
제일 먼저 들어온 페이지를 교체하는 방법
모든 page가 평등하게 frame에 거주하며, 구현하기 쉽다는 장점이 있음
어떤 page는 항상 필요할 수 있는데, 그런 경우에도 교체시킨다는 단점 존재
Belady's anomaly 현상이 발생할 수 있음
Belady's anomaly 현상 : frame이 늘어나도 page fault가 감소하지 않고 오히려 늘어나는 현상 ( 일반적으로는 frame이 증가할수록 page fault가 감소하지만 특정 구간에서 오히려 증가하는 경우가 발생 )
LRU (Least Recently Used) Algorithm
가장 오래전에 참조된 페이지를 교체하는 방법
Optimal에 근접한 방법이며, Belady's anomaly가 발생하지 않음
구현이 어렵고 접근 빈도를 고려하지 않는다는 단점 존재
연결 리스트로 LRU를 구현하면 O(1)만에 page를 찾고 삽입할 수 있음
제일 최근에 참조된 page를 가장 앞으로 옮기는 방식으로 구현 → replace가 일어날 때 가장 뒤에 있는 page를 교체
LFU (Least Frequently Used) Algorithm
참조 횟수가 가장 적은 페이지를 교체하는 방법
LRU에 비해 장기적인 시간 규모를 보기 때문에 page의 인기도를 조금 더 정확히 반영 가능하지만, 최근성은 반영 불가
힙(heap)을 사용하면 최소 빈도를 갖는 page를 찾거나 삽입, 삭제하는데 O(logn) 소요
Second Changed Algorithm (Clock Algorithm)
LRU의 근사(approximation) 알고리즘
가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체 방지를 위한 것으로, FIFO의 단점 보완
최근에 참조되었는지 여부를 나타내는 Reference bit이라는 정보 사용
Reference bit가 1인 페이지는 0으로 바꾼 후 지나가고, 0인 페이지를 찾으면 해당 페이지와 교체
보통의 경우 LRU가 가장 효율적이라고 한다!
Thrashing
프로세스가 원활한 수행에 필요한 최소한의 page frame을 할당받지 못해서, 실행보다 Swapping 하는데 더 많은 시간을 소모하는 현상
Thrashing 발생 과정
1. page가 부족하여 page fault가 증가 2. Swapping(I/O) 작업이 증가하여 CPU 효율성(Utilization)이 감소 3. OS는 Multiprogramming Degree를 높여야 한다고 판단하여 또 다른 프로세스를 시스템에 추가 4. 프로세스당 할당된 page frame이 더욱 감소하여 page fault가 더욱 증가 5. 프로세스는 Swapping으로 인해 매우 바빠져서 CPU 사용률 감소
* Multiprogramming Degree : 현재 메인 메모리에 존재하는 활성화된 일(active job)의 개수
Thrashing Prevention
Working-Set Model
가능한 최대 Multiprogramming Degree를 유지하면서 Thrashing을 막는 방법
프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 frame을 반납한 후 swap out
Multiprogramming degree가 너무 커져 working set을 보장할 수 없는 경우, 모든 page를 반납하고 suspeded 상태로 변환
Working Set : Locality에 기반하여 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합 * 즉, 어떤 프로그램이 실행되면서, 메모리에 빈번히 참조되는 page들의 집합
PFF(Page-Fault Frequency) Scheme
PFF는 page fault의 상한 값과 하한 값을 두고, page fault rate가 상한 값을 넘으면 frame을 더 할당하고, 하한 값보다 낮아지면 할당된 frame 수를 줄이는 방법
