[OS] 페이지 교체 알고리즘

1. 지역성

• 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질
  • 프로세스는 최근에 참조한 데이터와 코드를 다시 참조하는 경향성이 있다!
• 90/10 규칙 - 경험적 관찰에서 나온 것으로, “프로그램 코드의 10 %에서 실행 시간의 90 % 소비”
• 현재 프로세스의 실행 패턴을 관찰하면, 가까운 미래에 프로세스의 코드와 데이터 사용을 합리적으로 예측 → 메모리 할당과 페이지 교체 전략에 활용
• 참조의 지역성
  • 공간 지역성
    • 가까운 데이터에 접근할 확률 > 먼 거리에 있는 데이터에 접근할 확률
  • 순차적 지역성
    • 여러 작업이 순서대로 진행되는 경향이 있음
  • 시간 지역성
    • 가까운 시간에 접근한 데이터 > 더 먼 시간에 접근한 데이터보다 사용될 확률

2. Working set(작업 집합)

• 일정 시간 범위 내에 프로세스가 액세스(참조)한 페이지들의 집합
• 작업 집합에 포함된 페이지들이 모두 메모리에 적재되어 있는 것이 프로세스 실행의 최고 성능
• 페이지 폴트는 작업 집합을 메모리에 적재하는 과정
• 참조의 지역성으로 인해 일정 시간 내에 작업 집합 형성
• 시간 범위가 클수록 작업 집합도 큼. 시간 범위를 얼마로 정할 것인가?
  • 참조의 지역성 → 페이지 폴트 → 메모리에 작업 집합 형성
  • 즉, 일정 실행시간동안 참조한 페이지의 집합이라고 할 수 있음!

2.1. Working set의 형성

2.2. Working set shift

• 프로세스가 실행되는 동안 작업 집합 이동
  • 시간이 지나면 새로운 작업 집합 형성

3. 페이지 교체(page replacement)

• 메모리 프레임 중 하나를 선택하여 비우고 이곳에 요청된 페이지를 적재하는 과정
  • 스왑 영역으로 보낼 페이지를 결정하는 알고리즘
  • 요청된 페이지가 메모리 프레임에 없고, 요청된 페이지를 적재할 빈 프레임도 없는 경우
• 페이지 폴트 핸들러에서 실행되는 작업
  • 희생 프레임(victim frame)
    • 비우기로 선택된 프레임
  • 희생 페이지(victim page)
    • 희생 프레임에 들어 있는 페이지
  • 희생 페이지는 스왑-아웃, 요청 페이지는 스왑-인
• 현재 작업 집합에 포함되지 않거나 가까운 미래에 참조되지 않을 페이지를 희생 페이지로 선택
  • 페이지 폴트 횟수 줄임

3.1. 희생 프레임 선택 범위

• 지역 교체(local replacement)
  • 프로세스 별로 독립적으로 페이지 폴트 처리
  • 요청한 프로세스에게 할당된 프레임 중에서 희생 프레임 선택: per-process replacement
  • 한 프로세스에서 발생한 스래싱이 다른 프로세스로 전파되지 않음
    • 스레싱에 대한 대책으로 적합
• 전역 교체(global replacement)
  • 전체 메모리 프레임 중에서 선택
  • 지역 교체보다 더 효과적인 것으로 평가
  • 리눅스, Windows 등 많은 운영체제에서 사용
  • 캐시 히트율이 더 높은 것으로 밝혀짐
• 여담
  • 객체지향 프로그래밍은 참조 지역성이 많이 떨어짐
  • working set을 찾기 어려움 -> 하지만 거시적으로 볼 땐 찾을 수 있음

4. 페이지 교체 알고리즘 종류

• 성능 평가 기준
  • 같은 메모리 접근 패턴을 사용하여 부재 횟수와 페이지 성공 횟수 비교

4.1. 최적 페이지 교체 알고리즘

• 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮김
• 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시 점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정
• 페이지 폴트 횟수: 5 / 성공 횟수 : 5
• 이상적인 방법이지만 실제로 구현할 수 없음

4.2. 무작위 페이지 교체 알고리즘

• Random page replacement algorithm
• 스왑 영역으로 쫓아낼 대상 페이지를 특별한 로직 없이 무작위로 선정
• 지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정되기도 하여 성능이 좋지 않음

4.3. FIFO

• 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑영역으로 쫓아냄
• 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들이 위쪽으로 이동하며, 새로운 페이지가 아래쪽의 남은 공간에 들어옴
• 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어짐
• 페이지 폴트 횟수: 7 / 성공 횟수 : 3

4.4. Second chance algorithm

• FIFO의 변형
• FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용
• 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외 → “기회를 한번 더 준다”
  • 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 줌
• 페이지 폴트 횟수: 6 / 성공 횟수 : 4

4.5. Clock algorithm

• FIFO의 변형: 기본적으로 FIFO이지만, 1이라면 reference bit를 0으로 세팅하고 기회를 줌.
  • 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용
• 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용 → 원형큐를 따라 이동
  • 페이지가 참조될 때마다 참조비트를 1로 셋
  • 참조 비트가 0이면, 그 프레임을 희생 프레임으로 선택
  • 참조 비트가 1이면, 0으로 바꾸고 다음 프레임으로 이동
• 한 바퀴를 돌게 되면 처음 프레임 선택
  • 이게 너무 많이 돌아가면, 페이지 적재율이 많다는 것

• 2차 기회 페이지 교체 알고리즘에 비해 각 페이지에 참조 비트가 하나씩 추가
• 참조 비트의 초깃값은 0, 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경
• 대상 포인터는 메모리가 꽉 찰 경우 스왑 영역으로 쫓겨날 페이지를 가리킴
• 가리키는 페이지가 스왑 영역으로 쫓겨 나면 대상 포인터를 밑으로 이동하는데 이때 참조 비트가 1인 페이지는 0으로 만든 후 건너 뜀(2차기회를 줌)
• 페이지 폴트 횟수: 6 / 성공 횟수 : 4

4.6. LRU와 LFU

• 최적 근접 알고리즘의 접근방식
• 실제 구현이 가능하면서도 성능이 최적 근접 알고리즘에 근접한 알고리즘
• LRU 페이지 교체 알고리즘: Least Recently Used
  • 페이지에 접근한 시간을 기준으로 대상 페이지를 선정
• LFU 페이지 교체 알고리즘: Least Frequently Used
  • 페이지가 사용된 횟수를 기준으로 대상 페이지를 선정

4.7. LRU

• 최근 최소 사용 페이지 교체 알고리즘
  • 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮김
  • 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정
• 페이지 폴트 횟수: 6 / 성공 횟수 : 4

4.7.1. LRU 구현

• 시간 값 저장은 어떻게 구현하는 것인가? 2가지 방법이 있음
  1. 타임 스탬프 이용
  • 모드 프레임에 참조 시간을 기록할 수 있는 비트 추가
  • CPU가 페이지를 참조할 때마다 참조 시간 기록
  • 희생 페이지를 선택할 때, 참조 시간이 가장 오래된 것 선택
  • 시간 기록 및 참조 시간 검사에 많은 오버헤드 2. 참조 비트 시프트 사용
  • 누가 상대적으로 오래됐는지만 알면 됨. 절대 시간은 중요하지 않음: 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것
  • 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀜
  • 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동
  • 참조 비트를 갱신 하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정

4.8. LFU

• 페이지가 몇 번 사용 되었는지를 기준으로 대상 페이지를 선정
• 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮김
• 페이지 폴트 횟수: 5 / 성공 횟수 : 5
  • 우연히 이상적인 경우와 일치한 경우로 가장 좋다는 건 아님

4.9. NRU(NUR)

• NRU, NUR: 최근 미사용 페이지 교체 알고리즘
• LRU, LFU 페이지 교체 알고리즘은 성능은 좋으나 추가적인 오버헤드가 큼!
• 이를 개선한 NRU는 두 개의 비트만으로 구현 가능 → 페이지마다 참조 비트와 변경 비트를 가짐
  • 참조 비트 : 페이지에 접근(read/execute)하면 1이 됨
  • 변경 비트 : 페이지가 변경(write/append)되면 1이 됨
  • 모든 페이지의 초기 상태는 (0,0), 모든 값이 (1,1)이면 초기화
• “최근에 사용되지 않은 페이지는 이후에도 사용되지 않을 가능성이 높다”
  • 최근에 몇번을 참조 했는가는 의미 없음.
  • LRU처럼 가장 최근에 참조되지 않은 페이지를 선택하지만 교체되는 페이지의 참조 시점이 가장 오래되었음을 보 장하지 않음

• 대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾음
• 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정
• 페이지 폴트 횟수: 5 / 성공 횟수 : 5

5. Thrashing(스레싱)

• 메모리 공간(프레임)이 절대적으로 부족해서 계속 fault만 난다면요?
  • 아마 연달아서 page fault가 계속 날겁니다.
  • page fault를 처리하는 것도 엄연히 어느정도 비용(시간)이 드는 작업…!
  • 그리고 page fault가 처리되는 동안에는 CPU는 놀고있겠죠!
  • 왜냐? 얘는 MMU가 처리해주는 작업이니깐!
• Page fault로 인해 CPU가 이용률이 떨어지면…
  • CPU는 “할 일이 많이 없나?” 라고 생각해서 할 거를 더 찾습니다
  • 그래서 프로세스를 메모리로 추가로 가져오죠
  • 그런데 page fault가 일어나는 원인을 생각해보면….
    • 해당 페이지가 메모리에 없어서 → 왜 없지? → 충분히 프레임을 할당 못받아서… ⇒ 즉, 메모리가 부족하단 말
  • 메모리가 부족한데 프로세스를 메모리에 더 가져온다? → 메모리가 더 부족해진다 → 부족해지면 충분한 프레임을 확보 못하니 page fault가 더 빈번해지게 된다 → CPU는 더 논다 → 더 프로세스를 메모리로 가져온다. → 반복!
  • 이것이 바로 스레싱 Thrashing: 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태

5.1. 스레싱 발생 시점

• 다중프로그래밍 정도(DOM)가 높아질수록 자연스러운 CPU 활용률 증가
• 다중프로그래밍 정도(DOM)가 임계점 M을 넘어가면 스래싱 발생
  • CPU 활용률 급감. I/O비율 급상승
  • CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리에 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 되는 시점
• 물리 메모리의 크기를 늘리면 스레싱 발생 지점이 늦춰짐.

5.2. 해결 방법

5.2.1. 물리적 방법

• 다중프로그래밍 정도(DOM) 줄이기 → 몇몇 프로세스 종료
• 하드 디스크 대신 빠른 SSD 사용
• 메모리 늘리기

5.2.2. 기술적 방법

• 프로세스에 너무 적은 프레임을 할당하면 페이지 부재가 빈번히 일어남
• 프로세스에 너무 많은 프레임을 할당하면 페이지 부재는 줄지만 메모리가 낭비됨
• 따라서, 프로세스별로 적당히 잘 할당 하는 것이 굉장히 중요한 문제
  • 프레임 할당 문제!

6. 프레임 할당 문제

• 프레임 할당(frame allocation) 알고리즘
  • 프로세스당 할당할 프레임의 개수를 결정하는 문제
  • 프로세스에게 작업 집합에 포함된 페이지들을 적재할 충분히 메모리 할당
    • 페이지 폴트를 줄이기 위해 and 스레싱 예방

6.1. 프레임 할당 방법: 정적 할당

• 균등 할당(equal allocation)
  • 프로세스에게 크기와 관계없이 동일한 개수의 프레임 할당
  • 장점: 단순
  • 단점: 작은 프로세스에게는 프레임 낭비, 큰 프로세스는 빈번한 페이지 폴트 발생 가능

• 비례 할당(proportional allocation)
  • 프로세스의 크기와 비례하여 프레임 할당
  • 장점: 많이 필요한 프로세스에게 많은 프레임을 할당함으로써, 전체적으로 페이지 폴트의 수를 줄임
  • 단점: 프로세스의 크기는 실행 중에 완벽히 알기 쉽지 않음. 실행 중에 작업 집합을 판단할 필요. 낭비도 있을 수 있음.

6.2. 프레임 할당 방법: 동적 할당

6.2.1. 프레임 동적할당 모델: Working set model

• 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고, 이 집합에 있는 페이지들을 물리 메모리에 유지
  • 작업집합 크기
    • 작업집합 모델에서 물리 메모리에 유지할 페이지 크기
  • 작업집합 윈도우
    • 작업집합에 포함되는 페이지 범위
  • 윈도우의 크기가 프로세스 성능에 영향을 미침!
• 델타 동안 참조된 10개의 페이지 중 작업집합에는 $WS(t1)={1, 7, 5, 2, 3}$이 삽입되며, 이 페이지들은 다음번 윈도우에 도달할 때까지 물리 메모리에 보존

6.2.2. 프레임 동적할당 모델: Page fault frequency

• Working set model의 델타를 결정하는 알고리즘
• 페이지 부재 횟수를 기록하여 페이지 부재 비율을 계산하는 방식
• 페이지 부재 비율이 상한선을 초과하면 프레임을 추가하여 늘림: 델타 증가
• 페이지 부재 비율이 하한선 밑으로 내려가면 할당한 프레임을 회수: 델타 감소
• 페이지 부재 빈도 방식은 프로세스를 실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절

6.3. 프로세스 당 필요한 최소 프레임 개수

• 한 명령이 처리되는데 필요한 페이지의 개수
  • CPU 명령어의 주소 모드(addressing mode)에 달려 있음
• 주소 모드에 따라 한 명령이 처리되는데 필요한 페이지의 개수 계산
  • mov eax, 23
    • 최소 1개의 페이지(코드 자체에 대한 1페이지)
  • mov eax, [mem_addr]
    • 최소 2개(코드 자체에 대한 1 페이지 + 데이터 1 페이지)
  • mov eax, [[mem_addr] + 5000]
    • 최소 3개(코드 자체에 대한 1 페이지 + [mem_addr] 페이지 1 + [[mem_addr] + 5000] 페이지 1)

지극히 이론적인 페이지 개수를 의미하고 실제에선 모름

6.4. 프로세스에게 할당할 적정 프레임의 개수

• 작업 집합을 약간 넘나드는 크기