페이징
요구 페이징
- 프로세스 실행에 필요한 일부 페이지만 실제 물리 메모리에 올리고, 나머지는 필요할 때(Demand) 페이지 위로 가져오는 방식입니다.
(1) CPU가 특정 페이지에 접근하는 명령어를 실행한다.
(2) 해당 페이지가 현재 메모리에 있을 경우 ( 유효 비트가 1일 경우 ) CPU는 페이지가 적재된 프레임에 접근한다.
(3) 해당 페이지가 현재 메모리에 없을 경우 ( 유효 비트가 0일 경우 ) 페이지 폴트가 발생한다.
(4) 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
(5) 다시 (1) 번을 수행한다.
페이지 교체 알고리즘
- 요구 페이징 기법으로 페이지들을 적재하다보면 언젠간 메모리가 가득 차게 된다.
- 당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야한다.
- 이 때 , 어떤 페이지를 내보낼까?
- 이를 결정하는 방법(알고리즘)이 페이지 교체 알고리즘이다.
- 어떤 페이지 교체 알고리즘이 좋은걸까?
→ 페이지 폴트가 적은 알고리즘이 좋은 알고리즘이다! - 페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능이 저하된다.
- 어떤 페이지 교체 알고리즘이 좋은걸까?
- 페이지 참조열
- CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
FIFO 페이지 교체 알고리즘
→ 가장 단순한 방식
- 먼저 들어온 것을 먼저 내보내는 것이다
FIFO 페이지 교체 알고리즘 - 보완책
- 2차 기회 페이지 교체 알고리즘
기본 동작
- FIFO처럼 큐를 사용하지만, 각 페이지마다 Reference bit(참조 비트)를 둠
- 참조비트가 1이면 → 한 번 더 기회를 주고 뒤로 보냄
- 참조비트가 0이면 → 교체
흐름
- 큐 front의 페이지를 검사
- R 비트가 1이면 → 0으로 바꾸고 큐의 뒤로 이동 (2차 기회)
- R 비트가 0이면 → 교체
최적 페이지 교체 알고리즘
- 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
- 가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘이다
- 그러나, 실제 구현이 어렵다
LRU(Least-Recently-Used) 페이지 교체 알고리즘
- 최적 페이지 교체 알고리즘 : 가장 오래 사용되지 않을 페이지 교체
- LRU 페이지 교체 알고리즘 : 가장 오래 사용되지 않은 페이지 교체
핵심 기준
- 최근 사용 여부(시간적 지역성)
- 오랫동안 참조되지 않은 페이지는 앞으로도 잘 쓰이지 않을 가능성이 높다
동장 방식
페이지 접근(참조) 순서를 시간 기준으로 기록해두고,
-
페이지 폴트 발생 시
-
메모리에 있는 페이지 중
가장 오래 동안 사용되지 않은 페이지를 찾아 제거
-
새 페이지를 그 자리에 넣음
스래싱과 프레임 할당
페이지 폴트가 자주 발생하는 이유
- 나쁜 페이지 교체 알고리즘을 사용해서이다
- 프로세스가 사용할 수 있는 프레임 자체가 적어서이다.
스래싱
: 페이지 폴트가 너무 자주 발생해서 CPU가 실제 작업보다 페이지 교체(스와핑)에 더 많은 시간을 쓰는 비정상적인 상태
- 프로그램이 메모리에서 계속 필요한 페이지를 찾지 못함 → 페이지 폴트 발생
- 그때마다 디스크에서 페이지 가져오고(매우 느림)
- CPU는 실제 일을 못 하고 계속 페이지 적재 작업만 반복
→ 시스템 전체 속도가 극심하게 떨어지는 현상
스래싱 발생 이유
- 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다
- 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 항당해주어야 한다.
프레임 할당 방식
1.균등 할당
- 가장 단순한 할당 방식
- 모든 프로세스들에게 균등하게 프레임을 할당하는 방식이다.
2.비례 할당
- 프로세스의 크기를 고려해서 할당
3.작업 집합 모델
- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- 스레싱이 발생하는 이유는 빈번한 페이지 교체 때문
- 그렇다면 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 된다
- ‘프로세스가 일정 기간 동안 참조한 페이지 집합’을 기억하여 빈번한 페이지 교체를 방지
- 작업 집합이란 ‘실행 중인 프로세스가 일정 기간 동안 참조한 페이지의 집합’이다.
& 작업 집합 계산
- 1.프로세스가 참조한 페이지
- 2.시간 간격이 필요
4.페이지 폴트 빈도
- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- 두 개의 가정에서 생겨난 아이디어
- 1.페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
- 2.페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
정리
요구 페이징은 프로그램 전체를 메모리에 올리지 않고 필요한 페이지만 메모리에 적재하는 방식으로, CPU가 접근하려는 페이지가 메모리에 없으면 페이지 폴트가 발생하고, 운영체제가 해당 페이지를 디스크에서 가져와 적재한 뒤 다시 실행을 이어간다. 그러나 메모리가 가득 찬 상황에서는 새로운 페이지를 적재하기 위해 기존 페이지를 내보내야 하므로 페이지 교체 알고리즘이 필요해지는데, FIFO(가장 먼저 들어온 페이지 제거), 2차 기회(참조 비트로 한 번 더 기회 부여), 최적 알고리즘(앞으로 가장 늦게 사용되는 페이지 제거), LRU(가장 오래 사용되지 않은 페이지 제거) 등이 사용된다. 이 알고리즘들의 핵심 목표는 페이지 폴트를 최소화하여 성능을 높이는 것이다.
페이지 폴트가 과도하게 발생하면 시스템은 실제 작업보다 페이지 교체 작업에 더 많은 시간을 사용하게 되는데, 이를 스래싱(thrashing)이라고 하며 시스템 성능이 급격히 저하된다. 스래싱을 방지하기 위해 프로세스에 충분한 프레임을 배분해야 하며, 프레임 할당 방식으로는 균등 할당, 비례 할당, 작업 집합 모델(특정 기간에 사용된 페이지 집합에 기반한 동적 프레임 조절), 페이지 폴트 빈도(PFF) 방식(폴트율이 높으면 프레임 증가, 낮으면 감소)이 있다. 이러한 기법들은 프로세스의 메모리 요구량을 정확히 충족시켜 불필요한 페이지 교체를 줄이고 안정적인 시스템 성능을 유지하는 것을 목표로 한다.
참고
