14. 가상 메모리
1) 연속 메모리 할당
스와핑
프로세스를 보조기억장치의 일부 영역으로 쫓아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 당장 필요한 프로세스를 적재하는 메모리 기법
- 스왑 아웃(swap-out) : 프로세스를 보조기억장치의 일부 영역으로 쫓아내는 것
- 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨짐
- 스왑 인(swap-in) : 스왑 아웃된 프로세스를 메모리에 적재하는 것
- 스왑 영역 (swap space): 스왑 아웃된 프로세스가 적재되는 보조기억장치 영역
- 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
메모리 할당
프로세스는 메모리 내의 빈 공간에 적재되어야 한다. 빈 공간이 여러 개 있다면 프로세스를 어디에 배치해야할 지
- 최초 적합(first fit) : 최초로 발견한 적재 가능한 빈 공간에 프로세스를 즉시 배치하는 방식
- 최적 적합(best fit) : 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식
- 최악 적합(worst fit) : 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
연속 메모리 할당
프로세스를 메모리에 연속적으로 배치하는 방식
- 부작용 : 외부 단편화
- 프로세스들이 실행되고 종료되길 반복하며 빈 공간이 생기는 메모리 낭비 현상
- 프로세스 B, D 실행 종료로 남아 있는 공간은 50MB이지만, 실제 50MB 프로세스를 적재할 수는 없다.
연속 메모리 할당 | 외부 단편화 |
---|
| |
외부 단편화
프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상을 의미함
- 해결 방법
- 메모리 압축 (compaction) : 메모리 조각 모음
- 메모리 내에 저장된 프로세스를 적당히 재배치 시켜서 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
- 단점 : 압축하는 동안에 시스템이 하는 일을 중지해야하며, 옮기는 작업은 많은 오버헤드를 야기한다.
- 페이징 기법
- 메모리와 프로세스를 일정 단위로 자르고, 잘라진 공간에 프로세스를 할당하는 방법으로 해결한다.
2) 페이징을 통한 가상 메모리 관리
프로세스를 메모리에 연속적으로 할당하는 방식에서의 두가지 문제점
- 외부 단편화
- 물리 메모리보다 큰 프로세스를 실행할 수 없다.
가상 메모리(virtual memory)
- 프로세스의 일부만을 적재하여 실제 물리 메모리보다 더 큰 프로세스를 실행하는 기술
- 가상 메모리 관리 기법
- 페이징은 현대 운영체제에서 가장 대중적으로 사용되는 가상 메모리 관리 기법
- 세그멘테이션
페이징
- 물리 메모리를 프레임(frame)이라는 일정한 크기로 나누고
- 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 크기로 나눈 뒤
- 페이지를 프레임에 매핑(할당)하는 메모리 관리 방식
페이징 |
---|
|
페이징 시스템의 핵심
- 논리 주소 공간(Logical Address Space): 프로세스가 사용하는 주소 공간으로, 페이지(page)로 나뉜다. 각 페이지는 프로그램 코드, 데이터, 스택 등을 포함할 수 있는 메모리의 연속적인 블록이다.
- 물리 메모리(Physical Memory): 실제 메모리 주소 공간으로, 프레임(frame)으로 나뉜다. 각 프레임은 페이지와 동일한 크기의 메모리 블록으로, 페이지가 실제로 저장되는 위치이다.
- 페이지 테이블(Page Table): 프로세스의 각 페이지가 물리 메모리의 어느 프레임에 매핑되어 있는지를 나타내는 테이블이다. 운영 체제는 이 테이블을 사용하여 논리 주소를 물리 주소로 변환한다.
- 페이징에서도 스와핑을 사용할 수 있다.
-
프로세스 전체가 스왑 아웃/스왑 인되는 것이 아닌, 페이지 단위로 스왑 아웃/스왑 인(페이지 아웃/페이지 인)된다.
-
하나의 프로세스를 실행하기위해 프로세스 전체가 메모리에 적재될 필요가 없다. 실행에 필요한 일부 페이지만 메모리에 적재하고 그렇지않은 페이지들은 보조기억장치 들에 남겨둘 수 있다.
페이지 테이블
프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 ‘다음에 실행할 위치’를 찾기 힘들어진다.
물리주소(실제 메모리 내의 주소)에 불연속적으로 배치되어도 논리 주소(CPU가 바라보는 주소)에는 연속적으로 배치되도록 페이지 테이블 이용한다.
- 어떤 페이지가 어떤 프레임에 매핑되었는지 확인하기 위함
- 프레임과 페이지의 매핑 정보를 담고 있는 표 형태의 데이터로, 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있다.
- 프로세스마다 페이지 테이블을 가지고 있다.
- 물리 주소상에서는 분산되어있지만, CPU입장에서 바라본 논리 주소는 연속적으로 보인다.(페이지 테이블을 바라 보는 것)
내부 단편화
외부 단편화를 해결하는 페이징은 내부 단편화 문제를 야기할 수 있다.
원인 :
- 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것이 아니다.(모든 프로세스의 크기가 페이지의 배수가 아니기 때문)
- 하나의 페이지 크기보다 작은 크기로 발생.
- 페이지 크기를 너무 적게 설정하면 페이지 테이블의 크기가 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비된다.
해결방법 : 내부 단편화를 적당히 방지하면서 너무 크지않은 페이지 테이블이 만들어 지도록 페이지의 크기를 조정한다.
페이지 테이블 베이스 레지스터(PTBR)
- 각 프로세스의 페이지 테이블 위치(주소)를 가리키는 레지스터
- MMU(Memory Management Unit)가 논리 주소를 물리 주소로 변환할 때 해당 페이지 테이블에 접근한다.
페이지 테이블이 메모리에 있을 경우, CPU에서 메모리로의 두 번 접근하기 때문에 메모리 접근 시간이 두 배 소요 된다.
⇒ TLB 사용
TLB(Translation Look-aside Buffer)
- MMU 내에(CPU 곁) 존재하는 페이지 테이블의 캐시 메모리
- TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용 저장한다.
- 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와서 저장한다.
캐싱 원리는 참조 지역성(Principle of Locality)의 원리를 기반으로 한다.
이를 활용하여, 최근에 접근된 데이터나 그 주변 데이터를 미리 캐시에 저장함으로써, 다음에 같은 데이터에 접근할 때 더 빠른 속도로 데이터에 접근할 수 있도록 한다.
참조 지역성은 프로그램 실행 도중 메모리의 특정 부분이 집중적으로 사용된다는 관찰에 근거한 개념이다. 이 원리는 두 가지 형태로 나타난다:
- 시간 지역성(Temporal Locality): 한 번 참조된 데이터는 가까운 미래에 다시 참조될 가능성이 높다는 원리. 예를 들어, 루프 내에서 반복적으로 사용되는 변수가 이에 해당한다.
- 공간 지역성(Spatial Locality): 메모리 상에서 서로 인접한 위치에 있는 데이터들이 연속적으로 참조될 가능성이 높다는 원리이다. 예를 들어, 배열을 순차적으로 접근하는 경우가 이에 해당한다.
- CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 존재 여부
- 있을 경우, TLB히트 : 페이지가 적재된 프레임을 알기 때문에 메모리 접근 불필요
- 없을 경우, TLB 미스 : 메모리내에 페이지 테이블 접근 필요
TLB |
---|
|
페이징에서의 주소 변환
하나의 페이지 혹은 프레임은 여러 주소를 포함 하기 때문에, 특정 주소에 접근하려면 두 가지 정보 필요하다.
- 어떤 페이지 혹은 프레임에 접근하고싶은지
- 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
- 논리주소 = 페이지 번호 + 변위
- ex) CPU가 32비트 주소를 내보냈다. 이 중 N 비트는 페이지 번호, 32-N비트는 변위
- 페이지 번호 : 접근하고자 하는 페이지 번호
- 변위 : 접근하려는 주소가 프레임의 시작 번지로부터 얼마나 떨어져 있는지에 대한 정보
논리 주소 <페이지 번호, 변위>
는 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>
로 변환 된다.
페이지 테이블 엔트리
페이지 테이블의 각각의 행들을 페이지 테이블 엔트리라한다.
페이지 테이블 엔트리에는 페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트들의 정보가 있다.
- 유효 비트(valid bit)
- 접근하려는 페이지가 보조기억장치에 있는지, 메모리에 있는지
-
1 : 해당 페이지가 실제 메모리에 적재되어 있음을 의미한다. 따라서, CPU는 해당 페이지에 직접 접근할 수 있다.
-
0 : 페이지가 메모리에 적재되어 있지 않음을 나타낸다. 이 경우, 접근하려는 페이지가 보조기억장치(예: 하드 드라이브)에 있으므로, 시스템은 다음 단계를 따라 페이지 폴트 처리 과정을 진행한다:
페이지 폴트 처리 과정
- 기존 작업 내역 백업: 현재 CPU 상태를 저장하여 나중에 작업을 재개할 수 있도록 한다.
- 페이지 폴트 루틴 실행: 운영 체제는 페이지 폴트 핸들러 또는 루틴을 실행하여, 접근하려는 페이지를 보조기억장치에서 찾아 메모리로 적재한다.
- 유효 비트 1로 변경: 페이지가 메모리에 성공적으로 적재되면, 페이지 테이블 내 해당 페이지의 유효 비트를 1로 변경하여, 이제 메모리에 존재함을 표시한다.
- 접근하려는 페이지 접근: 이제 CPU는 페이지에 접근하여 필요한 작업을 계속 진행할 수 있다.
- 보호 비트(protection bit)
- 페이지에 접근할 권한을 제한하여 페이지를 보호하는 비트
- 접근하려는 페이지의 'r', 'w', 'x' 권한이 페이지 단위로 적용된다.
- r(Read) : 읽기 가능한 페이지
- w(Write) : 쓰기 가능한 페이지
- x(eXecute) : 실행 가능한 페이지
- 참조 비트(reference bit)
- 접근한적이 있는 페이지 있는지 확인
- 1 : 적재 이후 CPU가 읽거나 쓴 페이지
- 0 : 적재 이후 한 번도 접근한 적이 없는 페이지
- 주로 페이지 교체 알고리즘에서 사용된다.
- 수정 비트 (modify bit / dirty bit)
- 쓰기 작업을 한 적 있는 페이지 인지
- 1 : 수정한 적 있는 페이지
- 보조기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내용이 서로 다른값을 가진다.
- 변경 된 값을 보조기억장치에 기록하는 작업이 추가로 필요하다.
- 0 : 수정한 적 없는 페이지
- 페이지가 스왑 아웃될 때 수정되었는지 여부를 나타내므로, 수정된 페이지만 보조기억장치에 다시 쓰기 위해 사용된다.
- 주로 페이지 교체 알고리즘에서 사용된다.
페이징의 이점
- 외부 단편화 문제 해결
- 프로세스 간에 페이지를 공유할 수 있다. ⇒ 쓰기 시 복사 (copy on write)
멀티프로세스에서
- 프로세스를 fork하여 동일한 프로세스 두 개가 복제되면 코드 및 데이터 영역을 비롯한 모든 자원이 복제되어 메모리에 적재된다.
- 프로세스를 통째로 메모리에 중복 저장하지 않으면서 프로세스끼리 자원을 공유하지 않는 방법도 있다.
- 부모 프로세스의 메모리 영역이 다른 영역에 자식 프로세스로서 복제되고, 각 프로세스의 페이지 테이블은 자신의 고유한 페이지가 할당된 프레임을 가리킨다.
- 이는, 생성 시간을 늦추고 불필요한 메모리 낭비를 야기한다.
쓰기 시 복사
- 부모 프로세스와 동일한 자식 프로세스가 생성되면,
- 자식 프로세스가 부모 프로세스와 동일한 프레임을 가리킨다.
- 굳이 부모 프로세스의 공간을 복사하지 않고 동일한 코드 및 데이터 영역을 가리킬 수 있다.
- 프로세스 간에는 자원을 공유하지않기 때문에 쓰기 작업을 하게 되면, 그 수간 해당 페이지가 별도의 공간으로 복제된다.
- 각 프로세스는 자신의 고유한 페이지가 할당된 프레임을 가리킨다.
계층적 페이지
프로세스를 이루는 모든 페이지 엔트리를 메모리에 두는 것은 메모리 낭비로, 항상 메모리에 유지않지 않을 수 있는 방법
- 페이지 테이블을 페이징하여 여러 단계 페이지를 두는 방식
- 메모리 관리의 복잡성을 줄이고, 물리적 메모리 사용을 더 효율적으로 만든다
- 큰 주소 공간을 관리할 때 발생할 수 있는 메모리 낭비를 줄이는 데 도움이 된다.
3) 페이지 교체와 프레임 할당
요구페이징
처음부터 모든 페이지를 적재하지 않고 필요한 페이지만(페이지 폴트가 발생하면)을 메모리에 적재하는 기법
- CPU가 특정 페이지에 접근하는 명령어 실행
- 유효 비트가 1일 경우, CPU는 페이지가 적재된 프레임에 접근
- 유효 비트가 0일 경우, 페이지 폴트 발생
- 페이지 폴트 처리 루틴은 해당 페이지를 메모리를 적재하고 유효 비트를 1로 설정
- 다시 1 번을 수행
순수 요구 페이징
- 아무 페이지를 적재하지 않고 실행
- 첫 명령어 실행부터 페이지 폴트
- 적당한 페이지가 적재된 이후부터 페이지 폴트 감소
물리 메모리가 크면 근본적으로 해결
- 프레임이 무한히 많은 메모리 : 무한히 많은 페이지 적재 가능
- 프레임이 한 개 있는 메모리 : 페이지 접근할 때마다 페이지 폴트
스레싱
- 프로세스 실행 시간 보다 페이징에 더 많은 시간이 소요되는 문제
- 지나친 페이지 폴트로 인해 페이지 교체에 너무 많은 시간을 소요하여 성능이 저하되는 문제
- 동시 실행되는 프로세스를 늘린다 해서, 반드시 CPU 이용률이 비레하여 높아지는 것이 아니다.
- 메모리에서 동시에 실행되는 프로세스의 수 == 멀티프로그래밍의 정도
- 해결법 : 많은 물리 메모리(프레임)를 확보할 수 없다면 페이지 폴트를 줄인다.
- 보조기억 장치로 내보낼 페이지 / 메모리에 적재할 페이지를 잘 선별 할 것 == 페이지 교체 알고리즘
- 발생원인 : 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장 되지않았기 때문
- 균등 할당 : 모든 프로세스에 동일한 프레임을 배분하는 방식
- 비례 할당 : 프로세스 크기에 따라 프레임을 배분하는 방식
- 프로세스 크기가 작아도 실행해보니 많은 프레임을 필요로 하는 경우가 있다.
- 프로세스 실행하는 과정에서 배분할 프레임을 결정하는 방식(동적 할당 방식)
- 작업 집합 모델 : 프로세스가 일정 기간 동안 참조한 페이지의 집합을 기억, 작업 집합의 크기만큼만 프레임을 할당하는 방식
- 페이지 폴트 빈도 : 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위안에서만 프레임을 할당하는 방식
페이지 교체 알고리즘
- 메모리에 적재된 페이지 중 페이지-아웃시킬 페이지를 선정하는 방법
- 좋은 페이지 교체 알고리즘은 페이지 폴트를 적게 일으키는 알고리즘
페이지 폴트를 적게 일으키는 것을 알 수 있는 방법
- 페이지 참조열 : CPU가 참조하는 페이지 중 연속된 페이지를 생략한 페이지열
- 중복된 페이지를 참조하는 것은 페이지 폴트를 발생시키지 않기 때문에 연속된페이지를 생략
- 참조한 페이지 : 2 2 2 3 5 5 5 3 3 7
- 페이지 참조열 : 2 3 5 3 7
FIFO 페이지 교체 알고리즘
가장 먼저 메모리에 적재된 페이지부터 페이지-아웃
- 문제 : 초기에 적재된 페이지 중 프로그램 실행 내내 유지할 데이터가 있을 수 있다.
2차 기회 FIFO 페이지 교체 알고리즘
FIFO 페이지 교체 알고리즘의 변형
- 기본적으로 가장 오래 메모리에 머물렀던 페이지부터 페이지-아웃
- 다만 참조 비트가 1일 경우, 이를 0으로 변경 후 한번 더 기회 부여
- 참조 비트가 0일 경우 페이지-아웃
최적 페이지 교체 알고리즘
앞으로의 사용 빈도가 가장 낮은 페이지부터 교체하는 알고리즘
- 앞으로 쓸 일이 잘 없는 페이지
- 가장 낮은 페이지 폴트 빈도율을 보장하는 알고리즘
- 문제 : CPU가 어떤 페이지를 얼마나 참조할지 예측하기란 매우 어렵다.
- 이론적으로 페이지 교체 알고리즘의 성능을 평가할 때 주로 사용되는 알고리즘
LRU 페이지 교체 알고리즘
- 가장 적게 참조할 페이지는 예측하기 어려워도 계산하기가 쉽다.
- 최근에 사용되지 않은 페이지를 페이지-아웃
6주차 미션
진도: Chapter 14 ~ 15
기본 미션: p. 400의 확인 문제 1번 풀고 인증하기
선택 미션: Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기
기본 미션 : p. 400의 확인 문제 1번 풀고 인증하기
선택 미션: Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기
사용할 수 있는 프레임 : 3개
페이지 참조열 : 2 3 1 3 5 2 3 4 2 3
LRU페이지 교체 알고리즘 : 가장 오랫동안 사용되지 않은 페이지를 교체
페이지 참조열 | 2 | 3 | 1 | 3 | 5 | 2 | 3 | 4 | 2 | 3 |
---|
프레임1 | 2 | 2 | 2 | 2 | 5 | 5 | 5 | 4 | 4 | 4 |
프레임2 | | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
프레임3 | | | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
보조기억장치 | | | | | 2 | 1 | | 5 | | |
페이지 폴트 발생 | | | | | 발생 | 발생 | | 발생 | | |
페이지 폴트는 총 3번 발생한다.
6주차 회고