06 OS - 스케줄링

1. 스케줄링

1. 스케줄링

• OS 스케줄링이란, 디스크에 저장된 작업을 메모리 내 준비 큐에 올리고, 그중에서 실행할 프로세스나 스레드를 선택하여 CPU에 할당하는 일련의 과정
• 좋은 스케줄링은 프로세서의 효율을 높이고, 작업의 응답시간을 최소하하여 시스템의 작업 처리능력을 향상시킴

2. 스케줄링 목적

• 자원 할당의 공정성 보장
• 단위시간당 처리량 최대화
• 적절한 반환시간 보장
• 예측가능성 보장
• 오버헤드 최소화
• 자원 사용의 균형유지
• 반환시간 자원의 활용 간에 균형 유지
• 실행 대기 방지
• 우선순위
• 서비스 사용기회 확대
• 서비스 수 감소 방지

2. 스케줄링의 단계

1. 장기스케줄러

• 프로세스를 디스크에서 메모리로 올려 실행 준비 상태로 만드는 역할
• 시스템에 프로세스를 얼마나, 언제 투입할지 결정
• 주로 분 단위 단위로 작동하며, 작업의 ‘수준’과 ‘부하’를 조절함

2. 중기스케줄러

• 메모리에서 프로세스를 일시 중단하거나 다시 재개시켜 자원 관리를 조정
• 주로 메모리 부족 시 프로세스 일부를 디스크로 옮겨 일시 중단 후, 자원 확보 시 재개

3. 단기스케줄러

• 준비 큐에 있는 프로세스/스레드 중에서 CPU에 즉시 할당할 실행 대상을 선택
• 매우 빈번하게 작동하며, 프로세스 실행 흐름을 직접 제어

3. 스케줄링 알고리즘 선택기준

도착          실행시작          첫 번째 출력       실행종료
 |----------------|----------------|--------------|
 ↑                ↑                ↑              ↑
 |<-- 대기 시간 -->|<-- 실행 시간 -->|
 |<------------ 응답 시간 --------->|
 |<-------------- 반환 시간 ---------------------->|

기준 항목	설명
프로세서 활용률 (Processor Utilization)	프로세서를 항상 실행 상태로 유지하여 유휴 상태가 되지 않도록 한다. 입출력 중심 작업보다는 프로세서 중심 작업 실행
처리율 (Throughput)	단위 시간당 완료되는 프로세스 수가 많도록. 높은 처리율은 많은 작업을 빠르게 끝냄을 의미
반환 시간 (Turnaround Time	프로세스가 올라간 시점부터 종료될 때까지 걸린 총 시간
대기 시간 (Waiting Time	프로세스가 준비 큐에서 대기한 시간
응답 시간 (Response Time	사용자가 요청한 시점부터 첫 번째 응답(첫 실행)이 나올 때까지의 시간

4. 스케줄링 알고리즘 🔖

• 준비 큐(Ready Queue)에서 어떤 작업(스레드/프로세스)을 먼저 실행할지 선택하는 정책 및 방법

한글명	알고리즘 (영문)	방식	핵심 특징	장단점 요약
선입선출 처리	FCFS (First-Come, First-Served)	비선점형	먼저 도착한 순서대로 처리	단순하지만 평균 대기시간/반응시간이 길어짐
최소 작업 우선 스케줄링	SJF (Shortest Job First)	비선점형	실행시간이 가장 짧은 작업부터 처리	평균 대기시간 낮음, 기아 상태 발생 가능
우선순위 스케줄링	Priority Scheduling	선점/비선점 가능	우선순위가 높은 작업부터 처리	기아 상태 가능 → 에이징 기법 필요
라운드로빈 스케줄링	RR (Round Robin)	선점형	타임퀀텀 기반으로 순환 처리	공정성↑, 문맥 전환 오버헤드 발생
다단계 큐 스케줄링	Multilevel Queue (MLQ)	선점/비선점 가능	여러 큐로 분류, 각 큐별로 우선순위 및 퀀텀 기반 시간 분할 스케줄링 적용	고정적, 유연성 부족
다단계 피드백 큐 스케줄링	Multilevel Feedback Queue (MFQ)	선점형	큐 간 이동 가능, 각 큐는 퀀텀 기반 동작, CPU 사용량에 따라 큐 이동 및 동적 우선순위 조정	복잡하지만 실무적, 기아 상태 방지 가능
응답비율 우선 스케줄링	HRRN (Highest Response Ratio Next)	비선점형	(대기시간 + 서비스시간) / 서비스시간 위 공식의 비율로 우선순위 결정, 오래 기다린 프로세스에 유리	SJF보다 공정하고 기아 상태 방지 가능

5. 다중 프로세서 스케줄링

• 멀티코어 환경에서 여러 CPU 코어에 맞춰 준비 큐를 어떻게 구성하고, 프로세스/스레드를 어떻게 분배할지 결정하는 스케줄링 전략

  1. 대칭형 다중처리(Symmetric Multiprocessing, SMP)

• 여러 CPU가 OS의 핵심 기능(스케줄링, 인터럽트 처리 등)을 모두 공유하고 동등한 권한을 가짐
• OS가 여러 CPU를 직접 관리하며, 각 CPU가 프로세스를 실행함
• 주로 사용하는 스케줄링 정책
  • 전역 스케줄링(Global Scheduling) : 모든 CPU가 하나의 작업 큐를 공유하며, OS가 균등하게 작업을 분배
  • 분산 스케줄링(Distributed Scheduling) : 각 CPU가 자체 작업 큐를 가지며, 필요하면 작업을 서로 훔쳐가는(work stealing) 기법도 사용
  • 고정 할당 스케줄링(Partitioned Scheduling) : 프로세스를 특정 CPU에 고정해서 실행, CPU 간 이동이 제한적임

2. 비대칭형 다중처리(Asymmetric Multiprocessing, AMP)

• 한 CPU만 OS의 주요 기능과 스케줄링을 담당
• 나머지 CPU는 단순히 작업 실행에만 집중하며 OS 역할이 제한적임
• 보통 임베디드 시스템이나 특수 목적 시스템에서 사용

6. 다중 스레드 스케줄링

• 준비 큐에 있는 스레드들 중 어떤 스레드를 어느 CPU 코어에서 실행할지 결정하는 과정 (멀티코어 내 스레드 단위 스케줄링)

1. 부하 공유 (Load Sharing)

• 시스템 내 여러 프로세서에 스레드를 균등하게 분배하여 프로세서 간 부하를 균형 있게 유지하는 방법
• 특정 프로세서에 작업이 몰리지 않고, 전체 CPU 자원을 효율적으로 사용하기 위함
• 특징:
  • 각 프로세서가 자신의 로컬 큐에서 스레드를 실행하거나, 필요 시 다른 프로세서에서 작업을 가져오기도 함
  • 부하 불균형 발생 시 스레드를 이동시켜 균등화

    2. 갱 스케줄링 (Gang Scheduling)

• 병렬로 동작하는 스레드 그룹(갱)을 동시에 여러 프로세서에서 동시에 스케줄링하는 기법
• 병렬 프로세스 간 동기화가 필요할 때, 모든 관련 스레드를 동시에 실행해 교착상태나 불필요한 대기 시간을 줄임
• 특징:
  • 모든 스레드를 묶어 한 번에 스케줄링 (모든 프로세서에서 동시 실행)
  • 동기화 비용 및 대기시간 감소

3. 전용 프로세서 할당 (Dedicated Processor Assignment)

• 특정 스레드나 프로세스에게 특정 프로세서(또는 CPU 코어)를 전용으로 할당하는 방법
• 프로세서 친화성(Processor Affinity) 유지, 캐시 활용 극대화, 컨텍스트 스위칭 최소화
• 특징:
  • 스레드가 할당된 프로세서에서만 실행
  • 시스템 자원이 제한적인 상황에서 효율적
  • 하지만 부하 불균형 가능성 존재

4. 동적 스케줄링 (Dynamic Scheduling)

• 시스템 상태(부하, 프로세서 가용성 등)에 따라 스케줄링 정책이나 스레드 할당을 실시간으로 조정하는 방법
• 변화하는 시스템 환경에 맞게 최적화된 CPU 자원 배분
• 특징:
  • 스레드 이동, 우선순위 조정, CPU 재할당 등이 동적으로 이루어짐
  • 복잡한 알고리즘과 모니터링 필요