운영체제 - 프로세스 동기화

프로세스 동기화

경쟁 상태 (Race Condition)

2개 이상의 프로세스가 공유 자원을 병행해서 읽거나 쓰는 상황을 경쟁 조건이 발생했다고 한다.
여러 프로세스 또는 스레드에서 하나의 공유 자원에 접근하는 경우가 있는데, 이때 자원에 접근하는 순서에 따라 결과 값이 달라질 수 있다.

이러한 현상을 공유 자원에 동시에 접근해 경쟁하는 상태라고 해서 경쟁 상태라고 한다.
경쟁 상태의 문제를 해결하려면 프로세스 동기화가 이루어져야 한다.

임계영역 (Critical Section)

공유 자원에 접근할 수 있고, 접근 순서에 따라 결과가 달라지는 코드 영역을 임계 영역 이라고 한다.

임계 영역에서 경쟁 상태가 발생하는 것을 방지하려면, 여러 프로세스가 공유 자원에 접근해도 데이터의 일관성이 유지되도록 프로세스 동기화를 해야 한다.
임계구역에서는 프로세스들이 동시에 작업하면 안된다.

임계 영역에 여러 접근이 동시에 발생하는 것을 방지하기 위한 조건

• 상호배제 기법 (mutual exclusive)
  어떤 프로세스가 임계 영역을 실행 중일 때 다른 프로세스가 임계 영역에 접근할 수 없다.
  상호배제 기법으로는 뮤텍스와 세마포어가 있다.

• 진행의 융통성 (progress flexibility)
  임계 영역을 실행 중인 프로세스가 없을 때 다른 프로세스가 임계 영역을 실행한다.
  한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.

• 한정된 대기 (bounded waiting)
  임계 영역에 접근을 요청했을 때 무한한 시간을 기다리지 않는다.

< br />

• 동시성: 하나의 코어(싱글 코어)에서 여러 작업을 번갈아 가면서 처리하는 방식
  하나의 CPU에서 여러 작업을 번갈아 가면서 처리하기 위해 처리 중인 작업을 교체하는 것을 콘텍스트 스위칭이라고 한다.

• 병렬성: CPU가 여러 개(멀티 코어) 있어서 각 CPU에서 각 작업을 동시에 처리하는 방식

병행성(동시성)에 대해 설명해주세요.
병행성은 여러 작업을 번갈아가며 빠르게 수행시킴으로써 사용자가 다수의 작업이 동시 작동하는 것 처럼 느끼는 것을 말합니다.
여러 프로세스들을 번갈아가며 수행 시키면, 공유 자원에 대해 문제가 생길 수 있기 때문에 프로세스간 동기화 작업을 해줘야 합니다.

병렬성에 대해 설명해주세요.
실제 물리적으로 동시에 실행되는 것을 뜻합니다.
여러개의 CPU들이 동시에 멀티 쓰레드를 실행시키는 것을 예로 들 수 있습니다

프로세스 동기화에 대해 설명해주세요.
프로세스 동기화란, 협력하는 프로세스 사이에서 공유 자원의 일관성을 보장하는 것을 의미합니다.
프로세스가 공유 자원을 서로 사용하려고 하는 상황에서, Race Condition(경쟁 조건)을 방지하기 위해 특별한 규칙(Lock - 뮤텍스, 세마포어)을 만드는 것이 프로세스 동기화입니다.

Critical Section에 대해 설명해주세요.
Critical Section(임계 영역)은 공유자원에 접근할 수 있고, 접근 순서에 따라 결과가 달라지는 코드 영역을 말합니다.
공유 자원에 대한 동시 접근은 어떤 프로세스가 마지막에 공유 데이터를 다뤘는지에 따라 연산의 최종 결과가 달라지기 때문에 Critical Section에 대한 동기화 작업을 해줘야 합니다.

Race Condition이 무엇인가요?
Race Condition은 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황을 말합니다.
공유 데이터에 대한 동시 접근은 어떤 프로세스가 마지막에 공유 데이터를 다뤘는지에 따라 연산의 최종 결과가 달라지기 때문에 공유 데이터 접근에 대한 프로세스 동기화 작업을 해줘야 합니다.

Race Condition을 어떻게 해결할 수 있나요?
가장 간단한 방법은 한 순간에 하나의 프로세스나 쓰레드가 접근할 수 있도록 락(lock, 잠금)을 활용하는 것입니다.

Mutual Exclusion(상호배제 기법)에 대해 설명해주세요.
상호배제란, 특정 시점에 단 하나의 프로세스만이 Critical Section 즉 공유자원에 접근하게 하는 방법입니다.
공유 데이터에 대한 동시 접근은 어떤 프로세스가 마지막에 공유 데이터를 다뤘는지에 따라 연산의 최종 결과가 달라지기 때문에 상호배제를 통한 동기화 작업을 해줘야 합니다.

Mutual Exclusion을 할 수 있는 방법은 무엇인가요?
소프트웨어적으로는 프로세스 수행에 대한 순서번호 변수와 공유변수 사용 의사를 표현하는 변수들을 통해 상호배제를 구현할 수 있습니다.
대표적으로 피터슨 알고리즘이 있습니다.

하드웨어적으로는 읽기와 쓰기 작업이 원자적으로 실행되도록하면 상호배제를 보장할 수 있습니다.

또한 OS에서 지원하는 세마포어를 사용하거나 프로그래밍 언어 레벨에서 지원하는 모니터를 사용하여 상호배제를 구현할 수 있습니다.

피터슨 알고리즘

상호 배제를 위한 병렬 프로그래밍 알고리즘으로서, 공유 메모리를 활용하여 여러 개의 프로세스가 하나의 자원을 함께 사용할 때 문제가 발생하지 않도록 해준다.

bool flag[2]
int turn

flag[0] = false // false는 임계 구역 사용을 원하지 않음을 뜻함
flag[1] = true
turn = 0 // 0번 프로세스를 가리킴

P0: flag[0] = true
	turn = 1
    while(flag[1] && turn == 1) {
    	// flag[1]이 turn[1]을 가지고 있으므로 현재 사용중임
        // 임계 구역이 사용 가능한지 계속 확인
    } // 임계구역
    ...
    // 임계구역의 끝
    flag[0] = false

P1: flag[1] = true
	turn = 0
    while(flag[0] && turn == 0) {
    	// 임계 구역이 사용 가능한지 계속 확인
    } // 임계 구역
    ...
    // 임계 구역의 끝
    flag[1] = false

임계구역 보호 방법

뮤텍스

락(lock)을 가진 프로세스만이 공유 자원에 접근할 수 있게 하는 방법
예: 화장실 한 칸 문제

임계 영역에 접근한 프로세스가 임계 영역에 락을 건다고 해서 락킹 매커니즘이라고도 한다.
임계 영역에 접근하지 못한 프로세스는 락을 얻기 위해 기다리는 동안 락이 풀렸는지 반복문을 돌면서 확인한다.
이를 바쁜 대기의 한 종류인 스핀락이라고 한다.

프로세스가 대기 상태가 되지 않고 반복문을 돌면서 자원의 사용 가능 여부를 확인하므로, 프로세스가 빠르게 교체될 수 있다.

세마포어

공유 자원에 접근할 수 있는 프로세스의 수를 정해 접근을 제어하는 방법
예: 화장실 3개

임계 영역에 접근할 수 있는 키 n개를 지정하고, 이 중 하나를 가진 프로세스만이 임계 영역에 접근하게 하는 방식이다.
이 방식은 공유 자원에 접근한 프로세스가 접근을 해제하면 다른 프로세스가 접근할 수 있도록 신호를 보낸다고 해서 시그널링 매커니즘 이라고도 한다.

즉, 프로세스가 작업을 마치면 세마포어는 다음 프로세스에게 임계구역을 사용하라는 동기화 신호를 보낸다.
세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up() 신호를 받으면 큐에서 나와 임계구역에 진입한다.

세마포어에는 계수 세마포어, 이진 세마포어가 있다.

• 계수 세마포어
  n개의 자원을 locking하는 방법으로, 일반적으로 말하는 세마포어이다.

• 이진 세마포어
  1개의 자원을 locking하는 방법으로, 쓰레드가 자원을 사용시 Lock, 자원 반납시 unLock

동기: 여러 작업을 처리할 때 작업 순서를 보장함
비동기: 여러 작업을 처리할 때 작업 순서를 보장하지 않음
블로킹: 작업을 수행할 때 대기할 수 있다는 것을 의미하며, 작업 순서를 보장하지 않음
넌블로킹: 작업을 시작하면 대기 없이 수행한다는 것을 의미

모니터

모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화시킨다.

즉, 모니터는 시스템 호출과 같은 개념이다.
시스템 자원을 사용자로부터 숨기고 사용자 요구 사항을 처리할 수 있는 인터페이스만 제공하는데, 이것이 시스템 호출이다.

모니터는 프로세스의 요청을 모니터 큐에 넣은 후, 순서대로 실행하고 그 결과만 해당 프로세스에게 알려준다.
사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고, 시스템 입장에서는 임계구역을 보호할 수 있어서 좋다.

임계구역의 보호나 프로세스의 동기화가 모니터 내부에서 처리되므로 사용자는 시스템 호출만 하면 된다.

• 임계구역 보호 도구 중 모니터는 lock과 unlock, 동기화를 자동으로 처리하는 방식이다.

뮤텍스(Mutext)에 대해 설명해주세요.
뮤텍스는 공유 자원에 대해 Lockrhk UnLock을 수행함으로써 상호배제를 보장하는 방법입니다.
뮤텍스에서는 프로세스가 공유자원을 사용하기 위해서 Lock을 획득해야 합니다.
그리고 공유자원을 다 사용했다면, unLock을 해주어 다른 프로세스가 사용할 수 있도록 해줘야 합니다.
뮤텍스는 하나의 공유 자원에 대해 동기화를 수행한다는 점에서 이진 세마포어와 비슷합니다.

하지만 뮤텍스에서는 공유자원에 Lock을 걸었던 프로세스만이 Lock을 풀 수 있고, 이진 세마포어는 공유자원에 Lock을 걸었던 프로세스가 아니어도 Lock을 풀 수 있다는 차이가 있습니다.

세마포어란 무엇인가요?
공유 자원에 접근할 수 있는 프로세스의 수를 정해 접근을 제어하는 방법입니다.
임계 영역에 접근할 수 있는 키 n개를 지정하고, 이 중 하나를 가진 프로세스만이 임계 영역에 접근하게 하는 방식입니다.
공유 자원에 접근한 프로세스가 접근을 해제하면 다른 프로세스가 접근할 수 있도록 신호를 보낸다고 해서 시그널링 매커니즘 이라고도 합니다.
프로세스가 작업을 마치면 세마포어는 다음 프로세스에게 임계구역을 사용하라는 동기화 신호를 보냅니다.
세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up() 신호를 받으면 큐에서 나와 임계구역에 진입합니다.

세마포어에 대해 더 자세히 설명해주세요.
세마포어는 프로세스 동기화 기능을 제공해주는 추상 자료형입니다.
세마포어 자료형의 세마포어 변수는 자원의 개수를 나타내고 P연산과 V연산은 각각 공유 자원의 획득과 반납을 수행합니다.
P연산은 세마포어 변수를 하나 감소 시킵니다.
만약 이때 세마포어 변수가 음수가 되면 해당 프로세스를 세마포어의 블락큐로 이동시켜 대기하게 합니다.
V연산은 세마포어 변수를 하나 증가시킵니다.
만약 이때 블락큐에 대기하고 있던 프로세스가 있다면, 해당 프로세스를 깨우고 공유 자원을 획득하고 수행할 수 있도록 합니다.
Critical Section에 진입하기 전에 P연산을 통해 공유 자원을 획득하고, Critical Section에서 나오면서 V연산을 통해 공유 자원을 반납합니다.
프로그래머의 실수로, 세마포어의 P연산과 V연산을 잘못쓰게 되면 상호배제가 깨지거나 데드락이 발생할 수 있는 단점이 있습니다.
이런 문제는 고수준의 동기화 기능을 제공하는 모니터로 해결할 수 있습니다.

뮤텍스(Mutex)와 이진 세마포어의 차이에 대해 설명해주세요.
뮤텍스와 이진 세마포어의 핵심 차이는 뮤텍스의 경우 락을 설정한 프로세스만이 락을 해제할 수 있지만, 이진 세마포어의 경우 락을 설정한 프로세스와 해제하는 프로세스가 서로 다를 수 있습니다.

모니터에 대해 설명해주세요.
모니터는 프로그래밍 언어 수준에서 동기화 기능을 제공해줍니다.
모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화시킵니다.
즉, 모니터는 시스템 호출과 같은 개념입니다.
모니터는 프로세스의 요청을 모니터 큐에 넣은 후, 순서대로 실행하고 그 결과만 해당 프로세스에게 알려줍니다.
임계구역의 보호나 프로세스의 동기화가 모니터 내부에서 처리되므로 사용자는 시스템 호출만 하면 됩니다.

교착 상태(DeadLock)

상호배제 기법 때문에 2개 이상의 프로세스가 각각 자원을 가지고 있으면서 서로의 자원을 요구하며 기다리는 상태를 교착 상태라고 한다.

교착 상태는 아사 현상과 비슷해 보이지만 차이가 있다.
아사 현상은 잘못된 정책으로 특정 프로세스의 작업이 지연되는 문제인 반면, 교착 상태는 여러 프로세스가 작업을 진행하다 보니 발생하는 자연적인 현상이다.

아사 현상은 프로세스가 양보할 수 있는 상한선을 정하는 에이징으로 해결할 수 있다.
하지만 아사 현상과 달리 교착 상태는 정책상 잘못이나 오류가 없어도 자연적으로 발생한다.

컴퓨터 시스템에서 교착 상태는 시스템 자원을 사용하거나 잠금을 사용할 때 발생할 수 있다.

교착 상태가 발생하는 필요 충분 조건 4가지

• 상호배제 (mutual exclusion)
  하나의 공유 자원에 하나의 프로세스만 접근할 수 있다.

• 점유와 대기 (hold and wait)
  프로세스가 최소 하나의 자원을 점유하고 있는 상태에서 추가로 다른 프로세스에서 사용 중인 자원을 점유하기 위해 대기한다.

• 비선점 (non-preemption)
  다른 프로세스에 할당된 자원을 뺏을 수 없다.

• 환형 대기 (circular wait)
  점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.
  프로세스가 자신의 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구한다.

교착 상태를 막으려면 4가지의 필요 충분 조건 중에서 한 가지를 제거하면 된다.

교착 상태 예방

• 상호배제 부정
  여러 프로세스가 동시에 하나의 공유 자원을 사용할 수 있게 한다.
  하지만 상호 배제를 무력화하기는 사실상 어렵다.

• 점유와 대기 부정
  프로세스가 실행되기 전에 필요한 모든 자원을 할당함으로써 프로세스 대기를 없앤다.
  또는 프로세스가 자원을 점유하지 않은 상태에서만 자원을 요구하게 한다.
  하지만 프로세스가 자신이 사용하는 모든 자원을 자세히 알기는 어려우며, 자원의 활용성이 떨어진다.
  또한, 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하며 결국 일괄 작업 방식으로 동작하게 된다.

• 비선점 부정
  자원을 점유한 프로세스가 다른 자원을 요구할 때 점유한 자원을 반납하게 한다.
  하지만 아사 현상이 발생할 수 있으며 아사 현상 해결을 위해 에이징을 사용하는 것은 다시 교착 상태에 빠질 수 있어 힘들다.

• 원형 대기 부정
  자원을 선형 순서로 정렬해 고유 번호를 할당한다.
  그리고 각 프로세스에서 요구할 수 있는 번호의 방향을 정해서 한쪽 방향으로만 자원을 요구하게 한다.
  하지만 자원에 번호를 어떻게 부여할지가 문제이며, 프로세스 작업 진행에 유연성이 떨어지게 된다.

교착 상태 회피

교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어 주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법이다.
교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.

자원을 많이 할당할 수록 교착 상태가 발생할 확률이 커진다.
교착 상태 회피에서는 자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고, 시스템이 안정 상태를 유지하도록 자원을 할당한다.

즉, 교착 상태 회피에서는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피한다.

• 안정 상태
  각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우

• 불안정 상태
  각 프로세스의 기대 자원과 비교하여 가용 자원이 더 작을 경우가 한 번 이상인 경우

하지만 다음과 같은 문제가 있어서 실제 시스템에서는 교착 상태 회피를 사용하지 않는다.

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
• 시스템의 전체 자원 수가 고정적이어야 한다.
• 자원이 낭비된다.
  자원이 충분한데도 안정 상태에 맞추어 자원 할당을 조금만 하는 것은 자원 낭비다.

교착 상태 검출

[ 타임아웃 ]

타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다.
타임아웃을 이용하는 방법을 가벼운 교착 상태 검출 이라 하고, 자원 할당 그래프를 이용하는 방법을 무거운 교착 상태 검출 이라 한다.

윈도우에서 '프로그램 응답이 없어 종료합니다.'라는 메시지는 타임아웃을 이용한 방법의 대표적인 예이다.

하지만 타임아웃을 이용한 방식에는 다음과 같은 문제가 있다.

• 엉뚱한 프로세스가 강제 종료될 수 있다.
• 모든 시스템에 적용할 수 없다.
  분산 데이터베이스는 데이터가 여러 시스템에 나뉘어 있고, 각 시스템이 네트워크로 연결되어 있다.
  이러한 시스템에서는 원격지에 있는 프로세스의 응답이 없는 것이 교착 상태 때문인지, 네트워크 문제 때문인지, 단순히 처리가 늦어지는 것인지 정확히 알 수 없다.
  그러므로 타임아웃 방법을 적용하여 교착 상태를 파악하기 어렵다.

[ 자원 할당 그래프 ]

자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지를 알 수 있다.
자원 할당 그래프를 이용하여 교착 상태를 검출하는 방법은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 장점이 있다.

그러나 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 인해 오버헤드가 발생한다는 단점이 있다.

교착 상태 회복

교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데, 이를 교착 상태 회복이라 한다.
교착 상태 회복 단계는 교착 상태를 유발한 프로세스를 강제로 종료한다.

다음과 같은 두 가지가 있다.

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료한다.
  종료된 프로세스들이 동시에 작업을 시작하면, 다시 교착 상태를 일으킬 가능성이 크다.
  모든 프로세스를 강제로 종료한 후, 다시 실행할 때는 순차적으로 실행해야 한다.

• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료한다.
  프로세스 종료 순서를 정할 때는 다음과 같은 기준이 필요하다.

  • 우선순위가 낮은 프로세스를 먼저 종료한다.
  • 우선순위가 같으면 작업 시간이 짧은 프로세스를 먼저 종료한다.
  • 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스를 먼저 종료한다.

교착 상태 회복 단계에서는 관련 프로세스를 강제로 종료하는 일 뿐 아니라 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야한다.
s
시스템 복구는 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 식으로 한다.

데드락이 무엇인가요?
상호배제 기법 때문에 2개 이상의 프로세스가 각각 자원을 가지고 있으면서 서로의 자원을 요구하며 기다리는 상태를 교착 상태라고 합니다.

데드락 발생 조건 4가지를 설명해주세요.
상호 배제, 점유와 대기, 비선점, 환형 대기가 있습니다.
상호 배제는 하나의 공유 자원에 하나의 프로세스만 접근할 수 있다는 것이며,
점유와 대기는 프로세스가 최소 하나의 자원을 점유하고 있는 상태에서 추가로 다른 프로세스에서 사용 중인 자원을 점유하기 위해 대기하는 것입니다.
비선점은 다른 프로세스에 할당된 자원을 뺏을 수 없는 것이며, 환형 대기는 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다는 것입니다.

데드락을 막는 방법에 대해 설명해주세요.
교착상태 예방으로는 교착 상태 발생 조건 4가지 중 하나라도 만족되지 않도록 만드는 것입니다.
교착상태 회피로는 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시켜 교착 상태를 피하는 것입니다.
교착상태 검출 후 회복으론 타임아웃이나 자원 할당 그래프를 활용해 교착 상태를 검출하고, 교착 상태를 일으킨 프로세스를 종료해서 교착 상태를 회복합니다.