[운영체제] - 스케줄러

스케줄링 종류

스케줄러는 크게 non-preemtive 스케줄러와** preemtive 스케줄러** 두가지로 나뉜다. 이번 게시글에서는** non-preemtive 스케줄러**와** preemtive 스케줄러** 각각의 종류와 장단점을 비교하고 더 나아가 multi-level-feedback-queue 에 대해서 알아본다

평가 지표

스케줄러의 성능을 비교하려면 적절한 평가지표가 사용되어야한다. 평가지표중 하나로는 turnaround time 이 존재한다

turnaround time = 작업이 완료된 시간 - 작업이 도착한 시간

Non-preemtive 스케줄러

Non-preemtive 스케줄러는 프로세스가 자발적으로만 프로세스의 상태를 변경하는 스케줄러를 말한다.

First-in-Fisrt-Out 스케줄러

먼저 들어온 작업을 먼저 실행한다, 먼저 들어온 작업의 실행시간이 길어지면 convoy-effect 가 발생할 수 있다

Shortest job first

남은시간이 가장 작은 프로세스부터 시작한다. FIFO 와 마찬가지로 convoy-effect 가 발생할 수 있다.

Preemtive 스케줄러

Preemtive 스케줄러는 우선순위에 따라서 운영체제가 프로세스의 실행 권한을 강제로 뺏어올수 있는 스케줄러를 말한다.

Shortest Remaining Time Next (SRTN)

스케줄러가 남은 실행시간이 짧은 프로세스를 선택하고 새로운 작업과 해당 작업시간을 비교한다. 이때 새로운 작업의 남은 시간이 더 적으면 현재 프로세스의 상태를 저장하고 새로운 프로세스를 실행한다.

Round Robin (RR)

정해진 시간 내에 프로세스가 작업을 완료하지못하면 다음 프로세스로 실행한다. RR은 모든 프로세스에게 동일한 실행시간을 부여한다

Prioirity Scheduling

우선순위가 높은 프로세스 부터 시작한다.

Multi Level Feedback Queue

MLFQ 는 기본적으로 기존의 스케줄링 알고리즘을 활용하여 프로세스의 평균 반환시간을 최대한 단축시켜서 사용자에게 빠른 응답을 제공해주기 위해 고안된 개념임.

기본 규칙

• 여러개의 큐로 구성되며 각각 다른 우선순위(priority level) 가 배정된다
• 실행 준비가 된 프로세스는 이중 하나의 큐에 존재한다.
• 높은 우선순위 큐에 존재하는 작업이 선택된다.
• 큐에는 둘 이상의 작업이 존재할 수 있고, RR 스케줄링 알고리즘이 사용된다. (우선순위가 동일할 경우)

우선순위의 변경

• 프로세스에는 짧은 실행 시간을 갖는 CPU를 자주 양보하는 대화형 작업과, 긴 실행시간을 가지지만 응답시간은 중요하지 않은 작업들이 서로 섞여있음

한개의 긴 시간을 가진 작업

1. 최고 우선순위로 진입 (Q2)
2. 10ms 타임 슬라이스가 지나면 우선순위 감소 (Q1)
3. 10ms 동안 Q1에서 실행후 끝나면 Q0로 이동

 

짧은 작업과 함께

1. 스케줄러는 처음에 해당 작업이 짧은 시간인지 긴 작업인지 알 수 없기 때문에 우선 짧다고 가정한다음에 가장 윗 우선순위 큐에 작업을 넣음
2. 만약 짧은 작업이면 우선순위가 내려가기 전에 종료 될것임

입출력 작업에 대해서

• 대화형 작업이 키보드나 마우스로 부터 입출력을 자주 수행하면 타임슬라이스가 종료되기 전에 CPU를 다른 프로세스에게 양도하게 될 것임 이런 경우에는 우선순위를 그대로 유지함

 

현재 문제점

• 시스템에 너무 많은 대화형 작업이 존재하면 실행시간이 긴 작업에 대해서는 기아현상이 발생할 수 있음
• 이를 해결할수 있는 알고리즘을 적용해야함

해결방법 1: 우선순위의 상향조정

• 일정 시간 S 가 지나면 작업의 우선순위를 전부 상위로 올림
• 너무 길면 긴 작업에 대해서 Starvation 이 발생할 수 있고 너무 짧으면 대화형 시스템이 적절한 양의 CPU 를 사용할 수 없게 됨

MLFQ 조정과 다른 쟁점들

• 몇개의 큐가 존재해야하는가, 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가, 얼마나 자주 우선순위가 상향 조정되어야 하는가
• 결국 워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 함
• 대부분의 MLFQ는 큐별로 다른 타임 슬라이스 시간을 셋 할 수 있는데 보통 낮은 우선순위는 긴 CPU 작업을 포함하므로 긴 슬라이스, 높은 우선순위는 대화형 작업이 많으므로 짧은 슬라이스 값을 세팅함

요약

지정된 작업의 우선순위를 정하기 위하여 피드백을 사용함, 과거에 보여준 행동이 우선순위 지정의 지침이 됨

규칙 1: 우선순위(A) > 우선순위(B) 일경우 A 가 실행, B는 실행되지 않음

규칙 2: 우선순위(A) = 우선순위(B) 일 경우 A 와 B는 RR 방식으로 실행됨

규칙 3: 작업이 시스템에 들어가면 최상단 큐에 배치됨

규칙 4: 작업이 지정된 단계에서 배정받은 시간을 소진하면, 작업의 우선순위는 감소함

규칙 5: 일정 주기 S 가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킴