페이지 교체와 프레임 할당
* 혼자공부하는 컴퓨터 구조와 운영체제 책을 공부하였습니다.
물리적으로 메모리는 크기가 한정되어있다.
페이징을 통해 물리적인 메모리 크기보다 더 큰 프로세스를 실행 할 수 있지만, 결과적으로 한계가 있을수밖에 없다.
두가지 문제를 해결해야한다.
1) 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고
2) 프로세스들에게 적절한 수의 프레임을 할당해야 한다.
요구페이징 (demand paging)
- 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
- 요구되는 페이지만 적재되는 기법이다.
1) 기본양상
- CPU가 특정 페이지에 접근하는 명령어를 실행한다.
- 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
- 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다.
- 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
- 다시 1번을 수행한다.
>>
안정적으로 작동하려면
첫째, 페이지 교체
둘째, 프레임 할당
해결되어야 한다.
순수 요구 페이징 (참고)
- 아무런 페이지도 메모리에 적재하지 않은채 무작정 실행부터 해버리는 방법
- 첫번째 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생한다.
- 실행할 페이지가 어느정도 적재된 이후부터 페이지 폴트 발생 빈도가 떨어지게 될것이다.
페이지 교체 해결방법
페이지 교체 알고리즘
- 요구 페이징 기법으로 페이지들을 적재하다보면 언젠가 메모리가 가득 차게 된다.
- 당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야한다.
이때 어떤 페이지를 내보낼까?
- 이를 결정하는 방법(알고리즘)이 페이지 교체 알고리즘이다.
무엇이 좋은 페이지 교체 알고리즘일까?
- 페이지 폴트가 적은 알고리즘
- 페이지 폴트가 발생하면 보조기억장치에 접근해야하므로 성능이 저하된다.
- 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있다.
1. FIFO 페이지 교체 알고리즘
- 가장 단순한 방식이다.
- 메모리에 가장 먼저 올라온 페이지부터 내쫒는 방식
- 그러나, 프로그램 실행 내내 사용될 페이지가 있을 수 있으므로 문제가 된다.
2. Second Chance 페이지 교체 알고리즘
- 참조 비트 1: CPU가 한 번 참조한 적이 있는 페이지를 참조 비트 0으로 초기화 한 뒤 적재 시간을 현재 시간으로 설정하여 한번 더 기회를 준다.
- 참조비트 0 : CPU가 참조한 적이 없는 페이지는 내쫒는다.
3. 최적 페이지 교체 알고리즘
- CPU에 의해 참조되는 횟수를 고려
- 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지
- 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
- 즉, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다.
(가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘이지만, 실제 구현이 어렵다. 앞으로 오랫동안 사용되지 않을 페이지 예측이 어렵기 때문 / 보통 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주한다.)
4. LRU(Least-Recently-Used) 페이지 교체 알고리즘
LRU는 가장 오래 사용되지 않은 페이지 교체한다. (최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 생각이 기반된다)
5. 기타 페이지 교체 알고리즘
- 이외에도 많은 페이지 교체 알고리즘이 있다.
스레싱과 프레임 할당
페이지 폴트가 자주 발생하는 이유
- 나쁜 페이지 교체 알고리즘
- 프로세스가 사용할 수 있는 프레임 자체가 작아서
스레싱이란
- 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제는 아주 대중적인 문제이다.
- 동시 실행되는 프로세스의 수를 늘린다고 CPU의 이용률이 높아지는 것이 아니다.
>> 멀티 프로그래밍의 정도 : 메모리에 동시에 실행되는 프로세스의 수
스레싱
- 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문에 운영체제는 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적합한 프레임을 할당해주어야 한다.
운영체제의 프레임 할당 방식
1) 균등 할당 (Equal allocation)
- 가장 단순한 할당 방식
- 모든 프로세스들에게 균등하게 프레임을 할당하는 방식
-> 현재 300개의 프레임을 할당 할수 있고 3개의 프로세스가 있다면 각각 100개씩 할당하는것이다.
-> 프로세스마다 크기가 다를텐데 균등하게 할당하는것은 비합리적이다.
2) 비례 할당 (proportional allocation)
- 프로세스의 크게를 고려하는 방식
- 프로세스의 크기에 비례하여 프레임 할당
-> 권장방법은 아님, 크기가 큰 프로세스인데 막상 실행해보니 많은 프레임을 필요로 하지 않을 수 있다.
-> 반대의 경우도 있다. 작은 프로세스이지만 많은 프레임 필요
1)2) 균등과 비례 방식은 정적 할당방식이다. (프로세스의 실행과정을 고려하지 않기때문)
3) 작업 집합 모델
- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- 스레싱이 발생하는 이유는 빈번한 페이지 교체 때문이다. (이는 CPU가 특정시간동안 주로 참조한 페이지 개수만큼만 프레임을 할당해주자)
- 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지한다.
- 프로세스가 참조한 페이지 / 시간 간격이 필요하다.
4) 페이지 폴트 빈도 기반
- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- 페이지 폴트율이 너무 높으면 너무 적은 프레임을 갖고있다고 판단하고
- 페이지 폴트율이 너무 낮으면 너무 많은 프레임을 갖고있다고 판단한다.
즉, 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서 프레임을 할당하는 방식