# 5/26 스터디
## 임태현
### RedBlack Tree
https://zeddios.tistory.com/237
- Binary Search Tree에서 색깔 규칙을 추가한 트리
- Binary Search Tree는 왼쪽 자식이 더 작고 오른쪽 자식이 더 크다.
- Binary Search Tree가 편향 트리가 되면 최악의 경우 순회를 O(n)이 되는 단점을 극복하기 규칙을 추가한 것이다.

#### Rule
1. Root Property: 루트의 색깔은 Black이다.
2. External Property: 모든 Leaf는 Black이다.
- Leaf는 실질적으로 데이터를 갖는 Node가 아니다.
4. Internal Property: Red의 자식 방향으로 연속해서 나올 수 없다.
5. Depth Property: 모든 Leaf의 Black Depth는 같다.

#### 삽입
- Binary Search Tree의 삽입처럼 자리를 찾아 Leaf에 들어간다.
- 처음 Default 색깔은 Red로, 부모와 Double Red일 경우 조정된다.
1. Restructuring
- 삼촌이 Black일 경우
- 자신, 부모, 조부모를 오름차순으로 정렬한 뒤, 중간 값을 부모로, 나머지 자식으로 매단다.
- 이 때 부모는 Black, 자식들은 Red가 된다.
- Restructuring이 일어난 후의 다른 작업은 Chaining되지 않는다. 왜냐하면 Black Depth가 바뀌지 않았기 때문이다.
- 시간복잡도는 O(1)
3. Recoloring
- 삼촌이 Red일 경우
- 부모와 삼촌을 Black으로 만들고 조부모를 Red로 만든다.
- Recoloring 자체의 연산은 O(1)
- Recoloring은 한번의 조정 후 또 다른 Recoloring이나 Restructuring이 일어날 수 있는데, 최악의 상황엔 루트까지 거치므로 O(logn)
- 삽입의 총 시간 복잡도는 Binary Search Tree만의 O(logn) + O(logn) = O(logn)

### Amortized Analysis
- 최악의 경우가 발생하도록 연속된 연산을 수행하고, 연산할 때 그 한번의 연산에 대한 평균수행시간을 분석하는것
- 최선의 상황만 발생하다 아주 가끔씩 최악의 상황이 발생할 때 Asymptotic analysis(점근적 분석)은 최악의 상황으로 복잡도를 수행한다.
- 예를 들어, 거의 O(1)로 연산하는 작업이 가끔 O(n) 연산을 해도 점근적 분석 방법으론 O(n)이 된다.
- 최악의 경우를 발생시키는 한 번의 연산에 대한 평균 비용(Amortized Cost)을 구함

Amortized Cost = actual cost + accounting cost

#### Array Doubling
- 크기 n의 Array가 있다고 가정
- push를 기본 연산으로 적용해 연산 시간을 1로, 원소를 옮기는 시간을 t로 설정
- actual cost: 당장 필요한 에너지
- ArrayDoubling이 일어난 경우: 1+tn
- ArrayDoubling이 일어나지 않은 경우: 1
- accounting cost: 피로 누적도
- ArrayDoubling이 일어난 경우: -tn+2t-1
- 2t-(tn+1)
- 2t가 ArrayDoubling에 대한 보험인데, 이유는 아래에 있는 ArrayDoubling이 일어나지 않는 경우에 서술했음
- -(tn+1)은 actual cost에 필요한 연산 수로 쌓아둔 비용에서 빼낼 필요가 있음
- ArrayDoubling이 일어나지 않은 경우: 2t
- ArrayDoubling이 일어난다고 가정했을 때 당장 옮기는 시간 tn+1만큼 시간이 필요하다.
- 여기서, n을 2n으로 늘린 상황인데, n 또한 n/2 크기에서 늘린 결과이고 이것들이 재귀적으로 쌓아진 결과이다.
- (tn + tn/2 + tn/4 + tn/8 + .... + 1) = 2tn
- 즉, 전체 상황을 놓고 따졌을 때 2tn의 비용이 든 것이다.
- 그래서 최악의 상황에서의 비용 2tn을 n+1번째 원소를 넣는 기회만큼 수를 나눈 것이다.
- 2tn/(n+1) = 2t
- 즉, ArrayDoubling이 일어난 경우는 (1+tn) + (-tn+2t-1) = 2t = O(1)
- ArrayDoubling이 일어나지 않은 경우는 (1) + (2t)
- 최종적으로 1+2t가 ArrayDoubling에 대한 Amortized Cost이다.

## 최지수

### 프로세스란?
프로그램이 메모리에 적재되면 프로세스가 된다. 실행 중인 프로그램

운영체제로부터 주소 공간, 파일, 메모리 등을 할당받으며 이것들을 총칭하여 프로세스라고 한다.

CPU는 한 순간에 하나의 프로세스만 실행할 수 있는데 빠르게 프로세스를 교체하고 있기 때문에 동시에 실행되는 것 처럼 느낀다.

### 프로세스 제어 블록PCB
프로세스에 대한 정보는 프로세스 제어 블록(PCB, Process Control Block)에 저장된다.
운영체제는 프로세스를 관리하기 위해 프로세스의 생성과 동시에 고유한 PCB 를 생성한다.

프로세스는 CPU 를 할당받아 작업을 처리하다가도 프로세스 전환이 발생하면 진행하던 작업을 저장하고 CPU 를 반환해야 하는데, 이때 작업의 진행 상황을 모두 PCB 에 저장하게 된다. 그리고 다시 CPU 를 할당받게 되면 PCB 에 저장되어있던 내용을 불러와 이전에 종료됐던 시점부터 다시 작업을 수행한다.

*PCB 에 저장되는 정보*
- 프로세스 식별자(Process ID, PID) : 프로세스 식별번호
- 프로세스 상태 : new, ready, running, waiting, terminated 등의 상태를 저장
- 프로그램 카운터 : 프로세스가 다음에 실행할 명령어의 주소
- CPU 레지스터
- CPU 스케쥴링 정보 : 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등
- 메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함
- 입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록
- 어카운팅 정보 : 사용된 CPU 시간, 시간제한, 계정번호 등

### 프로세스 관리
운영체제는 프로세스의 상태를 실행, 준비, 블록 상태로 나눈다.

사용자가 프로그램을 실행하면 프로세스가 생성되고 준비리스트에 추가된다. 그 다음 CPU를 할당받으면서 실행 상태가 된다.
이 과정을 디스패칭이라고 하고 디스패처가 이 일을 수행한다.

연산을 하고 CPU를 반납하게 된다. 작업이 끝나지 않으면 다시 준비상태로 돌아간다.

### 스레드란?
프로세스의 처리속도를 높이기 위해 하나의 프로세스가 수행해야 할 여러 작업들을 나누어 수행할 수 있도록 설계된 것이다.

프로세스가 할당받은 자원을 이용하는 실행의 단위

한 프로세스에 존재하는 모든 스레드들은 프로세스의 상태를 공유한다.

스레드는 각각의 스택 영역을 가지고 있는 하나의 함수라고 생각하면 이해가 쉽다.

### 멀티 스레드
하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것을 멀티스레딩이라고 한다.

- 멀티 태스킹
하나의 CPU가 여러 프로세스를 번갈아 가면서 실행하는 것
- 멀티 프로세싱
하나의 프로세스를 여러 개의 CPU를 사용해서 실행
- 멀티 스레드
스레드를 여러 개 만들어서 실행

**장점**
- 작업 처리 시간을 향상시킨다
- 프로세스 내의 모든 데이터가 접근 가능하므로 자원 공유가 번거롭지 않다

**단점**
- 하나의 스레드만 문제가 생겨도 전체 프로세스가 영향을 받는다
- 스레드를 너무 많이 생성하면 스케줄링해야하므로 성능 저하가 발생한다

## 문예지
### Redis
- NoSQL의 일종
- in memory 저장소

> 특징
>
1. 리스트 형식 데이터처리에 특화
- 데이터형으로 string, 리스트, set, sorted set, hash 사용
- 리스트형 데이터 입력과 삭제가 MySQL에 비해 빠름
2. 여러 프로세스에서 동시에 같은 key에 대한 갱신을 요청하는 경우 순차적 처리가 가능한 함수를 제공
3. 메모리를 활용하면서 영속적인 데이터보존
- 명령어로 명시적으로 삭제하거나 만료일을 설정하지 않으면 삭제하지 않음
- 스냅샷 기능을 제공해 메모리 내용을 저장해놨다가 복구 가능
4. 여러대의 서버 구성 가능
5. DB로도 Cache로도 사용 가능
6. 메모리 파편화 발생 가능
- Redis는 싱글 스레드라 스냅샷 생성시 자식프로세스를 만들어 낸 후 새로 변경된 내용을 복사해서 사용
- 실제로 필요한 메모리 양보다 더 많은 메모리를 사용

> Redis-Cluster 구성하기
>
#### master-slave
master-slave 구조로 cluster 구성
**cluster**: 각기 다른 서버를 묶어 하나의 시스템처럼 동작하게 하는 것

- cluster를 master로만 구성하면 노드 중 하나만 장애가 발생하도 해당 노드의 데이터가 유실 :arrow_right: 데이터 수평확장외 장점은 없음 :arrow_right: slave 구축

- Slave를 추가로 구성하면 Master의 내용을 복제하여 가지고 있게 되므로 장애가 나더라도 Slave노드가 Master로 승격 되면서 중단없이 서비스를 제공

- 하나의 서버에 동일한 데이터를 가진 마스터와 슬레이브가 동시에 존재하지 않도록 장비를 구성하는 것이 중요 :arrow_right: 서버 하나가 사망했을때 해당 장비에 Master와 백업본 Slave가 같이 있으면 데이터를 복구할 수 없음

### Express.js
- Node.js 핵심 모듈인 http와 Connect 컴포넌트를 기반으로 하는 웹 프레임워크
- 개발자들이 프로젝트에 필요한 라이브러리를 자유롭게 선택할 수 있음
- MVC 구조 제공

> 작동 방식
>
main 파일이라고 하는 진입점이 존재

1. controller, modle 등 자체 모듈 + 3rd 파티 모듈을 가져옴
2. 템플릿 엔진과 해당 엔진의 확장자와 같은 express.js 앱 설정을 구성
3. 미들웨어 정의
4. 라우팅 정의
5. 데이터베이스 연결
6. 앱 구동

> Express의 바탕
>
- Middleware: function 배열
- 모든 코드를 실행
- 요청 및 응답 오브젝트에 대한 변경을 실행
- 요청-응답 주기를 종료 (res.end())
- 스택 내의 그 다음 미들웨어 함수를 호출 (next())
<br>

- Routing: 미들웨어와 비슷하지만 특정 http method로 특정 url을 방문할 때 호출
- Views: 여러 종류의 view engine 사용 가능
- Extensions to request and response objects: res.redirect, res.sendFile, res.send등 편의를 위한 기능 제공