[운영체제] CPU 스케줄링

CPU 스케줄링이란? 

여러 프로세스가 실행되고 있는 경우 CPU를 효율적으로 사용하기 위해 프로세스를 잘 배정하도록 하는 것
오버헤드는 줄이고, 사용률은 늘리고 기아 현상은 발생하지 않도록 하는 것 
Batch System : 가능하면 많은 일을 수행, 처리량이 중요하다. 
Interactive System : 빠른 응답시간 == 적은 대기 시간 
Real-time System : 데드라인 맞추기

선점과 비선점 스케줄링 

1. 선점 스케줄링 : OS가 CPU의 사용권을 프로세스에게 뺏을 수 있는 경우 
2. 비선점 스케줄링 : 프로세스가 종료되거나 I/O가 발생하는 경우를 제외하고는 실행 보장

CPU 스케줄링의 종류 

비선점 스케줄링 : FCFS (Fist Come First Served)

1. FIFO(First In First Out)라고도 불리는 알고리즘, 말 그대로 가장 먼저 들어온 프로세스가 가장 먼저 CPU를 할당받는다. 
2. 만약 처리하는데 오랜 시간이 걸리는 프로세스가 앞쪽으로 오게 되면 평균 대기 시간이 길어진다. 

비선점 스케줄링 : SJF (Shortest Job First) 

1. FCFS의 대기시간이 크다는 문제를 해결하기 위해 나온 알고리즘이다. 
2. FCFS가 수행시간이 긴 프로세스가 앞으로 오게 되면 평균 대기시간이 길어진다는 점을 방지하기 위해 수행시간이 짧은 프로세스를 먼저 CPU를 할당시키도록 하는 것이다. 
3. FCFS보다 평균 대기 시간이 감소했지만, 짧은 작업에 유리하다는 단점이 존재하다.
4. 하지만 CPU가 프로세스를 처리하기 전에 프로세스의 수행시간을 알 수 있는 방법이 없었기에 실제로 적용시키는 어려운 알고리즘이다. 

비선점 스케줄링 : HRN (Hightest Response-ratio Next) 

1. 우선순위를 공식을 이용하여 계산하여 SJF의 단점인 점유 불평등(짧은 작업에 유리)를 보완한 방법이다.
2. 우선순위 = (대기시간 + 실행시간) / 실행시간 
3. 오랫동안 대기하는 프로세스의 우선순위를 증가시킴으로서 기아 문제도 해결할 수 있다.

선점 스케줄링 : Priority Scheduling 

1. 준비 큐에 프로세스가 도착하면, 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에게 CPU를 할당한다. 
2. 만약 동일한 우선순위를 가지고 있다면 먼저 들어온 프로세스가 우선적으로 처리된다.
3. 우선 순위가 낮은 프로세스가 무한정 기다리는 기아 상태가 발생 할수도 있다.
4. 대기 시간에 비례하여 우선순위를 부여하는 에이징 기법을 적용하여 기아 상태를 방지할 수 있다.

선점 스케줄링 : Round Robin 

1. FCFS와 동일하게 처리되지만 각 프로세스는 동일한 시간의 타임 퀀텀 만큼 CPU를 할당 받는다.
2. 만약 타임 퀀텀이 크면 FCFS와 동일해지고, 작으면 Context Switching이 잦아져서 오버헤드가 증가하게 된다.

선점 스케줄링 : Multilevel-Queue 

1. 프로세스의 그룹에 따라 큐를 여러 개로 분리해놓고 큐 별로 스케줄링 알고리즘(보통 RR or FCFS)을 지정하는 것이다. 
2. foreground(Interactive Processes, System Processes)는 Round Robin 스케줄링을 적용시켜 Interactive하게 만들고 background는(Batch Processes) 프로세스들은 FCFS 스케줄링을 적용시킨다. 
3. 특정 큐에 들어가면 프로세스는 다른 큐로 이동하지 못한다.
4. 대기열 간의 스케줄링은 두가지 방법이 존재한다.

• 고정 우선 순위 선점형 스케줄링 방법 

각 큐는 우선 순위가 낮은 큐보다 절대적으로 높은 우선순위를 가지게 된다. 따라서 3번 큐는 1,2번 큐가 모든 프로세스를 완료할 때 까지 절대로 프로세스를 처리할 수 없다. 

• 타임 슬라이싱 

타임 퀀텀을 큐마다 다르게 설정하여 처리하는 방식이다. 

 

 

선점 스케줄링 : Multilevel-Feedback-Queue 

1. Multilevel Queue와 다르게 프로세스의 큐 간 이동이 허용된다.
2. 우선순위는 중요도를 판단하여 지정되지만 이것이 절대적이지 않을수도 있다, Multilevel Queue는 우선순위가 잘못된 것을 알아도 수정하지 못하지만 Multilevel Feedback Queue는 잘못된 것을 알면 피드백이 가능하다. 
3. 피드백을 위해 높은 우선순위 큐로 격상시키는 시기 결정 알고리즘과 격하시키는 시기 결정 알고리즘 마지막으로 프로세스들이 어느 큐에 들어갈지 결정하는 알고리즘이 존재한다. 
4. 낮은 우선 순위 큐의 프로세스는 높은 우선 순위 큐가 비어 있는 경우에만 실행이 가능하며, 높은 우선 순위 큐에 새로운 프로세스가 들어오면 낮은 우선 순위 큐에서 실행 중이던 프로세스는 중단된다.

• 동작 방식

  1. 프로세스가 실행을 시작하면 먼저 큐1에 들어간다.
  2. 큐 1에서 프로세스는 퀀텀 4로 실행되고 퀀텀 4를 통해 완료되거나 I/O작업을 수행하게 되는 경우에는 우선 순위가 변경되지 않고 다시 큐1에서 실행하게 된다.
  3. 만약 퀀텀 4로 완료되지 않으면 큐2로 이동한다.
  4. 2,3번 과정도 큐2에서 반복되지만 퀀텀 8로 실행되며, 만약 퀀텀8로 완료되지 않으면 큐3으로 이동하게 된다.
  5. 마지막 대기열 프로세스는 FCFS 방식으로 실행되게 된다.

스케줄링의 성능을 측정할 수 있는 기준 

1. Response Time : 작업이 처음 실행되기까지 걸린 시간
2. Turnaroudn TIme : 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때 까지 걸린 시간

 

Reference

https://www.geeksforgeeks.org/multilevel-queue-mlq-cpu-scheduling/

Multilevel Queue (MLQ) CPU Scheduling - GeeksforGeeks

https://gyoogle.dev/blog/computer-science/operating-system/CPU%20Scheduling.html

CPU Scheduling | 👨🏻‍💻 Tech Interview

https://www.geeksforgeeks.org/multilevel-feedback-queue-scheduling-mlfq-cpu-scheduling/

Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling - GeeksforGeeks