[운영체제-김덕수 교수님] 가상 메모리 관리(4/6) - 고정할당 시 교체 전략

메모리에 접근하면서 지역성이 왜 중요한지 예시를 통해 알아보고,
프로세스가 고정된 page frame 을 할당 받는 방식에서의 교체전략을 알아 보자.

목차.
1. 지역성
2. 교체 전략
    1. 고정 할당 방식
        1. MIN algorithm
        2. Random algorithm
        3. FIFO algorithm
        4. LRU (Least Recently Used) Algorithm
    2. 가변 할당 방식

---

1.Locality

• 가정
  • Paging system
  • Page size = 1000words
  • machine instruction size = 1 word
  • 주소 지정은 word 단위로 이루어짐
  • 프로그램은 4번 page 에 continuous allocation 됨
  • n = 1000
• 4번 페이지엔 코드가 들어있다
• 6번 페이지엔 Array A 의 값
  • 쉽게 말해서 6페이지엔 1000개의 요소가 들어가는데 1000개짜리 배열이 들어갔다고 보면 수월.
• 7번 페이지엔 Array B 의 값
• 8번 페이지엔 Array C 의 값
• 9번 페이지엔 one, n 이 있다
• 1 페이지당 1000word 라고 가정했으므로 주소의 첫의 자릿수가 페이지의 번호이다.

• for 문을 하나 도는 것을 예시로 들어 보자.
  • for 문이 1000번 도는 동안
  • 메모리 참조 횟수 = ω
  • 실제 참조한 page의 주소 = [4,6,7,8,9]

• ω 는 메모리를 참조한 횟수의 총합이다.
• 약 9000번의 메모리 참조 중에서
  5개의 page 만을 참조하였다.
  • Locality 를 활용

---

2. Replacement Strategies

• Fixed allocation
  • 프로세스가 메모리에 데이터를 적재시킬 때
  • 프로세스에게 고정된 숫자의 page가 할당되고,
  • 새로운 데이터 block 을 메모리에 적재해야하는 경우에는 기존에 있는 page frame 을 교체해야한다.
  • 이 교체하는 데 있어서 어떤 전략을 사용하는지 위주로 학습해보자.
    • Min algorithm, FIFO, LRU, LFU, NUR, Clock, etc...
• Variable allocation
  • 다음 시간에 학습해보자.

2-1. Min Algorithm(OPT algorithm)

y 의 페이지를 가장 마지막에 참조하므로 현재 메모리 상태에서 y page frame 을 교체

• 1966년 Belady 에 의해 제시
• Minimize page fault frequency(proved)
  • Optimal solution
• 기법
  • 앞으로 가장 오랫동안 참조되지 않을 page 교체
    • Tie-breaking rule: Page 번호가 가장 큰/작은 페이지 교체

• 실현 불가능한 기법(unrealizable)
  • page reference string 을 미리 알고 있어야함
• 교체 기법의 성능 평가 도구로 사용됨

 

메모리에서 현재 가지고 있는 프레임 중에 가장 마지막으로 보는 프레임을 교체하는 전략

한번 들어가보자. 
1 타임에 참조 1을 메모리에 올렸다. 빈 메모리였으니까 Page fault 가 발생하였다.
메모리 스테이트의 크기가 4이니까, 메모리 스테이트가 가득 차는 타임 5까지 page fault 가 총 4개 발생하였다. (1, 2, 6, 4)
자, 이제 6 타임에서 5를 올려야하는 데 어떤 pafe frame을 뺄 것인가?
1. 14 타임을 보니 5가 올라가는 데 현재 메모리 스테이트에 5가 없으므로 넘어간다.
2. 13 타임에 4가 있고 현재 메모리 스테이트에 4가 있으나, 10 타임에서 곧 요청할 것이므로 넘어가고,
3. 12 타임에 6이 가장 오래 요청이 되지 않는 page frame 이므로 [1,2,6,4] 에서 6을 빼고 그자리에 5를 집어넣어서 [1,2,5,4] 를 만든다.
4. page fault 수 = 4 + 1 = 5
5. 6에서 11 타임까지는 메모리 스테이트에 페이지 프레임을 들고 있으므로 그냥 넘어간다. 
6. 12타임에서 6을 올려야 한다. 
7. [1,2,5,4] 중  4,5 는 앞으로 참조 계획이 있다. 그러므로 교체될 프레임이 아니다.
1과 2 는 나중에 참조될 계획이 없다. 교체할 수 있는 프레임이다. 그렇다면 누구를 바꿔 줄 것인가? 
8. 여기서 등장하는게 Tie-breaking Rule 이다. 무승부일 때 누구를 선택할지 고르는 규칙이다.
9. 둘 중에 작은 수를 뺀다고 tie-breaking rule 을 정하고, 1을 뺀다. number of page fault = 6

보면 알겠지만, 앞으로 읽어 들일 모든 메모리가 언제 올라오고 무엇을 올릴지 알고 있어야한다. 
미래를 예견하는 장치를 인간은 만들 수 없다. 비현실적이란 말이다.
그래서 MIN 알고리즘은 성능 측정의 지표로 쓰이는 알고리즘이 되었다. 

2-2. Random Algorithm

• 무작위로 교체할 page 선택
• Low overhead
• No policy
• 또 다른 성능 평가의 기준이다.
  • "랜덤보다 떨어지는 알고리즘 왜 씀?" 이런 식이다.

2-3. FIFO Algorithm

• First In First Out
  • 가장 오래된 page 를 교체
• Page 가 적재된 시간을 기억하고 있어야 함
• 자주 사용되는 page 가 교체 될 가능성이 높음
  • Locality에 대한 고려가 없음
• FIFO abnomaly(Belady's anomaly)
  • FIFO 알고리즘의 경우, 더 많은 page frame 을 할당 받음에도 불구하고 page fault 의 수가 증가하는 경우가 있음

• 들어온 시간 순서대로 내보냈기 때문에, page fault = 10
• Min algo, 6 인데 반에 FIFO 는 더 주고도 10 이라서 안좋아 보인다.

2-4. LRU(Least Recently Used) Algorithm

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

Page Fault = 7, (min 6)

단점

• 참조 시 마다 시간을 기록해야함(overhead)
  • 간소화된 정보 수집으로 해소 가능
    • 예) 정확한 시간 대신, 순서만 기록
• Loop 실행에 필요한 크기보다 작은 수의 page frame 이 할당 된 경우, page fault 수가 급격히 증가함
  • 예) loop 를 위한 |Ref.string| = 4
    • 할당된 page frame = 3
      • page fault 가 우수수 나온다.
  • Allocation 기법에서 해결해야함
  • 조금 설명을 보태자면, for 문을 도는데 4 개의 Ref.string 을 할당해야한다. 이때 Page frame 을 3개만 주면,
    1,2,3 을 첫바퀴에 할당하고 다음 4를 할당하기 위해서 가장 오래된 1을 빼고 넣는다. 결과 [4,2,3].
  • 다음 바퀴에서 가장 오래된 2가 빠지고 [4,1,3] 이 된다.
  • 다음 순회에서 가장 오래된 3이 빠지고 [4,1,2] 가 된다.
  • 그 다음 순회에서 가장 오래전에 참조된 4가 빠지고 [3,1,2] 가된다..
    메모리 접근을 할때마다 Page fault 가 나는 것을 볼 수 있다.

 

결론.

1. 메모리 접근에서 지역성이 왜 중요한지 알아보았다.

2. 고정 할당 방식에서 교체할 page frame을 찾아내는 전략들을 알아보았다.