가상 메모리(Virtual Memory)
Paging & Segmentation
페이징과 분할의 두 가지 특성은 메모리 관리에서 획기적인 발전의 열쇠이다.
1. 프로세스는 여러 조각(페이지 또는 세그먼트)으로 분할될 수 있으며, 이러한 조각은 실행 중인 메인 메모리에 연속적으로 위치할 필요가 없음.
2. 프로세스 내의 모든 메모리 참조는 실행 시 물리적 주소로 동적으로 변환되는 논리적 주소이다. 이는 프로세스가 상이한 시간에 메인 메모리의 상이한 영역일 수 있다는 것을 의미한다.
지역성(Locality)
프로세스 내의 프로그램 및 데이터 참조가 클러스터링 되는 경향이 있음.
- Knuth의 추정 : 90%의 시간이 코드의 10% 내에서 발생한다.
- 즉 일정 기간동안 몇 가지 프로세스만 필요할 것이다.
따라서 우리는 지역성의 원리가 가상 메모리 체계에서 사용됨을 생각할 수 있다.
페이징 또는 세분화를 기반으로 하는 가상 메모리는 현대 운영 체제의 필수 구성 요소가 되었음.
Fetch Policy
페이지를 메인 메모리로 불러 올 시기를 결정한다.
Demand Paging
- 페이지는 해당 페이지의 위치를 참조할 때만 메인 메모리로 가져온다.
- 프로세스가 처음 시작되면 여러 페이지 오류가 발생한다.
- 시간이 지나면 문제가 진정되고, 페이지 폴트 수가 매우 낮은 수준으로 떨어진다.
- 거의 모든 페이징 시스템이 위와 같음.
Preparing
- 페이지 폴트로 인해 요구된 페이지 이외의 페이지가 들어온다.
- 프로세스의 페이지가 보조 메모리에 연속적으로 저장되는 경우, 한 번에 여러 개의 연속된 페이지를 가져오는 것이 더 효율적이다.
- 미래를 미리 모르면 효과적으로 하기 어렵다.
Replacement Policy
현재 메모리에서 바꿀 페이지를 결정하는 것.
- 메인 메모리가 가득 찰 때 마다 발생한다. (사용 가능한 프레임이 없을 때)
- OS가 많은 프로세스를 메인 메모리로 가져오려고 할 때 발생한다. (멀티 프로그래밍 수준 증가)
목표
- 제거되는 페이지는 가까운 미래에 참조될 가능성이 가장 낮은 페이지여야만 한다.
- 최근 참조 이력과 가까운 미래 참조 패턴 간의 상관 관계.
- 따라서 대부분의 정책은 과거의 행동에 기초하여 미래의 행동을 예측하려고 한다.
Replacement Algorithm
1. 최적(Optimal)
2. 선입선출(FIFO)
3. 가장 최근에 사용한 것(LRU)
4. Clock (Second-Chance)
5. 두 번째 기회 증가
서로 다른 알고리즘을 비교하기 위해, 우리는 그들 사이의 페이지 폴트 횟수를 비교한다.
참조 문자열 : 참조되는 페이지 순서 , 호출된 페이지 주소 스트림
초기 페이지 오류
- 초기 참조로 인해 페이지 오류가 발생한다.
- 초기 페이지 오류는 계산하지 않는다. (이 숫자의 수는 모든 알고리즘에서 동일하기 때문이다.)
1. Optimal Page Replacement
미래를 알 필요가 있지만, 다른 알고리즘과 비교할 수 있는 표준 역할을 한다.
- 페이지 폴트 발생 횟수가 가장 적음.
- 구현 불가능
가장 오랫동안 사용되지 않는 페이지를 replace 하는 것이다. ( 향후 모든 참조 파악 )
Reference String : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 라고 가정.
Page Faults 횟수 : 2번
2. FIFO Replacement
프로세스에 할당된 페이지 프레임을 버퍼로 처리한다.
장점 : 구현이 간단하다
단점 : 자주 사용하는 페이지가 가장 오래된 경우가 많으므로, FIFO에 의해 반복적으로 호출된다. Belady's Anomaly
Reference String : 1,2,3,4,1,2,5,1,2,3,4,5 가정
4Frame 존재 시 : 6번의 page faults.
3Frame 존재 시 : 5번의 page faults.
더 많은 프레임 존재 시 페이지 폴트의 수는 줄어드는데 Belady's Anomaly는 더 많은 프레임 존재 시 페이지 폴트가 증가함을 일컫는다.
3. LRU(Least Recently Used)
가장 오랫동안 참조되지 않은 페이지를 replace 한다.
Optimal policy 근사화 시도 : 과거를 보고 미래를 추론하는 것.
- optimal policy와 거의 동일한 성능을 발휘하지만, 구현이 어려움.
구현 문제
- 각 참조 페이지의 타임 스탬프
- 각 페이지는(페이지 테이블 엔트리에서) 각 메모리 참조의 시간으로 태그 지정될 수 있다.
- 스택 사용(페이지가 참조 될 때 마다 스택에서 제거되어 맨 위에 배치됨.)
- 이를 위해서는 값비싼 하드웨어와 많은 오버헤드가 필요함.
- LRU 교체 정책에 대한 하드웨어 지원이 부족함.
장점 : LRU는 Belady의 이상 징후를 겪지 않는다. optimal policy에 근사하다.
단점 : 비용 문제. (참조별로 페이지 유지 관리 , 모든 참조에 대한 업데이트)
Reference String : 1,2,3,4,1,2,5,1,2,3,4,5 가정
Page faults 횟수 : 4번
4. Clock(Second Chance)
- 프레임 집합은 순환 버퍼로 간주됨.
- 페이지 프레임에 하나의 참조 비트 사용
- 각 프레임의 사용 비트는 항상 1로 설정됨.
- 페이지가 먼저 프레임에 로드되고 동시에 해당 페이지가 참조됨.
- 메인 메모리가 가득 차면 포인터가 버퍼의 다음 프레임으로 이동함.
- 사용 비트 == 0 으로 발견된 첫 번째 프레임을 바꿈.
- 사용 비트 == 1이면 사용 비트가 0으로 변경됨. Ex. 리눅스 커널
Page 556이 Page 727로 대체됨.
5. 두 번째 기회 증가 (Enhanced Second-chance)
참조 비트와 수정 비트를 모두 순서 쌍으로 간주함.
(0,0) : 최근에 사용하거나 수정하지 않음. - 대체할 가장 좋은 페이지
(0,1) : 최근에 사용되지 않고 수정됨. -쓰기(dirty page)필요 -> I/O 추가 발생
(1,0) : 최근에 사용되었지만 clean. -> 아마 곧 다시 사용 될 것이다.
(1,1) : 최근에 사용 및 수정됨. ->곧 사용됨(쓰기 필요), 가장 낮은 우선순위에서 발견된 첫 번째 페이지를 바꿈
알고리즘 비교
Resident Set Policy
각 프로세스에 할당할 페이지 프레임 수를 결정하는 정책.
- 교체 검토 대상 페이지 세트를 페이지 장애를 일으킨 프로세스로 제한할 지, 또는 메인 메모리의 모든 페이지 프레임을 포함할 지 여부
1. 고정 할당 방식(Fixed-allocation policy)
- 프로세스에 고정 개수의 프레임을 제공한다.
- 해당 프로세스의 페이지 중 하나를 필요한 페이지로 교체해야 한다.
2. 가변 할당 방식(Variable-allocation policy)
- 변경할 프로세스에 할당된 페이지 프레임 수
- 높은 수준의 페이지 폴트를 겪고 있는 프로세스에는 추가 페이지 프레임이 부여된다.
- 반면 페이지 폴트율이 낮은 프로세스에는 낮은 할당이 부여된다.
Thrashing
- 멀티프로그래밍 수준이 높아짐에 따라, 프로세서 utilization도 상승할 것으로 예상된다.
- 페이지 폴트 수가 급격히 증가하여 프로세서 사용률이 감소한다.
- 프로세스에서 페이지를 안팎으로 교환하고 있다.
working set은 프로그램이 임의의 지점에서 접근하는 페이지 집합이다.
(t,Δ) : t 시간에 마지막 Δ에서 참조된 해당 프로세스의 페이지 집합.
Δ는 윈도우 사이즈임.
Working Set Model(Peter Denning)
- 프로세스의 상주 집합에서 작업 집합에 없는 페이지(기본적으로 LRU 정책)를 주기적으로 제거한다.
- 각 프로세스에 대해 시간 순서대로 페이지 대기열을 유지
- 이 경우 모든 프로세스의 워킹 세트 > 물리적 메모리 : Thrashing
각 프로세스에 대한 워킹 세트 측정이 비효율적
- 워킹 세트의 이 개념은 거주자 세트 관리를 위한 참조로 사용될 수 있다.
Δ의 최적값은 알 수 없다.
- Δ가 너무 작으면, 전체 지역을 포함하지 않는다.
- Δ가 너무 클 경우 여러 지역 간에 겹칠 수 있다.
- 극단적으로 Δ가 무한대일 경우 워킹 세트는 프로세스 실행 중에 터치된 페이지 세트이다.