[운영체제] 프로세스 동기화

JSCODE 모의면접 스터디
운영체제 6기 4주차

목차

 

1. 프로세스의 병행성과 병렬성

병행성(Concurrency, 동시성)

여러 작업이 동시에 실행되는 것처럼 보이는 것으로, 프로그램(논리적 수준)이 작업을 처리하는 방식입니다.

• 싱글 코어에서는 시분할(Time-Sharing) 방식으로 CPU를 나누어 사용하여 동시 실행되는 것처럼 처리
• 멀티 코어에서도 실행 가능하며, 이 경우 실제 병렬 처리도 가능
• 작업 전환 시 Context Switching이 발생하여 현재 작업 상태를 저장하고 다음 작업을 불러옴

 

병렬성(Parallelism)

여러 작업이 실제로 동시에 처리되는 것으로, 실제 CPU의 물리적인 코어(물리적 수준)를 여러 개 사용하여 동시에 처리하는 방식이다. 

오직 멀티 코어에서만 동작이 가능하다.

 

병렬성 종류

• 데이터 병렬성(Data Parallelism): 동일한 작업을 서브 데이터로 나눠 동시에 처리
• 작업 병렬성(Task Parallelism): 서로 다른 작업을 동시에 처리

 

 

2. 프로세스 동기화

동기화 (Synchronization)

프로세스 동기화는 여러 프로세스가 공유하는 자원의 일관성을 유지하기 위해 프로세스들의 실행 시기를 제어하는 것이다. 여러 프로세스가 서로 협력해 공유자원을 사용하는 상황에서 Race Condition이 발생하면 공유자원의 신뢰성이 떨어진다. 이를 방지하기 위해 실행 순서 제어와 상호 배제라는 두 가지 형태로 동기화가 이루어진다.

 

동기화 종류

• 실행 순서 제어: 프로세스를 올바른 순서대로 실행
• 상호 배제: 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하도록 제어

 

상호 배제 (Mutual Exclusion)

상호 배제는 동기화의 한 형태로, 여러 프로세스가 공유 자원에 동시에 접근하는 것을 막는 것이다. 한 프로세스가 공유 자원을 사용하는 동안 다른 프로세스가 그 자원을 사용하지 못하도록 제어하는 방법이다.

 

필요성

• 데이터의 일관성 유지
• Race Condition 방지
• 프로세스 간 충돌 방지

 

Race Condition

Race Condition은 여러 프로세스가 공유 데이터에 동시에 접근할 때 실행 순서에 따라 결과가 달라질 수 있는 상황이다. 프로세스들이 공유 데이터에 대해 동시 접근이 가능하고, 실행 순서가 예측 불가능하기 때문에 발생한다. 공유 데이터의 동시 접근은 데이터의 일관성을 해칠 수 있다.

 

발생 상황

• 커널 모드 수행 중 인터럽트 발생 시 커널 데이터 접근
• 프로세스가 시스템 콜로 커널 모드 수행 중 문맥 교환으로 인한 커널 데이터 접근
• 멀티프로세서에서 공유 메모리 내 커널 데이터 접근

 

Race Condition의 해결 방법

Race Condition을 해결하기 위해서는 프로세스들의 공유 데이터 접근을 체계적으로 관리해야 한다.

공유 데이터를 접근하는 코드 영역을 임계 구역(Critical Section)으로 지정하고, 한 번에 하나의 프로세스만 접근할 수 있도록 제어하여 데이터의 일관성을 보장한다.

 

임계 구역 (Critical Section)

임계 구역은 여러 프로세스가 공유하는 데이터를 접근하는 코드 영역이다.(코드 영역 > 임계 구역) 즉, 코드 상에서 Race Condition이 발생할 수 있는 특정 부분을 말한다.

 

임계 구역의 구성

• Entry Section: 임계 구역 진입 전 진입 허가를 요청하는 부분
• Critical Section: 실제 공유 데이터를 접근하고 수정하는 부분
• Exit Section: 임계 구역을 벗어나면서 다음 프로세스가 진입할 수 있도록 퇴출을 알리는 부분
• Remainder Section: 임계 구역과 무관한 나머지 코드 부분

 

임계 구역 문제 해결을 위한 3가지 조건

• 상호 배제(Mutual Exclusion): 한 프로세스가 임계 구역에서 실행 중이면 다른 프로세스는 진입 불가
• 진행(Progress, Deadlock 회피): 임계 구역에 프로세스가 없다면 진입 요청한 프로세스가 진입 가능
• 한정 대기(Bounded Waiting, Starvation 회피 ): 프로세스의 임계 구역 진입 요청 후 무한정 대기하지 않음 (언젠가는 임계 구역에 진입)

 

동기화 기법의 필요성

동기화 기법은 임계 구역 문제를 해결하기 위해 상호 배제를 구현하는 방법이다.

즉, 임계 구역 문제를 해결하기 위한 3가지 조건은 "무엇을 만족해야 하는가"이고, 동기화 기법은 "어떻게 구현할 것인가"를 정의하는 방법이다.

 

 

3. 동기화 도구

동기화 도구는 동기화 기법을 실제로 구현하기 위해 사용하는 구체적인 프로그래밍 도구나 메커니즘을 의미한다.

뮤텍스 (Mutex)

뮤텍스는 임계 구역을 보호하고 Race Condition을 방지하기 위한 잠금 메커니즘으로, 공유 자원에 대한 접근을 제어하는 자물쇠 역할을 한다. 0(잠금 해제)과 1(잠금)의 두 가지 상태만 가지는 가장 단순한 형태의 동기화 도구이다.

 

구성 요소

• 전역 변수 lock: 자물쇠 역할을 하는 프로세스들의 공유 변수
• acquire(): 임계 구역을 잠그는 역할
• release(): 임계 구역의 잠금을 해제하는 역할

 

동작 방식

1. 임계 구역 진입 전: acquire() 호출
   • 임계 구역이 잠겨있으면 열릴 때까지 반복 확인
   • 임계 구역이 열려있으면 잠금 (lock을 1로 변경)
2. 임계 구역 작업 완료 후: release() 호출
   • 임계 구역의 잠금을 해제 (lock을 0으로 변경)

 

Buzy Waiting

acquire() 함수에서 프로세스가 임계 구역에 진입하기 위해 락(lock)을 획득할 때까지 반복적으로 확인하는 상태이다. CPU 자원을 낭비하는 단점이 있다.

 

세마 포어 (Semaphore)

세마포어는 카운터를 이용하여 공유 자원에 접근할 수 있는 프로세스의 수를 제한하는 동기화 도구이다. 여러 프로세스나 스레드가 임계 구역에 진입할 수 있는 신호 메커니즘으로, Block & Wakeup 방식을 사용하여 Busy Waiting 문제를 해결한다. (프로세스를 대기 큐에서 대기하도록 하여(Block) CPU 자원을 낭비하지 않고, 필요할 때 깨우는(Wakeup) 방식)

 

프로세스 간 동기화뿐만 아니라 스레드 간 동기화에도 사용 가능하며, 카운팅 세마포어를 통해 여러 자원에 대한 접근 제어가 가능하다.

 

종류

• 이진 세마포어: 0과 1 두 가지 값만 가짐, 한 개의 자원을 다루는 경우 사용 (뮤텍스와 유사)
• 카운팅 세마포어: 여러 개의 값을 가질 수 있으며, 여러 개의 자원을 다루는 경우 사용

 

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

뮤텍스와 이진 세마포어는 모두 공유 자원에 대한 접근을 제어하는 동기화 도구이지만, 동작 방식이 다르다.

	뮤텍스	이진 세마포어
기본 메커니즘	자물쇠처럼 잠금/해제로 동작 (잠금 메커니즘)	신호를 주고받는 방식으로 동작 (신호 메커니즘)
동작 특성	잠금을 획득한 스레드만 잠금을 해제할 수 있음	어떤 스레드든 신호를 보내서 세마포어를 해제할 수 있음

 

구성 요소

• 세마포어 값(S): 사용 가능한 공유 자원의 개수(임계 구역에 진입할 수 있는 프로세스의 개수)
• wait(): 자원을 사용하기 위해 세마포어 값을 감소시키고 자원 사용 여부를 확인하는 함수
• signal(): 자원 사용을 마치고 세마포어 값을 증가시켜 다른 프로세스의 자원 사용을 허가하는 함수

 

동작 방식 (Block & Wakeup 방식)

1. wait(): 자원 획득
   • 세마포어 값(S) 감소
   • S가 0 이하면 프로세스를 대기 큐에 넣음 (Block)
   • S가 양수면 자원 획득 가능
2. signal(): 자원 반납
   • 세마포어 값(S) 증가
   • 대기 큐에 프로세스가 있다면 깨워서 준비 상태로 변경 (Wakeup)

 

모니터

모니터는 동시 수행 중인 프로세스나 스레드가 공유 데이터를 안전하게 접근할 수 있도록 지원하는 고수준 동기화 도구이다. 공유 데이터에 접근하는 코드(임계 구역)에 대해 상호 배제를 자동으로 보장하며, 프로그래머가 직접 동기화를 구현하지 않아도 된다.

 

모니터는 상호 배제를 자동으로 보장하여 동시 접근 문제는 해결하지만, 프로세스의 실행 순서는 제어하지 못한다. 
이를 위해 조건 변수(Condition Variable)를 제공한다. 조건 변수의 wait()와 signal() 연산을 통해 프로세스의 실행 순서를 제어할 수 있다.

 

 

구성 요소

• 공유 데이터 (Shared Data): 여러 프로세스가 접근해야 하는 데이터를 포함하며, 모니터 내부에서만 관리
• 조건 변수(Condition Variable): 프로세스 간 실행 순서 제어를 위해 사용되는 변수로, wait(), signal() 연산을 제공
• 공유 자원 연산(인터페이스): 공유 데이터 접근을 위한 인터페이스로 프로시저를 통해 구현됨
• 프로시저: 실제 연산을 실행하기 위한 함수로 임계 구역에 해당
• 초기화 코드(Initialization Code): 공유 데이터를 초기화하는 코드로 임계 구역에 해당

 

동작 방식

1. 프로세스가 모니터의 프로시저를 호출하여 공유 데이터 접근 요청
2. 모니터 진입 제어
   • 모니터가 비어있다면 바로 진입(자동으로 상호배제 보장)
   • 사용 중이면 진입 큐(Entry Queue)에서 대기
3. 조건 변수의 wait(), signal() 연산으로 프로세스 실행 순서 제어
   • wait(): 프로세스를 해당 조건 변수의 큐에서 대기하도록 함
   • signal(): 해당 조건 변수의 큐에서 대기 중인 프로세스를 깨워서 실행 재개

=> 모니터는 프로세스 간 상호 배제를 보장하고, 실행 순서를 관리해 공유 데이터에 대한 안전한 접근을 지원한다.

 

 

2. 교착 상태(Deadlock)

교착 상태(Deadlock)란 두 개 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며, 서로의 작업을 끝나기만을 기다리며 둘 다 영원히 끝나지 않는 상황을 말한다.

 

교착 상태 발생 조건

아래 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다. (반드시 발생 X, 필요충분조건)

 

1. 상호 배제(Mutual Exclusion)

한 번에 한 개의 프로세스만 공유 자원 사용 가능

 

2. 점유와 대기(Hold and Wait)

프로세스가 자원을 할당받은 상태에서 다른 자원을 요청하여 대기

 

3. 비선점(Nonpreemption)

이미 할당받은 자원을 강제로 빼앗을 수 없음

(프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때까지 기다림)

 

4. 순환 대기(Circular Wait)

프로세스의 자원 점유와 요구 관계가 원형을 이루며 대기하는 상태

즉, 각 프로세스는 다음 프로세스가 점유하고 있는 자원을 요구하는 연쇄적인 관계를 형성

 

교착 상태 해결 방법

1. 예방(Prevention)

교착 상태를 예방하는 방법은 애초에 교착 상태가 발생하지 않도록 교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하는 방법이다. 시스템의 처리량과 자원 사용의 효율성을 떨어뜨리는 단점이 있다.

 

• 상호 배제 부정
  • 한 번에 여러 프로세스가 공유 자원 사용하도록 허용
• 점유와 대기 부정
  • 프로세스 실행 전 필요한 모든 자원 한 번에 할당하여 대기 없앰
  • 자원이 점유되지 않은 상태에서만 자원 요청 허용
• 비선점 부정
  • 자원에 대한 선점 허용
  • 높은 우선순위의 프로세스가 다른 프로세스의 자원을 선점 가능
• 순환 대기 부정
  • 자원에 고유 번호를 할당
  • 각 프로세스는 한 방향으로만 자원 요청 가능 (선형)

 

2. 회피(Avoidance)

교착 상태 회피는 시스템의 상태를 지속적으로 감시하며, 프로세스들에 배분할 수 있는 자원의 양을 고려하여 안전 상태(Safe state)에서만 자원을 할당하는 방법이다.

• 안전 순서(Safe Sequence): 교착 상태 없이 자원을 할당할 수 있는 프로세스 순서
• 안전 상태(Safe State): 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태 (안전 순서가 존재하는 상태)
• 불안전 상태(Unsafe State): 교착 상태가 발생할 가능성이 있는 상태 (안전 순서가 없는 상태)

 

회피 알고리즘

• 은행원 알고리즘
• 자원 할당 그래프 알고리즘

 

필요 조건

• 프로세스 수가 고정되어 있어야 함
• 자원의 종류와 수가 고정되어 있어야 함
• 프로세스가 요구하는 최대 자원의 수를 미리 알아야 함
• 프로세스는 자원 사용 후 반드시 반납해야 함

 

3. 검출(탐지) 후 회복 (Detection & Recovery)

교착 상태 발생을 허용하고 주기적으로 발생 여부를 검사하여, 교착 상태 발견 시 회복하는 방법이다. 검출 과정에서 지속적인 모니터링으로 인한 오버헤드가 발생할 수 있다.

 

회복 방법

1. 프로세스 강제 종료
   • 모든 교착 상태 프로세스 종료 -> 확실하지만 작업 내역 손실 가능성
   • 교착 상태가 해결될 때까지 한 프로세스씩 종료 -> 작업 손실 최소화하지만 오버헤드 발생
2. 자원 선점
   • 프로세스로부터 자원을 강제로 선점하여 교착 상태가 해결될 때까지 한 프로세스에게 자원 할당

 

 

---

 REF

• 병행성과 병렬성

https://velog.io/@changchanghwang/%EB%B3%91%ED%96%89%EC%84%B1%EA%B3%BC-%EB%B3%91%EB%A0%AC%EC%84%B1

https://velog.io/@heyoni/Concurrency-Parallelism%EC%9D%98-%EC%B0%A8%EC%9D%B4

https://nesoy.github.io/articles/2018-09/OS-Concurrency-Parallelism

• 동기화 & 동기화 기법

https://rebro.kr/176

https://eunsolsblog.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EB%8F%99%EA%B8%B0%ED%99%94#mutex%C-%A-lock

https://www.geeksforgeeks.org/difference-between-binary-semaphore-and-mutex/

• 교착 상태

https://cocoon1787.tistory.com/858

https://chanhuiseok.github.io/posts/cs-2/