동기화(Synchoronization)

동기화란?

동기화는 여러 프로세스나 스레드가 공유 자원에 동시에 접근할 때 발생할 수 있는 문제들을 해결하기 위한 방법입니다.
동기화에는 실행 순서 제어를 위한 동기화와 상호 배제(mutual exclusion)를 위한 동기화가 있습니다.
- 실행 순서 제어를 위한 동기화
  - Writer 프로세스는 Book.txt 파일에 값을 저장하는 프로세스이고, Reader 프로세스는 Book.txt 파일에 저장된 값을 읽어 들이는 프로세스라고 가정해 보겠습니다.
  - 이럴 경우, 반드시 Writer 프로세스가 Reader 프로세스보다 먼저 실행되어야지 Reader 프로세스가 올바르게 Book.txt 파일의 값을 읽어올 수 있습니다.
- 상호 배제(mutual exclusion)를 위한 동기화
  - 상호 배제는 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘입니다.
  - 예를 들어 계좌에 10만 원이 저축되어 있을 때 프로세스 A는 현재 저축된 금액에 2만 원을 넣는 프로세스이고, 프로세스 B는 현재 저축된 금액에 5만 원을 넣는 프로세스입니다.
    - 프로세스 A의 실행과정
      - 계좌의 잔액을 읽어 들인다.
      - 읽어 들인 잔액에 2만 원을 더한다
      - 더한 값을 저장한다
    - 프로세스 B의 실행과정
      - 계좌의 잔액을 읽어 들인다.
      - 읽어 들인 잔액에 5만 원을 더한다
      - 더한 값을 저장한다.
  - 이때 프로세스 A와 프로세스 B가 동시에 실행된다고 하면 기대되는 값은 17만 원 일 것입니다. 하지만 만약 두 프로세스 실행과정 사이에서 컨텍스트 스위칭이 발생한다고 하면 이상한 결과 값이 나올 수 있습니다.
    - (프로세스 A) 잔액 읽기 (10만 원) → (프로세스 A) 읽은 값에 2만원 더하기(12만원) → 컨텍스트 스위칭 → (프로세스 B) 잔액 읽기 (10만원) → (프로세스 B) 읽어들인 값에서 5만원 더하기(15만원) → 컨텍스트 스위칭 → (프로세스 A)더한 값 저장(12만원 저장) → 컨텍스트 스위칭 → (프로세스 B) 더한 값 저장(15만 원 저장)
    - 이럴 경우 17만 원이 저장되어야 하지만 중간에 컨텍스트 스위칭으로 인해 올바르게 작업이 진행되지 못해서 15만 원이 저장되게 되었습니다.
  - 이러한 경우를 방지하기 위해 상호 배제를 위한 동기화가 필요합니다.

생산자와 소비자 문제 (상호배제를 위한 동기화 예시)

생산자와 소비자 문제는 상호배제를 위한 동기화가 필요한 대표적인 예시입니다.

생산자는 데이터를 계속 버퍼에 넣고, 소비자는 버퍼에서 데이터를 빼는 작업을 합니다.

동기화 없이 작업을 할 경우 아래처럼 문제가 발생할 수 있습니다. (위 설명 중 계좌 업데이트 예시랑 비슷한 상황입니다. 같은 자원에 동시 접근하여 생기는 문제)

import time
from multiprocessing import Process, Manager


def produce(shared_value):
    for _ in range(10000):
        shared_value.value += 1


def consume(shared_value):
    for _ in range(10000):
        shared_value.value -= 1


if __name__ == "__main__":

    with Manager() as manager:
        shared_value = manager.Value("i", 0)
        print(f"초기 합계: {shared_value.value}")

        producer = Process(target=produce, args=(shared_value,))
        consumer = Process(target=consume, args=(shared_value,))

        producer.start()
        consumer.start()

        producer.join()
        consumer.join()

        print(f"producer, consumer 프로세스 실행 이후 합계: {shared_value.value}")

-->
초기 합계: 0
producer, consumer 프로세스 실행 이후 합계: -87

Lock 장치를 통해서 정상적으로 실행되도록 할 수 있습니다.

import time
from multiprocessing import Process, Manager, Lock


def produce(shared_value, lock):
    for _ in range(10000):
        with lock:
            shared_value.value += 1


def consume(shared_value, lock):
    for _ in range(10000):
        with lock:
            shared_value.value -= 1


if __name__ == "__main__":
    lock = Lock()

    with Manager() as manager:
        shared_value = manager.Value("i", 0)
        print(f"초기 합계: {shared_value.value}")

        producer = Process(target=produce, args=(shared_value, lock))
        consumer = Process(target=consume, args=(shared_value, lock))

        producer.start()
        consumer.start()

        producer.join()
        consumer.join()

        print(f"producer, consumer 프로세스 실행 이후 합계: {shared_value.value}")

-->
초기 합계: 0
producer, consumer 프로세스 실행 이후 합계: 0

공유 자원과 임계구역

여러 프로세스나 스레드가 공유하는 자원 공간을 공유 자원(shared resource)이라고 합니다. 계좌 문제나 생산자 소비자 문제에서 잔액 변수나 총합 변수에 공동의 자원을 두고 작업했습니다. 이러한 공간을 공유 자원이라고 합니다.
임계 구역이란 각 프로세스나 스레드에서 해당 공유 자원으로 접근하는 코드 영역을 임계구역이라고 합니다.
두 개 이상의 프로세스나 스레드가 임계 구역에 진입하고자 하면 둘 중 하나는 대기해야 합니다.
- 만약 대기하지 않고 동시에 임계 구역에 진입하여 코드를 실행한다면 문제가 발생할 수 있습니다. 이러한 문제를 경쟁 상태(Race Condition)라고 합니다.

동기화 기법

스핀락(Spinlock)과 뮤텍스 락(Mutext lock: MUTual Exclusion lock)

스핀락과 뮤텍스락은 비슷한 개념입니다. 둘의 가장 큰 차이점은 바쁜 대기를 하느냐 하지 않느냐의 차이입니다.
스핀락과 뮤텍스 락은 화장실을 갈 때 화장실 열쇠를 가지고 가는 것과 동일합니다. 공유 자원에 접근할 때 Lock을 획득(acquire)하게 되고, 공유 자원을 나오게 되면 Lock을 반환(release)하게 됩니다. 그러면 대기하고 있던 다른 프로세스나 스레드가 해당 Lock을 가지고 공유 자원에 들어가게 됩니다. 이러한 작업을 통해 공유 자원에 여러 프로세스나 스레드가 접근하지 못하게 하는 방법입니다.
생산자 소비자 문제에서 Lock을 이용해 동기화 문제를 해결했는데, 이 방식이 뮤텍스 락 방식입니다.
- with문으로 한 번에 표현했지만, lock.acquire()과 lock.release()로 나누어서 표현해도 됩니다. with문은 with문 집입시에 lock.acquire()이 되는 거고, with문을 탈출할 시에 lock.release()가 되는 것입니다.
- acquire() // 화장실 열쇠 있는지 확인, 열쇠가 있다면 열쇠를 가지고 화장실 가기
  임계구역 // 임계구역에서의 작업진행(화장실에서 작업 진행)
  release() // 화장실에서 나오면 열쇠를 반환
이러한 방식은 만약 해당 공유 자원이 lock 되어 있으면, 계속해서 공유 자원이 열려있는지 확인해야 합니다. (acquire() 함수에서 화장실 문이 열렸는지 계속해서 확인해야 함.) 이러한 대기 방식을 바쁜 대기(busy wait)라고 합니다.
- 이는 CPU를 낭비하는 것입니다.
- 여기서 아무런 작업을 하지 않으면 계속해서 lock이 풀렸는지 확인하는 것은 스핀락입니다.
- 하지만 lock이 풀렸는지 매번 확인하지 않고, 대기큐에 있다가 lock이 풀리게 됐을 때 대기큐에 알려줘서 실행하게 하는 방식이 뮤텍스 락입니다. (이러한 방식은 lock이 풀렸는지 계속해서 확인하지 않아도 되기 때문에 CPU를 낭비하지 않습니다.)

세마포어 (Semaphore) (카운팅 세마포어)

뮤텍스 락은 하나의 화장실이 있을 경우를 가정하고 만든 열쇠였습니다. 이에 반해 세마포어는 화장실이 여러 개인 것을 고려하여 만든 장치입니다.
사람들이 한 줄로 대기실에서 화장실칸이 여러 개 있는 화장실을 가기 위해 대기 중입니다. 이제는 열쇠가 아닌 전광판에 화장실 칸이 몇 개가 비어있는지 표시해 주는 장치가 설치되어 있습니다. 이럴 경우, 대기 중인 사람들은 대기실에 있는 전광판을 보고 화장실을 이용가능한지 확인하고 비어있다면 화장실에 가서 화장실을 이용할 수 있습니다.
- 컴퓨터를 예시로 들면, 세대의 프린터가 있을 때 여러 개의 프로세스가 해당 프린터를 사용하고 싶을 경우 몇 개의 프린터가 사용가능한지 확인하고 사용가능한 프린터개수가 있을 경우 해당 프린터기를 사용하면 됩니다. 만약 사용 가능한 프린터기가 없다면 대기하고 있으면 됩니다.
여러 프로세스가 공유자원을 사용하고 싶을 때, 사용가능한 공유자원 개수가 남았는지 확인하고 남아 있다면 임계구역에 진입하여 코드를 실행하면 됩니다. 만약 남아있지 않을 경우에는 임계 구역 앞에서 대기하고 있어야 합니다.
뮤텍스락은 전역변수 lock, acquire함수, release함수를 이용했습니다. 이에 반해 세마포어는 전역변수 S, wait 함수, signal 함수를 이용합니다.
- 전역변수 S는 화장실이 몇 칸 남았는지 알려주는 변수입니다.
  - 전역변수 S가 1이라면 이는 뮤텍스락과 비슷한 역할을 합니다. (S=1이면 이진(binary) 세마포어입니다.) 하지만 정확히 보면 차이점이 존재합니다. 아래 참고
- wait의 경우는 임계구역에 들어가도 될지, 기다려야 할지를 알려주는 함수입니다.
- signal은 화장실에서 사람이 나오면 이제 들어가도 좋다는 signal을 보내주는 함수입니다.
공유 자원 2개, 프로세스 3개인 경우 예시
- 바쁜 대기 현상 발생
  - 공유 자원이 2개 이므로 S=2로 시작
  - 프로세스 P1이 wait 호출, S>0이므로, 임계구역 진입 (S=1이 됨)
  - 프로세스 P2가 wait 호출, S>0이므로, 임계구역 진입 (S=0이 됨)
  - 프로세스 P3가 wait 호출, S=0이므로 무한히 반복하며 S가 0보다 커지는지 확인해야 함 (화장실 비어있는 칸을 표시해 주는 전광판을 계속해서 확인해야 함.)
  - 프로세스 P1이 임계 구역 작업 종료, signal() 호출하면서 S를 1 증가
  - 프로세스 P3는 S가 1이 되는 것을 확인하고, S를 1을 감소시키면서 임계구역에 진입
- 스핀락처럼 세마포어도 S가 0보다 큰지 계속해서 확인해야 하는 바쁜 대기(busy wait) 현상이 발생합니다. 세마포어는 이러한 CPU 낭비를 해결하기 위해 뮤텍스락처럼 세마포어를 위한 대기 큐를 사용합니다. (즉, 대기상태로 만들고, 작업이 끝난 프로세스가 대기 큐에서 준비큐로 옮겨줍니다.)
  - 공유 자원이 2개 이므로 S=2로 시작
  - 프로세스 P1이 wait 호출, S>0이므로, 임계구역 진입 (S=1이 됨)
  - 프로세스 P2가 wait 호출, S>0이므로, 임계구역 진입 (S=0이 됨)
  - 프로세스 P3가 wait 호출, S=0이므로 본인의 PCB를 대기 큐에 넣고 대기 상태로 전환합니다.
  - 프로세스 P1이 임계 구역 작업 종료, signal() 호출하면서 S를 1 증가시킵니다. 그 와 동시에 대기 상태였던 P3를 대기 큐에서 꺼내 준비 큐로 옮겨줍니다.
  - 깨어난 프로세스 P3는 임계 구역에 진입하게 됩니다.
세마포어를 이용하면 프로세스의 순서를 제어하는 것도 가능합니다. (실행 순서 제어를 위한 동기화)
- 먼저 세마포어의 변수 S를 0으로 두고 먼저 실행할 프로세스 뒤에 signal 함수, 다음에 실행할 프로세스 앞에 wait함수를 붙이면 됩니다. (즉, P1을 P2보다 먼저 실행하고 싶은 경우)
- 이 경우, P1이 먼저 실행되면 P1이 임계 구역에 먼저 진입하는 것은 당연한 거고, P2가 먼저 실행되더라도 P2는 wait에서 S가 0이므로 임계구역에 진입하지 못하고 대기상태가 됩니다. P1은 wait이 없기 때문에 바로 임계구역에 진입하게 됩니다.
- 따라서, 어떤 상황이서든지 P1이 P2보다 먼저 실행되게 됩니다.
- 예시로 생각해 보면 P1이 화장실 전광판(비어있는 칸이 없음으로)을 고장 내놓고, 자신만 전광판이 고장 나있다고 알고 있는 상태입니다. 따라서 자신은 고장 나있는 것을 알기 때문에 그냥 바로 화장실을 사용하러 들어가지만 다른 사람들은 그걸 모르기 때문에 대기해야 합니다. 그러다가 P1은 자기가 화장실을 다하고 나면 그제야 전광판을 정상적으로 돌려놓는 것입니다.

뮤텍스와 이진 세마포어의 차이

뮤텍스와 이진세마포어는 비슷해 보이지만 정확히 보면 같지 않습니다.
뮤텍스는 락을 가진 자만이 락을 해제할 수 있지만 세마포어는 그렇지 않습니다.
- 바로 위 예시만 보더라도 wait를 하는 프로세스와 signal을 보내는 프로세스가 다릅니다.
- 뮤텍스는 무조건 락을 가진 사람만이 락을 해제할 수 있습니다.
  - 따라서 누가 락을 해제할지 예측을 할 수 있습니다.
- 세마포어는 전광판이라 다른 사람이 조정이 가능하지만, 뮤텍스는 직접 키를 가져가기 때문에 키를 가져간 사람만이 해제할 수 있다고 생각하면 외우기 쉽습니다.
또 다른 차이점으로 뮤텍스는 priority inheritance(우선순위 상속) 속성을 가지지만 세마포어는 그 속성이 없습니다.
- 우선순위 상속이란?
  - 여러 프로세스나 스레드가 동시에 실행을 하게 되면 누굴 먼저 실행할지 스케줄링을 해야 합니다. 우선순위 상속은 스케줄링 기법 중 우선순위 스케줄링 기법에서 나오는 개념입니다. (선점형 우선순위 스케줄링)
  - 동기화를 진행하게 되면 우선순위가 이상해지는 현상이 발생합니다.
    - 예를 들어 아래그림처럼 P2가 다른 어떤 프로세스들보다 우선순위가 높지만 같이 동기화된 P1 프로세스가 Lock을 가지고 있어, P1이 끝날 때까지는 자기보다 낮은 우선순위의 작업들이 오더라도 실행을 하지 못하게 됩니다.
  - 이러한 현상을 방지하기 위해 우선순위가 높은 프로세스들에 대해서는 그 해당 동기화된 프로세스의 우선순위도 동일하게 높여주는 것을 우선순위 상속이라고 합니다. 우선순위를 할 경우 아래처럼 P2가 P3, P4보다 먼저 처리되는 것을 볼 수 있습니다.
- 그렇다면 뮤텍스락은 우선순위 상속 속성을 가지지만 세마포어는 왜 우선순위 상속 속성을 가지지 않을까요?
  - 이는 이제 위에서 설명했던 누가 락을 해제할지 알고 있는지 유무에 따른 것입니다.
  - 뮤텍스락의 경우 락을 가진 사람만이 락을 해제하지만, 세마포어의 경우 누가 락을 해제할지 모릅니다. 따라서 누가 락을 해제할 수 있는지 명확히 알 수 있는 뮤텍스락만이 우선순위 상속 속성을 가집니다.

모니터(monitor)

모니터는 조건에 따라 스레드가 대기(wating) 상태로 전환이 가능합니다.
- 화장실에서 변을 보는데 변이 너무나 안 나와서 일단 다른 사람에게 작업을 양보하다가 변비약을 가진 특정사람이 올경우에 다시 그 변비약을 먹고 변을 보는 것이 가능해지는 것입니다.
모니터는 여러 스레드와 협업을 할 때 사용할 수 있습니다.
모니터의 구성요소
- mutex lock
  - mutex lock이 없는 대기자들은 큐에 들어가서 대기 상태로 있습니다.
  - mutex lock이 있는 사람이 lock을 반환하면 큐에 대기상태로 있던 스레드 중 하나가 실행됩니다.
  - acquire / release
- condition variables
  - 조건이 충족되길 기다리는 스레드들이 대기 상태로 머무는 wating queue가 존재합니다.
  - 주요 동작
    - wait : thread가 자기 자신을 condition variable의 waiting queue에 넣고 대기 상태로 전환(자기가 기대한 조건이 아직 충족되지 않았을 때 wating queue로 들어가 조건이 올 때까지 기다림)
    - signal : waiting queue에서 대기 중인 스레드 중 하나를 깨웁니다.
    - broadcast : wating queue에서 대기 중인 스레드 전부를 깨웁니다.
- - entry queue : critical section에 진입을 기다리는 큐
  - wating queue : 조건이 충족되길 기다리는 큐
Bounded 생산자 소비자에서 모니터 사용
- Bounded 생산자 소비자란 생산자는 buffer가 꽉 차면 더 이상 생산하면 안 되고, 소비자는 buffer에 내용이 없으면 소비할 것이 없는 상태입니다. 따라서 이거를 매번 생산자는 buffer가 꽉 찼는지 확인하고, 소비자는 buffer에 내용이 있는지 확인해야 하면 CPU 낭비입니다. 따라서 이를 이제 조건을 통해서 해결이 가능합니다.
- 생산자는 버퍼가 가득 차면 lock을 반환하고 waiting queue에 들어간 뒤 버퍼가 소비되는 조건이 될 때까지 기다립니다. 소비자가 버퍼에서 값을 소비하면 그때 이제 signal을 발생시켜 waiting queue에서 생산자를 깨워줍니다.
- 마찬가지로 소비자도 버퍼를 계속 소비하다가 내용물이 없으면 내용물이 찰 때까지 waiting queue에 들어갑니다. 그 후 이제 생산자가 buffer에 내용물을 넣으면 signal을 발생시켜 소비자를 깨워줍니다.
- 여기서 중요한 점은 waitng queue에 들어갈 때 lock을 반환하고 wating queue에 있는 작업을 깨우고 lock을 반환한다는 것입니다.
모니터방식을 적용하지 않을 경우 Bounded 생산자 소비자에서 발생할 수 있는 문제
- 이런 방식(lock을 가진상태로 실행할 때 중간에 실행조건에 맞지 않을 경우 lock을 반환)을 적용하지 않을 경우에는 만약 q가 꽉 찼는데 생산자가 lock을 가지고 해당 함수를 진행하게 되면, 큐에 내용물이 꽉 차 while문을 통해 q를 소비하기까지 기다려야 합니다. 하지만 이 조차도 이제 lock을 가지고 있는 상태이기 때문에 소비자가 lock을 가질 수가 없어 절대 소비할 수 없는 상태가 되어버립니다.

파이썬 모니터 예시

멀티프로세스 모니터 예시

from multiprocessing import Process, Manager
from multiprocessing.managers import BaseManager

class Buffer:
    def __init__(self, capacity):
        self.capacity = capacity
        self.buffer = []
        self.lock = Manager().Lock()
        self.not_empty = Manager().Condition(self.lock)
        self.not_full = Manager().Condition(self.lock)

    def produce(self, item):
        with self.not_full:
            while len(self.buffer) == self.capacity:
                self.not_full.wait()
            self.buffer.append(item)
            print(f"Produced {item}")
            self.not_empty.notify()

    def consume(self):
        with self.not_empty:
            while not self.buffer:
                self.not_empty.wait()
            item = self.buffer.pop(0)
            print(f"Consumed {item}")
            self.not_full.notify()
            return item

def producer(buffer):
    for i in range(10):
        buffer.produce(i)

def consumer(buffer):
    for i in range(10):
        buffer.consume()

if __name__ == "__main__":
    BaseManager.register('Buffer', Buffer)
    manager = BaseManager()
    manager.start()
    buffer = manager.Buffer(2)
    
    p = Process(target=producer, args=(buffer,))
    c = Process(target=consumer, args=(buffer,))

    p.start()
    c.start()

    p.join()
    c.join()

멀티스레드 모니터 예시

import threading

class Buffer:
    def __init__(self, capacity):
        self.capacity = capacity
        self.buffer = []
        self.condition = threading.Condition()

    def produce(self, item):
        with self.condition:
            while len(self.buffer) == self.capacity:
                self.condition.wait()
            self.buffer.append(item)
            print(f"Produced {item}")
            self.condition.notify()

    def consume(self):
        with self.condition:
            while not self.buffer:
                self.condition.wait()
            item = self.buffer.pop(0)
            print(f"Consumed {item}")
            self.condition.notify()
            return item

# 예제 실행
def producer(buffer):
    for i in range(10):
        buffer.produce(i)

def consumer(buffer):
    for i in range(10):
        buffer.consume()

buffer = Buffer(2)
p = threading.Thread(target=producer, args=(buffer,))
c = threading.Thread(target=consumer, args=(buffer,))

p.start()
c.start()

p.join()
c.join()

출처

'Computer Science > 운영체제(Operating System)' 카테고리의 다른 글

가상 메모리 (0)	2024.04.05
교착상태(Deadlock) (0)	2024.04.05
CPU 스케줄링 (1)	2024.04.03
멀티프로세스와 멀티스레드 (0)	2024.04.02
프로세스와 스레드 (0)	2024.03.29

컴돈AI

동기화(Synchoronization)

동기화(Synchoronization)

동기화란?

생산자와 소비자 문제 (상호배제를 위한 동기화 예시)

공유 자원과 임계구역

동기화 기법

스핀락(Spinlock)과 뮤텍스 락(Mutext lock: MUTual Exclusion lock)

세마포어 (Semaphore) (카운팅 세마포어)

뮤텍스와 이진 세마포어의 차이

모니터(monitor)

출처

'Computer Science > 운영체제(Operating System)' 카테고리의 다른 글

티스토리툴바

동기화(Synchoronization)

동기화(Synchoronization)

동기화란?

생산자와 소비자 문제 (상호배제를 위한 동기화 예시)

공유 자원과 임계구역

동기화 기법

스핀락(Spinlock)과 뮤텍스 락(Mutext lock: MUTual Exclusion lock)

세마포어 (Semaphore) (카운팅 세마포어)

뮤텍스와 이진 세마포어의 차이

모니터(monitor)

출처

'Computer Science > 운영체제(Operating System)' 카테고리의 다른 글

관련글

티스토리툴바