2021년 09월 12일 TIL

오늘은 CPU 스케쥴러에 대해 공부했다.

CPU Scheduling

CPU 스케줄링의 결정 시점은 다음과 같이 프로세스의 상태변화가 있을때 발생한다.

1. 수행 -> 대기 (interrupt)
2. 수행 -> 준비 (time-out)
3. 대기 -> 준비 (wake-up)
4. 수행 -> 종료

선점형 vs 비선점형

• 선점형 스케쥴러(Preemptive Scheduling)
  • 하나의 프로세스가 다른 프로세스 대신에 프로세서(CPU)를 차지할 수 있음
  • 프로세스 running 도중에 스케쥴러가 이를 중단시키고 다른 프로세스로 교체 가능하다는 의미
• 비선점형 스케쥴러(Non-Preemptive Scheduling)
  • 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없음
  • 프로세스가 자발적으로 blocked 상태로 들어가거나 실행이 끝났을 때에만 다른 프로세스로 교체 가능하다는 의미
  • 위의 결정 시점 중 1번과 4번의 상황에서만 스케줄링 발생
  • 일반적으로 선점형보다 스케줄러의 호출 빈도가 낮으며, context switching overhead가 적다.
    • context switching란, 멀티 프로세서 환경에서 인터럽트 요청에 의해 다음 우선 순위의 프로세스가 실행되어야 할 때 기존 프로세스의 상태 또는 레지스터의 값을 저장하고, cpu가 다음 프로세스를 실행하도록 새로운 프로세스의 상태 또는 레지스터의 값을 저장하는 작업.
    • 그 과정에서의 시간과 메모리를 context switching overhead라고 하는것이다

스케쥴링 알고리즘

어떤 프로세스를 먼저 실행시킬 지에 대한 알고리즘

• FIFO(FCFS) First In First Out / First Come First Served
  • 들어오는 순서대로 처리하는 알고리즘
• SJF
  • FIFO의 단점을 보완하기 위해 만든 스케쥴링 알고리즘
  • 가장 CPU burst가 적은 것을 먼저 수행한다( 빨리 끝나는 것부터 처리한다. )
  • 선점형 방식(preemptive)과 비선점형 방식(non-preemptive)이 있다.
    • non-preemptive한 방식의 SJF는 그냥 SJF라고 부른다
    • preemptive한 방식은 shortest remaining time first라고 부른다. (SRTF)
• Priority-Based
  • 우선순위를 부여하여 스케쥴링하는 방식
  • 우선순위는 운영체제가 정하는 것이 아니라, 바깥에서 이미 설정된 기준에 따른다
  • 단점으로는 starvation이 있다.
    • Priority가 낮은 프로세스가 무한히 기다리는 것을 말한다.
    • aging 기법등을 통해 해결 가능

시분할 시스템을 위한 기본 알고리즘(선점형 스케쥴러)

• Round-Robin
  • 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나
  • 프로세스들 간에 우선순위를 두지 않고 순서대로 시간단위로 CPU를 할당하는 CPU 스케줄링 알고리즘