03_Scheduling.md

CPU 스케줄링

선점형 스케줄링와 비선점형 스케줄링의 차이를 말해보세요.

• 선점형 스케줄링은 CPU에 할당된 프로세스가 작업이 완전히 끝나지 않아도 강제적으로 기존 프로세스를 새로운 프로세스로 교체해버리는 스케줄링 방법입니다.
• 비선점형 스케줄링은 반대로 CPU에 할당된 프로세스의 작업이 완전히 끝난 이후에 CPU에 할당되는 프로세스를 교체하는 스케줄링 방법입니다.

FCFS 스케줄링 알고리즘이 뭔지 알아요?

• FCFS 알고리즘은 준비 큐에 먼저 도착한 프로세스를 CPU에 할당하는 프로세스로 선택하는 스케줄링 알고리즘입니다.

이 알고리즘을 많이 쓸까요?

• 아닙니다. FCFS 알고리즘은 항상 먼저 도착한 프로세스를 선택하기 때문에 만약 가장 늦게 도착한 프로세스가 얼마 걸리지 않는 작업을 수행하는 프로세스일 경우에 문제가 생깁니다. 해당 프로세스가 실제로 작업에 필요한 시간은 짧지만 실행을 위해 준비 큐에서 오랫동안 기다려야 하는 큰 취약점을 가지고 있습니다.

그럼 Shortest Job First 알고리즘은 어떨까요?

• SJF 알고리즘은 수행시간이 가장 짧은 프로세스를 우선적으로 처리하여 준비 큐의 프로세스들의 대기시간을 최소화하는 알고리즘입니다. 따라서 운영체제의 스케줄링에 가장 적합한 알고리즘이라고 할 수 있습니다.

그럼 이 알고리즘을 많이 쓸까요?

• 아닙니다. 실제로 어떤 프로세스의 수행시간을 실행하지 않고 알아낼 수 있는 방법이 없기 때문에 구현이 불가능한 알고리즘입니다. 하지만 다음 프로세스의 수행시간이 이전 수행시간과 비슷할 것이라는 가정을 하여 수학적 예측을 통해 구현할 수는 있습니다.

그럼 실제로는 어떤 알고리즘을 주로 사용할까요?

• Round Robin 이나 Priority 스케줄링을 함께 사용합니다. 라운드 로빈 스케줄링은 time quantum 이라고 부르는 타임스탬프를 사용해서 스케줄링을 합니다.
• 운영체제는 준비 큐에 있는 프로세스들을 정확히 time quantum 시간만큼만 CPU에 할당시키고 시간이 끝나면 곧바로 다음 프로세스와 교체시킵니다. 이렇게 스케줄링을 하면 다수의 프로세스를 여러번에 나눠서 실행할 수 있기 때문에 반응속도가 중요한 시스템에서 유용하게 사용될 수 있습니다.
• Priority 스케줄링은 준비 큐에 있는 프로세스들을 우선순위에 따라 CPU에 할당하는 알고리즘입니다. 새로운 프로세스가 준비 큐에 도착했을 때, 우선순위가 높다면 도착시간과는 관계없이 먼저 선택됩니다.

라운드 로빈 알고리즘의 단점은 없을까요?

• 라운드 로빈 알고리즘은 time quantum 에 의존적입니다. 만약 time quantum 이 준비 큐에 있는 각 프로세스의 수행시간보다 길다면, FCFS과 동일한 스케줄링이 됩니다. 반대로 time quantum 이 너무 짧다면, 프로세스의 컨텍스트 스위칭이 지나치게 많이 발생할 수 있습니다.

그럼 Priority 스케줄링의 단점은요?

• 우선순위에 따라 스케줄링을 하게되면 우선순위가 상대적으로 낮은 프로세스가 실행되지 못하고 장시간동안 준비 큐에 남아있을 수 있습니다. 이런 현상을 Starvation 혹은 Indefinite Blocking 이라고 합니다.

이 문제는 어떻게 해결할 수 있을까요?

• 두 가지 방법이 있습니다. 첫번째는 Aging 기법을 사용하여 준비 큐에 오래 머무는 프로세스의 우선순위를 점진적으로 높여주는 방식입니다. 다른 방법은 라운드 로빈 알고리즘을 섞어서 사용하는 것입니다. 라운드 로빈은 공정하게 모든 프로세스에게 CPU를 점유하게 합니다. 우선순위에 따라 프로세스들이 정렬되고 이 프로세스들에 대해 라운드 로빈 알고리즘을 사용한다면 큐의 뒤에 위치한 프로세스도 CPU 점유의 기회를 받을 수 있게 됩니다.

멀티 레벨 큐에 대해서 들어봤어요?

• 멀티 레벨 큐는 준비 큐를 여러개의 큐로 구성하고 새로운 프로세스가 들어올 때마다 중요도에 따라 각각 다른 큐에 넣어 관리하는 알고리즘입니다. 각 큐는 서로 다른 스케줄링 알고리즘을 사용합니다. 하지만 각 프로세스가 한 큐에서 다른 큐로 이동할 수 없어 유연하지 못한 스케줄링 알고리즘입니다.

그럼 멀티 레벨 피드백 큐는 뭐예요?

• 멀티 레벨 피드백 큐는 여러 큐로 나눈 준비 큐의 상위 계층에 time quantum 을 두어 CPU 사용시간에 따라 프로세스의 위치를 바꿔주고 스케줄링 알고리즘을 단계별로 다르게 적용하는 알고리즘 입니다.

실시간 스케줄링에는 어떤 방법이 있어요?

• 먼저, Rate Monotonic 스케줄링이 있습니다. 이 알고리즘은 프로세스의 우선순위에 따라 CPU에 프로세스를 스케줄링합니다. 이때, 우선순위는 각 프로세스가 가지는 CPU 요청 주기에 따라 주기가 짧은 프로세스가 높은 우선순위를 가지게됩니다.
• 다음은 Earlist Deadline First 스케줄링입니다. 이 알고리즘은 각 프로세스의 마감시간을 기준으로 우선순위를 부여합니다. 마감시간이 빠르면 높은 우선순이가 부여됩니다. 각 프로세스들은 자신이 실행가능한 상태가 되면 시스템의 자신의 마감시간을 알리고 이 마감시간으로 우선순위를 부여하게됩니다. 이 알고리즘은 이론적으로는 완벽하지만 프로세스가 교체되면서 발생하는 컨텍스트 스위칭의 오버헤드 때문에 딜레이가 생겨 실제로는 구현이 불가능합니다.