[혼공학습단 9기] 혼공컴운 6주차 챕터14 : 가상 메모리

연속 메모리 할당

• 프로세스에 연속적인 메모리 공간을 할당하는 방식

스와핑

• 실행되지 않는 프로세스들을 보조기억장치 일부 영역으로 쫓아내고
  그렇게 해서 생긴 메모리상의 빈 공간에 다른 프로세스를 적재하여 실행하는 방식
  

• 스왑 영역 : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
• 스왑 아웃 : 실행되지 않는 포르세스가 메모리에서 스왑 영역으로 옮겨지는 것
• 스왑 인 : 스왑 영역에 있는 프로세스가 다시 메모리로 옮겨오는 것

• 스왑 아웃 되었던 프로세스가 스왑 인 될 때는 스왑 아웃 되기 전의 물리 주소와 다른 주소에 적재될 수 있다.

• 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있다.

메모리 할당

최초 적합

• 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
• 검색을 최소화할 수 있고 빠른 할당이 가능하다

최적 적합

• 운영체제가 빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식

최악 적합

• 운영체제가 빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식

위 세 방식 모두 연속 메모리 할당 방식이다.

외부 단편화

• 프로세스를 메모리에 연속적으로 배치하는 할당은 비효율적이다.
  

• 위 예시에서 빈 공간은 50이지만 50크기의 프로세스를 적재할 수 없다.
  프로세스들이 실행되고 종료되길 반복하며 메모리 사이에 공간 발생

• 외부 단편화
  프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
  

해결 방안

• 메모리를 압축하는 것
  흩어져 있는 빈 공간들을 하나로 모으는 방식
  프로세스를 재배치시켜 작은 빈 공간들을 큰 빈 공간으로 만드는 방법
  

• 단점
  1. 빈 공간들을 모으는 동안 시스템은 중지해야한다.
  2. 메모리에 있는 내용을 옮기는 작업은 오버헤드를 야기한다.
  3. 어떻게 옮겨야 오버헤드를 최소화할 수 있는지에 대한 명확한 방법을 결정하기 어렵다.

외부 단편화를 없앨 수 있는 다른 방법이 페이징 기법이다.

페이징을 통한 가상 메모리 관리

• 가상 메모리
  실행하고자 하는 프로그램 일부만 메모리에 적재하여 실제 물리 메모리보다 더 큰 프로세스를 실행할 수 있게 하는 기술

페이징이란

• 프로세스의 논리 주소 공간을 페이지라는 단위로 자르고
  메모리 물리 주소 공간을 프레임이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤
  페이지를 프레임에 할당하는 가상 메모리 관리 기법
  

• 페이징에서도 스와핑을 사용할 수 있다.
  프로세스 전체가 아닌 페이지 단위로 스왑 아웃 / 인 된다.
  페이지 아웃 / 페이지 인 이라고 부르기도 한다.
  한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요는 없다.
  

• 프로세스를 이루는 페이지 중 필요한 페이지만 메모리에 적재하고, 나머지는 보조기억장치에 남겨둔다.
  이를 통해 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.

페이지 테이블

• 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU는 이를 순차적으로 실행할 수 없다.
  그래서 페이지 테이블을 이용한다.
  

• 페이지 테이블
  (실제 메모리 내의 주소)물리 주소에 불연속적으로 배치되더라도
  (CPU가 보는 주소) 논리 주소에는 연속적으로 배치되도록 하는 방법
  

• 페이지 번호와 프레임 번호를 짝지어주는 역할
  어떤 페이지가 어떤 어떤 프레임에 할당되었는지를 알려준다.
  페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있다.
  물리 주소에는 불연속적이더라도 논리 주소에는 연속적으로 배치되도록 한다.
  

• 페이징은 외부 단편화 문제를 해결할 수 있지만 내부 단편화 문제를 야기할 수 있다.
  내부 단편화는 페이지 크기보다 작은 크기로 발생
  

PTBR

• CPU 내의 페이지 테이블 베이스 레지스터
  각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.

• 이렇게 페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배가 된다.
  페이지 테이블을 보는데 한 번, 프레임에 접근하는데 한 번이 소요됨.

TLB

• 위 문제를 해결하기 위해 CPU 곁에 TLB를 둔다.

TLB : 페이지 테이블의 캐시 메모리
페이지 테이블의 일부를 가져와 저장한다.

TLB 히트 : 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우
→ 메모리에 접근할 필요가 없어 한 번만 접근하면 된다.

TLB 미스 : 페이지 번호가 TLB에 없을 경우

페이징에서의 주소 변환

• 특정 주소에 접근하려면 정보가 필요하다.
  • 어떤 페이지 혹은 프레임에 접근하고 싶은지
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지

• 페이징 시스템에서는 모든 논리 주소가 페이지 번호와 변위로 이루어져 있다.
  
  • 페이지 번호 : 접근하고자 하는 페이지 번호
  • 변위 : 접근하려는 주소가 프레임의 시작 번지로부터 얼마나 떨어져 있는지

• <페이지 번호, 변위>로 이루어진 논리 주소는 페이지 테이블을 통해
  <프레임 번호, 변위>로 변환된다.
  
  논리 주소의 변위와 물리 주소의 변위 값은 같다.

페이지 테이블 엔트리

• 페이지 테이블의 각각의 행들을 말한다.
  페이지 번호, 프레임 번호 외에도 다른 정보들이 들어있다.

유효 비트

• 현재 해당 페이지에 접근 가능한지 여부를 알려준다.
• 현재 페이지가 메모리와 보조기억장치 중 어디에 적재되었는지를 알려주는 비트
  메모리에 적재되어 있다면 1, 그렇지 않다면 0
  
• 유효비트가 0인 페이지에 접근하려고 하면 페이지 폴트 인터럽트 발생
  

보호 비트

• 페이지 보호 기능을 위해 존재하는 비트
• 해당 페이지가 읽고 쓰기가 모두 가능한지, 혹은 읽기만 가능한 페이지인지를 나타낼 수 있다.
  0이면 읽기만 가능, 1이면 둘 다 가능

• 세 개의 비트로 더 복잡하게 구현 가능하다.
  읽기(r), 쓰기(w), 실행(x)의 조합으로 나타낸다.
  100의 경우 읽기만 가능, 110의 경우 읽고 쓰기만 가능

참조 비트

• CPU가 페이지에 접근한 적이 있는지 여부를 나타낸다.
• 적재 이후 읽거나 쓴 페이지는 1로, 그렇지 않은 경우는 0으로 유지

수정 비트 (더티 비트)

• 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려준다.
• 1이면 변경된 적 있고, 0이면 변경된 적 없다.

• 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업 필요 여부를 판단하기 위해 존재

페이지 교체와 프레임 할당

• 물리 메모리의 크기는 한정되어 있다.
  기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고
  프로세스들에게 적절한 수의 프레임을 할당할 수 있어야 한다.

요구 페이징

• 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
  
• 요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체, 프레임 할당을 해결해야 한다.

페이지 교체 알고리즘

• 쫓아낼 페이지를 결정하는 방법
• 일반적으로 페이지 폴트를 적게 일으키는 알고리즘을 좋은 알고리즘으로 평가한다.
  페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야해서 메모리에 있는 페이지를 가져오는 것보다 느리기 때문이다.

• 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있다.

페이지 참조열

• CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

• 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않아 연속된 페이지 생략함.

FIFO 페이지 교체 알고리즘

• 가장 먼저 올라온 페이지부터 내쫓는 방식
  

• 초기에 적재된 페이지가 계속 사용될 내용을 담고 있을 경우 문제가 된다.

• 보완책 : 2차 기회 페이지 교체 알고리즘

  참조 비트 1 : CPU가 참조한 적이 있는 페이지 → 참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정

  참조 비트 0 : CPU가 참조한 적이 없는 페이지 → 내쫓기

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려하는 알고리즘
  사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
  
• 페이지 폴트 발생 빈도가 가장 낮다.
  하지만 가장 사용되지 않을 페이지를 예측하는 것이 어렵기 때문에 실제 구현이 어렵다.
  

LRU 페이지 교체 알고리즘

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

스래싱과 프레임 할당

• 프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트가 자주 발생한다.

스래싱

• 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요해 성능이 저해되는 문제

• 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않기 때문

• 동시 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 높아지는 것이 아니다.
  

• 그렇기에 운영체제는 최소한의 프레임 수를 파악하고 적절한 프레임을 할당할 수 있어야 한다.

프레임 할당 방식

• 균등 할당
  모든 프로세스에 균등하게 프레임을 제공하는 방식
  

• 비례 할당
  프로세스의 크기에 비례하여 프레임을 할당하는 방식

배분할 프레임 결정하는 방식

1. 작업 집합 모델
   프로세스가 일정 기간 동안 참조한 페이지 집합을 기억해 페이지 교체 방지하는 방식
   작업 집합 : 실행 중인 프로세스가 일정 시간 동안 참조한 페이지 집합

• 작업 집합을 구하려면 필요한 것
  1. 프로세스가 참조한 페이지
  2. 시간 간격

2. 페이지 폴트 빈도 기반
   
   페이지 폴트율에 상한선, 하한선을 정하고 이 범위 안에서만 프레임 할당하는 방식