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

?Mô hình Tiến trình

?Trạng thái tiến trình

?Thông tin quản lý tiến trình

?Quá trình điều phối tiến trình

?Các thuật toán điều phối

pdf57 trang | Chuyên mục: Hệ Điều Hành | Chia sẻ: dkS00TYs | Ngày: 22/10/2014 | Lượt xem: 2301 | Lượt tải: 5download
Tóm tắt nội dung 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, để xem tài liệu hoàn chỉnh bạn click vào nút "TẢI VỀ" ở trên
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

File đính kèm:

  • pdfBà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.pdf
Tài liệu liên quan