[OS] Job Scheduling Algorythm *유지보수중

선점 스케쥴링(Preemptive Scheduling)

 

1. 최소 잔여시간 우선 스케쥴링(SRTF, Shortest Remaining Time First Scheduling)

선점형SJF, 선점 최소 작업 우선 스케쥴링 이라고도 한다.

2. 선점 우선순위 스케쥴링

새로 도착한 프로세스의 우선순위가, 현재 실행되는 프로세스의 우선순위보다 높으면 프로세서를 선점

3. 순환 할당 (Round Robin) 스케쥴링

시분할 시스템을 위한 스케쥴링.

규정 시간량(Time Quantum) 또는 시간 할당량(Time Slice)이라고 하는 작은 단위의 시간을 정의.

일반적으로 10x10밀리 초에서 100x10밀리초 범위로 한다.

프로세스는 프로세서에 Time Slice만큼 할당되고 시간이 지나면 다시 준비 큐의 맨 뒤에 덧붙여진다.

4. 다단계 큐 (Multi-Level Queue) 스케쥴링

각 작업들을 서로 다른 묶음으로 분류할 수 있을 때 사용.

예를 들어 전면작업(대화형, Foreground Task)과 후면작업(일괄처리형, Background Task)으로 분류한다면 두 유형의 요구 반응 시간이 다르므로 서로 다르게 스케줄링해야 한다. 보통 전면작업이 후면작업에 비해 높은 우선순위를 갖는다.

5. 다단계 피드백 큐(Multi-Level Feedback Queue) 스케쥴링

작업이 시스템에 들어가면 한 큐에서만 고정되어 실행된다. 즉, 작업은 다른 큐로 옮겨지지 않는다.

 

비선점 스케쥴링(Nonpreemptive Scheduling)

1. 선입 선처리 (FCFS, First-come First-served) 스케쥴링

가장 간단. 프로세서를 요구하는 순서로 프로세서를 할당

선입선출(FIFO) 큐로 구현.

일괄 처리 시스템에 매우 효율적, 대화식 시스템에서는 적합하지 않다.

2. 최소 작업 우선(SJF, Short Job First) 스케쥴링

버스트 시간(처리하는데 걸리는 시간)이 가장 짧은 작업에 프로세서를 할당하는 기법.

동일한 프로세서 버스트를 가진다면 선입 선처리 스케쥴링을 적용.

3. 비선점 우선순위 스케쥴링

단순히 준비 큐의 머리 부분에 새로운 프로세스를 넣는다.

4. HRN (Highst Response-Rate Next)스케쥴링

최소 작업 우선(SJF)기법의 약점인 긴 작업과 짧은 작업 간의 지나친 불평등을 어느 정도 보완한 기법.

각 작업의 우선순위는 작업이 서비스를 받을 시간뿐만 아니라 서비스를 기다린 시간 등, 두 가지의 함수로 나타냄.

한 작업이 프로세서를 차지하면 종료될 때까지 실행된다.

 

서비스를 받을 시간(실행시간)이 짧고, 대기한 시간이 길수록 우선순위가 높아진다.

따라서 '시스템의 응답시간 : 대기한 시간 + 서비스를 받을 시간(실행시간)'  이 된다.

분자를 1늘리면서 분모도 1을 늘리는 것보단,

분자를 1줄이면서 분모도 1을 줄이는 것이 절대값이 높으므로(우선순위가 높아지므로)

(5/4 = 1.25, 6/5 = 1.2, 4/3 = 1.3)

대기한 시간이 긴 것 보다는 실행 시간이 짧은 것이 보통 먼저 처리되는 편이다

프로세스	도착시간	실행시간	대기한 시간	우선순위
P1	0	3	0	1등
P2	2	6	1	2등
P3	4	4	1차 : 9-4 = 5	1차 : (5+4)/4 = 2.25 3등
P4	6	5	1차 : 9-6 = 3 2차 : 13-6 = 7	1차 : (3+5)/5 = 1.6 2차 : (7+5)/5 = 2.4 5등
P5	8	2	1차 : 9-8 = 1 2차 : 13-8 = 5	1차 : (1+2)/2 = 1.5 2차 : (5+2)/2 = 3.5 4등

여기서 P2의 도착 시간은 2인데, 이 때 P1은 이미 실행시간이 3-2=1 이 된다.

따라서 시간 3에서 P1이 끝나면 큐에 P2밖에 없으므로 자동적으로 처리되므로 P2까지는 우선순위를 따질 필요가 없다.

문제는 P3~P5이다. P2는 시간 9까지 처리되는데 그 안에 P3~P5가 도착하므로 3개의 우선 순위는 구해야한다.

공식을 사용하여 구하면 P3 의 우선순위가 가장 높으므로 P3이 실행된다. P3의 실행시간은 4이므로 시간 13까지 기다려야 한다.

P3이 끝났다면 이제 P4와 P5의 우선순위를 구해야 한다. P3이 끝난 시간 13을 기준으로 계산한다.(P4,P5의 2차 참조)

우선순위의 수치값이 P5가 더 높으므로 먼저 실행된다

따라서 P1 -> P2 -> P3 -> P5 -> P4의 순서로 실행이 된다.

 - 기타 스케쥴링

1. 다중 처리기(Multi Processor) 스케쥴링

2. 스레드(Thread) 스케쥴링

 - 갱(Gang) 스케쥴링

 - 전용 프로세서 할당

 - 동적 스케쥴링

3. A-Steal 스케쥴링 (A-Steal Job Scheduling Algorithm)

멀티 프로세서 환경에서 사용하는 스케쥴링.

각 프로세서마다 자신이 먼저 처리해야할 작업들이 들어있는 Deque가 존재한다.

A 프로세서가 자신에게 할당된 작업을 처리하기 위해서 Deque의 선두에서 요소를 얻어온다.

만약 다른 B 프로세서가 자신에게 할당된 작업들을 담아놓은 Deque에 있는 작업들을 모두 처리했다면,

A 프로세서의 Deque에서 작업을 가져온다. 이를 '훔친다'고 표현하여 A-Steal 작업 스케쥴링이라고 한다.

이때, B프로세서는 A프로세서의 Deque에서 꼬리쪽에서 작업을 가져오므로 Queue가 아닌 Deque를 사용한다.