CS 4일차

• Tree
• 퀵 정렬
• HTTP의 문제점들
• 데이터베이스 | DB를 사용하는 이유 | DB의 성능
• 프로세스 vs 스레드

Tree

• 계층적 관계 표현
• 루트 노드를 제외하고 모든 노드는 단 하나의 부모 노드만을 갖는다.
• 이진 트리는 배열과 연결 리스트로 표현 가능.
• 이진 트리란?
  • 루트를 기준으로 left, right subtree가 존재하고, 두 서브트리 모두 이진트리여야 한다.
  • 따라서 공집합도 노드로 인정한다.
  • 각 노드가 최대 2개 까지만 자식 노드를 갖을 수 있다.
• 이진 트리의 종류
  • 정 이진 트리 ( FULL )
    • 리프 노드를 제외하고 2개의 자식 노드를 갖는다. ( 자식이 있다면 2개고 아니면 없다! )
  • 완전 이진 트리 ( COMPLETE )
    • 왼쪽에서 오른쪽으로 순서대로 차곡 차곡 쌓인다
  • 포화 이진 트리 ( PERFECT )
    • 리프 노드 빼고 모든 노드가 2개의 자식 노드를 갖으며, 리프 노드들은 같은 레벨에 위치한다.
  • 이진 탐색 트리 ( BST )
    • 모든 키는 유일하다.
    • 어느 한 노드의 키 값은 자신의 왼쪽 부트리의 모든 노드들 보다 크다.
    • 어느 한 노드의 키 값은 자신의 오른쪽 부트리의 모든 노드들 보다 작다.
    • 왼쪽, 오른쪽 부트리 역시 위 조건들을 만족한다.
    • 이진 탐색의 빠른 검색 속도 O(log n)와 연결리스트의 장점인 삽입 삭제가 빠른 장점을 합친 것이다.
      삽입, 삭제는 O(1)이지만 위치를 찾는데에 검색 시간만큼인 log n 이 소요되어 O(log n) 이다.
  • 편향 이진 트리 ( SKEWED )
    • 한 쪽으로 편향된 트리 => AVL, Red - Black 트리로 해결할 수 있다.
  • B-tree, B+tree, AVL, Red-Black tree 등 여러 보완된 트리 구조들이 있다.

Quick Sort

int partition(int *arr, int left, int right){
    int i = left;
    int j = right;
    int mid = (i + j) / 2;
 
    int tmp = arr[mid];
    arr[mid] = arr[i];
    arr[i] = tmp;
 
    int pivot = arr[i];
 
    while(i < j){
        while(pivot < arr[j]){
            --j;
        }
 
        while(i < j && pivot >= arr[i]){
            ++i;
        }
 
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
 
    arr[left] = arr[i];
    arr[i] = pivot;
 
    return i;
}
 
void quickSort(int arr[], int left, int right){
    if(left < right){
        int pivot = partition(arr, left, right);
 
        quickSort(arr, left, pivot-1);
        quickSort(arr, pivot+1, right);
    }
}

• 퀵정렬은 분할-정복 방식의 O(n logn)의 속도를 지닌 빠른 정렬기법이며,
  같은 시간 복잡도를 지닌 정렬기법이라도 일반적인 경우에는 퀵정렬이 제일 빠른다.
• 그 이유는 캐시메모리의 히트율이 높은 in-place 기법이며,
  매 라운드마다 pivot의 위치가 정해져서 1개의 원소가 정렬 대상에서 빠져나가기 때문인다. 
• 정렬된 상태의 배열을 만날 때 최악의 경우로 O(n^2) 속도를 지니지만, 최선, 평균 시간 복잡도는 O(n logn) 이다.
• 이러한 경우를 극복하기 위해 pivot 선정을 랜덤, 중간값으로 하는 다양한 방식들이 있다.
• partition 함수는 pivot을 기준으로 그 수보다 작은 수들의 배열, pivot, 큰 수들의 배열로 정렬하는 역할로 O(n) 을 차지한다.
• quickSort 함수는 partition을 통해 구한 pivot의 위치를 기준으로 또다시 partition을 호출하는 분할하는 역할로 O(logn)을 차지한다.
• in-place 정렬이므로 공간복잡도는 O(n) 이다,
• 퀵정렬은 unstable sort 이다.

HTTP의 문제점들 ( victorydntmd.tistory.com/286 )

• 비연결성 단점
  • 비연결성으로 인한 장점도 있지만, 클라이언트의 요청을 완료하고 나면 해제하는 일은
    동일한 클라이언트에 대해서도 앞으로의 모든 요청에 대해 매번 새로운 연결 시도 및 해제의 과정을 거쳐야하므로
    오버헤드가 발생한다는 단점이 있다.
  • KeepAlive 패킷을 주고 받아 해결할 수 있지만, 수 많은 동시다발적인 인터넷 환경에서 클라이언트 마다
    keep alive 속성을 기록하고 계산하는 것은 서버에 과부하를 유발한다.
  • 비연결성으로 인해 서버는 같은 클라이언트인지를 식별할 수가 없어서 보안에 주의를 기울여야하고
    이러다 보면 번거로운 과정이 생긴다.
    => 이것을 Stateless라고 하며 상태를 기억하기 위해 세션, 쿠키, 토큰 등을 활용한다.
• 암호화 없이 Plain Text를 주고 받기 때문에 통신 과정에 도청 위험이 있다.
  => HTTPS 를 통해 SSL, TLS 를 사용하여 암호화하여 통신하는 것으로 방지할 수 있다.
• 비연결성으로 인해 서로의 통신상대에 대한 정보를 저장, 확인하는 과정이 없기 때문에 위장이 가능하다.
  따라서 자신이 통신하는 상대에 대한 신뢰성이 없기 때문에 DoS, 악성 위조 사이트 접근 등 여러 문제가 발생한다.
  => HTTPS 를 통해 통신하도록 하면 CA 가 서로의 신분을 보장하기 때문에 무분별하고 신뢰받지 못하는 접근을 방지할 수 있다.
• 무결성을 보장 못 한다.
  위의 두 특성이 가능한 덕분에 Man in the Middle 공격이 가능하다. 갈취 - 변조 - 위장 전송 의 과정을 거친 데이터인지 확인 불가.
  => HTTPS를 통해 대칭키를 안전하게 교환하여 암호문으로 통신을 한다면 통신 대상자 이외에는 전송, 데이터 작성, 데이터 복호화가 불가능해져 무결성이 보장된다.

DataBase

• 데이터베이스란 여러 사람에 의해 공유되어 사용될 목적으로 통합하여 관리되는 데이터의 집합을 말한다.
• 일반적으로 컴퓨터 시스템에 전자 방식으로 저장된 구조화된 정보 또는 데이터의 체계적인 집합을 의미한다.
• 데이터베이스를 사용하는 이유는 기존의 파일시스템의 단점들을 극복할 수 있기 때문이다.
  • 데이터 독립성
    • 물리적 독립성 - db의 사이즈를 늘리거나 성능 향상을 위해 데이터 파일을 새롭게 추가하더라도 응용프로그램을 수정할 필요가 없다.
    • 논리적 독립성 - db는 논리적인 구조로 다양한 응용 프로그램의 논리적 요구를 만족시켜줄 수 있다.
  • 데이터 무결성 - 데이터의 유효성 검사를 실시할 수 있어 다양한 경로로 잘못된 데이터가 발생되는 것을 방지할 수 있다.
  • 데이터 보안성 - 인가된 사용자들에게만 접근을 하용하여 보안성이 좋다.
  • 데이터 중복 최소화와 일관성 - 관련 데이터를 논리적인 구조로 관리함으로써 자료의 중복 문제와 이러한 데이터에 대한 불일치성 문제를 해결 할 수 있다.
• 데이터 베이는 I/O 에대한 처리를 줄이고 얼마나 빠르게 하느냐에 달려 있다.
  • 이를 위해 디스크 스캔 알고리즘, 쿼리 튜닝, 인덱스 사용 등이 이용된다.

Process

• 실행 중인 프로그램으로 메모리에 적재되어 CPU의 할당을 받을 수 있는 것.
• 운영체제로 부터 시스템 자원인 주소, 파일, 메모리, 스택, 힙, 데이터, 코드 영역과 고유 PCB 를 할당 받는다.
• PCB엔 PID, 프로세스 상태, PC, CPU register, 스케줄링 정보, 메모리 관리 정보 등이 있다.
• 할당 받은 자원들은 프로세스마다 각각 독립적이며 다른 프로세스의 변수나 자료에 임의로 접근할 수 없다.
  => IPC 기법을 사용하면 접근이 가능하다 - 파이프, 소켓, 파일 등을 이용한 통신 방법.
• 최소 1개의 쓰레드를 가지고 있다.
• 멀티 프로세스 프로그래밍
  • 하나의 응용 프로그램을 여러 프로세스로 구성한다.
  • 장점
    • 프로그램 구현, 설계가 직관적이고 쉽다.
    • 문제 발생 시 해당 프로세스만 처리하면 되고 이러한 결과가 다른 프로세스에 쉽게 영향을 끼치지 않는다.
  • 단점
    • 응용 프로그램 구동시 필요한 공유 자원인 경우에 IPC 기법이라는 복잡하고 까다로운 기술이 필요하다.
    • 특정 조건에 의해 Context Switching이 발생할 경우 오버헤드가 크다.
    • CS 발생 시 여러 자원 정보(특히 cashe)를 PCB에 저장하고 초기화하고, 다시 할당 받을 때 적재하여야 한다.

Thread

• 프로세스의 실행 단위로서 프로세스의 특정한 수행을 처리한다.
• 프로세스의 여러 자원을 (Code, Data, Heap )을 공유하고, 레지스터(PC)와 Stack 영역은 쓰레드마다 할당 받는다.
• 멀티 스레드 프로그래밍
  • 하나의 응용프로그램을 여러 개의 스레드로 구성하고 각 스레드로 하여금 하나의 작업을 처리하도록 하는 것이다.
  • 장점
    • 메모리 공간, 시스템 자원 소모가 감소되어 자원의 효율성이 증가한다.
      프로세스마다 필요한 자원을 하나로 나누어 쓰고, 이를 할당하는 데 필요한 시스템콜도 줄어든다.
    • 프로세스 내의 여러 쓰레드는 Heap 등을 통해 공유 자원 접근 및 통신이 용이하다.
    • 따라서 처리량, 응답시간이 상승한다.
    • 프로세스에 비해 작업의 크기가 작아 CS이 빠르고 모든 자원이 아닌 쓰레드의 Stack 영역만 초기화, 적재하면 된다.
  • 단점
    • 프로그래밍 설계가 복잡하고 어렵다.
    • 하나의 쓰레드에 문제가 있을 시 전체 프로세스에 악영향이 끼친다.
    • 공유 자원에 대한 동기화 문제가 존재한다.
  • Thread Safe 한 멀티 쓰레드 프로그래밍
    • 동기화 문제, 공유 자원 접근 시의 문제를 해결 하여 의도한대로 작동하도록 설계하자.
    • 임계영역에 대한 상호배제, 진행, 한정된 대기 특성을 만족시켜서 동기화를 달성한다.
    • 공유 자원 접근 시 제공된 매개 변수만을 사용하여 재진입성을 보장한다.