[운영체제]페이지 교체 알고리즘

페이지 교체 알고리즘

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

• 좀 더 자세하게 생각해보면?

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둠

하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있음

따라서 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 함

여기서 어떤 페이지를 out 시켜야할 지 정해야 함. (이때 out 되는 페이지를 victim page라고 부름)

기왕이면 수정이 되지 않는 페이지를 선택해야 좋음
(Why? : 만약 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 진행해야 하므로 시간이 오래 걸림)

이와 같은 상황에서 상황에 맞는 페이지 교체를 진행하기 위해 페이지 교체 알고리즘이 존재하는 것!

Page Reference String

CPU는 논리 주소를 통해 특정 주소를 요구함

메인 메모리에 올라와 있는 주소들은 페이지의 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 페이지 결함 발생 X

따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 바로 Page Reference String

1. FIFO 알고리즘

   First-in First-out, 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘

   victim page : out 되는 페이지는, 가장 먼저 메모리에 올라온 페이지

   가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법임

   초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮음

   하지만 처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능함

2. OPT 알고리즘

   Optimal Page Replacement 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄

   FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있음

   하지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘임

   

3. LRU 알고리즘

   Least-Recently-Used, 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘

   최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나옴

   OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘

   (실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다)

   OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나임

   
   이렇게 페이지 스왑이 많아지게 되면

스레싱

Thrashing이란 사용하는 프로세스가 많아질 때 어느 한계점 까지는 CPU이용율이 증가하다가 한계점 이상부터는 CPU 이용율이 떨어지게 되는데 이 때 사용량이 떨어지는 이유 중 하나가 스레싱 때문이다.

스레싱(Thrashing)이란 페이지 부재율(Page fault)이 증가하여 CPU 이용율이 급격하게 떨어지는 현상을 얘기한다. 스레싱이 발생하는 이유는 프로세스를 처리하는 시간보다 메모리에 적재되지 못한 페이지로 인하여 페이지 교체에 드는 시간이 증가하게되고 그로 인해 CPU이용률이 떨어지게 된다.

운영체제는 CPU 이용율이 낮으면 메모리에 동시에 올라가 있는 프로세스의 수인 MPD(다중 프로그래밍의 정도, Multi-Programming Degree)를 높이게 되는데 동시에 실행하는 프로세스가 많아질 수록 각 프로세스에 할당된 메모리 페이지 프레임들은 더욱 작아지게 된다. 너무 적은 페이지 프레임을 할당받은 프로세스들은 페이지 부재가 증가하게되어 Swapping이 증가하게 되고 결국 CPU의 이용율이 더욱 떨어지는 악순환이 생기게 된다.

스레싱이 발생하는 일반적인 상황

스래싱은 일반적으로 1. 시스템 메모리가 충분하지 않거나, 2. 시스템 스왑 파일이 제대로 구성되지 않았거나, 3. 너무 많은 백그라운드 서비스가 실행 중이거나, 4. 동시에 여러 프로그램이 실행 중일 때 발생합니다.

이 경우, 시스템 메모리가 부족하고 작업을 완료해야 할 때, 커널은 비활성 페이지를 느린 하드 디스크로 스왑하기 시작합니다. 이렇게 되면 시스템의 I/O 하위 시스템에 부하가 증가하여 시스템이 느려지거나 '스래싱'이 발생합니다.

스래싱을 방지하기 위해서는 RAM을 늘리거나, 코드를 최적화하거나, 동시에 실행되는 프로그램의 수를 줄이거나, 페이지 결함을 줄이는 페이지 교체 알고리즘을 사용할 수 있습니다. 가상 메모리 시스템에서는 "워킹셋 모델"이나 "페이지 폴트 빈도"와 같은 기술을 사용하여 스래싱을 방지할 수 있습니다.

가상 메모리 시스템 내 스레싱 방지 기술

Working set

지역성의 원리를 이용하여 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 방법이다.

워킹셋이라는 이름과 같이 프로세스의 작업을 구성하는 자주 참조되는 페이지들을 묶는다고 생각하면 이해하기 좀 더 편하다. 해당 워킹셋의 합인 전체 프레임이 할당된 페이지 프레임보다 크게되면 Thrashing이 발생하게 된다.

*지역성의 원리: 프로세스가 일정 시간 동안 집중적으로 특정 주소 영역을 참조하는 경향

Page Fault Frequency(페이지 부재 빈도)

프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거하여 각 프로세스에 할당할 메모리 양을 동적으로 예측하고 조절하는 알고리즘이다. 현재 페이지 부재와 직전 페이지 부재 사이의 시간을 관찰하여 상한 값(upper bound)을 초과하거나 하한 값(lower bound) 미만이 되면 운영체제가 메모리에 올라가 있는 프로세스의 수를 조절한다.

교체 방식

• Global 교체

  메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식

• Local 교체

  메모리 상의 자기 프로세스 페이지에서만 교체하는 방식

글로벌 교체(Global Replacement): 이 방법에서는 운영 체제가 전체 시스템의 페이지를 고려하여 페이지를 교체한다. 즉, 한 프로세스가 페이지 부재를 겪었을 때, 운영 체제는 모든 프로세스의 페이지를 검토하여 교체 대상을 결정할 수 있습니다. 글로벌 교체 전략은 시스템 전체를 효율적으로 활용할 수 있지만, 교체 대상 페이지를 선택하는 데 추가적인 오버헤드를 발생시킬 수 있습니다.

로컬 교체(Local Replacement): 이 방법에서는 운영 체제가 페이지 부재를 겪은 특정 프로세스의 페이지만 고려하여 페이지를 교체한다. 즉, 한 프로세스가 페이지 부재를 겪었을 때, 운영 체제는 해당 프로세스의 페이지만 검토하여 교체 대상을 결정합니다. 로컬 교체 전략은 결정을 내리는 데 더 적은 오버헤드를 발생시키지만, 시스템 전체의 사용률을 최적화하는 데는 제한적일 수 있습니다.

실제로는 이 두 가지 전략을 적절히 혼합하여 사용하는 경우가 많습니다. 시스템의 요구사항과 환경에 따라 가장 효과적인 방법을 선택해야 합니다.

다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음

따라서, 다양한 프로세스의 페이지가 메모리에 존재함

페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이

→ 실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 함. 자기 프로세스 페이지(로컬)에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적