9장 가상 메모리 관리

1. 메모리 적재(fetch)전략

: 페이지(page)나세그먼트(segment)를 보조기억장치에서 메모리로 이동시키는 시점 결정
1) 요구페이징(demand paging) : 페이징 시스템에서 요구할 때 페이지를 적재하는 것
2) 예측페이징(anticipatory paging) : 프로세스가 조만간 참조할 것 같은 페이지를 예측하여 적재

2. 지역성(locality)

: 프로세스는 현재 실행되는 주소 부근에서 국부적인 부분만을 집중적으로 참조한다는 성질

 

페이지부재(page fault)
•참조하려는 페이지가 메모리에 없는 상황
페이지 부재가 발생하면
•해당 페이지를 보조기억장치에서 메모리로 적재
•페이지 사상표(page map table)의 해당 항목 갱신
빈페이지 프레임이 없으면, 메모리상의 페이지를 보조기억장치로 방출, 공간 확보
•교체대상 페이지가 수정되지 않은 경우
–보조기억장치로 저장 불필요
•변경비트(modified bit, dirty bit) 사용
–페이지사상표의 항목에 포함
–해당 페이지의 변경 여부 표시

 

 

 

3. 페이지 교체 전략 : 어떤 페이지를 메모리에서 내보낼지 결정

Fixed allocation

- 최적의 페이지 교체 전략 : 가장 오랫동안 참조되지 않을 페이지 선택, 휴리스틱 이용, 
- 무작위 페이지 교체 : 무작위로 교체할 페이지 선택
- 선입선출(First-In-First-Out, FIFO)  페이지 교체 : 가장 오랫동안 메모리에 머문 페이지 교체, 비교적 낮은 비용으로 구현 가능, 가장 빈번하게 사용되는 페이지가 교체될 가능성

  -> Belady의 모순 : FIFO  페이지 교체전략 사용 중 페이지 프레임의 개수를 늘리면 페이지 부재의 발생이 감소해야 하나,  오히려 늘어나는 경우가 발생하는 상황 (지역성을 활용하지 않아서)

- 최소최근사용(Least-Recently-Used, LRU) 페이지 교체 : 가장 오랫동안 참조되지 않은 채 메모리를 차지한 페이지 교체, loop 구조에서 문제
- 최소사용빈도(Least-Frequently-Used, LFU)  페이지 교체 : 가장 적게 사용되는 페이지 교체

- 최근미사용(Not-Used-Recently, NUR)  페이지 교체 : 최소최근사용(LRU) 방법을 낮은 비용으로 근사

참조비트(reference bit)와 변경비트(modified bit) 사용

(r,m)이 (0,0)->(0,1)->(1,0)->(1,1) 순으로

- 이차기회(Second Chance) 페이지 교체 : 페이지 별로 참조비트(referenced bit)가 있는 FIFO  전략

참조비트가 1이면 0으로 바꾸고 FIFO 대기열의 맨 뒤로 배치, 0이면 해당 페이지 교체 

참조될 때마다 참조비트 1로 설정
- 클록(Clock) 페이지 교체 : 이차기회(Second chance) 페이지 교체와 유사, FIFO 대기열 대신 환형 리스트(circular list) 사용 

먼재 적재된 page가 교체될 가능성이 높고, 참조비트 사용해 교체 페이지를 결정한다.
- 원거리 페이지(far page) 교체 : 프로세스의 참조 패턴을 나타내는 접근그래프(access graph) 생성하고 접근 그래프에서 참조된 페이지로부터 가장 멀리 떨어진 참조되지 않은 페이지 교체

 

Variable allocation

 

* 쓰레싱 :  페이지부재(page fault)가 계속적으로 발생하여,  프로세스의 처리시간보다 페이지 교체 시간이 더 많아지는 현상

* 작업 집합 : 실행중인 프로세스가 일정시간 동안 참조하는 페이지들의 집합

메모리에 있어야 하는 페이지들의 집합, 지역성(locality) 특성 때문에 작업집합 유지 가능

W(t,w)는 시간윈도우[𝑡−𝑤,𝑡] 동안 프로세스가 참조한 페이지들의 집합

윈도우 크기𝒘가 커짐에 따라 메모리에 유지하는 작업집합도 커지지만,  w가 일정 수준 이상 커지면 작업집합이 증가하지 않음

- 작업집합(working set) 기반 페이지 교체 전략 : 작업집합 간의 전이를 할 때 

- 페이지 부재 빈도(PFF) 페이지 교체

프로세스의 페이지 부재 빈도에 따라 메모리에 유지할 페이지 개수를 조절한다.

페이지 부재가 자주 일어나면, 프로세스에 할당된 페이지 프레임 수를 증가신다. (메모리 할당 증가)

페이지 부재가 발생할 때만 수행(cf 작업집합 - 메모리에 참조할 때마다 관리)

 

 

페이지 크기가 작을 경우

- 페이지 테이블 크기 증가, 내부 단편화 감소, I/O 시간 증가, page fault 증가

페이지 크기가 클 경우

- 페이지 테이블 크기 감소, 내부 단편화 증가, I/O 시간 감소, page fault 감소

 

전역/지역 페이지 교체

페이징에서 프로그램 동작

LINUX의 페이지 교체 전략

---

 

13. 시간 지역성, 공간 지역성

시간 지역성은 최근 참조된 메모리 공간이 가까운 미래에도 계속 참조될 가능성이 높다는 성질이다.

반복 구조, 프로시저, 스택 등이 있다.

공간 지역성은 일단 어떤 메모리가 참조되면, 근처 메모리 공간도 계속 참조되는 경향이 높다는 성질이다.

배열검색, 순차적 코드의 실행, 관련 변수의 인접 선언 등이 있다.

 

14. 이차기회 페이지 교체 알고리즘을 FIFO 교체 알고리즘과 비교하여 설명

15. 클록 페이지 교체 알고리즘과 이차기회 페이지 알고리즘 비교하여 설명

16. 원거리 페이지 교체 알고리즘

 

17. 쓰레싱

 

18. 작업 집합과 지역성의 관계

 

19. 페이지 부재 빈도 페이지 교체 알고리즘

 

20. 리눅스에서 사용된 변형된 클록 페이지 교체 전략

활성 리스트와 비활성 리스트 2개의 연결 리스트를 사용하는데, 페이지 교체는 비활성 리스트에서 일어난다.

 

21. 페이지 크기가 크거나 작을 때의 메모리 관련된 특성

페이지 크기가 작으면, 내부 단편화를 감소시키고 특정한 참조 지역성만을 포함하기 때문에 기억장치 효율은 좋을 수 있다.