CPU 스케쥴링 (CPU Scheduling)

CPU 스케쥴링 (CPU Scheduling)

Ready Queue 혹은 메인 메모리 안에 여러 개의 프로세스가 기다리고 있을 때, 지금 실행 중인 프로세스가 끝나면 어떤 프로세스에게 다음 서비스를 받게 할 것인지 결정하는 작업

선점 (Preemptive) vs 비선점 (Non-Preemptive)

선점 (Preemptive) 방식

어떤 프로세스가 현재 실행중임에도 강제로 쫓아내고 새로운 프로세스를 실행시키는 스케쥴링 방식

비선점 (Non-Preemptive) 방식

현재 실행 중인 프로세스가 끝나거나 새로운 인터럽트가 발생하기 전에는 새로운 프로세스를 실행시킬 수 없는 스케쥴링 방식

Scheduling Criteria

스케쥴링 척도 (Scheduling Criteria)

스케쥴링의 효율적인 정도를 측정하는 척도

• CPU Utilization (CPU 이용률) : CPU가 수행되는 비율 (%)
• Throughput (처리율) : CPU가 시간 당 처리하는 정도 (개수)
• Turnaround Time (반환시간) : 하나의 작업이 시작부터 끝날 때 까지의 소요 시간
• Waiting Time (대기시간) : 어떤 작업이 Ready Queue에서 기다리는 시간
• Response Time (응답시간) : 대화형 시스템에서 어떤 입력에 대해 반응하는데 걸리는 시간

CPU 스케쥴링 알고리즘 (CPU Scheduling Algorithms)

First-Come, First-Served (FCFS)

먼저 도착한 프로세스가 먼저 CPU를 점유하는 방식

매우 단순하고 공평하며 많이 사용되지만 항상 효율적이지는 않다.

Convoy Effect

FCFS는 비선점 (non-Preemptive) 방식이다.

시간이 가장 오래 걸리는 작업이 제일 먼저 실행된다면 다른 작업들은 시간이 훨씬 짧을지라도 꼼짝없이 기다려야 한다.

Shortest-Job-First (SJF)

가장 짧은 프로세스가 제일 먼저 실행되는 방식이다.

그 어떤 방식보다도 평균 대기시간이 제일 짧은 방식이다.

하지만 SJF 방식은 매우 비현실적이다. 왜냐하면 현실적으로 각 프로세스가 CPU를 얼마나 사용하는지를 알 수 없기 때문이다. 따라서 각 프로세스의 점유 시간을 예측해야 하는데, 이는 상당한 Overhead를 발생시킨다.

즉, 문맥 전환이 일어날 때마다 모든 프로세스의 점유 시간을 예측해야 하므로 Overhead가 매우 크게 발생한다.

SJF는 선점과 비선점 방식 모두 가능하다.

SJF는 남아있는 시간 중 제일 짧은 프로세스를 선택한다.
현재 진행 중인 프로세스보다 더 짧은 프로세스가 있다면 갈아끼울 수 있고, (선점)
현재 진행 중인 프로세스가 제일 빨리 끝난다면 갈아끼우지 않는다. (비선점)

Priority Scheduling

우선순위 (Priority)가 제일 높은 프로세스를 제일 먼저 실행하는 알고리즘이다.
일반적으로 우선순위는 정수로 나타내며, 숫자가 낮을수록 우선순위가 높음을 의미한다.

우선순위는 크게 내부 요인, 외부 요인으로 나눠서 결정할 수 있다.

• 내부요인 : Time Limit, Memory Requirement, I/O to CPU burst 등등
• 외부요인 : Amount of funds being paid, Political factors 등등

Priority Scheduling은 Starvation (기아) 현상이 발생할 수 있다.

• Starvation : 너무 낮은 우선순위 덕분에 다른 프로세스들에게 계속 밀려 오랫동안 실행되지 못하는 프로세스

Starvation 현상은 aging을 통해 해결할 수 있는데, aging이란 너무 오래 기다리는 프로세스는 그 우선순위를 조금씩 올려주는 방식이다. 따라서 오래 기다릴수록 우선순위가 조금씩 높아져서 언젠가는 수행될 수 있게 된다.

Round-Robin

Round-Robin이란 마치 원 모양으로 모든 프로세스가 돌아가며 수행되는 방식이며 주로 시분할 시스템에서 많이 사용된다.

전체 시간을 일정하게 나눈 후, 각 시간마다 서로 다른 프로세스를 할당하는 방식이다. 즉, 일정 시간 동안 하나의 프로세스가 수행되고, 그 다음 똑같은 시간 동안 또 다른 프로세스 수행되는 방식이다. 이렇게 모든 프로세스가 한번씩 수행되고 마지막 프로세스가 끝나면 다시 처음 프로세스부터 다시 시작된다.

다시 처음 프로세스부터 다시 시작하는 이유는 프로세스를 일정 시간 만큼만 수행하는 것이지, 이 프로세스가 끝날 때 까지 계속 수행하는 것이 아니기 때문이다. 프로세스가 끝나는지 여부와 상관 없이 일정 시간이 지나면 무조건 다음 프로세스로 넘어가게 된다.

이때 여러 개로 나뉘어진 일정 시간을 시간 양자 (Time Slice 혹은 Time Quantum)라고 한다.

Round-Robin은 일정 시간이 지나야지만 다음 프로세스가 수행되므로 선점 방식이다.

Time Quantum

Round Robin 방식은 Time quantum의 크기에 따라 그 작동 방식이 크게 달라진다. 만약 각각의 Time Quantum이 무한대라면 FCFS 방식과 동일하게 동작한다. 또한 Time Quantum이 0이라면 Switching이 매우 빈번하게 발생하기 때문에 마치 모든 프로세스가 동시에 실행되는 것 처럼 동작한다.

Multilevel Queue Scheduling

프로세스는 사실 여러 가지의 종류가 있다.

• System Processes : 운영체제 커널 수준의 프로세스
• Interactive Processes : 유저 수준의 대화형 프로세스
• Interactive Editing Processes : 대화형 프로세스
• Batch processes : 대화형 프로세스와 반대되는 일괄 처리형 프로세스 (컴파일러 등)
• Student Processes : 학생용 프로세스

서로 다른 종류의 프로세스를 하나의 Ready Queue (Single Ready Queue)에 몰아넣는 것은 비효율적이라는 판단에서 등장한 것이 바로 Multilevel Queue Scheduling 즉, 프로세스의 각 종류에 맞춰서 여러개의 Queue (Several Seperate Queues)를 두는 방식이다.

각각의 Queue에 우선 순위를 부여하여 Queue의 실행 순서를 정할 수 있다. 그림에서의 Highest Priority ~ Lowest Priority가 바로 Queue 우선 순위이다.
또는 CPU 시간을 각 Queue에 차등배분 할 수도 있고, 각 Queue마다 서로 다른 Scheduling 정책을 반영할 수도 있다.

Multilevel Feedback Queue Scheduling

Multilevel Queue Scheduling과 같이 여러 개의 Queue를 사용한다는 점은 맞지만, 하나의 Queue가 어느 정도 실행되었는데도 끝나지 않는다면 다른 Queue로 이동한다는 차이가 있다.

그림에서 보듯이 모든 프로세스는 하나의 입구로 진입한다. 하나의 Queue가 CPU를 너무 오랫동안 점유한다면 Time Out이 발생하고 다른 Queue로 이동한다. 만약 Starvation (기아) 상태가 발생한다면 우선 순위가 낮은 Queue 안에 있는 Process를 우선 순위가 높은 Queue로 옮길 수 있다.