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

Trang chủ » Các Thuật Toán Lập Lịch Cho Cpu » Tính Toán Thời Gian Chờ Của Các Giải Thuật Lập Lịch CPU

Có thể bạn quan tâm

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

Share this:

  • Twitter
  • Facebook
Like Loading...

Related

Post navigation

← Lập Trình Cơ Sở Dữ Liệu Java Swing Cơ Bản – Ôn Tập 6 Giải Thích Một Số Hình Vẽ Trong Sách William Stallings, “Operating Systems”, 7th edition, 2012 – Ôn Tập 2 →

Leave a comment Cancel reply

Δ

Search

Search for:

Chủ Đề

  • Arduino (2)
  • Hệ Điều Hành (4)
  • Java (6)
  • Javascript (2)
  • Lập Trình Cấu Trúc (2)
  • OpenCV (1)
  • PHP (8)
  • PROLOG (5)
  • Uncategorized (1)

Lưu Trữ

  • August 2019 (1)
  • September 2017 (2)
  • July 2017 (1)
  • June 2017 (8)
  • May 2017 (12)
  • April 2017 (7)

Số lượt xem trang

  • 58,564 Views
Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use. To find out more, including how to control cookies, see here: Cookie Policy
  • Comment
  • Reblog
  • Subscribe Subscribed
    • Võ Xuân Phong
      • Sign me up
    • Already have a WordPress.com account? Log in now.
    • Võ Xuân Phong
    • Customize
    • Subscribe Subscribed
    • Sign up
    • Log in
    • Copy shortlink
    • Report this content
    • View post in Reader
    • Manage subscriptions
    • Collapse this bar
Loading Comments... Write a Comment... Email (Required) Name (Required) Website %d Design a site like this with WordPress.comGet started

Từ khóa » Các Thuật Toán Lập Lịch Cho Cpu