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

i
 Caùc tieán trình ñoäc laäp vôùi nhau => khoâng coù söï trao ñoåi
thoâng tin hieån nhieân
winword
Visual C
CDplayer
Excel
OS
VD: Giôø thi lyù thuyeát moân Heä Ñieàu haønh
Moãi sinh vieân laø moät tieán trình :
Cuøng laøm baøi => Hoaït ñoäng ñoàng haønh
Coù baøi thi , buùt, giaáyrieâng => Taøi nguyeân rieâng bieät
Ñoäc laäp => Khoâng trao ñoåi (veà nguyeân taéc)
22
Tiểu trình
 Mỗi tiến trình có một không gian địa chỉ và một
dòng xử lý.
 Một số ứng dụng cần nhiều dòng xử lý cùng chia
sẻ một không gian địa chỉ tiến trình, điều này đưa
đến một cơ chế thực thi mới, được gọi là tiểu trình.
 Tiểu trình là một đơn vị xử lý cơ bản trong hệ
thống, nó hoàn toàn tương tự như tiến trình. Tức là
nó cũng phải xử lý tuần tự các chỉ thị máy, nó cũng
sở hữu con trỏ lệnh, một tập các thanh ghi, và một
không gian stack riêng.
 Một tiến trình bao gồm nhiều tiểu trình.
23
Tieåu trình - Thread
25
 Tiểu trình là một đơn vị xử lý cơ bản trong hệ
thống, nó hoàn toàn tương tự như tiến trình.
 Tức là nó cũng phải xử lý tuần tự các chỉ thị máy
của nó, nó cũng sở hữu con trỏ lệnh, một tập các
thanh ghi, và một không gian stack riêng.
 Một tiến trình đơn có thể gồm nhiều tiểu trình.
Các tiểu trình trong một tiến trình chia sẻ một
không gian địa chỉ chung => có thể chia sẻ các
biến toàn cục của tiến trình và có thể truy xuất lên
các vùng nhớ stack của nhau.
Tiểu trình
PCB vaøTCB trong moâ hình multithreads
pid
Threads list
Context
(Mem, global 
ressources)
Scheduling statistic
Relatives
( Dad, children)
PCB
tid
State
(State, details)
Context
(IP, local stack)
Thread Control Block
TCB
26
Lợi ích của Tiểu trình
 Ñaùp öùng nhanh: Cho pheùp chöông trình tieáp tuïc
thöïc thi khi moät boä phaän bò khoùa hoaëc moät hoaït
ñoäng daøi
 Chia seû taøi nguyeân: tieát kieäm khoâng gian nhôù
 Kinh teá: taïo vaø chuyeån ngöõ caûnh nhanh hôn tieán
trình
VD: trong Solaris 2, taïo process chaäm hôn 30 laàn,
chuyeån chaäm hôn 5 laàn
 Trong multiprocessor: coù theå thöïc hieän song song
27
Ví duï: Tieåu trình
 Thöïc haønh moân Heä Ñieàu haønh
Moãi nhoùm 2 sinh vieân laø moät tieán trình :
Moãi sinh vieân laø moät tieåu trình
 Cuøng laøm baøi => Hoaït ñoäng ñoàng haønh
 Coùù baøi thöïc haønh chung => Taøi nguyeân
chung
 Trao ñoåi vôùi nhau
28
Tieåu trình vs Tieán trình
 Tieåu trình: 1 doøng xöû lyù
 Tieán trình: 
 1 khoâng gian ñòa chæ
 1 hoaëc nhieàu tieåu trình
 Caùc tieán trình laø ñoäc laäp
 Caùc tieåu trình trong cuøng 1 
tieán trình khoâng coù söï baûo veä
laãn nhau (caàn thieát ? ).
P1
int a;
T1 T2 T
3
29
Phaân chia CPU?
 1 CPU vaät lyù: laøm theá naøo ñeå taïo aûo giaùc moãi
tieán trình sôû höõu CPU rieâng cuûa mình ?
 Luaân chuyeån CPU giöõa caùc tieán trình
 2 thaønh phaàn ñaûm nhieäm vai troø ñieàu phoái:
 Scheduler choïn 1 tieán trình
 Dispatcher chuyeån CPU (processor) cho tieán trình
ñöôïc choïn
CPU
30
Scheduler - Nhieäm vuï
 Ra quyeát ñònh choïn moät tieán trình ñeå caáp
phaùt CPU :
 ÖÙng cöû vieân = {Caùc tieán trình ready list}
 0 tieán trình : CPU raûnh roãi (idle)!
 1 tieán trình : khoâng caàn suy nghó nhieàu, ñuùng
khoâng ?
 >1 : choïn ai baây giôø ?  Caàn coù thuaät toaùn
ñieàu phoái
31
Dispatcher - Nhieäm vuï
 Nhieäm vuï cuûa Dispatcher: Chuyeån ñoåi ngöõ caûnh
 Xeùt ví duï
 Tieán trình A ñang duøng CPU 1 chuùt thì bò HÑH thu hoài
CPU
 HÑH caáp CPU cho B duøng 1 chuùt, HÑH thu hoài laïi CPU.
 HÑH caáp CPU trôû laïi cho A.
 Giaù trò caùc thanh ghi giöõa nhöõng laàn chuyeån ñoåi
CPU?
 Kòch baûn :
 Löu ngöõ caûnh tieán trình hieän haønh
 Naïp ngöõ caûnh tieán trình ñöôïc choïn keá tieáp
32
33
Phân biệt chương trình và tiến trình
 Một chương trình là một thực thể thụ động,
chứa đựng các chỉ thị điều khiển máy tính để
tiến hành một tác vụ nào đó.
 Khi cho thực hiện các chỉ thị này, chương
trình chuyển thành tiến trình, là một thực thể
hoạt động, với con trỏ lệnh xác định chỉ thị kế
tiếp sẽ thi hành, kèm theo tập các tài nguyên
phục vụ cho hoạt động của tiến trình.
2. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH
2.1. Trạng thái tiến trình và sự chuyển
trạng thái tiến trình
 Trạng thái của tiến trình tại một thời điểm được
xác định bởi hoạt động hiện thời của tiến trình tại
thời điểm đó.
 Nguyên nhân một tiến trình thay đổi trạng thái :
 Phải chờ một sự kiện nào đó xảy ra
 Đợi một thao tác nhập/xuất hoàn tất
 Buộc phải dừng hoạt động do đã hết thời gian xử lý
35
36
ready running
dispatch
interrupt
I/O or event 
completion
I/O or 
event wait
new
terminated
waiting
admit exit
37
Các trạng thái của tiến trình
 New (Mới tạo): tiến trình đang được tạo lập.
 Running (thực hiện): Là trạng thái mà tiến trình đang
được sở hữu processor để hoạt động
 Blocked hay waiting (khoá): Là trạng thái mà tiến
trình đang chờ để được cấp phát thêm tài nguyên hay
chờ một sự kiện xảy ra .
 Ready : là trạng thái của một tiến trình trong hệ thống
đã có đủ tài nguyên, đang chờ được cấp processor
để bắt đầu thực hiện.
 Kết thúc (terminated): tiến trình hoàn tất xử lý.
Tại một thời điểm, chỉ có một tiến trình có thể nhận
trạng thái running trên một bộ xử lý bất kỳ. Trong khi
đó, nhiều tiến trình có thể ở trạng thái blocked hay
ready
2.2. Cấu trúc dữ liệu khối quản lý
tiến trình
38
Khối quản lý tiến trình hay Khối điều khiển tiến trình
(process control block - PCB). 
 Quản lý mọi hoạt động của tiến trình
 Cấu trúc dữ liệu của khối điều khiển bao gồm:
 Định danh tiến trình
 Trạng thái của tiến trình
 Ngữ cảnh của tiến trình
 Thông tin giao tiếp
 Thông tin thống kê
status
pid
Waiting list
CPU-state-rec
Processor
Main store
Resource
Created recource
Parent
Progency
Priority 
CPU time 
Unit 1 Unit 2
RCB 1 RCB 2
RCB 1 RCB 2
PCB
PCB 1 PCB 2
(3) Ngữ cảnh của trình
(4) Thông tin giao tiếp
(5) Thông tin thống kê
(2) Trạng thái trình
(1) Định danh trình
39
40
Cấu trúc dữ liệu khối quản lý tiến trình
 Định danh của tiến trình (1) : giúp phân biệt các
tiến trình
 Trạng thái tiến trình (2): xác định hoạt động hiện
hành của tiến trình.
 Ngữ cảnh của tiến trình (3): mô tả các tài nguyên
tiến trình đang trong quá trình, hoặc để phục vụ
cho hoạt động hiện tại, hoặc để làm cơ sở phục
hồi hoạt động cho tiến trình, bao gồm các thông
tin về:
 Trạng thái CPU: nội dung các thanh ghi, quan trọng
nhất là con trỏ lệnh IP lưu trữ địa chỉ câu lệnh kế tiếp
tiến trình sẽ xử lý. Các thông tin này cần được lưu trữ
khi xảy ra một ngắt, nhằm có thể cho phép phục hồi
hoạt động của tiến trình đúng như trước khi bị ngắt.
41
Ngữ cảnh của tiến trình (3)
 Bộ xử lý: dùng cho máy có cấu hình nhiều CPU,
xác định số hiệu CPU mà tiến trình đang sử dụng.
 Bộ nhớ chính: danh sách các khối nhớ được cấp
cho tiến trình.
 Tài nguyên sử dụng: danh sách các tài nguyên hệ
thống mà tiến trình đang sử dụng.
 Tài nguyên tạo lập: danh sách các tài nguyên được
tiến trình tạo lập.
42
Cấu trúc dữ liệu khối quản lý tiến trình
 Thông tin giao tiếp (4): phản ánh các thông tin về
quan hệ của tiến trình với các tiến trình khác
trong hệ thống :
 Tiến trình cha: tiến trình tạo lập tiến trình này .
 Tiến trình con: các tiến trình do tiến trình này tạo lập .
 Độ ưu tiên : giúp bộ điều phối có thông tin để lựa chọn
tiến trình được cấp CPU.
 Thông tin thống kê (5): thống kê về hoạt động
của tiến trình
 Thời gian đã sử dụng CPU
 Thời gian chờ.
 Các thông tin này có thể có ích cho công việc đánh giá
tình hình hệ thống và dự đoán các tình huống tương
lai.
Lưu đồ chuyển CPU từ tiến trình này 
sang tiến trình khác
43
44
Process table
45
Process table
 Hệ điều hành lưu con trỏ tới từng PCB của mỗi tiến
trình trong một bảng tiến trình của toàn hệ thống
hoặc từng người dùng.
 Truy cập nhanh tới các PCB
 Khi một tiến trình bị dừng, hệ điều hành loại bỏ tiến
trình khỏi bảng tiến trình và giải phóng tất cả các tài
nguyên của tiến trình
46
2.3. Thao tác trên tiến trình
 Tạo lập tiến trình (create)
 Kết thúc tiến trình (destroy)
 Tạm dừng tiến trình (suspend)
 Tái kích hoạt tiến trình (resume)
 Thay đổi độ ưu tiên tiến trình
3. TÀI NGUYÊN GĂNG VÀ ĐIỀU ĐỘ TIẾN TRÌNH
3.1. Tài nguyên găng (Critical Resource) 
 Trong môi trường đa nhiệm dẫn đến dùng chung tài
nguyên -> cạnh tranh.
 Xung đột được thể hiện: Hai tiến trÌnh hoạt động đồng
thời cùng ghi vào một không gian nhớ chung (một
biến chung) trên bộ nhớ hay hai cùng ghi dữ liệu vào
một file chia sẻ.
 Những tài nguyên được hệ điều hành chia sẻ cho
nhiều tiến trÌnh hoạt động đồng thời dùng chung, mà
có nguy cơ dẫn đến sự tranh chấp được gọi là tài
nguyên găng.
 Tài nguyên găng có thể là tài nguyên phần cứng hoặc
tài nguyên phần mềm, có thể là tài nguyên phân chia
được hoặc không phân chia được.
48
Tài nguyên găng (Critical Resource)
Ví dụ: bài toán rút tiền ngân hàng từ tài khoản dùng chung
If (tài khoản – tiền rút >=0)
tài khoản:=tài khoản – tiền rút
Else
Thông báo lỗi
endif
49
3.2 Đoạn găng (Critical Section)
 Các đoạn code trong các chương trình dùng để
truy cập đến tài nguyên găng được gọi là đoạn
găng
 Để hạn chế lỗi có thể xảy ra do sử dụng tài
nguyên găng, tại 1 thời điểm HĐH chỉ cho 1 tiến
trình nằm trong đoạn găng
 HĐH có cơ chế điều độ tiến trình qua đoạn găng
50
51
 Trong kho¶ng thêi gian tiÕn tr×nh sö dông tµi
nguyªn g¨ng th× ta gäi ®ã lµ tiÕn tr×nh g¨ng.
 Mét tiÕn tr×nh cã thÓ chia lµm 2 ®o¹n : ®o¹n
g¨ng vµ ®o¹n cßn l¹i.
2.3 Yêu cầu của công tác điều độ tiến
trình qua đoạn găng
 Tại 1 thời điểm chỉ cho phép 1 tiến trình nằm
trong đoạn găng, các tiến trình khác có nhu cầu
vào đoạn găng phải chờ
 Tiến trình chờ ngoài đoạn găng không được ngăn
cản các tiến trình khác vào đoạn găng
 Không có tiến trình nào phải chờ lâu để được vào
đoạn găng
 Đánh thức các tiến trình trong hàng đợi để tạo
điều kiện cho nó vào đoạn găng khi tài nguyên
găng được giải phóng
52
53
Điều độ tiến trình qua đ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