필기용 블로그

●Heap

 ▷Binary Tree의 일종

 ▷Node에 key값들을 저장한다.

 ▶조건

  ▶Heap-Order : key(v) ≥ key(parent(v)) 만족

   ▷최소 Heap - root = 최소 key

   ※ key(v) ≤ key(parent(v)) 인 경우, 최대 Heap

  ▶Complete Binary Tree 만족

   ▷높이가 h인 Binary Tree에 대해서, depth i (i < h)에는 2ⁱ 개의 Node가 있다.

   ▷Internal nodes는 External nodes의 왼쪽에 있다.

 ▶Height of a Heap

  ▷n개의 key를 가지는 Heap의 height : log(n)

  ▷n = 1 + 2 = 4 + ... + 2^h-1 + (1 ~ 2^h) ＜ (2^h+1)

 ▶Bottom-up Heap Construction

  ▶Heap Merging 이용

   ▷2개의 Heap과 새로운 key K에 대해

   ▷k를 root로하며, 2개의 Heap을 subtree로 하는 Heap 생성

   ▷downheap - heap order restore

  ▶phase i에서

   ▷2ⁱ - 1의 heap 2개를 가지고 2ⁱ⁺¹ - 1인 Heap을 만듬.

   ▷O(log(n))

 ▶Heap - Priotity Queue

  ▷Heap을 이용하여 Priority Queue 구현

  ▷각 Node에 Key, Element 저장

  ▷Insert, removeMin 효율적으로 동작 가능

  ▷Last Node Tracking (마지막 노드)

  ▶Insertion

   ▷Last Node 다음에 새로운 element 저장 (key값 저장, Last Node Update)

   ▶Heap Order Restore (Upheap)

    ▷새로운 Node가 Heap order를 만족하지 않을 수 있음.

    ▷부모 노드로 가며 Swaping (key값이 부모 노드보다 작으면 Swap)

    ▷root이거나, 부모 노드보다 클 때 까지 반복

    ▷O(log(n))

  ▶Removal

   ▷Root Node의 Key를 제거

   ▷공백을 Last Node로 매꿈 (+Last Node Update)

   ▶Heap Order Restore (Downheap)

    ▷새로운 root Node가 Heap order를 만족하지 않을 수 있음.

    ▷root에서 자식 노드로 가며 Swaping (key값이 자식 노드들보다 크면 자식 중 하나와 Swap)

    ▷최대 height (log(n)) 에 도달하거나, 자식 노드들보다 작을 때 까지 반복

    ▷O(log(n))

  ▶Last Node Update

   ▷left child에 도달하거나, root에 도달할 때 까지 위로 감. (부모로 감)

   ▷left child에 도달한다면, right child로 이동

   ▷leaf까지 왼쪽 아래로 이동

   ▷O(log(n))

○Heap-sort

 ▷Heap으로 구현된 Priority Queue의 Sorting

 ▷차지하는 공간 : O(n)

 ▷Insert : O(log n)

 ▷removeMin : O(log(n))

 ▷n개의 element : O(n log(n))

○Vector-based Heap

 ▷Vector로 Heap 구현

 ▷length : n + 1인 Vector 사용 (index 0은 사용하지 않음)

 ▶Positioning : rank i의 Node에 대해

  ▷left child : rank 2i

  ▷right child : rank 2i+1

 ▷Insert(e) : rank n+1에 insert

 ▷removeMin() : rank n remove

 ▶In-place Heap Sort

  ▷1. Vector를 Heap으로 만듬

  ▷2. removeMin()하며 Sorting

●Priority Queues

 ▷우선순위의 개념으로 entry들의 집합을 저장함.

 ▷entry: key, value의 짝

 ▷위치가 아닌 우선순위를 기준으로 저장

 ▶메소드

  ▶Main Methods

   ▷Insert(e) : entry e 추가.

   ▷removeMin() : key값이 가장 작은 값(들)을 제거, return

  ▶Additional Methods

   ▷min() : 가장 작은 key를 return (지우진 않음)

   ▷size()

   ▷empty()

 ▶Total Order Relation

  ▷Key값 : 순서가 명시되는 arbitary object여야함.

  ▷다른 2개의 entry가 동일한 key를 가질 수 있다.

  ▶비교 규칙

   ▷Reflexive property (반사성) : x ≤ x

   ▷Antisymmetric property (비대칭성) : x ≤ y ∧ y ≤ x => x = y

   ▷Transitive property (이행성) : x ≤ y ∧ y ≤ z => x ≤ z

○Sequence-based Priority Queue

 ▶Unsorted List

  ▷정렬되지 않는 상태로 저장

  ▶Algorithm

   ▷Insert : O(1) - 바로 넣음.

   ▷removeMin : O(n) - 가장 작은 값 찾아야 함.

 ▶Sorted List

  ▷정렬된 상태로 저장

  ▶Algorithm

   ▷Insert : O(n) - 적절한 위치에 넣어야 함.

   ▷removeMin : O(1) - 가장 앞의 값

○Priority Queue Sorting

 ▷1. 모든 element들을 priority queue에 넣음.

 ▷2. removeMin으로 가장 작은 element부터 가져옴.

 ▶Selection Sort

  ▷Unsorted List를 이용

  ▷1. n개의 insert -> O(n)

  ▷2. n번의 removeMin -> 1+2+...n = n(n-1)/2

  ▷-> O(n²)

 ▶Insertion Sort

  ▷Sorted List를 이용

  ▷1. n개의 insert -> 1+2+...n = n(n-1)/2

  ▷2. n번의 removeMin -> O(n)

  ▷-> O(n²)

○Comparator

 ▷우선순위 비교를 위한 

 ▶isLess(p, q)

  ▷return p < q;

 ▷같다 : !isLess(p, q) && !isLess(q, p)

○Exception Control

 ▷CPU는 단순히 명령을 읽고, 실행하기만 함. -> 시스템 상태 변화에 대응하기 힘듬.

 ▷예외 상황에 대응하기 위해 Kernal 사용

 ▶Exception

  ▷특정 event에 대응항져 Control을 User에서 Kernal로 이전시킴.

  ▷각 event는 고유한 exception handler를 가짐.

  ▶Asynchronous Exception

   ▷외부 프로세서의 interrupt pin에 의해 발생

   ▷next instruction을 return

   ▷Timer interrput, I/O interrupt from external device

  ▶Synchronous Exception

   ▶Traps

    ▷의도적인 Exception

    ▷next instruction을 return함

    ▷system calls, breakpoint traps, special instructions

   ▶Faults

    ▷의도적이지 않지만, 복구 가능한 Exception

    ▷current instruction을 다시 시도하거나, abort

    ▷page faults, protection faults(unrecoverable), floating poinr exceptions

   ▶Aborts

    ▷의도적이지 않고, 복구 불가능한 Exception

    ▷Abort함.

    ▷illegal instruction, parity error, machine check

○Static Library (.a)

 ▷여러 개의 Relocatable Object File을 모아 index가 있는 하나의 파일로 만든다.

 ▷unresolved external reference를 resolve하면 이를 reference하게 한다.

 ▶생성

  ▷.o 파일을 한데 묶어 생성

 ▶Linking

 ▶자주 사용되는 Library

  ▷C Standard Library (libc.a)

  ▷C Math Librarry (libm.a)

○Dynamic Library (.so, DLLs)

 ▶Static Library의 단점을 보완하기 위해 새롭게 고안된 라이브러리

  ▷라이브러리 코드가 실행 파일내에 내장되기 때문에, 실행 파일의 크기가 커진다.

  ▷라이브러리가 동시에 여러 파일에 포함되어 실행되면 메모리 공간 효율이 떨어짐

 ▷필요시에 사용할 수 있도록 최소한의 정보만 포함하거나, 독립적으로 DLL을 로드/사용/해제 가능

 ▶Linking

  ▶load-time linking

   ▷exe 파일이 처음 load되고 실행될 때, link함. (.so)

  ▶run-time linking

   ▷프로그램 실행 중에 dlopen()을 통해 link함. 

   ▷dlopen(), dlsym() 작업이 선행되어야 함.

   ▷사용이 끝난 뒤에는 dlclose()를 해주어야 함.

○Linking

 ▷obj 파일, 라이브러리 파일을 한데 묶어 실행파일로 만드는 과정

 ▶사용하는 이유

  ▶Modularity

   ▷여러 개의 소스파일을 모듈화하여 관리 가능하다. (각 팀이 다른 코드를 관리 가능)

   ▷자주 사용하는 함수들을 라이브러리로 만들어 사용 가능

  ▶Efficency

   ▷하나의 소스파일이 바뀌어도 모든 소스를 재컴파일 할 필요가 없기 때문에, 시간 절약 가능

   ▷라이브러리로 자주 사용하는 함수를 여러번 재정의할 필요가 없기 때문에, 공간 절약 가능

 ▶역할

  ▶Syombol Resoultion

   ▷프로그램은 함수명/변수명 등의 symbol을 정의하고, 이를 reference시킨다.

   ▷이런 symbol table은 obj파일의 symbol table에 배열의 형태로 있다. (이름, 크기, 위치)

   ▷linker는 각 symbol과 reference를 연결시켜준다.

  ▶Reolcation

   ▷각각의 code, data section을 하나로 합친다.

   ▷obj파일에 상대적으로 정해진 symbol들을 재배치시킨다.

   ▷모든 reference를 새로 정해진 위치로 Update시킨다.

 ▶Object Files 종류

   ▶Relocatable Object File (.o)

    ▷하나의 소스 파일 (.c)의 데이터, 코드의 정보를 담고 있는 파일   

    ▷ 다른 .o 파일들과 결합하여 실행파일을 만들 수 있다.

   ▶Executable Object File (.out)

    ▷코드, 데이터들이 메모리에 복사되어 바로 실행가능하다.

   ▶Shared Object File (.so)

    ▷load-time / run-time 도중에 동적으로 linking가능한 Relocatable Object File.

    ▷Dynamic Link Libraries (DLLs)라고도 부른다.

 ▶Ecutable and Linkable Format (ELF)

  ▷Linux에서 Object file에 대한 Standard binary format

  ▷ELF header : Word size, Byte ordering, File type, machine type, ...

  ▷Segment header table : Page size, virtual addresses memory segments, ...

  ▷.text section : Code

  ▷.rodata section : Read only data: jump tables, ...

  ▷.data section : Initialized lobal variables

  ▶.bss section

   ▷Uninitialized global variables

   ▷Symbol만을 가짐, 공간을 차지하지 않음?

  ▶.symtab section

   ▷Symbol table

   ▷Procedure and static variable names

   ▷Section names and locations

  ▶.rel.text section

   ▷Relocation info of .text section

   ▷명령의 주소가 exe파일에서 수정될 필요가 있음. (상대주소 - rip에서 연산)

  ▶.rel.data section

   ▷Relocation info of .data section

   ▷포인터의 주소가 exe파일에서 수정될 필요가 있음.

  ▷.debug section : symbolic debugging info (gcc -g)

  ▷.Section header table : Offsets and sizes of each section

 ▶Linker symbol

  ▶Global Symbols

   ▷해당 모듈에서 정의되어 다른 모듈에서 referenced 되는 symbol

   ▷non-static C functions, non-static global variables

  ▶External Symbols

   ▷다른 모듈에서 정의되어 해당 모듈에서 referenced 되는 symbol

  ▶Local Symbols

   ▷오직 해당 모듈에서 정의되고, referenced 되는 symbol (.bss, .data에 저장)

   ▷static-global variables

   ▷지역 변수와는 다르다. (지역 변수 - stack에 저장)

 ▶중첩 symbol

   ▷Strong : 초기화된 global variable

   ▷Weak : 초기화되지 않은 global variable / extern이 붙은 global variable

   ▶규칙

    ▷여러 개의 Strong : 컴파일 에러

    ▷하나의 Strong, 여러개의 Weak : Strong 선택

    ▷여러 개의 Weak : Weak중 무작위로 선택 -> 가장 위험!

   ▶해결책

    ▷Global variable의 사용을 피한다.

    ▷사용한다면 static/extern 한정자를 붙이거나 초기화 시킨다.

 ▶exe파일 -> Memory