이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.
운영체제는 한정된 물리적 메모리 용량 때문에, 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고, 프로세스들에게 적절한 수의 프레임을 할당해야 한다.
요구 페이징
처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
요구되는 페이지만 적재하는 기법
요구 페이징은 아래의 과정으로 흘러간다.
순수 요구 페이징(pure demand paging)
아무런 페이지도 메모리에 적재하지 않은 채 일단 프로세스 실행
프로세스의 첫 명령어부터 페이지 폴트가 발생
어느 정도 시간이 지난 후부터 페이지 폴트 발생 빈도가 적어짐
요구 페이징이 안정적으로 작동하려면
요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 아래의 두 가지를 해결해야 한다.
페이지 교체
프레임 할당
페이지 교체 알고리즘
요구 페이징 기법으로 페이지를 적재하다 보면 언젠간 메모리가 가득 차게 된다.
메모리가 가득 찬 상황에서 당장 실행에 필요한 페이지를 적재하려면 기존에 적재된 페이지를 보조기억장치로 내보내야 한다.
이때, '기존에 적재된 페이지 중에 어떤 페이지를 내보낼 것인가'를 선택하는 것이 페이지 교체 알고리즘이다.
교체 알고리즘의 성능을 판단할 때 가장 좋다고 보는 것은 페이지 폴트의 횟수가 가장 적은 알고리즘이다.
페이지 폴트가 자주 발생하면 보조기억장치에 접근하는 횟수가 증가한다는 뜻이기 때문이다.
그렇기에 페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수를 알 수 있어야 한다.
그리고 페이지 폴트 횟수는 페이지 참조열(page reference string)을 통해 알 수 있다.
페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지 열을 의미한다.
예를 들어 2 2 2 3 5 5 5 3 7이라는 연속된 페이지열이 있다고 하면 페이지 참조열은 2 3 5 3 7이다.
연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문이다.
페이지 교체 알고리즘을 평가할 때 관심 있게 고려할 것은 오직 페이지 폴트의 발생 횟수이기 때문이고, 어차피 페이지 폴트가 일어나지 않을 연속된 페이지에 대한 참조는 고려하지 않아도 된다.
FIFO(First-In First-Out) 페이지 교체 알고리즘
가장 단순한 방식
메모리에 가장 먼저 적재된 페이지부터 교체되는 알고리즘
프로그램 실행 내내 사용될 페이지조차 오래되면 교체되기 때문에 페이지 폴트가 빈번하게 일어날 수 있다
2차 기회(second-chance) 페이지 교체 알고리즘 -FIFO 페이지 교체 알고리즘의 단점을 보완 -페이지의 참조 비트가 1일 경우(페이지를 참조한 적이 있을 경우) 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 변경 -메모리에 오래 적재되었더라도 CPU가 최근에 접근한 적이 있다면 교체를 미룬다.
최적 페이지 교체 알고리즘
CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
사용 빈도가 가장 낮은 페이지를 예측하여 해당 페이지를 교체하는 알고리즘
실제 구현이 매우 어렵다.(예측을 하는 것이 까다롭다)
주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용
최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 다른 페이지 교체 알고리즘에서 발생하는 페이지 폴트의 하한선으로 간주(평가 목적)
LRU(Least Recently Used) 페이지 교체 알고리즘
가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
페이지마다 마지막으로 사용한 시간을 토대로 가장 사용이 적었던 페이지를 교체
스레싱과 프레임 할당
스레싱(thrashing)
페이지 폴트가 자주 발생하는 이유는 아래와 같다.
나쁜 페이지 교체 알고리즘을 사용해서
프로세스가 사용할 수 있는 프레임 자체가 적어서(메모리 용량이 적어서) (근본적인 이유)
프로세스가 사용할 수 있는 프레임 수가 많으면 일반적으로 페이지 폴트 빈도는 감소한다
반대로 프로세스가 사용할 수 있는 프레임 수가 적어지면 페이지 폴트는 자주 발생한다.
페이지 폴트로 인한 페이지 교체 빈도가 올라가면 성능은 크게 저하된다.
이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱이라고 한다.
스래싱을 그래프로 표현하면 아래와 같다.
x축(멀티프로그래밍의 정도) : 메모리에서 동시 실행되는 프로세스의 수
y축(CPU 이용률) : 말 그대로 CPU 이용률을 뜻한다
이 그래프는 동시에 실행되는 프로세스의 수를 늘린다고 해서 CPU 이용률이 비례해서 증가하는 것이 아님을 나타냄
아무리 CPU의 성능이 뛰어나도 동시에 실행되는 프로세스를 수용할 물리적 메모리 용량이 적다면 전체 컴퓨터의 성능이 나빠진다.
스레싱이 발생하는 근본적 원인은 각 프로세스가 필요로 하는 프레임 수가 보장되지 않았기 때문이다.
예를 들어, A 프로세스는 최소 10개의 프레임이 필요한데, 5개의 프레임 밖에 없다면 페이지 폴트가 자주 발생한다.
따라서 스레싱 발생 위험도 높아진다.
그렇기에 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.
프레임 할당
정적 할당 방식
균등 할당(equal allocation) : 모든 프로세스들에게 균등하게 프레임을 할당하는 방식(프로세스들의 크기는 각기 다른데 모두 동일하게 할당)
비례 할당(proportonal allocation) : 프로세스의 크기에 비례하여 프레임을 할당하는 방식
균등 할당은 기초대사량이 많은 사람과 적은 사람에게 모두 동일한 양의 음식을 주는 것과 같다.
비례 할당은 프로세스의 크기가 클지라도 막상 실행해 보면 많은 프레임을 필요로 하지 않는 경우(지역성이 높은 프로그램)도 많다.
위 두 방식은 단순히 프로세스의 크기와 물리 메모리의 크기만 고려한 방식이라는 점에서 정적 할당 방식이라고 한다.
즉, 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 아는 경우가 많다.
동적 할당 방식
프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 크게 아래 두 가지 방법이 있다.
작업 집합 모델(working set model) : '프로세스가 일정 기간 동안 참조한 페이지 집합'을 기억하여 빈번한 페이지 교체를 방지하는 방식
페이지 폴트 빈도(PFF:Page-Fault Frequency) : 페이지 폴트의 빈도수의 상한선과 하한선을 정하여, 상한선이면 프레임을 더 할당하고, 하한선이라면 프레임을 회수하는 방식
작업 집합을 구하는 방법 작업 집합 : 프로세스가 일정 기간 동안 참조한 페이지 집합
페이지 폴트 빈도
-상한선이라면 프레임을 더 할당함 -하한선이라면 프레임을 회수함
작업 집합 모델과 페이지 폴트 빈도는 프로세스의 실행을 보고 할당할 프레임 수를 결정한다는 점에서 동적 할당 방식이라고 한다.
댓글