Race condition과 간단한 동기화

 

경쟁 상태(Race Condition)

다수의 프로세스나 스레드가 공유 자원을 동시에 읽거나 쓰려고 하는 상태를 의미한다.
최종 수행 결과는 프로세스들의 수행 순서에 따라 달라진다.

 

싱글프로세서에서 race condition

 

싱글 프로세서에서 stack1에 쓰레드1, stack2에 쓰레드2가 진행된다고 했을 때 아래 그림의 전역변수 counter에 접근한다고 한다면 counter는 2가 되어야 할 것이다.

 

 

 

아키텍쳐마다 다르지만 counter++명령이 밑의 3개의 작업으로 이루어진다고 했을 때 

 

쓰레드 A에서 전역변수 counter를 로드한 시점에 스케쥴러에 의해 쓰레드 B가 실행되고 counter++작업을 마쳤다.

다시 쓰레드 A로 돌아가서 작업을 할때는 이미 load된 counter값인 0에 1을 더하고 저장하기 때문에 counter에는 2가 아니라 1이 다시 저장될 것이다.

 

 

 

멀티 프로세서에서의 race condition

 

멀티 프로세서에서도 마찬가지로 스케쥴러의 타이밍 때문에 load counter가 A,B에서 동시에 이루어 지면 counter에는 싱글 프로세서에서와 마찬가지로 0 + 1인 1이 저장될 것이다.

 

 

위와 같은 문제를 해결하기 위해 전역변수 처럼 둘 이상의 쓰레드가 동시에 접근해서는 안되는 ciritical resource 임계자원) 라는 개념을 만들었고, 이러한 데이터들이 저장되어 있는 critical section 임계구역) 이라고 한다.

(read일때는 신경안써도됨 wirte만) 

 

임계 구역(크리티컬 섹션, Critical Section)

critical section이란 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부를 의미한다. 

(= race condition이 발생할 수 있는 코드의 일부)

 

 

임계구역에 존재하는 자원들을 동시에 접근할 때 하나의 쓰레드에만 접근할 수 있게 보장해주는 요구사항이 상호 배제 이다.

 

critical section problem을 해결하기 위한 조건

 

mutual Exclusion 상호 배제

하나의 프로세스나 쓰레드가 크리티컬 섹션 코드를 진행하고 있다면 다른 프로세스, 쓰레드들은 크리티컬 섹션에 접근할 수 없다.

 

Progress 진행

어떤 프로세스, 쓰레드가 크리티컬 섹션에 접근하려고 할 때 아무도 크리티컬 섹션을 사용하고 있지 않는다면 접근한 프로세스, 쓰레드가 대기하지 않고 크리티컬 섹션을 사용한다.

 

Bounded Wating

크리티컬 섹션에 여러 프로세스, 쓰레드가 동시에 접근한다면 대기를 하는 프로세스가 존재하게 되는데 이 대기시간은 무한히 길어지면 안되고 한계 시간을 정해두어야 한다.

 

 

간단한 동기화 (이젠 쓰지 않는)

 

방법1

프로그램 A
While(1) /*Enter CS */ {
	if(bOccupied == 0) {
    bOccupied = 1;
    break; }
}
/*Critical Section*
bOccupied = 0; /*Exit CS */

프로그램 B
While(1) /*Enter CS */ {
	if(bOccupied == 0) {
	bOccupied = 1;
	break; }
}
/*Critical Section*/
bOccupied = 0; /*Exit CS */

전역 변수 bOccupied를 사용해서 프로그램 A, B가 임계 구역을 사용 중임을 알려주는 방법인데,

bOcccupied가 0인 상태에서 A를 실행중에 bOcccupied가 1로 바뀌기 전에 스케쥴러에 의해 B가 실행될 수 있으므로

이는 여전히 상호배제 조건을 만족하지 못한다.

 

방법2

프로그램0
do {
    flag[0] = TRUE;
    while ( flag[1]);
    CRITICAL SECTION
    flag[0] = FALSE;
    REMAINDER SECTION
} while (TRUE);

프로그램1
do {
    flag[1] = TRUE;
    while ( flag[0]);
    CRITICAL SECTION
    flag[1] = FALSE;
    REMAINDER SECTION
} while (TRUE);

이 방법은 프로세스가 2개 일 때 전역 배열 flag에 임계구역을 사용중임을 나타내는 방법이다

여기서도 0번째 프로그램에서 임계구역을 사용하기 위해 flag[0]을 true로 바꾼 시점에서 스케쥴링이 일어난다면 1번째 프로그램에서 flag[1]을 true로 바꾸고, 두 프로그램 모두 while문이 계속 반복되어 busy waiting이 일어날 것이다.

 

peterson's algorithm

프로그램0
do {
	flag[0] = TRUE;
	turn = 1;
	While ( flag[1] && turn == 1);
	CRITICAL SECTION
	flag[0] = FALSE;
	REMAINDER SECTION
} while (TRUE);

프로그램1
do {
    flag[1] = TRUE;
    turn = 0;
    While ( flag[0] && turn == 0);
    CRITICAL SECTION
    flag[1] = FALSE;
    REMAINDER SECTION
} while (TRUE);

위의 두 방법을 혼용한 알고리즘이다.

turn 전역 변수를 추가하여 각 프로세스를 주시하고, 적절히 진행가능하게 만들었지만 리팩터링에서 문제가 생길 수 있고, 프로세스의 개수가 많아 질수록 복잡해져 사용하지 못한다.

 

 

HW support

 

- 동기화를 가능하게 하기 위해서 HW 단계에서 줄 수 있는 도움

 

Test and Set(TAS)

여러 instruction을 하나의 연산으로 만드는 하드웨어 단계에서의 기법이다. (make atomic operation)

old값이 1이면 임계구역을 사용하고 있다는 뜻이므로 busy waiting하고 0으로 바뀌면 새로운 프로세스가 임계구역을 사용한다.

 

 

Compare and Swap(CAS)

위와 동일하게 atomic opration을 만드는데,

기대값을 정하여 old값이 0이라면 (임계구역을 사용하고 있지 않다면) 1로 바꿔줄 수 있다.

 

 

 

이렇게 busy waiting을 통해 동기화를 시도하는 방법을 spin lock이라고 한다.

 

 

spin lock

spin lock은 안정적으로 하나의 쓰레드만 임계구역을 사용할 수 있지만 busy wating으로 cpu 사용의 비효율을 발생시킨다. 

 

하지만 상대적으로 unlock을 빈번히 발생하는 멀티 프로세서 환경에서는 자주 사용되지만 어느 프로세서에 임계구역을 할당할지 정하지 못해 fairness 관점에서 불리한 방법이다.