## 목차 ##
## 1. 요구 페이징 ##
- 요구 페이징(demand paging)
- 프로세스가 요청할 때 해당 페이지를 메모리로 가져오는 가져오기(fetch) 정책
(1) 요구 페이징 개요
프로세스의 일부만 메모리에 올리는 이유
- 메모리의 효율적 관리
- 응답 속도 향상
게으른 스와퍼(lazy swapper)
- 사용자가 요청한 페이지만 메모리로 가져오는 것
- 페이저(pager)라고도 한다.
(2) 페이지 테이블 엔트리의 자료구조
reserved
- 직접 매핑일 경우는 페이지 번호가 곧 인덱스이므로 페이지 번호가 필요없다.
- 연관 매핑의 경우 페이지 번호가 필요하다.
access bit(접근 비트)
- 페이지가 메모리로 스왑 인(swap in) 된 후 사용된 적이 있는지 나타내는 비트
- 참조 비트(reference bit)라고도 한다.
modified bit(변경 비트)
- 페이지가 메모리로 스왑 인(swap in) 된 후 데이터 변경이 있었는지 나타내는 비트
- 오염되었단 의미에서 dirty bit라고도 한다.
valid bit(유효 비트)
- 해당 페이지가 메모리에 있는지를 나타낸다.
- present bit라고도 한다.
protection bits(보호 비트들)
- read(읽기), write(쓰기), 실행(execute) 비트들로 권한을 나타내는 비트들이다.
caching bit(캐싱 비트)
- 캐싱을 허용할지 말지 설정하는 비트
frame number(프레임 번호)
- 유효 비트가 0이면 페이지가 메모리에 존재하므로 프레임 번호 저장
- 유효 비트가 1이면 스왑 영역에 있는 페이지의 주소 저장
(3) 페이지 부재
페이지가 스왑 영역에 있는 경우(유효 비트값 1)를 페이지 부재(page fault)라고 한다.
메모리에 여유공간이 있는 경우 페이지 부재 발생
- 해당 페이지를 메모리의 빈 프레임으로 스왑 인(swap in)
- 페이지 테이블 업데이트(유효 비트 0으로, 스왑 주소를 프레임 번호로)
메모리에 여유공간이 없는 경우 페이지 부재 발생
- 교체 알고리즘에 의해 선정된 대상 페이지(victim page)를 스왑 아웃(swap out)
- 해당 페이지 테이블 업데이트(유효 비트 1로, 프레임 번호를 스왑 주소로)
- 요구 페이지 스왑 인(swap in)
- 해당 페이지 테이블 업데이트(유효 비트 0으로, 스왑 주소를 프레임 번호로)
(4) 지역성
데이터 지역성(locality)
- 메모리 접근 패턴은 일반적으로 전체에 골고루 퍼지지 않고 특정 영역에 집중된다.
- 공간적 지역성, 시간적 지역성, 순차적 지역성
- 페이지 부재 시에 지역성에 따라 앞으로 사용될 확률이 가장 낮다고 판단되는 페이지를 대상 페이지로 선정하기 위해 지역성을 사용
공간적 지역성
- 현재 접근한 데이터와 가까운 데이터일수록 미래에 접근할 확률이 높다.
시간적 지역성
- 최근에 접근한 데이터일수록 앞으로도 사용될 확률이 높다.
순차적 지역성
- 프로그램 코드가 순차적으로 실행되는 경향
- 공간적 지역성의 특별한 경우
## 2. 페이지 교체 알고리즘 ##
(1) 무작위 페이지 교체 알고리즘
무작위로 대상 페이지 선정
지역성을 고려하지 않기에 성능이 좋지 않다. 거의 사용되지 않는다.
(2) FIFO 페이지 교체 알고리즘
가장 먼저 메모리에 들어온 페이지를 대상 페이지로 선정
큐를 사용해서 구현
시간의 지역성만 고려하여 성능이 좋지 않다.
(3) 최적 페이지 교체 알고리즘
미래의 메모리 접근 패턴에서 가장 나중에 사용될 페이지를 대상 페이지로 선정
미래의 메모리 접근 패턴을 알 수 없어 이론만 존재하고 구현이 불가능
유사한 성능을 보이는 최적 근접 알고리즘(LRU, LFU 등)을 사용
- 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하는 방식
(4) LRU 페이지 교체 알고리즘
Least Recentry Used(최근 최소 사용)
메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 대상 페이지로 선정
페이지 테이블에 접근한 시간, 카운터, 혹은 참조 비트를 사용하여 최근 사용 페이지 기록
접근 기록을 위한 추가 메모리 공간 필요
일반적으로 성능이 FIFO보다 우수하고 최적 알고리즘보다 조금 떨어진다.
(5) LFU 페이지 교체 알고리즘
Least Frequently Used(최소 빈도 사용)
메모리에 올라온 후 사용된 횟수가 가장 적은 페이지를 대상 페이지로 선정
사용 횟수 기록을 위한 추가 메모리 공간 필요
일반적으로 LRU 교체 알고리즘과 성능이 비슷하다.
(6) NUR 페이지 교체 알고리즘
Not Used Recently(최근 미사용)
LRU와 LFU와 성능이 비슷하면서 공간 낭비 문제를 완화한 알고리즘
- 기록을 위해 페이지 테이블 엔트리의 접근(참조) 비트와 변경 비트 2개만 사용
(접근비트, 변경비트)의 초기값은 (0,0)
- 읽기, 실행이 발생하면 접근 비트는 1로 SET
- 쓰기, 추가 같은 변경이 일어나면 변경 비트가 1로 SET
- (0,0), (0,1), (1,0), (1,1) 우선순위로 대상 페이지로 선정
가장 많이 사용된다.
## 3. 스레싱과 프레임 할당 ##
(1) 스레싱의 발생
- 스레싱(thrashing)
- 잦은 페이지 부재 발생으로 실제 CPU 사용시간보다 스와핑 시간이 커지는 현상
- 멀티 프로그래밍 정도가 일정 수준에 도달하면 스레싱이 발생한다.
- 동시에 실행되는 여러 프로세스 각각에 프레임을 적절히 할당해야 스레싱 발생을 막을 수 있다.
(2) 정적 할당
프로세스 실행 초기에 프레임을 나누어준 후 그 크기를 고정
- 균등 할당, 비례 할당
균등 할당
- 프로세스 크기에 관계없이 모든 프로세스에 프레임을 동일하게 할당
- 큰 프로세스의 경우 빈번한 페이지 부재 발생, 작은 프로세스의 경우에는 메모리 낭비
비례 할당
- 프로세스 크기에 비례하여 프레임을 할당
- 정적 할당이므로 프로세스 실행 중 필요한 프레임을 유동적으로 반영하지 못한다.
- 필요없는 프레임을 미리 할당해놓아 메모리 낭비(요구 페이징의 경우 큰 프로세스라도 전체가 메모리에 올라오지 않는다.)
(3) 동적 할당
프로세스 실행 중 계속해서 변하는 요청을 수용하는 방식
- 작업집합 모델, 페이지 부재 빈도 모델
작업집합(working set model) 모델
- 지역성 이론을 바탕으로 한다.
- 최근 액세스된 프레임은 이후에 또 액세스될 것이라 가정
- 최근 일정 시간 동안 액세스된 프레임을 집합으로 만들고 이 집합을 물리 메모리에 유지
- 작업 집합 윈도우 : 현재 시점에서 실행했던 페이지들을 살펴보는 폭(width)
- 작업 집합 크기 : 작업 집합 모델에 유지할 페이지의 최대 수
- 작업 집합 윈도우의 크기가 성능을 좌우하므로 적절한 크기로 잡아야한다.
- 프로세스에 프레임을 얼마나 할당해야 할지는 알 수 없어 스레싱은 해결하지 못한다.
- 페이지 부재 빈도(page fault frequency) 모델
- 페이지 부재가 상한 임계치 이상 발생 -> 더 많은 프레임 필요하다고 판단 -> 프레임 추가 할당
- 페이지 부재 적게 발생 -> 프레임이 남아돈다고 판단 -> 할당된 프레임 회수
## 4. 프레임 관련 이슈 ##
(1) 전역교체와 지역교체
전역 교체
- 모든 프로세스의 전체 프레임을 대상으로 교체 알고리즘 적용
- 다른 프로세스의 페이지를 스왑아웃 시켜 스레싱에 빠뜨릴 수도 있다.
- 전체 시스템 관점에서는 전역 교체가 효율적
지역 교체
- 자신의 프로세스 프레임만 대상으로 교체 알고리즘 적용
- 다른 프로세스에 영향을 미치지 않는다.
- 자주 사용되는 페이지가 스왑 아웃되어 자신의 스레싱 발생 확률이 올라간다.