Demand paging
프로세스가 실제로 페이지를 필요로 할 때 메모리에 올리는 것을 demand paging이라고 한다. 이런 행위의 장점은 다음과 같다.
- I/O 양의감소
- 메모리 사용량 감소
- 빠른 응답시간
- 더 많은 수용자 수용
page fault
페이지 테이블에는 vaild-invalid bit가 존재한다. invalid는 프로세스에서 사용되지 않는 주소 영역인 경우&페이지가 물리적 메모리에 없는 경우(디스크에 스왑된 경우) 세팅된다. 만약 주소 변환시에 엔트리에 invalid bit가 세팅되어있다면, 이것을 page fault라고 부른다.
invalid bit가 세팅된 페이지를 접근하면 먼저 mmu가 trap을 발생시킨다. 그 뒤에 OS가 cpu를 잡고 커널 모드로 전환해서 다음과 같은 순서로 page fault를 처리한다.
- 허용되지 않은 주소로 접근한다. (limit를 넘거나 하는 요청) -> 프로세스를 종료시킨다.
- 그렇지 않다면, 페이지가 디스크에 스왑되어 있는 것으로 우선 빈 페이지 프레임을 하나 획득한다.
- 빈 페이지 프레임이 없다면 다른 프로세스로부터 뺏어온다.
- 해당 페이지를 디스크에서 메모리로 읽어온다.
-> 디스크 I/O가 끝나기까지 이 프로세스는 cpu를 다른 프로세스에게 선점당한다. (block)
-> 디스크 I/O가 끝나면 페이지 테이블의 엔트리의 valid-invalid bit를 valid로 바꿔준다.- 이 프로세스가 cpu를 잡고 다시 running한다.
- 아까 중단되었던 instruction을 재개한다.
3번의 경우처럼 만약 빈 페이지 프레임이 없는 경우, 어떤 프레임을 뺏어올지 결정해야 한다. 곧바로 사용되지 않을 페이지를 쫓아내는 것이 좋지만 동일한 페이지가 여러번 메모리에서 쫓겨났다가 다시 들어오는 문제가 발생할 수 있으므로 주의해야한다.
이에 따라 어떤 프레임을 뺏어올지 결정하기 위한 알고리즘이 필요하다. 이 알고리즘은 page fault rate(page fault의 비율)을 최소화하는 것을 목적으로 한다.
여러 알고리즘
Optimal algorithm
앞으로 가장 오랫동안 참조되지 않을 페이지를 replace한다. 하지만 어떤 페이지가 미래에 참조될지 알 수 없으므로 (미래를 알 수 없다) 실제 시스템에선 사용이 불가능하다.
하지만 제일 이상적인 상황으로써, 다른 알고리즘과 성능을 비교할 때 사용한다.
FIFO(First-in First-out)
FIFO는 먼저 들어온 페이지를 먼저 내쫓는 알고리즘이다. 즉 선입선출의 알고리즘이다.
위 그림처럼, 메모리가 꽉차자 맨 먼저 들어온 1을 내쫓는 것을 볼 수 있다.
FIFO의 단점은 프레임 갯수를 늘렸는데 page fault가 오히려 더 늘어날 수 있다는 것이다. 즉 프레임을 늘린다고 page fault가 적어지는 것을 보장할 수 없다.
LRU
LRU는 가장 오래 전에 참조된 페이지를 지우는 알고리즘이다.
LFU
LFU는 참조 횟수가 가장 적은 페이지를 지운다. 만약 최저 참조횟수인 페이지가 여러 개 있는 경우 여러 페이지중 임의로 선정해서 내쫓는다.
LFU는 LRU처럼 직전 참조시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 페이지의 인기도를 좀 더 정확히 반영할 수 있다. 하지만 참조 시점의 최근성을 반영하지 못할 수 도 있다. 무슨 말이냐면 막 들어온 페이지가 참조 횟수가 0이기 때문에 다시 내쫓길 가능성이 있다는 뜻이다.
LRU, LFU 구현
LRU는 큐를 사용하면 된다. 이미 존재하는 페이지는 참조될 때마다 head로 보내고, 새로운 페이지가 들어오면 tail의 페이지를 삭제하고 head에 페이지를 넣는다.
LFU는 참조 횟수의 오름차순으로 페이지를 리스트에 넣은 다음에, page fault가 발생하면 head에 있는 페이지를 삭제한다. 그리고 만약 존재하는 페이지가 참조되면 그 페이지의 참조 횟수를 1 늘리고, 올바른 위치에 다시 정렬시킨다.
다만 이렇게 비교해야하기 때문에 O(n)이라는 시간이 걸린다. 따라서 힙을 이용한 알고리즘을 사용하기도 한다. 이렇게 구현하면 O(log n)의 시간이 걸린다.
캐싱 시스템
캐싱 기법은 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식이다. 페이징 시스템뿐만 아니라 다른 여러 시스템에서도 사용하고 있다.
다만 캐시가 다 찼을 때 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다.
버퍼 캐시 시스템이나 웹 캐시 시스템의 경우 O(1) ~ O(log n)까지 허용하고 있지만, 페이징 시스템인 경우에는 이러한 교체 알고리즘 자체가 불가능하다.
왜냐하면, 교체 알고리즘을 사용하려면 이것을 관리하는 OS가 참조 시각, 참조 횟수와 같은 정보를 알고 있어야 하는데, 만약 이미 메인 메모리에 페이지가 존재하는 경우에는 page fault가 발생하지 않아 OS에게 cpu가 넘어오지 않기 때문에 그 상황에서는 위와 같은 정보를 OS가 알고 있는 것이 불가능하다. 따라서 오직 page fault가 발생했을 때만 OS가 cpu를 잡기 때문에 page fault가 발생하지 않으면 자료구조에 대한 조작이 불가능해진다.
Clock 알고리즘
이에 대한 대안으로 LRU의 근사 알고리즘인 clock 알고리즘이 존재한다.
clock 알고리즘엔 reference bit와 modified bit가 존재한다. 만약 페이지가 참조되면 하드웨어가 reference bit를 1로 바꾼다. 이것은 최근에 참조됐다는 것을 의미한다. 만약 page fault가 발생하면 한 바퀴 돌면서 reference bit가 0인 것을 찾아서 그 페이지를 교체한다. 근데 이 때 만약 reference bit가 1이라면 0으로 바꾸고 그 다음 페이지의 reference bit를 확인한다.
modified bit는 만약 페이지에 write가 발생하면 1로 바뀐다. 이 bit가 0이라면 변경된 것이 없으므로 reference bit가 0일 때 메모리에서 내쫓기만하지만, 1이라면 메모리에 올라온 이후로 내용이 변경된 것으로 디스크에 수정된 내용을 반영해야한다. 따라서 메모리에서 내쫓기전에 디스크에 해당 페이지를 새로 저장하고 내쫓는다.
페이지 프레임의 할당 문제
각 프로세스에 얼마만큼의 페이지 프레임을 할당할 것인가에 대한 문제다. 보통 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시 참조하기 때문에 명령어 수행을 위해 최소한 할당되어야 하는 프레임의 수가 존재한다.
예를 들어 루프를 구성하는 페이지들은(반복문) 한꺼번에 할당되는 것이 유리하다. 또한 루프에 필요한 최소한의 할당이 없으면 매 루프마다 page fault가 발생할 것이다.
프레임을 할당하는 방법에는 세 가지가 존재한다.
equal allocation: 모든 프로세스에 똑같은 갯수 할당
proportional allocation: 프로세스 크기에 비례하여 할당
priority allocation: 프로세스의 우선순위에 따라 할당
Global replacement
메모리 상의 모든 페이지에 대해 교체 작업을 수행하는 방법이다. FIFO, LRU, LFU처럼 메모리상에 올라와있는 페이지들을 전부 확인하고 교체 작업을 수행하는 것이 바로 그 예제다. working set, PFF 알고리즘을 사용하기도 한다.
Local replacement
메모리 상의 자기 자신의 프로세스 페이지에 대해서만 교체 작업을 수행한다. FIFO, LRU, LFU 등의 알고리즘을 프로세스별로 운영하면 된다.
Thrashing
thrashing은 프로세스의 원활한 수행에 필요한 최소한의 페이지 프레임 수를 할당 받지 못한 경우 발생한다.
cpu가 여러 개의 프로세스를 실행시키고 있다고 해보자. 그렇다면 메인 메모리에 여러 프로그램이 동시에 올라와 있을 것이다. 이 상황에서 프로세스를 더 추가할수록 메모리에는 더 많은 프로그램이 올라가고, cpu의 이용률은 늘어날 것이다.
근데 어느 시점에 다다르면, cpu의 이용률이 급격하게 낮아진다. 왜냐하면 프로세스를 많이 실행할수록 메인 메모리의 비어있는 프레임 갯수는 줄어들게 되고, 결국엔 꽉차게 되는데 그 시점부터는 page fault가 자주 발생하게 된다. page fault의 작업은 disk I/O작업으로 cpu를 사용하지 않는다. 따라서 cpu의 이용률이 떨어지게 된다.
이에 동시에 메모리에 올라가있는 프로세스의 갯수에 대한 조절이 필요하다.
Working-set model
프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조하는 특징이 있다. 이런 집중적으로 참조되는 해당 페이지들의 집합을 locality set이라고 한다. 하지만 locality는 치명적인 단점이 있는데 프로세스를 실행시켜봐야 알 수 있다는 점이다.
따라서 이를 해결하기 위해 working-set model이 나왔다. 이 방법에서는 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와있어야 하는 페이지들의 집합을 working set이라고 정의한다.
또 프로세스의 working set 전체가 메모리에 올라와있어야 수행되고 그렇지 않은 경우에는 모든 프레임을 반납후 swap out(suspend)된다.
working set은 working set window를 통해 알아낼 수 있다. window는 일정한 델타의 길이로 페이지를 관찰한다. 그리고 어떤 시간 t에 대해 해당하는 working set을 알아낸 뒤 그에 대한 갯수만큼 프레임을 할당한다.
만약 프로세스들의 working set 크기의 합이 페이지 프레임보다 큰 경우에는 일부 프로세스를 swap out시켜 남은 프로세스의 working set을 우선적으로 충족시켜준다.
그리고 working set을 다 할당하고도 페이지 프레임이 남는 경우에 swap out된 프로세스에게 working set을 할당시켜준다.
PFF(page-fault frequency)
page fault 비율의 상한값과 하한값을 두는 방법이다. 만약 상한값을 넘으면 프레임을 더 할당시키고 하한값 이하라면 할당 프레임 수를 줄인다. 빈 프레임이 없으면 일부 프로세스를 swap out한다.
페이지 사이즈의 결정
페이지 사이즈를 감소시키면
- 페이지 수 증가
- 페이지 테이블 크기 증가
- 내부 단편화 감소
- 디스크 탐색의 효율성 감소 -> 탐색할 때 한 번에 많이 가져올 수록 좋다.
- 장기적으로 page fault의 비율 감소
필요한 정보만 메모리에 올라와 메모리 이용이 효율적이기도 하다.
반대로 페이지 사이즈를 증가시키면
- 페이지 수 감소
- 페이지 테이블 크기 감소
- 내부 단편화 증가
- 디스크 탐색의 효율성 증가
- 장기적으로 page fault의 비율 증가
와 같은 측면이 존재한다. 트렌드는 페이지 사이즈를 증가시키는 데에 있다.
반효경 교수님의 운영체제 강의를 바탕으로 작성했습니다
