[ OS ] 17. 메모리 관리 전략 - 가상 메모리 Paging(페이지 교체 알고리즘)과 Thrasing(쓰레싱)

페이지 교체 알고리즘

페이지 부재 발생 → 새로운 페이지 할당 해야함 → 현재 할당된 페이지 중 어떤 것을 교체할 지 결정하는 방법

위 그림은 페이지 교체가 필요한 상황을 보여준다.

현재 1번 프로세스가 가리키고 있는(PC)가 B 페이지는 Page-Out되어 있는 상태고 Storage에서 B라는 페이지를 가져오려고(스와핑 시도) 하는데, 현재 physical memory에 자리가 없다(no free frame). 이 때 어떤 프로세스를 교체해야 가장 효율적으로 교체할 수 있을까?
→ 페이지 교체 알고리즘 필요

victim(페이지 out의 대상)을 하나 정하고, victim이 있으면 page out - page in 시킨다.

그러면 어떤 Victim을 선택해야 효율적인가?

→ Secondary Storage I/O는 매우 시간이 많이 걸리기 때문에 이를 효율적으로 선택해야 시스템 효율이 증가한다.
→ 기왕이면 수정이 되지 않는 페이지를 선택하는 것이 좋다.

• Page reference string (참조 문자열)
  • CPU는 논리 주소를 통해 특정 논리 주소를 요구한다.
  • 메인 메모리에 있는 주소들은 페이지의 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 결함이 발생하지 않는다.
  • 따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 Page Reference String이다.
  • 이을 가지고 page faults의 개수를 계산한다.(frame이 많으면 많을수록 page faults는 적어진다.)
    (ex. 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1)

- FIFO

Fisrt-In Fisrt-Out

과거를 바라본다.

• 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
• 가장 오래된 페이지를 교체한다.
• 초기화 코드에서 적절한 방법이다.
• 장점
  • 구현하기도 쉽다.
• 단점
  • Belady's Anomaly가 발생한다.
  • page frame의 개수를 늘리면 늘릴수록 page faults가 줄어야 하는데 오히려 늘어나는 현상

- OPT

Optimal

미래를 바라본다.

• 앞으로 가장 사용하지 않을 페이지를 먼저 내보내는 알고리즘
• FIFO에 비해 결함의 횟수를 많이 감소시킬 수 있다.
• 하지만, 실질적으로 futrue knowledge가 필요하기 때문에, 단지 논리적으로만 최적의 알고리즘이다.

- LRU

Least Recently Used

과거 + 미래

• 최근에 사용하지 않았으면 나중에도 사용되지 않을 것이라는 아이디어이다.

• 실직적으로 사용이 가능한 알고리즘

• 최근 가장 오래동안 사용(참조되지)하지 않은 페이지를 내보낸다.

• OPT보다는 페이지 결함이 더 일어날 수 있지만, 실질적으로 가장 좋은 방법 중 하나이다.

• 단점

  • 해당 프레임이 언제 마지막으로 사용되었는가 알아야 하지만 그 계산하는 데 비용이 많이 든다.
  • 그래서 하드웨어 지원이 받는 것이 쉽지 않다..

• Counter implementation

  • 페이지가 참조될 때 counter(or clock)을 copy해서
  • 가장 낮은 값을 가진 페이지를 교체한다.

• Stack implementation

  • page number를 스택으로 구현

- LRU Approximation

LRU 근사 페이지 교체

• LRU 알고리즘을 소프트웨어로 구현하는 것은 비용이 너무 많이 들고, 하드웨어 도움을 받아야 하지만 그것이 쉽지많은 않다.
• 따라서 하드웨어의 지원없이 reference bit 이용해서 구현하는 알고리즘이다.

1. Additional-Reference-Bits Algorithm
   • Page Table 내 각각의 Page에 8비트 짜리 참조 비트가 존재해서 일정 시간의 간격마다 Access 되었던 페이지들의 비트들을 오른쪽으로 Shift하는 연산을 수행한다.
   • 그러면 가장 큰 값의 비트를 가진 페이지가 최근에 Access되었다는 것을 알 수 있다.
   • 또한 가장 작은 값의 비트를 가진 페이지들이 Victim Page로 선택이 되면서 같은 값에 대해서는 FIFO 알고리즘을 이용해 Victim을 선정한다.
2. Second-Chance Algorithm
   • 말 그대로 한번의 기회를 더 준다.
   • Page Table의 각각의 Page 에는 1비트 짜리 Reference Bit가 존재하고 초기값은 모두 0이며 Access가 되면 1로 바꾼다
   • FIFO 알고리즘을 기반으로 하기 때문에 Reference Bit가 1이어도 선택이 될 수 있는데, 이 때 만일 Reference Bit가 1이면 최근에 Access되었다는 것으로 간주하여 0으로 바꾼 후, 한 번의 기회를 더 주고 다른 Victim Page를 찾는다.
   • Reference Bit가 1이면 한번 봐주고 Reference Bit가 0이면 (그 다음에도 참조가 되면) Victim으로 선정한다.
   • 시계 방향으로 탐색하며 원형의 구조를 생각할 수 있어서 Clock Algorithm 이라고도 한다.
3. Enhanced Second-Algorithm
   • Reference Bit와 Modify Bit를 이용해서 Victim Page를 찾는다.
   • 해당 부분 내의 값이 바뀌면 Modify Bit를 1로 바꾸어준다.
   • Reference Bit와 Modify Bit가 둘 다 1이라는 뜻은 최근에 Access되고 값의 변화가 있으므로 다시 선택될 가능성이 높다는 뜻이고, Victim Page로는 적절하지 않다는 의미이다.
   • 하지만 모든 Page Table을 전부 뒤져야 한다는 단점이 존재한다.

- Counting Algorithm

카운팅 알고리즘은 일반적으로 잘 사용되지 않는다.

구현하는데 많은 비용이 들고 최적 페이지 교체 정책을 제대로 근사하지 못하기 때문이다.

- LFU

Least Frequently Used

Counting Based Algorithm

• 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘
• 활발히 사용되는 Page는 큰 참조 값을 가지게 될 것이고 교체될 가능성이 적다고 판단한다.
• 하지만 초기에는 많이 사용되고 나중에는 많이 사용되지 않는다면 문제가 된다.
• 해결책으로 참조 횟수를 일정한 시간마다 하나씩 오른쪽으로 이동해서 지수적으로 그 영향력을 감소시키는 방법이 있다.

- MFU

Most Frequently Used

Counting Based Algorithm

• 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
• 가장 작은 참조회수를 가진 페이지가 가장 최근에 참조된 것이고 앞으로 사용될 것이라는 아이디어.

Frame Allocation Issue

128frame 중에 35 frame을 사용하고, 93frame이 남았다고 생각하자.

그러면 93 page faults가 일어나서 93 frame이 다 차고, 94번째 page faults가 일어났다고 가정하자.

근데 두개의 프로세스가 있는데 어떤 프로세스에게 프레임을 더 많이 줘야하나?

N개의 프로세스가 존재할 때 M개의 프레임이 주어지면 어떻게 할당할 것인가? 라는 문제가 존재한다.

• Equal vs Proportional
  • 모든 프로세스에게 동등하게 줄것이냐 vs 프로세스 사이즈가 큰, 많이 필요한 애한테 많이 줄거냐ㅑ
• Global vs Local
  • 자기 victim을 global하게 할당할 것이냐, 자기 victim을 자기 껄로 정할거냐,
  • Global : 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식 (실제로 Local보다 효율이 좋다)
  • Local : 메모리 상의 자기 프로세스 페이지에 대해서만 교체하는 방식

Thrashing

스레싱

page fault가 빈번하게 발생하여, 페이지 교체하는(page-in , page-out) 시간이 많아지는 현상

• 어떤 프로세스가 busy swapping page in and out 상황에 있을 때 (swapping하느라 너무 바쁠때)
• 프로세스가 충분한 페이지를 가지고 있지 못한다면
  • page-fault 비율이 매우 높을때
  • = 멀티 프로그래밍의 정도가 매우 높아 질 때 (degree of Multiprogramming)
• 어느 시점에서 CPU Utilization이 급격히 하락한다.
• ex. 프로세스가 100개인데 페이지가 100개이다. CPU는 놀고 있는데 프로세스는 스와핑하느라 너무 바쁜 상태
• 해결방법
  • 메인 메모리를 늘려준다. (physical memory가 부족해서 나타나는 현상이기 때문에)
  • 하드디스크를 SSD로 바꿔준다.

< Working-Set Model >

• 위 그림과 같이 한군데만 막 집중적으로 참조(참조 지역성)하다가 텅 빈 공간이 생기게 된다.
• 그럼 인접한 곳(가장 많이 쓰이는 곳) 계속 메모리에 상주시켜 스레싱을 줄일 수 있다.
• 워킹셋 윈도우에 해당하는 페이지들은 Victim으로 선정하지 않는다.
• Working Set
  • 메모리에 한꺼번에 올라가 있어야 하는 페이지들의 집합
• Working Set Window
  • 워킹셋 윈도우를 주로 델타로 나타내고, 이는 고정되어 있다.
• Working Set Size
  • 각 프로세스 별로 가장 많이 쓰이고 있는 페이지의 개수

이 워킹셋 속한 페이지들은 가장 최근에 참조된 페이지들의 집합이기 때문에
만약에 해당 페이지가 사용중이라면, 해당 페이지는 워킹셋에 속해 있을 것이고
만약에 해당 페이지가 더이상 사용중이지 않다면, 워킹셋 바깥에 있을 것이기 때문에, 바깥에 있는 페이지들을 Victim으로 선정한다.

왼쪽 그림과 같이 워킹셋 윈도우가 10으로 고정되어 있으면, t1 에서 워킹셋은 {1, 2, 5, 6, 7}이고, 워킹셋 사이즈는 5이다.

오른쪽 그림과 같이 워킹셋 윈도우가 10으로 고정되어 있으면, t2에서 워킹셋은 {3, 4}이고, 워킹셋 사이즈는 2이다.

각 프로세스의 워킹셋 사이즈 총합을 D라고 하면
D : 현재 각 프로세스가 필요로 하는 전체 프레임의 개수
m : physical memory의 크기 일때

D > m 이면 스레싱이 발생하므로 D가 m보다 작도록 계속 유지해야 스레싱이 발생하지 않는다.

=> 따라서 Working Set Model은 Thrashing 문제를 해결할 수 있는 모델이다.

< PFF >

Page Fault Frequency

Page-Fault의 빈도를 조절하는 방법으로 페이지 폴트가 적당한 범위 기준 내에서 발생하도록 유지하는 방법이다.

• page fault 발생 횟수가 상한선을 초과한다면
  • 프레임 할당이 너무 적다는 것을 의미하므로
  • 프레임을 추가하여 늘려준다.
• page fault 발생 횟수가 하한선 미만이라면
  • 프레임 할당이 너무 많아 메모리 낭비 중인 것을 의미하므로
  • 프레임을 회수하여 줄여준다.