CS 공부
주기억 장치 관리 전략(페이지 반입, 배치, 교체 전략) 본문
반입(Fetch) 전략
반입(Fetch) 전략이란
프로그램/데이터를 주기억 장치로 가져오는 시기를 결정하는 전략
반입(Fetch) 전략 종류
요구 반입: 새로 반입된 데이터나 프로그램을 주기억 장치에 언제 위치시킬 것인가 결정하는 방법
예상 반입: 앞으로 요구될 가능성이 큰 데이터 또는 프로그램을 예상하여 주기억 장치로 미리 옮기는 방법
배치(Placement) 전략
배치(Placement) 전략이란
프로그램/ 데이터를 주기억 장치 내의 어디로 위치 시킬 것인가를 결정하는 전략
배치(Placement) 전략 종류
최초적합
- 입력된 작업을 주기억 장치 내에서 그 작업을 수용할 수 있는 첫 번째 공백에 배치한다.
초기 결정력이 가장 빠르다
운영체제 다음부터가 시작점이다.
처음부터 순차적으로 검색하여 적재될 수 있는 공백이면 배치한다.
최적적합
- 입력된 작업을 주기억장치 내의 공백중에서 그 작업에 가장 잘 맞는 공백에 배치한다.
- 내부 단편화가 가장 작거나 없는 공백에 배치
- 가장 잘맞는 공백을 찾아야하므로 결정력이 느리다.
- 최적적합은 힙으로 구현할때 최대 성능
최악적합
- 입력된 작업을 주기억장치 내에서 가장 잘 맞지않는 공백 즉 가장 큰 공백에 배치한다.
- 내부 단편화가 가장 큰 공백에 배치
- 가장 잘 맞지 않는 공백을 찾아야하므로 결정력이 느림
페이지 교체 알고리즘
페이지 교체 알고리즘이란
페이지 교체 전략이란 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지 할당을 위해 어떤 페이지 프레임을 선택하여 교체할지 결정하는 기법이다.
요구 페이징 시스템은 프로세스가 특정 페이지를 요구할 때 해당 페이지를 메인 메모리에서 로딩한다.
메인 메모리에 필요한 페이지가 있을 때는 잘 진행되지만, 없을 경우에는 문제가 생긴다.(페이지 부재 발생) 프로세스가 필요로 하는 페이지가 없는 경우(page-fault) 보조 기억 장치에서 페이지를 찾아 빈 프레임에 로딩하는데, 여기서 또다시 ‘페이지를 올릴 빈 프레임이 없을 경우’ 란 문제에 직면할 수 있다.
이 때 사용하는 것이 새로 올릴 페이지와 교체할 희생 프레임을 찾는 알고리즘, 페이지 교체 알고리즘이다.
페이지 부재(Page Fault, PF)란 메모리에 적재된 페이지 중 사용해야 하는 페이지가 없을 때를 의미한다.
페이지 적중률이 높도록 교체 전략을 선택해야한다.
교체 알고리즘 종류
FIFO(first in first out)
- 가장 간단한 알고리즘으로, 메모리에 올라온 지 가장 오래된 페이지를 교체한다.
- 이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나, 페이지가 올라온 순서를 큐(Queue)에 저장하는 방식 등을 사용할 수 있다.
- 이해 설계가 쉽다.
- 벨레이디의 모순 현상이 발생할 수 있다
벨레이디의 모순현상이란: 페이지 수를 증가했는데 페이지 부재가 증가하는 경우
메모리에 올라온 지 가장 오래된 페이지가 가장 자주 사용되는 페이지라면 페이지 부재가 증가한다.
즉 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질 위험이 있다는 말이다.
최적 페이지 교체(Optimal)
- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법.
선행 전제 조건: 프로세스가 앞으로 사용할 페이지를 미리 알아야한다는 것
- 앞으로 나올 페이지들의 호출 순서와 참조 상황을 예측해야 하므로 실현 가능성이 희박하다.
- 최적 교체 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 알고 교체하기 때문에 모든 페이지 교체 알고리즘을 통틀어 가장 페이지 교체 수가 적다.
LRU(least-recently-used)
- 가장 오래 사용되지 않은 페이지를 교체하는 알고리즘
- 최적 알고리즘은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘이다.
- 계수기(시간 영역)를 두어 가장 오랫동안 사용하지 않은 페이지를 교체할 페이지로 선택함
- 최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있다. 미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 교체하는 것은 가능하다. 예측 방법으로 가장 오랜 기간 사용되지 않은(least recently used) 페이지를 교체하는 방식을 사용하는 것이다.
- LRU 알고리즘은 많은 운영체제가 채택하는 알고리즘이며, 좋은 알고리즘이라고 평가 받고 있다.
구현 방법
- Counter implementation
- 페이지가 참조되면, 카운터나 클럭을 카피한다. 가장 작은 값을 갖고 있는 페이지를 죽인다→LFU?
- Stack implementation
- 완전히 스택처럼 움직이지는 않지만 참조되면 위로 올림(?)
- 제일 아래에 있는 애를 죽인다.
- Double linked list를 통해 구현
- 헤드에 가까운 데이터일 수록 최근에 사용한 데이터고, tail에 가까울 수록 가장 오랫동안 사용하지 않은 데이터로 간주한다.
- 삽입된 데이터를 사용하게 되면 head로 옮겨 우선순위를 높인다.
NUR(Not Used Recently)
- 최근에 호출하지도 사용하지도 않은 페이지를 제거
- 두 개의 하드웨어 비트인 참조비트와 변형비트를 이용
- 참조비트가 0이면 오래전에 호출 1이면 최근호출
- 변형비트가 0이면 오래전에 사용 1이면 최근사용
Second Chance
- 가장 오래된 페이지가 최근에 사용할 가능성이 클 것이라는 가정하에 가장 오래된 페이지는 교체대상에서 제외하고 사용한 것으로 취급
- 각 페이지 프레임을 FIFO순으로 유지하면서 LRU와 근사알고리즘처럼 참조 변수를 갖게한다.
- FIFO의 2차 기회 부여방법
PFF
- 워킹 셋에 존재하지 않는 페이지들을 관찰하여 최근에 자주 사용되고 있지 않은 페이지와 워킹 셋에 속하지 않은 페이지 중에 최근에 자주 사용하는 페이지와 교체
계수-기반(Counting-Based) 페이지 교체
페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅하는 방법이다. 이 방법을 이용해 LFU와 MFU 두 가지의 알고리즘을 만들 수 있다.
사실 LFU와 MFU는 실제 사용에 잘 쓰이지 않는다.
구현에 상당한 비용이 들고,
최적 페이지 교체 정책을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문이다.
LFU(least-frequently-used)
- 사용(참조) 횟수가 가장 작은 페이지를 교체하는 알고리즘
- 사용한 횟수를 기억할 참조변수를 페이지마다 갖게하여 사용할 때 마다 1씩 증가한다.
- 만약 교체 대상인 페이지가 여러 개 일 경우, LRU 알고 리즘을 따라 가장 오래 사용되지 않은 페이지로 교체한다.
- LFU 알고리즘은 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있다. 앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문이다.
MFU(most-frequently-used)
- 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
- 참조 횟수가 적은 페이지가 최 근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단이다.
참고
