[OS] CPU 스케줄링

CPU 스케줄링

• 메모리에 있는 여러 프로세스에게 어떤 식으로 CPU time을 할당을 해줄 것인지 정하는 것입니다.
• 멀티 프로그래밍을 기반으로 합니다.
• CPU 사용률, 처리량을 최대로 하는 것이 CPU 스케줄링의 목적입니다.

 

CPU 스케줄링의 종류

CPU 스케줄링이 동작하는 시점은 4가지가 있습니다.

1. Running -> Waiting

2. Running -> Ready

3. 프로세스 종료

4. Ready -> Running

 

 

비선점형 스케줄링

• 1과 3의 상황에서만 동작하는 스케줄링 기법입니다.
• 한 작업이 CPU time을 할당받으면 그 작업이 끝날 때까지 운영체제가 중단하거나 다른 작업을 할당할 수 없습니다.

 

선점형 스케줄링

• 그 외의 다른 스케줄링 기법입니다.
• 운영체제가 중간에 실행중인 작업을 중단하고 다른 작업을 할당하는 게 가능합니다.

 

스케줄링의 중요한 요소

CPU 사용률 (CPU Utilization)

• 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율입니다.
• CPU가 잘 사용됬는지 안됬는지를 판단하는 기준이라고 할 수 있습니다.

처리량 (Throughput)

• CPU가 단위 시간 당 처리하는 프로세스의 개수입니다.

응답 시간 (Response Time)

• Interactive System에서 요청 후 첫 응답이 올 때까지의 시간입니다.

대기 시간 (Waiting Time)

• Process가 Ready Queue 내에서 대기하는 시간의 총합입니다.
• 얼마나 Process들에게 공평하게 시간을 나눠줬는지를 판단할 수 있습니다.

Turnaround Time

• Process가 시작해서 끝날 때까지 걸리는 시간을 말합니다.

 

스케줄링 알고리즘

1.  FCFS Scheduling

2. Shortest Job First Scheduling

3. Priority Scheduling

4. Round Robin Scheduling

5. Multilevel Queue Scheduling

6. Multilevel Feedback Queue Scheduling

 

1.  FCFS Scheduling (선입 선출)

• 선착순 방식으로 온 순서대로 처리하는 방식입니다.
• 작업의 수행 순서에 따라서 대기시간이 바뀝니다.
• 비선점형 방식입니다.

 

 

2.  Shortest Job First Scheduling (SJF)

• CPU Burst Time (CPU 연산에 수행되는 시간)이 가장 짧은 Process를 CPU에 할당하는 방식입니다.
• 비선점형 방식과 선점형 방식(SRTF)으로 나뉩니다.
  • 비선점형은 한번 작업이 시작되면 중간에 끝날 수 없고, 작업이 끝났을 때 시점으로 CPU burst time이 적은 일 순서대로 처리하는 방식입니다.
  • 선점형 방식은 작업이 실행되고 있는 중에도 남아있는 시간이 적은 작업이 새로 들어오면 그 job을 먼저 실행시켜주는 방식입니다.

 

3.  Priority Scheduling 

• 여러 가지 프로세스 중에서 운영체제나 사용자가 우선순위를 정해서 우선순위대로 처리해주는 방식입니다.
• 비선점형 방식과 선점형 방식이 있습니다.
• 문제점 : 우선순위가 낮은 프로세스는 계속 수행되지 못합니다. (기아 상태)
• 해결책 : Aging 기법 사용, 할당을 기다리는 시간에 따라 우선순위를 증가시켜줍니다.
• 예시 : 자동차에서의 브레이크 작업 (우선순위 1위)

 

4.  Round-Robin Scheduling (RR)

• CPU를 일정 시간 단위(Time Quantum)로 할당합니다.
• Time Quantum 만큼 공평하게 프로세스들에게 CPU를 돌아가며 할당시켜주는 방식입니다.
• Time Quantum 만큼 수행한 프로세스는 Ready Queue의 끝으로 들어가 다시 할당을 기다립니다.
• 처리해주는 순서 자체는 FCFS와 동일합니다.
• 선점형 방식입니다.
• Time Quantum이 클수록, FCFS 스케줄링과 같아져 성능이 저하됩니다.
• Time Quantum이 작을수록, 문맥 전환(Context Switching) 오버헤드가 커져서 효율이 떨어질 수 있습니다.
• 결론 : Time Quantum을 잘 정해야 합니다.

 

5.  Multilevel Queue Scheduling

• 우선순위에 따라 큐를 여러 개로 분리해서 각각에 대해 다른 스케줄링 알고리즘을 사용하는 기법입니다.

 

6.  Multilevel Feedback Queue Scheduling

• Multilevel Queue에서 프로세스들이 다른 큐로 이동할 수 있게 한 스케줄링 기법입니다.

 

Reference

https://velog.io/@mu1616/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81

CPU 스케줄링