Study/WIL(Weekly I Learned)

크래프톤 정글 - 4Week 24.02.01 - 24.02.07

에린_1 2024. 2. 8. 17:09

728x90

회고

4주차부터는 c언어가 시작됐고, rb트리 구현이 과제로 주어졌다.

아에 처음은 아니지만 python을 계속 써와서 다시 적응하는데 좀 시간이 걸렸다.

레드블랙 트리를 이해하고 구현하는데 좀 시간을 많이 사용했는데, 구현부분에서는 예림님과 재희님이 큰 도움을 주셔서 편하게 할 수 있었다.

뭔가 뭔가 더 잘할 수 있을 것 같은데 약간약간이 아쉬운 것 같다. 조금만 더 힘내봅시다룽

이제 5주차가 시작하고 설날 연휴가 껴있어서 생각보다 길게 진행이 된다. 쳐지지 않고 이 익스텐션을 잘 유지하면서 공부해보자

CSAPP

7. 링커 Linking

링킹(linking)은 여러개의 코드와 데이터를 모아서 연결하여 메모리에 로드 될 수 있고 실행 될 수 있는 한 개의 파일로 만드는 작업이다. 링킹은 컴파일 시에 수행 할 수 있으며, 이때 소스코드는 머신코드로 번역된다. 프로그램이 메모리에 로드되고, 로더에 의해서 실행될 떄는 로드타임에 응용 프로그램에 의해서 심지어 실행시에도 수행될 수 있다.
링커는 독립적인 컴파일을 가능하게 한다. 큰 규모의 응용 프로그램을 한 개의 소스 파일로 구성하는 대신 별도로 수정할 수 있고, 컴파일 할 수 있는 보다 관리할 만한 규모의 더 작은 모듈들로 나눌 수 있다. 이 모듈 중에 한 개를 변경할 때, 이 파일만을 간단히 재 컴파일하고 다른 파일들을 재 컴파일 할 필요 없이 이 응용을 다시 링크한다.
링킹에 대해 배워야 하는 이유
- 큰 프로그램을 작성하는데 도움이 된다. 다양한 이유로 링커 에러가 발생하는 이런 오류를 이해하지 못하면 혼란스럽고 당혹스러울 것이다.
- 위험한 프로그래밍 에러를 피할 수 있게 된다.
- 어떻게 언어의 변수 규칙이 구현 되었는지 이해하는데 도움이 된다.
- 다른 중요한 시스템 개념을 이해할 수 있게 된다.
- 공유 라이브러리에 대해 이해할 수 있다.

7.1 컴파일러 드라이버

드라이버는 C전처리기 (cpp) 를 돌리고, 이것은 main.c 를 ASCII 중간 파일인 main.i로 번역한다.
드라이버는 C컴파일러 (cc1) 을 돌려서 main.i를 ASCII 어셈블리 언어 파일인 main.s로 번역해준다.
드라이버는 어셈블러 (as) 를 돌려서, main.s를 재배치 가능한 바이너리 목적 파일인 main.o로 번역한다.
드라이버는 sum.o를 생성하기 위해 동일한 과정을 수행한다. 마지막으로, 링커 프로그램 Id를 실행하는데, 이것은 필요한 시스템 목적 파일들과 함께 실행가능 목적파일 prog를 생성하기 위해 main.o 와 sum.o를 생성한다.
쉘은 로더라고 부르는 운영체제 내의 함수를 호출하며, 로더는 실행파일 prog의 코드와 데이터를 메모리로 복사하고, 제어를 프로그램의 시작 부분으로 전환한다.

7.4 재배치 가능 목적파일

전형적인 ELF(Executable and linkable format) 재배치 가능 목적파일의 포맷이다. ELF 헤더는 이 파일을 생성한 워드 크기와 시스템 바이트 순서를 나타내는 16바이트 배열로 시작한다. ELF 헤더의 나머지는 링커가 목적파일 구문분석하고, 해석하도록 하는 정보를 포함하고 있다. 여기에는 ELF 헤더 크기, 목적파일 타입 재배치 가능, 실행 가능, 공유, 머신타입(예, x86-64), 섹션 헤더 테이블의 파일 오프셋, 섹션 헤더 테이블의 크기와 엔트리 수가 들어 있다. 여러가지 섹션들의 위치와 크기는 섹션헤더 테이블로 나타내며 이 테이블은 목적파일의 각 섹션에 대해 고정된 크기의 엔트리를 갖는다.
ELF 헤더와 섹션 헤더 테이블 사이에 섹션 내용이 들어있다.
- .text : 컴파일 된 프로그램의 머신코드
- .rodata : printf 문장의 포맷 스트링, switch문의 점프 테이블과 같은 읽기 - 허용 데이터
- .data : 초기화 된 전역변수 및 정적변수, 지역변수들은 런타임에 스택에 저장되며 data,bss섹션에는 나타나지 않는다.
- .bss : 초기화 되지 않은 전역변수와 정적변수 그리고 0으로 초기화 된 전역변수 및 정적변수, 이 섹션은 목적 파일에 실제 공간을 차지하지는 않는다(단순히 위치를 표시). 목적파일 포맷은 공간 효율성을 위해 초기화 한 공간과 초기화 하지 않은 변수들을 구분한다 : 초기화 하지 않은 변수들은 목적파일에서 실제 디스크 공간을 차지할 필요가 없다. 런타임에 이 변수들은 메모리에 0으로 초기화 되어 할당된다.
- .symtab : 프로그램에서 정의되고 참조되는 전역변수들과 함수에 대한 정보를 가지고 있는 심볼 테이블. 모든 재배치 가능 목적 파일은 .symtab에 심볼 테이블을 가지고 있다. 그러나 컴파일러 내부의 심볼테이블과는 달리, .symtab 심볼 테이블은 지역변수에 대한 엔트리를 가지고 있지 않다.
- .rel.text : 링커가 이 목적파일을 다른 파일들과 연결할 때 수정되어야 하는 .text 섹션 내 위치들의 리스트. 일반적으로 외부함수를 호출하거나 전역변수를 참조하는 인스트럭션들은 모두 수정되어야 한다. 반면에, 지역함수를 호출하는 인스트럭션들은 수정될 필요가 없다. 재배치 정보는 실행 가능 목적파일에는 필요하지 않으며, 사용자가 링커에게 명시적으로 이것을 포함하라고 지시하기 전에는 대개 이 정보는 빠진다는 점에 유의해야 한다.
- .rel.data : 이 모듈에 의해 정의되거나 참조되는 전역변수들에 대한 재배치정보. 일반적으로 초기값이 전역변수 또는 외부에 정의된 함수의 주소인 초기화된 전역변수들 모두는 수정되어야 한다.
- .debug : 프로그램내에서 정의된 지역변수들과 typedef, 프로그램과 최초 C소스 파일에서 정의되고 참조되는 전역변수를 위한 엔트리를 갖는 디버깅 심볼 테이블 컴파일러 드라이버가 - g옵션을 불린 경우 생성된다.
- .line : 최초 C소스 프로그램 .text 섹션 내 머신코드 인스트럭션 내 라인 번호들 간의 매핑. 이것은 컴파일러 드라이버가 -g 옵션으로 호출된 경우에만 생긴다.
- .strtab : .strtab과 .debug 섹션들 내에 있는 심볼 테이블과 섹션 헤더들에 있는 섹션 이름들을 위한 스트링 테이블. 스트링 테이블은 널 문자로 종료된 스트링의 배열이다.

7.4 재배치 가능한 목적파일

컴파일 파이프라인에서 어셈블리 단계의 결과물
C언어 프로젝트의 임시 결과물로 간주, 이후 최종 결과물을 만드는 주 재료다.
링커가 수행하는 과정에서 비롯된다. 링커는 재배치 가능한 목적 파일 여러개를 모아서 더 큰 목적파일을 형성하는데, 하나의 재배치 가능한 목적 파일에서 나타나는 기계 수준의 명령어는 다른 재배치 가능한 목적 파일에서 나온 기계 수준의 명령어 다음에 위치한다.( 즉, 명령어가 이동할 수 있거나 재배치 가능하다는 점을 의미한다)
따라서, 재배치 가능한 목적 파일에서 명령어는 주소를 갖지 않는다. 링크 단계를 거치고 나서 명령어는 주소를 갖는다.

7.9 실행 가능 목적 파일의 로딩

실행 가능 목적파일 prog를 실행하기 위해서, 리눅스 쉘의 명령줄에 그 이름을 다음과 같이 입력할 수 있다.

/prog

prog가 내장 쉘 명령어에 대응되지 않기 때문에 쉘은 prog가 실행 가능한 목적파일이라고 가정되며 쉘은 로더라고 알려진 메모리 상주 운영체제를 호출해서 이 프로그램을 실행한다. 모든 리눅스 프로그램은 execve 함수를 호출해서 로더를 호출할 수 있다.
- execve 함수 : 다른 프로그램을 실행하고 자신을 종료한다.
로더는 디스크로 부터 실행 가능한 목적파일 내의 코드와 데이터를 메모리로 복사하고, 이 프로그램의 첫 번째 인스트럭션, 즉 엔트리 포인트로 점프해서 프로그램을 실행한다. 이와 같이 프로그램을 메모리로 복사하고 실행하는 과정을 로딩이라고 한다.
모든 실행 중인 리눅스 프로그램은 그림과 유사한 런타임 메모리 이미지를 가진다. x86-64 리눅스 스스템에서 코드 세그먼트는 주소 0x400000에서 시작하고, 뒤이어 데이터 세그먼트가 온다. 런타임 heap은 데이터 세그먼트 다음에 따라오고, malloc 라이브러리를 호출해서 위로 성장한다. 이 다음에는 공유 모듈들을 위해 예약된 영역이 존재한다. 사용자 스택은 가장 큰 합법적 사용자 주소(2^48-1) 아래에서 시작해서 더 작은 메모리 주소 방향인 아래로 성장한다. 스택 위의 영역은 운영체제의 메모리 상주 부분인 커널의 코드와 데이터를 위해 예약되어 있다.
단순화 하기 위해서 힙, 데이터, 코드 세그먼트를 붙여서 표시했으며, 스택의 탑을 최대 합법 사용자 주소에 배치했다. 실제로는 .data 세그먼트의 정렬요건으로 인해 코드와 데이터 세그먼트 사이에 공간이 존재한다. 또한, 링커는 런타임 주소를 스택, 공유 라이브러리, 힙 세그먼트에 할당할 때, 주소공간 배치 랜덤화 ASLR를 사용한다.
비록 이들 영역의 위치가 프로그램이 실행될 때 매번 변경될지라도 이들의 상대적인 위치는 동일하다.
로더가 돌아갈 때 위 그림과 유사한 메모리 이미지를 생성한다. 실행 파일 내부의 프로그램 내부프로그램 내부의 프로그램 헤더 테이블에 따라 실행 파일의 덩어리를 코드와 데이터 세그먼트로 복사한다. 다음으로, 로더는 프로그램의 엔트리 포인트로 점프하며, 이것은 항상 _start 함수의 주소가 된다. 이 함수는 시스템 목적파일 ctr1.o에 정의되어 있으며, 모든 C프로그램에서 이 점은 동일하다. _start 함수는 시스템 초기화 함수인 __libc_start_main을 호출하며, 이것은 libc.so 에 정의되어 있다. 이 함수는 실행 환경을 초기화 하고, 사용자 수준의 main 함수를 호출하고, 리턴 값을 처리하며, 필요한 경우 제어권을 커널로 넘겨준다.

8. 예외적인 제어 흐름

프로세서에 전원을 처음 공급하는 시점부터 전원을 끌 때까지 프로그램 카운터는 연속된 값들을 가정한다. 인스트럭션 ik에 대응되는 주소가 ak다 . ak에서 ak+1로의 전환은 제어이동이라고 부른다.
가장 간단한 유형의 제어흐름은 ‘점진적인’ 순서로, 각각 ik와 ik+1이 메모리에 서로 나란히 있는 경우다. 일반적으로 점진적인 흐름에 갑작스럽게 변화가 생기는 경우는 jump, call 리턴 같은 친숙한 프로그램 인스트럭션에 의해 발생한다. 이러한 명령어들은 프로그램 변수에 의한 내부 프로그램 상태 변화에 프로그램이 반응하도록 하기 위하여 반드시 필요한 메커니즘이다.
그러나 시스템들은 또한 배부 프로그램 변수에 의해 표시되지 않으며, 프로그램의 실행과는 반드시 관련되어 있지 않은 시스템의 상태의 변화에도 반응할 수 있어야 한다. 예를들어, 하드웨어 타이머는 규칙적인 간격으로 꺼지며, 시스템은 이것을 반드시 처리 해줘야 한다. 패킷들은 네트워크 어댑터에 도착하고 메모리에 저장되어야 한다. 프로그램은 디스크로부터 데이터를 요청하며, 그 후에 데이터가 준비되었다는 통지를 받을 때 까지 잠든 상태에 들어간다. 자식 프로세스를 생성하는 부모 프로세스는 자신의 자식이 종료할 때 통지를 받아야 한다.
현대의 시스템들은 제어흐름의 갑작스런 변화를 만드는 방법으로 이러한 상황에 반응한다. 일반적으로 이와 같은 급격한 변화를 예외적인 제어흐름(exceptinal control flow : ECF)라고 부른다. 예외적인 제어흐름은 컴퓨터 시스템의 모든 수준에서 발생한다. 예를 들어, 하드웨어 수준에서 하드웨어에 의해서 검출되는 이벤트들을 예외 핸들러로 갑작스런 제어이동을 발생시킨다. 운영체제 커널 수준의 문맥전환을 통해서 사용자 프로세스에서 다른 프로세스로 제어가 이동한다. 응용수준에서 프로세스는 시그널을 수신하는 곳에 있는 시그널 핸들러로 제어를 급격히 이동하는 다른 프로세스로 시그널을 보낼 수 있다. 개별 프로그램은 일반적인 스택 운영을 회피하고 다른 함수 내 임의의 위치로 비지역성 점프를 하는 방법으로 에러에 대응할 수 있다.
프로그래머로서 ECF를 이해하면 좋은 여러 중요한 이유
- 중요한 시스템을 이해하는데 도움이 된다. ECF는 운영체제가 입출력, 프로세스, 가상메모리를 구현하기 위해 사용하는 기본 메커니즘이다.
- 응용들이 어떻게 운영체제와 상호 작용하는지를 이해하는데 도움이 된다. 응용은 트랩 또는 시스템 콜이라고 알려진 ECF에 한 가지 형태를 사용해서 운영체제로 부터 서비스를 요청한다. 기본 시스템 콜을 이해하면 어떻게 이러한 서비스들이 응용에 제공되는지 이해하는데 도움이 된다.
- 재미있는 새로운 응용 프로그램 작성에 도움이 된다. 운영체제는 새로운 프로세스를 만들거나, 프로세스가 종료하기를 기다리거나, 다른 프로세서에게 시스템 내의 예외 이벤트를 알리거나, 이러한 이벤트를 감지하고 반응하는 등의 작업을 위한 강력한 ECF 메커니즘을 응용 프로그램들에 제공한다. 만일 이 ECF 메커니즘들을 이해한다면, 이들을 사용해서 Unix 쉘과 웹서버 같은 흥미로운 프로그램을 작성할 수 있다.
- 동시성을 이해하는데 도움이 된다. ECF는 컴퓨터 시스템에서 동시성을 구현하는 기본 메커니즘이다.
- 소프트웨어적인 예외사항이 어떻게 동작하는 이해하는데 도움이 된다.

8.1 예외상황

예외상황은 부분적으로는 하드웨어와 운영체제에 의해서 구현된 예외적인 제어흐름의 한 가지 형태다.
예외상황은 어떤 프로세서 상태의 변화에 대한 대응으로, 제어흐름의 갑작스런 변화다. 예를 들어, 가상 메모리 페이지 오류, 산술 오버플로우가 발생하거나 어떤 인스트럭션이 divide by zero를 시도하는 경우다.
프로세서가 이벤트가 발생했다는 것을 감지하면, 예외 테이블이라고 하는 점프 테이블을 통해서 이 특정 종류의 이벤트를 처리하기 위해 특별히 설계된 운영체제 서브루틴(예외처리 핸들러)으로 간접 프로시저 콜을 하게 된다.
예외 처리 핸들러가 처리를 끝마치면, 예외상황을 발생 시킨 이벤트의 종류에 따라서 다음과 같은 세 가지 중의 한 가지 일이 발생한다.
1. 핸들러는 제어를 현재 인스트럭션으로 돌려준다.
2. 핸들러는 제어를 다음 인스트럭션으로 돌려준다.
3. 핸들러는 중단된 프로그램을 종료한다.

8.1.1 예외처리

한 시스템 내에서 가능한 예외상황의 종류마다 중복되지 않는 양의 정수를 예외번호로 할당하고 있다. 이 숫자들의 일부는 프로세서 설계자가 부여한 것이다. 나머지 번호는 운영체제 커널(운영체제 메모리가 상주하는 부분) 설계자가 할당한다. 전자의 예로는 divide by zero, 페이지 오류, 메모리 접근 위반, break point, 산술 연산 오버플로우가 포함된다. 후자의 예에는 시스템 콜, 외부 I/O 디바이스로부터의 시그널이 포함된다.
시스템 부팅 시(컴퓨터가 리셋되거나 전원이 공급될 때), 운영체제는 예외테이블이라고 하는 점프테이블을 할당하고 초기화해서 엔트리 k가 예외상황 k에 대한 핸들러의 주소를 갖는다.
런타임 C시스템이 프로그램을 실행하고 있을 때에 프로세서는 이벤트가 발생했다는 것을 감지하고, 대응되는 예외번호 k를 결정한다. 프로세서는 그 후에 예외 테이블의 엔트리 k를 통해서 간접 프로세서가 예외 테이블을 이용해서 해당 예외 핸들러의 주소를 어떻게 만드는지를 보여준다. 예외 번호는 예외 테이블에서 인덱스이며, 이 테이블의 시작 주소는 예외 테이블 베이스 레지스터라는 특별한 CPU 레지스터에 저장되어있다.
예외상황은 프로시저 콜과 유사하지만 일부 중요한 차이점이 있다.
- 프로세서는 프로시저 콜을 사용해서 핸들러로 분기하기 전에 스택에 리턴 주소를 푸시한다. 그렇지만, 예외의 종류에 따라 리턴 주소는 현재 인스트럭션이거나 다음 인스트럭션이 된다.
- 프로세서는 핸들러가 리턴할 때 중단된 프로그램을 다시 시작하기 위해 필요하게 될 스택 상에 추가적인 프로세서 상태를 푸시한다.
- 제어가 사용자 프로그램에서 커널로 전환하고 있을 때, 이 모든 아이템들은 사용자 스택 위가 아니라 커널 스택상에 푸시된다.
- 예외 핸들러는 커널 모드에서 돌아가는데, 이것은 이들이 모든 시스템 자원에 완전히 접근할 수 있는 것을 의미한다.
하드웨어가 예외상황을 촉발해서 남은 작업은 예외 핸들러에 의해 소프트웨어로 진행된다. 핸들러는 예외처리로 인해 발생된 이벤트를 처리한 경우에 따라서는 ‘인터럽트에서 원래 위치로 복귀’ 라는 특별한 인스트럭션을 실행시켜서 인터럽트에 의해서 중단된 프로그램으로 돌아간다. 이 인스트럭션은 인터럽트가 발생되기 전의 원래 프로세서의 제어상태와 데이터 레지스터 상태를 스택으로 부터 팝해서 돌려주고, 만일 예외가 사용자 프로그램을 중단했으면 상태를 사용자 모드로 되돌리고, 최정적으로 제어를 중단되었던 프로그램으로 리턴해준다.

8.1.2 예외의 종류

예외상황은 네 가지 종류로 구분 할 수 있다.
- 인터럽트
- 트랩
- 오류 Fault
- 중단 abort

인터럽트

인터럽트는 프로세서 외부에 있는 입출력 디바이스로 부터 시그널의 결과로 비동기적으로 발생한다. 하드웨어 인터럽트는 비동기적이며, 즉 특정 인스트럭션을 실행해서 발생하는 것이 아니라는 의미에서 그렇다. 하드웨어 인터럽트를 위한 예외 핸들러는 종종 인터럽트 핸들러 라고 부른다.
네트워크 어댑터, 디스크 컨트롤러, 타이머 칩 같은 입출력 디바이스들은 프로세서 칩의 핀에 시그널을 보내서 인터럽트를 발생시키고, 인터럽트를 발생시킨 디바이스를 식별하는 예외번호를 시스템 버스에 보낸다.
현재의 인스트럭션이 실행을 완료한 후에, 프로세서는 인터럽트 핀이 high로 올라갔다는 것을 발견하고 시스템 버스에서 예외번호를 읽으며, 적절한 인터럽트 핸들러를 호출한다. 핸들러가 리턴할 때, 제어를 다음 인스트럭션으로 돌려준다. 그 효과는 프로그램이 인터럽트가 마치 발생하지 않았던 것처럼 계속해서 실행되는 것이다. 나머지 예외의 종류틀은 지금의 인스트럭션을 실행한 결과로 동기적으로 일어난다. 우리는 이것을 오류 인스트럭션이라고 부른다.

트랩과 시스템 콜

트랩은 의도적인 예외상황으로, 어떤 인스트럭션을 실행한 결과로 발생한다. 인터럽트 핸들러와 마찬가지로 트랩 핸들러는 제어를 다음 인스트럭션으로 리턴한다. 트랩의 가장 중요한 사용은 시스템 콜이라고 알려진 사용자 프로그램과 커널 사이의 프로시저와 유사한 인터페이스를 제공하는 것이다.
사용자 프로그램은 파일을 읽거나(read), 새로운 프로세스를 만들거나(fork), 새 프로그램을 로드하고(execve), 현재 프로세스를 종료하는 등의 서비스를 종종 커널에게 요청할 필요가 있다. 이러한 커널 서비스의 제한된 접근을 하기 위해서 프로세서는 특별한 ‘n’ 인스트럭션을 제공하며 이들은 사용자 프로그램이 서비스 n을 요청하고자 할 때 사용자 프로그램이 사용할 수 있는 인스트럭션이다. syscall 인스트럭션을 실행하면 트랩 인자들을 해독하고 적절한 커널 루틴을 호출하는 예외 핸들러로 가게 한다. 프로그래머의 관점에서는 함수호출과 동일하다.
그렇지만 실제 구현은 매우 다르다. 보통의 함수는 사용자 모드에서 돌아가며, 이 때문에 이들이 실행할 수 있는 인스트럭션은 제한적이며, 이들은 호출하는 함수와 동일한 스택을 사용한다. 시스템 콜은 커널 모드에서 돌아가며, 이로 인해 커널 내에서 정의된 스택에 접근하며, 특권을 가진 인스트럭션을 실행할 수 있도록 해준다.

오류(fault error와 다르다)

오류는 핸들러가 정정할 수 있을 가능성이 있는 에러조건으로 부터 발생한다. 오류가 발생하며 프로세서는 제어를 오류 핸들러로 이동해준다. 만일 핸들러가 에러조건을 정정할 수 있다면, 제어를 오류를 발생시킨 인스트럭션으로 돌려주어서 거기서부터 재실행한다. 그렇지 않다면 핸들러는 커널 내부의 abort 루틴으로 리턴해서 오류를 발생시킨 응용 프로그램을 종료한다.
오류의 고전적인 예는 페이지 오류 예외로, 이것은 인스트럭션이 가상메모리 테이블을 참조했을 때 대응되는 실제 메모리 page가 존재하지 않는 상황이며, 따라서 디스크에서 가져와야 할 때 발생한다. 페이지는 가상 메모리의 연속적인 블록이다.(대개 4kb). 페이지 오류 핸들러는 디스크에서 적절한 페이지를 로드해서 오류를 발생시킨 인스트럭션으로 제어를 넘겨준다. 이 인스트럭션이 다시 실행될 때 적절한 페이지는 메모리에 있게 되므로 인스트럭션은 오류를 발생시키지 않고 완료할 때까지 동작할 수 있다.

중단

중단은 대개 DRAM이나 DRAM이 고장날 때 발생하는 페리티 에러와 하드웨어 같은 복구할 수 없는 치명적인 에러에서 발생한다. 중단 핸들러는 절대 응용 프로그램으로 제어를 리턴하지 않는다. 핸들러는 제어를 응용 프로그램을 종료하는 중단 루틴으로 넘겨준다.

8.13 리눅스/x86-64 시스템에서의 예외상황

리눅스 / x86-64 오류와 중단

나누기 에러 : 나누기 에러(예외번호 0)는 응용이 0으로 나누려고 할 때, 또는 나눗셈 인스트럭션의 결과가 목적지 오퍼랜드에 비해 너무 큰 경우 발생한다. unix는 나누기 에러에서 복구하려는 시도를 하지 않으며, 대신 시스템을 중단하는 것을 선택한다. 리눅스 쉘은 대개 나누기 에러를 ‘부동 소수 예외’로 보고한다.
일반 보호 오류 : 악명 높은 일반 보호 오류(예외번호 13)는 여러가지 이유로 발생하며, 대개 프로그램이 가상 메모리의 정의되지않은 영역을 참조하거나 프로그램이 read-only 텍스트 세그먼트에 쓰려고 하기 때문이다. 리눅스는 이 오류에서 복구하려는 시도를 하지 않는다. 리눅스 쉘은 대개 ‘세그먼트 오류’같은 일반적인 텍스트로 오류를 알려준다.
페이지 오류 : 페이지 오류(예외번호 14) 는 오류 발생 인스트럭션이 재시작하는 예외의 예다. 핸들러는 필요한 디스크의 가상 메모리의 해당 페이지를 물리 메모리 페이지로 매핑하고 그 후 오류 인스트럭션을 다시 시작한다.
머신체크 : 머신체크(예외번호 18)는 오류 인스트럭션을 실행하는 동안에 검출된 치명적적인 하드웨어의 결과로 발생한다. 머신체크 핸들러는 절대로 제어를 응용 프로그램에게 돌려주지 않는다.

리눅스/x86-64 시스템 콜

리눅스는 파일을 읽거나 쓸 때, 또는 새로운 프로세스를 만들 때 응용프로그램이 사용할 수 있는 수 백개의 시스템 콜을 제공한다. 시스템 콜은 커널 점프 테이블의 오프셋에 대응되는 유일한 정수를 갖는다.( 이 점프 테이블은 예외 테이블과는 다르다는 점에 유의하자)
표준 C라이브러리는 대부분 시스템 콜에 대해서 편리한 래퍼(wrapper) 함수들을 제공한다. 래퍼함수는 인자들을 패키징하고, 커널을 적잘한 시스템 콜 인스트럭션으로 트랩을 걸고, 호출하는 프로그램으로 시스템 콜의 리턴 상태를 전달한다.
x86-64 시스템에서 리눅스 시스템을 직접 호출하기 위해서 이 인스트럭션을 어떯게 사용할 수 있는지 배우는 것은 상당히 흥미롭다. 리눅스 시스템 콜에 전달되는 모든 인자들은 스택보다는 범용 레지스터를 통해서 이루어진다. 관습적으로, 레지스터 %rax는 시스템 콜 번호를 보관하며, %rdi, %rsi, %rdx, %r10, %r8, %r9에 최대 여섯 개의 인자들을 보관할 수 있다. 시스템 콜에서 리턴될 때, 레지스터 %rcx, %r11은 값들이 지워지고, %rax는 리턴 값을 보관한다. -4,095에서 -1 사이의 음수 리턴 값은 음수의 errno에 대응하는 에러를 나타낸다.

8.5 시그널

리눅스 시그널이라고알려진 상위 수준의 소프트웨어 형태의 예외적 제어 흐름. 이 시그널은 프로세스와 커널이 다른 프로세스를 중단하도록 한다.
시그널은 작은 메세지 형태로, 프로세스에게 시스템 내에 어떤 종류의 이벤트가 일어났다는 것을 알려준다.
각 시그널 타입은 특정 종류의 시스템 이벤트에 대응된다. 하위 수준 하드웨어 예외는커널의 예외 핸들러에 의해 처리되며, 정상적으로는 사용자 프로세스에서는 볼 수 없다. 시그널은 이러한 예외들을 사용자 프로세스에 노출해주는 메커니즘을 제공한다.

8.5.1 시그널 용어

시그널을 목적지 프로세스로 전달하는 것은 두 단계로 이루어진다.
- 시그널 보내기 : 커널은 목적지 프로세스의 컨텍스트 내에 있는 일부 상태를 갱신해서 시그널을 목적지 프로세스로 보낸다(배달한다). 시그널은 다음 두 가지 이유 중의 하나로 배달된다.
  1. 커널이 0으로 나누거나 자식 프로세스의 종료 같은 시스템 이벤트를 감지한다.
  2. 어떤 프로세스가 커널에 명시적으로 시그널을 목적지 프로세스에 보낼 것을 요구하기 위해서 kill 함수를 호출하였다.
- 시그널 받기 : 목적지 프로세스는 배달된 신호에 대해서 커널이 어떤 방식으로 반응 해야 할 때 목적지 프로세스는 시그널을 받는다. 프로세서는 시그널 핸들러라고 부르는 사용자 수준 함수를 실행해서 시그널을 무시, 종료, 획득할 수 있다.
보내졌지만 아직 받지 않은 시그널은 펜딩(pending) 시그널 이라고 부른다. 시간 상으로 어떤 시점에서, 특정 타입에 대해 최대 한 개의 펜딩 시그널이 존재할 수 있다. 만일 어떤 프로세스가 타입의 k의 펜딩 시그널을 가지고 있다면 이 프로세스로 다음에 발생하는 k타입의 시그널은 큐에 들어가지 않는다.(이들은 단순하게 버려진다) 프로세스는 선택적으로 어떤 시그널의 수신을 블록할 수 있다. 어떤 시그널이 블록될 때 배달은 될 수 있지만 펜딩 시그널은 이 프로세스가 시그널의 블록을 끌 때까지는 수신되지 않는다.
펜딩 시그널은 최대 한 번만 수신된다. 각 프로세스에 대해, 커널은 pending 비트 벡터 내에 펜딩하고 있는 시그널의 집합을 관리하며, blocked 비트 벡터내에서 블록된 시그널 집합을 관리한다. 커널은 pending 내에 비트 k를 타입k의 시그널이 배달 될 때 마다 설정하며, 시그널 타입 k가 수신될 때 마다 pending의 비트 k를 0으로 만든다.

8.5.2 시그널 보내기

프로세스 그룹

모든 프로세스는 정확히 한 개의 프로세스 그룹에 속하며, 이것은 양수 process group ID로 식별한다. getpgrp 함수는 현재 프로세스의 프로세스 그룹 ID를 리턴한다.
기본적으로, 자식 프로세스는 자신의 부모와 동일한 프로세스 그룹에 속한다. 프로세스는 자신의 프로세스 그룹 또는 다른 프로세스의 그룹을 setpgid 함수를 사용해 변경할 수 있다.

키보드에서 시그널 보내기

unix 쉘은 작업의 추상화를 사용해서 한 개의 명령줄을 해석한 결과로 만들어진 프로세스에 반영한다. 시간상의 어떤 시점에서도 최대 한 개의 포그라운드 작업과 0또는 그 이상의 백그라운드 작업이 존재한다.
쉘은 각 작업마다 별도의 프로세스 그룹을 만든다. 일반적으로 프로세스 그룹 ID는 작업 내에 부모 프로세스 중 하나에서 가져온다.

8.5.3 시그널의 수신

커널이 프로세스 P를 커널 모드에서 사용자 모드(시스템 콜에서 리턴하거나 문맥전환을 끝 마치는것과 같은)로 전환할 때, 커널은 프로세스 P에 대한 블록 되지않은 펜딩 시그널(pending & ~ blocked) 의 집합을 체크한다. 만일 이 집합이 비어있다면(대개의 경우), 커널은 제어를 p의 논리 제어 흐름 내의 다음 인스트럭션으로 전달한다.
비어있지 않다면, 커널을 집합 내 어떤 시그널 k를 선택해서(대개 가장 작은k) p가 시그널 k 를 수신하도록 한다. 시그널을 수신하면 프로세스는 어떤 동작을 개시한다. 일단 프로세스가 이 동작을 완료하면, 제어는 p의 논리 제어 흐름내의 다음 인스트럭션으로 돌아간다. 각 시그널 타입은 사전 정의된 기본 동작을 가지며, 이들은 다음 동작 중의 하나이다.
- 프로세스가 종료한다.
- 프로세스는 종료하고 코어를 덤프한다
- 프로세스는 SIGCONT 시그널에 의해 재시작 될 때 까지 정지한다.(지연한다)
- 프로세스는 시그널을 무시한다.
프로세스는 시그널과 연결된 기본 동작을 signal 함수를 사용해서 수정할 수 있다.
어떤 프로세스가 타입 k의 시그널을 잡을 때, 시그널 k를 위해 설치된 핸들러는 k에 설정된 한 개의 정수 인자를 사용해서 호출한다. 이 인자는 동일한 핸들러 함수가 서로 다른 종류의 시그널을 잡을 수 있도록 한다.
핸들러가 return 문장을 실행할 때, 제어는(대개) 프로세스가 시그널의 수신으로 중단되었던 제어 흐름 내의 인스트럭션으로 다시 전달된다. 여기서 ‘대개’라고 했는데, 일부 시스템의 경우 중단된 시스템 콜들이 에러가 발생하면 즉시 리턴하기 때문이다.

8.5.4 시그널 블록하기와 블록 해제하기

리눅스는 시그널을 블록하기 위해 묵시적이고 명시적인 방법을 제공한다.
- 묵시적 블록 방법 : 기본적으로 커널은 핸들러에 의해 처리되고 있는 유형의 모든 대기 시그널의 처리를 막는다.
- 명시적 블록 방법 : 응용 프로그램들은 sigprocmask 함수와 이들의 도움 함수를 이용해서 시그널들을 명시적으로 블록하거나 블록 해제할 수 있다.

8.5.5 시그널 핸들러 작성하기

핸들러는 이해하기 어렵게 만드는 몇 가지 특성을 가진다.
1. 핸들러는 메인 프로그램과 동시적으로 돌아가고, 같은 전역변수를 공유하며, 그래서 메인 프로그램과 다른 핸들러들과 뒤섞일 수 있다.
2. 어떻게 그리고 언제 시그널들이 수신 될 수 있는지는 종종 직관적이지 않다.
3. 다른 시스템들은 다른 시그널 처리 방식을 갖는다.

안전한 시그널 처리

G0 : 핸들러는 가능한 간단하게 유지하라.
G1 : 핸들러에서 비동시성-시그널 안전한 함수만 호출하라
G2 : errno를 저장하고 복원하라
G3 : 모든 시그널을 블록 시켜서 공유된 전역 자료구조들로의 접근을 보호하라
G4 : 전역변수들을 volatile로 선언하라
G5 : sig_atomic_t 로 플래그들을 선언하라.

9.9.8 가용블록의 분할

할당기가 크기가 맞는 가용 블록을 찾은 후에 가용 블록의 어느 정도를 할당할지에 대해 정책적 결정을 내려야 한다. 한 가지 옵션은 이 가용 블록 전체를 사용하는 것이다. 비록 간단하고 빠르지만, 큰 단점은 내부 단편화가 생긴하는 것이다. 만일 배치 정책으로 인해 크기가 잘 맞는다면, 일부 추가적인 내부 단편화는 수용할 수도 있다.
그렇지만 크기가 잘 안맞는다면, 할당기는 대개 가용 블록을 두 부분으로 나누게 된다. 첫 번째 부분은 할당한 블록이 되고, 새로운 가용 블록이 된다.

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

할당기가 요청한 블록을 찾을 수 없다면, 메모리에서 물리적으로 인접한 가용 블록들을 합쳐서(연결해서) 더 큰 가용 블록을 만들어 본다. 이렇게 해도 충분히 큰 블록이 만들어지지 않거나 가용 블록이 이미 최대로 연결 되었다면, 할당기는 커널에게 sork 함수를 호출해서 추가적인 힙 메모리를 요청한다. 할당기는 추가 메모리를 한 개의 더 큰 가용 블록으로 변환하고, 이블록을 가용 리스트에 삽입한 후에 요청한 블록을 이 새로운 가용 블록에 배치한다.

9.9.10 가용 블록 연결하기

할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록이 있을 수 있다. 이러한 인접 가용 블록들은 오류 단편화(false fragmentation)라는 현상을 유발할 수 있으며, 이때는 작고 사용할 수 없는 가용 블록으로 쪼개진 많은 가용 메모리들이 존재한다.
오류 단편화를 극복하기 위해 실용적인 할당기라면 연결(coalesing)이라는 과정으로 인접 가용 블록들을 통합해야 한다. 이 과정에서는 언제 연결을 수행할지에 관한 중요한 정책 결정을 해야한다. 할당기는 블록이 반환 될 떄마다 인접 블록을 통합해서 즉시 연결을 선택할 수 있다. 또는 일정 시간 후 가용 블록들을 연결하기 위해 기다리는 지연 연결을 선택할 수도 있다.
즉시 연결은 간단하며 상수 시간내에 수행할 수 있지만, 일부 요청 패턴에 대해서는 블록이 연속적으로 연결되고 잠시 후에 분할 되는 쓰래싱의 형태를 유발할 수 있다. 할당기에 대한 논의에서 즉시 연결을 가정하겠지만, 빠른 할당기들은 종종 지연 연결의 형태를 선택한다는 것을 알아야한다.

9.9.11 경계태그로 연결하기

현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이것은 다음 블록이 가용한지 결정하기 위해 체크 될 수 있다. 그렇다면, 그 크기는 단순히 현재 헤더의 크기에 더해지고, 블록은 상수 시간 내에 연결할 수 있다.
이전 블록 연결의 경우 헤더를 상용하는 묵시적 가용리스트가 주어진다면, 유일한 옵션은 현재 블록에 도달할 때 까지 전체 리스트를 검색해서 이전 블록의 위치를 기억하는 것이다. 묵시적 가용 리스트를 사용하면, 이것은 각각의 free 호출이 힙의 크기에 비례하는 시간을 소모할 것이라는 걸 의미한다. 보다 복잡한 가용 리스트의 구조를 사용하더라도 이 검색 시간은 상수가 될 수 없다.
knuth의 경계 태그 : 상수 시간 이전 블록을 연결하게 해준다. 각 블록의 끝 부분에 풋터(footer 경계태그) 를 추가하는 것으로, 풋터는 헤더를 복사한 것이다. 만일 각 블록이 이와 같은 풋터를 포함하게 되면, 할당기는 시작 위치와 이전 블록의 상태를 자신의 풋터를 조사해서 결정할 수 있게 되며, 이것은 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치한다.
경계 태그 아이디어는 여러가지 유형의 할당기와 가용 리스트 구성에도 일반화 될 수 있는 간단하고 우아한 개념이다. 그렇지만 여기에도 잠재적인 단점이 존재한다. 각 블록이 헤더와 풋터를 유지해야 하므로 만일 응용이 많은 작은 크기의 블록을 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다.
현재 블록의 추가적인 하위 비트들 중의 하나에 이전 블록의 할당/가용 비트를 저장하려고 한다면, 할당된 블록들은 풋터가 필요 없어지고, 이 추가적인 공간을 데이터를 위해 사용할 수 있었을 것이다. 그렇지만 가용 블록은 여전히 풋터를 필요로 한다는 점에 유의해야 한다.

9.9.13 명시적 가용 리스트

블록 할당 시간이 전체 힙 블록 수에 비례하기 때문에 묵시적 가용 리스트는 범용 할당기에는 적합하지 않다. 더 좋은 방법은 가용 블록들을 일종의 명시적 자료구조로 구성하는 것이다. 정의에 의해 가용 블록의 본체는 프로그램에서 필요하지 않기 때문에 이 자료구조를 구현하는 포인터들은 가용 블록의 본체 내에 저장 될 수 있다. 힙은 각 가용 블록내에 pred(predecessor)와 succ(successor) 포인터를 포함하는 이중 연결 가용 리스트로 구성될 수 있다.
묵시적 가용 리스트 대신에 이중 연결 리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서 가용 블록의 수에 비례하는 것으로 줄일 수 있다. 그렇지만 블록을 반환하는 시간은 가용 리스트 내에서 블록을 정렬하는 정책을 어떤 것을 선택하는 가에 따라 비례하거나 상수시간을 가질 수 있다.
한 가지 접근법은 리스트를 새롭게 반환한 블록들을 리스트의 시작 부분에 삽입해서 후입선출(LIFO)순으로 유지하는 것이다. LIFO 순사와 first fit 배치 정책을 사용하면, 할당기는 대부분의 최초에 사용된 블록들을 먼저 조사한다. 이 경우 블록의 반환은 상수 시간에 수행된다. 만일 경계태그를 사용하면 연결도 상수 시간에 수행할 수 있다.
또 다른 접근법은 리스트를 주소 순으로 관리하는 것으로, 리스트 내 각 블록의 주소가 다음 블록의 주소보다 작다. 이 경우 블록의 반환은 적당한 선행 블록을 찾는데 선형 검색시간을 필요로 한다.
명시적 리스트의 단점은 일반적으로 가용 블록들이 충분히 커서 모든 필요한 포인터 뿐만 아니라 헤더, 추가적으로 풋터까지 포함해야 한다는 점이다. 그 결과 최소 블록 크기가 커지고 잠재적인 내부 단편화 가능성까지 증가한다.

9.9.14 분리 가용 리스트

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

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이 자주 호출되면, 힙은 점차적으로 가비지로 가득 차게 되고, 최악의 경우 전체 가상 주소공간을 소모하게 된다. 메모리 누수는 특히 데몬, 서버와 같이 종료 되지 않는 프로그램들의 경우에 심각하다.

C & C++

배열
- 자료형 변수이름 [원소개수]
const
- 상수, 그 값이 주어지고 그 값이 영원히 바뀌지 않는다.
포인터
- 메모리 상에 위치한 특정 데이터의 (시작) 주소값을 보관하는 변수
- 간접접근 할 때 사용한다. 프로그램은 스택과 코드 섹션에는 직접 접근이 가능하다. 힙에는 직접 엑세스 하지 않는데, 프로그램의 정책은 힙에 직접적으로 엑세스하지 않는 것이다.
- 포인터를 사용하는 이유
  - Accessing Heap
  - Accessing Resource
  - Parameter Passing
- & 연산자 피연산자의 주소값을 불러온다.
- - 연산자 피연산자의 주소에 접근한다.
- 상수 포인터
  - const int* : 값을 상수화
  - int* const : 주소를 상수화
- 포인터의 덧셈 → 배열 인덱스
  - []연산자 → a[3] ⇒ *(a+3)
- 포인터 배열
  - 2차원 배열은 메모리에 선형으로 존재한다.

가상화

가상화는 서버, 스토리지, 네트워크 및 기타 물리적 시스템에 대한 가상표현을 생성하는데 사용할 수 있는 기술이다.
가상 소프트웨어는 물리적 하드웨어 기능을 모방하여 하나의 물리적 머신에서 여러 가상 시스템을 동시에 실행한다. 컴퓨터가 하드웨어 리소스를 디지털로 분리된 여러 환경과 공유할 수 있도록 하는 프로세스다. 각 가상화된 환경의 메모리, 처리능력, 스토리지등 할당된 리소스 내에서 실행된다.
가상화의 이점
- 효율적인 리소스 사용
- 자동화된 IT 관리
- 신속한 재해복구

C++ 참조(reference)

같은 메모리의 변수에 대한 또 다른 이름
왜 다른 이름이 필요한가.
- 매개변수 전달에 유용하다
- 작은 함수를 작성할 때 포인터가 아닌 레퍼런스를 사용한다.

구조체 포인터

구조체 포인터는 멤버가 아니라 포인터다. 멤버를 가지는 것이 아니라 주소를 가지고 접근한다.
(*p).length = 20;
p→length = 20;
포인터를 이용 구조체에 엑세스 하는 메서드. → 화살표 사용
call by value로 접근할 때는 .연산자
call by address로 접근할 때는 → 연산자

함수(function)

특정 작업을 수행하는 코드의 집합, 큰일을 나눠 수행할 수도 있다.
프로그램을 작은 작업으로 쪼개서 작은 작업에 집중하고 큰 것을 완성
프로그래밍의 생산성과 재사용성을 늘려준다.

int add(int a, int b) // 함수의 프로토타입, 함수의 헤더, 함수의 선언이다.
{
 ---- // 함수 기능의 정의, 기능의 설명
}

함수에서 쓰는 매개변수 : formal parameter
main() 함수에서 초기화하고 함수에 전달되는 매개변수 : actual parameter
한 함수는 다른 함수에 접근할 수 없다.

매개변수 넘기기

call by value
- formal parameter 변화가 actual parameter의 변화에 영향을 주지 않는다.
- actual parameter를 수행 할 필요가 없는 경우 call by value를 쓴다.
call by address
- actual parameter 주소가 formal parameter로 전달되고 formal parameter 형식은 포인터여야 한다.
- 포인터를 이용한다.
call by reference(C++에서만 지원)
- call by value의 formal parameter에 & 연산자를 추가한다.
- 참조는 메모리를 필요로 하지 않는다. 추가 메모리가 필요없다.
- 지역변수는 다른 함수에서 직접 접근할 수 없다. → 간접적으로만 가능하다. call by reference의 경우 직접 접근을 했는데 이것이 어떻게 가능한가 하면 메모리 내부를 보면 함수가 별도 호출을 하지 않고, main 함수 스택프레임 내에서 실행이 되었다. 별개의 함수가 아니라 main 함수의 일부가 됐다.
- reference로 호출하면 해당 함수 코드는 함수 호출 장소에 복사된다.
- 간단한 함수에서는 사용하고 복잡한 논리를 가지는 큰 함수에는 조심해서 사용해야한다.

선언(declaration)과 정의(definition)

프로그래밍에서 선언(declaration)과 정의(definition)는 명백히 다른 역할을 하지만 혼동하여 사용하기 쉽다.
선언과 정의의 가장 큰 차이는 ‘메모리를 할당하는가’ 이다.
메모를 할당하지 않고, 대상의 이름만 알려준다면 선언이고 대상의 메모리가 할당된다면 그것은 정의다.

선언

컴파일러가 참조할 식별자(identifier)와 이름을 알립니다.
- 식별자란 변수의 타입과 함수의 인수목록을 뜻하며 이름은 변수, 함수, 클래스의 이름, 네임 스페이스를 뜻합니다.

정의

정의는 식별자와 이름으로부터 코드를 생성하여, 함수를 호출되거나 변수를 사용할 때 생성된 코드를 참조한다.
정의는 고유 사양으로 프로그램에는 정의가 하나만 있어야 한다. 같은 식별자와 이름의 정의가 두 개 이상이라면 컴파일 에러가 발생한다. 반면, 선언만 하고 정의를 하지 않은 경우에는 링커 단계에서 참조할 코드가 없기 때문에 링커 에러가 발생하는데 예외 사항 아래의 경우 정의가 필요 없다.
- 함수가 선언만 있고, 정의가 없지만 함수를 호출하거나 함수의 주소를 참조하는 일이 없음
- 정의를 알 필요가 없는 방식으로만 사용됨(전방선언)

전방 선언(forward declaration)

함수나, 구조체, 열거자, 공용자, 외부(extern) 변수 등을 실제 구현(implementation) 시점보다 앞서서 선언(declare)만 하는 것을 말한다.
물론, 구현부와 선언부의 서명(signature)은 일치해야 한다.
서로를 호출하는 함수, 외부(extern) 변수, plmple기법 등에서 사용된다.
헤더와 소스 파일로 구현부, 선언부를 분리하는 행위는 기본적으로 모두 전방 선언에 속한다.

static, extern 변수

static의 역할 : 현재 파일 내에서의 지역변수로 바뀐다. 즉, 현재 파일 내에서만 사용 가능한 변수가 된다.
extern의 역할 : 다른 파일에서 이미 이름이 같은 전역변수가 선언이 되었다는 의미. 즉, 다른 파일간의 변수를 공유하고 있다는 뜻이다.
static이 붙어있는 변수
- 현재 파일 내에서만 존재하는 파일의 지역변수 취급을 받기 때문에 이름이 같더라도 서로 다른 파일에서 각각 다른 변수로 취급이 된다.
- 따라서 static 변수를 통해 혹시 모를 전역변수의 이름이 같게 되는 문제를 조금이나마 완화할 수있다.
- 초기화를 생략하면 0으로 자동 초기화된다.
- 외부 파일에서 접근이 불가능하다.
extern이 붙어있는 변수
- 정말 global 변수라는 뜻으로 사용되며 다른 파일에 같은 이름의 전역변수가 존재한다는 것이기 때문에 이 정보를 컴파일러에게 전달하고 main.o 와 header.o 링킹 해준다.
- 진정한 global 변수라고 볼 수 있다.
- extern 키워드는 전역변수가 외부에 있다는 것을 표시만 할 뿐이고 선언을 하지는 않는다. 따라서 어디엔가 정의되어 있지 않으면 링크에러가 발생하게 된다.
- extern은 다른 파일의 함수나 변수를 가져오는 것 이외에도 현재 파일내에서도 작동이 가능하다.

enum

열거형은 정수형 상수에 이름을 붙여서 코드를 이해하기 쉽게 해준다.

enum 열거형이름 {
    값1 = 초깃값,
    값2,
    값3
};

전처리 명령

#include
- #include <파일명> : C언어 기본 라이브러리를 포함할 때 사용
- #include “파일명” : 우리가 임의로 만든 파일을 포함할 때 사
- 파일을 포함한다.
#define
- 매크로명을 정의해서 복잡한 상수나 문장을 의미있는 단어로 사용할 수 있도록 한다.
- #define 매그로명 확장문자열
#if, else, elif, ifdef, ifndef, endif
- 조건부 컴파일은 프로그램 코드를 조건에 따라 선택적으로 컴파일 할 수 있도록 전처리 단계에서 걸러준다.
- 조건식에 괄호가 필요 없으며 반드시 #endif로 끝을 표시해 준다.
- 헤더 파일이 겹치는 것을 막기 위한 일종의 매크로이다.
#error
- 소스 라인에 직접 에러 메세지를 출력한다. 전처리기가 #error문을 만나면 그 즉시 컴파일을 중단하고 다음과 같은 에러 메시지를 출력한다.
#pragma
- 컴파일 옵션의 지정. 컴파일러 작성자에 의해서 정의된 다양한 명령을 컴파일러에게 제공하기 위해 사용되는 지시어이다. 컴파일러의 여러 가지 옵션을 명령행에서가 아닌 코드에서 직접 설정한다. #pragma는 함수의 바로 앞에 오며 그 함수에만 영향을 준다.

반복자(iterator)

어떤 컨테이너(자료구조)에 접근하든 동일한 방법으로 접근하기 위해서 제공되는 객체.
자료구조마다 서로 다른 방법으로 내부의 요소들에 접근을 하는데 반복자를 사용하게 되면 컨테이너의 내부 구조를 몰라도 쉽게 컨테이너를 순회하는게 가능해지며, 서로 다른 컨테이너에 통일된 인터페이스로 접근이 가능하다.

비트 연산자

비트 연산자는 비트(bit) 단위로 논리 연산을 할 때 사용하는 연산자이다.
또한, 비트 단위로 전체 비트를 왼쪽이나 오른쪽으로 이동시킬 때도 사용한다.

비트 연산자 설명

&	대응되는 비트가 모두 1이면 1을 반환함. (비트 AND 연산)

^	대응되는 비트가 서로 다르면 1을 반환함. (비트 XOR 연산)
~	비트를 1이면 0으로, 0이면 1로 반전시킴. (비트 NOT 연산)
<<	지정한 수만큼 비트들을 전부 왼쪽으로 이동시킴. (left shift 연산)
>>	부호를 유지하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴. (right shift 연산)

가변인자

인자의 개수가 정해지지 않았을 때 사용하는 것이 바로 가변인자(variable argument)이다.
함수에서 가변인자를 선언하기 위해서는 …을 이용한다.
함수에 가변인자를 정의하여 그 가변인자를 사용하기 위해서는 라이브러리를 추가해 주어야한다.
- <stdarg.h> : 가변인자들을 제어하기 위한 라이브러리 헤더 파일
- va_list : 가변인자 목록으로 가변인자의 메모리 주소를 저장하는 포인터
- va_start : 가변인자를 가져올 수 있도록 설정
- va_arg : 가변인자 포인터에서 특정 자료형의 크기만큼 값을 꺼낸다.
- va_end : 가변인자 처리가 끝났을 때 포인터를 NULL로 초기화해준다.
가변인자를 사용할 때 주의사항
- 가변인수를 사용하기 위해서는 가변인수의 갯수를 알 수 있어야 하기 때문에 반드시 하나 이상의 고정인자가 필요하다.
  - 가변인수의 크기를 알아야만 함수에서 정확한 제어가 가능하기 때문이다.
  - 고정인자를 통해 함수 내에서 크기를 유추하게 구현 또한 가능하다.
- 가변인수는 항상 함수의 가장 뒤에 호출이 돼야 한다.
  - 당연히 고정인자와 가변인자를 구분하기 위해서는 가변인자는 뒤에 있어야 한다.
- 가변인수의 자료형을 명확하게 알아야 한다.

Algorithm

AVL Tree

자가균형 이진 탐색트리의 한 유형
각 노드의 서브트리 높이 차이가 최대 1을 유지하도록 스스로 균형을 유지하는 트리
이 서브트리의 높이 차이를 균형계수(BalanceFactor, BF)라 한다.
그렇기 때문에 삽입, 삭제 연산을 수행할 때마다 트리의 균형계수를 체크하고, 균형계수가 1보다 커질 때 회전(Rotation) 연산을 통해 균형을 유지한다.
검색, 삽입, 삭제 모두 O(logN) 하지만 삽입, 삭제시마다 회전연산을 수행하기에 연산속도가 느릴 수 있다.
회전연산의 종류
- 왼쪽 - 왼쪽
- 오른쪽 - 오른쪽
  - Single rotation
- 왼쪽 - 오른쪽
- 오른쪽 - 왼쪽
  - double rotation
특징
1. 이진 검색 트리
2. 모든 노드의 두 하위 트리의 높이는 최대 1까지 차이가 난다.
3. 트리의 모든 노드는 노드에서 리프노드까지의 가장 긴 경로 길이인 높이 값을 갖는다.
4. 루트노드는 높이 0에 위치한다
5. 노드 균형계수는 왼쪽과 오른쪽 하위 트리의 높이 차이로 정의된다. AVL트리에서 노드 균형계수는 항상 -1, 0, 1 이다