프로세스 전체가 메모리에 올라오지 않더라도 실행이 가능하도록 하는 기법
→ 메모리 크기 제약으로부터 자유로워짐
- 가상 메모리 공간 > 실제 메모리 공간
- 프로그램의 일부만 실행을 위해 메모리에 상주
- 프로그램들이 보다 빨리 실행
어떤 page가 필요한 시점에만 해당 page를 메모리로 가져오는 전략
- page가 필요하지 않을 때는 메모리에 로드 X
- 적은 메모리로 프로그램 실행 가능
- 더 많은 사용자들을 받을 수 있음
- 입출력 감소
- 응답시간 빨라짐
🤔 메모리에 없는 아무 프로세스나 접근 하고 싶으면? 응답 시간이 늘어나지 않을까?
🤭 지역성의 원리(Locality of reference)로 인해 페이지 부재 확률은 매우 낮다.
시간적 지역성
: CPU는 어느 메모리 공간을 읽은 후, 시간이 지나도 그 공간을 다시 읽을 확률이 매우 높다는 것을 말한다.
대표적인 예로 반복문이 있다. 반복문은 하나의 코드 공간을 여러 번 읽는다.
공간적 지역성
: CPU가 메모리 공간을 읽을 때는 인접한 범위 내에서 읽는다는 의미이다.
프로그램은 대부분 절차적인 순서로 구현되어 있어 순서대로 읽는 경우가 빈번하다.
프로세스가 최초로 실행될 때는 어떤 페이지가 필요한지 알 수 없으므로, 아무 페이지도 올리지 않음.
순수하게 필요한 페이지만 올려 메모리를 최대한 효율적으로 사용
→ 프로그램을 실행하자마자 page fault가 발생
- 공통점
- 메모리와 backing store 사이를 서로 오고 가는 기능 수행
- 차이점
- swapper: 전체 프로세스를 페이징
- lazy swapper (pager): 프로세스 내의 개별 페이지들을 관리
- 0: 해당 페이지가 유효하지 않거나(가상 주소 공간상 정의 X) 유효 하지만 디스크에 존재
- 1: 해당 페이지가 메모리에 존재
Demending Paing은 페이지 테이블에 해당 페이지가 없으면 backing store에서 메모리로 가져오는 과정이 있으므로, 페이지 테이블에 해당 페이지가 있을 때와 없을 때 시간 차이가 발생한다.
이러한 시간 차이를 고려하여 평균적으로 어느정도 소요되는지 계산하는 것을 유효 접근 시간이라 한다.
메모리 접근 시간 = 200nsec
평균 페이지 폴트 처리 시간 = 8msec (seek time + rotational delay + transfer time)
유효 접근 시간 = (1-p) 200 + p 8,000,000 = 200 + 7,999,800 * p
= 1/1,000 => T = 8.2usec (40배 정도 느림)
= 1/399,990 => T = 220nsec (10% 정도 느림)
위의 예제로는 요구 페이징 때문에 컴퓨터가 40배나 느려지기 때문에 page fault는 매우 적은 확률로 발생해야 효율적이다.
그러나 위에서 설명한 지역성의 원리로 페이지 부재가 현실적으로 발생할 확률은 매우 낮으므로 예제와 같이 40배로 느려지는 일은 거의 없다. 여기서 더 효율적으로 사용하기 위해서는 페이지 부재일 때 소요되는 시간을 줄일 수 있는데, backing store로 HDD를 사용하기 보다는 더욱 빠르게 동작하는 SSD나 저가 DRAM과 같은 것을 사용하는 방법이 있다.
- 메인 메모리에 load해 돌리는 프로그램의 개수가 늘어나 CPU 이용률이 높아져 생산성 증가
- 과도한 메모리 할당으로 인해 빈 메모리 공간이 없을 수 있음
- 프로세스 한 개를 죽여 사용중이던 메모리 회수. (실행 중 죽었기 때문에 피해 큼 😅)
- Page Replacement
- 디스크에서 원하는 페이지의 위치 찾기
- 내용을 메인메모리로 가져오기 위해 빈 프레임 찾음
- 빈 프레임이 있는 경우 해당 프레임 사용
- 여유 프레임이 없는 경우, 페이지 교체 알고리즘을 이용해 희생될 프레임 선정
- swap out 하기 위해 디스크에 write 한 후 희생된 페이지의 테이블 번호를 지우고 invalid로 변경
- 빼앗은 프레임에 새 페이지를 읽어오고 프레임 테이블 업데이트
- 페이지 폴트가 발생한 지점에서부터 사용자 프로세스 재시작
→ 빈 프레임이 없는 경우 디스크를 두 번(프레임을 비울 때, 읽어 들일 때) 접근해야됨
= 페이지 폴트 처리시간 2배 소요
= 유효 접근 시간 증가
- 페이지 전송의 오버헤드 감소를 위해 페이지가 수정될 때 변경 비트(modify bit) 기록
- 0일 경우 메인메모리와 디스크의 내용이 같아 write 작업 없이 swap out 가능 (쓰는 작업 생략. 읽는 작업만)
- 1일 경우 수정된 것이기 때문에 내용이 달라 디스크에 write 해야 빈 자리 마련 가능
- 가장 간단한 페이지 교체 알고리즘
- 메모리에 올리온 지 가장 오래된 페이지가 교체 대상
- FIFO queue 를 사용해 순서 기억
- 성능이 항상 좋지는 않음
- 교체된 페이지가 초기화 된 뒤 계속해서 자주 사용되는 변수를 포함하고 있을 수 있음
- 앞으로 가장 오래 사용하지 않을 페이지가 교체 대상
- 이론적으로는 최적이지만 실현 불가능
- 프로세스가 앞으로 메모리를 어떻게 참조할 것인지 미리 알아야 하기 때문
- 가장 최근에 사용되지 않은 페이지가 교체 대상
- 최적 알고리즘의 근사 알고리즘(미래 대신 과거 시간에 대해 적용한 최적 교체 정책)
- 각 페이지마다 마지막 사용 시간 유지
- 페이지 교체 알고리즘으로 자주 사용. 좋은 알고리즘으로 인정받음
- 메모리가 커지면 fault 가 늘어나지 않고 줄어들거나 같음 (
Belady's Anomaly) - 가장 오래 전 사용된 페이지를 찾기 위해 하드웨어의 지원 필요
- Counters 사용
- Stack
- 하드웨어 지원이 없어 counter, stack을 쓸 수 없는 경우
- 그러나 많은 시스템은 참조 비트(reference bit)로 어느 정도의 지원은 하고 있음
- 페이지가 참조될 때마다 비트 0 → 1
Page table 내 각각의 Page에 8 비트 짜리 참조 비트가 존재하여 일정 시간의 간격마다 Access 되었던 페이지들의 비트들을 오른쪽으로 Shift 하는 연산 실행
→ 가장 큰 값의 비트를 가진 페이지가 최근에 Access 되었다는 것 알 수 있음
또, 가장 작은 값의 비트를 가진 페이지들이 교체 대상으로 선택 되며 같은 값들에 대해서는 FIFO 알고리즘을 이용하여 교체 페이지 선정
FIFO 알고리즘을 기반, 2차 기회를 줄지 안줄지는 참조 비트를 사용해 결정
참조 비트가 0이면 페이지를 교체하고 1이면 다시 한 번 기회를 주고 참조 비트를 0으로 설정한 후 다음 FIFO 페이지로 이동
만일 모든 Page의 Reference bit가 1이라면 결국은 FIFO 방식으로 작동
참조 비트와 변경 비트를 사용
- (0, 0) 최근에 사용되지도 변경되지도 않은 경우 → 교체하기 가장 좋은 페이지
- (0, 1) 최근에 사용되지 않았지만 변경된 경우 → 이 페이지를 뺏으려면 디스크에 내용 기록해야 됨
- (1, 0) 최근에 사용됐지만 변경은 되지 않은 경우 → 이 페이지는 곧 다시 사용될 가능성이 높음
- (1, 1) 최근에 사용됐고 변경도 된 경우 → 아마 곧 다시 사용될 것이면 뺏으려면 디스크에 내용 기록해야 됨
각 페이지를 참조할 때마다 계수
- LFU(Least Frequently Used) Algorithm
- 사용 빈도수 낮은 페이지 교체
- 지금까지 사용이 잘 안됐기 때문에 앞으로도 사용 안할 것
- 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제 발생
- MFU(Most Frequently Used) Algorithm
- 사용 빈도수 높은 페이지 교체
- 참조 회수가 적으면 가장 최근 참조된 것이고 앞으로 사용될 것
- 구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문에 실제 사용 거의 X
- 시스템들이 가용 프레임 여러 개를 풀(pool)로 가지고 있다가, 페이지 폴트 발생 시 교체될 페이지 내용을 디스크에 기록하기 전 가용 프레임에 새로운 페이지를 먼저 읽어 들이는 방법
- 페이지 폴트 발생 시
- 교체될 페이지 선택
- 교체될 페이지가 기록되기 전에 원하는 페이지가 풀에서 자유 프레임으로 읽혀짐
- 교체될 페이지가 기록되고 해당 프레임이 자유 프레임 풀에 추가됨
- swapping 시간 단축(2n → n)으로 fault가 발생한 페이지를 메인메모리로 빨리 옮기는 것 가능
- 전체 작업 양은 동일
- 각 프로세스마다 최소로 할당해야 할 프레임 수 존재
- 정적 할당
- 균등 할당 (Equal Allocation)
모든 프로세스에게 똑같은 메모리 할당 - 비례 할당 (Proportional Allocation)
프로그램 크기에 비례해 메모리 할당 - 우선 순위 할당 (Priority Allocation)
우선 순위 높은 프로세스에게 메모리 많이 할당
메모리 많이 할당 시 페이지 폴트 발생 감소 → 더 빨리 실행
- 균등 할당 (Equal Allocation)
- 동적 할당
- Locality Model
- 특정 시간에는 일정 범위의 페이지를 주로 참조하기 때문에 특정 시간에 따라 사용하는 페이지의 개수만큼 프레임을 할당
- 프로세스를 미리 수행해봐야 할 수 있다는 단점
- 프로세스를 수행할 때마다 사용하는 기능이 달라질 수 있으므로, Locality를 이용하는 방법은 비현실적
- Working Set Model
- locality의 방식과 유사한데, 미래가 아닌 과거를 보는 것
- working set = 현재 시간에서 일정 시간(△) 이전동안 사용되었던 페이지의 집합
- working set의 개수만큼 프레임 할당
- Locality Model
- 전역 교체
메모리 상의 모든 프로세스 페이지에 대한 교체 작업 수행- 장점: 전체를 보기 때문에 효율적 메모리 운영 가능
- 단점: 어떤 프로세스 성능이 상황에 따라 실행 중 달라질 수 있음. 메모리 영역이 줄어들수록 프로그램 실행 중 fault 많이 발생
- 지역 교체
메모리 상의 자기 자신의 프로세스 페이지에 대해서만 교체 작업 수행- 장점: 프로세스의 성능이 변하지 않고 일정하게 유지
- 단점: 다른 프레임 작업이 끝나 비어있어도 fault 발생한 프레임에만 할당 해 전체적인 생산성은 안좋아질 수 있음. 성능에 도움 X
page in/out은 디스크 I/O 작업이다. 그러므로 이 작업이 많아질수록 CPU는 그동안 아무것도 하지 않게 된다.
- 프로세스가 증가했지만 충분한 메모리가 각 프로세스에 할당되지 않아 fault 발생
- 각 프로세스에 할당된 메모리가 극단적으로 작아지면 fault 극단적으로 늘어남
- fault 처리를 위해 page in/out 작업 발생
- page in/out은 디스크 I/O 작업으로 작업 속도가 느리고 CPU를 사용하지 않는 작업
= page fault 처리되지 않고 wait 상태 - wait 상태에서 기다리는 프로세스들이 많아짐
→ ready 상태의 프로세스가 없어져 CPU는 그동안 아무것도 하지 않음. 사용자가 느끼기엔 컴퓨터가 먹통
- Global Replacement보다 Local Replacement를 사용
메모리 사용 효율이 떨어지는 단점 존재 - 프로세스당 충분한/적절한 수의 프레임(메모리) 할당
출처