Convoy Effect, Starvation, Busy Wait

운영체제의 프로세스 스케줄링에서 발생할 수 있는 주요 문제점들을 이해하는 것은 시스템 성능 최적화에 매우 중요합니다. 오늘은 Convoy Effect, Starvation, Busy Wait의 차이점과 각각의 해결 방안을 자세히 알아보겠습니다.

 

1. Convoy Effect (호위 효과)

 

 

몇 개의 시간이 오래 걸리는 프로세스로 인해 다른 프로세스들의 실행이 느려지는 현상

 

정의 및 특징

• 전체적인 프로세스 성능 저하 야기
• 평균 대기시간 증가
• 주로 FCFS(First Come First Served) 알고리즘에서 발생

 

발생 시나리오

프로세스 대기열:
P1 (실행시간: 100초) → P2 (실행시간: 1초) → P3 (실행시간: 1초) → P4 (실행시간: 1초)

FCFS 스케줄링 결과:
시간: 0      100    101    102    103
     [  P1   ][ P2 ][P3 ][P4 ]

대기 시간:
- P1: 0초
- P2: 100초 (불필요하게 긴 대기)
- P3: 101초 (불필요하게 긴 대기)  
- P4: 102초 (불필요하게 긴 대기)

평균 대기시간: (0 + 100 + 101 + 102) / 4 = 75.75초

 

실생활 비유

마트에서 한 손님이 대량 구매를 하고 있을 때, 뒤에 있는 간단한 구매 고객들이 모두 오래 기다려야 하는 상황과 유사합니다.

해결책

• SJF(Shortest Job First) 알고리즘 사용
• Round Robin 스케줄링 적용
• 우선순위 기반 스케줄링 도입

 

2. Starvation (기아 상태)

 

 

어떤 프로세스가 무기한으로 대기하며 CPU 소유권을 영원히 얻을 수 없는 현상

 

정의 및 특징

• 프로세스가 아예 실행되지 않는 극단적 상황
• 우선순위가 계속 밀려나는 현상
• 주로 SJF 알고리즘이나 우선순위 스케줄링에서 발생

발생 메커니즘

프로세스 상황:
- P1: 실행시간 50초, 우선순위 낮음
- P2: 실행시간 1초, 우선순위 높음 (계속 도착)
- P3: 실행시간 2초, 우선순위 높음 (계속 도착)

SJF 스케줄링 결과:
시간: 0    1    3    4    6    7    9   ...
     [P2][P3][P2][P3][P2][P3][P2]...

결과: P1은 영원히 실행되지 않음 (Starvation 발생)

 

실생활 비유

응급실에서 중증 환자들이 계속 들어와 가벼운 증상의 환자가 무한정 대기하게 되는 상황과 비슷합니다.

해결책: Aging 기법

 

Aging : 실행되지 않은 프로세스의 우선순위를 시간이 지남에 따라 점진적으로 높여주는 기법

Aging 적용 예시:
초기 상태:
- P1: 우선순위 5 (낮음), 대기시간 0초
- P2: 우선순위 1 (높음), 대기시간 0초

10초 후:
- P1: 우선순위 3 (상승!), 대기시간 10초  
- P2: 우선순위 1, 대기시간 0초

20초 후:
- P1: 우선순위 1 (최고 우선순위 달성!), 대기시간 20초

 

3. Busy Wait (바쁜 대기)

 

 

프로세스나 스레드가 특정 조건을 만족할 때까지 지속적으로 확인하는 동기화 기술

 

정의 및 특징

• 상호배제(Mutual Exclusion) 달성에 사용
• 공유자원에 대한 동시 접근 방지
• 지속적인 조건 확인으로 CPU 자원 소모

동작 방식

// Busy Wait 예시 (스핀락)
while (lock == 1) {
    // 아무것도 하지 않고 계속 확인
    // CPU를 계속 사용하면서 대기
}
lock = 1;  // 락 획득
// 임계 구역 실행
lock = 0;  // 락 해제

 

 1. 우선순위 역전 문제

상황:
- 고우선순위 프로세스 A: 락을 기다림 (Busy Wait)
- 저우선순위 프로세스 B: 락을 보유

문제: A가 계속 CPU를 점유하여 B가 실행되지 못함
결과: 락이 영원히 해제되지 않음

 

 

 2. CPU 자원 낭비

시나리오: 락 대기시간이 긴 경우

일반적인 대기:
시간: 0    10   20   30   40   50
     [대기]              [실행]
CPU 사용률: 0%           100%

Busy Wait:
시간: 0    10   20   30   40   50  
     [확인][확인][확인][확인][확인][실행]
CPU 사용률: 100% 100% 100% 100% 100% 100%

 

구분	장점	단점
Busy Wait	• 즉시 응답 가능<br> • 컨텍스트 스위칭 없음	• CPU 자원 낭비<br> • 우선순위 역전 문제
Block & Wakeup	• CPU 효율적 사용<br> • 다른 프로세스 실행 가능	• 컨텍스트 스위칭 오버헤드<br> • 응답 지연

적절한 사용 시기

• 짧은 대기시간이 예상되는 경우
• 멀티프로세서 환경에서 다른 CPU가 락을 빨리 해제할 경우
• 실시간 시스템에서 즉각적인 응답이 필요한 경우

문제점 비교 요약

문제발생	조건	주요 영향	해결 방안
Convoy Effect	FCFS + 긴 작업 먼저	평균 대기시간 증가	SJF, Round Robin
Starvation	우선순위 기반 스케줄링	특정 프로세스 무한 대기	Aging 기법
Busy Wait	동기화 대기 상황	CPU 자원 낭비	Block & Wakeup

 

심각도 수준

Starvation > Convoy Effect > Busy Wait
   (완전 차단)   (성능 저하)    (자원 낭비)

 

 대응 전략

 

 1. 스케줄링 정책 개선

• 다단계 큐 스케줄링 적용
• 동적 우선순위 조정 구현
• 시간 할당량 최적화

 2. 동기화 메커니즘 선택

• 짧은 대기: Spin Lock (Busy Wait)
• 긴 대기: Mutex, Semaphore (Block & Wakeup)
• 하이브리드: Adaptive Spin Lock

 3. 모니터링 및 튜닝

• 대기시간 분석
• CPU 사용률 모니터링
• 프로세스 우선순위 재조정