요구 페이징(Demand Paging)
처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법이다. 이름 그대로 요구되는 페이지만 적재한다.
순수 요구 페이징(Pure Demand Paging)
아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 할 수도 있다. 이 경우 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하게 되고 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이제 폴트 발생 빈도가 떨어진다. 이를 순수 요구 페이징기법이라고 한다.
요구 페이징 시스템이 안정적으로 작동하려면 해결되어야할 2가지 문제
페이지 교체
요구 페이징 기법으로 페이지들을 적재하다보면 언젠간 메모리가 가득 차게 된다. 당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야 한다. 이때 어떤 페이지를 내보낼까 결정하는 방법(알고리즘이) 페이지 교체 알고리즘이다.
페이지 교체 알고리즘
무엇이 좋은 페이지 교체 알고리즘일까?
페이지 폴트가 적은 알고리즘이다. 왜나하면 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것 보다 느려지기 때문이다. 그러므로 페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능이 저하된다.
페이지 폴트 횟수는 어떻게 알 수 있을까?
페이지 참조열(Page Reference String)
CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열이다.
2 2 2 3 3 3 5 3 3 7
여기서 연속된 페이지를 생략한 페이지열 즉 아래 숫자열이 페이지 참조열이다.
2 3 5 3 7
연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문이다.
01 FIFO 페이지 교체 알고리즘
가장 단순한 방식이다. 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식으로 "오래 머물렀다면 나가라"는 알고리즘이다.
알고리즘의 아이디어와 구현이 단순하지만 막 사용하면 안되는 이유는 프로그램 실행 초기에 잠깐 실행될 페이지에서는 좋겠지만 프로그램 실행 내내 사용될 페이지에서는 사용하면 안되기 때문이다.
02 2차 기회(Second-Chance)페이지 교체 알고리즘(FIFO페이지 교체 알고리즘 보완책)
참조 비트1 : CPU가 한 번 참조한 적이 있는 페이지
참조 비트0 : CPU가 참조한 적이 없는 페이지
참조 비트가 1인 경우 한 번 더 기회를 준다. 참조 비트를 0으로 초기화 한 후 적재 시간을 현재 시간으로 설정한다. 그리고 참조비트가 0이면 내쫓는다.
예시
페이지 2의 참조비트가 1이므로 참조비트를 0으로 변경한 후 최근에 적재된 페이지로 간주한다.
03 최적 페이지 교체 알고리즘
CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘이다. 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지이므로 앞으로의 사용빈도가 가장 낮은 페이지를 교체하는 알고리즘을 페이지 교체 알고리즘으로 삼는 것이 가장 합리적이다.
가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘이다. 하지만 구현이 몹시 복잡다. 앞으로 오랫동안 사용되지 않을 페이지를 예측하는 것이 어렵다. 그러므로 최적 페이지 교체 알고리즘은 그 자체를 운영체제로 사용하기보다는 주로 다른 페이지 교체 알고리즘에 이론상 성능을 평가하기 위한 하한선 사용된다.
04 LRU(Least-Recently-Used)페이지 교체 알고리즘
가장 오래 사용되지 않은 페이지를 바다. 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체한다.
이외에도 페이지 교체 알고리즘의 종류는 다양하다.
스래싱
프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제이다.
멀티프로그래밍의 정도(동시 실행되는 프로세스의 수)를 늘린다고 CPU 이용률이 높아지는 것이 아니다.
스래싱이 발생하는 근본적인 이유
각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다. 그러므로 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다.
스래싱과 프레임 할당
01 균등 할당(Equal Allocation)
가장 단순한 할당 방식이다. 모든 프로세스들에게 균등하게 프레임을 할당한다.
02 비례 할당(Proportional Allocation)
프로세스의 크기에 비례하여 프레임을 할당한다.
※ 균등 할당과 비례 할당 방식은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고려한 방식이라는 점에서 정적 할당 방식이라고도 한다.
비례 할당 또한 오나변학 방식은 아니다. 프로세스의 크기가 클지라도 막상 실행해 보니 많은 프레임을 필요로 하지 않는 경우도 있다. 이와 반대로 프로세스의 크기가 작아도 실행해 보니 많은 프레임을 필요로 하는 경우도 있다. 즉 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 안다.
03 작업 집합 모델(Working Set Model)
프로세스가 실행하는 과정에서 배분할 프레임 결정이다. 스레싱이 발생하는 이유는 빈번한 페이지 교체 때문이다. 그러므로 CPU가 과거에 주로 참조한 페이지를 작업 집합에 포함한다면 운영체제는 작업 집합의 크기만큼만 프레임을 할당해주면 된다. 이렇게 한다면 프로세스가 작업집합(일정 기간 동안 참조한 페이지 집합,Work Set)을 기억하여 빈번한 페이지 교체를 방지할 수 있다.
작업 집합 구하는 방법
1) 프로세스가 참조한 페이지 2) 시간 간격이 필요
그러므로 t1에서는 최소 3개의 프레임이 필요로 한다.
04 페이지 폴트 빈도
프로세스가 실행하는 과정에서 배분할 프레임을 결정한다. 페이지 폴트율에 상한선과 하한선을 정하고 그 내부 범위 안에서만 프레임을 할당하는 방식이다.
참고 : 본 내용은개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제강의를 수강하여 작성하였습니다. https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard
'cs공부 > 운영체제' 카테고리의 다른 글
운영체제 - 스택 메모리, 힙 메모리 자세히 알아보기 +) args란 (0) | 2024.05.15 |
---|---|
운영체제 - 페이징의 쓰기 시 복사(copy on write), 계층적 페이징 (0) | 2024.03.04 |
운영체제 - CPU 스케줄링(우선순위, 스케줄링 큐, 선점 및 비선점형 스케줄링) (0) | 2024.01.21 |
운영체제 - 병렬처리(Parallel Loops, Parallel Invoke,Parallel Partitioning) (0) | 2023.06.06 |
운영체제 - TLS(Thread Local Storage) (0) | 2023.06.06 |
댓글