인기 검색어

Computer Science/Operating System

6. Process Synchronization

  • -
728x90
반응형

Synchronization

global 자료들을 여러 개의 쓰레드가 동시에 엑세스 할 때 문제가 발생할 수 있음. 결과적으로 공유 자원을 사용하는 과정에서 발생하는 문제라고 생각하면 됨.

Producer Consumer problem (코드 암기)

→ producer와 consumer의 속도가 차이가 나게 되면, 한정된 버퍼 상에서 문제가 발생할 수 있음 (다 차거나, 다 비거나)

→ counter : valid한 변수가 몇 개 있는지

이때, counter를 공유하고 있는 상황

💡
위 자료구조는 원형 큐 자료구조를 활용하고 있음.

만약 producer와 consumer가 서로 다른 cpu에 돌고 있다고 가정

일단 쓰려면 register에 load하는 과정을 거쳐야함

→ 이 결과를 거치면 4가 됨 (non-deterministic)

Synchronization Problem

이런 경우를 race condition 이라고 부름

→ Two or more concurrent processes access a shared resources without any synchronization

이러한 race condition을 해결하기 위해서 등장한 것이 동기화 개념

💡
Synchronization은 공유되는 자료구조에는 반드시 필요하다. 예를 들어 버퍼, 큐, 리스트
  • 단일 CPU에서도 race condition을 고민해야하는가?

    당연히 고려해야 한다. 왜냐하면, 실제로는 kernel는 user space의 맥락에서 돌고 있는 상황이기 때문이다. 예를 들어 system call handler가 돌고 있는 상황에서 interrupt가 들어왔다고 생각해보자. 만약 위 커널이 preemptive kernel이면, interrupt를 먼저 처리하게 된다. 이 과정에서 만약 interrupt handler가 system call handler가 다루고 있던 공유 자원을 건드리면 race condition이 충분히 발생할 수 있다.

Sharing Resources

특정 process(thread)가 system call을 불렀다고 가정해보자, 그러면 커널 모드로 감 (사실 커널의 코드와 데이터는 근본적으로 여러 프로세스와 공유되는 것으로 할 수 있음)

→ 사실 system call handler는 kernel의 데이터를 건드리는 것임

system call handler를 처리하는 도중에 interrupt가 오면 system call handler를 돌리다가 interrupt를 처리함. 만약 근데 interrupt handler가 system call handler가 건드리고 있는 데이터를 건드리게 되면 정말로 문제가 발생할 수 있음.

💡
물론 중간에 interrupt가 와도 현재 돌고 있는 kernel process의 preemptive를 허용하지 않을 수 있다.(Non-preemptive kernel) 하지만, 현재 대부분의 OS는 preemptive kernel이므로 interrupt를 우선적으로 처리한다.
  • 왜 preemptive kernel이 선호되는가?
    1. Responsive : 무작정 막기엔 time-consuming
    1. suitable for real-time programming
Critical Sections
  • Definition

    코드 영역 중 공유 데이터를 사용하는 부분

특정한 코드가 global variable를 쓸 때 (즉 critical section을 실행시킬 때), 안전한 방법은 자기만 쓸 수 있게끔 하는 것이다. 즉 다른 프로세스가 critical section을 실행시키는 것을 허용하지 않아야 한다.

entry section ~ exit section : 이 부분에는 해당 process만 쓰겠다.

→ 그래서 어떻게 효율적으로 처리할 것인가 (병렬성이 있는 도중에 직렬화(Serialization) 시키는 개념이라고 생각할 수 있음. 왜냐하면 성능이 떨어지기 때문임)

사실, 얼마나 막을 것인지는 코더의 실력에 의해서 관여됨 (해당 부분 정도만 막아도 괜찮다는 것을 판단을 해야하는 문제 때문에)

→ 그래서 entry랑 exit를 만드는 것이 목표

Requirements for Solution to Critical Sections (매우 중요)

좋은 동기화 primitive의 조건

  1. Mutual Exclusion
  1. Progress : critical section에 어떤 프로세스도 진입하지 않았다면, critical section에 들어가고자 하는 프로세스는 들어갈 수 있어야 한다.
  1. Bounded Waiting : 특정 process가 critical section에 들어오고 싶다면, 언젠가는 들어올 수 있어야 한다. 즉 starvation problem이 일어나서는 안된다.
Solutions for critical Sections : Classification
Assumption
  1. 모든 process의 speed는 random이다.
  1. 완전히 process가 랜덤하게 돌아간다고 가정 (순서에 대한 가정을 넣으면 안된다.)
  • Solution

    Entry section과 exit section을 명시함으로써 이를 해결하고자 함

Low-level synchronization primitive : Locks

매우 원초적이고, 동작이 상대적으로 간단함, high-level synchronization을 하기 위한 building block으로 활용됨.

  1. Software-only solutions (spinlock)
    • Dekker’s algorithm, Peterson’s algorithm
  1. Hardware atomic solutions (spinlock)
    • Test-and-set, Swap instructions
  1. Disabling interrupts
    • Prevent context switches
Locks

사용하는 function : acquire , release

→ 초기에는 lock이 풀려있음

→ critical section에 들어갈 때 acquire를 call하고, 나오고 난 후에 release를 call한다.

→ acquire함수는 계속 spin하면서 lock이 되어있는지 여부를 체크함 (문제로 작용)

Software-only Solution 1 : turn only
  1. Mutual exclusion : 보장
    • Proof

      W.L.O.G i번째 프로세스가 critical section을 돌리고 있다고 가정하자. 즉 turn의 값이 i라는 의미이고, critical section이 끝날때까지 turn값은 바뀌지 않는다. 이때, Mutual exclusion이 보장이 안된다는 것은 j번째 프로세스도 critical section을 동시에 돌리고 있다는 말이다. 즉 turn이 j라는 의미이다. 하지만, turn은 i와 j 동시에 성립할 수 없으므로 모순이다.

  1. Progress : 안됨 (만약 상대방이 안주면 내가 못씀)
    • Counter example

      만약, 프로세스 i가 critical region을 수행하고 나온 상황이라고 가정하자. 그러면 turn값이 결과적으로 j로 변동될 것이다. 만약 j가 critical region을 원하지 않고, i가 critical region을 지속적으로 원하는 상황이라고 할 때, critical region은 비어있음에도 불구하고 process i는 진입하지 못하는 문제점이 발생한다.

  1. Bounded waiting : 보장
    • Proof

      프로세스가 2개만 있는 상황이고, critical section을 빠져나오면서 turn을 상대방에게 반드시 넘기므로 특정 프로세스가 다른 프로세스에 비해 압도적으로 바꿔도 한번씩 순환적으로 처리되는 것을 보장할 수 있다.

💡
Key idea : 상대방이 턴을 가지고 있는지를 critical section에 들어가기 전에 확인하고, 자기가 critical section을 나오면서 턴을 상대방에게 넘긴다.
Software-only Solution 2 : flag only
  1. Mutual exclusion : 보장
    • Proof

      W.L.O.G process i 가 critical region을 돌고 있는 상황이라고 가정하자. (i.e. flag[i] = true, flag[j]가 진입당시에는 false) 만약 이 상황에서 Mutual exclusion이 깨지는 상황은 process j도 critical region에 있는 경우가 유일하다. 그러려면 flag[i]가 false여야 한다. 하지만, flag[i]는 process i 가 critical region을 도는 동안에는 절대로 false로 바뀌지 않으므로 모순이다. 따라서 Mutual exclusion이 보장된다.

  1. Progress : 안됨
    • Counter example

      예를 들어, 현재 critical section을 돌리고 있는 프로세스는 존재하지 않고, process i가 flag[i]를 true로 변경시키고, 그 다음에 process j 가 flag[j]를 true로 변경시켰다고 가정하자. 그러면 그 다음에 둘 중 어느 process가 실행되더라도 더이상 진행되지 않는다. 따라서 어떠한 process도 critical section에 존재하지 않음에도 불구하고, 진입하지 못하는 경우가 충분히 존재할 수 있다.

  1. Bounded Waiting : 보장
    • Proof

      만약 process i와 j가 동시에 critical section 사용을 원하는 경우, 결과적으로 i와 j는 무조건 번갈아 가면서 쓸 수 밖에 없다. 현재 critical section을 process i가 돌리고 있고, process j가 critical section을 쓰기 위해 spinning 하고 있는 상황이라고 가정하자. bounded waiting 이 보장이 안된다는 말은 process i 가 지속해서 critical section을 실행시킬 수 있다는 말이다. 즉 그러기 위해서는 flag[j]가 false여야 한다. 그러나 process j는 spinning하고 있는 상황이므로 flag[j]는 반드시 true이다. 따라서 모순이다.

💡
Key idea : 상대방이 깃발을 안들고 있을 때만 critical section에 진입할 수 있고, critical section을 나오면서 자신의 flag를 false로 바꾼다.
Software-only Solution 3 : Peterson’s algorithm (mixed version)
  1. Mutual exclusion : 보장
    • Proof

      W.L.O.G process i가 critical region 부분의 코드를 돌리고 있다고 가정하자.(즉 진입당시에 flag[j]가 false이거나 turn이 i여야 한다.) Mutual exclusion이 안되는 경우는 process j또한 critical region을 돌리고 있어야 한다. 그러기 위해서는 flag[i]가 false이거나 turn이 j여야 한다. 가정에 의해서 flag[i]는 process i가 critical region이 끝날때까지 true가 보장이 되므로 turn이 j라는 의미이다. 하지만 turn은 i와 j 동시에 성립할 수 없으므로 모순이다.

      💡
      만약 process i와 process j가 거의 비슷하게 critical region을 접근하려고 한다고 가정해보자. 우리는 일반성을 잃지않고 process i가 turn을 j로 먼저 바꾼 이후, process j가 turn을 i로 바꿨다고 가정할 수 있다. 그렇게 되면 결과적으로 먼저 도착한 process가 먼저 critical region에 진입하게 된다.
  1. Progress : 보장
    • Proof

      크게 보면 2가지 경우를 생각해볼 수 있다. 첫번째로는 process 1개만 critical region 접근을 원하는 상황과, 두번째로는 두 process 모두 접근을 원하는 경우이다. 하나씩 살펴보도록 하자. (물론 당연히 현재 critical section을 쓰고 있는 process는 존재하지 않는다.)

      일반성을 잃지 않고, process i만 critical region에 접근하는 상황이라고 가정해보자. 이때, 현재 critical section을 쓰고 있는 process가 없고, process j는 critical region에 접근하려고 하는 상황이 아니므로 flag[j]는 false가 된다. 따라서 process i는 critical region에 정상적으로 진입할 수 있다.

      반대로, 두 process 모두 critical region에 접근을 원하는 케이스도 살펴보도록 하자. 앞서 mutual exclusion에서 살펴본 것처럼 어떠한 케이스에서도 turn값은 슈뢰딩거 고양이처럼 i이면서 j일 수 없다. 따라서 둘 중 하나의 process는 반드시 critical region에 진입할 수 있다.

  1. Bounded Waiting : 보장
    • Proof

      W.L.O.G 현재 process i가 critical section을 실행하고 있고, process j가 critical section을 돌리기 위해서 spinning하고 있는 상황이라고 가정하자. process i가 critical section을 나오게 되면 flag[i]는 true로 바뀌게 된다.

      만약 process i를 돌리고 있는 processor가 process j를 돌리고 있는 processor보다 느리다면 flag[i]가 true로 바뀜에 따라 process j가 critical section에 들어갈 수 있는 것은 쉽게 보일 수 있다. 하지만 만약 process i를 돌리고 있는 processor가 process j를 돌리고 있는 processor보다 압도적으로 빨라서 미처 process j가 while condition을 돌리기 전에 다시 critical section에 진입할 수 있는지를 체크해봐야 한다.

      사실 결론적으로 불가능하다. 왜냐하면 그게 가능하다고 가정 했을 때, 결과적으로 flag[i] = true, flag[j] = true, turn = j일 것이다. 그렇게 되면 process i는 spinning할 수 밖에 없고, 다음으로 critical section 영역을 진행하게 되는 것은 반드시 process j라고 보장할 수 있게 된다.

💡
Key idea : flag condition과 turn condition은 Progress를 보장할 수 없다. 따라서 2개를 동시에 써서 progress 조건을 추가적으로 만족하자는 것이 핵심이다.
💡
주의 : Figure 6.4에서 볼 수 있는 것처럼, flag[i] := true와 turn := j의 순서를 절대로 바꾸면 안된다. 손부터 들어야 한다(현대 컴퓨터 아키텍쳐에서는 성능을 높이기 위해서 processor나 compilor가 dependency가 없는 데이터들을 reorder하는 부분 때문에 Peterson’s Algorithm은 반드시 동기화 문제를 현대 컴퓨터 아키텍쳐 상에서는 보장할 수 없다. 따라서 HW적인 support가 요구되기 시작함)
Memory Barriers

다중 thread나 processor를 사용하는 경우, memory visibility problem이 나타나게 된다. 즉 어떤 한 코어에서 돌아가고 있는 thread에서 변경한 특정 메모리의 값이, thread에서도 제대로 잘 읽어지는 지에 대한 문제가 발생하게 된다. 해당 문제가 발생하는 이유는 다음과 같다.

  1. Register와 캐시의 존재 (즉 메인메모리를 바로 쓰는 개념이 아니다보니 문제가 발생할 수 있다.)
  1. 컴파일러 차원에서의 최적화

이러한 문제를 해결하기 위해서 등장한 개념이 Memory Barrier 이다. Memory Barrier를 만나게 되면 그전까지의 CPU안에 있는 레지스터와 캐쉬값의 변경을 메인메모리에 반영하게 된다.

  • 그래서 위 개념이 동기화 개념과 무슨 관련이 있는가?

    동기화를 위한 Lock을 사용하는 곳에서는 암시적으로 메모리 장벽이 설치된다. Lock이라는 것도 결국 Lock을 소유하는 코어가 특정 메모리에 표시를 해 두면, 다른 코어가 그 값을 보고 자신이 Lock을 소유할 수 없다는 것을 판단해야 하기때문에, lock을 위한 메모리를 읽고 쓰는 과정에는 memory barrier가 필수적으로 요구된다.

    또한 추가적으로 앞서 언급한 것처럼 컴파일러는 최적화 작업을 수행하면서 reordering을 진행하게 되는데, memory barrier를 걸어두면 Peterson’s Algorithm과 같은 문제들을 명시적으로 막을 수 있게 된다.

Hardware Atomic Solutions

등장 배경 : 하드웨어적으로 하면 보다 쉽게 동기화 문제를 해결할 수 있고, 앞서 살펴본 것처럼 Peterson’s algorithm은 현대 computer architecture 상에서는 한계가 분명히 있다.

→ atomic 이라는 instruction을 HW 차원에서 제공 (이를 통해 HW적으로 Mutual exclusion을 제공할 수 있게됨)

  • Test and Set, Swap
💡
Atomic이라는 것은 un-interruptible unit이다. 즉 한번에 처리한다는 것을 하드웨어 차원에서 보장해주는 것이다.
Hardware Atomic Solution 1 : Test and set
💡
return value : 초기 lock값
  • Case 1 : 현재 critical section을 쓰고 있는 process가 없음 (lock값이 false)

    → lock값을 1로 변경시키고, Test-and-Set(lock)의 return 값은 0이므로 critical section에 진입

  • Case 2 : 현재 critical section을 쓰고 있는 process가 있는 경우 (lock값이 true)

    → lock값을 1로 업데이트하지만, 기존의 lock값도 1이기 때문에 Test-and-Set(lock)의 return 값은 1이기 때문에 게속 spinning하게 된다.

💡
이때, Test-and-Set() 함수는 atomically하게 돌아간다는 점을 명심해야 한다. 즉 함수 내부에서의 저 2줄은 한번에 실행되게 된다.
  1. Mutual exclusion : 보장 (하드웨어적으로 보장해줌)
  1. Progress : 보장
    • Proof

      Atomic하게 돌아가는 상황이고, software한 접근과 달리 서로 turn을 주고받는 상황이 아니기 때문에 쓰고 있는 process가 아니라면 critical section에 접근할 수 있다.

  1. Bounded waiting : 안됨
    • Proof

      예를 들어 일반성을 잃지 않고 현재 critical section을 process i 가 쓰고 있고, critical section을 쓰기 위해 process j가 spinning하고 있다고 가정하자. 이때, 만약 process i가 돌고있는 processor가 압도적으로 빠르다면 lock을 풀고 바로 다시 풀려있는 lock을 다시 잡아 critical section에 진입하는 것이 가능하다. 따라서 Bounded waiting을 보장할 수 없다.

Hardware Atomic Solution 2 : Swap
💡
아이디어 자체는 Test and Set과 완전히 동일하다. lock 값을 무조건 true로 업데이트하고, 기존에 lock에 있는 값을 기준으로 critical section에 진입가능 여부를 판단한다.
Problems with Lock

하드웨어적으로 구현을 하든, 소프트웨어적으로 구현을 하든 spinning하는 작업이 수반된다. 이 과정에서 자원을 낭비하게 된다. (spinning하는 작업도 cpu가 계속 해당 process의 무의미한 작업을 계속 수행하는 것이기 때문이다.)

Disabling Interrupts

예를 들어 단일 cpu에서 system call handler가 공유 데이터를 쓰고 있는 도중에 interrupt가 왔다고 가정해보자. 만약 해당 interrupt handler가 system call handler가 수정하고 있던 공유 데이터를 쓰려고 하면 문제가 발생

사실 이러한 문제는 critical section에 대한 문제는 단일 코어에서는 공유 자원을 접근하고 있는 동안 interrupt를 막아버리면 해결할 수 있다.

  • Problem
    1. kernel 내부에서만 동기화 문제를 해결할 수 있다.
    1. Kernel의 responsiveness가 많이 훼손된다.
    1. Multi-processor의 경우 위와 같은 방법으로 해결할 수 없다. (여러 프로세서가 있는 상황이므로 다른 프로세서에서 공유 데이터를 건드리면 여전히 문제가 발생한다.)
💡
사실 단일 프로세서의 경우에는 현실적으로 interrupt를 막는 방법만 사용할 수 있다. 둘 중 하나의 쓰레드만 돌 수 있는 상황이라는 점을 잘 생각해보자. 그래서 Linux kernel의 경우, 멀티프로세서만 spin lock을 사용한다.
High-level synchronization

운영체제 및 PL 차원에서 함수나 자료구조 형태로 프로그래머에게 제공 (Low-level synchronization을 이용해서 구현됨. 즉 atomic하게 진행된다.)

  • Mutex, Semaphore, Monitor, Message passing
Mutex lock (Spin lock)

기존에 하드웨어나 소프트웨어 차원에서 구현했던 것들을 OS차원에서 지원해주는 것이라고 생각해주면 된다.

💡
Busy waiting이 있다는 측면은 Semaphore와 가장 구분되는 것이므로 반드시 기억해두도록 하자.
  • 장점은 없나?

    Context switch를 요구하지 않는다는 점에서는 장점을 가진다.

Semaphore

가질 수 있는 숫자에 따라 2가지의 Semaphore로 구분된다.

  • Binary semaphore

    → Counter value가 1으로 초기화된다.

  • Counting semaphore

    → Counter value가 N으로 초기화 된다. (이 숫자는 해당 unit이 얼마나 사용가능한지와 관련이 있다. 프린터기의 개수정도로 이해해도 된다.)

일단 기본적으로 Mutex lock과 거의 비슷하나, busy waiting이 없고 block된다는 점에서 차이를 보인다.

또한 추가적으로 block된 것을 관리하기 위해 해당 semaphore와 관련된 waiting list를 따로 관리한다.

기본적으로 2가지의 독립적인 operation이 존재함.

wait : critical region에 들어갈 수 있을때까지 block된다. busy wait방식이 아니라는 점에 주의해야 한다.

signal : block된 프로세스가 critical region에 들어올 수 있게끔하는 역할을 수행함

→ 사실상 semaphore가 깃발 역할을 수행하는 것에 불과하다.

→ wait은 값이 1 이상이면 통과시키고

→ signal은 값을 1 증가시키는 역할을 수행시킨다.

💡
S.value도 공유 변수이기 때문에 이것도 동기화에 대한 문제가 발생한다. 이를 해결하기 위해 low-level에서의 spinlock 등을 사용하게 된다. (이러한 측면에서 semaphore가 아얘 busy waiting이 없는 것은 아니지만, 상대적으로 엄청 작은 편이다.)

추가적으로 semaphore는 process의 순서를 제어하는데에도 사용될 수 있다.

만약 A가 B보다 무조건 먼저 실행되게끔하고 싶은 상황이라고 가정하자. 그러면 counter value를 0으로 초기화해주고 다음과 같은 템플릿을 사용해주면 된다.

  • 단점은 없는가?

    기능이 굉장히 강력하기 때문에 dead-lock이 발생할 수 있다.

    대표적으로 Dining-Philosophers problem이 있다.

    위 문제의 경우 semaphore를 써도 dead-lock에 걸릴 수 있다. (예를 들어 전부 다 왼쪽 젓가락을 드는 경우)

Problems with Semaphore
  1. 기본적으로 Semaphore는 global variable이라는 점에서 문제가 발생할 수 있다.
  1. critical section과 process 순서 제어를 모두 할 수 있다는 점에서 너무 강력하다.
  • 만약 semaphore를 통해 critical region에 접근했는데, 이 과정에서 wait()처리가 되면 어떻게 되는가?
    void* producer(void* args){
	while(1){
		int x = rand() % 100;
		sem_wait(&buffer_full);
		sem_wait(&buffer_access);
		buffer[counter] = x;
		counter++;
		sem_post(&buffer_access);
    // buffer가 비었을 때 producer가 먼저하게 강제
		sem_post(&buffer_empty);
		printf("producer value : %d\n", x);
		sleep(1);
	}
}

    예를 들어 sem_wait(&buffer_full)을 수행해서 현재 semaphore인 buffer_full의 value가 1이상이면 해당 값을 1 감소시키고 다음 줄을 계속 실행하게 된다. 그런데 만약 sem_wait(&buffer_access)에 의해 wait 상태에 들어가게 되면 어떻게 되는가?

    문제가 발생한다. 극단적으로 buffer_full이 binary semaphore인 경우 다른 process들이 buffer_full semaphore를 이용하지 못하는 문제가 발생한다.

Critical Region

부정확한 semaphore의 이용이 문제를 발생시킬 수 있음. 조금 더 추상화가 필요해지게 됨에 따라 등장한 개념.

→ critical region을 쓰고 있는 다른 process가 없으면 접근이 가능하도록 하자.

Monitors

PL 차원에서 지원해주는 것. 기본적으로 모니터 안에는 한번에 1개의 process만 들어갈 수 있고, 동기화나 공유 데이터에 대한 보장은 monitor차원에서 해주는 것. 또한 condition variable을 두고 있어서 더이상 진행할 수 없을 때 사용한다. Wait queue방식으로 관리된다.

예시) Bounded Buffer with Monitors

Synchronization in Pthreads

Condition 변수와 Mutex를 같이 써서 monitor처럼 쓰는 것

Message Passing

프로세스간 소통 방식으로 일반적으로 사용되는 방법이다. 이것을 활용해서 2개의 process들의 order를 컨트롤하는 것이 목표.

sender와 receiver를 각각 synchronous, asynchronous 총 4가지 조합이 가능. 일반적으로는 sender 입장에서는 받았는지 여부를 체크하지 않고 진행하는 것이 자연스럽고, receiver 입장에서는 해당 정보를 받을 때까지 block되어있는 것이 자연스럽다. 물론 다른 형태의 조합도 충분히 가능하다.

2개의 primitive가 존재한다.

  • send(destination, message)
  • received(source, message)
반응형
Contents

당신이 좋아할만한 콘텐츠

댓글 0

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.

SHARE

DARK

MENU

티스토리툴바