CSAPP 9

CSAPP

9. 가상 메모리

• 메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상메모리(VM : Virtual Memory)이라고 알려진 메인 메모리 추상화를 제공한다.
• 가상 메모리는 한 개의 깔끔한 메커니즘을 사용해서 세 개의 중요한 기능을 제공한다.
  1. 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급해서 메인 메모리 내 활성화 영역만 유지하고, 데이터를 디스크와 메모리안에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용한다.
  2. 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.
  3. 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.

9.1 물리 및 가상주소 방식

• 컴퓨터 시스템의 메인메모리는 M개의 연속적인 바이트 크기 셀의 배열로 구성된다. 각 바이트는 고유의 물리주소(PA)를 가진다. 첫 번째 바이트는 주소 0, 다음 바이트는 주소 1, 다음은 2, 이런 식으로 진행된다. 이와 같은 간단한 구조가 주어졌을 때, CPU가 메모리에 접근하는 가장 자연스러운 방식은 물리주소를 사용하는 것이다. 이런 접근법을 물리 주소방식이라고 한다.
• 현대의 프로세스들은 가상주소 방식이라는 같은 주소 형태를 사용한다.
• CPU는 가상주소지정으로 가상주소(VA)를 생성해서 메인메모리에 접근하며, 이것은 메모리로 보내지기 전에 적절한 물리 주소로 변환된다. 가상주소를 물리 주소로 변환하는 작업은 주소 번역이라고 알려져 있다. CPU 칩 내에 메모리 관리 유닛(MMU)이라고 부르는 전용 하드웨어는 메인 메모리에 저장된 참조 테이블을 사용하여 실행 중에 가상주소를 번역하며, 이 테이블의 내용은 운영체제가 관리한다.

9.2 주소공간

• 주소공간은 비음수 정수 주소의 정렬된 집합이다.
• 주소공간의 정수가 연속적이라면, 이 공간은 선형주소공간이라고 한다. 가상메모리를 갖는 시스템에서, CPU는 가상 주소공간이라고 불리는 N=2^n 주소의 주소공간에서 가상의 주소를 생성한다.
• 주소공간의 크기는 가장 큰 주소를 표시하는데 필요한 비트 수로 나타낸다. 현대 시스템은 전형적으로 32비트 또는 64비트 가상 주소공간을 지원한다.
• 또한 컴퓨터 시스템은 이 시스템 내의 M바이트의 물리메모리로 대응되는 물리 주소 공간을 갖는다.
• 메인메모리의 각 바이트는 가상 주소공간으로 부터 선택된 가상주소를 가진다.

9.3 캐싱도구로서의 VM

• 가상 메모리 디스크에 저장된 N개의 바이트 크기의 셀 배열로 구성된다. 각 바이트는 특정한 가상주소를 가지며 배열의 인덱스로 작용한다. 디스크 안의 배열 정보는 메인 메모리에 캐시된다. 메모리 계층구조 안에 있는 캐시는 블록 단위로 분할이 되며, 디스크와 메인메모리 사이에 징검다리 역할을 한다. VM system은 가상메모리를 규정된 사이즈 블록단위로 분할하여 관리한다. 분할된 블록들은 가상 페이지라고 부른다. 각 가상 페이지는 P = 2p바이트의 크기를 갖는다. 이와 비슷하게 물리 메모리도 물리 페이지로 분할되어 사용한다.
• 시간상의 어느 시점에서도 가상 페이지 집합은 세 개의 중첩되지 않는 부분 집합으로 나누어진다.
  • unallocated : VM 시스템에 의해 아직까지 할당되지 않은 페이지들 비할당된 블록들을 이들과 관련된 데이터를 하나도 가지고 있지 않으며, 따라서 디스ㅡ크 상에 어떤 공간도 차지하지 않는다.
  • cached : 현재 물리 메모리에 캐시되어 할당된 페이지들.
  • uncached : 물리 메모리에 캐시되지 않은 할당된 페이지들.

9.3.1 DRAM 캐시의 구성

• 메모리 계층구조 내에서 DRAM 캐시의 위치는 이들이 구성된 방식에 큰 영향을 갖는다. DRAM이 SRAM보다 10배는 더 느리고, 디스크는 DRAM보다 100,000더 느리다. 따라서 DRAM 캐시미스는 SRAM 캐시미스와 비교해서 값이 매우 비싸다.
• 큰 규모의 미스 비용과 첫 번째 바이트를 접근하는데 드는 비용 때문에 가상페이지는 더 커지고 있으며, 대개 4KB에서 2MB 값을 가진다. DRAM 캐시는 완전 결합성이다. 즉, 모든 가상페이지는 물리 페이지에 둘 수 있다. 디스크의 큰 접근 시간 때문에 DRAM은 항상 write-through 대신에 write-back을 사용한다.

9.3.2 페이지 테이블

• 물리 메모리에 저장된 자료구조의 조합. 가상 페이지를 물리페이지로 매핑한다.
• 주소 번역 하드웨어는 이들이 가상주소를 물리 주소로 변환할 떄마다 페이지 테이블을 읽는다. 운영체제는 페이지 테이블의 콘텐츠 관리와 페이지들을 디스크와 DRAM 사이에서 왔다갔다 하는 것을 관장한다.
• 페이지 테이블은 페이지 테이블 엔트리(PTE)의 배열이다. 가상 주소공간의 각 페이지는 페이지 테이블 내에 고정된 오프셋 위치에 PTE를 갖는다. 편의상 각 PTE가 한 개의 유효비트(vaild), n 비트의 주소 필드로 구성된다고 가정하겠다. 유효비트는 가상페이지가 현재 DRAM에 캐시되어 있는지를 나타낸다.
• 유효비트가 세팅되었다면, 주소 필드는 가상페이지가 캐시되어 대응되는 DRAM의 물리 페이지의 시작을 나타낸다. 만일 유효비트가 세팅되어 있지 않다면, NULL주소는 가상페이지가 아직 할당되지 않았음을 나타낸다. 그렇지 않은 경우 주소는 디스크상의 가상페이지의 시작 부분을 가리킨다.

9.3.4 페이지 오류

• DRAM 캐시 미스를 페이지 오류(Page fault)라고 한다.
• 가상메모리 용어에서 블록은 페이지라고 알려져 있다. 디스크와 메모리 사이에 페이지를 전송하는 동작은 스와핑 또는 페이징이라고 알려져 있다. 페이지들은 디스크에서 DRAM으로 스와핑해 들어오며(페이징되어 들어오며), DRAM에서 디스크로 스와핑되어 나간다(페이징되어 나간다). 미스가 발생할 때, 하나의 페이지로 스와핑 되어 들어오는 마지막 순간까지 기다리는 전략은 요구페이징(Demand paging)이라고 알려져 있다.

9.4 메모리 관리를 위한 도구로서의 VM

• 운영체제는 각 프로세스마다 별도의 페이지 테이블을 제공하며, 그래서 별도의 가상주소공간을 제공한다.
• 다수의 가상페이지들이 동일한 공유된 물리 메모리에 매핑될 수있다.
• 요구페이징과 분리된 가상 주소공간 조합은 메모리가 시스템에서 사용되고 관리하는 방식에 중요한 영향을 미친다. 특히 VM은 링킹 과정과 로딩, 코드와 데이터의 공유, 응용으로의 메모리 할당을 단순화 해준다.
  • 링킹을 단순화 한다. 별도의 주소공간은 각 프로세스들이 각 메모리 이미지에 대해서 코드와 데이터가 실제로 물리 메모리내 어디에 위치하는지에 상관없이 동일한 기본 포맷을 사용하도록 해준다. 이러한 통일성은 링커의 설계와 구현을 매우 단순화 해주며 물리 메모리 상에서 궁극적인 코드와 데이터의 위치에 독립적인 완전히 링크된 실행가능 파일을 만들 수 있게 해준다.
  • 로딩을 단순화 해준다. 실행 파일과 공유 목적 파일들을 메모리에 로드하기 쉽게 해준다. 목적파일의 .data와 .text 섹션들을 새롭게 생성된 프로세스에 로드하기 위해서, 리눅스 로더는 코드와 데이터 세그먼트를 위한 가상의 페이지를 할당하고, 이들을 무효로 표시하고,(즉 캐시되지 않은 상태) 이들의 페이지 테이블 엔트리를 목적파일의 해당 위치를 가리키게 한다. 흥미로운 점은 로더가 실제로 디스크로부터 메모리로 데이터를 전혀 복사하지 않았다는 것이다. 각 페이지가 최초로 참조될 때, CPU가 인스트럭션을 선입하거나 메모리 위치를 참조하는 인스트럭션을 실행할 때, 데이터는 요청에 의해 자동으로 페이지화 된다.
  • 연속된 가상 페이지를 임의의 파일 내의 임의의 위치로 매핑하는 개념은 메모리 매핑이라고 알려져 있다.
  • 공유를 단순화 해준다. 별도의 주소공간은 운영체제에 사용자 프로세스와 운영체제 자신 사이에 공유를 관리하는 일정한 메커니즘을 제공한다. 일반적으로 각 프로세스는 다른 프로세스와 공유되지 않은 자신만의 사적인 코드, 데이터, 힙, 스택 영역을 가진다. 이 경우에 운영체제는 대응되는 가상페이지를 중첩되지 않는 물리 페이지로 매핑하는 페이지 테이블을 만든다.
  • 일부의 경우 프로세스들이 코드와 데이터를 공유하는 것이 바람직 할 때가 있다. 모든 프로세스는 동일한 운영체제 커널 코드를 호출해야 하며 모든 C프로그램은 표준 라이브러리 루틴을 호출한다. 커널과 표준 C라이브러리 코드를 각 프로세스에 별도로 포함시키기 보다 운영체제는 가상페이지들은 동일한 물리 페이지로 적절하게 매핑해서 이 코드들의 한 개의 사본을 공유할 수 있게 한다.
  • 메모리 할당을 단순화 해준다. 사용자 프로세스로 돌고 있는 프로그램이 추가적인 힙 공간을 요청할 때, 운영체제는 적당한 수의, 연속적인 가상 메모리 페이지를 할당하고, 이들을 물리 메모리 내에 위치한 k개의 임의의 물리 페이지로 매핑한다.

9.5 메모리 보호를 위한 도구로서의 VM

• 모든 현대 컴퓨터 시스템은 운영체제가 메모리 시스템에 접근하는 것을 제어할 수 있는 수단을 제공한다.
• 별도의 가상 주소공간을 제공하면 사적 메모리를 다른 프로세스로부터 분리하는 것이 쉬워진다.
• CPU가 주소를 만들 때마다 PTE를 읽기 때문에 PTE에 허가비트를 추가해서 주소 번역 하드웨어가 가상페이지 내용으로의 접근을 제어하게 한다.
• PTE에 세 개의 허가비트
  • SUP비트는 프로세스들이 이 페이지에 접근하기 위해 커널 모드(수퍼바이저)로 돌고 있어야 하는지를 나타낸다. 커널 모드로 돌고 있는 프로세스들은 모든 페이지에 접근하도록 허용되지만, 사용자 모드에서 돌고 있는 프로세스들은 SUP가 0인 페이지들만 접근이 허용된다.
  • READ와 WRITE 비트는 이 페이지에 대한 읽기와 쓰기 접근을 제어한다.

9.6 주소의 번역

• 주소 번역은 N - 원소 가상 주소공간(VAS : virtual address space)과 M - 원소 물리 주소공간(PAS : physical address space)의 원소들 간의 매핑이다.
• CPU 내에 있는 제어 레지스터인 페이지 테이블 베이스 레지스터(PTBR : Page Table Base Register)는 현재 페이지 테이블을 가리킨다. n비트 가상주소는 두 개의 컴포넌트를 가진다.
  • P비트 가상 페이지 오프셋(VPO : virtual page offset)
  • (n-p)비트 가상페이지 번호(VPN : virtual page number)
• MMU는 VPN을 사용해서 적합한 PTE를 선택한다. 대응되는 물리주소는 페이지 테이블 엔트리에서 가져온 물리 페이지 번호(PPN : physical page number)와 가상주소에서 온 VPO를 연결한 것이다. 물리와 가상 페이지 모두 P바이트이므로 물리 페이지 오프셋(PPO : physical page offset)은 VPO와 동일하다.

그림 9.13

9.6.1 캐시와 VM의 통합

• 가상메모리와 SRAM 캐시를 사용하는 모든 시스템에는 SRAM 캐시를 접근하기 위해 가상주소 또는 물리 주소를 사용할 수 있다. 대부분의 시스템은 물리 주소지정을 선택한다. 물리주소를 사용하면, 다중 프로세스들이 캐시에서 블록을 갖는 것과 마친가지로 가상페이지로부터 블록을 공유하는 것이 단순해진다. 게다가 캐시는 보호 이슈를 다룰 필요가 없어지는데, 접근권한이 주소 번역 과정의 일부로 체크되기 때문이다.
• 메인 아이디어는 주소 번역이 캐시 참조 이전에 일어난다는 것이다. 페이지 테이블 엔트리들이 다른 데이터 워드와 마찬가지로 캐싱될 수 있다는 점에 주목해야 한다.

9.6.2 TLB를 사용한 주소 번역 속도의 개선

• CPU가 가상주소를 생성할 때마다 MMU는 가상주소를 물리 주소로 번역하기 위해 PTE를 참조해야 한다. 최악의 경우, 이것은 메모리로부터 추가적인 선입 작업을 필요로 하며, 이를 위해서 수숩에서 수백 사이클의 비용이 들게 된다. PTE가 L1에 캐싱되어 있다면, 이 비용은 2에서 1사이클로 줄어든다. 그렇지만 많은 시스템들은 이 비용마저 MMU내 번역 참조 버퍼(TLB : translation lookaside buffer)라고 부르는 작은 캐시를 포함해서 제거하려고 한다.
• TLB는 작은 가상주소지정 캐시로, 각 라인의 하나의 PTE로 구성된 하나의 블록을 저장한다. TLB는 대개 높은 수준의 결합성을 가진다. 집합선택과 라인매칭을 위해 사용되는 index와 tag 필드는 가상주소 내의 가상 페이지 번호에서 추출된다.
• 모든 주소 번역 단계들이 온칩 MMU 내에서 수행되기 때문에 매우 빠르다.

9.6.3 다중 레벨 테이블

• 페이지 테이블을 압축하는 보편적인 접근법은 대신 페이지 테이블의 계층구조를 사용하는 것이다.
• 1단계 테이블의 각 PTE는 가상 주소공간 크기를 매핑하는 역할을 하며, 이들 각각의 블록은 연속적인 페이지들로 이루어진다.
• 만일 블록 i안의 모든 페이지들이 할당된다면 1단계 PTE i는 널이다. 그렇지만 최소한 블록 i의 한 개 페이지가 할당된다면 1단계 PTE i는 2단계 페이지 테이블의 베이스를 가리킨다.
• 2단계 페이지 테이블 내의 각 PTE들은 가상메모리 페이지를 관리하며, 이것은 앞에서 단일 레벨 페이지 테이블을 살펴보았을 때와 동일하다.
• 이 기법은 메모리 요구량을 두 가지 방법으로 줄여준다
  1. 만일 1단계 테이블의 PTE가 널이면, 해당 2단계 페이지 테이블이 존재할 필요가 없어진다.
  2. 1단계 테이블만이 항상 메인 메모리에 있을 필요가 있다. 2단계 페이지 테이블은 이들이 필요할 때 VM 시스템에 의해서 생성되고, 페이지 인 또는 아웃 될 수 있으며, 이로 인해 메인 메모리로의 압박을 줄일 수 있다. 과도하게 사용된 2단계 페이지 테이블만이 메인 메모리에 캐시될 필요가 있다.

9.7 사례 연구 : 인텔 코어 i7/리눅스 메모리 시스템

9.7.2 리숙스 가상 메모리 시스템

• 커널 가상 메모리는 커널 내의 코드와 데이터 구조를 포함한다. 일부 커널 가상메모리 영역은 모든 프로세스가 공유하는 물리페이지에 매핑되어 있다. 각 프로세스는 커널의 코드와 전역데이터 구조를 공유한다. 흥미롭게도, 리눅스는 또한 연속적인 가상페이지 집합을 대응하는 연속적인 물리 페이지의 집합에 매핑한다.

리눅스 가상메모리 영역

• 리눅스는 가상메모리 영역(세그먼트)들의 집합으로 구성한다. 한 개의 영역은 기존(할당된) 가상메모리의 연속된 묶음으로, 이들의 페이지는 어떤 형식으로 연관되어 있다. 각각의 기존 가상페이지는 특정 영역에 포함되고 특정 영역의 일부분이 아닌 가상페이지들은 존재하지 않으며, 프로세스에 의해 참조될 수 없다. 영역이라는 개념은 중요한데, 이것은 가상 주소공간이 간격을 가질 수 있게 해준다. 커널은 존재하지 않는 가상페이지를 계속해서 추적하지는 않으며, 이러한 페이지들은 메모리, 디스크 또는 커널 자신 내부에서 추가적인 자원을 소모하지 않는다.
• 커널은 시스템 내 각 프로세스를 위해 고유의 태스크 구조를 관리한다. 태스크 구조의 원소들은 커널이 프로세스를 실행하는데 필요한 모든 정보를 포함하거나 가리킨다.
• 태스크 구조 내 엔트리 중의 하나는 가상메모리의 현재 상태를 구정하는 mm_struct를 가리킨다.

9.8 메모리 매핑

• 리눅스는 가상메모리 영역의 내용을 디스크의 객체에 연결해서 초기화한다. 영역들은 다음 두 종류의 객체 중의 하나로 매핑될 수 있다.
  1. 리눅스 파일 시스템 내의 일반 파일 : 한 영역은 실행가능 목적파일과 같은 일반 디스크 파일의 연속적인 섹션으로 매핑될 수 있다. 파일 섹션은 페이지 크기의 조각들로 나누어지고, 이들은 각각 가상페이지의 초기 내용을 포함하고 있다. 요구 페이징 때문에 CPU가 처음 페이지에 접근할 때까지는 이 가상페이지들 중 아무것도 실제로 물리 메모리로 스왑되어 들어오지 않는다. 만일 이 영역이 파일 섹션보다 더 크다면, 이 영역은 0으로 매핑된다.
  2. 무기명 파일 : 한 영역은 또한 무기명 파일로 매핑될 수 있다. 이 파일은 커널이 만든 것이며, 모두 이진수0을 포함한다. CPU가 이 영역의 가상페이지에 처음으로 접근할 때, 커널은 물리 메모리 내에서 적당한 희생자 페이지를 찾아내고, 만일 이것이 dirty하다면 희생자 페이지를 스왑아웃하고, 희생자 페이지를 이진수0으로 덮어쓰고, 이 페이지가 존재한다고 표시하기 위해 페이지 테이블을 갱신한다. 어떤 데이터도 실제로는 디스크와 메모리 사이에 이동하지 않았다는 점에 유의해야 한다. 이 이유에서 무기명 파일로 매핑된 영역 내의 페이지들은 때로 무요구(demand-zero) 페이지 라고 불린다.

9.8.1 다시보는 공유객체

• 각각의 프로세스를 위해 물리 메모리 상에 이와 같이 공통으로 사용하는 코드를 중복해서 두는 것은 매우 낭비다. 메모리 매핑을 통해서 어떻게 객체들이 다수 프로세스들에 의해 공유될 수 있는지 깔끔한 메커니즘을 가지게 됐다.
• 객체는 공유 가상메모리 영역으로 공유객체 또는 사적객체로 매핑될 수 있다. 공유객체를 자신의 공유 주소공간으로 매핑한다면, 이 프로세스가 이 영역에 쓰는 모든 내용은 자신의 공유 메모리 내로 객체를 매핑한 다른 프로세스들도 볼 수 있게 된다. 나아가서 이러한 변경된 내용은 디스크 상의 원래의 객체에도 반영된다.
• 반면에 사적객체에 매핑된 영역에 관한 수정사항들은 다른 프로세스들은 볼 수 없으며, 이 영역에서 프로세스가 수행한 모든 쓰기 작업들은 디스크 상의 객체에는 반영되지 않는다. 공유된 객체가 매핑된 가상메모리 영역은 종종 공유영역이라고 불린다. 사적영역과 비슷하게 정의된다.
• 사적객체를 매핑하는 각 프로세스에 대해서, 대응되는 사적영역에 대한 페이지 테이블 엔트리는 읽기 - 허용으로 표시되어 있으며, 영역 구조체는 사적 copy-on-write로 표시 되어있다. 두 프로세스 모두 자신의 사적영역에 쓰려고 하지 않는 한, 이들은 물리 메모리에 단 한 개의객체 사본을 계속 공유한다. 그렇지만 한 프로세스가 사적영역내의 일부 페이지에 쓰려고 하는 순간 쓰기 작업은 보호 오류를 유발한다.
• 핸들러는 이 페이지의 새로운 사본을 물리 페이지 내에 만들고, 페이지 테이블을 갱신해서 새로운 사본을 가리키도록 하며, 그 후에 이 페이지에 대한 쓰기 허가를 복원한다. 오류핸들러가 리턴할 때, CPU는 이 쓰기작업을 재실행한다.

9.9 동적메모리 할당

• 동적메모리 할당기는 힙이라고 하는 프로세스의 가상메모리 영역을 관리한다.
• 힙이 미초기화된 데이터 영역 직후에 시작해서 위쪽으로(높은 주소 방향으로) 커지는 무요구 메모리 영역이라고 가정할 것이다. 커널은 힙의 꼭대기를 가리키는 변수 brk를 사용한다.
• 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당 되었거나 가용한 가상메모리의 연속적인 묶음이다. 할당된 블록은 응용하기 위해 명시적으로 보존되었다. 가용한 블록은 할당을 위해 사용할 수 있다. 가용블록은 응용이 명시적으로 할당할 때 까지 가용한 상태로 남아있다. 할당된 블록은 응용에 의해 명시적으로 또는 메모리 할당기 자신에 의해 묵시적으로 반환될 때까지 할당된 채로 남아있다.
• 메모리 할당기 두 가지 유형
  • 명시적 할당기 : 응용이 명시적으로 할당된 블록을 반환해줄 것을 요구한다.
  • 묵시적 할당기 : 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출 할 수 있을 것을 요구한다. 가비지 컬렉터라고 알려져 있다. 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라고 부른다.

9.9.1 malloc과 free 함수

• malloc 함수는 블록 내 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다. 32비트 모드에서 malloc은 주소가 항상 8의 배수인 블록을 리턴하고 64비트 모드에서 주소는 항상 16의 배수다.
• sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다. 성공한다면 이전의 brk값을 리턴하고, 아니면 -1을 리턴하고 errno을 ENOMEM으로 설정한다. 만일 incr이 0이면 sbrk는 현재 brk값을 리턴한다. 프로그램들은 할당된 힙 블록을 free함수를 호출해서 반환한다. 인자는 할당된 블록의 시작을 가리켜야 한다.

9.9.3 할당기의 요구사항과 목표

• 명시적 할당기들은 다소 엄격한 제한사항 내에서 동작해야한다.
  • 임의의 요청순서 처리하기 : 응용 프로그램은 각각의 가용블록이 이전의 할당 요청에 의해 현재 할당된 블록에 대응되어야 한다는 제한사항을 만족하면서 임의의 순서로 할당과 반환요청을 할 수 있다.
  • 요청에 즉시 응답하기 : 할당기는 할당 요청에 즉시 응답해야한다. 따라서 할당기는 재요청하거나 버퍼 요청을 할 수 없다.
  • 힙만 사용하기 : 확장성을 갖기 위해서 할당기가 사용하는 비확장성 자료구조들은 힙 자체에 저장되어야 한다.
  • 블록 정렬하기(정렬요건) : 할당기는 블록들이 이들이 어떤 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 한다.
  • 목표1. 처리량 극대화 하기
  • 목표2. 메모리 이용도를 최대화 하기

9.9.4 단편화

• 나쁜 힙 이용도의 주요 이유는 단편화라고 알려진 현상인데, 이것은 가용메모리가 할당 요청을 만족시키기에는 가용하지 않았을 때 일어난다.
• 내부 단편화
  • 내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다.
  • 내부 단편화는 정량화 하기가 간단하다. 이것은 단순히 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합이다.
• 외부 단편화
  • 외부 단편화는 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리 할 수 있는 단일한 가용블록은 없는 경우에 발생한다.
  • 외부 단편화는 내부 단편화보다는 훨씬 더 측정하기 어려운데, 그것은 이전 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라 미래의 요청 패턴에도 의존하기 때문이다.
  • 외부 단편화가 측정하기 어렵고 예측하기 불가능하기 때문에 할당기들은 대개 많은 수의 더 작은 가용블록들 보다는 더 적은 수의 더 큰 가용블록들을 유지하려는 방법들을 채택한다.

9.9.6 묵시적 가용리시트

• 헤더는 블록이 할당 되었는지 가용상태인지를 나타내기 위해 최소 중요비트(할당된 비트)를 사용한다. 헤더 다음에는 응용이 malloc을 불렀을 때 요구한 데이터가 따라온다. 데이터 다음에는 사용하지 않는 패딩이 따라올 수 있는데, 이들의 크기는 가변적이다.
• 이러한 구조를 묵시적 리스트라고 부르는데 그것은 가용블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문이다. 할당기는 간접적으로 가용블록 전체 집합을 힙 내의 전체 블록을 다니면서 방문 할 수 있다. 어떤 특별히 표시한 마지막 블록이 필요하다.
• 묵시적 가용리스트의 장점은 단순성이다. 중요한 단점은 할당된 블록을 배치하는 것과 같은 가용리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 것이다.

9.9.7 할당한 블록의 배치

• 요청한 블록을 저장하기에 충분히 큰 가용블록을 검색하는데 수행하는 방법을 배치정책이라고 한다.
• first fit : 가용리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용블록을 선택한다.
  • 장점 : 리스트의 마지막에 가장 큰 가용블록을 남겨두는 경향이 있다
  • 단점 : 리스트의 앞 부분에 작은 가용 블록들을 남겨두는 경향이 있어서 검색시간이 늘어난다.
• next fit이 first fit보다 최악의 메모리 이용도를 갖는다.
• best fit이 일반적으로 first fit이나 next fit 보다는 더 좋은 메모리 이용도를 가진다.

9.9.8 가용블록의 분할

• 할당기가 크기가 맞는 가용블록을 찾은 후에 가용블록의 어느정도를 할당할지에 대해 정책적 결정을 내려야 한다. 한 가지 옵션은 이 가용블록 전체를 사용하는 것이다. 간단하고 빠르지만 큰 단점은 내부 단편화가 생긴다는 것이다.

9.9.9 추가적인 힙 메모리 획득하기

• 할당기는 커널에게 sork 함수를 호출해서 추가적인 힙 메모리를 요청한다. 할당기는 추가 메모리를 한 개의 더 큰 가용블록으로 변환하고, 이 블록을 가용리스트에 삽입한 후에 요청한 블록을 이 새로운 가용블록에 배치한다.

9.9.10 가용블록 연결하기

• 오류 단편화(false fragmentation)를 극복하기 위해 실용적인 할당기라면 연결(coalescing)이라는 과정으로 인접 가용블록들을 통합해야 한다. 이 과정에서 언제 연결을 수행해야 할 지에 관한 중요한 정책결정을 해야 한다.
• 블록이 반환될 때마다 인접블록을 통합해서 즉시연결이나 일정 시간후에 가용블록들을 연결하기 위해 기다리는 지연연결을 선택할 수 있다.

9.9.11 경계태그로 연결하기

• 각 블록의 끝 부분에 풋터(footer)를 추가하는 것으로, 이 풋터는 헤더를 복사한 것이다. 만일 각 블록이 이와 같은 풋터를 포함하게 되면, 할당기는 시작 위치와 이전 블록의 상태를 자신의 풋터를 조사해서 결정할 수 있게되며, 이것은 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치한다.
• 단점은 각 블록이 헤더와 풋터를 유지해야 하므로 만일 응용이 많은 작은 크기의 블록을 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다.

9.9.14 분리 가용리스트

• 단일 연결 가용블록리스트를 사용하는 할당기는 한 개의 블록을 할당하는데 가용블록의 수에 비례하는 시간이 필요하다. 할당시간을 줄이는 대표적인 방법으로 알려진 분리저장장치(segregated storage)는 다수의 가용리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장한다. 기본적인 아이디어는 모든 가능한 블록 크기를 크기 클래스 size class 라고 하는 동일 클래스의 집합들로 분리하는 것이다.
• 할당기는 가용리스트의 배열을 관리하고, 크기 클래스마다 크기가 증가하는 순서로 한 개의 가용리스트를 가진다. 할당기가 크기 n의 블록이 필요하면 적당한 가용리스트를 검색한다. 만일 크기가 맞는 블록을 찾을 수 없다면, 다음 리스트를 검색하는 식으로 진행한다.

9.10 가비지 컬렉션

• 가비지 컬렉터는 더 이상 프로그램에서 사용하지 않는 블록들을 자동으로 반환하는 동적 저장장치 할당기다. 이러한 블록들을 가비지 라고한다. 자동으로 힙 저장장치를 반납하는 과정을 가비지 컬렉션이라고 한다. 가비지 컬렉션을 지원하는 시스템에서 응용프로그램은 명시적으로 힙 블록을 할당하지만, 결코 명시적으로 이들을 반환하지 않는다. 대신, 가비지 컬렉터가 주기적으로 가비지 블록을 식별하고 이 블록들을 가용리스트로 돌려주기 위해 적절하게 free를 호출한다.

9.10.1 가비지 컬렉터 기초

• 가비지 컬렉터는 방향성 도달 그래프로 메모리를 고려한다. 그래프의 노드들은 루트노드들과 힙노드들로 나눈다. 각 힙 노드는 힙 내 한 개의 할당된 블록에 대응된다. 방향성edge p→q는 블록 p내부의 위치가 블록 q내부의 위치를 가리킨다는 것을 의미한다. 루트노드는 힙으로의 포인터를 포함하는 힙에 속하지 않는 위치들에 대응된다.
• 어떤 루트노드에서 p로 edge가 존재한다면 p는 도달할 수 있다. 응용프로그램은 어떤 시점에서든 도달 할 수 없는 노드를 다시는 사용할 수 없는 가비지에 대응시킨다. 가비지 컬렉터의 역할을 이 도달성 그래프의 표시를 관리하는 것과 도달 불가 노드들을 free시켜 반환받고, 이들을 가용리스트로 돌려주는것이다.

9.11 C프로그램에서의 공통된 메모리 관련버그

9.11.1 잘못된 포인터의 역참조

• 한 프로세스의 가상 주소공간 내에 어떤 의미 있는 데이터로도 매핑되지 않은 큰 구멍들이 존재한다. 만일 포인터를 이 구멍들 중의 하나로 역참조 하려하면, 운영체제는 프로그램을 segmentation 예외로 종료한다. 또한, 일부 가상메모리는 읽기-가능만 허용되어 있다. 이 영역에 쓰려고 하면 보호 예외로 프로그램을 종료시킨다.

9.11.2 초기화되지 않은 메모리를 읽는 경우

• bss 메모리 위치들(초기화되지 않은 전역 C 변수들 같은)은 항상 로더에 의해 0으로 초기화 되며, 이것은 힙 메모리의 경우에는 그렇지 않다. 보편적인 에러는 힙 메모리가 0으로 초기화 한다고 가정하는 것이다.

9.11.3 스택 버퍼 오버플로우 허용하기

• 입력 스트링의 길이를 조사하지 않고 스택 상의 타깃 버퍼에 쓰려고 한다면 이 프로그램은 버퍼 오버플로우 버그를 갖게 된다.

9.11.4 포인터와 이들이 가리키는 객체들이 같은 크기라고 가정하기

• 한 가지 큰 실수는 객체를 가리키는 포인트들이 이들이 가리키는 객체들과 같은 크기라고 가정하는 것이다.

9.11.5 Off-by-One 에러 만들기

• 덮어쓰기 버그의 한 종류이다.

9.11.6 포인터가 가리키는 객체 대신에 포인터 참조하기

• C 연산자의 결합성과 우선순위에 대해 부주의하면, 포인터가 가리키는 객체 대신에 포인터를 잘못 조작하게 된다.
• 우선순위와 결합성에 대해 의심스럽다면 괄호를 사용해야 한다는 것이다.

9.11.7 포인터 연산에 대한 오해

• 또 다른 공통적인 실수는 포인터에 대한 산술연산이 반드시 이들이 가리키는 객체의 크기 단위로 수행되어야 하는 것이지 바이트 단위로 이루어지는 것이 아니라는 것이다.

9.11.8 존재하지 않는 변수 참조하기

• 더 이상 유효하지 않은 지역변수를 참조하게 되는 경우

9.11.9 가용 힙 블록 내 데이터 참조하기

• 이미 반환한 힙 블록 내 데이터를 참조한는 것이다.

9.11.10 메모리 누수 leak 유발

• 메모리 누수는 프로그래머가 할당된 블록들을 반환하는 것을 잊어서 힙에 가비지를 부주의하게 만들 때 일어나는 조용한 살인자다.
• 만일 leak이 자주 호출되면, 힙은 점차적으로 가비지로 가득 차게 되고, 최악의 경우 전체 가상 주소공간을 소모하게 된다. 메모리 누수는 특히 데몬, 서버와 같이 종료 되지 않는 프로그램들의 경우에 심각하다.