* First-Come-First-Served(FCFS)
- 비선점형(Non-preemptive)
- 가장 단순한 형태의 스케줄링 정책이며, FIFO(First-Input-First-Output)라고도 불린다.
- 짧은 프로세스보다는 긴 프로세스에 유리하다.
* Round-Robin(RR)
- 선점형(Preemptive)
- 시간 할당량(Time Slicing 또는 Time Quantum) 기법
- 모든 프로세스는 한 번에 정해진 시간 조각만큼만 실행 한 후 강제적으로 CPU를 빼앗는다.
* Shortest Process Next(SPN)
- 비선점형(Non-preemptive)
- 가장 짧은 프로세스를 먼저 수행
- 구현 불가능(각 프로세스가 요구하는 총 실행시간을 미리 알아야 함)
* Shortest Remaining Time(SRT)
- 선점형(Preemptive)
- 예상되는 남아 있는 실행시간이 가장 짧은 프로세스가 선택
* Highest Response Ratio Next(HRRN)
- 비선점형(Non-preemptive)
- 반환 시간(TAT) : 프로세스가 시스템에 진입한 후 대기한 시간과 실행한 시간을 모두 합쳐 결국 시스템 내에서 머문 총 시간을 의미한다.
실제 서비스 시간 대비 반환시간의 비율을 나타낸다.
- R(응답 비율) = ( time spent waiting(처리기를 기다리며 대기한 시간) + expected service time(예상되는 서비스 시간) ) / expected service time(예상되는 서비스 시간)
- 대기시간이 길어지면 R값이 커지기 때문에 스케줄러에게 보상 받는다.
- 계산시간이 복잡하고 증가면 이 알고지름의 시간 복잡성이 증가하여 오버헤드가 발생할 가능성이 크기 때문에 고려해야한다.
* 스케줄링 정책들의 비교 분석 *
|
프로세스 |
A |
B |
C |
D |
E |
|
도착시간 |
0 |
2 |
4 |
6 |
8 |
|
서비스시간(Ts) |
3 |
6 |
4 |
5 |
2 |
<FCFS>
|
평균 | ||||||
|
종료시간 |
3 |
9 |
13 |
18 |
20 |
|
|
반환시간(Tr) |
3(3-0) |
7(9-2) |
9(13-4) |
12(18-6) |
12(20-8) |
8.60 |
|
Tr/Ts |
1.00 |
1.17 |
2.25 |
2.40 |
6.00 |
2.56 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
A |
||||||||||||||||||||
|
B |
||||||||||||||||||||
|
C |
||||||||||||||||||||
|
D |
||||||||||||||||||||
|
E |
<RR q=1>
|
평균 | ||||||
|
종료시간 |
4 |
18 |
17 |
20 |
15 |
|
|
반환시간(Tr) |
4(0-4) |
16(18-2) |
13(17-4) |
20(20-6) |
7(15-8) |
10.80 |
|
Tr/Ts |
1.33 |
2.67 |
3.25 |
2.80 |
3.50 |
2.71 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
A |
||||||||||||||||||||
|
B |
||||||||||||||||||||
|
C |
||||||||||||||||||||
|
D |
||||||||||||||||||||
|
E |
<RR q=4>
|
평균 | ||||||
|
종료시간 |
3 |
13 |
11 |
20 |
19 |
|
|
반환시간(Tr) |
3(3-0) |
11(13-2) |
7(11-4) |
14(20-6) |
11(19-8) |
10.00 |
|
Tr/Ts |
1.00 |
2.5 |
1.75 |
2.80 |
5.50 |
2.71 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
A |
||||||||||||||||||||
|
B |
||||||||||||||||||||
|
C |
||||||||||||||||||||
|
D |
||||||||||||||||||||
|
E |
<SPN>
|
평균 | ||||||
|
종료시간 |
3 |
9 |
15 |
20 |
11 |
|
|
반환시간(Tr) |
3(0-3) |
7(9-2) |
11(15-4) |
14(20-6) |
3(11-8) |
7.60 |
|
Tr/Ts |
1.00 |
1.17 |
2.75 |
2.80 |
1.50 |
1.84 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
A |
||||||||||||||||||||
|
B |
||||||||||||||||||||
|
C |
||||||||||||||||||||
|
D |
||||||||||||||||||||
|
E |
<SRT>
|
평균 | ||||||
|
종료시간 |
3 |
15 |
8 |
20 |
10 |
|
|
반환시간(Tr) |
3(0-3) |
13(15-2) |
4(8-4) |
14(20-6) |
2(10-8) |
7.20 |
|
Tr/Ts |
1.00 |
2.17 |
1.00 |
2.80 |
1.00 |
1.59 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
A |
||||||||||||||||||||
|
B |
||||||||||||||||||||
|
C |
||||||||||||||||||||
|
D |
||||||||||||||||||||
|
E |
<HRRN>
|
평균 | ||||||
|
종료시간 |
||||||
|
반환시간(Tr) |
||||||
|
Tr/Ts |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
A |
||||||||||||||||||||
|
B |
||||||||||||||||||||
|
C |
||||||||||||||||||||
|
D |
||||||||||||||||||||
|
E |
<Feedback>
|
평균 | ||||||
|
종료시간 |
||||||
|
반환시간(Tr) |
||||||
|
Tr/Ts |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
A |
||||||||||||||||||||
|
B |
||||||||||||||||||||
|
C |
||||||||||||||||||||
|
D |
||||||||||||||||||||
|
E |
'Education > Operating System' 카테고리의 다른 글
| 명령어 수행 (2) | 2009.10.22 |
|---|---|
| Interrupt (2) | 2009.10.22 |
| Scheduling(1) (1) | 2009.10.22 |
| Trace of Process (2) | 2009.10.12 |
| HAL(Hardware Abstraction Layer) (0) | 2009.10.07 |
