💻 [OS 오퍼레이팅시스템] #11 | Synchronization (상호배제) | 동기화, 세마포어, 스핀락

 

---

💻 Race Condition

 - Synchronization 
쓰레드가 멀티쓰레딩 프로그램에서 같이 일할 때 공유 자원에 접근하는 것. -> 동기화 문제 발생

이 때, 올바르지 못한 결과가 나오는 문제 -> race condition

 

 - Race Condition 

다수의 프로세스나 쓰레드가 동시에 공유 자원에 접근하고 변경하려고 할 때 발생하는 버그 문제.

공유 자원에 접근할 결과가 다음과 같다.

- Non-deterministic한 Incorrect한 결과

- Non-Reproducible (재생산 불가능)

 

실행 시간에 달려있다. (실행 속도와 스케쥴링 타임 조절 불가능)

- 멀티쓰레딩 : CPU 스케쥴러에 의해 '끼어들기(interleaving)'가 발생할 수 있다. -> 예측 불가능

- 멀티프로세서 : 멀티 프로세서의 실행 시간이 다르다. -> 프로세서가 얼마나 busy한가에 달려있다. 예측 불가능

멀티프로세서의 두 개의 쓰레드가 동시에 공유 자원 접근하면 한 쪽의 정보 손실이 발생한다.

(사실 모든 쓰레드가 읽기만 한다면 race condition은 X)

 

atomic한 연산으로 공유 자원에 접근하기 어렵다

단일 연산도 다수개의 명령어로 컴파일 될 수 있다. (++연산은 load, add, store 명령어 3개로 이루어짐) -> atomic하다는 보장 X

* atomic operation : non-interruptible한 연산 (다 처리 또는 다 처리X)

 

 - 멀티 쓰레드 예시 

보통 전역변수 접근해서 연산하려고 하는 상황에서 (load->add->store) 전역변수 a 초기값 0이라고 하면

스레드A가 load한 뒤에(a=0) 스케쥴러에 의해 스레드B가 실행되고 다시 전역변수를 load(a=0), add(a=1), store(a=1)한 뒤 또 다시 스레드A가 이어서 add(a=1)부터 실행되고 store(a=1)가 되면 race condition이 발생한다. 

-> 스레드B에서 실행된 정보 손실. 우리가 원했던 결과는 2이여야하는데 1이 나오는 문제가 발생

 

---

💻 Critical Section 임계영역 

 - Sharing Resource 

각 쓰레드는 각자 자신의 스택과 CPU 레지스터의 카피본을 가지고 있다. (나머지는 다 공유자원)

공유 자원 예시 : static data, heap memory, files, I/O, printers, tape drives, variables, arrays, buffers, queue

 

 - Critical Resource (임계 자원) 

한번에 최대 한 프로세스만 사용해야 하는 자원 (shared resource라고도 불림)

ex) counter (전역변수)

 

 - Critical Section (임계 영역) 

또는 Critical Region이라고 불림

임계자원에 접근하는 코드부분을 임계영역이라고 한다. 

ex) counter++; (코드)

 

 - Critical Section Problem 문제 해결 조건 

다음의 3가지 조건을 반드시 만족해야한다.

1) Mutual Exclusion 상호배제 : 프로세스 A가 임계영역을 실행 중이라면, 다른 프로세스는 임계영역에 실행할 수 없다.

2) Progress 진행 : 임계영역을 실행 중인 프로세스가 없고 임계영역에 들어가기를 기다리는 프로세스가 있다면 대기하지 말고 실행하게 한다.

3) Bounded Waiting 한정 대기 : 프로세스가 임계영역을 실행하기 위해 대기하면서 다른 프로세스가 임계영역을 실행하는 횟수에 제한이 있다. (영원히 대기 X, limit이 존재한다)

---

💻 Mutual Exclusion 상호배제

 - Mutual Exclusion 

임계영역에 무조건 한 쓰레드(또는 프로세스)만 실행됨을 보장하는 것으로 임계영역의 목표라고 할 수 있다.

 

* 정리 : 프로세스/쓰레드 동기화는 race condition을 피하고 올바른 실행결과를 보장하는 상호 배제를 임계영역에 제공하는 매커니즘이다.

 

 - 동기화 분류 

1) Mutual Exclusion : 한 번에 한 프로세스가 공유 자원 접근하도록 보장

2) Condition Synchronization : 어떤 일(조건)이 일어날 때까지 프로세스가 대기하도록 하는 것

 

* 이번 글에서는 Mutual Exclusion 설명, 다음 글에서 Condition Synchronization 설명

---

💻 SW적 동기화 전략들

 - Naive한 접근 (잘못된 접근 방식) 

lock을 위해 간단한 flag를 구현한 방식 (진입 전 lock할 때 1로, 실행 후 unlock할 때 0으로)

Navie Approach : Broken Case

 

1) 프로세스 A에서 flag=0확인 후 스케쥴링이 발생

2) 프로세스 B에서 flag=0확인 후 flag=1로 lock하고 임계영역 실행

3) 실행 후 다시 스케쥴링 되어 프로세스 A로 돌아와서 flag=1로 lock

4) 프로세스 A도 똑같이 임계영역에 동시에 들어오게 된다

-> Mutual Exclusion 상호배제 만족 X

 

 

 

 - SW approach (1) 

flag를 여러개로 나눈다. ex) Boolean flag[2] = {false, false}

- flag[0]=true ->T1이 사용할 의사가 있다는 의미

- flag[1]=true ->T2이 사용할 의사가 있다는 의미

Mutual Exclusion (상호배제) 만족, 하지만 Progress (진행) 요구사항을 만족 X

broken case: 무한대기 -> Progress 요구사항 만족X

 

 - SW approach (2) - Peterson 

turn=0 : T0의 차례      turn=1 : T1의 차례

3가지 요구사항을 만족한다. (M.E + Progress + Bounded Waiting)

피터슨 해결법의 한계 : 복잡해서 2개의 프로세스만 가능하다는 제약이 있고, 코드 reordering 문제가 있다.(보장 X)

Peterson : 3가지 요구사항 만족

---

💻 HW적 동기화 전략들

 - Disabling Interrupt 인터럽트 금지 기법

인터럽트를 끄면 다른 스케쥴링에 의한 실행흐름을 방지할 수 있다.

단일 프로세서 시스템을 위해 사용된 해결법

인터럽트 금지 기법

장점	단점
심플하고 막강하다.	장시간 인터럽트를 끄면 인터럽트가 손실될 수 있다. 이런 권한 있는 작업은 일부 악성 프로그램에 의해 악용될 수 있다. 멀티프로세서에게 부적절하다(효과적 X)

 

 - TAS (Test-And-Set operation) 

메모리 영역의 값에 대해 Test(load)와 Set(store)을 단일의 원자적 수행으로 만들어주는 하드웨어 명령 TAS를 이용

Test : old lock 값을 검사한다.

Set : 새로운 값을 lock한다.

TAS

 

 - CAS (Compare And Swap) 

현재 쓰레드에 저장된 값과 메인 메모리에 저장된 값을 비교하고 일치하는 경우에만 새로운 값으로 수정

(일치하지 않는다면 실패하고 재시도)

TAS랑 비슷한 lock 구현

CAS

 

---

💻 다른 동기화 전략들

 - Spin Lock 스핀 락 

상호배제 만족 : spin lock은 한번에 한 쓰레드만 임계 영역에 들어가게 한다.

 

[ cost 성능 ]

- 단일프로세서 : 잠금을 유지하는 스레드를 제외한 다른 모든 스레드는 spinning동안 CPU cycle 낭비 (busy-waiting -> CPU 낭비)

- 멀티프로세서 : 다른 프로세서에 lock 대기하려고 spinning하는거에 많은 cycle이 낭비되지는 X

 

[ fairness (공정성) ]

- 스핀락은 공정성을 보장하지 않아 starvation 발생할 수도 있다.

 

 - Semaphore 세마포어 

(일반적인 동기화 방법) 세마포어 S : 정수값을 가진 객체 ('자원' 또는 '상태'로 해석)

semWait() : 값을 감소하는 함수, lock -> P(S);

semSignal() : 값을 증가하는 함수, unlock -> V(S);

Semaphore

* no busy waiting으로 구현됨 -> busy waiting이 발생한다.

- busy waiting 피하기 위해 세마포어에서 대기 중인 프로세스 큐를 사용할 수도 있다.

- 세마포어를 사용하여 n-프로세스 임계 영역 문제를 해결한다. (sleep-awake기법 사용)

 

데드락 발생 가능성 있다. (서로 다른 리소스 가지는데 다른거 요청하는 상황)

데드락 발생 상황

 

+TMI) 세마포어는 1965년에 다익스트라가 발명한 개념이다.

세마포어 분류 2가지 : binary semaphore, counting semaphore

 

 - 1) Binary Semaphore 세마포어 

lock으로 사용되는 정수 값이 무조건 0과 1이여야 한다. (lock/unlock 또는 unavailable/available)

mutex locks으로 알려져있다. 

Binary Semaphore

 

 - 2) Counting Semaphore 세마포어 

lock으로 사용되는 정수 값 제한 X 모두 가능general semaphore로 알려져있다. 

Counting Semaphore

example-counting semaphore

example-counting semaphore

semaphore의 구현

 

 

 - Locks in Linux 

locks in linux

 

 

---

💻 Example

 -  pthread_mutex_lock와 pthread_cond_wait/ pthread_cond_signal을 이용 

 

 - 세마포어 사용