: 요청이 있으면 그 page를 메모리에 올리겠다는 뜻.
paging 기법은 프로그램이 실행될 때 그 프로세스를 구성하는 주소공간을 전부 한꺼번에 메모리에 올리는게 아니라 demand paging
기법을 사용한다.
paging 기법에서 각각의 page table entry마다 valid/invalid bit이 있음.
하나의 프로그램을 구성하는 논리적인 메모리.
page table을 통해서 page에 대한 주소변환 정보가 담겨있음.
물리적인 메모리가 주어져있음.
disk, backing store, 즉 swap area
라고 하는 부분이 있음.
그래서, 프로그램을 구성하는 이 page들 중에서 당장 필요한 부분은 demand paging
에 의해서 물리적 메모리에 올라가 있을 것. 그렇지 않은 부분은 Swap Area
에 내려가 있게 된다.
물리적 메모리에 올라간다면 page table의 valid로 표시. 주소 변환 정보가 의미있는 값이 들어가 있음. 반면에, 나머지 page들은 물리적 메모리에 안올라가 있고, backing store에 내려가 있기 때문에 invalid로 표시되어 있다.
사용되지 않는 주소 영역도 invalid라고 표시됨.
page fault
: 해당 페이지를 물리적 메모리에 접근하려고 page table에서 주소를 보려고 하는데 invalid 값이 set되어 있다면, page fault가 난다.
1. 메모리 reference가 있었는데, 주소 변환을 하려고 봤더니, invalid로 표시. 이 page가 메모리에 올라와있지 않다는 뜻.
2. trap이 걸려서 cpu가 운영체제한테 자동으로 넘어간다.
3. 운영체제는 backig store에 있는 page를,
4. 물리적인 메모리에 올려놓는다. 만약에 빈 page frame이 없으면 무언갈 쫓아내고 넣음.
5. 해당하는 frame 번호를 entry에다가 적어놓고 valid로 바꾼다.
6. 나중에 cpu를 다시 얻어서 주소 변환을 하게되면 valid로 되어있고, 주소변환을 정상적으로 해서 해당하는 물리적인 메모리의 page frame에 접근할 수 있게 된다.
그런데 page fault가 났을때 디스크에 접근하는 것은 대단히 오래 걸리는 작업이다.
page fault가 얼마나 나느냐에 따라서 메모리 접근 시간이 크게 좌우된다.
page fault의 비율을 0에서 1사이의 값임
실제 page fault가 얼마나 나는지 계산했을 때 거의 이 범위 내에서 난다.
거의 안난다는 뜻. page default가 나지 않고, 직접 메모리부터 직접 주소 변환 할 수 잇음.
메모리 접근 시간을 page fault까지 감안해서 계산해보자.
Page replacement
빈 page frame이 없을 때 어떤 frame을 빼앗는 것
앞으로 이 replacement 알고리즘에 대해 알아보자 ~~
reference string
: 페이지들에 서로 다른 번호를 붙여놓고, 시간 순서에 따라서 참조된 순서를 나열한 것.
어떤 것을 쫓아낼지 결정하고,
디스크로 쫓아낸 후,
만약 디스크로 쫓아내기 전, 내용이 변경됐다면 (write), 변경된 내용을 backing store에 써줘야 한다. 변경된 내용이 없다면 그냥 지워버리면 됨.
쫓겨난 page의 entry에는 bit를 invalid로 바꿔준다.
메모리에 올라온 page의 frame 번호를 entry에 적어주고, bit를 valid로 바꿔준다.
최적의 알고리즘임.
: page fault를 가장 적게함.
FIFO Anomaly
: 그런데 이 알고리즘은 메모리를 늘리면 성능이 좋아져야 하는데, 즉, page fault가 적어져야 하는데 되려 늘어날 수 있음.
: 가장 덜 빈번하게 사용된 page 쫓아내자.
LRU와 LFU를 비교해보자.
LRU 알고리즘은 참조 시간에 따라서 한줄로 줄세우기 함.
LFU 알고리즘은 적은 한줄로 줄세우기 함.
그래서 이런 자료구조를 쓰지 않고, heap이라는 자료구조를 이용해서 구현함.
자식이 두개씩 있는 이진트리
맨위에는 참조횟수가 제일 적은 page
밑으로 갈수록 참조횟수가 많은 page임.
자식 둘과만 비교해서 만약 내가 참조횟수가 많으면 자리를 변경한다.
전체가 n개라고 라면, 높이가 log 2의 N이 된다.
n이 100만이라고 하면,
log 2의 100만이라고 하면, 값이 10~20 숫자