Chapter5. 프로세스 스케줄링

유튜브에 있는 김덕수 교수님의 Operating System 강의를 듣고 정리한 내용입니다.
중간에 등장하는 ppt 내용들은 모두 강의자료를 캡처한 것입니다.

🔧 스케줄링이란

Multi-Programming

• 시스템 내에 여러 개의 프로세스가 존재
• 자원을 할당 할 프로세스를 선택해야 함 → 스케줄링(Scheduling)
• 시스템 성능(Performance) 향상을 위해 효율적인 스케줄링 필요

시스템 성능 지표 (index)

목적에 맞는 지표를 고려하여 스케줄링 설계

• 평균 응답 시간
• 처리량
• 자원 할당의 공평성
• 예측 가능성
• 오버헤드 최소화
• 실행 대기 방지
• 등등..

🔧 스케줄링 기준 (Criteria)

• 프로세스의 특성
  • I/O-bounded (I/O 대기가 더 긴 프로그램)
  • compute-bound (CPU 사용이 더 긴 프로그램)
• 시스템 특성
  • Batch-system or interactive-system
• 프로세스의 긴급성 (urgency)
• 프로세스 우선순위 (priority)
• 프로세스 총 실행 시간
• 등등..

CPU burst vs I/O burst

• 프로세스의 수행은 CPU사용 + I/O 대기
• CPU burst = CPU 사용시간
• I/O burst = I/O 대기시간
• CPU burst > I/O burst → compute-bound
• CPU burst < I/O burst → I/O-bounded
• burst time은 스케줄링의 중요한 기준

🔧 스케줄링 단계 (Level)

• 발생 빈도 및 할당 자원에 따라 구분
• Long-term scheduling (가끔)
• Mid-term scheduling (종종)
• Short-term scheduling (자주)

Long-term Scheduling

• 커널에 등록할 작업(Job) 결정
  • Job scheduling 이라 부르기도 함
• 시스템 내 프로세스 수 조절
• I/O-bounded 와 compute-bounded 프로세스들을 잘 섞어줘야 함
• time sharing 시스템은 거의 모든 작업을 시스템에 등록하기 때문에 Long-term scheduling 덜 중요함

Mid-term Scheduling

• 메모리 할당 결정 (memory allocation)
  • Intermediate-level scheduling
  • Swapping (swap-in/swap-out)

Short-term Scheduling

• Process scheduling
• 프로세서를 할당할 프로세스 결정
• 가장 빈번하게 발생
  • Interrupt, block(I/O), time-out, …
  • 성능에 결정적인 요소. 매우 빨라야 함

전체 단계

🔧 스케줄링 정책 (Policy)

Preemptive vs Non-Preemptive

• Preemptive scheduling
  • 타의에 의해 자원을 빼앗길 수 있음
    • ex) 할당 시간 종료, 우선순위 높은 프로세스 등장, …
  • Time-sharing system에 적합
  • 단점: Context switch overhead 큼
• Non-Preemptive scheduling
  • 할당 받은 자원을 스스로 반납할 때까지 사용
  • 장점: Context switch overhead 적음
  • 단점: 우선순위 역전, 평균 응답 시간 증가

Priority

• Static priority
  • 프로세스 생성시 결정된 우선순위 유지
  • 구현 간단, overhead 적음
  • 시스템 환경 변화에 대한 대응이 어려움
• Dynamic priority
  • 프로세스의 상태 변화에 따라 우선순위 변경
  • 구현 복잡, priority 다시 계산하는 overhead 큼
  • 시스템 환경이 변해도 유연한 대응 가능

🔧 기본 스케줄링 알고리즘

Basic scheduling algorithms

• FCFS (First-Come-First-Service)
• RR (Round-Robin)
• SPN (Shortest-Process-Next)
• SRTN (Shortest-Remaining-Time-Next)
• HRRN (High-Response-Ratio-Next)
• MLQ (Multi-level-Queue)
• MFQ (Multi-level-Feedback-Queue)

FCFS (First-Come First-Service)

• ready queue기준 먼저 도착한 프로세스 먼저 처리
• Non-preemptive scheduling
• 장점: 자원을 효율적으로 사용 가능
• 단점: 수행시간 긴 프로세스 있으면 뒤에 다 밀림
• Batch system에 적합, Interactive system에 부적합

Round-Robin

돌아가면서 쓰자	스케줄링

• ready queue기준 먼저 도착한 프로세스 먼저 처리
• Time quantum (자원 사용 제한 시간)이 있음
  • 프로세스는 할당된 시간이 지나면 자원 반납
  • 특정 프로세스의 자원 독점(monopoly) 방지
  • Context switch overhead 큼
• Time quantum 설정이 시스템 성능을 결정하는 핵심 요소

SPN (Shortest Process Next)

• 실행시간(burst time) 기준
• burst time 가장 작은 프로세스를 먼저 처리
• 장점
  • 평균 대기시간(WT) 최소화
  • 시스템 내 프로세스 수 최소화 (시스템 효율 향상)
    • 스케줄링 부하 감소, 메모리 절약
  • 많은 프로세스들에게 빠른 응답 시간 제공
• 단점
  • Starvation (무한대기) 현상 발생
    • BT가 긴 프로세스는 우선순위가 계속 밀림
  • 정확한 실행시간 구하는 것이 생각보다 어려움

SRTN (Shortest Remaining Time Next)

• SPN 변형
• 잔여 실행 시간이 더 적은 프로세스 먼저 처리
• 단점: 잔여 실행을 계속 추적해야 함
  • 구현 및 사용하기에 비현실적

HRRN (High Response Ratio Next)

• SPN + Aging concepts
• Aging Concept: 프로세스의 대기시간(WT)를 고려
• Response ratio(응답률) 높은 프로세스 먼저 처리
  • 읍답률 = (WT+BT / BT) 장점: SPN + Starvation 방지 단점: 실행시간 예측 (overhead)

MLQ (Multi-Level Queue)

• 작업(or 우선순위)별 별도의 ready queue 가짐
  • 최초 배정된 queue 벗어나지 못함
  • queue 구성은 OS 정책에 따라 결정
  • 각각의 queue는 개별 스케줄링 기법 사용
• Queue 사이에는 우선순위 기반 스케줄링 사용
  • ex) Fixed-prioirity preemptive scheduling
• 단점
  • 여러 개의 Queue관리 등 스케줄링 overhead
  • 우선순위 낮은 queue는 starvation 발생

MFQ (Multi-Level Feedback Queue)

• Queue간 이동이 허용된 MLQ
• Feedback을 통해 우선 순위 조정 (Dynamic priority)
• 단점
  • 설계 및 구현 복잡
  • 스케줄링 overhead 큼
• Parameters for MFQ scheduling
  • Queue 갯수
  • Queue 사이 스케줄링 알고리즘
  • 우선 순위 조정 기준
  • 최초 Queue 배정 기준
  • …
• Example
  • 각 ready queue 마다 시간 할당량을 다르게 배정
  • I/O-bounded 프로세스들을 상위 단계 queue로 이동 (우선순위 높임)
  • 대기 시간이 지정된 시간을 초과하면 상위 queue로 이동 (aging)

맨 위로 이동하기

OS 카테고리 내 다른 글 보러가기