운영체제 10. 가상 메모리 관리 (3) - Replacement Strategies for Fixed Allocation 1

출처 : https://www.youtube.com/watch?v=xLovOdiRtjI&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=34

 

 

 

지난 시간에는 가상 메모리의 관리 기법들을 공부하였다. 이번 시간에는 관리 기법 중에서도 replacement strategies(교체 기법)의 Fixed allocation에 대해서 알아본다.

 

 

Locality

 

우리가 replacement(교체)를 하는데 기준이 필요하다. 이때, locality를 기준으로 한다. 

 

• 프로세스가 프로그램 / 데이터의 특정 영역을 집중적으로 참조하는 현상

 

• 원인
  • Loop structure in program
  • Array, structure 등의 데이터 구조

 

• 공간적 지역성 (Spatial locality)
  • 참조한 영역과 인접한 영역을 참조하는 특성
• 시간적 지역성 (Temporal locality)
  • 한 번 참조한 영역을 곧 다시 참조하는 특성

 

 

Locality (example)

 

• 가정
  • Paging system
  • Page size = 1000 words. 1000줄 짜리 워드
  • Machine instruction size = 1 word. machine instruction이 한 줄을 차지함
  • 주소 지정은 word 단위로 이루어짐
  • 프로그램은 4번 page에 continuous allocation 됨
    • 우리가 만든 프로그램은 B와 C라는 array의 합을 A라는 array에 저장하는 반복문 프로그램
    • 해당 프로그램은 4번 page에 존재함
  • n = 1000

 

 

코드는 4번 page에 존재하므로 memory address는 4000번대부터 시작한다.

array A는 6번 page, array B는 7번, array C는 8번 page에 존재한다.

ONE, n 이라는 local variable(지역 변수)는 9번 page에 존재한다.

 

이 프로그램을 실행할 때 참조하는 page들 ω (=reference string)이 존재한다.

ω를 보았을 때, 맨 처음에는 시작 주소인 4번 page(address 4000)를 보고 ONE이라는 지역 변수를 참조한다. 그러면 ONE이 존재하는 9번 page(address 9000)를 보고, 다시 4번 page(4001)를 보았을 때 n이라는 지역 변수를 참조하므로 n이 존재하는 9번 page(9001)를 본다.

그 다음 4번 page들(4002, 4003)을 본다.

(494944)

 

그 다음부터는 4번 page(4004)를 보고 B를 참조해야하므로 7번 page를 본다.

다시 4번 page(4005)를 보고 C를 참조해야하므로 8번 page를 본다.

다시 4번 page(4006)를 보고 A를 참조해야하므로 6번 page를 본다.

이제 4번 page들(4007, 4008)를 보았는데, address 4008에서 branch 4002(4002번 주소로 돌아가라)가 있으므로 4번 page(4002)를 다시 본다.

(474846444)가 n번만큼 반복되게 된다.

 

우리가 무수히 많은 메모리 참조 중 5개의 page(4, 6, 7, 8, 9번)만을 집중적으로 접근하게 된다.

이 5개의 page가 locality가 된다.

우리가 메모리 접근을 할때 locality가 존재한다. 그러므로 교체 기법 혹은 메모리 관리 기법을 사용할 때, locality를 최대로 활용하면 성능을 향상시킬 수 있다.

 

 

Replacement Strategies

 

replacement strategies는 allocation 기법에 따라 크게 2가지로 분류된다.

 

• Fixed allocation
• Variable allocation

이번 시간에서는 Fixed allocation을 중점적으로 공부해보자.

 

• Fixed allocation : 각 프로세스에게 고정된 수의 page frame을 할당하는 기법
  • 어떤 프로세스 Pi가 4개의 page frame을 가진다고 해보자. 만약 4개의 page frame에 A, B, C, D라는 page들이 들어와있어서 메모리의 공간이 없는 상황에서 새로운 page E를 메모리에 적재하려고 한다면, 기존의 page들(A, B, C, D) 중 하나가 메모리에서 빠져나와야 새로운 page E를 메모리에 적재할 수 있다. 즉, 교체가 발생해야 한다.
  • 그렇다면 어떤 page를 교체할 것인가? 에 대한 것이 바로 replacement strategies이다.

 

 

Min Algorithm (OPT Algorithm)

 

• 1966년 Belady에 의해 제안됨
• Minimize page fault frequency (proved) : page fault의 발생 빈도를 최소화시키는 알고리즘이다.
  • Optimal solution
• 기법
  • 우리가 앞으로 볼 page reference string을 알고있다고 가정했을 때, 앞으로 가장 오랫동안 참조되지 않을 page를 교체 -> page fault frequency를 최소화 -> performance 최대
    • Tie-breaking rule : page 번호가 가장 큰 / 작은 page 교체
• 실현 불가능한 기법 (Unrealizable)
  • Page reference string을 미리 알고 있어야 함
• 교체 기법의 성능 평가 도구로 사용 됨. 우리가 replacement strategy를 만들었을 때, 얼마나 최적의 근접한가에 대한 기준이 됨 (전투력 측정기)

 

 

메모리에 x, y, z 라는 page들로 가득차있는 상황에서 w라는 새로운 page를 보려고 한다. 그러면 x, y, z 중 누군가를 w와 교체해주어야 한다. Min Algorithm에서는 가장 늦게 참조를 하는 y를 w와 교체시킨다.

 

 

• Example
  • 프로세스가 4개의 page frame을 할당받았다. 맨 처음에 메모리는 비어있다.
  • reference string ω를 알고있다. ( ω = 12614512145645)
  • Time 1 : 최초에는 memory가 비어있으므로 그냥 reference string 1번을 memory에 적재한다.
  • Time 2 : 2번도 memory에 빈 공간이 있으므로 그냥 적재한다.
  • Time 3 : 6번도 memory에 빈 공간이 있으므로 그냥 적재한다.
  • Time 4 : 1번은 이미 memory에 존재하므로 넘어간다.
  • Time 5 : 4번도 memory에 빈 공간이 있으므로 그냥 적재한다.
  • Time 6 : 5번을 읽을려고 하는데 memory에 빈 공간이 없다. 그러므로 1, 2, 4, 6번 중 가장 늦게 참조하는 6번을 5번과 교체한다.
  • Time 7 ~ 11 : 1, 2, 1, 4, 5 번까지는 이미 memory에 존재하므로 page fault가 일어나지 않는다.
  • Time 12 : 6번을 읽으려고 하는데 memory에 빈 공간이 없다. 그러므로 1, 2, 4, 5번 중 4번과 5번은 뒤에서 다시 봐야하므로 1번과 2번 중 하나를 교체해야 한다. 둘 중 무엇을 교체할지는 규칙을 만들어서 정하면 된다(tie breaking rule : 동점일 때 하나를 정하는 방법). 이 예시에서는 작은 1번을 교체한다.
  • Time 13 ~ 14 : 4번과 5번은 memory에 존재하므로 page fault가 발생하지 않고 넘어간다.
• Page fault는 총 6번 발생한다. 이것이 optimal solution이다.

 

 

Random Algorithm

 

• 무작위로 교체할 page 선택
• Low overhead
• No policy
• Min algorithm과 마찬가지로 어떤 평가의 기준으로 사용할 수 있음

 

 

FIFO Algorithm

 

• First In First Out
  • 가장 오래된  page를 교체
• Page가 적재된 시간을 기억하고 있어야 함

 

• 자주 사용되는 page가 교체 될 가능성이 높음
  • Locality에 대한 고려가 없음
• FIFO anomaly (Belady's anomaly)
  • FIFO 알고리즘의 경우, 더 많은 page frame을 할당 받음에도 불구하고, page fault의 수가 증가하는 경우가 있음 (Locality를 고려하지 않았기 때문에)

 

 

3개의 page frame이 존재하고 과거에 z, x, y 라는 page가 memory에 적재되었다. memory에 빈 공간이 없는 상황에서 w라는 page를 새롭게 적재해야한다.

 

FIFO 알고리즘은 가장 오래 전에 적재한 z를 w와 교체한다.

 

 

• Example
  • 초기 조건은 이전 예시와 동일하다.
  • Time 1 : 맨 처음 memory는 비어있으므로 1번은 그대로 memory에 적재한다.
  • Time 2 : 2번도 memory에 빈 공간이 있으므로 그냥 적재한다.
  • Time 3 : 6번도 memory에 빈 공간이 있으므로 그냥 적재한다.
  • Time 4 : 1번은 memory에 이미 있으므로 page fault가 발생하지 않는다.
  • Time 5 : 4번은 memory에 빈 공간이 있으므로 그냥 적재한다.
  • Time 6 : 5번을 memory에 적재해야하는데 빈 공간이 없다. 적재한 page(1, 2, 4, 6번) 중 가장 오래된 1번을 5번과 교체한다.
  • Time 7 : 1번을 memory에 적재해야하는데 빈 공간이 없다. 적재한 page(2, 4, 5, 6번) 중 가장 오래된 2번을 1번과 교체한다.
  • Time 8 : 2번을 memory에 적재해야하는데 빈 공간이 없다. 적재한 page(5, 1, 6, 4번) 중 가장 오래된 6번을 2번과 교체한다.
  • Time 9 ~ 11 : 1, 4, 5번은 memory에 이미 있으므로 page fault가 발생하지 않는다.
  • Time 12 : 6번을 memory에 적재해야하는데 빈 공간이 없다. 적재한 page(5, 1, 2, 4번) 중 가장 오래된 4번을 6번과 교체한다.
  • Time 13 : 4번을 memory에 적재해야하는데 빈 공간이 없다. 적재한 page(5, 1, 2, 6번) 중 가장 오래된 5번을 4번과 교체한다.
  • Time 14 : 5번을 memory에 적재해야하는데 빈 공간이 없다. 적재한 page(4, 1, 2, 6번) 중 가장 오래된 1번을 5번과 교체한다.
• Page fault는 총 10번 발생한다. 

 

 

FIFO 알고리즘을 사용했더니 page fault가 너무 많이 발생하게 된다. page fault를 줄이기 위해서는 어떻게 해야할까?

 

첫 번째로는 해당 프로세스에게 page frame을 더 많이 할당해주는 것을 생각해볼 수 있다. 하지만 과연 실제로 page frame을 더 할당해주면 page fault가 줄어들까?

 

새로운 예시를 진행해본 결과 page frame이 3개일 때는 page fault가 9번 발생하는데, page frame이 4개일 때는 page fault가 10번 발생해서 오히려 성능이 떨어지는 것을 확인할 수 있다.

이런 현상을 FIFO Anomaly 라고 한다.

 

 

LRU(Least Recently Used) Algorithm

 

• 가장 오랫동안 참조되지 않은 page를 교체 <- locality
• Page 참조 시 마다 시간을 기록해야 함 -> overhead 발생
• Locality에 기반을 둔 교체 기법
• Min Algorithm에 근접한 성능을 보여줌
• 실제로 가장 많이 활용되는 기법

 

 

3개의 page frame이 존재하고 memory에는 z, x, y 순으로 적재되었다. 이때 새로운 page w가 들어오면 어느 page와 교체를 해주어야 할까? 사실 이 정보만으로는 알 수 없다. z, x, y 순으로 적재가 되었지만 적재된 후에도 참조되었을 수도 있기 때문이다. 위 그림에서는 x가 가장 오래전에 참조했다면 x와 w를 교체하겠다고 한다.

 

 

• LRU Algorithm의 단점
  • 참조 시 마다 시간을 기록해야 함 (overhead 발생)
    • 간소화된 정보 수집으로 해소 가능
      • ex) 정확한 시간 대신, 순서만 기록
  • Loop 실행에 필요한 크기보다 작은 수의 page frame이 할당 된 경우, page fault 수가 급격히 증가함
    • ex) loop를 위한 |Reference string| = 4 / 할당된 page frame이 3개
      • page 1, 2, 3, 4가 있고 page frame A, B, C가 있고 1, 2, 3, 4가 반복해서 메모리에 적재된다고 해보자. 맨처음 page frame에는 1, 2, 3번이 들어오는데 4번이 들어오려면 1번과 교체해야한다. 그 다음에 1번이 들어오려면 2번과, 2번이 들어올 때는 3번과, 3번이 들어오려면 4번과 교체를 하면서 계속해서 page fault가 발생하게 된다.
    • Allocation 기법에서 해결해야 함. page frame이 부족하면 늘려주면 된다.

 

 

• Example
  • 초기 조건은 이전 예시와 동일하다.
  • Time 1 ~ 5 : 이전과 동일하다.
  • Time 6 : 5번이 들어와야하는데 memory에 빈 공간이 없다. memory에 적재된 page들(1, 2, 6, 4번) 중 가장 오래전에 참조한 2번과 5번을 교체한다.
  • Time 7 : 1번이 memory에 적재되어있으므로 page fault가 발생하지 않는다.
  • Time 8 : 2번이 들어와야하는데 memory에 빈 공간이 없다. memory에 적재된 page들(1, 5, 6, 4번) 중 가장 오래전에 참조한 6번과 2번을 교체한다.
  • Time 9 ~ 11 : 해당 reference string들(1, 4, 5)이 memory에 적재되어있으므로 page fault가 발생하지 않는다.
  • Time 12 : 6번이 들어와야하는데 memory에 빈 공간이 없다. memory에 적재된 page들(1, 5, 2, 4번) 중 가장 오래전에 참조한 2번과 6번을 교체한다.
  • Time 13 ~ 14 : 4번과 5번이 memory에 적재되어있으므로 page fault가 발생하지 않는다.
• Page fault는 총 7번 발생한다. Min algorithm(page fault 6번 발생)과 거의 유사한 성능을 보인다.