[Computer Science] [운영체제] 동기화와 교착상태

동기화와 교착상태

동기화

동시다발적으로 실행되는 프로세스와 스레드의 실행 순서와 자원의 일관성을 보장해야 한다.

운영체제가 제공하는 동기화의 의미

• 실행 순서 제어: 프로세스를 올바른 순서로 실행하기 (실행 순서 제어를 위한 동기화)
  1. Book.txt가 없다면 파일을 만들고 값을 쓰고 저장하는 프로세스
  2. Book.txt를 읽어들이는 프로세스
  여기서 2번은 Book.txt가 있다는 조건이 만족되어야만 실행 가능
• 즉, 1 → 2 순으로 실행해야만 올바르게 실행된다.
• 상호 배제: 동시에 접근해서는 안되는 자원에 하나만 접근하기
  1. 2만원 입금 프로세스
     1. 잔액을 읽어들인다
     2. 잔액에 2만원을 더한다
     3. 더한 값을 저장한다
      
  2.  
  3. 5만원 입금 프로세스
     1. 잔액을 읽어들인다
     2. 잔액에 5만원을 더한다
     3. 더한 값을 저장한다
      
   

문제의 근본적인 발생 원인

• 동시에 접근해서는 안되는 자원에 접근했기 때문
• 상호 배제를 위한 동기화가 이루어지지 않았기 때문

동시에 접근해서는 안되는 자원

• 공유 자원: 공동의 자원 (e.g. 파일, 전역 변수, 입출력장치, ...)
• 임계구역:동시에 접근하면 문제가 발생할 수 있는 공유자원에 접근하는 코드

레이스 컨디션(race condition)

• 임계 구역을 동시에 실행하여 자원의 일관성이 깨지는 현상
• 이 레이스 컨디션은 코드 한 줄로도 발생할 수 있다.

아래 이미지를 보면 1씩 증가하거나 1씩 감소하는 코드인데 문맥 교환을 아래 처럼 진행하게 되는 경우 총합이 기대하는 값과 다르게 나오게 된다.

생산자와 소비자 문제

위에서 말한 프로세스와 스레드가 동기화되지 않았을 경우에 발생하는 문제들의 예시를 한 번 확인해보자.

• Producer: 생산을 하는 프로세스와 스레드를 의미한다. 데이터 생성 등
• Consumer: 소비를 하는 프로세스와 스레드를 의미한다. 데이터 읽기, 조작 등

코드로 보는 문제

아래 코드를 보면 produce와 consum이 있다.

공동으로 접근할 변수 sum이 있다. sum을 조작하는 코드가 임계구역이다.

아래 코드는 동기화를 하지 않았기에 결과가 예측대로 나오지 않는다. 또한 균일한 값이 출력되는 것이 아니라 다른 값이 계속 출력된다.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void* produce(void* arg);
void* consume(void* arg);

int sum = 0;

int main() {
    printf("초기 합계: %d\\n", sum);

    pthread_t producer_thread, consumer_thread;
    pthread_create(&producer_thread, NULL, produce, NULL); // produce 함수 실행
    pthread_create(&consumer_thread, NULL, consume, NULL); // consume 함수 실행

    pthread_join(producer_thread, NULL);
    pthread_join(consumer_thread, NULL);

    printf("실행 이후 합계: %d\\n", sum);

    return 0;
}

void* produce(void* arg) {
    for (int i = 0; i < 100000; i++) {
        sum++;
    }
}

void* consume(void* arg) {
    for (int i = 0; i < 100000; i++) {
        sum--;
    }
}

public class ProducerConsumer {

    private static int sum = 0;

    public static void main(String[] args) {
        System.out.println("초기 합계: " + sum);

        Thread producerThread = new Thread(new Producer());
        Thread consumerThread = new Thread(new Consumer());

        producerThread.start();
        consumerThread.start();

        try {
            producerThread.join();
            consumerThread.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("실행 이후 합계: " + sum);
    }

    static class Producer implements Runnable {
        @Override
        public void run() {
            for (int i = 0; i < 100000; i++) {
                sum++;
            }
        }
    }

    static class Consumer implements Runnable {
        @Override
        public void run() {
            for (int i = 0; i < 100000; i++) {
                sum--;
            }
        }
    }
}

뮤 텍스와 세마포어

상호 배제를 위한 동기화 도구로 Mutex lock, Semaphore가 있다.

동기화 해결의 세가지 원칙

1. 상호배제: 한 프로세스가 임계구역에 진입했다면 다른 프로세스는 대기해야 함
2. 진행 : 어떤 프로세스도 임계 구역에 진입하지 않았다면 진입이 가능해야 함
3. 유한대기: 한 프로세스가 임계구역 진입을 위해 대기하고 있다면 언젠간 진입이 가능해야 함

뮤텍스 락 (Mutex Lock)

공유하는 데이터가 여러개 스레드에서 접근하는 것을 방지하는 기법.

프로그래밍 언어에서 지원을 한다. 아래 사이트에서 확인 가능하다.

https://en.cppreference.com/w/cpp/thread/mutex, https://docs.python.org/3/library/asyncio-sync.html#asyncio.Lock

• 한 마디로 자물쇠(lock)
• 자물쇠 역할: 프로세스들이 공유하는 전역변수 lock
• 자물쇠 잠그기: acquire 함수
• 자물쇠 열기: release 함수

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void* produce(void* arg);
void* consume(void* arg);

int sum = 0;
pthread_mutex_t mutex;

int main() {
    printf("초기 합계: %d\\n", sum);

    pthread_t producer_thread, consumer_thread;
    pthread_mutex_init(&mutex, NULL);

    pthread_create(&producer_thread, NULL, produce, NULL);
    pthread_create(&consumer_thread, NULL, consume, NULL);

    pthread_join(producer_thread, NULL);
    pthread_join(consumer_thread, NULL);
    pthread_mutex_destroy(&mutex);

    printf("실행 이후 합계: %d\\n", sum);
    return 0;
}

void* produce(void* arg) {
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&mutex);
        sum++;
	pthread_mutex_unlock(&mutex);
    }
}

void* consume(void* arg) {
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&mutex);
	sum--;
	pthread_mutex_unlock(&mutex);
    }
}

세마포(semaphore)

세마포: 상호 배제 & 실행 순서 제어를 위한 동기화 도구

마찬가지로 아래 프로그래밍 언어 공식 문서에서 확인이 가능하다.

• https://en.cppreference.com/w/cpp/thread/counting_semaphore
• https://docs.python.org/3/library/asyncio-sync.html#asyncio.Semaphore
• 뮤텍스락은 기본적으로 공유자원이 하나일 경우 상정
• 세마포는 공유 자원이 여러 개 있을 경우도 동기화* 가능
• 실행 순서 제어, 상호 배제 동기화
• 가라는 신호를 받으면 (임계 구역에) 진입해도 좋다
• 멈추라는 신호를 받으면 (임계 구역에) 진입해서는 안된다

알고리즘

1. 변수S:임계구역에진입할수있는프로세스의개수(사용가능한공유자원의개수)
2. wait 함수: 임계구역에 들어가도 좋은지, 기다려야 할지를 알려주는 함수
3. signal 함수: 임계구역 앞에서 기다리는 프로세스에게 ‘이제 가도 좋다’고 신호를 주는 함수

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

void* produce(void* arg);
void* consume(void* arg);

int sum = 0;
sem_t semaphore;

int main() {
    printf("초기 합계: %d\\n", sum);

    // 세마포어 초기화. 세마포어 값은 1로 설정
    if (sem_init(&semaphore, 0, 1) != 0) {
        perror("세마포어 초기화 에러");
        exit(EXIT_FAILURE);
    }

    pthread_t producer_thread, consumer_thread;
    pthread_create(&producer_thread, NULL, produce, NULL);
    pthread_create(&consumer_thread, NULL, consume, NULL);

    pthread_join(producer_thread, NULL);
    pthread_join(consumer_thread, NULL);

    sem_destroy(&semaphore);

    printf("실행 이후 합계: %d\\n", sum);

    return 0;
}

void* produce(void* arg) {
    for (int i = 0; i < 100000; i++) {
        sem_wait(&semaphore);
        sum++;
        sem_post(&semaphore);
    }
    return NULL;
}

void* consume(void* arg) {
    for (int i = 0; i < 100000; i++) {
        sem_wait(&semaphore);
        sum--;
        sem_post(&semaphore);
    }
    return NULL;
}

 

1. 프로세스 P1 wait 호출. S는 현재 2이므로, S값을 1 감소시키고 임계구역 진입
2. 프로세스 P2 wait 호출. S는 현재 1이므로, S값 1 감소시키고 임계구역 진입
3. 프로세스 P3 wait 호출. S는 현재 0이므로, 무한히 반복하며 S값 확인
4. 프로세스 P1 임계구역 작업 종료, signal() 호출. S값 1 증가.
5. 프로세스 P3 S값이 1이 됨을 확인. S는 현재 1이므로, S값 1 감소시키고 임계구역 진입

• 실행 순서를 위한 동기화
• 먼저 실행할 프로세스 뒤에 signal을 붙이면 된다.
• 나중에 실행할 프로세스 앞에 wait을 붙이면 된다.

결론

• 생산자와 소비자 문제가 발생하지 않기 위해 Mutex Lock과 Semaphore 기법이 존재한다.
  • Mutex Lock은 말그대로 잠궈서 공유 데이터를 여러 스레드가 접근하는 것을 방지한다.
  • Semaphore은 프로세스 상태 전이를 활용하여 반복적으로 검사하는 것이 아닌 대기 상태와 준비 상태를 이용하여 상호 배제 & 실행 순서 제어를 위한 동기화 도구이다.

조건변수와 모니터

기존 동기화 도구(Mutex, Semaphore)는 문제점이 존재한다.

이러한 문제점을 해결하기 위해 사용이 간편한 동기화 도구가 나왔다.

모니터

• 공유 자원에 접근하기 위한 인터페이스
• 인터페이스를 통해서만 접근(상호 배제)
• 실행순서 제어를 위한 동기화를 위해 조건 변수(현재 프로세스의 상태를 변경하는 변수)를 사용
• wait(), signal()연산이 가능한 특별한 변수
• 프로세스 상태 전이가 가능한 특별한 변수
  • wait() : 호출한 프로세스를 대기 상태로 전환
  • signal() : 호출한 프로세스를 깨움
• 마찬가지로 프로그래밍 언어 공식 문서에서 확인이 가능하다.
  • https://docs.python.org/3/library/threading.html#condition-objects
  • https://en.cppreference.com/w/cpp/thread/condition_variable
  • https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Condition.html
• 조건 변수를 활용한 실행 순서 제어

1. 아직실행될조건이되지않았을때에는wait을통해실행중단
2. 실행될 조건이 충족되었을 때에는 signal을 통해 실행 재개

모니터를 활용하는 대표적인 프로그래밍 언어: Java

• synchronized 키워드

결론

기존 동기화 도구(Mutex, Semaphore)는 문제점이 존재하기 때문에 더 사용이 간편한 모니터 동기화 도구를 사용한다. 모니터는 인터페이스를 통해서만 접근이 가능하여 상호배제(동시에 접근해서는 안되는 자원에 하나만 접근하기) 문제를 최소화한다. 그리고 **실행 순서 제어(프로세스를 올바른 순서로 실행하기)**를 위해 현재 프로세스의 상태를 변경할 수 있는 조건 변수를 사용한다.

동기화 실습

같은 자원을 동시에 접근하는 코드를 작성해보면 매번 예측하지 못한 값이 출력되었다.

그것을 어떻게 해결할지 코드로 알아보자.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void* produce(void* arg);
void* consume(void* arg);

int sum = 0;
pthread_mutex_t mutex;

int main() {
    printf("초기 합계: %d\\n", sum);

    pthread_t producer_thread, consumer_thread;
    pthread_mutex_init(&mutex, NULL);

    pthread_create(&producer_thread, NULL, produce, NULL);
    pthread_create(&consumer_thread, NULL, consume, NULL);

    pthread_join(producer_thread, NULL);
    pthread_join(consumer_thread, NULL);
    pthread_mutex_destroy(&mutex);

    printf("실행 이후 합계: %d\\n", sum);
    return 0;
}

// mutex_lock을 통해 sum을 접근하기 전에 Mutex를 잠근한다. 그리고 임계구역을 벗어나면 unlock을 호출한다.
void* produce(void* arg) {
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&mutex);
        sum++;
	pthread_mutex_unlock(&mutex);
    }
}

// mutex_lock을 통해 sum을 접근하기 전에 Mutex를 잠근한다. 그리고 임계구역을 벗어나면 unlock을 호출한다.
void* consume(void* arg) {
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&mutex);
	sum--;
	pthread_mutex_unlock(&mutex);
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

void* produce(void* arg);
void* consume(void* arg);

int sum = 0;
sem_t semaphore; // semaphore 객체 생성

int main() {
    printf("초기 합계: %d\\n", sum);

    // 세마포어 초기화. 세마포어 값은 1로 설정
    if (sem_init(&semaphore, 0, 1) != 0) {
        perror("세마포어 초기화 에러");
        exit(EXIT_FAILURE);
    }
    
    // 스레드 생성
    pthread_t producer_thread, consumer_thread;
    pthread_create(&producer_thread, NULL, produce, NULL);
    pthread_create(&consumer_thread, NULL, consume, NULL);

    pthread_join(producer_thread, NULL);
    pthread_join(consumer_thread, NULL);

    sem_destroy(&semaphore);

    printf("실행 이후 합계: %d\\n", sum);

    return 0;
}

// 임계구역 접근전에 semaphore 호출.
void* produce(void* arg) {
    for (int i = 0; i < 100000; i++) {
        sem_wait(&semaphore);
        sum++;
        sem_post(&semaphore);
    }
    return NULL;
}

// 임계구역 접근전에 semaphore 호출.
void* consume(void* arg) {
    for (int i = 0; i < 100000; i++) {
        sem_wait(&semaphore);
        sum--;
        sem_post(&semaphore);
    }
    return NULL;
}

동기화가 상호 배제 문제와 실행 순서 문제 없이 잘 작동되어 예측한 값이 나오게 되었다.

 

 

 

교착상태

운영체제내에서 중요한 주제이다. deadlock

프로세스는 실행을 위해 자원이 필요하다 ..그런데 서로의 자원을 무한히 기다리기만 한다면? 🧐

서로 자원을 계속 기다리는 상황이 되어 프로세스 or 스레드가 실행되지 않는다.

식사하는 철학자 문제

• 대표적인 교착상태의 발생 조건 및 해결 방법을 위한 모델이다.
• N명의철학자,두개의포크로먹을수있는음식,원형테이블

• 철학자들의 식사 알고리즘
  • 계속 생각을 하다가, 왼쪽 포크가 사용 가능하면 집어든다.
  • 계속 생각을 하다가, 오른쪽 포크가 사용 가능하면 집어든다.
  • 왼쪽과 오른쪽 포크를 모두 집어들면, 정해진 시간동안 식사를 한다.
  • 식사 시간이 끝나면, 오른쪽 포크를 내려놓는다.
  • 오른쪽 포크를 내려놓은 뒤, 왼쪽 포크를 내려놓는다.
  • 1번부터 다시 반복한다.
• 만약 모든 철학자들이 동시에 포크를 집어드는 순간 누구도 식사를 할 수 없음
  • 서로의포크를계속바라만볼뿐
  • 철학자 == 프로세스(혹은 스레드)
  • 포크==실행을위해필요한자원

교착상태

즉, 교착상태란 일어나지 않을 사건(필요한 자원의 할당)을 기다리며 무한히 대기하는 현상

교착 상태 발생 조건

1. 상호배제
   1. 동시에 자원 사용이 불가능한 경우
2. 점유와 대기
   1. 자원을 할당받은 채 다른 자원의 할당을 기다리는 경우
3. 비선점
   1. 강제로 자원을 빼앗을 수 없는 경우
4. 원형대기
   1. 자원을 원형으로 대기할 경우

아래 이미지를 보면 파란선은 할당이고 빨간선은 할당을 기다리고 있는 상황이다.

교착상태 해결 방법

교착상태 예방

• 교착상태 발생 조건 네 가지 중 하나를 없애는 것이다.
• 교착 상태 발생 배경 원천 차단
• 교착상태가 발생하지 않음을 보장 할 수 있지만, 여러 부작용이 따르는 방식
• 상호 배제 조건 없애기
  • 자원을 공유 가능하도록 변경한다, 하지만 모든 자원에 대해 적용할 수 없다.
• 점유와 대기 조건 없애기
  • 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않는 방법이다.
  • 이러면 자원의 활용률이 저하가 된다.
• 비선점 조건 없애기
  • 선점하여 사용 가능한 자원에 대해서는 효과적이다.(CPU 스케줄링에서 이용)
  • 하지만 모든 자원에 대해 적용이 가능하지 않다.(프린터기)
• 원형 대기 조건 없애기
  • 자원에 번호 매기기
  • 오름차순으로 자원 할당한다. 하지만 이방법도 모든 자원에 번호를 매기기 어렵고 자원 번호가 높은 요소(우선순위가 낮은 요소)는 활용하기 어렵다.

교착상태 회피

• 교착 상태가 발생하는 이유를 자원의 무분별한 할당으로 간주한다.
  • 포크가두개있는상황에서여러개의자원을요구했다면?
• 교착 상태가 발생하지 않을 정도로만 조금씩 자원을 할당하는 방법이다.
• 아래 이미지를 보며 예시를 봐보자
• 현재 할당 가능한 자원은 12인데 사용량을 빼면 남은 자원은 3이다.

• 이때 P2의 최대 요구량을 사용한다면 11이 되니 가능하고 P2가 종료되면 총 5의 자원이 생긴다.

 

• 이러한 알고리즘을 교착 상태 회피를 판단하는 알고리즘의 대표적인 예시가 은행원 알고리즘이 있다.

교착상태 검출후회복

• 교착 상태가 발생하면 그때 회복하는 방식
  • 선점을 통한 회복
  • 프로세스 강제 종료를 통한 회복

교착상태 무시

• 사실 교착상태를 무시하는 경우도 있다.
• 타조 알고리즘이라 하는데 사실 이것은 좋지 않은 상황이다.

결론

교착상태는 프로세스들이 서로 필요한 자원을 점유한 채 다른 자원을 무한정 기다리는 현상이다.

이를 해결하기 위한 방법으로는 예방, 회피, 검출 후 회복, 무시가 있다.

예방은 교착상태 발생 조건을 제거하는 방법이지만 자원 활용도가 낮아지는 단점이 있고, 회피는 은행원 알고리즘과 같이 안전한 상태를 유지하며 자원을 할당하는 방법이다. 검출 후 회복은 교착상태 발생 시 선점이나 프로세스 종료를 통해 해결하며, 무시는 교착상태 해결 비용이 더 클 경우 선택하는 방법이지만 바람직하지 않다.