9. 동시성 제어 (동기 vs 비동기 & Blocking vs Non-blocking) 총 정리

1. 동시성 제어 (Concurrency Control)

• Context-Switch : CPU에서 running 중이던 process를 PCB에 store 하고, 다른 PCB의 register 정보(PC, IR)를 CPU에 load 해오는 상황
• Concurrency-Control : Context-Switch 를 통해서 time-sharing을 함. 즉, 동시성 = 시분할

 

2. Concurrent vs Parallel

• Concurrenct : 시분할
• Parallel : multicore에서 실제 동시에 병렬적으로 실행 Parallelism
  1. data parallelism
  2. task parallelism

 

3. 동기(synchronous) vs 비동기(asynchronous) / blocking vs non-blocking

• Synchronous VS Asynchronous
  • 두 가지 이상의 대상(메서드, 작업, 처리 등)과 이를 처리하는 시간으로 구분한다.
  • Synchronous
    • 호출된 함수의 리턴하는 시간과 결과를 반환하는 시간이 일치하는 경우
    • 함수의 결과를 호출한 쪽에서 처리
  • Asynchronous
    • 호출된 함수의 리턴하는 시간과 결과를 반환하는 시간이 일치하지 않는 경우
    • 함수의 결과를 호출한 쪽에서 처리하지 않는다.
    • 호출되는 함수에게 callback을 전달해서, 호출되는 함수가 전달받은 callback을 실행
• Blocking VS Non-Blocking
  • 호출되는 대상이 직접 제어할 수 없는 경우 이를 구분할 수 있다.
  • Blocking: 호출된 함수가 자신의 작업을 모두 마칠 때까지 호출한 함수를 기다리게 만든다.
  • Non-Blocking: 호출된 함수가 바로 리턴해서 호출한 함수에게 제어권을 준다.

 

4. 동기화 객체의 종류

• 스레드 동기화 방법
  1. 실행 순서의 동기화
     • 스레드의 실행 순서를 정의하고, 이 순서에 반드시 따르도록 하는 것
  2. 메모리 접근에 대한 동기화
     • 메모리 접근에 있어서 동시 접근을 막는 것
     • 실행의 순서가 중요한 상황이 아니고, 한 순간에 하나의 스레드만 접근하면 되는 상황을 의미
• 동기화 기법의 종류
  1. 유저 모드 동기화
     • 커널의 힘을 빌리지 않는(커널 코드가 실행되지 않는) 동기화 기법
     • 성능상 이점, 기능상의 제한
     • Ex) 크리티컬 섹션 기반의 동기화, 인터락 함수 기반의 동기화
  2. 커널 모드 동기화
     • 커널에서 제공하는 동기화 기능을 활용하는 방법
     • 커널 모드로의 변경이 필요하고 이는 성능 저하로 이어짐, 다양한 기능 활용 가능
     • Ex) 뮤 텍스 기반의 동기화, 세마포어 기반의 동기화, 이름있는 뮤텍스 기반의 프로세스 동기화, 이벤트 기반의 동기화

 

 

5. 동기화 관련 문제들

1. busy-waiting → sleep and wakeup으로 해결
2. 생산자 소비자 문제 (Producer-Consumer)
   • 생산자 (producer) : 버퍼에 정보를 삽입
   • 소비자 (consumer) : 버퍼에서 정보를 제거
   • 버퍼가 가득 차 있다면? 생산자를 sleep --> 소비자 수행 후, wakeup
   • count에 대한 접근 → Race-Condition (경쟁 조건) → wakeup signal 분실 가능
   • 해결 : 세마포어 활용
3. 식사하는 철학자들 문제
   • 철학자는 스파게티를 먹기 위해 양옆의 포크를 동시에 들어야 한다.
   • 이때, 전부 왼쪽 포크를 먼저 들면, 오른쪽 포크를 전부 못 들어 무한정 기다리게 된다.
   • 즉, 제한된 수의 자원에 접근하는 문제
   • 동시성 + 데드락 : 여러 프로세스가 동시에 돌아갈 때 교착 상태에 빠지는 원인
   • 해결 : 동시성을 제거 - 필요한 포크가 사용 중이라면, 배고픈 철학자라도 블락된다
4. 독자 저자 문제 (The Readers and Writers Problem)
   • 식사하는 철학자 문제가 I/O와 같이 제한된 수의 자원에 접근하는 문제라면
   • 읽는 자 쓰는 자는 데이터베이스에 접근하는 모델
   • 여러 리더가 존재 가능
   • Reader와 Writer의 배타적 접근
   • 해결 : 뮤 텍스 세마포어
5. 잠자는 이발사 문제
   • 한 명의 이발사, 하나의 이발용 의자, 기다리는 손님을 위한 n개의 의자
   • 손님이 없으면 이발사는 sleep
   • 손님이 오면 이발사는 wakeup
   • 이발 중 손님이 오면 대기용 의자에서 기다림
   • 대기용 의자도 만석이면 손님은 그냥 이발소를 떠남
   • ⇒ 이발사와 손님이 Race-Condition에 빠지지 않도록 하는 것
   • 해결 : 뮤 텍스
     • 한 번에 한 명만이 동작 상태를 바꿀 수 있게 한다.
     • 이발사 : 뮤 텍스 얻어야 대기실 손님 확인 가능
     • 손님 : 뮤텍스 얻어야 이발소 들어갈 수 있음, 대기실 or 의자에 앉으면 뮤텍스 반납
   • 복수의 잠자는 이발사 문제 : 세마포어 필요

 

6. Critical Section (임계 영역)

• 멀티 스레딩에 문제점에서 나오듯, 동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역
• Race Condition을 유발하는 코드 블록
• (e.g. 공유하는 변수 사용, 동일 파일을 사용하는 등)

 

7. Race Condition 이란?

• 공유 자원에 대해 여러 프로세스/스레드가 동시에 접근을 시도하는 상황
• 즉, 하나의 자원을 두고 경쟁하는 것
• 타이밍에 따라서 결과가 다를 수 있어, 자료의 일관성을 해치는 결과가 나타남
• ex) 은행에서 출금하는 스레드 사이에서 발생하는 경우 balance가 덜 줄어듦 → 심각한 문제
  1.  

 

8. Race Condition이 발생하는 경우

• Shared resource에 access 했는데 동기화를 하지 않으면 발생

1. 커널 작업을 수행하는 중에 인터럽트 발생
   • 문제점 : 커널 모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
   • 해결법 : 커널 모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
2. 프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
   • 문제점 : 프로세스 1이 커널 모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )
   • 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
   • 문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
   • 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

 

9. Thread-safe 의미, 구현

• 의미
  • 멀티스레드 환경에서 여러 스레드가 동시에 하나의 객체 및 변수(공유 자원)에 접근할 때, 의도한 대로 동작하는 것
• 구현
  • 결국 동기화
  • 2개의 critical region이 mutual exclusive 하게 수행되도록 막아서, 2개의 thread를 synchronize 하면 Race-condition을 없앨 수 있다.

 

10. Critical Section Problem (임계 영역 문제)를해결하기 위한 조건

1. 상호 배제 (Mutual Exclusion) : 한 프로세스가 임계 구역에 들어가 있으면 다른 프로세스 들어갈 수 없다.
2. 진행 (Progress) : 임계구역에 들어간 프로세스 없다면 어느 프로세스가 들어갈지 적절히 선택
3. 한정 대기 (Bounded Waiting) : 기아 방지를 위해 한 번 들어갔다 나온 프로세스는 다음에 들어갈 때 제한을 준다. - no Starvation

(+) CPU의 속도 등에 대한 어떠한 가정도 하면 안 된다

 

 

11. Mutex (Mutual Exclusive), 상호 배제

• Mutual exclusive 하게 수행하도록 하여 synchronize 하는 것
• 그러므로 Race Condition을 없앤다.
• 화장실이 하나뿐인 식당, 열쇠 1개
• 여러 프로세스/스레드가 공유된 자원에 접근하는 것을 막는 것
• 여러 프로세스가 공유 자원 사용하려 할 때 번갈아 가며 사용하도록 함
• 임계 구역 내에서 인터럽트, 교착상태, 무한반복 발생하지 않도록 해야 함
• 키가 1개인 세마포어라고 볼 수 있다. (이진 세마포어)
• 구현 방법
  • 2개 프로세스 기준 : 데커 알고리즘, 피터슨 알고리즘
  • 여러 개 프로세스 기준 : Lamport의 빵집 알고리즘

 

 

12. Critical Section Problem 해결 방법 4가지

1. Lock
2. Semaphore
3. Monitor
4. Message

 

13. Lock

• 자원을 사용하는 동안 들어오지 못하도록 잠구는 것
• 하나의 자원에 여러 스레드가 동시에 접근하는 것을 조율해준다.

1) 기본형

• 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section에 진입하는 프로세스는 Lock을 획득하고 Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다.

while (lock == 1);
lock = 1;
Critical_region();
lock = 0;

• 한계 : lock 이 0 일 때 두 스레드가 동시에 진입하면 문제!

2) Spin Lock

• busy waiting을 사용한 lock
• 장점 : lock이 해제될 때 context-switching 이 없어서, 오버헤드 없이 critical section 접근 가능
• 단점 : 어떤 스레드가 락을 오래 소유하면, CPU 낭비
• 한계 : Progress를 만족하지 않음 - 010101 번갈아서 들어와야 함 / 000 이면 실행 안됨
• 언제 사용? 멀티-스레드에서 critical section 이 아주 작거나, 빠른 처리 가능할 때

while(True) {
	while (turn != 0);
	Critical_region();
	turn = 1;
	Noncritical_region();
}

 

while(True) {
	while (turn != 1);
	Critical_region();
	turn = 0;
	Noncritical_region();
}

 

3) Peterson's Solution

• 소프트웨어적으로 이 방법을 쓰면 해결 가능하지만, 오버헤드가 크다

4) TSL (Test and Set Lock) instruction

• 하드웨어적으로 제공되는 명령어로 atomic 하게 실행된다.

# 하드웨어에서 이런 명령어를 제공
bool Test_and_Set(bool *flag) {
	bool old = *flag;
	*flag = True;
	return old;
}

lock = false;
repeat
	while Test_and_Set(lock) do no-op;
	Critical Section
	lock = false;
	Remainder Section
until false

• 문제
  • Spin Lock 이기 때문에 CPU를 계속 써야 함 (Lock 값 계속 체크해야 함)

 

 

14. Sleep and Wakeup

• busy-waiting 해결 → 임계 구역 진입이 허용되지 않을 때, CPU 시간을 낭비하는 대신 블록 하는 프로세스 간 통신 고려
  • sleep : 호출자를 block → 다른 프로세스가 깨울 때 (wakeup)까지 보류
  • wakeup
• 발생 문제 : 생산자 - 소비자 문제 (한정된 버퍼 문제)
  • 생산자 (producer) : 버퍼에 정보를 삽입
  • 소비자 (consumer) : 버퍼에서 정보를 제거
  • 버퍼가 가득 차 있다면? 생산자를 sleep --> 소비자 수행 후, wakeup

 

 

15. Semaphore

• 화장실이 여러 개 있는 레스토랑, 열쇠 = 칸 개수만
• 현재 공유자원에 접근할 수 있는 프로세스/스레드 수를 나타내는 값을 두어 상호 배제
• Lock시 특정 수만큼의 카운트를 더하고
• Unlock시 빼주는 형식으로 처리
• 이런 락을 슬립( Sleep ) 가능한 락이라고 함
• Up, Down은 atomic 하게 동작
• 생산자 소비자 문제의 근본적 해결
• 동기화해야 하는 대상이 여러 개일 때 사용

1) 카운팅 세마포어

• 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수로 초기화된다. 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가한다.
• 생산자 소비자 문제와 비교하기
• count 하나로 표현되던 부분들이 up, down을 이용하여 mutex, empty, full로 표현

#define N 100   // 버퍼 용량
int mutex = 1;  // 공유 데이터를 위한 mutex
int empty = n   // 빈 용량
int full = 0    // 찬 용량

void producer(void) {
	int item;

	while(TRUE) {
		item = produce_item();  // item 생성
		down(&empty);           // if 꽉차지 않았으면 empty--;
		down(&mutex);           // mutex = 0 으로 해서, lock 처리
		insert_item(item);      // 버퍼에 추가
		up(&mutex);             // mutex = 1 으로 해서, unlock 처리
		up(&full);
	}
}

void consumer(void) {
	int item;

	while(TRUE) {
		down(&full);
		down(&mutex);
		item = remove_item();  // 
		up(&mutex);
		up(&empty);
		consume_item(item);  
	}
}

2) 이진 세마포어 (MUTEX)

• MUTEX라고도 부르며, 상호 배제의 (Mutual Exclusion)의 머릿글자를 따서 만들어졌다. 이름 그대로 0과 1 사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용한다.

 

16. Monitor

• 동기화를 구현하기 위한 특수 프로그램 기법
• 특정 공유 자원을 프로세스에게 할당하는 데 필요한 데이터와 이 데이터를 처리하는 프로시저로 구성
• 자료 추상화, 정보 은폐 개념을 기초, 병행성 구조
• 상호 배제가 low-level 단에서 지원됨
• → "단 하나의 프로세스만 한 순간에 모니터에서 활동할 수 있다."
• 생산자-소비자 문제 해결
  • 조건 변수 wait, signal 도입
  • sleep, wakeup과 달리 모니터에서는 자동적으로 상호 배제가 됨→ 문맥교환 될 걱정하지않고 연산 완료 가능
  • → wait, signal은 상호배제가 아님

 

17. Message Passing

• send / receive ; 시스템 호출 일종
• acknowledgement 분실 문제 -> 메시지 구별 필요
• 인증 --> 프로세스의 유일성 보장
• 생산자 - 소비자 문제
  • 공유 메모리가 아닌, 메시지 전달로 해결
  • 가정
    1. 모든 메시지는 동일한 크기
    2. 메시지는 운영체제에 의해 자동 버퍼링
  • 방법
    1. 소비자는 시작할 때, N개의 빈 메시지를 생산자에게 보냄
    2. 생산자는 소비자에게 전달할 아이템을 생산하면, 빈 메시지 수신 → 아이템이 들어 있는 메시지 전송