가상 메모리

연속 메모리 할당

프로세스에 연속적인 메모리를 할당하는 방식을 연속 메모리 할당 방식이라고 한다.

 

스와핑

오랫동안 사용되지 않은 프로세스들을 임시로 보조기억장치 일부 영역으로 쫒아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식을 스와핑이라고 한다.

 

이때 프로세스들이 쫒겨나는 보조기억장치의 일부 영역을 스왑 영역이라고 한다.

실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃이라고 한다.

스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인이라고 한다.

 

이때 스왑 인될 때 스왑 아웃되기 전의 물리 주소와 다른 주소에 적재될 수 있다.

 

프로세스들이 요구하는 메모리 공간 크기가 실제 메모리 크기보다 큰 경우

당장 실행될 필요가 없는 프로세스 B를 스왑 아웃 하고 프로세스 D를 적재한다.

이런 과정을 통해 실제 메모리 보다 큰 프로세스를 동시에 실행시킬 수 있다.

 

메모리 할당

대표적으로 최초 적합, 최적 적합, 최악 적합의 세 가지 방식이 존재한다.

최초 적합은 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 프로세스를 배치하는 방식이다.

검색을 최소화할 수 있고 결과적으로 빠른 할당이 가능하다.

 

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

 

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

 

외부 단편화

연속 메모리 할당은 외부 단편화 문제를 내포하고 있다.

프로세스 B, D가 종료되고 남아있는 빈 공간의 총합은 50mb이다.

그러나 위 공간에 50mb 크기의 프로세스를 적재할 수 있는지 보면 불가능하다.

 

총합은 50mb일지라도 어느 빈 공간에도 50mb 크기의 프로세스가 적재될 수 없기 때문이다.

 

이처럼 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이에 빈 공간들이 생긴다. 이런 공간보다 큰 프로세스를 적재하기 어려운 상황이기 때문에 결국 메모리 낭비가 생긴다. 이를 외부 단편화라고 한다.

 

스와핑 과정에서도 외부 단편화가 일어난다. 이를 해결하기 위해 메모리를 압축하는 방법이 있다.

 

메모리 내에 저장된 프로세스를 적당히 재배치시켜서 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법이다.

이를 메모리 조각 모음이라고도 한다.

 

그러나 문제점으로

• 시스템은 하던 일을 중지해야한다.
• 많은 오버헤드를 야기한다.
• 최소한의 오버헤드를 발생시키는 명확한 방식을 결정하기 애매하다.

 

연속 메모리 할당의 두 가지 문제점

외부 단편화 때문에 물리 메모리보다 큰 프로세스 실행 불가하다.

위 같은 경우 적재할 프로세스 용량이 메모리보다 크기 때문에 실행 불가능하다.

 

가상 메모리

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

 

페이징

프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고

메모리 물리 주소 공간을 프레임이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.

페이징을 사용하는 시스템에서는 프로세스 전체가 스왑 아웃/스왑 인되는 것이 아닌 페이지 단위로 스왑 아웃/ 스왑 인된다.

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

 

페이지 테이블

프로세스에 메모리가 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행할 수 없다.

그래서 이를 해결하기 위해 물리 주소에 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 이용한다.

물리 주소상에서 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보일 수 있다.

즉 CPU는 논리 주소를 그저 순차적으로 실행하면 된다.

 

내부 단편화

만약 페이지 크기가 10kb이고 프로세스 크기가 108kb인 경우

마지막 페이지는 2kb만큼의 크기가 남는다.

따라서 내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생한다.

• 페이지 크기가 작으면 발생하는 내부 단편화의 크기가 작아진다.
• 페이지의 크기를 너무 작게 설정하면 그만큼 페이지 테이블의 크기가 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비된다.

 

그래서 내부 단편화를 적당히 방지하면서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지 크기를 조정하는 것이 중요하다.

 

PTBR

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

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

 

프로세스 A가 실행될 때 PTBR은 프로세스 A의 페이지 테이블을 가리키고 CPU는 프로세스 A의 페이지 테이블을 통해 프로세스 A의 페이지가 적재된 프레임을 알 수 있다.

 

그러나 페이지 테이블을 메모리에 두면 메모리 접근 시간이 2배로 늘어난다는 문제가 있다.

(페이지 테이블 접근 1회, 프레임 접근 1회)

 

이를 해결하기 위해 CPU 곁에 TLM라는 페이지 테이블의 캐시 메모리를 둔다.

참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 저장한다.

 

만약 CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 이를 TLB 히트라고 부른다.

그러나 만약 페이지 번호가 TLB에 없다면 메모리 내의 페이지 테이블에 접근해야 한다. 이를 TLB 미스라고 한다.

 

페이징에서의 주소 변환

하나의 페이지, 프레임은 여러 주소를 내포하고 있다.

따라서 특정 주소에 접근하려면 아래와 같은 두 가지 정보가 필요하다.

 

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

 

그렇기에 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 이루어져있다.

페이지 번호, 변위로 이루어진 논리 주소는 페이지 테이블을 통해 프레임 번호, 변위로 변환된다.

5번 페이지에 접근한다면 프레임 번호는 1이다.

이때 물리 주소 공간은 8번지이고 변위가 2이므로 10번에 접근하게 된다.

 

페이지 테이블 엔트리

페이지 테이블의 각각의 행들을 페이지 테이블 엔트리라고 부른다.

유효 비트(valid bit)는 해당 페이지에 접근 가능한지 여부를 알려준다.

현재 페이지가 스왑 영역으로 가있는지 혹은 메모리에 올라와 있는지 확인해준다.

 

만약 CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면 페이지 폴트라는 예외가 발생한다.

이는 하드웨어 인터럽트를 처리하는 과정과 유사하다.

 

보호 비트(protection bit)는 페이지 보호 기능을 위해 존재하는 비트다.

• 0인 경우 읽기 전용
• 1인 경우 읽기 쓰기가 모든 가능한 페이지임을 나타낸다.

 

프로세스를 이루는 요소 중 코드 영역은 읽기 전용 영역이다.

이러한 읽기 전용 페이지에 쓰기를 시도하면 운영체제가 이를 막아준다.

보호 비트는 세 개의 비트로 조금 더 복잡하게 구현할 수도 있다.

 

참조 비트(reference bit)는 CPU가 이 페이지에 접근한 적이 있는지 여부를 나타낸다.

 

수정 비트(modified bit)는 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려준다. 이는 더티 비트(dirty bit)라고도 불린다.

 

수정 비트는 페이지가 메모리에 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지 판단하기 위해 필요하다.

 

만약 한번도 접근하지 않았거나 읽기만 한 페이지는 메모리와 보조기억장치에 저장된 내용이 같기 때문에 추가 작업 없이 새로 적재된 페이지로 덮어쓰기만 하면 된다.

 

수정된 페이지는 스왑 아웃될 때 보조기억장치에도 쓰기 작업을 거쳐야 한다.

수정 비트가 0이라면 굳이 반영할 필요가 없고 1이라면 반영해줘야 한다.

 

추가 페이징의 이점 + 계층적 페이징

fork의 경우 그저 복사된다.

 

수정된 작업만 복제하여 사용한다.

• 생성 시간 절약
• 메모리 절약

 

이를 다단계 페이지 테이블 기법이라고 부른다.

 

위 예시는 2단계 페이징이지만 더 계층적으로 구성될 수도 있다.

계층이 많으면 페이지 폴트 발생 시 참조량도 많아지므로 항상 이점이 있는 것은 아니다.

 

페이지 교체와 프레임 할당

물리 메모리보다 큰 프로세스를 실행할 수 있지만 그럼에도 물리 메모리 크기는 한정되어 있다.

따라서 기존에 적재된 불필요한 페이지를 선별해서 보조기억장치로 내보내고 프로세스들에게 적절한 수의 프레임을 할당해야 한다.

 

요구 페이징

프로세스를 메모리에 적재할 때 필요한 페이지만 메모리에 적재하는 기법을 요구 페이징이라고 한다.

아예 적재하지 않고 실행해버리는 기법을 순수 요구 페이징이라고 부른다.

 

요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득찬다.

그래서 위와 같은 요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 다음 두 가지를 해결해야 한다.

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

 

페이지 교체 알고리즘

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

따라서 페이지 폴트 횟수를 알아야 한다.

이는 페이지 참조열을 통해 알 수 있다.

여기서 연속된 페이지를 생략한 페이지열을 페이지 참조열이라고 한다.

연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문이다.

 

FIFO 페이지 교체 알고리즘

이름 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식이다.

그러나 프로그램 실행 내내 사용될 내용을 포함하고 있는 경우 메모리에 먼저 적재되었다고 해서 내쫓아서는 안 된다.

 

그래서 이를 보완한 알고리즘이 나왔다.

참조 비트를 0으로 만들고 가장 끝으로 보내준다.

 

 

최적 페이지 교체 알고리즘

CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘이다.

메모리에 오래 남아야 할 페이지는 자주 사용될 페이지이므로 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지다.

따라서 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다.

이렇듯 최적 페이지 교체 알고리즘은 이름 그래도 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다.

그러나 앞으로 오랫동안 사용되지 않을 페이지를 예측하기란 어렵다.

 

따라서 구현이 어렵기 때문에 알고리즘 성능 평가를 위해 주로 사용된다.

다른 페이지 교체 알고리즘 성능 평가하기 위한 하한선으로 간주한다.

 

LRU 페이지 교체 알고리즘

가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘

이외에도 페이지 교체 알고리즘의 종류는 다양하다.

따라서 페이지 교체를 왜 해야하고 무엇이 좋은 페이지 교체 알고리즘인지 알아야 할 필요가 있다.

 

스레싱과 프레임 할당

근본적으로 페이지 폴트가 자주 발생하는 이유는 프로세스가 사용할 수 있는 프레임 자체가 적다는 것이다.

 

스레싱이란 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제다.

 

 

메모리에서 동시에 실행되는 프로세스의 수를 멀티프로그래밍의 정도라고 한다.

동시에 실행되는 프로세스의 수를 늘린다고 CPU의 이용률이 그에 비례해서 증가하는 것이 아니다.

 

필요 이상으로 늘리면 각 프로세서들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 지나치게 많이 발생하고 이에 따라 CPU 이용률이 떨어져 전체적인 성능이 저해되는 것이다.

 

균등 할당

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

프로세서의 크기는 각기 다른데 동일한 프레임 개수를 할당하는 것은 그리 권장할 방법이 아니다.

 

비례 할당

프로세스의 크기에 맞게 프레임을 할당하는 방식

그러나 막상 실행시켜보니 많은 프레임을 필요로 하지 않는 경우가 있을 수 있고 프로세스의 크기가 작아도 실행해보니 많은 프레임을 필요로 할 수 있다.

 

(위 둘을 정적 할당 방식이라고 한다.)

 

그래서 프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 크게 작업 집합 모델과 페이지 폴트 빈도를 사용하는 방식이 존재한다.

 

(위 둘을 동적 할당 방식이라고 한다.)

 

작업 집합 모델을 사용한 방식

실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합이라고 한다.

CPU가 과거에 주로 참조한 페이지를 작업 집합에 포함한다면 운영체제는 작업 집합의 크기만큼만 프레임을 할당해주면 된다.

최소 5개의 프레임이 t2 시간에 필요하다.

 

페이지 폴트 빈도를 기반으로 한 방식

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

이를 그래프로 표현하면 다음과 같다.

위 그림처럼 상한선과 하한선을 정하고 이 범위 안에서만 프레임을 할당하는 방식이다.

 

유튜브 강의

출처: 혼자 공부하는 컴퓨터 구조 + 운영체제

혼자 공부하는 컴퓨터 구조+운영체제 - 예스24