Skip to content

Instantly share code, notes, and snippets.

@Gumball12
Last active October 4, 2021 10:52
Show Gist options
  • Save Gumball12/f276c3be86405e7ab41f26f2bee06727 to your computer and use it in GitHub Desktop.
Save Gumball12/f276c3be86405e7ab41f26f2bee06727 to your computer and use it in GitHub Desktop.
시험용 (h: 중간고사, f: 기말고사)

탐색

  • 탐색

    • 상태공간 내에서
    • 시작상태에서 목표상태까지의 경로를 찾는 것
    • 각 상태를 생성하는 것을 연산자 라고 함
  • 상태, 연산자, 그리고 상태 트리를 이용해 답을 찾아나가는 것

    • 물론 이를 직접 프로그래밍 하지는 않으며, DFS/BFS 를 사용해 풀어나감
  • 알고리즘

    • 맹목적인 탐색
      • 임의의 경로: BFS, DFS
      • 최적의 경로: 균일 비용 탐색
    • 경험적 탐색(휴리스틱)
      • 임의의 경로: 언덕오르기, 최적 우선
      • 최적 경로: A* 알고리즘
  • 이를 8-Puzzle 예제를 통해 보도록 하겠다

8-Puzzle

  • 8-puzzle에서의 시작, 목표 상태는 다음과 같음

https://i.imgur.com/ZdLDAi4.png

  • 연산자는 총 4개가 있으며, 다음과 같음
    • UP: 공백을 위로
    • RIGHT: 공백을 우측으로
    • BOTTOM: 공백을 아래로
    • LEFT: 공백을 좌측으로

DFS

  • Stack을 이용
    • 알고리즘 보면 알겠지만, FIFO
// define arrays
open := [start]
closed := []

while (open != []) { // while open has items
  item := open.unshift() // get item (when left end of open)

  if (item == goal) { // check item is goal state
    return SUCCESS
  }

  closed.push(item) // put item on closed

  for(generated_item : generate_children(item)) { // generate children of item
    if ((open or closed) not contain generated_item) { // check duplicated
      open.shift(generated_item) // left end of open
    }
  }
}
  1. 맨왼쪽의 open item 얻어내고
  2. 이를 goal state와 비교하고
  3. 아니면 children generate하고
  4. closed와 비교해 중복제거하며 open의 왼쪽에 넣고
  5. 마지막으로 item을 closed에 넣어주고

BFS

  • Queue 이용하는 것
    • LIFO
open := [start]
closed := []

while (open != []) {
  item := open.unshift()

  if (item == goal) {
    return SUCCESS
  }

  closed.push(item)

  for (generated_item : generate_children(item)) {
    if ((open or closed) not contain generated_item) {
      open.push(generated_item) // right end of open
    }
  }
}
  1. 알고리즘 나머지 다 같고
  2. 단지 generated_itemopen의 right에 넣는다는 차이점 만 있다
  3. 이건 LIFO로 구현해야 하니 이러하게 된 것
  • 효율은 BFS가 더 좋다

경험적 탐색

  • 그러나 이들은 가능한 노드를 모두 탐색해대니 느릴 수 밖에 없다

    • 경험적 탐색은 경험적(휴리스틱) 정보 를 사용해 좀 더 효율적인 동작이 가능하다
  • 8-puzzle에 대한 휴리스틱 정보는 다음 두 가지로 나눌 수 있다

    • h1: 현재 제 위치에 있지 않은 타일의 개수
    • h2: 각 타일의 목표 위치까지의 거리
  • 이들을 이용해 각각의 휴리스틱 탐색을 진행할 수 있는 것

    • 휴리스틱 정보. 즉, 평가함수의 값을 원하는 상태(goal)로 향하도록 진행하는 탐색
    • 가령 h1은 값이 낮은 방향으로 진행하는... 그런 것을 말한다
    • 이렇게 평가함수는 문제에 따라 종속적이라고 할 수 있음
  • 이는 언덕오르기 알고리즘 을 이용해 진행한다

    • 자신이 목표로 하는 상태에 더 가까운 것을 선택하는 알고리즘
    • 선택되지 않은 상태는 저장되지 않음 = 중복허용
    • 더 이상 선택할 것이 없을 때, 그 곳을 정상이라고 판단
      • 이 때문에, local maxima 이슈가 발생될 수 있고
  • 알고리즘은 다음과 같음

open := [{ start, eval_value }]
closed := []

while (open != []) {
  item :=  open.unshift()

  if (item == goal) {
    return SUCCESS
  }

  closed.push(item)

  for (generated_item : generate_children(item)) {
    if ((open or closed) not contain generated_item) {
      eval_value := calc_eval(generated_item) // calc eval_function value

      open.push({ generated_item, eval_value })

      open.sort('eval_value') // sort by 'eval_value'
    }
  }
}
  • 그러나 local maxima같은 문제가 발생하게 된다

A* 알고리즘

  • 너무 깊이는 들어가지 않도록 하는 것

    • 평가함수 f(n) = g(n) + h(n)
    • h(n): 현재 노드에서 목표까지의 거리
    • g(n): 초기 상태에서 현재까지의 비용(깊이)
  • 알고리즘은 비슷한

open := [{ start, eval_value }]
closed := []

while (open != []) {
  item := open.unshift()

  if (item == goal) {
    return SUCCESS
  }

  closed.push(item)

  for (generated_item : generate_children(item)) {
    if ((open or closed) not contain generated_item) {
      // eval_value = h + g
      eval_value := calc_h(generated_item) + calc_g(gengerated_item)

      open.push({ generated_item, eval_value })

      open.sort('eval_value') // sort by 'eval_value'
    }
  }
}

탐색의 방향

  • 지금까지 한 탐색은 '전향추론'

    • 전향추론: 초기상태 => 목표상태 탐색
    • 후향추론: 목표상태 => 초기상태 탐색
  • 문제에 따라 후향추론이 더 알맞은 경우도 있다

Mini-Max 알고리즘

https://t1.daumcdn.net/cfile/tistory/25579C38596D93C127

  • 두 명 이상의 상대가 서로 겨룰 때 사용할 수 있는 알고리즘

    • depth를 진행할 때 마다 서로 번갈아가며
    • 자신에게 최적인(자신이 원하는) 결과를 취하도록 한다
    • 위의 그림에서는 짝수는 Max, 홀수는 min 값을 취하도록 함
  • 마지막 node에 도착해야만이 중간 node의 값을 알 수 있음

    • 아래부터 올라오는 구조이기 때문
    • 따라서 비효율적
    • 또한, 너무 깊이 들어갈 수가 있기에 max-depth를 잡곤 함

alpha-beta 가지치기

  • a, b를 이용해 가지쳐서 Mini-Max 알고리즘을 좀 더 빠르게 진행할 수 있도록 하는 방법

    • a는 Max (init: a := -inf)
    • b는 min 을 가리킴 (init: b := inf)
  • 진행하며 가지치는 것

전문가 시스템

  • 생성규칙: IF-THEN 으로 표현한 문장

    • IF: 조건
    • THEN: 결과
  • 전문가 시스템은 info와 생성 규칙을 이용하는 것

    • 정보(info): 의미가 있게 체계화된 것
    • 데이터: 의미가 없는 그냥 사실
    • 지식(knowledge): 더욱 일반화되고 모호해진, 정제된 정보
  • 이런 전문가 시스템은 사실로 새로운 사실을 만들어 내는 것이기에

    • 결과에 대한 이유를 설명할 수 있다

https://i.imgur.com/3Fv0X9I.png

  • 전문가 시스템의 세 파트

    • 지식 베이스
    • 추론엔진
    • 인터페이스
  • 다음과 같이 동작하는 것

https://i.imgur.com/5GPgtGC.png

  • 점화를 이용해 추론을 진행하는데
    • 이 떄, 순방향/역방향이 가능

순방향 연결 추론

https://i.imgur.com/jjlYNe8.png

  • 사실 Z를 찾는다고 하자
    • 초기값은 다음과 같다고 가정하고
    • 찾는 과정은 아래와 같음

https://i.imgur.com/oU6xguP.png

  1. 기반지식 위에서부터 하나씩 진행한다
    • Y & DX & B & E 이거 세 개는 없어서 건너뛴거
  2. 사실 A가 있으니, A -> X 진행하고
    • X를 사실DB에 넣으라는 말
  3. C 있으니, C -> L
  4. L & M은 없으니 일단 건너뛰고
    • 다시 맨 위에서부터 시작
  5. X & B & E 있으니, X & B & E -> Y 진행
    • L & M은 마찬가지로 없고
  6. Y & D 있으니, Y & D -> Z 진행
    • 이를 통해 Z를 찾아내지
  • 이렇게 진행하는 것이다
    • 단, 보다싶이 마구잡이로 사실을 막 생성하기에
    • 좀 비효율적 ㅎ

역방향 연결 추론

https://i.imgur.com/jjlYNe8.png

  • 얘는 목표 지향
    • 쓸데없는 상태 만들지 않는다는 말
    • 왜냐고? 애초에 goal에서 시작하걸랑
    • 초기 상태는 동일

https://i.imgur.com/4dDlxMD.png

  1. 목표 사실 Z부터 시작해 역으로 추론을 시작한다
  2. Y & C -> Z니까, YC를 찾아줌
    • 참고로 C는 이미 있으니, Y만 찾아주면 되겠지
  3. X & A -> Y
    • A는 이미 있고, X만 찾아주면 된다
  4. B -> X
    • 이를 통해 Z가 추론가능함을 알 수 있겠지
  5. 그대로 추론진행

지식표현

  • AI의 핵심은 지식 인데, 이를 체계적으로 정제한 것

  • 지식표현 종류

    • 논리
    • 규칙
    • 의미망
    • 프레임
    • OOR(Object-Oriented Representation)
  • 규칙

    • 앞서 전문가시스템에서 봤지
    • (A, B) -> (C, D, E) 로도 표현이 가능하댄다
  • 의미망

    • 카나리 is a 새
    • 새 has 날개
    • 배니 is a 카나리
    • 뭐 이런 관계를 명시한 것
    • 전문가 시스템과 함께 사용하곤 한다
  • 프레임

    • 속성과 메서드가 합쳐저 있는, 마치 Class 비슷한 애
    • 전문가 시스템과 함께 사용하곤 한다

몀제논리의 추론

  • 인공지능에서의 논리

    • 명제논리: P, R 이런걸로 추상화하는거
    • 술어논리: 전체 문장을 주어/목적어 이렇게 분리하는 것
  • 이 중, 명제논리를 구현해보면 다음과 같음

C D ­ C -> D
T T ­ T
T F ­ F
F T ­ T
F F ­ T
  • 이게 뭘 의미하느냐?

    • 조건 C가 참이면, 결과 D도 참
    • 물론, C가 참이 아니어도, 결과 D는 참이 될 수 있음
    • 그러나, C가 참이나 결과 D가 거짓일 수는 없음
  • 기억해야하는 규칙들 (위의 구현과 함께 보면 좋겠지)

    • Modus Tollens(부정식)
      • A -> B일 때, ~B~A
      • 결과가 false면, 가정도 false
      • (A -> B) and ~B => ~A
    • Modus Ponens
      • A -> B일 때, AB
      • 가정이 true면, 결과도 true
      • (A -> B) and A => B
    • Chain Rule (삼단논법): A -> B, B -> C일 때, A -> C
      • A -> B and B -> C => A -> C

술어논리의 추론

  • 명제논리를 술어논리로 변환
p q ­ ~p ­ ~p v q ­ p -> q
T T ­ F ­ T ­ T
T F ­ F ­ F ­ F
F T ­ T ­ T ­ T
F F ­ T ­ T ­ T
  • 그냥 뭐 그대로 대치되는 것

    • 즉, ~p v q <=> p -> q
  • 예시

    • forall(x): DOG(x) -> MAMML(x)
    • ~DOG(x) v MAMML(x)

Fuzzy

https://i.imgur.com/B6nyKLQ.png

  • fuzzy: 확실하지 않은... 확률의 세계 (0.0 ~ 1.0)

    • fuzzy logic: 명확히 정의할 수 없는 지식을 표현하는 방법
    • fuzzy set: 이런 애매모호한 값들의 집합을 나타내기 위한 방법
  • 일반 집합

    • A = { x | x > 6 }
  • 퍼지 집합

    • A = { x, u A(x) | x in A }
      • u는 비율
    • A = { u A (x_i) / x_i | x in A } (참고로 /는 나누는 게 아니라, 그냥 구분기호임)
      • A = {u_A (x_1) / x_1}, {u_A (x_2) / x_2}, ...
      • 이렇게 비율별로 나타내는 것

연산

  • 설정한 Fuzzy set에 대해, 이를 좀 더 집중화 할 수가 있다

    • 이를 헤지 라고 하며, 좀 더 모호한?표현을 할 수 있도록 함
  • 일반적인 퍼지 집합

https://i.imgur.com/va9mCt2.png

  • 헤지를 적용한 퍼지 집합(초록색)

https://i.imgur.com/yrO9oU4.png

  • 이러한 헤지는 기존의 퍼지 집합에 대해 다음과 같은 연산을 통해 가능하겠지
    • [u_A (x)]^{n}
    • n < 1: 볼록해짐
    • n > 1: 오목해짐 (위 그림과 같음)

퍼지추론

  • 규칙에 대해

    • OR: max
    • AND: min
    • NOT: 1 - value (여집합)
  • 전건: IF

  • 후건: THEN

  • 소속 함수: u_A (x)

1. 뭐암튼 이렇게 해서 퍼지 값을 구하고 (퍼지화)

https://i.imgur.com/BfsCq5C.png

  • 어떠한 일을 진행하는데 있어 정의된 평가 기준에 따라 퍼지값을 구한다

  • A

    • u(x = A2) = 0.2
    • u(x = A3) = 0.2
  • B

    • u(y = B1) = 0.1
    • u(y = B2) = 0.8

2. 이를 규칙에 따라 값을 구한다 (규칙 평가)

https://i.imgur.com/zBAH91f.png

  • 위와 같은 규칙 집합 및 아래와 같은 규칙들이 있다고 한다

    • 이 역시 미리 정의된 규칙이겠지
  • 규칙1 (C1): xA2 OR yB1

    • max(u(x = A2), u(y = B1)) = max(0.2, 0.1) = 0.2
    • 즉, 규칙 C1 = 0.2
  • 규칙2 (C2): xA2 AND yB2

    • min(u(x = A2), u(y = B2)) = min(0.2, 0.8) = 0.2
    • 즉, 규칙 C2 = 0.2
  • 규칙3 (C3): xA1

    • C3 = u(x = A1) = 0

https://i.imgur.com/latKqBZ.png

  • 이를 통해 위와 같이 구해지겠다

3. 통합 (규칙 후건의 통합)

https://i.imgur.com/QQnmG1M.png

  • 이렇게 통합되고

4. 역퍼지화

  • 다음 수식을 통해 무게중심을 구한다
    • 무게중심의 값은 u_A (x) 안에 있다

https://i.imgur.com/KQzqV32.png

  • 해 보면 다음과 같음

https://i.imgur.com/SZJia1T.png

  • 즉, 35%의 확률로 어떠한 일이 발생된다는 것을 암시한다는 말

베이즈 추론

  • 다음을 기반으로 한다

https://i.imgur.com/QoYBB0O.png

  • 위를 통해 다음을 이끌어낼 수 있다
    • AB가 함께 일어날 확률은
    • B가 일어난 상태에서 A가 일어날 확률

https://i.imgur.com/vzYYw6D.png

  • 여기서, 교집합의 교환법칙으로 인해 다음과 같음을 알 수 있다

https://i.imgur.com/SiOyPKQ.png

  • 따라서, 다음과 같다고 할 수 있다

https://i.imgur.com/xIvk51W.png

응용

  • A가 일어날 확률을 다음과 같이도 표현할 수 있을 것이다
    • B가 일어난 상태에서 A가 일어날 확률 +
    • B가 일어나지 않은 상태에서 A가 일어날 확률
    • 이를 수식으로 표현하면 다음과 같다

https://i.imgur.com/3xbCGOK.png

  • 이를 통해 위의 식을 다음과 같이 표현할 수 있음

https://i.imgur.com/3HW0Taf.png

문제풀이

진화 알고리즘

  • 인코딩 과정
    • 평가
    • 선택
    • 교차
    • 변이 (이후 다시 평가 반복)

참고

n-queen 경우의 수

https://i.imgur.com/TGaUngX.png

노팅

  • 지식, 정보, 데이터
  • 낫피오큐
  • modus tollens
  • modus ponens
  • 소속 함수
  • 평가, 선택, 교차, 변이

1. 컴파일러의 개요

1.1 컴파일러의 필요성

  • 언어의 종류
    • 형식언어 => 프로그래밍 언어
    • 자연언어

매개변수

  • 매개변수 종류

    • 형식 매개변수: 파라미터
    • 실 매개변수: 인자
  • 매개변수 전달 방법

    • 참조 호출: call by reference
    • 값 호출: call by value
    • 이름 호출: 파라미터 자체가 인자로 치환되는 것

매개변수 전달 방법 예제

  • 다음을 각각 참조, 값, 이름 호출로 호출하면?
Begin Integer A, B:
  Procedure F(X, Y, Z); Integer X, Y, Z;
    Begin
      Y := Y + 2;
      Z := Z + X;
    End F;

  A := 3;
  B := 5;

  F(A + B, A, A);
  PRINT A         // <= 결과무엇?

END
  • 참조

    • YZA를 가리킨다는 것만 잘 알고 있으면 된다
    • 따라서 PRINT A13을 출력
    • 이건 뭐... 당연히 3을 출력
  • 이름

    • F(X, Y, Z)F((A + B), A, A)로 변하는 것
    • 따라서 다음과 같아진다
      • Y := Y + 2 => A := A + 2 => A := 5 + 2
      • Z := Z + X => A := A + (A + B) => A := 5 + (5 + 5)
    • 답은 15

1.3 번역기의 종류

  • 어셈블러
    • 대부분 two-pass-assembler 로 구성된다
    • first pass: 어셈블리 코드로 기호표를 작성
    • second pass: 이를 bit로 표시

2. 간단한 컴파일러의 구조

2.1 컴파일러의 논리적 구조

  • 다음 순서로 진행되겠지

    1. 어휘분석: 토큰화
    2. 구문분석: 파스 트리
    3. 의미분석
    4. 중간코드 생성
    5. 최적화
    6. 목적코드 생성
    7. 목적 프로그램
  • 구문분석에서 parse tree 만드는거 나온다고

1.1 인터넷이란 무엇인가

  • 구성 요소

    • 물리
      • host (end-system)
      • link
      • switch (router)
    • 논리
      • 인터넷
      • 프로토콜
      • 인터넷 표준 (RFC, IETF)
  • ISP: Internet Service Provider

  • Switch는 host간의 연결을 위한 것

  • Router는 routing과 관련된 것

1.2 네트워크의 가장자리

https://i.imgur.com/AZEdARY.png

  • 네트워크 가장자리 (Edge)

    • 여기서 호스트(클라이언트, 서버)가 있다
  • 접속 네트워크 (Access Network)

    • 유/무선 통신 link
  • 코어 네트워크 (Core Network)

    • 상호 연결된 라우터들
    • 네트워크들의 네트워크
  • DSL: 기존의 전화선 사용한 통신 (돈애낄려고)

  • FTTH: 광케이블 (개빠름)

  • Ethernet: 내부 통신망

    • Ethernet Switch 라는 걸 이용한댄다
  • IP (Internet Protocol)

    • 무수한 길이 있는 Internet에서 올바른 길을 찾기 위한 프로토콜
  • TCP: host에서 동작하는 프로토콜

    • Router는 이를 보내기만 하는 것
    • 이 프로토콜을 통해 데이터가 섞여 들어와도 올바르게 통신이 가능하다

1.3 네트워크 코어

  • 네트워크 코어(코어 네트워크) 란?

    • 위 그림에서도 나오듯, 상호 연결된 라우터들의 연결망
    • 패킷 스위칭 기법을 사용하여 데이터를 분할해 최대 전송률 속도로 전송
      • 패킷 스위칭: 패킷이 어디로 가는지를 선택하는 것
    • 라우터들을 거쳐 상대방 host로 도착하게 된다
  • 네트워크 코어는 패킷에 대한 라우팅 그리고 전달 이 주요 기능

    • 라우팅
      • Src에서 Dest까지 패킷 경로 결정 (라우팅 알고리즘에 따라)
      • 이를 통해 라우팅 테이블이 만들어진다
    • 전달
      • 라우팅 테이블에 따라 패킷을 전달
  • 네트워크 코어의 구성 방식은 패킷 교환 그리고 회선 교환 이 있음

    • 패킷 교환이 더 효율적이다

패킷 교환 방식

  • 호스트는 다음의 동작으로 송신한다

    1. host는 message를 L bit 단위의 덩어리인 패킷 으로 분할
    2. 이를 link의 전송률(전송속도) R bits/sec 로 전송
  • 이렇게 하나의 패킷을 전송하는데 걸리는 시간을 전송 지연 이라고 함

    • 전송 지연 = link로 L bit를 전송하는데 걸리는 시간 = L / R
  • 큐잉 지연 및 손실

    • 만약 link 속도보다 패킷 들어오는 속도가 빠르면, Queue를 사용해 패킷을 버퍼링한다
    • 만약 큐가 꽉 찼다면? 그대로 손실되는거
      • 단, TCP에서 이러한 loss를 관리해 다시 보내게끔 한다
    • 큐에 이렇게 쌓이는 것을 혼잡 이라고 함

전송 지연 및 Store-and-forward 전달

https://i.imgur.com/4CJ208i.png

  • 패킷 전송 시, 목표 라우터에 모두 도착해야 다음 라우터로 전송한다

    • 이를 store-and-forward 전송 이라고 함
    • 위 그림의 경우, 총 2 * L / R 전파 지연이 걸리겠지
  • 전송 지연의 예시; L = 7.5 Mbits, R = 1.5 Mbps

    • 전송 지연: 7.5 / 1.5 = 5 sec
    • 총 전송 지연: 5 sec * 2 hop = 10 sec

회선 교환 방식

  • 일정 시간동안 link 나눠 예약하는거
    • 자원 공유 불가능하고
    • 지속적으로 끊김 없이 연결되겠지
    • 물론 사용하지 않는 경우, 그냥 그대로 낭비되는 것이겠지

https://i.imgur.com/j4qBDfm.png

  • FDM (Frequency-Division)

    • 주파수 단위로 나눠 공유
  • TDM (Time-Division)

    • 시간 단위로 나눠 공유

1.4 패킷 교환 네트워크에서의 지연, 손실과 처리율

  • 패킷은 link 출력 용량 넘어서면 Queue에서 대기
    • 큐잉지연: 패킷이 큐에서 대기하는 지연
    • 전송지연: 패킷을 링크로 밀어내는 지연 (L / R)

https://i.imgur.com/5alXAml.png

  • 패킷 지연 유형

    • 큐잉 지연
    • 전송(Transmission) 지연
    • 전파(Propagation) 지연
    • 노드 처리 지연
    • 전체 노드 지연은 이를 모두 더한것: 큐잉 + 전송 + 전파 + 노드 처리
  • 노드 처리 지연

    • 라우터에서 패킷을 어디로 보낼까 조사하는 지연
    • 일반적으로 ms 이하
  • 전파 지연

    • link에 오르고, 다음 라우터까지 전파되기까지의 지연
    • FTTH 통해 거의 빛의 속도로 보낸다
    • 라우터 간의 거리 / 전파 속도 = d / s
  • 큐잉 지연은 다음과 같이 측정이 가능: La / R

    • L: 패킷 깃이, bit의 수
    • R: link로 나가는 속도
    • a: 큐로 패킷이 들어오는 비율
    • La: bit가 큐로 들어오는 비율
    • 이 값이 1에 가까울수록 link의 처리율에 가까워진다는 의미고, 이는 즉 큐잉 지연이 개높아진다는 의미가 되겠지

전파 지연과 전송 지연의 차이 예제 1

https://i.imgur.com/VrLOae7.png

  • 가정

    • 총 12대의 차
      • 12대 = 패킷
      • 여기서 각각의 차는 패킷의 bit를 의미
    • 100km마다 놓여있는 톨게이트
    • 톨게이트는 차 한 대당 10초 걸림
    • 차의 속도는 100km/h
  • 계산

    • 전송 지연: 12대 * 10초 = 120초 = 2분
      • 즉, 마지막 차가 보내지는 데 까지 2분
    • 전파 지연: 100km / (100km / h) = 1시간 = 60분
  • 총 지연: 62분

    • 막차출발 + 전파지연

전파 지연과 전송 지연의 차이 예제 2

  • 가정

    • 총 12대의 차
    • 100km마다 놓인 톨게이트
    • 톨게이트는 차 한 대당 1분 걸림
    • 차의 속도는 1000km/h
  • 계산

    • 전파 지연: 100km / (1000km / h) = 0.1시간 = 6분
    • 전송 지연: 12대 * 1분 = 12분
  • 7분 후에는 이미 두 번째 톨게이트에 차가 도착해 있는 상황

    • 첫 번째 톨게이트에서 출발하지도 못한 차가 있는데 말이지
    • 그러나 모든 차가 두 번째 톨게이트에 도착해야 하기에(store-and-forward) 두 번째 톨게이트에서 기다림
  • 총 지연: 12분 + 6분 = 18분

처리율

  • host 간에 비트가 전송되는 비율

    • 전송률이 아니다. 이건 node(router) 사이에 비트가 전송되는 비율을 의미
  • host 간의 처리율은 bandwidth가 더 작은 곳의 전송률을 따른다

https://i.imgur.com/gWIN50H.png

  • 이 경우 min(R_s, R_c) 가 된다는 말
    • 제일 느린것을 찾는다는 말
    • 이렇게 처리율을 제약하는 link를 병목 링크 라고 한다

처리율 예제

https://i.imgur.com/vEmfQxI.png

  • 10개의 클라, 10개의 서버

    • 중간의 링크는 10개의 다운로드에 대해 공평하게 처리한다고 가정
  • 이 때의 처리율은?

    • min(R_s, R_c, R / 10)
    • 마찬가지로 제일 느린걸로 처리율을 판단한다

1.5 프로토콜 계층과 서비스 모델

  • 프로토콜에도 계층이 있다

    • 이를 통해 side-effects 없이 Interface로 서로 통신이 가능
  • 원래는 OSI 모델이었는데

    • 물링네전세프응
    • 여기서 세션, 프레젠테이션 부분 빠지고 아래의 형태로 간략화되었다
      • 이를 application 계층에서 구현했기 때문
    • 프레젠테이션: 압축, 암호화 등 데이터 의미 해석
    • 세션: 데이터 교환 경계
  • 인터넷 프로토콜 스택

    • 애플리케이션: Message
      • 네트워크 응용
      • Socket을 이용해 트랜스포트 계층과 데이터 주고받음
      • FTP, SMTP, HTTP
    • 트랜스포트: Segment
      • 프로세스간 데이터 전송
      • TCP, UDP
    • 네트워크: Datagram
      • 호스트간 데이터 전송
      • IP
    • 링크: Frame
      • 노드간 데이터 전송
      • Ethernet, WIFI
    • 물리
      • 매체 상 데이터 전송

https://i.imgur.com/zlJCFsg.png

  • 캡슐화: 패킷 = 헤더 + 페이로드
    • 헤더: 프로토콜 레이어 데이터
    • 페이로드: 지금까지 붙은 데이터들

2.1 네트워크 애플리케이션의 원리

  • 프로세스는 Socket을 통해 통신

    • Socket은 애플리케이션 계층과 트랜스포트 계층 사이의 인터페이스
  • 애플리케이션 계층 프로토콜

    • 메시지 타입이나 문법, 의미에 대한 규칙이겠지
    • HTTP같은 Open Protocol도 있고, Kakao같은 Private Protocol도 있고
  • 여기서는 트랜스포트 계층에 다음을 요구한다

    • 데이터 무결성
    • 최대의 처리율
    • 최소한의 지연
    • 보안
  • 이에 대해 Transport layer는 다음 서비스를 제공한다

    • TCP
    • UDP
  • TCP

    • 연결지향형 (handshake)
    • 신뢰성 (무결성)
    • 흐름제어
    • 혼잡제어
    • 제공하지 않는 것들: 시간, 처리율, 보안
  • UDP

    • 비연결형 (non-handshake)
    • 비신뢰적
      • 데이터가 도착하든말든 지 보낼것만 보냄
    • 제공하지 않는 것들: 흐름제어, 혼잡제어, 시간, 처리율, 보안
  • SSL (보안 TCP)

    • 암호화 없는 TCP와 UDP
    • 때문에 Application layer에서는 SSL을 구현해 사용한다

2.2 웹과 HTTP

  • HTTP

    • 애플리케이션 계층에서의 웹 프로토콜
    • 클라이언트/서버 모델
    • TCP 사용해 통신한다 (port: 80)
  • HTTP는 State-less 프로토콜 (복잡해서)

    • 이전 상태가 어떠했는지 정보를 유지하지 않는다는 말
    • 이건 직접 구현하든가 해야만 한다는 의미이다
  • 연결 방식

    • 비지속 연결: 1연결 1객체 받아오기
      • Request/Response 서로 분리된 TCP 연결에서 진행
      • HTML 해석하다가 필요한 객체 있으면 그거 또 새로 연결해서 받아오고 하는거
      • 비효율적
    • 지속 연결: 1연결 n객체 받아오기
      • Request/Response 서로 같은 TCP 연결에서 진행
      • 마찬가지로 필요 객체 있으면 그냥 연결된 TCP 이용해서 계속 받아오는거

https://i.imgur.com/IlUtBCk.png

  • RTT: 서버까지 왔다갔다 하는 총 시간

    • 비지속 연결: 2RTT (초기화 + 파일요청)
      • 이 때문에 종종 병렬로 요청하곤 한다고 함
    • 지속 연결: 1RTT
  • HTTP는 두 가지 종류의 메시지가 있다.

    • Request, Response
    • 메시지 포맷을 잘 알아두자
  • 쿠키

    • 사용자 상태를 추적하기 위해 사용함
    • 이를 이용해 사용자 상태의 보존이 가능
    • 다만 정보유출의 가능성이 있겠지
  • REST

    • 웹을 활용한 분산 시스템 소프트웨어 아키텍쳐
    • CRUD

HTTP Request Message

https://i.imgur.com/sDDE6uS.png

  • method: GET, POST, OPTION, DELETE, ...
  • URL: File path
  • Version: HTTP/1.1, HTTP/2
  • header field name: Content-Type, Accept-Headers, User-Agent, ...

HTTP Response Message

https://i.imgur.com/8NVsTLd.png

  • version: HTTP/1.1, HTTP/2
  • status code: 200, 301, 400, 404, 505 ...
    • 200: 성공
    • 301: 객체 이동됨
    • 400: 요청 이해 불가
    • 404: 존재하지 않는 문서
    • 505: 요청한 HTTP 버전을 지원하지 않음
  • phrase: 상태와 관련된 문장 (OK, ERR, ...)

웹 캐시 (프록시 서버)

  • Origin Server를 대신해 HTTP 요청을 처리하는 서버

    • 브라우저는 웹 캐시에 요청하고, 있으면 그걸 사용하는 것 (혼잡제어)
    • 없으면 뭐 프록시 서버가 Origin에서 가져와 줘야지
  • 이런건 개인이 아니라 ISP가 설치한다

    • 이를 이용하면 느린 네트웤에서도 어느정도 빠르게 가능할테니까
  • 조건부 GET

    • 프록시 서버는 일정 시간마다 Origin으로 GET 하는데
    • 만약 이게 최신버전이다? 그럼 Body 보내지 않는 것

사용 예시; 웹 캐시가 없을 때

https://i.imgur.com/O03cGeF.png

  • 가정

    • 내부 네트워크 전송률: 100Mbps
    • 외부 네트워크로 나가는 link 전송률: 15Mbps
    • 파일 크기: 1MB
    • 요청 주기: 15 회 / 초
  • 결과

    • LAN 이용률: (15회 * 1MB) / 100Mbps = 0.15, (15%)
    • link 이용률: (15회 * 1MB) / 15Mbps = 1, (100%)
      • 문제발생
  • 물론 link 증설하면 되겠지만, 돈이 많이 들고 웹 캐시보다 효율도 떨어진다

사용 예시; 웹 캐시가 있을 때

https://i.imgur.com/v4sybVJ.png

  • 가정

    • 내부 네트워크 전송률: 100Mbps
    • 외부 네트워크로 나가는 link 전송률: 15Mbps
    • 파일 크기: 1MB
    • 요청 주기: 15 회 / 초
    • 캐시 히트 확률: 40%
  • 결과

    • 회선 이용률 40% 감소

2.3 인터넷 전자메일

  • 메일은 다음의 주 요소로 이루어짐

    • 사용자 에이전트
      • 메시지 읽고, 작성하고, 보내고
    • 메일 서버
      • Mailbox: 메일 받은거 저장
      • Queue: 메일 보낼 때 큐잉
    • SMTP: 메일 주고받는 프로토콜
      • 서버: 받는 메일 서버
      • 클라이언트: 보내는 메일 서버
    • POP, IMAP, HTTP: 메일 꺼내오기
  • RFC 822: 텍스트 메시지 포맷 표준

SMTP

https://i.imgur.com/mLRhckZ.png

  • 포맷(RFC 822) 구성

    • header
      • To, From, Subject
    • body
      • ASCII 메시지
  • 3가지 전송 과정 (지속 연결 사용, HTTP의 그것)

    1. handshake
    2. 메시지 전송
    3. 종료
SMTP HTTP
Resource PUSH 프로토콜 Resource PULL 프로토콜
객체 자체를 하나의 메시지로 각 객체는 응답 메시지 안에 캡슐화됨
  • HTTP와의 차이점은 위와 같음
    • Resource PUSH: 말 그대로 서버에 리소스 밀어넣는거지
    • Resource PULL: 말 그대로 서버에서 리소스 가져오는거지

MIME

  • ASCII가 아닌 데이터를 보내기 위한 RFC 822 확장

    • 텍스트 아닌 건 일단 ASCII로 인코딩하고
    • 헤더에 타입 명시
  • 보통 base64 인코딩 진행

    • '8bit * 3개' 이거를 '6bit * 4개' 이거로 바꿈
    • ASCII 표현을 위함

POP, IMAP, HTTP

  • 이 프로토콜들을 이용해 메일 서버에서 메시지를 추출

    • 요즘엔 HTTP를 사용해서 가져오곤 한다
  • POP

    • State-less
    • 다운로드 후 바로 삭제 (말 그대로 POP)
  • IMAP

    • State 유지

2.4 DNS

  • Domain to IP

    • 도메인(호스트 네임)을 들어가면 IP로 연결
    • 반대는 성립하지 않음 (이름만으로는 접속할 수 없기에 IP랑 연결해줘야 하겠다)
    • 계층구조
  • DNS는 해당 호스트 네임에 대해 여러 별칭을 만들어놓는다

    • 이를 통해 부하 분산이 가능

https://i.imgur.com/mxnOQFz.png

  • 이렇게 계층화시킨다

    1. com의 DNS 서버를 찾기 위해 root 서버에 질의
    2. amazon.com의 DNS 서버를 찾기 위해 com DNS 서버에 질의
      • TLD (Top-Level Domain) 서버
    3. www.amazon.com의 IP 얻기 위해 amazon.com에 질의
      • 책임 DNS 서버
  • 우측의 것부터 하나하나씩 풀어나가는 것

    • TLD 서버: com, org, kr, uk 이런거에 대한 책임 서버
    • 책임 DNS 서버: host name을 최종적으로 IP 주소로 매핑시키는, 기관 내 서버
    • 로컬 DNS 서버: DNS 서버에 대한 프록시 서버

동작 예시

반복적 질의

  • gaia.cs.umass.edu를 질의

  • 반복적 질의는 Local DNS Server가 IP 알아내는 것을 책임지는 것

https://i.imgur.com/rHt7K8X.png

  1. IP 주소 알기 위해 Local DNS Server 로 질의
    • 안타깝게도 Local DNS Server는 모른다고 가정
  2. 때문에, root 주소부터 알기 위해 Root DNS Server 로 질의
  3. 결과를 받고
  4. 결과를 이용해 TLD Dns Server 다음 질의
  5. 받고
  6. 결과 이용해 책임 DNS Server 로 IP 주소 질의
  7. gaia.cs.umass.edu IP 주소 얻어나고
  8. 이를 클라이언트에게 반환

재귀적 질의

  • gaia.cs.umass.edu를 질의

  • 재귀적 질의는 상위 DNS Server가 알아내는 것

https://i.imgur.com/R79QEvH.png

  1. Local DNS Server로 질의하고
  2. Local DNS Server는 아는게 없으니 root부터 알기 위해 root DNS Server로 질의
  3. Root는 자신이 아는걸 이용해 질의와 관련된 TLD DNS Server로 질의
  4. TLD DNS Server는 이를 마찬가지로 질의와 관련된 책임 서버로 질의
  5. 책임 서버는 질의에 대한 IP 주소를 알아내고
  6. 이를 TLD DNS Server로 반환
  7. 이를 Local DNS Server로 반환
  8. 클라이언트에게 반환

DNS 레코드

  • DNS는 자원 레코드(Resource Record, RR) 를 관리하는 것

    • RR format: (name, value, type, ttl)
  • Types

    • A; host Address
      • name: 호스트 네임
      • value: IP 주소
    • NS; Name Server
      • name: 도메인 (e.g. foo.com)
      • value: 도메인에 대한 책임 서버 DNS의 호스트 이름
    • CNAME; Canonical NAME
      • name: 별칭 호스트 네임 (e.g. www.ibm.com)
      • value: 정식 호스트 네임 (e.g. servereast.backup2.ibm.com)
    • MX; Mail eXchange
      • value: 메일서버의 별칭 호스트 네임
      • name: 메일서버의 정식 호스트 네임
  • DNS 프로토콜의 메시지 포맷은 다음과 같음

    • 질의 또는 응답 시 이런 포맷을 사용

https://i.imgur.com/dvHvhc4.png

  • message headers

    • Identification
      • 질의를 식별 식별자
      • 응답도 같은 식별자를 보냄
    • Flags
      • 질의/응답 구분
      • 재귀적인 질의 요청
  • Records

    • <n>은 레코드 개수를 의미
    • 아래 record body와 중복되는 내용이기에, 구조가 크게 어렵지는 않음

2.5 P2P 파일분배

  • 구조가 복잡
    • 대신에 서버/클라 형태가 아니기에 대역폭이 작아도 서비스 가능

파일 분배 예시; 서버와 P2P 성능비교

  • 파일크기: F
  • 피어(클라이언트) 수: N
  • 업로드 속도 u

클라-서버 모델

  • 서버: 파일 복사본 N개를 클라에게 전송한다

    • 1개 전송 시간: F / u
    • N개 전송 시간: N * F / u
    • 참고로 서버가 분할적으로 클라이언트에게 뿌린다고 생각하자
  • 클라이언트: 파일을 다운로드한다

    • d_min: 가장 낮은 다운로드 속도를 갖는 클라의 다운로드 속도
    • 이 클라의 다운로드 시간: F / d_min
  • 클라-서버 방식으로 N 개의 클라에게 F를 분배하는 시간 D

    • D >= max(N * F / u, F / d_min)
    • 클라 수가 많아지면, 더 오래 걸릴 것이다

P2P 모델

  • 서버: 복사본 1개만을 전송

    • 1개 전송 시간: F / u
  • 각 피어: 파일 다운로드

    • d_min: 가장 낮은 다운로드 속도를 갖는 피어의 다운로드 속도
    • 이 피어의 다운로드 시간: F / d_min
  • 모든 피어: 파일 업로드

    • 피어 i의 업로드 속도: u_i
    • 모든 피어의 업로드 속도: sum(u_i)
    • 전체 업로드 속도: u + sum(u_i)
      • 서버 + 피어 업로드 속도
    • N 피어에게 분배하는 시간: N * F / (u + sum(u_i))
      • 피어 수 N이 증가할수록, 업로드 속도 u + sum(u_i)도 증가하겠지
  • P2P 방식으로 N개 의 피어에게 F를 분배하는 시간 D

    • D >= max(F / u, F / d_min, N * F / (u + sum(u_i))

2.6 비디오 스트리밍과 CDN

스트리밍

  • 압축 기법

    • CBR: 일정한 속도의 인코딩
    • VBR: 공간, 시간적으로 가변적인 인코딩
  • DASH (Dynamic, Adaptive Streaming over HTTP)

    • 멀티미디어 파일을 조각(blob)낸 다음
    • 이를 대역폭에 따라 가변적인 품질로 보내는 것

CDN

  • 다수의 분산된 서버

    • 각 서버에 컨텐츠의 복사본이 저장되어있다
    • Origin Server에 CDN Manifest 요청하고, 이를 통해 CDN에서 데이터 가져오는 것
  • 종류

    • enter deep: ISP 내부에 깊숙히 배치되어있는 CDN
    • bring home: ISP 근처에 구축한 CDN
  • OTT: 인터넷을 통해 미디어 컨텐츠를 제공하는 서비스

    • 넷플릭스 이런거

CDN 컨텐츠 접근 동작

https://i.imgur.com/0vvy1VY.png

  1. 컨텐츠 받기 위해 Origin Server인 www.NetCinema.com 으로 접근
    • 여기서 해당 컨텐츠의 URL을 얻어온다 (NetCinema.com/gk3RFq64)
  2. NetCinema.com/gk3RFq64의 IP를 얻기 위해 Local DNS Server로 질의하고
  3. NetCinema 책임 DNS Server를 찾아 질의한다
    • 여기서 CDN URL 반환 (KingCDN.com/t4TnXZD32)
  4. KingCDN.com/t4TnXZD32의 IP를 얻기 위해 KingCDN 책임 DNS Server를 찾아 질의
  5. IP주소 얻어온다
  6. 이를 이용해 컨텐츠 요청 및 가져오기

2.7 소켓 프로그래밍

  • 소켓을 이용해 트랜스포트 서비스를 이용할 수 있음

    • UDP: 비연결형
    • TCP: 연결형
  • UDP

    • 초기 handshake가 없기에
    • 요청 시마다 IP랑 Port 명시해줘야 함
  • TCP

    • 초기 접속을 위한 socket 및 IP, Port 명시 필요
    • 서버는 초기 접속 시, 해당 클라에 대한 요청을 처리하는 소켓 생성

3.1 트랜스포트 계층 서비스 개요

  • process 간의 논리적 통신을 위해 트랜스포트 프로토콜을 구현한다

    • TCP, UDP를 왜 구현(사용)하겠는가? 이를 위한 것이다
  • 제공기능

    • TCP: 혼잡제어, 흐름제어, 연결
    • UDP: 데이터 전송
    • 지연, 대역폭 보장은 없음

3.2 다중화(Multiplexing)와 역다중화(Demultiplexing)

https://i.imgur.com/94vqdTA.png

  • 다중화: 합치기 (여러 프로세스에서 하나의 데이터로)

    • 소켓에서 데이터 모으고 헤더붙이기
  • 역다중화: 나누기 (하나의 데이터에서 여러 프로세스로)

    • 헤더 정보 사용해 분리된 세그먼트(메시지)를 올바른 소켓에 전달

역다중화

https://i.imgur.com/gpLU8Q6.png

  • TCP/UDP의 Segment는 위와 같은 형태
    • Datagram은 이런 Segment를 하나씩 가지고 있으며, 여기에 추가로 IP 정보를 가짐
    • 상대방 host는 이 IP, port를 사용하여 소켓으로 전달하는 것

비연결형 역다중화

  • UDP 말하는 것
    • UDP는 그냥 주기만 하면 되기에, 다음의 정보만 필요
    • Dest IP/port
    • 물론 주는 건 source, dest 둘 다 주긴 함

https://i.imgur.com/d8p4opt.png

  • 동작은 마찬가지로 Dest IP/port 사용해 타겟 소켓으로 넘길 뿐임
    • Dest IP/port만 보기에
    • 같은 목적지를 가지면, 클라이언트 구분 없이 같은 소켓으로 전달한다

연결지향형 역다중화

  • TCP 말하는 것
    • 요청 받는 것 뿐만 아니라, 이에 대한 응답을 해 줘야 하기에 다음이 필요
    • Source IP/port, Dest IP/port

https://i.imgur.com/hxGkdGu.png

  • Source IP/port 그리고 Dest IP/port 사용해 타켓 소켓으로 넘긴다

    • 같은 Dest IP/port 인 경우에도, Source IP/port가 다르다면 다른 소켓으로 넘긴다
    • 즉, 클라이언트 구분해서 소켓으로 전달한다 는 의미
  • port가 소켓을 의미하지 않음을 유의한다

3.3 비연결형 트랜스포트: UDP

  • UDP의 기능

    • 다중화, 역다중화
    • 에러 검출
    • 빠름 (혼잡지연 우회)
  • 단점

    • 손실 감내
    • 순서 어긋남 감내

https://i.imgur.com/PoI1RrR.png

  • 세그먼트 구조는 위와 같음
    • checksum 을 이용해 오류를 검출하는 것

3.4 신뢰성있는 데이터 전송의 원리

  • Unreliable한 Internet 환경에서의 데이터 전송은 많이 빡세다
    • 이에 대한 방안이라고 RDT라는게 나왔다

https://i.imgur.com/Q9kGdTi.png

  • RDT에서는 다음 네 개의 인터페이스를 사용함
    • rdt_send(): 상위계층(app-layer)에서 호출, 수신측의 상위계층으로 전송할 데이터 전달
    • udt_send(): 패킷을 수신 측에 전송하는 동작
    • rdt_rcv(): 패킷이 수신 측에 도착 시 호출
    • deliver_data(): 상위 계층에 데이터 전달될 때 호출 (에러없음을 의미)

RDT 1.0; 완전히 신뢰적인 채널 상의 신뢰적인 전송

  • 다시말하지만, 하위 채널이 완전히 신뢰적인 채널에서의 전송을 의미
    • bit error 없고
    • packet loss 없고

https://i.imgur.com/4rpEnn2.png

  1. sender에서 rdt_send() 실행되면
    • 패킷 만들고(make_pkt())
    • 이를 전송(udt_send())
  2. receiver에서 데이터 들어와 rdt_rcv() 호출되면
    • 에러 검출 필요가 없으니
    • 바로 deliver_data() 호출해 app-layer로 데이터 전달

RDT 2.0; 비트 오류가 있는 채널

  • 채널에서 bit error가 발생될 수 있음

    • checksum 사용해 오류를 검출할 수 있겠지
  • 이를 위해, 데이터 도착 후 다음의 상태를 sender에게 보내는 것으로 정의함

    • ACK: 오류 없음
    • NAK: 오류 있고, 재전송 바람
  • rdt 2.0 사항들

    • 오류 검출
    • 피드백 전송

https://i.imgur.com/Fx1tpQX.png

  1. sender는 rdt_send() 호출되면
    • 패킷만들고
    • 전송하고 (udt_send())
  2. receiver는 rdt_rcv() 확인하고
    • 성공하면 그대로 sdt_send(ACK)
    • 실패하면 udt_send(NAK)
  3. sender에서는 상태 뭐오나 대기탔다가
    • ACK 오면 암것도안하고(Lambda)
    • NAK 오면 재전송 (udt_send())
  • 그러나 ACK, NAK도 오류가 생길 수 있겠지
    • 그럼 sender는 receiver의 상황을 제대로 알 수 없을테고
    • 별 수 없이 패킷 재전송해버리면 중복 패킷 문제가 발생되겠지

RDT 2.1; ACK/NAK의 오류 고려

  • 알아볼 수 없게 오면 어떡하지? 패킷이 중복되어버리는 건 어쩌나?

  • 해결책

    • sender는 패킷 보낼 때 번호(0 and 1) 붙여서 전송한다
    • receiver는 상태 보내고, 여기서 에러가 뜬다고 가정하자
    • 일단 에러 뜨면 재전송한다
    • sender는 새로운 번호 붙여서 재전송하겠지
    • receiver는 이걸로 다시 상태 보내고 말야

https://i.imgur.com/4hMA9NU.png

  1. sender에서 rdt_send() 호출하면
    • 했던 대로 패킷을 보내긴 하는데, 이번에는 번호(0)를 붙인다 (make_pkt(0, ...))
    • 그리고 전송 (udt_send())
  2. receiver는 받고 오류 있거나 0번 패킷이 아니면 #1, 없으면 #2 실행
    • #1: NAK 보냄. 재전송하라고
    • #2: 정상적으로 받았다고 ACK 보내고 deliver_data()
  3. sender는 NAK 또는 ACK 기다렸다가 결과에 따라 행동하지
    • NAK거나 이상하게 오면 뭐 다시보내고, 아니면 넘어가고(Lambda)
  4. 다음 sender 전송(rdt_send()) 호출하면
    • 패킷을 보내는데, 이번에는 1번 붙여서 전송 (make_pkt(1, ...))
  5. receiver는 '2'에서와 마찬가지로
    • 오류가 있거나 1번 패킷이 아니면 #3, 아니면 #4 실행
  6. sender는 마찬가지로 NAK, ACK 기다리고 행동하고
  7. 다음 전송은 다시 0번으로 돌아간다
  • 상태가 2배 늘어났는데, 이는 01 둘 다를 표현해주기 위함이다

RDT 2.2; NAK 없는 프로토콜

  • 놀랍게도 여기서 NAK는 빠질 수 있다고 함
    • receiver는 NAK 대신에, 마지막에 올바르게 수신된 패킷에 대한 ACK만을 보내면 되겠지
    • sender는 중복된 ACK 받았다? 그러면 재전송인거고 (NAK 받은듯이 행동)

https://i.imgur.com/v04F3ik.png

  1. sender 똑같이 행동은 하는데
    • 번호붙이는거 동일
  2. receiver에서는 ACK 줄 때, 번호를 붙여서 준다
    • #4: 정상적이면, 받은 데이터의 번호(0) 그대로 주고
    • #3: 아니면, 다른 번호(1) 주고
  3. sender는 이거 확인해서 내가 보낸 번호와 다르다? 좀 이상한 번호다? 그러면 재전송(#1)
    • 물론 ACK 에러나도 재전송
  4. 아니면 정상진행(#2)
  5. 이후 과정은 같음

RDT 3.0; 오류와 손실이 있는 채널

  • 이제 bit error 뿐만 아니라, packet loss까지 고려해서 진행해보도록 하자

    • 아예 오지 않으면 어떡하지?
  • 해결책

    • sender는 충분한 시간 동안 ACK를 기다리다가... 안오면 재전송
      • 중복 패킷 문제가 발생될 수 있지만, 이는 이미 rdt 2.1에서 해결되었다
    • 근데 오지 않은게 아니라, 지연된 상황이었다면?
      • 그럼 재전송은 중복 패킷이 되겠지만, 이는 앞서 말했듯이 solved 되었지
    • 즉, Countdown timer가 필요하다

https://i.imgur.com/A7qHme7.png

  1. sender가 rdt_send() 호출하면 데이터를 전송하겠지
    • 하던대로 하는데, 여기서 start_timer가 들어간다
  2. 일단 중복-ACK 또는 ACK 에러 뜨면 기다리고
    • 어차피 Timer에서 잡아주니까
  3. timeout 되어버리면 재전송
    • 재전송하고 다시 start_timer로 돌리고
  4. 만약 정상적으로 오는 경우 stop_timer로 타이머 멈춰주지
  • 참고로 receiver는 RDT 2.2와 다를 게 없다는 사실~

RDT 3.0의 동작; no loss

https://i.imgur.com/5RelgtK.png

  • 따로 설명은 필요없음

RDT 3.0의 동작; packet loss

https://i.imgur.com/Od9Tyad.png

  1. 처음엔 정상적으로 주고받다가
  2. 로스뜨면, 일단기다리고
  3. timeout 되면 재전송

RDT 3.0의 동작; ACK loss

https://i.imgur.com/pizcO21.png

  1. 정상통신 하다가
  2. ACK loss 뜨면?
    • 그냥 뭐 timeout 기다린다
  3. timeout 되면 재전송

RDT 3.0의 동작; 지연

https://i.imgur.com/ml7mI3e.png

  1. 하도 응답이 안와서 timeout되고, 재전송해버렸는데
  2. 지연된 ACK가 와버렸다?
  3. 이건 재전송된 패킷의 ACK라고 판단
    • 다음 패킷 pkt0 보내고
  4. receiver에서는 pkt1 이거 중복된거니 무시하고
    • 상태도 보면 알겠지만, 이 경우에도 ACK 보내긴 하니 보내줌
  5. ACK1 sender에서 받아봤자 중복된거 아니까 아무것도 안하고(Lambda)
  6. receiver는 ptk0에 대한 응답 ACK0 보내주고

RDT 3.0의 성능 이슈

https://i.imgur.com/ld98vtB.png

  • 동작은 잘 하지만, 성능은 그리 좋지 못함

    • 한 패킷씩 보내니까
    • 그래서 한 번에 여러 패킷을 보내는 작업을 pipeline을 사용
  • 가정

    • link: 1Gbps
    • RTT: 30ms
    • L: 8000bit
  • 결과

    • D = 8000 / 10^9 = 8 microsec = 0.008ms
    • 총 지연시간 t = RTT + D = 30ms + 0.008ms = 30.008ms
    • 이는 30.008ms동안 8000bit밖에 못 보냈음을 의미하며, 1Gbps link에서 267kbps 처리밖에 못했음을 의미
      • 1sec / 30.008ms * 8000bit = 1000ms / 30.008ms * 8000bit ~ 267kbit

Pipeline 프로토콜

  • Sender가 ACK를 기다리지 않고 여러 패킷을 전송
    • 따라서 01 뿐만 아니라, 추가적으로 더 많은 순서번호가 필요

https://i.imgur.com/S9YcVom.png

  • 종류는 GBN(Go-Back-N), SR(Selective Repeat) 두개가 있음
    • 뭐가 왔는지 안왔는지 판별하고, 이에 따라 패킷을 어떻게 보내줄지에 대한 종류

GBN(Go-Back-N) 방식

  • sender는 N개의 패킷을 ACK 없이 연속전송
    • receiver는 들어온 패킷에 대해 마지막으로 성공한 ACK(누적 ACK) 만을 전송
    • 만약 ACK 번호에 갭이 있다면 그건 실패한 것
    • sender는 timeout 시 가장 오래된 ACK 없는 애부터 ACK 없는 패킷 재전송
      • 사실상 ACK 없는 애부터 모든 패킷이지
    • 이건 sender 에서만 buffer가 필요하다

https://i.imgur.com/sNjIpuY.png

  • Sender는 위와 같은 buffer를 가짐

    • ACK 정상적으로 오면 window는 한 칸씩 우측으로 이동하겠지
    • window size N은 그대로고 말야
    • timeout 되면 window 안에 포함된거 보내는거구
  • 이를 이용한 상태도는 다음과 같다.

https://i.imgur.com/z2pSFBL.png

  1. sender는 일단 base = 1, nextseqnum = 1 초기화한다
  2. 이후 rdt_send() 호출되면
    • 번호붙여서 패킷전송하지
    • 타이머도 시작하고 (start_timer)
  3. receiver는 일단 받으면 마지막 성공 보내고
  4. 정상인 경우 한번 더 넘기고 기대넘버++ 시키지
    • 어차피 중복패킷은 무시할테니까
  5. sender에서 ACK 받으면
    • base++ 해줘서 Already ACK'd 하나 늘려주고 (#1)
    • 끝났는지 확인해서 끝나면 stop_timer 아니면 타이머 초기화(start_timer)
  6. sender에서 에러뜨면 타이머 대기하고
  7. timeout 시 타이머 초기화하고, 안온것부터 해서 모두 재전송하지
    • ACK 없는 제일 오래된 애부터
  • 참고로 (그림 3.19)에서 Already ACK'd 이걸로 받은거 마치 저장된듯이 보여주는데
    • 사실 저장 안된다. 성공된거는 그냥 신경안쓰고 제거함

https://i.imgur.com/KsoHIdA.png

  • pkt2부터 안온다? 그럼 모두 보내는거야

SR(Selective Repeat) 방식

  • sender는 N개의 패킷을 한꺼번에 보내는 것은 동일

    • 단, 개별 패킷에 대해 receiver가 ACK 보내고
    • sender는 마찬가지로 개별 패킷에 대한 Timer를 가짐
    • timeout 시 해당 개별 패킷만 resend
  • 얘는 비순차적이기에, sender/receiver 둘 다 buffer가 필요하다

  • 생김새는 비슷하기에 뭐 따로 적지는 않겠다

    • 그냥 개별 패킷에 대한 타이머가 있고없고 차이
  • 문제점

    • buffer(window) 크기가 너무 크면 seq num에서 중복이 일어날 수 있다
    • 따라서 window size <= seq num / 2 이어야 함

3.5 연결지향형 트랜스포트: TCP - 세그먼트 구조

  • 흐름 제어
    • sender는 receiver의 수신 한계를 넘어서는 송신을 하지 않음
    • 이를 위해 receiver는 sender에게 window size을 전송함

https://i.imgur.com/YyRFD46.png

  • src port: 출발지 port
  • dest port: 도착지 port
  • seq num: 패킷 번호
  • ACK num: 기대 ACK 번호 (누적 ACK)
  • head len: length of header
  • R(RST), S(SYN), F(FIN): 연결 관련 상태
  • receive window: receiver의 window size

TCP 왕복시간 및 타임아웃

  • TCP는 GBN과 유사한 타임아웃/재전송 매커니즘을 이용함

    • 모두 보내는 대신, 가장 오래된 ACK 못받은 패킷 하나만 보내는 것
  • 이 때, 타임아웃 거는 주기를 적절하게 잡아야 하는데, 이게 힘들더라

    • 그래서 공식을 사용함
  • 공식 보기 전에, 용어들부터 정의하고 들어가겠다

    • SampleRTT: 실제 측정된 RTT
    • EstimatedRTT: 예측된 RTT
    • DevRTT: 여유값
    • TimeoutInterval: 실제 적용하는 타임아웃 값

https://i.imgur.com/MDcNaQy.png

  • 공식은 위와 같고, 이해는 다음과 같다

    • EstimatedRTT: 이전의 값을 지수적으로 낮추고, 새로운 값을 비율로 넣는 것
    • DevRTT: 이전의 값을 지수적으로 낮추고, 새로운 값(오차)을 비율로 넣는 것
    • TimeInterval: 이거 두 개를 더하는데 DevRTT 값이 낮으니 4를 곱해서 더함
  • ab는 일반적으로 주어짐

3.5 연결지향형 트랜스포트: TCP - 신뢰적인 데이터 전달

  • TCP는 비신뢰적 채널에서도 신뢰적으로 데이터를 전송하지

    • pipeline
    • 누적 ACK
    • 재전송은 하나만 (단일 재전송)
      • 중복 ACK 또는
      • 타임아웃 시점에 재전송
  • 이를 위한 sender부터 보도록 한다

    • 간소화된 TCP Sender
    • 중복 ACK 무시, 흐름제어/혼잡제어 무시

https://i.imgur.com/hx3qzgk.png

  • 이러한 구조를 갖게 되면 다음과 같은 동작이 가능하다

ACK 손실

https://i.imgur.com/71ChyGE.png

  • ACK 손실 발생 시
  • sender는 못받았으니 재전송하고
  • receiver는 중복패킷이니 무시하고
  • 마지막 성공 ACK 다시보낸다

지연 발생

https://i.imgur.com/93J9XeV.png

  • receiver로 중복패킷 들어오면
  • 무시하고 마지막 성공 ACK 전송한다
  • sender는 이를 보고 지 할거 하고

누적 ACK

https://i.imgur.com/neGe4Hs.png

  • pipelining 시
  • 들어온 ACK가 지금 가지고 있는 것보다 높으면
  • 그걸로 취한다는 동작

빠른 재전송

  • timeout 주기가 효율적이지 못하면

    • 중복-ACK 사용해 손실된거 감지하고
    • 해당 패킷 재전송하는거
  • 이를 빠른 재전송 이라고 하고

    • 일반적으로 중복-ACK는 3개로 정의함

https://i.imgur.com/klgSXsM.png

연결지향형 트랜스포트: TCP - 흐름제어

  • 흐름제어

    • receiver의 buffer overflow를 방지하는 것
    • receiver가 주체
  • Receiver는 앞서 본 TCP Segment의 헤더 부분에

    • rwnd(receive window?) 값을 넣어서
    • Sender에게 버퍼 여유공간을 알림
  • Sender는 이 값을 보고 얼마나 보내야겠다 판단하는 것

    • 당연한 말이지만, 여유 공간보다 적게 보내겠지

연결지향형 트랜스포트: TCP - 연결설정

  • TCP는 handshake 한다고 했었지

    • 여기서 buffer(window) size, seq number 이런거 교환하는 거
    • 메시지 교환이 아니라
  • 이 때, handshake는 2-way가 아니라, 3-way handshake를 진행한다

    • handshake 시 손실이나 에러, 지연, 순서 어긋남 등이 발생할 수 있기 때문

2-way handshake에서 문제가 발생되는 이유

https://i.imgur.com/QGnbeJZ.png

  • 서버에 연결은 되었는데

    • 클라이언트는 없는 상황
  • 따라서 3-way handshake를 사용하여 이를 방지해야만 한다

TCP 3-way handshake

https://i.imgur.com/Pbs2LED.png

  1. server에서는 먼저 SYN listen
  2. client에서 SYN 보내고
  3. server에서 받으면 SYN + ACK 보냄
  4. client에서 이거 받으면 마지막으로 ACK 보내고

이를 FSM으로 표현하면 다음과 같음

https://i.imgur.com/L3QZsSz.png

Close

https://i.imgur.com/0mTdyU0.png

  • client, server 각각 한 번씩 FIN을 보내게 됨
  • client는 마지막 FIN을 받아도 조금 기다리는데, 이는 지연된 데이터가 있을까봐 그러는 것

혼잡제어의 원리

  • receiver 주체의 흐름제어와는 달리

    • 혼잡제어는 sender가 알아서 제어하는 것
  • 왜 혼잡이 일어나느냐?

    • 너무 많은 Source에서 너무 많은 데이터를 너무 빨리 송신
    • 그 결과 라우터에서 이걸 다 처리할 수가 없게 되고,,,
  • 그럼 혼잡이 일어나면 어떻게 되느냐?

    • 패킷 손실
    • 패킷 지연

혼잡 시나리오

  • 이제부터 우린 '왜 혼잡이 일어나는지' 보도록 하겠다

https://i.imgur.com/8fp7CaV.png

  • 송신률: lambda_in, lambda_out
  • 라우터 처리량: R

시나리오 1 - 무한 크기의 버퍼

  • 가정

    • 무한 버퍼
    • 재전송 없음
  • 이 결과 다음과 같이 나타남

https://i.imgur.com/ocV4cYt.png

  • 라우터는 최대 R만큼 처리할 수 있으며
    • link가 2개니, 결국 R / 2가 최대 처리량
    • 이걸 넘어버리면 일단 큐에 저장해대고
    • 계속 큐에만 쌓이니... 딜레이가 개 높아지기만 한다

시나리오 2 - 유한 버퍼 (손실 가능)

  • 가정

    • 유한 버퍼 = 손실 있음
    • Sender는 손실 패킷을 재전송함
  • lambda_in: 보낸 패킷

    • lambda_in': 보낸 패킷 + 재전송 패킷
    • 결국 패킷 손실되면 lambda_in' > lambda_in가 되어버림
  • 이는 두 가지 상황으로 분리가 가능

    • Sender는 R이 처리가능할 때만 패킷을 전송함
    • 걍 계속 보냄

시나리오 2.1 - 처리가능 전송

  • 다음과 같은 그래프가 나오며

https://i.imgur.com/5jZtnkU.png

  • 이는 곧 손실은 없음 을 의미
    • 그러나 실제로는 이렇게 동작하지 않지

시나리오 2.2 - 걍 계속 보냄

  • 손실된 패킷은 한 번만 재전송

https://i.imgur.com/297iqy6.png

  • 이건 무엇을 의미하는가? #1부터 받지 못하는 loss가 생긴다는 말
    • 어쨌건 보내는 패킷은 모두 도착한다는 말
    • 단, delay는 책임못진다

시나리오 2.3

  • 손실된 패킷을 두 번 재전송
    • 넘빠른타임아웃으로 인함

https://i.imgur.com/QB0CVkI.png

  • 이는 곧 모든 패킷을 보낼 수 없음을 의미한다

시나리오 3 - 실제 상황

https://i.imgur.com/jHRJdZK.png

  • 얼마나 끔찍한 상황인가, 근데 이게 실제 현실에서의 상황이다

https://i.imgur.com/igxpSPp.png

  • 패킷 재전송이 빈번하게 일어나
    • 패킷 전송(lambda_in')을 아무리 해도
    • 도착은 정말 일부만 되어버리지

TCP 혼잡제어

  • TCP에서는 AIMD 를 이용해 이런 혼잡을 제어

    • 손실 감지될 때 까지 window++
    • 손실 감지된다? 그럼 window /= 2
    • 그리고 다시, 손실 감지될 때 까지 window++
  • 이런 그래프가 나오겠지

https://i.imgur.com/4kVlnr9.png

window

  • 혼잡 제어 시 다음과 같은 window를 사용한다

https://i.imgur.com/CVSCGtD.png

  • 여기서 이 cwnd가 동적으로 변하는 window 크기

TCP 슬로 스타트

https://i.imgur.com/nQCNSBq.png

  • 하나씩 늘리는 건 좀 느리기에, 'TCP 슬로 스타트' 라는 걸 사용한다
    • 임계치(threshold)까지는 두 배씩 늘리고, 그 이후에는 하나씩 늘림
    • 타임아웃(손실) 발생 시 두 가지 방식으로 이를 처리
      • TCP Reno, TCP Tahoe
      • threshold는 손실 시점의 반으로 줄어듦 (cwnd / 2)

https://i.imgur.com/1TrNHE5.png

TCP Reno

  • 타임아웃이면 cwnd = 1
  • 3개의 중복 ACK면 cwnd /= 2
    • 이후 하나씩 늘림 (threshold 이후니까)

TCP Tahoe

  • 구분 없이 걍 cwnd = 1
    • 마찬가지로 threshold까지는 두 배, 그 이후에는 하나씩

평균 TCP 처리율

  • 슬로스타트 없고, 언제나 데이터 send한다고 하면 다음과 같은 그래프가 만들어지고

https://i.imgur.com/hr2FVX1.png

  • 평균은 그냥 다음과 같이 구할 수 있다
    • (w / 2 + w) / 2 = 3 / 4 w

TCP 공평성

  • N개의 hosts가 R 처리율을 갖는 라우터를 사용한다고 했을 때

    • 이상적으로 각각의 host는 R / N의 처리율을 갖겠지
    • 물론 현실은 그렇지 않음
  • UDP 는 TCP를 사용하지 않는다

    • 즉, 혼잡제어 이런거 없다는 말
    • UDP는 가는데, TCP는 안가고 이런 일이 발생될 수 있다는 말이다
  • 또한 TCP를 다중으로 연결할수도 있음

    • 남들의 대역폭을 훔치는? 뭐 그런거라고도 할 수 있겠고
  • 명시적 혼잡 제어

    • sending 시, router가 datagram의 ECN 이라고 혼잡제어 여부 나타내는 값을 넣어
      • receiver에게 알린다
    • receiver는 이를 segment의 ECE 이라는 혼잡 여부 나타내는 값을 넣어
      • sender에게 알려
      • 조금만 보내라고 함으로써, 명시적으로 제어

1.1 정보는 비트와 컨텍스트로 이루어짐

  • 컴퓨터는 모두 bit(0, 1)로 저장

    • 이를 어떻게 해석하느냐에 따라 의미가 달라지는 것
  • 고급 언어: 프로그래머가 작성한 소스 프로그램(ASCII)

  • 어셈블리 언어: 명령어를 기호로 표시

  • 기계어: bit로 표현된 명령어

1.2 프로그램은 다른 프로그램에 의해 다른 형태로 번역됨

  • Source Program은 c-컴파일러에 의해 기계 명령어의 Object Program으로 번역됨
    • 이는 실행 가능하며 디스크에 저장되어있다가 RAM에 올라가 실행되는거

컴파일 과정

  • 컴파일은 source program에 대해 네 단계를 수행하며 기계어로 번역함
    • 전처리기(CPP), 컴파일러, 어셈블러, 링커

complication system

  • 컴파일 시 옵션들

    • -O: 배포 시
    • -g: 디버깅 시
  • CPP(전처리기) *.c -> *.i

    • 지시어(directive, #)에 따라 source program에 대한 전처리 작업 시행
    • 가령 #include <stdio.h>#define MAX 100 같은 것 말이지
  • 컴파일러 *.i -> *.s

    • 컴파일러는 어셈블리어 프로그램으로 변환하는 작업을 담당
    • 여기까지는 text(ASCII)
  • 어셈블러 *.s -> *.o

    • 어셈블리 코드를 기계어 명령어로 변환하는 작업
    • 재배치 가능한 프로그램 생성해 디스크에 저장
    • 기계어기 때문에, 볼려면 objdump 툴 이용해 dis-assemble해야 함
  • 링커 *.o -> runnable file

    • 라이브러리 등을 결합한 파일 생성
    • 이걸 메모리에 적재해 실행하는 것

1.4 프로세서는 메모리에 저장된 명령어를 읽고 해석함

  • 명령어 해석기인 'Shell' 을 통해 명령을 받고 실행

  • Bus

    • 하드웨어 구성 요소들 간의 정보 전달 배선
    • 단위는 Word
      • 32bit OS: 4byte
      • 64bit OS: 8byte
      • => 레지스터 사용 생각해보면 구분 쉽게 가능
  • IO device

    • 시스템과 외부 장치와의 경계
  • Main Memory

    • 실행되는 프로그램에 대한 데이터 저장
  • Processor: 리소스에 대한 추상화

    • Main Memory에 저장된 프로그램의 명령어 가져와 해독 및 실행
    • 여기에 레지스터, PC, ALU 이런게 있음
    • 명령의 요청으로 인해 프로세서는 주로 다음 작업들을 실행함
      • Load: 메모리를 레지스터로 가져옴
      • Store: 레지스터 값을 메모리에 저장
      • Operate: 레지스터에 대해 ALU에서 연산을 진행하고, 이를 다시 레지스터에 저장
      • Jump: PC를 덮어씌워 다음 실행 주소를 지정

Hello Program 실행

컴퓨터 구조를 극단적으로 단순하게 나타내면 다음과 같다.

https://i.imgur.com/NOqmwGk.png

이러한 구조를 가지고 있을 때, ./hello 프로그램을 실행한다고 하겠다.

https://i.imgur.com/Z39ZRX9.png

1. 먼저 hello를 입력해야겠지

2. 이 문자열은 CPU를 거쳐 Memory에 저장됨

https://i.imgur.com/MOhpBlW.png

3. 디스크에서 hello 파일 찾아내 메모리에 적재

https://i.imgur.com/xtODNG5.png

4. 프로그램을 실행한다. 내용은 "Hello"를 프린트 하라는 것

5. 이를 위해 "Hello" 문자열을 메모리에서 CPU의 레지스터로 이동

6. CPU 레지스터에서 디스플레이 장치로 이동해 화면에 표시

이렇게 진행한다. 참고로, 디스크에서 DMA 이용해 바로 메모리로 가지 않는 이상, 모두 CPU를 거쳐야 한다는 것을 유의.

1.5 캐시 중요, 1.6 저장장치들은 계층 구조를 이룸

  • 시스템에서의 정보 이동으로 많은 시간을 소비
    • 메모리 => CPU => 디스플레이
    • 이를 빠르게 하는 방법으로 메모리가 계층 구조로 설계됨

https://i.imgur.com/zHE3L1i.png

  • 레지스터, 캐시, 메모리, 디스크, 웹 서버

  • 서로 겹치는 부분 두어 빠르게 접근할 수 있도록 함

    • 특히 캐시 메모리를 도입하여 데이터 접근 속도를 매우 높임

1.7 운영체제는 하드웨어를 관리함

  • 하드웨어와 소프트웨어 사이에 위치한 OS

    • SW로 HW를 조작할 수 있도록 함
  • 이는 추상화 를 통해 가능해짐

    • 파일(폴더): 입출력 장치의 추상화
      • USB 이런거를 폴더로 관리하는 걸 생각해보라
    • 가상메모리: 메인 메모리와 디스크 입출력 장치의 추상화
      • 마치 우리는 메모리를 다루는 듯이 프로그래밍하지만, 실제로는 그러하지 않음
    • 프로세스: CPU, Main Memory, IO 모두의 추상화
      • 프로세스는 실행중인 프로그램에 대한 추상화
      • 이는 곧 위의 세 개에 대한 추상화라고도 할 수 있겠음

프로세스

  • 하나의 Processor는 다수의 프로세스를 마치 동시에 실행되듯 관리함
  • 프로세스가 실행되는데 필요한 모든 상태들을 문맥(Context) 이라 함
  • 실행되지 않을 때 이 문맥을 저장하고, 다시 실행될 때 이 문맥을 복원해 실행하는 것
  • 이를 문맥 전환 기법 이라고 함

https://i.imgur.com/UfY7Qrm.png

  • 문맥 전환(Context Switch) 동작

    • Process A가 실행되고 있다가
    • Process B를 실행할 때, 인터럽트 걸고 문맥전환
    • Process B 실행하다가
    • Process A를 실행할 때, 인터럽트 걸고 문맥전환
  • 문맥 전환 동작 2; 쉘의 실행

    • 처음에는 쉘이 제어권을 가짐
    • 쉘에서 hello 쳐서 프로그램 실행하면
    • 일단 system call 이라는 함수로 OS에게 제어권 넘기고
    • OS는 쉘의 context를 저장 후 hello의 context 생성하고 제어권을 hello로 넘김
    • hello가 끝나면 쉘의 context 복구하고
    • 제어권을 쉘로 다시 넘김

스레드

  • 하나의 프로세스에는 Thread라는 다수의 실행 유닛이 있음
  • 동일한 코드와 전역 데이터를 공유
  • 데이터(메모리) 공유 된다는 것이 중요
  • 멀티-프로세서 환경에서의 Multi-Threading은 완전하게 동시에 실행되는 병렬(Parallel) 처리임.

가상메모리

https://i.imgur.com/IuiDCVm.png

  • 메모리를 추상화시킨 것. 이를 통해 메모리를 독립적으로 사용하는 것 같은 효과를 줌.
  • 물론 이는 실제 메모리의 구조가 아님
  • 위 그림같이 코드, 힙, 라이브러리, 스택, 커널 이렇게 분리됨

파일

  • 모든 IO 장치는 파일로 모델링됨
  • 다양한 IO 장치에 대해 통일된 관점을 제공하지

1.8 시스템은 네트워크를 사용하여 다른 시스템과 통신함

  • 컴퓨터 시스템은 네트워크를 통해 서로 연결됨
    • 즉, 또 다른 IO 장치라고 할 수 있겠음
    • 이를 그저 프로토콜에 따라 다르게 처리할 뿐이지

1.9 중요한 주제들

암달법칙

  • 전체 성능의 증가는 성능 높이려는 부분의 비율에 따라 달라짐

    • 가령 곱셈 부분이 50%인 프로그램에 대해, 곱셈기 성능 4배 하면, 전체 성능은 2배가 증가하는 것
  • https://i.imgur.com/TZ9BgtN.png

    • 성능 개선 후 실행 시간 = 영향 안받는 시간 + 영향 받는 시간 / 개선 배율
  • https://i.imgur.com/4hcKP8t.png

    • 얼마나 개선되었는지 비율을 구하는 것은 간단히 이전 시간 / 개선 시간 으로 해 보면 되겠지

수행 시간의 60%를 소모하는 시스템의 일부를 3배 빠르게 개선하였다면, 전체 속도의 향상률은?

  1. a0.6 이라는 말
  2. T_new = (1 - a) T_old + a / k * T_old = 0.4 T_old + 0.2 T_old = 0.6 T_old
  3. S = T_old / T_new = 10 / 6 = 1.666...
    • 1.67배 상승했다고 할 수 있음

소프트웨어를 4 배 성능개선 한다고 할 때, 90%의 시간을 소모하는 시스템의 한 부분을 얼마나 개선해야 하는가?

  1. a = 0.9
  2. T_new = 0.25 T_old = 0.1 T_old + 0.9 / k * T_old
  3. 0.15 = 0.9 / k
  4. k = 6
    • 90% 시간 소모하는 부분을 6배 개선해야 전체 4배 성능개선 된다고 할 수 있음

멀티프로세서

  • 하나의 OS, 여러 CPU

    • 여러 CPU를 하나의 칩에 내장한 것
  • 하이퍼스레딩

    • 하나의 CPU가 여러 스레드 제어
  • 멀티프로세서 성능 개선

    • 멀티프로그래밍: 하나의 CPU 여러 프로세스 (concurrent)
    • 멀티스레드: 여러 CPU 하나의 프로세스 (parallel)
  • 명령어 수준 병렬성

    • 슈퍼스칼라 프로세서: 1클럭 / 하나 이상의 명령어 처리
    • SIMD: 1명령 / 여러 데이터 처리

  • 추상화

    • 파일: 입출력
    • 가상메모리: 메모리
    • 프로세스: 실행 중 프로그램 (프로세서, 메모리, 입출력장치 추상화)
  • 암달법칙

    • T_new = (1 - a) T_old + a / k * T_old

2.1 정보의 저장

  • 모든 정보는 bit

    • 이를 어떻게 해석하느냐에 따라 의미가 달라지는 것
  • byte = 8bit (0x00 ~ 0xFF)

    • 주소지정이 가능한 최소의 단위
    • 이 단위로 주소지정한다는 말
    • 또한 하나의 주소 안에는 하나의 byte가 들어감
  • word (32bit = 4 byte, 64bit = 8 byte)

    • CPU가 한 번에 처리할 수 있는 단위
    • 데이터 타입 크기에도 영향을 끼침
    • 특히 pointer의 경우 word의 크기와 같음 (그리고 pointer는 unsigned long 타입이지)
      • 32bit: 0x 00 00 00 00 => 256^4 byte = 4GB
      • 64bit: 0x 00 00 00 00 00 00 00 00 => 256^8 byte = 16EB
  • 하나의 주소 안에는 하나의 byte가 들어있다

    • 0x00 ~ 0xFF의 값이 들어있음

https://i.imgur.com/PWMqWNz.png

  • 주소지정방식

    • 빅 엔디안(MSB): 작은 주소부터 값이 들어가는 것 => SUN, 네트워크
    • 리틀 엔디안(LSB): 큰 주소부터 값이 들어가는 것 => 인텔
    • 하나의 주소 안에는 하나의 바이트가 들어간다는 것을 잊지 말자
  • 포인터 저장방식

    • 컴파일러, 머신 종류(회사)에 따라 다름
  • 문자열 저장방식

    • 알다시피 문자의 배열로 표현하는데
    • 바이트 순서와 상관없이 항상 낮은 주소부터 저장

부울 대수

  • TRUEFALSE로 표현

  • 다음과 같이 집합으로 표현이 가능

    • 01101001 = {0, 3, 5, 6}
    • 인덱스가 76543210 순서로 간다는 것을 주의
  • left shift: x << y

    • xybit 만큼 좌측 이동
    • 우측은 0으로 채움
  • right shift: x >> y

    • xybit 만큼 우측 이동
    • 논리 쉬프트: 좌측은 0으로 채움
    • 산술 쉬프트: 좌측은 최상위 비트(sign bit)로 채움
      • 수치가 변하지 않게 하는 것이 산술 쉬프트
      • C 컴파일러 기본값. 수치계산 좋아하는 듯

2.2 정수의 표시

  • 정수는 다음과 같이 인코딩됨 (w-byte 워드에 대해)
    • Unsigned: 0 ≤ x ≤ 2^w - 1
    • Signed: -2^(w - 1) ≤ x ≤ 2^(w - 1) - 1

https://i.imgur.com/XVPzEkp.png

  • 주의해야 할 것은 negative가 11..11에서부터 시작한다는 것

    • 이는 그냥 2의 보수 구해보면 간단히 나오긴 함
    • 참고로 0S_MIN의 경우 2의 보수 취해도 자기 자신이 나옴
  • 뭐 근데 보다싶이 해석만 다르게 진행되는 것이지, bit는 같다는 것을 잊지 말자

    • 따라서 unsigned <-> signed는 묵시적으로 형변환 가능히다
    • operand 중 어느 하나라도 unsigned면, 모든 operand와 결과값이 unsigned가 됨
  • signed type에 대해, bit 확장 시 부호 비트가 복사되어 확장됨

    • 가령 1000 0000을 4bit 확장한다 하면 다음과 같음
    • 1000 0000 => 1111 1000 0000
    • right shift를 생각해보면 된다. 기본값이 arithmetic shift니까...
    • negative signed value에서 unsigend value로의 변환은 간단히 neg_signed_num + U_MAX + 1
    • -1은 항상 { 1111 11..11 1111 }(2)

2.3 정수의 산술연산

https://i.imgur.com/deUDODm.png

  • unsigned 덧셈
    • 더하고 overflow되는 bit는 버림

https://i.imgur.com/zDJADtR.png

  • signed 덧셈
    • 마찬가지로 overflow되는 bit는 버리는데,
    • 부호가 반대가 되겠지. 맨 아래서부터 다시시작하잖아

곱셈

  • Unsigned 곱셈: 0 * 0 ≤ x * y ≤ (2^w - 1) * (2^w - 1)

    • 최소값: 0
    • 최대값: (2^w - 1)^2
  • Signed 곱셈: -2^(w - 1) * (2^(w - 1) - 1) ≤ x * y ≤ -2^(w - 1) * -2^(w - 1)

    • 최소값: -2^(2w - 2) + 2^(w - 1)
    • 최대값: 2^(2w - 2)
  • 이렇게 계산된 결과에서 overflow bits를 버린다.

  • 2 멱승 곱셈은 shift를 사용해 쉽게 가능하겠지

나눗셈

  • shift 이용하면 나눗셈도 가능

    • 당연히 기본값인 arithmetic shift가 적용됨
  • floating일 경우 방향이 반대인 반올림이 됨

    • 13 >> 1 = 6 (origin: 6.5)
    • -13 >> 1 = -7 (origin: -6.5)

2.4 부동소수점

  • 부동소수점의 이진 표현 (정규화)

    • +- 1.xxxx * 2^(yyyy) (x는 binary)
    • { 110.1001 }_(2) = { 1.101001 }_(2) * 2^(2)
  • 지수표기는 2^n으로 나눠떨어져야 유한소수로 표현됨

    • 즉, 표현에 한계가 있고, 이걸 넘어가는 애들은 중간에 잘라 approximation 함
    • 이 때문에 오차가 발생되는 것이고
  • 2진수 부동소수점 to 10진수

    • 그냥 2^(-i)로 진행하면 된다.
    • { 110.1001 }_(2) = 2^2 * 1 + 2^1 * 1 + 2^(-1) * 1 + 2^(-4) * 1 = 6.5625

단일정밀도

https://i.imgur.com/tS31Qvh.png

  • 단일정밀도 (single precision): 32bit
    • sign: 1bit
    • exp: 8bit
    • frac: 23bit
    • (-1)^<sign> * 1.<frac> * 2^<exp>

단일정밀도 인코딩; { -0.75 }_(10)을 기준으로

  1. 일단 이걸 2진수 부동소수점 형태로 바꿔줌
    • { -0.75 }_(10) = { -0.11 }_(2) = -1 * { 1.1 }_(2) * 2^(-1)
  2. 이걸 통해 변환해주는 것
    • sign bit: 1 (negative)
    • frac bit: 1
    • exp bit: -1 + 127 = { 126 }_(10) = { 0111 1110 }_(2)
  3. exp 부분은 음수 표현 못하게 +127을 해서 넣어준다는 것을 유의
    • 이를 bias 라고 함
  4. Q.E.D. 1 01111110 10000000000000000000000
    • exp는 우측부터 좌측으로 2^{i}가 증가하고
    • frac은 좌측부터 우측으로 2^{i}가 감소함
    • 2진수 부동소수점 표현을 생각해보면 좋을 것
  • 팁: 10진수 소수점을 2진수 소수점으로 바꾸기
    • 수에 계속 2를 곱해줌
    • 1이상이 나오면, 해당 자리에 1이 들어가고
    • 안나오면, 0이 들어감
    • 하다가 정확히 1이 나오면 1 넣고 끝

단일정밀도 디코딩; { 1 01111110 10000000000000000000000 }_(2)를 기준으로

  1. 일단 이를 통해 빼올 수 있는 정보 빼오고
    • sign bit: 1
    • frac binary: 1.1
    • exp: 126 - 127 = -1
      • { 01111110 }_(2) = 126
      • 위에서 음수표현땜에 +127 했기에, -127을 똑같이 해줌
  2. 이를 통해 2진수 부동소수점 형태로 정규화 한 담에, 소수점으로 풀어주고
    • (-1)^1 * { 1.1 }_(2) * 2^(-1) = { -0.11 }_(2)
  3. 이를 10진수로 바꾸어주면 되겠지
    • { -0.11 }_(2) = -(0.5 + 0.25) = -0.75

최대 및 최소값

  • exp 값에 따라 달라질 수 있겠다

    • 참고로 00000000, 11111111 이 둘은 예약됨
  • 따라서,

    • 최소값은: exp = 00000001, frac = 000...0000
    • 최대값은: exp = 11111110, frac = 111...1111

이중정밀도

  • 이중정밀도 (double precision): 64bit

    • sign: 1bit
    • exp: 11bit
    • frac: 52bit
  • 참고로 bias = { 111 1111 1111 }_(2) = 1023

    • 인코딩 또는 디코딩 시 +1023, -1023 해 줘야 한다는 말
    • 모든 음수를 포용해야 하니 이렇게 수가 나오는 것

연산

  1. 지수를 맞춤
  2. 유효자리 부분 더함
    • 지수부 제외 나머지 부분
  3. 정규화
  4. 이를 미리 정의한 유효자리 에 맞춤 (round)
    • overflow 발생 방지를 위해

예제1: 9.999 * 10^1 + 1.610 * 10^(-1) (유효자리 4자리 가정)

  1. 지수를 큰 수에 맞춤
    • 9.999 * 10^1 + 0.016 * 10^1
  2. 유효자리 더함
    • (9.999 + 0.016) * 10^1 = 10.015 * 10^1
  3. 정규화
    • 1.0015 * 10^2
  4. 유효자리에 맞춰 round
    • Q.E.D. 1.002 * 10^2

예제2: 0.5 + (-0.4375) (유효자리 4자리 가정)

  1. 정규화
    • 0.5 = { 1.0 }_(2) * 2^(-1)
    • -0.4375 = { -0.0111 }_(2) = { -1.11 } * 2^(-2)
  2. 지수 맞춤
    • { 1.0 }_(2) * 2^(-1) - { 0.111 }_(2) * 2^(-1)
  3. 유효자리 덧셈
    • { 0.001 }_(2) * 2^(-1)
  4. 정규화 및 유효자리 round
    • Q.E.D. { 1.0 }_(2) * 2^(-4)

예제3: (1.110 * 10^(10)) * (9.200 * 10^(-5)) (유효자리 4자리)

  1. 곱셈의 경우는 지수부 맞출 필요 없고, 서로 더해주면 됨
    • 10 + (-5) = 5
  2. 유효자리 곱셈
    • 1.11 * 9.2 = 10.212
  3. 조합
    • 10.212 * 10^5
  4. 정규화 및 유효자리 round
    • 1.0212 * 10^6 => 1.021 * 10^6
  5. 부호 결정
    • Q.E.D. + 1.022 * 10^6

예제4: 0.5 * (-0.4375) (유효자리 4자리)

  1. 정규화
    • 0.5 = { 1.0 }_(2) * 2^(-1)
    • -0.4375 = { -1.11 } * 2^(-2)
  2. 지수 덧셈
    • -1 + (-2) = -3
  3. 유효자리 곱셈
    • 1.0 * 1.11 = 1.11
  4. 조합
    • { 1.11 }_(2) * 2^(-3)
  5. 부호 결정 (pos * neg = neg)
    • Q.E.D. - 1.11 * 2^(-3)

3.1 역사적 관점

  • 칩 종류
    • CISC: 많은 기계 명령어 (Complex)
      • 호환성땜에 사용
    • RISC: 일부 명령어 (Reduced)
    • 요즘은 CISC가 RICS 따라잡았다

3.2 프로그램의 인코딩

  • 여러 상태들

    • PC: 프로그램 카운터 (또는 RIP)
      • 다음 실행될 명령어 주소 저장
    • 레지스터 파일
      • 자주 사용되는 프로그램 데이터 저장
    • 조건 코드
      • 최근에 수행된 연산 결과에 대한 상태 저장
      • 가령 a > b 연산 진행했을 때 a - b의 sign bit만 저장하고 있다던가...
      • 이를 이용해 jump, if 등을 수행하는 것
    • 메모리
      • 프로그램의 코드와 데이터가 들어가는 곳
  • 디버깅을 위한 최적화는 -Og를 사용

    • 어셈블리어 코드 생성을 위한 -S 옵션
    • 목적코드 생성을 위한 -c 옵션
    • 실행파일 생성을 위한 -o 옵션
  • 실제 실행파일 생성 시에는 linking 과정을 거치기에

    • 메모리 위치도 달라지고
    • 함수도 실제 위치로 연결된다
  • 어셈블리어에서 소괄호(' () ')는 pointer를 의미한다

    • 즉, 소괄호 안의 값을 메모리 주소삼아서...

3.3 데이터의 형식

C Intel Assembly Size(byte)
char Byte b 1
short Word w 2
int Double Word l 4
long Quad Word q 8
char * Quad Word q 8
float Single Precision s 4
double Double Precision l 8
  • 위의 것들이 명령어에 접미어로 붙어 타입을 명시하는 것
    • movq, leaq
    • 참고로 q는 대부분 생략 한다고 함

3.4 정보 접근하기

레지스터

Usage Name(64bit) Name(32bit)
Return Value %rax %eax
Callee Saved %rbx %ebx
4th arg %rcx %ecx
3rd arg %rdx %edx
2nd arg %rsi %esi
1st arg %rdi %edi
Stack Pointer %rsp %esp
Callee Saved %rbp %ebp
5th arg %r8 %r8d
6th arg %r9 %r9d
Caller Saved %r10 %r10d
Caller Saved %r11 %r11d
Callee Saved %r12 %r12d
Callee Saved %r13 %r13d
Callee Saved %r14 %r14d
Callee Saved %r15 %r15d
  • 레지스터 종류는 위와 같음 (16개로 한정됨)

    • args가 6개를 넘어가면 어쩔 수 없이 메모리를 이용해 저장
    • 호환성을 위해 64bit 말고도 32bit, 심지어 16bit 8bit도 접근이 가능
  • 일반적으로 명령은 하나 이상의 operand를 가짐

    • 상수($~), 레지스터(%~) 또는 메모리 값((~))이 될 수 있겠지
    • 소괄호가 pointer를 의미한다는 것을 다시 한 번 말한다

명령어 주소지정 형식

Type Form Value Name
상수 $Imm Imm 즉시값 (Immediate)
레지스터 r_a R[r_a] 레지스터의 값
메모리 Imm M[Imm] 절대 참조
­ (r_a) M[R[r_a]] 간접 참조
­ Imm(r_b) M[Imm + R[r_b]] 베이스(R[r_b]) + 오프셋(Imm)
­ (r_a, r_i) M[R[r_a] + R[r_i]] 인덱스
­ Imm(r_a, r_i) M[Imm + R[r_a] + R[r_i]] 인덱스
­ (r_b, r_i, s) M[R[r_b] + R[r_i] * s] 인덱스
­ Imm(r_b, r_i, s) M[Imm + R[r_b] + R[r_i] * s] 인덱스
­ (, r_i, s) M[R[r_i] * s] 인덱스
­ Imm(, r_i, s) M[Imm + R[r_i] * s] 인덱스
  • 참고로 더해지는 Imm1 byte 단위

예제: operand 값 구하기

https://i.imgur.com/kEsT8go.png

  • %rax = 0x100

    • 참조 이런게 아니고, 그냥 레지스터 안의 값을 가져옴
  • 0x104 = 0xAB

    • $가 붙지 않으면 절대참조(M[0x104])가 됨
  • $0x108 = 0x108

    • $가 붙는 건 상수
  • (%rax) = 0xFF

    • %rax = 0x100이고, 이를 값으로 주소참조하니...
  • 4(%rax) = 0xAB

    • 4(%rax) = M[4 + 0x100]
  • 9(%rax, %rdx) = 0x11

    • 참고로 9는 10진수
    • 9(%rax, %rdx) = M[0x9 + 0x100 + 0x3]
  • 260(%rcx, %rdx) = 0x13

    • 260이 10진수 라는 것을 주의하자. 16진수로 바꾸면 0x104
    • 260(%rcx, %rdx) = M[0x104 + 0x1 + 0x3]
  • 0xFC(, %rcx, 4) = 0xFF

    • 0xFC(, %rcx, 4) = M[0xFC + 0x1 * 4]
  • (%rax, %rdx, 4) = 0x11

    • (%rax, %rdx, 4) = M[0x100 + 0x3 * 4]

이동 명령을 통한 참조 기법

  • movq <src>, <dest> 명령과, 위의 명령어 주소지정 형식을 이용하면 간결하게 참조 및 대입을 할 수 있다
Assembly C
movq $0x4, %rax t1 = 0x4;
movq $-147, %rax *t1 = -147;
movq %rax, %rdx t2 = t1;
movq %rax, (%rdx) *t2 = t1;
movq (%rax), %rdx t2 = *t1;
  • 꽤나 유용하고 자주 사용하는 기법

3.5 산술연산과 논리연산

  • 여기서 q 생략한다

  • lea 명령은 pointed 되는 값이 아니라, 주소 자체를 적재하라는 말

    • lea 0xfffffbf4(%ebp), %eax => %eax := %ebp + 0xfffffbf4
    • 이를 이용하면 위와 같이 매우 빠른 게산 및 적재를 진행할 수 있다.
  • 헛갈리기 쉬운 일부 명령어에 대해서만 정리함

    • salq <src>, <dest> => dest <<= src
    • sarq <src>, <dest> => dest >>= src // Arithmetic
    • shrq <src>, <dest> => dest >>= src // Logical
    • incq <dest> => dest += 1
    • decq <dest> => dest -= 1
    • negq <dest> => dest = -dest
    • notq <dest> => dest = ~dest
  • 문자열은 C에서도 그러하듯 어떤 값으로 나타낼 수 없기에, pointer를 통해 지정

    • register 내에서도 포인터 값이 들어가게 된다

일반적인 레지스터의 이용

  • temporary: %rax, %rdx, %rcx, ...

  • Location runtime stack: %rsp

    • local variable이 들어가는 스택
  • Location current code control point: %rip

    • Program Counter
  • Statuc of Recent Tests (Condition Codes): CF, OF, SF, ZF

    • CF: Crry Flag
    • OF: Overflow Flag
    • SF: Sign Flag
    • ZF: Zero Flag
    • 이들은 아래에서 다룸

산술연산 번역의 예

  • 다음의 코드에 대해
long arith(long x, long y, long z) {
  long t1 = x + y;
  long t2 = z + t1;
  long t3 = x + 4;
  long t4 = y * 48;
  long t5 = t3 + t4;
  long rval = t2 * t5;
  return rval;
}
  • 어셈블리로 번역하면 다음과 같다.
arith:
  leaq (%rdi, %rsi), %rax       # t1
  addq %rdx, %rax               # t2
  leaq (%rsi, %rsi, 2), %rdx    # t4
  salq $4, %rdx
  leaq 4(%rdi, %rdx), %rcx      # t5
  imulq %rcx, %rax              # rval
  ret
  • 이해가 안 된다면 직접 하나하나 연결하면서 해 보자

    • t3t5 연산 과정 안에 포함됨
    • t4 계산은 빠른 곱셈 계산을 위해 shift를 사용하려고 하다 변형된 것
  • 참고로 반환이 int 타입일 경우 %rax가 아니라 %eax가 된다는 것을 유의

3.6 제어문

  • 연산 결과를 Condition으로 지정하기 위해, Condition Code 라는 것을 도입했다

    • CF: Crry Flag
      • 최근 연산 결과에서 올림수 발생 시 1
      • unsigned type의 overflow 검출 시 유용하게 사용
        • sign type에서는 다른 overflow가 발생된다
        • 이는 OF를 참고
    • ZF: Zero Flag
      • 최근 연산 결과가 ZERO 인 경우 1
      • 연산 결과가 0이어야 ZF := 1이 된다는 것을 매우 조심하자
    • SF: Sign Flag
      • 최근 연산 결과가 음수 인 경우 1
      • 즉, sign type의 sign bit라고도 할 수 있겠다
    • OF: Overflow Flag
      • 연산 결과로 2의 보수 overflow 발생 시 1
      • signed type에서 overflow 검출 시 유용하게 사용
      • 물론 unsigned type에서도 사용은 가능하지만, 다음의 규칙이 있다.
        • Unsigned 일 때: CF == OF
        • Signed 일 때: CF != OF
        • CF는 그저 올림수가 발생되었는지 여부만을 따진다
        • Singed의 overflow는 올림수가 아니라, 부호가 뒤바뀌는 것이니까...
  • 일반적인 명령의 결과로 Condition Code가 업데이트됨 (implicit 하게)

  • lea로 연산할 경우 Condition Code 업데이트 안된다

    • 물론 explicit하게 할 수는 있음
    • cmp, test 명령을 사용하여 가능
  • cmpq <src2>, <src1>

    • 순서 주의, 참고로 종종 setX와 함께 사용함
    • src1 - src2 결과로 Condition Code 업데이트
    • dest가 없기에, src 중 어떠한 곳도 값 업데이트가 되지 않음
  • test <src2>, <src1>

    • 순서 주의
    • src1 & src2 결과로 Condition Code 업데이트
    • 마찬가지로 dest 없으며, src 중 어떠한 곳도 값 업데이트 없음
  • 주의사항들

    • unsigned 0x1 - 0x2 진행하면 U_MAX 나오는데, 이 때 CF := 1이 된다
      • 물론 OF := 1
    • signed S_MAX + 0x1 해도 CF := 0
      • 단, OF := 1
    • unsigned type에서 각각의 operand는 negative value를 가질 수 없다 는 것을 유의한다

setX <dest> 명령어

  • 조건에 따라 dest의 값을 set
command condition description
sete ZF equal, zero
setne ~ZF not equal, not zero
sets SF negative
setns ~SF non-negative
setg ~(SF ^ OF) & ~ZF greater (signed)
setge ~(SF ^ OF) greater equal (signed)
setl (SF ^ OF) less (signed)
setle `(SF ^ OF) ZF`
seta ~CF & ~ZF Above (unsigned)
setb CF Below (unsigned)
  • 외우지 말자
    • sete, setne, sets, setns 이거 네 개는 설명 없어도 이해갈테니
    • 나머지에 대한 예제를 보며 이해해보도록 하자

Signed type에 대한 setX 예제

command condition description
setg ~(SF ^ OF) & ~ZF SFOF가 같고, ZF0이 아닌 경우
setge ~(SF ^ OF) SFOF가 같음
setl (SF ^ OF) SFOF가 다름
setle `(SF ^ OF) ZF`
  • 다음 명령에 대해 진행한다
cmpq b, a     # a - b

setg %al
setge %bl
setl %cl
setle %dl

Case 1; a := 0x10, b := 0x5 (a > b)

  • a - b = 0x5
    • CF := 0
    • ZF := 0
    • SF := 0
    • OF := 0
setg %al    # 1
setge %bl   # 1
setl %cl    # 0
setle %dl   # 0

Case 2; a := 0x10, b := 0x10 (a = b)

  • a - b = 0
    • CF := 0
    • ZF := 1
    • SF := 0
    • OF := 0
setg %al    # 0
setge %bl   # 1
setl %cl    # 0
setle %dl   # 1

Case 3; a := 0x5, b := 0x10 (a < b)

  • a - b = -0x5
    • CF := 0
    • ZF := 0
    • SF := 1
    • OF := 0
setg %al    # 0
setge %bl   # 0
setl %cl    # 1
setle %dl   # 1

Case 4; a := S_MAX, b := -0x1 (a - b = 'positive overflow')

  • a - b = S_MIN // positive overflow
    • CF := 0
    • ZF := 0
    • SF := 1
    • OF := 1
setg %al    # 1
setge %bl   # 1
setl %cl    # 0
setle %dl   # 0

Case 5; a := S_MIN, b := 0x1 (a - b = 'negative overflow')

  • a - b = S_MAX // negative overflow
    • CF := 0
    • ZF := 0
    • SF := 0
    • OF := 1
setg %al    # 0
setge %bl   # 0
setl %cl    # 1
setle %dl   # 1

Unsigned type에 대한 setX 예제

command condition description
seta ~CF & ~ZF CFZF 둘 다 0인 경우
setb CF CF1인 경우
  • 다음 명령에 대해 진행한다
    • 이 때, ab는 Unsigned type
cmpq b, a     # a - b

seta %al
setb %bl

Case 1; a := 0x10, b := 0x5 (a > b)

  • a - b = 0x5
    • CF := 0
    • ZF := 0
    • SF := 0
    • OF := 0
seta %al  # 1
setb %bl  # 0

Case 2; a := 0x5, b := 0x10 (a < b)

  • a - b = U_MAX - 0x5 // underflow
    • CF := 1
    • ZF := 0
    • SF := 0
    • OF := 1
seta %al  # 0
setb %bl  # 1

jX <dest> 명령어

  • 조건에 따라 dest로 jump
    • 규칙은 setX와 같다
command condition description
jmp 1 jump dest (unconditional)
je ZF equal, zero
jne ~ZF not equal, not zero
js SF negative
jns ~SF non-negative
jg ~(SF ^ OF) & ~ZF greater (signed)
jge ~(SF ^ OF) greater equal (signed)
jl (SF ^ OF) less (signed)
jle `(SF ^ OF) ZF`
ja ~CF & ~ZF Above (unsigned)
jb CF Below (unsigned)
  • 마찬가지로 외울 필요 없이 상황을 가정하고 잘 생각해본다

규칙에 대한 이해

  • greater

    • ab보다 큰 경우
    • a - b는 positive가 될 것이다 (SF := 0, OF := 0)
    • negative가 되는 경우는 overflow가 되는 것 밖에 없다 (SF := 1, OF := 1)
  • less

    • ab보다 작은 경우
    • a - b는 negative가 될 것이다 (SF := 1, OF := 1)
    • positive가 되는 경우는 overflow가 되는 것 밖에 없다 (SF := 0, OF := 1)
  • above

    • ab보다 큰 경우
    • a - b는 overflow가 될 수 없고 (~CF)
    • zero 값 역시 불가능하다 (~ZF)
  • below

    • ab보다 작은 경우
    • a - b는 무적권 overflow가 발생된다 (CF)

조건 분기

  • jump를 사용하여 조건 분기를 할 수 있다
long absdiff(long x, long y) {
  long result;

  if (x > y) {
    result = x - y;
  } else {
    result = y - x;
  }

  return result;
}
  • 위 C 코드는 다음과 같이 번역된다
absdiff:
  cmpq %rsi, %rdi   # xy의 크기 비교 (x - y)
  jg .L4            # x > y 인 경우 L4로 jump

  # x <= y
  movq %rsi, %rax   # result = y
  subq %rdi, %rax   # result -= x
  ret               # return result

.L4:
  # x > y
  movq %rdi, %rax   # result = x
  subq %rsi, %rax   # result -= y
  ret               # return result
  • 주의할 것은, goto처럼 해당 라벨로 이동한 다음 계속 명령을 진행하는 것이기에
    • 중간의 ret 처럼 반드시 끊어주거나
    • 아니면 다른 라벨로 jump 시켜줘야만 한다

cmovX <src>, <dest> 명령 (Conditional Move Instruction)

  • 분기 명령은 솔직히 말해 좋지 못한 패턴

    • 파이프라인 처리를 방해하여 병렬 처리 못하게 한댄다
    • 이는 컴파일 시 -fif-conversion 옵션으로 cmovX 명령 사용하도록 할 수 있음
  • cmovX 명령은 조건에 따라 데이터 이동하는 명령

    • 조건문 있으면, 각 상황의 값 모두를 계산해 놓고
    • condition 계산되면 해당 값으로 사용하는 것
    • 참고로 X 보면 알 수도 있겠는데, 규칙은 setXjX와 같음
  • goto로 이를 표현해보면 다음과 같다

// common representation
val = Condition ? Then_Expr : Else_Expr;

// goto representation
true_val = Then_Expr;
result = Else_Expr;

if (Condition) result = true_val;

return result;
  • 유의사항
    • 과도한 계산 수행 자제
      • val = Test(x) ? HardWork_1(x) : HardWork_2(x);
      • 모든 값을 계산하기에, 성능 이슈 발생 가능
    • 위험한 계산 자제
      • val = p ? *p : 0
      • 모든 값을 계산하기에, p가 null pointer인 경우 에러 발생 가능
    • side-effects 발생 가능
      • val = Test(x) ? x *= 10 : x *= 5;
      • 모든 값을 계산한다는 의미는, 양쪽의 코드를 실행한다는 의미
      • 즉, 위와 같을 경우, x *= 10x *= 5 둘 다 실행하게 되어서
      • 의도치 않았던 결과를 내보일 수 있음
@Gumball12
Copy link
Author

네트워크

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment