Chapter 9-3. Virtual Memory III
Clock Algorithm
LRU와 비슷한 알고리즘으로, Second chance algorithm, NUR, NRU라고도 불린다.
Circular Linked list 구조를 취하고 있다.
이 알고리즘에서는 Reference bit이라는 것이 사용된다.
하드웨어에 의해 조작되며 운영체제는 Reference bit을 참고해서 쫓아낼 페이지를 결정하게 된다.
Reference bit이 1이면, 최근에 사용된 페이지이고 0이면 최근에 사용된 것이 아니기 때문에 page fault를 발생한다.
이름 그대로 시계모양을 하고 있으며,
시계 방향으로 움직이면서, reference bit이 1이면 0으로 바꾸고, 한바퀴를 돌고 돌아와서 0인 것을 쫓아낸다.
한 바퀴를 돌고 있을 동안에 사용되지 않았다, 즉 reference bit값이 다시 1로 되지 않았다는 것은
최근에 사용되지 않았다는 뜻이므로 내쫓으면 되는 것이다.
개선
Modified bit(dirty bit)
메모리 페이지가 read로 참조될 수도 있지만 write로 참조가 될 수도 있다.
그래서 modified bit은 해당 페이지가 write 흔적이 있는지 없는지를 알려준다.
0은 write작업이 없음을 뜻하고 1은 write작업이 있음을 뜻한다.
1일 경우에는 메모리에 올라온 이후로 적어도 한 번의 write 과정이 있었으므로,
바로 내쫓지 못하고 변경된 사항에 대해서 디스크에 저장을 한 뒤에 내쫓아야 하는 것이다.
이는 상당히 번거로운 작업이다.
그래서 reference bit 값이 0인데, modified bit값이 0인 것과 1인 것 두 가지가 존재할 경우엔 0을 내쫓는다.
Page Frame의 Allocation
Allocation에도 알고리즘이 필요하다.
프로그램마다 할당받아야 하는 페이지의 개수가 존재하기 때문이다.
또 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지가 동시에 참조하는 페이지도 존재하기 때문에 복잡해진다.
Allocation Problem : 각 process에 얼마만큼의 page frame을 할당할 것인가?
Allocation Scheme
Equal allocation : 모든 프로세스에 똑같은 개수 할당
Proportional allocation : 프로세스 크기에 비례하여 할당
Priority allocation : 프로세스의 우선순위에 따라 할당
Replacement
Global replacement
replace시 다른 process에 할당된 frame 을 빼앗아 올 수 있다.
그 때 그 때 메모리 할당량이 알고리즘에 의해 조절이 된다.
Local replacement
자신에게 할당된 frame내에서만 replacement 가 이루어진다.
FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영한다.
Thrashing
프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우에 발생하는 현상을 말한다.
전체적으로 Page fault rate가 높아지게 되며 CPU Utilization 이 낮아진다.
OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단하여 또 다른 프로세스를 추가하게 된다.
결국 프로세스당 할당된 frame 수는 더욱 감소하게 된다.
대부분의 프로세스들이 page 의 swap in/out으로 많은 시간을 소비하게 되고
이에 비해 CPU는 한가해지게 된다.
결과적으로 Low Throughput을 산출하게 된다.
Thrashing을 방지하기 위해 Working-Set Model, PPF 두 가지 방법이 사용된다.
Working - Set Model
프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조한다.(Locality Reference) ex) loop
이 특성을 이용한 model로 집중적으로 참조되는 해당 page들의 집합을 locality set이라 정의한다,
그락ㅎ Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해
한꺼번에 메모리에 올라와있어야 하는 page들의 집합을 Working Set이라 정의한다.
Process의 Working Set전체가 메모리에 올라와있어야 수행이 되고 그렇지 않을 경우 page를 더 요구하지 않고
모든 page frame을 반납 후 swap out(suspend state)된다.
즉, 이미 메모리에 올라가 있는 프로세스에게 page frame을 양보함으로써 Thrashing을 방지하는 것이다.
Working Set은 Working set window라는 것을 이용하여 과거를 통해 추정한다.
PPF(Page-fault Frequency)
각 프로세스마다 page fault rate의 상한값과 하한값을 설정해 둔다.
Page fault rate의 값이 상한 값을 넘으면 해당 프로세스에게 frame을 더 할당해주고,
빈 frame이 없는 경우에는 일부 프로세스를 swap out하여 Thrashing 을 방지한다.
Page fault rate의 값이 하한 값을 이하이면 쓸데없이 메모리를 너무 많이 갖고 있음을 의미하므로, 할당 frame수를 줄인다.
Chapter 9-3. 끝
이 포스팅은 이화여대 반효경 교수님 강의를 듣고 요약한 내용을 담고 있습니다.
'Dev.Basic > 운영체제' 카테고리의 다른 글
[OS] 10-2. File System II (0) | 2016.06.16 |
---|---|
[OS] 10-1. File System (2) | 2016.06.15 |
[OS] 9-2. Virtual Memory II (0) | 2016.06.13 |
[OS] 9-1. Virtual Memory I (3) | 2016.06.07 |
[OS] 8-5. Memory Management V (0) | 2016.06.06 |