[OS] CPU Scheduling

스케줄링

CPU를 잘 사용하기 위해 프로세스를 잘 배정하기

• 조건 : 오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓
• 목표

1. Batch System: 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
2. Interactive System: 빠른 응답 시간. 적은 대기 시간.
3. Real-time System: 기한(deadline) 맞추기.

스케줄링 종류

스케줄링은 선점 스케줄링, 비선점 스케줄링으로 나뉜다.

프로세스 상태

• 비선점 스케줄링 : Interrupt, Scheduler Dispatch
• 선점 스케줄링 : I/O or Event Wait

프로세스의 상태 전이

승인 (Admitted) : 프로세스 생성이 가능하여 승인됨
스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행
인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리
입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태
입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만듦

선점 스케줄링

CPU가 어떤 프로세스에 의해 점유 중일 때, 우선순위가 높은 프로세스가 CPU를 차지하는 방식의 스케줄링

특징

• 우선순위가 높은 프로세스를 빠르게 처리할 경우 유용하다.
• 선점이 일어나면 오버헤드가 발생하며 처리 시간을 예측하기 힘들다.
• 스케줄링이 일어나는 시점 : I/0 요청, I/0 응답, Interrupt 발생, 작업 완료 등

선점 스케줄링 종류

• SRT(Shortest Remaining Time) 스케줄링
  짧은 시간 순서대로 프로세스 수행한다.
  남은 처리 시간이 더 짧은 프로세스가 Ready 큐에 들어오면 그 프로세스가 바로 선점된다. SJF의 선점 버전
• RR(Round-Robin) 스케줄링
  각 프로세스는 같은 크기의 CPU 시간을 할당받고 FIFO에 의해 실행된다.
  할당 시간이 너무 크면 스케줄링의 의미가 없어지고, 너무 작으면 오버헤드가 커진다.
• 다단계 큐(Multi-level Queue) 스케줄링
  Ready 큐를 여러 개 사용하는 방법이다.
  각각의 큐는 자신의 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위를 부여한다.
• 다단계 피드백 큐 스케줄링
  다단계 큐와 비슷하나 프로세스들이 큐를 이동할 수 있다.

비선점 스케줄링

CPU가 어떤 프로세스에 의해 점유 중일 때, 다른 프로세스가 CPU를 차지하지 못하는 방식의 스케줄링

특징

• 모든 프로세스에 대한 요구를 공정하게 처리할 수 있다.
• 응답 시간 예측에 용이하다.
• 스케줄링이 일어나는 시점 : 프로세스가 스스로 CPU를 놓아주는 시점(작업이 완료되는 시점)

비선점 스케줄링 종류

• HRN(Highest Response ratio next) 스케줄링
  수행 시간의 길이와 대기 시간을 모두 고려해 우선순위를 정하는 방법.
  긴 작업과 짧은 작업 간의 지나친 불평등을 어느 정도 보완한다.
  우선순위 계산 공식 : (대기시간 + 서비스 시간) / 서비스시간
• SJF(Shortest Jop First) 스케줄링
  큐 안에 있는 프로세스 중 수행 시간이 짧은 것부터 수행하는 방법.
  평균 대기 시간을 감소시킨다.
• Priority 스케줄링
  프로세스에게 우선순위를 정적 또는 동적으로 부여하여 우선순위가 높은 순서대로 처리한다.
  동적으로 부여하는 경우, 구현이 복잡하고 오버헤드가 많다는 단점이 있지만 시스템의 응답 속도를 증가시킬 수 있다.
• Deadline 스케줄링
  작업을 명시된 시간이나 기한 내에 완료하도록 계획하는 방법.
• FCFS 스케줄링
  프로세스가 Ready 큐에 도착한 순서대로 CPU를 할당받는 방법.
  작업 완료 시간을 예측하기 매우 용이하다.
  하지만 중요한 작업을 기다리게 할 수 있다.

Aging 기법

특정 프로세스의 우선순위가 낮아 무한정 기다리는 경우, 한 번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당받도록 하는 기법

SJF나 Priority 스케줄링에서 발생하는 무한 연기 상태, 기아 상태를 예방할 수 있다.

참고 사이트

CPU Scheduling
선점 스케줄링, 비선점 스케줄링
CPU 스케줄링 기법