07. CPU: Synchronization

공유하고 있는 하나의 버퍼를 보면, 누구는 생산을 해서 넣고 다른 누구는 소비를 해서 거기에서 꺼낸다. 버퍼 안의 데이터 수를 카운터라는 변수로 추적하여 생산을 하고 꺼낸다. (consumer-producer problem)

프로세스와 consumer이 동시에 진행된다고 봐도 되고 하나의 프로세스에서 consumer, process가 OS에 의해 계속 context switching되며 번갈아가며 스케줄링한다고 봐도 됨.

 

 

Race Condition

두 프로세스가 공유자원을 놓고 경쟁하는 상황을 말한다. (다른 프로세스와 같이 쓰는 변수를 사용하는 등)

counter 변수는 메모리에 적재되어있다. CPU가 이 연산을 하기 위해 레지스터로 counter 값을 가져온다. 이후 레지스터에 있는 counter 값을 하나씩 증가시키고 이 값을 레지스터에 업데이트 해준다. 최종적으로 메모리 상에 있는 counter 값이 업데이트 된다.

 

counter++ //사람이 보는 코드

register1 = counter     // CPU가 처리하는 instruction

register1 =register1 + 1   

counter = register1

 

counter-- //사람이 보는 코드

register2 = counter     // CPU가 처리하는 instruction

register2 = register2 - 1

counter = register2

 

-> 처리 순서에 따라 결과가 달라짐

S0: register1 = counter (producer) //생산자가 메모리에있는 counter을 가져와서 register1에 넣음

S1: register1 =register1 + 1  (producer)

S2: register2 = counter (consumer)

S3: register2 = register2 - 1 (consumer)

S4: counter = register1 (producer)

S5: counter = register2 (consumer)

S4가 실행되기 전(counter++을 메모리에 업데이트 하기 전)에 S2가 실행되어 register2에는 업데이트 전의 counter값이 들어가는 문제가 생긴다.

 

 

Critical Section

동기화 문제 발생 가능성이 있는 부분을 파악하고 그곳을 Critical Section으로 정의한다.

ctirical section은 프로세스가 공유하고 있는 자원을 변경할 수 있는 부분이다. 이것이 다른 프로세스와 동시에 수행되면 race condition이 발생한다.

따라서, entry section과 exit section을 이용하여 다른 프로세스가 critical section에 동시에 들어오지 않도록 보호해야한다. 위의 예시에서는 counter++,--를 하는 과정에서 다른 프로세스가 들어오지 않게 해야한다.

 

do{

   [entry section]

              critical section

   [exit section]

              remainder section (entry, exit, critical을 제외하고 남은 것)

  } while(true);

 

 

ex)  do {

            whlie(turn==j); 

                   critical section

            turn = j;

                   remainder section

      } while (true);

 -> turn == j이면 Pj를 수행함. Pi는 무한 루프에 빠져서 돌고 있고 Pj가 끝나면 turn을 i로 바꿔주고 Pi는 critical section 을 수행한다. Pi 작업이 끝나면 다시 turn을 j로 바꿔준다.

 

이런 코드를 작성할 때 지켜줘야하는 조건:

코드를 잘못짜면 하나가 Critical Section을 오래 대기해야하는 상황이 발생한다. 특정 프로세스가 Critical Section에 들어가지 못하는 상황도 발생하기 때문에 주의해야한다.

1) Mutual Exclusion [상호배제]

    Critical Section에 누가 들어와있으면 다른 프로세스는 들어오면 안 된다.

2) Progress [진행 해야함]

    만약 어떠한 프로세스들도 Critical Section에 진입해있지 않고 한 프로세스가 Critical Section에 진입하려고 시도하면  그 프로세스는 무조건 Critical Section에 들어갈 수 있어야함. 즉, Critical Section가 비어있을때 어떤 이유로 인해 들어가고자 하는 프로세스가 못들어가면 안 된다.

3) Bounded Waiting (↔ unbounded. 대기 시간이 얼마나 될지 모른다)

   일정 시간내에 작업이 완료되어야한다.

 

잘못된 ex)

turn =0 으로 초기화 되어있고 turn =0이면 P0이 Critical Section에 진입할 수 있다고 가정.

P0  while (turn !=0 );

          Critical Section

     turn = 1;

          remainder section

 

P1  while (turn !=1);

          Critical Section

     turn = 0;

          remainder section

-> mutual exclusion, bounded waiting은 만족했으나 progress 는 만족하지 못함. turn = 0으로 초기화되었으므로 P0은 바로 Critical Section에 접근할 수 있다. P1의 경우는 P0이 turn=1을 해줄때까지 Critical Section에 아무도 없는데도 계속 기다려야한다.

 

flag[0], flag[1]은 false로 초기화. flag[0]=true일때 P0이 Critical Section에 접근할 수 있고 flag[1]=true일때 P1이 Critical Section에 접근할 수 있다고 가정함.

P0  flag[0]=true;

     while(flag[1]);

         Critical Section

     flag[0]=false;

         remainder section

P1 flag[1]=true;

    while(flag[0]);

        Critical Section

    flag[1]=false;

        remainder section
-> mutual exclusion은 만족했으나 progess, bounded waiting은 만족하지 못함.

flag[0]이 수행을 마치고 flag[1]이 remainder section을 돌고 있는 상황이면 flag[1]이 false 상태이므로 flag[0]은 다시 while문에 진입할 수 있음. 대기하지 않음. BUT 동시에 while문에 들어가려고 하는 상황이면 둘 다 못들어감. 

 

위의 예시와 같은 조건.

Peterson's Solution

P0  flag[0]=true;

     turn = 1; //일단 P1이 먼저 동작하게 순서를 넘겨줌

     while(flag[1] && (turn ==1) );

       //flag[1]이 true이면 CS에 접근하고 싶다는 의사가 있는 것이고 turn==1이면 순서를 P1이 잡고있다는 뜻.

         Critical Section

     flag[0]=false;

         remainder section

P1 flag[1]=true;

    turn = 0; //혹시 P0이 대기중이면 먼저 하라고 순서를 넘겨줌

        Critical Section

    while(flag[0] && (turn ==0) );

    flag[1]=false;

        remainder section

->세가지 조건을 모두 만족한다.

P0 프로세스를 먼저 살펴봤을때 turn =1 이므로 P1로 넘어간다. P1 역시 turn =0으로 P0에게 순서를 양보한다. 다시 P0으로 넘어왔을때 flag은 true지만 turn==0이므로 P0이 먼저 동작한다. Critical Section에서 작업이 끝나면 flag[0]=false로 바꿔준다. P1은 turn ==0이지만 flag[0]이 false이므로 Critical Section에 접근하고 작업이 끝나면 flag[1]을 false로 바꿔준다. flag[0]은 다시 Critical Section에 들어가고 작업이 끝나면 flag[0]을 false로 바꿔준다. P2는 flag[0]이 false이므로 Critical Section에 접근할 수 있다. 이를 계속하여 반복한다.

두번째 예시와 같이 동시에 실행시키는 경우에도 dead-lock 문제가 발생하지 않는다. 두번째 라인까지 동시에 실행해도 turn=0 or 1이므로 둘 중 하나는 실행시킬 수 있다.

하지만 Peterson's solution은 여러개의 프로세스로 확장하기 어렵다는 한계가 있다.

 

Critical-Section Handling in OS

Critical Section 문제가 OS에서는 어떤 의미를 가지는가?

OS 스케줄러는 preemptive하거나 non-preemtive하다. preemptive는 기본적으로 우리가 쓰고 있는 것이다.

• preemptive: 프로세스가 동작하는 중간에 한 지점에서 프로세스를 끊을 수 있다. 즉, entry section, Critical Section 가 동작하는 중간에도 끊을 수 있다는 소리로 동기화 문제가 심화되는 원인이다.
• Non-preemptive: 프로세스 동작 중간에 중단 시킬 수 없다. 따라서 자발적인 양보도 없어야하며 I/O 작업도 하지 말아야한다.
• 커널 모드는 그 자체로 하나의 큰 Critical Section라고 볼 수 있음. (거대한 공유 자원)
  여러 프로세스들이 동시에 시스템 콜을 실행해서 커널 코드에 진입하면? 공유 자원들이 꼬인다. 커널 코드에서 동기화 문제가 발생한다. 옛날에는 시스템 콜 자체가 entry section 역할을 했다. 시스템 콜을 빠져나올때 exit section 역할을 했다. 즉, 커널을 Critical Section처럼 관리한 것이다. 하지만 시스템 콜에 한 프로세스만 접근 가능하게 하면 성능이 저하되는 문제가 발생한다. 이를 해결하기 위해 네트워트와 파일 시스템의 Critical Section는 따로 관리하기 시작하고 시스템 효율을 높이기 위해 점점 Critical Section를 세분화했다. 

 

Synchronization Hardware

소프트웨어적으로만 접근하면 한계가 있어서 Critical Section를 보호할 수 있는 근복적인 방법을 찾지 못한다.

위의 race condition 예시에서 나타난 문제는 CPU가 세 줄의 코드를 묶어서 한번에 작동시키면 해결된다.

하드웨어가 기본적으로 Atomic(쪼개지지 않는)한 instruction을 제공하는 것이다. 우리는 이것을 기반으로 Critical Section Solution 을 짠다. 하드웨어 솔루션을 쓴다고 모든 문제가 해결되는 것은 아니다. 기반이 될뿐! mutual exclusion은 하드웨어적으로 해결이 가능하지만 progress, bounded waiting은 소프트웨어적으로 해결해야한다.

 

do{

     [acquire lock]

               critical section

     [release lock]

               remainder section

} while (TRUE);

 

• test_and_set Instruction (automic함)
  boolean test_and_set (boolean *target)
    {
          boolean rv = *target;
          *target = TRUE;
           return rv:
           //기존 target 값은 return해주고 실제 target 값은 true로 바꿔줌
  }
  
  ex) lock은 false로 초기화됐음
  do {
           whlie(test_and_set (&lock) ); //lock을 true로 바꿔주고 이전 값인 false를 return함
             //다음에 들어오는 프로세스는 lock이 true 이므로 while에서 계속 대기함
                  Critical Section
           lock = false; //기다리고 있던 한 프로세스만 빠져나와 Critical Section를 수행할 수 있게됨.
                  remainder section
    }  whlie (true);
  
  
• compare_and_swap Instruction
  int compare_and_swap (int *value, int expected, int new_value){
       int temp=*value;
       if( *value == expected)
           *value = new_value;
    return temp;
   }
  ex) lock =0으로 초기화한 상태
      do {
           whlie ( compare_and_swap (&lock, 0, 1) !=0); //기존 lock 값이 0과 같은지 확인. 같으면 lock을 1로 바꿈.
            //바뀌는 동시에 기존 lock 값이 리턴됨. 0 == 0 이므로 Critical Section에 접근 가능하다.
            // 다음에 들어오는 프로세스들은 lock 값이 1이 되므로 계속 while loop을 돈다.
            Critical Section
            lock=0; //대기하던 프로세스 중 하나만 Critical Section에 접근할 수 있게 됨
            remainder section
  }  while (true);
  
  

 

 

Synchronization mechanisms

• Mutex lock (spinlock)
  가장 간단한 형태로 Critical Section를 관리할 수 있는 동기화 메커니즘.
  acquire() (lock하는 함수)와 release() (lock 푸는 함수) 두개의 instruction을 사용한다.
  
  acquire() {
       while (!available);
          /*busy wait*/
          //뮤텍스락의 특징. while문을 계속 돌면서 available을 계속 보고있기 때문에 바쁘게 대기한다.
            =CPU를 계속 쓰고있다는 뜻. CPU가 낭비되지만 빠르게 동작한다. 금방 available 상태가 변할 경우에 유리.             (Critical Section가 길지 않거나 Critical Section에 오래 머물지 않거나 Critical Section하려고 대기하는 애들 이 적은 경우)
       available = false;
    }
  
  release() {
       available = true;
  }
  -> non busy wait: while 문으로  available을 보는게 아니라 if문으로 한번만 검사한다. 들어갈 수 없는 상태면 누군가에게 들어갈 수 있을때 알려달라고 요청하고 쉬러간다. 다른 프로세스들도 CPU를 쓸 수 있게 해주는 것이다.
• Semaphore
  더 복잡한 문제의 동기화를 다루는 매커니즘.
  Critical Section에 들어갈 수 있는 프로세스 수를 여러개로 관리할 수 있다.
  wait()와 signal() (=P() 와 V()) 두가지 operation을 사용한다.
  
  wait(S){
     while( s <= 0);   //s는 Critical Section에 접근할 수 있는 프로세스 수를 나타냄
          //busy wait
     s--;  
    }
  
  signal(S) {
     s++;
   }
  
  ex) S=3;
       wait(S);
        Critical Section
       signal(S);
        remainder section
  -> 첫번째 프로세스가 실행되면 S=2가 되고 CS에 들어감. 두번째, 세번째 프로세스도 마찬가지. 이때 네번째 프로세스는 S=0인 상태이므로 while문에서 대기하게됨. 이 와중에 첫번째 프로세스는 signal에 들어가 S=1로 만들고 끝냄. 기다리고 있던 네번째 프로세스는 S=1이 되었으므로 while문으로 들어가 s를 다시 0으로 만듦. 
  이렇게 프로세스의 수를 세며 Critical Section에 여러 프로세스를 넣는 것을 counting semaphore라고 함.
  
  Binary Semaphore (한번에 한 프로세스만 들어갈 수 있음. S=2 이상인 경우 counting semaphore 사용)
  S1=1, S2=0, C=n 으로 초기화된 상태. n은 Critical Section 에 있는 co-excuted 프로세스의 개수이다.
  wait operation
  P(S1);
  C--;
  if (C<)){
      V(S1);
      P(S2);
  } else
      V(S1);
  
  signal operation
  P(S1);
  C++;
  if(C<=0){
      V(S2);
  }
      V(S1);
      

busy waiting: CPU 타임 슬라이스 안에서 계속 while을 돌면서 CPU를 활용한다.

non busy waiting: 주어진 타임 슬라이스가 있음에도 불구하고 entry section을 수행하고 나서 바로 sleep을 하고 다른 녀석에게 CPU를 양보하겠다. sleep을 하면 런 큐에 있던 프로세스가 웨이팅 큐로 간다. 다시 CPU 스케줄링을 받아야 런 큐로 갔다가 CPU를 잡을 수 있다. 이 과정을 필수적으로 다른 프로세스로 context switching하는 시간을 포함한다.
ex) A가 10ms에 sleep하도록 설정한다. 10~20ms엔 B를 수행하고 30ms에 세마포어가 풀려 A가 시그널을 갖고 Critical Section에 진입한다. 그런데 만약 10ms에 C가 A에게 시그널을 보내면? A는 context switching overhead를 감수하며 B에게 CPU를 양보해줬는데 다시 A가 CPU를 사용해야하는 것이 된다. 이런 경우에는 굳이 sleep을 안하고 busy waiting을 하는게 낫다... 적어도 작업 시간이 0.1ms 이상 되어야 sleep 세마포어를 쓸 가치가 있다. 네트워크 작업, ssd에서 읽어오기, I/O 작업 등의 시스템콜을 사용하는 일이나 예측할 수 없는 작업을 하는 경우 non busy 방식을 쓰는게 좋다.

 

Deadlock and Starvation

• Deadlock ) 모든 프로세스들이 공유자원에 접근하지 못하고 멈춰있는 상태
  ex) Critical Section에 들어가기 위해 S, Q 두개의 세마포어를 모두 잡아야한다고 가정함. S, Q=1로 초기화.
      P0 wait(Q); wait(S); signal(Q); signal(S);
      P1 wait(S); wait(Q); signal(S); signal(Q);
      S, Q=1이므로 두 프로세스 모두 S,Q를 무한히 기다림
• Starvation ) 다들 Critical Section 잘 들어간 것 같은데 하나만 절대 Critical Section에 못들어가는 문제 발생
                  못들어간 프로세스의 starvation 이라고 표시한다.
                  priority 기반의 스케줄링에서 발생하는 문제. 높은 우선순위인 프로세스가 낮은 우선순위를 가진 프로                 세스가 갖고 있는 공유 자원때문에 실행을 못하는 것.
  -> 우선순위 상속으로 해결
  non busy는 하나의 프로세스를 깨우고 list에서 꺼내는 방식으로 동작한다. 이때 리스트 중 누구를 골라야할지에 대한 문제가 발생한다. 우선순위 스케줄링으로 수행시키면 우선순위가 낮은 프로세스는 starvation 문제에 빠진다.
  A의 우선순위가 B보다 낮은 우선순위 스케줄링이 있다고 가정하자. A가 동작하는 도중에 OS가 모르고 CPU에서 빼버린 후 B에게 CPU를 줬다고 가정하자. 그런데 A가 공유 자원을 계속 잡고있어서 B는 잡지 못한다. 즉, B는 CPU를 받았는데 계속 공유자원을 대기해야하는 상황이다. A가 다시 CPU를 받기 전까지 B는 수행을 못한다. 일반적으로는 B가 한번 타임 슬라이스를 쓰고 나면 A가 다시 타임 슬라이스를 받으면서 공유자원을 쓰고 어느 순간에 release를 한 후 다시 B가 공유자원을 잡을 수 있는 상태가 된다. 그런데 우선순위 스케줄링을 하게 되면 B가 공유자원을 계속 대기하면서 타임 슬라이스를 무한히 사용해버린다(우선 순위가 가장 높으니까). 이로 인해 시스템이 마비되고 이를 해결하기 위해서 공유자원에게 -1과 같은 아주 높은 우선순위를 부여해준다. 공유자원을 잡은 프로세스는 공유자원을 사용하는 동안에 -1이라는 우선순위를 갖도록 변경해준다. 이것이 바로 우선순위 상속이다. 작업이 끝나면 다시 원래의 우선순위로 돌아오게 한다.

 

Monitors

동기화 문제를 해결하는 서비스이다.

아주 높은 레벨의 서비스라서 특수한 high level 언어에서만 제공한다.

언어 차원에서 동기화 문제를 다 해결한다. 사용자가 사용할때 신경쓰지 않아도 된다.