1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệ thông tin
Trường Đạihọc Công nghệ
2
Lậplịch CPU
3
Tạisaophảilậplịch CPU?
z Số lượng NSD, số lượng tiến trình luôn lớn
hơnsố lượng CPU củamáytínhrất nhiều
z Tạimộtthời điểm, chỉ có duy nhấtmộttiến
trình đượcthựchiệntrênmộtCPU
z Vấn đề:
z Nhu cầusử dụng nhiềuhơn tài nguyên (CPU)
đang có
z Do đócầnlậplịch để phân phốithờigiansử dụng
CPU cho các tiếntrìnhcủa NSD và hệ thống
4
Hàng chờ lậplịch tiếntrình
Hàng chờ sẵn
sàng thựchiện
Hàng chờ vào/ra
Yêu cầuvào/ra
Hếtthờigian
sử dụng CPU
Tạomộttiến
trình con
Chờ ngắt
CPU

nhiều)
8
Bộ lậplịch ra hoạt động khi…
1. Mộttiến trình chuyểntừ trạng thái running
sang waiting
2. Mộttiến trình chuyểntừ trạng thái running
sang ready
3. Mộttiến trình chuyểntừ trạng thái waiting
sang ready
4. Mộttiếntrìnhkếtthúc
9
Các phương pháp lậplịch
terminated
new
ready running
waiting
admitted
exit
I/O hoặcsự kiện
đãhoàntất
Bị ngắt
(Interrupt)
Chờ I/O hoặc
sự kiện
Lậplịch
2
1
3
4
z 1 và 4: Lậplịch non-preemptive

Thể hiệnqua tảiCPU –làmộtsố từ 0% đến
100%.
z Trong thựctế các hệ thống thường có tảitừ 40%
(tảithấp) đến 90% (tảicao)
z Thông lượng (throughput): Là số lượng các
tiến trình hoàn thành trong một đơnvị thời
gian
14
Các tiêu chí đánh giá lậplịch
z Thời gian hoàn thành (turnaround time):
z t
turnaround
= t
o
-t
i
với t
i
là thời điểmtiếntrìnhvàohệ
thống, t
o
là thời điểmtiếntrìnhrakhỏihệ thống
(kếtthúcthựchiện)
z Như vậy t
turnaround
là tổng: thờigiantảivàobộ nhớ,
thờigianthựchiện, thời gian vào ra, thờigian
nằm trong hàng chờ…
15
Các tiêu chí đánh giá lậplịch

là thời điểmnhậnyêu
cầu, t
s
là thời điểmbắt đầu đáp ứng yêu cầu
17
Đánh giá các thuậttoánlậplịch
XấuTốtThờigianđáp ứng (response
time)
XấuTốtThờigianchờ (waiting time)
-> Thờigianchờ trung bình
XấuTốtThờigianhoànthành
(turnaround time)
TốtXấuThông lượng (throughput)
TốtXấuKhả năng tậndụng CPU
(CPU utilization)
Giá trị caoGiá trị thấpTiêu chí
18
Các thuậttoánlậplịch
4
19
FCFS (First Come First Served)
z Tiến trình nào có yêu cầusử dụng CPU
trướcsẽđượcthựchiệntrước
z Ưu điểm: Thuậttoánđơngiảnnhất
z Nhược điểm: Hiệuquả củathuậttoánphụ
thuộcvàothứ tự củacáctiến trình trong hàng
chờ, vì thứ tự này ảnh hưởng rấtlớn đến thời
gian chờ trung bình (average waiting time)
20
Ví dụ FCFS 1a

3
0242733
21
Ví dụ FCFS 1b
z Xét ba tiếntrìnhtrongvídụ 1a vớithứ tự xếp
hàng P
3
, P
2
, P
1
z Biểu đồ Gantt:
z Thờigianchờ củacáctiếntrìnhlà: P
3
chờ
0ms, P
2
chờ 6ms, P
3
chờ 9ms
z Thờigianchờ trung bình: (0+6+9)/3=5ms
z Thờigianchờ trung bình thấphơnthờigian
chờ trung bình trong ví dụ 1a
P
1
P
2
P
3
069 33

Q
3
(10) Q
2
(10) Q
1
(10) P (40)
P (50) Q
1
(10) Q
2
(10) Q
3
(10)
24
Convoy effect: Thờigiansử
dụng CPU và thiếtbị vào ra
Thiếtbị
vào ra
CPU
0
40 50 60 70
P
Q
1
Q
2
Q
3
40

, Q
2
, Q
3
là 3 tiến trình “nhỏ”cóchukỳ sử dụng CPU trong
10ms và vào ra trong 10ms
z Thứ tự xếp hàng: P, Q
1
, Q
2
, Q
3
Rỗi
5
25
SJF (Shortest Job First)
z Với SJF, tham số lậplịch có thêm độ dài của
phiên sử dụng CPU tiếp theo t
nextburst
z Tiếntrìnhcót
nextburst
nhỏ nhấtsẽđượclập
lịch sử dụng CPU trước
z Nếu hai tiếntrìnhcót
nextburst
bằng nhau thì
FCFS đượcápdụng
26
SJF (Shortest Job First)
z Vớilậplịch dài hạn: Có thể biết t

z p
1
>p
2
có nghĩalàtiếntrìnhP
1
có độ ưutiênthấphơn P
2
z SJF là trường hợp đặcbiệtcủalậplịch có ưutiênvới
ưutiêncủacáctiếntrìnhlànghịch đảo độ dài phiên
sử dụng
28
Lậplịch có độ ưutiên
z Hai cách xác định độ ưu tiên:
z Độ ưutiêntrong: Được tính toán dựatrêncác
tham sốđịnh lượng củatiếntrìnhnhư giớihạnvề
thờigian, bộ nhớ, số file đang mở, thờigiansử
dụng CPU
z Độ ưutiênngoài: Dựavàocácyếutố như mức
độ quan trọng, chi phí thuê máy tính…
z Chờ không xác định: Mộttiếntrìnhcóđộ ưu
tiên thấpcóthể nằm trong hàng chờ trong
mộtkhoảng thờigiandàinếu trong hàng chờ
luôn có các tiếntrìnhcóđộ ưutiêncaohơn
29
Lậplịch có độ ưutiên
z Để tránh hiệntượng chờ không xác định, có
thêm tham số tuổi để xác định thờigiantiến
trình thờigiannằm trong hàng chờ
z Tham số tuổi đượcsử dụng để làm tăng độ

10
1
2
1
5
P
1
P
2
P
3
P
4
P
5
Độ ưu
tiên
Thờigian
thựchiện
(ms)
Tiến
trình
P
1
(3)P
5
(2)
06 16
P
2

quantum
nhỏ thì hiệuquả của RR giảmvìbộ
điềuphốiphảithựchiệnnhiềuthaotácchuyển
trạng thái, lãng phí thờigianCPU
z Nếu t
quantum
lớnthìsố thao tác chuyểntrạng thái
giảm đi
z Nếu t
quantum
rấtnhỏ (ví dụ 1ms) thì RR được
gọi là processor sharing
z Nếu t
quantum
= ∞ thì RR trở thành FCFS
33
Ví dụ RR
z Giả sử có 3 tiếntrìnhP
1
, P
2
, P
3
vớithờigianthực
hiệntương ứng là 24ms, 3ms, 6ms, thứ tự trong
hàng chờ P
1
, P
2
, P

: 0+(11-4)+(17-15)=9ms
z P
2
: 4ms
z P
3
: 7+(15-11)=11ms
z Thờigianchờ trung bình:
(9+4+11)/3=8ms
34
Lậplịch vớihàngchờđamức
z Thuậtngữ: Multilevel queue scheduling
z Đượcsử dụngkhitacóthể chia các tiến
trình thành nhiềulớp khác nhau để lậplịch
theo các tiêu chí khác nhau, ví dụ:
z Lớpcáctiến trình có tương tác (interactive hoặc
foreground process) cầncóđộ ưutiêncaohơn
z Lớpcáctiếntrìnhchạynền (background) thường
khôngcótương tác vớiNSD: Độ ưutiênthấphơn
35
Lậplịch vớihàngchờđamức
z Thuậttoánlậplịch với hàng chờđamứcchia
hàng chờ ready thành nhiềuhàngchờ con
khác nhau, mỗihàngchờ con đượcápdụng
mộtloạithuật toán khác nhau, ví dụ:
z Hàng chờ các tiến trình background: FCFS
z Hàng chờ các tiếntrìnhcótương tác:RR
z Các tiếntrìnhđượcphânlớpdựavàođặc
tính như bộ nhớ, độ ưu tiên, …
z Cầncóthuậttoánlậplịchchocáchàngchờ

z Tiến trình chiếmnhiềuthờigianCPU sẽ bị
chuyểnxuống hàng chờ có độ ưutiênthấp
z Tiếntrìnhnằm lâu trong hàng chờ sẽđược
chuyển lên hàng chờ có độ ưutiêncaohơn
39
Các tham số củabộ lậplịch
hàng chờđamứccóphảnhồi
z Số lượng các hàng chờ
z Thuậttoánlậplịch cho mỗihàngchờ
z Phương pháp tăng độ ưutiênchomộttiếntrình
z Phương pháp giảm độ ưutiênchomộttiếntrình
z Phương pháp xác định hàng đợinàođể đưa
mộttiếntrìnhvào
40
Các thuậttoánlậplịch khác
z Sinh viên tìm hiểu trong giáo trình:
z Lậplịch đaxử lý
z Lậplịch thờigianthực
41
Các phương pháp đánh
giá thuậttoánlậplịch
42
Mô hình xác định
z Thuậtngữ: Deterministic modeling
z Dựa vào các trường hợpcụ thể (chẳng hạn
các ví dụđã nói trong bài giảng này) để rút ra
các kếtluận đánh giá
z Ưu điểm: Nhanh và đơngiản
z Nhược điểm: Không rút ra đượckếtluận
đánh giá cho trường hợptổng quát

z Ưu điểm: Đánh giá đượchiệuquả thựcsự
khi sử dụng
z Nhược điểm:
z Chi phí cao
z Hành vi củangườisử dụng có thể thay đổi theo
môi trường hệ thống
46
Tóm tắt
z Khái niệmlậplịch, các tiêu chí đánh giá thuật
toán lậplịch
z Các phương thứchoạt động preemptive và
non-preemptive
z Các thuật toán lậplịch FCFS, SJF, ưu tiên,
RR
z Lậplịch vớihàngchờđamức, có và không
có phảnhồi
z Các phương pháp đánh giá thuậttoánlập
lịch
47
Bài tập
z Thựchiệnvídụ RR vớilượng tử thờigian
2ms, 6ms và 6ms.
z Tính thờigianchờ trungbìnhcủacáctiếntrình
trong các trường hợp này.
z Khi lượng tử thời gian thay đổi, thờigianchờ
trung bình thay đổithế nào?
z Tính thời gian hoàn thành (turnaround time) của
tấtcả các tiến trình trong các trường hợptrên
z Nhậnxétvề sự thay đổithời gian hoàn thành của
các tiếntrìnhkhilượng tử thời gian thay đổi