Home [CS] 프로세스와 스레드 04 - 프로세스와 상호배제
Post
Cancel

[CS] 프로세스와 스레드 04 - 프로세스와 상호배제

Posted Sep 23, 2023 Updated Mar 25, 2024
By yanghs6
18 min read

개요

안녕하세요.

이번 글에서는 프로세스의 상호배제에 대해 살펴보겠습니다.

프로세스와 상호배제를 들어가기 앞서

상호배제의 배경: 사과 자판기

어느 사과 자판기가 있습니다.

자판기 앞에는 사과가 몇 개 있는지 적힌 표지판이 있어요.

지금은 자판기에 10개 있다고 적혀있습니다.

A는 사과 자판기에 사과 6개를 저장하고자 합니다.

B는 사과 자판기의 사과 반을 가져가서 잼을 만들고자 합니다.

A가 와서 사과가 10개 있다는 표지판을 보고 사과를 6개 넣기 시작합니다.

한편 B는 사과가 10개 있다는 표지판을 보고 그 중 반의 사과를 가져가서 잼을 만듭니다.

여기서 만약 A가 사과를 넣는 와중에 B가 사과를 가져간다면 창고에는 몇 개의 사과가 있고 표지판에는 몇 개의 사과를 적을까요??

A가 먼저 끝난다면 사과 자판기의 표지판은 16개 -> 8개로, B가 먼저 끝난다면 사과 자판기의 표지판은 5개 -> 11개로 바뀔 겁니다.

상호배제의 해결책: 사과 자판기의 자물쇠

그래서 자판기의 주인 C는 자판기에 자물쇠를 가져다 두었습니다.

“자판기를 사용할 때는 자물쇠를 걸고 끝나면 표지판에 사과를 적으시오”라는 안내문도 같이 말이죠.

이제 자판기는 혼자만 사용할 수 있고 A와 B 중 한 명이 작업을 끝내고 자물쇠를 풀지 않으면 사용할 수 없기 때문에 혼란이 사라졌습니다!

그래서 상호배제는??

위의 상황에서는 사과 자판기를 공유 자원, 자판기를 이용하는 A와 B는 프로세스나 쓰레드, 자판기의 자물쇠는 상호배제인 mutex로 비유했습니다.

공유 자원을 누구나 사용한다면 자원의 상태를 예측할 수 없고 여기서 발생한 오차가 전체 시스템에 문제를 야기할 수 있습니다.

따라서 공유 자원으로의 접근을 막는 mutex가 필요합니다.

상호배제 상세

상호배제의 개념

상호배제(Mutex; mutual exclusion)는 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘을 의미합니다.

읽시 연산은 공유 데이터에 동시에 접근해도 문제가 발생하지 않습니다.

하지만 변수나 파일은 프로세스별로 하나씩 차례로 읽거나 쓰도록 해야 하는데 이렇게 공유 자원을 동시에 사용하지 못하게 실행을 제어하는 방법을 동기화(synchronization)라고 합니다.

다음 그림을 통해 구체적으로 알아보겠습니다.

상호배제 개념 [그림01] 상호배제 개념

프로세스 P1과 P2를 같은 컴퓨터에서 실행한다고 해보겠습니다.

두 프로세스가 동시에 사용할 수 없는 공유 자원을 임계 자원(critical resource), 임계 자원에 접근하고 실행하는 프로그램 코드 부분을 임계영역(critical section)이라고 합니다.

임계 영역은 다음 3가지 조건을 만족해야 합니다.

  • 상호배제: 어떤 프로세스가 임계 영역에서 작업 중이면 다른 프로세스는 임계영역으로 들어갈 수 없습니다.
  • 진행: 임계 영역에 프로세스가 없는 상태에서 여러 프로세스가 들어가려고 할 때는 어떤 프로세스가 들어갈지 적절히 결정해야 합니다.
  • 한정 대기: 다른 프로세스가 임계 영역을 무한정 기다리는 상황을 방지하려면 임계 영역에 한 번 들어갔던 프로세스는 다음에 임계 영역에 다시 들어갈 때 제한을 둡니다.

프로세스가 공유 데이터에 접근할 때 “프로세스가 임계 영역에 있다”고 합니다.

1단계에서는 P1이 공유 메모리에 진입하고 2단계에서 인터럽트가 발생하여 P1 작업을 완료하기 전에 P2 실행을 예정합니다.

P2가 공유 메모리에 진입을 시도하지만, P1이 공유 메모리에 있으므로 P1을 종료할 때까지 P2를 차단합니다.

그러므로 상호배제는 프로세스가 수정할 수 있는 공유 데이터에 접근할 때만 적용하고, 단순 읽기 등을 할 때는 동시에 수행하도록 허용해야 합니다.

상호배제의 조건

한편, 프로세스는 다른 프로세스와 충돌하지 않는 연산을 할 때 동시에 수행하도록 허용해야 합니다.

따라서 상호배제는 다음 4가지 조건을 만족해야 합니다.

  • 두 프로세스는 동시에 공유 자원에 진입할 수 없습니다.
  • 프로세스의 속도나 프로세서 수에 영향을 받지 않습니다.
  • 공유 자원을 사용하는 프로세스만 다른 프로세스를 차단할 수 있습니다.
  • 프로세스가 공유 자원을 사용하려고 너무 오래 기다려서는 안 됩니다.

상호배제의 방법

상호배제를 적용하는 방법으로는 뮤텍스, 세마포어, 모니터 등이 존재합니다.

이번 글에서는 뮤텍스와 세마포어에 대해 간단히 알아보겠습니다.

뮤텍스

개요

락(Lock) 혹은 뮤텍스(mutex)은 데이터 접근 이전에 락을 얻게 함으로써 각 스레드가 서로 협력하는 동기화 방식입니다.

가장 단순한 락은 이진 세마포어입니다.

다음 그림을 통해 살펴보겠습니다.

뮤텍스 [그림02] 뮤텍스

이 그림에서는 프로세스 P1, P2가 임계 영역 1개를 뮤텍스를 활용해 접근합니다.

초기 상태에서는 임계 영역에 진입할 수 있는 뮤텍스가 있습니다.

2단계에서는 P1이 뮤텍스를 획득하고 임계 영역에 진입합니다.

3단계는 P2가 뮤텍스를 획득하고 임계 영역에 진입하려고 합니다.

하지만 이미 P1이 뮤텍스를 소유 중이므로 P2는 임계 영역에 진입하지 못합니다.

4단계에서 P1은 임계 영역을 탈출하며 소유 중인 뮤텍스를 해제합니다.

5단계에서 P2는 다시 한 번 임계 영역에 진입을 시도하는데요.

3단계와 달리 뮤텍스가 남아있으므로 이를 획득하고 성공적으로 진입합니다.

특징

  • 리소스에 접근하는 스레드나 프로세스를 1개로 제한 가능
  • 단순하고 fine-grained의 granularity을 가지는 저수준의 메커니즘
    • granularity는 크게 fine-grained와 coarse-grained로 나뉩니다.
    • 어원은 grain(곡식을 낱알로 분리하는 작업)을 fine(곱게)하게 또는 coarse(거칠게)하는지의 여부입니다.
    • fine-grained는 하나의 작업을 잘게 나눠 다수의 호출로 결과를 생성합니다.
    • coarse-grained는 하나의 작업을 큰 단위로 나눈 뒤 1번의 호출로 결과를 생성합니다.
  • 사용 전 오버헤드, lock 경쟁, 교착상태라는 3가지 특성 확인 필요
    • 오버헤드는 락을 위한 메모리, CPU 시간, 락 획득 및 해제 시간 등의 추가 리소스를 의미합니다.
    • lock 경쟁은 granularity와 관련있습니다. 예를 들어, 특정 테이블의 1개 값이 임계영역이라고 해보겠습니다. fine-grained하다면 그 값에 lock을 적용하지만 coarse-grained하다면 해당 테이블에 lock을 적용합니다.
    • 교착상태는 2개 이상의 태스크가 다른 태스크가 가진 락을 기다리는 상황입니다. 하나라도 종료되지 않는다면 두 태스크는 영원히 대기합니다.
  • 다음에 설명한 세마포어 중 이진 세마포어에 속함

세마포어

세마포어는 공유 자원의 접근 제어와 임계 영역 문제 회피를 위해 사용됩니다.

종류

세마포어는 크게 이진 세마포어(binary semaphore)와 계수형 세마포어(counting semaphore)로 나뉩니다.

  • 이진 세마포어
    • 뮤텍스 락이라고도 부릅니다.
    • 0과 1의 2가지 값만 가질 수 있습니다.
    • 다수의 프로세스가 사용되는 임계 영역 문제의 해결책으로 사용됩니다.
  • 계수형 세마포어
    • 제한되지 않은 도메인에 걸쳐 있을 수 있습니다.
    • 여러 인스턴스가 있는 리소스에 대한 액세스를 제어하는 데 사용됩니다.

연산의 상세

세모포어를 사용하는 프로세스는 wait(P)와 signal(V)의 2가지 연산을 제공합니다.

이때, 두 연산은 모두 원자성을 만족해야 합니다.

wait 연산은 세마포어의 값을 감소시키고 signal 연산은 세마포어의 값을 증가시킵니다.

세마포어의 값이 0이 된다면 wait 연산을 실행하는 모든 프로세스가 다른 프로세스의 signal 연산 수행까지 대기합니다.

정확한 비유는 아니지만 semaphore라는 변수의 개수가 곧 임계영역에 진입할 수 있는 프로세스의 개수라고 봐도 좋습니다.

wait 연산은 semaphore가 0일 때는 대기, 아니라면 semaphore를 하나 소유하구요.

signal 연산은 semaphore에 1을 더해서 소유한 세마포어를 해제합니다.

다음은 위 2가지 연산의 의사코드 예시입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

P(semaphore s){
  while(S == 0);
  s = s - 1;
}

V(semaphore s){
  s = s + 1;
}

...

// code 1
P(s);
// critical section.
V(s);
// code 2

다음은 파이썬으로 구현한 이진 세마포어의 예시입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

from enum import Enum
from queue import Queue

class Semaphore:
    class Value(Enum):
        Zero = 0
        One = 1

    def __init__(self):
        # 세마포어 대기 큐
        self.q = Queue()
        # 세모포어 값을 1로 설정
        self.value = Semaphore.Value.One

    def P(self, s, p):
        # 세마포어를 사용할 수 있다면 값을 0으로 변경하고 임계영역 진입
        if s.value == Semaphore.Value.One:
            s.value = Semaphore.Value.Zero
        # 세마포어를 사용할 수 없다면
        else:
            # 세마포어 대기 큐에 해당 프로세스 추가
            s.q.put(p)
            # 해당 프로세스를 대기 상태로 전황
            p.Sleep()

    def V(self, s):
        # 세마포어 대기 큐가 비어있다면 세마포어 값을 1로 설정
        if s.q.qsize() == 0:
            s.value = Semaphore.Value.One
        # 세마포어 대기 큐에 프로세스가 있다면
        else:
            # 세마포어 대기큐에서 프로세스 가져오기
            p = s.q.queue[0]
            s.q.get()
            # 프로세스 실행
            p.Wakeup()

마무리하며

이번 글에서는 상호배제를 살펴보았습니다.

상호배제는 공유 불가능한 자원의 동시 자원 사용을 회피하는 알고리즘입니다.

상호베제 적용하는 방법은 다양한데 이 글에서는 뮤텍스와 세마포어가 있습니다.

이 글이 조금이나마 도움이 되셨으면 합니다.

감사합니다. 😀

참고 문헌

Computer Science, general
컴퓨터과학(computer_science) 개념(concept) 프로그램(program) 프로세스(process) 스레드(thread) 상호배제(mutual_exclusion) 뮤텍스(mutex) 락(lock) 세마포어(semaphore) 메모리(memory) 교착상태(deadlock)
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents

[CS] 프로세스와 스레드 03 - 스레드의 개념과 구현

[CS] 프로세스와 스레드 05 - 프로세스와 여러 현상

Comments powered by Disqus.