with with

트리에 대한 이론적인 부분은 세 번에 걸쳐 포스팅한 바 있다. Tree 트리구조는 아주 중요한 알고리즘이라 세 번에 나누어서 진행할 예정이다. Tree... 이게 얼마나 사기(?)냐 하면은 트리를 이용하여 데이터를 관리할 경우 데이터 탐색에 필요한 시간이 O(n^2)에서 O( with611.tistory.com Tree - Binary Search Tree Binary Tree 중, 아래의 조건을 만족하는 Tree이다. 1. 루트노드의 왼쪽 서브트리의 노드는 루트노드보다 작거나 같아야 한다. 2. 루트노드의 오른쪽 서브트리의 노드는 루트노드보다 커야한다. BST로 with611.tistory.com Tree - Heap, B-Tree Heap Heap은 complete binary tree의 일종으로 추..

연결 리스트는 데이터와 포인터를 가진 노드들이 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조. vector와 같은 배열과 다르게 리스트의 중간 지점에서도 자료의 추가와 삭제가 빠르고, 메모리 선할당이 없고, 크기도 마음대로 정할 수 있을 뿐더러, 데이터의 추가/삭제시에도 이터레이터가 유효하다는 장점이 있지만, 랜덤 액세스가 느리다는 단점이 있다. 노드들이 포인터를 이용해서 연결되어 있는 방식에 따라 다음의 세 종류로 분류된다. - 단일 연결 리스트 (Singly Linked List) 각 노드에 데이터와 하나의 포인터가 있고, 각 노드는 다음 노드를 가리키는 구조이다. - 이중 연결 리스트 (Doubly Linked List) 각 노드에 데이터와 두 개의 포인터가 있고, 각 노드는 이전과 다..

- 정적 배열 (Static Array) 크기가 고정되어 있는 배열로 저장할 수 있는 데이터의 개수가 고정되어 있다. 한 번 할당하면 메모리를 추가적으로 할당하거나 해제하지 않아도 되고, 랜덤 액세스 속도가 빠르다는 장점이 있지만, 필요에 따라 크기를 조절할 수 없고, Stack영역에 할당되기 때문에 최대 크기의 제약이 있다는 단점이 있다. c++ STL의 array 라이브러리이다. 위 코드는 4행 8열의 배열을 생성한 후 이터레이터를 이용해서 탐색하는 코드이다. - 동적 배열 (Dynamic Array) 크기가 유동적으로 변하는 배열. 필요에 따라 배열의 크기를 조절할 수 있다는 장점이 있지만, 배열의 크기를 조절할 때 마다 메모리를 추가적으로 할당하기 때문에 퍼포먼스 이슈가 발생할 수 있다. c++ ..

레지스터와 명령어에 대해 살펴보자. (x86 아키텍쳐의 GAS/GNU format에 대해 다룹니다) - Register 레지스터 설명 %eax 데이터를 저장 %edx 데이터를 저장 %ecx 데이터를 저장 %ebx 데이터를 저장 %esi ? %edi ? %esp stack의 top. 즉 stack frame의 끝을 가리킴 %ebp stack frame의 시작을 가리킴 %eip program counter. 현재 실행중인 라인을 가리킴 레지스터 안에는 기본적으로 메모리의 주소가 저장되어 있다. (e.g. %eax = 0x8048b90) (%eax)와 같이 레지스터에 괄호를 치는 경우에는 레지스터가 가리키는 메모리주소에 담긴 값을 가리킨다. (e.g. (%eax) = 100 ) 상수는 $표시를 앞에 붙여 사용..

여러개의 분할된 ELF(Executable and Linkable Format)파일을 연결하는 과정을 linking이라고 부른다. 이 과정을 컴파일러의 linker가 수행하게 되는데, 그 동작 과정을 살펴보자. - Static linking 1. Symbol resolusion 심볼이란 함수 이름, 변수 이름 등 사람이 보기 편한 이름들을 말하며 이는 symbol table에 의해 관리된다. symbol resolusion은 이러한 심볼을 기계가 알아들을 수 있도록 이름을 주소값으로 바꾸는 작업을 말한다. 2. Relocation 분리되어있는 영역을 하나의 영역으로 합친다. 이 때, 코드의 위치가 변하게 되기 때문에 주소 값 역시 변하게 된다. 그 변화하는 주소 값을 계산하는 역할을 수행한다. linki..

프로세스는 CPU에 의해 위와 같은 가상 메모리 영역을 할당받게 되고, 이 가상 메모리는 MMU(Memory Management Unit)에 의해 실제 DRAM의 메모리 영역에 매핑된다. malloc으로 메모리를 할당받을 수 있고, realloc으로 메모리 영역을 확장할 수 있다. 하지만 경우에 따라 realloc시 메모리 영역을 통째로 복사해야 하는 경우가 생긴다. 이런 경우 성능저하 이슈가 생길 수 있는데, 이런 경우를 줄이기 위해 메모리 공간을 할당부터 관리까지 세심한 노력이 필요하다. 지금부터 그 노력의 흔적을 살펴보자. 메모리를 위와 같이 words 단위로 관리한다고 가정하자. (실제로 1word = 32B or 64B 이렇게 하고있긴 함) 만약 p = malloc으로 메모리 공간을 할당 받았는..

두 개 이상의 스레드가 하나의 메모리 공간을 동시에 참조하는 경우, 레이스 컨디션이 발생하여 프로그램을 실행할 때 마다 다른 결과가 출력되는 일이 발생할 수 있다. 이를 방지하기 위해 동기화를 하고, critical section(임계 영역)에 접근할 수 있는 스레드의 수를 제한한다. 동기화를 달성하기 위한 방법으로 mutex와 semaphore가 있다. - Mutex mutual exclusion(상호 배제)의 약자로 lock이라고도 한다. 기본적인 아이디어는 임계 영역에 진입할 때는 스레드가 뮤텍스를 잠그고, 나갈 때 잠금을 해제하는 아이디어이다. 즉, 잠겨있는 뮤텍스 아래로는 실행이 불가능하다. 뮤텍스를 사용할 때 주의할 점은, 임계영역으로 진입한 스레드가 뮤텍스를 풀기 전 중지되면 안된다는 것이다..

프로그램의 실행 흐름으로 c에서는 보통 posix threads library를 이용하여 구현한다. 스레드의 주된 활용법은 I/O, 네트워크 통신 등 처리시간이 오래 걸리거나, 언제 종료될지 모르는 동작을 수행하면서 동시에 다른 중요한 동작을 수행해야 할 때, 대기시간이 긴 동작을 자식 스레드에게 위임하는 방식으로 주로 활용한다. - pthread_create void *processfd(void *arg) { char buf[BUFSIZE]; int fd; ssize_t nbytes; fd = *((int *)(arg)); for ( ; ; ) { if ((nbytes = read(fd, buf, BUFSIZE)) < 0) break; // process buf data } return NULL; } ..