Bài giảng Nguyên lý hệ điều hành - Nguyễn Hải Châu - Tuần 3: Lập lịch tiến trình

 (0+24+27)/3=17ms
P1 P2 P3
0 24 27 33
21
Ví dụ FCFS 1b
z Xét ba tiến trình trong ví dụ 1a với thứ tự xếp
hàng P3, P2, P1
z Biểu đồ Gantt:
z Thời gian chờ của các tiến trình là: P3 chờ
0ms, P2 chờ 6ms, P3 chờ 9ms
z Thời gian chờ trung bình: (0+6+9)/3=5ms
z Thời gian chờ trung bình thấp hơn thời gian
chờ trung bình trong ví dụ 1a
P1P2P3
0 6 9 33
22
Hiện tượng “đoàn hộ tống”
z Thuật ngữ: convoy effect
z Xảy ra khi có một tiến trình “lớn” P nằm ở đầu
hàng chờ và nhiều tiến trình “nhỏ” Qi xếp hàng
sau P. 
z “Lớn”: Sử dụng nhiều thời gian CPU và vào ra
z “Nhỏ”: Sử dụng ít thời gian CPU và vào ra
z Thuật toán lập lịch được sử dụng là FCFS.:
z Hiện tượng xảy ra: CPU, thiết bị vào ra có nhiều
thời gian rỗi, thời gian chờ trung bình của các
tiến trình cao
23
Ví dụ convoy effect
Hàng chờ sẵn
sàng thực hiện
Hàng chờ vào/ra Yêu cầu vào/ra
Hết thời gian
sử dụng CPU
Tạo một tiến
trình con
Chờ ngắt
CPU
Vào/ra
Tiến trình con 
thực hiện
Ngắt xuất hiện
Q3(10) Q2(10) Q1(10) P (40)
P (50) Q1(10) Q2(10) Q3(10)
24
Convoy effect: Thời gian sử
dụng CPU và thiết bị vào ra
Thiết bị
vào ra
CPU
0 40 50 60 70
P Q1 Q2 Q3
400
Rỗi
90
P
90
Rỗi
Q1 Q2 Q3
100 110 120 130
130
P
Rỗi
140
Q1 Q2 Q3
150 160 180
180
P
z Giả sử P là tiến trình “lớn” có chu kỳ sử dụng CPU trong 40ms 
và vào ra trong 50ms
z Q1, Q2, Q3 là 3 tiến trình “nhỏ” có chu kỳ sử dụng CPU trong
10ms và vào ra trong 10ms
z Thứ tự xếp hàng: P, Q1, Q2, Q3
Rỗi
525
SJF (Shortest Job First)
z Với SJF, tham số lập lịch có thêm độ dài của
phiên sử dụng CPU tiếp theo tnextburst
z Tiến trình có tnextburst nhỏ nhất sẽ được lập
lịch sử dụng CPU trước
z Nếu hai tiến trình có tnextburst bằng nhau thì
FCFS được áp dụng
26
SJF (Shortest Job First)
z Với lập lịch dài hạn: Có thể biết tnextburst vì có
tham số chỉ ra thời gian chạy của tiến trình khi
đưa tiến trình vào hệ thống (job submit)
z Khó khăn: Chỉ có thể phỏng đoán được tnextburrt
với lập lịch ngắn hạn
z Đọc ở nhà: Dự đoán tnextburst bằng công thức
trung bình mũ (exponential average) trang
160-162 trong giáo trình
z SJF không tối ưu được với lập lịch ngắn hạn
z SJF thường được áp dụng cho lập lịch dài hạn
27
Lập lịch có độ ưu tiên
z Thuật ngữ: Priority scheduling
z Mỗi tiến trình được gắn một tham số lập lịch gọi là độ
ưu tiên p, với p là một số thực
z Tiến trình có độ ưu tiên cao nhất được sử dụng CPU
z Qui ước trong môn học này:
z Tiến trình P1 và P2 có độ ưu tiên p1, p2 tương ứng
z p1>p2 có nghĩa là tiến trình P1 có độ ưu tiên thấp hơn P2
z SJF là trường hợp đặc biệt của lập lịch có ưu tiên với
ưu tiên của các tiến trình là nghịch đảo độ dài phiên
sử dụng
28
Lập lịch có độ ưu tiên
z Hai cách xác định độ ưu tiên:
z Độ ưu tiên trong: Được tính toán dựa trên các
tham số định lượng của tiến trình như giới hạn về
thời gian, bộ nhớ, số file đang mở, thời gian sử
dụng CPU
z Độ ưu tiên ngoài: Dựa vào các yếu tố như mức
độ quan trọng, chi phí thuê máy tính…
z Chờ không xác định: Một tiến trình có độ ưu
tiên thấp có thể nằm trong hàng chờ trong
một khoảng thời gian dài nếu trong hàng chờ
luôn có các tiến trình có độ ưu tiên cao hơn
29
Lập lịch có độ ưu tiên
z Để tránh hiện tượng chờ không xác định, có
thêm tham số tuổi để xác định thời gian tiến
trình thời gian nằm trong hàng chờ
z Tham số tuổi được sử dụng để làm tăng độ
ưu tiên của tiến trình
z Ví dụ thực tế: Khi bảo dưỡng máy tính IBM 
7094 của MIT năm 1973, người ta thấy một
tiến trình nằm trong hàng chờ từ năm 1967 
nhưng vẫn chưa được thực hiện
30
Ví dụ lập lịch có độ ưu tiên
z Xét 5 tiến trình như trong
bảng với thứ tự trong hàng
chờ là P1, P2, P3, P4, P5
z Sử dụng thuật toán lập lịch
có ưu tiên, ta có thứ tự
thực hiện của các tiến trình
như sau biểu đồ dưới
z Thời gian chờ trung bình là
(1+6+16+18)/5=8.2ms
3
1
4
5
2
10
1
2
1
5
P1
P2
P3
P4
P5
Độ ưu
tiên
Thời gian
thực hiện
(ms)
Tiến
trình
P1(3)P5(2)
0 6 16
P2(1)
1
P3(4) P4(5)
18 19
631
Round-robin (RR)
z Còn gọi là lập lịch quay vòng
z Được thiết kế để áp dụng cho các hệ phân
chia thời gian (time-sharing)
z RR hoạt động theo chế độ preemptive
z Tham số lượng tử thời gian (time quantum) 
tquantum: Mỗi tiến trình được sử dụng CPU 
trong nhiều nhất bằng tquantum, sau đó đến
lượt tiến trình khác
32
Round-robin (RR)
z Hiệu quả của RR phụ thuộc độ lớn của
tquantum
z Nếu tquantum nhỏ thì hiệu quả của RR giảm vì bộ
điều phối phải thực hiện nhiều thao tác chuyển
trạng thái, lãng phí thời gian CPU
z Nếu tquantum lớn thì số thao tác chuyển trạng thái
giảm đi
z Nếu tquantum rất nhỏ (ví dụ 1ms) thì RR được
gọi là processor sharing
z Nếu tquantum = ∞ thì RR trở thành FCFS
33
Ví dụ RR
z Giả sử có 3 tiến trình P1, P2, P3 với thời gian thực
hiện tương ứng là 24ms, 3ms, 6ms, thứ tự trong
hàng chờ P1, P2, P3 ,vào hàng chờ cùng thời điểm 0
z Giả sử tquantum=4ms
z RR lập lịch các tiến trình như sau:
P2 P3 P1 P3 P1 P1 P1 P1P1
0 4 7 11 15 17 21 25 29 33
z Thời gian chờ
z P1: 0+(11-4)+(17-15)=9ms
z P2: 4ms
z P3: 7+(15-11)=11ms
z Thời gian chờ trung bình: 
(9+4+11)/3=8ms
34
Lập lịch với hàng chờ đa mức
z Thuật ngữ: Multilevel queue scheduling
z Được sử dụng khi ta có thể chia các tiến
trình thành nhiều lớp khác nhau để lập lịch
theo các tiêu chí khác nhau, ví dụ:
z Lớp các tiến trình có tương tác (interactive hoặc
foreground process) cần có độ ưu tiên cao hơn
z Lớp các tiến trình chạy nền (background) thường
không có tương tác với NSD: Độ ưu tiên thấp hơn
35
Lập lịch với hàng chờ đa mức
z Thuật toán lập lịch với hàng chờ đa mức chia
hàng chờ ready thành nhiều hàng chờ con 
khác nhau, mỗi hàng chờ con được áp dụng
một loại thuậ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ến trình có tương tác:RR
z Các tiến trình được phân lớp dựa vào đặc
tính như bộ nhớ, độ ưu tiên, …
z Cần có thuật toán lập lịch cho các hàng chờ
con, ví dụ: preemptive có độ ưu tiên cố định 36
Ví dụ hàng chờ đa mức
z Ví dụ các hàng chờ đa mức có độ ưu tiên
giảm dần:
z Hàng chờ các tiến trình hệ thống
z Hàng chờ các tiến trình có tương tác
z Hàng chờ các tiến trình là editor
z Hàng chờ các tiến trình hoạt động theo lô
z Hàng chờ các tiến trình thực tập của sinh viên
737
Lập lịch với hàng chờ đa mức
có phản hồi
z Thuật ngữ: Multilevel feedback-queue 
scheduling
z Thuật toán lập lịch kiểu này nhằm khắc phục
nhược điểm không mềm dẻo của lập lịch với
hàng chờ đa mức
z Ý tưởng chính: Cho phép tiến trình chuyển từ
hàng chờ này sang hàng chờ khác, trong khi
lập lịch với hàng chờ đa mức không cho phép
điều này
38
Lập lịch với hàng chờ đa mức
có phản hồi
z Cách thực hiện:
z Độ dài phiên sử dụng CPU và thời gian đã nằm
trong hàng chờ là tiêu chuẩn chuyển tiến trình
giữa các hàng chờ
z Tiến trình chiếm nhiều thời gian CPU sẽ bị
chuyển xuống hàng chờ có độ ưu tiên thấp
z Tiến trình nằm lâu trong hàng chờ sẽ được
chuyển lên hàng chờ có độ ưu tiên cao hơn
39
Các tham số của bộ lập lịch
hàng chờ đa mức có phản hồi
z Số lượng các hàng chờ
z Thuật toán lập lịch cho mỗi hàng chờ
z Phương pháp tăng độ ưu tiên cho một tiến trình
z Phương pháp giảm độ ưu tiên cho một tiến trình
z Phương pháp xác định hàng đợi nào để đưa
một tiến trình vào
40
Các thuật toán lập lịch khác
z Sinh viên tìm hiểu trong giáo trình:
z Lập lịch đa xử lý
z Lập lịch thời gian thực
41
Các phương pháp đánh
giá thuật toán lập lịch
42
Mô hình xác định
z Thuật ngữ: Deterministic modeling
z Dựa vào các trường hợp cụ thể (chẳng hạn
các ví dụ đã nói trong bài giảng này) để rút ra
các kết luận đánh giá
z Ưu điểm: Nhanh và đơn giản
z Nhược điểm: Không rút ra được kết luận
đánh giá cho trường hợp tổng quát
843
Mô hình hàng chờ
z Thuật ngữ: Queueing model
z Dựa trên lý thuyết xác suất, quá trình ngẫu nhiên. Tài
liệu tham khảo:
z Leonard Kleinrock, Queueing Systems: Volume I – Theory
(Wiley Interscience, New York, 1975) 
z Leonard Kleinrock, Queueing Systems: Volume II –
Computer Applications (Wiley Interscience, New York, 1976) 
z Ưu điểm: So sánh được các thuật toán lập lịch trong
một số trường hợp
z Hạn chế: Phức tạp về mặt toán học, lớp các thuật
toán phân tích so sánh được còn hạn chế
44
Mô phỏng
z Thuật ngữ: Simulation
z Thực hiện các tình huống giả định trên máy
tính để đánh giá hiệu quả của các thuật toán
lập lịch, kiểm nghiệm các kết quả lý thuyết
z Mô phỏng thường tốn thời gian CPU và
không gian lưu trữ
z Được sử dụng nhiều trong công nghiệp
z Ví dụ các hệ mô phỏng mạng (có module 
hàng chờ): OPNET, NS-2, Qualnet
45
Cài đặt thử trong thực tế
z Mô phỏng có thể xem như “qui nạp không
hoàn toàn”
z Có thể xây dựng hệ thống thử trong thực tế
z Ưu điểm: Đánh giá được hiệu quả thực sự
khi sử dụng
z Nhược điểm: 
z Chi phí cao
z Hành vi của người sử dụng có thể thay đổi theo
môi trường hệ thống
46
Tóm tắt
z Khái niệm lập lịch, các tiêu chí đánh giá thuật
toán lập lịch
z Các phương thức hoạt động preemptive và
non-preemptive
z Các thuật toán lập lịch FCFS, SJF, ưu tiên, 
RR
z Lập lịch với hàng chờ đa mức, có và không
có phản hồi
z Các phương pháp đánh giá thuật toán lập
lịch
47
Bài tập
z Thực hiện ví dụ RR với lượng tử thời gian
2ms, 6ms và 6ms. 
z Tính thời gian chờ trung bình của các tiến trình
trong các trường hợp này. 
z Khi lượng tử thời gian thay đổi, thời gian chờ
trung bình thay đổi thế nào?
z Tính thời gian hoàn thành (turnaround time) của
tất cả các tiến trình trong các trường hợp trên
z Nhận xét về sự thay đổi thời gian hoàn thành của
các tiến trình khi lượng tử thời gian thay đổi
48
Bài tập
z Hãy xây dựng một ví dụ về hiện tượng convoy 
effect sao cho thời gian rỗi của thiết bị vào ra
ít hơn thời gian rỗi của CPU. Giả sử có 4 tiến
trình, trong đó P là tiến trình “lớn”, Q1, Q2, Q3
là các tiến trình “nhỏ” được nằm trong hàng
chờ theo thứ tự: P, Q1, Q2, Q3
z Tìm hai ví dụ trong thực tế về hàng chờ đa
mức và hàng chờ đa mức có phản hồi và giải
thích các ví dụ này.