CPU 스케줄링 알고리즘

CPU 스케줄링이란?

CPU 스케줄링은 운영체제의 주요 기능 중 하나로, 시스템에서 여러 프로세스를 효울적으로 관리하고 실행하기 위해 CPU 시간을 할당하는 방법을 결정하는 과정입니다. 하나의 CPU 코어는 한 번에 하나의 작업만 실행할 수 있기 때문에 스케줄링 알고리즘이 필요합니다.

 

작동 원리

1. 프로세스 생성 : 새로운 프로세스가 생성되면 준비 큐에 추가됩니다.
2. 큐 관리 : 준비 큐는 프로세스들이 대기하는 곳으로, 각 프로세스는 CPU를 기다립니다.
3. 스케줄링 결정 : 스케줄러는 특정 알고리즘에 따라 준비 큐에서 다음 실행할 프로세스를 선택합니다.
4. 문맥 교환 : 선택된 프로세스가 CPU에서 실행되고 있는 프로세스와 교체되며, 이 과정은 문맥 교환이라 불립니다.
5. 프로세스 실행 : 선택된 프로세스는 CPU에서 실행되며, 시간이 다하거나(선점형 스케줄링) 작업이 완료되면 다시 준비 큐로 돌아가거나 종료됩니다.

 

선점형? 비선점형?

두 가지 유형은 CPU할당 방식과 실행 중인 프로세스의 중단 여부에 따라 다릅니다.

 

선점형

• 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺐을 수 있는 방식
• CPU처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능합니다.
• 잦은 문맥 교환으로 오버헤드가 커질 수 있습니다.

비선점형

• 프로세스가 CPU를 점유하고 있다면 이를 뺐을 수 없는 방식
• 필요한 문맥 교환만 일어나므로 오버헤드가 상대적으로 적지만 프로세스 배치에 따라 효율성 차이가 많이 납니다.

특성	선점형 스케줄링	비 선점형 스케줄링
문맥 교환	빈번하게 발생할 수 있음	드물게 발생
응답 시간	짧음	길어질 수 있음
우선순위 처리	높은 우선순위 즉시 처리 가능	우선순위 고려 어려움
시스템 복잡성	높음	낮음
오버헤드	높음	낮음

 

 

CPU 스케줄링 평가 기준

 

평가 기준	정의	목표	계산 방법
CPU 이용률	CPU가 작업을 수행하는 시간의 비율	CPU가 가능한 한 많이 사용되도록 하여 자원을 낭비하지 않는 것
처리율	단위 시간당 완료된 프로세스의 수	주어진 시간 동안 최대한 많은 프로세스를 완료하는 것
반환 시간	프로세스가 시스템에 도착해서부터 완료될 때까지 걸리는 총 시간	각 프로세스의 턴어라운드 시간을 최소화하는 것	반환시간 = 종료 시간 - 도착 시간
대기 시간	프로세스가 준비 큐에서 기다린 총 시간	각 프로세스의 대기 시간을 최소화하는 것	대기 시간 = 반환 시간- 실행 시간
응답 시간	프로세스가 처음 요청을 제출한 후 처음 응답이 반환될 때까지의 시간	대화형 시스템에서 응답 시간을 최소화하는 것	응답 시간 = 첫 실행 시작 시간 - 도착 시간

 

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

 

 

오버헤드 : 스케줄링을 관리하고 문맥 교환을 수행하는데 드는 추가적인 비용
기아 현상 : 특정 프로세스가 무한정 대기하는 현상

 

 

CPU 스케줄링 알고리즘

 

 

◽선입 선처리(First Come First Served, FCFS)

가장 먼저 도착한 작업을 처리합니다.

동작 과정

1. 준비 큐에 도착한 순서대로 작업이 대기
2. CPU가 유휴 상태가 되면 준비 큐의 맨 앞 작업을 선택하여 실행
3. 실행이 끝난 작업은 시스템에서 제거되고, 다음 작업이 실행

문제점

• 호위 효과(Convoy Effect) : 긴 작업이 앞에 도착하면 뒤에 도착한 짧은 작업들이 오랫동안 기다려야 하는 현상. 시스템 전체의 효율을 떨어뜨릴 수 있습니다.
• 비선점형 : 새로운 작업이 도착해도 현재 작업이 끝날 때까지 대기해야 합니다.

 

 

◽최단 작업시간 우선(Shortest Job First, SJF)

실행 시간이 가장 짧은 작업부터 처리합니다.

동작 과정

1. 준비 큐에서 가장 짧은 실행 시간을 가진 작업을 선택
2. CPU가 유휴 상태가 되면 가장 짧은 작업을 선택하여 실행
3. 실행이 끝난 작업은 시스템에서 제거, 다음 짧은 작업이 실행

문제점

• 기아 현상 (Stavation) : 긴 작업이 계속해서 짧은 작업들에 밀려 무한정 대기할 수 있습니다.
• 비선점형

 

◽최고응답률 우선(Highest Response-ratio Next, HRN)

응답 비율이 가장 높은 작업을 선택합니다.

 

동작 과정

1. 준비 큐에서 각 작업의 응답 비율을 계산
2. 응답 비율이 가장 높은 작업을 선택하여 실행
3. 실행이 끝난 작업은 시스템에서 제거, 다시 응답 비율을 계산

응답 비율 계산

• 응답 비율 = (대기 시간 + 실행 시간) / 실행 시간

문제점

• 복잡한 계산 : 각 작업의 응답 비율을 계산하는 과정이 복잡할 수 있습니다.

 

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

각 작업이 일정한 시간 할당량을 받으며 순차적으로 처리됩니다.

 

동작 과정

1. 준비 큐에 도착한 순서대로 작업을 대기
2. CPU는 각 작업에 일정한 시간 할당량을 부여하고, 그 시간 동안만 작업을 실행
3. 실행 시간이 남은 작업은 준비 큐의 뒤로 이동하여 다시 대기

문제점

• 문맥 교환 오버헤드 : 짧은 시간 할당량은 문맥 교환 오버헤드를 증가시킬 수 있습니다.
• 시간 할당량 설정 : 시간 할당량이 너무 크면 선입선처리(FCFS)와 유사해지고, 너무 작으면 오버헤드가 증가합니다.

 

◽최소 잔여 시간 우선(Sortest Remaining Time, SRT)

남은 실행 시간이 가장 짧은 작업을 우선 처리합니다.

 

동작 과정

1. 준비 큐에 있는 작업 중 남은 실행 시간이 가장 짧은 작업을 선택
2. 새로운 작업이 도착하면 남은 실행 시간을 재평가
3. 남은 실행 시간이 가장 짧은 작업이 실행

문제점

• 기아 현상
• 선점형 : 새로운 작업이 도착하면 현재 작업을 중단하고 새 작업을 평가합니다.
• 문맥 교환 오버헤드 : 작은 문맥 교환으로 인해 오버헤드가 발생할 수 있습니다.

 

◽다단계 큐(Multi-level Queue, MQ)

여러 개의 큐를 사용하여 작업을 우선순위에 따라 분류하고, 각 큐는 다른 스케줄링 알고리즘을 사용합니다.

 

동작 과정

1. 작업은 우선순위에 따라 적절한 큐에 배치
2. 높은 우선순위 큐의 작업이 먼저 처리
3. 각 큐는 자신의 스케줄링 알고리즘을 사용하여 작업을 관리

문제점

• 기아현상
• 복잡성 : 큐 간의 우선순위 및 스케줄링 알고리즘을 설정하는 것이 복잡할 수 있습니다.

 

◽다단계 피드백 큐(Multi-level Feedback Queue, MFQ)

다단계 큐의 변형으로 작업이 다른 큐로 이동할 수 있습니다. 우선순위가 높은 큐에서 시작하여 시간이 지나면 우선순위가 낮아집니다.

 

동작과정

1. 작업이 높은 우선순위 큐에서 시작
2. 일정 시간 동안 실행 후, 작업이 완료되지 않으면 낮은 우선순위 큐로 이동
3. 낮은 우선순위 큐로 이동할수록 긴 시간 할당량을 받음

 

문제점

• 설정 복잡성 : 각 큐의 시간 할당량과 이동 규칙을 설정하는 것이 복잡할 수 있습니다.

 

알고리즘	동작 과정	문제점
선입 선처리  (FCFS)	준비 큐에 도착한 순서대로 작업이 대기. CPU가 유휴 상태가 되면 준비 큐의 맨 앞 작업을 선택하여 실행.	호위 효과(Convoy Effect)
최단 작업 우선 (SJF)	준비 큐에서 가장 짧은 실행 시간을 가진 작업을 선택. CPU가 유휴 상태가 되면 가장 짧은 작업을 실행.	기아 현상(Starvation)
최고응답률 우선 (HRN)	준비 큐에서 각 작업의 응답 비율을 계산. 응답 비율이 가장 높은 작업을 선택하여 실행.	복잡한 계산: 각 작업의 응답 비율을 계산하는 과정이 복잡
라운드로빈 (RR)	준비 큐에 도착한 순서대로 작업이 대기. CPU는 각 작업에 일정한 시간 할당량을 부여하고 순차적으로 처리.	문맥 교환 오버헤드: 짧은 시간 할당량은 문맥 교환 오버헤드를 증가시킬 수 있음
최소 잔여 시간 우선 (SRT)	준비 큐에서 남은 실행 시간이 가장 짧은 작업을 선택. 새로운 작업이 도착하면 남은 실행 시간을 재평가.	기아 현상
다단계 큐 (MQ)	여러 큐를 사용하여 작업을 우선순위에 따라 분류. 높은 우선순위 큐의 작업이 먼저 처리됨.	기아 현상
다단계 피드백 큐 (MFQ)	작업이 높은 우선순위 큐에서 시작. 일정 시간 동안 실행 후 완료되지 않으면 낮은 우선순위 큐로 이동.	설정 복잡성: 각 큐의 시간 할당량과 이동 규칙을 설정하는 것이 복잡.

색상  : 비선점형 스케줄링

색상 : 선점형 스케줄링

 

출처 : 
code-lap1
eunajung01
한빛미디어-유투부