프로세스 스케줄링

스케줄링 단계

상위단계 스케줄링 (Long-term Scheduling)

• 디스크에 있는 프로세스 중 어떤 프로세스를 메모리(Ready Queue)로 올릴지 결정
• 실행할 프로세스의 수를 조절하여 CPU 및 시스템의 부하를 관리

중간단계 스케줄링 (Medium-term Scheduling)

• 메모리 관리 기법 중 스와핑(Swapping)을 통해 일시적으로 실행 중인 프로세스를 메모리에서 제거(중단)하고 다시 실행할 프로세스를 선택
• CPU가 과부하 상태일 때 메모리 점유를 줄이기 위한 목적

하위단계 스케줄링 (Short-term Scheduling)

• CPU를 사용할 프로세스를 선택하여 실행하는 단계
• 실행 중인 프로세스가 종료되거나 인터럽트가 발생할 때 새로운 프로세스를 선택

스케줄링 목표

• 공정성(Fairness): 모든 프로세스가 공정하게 CPU를 할당받도록 함
• 균형: 시스템 자원이 충분히 활용될 수 있게 함

운영체제의 유형에 따른 스케줄링 목표 

• 일괄처리 운영체제 : 처리량 극대화, 반환 시간 최소화, CPU 활용의 극대화
• 시분할 운영체제 : 빠른 응답시간, 과다한 대기시간 방지
• 실시간 운영체제: 처리기한 맞춤 

선점 스케줄링 (Preemptive Scheduling)

• 실행 중인 프로세스에 인터럽트를 걸어 CPU를 다른 프로세스에 할당할 수 있는 방식.
• 운영체제가 우선순위가 높은 프로세스를 실행하기 위해 현재 실행 중인 프로세스를 중단할 수 있음.
• SRT, RR, 다단계 피드백 큐

비선점 스케줄링 (Non-preemptive Scheduling)

• 실행 중인 프로세스가 스스로 종료되거나 I/O 작업을 수행할 때까지 CPU를 계속 점유하는 방식.
• 실행 중인 프로세스를 중간에 강제로 중단할 수 없음.
• FCFS, SJF, HRN..

문맥(Context)

• 현재 실행 중인 프로세스의 CPU 레지스터, 프로그램 카운터, 스택 정보 등의 상태.
• 프로세스가 실행을 멈추고 다시 실행될 때 이전 상태를 복원할 수 있도록 관리됨.

Context Switching (문맥 교환)

• CPU가 실행 중인 프로세스를 변경할 때 발생하는 과정으로, 이전 프로세스의 문맥을 저장하고 새로운 프로세스의 문맥을 복원하는 작업.
• 오버헤드(Overhead)가 발생하여 너무 잦은 Context Switching은 성능 저하를 유발할 수 있음.

스케줄링 평가 기준

평균 대기 시간(Average Waiting Time)

• 프로세스가 CPU를 할당받기까지 준비 큐에서 대기한 총 시간의 평균값

$$
\text{평균 대기 시간} = \frac{\sum (\text{프로세스의 대기 시간})}{\text{총 프로세스 수}}
$$

평균 반환 시간(Average Turnaround Time)

• 프로세스가 처리 완료되기까지 걸린 총 시간(대기 시간 + 실행 시간)

$$
\text{평균 반환 시간} = \frac{\sum (\text{프로세스 완료 시간} - \text{프로세스 도착 시간})}{\text{총 프로세스 수}}
$$

---

주요 스케줄링 알고리즘

1. FCFS (First Come First Serve) - 선입선출

• 준비 큐에 도착한 순서대로 CPU를 할당하는 방식 (비선점)
• 단점: 실행 시간이 긴 프로세스가 먼저 도착하면 기다리는 프로세스의 대기 시간이 증가

도착 순서: P1(8ms), P2(4ms), P3(2ms)
실행 순서: P1 → P2 → P3

2. SJF (Shortest Job First) - 최단 작업 우선

• 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식 (비선점)
• 일괄처리 환경에서 구현하기 쉬우나, 실행 시간이 긴 프로세스는 무한정 대기할 수도 있음

실행 순서: P3(2ms) → P2(4ms) → P1(8ms)

3. SRT (Shortest Remaining Time) - 최단 잔여 시간 우선

• SJF의 선점형 버전으로, 남은 실행 시간이 가장 짧은 프로세스를 우선 실행
• 새로운 프로세스가 도착하면 실행 중인 프로세스보다 실행 시간이 짧으면 교체됨
• SJF보다 평균대기시간이나 평균반환시간에서 효율적이나 SJF 보다 오버헤드가 큼 

실행 순서: P3(도착) → P2(남은 시간 짧음, 교체) → P1

4. RR (Round Robin) - 라운드 로빈

• 각 프로세스에 일정한 시간 할당량(Time Quantum)을 적용하여 실행 (선점)
• Time Quantum이 너무 작으면 Context Switching이 빈번하게 발생하여 성능 저하

5. HRN (Highest Response Ratio Next) - 최고 응답 비율 우선

• 응답 비율(Response Ratio)이 가장 높은 프로세스를 우선 실행 (비선점).
• $$
  \text{응답 비율} = \frac{\text{대기 시간} + \text{실행 시간}}{\text{실행 시간}}
  $$
• 실행 시간이 짧은 프로세스와 오래 기다린 프로세스를 균형 있게 실행 가능.

대기 시간 10ms, 실행 시간 2ms → 응답 비율 = (10+2)/2 = 6 (높은 값이 우선)

6. 다단계 피드백 큐 (Multilevel Feedback Queue)

• 여러 개의 우선순위 큐를 사용하여 프로세스를 관리 (선점).
• 처음에는 높은 우선순위의 큐에서 실행하며, 일정 시간을 초과하면 낮은 우선순위 큐로 이동.
• I/O 중심 프로세스(짧은 작업)가 CPU 중심 프로세스(긴 작업)보다 우선권을 갖도록 설계.

1. 짧은 작업 → 높은 우선순위 큐에서 실행.
2. 오래 실행된 작업 → 낮은 우선순위 큐로 이동.

---

정리

알고리즘	방식	특징
FCFS	비선점	먼저 온 순서대로 실행
SJF	비선점	실행 시간이 가장 짧은 작업 우선
SRT	선점	남은 실행 시간이 가장 짧은 작업 우선
RR	선점	일정 시간(Time Quantum) 단위로 실행
HRN	비선점	응답 비율이 높은 프로세스 우선
다단계 피드백 큐	선점	우선순위 큐를 사용하여 관리