[운영체제] Ch.6 프로세스 동기화와 상호배제, 세마포어 Python 구현

본 글은 김덕수 교수님의 2019년도 봄학기 운영체제(CPA310)

강의 내용을 바탕으로 요약 정리한 내용입니다.

 

https://sites.google.com/view/hpclab/courses/operating-system

HPC Lab., KOREATECH - Operating System

 

---

 

Process synchronization

 

프로세스 동기화는 프로세스들이 서로 정보를 공유하는 것이다.

다중 프로그래밍 시스템에서는 여러 개의 프로세스들이 시스템에 존재하고,

서로 독립적으로 동작하기 때문에 공유 자원 or 데이터가 있을 때 문제가 발생할 수 있다.

 

프로세스들이 서로에 대해 모르고, 여러 개의 프로세스들이 동시에 시스템에 존재하는

즉, 비동기적이고 병행적인(Asynchronous, Concurrent) 상황에서는 공유 자원에 동시 접근할 때 문제가 발생한다.

 

* 용어 정리

(1) Shared Data (Critical Data) = 여러 프로세스들이 공유하는 데이터

(2) Critical Section = 공유 데이터를 접근하는 코드 영역

(3) Mutual Exclusion(상호 배제) = 둘 이상의 프로세스가 동시에 Critical Section에 진입하는 것을 막는 것

 

 

아래 그림처럼 만약 Mutual Exclusion으로 여러 프로세스가 Critical Section으로 접근하는 것을막지 않는다면, Race Condition의 문제가 발생한다.

* Race Condition : 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과 값에 영향을 줄 수 있는 상태

 

Race Condition의 예시

 

사용자가 프로세스 i, j를 실행하면서 sdata를 각각 1씩 더해주고 2라는 결과를 유도했다고 생각하면

명령 수행 과정(1) 처럼 진행되면 의도한 대로 결과가 나올 것이다.

그런데 만약 명령 수행 과정(2)처럼 프로세스i가 작업 수행 도중에 Preemption되고, j에게 CPU가 넘어가서

작업이 쭉 수행된다고 가정하면 sdata의 결과는 1번 수행 과정과 달라지는 것이다. 즉, Race Condition이 발생한다.

 

---

 

Mutual Exclusion

 

둘 이상의 프로세스가 critical section에 진입하는 것을 방지하기 위해

(혹은 race condition이 발생하는 것을 방지하기 위해)

상호 배제라는 개념이 등장한다.

 

Mutual Exclusion

 

상호 배제 솔루션은 크게 enterCS()와 exitCS() 기능으로 나뉜다.

enterCS()는 Critical Section(CS)을 검사하여 다른 프로세스가 임계 영역에 있는지 검사하는 것.

exitCS()는 Critical Section을 벗어남을 알리는 것이다.

 

임계 영역 문제를 완벽하게 해결하기 위해서는 3가지 조건이 모두 만족되어야 한다.

 

1. Mutual Exclusion - CS에 다른 프로세스가 있으면, 다른 프로세스의 진입을 금지시켜야 한다.

2. Progress - CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안된다.

3. Bounded Waiting - 프로세스의 CS 진입은 유한시간 내에 허용되어야 한다. ( 무한 대기 X )

 

상호 배제를 구현하기 위해서 여러 SW, HW, OS가 지원하는 SW 솔루션,

그리고 언어 레벨에서 제공되는 솔루션들이 사용된다.

 

그 중에서 SW 솔루션으로는 다익스트라 알고리즘과 피터스 알고리즘이 있는데

SW 솔루션들은 속도가 느리고, 구현이 복잡하며, ME 과정 실행 중에 Preemption 될 수 있고, Busy Waiting

발생 가능성이 있다는 단점들이 존재한다.

 

HW 솔루션으로는 TAS(TestAndSet) 명령이 있는데

Test와 Set을 한 번에 수행하는 기게어이다.

실행 중 interrupt를 받지 않는다는 특징이 있으나, Busy Waiting은 여전히 피할 수 없다.

 

 

 

---

 

Semaphore

 

세마포어는 운영체제 차원에서 제공하는 대표적인 공유 자원 접근 제한 방법이다.

연산으로는 초기화 연산, P() 연산, V() 연산이 있으며

음이 아닌 정수형 변수 S 하나에 ready queue 하나가 할당된다.

S는 쉽게 생각하면 가용한 자원의 개수로 생각하자.

 

세마포어의 종류로는 이진 세마포어, 카운팅 세마포어가 존재한다.

이진 세마포어는 S가 0과 1 두 종류의 값만 갖는 경우를 의미하며, MUTEX라고도 한다.

여러 프로세스간의 상호배제나 프로세스 동기화의 목적으로 사용한다.

 

카운팅 세마포어는 S가 0이상의 정수 값을 가질 수 있다.

생산자-소비자 문제 등을 해결하기 위해 사용한다.

 

세마포어로는 상호배제 문제, 프로세스 동기화 문제, 생산자-소비자 문제, 다이닝 필로소퍼 등을 모두 해결할 수 있다.

 

초기화 연산은 S 변수에 초기 값을 부여하는 연산이다.

그리고 P(), V() 연산은 다음과 같다.

P(S), V(S)

P는 임계 구역에 들어가기 전에 수행하는 연산이고, V는 임계 구역에서 나올때 수행하는 연산이다.

OS 차원에서 지원하는데, 연산 전체가 한 instruction cycle에 수행되어 도중에 Preemptive 당할 걱정은 없다.

즉, indivisible(분리 불가능)하다.

 

 

만약 새로운 프로세스가 임계 영역에 들어가기 위해서 P연산을 실행했는데 S(위 그림에선 active) 변수 값이

0이라면, 그냥 프로세스를 block시키고 ready Queue에 들어가서 기다리게 만들면되는 것이다.

( 반복문으로 계속 체킹하는 busy waiting 현상도 발생하지도 않는다. )

어차피 임계 영역에 들어간 프로세스가 임계 영역에서 나올 때 큐에 있는 process를 wake-up 해줄 것이다.

 

또한, 세마포어는 Busy Waiting이 없다.

P() 연산을 통해 기다려야 하는 프로세스가 생기면 block state가 되기 때문이다.

단, Semaphore queue에 대한 wake-up 순서는 결정되지 않았기 때문에 Starvation 문제는 발생할 수 있다.

 

---

Python에서는 threading 모듈을 통해 세마포어 기능을 구현할 수 있다.

 

import time
import threading

# 세마포어 객체 생성
semaphore = threading.Semaphore(2)  # 최대 2개의 스레드가 동시에 실행될 수 있음


def worker():
    semaphore.acquire()  # 세마포어 획득
    print("Working...")
    time.sleep(2)
    semaphore.release()  # 세마포어 해제


# 스레드 생성 및 실행
t1 = threading.Thread(target=worker)
t2 = threading.Thread(target=worker)
t3 = threading.Thread(target=worker)

t1.start()
t2.start()
t3.start()

 

위 예제는 최개 2개의 쓰레드가 동시에 실행될 수 있도록 새마포어 객체를 생성하였고,

worker() 함수에서 세마포어의 P(), V()연산을 acquire(), release()로 구현하였다.

위 코드를 실행하면 최대 2개의 쓰레드가 동시에 실행되며, t3 쓰레드는 자원을 얻기 위해 기다린다.