Race Condition

• 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
• 데이터의 최정 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라집니다.
• 즉, 프로세스들은 병렬적으로 실행이 될 수 있기 때문에 여러 프로세스가 공유하고 있는 데이터의 무결성에 문제를 야기할 수 있습니다.

1. Producer-Consumer Problem

1. A(생산자)와 B(소비자)는 버퍼를 공유하고 있습니다.
2. A는 공유하고 있는 버퍼에 데이터를 채워 넣기만 하고, B는 데이터를 가져가기만 합니다.
3. 버퍼가 가득 차있으면 A는 버퍼에 빈 공간이 생길 때까지 대기하여야 하고, 버퍼가 텅 비어있다면, B는 A가 데이터를 넣어줄 때까지 대기해야 합니다. 여기서 두 프로세스는 Counter라는 int형 변수를 이용해 버퍼에 얼마만큼의 데이터가 존재하는지 파악하게 됩니다.
4. A와 B에서 실행되는 코드를 들여다보면, A에서는 데이터를 채워 넣을 때마다 "counter++"를 실행할 것이고, B에서는 데이터를 빼낼 때마다 "counter--"를 실행하게 될 것입니다. counter가 현재 5이고, A가 먼저 데이터를 채워 넣고 그 뒤에 B가 데이터를 가져가는 실행을 예로 들면, counter는 다음 그림과 같이 조작이 됩니다.
5. Register 1에 counter 값을 가져와서 수정을 해준 뒤 다시 counter 변수에 옮겨주는 형태입니다. 결과적으로 데이터를 한 개 집어넣은 뒤 하나를 빼냈기 때문에, counter 값은 그대로 5가 되어 올바른 값이 나옵니다. 하지만, 타이밍의 문제로 A의 호출 거의 직후에 B가 실행되면 다음과 같이 실행되는 경우가 발생할 수 있습니다.
6. 이 경우에는 A의 연산이 채 끝나기 전에 B가 실행되어 버려 결과적으로 counter는 잘못된 값인 4를 가지게 됩니다.

다중 코어, 다중 스레드의 작동 방식을 고려해보면 이러한 일들이 빈번하게 일어날 수 있다고 예상할 수 있습니다. 때문에 반드시 동시에 실행되는 프로세스들 간에는 동기화 처리가 되어있어야 합니다.

2. Critical-Section Problem (임계구역 문제)

Critical Section (임계구역) : 코드 중에 다른 프로세스와의 공유하고 있는 변수를 변경하거나, 파일을 쓰는 등, Race Condition이 발생할 수 있는 부분

• Remainder section : Critical Section이 아닌 영역

하나의 프로세스가 이미 Critical section 안에 들어가 있다면, 다른 프로세스들은 Critical section에 접근해서는 안됩니다. 두 프로세스가 동시에 하나의 Critical section안에 들어가게 되면 바로 위에서 봤던 것과 같이 타이밍의 문제로 올바르지 않은 값이 변수에 저장될 수 있기 때문입니다.

→ 따라서 하나의 Critical section에는 하나의 프로세스만 접근할 수 있는 프로토콜을 설계하는 것이 중요합니다.

Critical section 보호 방법

다음 세 가지가 모두 지켜질 때 Critical section이 보호될 수 있습니다

1. Mutual Exclusion (상호 배제)

의미 : Mutual Exclusion은 한 번에 하나의 프로세스만 Critical section에 들어갈 수 있다

프로세스 A가 한 Critical section에서 실행되고 있다면, 다른 프로세스들은 이 Critical section을 실행할 수 없습니다.

2. Progress (진행)

의미 : Progress는 한 Critical section에서 실행되고 있는 프로세스가 없는 상황에서, 어떤 프로세스가 그 Critical section에 들어가고 싶어 한다면, 들어갈 수 있어야 한다

비어있는 Critical section이 있다면, Remainder section에서 실행 중인 프로세스들을 제외한 다른 프로세스들은 Critical section으로의 진입을 요청할 수 있고, 진입을 요청한 프로세스들 중에서 알고리즘에 의해 다음으로 Critical section에 들어가게 될 프로세스가 결정되게 됩니다.

3. Bounded Waiting (한정된 대기)

의미 : Critical Section으로 들어가고자 하는 프로세스는 비록 지금은 알고리즘에 의해 우선순위가 밀려서 못 들어갈 수 있을지언정, 언젠가는 해당 Critical section에 진입할 수 있어야 한다

프로세스가 진입을 요청하게 되면 그 요청이 허용되어 Critical section에 들어가기까지, 그 사이에 다른 프로세스들은 정해진 횟수만큼만 들어갈 수 있어야 합니다.

대표 예시 : Strict Alternation 방법

그림의 방법을 Strict Alternation이라고 합니다. 프로세스가 2개만 존재한다는 가정 하에 만들어 진 방법입니다. 

프로세스 i는 j가 turn을 i로 변경할 때까지 기다리고, j가 변경한 후 Critical section으로 들어가 작업을 수행합니다. 작업이 완료되면 j는 turn을 j로 변경하고 Remainder section을 실행합니다. 그리고 i는 Critical section에서 빠져나와서 turn을 j로 변경합니다. 이때 j는 while문 안에 갇혀있기 때문에 두 개의 프로세스가 동시에 Critical section을 실행하지 않습니다..

• 하지만 위의 세 가지 조건 중 Progress를 만족하지 못하는 상황이 존재할 수 있습니다.

  1. i가 Critical section에서 빠져나오면서 turn을 j로 바꿔줍니다. 이 때 프로세스 j는 while문에 갇혀있거나, Remainder section을 실행하고 있을 것입니다.

  2. j가 Remainder section을 실행하고 있다고 생각해 봅시다. 마침 j가 Remainder section에서 시간이 오래 걸려서 i가 먼저 Remainder section을 모두 수행하고 다시 while문에 들어가 Critical section에 들어가고 싶어 하는 상황이 생겼습니다.

  3. 이때 Critical section은 비어있고, i는 진입을 요청했기 때문에, Progress를 만족하려면, i는 Critical section에 들어갈 수 있어야 합니다.

  4. 하지만 j는 아직 Remainder section을 수행하고 있고, turn을 i로 바꿔줄 수가 없는 상황입니다. 이렇게 되면 Progress를 만족하지 못하게 됩니다.

     즉, 상대방이 준비가 안되어 있는 상황에서 turn을 넘겨주게 되면 상황이 꼬일 수 있습니다.

3. Peterson's Solution

Strict Alternation이 문제점을 가지고 있었기 때문에 다음으로는 Peterson's Solution이라는 것이 등장합니다.

(그림) : Peterson's Solution

여기서는 두 가지 변수를 사용합니다.

• int turn : 누가 Critical section에 들어갈 차례인지를 표시
• boolean flag[2] : 각 프로세스가 Critical section에 진입 가능한 상태인지 표시. flag값이 true면 준비가 되어있다는 뜻.

상대방의 flag가 true여서, 상대방이 Critical section에 들어갈 준비가 되어있고, turn도 상대방에게 있는 상황에서만 while문에서 Critical section으로 들어가기 위해 대기할 수 있습니다.

코드 상으로 Peterson's Solution은 세 가지 조건을 모두 만족합니다.

• 이제는 문제점이 없을까요? 있습니다. 컴파일 도중에 코드의 순서가 바뀔수도 있다는 점입니다. 컴파일러는 메모리 접근을 위해 컴파일 도중에 필요에 따라 코드들의 위치를 조금씩 조정하기도 합니다. 그래서 만약 Peterson's solution에서 flag [i] = true;, while(flag [j] && turn ==j);줄의 순서가 바뀌면 제대로 동작하지 않을 수 있게 됩니다.
  

Synchronization Hardware (동기화 하드웨어)

Synchronization Hardware(동기화 하드웨어)는 시스템이나 장치 간에 동기화를 위해 사용되는 하드웨어 구성 요소를 가리킵니다. 이러한 동기화는 여러 개의 장치나 시스템이 함께 작동하고 데이터를 교환하거나 특정 작업을 동시에 수행할 때 필요한 시간적 조정을 의미합니다.

위에서 Race Condition을 SW로 해결하는 것에 한계가 있었습니다(컴파일러). 이러한 문제를 해결하기위해 atomic 명령어를 지원합니다.

• atomic 명령어 atomic 명령어는 해당 명령어가 실행되는 동안에는 다른 스레드의 접근을 허용하지 않고, 해당 명령어의 실행이 완료될 때까지 자원을 보호합니다. 이를 통해 데이터의 일관성을 유지하고, 동시 접근으로 인한 문제를 예방할 수 있습니다. atomic(원자적인) 뜻 그대로 쪼갤 수 없이 하나의 명령어로 수행됩니다.
  

test_and_set(TS)와 compare_and_swap(CAS)라는 instruction(명령어)들 입니다. 만일 두 개의 CPU들이 test_and_set이나 compare_and_swap을 각각 동시에 실행하여 같은 메모리 주소의 값을 변경하게 되면, 하드웨어는 알아서 하나의 CPU만 실행을 하도록 허용을 해줍니다.

test_and_set ( )

bool test_and_set(T* address)

• address: 값을 설정할 주소(메모리 위치)입니다. test_and_set 연산은 다음과 같은 과정을 수행합니다.
  1. address에 있는 값을 읽어옵니다.
  2. address의 loack의 값을 1(true)로 설정합니다.
  3. 이전의 값을 반환합니다.
  4. lock의 값을 0(false)로 설정합니다.

test_and_set은 말 그대로 lock의 값이 true인지 false인지 확인해 보고 true이면 누군가 Critical Section에 들어가 있다는 뜻이므로 false를 리턴해주고 lock의 값이 false면 lock의 값을 true로 바꾼 뒤에 true를 리턴해주는 명령어입니다. test_and_set을 소프트웨어적으로 구현해보면 다음과 같이 코드를 작성해 볼 수 있습니다.

그런데 이렇게 소프트웨어적으로 구현하여 함수를 호출하는 식으로 사용하면 만일 어떤 프로세스가 lock = true;까지 실행하고 context switching을 당하는 경우가 발생할 수 있습니다. 이러한 경우에 lock이 true가 된 상태여서 아무도 Critical section에 접근할 수 없기 때문에 다른 프로세스들이 Critical section을 실행하지 못하는 문제가 생기게 됩니다.

test_and_set() 명령어는 다음과 같이 사용될 수 있습니다.

compare_and_swap ( )

bool compare_and_swap(T* address, T expected, T desired)

• address: 값을 비교하고 변경할 주소(메모리 위치)입니다.
• expected: 현재 주소에 있는 값을 비교할 값입니다.
• desired: 주소에 저장할 값을 나타내는 값입니다.

compare_and_swap은 다음과 같은 과정을 수행합니다:

1. address에 있는 값을 읽어와 expected와 비교합니다.
2. address의 값이 expected와 같다면, desired 값을 address에 저장합니다.
3. address의 값이 expected와 다르다면, 아무 작업도 수행하지 않습니다.

lock의 값에 따라 0이면 lock의 값을 desired 인 1로 바꿔주고 0을 리턴해주기 때문에 while문을 탈출할 수 있고, lock의 값이 1이라면 그대로 원래 lock 값인 1을 리턴해 주는 형태입니다.

문제점

세 가지의 조건 (Mutual exclusion, Progress, Bounded waiting)중 Bounded waiting을 만족하지 않는다는 것입니다.

lock이라는 변수를 여러 Process가 공유하며 경쟁하므로 Bounded waiting을 만족하지 못하는 상황이 발생할 수 있습니다. 즉 얼마나 오랜 시간을 기다렸는지와는 전혀 상관없이 while문을 계속 돌며 경쟁적으로 lock을 가지려고 하기 때문입니다.

Mutex Locks

하드웨어를 통한 동기화 기법인 test_and_set이나 compare_and_swap의 경우에도 문제점이 있었습니다. 그래서 운영체제의 설계자들은 이러한 문제를 해결하기 위해 다시 소프트웨어 툴을 개발합니다. 그리고 이 중에 가장 간단한 도구가 바로 Mutex Lock입니다.

Mutex(Mutual Exclusion)

• acquire() 함수를 통해 lock을 획득

• release() 함수를 통해 lock을 반납

• 모든 프로세스는 Critical section에 들어가기 위해 lock을 획득해야만 하며, 빠져나올 때 반환해야 합니다.

  

  • available이라는 변수를 통해 현재 Lock이 사용 가능한지 아닌지를 표시 Mutex Lock도 앞에서 설명한 test_and_set이나 compare_and_swap과 같이 원자적으로 수행됩니다.

• 단점 : 바쁜 대기 (Busy Waiting).

  lock을 얻지 못하여 Critical section에 들어가지 못하는 동안 acquire 함수 내에서 while문을 돌고 있어야 한다는 점이 있습니다.

  현재 Critical section에 들어가지 못하여 어차피 프로세스는 할 일이 없음에도 불구하고 계속 while문을 통해 available 변수의 상태를 확인해야 합니다. 이것을 보고 프로세스가 Lock을 기다리면서 계속 회전하고 있다고 해서 Mutex Lock을 Spinlock이라고도 부릅니다.
  

• 장점 : 바쁜 대기 (?)

  프로세스가 계속 일을 하고 있기 때문에 Context Switching을 할 필요가 없다는 점이 장점으로 작용하기도 합니다.
  

결론 : 프로세스들이 짧은 시간 동안 Lock을 소유하는 경우라면 Mutex가 유용하게 사용될 수 있습니다.

Semaphore

Mutex에서의 Lock은 boolean 값으로써 true나 false의 값만 가집니다. 하지만 Semaphore에서는 boolean 대신 integer 값의 변수를 이용합니다.

Semaphore

• integral variable
• 두 가지 atomic 연산에 의해서만 접근이 가능하다

  def P(S):
  	while S<=0:
  		pass
  	S--

  def V(S):
  	S++

• 처음에 S의 값을 resource의 개수로 초기화
• 사용할 때는 S(wait)를, 반납할 때는 V(signal)을 호출
• S의 값이 0이 되었을 때는 현재 사용 가능한 resource가 없으므로 누군가 반납할 때까지 대기

wait와 signal도 원자적으로 실행이 되며, busy waiting 방식(P의 while문)을 사용합니다. S 값을 이용하여 현재 Critical section에 들어갈 수 있는지 없는지 판단을 하게 됩니다.

Semaphore의 구현

# Process P
while 1:
	P(mutex)
	critical section
	V(mutex)
	remainer section

Semaphore와 Mutex Lock 모두 busy waiting이라는 단점을 가지고 있습니다.
그래서 이를 극복하기 위해 Linked list를 이용하면서 변경된 wait와 signal 함수를 를 사용합니다.

Linked List wait & signal (Bloack & Wakeup Implementation)

구조

class S: # Semaphore
	def __init__(self):
		self.value = 0
		self.L = [] # 리스트처럼 표현했지만 링크드리스트

def P(S):
	S.value-=1
	if S.value < 0:
		S.L.append(now_process)
		block()

def V(S):
	S.value+=1
	if S.value<=0:
		S.L.del(S)
		wakeup(process)

동작 방식

1. 우선 구조체를 하나 만들어줍니다. value는 위에서의 S의 값과 똑같은 역할을 하고 L은 waiting queue의 head를 가리키게 됩니다.
2. P가 실행되면, 물론 Critical section에 들어갈 수 있는 상황이면 그냥 들어가면 되고, S의 값을 줄여주면 됩니다. 하지만 S의 값이 0이거나 0보다 작은 경우 해당 프로세스를 linked list로 구현된 waiting queue에 추가해주고 block 시켜 버립니다. 그럼 해당 프로세스는 running 상태에서 waiting 상태로 바뀌게 되고, CPU 스케쥴러는 새로운 프로세스를 선택하여 실행시킵니다.
3. signal()이 실행되면, 프로세스가 wakeup()을 통해 재시작됩니다. Wait 상태에 있던 프로세스는 깨어나서 Ready 상태가 되어 Ready queue로 들어가게 되고 스케쥴러에게 선택받기를 기다리게 됩니다.
4. S의 값이 0 이하로도 계속 내려가게 구현을 하는 이유는 현재 waiting 상태로 대기 중인 프로세스의 수를 파악하기 위해서 입니다. S의 값이 -2라면 현재 2개의 프로세스가 대기 중이라는 뜻이 되기 때문입니다. 이를 위해서 기존의 wait 함수에서 S의 값의 감소시키는 부분과 S 값을 검사하는 부분의 순서를 바꾼 것입니다.

Semaphore에는 두 가지 방식이 존재합니다

• Counting Semaphore Counting Semaphore는 integer 값을 모두 사용하기 때문에 여러 프로세스에 제한된 양의 resource를 할당해 줄 때 유용하게 사용할 수 있습니다
  
• Binary Semaphore Binary Semaphore는 0과 1만을 사용하기 때문에 Mutex Lock과 거의 동일한 기능을 합니다.
  

Deadlock and Starvation on semaphore

Waiting queue를 이용한 Semaphore 구현에서는 둘 이상의 프로세스가 서로의 signal 함수를 기다리면서 서로 더 이상 무한정 실행이 되지 못하는 상황이 발생할 수도 있습니다. 이러한 상황을 Deadlock (교착상태)이라고 합니다.

Wait queue가 후입선출 (Last-In-First-Out)의 방법으로 구현된다면 여기서도 starvation 문제가 발생할 수 있습니다. 따라서 이러한 점들을 고려하여 알고리즘을 설계해야 합니다.