CS: APP 9장. 가상메모리란?
CPU 연산
에니악이라는 컴퓨터의 원조는 암호의 경우의 수를 풀기위한 계산기였다. 에니악이 생긴지 겨우 몇십년만에 이렇게 복잡하고 멋진 컴퓨터가 되었지만. 결국에 중요한 건, CPU에서 진행하는 연산을 이용해서 이런 멋진 결과물을 만들어 내는 것이다.
직접 주소 방식
CPU는 메모리에 저장되어있는 바이너리 값을 가져와서 연산한다. 매우 직관적인 방법은 Figure 9.1 그림처럼 물리적 메모리공간인 Main Memory(DRAM)의 물리적 주소(PA)에서 load하는 방법이다. 이러한 방식을 '직접 주소 방식', '물리 주소 방식' 이라고 하며, 이런 방식을 차용하는 application으로는 마이크로 컨트롤러, 임베디드, Cray 슈퍼 컴퓨터 등이 있다.
가상메모리 방식과 사용 이유
그럼 우리가 쓰고 있는, 내가 지금 타자를 치고 있는 이 컴퓨터는 어떤 방식을 차용할까?
바로, 위 그림처럼 가상메모리 방식을 적용한다. 가상메모리를 한단어로 표현하면 '메인 메모리의 추상화'이다. 즉, DRAM을 Disk에 복제한 것이다. 이러한 짓을 왜 하는 걸까? 가상메모리라는 것을 쓰는 걸까?
그 이유를 책에서 3가지로 설명하고 있다. 첫번째, 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급해서 메인 메모리 내 활성화 영역만 유지, 데이터를 디스크와 메모리 간에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용할 수 있다.
-> 프로세스는 가상 주소를 사용하고, 실제 해당 주소에서 데이터를 읽고/쓸때만 물리 주소로 바꿔주면 된다.
이때 사용하는 장치 MMU(Memory Management Unit)
: CPU에 코드 실행시, 가상 주소 메모리 접근이 필요할 때, 해당 주소를 물리 주소값으로 변환해주는 하드웨어 장치
두번째, 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 효율적으로 사용한다.
세번째 각 프로세스의 주소 공간을 다른 프로세스에 의한 손상으로부터 보호한다.
-> 마지막 이미지를 보면 이해하기 쉬울 수 있다. 메인메모리(DRAM)데이터를 백업하는 역할.
가상 메모리의 구조, 데이터 세그먼트
하나의 프로그램, 즉 프로세스를 실행하면 OS는 프로세스당 하나의 가상메모리 공간을 할당한다. 우리가 강제종료할 때 많이 보는 작업관리자에서 '프로세스'를 보면 다음과 같이 메모리 공간을 확인 할 수 있다. 브라우저를 예를 들면, 많은 웹창을 켜놓을 수록, 부하가 많아지고, 차지하는 메모리 공간이 커진다. 반대로 웹 창을 하나정도 켜놓는다면 차지하는 메모리가 적은 것을 알 수있다. 어떻게 이렇게 사용자에 따라 동적으로 메모리를 조절할 수 있을까? 가상 메모리는 어떻게 생겨먹었길래?
위 사진은 CS:APP에 실려있는 리눅스 프로세스의 가상메모리를 추상화 한것이다. 뭐, 윈도우와 리눅스가 그리 다르진 않으리라 생각한다.이 이미지가 바로 요번 주차에 있는 keyword인 데이터 세그먼트이다.
User space에는 프로그램(이하 프로세스)가 실행되었을 때 컴파일러에 의해 차곡차곡 쌓아 생긴 값들이다. 아래부터 코드영역, 데이터 영역(전역 변수, 정적 변수 데이터 저장), 런타임 힙, 그리고 요번에 우리가 구현해야할 힙 영역, 그리고 함수실행에 따라 쌓이는 stack 영역으로 이루어져 있다.
힙 세그먼트(heap segment)
힙 세그먼트(heap segment)란 무엇일까.우리가 게임이든 어떤 응용 프로그램을 만들 때, 유저가 input한 데이터를 어디다 담아둬야 할 것이다. 근데 담아둘 공간을 배열로 만든다고 가정해보자.배열의 크기가 작다면 유저가 더 많은 input을 줬을 때 저장하지 못하고 프로그램이 뻥(?)날 것이다.반대로 크기가 너무 크게 만든다면 작업관리자 창에서 보았듯이 프로그램만 켰을 뿐인데, 메모리 용량을 어마하게 잡고 있을 것이다.
이런 멍청한 프로그래머가 되지 않으려면 사용자의 사용량에 따라 유동적인, 동적 메모리 할당을 해야한다.동적 메모리가 할당되는 영역이 바로 힙 세그먼트 영역이며, 사용자에따라 크기가 유동적으로 변하는 공간이다.동적 메모리 할당을 하는 다른 이유는 stack 영역의 함수가 종료된 이후에도 메모리 할당이 살아 있게 함으로써 lifecycle, large size를 유지 및 늘리기 위해 사용한다고 한다.
이런 가상메모리는 OS단에서 관리한다. 우리가 작성한 user 함수로는 감히 접근하지 못한다. 이러한 방법으로 OS는 멍청한 프로그래머로부터 컴퓨터를 한단계 더 보호한다.이런 보호막이 없었다면, "Segmentation fault", "Protection fault"에러를 띄우면서 컴퓨터가 먹통이 되었을 것이다.(malloc코딩을 하면서 너무 체감되었다.😣)
시스템 콜(system call)
그렇다면 동적 메모리할당을 하려면 어떻게 할까? 그 때 사용하는 함수가 시스템 콜 함수다. 시스템 콜(system call)은 운영 체제에서 제공하는 기능을 사용하기 위한 인터페이스이다. 시스템 콜은 사용자 프로그램이 운영 체제에 요청하는 것으로, 일반적으로 프로그램이 운영 체제에게 하드웨어나 다른 프로세스와의 상호작용을 요청할 때 사용된다. 예를 들어, 파일 시스템 접근, 프로세스 생성 및 종료, 메모리 할당 및 해제, 네트워크 통신 등의 작업을 수행할 때 사용한다. 작업 관리자에서 강제종료하는 것도 TerminateProcess() 함수를 통해 시스템 콜하는 것이다.
시스템 콜은 커널(kernel)이라는 운영 체제의 핵심 부분에서 처리된다. 프로그램이 시스템 콜을 호출하면, 커널은 해당 요청을 처리하고, 결과를 프로그램에 반환한다.
sbrk, mmap
malloc처럼 힙메모리를 할당하거나 반환할 때 사용하는 시스템콜은 sbrk, mmap이 있다. sbrk함수는 커널의 brk 포이터에 incr을 더해서 힙을 늘리거나 줄인다.mmap() 시스템 콜은 새로운 메모리 영역을 할당하고, 이를 가상 주소 공간에 매핑한다. 이후, 프로그램은 이 메모리 영역을 사용할 수 있다. munmap() 시스템 콜은 반대로, 가상 주소 공간에서 메모리 영역을 제거하고, 이를 해제합니다. 이를 통해 프로그램이 더 이상 사용하지 않는 메모리를 시스템에 반환할 수 있다.
malloc-lab
다시 말하지만, 가상 메모리 공간은 OS가 관리한다. 따라서 동적 메모리 함수 구현을 연습하려면, 시스템 콜함수를 사용해 OS에게 가상메모리 힙 공간을 제어해야한다.하지만 실제로 코딩연습을 위해 시스템 콜을 무작위로 사용했다가는, 비싼 컴퓨터를 버리게 될것이므로, 친절하고 영리한 정글에서는 CMU(Carnegie Mellon University)의 '가상메모리 공간'을 c언어로 모델링한 드라이버 프로그램,malloc-lab을 통해 코딩연습 기회를 제공한다.
여기까지가 요번주 무엇을 하는 것인가에 대한 파악이었다.다음에는 어떻게 동적메모리 할당을 다루는지 정리해 보겠다.
동적 메모리할당 방법들
동적 메모리 할당은 명시적 할당기(explicit allocator)과 묵시적 할당기(implicit allocator)방법이 있다.
명시적 할당기는 사용자가 직접 메모리 할당 및 함수를 사용하여 메뫼를 관리하는 방법으로 자유도가 높지만, 오버헤드 우려가 있다. 예시로는 우리가 구현해야할 malloc함수, free함수가 있다.
묵시적 할당기는 내부적으ㅗ 자동으로 메모리가 할당되는 방법이다. 할당기가 프로그램에 사용되지 않는 메모리 블록을 검출할 수 있을 것을 요구한다. 이러한 작업을 가비지 컬렉션(garbage collection)이라고 하며, List, ML, 자바, 파이썬 같은 상위 수준 언어들이 사용한다. 이 때문에, c언어보다 동작이 느릴 수 있다.
malloc-lab에서는 명시적 할당 방법을 위한 malloc함수와 free함수, 그 밖에 realloc함수 등을 구현한다.
단편화(fragmentation)
빠른 프로그램은 메모리를 효율적이게 써야하고, 처리 속도도 빨라야 할 것이다. malloc-lab 드라이버 프로그램에서는 구현한 함수를 메모리 효율, 데이터 속도 처리에 대해 값을 메겨서 채점해준다.
그러면 메모리 효율은 무엇일까. 데이터를 메모리에 할당하고, 해제(free)시켰을 때, 나타는 현상인 단편화를 이해하면 메모리 효율을 잘 이해할 수 있다. 메모리 단편화는 메모리 영역에서 사용 가능한 메모리가 작은 조각들로 나뉘어져서, 요청한 메모리 크기에 맞는 연속된 메모리 영역을 할당할 수 없게 되는 상황을 말한다. 이는 프로그램의 성능을 저하시키는 주요한 원인 중 하나이다.
내부 단편화(internal fragmentation) 외부 단편화(external fragmentation)
메모리 단편화는 크게 내부 단편화(internal fragmentation)와 외부 단편화(external fragmentation)로 나뉜다. 내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다. 이러한 이유는 cpu에서 메인메모리로 이동(load)될 때 빨리 이동할 수 있도록 word단위로 데이터를 맞춰놓다보니, 원래 넣으려는 데이터보다 할당된 블록이 더 클 때 일어나는 메모리 비효율 문제이다. 또한, 어느 메모리 공간이 비어있나, 크기가 적당한가를 탐색하기 위해서 header,footer같은 의미적 메모리를 사용하는데 이러한 의미적 메모리가 과도하게 많을 때도 발생한다.
외부 단편화는 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 떄는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우에 발생한다. 아래는 외부 단편화를 잘 표현한 그림이다.(e)상황에서 6개의 Word가 존재하지만, 조각나있어 크기6의 메모리를 할당할 수 없는 문제가 발생한다.
구현 방법들
묵시적 가용리스트(Implicit free list)
: 가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문에 묵시적 연결리스트로 불린다.
연결리스트 자료구조 방식, 간단하지만 효율이 떨어진다.
블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 범용 할당기에는 적합하지 않다. 이를 개선하기 위해 앞에서 할당 가능한 블록을 탐색하는 first fit방법 대신, next fit, best fit 등을 사용하기도 한다.
명시적 가용 리스트(Explicit free list)
:이중 연결리스트 자료구조 방식. 할당을 하기위해 free block을 탐색하는 효율을 높이기 위해 free block을 이중 연결 리스트 방식으로 관리한다.
분리 가용 리스트(Segregated free list)
분리 저장장치(sefregated storage)를 사용하여, 다수의 가용 리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장하는 방법이다. 기본적인 아이디어는 모든 가능한 블록 크기를 크기 클래스(size class)라고 하는 동일 클래스 집합들로 분리하는 것이다. 크기 클래스를 정의하는 많은 방법이 있지만, 책에서 설명하는 방법은 블록 크기를 2의 제곱으로 나누는 것이다.
이러한 할당 방법은 GNU malloc패키기 같은 수준에서 자주 선택된다.
버디 시스템(Buddy system)
버디 시스템은 각 크기 클래스가 2의 제곱인 특수한 경우의 분리 맞춤 방식이다. 버디 시스템의 핵심사항은 블록의 주소와 크기가 주어지면 이 블록의 버디 주소를 계산하는 것은 쉽다는 것이다. 따라서 버디 시스템 할당기의 중요한 장점은 빠른 검색과 연결이다. 주요 단점은 블록 크기가 2의 제곱이라는 사실은 상당한 내부 단편화를 유발할 수 있다는 것이다. 그래서 버디 시스템 할당기는 범용 부하에서는 부적당하다. 하지만, 특정 응용에 국한된 부하에 대해 블록 크기가 사전에 2의 제곱이라고 알려진 경우에는 일정 효과를 거둘 수 있다.
더 많은 이론이 있지만, 이제 코드 내용으로 들어가야 하기 때문에 이정도로 정리하도록 하겠다.
이이상 적는 것은 어차리 CS:APP책에 더 자세히 있으므로. 자, 코딩 시작!
