명품 운영체제 6장 스레드 동기화

스레드 동기화 

 

다수의 스레드들이 공유 데이터에 동시에 접근하여 쓰기를 수행하면 공유 데이터가 훼손되어 문제가 발생 할 수 있다. 

공유 데이터에 대한 스레드들의 동시 접근시 발생하는 문제를 해결하는 방법이 바로 스레드 동기화이다. 

 

스레드 동기화란 다수의 스레드가 공유 데이터를 동시에 쓰는 충돌 상황에서, 공유 데이터가 훼손되지 않도록 스레드의 실행을 제어하는 방법이다. 

 

---

1. 스레드 동기화의 필요성 

 

공유 데이터에 동시 접근시 발생 할 수 있는 문제 

왜 다수의 스레드들이 동시에 공유 데이터에 쓰기 작업을 할 때 문제가 발생할까? 

예를들어 아래의 코드를 실행한다고 하자. 

sum= sum+10 

 

이러한 코드는 사람을 위한 코드로  컴퓨터는 이해 할 수 없기 때문에 컴퓨터의 언어로 바꿔서 알려줘야한다. 따라서 아래의 3개의 기계 명령으로 번역된다. 

mov ax,sum : sum 변수값을 읽어 ax 레지스터에 저장
add ax,10     : ax 레지스터 값을 10 증가
mov sum,ax : ax 레지스터 값을 sum 변수에 저장 

 

사실상 코드가 한줄이 아닌 세 개의 명령으로 이루어져있는 것이다. 

 

이러한 명령을 두개의 스레드 t1,t2가 동시에 실행한다고 생각해보자. (초기 sum의 값은 0이라고 가정하자)

 

먼저 t1이 첫번째 mov 연산을 통해 sum 변수의 값인 0을 ax에 저장했다. 그런데 갑자기 인터럽트가 발생하여 t1 스레드의 작업이 중단되고 t2가 실행되었다고 하자. 

 

t2는 첫번째 mov연산을 통해 sum의 초기값인 0을 ax에 저장하고, ax에 10을 더하여 다시 sum 변수에 저장한다. 따라서 t2 스레드의 작업이 종료되고 난 후 sum의 값은 10이 되었다. 

 

그렇다면 일반적인 생각으로는 작업이 중단되었던 t1에서는 t2가 끝난후 다시 시작되는 것이므로, sum=10의 값에 다시 10을 더하여 20이 되겠구나 라고  생각할 수 있으나, t1은 첫번째 mov 연산을 끝낸 이후에  작업이 중단 되었다. 

즉, 변경된 결과가 반영되기 전의 값을 이미 읽어온 상태이므로 t2의 결과가 t1 스레드에는  반영되지 않는다 

 

따라서 t2의 작업이 끝난 뒤 다시 시작된 t1 스레드의 작업에 의해 최종적으로  sum의 값에는 10이 저장된다. 

 

만약 위의 상황이 은행계좌에 돈을 입금하는 상황이었다고 생각해보자. 나와 친구가 동시에 나의 계좌에 10억씩 넣는다고 하자.

그렇다면 입금이 끝난 후, 나의 계좌에는 20억이 들어있어야하는데 , 10억만 들어있는 상황인것이다. 분명 둘다 10억씩 입금 했는데도 불구하고 고 10억만 들어있다는것은 누군가의 10억이 증발 했다는 것인데 이건 정말 큰 문제가 아닐 수 없다!! 

 

 

이러한 문제는 두 스레드가 동시에 작업을 하며 발생한 충돌상황 때문에 발생하게 되는것이다. 

 

 

공유 데이터에 대한 동시 접근 문제의 해결책 

위에서 보았듯이, 여러 스레드가 공유 데이터에 동시에 접근하여 쓰기를 수행할때 충돌이 발생하여 문제가 발생할 수 있다. 

이에 대한 해결책은 하나의 스레드가 공유 데이터를 사용하고 있을때 다른 스레드는 그 공유 데이터를 사용하지 못하도록 막는것이다. 

즉, 공유 데이터에 대한 독점권을 부여해주는 것이다. 

 

 

• 임계 구역과 상호배제 

사용자가 작성한 프로그램 중, 공유 데이터를 이용하는 코드 블록을 임계 구역 이라고 한다. 

 

임계 구역은 공유 데이터를 다루고 있는 코드 블록이므로, 반드시 한 스레드만 배타적 독점권을 가지고 실행 될 수 있도록 관리되어야한다. 그리고 이를 상호배제 라고 한다. 

 

상호배제의 핵심은 임계 구역에 먼저 접근한 스레드가 도중에 작업이 중단되지 않도록, 작업을 보장해주는 것을 말한다. 

상호배제가 없는 임계구역은 존재 할 수 없다. 반드시 임계구역에 대한 상호배제가 이뤄질 수 있도록 설정해줘야한다. 

 

이러한 임계구역은 개발자의 판단에 따라 이뤄질 수 있다.  스레드 동기화를 위해 제공되는 멀티스레드 라이브러리나 시스템 호출을 이용하여 작성 할 수 있다. 

 

---

 

2. 상호배제 

상호 배제란 하나의 스레드가 임계구역 전체를 독점적으로 실행할 수 있도록 보장해주는 방법이다. 

 

상호배제 위치 

임계구역 전후에 상호배제 코드가 작성된다. 

이 두 코드를 각각 임계구역 진입코드(entry코드) , 임계구역 진출코드(exit코드)라고 한다. 

 

• 일반코드

공유 데이터가 존재하지 않는 코드 영역이다. 이 부분의 코드는 스레드가 동시에 실행되든, 그렇지 않든 큰 영향을 미치지 않는 부분이다. 

 

• 임계구역 진입코드(entry 코드) - 상호배제 코드 

공유 데이터를 다루는 구역안으로 들어가기 전의 코드로, 이곳에서 먼저 임계구역에서 실행중인 스레드가 있는지 확인한다. 

실행중인 스레드가 있다면 해당 스레드의 작업이 끝날때 까지 현재 스레드를 대기 시키고 , 없다면 작업을 하는 동안 다른 스레드가 들어오지 못하도록 조치를 취한다.  

 

• 임계구역 코드

공유 데이터를 다루고 있는 코드 영역으로, 한번에 한 스레드만 실행되도록 보장되어야하는 부분이다. 

임계구역은 짧을 수록 좋기 때문에, 임계구역은 최소한의 코드로 만드는것이 좋다. 

임계구역을 넓게 설정하면 스레드들이 작업할때 마다 lock 이 걸리는 시간이 늘어나기 때문에 작업효율이 떨어진다. 

 

• 임계구역 진출코드 (exit코드) - 상호배제 코드 

스레드가 임계구역의 실행을 마칠때 실행되는 코드로, 대기하고 있는 다른 스레드들이 임계구역 코드를 사용할 수 있도록 조치를 취해야한다. 

 

 

상호배제 코드 구현 

상호배제를 하는 방법은 결국 임계구역에 한 스레드만 들어가게 하는 방법이다. 

상호배제를 구현하는 방법에는 소프트웨어적인 방법과 하드웨어적인 방법이 있다. 

 

소프트웨어적인 방법은 알고리즘 수준에서 제시 된것들 이기 때문에 실제 사용하기에는 많은 문제점이 있다. 

오늘날에는 하드웨어적인 방법을 이용하며, 그중에서 원자명령을 활용하는 방법을 이용하고 있다. 

이제 entry 코드와 exit코드를 어떻게 구현하는지 알아보자. 

 

 

 방법1- 인터럽트 서비스 금지하기 

임계구역 안에서는 인터럽트가 실행되지 않도록 하는 방법이다. 

 

입출력 장치나 타이머가 인터럽트를 걸 수 있도록 허용 해놓고, 임계구역을 실행하는 동안만 CPU가 인터럽트 서비스를 못하도록 한다. 임계구역을 벗어난 이후에는 다시 인터럽트 서비스가 실행될 수 있도록 한다. 

 

이를 위해 entry 코드에서는 CPU가 인터럽트를 못하도록 명령을 작성하고, exit코드에서는 다시 인터럽트를 허용하도록 기계 명령 작성한다. 

 

이렇게 하면, 스레드가 임계구역에 있는 동안에는 인터럽트가 무시되기 때문에 임계구역을 독점적으로 사용할 수 있다. 

cli  : entry코드. 인터럽트 서비스 금지 명령 (cli : clear interrupt flag) 
=============
임계구역 코드
=============
stl : exit코드. 인터럽트 서비스 허용 명령 (sti : set interrupt flag)

 

• cli 명령은 CPU 내부의 인터럽트 플래그(IF)를 0으로 만들어, 인터럽트가 발생해도 CPU가 인터럽트를 무시하고 현재 작업을 수행하도록 한다. 
• sti 명령은 CPU 내부의 인터럽트 플래그(IF)를 1로 설정하여, 인터럽트가 발생하면 CPU가 하던일을 멈추고 ISR(인터럽트 서비스 루틴) 을 실행하게 한다. 

 

임계구역에 진입하기 전에 인터럽트 서비스를 중지시켜 상호배제가 성공하였다. 하지만 이 방법에는 2가지 문제점이 있다. 

 

첫번째 문제점은, 임계구역을 실행하는 동안 모든 인터럽트가 무시된다는 것이다. 

만약 임계구역을 실행하는 도중 문제가 발생하여 실행시간이 매우 길어지게 되더라도 인터럽트를 실행할 수 없기 때문에 다른 스레드들은 무한정 대기해야하는 상황이 발생할 수 있다. 

 

두번째 문제점은, 이 방법은 멀티코어를 비롯한 다중 CPU 환경에서는 사용할 수 없다. 각각의 CPU는 인터럽트 서비스를 수행 할 수 있는데 하나의 CPU에서 인터럽트 서비스를 금지 시킨다 하더라도 다른 코어의 인터럽트 서비스까지 금지시키지는 못한다. 

따라서 작업중인 스레드가 인터럽트로 인해 도중에 중단되지는 않지만, 다른 코어에서 실행되는 스레드가 임계구역에 들어오는것은 막지 못하는 문제가 발생한다. 

 

 

 방법2- 원자명령 

 

원자명령 없이는 상호배제가 근본적으로 불가능하다. 그 이유를 알아보자

 

 

• 원자명령없이 lock변수를 이용한 상호배제 -   locking/unlocking 방법 

화장실에 들어갈때 문을 잠그고(lock=1), 나올때 문을 열어 놓아(lock=0) 다른 사람이 들어갈 수 있도록 하는 방법 처럼

임계구역에 들어가기전에 lock 변수의 값을 1로 설정하여 다른 스레드들이 들어오지 못하게 막고, 작업을 끝내고 나오면서 lock 값을 0으로 설정하여 다른 스레드가 작업을 할 수 있도록 한다.  

 

entry 코드 // locking
=============
임계구역 코드
=============
exit 코드 // unlocking

entry 코드에서 문을 잠그고, 작업을 마치고 나오면서 exit코드에서 화장실 문을 열자 

 

이를 기계명령어로 작성하면 아래와 같다  

L1:
 mov ax,lock // lock 변수값 읽기
 mov lock,1  // locking
 cmp ax,0    // 문이 잠겼는지 확인한다 
 jne L1      // jump not equal... ax가 0이 아니라면 L1으로 다시 돌아간다
 ==========================
 임계구역
 ==========================
 mov lock,0 // unlocking

 

 

임계구역에서 실행중인 스레드가 있다면, 대기중인 스레드는 lock의 값이 0이 될때까지 L1명령을 계속 반복한다. 

 

하지만 이 방법에도 문제가 있다. 

lock 변수의 값을 읽어오는 과정과 lock변수의 값을 1로 바꾸는 명령이 하나의 단위로 실행되지 않기 때문에 먼저 실행중이던 스레드가 lock 변수의 값을 읽어온뒤 작업이 종료된다면, 이후에 작업을 시작한 다른 스레드에서는 lock의 값이 0이 었기 때문에 임계구역에 진입할 것이다. 

그때 앞선 스레드의 작업이 다시 실행된다면, 이전에 읽어온 값에서는 lock 의 값이 0 이었기 때문에 임계구역으로 진입할것이다. 

그래서 임계구역에서 충돌이 발생하게 된다. 

 

• 원자명령

이 문제의 해결방법은 lock 변수의 값을 읽어오고 lock 변수의 값을 1로 바꾸는 명령 사이에 컨텍스트 스위칭이 일어나지 않도록 두 명령을 하나의 명령으로 만드는 것이다. 이런 명령을 원자명령 혹은 TSL(test amd set lock)이라고 한다. 

 

두 명령을 하나의 명령으로 설정한다면 두 명령은 동시에 일어나기 때문에 변수의 값을 읽어오는 과정에 다른 스레드가 끼어들수 없다

 

L1:
 TSL ax,lock // 원자명령
 cmp ax,0    // 문이 잠겼는지 확인한다 
 jne L1      // jump not equal... ax가 0이 아니라면 L1으로 다시 돌아간다
 ==========================
 임계구역
 ==========================
 mov lock,0 // unlocking

 

 

멀티스레드 응용프로그램을 작성할때 개발자가 직접 원자명령을 이용한 상호배제 코드를 만드는것은 무리이다. 

이런건 동기화 라이브러리를 이용하자. 

 

---

 

3. 멀티스레드 동기화 기법

상호배제의 기반 위에, 여러 스레드들이 문제없이 공유 자원을 활용하도록 돕는 멀티스레드 동기화 기법에 대하여 알아보자. 

동기화 기법들은 겉으로 드러나지는 않지만, 임계구역에 진입할때 상호배제를 위해 원자명령을 사용한다. 

이러한 방법들은 멀티스레드 응용프로그램에서 반드시 사용되어야하므로  "동기화 프리미티브" 로 부른다. 

 

 

뮤텍스 동기화 기법 

락 변수를 이용하여, 한 스레드만 임계구역에 진입시키고 다른 스레드들은 큐에 대기시키는 방법이다. 

 

임계구역을 이용중인 스레드가 있다면(락이 잠겨있다면) , 해당 스레드의 작업이 끝날때까지(락이 풀릴때까지) 스레드가 블록 상태로 대기큐에서 잠을 자기 때문에 블로킹 락 또는 수면 대기 락이라고 한다. 

 

뮤텍스는 임계구역의 실행시간이 짧은 경우 비효율적이다. 왜냐하면 실행시간보다 스레드가 잠자고 깨는데 걸리는 시간이 더 클 수 있기 때문이다. 

 

스핀락 기법 

뮤텍스와 같이 락 변수를 기반으로 하지만, 대기 큐가 없다. 

 

락이 잠겨있다면, 락이 풀릴때까지 락 검사를 무한으로 반복한다. 그래서 스핀락은 공격적인 뮤텍스 또는 바쁜 대기 락이라고도 한다, 

 

스핀락은 단일 CPU환경에서는 매우 비효율적인 동기화 방법이다.  왜냐하면 지속적인 락 검사에 CPU를 활용해야하기 때문에, 새로운 스레드에게 주어진 타임 슬라이스가 끝날때 까지 무의미한 검사가 계속된다. 

하지만 멀티 코어 CPU환경이라면 경쟁을 하는 스레드 각각에게 코어를 분산 시킬 수 있으므로 효과적인 방법이 될 수 있다. 

 

스핀락 방법의 경우 뮤텍스와 달리, 스레드를 재우고 깨우지 않기 때문에 임계구역의 실행시간이 짧은 경우에 적용하기 좋은 방법이다. 

 

 

세마포

세마포는 n개의 자원을 다수의 스레드가 공유하여 사용하도록 돕는 자원 관리 기법이다.

뮤텍스나 스핀락 기법은 한 스레드에게 임계구역을 배타적으로 사용하도록 하는데 목적이 있지만, 세마포는 n개의 자원이 있고 여러 스레드들이 자원을 사용하고자 할때  원활하게 관리하는 것이 목적이다. 

 

 

예를들어 12개의 방이 있는 세미나 실이 있을때 현재 8개의 방이 사용중이라고 하자. 

그럼 사용가능한 방의 수는 4개이므로 한 학생이 방을 빌리러 오면 사용 가능한 방의 수를 3으로 고치고 세미나 방을 사용하면 된다.  

만약 12개의 방이 모두 사용중이라면 대기자 수를 1로 고치고 대기줄에서 기다리면 된다. 

 

여기서 사용가능한 방의 개수는 카운터 변수로, 방을 사용하기 위해 대기하는 학생의 줄은 대기 큐로 나타낸다. 

 

세마포는 자원을 다 사용한 스레드가 자원을 반납했을때 이를 대기 중인 스레드에게 알려 자원을 사용할 수 있도록 관리해주는 일을 한다. 

 

세마포가 하는일 

• 세마포는 자원의 개수 n을 알고, 스레드의 요청을 받아 자원의 사용을 허락한다. 
• 자원이 모자랄때 요청한 스레드를 대기큐에서 잠을 재운다. 
• 자원 사용을 끝낸 스레드가 세마포에게 알리면, 대기 큐에서 기다리고 있는 스레드를 깨워 자원을 사용하도록 허락한다. 

 

세마포의 구성요소 

• 자원 
• 대기 큐 - 자원을 할당 받지 못한 스레드가 잠을 자는 곳
• 카운터 변수 - 사용가능한 자원의 개수를 나타내는 변수. 카운터 변수가 음수이면 자원을 기다리는 스레드의 개수를 의미한다
• P/V연산 
  P연산 자원 요청시, 세마포가 스레드에게 자원 사용을 허가하는 과정 
  V연산은 자원 반환시, 스레드가 세마포에게  자원 사용이 끝났음을  알리는 과정

 

P/V연산은 wait/signal 연산이라고도 불린다. 

자원을 사용하려는 스레드는 대기 큐에 있든 무한 루프를 돌든 자원을 얻을때까지 대기(wait)하고

자원 사용이 끝난 스레드는 세마포에게 신호를 보내 세마포가 다른 스레드에게 자원을 사용 할 수 있도록 하기 때문이다. (signal) 

 

 

세마포의 종류

세마포는 자원을 할당 받지 못한 스레드를 다루는 방법에 따라 2종류로 나뉘며, P/V연산이 다르게 작동한다. 

• 수면 대기 세마포
• 바쁜 대기 세마포 

 

수면 대기 세마포
 P연산 중 자원 사용을 허락 받지 못한 스레드를 대기 큐에서 잠 재우고, V연산에서 사용 가능한 자원이 생기면 스레드를 깨워 자원 사     용을 허락하는 방법이다. 

 

 

바쁜 대기 세마포
P 연산에서 사용을 허락 받지 못한 스레드가 사용 가능한 자원이 생길때까지 무한 루프를 돌면서 검사하다가, V 연산에 의해 사용 가능한 자원이 생기면 P연산을 통과한 후 자원을 획득하는 방식이다. ( 따라서 대기큐가 없다 ) 

 

 

 

 이진 세마포 

세마포는 관리하는 자원이 1개인 경우와 여러개인 경우에 따라 아래와 같이 구분된다. 

• 이진 세마포 - 자원이 1개인 경우
• 카운터 세마포  - 자원이 여러개인 경우 

 

이진 세마포의 구성요소 

• 세마포 변수 S - 0또는 1의 값을 가지는 변수. 1로 초기화됨 
• 대기 큐
• P/V연산 
  P연산: 자원 사용의 허가를 얻는 과정
  V연산: 자원 사용이 끝났음을 알리는 과정

 

이진 세마포는 하나의 자원에 대해 여러 스레드가 사용하고자 할때 관리하는 기법으로 뮤텍스와 매우 유사하다. 

 

 

 

동기화 이슈: 우선순위 역전

 

우선순위 역전이란  스레드 동기화로 인해, 우선순위가 높은 스레드가 낮은 스레드보다 늦게 실행되는 상황을 말한다.

 

우선순위 역전의 해결방법

 

• 우선순위 올림
  스레드(T1)가 공유자원을 소유하게 될때 우선순위를 일시적으로 미리 정해진 우선순위(T3)로 높이는 방법이다. 공유 자원에 대한 엑세스가 끝나면 원래 우선순위로 되돌린다. 

 

• 우선순위 역전 
  스레드(T1)가 공유 자원을 획득하고 실행하는 동안, 높은 순위의 스레드(T3)가 자원을 요청하면 요청한 스레드 보다 높게 변경하여 계속 실행시키고 공유 자원에 대한 사용이 끝날때 원래 순위로 되돌린다. 

 

 

4. 생산자 소비자 문제

 

 

생산자 소비자 문제는, 유한한 크기의 공유버퍼에 데이터를 공급하는 생산자와 공유버퍼에서 데이터를 읽고 소비하는 소비자가 공유버퍼를 문제없이 사용하도록 생산자와 소비자를 동기화 시키는 문제이다. 

 

생산자 소비자 문제는 유한한 크기의 버퍼로 인해 발생하므로 유한 버퍼 문제라고도 한다. 

 

 

생산자 소비자 문제는 구체적으로 3가지 문제가 있다. 

• 문제1- 상호배제 (생산자들과 소비자들가 공유버퍼에 동시에 접근할때)
• 문제2 - 비어있는 공유버퍼 문제
• 문제3- 꽉찬 공유버퍼 

 

해결방법

• 상호배제 해결 

공유 버퍼에 대한 동시 접근 문제는 생산자와 소비자뿐만 아니라, 생산자와 소비자가 각각 여러명있는 경우에는 생산자들 사이에 혹은 소비자들 사이에도 발생할 수 있다. 

공유하는 하나의 자원에 대한 배타적 독점권을 위해 뮤텍스나 세마포를 이용하도록 한다. 

 

 

• 비어있는 공유 버퍼 문제 해결

소비자 스레드가 공유 버퍼를 읽을때 읽을 데이터가 없다면, 생산자 스레드를 공유 버퍼에 데이터를 기록하고 기다리고 있는 소비자 스레드를 깨운다. 

이 과정은 소비자 스레드가 대기하고, 생산자 스레드가 대기하는 스레드를 깨어나도록 알리는 방식 (wait/signal)이므로 세마포 방식으로 해결한다. 

 

세마포R을 만들고 세마포R에 대한 P연산은 소비자 스레드가, V연산은 생산자 스레드가 실행한다.

 

 

 

• 꽉 찬 공유 버퍼 해결 

생산자 스레드는 공유 버퍼에 기록하기 전에 반드시 버퍼가 꽉 차 있는지 확인한다. 만약 버퍼가 꽉 차 있다면, 생산자 스레드는 소비자 스레드가 하나의 버퍼라도 비울때까지 기다려야한다. 

소비자 스레드는 버퍼에서 데이터를 읽은 후, 기다리고 있는 생산자 스레드를 깨운다. 생산자 스레드는 깨어나서 버퍼에 데이터를 쓴다. 

 

이 과정은 세마포W로 구현한다.  세마포W에 대한 P연산은 버퍼에 쓰기 위해 생산자 스레드가, V연산은 소비자 스레드가 실행한다.

 

 

 

생산자와 소비자 알고리즘 

생산자와 소비자를 구현하기 위해선 2개의 카운팅 세마포가 필요하며, 카운터 변수의 최댓값은 공유 버퍼의 개수이다. 

• 세마포R : 읽기 가능한 버퍼의 개수가 0이면 대기 
• 세마포W : 쓰기 가능한 버퍼의 개수가 0이면 대기 
• 뮤텍스M : 생산자와 소비자 두 스레드에 의해 사용(상호배제)