4. 프로세스 동기화

동기 vs 비동기

동기와 비동기를 구분하는 기준은 작업 순서이다. 동기식 모델은 모든 작업들이 순서를 따르며 그 순서에 맞게 동작한다. 즉 A,B,C순서대로 작업이 시작되었다면 A,B,C순서로 작업이 끝나야 한다. 설령 여러 작업이 동시에 처리되고 있다고 해도, 작업이 처리되는 모델의 순서가 보장되면 이는 동기식 처리 모델이라고 할 수 있다.

 

반면 비동기식 모델은 작업의 순서가 보장되지 않는다. A,B,C순서로 작업이 시작되어도 A,B,C 순서로 작업이 끝난다고 보장할 수 없다. 비동기식 처리 모델이 이득을 보는 경우는 각 작업이 분리될 수 있으며, Latency(내부지연시간)가 큰 경우이다. 예를들어 각 클라이언트 또는 작업별로 Latency가 발생하는 네트워크 처리나 파일 입출력등이 훌륭한 적용 예시이다.

 

*Latency: 운영체제가 언제 프로세스를 수행시킬지에 대한 스케줄링을 적용한다. 이를테면 프로세스가 컴퓨터카드의 전압 출력을 high - low - high - low로 설정함으로써 1000Hz의 속도를 내도록 명령을 내린다고 치자. 운영체제는 내부시계를 기반으로 각 변화( high - low 또는 low - high)가 생길때 스케줄링의 수정을 선별할 수 있다. 레이턴시는 이러한 변화를 명령하는 프로세스 명령과 전압을 실제로 변화시키는 하드웨어 간의 지연을 의미한다.

 

프로세스 동기화 (Process Synchronization)

협력하는 프로세스 사이에서 실행 순서 규칙을 정하여 공유 자원의 일관성을 보장하는 것

프로세스가 서로 협력하며 공유 자원을 사용하는 상황에서, 경쟁 조건이 발생하면 공유 자원을 신뢰할 수 없게 만들 수 있다. 이를 방지하기 위해 프로세스들이 공유 자원을 사용할 때 특별한 규칙을 만드는 것이 프로세스 동기화이다.

 

경쟁조건 (Race Condition)

여러 프로세스(또는 스레드)가 공유 자원에 동시에 접근할 때, 공유 자원에 대한 접근 순서에 따라 실행 결과가 달라질 수 있는 상황

 

임계구역 (Critical Section)

여러 프로세스(또는 스레드)가 자원을 공유하는 상황에서, 하나의 프로세스(스레드)만 접근할 수 있도록 제한해둔 코드 영역

 

	do {
	// Entry Section
	// Critical Section
	// Exit Section
	// Remainder Section
	} while (true);

view raw CriticalSection.cpp hosted with ❤ by GitHub

반응형

동기화와 관련한 고전적인 문제

은행 계좌 문제 ( Bank Account Problem)

부모는 은행 계좌에 입금을 한다. 자식은 은행 계좌에서 출금한다.

입금과 출금 과정이 별도로 이루어져야 한다.

Critical section: 은행 계좌

 

독자 저자 문제 (Readers Writers Problem)

독자는 책(공유 데이터베이스)에 쓰여있는 글을 읽는다. 저자는 책에 글을 써서 추가한다.

독자가 글을 읽고 있다면, 독자는 추가적으로 글을 읽을 수 있지만, 저자는 글을 쓸 수 없다.

저자가 글을 쓰고 있다면, 독자는 글을 읽을 수 없으며, 저자 또한 추가적으로 글을 쓸 수 없다.

Critical section: 책 (공유 데이터베이스)

 

생산자 소비자 문제 (Producer Consumer Problem)

한정 버퍼 문제 (Bounded Buffer Problem)이라고도 한다.

생산자는 물건을 생산하여 창고(버퍼)에 넣는다. 소비자는 창고에서 물건을 꺼내서 소비한다.

창고가 가득 차면 생산자는 물건을 넣을 수 없고, 창고가 비어 있으면 소비자는 물건을 소비할 수 없다.

Critical section: 창고 (버퍼)

 

식사하는 철학자 문제 (Dining Philosopher Problem)

원형 테이블에 철학자들이 앉아있고 철학자의 수만큼 젓가락이 철학자 사이에 하나씩 놓여있다.

철학자들이 식사를 하기 위해서는 양쪽에 하나씩 놓여있는 젓가락을 둘 다 들어서 사용해야 한다.

어떤 철학자가 젓가락을 사용중이라면, 다른 어떤 철학자는 식사를 할 수 없다.

Critical section: 젓가락

 

임계 구역 문제의 해결 조건

상호배제 (Mutual Exclusion)

어떤 프로세스(또는 스레드)가 임계 구역에서 작업 중일 때, 다른 프로세스는 임계 구역으로 접근할 수 없다.

 

진행 (Progress)

임계 구역에서 작업 중인 프로세스가 없다면, 임계 구역으로 진입하려는 프로세스 중 하나를 적절히 선택하여 임계구역에 진입할 수 있게 해야 한다.

 

유한 대기 (Bounded Waiting)

다른 프로세스의 기아(Starvaion)을 방지하기 위해, 임계 구역에 한 번 접근했던 프로세스는 다시 임계 구역에 들어갈 때 제한을 두어야 한다.

 

임계 구역 문제의 해결 방안

소프트웨어 동기화 방법

피터슨의 알고리즘 (Peterson's Algorithm): 피터슨의 해결안이라고도 하며, 2개의 프로세스만 있을 때 사용할 수 있다.

데커의 알고리즘 (Dekker's Algorithm): 피터슨의 알고리즘과 비슷하며, 2개의 프로세스만 있을 때 사용할 수 있다.

램포트의 빵집 알고리즘 (Lamport's bakery algorithm): 2개 이상의 프로세스에서 사용할 수 있다.

 

	* Peterson Algorithm
	// Shared data
	int turn;
	bool flag[2];
	// Process i
	do {
	flag[i] = true;
	turn = j;
	while (flag[j] && turn == j);
	/* Critical Section */
	flag[i] = false;
	/* Remainder Section */
	} while (true);
	// Process j
	do {
	flag[j] = true;
	turn = i;
	while (flag[i] && turn == i);
	/* Critical Section */
	flag[j] = false;
	/* Remainder Section */
	} while (true);

view raw Peterson's_Algorithm.cpp hosted with ❤ by GitHub

하드웨어 동기화 방법

락(lock)을 이용한 해결 방안이다. 프로세스가 락을 획득해야만 임계 구역에 진입할 수 있고, 임계 구역을  벗어나면 락을 반납하여, 임계 구역 문제를 해결한다.

싱글 프로세서 환경에서는 공유 데이터가 변경되는 동안 인터럽트를 막으면 임계 구역 문제를 해결할 수 있다. 비선점형 커널에서도 이 방법을 사용한다.

하지만 멀티 프로세서 환경에서는 시스템 효율성때문에 인터럽트를 막을 수 없다. 멀티 프로세서 환경에서는 동기화 하드웨어로 임계 구역 문제를 해결할 수 있다. 주로 TestAndSet()과 Swap() 명령어로 이를 구현한다.

 

	* TestAndSet
	bool TestAndSet(bool *target) {
	bool ret = *target;
	*target = true;
	return ret;
	}
	do {
	while (TestAndSet(lock));
	/* Critical Section */
	lock = false;
	/* Remainder Section */
	} while (true);
	* Swap
	void Swap(bool *a, bool *b) {
	bool temp = *a;
	*a = *b;
	*b = temp;
	}
	do {
	key = true;
	while (key == true) Swap(&lock, &key);
	/* Critical Section */
	lock = false;
	/* Remainder Section */
	} while (true);

view raw TestAndSet,Swap.cpp hosted with ❤ by GitHub