깃으로 관리되는 폴더 안으로 들어가서 git rm -r --cached . 명령어 입력

git add . 명령어 입력

git commit -m "커밋 내용"

커밋을 하면 아래와 같이 지워진 것을 볼 수 있다.

마지막으로 git push를 통해 마무리

제대로 변경된 모습을 볼 수 있다.

참고

https://adjh54.tistory.com/376#google_vignette

• red black tree (이진 균형 트리) 구조
• 추가/탐색/삭제 : O(logN)
• 코드

  #include <map>
  using namespace std;
  

int main() { map<int, string> m; m.insert({100, "Kim"}); m.insert({200, "Jun"}); m.insert({100, "Lee"});

//중복된 값을 쓰고 싶으면, multimap 써야함
cout << m[100] <<" \n"; //Kim
m[100] = "Leem"; //value값 덮어쓴다.
cout << m[100] << "\n"; //Leem

}

## hash map
* C++ STL에서 unordered_map
* C#에서는 dictionary
* 추가/탐색/삭제 : O(1)
  * 메모리를 더 많이 쓰는 대신 속도가 빠르다.
* 코드 
`unorderd_map<key, value>`
`unordered_multimap<key, value>`
  * unordered_multimap에서는 `[]` operator 사용 불가능
  * `insert` 로 값 넣기
* unordered_map을 순회해서 값을 찾고 싶을때

auto u = um.equal_range(cur); for(auto it = u.first; it != u.second; ++it) { cout<second<<"\n"; }

### cf) hash table
* table
  * O(1)에 추가/탐색/삭제를 할 수 있는 구조
  * 키와 데이터의 쌍으로 구성
  * 그러나 데이터가 너무 커지면, 더이상 효율성이 사라짐
  * 이 문제를 해결하기 위해 hash 사용
* hash
  * 키에 따라 데이터를 넣을 때 충돌된 것을 해결해주는 방법
  * 충돌 방지 기법
    * 선형 조사법
      * 이미 있는 key 값이라면, 한칸 뒤로 밀면서 빈 key값 찾기
    * 이차 조사법
      * 이미 있는 key 값이라면, 제곱값 만큼 밀면서 빈 key값 찾기
    * 체이닝 기법
      * 이미 있는 key 값이라면, 중복된 key값을 가지는 value 넣어주기
* hash 예시 코드

void TestHash() { struct User { int userId = 0; string username; };

vector<User> users;
users.resize(1000);

const int userId = 123456789;
int key = (userId % 1000); //hash 함수를 통해 만든 key

//정보 넣기
users[key] = User{ userId, "Leem" };

//정보 찾기
User& user = users[key];
if (user.userId == userId)
{
    string name = user.username;
    cout << name << "\n";
}  

}

* 체이닝 예시 코드

void TestHashTableChaining() { struct User { int userId = 0; string username; };

vector<vector<User>> users;
users.resize(1000);

const int userId = 123456789;
int key = (userId % 1000); //hash 함수를 통해 만든 key

//정보 넣기
users[key].push_back(User{ userId, "Leem" });
users[key].push_back(User{ 789, "Jun" });


//정보 찾기
vector<User>& bucket = users[key];
for (const auto& user : bucket)
{
    if (user.userId == userId)
    {
        string name = user.username;
        cout << name << "\n";
    }
}

}

### 참고) unordered_map에서 key값으로 pair를 쓰고 싶을 때

struct pair_hash { template<class T1, class T2> size_t operator () (const pair<T1,T2>&pair) const { auto hash1 = hash{}(pair.first); auto hash2 = hash{}(pair.second); return hash1^hash2;
} }

unordered_map<pair<string, string>, int, pair_hash> um; ```

참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제 사진 출처 : Operating System Concepts 10E

1. 연속 메모리 할당

<스와핑>

1. 개요

• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고 생긴 공간에 새 프로세스 적재
• 스왑 인, 스왑 아웃

2. 스와핑의 이점

• 프로세스들이 요구하는 메모리 공간 크기 > 실제 메모리 크기

  <메모리 할당>

  1. 개요

• 프로세스는 메모리의 빈 공간에 할당되어야 한다.
• 빈 공간이 여러 개라면, 어느 곳에 할당하는 것이 이득일까?
  • 세가지 방식을 이용: 최초, 최적, 최악 적합

    2. 최초 적합 (first-fit)

• os가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 배치하기
• 장점: 검색의 최소화 & 빠른 할당

  3. 최적 적합 (best-fit)

• os가 빈 공간을 모두 검색해본 다음, 적재 가능한 가장 작은 공간에 할당하기

  4. 최악 적합 (worst-fit)

• os가 빈 공간을 모두 검색해본 다음, 적재 가능한 가장 큰 공간에 할당

  <외부 단편화 (external fragmentation)>

  1. 개요

• 위에서 언급한 세가지 방식, 즉 프로세스를 연속적으로 할당하는 방식은 메모리를 효율적으로 사용하는 방법이 아니다.

  2. 외부 단편화 예시

• 프로세스들이 실행되고 종료되길 반복하면서 메모리 사이사이 빈 공간이 발생하는데,
• 빈 공간의 합만큼의 메모리를 할당하지 못해서,
  • 빈 공간의 합은 50MB이지만, 30MB, 20MB 이런식으로 떨어져 있으므로 50MB짜리 프로세스를 할당하지 못함
  • 아래 그림 참고
• 메모리가 낭비되는 현상

  <외부 단편화 해결 방법>

  1. 메모리 압축 (Compaction)

• 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
• 프로세스를 재배치시켜 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
• 오버헤드가 크다는 단점
• 그렇다면 현재는 어떤 방식을 사용하는가?

  -> 2. 가상 메모리 기법, 페이징!

  2. 페이징을 통해 가상 메모리 관리

  <연속 메모리 할당의 문제점>

  1. 외부 단편화

  2. 물리 메모리보다 큰 프로세스 실행 불가

  <가상 메모리 (virtual memory)>

  1. 개요

• 가상 메모리란, 실행하고자 하는 프로그램을 일부만 메모리에 적재해서 물리 메모리보다 큰 프로세스를 실행하도록 하는 기술
• 페이징과 세그멘테이션이 존재

  <페이징 (paging)>

  1. 개요

• 외부 단편화의 근본적인 문제는, 각기 다른 크기의 프로세스를 메모리에 연속적으로 할당했기 때문임
• 모든 프로세스가 같은 크기였다면, 외부 단편화 발생 x
• 이러한 아이디어를 사용한 것이 페이징

  2. 페이징

• 간단하게 말하면 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당하도록 하는 기술
• 페이징 동작 방식
  • 프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고,
  • 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 일정한 단위로 자른 뒤
  • 페이지를 프레임에 할당하는 가상 메모리 관리 기법

3. 페이징에서의 스와핑

• 프로세스 단위의 스왑 인, 아웃이 아닌 페이지 단위의 페이지 인, 아웃 실행
  • 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃 (페이지 아웃)
  • 실행에 필요한 페이지들은 메모리로 스왑 인(페이지 인)
• 프로세스를 실행하기 위해 모든 페이지가 적재될 필요 없다.
  • 물리 메모리보다 큰 프로세스 실행 가능!

    4. 페이징에서의 의문점

• 프로세스를 이루른 페이지가 어느 프레임에 적재되어 있는지 CPU가 일일이 알기는 어렵다.
• 프로세스가 메모리에 불연속적으로 배치되어있다면, CPU 입장에서 이를 순차적으로 실행할 수 없다.
• CPU 입장에서 다음에 실행할 명령어 위치를 찾기 어려움
• 그렇다면, 물리 메모리에 분리되어 저장된 것을 어떻게 다시 모아서 CPU가 실행할 것인가? -> 페이지 테이블 이용!!

  <페이지 테이블>

  1. 개요

• 실제 메모리 내의 주소인 물리 주소에 불연속적으로 배치되더라도
• CPU가 바라보는 주소인 논리 주소에는 연속적으로 배치되도록 하는 방법

  2. 페이지 테이블

• 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표
• 물리적으로는 분산되어 저장되어 있더라도 CPU입장에서 바라본 논리 주소는 연속적이다
• 결과적으로 CPU는 논리 주소를 순차적으로 실행하면 된다.
• 그러나 내부 단편화라는 문제 발생..

  <내부 단편화 (internal fragmentation)>

  1. 개요

• 내부 단편화는 어떤 프로세스의 크기가 페이지 크기의 배수가 되지 않을 때 발생
• 결과적으로 하나의 페이지 크기보다 작은 크기가 낭비된다.
• 낭비되는 크기가 외부 단편화 보다는 작다. (대체로)

  <프로세스 테이블 베이스 레지스터 (PTBR)>

  1. 개요

• PTBR은 각 프로세스가 가지고 있는 페이지 테이블이 어디에 저장되어있는지를 나타내기 위한 레지스터
  • 각 페이지 테이블은 CPU 내의 PTBR이 가리킨다.

    2. 문제점

• 페이지 테이블이 메모리에 있다면, 메모리 접근 시간이 2배로 든다.
  • 페이지 테이블을 참조할 때 + 페이지를 참조할 때
• 해결방안은 TLB를 사용하기!!

  < TLB>

  1. 개요

• TLB란 페이지 테이블의 일부를 가져와서 저장하는 캐시 메모리
• 자주 참고하는 페이지 테이블 내용을 저장한다.

  2. 동작 방식

• TLB hit
  • CPU가 접근하려는 논리 주소가 TLB에 있는 경우
  • 메모리 접근을 한번만에 수행가능
• TLB miss
  • CPU가 접근하려는 논리 주소가 TLB에 없는 경우
  • 메모리 접근을 두번할 수 밖에 없다.

    <페이징에서의 주소 변환>

    1. 개요

• 특정 주소에 접근하기 위해 필요한 정보
  • 어떤 페이지, 프레임에 접근하고 싶은지
  • 접근하고자하는 주소가 그 페이지,프레임으로부터 얼마나 떨어져 있는지

    2. 페이징 시스템에서의 논리 주소의 구조

• 페이지 번호와 변위를 가짐
• <페이지, 변위> 로 이루어진 논리 주소는, 페이지 테이블을 통해 <프레임 번호, 변위>인 물리 주소로 변환된다.
  • 이때 변위는 같아야 한다.

<페이지 테이블 엔트리>

1. 개요

• 페이지 테이블의 각각의 행을 페이지 테이블 엔트리(PTE)라고 한다.

  2. PTE에 담기는 정보

• 페이지 번호
• 프레임 정보
• 유효 비트
  • 현재 해당 페이지에 접근 가능한지 여부를 알려줌
    • 유효 비트가 1이면 메모리에 적재된 페이지, 0이면 적재되지 않은 페이지
    • 유효 비트가 0인 페이지에 접근하려 하면, page fault라는 인터럽트 발생

    • CPU가 기존 작업 내용 백업

    • 페이지 폴트 처리 루틴 실행

    • 페이지 처리 루틴은 원하는 페이지 메모리로 가져온 뒤 유효 비트를 1로 변경

    • 페이지 폴트를 처리했다면, CPU는 해당 페이지에 접근 가능

• 보호 비트
  • 예를 들어 읽기 전용 페이지같은 경우, 보호 비트를 1로 설정해서 쓰기와 같은 다른 작업을 못하게 한다.
• 참조 비트
  • CPU가 해당 페이지에 접근한 적이 있다면 1, 없다면 0
• 수정 비트 (dirty bit)
  • CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부
  • swaping을 위해서 존재
  • 만약 페이지가 수정된다면, 보조기억장치에도 쓰기 작업을 해야함

<쓰기 시 복사 (Copy on Write)>

1. 개요

• 프로세스를 fork()하면 부모와 같은 내용을 가진 자식 프로세스가 생기므로,
• 프로세스 생성 시간이 지연되고, 메모리가 낭비되는 단점이 있다.

2. 쓰기 시 복사

• fork된 자식 프로세스는 부모 프로세스와 동일한 프레임을 가리키는 것
  • 만약 이때 아무 쓰기 작업도 이루어지지 않으면, 현재 상태를 유지한다.
• 그러나 쓰기 작업을 하게 된다면,
  • 쓰기 작업을 한 페이지는 별도의 공간으로 복제된다.

<계층적 페이징>

1. 개요

• 프로세스 테이블의 크기는 생각보다 작지 않기에, 프로세스를 이루는 모든 PTE에 메모리에 두는 것은 낭비이다.
• 프로세스를 이루는 모든 PTE를 항상 메모리에 유지하지 않는 기법

  2. 계층적 페이징

• 페이지 테이블을 페이징하여, 여러 단계의 페이지를 두는 방식
• CPU와 가장 가까이 위치한 페이지 테이블 (outer page table)만 항상 메모리에 유지

3. 페이지 교체와 프레임 할당

• 물리 메모리보다 큰 프로세스를 실행할 수 있지만, 물리 메모리의 크기는 한정되어있다.
• 결과적으로
  • 기존에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보내고, (페이지 교체)
  • 프로세스들에게 적절한 수의 프레임을 할당해야 함! (프레임 할당)

    <요구 페이징 (demand paging)>

    1. 개요

• 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만 메모리에 적재하는 기법

  2. 요구 페이징

  1) CPU가 특정 페이지에 접근하는 명령어 실행 2) 해당 페이지가 현재 메모리에 있을 경우 (유효비트가 1인 경우) CPU는 페이지가 적재된 프레임에 접근한다. 3) 해당 페이지가 현재 메모리에 없을 경우 (유효비트가 0인 경우) 페이지 폴트 발생 4) 페이지 폴트 시에는 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다. 5) 다시 1번 수행

  cf) 순수 요구 페이징

• 아무런 페이지도 메모리에 적재하지 않고 실행하는 기법
• 첫번째 명령어를 실행하는 순간부터, 계속해서 페이지 폴트 발생
• 점차적으로 페이지 폴트가 적어진다

  3. 요구 페이징이 해결해야 할 문제

• 페이지 교체
• 프레임 할당

  <페이지 교체>

  1. 개요

• 요구 페이징 기법으로 페이지를 적재하다보면 언젠가는 메모리가 가득 찬다.
• 당장 실행에 필요한 페이지를 적재하기 위해 적재된 페이지를 보조 기억장치로 내려야 하는데,
• 이때 어떤 페이지를 내보내야 하는가?

2. 페이지 교체 알고리즘

• 좋은 페이지 알고리즘은?
  • 페이지 폴트가 적은 알고리즘!
  • 페이지 폴트가 발생하는 순간 보조기억장치로 접근해야 하므로 성능이 저하되기 때문에
• 페이지 폴트의 횟수를 알기 위해 페이지 참조열 이용

3. 페이지 참조열 (page reference string)

• CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
• 연속된 페이지를 삭제해야 페이지 폴트를 줄일 수 있다.
  • ex)
    • 2 2 2 3 5 5 5 3 3 7 : 페이지 참조 순서
    • 2 3 5 3 7 : 페이지 참조열

      <페이지 교체 알고리즘>

      1. FIFO

• 가장 단순한 방식
• 메모리에 가장 먼저 올라온 페이지부터 내리는 방식
• 문제점
  • 프로그램 초기에 적재되었는데, 프로그램 실행 내내 사용될 페이지가 내쫓아진다면 성능면에서 이점이 없다.

2. 2차 기회(second-chance) 페이지 교체 알고리즘

• FIFO의 단점을 보완한 알고리즘
• 동작 방식
  • 참조 비트1
    • CPU가 한 번 참조한 적이 있는 페이지

    • 오래되긴 했지만, 자주 쓴 것

    • 한번 더 기회를 주기

    • 참조 비트를 0으로 초기화 하고

    • 적재 시간을 현재로 바꿈

  • 참조 비트0
    • CPU가 참조한 적이 없는 페이지
    • 내쫓기

      3. 최적(Optimal) 페이지 교체 알고리즘

• 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
  • CPU에 의해 참조되는 횟수를 고려
  • 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지!
• 동작 방식

• 문제점
  • 가장 낮은 페이지 폴트율을 보장하기는 하지만,
  • 구현이 어렵다. (예측을 어떻게 할건데?)

    4. LRU (Least-Recently-Used) 페이지 교체 알고리즘

• 가장 오래 사용되지 않은 페이지 교체
• 동작 방식

<스래싱>

1. 개요

• 페이지 폴트가 자주 발생하는 이유
  • 좋지 않은 페이지 교체 알고리즘을 사용했기 때문
  • 프로세스가 사용할 수 있는 프레임 자체가 적어서

    2. 스래싱 (Thrashing)

• 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
  • 지나치게 많은 페이징 때문
• 동시에 실행되는 프로세스의 수를 아무리 늘려도 CPU 이용률이 높아지지는 않는다.
• 원인
  • 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
• 해결 방안
  • 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고,
  • 프로세스들에게 적절한 프레임을 할당해야함

    <프레임 할당>

    1. 균등 할당 (equal allocation)

• 가장 단순한 방식
• 모든 프로세스들에게 균등하게 프레임을 할당하는 방식

  2. 비례 할당 (proportional allocation)

• 프로세스의 크기에 비례하여 프레임 할당
• 프로세스의 실행 과정을 교려하지 않기 때문에 정적할당 방식이라고 한다.
• 문제점
  • 크기가 큰 프로세스이긴 하지만, 많은 프레임이 필요없을수도..
  • 필요한 프레임 수는 실행해봐야만 알 수 있다.
• 해결방안
  • 프로세스를 실행하는 과정에서 프레임을 결정하는 방식이 필요하다.

  • 작업 집합 모델 & 페이지 폴드 빈도 기반 방식 (동적 할당 방식)

    3. 작업 집합 모델

• 스레싱의 원인이 과도한 페이징 이므로
  • CPU가 특정 시간동안 주로 참조한 페이지 갯수만큼만 프레임을 할당하기
• 프로세스가 일정 기간동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체 방지
  • 작업 집합이란, 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 말한다.
• 작업 집합 구하기
  • 프로세스가 참조한 페이지
  • 시간 간격 필요

4. 페이지 폴트 빈도

• 아래 두가지 가정에서 생긴 아이디어
  • 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
  • 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
• 페이지 폴트율에 상한과 하한선을 정하고, 그 범위 안에서 프레임을 할당해주는 방식

참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제 사진 출처 : Operating System Concepts 10E

1. 교착 상태란

<식사하는 철학자 문제 (Dining philosophers problem)>

1. 어떤 문제인가..

1) 철학자들은 계속 생각하다가, 왼쪽 포크가 사용 가능하면 집어든다. 2) 철학자들은 계속 생각하다가, 오른쪽 포크가 사용 가능하면 집어든다. 3) 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다. 4) 식사 시간이 끝나면 오른쪽 포크를 내려둔다. 5) 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려둔다. 6) 다시 1)부터 반복한다.

사진 출처: https://en.wikipedia.org/wiki/Dining_philosophers_problem

2. 교착 상태란?

• 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상
• 모든 철학자가 1)을 수행하면 사용 가능한 오른쪽 포크가 없으므로 멈춰버림

  <dead lock 해결하기 위해서>

  1. 개요

• 교착 상태가 발생했을 때의 상황을 정확히 표현하기
• 교착 상태가 일어나는 근본적인 이유 이해하기

  2. 자원할당 그래프

• 교착 상태가 발생했을 때의 상황을 표현하는 그래프
• 교착 상태 발생 조건 파악 가능
  • 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
  • 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능
• 그리는 방법
  • 프로세스는 원으로, 자원의 종류는 사각형으로 그리기
  • 자원의 갯수는 사각형 내의 점으로 표현
  • 프로세스가 할당 받은 자원은 화살표(r->p)로 표시
  • 프로세스가 기다리는 자원은 반대 화살표(p->r)로 표시
• 교착 상태가 일어나는 자원할당 그래프는 원의 형태이다.

  3. 교착상태가 발생할 조건

• 네가지 조건!!
• 1) 상호 배제 (Mutual exclusion)*

• 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

• 2) 점유와 대기 (Hold and wait)*

• 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태

• 3 비선점 (No preemption)*

• 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

• 4) 원형 대기 (Circular wait)*

• 프로세스들이 원의 형태로 자원을 대기하는 상태

• 이 네가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않고, 모두 만족해야 교착 상태가 발생한다.

  2. 교착 상태 해결 방법

  <예방 (Prevention)>

• 애초에 교착 상태가 발생하지 않도록 하기
• 네가지 발생 조건 중 하나를 없애버리기
• 교착 상태가 발생하지 않음을 보장할 수는 있지만, 부작용이 있다...

  1. 상호 배제 없애기

• 모든 자원을 공유가능하게 만들기?

• 현실적으로 불가능

  2. 점유와 대기 없애기

• 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분

• 자원의 활용률이 낮아지는 단점..

  3. 비선점 조건 없애기

• 선점이 가능한 자원(CPU)에 한해서 효과적임!

• 그러나 모든 자원이 선점 가능한 것은 아니다.

  4. 원형 대기 조건 없애기

• 자원에 번호를 붙이고, 오름차순으로 할당하면 원형대기는 발생하지 않음
• 예를 들면 원형이 아닌 일자로 된 식탁에서 식사하는 방법
• 그러나

• 자원에 번호를 붙이는 것은 어려운 작업이며

• 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.

  <회피 (Avoidance)>

  1. 개요

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
• 교착 상태가 발생하지 않을 만큼 조심히 할당하기
• 배분할 수 있는 자원의 양을 고려하기

  2. 교착 상태 회피

• 안전 순서열
  • 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 안전 상태
  • 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
  • 안전 순서열이 있는 상태
• 불안전 상태
  • 교착 상태가 발생할 수도 있는 상태
  • 안전 순서열이 없는 상태

• 예시 (안전 순서열이 존재하는 경우 - 위의 표 사용)
  • 할당 가능 자원 = 12
  • 할당한 자원 = 5+2+2 = 9
  • 남은 자원 = 12 - 9 = 3
  • 안전 순서열: P2->P1->P3
• 안전 순서열에 따라 동작하는 순서
  • P2가 먼저 2만큼 할당
    • 할당한 자원 = 9+2 = 11
    • 남은 자원 3 - 2 = 1
  • 요구한 자원을 모두 할당 받았으므로 P2의 자원 반환
    • 할당한 자원 = 11 - 4 = 7
    • 남은 자원 = 1 + 4 = 5
  • P1에 자원 할당
    • 할당한 자원 = 7 + 5 = 12
    • 남은 자원 = 5 - 5 = 0
  • P1자원 반환
    • 할당한 자원 = 12 - 10 = 2
    • 남은 자원 = 0 + 10 = 10
  • P3에 자원 할당
    • 할당한 자원 = 2 + 7 = 9
    • 남은 자원 = 10 - 7 = 3
  • 결론적으로 모든 프로세스가 자원을 할당 받았음!
    • 만약 다른 순서로 동작했다면, 모든 프로세스가 자원을 할당 받지 못하는 상황이 발생한다.
• 결론: 교착 상태 회피는 항상 안전 상태만을 유지하도록 자원을 할당하는 방식이다
• ex) 은행원 알고리즘

<검출 후 회복(Detection and Recovery)>

• 교착 상태의 발생을 인정하고 사후에 조치
• 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복

  1. 선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식

  2. 프로세스 강제 종료를 통한 회복

• 교착 상태에 놓은 프로세스를 모두 강제 종료
  • 작업 내역을 잃을 위험이 있다.
• 교착 상태가 해결될 때 까지 한 프로세스씩 강제 종료
  • 오버헤드가 발생

    <무시>

    1. 타조 알고리즘

• 문제 발생의 확률이나 정도가 약하다면 무시하는 것이 더 효율적인 경우가 있다.

참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제 사진 출처 : Operating System Concepts 10E

1. 동기화란

개요

• 프로세스와 스레드는 동시 다발적으로 동작한다.
• 자원의 일관성을 위해 프로세스와 스레드의 동기화 필요

<동기화의 의미>

1. 개요

• 공동의 목적을 위해 동시에 수행되는 프로세스들은
• 올바른 수행을 위해 동기화되어야 한다.

  2. 프로세스의 동기화

• 프로세스(스레드)들의 수행 시기를 맞추는 것
• 실행 순서 제어
  • 프로세스를 올바른 순서대로 실행하기
• 상호 배제
  • 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기

    <동기화 예시>

    1. 실행 순서 제어를 위한 동기화

• Reader Writer Problem
  • Writer
    • 파일에 값을 저장하는(쓰는) 프로세스
  • Reader
    • 파일에 저장된 값을 읽어들이는 프로세스
• 실행의 순서 지켜야함!
  • reader 프로세스는 파일 안에 값이 존재한다는 특정 조건이 만족되어야 실행 가능
  • writer의 조건이 먼저 선행되어야 함

    2. 상호 배제를 위한 동기화

• 예시 1) Bank Account Problem*
  • 공유가 불가능한 자원의 동시 사용을 피하기 위한 동기화
• 예시
  • 프로세스 A
    • 계좌 잔액 읽고
    • 잔액에 2만원 추가
    • 저장
  • 프로세스 B
    • 계좌 잔액 읽고
    • 잔액에 5만원 추가
    • 저장
  • 문제가 되는 상황은 (처음 잔액 10만원)
    • 프로세스 A 진행 도중, 저장이 되기 전 context swtich 발생하고 (10만원)
    • 프로세스 B도 저장이 되기 전까지 진행 후 context swtich 되어 (10만원)
    • 프로세스 A의 값 저장 (12만원)
    • 프로세스 B의 값 저장 한 상황 (15만원)
    • 결과적으로 17만원이 아닌 15만원이 잔액이 된다.
  • 문제를 막으려면
    • 한 번에 하나의 프로세스만 접근해야 하는 자원에 동시 접근을 막기
    • 프로세스 A가 다 끝난 후에 프로세스 B 실행

예시 2) Producer & Consumer Problem producer and consumer c++ code

• Producer: 물건을 계속해서 생산하는 생산자
• Consumer: 물건을 계속해서 소비하는 소비자
• 총합: 공유 자원

총합 = 10 //전역변수

Producer()
{
    //버퍼에 데이터 삽입
    //총합 변수 1 증가
}

Consumer()
{
    //버퍼에서 데이터 꺼내기
    //총합 변수 1 감소
}

• 이러한 상태에서 생산자와 소비자를 각각 100,000 실행하면?
  • 0과는 다른 값이 되거나, 오류가 발생하기도 한다.
  • 이유는?
    • 동기화가 되지 않았기 때문에 발생한 문제
    • 동시에 접근해서는 안되는 자원(공유자원)에 동시에 접근한 결과

<공유 자원과 임계 구역>

1. 공유 자원 (Shared Resource)

• 여러 프로세스 혹은 스레드가 공유하는 자원
• ex)
  • 전역 변수, 파일, 입출력장치, 보조기억장치

    2. 임계 구역 (Critical Section)

• 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
• 임계 구역에 진입하고자 하면, 진입한 프로세스 이외에는 대기해야 한다.
  • 프로세스 A가 실행중이면, 프로세스 B는 A가 끝날 때까지 대기했다가 실행
• ex)
  • 위 예시의 총합 변수, 잔액 변수

    3. Race Condition

• 임계구역에 동시에 접근하여 자원의 일관성이 깨지는 상태

  4. 운영체제가 임계구역 문제를 해결하는 세가지 원칙

• 상호 배제 (mutual exclusion)
  • 한 프로세스가 critical section에 진입했다면 다른 프로세스는 들어올 수 없다.
• 진행 (progress)
  • critical section에 어떤 프로세스도 진입하지 않았다면, 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
• 유한 대기 (bounded waiting)
  • 한 프로세스가 critical section에 진입하고 싶다면, 언젠가는 critical section에 들어올 수 있어야 한다.

2. 동기화 기법

<뮤텍스락 (Mutex Lock)>

mutex lock C++ code

1. 개요

• 상호 배제를 위한 동기화 도구 (자물쇠 역할)

• ex) 탈의실(임계구역)에 들어가는 손님(프로세스), 탈의실을 잠그는 자물쇠(뮤텍스락)

  2. 뮤텍스락

• 코드로 구현해 보기

  • 전역변수 하나와 함수 두 개로 구현 가능
  • 전역 변수 lock
    • 자물쇠 역할
  • acquire 함수
    • 임계구역을 잠그는 역할
    • 프로세스가 임계 구역에 진입하기 전에 호출
    • 임계구역이 잠겨 있다면, 열릴 때 까지 계속 체크
    • 임계구역이 열려 있다면, 임계구역을 잠그기
  • release 함수
    • 임계 구역의 잠금을 해제하는 역할
    • 임계 구역에서의 작업이 끝나고 호출
    • 현재 잠긴 임계 구역을 열기

• 예시

  acquire()
  {
    while(lock == true) //잠겨있다면,
           ;                //임계구역이 잠겨있는지 계속 확인
    lock = true;        //lock == false인 경우 임계구역 진입 후 lock을 다시 true로 만들기
  }
  

release() { lock = false; // 임계구역 작업 끝났으니 lock 해제 }

#### 3. Busy Waiting
* `while(lock == true) ;` 
* 무한히 대기하면서 임계구역을 체크하는 것 -> 좋은 방식은 아니다.
### <세마포 (Semaphore)>
[semaphore c++ code](https://github.com/GbLeem/Simple_cpp_OS/blob/main/03Synchronization/Synchronization_cpp/semaphore2.cpp)
#### 1. 개요
* 뮤텍스락 보다 일반화된 방식의 동기화 도구
* 공유 자원이 여러개 있는 경우에도 작용 가능
* **상호 배제와 실행 순서 동기화** 수행 가능
* ex) 이진 세마포, 카운팅 세마포 
#### 2. 카운팅 세마포
* 임계 구역 앞에서 멈춤 신호를 받으면 잠시 기다리기
* 임계 구역 앞에서 가도 좋다는 신호를 받으면 임계 구역 진입
* 코드로 구현해 보기
  * 전역변수 하나, 함수 두 개로 구현가능
  * 전역변수 S 
    * 임계 구역에 진입할 수 있는 프로세스의 갯수
    * 다른 말로 하면 사용 가능한 공유 자원의 갯수
  * wait 함수
    * 임계구역에 들어가도 좋은지, 기다려야 할지를 알려주는 함수
  * signal 함수
    * 임계구역 앞에서 기다리는 프로세스에 '이제 가도 좋다' 라고 신호를 주는 함수
* 예시

wait() { while(S<=0) //임계 구역에 진입 못하면 ; //진입 가능한 자원 있을때 까지 확인 S--; //진입할 수 있다면, S하나 감소시키고 임계구역 진입 }

signal() {
S++; //임계구역에서 작업을 마친 뒤 S를 1증가 }

#### 3. 문제점과 해결 방안
* 문제점
  * 세마포 방식 또한 busy waiting을 한다
  * CPU 사이클의 낭비!
* 해결 방법
  * 사용할 수 있는 자원이 없을 경우 **대기 상태**로 만든다.
  (해당 프로세스의 PCB를 대기 큐에 삽입)
  * 사용할 수 있는 자원이 생긴 경우, 대기 큐의 프로세스를 **준비 상태**로 만듦 
  (해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입)
* 코드 예시

wait() { S--; if(S<0) { add this process to Queue; //PCB를 대기큐에 삽입 sleep(); //대기 상태 } }

signal() { S++; if(S<=0) { remove a process p from Queue; //대기 상태에 있는 프로세스 제거 wakeup(p); //프로세스 p를 대기 상태에서 준비 상태로 만들기 } }

#### 4. 세마포의 실행 순서 동기화
* 예시
  * 변수 S를 0으로 두고 
  * 먼저 실행할 프로세스 뒤에 signal 함수
  * 다음에 실행할 프로세스 앞에 wait 함수를 붙이기
* 동작 순서
  * process1이 임계 구역 들어가서 실행 후 종료하면, siganl 함수를 통해 S가 1이 되고, 
  * process2가 S가 1인 것을 확인 후 실행
  * 결론적으로 p1 이 p2보다 먼저 실행된다.
### <모니터>
#### 1. 개요
* 매번 임계구역 앞 뒤로 wait(), signal() 호출하는 것이 번거롭다. 
* 아래의 이유들 때문에 실수 유발 가능
  * 세마포 누락
  * 함수 순서 바꿈
  * 함수 중복 사용
  * etc
* **상호 배제와 실행 순서 동기화** 수행 가능
* 모니터 안에는 하나의 프로세스만 있을 수 있다.
#### 2. 모니터의 상호 배제
* 인터페이스를 위한 큐
* 공유자원에 접근하고자 하는 프로세스를 큐에 삽입
* 큐에 삽입된 순서대로 공유 자원 이용
#### 3. 모니터의 실행 순서 제어를 위한 동기화
* 코드를 만든다면
  * 조건 변수 이용
    * 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수
    * 조건변수에 대한 큐가 존재 (아래 그림의 빨간 네모칸)
  * 조건변수.wait()
    * 대기 상태로 변경, 조건 변수에 대한 큐에 삽입
  * 조건변수.signal()
    * wait()으로 대기 상태로 접어든 조건변수를 실행 상태로 변경
* 실행 순서 제어를 위한 동기화의 핵심!
  * **특정 프로세스가 아직 실행될 조건이 되지 않았을 때에는 wait을 통해 실행을 중단한다.**
  * **특정 프로세스가 실행될 조건이 충족되었을 때에는 signal을 통해 재개한다.**
#### 4. 모니터의 구조
![](https://velog.velcdn.com/images/gb_leem/post/46c77b66-8afc-4e61-b5d1-8a02ad9eda6b/image.png)

참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제 사진 출처 : Operating System Concepts 10E

1. CPU 스케줄링 개요

<CPU 스케줄링이란>

1. 개요

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

2. 가장 공정한 방법?

• 프로세스마다 우선순위를 생각해서 스케줄링 해야함
  • ex) 입출력 작업이 많은 프로세스는 CPU 작업이 많은 프로세스보다 우선순위가 높다.
    • 입출력 작업이 많은 프로세스는 대기하는 시간이 길다.
    • 즉, 미리 입출력 작업을 빠르게 끝내버리고 CPU 작업이 많은 프로세스에게 CPU를 몰빵하는 것

      <프로세스 우선순위>

      1. 개요

• PCB에 저장되어 우선순위 높은 것 부터 실행

  2. 우선순위를 찾는 방법

• 매번 모든 프로세스의 PCB를 찾아서 우선순위 높은 것을 찾는 것은 너무 낭비이고 오래걸린다.

• 스케줄링 큐 이용

<스케줄링 큐>

1. 개요

• 프로세스 마다 요구하는 자원들을 그에 따라 큐에 정리함
• 같은 큐 내에서도 우선순위 별로 처리한다
  • cf)스케줄링 큐에서 큐는 반드시 FIFO는 아니다.

2. 준비 큐

• CPU를 이용하기 위해 기다리는 큐

  3. 대기 큐

• 입출력장치를 이용하기 위해 기다리는 큐
• 같은 장치를 요구한 프로세스들은 같은 큐에서 대기
  • ex) 프린터 대기 큐, 하드디스크 대기 큐

4. 그렇다면

• 현재 진행중인 프로세스보다 우선순위가 높은 프로세스가 ready queue에 들어오면 누구를 먼저 실행할 것인가?

• 선점형 비선점형 스케줄링으로 결정

<선점형과 비선점형 스케줄링>

1. 개요

• 현재 한 프로세스가 실행중인데, 다른 프로세스가 너무 급해서 CPU를 할당해달라고 할 때

• 현재 사용중인 프로세스로부터 CPU 자원 빼앗기

• 현재 사용중인 프로세스 끝날 때 까지 기다리기

  2. 선점형 스케줄링 (preemptive)

• 프로세스마다 정해진 시간은 모두 지키고, 타이머 인터럽트 발생했을 때 CPU 넘겨주기
• 장점)
  • 한 프로세스의 독점을 막음
  • 프로세스들에 골고루 자원 배분 가능
• 단점)
  • context switching이 많기 때문에 오버헤드 발생 가능

    3. 비선점형 스케줄링 (non-preemptive)

• 현재 진행중인 프로세스의 CPU 할당을 빼앗아서 급한 프로세스에게 바로 넘겨주기
• 장점)
  • context switch 오버헤드 적다
• 단점)
  • 모든 프로세스에게 골고루 자원 배분 못할 수 있다.

2. CPU 스케줄링 알고리즘

<선입 선처리 (First Come First Served>

• ready queue에 삽입된 순서대로 처리하는 비선점 스케줄링
• 동작방식
  • 먼저 CPU를 요청한 프로세스부터 CPU 할당
• 단점)
  • 프로세스들이 기다리는 시간이 매우 길어질 수 있다.
  • ex) 먼저 실행된 프로세스의 실행시간이 길 때, 매우 오래 기다려야함

    <최단 작업 우선 (Shortest Job First)>

• FCFS의 단점을 해결한 방식
• CPU 사용시간이 가장 짧은 프로세스부터 처리하는 방식
  • 비선점형 스케줄링
  • CPU 시간이 긴 프로세스를 나중에 실행하기

    <라운드 로빈 (Round Robin)>

• FCFS + 타입 슬라이스 를 사용하는 방식
  • 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
  • 타임 슬라이스의 크기를 잘 정하는 것이 중요
• 동작 방식
  • 큐에 삽입된 순서대로 프로세스들이 CPU를 이용하다가 정해진 시간 만큼만 사용
  • 만약 정해진 시간동안 못 끝냈다면, 다시 큐의 맨 뒤에 삽입

    <최소 잔여 시간 우선 (Shortest Remaining Time)>

• SJF + Round Robin 방식
• 동작 방식
  • 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스 선택

    <우선순위>

• 동작방식
  • 프로세스들에 우선순위 부여하고 우선순위 높은 프로세스부터 실행
  • 우선순위 같은 프로세스는 FCFS로 스케줄링
• SJF, SRT 스케줄링을 포함하는 개념

  cf) Starvation

• Starvation 현상이 발생할 수 있다는 근본적인 문제점 존재
  • 우선순위가 높은 프로세스만 계속 실행되고, 낮은 프로세스는 계속 연기된다.
• 해결방안
  • aging 기법 : 오랫동안 대기한 프로세스의 우선순위를 높여주는 방식

    <다단계 큐 (Multilevel queue)>

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
  • 큐가 여러 개이므로, 각자 다른 스케줄링 방식을 쓸 수 있다.
• 동작방식
  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스 처리
• 문제점
  • 큐 간의 이동이 불가능 하므로,
  • 결국 우선순위가 낮은 큐는 계속 실행을 못하는 starvation 발생 가능

    <다단계 피드백 큐 (Multilevel feedback queue>

• 다단계 큐 스케줄링의 발전된 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• CPU를 많이 써야할수록 우선순위가 낮아진다.
• 동작방식 (아래 사진 참고) 참고 : quantum = 8 이 우선순위가 가장 높은 것
  • 8의 quantum 동안 프로세스가 끝나면 ok
  • 8의 quantum 동안 프로세스가 끝나지 않으면 CPU를 더 써야하는 것이므로 우선순위를 하나 내려준다.
  • 반복하다보면, CPU 집중 프로세스는 우선순위가 낮아지고, IO 집중 프로세스의 우선순위는 높아진다.
• 다단계 피드백 큐에서도 aging 기법 사용 가능

참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제 사진 출처 : Operating System Concepts 10E

1. 프로세스 개요

<실행 중인 프로그램, 프로세스>

1. 프로세스 확인하기

• foreground process: 사용자가 볼 수 있는 공간에서 실행
• background process: 사용자가 볼 수 없는 공간에서 실행
  • 사용자와 상호작용 o
  • 사용자와 상호작용 x - daemon, service

<프로세스 제어 블록>

1. 개요

• 모든 프로세스는 실행을 위해 CPU가 필요하다. but CPU 자원은 한정되어있음
• 그 결과 한정된 시간만큼만 CPU 사용해야함
  • 자신의 차례에 정해진 시간만큼 CPU 이용
  • 타이머 인터럽트 발생하면 다음 프로세스 실행

    2. 프로세스 제어 블록 (PCB)

• 빠르게 번갈아 수행되는 프로세스 관리를 위해 사용하는 자료구조
  • 프로세스 관련 정보 저장 (상품에 달린 태그와 같은 역할)
  • 프로세스 생성 시 커널 영역에 생성, 종료 시 폐기
• PCB에 담기는 정보
  • 프로세스 ID (PID)
    • 특정 프로세스 식별하기 위한 번호
  • 레지스터 값
    • 존재 이유: 마지막으로 어디까지 연산 수행했는지 기억하려고
    • 자신의 실행 차례가 오면 이전까지 사용한 레지스터 중간 값을 모두 복원 (프로그램 카운터, 스택 포인터)
  • 프로세스 상태
    • 입출력 장치를 사용하기 위해 기다리는 상태
    • CPU를 사용하기 위해 기다리는 상태
    • CPU 이용중인 상태 등
  • CPU 스케줄링 정보
    • 프로세스가 언제, 어떤 순서로 CPU 할당 받을 것인지
  • 메모리 정보
    • 프로세스가 어느 주소에 저장되어 있는지
    • 페이지 테이블 정보
  • 사용한 파일과 입출력 장치 정보
    • 할당된 입출력 장치, 열린 파일 정보 등

<문맥 교환(context switch)>

1. Context Switch 과정

• 프로세스 A에서 프로세스 B로 실행 순서가 넘어가면?
  • 기존에 실행되던 프로세스 A의 중간 정보(context)를 백업
  • 프로세스 B의 context 복구
  • 다시 프로세스 A 차례가 오면 중간 정보를 기반으로 다시 복구

    2. Context Switch

• 기존의 실행 중인 프로세스 문맥을 백업하고, 새로운 프로세스 실행을 위해 문맥을 복구하는 과정

<프로세스의 메모리 영역>

1. 코드 영역 (텍스트 영역)

• 실행할 수 있는 코드 (기계어로 이루어진 명령어 저장)
• 데이터가 아닌 CPU가 실행할 명령어가 담겨있음 (read-only)
• 크기 고정 (정적 할당 영역)

  2. 데이터 영역

• 잠깐 썻다가 없어지는 데이터가 아니라 프로그램이 실행되는 동안 유지할 데이터 저장
• 크기 고정 (정적 할당 영역)
• ex) 전역변수

  3. 힙 영역

• 프로그램을 만드는 사용자, 즉 프로그래머가 직접 할당할 수 있는 저장공간
  • 할당하면, 언젠가는 반환(해제)를 해주어야 함
  • cf) garbage collection
• 동적 할당 영역
  • 일반적으로 낮은 주소에서 높은 주소로 할당

    4. 스택 영역

• 데이터가 일시적으로 저장되는 공간
  • 잠깐 쓰다가 말 값들이 저장되는 공간
• ex) 매개변수, 지역변수
• 동적 할당 영역
  • 일반적으로 높은 주소에서 낮은 주소로 할당

2. 프로세스 상태와 계층 구조

<프로세스 상태>

1. 생성 상태

• 이제 막 메모리에 적재되어 PCB를 할당 받은 상태
• 준비가 완료되었다면, 준비 상태로 이동

  2. 준비 상태

• 당장이라도 CPU를 할당받아서 실행할 수 있지만,
• 자신의 차례가 아니기에 기다리는 상태, 자신의 차례가 된다면 실행 상태로 이동 (디스패치)

  3. 실행 상태

• CPU를 할당 받아 실행 중인 상태
• 할당된 시간 모두 사용 시 (타이머 인터럽트 발생) 준비 상태로 이동
• 실행 도중 입출력장치 사용하면, 입출력 작업이 끝날 때까지 대기 상태로 이동

  4. 대기 상태

• 프로세스가 실행 도중 입출력 장치를 사용하는 경우
• 입출력 작업은 CPU에 비해 느리기 때문에 대기 상태로 접어둠
• 입출력 작업이 끝나면 (입출력 완료 인터럽트 발생하면) 준비 상태로 이동

  5. 종료 상태

• 프로세스가 종료된 상태
• PCB, 프로세스의 메모리 영역 정리

<프로세스 계층 구조>

• 프로세스 실행 도중 (시스템 호출을 통해) 다른 프로세스 생성 가능
  • cf) 윈도우는 계층 구조 아님
• 새 프로세스를 생성한 프로세스: 부모 프로세스
• 부모 프로세스에 의해 생성된 프로세스: 자식 프로세스
  • 부모 프로세스와 자식 프로세스는 별개의 프로세스이므로 PID가 다르다.
  • 일부 OS는 자식 프로세스 PCB에 부모 프로세스 PID (PPID)를 명시하기도 함
• 부모 -> 자식 -> 자식 -> ... : 계층 구조 형성

<프로세스 생성 기법>

1. 개요

• cf) 윈도우 운영체제와 관련은 없음
• 질문
  • 부모 프로세스는 자식 프로세스를 어떻게 만들어내는가
  • 자식 프로세스는 어떻게 자신만의 코드를 실행하는가
• 답
  • 복제와 옷 갈아입기
  • 부모 프로세스는 fork 시스템 호출을 통해 자신의 복사본을 자식 프로세스로 생성 (복제)
  • 자식 프로세스는 exec 시스템 호출을 통해 자신의 메모리 공간을 다른 프로그램으로 교체 (옷 갈아입기)

2. 프로세스 생성 기법

• fork 시스템 호출
  • 복사본(자식 프로세스) 생성, 부모와 같은 복사본
    • but PID와 저장된 메모리 공간은 다르다
  • 부모 프로세스의 자원 상속
    • 부모 프로세스의 메모리 영역을 복사해서 가져온다.
• exec 시스템 호출
  • 메모리 공간을 새로운 프로그램으로 덮어쓰기
  • 코드/데이터 영역은 실행할 프로그램 내용으로 바뀜
  • 나머지 영역은 초기화

    3. 스레드

    <스레드란>

    1. 스레드란

• 프로세스를 구성하는 실행 흐름의 단위
  • 하나의 프로세스는 하나 이상의 스레드를 가질 수 있다.
• 단일 스레드 프로세스
  • 실행 흐름이 하나인 프로세스
• 멀티 스레드 프로세스
  • 프로세스를 이루는 여러 명령어 동시 실행 가능

2. 스레드의 구성 요소

• 스레드 ID
• 레지스터 값 (프로그램 카운터)
• 스택 값
• 실행에 필요한 최소한의 정보
  • 코드, 데이터 영역, 자원을 공유함 (위 사진 참고)

<멀티 프로세스와 멀티 스레드>

1. 멀티 프로세스

• 동일한 작업을 수행하는 단일 스레드 프로세스 여러 개 실행 (a)
• 프로세스 끼리는 자원 공유 x
  • 프로세스 fork하면, 모든 자원이 복제된다.
  • 저장된 메모리 주소를 제외하고 모든 것이 동일한 프로세스가 메모리에 적재된다. (중복!)
  • cf) 실제로는 "copy on write" 해서 중복 저장을 없애주긴 함!
• 독립적으로 실행된다.
• IPC : 프로세스 간 통신
  • 프로세스간에 자원을 주고 받을 수 있기는 하다.
  • 스레드 간 통신 보다는 어려움
    • 파일, 공유 메모리를 통해서 IPC 수행

      2. 멀티 스레드

• 하나의 프로세스를 여러 스레드로 실행 (b)
• 스레드 끼리는 같은 프로세스 내 자원 공유 o
  • 레지스터 값, 스택 값 만 가지고,
  • 코드, 데이터, 힙, 파일 영역은 공유한다.
• 협력과 통신에 유리하다.
  • 하나의 스레드가 문제 생기면, 전체 프로세스에 문제가 생길 가능성이 있다. (단점)

참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제 사진 출처 : Operating System Concepts 10E

1. 운영체제를 알아야 하는 이유

<운영체제란>

1. 운영체제는

• 실행할 프로그램에 필요한 자원을 할당하고
• 프로그램이 올바르게 실행되도록 돕는
• 특별한 프로그램
  • 프로그램이기 때문에 메모리에 저장되어야 한다
  • 운영체제는 커널 영역에 적재된다.
  • cf) 응용 프로그램(application)은 사용자 영역에 적재
• 하드웨어와 응용 프로그램 사이에서 우리가 편리하게 사용할 수 있도록 도와준다.

2. 운영체제의 메모리 관리

• 운영체제는 응용 프로그램이 실행되거나 종료될 때 적절한 메모리에 할당하거나 해제시킨다.

3. 운영체제의 CPU 관리

• 응용 프로그램이 동시에 실행되고 있더라도, 각 프로그램의 우선순위에 따라 CPU 사용량을 조절해준다.

4. 운영체제의 입출력장치 관리

• 프린터, 키보드 등 우선순위 관리
• +)보조 기억 장치에 있는 것을 파일과 폴더로 관리

5. 운영체제는 '정부' 와 유사한 일을 한다.

<운영체제를 알아야 하는 이유>

1. 개발자가 하드웨어를 직접 조작하는 일 없이 편리하게 개발할 수 있게 해준다.

• 운영체제는 사용자를 위한 프로그램이 아니라 프로그램을 위한 프로그램이다.
• 문제가 생긴다면 운영체제가 도움을 준다.
  • 프로그램이기 때문에 오류 메세지를 준다.

2. 운영체제의 큰 그림

<커널이란?>

1. 커널

• 운영체제의 핵심 서비스를 담당하는 부분

  2. UI

• OS에는 속하지만 커널에는 속하지 않는 기능
• 사용자와 컴퓨터 간의 통로일 뿐
• ex) 그래픽 유저 인터페이스, 커맨드라인 인터페이스

  <운영체제의 서비스 종류>

  1. 프로세스 관리

• 프로세스
  • 프로세스 == 실행중인 프로그램
  • 동시다발적으로 생성/실행/삭제되는 프로세스들을 관리해야 함!

    2. 자원 접근 및 할당

• CPU
  • CPU 스케줄링: 어떤 프로세스를 먼저, 얼마나 오래 실행할지
• 메모리
  • 적재할 빈 메모리 공간을 어떻게 찾을지, 다 적재해야 하는지..
  • 페이징, 스와핑
• 입출력장치
  • 하드웨어 인터럽트 서비스 루틴

    3. 파일 시스템 관리

• 관련된 정보를 파일이라는 단위로 저장 장치에 보관
• 파일을 묶어 폴더(디렉토리) 단위로 저장 장치에 보관

<시스템 콜과 이중 모드>

1. 사용자가 실행하는 프로그램은 자원에 직접 접근할 수 있을까?

• NO! 자원에 직접 접근은 위험하다.
• 그렇기 때문에 OS는 응용 프로그램이 자원에 접근하여 할 때 OS를 통해서만 접근하도록 보호해준다.

2. 이중모드

• CPU가 명령어를 실행하는 모드의 두 가지 (이중모드)
  • 사용자 모드
    • OS 서비스 제공 x
    • 커널 영역 코드 실행 x
    • 자원 접근 x
  • 커널 모드
    • OS 서비스 제공 o
    • 자원 접근 o
• 플래그 레지스터
  • 슈퍼바이저 플래그를 통해 커널 모드인지 사용자 모드인지 확인한다.

3. 시스템 호출

• 커널 모드로 전환하여 실행하기 위해 호출!
  • 운영체제한테 도움 청하기!
• 일종의 소프트웨어 인터럽트 1) 시스템 호출 2) 운영체제 코드 실행 (하드웨어 접근 코드 실행) 3) 시스템 호출 복귀 (사용자 모드로 간다)
• 시스템 호출 명령어들

• Objects : collection of data
• Actor : object on the level
• Components : objects that can go on an actors

  Add Impulse

  
• Vel Change 체크하면, 물체의 질량에 관계없이 Impulse 에 가한 값만큼 움직인다.

• 400cm/s

F8

• game을 플레이하는 플레이어에서 탈출해서 조작할 때

Pawn Rotation

• get actor rotation 언리얼 카메라와 pawn 의 rotation은 기본적으로 연동되어있지 않다.
• get control rotation 카메라의 rotation 반영함

Get Forward Vector

• 크기 1짜리

Geometry

• subtractive 사용해서 창문 처럼 뚫을 수 있다.

  Fix Collision

• mesh가 여러 개가 바짝 붙어있을 때 충돌 때문에 불안정 한 현상 고치기 (아래 사진처럼 만들기) 1) 바꾸려고 하는 매시 선택후 collision 선택 2) remove collision 한다음 simplified collision 선택하기

Pure Function

• A function with no side effect
  • side effect : observable effect of a function
• NO EXECUTION PIN!
• only return values
• ex)
  • get ammo
  • get actor forward vector
  • math function (*, -, >...)
• 예시

원본 코드: https://github.com/GbLeem/CodingTest2024/blob/main/CPP/Inheritance/inheritance_test.cpp

함수 오버라이딩

• 덮어쓰기라고 생각하면 편함
  • C++는 기본적으로 정적 바인딩한다.
• 예시 코드 Bar() 함수가 overriding 된 함수이며 실행 예시를 보면 클래스 type에 따라 실행된다.

가상함수

• 다형성의 가장 핵심이 되는 것
• 동적 바인딩
• 가상 테이블이 생성되며, 이는 클래스마다 하나를 가진다.
• 예시 코드 Foo() 함수가 가상함수이며 실행 예시를 보면 실제로 가리키는 것에 따라 실행된다.

상속

• 예시 코드 d 는 Derived 타입변수이며 Base로 부터 상속을 받았으므로, Base Class의 멤버함수 OnlyBase()를 쓸 수 있다.

  예시 코드

  #include <iostream>
  using namespace std;
  

class Base { public: virtual void Foo() { printf("Base::Foo\n"); } void Bar() { printf("Base::Bar\n"); } void onlybase() { cout << "onlybase\n"; } };

class Derived : public Base { public: virtual void Foo() { printf("Derived::Foo\n"); } void Bar() //Overriding { printf("Derived::Bar\n"); } void OnlyDerived() { cout << "only derived\n"; } };

int main() { Derived* d = new Derived(); //여기서 base 묵시적으로 만들어짐 Base* b = reinterpret_cast<Base>(d); Base b2 = new Base();

d->Foo(); //Derived::Foo
d->Bar(); //Derived::Bar
d->onlybase();
d->OnlyDerived();
cout << "\n";

b->Foo(); //Derived::Foo    
b->Bar(); //Base::Bar
b->onlybase();
cout << "\n";

b2->Foo(); //Base::Foo
b2->Bar(); //Base::Bar
b2->onlybase();

}

0. intro

• DP 문제는 뭔가 작은 값들을 계산하다 보면 결국 큰 값도 결과가 나올 수 있을 것 같은 문제에서 쓰기
• 시간 복잡도 줄이기
• prefix sum 기법도 있다. (BOJ 11659)

1. DP 문제를 위한 흐름

1) 테이블 정의하기 2) 점화식 찾기 3) 초기값 찾기

2. DP를 풀 때 팁

(정답은 아니고 풀다가 생각을 정리한 것 들입니다.)

• 점화식을 만들 때 d[1] 부터 계산해 나가면서 규칙 찾아내는 식으로 풀기
• 단순히 1차원 배열로 해결이 안될 것 같으면 2차원 배열도 생각해보기
• 점화식이 잘 안 만들어 지면 맨 끝값부터 처리하는 것도 생각해보자 (BOJ 15486)
• 점화식 만들 때는 현재 시점에 어떠한 행동을 했다고 가정했을 때, 과거의 값들에 대한 비교를 통해 현재 점화식 값을 설정한다.
• 초기값은 for문을 돌리면서 초기값으로 필요할 것들을 직접 대입해서 설정해주기

3. DP 문제 예시

예시1) BOJ 2579 계단 오르기

#include <iostream>
using namespace std;

int n;
int board[305];
int d[305][305];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> board[i];

    d[1][1] = board[1];
    d[1][2] = 0;
    d[2][1] = board[2];
    d[2][2] = board[1] + board[2];

    for (int i = 3; i <= n; ++i)
    {
        d[i][1] = max(d[i - 2][2], d[i - 2][1]) + board[i];
        d[i][2] = d[i - 1][1] + board[i];
    }
    cout << max(d[n][1], d[n][2]);
}

• 점화식 부분)
  • d[i][j] : i번째 계단을 밟은것 / j번 연속 밟은 것
  • d[i][1]
    • 현재 i 번째 계단을 밟았다고 (현재시점) 했을 때 j는 1이므로 한번 연속 밟았으니, 하나 전 계단은 밟을 수 없음 (하나 전 계단도 밟았으면 j가 2여야 하므로)
    • 두개 전 계단을 밟았을 때 (과거시점) 연속 1번 밟은 것과 연속 2번 밟은 것 중 큰 값을 가져오고
    • 마지막으로 현재의 계단을 밟았을 때 값을 더해준다.
  • d[i][2]
    • 현재 i 번째 계단을 밟았다고 (현재시점) 했을 때, 연속 두번 밟았으므로
    • 하나 전 계단 (과거시점) 은 무조건 밟아야한다.
    • 마지막으로 현재 계단에 대한 값도 더해주면 된다.

예시2) BOJ 9465 스티커

#include<iostream>
using namespace std;

int t, n;
int board[2][100005];
int d[100005][3]; //(값, 마지막으로 선택한 타일)

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;

    while (t--)
    {
        cin >> n;

        for (int i = 0; i < 2; ++i)
            fill(board[i], board[i] + n, 0);

        for (int i = 0; i < n; ++i)
            fill(d[i], d[i] + 3, 0);

        for (int i = 0; i < 2; ++i)
        {
            for (int j = 0; j < n; ++j)
                cin >> board[i][j]; // board[0][1] 은 첫줄 2번째
        }

        d[0][0] = 0;
        d[0][1] = board[0][0];
        d[0][2] = board[1][0];    

        if (n == 1)
            cout << max(max(d[0][0], d[0][1]), d[0][2]) << "\n";
        else
        {
            for (int i = 1; i < n; ++i)
            {
                //첫줄 붙이거나 둘째줄 붙이거나 안붙이거나
                d[i][0] = max(max(d[i - 1][1], d[i - 1][2]), d[i - 1][0]);
                d[i][1] = max(d[i - 1][0], d[i - 1][2]) + board[0][i]; //첫줄 붙임
                d[i][2] = max(d[i - 1][0], d[i - 1][1]) + board[1][i]; //둘째줄 붙임
            }

            cout << max(max(d[n - 1][0], d[n - 1][1]), d[n - 1][2]) << "\n";
        }
    }
}

참고 https://www.aleksandrhovhannisyan.com/blog/implementing-a-finite-state-machine-in-cpp/#what-is-a-finite-state-machine https://gameprogrammingpatterns.com/state.html https://ansohxxn.github.io/design%20pattern/chapter11/ https://docs.unrealengine.com/4.27/ko/AnimatingObjects/SkeletalMeshAnimation/StateMachines/Overview/ https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jerrypoiu&logNo=221235988023

FSM (Finite State Machine)

1. FSM

• 다양한 상태들 간의 전이와 그에 따른 동작을 모델링하는 방식
  • 유한한 갯수의 상태들을 가지며, 상태들 중 하나의 상태만 취하는 상황
  • 특정 조건이 되면 다른 상태로 변할 수 있어야 한다.
• FSM을 쓰는 이유
  • 가능한 상태들을 명확히 규정할 수 있다.
  • 상태 중복을 피할 수 있다.
  • 유지보수가 좋다.
• 예시(캐릭터의 점프를 구현하기) 1) 특정 키를 눌러서 점프하는 코드를 작성했다.

  if(input == PRESS_B)
  {
    Jump();
  }

  2) 이단 점프를 막기 위해 bool 변수를 하나 도입해서 처리해준다.

  if(input == PRESS_B)
  {
    if(!bIsJumping)
    {
         bIsJumping = true;
          Jump();
    }
  }

  3) 아래 키보드를 누르면 엎드리고 떼면 일어서는 코드를 작성한다.

  if(input == PRESS_B) 
  {
    if(!bIsJumping)
    {
         bIsJumping = true;
          Jump();
    }
  } 
  else if(input == PRESS_DOWN) 
  {
    if(!isJumping_) 
    {
        Duck();
    }
  }
  else if(input == RELEASE_DOWN) 
  {
    Stand();
  }

  위처럼 하나의 기능이 추가될 때 마다 if 문이 늘어나고, 새로운 변수가 계속해서 늘어나게 된다는 문제점이 있다.

• FSM으로 이러한 문제를 해결

• 간단한 방법으로는 FSM 상태를 enum class로 만들어서 switch case문으로 처리할 수 있다.
• switch case도 코드가 꼬일 수 있기 때문에 상태를 별도의 클래스로 캡슐화한 다음 현재 상태를 나타내는 객체에게 행동을 위임하는 방식을 사용

2. FSM 코드

https://www.aleksandrhovhannisyan.com/blog/implementing-a-finite-state-machine-in-cpp/#what-is-a-finite-state-machine

...

3. FSM in Unreal Engine

• State Machine
  • 언리얼 엔진에서 애니메이션을 위해 구현되어 있는 기능
  • Animation Bluprint를 만들어서 사용 가능하다.
• 위의 캐릭터 애니메이션 프로세스 흐름도를 아래의 state machine으로 구성할 수 있다.
• 구성 요소
  • State
    • 캐릭터가 어떤 행동을 해야 할지에 대한 상태를 나타내기
    • 해당 state를 더블클릭하면 output animation pose를 결정하도록 되어있다.

• Transition
  • 한 상태에서 다른 상태로 전환함에 있어서 어떤 식으로 전환할지를 정하기
  • 이때 transition rule에 따라 전환된다.

• Conduit
  • transition은 한 상태에서 다른 상태로 일대일 대응관계이지만, conduit은 일대다, 다대다 대응이 가능하다.

참고자료 배열 : https://learn.microsoft.com/ko-kr/cpp/cpp/arrays-cpp?view=msvc-170 constexpr : https://learn.microsoft.com/ko-kr/cpp/cpp/constexpr-cpp?view=msvc-170

1. Array

특징

• 인접한 메모리 영역 차지

  생성 방식

• 스택 선언

  constexpr size_t size = 1000;
  double numbers[size]{ 0 };
  numbers[0] = 1;
  

for (size_t i = 1; i < size; ++i) { numbers[i] = numbers[i - 1] * 1.1; }

for (const auto n : numbers) { cout << n << " "; //1 1.1 1.21 1.331 ... }

* 힙 선언 (동적)

size_t size2 = 100; int* numbers2 = new int[size2] {0}; numbers2[0] = 1;

for (size_t i = 1; i < size2; ++i) { numbers2[i] = 100; } int* p = numbers2;

for (size_t i = 0; i < size2; ++i) { cout << *(p++) << " "; //100 100 100 100 ... }

* stl array -> `#include <array>` 필요

array<int, 3> a1; a1[0] = 100; a1[1] = 200; a1[2] = 300;

### 추가
* 함수에 배열 전달
  * 배열이 함수에 전달되면 첫번째 요소에 대한 포인터로 전달된다.
  * 예시)

int Sum(const int *num, const size_t len) { int sum = 0; for (size_t i = 0; i < len; ++i) { sum += num[i]; } return sum; }

* `constexpr` 변수
  * 컴파일 시간에 초기화해야 한다.
  * 컴파일 도중에 "반드시" 값이 결정되도록 할 때 사용
  * 예시
  `constexpr float x = 42.0f;` -> ok
  `constexpr int i;` -> error (초기화 불가)
  `constexpr int k = i+1`
* `size_t`
  * 정의 :`typedef unsigned __int64 size_t;`
  * 64비트일 때 8바이트 unsigned int
  * 주로 배열 인덱싱 및 loop계산에 사용된다.
  -> unsigned_int가 UINT_MAX를 초과하는 경우 예방?
## 2. Vector
### 특징
* 어떤 자료형도 넣을 수 있는 동적 배열
* 연속된 메모리 공간에 위치
* 자동 메모리 관리, 어떤 요소에도 임의 접근 가능

### 생성 방식
`std::vector<int> name1;`
`std::vector<int> name2(name1);` : 복사 생성자
`std::vector<int> name3(10);` : 0으로 값 초기화
* vector 생성 후에`reserve()` 써서 속도 빠르게 하는 것 좋다.

### 기본 함수
`push_back()` : 삽입
`pop_back()` : 삭제
`reserve()` : 공간 할당 하기
`capacity()` : **할당된** 요소의 공간 수
`size()` : 실제 들어있는 요소의 수
`insert(iterator, value)` : value를 특정 위치에 삽입
`erase(iterator)` : 특정 위치의 요소 삭제
`assign(num, value)` : vector를 value로 num 만큼 할당하기
`swap(vector)` : vector 교환하기
`resize()` : 
`clear()` : 모든 요소 제거, 크기 0이지만, 용량은 그대로

### 사용 예시

#include #include using namespace std;

int main() { vector vec1; vector vec2;

vec1.reserve(10);
vec1.push_back(10);
vec1.push_back(20);
vec1.push_back(30);

vec2.assign(11, 100);

//순차적으로 출력
for (vector<int>::const_iterator it = vec1.begin(); it != vec1.end(); ++it)
{
    cout << *it << endl; //10 20 30
}
cout << "\n";

//역으로 출력
for (vector<int>::reverse_iterator it = vec1.rbegin(); it != vec1.rend(); ++it)
{
    cout << *it << endl; //30 20 10
}
cout << "\n";

//vector 교환
vec1.swap(vec2);
for (vector<int>::const_iterator it = vec1.begin(); it != vec1.end(); ++it)
{
    cout << *it << endl; //100 100 100 100 100 100 100 100 100 100 100
}

//vector 지우기
vec1.clear();
cout << vec1.size() << " " << vec1.capacity() << endl; //0 11
cout << "\n";

//특정 위치 삽입
vector<int>::iterator iter = vec2.begin();
vec2.insert(iter + 1, 100);

for (vector<int>::const_iterator it = vec2.begin(); it != vec2.end(); ++it)
{
    cout << *it << endl; //10 100 20 30
}
cout << "\n";

}

### 추가
* 포인터 벡터

## 3. List
### 특징
* double linked list와 같은 구조
* 삽입과 제거 O(1), 메모리 연속으로 존재하지 않음
* 탐색이 느림, 임의 접근 불가능
### 사용 함수
`push_front()`
`push_back()`
### 사용 예시

#include #include using namespace std;

int main() { list scores; scores.push_back(10); scores.push_back(20); scores.push_front(30);

list<int>::const_iterator it = scores.begin();

for (; it != scores.end(); ++it)
{
    cout << *it << endl; //30 10 20
}

}

## 4. Map
### 특징
* key와 value의 쌍을 저장하는 자료구조
* key를 기준으로 정렬된다. -> 이진 탐색 트리 기반
* 시간복잡도 O(logN) -> 탐색 속도는 vector보다 빠르다.
* 만들면 자동으로 정렬된다.
* 해쉬맵이 아니다.
### 사용 함수
`insert()` : key와 value값 삽입
-> 이미 있는 key 값을 insert 하면 false 반환한다.
`[]` operator : 참조 반환
-> 없는 키를 쓰면 새 요소 삽입, 있는 키값이면 덮어쓰기  
`find()` : key값을 찾으면 해당 key 가지는 iterator 반환
`swap()` : 두 map의 key와 value 바꾸기
`clear()` : map 비우기
`erase()` : 한 요소 제거

### 사용 예시

#include

int main() { map<string, int> Scores; Scores.insert(pair<string, int>("A", 100)); Scores.insert(pair<string, int>("B", 80)); Scores.insert(pair<string, int>("C", 50));

Scores.insert(pair<string, int>("C", 10)); //false
Scores["D"] = 30;

cout << Scores["A"] << endl; //100
cout << Scores["C"] << endl; //50
cout << Scores["D"] << endl; //30

//복사 생성자
map<string, int> copyScores(Scores);

for (map<string, int>::iterator it = copyScores.begin(); it != copyScores.end(); ++it)
{
    cout << it->first << " " << it->second << endl;
}

map<string, int>::iterator it = Scores.find("A");

if (it != Scores.end()) // 찾았을 때 -> 못찾으면 end iterator 반환
{
    it->second = 99;
}
cout << Scores["A"] << endl; //99

Scores.swap(copyScores);

cout << copyScores["A"] << " " << Scores["A"] << endl; //99 100

}

### 참고
* map에 내가 만든 class를 넣는 경우
  * 해당 class의 key를 비교하는 operator나 compare 함수를 구현해야함
* 사용 예시

class Player { public: Player(int s,int i, string n) :Score(s) ,ID(i) ,Name(n) { } bool operator<(const Player& other)const //operator 구현 { return this->getScores() < other.getScores(); } int getScores() const { return this->Score; } string getName() const { return this->Name; } private: int Score; int ID; string Name; };

class PlayerCompare //compare 함수 구현 { public: bool operator() (const Player& left, const Player& right) const { return (left.getScores() < right.getScores()); } };

int main() { Player p1{ 100, 1, "AAA" }; Player p2{ 50, 2, "BBB" };

//operator 연산자                              
map<Player, string> test;
test.insert(pair<Player, string>(p1, "aaa"));
test.insert(pair<Player, string>(p2, "bbb"));

cout << test[p1] << " " << test[p2] << endl; // aaa bbb

//compare 함수
map<Player, string, PlayerCompare> test2;
test2.insert(pair<Player, string>(p1, "aaa"));
test2.insert(pair<Player, string>(p2, "bbb"));

for (map<Player, string>::iterator it = test2.begin(); it != test2.end(); ++it)
{
    cout << it->first.getName() << ", " << it->second << endl; //BBB bbb AAA aaa
}

}

## 5. Unordered_map
### 특징
* 정렬안된 map
* 해쉬로 구현되어서 일반 map 보다 빠르다.
* 특정값이 해쉬함수를 거쳐 index가 되고 bucket에 index를 통해 O(1)의 검색시간 가능하다.
  * 그러나 bucket 때문에 메모리 사용량은 증가
* 해쉬 함수는 충돌이 나지 않게 만드는 것이 중요하다.
* **해쉬 충돌이 생기지 않는 해쉬맵**
  * Closed Addressing (Chaining)
    * 충돌이 발생하면 같은 버킷에 여러 항목을 저장하는 방법
  * Open Addressing
    * 충돌이 발생하면 다른 빈 버킷을 찾는 방법
### 사용 예시

참고 프로퍼티 리플리케이션 : https://docs.unrealengine.com/4.27/ko/InteractiveExperiences/Networking/Actors/Properties/ 프로퍼티 지정자 : https://docs.unrealengine.com/4.27/en-US/ProgrammingAndScripting/GameplayArchitecture/Properties/Specifiers/ 조건식 리플리케이션 : https://docs.unrealengine.com/4.27/ko/InteractiveExperiences/Networking/Actors/Properties/Conditions/ 아키타입 : https://coding-hell.tistory.com/81 언리얼 엔진 네트워킹 : https://docs.unrealengine.com/5.3/ko/networking-overview-for-unreal-engine/

프로퍼티 지정자

• 엔진 및 에디터의 다양한 면에 대한 프로퍼티 작동방식을 지정하기 위해 UProperty 를 선언할 때 사용되는 키워드
• 사용 예시 1)

  UPROPERTY(EditAnywhere, BlueprintReadOnly, meta = (AllowPrivateAccess = "true"))
  class UWidgetComponent* OverheadWidget;

• 아키타입(내가 만든 블루프린트 클래스, c++클래스)과 인스턴스(bp와 c++ 클래스를 맵에 배치한 것) 둘 다 편집 가능

• 블루프린트에서는 수정 불가능

• 해당 변수는 클래스 내부에서만 접근 가능함

• 사용 예시 2)

  UPROPERTY(ReplicatedUsing = OnRep_OverlappingWeapon)
  class AWeapon* OverlappingWeapon;

• 네트워크 상에서 변수 값을 동기화 하는데, 해당 변수가 변경될 때 함수 OnRep_OverlappingWeapon 를 호출한다.

프로퍼티 리플리케이션

• 서버는 replicate된 프로퍼티의 값이 변할 때 마다 각 클라이언트에 업데이트를 전송, 클라이언트는 액터의 로컬 버전에 적용
• 프로퍼티 구성 1) 헤더에 UPROPERTY(replicated) 사용 2) 액터 클래스 구현부에GetLifetimeReplicatedProps 함수 구현 필요

• DOREPLIFETIME(클래스 이름, 변수 이름); 매크로 사용 3) 액터 생성자에 bReplicates = true; 설정

• 결과로 리플리케이트로 지정된 값이 바뀐다면 나머지 클라이언트에도 다 바뀐걸로 적용된다.

  조건식 리플리케이션

• 프로퍼티가 리플리케이션에 등록되면 해제시킬 수 없기 때문에 가급적 많은 정보를 넣고 다수의 접속에서 공유하여 시간 절약을 할 수 있다.
• DOPERPLIFETIME_CONDITION 매크로 사용
• 사용 예시
• 목표 (weapon에 닿았을 때 자신의 화면에서만 widget을 끄기/켜기 를 반복하기 위해서) 1) 위젯은 자신의 화면에서만 보고 싶다. simulated 에서는 보여줄 필요 없다. 2) 조건식 매크로에 COND_OwnerOnly 쓰면 pawn을 움직인 당사자의 화면과 서버에 변경된 점이 적용된다. 3) 서버에서 안보이게 하기 위해서는 replicated 될 때만 바뀌게 만들었는데, 이렇게 되면 서버의 경우 위젯이 뜨지 않는다.
• 결과 영상 https://youtu.be/vspiWPZq5m0

참고) property

참고 자료 델리게이트: https://docs.unrealengine.com/4.27/ko/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/Delegates/#%EB%8D%B8%EB%A6%AC%EA%B2%8C%EC%9D%B4%ED%8A%B8%EC%84%A0%EC%96%B8%ED%95%98%EA%B8%B0 다이나믹 델리게이트 : https://docs.unrealengine.com/4.27/ko/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/Delegates/Dynamic/ 멀티캐스트 델리게이트 : https://docs.unrealengine.com/4.27/ko/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/Delegates/Multicast/

델리게이트 (Delegate)

1. 델리게이트란

• C++ 오브젝트 상의 멤버 함수를 가리키고 실행시키는 데이터 유형
• 특징
  • heap에 메모리 할당된다.
  • 가급적 참조 전달 하기
• Delegate로..
  • C++ 오브젝트 상의 멤버 함수 호출을 안전하게
  • 임의 오브젝트의 멤버 함수에 동적으로 바인딩 & 오브젝트에서 함수 호출 가능 (호출하는 곳에서 오브젝트의 유형 몰라도 된다

    2. 델리게이트 선언하기

• 선언 매크로를 사용하여 선언한다.

  3. 델리게이트 바인딩하기

• UObject나 shared pointer 클래스 멤버에 바인딩 하는 경우 weak reference 유지

• 오브젝트가 소멸된 경우 IsBound() 함수를 통해 처리 가능

  4. 델리게이트 실행하기

• 함수
  • Execute()
    • 델리게이트에 바인딩 된 함수를 실행
    • 바인딩 되어있는지 체크하고 실행해야 한다!

    • 초기화되지 않은 상태로 접근 가능한 반환값과 출력 파라메터가 델리게이터에 있을수 있기 때문

  • ExecuteIfBound()
    • 반환값이 없는 델리게이트 안전 체크
  • IsBound()
    • 델리게이트를 실행해도 안전한지 체크

5. Dynamic Delegate

• Serialize 가능하며, 함수를 이름으로 찾을 수 있지만, 일반 델리게이트 보다는 느리다.
• 선언
• 바인딩
• 실행 : 일반 델리게이트와 같다.

6. Multicast Delegate

• 여러 함수에 바인딩 시켜 실행시킬 수 있는 델리게이트
• 선언 : MULTICAST만 붙이면 된다.
• 바인딩
• 실행
  • 여러 함수 델리게이트를 attach 한 다음 Broadcast() 함수를 통해 모두를 동시에 실행한다.
  • 아무것도 바인딩 되어있지 않아도 문제없다.

  • 델리게이트를 사용하여 출력 변수를 초기화 시킬 때는 위험할 수 있다.

  • Broadcast() 호출 시 함수의 실행 순서는 정의되지 않는다.

    7. 사용 예시

• 커스텀 델리게이트
• 선언
  • FOnCreteSessionComplete 델리게이트 정의
• 바인딩
• 사용 (멀티캐스트 델리게이트 이므로 Broadcast() 함수 사용)

(참고) Serialization

언리얼 오브젝트 처리 (UObject 시스템) : https://docs.unrealengine.com/4.26/ko/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/Objects/Optimizations/

• serialization란 언리얼 오브젝트를 한번에 안전하게 전달하는 것
• 다이나믹 델리게이트에서는 동적으로 메소드를 바인딩하기 때문에 serialization 특성이 필요하다.
• 다이나믹 델리게이트는 serialize 특징 덕분에 블루프린트에서 사용 가능하다??

• wireless network 구조

  • 무선랜 access network
    • AP(Access Point)가 존재
    • 중계해주는 역할
  • 이동통신망 access network
    • BS(Base Staion) 기지국 존재

• wireless links 들의 특징

  • wifi는 범위는 좁지만 속도는 빠름
  • bluetooth는 범위도 좁고 속도도 느림
  • 이동통신망은 범위가 넓다.

• wireless network의 동작 mode

  • infrastructure mode
    • 공유기와 같은 인프라의 도움을 받아서 데이터를 주고받음
  • ad hoc mode
    • 기지국과 같은 것이 존재하지 않음

      2. Wireless

• 무선 네트워크의 특징

  • 무선 링크의 에러 발생확률이 높다
  • 사용자의 이동성이 크다

• 이동통신망의 연결 동작 방식

  • handoff : 하나의 cell에서 거리가 멀어저 BS와 연결이 끊어지면 다음으로 가까운 cell의 BS와 연결된다.

    2-1. Wireless Links and network characteristics

• Wireless Link Characterisitics

  • 신호 감소 (path loss)
  • 다른 시스템의 영향을 받음 (interference)
  • sender가 방사형으로 신호를 전파함 -> 이 특성으로 인해 receiver는 다양한 시간대의 data를 수신받아 원래의 모양과 다른 신호를 수신받게 된다.
  • SNR이 클수록 좋은 신호!
    • SNR이 높다면 BER이 낮아진다. / SNR이 고정되어있다면 BER이 가장 작은 것을 선택하기
    • SNR (Signal to Noise Ratio)
      • $SNR = \frac{S}{N}=\frac{신호전력}{잡음전력}$
    • BER (Bit Error Rate)
  • Hidden Terminal Problem
    • CSMA 가정
    • A->B 전송함에 있어서 idle 상태이므로 전송을 함
    • C->D 전송함에 있어서 idle 이므로 전송을 하지만 C의 전송범위는 B까지 포함하기 때문에 C->D를 수행하는 순간 B에서 충돌이 발생한다.

      2-2. WiFi: 802.11 wireless LANs

• 정의

  • 공식 무선랜 표준
  • wifi라는 용어는 표준을 통과했을 때 주는 인증표시를 말한다.

• 802.11 LAN 구조

  • infrastructure 모드일때는 BS(=AP)의 도움을 받아 통신한다.
  • BSS(Basic Service Set)

• 802.11: Channels, association

  • AP의 admin이 사용할 수 있는 주파수를 선택하는 방식 -> 채널을 scan 하고 beacon을 들으면서 AP를 선택함 (DHCP)

  • scan의 방식

    • passive
      • 모바일 기기는 아무것도 하지 않음
      • 각 주파수마다 beacon을 보내는지 아닌지 확인
      • 연결이 필요할 때 request 보냄 (association request)
      • response 오면 연결 (association response)
    • active
      • AP가 있는지 probe request
      • probe response
      • association request
      • association response

  • 802.11 다중접속

    • CSMA/CA (2-frame)

      • DIFS 동안 idle 인지 확인함
      • idle 이면 전송 시작
      • busy라면 끝날때 까지 기다림
      • DIFS 동안 idle인지 확인
      • idle 이면 backoff 실행->작은 backoff 한 station이 전송 시작

    • RTS, CTS 방식(4-frame) -> hidden terminal 방지

      • A->B 과정에서 RTS를 통해 A의 전송범위에 broadcast
      • B는 CTS 응답주면서 B의 전송범위에 broadcast
      • A->B data 전송 & B->A ack 전송

• 802.11 frame: addressing

  • head에 주소가 4개인 이유는 아래 정보들를 담아야 하기 때문
    • 보내는 station의 주소
    • AP의 주소
    • 도착지 station의 주소
    • ad hoc mode를 위한 주소

• 802.11: mobility within same subnet

  • 한 subnet 아래 bss에서는 이동해도 커버가 가능하다. (작은 범위의 이동성)
  • bss1->bss2로 이동하는 것은 이동할 때마다 association을 하기 때문에 해당 기기가 이동했는지 알 수 있다.

• 802.11: advanced capabilities

  • rate adaptation
    • 와이파이의 연결상태가 좋으면 고속으로 전송하고 그렇지 않다면 저속으로 전송하는 시스템
    • 자동으로 해줌, 저속으로 전송하는 이유는 bit error를 줄이기 위해서
  • power management
    • 베터리에 의존하기 때문에 power관리를 해야함!
    • node to AP : node가 자신은 sleep 할거라고 AP에게 알려주어서 해당 node에게 전송할 필요 없게 되어 power를 save한다.
    • beacon frame : AP가 보낸 list를 확인해서 자신이 받을 packet이 없다면 해당 기기는 쉬기

• 용어
  • node : host & router
  • frame : 2계층에서 packet을 부르는 말
  • link : source에서 destination을 가는 동안 존재하는 경로에서 router와 host를 연결하는 것들을 말한다.
• link layer이 제공하는 services
  • framing, link access
    • channel access : 경쟁을 통해 channel 확보하기
    • MAC 주소 : 2계층만의 고유한 주소값, 시작점과 도착지의 정보
  • flow control
  • error detection
  • error correction
  • half duplex and full duplex
• link layer는 NIC(Network Interface Card) 에 구현되어있다.

  2. Error detection, correction

• Error detection
  • EDC : error detection과 correction을 하는 bits
• Parity Checking
  • single bit parity
    • 짝수나 홀수 패리티 방식을 통해 1의 갯수를 측정하여 error를 찾아낸다
    • 그러나 한번에 한개의 비트가 아닌 여러개의 비트 error가 생긴 경우 문제를 해결하지 못한다.
  • two-dimensional bit parity
    • 행과 열 두개로 패리티를 구성하여 두 번의 체크를 통해 error를 찾아낸다.
• CRC(Cyclic Redundancy Check)
  • 용어
    • D는 data bit
    • R은 CRC bit, 크기는 r bits
    • G는 bit pattern(generator), r+1 bits
  • 구조
  • 계산
    • $\frac{<D,R>}{G}$ 의 결과가 나머지가 없어야 error가 없다고 판별!
    • $<D,R> = D*2^r$ XOR $R$
      • 이때 $D*2^r$은 r비트만큼 왼쪽으로 shift 하는 결과
    • 결론적으로 우리가 구하는 것은 R이고 $\frac{D*2^r}{G}$의 나머지가 $R$이다.
  • 예시
    • D=[101110], G=[1001], r=3(G의 크기로부터 알수있음)
    • $R = \frac{D*2^r}{G}$의 나머지
      • $D*2^3 = 101110 000$
      • $\frac{D*2^r}{G}=$ 몫: 101011 나머지: 011
      • 101110 011 은 1001로 나눠떨어지게 된다.

        3. Multiple access protocols

• 2계층 프로토콜의 핵심 기능 중 하나
  • link의 두가지 타입
    • point to point : one server one receiver
    • broadcast
• 그렇다면 하나의 공유하는 broadcast channel을 어떻게 분배할 것인가! (channel의 사용권 결정하기)
  • 이상적인 경우
    • MAC(Multiple Access Channel) of rate Rbps
    • M개의 노드가 있다면,,, R/M으로 나누기
    • 완전히 분산된 시스템이다. 동기화나 정지하는 마스터 노드가 없다. 단순하다는 장점은 있다.
• MAC protocol의 종류
  • channel partitioning
    • 채널을 작은 조각들로 나누기
    • 안쓰는데 1/M으로 나눠진 것들은 낭비가 된다.
  • random access
    • 사용권을 경쟁을 통해 획득
    • 가장 많이 쓰는 방식
  • taking turns
    • 경쟁없이 돌아가면서 쓰는 방식
• Channel Partitioning MAC Protocols
  • TDMA
    • 시간을 1/N으로 나누기
    • 각 frame을 고정된 길이로 나눈다.
  • FDMA
    • 대역폭을 1/N으로 나누기
• Random Access Protocol
  • 전송 노드는 항상 최대 전송률인 Rbps로 전송
  • 만약 충돌이 발생하면 랜덤한 시간동안 기다린 후 재전송을 진행한다.
  • Slotted ALOHA
    • 전제조건
      • 모든 frame은 같은 크기
      • 충돌이 발생하면, 성공할 때 까지 p의 확률로 재전송
        • 이때 확률 p로 재전송 하는것은 확률이 매우 치우친 동전던지기를 하는 것과 같다.
    • 특징
      • 장점 : 매우 분산적이며, 간단하다.
      • 단점 : 충돌이 발생하고, slot이 낭비된다. 충돌이 발생해도 해당 slot의 전송을 끊지 않고 계속 보냄
    • 효율성
      • 임의의 한 노드가 성공적으로 보낼 확률 : $Np(1-p)^{N-1}$
      • 최대 효율은 1/e = .37 (37%)
      • 충돌이 발생하지 않으려면, 전송 시작 전 slot에서 전송하려는 데이터 이외의 데이터가 발생하지 않으면 충돌이 발생하지 않는다.
  • Pure ALOHA
    • slot을 사용하지 않는 알로하, 동기화 작업 안함 -> 충돌이 더 많아진다는 문제점이 있다.
    • pure 알로하가 충돌이 발생하지 않으려면 1) data A가 전송하는데 걸리는 시간 T만큼 이전 기간동안 데이터가 발생하면 안된다. 2) data A를 전송하는 시간 T 동안 다른 데이터가 발생하면 안된다.
    • 효율성
      • 최대 효율이 18%
  • CSMA(Carrier Sense multiple Access)
    • channel을 쓰고 있는지 아닌지를 확인
      • 안쓰고 있다면(idle) 바로 데이터 전송
      • 쓰고 있다면(busy) 종료될 때 까지 대기
    • 이 방식은 충돌을 피하는 것은 불가능하다.
      • propagation delay가 길어지면(node와 node 사이가 멀어지면) 충돌 발생 가능성이 더욱 높아진다. -> 그래프의 기울기가 완만해 지는 것
      • 충돌이 발생하면 다른 node들이 전송을 할 수 없어서 낭비된다.
  • CSMA/CD(CSMA with Collision Detection)
    • 이더넷에서 쓰는 방식
    • 충돌이 검출되면 전송을 끊어버림
    • 알고리즘 1) network layer에서 datagram 가져와서 frame 만들기 2) Idle인지 busy인지 carrier sensing 수행 3) 전체에서 충돌 없다면 frame 보내고 종료 4) 다른 전송을 확인한 경우 -> abort
      • abort된 경우 binary exponential backoff 수행
      • m번의 collision 발생한 경우 -> K를 ${0,1,2,...,2^{m-1}}$에서 K를 선택
      • NIC는 K*512 bit time을 기다린 후 2)로 돌아감
        • if) R = 100Mbps -> 1 bit time = $10^{-8}sec$
      • 많은 충돌이 발생할수록 집합의 크기가 지수적으로 커짐
    • 효율성
      • $efficieny = \frac{1}{1+5\frac{t_{prop}}{t_{trans}}}$
      • propagation delay가 0일수록, transmit max-size frame 시간이 무한대에 가까울수록 효율성이 1과 가까워짐
      • 결론은 ALOHA보다 성능이 좋다
• Taking turns
  • polling
    • 중앙집중형, 마스터 노드가 RR 방식으로 polling 수행 -> master 노드가 다른 노드들에게 최대로 보낼 수 있는 프레임을 알려줌
    • 오버헤드, 한번에 다 고장난다는 문제점 있다.
  • token passing
    • token이라는 짧은 제어 message를 사용하는 방식
    • 즉 전송중인 노드는 token을 가지고 있는 방식
    • 그러나 token이 문제가 생길 수 있다는 단점이 있다.

      4. LANs

• IP address
  • network layer의 주소이다. 32bit, ex) 128.119.40.136
  • 3계층의 forwarding을 위해 사용
  • 위치에 따라 주소가 달라짐
• MAC address
  • link layer의 주소이다. 48 bit, ex) 1A-2F-BB-76-09-AD
  • 물리적으로 연결된 다른 인터페이스의 frame을 가져옴
  • 어뎁터의 MAC 주소는 위치에 따라 바뀌지 않음!!

    4-1. ARP (Address Resolution Protocol)

• 정의: IP주소와 MAC주소를 변환해주는 역할
  • ARP table : IP주소, MAC 주소, TTL 순서로 작성된다.
    • TTL(time to live): 대체로 20분으로 설정, 20분 동안 address mapping이 이루어지지 않으면 table에서 지워진다.
• ARP protocol (A와 B가 같은 subnet에 존재)
  • ARP table 비어있을 때 (A 기준)
    • 도착지 MAC 주소: FF-FF-FF-FF-FF-FF (전체에게 보낸다는 의미)
    • 만약 B가 해당 query에 응답한다면 MAC 주소를 다시 보냄
    • ARP table에 B의 IP 주소와 MAC addr, TTL을 적는다.
• ARP protocol (A와 B가 다른 subnet에 존재)
  • R이라는 라우터를 통해 B로 이동한다.
  • A의 목적지 MAC주소는 R의 인터페이스 MAC주소이고 목적지 IP 주소는 B의 IP 주소이다.
  • 이후 subnet과 subnet 간의 이동은 link layer의 역할이 아니다.
  • 다시 R의 전송 시작 주소는 R의 MAC주소이고 도착지 주소는 B의 MAC주소가 되어 A->R->B로 전달된다. IP 주소는 그대로

    4-2. Ethernet

• 선으로 연결된 근거리 통신망, 싸고 단편하다.
• topology
  • 이전에는 bus방식 썼지만, 충돌이 발생해서 switched 방식으로 바뀜
• frame structure
  • preamble: 동기화, 신호의 시작 알려주기
  • address: MAC 주소의 도착지
  • type: 2->3계층으로 옮기기 위한 protocol
  • CRC: error 검출
• 특징
  • connectionless
  • unreliable : 안정적인 전송 불가능
  • CSMA/CD 사용

    4-3. Switch

• 이더넷의 스위치는 스스로 알아서 동작함
  • transparent
  • plug and play, self learning
• multiple simultaneous transmission
  • host들은 스위치와 전용 direct 연결로 구성
  • collision 발생 안함 -> 각 경로가 full duplex이므로
    • A->A' B->B'은 동시에 일어날 수 있고 충돌도 안생김
    • 그러나 A->A'과 B->A'이라는 전송이 동시에 이루어지면 충돌 발생
• self learning
  • cf) IP의 forwarding table은 라우팅 프로토콜로 구성되며, 양이 매우 많다..(self learning 불가능)
  • MAC 주소는 IP에 비해 간단하므로 self learning이 가능하다.
    • 위의 그림처럼 A->A'를 지나간다면, 테이블을 채우고 다음 것을 진행하면서 테이블을 모두 채운다. (TTL : time to live 데이터의 유효기간)
    • 만약 drop time때까지 도착지에 도착을 못하면 drop 해버림
• 스위치와 라우터의 차이점
  • 스위치
    • link layer 장치이며, store-and-forward 진행
    • flooding, learning, MAC 주소를 통해 forwarding table을 만든다.
  • 라우터
    • network layer 장치이며 store-and-forward 진행
    • 라우팅 알고리즘을 통해 table 계산, IP 주소이용

      A Day in the life of a web request

• 참고 유튜브 https://www.youtube.com/watch?v=paT7cVt-ySQ

• Network-layer functions (Recap)
  • forwarding: data plane / 라우터 안에서
  • routing: control plane / 전체 경로상에서
• Per-router control plane
  • 기존에 쓰던 방식
  • 각 라우터당 라우팅 알고리즘 존재
• Software-Defined Networking control plane
  • 중앙 집중형
  • agent가 server에 존재

    2. Routing Protocols

• 출발지에서 목적지까지 "good" "path"를 결정하기
  • path
    • router packet의 sequence
    • initial source에서 destination host까지의 경로
  • good : 적은 cost (빠름, 혼잡x)
• Graph abstraction: link costs
  • $cost = \frac{1}{bandwidth}$ or $cost = \frac{1}{congestion}$
  • 각 링크 당 가중치를 cost로 생각하고 그래프 문제를 푼다.
    • 가중치가 무한대라면 직접 연결이 안된 경우
• Routing Algorithm Classification

  2-1. Link State

• 다익스트라 link-state 라우팅 알고리즘
  • 특징
    • centralized
    • iterative
  • notation
    • $C_{x,y}$ : x,y를 직접 연결한 link의 가중치
    • $D(v)$ : 목적지 v까지의 최소 비용
    • $p(v)$ : 목적지까지 가는길에 바로 직전의 노드
    • $N'$ : 최소비용경로가 알려진 노드
  • 알고리즘
    • $N'$에 자기 자신(시작) 노드를 넣고 시작해서 최소 비용인 노드들을 하나씩 넣다가 모든 노드가 $N'$에 들어가면 반복을 종료한다.
  • 목적지까지의 최소 비용 계산식
    • $D(v) = min(D(v), D(w)+C_{w,v})$
      • $D(v)$ : 기존값
      • $D(w)+C_{x,y}$ : 새로 비교하게 되는 값
  • 분석
    • 알고리즘 시간 복잡도
      • n개의 노드가 있을때 $O(n^2)$
      • $O(nlgn)$으로도 구현 가능
    • message 복잡도
      • 각 노드가 연결된 모든 노드에 정보를 전달해야함
      • $O(n^2)$
• Oscillations Possible
  • 네비게이션의 경로 추천 기능 처럼..
  • A경로가 빠를 때 A경로를 추천하지만, 점차 A경로가 포화상태가 되고 이후로는 B경로를 추천하게된다.

    2-2. Distance Vector

• Bellman-Ford equation (DP)
  • $D_x(y)=min_v{c_{x,y}+D_v(y)}$
• BF Example
• Distance vector algorithm
  • 다른 노드가 계산된 결과를 바탕으로 계속해서 업데이트하기 (다익스트라 알고리즘은 다른 노드의 정보 생각x)
  • "good news travels fast" : 더 좋은 값으로 바뀐 것은 더 빨리 다른 노드들로 전파된다.
  • "bad news travels slow" : count to infinity

    2-3. Comparison of LS and DV

• message complexity
  • LS : n개의 라우터 -> $O(n^2)$
  • DV : 수에 따라 달라짐
• speed of convergence
  • LS : global, $O(n^2)$
  • DV : distributed and iterative (LS보다 오래걸림)
• robustness
  • LS
  • DV : 잘못된 정보 한번에 모두가 잘못될 수 있다. (LS보다 보안이 취약함)

    3. Intra-ISP routing: OSPF

• making routing scalable
  • 이전까지는 라우터가 모두 동일한 것으로 생각했지만 실생활에서는 그렇지 않다.
  • 실제로는 모든 라우터들의 도착지를 테이블에 저장할 수 없으며, 각 ISP는 네트워크를 자신이 원하는 대로 운영하고 싶어한다. 이런 것들을 위해 "autonomous systems 으로 조직화 해서 운영한다!

    Autonomous Systems (aka domains)

  • Intra-AS
    • AS 내부의 동작
    • AS 내부에서는 같은 프로토콜로 동작한다.
    • gateway router 라는 다른 AS와 연결되는 link가 존재한다.
  • Inter-AS
    • AS와 AS간의 동작
    • 특정 AS에서 나가는 datagram이 있을때 어떤 라우터를 골라야 하는지는 연결된 AS를 보고 어디로 갈 수 있는지를 확인해 본 후 결정한다.
• Intra-AS routing
  • RIP(Routing Information Protocol)
    • classic DV 방식, 잘 안씀
  • EIGRP(Enhanced Interior Gateway Routing Protocol)
    • DV based
  • OSPF(Open Shortest Path First)
    • Link-State 라우팅
    • IS-IS protocol(OSPF와 유사)

      OSPF routing

• 특징
  • 라우팅 동작 방식이 공개되어있다.
  • classic link-state 방식으로 동작함
    • 링크 상태 flooding, 인접한 것 뿐만 아니라 모든 라우터에게 정보를 broadcasting
  • multiple link cost metrics : 동일한 비용을 가진 다른 링크를 이용할 수 있다. (분산시키기)
  • security : 모든 메세지를 인증을 통해 참여한다.
  • two-level hierarchy
    • backbone(inter AS 담당)->border(gateway 역할)->local 라우터

4. Routing Among ISPs: BGP

• Inter-AS routing 방식이기 때문에 전 세계에 하나만 존재한다.
• BGP(Border Gateway Protocol)
  • 라우터의 forwarding table의 목적지가 AS 외부에 있는 경우 필요한 프로토콜
  • eBGP(external BGP)
    • AS와 AS를 연결하는 BGP
  • iBGP(internal BGP)
    • 같은 AS 내의 라우터 간 BGP 연결
    • iBGP가 필요한 이유는 바깥에서 받아온 정보를 내부에 알려주기 위해서 이다

• BGP basics
  • BGP session
    • 두개의 BGP 라우터끼리는 반영구적인 TCP를 통해 연결한다.
  • 동작 예시 1) 위의 그림에서 AS3에서 x라는 데이터를 AS2에게 보내면 AS3, x라고 표시한다. 2) 이후 AS2는 AS1으로 전달하면서 x는 AS2를 거쳐 AS3로부터 왔다는 뜻으로 AS2,AS3,x 라고 표시한다.
• 경로 특성
  • prefix(목적지) + attributes(특성)의 형태로 전달
  • policy-based
    • use import policy
  • 특성의 종류
    • AS-PATH : 목적지 주소에 대한 배포가 어떤 주소를 거쳐서 왔는지
    • NEXT-HOP : AS-PATH를 시작하는 라우터 인터페이스의 IP 주소
• BGP advertisement
• BGP message
  • OPEN
  • UPDATE
  • KEEPALIVE
  • NOTIFICATION
• BGP path advertisement??
• Intra vs Inter AS
  • policy : inter AS의 경우 관리자가 라우팅되는 방법이나 누가 라우팅 하는지 등을 제어한다. intra AS는 단일 관리자이므로 정책이 의미 없다
  • scale : 계층 라우팅을 통해 사이즈와 트래픽을 줄인다.
  • performance : intra AS가 성능에 더욱 focus
• Hot potato routing
  • domain 내에서 비용이 가장 적은 local gateway를 선택하기
  • AS 바깥의 비용은 생각하지 않고 빨리 자신의 AS내에서 밖으로 보내는 것
• BGP: achieving policy via advertisements
  • 다른 ISP간의 transit traffic을 전달하지 않기 (X가 B와 C간의 트래픽을 전달하는 것을 막는 것이 목적)
  • X가 자신을 제외하고 다른 경로가 없다고 알려주어서 B에서 C의 경로를 막는다.
• BGP route selection 1) policy 따르기!, 지역 선호도 2) 짧은 AS-PATH 3) 가까운 NEXT-HOP, 뜨거운 감자 4) 다른 기준들

  5. SDN control plane

• 왜 control plane을 centralized 했을까
  • network mangement를 쉽게 하기
  • programming이 쉽다.
  • open 해서 기술의 발전을 도모
• Traffic engineering
  • 과거의 방식
    • 가중치를 분산시키기 위해 source에서 destination 까지의 경로를 다양하게 구성하는 것이 어렵다.
    • load balancing 구현 어렵다.
    • 특정 지점을 지나서 가는 경로를 만들도록 구현하기가 어렵다.
  • SDN
    • 과거의 방식에서 불가능한 것을 할 수 있게 되었다.
    • SDN은 hardware/controller/application 세가지로 분류하여 동작한다.
      • dataplane switches
        • hardware에 구현된 dataplane forwarding을 위한 switch
        • openflow를 통해 control plane과 정보를 주고받음
      • software controller(network OS)
        • network의 상태 체크하는 역할
        • sounthbound API를 통해 switch들과 상호작용하며, northbound API를 통해 application들과 상호작용한다.
      • network-control apps
        • unbundled 한 특성 (각각 하는 기능이 따로 나누어져 있다)
• OpenFlow protocol
  • 세가지 메세지 종류
    • controller to switch
    • asynchronous (switch to controller)
    • symmetric
  • controller-to-switch message(flow table 세팅을 위한 메세지)
    • features: controller가 질문하고 switch가 응답함
    • configure
    • modify state: openflow table 수정
    • packet-out: controller가 제어하는 스위치의 지정된 포트에서 특정 패킷을 내보낸다.
  • switch-to-controller message
    • packet in: packet을 controller에게 전달
    • flow-removed: flow table entry를 삭제한다.(시간 만료나 modify state 메세지 수신한 경우)
    • port status: 스위치가 port의 상태를 controller에게 알리기
• 다익스트라 LS가 SDN으로 동작하는 예시
• SDN의 문제점
  • 중앙집중형이므로.. 한번에 고장남

    6. Internet Control Message Protocol

• ICMP
  • host와 라우터의 통신할때 사용 (3계층에서-network layer)
  • error reporting 할때 많이 사용한다.
• Traceroute and ICMP
  • 출발지에서 도착지까지의 경로 구하기(출발지와 목적지 사이의 라우터 이름과 주소를 알아내기)
  • 도착지에 도달하면 "port unreachable" 메세지를 통해 도착지에 도달한 것을 알 수 있다.

    7. Network Management, configuration

• skip*

• network layer의 sevice 와 protocols
  • sender는 segments(transport layer의 packet)를 encapsulate 하여 datagram(network layer의 packet)으로 만들어서 보내기
  • receiver는 segment 를 추출해서 transport layer로 보내기
• network-layer functions
  • forwarding
    • 라우터 안에서 패킷을 적절한 output 링크로 보내주기
    • data plane과 관련!
  • routing
    • 패킷 경로를 설정하기
    • control plane과 관련!

      1-1. data plane

• local, per-router function
• forwarding table을 통해 router의 input port로 들어온 datagram이 적합한 output port로 나가도록 하는 것

  1-2. control plane

• network-wide
• 전체 packet 전송 과정에서 source에서 destination으로 갈 때 어떤 경로를 통해 갈 것인지 설정
• two control-plane approaches
  • 전통적인 방식 : 라우터에 구현하기
  • SDN (software-defined networking) : routing 기능을 별도의 서버에 구현하기

1-3. network service model

• 정의 : 송수신 호스트 간 패킷 전송 특성
• 서비스의 예시..
  • 보장된 전달
  • 지연 제한 이내의 보장된 전달
  • 순서화 패킷 전달
  • 최소 대역폭 보장
  • 보안 서비스
• best effort service
  • 보장된 것이 없는 서비스
    • 순서 보장 x
    • 전송 자체 보장 x
    • 지연, 최소 대역폭 보장 x
• cf) QoS (Quality of Service)

  2. What's inside a router

  2-1. input ports, switching, output ports

  전체적인 모습
• Input Ports
  • line termination : physical layer의 값 처리 (bit level)
  • link layer protocol
  • look up, forwarding queueing (decentralized switching)
    • 검색기능 (header를 통해 output찾기)
    • destination-based forwarding
      • 목적지 주소를 보고 forwarding 하기
      • 주소값의 범위를 가지고 앞에서부터 비교해서 어느 지점까지 확인해서 output 링크를 정하는 방식
      • Longest prefix matching
        • 비교한 것이 같을 때 처리하는 방식
        • 가장 길게 matching 되는 것 선택하기
        • TCAMs 라는 메모리 사용함 (빠르다)
    • generalized forwarding
      • 다른 정보를 추가로 활용한 forwarding
• Switching
  • 정의 : input 링크로 들어온 packet을 올바른 output 링크로 연결하는 것
  • switching rate
  • 많이 사용하는 방식 세가지
    • memory
      • 입력포트와 출력포트를 연결하는 system bus에 있어서 메모리라는 중간 매개체를 이용
      • packet이 system memory로 복사된 후 보내진다.
      • 복사를 해야하기 때문에 속도가 느리다.
    • bus
      • 공유하는 하나의 bus를 사용
      • 동시전송이 안되고, 하나의 input을 처리할때 bus를 독점해야 한다.
    • interconnection network
      • 동시에 통신을 가능하게 하는 방법
      • multistage switch
        • nxn switch 사용
      • exploiting parallelism
• Output Ports
  • cf) Input Port queuing
    • 입력 대비 switch가 느리게 동작하는 것을 방지하기 위해 존재
    • Head-of-the-Line blocking
    • 가끔 발생할 수 있는 일을 방지하기 위해 존재함
  • Output Port Queuing
    • buffering : 꽉 찼을때 버리기
    • scheduling discipline : 우선순위를 통해 큐에서 보낼 것 정하기

      2-2. buffer management, scheduling

• Buffer Management
  • drop : packet을 버리는 방식
    • tail drop: 맨 뒤에(꼬리)에 있는것 버리기
    • priority: 우선순위 정해서 버리기
  • marking : 마킹해두기
    • ECN, RED
• Scheduling
  • FCFS : first come first served (먼저 온 것 먼저 보내기)
  • Priority : 헤더를 통해 우선순위 구별하기
    • low pri와 high pri가 존재해서 low 의 경우 high가 모두 보내진 다음 보내게 되어있다.
  • Round Robin
    • 큐의 우선순위에 따라 돌아가면서 쓰는 방식
    • 각 큐는 같은 가중치를 가진다.
  • Weighted fair queueing
    • RR의 진화된 방식 -> 많이 사용되는 큐의 가중치를 더 많이 주어서 더 많이 반복되게 한다!
    • 최소 bandwidth가 보장된다.
    • QoS를 지킨다.

      3. IP: the Internet Protocol

• Network Layer: Internet

  3-1. datagram format

  

  3-2. addressing

• Intro
  • IP address: 라우터나 호스트를 구별하기 위한 식별자
  • Interface : 호스트와 물리적 링크 사이의 경계
• Subnets
  • 라우터 없이 물리적으로 서로에게 도달할 수 있는 장치 인터페이스
  • subnet 주소 예시
• CIDR(Classless InterDomain Routing)
  • subnet 주소체계 표기를 일반화 하기
  • a.b.c.d/x의 형식
    • x는 subnet 주소의 길이를 알려줌
• DHCP(Dynamic Host Configuration Protocol)
  • 서버로부터 동적으로 IP 할당받기
  • 동작 과정
    • DHCP discover를 통해 DHCP 서버 존재여부 확인
    • DHCP offer를 통해 사용할 수 있는 IP 주소 알려줌
    • DHCP request를 통해 사용하겠다고 알려줌
    • DHCP ACK을 통해 IP 주소 사용 확인
  • IP 주소뿐만 아니라 첫번째 홉 라우터의 주소나, DNS서버의 정보 network mask등의 정보도 DHCP가 준다.
• how to get IP address?
  • IP 주소의 subnet part의 경우는 주소를 바꾸지 못한다.
  • 그 뒤에 수정 가능한 부분을 수정하기
• Hierarchical addressing
  • route aggregation
  • IP 주소가 ~ 로 시작하는 것끼리 묶어두어 더 효율적으로 addressing 할 수 있다.
  • 여기서도 long dest prefix에 따라 동작하므로, 만일 1번 ISP의 Organization이 2번으로 간 경우라도 제대로 동작한다.

    3-3. NAT(Network Address Translation)

    
• 정의 : 바깥세상(rest of Internet)으로 나갈 때 사설IP를 진짜 IP로 변환해주는 것
• port# 를 통해 사설 IP를 구별한다.
• cf) NAT는 network 계층인데, port#(transport layer)를 건드리는것은 원칙은 아니지만, 동작하는데 문제없어서 그냥 쓰고 있다.

  3-4. IPv6

• IPv6가 나오게 된 동기
  • IP 주소의 고갈 (IPv6 -> 128bit)
  • speed processing (빠른 처리와 forwarding, IP packet 단순화) -> 간소화된 header
  • 서로 다른 flow에서 서로다른 network 처리 (QoS)
• datagram format 특이점 (IPv4와 차이점)
  • no checksum, fragmentation, options
• tunneling
  • IPv4를 IPv6로 전환하는 과정!
  • IPv6를 IPv4처럼 캡슐화 해서 진행
    • 예를들어 A->F 경로 중 C,D가 IPv4 터널일때 B->E까지의 경로로 캡슐화해서 진행

      4. Generalized Forwarding, SDN

      4-1. Match+Action

• 정의
  • Match : 목적지의 IP 주소를 찾기
  • Action : 패킷을 지정된 출력 포트로 전송
• Generalized forwarding vs. Destination based forwarding
  • destination based forwarding은 오직 도착지 주소만 가지고 수행하지만, generalized 는 다양한 헤더들을 통해 action을 수행한다.
• Flow table(forwarding table)
  • flow : 헤더값에 정의되어 있다.
  • generalized forwarding
    • match
    • action : drop, forward, modify 등등
    • priority : 중복 제거?
    • counters : 얼마나 사용했는지

      4-2. OpenFlow: match+action in action

• 간단한 forwarding 예시
• load balancing
• firewall
• 요약
  • router
    • match: 가장 긴 도착지 IP prefix
    • action: forward out a link
  • switch
    • match: 도착지 MAC 주소
    • action: forward or flood
  • firewall
    • match: IP 주소, TCP/UDP 포트#
    • action: permit or deny
  • NAT
    • match: IP 주소, port#
    • action: 주소와 port 다시 쓰기

      5. Middleboxes

• RFC 3234: "출발지 호스트와 목적지 호스트 사이의 데이터 경로에서 IP 라우터의 정상적이고 표준적인 기능과는 별도로 기능을 수행하는 모든 미들박스"
• Middlebox의 역할
  • NAT
  • 보안 (Firewall, IDS)
  • 성능 향상 (Load balancer, Cache)
• "whitebox" hardware
  • network를 sw화 해서 범용으로 쓸 수 있게 만들었다.
  • SDN
  • NFV(Network Functions Virtualization)
    • whitebox위에 어떤 sw를 설치하는가에 따라 다른 역할을 할 수 있도록 만들기
  • IP hourglass
    • 초기 : IP 가 유일한 network layer protocol
    • 중기 : IP, NAT, caching, NFV, Firewall (middle box 들)
• 결론은 Internet의 core를 simple하게 만들고, 복잡한 것들은 Internet edge에 배치하기

<segment structure & reliable data transfer>

1. TCP overview

• point to point (1:1 통신)
  • cf1) 1 : 모두 -> broadcast
  • cf2) 1 : 다수 -> multicast
• reliable, in-order byte stream
• full duplex data
  • 하나의 링크를 통해 데이터 보내고 받기 수행
• cumulative ACKs
• pipelining
  • congestion and flow control
• connection-oriented
• flow controlled

2. TCP segment structure

• source port, dest port
• seq #
• ack #
• checksum
• receive window : for flow control
• C,E : congestion 알려주는 것
• data

  3. TCP sequence numbers, ACKs

• telnet?

  4. TCP round trip time, timeout

• timeout값을 정하는 기준
  • RTT의 평균보다는 큰 값
  • 너무 작으면 성급한 timeout 발생
  • 너무 크면 반응이 느려짐
• RTT 측정
  • sampleRTT : segment를 받은 시간부터 해당 segment에 대한 ACK이 오기 전까지 시간
  • sampleRTT는 불규칙하다!
  • 해결 : sampleRTT의 평균치 구하기 -> EstimatedRTT
• EstimatedRTT
  • $EstimatedRTT=(1-\alpha)EstimatedRTT + \alphaSampleRTT$
• exponential weighted moving average (EWMA)
  • 최근 sample에 대한 값의 우선순위 주기!
  • 더 smooth 한 결과를 얻을 수 있다.
• timeoutInterval
  • $TimeoutInterval = EstimatedRTT+4*DevRTT$
  • 4*DevRTT는 safety margin (여윳값)
• DevRTT(RTT변화율, 표준편차)
  • $DevRTT = (1-\beta)DevRTT+\beta|SampleRTT-EstimatedRTT|$
  • sample이 평균으로부터 얼마나 떨어져있는가..

    5. TCP sender

• application으로 부터 data받기
• timeout
• ACK received

  6. TCP receiver

• arrival in-order
• out of order

  7. TCP: retransmission scenarios

• lost ACK
• premature timeout
• cumulative ACK covers for earlier lost ACK

<flow control & connection management>

8. TCP flow control

• Congestion control 이랑 다른것
• 수신하는 application의 읽는 속도와 송신자가 전송하는 속도를 같게 하는 것
• TCP segment structure에 존재하는 receive window 사용
• 과정
  • receive window는 수신측에서 가용한 버퍼 공간이 얼마인지 송신자에게 알려준다.
  • 수신자는 수신 받을 것이 생기면 수신 버퍼(RcvBuffer)를 할당한다.
  • 수신버퍼에 저장된 번호 - 버퍼로부터 읽은 번호 <= RcvBuffer 인 경우를 유지해서 넘치지 않게 한다.
  • rwnd = RcvBuffer-(수신버퍼 저장된 번호 - 버퍼로부터 읽은 번호) 수식을 만족하는 동적인 공간이 존재한다.

    9. TCP connection management

• 데이터를 교환하기 전에 sender와 receiver가 handshake 하기
• 2-way handshake 쓰면 안되는 이유
  • variable delay
    • client는 timeout 발생했지만, server는 응답을 보낸경우 -> half open 상태
  • message loss & reordering
  • client와 server는 각자 다른 쪽의 상태를 모른다.
• 3-way handshake과정
  • SYN이라는 1비트 보내기(sent 상태), client_isn 선택하여 seq #에 넣기
  • server host는 TCP SYN 추출 / 다시 응답을 보낼때 SYN은 1로(receive상태) seq#는 server_isn으로 ACK#을 client_isn+1로 설정해서 보낸다.
  • 다시 client가 응답을 받으면 SYN은 0으로 seq#는 client_isn+1로 ACk#은 server_isn+1로 설정한다.

    6. Principles of congestion control

    1. introduction

• congestion : network가 처리하기에 너무 많은 양의 data가 들어옴
• long delay
• packet loss

  2. Causes/cost of congestion

  1. scenario 1: 2개의 송신자와 무한 버퍼 라우터 하나

• packet 손실 x, 라우터의 용량 R, throughput R/2
• 링크를 둘이서 공유해야 하므로 R/2가 최대 값
• packet이 불규칙적으로 들어오는 경우 R/2 부근에서 지연이 무한대가 된다.

  2. scenario 2: 2개의 송신자, 유한 버퍼 라우터

• retransmit lost, time-out packet
• 버퍼가 가득찬 상황에서 도착한 패킷은 버려짐 -> 재전송 필요
• 재전송을 하게되면 보내야 하는 양이 늘어남
• 종류
  • perfect knowledge
  • some perfect knowledge
    • retransmissions 때문에 끝에서 꺾인다.
  • un-needed duplicates

3. scenario 3: 4개의 송신자, 유한 버퍼 라우터, 멀티홉

3. Approaches towards congestion control

• congestion에 대한 정보는 network 계층이 가장 잘 안다. 그러나 network 계층은 혼잡 처리에 대해 아무일도 하지 않는다. -> host가 혼잡제어 하기
• End-End congestion control
  • network 계층의 피드백 없는 경우
  • RTT나 timeout을 통해 추론하기
• Network-assisted congestion control
  • router가 최소한의 피드백을 전해준다.
  • ex) TCP ECN

    7. TCP congestion control

    1. TCP congestion control: AIMD

• Additive Increase Multiplicative Decrease
• Additive Increase
  • 시간에 따라 선형적으로 네트워크에 주입되는 data양을 늘리기
  • AI 수행 후 MD 수행
• Multiplicative Decrease
  • 혼잡이 생긴 부분에서 data양을 확 줄이기
  • MD 수행 후 다시 AI 수행

    2. TCP overview

• TCP 혼잡의 증상 1) timeout (2번보다 심각한 문제) 2) 3 duplicate ACKs
• TCP Tahoe
  • 가장 초기의 TCP
  • TCP혼잡 증상인 1,2에 대해 모두 동일하게 처리
  • sending rate를 1로 돌아가서 다시 올라오기
• TCP Reno
  • 1의 경우는 Tahoe처럼 처리
  • 2의 경우는 congestion 값 * 0.5에서 다시 시작하기

    3. TCP congestion control: details

• CWND : receiver에 상관없이 sender가 보낼 수 있는 최대 값
• TCP rate (throughput) = $\frac{CWND}{RTT}bytes/sec$
• (LastByteSent - LastByteACKed) <=CWND

4. TCP slow start

• TCP rate를 1->2->3->4-> ... 올리면 너무 오래걸리기때문에 지수 형태로 1->2->4->8->... 로 올리기
• slow start의 threshold (SST)는 지수형태로 올라가다가 AIMD로 바뀌는 지점이다.

  5. TCP: from slow start to congestion avoidance

  
• 위 그림에서 Reno는 round 9 에서 cwnd 9에서 부터 시작해야함!! - 그림 틀렸음
• if) duplicate ACK 상황에 12에서 congestion 발생
  • 위의 그래프에서 Tahoe인 경우 1로 내려가서 slow start로 다시 시작후 SST가 6이므로 이때부터 AIMD 수행
  • Reno인 경우 6에서 다시 시작 SST가 6이므로 바로 AIMD 수행

6. summary: TCP congestion control

7. TCP CUBIC

• TCP Reno의 다음 버전 (Linux의 default)
• 한번 혼잡이 발생한 이후 가까운 다음 시점에도 혼잡 발생한 시점이 비슷할것이기 때문에 최대 window size(W_max) 까지는 급격하게 올리고 근처에서 천천히 올리기

8. TCP and the congested "bottleneck link"

• bottleneck link : data가 전송이되는 링크는 항상 혼잡하지 않아야 한다

9. Delay-based TCP (TCP Vegas)

• just full enough, but no fuller!
• bottleneck link가 넘치치 않을 정도로 바쁘게 하기
• Throughput = $\frac{CWND}{RTTmin}$ : 혼잡하지 않을때 처리율
• ex) BBR

  10. Explicit congestion notification (ECN)

• network로 부터 congestion에 대한 정보 받아오는 방식
• TCP segment에 존재하는 C,E field 이용
• 여기서 congestion 하다는 정보는 주지만, 이에 대한 처리는 각자 다른 방식으로 하는것

11. TCP fairness

• bottleneck router capacity이 R이고 TCP session이 K개 있다면 하나당 R/K의 속도 가진다.
• TCP는 fair 하다! -> 아래의 그림으로 증명
• 위의 그림을 통해 어떠한 곳에서 시작해도 결국 bandwidth 가 같은 선위로 가게 된다. (AIMD로 동작하는 것)

12. must all network apps be fair?

• UDP는 fair 하지 않음
• TCP가 fair 하다는 것은 host 기반으로 봤을땐 fair하지 않음

8. Evolution of transport-layer functionality

1. QUIC: Quick UDP Internet Connections

• TCP와 UDP의 중간 지점
• application layer에 QUIC라는 protocol을 올림 (아래 오른쪽 그림)