'피포'에 해당되는 글 1건

  1. 2009.10.22 Scheduling by 초상큼발랄

* 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
Posted by 초상큼발랄
l