06-Synchronization

1.     Background

-       Parallel access가 실행 될 때 동시에 공유된 데이터를 사용하려고 해서 동기화가 필요하다.

-       Process synchronization : Orderly execution을 통해서 순서대로 process를 실행 해야 한다.  => 그러지 않을 시 결과값이 달라질 수 있다. 

 

2.     Race Condition

-       여러 프로세스가 동시에 동일한 데이터를 접근하고 조작한다.

-       실행결과가 접근이 이루어지는 특정 순서에 따라 달라진다.

-       Solution : 동시에 실행되는 프로세스들이 synchronization (동기화) 되어야한다

2-1.  Mutually exclusive access 를 critical section에서 실행해야한다

1)     Software C.S : Perterson’s Solution

2)     Hardware C.S : Mutexes Locks

3)     Semaphores – 공유자원에 대한 접근을 제어하기 위해 사용되는 동기화 도구

-       생산자와 소비자 프로세스가 각각 실행될 때는 올바르게 작동하더라도, 동시에 실행될 때는 제대로 동작하지 않을 수 있다.

-       Concurrent : 하나의 스레드가 interrupt 받아서 하던 것을 멈추고 다른 스레드가 실행될 때 발생

-       Parallel : 두개의 스레드가 동시에 하나의 데이터를 필요로 할 때

 

3.     Critical-Section Problem 

-       Critical section : shred resource하는 코드들

-       한 번에 한 프로세스만이 자신의 CS 구간에서 실행될 수 있도록한다.

-       But, 여러 프로세스가 동시에 실행되면서 공유자원에 접근할 때 발생할 수 있는 문제

-       각각의 Process는 entry section, critical section, exit section, remainder section 순으로 들어갈때 request를 해야한다

Ex. Lock & Unlock : Pthread_mutex_lock (entry section) , pthread_mutext_unlock(exit section) 

Ex. Producer&consumer : counter변수를 공유하는부분이 critical section

 

4.     C.S. Requirements

1)     Mutual Exclusion : 한번에 한 프로세스만 critical section에 들어갈 수 있도록 한다.

2)     Progress : critical section에 process가 존재하지 않으면, critical section을 원하는 process가 들어가야한다 – deadlock (두개의 프로세스가 서로 소유하고 있는 자원을 기다리면서 무한정 대기하게 되는 상태) free

3)     Bounded Waiting : 유한한 시간 내로 각각의 process는 critical section에 들어가야한다 – starvation free (계속기다리지 않아야 한다)

 

5.     C.S. Algorithm

-       Shared variable : wants[] (true or false)

do { 

      wants[i] = true; //entry section

      while (wants[j]){;} //대기 = j 프로세스가 원한다면 

                critical section

      wants[i] = false; //exit section

} while (TRUE);

 

6.     Peterson’s Solution

-       Software-based solution : hardware의 지원없이 C.S. problem을 해결하는 것

-       Shared variable : not_turn; = 내 차례가 아니라고 말해주는 것. 양보변수이다.이 변수를 통해 2개의 프로세스가 각각 차례대로 들어갈 수 있다. 배열 아님!

for (;;) { 

      wants[i] = true; //entry section

      not_turn = i;

      while (wants[j] && not_turn == i){;} //대기 = j 프로세스가 원한다면 

                critical section

      wants[i] = false; //exit section

} while (TRUE);

          

1)     Mutual exclusion ? 

-       두개의 프로세스가 동시에 C.S.에 들어갈 수 없다. 

-       not_turn variable이 하나를 막아준다

2)     Progress? Bounded-waiting?

-       영원히 대기 할 수 없다 -> not_turn variable이 적어도 하나는 들어가게 해주기 때문 so, 유한한 기다리는 시간을 가진다

 

7.     Hardware Approach

-       Peterson’s Algorithm (Software solution)은 매우 비싸고 느리고, 오직 2개의 프로세스 사이에서만 가능하다.

-       많은 system들은 hardware support (ex. Atomic Instructions)를 받는다.

-       모든 해결책은 lock (동시에 접근하지못하도록 제어하는 잠궈버리는것)을 통해 critical section을 보호하는 아이디어에 기반

-       현대 System은 Atomic 한 hardware instruction을 제공한다

Atomic = 중간 불가능, interrupt 불가능 = non-interruptible

 

8.     Atomic intructions (Hardware Instruction) non-interruptible

1)     TestAndSet() : lock = false 로 initialize

do {

      while (TestAndSet(&lock)) //atomic 한 operation

                ;

      CRITICAL SECTION

 

      lock = FALSE;

      REMAINDER SECTION

} while (TRUE)

 

Boolean TestAndSet(Boolean *target){ //true로 바꿔주는 것, 현재상태를 return
      Boolean rv = *target;

      *target = TRUE;

      Return rv;

} //lock을 true로 만들어주고 critical section을 지나가게 한다음 바로 false로 바꾸어서 다른 process가 못 들어오게 한다. 

 

9.     Mutex Locks

-       Hardware solution은 매우 복잡해서 프로그래머들이 사용할 수없다

-       Software solution(API)에다가 hardware support를 더하는 것이다

Acquire () { //entry section

          While (!available);  //wait

          Available = false;

}

 

Release() { //exit section

          Available = true;

}

-       Acquire() , release() => atomic한 성격이다. (hardware instruction)

// 초기화

mutex->available = 0;

// Test and Set을 사용한 획득

void acquire(lock *mutex) {

    while (test_and_set(&mutex->available) != 0)

        ; // busy-wait

    return;

}

void release(lock *mutex) {

    mutex->available = 0;

    return;

}

-       Busy waiting : 프로세스가 특정 조건이 만족 될 때까지 반복해서 확인하는 동기화 기술이다. CPU자원을 소모할 수있다. 

 

10.  Busy waiting (=spin lock)

-       Waiting 하는동안 loop를 계속 도는 것. While문에서! 짧은시간동안 락이 필요할 때 효율적이다

-       단점 : waiting하는 동안 아무거도 할 수 없다.

-       단점 : CPU 사이클을 소모한다. 

-       대안 : process를 waiting state로 보내서 다른 process와 context switch 할 수 있도록 한다. 

-       장점 : spinlock 동안에는 context switch 가 없다. 짧은 시간에 lock를 기대하면 유용하다. 

-       Tradeoff : context switch time vs spinlock time 중에 유용한걸 선택

 

11.  Semaphore : 자원의 개수가 여러개일때

-       S : integer variable

-       두개의 atomic 한 standard operation이 있다 : wait() , signal()

-       S<=0, S--, S++ 은 atomic operation이므로 hardware support가 일어난다

-       Mutex lock보다 동기화에 대해서 더 정교한 방법이다.

1)     Binary semaphore (=mutex lock)

n  1개의 자원을 다룸

n  S가 0 또는 1

n  Mutex lock과 같다

n  한번에 하나의 스레드만 자원에 접근가능

2)     Counting semaphore

n  여러개의 양의 정수 개수의 자원을 다룸 -> so, 여러 스레드가 동시에 접근 

n  사용가능한 자원의 수를 나타냄

n  주로 producer-consumer에서 사용된다

n  여러 스레드가 동시에 접근할 수 있도록 한다.

Wait (S) { 자원줄이기

          While (S<=0) //자원이 남아있는지 확인

                    ; //busy waiting

                    S--;

          }

 

          Signal (S) { //자원 반납. 늘리기

                    S++;

          }

 

12.  Binary semaphore

-       S = 1 initialized

do {

          wait(S);

          //critical section

          signal(S);

          //remainder Section

} while (true);

 

13.  Problems

1)     Deadlock and Starvation

-       Deadlock : 두 개의 프로세스가 무한정 대기하는 형상

-       Semaphore 사용방식은 서로 간의 상호배제를 보장하지만, 잘못된 순서로 사용되면 deadlock을 유발할 수 있다.

2)     Priority Inversion 우선순위 역순

-       낮은 프로세스가 높은 프로세스가 필요한 자원을 보유하고 있을 때 발생하는 문제

-       Solution : priority-Inheritance Protocol (우선순위 상속 프로토콜)

-       낮은 프로세스에게 높은 프로세스의 우선순위를 상속받아 자원을 해제할 때까지 상속받는다. 그리고 다시 원래의 우선순위를 되찾는다.

3)     Incorrect Use of Semaphores

-       세마포어 연산의 올바른 사용이 쉽지 않다

-       Signal(mutex) .. wait(mutex) : +1 -> -1 => 1이 된다. 상호배제가 위반 되어 여러 프로세스가 동시에 critical section에 진입할 수 있다.

-       Wait(mutex) .. wait(mutex) : -1 -> -1 => -1이 되어 deadlock이 발생한다. 프로세스가 무한히 대기상태

-       Wait(mutex) or signal(mutex) : 둘 중 하나를 생략하면 상호 배제가 위반되거나 데드락이 발생한다. 

 

14.  Semaphore with Block operation

-       Spinlock(busy waiting)을 피하기 위해 사용

-       Block () : S<=0 이면 블록을 사용하여 대기한다. Busy waiting을 하는대신 waiting queue로 넘어가 CPU scheduler가 ready queue에 있는 프로세스를 선택하여 실행한다.

-       Wakeup() : 다른 프로세스가 signal() 연산을 실행하면 (critical section을 모두 사용했다는 의미), blocked 된 process가 다시 시작된다. Waiting queue -> ready queue로 이동

wait (S) {

S.value--;

          if (S.value < 0) {

//기다리지않고 waiting queue로 이동

block(); }

}

          }

 

          signal (S) {

S.value++;

if (S.value <= 0) {

//waiting queue->ready queue

wakeup(P); 

}

}

 

15.  Classical Problems of Synchronization

-       Counting semaphore 기반의 동시프로그래밍을 할 때 발생할 수 있는 문제점

 

1)     Bounded-Buffer Problem : 생산자와 소비자가 한정된 크기의 버퍼를 공유할 때 발생하는 문제. 생산자는 N버퍼가 full일때 waiting, 소비자는 N버퍼가 empty 일때 waiting

n  Semaphore mutex = 1

n  Semaphore full = 0 //buffer에 있는 자원의 수

n  Semaphore empty //buffer에 남아있는 empty slot의 개수

n  full + empty = N

-       producer

wait(empty);

wait(mutex);

signal(mutex);

signal(full);

-       consumer

wait(full);

wait(mutex);

signal(mutex);

signal(empty);

 

2)     Reader-Writer Problem : data 를 동시에 process할 수있는 것이있다. 

-       Reader는 data를 같은 순간에 여러명 reading 할 수있다

-       Writer는 하나의 single writer가 되어야한다. 

n  Data set

n  Semaphore mutex = 1

n  Semaphore wrt = 1 //mutual exclusion

n  Readcount = 0 //reader의 명수 count

-       Writer : write를 진행하는동안 아무거도 실행하면 안된다

Wait(wrt); wrt = 0 기다리기

//CS

Signal(wrt);  wrt = 1

-       Reader : readcount 는 읽는 사람들이 충돌하면 안되기 때문에 mutual exclusion을 보장하기 위해 있다

Wait(mutex);

Readcount++;

If (readcount == 1) //읽는사람이 생겼기 때문에

      Wait(wrt); //write하는 것을 기다린다

Signal(mutex);

//CS

Wait(mutex);

Readcount--;

If (readcount==0)

      Signal(wrt);

Signal(mutex);

 

3)     Dining philosopher problem