SP - 5.2 Semaphore Synchronization (1)

  지난 시간 우리는 Thread Programming 시의 Synchronization에 대해 다루었다. cnt라는 전역변수를 두 개의 Thread에서 각각 Increment하는 프로그램을 예시로 들었다. 만약, 프로그램의 입력 값이 10000이라면, 20000이라는 결과가 나와야하는데, 그렇지 않은 수행 상황을 발견한 바 있다.

  그 이유는 결국 Thread Routine 내의 "cnt++;"라는 명령이 겉보기완 다르게 Atomic하지 않아서였다. 즉, "cnt++;"라는 명령어의 수행 Sequence가 Interleaving되고 있는 것이다.

"cnt++;"라는 명령은 Assembly 단위에서 'Load->Update->Store'의 세 Instruction의 Sequence인데, 그 중간 수행 과정에서 Context Switch가 일어나는 것이다.

  이어서, 우리는 Progress Graph 개념을 배운 후, 예시 프로그램에서의 여러 Possible Trajectory Case들을 확인해보았다. 두 개의 Thread가 수행될 때, 여러 Trajectory가 가능한데, 양 Thread의 'Load->Update->Store'의 과정 사이에서 Trajectory가 침범해 들어올 경우, 즉, Critical Section이 침범될 경우, 프로그램의 의도를 벗어났다.

  양 Thread의 Critical Section이 이루는 영역이 'Unsafe Region'이다.

우리는 Trajectory가 Unsafe Region을 지나가지 않도록 설정해주어야 한다. 이러한 Thread Programming 기법을 'Synchronization', 'Synchronizing Threads'라고 한다.

Mutual Exclusion

우리는 어떻게 'Safe Trajectory'를 보장할 수 있을까?

Critical Section이 수행될 때에는, 두 Thread가 '상호 배타적으로(Mutually Exclusive)' 수행되어야 한다.

'Synchronization'은 곧 'Mutual Exclusion'이다. ★★★

Thread가 경쟁할 때, 한 Thread만 독점하도록 만들어주는 것이다. ★★★

양 Thread의 Critical Section 수행 시, Shared Variable에 대한 'Mutually Exclusive Access'가 Guarantee되어야 한다. ★★★

• Trajectory가 Unsafe Region을 침범하지 않도록 상호 배타적인 접근을 유도하는 것이다.

  이러한 문제 상황에서 'Mutually Exclusive Access'를 보장하는 아주 대표적인 Concept, Classic한 Solution은 바로 'Semaphore'이다.

  Semaphore는 Computer Science를 논할 때 빼놓을 수 없는 인물인 '에츠허르 데익스트라(Edsger Dijkstra)' 교수가 1960년대에 제안한, 컴퓨터 과학의 핵심을 이루는 주요 이론 중 하나이다. 그만큼 어렵고, OS의 핵심이 되는 이론이기도 하다. 컴퓨터공학도라면 반드시 알아야할 내용이다. 우리는 본 포스팅에서 세마포에 대해 알아볼 것이다.

  한편, Semaphore 외에도 Mutex & Condition Variable, 그리고 Java의 Monitor라는 여러 Synchronization 기법이 존재한다. 본 연재는 Semaphore만 다룬다.

Semaphore

Semaphore는 음이 아닌 Integer Type의 전역 변수이자 Synchronization Variable로, P와 V라는 연산에 의해 제어된다.

• int s;
  • Non-Negative Integer & Global

P Operation

P연산은 Semaphore s가 0인지 확인해, 0이 아닌 값(양수)이면 Decrement하고 종료한다.
만약, s가 0이면, P연산을 수행한 Thread가 Suspend된다.

Sleep한 Thread는 다른 Thread에서 수행한 V연산에 의해 다시 재실행된다.
재실행된 Thread는 s를 Decrement하고 즉시 종료하여 Caller에게 제어권을 넘긴다.

• Semaphore가 0이라는 것은, 어떠한 다른 Thread가 이미 Semaphore를 Decrement해놓고 점유하고 있다는 의미이다.
• Semaphore가 다시 0보다 큰 값이 될 때까지 P연산을 호출한 Thread는 Sleep한다. ★

즉, 누군가(다른 Thread)가 Semaphore를 0보다 큰 값을 만들어줄 때까지 나(Thread)는 자고 있겠다는 것이다. Signal을 받아서 깨어난다. ★

• P 연산의 'Test(0인지 확인하는 과정)'와 'Decrement(s에서 1을 뺌)'는 Atomic하게 수행된다.

  • 즉, Indivisible하다. (믿고 사용해도 된다는 것임)

• 주의 : Sleep한 Thread가 깨어나는 동작은, Sleep한 Thread가 상시로 s를 계속 체크하는 것이 아니라, 타 Thread의 V연산에 의한 Signal이 도달해서 깨어나는 것이다. ★

V Operation

V연산은 Semaphore s를 Increment한다.

P연산이 먼저 수행되고, P와 V 사이의 Critical Section이 수행되고 나서, V연산이 수행되는 것이다. (즉, Thread가 빠져나올 때 사용하는 연산)

즉, V연산은, Semaphore s를 점유하고 있는 Thread가 점유를 종료할 때 호출되어 s를 Increment하는 연산인 것이다.

• V연산의 'Increment' 동작은 Atomic하다. (믿고 맡겨라!)

• P연산을 호출해놓고 Semaphore가 이미 0이라서 Blocked(Sleep, Suspended)가 된 Thread들은 Semaphore s가 Nonzero가 되길 기다린다고 했다.

  • V연산이 호출되면, Semaphore s를 양수로 Increment하고, Sleep한 Thread들을 모두 동시에 재실행한다.
    • 재실행된 Thread들은 경쟁을 시작한다.

• P연산과 V연산은 Atomic하다. 즉, Indivisible하다. 쪼개질 수 없는 것이다.
  • P연산 : Variable Test + Variable Setting(Decrement)
  • V연산 : Variable Setting(Increment)

Semaphore Detail

• Critical Section(Shared Variable)에 T1, T2, T3 Thread들이 경쟁을 한다. 그 Section 안에는 하나의 Thread만 Mutually Exclusive하게 들어갈 수 있다.

  • Critical Section에 들어가 Lock을 잡아야한다.
    • 세 Thread가 모두 P(s)를 호출한 상황이다.

• 이때, 예를 들어, T1이 경쟁에서 승리해 Lock을 잡았다고 하자.

  • 그렇다면, T2, T3는 Lock을 잡기 위해 P(s)를 호출했지만, s가 먼저 Lock을 잡은 T1에 의해 Zero가 되어 있으므로 T2와 T3는 Sleep하게 된다.
    • T1이 자기가 Critical Section에서 할 일을 마친 후, V(s)를 호출해 Unlock하게 되면, 기다리고 있던 T2와 T3가 모두 깨어나게 된다.

• 사실, V(s)로 인해 재-경쟁을 시키는 과정은 구현 방법에 따라 달라질 수 있다.

  • 대표적인 방식은 모든 Sleep Threads를 Wake up 시켜서 다시 경쟁을 시키는 것이다.
    • Ready->Running->Sleep(Blocked)의 흐름을 거친 Thread들을 다시 Ready 상태로 만드는 것이다.
      • 누가? V(s)가 말이다.

• 깨어난(재실행된) Thread끼리 경쟁을 다시 해서 Lock을 잡게 되는 것이다.

Q) 위의 예시 상황에서 T1은 새로운 경쟁에 참여하지 않는가?
A) 그렇다. Critical Section을 수행하고 나서 V(s)를 통해 Lock을 풀고 나온 Thread는 자신의 Unlock으로 인해 수행되는 Re-Race에는 참여하지 않는다. 물론, 구현 방식에 따라 다르겠지만, 기본적인 의미만 보았을 때는, 그렇게 구현하여야 Mutual Exclusion을 실현시킬 수 있다. (이는 그냥 Code에 의해 좌우되긴 함)

Q) Interleaving이란 용어는 정확히 무엇을 의미하나요?
A) 복수의 Threads의 Critical Section들이 상호 겹치는 상황을 의미한다. 예시를 든 것처럼, "cnt++;"의 Load->Update->Store가 T1에 대해 L1/U1/S1, T2에 대해 L2/U2/S2라고 한다면, 이 두 Sequence가 서로 겹치는 것이다.

Q) T2, T3를 다 깨워주나요?
A) 그렇다. Sleep Threads를 다 깨우고, 그들이 다시 경쟁하여 Exactly one of those thread가 'Lock을 잡게 되는 것(Restart)'이다. 적어도 POSIX의 Pthread에선 그러하다.

Q) 모든 Sleep Threads를 다 깨워서 재경기하는 것보다, 그들에게 순서를 부여하는 방식이 더 좋은 것 아닌가요?
A) 아니다. 잘 생각해보자. Semaphore 기법 자체가 곧 Ordering을 부여하는 행위라고 보는 것이 맞다. 왜냐? Semaphore를 통해 중간의 Interleaving이 방지되고, 이전에 Lock을 잡은 Thread는 경쟁에 참여하지 않게 되면서 '알아서 Order를 갖추게' 된다. ★ (앞선 첫 번째 Q에 대한 해답이기도 한 것)

Q) Lock을 활용해 오직 하나의 Thread만 상호 배타적으로 수행된다면, 하나의 Thread만이 (단일) CPU를 독점하고, 그렇다면 Context Switch로 인해 불필요한 Overhead가 발생할 것 같습니다.
A) Sleep하고 있는 Thread들은 CPU Cycle을 사용하지 않는다. 말 그대로, Suspended Process를 생각하면 된다. 따라서, Context Switch에 참여하지 않는다. 그런데, 이를 '불필요한 Overhead'의 발생이라 볼 이유는 없다. 어차피 컴퓨터는 Time Sharing을 하기 때문에, Thread를 띄우고 있는 프로그램 외에도 다른 프로그램이 함께 돌아가고 있을 것이니 말이다.
  한편, Sleep Threads가 다시 깨어날 때의 Overhead는 존재하긴 한다.

Q) Sleep Threads가 Re-Race한다면, 운이 없는 Thread의 경우 Starvation 문제에 빠질 수 있는 것 아닌가요?
A) 정확하다. Semaphore 기법은 Starvation 문제를 해결하지는 못한다. Synchronization을 제공할 뿐이다.

POSIX Pthreads

  POSIX에서 제공하는 Pthread에서 Semaphore와 관련된 연산도 함께 제공한다. 아래를 보자.

#include <semaphore.h>
int sem_init(sem_t *s, 0, unsigned int val);} 	/* s = val */
int sem_wait(sem_t *s); 						/* P(s), 기다리기 때문에 wait이라 함 */
int sem_post(sem_t *s); 						/* V(s), 이후 연산이라 post라 함 */

// 우리는 sem_wait과 sem_post를 이용해 아래와 같은 Wrapper Function을 만들 수 있다.
void P(sem_t *s);								// 참조 교재의 csapp.h에서 제공
void V(sem_t *s);								// 내부 구현은 생략

  Unique한 Semaphore Mutex를 마련한다. 초기값은 1로 하자. 모든 Thread에서 이를 접근할 수 있다.

Semaphore 기법 적용 방법 : P(mutex)와 V(mutex)로 Critical Section을 감싼다. ★

이를 통해 해당 구간에 대한 Mutual Exclusion을 제공한다.

• Binary Semaphore : 항상 Semaphore s의 값이 0 또는 1인 Semaphore

  • 딱 하나의 Thread만 Critical Section을 점유하도록 만듦!

• Mutex : Mutual Exclusion을 실현하는 Binary Semaphore 변수를 일컫는 용어

  • P연산 : Mutex를 Locking한다.
  • V연산 : Mutex를 Unlocking/Releasing한다.
  • Holding Mutex : Locked이지만, 아직 Unlocked인 Mutex를 가리킨다.

• Counting Semaphore : 여러 값을 가질 수 있는 Semaphore를 의미한다.

  • 여러 Threads가 Critical Section을 점유할 수 있음.

Proper Synchronization Example

volatile long cnt = 0; 		// Shared Variable (volatile)
sem_t mutex; 				// Binary Semaphore which protects 'cnt'
Sem_init(&mutex, 0, 1); 	// Initial Value of Semaphore is 1

/* 지난 포스팅에서 다룬 example Program(cnt프로그램)과 동일한 main 함수 : 생략 */

void *thread(void *vargp) { 			// Thread Routine
	long i, niters = *((long *)vargp);
										
	for (i = 0; i < niters; i++) {
		P(&mutex);
		cnt++;					// Critical Section를 P와 V로 감싼다. ★★★
		V(&mutex);				// Synchronization via 'Mutual Exclusion'
	}
        
	return NULL; 
} 

(출력)
> ./example 10000
Yeah! cnt is 20000
> ./example 10000
Yeah! cnt is 20000

  지난 포스팅에서 예로 든 프로그램에 Synchronization을 적용한 상황이다. 수정 이전의 경우, 각 Thread가 무작위 순서로 cnt에 접근했었는데, 이제는 Mutual Exclusion이 적용되어 각 Thread의 접근이 '직렬화'되어 있다.

이때, 의외로 수행 속도 측면에서는 Synchronization을 적용하지 않은 이전 Version이 더 우수하다. 일련의 '직렬화 과정'이 필요없기 때문이다.

New Version’s orders of magnitude slower than Previous Version !!

• 평시에는 Mutex 값이 1로 유지되고, 두 Thread 중 하나가 Critical Section에 들어가면 0으로 설정되어, 다른 하나를 Sleep시켜놓고 있음에 주목하자.

  • Semaphore 기법의 P, V 연산으로 인해 Unsafe Region에 들어가기 위해선 Mutex가 -1이 되어야 한다.
    • Mutex s는 Non-Negative이므로, 물리적으로 불가능해지는 것이다.
      • 따라서, Semaphore Invariant는 Unsafe Region을 둘러싸, 어떠한 Trajectory도 Unsafe Region으로 못들어가게 막는 Forbidden Region을 형성하게 된다. ★★★

• sem_wait(P연산)과 sem_post(V연산)으로 특정 명령 구간을 둘러싸면, 그 구간은 곧 'Test-And-Set'이 된다. 무슨 말이냐 하면, CPU에서 마치 해당 구간을 '하나의 Instruction'처럼 취급하게 되는 것이다. 한 줄짜리 기계어 코드를 처리하듯이 말이다.

  금일 포스팅은 여기까지이다.