[운영체제] 프로세스 스케줄링

전공 수업 내용 정리 (문제 발생시 비공개합니다.)

 

---

프로세스 스케줄링

1. CPU 버스트와 I/O 버스트

• CPU 버스트: CPU가 작업을 실행하는 데 걸리는 시간
• I/O 버스트: CPU가 I/O를 대기하는 데 걸리는 시간
• CPU - I/O 버스트 주기: 각 프로세스 실행은 CPU 실행 및 I/O 대기 주기로 구성
• 프로세스 유형에 따라 CPU 및 I/O 버스트가 변경될 수 있음.
  • (a) CPU 기반: 긴 CPU 버스트 후 I/O 차단
  • (b) I/O 기반: 짧은 CPU 버스트 후 I/O 차단

2. 프로세서 스케줄링의 목적

• 프로세서를 시스템 목표를 충족하는 방식으로 실행할 프로세스를 할당.

3. 프로세서 스케줄링의 유형

스케줄링 다이어그램

• 장기 스케줄링: 새로운 프로세스를 시스템에 진입시킬지 결정.
• 중기 스케줄링: 멀티프로그래밍 정도를 제어하고 프로세스를 메인 메모리로 불러올지 결정.
• 단기 스케줄링: 이벤트 발생 시 현재 프로세스의 CPU를 뺏고 실행할 다음 프로세스를 결정.

4. 스케줄링 평가 척도

사용자 지향(User Oriented)

• 반환 시간(Turnaround time): 프로세스의 제출과 완료 사이의 시간 간격
• 응답 시간: 대화형 프로세스의 경우 요청 제출 후 응답 수신까지의 시간
• 데드라인: 프로세스 완료 시간을 지정, 정해진 시간 내에 완료되어야 함.

시스템 지향(System Oriented)

• 처리량(Throughput): 시간 단위당 완료된 프로세스 수
• 프로세서 사용률(Processor utilization): 프로세서가 사용 중인 시간의 백분율
• 공정성(Fairness): 프로세스는 동일하게 취급되어야 하며, 기아가 발생하지 않아야 함.

5. 기아(Starvation)

• 순서가 뒤로 밀려나는 현상.

6. 선택 함수(Selection Function)

• 준비된 프로세스 중 어떤 프로세스가 적합한지 결정.
  • 기능: 우선순위, 자원에 기초

7. 결정 모드(Decision Mode)

• 비선점(Non-preemptive): 프로세스가 실행상태에 진입하면 CPU를 뺏기지 않음.
• 선점(Preemptive): 실행 중인 프로세스라도 인터럽트가 걸리면 준비 큐로 이동.

8. 스케줄링 알고리즘

1. FIFO (First In, First Out)

• 선택 함수: max[w]
• 결정 모드: 비선점
• 장점: 가장 간단하고, 긴 프로세스에서 더 나은 성능 제공
• 단점: 호위 효과(convoy effect), 짧은 프로세스에서 불리

2. 최단작업 우선 (Shortest Process Next, SPN)

• 선택 함수: min[s]
• 결정 모드: 비선점
• 장점: TAT 향상, 평균 실행 시간 유지 가능
• 단점: 기아 발생 가능, 필요한 프로세스 시간 파악 필요

3. Shortest Remaining Time (SRT)

• 선택 함수: min[s-e]
• 결정 모드: 선점
• 장점: SPN보다 뛰어난 처리 시간 성능, 평균 대기 시간 단축
• 단점: 기아 발생 가능, 서비스 시간 예측 어려움

4. Highest Response Ratio Next (HRRN)

• 선택 함수: max[(w+s)/s]
• 결정 모드: 비선점
• 장점: 공정함, 긴 과정도 경쟁적으로 더 짧은 일자리를 수용
• 단점: 예상 서비스 시간 추정 필요, 문맥 교환 비용 증가 가능

5. 라운드 로빈 (Round-robin)

• 개요: 각 프로세스가 일정 시간 동안 CPU를 사용할 수 있는 방식.
• 타임 슬라이싱 기법: 시간 할당량(time quantum) 설정.
• 선택 함수: 상수
• 결정 모드: 선점
• 장점:
  • 공정함.
  • FIFO로 인해 짧은 작업이 겪는 페널티를 줄이는 간단한 방법.
• 단점:
  • 시간 할당량이 너무 크면 평균 대기 시간이 길어질 수 있다. (FCFS 스케줄링과 유사)
  • 시간 할당량이 너무 작으면 처리량이 낮아지며 문맥 전환이 잦아짐.
• 해결책:
  • 가상 라운드 로빈
  • 멀티 레벨 피드백 큐
• 설계 문제:
  • 타임 슬라이싱의 길이 ( q )
    • ( q )가 짧으면 SPN에 유리 (짧은 프로세스 유리)
    • ( q )가 길면 FIFO에 유리 (긴 프로세스 유리)
• 예제:
  • Turnaround time: A: 4, B: 16, C: 13, D: 14, E: 7
  • 평균 turnaround time: (4 + 16 + 13 + 14 + 7) / 5 = 10.8

6. 가상 라운드 로빈 (Virtual Round Robin = VRR)

• 개요: 긴 프로세스를 위한 편향을 줄인 가상의 라운드 로빈 대기 큐 사용.
• 특징:
  • 입출력이 완료된 프로세스가 준비 큐의 끝으로 가는 대신 "보조 큐"라는 별도의 FCFS 큐에 진입.
  • 보조 큐의 프로세스는 기본 준비 대기열의 프로세스보다 먼저 실행됨.
• 장점: 기존 라운드 로빈보다 공정성이 우수.

7. 멀티 레벨 피드백 큐 (Multi-Level Feedback Queues)

• 장점:
  • 프로세스가 대기열 간에 이동 가능.
  • 시간 할당량이 있는 선점 모드 + 동적인 우선순위 정책.
• 단점: 장시간 실행되는 작업은 기아 발생 가능.
• 매개변수:
  • 대기열 수
  • 각 대기열에 대한 예약 알고리즘
  • 프로세스 승격 및 강등 시기를 결정하는 방법
  • 기아를 피하기 위한 노화

다양한 스케줄링 방식 비교분석

4. 멀티 프로세서(MP) 스케줄링

MP 시스템의 분류

• 약결합 시스템: 각 프로세서는 자체 메인 메모리와 I/O 채널을 가짐.
  • 예: 클러스터 시스템.
• 강결합 시스템: 공통 메인 메모리를 공유하는 프로세서 집합.
  • 운영 체제에 의해 통합 관리.

MP 스케줄링 접근 방식

1. 비대칭적 다중 처리 (master/slave):
   • 모든 스케줄링 결정은 마스터에 의해 이루어짐.
   • 단순하지만 마스터 서버가 병목 현상이 될 수 있음.
2. 대칭적 다중 처리 (SMP, peer):
   • 커널은 모든 프로세서에서 실행 가능하며, 각 프로세서는 자체 스케줄링 수행.

설계 문제

• 단일 프로세서 및 멀티 프로세서의 스케줄링 작업 결정.
• 프로세스의 실제 디스패칭, 준비 큐 유지, 프로세서에 프로세스 할당 등.

단일 큐 MP 스케줄링 (Single-Queue MP Scheduling)

• 전역 준비 큐 유지, 프로세스는 특정 프로세서에 할당되지 않음.
• 장점: 단순성, 부하 공유.
• 단점: 다른 프로세서에서 동시에 실행될 수 있음.

프로세서 친화성 (Affinity)

• 종류:
  • 소프트 친화성: 운영 체제는 프로세서가 동일하게 실행되도록 시도하지만 보장하지 않음.
  • 하드 친화성: 프로세스가 실행할 수 있는 프로세서의 하위 집합을 지정 가능.

멀티 큐 MP 스케줄링 (Multi-Queue MP Scheduling)

• 각 프로세서는 개별 큐 보유.
• 장점: 동기화 문제 회피, 높은 확장성과 프로세서 친화성.
• 단점: 부하 불균형 가능성.

프로세스 이동 방법

• Pull: 유휴 프로세서가 비유휴 프로세서로부터 프로세스를 훔침.
• Push: 특정 작업이 주기적으로 각 프로세서의 부하를 확인.

SMP 시스템에서 두 개 이상의 프로세서의 이점을 최대한 활용하기 위해 모든 프로세서 간에 작업 균형을 유지하는 것이 중요하다. 다양한 스케줄링 알고리즘과 기법을 통해 성능과 공정성을 높이는 노력이 필요하다.

이질적 멀티프로세싱 (Heterogeneous Multiprocessing, HMP)

• 동일한 명령어 집합을 실행하지만, 클럭 속도 및 전력 관리 측면에서 다른 코어를 이용하여 설계됨.
• 비대칭 멀티프로세싱의 형태가 아님.
• ARM 프로세서에서 지원: 고성능 "빅 코어"와 저전력 "리틀 코어"를 조합한 big.LITTLE 솔루션.
  • 리틀 코어: 높은 성능이 필요하지 않지만 긴 시간 동안 실행해야 하는 작업.
  • 빅 코어: 많은 처리 능력이 필요하지만 짧은 시간 내에 실행될 수 있는 상호작용 응용 프로세스.

실시간 스케줄링 (Real-Time Scheduling)

• 비동기 이벤트를 주어진 시간 내에 처리해야 하는 스케줄링 방식.
• 이벤트 발생 시 즉시 응답할 수 있는 선점 가능한 커널 제공.
• 이벤트 발생 시기:
  • 주기적 이벤트
  • 비주기적 이벤트 (타이머 만료 등)
• 이벤트 대기 시간(latency) = 인터럽트 대기 시간 + 디스패처 대기 시간.
• 선점 커널은 디스패처 대기 시간을 낮추는 효율적인 기술임.

💡 가치있는 시간 내에 작업을 완료(또는 시작)하는 것이 중요!

실시간 작업 분류

1. 연성 실시간 시스템 (Soft Real-Time Systems): 실시간 프로세스가 우선적으로 처리되지만, 마감 기한 보장은 없음. 원하는 마감 기한이 있지만 의무는 아님.
2. 경성 실시간 시스템 (Hard Real-Time Systems): 프로세스는 마감 기한에 따라 서비스를 받아야 하며, 마감 기한이 지켜지지 않으면 시스템에 심각한 손상이나 오류 발생.

작업 유형

• 주기적 작업 (Periodic Task): 일정한 시간 간격으로 반복 발생; 고정된 실행 시간과 마감 기한 있음.
• 비주기적 작업 (Aperiodic Task): 간헐적으로 발생하며, 발생 간격이 일정하지 않음.

마감시간

• 시작 마감시간 (Starting Deadline): 작업의 시작 시점에서의 마감시간.
• 종료 마감시간 (Completion Deadline): 작업 완료 후의 마감시간.

우선순위 스케줄링 (Priority-Based Scheduling)

• 높은 우선순위를 가진 프로세스가 먼저 스케줄링됨.
• 단점: 하위 우선 순위를 가진 프로세스의 기아(starvation) 가능성.

데드라인 스케줄링

Earliest-Deadline-First (EDF)

• 프로세스의 마감일 요구 사항을 스케줄러에 알리며, 마감에 따라 우선 순위가 동적으로 할당됨.
• 장점: 데드라인을 맞추지 못하는 프로세스 수 최소화.
• 데드라인이 더 이른 경우 우선 순위 상승; 늦을 경우 우선 순위 하락.

비율 단조 스케줄링 (Rate Monotonic Scheduling, RMS)

• 정적 우선 순위 정책 사용.
• 우선 순위는 실행 주기의 역수로 결정됨; 주기가 짧을수록 우선 순위를 높임.
• 장점: 분석하기 쉬움.

공식 및 조건

• ( C ): 실행 시간 (작업이 완료되는 데 필요한 시간)
• ( T ): 주기
• ( U = \frac{C}{T} ): 프로세스 이용률
• 모든 프로세스의 이용률 합은 1을 넘지 않아야 함.

예제

• 작업 P1: ( C_1 = 20, T_1 = 100, U_1 = 0.2 )
• 작업 P2: ( C_2 = 40, T_2 = 150, U_2 = 0.267 )
• 작업 P3: ( C_3 = 100, T_3 = 350, U_3 = 0.286 )

총 이용률: ( 0.2 + 0.267 + 0.286 = 0.753 )
RMS의 상한은 ( 0.779 )보다 낮아, 모든 작업이 성공적으로 예약됨.

EDF vs RMS 비교

• EDF: 이론적으로 최적이지만, 교체와 인터럽트 처리 비용으로 인해 높은 CPU 이용률을 달성하기 어려움.
• RMS: 산업 응용에서 널리 사용되며, 정적 우선 순위 정책을 사용하여 안정적임.

경성 실시간 시스템과 연성 실시간 시스템을 동시에 포함하는 경우 많은 시스템이 존재하며, 이러한 시스템에서는 고성능과 안정성을 위해 우선 순위 정책을 적절히 조절해야 함.

 

---