선점적 스케줄링 방식

지난 시간 알아본 비선점적 스케줄링 방식과는 달리, 선점적 스케줄링 방식은 CPU 자원을 사용 중인 프로세스에 인터럽트를 걸고, 다른 프로세스를 실행 시킬 수 있다. 그럼 어떤 프로세스를 올리고, 어떤 경우에 프로세스에 인터럽트를 걸지 알아보도록 하자

1. 라운드 로빈 스케줄링

라운드 로빈은 가슴이 붉은 새인 로빈에게서 유래되었다. 로빈은 새에게 먹이를 줄 떄 순서대로 준다. 즉, 자식이 5마리면 먹이를 작게 잘라 순서대로 주고, 순서가 끝난다면 다시 처음부터 먹이를 또 순서대로 준다.

이러한 로빈의 먹이주는 방식에 근거하여, 라운드 로빈 스케줄링은 한 프로세스가 할당받은 시간(time slice, time quantum) 동안 작업을 하다가 작업을 완료하지 못하면 ready queue의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. 프로세스들이 작업을 완료할 때까지 계속 순환을하면서 실행된다. 선점형(preemptive) 방식 중에 가장 단순하다.

즉, 들어온 순서대로 하는 것을 생각해보면 FCFS와 유사하다. 차이점은 FCFS는 비선점형이고, 라운드 로빈은 선점형 방식이라는 것이다. 즉, 라운드 로빈은 각 프로세스마다 CPU를 사용할 수 있는 최대 시간, 타임 슬라이스가 있다는 것이다. 프로세스는 자신에게 주어진 타임 슬라이드 동안만 작업을 할 수 있으며 작업이 다 끝나지 않으면 ready queue의 맨 뒤로 다시 삽입된다.

다음과 같이 ready queue에서 하나씩 프로세스들에게 CPU 자원을 할당하고 프로세스들은 주어진 타임 슬라이스만큼 실행된다. 만약 더 이상 실행될 것들이 없다면, 즉 실행 시간 <= 타임 슬라이스이면 완료되고, 실행할 시간이 남아있다면 타임 아웃되어 ready queue 맨 뒤에 다시 들어가서 자신을 순서가 오기를 기다린다. 순서대로 진행되기 때문에 PCB1, PCB2, PCB3, PCB4, PCB5 까지 실행되고, 모두 실행시간이 남아서 ready queue에 다시 들어간다면 또 PCB1, PCB2, PCB3 , PCB4, PCB5 순서로 실행된다.

FCFS와 마찬가지로 공평하게 반드시 실행된다는 장점이 있다. 그러나 convey 효과가 있는 FCFS와는 달리 제한 시간인 타임 슬라이스가 있고, 선점적 방식이기 때문에 convey 효과가 없어 더욱 효율적이다.

1.1 라운드 로빈 스케줄링의 성능

타임 슬라이스가 10ms일 때 다음의 예제를 통해 알아보자

p1이 들어오고 10ms동안 진행된다. 그리고 10ms가 끝나게되면 p1은 인터럽트에 걸리게 되어 ready qeueu 맨 뒤로 가고 p2에게 CPU 자원이 할당된다. p2는 10ms 동안 실행되어 20ms에 CPU자원을 반환하고 ready queue에 들어간다. p3가 CPU 자원을 이어받지만 P3는 작업 시간이 9ms이기 때문에 타임 슬라이스보다 시간이 적다. 때문에 p3는 10ms인 타임슬라이스 동안 실행이 완료되고 종료된다. p1은 20ms, p2는 8ms가 남은 시점에서 p1의 차례가 되어 10ms동안 실행된다. 이후 p2가 실행되고 10ms보다 적게 실행되기 때문에 8ms만 실행된다. 때문에 39~47ms 까지만 시간을 사용하고 p1에게 차례를 넘긴다. p1은 10ms만큼 남았으므로 타임 슬라이스 10ms가 끝나면 종료된다. 이후에 ready queue에는 아무것도 없게 된다.

• 프로세스1( P1 )의 대기 시간

1. 들어오자마자 시작 하므로 맨 처음에는 0이고 10ms에 끝난다. 남은 시간은 20ms이다.
2. 이전 10ms에 끝나게 되고, 29ms에 다시 실행되므로 29-10 = 19ms 이고 남은 시간은 10ms이다.
3. 이전 39ms에 끝나고, 47ms에 다시 실행되므로 47 - 39 = 8ms이고 남은 시간은 0ms가 된다.
4. p1의 대기 시간은 0 + 19 + 8 + = 27ms이다.

• 프로세스2( P2 )의 대기 시간

1. 3ms에 들어오고 10ms에 실행되므로 10 - 3 = 7ms가 된다. 남은 실행시간은 8ms가 된다.
2. 이전 20ms에 끝나고, 39ms에 실행되므로 39- 20 = 19ms가 된다. 남은 실행시간은 0ms이다.
3. p2의 대기 시간은 7 + 19 = 26ms가 된다.

• 프로세스3( P3 )의 대기 시간

1. 6ms에 들어오고 20ms에 실행된다. 따라서 20-6 = 14ms가 된다. 남은 실행시간은 0이다.
2. p3의 대시 시간은 14ms 이다.

• 평균 대기 시간
  (27ms + 27ms + 14ms ) = 67ms 이고 3으로 나누면 22.33ms가 된다.

라운드 로빈 스케줄링 같은 선점형 방식에서는 프로세스가 CPU를 일정 시간 동안 사용한 후 다른 프로세스에게 주어야 하기 때문에 앞의 긴 작업을 무작정 기다리는 convey 효과가 줄어들게 된다.

1.2 라운드 로빈 스케줄링의 단점

같은 예제에 대해서 이전에 FCFS는 23ms이고 라운드 로빈은 22.33ms가 되었다. 라운드 로빈이 평균 대기 시간이 미세하게 앞서지만 더 효율적이라고는 단언하기 힘들다. FCFS의 convey 효과를 해결하기위해 작업 시간 순서를 달리하면 평균 대기 시간이 줄어들게 된다. 이렇게 되면 라운드 로빈보다 더 효율적이라고 볼 수 있다.

또한, 가장 큰 문제점은 **선점적 방식을 위한 context switching이 발생한다는 것이다. context switching은 굉장히 오버헤드가 큰 작업이다. 프로세스의 정보를 PCB에 기록하고, 다음 프로세스를 실행시키고 정보를 기록하고 등등 복합적으로 피곤한 작업이다. 그럼 context switching을 적게 발생시키면 되지않을까?? 그러기 위해서는 타임 슬라이스```를 크게하면된다.

• 타임 슬라이스가 큰 경우
  타임 슬라이스가 커지면 context switching이 적게 발생할 것이다. 그러나 이는 FCFS와 다를 바 없어질 수도 있다. 또한, 반응 속도가 매우 느려져 프로그램을 다루는데 힘들게 된다.

• 타임 슬라이스가 작은 경우
  타임 슬라이스가 작으면 반응 속도가 빨라지고 평균 대기 시간이 개선된다. 그러나 너무 작으면 context switching이 발생하는 시간이 너무 자주 일어나서 context switching을 고려한 시간이 실제 작업 시간보다 많을수도 있게 된다.

이에 따라 유닉스에서는 타임 슬라이스를 대략 100ms로 정한다. 물론 고정된 것은 아니면 10~200ms 사이에서 조정할 수 있도록 한다고 한다.

2.1 SRT 우선 스케줄링 방식

+2023/06/07일로 수정하였습니다. 덧글을 확인해주세요.

SRT(Shortest Remaining Time) 최소 잔류 시간 우선 스케줄링으로, SJF(shortest job first)의 preemptive 버전이라고 할 수 있다.

SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만 CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다. 라운드 로빈 스케줄링이 큐에 있는 순서대로 CPU를 할당한다면 SRT 스케줄링은 남은 작업 시간 순서 중 가장 적은 프로세스를 선택한다.

ready queue에 있는 프로세스 중 잔류 시간(남아있는 실행 시간)이 가장 짧은 프로세스를 선정하여 실행시킨다. 만약 모두 동일하다면 라운드 로빈으로 순서대로 돌아가면서 실행된다. 참고로, SRT는 time slice를 따로 두지 않기 때문에 한 번 실행되면, 자신보다 작업시간이 짧은 process가 있지 않는 한 계속해서 실행된다.

다음의 예시를 보자.

프로세스 P1이 가장 먼저 도착하며, 작업 시간은 30ms이다. 프로세스 P1보다 짧은 작업시간은 맨 처음에는 없기 때문에 P1이 실행된다. 3ms 후 P2가 들어오는데, 18초ms 작업 시간을 갖는다. 따라서, 3ms시간을 작업한 프로세스 P1은 27ms가 남았으므로, P2 프로세스가 선점되어 실행된다. 즉, P1은 CPU에서 나가고 P2가 실행되는 것이다. 6ms에 P3 프로세스가 들어오며, P3 프로세스는 9ms의 작업 시간을 가진다. p2는 3ms정도 실행되었기 때문에 15ms의 작업시간이 남아 프로세스 P3가 더 짧은 작업 시간을 갖는다. 프로세스 P3가 실행되는데, 프로세스 P3보다 짧은 작업 시간의 프로세스가 없어 계속 실행된다. 이후, 작업 시간이 27ms인 프로세스 P1보다 짧은 작업 시간인 15ms가 남은 프로세스 P2가 실행되고, 15ms간 실행된다. 이후 P2가 끝난 후, P1이 남은 작업 시간 27ms를 실행하게 된다.

• p1의 대기 시간

1. p1은 0ms에 들어오고 바로 실행된다. 이 때는 대기 시간이 0ms가 된다.
2. 이후 남은 잔류 시간이 27ms으로, 시간 축으로 30ms에 시작되어 27ms의 대기시간을 갖는다.

• p2의 대기 시간

1. 시간 축에서 6ms부터 대기하기 시작하여 15ms에 시작되므로 9ms의 대기시간을 갖는다.

• p3의 대기 시간

1. 들어오고 바로 시작되어 0ms의 대기시간을 갖는다

• 평균 대기 시간
  (0 + 27 + 9) / 3 = 12ms가 된다.

2.1.2 SRT 스케줄링의 평가

SJF 스케줄링과 SRT 스케줄링의 평균 대기 시간을 비교해보면 SRT 스케줄링의 평균 대기 시간이 짧다. 하지만 SRT 스케줄링은 좋은 알고리즘이 아니다. 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 context switching을 해야 하므로 SFT 스케줄링에는 없는 작업이 추가된다. 또한 SRT 스케줄링은 SJF 스케줄링과 마찬가지로 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 starvation 현상이 일어나기 때문에 잘 사용하지 않는다. 즉, 실제로는 실현할 수 없는 불가능한 알고리즘이라는 것이다.

또한, 구현한다해도 fairness문제가 있어, 작업 시간이 긴 특정 프로세스는 짧은 작업 시간을 가진 프로세스에 밀려서 영영 실행이 안될 수도 있다.

2.2 Advanced SRT 우선 스케줄링 방식

SRT의 문제로 fairness문제가 있다고 했다. 즉, 작업 시간이 긴 프로세스는 실행되지 않는 starvation 문제가 발생할 수 있다. 이는 SRT 알고리즘이 time slice없이 동작하기 때문이다. 그렇다면 time slice를 주어 특정 프로세스만 계속해서 동작하지 않도록 해주면, fairness를 어느정도 개선할 수 있다.

2.2.1 SRT 스케줄링의 성능

위의 예제와 동일한 예제로 Advanced SRT 평균 대기 시간을 측정해보자

타임 슬라이스가 10ms인 시스템에서 Advanced SRT가 어떻게 작동하는 지 보도록 하자

p1프로세스가 먼저오게되고 타임 슬라이스 10초 동안 실행되게된다. 남은 작업 시간을 계산하면 다음과 같다. p1 = 20ms, p2 = 18ms, p3 = 9ms가 되었다. 남은 잔류 시간 중에 가장 적은 프로세스는 p3가 된다. p3가 타임 슬라이스 10ms를 받게되고 19ms까지 실행되고 p3는 종료된다. 남은 작업 시간을 계산하면 다음과 같다. p1 = 20ms, p2 = 18ms이다. p2 가 더 적은 작업 시간이므로 p2를 실행시킬 수 있다. p2가 10ms만큼 실행되고 8ms가 남는다. 따라서 p1 = 20ms, p2 = 8ms이므로 p2가 연속적으로 실행된다. 이후 p2는 8ms만큼 실행되고, p1이 남아있어 연속적으로 실행된다.

• p1의 대기 시간

1. p1은 0ms에 들어오고 바로 실행된다. 이 때는 대기 시간이 0ms가 된다.
2. 이후 남은 잔류 시간이 20ms이므로 p2, p3보다 많아서 맨 나중에 실행된다. 37ms에 실행되어 37 - 10 = 27ms가 된다.

• p2의 대기 시간

1. 3ms에 들어오고 19ms에 실행된다. 19 - 3 = 16ms가 된다.

• p3의 대기 시간

1. 6ms에 들어오고 남은 시간이 9ms이므로 10 - 6 = 4ms가 된다.

• 평균 대기 시간
  (27 + 16 + 4) / 3 = 15.66ms 가 된다.

기존 SRT 알고리즘보다 더 긴 대기 시간을 갖지만, time slice만큼은 실행되는 것을 보장하기 때문에 계속해서 최소의 작업 시간이 변경된다는 장점이 있다. 이는 각 프로세스의 동작에 fairness를 어느정도 개선했다고 볼 수 있다.

3. 우선순위 스케줄링

프로세스는 중요도에 따라 우선순위(priority)를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다. 우선순위 스케줄링은 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다. 예를 들어 FCFS 스케줄링에서, 우선순위를 작업 시간이 짧은 프로세스에게 높게 설정했다고 가정해보자

다음과 같이 실행 시간이 적은 순서로 우선순위를 높게 정했다. 참고로 우선순위 값이 낮을수록 높은 것이다.

시작 시점에는 프로세스 P1뿐이므로 P1은 대기하지 않고 바로 실행된다. P1이 작업을 마치면 P2와 P3이 기다리고 있다. 두 프로세스 중 P3의 우선순위가 P2보다 높기 때문에 P3이 먼저 실행되고, P3이 작업을 마치면 이어서 P2가 실행된다. 이 경우 총 대기 시간과 평균 대기 시간은 SJF 스케줄링과 같다.

참고로 우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있다

• 비선점형 방식

1. SJF 스케줄링 : 작업 시간이 짧은 프로세스에 높은 우선순위를 부여한다.
2. HRN 스케줄링 : 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여한다.

• 선점형 방식

1. SRT 스케줄링 : 남은 시간이 짧은 프로세스에 높은 우선순위를 부여한다.

따라서, 우선순위 스케줄링은 선점형 혹은 비선점형 방식으로 구현이 가능하다.

1. 고정 우선순위 알고리즘 : 한 번 우선순위를 부여받으면 종요될 때까지 우선순위가 고정된다. 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다.
2. 변동 우선순위 알고리즘 : 일정 시간마다 우선순위가 변한다. 일정 시간마다 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템의 상황을 반형하여 효율적인 운영이 가능하다.

3.1 우선순위 스케줄링의 평가

우선순위 스케줄링은 ready queue에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위해하고 starvation 현상을 일으킨다는 것이 문제이다. 또한 ready-queue에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성을 떨어뜨린다.

이러한 단점에도 불구하고 프로세스의 우선순위는 시스템의 효율성이 아니라 프로세스의 중요도를 기준으로 결정된다. 만약 커널 프로세스가 일반 프로세스와 같은 우선순위라고 가정해보자. 일반 프로세스가 실행된 다음 커널 프로세스가 실행되면 커널 프로세스가 제 역할을 못할 수 있다. 따라서 우선순위는 시스템의 효율성보다 프로세스의 중요도에 따라 정해지는 것이다.

4. 다단계 큐 스케줄링

다단계 큐(multilevel qeuue)스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다. 라운드 로빈 방식으로 운영되는 큐는 우선순위 따라 다단계로 나눠어 있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정된다. 우선순위는 고정형 우선순위를 사용하며 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

다단계 큐 스케줄링은 우선순위에 따라 다양한 스케줄링이 가능한 선점형(preemptive) 방식이다. 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있을뿐더러 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있다.

가령, 전면 프로세스는 반응 속도를 높이기 위해 타임 슬라이스를 작게 하고, 후면 프로세스는 사용자와의 상호작용이 없으므로 FCFS 방식으로 처리한다. 즉 프로세스의 우선순위와 작업 형태를 고려하여 스케줄링을 할 수 있다.

다단계 큐 스케줄링은 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다. 우선순위가 1번인 큐에 CPU 할당을 기다리는 프로세스가 있다면 우선순위가 2번인 큐의 프로세스는 1번 큐에 프로세스의 작업이 끝날 때까지 기다려야 한다. 즉 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는데 이러한 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링이다.

즉, 하나의 큐에서는 선점형 방식으로 프로세스들이 타임 슬라이스를 할당받아 작업이 진행되지만, 큐들 끼리는 비선점형 방식으로 상위 큐에서 프로세스들이 실행이 완료되기 전까지는 하위가 실행될 수 없다.

5. 다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완하는 방식이다. 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링과 기본적인 형태가 같아 우선순위를 가진 여러 개의 큐를 사용한다. 하지만 다단계 큐 스케줄링의 경우 각 단계의 큐에 라운드 로빈 방식을 사용하고 우선순위에는 변화가 없는 데 반해, 다단계 피드백 큐 스케줄링의 경우 CPU를 사용하고 난 뒤 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스는 원래 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.

결국 다단계 피드백 큐 스케줄링에서 마지막 큐에 있는(우선순위가 가장 낮은) 프로세스는 무한대의 타임 슬라이스를 얻는다. 때문에 가장 마지막 큐에 들어온 프로세스를 처리하는 방식은 FCFS가 된다.

다단계 피드백 큐 스케줄링은 오늘날의 운영체제가 CPU가 스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 예이다. 유닉스에서 타임 슬라이스를 고정하지 않고 10~200 ms 사이에서 조정할 수 있도록 한 이유는 바로 다단계 피드백 큐 스케줄링을 사용하기 때문이다.