OS - (5) Synchronization

Background

Cooperating Process

cooperating process는 협동적인 프로세스들. 시스템 내 실행중에 다른 process들에 의해 영향을 주고받는 프로세스를 말한다. logical한 주소공간(code,data)에 의해 직접 공유하거나(thread : 해당 공간 share), 파일이나 메세지를 통하여 데이터를 공유하는 등 협동한다. (반대 개념은 Independent process)

Process Synchronization

많은 환경에서 cooperating process가 우세하다(많이 존재함). cooperating process들은 서로 영향을 미치고 데이터,흐름에 대한 동기화 문제가 발생할 수 있다. 이 프로세스들 사이에 동기화 하는 것을 process synchronization이라고 하며 현대에는 대부분 thread 기준으로 switching을 하므로 thread synchroniation이라고도 한다. synchronization은 공유되는 자원의 일관성을 유지하는 것.

Thread Synchronization

하나의 코드블록 또는 메소드를 한 순간에 정해진 스레드만이 이용하도록 제어하는 것.
프로세스 동기화는 하나의 자원(context switchng 단위)을 한 순간에 정해진 프로세스만이 이용하도록 제어하는 것.
현대의 운영체제는 thread switching을 위주로(P1의 a thread -> P2의 b thread) 처리가 이루어지므로 (context switching 단위가 thread) 프로세스 동기화는 하나의 자원(코드블록,메소드,cpu자원)을 한 번에 하나 프로세스의 스레드가 자원의 이용하도록 제어하는 것이다.
컴퓨터 자원은 한정되어있고 context switching을 통해 여러 프로세스들이 실행된다. 이 떄 context switching이 빈번하게 발생하게되고 (스케줄링 등) 이 때 데이터 무결성을 해치는 등 작업이 꼬이게 될 수 있으므로, 이를 처리하기 위한 것이 synchronization.

Race Condition

동시에 여러 process(thread)들이 동일 데이터에 접근하여 변경하는 등, 실행 결과가 접근특정 순서에 의존하는 현상, 어떤 순서로 접근하느냐에 따라 결과가 달라질 수 있는 상황. (경쟁상황)
-> 데이터 불일치 문제를 발생시킬 수 있다.

Race condition 발생 상황 예

• kernel모드 수행 중 interrupt 발생 경우
  
  count라는 변수에 값을 1 증가시켜주는 연산(++)은
  (1) Load
  (2) Increase
  (3) Store
  세 가지의 작업으로 이루어져있다.
  --연산도 마찬가지.
  만약 ++연산 후 --연산해 기존 값을 유지하는 작업에서,
  ++연산 도중에 intterupt되어 count--연산을 하게된다면,
  count++흐름은 --되기 전 값을 load한 상태에서 문맥정보를 저장 한다. 그리고 interrupt된 스레드,프로세스가 --연산을 수행하고 저장한다. --연산 완료 후 다시 이전 ++연산의 문맥정보를 가지고와서 작업을 완료한다. 이 때 ++연산은 이미 --되기 전 값을 load했기 때문에 --연산은 무시된다. : 동기화 문제 발생.
  => 커널모드의 수행이 끝나기 전에는 interrupt를 받지 않도록 하는 방법(disable/enable)로 문제 해결이 가능하다.( 커널모드 작업에 원자성 부여:인터럽트제한 )

• 프로세스가 시스템콜을 호출해서 커널모드로 수행중인데 context switch가 발생하는 경우
  두 프로세스 주소공간에서는 데이터를 공유하지 않지만 system call 수행동안에는 둘 다 커널 주소공간의 데이터에 접근한다. 커널 주소공간에서 작업 도중 CPU 점유 전환이 일어나면 race condition이 발생한다.
  
  이는 kernel모드 수행 중일 시 cpu가 preempt(전환)되지 않도록 하고, kernel모드에서 user모드로 돌아갈 때 preempt되도록 함으로 써 해결 가능.( 커널모드 작업에 원자성 부여 : context switching(스케줄링 등) 제한 )

• multiprocessor에서 공유 메모리 내 커널 데이터에 접근하는 경우
  
  어떤 cpu가 마지막으로 count를 저장했는지에 따라 결과값이 달라지는데, single processor의 경우 인터럽트 제한으로 해결이 가능하지만 멀티 프로세서의 경우 해당 방법으로 해결이 안된다. 한 번에 한 CPU만 커널에 들어가는 방법은 비효율적. 커널 내부에 있는 각 공유 데이터에 접근할 때 마다 해당 데이터에 대해서만 lock/unlock하는 방식으로 해결 가능.( 이용중인 데이터에 대한 접근 제한 )

Critical Section Problem

Critical Section

• Critical Section은 코드 상에서 Race Condition이 발생할 수 있는 특정 부분을 말한다. : 공유 데이터를 접근하는 코드 부분

• Critical Section 해결을 위한 조건

  1. Mutual Exclusion (상호 배제)
     Process가 Critical Section에 실행되는 동안 다른 Process들 Critical Section에 진입 불가.
  2. Progress (진행)
     Critical Section에서 작업 중인 프로세스가 없다면, Critical Section에 진입하고자 하는 프로세스가 진입 가능해야한다. (임계구역에서 실행중이지 않은 프로세스들만 다음 임계구역 진입 프로세스를 결정하는데 참여 가능하며 이 선택은 무제한 연기 No)
  3. Bounded Waiting (한정된 대기)
     Process가 Ciritical Section에 들어가기 위한 요청 한 후부터 요청이 허용될 때 까지, 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야한다. Critical Section에 진입하려는 프로세스가 무한정 기다려서는 안된다.(기아방지)

• Critical Section problem 해결 방법론
  단일 코어 시스템이라면 그저 공유 변수 수정중이면 interrupt를 disable해 해결할 수 있다.
  멀티 코어 시스템 + 비선점형 커널이라면 선점을 허용하지 않는 프로세스 스케줄링 특성상 Race condition이 발생할 일 조차 없다.
  하지만 현대 운영체제는 빠른 속도를 이유로 멀티 코어 시스템 + 선점형 커널을 사용하고 있고 이를 해결하기 위한 다양한 방법론들이 있다.
  
  SW관점, HW관점, 일반적 관점으로 생각해볼 수 있다.

Solution for Critical Section - SW method

Peterson's Solution (Two Process)

peterson's solution은 flag, turn변수를 사용한다.

• flag : 특정 프로세스가 임계 구역으로 들어갈 준비가 되었음을 나타냄.
• turn : 임계 구역으로 진입할 프로세스 순번
  

• mutual exclusion
  프로세스 진입하고싶음을 flag로 나타내지만, turn은 둘 중 하나로만 나타낸다.
  flag[i]==flag[j]==true이더라도, turn==i일경우 j는 진입이 불가능하다. 상대 프로세스가 flag가 false이거나, turn을 i로 바꾸어주어야한다. (한 번에 한 프로세스만 들어갈 수 있음)

• progress
  Pi가 ciritical section에 들어갈 준비가 안되어있다면(진입하고자 하는 상태가 아니라면) flag[i]==false이다. critical section에 들어갈 때는 flag를 true로 만들고, critical section에서 나오면서 flag를 false로 만들기 때문에 flag[i]가 false이면 Pi는 실행중이 아니다. 이 때 Pj가 들어가고 싶다면, while문에서 flag[i]는 False문으로 해당 while문은 False이고, Critical Section에 진입할 수 있다.

• bounded waiting
  Pi,Pj모두 Critical section에 진입하고싶을 때, turn flag를 상대방으로 만들어준다. 그렇기 때문에 먼저 대기중이던 프로세스가 있다면 해당 프로세스를 우선적으로 실행시켜주고, 해당 프로세스가 끝나면 flag를 false로 만들음으로써 while문에서 flag[상대]==False로 while문은 false로 critical section에 진입이 가능해진다. 그러므로 최대 1번만 기다리고 ciritical section을 수행할 수 있다.

• 문제점
  Critical section 진입을 기다리면서 CPU와 메모리를 사용하는 Busy Wating 문제점 존재. 또한 현대 컴퓨터 아키텍처에서는 종속성이 없는 읽기/쓰기 작업을 컴파일러나 프로세서가 재정렬할 수 있기 때문에 사용 불가할 수 있음.

Bakery Algorithm ( multi process )

n개의 프로세스를 처리하며 번호를 부여받고 가장 낮은 수의 번호를 가지고있는 process가 Critical Section에 진입하는 구조.

• choosing[i] : Pi가 번호를 받았는지 여부.
• number[i] : Pi의 대기번호 저장.
  Bakery 알고리즘은 max번호의 +1번호를 할당하여, 앞의 번호 choosing이 해소될 때 까지 대기하는 방식.

• Mutual Exclusion
  프로세스 중 낮은 번호를 가지고 있는 것이 critical section 진입하므로 가장 낮은 하나만 진입한다. (진입하고자 할 때 번호를 0부터 해당 번호까지 하나라도 choosing이 true(번호 선택중)이거나, number[j]가 자신의 number보다 작으면(!=0) busy waiting에 걸리므로)
• Process : exit section에서 자신의 번호를 반납하고 나오므로(number[i]=0)) number[j]!=0조건 해소에 따라 critical section에 진입할 수 있다.
• Bounded waiting : 먼저 번호를 발급받을수록 ciritical section에 먼저 진입하고, FCFS에 기반을 두어 최대 번호 +1이 최신의 번호가 되고 작은 순서대로 제거(0)되므로 n개만큼만 기다리게된다.

Synchronization Hardware (Solution for Critical Section - HW method)

busy wating과 현대 컴퓨터 구조의 문제로 sw적 방법에는 단점 존재하거나 사용불가하므로 HW에서 제공하는 방법 사용한다.
HW적 방법은 Atomic(인터럽트되지 않는)한 명령어를 사용한다.(locking scheme)

Test and Set

Test and set은 atomic하게 실행되며, 읽고 쓰는 것을 하나의 명령어로 동시에 수행할 수 있게 구현해준다.

hw적인 명령어는 bounded waiting을 만족하지 못하는 단점이 있다.
: waiting array를 사용하여 보완.

Mutex Locks

Mutex Lock은 Critical Section을 해결하기 위한 소프트웨어 도구 중 가장 간단한 방법이다.
프로세스가 ciritical section에 들어가기 전에 lock을 획득하고, 나올 때 lock을 반환한다.


available이라는 변수를 통해 lock의 가용 여부를 판단한다.
단점으로는 역시 sw적인 방법으로 busy waiting(CPU낭비)

Semaphores

Semaphore : 정수 변수. wait()과 signal() 두 개의 atomic한 연산으로만 변경할 수 있게 제공하는 방법.
ex) A class와 B class가 Critical Section(공통된 변수)를 가지고있을 경우, A 클래스가 들어가면 B클래스가 들어가지 못하게 하는 개념.)
mutext와 다르게 counting이 가능하고, 가용 프로세스 동시 실행이 가능하다.

• binary semaphore(이진 세마포)

  • 0,1값만 가능하며 시작 시 1로 초기화.
  • 이진 세마포와 뮤텍스
    • mutex와 사실상 역할은 같다(뮤텍스는 lock 메커니즘, 이진 세마포는 signaling 메커니즘, 뮤텍스는 객체이지만 세마포는 정수 변수.)
    • mutex의 경우 mutex를 소유하고 있는 thread가 mutex를 해제할 수 있다. semaphore는 소유하지 않고 있는 thread가 semaphore를 해제할 수 있다.
    • semaphore는 mutex가 될 수도 있지만, mutex는 semaphore가 될 수 없다( mutex는 thread에서 lock을 가지고 있기 때문, mutex는 소유할 수 있고 소유주가 책임지지만 semaphore는 소유 불가.)
    • semaphore는 시스템 범위에 걸쳐있고 파일시스템 상 파일 형태로 조재. mutex는 프로세스 범위를 가지고 프로그램이 종료될 때 자동으로 지워짐.

• counting semaphore

  • 세마포는 가용 자원 개수로 초기화된다.
  • 유한 개수를 가진 자원 접근 제어용으로 사용. (몇 개 접근하는지 셀 수 있다.)

• busy-wait 방식

  • wait()을 통해 S를 감소시키고(자원 사용), signal()을 통해 S를 증가시킨다.(자원 방출)
  • S값이 0이되면 모든 자원이 사용중이며 blocking하게된다. busy wait 발생가능. => Block & Wakeup 방식은 Critical Section으로의 진입에 실패한 프로세스를 기다리게 하지 않고 Block 시킨 뒤 Critical Section에 자리가 나면 다시 깨워줌으로써 Busy waiting에서의 CPU 낭비 문제를 해결

• block-wake up 방식
  
  Block을 수행하면, 커널은 block을 호출한 프로세스를 suspend 시키고 해당 프로세스의 PCB를 wait queue에 넣어준다.
  Wakeup을 수행하면 block 된 프로세스 P를 깨운 다음, 이 프로세스의 PCB를 Ready Queue로 이동시킨다.

critical section의 길이가 긴 경우에는 block-wakeup방식이 유리하다. 그러나 짧다면 context switching이 잦아져 오버헤드가 증가하고 ciritical section이 짧은 경우에는 busy-wait방식이 유리.

Monitors

세마포어의 문제점은 코딩하기가 힘들고 실수하기 쉬우며, 정확성을 입증하기가 어렵다. 세마포가 어셈블리 수준이었다면 monitor는 하이레벨.
Monitor(모니터)는 동시 수행 중인 프로세스 사이에서 추상 데이터의 안전한 공유를 보장하기 위한 High-level(고급 언어 수준) 동기화 구조

공유 데이터를 접근하기 위해서는 모니터의 내부 Procedure(wait,signal)를 통해서만 접근할 수 있도록 한다.
세마포어와의 가장 큰 차이점은, 모니터는 락(Lock)을 걸 필요가 없다. 세마포어는 프로그래머가 직접 wait와 signal을 사용하여 Race condition을 해결해야 하지만 모니터는 자체적인 기능으로 해결할 수 있게 된다.

monitor의 경우 2가지 queue를 가진다.

Mutual Exclusion Queue, Conditional Synchronization Queue로 이루어져있음.

• mutual exclusion : 하나의 스레드만 공유 자원에 접근할 수 있게 하는 queue. 특정 스레드가 공유자원을 사용하는 함수를 사용하고있다면, 다른 스레드는 접근 불가능하고 이 queue에서 대기한다.
• conditional synchronization : 진입 스레드가 block되면서 새 스레드가 진입 가능하게 하는 공간. 새 스레드는 해당 queue로 블록된 스레드를 wake up(깨우기) 할 수 있다. 깨워진 스레드는 현재 스레드가 나가면 재진입 가능해짐
  
  
  위에서 notify는 signal(블록된 스레드를 깨우며, 새로운 스레드가 실행하는 방식으로 깨움)을 의미

Mutex + Condition value을 합친 것을 monitor라 한다. (mutex 상위 호환)

• 조건 변수(Condition Variables)
  • 조건(Condition) x, y
  • 프로그래머는 하나 이상의 조건 타입 변수를 정의할 수 있다.

• 조건 변수에 적용되는 두 가지 연산
  • wait() : 연산을 호출한 프로세스는 보류
  • signal() : wait()를 호출한 프로세스 중 하나가 재개
    보류하는 프로세스가 없다면, 아무것도 일어나지 않는다.
• 연산이 발생된 이후 2가지 가능성
  • P가 signal(), Q가 wait()인 경우
    • Singal and wait : P는 Q가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.
    • Singal and continue : Q는 P가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.