연속 메모리 할당

😎 프로세스들을 메모리에 연속적으로 할당할 때
무엇을 고려해야 하고, 어떤 잠재적 문제가 있는지 알아보자

스와핑

: 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고, 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법

스왑 영역 : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역

스왑 아웃 : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것

스왑 인 : 스왑 영역에 있던 프로세스가 다시 메모리고 옮겨지는 것

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

프로세스 A, B, C, D의 크기를 합하면 메모리의 크기보다 큰 상황이 있습니다.
➡️ 스와핑을 통해 네 개의 프로세스를 동시에 실행할 수 있습니다.

메모리 할당

프로세스는 메모리의 빈 영역에 적재되어야 합니다.

메모리 내에 빈 공간이 여러개 있다면 어디에 배치해야 할까요?

👉 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식을 알아봅시다.

⚠️ 20MB 크기의 프로세스를 적재하고 싶습니다. 메모리의 사용자 영역은 총 200MB입니다.
프로세스를 적재할 수 있는 빈 공간은 A, B, C 세 군데가 있습니다.

최초 적합

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

최적 적합

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

최악 적합

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

외부 단편화

🔥 연속 메모리 할당은 메모리를 효율적으로 사용하는 방법이 아닙니다.
외부 단편화라는 문제를 내표하고 있습니다.

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

외부 단편화를 해결 할 수 있는 방법에는 메모리를 압축하는 방법이 있습니다.
흩어져 있는 빈 공간들을 하나로 모으는 방식입니다.

하지만. 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 합니다.

또 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기합니다.
➡️ 또 다른 해결 방안으로 페이징 기법이 등장했습니다.

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

🔥 연속 메모리 할당의 두 가지 문제
1. 외부 단편화
2. 물리 메모리보다 큰 프로세스를 실행할 수 없다.

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

이를 가능하게 하는 가상 메모리 관리 기법에는 페이징과 세그멘테이션이 있습니다.

페이징이란

외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문입니다.

🙂 메모리와 프로세스를 일정한 단위로 자르고, 이를 메모리에 불연속적으로 할당한다면 외부 단편화가 발생하지 않겠죠?

페이징
: 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법

페이징에서도 스와핑을 사용할 수 있습니다.
여기서는 프로세스 전체가 스왑 아웃/스왑 인 되는 아니라 페이지 단위로 스왑 아웃/스왑 인 된다.
페이징에서 스왑 아웃은 페이지 아웃, 스왑 인은 페이지 인으로 부르기도 합니다.

프로세스를 이루는 페이지 중에서 실행에 필요한 일부만 메모리에 적재하고, 필요하지 않은 페이지는 보조기억 장치에 남겨둘 수 있습니다.

➡️ 물리 메모리보다 더 큰 프로세스를 실행할 수 있습니다.

페이지 테이블

그런데! 프로세스가 메모리에 불연속적으로 배치되어 있으면 CPU는 순차적으로 실행할 수 없어요

이를 해결하기 위해 (실제 메모리 내의 주소인) 물리 주소에는 불연속적으로 배치되더라도
(CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 이용합니다.

페이지 테이블은 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표입니다.

CPU가 페이지 번호만 보고 프레임 번호를 찾을 수 있게 해줍니다.

물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보일 수 있습니다. CPU는 논리 주소를 그저 순차적으로 실행하면 됩니다.

😎 내부 단편화
페이징은 외부 단편화를 해결할 수 있지만, 내부 단편화가 발생할 수 있어요.

페이징은 프로세스의 논리 주소 공간을 페이지라는 단위로 나눕니다.
그런데 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것이 아닙니다.

내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생합니다.

프로세스마다 각자의 프로세스 테이블을 가지고 있고, 이 테이블들은 메모리에 적재되어 있어요.

그리고, CPU 내의 페이지 테이블 베이스 레지스터(PTBR)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있어요.

그런데! 이렇게 페이지 테이블을 메모리에 두면 문제가 있어요.

메모리 접근 시간이 두배로 늘어난다. 페이지 테이블을 보기 위해, 프레임에 접근하기 위해

이를 해결하기 위해 CPU 곁에(일반적으로 MMU내에) TLB라는 페이지 테이블의 캐시 메모리 를 둡니다. 참조 지역성에 근거해 최근에 사용된 페이지 위주로 가져와 저장합니다.
TLB = Translation Lookaside Buffer

TLB 히트 : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우

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

페이징에서의 주소 변환

특정 주소에 접근하려면 두 가지 정보가 필요합니다.

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

페이징 시스템에서는 논리 주소가 페이지 번호와 변위(offset)으로 이루어져 있어요.

• 페이지 번호 : 접근하고자 하는 페이지 번호
  페이지 테이블에서 해당 페이지 번호를 찾으면 어떤 프레임에 할당되었는지 알 수 있다.

• 변위 : 접근하려는 주소가 프레임의 시작 번지부터 얼만큼 떨어져 있는지의 정보

➡️ 논리주소<페이지 번호, 변위>는 물리주소<프레임 번호, 변위>로 변환됩니다.

페이지 테이블 엔트리

: 페이지 테이블의 각 행

페이지 테이블 엔트리에는 페이지 번호, 프레임 번호 이외에도 다른 중요한 정보가 있습니다.

유효 비트 (valid bit)

: 현재 해당 페이지에 접근 가능한지 여부

프로세스의 모든 페이지가 메모리에 존재하는 것이 아닙니다. 일부 페이지는 스왑 영역에 있는 경우가 많습니다.

현재 페이지가 메모리에 적재되어 있는지 보조기억장치에 있는지 알려주는 비트입니다.

메모리에 적재되어 있다면 유효 비트가 1, 적재되어 있지 않다면 유효 비트가 0이 됩니다.

여기서! 유효비트가 0인 페이지로 접근하려고 하면 페이지 폴트라는 예외가 발생합니다.

😎 CPU가 페이지 폴트를 처리하는 과정
1. CPU는 기존의 작업 내역을 백업한다.
2. 페이지 폴트 처리 루틴을 실행한다.
3. 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경한다.
4. CPU는 이제 해당 페이지에 접근할 수 있다.

보호 비트 (protection bit)

: 페이지에 접근할 권한을 제한하여 페이지를 보호하는 비트

해당 페이지의 읽기/쓰기 모드를 확인 할 수 있습니다.

0일 경우 읽기만 가능한 페이지이고, 1일 경우 읽기/쓰기가 모두 가능한 페이지입니다.

세 개의 비트로 더 복잡하게 구현도 가능합니다. 읽기(r), 쓰기(w), 실행(x)의 조합으로 나타낸다.

참조 비트 (reference bit)

: CPU가 이 페이지에 접근한 적이 있는지 여부

적재 이후 CPU가 읽거나 쓴 페이지는 1로, 적재 이후 한 번도 읽거나 쓴 적이 없으면 0

수정 비트 (modified bit)

: 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부
더티 비트라고도 부른다.

1이면 변경된 적이 있는 페이지. 0이면 변경된 적이 없는 페이지입니다.

페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야하는지 판단하기 위해 존재합니다.
CPU는 메모리를 읽기도 하지만 메모리에 값을 쓰기도 합니다.
CPU가 쓰기 작업을 한 페이지는 보조기억장치에 저장된 내용과 다른 값을 가지게 됩니다.

페이지 교체와 프레임 할당

요구 페이징

: 프로세스를 메모리에 적재할 때 필요한 페이지만을 메모리에 적재하는 기법

요구 페이징의 기본적인 양상
1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2. 해당 페이지가 현재 메모리에 있으면 CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현재 메모리에 없으면 페이지 폴트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고, 유효 비트를 1로 설정한다.
5. 다시 1번을 수행한다.

순수 요구 페이징
: 아무런 페이지도 메모리에 적재하지 않은 채로 무작정 실행한다. 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하고, 실행에 필요한 페이지가 메모리에 어느 정도 적재되면 페이지 폴트 발생 빈도가 떨어진다.

요구 페이징 시스템이 안정적으로 작동하기 위해 두 가지를 해결해야 합니다.

• 페이지 교체
• 프레임 할당

페이지 교체 알고리즘

요구 페이징 기법으로 메모리에 페이지를 적재하다보면 언젠가는 메모리가 가득 차게 된다.

당장 실행에 필요하지 않은 페이지는 보조기억장치로 내보내야 한다. 어떤 페이지를 내보내야 할까?

페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 페이지 교체 알고리즘으로 평가한다.

페이지 교체 알고리즘을 이해하려면 페이지 폴트 횟수를 알 수 있어야 한다. 그리고 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있습니다.

페이지 참조열 : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
CPU가 아래와 같은 순서로 페이지에 접근했습니다.

2 2 2 3 5 5 5 3 3 7

➡️ 페이지 참조열은 다음과 같습니다.

2 3 5 3 7

FIFO 페이지 교체 알고리즘

: 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식

다음과 같은 페이지 참조열이 있습니다.

2 3 1 3 5 2 3 4 2 3

😎 2차 기회 페이지 교체 알고리즘
참조 비트가 1이면, 당장 내쫓지 않고 참조 비트를 0으로 만든다.
참조 비트가 0이면 보조기억장치로 내보낸다.

최적 페이지 교체 알고리즘

: 앞으로 사용 빈도가 가장 낮은 페이지를 교체

다음과 같은 페이지 참조열이 있습니다.

2 3 1 3 5 2 3 4 2 3

앞으로 오랫동안 사용하지 않을 페이지를 예측하는 것을 어렵기 때문에 실제 구현이 어렵다.

LRU 페이지 교체 알고리즘

: 가장 오랫동안 사용되지 않은 페이지를 교체

다음과 같은 페이지 참조열이 있습니다.

2 3 1 3 5 2 3 4 2 3

스래싱과 프레임 할당

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

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

그래프로 스래싱을 표현해 봅시다.

세로축은 CPU 이용률 입니다.
CPU 이용률이 높다는 것은 CPU가 일을 쉬지 않고 하고 있다는 것입니다.

가로축은 멀티프로그래밍의 정도입니다.
이 값이 높으면 현재 메모리에서 많은 프로세스가 동시에 실행 중이라는 것입니다.

스래싱은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않아서 발생합니다.
따라서 운영체제는 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 할당해 줄 수 있어야 합니다.

프레임 할당 방식

정적 할당 방식

: 프로세스의 실행 과정은 고려하지 않고 프로세스의 크기와 물리 메모리 크기만 고려한 방식

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

• 비례 할당
  : 프로세스의 크기에 따라 크기가 크면 프레임을 많이 할당하고, 크기가 작으면 프레임을 적게 나눠주는 방식
  

동적 할당 방식

: 프로세스의 실행을 보고 할당할 프레임의 수를 결정하는 방식

• 작업 집합 모델
  : 작업 집합의 크기만큼 프레임을 할당한다.
  작업 집합 : 프로세스가 일정 시간 동안 참조한 페이지의 집합
  프로세스는 특정 시간동안 몇몇개의 페이지만 집중적으로 참조하게 된다.
  ➡️ CPU가 특정 시간동안 주로 참조한 페이지 개수만큼만 프레임을 할당한다.

• 페이지 폴트 빈도
  : 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식
  한 프로세스에 할당된 프레임 수와 페이지 폴트율은 반비례 관계를 보인다.
  
  여기에 임의로 상한선과 하한선을 그린다.
  
  페이지 폴트율이 상한선보다 높아지면 프레임을 더 할당해준다.
  페이지 폴트율이 하한선보다 낮아지면 프레임을 회수한다.