• 가상 메모리는 프로세스 전체가 메모리내에 올라오지 않더라도 실행이 가능하도록 하는 기법이다.

1. Background

• 실행 중인 프로그램은 반드시 메모리에 적재되어야 사용할 수 있다는 타당한 요구조건으로 보이지만, 프로그램의 크기가 Physical Memory를 넘지 않아야한다는 점에서 한계점을 가진다.
• 프로그램에서는 거의 실행되지 않는 부분도 있고, 모든 부분을 동시에 요구하는 경우는 거의 존재하지 않는다.
• 그래서 프로그램을 메모리에 부분적으로 load하는 방식을 생각해보고 그 이점을 알아보면
  • 프로그램은 더이상 Physical Memory의 크기에 제한을 받지 않는다.
  • 각 프로그램의 Memory 사용량이 줄어들면서 CPU의 이용률과 처리율이 올라간다.
• 가상 메모리는 Logical Memory와 Physical Memory의 분리를 통해 실제 프로그램 수행에 필요한 Logical Memory의 부분을 Pyhsical Memory에 적재하여 실행한다. 또한 이 방법을 사용하면 Logical Memory의 특정 공간을 다른 프로세스와 공유할 수 있다.
• 프로세스의 Logical address space는 프로세스에 대한 프로그래머의 관점이고 아래와 같이 표현된다. 이런 Logical Memory와 Physical Memory의 mapping은 MMU에 의해 일어난다.
  

2. Demand Paging

• Demand Paging을 사용하는 가상 메모리에서는 페이지들이 실행과정에서 실제로 필요해질때 적재된다.
• Demand Paging은 요구되는 page만 관리하고 Swapping은 전체 프로세스를 페이징 한다.
• Demand Paging기법에서 pager가 page를 관리한다.

A. Basic Concept

• pager는 프로세스 전체를 swap - in하는 대신에 실제 필요한 page들만 메모리로 읽어온다.
• 이렇게 하기 위해서는 어느 페이지가 디스크에 있고, 어느 페이지가 메모리에 올라와 있는지 알아야한다. 이 기법엔 vaild/invaild 기법이 사용될 수 있다.
• Page Table의 특정 항목에 bit가 vaild하면 그 페이지는 메모리에 적재되어있고, invaild하다고 설정되어 있는 경우 해당 page가 유효하지 않거나, 유효하지만 디스크에 존재한다는 것을 의미한다.

B. Page Fault

• 프로세스가 메모리에 올라와 있지 않은 페이지를 접근하려고 하면 Page Table항목이 invaild로 설정되어있으므로 Page Fault Trap을 발생 시킨다.

  
  1. 프로세스에 대한 내부 테이블(일반적으로 PCB)을 검사해서 그 메모리 참조(reference)가 vaild/invaild 인지를 알아낸다. - User mode
  2. 만약 invaild한 page에 대한 참조라면 그 프로세스는 중단된다. 하지만 유효한 참조인데 페이지가 아직 메모리에 올라오지 않았다면, 그것을 디스크로부터 가져와야한다.(OS가 trap 발생; wait) - Kernel mode
  3. 빈 공간, 자유 프레임을 찾는다. - Kernel mode
  4. 디스크에 새롭게 할당된 frame으로 해당 page를 읽어 들이도록 요청한다. - Kernel mode
  5. 디스크 읽기가 끝나면, 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며, 프로세스가 유지하고 있는 내부 테이블을 수정한다.(vaild bit로 설정) - Kernel mode
  6. Trap에 의해 중단되었던 명령어를 다시 수행한다. - User mode

• 프로세스가 수행하는데 필요한 모든 페이지가 메모리에 올라올 때까지 필요할 때마다 Page Fault가 발생한다. 그래서 모든 Page가 적재되어 더이상 fault가 발생하지 않을 때 발생하지 않는다. 이것을 순수 요구 페이징이라고 한다.

• 프로그램들은 참조의 지역성이라는 성질을 가져서 프로그램의 어느 한 특정부분만 집중적으로 참조하여 요구페이징은 만족할만한 성적을 낸다.

• Demand Paging기법은 Page Fault 후 명령어 처리를 이어서 할 수 있어야 한다

3. Page Replacement

• 프로세스 진행 도중 Page Fault발생시 빈 프레임이 없다면 현재 사용되고 있지 않는 프레임을 찾아서 비우고 새로운 페이지를 프레임에 할당한다.

A. Page Replacement

1. 디스크에서 필요한 페이지의 위치를 알아낸다
2. 빈 페이지 프레임을 찾는다.
   1. 빈 프레임이 있다면 그것을 사용한다.
   2. 빈 프레임이 없다면 희생될 프레임을 선정하기 위하여 페이지 교체 알고리즘을 가동 시킨다. 그 후 희생될 페이지를 디스크에 기록하고 관련 테이블을 수정한다.
3. 빼앗은 프레임에 새 프레임을 읽어오고 테이블을 수정한다.
4. Page Fault가 발생한 지점에서부터 사용자 프로세스를 계속한다.

• 빈 프레임이 없는 경우에는 희생될 페이지를 디스크에 기록하고, 불러올 페이지를 가져오기 위해 디스크에 접근 해야한다. 디스크에 2번 접근해야한다는 것이다.
• 이러한 오버헤드는 변경 비트를 통해 감소시킬 수 있다. 만약 CPU가 Page에 write를 했다면 Page 내용이 바뀌었을테니 바뀐 내용을 새로 디스크에 저장해야 한다. 하지만 바뀌지 않았다면 굳이 똑같은 내용을 다시 디스크에 저장할 필요가 없다.
• Page Replacement는 여러 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 프레임을 할당해야 할지 결정(프레임 할당 알고리즘)해야 한다. 또한 페이지 교체가 필요할 때마다 어떤 페이지를 교체해야 할지 결정(페이지 교체 알고리즘)해야 한다.
• 페이지 교체 알고리즘의 목표는 낮은 Page-fault 비율을 달성하는 것이다.

B. Page-replacment Algorithm: FIFO

• 메모리에 가장 오래 있던 Page가 교체 된다.

C. Page-replacment Algorithm: Optimal Page Replacement

• 최적의 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 Page를 교체하는 것이다.
• 안타깝게도 이 방법은 프로세스가 앞으로 메모리를 어떻게 참조해야하는지 알아야 한다는 것에 실제로 사용되기는 어렵다.

D. Page-replacment Algorithm: LRU Page Replacement

• LRU 알고리즘은 가장 오랫동안 사용되지 않은 Page를 교체하는 알고리즘이다.
• LRU 알고리즘은 각 페이지마다 마지막 사용 시간을 유지하여 구현한다.
  • Counter 구현: Page가 reference될때마다 계수기나 시간을 기록한다.
  • Stack 구현: Page reference시 그 페이지 번호는 stack의 top에 넣어진다. 이런 방식을 반복하면 스택의 bottom엔 가장 오랫동안 사용되지 않은 페이지 번호가 있을 것이다.

E. Page-replacment Algorithm: LRU Approximation Page Replacement

• LRU 페이지 교체 알고리즘을 충분히 지원하는 하드웨어는 드물다. 대신 참조 비트를 이용한 형태로 어느정도 지원 하고 있다.

a. Additional-Reference Bits Algorithm

• 부가적 참조 비트 알고리즘은 각 페이지마다 8-bit shift register를 이용하여 참조를 기록하는 것이다.
• 일정한 시간 간격마다 참조 비트들을 오른쪽으로 이동 시키고 최상위 참조 비트에 참조에 대한 기록을 남긴다. 이때 참조 되었다면 1, 아니라면 0 이다.
• 이 방식을 통해 8비트를 이진수로 변환하여 생각한다면 가장 최근 참조된 페이지의 경우 8bit의 값이 가장 크고, 참조된지 가장 오래된 페이지는 8bit의 값이 가장 작을 것이다.
• 이러한 방식을 통해 8bit의 수가 가장 작은 페이지가 LRU가 되어 교체 된다.
• shift register의 크기와 시간 간격은 상황에 따라 다르다.

b. Second-Chance Algorithm

• 2차 기회 알고리즘의 기본은 FIFO Algorithm이다.
• 메모리에 올라온지 가장 오래된 Page를 교체할 페이지로 여기되, 참조비트를 확인하여 참조비트가 0 이면 교체하고 1이면 그 참조비트를 0으로 수정한 후 다음 FIFO Page로 넘어 간다.
• 구현은 Circular-Queue를 통해 주로 구현되며, 참조비트 값이 1인 페이지는 값을 0으로 수정하며, 참조비트가 0인 페이지를 찾을 때 까지 큐를 순환한다.

c. Enhanced Second-Chance Algorithm

• (Reference bit, Modify bit)로 구성된 쌍을 이용하여 2차 기회 알고리즘을 개선할 수 있다.
  1. (0,0): 최근에 참조되지도 않고, 2차기회 알고리즘에서 수정된 적도 없는 비트 → 교체하기 가장 좋은 페이지
  2. (0,1): 최근에 참조되지는 않았지만, 변경은 된 경우 → 이 페이지를 교체한다면 변경 내용을 디스크에 기록해야 한다.
  3. (1,0): 최근에 참조되었지만, 변경은 되지 않은 경우 → 이 페이지는 다시 사용될 가능성이 높다.
  4. (1,1): 최근에 참조되었고, 변경된 경우 → 이 페이지는 다시 사용될 가능성이 높을 뿐더러 교체 한다면 변경 내용을 디스크에 기록해야한다.

F. Page-replacment Algorithm: Counting-Based Page Replacement

a. LFU(Least Frequently Use) Algorithm

• 참조 횟수가 가장 적은 Page를 교체하는 것이다.
• 집중적으로 참조가 되어 횟수가 높은 Page인 경우, 참조비트를 일정한 시간마다 오른쪽으로 shift하여 exponential하게 그 영향력을 줄이는 방법을 사용할 수 있다.

b. MFU(Most Frequently Use) Algorithm

• 참조 횟수가 가장 적은 Page가 가장 최근에 참조된 것이고 앞으로 사용될 것이라는 판단

G. Page-Buffering Algorithm

• Page-Replacement Algorithm 과 더불어 Page Fault의 속도를 올리기 위한 방법이다

a. Keep a pool of Free-Frames

• Page-Fault 발생시 교체될 프레임을 찾지만, 교체될 프레임의 내용을 디스크에 기록하기 전에 시스템의 가용 프레임 풀에 있는 Frame중 하나에 먼저 새로운 Page를 읽어들이는 방식이다.
• 이 방식을 쓰면 지금 당장 필요한 Page를 더 빨리 사용할 수 있다.

b. keep a list of Modified Pages

• 위의 개념의 확장으로 변경된 Page를 디스크에 기록해야 하는 경우, HardWare가 Idle한 상태일 때 디스크에 변경된 내용을 기록하고 Modified bit를 0으로 수정한다.

C.Keep a pool of Free-Frames + 위치 기억

• Frame이 교체되어 디스크에 변경된 내용을 기록 후 Free-Frames Pool에 속해도 그 Frame에 있는 내용은 변경 되지 않았다면 그 Frame에 저장 되었던 Page의 내용은 남아있다.
• 따라서 Page Fault가 발생한 후 찾는 Page가 Free-Frame Pool에 훼손되지 않은 채로 남아 있는지 검사 한 후 남아 있다면 그대로 사용하고, 남아 있지 않다면 디스크에서 Page를 불러 읽어들인다.

4. Allocation of Frames

• 프로세스에 프레임을 얼마나 할당 할지 결정하는 것은 중요한 문제다. 만약 너무 적은 프레임을 할당한다면 Page Fault가 높아 효율적인 실행이 이뤄지기 힘들 것이다.
• 가장 쉬운 할당 방법은 프로세스에게 균일한 프레임을 할당(균일 할당)하는 것이지만, 프로세스마다 필요한 프레임의 수가 다르기 때문에 이 방법은 비효율적이다.
• 그래서 프로세스의 크기 비율에 맞추어 할당하는 방식인 비례할당 방식도 이용 되지만, 우선 순위가 낮아도 프로세스 크기별로 페이지가 할당될 수 있기에 이 경우, 우선순위와 프로세스의 크기를 조합하여 프레임을 할당한다.

A. Global Allocation VS Local Allocation

• 얼마만큼의 프레임을 할당하느냐의 문제와 더불어 Page-Replacment Algorithm에서 교체될 페이지의 범위를 결정하는 것 또한 중요한 문제이다.
• Global Allocation 방식은 프로세스가 교체할 프레임을 다른 프로세스가 속한 프레임을 포함한 모든 프레임을 대상으로 찾는 경우이다.
• 이 경우 우선순위가 높은 프로세스는 우선순위가 낮은 프로세스를 희생시킬 수 있다. 그러나 이 방식은 현재 Concurrent하게 실행되는 프로세스에 따라 Page Fault율이 영향을 받는다.
• Local Allocation 방식은 각 프로세스가 자신에게 할당된 프레임 중에서만 교체될 희생자를 고를 수 있는 알고리즘이다.

B. Non-Uniform Memory Access

• 복수의 CPU를 가진 시스템에서 CPU와 Memory의 연결 방식에 따라 특정 CPU는 특정 Memory에 더 빨리 접근할 수 있다.
• 이러한 시스템에서는 프로세스가 실행되는 CPU에 가장 가까운 Memory Frame이 할당되도록 해야한다.
• 더불어 스케쥴러는 프로세스가 마지막으로 실행된 CPU를 추적하고 그곳으로 스케쥴하고 메모리 관리 시스템은 스케쥴된 CPU와 가까운 메모리의 프레임으로 할당한다면, Cache 적중률이 올라가고 메모리 접근 시간이 감소할 것이다.

5. Thrashing

• 어떤 프로세스가 실행하기에 충분한 프레임을 할당받지 못한 경우, 그 프로세스는 반복적으로 Page Fault가 발생될 것이다. 이렇게 과도한 Paging작업으로 실제 프로세스가 execute되는 시간보다 더 많은 시간을 Paging에 쓸 경우 Thrashing이 발생했다고 한다.

A. Cause of Thrashing

• 운영체제는 CPU의 이용률(다중 프로그래밍의 정도)가 내려가면 새로운 프로세스를 시스템에 추가한다. 하지만 점점 Page Fault 비율이 올라가면서 CPU의 이용률이 더욱 떨어지게 되고 다시 운영체제는 새로운 프로세스를 추가하면서 Thrashing현상이 일어나게 된다.
• 프로세스 실행의 지역성 모델(Locality Model)은 프로세스가 실행될 때, 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조한다. 만약 어떤 프로세스에게 현재 지역성을 포함시키기에 충분한 프레임을 제공해주는 경우, 프로세스는 현재 지역의 모든 페이지가 메모리에 올라오기 전까지 Page Fault를 일으키지만 그 후에 지역이 변경되기 전까지는 Page Fault를 일으키지 않는다. 하지만 필요로하는 지역성의 크기보다 적은 크기의 프레임을 할당하게 되면 접근해야하는 모든 페이지를 메모리에 유지 할 수 없으므로 쓰레싱이 일어나게 된다.

B. Working-Set Model

• 프로세스 실행의 지역성 모델에 기초한 방식으로, 일정 시간마다 참조한 페이지를 기록하고 그 기록의 최근 N(작업 집합은 시간의 흐름에 따라 바뀐다)만큼의 참조를 작업 집합(Working Set)으로 보는 것이다.
• 그 작업 집합에 속한 페이지 집합이 프로그램 지역성의 근삿값이 되고, 운영체제는 이러한 작업집합 크기에 맞는 충분한 프레임을 할당한다.
• 프로세스는 시간이 지남에 따라 참조하는 지역이 달라지므로, 작업 집합또한 프로세스가 진행되면서 바뀐다. 따라서 새로운 지역을 참조 할 때 Demand Paging이 일어나고 원래 있던 Page를 교체하며 Page Fault율이 올라가고, 새로운 지역의 작업 집합이 메모리에 적재 되면 Page Fault율이 내려간다.

C. PFF; Page Fault Requency

• Page Fault Requency를 통해 Thrashing을 조절하는 방식이다.
• Page Fault율의 상한과 하한을 정해서 Page Fault가 상한을 넘으면 그 프로세스에게 프레임을 더 할당해주고 하한 아래로 내려가면 그 프로세스의 프레임 수를 줄이는 방식으로 Thrashing을 조절한다.