10.2 Virtual Memory 2

 

1. Caching

 캐싱은 한정된 빠른 공간에 요청된 데이터를 저장했다가 나중에 그 데이터를 요청할 때 바로 제공하는 것. 지금까지 배운 페이징 기법도 캐싱의 한 예이다. page fault는 cache miss인 것이다. paging system 말고도 cache memory, buffer caching, web caching(proxy server)에서도 사용하는 것이 바로 이 캐싱 기법이다. 

 그리고 캐시를 교체하는 알고리즘의 제약은 당연하게도 존재한다. Buffer caching이나 Web caching의 경우 삭제할 항목을 결정하는 것은 O(1)~O(logn) 안에 결정되어야 한다. 그러나 Paging system에서는 paging 기법을 통해 주소를 변환할 때, 그리고 그 page가 메모리에 이미 있는 경우 OS는 CPU 제어권을 갖지 않는다. 따라서 OS는 LRU나 LFU 알고리즘 같은 것들을 실제로 적용할 수 없다. 오직 page fault가 일어나서 trap이 걸렸을 때만 OS가 CPU를 갖게 되기 때문이다. 따라서 LRU에서 Linked list의 원소를 뒤로 옮기는 작업을 O(1)만큼 걸린다고 해도 OS는 할 수 없게 된다. 대신 LRU나 LFU는 buffer caching, web caching에서는 사용될 수 있다는 것이다.

---

Second-Chance Algorithm(Clock Algorithm)

  Second chance는 LRU의 근사 알고리즘이다. NUR(Not Used Recently) 혹은 NRU(Not Recently Used)라고도 부른다. referenct bit를 통해서 교체할 페이지를 선정하는데 'Clock'이라는 이름에 걸맞게 Circular list로 처리한다. reference bit가 0인 것을 찾을 때까지 포인터를 이동하며 포인터 이동 도중에 bit가 1인 것은 전부 0으로 바꾼다. 이때 bit가 0인 것을 찾았다는 것은 한 번 회전할 때까지 그 페이지를 참조한 적이 없다는 것을 의미한다. 그리고 그 bit를 세팅하는 것은 OS가 하는 것이 아니라 하드웨어가 하는 것이다. 그러면 나중에 page fault가 발생하고 메모리로부터 페이지를 쫓아낼 때 그 clock을 순차 탐색하면서 bit를 확인하면 되는 것이다. 어느 정도 오랫동안 참조가 되지 않은 페이지를 쫓아내기 때문에 LRU 하고 비슷한 효과를 낼 수 있다.

 

 추가적으로 Dirty bit라는 것을 둘 수 있다. 메모리에서 write로 참조될 수 있는데 어떤 페이지가 쫓겨날 때 dirty bit가 1이면 적어도 한 번은 내용을 수정한 페이지라고 가정한다. 그때는 backing store에 수정된 내용을 반영해야 한다. 쫓아내려면 디스크에다가 써주고 나서 쫓아내야 한다는 것이다. 즉, 일이 더 많은 것이기 대문에 dirty bit가 1인 것은 웬만하면 쫓아내지 않고 0인 것을 쫓아낸다면 좀 더 성능을 향상할 수 있을 것이다.

 

 

---

Page Frame의 Allocation

 프로그램 여러 개는 메모리에 동시에 올라가 있다. 그러나 쫓아낼 때는 어떤 프로세스인지와는 관계없이 특정 알고리즘에 따라 쫓아내었다. 그러나 실제로는 어떤 프로그램이 원활하게 실행되기 위해서는 이 프로그램이 CPU에서 실행이 되면서 page fault를 잘 내지 않으며 일련의 page들이 메모리에 함께 올라와 있어야 더 효율적이 되는 것이다. 예를 들어, loop를 도는 프로그램을 생각하자. 그것을 구성하는 page 들은 한꺼번에 메모리에 allocate 되어야 할 것이다. 그렇지 않으면 루프를 돌 때마다 계속해서 page fault가 발생할 것이다. 그렇다고 하더라도 한 프로세스가 메모리를 장악하면 비효율적이 될 것이다. 그래서 Allocation은 각 프로세스에게 메모리를 어느 정도는 나누어주자는 것이다.

 

1. Equal allocation : 모든 프로세스에 똑같은 만큼을 할당

2. Proportional allocation : 프로세스 크기에 비례하여 할당

3. Priority allocation : 프로세스 priority(CPU 우선순위)에 따라 할당

---

Global vs Local Replacement

 그러나 우리가 임의로 allocate를 하지 않더라도 Replacement Algorithm에 따라 처리를 하다보면 그때그때 어떤 프로세스가 메모리를 많이 요구하면 그 프로세스에 더 많은 프레임을 할당해 줄 수 있다. 이처럼 미리 할당을 하지 않고 알아서 알고리즘을 사용했을 때 프로세스 별로 메모리 할당량이 조절될 수 있다. 그러나 FIFO, LRU, LFU는 할당 효과가 없지만 Working set, PFF알고리즘은 그 효과가 존재한다. 

 Global Replacement는 다른 process에 할당된 프레임도 뺏을 수 있는 것이고, Local Replacement는 프로그램한테 해놓은 부분 이외에는 빼앗지 못하는 것을 의미한다.

---

Thrashing(쓰래슁)

 

처음에 프로그램 하나만 올라가 있으면 CPU utilization이 낮다. 그 이유는 I/O를 하러 가는 순간 CPU는 휴식해야 하기 때문이다. 그래서 메모리에 프로그램을 계속해서 올리면 다른 프로그램을 CPU가 실행할 수 있기 때문에 utilization이 늘어난다. 그러다가 degree가 어느 이상 도달하면 utilization이 뚝 떨어진다. 이것을 Thrashing이라고 한다.

 Thrashing은 page fault rate가 너무 높아지면서 발생하게 되는데, 실행해야 할 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 allocate받지 못했을 때 발생하게 되는 것이다. 근데 OS는 "어? CPU utilization이 낮네? Multiprogramming degree를 높여야겠다." 라고 판단하게 된다. 그렇게 되면 프로세스 당 할당된 frame 수가 더 감소하고 low throughput으로 이어진다. 이걸 막으려면 MPD를 조절해주어야 한다. 

 

---

Working-Set Algorithm [Global Replacement]

 그 MPD를 조정해 주는 것이 Working-Set Algorithm이다. 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조하는 특징을 갖고 있다(for loop예시). 그 집합을 locality set이라고 한다. 좀 더 일반적으로 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼뻔에 메모리에 올라와 있어야 하는 page set을 Working set이라고 한다. Working set은 적어도 한꺼번에 메모리에 올라와 있음을 보장해주는 것이 필요하다.

 Working set모델에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행이 된다. 따라서 메모리에 working set이 전부 올라와있지 못하게 되는 경우는 그냥 자기가 갖고 있는 frame들을 전부 반납하여 swap out된다. (suspended 상태)

 

 

* working set의 결정

 working set window를 통해 set을 결정한다. window의 크기는 delta로 나타내며 이 delta값은 시시각각 변할 수 있다. 다음 예시에서는 10으로 두었을 때인데, t1시점에서 delta를 10으로 두고 working set을 살펴보면 {1, 2, 5, 6, 7}이다. 즉, 5개의 페이지 프레임을 필요로 하며 만약 이보다 적은 개수의 프레임을 할당하려고 할 시에는 그냥 swap out되어 버린다. 그러나 t2시점에서 delta를 10으로 두었을 때 working set은 {3, 4}이다. 즉, 2개의 페이지 프레임을 필요로 하게 된다. 이것은 결국 참조된 후 delta 시간 동안 해당 page를 메모리에 유지한 후 버리는 것과 완전히 동일하다. 

 

 

---

 

 

PFF(Page-Fault Frequency) Scheme [Global Replacement]

PFF는 간단하다. Page-fault rate의 상한값과 하한값을 둔다. 그리고 page fault를 많이 일으키는 프로그램에게는 페이지 프레임을 더 주고 너무 적게 발생하는 프로그램에게는 페이지 프레임을 빼앗는다. 일반적으로 프로그램'마다' 할당받는 frame이 커지면 page fault rate는 당연하게 줄어든다.

 

---

 

Page size의 결정

 page size를 줄어게 되면

1. 페이지 수가 증가하고

2. 페이지 테이블 entry가 증가하여 페이지 테이블을 위한 메모리 낭비가 심해진다.

3. Internal fragmentation이 감소

4. Disk transfer의 효울성 감소.

    - 기본적으로 disk는 헤드가 이동할 때는 많은 양의 뭉치를 읽어서 올리는 게 좋은데 페이지 작으면 page fault가 일        어날 때 너무 큰 비용이 듦.

5. locality의 측면에서는 page size가 작은 것이 좋지 않다.

6. 하지만 필요한 정보들만 메모리에 올릴 수 있어서 메모리 이용이 효율적이 될 수 있다. 

 

그래서 최근에는 page size를 점점 키우고 있는 추세이다. (기본적으로는 4kb)

 

 

 

본 글들은 이화여대 반효경 교수님 2014학년도 1학기 운영체제 강의를 기반으로 작성됩니다.

링크 : http://www.kocw.net/home/search/kemView.do?kemId=1046323