[CS/운영체제] CH9. 가상 메모리 2
CH9. 가상 메모리 2
목차
1. 다양한 캐슁 환경
2. Clock Algorithm
3. Page Frame의 Allocation
4. Global vs. Local Replacement
5. Thrashing
6. Working-Set Model
7. Working-Set Algorithm
8. PFF(Page-Fault Frequency) Scheme
9. Page Size의 결정
1. 다양한 캐슁 환경
1. 캐슁 기법
● 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
● paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용
2. 캐쉬 운영의 시간 제약
● 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 겨웅 실제 시스템에서 사용할 수 없음
● Buffer cahcing이나 Web caching의 경우엔 O(1)에서 O(log n)정도까지 허용
● Paging System의 경우
- page fault인 경우에만 OS가 관여함
- 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
- O(1)인 LRU의 list 조작조차 불가능
-> 따라서 Paging System에서는 아래 설명할 Clock Algorithm을 사용합니다
2. Clock Algorithm
1. Clock Algorithm이란
● LRU의 근사(approximation) 알고리즘
● 여러 명칭으로 불림
- Second chance algorithm
- NUR(Not Used Recently) 또는 NRU(Not Recently Used)
● Reference bit을 사용해서 교체 대상 페이지 선정(circular list)
● reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
● Reference bit이 0인 것을 찾으면 그 페이지를 교체
● 한 바퀴 되돌아와서도(=second chance) 0이면 그때에는 replace 당함
● 자주 사용되는 페이지라면 second chance가 올 때 1
2. Clock Algorithm의 개선
● reference bit과 modified bit(dirty bit)을 함께 사용
● reference bit = 1 : 최근에 참조된 페이지
● modified bit = 1 : 최근에 write가 일어나 변경된 페이지 (I/O를 동반하는 페이지)
-> I/O를 동반하는 페이지는 교체시 오버헤드가 크기 때문에 교체 후순위로 밀림
3. Page Frame의 Allocation
Allocation Problem : 각 Process에 얼마만큼의 page frame을 할당할 것인가?
Allocation의 필요성
● 메모리 참조 명령어 수행시 명령어, 데이터 등의 여러 페이지를 동시 참조
-> 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
● Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함
-> 최소한의 allocation이 없으면 매 loop마다 page fault
- 그렇다해도 한 프로세스가 필요하다고 page를 왕창 올려버리면 다른 프로세스의 페이지를 다 밀어내고 한 프로세스의 페이지만 올려놓기 때문에 비효율적임
Allocation Scheme
● Equal Allocation : 모든 프로세스에 똑같은 갯수 할당
● Proportional Allocation : 프로세스 크기에 비례하여 할당
● Priority Allocation : 프로세스의 priority에 따라 다르게 할당
4. Global vs Local Replacement
● Global replacement
-> Replace시 다른 process에 할당된 frame을 빼앗아 올 수 있다
-> Process별 할당량을 조절하는 또 다른 방법
-> FIFO, LRU, LFU 드으이 알고리즘을 global replacement로 사용시에 해당
-> Working set, PFF 알고리즘을 사용
● Local replacement
-> 자신에게 할당된 frame 내에서만 replacement
-> FIFO, LRU, LFU 등의 알고리즘을 process별로 운영시
5. Thrashing
● 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생하는 현상
Thrashing 발생 과정
1. page가 부족하여 page fault rate가 높아짐
2. Swapping(I/O) 작업이 늘어나서 CPU utilization이 낮아짐
3. OS에서는 CPU utilization이 낮아졌으니 MPD(Multiprogramming degree)를 높여야 한다고 판단
4. 따라서 또 다른 프로세스가 시스템에 추가됨
5. 프로세스당 할당된 frame 수가 더 감소
6. Swapping(I/O) 작업이 증가함
7. CPU Utilization이 낮아짐... 반복
6. Working-Set Model
7. Working-Set Algorithm
8. PFF(Page-Fault Frequency) Scheme
9. Page Size의 결정
