[cs]가상메모리

연속 메모리 할당

프로세스에 연속적인 메모리 공간을 할당

스와핑

• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고
  생긴 빈 공간에 새 프로세스 적재
• 모든 프로세스의 필요한 메모리의 합이 실제 메모리보다 커도 스와핑을 통해서 모두 실행 가능하다

메모리 할당

• 빈 공간이 여러 개 있을 때 빈 공간을 선택하는 방법

최초 적합

• 운영체제가 빈 공간을 찾다가 최초에 발견한 프로세스를 적재할 수 있는 빈 공간에 프로세스를 적재

최적 적합

• 운영체제가 빈 공간을 모두 탐색한 후 프로세스를 적재할 수 있는 가장 작은 빈 공간에 프로세스를 적재

최악 적합

• 운영체제가 빈 공간을 모두 탐색한 후 프로세스를 적재할 수 있는 공간 중 가장 작은 큰 공간에 프로세스를 적재

외부 단편화

• 메모리를 연속적으로 할당하여 발생하는 문제
• 프로세스 메모리의 중간 중간 빈 공간이 생기게 되어 메모리가 낭비 되는 것

압축

• 빈 공간을 압축하여 큰 공간으로 만들어 외부 단편화를 해결하는 방법
• 프로세스를 재배치 하는 동안 오버헤드가 발생하는 문제 발생

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

가상 메모리

• 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
• 가상 메모리 관리 기법에는 페이징과 세그멘테이션이 있지만 현대 운영체제 대부분은 페이징을 사용한다.

세그멘테이션

• 프로세스를 섹션이라 불리는 각기 다른 크기로 자른다.
• 섹션의 크기는 사용자에 의해 결정된다.
• 섹션의 크기가 각기 다르기 때문에 외부 단편화 문제를 야기한다.

페이징이란

• 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당하여 외부 단편화 문제를 해결
• 프로세스의 논리 주소 공간을 페이지라는 일정 단위로 자르고,
  메모리의 물리 주소 공간을 프레임이라는 페이지와 동일한 일정한 단위로 자른 뒤
  페이지를 프레임에 할당하는 가상 메모리 관리 기법

페이징에서의 스와핑

• 프로세스 단위의 스왑 인, 스왑 아웃이 아닌 페이지 단위의 스왑 인(페이지 인), 스왑 아웃(페이지 아웃)
• 현재 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃
• 실행에 필요한 페이지들은 메모리로 스왑 인
• 프로레스를 실행하기 위해 모든 페이지가 적재될 필요 없다.

페이지 테이블

• 프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 이를 순차적으로 실행하기 어려워진다. 이를 해결하기 위해서 페이지 테이블이 존재한다.
• 물리 주소에 불연속적으로 배치되더라도
  논리 주소에는 연속적으로 배치되도록 하는 방법
  페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표

내부 단편화

• 페이징으로 외부 단편화를 해결할 수 있지만 내부 단편화 문제를 야기할 수 있다.
• 내부 단편화는 프로세스가 페이지 크기로 정확히 나누어 떨어지지 않을때 마지막 페이지에서 프로세스가 할당되지 않은 빈 공간이 생기게 된다.

페이지 테이블 베이스 레지스터(PTBR)

• 각각의 프로세스가 가지는 페이지 테이블의 메모리 주소를 저장하고 있는 레지스터
• 페이지 테이블이 메모리에 있으면 메모리 접근 시간이 두배로 늘어난다.
  • 페이지 테이블 참조 1회
  • 페이지를 참조하기 위해 1회

TLB

• CPU 곁에 페이지 테이블의 캐시 메모리
• 페이지 테이블의 일부를 저장

페이징에서의 주소 변환

• 특정 주소에 접근하고자 할 때 알아야 할 정보
  • 어떤 페이지/프레임에 접근하고 싶은지
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
• 페이징 시스템에서의 논리 주소는 <페이지 번호, 변위>로 이루어져 있고
  페이지 테이블을 통해 <프레임 번호, 변위>로 변환됨
• 프레임과 페이지의 크기는 같기 때문에 변위의 값은 같다.

페이지 테이블 엔트리

• 페이지 번호, 프레임 번호 이외에 담기는 정보들

유효 비트

• 현재 해당 페이지에 접근 가능한지 여부
• 유효 비트가 0인 페이지에 접근하려고 하면? (메모리에 적재되지 않은 페이지에 접근하려고 하면)
  • 페이지 폴트라는 인터럽트 발생

보호비트

• 페이지 보호 기능을 위해 존재하는 비트
• 읽기, 쓰기, 실행 권한 등의 비트 조합을 가질 수 있다.

참조 비트

• CPU가 페이지에 접근한 적이 있는지 여부를 표현하는 비트

수정 비트

• CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부
• 해당 페이지에 새롭게 쓰여진 데이터가 없으면 스왑 아웃 시에 보조기억장치에 쓰기작업을 하지 않아도 된다.

페이징의 이점

쓰기 시 복사

• 이론적인 fork()
  • 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 적재(프로세스 생성 시간 지연, 메모리 낭비)
• 쓰기 시 복사는 이론적은 fork()의 문제점을 해결
• 부모 프로세스와 동일한 자식 프로세스가 복제되어 생성되면
  자식 프로세스는 부모 프로세스와 동일한 프레임을 가리킴
• 부모 프로세스/ 자식 프로세스 중 하나가 페이지에 쓰기 작업 수행 시 해당 페이지는 별도의 공간으로 복제(프로세스 생성 시간 절약, 메모리 절약)

계층적 페이징

• 프로세스 테이블의 크기는 생각보다 작지 않다,
• 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 낭비
• 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 방법
• 페이지 테이블을 페이징하여 여러 단계의 페이지 페이지를 두는 방식
• 계층적 페이징을 이용하는 환경에서의 논리 주소
  • 바깥 페이지 번호 | 안쪽 페이지 번호 | 변위

페이지 교체와 프레임 할당

요구페이징

• 요구하는 페이지만 적재하는 기법

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

순수 요구 페이징

• 아무런 페이지도 메모리에 적재하지 않은 상태로 실행

페이지 교체 알고리즘

• 메모리가 가득찼을 때 어떤 페이지를 스왑 아웃 할지 정하는 알고리즘이 페이지 교체 알고리즘이다.
• 페이지 폴트가 적은 알고리즘이 좋은 알고리즘이다.
• 페이지 참조열을 통해 페이지 폴트 횟수를 알 수 있다.
  • 페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

알고리즘 종류

FIFO 페이지 교체 알고리즘

• 가장 단순한 방식
• 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
• 프로그램 실행 내내 사용될 페이지가 먼저 적재되었다는 이유로 스왑 아웃될 수 있다.

2차 기회 페이지 교체 알고리즘(FIFO 페이지 교체 알고리즘 보완 알고리즘)

• 참조 비트를 통해 스왑 아웃하기 전 참조 비트를 통해 참조된 적이 있다면(1이라면)
  참조 비트를 초기화 한 후(0으로 초기화) 최근에 적재된 페이지로 간주한다.

최적 페이지 교체 알고리즘

• 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
• CPU에 의해 참조되는 횟수를 고려
• 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지
• 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
• 가장 낮은 페이지 폴트율을 보장하지만 실제 구현이 어렵다.

LRU 페이지 교체 알고리즘

• 가장 오래 사용되지 않은 페이지 교체
  • 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이다.

스레싱

• 페이지 폴트가 자주 발생하는 이유
  • 나쁜 페이지 교체 알고리즘을 사용하는 경우
  • 프로세스가 사용할 수 있는 프레임 자체가 적은 경우
• 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
• 동시 실행되는 프로세스의 수가 늘어난다고 CPU 이용률이 높아지는 것은 아니다.

• 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문
• 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다.

프레임 할당 방식

정적 할당 방식

균등 할당

• 가장 단순한 할당 방식
• 모든 프로세스들에게 균등하게 프레임을 할당하는 방식

비례 할당

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

동적 할당 방식

작업 집합 모델

• 프로세스가 실행하는 과정에서 배분할 프레임 결정
• 스래싱이 발생하는 이유는 빈번한 페이지 교체 때문
  • CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당
• 작업 집합 구하기
  • 프로세스가 참조한 페이지와 시간 간격이 필요

페이지 폴트 빈도 기반 프레임 할당

• 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 가지고 있다.

• 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 가지고 있다.
  

• 상한선 하한선 내에서 프레임을 할당한다.

참고자료