[운영체제] CPU 스케줄링 알고리즘

1. 개요

---

프로세스가 여러 개라면 어떤 프로세스에게 먼저 CPU 소유권을 제공해야 할까요? 이런 고민 속에서 CPU의 이용률은 높이고, 프로세스의 대기 시간은 줄이면서, 응답 시간은 짧게 하기 위해서 나온 것이 CPU 스케줄링 알고리즘입니다.

 

CPU 스케줄링 알고리즘의 7가지 종류 (이외에도 더 존재하지만 여기서는 이정도만)

 

• CPU 스케줄링 알고리즘은 크게 비선점형과 선점형으로 나눌 수 있습니다.
• 비선점형 방식에는 FCFS(First Come, First Served), SJF(Shortest Job First), 우선순위 알고리즘이 존재합니다.
• 선점형 방식에는 Round Robin(RR), SRT(Shortest Remaining Time), 다단계 큐, 다단계 피드백 큐 방식이 존재합니다.

 

 

 

2. 비선점형 방식 (non-preemptive)

---

• 비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식입니다.
• 다시 말해서 CPU가 실행되는 도중 중간에 강제로 프로세스를 중지하지 않는 방식을 말합니다.
• Context Switching이 적게 일어나기 때문에 부하가 적다는 특징이 있습니다.

 

(1) FCFS (First Come First Served)

• 이름 그대로 Ready Queue에 먼저 들어온 순서대로 처리하는 알고리즘입니다.
• 먼저 요청한 프로세스부터 CPU를 할당하여 처리합니다.
• 먼저 들어온 프로세스가 처리되는 시간 동안 프로세스들이 기다리는 시간이 길어지는 단점이 발생합니다. 이런 현상을 호위 효과라고 합니다.

Process 1이 처리되는 오랜 시간동안 기다리는 다른 프로세스들

 

 

(2) SJF (Shortest Job First)

• FCFS에서 발생하는 호위 효과를 방지할 수 있는 알고리즘입니다.
• CPU를 점유하는 시간이 짧은 프로세스부터 실행합니다.
• 호위 효과는 피할 수 있지만, 긴 처리 시간을 요구하는 프로세스가 실행되지 않는 기아현상(Starvation)이 발생할 수 있습니다.

파란색 Process가 처리된 후 빨간색이 들어오고, 그 다음으로 노란색이 들어와서 처리되는 상황 (초록색이 실행되지 않는 기아현상)

 

 

(3) 우선순위 알고리즘

• 프로세스들에게 우선순위를 부여하고, 그 우선순위대로 프로세스를 처리하는 알고리즘입니다.
• 만약 2개의 프로세스가 우선순위가 동일하다면 먼저 Ready Queue에 들어온 순서대로 처리합니다.
• 위에서 설명한 FCFS, SJF 알고리즘도 우선순위 알고리즘에 포함시킬 수 있습니다.
• 우선순위 알고리즘에서 발생할 수 있는 위험 요소는 위에서 말했던 "기아현상(Starvation)"이 있습니다.
• 기아현상을 해결하기 위해서 오랫동안 대기상태였던 프로세스의 우선순위를 점차 증가시키는 Aging(에이징) 기법을 사용합니다.

 

 

 

3. 선점형 방식

---

• 선점형은 현재 실행 중인 프로세스를 강제로 중단시켜 다른 프로세스에게 CPU 소유권을 할당하는 방식입니다.
• 비선점형에 비해 Context Switching이 빈번하게 발생한다는 특징이 있습니다.

 

(1) Round Robin(RR, 라운드 로빈)

• FCFS 알고리즘에 Time Slice(타임 슬라이스) 개념을 추가한 알고리즘으로 현대적인 CPU 스케줄링 방법입니다.
• 정해진 타임 슬라이스만큼 프로세스에게 CPU 소유권을 줘서 처리하는 방식입니다.
• 정해진 타임 슬라이스 만큼 CPU를 선점하여 프로세스를 처리하고, 만약 타임 슬라이스가 지났는데도 아직 처리되지 못했다면 Ready Queue의 가장 뒤쪽에 삽입됩니다.
• 타임 슬라이스가 너무 크다면 FCFS와 다를 것이 없어 호위 효과가 발생할 수 있고, 타임 슬라이스가 너무 작다면 Context Switching이 너무 빈번하게 발생하여 오버헤드가 증가되는 현상이 발생할 수 있습니다.
• 적당한 타임 슬라이스를 정하는 것이 중요한 알고리즘입니다.

Time Slice : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 말합니다.

 

 

(2) SRT (Shortest Remaining Time)

• Rround Robin 알고리즘에 SJF 알고리즘을 합친 알고리즘입니다.
• SRT에서는 프로세스가 정해진 시간(타임 슬라이스)만큼 CPU의 소유권을 얻어 처리될 수 있습니다. (Round Robin)
• 이때 CPU의 소유권을 얻는 우선순위는 남은 처리 시간이 적은 순으로 결정됩니다. (SJF)

 

 

(3) 다단계 큐 스케줄링 (Multilevel Queue 스케줄링)

• 우선순위별로 Ready Queue를 여러개 사용하는 방식의 스케줄링 알고리즘입니다.
• 우선순위가 낮은 Queue에 있는 프로세스부터 모두 처리하고, 그다음 우선순위의 Queue에 있는 프로세스를 처리합니다.
• 각 Ready Queue는 사용하는 알고리즘이 다를 수 있습니다.
• 대표적인 특징으로는 Queue에서 Queue 사이에 프로세스 이동은 불가능하기 때문에 Starvation(기아현상)이 발생할 확률이 높은 알고리즘입니다.

 

 

(4) 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue 스케줄링)

• 다단계 큐 스케줄링 방식에서 발전시킨 알고리즘입니다.
• Queue와 Queue 사이에 프로세스 이동이 가능하고, Aging 기법도 적용할 수 있는 스케줄링 알고리즘입니다.

다단계 피드백 큐 스케줄링 방식의 프로세스 처리 과정

 

• 위 과정에서 우선순위가 낮은 CPU 집중 프로세스들에서 Starvation이 발생할 수 있기 때문에 Aging 기법을 적용하여 이런 문제점을 보완합니다.

 

 

💡 면접에서 나올 수 있는 질문

1. CPU 스케줄링 알고리즘의 종류와 특징을 설명하고, 장점과 단점에 대해서 설명해 보세요.
2. 비선점형 방식과 선점형 방식의 차이점을 설명해 보세요.

 

 

🔗 참고자료

면접을 위한 CS 전공지식 노트

강민철 강사님의 운영체제 강의