운영체제는 어떻게 메모리를 관리할까?

오늘은 운영체제가 어떻게 메모리를 어떻게 관리하는지에 대해 알아보려고 합니다. 운영체제(OS)의 대표적인 일이라고 하면 메모리 관리도 있습니다. 메모리 관리라고 한다면 사용자가 쉽게 메모리를 사용할 수 있게 도와주는 것을 말합니다. 사용자가 메모리를 쉽게 사용하기 위해 운영체제가 메모리를 효율적으로 관리를 해줍니다. 또한 교착상태를 막기위해 메모리를 보호하기도 합니다.
우선 구체적으로 메모리 관리에 대해 알아보면서 질문에 답을 하기전에 몇가지 개념을 잡고 이어나가도록 하겠습니다.

💡 Memory(메모리)
메모리는 컴퓨터의 기억을 담당하는 것으로 상태나 명령어등을 기록하는 장치입니다. 메모리의 계층 구조로는 레지스터 → 캐시 → 메인메모리 → 저장장치 순으로 저장장치(보조기억장치)로 갈수록 용량이 커지고 그만큼 속도는 느려집니다.

🎓 사전 개념

링킹(Linking)

위 그림에서 볼 수 있듯이, 링킹은 기계어 파일들을 라이브러리 파일들을 링킹(linking)하여 실행 가능한 파일로 만드는 역할을 합니다. 링킹에는 두가지 개념이 존재합니다.

• 정적 링킹 : 코드 유출을 막고 시간을 단축시키지만, 컴파일할 때마다 공통 라이브러리를 포함시켜야 해서 메모리 문제가 발생합니다.
• 동적 링킹 : 하나를 올려놓고 왔다갔다하면서 사용하는 방법으로 메모리를 적게 사용합니다. 왔다갔다하니까 오버헤드도 발생합니다..

로딩(Loading)

로딩은 프로그램을 실행시킬 때, 메모리에 파일(데이터)를 적재하는 것을 말합니다. 로딩에도 두가지 개념이 존재합니다.

• 동적 적재(Dynamic Loading) : 메모리 크기가 프로세스 크기보다 큰 경우에 사용하는 방식으로 필요할때만 사용하고 빼내는 방식입니다.
• 오버레이 적재(Overlays Loading) : 이와 다르게 오버레이는 프로세스가 더 클때 사용하는데 프로세스 두개가 있다면 A를 올린다음 끝내고 B를 올리는 식입니다. 그것도 사람이 직접 구현해야한다는 단점이 있습니다.

오버레이 적재방식의 단점을 보완하고자 Paging 기법과 VMM(Virtual Machine Moniter)가 현재도 사용되고 있습니다. 이유는 이 둘이 사람대신 OS가 관리하기 때문이죠.

VMM

앞서, 오버레이 적재 방식 대신해서 VMM을 사용한다고 했습니다. VMM을 이해하기 전에 스와핑(Swaping)이라는 개념을 알고가면 좋을 것 같습니다.
스와핑은 메모리에 최대 10개의 프로세스를 올릴 수 있다고 할 때, 11번째 프로세스를 실행시킨다면, 10개중 하나를 내리고 11번째를 올리자라는 아이디어로 등장했습니다. 이때 10개중 하나를 빼낸다는 개념을 Swap Out이라고 합니다. 이 빼낸 프로세스는 버려지는게 아니라 보조기억장치에 실행 상태를 유지하게 되죠. 새롭게 올린 11번째 프로세스가 종료되고 다시 보조기억장치에 있던 프로세스를 올리는게 Swap in이라고 합니다.
이때, 스와핑은 프로세스 단위라면 VMM은 페이징 단위로 메인 메모리에 페이지를 올리고 빠진 페이지를 보조 기억장치에 저장했다가 바꿔주는게 스와핑이랑 비슷합니다.

바인딩(메모리 주소 할당)

데이터를 메모리에 저장할 때, 데이터에 저장된 메모리 주소를 명시하는 것을 메모리 주소 할당이라고 합니다.
바인딩에는 3가지 방법이 있는데 현대에는 마지막 방법인 실행 타임 방식을 적용하고 있습니다.

• 컴파일시 메모리 주소 할당 : 물리적인 주소만을 사용해 물리주소와 논리주소가 동일합니다.(물리주소 직접 접근)
• 로드타임 메모리 주소 할당 : 동일한 주소의 프로그램을 사용하고 있지 않으니 다른 논리주소(가상주소)를 사용합니다. 이렇게 매핑해주는 녀석이 MMU 입니다.
• 실행타임 메모리 주소 할당 : 매번 메모리에 로딩할 때, 주소 변환 작업을 해야하므로 병목현상이 발생합니다. 하드웨어가 대신 변환할 때 연산을 해준다. 그러면 그때 그때 바로 처리할 수 있습니다.

📌 메모리 할당

사전 지식에서 알아봤던 실행타임 메모리 주소 할당에서 MMU를 이용해 연산만으로 논리적 주소를 물리적 주소로 바꿔 연속적으로 메모리에 할당할 수 있다고 했습니다. 이외에도 MMU는 메모리를 보호하는 기능도 할 수 있습니다.

MMU

MMU(Memory Management Unit, 메모리 관리 장치)는 논리주소를 물리주소로 변환해줄 뿐만아니라 메모리 보호나 캐시 관리를 해주는 하드웨어입니다.

• 메모리 보호 : MMU는 프로세스가 독립적인 공간을 사용할 수 있도록 잘못된 주소를 참조하지 않게 막아줍니다. Limit(상한 레지스터)를 사용해 레지스터 값보다 크다면 fault를 발생시켜(인터럽트) 운영체제에게 요청하여 처리합니다.

하지만, 이러한 연속메모리 할당 방법은 단점이 존재합니다. 왜냐하면 외부 단편화(External Fragmentation)가 발생하게 되며 결론적으로는 현재 MMU의 연속 메모리 할당이 안쓰게 되죠.

단편화가 무엇인가요?

단편화(Fragmentation)은 두가지 종류로 나눌 수 있어요. 내부 단편화와 외부 단편화로요. 데이터에게 메모리를 할당할 때, 이렇게 연속적으로 할당하게 되면 외부 단편화가 발생하고 반대로 분산 할당하게 되면 내부 단편화가 발생하게 됩니다.

연속 할당

메모리할당에는 연속할당과 불연속할당으로 나눕니다.
연속 할당방법은 말그대로, 메모리 주소를 연속적으로 사용하기 때문에 두가지로 분할해서 올릴 수 없는 할당 방법을 말합니다. 연속적으로 할당하는 것이죠. 연속할당 방법에는 다음과 같이 단일로 관리하는 방법과 분할해서 관리하는 방법이 있습니다.

• 단일 프로그래밍(Uni) : 오직 하나의 프로그램만 저장합니다. 두개가 들어오면 하나가 끝난다음에 다음 프로그램이 저장됩니다. 오버레이
• 다중 프로그래밍 : 다른 프로세스들도 같이 저장하는 멀티 프로그래밍 방식입니다.
  • 고정 분할 방식(MFT, Fixed) : 메모리를 미리 나누어 공간을 할당하기 때문에 내부 단편화가 발생할 수 있습니다. 프로세스가 고정 파티션 크기보다 클 수 있습니다.
  • 가변 분할 방식(MVT, Variable) : 프로그램 크기에 맞게 나눠 사용합니다. 외부 단편화가 발생할 수 있습니다.

가변 분할 방식으로 프로그램 크기에 맞게 연속적으로 적재하게 되고 많은 프로그램들이 종료되고 실행되고 합니다. 그러다 다음과 같은 외부 단편화 문제가 발생할 수 있습니다. 이렇게 가용 공간(Hole)이 남는데도 불구하고 5번 프로세스가 들어갈 공간이 없는 상황이 생기게 되는 것이죠. 수용 가능한 공간들이 연속적이지 않아 새 프로세스를 메모리에 올리지 못하는 문제를 외부 단편화라고 합니다.

물론, 앞선 문제를 해결하기 위해 Compaction이라는 방법을 사용하면 Hole을 한쪽으로 공간을 모아줄 수 있습니다. 이때, 프로세스를 잠깐 보조기억장치에 복사해 붙여넣기하는데 보조기억장치는 느리기 때문에 I/O 문제가 발생할 수 있습니다.

프로세스는 어디에 넣는게 적합할까?

그렇다면 새로운 프로세스는 메모리 어디에 넣는게 적합할지 판단하는 기준에는 뭐가 있을까?

• 최초 적합(First-fit) : 메모리를 탐색하다 최초로 발견되는 공간에 할당하는 기법 (속도 최적)
• 최적 적합(Best-fit) : 모든 공간을 다 탐색하고 가장 적합한 공간에 넣는 기법 (공간 최적)
• 최악 적합(Worst-fit) : 불 필요한 공간에 넣는 기법(프로세스 크기 차이가 많이 나는 곳에 할당)

아무리 최적 적합이나 최초 적합을 사용한다 해도 단편화 문제는 여전히 존재합니다. 이러한 외부 단편화 문제를 해결하기 위해 메모리를 고정된 크기로 분할하는 방법이 필요합니다. Paging이라는 단위로 메모리를 고정적으로 분할하는 방법을 고정 분할이라고 합니다.

불연속 할당

페이징(Paging)은 프로세스를 고정된 크기로 쪼갠 단위를 의미합니다.
이렇게 쪼갠 작은 페이지들을 메모리 적재하는 것입니다. 예를 들어서 다음과 같이 A, B라는 프로세스를 물리 메모리에 적재해 실행시킨다고 가정한다면 페이지 매핑 테이블(Page Mapping table)이란 것을 통해 물리주소에 적재되는 것을 볼 수 있습니다.

자세히 보면 물리 메모리에 프레임은 뒤죽박죽이고 가상 메모리는 정리되어 있습니다. 그럼 뒤죽박죽 실행되는 걸까요? 그렇진 않습니다. 매핑 테이블이 대응되는 페이지와 프로세스끼리 연속적으로 연결해주어서 순차적으로 프레임을 실행시키게 도와줍니다. 다음과 같이 물리 메모리에 불연속적으로 할당되는 것을 불연속 할당이라고 합니다. 불연속 할당에는 고정 분할(paging)과 가변 분할(segementaion)이 있습니다.

앞 그림 처럼 동일한 크기의 페이징으로 분할하기 때문에(고정 분할) 딱 맞게 떨어지지 않게 쪼개지는 것을 볼 수 있습니다. 이렇게 쪼개지는 단편화를 내부 단편화라고 합니다. 그렇지만 내부 단편화는 외부 단편화보다는 낭비되는 공간이 상대적으로 매우 적기 떄문에 페이징 방법을 더 선호하는 편입니다.

💡 페이지 테이블을 통해 논리 주소를 물리 주소로 변환할 때, 프로세스의 개수가 많아지면 페이지 개수 또한 많아집니다. 이렇게 엄청난 양을 차지하게 되면 성능에 문제가 발생할 수 있습니다.

💡 세그먼테이션 기법(Segmentation)
다양한 크기인 세그먼트(의미) 단위로 분할하여 빈공간에 할당하는 방식을 말합니다. 크기가 고정되어 있지 않아 외부 단편화가 발생할 수 있습니다. 다른 영역에 접근을 못하도록 보호 키가 필요합니다. 이러한 두가지 강점을 잘 살린 게 페이지드 세그먼테이션 방법입니다.

📌 페이지 테이블의 성능 문제

다음과 같이 페이지 테이블의 페이지 개수가 증가하게 된다면 성능의 문제가 발생합니다. 이유는 페이지 매핑 테이블이 CPU의 MMU에 저장해야 하기 때문입니다. 왜 MMU에 저장하냐구요? CPU 속도가 빠르기 때문입니다. 그러다 용량이 커지면 CPU가 과부하됩니다.

방금 말했던 것처럼 페이지 개수가 증가하게 되면 테이블의 크기는 커지고 디스크를 접근하는 횟수 또한 많아지기 때문에 과부하가 일어납니다.

캐시 메모리

그렇다고 메인 메모리에 저장을 하게 되면 페이지 매핑 테이블과 메인 메모리를 두번 참조해야하는 문제가 발생합니다. 그러나 캐싱 메모리를 이용하면 성능을 저해시키지 않고 매핑 테이블을 CPU에 넣을 수 있습니다.

캐시의 지역성 덕분!

캐시 메모리는 CPU가 주기억장치에서 데이터를 읽어올 때, 자주 사용하는 데이터(집중적으로 참조해야하는 데이터)는 캐시 메모리에 저장한뒤 주기억장치까지 갈필요 없이 캐시 메모리를 가져와 속도를 향상 시켜주는 역할을 합니다. 메모리를 참조하거나 뺴내는 비용을 줄일 수 있다는 장점이 있습니다. 이렇게 자주 사용하는 데이터를 사용할 수 있게 하는게 캐시의 지역성 덕분입니다. 지역성에는 두가지로 나뉘게 됩니다.

• 시간 지역성 : 일정 시간 동안 집중적으로 데이터를 접근하는 현상
• 공간 지역성 : 일정 위치에 집중적으로 데이터를 접근하는 현상

우리가 반복문을 사용할 때, 반복적으로 배열을 접근하는 것도 지역성의 특징을 갖는다고 생각하시면 됩니다.

캐시 매핑 원리

위 그림을 보게되면 캐시에서 원하는 데이터를 가져올 수 있는 경우를 캐시 히트(Cache Hit)라고 하고, 만약 캐시에 원하는 데이터가 없다면 즉, 자주 사용하는 데이터가 아니라면 캐시 미스(Cache Miss)로 메모리에 있는 데이터를 캐시로 가져오게 됩니다. 캐스 미스가 발생했을 경우 당연히 속도가 더 느리겠죠. 캐시 히트가 되기 위해 다양한 매핑 방식이 존재합니다.

• 직접 매핑(Direct Mapping) : 캐시에 저장된 데이터를 메모리에 동일한 배열을 갖도록 매핑하는 방법입니다.
  • 장점 : 단순하고 탐색이 쉽다.
  • 단점 : 적중률(Hit ratio)가 낮다.
• 연관 매핑(Associative Mapping)
  • 순서와 상관 없이 캐시를 전부 뒤져서 같은 데이터가 있는지 병렬 검사한다.
  • 시간이 오래걸리지만 적중률은 보장한다.
• 집합 연관 매핑(Set Associative Mapping)
  • 먼저, 세트 번호(set)를 통해 탐색하기 때문에 병렬 탐색의 단점을 보완한다.
  • 모든 라인이 무작위로 위치해 직접 매핑의 단점도 보완한다.

캐시와 버퍼의 차이

• 데이터 저장 : 버퍼는 일반적으로 캐시보다 처리크기가 크며 연산이 끝나면 바로 폐기를 합니다.(전송 동안에만 데이터 보관) 반면, 캐시는 추후에도 사용할 수 있게 데이터를 저장합니다.
• 탄생 목적 : 캐시와 버퍼는 작업 속도를 증진시키기도 하지만 버퍼는 그 뿐만아니라 작업간의 무결성(협동)을 지원합니다.

실제로 Linux 메모리내 캐시 영역에 페이지 캐시(Page cahce)와 버퍼 캐시(Buffer cache)가 있습니다.

• 페이지 캐시(Page Cache)는 파일의 내용을 저장하는 캐시를 말하고
• 버퍼 캐시는 파일의 메타 데이터와 관련된 블록들을 저장하는 캐시를 말합니다.

리눅스 2.4 버전 부터는 버퍼 캐시가 페이지 캐시 안에 포함되면서 이중 캐시 문제점이 해결되었습니다.참고

• 우리가 흔히 볼수 있는 캐시로는 쿠키, 로컬 스토리지, 세션 스토리지 등이 있습니다. 보통 이러한 캐시들은 서버에 요청할 때, 중복을 방지하기 위해 사용됩니다.
• 또한, 데이터베이스 시스템에서 메인 데이터베이스 위에 Redis라는 캐싱 계층을 두어 성능을 향상시키기도 합니다.

메모리에 데이터가 없다?

가상 메모리는 프로세스가 실행할 때 실질적으로 필요한 데이터만 메인 메모리에 올라가고 나머지는 하드 디스크에 옮겨 놓는데 이 메모리 주소와 매핑되는 메모리가 가상 메모리입니다.

요구 페이징 도중 페이지 폴트 발생!

그런데 이렇게 당장 필요한 페이지만 메모리에 올리는 요구 페이징 방식을 사용하면서 물리 메모리에 없는 경우 경도 생기게 됩니다. 이러한 현상을 페이지 폴트(Page Fault)라고 하는데요.

이때, CPU가 TRAP을 발생시켜 운영체제가 CPU를 멈추고 가상 메모리에 페이지가 있는지 확인합니다. 만약 페이지가 존재하지 않는다면 물리 메모리가 비어 있는지 확인하고 디스크에서 메모리를 로드하게 됩니다. 페이지 테이블에 해당 페이지가 메모리 적재 되었다는 정보를 저장하게 됩니다.

그런데 만약에, 물리 메모리가 비어있지 않으면 어떻게 될까요?
운영체제 페이지 교체 알고리즘(Page Replacement)을 통해 사용하지 않는 페이지를 디스크로 내보내고 새로운 페이지를 메모리에 적재합니다. 이렇게 디스크로 보내고 하드디스크에 일부분을 메모리 처럼 불러와 사용하는게 스와핑(Swapping)이라고 합니다.

해당 프레임에 페이지를 로드하고 테이블을 최신화합니다. 그리고 마치 폴트가 없던 것 처럼 다시 CPU를 시작합니다.

페이지 교체 알고리즘을 이용한 스와핑으로 해결!

• OPT(Optiomal) : 최적교체로 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
• FIFO(First In First Out) : 가장 간단한 알고리즘으로 가장 먼저 올라온 페이지를 제거하는 알고리즘입니다. → SCR(2차 교체)
• LRU(Least Recently Used) : 가장 오랫동안 사용되지 않았던 페이지를 제거하는 알고리즘입니다.
• LFU(Least Frequently Used) : 사용 빈도가 가장 낮은 페이지를 제거하는 알고리즘입니다.
• NUR(Not Used Recently) : 최근에 사용하지 않은 페이지를 교체하는 기법으로 참조 비트와 변형비트가 사용됩니다.

페이지 폴트가 많이 발생하면 CPU를 멈추는 일이 많아져 시스템 성능이 저화됩니다.(스레싱의 원인) 그러므로 교체 알고리즘을 최적화하여 페이지 폴트를 최소화하는 게 중요합니다.

스레싱

메모리에 많은 프로세스가 동시에 올라가게되면 실제 사용되는 프로세스가 많아지게 됩니다. 이렇게 되면 스와핑 작업도 많이 일어나는데요. 잦은 스와핑 작업으로 그만큼 페이지 폴트률도 높아져서 발생하게 됩니다. 이렇게 되면 스레싱으로 인해 프로세스를 다 처리하지 못해 교체로 드는 시간이 많아져 이용률이 떨어지는 것이죠.

운영체제는 CPU 이용율이 낮으면 메모리에 동시에 올라가 있는 프로세스의 수인 MPD(다중 프로그래밍의 정도, Multi-Programming Degree)를 높이게 되는데 동시에 실행하는 프로세스가 많아질 수록 각 프로세스에 할당된 메모리 페이지 프레임들은 더욱 작아지게 됩니다. 너무 적은 페이지 프레임을 할당받은 프로세스들은 페이지 부재가 증가하게되어 Swapping이 증가하게 되고 결국 CPU의 이용율이 더욱 떨어지는 악순환이 생기게 된다.

스레싱 해결방법

• Working set

지역성의 원리를 이용하여 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 방법이다. 프로세스가 일정시간동안 자주 참조하는 페이지들을 집합으로 묶습니다.

*지역성의 원리: 프로세스가 일정 시간 동안 집중적으로 특정 주소 영역을 참조하는 경향

• Page Fault Frequency(페이지 부재 빈도)

프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거하여 각 프로세스에 할당할 메모리 양을 동적으로 예측하고 조절하는 알고리즘이다.
현재 페이지 부재와 직전 페이지 부재 사이의 시간을 관찰하여 상한 값(upper bound)을 초과하거나 하한 값(lower bound) 미만이 되면 운영체제가 메모리에 올라가 있는 프로세스의 수를 조절한다.

• 메모리를 늘리거나 HDD를 SDD를 바꾸는 방법

Resource

https://jhnyang.tistory.com/247
https://techblog-history-younghunjo1.tistory.com/511
https://blog.mglee.dev/blog/세그멘테이션과-페이징-비교/
https://velog.io/@anjaekk/OS-Thrashing

정리