자료구조
Array: data를 연속적이며 순차적으로 미리 할당된 크기 만큼 저장
=> 검색과 추가가 빠르다. 따라서 조회를 자주 해야 하는 경우 사용
=> 크기를 미리 정해야 하기 때문에 메모리 낭비나 overhead 발생 가능
Linked List: Node로 이루어져 있음, Node는 데이터 값과 다음 Node의 address저장.
=> Node의 next address를 통해 불연속적인 데이터를 연결하여 논리적 연속성 보장
저장 개수가 정해져 있고 조회가 많은 경우 Array 사용, 개수가 불 명확하고 삽입 삭제가 잦다면 Linked list 사용
Queue: queue는 FIFO 먼저 들어간 데이터가 먼저 나온다.
Stack: stack은 LIFO 마지막에 들어간 데이터가 먼저 나온다.
Priority queue: 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 이진완전트리를 활용한 Heap 자료구조를 사용하여 구현
BST(Binary Search Tree): 이진탐색트리, 어느 node를 선택하든 해당 node의 왼쪽 서브트리는 그 노드의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 오른쪽 서브트리는 그 노드의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 형태이다.
=> 시간 복잡도는 모두 O(logn)이고, 최악의 경우는 한쪽으로 치우친 tree가 된 경우로 O(n)이다.
Hash table: key-value 쌍의 데이터 입력받는다. 키 k값을 갖는 원소가 위치 h(k)에 hash된다.
=> 서로 다른 key의 해시값이 같을 때를 collision이라고 하는데, 우선 이러한 상황이 나오지 않도록 설계해야 하고 발생한 경우 해당 위치에 값이 있으면 다른 곳에 저장해주는 open addressing이나 linked list를 이용해 이어서 저장해주는 seperate cahining을 사용한다.
운영체제
프로세스: 실행파일 형태로 존재하던 프로그램이 메모리에 적재되어 cpu에 의해 실행되는 것
쓰레드: 쓰레드는 프로세스 내에서 실행되는 동작의 단위. 각 쓰레드는 속해있는 프로세스의 Stack메모리를 제외한 나머지 메모리 영역을 공유할 수 있다.
멀티 프로세스와 멀티 쓰레드:
- 멀티 쓰레드는 하나의 쓰레드 문제로 전체 쓰레드가 종료 될 수 있다.
- 멀티 프로세스는 하나의 프로세스가 죽더라도 다른 프로세스에 영향을 주지 않아 안정성이 높다
- 멀티 쓰레드를 사용하면 메모리 공간과 시스템 자원 소모가 줄어들게 된다. 또한 process를 생성하고 자원을 할당하는 등의 system call을 생략할 수 있기 때문에 자원을 효율적으로 관리할 수 있다.
프로세스간 통신: inter process communication 은 공유메모리를 사용하거나 소켓을 사용하여 구현한다.
동기화 문제:
1. Mutex: mutual exclusion 공유자원에 접근할 수 있는 process/thread의 수를 1개로 제한 임계영역에 들어가기 전에 반드시 lock을 획득해야 하고, 임계구역을 빠져나올 때 lock을 반환해야 함
- 세마포어: 변수에 동시에 접근 가능한 프로세스/쓰레드 개수를 저장. 변수가 0보다 크면 접근 가능, 임계영역에 접근시 변수 값 1 감소 임계영역에서의 작업이 끝나면 변수 값 1 증가
데드락: 상호배제, 점유대기, 비선점, 순환대기 조건을 다 가지고 있으면 발생할 수 있음.
=> 발생 확률이 낮은 경우 무시
=> 4가지 조건중 하나가 성립하지 않도록 예방
=> 순환 대기 상태가 발생하지 않도록 자원을 할당
=> deadlock발생을 탐지하고, 이를 회복
페이징: 메모리 공간을 동일한 크기의 page 단위로 나누어 물리적 메모리의 서로 다른 위치에 page들을 저장하는 메모리 관리 기법
=> 내부 단편화 문제 발생 가능
세그먼테이션: 메모리 공간을 논리적 의미 단위로 나누어, 연속되지 않는 물리 메모리 공간에 할당될 수 있도록 하는 메모리 관리 기법
=> 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되면 외부단편화 문제 발생 가능.
