Last update: @1/7/2023
•
요구 페이징(demand paging)
: 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 실행에 요구되는 페이지만을 메모리에 적재하는 기법
◦
기본적인 양상
1.
CPU가 특정 페이지에 접근하는 명령어를 실행
2.
해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레
임에 접근
3.
해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생
4.
페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정
5.
다시 1 번을 수행
◦
순수 요구 페이징 기법(pure demand paging)
: 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 하는 것
▪
이 경우 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하게 되고, 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어짐
◦
페이지 교체 알고리즘
: 메모리가 가득 찼을 때 쫓아낼 페이지를 결정하는 방법
▪
페이지 폴트가 적게 일어나게 하는 것이 좋은 페이지 교체 알고리즘임
▪
따라서 페이지 폴트 횟수를 알 수 있어야 하고, 이는 페이지 참조열(page reference string)을 통해 알 수 있음
•
페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미함
◦
예를 들어 CPU가 2 2 2 3 5 5 3 3 7의 순서로 페이지에 접근한 경우 연속된 것을 제외한 2 3 5 3 7이 페이지 참조열
◦
연속된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문에 생략함
▪
알고리즘의 종류
•
FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacment Algorithm)
: 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
◦
아이디어와 구현이 간단하지만 좋지 않은 방식
•
2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)
: FIFO 페이지 교체 알고리즘의 변형으로, 참조 비트가 1일 경우 당장 내쫓지 않고 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정하는 방식.
◦
메모리에 가장 오래 머물렀다고 할지라도 참조 비트가 1이라는 의미는 CPU가 접근한 적이 있다는 의미이므로 한 번의 기회를 더 주는 셈
◦
메모리에 가장 오래 머무른 페이지의 참조 비트가 0일 경우 이 페이지는 가장 오래된 페이지이면서 동시에 사용되지 않은 페이지라고 볼 수 있으므로 보조기억장치로 내보내면 됨
•
최적 페이지 교체 알고리즘(optimal page replacement algorithm)
: CPU에 의해 참조되는 횟수를 고려하여 앞으로의 사용 빈도가 가장 낮을 페이지를 교체하는 알고리즘
◦
최적 페이지 교체 알고리즘은 이름 그대로 가장 낮은 페이지 폴트율을 보장하기에 타 알고리즘에 비해 페이지 폴트 발생 빈도가 가장 낮음
◦
앞으로 오랫동안 사용되지 않을 페이지를 예측하는 것이 어렵기 때문에 실제 구현이 어려움
◦
따라서 최적 페이지 교체 알고리즘은 그자체를 운영체제에서 사용하기보다는, 주로 다른 알고리즘의 이론상 성능을 평가하기위한 목적으로 사용됨
▪
최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 페이지 폴트의 하한선으로 간주하고, 이에 비해 얼만큼 페이지 폴트가 발생하느냐를 통해 알고리즘을 평가함
•
LRU 페이지 교체 알고리즘(LRU; Least Recently Used Page Replacement Algorithm)
: 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘.
◦
‘최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것’이라는 아이디어를 토대로 만들어진 알고리즘
◦
페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체함
◦
스래싱과 프레임 할당
▪
프로세스가 사용할 수 있는 프레임 수가 적으면 페이지 폴트가 자주 발생함
▪
스래싱(thrashing)
: 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
•
멀티프로그래밍의 정도(degree of multiprogramming)
: 메모리에서 동시에 실행되는 프로세스의 수
•
동시에 실행되는 프로세스 수가 어느 정도 증가하면 CPU 이용률이 높아지지만, 필요 이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 지나치게 빈번히 발생하고, 이에 따라 CPU 이용률이 떨어져 전체적인 성능이 저해됨
•
아무리 CPU의 성능이 뛰어나도 동시에 실행되는 프로세스를 수용할 물리 메모리가 너무 작다면 전체 컴퓨터의 성능이 안 좋아지는 이유는 이러한 이유 때문
•
스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문임
◦
가령 프로세스 A를 무리 없이 실행하기 위해서는 최소 열 개의 프레임이 필요한데도 불구하고 프로세스 A가 다섯 개의 프레임만 이용할 수 있다면 이 프로세스는 페이지 폴트가 자주
발생함. 스래싱 발생 위험이 높아지는 것
◦
그렇기에 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 함
▪
프레임 할당 방식
•
정적 할당 방식
: 프로세스의 실행 과정을 고려하지 않고 단순히 프로세서의 크기와 물리 메모리의 크기만을 고려해 프레임을 할당하는 방식
◦
균등 할당(equal allocation)
: 모든 프로세스에 균등하게 프레임을 제공하는 방식
◦
비례 할당(proportional allocation)
: 프로세스의 크기에 비례해 프레임을 제공하는 방식
•
동적 할당 방식
: 프로세스가 실행되는 것을 보고 실제로 필요한 프레임 수를 할당하는 방식
◦
작업 집합 모델(working set model)
: ‘프로세스가 일정 기간 동안 참조한 페이지 집합’인 작업 집합(working set)을 기억하여 빈번한 페이지 교체를 방지(참조 지역성의 원리)
▪
어떤 프로세스를 실행할 때 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당
▪
A, B 프로세스가 각각 10번씩 페이지를 참조했어도 A는 한 개의 프레임만 집중적으로 참조했을 수도 있고, B는 10개의 페이지를 골고루 참조했을 수도 있음. 이 경우 A 프로세스에는 한 개의 프레임을, B 프로세스에는 10개의 페이지를 할당하는 식임
◦
페이지 폴트 빈도(PFF; Page-Fault Frequency)
: 페이지 폴트 빈도가 높은 프로세스에 더 많은 프레임을 할당하는 방식
▪
페이지 폴트율이 하한선을 넘어가면 프레임을 더 할당함
▪
페이지 폴트율이 상한선을 넘어가면 프레임을 회수함