본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 14. 가상메모리 부분을 읽고 정리한 내용입니다.
연속 메모리 할당
- 프로세스에 연속적인 메모리 공간을 할당
스와핑
- 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고 생긴 빈공간에 새로운 프로세스를 적재
- swap space: 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
- swap-out: 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
- swap-in: 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨 오는 것
스와핑을 이용하면 실제 메모리 크기보다 프로세스들이 요구하는 메모리 공간 이 더 크더라도 동시에 실행할 수 있음
스왑 영역 크기 확인하기 (mac): sysctl vm.swapusage
$ sysctl vm.swapusage
vm.swapusage: total = 4096.00M used = 2755.62M free = 1340.38M (encrypted)메모리 할당
- 프로세스는 메모리의 빈 공간에 할당되어야 하는데 여러개라면?
- 최초 적합, 최적 적합, 최악 적합
- 빈공간 A, B, C가 있다면?
최초 적합(first-fit)
- 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
- 순서대로 검색한다는 의미는? 어디서부터 검색?
- 검색 최소화, 빠른 할당
최적 적합(best-fit)
- 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 배치
최악 적합(worst fit)
- 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 프로세스를 배치
외부 단편화(external fragmentation)
- 프로세스들이 실행&종료 되길 반복하며 메모리 사이사이에 빈 공간이 발생해서 메모리가 낭비되는 현상
외부 단편화를 해결할 수 있는 대표적인 방법들
- 메모리 압축
- 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
단점
- 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야하고, 메모리에 있는 내용들을 옮기는 작업은 많은 오버헤드를 야기
- 프로세스 이동 방법에 대한 방법을 결정하기 어려움
- 물리 메모리보다 큰 프로세스 실행 불가
페이징을 통한 가상 메모리 관리
가상 메모리
- 실행하고자 하는 프로그램의 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
페이징이란?
- 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당하는 메모리 관리 기법
- 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고,
- 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 일정한 단위로 자른 뒤
- 페이지를 프레임에 할당하는 가상 메모리 관리 기법
페이지 교체와 프레임 할당
요구 페이징(Demand paging)
- 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
기본적인 양상
- CPU가 특정 페이지에 접근하는 명령어를 실행
- 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1인 경우) CPU는 페이지가 적재된 프레임에 접근
- 해당 페이지가 현재 메모리에 없을 경우(유효비트가 0인 경우) 페이지 폴트가 발생
- 페이지 폴트 처리 루틴은 해당 페이지를 메모리에 적재하고 유효 비트를 1로 설정
- 다시 위의 1번을 수행
* 순수 요구 페이징(pure demand paging)
- 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 하는 기법
- 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생함
- 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어짐
요구페이징이 안정적으로 작동하기 위해서는 아래의 2가지가 해결되어야 함
- 페이지 교체
- 프레임 할당
페이지 교체
- 요구 페이징 기법으로 페이지들을 적재하다보면 언젠가 메모리가 가득 차게 됨
- 당장 실행에 필요한 페이지를 적재하려면 페이지를 보조 기억장치로 보내야 하는데 이를 결정하는 방법이 페이지 교체 알고리즘
페이지 교체 알고리즘
- 일반적으로 페이지 폴트가 가장 적제 발생하는 알고리즘을 좋은 알고리즘으로 평가
- 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야하기 때문에 성능 저하발생하기 떄문
페이지 폴트 횟수를 어떻게 알 수 있을까?
⇒ 페이지 참조열 (page reference string) 사용
CPU가 참조하는 페이지들중 연속된 페이지를 생략한 페이지열 (연속된 페이지 참조에서는 페이지 폴트가 발생하지 않기 때문)
예를 들어 아래 숫자들의 페이지 번호들을 CPU가 참조했다면,
2 2 2 3 5 5 5 3 3 7
연속된 페이지를 생략한 페이지 참조열은 아래와 같음
2 3 5 3 7
FIFO 페이지 교체 알고리즘
- First-In, First-Out Page Replacement Algorithm
- 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
- 페이지가 초기에 적재될 때 발생할 수 있는 페이지 폴트는 고려하지 않음
단점
- 프로그램 실행 내내 사용될 내용을 포함할 수도 있는데 이런 페이지를 메모리 메모리에 먼저 적재되었다고 내쫓을 수 있음
2차 기회(second-chance) 페이지 교체 알고리즘
- 참조 비트 1인 경우: 한번 더 기회를 주기
- 참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정
- 참조 비트 0인 경우: CPU가 참조한 적이 없는 페이지로 바로 내쫓기
페이지 3의 참조 비트가 1인 경우
페이지 3의 참조비트를 0으로 초기화 후 가장 최근에 적재된 페이지로 간주
최적 페이지 교체 알고리즘(Optimal p age replacement algorithm)
- CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
- 앞으로 사용빈도가 가장 낮은 페이지를 교체하는 방식
2 3 1 3 5 2 3 4 2 3
- 첫 페이지 폴트: 페이지 1의 경우 한번 사용된 후 이후에 사용되지 않기 때문에 이를 교체함
- 두번째 페이지 폴트: 2,3,5 페이지가 적재된 상황에서 4 페이지를 적재해야 할 때, 그 이후 페이지 2, 3이 사용되므로 5를 교체
특징
- 가장 낮은 페이지 폴트율을 보장하는 알고리즘
- 앞으로 사용되지 않을 페이지 예측관련해 실제 구현이 어려움
- 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주
LRU 페이지 교체 알고리즘
- Least Recently Used Replacement Algorithm
- 가장 오래 사용되지 않은 페이지 교체
첫 페이지 폴트
- 페이지 2, 3, 1이 적재된 상태
- 페이지 5를 적재하려는 상황에서 최근에 페이지 1, 3, 이 적재되었으므로 페이지 2를 교체
두번째 페이지 폴트
- 페이지 5, 3, 1이 적재된 상태
- 페이지 2를 적재하려는 상황에서 최근에 페이지 5, 3, 이 적재되었으므로 페이지 1을 교체
세번째 페이지 폴트
- 페이지 5, 3, 2가 적재된 상태
- 페이지 4를 적재하려는 상황에서 최근에 페이지 2, 3 이 적재되었으므로 페이지 5를 교체
스래싱과 프레임 할당
페이지폴트가 자주 발생하는 이유
- 나쁜 페이지 교체 알고리즘
- 프로세스가 사용할 수 있는 프레임 자체가 적어서
- 새로운 페이지를 참조할 때마다 페이지 폴트가 발생 → 저조한 CPU 이용율
스래싱(Thrashing)
- 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
- 동시에 실행되는 프로세스의 수를 늘린다고 CPU의 이용률이 높아지는 것은 아님
* 멀티프로그래밍의 정도: 메모리에 동시에 실행되는 프로세스의 수
- 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문에 발생
- 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 함
프레임 할당 방식
- 균등 할당(equal allocation)
- 가장 단순한 할당 방식
- 모든 프로세스들에게 균등하게 프레임을 할당하는 방식
- 300개의 프레임을 3개의 프로세스에 할당 시 각 프로세스에 100개의 프레임을 할당
- 실행되는 프로세스들의 크기를 고려하지 못한 방식
2. 비례 할당(proportional allocation)
- 프로세스의 크기에 비례하여 프레임 할당
참고) 균등할당과 비례 할당은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고령한 방식이라는 점에서 정적 할당 방식이라고 함
프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식의 종류
- 작업 집합 모델(working set model)
- 작업집합: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
- 프로세스가 일정기간동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지
- 페이지 폴트 빈도(PFF: Page-Fault Frequency)
아래 2가지 가정에서 생겨난 아이디어
- 페이지 폴트율이 너무 높으면 프로세스는 너무 적은 프레임을 갖고 있다
- 페이지 폴트율이 너무 낮으면 프로세스는 너무 많은 프레임을 갖고 있다
- 상한선, 하한선 범위 안에서만 프레임을 할당하는 방식
참고
1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"