목표
가상메모리 관리 기법의 기초와 교체 알고리즘, 다양한 캐슁 환경에 대해 알아본다.
물리적 메모리의 주소 변환은 운영체제가 관여하지 않는다. 가상 메모리 기법은 전적으로 운영체제가 관여를 하고 있다.
demand paging
- 요청이 있으면 그 페이지를 메모리에 올리겠다
- 페이징 기법을 사용한다고 가정
- 실제로 대부분 시스템은 페이징 기법을 사용함
페이징 기법은 프로그램을 사용할 때 그 프로세스를 구성하는 주소 공간의 페이지를 올릴 때 다 올리는게 아니라, 요청을 받을 때 페이지를 올리는 것 !
page fault인 상황이다.
그런데 page fault가 났을 때 디스크로 접근하는 것은 대단히 오래 걸리는 작업이다. page fault가 얼마나 나느냐에 따라 메모리 접근 시간이 크게 좌우된다.
메모리부터 직접 주소 변환을 할 수 있고, 그렇지 않은 경우에 page fualt 가 나서 디스크 접근을 필요로 한다
대부분의 경우엔 page fault가 안나지만 한번 나게 되면 엄청난 시간을 겪어야 한다.
메모리 접근하는 시간은 페이지 폴트까지 감안해서
빈페이지가 없는 경우 쫓아내야 한다고 했다.
: page replacement
어떤 메모리를 쫓아내고 그자리에 새로운 페이지를 올려놓을 것인가를 결정하는 일이다.
1)page fault 를 0에 가깝도록! => 메모리에서 직접 참조되는게 좋아
디스크에서 메모리로 올라온 이후에, 내용이 변경됐다면?즉 , write가 생겼다면> 쫓아낼 때 변경된 메모리에서 backing store에 써줘야 한다.
어떤 알고리즘이 제일 좋은 알고리즘인가?
optimal algorithm
페이지 폴트를 가장 적게 하는 알고리즘
실제 시스템에서는 미래를 알 수 없다. 이걸 쫓아내야할지 말아야 할지 결정하기 어려워.
이 알고리즘은 미래를 안다고 가정.
FIFO algorithm
[리더를 버리는 알고리즘]
미래를 모를 때 사용하는 알고리즘
그러니, 과거를 봐보자 ~
특이점: 메모리 크기를 늘리면 성능이 더 나빠지는 경우가 생길 수 있다. => fifo anomaly다 ~
LRU algorithm
[현재 찐따를 버리는 알고리즘]
LFU algorithm
[최종 찐따를 버리는 알고리즘]
LRU와 LFU 알고리즘 예제
LRU: 어떻게 구현? => 메모리 안에 있는 페이지를 참조 시간에 따라서 한줄로 줄을 세운다.
LRU와 LFU 알고리즘 구현
따라서 LFU 알고리즘은 리스트 형태로 X 힙이라는 구조로 구현을 하게 된다.
시간 복잡도
n과 log n은 굉장히 다르다.
n이 100만개라 할 때 log n은 10에서 20사이의 숫자로 나온다.
