Synchronization: The Critical Section Problem(1)

Candidate Solutions

What is the Critical Section Problem?

이전에 이미 언급했듯이, 코드에는 한 번에 한 스레드에서만 실행되어져야 하는 중요한 부분이 있습니다. 이러한 요구사항을 mutual exclusion이라고 합니다. 오직 하나의 스레드나 프로세스만에 공유된 자원에 접근할 수 있는 조건입니다.

멀티스레드 프로그램에서 이러한 critical section(이하 CS)을 mutex lock과 unlock으로 둘러쌉니다.

pthread_mutex_lock() - one thread allowed at a time! (others will have to wait here)
... Do Critical Section stuff here!
pthread_mutex_unlock() - let other waiting threads continue

그렇다면 어떻게 이러한 lock과 unlock call을 수행할까요? mutual exclusion을 보증하는 알고리즘을 만들어볼 수 있을까요? 다음 코드는 잘못된 구현의 예입니다.

pthread_mutex_lock(p_mutex_t *m)     { while(m->lock) {}; m->lock = 1;}
pthread_mutex_unlock(p_mutex_t *m)   { m->lock = 0; }

얼핏 보기에는 코드가 정상적으로 작동할 것 같습니다. 하나의 스레드가 mutex lock을 시도한다면, 다음 스레드는 lock이 해결될 때까지 기다릴 것입니다. 하지만 이러한 구현은 Mutual Exclusion을 만족하지 못합니다. 이 구현을 두 스레드가 동시에 동작하는 관점에서 좀 더 자세히 살펴봅시다. 다음 표의 순서대로 스레드가 동작한다고 생각해 봅시다.

Time	Thread 1	Thread 2
1	while(lock) {}
2		while(lock) {}
3	lock = 1	lock = 1

위와 같은 경우, race condition이 발생합니다. 이런 불운한 케이스에 두 스레드는 lock을 체크하여 잘못된 값을 읽어옵니다.이런 경우 더이상 진행이 불가능합니다.

Candidate solutions to the critical section problem.

상황을 좀 더 단순화 시키기 위해 2개의 스레드만 존재한다고 가정해봅시다. thread와 process, 고전적인 CS literature에서 동작하는 이러한 인자들은 두 프로세스들이 독점적인 접근을 필요로 하는 CS나 shared memory에 주목합니다.

플래그를 세우는 것은 thread/process의 CS에 진입하는 것을 의미합니다.

아래에 제시될 psuedo-code는 큰 프로그램의 일부입니다. 스레드나 프로세스는 일반적으로 프로세스가 실행되는 동안 여러번 CS에 진입할 필요가 있습니다. 스레드나 프로세스가 임의의 시간동안 동작하는 loop를 둘러싸고 있는 예를 상상해보세요.

아래에 있는 해결책 후보에 문제점이 있을까요?

// Candidate #1
wait until your flag is lowered
raise my flag
// Do Critical Section stuff
lower my flag 

답: 정답 후보 1번은 race condition입니다. 예를 들어, 두 스레드나 프로세스가 각각 상대편의 flag value(l=lowered)를 읽게 된다면 계속 진행이 되어 Mutual exclusion을 만족하지 못합니다.

정답후보 2번은 다른 스레드의 flag를 확인하기 전에 flag를 드는 것입니다.

// Candidate #2
raise my flag
wait until your flag is lowered
// Do Critical Section stuff
lower my flag 

후보 2는 mutual exclusion을 만족합니다. 즉 두 스레드가 동시에 CS에 진입하는 것이 불가능합니다. 하지만 이 코드는 dead lock을 유발할 수 있습니다.두 스레드가 하나의 CS에 동시에 진입하길 원하는 상황을 가정해 봅시다.

Time	Thread 1	Thread 2
1	raise flag
2		raise flag
3	wait ...	wait ...

두 스레드/프로세스는 서로 상대편이 flag를 내리기를 기다리고 있습니다. 둘 다 CS에 진입하지 못하고 영원히 멈추게 됩니다.

이 결과는 누가 진행해야 할지 결정하기 위해 턴 기반 변수를 사용해야 하는 것을 암시합니다.

Turn-based solutions

다음 후보 3번은 turn-based variable을 사용해 한 스레드가 진행하게 하고 그 다음 나머지가 진행됩니다.

// Candidate #3
wait until my turn is myid
// Do Critical Section stuff
turn = yourid

후보 3번은 mutual exclusion을 만족지만, 두 스레드/프로세스가 각각 CS에 진입하기 위해서 엄격한 turn-based approach를 적용해야합니다.예를 들어 교대로 CS에 접근하게 되는 패턴을 사용하도록 강제됩니다. 만약 스레드1이 1밀리세컨드마다 해시테이블을 읽기를 원하고 다른 스레드가 매 초마다 해시테이블에 쓴다면, 해시테이블을 읽는 스레드는 다시 해시테이블을 읽기까지 999ms동안 기다려야 합니다. 이 해결 방법은 현재 CS에 진입한 다른 스레드가 없다면 바로 진행되어 CS에 진입할 수 있어야 하기 때문에 그다지 효과적이지 않습니다.

Desired properties for solutions to the Critical Section Problem?

Criticla Section Problem을 해결하는 방법에는 3가지 주요 특성이 있습니다.

• Mutual Exclusion - 스레드나 프로세스가 독접적인 접근을 얻습니다. 하나가 CS에 진입해 있다면 다른 하나는 이미 진입한 스레드나 프로세스가 CS를 나올 때까지 기다려야 합니다.
• Bounded Wait - 만약 스레드나 프로세스가 기다려야 한다면, 정해진 시간만을 기다려야 합니다.(무한히 기다리는 것이 허용되지 않습니다) bounded wait의 정확한 정의는 주어진 프로세스가 CS에 들어가기 전에 다른 프로세스가 진입할 수 있도록 상한선이 정해져야 한다는 것입니다.
• Progress - 만약 CS안에 스레드나 프로세스가 존재하지 않는다면 기다리지 않고 스레드나 프로세스가 진행되어야 합니다.

이러한 아이디어를 기반으로 두 스레드가 동시에 요청했을 때 turn-based flag를 사용하는 해결책 후보를 생각해봅시다.

Turn and Flag solutions

아래는 CS problem에 올바른 해결책일까요?

\\ Candidate #4
raise my flag
if your flag is raised, wait until my turn
// Do Critical Section stuff
turn = yourid
lower my flag

한 강사와 다른 CS 교수가 그렇게 생각했습니다. 그러나 이 해결책을 분석하는 것은 까다롭습니다. 심지어 특정 주제에 대한 논문도 부정확한 정답을 포함하고 있습니다. 얼핏 봤을 땐 mutual exclusion, Bounded Wait, Progress를 모두 만족하는 것처럼 보입니다. turn based flag는 오직 같을 경우에만 사용되고 mutual exclusion도 만족하는 것처럼 보입니다. 반례를 찾을 수 있을까요?

후보4번은 다른스레드가 flag를 내릴 때까지 기다리지 않기 때문에 실패합니다. 다음 시나리오가 발생해 Mutual exclusive를 만족시키지 못하는 것을 알 수 있습니다.

처음 스레드가 코드를 두번 실행한다고 (turn flag가 두번째 스레드를 가리킴) 생각해봅시다. 첫 번째 스레드가 여전히 CS에 존재하는 중에 두 번째 스레드가 도착합니다. 이 두 번째 스레드는 즉시 CS안으로 진입합니다!

1	2	raise my flag
2	2	if your flag is raised, wait until my turn	raise my flag
3	2	// Do Critical Section stuff	if your flag is raised, wait until my turn(TRUE!)
4	2	// Do Critical Section stuff	// Do Critical Section stuff - OOPS