# CS Note

## 자료구조 및 알고리즘

- 링크드 리스트와 배열
- 정렬(선택, 삽입, 버블, 머지, 퀵, 힙)
- 힙 (우선순위 큐)
- 해싱
- 이진 트리
- 포화 이진트리(perfect), 정 이진 트리(full), 편향 이진(skewed)
- 완전 이진트리(Complete), 균형 이진 트리(Balanced)
- 이진 트리 순회 (중위, 전위, 후위)
- 이진 탐색 트리
- 균형 이진 탐색 트리, AVL tree
- B tree, B+ tree
- 최단경로 알고리즘 (그래프)
- 레드 블랙 트리
- trie(트라이)

#### 링크드 리스트 vs 배열 (ArrayList)

- ArrayList
- 원하는 데이터에 무작위로 접근 가능 O(1), 랜덤 access가 가능
- 리스트의 크기가 제한되어 있으며, 리스트의 크기를 재조정하는 것은 많은 연산이 필요함
- 데이터 추가/삭제를 위해서는 임시 배열을 생성하여 복제해야 하므로 시간이 오래 걸림
- 맨 마지막 요소에 대한 추가/삭제는 시간이 오래 걸리지 않는다. O(1)

- LinkedList
- 리스트의 크기에 영향 없이 데이터를 추가 가능
- 데이터를 추가하기 위해 새로운 노드를 생성하여 연결하므로 맨 앞 , 맨 뒤의 추가/삭제 연산이 빠르다.
- 무작위 접근이 불가능하며, 순차 접근만이 가능하다. 랜덤 access 불가능
- 링크드 리스트에서 중간에 있는 요소를 바꿀 때에는 O(n)의 시간 복잡도를 가진다. 이유는 추가, 삭제할 위치를 찾는 검색 시간이 걸리기 때문.
- 그래도 빈번한 추가/삭제 연산에는 LinkedList가 ArrayList보다 더 좋음

- get/set을 자주 사용한다면 **ArrayList**
- 처음이나 끝에 잦은 삽입, 삭제가 발생한다면 **LinkedList**
- 하지만, 공간 복잡도의 경우 ArrayList는 연속된 메모리안에 저장되므로 낭비되는 공간이 없기 때문에 종종 속도가 빠른 경우가 발생할 수 있다. LinkedList는 요소마다 두개의 참조 노드가 필요하기 때문에 더 많은 공간을 차지하고 메모리 여기저기 노드가 흩어져 존재하는 경우 효율이 더 떨어질 수 있으니 잘 선택해서 사용해야한다.

#### 정렬 (선택, 삽입, 버블, 머지, 퀵, 힙)

- 6개 정렬에 대한 이론 공부
- 각 정렬에 대한 시간 복잡도

**선택 정렬**
> 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬과 최대 선택 정렬로 구분할 수있다. 이 둘의 차이는 오름차순 정렬, 내림차순 정렬로 구분한다.

1. 정렬되지 않은 인덱스의 맨 앞부터, 그 이후의 배열값 중 가장 작은 값을 찾는다.
2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
3. 위의 과정을 반복한다.
4. 시간 복잡도는 O(n^2)이다. 공간복잡도는 O(n)이다.

**삽입 정렬**
> 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.

1. 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장하고, 비교 인덱스를 현재 인덱스 -1로 잡는다.
2. 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장하고, 비교 인덱스를 -1하여 비교를 반복한다.
4. 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.
5. 시간 복잡도는 O(n^2)이고, 공간복잡도는 O(n)이다.

**버블 정렬**
> 버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다. 오름차순으로 정렬할 경우, 비교시마다 큰 값이 뒤로 이동하여 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다. 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장 되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 만 반복하면 된다.

1. 버블 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스와 이전의 인덱스 값을 비교한다.
2. 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
3. 현재 인덱스가 더 크면, 유지하고 다음 인덱스로 넘어간다.
4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.
5. 시간 복잡도는 O(n^2)이고 공간복잡도는 O(n)이다.

**합병 정렬**
> 분할 정복 방식으로 설계된 알고리즘이다. 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해나가는 방식으로, 분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다. 합병은 두 개의 배열을 비교하여 정렬하여 하나의 배열을 생성한다.

<분할 과정>
1. 배열의 시작 위치와 종료 위치를 입력받아 둘을 더한 후 2로 나눠 그 위치를 기준으로 배열을 반으로 나눈다.
2. 배열의 크기가 0이거나 1이 될 때까지 반복한다.

<합병 과정>
1. 두 배열 A,B의 크기를 비교한다. 각 배열의 현재 인덱스를 i,j로 가정하자.
2. i에는 A 배열의 시작 인덱스를 저장하고, j에는 B 배열의 시작 인덱스를 저장한다.
3. A[i]와 B[j]를 비교한다. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장한다.
4. 이를 i나 j 둘중 하나가 각자 배열의 끝에 도달할 때까지 반복한다.
5. 끝까지 저장을 못한 배열의 값을, 순서대로 C에 저장한다.
6. C 배열을 원래 배열에 저장한다.

- 시간 복잡도는 O(NlgN)이다. 공간복잡도는 정렬을 위한 배열을 하나 더 생성하므로 2N개 사용한다.

**퀵 정렬**
> 분할 정복을 이용하여 정렬을 수행하는 알고리즘이다. pivot으로 기준 값을 설정하여, pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다. 이를 반복하여 분할된 배열의 크기가 1이되면 배열이 정렬된 것이다.

1. pivot으로 잡을 배열의 값 하나를 정한다. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열의 중간값이나 랜덤 값을 정한다.
2. pivot을 기준으로 좌측 배열의 인덱스를 저장하는 left 변수, 우측 배열의 인덱스를 저장하는 right 변수를 생성한다.
3. right부터 비교를 진행한다. 비교는 right이 left보다 클 때만 반복하며 비교한 배열 값이 pivot 보다 크면 right를 하나 감소시키고 다시 비교를 반복한다.
4. pivot 값보다 큰 배열 값을 찾으면, 반복을 중지한다.
5. left 인덱스 값과 right 인덱스의 값을 바꿔준다.
6. 3,4,5 과정을 left < right를 만족할 때 까지 반복한다.
7. 위 과정이 끝나면 left 값과 pivot을 바꿔준다.
8. 맨 왼쪽부터 left-1까지 left+1부터 맨 오른쪽까지 나눠 퀵 정렬을 반복한다.

- 이미 정렬이 된 배열의 경우는 최악의 경우다. 이 경우 시간 복잡도는 O(N^2)이다. 이를 방지하기 위해 전체 배열 값 중 중간값이나 랜덤 값으로 pivot 값을 정하기도 한다.
- 일반적인 시간복잡도는 O(NlgN)이고 공간복잡도는 N이다.

**힙 정렬**

- 완전 이진 트리를 활용하여 최대 혹은 최소값을 쉽게 추출할 수 있는 자료구조이다. Java에서는 우선 순위 큐로 힙을 활용할 수 있다.

#### 해싱

- 장점
- 검색 방법 중 속도가 가장 빠르다.
- 데이터에 대한 추가, 삭제가 쉽다.
- 단점
- 해시 함수 선정에 문제가 있다.
- 충돌이 많아질 경우 오버플로 처리가 많아지고 메모리가 낭비된다.
- 대부분의 탐색 방법은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 탐색을 원하는 항목에 접근한다. 반면 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 직접 접근한다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(Hash Table)이라 부르고, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다.

- 해싱을 위한 탐색 키들은 문자열이거나 매우 큰 숫자일 수 있다. 탐색 키를 직접 배열의 인덱스로 사용하기에는 무리가 있다. 그래서 각 탐색 키를 작은 정수로 사상(mapping)시키는 함수(hash function)가 필요하다.

- 해시 함수란 탐색 키를 입력받아 해시 주소를 생성하고 이 해시 주소가 배열로 구현된 해시 테이블의 인덱스가 된다. 이 인덱스를 활용하여 자료를 저장할 수 있고 저장된 자료를 꺼낼 수도 있다.

- 지금까지 만들어진 어떤 해시 함수도 완벽히 다른 주소로 변환하는 함수는 존재하지 않는다. 동일한 주소를 반환하는 충돌 문제가 발생할 수 있다.

- 해쉬 테이블은 n개의 버켓으로 이루어지는 테이블이다. 하나의 버켓은 여러 개의 슬롯을 가질 수 있으며, 하나의 슬롯에는 하나의 항목이 저장된다.
https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=http%3A%2F%2Fcfile26.uf.tistory.com%2Fimage%2F992B23335989743235F108
- 하나의 버켓에 여러 개의 슬롯을 두는 이유는 서로 다른 두 개의 키가 동일한 해시 주소로 변환될 수 있으므로 여러 개의 항목을 동일한 버켓에 저장하기 위함이다.

- 충돌이 발생하면 같은 버켓에 있는 다른 슬롯에 항목을 저장하게 된다. 충돌이 자주 발생하면 버켓 내부에서의 순차 탐색 시간이 길어져서 탐색 성능이 저하될 수 있으므로 해시 함수를 수정하거나 해시 테이블의 크기를 적절히 조절해야한다. 이렇게 동일한 버켓에 슬롯을 여러 개 두어 충돌을 해결하는 방법이 **체이닝**이다.

- 이러한 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하면 해당 버켓에 더 이상 항목을 저장할 수 없게 되는 오버프로가 발생한다. 만약 버켓 당 슬롯의 수가 하나이면 충돌이 곧 오버플로가 될 것이다.

- 또 다른 충돌의 해결 방법은 **개방 주소법** (Open Addressing)이다. 이것은 비어있는 해시(버킷)를 찾아 데이터를 저장하는 기법이다. 개방 주소법에서의 해시 테이블은 1개의 버킷에 1개의 슬롯이 매칭되어 있는 형태로 유지된다.

- 비어 있는 버킷(해시)을 찾는 과정은 동일해야 한다.(일정한 규칙이 있어야 한다.)
1. 선형 탐색 : 다음 버킷(+1)이나 n개(+n)를 건너뛰어 비어있는 버킷에 데이터를 저장한다.
2. 제곱 탐색 : 충돌이 일어난 버킷의 제곱을 한 버킷에 데이터를 저장한다.
3. 이중 해시 : 다른 해시 함수를 한번 더 적용하여 다른 버킷에 데이터를 저장한다.
- 장점
- 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
- 또 다른 저장공간에서의 추가작업이 없다.
- 단점
- 해시 함수 성능에 의해 해시 테이블 성능이 좌지우지 된다.
- 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해야 한다.

#### 트리 (포화 이진트리(perfect), 정 이진 트리(full), 편향 이진(skewed), 완전 이진트리(Complete), 균형 이진 트리(Balanced), 레드 블랙 트리 , B-tree, B+tree, AVL-tree, Trie(트라이) ,이진 트리)

- 이진 트리
- 자식을 최대 2개까지만 가질 수 있는 트리.

- 완전 이진 트리 (Complete)
- 이진 트리 조건을 만족해야한다.
- 마지막 레벨을 제외한 나머지 레벨에서는 노드들이 꽉 차있어야한다.
- 마지막 레벨은 왼쪽부터 노드가 채워져 있어야 한다.

- 정 이진 트리 (full binary tree)
- 이진 트리의 조건을 만족해야 한다.
- 루트 노드를 제외한 모든 노드들은 2개의 자식 노드를 가지거나 자식 노드가 하나도 없어야 한다.
- 위의 완전 이진 트리 그림에서 15번이 없어진다면 full binary tree 이다.

- 포화 이진 트리 (perfect binary tree)
- 이진 트리 조건을 만족해야한다.
- 마지막 레벨에 있는 노드를 제외한 모든 나머지 노드들이 2개의 자식 노드를 가져야 한다.
- 이진 트리가 보유할 수 있는 최대의 노드를 가진 형태이다. 높이가 h인 이진 트리에서 있을 수 있는 최대 노드 수는 2^(h+1) - 1이다.

- 편향 이진 트리 (skewed binary tree)
- 편향 이진 트리란 모든 노드가 부모의 왼쪽 자식 혹은 오른쪽 자식이어서 트리의 구조가 한쪽으로 편향되어 치우친 트리이다.

- 균형 이진 탐색 트리 (balanced binary search tree)
- 오른쪽 서브 트리의 높이와 왼쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리를 말한다.
- 이러한 높이 차이를 균형인수(Balance Factor)라고 한다.
- 균형 이진 탐색 트리는 노드의 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지한다.
- 균형 이진탐색 트리 그림 
- (a)처럼 균형이 맞지 않는 트리의 경우 루트에서 특정 노드로 갈 때 평균 3.27회의 노드 접근이 필요하다. 하지만 (b)처럼 트리의 높이 균형을 맞춘다면 이동 비용이 3.0으로 감소된다.
- 이런 균형 이진 탐색 트리에는 여러가지가 있는데 대표적으로 AVL 트리, 레드 블랙 트리, B 트리, B+트리, B* 트리가 있다.
- https://velog.io/@soonbee/AVL-Tree%EB%A5%BC-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90
- 위의 링크는 AVL 트리가 높이 balancing 하는 방법을 나타낸 블로그이다.
- AVL 트리 문제 나올 확률 ★★★★

- AVL 트리
- AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형이 잡혀 있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전을 필요로 할 수 있다.

- 레드 블랙 트리
- 이진검색 트리는 저장과 검색에 평균 O(logN)시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 이루지 못한다. 편향 이진 트리가 되면 O(N)에 근접한 시간이 소요될 수 있다. 그래서 고안해 낸 것이 균형잡힌 이진검색 트리이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형 잡힌 이진검색트리로 대표적인 것은 레드블랙트리와 AVL 트리이다.
- 레드블랙 트리는 자가균형이진탐색 트리(self-balancing binary tree)로써, 대표적인 연관배열 등을 구현하는데 사용되는 자료구조이다. 레드블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을 때 O(logN)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.
- 레드블랙 트리는 이진검색트리의 모든 노드에 레드 또는 블랙의 색상을 칠한다. 단, 다음의 성질을 만족하도록 색칠해야 한다. 이를 레드블랙 특성이라 한다.
- 1. 루트는 블랙이다.
- 2. 모든 리프(NIL)는 블랙이다.
- 3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다. )
- 4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
- 5. 새로 삽입되는 노드는 레드이다.
- 레드 블랙 트리는 함수형 프로그래밍에서 유용하다. 함수형 프로그래밍에서 쓰이는 연관 배열이나 집합(set)등을 내부적으로 레드 블랙 트리로 구현해 놓은 경우가 많다. 이런 구현에는 삽입, 삭제시 O(log N)만큼의 시간이 필요하다.
- 
- Java의 HashMap 사이즈가 64가 넘을 때, 레드 블랙 트리를 사용하고 TreeMap 또한 레드 블랙 트리를 사용한다.

- B 트리
- 이진 트리를 확장해서 더 많은 수의 자식을 가질 수 있게 하였다. 대량의 데이터를 처리해야 하는 검색 구조인 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 큰 장점이다. 예를 들어 한 블럭이 1024바이트라면 2바이트를 읽으나 입출력에 대한 비용은 동일하다. 대량의 데이터는 메모리 보다는 하드디스크 혹은 SSD에 저장되어야 하는데 이들 외부 기억 장치들은 블럭 단위로 입출력을 하기 때문이다.
- 그렇다면 하나의 노드를 1024바이트가 되도록 조절한다면 입출력 면에서 매우 효율적인 구성이 된다. 이런 장점으로 실제 B-Tree는 많은 데이터베이스와 파일 시스템의 인덱스 저장 방법으로 애용되고 있다.
- 하나의 노드에 여러 자료가 배치되는 트리 구조이다. 한 노드에 M개의 자료가 배치되면 M차 B-Tree라고 한다.
- 스스로 균형을 맞추는 트리이므로, 최악의 경우에도 O(logN)의 검색 성능을 보인다.
- 각 노드의 자료는 정렬된 상태여야 하고, 노드의 자료수가 N이라면 자식의 수는 N+1이어야 한다.
- 입력 자료는 중복될 수 없고 외부 노드로 가는 경로의 길이는 모두 같다. (외부 노드는 모두 같은 레벨에 있다.)
- Root 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
- Root 노드는 적어도 2개 이상의 자식을 가져야 한다.
- 

- B+ 트리
- 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표한하기 위한 트리자료구조의 일종이다.
- 동적이며, 각각의 인덱스 세그먼트(보통 블록 또는 노드라고 불리는) 내에 최대와 최소 범위의 키를 개수를 가지는 다계층 인덱스로 구성된다.
- 

#### 이진 트리 순회

- 전위 순회( Pre-Order )
- 뿌리(root)를 먼저 방문한다.
- root(중간) -> 왼쪽 자식 -> 오른쪽 자식
- 중위 순회 ( In-Order )
- 왼쪽 자식 트리를 먼저 방문 후 뿌리(root)를 방문한다.
- 왼쪽 자식 -> root(중간) -> 오른쪽 자식
- 후위 순회 ( Post-Order )
- 왼쪽 부터 모든 자식 트리를 먼저 방문 하고 뿌리(root)를 방문한다.
- 왼쪽 자식 -> 오른쪽 자식 -> root(중간)

- 전위 순회 : 0 -> 1 -> 3 -> 7 -> 8 -> 4 -> 9 -> 10 -> 2 -> 5 -> 11 -> 6
- 중위 순회 : 7 -> 3 -> 8 -> 1 -> 9 -> 4 -> 10 -> 0 -> 11 -> 5 -> 2 -> 6
- 후위 순회 : 7 -> 8 -> 3 -> 9 -> 10 -> 4 -> 1 -> 11 -> 5 -> 6 -> 2 -> 0
https://minhamina.tistory.com/83 순회 관련 포스팅, 참고하면 좋을듯
왠지 나온다면 문제를 풀고 전위 중위 후위 순으로 작성해라 or 코드 보여주면서 틀린곳있냐 체크할 듯?
https://www.acmicpc.net/problem/2263 이 문제를 단답형 주관식으로 나올수도 있으니 한번 풀어보면 좋을듯

#### 이진 탐색 트리

> 이진 탐색 트리란 이진 탐색(binary search)과 연결리스트(Linked List)를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.
> 이진 탐색(이분 탐색)의 경우 탐색에 소요되는 시간 복잡도는 O(logN)으로 빠르지만 자료 입력, 삭제가 불가능하다. 연결리스트의 경우 자료 입력, 삭제에 필요한 시간 복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 시간복잡도가 발생한다. 두 마리 토끼를 잡는 것이 이진 탐색 트리의 목적이다.

- 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
- 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
- 중복된 노드가 없어야한다.
- 왼쪽, 오른쪽 서브트리 또한 이진 탐색 트리이다.
- InOrder(중위 순회)를 통하여 모든 키를 정렬된 순서로 가져올 수 있다. (자식 노드가 2개 인 노드를 삭제할 때 필요.)

- <삽입>
- 1. 삽입을 하기 전, 검색을 수행한다.
- 2. 트리를 검사한 후,(모든 노드를 검사하는 것이 아니다.) 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

- <삭제>
- 자식 노드가 없는 노드(리프 노드) 삭제 : 해당 노드를 단순히 삭제한다.
- 자식노드가 1개인 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식 노드를 대입한다.
- 자식노드가 2개인 노드 삭제 : 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰 값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽 서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브 트리에서 가장 작은 값을 가지는 노드)를 삭제한다.
https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/
---- 이진 탐색 트리 연산 문제 왠지 나올듯? 예제 검색해서 풀어보면 좋을듯 !!!!!! ★★★★★

## 프로그래밍 언어

- 기계어, 어셈블리어
- 기계어
- 기계어는 컴퓨터가 사용하는 언어이다. 구체적으로 이야기하면 컴퓨터의 CPU가 명령을 처리할 때 사용하는 언어이고, 이진법으로 구성되어 있다.
- 어셈블리어
- 기계어 자체를 사용하여(이진법만으로) 프로그래밍 할 수 있지만 말 같지도 않은 소리다.
- 기계어 숫자의 의미를 사람이 좀 더 이해하기 쉬운 단어로만 변경해도 훨씬 편해진다.
- 
- 기계어에서 숫자를 의미 있는 단어로 바꿔서 사람들이 이해하기 쉽게 만든 언어가 '어셈블리어'이다.
- 
- 하지만 CPU 입장에서는 어셈블리어를 이해할 수 없기 때문에 프로그래머가 어셈블리어로 작성한 프로그램 소스를 기계어로 번역해야지만 CPU가 사용할 수 있다.
- 어셈블리어를 기계어로 번역하는 프로그램이 바로 "어셈블러"이다.
- 고급언어
- 프로그래밍 언어의 문법 구조가 기계어와 유사하면 '저급 언어', 사람들이 이해하기 편하도록 만들어진 언어를 '고급언어'라고 한다.
- High, Low의 의미는 사람의 언어에 가까운지, 기계 언어에 가까운지 차이지 좋고 나쁨을 이야기 하는 것이 아니다.
- 어셈블리어와 기계어는 '저급 언어'이고 C, C++, Java와 같은 언어들은 '고급 언어'이다.
- C언어와 같이 고급 언어를 저급 언어로 바꿔주는 프로그램을 "컴파일러" 라고 한다.

- oop 4가지 특징
- 캡슐화 (Encapsulation)
- 캡슐화의 속성으로는 2가지가 있다.
- 1. 필드와 메소드를 클래스로 묶는 '데이터 캡슐화'.
- 2. 외부에서 객체의 상태를 변경하는 것을 막기위한 '은닉화'(접근제어자, setter, getter사용)
- 프로그램을 설계 할때 '높은 응집도'(변경시 해당 클래스만 변경됨)와 '낮은 결합도'(다른 클래스들의 간섭이 낮음)를 유지해야 요구사항을 변경하기 쉽다. 캡슐화는 낮은 결합도를 유지할 수 있도록 해주는 `객체지향 설계 원리`이다.
- Class 사용자는 Class 내부 구현에는 신경 쓸 필요 없이, 제공되는 Interface(method)를 이용하기만 하면 된다.
- 상속(Inheritance)
- 자식 클래스가 부모 클래스를 물려받고 기능을 추가하여 확장하는 개념이다.
- 부모 클래스를 Super class라 부르며 자식 클래스를 Sub class라 부른다.
- 자식 클래스는 부모 클래스의 속성을 물려받아 재사용함으로써 코드 작성에 드는 시간과 비용을 높이는 효과가 있다.
- Java에서 상속은 단일 상속만 지원한다. 즉, 자식은 하나의 부모만 가질 수 있다. (ㅅ;발 싸피)
- Java에서 단일 상속의 제한점을 극복한 방법이 "Interface"를 이용하는 것이다.
- 다중 상속을 허용하지 않는 이유는 코드의 모호성을 배제하기 위해서다.
- 다형성 (Polymorphism)
- 오버라이딩(overriding) vs 오버로딩(overloading)을 잘 알자!
- 말 그대로 여러가지 형태를 가질 수 있는 것이다.
- 하나의 참조변수로 여러 타입의 객체를 참조할 수 있다. 즉, 부모타입의 참조변수로 자식타입(상속)의 객체를 다룰 수 있는 것이 다형성의 기본 개념이다.
- 오버라이딩(Overriding)
- 자식 클래스에서 부모 메소드의 기능을 자신의 기능에 맞게 메소드 내용(Body)을 새롭게 재정의 하는 것이다.
- 오버로딩(Oveloading)
- 클래스 내에서 이름은 같지만 서로 다르게 동작하는 여러 메소드를 오버로딩이라고 한다.
- 클래스 O의 메소드 a는 두 개의 본체를 갖고 있다. 동시에 두 개의 본체는 하나의 이름인 a를 공유하고 있다. 같은 이름이지만 서로 다른 동작 방법을 갖고 있기 때문에 오버로딩은 다형성의 한 예라고 볼 수 있다.
- 추상화 (Abstraction)
- 추상화란 말 그대로 상세한 정보는 무시하고 필요성에 의해 있어야할 정보들만 간추려서 구성하는 것이다.
- 추상 메소드, 추상클래스와 인터페이스가 그 예이다. 즉, 공통적인 특성(변수, 메소드)들을 묶어 표현한 것이다.

- OOP 설계 5가지 원칙, SOLID
- 클린 코드의 저자, 로버트 마틴이 객체 지향 프로그래밍 및 설계의 다섯 가지 기본 원칙을 마이클 패더스가 SOLID라는 약어로 소개한 것이다.
- 1. 단일 책임 원칙, SRP(Single Responsibility Principle)
- 하나의 클래스는 하나의 책임만 가져야한다. 클래스는 그 책임을 완전히 캡슐화해야 함을 말한다.
- 어떤 변화에 의해 클래스를 변경해야 하는 이유는 오직 하나뿐이어야 함을 의미한다.
- 2. 개방 폐쇄 원칙, OCP(Open - Closed Principle)
- 확장에는 열려있고, 변경에는 닫혀있다. 기존의 코드는 변경하지 않으면서(Closed), 기능을 추가할 수 있도록(Open) 설계해야 한다.
- OCP는 강한 응집도와 낮은 결합도를 유지시킨다.
- 3. 리스코프 치환 원칙, LSP (Liskov Substitution Principle)
- 객체는 프로그램의 정확성을 깨지 않으면서, 하위 타입의 인스턴스로 바꿀수 있어야 한다.
- 이를 위해서 하위 타입의 객체는 상위 타입의 책임을 무시하거나 재정의 하지 않고 확장만 수행하도록 설계해야 한다.
- 4. 인터페이스 분리 원칙, ISP (Interface Segregation Priciple)
- 하나의 범용적인 인터페이스보다 여러 개의 구체적인 인터페이스가 좋다는 원칙이다.
- 5. 의존관계 역전 원칙, DIP (Dependency Inversion Principle)
- 의존 관계를 맺을 때 변화하기 쉬운 것, 자주 변화하는 것보다는 변화하기 어려운 것, 거의 변화가 없는 것에 의존하라는 원칙이다.
- 즉, 구체적인 클래스(구체화)보다 인터페이스나 추상 클래스(추상화)에 의존하라는 뜻이다.

- 자료형 (Java)

- 인터프리터, 컴파일러 (에서의 함수 구현) + (둘의 차이)
- 
- https://blog.naver.com/ehcibear314/221228200531 (참고)
- 컴파일러와 인터프리터는 사람이 이해할 수 있는 고급언어로 작성된 소스코드를 기계가 이해할 수 있는 기계어로 번역해주는 프로그램이다.
- 컴파일러
- 컴파일러는 사람이 고급 언어를 작성하면 해당 고급 언어를 한번에 번역을 한다. 그렇기 때문에 줄 단위로 번역을 하는 인터프리터에 비해 번역 시간은 오래 걸린다.
- 하지만, 컴파일러는 한번 번역을 하면 실행 파일이 생성이 되어 다음에 실행을 할 때 기존에 생성되었던 실행 파일을 실행하기 때문에 인터프리터에 비해 실행 시간은 빠른 편이다.
- C가 컴파일러가 있다. Java는 컴파일러 인터프리터 둘다 있다.
- 인터프리터
- 인터프리터는 컴파일러와 다르게 한줄 한줄씩 번역을 진행하기 때문에 한번에 번역을 진행하는 컴파일러에 비해 번역 시간은 빠른 편이다.
- 번역을 할 때 실행 파일을 생성하지 않기 때문에 매번 실행을 할 때마다 같은 번역을 진행해야 합니다.
- 그래서 매번 번역을 거치기 때문에 인터프리터를 사용하는 언어들은 컴파일러를 사용하는 언어들에 비해 실행 속도가 느린 편이다.
- 인터 프리터 vs 컴파일러
- 언뜩 보기에는 컴파일러가 인터프리터보다 실행 속도가 빠르기 때문에 좋아보이는데 인터프리터도 사용하는 이유가 무엇일까요?
- 컴파일러는 플랫폼(하드웨어)에 종속적이지만, 인터프리터는 모든 플랫폼(하드웨어)에 종속되지 않는 특징이 있다.
- 각각 A, B라는 CPU가 존재하고 이 둘은 호환이 되지 않는다고 가정하자.
- A CPU에서 돌아가는 프로그램을 만들고 컴파일러를 통해 실행파일을 만들고 이를 B CPU에서 실행시키면 작동이 안될 것이다.
- A CPU에서 컴파일러를 통해 실행파일을 만들게 되면 A 하드웨어의 환경에 맞게 변환을 하기 때문에 A CPU와 호환되는 CPU에서만 작동될 수밖에 없다.
- 하지만 인터프리터는 해당 프로그램을 번역하는 하드웨어의 환경에 맞게 변환을 하기 때문에 B CPU에서 실행을 해도 잘 작동될 것이다.
- 이러한 장점 때문에 인터프리터를 사용하기도 한다.
- 컴파일러와 전처리기 차이
- 전처리기
- 전처리기(preprocessor)란, 컴파일러가 소스 파일을 컴파일하기 전에 사용자가 지시한 작업을 먼저 처리하는 것이다.
- 즉, 컴파일러보다 먼저 작업을 처리해준다. 그래서 중요한 작업은 전처리기가 하는 경우가 많다.
- C에서 #include를 많이 썼는데 #이 전처리기가 작업하라고 표시하는 것이다.
- 컴파일 주요 과정
- 인터프리터 과정
- 정적 시맨틱, 동적 시맨틱
- 제네릭
- https://st-lab.tistory.com/153 (참고)
- 데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질수 있도록 하는 방법이다.
- 객체와 클래스 , 인스턴스
- 클래스 (Class)
- 객체를 만들어 내기 위한 설계도 혹은 틀
- 연관되어 있는 변수와 메소드의 집합
- 객체(Object)
- 소프트웨어 세계에서 구현할 대상
- 클래스에 선언된 모양 그대로 생성된 실체
- '클래스의 인스턴스' 라고도 부른다.
- 객체는 모든 인스턴스를 대표하는 포괄적인 의미를 갖는다.
- oop 관점에서 클래스의 타입으로 선언되었을 때 '객체'라고 부른다.
- 인스턴스(Instance)
- 설계도를 바탕으로 소프트웨어 세계에 구현된 구체적인 실체를 말한다.
- 즉, 객체를 소프트웨어에 실체화 하면 그것을 '인스턴스'라고 부른다.
- 실체화된 인스턴스는 메모리에 할당된다.
- 인스턴스는 객체에 포함된다고 볼 수 있다.
- oop의 관점에서 객체가 메모리에 할당되어 실제 사용될 때 '인스턴스'라고 부른다.
- 추상적인 개념(또는 명세)과 구체적인 객체 사이의 관계에 초점을 맞출 경우에 사용한다.
- '~의 인스턴스'의 형태로 사용된다.
- 객체는 클래스의 인스턴스다.
- 객체 간의 링크는 클래스 간의 연관 관계의 인스턴스다.
- 실행 프로세스는 프로그램의 인스턴스다.
- 즉, 인스턴스라는 용어는 반드시 클래스와 객체 사이의 관계로 한정지어서 사용할 필요는 없다.
- 인스턴스는 어떤 원본(추상적인 개념)으로부터 '생성된 복제본'을 의미한다.
- 

- 상속, 접근 제어
- 

- 동적 바인딩 , 정적 바인딩
- 동적 바인딩 (Run-time Binding, Late Binding)
- 동적바인딩은 프로그램이 실행되어야 메모리에 크기가 얼마만큼 할당되는지 알 수 있게 되는 것을 의미한다.
- 자바의 경우 모든 new를 사용하여 만들어진 객체는 동적 바인딩된 것이라 할 수 있다.
- 정적 바인딩 (Compile-time Binding, Early Binding)
- 컴파일러 시간에 변수의 크기를 정할 수 있는 것을 의미한다.
- char, short, int, float, double 변수가 정적 바인딩된 변수이다.

- 함수형 언어 (함수형 프로그래밍?)
- 변경 가능한 상태를 불변 상태(Immutable)로 만들어 SideEffect를 없애자.
- f(x) = y , 함수 f()에 x를 입력하면 항상 y라는 결과값이 나오는 것을 말한다. 여기서 중요한 것은 함수 안에서 상태를 관리하고 상태에 따라서 결과값이 달라지면 안된다는 점이다. 상태를 사용하지 않음으로 SideEffect를 사전에 차단할 수 있다. 또한, 변수보다는 상수를 사용해 SideEffect를 차단한다.
- 모든 것은 객체이다.
- 함수형 언어에서는 모든 것이 객체이다. 클래스 외에 함수 또한 객체이기 때문에 1.함수를 값으로 할당 할 수있고, 2.파라미터로 전달 및 3.결과 값으로 반환이 가능하다. 위 3가지를 만족하는 객체를 1급 객체라고 한다.

- 코드를 간결하게 하고 가독성을 높여 로직에 집중 시키자.
- Lambda 및 Collections, Stream과 같은 API를 통해 보일러 플레이트(단순 노동 작업을 없애주는것)를 제거할 수 있다.
- 내부에 직접적인 함수 호출을 통해 가독성을 높일 수 있다. 실제 구현할 로직에만 집중할 수 있다.
- 

- 동시성 작업을 보다 쉽고 안전하게 구현하자.
- 위에서 설명한 immutable 값을 사용하여, 여러 쓰레드에서 접근을 하더라도 SideEffect를 발생시키지 않는다. 또한, Lock, UnLock 같은 보호 장치도 필요 없다.

> 참고 (프로그래밍 언어론 관련)
> http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791185578729
> https://chayan-memorias.tistory.com/98

## 네트워크

- OSI 7계층 기본적인 내용
- https://copycode.tistory.com/28?category=740132 (참고)
- 각각의 호스트들은 OSI 7계층을 가지고 통신을 수행한다. 일반 사용자는 OSI 7계층 맨 위에 있는 응용 계층으로부터 데이터 송수신을 요청하고 이 요청은 하단의 계층으로 순차적으로 전달되어 맨 아래에 있는 물리 계층에 도달하여 상대 호스트에 전송하게 된다. 각각의 층들은 다른 일을 수행하며 데이터를 안전하게 옮기게 된다. 데이터를 수신하는 호스트는 송신 호스트와 반대로 하단의 물리 계층에서 데이터를 받아 응용 계층까지 올려주게 된다.
- 물리 계층
- 전송 매체의 물리적인 인터페이스에 관한 사항을 다룬다. 전송 매체에서는 비트 교환 문제를 다룬다. 7계층 중 물리 계층만이 하드웨어 시스템으로 구현된다.
- 데이터링크 계층
- 물리 계층을 통해 전송되는 데이터의 물리적 전송 오류를 해결한다. 데이터의 단위로 `프레임`을 이용하며 프레임 헤더에 표시되는 송수신 호스트 정보에는 LAN 카드에 내장된 송수신 호스트의 MAC 주소가 기록된다. 송수신 호스트의 전송/처리 속도 차이를 처리하는 `흐름 제어`의 기능도 수행한다.
- 네트워크 계층
- 네트워크 계층의 가장 중요한 역할은 경로 설정이다. 송신 호스트가 전송한 데이터가 어떤 경로를 통해 수신 호스트에 전달되는지를 결정하는 라우팅 문제를 처리한다. 전달 경로는 미리 정해진 길을 가는 정적인 방식과 상태에 따라 경로를 설정하는 동적인 방식으로 나뉜다. 네트워크 계층의 데이터는 `패킷`이라고 불리며 경로 선택을 위해 호스트 주소가 필요하다. 인터넷에서 사용하는 호스트 주소가 바로 IP 주소이다. 패킷이 지나치게 많으면 전송 속도가 떨어지게 되는 이러한 과도한 트래픽의 증가를 막기 위한 `혼잡 제어`의 역할을 수행한다.
- 전송 계층
- 전송계층은 7계층 중에서 가장 중요한 계층으로 꼽힌다. 전송 계층은 통신 양단에 있는 최종 사용자 사이의 종단 연결을 제공한다. 호스트에서 실행되는 프로세스와 프로세스 사이의 연결을 설정하여 데이터를 주고받을 수 있게 해주는 것이 전송 계층이다. 컴퓨터 내부에서 논리적으로 구축되는 통신 당사자인 프로세스 사이의 통신 문제를 다룬다. TCP/IP 모델에서는 운영체제 내부에 계층 4까지의 기능을 구현하고, 상위 계층의 기능은 사용자 프로그램으로 구현된다.
- 세션 계층
- 세션 계층은 전송 계층과 매우 유사한 기능을 수행한다. 하지만 조금 더 상위 계층인 만큼 사용자에게 더 가까운 기능을 수행한다. 대화 제어와, 토큰 제어, 동기 기능을 수행한다. 대화 제어는 대화 내용에 관련된 내용을 수정하는 작업을 하고 토큰 제어는 발언권에 대한 역할을 수행한다.
- 표현 계층
- 표현 계층은 데이터의 의미와 표현 방법을 처리한다. 호스트 간의 데이터를 이해할 수 있도록 변환 하는 과정을 수행한다. 또한 보안과 용량 크기를 고려하는 암호화와 압축의 기능도 수행한다.
- 응용 계층
- 응용 계층은 다양하게 존재하는 응용 환경에서 공통을 필요한 기능을 수행한다. http, ftp(파일 공유 서비스), telnet(인터넷 서비스)등 사용자에게 서비스를 해주는 모든 부분이 응용 계층의 기능이라고 할 수 있다.

- application layer
- transport layer
- network layer

- 서브넷 마스크(subnet mask)
- 서브넷 마크스의 형태는 기본적으로 IP 주소와 같은 32bit 이진수이다. IP와 똑같은 xxx.xxx.xxx.xxx의 형태를 띄고 있다. 서브넷 마스크의 목적은 IP 주소와 AND 연산하여 Network 부분의 정보를 걸러내려는 것이다.
- 
- 클래스 A를 예로 들면, 클래스 A의 IP가 116.81.97.8일 경우 클래스 A의 서브넷 마스크는 255.0.0.0 이므로 이것을 이진수로 변환했을 경우 AND 조건을 수행했을 시 나오는 것은 116.0.0.0이다. 이것이 바로 클래스 A의 Network ID이다. 나머지는 Host를 식별하는 Host ID 부분이다.
- 
- 그리고 IP 주소 뒤에 /24 같은 표시가 붙은 것을 볼 수 있다. 이것은 서브넷 마스크의 bit수를 의미한다. 클래스 A를 예로 들면 서브넷 마스크의 초기 8개의 bit가 1로 되어있기 때문에 /8로 붙는다. 또 하나의 예를 들면 192.168.3.19/24는 네트워크 ID가 192.168.3.0이며, 서브넷 마스크는 255.255.255.0이라는 뜻이다. 이 서브넷 마스크는 Network ID부분은 1이 연속적으로 있어아하며, Host ID 부분은 0이 연속적으로 있어야 하는 규칙이 있다.
- 서브넷팅
- 네트워크 성능을 향상시키기 위해, 자원을 효율적으로 분배하는 것을 서브네팅이라고 한다.
- 여기서 말하는 자원을 효율적으로 분배한다는 것은 네트워크 영역과 호스트 영역을 분할하는 것으로 생각하면 된다.

- TCP/IP 프로토콜
- 인터넷 프로토콜 중 가장 중요한 역할을 하는 TCP와 IP의 합성어로 인터넷 동작의 중심이 되는 통신규약이다.
- 데이터의 흐름 관리, 데이터의 정확성 확인(TCP 역할), 패킷을 목적지까지 전송하는 역할(IP 역할)을 담당한다.
- `IP`는 데이터를 한 장소에서 다른 장소로 옮겨주는 역할을 하며, `TCP`는 전체 데이터가 잘 전송될 수 있도록 데이터의 흐름을 조절하고 성공적으로 상대편 컴퓨터에 도착할 수 있도록 보장하는 역할을 한다.
- TCP/IP는 응용 계층, 트랜스포트 계층, 인터넷층, 네트워크 인터페이스 층의 4개 계층으로 구성되어 있다.
- 응용 계층
- 사용자 응용 프로그램으로부터 요청을 받아서 이를 적절한 메시지로 변환하고 하위 계층으로 전달하는 기능을 담당한다.
- 트랜스포트 계층
- IP에 의해 전달되는 패킷의 오류를 검사하고 재전송을 요구하는 등의 제어를 담당하는 계층으로 TCP, UDP 두 종류의 프로토콜이 사용된다.
- 인터넷 층
- 전송 계층에서 받은 패킷을 목적지까지 효율적으로 전달하는 것만 고려한다.
- 데이터그램이 가지고 있는 주소를 판독하고 네트워크에서 주소에 맞는 네트워크를 탐색, 해당 호스트가 받을 수 있도록 데이터그램에 전송한다.
- 네트워크 인터페이스 층
- 특정 프로토콜을 규정하지 않고, 모든 표준과 기술적인 프로토콜을 지원하는 계층으로서 프레임을 물리적인 회선에 올리거나 내려받는 역할을 담당한다.

- TCP/IP vs OSI 7계층
- 공통점
- 다양한 서비스 기능을 가진 응용 프로그램 계층이 존재하고, 전송계층 / 네트워크 계층과 호환하는 계층이 존재한다.
- 차이점
- TCP/IP 프로토콜의 응용 계층은 OSI 참조모델의 표현계층과 세션계층을 포함하며, TCP/IP 프로토콜은 물리계층과 데이터링크계층을 하나로 취급한다는 점이다.

## 운영체제

- 부팅
- 프로세스와 스레드
- (참고)https://charlezz.medium.com/process%EC%99%80-thread-%EC%9D%B4%EC%95%BC%EA%B8%B0-5b96d0d43e37
- 프로그램
- 어떤 작업을 하기 위해 실행할 수 있는 파일 또는 프로그램
- 프로세스
- 메모리에 적재되고 CPU 자원을 할당받아 프로그램이 실행되고 있는 상태
- 운영체제(OS)는 여러 프로세스(프로그램)를 실행하고 관리할 수 있다. 이것을 멀티 태스킹이라고 한다.
- Context Switching(문맥 교환)
- 멀티태스킹이라 함은 여러 프로세스가 동시에 실행되고 관리 되는 것처럼 보이지만, 사실 CPU는 한번에 한가지 명령어밖에 처리하지 못한다. 즉, 동시가 아닌 재빠르게 프로세스들을 번갈아가며 실행하고 관리하는 것이 동시에 하는 것처럼 보일 뿐이다.
- Context Switching은 운영체제의 CPU 자원을 할당하는 스케줄러(Scheduler)에 의해 발생한다. CPU를 적절하고 효율적으로 사용할 수 있도록 하는 작업을 스케줄링이라 한다.

- CPU 스케줄러
- 스케줄러는 레디 큐에 존재하는 프로세스들을 특정한 우선 순위를 기반으로 CPU를 할당받게 해주는 역할을 한다. 스케줄링의 목적은 3가지로 표현할 수 있다.
- 1. CPU를 최대한 활용하기
- 2. 대기 시간을 최소화 하기
- 3. 처리량을 최대화 하기
- 스케줄링은 멀티 태스킹 작업을 만들어내는 데에 있어서 핵심적인 개념이다.
- 스케줄링을 구현하는데 있어, 반드시 자료구조의 구현이 따른다. 어떤 자료구조를 이용하는지가 스케줄링에 중요한 요소이다. 대표적으로 Linked List, Hash List, Bitmap, Red-Black Tree 등이 있다.
- 스케줄링을 구현하는 알고리즘에 따라 스케줄링 종류가 또 나뉜다.
- 1. FCFS : First Come, First Serve의 약자로, 선착순 알고리즘이다. 먼저 도착한 프로세스를 처리하는 스케줄링이다.
- 2. SJF : Shorted Job First의 약자로, 최단 작업을 우선하는 스케줄링이다.
- 3. Priority Scheduling : 미리 주어진 프로세스의 우선 순위에 따라서 스케줄링하는 방식이다.
- 4. RR : Round Robin, 정해진 시간에 주어진 만큼 프로세스를 할당한 뒤 작업이 끝난 프로세스는 레디큐의 가장 마지막에 가서 재할당을 기다린다. (== 컴퓨터 자원을 사용할 수 있는 기회를 프로세스들에게 공정하게 부여하기 위한 방법으로서, 각 프로세스에 일정시간을 할당하고, 할당된 시간이 지나면 그 프로세스는 잠시 보류한 뒤 다른 프로세스에게 기회를 주고, 또 그 다음 프로세스에게 하는 식으로, 돌아가며 기회를 부여하는 운영방식이다.)
- 5. Multilevel-Queue : 레디큐를 여러 개의 큐로 분류하여 각 큐가 각각 다른 스케줄링 알고리즘을 가지는 방식
- 6. Multilevel-Feedback-Queue : Multilevel-Queue는 특정 프로세스가 큐에 고정되어 있지만, Multilevel-Feedback-Queue는 큐와 큐 사이에 프로세스가 이동하는 것을 허용한다.

- PCB와 프로세스 상태
- 프로세스 제어 블록(Process Control Block, PCB)은 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는 운영체제 커널의 자료 구조이다.
- PCB가 필요한 이유는 바로 Context Switching 때문이다. CPU가 여러 프로세스를 빠르게 번갈아가면서 작업하기 위해서는 프로세스에 대한 정보 및 상태를 저장/복원할 필요가 있다.
- 운영체제에 따라 PCB에 포함되는 항목이 다를 수 있지만, 일반적으로 다음과 같은 정보가 포함된다.
- 프로세스 식별자 (PID ; Process ID)
- 프로세스 상태 (Process State)
- 프로그램 계수기 (Program Counter)
- CPU 레지스터 및 일반 레지스터
- CPU 스케줄링 정보
- 메모리 관리 정보
- 프로세스 계정 정보
- 입출력 상태 정보
- 프로세스 상태 그림 
- 프로세스는 다음과 같은 생명 주기를 갖는다.
- new : 프로세스가 생성되는 상태
- ready : 프로세스가 CPU에 할당되어, 처리되기를 기다리는 상태
- running : 프로세스가 CPU에 할당되어, 명령어들이 실행되는 상태
- waiting : 어떤 이벤트의 발생으로 인해 프로세스가 기다리는 상태
- terminated : 프로세스가 종료되는 상태
- 프로세스간 Context Switching 그림 
- 두 프로세스 P0, P1이 있다고 가정한다. P0은 Running(실행중)인 상태, P1은 Ready(대기) 상태이다. 이 상태에서 interrupt 또는 시스템 콜이 발생하면 P0은 Running이 아닌 Ready 상태로 전환된다. 추후 복원될 P0을 위해 해당 프로세스 정보를 PCB에 담아 저장한다. P1은 이전에 저장한 PCB로부터 상태를 복원하여 작업을 계속 수행한다. P1도 어느 시점이 되면 다시 Ready 상태가 되어 PCB에 상태를 담아 저장하고, P0가 PCB로부터 복원되어 작업을 계속 수행한다.
- 이러한 과정을 Context Switching이라고 한다. Context Switching도 메모리에 I/O를 하는 작업이기 때문에 실행되는 프로세스의 수가 많거나, Context Switching의 빈번한 발생은 Overhead를 발생시켜 성능 저하의 결과를 가져온다.
- 메모리 영역
- 여러 프로세스를 관리하는 운영체제의 모습을 도식화한 그림 
- 위 그림과 같이 하나의 프로세는 독립된 메모리 영역( Code, Data, Stack, Heap)을 할당받는다.
- 코드(Code) 영역
- 코드 영역은 실행할 프로그램의 코드 및 매크로 상수가 기계어 형태로 저장되는 영역이다. CPU는 코드 영역에 저장된 명령어를 하나씩 처리한다.
- 데이터(Data) 영역
- 데이터 영역은 코드에서 선언한 전역 변수와 정적(Static) 변수가 저장되는 영역이다. 데이터 영역은 프로그램의 시작과 함께 할당되어 종료될 때 소멸된다.
- 스택(Stack) 영역
- 스택 영역은 함수 안에서 선언된 지역변수, 매개변수, 리턴 값, 등이 저장되고 함수 호출 시 기록하고 종료되면 제거한다. 스택이라는 자료구조 명칭에서도 알 수 있듯이 후위선출(LIFO) 메커니즘을 따른다.
- 힙(Heap) 영역
- 힙 영역은 관리가 가능한 데이터 이외의 다른 형태의 데이터를 관리하기 위한 공간(Free Space)이다. 이 공간은 동적 메모리 할당 공간이므로 사용이 끝나면 운영체제가 쓸 수 있도록 반납해야 한다. 프로그램이 실행하는 순간 프로그램이 사용할 메모리 크기를 고려하여 메모리의 할당이 이루어지는 데이터 또는 스택과 같은 정적 메모리 할당과는 대조적이다. 동적 메모리 할당은 어느 시점에 어느 정도의 공간을 할당할 수 있을지 정확하게 예측할 수 없으므로, 런타임에 확인가능하다.

- IPC ( Inter-Process Communication)
- 안드로이드의 Parcelable을 통해 IPC 하는 그림 
- 각 프로세스는 별도의 공간에서 실행되기 때문에, 한 프로세스에서 다른 프로세스의 메모리 영역에 접근할 수 없다. 만약 프로세스가 다른 프로세스 자원에 접근하려면 IPC(Inter-Process Communication)를 사용해야 한다.
- IPC란 운영체제 상에서 실행 중인 프로세스 간에 정보를 주고받는 것을 말한다. 프로세스는 자신에게 할당된 메모리 내의 정보만 접근할 수 있는데, 이는 안정성을 위해 운영체제에서 자기 프로세스의 메모리만 접근하도록 강제하고 있다는 것이다.
- IPC의 종류로는 메일슬롯, 파이프, 소켓, 시그널, 공유메모리 등이 있다. 안드로이드에서는 대표적인 IPC의 예가 Parcelable이다. 이외에도 AIDL과 같은 서비스 바인딩 등이 있다.

- 쓰레드
- 어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위를 말한다. 일반적으로 하나의 애플리케이션(프로그램)은 하나 이상의 프로세스를 가지고 있고, 하나의 프로세스는 하나 이상의 스레드를 갖는다. 즉, 프로세스를 생성하면 기본적으로 하나의(메인) 스레드가 생성되는 셈이다.
- 시간에 따른 프로세스와 스레드의 흐름 그림 

- 프로세스 vs 쓰레드
- 메모리 관점에서 본 프로세스와 스레드 그림 
- 프로세스는 실행될 때 운영체제로부터 각각 독립된 메모리 영역을 할당받는다. 스레드는 한 프로세스 내에서 동작되는 흐름으로 프로세스 내에서 Stack 영역만 별도로 할당 받고, 부모 프로세스의 Code, Data, Heap 영역은 공유한다. 즉, 프로세스내에서 자식 스레드들은 서로 주소 공간이나 자원들을 공유하면서 실행될 수 있다.

- 멀티 프로세스 vs 멀티 쓰레드
- 멀티 프로세스
- 멀티 프로세스란 하나의 애플리케이션을 여러 개의 프로세스로 구성하여 각 프로세스가 하나의 작업을 처리하도록 하는 것이다.
- 멀티프로세스 그림 
- 1. 안정성이 좋다. 여러 개의 자식 프로세스 중 하나에 문제가 발생해도, 다른 자식 프로세스에 영향이 확산되지 않는다.
- 2. 구현이 비교적 간단하다. 각 프로세스들이 독립적으로 동작하며 자원의 서로 다르게 할당된다.
- 3. 프로세스 간 통신을 하기 위해서는 IPC를 통해야 한다.
- 4. 메모리 사용량이 많다.
- 5. 스케줄링에 따른 Context Switch가 많아지고, 성능 저하의 우려가 있다.
- 멀티 스레드
- 멀티 스레드란 하나의 애플리케이션을 여러 개의 스레드로 구성하여 하나의 스레드가 하나의 작업을 처리하도록 하는 것이다. 일반적으로 멀티스레드를 사용하는 이유는 사용자와 상호작용하는 애플리케이션에서 단일 스레드로 Network 또는 DB와 같은 긴 작업(Long-runnig task)을 수행하는 경우 해당 작업을 처리하는 동안 사용자와 상호작용이 불능인 상태가 될 수 있기 때문이다.
- 멀티 스레드 그림 
- 위 그림을 보면 두 개의 스레드가 서로에게 방해주지 않고, 각자 할일을 한다.
- 1. 응답성이 좋다. 프로그램의 일부분(자식 스레드)이 오류 또는 긴 작업으로 인해 중단되어도 프로그램이 계속적으로 수행된다.
- 2. 자원 공유가 쉽다. 스레드들은 부모 프로세스의 자원과 메모리를 공유할 수 있다.
- 3. 프로세스를 할당하는 것보다 스레드를 할당하는 것이 비용이 적다.
- 4. 멀티프로세서 구조에서 각각의 스레드가 다른 프로세서에서 병렬로 수행될 수 있다.
- 5. 구현 및 테스트, 디버깅이 어렵다.
- 6. 너무 많은 스레드 사용은 오버헤드를 발생시킨다.
- 7. 동기화 그리고 교착상태가 발생하지 않도록 주의해야 한다.
- 8. 자식 스레드 중 하나에 문제가 생긴 경우 전체 프로세스에 영향을 줄 수 있다.
- 멀티프로세스와 멀티 스레드의 비교
- 멀티 스레드는 멀티 프로세스에 비해 상당한 이점을 가지는 반면 위험 부담도 따른다. 그 이유를 알아보자.
- 자원의 효율성 증대
- 멀티 프로세스로 실행되는 작업을 멀티 스레드로 실행할 경우 프로세스를 생성하여 자원을 할당하는 비용이 적고, 스레드는 프로세스 내의 메모리를 공유하기 때문에 독립적인 프로세스와 달리 스레드 간 데이터를 주고 받는 것이 간단해지고 시스템 자원 소모가 줄어든다.
- 응답 시간 단축 및 처리 비용 감소
- 프로세스간 IPC를 사용하여 통신하는 것은 상대적으로 비용이 크다. 하지만 스레드는 프로세스의 메모리 영역을 공유하여 스레드 간의 통신 비용이 적게 든다. 또한 프로세스간의 Context Switching은 느린 반면 쓰레드간의 Context Switching은 빠른데, 그 이유는 Context Switching 시 스레드는 Stack 영역만 처리하면 되기 때문이다.
- 멀티 스레드의 안정성 문제
- 여러 개의 스레드가 동일한 데이터 공간(Critical Section)을 공유하면서 이들을 수정한다는 점에 필연적으로 생기는 문제이다. 멀티 프로세스의 프로그램은 문제가 생기면 해당 프로세스가 중단되거나 중단 시키고 다시 시작하면 된다. 하지만 멀티 스레드 방식의 프로그램에서는 하나의 스레드가 자신이 사용하던 데이터 공간을 망가뜨린다면, 해당 데이터 공간을 공유하는 모든 스레드를 망가뜨릴 수 있다.
- Critical Section : 임계 구역(critical section) 또는 공유 변수 영역은 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원(자료 구조 또는 장치)을 접근하는 코드의 일부를 말한다.

- 스케줄링
- 그림 

- (참고) https://namu.wiki/w/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%20%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81
- 개요
- 여러 프로세스를 처리할 때, 한 프로세스가 모든 작업이 끝날때까지 기다렸다가 다음 프로세스를 실행하는 방법보다 **한 프로세스를 실행 가능한 시점까지 실행하고, I/O 등 CPU를 사용하지 않는 작업을 할 때는 다른 프로세스를 실행**하는 일종의 기술이다.
- 운영체제는 준비 큐(Ready Q), 대기 큐(Waiting Q) 등의 자료구조를 두어 이들 프로세스를 관리한다. 준비 큐는 준비 상태에 있는 프로세스들을 모아놓은 큐이다. 운영체제는 CPU 스케줄러를 통해 준비 큐에 있는 프로세스 중 한 프로세스를 골라 다음에 실행시킨다.
- 프로세스 스케줄링은 4가지 경우에 일어날 수 있다.
- 1. 프로세스가 실행 상태(running)에서 대기 상태(waiting)으로 전활될 때
- 2. 프로세스가 실행 상태(running)에서 준비 상태(ready)로 전활될 때
- 3. 프로세스가 대기 상태(waiting)에서 준비 상태(ready)로 전환될 때
- 4. 프로세스가 종료되었을 때(terminated)
- 프로세스 스케줄링이 첫 번째와 네 번째 경우에만 일어난다면 이를 비선점 스케줄링이라 한다. 비선점 스케줄링에서는 프로세스가 대기 상태에 들어가거나 종료되지 않고서는 프로세스 전환이 일어나지 않는다.
- 프로세스 스케줄링이 위의 네 가지 경우 모두에 일어난다면 이를 선점 스케줄링이라 한다. 선점 스케줄링에서는 운영체제가 프로세스에 할당되었던 CPU를 자체적으로 판단하여 뺏어올 수 있다.
- 선점 스케줄링과 비선점 스케줄링은 이름 때문에 헷갈릴 수 있다. '선점(먼저 차지)'이 작업이 다 끝날때까지 반환하지 않는것처럼 들린다. 하지만 이것은 비선점 스케줄링의 특징이다. 선점 스케줄링은 운영체제가 CPU를 먼저 '선점(preemptive)'하여 필요하다면 CPU를 프로세스로부터 뺏을 수 있는 스케줄링 방법이고 비선점은 그 반대로 이해하면 좋다.
- 선점형 스케줄링
- 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식
- 비교적 응답이 빠르다는 장점이 있지만, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드를 초래한다.
- 실시간 응답환경, Deadline 응답환경 등 우선순위가 높은 프로세스를 빠르게 처리해야 할 경우에 유용하다.
- RR(라운드 로빈), SRTF(Shortest Remaining Time First), 다단계 큐 스케줄링(MLQ, MultiLevel Q), 다단게 피드백 큐 스케줄링(MLFQ), Priority Q
- 비선점형 스케줄링
- 하나의 프로세스가 CPU를 차지하고 있을 때, 프로세스가 끝날때까지 CPU를 빼앗기지 않는다.
- FCFS(First Come First Served), SJF(Shortest Job First, 비선점형 => SJF, 선점형 => SRTF), Priority Q
- 프로세스 동기화
- 프로세스 사이에 데이터 혹은 흐름에 대한 동기화 하는 것을 프로세스 동기화(Process Syncronization)라고 한다. (현재에는 대부분 쓰레드 기준으로 스위칭을 하므로, Thread Syncronization으로 많이 불린다.)
- 주로 공통변수(Common Variable)에 대한 동시 업데이트에서 동기화 이슈가 일어난다.
- 이를 해결하는 방법은 공통 변수에 접근하는 쓰레드는 하나만 접근하도록 관리해야 한다. 이러한 공통변수 구역을 "임계구역" 이라한다.
- 임계구역
- 임계구역은 여러 개의 쓰레드가 수행되는 시스템에서 각 쓰레드들이 공유하는 데이터(변수, 테이블, 파일 등)를 변경하는 코드 영역을 말한다.
- 이를 해결하기 위해서는 3가지 조건이 만족해야 한다.
- 1. Mutual exclusion( 상호 배타) : 오직 한 쓰레드만이 진입 가능하다. 한 쓰레드가 임계구역에서 수행 중인 상태에서는 다른 쓰레드는 절대 이 구역에 접근할 수 없다.
- 2. Progress(진행) : 한 임계구역에 접근하는 쓰레드를 결정하는 것은 유한 시간 이내에 이루어져야한다.
- 3. Bounded waiting(유한대기) : 임계구역으로 진입하기 위해 대기하는 모든 쓰레드는 유한 시간 이내에 해당 임계구역으로 진입할 수 있어야 한다.
- 프로세스 / 쓰레드 동기화
- 프로세스 (쓰레드) 동기화를 통해 이루고자 하는 목적은 다음과 같다.
- 원하는 결과값을 도출하도록 임계구역 문제를 해결한다.
- 프로세스의 실행 순서를 원하는대로 제어한다.
- Busy wait 등과 같은 비효율성을 제거한다.
- 세마포어(Semaphore)
- 세마포어는 동기화를 위해 만들어진 소프트웨어이다. 공유된 자원의 데이터 혹은 임계 영역 등에 여러 Process 혹은 Thread가 접근하는 것을 막아준다. (즉, 동기화 대상이 하나 이상)
- 세마포어로 뮤텍스(Mutual exclusion의 줄임말)를 구현할 수 있고, 뮤텍스로 세마포어를 구현할 수 있다. 세마포어는 동시에 여러 개의 프로세스/스레드가 임계 구역에 접근할 수 있도록 카운트를 가지고 있는데 카운트가 1인 특별한 세마포어가 뮤텍스이다.
- 상호 배제의 원리를 보장하는 알고리즘이다.
- 세마포어는 P연산과 V연산을 이루어진다.
- 
- 뮤텍스 (Mutex)
- 뮤텍스는 Key에 해당하는 어떤 오브젝트가 있으며, 이 오브젝트를 소유한 (프로세스, 스레드)만이 공유자원(Critical section)에 접근할 수 있다.

- 교착 상태 (DeadLock)
- 교착상태는 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미한다.
- 
- 교착 상태가 발생하기 위해서는 네가지 조건이 충족되어야 한다. 네가지중 하나라도 충족되지 않으면 교착상태가 발생하지 않는다.
- 1. 상호배제(Mutual Exclusion)
- 한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
- 2. 점유와 대기(Hold and Wait)
- 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
- 3. 비선점 (Non-preemption)
- 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야한다.
- 4. 환형 대기 (Circular wait)
- 공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.
- 교착 상태가 발생하지 않도록 해결하는 방법은 4개가 있다.
- 1. 예방 기법 (Prevention)
- 교착상태 예방 기법은 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로 교착상태 발생의 네가지 조건 중에서 어느 하나를 제거함으로써 수행된다. 자원낭비가 가장 심한 기법이다.
- 1. 상호 배제(Mutual Exclusion) 부정 : 한번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
- 2. 점유 및 대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.
- 3. 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
- 4. 환형 부정 : 자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 하는 것이다.
- 2. 회피 기법 (Avoidance)
- 교착상태 회피 기법은 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법으로, 주로 은행원 알고리즘이 사용된다.
- 
- 3. 발견 기법 (Detection)
- 교착상태 발견 기법은 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미한다.
- 1. 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다.
- 4. 회복 기법 (Recovery)
- 교착상태 회복 기법은 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미한다.
- 프로세스 종료
- 교착상태에 있는 프로세스를 종료하는 것으로, 교착상태에 있는 모든 프로세스를 종료하는 방법과 교착상태에 있는 프로세스들을 하나씩 종료해가며 교착상태를 해결하는 방법이 있습니다.
- 자원선점
- 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법이다. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점합니다.
- 

- 물리 메모리 관리

- 가상 메모리 관리
- https://copycode.tistory.com/113 (참고)
- 메인 메모리의 크기가 한정되어 있으므로 물리적인 메모리 크기보다 크기가 큰 프로세스를 실행시킬 수 없다. 그렇다면 메인 메모리보다 크기가 큰 프로세스를 실행시키고 싶으면 어떻게 해야 할까? 단순히 메인 메모리가 더 큰 컴퓨터를 사용해야 하는가? 이런 방법은 매우 비효율적일 것이다. 그래서 나온 방법이 바로 "가상 메모리"이다.
- 프로세스는 `필요한 부분만 메모리에 올림으로써 메인 메모리에 올라가는 프로세스의 크기`를 줄인다. 프로세스 이미지를 모두 메모리에 올릴 필요가 없다. 동적 적재와 비슷하다.
- 
- 우선 실행하고자 하는 프로세스들을 `페이징` 과정을 먼저 실행한다.
- 페이징 : 프로세스를 일정 크기인 페이지로 잘라서 메모리에 적재하는 방식. ( 외부단편화 해결, 내부 단편화 존재)
- 메모리 단편화 : RAM에서 메모리 공간이 작은 조각으로 나뉘어져 사용가능한 메모리가 충분히 존재하지만 할당(사용)이 불가능한 상태를 보고 메모리 단편화가 발생했다고 한다.
- 내부 단편화 : 메모리를 할당할 때 프로세스가 필요한 양보다 더 큰 메모리공간이 할당되어서 프로세스에서 사용하는 메모리 공간이 낭비 되는 현상
- 외부 단편화 : 메모리가 할당 및 해제 작업의 반복으로 작은 메모리가 중간중간에 사용하지 않는 메모리로 존재하여 총 메모리 공간은 충분하지만 실제로 할당할 수 없는 상황.
- 여러 공간이 여러 조각으로 나뉘는 현상.
- 메인 메모리의 `외부 단편화` 문제를 해결하여 메모리 낭비를 줄이는 데 `페이징`을 사용하면 매우 효율적이기 때문이다. 따라서 페이징 과정을 거쳐 특정 단위인 페이지 단위로 프로세스를 자른다. 그러면 페이지들마다 필요한 부분과 필요 없는 부분으로 나눌 수 있다. 여기서 "필요한 페이지만 메모리에 적재"를 하면 많은 메모리의 낭비를 막고 우리가 필요한 프로세스들을 모두 메인 메모리에서 실행을 시킬 수 있게 되는 것이다. 이를 `요구 페이징`이라고 한다.
- 요구 페이징(Demand Paging)
- `요구 페이징`은 프로세스의 이미지를 backing store에 저장한다. backing store는 swap device로 하드웨어의 부분이다. "페이지를 임시로 보관하는 공간이다." 프로세스는 페이지의 조합이기 때문에 필요한 페이지만 메모리에 올린다. 이를 요구되는 페이지만 메모리에 올린다는 의미로 `요구 페이징`이라고 부른다.
- 
- 페이징 기법을 사용할 때 페이지 테이블이라는 부분을 놔두게 된다. `MMU`의 재배치 레지스터를 통해 논리 주소를 물리 주소로 바꾸어주는 주소 변환 과정을 거쳐, CPU가 프로세스는 연속적으로 할당되어져 있다고 속게 만드는 작업을 한다.
- MMU : 메모리 관리 장치 (Memory Management Unit)는 CPU가 메모리에 접근하는 것을 관리하는 컴퓨터 하드웨어 부품이다. 가상 메모리 주소를 실제 메모리 주소로 변환하며, 메모리 보호, 캐시 관리, 버스 중재 등의 역할은 담당한다.
- 그런데 요구 페이징 기법을 사용하면 페이지가 메모리에 올라와 있는 것도 있고 올라가지 않고 backing store에 보관되어 있는 것도 존재한다. 따라서 페이지 테이블을 작성할 때, 이를 구분해줄 도구가 필요하다. 그래서 `Valid 비트 필드`를 페이지 테이블에 추가한다. 1과 0의 값으로 메모리에 적재되어 있는지 없는지를 구분할 수 있다.
- 만약 오류가 발생한다면 오류를 제어할 수 있는 코드를 실행해야한다. CPU에서 해당 메모리를 가져오라고 논리 주소를 보냈는데 페이지 테이블에서 접근하려는 페이지가 메모리에 없다고 표시되어 있다.
- 이는 `Valid 비트 필드`에 의해서 결정된다. 그러면 Backing store에 해당 페이지를 가져와야한다. 이를 수행하기 위해서 CPU는 잠시 하는 일을 멈추고 운영체제가 나서서 Backing Store를 뒤져 필요한 페이지를 메모리에 적재하게 된다. 그리고 `valid 비트`를 올라와 있다고 바꾸어 준다. 이런 현상을 `페이지 결함`, `페이지 부재(Page Fault)`라고 부른다.
- 
- 요구 페이징을 할 때, 두 가지의 종류가 있다. (1)처음부터 모든 페이지를 적재시키지 않고 CPU가 요구할 때 valid를 바꾸어 페이지를 적재하는 방법과 (2) 우선 필요할 것 같은 페이지를 적재시키고 필요할 때 다른 페이지를 적재시키는 방법이 있다. (1)은 pure demand paging이고 (2)는 prepaging이다. (1) 기법을 사용하면 페이지를 요구할 때만 메모리에 적재하므로 메모리의 낭비는 매우 줄일 수 있다. 하지만 요구에 의해 앞선 페이지 부재의 현상을 처리하려고 하면 많은 부담이 발생한다. 이에 반해 미리 올라와져 있는 (2) 기법은 처리하는 속도는 빠르지만 메모리가 낭비될 수 있다.

- 세그멘테이션(segmentation)
- 프로세스를 물리적인 단위인 페이지 말고 논리적 내용 단위인 세그먼트로 자를 수 있는 세그먼 테이션 방법이있다. 세그먼테이션은 다른 크기로 잘라서 보관하는 것이다.
- 세그멘테이션은 프로세스를 세그먼트의 집합으로 생각한다. 세그먼테이션은 물리적인 크기의 단위가 아닌 논리적 내용의 단위(의미가 같은)로 자르기 때문에 세그먼트들의 크기는 일반적으로 같지 않다.
- 프로세스를 어떻게 자르는가에 대한 방법 빼고 메모리에 할당하는 방법에 대해서는 페이징과 방법이 같다. MMU 내의 재배치 레지스터를 이용하여 논리 주소를 물리 주소로 바꾸어 주는 방식을 취한다. MMU는 세그먼트 테이블로 CPU에서 할당한 논리 주소에 해당하는 물리 주소의 위치를 가지고 있다. 이 방법을 이용하면 CPU는 프로세스가 연속된 메모리 공간에 위치한다고 착각한다.
- 
- 주소를 변환하는 방법 역시 같다. 하지만 논리 주소에서 보내는 주소 값에서 하위 변위 비트를 제외한 앞의 비트들은 페이징 번호가 아니라 세그먼트 번호가 되는 것이다. 따라서 논리 주소는 세그먼트 번호와 변위 비트로 이루어져 있게 된다.
- 세그먼테이션의 경우에도 보호와 공유의 기능을 수행하고 있다. 모든 논리 주소들은 세그먼테이션 테이블을 경우하게 되므로 세그먼트 테이블 엔트리마다 r,w,x 비트를 만들어 해당 세그먼트에 대한 접근 제어를 가능하게 해준다. 또한 같은 프로그램을 사용하는 복수 개의 프로세스가 있다면 메모리에 하나만 적재하여 프로세스의 세그먼트 테이블 코드 영역이 같은 곳을 가리키게 만든다. 그러면 위와 같은 기능이 페이징의 기법보다 더 좋다고 말할 수 있다. 페이징은 프로세스를 같은 단위로 자르게 되므로 중요한 부분과 중요하지 않은 부분이 같은 페이지 안으로 잘라질 수 있다. 하지만 세그먼트는 논리적인 내용 측면으로 자를 수 있기 때문에 중요 여부에 대해서 자를 수 있다. 이렇게 되면 보호와 공유의 기능이 더 수월해진다.
- 그러면 세그먼테이션만 사용하면 될 것 같지만 이 또한 단점을 가지고 있다. 세그먼트는 크기가 고정되어 있지 않고 가변적이다. 크기가 다른 각 세그먼트를 메모리에 두려면 동적 메모리 할당을 해야 한다. 앞에서 말한 `외부 단편화`가 발생할 수 있다. 외부 단편화는 메모리 낭비를 매우 크게 발생시킨다.
- 두 방식 모두 장단점을 가지고 있으니 장점만을 가져오면 좋은 방법이 될 수 있다. `세그먼테이션`과 `페이징`기법을 모두 사용한다. 세그먼테이션은 보호와 공유 면에서 효과적이고 페이징은 외부 단편화 문제에 효과적이다. 따라서 "세그먼트를 페이징 하는 방법"을 취한다.
- 
- 프로세스를 처음에 세그먼트 단위로 자른다. 의미 있는 단위로 나누게 되면 보호와 공유를 하는 측면에 이점을 가질 수 있다. 하지만 앞서 말했듯 외부 단편화가 발생할 수 있다. 그래서 우리는 잘라진 세그먼트를 다시 일정 간격인 페이지 단위로 자르는 페이징 방법을 취한다. 그래서 메모리에 적재하면 페이징의 일정 단위로 다시 잘렸기 때문에 외부 단편화가 발생하지 않는다. 하지만 이와 같은 경우에는 테이블을 두 가지 모두 거쳐야 하므로 속도 면에서 조금 떨어질 수 있다.

- 페이지 교체
- https://copycode.tistory.com/117?category=740133 [ITstory]
- 요구 페이징은 요구되어지는 페이지만 backing store에서 가져와 메인 메모리에 적재하는 방법이다. 필요한 페이지만 메인 메모리에 올리므로 메모리의 낭비를 줄이는 방법으로 사용되었다. valid 비트를 추가한 페이지 테이블과 필요하지 않은 페이지를 보관하는 backing store를 가지고 기능을 수행할 수 있다.
- 하지만 프로그램 실행이 계속 진행되게 되면 요구 페이지가 늘어나게 되고 언젠가는 메모리가 가득 차게 될 것이다. 페이지를 backing store에서 가져와 메모리에 올려야 되는데 메모리에 자리가 없는 것이다.
- 이럴 경우 메인 메모리에 있는 특정 페이지를 내보내야할 필요가 있다. 그 자리에 필요한 다른 페이지를 올려야한다. 이를 `페이지 교체`라고 한다.
- 메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 backing store로 몰아내고 그 빈 공간으로 페이지를 가져온다. backing store로 페이지를 몰아내는 것을 `page-out`이라고 하고 반대로 빈 공간으로 페이지를 가져오는 것을 `page-in`이라고 한다. 여기서 몰아내는 페이지를 `victim page`라고 말한다. 말 그대로 희생양 페이지라는 것을 의미한다.
- 
- 페이지의 교체하기 위해서는 특정 페이지를 몰아내는 page-out으로 희생양 페이지를 만들어야한다. 그러면 어떤 페이지를 victim page를 만들어야 되는가를 선정해야한다. 만약 페이지를 backing store로 몰아낼 때 페이지에 명령에 수정이 일어나지 않았으면 우리는 page-out 과정에서 수정을 할 필요가 없다. 하지만 명령에서 수정이 일어났다면 하드디스크에 저장하기 위해 수정하는 작업이 필요하다.
- 따라서 두 가지의 경우에는 page-out 과정에서 발생하는 시간이 다르다. 수정이 필요하지 않으면 몰아내는 과정만 진행하면 되지만 수정이 필요한 경우에는 수정하는 작업의 시간이 추가로 발생하게 된다.
- 따라서 시간을 절약하기 위해서 victim page로 수정되지 않은 페이지를 victim으로 선택하는 경우가 많다. 이를 위해서는 페이지가 수정이 되었는지 아닌지에 대한 기록이 필요하다. 이를 modified bit(dirty bit)를 만들어 이 값을 통해 수정이 되었는지 아닌지를 판별할 수 있게 한다.

- 입출력 시스템과 저장장치
- https://danidanee.tistory.com/14
- 입출력 버스의 구조
- 현대의 컴퓨터는 CPU와 메모리를 연결하는 `메인버스`, CPU와 그래픽 카드를 연결하는 `그래픽 버스`, `고속 입출력 버스`와 `저속 입출력 버스`를 사용한다.
- 저속 주변 장치
- 키보드 같은 메모리와 주변상치 사이에 오고 가는 데이터의 양이 적어 데이터 전송량이 낮은 장치
- 고속 주변 장치
- 그래픽카드나 하드디스크 같은 메모리와 주변장치 사이에 대용량의 데이터가 오고가서 데이터 전송률이 높은 장치
- 입출력 방법
- 프로세서 제어 입출력
- 프로세서 내부의 입출력 데이터와 주소 레지스터를 입출력 모듈과 연결한 형태
- 데이터 입력
- 입출력 모듈을 거쳐 한번에 한 워드 씩만 데이터 레지스터로 전송, 입출력 데이터 레지스터에서는 프로그램을 이용해 산술 논리 연산장치로 전송
- 데이터 출력
- 산술 논리연산장치에서 입출력 데이터 레지스터로 이동, 프로그램을 이용해 입출력 모듈로 전송
- 폴링 방법
- 상태 비트를 주기적으로 검사해 프로세서보다 상대적으로 느린 입출력장치의 상태를 확인.
- 인터럽트 기반 입출력 방법
- 입출력장치가 작업을 완료한 후에 작업과 관련된 상태와 결과를 메모리에 저장하고 인터럽트를 발생시켜 프로세서에 알림
- 인터럽트를 받은 프로세서는 입출력 명령을 전송하고 입출력 작업 중에 다른 명령 시작
- DMA 입출력 (직접 메모리 접근)
- 프로세서의 도움 없이도 메인 메모리를 직접 제어해 데이터를 전송하는 형태
- CPU의 도움 없이도 메모리에 접근할 수 있도록 입출력 제어기에 부여한 권한으로, 입출력 제어기에는 직접 메모리에 접근하기 위한 DMA 제어기가 마련되어 있다.
- 입출력 제어기는 여러 채널에 연결된 주변 장치로부터 전송된 데이터를 적절히 배분해 하나의 데이터 흐름을 만든다.
- 채널 선택기는 여러 채널에서 전송된 데이터 중 어떤 것을 메모리로 보낼지 결정한다.
- 이렇게 주변장치에서 전송된 데이터는 DMA 제어기를 거쳐 메모리에 올라간다.
- 
- 디스크 관리 장치
- 파티션
- 디스크를 논리적으로 분리하는 방식
- 포메팅
- 디스크 표면을 초기화하는 작업
- 조각모음
- 디스크에 파일을 저장했다 지우기를 반복함으로써 중간중간에 생긴 빈공간을 하나로 모으는 작업.
- RAID
- 자동으로 백업을 하고 장애가 발생하면 이를 복구하는 시스템
- 동일한 규격의 디스크를 여러 개 모아 구성하며 장애가 발생했을 때 데이터를 복구하는 데 사용.
- 여러 대의 물리적 디스크를 하나의 논리적 디스크로 인식하는 기술

- 파일 시스템

## 데이터베이스

- 정규화/비정규화
- 트리거
- 인덱스
- 트랜잭션
- 동시성 제어
- 회복
- sql vs nosql