크래프톤 정글 - 3Week 24.01.25 - 24.01.31 부제 : 새로운 시작

회고

3주차가 벌써 지나갔다.

너무 빠른 것 같기도 하고, 뭔가 쉴 틈 없이 몰아치니 더 빠른 것 같기도 하고..

어렵다! 매주 더 어려워 질 수 있나? 더 힘들어 질 수 있나? 생각 하는데, 그 생각을 관통하듯이 점점 더 어려워진다. 내가 성장할수록 적이 강해진다니 소년만화의 왕도일지도

파워 인플레이션이 일어난 장기연재 만화마냥 해결해야할 문제가 점점 강해지는 것을 보니 골치가 아프다.

하지만 내가 더 강해질거니까.

대체 불가능한 개발자가 되려면 이 정도는 해결할 수 있어야지.

제일 중요한 건 나만 힘든게 아니고, 나만 힘들었던게 아니니까. 그리고 내가 선발자로 걸어가는게 아닌 남들이 걸어갔던 그 길을 걸어가고 있는거니까 덜 힘들다고 생각한다.

그리고 사실 아직 숨 쉴만하다.

막막해서 울고 싶지는 않으니까 더 강해져도 이겨낼 수 있지 않을까 생각한다.

이제 4주차는 C언어와 RB트리다. 다시 C를 하게됐는데 잘..할수있게씨ㅣㅣ지..?

조아조아 이번주 WIL도 레츠꼬!!

CSAPP

3.10.2 실제 적용하기 : GDB 디버거 사용하기

• GDB를 사용하며, 프로그램의 실행을 정교하게 제어하면서 실행되는 프로그램을 관찰하여 프로그램의 동작을 분석할 수 있다.
• 일반적인 방법은 브레이크 포인트(BreakPoint)를 프로그램에서 관심이 있는 부분 근처에 설정하는 것이다.
• 함수의 시작 직후나 프로그램의 특정 주소에 설정할 수 있다. 프로그램 실행 중에 브레이크 포인트를 만나게 되면, 프로그램은 실행을 중단하고, 제어를 사용자에게 넘긴다. 브레이크 포인트로부터 레지스터나 메모리의 위치의 값을 다양한 형식으로 조사할 수 있다.

3.10.3 범위를 벗어난 메모리 참조와 버퍼오버플로우

• C에서 배열참조시 범위를 체크하지 않으며, 지역변수들이 스택에 보존용 레지스터들과 리턴주소 같은 상태 정보와 함께 스택에 저장된다. 이러한 조합 때문에 심각한 프로그램 에러가 발생할 수 있는데, 스택에 저장된 상태정보가 범위를 벗어난 배열의 원소에 대한 쓰기 작업에 의해 변경되는 것이다. 그러고 나서 프로그램이 레지스터값을 재 적재 하거나 이렇게 변경된 상태정보를 사용해서 ret 인스트럭션을 실행할 때, 심각한 결과를 초래한다.
• 일반적으로 gets나 저장공간을 오버플로우하게 되는 함수를 사용하는 것은 나쁜 프로그램이 습관으로 평가한다.
• 자주 사용하는 strcpy,strcat,sprintf 같이 자주 사용되는 많은 라이브러리 함수들은 대상 버퍼 크기를 나타내는 아무런 수단도 없이 일련의 바이트를 생성할 수 있는 특성을 가진다. 이런 조건들은 버퍼오버플로우 시 취약성이 될 수 있다.
• 버퍼 오버플로우의 보다 치명적인 사용은 일반적으로 프로그램이 하지 않을 기능들을 실행하도록 하는 것이다. 이것은 컴퓨터 네트워크 상의 시스템 보안성을 공격하는 가장 일반적인 방법 중 하나다. 일반적으로 탐색코드 라고 하는 실행코드를 바이트 인코딩한 탐색코드를 가리키는 포인터로 리턴주소를 덮어쓰는 약간의 추가적인 바이트들을 포함하는 스트링을 입력한다. ret 인스트럭션을 실행하면 탐색코드로 점프하게 된다.

3.10.4 버퍼오버플로우 공격 대응기법

스택랜덤화

• 스택의 위치를 프로그램의 매 실행마다 다르게 해주는 것이다. 그래서 많은 컴퓨터가 동일한 코드를 실행하고 있을지라도 이들은 모두 완전히 다른 스택 주소를 사용하게 된다.

스택 손상 검출

• 스택이 손상되는 것을 감지하는 것이다. C에서 배열의 경계를 넘는 쓰기 작업을 방지하는 안정적인 방법은 존재하지 않는다. 그 대신, 프로그램은 해로운 효과를 발생하기전에 이러한 쓰기 작업이 발생하는 것을 감지하는 시도를 할 수 있다.
• 최신 GCC에서는 스택 보호코드를 버퍼오버플로우를 감지하기 위해 생성된 코드에 추가하는 기법을 구현한다.

실행코드 영역 제한하기

• 공격자가 실행코드를 시스템에 추가 할 가능성을 제거하는 것이다. 한 가지 방법은 어느 메모리 영역이 실행코드를 저장하는지를 제한하는 것이다. 일반적인 프로그램에서 컴파일러가 만든 코드를 저장하는 메모리 부분만이 실행 가능하면 된다. 다른 부분들은 일긱와 쓰기만 허용하도록 제한할 수 있다.

3.10.5 가변크기 스택프레임 지원하기

• 일부 함수들은 가변적인 지역공간 크기를 필요로 한다. 이런 경우는 함수가 스택에 임의의 크기의 바이트를 할당하는 표준함수인 alloca를 호출할 때 일어난다. 또 이 코드가 가변 크기의 지역 배열을 선언할 때 일어날 수 있다.
• 가변 크기 스택 프레임을 처리하기 위해 x86-64 코드는 레지스터 %rbp를 이용해서 프레임 포인터(frame pointer, base pointer라고 부르며, 따라서 %rbp에서 문자 bp를 사용한 것을 볼 수 있다.) %rbp 레지스터는 피호출자 - 저장 레지스터기 때문에 이 코드는 스택에 이전 버전의 %rbp를 보관한다. 그 후 이 함수가 실행되는 동안 계속 %rbp를 현 위치를 가리키도록 유지하며, 이것은 고정길이 지역변수들을 %rbp에 대한 상대적인 오프셋 값으로 참조한다.

3.11 부동소수점 코드

• 프로세서의 부동소수점 아키텍처의 여러가지 개념
  • 부동소수점 값들이 저장되고 접근되는 방법, 이것은 대개 레지스터들의 일부 형태로 이뤄진다.
  • 부동소수점 데이터로 연산하는 인스트럭션
  • 함수들의 인자와 리턴값으로 부동소수점 값들을 전달하기 위해 이용되는 관례들
  • 함수를 호출하는 동안 레지스터를 보존하는 관례들 - 일부 레지스터는 호출자 보관으로 저장한다. 나머지는 피호출자 저장으로 지정한다.
• SIMD 단일 인스트럭션 다중 데이터 방식
• 동일 연산이 다수의 서로 다른 데이터 값들에 대해 병렬로 수행된다.
• x86-64 부동소수점은 프로시저 인자의 전달과 리턴 값의 전달 관습을 포함해서 SSE나 AVX에 기초하고 있다.
• AVX 부동소수점 아키텍처는 %ymm0 - %ymm15로 이름 붙인 16개의 YMM레지스터들에 저장된다. 각 YMM레지스터는 256비트(32바이트)길이를 갖는다. 스칼라 데이터로 연산할 때, 이 레지스터들은 부동소수점 데이터만을 보관하며, 하위 32비트(float), 64비트(double)만이 사용된다.

3.11.1 부동소수점 이동 및 변환 연산

• 메모리를 참조하는 인스트럭션들은 스칼라 인스트럭션들이며, 이것은 이들이 묶인 데이터 값들이 아닌 개별 값들에 대해 연산한다는 것을 의미한다. 데이터는 메모리나 XMM 레지스터들에 저장된다.
• GCC에서 데이터를 메모리에서 XMM레지스터로, 또는 XMM레지스터에서 메모리로 이동하기 위해서만 스칼라 이동연산을 이용한다. 두 개의 XMM 레지스터 간의 데이터 이동을 위해서는 한 개의 XMM레지스터의 내용 전체를 다른 레지스터로 복사하기 위해 두 개의 인스트럭션 중 하나를 이용한다.
  • 단일 정밀도 vmovaps
  • 이중 정밀도 vmovapd
• 이들의 경우 프로그램이 레지스터 전체를 복사하는지, 하위 값들만 복사하는지 여부는 프로그램의 기능이나 실행속도에는 아무 영향을 주지 않으며, 따라서 스칼라 데이터에 국한된 인스트럭션 대신 이 인스트럭션을 사용하더라도 아무런 실질적인 차이가 없다. 이들 인스트럭션의 문자 ‘a’는 ‘aligned’를 의미한다. 메모리에 읽고 쓰기 위해 사용될 때, 만일 주소가 16바이트 정렬요건을 만족하지 못한다면 이들은 예외를 발생시킨다. 두개의 레지스터 간에 이동에 대해서는 부정확한 정렬의 가능성은 없다.

3.11.2 프로시저에게 부동소수점 코드

• x86 - 64에서 XMM레지스터들이 함수로 부동소수점 인자를 전송하고 부동소수점 값들을 리턴 할 때 사용된다.
  • 최대 여덟개의 부동소수점 인자들이 %xmm0 - %xmm7 XMM 레지스터들로 전달될 수 있다.
  • 한 개의 부동소수점 값을 리턴하는 함수는 레지스터 %xmm0을 이용한다.
  • 모든 XMM레지스터들은 호출자 저장방식이다. 피호출자는 이들 레지스터를 저장하지 않은채로 변경할 수 있다.
  • 어떤 함수가 포인터, 정수, 부동소수점 인자들의 조합을 가지고 있을 때, 포인터와 정수들은 범용 레지스터로 전달되지만, 부동소수점 값들은 XMM레지스터들로 전달된다.
  • 이것은 인자들의 레지스터 매핑이 이들의 타입과 순서에 의존한다는 것을 의미한다.

9. 가상메모리

• 한 시스템의 프로세스들은 CPU와 메인 메모리를 다른 프로세스들과 공유한다.
• 메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상 메모리VM 라고 알려진 메인 메모리의 추상화를 제공한다. 가상 메모리는 각 프로세스에 하나의 크고 통합 된 사적 주소공간을 제공한다. 이것은 하드웨어 예외, 하드웨어 주소번역, 메인 메모리, 디스크 파일, 커널 소프트웨어들 사이의 상호작용이다. 가상 메모리는 한 개의 깔끔한 메커니즘을 사용해 세 주요 기능을 제공한다.
  1. 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급해서 메인 메모리내 활성화 영역만 유지하고, 데이터를 디스크와 메모리간에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 상용한다.
  2. 각 프로세스에 통일된 주소 공간을 제공함으로써 메모리 관리를 단순화 한다.
  3. 각 프로세스의 주소 공간을 다른 프로세스에 의한 손상으로 부터 보호한다.
• 가상 메모리를 프로그래머가 이해해야 하는 이유
  • 가상 메모리가 중심이다. 가상 메모리는 모든 컴퓨터 수준에 스며들어 있으며, 하드웨어 예외, 어셈블러, 링커, 로더, 공유 객체 파일, 프로세스를 설계하는데 중요한 역할을 한다. 가상 메모리를 이해하면 어떻게 시스템이 일반적으로 동작하는지 이해하는데 도움이 된다.
  • 가상 메모리는 강력하다. 가상 메모리는 이용에 메모리 블록을 생성하고 없애고, 메모리 블록을 디스크 파일로 매핑하고, 메모리를 다른 프로세스들과 공유할 수 있는 강력한 기능을 준다. 가상 메모리를 이해하면 가상 메모리의 강력한 성능을 여러분의 응용 프로그램에 적용하는데 도움이 될 것이다.
  • 가상 메모리는 위험하다. 응용 프로그램은 이들이 변수를 참조하고, 포인터를 역참조하고, malloc 같은 동적 할당 패키지로 호출할 때마다 가상 메모리와 상호작용을 한다. 만일 가상 메모리가 잘못 사용되면, 응용 프로그램은 당혹스럽고 퍼저나가는 메모리 관련 버그로 부터 괴로움을 당할 수 있다. 가상 메모리와 이를 관리하는 malloc같은 할당 패키지를 이해하면 이러한 에러를 피하는데 도움이 된다.

9.1 물리 및 가상주소의 방식

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

9.2 주소공간

• 주소공간은 비음수 정수 구조의 정렬된 집합이다.
• 만약 주소공간의 정수가 연속적이라면, 이 공간은 선형 주소공간이라고 한다. 우리는 논의를 간단히 하기 위해서 언제나 선형 주소공간을 가정하겠다. 가상 메모리를 갖는 시스템에서 CPU는 가상주소 공간이라고 불리는 N=2^N 주소의 주소공간에서 가상의 주소를 생성한다.
• 또한 컴퓨터 시스템은 이 시스템내의 M바이트의 물리 메모리로 대응되는 물리 주소 공간을 갖는다.
• 주소공간의 개념은 중요한데, 그것은 이 개념이 데이터 객체와 그들의 특성(주소들)들 간에 명확한 구별을 해주기 때문이다. 이 구별을 인지하면 일반화 할 수 있으며, 각 데이터 객체가 다중 독립주소를 가질 수 있도록 하고, 이 각각의 주소는 서로 다른 주소공간에서 선택되었다. 이것은 가상 메모리의 기본 아이디어다. 메인 메모리의 각 바이트는 가상주소 공간으로 부터 선택된 가상주소를 가진다.

9.3 캐싱도구로서의 VM

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

9.3.1 DRAM 캐시의 구성

• 메모리 계층 구조 내에서 DRAM 캐시의 위치는 이들이 구성된 방식에 큰 영향을 가진다. DRAM이 최소한 SRAM보다 10배는 더 느리고, 디스크는 DRAM보다 100,000배 더 느리다는 점을 상기 해야한다. 따라서 DRAM 캐시미스는 SRAM 캐시에서의 미스에 비교하면 값이 매우 비싸며, 그 이유는 DRAM 캐시 미스는 디스크에서 처리되지만 SRAM 캐시미스는 대개 DRAM 기반 메인 메모리로 부터 지원 받기 때문이다. 더 나아가, 디스크 섹터로 부터 첫 번째 바이트를 읽는 비용은 섹터에서 연속적인 바이트를 읽는 것보다 약 100,000배 더 느리다. 최소한 DRAM 캐시의 조직이 전적으로 엄청난 미스 비용으로 진행되었다. 최소한 DRAM 캐시의 구성은 전적으로 엄청난 규모의 미스비용으로 영향받는다.
  • 캐시히트 : CPU에서 요청한 데이터가 캐시에 존재하는 경우
  • 캐시미스 : CPU에서 요청한 데이터가 캐시에 존재하지 않는 경우
  • 섹터 : 디스크의 저장공간을 나누는 단위 중 최소 단위
• 큰 규모의 미스 비용과 첫 번재 바이트를 접근하는데 드는 비용 때문에 가상 페이지는 커지고 있으며, 대개 4KB에서 2MB까지 값을 가진다. DRAM 캐시는 완전 결합성이다. 즉, 모든 가상 페이지는 물리 페이지에 둘 수 있다. 미스 발생 시 교체 정책은 더 큰 중요성을 가정하는데, 그것을 잘못 된 가상 페이지를 교체하는 것과 관련된 비용이 매우 높기 때문이다. 그래서 운영체제는 하드웨어가 SRAM 캐시에 대해서 처리하는 것보다 훨씬 더 복잡한 DRAM 캐시를 위한 교체 알고리즘을 사용한다. 마지막으로 디스크의 큰 접근 시간 때문에 DRAM은 항상 write-through 대신에 write-back을 사용한다.

9.3.2 페이지 테이블

• 모든 캐시에서처럼 VM 시스템은 가상 페이지가 DRAM 어딘가에 캐시 되었는지 결정하기 위한 방법을 가지고 있어야 한다. 그렇다면, 이 시스템은 어떤 물리 페이지를 캐싱했는지 결정해야 한다. 만일 미스가 존재한다면 시스템은 디스크 어디에 가상 페이지가 저장 되어 있는지 결정해야 하며, 물리 메모리중에서 희생자 페이즈를 선택해야 하고, 가상 페이지를 디스크에서 DRAM으로 복사해서 희생자 페이지를 교체한다.
• 이러한 역량은 운영체제 소프트웨어와 MMU내의 주소 번역 하드웨어, 가상 페이지를 물리 페이지로 매핑하는 페이지테이블이라고 알려진 물리 메모리에 저장된 자료구조의 조합으로 제공된다. 주소 번역 하드웨어는 이들이 가상주소를 물리주소로 변환할 때마다 페이지 테이블을 읽는다. 운영체제는 페이지 테이블의 콘텐츠 관리와 페이지들을 디스크와 DRAM 사이에서 왔다 갔다 하는 것을 관장한다.
• 페이지 테이블의 기본구조. 페이지 테이블은 페이지 테이블 엔트리(PTE)의 배열이다. 가상주소 공간은 각 페이지는 페이지 테이블 내에 고정된 오프셋 위치에 PTE를 갖는다. 편의상 PTE가 한 개의 유효비트, N개의 주소필드로 구성된다고 가정하겠다. 유효비트는 가상 페이지가 현재 DRAM에 캐시되어 있는지를 나타낸다. 만일 유효비트가 세팅 되었다면, 주소 필드는 가상페이지가 캐시되어 대응되는 DRAM의 물리 페이지의 시작을 나타낸다. 만일 유효비트가 세팅되어있지 않다면, NULL 주소는 가상 페이지가 아직 할당 되지 않았음을 나타낸다. 그렇지 않은 경우에 주소는 디스크 상의 가상 페이지의 시작 부분을 가리킨다.

9.3.3 페이지 적중

• CPU가 DRAM에 캐시되어 있는 가상 메모리의 워드를 한 개 읽을 때, 주소번역 하드웨어는 PTE를 찾기 위해서 인덱스로 가상주소를 사용하고, 이것을 메모리에서 읽는다. 유효비트가 세팅되어 있기 때문에 주소번역 하드웨어는 메모리에 캐시되어 있다는 것을 알고 있다. 그래서 PTE내의 물리 메모리 주소를 사용해서 해당 워드의 물리주소를 구성한다.

9.3.4 페이지 오류

• 가상 메모리 용어에서 DRAM 캐시미스는 페이지 오류(Page Fault)라고 알려져 있다.
• CPU는 DRAM에 캐시되어 있지 않은 워드를 참조했다. 주소번역 하드웨어는 메모리에서 PTE를 읽으며, VP가 캐시되어 있지 않다는 것을 유효 비트로부터 유추해서 페이지 오류 예외를 유발시킨다.

9.3.5 페이지의 할당

• 운영체제가 가상메모리의 새로운 페이지를 할당할 때 디스크 상에 공간을 만들고, 디스크에 새롭게 만든 페이지를 가리키도록 한다.

9.3.6 문제 해결을 위한 또 한 번의 지역성 등장

• 프로그램이 전체 실행하는 동안 참조하는 서로 다른 페이지의 수가 전체 물리 메모리의 크기보다 더 클지라도 지역성의 원리는 시간 상의 어느 시점에서라도 이들이 동작집합(Working set) 또는 거주집합(Resident set)이라고 알려진 보다 작은 활성화된 페이지 집합에서 동작하는 경향을 보일 것이라는 점을 약속한다.
• 우리의 프로그램이 좋은 시간 지역성을 가지고 있으면, 가상 메모리 시스템은 상당히 잘 동작한다. 하지만 만일 동작집합 크기가 물리 메모리보다 더 크면, 프로그램은 쓰레싱(thrashing)이라고 알려진 불행한 상황을 만들 수 있는데, 이 경우 페이지들이 연속적으로 스왑해서 들어오고 나가기를 반복한다.

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

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

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

• 모든 현대 컴퓨터 시스템은 운영체제가 메모리 시스템에 접근하는 것을 제어할 수 있는 수단을 제공한다. 사용자 프로세스는 자신의 읽기 - 허용 코드 섹션을 수정하도록 허용되지 않아야 한다. 또한 커널 내의 코드와 데이터 구조들도 읽거나 수정할 수 없어야 한다. 모든 관련 프로세스들이 명시적으로 허용하지 않았다면(명시적인 프로세스 간 통신 시스템 콜을 호출해서) 다른 프로세스의 사적 메모리를 읽거나 쓸 수 없어야 한다.
• 별도의 가상주소 공간을 제공하면 사적 메모리를 다른 프로세서로부터 분리하는 것이 쉬워진다. 그러나 주소 번역 메커니즘은 보다 섬세한 접근 제어를 제공하기 위한 자연스러운 방법으로 확장될 수 있다.
• CPU가 주소를 만들 때 마다 PTE를 읽기 때문에 PTE에 허가 비트를 추가해서 주소 번역 하드웨어가 가상 페이지 내용으로의 접근을 제어 하는 것은 간단하다.
• 프로세스는 SUP0인 페이지만 접근을 허용한다. READ,WRITE는 이 페이지에 대한 읽기와 쓰기 접근을 제어한다.
• 만일 어떤 인스트럭션이 이 허가 사항을 위반한다면, CPU는 일반 보호 오류를 발생시켜서 SIGSEGV 시그널을 위반한 프로세스로 보내서 커널 내의 예외 핸들러로 제어를 이동시킨다. 리눅스 쉘은 이와 같은 예외를 ‘세그먼트 오류(Segmentation Fault)’라고 본다.
• 한 시스템의 프로세스들은 CPU와 메인 메모리를 다른 프로세스들과 공유한다.
• 메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상 메모리 VM이라고 알려진 메인 메모리의 추상화를 제공한다. 가상 메모리는 각 프로세스에 하나의 크고 통합된 사적 주소 공간을 제공한다. 이것은 하드웨어 예외, 하드웨어 주소 번역, 메인 메모리, 디스크 파일, 커널 소프트웨어들 사이의 상호작용이다. 가상 메모리는 한 개의 깔끔한 메커니즘을 사용해 세 주요 기능을 제공한다.
  • 메인 메모리를 디스크에 저장 된 주소 공간에 대한 캐시로 취급해서 메인 메모리내 활성화 영역만 유지하고, 데이터를 디스크와 메모리 간에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용한다.
  • 각 프로세스에 통일된 주소 공간을 제공함으로써 메모리 관리를 단순화 한다.
  • 각 프로세스의 주소 공간을 다른 프로세스에 의한 손상으로 부터 보호한다.

9.6 주소의 번역

• 주소 번역의 N원소 가상주소 공간(Virtual Address Space : VAS)과 M 원소 물리주소 공간(Physical Address Space : PAS)의 원소들 간의 매핑이다.
• CPU내에 있는 제어 레지스터인 페이지 테이블 베이스 레지스터(page table base register : PTBR)는 현재 페이지 테이블을 가리킨다. N비트 가상주소는 두 개의 컴포넌트를 가진다.
• p비트 가상 페이지 오프셋(virtual page offset : VPO)과 (n-p) 비트 가상 페이지 번호(virtual page number : VPN). MMU는 VPN을 사용해서 적합한 PTE를 선택한다. VPN0은 PTE0을 선택하고, VPN1은 PTE1을 선택하는 식으로 진행된다. 대응되는 물리주소는 페이지 테이블 엔트리에서 가져온 물리페이지 번호(Physical page number : PPN)와 가상주소에서 온 VPO를 연결한 것이다. 물리와 가상페이지가 모두 P바이트 이므로 물리 페이지 오프셋(physical page offset : PPO)는 VPO랑 동일하다.
• 페이지 히트
  1. 프로세서는 가상 주소를 생성한다.
  2. MMU는 PTE 주소를 생성하고, 이것을 캐시/메인 메모리에 요청한다.
  3. 캐시/메인 메모리는 PTE를 MMU로 리턴한다.
  4. MMU는 물리주소를 구성하고 이것을 캐시/메인 메모리로 보낸다.
  5. 캐시/메인 메모리는 요청한 데이터 워드를 프로세서로 보낸다.
  • 하드웨어가 모두 처리하는 페이지 적중과는 달리, 페이지 오류를 처리하는 것은 하드웨어와 운영체제 커널과의 협력을 필요로 한다.
• 페이지 오류
  1. 위 1 - 3 단계와 동일
  2. PTE의 유효비트는 0이므로 MMU는 예외를 발생시키고, CPU 내의 제어를 운영체제 커널의 페이지 오류 예외 핸들러로 이동시킨다.
  3. 오류 핸들러는 물리 메모리 내의 희생자 페이지를 결정하고, 만일 이 페이지가 수정되었다면 디스크로 페이지를 이동한다.
  4. 오류 핸들러는 새 페이지를 페이지 이동해서 들여오고, 메모리 내의 PTE를 갱신한다.
  5. 오류 핸들러는 처음의 프로세스로 돌아가고, 오류 인스트럭션은 재시작 된다. CPU는 문제를 일으킨 가상 주소를 MMU로 다시 전송한다. 이 가상 페이지는 이제 물리 메모리내에 캐시되어 있으므로 적중이 발생하고 MMU가 단계를 수행한 후에 메인 메모리는 요청한 워드를 프로세서로 넘겨준다.

9.6.1 캐시와 VM의 통합

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

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

• CPU가 가상주소를 생성할 때마다 MMU는 가상 주소를 물리 주소로 번역하기 위해 PTE를 참조 해야한다. 최악의 경우, 이것은 메모리로 부터 추가적인 선입 작업을 필요로 하며, 이를 위ㅎ해서 수십에서 수백 사이클의 비용이 들게 된다. 만일 PTE가 L1에 캐싱 되어 있다면, 이 비용은 2에서 1사이클로 줄어든다. 그렇지만, 많은 시스템들은 이 비용마저도 MMU내에 번역 참조버퍼(Translation lookaside buffer : TLB) 라고 부르는 작은 캐시를 포함해서 제거하려고 한다.
• TLB는 작은 가상 주소 지정 캐시로, 각 라인은 하나의 PTE로 구성된 하나의 블록을 저장한다. TLB는 대개 높은 수준의 결합성을 가진다. 집합선택과 라인매칭을 위해 사용되는 index와 tag필드는 가상 주소내의 가상 페이지 번호에서 추출된다. 만일 TLB가 T 2^t개의 집합을 가지면, TLB 인덱스(TLBI)는 VPN의 t개의 최소 중요 비트와 나머지 비트들로 구성된 TLBtag(TLBT)로 이루어진다.
• TLB 적중이 발생할 때(대부분의 경우) 관련된 단계들을 보여준다. 핵심은 모든 주소 번역 단계를이 온칩 on-chip MMU내에서 수행되기 때문에 매우 빠르다는 것이다.
  1. CPU는 가상 주소를 생성한다.
  2. 2 - 3 MMU는 적당한 PTE를 TLB로 부터 선입한다.
  3. MMU는 가상 주소를 물리 주소로 번역하고, 그것을 캐시/메인 메모리로 전송한다
  4. 캐시/메인 메모리는 요청한 데이터 워드를 CPU로 리턴한다.

9.6.3 다중 레벨 페이지 테이블

• 지금까지 시스템이 주소를 번역하기 위해 한 개의 페이지 테이블을 사용한다고 가정해왔다. 그러나 만일 32비트 주소 공간, 4KB 페이지, 4바이트 PTE인 경우 응용이 작은 크기의 가상주소 공간만 참조하는 경우에도 메모리에 항상 4MB 페이지 테이블을 필요로 하게 된다. 이 문제는 64비트 주소 공간을 사용하는 시스템에 대해서 더 악화된다.
• 페이지 테이블을 압축하는 보편적인 접근법은 대신 페이지 테이블의 계층 구조를 사용하는 것이다.

9.8 메모리 매핑

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

9.8.1 다시보는 공유객체

• 프로세스의 개념은 각 프로세스에 자신만의 가상주소 공간을 제공하며, 이것은 다른 프로세스들에 의해 잘못된 쓰기와 읽기 작업이 발생하는 것을 막아준다. 그렇지만 많은 프로세스들은 동일한 읽기 - 허용 코드 영역을 가지고 있다.
• 많은 프로그램들은 동일한 읽기 - 허용 런타임 라이브러리 코드에 접근할 필요가 있다. 예를 들어, 모든 C 프로그램들은 printf 같은 표준 C라이브러리 함수를 필요로 한다. 각각의 프로세스를 위해 물리 메모리 상에 이와 같이 공통으로 사용하는 코드를 중복해서 두는 것은 매우 낭비다. 메모리 매핑을 통해서 어떻게 객체들이 다수의 프로세스들에 의해 공유될 수 있는지를 제어하는 깔끔한 메커니즘을 가지게 됐다.
• 객체는 공유 가상 메모리 영역으로 공유 객체 또는 사적(Private) 객체로 매핑 될 수 있다. 만일 공유 객체를 자신의 공유주소 공간으로 매핑한다면, 이 프로세스가 이 영역에 쓰는 모든 내용은 자신의 공유 메모리 내로 객체를 매핑한 다른 프로세스들도 볼 수 있게 된다. 나아가서 이런 변경된 내용은 디스크 상의 원래의 객체에도 반영된다.
• 반면에, 사적 객체에 매핑된 영역에 가한 수정사항들은 다른 프로세스들은 볼 수 없으며, 이 영역에서 프로세스가 수행하는 모든 쓰기 작업들은 디스크상의 객체에는 반영되지 않는다. 공유된 객체가 매핑된 가상 메모리 영역은 종종 공유 영역이라고 불린다. 사적영역과 비슷하게 정의된다.
• 객체가 여러 공유 영역에 복수로 매핑된 경우에도 단 한 개의 공유 객체만이 물리 메모리에 저장된다.
• 사적 객체들은 copy-on-write 라고 알려진 영리한 기법을 사용해서 가상 메모리에 매핑된다. 사적 객체는 공유 객체와 똑같은 방법으로 만들어지며, 물리 메모리에 단 한 개의 사적 객체만이 저장된다. 사적 객체를 매핑하는 각 프로세스에 대해서 대응되는 사적 영역에 대한 페이지 테이블 엔트리들은 읽기 - 허용으로 표시되어 있으며, 영역 구조체는 사적 copy-on-write로 표시되어있다. 두 프로세스 모두 자신의 사적 영역에 쓰려고 하지 않는 한, 이들은 물리 메모리내에 단 한 개의 객체 사본을 계속 공유한다. 그렇지만, 한 프로세스가 사적 영역 내의 일부 페이지에 쓰려고 하는 순간 쓰는 작업은 보호 오류를 유발한다.
• 오류 핸들러가 어떤 페이지를 사적 copy-on-write 영역에 쓰려고 하는 프로세스에 의해서 보호 예외가 발생했다고 알릴 때, 핸들러는 이 페이지의 새로운 사본을 물리 페이지 내에 만들고, 페이지 테이블을 갱신해서 새로운 사본을 가리키게 하며, 그 후에 이 페이지에 대한 쓰기 허가를 복원한다. 오류 핸들러가 리턴 할 때, CPU는 이 쓰기 작업을 재 실행하고, 이것은 이제 새롭게 만들어 진 페이지에서 정상적으로 진행한다.
• copy-on-write는 마지막 가능한 순간까지 사적 객체 내에서 페이지를 복사 하는 것을 지연시켜서 부족한 메모리를 가장 효율적으로 사용한다.

9.8.4 함수를 이용한 사용자 수준 메모리 매핑

• 리눅스 프로세스들은 함수를 이용해서 가상 메모리의 새로운 영역들을 만들 수 있으며, 객체들을 이 영역으로 매핑할 수 있다.

9.9 동적 메모리 할당

• 동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상 메모리 영역을 관리한다. 자세한 내용은 시스템마다 다르지만, 일반화의 오류를 범하지 않는 한도에서 힙이 미 초기화 된 영역 직후에 시작해서 위쪽으로(높은 주소 방향으로) 커지는 무 요구 메모리 영역이라고 가정할 것이다. 각각의 프로세스에 대해서, 커널은 힙의 꼭대기를 가리키는 변수 brk(break라고 발음)을 사용한다.
• 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당 되었거나 가용한 가상 메모리의 연속적인 묶음이다. 할당된 블록은 응용하기 위해 명시적으로 보존되었다. 가용한 free블록은 할당을 위해 사용할 수 있다. 가용 블록은 응용이 명시적으로 할당할 때까지 가용한 상태로 남아있다. 할당된 블록은 응용에 의해 명시적으로 또는 메모리 할당기 자신에 의해 묵시적으로 반환 될 때 까지 할당된 채로 남아있다.
• 할당기의 두 개의 기본 유형
  • 명시적 할당기 : 응용이 명시적으로 할당된 블록을 반환해 줄 것을 요구한다. 예를 들어, C표준 라이브러리는 malloc 패키지라고 하는 명시적 할당기를 제공한다. c프로그램은 malloc함수를 호출해서 블록을 할당하며 free함수를 호출해서 블록을 반환한다.
  • 묵시적 할당기 : 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을 것을 요구한다. 묵시적 할당기는 가비지컬렉터(garbage collector)라고 알려져 있으며, 자동으로 사용하지 않는 할당된 블록을 반환 시켜주는 작업을 가비지 컬렉션이라고 한다.

9.9.1 malloc과 free함수

• C표준 라이브러리는 malloc 패키지로 알려진 명시적인 할당기를 제공한다. 프로그램은 malloc 함수를 호출해서 힙으로 부터 블록들을 할당 받는다.
• malloc 함수는 블록 내에 포함 될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size바이트를 갖는 메모리 블록의 포인터를 리턴한다. 실제 구현에서 정렬은 코드가 32비트, 64비트 모드에서 동작하도록 컴파일 되어있는지 여부에 따라 다르다. 32비트 모드에서는 malloc주소가 8의 배수 블록을 리턴하고, 64비트에서는 16의 배수를 리턴한다.
• malloc은 프로그램이 가용한 가상 메모리 보다 더 큰 크기의 메모리 블록을 요청 받으면 널을 리턴하고 errno를 설정한다. malloc은 리턴 하는 메모리를 초기화 하지 않는다. 초기화한 동적 메모리를 원하는 응용들은 calloc을 사용할 수 있는데, 이것은 할당된 메모리를 0으로 초기화하는 calloc함수 주위의 얇은 래퍼 함수이다. 이전에 할당된 블록의 크기를 변경하려는 응용은 realloc 함수를 사용할 수 있다.
• malloc같은 동적 메모리 할당기는 mmap와 munmap 함수를 사용해서 명시적으로 힙 메모리를 할당하거나 반환하며, 또는 sbrk 함수를 사용할 수 있다.
• sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다. 성공한다면 이전의 brk값을 리턴하고, 아니면 -1을 리턴하고 errno를 ENOMEM으로 설정한다. 만일 incr이 0이면 sbrk는 현재의 brk를 리턴한다. sbrk를 음수 incr로 호출하면 합법적이지만, 리턴 값(이전 brk값)이 새로운 힙의 탑을 지나서 abs(incr)바이트를 가리키기에 복잡해진다.
• 프로그램은 할당된 힙 블록을 free 함수를 호출해서 반환한다.
• ptr인자는 malloc, calloc, realloc에서 획득한 할당된 블록을 가져야 한다. 그렇지 않다면 free 동작은 정의되지 않는다. 더 나쁜 것은 아무것도 리턴 하지 않기 때문에 free는 응용에게 뭔가 잘못 되었다는 것을 알릴 수 없다는 점이다. 이것은 혼란스러운 런타임 에러를 유발한다.

9.9.2 왜 동적 메모리 할당인가?

• 프로그램을 실제 실행하기 전에는 자료구조의 크기를 알 수 없는 경우들이 있기 때문이다.
• 배열을 정해진 최대 배열 크기를 갖는 정적 배열로 사용해서 할당하는 것은 종종 나쁜 방법이 된다. 사용자가 더 큰 파일을 읽으려고 한다면, 가능한 유일한 대책은 프로그램을 더 큰 값을 사용해서 다시 컴파일 하는 것이다.
• 더 나은 방법은 n값을 알 수 있을 때, 배열을 런타임에 동적으로 할당하는 것이다. 이 방법으로, 배열의 최대 크기는 가용 한 가상 메모리의 양에 의해서만 제한된다.

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

• 명시적 할당기는 다소 엄격한 제한 내에서 동작해야 한다.
  • 임의의 요청 순서 처리하기 : 응용 프로그램은 각각의 가용 블록이 이전의 할당 요청에 의해 현재 할당된 블록에 대응 되어야 한다는 제한사항을 만족하면서 임의의 순서로 할당과 반환 요청을 할 수 있다. 그래서 할당기는 할당과 반환 요청의 순서에 대해서는 아무 가정도 할 수 없다.
  • 요청에 즉시 응답하기 : 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 한다.
  • 힙만 사용하기 : 확장성을 갖기 위해서는 할당기가 사용하는 비확정성 자료구조들은 힙 자체에만 저장 되어야 한다.
  • 블록 정렬하기(정렬요건) : 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬 해야한다.
  • 할당된 블록을 수정하지 않기 : 할당기는 가용 블록을 조작하거나 변경할 수만 있다. 특히, 일단 블록이 할당되면 이들은 수정하거나 이동하지 않는다. 그래서 할당된 블록을 찹축하는 것 같은 기법들은 허용되지 않는다.
• 이러한 제한 사항들을 가지고 작업하기 위해서 할당기 개발자는 처리량과 메모리 이용도를 최대화 하려는 종종 상충되는 성능 목표를 달성하기 위해 노력한다.
  • 목표 1. 처리량 극대화 하기 : 할당기의 처리량을 최대화 하려고 하며, 이것은 단위 시간 당 완료되는 요청의 수로 정의된다. 일반적으로, 할당과 반환 요청들을 만족 시키기 위한 평균 시간을 최소화해서 처리량을 최대화 한다. 할당 요청의 최악 실행시간이 가용 블록 수에 비례하고, 반환 요청의 실행 시간이 상수인 적당히 좋은 성능의 할당기를 만드는 것은 그리 어렵지 않다.
  • 목표 2. 메모리 이용도를 최대화 하기 : 한 시스템에서 모든 프로세스에 의해 할당된 가상 메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한된다. 할당기가 힙을 얼마나 효율적으로 사용하는지를 규정하는 많은 방법이 있다. 가장 유용한 단위는 최고 이용도(peak utilzation)이다.

9.9.4 단편화

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

9.9.5 구현 이슈

• 가장 간단히 상상할 수 있는 할당기는 힙을 하나의 커다란 바이트의 배열과 이 배열 첫 번째 바이트를 가리키는 포인터 p로 구성할 수 있다. size 바이트를 할당하기 위해서 malloc은 현재 p값을 스택에 저장하고, p를 size 만큼 증가시키고, p의 이전 값을 호출자에게 리턴한다. free는 아무것도 하지 않고 단순히 호출자에게 리턴한다.
• 이 초보적인 할당기는 디자인 공간에서 극단점에 해당한다. 각 malloc과 free가 적은 수의 인스트럭션들을 실행하기 때문에 처리량은 매우 좋다. 그렇지만, 할당기는 블록들을 하나도 재사용하지 않기 때문에 메모리 이용도는 매우 나쁠 것이다. 처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈를 고려해야 한다.
  • 가용 블록 구성 : 어떻게 가용블록을 지속적으로 추적하는가?
  • 배치 : 새롭게 할당된 블록을 배치하기 위한 가용블록은 어떻게 선택하는가?
  • 분할 : 새롭게 할당된 블록을 가용블록에 배치한 후 가용블록의 나머지 부분들로 무엇을 할 것인가?
  • 연결 : 방금 반환한 블록으로 무엇을 할 것인가?

9.9.6 묵시적 가용 리스트

• 모든 실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 가용블록을 구분하는 데이터 구조를 필요로 한다. 대부분의 할당기는 이 정보를 블록 내에 저장한다.
• 한 블록은 1워드 헤더, 데이터, 추가적인 패딩으로 구성한다. 헤더는 블록 크기(헤더와 추가적인 패딩 포함)와 블록이 할당 되었는지 가용상태인지를 인코딩한다. 만일 더블 워드 정렬 제한 조건을 부과한다면 블록 크기는 항상 8의 배수이고, 블록 크기의 하위 3비트는 항상 0이다. 그래서 블록 크기의 상위 29비트만 저장 할 필요가 있으며, 나머지 3비트는 다른 정보를 인코드 하기 위해 남겨둔다. 이 경우 블록이 할당 되었는지 가용 상태인지를 나타내기 위해 최소 중요 비트(할당된 비트)를 사용하고 있다.
• 헤더 다음에는 응용이 malloc을 불렀을 때 요구한 데이터가 따라온다. 데이터 다음에는 사용하지 않은 패딩이 따라올 수 있는데, 이들의 크기는 가변적이다. 패딩을 해야하는 이유는 여러가지가 있다. 외부 단편화를 극복하기 위한 할당기 전략의 일부분일 수도 있다. 또는 정렬 요구사항을 만족하기 위해 필요할 수 있다.
• 이러한 구조를 묵시적 리스트라고 부르는데, 그것은 가용블록이 헤더 내 필드에 의해서 묵시적으로 연결 되기 때문이다. 할당기는 간접적으로 가용블록 전체 집합을 힙 내의 전체 블록을 다니면서 방문 할 수 있다. 어떤 특별히 표시한 마지막 블록이 필요하다는 점에 유의하자.
• 장점
  • 단순성
• 중요한 단점
  • 할당된 블록을 배치하는 것과 같은 가용리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당 된 블록과 가용 블록의 수에 비례한다는 것이다.
• 시스템의 정렬 요구 조건과 할당기의 블록 포맷 선택이 할당기에 최소 블록 크기를 결정한다는 것을 깨닫는 것이 중요하다. 할당되거나 반환된 블록 모두는 이 최소 값보다 작을 수 없다.

9.9.7 할당한 블록의 배치

• 어플리케이션이 k바이트의 블록을 요청할 때, 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색한다. 할당기가 이 검색을 수행하는 방법은 배치 정책에 의해서 결정된다. first fit, next fit, best fit이 주로 사용된다.
• First fit 은 가용 free 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택한다. Next fit은 first fit 과 비슷하지만 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다. Best fit은 모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록을 선택한다.
• First fit의 장점은 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다는 점이다. 단점은 리스트의 앞 부분에 작은 가용 블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어난다는 것이다. Next fit은 first fit에 대한 대안으로, 이전 검색에서 가용 블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안한 방법이다. Next fit은 first fit에 비해서 매우 빠른 속도를 갖는데, 리스트의 앞 부분이 많은 작은 크기의 조각들로 구성되면 특히 더 이런 성향을 보인다. 그렇지만 일부 연구 결과에 의하면 Next fit이 first fit보다 최악의 메모리 이용도를 갖는것으로 밝혀졌다. 연구결과는 best fit이 일반적으로 first fit이나 next fit보다는 더 좋은 메모리 이용도를 갖는다는 것을 밝혀냈다. 그렇지만 묵시적 가용 리스트 같은 단순한 가용 리스트 구성을 사용해서는 best fit을 사용하는 단점은 힙을 완전히 다 검색해야 한다는 점이다.

Algorithm

그리디 알고리즘(Greedy Algorithm)

• 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론
• 각 단계에서 최적이라고 생각되는것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 이다.
• 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 ‘근시값’을 목표로 하고 있다.

그리디 알고리즘 주요속성

1. 탐욕선택속성(Greedy Choice Property)
   1. 각 단계에서 ‘최선의 선택’을 했을때 전체 문제에 대한 최적해를 구할 수 있는 경우
2. 최적부분구조(Optimal Substructure)
   1. 전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 경우
   2. 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 다음 이를 조합해 전체 문제의 최적해를 구하는 것을 의미

단계

1. 문제의 최적해 구조를 결정한다
2. 문제의 구조에 맞게 선택절차를 정의한다. - 선택절차
3. 선택절차에 따라 선택수행
4. 선택된 해가 문제의 조건을 만족하는지 검사한다. - 적절성검사
5. 조건을 만족하지 않으면 해당 해를 제외한다.
6. 모든 선택이 완료되면 해답을 검사한다 - 해답검사
7. 조건을 만족하지 않으면 해답으로 인정되지 않는다.

• 선택절차 (Selection precedure) : 현재상태에서 최적인 선택을 한다
• 적절성 검사(Feasibility check) : 선택한 항목이 문제의 조건을 만족하는지 확인한다
• 해답검사(Solution check) : 모든 선택이 완료, 최종선택이 문제의 조건을 만족 시키는지 확인한다.

동적계획법(DP : Dynamic Programming)

• 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘
• 중복 계산을 줄여서 계산속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다 일반적으로 재귀로 구현되며 메모이제이션(memoization) 기법을 사용하여 중복 계산을 피한다
  • 메모이제이션 - 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복계산을 피함으로서 성능을 향상 시킬 수 있다.

구현단계

1. 문제를 하위 문제로 쪼갠다
2. 하위 문제를 재귀적으로 해결한다
3. 결과를 저장한다(메모이제이션, 테블레이션)
4. 저장된 결과를 이용해 큰 문제를 해결한다.

동적 계획법 조건

1. 최적부분구조(Optimal Substucture)
   1. 전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 경우
   2. 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 다음 이를 조합해 전체 문제의 최적해를 구하는 것을 의미
2. 중복부분문제(Overlapping Subproblems)
   1. 동일한 작은 문제를 반복적으로 해결해야하는 성질

동적계획법 종류

1. 탑 다운(Top-down) : 큰 문제를 해결하기 위해 작은 문제를 호출하는 형식
   1. 장점 : 작은 문제들의 결과값을 저장함으로써 동일한 계산을 반복하지 않아 시간복잡도도 감소한다 - 메모이제이션
   2. 단점 : 스택오버플로우 발생 가능성이 있다 - 재귀 때문에
2. 바텀 업(Bottom-up) : 작은 문제부터 차례대로 해결해 나가는 방식
   1. 장점 : 부분 문제의 해를 저장하고 이를 활용하여 다음 문제를 해결함으로써 시간복잡도도 감소한다. - 테블레이션
   2. 단점 : 초기값을 설정해줘야 하고, 작은 문제들의 결과값을 임시적으로 저장해둘 공간이 필요하다.

최장 공통 부분수열(Longest Common Subsequence)

최장 공통 문자열Longest common substring

• 점화식

if i == 0 or j == 0:
	LCS[i][j] = 0
elif string_A[i] == string_B[j]
	LCS[i][j] = LCS[i-1][j-1] + 1
else:
	LCS[i][j] = 0

동작

1. 문자열 A, 문자열 B의 한 글자씩 비교한다.
2. 두 문자가 다르다면 LCS[i][j]에 0을 표시
3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 + 1
4. 위 과정을 반복한다.

• 이 과정이 성립하는 이유는 공통 문자열은 연속 되어야 하기 때문에 현재 두 문자가 같을 때 두 문자의 앞 글자 까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어가게 될 것이다.

최장 공통 부분수열

• 점화식

if i == 0 or j == 0:
	LCS[i][j] = 0
elif string_A[i] == string_B[j]
	LCS[i][j] = LCS[i-1][j-1] + 1
else:
	LCS[i][j] max(LCS[i-1][j],LCS[i][j-1])

동작

1. 문자열 A, 문자열 B의 한 글자씩 비교한다
2. 두 문자가 다르다면 LCS[i-1][j] 와 LCS[i][j-1] 중 큰 값을 표시한다.
3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 +1 한다
4. 위 과정을 반복한다.

• 부분 수열은 연속된 값이 아니다. 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지된다.

배낭 알고리즘(Knapsack)

• n개의 물건과 배낭이 있을 때 각 물건에는 가치와 무게가 존재한다.
• 또한 각 물건은 1개씩만 있다.
• 배낭에는 담을 수 있는 최대 용량이 존재한다.
• 이러한 조건일 때, 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제이다.

Knapsack problem

• 배낭문제는 물건을 쪼갤 수 있는 Fractional Knapsack problem과 물건을 쪼갤 수 없는 0-1 Knapsack problem으로 나뉜다.

 

고생많았다. 너도 나도 우리도