[운영체제] CPU Scheduling

CPU Scheduling

• CPU Burst
  • CPU를 사용하는 단계
• I/O Burst
  • I/O 작업하는 단계
• CPU bound job : CPU를 많이 사용하는 작업
• I/O bound job : I/O를 많이 사용하는 작업
• CPU 스케줄링이 필요한 이유
  • I/O 가 CPU 사이에 자주 끼기 때문

CPU Scheduler와 디스패처

• 스케줄러 : ready 상태 프로세스 중 CPU를 줄 프로세스를 고름
• 디스패처 : CPU 의 제어권을 스케줄러로부터 선택된 프로세스에게 넘김
  • 이 과정을 context switch라고 함
• CPU 스케줄링 언제 필요?
  • Running → Blocked (I/O)
  • Running → Ready (할당 시간 만료 timer interrupt)
  • Blocked → Ready (I/O 완료 후 인터럽트)
  • Terminate

비선점, 선점으로 크게 두가지 분류를 할 수 있음

성능 척도 (Scheduling Criteria)

• 어떤 알고리즘이 좋은지 판별하기 위한 척도
• 시스템 입장
  • CPU utilization (이용률) : 전체 시간 중에 CPU가 놀지 않고 일한 비율
  • Throughput (처리량) : 단위 시간 당 몇개의 작업을 완료했나
• 프로그램 입장 (고객 입장)
  • Turnaround time (소요 시간, 반환 시간) : CPU 쓰러 들어와서 다쓰고 나갈 때가지 걸린 시간 (대기 시간 포함)
  • Waiting time (대기 시간) : CPU를 쓰기 위해 기다린 시간
  • Response time (응답 시간) : 레디 큐에 들어와서 처음으로 CPU를 얻기까지 걸린 시간

FCFS (First-Come-First-Served)

• 비선점
• 먼저 온게 먼저
• 앞에 어떤 프로세스가 버티냐에 따라 상당히 다른 퍼포먼스
• 긴 프로세스 떄문에 짦은 프로세스가 많이 대기하는 것 → Convoy effect

SJF (Shortest-Job-First)

• 비선점, 선점 두가지 버전 존재 (선점은 SRJF)
• CPU burst time이 가장 짧은 프로세스에게 할당
• 평균 대기 시간이 가장 짧음 (선점형의 경우)
• 문제점
  • Starvation : 긴 프로세스는 계속 CPU 할당을 못받음
  • CPU 사용 시간을 미리 알수 없음
    • 추정을 통해서 해결 → 과거의 CPU burst time을 이용하여 추정

Priority Scheduling

• 우선순위 높은 프로세스에게 CPU 할당
• 선점, 비선점 두가지 다 가능
• SJF 도 일종의 priority scheduling
• 문제
  • 기아 현상
• Solution
  • aging : 오래 기다리면 우선순위를 조금씩 높여주는 것

Round Robin (RR)

• 각 프로세스에 동일한 크기의 할당 시간(time quantum)을 줌
• 보통 10 ~ 100 밀리세컨드
• 할당 시간이 끝나면 선점되고 큐의 맨뒤로
• 응답 시간이 좋음
• 어떤 프로세스도 (n - 1)q time unit 이상 기다리지 않는다
• 성능
  • q 가 크면 → FCFS와 다를게 없음
  • q 가 작으면 → context switch 오버헤드 높음

Multilevel Queue

• 레디 큐가 여러개
• 위로 갈수록 우선순위 높음
  • 시스템 프로세스
  • interactive 프로세스
  • interactive editing process
  • batch process
  • student process
• foreground (interactive)
• background (batch - no human interaction)
• 각 큐마다 독립적인 스케줄링 알고리즘 가짐
  • foreground - RR
  • background - FCFS
• 큐끼리의 스케줄링도 필요
  • 고정 우선순위 스케줄링
    • foreground 다 끝나면 background
    • 기아 현상 야기
  • 타임 슬라이스
    • 각 큐에 CPU time 적절 비율로 할당

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능
• aging을 구현하는 하나의 방법
• 상위 큐일수록 퀀텀이 짧음 → 맨 아래는 FCFS
• 처음 프로세스는 우선순위 가장 높음
• 다 끝내지 못할 시 하나씩 강등됨

Multiple-processor scheduling

• CPU가 여러 개인 경우의 스케줄링
• Homogeneous processor
  • queue에 한줄로 세워서 각 프로세서가 알아서 꺼내감
  • 반드시 특정 프로세서에서 수행되어야하는 작업의 경우 문제가 복잡해짐
• Load sharing
  • 일부 프로세서에 쏠리지 않도록 부하 공유하는 메커니즘
  • 별개 큐 vs 공동 큐
• Symmetric Multiprocessing (SMP)
  • 각 프로세서가 각자 알아서 스케줄링
• Assymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터 접근, 공유 책임지고 나머지 프로세서는 이를 따름

Real-Time Scheduling

• hard real-time system
  • 정해진 시간 안에 반드시 끝내도록 스케줄링해야함
• soft real-time system
  • 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
  • 데드라인 완전 엄수까지는 아님

Thread Scheduling

• Local Scheduling
  • ULT 의 경우 사용자 수준의 스레드 라이브러리에 의해 어떤 스레드를 스케줄할지 결정
• Global Scheduling
  • KLT의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정