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

생활코딩의 강좌를 들으며 하는 공부 기록

생활코딩 감사합니다.

https://opentutorials.org/course/1

WebApp 학습계획

1. HTML
2. CSS
3. JavaScript와 PHP 이론
4. DataBase

html 코드가 해석될 때 script tag가 나오면 javascript 코드를 해석한다.

php 코드를 만나면 웹서버와 데이터베이스가 연결되어 html 파일을 완성한다.

JavaScript와 PHP

• 둘 다 동적인 언어이다.
• JavaScript는 스크립트가 들어있는 웹 문서를 읽는 브라우저에서 실행된다.
• PHP는 서버사이드 언어이므로 서버에서 실행되고 브라우저에는 그 결과만을 보여준다. 
• 따라서 브라우저에서는 PHP의 소스 보기를 해도 PHP 소스는 볼 수 없고, 마치 HTML문서처럼 보인다.

PHP는 <?PHP?> 태그로 감싸지고 JS는 <script></script> 태그로 감싸진다.

PHP echo는 PHP 인터프리터에 의해 해석된다. 

<!DOCTYPE html>
<html>
<head>
     <meta charset="utf-8">
</head>
<body>
  <h1>php</h1>
  <?php
    echo 10+10;
  ?>
  <h1>JavaScript</h1>
  <script>
    document.write(10+10);
  </script>
</body>
</html>

문자와 숫자를 표기하는 방법

• 숫자를 표기할 때에는 따옴표가 없어야 한다.
• 문자를 표기할 때에는 따옴표가 있어야 한다.
• "10"+"10"
  • PHP : 20 -> "10"."10"을 쓰면 1010이 나온다.
  • JS : 1010

변수를 작성하는 방법

• PHP : $name = "suintodev";
• JS : name = "suintodev";
• 변할 수 있는 부분과 없는 부분을 구분해 변수를 사용한다.

JS로 로그인 기능 구현

prompt를 이용해 비밀번호를 사용한다.

<!DOCTYPE html>
<html>
<head>
     <meta charset="utf-8">
</head>
<body>
  <script>
    password = prompt("비밀번호");
    if(password == 1111) {
      document.write("안녕하세요. 주인님");
    } else {
      document.write("뉘신지?");
    }
  </script>
</body>
</html>

PHP로 로그인 기능 구현

<!DOCTYPE html>
<html>
<head>
     <meta charset="utf-8">
</head>
<body>
  <?php
    $password = $_GET["password"];
    if($password == "1111"){
        echo "주인님 환영합니다";
    } else {
        echo "뉘신지?";
    }
   ?>
</body>
</html>

배열과 반복문 예제

• PHP : $list = array("1","2","3");
• JS : list = new Array("1","2","3");

<!DOCTYPE html>
<html>
<head>
     <meta charset="utf-8">
</head>
<body>
  <h1>JavaScript</h1>
  <ul>
  <script>
    list = new Array("최진혁", "최유빈", "한이람", "한이은", "이고잉");
    i = 0;
    while(i < list.length){
      document.write("<li>"+list[i]+"</li>");
      i = i + 1;
    }
  </script>
  </ul>
 
  <h1>php</h1>
  <ul>
  <?php
    $list = array("최진혁", "최유빈", "한이람", "한이은");
    $i = 0;
    while($i < count($list)){
      echo "<li>".$list[$i]."</li>";
      $i = $i + 1;
    }
  ?>
  </ul>
</body>
</html>

함수 예제

•  PHP : function (){contents)
• JS : function a(){contents}

<!DOCTYPE html>
<html>
<head>
     <meta charset="utf-8">
</head>
<body>
  <h1>JavaScript</h1>
  <script>
    function a(input){
      return input+1;
    }
    document.write(a(6));
  </script>
 
  <h1>php</h1>
  <?php
    function a($input){
      return $input+1;
    }
    echo a(6);
  ?>
</body>
</html>

생활코딩의 강좌를 들으며 하는 공부 기록

생활코딩 감사합니다.

https://opentutorials.org/course/1

WebApp 학습계획

1. HTML
2. CSS
3. JavaScript와 PHP 이론
4. DataBase

기본 내용

• CSS는 Cascading Style Sheets의 줄임말이다.
• 정보를 담는 것이 주 목적인 HTML과 달리 CSS는 정보를 꾸미는 역할을 한다.

태그 선택자를 사용해 해당 태그의 색깔, 폰트크기, 밑줄 여부를 바꾸는 법

<!DOCTYPE html>
<html>
<head>
     <meta charset="utf-8">
   <style>
     h1,h2 {
       color:red;
       font-size:10px
    }
    h2{
      text-decoration:underline;
    }
    header h1{
      border:1px solid red;
    }
   </style>
</head>
<body>
<header>
  <h1>CSS</h1>
</header>
<h2>JavaScript</h2>
<h3>HTML</h3>
<h1>PHP</h1>
</body>
</html>

태그의 id를 이용해 해당 id에 여러 모양의 박스를 만드는 법

<!DOCTYPE html>
<html>
<head>
     <meta charset="utf-8">
   <style>
     #selected {
       border:red 1px solid;
       padding:30px;
       margin:50px;
     }
     #extra {
       border:blue 1px solid;
     }
   </style>
</head>
<body>
  <ul>
    <li>html</li>
    <li id="selected">css</li>
    <li id="extra">javascript</li>
  </ul>
</body>
</html>

float : right, float : left 등으로 설정해주면 이미지의 위치를 정렬해 layout을 정할 수 있다.

border, width, height, nav ol, padding으로 웹페이지를 꾸미는 법

<!DOCTYPE html>
<html>
<head>
     <meta charset="utf-8">
    <style>
    header{
        border-bottom :1px solid gray;
        padding:20px
    }
    nav{
        border-right:1px solid gray;
        width:200px;
        height:600px;
        float:left;
    }
    nav ol{
        list-style:none;
    }
    article{
        float:left;
        padding:20px;
    }
    </style>

</head>
<body>
    <header>
        <h1><a href="http://localhost/">JavaScript</a></h1>
    </header>
    <nav>
        <ol>
        <li><a href="http://localhost/page_html.html">JavaScript란?</a></li>
        <li><a href="http://localhost/page_vc.html">변수와 상수</a></li>
        <li><a href="http://localhost/page_op.html">연산자</a></li>
        </ol>
    </nav>
    <article>
    heyheyheyheyheyheyhey~~~~~
    </article>
</body>
</html>

HTML과 CSS를 분리하는 법

1. style.css 파일을 만든다.
2. 원본 html 파일에서 style tag 내부 코드를 style.css에 붙인다.
3. 원본 html 파일의 style 내부에 <link rel="stylesheet" type="text/css" herf="http://localhost/style.css">를 작성한다.

CSS 코드를 별도의 파일로 분리했을 때의 장점

• 이 방법을 사용하면 같은 디자인의 웹페이지 레이아웃을 한번에 바꿀 수 있다.
• css가 각각 있을 때보다 빠르다.

생활코딩의 강좌를 들으며 하는 공부 기록

https://opentutorials.org/course/1

WebApp 학습계획

1. HTML
2. CSS
3. JavaScript와 PHP 이론
4. DataBase

기본 내용

• Bitnami WAMP stack을 사용해 MYSQL Database, Apach Web Server를 제어하고 에러 로그를 확인할 수 있다.
• 웹브라우저가 웹서버에게 페이지를 요청하면 HTML 파일을 보내주고, 이 내용이 웹브라우저에 보이는 방식으로 구동된다.
• HTML은 HyperText Markup Language의 약자이고 hypertext는 문서와 문서가 linking 된 모양이라 할 수 있다. 웹은 이 링크로 구성된다. 

html의 골격

<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8" />
</head>
<body>
	안녕하세요. <strong>suintodev</strong>입니다.
</body>
</html>

링크를 거는 법

<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8" />
</head>
<body>
	안녕하세요. <a href="https://suintodev.tistory.com/" target="_blank">suintodev</a>입니다.
</body>
</html>

ordered list와 unordered list로 요소를 작성하는 법

<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8" />
    <title>내가 먹고 싶은 것</title>
</head>
<body>
	<ul>
	<li>연어덮밥</li>
	<li>연어롤</li>
	<li>연어초밥</li>
	</ul>
	<ol>
	<li>이베리코</li>
	<li>삼계탕</li>
	<li>먹고싶다</li>
	</ol>
	
</body>
</html>

의미론적인 웹 구조로 ordered list작성

<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8" />
    <title>내가 먹고 싶은 것</title>
</head>
<body>
	<header>
		<h1>중학교 3-1</h1>
	</header>
	<nav>
		<ol>
			<li>인수분해</li>
			<li>이차방정식</li>
			<li>이차함수</li>
		</ol>
	</nav>
	<article>
		<h2>인수분해란?</h2>
		<ol>
			<li>식의 공통부분, 즉 인수를 뽑아내는 것</li>
			<li>삼계탕</li>
			<li>먹고싶다</li>
		</ol>
	</article>
	
</body>
</html>

하나의 완결된 웹페이지를 만드는 방법

1. 대문 페이지인 index.html를 <nav></nav>를 이용해 작성
2. 아직은 만들지 않았지만 연결되는 페이지를 http://localhost/new_page.html 링크를 포함해 작성해준다.
3. 각 html 페이지에 <article></article>을 이용해 내용을 작성한다.
4. <h1></h1>에 <a href=""></a>를 이용해 index.html로 연결해준다.

병행 프로세스와 상호 배제
(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, 최현섭 고형대 임철수 오상엽 저 (이한출판사)