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

eemptive scheduling):
tiến trình được chọn có quyền độc chiếm CPU
„ Các thời điểm kích hoạt Scheduler 
„ P cur kết thúc
„ P cur : running ->blocked
„ Điều phối không độc quyền (preemptive 
scheduling): tiến trình được chọn có thể bị cướp
CPU bởi tiến trình có độ ưu tiên cao hơn
„ Các thời điểm kích hoạt Scheduler 
„ P cur kết thúc
„ P cur : Running -> Blocked
„ Q : Blocked / New -> Ready
10/28/2005 Trần Hạnh Nhi 30
Hai nguyên tắc điều phối CPU
Không độc quyền
while (true) {
interrupt Pcur
save state Pcur
Scheduler.NextP() Ỉ Pnext
load state pnext
resume Pnext
}
Độc quyền
while (true) {
save state Pcur
Scheduler.NextP() Ỉ Pnext
load state pnext
resume Pnext
wait for Pnext
}
10/28/2005 Trần Hạnh Nhi 31
Đánh giá chiến lược điều phối
„ Sử dụng 2 đại lượng đo :
„ Turn- around time = Tquit –Tarrive: từ lúc vào HT đến khi hoàn tất
„ Waiting time = T in Ready
„ Xét trường hợp trung bình
„ N tiến trình
„ Avg Turn- around time = (Σ Turn- around time Pi )/N
„ Avg Waiting time = (Σ Waiting time Pi )/N
10/28/2005 Trần Hạnh Nhi 32
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
10/28/2005 Trần Hạnh Nhi 33
FCFS (First comes first served)
„ Tiến trình vào RL lâu nhất được chọn
trước
„ Theo thứ tự vào RL
„ Độc quyềnABC CPU
Ready List
CPUBC
Ready List
CPUC
Ready List
10/28/2005 Trần Hạnh Nhi 34
Minh họa FCFS
P TarriveRL CPU burst
P1 0 24
P2 1 3
P3 2 3
0:00 P1 vào RL
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
AvgWT = (23+25)/3 = 16
0:27 P2 kết thúc
P3 dùng CPU
P TT WT
P1 24 0
P2 27-1 24-1
P3 30-2 27-2
P1 P2 P3
0 24 27
10/28/2005 Trần Hạnh Nhi 35
Nhận xét FCFS
„ Đơn giản
„ Chịu đựng hiện tượng tích lũy thời gian chờ
„ Tiến trình có thời gian xử lý ngắn đợi tiến trình có thời gian xử lý
dài
„ Ưu tiên tiến trình cpu-bounded
„ Có thể xảy ra tình trạng độc chiếm CPU
10/28/2005 Trần Hạnh Nhi 36
Điều phối 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
ƒ Điều phối theo nguyên tắc FCFS
ƒ Mỗi tiến trình chỉ sử dụng một lượng q cho mỗi lần sử dụng CPU
Quantum/
Time slice
10/28/2005 Trần Hạnh Nhi 37
Minh họa RR, q=4
P TarriveRL CPU burst
P1 0 24
P2 1 3
P3 2 3
AvgWT = (6+3+5)/3 = 4.66
P TT WT
P1 30 0+(10-4)
P2 7-1 4-1
P3 10-2 7-2
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
…
10/28/2005 Trần Hạnh Nhi 38
Minh họa RR, q=4
P TarriveRL CPU burst
P1 0 24
P2 4 3
P3 12 3
P1 P1 P2 P1 P3 P1 P1 P1
0 4 8 11 15 18 22 26 30
RL
0:00 P1 
0:04 
0:8 P2 P1
?
ƒ Tranh chấp vị trí trong RL : “Chung thủy”
1. P : running -> ready
2. P : blocked -> ready
3. P: new ->ready
ƒ Không phải luôn luôn có thứ tự điều phối P1 
P2 P3 P4P1 P2 P3 P4...
0:11 P1
0:15 P3 P1
0:18 P1
0:04 P1 P2
0:04 P2 P1
“Chung thủy”
“Có mới nới cũ”
10/28/2005 Trần Hạnh Nhi 39
RR : Khi nào kết thúc 1 lượt sử dụng CPU
„ Hết thời lượng q ms (quantum) cho phép
„ Tiến trình kết thúc
„ Tiến trình bị khóa
„ ChờRs
„ Chờ biến cố
10/28/2005 Trần Hạnh Nhi 40
Nhận xét RR
„ Sử dụng cơ chế không độc quyền
„ Mỗi tiến trình không phải đợi quá lâu
„ Loại bỏ hiện tượng độc chiếm CPU
„ Hiệu quả ? 
„ Phụ thuộc vào việc chọn lựa quantum q
„ q quáù lớn ???
„ q quá nhỏ ???
„ Trường hợp xấu nhất của RR ?
Bao lâu ?
Giảm tíùnh tương
tác
Tăng chi phí chuyển đổi
ngữ cảnh
10/28/2005 Trần Hạnh Nhi 41
Điều phối với độ ưu tiê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
ƒ Tiến trình có độ ưu tiên cao nhất được chọn cấp CPU trước
10/28/2005 Trần Hạnh Nhi 42
Ví dụ: Độ ưu tiên của HĐH WinNT
„ WinNT gán cho mỗi tiến trình độ ưu tiên có giá trị giữa 0 & 31
„ 0 (độ ưu tiên nhỏ nhất): dành riêng cho trạng thái system idle
„ Độ ưu tiên được phân theo nhóm:
„ Realtime : (16 - 31)
„ Thích hợp cho các tiến trình thời gian thực
„ Dành riêng cho các tiến trình của người quản trị hệ thống
„ Dynamic : (0 - 15)
„ Thích hợp cho các tiến trình của người dùng thường
„ Chia thành 3 mức : 
„ high (11 - 15)
„ normal (6 - 10) 
„ idle (2 - 6)
10/28/2005 Trần Hạnh Nhi 43
Biểu đồ phân bố độ ưu tiên của WinNT
24
realtime
13
high
8
normal
system idle
dynamic idle
dynamic time-critical
realtime idle
realtime time-critical
0
1
15
dynamic
levels 1-15
16
31
realtime
levels 16-31
lowest (-2)
below normal (-1)
normal (0)
above normal (+1)
highest (+2)
4
idle
10/28/2005 Trần Hạnh Nhi 44
Nguyên tắc điều phối
„ Độc quyền
„ Lượt sử dụng CPU kết thúc khi: 
„ tiến trình kết thúc,
„ tiến trình bị khóa
„ Không độc quyền
„ Lượt sử dụng CPU kết thúc khi: 
„ tiến trình kết thúc, 
„ tiến trình bị khóa, 
„ cótiến trình với độ ưu tiên cao hơn vào RL
10/28/2005 Trần Hạnh Nhi 45
Minh họa độ ưu tiên (khôngđộc quyền) 
P TRL Priority CPU burst
P1 0 2
0
1
24
P2 1 3
P3 2 3
AvgWT = (6+0+2)/3 = 2.66
P TT WT
P1 30 0+(7-1)
P2 4-1 0
P3 7-2 4-2
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
P2
2
0:02 P3 vào (độ ưu tiên thấp hơn P2)
P3 khơng dành được quyền dùng CPU 
10/28/2005 Trần Hạnh Nhi 46
Nhận xét
„ Cách tính độ ưu tiên ?
„ Hệ thống gán : CPU times…
„ Người dùng gán tường minh
„ Tính chất độ ưu tiên :
„ Tĩnh
„ Động
„ Số phận tiến trình có độ ưu tiên thấp ?
„ Chờ lâu, lâu, lâu ...
starvation
Aging : tăng độ ưu tiên
cho những tiến trình chờ
lâu trong hệ thống
10/28/2005 Trần Hạnh Nhi 47
Shortest Job First (SJF)
P3
(cần 7 chu kỳ)
P1
(cần 5 chu kỳ)
P2
(cần 3 chu kỳ)
Ngắn nhất
Ready List
CPU
pi = thời_gian_cịn_lại(Processi)
Là một dạng độ ưu tiên đặc biệt với độ ưu tiên
Ỵ Cĩ thể cài đặt độc quyền hoặc khơng độc quyền
10/28/2005 Trần Hạnh Nhi 48
Minh họa SJF (độc quyền)(1) 
P TarriveRL CPU burst
P1 0 24
P2 1 3
P3 2 3
AvgWT = (23+25)/3 = 16
P TT WT
P1 24 0
P2 27 24-1
P3 30 27-2
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
10/28/2005 Trần Hạnh Nhi 49
Minh họa SJF (độc quyền)(2) 
P TarriveRL CPU burst
P1 0 24
P2 1 3
P3 1 2
AvgWT = (24+22)/3 = 15.33
P TT WT
P1 24 0
P2 29 26-1
P3 26 24-2
0:00 P1 vào, P1 dùng CPU
0:01 P2 vào
0:01 P3 vào
0:24 P1 kết thúc, P3 dùng CPU
0:26 P3 dừng, P2 dùng CPU
0:29 P2 dừng
P1 P3 P2
290 24 26
10/28/2005 Trần Hạnh Nhi 50
Minh họa SJF (khôngđộc quyền) (1)
P TarriveRL CPU burst
P1 0 24
P2 1 3
P3 2 3
AvgWT = (6+0+2)/3 = 2.66
P TT WT
P1 30 0+(7-1)
P2 4-1 0
P3 7-2 4-2
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
10/28/2005 Trần Hạnh Nhi 51
Minh họa SJF (khôngđộc quyền) (2)
P TarriveRL CPU burst
P1 0 24
P2 1 5
P3 3 4
AvgWT = (9+0+3)/3 = 4
P TT WT
P1 33 0+(10-1)
P2 6 0
P3 10 6-3
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:9 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 
10/28/2005 Trần Hạnh Nhi 52
Minh họa SJF (nhiều chu kỳ CPU)
P TarriveRL CPU1
burst
IO1
R
IO1
T
IO2
R
IO2
T
2 2
4
0
10
5
1
R2
R1
Null
1
CPU2 
burst
8
R1
R1
R2
P1 0 2
P2 2 1
P3 10 0
P1 P3
0 21
P2
2 16 0
P1
3
CPU
P1 P2
13
1913 15
P2
3
R1
P1 P3
221917 21
R2
P2
14
P3
15
P1
17
P3
10/28/2005 Trần Hạnh Nhi 53
Nhận xét SJF
„ Tối ưu thời gian chờ
„ Chứng minh ?
„ Không khả thi
„ Làm sao biết CPU burst ?
AvgWT = (3a+2b+c)
Min AvgWT ?
a<b<c
P1
a
P2
b
P3
c
past historyrelative weightmost recent 
information
( ) nnn t ταατ −+=+ 1 1
length of the nth 
CPU burst
predicted value for 
the nth CPU burst0<= α<=1
10/28/2005 Trần Hạnh Nhi 54
Điều phối với nhiều mức ưu tiên
„ Tổ chức N RL ứng với
nhiều mức ưu tiên
„ Mỗi RLi áp dụng một
chiến lược điều phối
thích hợp
„ Giữa các RL áp dụng
điều phối theo độ ưu
tiên :
„ RLi rỗng mới điều phối
RLi +1
Độ ưu tiên
1
…
2
n
C
P
U
Kết hợp
nhiều chiến lược
10/28/2005 Trần Hạnh Nhi 55
Điều phối với nhiều mức ưu tiên – Thực tế
„ Tổ chức N RL ứng với
nhiều mức ưu tiên
„ Mỗi RLi áp dụng RR
„ Giữa các RL áp dụng
điều phối theo độ ưu
tiên :
„ RLi rỗng mới điều phối
RLi +1
Độ ưu tiên
1
…
2
n
C
P
U
Kết hợp
nhiều chiến lược
10/28/2005 Trần Hạnh Nhi 56
Khuyết điểm
„ Starvation !!!
„ Giải pháp Aging :
„ Chờ lâu quá : chuyển lên RL 
với độ ưu tiên cao hơn
„ Chiếm CPU lâu quá : chuyển
xuống RL với độ ưu tiên thấp
hơn
/ /2 /
☺ ☺1 ☺ CPU
Chờ lâu quá
Khi nào thực hiện aging ?
Aging tiến trình nào ?
10/28/2005 Trần Hạnh Nhi 57
IO lần 1 IO lần 2
Thời
gian
Thiết
bị
Thời
gian
Thiết
bị
P1 0 8 5 R1 1 0 Null
P2 2 1 8 R2 2 5 R1
P3 10 6 5 R1 2 3 R2
P4 11 3 20 R2 0 0 Null
CPU2
Tiến
trình
Thời điểm
vào Ready 
list
CPU1
Bài tập: Hãy điều phối
CPU: SJF khơng độc quyền. R1,R2: FIFO