요구 페이징과 페이지 교체 알고리즘

요구 페이징

사용자가 요청할 때 메모리로 가져오는 것으로 이를 요구 페이징이라고 한다.

 

맥북을 오래 사용했을 때 느려지는 경험을 한 적이 있다.
이때 껏다 키면 다시 빨라진다.

오래 켜두었을 때 느려지는 이유는 작업을 하지 않고 쉬는 프로세스나 좀비 프로세스가 메모리를 차지하여 메모리 관리가 복잡해지기 때문이다.

따라서 메모리엔 꼭 필요한 프로세스만 유지하는 것이 좋다.

 

운영체제는 프로세스를 구성하는 모듈을 전부 메모리에 올리지 않고 필요한 모듈만 올린다.

 

이렇게 관리하는 이유는

메모리가 꽉 차면 관리가 어렵고 용량이 큰 프로세스를 저부 가져와 실행하면 느려질 수 있기 때문이다.

 

 

EX) 블로그 작성의 경우 작성 외에 글시체에 관련된 기능들이 있다.

글을 작성할 때 바로 글시체에 관련된 모든 기능들을 메모리에 올리면 공간이 낭비될 뿐만 아니라 시작되는 시간도 오래 걸린다.
따라서 메모리는 글쓰기에 필요한 프로그램만 올리고 글시체 관련 기능들은 
사용자가 필요할 때마다 가져오는 것이 효율적이다.

 

즉, 프로그램의 일부만 가져와 실행하고 특정 기능을 요구할 때 해당 모듈을 메모리에 올리면 메모리의 절약과 효율적 관리, 프로세스의 응답 속도 향상 등의 효과를 볼 수 있다.

 

예제처럼 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것을 요구 페이징이라고 한다.

 

 

---

 

페이지 테이블 엔트리 구성

 

가상 메모리 크기 = 물리 메모리 크기 + 스왑 영역의 크기

 

• 스왑 영역 : 하드디스크에 존재하거나 메모리 관리자가 관리하는 영역.
  • 스왑인 (swap-in): 스왑 영역에서 물리 메모리로 데이터를 가져오는 것.
  • 스왑아웃 (swap-out): 물리 메모리에서 스왑 영역으로 데이터를 내보내는 것.

 

가상 메모리 시스템에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 있다.

• 스왑 영역에 있는 경우
  • 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못하는 경우
  • 메모리가 꽉차서 스왑영역으로 옮겨지는 경우
• 페이지가 메모리에 있는지 스왑영역에 있는지 유효 비트로 표시한다.

 

 

• 페이지 번호
• 프레임 번호
• 플래그 비트
  • 접근 비트 : 페이지가 메모리로 올라온 후 사용한 적이 있는지 알려주는 비트.
  • 변경 비트 : 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트.
  • 유효 비트 : 페이지가 실제 메모리에 있는지를 나타내는 비트.
    • 유효 비트가 0인 경우: 페이지가 메모리에 있으므로 주소 필드에 물리 메모리의 프레임 번호가 저장된다.
    • 유효 비트가 1인 경우: 페이지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지의 주소가 저장된다. 
  • 읽기, 쓰기, 실행 비트: 페이지에 대한 읽기, 쓰기, 실행 권한을 나타내는 비트.

 

---

 

페이지 부재(page fault) / 페이지 교체

 

물리 메모리의 5번 공간이 비어있는 상황에서 D 페이지 요청이 들어왔을 때

 

페이지 부재

 

프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황 (스왑 영역에 있는 상황)

 

• 페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨줘야 한다.
• 이때 물리 메모리에 빈 공간이 있다면 그 자리로 페이지를 가져오면 된다.
• 만약 빈 공간이 없이 물리 메모리가 가득 차 있는 상태라면 어떤 페이지 하나를
  스왑 영역으로 내보내고(스왑 아웃) 원하는 페이지를 빈 공간에 넣어야 한다 (스왑 인) . 

 

페이지 교체

 

페이지 부재가 발생 시 스왑 영역에 있는 페이지를 메모리의 빈 영역에 올린 후 페이지 테이블을 업데이트하는 과정.

 

빈 프레임이 없을 땐 메모리에 있는 프레임 중 하나를 스왑 영역으로 내보낸 후에 해당 페이지를 가져올 수 있다.

 

E 페이지를 요청하였는데 빈 프레임이 없을 때

1. 페이지 테이블 4번의 유효 비트는 1이다
   • 즉, 스왑 영역에 있으므로 페이지 부재가 발생한다.
2. 물리 메모리에 빈 프레임이 없으므로 스왑 영역으로 보낼 대상 페이지를 선정하여 스왑 영역으로 보낸다.
3. 페이지 테이블의 대상 페이지 유효 비트와 주소를 변경한다. (업데이트 1)
4. 대상 페이지가 나가고 생긴 빈 프레임에 요청 페이지를 가져온다.
5. 페이지 테이블의 요청 페이지 유효 비트와 주소를 변경한다. (업데이트 2)

 

 

---

 

페이지 교체 알고리즘

페이지 부재가 발생해 메모리가 꽉 찼을 때 스왑 영역으로 보낼 페이지를 결정하는 알고리즘.

 

 

• 대상 페이지 : 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지 
• 지역성 : 기억장치에 접근하는 패턴이 메모리 전체에 분포되는 것이 아니라 특정 영역에 집중되는 성질을 말하며
  페이지 교체 알고리즘이 쫓아낼 페이지를 찾을 때 지역성을 바탕으로 한다.
  
  • 공간의 지역성 : 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다.
  • 시간의 지역성 : 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다.
  • 순차적 지역성 : 여러 작업이 순서대로 진행되는 경향이 있다.

메모리에서 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상시킨다.

 

 

---

 

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

 

스왑 영역으로 쫓아낼 대상 페이지를 특별한 로직없이 무작위로 선정.

 

지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정되기도 하여 성능이 좋지 않다.

 

FIFO 페이지 교체 알고리즘

 

시간상으로 메모리에 가정 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫓아낸다.

 

메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고, 나머지 페이지들은 위쪽으로 이동하며, 새로운 페이지가 아래쪽의 남은 공간에 들어온다.

 

무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어진다.

 

최적 페이지 교체 알고리즘

 

앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다.

 

메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리있는 페이지를 대상 페이지로 선정한다.

 

이상적인 방법이지만 실제로 구현할 수는 없다.

 

LRU(Least Recently Used) 페이지 교체 알고리즘

 

직역하면 최근 최소 사용 페이지 교체 알고리즘이다.

 

메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다.

최근에 사용된 페이지는 놔두고 오래 전에 사용된 페이지를 대상 페이지로 선정한다.

알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용하는 방법도 있다.

 

• 페이지 접근 시간에 기반한 구현
  • 페이지에 접근한 지 가장 오래된 페이지를 교체한다.
• 카운터에 기반한 구현
  • 시간 대신 카운터를 사용하여 구현
• 참조 비트를 이용한 구현
  • 각 페이지에 일정 크기의 참조 비트를 만드는 것
  • 참조 비트의 초기 값은 0이며 페이지에 접근할 때마다 1로 바뀐다.
  • 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동하므로, 오래될수록 오른쪽으로 1이 이동한다.
  • 조 비트를 갱신하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정한다

 

LFU(Least Frequently Used) 페이지 교체 알고리즘

 

직역하면 가작 적게 사용 페이지 교체 알고리즘 이다.

 

몇 번 사용되었는지를 기준으로 대상 페이지를 선정하는 알고리즘

현재 프레임에 있는 페이지마다 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮김

 

NUR(Not Used Recently page replacement algorithm) 페이지 교체 알고리즘

 

직역하면 최근 미사용 페이지 교체 알고리즘이다.

 

LRU, LFU 페이지 교체 알고리즘은 성능은 좋으나 추가적인 오버헤드가 크다.

이를 개선하기 위해 두 개의 비트만으로 구현한 알고리즘이다.

 

• 페이지마다 참조비트와 변경비트를 가진다.
• 페이지에 접근(read/execute)하면 참조 비트 1, 페이지가 변경(write/append)되면 변경 비트 1
• 모든 페이지의 초기 상태는 (0, 0) , 모든 값이 (1, 1)이 되면 초기화한다.
• 대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾는다.
• 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정한다.

 

FIFO 변형 알고리즘

 

2차 기회 페이지 교체 알고리즘

 

• 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외시켜준다.
• 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 준다.
• FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용한다.

 

 

시계 알고리즘

 

 

• 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용한다.
• 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용한다.
• 포인터가 큐의 맨 바닥으로 내려가면 다음 번에는 다시 큐의 처음을 가리키게 된다.

• 2차 기회 페이지 교체 알고리즘에 비해 각 페이지에 참조 비트가 하나씩 추가되었다.
• 참조 비트의 초깃 값은 0, 메모리에 있는 페이지를 성공적으로 참조하면 1로 변경한다.
• 대상 포인터는 메모리가 꽉 찰 경우 스왑 영역으로 쫓아낼 페이지를 가리킨다.
• 가리키는 페이지가 스왑 영역으로 쫓겨나면 대상 포인터를 밑으로 이동하는데 이때 참조 비트가 1인 페이지는 0으로 만든 후 건너뛴다.