[OS] 동기화(1) - 동기화 기초, SW/HW Solutions

1. Synchroniztion 이란?

동기화

운영체제는 다중 프로그래밍 시스템이기 때문에 여러개의 프로세스들이 존재하는데,

병행 수행 중인 비동기적 프로세스들이 공유 자원에 동시에 접근하게 된다면 문제가 발생할 수 있다.

이를 위해 필요한 것이 동기화이다.

동기화는 프로세스들이 서로 동작을 맞추고 정보를 공유하는 것을 의미한다.

 

2. Synchronization 용어

1) Shared data or Critical data

- 프로세스간 공유 데이터

 

2) Critical section(임계 영역)

- 공유 데이터를 접근하는 코드 영역(code segment)

- 임계 영역의 3가지 필요 조건

   (1) 상호 배제(Mutual exclusion) : 둘 이상의 프로세스가 임계 영역에 동시 진입 불가

   (2) 진행(Progress) : 임계 영역에 프로세스 자리가 비었다면 언제든지 진입 가능해야 함

   (3) 한정 대기(Bounded waiting) : 언젠가(유한 시간에)는 임계 영역에 프로세스가 진입 가능해야 함

 

3) Race condition

- 달리는(실행) 순서에 따라 결과 값이 달라지는 현상

 

4) Mutual exclusion(상호 배제) ★

- 둘 이상의 프로세스가 동시에 critical section에 진입하지 못하게 하는 것

- Race condition의 해결책

- critical section에 진입하기 전의 연산(검사)과 빠져나갈 때의 연산(알림)이 필요함

 

※ 기계어 명령의 특성 - 원자성

: 분리 불가능한 특성, 한 기계어 명령의 실행 도중에 인터럽트 받지 않는 특성

 

 

3. 상호 배제 SW 솔루션

1) 프로세스가 2개일 경우

데커(Dekker) 알고리즘, 피터슨(Peterson) 알고리즘

임계 영역 진입하기 전에 임계 영역 진입 전인 다른 프로세스를 while문에 가두고,

while문에서 turn값으로 while문을 빠져나올 하나의 프로세스를 정하는 알고리즘

두 알고리즘 모두 2개의 변수를 이용한다는 점에서 비슷하며, 피터슨 알고리즘이 더 간단하게 구현됨

 

2) 프로세스가 N개일 경우

(1) 다익스트라(Dijkstra) 알고리즘

- 최초로 프로세스 n개의 상호 배제 문제를 소프트웨어적으로 해결한 알고리즘

- 임계 지역 진입 시도를 두 단계로 직렬 연결해서, 프로세스 경쟁에 따른 부하를 덜어줌

- 루프문 시작 전에 상태를 선언하고, 루프문 내에서 유효성을 검토함

 

 

3) 위 SW 솔루션들의 문제점

- 많은 반복문으로 인한 속도 저하

- 구현이 복잡

- 실행 도중 선점 가능성 : interrupt를 억제함으로써 해결 가능하지만 그 만큼의 overhead 발생

- Busy waiting : 원하는 자원을 얻기 위한 권한을 얻을 때 까지 반복해서 확인하는 것

 

 

4. 상호 배제 HW 솔루션

1) TAS(TestAndSet) 이란?

- Test와 Set을 한번에 수행하는 명령

- 실행 중 interrupt를 받지 않기 때문에 선점되지 않는다는 보장이 있음

- 원자성

 

2) 이해를 돕기위한 TAS의 기본 흐름

※ 아래 소스 코드는 프로세스가 3개 이상일 때 한정 대기(Bounded waiting) 조건을 위배함. 프로세스간의 임계 영역 진입 순서가 불규칙적이기 때문에, 하나의 프로세스가 한없이 Busy waiting될 수 있음.

 

3) Bounded waiting 조건을 위배하지 않는 TAS Solution ★

위 코드의 ③번 부분을 보충설명하자면, while문을 탈출 할 수 있는 경우의 수는 다음과 같다.

- waiting[i]=false가 되는 경우 : 대기 상태인 프로세스가 존재할 경우

- lock=false가 되는 경우 : 대기 상태인 프로세스가 존재하지 않을 경우

 

 

4) 위 HW 솔루션들의 문제점

- 여전히 Busy waiting 문제가 존재한다.

 

 

 

이미지 출처 : 한빛 미디어 운영체제

참고 자료 : 김덕수 교수님 - www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN