04 OS - 병행프로세스와 상호배제

1. 병행프로세스

1. 독립 프로세스

• 다른 프로세스와 공유 메모리, 변수, 자원 등을 사용하지 않으며, 어떤 프로세스의 실행 여부나 결과에 영향을 주지도 받지도 않는 구조
• 종류
  • 단일 프로그래밍 : 하나의 프로세스가 CPU를 점유하여 종료된 후 다음 프로세스를 실행
  • 다중 프로그래밍 : 여러 프로세스가 메모리에 동시에 올라가 있으며, CPU는 문맥교환(context switch)을 통해 프로세스들을 번갈아가며 실행
  • 다중 처리 : 2개 이상의 CPU를 사용하여 물리적으로 여러 프로세스를 병렬로 실행

2. 협력 프로세스

• 협력 프로세스는 다른 프로세스와 데이터를 공유하거나 통신하며 공동 작업을 수행하는 구조
• 예시
  • 두 프로세스가 하나의 파일 또는 공유 메모리를 동시에 접근하는 경우
  • 생산자-소비자 모델 (Producer-Consumer)
  • 파이프라인 처리, 클라이언트-서버 모델

3. 병행프로세스 해결 과제

• 상호배제 : 공유 자원 접근 시 동시 접근 방지
• 프로세스 간 통신 (IPC) : 메시지 큐, 파이프, 공유 메모리 등을 통한 데이터 교환
• 일관된 실행 결과 보장 : 실행 순서에 관계없이 동일한 결과가 나와야 함 (레이스 컨디션 방지)

2. 상호배제

1. 상호배제

• 병행 프로세스 환경에서 하나의 프로세스가 공유 자원을 사용하는 동안, 다른 프로세스가 동시에 해당 자원에 접근하지 못하도록 보장하는 것
• 상호배제 만족 조건
• 동시 접근 금지: 둘 이상의 프로세스가 동시에 공유 자원에 진입할 수 없어야 함.
• 진행 조건 (Progress): 어떤 프로세스가 임계 구역에 들어갈 수 있을지는 시스템의 속도나 프로세서 수와 관계없이 결정되어야 함.
• 한정된 대기 (Bounded Waiting): 프로세스는 유한한 시간 내에 임계 구역에 들어갈 수 있어야 하며, 무기한 기다리면 안됨
• 비선점성 (No Preemption): 이미 임계 구역에 진입한 프로세스를 다른 프로세스가 강제로 중단시킬 수 없어야 함.

2. 임계영역

• 두 개 이상의 프로세스가 공유 자원(예: 변수, 버퍼, 파일 등)을 접근할 수 있는 코드 영역
• 임계 영역은 하나의 프로세스만 진입 가능해야함
• 일반적인 구조

  Entry Section → Critical Section → Exit Section → Remainder Section
  

• Entry Section: 임계 구역 진입을 위한 조건 검사 및 락 획득
• Exit Section: 임계 구역 탈출 후 락 해제
• Remainder Section: 공유 자원과 무관한 일반 실행 영역

3. 생산자 소비자 문제

• 비동기적으로 실행되는 두 프로세스(또는 스레드)가 공유 버퍼를 통해 데이터를 주고받는 고전적 동기화 문제
• 생산자 프로세스는 데이터를 버퍼에 저장하고, 소비자 프로세스는 버퍼에서 데이터를 읽어감
• 해결해야 하는 문제
  • 동기화(Synchronization) : 소비자가 읽기 전에 생산자가 데이터를 먼저 써야 함
  • 공유 자원 보호 : 버퍼는 임계 영역이므로 동시 접근이 불가
  • 버퍼 오버플로우 : 생산자는 버퍼가 가득 찼을 경우 대기해야 함
  • 언더플로우 방지 : 소비자는 버퍼가 비었을 경우 대기해야 함

3. 상호배제 방법

1. 상호 배제 방법

분류	방법	설명
고급 수준	소프트웨어로 해결	데커의 알고리즘, 크누스의 알고리즘, 핸슨의 알고리즘 등
	소프트웨어가 제공	세마포, 모니터 등
저급 수준	하드웨어로 해결	TestAndSet(테스) 등

2. 데커의 알고리즘 🔖

• 병행 프로그래밍의 상호배제 문제를 풀 수 잇는 첫번째 해결책으로 알려짐.
• 각 프로세스는 플래그를 설정할 수 있고, 그 플래그를 기준으로 진입여부를 결정함.
• 특징
  • 특별한 하드웨어 명령문이 필요없음.
  • 임계 영역 바깥에서 수행중인 프로세스가 다른 프로세스들이 임계영역에 들어가는걸 막지 않음.
  • 임계 영역에 들어가기를 원하는 프로세서를 무한정 기다리게 하지 않음.

3. TestAndSet(테스) 명령어 🔖

• 하드웨어 수준에서 상호배제를 보장하는 원자적 명령어
• 공유 플래그(락 변수)를 검사하고 동시에 값을 변경함
• 특징
  • 한 명만 임계 영역 진입 가능 (다른 프로세스는 반복 확인)
  • Busy Waiting(바쁜 대기) 발생 가능
  • 다중 프로세서 환경에서도 동기화 가능

4. 세마포 🔖

• 정수 값을 가지는 동기화 객체로, 자원 개수를 제어하는 데 사용
• 두 가지 기본 연산:
  • P() 또는 wait() : 자원을 얻음 (값 감소)
  • V() 또는 signal() : 자원을 반환 (값 증가)
• 특징
  • 상호배제 및 동기화 모두 가능
  • 이진 세마포(0,1 값만)는 락처럼 사용
  • 잘못 사용 시 교착 상태 발생 가능

5. 모니터 🔖

• 고급 언어 수준에서 제공되는 동기화 도구 (소프트웨어 기반)
• 임계영역은 모니터 안의 메소드로 구성되고, 하나의 스레드만 진입 가능
• 조건 변수(Condition Variable)로 상태 변화에 따라 스레드 대기/재개
• 특징
  • 병행 제어를 구조적으로 안전하게 구현
  • 바쁜 대기를 피하고, 자바나 파이썬에서도 기본 제공