[OS] CPU 스케줄링

CPU를 여러개 사용하는 것처럼 보이게 하기 위해 CPU 가상화를 사용한다.

가상화를 어떻게 하는걸까? 정말 쉽다. 여러개의 프로세스가 빠르게 전환하면서 CPU를 짧게식 사용하면 각 프로세스가 동시에 작업을 하는것처럼 보이게한다.

그런데 이러한 가상화를 실현하기 위해서는 우선 성능이 중요하다. 그렇다면 성능에 대해 먼저 알아보자.

성능 측정

우리가 성능을 측정할 떄는 소프트웨어 성능과 시스템 성능을 측정한다.

시스템 성능

시스템의 성능을 측정하는 척도는 다음과 같다.

1. CPU Utilization(CPU 이용률) : CPU를 많이 사용하면 할 수 록 성능이 좋다.
2. Throughput(처리량) : 주어진 시간에 얼마나 많은 일을 처리 하였는가.

소프트웨어 성능

1. TunrAroundTime(반환시간) : 작업을 끝내고 반환하는 시점 작업이 시스템에 도착한 시간을 뺀 시간
2. Waiting Time(대기 시간)  : Ready Queue에서 기다린 시간
3. Response Time(응답 시간)  : 처음 CPU를 할당받기위해 기다린 시간

 

이렇게 성능을 가장 좋게 사용하기 위해 나온 알고리즘들이 존재한다.

스케줄링 알고리즘

1. FIFO(First In Fisrt Out)

FIFO(선입선출) 알고리즘은 작업이 도착한 순서대로 처리되는 방식이다. 먼저 도착한 작업이 먼저 실행되며, 이후에 도착한 작업은 앞선 작업이 완료될 때까지 대기해야 한다.

이 방식의 단점은 실행 시간이 짧은 작업도 앞선 긴 작업이 끝날 때까지 기다려야 한다는 점이다. 이러한 현상을 Convoy Effect(호송 효과)라고 하며, 이는 짧은 작업들이 긴 작업이 끝날 때까지 자원을 사용할 수 없어 전체적인 반환 시간이 증가하는 문제를 초래한다.

 

 

이러한 단점을 없애기 위해 SJF가 나타났다.

2. SJF(Shortest Job First)

 

반환시간을 줄이기 위해 작업시간이 가장 작은 순으로 스케줄링하는 알고리즘이다.

 

하지만 조금 부족한거 같다.

만약 A작업이 0에 도착하여 작업시간이 100인 상태이고 B작업이 30에 도착하여 작업시간이 5라면 이렇게 중간에 들어오면 거의 똑같다.

3. STCF(Shortest Time-to-Completion First)

작업 소요시간이 가장적은걸 우선으로 하나는 의미이다.

언제든 새로운 작업이 들어온다면 작업 소요시간이 가장적은걸 스케줄한다. 즉 작업을 진행하는 프로세스를 중단시키고 작업 소요시간이 더 적은 프로세스에게 CPU를 할당합니다.

선점형 vs 비선점형 알고리즘

선점형 스케줄링은 운영 체제가 실행 중인 프로세스를 중단하고 다른 프로세스에 CPU를 할당할 수 있습니다.
비선점형 스케줄링은 프로세스가 시작되면 완료될 때까지 중단되지 않습니다.

 

 

작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면, STCF는 매우 훌륭한 정책이다. 하지만 현실적으로 작업의 길이를 미리 알고있기 힘들며, 사용자와 상호작용하는게 쉽지 않았습니다. 그렇기에 응답소요시간을 줄이이 위한 알고리즘이 필요했습니다.

4. Round Robin

Round Robin 스케줄링은 각 프로세스에 고정된 시간 할당량(타임 퀀텀)을 부여하여, 해당 시간 동안 프로세스가 작업을 수행하도록 합니다. 타임 퀀텀이 만료되면 운영체제는 문맥 교환(Context Switching)을 통해 CPU를 다음 프로세스에 할당합니다. 이처럼 빠르게 프로세스 간 전환이 이루어지면, 각 프로세스는 짧은 시간 동안이라도 CPU를 사용할 수 있게 되어 응답 시간이 줄어들고, 사용자와의 상호작용성이 개선됩니다.

하지만 이 방식에도 단점이 존재합니다.

• 타임 퀀텀이 너무 짧은 경우: 프로세스 간의 문맥 교환 비용이 증가하여 오버헤드가 커집니다.
• 타임 퀀텀이 너무 긴 경우: 결국 FIFO(선입선출) 스케줄링과 유사해져, 반응성이 떨어질 수 있

5. 입출력 작업을 고려한 스케줄링

모든 프로그램은 입출력(I/O) 작업을 수행합니다. 입력이 없는 프로그램은 매번 동일한 출력을 생성할 뿐이며, 출력이 없는 프로그램은 실행 의미가 없다고 볼 수 있습니다. 따라서 입출력은 시스템에서 필수적인 요소이며, 스케줄러는 이를 효율적으로 관리해야 합니다.

• 입출력 요청 시:
  프로세스가 입출력을 요청하면, 입출력이 완료될 때까지 대기 상태로 전환됩니다. 예를 들어, 하드 디스크 드라이브에 입출력을 요청한 경우, 드라이브의 워크로드에 따라 몇 초 또는 그 이상 블록될 수 있습니다. 이때 스케줄러는 CPU를 다른 준비 상태의 프로세스에 할당해 자원을 낭비하지 않도록 해야 합니다.
• 입출력 완료 시:
  입출력이 완료되면 인터럽트가 발생하고, 운영 체제는 해당 프로세스를 대기 상태에서 준비 상태로 이동시킵니다. 스케줄러는 이 프로세스를 즉시 실행할지, 아니면 다른 프로세스를 우선 실행할지 결정해야 합니다.

입출력을 고려하지 않는 스케줄링은 CPU가 입출력 대기 중인 프로세스로 인해 유휴 상태에 빠지게 만들어 자원을 낭비합니다. 따라서 효율적인 스케줄링은 CPU와 I/O 자원을 동시에 활용할 수 있어야 합니다.