CPU 스케쥴링 알고리즘이란 무엇인가요?

CPU 스케쥴링 알고리즘은 어떤 프로세스에게 CPU를 할당할 지 결정하는 알고리즘 입니다. CPU 알고리즘은 CPU 이용률은 높게, 준비 큐에 있는 프로세스는 적게, 그리고 응답시간은 짧게 구현하는 거을 목표로 합니다.

3.4.1. 비선점형 방식

비선점형 CPU 스케쥴링과 그 종류에 대해 설명해주세요

비선점형 CPU 스케쥴링은, 현재 동작 중인 프로세스로부터 CPU 소유권을 강제로 빼앗지 않는 스케쥴링 방식입니다. 따라서 프로세스가 스스로 소유권을 반납하기 전까지, CPU를 사용할 수 있기 때문에 컨텍스트 스위칭이 적게 일어납니다. 반면 우선순위가 낮은 프로세스들이 오랫동안 대기할 수 있는 문제가 발생합니다.

비선점형 CPU 스케쥴링 알고리즘에는 다음과 같은 종류가 있습니다.

• FCFS (First-Come, First-Served)
  먼저 도착한 프로세스부터 순서대로 CPU를 할당하는 알고리즘입니다. 프로세스의 도착 시간과 실행 시간에 따라 대기 시간이 크게 달라질 수 있습니다. 예를 들어 길게 수행되는 프로세스가 먼저 도착할 경우, 뒤에 대기하는 프로세스가 많아집니다.

• SJF (Shortest Job First)
  실행 시간이 가장 짧은 프로세스엑 CPU를 할당하는 알고리즘입니다. 실행 시간은 과거의 실행 시간을 바타으로 계산해 추측합니다. 평균 대기 시간을 최소화하는데 효과적이지만, 긴 시간을 가진 프로셋가 실행되지 않는 스타베이션(startvation)이 발생할 수 있습니다.

• 우선순위 (Priority Scheduling)
  각 프로세스마다 우선순위를 할당하고, 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 알고리즘입니다. 동일 우선순위에 대해서는 FCFS와 같은 다른 알고리즘을 적용할 수 있습니다.

• 최상 응답 비율 순서 (HRRN, Highest Response Ratio Next)
  대기 시간과 실행 시간을 고려하여 우선순위를 결정하는 알고리즘입니다. 실행 시간이 길어질수록 우선순위가 높아지는 방식으로 동작합니다. SJF 스케쥴링의 Starvation을 보완하기 위해 만들어진 알고리즘입니다.
  $${\displaystyle Priority={\frac {대기\ 시간+실행\ 시간}{실행\ 시간}}}$$

3.4.2. 선점형 방식

선점형 CPU 스케쥴링과 그 종류에 대해 설명해주세요

선점형 CPU 스케쥴링은 실행 중인 프로세스로부터 CPU 소유권을 강제로 가져올 수 있는 스케쥴링 방식입니다. 비선점형 방식에 비해 컨텍스트 스위칭이 많이 일어나지만, 유연하게 멀티 프로세싱(스레딩)을 지원할 수 있기 때문에 현대 운영체제에서 채택한 방식입니다.

선점형 CPU 스케쥴링 알고리즘에는 다음과 같은 종류가 있습니다.

• 라운드 로빈(Round Robin)
  각 프로세스마다 CPU 할당 시간을 일정하게 분배합니다. 예를 들어 할당 시간이 q이고, 총 프로세스가 N개라면, q*(N-1)의 시간마다 CPU를 할당 받게 됩니다.
  할당 시간이 너무 짧을 경우, 잦은 컨텍스트 스위칭으로 오버헤드가 발생합니다.
  반면 할당 시간이 너무 길 경우, 프로세스의 평균 응답 시간이 짧아집니다.

• SRTF(Shortest Remaining Time First)
  현재 프로세스 중 실행 시간이 가장 짧은 프로세스에게 CPU를 할당하는 알고리즘입니다. SJF 방식과 다르게 현재 프로세스가 실행도는 중이라도, 더 짧은 시간을 가진 프로세스가 들어오면 CPU 소유권을 넘겨줍니다.

• 다단계 큐(Multilevel Queue)
  프로세스들을 여러 개의 우선순위 큐로 분리하여 관리하는 알고리즘입니다. 각 큐마다 라운드 로빈이나 FCFS와 같은 서로 다른 스케줄링 알고리즘을 적용할 수 있습니다.