[17] 운영체제 - Virtual Memory-2

    안녕하세요!

정말 간만의 글이네요! 시험기간이다 뭐다 해서 정신이 없어서  이제야 밀린 포스팅을 작성하게 되었습니다.

저번 포스팅에서 언급했듯이 이번 포스팅에서는 개선된 LRU 알고리즘을 비롯하여

나머지 Page Replacement 알고리즘들을 살펴보는 시간을 갖도록 하겠습니다.

또한 프로세스들에게 Frame을 할당하는 방법도 공부해보도록 하겠습니다.

LRU-Approximation 알고리즘

LRU-Approximation 알고리즘은 기존의 LRU 알고리즘과 다르게 H/W의 지원 없이

Reference-Bit를 이용하여 구현하는 알고리즘 기법입니다.

이러한 개선된 LRU-Approximation 알고리즘에도 여러 가지 방법이 존재하는데요! 하나하나 간단히 살펴보도록 하겠습니다.

1. Additional-Reference-Bits 알고리즘

    이 알고리즘은 Page table 내 각각의 Page에 8 비트 짜리 참조 비트가 존재하여 

    일정 시간의 간격마다 Access 되었던 페이지들의 비트들을 오른쪽으로 Shift 하는 연산을 하게 됩니다.  

    그렇다면 가장 큰 값의 비트를 가진  페이지가 최근에 Access 되었다는 것을 알 수 있죠.

    또한 가장 작은 값의 비트를 가진 페이지들이 Victim Page로 선택이 되며 같은 값들에 대해서는 

    FIFO 알고리즘을 이용하여 Victim 페이지를 고르게 됩니다. 예를 들어 보겠습니다.

                                                                                              0-10000000

                                                                                              1-10000000

                                                                                              2-10000000

                                                                                           <0-Page Access>

                                                                                           <1-Page Access>

                                                                                          ----Interrupt----

                                                                                              0-01000000

                                                                                              1-01000000

                                                                                              2-10000000   

                                                                                           <2-Page Access>

                                                                                          ----Interrupt----

                                                                                              0-00100000

                                                                                              1-00100000

                                                                                              2-01000000   - > 가장 큰 값이므로 가장 최근 Access 된 것을  알 수 있음.

  

2. Second-Chance 알고리즘

    Second-Chance 알고리즘은 말 그대로 한 번의 기회를 더 주는 알고리즘을 말합니다.

    이 알고리즘은 FIFO 알고리즘을 기반으로 합니다. 

    하지만 Page Table의 각각의 Page에는 1 비트 짜리Reference bit가 존재하고 

    초기값은 모두 0이며 Access가 되면 1로 바꿉니다. 

    하지만 FIFO 알고리즘이 기본 알고리즘이기 때문에 Reference bit가 1이라도 

    선택이 될 수 있는데 이때 만일 Reference bit가 1이라면 최근에 Access되었다는 것이라고 

    간주를 하고 0으로 바꾼 후 한 번의 기회를 더 주고 다른 Victim 페이지를 찾습니다.

    만일 모든 Page의 Reference bit가 1이라면 결국은 FIFO 방식으로 작동하게 됩니다.

3. Enhanced Second-Chance 알고리즘

    Enhanced Second-Chance 알고리즘은 Reference bit와 Modify bit를 이용하여 Victim 페이지를 찾는 알고리즘입니다.

이전 포스팅에서 Modify bit에 관해 공부했었는데요! 해당 부분의 내의 값이 변하게 되면 Modify bit를 1로 바꿔준다는 것을 배웠었습니다.

그리하여 우선순위는 다음과 같습니다. 

Reference bit와 Modify bit가 둘 다 1이라는 뜻은 최근에 Access 되고 값의 변화가 있으므로 다시 선택될 가능성이 높다는 뜻이고 Victim 페이지로는 적절하지 않다는 것을 의미합니다. 하지만 모든 Page Table을 전부 뒤져야 한다는 단점이 존

Counting-Based 알고리즘

Counting-Based 알고리즘은 Access된 횟수를 Page table의 각 Page에 저장을 하여 횟수를 통해 Victim 페이지를 결정하는 알고리즘입니다. 이러한 Counting-Based 알고리즘에는 두 가지가 존재하는데 다음과 같습니다.

1. LFU (Least Frequently Used) 알고리즘

   LFU 알고리즘은 횟수가 가장 적은 페이지를 Victim 페이지로 선택하는 것이며 Access 횟수가 적다는 것은

    "앞으로도 선택이 안될 것이다"라고 판단하는 알고리즘입니다.

2. MFU(Most Frequently Used) 알고리즘

   MFU 알고리즘은 횟수가 가장 많은 페이지를 Victim 페이지로 선택하는 것이며 Access 횟수 참조횟수(hans12312님의 제보) 

   가 많다는 것은

    "지금까지 많이 Access 참조했으니 앞으로는 Access 참조되지 않을 것이다"라고 판단하는 알고리즘입니다.

Allocation of Frames

Demand Paging에서는 프로세스가 당장 수행해야 할 부분에 대해서 최소한의 Frame만을 할당하게 됩니다.

이러한 Frame을 할당해주는 방법에도 몇 가지가 존재하는데요. 바로 살펴보도록 하겠습니다.

1. Fixed allocation VS Priority allocation

<Fixed allocation>

 - Equal allocation : 이 방법은 프로세스의 목적과 성격에 상관없이 모든 프로세스에게 고정된 양의 Frame을 할당해주는 것을 의미합니다. 예를 들어 100개의 Frame과 5개의 프로세스가 존재한다면 각 프로세스에게 20개의 Frame을 할당해주는 방법입니다.

-Proportional allocation : 이 방법은 프로세스의 사이즈에 비례하여 Frame을 할당해주는 방법입니다.

<Priority allocation>

우선순위 할당은 말 그대로 우선순위가 높은 프로세스에게 더 많은 양의 Frame을 할당해주는 방법입니다.

보다 많은 Frame을 할당해주게 된다면 Page fault 횟수는 그만큼 감소하게 되고 프로세스는 작업을 보다 빨리 마치게 됩니다.

즉, 우선순위가 높은 프로세스가 작업을 빨리 마치게끔 하여 Frame을 반환하여 Frame의 순환율을 높이기 위한 방법입니다.

2. Global Replacement VS Local Replacement

<Global Replacement> : Victim 페이지를 찾을 때 모든 프로세스의 모든 페이지에서 Victim을 찾는 방식입니다.

<Local Replacement>: Victim 페이지를 찾을 때 해당 프로세스 내에서만 Victim을 찾는 방식입니다.

오늘은 이렇게 Victim 페이지를 찾는 나머지 알고리즘과 프로세스에게 Frame을 할당해주는 방법에 대해서 공부해보았습니다!

다음 시간에는 이러한 Page Replacement 알고리즘으로 인해 생기는 문제점인

Thrashing 현상과 기타 문제점들을 살펴보도록 하겠습니다.

감사합니다!