동기 vs 비동기
어떠한 프로그램 개발한다고 할 때, 어떤 function()를 구현할때 둘의 차이점은 아래와 같다.
동기 : function(); 이 끝나기를 기다렸다가 진행하는 것.
+) function()의 값이 꼭 필요하고 수행해야될 경우.
-) 그러므로 한 작업 시간이 길어지면, 전체 응답이 지연 될 수 있다.
비동기 : function(); 을 호출하고 바로 다음 줄로 넘어가는 방식.
+) function()의 값이 꼭 필요하지 않아 계속 진행해도 되는 경우.
+) 요청 순서에 상관없이, 동시&다수 작업 수행.
-) 작업이 끝날 때 이벤트 감지하고 결과를 받아 그에 따른 추가 작업을 해줘야 하므로 느릴 수 있음.
=> Callback 함수를 통해 지나갔지만 호출된 function()의 결과값이 받아진다.
node.js 및 안드로이드에서의 통신은 비동기가 대부분이다.
프로세스 동기화
: Race condition 해결하기 위함.
- 원하는 결과값을 도출하도록 임계구역 문제를 해결한다.
- 프로세스의 실행 순서를 원하는대로 제어한다.
- Busy wait 등과 같은 비효율성을 제거한다.
세마포는 동기화를 위해 만들어진 소프트웨어로서, 대표적인 동기화 도구이다. 사전적 의미로는 역이나 군대에서 사용하는 수신호라는 뜻이다.
세마포는 두 가지 동작이 존재하는데, 초기에는 P, V로 불렸다.(네덜란드에서 만들어져 네덜란드어의 약자이다. 현재에는 P는 test를 의미하며 acquire() 로 사용하고, V는 increment를 의미하며 release() 로 사용한다.
공통변수에 접근하는 쓰레드는 하나만 존재하도록 관리해야 한다. 이러한 공통변수 구역을 임계구역이라한다.
임계구역(Critical section) 문제
임계구역은 여러 개의 쓰레드가 수행되는 시스템에서 각 쓰레드들이 공유하는 데이터(변수, 테이블, 파일 등)를 변경하는 코드 영역을 말한다. 이는 동기화에서 중요한 문제 중 하나이다.
임계구역을 해결하기 위해서는 3가지 조건이 만족해야한다.
- Mutual exclusion(상호배타): 오직 한 쓰레드만이 진입 가능하다. 한 쓰레드가 임계구역에서 수행 중인 상태에서는 다른 쓰레드는 절대 이 구역에 접근할 수 없다.
- Progress(진행): 한 임계구역에 접근하는 쓰레드를 결정하는 것은 유한 시간 이내에 이루어져야한다.
- Bounded waiting(유한대기): 임계구역으로 진입하기 위해 대기하는 모든 쓰레드는 유한 시간 이내에 해당 임계구역으로 진입할 수 있어야 한다.
메모리 관리 전략
=> 내부 단편화 : 쪼개져 있는 상태에서 필요한 양 < 메모리 공간 할당
=> 외부 단편화 : 메모리 중간 중간에 사용하지 않는 공간.
압축(Compaction) : hole을 메모리 공간에서 이동시키기 위해서 메모리 계산의 부담이 발생
-연속 메모리 할당
: 메모리의 낭비 공간(hole)을 최소한으로 하기 위한 방법
a. 최초 적합(First-fit) : 가장 처음 만나는 빈 메모리 공간 = 빠름
b. 최적 적합(Best-fit) : 빈 메모리 공간 크기 & 프로세스 크기 => 최적의 공간 활용
c. 최악 적합(Worst fit) : 빈 메모리 공간 크기 & 프로세스 크기 => 최악의 공간 활용
https://www.youtube.com/watch?v=zjFpWi_tqDo
아래는 메모리 공간 연속 할당 X
- Paging
: , 프로세스를 일정한 단위(page -> frame + frame + frame + ...)로 잘라서 사용.
- 일정 크기로 나눈 다음에 프로세스 활용 but 내부 단편화가 생김.
+) 일정 공간으로 나눴기 때문에 메모리 사이에 hole, 즉 외부 단편화가 생기지않음.
- Segmentation
: 코드, 데이터, 스택 -> 3가지의 세그먼트를 논리적 내용의 단위로 자르기 때문에 크기가 일정하지 않다.
-) 필요한 크기만큼 메모리를 할당했다가, 해제해서 빈공간 생겨서 외부 단편화가 생김.
+) 프로세스가 필요한 크기만큼 메모리를 할당하기 때문에, 내부 단편화가 생기지 않음.
- Paging & Segmentation 혼용 기법
: 처음에는 Segement 단위로 자르고, 이로 인한 외부 단편화를 방지하기 위해 Segment->Page 단위로 자름.
- 테이블 2가지를 모두 거쳐야하므로 속도 느릴 수 있음.
가상 메모리
Drive(롤 10GB) -> Memory(필요한 부분만 올리게 됨 : 롤10GB여도 필요한 부분만 올림)-> CPU
위와 같이 필요한 부분만 Disk에 보관하는 기법을 가상 메모리라고 한다.
Page로 잘라서 보관함 -> Page Table(가상주소, 물리주소)에 보관해서 CPU에 알려줌.
이러한 L1, L2, L3, A, B와 같이 Page들을 가상메모리에 올려놓고 교체하는 것이 페이징 교체 알고리즘
캐시
- CPU 캐시 : Memory에 데이터를 요청해서 가져올 때 미리 저장해두어 접근 속도를 올려주는 용도.
a. 캐시 히트 : 캐시에 데이터가 있을 때
b. 캐시 미스 : 캐시에 데이터가 없을 때
- 데이터 지역성 2가지
a. 시간 지역성 : 한번 사용한 데이터는 다시 한번 사용 O
b. 공간 지역성 : 한번 참조된 데이터의 주변 데이터 참조 될 확률이 높음
=> 공간 지역성을 활용해 '캐시 라인'을 단위로 가져와서 캐시 적중률을 높힌다.
Array
: Random Access를 지원한다. 요소들을 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간복잡도는 O(1)
a. 정적 메모리 할당(컴파일 메모리 할당)
b. 인접한 메모리 위치 저장
c. 삽입/삭제 O(n)
Linkedlist
: Sequential Access를 지원한다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 한다. 따라서 특정 요소에 접근할 때 시간복잡도는 O(N)
a. 동적 메모리 할당(런타임에 메모리 할당)
b. 위치 주소가 linkedlist의 이전 요소에 저장
c. 삽입/삭제 O(1)
Stack
- FILO
- List로 구현하면 객체를 제거하는 작업이 필요하다. 하지만 Array로 구현하면 삭제할 필요 없이 index를 줄이고 초기화만 하면 되므로, Array로 구현하는 것이 좋다.
Queue
- FIFO
- Array로 구현하면 poll 연산 이후 객체를 앞당기는 작업이 필요하다. 하지만 List로 구현하면 객체 1개만 제거하면 되므로 삽입 및 삭제가 용이한 LinkedList로 구현하는 것이 좋다.
Deque(양방향 큐)
즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.
데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.
PriorityQueue의 동작 원리
우선순위큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해서 일반적으로 힙을 사용합니다. 힙은 완전이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(logn)입니다.
우선순위 큐는 힙이라는 자료구조를 가지고 구현한다. top이 최대면 최대힙, top이 최소면 최소힙으로 표현한다. 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있다. 이 성질을 통해 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있다.
Hash
해시테이블(HashTable)에 대해서 설명해주세요.
해시테이블은 효율적인 탐색을 위한 자료구조로 key값을 value에 대응시킨다. 해시테이블을 구현하기 위해서는 연결 리스트와 해쉬 함수가 필요하다. 해싱은 임의의 길이의 값을 해쉬 함수를 통해 고정된 크기의 값으로 변환하는 작업을 말하는데, 키 값을 해시 코드로 변환한 후 해당 해시 코드로 배열의 인덱스를 참조하여 값을 찾는다. 충돌이 발생할 수 있으며, 최악의 경우 O(N), 일반적으로 잘 구현된 경우는 O(1)의 시간 복잡도를 가지게 된다. 충돌은 Chaining, Open addressing 등의 방식으로 해결할 수 있다.
해시테이블은 균형 이진 탐색 트리로도 구현할 수 있다. 이 경우는 탐색 시간이 O(logN)이 된다. 이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다.
해시 테이블와 해시 테이블의 시간 복잡도에 대해 설명하시오.
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용합니다. 해시 테이블은 Key값에 해시함수를 적용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조입니다.
해시 테이블은 고유한 index로 값을 조회하기 때문에 평균적으로 O(1)의 시간복잡도를 갖습니다. 하지만 해시의 index값이 충돌이 발생한 경우 충돌된 index값에 대해 연결된 데이터들을 조회하여 원하는 값을 조회하기 때문에 O(N)까지 증가할 수 있습니다.
HashMap과 HashTable의 차이점에 대해 설명 해보세요.
동기화 지원 여부의 차이가 있다.
해시테이블(HashTable) : 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황
해시맵(HashMap) : 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황
- Thread-safe 여부
- Hashtable은 Thread-safe하고, HashMap은 Thread-safe하지 않다는 특징을 가지고 있습니다. 그렇기에 멀티스레드 환경이 아니라면 Hashtable은 HashMap 보다 성능이 떨어진다는 단점을 가지고 있습니다.
- Null 값 허용 여부
- Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용합니다.
- Enumeration 여부
- Hashtable은 not fail-fast Enumeration을 제공하지만, HashMap은 Enumeration을 제공하지 않습니다.
- HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있습니다.
- 최근까지 Hashtable은 구현에 거의 변화가 없지만, HashMap은 현재까지도 지속적으로 개선되고 있습니다.
'SW마에스트로 13기 > CS스터디' 카테고리의 다른 글
| 데드락(=교착상태)/사용자수준&커널수준 쓰레드/외부단편화&내부단편화/Context-Switching/Swapping (0) | 2022.10.11 |
|---|---|
| TCP, UDP, VPN(Virtual Private Network) (0) | 2022.10.05 |
| 프로세스와 쓰레드 (0) | 2022.09.27 |