8 CPU Scheduling

CPU 스케줄링은 운영 체제에서 여러 프로세스가 CPU를 공유하여 실행될 때, 어떤 순서로 CPU를 할당할지 결정하는 방법이나 정책을 의미합니다. 여러 프로세스가 동시에 실행될 수 있는 환경에서 CPU 스케줄러는 프로세스 간의 경쟁을 조절하고 효율적으로 CPU를 활용하기 위한 일련의 규칙과 알고리즘을 적용합니다.

 

CPU 스케줄링의 목표

• 공평성(Fairness): 모든 프로세스에게 공평한 실행 기회를 제공하여, 어떤 프로세스도 지나치게 소홀히 받지 않도록 합니다.
• 처리량(Maximum Throughput): 단위 시간당 최대한 많은 프로세스를 실행하여 시스템의 처리량을 극대화합니다.
• 대기 시간 최소화(Minimizing Waiting Time): 프로세스가 CPU를 기다리는 시간을 최소화하여 응답 시간을 향상시킵니다.
• 우선순위 지정(Priority Assignment): 특정 프로세스나 작업에 대해 우선순위를 지정하여 중요한 작업이나 시스템의 특정 요구 사항을 충족시킵니다.
• 전체 시스템의 효율화(Efficiency): CPU와 다른 자원들을 효과적으로 활용하여 시스템 성능을 향상시킵니다.

스케줄링 알고리즘은 이러한 목표들을 달성하기 위해 다양한 방식으로 프로세스를 선택하고 관리합니다. 알고리즘의 선택은 시스템의 특성, 사용 목적, 환경 등에 따라 다를 수 있습니다.

 

 

---

 

준비 큐(Ready Queue)와 대기 큐(Waiting Queue)

준비 큐는 현재 CPU에서 실행 가능한 프로세스들을 담는 큐이고, 대기 큐는 특정 이벤트를 기다리거나 특정 조건이 충족되기를 기다리는 프로세스들을 담는 큐입니다. 이들 큐는 스케줄러가 프로세스를 효과적으로 관리하고 스케줄링 알고리즘을 적용하기 위해 사용됩니다.

일반적으로 입출력 작업이 많은 프로세스는 CPU 작업이 많은 프로세스보다 우선순위가 높을 수 있습니다. 이는 입출력 작업이 완료될 때까지 해당 프로세스가 CPU를 사용하지 않는 대기 상태에 있어야 하기 때문입니다.

 

---

 

 

여러 가지 CPU 스케줄링 알고리즘

1) FCFS (First-Come-First-Served)

가장 간단한 스케줄링 알고리즘으로, 먼저 도착한 프로세스가 먼저 실행되는 방식입니다. 대기 시간이 긴 프로세스가 먼저 도착하면 평균 대기 시간이 늘어날 수 있습니다. (=호위 효과) 

2) SJF (Shortest Job First)
실행 시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘입니다. 평균 대기 시간을 최소화할 수 있으나, 실행 시간을 정확히 예측하기 어려운 경우가 있습니다.

3) Priority Scheduling
각 프로세스에 우선순위를 할당하고, 우선순위가 높은 프로세스를 먼저 실행하는 알고리즘입니다. 우선순위는 정적으로 할당될 수 있거나, 동적으로 변할 수 있습니다.

 

부작용으로는 우선순위가 높은 프로세스만 처리된다는 것입니다. 따라서 우선순위가 낮아 계속 대기 중인 프로세스는 기아 현상(Starvation)을 가지게 됩니다. 이를 해결하기 위해 프로세스의 우선순위를 점차 높이는 방식(=에이징)이 도입될 수 있습니다. 

4) Round Robin
각 프로세스에 일정한 시간의 할당량을 부여하고, 해당 시간이 지나면 다음 프로세스로 넘어가는 방식입니다. 시분할 시스템에서 주로 사용되며, 모든 프로세스에게 공평한 실행 기회를 부여합니다

FCFS + Time Slice (각 프로세스가 CPU를 사용할 수 있는 시간을 따로 정해둔 것)  

5) Multilevel Queue Scheduling
프로세스를 여러 개의 큐로 나누고 각 큐에 다른 우선순위를 부여하는 방식입니다. 각 큐마다 독립적인 스케줄링 알고리즘을 적용할 수 있습니다.

여러 개의 큐로 나누다보니 프로세스간에 이동이 불가능하고 우선순위가 낮은 프로세스는 계속 실행이 안 되는 기아 현상이 생깁니다. 

6) Multilevel Feedback Queue Scheduling
Multilevel Queue와 유사하지만, 프로세스가 다른 큐로 이동할 수 있는 동적인 방식을 가지고 있습니다. 우선순위가 낮은 큐에서 실행 중인 프로세스가 CPU를 많이 사용하면 우선순위를 높은 큐로 이동할 수 있습니다.

 

 

---

 

 

선점형 & 비선점형 스케줄링

선점형과 비선점형 스케줄링은 CPU 스케줄링에서 프로세스 간의 CPU 할당 방식을 나타내는 두 가지 기본적인 유형입니다.

선점형(Preemptive) 스케줄링

• 선점형 스케줄링은 현재 실행 중인 프로세스가 다른 프로세스에 의해 강제로 중단될 수 있는 방식입니다.
• 스케줄러는 언제든지 우선순위가 높은 새로운 프로세스로 전환할 수 있습니다.
• 선점형 스케줄링을 사용하는 시스템에서는 프로세스의 실행이 강제로 중단될 수 있기 때문에, 타임 슬라이스(time slice) 또는 양자(quantum)라 불리는 작은 시간 단위로 CPU를 할당합니다. 이 시간 동안에만 해당 프로세스가 CPU를 점유하며, 타임 슬라이스가 끝나면 다음 프로세스가 실행됩니다.
• 대표적인 선점형 스케줄링 알고리즘으로는 Round Robin이 있습니다.

 

비선점형(Non-Preemptive) 스케줄링

• 비선점형 스케줄링은 현재 실행 중인 프로세스가 완료되거나 대기 상태로 들어가지 않는 이상, 다른 프로세스에 의해 강제로 중단되지 않는 방식입니다.
• 한 프로세스가 CPU를 할당받으면 해당 프로세스가 종료되거나 I/O 요청 등으로 대기 상태에 들어가기 전까지 CPU를 계속 보유합니다.
• 선점형에 비해 간단하고 오버헤드가 적은 특징이 있지만, 응답 시간이 더 오래 걸릴 수 있습니다.
• 대표적인 비선점형 스케줄링 알고리즘으로는 FCFS(First-Come-First-Served)와 SJF(Shortest Job First)가 있습니다.

선점형과 비선점형 스케줄링의 선택은 시스템의 요구사항과 특성에 따라 달라지며, 성능과 효율성을 고려하여 적절한 방법을 선택하는 것이 중요합니다.

 

 

---

CPU scheduling is an operating system technique that determines how processes, sharing the CPU, are scheduled for execution, aiming to achieve efficient resource utilization and minimize response times.