Synchronization

동기화란

• 공유 데이터에 대한 동시 접근은 데이터의 일관성(consistency)를 해치는 결과를 낳을 수 있다.
  • Race Condition
    • 공유 데이터에 대해 여러 프로세스가 동시에 접근, 변경을 시도하는 상황으로 일관성이 보장되지 않는 상황
• 데이터 일관성을 유지하기 위해서는 수행하는 프로세스들이 순차적(serializing을 통해)으로 데이터를 접근하게 만드는 기법이 필요하다
  • 이것을 동기화(synchronization)라고 함
• OS뿐만 아니라 딥러닝에서도 동기화 과정은 필요하다. 딥러닝에는 모델을 학습시키는 수많은 프로세스들이 존재하는데, 이 프로세스들이 작업을 수행하면서 중간중간에 동기화를 해주며 모델을 업데이트해줘야 한다. 이 과정 없이는 모델이 정상적으로 통합되지 않는다.

예제

• 은행의 입출금 문제 1000원의 잔고가 남아있을 때, 500원의 입금과 500원의 출금이 동시에 일어날 경우, 그 결과는?

• 두 프로세스

  < Process A : 입금 처리>
  … //기타 관리 코드
  Balance = Balance + 500;
  … //종료
  

  < Process B : 출금 처리>
  … //기타 관리 코드
  Balance = Balance - 500;
  … //종료
  

• Balance 가 공유되고 concurrent 하게 수행하는 경우

구체적으로 보면

< Process A >
Register1 = Balance
Register1 = Register1 + 500
Balance = Register1

< Process B >
Register2 = Balance
Register2 = Register2 - 500
Balance = Register2

• 인터럽트로 인하여 execution interleaving :

T0: A process execute Register1=Balance [Register1=1000]
T1: A process execute Register1=Register1 + 500 [Register1=1500]
T2: B process execute Register2=Balance [Register2=1000]
T3: B process execute Register2=Register2 - 500 [Register2= 500]
T4: A process execute Balance =Register1 [Balance =1500]
T5: B process execute Balance =Register2 [Balance = 500]

• 최종적으로 500의 잔고가 남게 된다. 또는 Execution interleaving 순서에 따라 1500이 될 수도 있다. 즉, 결과를 예측할 수 없다는 문제가 생긴다 – race condition !

지금까지 배운 내용 중에서 동기화가 필요한 부분

• Thread programming
  • Data section is shared
• Shared memory
  • Multiple processes can access
• 커널
  • 커널 thread(execution flow)들끼리 커널의 자료구조가 공유된다.
  • Data structures shared

Critical section

• 동기화 문제를 Critical Section으로 모델링(복잡한 디테일들을 단순화)
• Critical section 이란
  • 여러 프로세스들이 공유하는 데이터에 접근하는 코드 영역
    • 위의 예제에서는 balance에 접근하는 코드가 해당된다.
  • 한 번에 오직 하나의 프로세스만이 critical section에 진입해야 함
    • 예: 은행 계좌의 Balance를 consistent하게 유지할 수 있음
• Critical Section을 사용하여 모델링하면:
  • entry section - critical section에 진입해도 되는지 확인 후 진입
  • critical section - 작업 수행
  • exit section - critical section에서 나온 후, 다른 프로세스가 들어갈 수 있도록 특정 작업 수행
  • remainder section - critical section과 관련 없는 작업들

Critical Section 해결 조건들

• Critical Section 문제를 해결하는 알고리즘은 아래와 같은 세 가지 조건을 모두 만족해야 함
  • Mutual Exclusion (상호 배제) - MUTEX
    • 만약 프로세스 A가 critical section에 진입해 있다면, 다른 모든 프로세스(priority와 상관 x)는 진입할 수 없어야 함
  • Progress
    • critical section에 진입하려는 프로세스가 존재한다면, 그 중에서 한 프로세스는 critical section에 진입할 수 있어야 함
  • Bounded Waiting
    • 어떤 프로세스가 Critical section에 진입할 때까지 걸리는 시간에 “limit”이 존재하여야 함

Corner case

같은 환경에서 항상은 아니지만 종종 발생할 가능성이 있는 예외 상황을 말한다. ex) 한번이라도 어떤 프로세스도 critical section에 진입을 못 하는 경우가 발생한다면 Corner case로, 반드시 예외 처리를 해줘야 한다.

두 프로세스를 위한 알고리즘

• Shared variables:

  int turn = 0; // 초기화 
                // turn = 0 일 때, P0 가 critical section에 진입 가능 
  

• Process P0

  while (turn != 0) ; // waiting (entry section)
  		critical section
  turn = 1;           // exit section
  		remainder section
  

• Process P1

  while (turn != 1) ; //waiting (entry section)
  		critical section
  turn = 0;           // exit section
  		remainder section
  

• 불만족 조건 : progress, bounded waiting

  • 두 프로세스의 수행 순서가 alternate 안되면 진행 안됨
    • P0, P0, P0 이면, 두 번째 P0 부터 멈추게 됨 (turn=1)
  • 정해진 dictate대로(P0-P1-P0-P1…) 프로세스가 수행되지 않을 경우에 progress가 만족되지 않음

개선된 알고리즘 – 두개의 flag 이용

• Shared variables:

  boolean flag[2]; // flag [0] = flag [1] = false 로 초기화 
  								 // flag [0] = true일 때, P0 이 critical section에 진입 
  								 // flag [1] = true일 때, P1 이 critical section에 진입 
  

• Process P0

  flag[0] = true;
  while (flag[1]) ; // waiting (entry section)
  		critical section
  flag[0] = false;  // exit section
  		remainder section
  

• Process P1

  flag[1] = true;
  while (flag[0]) ; // waiting (entry section)
  		critical section
  flag[1] = false;  // exit section
  		remainder section
  

• 만족 조건 : mutual exclusion

• 불만족 조건 : progress, bounded waiting

  • 두 프로세스가 동시에 flag[] 를 true 로 하면, Deadlock이 걸린다. 이것은 Corner case에 해당한다.

Peterson solution

• Shared variables

  int turn; 
  boolean flag[2]; // flag[0] = flag[1] = false 로 초기화
  

• Process P0

  flag [0] = true;
  turn = 1;
  while (flag [1] && (turn == 1)) ;
  		critical section
  flag [0] = false;
  		remainder section
  

• Process P1

  flag [1] = true;
  turn = 0;
  while (flag [0] && (turn == 0)) ;
  		critical section
  flag [1] = false;
  		remainder section
  

• 만족 조건 : mutual exclusion, progress, bounded waiting

  • 두 프로세스가 동시에 수행되더라도, turn 값에 의하여 결정됨

Peterson Solution의 한계

• Peterson solution의 확장은 가능한가?
  • 3개 이상의 프로세스에서는 어떻게 구현할 것인가
  • 확장된 알고리즘의 증명은 어떻게 할 수 있나
  • 어떤 경우에도 동작함을 보여야
• 일반적으로 이러한 증명은 NP 문제임
  • 증명이 되더라도 매우 복잡함

초기 해결책

• Critical section에 들어가면서 Interrupt를 disable함
  • Interleaving 방지
• 사용자 프로그램이 interrupt를 control하는 것은 바람직하지 않음
  • 커널이 사용자 프로그램에 의해 제어되는 것은 보안면에서 위험
• 커널을 critical section 으로 만듦 (Many to One)
  • process as protection boundary
  • 커널에 들어갈 때 interrupt disable함
  • 커널 전체가 거대한 critical section으로 처리함
• Scalability 문제점
  • 프로세스의 숫자가 많아 질 때 문제가 생긴다 – 대기시간 길어짐
  • 커널 multithreading 도입(Many to Many, One to One)

하드웨어 솔루션

• 인터럽트가 아닌 다른 방법이 필요함
  • 인터럽트는 하드웨어에 의해서 발생하는데, 이를 소프트웨어적으로 처리하려고 하니, 동기화 문제가 잘 해결되지 않음
  • 소프트웨어보다는 하드웨어에서 어떤 처리를 통해 문제를 간단히
• 명령어(instuction-하드웨어와 소프트웨어의 경계)로 처리하면 알고리즘이 매우 간단하게 됨
  • acquire lock (instruction)
  • critical section
  • release lock (instruction)
  • reminder section
• 동기화를 위한 instruction이 도입됨

Synchronization Instruction

• CPU에서 원자적(atomically)으로 수행되는 명령어(instruction) 이용

  • 원자적이란?
    • 원자(atom) : 쪼갤 수 없는 단위
    • 명령어가 수행되는 동안 인터럽트 발생 못함 (uninterruptible)
      • 어떤 instruction이 CPU의 5clock이 걸리는 작업이라면, 이 작업이 수행되는 5clock동안은 인터럽트가 발생할 수 없다.
      • 그런데 인터럽트는 어쨌든 Asynchronal하게 발생하는 이벤트인데, instruction 도중에 발생하는 인터럽트는 어떻게 처리?
        • instruction이 수행되는 동안에 프로세서는 하드웨어를 dispatch하지 않고 pending하고 있다가 instruction이 끝나고 다음 instruction이 시작하기 전에 인터럽트는 initiate한다.
      • 인터럽트가 interleaving(코드의 사이사이에 끼면서 데이터를 overwrite하는 것)의 원인이기 때문
      • 만약 하드웨어의 단계에서 여러 개의 instruction이 동시에 실행된다고 하더라도, 자원에 무언가를 읽고 쓰는 I/O는 한 위치에 대하여 한 instruction만이 가능하기 때문에 overwrite 문제가 발생하지 않는다.

• Test and Set 명령어

  • 다음 명령어를 하나의 instuction으로 정의하면 이 함수 내부의 코드(원래는 어셈블리어로 되어있어야 함)를 실행하는 동안에는 interrupt가 발생하지 않는다.
  • C언어를 어셈블리어로 바꾸는 명령어 = cc -s

  boolean TestAndSet(boolean *target) {
  	boolean rv = *target;
  	*target = true; // 명령어 내에서 implicit하게 true를 write
  	return rv;
  }
  

Q : CISC 구조가 RISC 구조는 instruction과 어떤 관계인가요? A : RISC에서는 CISC와 달리 곱셈을 덧셈을 여러번 수행하는 방식으로 구현한다. 이 말은 즉, RISC는 곱셈을 원자적으로 수행하지 않겠다는 뜻이다.

Q : atomic instruction을 지원하지 않는 하드웨어에서는 완벽한 동기화를 하는 방법이 없는건가요? A : 없는 것은 아니다. 그런데 문제는 프로세스가 늘어날 수록 발생할 수 있는 case가 기하급수적으로 늘어나서 어떤 Corner case도 없도록 하려면 아주 복잡한 알고리즘을 짜야 한다는 문제가 생긴다. (Scalability)

Q : test and set 명령어가 수행되는 도중에는 인터럽트가 발생되지 않는다고 하였는데, 명령어 수행 도중 갑자기 전원이 차단되는 등의 상황이 발생되는 경우는 어떻게 되나요? A : 이러한 상황은 피할 수 없는 인터럽트이므로 NMI(Non-Maskable Interrupt)라고 한다. Test and Set 같은 명령어는 전원이 나가버리면 더 이상 interrupt를 한다안한다의 의미조차 없다. 시스템이 서버리는 것이다.

Test-and-Set을 사용한 Peterson 솔루션

• Shared data:

  boolean lock = false; 
  

  • 위와 같은 변수를 lock variable이라고 한다.

• Process Pi

  • 어셈블리어로 작성된 코드를 C에서도 함수 형태로 호출이 가능하다. 여기서는 TestAndSet() 호출이 가능하다.
  • Atomic Property : 하나의 프로세스가 수행되고, lock이 다시 false가 되는 순간, loop를 돌고 있던 여러 프로세스들 중 하나의 프로세스만이 critical Section으로 들어갈 것이다. 왜? acquire lock (instruction)인 TestAndSet()이 atomic하기 때문이다.

  do {
  	while (TestAndSet(&lock)) ; // if return 1, loop
  			critical section
  	lock = false;
  			remainder section
  }
  

다른 명령어 - swap

• Swap 명령어

  void Swap(boolean *a, boolean *b) {
  	boolean temp = *a;
  	*a = *b;
  	*b = temp;
  }
  

• Intel 80x86 instruction set

  • BTS - Bit Test and Set (386+)
  • BSWAP - Byte Swap (486+)

Swap을 사용하는 솔루션

• Shared data (false 로 초기화):

  boolean lock; 
  boolean waiting[n];
  

• Process Pi

  do { 
  	key := true; 
  	while (key == true) 
  		swap(&lock, &key); 
  				critical section 
    lock := false; 
    			remainder section 
  }
  

Instruction으로 부족한 점

• 동기화 instruction을 쓰면 mutual exclusion은 해결이 되나, bounded waiting 같은 조건은 사용자 프로그램에서 제공해야 함
  • critical section에 진입할 수 있는 상황에서 어떤 프로세스가 언제 진입하게 될 지 결정하는 것은 하드웨어이므로
  • 그때그때 프로세스가 임의적으로 선택된다.
• Bounded waiting이 주어진 문제마다 조금씩 차이가 있기 때문에, 사용자 프로그램에서 제대로 처리하는 것을 기대하기 어려움
• 좀 더 comprehensive한 동기화 primitive가 필요함
  • 상위의 단계에서 우리가 쉽게 이해할 수 있는 동기화 primitive

Semaphore(세마포)

• 세마포: 두 개의 원자적 연산을 가지는 정수 변수
  • 원자적인 연산 :
    • wait() 또는 P()
    • signal() 또는 V()
  • 세마포는 2개의 원자적인 연산(atomic operation)에 의해서만 접근됨
• 동작
  • P는 critical section들어가기 전에 호출
  • V는 나와서 호출함
• P와 V연산은 서로 독립적으로 그리고 원자적으로 수행됨
  • 하나의 프로세스가 P를 수행하여 세마포어의 값을 수정하는 동안 다른 프로세스에서 P나 V를 수행해도, 동일한 세마포어의 값을 수정하지 못한다.

Q : P(), V()도 hardware 적인 instruction이라고 보면 될까요?? A : P()와 V()의 어딘가에는 hardware적인 instruction이 포함되어있겠지만, 이것들은 instruction 이외에도 더 많은 semantics를 갖고 있다.

Q : semaphore 자체가 하드웨어적으로 구현이 되어있는 경우도 있나요? A : 가능은 하지만 매우 긴 instruction이 되므로 비효율적이다.

Peterson 솔루션을 세마포로

• 차이점

  • flag 필요 없음
  • Process : 동일한 동작

• Process i:

  int s = 1;
    
  	P(s);
  Critical Section
  	V(s);
  remainder
  

세마포의 종류

• 세마포 값의 변화
  • P - decrement
  • V - increment
• 2가지의 세마포
  • Counting semaphore
    • 세마포 값의 범위는 양수
    • 초기값은 가능한 자원의 수로 정해짐
      • 자원의 수 : 프로세스가 들어갈 수 있는 버퍼의 길이가 된다.
  • Binary semaphore
    • 세마포 value가 가질 수 있는 값은 0과 1
    • Counting semaphore보다 구현이 간단함
• Binary semaphore를 이용하여 counting semaphore를 구현할 수 있음

Q : Semaphore, lock 등을 도입하더라도 critical section은 atomic해야하나요? A : entry section과 exit section이 원자적이면, critical section은 원자적이지 않아도, 한 순간에 하나의 프로세스만이 critical section에 진입하는 것이 보장되므로 critical section 자체가 원자적일 필요는 없다.

Original 세마포

• Busy waiting 이용

  • P(S)

    while ( S < = 0 ) loop ; 
    	S = S - 1;
    

  • V(S)

    S = S + 1;
    

• Busy waiting은 critical section에 진입할 조건이 될 때 까지 loop을 돌면서 기다린다.

  • 단점
    • Single core CPU 환경에서 CPU cycle을 낭비할 수 있음
      • s <= 0에서 P(s)가 수행될 경우, loop을 나갈 가능성이 없음
    • 대기 중인 프로세스 중에서 누가 critical section에 진입할지 정해지지 않음
  • 멀티코어에서는 busy waiting이 유리할 수 있음
    • P(s)에서 loop를 돌리는 동안 다른 코어에서 수행되던 프로세스가 V(s)를 수행하면 loop을 빠져나갈 수 있다.

Q : P와 V가 atomic한 연산이라고 하셨는데 그러면 P에서 loop과 s=s-1이 하나의 instruction으로 수행되어야한다는건가요? A : P와 V는 atomic한 연산은 맞지만 하나의 instruction으로 이뤄진 것은 아니다..

Q : 그러면 P가 여러 insturction으로 이루어져도 P가 수행되는 동안은 인터럽트가 발생 안한다는 뜻인가요? A : 세마포가 atomic하다는 의미는 instruction이 수행될 때 인터럽트가 발생한다는 것과는 다르다. 좀 더 rich한 의미이며, 인터럽트가 사이사이에 발생하더라도 atomic할 수 있는 방식이다.

세마포 with sleep queue

• Sleep queue를 이용
  • Busy waiting 방식의 CPU cycle을 낭비하는 문제를 해결
  • 세마포의 자료구조에 sleep queue를 추가하여, 대기중인 프로세스를 관리
    • 세마포의 값이 양수가 되어 critical section에 진입이 가능하게 되면, sleep queue에서 대기중인 프로세스를 깨워 실행시킴
    • 질문:
      • 누가 깨우는가
      • 누구를 깨우는가
    • Sleep은 context switching 발생시킴

세마포 sleep queue 구현

• 세마포 자료구조 와 P/V

  typedef struct {
  	int value; // 세마포어 값
  	struct process *list; // 세마포어를 대기하는 프로세스의 sleep queue
  }semaphore;
    
  P(semaphore *S):
  S->value --;
  if ( S->value < 0) {
  	add this process to S->list; //프로세스를 sleep queue에 삽입
  	block();
  }
    
  V(semaphore *S):
  S->value++;
  if (S->value <= 0) {
  	remove a process P from S->list; // 프로세스를 sleep queue에서 꺼내온 후,
  	wakeup(P); // 실행
  }
  

Binary Semaphore의 구현

• Semaphore S

  • critical section에 진입한 프로세스가 있는지 나타냄 (0 or 1)

• P(S)

  S = 1;    // 초기값
  lock = 0; // P 시작하면서 초기화 
  while (!lock)
  	swap(&lock, &S); // if lock is 0, loop (S==0)
  									 // p. 16과 reverse – S 값이 0 이면 wait 이므로 
  

• V(S)

  • S = 1;
  • 진입한 프로세스가 없음을 나타내어 wait()에서 대기 중인 프로세스를 진입 가능하도록 한다.

Counting Sepmaphore의 구현

• Binary semaphore를 이용하여 counting semaphore 구현

  • Counting semaphore를 CS라 하고, counting semaphore의 value는 C
  • 2개의 binary semaphore S1, S2 를 이용
  • S1 = 1, S2 = 0으로 초기화 (C가 양수라고 가정)

• wait operation
  P(S1);
  C--;
  if (C < 0) {
  	V(S1);
  	P(S2);
  }
  else
  	V(S1);
  

• signal operation
  P(S1);
  C++;
  if (C <= 0) {
  	V(S2);
  }
  V(S1);
  

Semaphore의 단점

• Deadlock이 발생할 가능성이 존재한다.
• P와 V의 연산이 분리되어 있기 때문에, 잘못 사용할 경우에 대한 대책이 없음
  • 사용자가 직접 프로그램에서 Critical Section 앞뒤로 P와 V를 끼워주는 규칙을 지켜줘야만 하며, 커널은 이것을 강제할 권한이 없다.
  • Exit without V
    • Critical section 후에 lock을 풀어주는 V가 없으므로, 한 프로세스가 critical section에 진입하고 나면 다른 프로세스들은 critical section에 진입 못하므로 deadlock이 발생
  • Access without P
    • Critical section 앞에 lock을 걸어주는 P가 없으므로 여러 프로세스가 동시에 critical section에 진입 할 수 있으므로 mutual exclusion을 보장 못함

Deadlock

• Deadlock
  • 두 개 이상의 프로세스들이 끝없이 기다리고 있는 상황

P0
wait(S);
wait(Q);
…
signal(S);
signal(Q);

P1
wait(Q);
wait(S);
…
signal(Q);
signal(S);

Q : P0가 wait(S)로 S를 점유하고 있고 P1이 wait(Q)로 Q를 점유하고 있다면 각각의 프로세스들은 critical section으로 들어가서 작업을 하고 V(s), V(Q)로 빠져나오지 않나요? 왜 Wait(S)를 하고 critical region에 들어가서 작업을 하고 V(S)를 바로 하지 않고 다시 wait(Q)를 하여 무한루프를 도는지 궁금합니다. 그리고 여기서 S와 Q를 점유한다는것이 critical region에 들어갔다고 이해해도 되는지와 S와 Q가 정확이 어떤것을 지칭하고 있는지 궁금합니다. A : 앞에서도 말했다시피, 질문에서처럼 같이 V 작업 처리를 안해주고, 바로 다른 자원을 요청하고 있는 프로그램이 충분히 있을 가능성이 있고, 이 특이한 상황에서는 커널이 Deadlock을 막을 수 없다. 이처럼 P나 V가 있어야할 곳에 없거나, 혹은 세마포 자체가 cross되는 상황에서는 Deadlock이 발생할 수 있다.

Q : P와 V가 atomic하다면 interrupt를 못받는 것으로 이해했는데 이럴때 preemption은 어떻게 일어나는건가요? A : Binary Semaphore의 swap() 정도를 제외하고는 모든 부분이 instruction이 아니기 때문에 모든 지점에서 preemption이 가능하다. 그래도 atomic property은 유지된다. synchronization과 scheduling이 서로 영향을 미치지 않는 상태에서 독립적으로 정상 수행이 되는 것이다. synchronization이 scheduling을 임의로 제어해서는 안된다. 예를 들어 sleepqueue에 한 프로세스를 깨울 것이냐에 관한 것은 scheduling의 영역이다. synchronization의 영역에서 누구를 선택할 것이냐를 선택하는 것은 월권이다. 따라서 실제로 코드로 구현할 때에는 어느 한 프로세스를 깨우지 않고, 모든 프로세스를 깨운다. 그 중에서 무엇이 돌아갈지는 커널이 scheduling decision을 통해 알아서 결정할 것이다.

Q : S가 접근가능한 공유 자원의 남은 개수 이면서, 이 값이 음수로 전환되면 대기중인 프로세스의 수를 나타낸다고 이해해도 될까요? A : 그렇다.

Partial Order

• Deadlock 을 해결하는 방법
  • 발생할 확률이 0.0001%만 있어도 문제
  • 하나의 시스템 뿐만 아니라 분산환경에서의 Deadlock 문제
• Partial Order(부분순서 집합) : 부분 순서가 정의된 집합. 모든 원소가 비교 가능할 것을 요구하지 않는다.
• Total Order(전순서 집합) : 임의의 두 원소를 비교할 수 있는 부분 순서 집합. 즉, 모든 원소가 비교 가능한 부분 순서.
• 어떤 집합의 원소들의 binary relation(≤)으로 reflexive, antisymmetric, transitive 조건을 만족한다.
• PO는 모든 원소 a,b,c에 대해 다음 조건을 만족한다.
  • a ≤ a (reflexivity)
  • if a ≤ b and b ≤ a then a = b (antisymmetry)
  • if a ≤ b and b ≤ c then a ≤ c (transitivity)

• 이것은 세마포를 걸만한 곳들에 세마포를 거는 순서를 정해둠으로써, Deadlock이 서로의 것을 점유하여 무한정 기다리는 일을 방지하는 방법이다.

Q : 교수님 total order가 아니라 partial order를 사용하는 이유는 deadlock이 걸릴 수 있는 것들만 order를 주기 때문인가요? A : 그렇다. 모든 resource들에 대하여 order를 지어줄 수는 없다. 따라서 서로의 critical section에 들어가게 되는 resource들끼리만 order를 지어준다.

Q : 만약에 S, Q 순서로 partial order가 있으면 S만 잡아도 되거나 Q만 잡아도 되더라도 S와 Q를 순서대로 모두 잡아야한다는 건가요? A : S->Q라면 S를 잡아야할 때는 S만 잡으면 되고, Q를 잡아야할 때는 그 전에 S도 잡아야 한다.

Q : partial order는 wait를 할때만 고려하면 되나요? 아니면 signal을 할때도 고려해야 하나요? A : signal을 할 때에도 고려해야 한다.

세마포의 실제 구현

• 세마포 여러 동작을 어떻게 atomic하게 처리하는가
• 커널이 single thread인 경우
  • P/V를 system call로
  • Kernel내에서 세마포 동작을 구현함
  • 커널 내 수행이 non preemptive이므로 커널에 들어간 프로세스가 critical section에 들어간 것임
• 커널이 multithread인 경우
  • P/V를 system call로
  • 커널 내에서 별도로 동기화를 해야 함
    • 이렇게 했을 경우 오버헤드가 크므로 왠만하면 동기화는 유저 레벨에서 하는 편이 더 효율적이다.

Q : P/V가 시스템 콜로 구현이 되어있으면 P,V는 non-preemptive하지만 P 이후 critical section 내에서 작업 하는 과정 자체는 preemptive하다고 볼 수 있나요? A : 그렇다. P/V는 atomic해야하며 critical section은 preemptive해야 한다.

Monitor

• 세마포는 사용자가 P/V를 제대로 사용해야 한다
  • 명시적으로 코드에 넣어야함
  • Error-prone
• High-level 언어에서의 동기화 방법이 필요
  • 예: Java의 thread에서 동기화를 위해 Monitor가 사용됨
  • 한 순간에 하나의 쓰레드만 monitor에서 활동하도록 보장
• Application은 procedure를 호출하는 것 만으로 동기화를 해결할 수 있음
  • 프로그래머는 동기화(P와 V연산)를 명시적으로 코딩할 필요가 없음

Monitor 사례: “synchronized” in Java

• “synchronized” 블럭을 통해 동기화되는 영역을 지정 가능

  public class account {
    private int balance;
      
    public int increaseBalance(int amount) {
      return balance += amount;
    }
  }
  

  public class account {
    private int balance;
      
    public synchronized int increaseBalance(int amount) {
      return balance += amount;
    }
  }
  

• 이는 자바의 한 함수에서 정의된 모든 코드들에 대하여 동기화를 시켜주며, 이 함수는 한 순간에 하나의 스레드에서만 실행될 수 있다.

synchronized 내부 동작

• Entry queue에서 대기하고 있는 쓰레드들은 increaseBalance() 함수에 진입하기 위해 기다리고 있음
• 쓰레드 T1이 increaseBalance() 함수에서 나간 후에 다른 쓰레드가 함수에 진입할 수 있음
• 즉 자바 함수 자체가 critical section이 되는 것

Monitor 사례: Transaction in Database

• Transaction
  • Transaction으로 처리해야 하는 명령문들을 모아놓은 작업 단위
    • 하나의 transaction은 atomic하게 움직임
    • 데이터베이스에서의 일관성을 위한 monitor와 같은 abstraction이므로 P/V, 시스템 콜 이런것들이 필요가 없다.
  • 모든 작업단위가 반드시 완전히 수행되면, 성공
    • 만약 어느 하나라도 실패한다면 transaction은 취소됨

Q : Partial order는 어느 레벨에서 어떤식으로 구현이 되나요? Monitor의 동작과 중복되는 부분이 있을 것 같아 질문드립니다! A : Monitor는 high-level 프로그래밍 언어에서 제공해주는 동기화 기법이기 때문에 Partial order는 Monitor가 없는 환경에서 개발자가 직접 코드로 동기화를 작성해줘야할 때 사용하는 기법이라고 할 수 있다. 즉 Partial order는 프로세스 레벨, 혹은 스레드 레벨, 시스템 콜 이런 단계에서 사용하는 기법이라고 할 수 있다.

Q : Semaphore의 실제 구현을 얘기하고 있을때, user level에서 구현하는게 비용이 더 많이 든다고 했습니다. 여기서 user level에서 구현이 된다는것은 kernel이 multithread인 경우 인가요? 그러면 kernel이 multithread는 single thread보다 더 많은 비용이 든다고 생각하면 되나요? A : user level에서 구현하는 게 더 비용이 많이 든다는 것은 정확히는 알고리즘이 복잡해지고 디버깅도 어려워짐을 의미한다. 그리고 user level에서 구현한다는 것은 kernel의 도움을 받지 않고 구현함을 의미한다.