[CS Study : OS] 가상 메모리 관리

컴퓨터 과학에 대한 지식을 습득하고 정리하는 기록용 포스팅입니다.
예외를 판단하는 사고를 기르고, 효율적인 코드를 작성하기 위해
컴퓨터 과학 지식을 활용하는 것을 목표로 합니다.

✅ 요구 페이징과 페이지 부재

📌 요구 페이징의 기본 개념

• 요구 페이징(Demand Paging)은 프로세스의 모든 데이터를 물리 메모리에 적재하지 않고, 필요한 시점에만 메모리에 가져오는 가져오기 정책을 뜻한다.
• 운영체제는 프로세스를 구성하는 모듈을 전부 메모리에 올리지 않는다. 필요한 모듈만 메모리에 올려 실행하고 나머지 모듈은 필요하다고 판단될 때 메모리로 불러온다.
  0
  
  

📌 요구 페이징의 필요성

• 메모리를 효율적으로 관리하기 위해서이다. 메모리가 꽉 차면 관리하기 어려우므로 가급적 적은 양의 프로세스만 유지한다.
• 응답 속도를 향상하기 위해서이다. 용량이 큰 프로세르르 전부 메모리로 가져와 실행하면 응답이 늦어질 수 있으므로 필요한 모듈만 올려 실행한다.

📌 페이지 테이블 엔트리의 구조

• 가상 메모리의 크기는 물리 메모리와 스왑 영역을 합친 것이다. 스왑 영역은 하드디스크에 존재하나 메모리 관리자가 관리하는 영역으로, 가상 메모리의 구성 요소 중 하나이다.

• 스왑 인 : 스왑 영역에서 물리 메모리로 데이터를 가져오는 것.
  스왑 아웃 : 물리 메모리에서 스왑 영역으로 데이터를 내보내는 것.

• 페이지 테이블 엔트리(PTE)는 페이지 테이블의 한 행을 말한다.
• 그림 처럼 페이지 번호, 플래그 비트, 프레임 번호로 구성된다.

플래그 비트의 종류

• 접근 비트(access bit) : 페이지에 올라온 후 사용한 적이 있는지 알려주는 비트이다. 참조 비트라고도 한다.

• 변경 비트(modified bit) : 페이지에 올라온 후 데이터 변경이 있었는지 알려주는 비트이다. 새로운 데이터 값으로 오염됐는다는 의미에서 더티 비트라고도 한다.

• 유효 비트(valid bit) : 페이지가 실제 메모리에 있는지, 스왑 영역에 있는 지를 나타내는 비트이다.
  

유효비트가 0일 때는 페이지가 메모리에 있으므로 주소 필드에 프레임 번호가 저장된다.
유효비트가 1일 때는 페에지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지의 주소가 저장된다.

• 읽기, 쓰기, 실행 비트(read, write, excute bit) : 페이지에 대한 읽기, 쓰기, 실행 권한을 나타내는 비트이다.

📌 페이지 부재(Page Fault)

• 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황을 페이지 부재라고한다.
• 가상 메모리 공간에는 존재하지만 실제 물리 메모리에는 없을 때 일어나는 인터럽트이며, 페이지 폴트가 발생하면 운영체제에서 스왑영역에서 해당 페이지를 물리 메모리에 올린다.

1. 페이지 부재 : 페이지 테이블의 유효 비트가 1이기 때문에 페이지 부재가 발생한다.
2. 스왑인 : 메모리 관리자는 스왑 영역의 0번에 있는 페이지를 메모리의 비어 있는 프레임인 5로 가져온다.
3. 업데이트 : 프레임 5에 페이지가 들어오면 PTE 3의 유효 비트는 1→0으로, 주소필드는 0→5로 변한다.

• 위의 경우와 같이 비어 있는 프레임이 있다면 작업이 수월하지만, 빈 프레임이 없을 때는 메모리에 있는 프레임 중 하나를 스왑 영역 밖으로 내보낸 후에야 해당 페이지를 가져올 수 있다.

• 어떤 페이지를 내보낼지 결정하는 알고리즘을 페이지 교체 알고리즘이라고 하며, 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지를 대상 페이지(Victim page)라고 한다.

1. 페이지 부재 : 페이지 테이블의 유효 비트가 1이기 때문에 페이지 부재가 발생한다.
2. 스왑 아웃 : 메모리가 꽉 차있기 때문에, 페이지 중 하나를 내보내야 한다.
3. 업데이트 : 대상 페이지 PTE 1의 유효 비트는 0→1으로, 주소 필드 값이 프레임 3에서 스왑 주소 6으로 바뀐다.
4. 스왑인 : 스왑 영역 1번에 있던 페이지 E가 올라간다.
5. 업데이트 : PTE 4의 유효 비트는 1→0으로, 주소 필드 값이 스왑 주소 1에서 프레임 3으로 바뀐다.

📌 지역성

• 페이지 교체 알고리즘은 지역성을 바탕으로 한다. 지역성은 기억 장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질을 말한다.

• 공간 지역성 : 현재 위치에서 가까운 데이터에 접근할 확률이 높다는 것이다.

• 시간 지역성 : 현재를 기준으로 가장 가까운 시간에 접근할 확률이 높다는 것이다.

• 순차적 지역성 : 여러 작업이 순서대로 진행되는 경향이 있다는 것이다.

---

✅ 페이지 교체 알고리즘

📌 기본 개념

• 프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재가 발생한다. 페이지 부재가 발생하면 스왑 영역에서 페이지를 메모리로 가져오는데, 만약 메모리가 꽉 찼다면 메모리에 있는 페이지를 스왑 영역으로 내보내야한다.
• 페이지 교체 알고리즘이란 스왑 영역으로 보낼 페이지를 결정하는 알고리즘으로, 메모리에 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상시킨다.

📌 페이지 교체 알고리즘의 종류

무작위 페이지 교체 알고리즘(Random page replacement algorithm)

• 스왑 영역에서 쫓아낼 대상 페이지를 특별한 로직 없이 무작위로 선정한다.
• 지역성을 전혀 고려하지 않기 때문에, 자주사용하는 페이지가 대상 페이지로 선정되기도 한다.

FIFO 페이지 교체 알고리즘(First In First Out page replacement algorithm)

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

• FIFO 페이지 교체 알고리즘은 큐로 구현한다. 메모리의 맨 위에 있는 페이지는 가장 오래된 페이지이고 새로운 페이지는 항상 아래에 삽입된다.

• 시간 지역성을 고려하면 가장 오래된 페이지를 대상 페이지로 선정하는 것이 맞다. 그러나 메모리에 올라온 지 오래됐더라도 자주 사용되는 페이지가 있다.

최적 페이지 교체 알고리즘(Optimal page replacement algorithm)

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

• 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋지만, 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없다.

• 아래 나올 LRU, LFU, NUR 알고리즘은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추청하기 때문에 최적 근접 알고리즘이라 부른다.

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

• 최근 최소 사용 페이지 교체 알고리즘으로, 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다.

• 즉, 최근에 사용된 페이지를 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정한ek.

• 페이지 접근 시간에 기반한 구현 : 페이지에 접근한 시간을 기록하여 구현하는 방식이다.

• 카운터에 기반한 구현 : 접근 카운터를 기록하여 구현하는 방식이다.

• 참조 비트 시프트 방식 구현 : 각 페이지에 일정 크기의 참조 비트를 만들어 사용한다. 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀐다. 또한 접근할 때마다 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동한다. 참조 비트를 갱신하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정한다.

• 위 방법 모두 추가로 공간을 사용한다는 단점이 있다.

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

• 최소 빈도 사용 알고리즘이라고하며, 페이지가 몇 번 사용 됐는지를 기준으로 대상 페이지를 선정한다.

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

• LFU 알고리즘 또한 낭비되는 메모리 공간이 많다는 단점이 있다.

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

• 최근 미사용 페이지 교체 알고리즘으로, LRU, LFU 알고리즘과 성능이 거의 비슷하면서도 불필요한 공간 낭비를 해결한 알고리즘이다.

• 참조 비트와 변경 비트를 사용하여 미래를 추정한다. 모든 페이지의 초기 상태는 (0,0)이며,
  참조가 발생할 때 (1,0)으로, 변경이 발생할 때 (0,1)으로, 둘다 발생하면 (1,1)으로 바뀐다.

• NUR 알고리즘에서 우선 고려 대상은 참조 비트이다. 때문에 다음과 같은 우선 순위를 갖는다.
  (0,0) < (0,1) < (1,0) < (1,1)

• 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정한다. 모든 페이지가 (1,1)이 되면 모든 페이지 비트를 (1,1)로 reset 한다.

---

✅ 참고

도서 : 쉽게 배우는 운영체제