동시성과 병렬성

 

순차성 / 동시성 / 병렬성

 

"Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once."

- Rob Pike, Concurrency is not Parallelism

 

# 동시성 (Concurrency)

싱글코어 시스템에서 멀티 스레드(혹은 다중 작업)를 처리하는 방식. 사실은 여러 개의 스레드들이 번갈아 가면서(Context Switching) CPU를 점유하며 조금씩 각자의 작업을 실행하는 것이지만 사용자 입장에서는 각 스레드가 병렬적으로 실행되는 것 처럼 보임. 논리적 관점에서의 멀티테스킹

 

# 병렬성 (Parallelism)

멀티코어 시스템에서 멀티 스레드(혹은 다중 작업)를 처리하는 방식. 실제로 한 번에 여러 스레드가 실행됨. 물리적 관점에서의 멀티테스킹

---

# 동기 (Synchronous)

 

 

동기식 처리 모델

 

메소드를 호출하는 Caller가 다음 로직으로 진행하지 못하고 호출한 메소드에서 Return value나 Exception을 받기 전까지 대기(Blocking)하는 것.

 

# 비동기 (Asynchronous)

 

 

비동기식 처리 모델

 

메소드 호출 후 Return value나 Exception을 받을 때 까지 대기하지 않고 다음 작업을 실행하는 것. 메소드의 종료(또는 리턴)은 Callback, Message, Future 등의 동기식 처리와는 다른 방법으로 받게 됨.

위 그림에서는 Task1이 호출된 이후 Call Stack에 쌓이고, Get Data from Server가 호출된다. 이때 이 함수의 콜백함수는 바로 실행되지 않고, 서버에서 요청한 데이터에 대한 응답이 올 때 까지 대기하다가 응답을 받은 후 Task Queue로 이동한다. 이후 Call Stack이 비워지면 다시 Call Stack으로 이동하여 실행된다. (Task2 -> Get Data from Server -> Task1)

대표적으로 자바스크립트의 Timer 함수(setTimeout(), setInterval()), Ajax 등이 비동기식 처리 모델로 동작함.

---

# 프로세스 (Process)

컴퓨터에서 실행되고 있는 프로그램. OS(유닉스 계열 한정)는 포크*(Fork)를 통해 프로세스를 만든다.

각 프로세스는 독립적인 스택과 데이터 영역을 가짐. -> 따라서 프로세스 간 데이터 공유가 어렵고, 권장되지 않음.

프로세스 간 통신을 위해서는 IPC(Inter Process Communication)를 통해서 가능.

프로세스가 시작될 때는 OS로부터 PCB**와 메모리 공간을 할당 후 초기화하는 과정이 필요.

OS 스케줄링에 의해 프로세스의 실행 순서를 결정

생성(Create), 실행(Running), 준비(Ready), 대기(Waiting/Block), 종료(Terminated) 중 하나의 상태를 가짐

Context Switching 시 레지스터의 교체 뿐만 아니라 CPU와 RAM 사이의 캐시 메모리에 대한 데이터를 초기화해야 하므로 오버헤드가 큼.

 

* Fork: 커널단에서 구현된 시스템 콜의 일종으로 프로세스를 복사하는 방식으로 새로운 프로세스를 생성한다.

**PCB(Process Control Block): 커널단의 자료구조로, 프로세스의 식별자, 상태, 프로그램 카운터, 레지스터가 저장됨

# 스레드 (Thread)

하나의 프로그램(프로세스) 내부에서 실행되는 흐름의 단위. OS 스케줄러의 최소 단위.

스레드별로 하나의 스택을 가지지만, 같은 프로세스 내의 다른 스레드와 데이터 영역과 코드 영역을 공유함 -> 스레드 간 공유 변수를 통해 쉽게 통신할 수 있지만, 한 스레드가 비정상 종료될 경우 같은 프로세스 내의 스레드들이 모두 영향을 받음.

동일한 데이터 영역을 공유하므로 Race Condition*, 또는 Dead Lock** 발생 우려가 있음.
일반적으로 New, Runnable, Waiting, Timed_Waiting, Block, Terminated 중 하나의 상태를 가짐

프로세스에 비해 Context Switching 시에 발생하는 오버헤드가 적음.

 

*Race Condition: 다수의 스레드(혹은 프로세스)가 동기화(Synchronizatoin) 메커니즘 없이 공유된 자원에 접근하려고 하는 상황.

**Dead Lock: 다수의 스레드(혹은 프로세스)가 Lock을 획득하기 위해 대기하는 상태에서, 이미 Lock을 획득하여 작업 중인 스레드(프로세스)도 또다른 Lock을 획득하기 위해 대기하며 서로 Block 상태에 놓이는 것.

 

# 코루틴 (Coroutine)

비동기(Asynchronous) 처리의 일종으로, 서브 루틴을 일시 정지(Suspend)하고 재개(Resume)할 수 있는 함수.

I/O Bound 작업과 같이 단순히 하나의 작업을 처리하기 위해 대기해야 하는 시간이 긴 작업에서, 대기 시간동안 다른 작업을 먼저 처리함으로써 CPU의 Idle time을 최소화 할 수 있다.

별도의 스레드 없이 하나의 스레드(주로 메인 스레드) 상에서 번갈아가면서 작업을 진행하며, 병렬처리와 유사한(동시성) 효과를 낼 수 있다. -> Race Condition을 걱정할 필요가 없음

작업 단위가 Object(Coroutine)이므로 힙 영역에 적재됨.

커널에 의한 Context Switching을 통해 동시성을 보장하는 스레드와 달리, 개발자가 코드 안에서 Switching 할 곳을 마음대로 정할 수 있음. -> OS단의 Context Switching이 불필요하기 때문에 작업 전환시 스레드보다도 오버헤드가 적음.

병렬성 처리가 아닌 동시성 처리이기 때문에 멀티코어 활용은 불가능

※ 코루틴은 스레드의 대체재가 아닌 Thread 안에서의 작업 흐름을 더 작게 쪼개어 사용할 수 있도록 해 주는 개념임.

---

# 경쟁 상태 (Race condition)

다수의 스레드 혹은 프로세스가 공유된 자원에 동시에 접근할 때, 접근 순서에 따라서 개발자가 의도하지 않은 결과가 도출될 수 있는 상황. 하나의 공유된 자원을 두고 경쟁(Race) 한다고 하여 Race condition 이라고 한다.

 

# 생산자-소비자 문제 (Producer-consumer problem)

유한 버퍼 문제(Bounded-buffer problem)라고도 하며, Race condition을 효과적으로 보여주는 예시이다.

• 생산자(Producer)는 자원을 생산하여 버퍼(Buffer)에 넣는다.

• 소비자(Consumer)는 버퍼에 있는 자원을 꺼내서 소비한다.

-> 버퍼가 가득 차면 생산자는 자원을 더 이상 넣을 수 없고, 버퍼가 비어 있으면 생산자는 소비할 수 없는 문제가 발생한다.

 

# 동기화 (Synchronization)

한정적인 자원에 여러 스레드(혹은 프로세스)가 동시에 접근하여 로직의 흐름이 꼬이는 것을 방지하기 위해 스레드(혹은 프로세스)들에게 하나의 자원에 대한 처리 권한을 주거나 순서를 조정해주는 기법. 주로 Mutex, Semaphore, Monitor와 같은 기법으로 구현된다.

# 임계 영역 (Critical Section)

공유된 자원에 접근하는 프로세스 혹은 스레드의 코드 안에 정의된 영역으로, 한 프로세스가 임계 영역의 접근 권한을 얻어 작업을 수행중일 때, 다른 프로세스가 임계 영역에서 작업을 수행한다면 앞서 설명한 유한 버퍼 문제와 같은 오류가 발생함. 쉽게 말해 동기화가 필요한 영역. 생산자-소비자 문제에서 버퍼가 임계 영역에 해당한다.

# 상호 배제, 뮤텍스 (Mutex, Mutual Exclusion)

공유된 자원의 데이터를 다수의 스레드가 동시에 접근하는 것을 방지하는 기법.

Locking/Unlocking을 사용하려 임계 영역에 접근하는 스레드는 Lock을 획득한 후 접근할 수 있고, 임계 영역을 벗어난 이후에는 Unlocking을 통해 이전에 획득한 Lock을 반환하는 원리로 동작한다.

Lock은 주로 Boolean의 형태로 구현됨. -> Lock은 획득(Aquire)할 수 있음.

Lock을 소유한 스레드만이 Lock을 해제할 수 있음

※ 동기화 대상이 하나일 때 사용

 

# 세마포어 (Semaphore)

공유된 자원의 데이터를 다수의 프로세스가 동시에 접근하는 것을 방지하는 기법.

OS 또는 커널 내부의 값으로서, 프로세스는 이를 확인하고 변경할 수 있음.

프로세스가 확인한 세마포어 값에 따라 해당 프로세스는 즉시 자원을 사용할지, 이미 자원을 사용중인 프로세스가 종료되기를 기다릴지 결정함.

세마포어는 주로 INT의 형태로 구현됨. -> 세마포어는 획득하는 것이 아닌 카운터를 증가시키는 것.

이진 세마포어(Binary Semaphore)의 경우 뮤텍스와 유사하게 동작함.

세마포어를 증가시키지 않은 프로세스도 세마포어를 해제할 수 있음.

※ 주로 동기화 대상이 하나 이상일 때 사용

 

# 모니터 (Monitor)

상대적으로 고급 언어들에서 지원하는 기법으로, 뮤텍스와 동일하게 상호배제를 함으로써 임계영역에 하나의 스레드만 접근할 수 있도록 한다.

뮤텍스는 프로세스 간 동기화에도 사용할 수 있지만, 모니터는 하나의 프로세스 안에 있는 다수의 스레드 간의 동기화에 사용된다.

프레임워크나 라이브러리 단에서 제공되므로 뮤텍스에 비해 좀 더 가볍고 빠르다.

 

https://stackoverflow.com/questions/7335950/semaphore-vs-monitors-whats-the-difference

Semaphore vs. Monitors - what's the difference?

# 교착 상태, 데드락 (Dead Lock)

 

Dead Lock

 

먼 길 - 윤석중

아기가 잠드는 걸
보고 가려고

아빠는 머리맡에
앉아 계시고.

아빠가 가시는 걸
보고 자려고

아기는 말똥말똥
잠을 안 자고.

OS 혹은 프로그램의 잘못된 자원 관리로 인해 다수의 프로세스가 서로 자원을 대기하는 교착 상태에 빠져 함께 멈추는 현상.

• 상호 배제 (Mutual Exclusion): 자원은 한 번에 한 프로세스만이 이용할 수 있다.

• 점유 대기 (Hold and Wait): 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스.

• 선점 불가 (No Preemption): 한 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 다른 프로세스에 할당될 수 없다.

• 순환 대기 (Circular Wait): 프로세스 집합 P={P0, P1, ... , Pn}에서 P0는 P1이 점유한 자원을 대기하고, Pn은 Pn+1의 자원을, Pn은 P0가 점유한 자원을 점유하기 위해 대기한다.

위 4가지 조건이 모두 만족되었을 때, 데드락이 발생할 수 있다. 따라서 네 가지 중 하나라도 부정으로 만들면 교착 상태를 해결할 수 있고, 교착 상태를 탐지하고 회복(Dijkstra의 은행원 알고리즘)하는 방법도 있지만 이들은 비용이 많이 드는 작업이기 때문에 대부분의 시스템에서는 교착 상태를 무시하고 사용자가 직접 해결(재부팅 등)하도록 둔다.