Chương IV: Đònh thời CPU
Khái niệm cơ bản
 Các bộ đònh thời
‟ long-term, mid-term, short-term
 Các tiêu chuẩn đònh thời CPU
 Các giải thuật đònh thời
‟ First-Come, First-Served (FCFS)
‟ Shortest Job First (SJF) và Shortest Remaining
Time First (SRTF)
‟ Priority Scheduling
‟ Round-Robin (RR)
‟ Highest Response Ratio Next (HRRN)
‟ Multilevel Queue
‟ Multilevel Feedback Queue


Khoa KTMT

1


Mục tiêu


Hiểu được:
– Tại sao phải định thời.
– Các tiêu chí định thời
– Một số giải thuật định thời

Khoa KTMT



Long-term
scheduling

suspended
ready

Long-term
scheduling
Medium-term
scheduling
ready

Short-term
scheduling

running

suspended
blocked

Khoa KTMT

Medium-term
scheduling
blocked

terminated

4



Short term scheduling
Xác đònh process nào trong ready queue sẽ được chiếm CPU
để thực thi kế tiếp (còn được gọi là đònh thời CPU, CPU
scheduling)
Short term scheduler còn được gọi với tên khác là dispatcher
Bộ đònh thời short-term được gọi mỗi khi có một trong các sự
kiện/interrupt sau xảy ra:
‟
t thời gian (clock interrupt)
‟ Ngắt ngoại vi (I/O interrupt)
‟ Lời gọi hệ thống (operating system call)
‟Chương
Signal này sẽ tập trung vào đònh thời

Khoa KTMT

ngắn hạn
6


Dispatcher




Dispatcher sẽ chuyển quyền điều khiển CPU về cho
process được chọn bởi bộ đònh thời ngắn hạn
Bao gồm:




System-oriented
‟ Sử dụng CPU (processor utilization): đònh thời sao cho CPU càng
bận càng tốt
cực đại
‟ Công bằng (fairness): tất cả process phải được đối xử như nhau
‟ Thông lượng (throughput): số process hoàn tất công việc trong
một đơn vò thời gian
cực đại.

Khoa KTMT

8


Hai yếu tố của giải thuật đònh thời


Hàm chọn lựa (selection function): dùng để chọn
process nào trong ready queue được thực thi (thường
dựa trên độ ưu tiên, yêu cầu về tài nguyên, đặc điểm
thực thi của process,…), ví dụ
„ w = tổng thời gian đợi trong hệ thống
„ e = thời gian đã được phục vụ
„ s = tổng thời gian thực thi của process (bao gồm cả “e”)

Khoa KTMT


Hàm định thời được thực hiện khi
( )
n từ ng i running sang waiting
( )
n từ ng i running sang ready
( )
n từ ng i waiting, new sang ready
( ) t
c
c thi
1 và 4 không cần lựa chọn loại định thời biểu, 2 và 3
cần
ng p ,
c i
nh
i nonpreemptive
ng p ,
c i
nh
i preemptive
c

Khoa KTMT

n cơ

o

hơn?


Service
Time

1

0

3

2

2

6

3

4

4

4

6

5

5

8

Hàm lựa chọn: Tiến trình nào yêu cầu CPU trước sẽ được cấp phát
CPU trước; Process sẽ thực thi đến khi kết thúc hoặc bò blocked do I/O
Chế độ quyết đònh: non-preemptive algorithm
Hiện thực : sử dụng hàng đợi FIFO (FIFO queues)
‟ Tiến trình đi vào được thêm vào cuối hàng đợi
‟ Tiến trình được lựa chọn để xử lý được lấy từ đầu của queues

5

0

10

15

20

P1
P2
P3
P4
P5

run

Khoa KTMT

add

13


Khoa KTMT

24

27

30

Giả sử thứ tự vào của
các tiến trình là
 P1, P2, P3
Thời gian chờ
 P1 = 0;
 P2 = 24;
 P3 = 27;
Thời gian chờ trung
bình
 (0+24+27)/3 = 17
14


FCFS Scheduling


Ví dụ:



Process

hơn..

30

Liệu có xảy ra trường hợp trì hỗn vơ hạn định
(starvation hay indefinte blocking) với giải thuật FCFS?
Nhận xét
15
Khoa KTMT


2. Shortest-Job-First(SJF) Scheduling





Đònh thời biểu công việc ngắn nhất trước
Khi CPU được tự do, nó sẽ cấp phát cho tiến trình yêu cầu ít
thời gian nhất để kết thúc ( tiến trình ngắn nhất)
Liên quan đến chiều dài thời gian sử dụng CPU cho lần tiếp
theo của mỗi tiến trình. Sử dụng những chiều dài này để lập
lòch cho tiến trình với thời gian ngắn nhất.

Khoa KTMT

16


2. Shortest-Job-First(SJF) Scheduling

P3
4
1
P4
5
4
Gantt Chart for Schedule
P1
0

P3
7

P2
8

P4
12

16

Average waiting time = (0+6+3+7)/4 = 4
Khoa KTMT

18


Preemptive SJF Scheduling
(hay Sortest Remaining Time First - SRTF)



5

P4
7

P1
11

16

Average waiting time =
(9+1+0+2)/4 = 3
Khoa KTMT

Process Arrival TimeBurst Time
P1
0
8
P2
1
4
P3
2
9
P4
3
5

19








Tng ng vi mi process cn cú di ca CPU burst tip theo
Hm la chn: chn process cú di CPU burst nh nht
Chng minh c: SJF ti u trong vic gim thi gian i trung
bỡnh
Nhc im: Cn phi c lng thi gian cn CPU tip theo ca
process
Gii phỏp cho vn ny?

Khoa KTMT

21


Nhaọn xeựt ve giaỷi thuaọt SJF





(Thi gian s dng CPU chớnh l di ca CPU burst)
Trung bỡnh tt c cỏc CPU burst o c trong quỏ kh
Nhng thụng thng nhng CPU burst cng mi cng phn
ỏnh ỳng hnh vi ca process trong tng lai


Mỗi process sẽ được gán một độ ưu tiên
CPU sẽ được cấp cho process có độ ưu tiên cao nhất
Đònh thời sử dụng độ ưu tiên có thể:
‟ Preemptive hoặc
‟ Nonpreemptive

Khoa KTMT

24


Gán độ ưu tiên
SJF là một giải thuật đònh thời sử dụng độ
ưu tiên với độ ưu tiên là thời-gian-sử-dụngCPU-dự-đoán.
 Gán độ ưu tiên còn dựa vào:


‟ Yêu cầu về bộ nhớ
‟ Số lượng file được mở
‟ Tỉ lệ thời gian dùng cho I/O trên thời gian sử
dụng CPU
‟ Các yêu cầu bên ngoài ví dụ như: số tiền
người dùng trả khi thực thi công việc
Khoa KTMT

25