혼자 공부하는 컴퓨터 구조 + 운영체제 Chapter 12

안녕하세요! 제이덥입니다~ 저는 학부 때 공부했던 CS 기초 내용을 Wrap-Up 하기 위해 혼공학습단 11기 활동을 진행하고 있는데요. 이제 5주째가 되니 어느정도 개념을 다시 정리한 느낌이 듭니다.
이번 포스팅에서는 Chapter 12 프로세스 동기화에 대해 다룹니다. 동기화란 무엇인지, 어떤 기법이 있는지 정리했습니다. 특히, CS 면접 기출 문제로 많이 나오니 이 글을 보시는 분도 세세하게 살펴보시는걸 추천드립니다.
해당 도서는 제가 직접 구매하여 글을 작성한 것이며, 혼공단 11기 활동의 일환으로 학습 내용에 대한 공유 글을 작성하게되었음을 알려드립니다. 도서에 대한 자세한 내용과 활동에 대한 내용을 알고 싶은 분들은 아래 Reference에서 확인해주세요~

Chapter 12. 프로세스 동기화

1️⃣ 동기화의 의미

• 동기화(synchronization)란
  • 동기화의 정의 : 동시 다발적으로 실행되는 프로세스들은 공동의 목적을 올바르게 수행하기 위해 서로 협력하여 영향을 주고 받는데, 이렇게 형력하여 실행되는 프로세스들의 실행 순서와 자원의 일관성을 보장해주는 것.
    • ex : 워드 프로레스의 동기화각각 모두 독립적인 프로세스이지만 '워드 프로세스'라는 프로그램을 위해 긴밀하게 협력함
    • 입력을 받는 프로세스 → 맞춤법을 검사해주는 프로세스 → 화면에 출력해주는 프로세스
  • 프로레스 동기화의 정의(feat. 국어사전) : 프로세스의 동기화란 작업들 사이에 수행시기를 맞추는 것,
  • 프로세스 동기화 방법 2가지
    • 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
    • 상호 배제: 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기
      📌 프로세스 뿐만 아니라 스레드도 동기화의 대상임!! 흐름을 갖는 모든 것은 동기화의 대상이 됨
  • 실행 순서 제어를 위한 동기화 예시
    • Writer Process, Reader Process가 동시에 실행된다는 가정
    • Writer Process : Book.txt에 값을 저장하는 프로세스
    • Reader Process : Book.txt의 값을 읽어오는 프로세스
      
    • 이 두 프로세스가 동시에 실행된다고 한다면, writer 프로세스가 Bootk.txt에 값을 적기도 전에 읽어 오면 안됨. 즉, Reader 프로세스는 Book.txt에 값이 존재한다라는 조건이 있고, 이러한 조건에 맞추어 순서가 생김 ⇒ 프로세스 동기화는 올바른 실행 순서를 갖추는 것
  • 상호 배제를 위한 동기화 예시
    • 상호배제(mutual exclusion) : 공유가 불가능한 자원을 동시에 사용하는 것을 피하기 위해 고안된 알고리즘
    • 은행 계좌 프로그램에서 계좌에 10만원이 있을 때, 프로세스 A는 5만원을 입금하는 프로세스, 프로세스 B는 2만원을 입금하는 프로세스라고 가정

      실행순서	프로세스 A	프로세스 B
      1	계좌의 잔액을 읽어 들인다.	계좌의 잔액을 읽어 들인다.
      2	읽어 들인 잔액에 5만원을 더한다.	읽어 들인 잔액에 2만원을 더한다.
      3	더한 값을 저장한다.	더한 값을 저장한다.

    • 상호배제가 이루어지지 않았을 때
      
      
    • 상호배제가 이루어졌을 때
      
      
    • 이와 같이 '잔액' 이라는 공유 자원을 접근할 때 다른 프로세스가 함께 접근하면 연산 및 저장 과정에서 문제가 생길 수 있음 ⇒ 동시에 접근하면 안되는 공유 자원을 접근하지 못하게 하는 것이 상호배제를 말함
• 생산자와 소비자의 문제 :: 상호 배제 동기화에 대해 깊게 알기
  • 생산자와 소비자 문제의 가정: 생산자와 소비자 문제는 물건을 계속해서 생산하는 프로세스인 생산자와 물건을 계속해서 소비하는 프로세스인 소비자가 존재
  • 문제 예시
    • 공유자원 : 총합
    • 생산자 : 버퍼에 물건을 넣은 후 물건의 총합 변수에 +1
    • 소비자 : 버퍼에 물건을 빼낸후 물건의 총합 변수에 -1
    • 코드 : 생산자, 소비자 프로세스 100000번 실행

#include<iostream>
#include<queue>
#include<thread>

void produce();
void consume();

std::queue<int> q;
int sum = 0 ;

int main(){
	std::cout << "초기 합계: " <<  sum << std::endl;
	std::thread producer(produce);
	std::thread consumer(consume);
	
	producer.join();
	consumer.join();
	
	std::cout << "producer, consumer 스레드 실행 이후 합계: " <<  sum << std::endl;

}

void produce() {
	  for(int i = 0; i < 100000; i++) {
	      q.push(1);
	      sum++;
	  }
}
void consume() {
    for(int i = 0; i < 100000; i++) {
        q.pop();
        sum--;
    }
}

• 실행결과 :
  
• 결론 & 해석: 우리가 기대하는 건 소비자, 생산자가 같은 숫자만큼 반복되었으니 총합이 10으로 유지되길 예상하지만, 전혀 다른 결과가 나왔다. 이는 공유자원에 접근 프로세스를 제한하지 않아, 미처 이전 프로세스가 저장되기 전에 실행되고 저장되는 것을 반복해 문제가 발생 ⇒ 동시에 접근하면 안되는 자원에 동시에 접근하여 발생

• 공유 자원과 임계 구역
  • 공유자원(shared resource) : 두 개 이상의 프로세스가 접근할 수 있는 자원이며, 동시에 접근해서는 안되는 자원을 말한다. 공유 자원은 전역 변수, 파일, 입출력장치, 보조기억장치가 될 수 있다.
  • 임계 구역(critical section) : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
  • 레이스 컨디션(race condition) : 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 것
    • 레이스 컨디션이 발생하는 근본적인 이유 : 컴퓨터는 고급 언어가 아닌 저급언어를 실행하는되, 고급 언어 한줄을 실행하는 과정에서 문맥 교환이 일어나고 이는 잘못된 레지스터 값을 저장할 수 있는 여지를 줌
  • ⇒ 데이터의 일관성이 깨지게 됨.
  • Race Condition을 해결하기 위한 세가지 조건
    • 상호 배제(mutual exclusion) : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없음
    • 진행(progress) : 임계 구역에 어떤 프로세스도 진입 X ⇒ 임계 구역에 진입하려는 프로세스는 진입 가능
    • 유한 대기(bounded waiting) : 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가 임계 구역에 등어올 수 있어야 함.(무한정 대기 X)

2️⃣ 동기화 기법

크게 뮤텍스 락, 세마포, 모니터

• 뮤텍스 락(Mutex-lock;MUTual EXclusive lock)
  • 공유자원을 체크하고, 이용하는 프로세스가 없으면 이용하는 자물쇠 방식
  • 뮤텍스 락이란 동시에 접근해서는 안되는 자원에 동시에 접근하지 않도록 만드는 도구, 상호 배제를 위한 동기화 도구
  • 임계 구역에 자물쇠를 걸어 '내가 임계구역에 있음'을 알리고, 임계 구역이 잠겨있다면 기다림
  • 구현 방법
    • 자물쇠 역할 : 프로세스들이 공유하는 자물쇠 변수 lock
    • 임계 구역을 잠그는 역할 acquire 함수
    • 임계 구역을 해제하는 역할 release 함수
  • acquire 함수
    • 프로세스가 임계 구역에 진입하기 전에 호출
    • lock이 false가 될 때까지 지속적으로 확인, 만약 열려있다면 lock을 true 바꿔 임계구역을 잠금.
    • ⇒ 지속적으로 확인하는 방식을 바쁜 대기(busy wait)라고 부름
  • release 함수
    • 임계 구역에서 작업이 끝나면 호출
    • 현재 잠긴 임계 구역을 열어주는 함수
  • C/C++/python 과 같은 연어에서 해당 기능을 제공
    • mutex를 이용한 동기화예시

#include <stdio.h>
#include <pthread.h>
#define NUM_THREADS 4
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int shared = 0;
void *foo(){
    pthread_mutex_lock(&mutex);
    for (int i = 0; i < 10000; ++i) {
        shared += 1;
    }
    pthread_mutex_unlock(&mutex);
    return NULL;
}
int main(){
		pthread_t threads[NUM_THREADS];
    for (int i = 0; i < NUM_THREADS; ++i) {
        pthread_create(&threads[i], NULL, foo, NULL);
    }

    for (int i = 0; i < NUM_THREADS; ++i) {
        pthread_join(threads[i], NULL);
    }
    printf("final result is %d\n", shared);
    return 0;
}

• 세마포(semaphore)
  • 뮤텍스 락과 비슷하지만, 조금 더 일반화된 방식의 동기화 도구 ⇒ 공유 자원이 여러개 있을 때 적용이 가능한 동기화 도구
    • 세마포에도 두가지 종류가 존재
      • 이진 세마포(binary semaphore) : 뮤텍스락과 유사함
      • 카운팅 세마포(counting semaphore) : 여러 공유 자원을 다룰 수 있는 세마포
  • 구현 방법
    • 전역 변수 S : 임계 구역에 진입할 수 잇는 프로세스 개수(사용 가능한 공유 자원의 개수)를 나타냄
    • wait 함수 : 임계 구역에 진입해도 되는지, 대기 해야할지 알려줌
    • signal 함수 : 임계 구역에 진입하기 위해 대기하는 프로세스에게 진입해도 된다는 신호를 주는 함수
  • 뮤텍스와 비교한 세마포의 장점 :
    • 뮤텍스는 바쁜 대기(busy wait)을 이용하지만 이는 CPU 자원을 낭비한다는 단점이 있음원리 : wait함수는 사용할 수 있는 자원이 없을 경우 프로세스를 대기 상태로 만들고, PCB에 세마포를 위한 queue에 집어넣음 ⇒ 다른 프로세스가 임계 구역에서 작업이 끝나고 signal 함수 호출 ⇒ 대기 중인 프로세스를 대기 큐에서 제거하고 준비 큐로 이동하여 실행 준비 ⇒ wait과 signal을 통해 해결
  • Python 코드

from threading import Thread, Semaphore

num = 0
sem = Semaphore(1)

def foo():
	global num
	sem.acquire()
    for _ in range(100000):
        num += 1
	sem.release()
    
if __name__ == '__main__':
    t1 = Thread(target=foo, args=(sem,))
    t2 = Thread(target=foo, args=(sem,))

    t1.start()
    t2.start()

    print(num)

• 모니터(monitor)
  • 세마포 단점 : 매번 임계 구역에 앞뒤로 일일이 wait와 signal 함수를 명시하는 것은 번거로울 수 있고, 잘못된 코드를 적어 넣을 경우 예상하지 못한 문제가 발생할 수 있음
  • 동기화
    • 공유 자원과 공유 자원에 접근하기 위한 인터페이스를 묶어서 관리
    • 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고 큐에 삽입된 순서대로 하나씩 공유자원을 이용하도록 함 ⇒ 공유자원을 다루는 인터페이스에 접근하기 위한 큐를 이용해 동기화
    • 조건 변수(condition variable) : 특정 조건을 바탕으로 프로세스를 실행하고 일 시 중단하기 위한 변수 ⇒ 프로세스나 스레드의 실행 순서를 제어 + 이를 이용해 wait/signal 연산 수행 가능
  • 자원 접근 할당:
    • 프로세스는 실행을 위해 자원을 필요로 하는데 이러한 자원을 접근하고, 조작하여 프로세스에 필요한 자원을 할당함
    • CPU : CPU 스케줄링을 이용하여 효율적으로 CPU를 관리
    • 메모리 : 프로세스에 메모리를 할당하고, 삭제 + 메모리가 부족할 경우 이를 해결
    • 입출력 장치 : 커널 영역의 인터럽스 서비스 루틴을 통해 입출력 장치 제어
  • 모니터 C/C++ 코드:

public class BoundedBuffer<E>{
    private static final int BUFFER_SIZE = 5;
    private E[] buffer;

    public BoundedBuffer() {
        count = 0;
        in = 0;
        out = 0;
        buffer = (E[]) new Object[BUFFER_SIZE];
    }

    /* 생산자가 호출하는 코드 */
    public synchronized void insert(E item) {
        while (count == BUFFER_SIZE) {
            try {
                wait();
            }
            catch (InterruptedException ie) {}
        }

        buffer[in] = item;
        in = (in + 1) % BUFFER_SIZE;
        count++;

        notify();
    }

    /* 소비자가 호출하는 코드 */
    public synchronized E remove() {
        E item;

        while (count == 0) {
            try {
                wait();
            }
            catch (InterruptedException ie){}
       }

       item = buffer[out];
       out = (out + 1) % BUFFER_SIZE;
       count--;
       notify();

         return item;
      }
}

Reference :

• 혼자 공부하는 컴퓨터구조 + 운영체제
• 혼공학습단 11기 활동
• 혼자 공부하는 컴퓨터구조+운영체제 GitHub