Khoa Công Nghệ Thông Tin & Truyền Thông
Đại học Cần Thơ
Giảng viên: Hà Duy An

9/19/2013

1

Chương 4: Định thời CPU


1.
2.
3.
4.

Các khái niệm
Các giải thuật định thời
Định thời trong hệ thống có nhiều bộ xử lý
Đánh giá giải thuật

9/19/2013

2

Chương 4: Định thời CPU



• Kỹ thuật đa chương giúp việc sử dụng
CPU đạt hiệu quả cao nhất.

• Quyết định định thời xảy ra khi một tiến trình:
1.
2.
3.
4.

Chuyển từ trạng thái đang chạy sang trạng thái chờ đợi
Chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng
Chuyển từ trạng thái chờ đợi sang sẵn sàng
Kết thúc

• Định thời không trưng dụng (nonpreemptive): tiến trình sẽ giữ
CPU và chỉ giải phóng CPU khi nó cần (trường hợp 1 và 4)
• Định thời trưng dụng (preempty): các trường hợp 2 và 3; Vấn đề:
o Tiến trình đang cập nhật dữ liệu chia sẽ chung?
o Tiến trình đang xử lý trong chế độ nhân (kernel mode)?
o Không thể bỏ qua tất cả các ngắt?

9/19/2013

6

Chương 4: Định thời CPU


• Bộ điều phối (Dispatcher): Có nhiệm vụ trao quyền điều
khiển CPU cho tiến trình được chọn bởi bộ định thời CPU,
công việc này bao gồm:
o Chuyển ngữ cảnh
o Chuyển sang chế độ người dùng


Chương 4: Định thời CPU


• Việc đánh giá giải thuật định thời được kiểm tra thông qua khả
năng tối ưu hóa các tiêu chí đinh thời của nó:
o
o
o
o
o

9/19/2013

Hiệu suất sử dụng CPU tối đa
Thông lượng tối đa
Thời gian xoay vòng tối thiểu
Thời gian chờ đợi tối thiểu
Thời gian đáp ứng tối thiểu

9

Chương 4: Định thời CPU



1.
2.
3.
4.


0

24

P3
27

30

• Thời gian chờ đợi: P1 = 0; P2 = 24; P3 = 27
• Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17
9/19/2013

12

Chương 4: Định thời CPU


• Giả sử các tiến trình xuất hiện theo thứ tự P2, P3, P1. Biểu đồ
Gantt cho lịch biểu là:
P2
0

•
•
•
•
•


CPU ngắn hơn thời gian thực thi còn lại của tiến trình đang chạy,
thì ưu tiên giao CPU cho tiến trình mới đến. Cách thức này được
gọi là Shortest-Remaining-Time-First (SRTF).

• SJF là tối ưu – nó tạo ra thời gian chờ đợi trung bình ngắn
nhất.

9/19/2013

14

Chương 4: Định thời CPU


Tiến trình
TG đến
P1
0.0
P2
2.0
4.0
P3
P4
5.0
• SJF (không trưng dụng)
P1
0

3


P4
• SJF (trưng dụng)
P1
0

P2
2

TG đến
0.0
2.0
4.0
5.0

P3
4

TG sử dụng CPU
7
4
1
4

P2
5

P1

P4
11



9/19/2013

18

Chương 4: Định thời CPU


• α =0
o τn+1 = τn
o Không tính đến thời gian sử dụng CPU gần nhất

• α =1
o τn+1 = tn
o Chỉ tính đến thời gian sử dụng CPU thực gần nhất

• α =1/2, lịch sử quá khứ và gần đây có trọng số tương đương.
• Nếu mở rộng công thức, ta có:
τn+1 = α tn+(1 - α) α tn-1 + … +(1 - α )j+1 α tn-j + … +(1 - α )n+1τ0

• Vì α và (1- α) nhỏ hơn hay bằng 1, mỗi số hạng tiếp theo có
trọng số nhỏ hơn số hạng trước đó.
9/19/2013

19

Chương 4: Định thời CPU



Priority
3
1
4
5
2

• Priority scheduling Gantt Chart

0

P1

P5

P2
1

6

P3
16

P4
18

19

• Average waiting time = 8.2 msec
9/19/2013


23

Chương 4: Định thời CPU


80% of CPU bursts should
be shorter than q

9/19/2013

24

Chương 4: Định thời CPU


Process TG sử dụng CPU
P1
53
17
P2
P3
68
P4
24
• Biểu đồ Gantt:
P1
0

P2

25

Chương 4: Định thời CPU