Aivle Cs 스터디 가상 메모리

Posted May 22, 2023 Updated Dec 12, 2024

By Changjin Kang

views 29 min read

Aivle Cs 스터디 가상 메모리

title: [AIVLE CS 스터디] 가상 메모리 date: 2023-05-22 13:35:06.350 +0000 categories: [AIVLE] tags: [‘cs 스터디’] description: 에이블러와 함께하는 CS 스터디 7주차 - 1 image: /assets/posts/2023-05-22-aivle-cs-스터디-가상-메모리/thumbnail.png

스터디 설명 : 에이블스쿨 교육생들과 CS 공부를 위해 자발적으로 개설 및 참여한 스터디입니다.
혼자 공부하는 컴퓨터 구조+운영체제를 교재로 사용하였고, 일부 내용은 별도의 자료로 공부하였습니다.

14-1. 연속 메모리 할당

지금까지는 메모리 내에 프로세스들이 연속적으로 배치되어 있는 (프로세스 사이에 빈 공간이 없는) 상황을 가정했다. 이러한 할당 방식을 연속 메모리 할당이라고 한다.

스와핑

스와핑(swapping) : 프로세스가 대기 상태가 되었거나, 오랫동안 사용되지 않았을 경우 메모리 공간 확보를 위해 프로세스들을 임시로 보조기억장치에 저장하고, 다른 프로세스를 메모리에 적재하여 실행하는 것
스왑 영역 : 메모리로부터 옮겨진 프로세스들이 저장되는 보조기억장치의 일부 영역
- 스왑 인 : 스왑 영역에 있던 프로세스가 다시 메모리로 적재되는 것
- 스왑 아웃 : 실행되지 않는 프로세스가 스왑 영역으로 옮겨지는 것
스와핑의 장점 : 전체 프로세스에 할당해야하는 메모리의 크기가, 실제 메모리 보다 큰 경우에도 프로세스들을 동시에 실행할 수 있다.
리눅스에서 free 명령어를 통해 현재 메모리의 사용량, 가용 용량 및 스왑 영역의 크기까지 확인할 수 있다.

메모리 할당 (연속 메모리 할당 방식)

메모리 공간에 프로세스를 연속적으로 할당하는 방법은 크게 3가지가 있다.

최초 적합

메모리의 빈 공간을 탐삭하다 최초로 발견한 적재 가능한 공간에 프로세스를 배치
장점 : 검색을 최소화하여 빠른 할당이 가능

최적 적합

모든 메모리의 빈 공간을 탐색 후 적재가 가능하면서 최소 크기인 공간에 프로세스를 배치
장점 : 가장 효율적인 메모리 사용가능

최악 적합

모든 메모리의 빈 공간을 탐색 후 적재가 가능하면서 최대 크기인 공간에 프로세스를 배치
빈 공간이 많이 남는 곳에 적재하면 그 빈공간에 다른 것도 적재할 수 있을 확률이 높다는 아이디어를 담고 있는 방식이다.

외부 단편화(External fagmentation) 문제

연속 메모리 할당의 문제점은 외부 단편화라는 문제로 인해 메모리를 효율적으로 사용할 수 없다는 점이다.
외부 단편화란 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 전체 메모리의 공간이 낭비되는 현상을 말한다.
- 프로세스가 실행되고 종료되는 과정에서 발생하는 빈 공간이 점점 파편화 되어 메모리의 낭비가 발생하게 된다.

압축

외부 단편화를 해결할 수 있는 방법으로, 빈 공간이 없도록 프로세스를 재배치하여 하나의 큰 공간만을 남긴느 방법이다.
프로세스를 재배치하기 위해 프로세스의 실행을 중지해야하고, 메모리 입출력 과정에서 많은 오버헤드를 야기한다.

결론적으로 압축을 대체하여 새롭게 외부 단편화를 없앨 수 있는 해결 방안으로 페이징 기법이 등장하여 가장 널리 활용되고 있다.

14-2. 페이징을 통한 가상 메모리 관리

가상 메모리 : 실행하고자 하는 프로그램의 일부만 메모리에 적재하여 메모리를 덜 사용하는 기술이다.
가상 메모리 관리 기법에는 페이징과 세그멘테이션이 있는데, 현대 대부분 운영체제에서는 페이징 기법을 사용한다.

페이징이란

외부 단편화가 발생하는 이유는 프로세스 별로 서로 다른 메모리 공간을 차지하기 때문이다. 페이징은 프로세스를 일정한 단위를 자르고, 이를 메모리에 불연속적으로 할당한다.
- 페이지 : 프로세스의 논리 주소 공간을 자르는 일정한 단위
- 프레임 : 메모리를 페이지 단위로 잘랐을 때 각 공간
- 페이징은 프로세스를 페이지 단위로 잘라 각 프레임에 할당하는 기법이다.

페이징 스와핑

페이징 기법에서도 스와핑을 사용할 수 있다.
프로세스 전체가 스왑 아웃/스왑 인 되는 것이 아니라, 페이지 단위로 이루어진다.
결과적으로 프로세스를 실행하면서도 실행되지 않는 부분을 부분적으로 스와핑할 수 있게 된다. → 메모리의 효율적인 사용 + 메모리의 물리적 크기보다 큰 프로세스 실행 가능
페이징 시스템에서 스왑 아웃/스왑 인을 페이지 아웃/페이지 인이라고 한다.

페이지 테이블

페이징 기법을 사용하면 하나의 프로세스가 메모리 내에 불연속적으로 적재되기 때문에 CPU가 프로그램 카운터를 통해 순차적으로 실행하는 것이 어렵다.
이를 해결하기 위해 페이지 테이블(page table)을 이용한다.
- 페이지 테이블은 CPU 입장에서 프로세스의 주소가 연속적으로 보일 수 있도록 불연속적인 물리 주소를 연속적인 논리 주소로 맵핑한 데이터이다.
하지만 페이지 테이블도 결국 메모리 공간을 차지하기 때문에, 페이지 테이블이 너무 많을 경우 역시 메모리 낭비가 발생할 수 있다.

페이지 테이블 베이스 레지스터(PTBR : Page Table Base Register)

CPU가 알 수 있도록 페이지 테이블이 적재된 주소를 저장하는 레지스터이다.
각 프로세스가 실행될 때 해당 프로세스의 페이지 테이블 주소를 PTBR에 저장하여 CPU가 해당 주소를 참조하도록 한다.
하지만 이 경우 1. 메모리로부터 페이지 테이블 접근하여 실제 주소 확인 → 2. 실제 주소에서 프로세스 데이터를 가져와 연산 이렇게 메모리 접근 시간이 두 배로 늘어나게 된다.

TLB(Translation Lookaside Buffer)

CPU 곁에 (일반적으로 MMU 내에) TLB라는 캐시 메모리를 두어 페이지 테이블의 일부 내용을 저장한다.
참조 지역성에 의해 가장 최근의 사용된 페이지 위주로 저장하며, 이를 통해 메모리 접근 없이 페이지 테이블을 참조할 수 있다.
- 참조 지역성 : 어떤 코드나 데이터를 한번 사용하면, 짧은 시간내에 같은 코드 및 데이터에 자주 액세스하게 되는 특성이다. 공간 지역성, 시간 지역성, 순차 지역성의 3가지 하위 항목으로 나뉜다.
TLB도 캐시 메모리인 만큼 TLB 히트와 TLB 미스가 발생한다.

내부 단편화(Internal fagmentation)

페이징 기법은 외부 단편화 문제를 해결 가능하지만, 내부 단편화 문제를 야기할 수 있다.
내부 단편화란, 하나의 페이지를 모두 사용하지 않음으로써 발생하는 메모리 낭비이다.
원인 : 모든 프로세스의 크기가 페이지의 배수가 아니기 때문에, 101KB를 10KB 단위로 자를 경우 마지막 페이지에서는 9KB의 메모리 낭비가 발생한다.
페이지 단위가 클 수록 내부 단편화가 많이 발생하며, 페이지 단위가 작을 수록 페이지 테이블로 인한 메모리 낭비가 많이 발생한다. 결국 적절한 페이지 단위를 찾는 것이 중요하다.

페이징에서의 주소 변환

페이지를 통해 프로세스의 특정 주소를 접근하기 위해서는 두 가지 정보가 필요하다.
1. 접근할 페이지 또는 프레임 → 페이지 번호
2. 접근하려는 주소가 페이지 또는 프레임에서 얼마나 떨어져 있는지 → 변위(offset)
때문에 페이징 기법에서 사용하는 주소 데이터는 페이지 번호 부분과 변위 부분 두가지로 구성된다.

페이지 테이블 엔트리(PTE; Page Table Entry)

페이지 테이블 엔트리 : 페이지 테이블 내의 각각의 행을 말한다.
페이지 테이블의 한 행은 페이지 번호(논리주소), 프레임 번호(실제주소), 유효 비트, 보호 비트, 참조 비트, 수정 비트로 구성된다.

유효 비트(vaild bit)

현재 해당 페이지에 접근 가능한지 여부를 알려준다.
페이지 스와핑으로 인해 일부 페이지는 보조기억장치의 스왑 영역에 존재할 수 있다. 유효 비트는 해당 페이지가 메모리에 있는지 스왑 영역에 있는지 알려주는 비트이다.
유효 비트가 0인 페이지에 접근하려 할 경우 페이지 폴트(page fault)라는 예외(Exception)가 발생한다.
- 페이지 폴트 처리 과정(인터럽트 처리와 유사)
  1. 기존의 작업 내역 백업
  2. 페이지 폴트 처리 루틴 실행 - 필요한 페이지를 메모리로 가져온 뒤 유효비트 1로 변경
  3. 다시 작업 내역을 불러와 해당 페이지에 접근하여 처리

보호 비트(protection bit)

페이지가 read만 가능한지, read와 write 모두 가능한지를 표시하는 비트이다.
보호 비트를 토대로 읽기 전용 페이지에 쓰기를 시도할 경우 운영체제가 이를 막아줄 수 있다.
읽기(r), 쓰기(w), 실행하기(x)의 3개 비트로도 나타낼 수 있다.
- 실행만 가능 : 0 0 1
- 읽기와 실행만 가능 : 1 0 1

참조 비트(reference bit)

메모리에 적재된 이후 한 번이라도 CPU가 접근한 적이 있는지 여부를 나타내는 비트이다.
참조 비트는 페이지 교체 알고리즘에서, 해당 페이지를 교체할지 말지 판단하는 정보로 쓰인다.

수정 비트(modified bit)

더티 비트(dirty bit)라고도 부른다.
해당 페이지가 적재 이후 수정 되었는지 여부를 알려준다.
수정 비트를 통해 페이지가 메모리에서 사라질 때(종료 혹은 스왑 아웃) 보조기억장치에 쓰기 작업을 해야하는지 여부를 판단할 수 있다.

실제 페이지 테이블은 이것 외에 다양한 정보가 있다. 관심이 있다면 교재에서 제공되는 깃허브 페이지를 참조하자

Copy on write

페이징의 또 다른 이점으로 프로세스간 페이지를 공유하는 Copy on write(쓰기 시 복사)라는 개념을 사용할 수 있다.
기존 멀티프로세스에서는 동일한 데이터라도 무조건 똑같이 복제하여 사용해야 한다.
- 부모 프로세스에서 자식 프로세스를 생성할 경우 복제된 별도의 메모리 생성 및 사용
하지만 Copy on write를 이용하면, 자식 프로세스는 부모 프로세스의 페이지 테이블만 복제하고, 실제 메모리 영역은 공유하여 사용할 수 있다.
이 상황에서 공유하는 페이지에 변경이 생길 경우, 해당 페이지만 별도의 공간에 복제하여 구분하는식으로 메모리를 효율적으로 상요하며, 프로세스 생성 시간도 줄일 수 있다.

계층적 페이징(Hierarchical Paging)

페이지 테이블은 생각보다 정말 많기 때문에, 페이지 테이블의 크기도 크다. 이 때 모든 페이지 테이블 엔트리를 메모리에 두는 것은 메모리 낭비를 유발한다.
계층적 페이징은 모든 페이지 테이블 엔트리를 메모리에 유지하지 않도록 하는 방법이다.
- 페이지 테이블을 여러 개의 페이지 테이블로 자르고, outer 페이지 테이블만 메모리 공간에 적재한다.
- outer 페이지 테이블에는 총 3가지 정보가 저장된다.
  1. CPU가 바라보는 페이지 번호(바깥 페이지 테이블의 번호)
  2. 각 페이지 테이블의 실제 주소(안 쪽 페이지 테이블의 번호)
  3. 변위(페이지 또는 프레임으로 부터의 거리)
- 이는 두 개의 계층으로 계층적 페이징을 한 경우(2단계 페이징)이며 실제로는 보다 많은 계층으로 구성된다.

14-3. 페이지 교체와 프레임 할당

보다 메모리를 효율적으로 사용하기 위해, 운영체제는 기존 메모리에 적재된 불필요한 페이지를 선별하여 페이지 스와핑을 진행하여야 한다.

요구 페이징(Demand Paging)

요구 페이징 : 프로세스를 처음 메모리에 적재할 때, 일부 필요한 페이지 만을 메모리에 적재하는 기법
- 만약 CPU가 요청한 페이지가 메모리에 없을 경우 페이지 폴트를 통해 적재 후 실행한다.
순수 요구 페이징 : 프로세스를 하나도 적재하지 않고 실행하는 기법으로, 실행 초기에는 페이지 폴트가 빈번하게 발생하다, 어느 정도 적재 후에는 페이지 폴트 발생 빈도가 감소한다.
요구 페이징 시스템이 안정적으로 작동하기 위해서는 페이지 교체와 프레임 할당이 원활히 이루어져야 한다.
- 메모리가 가득 찼을 경우, 가장 필요없는 페이지를 찾아내어 스왑 아웃하는 알고리즘을 페이지 교체 알고리즘이라고 한다.

페이지 교체 알고리즘

좋은 페이지 교체 알고리즘의 평가 기준은 페이지 폴트이다.
- 알고리즘을 통해 페이지를 스왑 아웃해도 페이지 폴트가 자주 발생하지 않는 것이 좋은 알고리즘이다.
- 이를 위해 페이지 폴트 횟수를 알 수 있어야 한다.
페이지 참조열 : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
1 2 페이지 열 : [1 1 3 2 2 3 4 2 2 2 3 3 5] 페이지 참조열 : [1 3 2 3 4 2 3 5]
- 중복 페이지를 참조하는 행위는 페이지 폴트를 발생하지 않기 때문에 생략한다.

FIFO 페이지 교체 알고리즘

가장 먼저 메모리에 적재된 페이지를 스왑 아웃하는 알고리즘이다.
가용 프레임이 세 개 있다고 가정할 때 흐름은 다음과 같다.
FIFO페이지 교체 알고리즘은 계속 적재되어 실행되어야 할 프로세스를 고려하지 못한다는 것이다.

2차 기회 페이지 교체 알고리즘

FIFO의 변형 알고리즘으로, 가장 오래된 페이지의 참조 비트를 확인한다.
- 참조 비트가 1일 경우 : 참조 비트를 0으로 하고 스왑 아웃 하지 않음
- 참조 비트가 0일 경우 : 스왑 아웃
말 그대로 참조된 페이지일 경우 기회를 한 번 더 주는 것이다.

최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm)

CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
페이지 교체가 필요할 때 CPU 스케줄에서 앞으로 가장 적게 참조될 페이지를 교체한다.
페이지 교체 알고리즘 중 가장 낮은 페이지 폴트율을 보장한다.
그러나 현실적으로 앞으로 어떤 페이지가 얼마나 참조될 것인지 알기는 현실적으로 어렵다. 때문에 최적 페이지 교체 알고리즘은 실제 사용할 수 없고, 다른 교체 알고리즘의 이론 성능을 평가하기 위해 사용한다.

LRU 페이지 교체 알고리즘(LRU : Least Recently Used)

페이지 교체가 필요할 때 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘
LRU를 기반으로 한 다양한 파생 알고리즘이 있다.

스래싱과 프레임 할당

페이지 폴트가 발생하는 근본적인 이유는 메모리의 사용할 수 있는 프레임 수가 적기 때문이다.
프레임 수가 부족하면 필연적으로 페이지 교체도 자주 발생하는데, 프로세스의 실행보다 페이징에 더 많은 시간을 소모해 성능이 저하되는 문제를 스래싱(thrashing)이라고 한다.
- CPU가 페이지 교체 완료를 기다리느라 연산을 하지 못하면서 이러한 문제가 발생한다.
일반적으로 CPU의 이용률은 동시의 실행되는 프로세스의 수(멀티프로그래밍의 정도)에 따라 증가하다가 어느 순간 급격히 감소하는데, 이 구간이 바로 스래싱이 발생하는 구간이다.
- CPU의 성능이 아무리 좋아도 메모리가 부족하다면 전체 컴퓨터의 성능이 저하되는 원인이다.
스래싱의 근본적인 원인은 프로세스가 적재될 프레임 수가 부족하기 때문이다. 물리적으로 프레임을 늘릴 수 없다면, 운영체제가 적절하게 프레임을 할당해줄 수 있어야 한다.

정적 프레임 할당 방식

균등 할당(equal allocation)

모든 프로세스에 동일한 비율로 프레임을 할당한다.
프로세스 마다 필요한 공간이 다르기 때문에 권장되지 않는 방법이다.

비례 할당(proportional allocation)

프로세스의 크기에 비례해서 프레임을 할당한다.
프로세스가 커도 실제 사용하는 프레임은 많지 않을 수 있다. 즉 프로세스가 실제로 사용하는 프레임을 고려하지 않기 때문에 그다지 효율적인 방법이 아니다.

위 두가지 프레임 할당 방식을 정적 할당 방식이라고 한다.

동적 프레임 할당 방식

작업 집합 모델(working set model) 기반 프레임 할당

프로세스가 일정 시간 간격 동안 참조한 페이지 집합(작업 집합)을 기억해 CPU가 동일한 작업을 다시 실행할 때 최소한 그 간격 동안 참조했던 페이지만큼은 전부 프레임에 할당하는 방식

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

어떤 프로세스의 페이지 폴트율이 높으면, 필요한 것보다 적은 프레임을 할당받고 있고, 반대로 어떤 프로세스의 페이지 폴트율이 낮으면 많은 프레임을 할당 받고 있다고 가정
페이지 폴트율의 상한선과 하한선을 설정하여 페이지 폴트율이 이 사이에서 유지되도록 각 프로세스에 프레임을 할당하는 방식이다.

This post is licensed under CC BY 4.0 by the author.