Bài giảng Hệ điều hành - Chương 2: Quản lý tiến trình

ua đoạn găng
Cã 2 møc ®é ®iÒu ®é s¬ cÊp vµ cao cÊp.
 ë møc s¬ cÊp
 c¸c lÖnh ®iÒu ®é ®-îc ®Æt ngay trong ch-¬ng tr×nh
ng-êi dïng: Kü thuËt khãa trong (®Ìn hiÖu), Kü thuËt
kiÓm tra vµ x¸c lËp, Kü thuËt semaphore
 §iÒu ®é cao cÊp
 lÖnh ®iÒu ®é ®Æt trong thµnh phÇn hÖ ®iÒu hµnh.
 ch-¬ng tr×nh ®iÒu phèi c«ng viÖc vµ ®iÒu phèi chÝnh
 Ng-êi sö dông kh«ng biÕt tµi nguyªn g× vµ khi nµo
thuéc lo¹i g¨ng => HÖ thèng ph¶i cã tr¸ch nhiÖm kiÓm
tra. nhËn biÕt vµ ®iÒu ®é: Dïng ch-¬ng tr×nh monitor
(th- ký) ®Ó ®iÒu ®é
4. TẮC NGHẼN VÀ CHỐNG TẮC NGHẼN
4.1 Tắc nghẽn (Deadlock)
 Tắc nghẽn: Hiện tượng bắt nguồn từ sự xung đột
về tài nguyên của hai hoặc nhiều tiến trình đang
hoạt động đồng thời trên hệ thống.
55
56
57
4.2. §iÒu kiÖn x¶y ra Tắc nghẽn
4 điều kiện cần có thể làm xuất hiện tắc nghẽn:
 Có sử dụng tài nguyên không thể chia sẻ
(Mutual exclusion): Mỗi thời điểm, một tài
nguyên không thể chia sẻ được hệ thống cấp
phát chỉ cho một tiến trình, khi tiến trình sử
dụng xong tài nguyên này, hệ thống mới thu
hồi và cấp phát tài nguyên cho tiến trình khác.
58
 Sự chiếm giữ và yêu cầu thêm tài nguyên
(Wait for): Các tiến trình tiếp tục chiếm giữ
các tài nguyên đã cấp phát cho nó trong khi
chờ được cấp phát thêm một số tài nguyên
mới.
 Không thu hồi tài nguyên từ tiến trình đang
giữ chúng: Tài nguyên không thể được thu
hồi từ tiến trình đang chiếm giữ chúng trước
khi tiến trình này sủ dụng chúng xong.
59
 Tồn tại một chu kỳ trong đồ thị cấp phát tài
nguyên (Circular wait): có ít nhất hai tiến trình
chờ đợi lẫn nhau: tiến trình này chờ được cấp
phát tài nguyên đang bị tiến trình kia chiếm giữ
và ngược lại (Đợi vòng tròn).
=> Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy
ra.
4.3. Các mức phòng tránh tắc nghẽn
 Ngăn ngừa
 Dự báo và tránh tắc nghẽn
 Nhận biết và khắc phục
60
61
Các phương pháp xử lý tắc nghẽn
3 hướng tiếp cận để xử lý tắc nghẽn :
 Sử dụng một quy tắc (protocol) để bảo đảm rằng
hệ thống không bao giờ xảy ra tắc nghẽn.
 Cho phép xảy ra tắc nghẽn và tìm cách sữa
chữa tắc nghẽn.
 Hoàn toàn bỏ qua việc xử lý tắc nghẽn, xem như
hệ thống không bao giờ xảy ra tắc nghẽn.
5. ĐIỀU PHỐI TIẾN TRÌNH
63
 Trong môi trường hệ điều hành đa nhiệm, bộ
phận điều phối tiến trình có nhiệm vụ xem xét và
quyết định khi nào thì dừng tiến trình hiện tại để
thu hồi processor và chuyển processor cho tiến
trình khác, và khi đã có được processor thì chọn
tiến trình nào trong số các tiến trình ở trạng thái
ready để cấp processor cho nó.
 Xác định process nào được thực thi tiếp theo
=>ĐIỀU PHỐI TIẾN TRÌNH còn gọi là định thời
CPU
5.1 Mục tiêu điều phối
 Hieäu quûa (Efficiency) 
  Thôøi gian
 Ñaùùp öùng (Response time): Cực tiểu hoá thời gian hồi đáp cho các
tương tác của người sử dụng
 Hoaøn taát (Turnaround Time = Tquit -Tarrive): Cực tiểu hóa thời gian
hoàn tất các tác vụ xử lý theo lô.
 Chôø (Waiting Time = T in Ready ) :
  Thoâng löôïng (Throughput = # jobs/s ): Cực đại hóa số công việc
được xử lý trong một đơn vị thời gian
 Hieäu suaát Taøi nguyeân
 Chi phí chuyeån ñoåi
 Coâng baèng ( Fairness): Taát caû caùc tieán trình ñeàu coù cô hoäi
nhaän CPU
64
5.2 Cơ chế điều phối
 Độc quyền: Tiến trình toàn quyền sử dụng processor
cho đến khi kết thúc hoặc tự động trả lại (tieán trình
ñöôïc choïn coù quyeàn ñoäc chieám CPU)
 Quyết định điều phối khi tiến trình chuyển từ Running sang
Waiting (blocked) hoặc kết thúc
 Không độc quyền: Tiến trình đang xử lý thì bị thu hồi
processor để cấp cho tiến trình khác (tieán trình ñöôïc
choïn coù theå bò cöôùp CPU bôûi tieán trình coù ñoä öu
tieân cao hôn)
 Quyết định điều phối khi tiến trình chuyển từ Running sang
Waiting (blocked) hoặc ready hoặc kết thúc hoặc từ Waiting sang
ready
65
5.3 Các đặc điểm của tiến trình
 Tính hướng xuất nhập
 Tính hướng xử lý
 Tương tác hay xử lý theo lô
 Độ ưu tiên của tiến trình
 Thời gian sử dụng CPU
 Thời gian còn lại để tiến trình hoàn tất
66
5.4 Tổ chức điều phối
 HĐH sử dụng 2 loại danh sách để tổ chức lưu trữ các
tiến trình:
 Danh sách Ready: Chỉ tồn tại 1 danh sách này
 Danh sách Waiting: Có thể tồn tại nhiều danh sách này
Ready List P1 P4 P5
Waiting Lists R1 P7P2
P10P3
P6
R2
R3
67
5.5 Các chiến lược điều phối
 FIFO (FCFS)
 Xoay vòng (Round Robin)
 Theo độ ưu tiên
 Công việc ngắn nhất (SJF)
 Nhiều mức độ ưu tiên
 …
68
FCFS (FIRST COMES FIRST SERVED)
 Tieán trình vaøo RL laâu nhaát
ñöôïc choïn tröôùc
 Theo thứ tự vaøo RL
 Độc quyền
ABC CPU
Ready List
CPUBC
Ready List
CPUC
Ready List
Tiến trình nào được đưa vào danh sách ready trước sẽ được
cấp Processor trước, sử dụng trong điều phối độc quyền nên
khi tiến trình được cấp processor nó sẽ sở hữu processor cho
đến khi kết thúc xử lý hay phải đợi một thao tác vào/ra hoàn
thành, khi đó tiến trình chủ động trả lại processor cho hệ thống.
69
MINH HOÏA FCFS
P TarriveRL
(Tđiểm vào)
CPU burst
(Tgian xử lý)
P1 0 24
P2 1 3
P3 2 3
P TT
(Hoàn tất)
W
(Chờ)
P1 24 0
P2 27-1 24-1
P3 30-2 27-2
0: P1 vào RL
P1 dùng CPU
1: P2 vào RL
2: P3 vào RL
24: P1 kết thúc
P2 dùng CPU
AvgWT = (0+23+25)/3 = 16
27: P2 kết thúc
P3 dùng CPU
P1 P2 P3
0 24 27
NHAÄN XEÙT FCFS
 Ñôn giaûn
 Chòu ñöïng hieän töôïng tích luõy thôøi gian chôø
 Tieán trình coù thôøi gian xöû lyù ngaén ñôïi tieán trình coù thôøi
gian xöû lyù daøi
 Öu tieân tieán trình cpu-bounded
 Coù theå xaûy ra tình traïng ñoäc chieám CPU
71
ÑIEÀU PHOÁI xoay vòng ROUND ROBIN (RR)
ABC CPU
Ready List
A chỉ chiếm CPU trong q ms
BCA CPU
Ready List
B được giao quyền sử dụng CPU
trong q ms kế tiếp
CAB CPU
Ready List
C được giao quyền sử dụng CPU
trong q ms kế tiếp
 Ñieàu phoái theo nguyeân taéc FCFS
 Moãi tieán trình chæ söû duïng moät löôïng q cho moãi laàn
söû duïng CPU
Quantum/
Time slice
72
MINH HOÏA RR, Q=4
P TarriveRL CPU burst
P1 0 24
P2 1 3
P3 2 3
P TT WT
P1 30 0+(10-4)
P2 7-1 4-1
P3 10-2 7-2
AvgWT = (6+3+5)/3 = 4.66
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30
0:00 P1 vào, P1 dùng CPU
0:01 P2 vào (đợi)
0:02 P3 vào (đợi)
0:04 P1 hết lượt, P2 dùng CPU
0:07 P2 dừng, P3 dùng CPU
0:10 P3 dừng, P1 dùng CPU
0:14 P1 vẫn chiếm CPU
…
73
ROUND ROBIN
 Khi naøo keát thuùc 1 löôït söû duïng CPU
 Heát thôøi löôïng q ms (quantum) cho pheùp
 Tieán trình keát thuùc
 Tieán trình bò khoùa
 Chờ Rs
 Chờ biến cố
74
ROUND ROBIN – NHAÄN XEÙT
 Söû duïng cô cheá khoâng ñoäc quyeàn
 Moãi tieán trình khoâng phaûi ñôïi quaù laâu
 Loaïi boû hieän töôïng ñoäc chieám CPU
 Hieäu quaû ?
 Phuï thuoäc vaøo vieäc choïn löïa quantum q
 q quaùù lớn ???
 q quaù nhỏ ???
Bao laâu ?
Giaûm tíùnh töông taùc
Taêng chi phí chuyeån ñoåi ngöõ
caûnh
75
ÑIEÀU PHOÁI VÔÙI ÑOÄ ÖU TIEÂN
Phân biệt tiến trình quan trọng >< tiến trình bình thường?
WinAmp
độ ưu tiên: cao (3)
Outlook
độ ưu tiên: thấp (-3)
WinWord
độ ưu tiên: trung bình (0)
Đ
ộ
 ư
u
 tiên
 Tieán trình coù ñoä öu tieân cao nhaát ñöôïc choïn caáp CPU 
tröôùc
76
NGUYEÂN TAÉC ÑIEÀU PHOÁI
 Độc quyền
 Lượt sử dụng CPU kết thuùc khi: 
 tiến trình kết thuùc,
 tiến trình bị khoùa
 Khoâng đĐộc quyền
 Lượt sử dụng CPU kết thuùc khi: 
 tiến trình kết thuùc, 
 tiến trình bị khoùa, 
 coùtiến trình vôùi đĐộ ưu tieân cao hơn vaøo RL
77
ÑOÄ ÖU TIEÂN – KHOÂNG ÑOÄC QUYEÀN
P TRL Priority CPU burst
P1 0 0 24
P2 1 2 3
P3 2 1 3
P TT WT
P1 30 0+(7-1)
P2 4-1 0
P3 7-2 4-2
AvgWT = (6+0+2)/3 = 2.66
0: P1 vào, P1 dùng CPU
1: P2 vào (độ ưu tiên cao hơn P1)
P2 dành quyền dùng CPU 
4: P2 kết thúc, P3 dùng CPU
7: P3 dừng, P1 dùng CPU
30: P1 dừng
P1 P3 P1
0 30
P2
41 7
P2
2
2: P3 vào (độ ưu tiên thấp hơn P2)
P3 không dành được quyền dùng CPU 
78
SHORTEST JOB FIRST (SJF)
P3
(cần 7 chu kỳ)
P1
(cần 5 chu kỳ)
P2
(cần 3 chu kỳ)
Ready List
CPU
 Có thể cài đặt độc quyền hoặc không độc quyền
79
 Chiến lược công việc ngắn nhất (shortest job first -
SJF):
 Đây là một trường hợp đặc biệt của giải thuật điều phối với
độ ưu tiên
 độ ưu tiên p được gán cho mỗi tiến trình là nghịch đảo của
thời gian xử lý t mà tiến trình yêu cầu : p = 1/t
 CPU được sẽ được 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
 Giải thuật này cũng có thể độc quyền hoặc không độc
quyền
80
MINH HOÏA SJF (ÑOÄC QUYEÀN)(1) 
P TarriveRL CPU burst
P1 0 24
P2 1 3
P3 2 3
P TT WT
P1 24 0
P2 27-1 24-1
P3 30-2 27-2
AvgWT = (23+25)/3 = 16
0:00 P1 vào, P1 dùng CPU
0:01 P2 vào RL
0:02 P3 vào RL
0:24 P1 kết thúc, P2 dùng CPU
0:27 P2 dừng, P3 dùng CPU
0:30 P3 dừng
P1 P2 P3
0 24 27 30
81
MINH HOÏA SJF (KHOÂNG ÑOÄC QUYEÀN) (1)
P TarriveRL CPU burst
P1 0 24
P2 1 3
P3 2 3
P TT WT
P1 30 0+(7-1)
P2 4-1 0
P3 7-2 4-2
AvgWT = (6+0+2)/3 = 2.66
0:00 P1 vào, P1 dùng CPU
0:01 P2 vào (độ ưu tiên cao hơn P1)
P2 dành quyền dùng CPU 
0:4 P2 kết thúc, P3 dùng CPU
0:7 P3 dừng, P1 dùng CPU
0:30 P1 dừng
P1 P3 P1
0 30
P2
41 7
82
MINH HOÏA SJF (KHOÂNG ÑOÄC QUYEÀN) (2)
P TarriveRL CPU burst
P1 0 24
P2 1 5
P3 3 4
P TT WT
P1 33 0+(10-1)
P2 5 0
P3 7 6-3
AvgWT = (9+0+3)/3 = 4
0:00 P1 vào, P1 dùng CPU
0:01 P2 vào (độ ưu tiên cao hơn P1)
P2 dành quyền dùng CPU 
0:6 P2 kết thúc, P3 dùng CPU
0:10 P3 dừng, P1 dùng CPU
0:33 P1 dừng
P1 P3 P1
0 33
P2
61 10
P2
3
0:03 P3 vào (độ ưu tiên < P2)
P2 dành quyền dùng CPU 
83
ÑIEÀU PHOÁI VÔÙI NHIEÀU MÖÙC ÖU TIEÂN
 Toå chöùc n RL öùng
vôùi nhieàu möùc öu
tieân
 Moãi RL
i
aùp duïng moät
chieán löôïc ñieàu phoái
thích hôïp
 Giöõa caùc RL aùp duïng
ñieàu phoái theo ñoä öu
tieân :
 RL
i
roãng môùi ñieàu
phoái RL
i +1
Độ ưu tiên
1
…
2
n
C
P
U
Kết hợp
nhiều chiến lược 84
KHUYEÁT ÑIEÅM
 Starvation !!!
 Giaûi phaùp Aging :
 Chôø laâu quaù : chuyeån leân 
RL vôùi ñoä öu tieân cao hôn
 Chieám CPU laâu quaù : 
chuyeån xuoáng RL vôùi ñoä öu 
tieân thaáp hôn
 2 
 1  CPU
Chờ lâu quá
Khi naøo thöïc hieän aging?
Aging tieán trình naøo?
85