Study with me =)

• 만약 어떤 player도 strictly dominant strategy(SDS)가 없다면 어떻게 해야 하는가?
  • Nash Equilibrium
    • P1이 S전략을 가지고 있고 P2가 T전략을 가지고 있다.
    • S가 T의 best response이며 T가 S의 best response라면 이는 Nash Equilibrium이다.
  • 만약 서로의 전략이 best response라면 다른 전략으로 이탈할 가능성이 없으므로 평형 상태라고 할 수 있다.
• 반면, 서로의 best response가 아닌 전략은 왜 평형 상태가 아닌가?
  • 상대가 다른 전략을 쓸 여지가 남아 있기 때문이다.
  • 결론적으로 Nash Equilibrium은 믿음의 평형이라 할 수 있다.

여섯번째 게임: 세 클라이언트 게임

• 두 회사 모두 SDS가 없다.
• 회사1의 best response는 A전략이다.
• 회사2의 best response는 A전략이다. 
• 따라서 (A,A)는 Nash 평형이다.

일곱번째 게임: 코디네이션 게임

• 두개의 Nash 평형이 생긴다. 
  • (파워포인트, 파워포인트)
  • (키노트, 키노트)
• 이때는 Focal point를 고려해야 한다.
• 몇몇 게임에서는 player가 하나의 Nash 평형 선택지를 고르도록 하는 자연스러운 요인이 있다.
• Nash를 확인하기 위해서 서로의 선택이 best인지 확인하는 것이 중요하다.

여덟번째 게임: stag hunt 버전의 발표냐 시험이냐

• SDS는 없고 Nash가 두개이다.
• 만약 당신이 더 높은 보상을 줄 수 있는 평형 전략을 선택할 것이라면 (발표,발표), 상대가 시험공부하기로 선택했을 수 있다는 리스크를 안고 가야한다.

아홉번째 게임: Hawk-Dove 게임

• 이 경우는 SDS가 없고 Nash가 있지만 같은 전략이 아닌 경우이다.
• (D,H)와 (H,D)가 Nash 평형 전략이고 이런 경우를 Chicken game이라 한다.
• 한쪽이 이득을 얻게 된다.
• 만약 Nash Equilibrium이 없다면 Mixed Stage를 사용해야 한다.
• 전략을 선택할 가능성을 정한다.
• players가 랜덤하게 행동할 수 있다면 Nash Equilibria는 항상 존재한다.

열번째 게임: 단순한 공격-방어 게임

• 이렇게 참가자들의 offset을 다 더하면 0이 되는 게임을 zero-sum game이라 한다.
• 어떤 경우에도, 각 플레이어는 자신의 동전을 뒤집고 싶어 할 것이므로 Nash 평형은 있을 수 없다.
• 왜냐하면 Nash는 상대의 전략을 알고 있어도 자신의 전략을 바꿀 여지가 없는 경우를 뜻하기 때문이다.
• 따라서 이 게임에서는 player가 서로의 전략을 예측하기 어렵도록 만들어야 한다. 이때 Mixed Strategies가 사용된다.
• H나 G를 전략으로 선택하는 것이 아닌, H를 선택할 확률과 G를 선택할 확률을 고른다.
• 이제 더이상 전략은 두개가 아니라, 0과 1사이 수의 집합이 된다.
• 즉, option을 mixing한 것과 같은 효과가 있다.
• Nash는 모든 게임에 최소한 하나의 mixed-strategy equilibrium이 있다는 것을 증명했다.
• 또한 한 게임에 pure strategy와 mixed가 둘 다 있을 수 있다.

• player2가 S전략을 행할 확률 q에 대한 player1의 payoff 계산
• player1이 S전략을 행할 확률 p에 대한 player2의 payoff 계산

• 게임에는 player, strategies, payoff 세 가지 요소가 있다.
• 상대의 선택을 SEPARATELY하게 분석해야 한다.
• 게임이론에서 중요한 것이 두가지 있다.
  • Best Response
    • S가 P1의 전략, T가 P2의 전략이라 할 때 전체 전략은 (S, T)라 한다.
    • P1(S, T)는 P1의 offset이다.
    • P2(S, T)는 P2의 offset이다.
    • P1(S, T) ≥ P1(S’, T)인 경우 S는 best response이다.
    • P1(S, T) > P1(S’, T)인 경우 S는 strict best response이다.
  • Dominant Strategy
    • P2의 모든 전략에 대해 best response인 P1의 전략은 dominant strategy이다.
    • P2의 모든 전략에 대해 strictly best response인 P1의 전략은 strictly dominant strategy이다.
    • player는 상대의 전략에 대해 여러 개의 dominant strategy를 가질 수 있다.

첫 번째 게임: 시험이냐 발표냐

• 만약 상대가 발표를 준비한다면, 당신은 발표를 준비할 때 90점, 시험을 준비할 때 92점을 받으므로 시험을 준비해야 한다.
• 만약 상대가 시험을 준비한다면, 당신은 발표를 준비할 때 86점, 시험을 준비할 때 88점을 받으므로 시험을 준비해야 한다.
• --> 상대가 뭘 하든 당신은 시험을 준비해야 한다. 이때 상대의 선택에 따라 당신의 더 나은 선택이 바뀌지 않으므로 이를 Strictly dominant strategy라 한다.
• --> 예상 평균은 88이다. 당신도 당신의 상대도 시험을 준비하는 것이 이득이기 때문이다.
• --> 이처럼 더 나은 상생에 대한 협의 없이 각자의 이득을 극대화하기 위한 것을 Rational Play라 한다.

두 번째 게임: 죄수의 딜레마

• 만약 죄수 2가 자백하지 않는다면, 죄수 1은 자백해야 할 것이다.
• 만약 죄수2가 자백한다면, 죄수 1은 자백해야 할 것이다.
• --> 죄수2가 뭘 하든 죄수 1은 자백해야 할 것이고 이는 strictly dominant strategy이다.

세 번째 게임: 약물을 할 것인가?

• 만약 선수 2가 약물을 하지 않는다면, 선수 1은 약물을 해야 할 것이다.
• 만약 선수2가 약물을 한다면, 선수 1은 약물을 해야 할 것이다.
• --> 선수2가 뭘 하든 선수 1은 약물을 해야 하므로 이는 strictly dominant strategy이다.
• --> 서로 우위를 점하기 위해 계속해서 위험한 선택을 하는 것을 Arms races라 한다.

네 번째 게임: 쉬운 시험일 때, 시험이냐 발표냐

• 만약 상대가 발표를 한다면, 당신은 발표를 해야 한다.
• 만약 상대가 시험을 준비한다면, 당신은 발표를 해야 한다.
• --> 상대가 뭘 하든 당신은 발표를 준비해야 하므로 이는 strictly dominant strategy이다.

다섯 번째 게임: 마케팅 전략 게임

• 만약 회사2가 낮은 가격을 책정한다면, 회사 1은 낮은 가격을 책정할 것이다.
• 만약 회사2가 높은 가격을 책정한다면, 회사 1은 낮은 가격을 책정할 것이다.
• --> 회사1의 strictly dominant strategy는 낮은 가격이다.
• 만약 회사1이 낮은 가격을 책정한다면, 회사 2는 높은 가격을 책정할 것이다.
• 만약 회사1이 높은 가격을 책정한다면, 회사 2는 낮은 가격을 책정할 것이다.
• --> 회사2는 dominant strategy가 없다.
• 하지만 다행히 회사 2는 높은 가격을 책정해야 하는 것을 안다.
• 아래 두가지 가정이 있기 때문이다.
  • 회사 2는 회사 1이 이득을 최대화하고 싶어 하는 것을 안다.
  • 회사 2는 회사 1이 자신의 이득을 알고 있음을 안다.

웹 그래프를 다음 구조로 알아보자!

1) real system인 Web이 있다.

2) 우리는 이 Web을 directed graph로 나타낼 것이다.

3) Graph theory 중 Strongly Connected Components를 주로 볼 것이다.

4) SCC가 실제로 Web Graph를 잘 나타내는지 실험적으로 확인할 것이다.

5) Structure of Web이 Bowtie라는 것을 알 수 있다!

1. The Web as a Graph

• 정의
  • bridge edge: 없으면 그래프가 끊긴다.
  • local bridge: edge of span>2, bridge는 아니다.
  • edge of span:
• node는 웹사이트, edge는 하이퍼링크라고 이해하면 된다.
• 옛날의 web link는 navigational 한 특징이 있었지만, 요즘은 좋아요, 댓글 등 transactional 하다.
• 한 node에 대해 In(A)와 Out(A)를 정의할 수 있다.
• 모든 웹상의 directed graph는 아래 두 가지 종류 중 하나로 표현할 수 있다.
  • Stringly Connected: 모든 노드에서 모든 노드로 도달할 수 있다,  In(A) = Out(A) = {all}
  • Directed Acyclic Graph: 사이클이 존재하지 않는다, u는 v로 갈 수 있지만 반대는 그렇지 못하다.
• Connected Graph
  • Strongly connected
  • Directly acyclic

2. SCC: Strongly Connected Component

• 정의
  • 모든 노드 쌍은 서로에게 도달할 수 있다.
  • 위 성질을 가진 더 큰 set은 없다.
• Every direct graph is a DAG on its SCCs
  • SCCs partitions the nodes of G
    • 각 노드는 정확히 하나의 SCC에만 포함된다.
  • Every directed graph is a DAG on its SCCs
    • 모든 방향성 그래프는 비순환 그래프이다.

3. Structure of the Web

• Goal
  • Take a large snapshot of the Web and try to understand how its SCCs fit together as a DAG
• Computational issue
  
  • starting node가 무엇인지에 따라 SCC를 찾기 위해 굉장히 많은 node를 순회해야 할 수도 있다.
• Bowtie Structure of the Web
  • In: 100
  • Out: 100
  • SCC: 56
  • Bowtie: 44 - 56 - 44

4. Why is it that axquaitances are most helpful?

• friendship에 대한 두가지 관점
  
  • Structural: 친구 집합은 그래프의 다른 부분에 위치한다.
  • Interpersonal: 관계는 weak이거나 strong이다.
    • structurally embedded edges는 strong 하다.
    • long range edges는 weak 하다.
    • strong 한 관계의 information은 redundant 하다.
• Tradic Closure
  • A-B 친구이고 A-C 친구이면 B-C가 친구일 확률이 높다.
• 만약 strong tradic closure가 만족된다면 local bridges are weak tie
• Edge Overlap
  • 두 노드 이웃 교집합/두 노드 이웃 합집합
  • edge가 local bridge라면 Overlap=0
• Edge Overlap과 Strength의 관계
  • permutated data보다 strength가 클수록 overlap이 컸다.
  • 그래프로 보았을 때도 strength가 큰 edge가 모여있는 것을 볼 수 있다.
• Edge Removal by Strength
  • strength가 낮은 것부터 끊었더니 largest component가 와해되는 속도가 빨랐다.
• Edge Removal by Overlap
  • overlap이 낮은 것부터 끊었더니 largest component가 와해되는 속도가 빨랐다.

1. Structural hole

• Structural hole 
  • 정보격차를 가진 두 개인 사이의 연결
  • 예시)
    • few structural hole : 학과 내에서의 교류
    • many structural hole : 타과와 많이 교류
• Network Constraint
  • 두 노드의 관계가 얼마나 일치하는지에 대한 값
    • 1/(친구수)
    • 예시)
      • network constraint가 낮으면 겹치는 친구가 없다 --> 타과생
      • network constraint가 높으면 겹치는 친구가 많다 --> 우리 과 사
• Redundant
  • 정보가 얼마나 중복되는가 (불필요한가)
  • 예시)
    • 자신의 친구들끼리 모여있다.
    • network constraint가 높다.
    • strongly tied
• 결론
  • 그래서 network constraint가 낮다는 것은 structural hole이 많다는 것을 뜻한다.
  • 그래서 정보일치성이 낮다는 것은 정보격차를 가진 개인 간의 연결이 있다는 것이다.
  • 그래서 낮은 network constraint는 실제로 좋은가?

2. How to detect dense community?

• Network community
  • 자기들끼리의 connection이 많고 바깥쪽으로는 적은 집합, 관계가 많이 겹치는 집합
  • 예시)
    • cluster
    • group
    • community
    • module
    • Micro-markets in sponsored search
    • Zachary's karate club network
• Definition of community
  • 우리는 clusterling을 위해 두가지 질문에 답해야 한다.
    • Q1. how to compute betweenness?
    • Q2. how to select the number of clusters?
  • A1. Girvan-Newman algorithm
    • division method for decomposing a network into hierarchical modules
    • 논리 
      • 그래프의 natural module을 찾기 위해 high betweenness를 가진 edge를 지운다.
      • 왜냐하면 high betweenness인 edge는 traffic of information의 bottleneck이기 때문이다.
      • 따라서 그래프를 파편화할 때 betweenness가 높은 edge를 끊는 것이 설득력 있다.
        • betweenness
          • 해당 edge를 통과해야만 하는 shortest path의 개수
            • 한 노드를 기준으로 잡고 BFS를 통해 그 노드로 가는 shortest path 개수 센다.
            • 수식
    • algorithm
      • 각 edge의 betweenness를 계산한다.
      • 가장 높은 betweenness를 가진 edge를 제거한다. --> 만약 같다면?
      • 남은 edge의 betweenness를 다시 계산한다.
      • 모든 edge가 사라질 때까지 반복한다.
      • 당연히 알고리즘이 진행될수록 module은 작아진다.
    • edge betweenness vs edge strength
      • betweenness는 그래프 구조만 사용한다.
      • strength는 weight를 사용한다.
    • 참고) www.youtube.com/watch?v=LtQoPEKKRYM
  • A2. Modularity Q
    • Girvan-Newman algorithm을 사용하며 언제 멈추어야 적절한 clusterling일지 알 수 있어야 한다.
    • '얼마나 잘 나뉘었는가'를 수치로 나타낸 것이 modularity Q이다. (-1~+1)
    • 기댓값이 0.3 ~ 0.7이면 partitioning이 잘 된 것이다. mod가 max일 때 가장 좋다.
    • Modularity Q
      • 네트워크가 얼마나 잘 partitioning 되었는가?
      • sum of {(# edges within group s) - (expexted # edges within group s})
    • 짚고 넘어간다: 왜 modularity를 decomposing의 기준으로 삼는가? (실제 edge 개수 - expected edge 개수)가 클수록 군집되어있기 때문에 community일 확률이 높다. 이것이 모든 community(라고 간주한 것)의 Q값 합을 구하는 이유
    • 왜 Q를 진작 optimize하지 않는가?
      • 모든 값을 계산해야 Q값이 나오기 때문이다.

3. Network with signed edge

• Signed edge
  • node가 positive인지 negative 관계인지 예측하는 것이 목적이다.
• Structural balance
  • balanced : (+,+,+) (+,-,-)
  • unbalanced : (+,+,-) (-,-,-)
  • 어떤 세 노드도 이 규칙에 위배되지 않는 그래프가 balanced graph
    • 모든 positive edge로 연결된 node는 한 set으로 취급 가능하다.
    • negative relationship은 이 set 간에만 이뤄진다.
  • 예시) international relationship

병행 프로세스와 상호 배제
(1) 데커와 피터슨의 알고리즘
(2) 세마포어와 모니터

1. 경쟁조건 (race condition)

경쟁조건이란 2개 혹은 그 이상의 프로세스들이 전체가 공유하는 메모리에 읽기/쓰기를 할 때, 어떤 프로세스가 먼저 실행되는지에 따라 결과가 달라질 수 있는 상황이다. race condition이 있는 코드를 예측하는 것은 불가능에 가깝기 때문에 그 코드에서는 원하는 결과가 나오지 않을 가능성이 높다. 

A 프로세스와 B 프로세스가 있다고 생각해보자. 두 프로세스 모두 공유 메모리에 저장된 3을 읽어와서 1을 더하고 다시 저장해야 한다. 우리의 예측으로는 두 프로세스가 한 번씩 더하고 다시 저장하니 모든 프로세스가 실행된 후에는 5가 나와야 한다. 실제로는 이렇게 동작하여 5가 아닌 4가 결괏값이 될 수도 있다.

• A 프로세스가 3을 읽어갔다.
• A 프로세스가 3에 1을 더했다.
• A 프로세스가 4를 공유 메모리에 다시 저장하기 전에 B 프로세스가 3이라는 값을 읽어갔다.
• A 프로세스가 4를 공유 메모리에 저장했다.
• B 프로세스가 3에 1을 더했다.
• B 프로세스가 이미 4인 공유 메모리에 다시 4를 저장했다.

내가 원하는 대로 코드를 동작시키려면 최대한 경쟁조건을 피해야 한다. 즉 동시에 공유 메모리, 공유 파일, 기타 공유와 관련된 문제를 피할 수 있도록 조치해야 한다.

2. 상호 배제와 임계 영역 (mutual exclusion and critical section)

상호 배제(mutual exclusion)는 한 프로세스가 공유 자원을 사용하고 있을 때 다른 프로세스들이 사용하지 못하게 배제시키는 제어 기법을 말한다. 만약 위에서 A 프로세스의 모든 동작이 끝난 다음 B 프로세스가 공유 메모리에 접근할 수 있었으면 4를 만드는 오류는 발생하지 않았을 것이다. 운영체제의 전반적인 설계에 있어서 이러한 상호 배제를 구현하는 것은 매우 중요하다.

공유 메모리가 동시에 참조되지 않게 하기 위해 공유 메모리가 참조되는 부분을 임계 영역(critical section)이라 한다. 프로그램의 수행 조건을 잘 조절해서 2개 이상의 프로세스가 임계 영역에 들어가지 않도록 한다면 경쟁 조건을 피할 수 있을 것이다.

다만 임계 영역만으로 경쟁 조건이 만들어지지 않을 때가 있다. 공유 메모리를 사용하는 병렬 프로세스가 올바르고 효율적으로 수행되려면 다음과 같은 추가 조건이 필요하다.

• Mutual exclusion
  
  • 두 개 이상의 프로세스들이 동시에 임계 영역에 있어서는 안 된다.
• Progress
  
  • 임계 구역 바깥에 있는 프로세스가 다른 프로세스의 임계 구역 진입을 막아서는 안 된다.
• Bounded Waiting
  • 어떤 프로세스도 임계 구역으로 들어가는 것이 무한정 연기되어서는 안된다.
• 프로세스들의 상대적인 속도에 대해서 어떤 가정도 해서는 안된다.
  • CPU의 성능과 속도에 영향을 받지 않아야 한다.

3. 2개 프로세스의 상호 배제

2개 프로세스가 있다고 할 때 상호 배제를 구현하는 방법들을 각자의 단점과 발전과정을 중심으로 알아볼 것이다. 

이해가 쉽도록 flag 값을 A, B라고 적었지만 실제로는 0과 1이다.

3.1. Strict Alternation

//A 프로세스의 구조

while(1){

    while(turn != A);
    
    V++; //critical section
    
    turn = B;
    
}

Strict Alternation은 turn 변수를 이용해 A 프로세스와 B 프로세스 중 하나에 순서를 준다. 위 코드는 turn이 A일 때에 임계 영역에 들어가지 않고 while문으로 대기하다가 임계 영역에서 동작을 마치면 turn을 B로 준다. 따라서 상호 배제를 만족한다.

하지만 이 코드는 임계 영역의 실행 순서를 두 프로세스가 교대로 가져야만 한다. 예를 들어 turn이 A가 되어 임계 구역 내부 코드를 실행한 후 turn이 B가 되었는데 B 프로세스가 실행될 필요가 없다면, A 프로세스는 두 번 연속해서 임계 영역에 들어갈 수 없다. 따라서 Bounded waiting과 Progress를 만족하지 못한다.

3.2. Using array

//A 프로세스의 구조

while(1){

    flag[A] = true;

    while(flag[B] == true);

    V++; //critical section
    
    flag[A] = false;

}

1번 방법에서는 turn이라는 공유 변수 1개 만을 사용해서 문제가 생겼다. 이번에는 turn을 flag 배열로 대치한다. 이 알고리즘에서 flag 배열은 처음에 false로 초기화되어 있고 A 프로세스에 진입할 때 flag [A]를 true로 만들어서 진입 의사를 밝힌다. 그 다음에 B 프로세스가 진입할 의사가 있는지 확인하고, B가 임계 영역에서의 일을 끝낼 때까지 while문에서 기다린다. 마지막으로 임계 영역에서의 볼일이 끝났다는 것을 flag[A]를 false로 바꿈으로써 표시한다.

그러나 이 코드는 Progress를 충족하지 못할 때가 있다. 만약 2개의 프로세스가 거의 같은 시간에 진입하려고 하면 turn [A]와 turn [B]가 모두 true가 되고 두 프로세스 모두 while문에서 영원히 돌게 된다. 이렇게 두 프로세스 모두 상대의 flag가 false가 되기를 기다리는 상태를 교착상태라고 한다.

교착상태는 임계 영역 진입을 위해서 일어날 수 없는 사건을 기다리는 상태를 뜻하는 말이다.

3.3. Dekker's Algorithm

//A 프로세스의 구조

while(1){

    flag[A] = true;
    
    while(flag[B]){
    
    	if(turn == B){
        
            flag[A] = false;
            
            while(turn == B);
            
            flag[A] = true;
            
        }
        
    }
    
        V++; //critical section
        
        flag[A] = false;
        
        turn = B;
}

데커의 알고리즘은 2개의 프로세스를 위한 최초의 정확한 상호 배제 해결법으로 알려져 있다. 구성요소는 다음과 같다.

• flag : 초기값은 flag [0] = flag [1] = false이고 임계 영역에 들어가겠다는 표시는 true로 한다.
• turn : 0 또는 1의 값을 갖는다. 0인 경우엔 A의 순서, 1인 경우엔 B의 순서이나 위 코드에는 이해를 위해 A, B로 표시한다.

두 프로세스는 동시에 진행하면서 자신의 flag를 true로 하고 상대방 flag를 검사한 다음 turn값에 따라서 if 이하 절을 수행하거나 수행하지 않을 수 있고, 결국 turn값이 A이면 A 프로세스가 진입하고 turn값이 B이면 B 프로세스가 진입하게 된다. 따라서 한 프로세스는 두 번 연속해서 임계 영역에 진입할 수 있다.

3.4. Peterson's Algorithm

//A 프로세스의 구조

while(1){

    flag[A] = true;
    
    turn = B;
    
    while(flag[B] && turn == B);
    
    V++; //critical section
    
    flag[i] = false;
}

피터슨의 알고리즘은 모든 상호 배제를 위한 추가 조건을 만족하고 데커의 알고리즘보다 단순하다. 구성요소는 데커의 알고리즘과 같다. 동작을 살펴보자.

• A 프로세스를 동작시키고 싶다면 임계 영역에 들어가고 싶다는 표시로 flag [A]를 true로 만든다.
• turn 변수를 B로 설정하고 내부 while문을 수행한다.
• 이때 B 프로세스가 들어갈 의사표시를 하지 않았다면, 즉 flag [B]가 false라면 A 프로세스는 임계 영역에 바로 들어갈 수 있다.
• 그러나 만약 두 프로세스가 동시에 동작하려고 하면 turn 변수가 늦게 수행된 프로세스가 내부 while문에서 기다리며 순서를 양보한다.
• 먼저 임계 영역에 들어갔던 프로세스는 나오면서 자신의 flag를 false로 만들고 다른 프로세스가 임계 영역에 들어가는 것을 허용한다.
• 따라서 두 프로세스가 동시에 수행될 때 내부 while문의 turn값에 따라서 어떤 프로세스가 임계 영역에 들어갈지가 결정된다. turn이 A이면 B 프로세스가 수행되고 turn이 B이면 A 프로세스가 먼저 수행된다.

출처 : Operating System, 최현섭 고형대 임철수 오상엽 저 (이한출판사)

과제로 부스 알고리즘을 사용해 볼 일이 있어서 알아봤는데 굉장히 흥미로웠다. 처음엔 오른쪽 시프트하고 부호 어떻게 채우는지 이해가 안돼서 굉장히 고생함ㅠㅠ

1. Booth's 알고리즘이란?

부호가 있는 이진수의 곱셈을 수행할 수 있도록 해주는 알고리즘으로, 영국의 컴퓨터과학자인 Andrew Donald Booth에 의해 개발되었다. 계산을 하기 전 계산에 사용되는 수에 대해 알아보자.

1.1. Booth's Algorithm을 이용한 계산에 사용되는 수

M x Q를 계산한다고 가정하자. 

• M = Multiplicant
• Q = Multiplier
• A = M의 bit수만큼 0으로 초기화한 후 계산에 사용하는 친구
• q0 = 계산에 사용하는 최하위 비트
• Count = loop를 돌리는 횟수로 계산하려는 2진수의 bit수이다.

1.2. Flowchart

아래 사진의 순서에 따라 loop를 돌며 곱셈의 결과를 도출할 것이다. 아래 예제를 보자.

2. Booth's 알고리즘을 이용한 음수 곱셈

2.1. 계산에 필요한 수 초기화 및 대입

(-12) x (30)을 6bits 곱셈으로 계산해 볼 것이다. 위 규칙에 따라 아래와 같이 초기화된다.

• M = -12의 2진수 표현 = 110100
• Q = 30의 2진수 표현 = 011110
• A = M의 bit수인 6자리를 0으로 초기화 = 000000
• q0 = 0으로 초기화 = 0
• Count = 계산하려는 2진수의 bit수 = 6

2.2. 계산과정

우리는 2.1.에서 정의한 'AQq0'를 Count만큼의 loop를 돌며 계산해 나갈 것이다. 

총 곱셈 과정에서 수행할 연산은 2's complement, Arithmatic right shift, 이진수 덧셈 세가지밖에 없으니 겁먹지 않아도 된다.

<모든 초기화가 끝난 상태>

이제 우리는 flowchart에서 봤던 것처럼 q1q0값이 무엇인지에 따라 아래 표를 채워나갈 것이다. 

현재 q1q0은 00이므로 flowchart의 아래로 내려가 AQq0에 대해 Arithmatic right shift를 수행하고 Count를 감소시킬 것이다.

<Count == 5 를 계산하는 중>

다음 q1q0는 이제 10으로 바뀌었다. 이번에는 flowchart의 왼쪽 화살표를 따라가 A = A - M 연산을 수행해야 한다.

A는 000 000이고 -M은 12, 즉 이진수로 001 100이다. 둘을 더하면 001 100일 것이다.

A = A - M 연산과 A = A + M 연산은 둘 다 덧셈 연산이다.
-M을 더하는지 M을 더하는지만 다르다고 생각하면 된다.

덧셈 계산을 수행한 다음 Arithmatic right shift를 수행하고 Count를 감소시켜야 한다. 

그 후 과정은 위에서 예시를 보였던 연산이므로 넘어가겠다.

Arithmatic right shift 연산을 할 때 왼쪽 공간에 채우는 숫자는 
A가 양수일 경우, 즉 첫비트가 0일 경우 0으로 채운다.
A가 음수일 경우, 즉 첫비트가 1일 경우 1으로 채운다.

<Count == 1 를 계산하는 중>

이번에는 q1q0가 01이 나왔으므로 A = A + M을 수행해야 한다.

M은 (-12)로, 이진수로는 110 100이다. 현재 A인 000 000과 더해주면 110 100이 나온다.

따라서 다음 A는 110 100이다. 계산을 마무리해 보자.

<완성된 표>

loop의 종료 조건인 Count == 0 이 만족되어 연산이 모두 끝났다.

AQ가 연산의 결과로, 111 010 011 000이 나왔다.

이 수의 2의 보수는 십진수로 확인해보면 000 101 101 000 = 256 + 64 + 32 + 8 = 360으로, 

(-12) x (30) = -360이 제대로 계산되었음을 알 수 있다.

통신 공부를 시작하려니 뭐가 뭔지 모르겠음 네트워크가 뭔가 패킷이랑 프로토콜은 뭔가 이건 왜하는거고 라우터와 스위치의 차이는 뭐지 하는 나를 위해 쓰는 글 앞으로 풍부하게 채워나가고 수정할 예정

1. 네트워크 (NetWork)

네트워크는 Net와 Work의 합성어로 "컴퓨터간의 통신"을 의미한다. 즉 네트워크로 연결된 컴퓨터는 언제 어디서든 원하는 정보를 공유하여 활용할 수 있다.

네트워크는 다음과 같은 장점이 있다.

1.1. 데이터 공유

A학과 사무실과 B학과 사무실에서 U학교의 학생 정보를 가져와서 신입생에 대한 정보를 명단에 추가한다고 생각해보자. A학과와 B학과는 각각 기존 학생 명단을 받아와 A과 신입생, B과 신입생의 명단을 추가할 것이다. 이때 A학과 사무실은 U학교 학생 명단 + A학과 신입생 명단을 가지고 있을 것이고 B학과 사무실은 U학교 학생 명단 + A학과 신입생 명단을 가지고 있을 것이다. 이 두 명단은 모든 신입생들의 정보를 가지고 있지는 않으므로 온전하다고 할 수 없다. 

이 문제는 학생 명단을 중앙 컴퓨터, 즉 서버에 저장함으로써 해결할 수 있다. 모든 사용자가 공유하며 수정할 수 있는 학생 명단이 있다면 편하지 않을까? 하나의 데이터 파일에 해당하는 마스터 사본을 파일서버(file server)에 저장하고 필요할 때마다 A학과 사무실과 B학과 사무실이 마스터 사본을 수정할 수 있도록 만드는 것이 각자의 컴퓨터에 저장하는 방법보다 더 효율적일 것이다.

그러나 U학교 구성원이 아닌 외부 사람이 학생 명단 데이터에 접근하는 것을 막아야 할 필요가 있을 것이다. 이때는 아래 방법을 사용한다.

• 읽기 전용읽기 전용 : 공유 장치에 저장된 데이터를 읽기만 할 수 있다. 이 권한이 있는 사용자는 데이터를 읽을 수만 있고 수정할 수 없기 때문에 데이터가 변경될 가능성이 없다.
• 읽기/쓰기 : 공유 장치에 저장된 데이터를 읽고 수정할 수 있다. 이 권한이 있는 사용자가 데이터를 수정하면 네트워크에 연결된 모든 사용자는 수정된 데이터를 공유한다.

1.2. 주변장치 공유

A학과 사무실에는 컴퓨터가 3대 있다. 과와 관련한 업무를 효율적으로 처리하려면 세 컴퓨터가 모두 프린트 기능을 사용해야 할 텐데 컴퓨터마다 프린터기를 한 대씩 총 세대 쓰는 것은 비용이 비쌀 것이다. 이럴 때 하나의 프린터기를 각 컴퓨터와 네트워크로 연결해서 공유한다면 비용을 절약하면서도 프린터기를 중앙 집중화할 수 있어 관리도 수월해질 것이다. 

1.3. 능률적인 통신

A, B, C, D, E학과 사무실은 서로 소통을 해야 할 일이 종종 생긴다. 메시지를 전달하기 위해서 각 학과의 사무실마다 네트워크를 연결한다면 간단히 계산해봐도 5! = 120개의 링크가 필요할 것이다. 하지만 우리가 널리 사용하는 데이터 통신 중 하나인 메일을 예로 들어보자. A학과가 D학과로 메시지를 담은 메일을 보내면 이 메일은 메일 서버로 이동하고, 서버는 새로운 메일이 도착했음을 D학과에게 알려줄 것이다. 그러면 D학과는 이메일 프로그램을 이용해 서버에서 메시지를 받아서 확인할 수 있다. 이 경우에는 5개의 사무실이 소통하기 위한 링크가 5개밖에 없을 것이다. 네트워크는 호스트 간의 데이터 송수신을 능률적으로 수행할 수 있도록 해준다.

1.4. 손쉬운 백업

데이터는 귀중한 자산이므로 데이터를 백업하는 일은 매우 중요하다. 네트워크를 이용하면 사용자가 접근 가능한 공유 저장장치 중 하나에 모든 데이터를 손쉽게 백업할 수 있다. 

2. 네트워크의 구성

네트워크에는 세가지 구성요소가 있다. 

2.1. 호스트(host)

호스트는 컴퓨터 네트워크에 연결된 컴퓨터나 기타 장치들을 의미한다. 컴퓨터, 휴대폰, 프린터기에서부터 서버까지 모두 호스트라고 할 수 있다. 우리가 휴대폰으로 카카오톡, 인스타그램 등을 하며 애플리케이션을 사용하는 중 다양한 데이터를 송수신하는데 이는 모두 호스트로부터 출발한다. 

2.2. 네트워크 접속 장치

네트워크 접속 장치는 애플리케이션의 데이터를 정상적으로 전송하기 위한 장치이다. 접속 장치는 다양한 종류가 있지만 기본적으로 스위치와 라우터가 존재한다. 스위치는 한 네트워크 내부에서 데이터를 전송하도록 돕는 장치이고 라우터는 서로 다른 네트워크를 구분 짓고 연결하는 장치이다. 

2.3. 네트워크 전송 매체

호스트와 네트워크 접속 장치는 네트워크 전송 매체에 의해 서로 연결된다. 전송 매체는 크게 유선 전송 매체와 무선 전송 매체로 나뉘는데, 유선 전송 매체는 일반적으로 케이블을 의미한다. 무선 전송 매체는 전파를 말하며, 네트워크 통신에 이용되는 전파는 규격에 따라 전파의 파장이나 주파수가 지정되어 있다. 네트워크에서 데이터를 송신할 때는 전송 매체에 따라 디지털 데이터가 물리적 신호로 변환된다. 

3. 네트워크의 종류

우리가 가까운 거리는 걸어가거나 지하철을 타고 먼 거리는 시외버스나 기차를 타듯이 테이터가 이동하고자 하는 거리에 따라서 네트워크의 종류를 구분할 수 있다. 가장 작은 규모의 네트워크인 PAN(Personal Area Network)부터 광대역 네트워크인 WAN(Wide Area Network)까지 그 쓰임과 네트워크 연결 방법이 다양하다. 지금은 기초를 위해 간단한 것들만 살펴본다.

3.1. LAN (Local Area Network)

LAN은 범위가 지역적인 네트워크로 범위가 건물 안이나 특정 지역인 네트워크이다. 따라서 한 건물 또는 인접한 건물군 내에 있는 네트워크는 하나의 LAN으로 간주된다. 집에서 인터넷을 이용할 때나 PC방, 사무실 등 작은 규모로 인터넷을 연결할 때 LAN을 사용한다. 만약 A학과 사무실과 B학과 사무실이 다른 LAN을 사용하는데 두 연구실 간 데이터 통신이 필요할 때는 두 LAN 간 링크를 만들어야 한다. 각 LAN은 특정한 프로토콜(데이터를 송수신하는 일련의 규칙)로 운용되기 때문에 링크를 만들기 위해서는 서로 다른 네트워크 유형의 데이터 공유 방법을 알아야 한다.

• 신호가 약해지거나 오류가 발생할 확률이 낮다.
• 데이터 전송 비용이 싸다.
• 연결 거리가 짧다.

3.2. WAN (Wide Area Network)

WAN은 2개 이상의 LAN을 넓은 지역에 걸쳐 연결한 것을 말한다. 서로 다른 LAN에 속하는 U학교의 C캠퍼스와 D캠퍼스는 데이터나 프로그램을 공유하기 위해 라우터를 연결하여 WAN을 구성하기도 한다. 추가적으로 LAN에 포함되지 않는 호스트도 WAN을 이용하여 연결될 수 있다. WAN은 ISP(Internet Service Provider)가 제공하는 서비스를 이용해 구축된 네트워크이다. ISP는 인터넷 상용 서비스를 하고 있는 SK, KT 등과 같은 통신 사업자를 의미한다. 

• 멀리 떨어진 LAN을 연결하므로 신호가 약해지거나 오류가 발생할 확률이 높다.
• 데이터 전송 설비를 임대하는 비용이 많이 든다.
• 거리가 멀어지는 만큼 속도가 느려진다.

3.3. 인트라넷 (Intranet)

인터넷에서 사용하는 회선과 여러 기반 기술을 이용하여 구축하는 사설 네트워크이다. 각 지방에 분산된 호스트를 전용 회선으로만 연결하는 것은 어려운 작업이지만 인트라넷을 활용하면 손쉽게 구현할 수 있다. 각 호스트에서 가장 가까운 ISP까지만 연결하면 되기 때문이다. 아무리 호스트가 멀리 떨어져 있어도 호스트를 ISP까지만 연결하면 저렴한 비용으로 사설 네트워크를 구축할 수 있다. 인트라넷을 이용하면 모든 호스트에서 문서관리, 메신저, 게시판, 결제내역 등을 공개되지 않은 웹페이지에서 처리할 수 있다. 예시로는 각 대학교의 포털을 들 수 있다. 

4. 패킷

우리가 매일 사용하는 인터넷은 전 세계의 작은 네트워크부터 큰 네트워크까지 연결된 거대한 연결망이다. 전 세계가 네트워크로 연결되어 있으므로 우리는 해외 웹사이트에 접속할 수 있다. 다만 이를 위해서는 통신에 관한 규칙이 필요한데 이 규칙에는 패킷(packet)이 사용된다. 패킷 구조에 대해서는 앞으로 다른 글에서도 자세히 알아볼 것이다.

패킷은 헤더(header), 페이로드(payload), 제어 요소 등을 포함하는 데이터 세그먼트이다. 헤더는 데이터의 형태와 데이터의 송수신지, 일련번호 등으로 구성되고 페이로드는 실제 전송 데이터를 포함하는 부분이다. 

또한 패킷은 컴퓨터 간에 데이터를 주고받을 때 네트워크를 통해 전송되는 데이터의 전송 단위이다. 만약 용량이 큰 고양이 이미지를 네트워크를 통해 보내고 싶다면 고양이 이미지 데이터를 작게 나누어서 보내는 것이 원칙이다. 만약 용량이 큰 데이터를 그대로 보낸다면 데이터가 네트워크 대역폭을 너무 많이 점유하여 다른 패킷의 흐름을 방해할 위험이 있기 때문이다. 

대역폭(bandwidth) : 네트워크에서 이용 가능한 신호의 최고 주파수와 최저 주파수의 차이로, 데이터를 전송할 수 있는 최대 전송 속도이며 기본 단위는 bps(bit per second)이다. 

송신자가 보낸 패킷은 보낸 순서대로 수신자에게 도착하지 않는다. 따라서 수신자가 예쁜 고양이 이미지를 보기 위해서는 패킷을 원래 순서대로 조립할 필요성이 있다. 그래서 송신 측에서 각 패킷에 순서대로 번호를 붙여 전송하고 수신 측에서는 번호에 맞춰 재조립함으로써 각 패킷을 원래의 위치로 되돌린다. 이렇게 번호 순서로 사진 전체의 패킷을 정렬하면 송신 측에서 보낸 예쁘고 귀여운 고화질의 고양이 사진을 수신 측이 드디어 볼 수 있는 것이다.

출처 : 한빛아카데미 4차 산업혁명과 함께하는 네트워크 개론 (진혜진 지음)