[시스템 소프트웨어]03-3 스케줄링 알고리즘 RR, MQ, MFQ

Priority Scheduling

(우선순위 스케줄링)

우선순위가 각 프로세스에 배정된다. 이전 포스트의 모든 스케줄링이 우선순위 스케줄링의 한 종류이다. 무엇을 우선순위로 줄 것인가에 따라 달라진다.

1. SJF는 우선순위가 프로세스의 수행시간(CPU Burst)인 경우이다. CPU burst가 클수록 우선순위는 작아지고 CPU burst가 작을수록 우선순위는 커진다.
2. SRTF는 우선순위가 잔여 CPU burst인 경우이다. 잔여 CPU burst가 클수록 우선순위는 작아지고 잔여 CPU burst 우선순위는 커진다.
3. 모든 프로세스의 우선순위를 동일하게 한 경우가 FCFS이다. 엄밀히 말하면 먼저 들어온 것이 우선순위가 큰 것이지만 모두에게 공평하게 주어지므로 우선순위가 동일하다고 말할 수 있다.

우선순위는 내부적 우선순위, 외부적 우선순위에 따라 결정할 수도 있다.

1. 내부적 우선순위는 시간제안, 메모리 요구, 열린 파일의 개수, 평균 I/O와 평균 CPU burst의 비율이 있다.
2. 외부적 우선순위는 O.S.의 외부적 요인이라고 할 수 있다. 프로세스의 중요도, 기부금의 유형과 액수, 스폰서의 프로세스, 기타 정책적인 요인이 있다.

우선순위 스케줄링의 문제점

1. Starvation(기아현상)
   레디큐에 현재 있는 프로세스보다 우선순위가 높은 것이 계속 들어와서 언제 실행될지 모르는 그때를 계속 기다리는 현상이다.
   해결책으로 aging 기법을 들 수 있는데, 오랫동안 시스템에 남아있는 프로세스에 대해 점진적으로 우선순위를 올려주는 기법이다.

2. Priority inversion (우선순위 반전 현상)
   높은 우선순위를 가지는 프로세스가 낮은 우선순위를 가지는 프로세스의 작업이 완료될 때까지 기다리는 현상이다.
   실시간 시스템인 경우 주어진 deadline을 맞추지 못하는 문제가 발생할 수 있다.
   client-server O.S에서 발생하기 쉽다.
   해결책으로 우선순위 상속 프로토콜을 사용하여 해결할 수 있다. 낮은 우선순위를 가진 프로세스에 우선순위를 한시적으로 증가시키는 것이다.

Round-Robin(RR)스케줄링

시분할 시스템을 위해 만들어진 알고리즘이다. 라운드로빈 스케줄링은 원형 큐를 필요로 한다. FCFS와 비슷하지만 프로세스간 스위치하는 데에 선점이 추가된 방식이다.
Preemptive FCFS이다.
어떤 프로세스도 한번에 1개 이상의 타임 슬라이스에 CPU가 할당되지 않는다는 특성이 있다. 평균 대기시간이 길수도 있다.

위 사진처럼 라운드 로빈에서는 time slice가 얼마인지 정해주고 그만큼 실행하고 다음 프로세스로 CPU를 넘겨준다.
프로세스들의 도착시간은 모두 같다.
P1의 실행시간이 24이지만 time slice가 4이므로 4만큼 실행되고 P2가 실행된다. P2는 실행시간이 3이므로 3만큼 실행되고 P3가 실행된다. time slice가 실행시간보다 작으면 time slice만큼 실행하지 못하므로 그냥 넘어간다. P3가 종료되면 P1이 계속 실행된다.
각각 대기시간은 P1: 6, P2: 4, P3: 7 이므로 따라서 평균 대기시간은 약 5.67이 된다.

라운드 로빈스케줄링은 time slice의 크기에 따라 수행능력이 크게 달라진다.
time slice의 크기가 너무 크면 FCFS와 같다. 너무 작으면 프로세스가 각각 자신만의 CPU가 있는 것처럼 나타난다.
Context switch를 할 때는 time slice가 context swtich time보다 커야한다. time slice의 크기가 작아질수록 context swtich하는 횟수가 커지므로 오버헤드가 커져서 성능이 저하가 된다. time slice크기가 적당해야 한다.

turnaround time(작업이 수행되는 시간) 또한 time slice의 크기에 따라 달라진다.

MQ

Multilevel Queue Scheduling
MQ알고리즘은 프로세스가 쉽게 다른 그룹으로 분류되는 환경을 위한 것이다.
MQ partition은 여러개의 분할된 레디큐로 되어 있다. 각 큐에서 그들만의 스케줄링을 사용한다.

위 사진의 5개의 프로세스 집단에 각각 큐를 할당하여 각 큐에서 스케줄링을 한다. 단점으로 큐를 스케줄링하는 것이 필요하다는 것이 있다.
장점으로는 그룹화를 하여 CPU bound와 I/O bound가 섞여서 효율이 안 좋은 것을 막을 수 있다.

이 MQ의 단점을 해결하는 것이 MFQ이다.

MFQ

Mulrilevel Feedback Queue Scheduling
MQ알고리즘은 스케줄링 오버헤드가 낮다는 장점이 있지만 융통성이 없다. 어떤 큐는 비어서 놀고 있고, 어떤 큐는 꽉차서 바빠도 운용상 어쩔 수 없다는 단점을 가진다.
그래서 MFQ는 큐 사이에 프로세스들이 이동할 수 있도록 한다.

만약 CPU를 많이 쓴다면 낮은 우선순위의 큐로 옮겨진다. 높은 우선순위의 큐를 떠난다는 뜻이다.
낮은 우선순위의 큐에서 너무 오래 기다리는 프로세스는 높은 우선순위의 큐로 옮겨져서 기아현상을 해결할 수 있다.

MFQ를 위해 결정해야 할 것들이 있다.
1. 큐의 개수
2. 각 큐에 사용할 스케줄링 알고리즘
3. 높은 우선순위의 큐로 프로세스를 옮길 때 결정하는데 사용되는 방법
4. 낮은 우선순위의 큐로 프로세스를 옮길 때 결정하는데 사용되는 방법
5. 프로세스가 실행을 필요로 할때 어떤 큐로 그 프로세스가 들어갈지 결정하는데 사용되는 방법