[CS] CPU 스케줄링

📌  스케줄링이란?

---

언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업. 

 

🔹 시스템에서의 시간은 기다리는(waiting) 시간과 작업을 수행하는 시간을 합친 것 이다.  시스템에서의 중요한 점은 이러한 시간의 합인 total time을 minimize 하는 것이 목표이다.

 

만약 작업에 데드라인이 있고, 각 작업이 동일한 완료 시간을 가진다고 가정한다. 또한 작업을 데드라인 내에 완료하면 이익을 얻는다. 작업이 해당 데드라인 이후에 수행되면 불가능한 스케줄이라고 한다. 이런 불가능한 스케줄은 고려하지 않는다. 왜냐하면 데드라인 이후에 작업을 실행하는 것은 이익을 얻을 수 없기 때문이다.

 

 따라서 목표는 이익의 총합이 극대화되게 하는 것이다.

Job	Deadline	Profit
1	2	30
2	1	35
3	2	25
4	1	40

 

이렇게 작업의 형태가 정해져있을 때 불가능하지 않는 모든 스케줄을 알아본다면,

Schedule	Total Profit
1, 3	55
2, 1	65
2, 3	60
3, 1	55
4, 1	70
4, 3	65

이때, [4, 1]이 최적의 스케쥴이란 걸 알 수 있다.

 

하지만 모든 가능한 스케줄을 시도하여 최적의 스케줄을 찾아내는 것이 최선은 아니기 때문에 다른 알고리즘 방식으로 최적의 스케줄을 구해야 한다. 왜냐하면 이러한 방법은 계승(factorial) 시간이 걸리며, 최악의 경우 지수(exponential) 시간이 소요될 수 있기 때문이다.

 

📑 CPU 스케줄링

---

여러 프로세스들 중에서 어떤 프로세스를 먼저 실행할지, 얼마나 오랫동안 실행할지 등을 결정하는 일련의 과정.

 

선점형(Preemptive), 비선점형(non-preemptive) 스케줄링

CPU 스케줄러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU를 할당해주는 역할을 한다.

 

CPU 스케줄러는 프로세스들이 다음과 같은 상황에 있을 때 스케줄링을 결정한다.

 

1. 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때 ( ex : I/O 발생 )
2. 실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : intterupt 발생 )
3. 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : I/O 완료 시 )
4. 종료(Terminated)될 때

1번과 4번 상황에서만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링이라고 한다.

이외의 모든 스케줄링은 선점형(preemptive) 스케줄링이라고 한다.

 

비선점형 스케줄링

    ◈  프로세스가 CPU를 점유하고 있다면 이를 가져올 수 없다.

    ◈  필요한 문맥 교환만 일어나므로 오버헤드(overhead)가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 난다.

 

선점형 스케줄링

    ◈  프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 가져올 수 있는 방식

    ◈  CPU 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영 가능

    ◈  잦은 문맥 교환으로 오버헤드(Overhead)가 커질 수 있다.

 

CPU 스케줄링 평가 기준 ( CPU Scheduling Criteria )

1. CPU 이용률(CPU utilization)
   • 시간당 CPU를 사용한 시간의 비율
   • 프로세서를 실행상태로 항상 유지하려고 해야 한다.
2. 처리율(Throughput)
   • 시간당 처리한 작업의 비율
   • 단위 시간당 완료되는 작업 수가 많도록 해야 한다.
3. 반환시간(Turnaround Time)
   • 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
   • 작업이 준비 큐(ready queue)에서 기다린 시간부터 CPU에서 실행된 시간, I/O 작업 시간의 합이다.
4. 대기시간(Waiting Time)
   • 대기열에 들어와 CPU를 할당받기 까지 기다린 시간
   • 준비 큐에서 기다린 시간의 총합
5. 반응시간(Response Time)
   • 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
   • 대기시간과 비슷하지만 다른 점은, 대기시간은 준비 큐에서 기다린 모든 시간을 합친 것이지만 반응 시간은 CPU를 할당받은 최초의 순간까지 기다린 시간 한번 만을 측정한다.

-> CPU 이용률과 처리율은 극대화하는 것이 좋고 반환시간, 대기시간, 반응시간은 줄이는 것이 일반적으로 좋다고 한다.

 

⛓ 스케줄링 알고리즘

---

FCFS (First Come First Served) 스케줄링

가장 먼저 요청한 프로세스에 CPU를 할당해주는 방식이다.

• 비선점형(Non-preemptive) 스케줄링이다.
• 작성이 간단하고 이해하기 쉽다.
• 평균 대기 시간(Average Waiting Time)이 길어질 수 있다.
• 응답 시간(Response Time)이 길어질 수 있다.
• 반환시간(Turnaround Time) 면에서는 좋을 수 있다.
• Convoy Effect(호위 효과)가 발생할 수 있다.

SJF(Shortest-Job-First) 스케줄링

다음 CPU burst time의 길이를 고려해서 스케줄링을 결정하는 알고리즘이다.

• 비선점형과 선점형이 따로 존재한다.
• 비선점형에서는 실행되고 있는 프로세스는 끝까지 실행한다.
• 선점형에서는 현재 실행되고 있는 프로세스의 남은 시간보다 도착한 다음 프로세스가 더 빨리 끝날 수 있는 프로세스라면 다음 프로세스를 실행하도록 바꾸게 된다. SRTF(Shortest Remaining Time First)라고도 부른다.
• SJF 스케줄링은 평균 대기 시간을 줄일 수 있다.
• 하지만 다음 프로세스의 CPU burst time을 예측하는 것이 어렵다는 문제가 존재한다.

deadline 스케줄링

작업들을 마감시간까지 완성하도록 계획한 스케줄링이다.

• 비선점형 이다.
• 프로세스에게 할당한 정확한 시간을 추정해야 한다.
• 사용자는 시스템이 요구한 프로세스에 대한 정확한 정보를 제공해야 한다.
• deadline이 빠르고 동작시간 짧은 순 정렬 한다.

기한부 스케줄링의 경우 foreach함수를 이용하여 다음과 같은 결과를 얻었다. 이때 기한부 스케줄링은 deadline이 빠르고 동작시간 짧은 순 정렬해야 하기 때문에 아래의 과정을 통해 정렬해준다.

this.process.sort((a, b) => a.deadLine - b.deadLine);

Deadline 스케줄링 코드 실행

Priority 스케줄링

각각의 프로세스에 우선순위 넘버가 있다.

• 가장 높은 우선순위의 프로세스에 CPU를 할당한다.
• 선점형과 비선점형이 나뉜다.
• SJF도 Priority 스케줄링이라고 할 수 있다. ( 다음 CPU burst time이 우선순위인 것처럼 작동하므로)
• 기아(Starvation) 문제가 발생할 수 있다. 기아 문제란 낮은 우선순위의 프로세스가 절대 실행되지 않는 문제를 뜻함.
• 기아문제를 해결하기 위해서 노화(aging)를 사용할 수 있다. 시간이 지날수록 프로세스의 우선순위를 높여주는 식.

기존의 deadline 스케줄링에서 정렬기준만 priority로 바꿔주면 되는 문제였다. 아래와 같이 우선순위에 맞게 정렬해준 후 출력값이 나오도록 코드를 작성했다.

this.process.sort((a, b) => a.priority - b.priority);

Priority 스케줄링 실행

Round Robin(RR) 스케줄링

각각의 프로세스에 동일한 CPU 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다.

• 할당 시간 내에 처리를 완료하지 못하면 다음 프로세스로 넘어가므로 선점형 방식이다.
• n개의 프로세스가 있을 때 할당 시간을 q로 설정하면, 어떤 프로세스도 (n-1) q 시간 이상을 기다리지 않아도 된다.
• 응답 시간을 빠르게 할 수 있다는 장점이 있다.
• q가 커진다면 FIFO 처럼 작동한다.
• q가 매우 작아지면 process sharing이라고 부른다. 이것은 n개의 프로세스가 프로세서 속도의 1/n 씩으로 작동함을 의미한다.

기존의 스케줄링과 다르게 한개의 프로세스가 끝날때까지 동작하는 것이 아니라 모든 프로세스를 1초마다 동작하는 것만 생각하고 코드를 작성했다.

라운드로빈 스케줄링 실행 영상

📸 참조

---

https://code-lab1.tistory.com/45