Tính Toán Thời Gian Chờ Của Các Giải Thuật Lập Lịch CPU – Ôn Tập 1

I. Giải Thuật First Come First Serve (FCFS)

Ví dụ: Xét 4 tiến trình P1, P2, P3,P4 đến tại thời điểm 0, với thời gian xử lý được tính bằng mili giây.

P4→P3→P2→P1→CPU.

Bảng thời gian xử lý:

Quá trình

Thời gian xử lý

P1

24

P2

4

P3

4

P4

5

Bảng thời gian chờ:

Vì các tiến trình đến cùng thời điểm tại t0=0 nên

P1

P2 P3

P4

P1

24 24

24

P2

4

4

P3

4

P4

Thời gian chờ TB: (0 + 24 +28 +32 ) / 4 = 21 (ms).

Lược đồ Gantt :

P1

P2 P3

P4

0                                                 24                             28                      32                                 37

II. Giải Thuật Shortest Job First (SJF)

Ví dụ 1: Xét 4 tiến trình P1, P2, P3,P4 đến tại thời điểm 0, với thời gian xử lý được tính bằng mili giây.

P4→P3→P2→P1→CPU.

Bảng thời gian xử lý:

Quá trình

Thời gian xử lý

P1

24

P2

4

P3

4

P4

5

Do đây là giải thuật SJF nên ta sắp xếp lại thứ tự đến CPU dựa vào thời gian xử lý, thời gian xử lý ngắn nhất thì được thực hiện trước tiên.

P1→P4→P3→P2→CPU.

P2 P3 P4

P1

P2

4 4 4

P3

4

4

P4

5

P1

Thời gian chờ TB: (4 + 8 + 13) / 4 = 6 (ms).

Lược đồ Gantt :

P2 P3 P4

P1

0           4               8                       13

Ví dụ 2:

Tiến Trình

Thời Gian Đến

Thời Gian Xử Lý

P1

0

12

P2

1

5

P3

2

7

P4

3

3

Bảng thời gian chờ:

P1

P2 P3

P4

T0

(-11)

T1

1 (-4)

T2 1 (-3) 1

T3

1 (-2) 1 1

T5

2 (-0) 2 2
T6 1 1

(-2)

T8 2 2

(-0)

T9

1 (-6)

T15

6 (-0)
T16 (-10)

T26 (-0)

Thời gian chờ TB: (15 + 0+ 7 + 3) / 4 = 6.25 (ms)

Lược đồ Gantt:

P1 P2 P4 P3

P1

0                       1                             6                             9                                 16                       27

Ví dụ 3:

Tiến Trình

Thời Gian Đến

Thời Gian Xử Lý

P1

0 6

P2

1

3

P3 2

4

P4 2

2

Bảng thời gian chờ:

P1 P2 P3 P4

T0

(-5)

T1 1 (-2)

T2

1 (-1) 1 1

T3

1 (-0) 1

1

T4 1 1

(-1)

T5

1 1 (-0)
T6 1 (-3)

T9

3 (-0)
T10 (-4)

T14

(-0)

Thời gian chờ TB: (9 + 0+ 4 + 2) / 4 = 3.75 (ms).

P1

P2 P4 P3

P1

0                                1                     4                        6                              10                           15

III. Giải Thuật Priority (P)

Ví dụ: Xét 6 tiến trình P1, P2, P3,P4,P5,P6 mỗi tiến trình có mỗi độ ưu tiên khác nhau đến cùng tại thời điểm t0=0 với thời gian xử lý được tính bằng mili giây.

Quá Trình

Thời gian xử lý

Độ ưu tiên

P1

5 6

P2

10 1

P3

15 5
P4 6

4

P5 2

2

P6 4

3

Do đây là giải thuật P nên ta sắp xếp lại thứ tự đến CPU dựa vào độ ưu tiên, độ ưu tiên nhỏ thì được thực hiện trước tiên.

P1→P3→P4→P6→P5→P2→CPU

P2 P5 P6 P4 P3 P1

P2

10 10 10 10 10
P5 2 2 2

2

P6

4 4

4

P4 6

6

P3

15

P1

Thời gian chờ TB: (0 + 10 + 12 + 16 + 22 + 37)/6=16.16 (ms).

Lược đồ Gantt :

P2 P5 P6 P4 P3

P1

0                  10                      12                          16                   22                     37                   42

IV. Giải Thuật Round Robin (RR)

Ví dụ 1: Xét 4 tiến trình P1, P2, P3,P4 đến tại thời điểm 0, với thời gian xử lý được tính bằng mili giây sử dụng thuật toán Round Robin (xoay vòng) để tính thời gian chờ trung bình.

Quá Trình

Thời Gian Xử Lý

P1

5

P2

20

P3

11

P4

8

Giả sử định mức thời gian là 10 mili giây.

Bảng thời gian chờ :

Thời Gian

P1 P2 P3 P4

T0

(-4) 1 1

1

T4 (-0) 4 4

4

T5

(-19) 1 1

T15

(-10) 9 9
T16 1 (-10)

1

T25 9 (-1)

9

T26

1 1 (-7)

T32

7 7 (-0)
T33 (-9) 1

T42 (-0) 9

T43 (-0)

Lược đồ Gantt:Thời gian chờ TB: (0+23+33+25)/4=20.25 (ms).

P1 P2 P3 P4 P1

P3

0              5                         16                              26                           33                        43

Ví dụ 2:

Quá Trình

Thời Gian Đến Thời Gian Xử Lý

P1

0

24

P2 1

3

P3

2

3

Giả sử định mức thời gian là 4 mili giây.

P1

P2

P3

T0

(-23)

T1

(-22) 1
T2 (-21) 1

1

T3 (-20) 1

1

T4

1 (-2) 1

T6

2 (-0)

2

T7 1

(-2)

T9

2 (-0)

T10

(-19)

T29 (-0)

Thời gian chờ TB:  (6 + 3 + 5) / 3 = 4.66 (ms).

P1

P2 P3

P1

0                                  4                                           7                                 10                           30

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s