운영체제 핵심 정리: CPU 스케줄링, 프로세스 동기화, 교착상태

1. CPU 스케줄링: 효율적인 CPU 사용을 위한 전략

운영체제가 프로세스들에게 CPU를 효율적으로 분배하는 정책.

목표 및 핵심 용어

• 목표: CPU 이용률 및 처리율 최대화, 반환시간/대기시간/응답시간 최소화
• CPU 이용률: CPU가 실제로 일한 시간의 비율
• 처리율 (Throughput): 단위 시간당 완료된 프로세스 수
• 반환시간 (Turnaround Time): 도착 → 종료까지의 시간
• 대기시간 (Waiting Time): 준비 큐에서 기다린 시간
• 응답시간 (Response Time): 요청 후 첫 응답까지의 시간

스케줄링 분류

• 기능별:

  • 장기: 작업 큐 → 준비 큐
  • 중기: Swapping
  • 단기: 준비 큐 → CPU

• 방법별:

  • 선점형 (Preemptive): 실행 중 프로세스를 중단 가능
  • 비선점형 (Non-preemptive): 실행 종료까지 양보 없음

주요 알고리즘 요약

알고리즘	유형	특징
FCFS	비선점형	간단하지만 Convoy Effect 발생
SJF	비선점형	평균 대기시간 최소, 기아 현상 가능
SRT	선점형	SJF의 선점형, 오버헤드/기아 존재
HRN	비선점형	응답 비율 높은 순, 기아 해결
우선순위	혼합형	우선순위 기반, Aging 필요
RR	선점형	Time Quantum 기반, 문맥 교환 비용
MLQ	혼합형	큐별 다른 정책, 큐 간 이동 없음
MFQ	선점형	큐 간 이동 가능, 동적 우선순위

---

2. 프로세스 동기화: 공유 자원 문제 해결

공유 자원 접근 시 정확한 순서와 실행 결과 보장을 위한 기술. 핵심은 임계 영역(Critical Section) 관리입니다.

세마포어 (Semaphore)

정수형 변수 S와 두 가지 원자적 연산으로 동기화 제어:

• wait(S) (P 연산): S -= 1 / S < 0 이면 Block
• signal(S) (V 연산): S += 1 / S ≤ 0 이면 Wakeup

유형:

• 이진 세마포어 (Binary / Mutex): 0 또는 1 → 상호 배제
• 카운팅 세마포어: 다수 자원 관리 (ex. 주차장)

대표 동기화 문제

생산자-소비자 문제

• 문제: 공유 버퍼의 오버/언더플로우
• 해결:

  mutex   // 상호 배제용 이진 세마포어
  empty   // 버퍼 빈칸 수 (카운팅)
  full    // 버퍼 채움 수 (카운팅)
  읽기-쓰기 문제
  문제: 여러 읽기 vs 단일 쓰기

해결 (읽기 우선):

wrt // 공유 자원 접근 통제 (이진)
mutex // readcount 보호 (이진)
readcount // 현재 읽는 프로세스 수 (정수)
식사하는 철학자 문제
문제: 포크(자원) 점유로 인한 교착상태

해결 방안:

짝수/홀수 철학자의 포크 집는 순서 변경

동시에 N-1명만 식사 허용

3. 교착상태 (Deadlock): 시스템 마비
   프로세스들이 자원을 서로 점유하고 상대방 자원 기다리며 무한 대기 → 시스템 정지

   발생 조건 (4가지 모두 충족 시 발생)
   상호배제: 한 자원은 한 프로세스만 사용 가능

점유와 대기: 자원을 점유한 채 다른 자원을 요청

비선점: 점유한 자원을 강제로 회수 불가

환형 대기: 자원을 원형으로 서로 기다림

해결 전략
1. 예방 (Prevention)
조건 중 하나 이상 제거:

상호배제 제거: 자원 공유 허용

점유와 대기 제거: 자원 일괄 요청

비선점 제거: 자원 회수 가능

환형 대기 제거: 자원 요청 순서 강제

2. 회피 (Avoidance)
   안전 상태(Safe State) 유지

은행원 알고리즘 (Banker’s Algorithm)

자원 할당 그래프 (RAG): 사이클 존재 여부 판단

3. 탐지 및 복구 (Detection)
   교착 상태 허용 + 주기적 탐지 → 자원 회수, 프로세스 종료 등으로 해결

4. 무시 (Ignore)
   아무 조치도 하지 않음 (실제 시스템에서 자주 사용)