9주차. 가상메모리(2) _ 캐시 기법 (Clock Algorithm + reference/modified bit), Trashing (Working Set, PFF), Page Size

Caching

• 한정된 빠른 공간(Cache)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
• program system외에도 cache memory, buffer caching, web caching등 다양한 분야에서 사용하고 있다.

캐쉬 운영의 시간 제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에 적용하기가 어렵다.
  마지노선 (log N)
• 빠르게 데이터를 가져오기 위해 사용하는 것인데, 메모리에 올리기위해 공간확보에 시간을 오래쓰게 되면 비효율적이다.

Buffer caching & Web caching의 경우

• → O(1) ~ O (log N) 정도까지 허용한다.
• 여기서 LRU, LFU 알고리즘이 사용된다.

Paging System의 경우

• page fault인 경우에만 OS가 관여한다.
• 문제는 page가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없다.
• O(1)인 LRU의 list 조작조차 불가능하다. (OS가 각 Page의 참조 시각 정보를 모른다.)
• 커널은 page fault가 발생해서 해당 page가 메모리에 존재하지 않는다는 정보만 알 뿐이다.

Why? → LRU, LFU 알고리즘이 동작할 때는 프로그램 프로세스가 수행중인 것으로 (유저 모드) 메모리에 적재되는 시간은 Kernel이 알수 없는 부분이다. 이부분을 알기위해서는 커널이 관리를 했어야 알 수 있다.

A. Paging system은 그래서 다른 알고리즘을 사용하게된다. → Clock Algorithm

---

Clock Algorithm

LRU의 근사 (approximation) 알고리즘으로, OS는 해당 page들이 언제 들어왔는지에 대한 정보를 모르므로, 가장 늦게 참조된 page도 알지 못한다. 그래서 최근에 사용되지 않는 page를 확인하는 방식으로 진행된다.

• Second change algorithm
• NUR(Not Used Recently), NRU(Not Recently Used) 라고 불린다.

작동방식

• Reference bit를 사용해서 교체 대상 page를 선정하게 된다.
• 자료구조는 Circular Linked List 구조를 갖는다.

진행

• Reference bit가 0인 것을 찾을 때까지 포인터를 한칸씩 이동한다. (참조되지 않은 page를 찾는 것으로 최대 한바퀴)
• 포인터가 이동중에 reference bit가 1인 Page는 bit를 0으로 바꾼다. (참조 내역을 끔)
• reference bit가 0인 것을 찾으면 해당 page를 내쫓고 교체해준다.

참고

• 만약 한바퀴를 되돌아와서도 (= second chance) 0이면 그때는 replace 당한다 → 자기가 0으로 바꾸고, 그뒤로 참조된적이 없으니 교체하는 것
• 만약 자주사용되는 page라면 한바퀴 돌아왔을 때 1로 바뀌어 있을 수 있으므로, 교체당하지 않는다.

Modified Bit 사용

• 성능향상을 위해 Modified bit를 같이 써서 참조된 Page에 대해 정보의 변경 여부를 알려준다

Why? → 수정된 page를 쫓아내야한다면 메모리에서 바로 내쫓을 수가 없다. Swap Area(DISK)에 변경된 내용을 반영해주고 쫓아내야 하므로, Modified bit가 체크되어있다면 내쫓지 않는것이다.

 

---

Page Frame의 Allocation

Allocation problem → 각 프로세스에 얼마만큼의 page frame을 할당해 줘야할까?

Allocation의 필요성

• 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시에 참조하게 된다.
• 명령어 수행을 위해 최소한 할당되어야 하는 Frame 수가 있다.
• 반복문을 구성하는 Page 부분은 한꺼번에 Allocation되는 것이 유리하다.
  → 최소한의 allocation이 없으면 매 loop마다 page fault가 발생한다

Allocation Scheme

• Equal Allocation: 모든 프로세스에 똑같은 개수로 할당한다.
• Proportional Allocation: 프로세스 크기에 비례하여 할당한다.
• Priority Allocation: 프로세스의 priority에 따라 다르게 할당한다.

Global replacement vs. Local Replacement

Global replacement

• LRU, LFU 등 replace 발생 시 자연스럽게 다른 process에 할당된 frame을 빼앗아 올 수 있다.
• 자연스럽게 porcess별 할당량이 조절되는 것에 맡기는 방법으로 전체 프로세스의 Frame에 대해 교체를 허용한다.
• FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당한다.
• Working set, PFF 알고리즘을 사용한다. 이 경우는 반복문 등 연관 Page를 한꺼번에 가져오는 구현이 가능하다.

Local replacement

• 특정 프로세스에게 할당된 Frame내에서만 replacement를 허용한다. (동등, 비율, 우선순위 별 할당된 Frame 내에서)
• FIFO, LRU, LFU 등의 알고리즘을 process 별로 사용할 수 있다.

Trashing

프로세스의 원할한 수행에 필요한 최소한의 page frame수를 할당 받지 못해 잦은 page fault가 발생하는 현상

1. CPU 이용률이 낮으니깐 Multi Programming Degree를 높인다. 즉 더 많은 프로세스를 물리적 메모리에 올려준다.
2. 일정 수준까지는 CPU 이용률과 Multi Programming Degree가 비례해서 올라가다가 일정 수준부터 Page fault의 비율이 올라간다.
3. 이로 인해 CPU 이용률이 낮아진다.
4. OS는 CPU 이용률이 낮으므로 Multi Programming Degree를 높여야 한다고 판단한다.
5. 또 다른 프로세스가 시스템에 추가된다. Multi Programming Degree도 올라간다.
6. 메모리의 공간은 이미 부족하므로 프로세스 별로 할당되는 메모리 frame의 수는 줄어들고, 프로세스는 page fault가 더욱 자주 발생해서 swap in / out으로 바빠지게 된다.
7. 정작 CPU는 Page Fault -> Swap Area IN/OUT 의 반복으로 인해 한가해지게 되는 결과를 낳고
8. → Low throughput을 갖게된다.

위와 같은 Trashing 현상을 막기위해서는 Multi Programming Degree를 조절해줘야 한다.

→ Working Set Algorithm & PFF (Page Fault Frequency) Algorithm 을 사용해서 조절

Working Set Model

Locality of reference

• 프로세스가 작업하는 특정 시간 동안 일정 장소만을 집중적으로 참조하는 현상
• 집중적으로 참조되는 해당 page들의 집합을 Locality Set이라 한다 (→ working set algo에서는 이를 working set이라 지칭)

Working-Set model

• Locality에 기반하여 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working-Set이라 정의한다.
• working set 모델에서는 process의 working set 전체가 메모리에 올라올수 있는 경우에만 수행이 된다.
• working set을 확보하지 못하다면 모든 frame을 반납하고 swap out 되어서 suspend 상태가 된다.
• 즉, Page 5개가 필요한데 3개밖에 올릴 공간이없다면 올리지 않고 반납하고 suspend상태로 전환되는 것이다.

→ 이렇게 함으로서 Trashing을 방지할 수 있고 & multi programming degree를 결정한다.

Working-Set Alogorithm

working set의 결정

• working-set window를 통해 알아낸다.
• 시간대 별 Frame의 사용이 다르므로 window size 또한 가변적이다.
• 특정 시각 t에서의 윈도우 크기가 ∆일 경우
  working-set WS (t) → time interval [t-∆ ~ t] 동안 참조된 서로 다른 페이지들의 집합의 크기
• working set에 속한 page는 메모리에 유지되고, 그렇지 않은 page는 버려진다.
  (처음 참조되고, ∆시간 동안은 page가 메모리에 유지됨)

위의 경우 Working Set Window의 크기는 10이다. 이때 사용된 Page Frame은 2 6 1 5 7 7 7 7 5 1 이 있다. 여기서 중복을 제거하면 Working Set은 1, 2, 5, 6, 7이 되므로 WS은 5가되고 5개의 Frame을 올릴 공간이 확보되어야만 메모리에 프로세스를 올리고 수행되게 된다.

WS은 시간대별로 사용된 Frame 종류도 다르므로 WS 또한 시간대 별로 다르다. t2시에는 WS가 3, 4 Frame으로 2인것을 알 수 있다.

 

Process들의 working set size의 합 > Page Frame의 총 수 인 경우

• 일부 프로세스를 swap out시켜서 남은 process의 working set을 우선적으로 충족시켜준다.
• MPD를 낮춘다.

Process들의 working set size의 합 < Page Frame의 총 수 인 경우

• Swap out 되었던 프로세스에게 working set을 할당해준다.
• MPD를 올려준다

Window size ∆ 결정의 필요성

• working set을 제대로 탐지하기 위해서는 window size를 잘 결정해줘야 한다

Q. 너무 작게 잡으면?

A. Locality set을 제대로 파악하지 못해서 page fault가 자주 발생하게 되어, CPU utilization이 낮아진다.

 

Q. 무한으로 잡으면?

A. 전체 프로그램을 구성하는 page를 전부 working set으로 간주하는 것이 되므로 Multi programming 정도가 낮아진다.

 

Q. 너무 크게 잡으면?

A. Locality set이 너무 커지니깐 프로세스를 많이 올릴수 없어서 MPD가 낮아지고, 쓸데없는 Frame도 메모리에 다 올리게 되어서 CPU utilization도 낮아진다.

PFF (Page Fault Frequency) Algorithm

page fault rate의 상한값과 하한값을 설정해서 page frame의 할당량을 조절한다.

• page fault rate의 상한값 이상인 경우: frame을 더 할당해 준다.
• pgae fault rate가 하한값 이하인 경우: frame을 좀 뺏는다.

만약 할당해줘야 하는데 빈 frame이 없다면 일부 프로세스를 swap out시켜서 suspend상태로 바꾼다.

---

Page Size의 결정

논리 주소공간, 물리 주소공간 모두 동일한 page, frame으로 자르므로 크기를 잘 결정해야한다.

page size가 작으면

• page 수 증가
• page 테이블 크기 증가 (각 Page를 가리키기 위한 인덱스를 가져야하므로 테이블의 크기가 증가한다)
• Internal fragmentaion 감소 (더 작은 단위로 프로세스를 쪼개므로 내부 단편화도 줄어든다)
• Disk Transfer의 효율성 감소
  Why?
  A. DISK는 기본적으로 디스크 헤더가 seek해서 찾게되는데, 시간이 매우 느리므로 한번 접근해서 메모리를 가져올 때 많이 가져오는게 좋다.
  → Seek / rotation vs. transfer

• 필요한 정보만 메모리에 올라오게 되므로 메모리 이용이 효율적이다. 세밀하게 필요한 부분만 올릴수 있음
• Locality의 활용성 측면에서 좋지 않다.
  Why?
  A. page는 연속적으로 사용되는 경우가 많다. page의 크기가 크면 한번의 page fault를 일으키고 관련 부분은 같이 가져왔으므로 바로 사용할 수 있다.
  그런데, page size가 작으면 각각의 page로 존재하므로 따로 page fault를 일으키면서 각각 가져와야하므로 비효율적일수 있다.

결과적으로 현재에는 Page Size를 크게 잡아서 사용한다.