Computer Science/OS

가상 메모리 | 페이지 교체 알고리즘

물리 water lee 2024. 9. 20. 10:53

가상 메모리 이전 내용

 

가상 메모리

👩🏻‍💻 학습 목표스와핑이 무엇인지 이해하기연속 메모리 할당 기법과 외부 단편화 문제 이해하기가상 메모리 관리 기법인 페이징의 개념과 작동을 이해하기요구 페이징의 개념과 페이지

water-lee.tistory.com

 

3. 페이지 교체와 프레임 할당

 

가상 메모리를 통해 작은 물리 메모리보다 큰 프로세스도 실행할 수 있다고는 하지만, 글머에도 불구하고 여전히 물리 메모리의 크기는 한정되어 있음.

 

운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록

기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보낼 수 있어야 하고,

프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 해야함.

 

1) 요구 페이징

📌 요구 페이징 demand paging

프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법.

이름 그대로, 실행에 요구되는 페이지만 적재.

 

  1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
  2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
  3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다.
  4. 페이지 폴드 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
  5. 다시 1번을 수행한다.

✅ 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 할 수도있음. = 순수 요구 페이징 pure demand paging 기법

➡ 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생 ➡ 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도 감소

 

📌 요구 페이징이 안정적으로 작동하기 위해 두 가지 해결해야함

  1. 페이지 교체
  2. 프레임 할당

 

 

페이지 교체

요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득 차게 됨.

당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 함.

메모리에 적재된 많은 페이지 중 어떤 페이지를 내보내는 것이 최선일까?

이를 결정하는 방법 = 페이지 교체 알고리즘

 

2) 페이지 교체 알고리즘

좋은 페이지 교체 알고리즘 = 페이지 폴트를 가장 적게 일으키는 알고리즘

  • 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려짐

페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수을 알 수 있어야 함. ➡ 페이지 참조열 page reference string을 통해 알 수 있음.

 

CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미.

 

[예시]

CPU가 아래와 같은 순서로 페이지에 접근

2 2 2 3 5 5 5 3 3 7

연속된 페이지를 생략한 페이지열

2 3 5 3 7

 

연속된 페이지를 생략하는 이유? 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문.

(CPU가 특정 페이지에 열 번 연속으로 접근한다고 해서 한 번 접근하는 것보다 페이지 폴트가 많이 발생하지 않는 것처럼)

 

 

1️⃣ FIFO 페이지 교체 알고리즘; First-In First-Out Page Replacement Algorithm.

메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식

오래 머물렀으면 나가게 하는 알고리즘

 

 

페이지가 초기에 적재될 때 발생할 수 있는 페이지 폴트는 고려하지 않고, 적재된 페이지를 교체하기 위해 발생한 페이지 폴트만을 페이지 폴트로 간주.

 

아이디어와 구현이 간단하지만, 마냥 좋은 것은 아님.

프로그램 실행 초기에 적재된 페이지 속에는 프로그램 실행 초기에 잠깐 실행되다가 이후에 사용되지 않을 페이지도 있겠지만, 프로그램 실행 내내 사용될 내용을 포함할 수도 있음. ➡ 이런 페이지는 메모리에 먼저 적재되었다고 해서 내쫓아서는 안 됨.

 

2️⃣ 최적 페이지 교체 알고리즘 Optimal Page Replacement Algorithm

CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘

앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘

 

메모리에 오랫동안 남아야 할 페이지 = 자주 사용될 페이지

메모리에 없어도 될 페이지 = 오랫동안 사용되지 않을 페이지

오랜 기간 메모리에 있었던 페이지 != 쫓아낼 페이지

 

보조기억장치로 내보내야 할 페이지 = 앞으로 사용 빈도가 가장 낮은 페이지

 

 

낮은 페이지 폴트율을 보장하는 알고리즘 ➡ 타 페이지 교체 알고리즘에 비해 페이지 폴트 발생 빈도가 가장 낮음

 

단점 : 구현이 어려움

"앞으로 오랫동안 사용되지 않을 페이지"를 예측하기 어려움.

프로세스가 앞으로 메모리 어느 부분을 어떻게 참조할지 미리 알아야 하는데, 이는 현실적으로 불가능에 가깝기 때문.

 

따라서 최적 페이지 교체 알고리즘은 그 자체를 운영체제에서 사용하기 보다는, 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용함.

 

 

즉, 최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 페이지 폴트의 하한선으로 간주하고,

최적 페이지 교체 알고리즘에 비해 얼만큼 페이지 폴트 횟수가 발생하느냐를 통해 페이지 교체 알고리즘을 평가하기 위해 사용함.

 

3️⃣ LRU 페이지 교체 알고리즘 Least Recently Used Page Replacement Algorithm

가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘.

 

LRU 페이지 교체 알고리즘은 "최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것"이라는 아이디어를 토대로 만들어진 알고리즘.

페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체.

 

 

이 외에도 페이지 교체 알고리즘 종류는 매우 다양하다.

(초보는 페이지 교체 알고리즘의 사용 이유, 페이지 교체 알고리즘 별 아이디어와 장점을 이해하는데에 중점)

 

3) 스래싱과 프레임 할당

페이지 폴트가 자주 발생하는 이유

  • 나쁜 페이지 교체 알고리즘
  • 프로세스가 사용할 수 있는 프레임 수가 적음

 

프로세스가 사용할 수 있는 프레임 수가 많으면 일반적으로 페이지 폴트 빈도는 감소

프레임 수가 부족하면 CPU는 페이지 폴트가 자주 발생할 수 밖에 없음.

실행의 맥이 탁탁 끊기고, 결과적으로 CPU의 이용률도 떨어짐.

CPU가 쉴새 없이 프로세스를 실행해야 컴퓨터 전체의 생산성도 올라갈 텐데, 페이지 교체에 너무 많은 시간을 쏟으면 당연히 성능에도 큰 악영향이 초래됨.

이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱 thrashing이라고 함.

 

스래싱 Thrashing

📌 스래싱이란 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제를 말함.

 

 

CPU 이용률이 높을수록 CPU가 쉴새 없이 일하고 있다는 말.

멀티프로그래밍의 정도가 높을 수록 메모리에 올라와 있는 프로세스의 수가 많다는 것을 의미.

 

메모리에서 동시 실행되는 프로세스의 수를 멀티그래밍의 정도 degree of multiporgramming이라고 함.

 

필요 이상으로 프로세스 수가 증가하면,

각 프로세스들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 지나치게 빈번히 발생함.

➡ CPU 이용률이 떨어져 전제적인 성능이 저해됨.

 

아무리 CPU의 성능이 뛰어나도 동시에 실행되는 프로세스를 수용할 물리 메모리가 너무 작다면,,,

➡ 전체 컴퓨터의 성능이 안 좋아지는 이유

 

📌 스래싱 발생 근본 원인 = 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문.

➡ 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수 만큼 프레임을 할당해 줄 수 있어야 함.

 

프레임 할당 방식

  1. 정적 할당 방식
    1. 균등 할당 equal allocation
      • 모든 프로세스에 동일한 프레임을 배분하는 방식
      • 지양
      • 실행되는 프로세스들의 크기는 각기 다른데, 동일한 프레임을 할당하는 건 비합리적
    2. 비례 할당 proportional allocation
      • 프로세스 크기에 따라 프레임을 배분하는 방식
      • 완벽하지는 않음
        • 프로세스의 크기가 클지라도 막상 실행해보니 많은 프레임을 필요로 하지 않는 경우도 있음.
        • 프로세스의 크기가 작아도 실행해보니 많은 프레임을 필요로 하는 경우도 있음
        • 즉, 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 아는 경우가 많음
  2. 동적 할당 방식
    1. 작업 집합 모델 working set model 기반 프레임 할당
      • 작업 집합의 크기만큼만 프레임을 할당하는 방식
      • 프로세스가 일정 기간 동안 차좀한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지함.
      • CPU가 메모리를 참조할 때는 참조 지역성의 원리에 의거해 주로 비슷한 구역을 집중적으로 참조함(참조 지역성의 원리)
        • CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 페이지 교체는 빈번하게 발생하지 않음.
        • 만약, CPU가 어떤 프로세스를 실행하는 동안 3초에 일곱 개의 페이지를 집중저긍로 참조했다면 운영체제는 그 프로세스를 위해 그 순간만큼은 최소 일곱 개의 프레임을 할당하면 됨.
      • 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합 = 작업 집합 working set
      • CPU가 과거게 주로 참조한 페이지를 작업 집합에 포함한다면 운영체제는 작업 집합의 크기만큼만 프레임을 할당해 주면 됨.
      •  
      • 더보기
        작업 집합 구하기
    2. 페이지 폴트 빈도 PFF; Page-Fault Frequency 기반 프레임 할당
      • 페이지 폴트율에 상한선과 하한선을 정하고, 이 범위 안에섬나 프레임을 할당하는 방식
      • 2개의 가정
        • 페이지 폴트율이 너무 높으면, 그 프로세스는 너무 적은 프레임을 갖고 있다.
        • 페이지 폴트율이 너무 낮으면, 그 프로세스는 너무 많은 프레임을 갖고 있다.
      • 임의로 페이지 폴트율의 상한선과 하한선을 그어보기.
        • 만일 페이지 폴트율이 상한선보다 더 높아지면
          ➡ 그 포로세스는 너무 적은 프레임을 갖고 있다고 볼 수있음 ➡ 프레임 더 할당
        • 페이지 폴트율이 하한선보다 더 낮아지면
          ➡ 그 프로세스는 너무 많은 프레임을 갖고 있음 ➡ 프레임 회수

 

📌 키워드 정리

  • 요구 페이징은 페이지가 필요할 때에만 메모리에 적재하는 기법.
  • 페이지 교체 알고리즘에는 FIFO, 최적, LRU 페이지 교체 알고리즘 등이 있습니다.
  • 스래싱이란 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제를 뜻함.
  • 프레임 할당 방식에는 균등 할당과 비례 할당, 작업 집합 모델 기반과 페이지 폴트율 기반 프레임 할당 방식이 있다.

 

[참고]

  • 균등 할당, 비례 할당 방식은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고려한 방식이라는 점에서 정적 할당 방식이라고도 함
  • 작업 집합 모델과 페이지 폴트 빈도를 사용하는 방식은 프로세스의 실행을 보고 할당할 프레임의 수를 결정한다는 점에서 동적 할당 방식이라고 함.

 

[내용 출처]

https://www.youtube.com/watch?v=isj4sZhoxjk&t=1s

 

 

 

저작자표시 비영리 변경금지 (새창열림)