Bài giảng Hệ điều hành - Chương 4: Lập lịch biểu CPU (CPU Scheduling)

time 
„ Min waiting time 
„ Min response time
5.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
First-Come, First-Served (FCFS)
Process Burst Time
P1 24
P2 3
P3 3
„ Giả sử các quá trình đến theo thứ tự: P1 , P2 , P3 
Biểu đồ Gantt cho lịch biểu:
„ Waiting time: đối với P1 = 0; P2 = 24; P3 = 27
„ Waiting time trung bình: (0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 300
5.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
FCFS (Cont.)
Giả sử các quá trình đến theo thứ tự:
P2 , P3 , P1
„ Biểu đồ Gantt cho lịch biểu:
„ Waiting time đối với P1 = 6; P2 = 0; P3 = 3
„ Average waiting time: (6 + 0 + 3)/3 = 3
„ Tốt hơn nhiều so với trường hợp trước
„ Hiệu ứng đoàn xe: quá trình ngắn đi sau quá trình dài
P1P3P2
63 300
5.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
Shortest-Job-First (SJF)
„ Kết hợp với mỗi quá trình độ dài chu kỳ CPU của nó. Sử dụng các
độ dài này để lập lịch biểu quá trình với thời gian ngắn nhất
„ Hai sơ đồ: 
z Không trưng dụng: mỗi khi CPU được gán cho một quá trình, 
nó không bị trưng dụng đến tận khi hoàn tất chu kỳ CPU của
nó
z Trưng dụng: Nếu một quá trình mới đến có chu kỳ CPU ngắn
hơn thời gian còn lại của quá trình đang thực hiện, trưng dụng
CPU của quá trình đang thực hiện, cấp CPU cho quá trình mới
đến. Sơ đồ này được biết dưới tên: 
Shortest-Remaining-Time-First (SRTF)
„ SJF là tối ưu với nghĩa nó cho thời gian chờ trung bình cực tiểu đối
với tập đã cho các quá trình
5.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
„ SJF không trưng dụng
„ Thời gian chờ trung bình = (0 + 6 + 3 + 7)/4 = 4
VÍ DỤ SJF KHÔNG TRƯNG DỤNG
P1 P3 P2
73 160
P4
8 12
5.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
VÍ DỤ SJF TRƯNG DỤNG
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
„ SJF trưng dụng
„ Thời gian chờ trung bình = (9 + 1 + 0 +2)/4 = 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
5.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
XÁC ĐỊNH ĐỘ DÀI CHU KỲ CPU KẾ TIẾP
„ Chỉ có thể ước lượng độ dài
„ Sử dụng độ dài cùa các chu kỳ CPU trước đó, ước lượng độ dài
chu kỳ CPU kế tiếp theo trung bình mũ:
- tn = độ dài chu kỳ CPU thứ n
- τn = độ dài ước lượng chu kỳ CPU thứ n
- α: 0 ≤ α ≤ 1
- độ dài ước lượng chu kỳ CPU thứ n+1 được xác định:
( ) .1 1 nnn t ταατ −+=+
5.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
TIÊN ĐOÁN ĐỘ DÀI CHU KỲ CPU KẾ TIẾP
5.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
VÍ DỤ TRUNG BÌNH MŨ
„ α =0
z τn+1 = τn
z Lịch sử gần không được tính đến
„ α =1
z τn+1 = tn
z Chỉ chu kỳ CPU hiện tại được tính đến
„ Triển khai công thức, ta được:
τn+1 = α tn+(1 - α)α tn -1 + …
+(1 - α )jα tn -j + …
+(1 - α )n +1 τ0
5.18 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
LẬP LỊCH BIỂU ƯU TIÊN
„ Mỗi quá trình được gán cho một số ưu tiên (một số nguyên)
„ CPU được cấp cho quá trình với độ ưu tiên cao nhất (thông
thường số ưu tiên nhỏ = độ ưu tiên cao)
z Trưng dụng
z Không trưng dụng
„ SJF là lập lịch biểu ưu tiên trong đó quá trình có chu kỳ CPU tiên
đoán ngắn nhất có độ ưu tiên cao nhất
„ Vấn đề: Sự chết đói – quá trình có độ ưu tiên thấp nhất có thể
không bao giờ được thực hiện
„ Giải pháp: tăng độ ưu tiên cho quá trình theo thời gian
5.19 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
Round Robin (RR)
„ Mỗi quá trình nhận được một đơn vị thời gian (nhỏ) - time 
quantum , thông thường 10-100 milliseconds. Sau khoảng thời
gian này, quá trình bị lấy lại CPU và được đưa vào cuối hàng
đợi sẵn sàng.
„ Nếu có n quá trình trong hàng đợi sẵn sàng, time quantum là q, 
khi đó thời gian chờ của mỗi quá trình không quá (n-1)q.
„ Hiệu năng
z q lớn⇒ FIFO
z q nhỏ⇒ tổng phí chuyển ngữ cảnh cao⇒ q phải đủ lớn
5.20 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
VÍ DỤ RR với Time Quantum = 20
Process Burst Time
P1 53
P2 17
P3 68
P4 24
„ Biểu đồ Gantt: 
„ Thông thường, So với SJF, thời gian quay vòng trung bình của RR 
cao hơn, nhưng thời gian đáp ứng trung bình của RR tốt hơn
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
5.21 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
TIME QUANTUM VÀ THỜI GIAN CHUYỂN 
NGỮ CẢNH
5.22 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
THỜI GIAN QUAY VÒNG VỚI TIME QUANTUM
5.23 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
HÀNG ĐỢI ĐA MỨC
„ Hàng đợi sẵn sàng được phân hoạch thành một các hàng đợi:
foreground (interactive)
background (batch)
„ Mỗi hàng đợi có thuật toán lập lịch biểu riêng của nó
z foreground – RR
z background – FCFS
„ Lập lịch biểu được làm giữa các hàng đợi
z Lập lịch biểu ưu tiên cố định (phục vụ tất cả quá trình trong
foreground sau đó mới đến các quá trình trong background). 
Có thể gây nên chết đói.
z Lát thời gian: mỗi hàng đợi nhận một lượng thời gian CPU nhất
định để lập lịch biểu cho các quá trình của nó (ví dụ 80% thời
gian cho hàng đợi foreground với RR, 20% cho background với
FCFS) 
5.24 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
LẬP LỊCH BIỂU HÀNG ĐỢI ĐA MỨC
5.25 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
HÀNG ĐỢI PHẢN HỒI ĐA MỨC
„ Mỗi quá trình có thể di chuyển giữa các hàng đợi
„ Bộ lập lịch biểu hàng đợi phản hồi đa mức được xác định bởi các
tham số sau:
z Số hàng đợi
z Các thuật toán lập lịch biểu cho mỗi hàng đợi
z Phương pháp xác định khi nào nâng cấp quá trình
z Phương pháp xác định khi nào hạ cấp quá trình
z Phương pháp xác định hàng đợi một quá trình sẽ được đặt vào
khi quá trình cần sự phục vụ
5.26 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
VÍ DỤ HÀNG ĐỢI PHẢN HỒI ĐA MỨC
„ Ba hàng đợi: 
z Q0 – RR với time quantum 8 milliseconds
z Q1 – RR với time quantum 16 milliseconds
z Q2 – FCFS
„ Lập lịch biểu
z Một công việc mới được sắp vào hàng đợi Q0, ở đó nó được
lập lịch biểu RR với time quantum = 8 miliseconds, nếu quá
trình chua kết thúc sau 8 miliseconds, nó được chuyển sang 
hàng đợi Q1
z Trong Q1 công việc được phục vụ theo RR với time quantum 
16 miliseconds. Nếu nó vẫn chua hoàn tất, nó sẽ được chuyển
sang Q2
z Trong Q2 quá trình được lập lịch biểu FCFS
5.27 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
CÁC HÀNG ĐỢI PHẢN HỒI ĐA MỨC
5.28 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
LẬP LỊCH BIỂU ĐA Processors
„ Phức tạp hơn
„ Các processors thuần nhất
„ Chia sẻ nạp
„ Đa xử lý phi đối xứng – chỉ một processor truy xuất các
cấu trúc dữ liệu hệ thống làm giảm nhẹ sự cần thiết chia
sẻ dữ liệu
5.29 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
LẬP LỊCH BIỂU THỜI GIAN THỰC
„ Các hệ thời gian thực cứng (Hard real-time systems): 
đòi hỏi hoàn tất một nhiệm vụ khẩn cấp trong một
lượng thời gian xác định
„ Tính toán thời gian thực mềm (Soft real-time
computing): – Đòi hỏi các quá trình khẩn cấp nhận
được ưu tiên trên các quá trình khác
5.30 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
CÁC VÍ DỤ HĐH
„ Solaris scheduling
„ Windows XP scheduling
„ Linux scheduling
5.31 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
LẬP LỊCH BIỂU Solaris 2
5.32 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
BẢNG ĐIỀU VẬN Solaris
5.33 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
CÁC ƯU TIÊN Windows XP
5.34 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
LẬP LỊCH BIỂU Linux
„ Hai thuật toán: time-sharing và real-time
„ Time-sharing
z Ừu tiên dựa trên tín dụng: quá trình với tín dụng cao nhất được
chọn kế tiếp
z Tín dụng bị trừ khi ngắt đồng hồ xảy ra
z Khi tín dụng = 0, quá trình khác được chọn
z Khi tất cả các quá trình có tín dụng = 0, lập lại tín dụng
 Dựa trên các nhân tố bao gồm độ ưu tiên và lịch sử
„ Real-time
z Real-time mềm
z Posix.1b compliant – hai lớp
 FCFS và RR
Quá trình độ ưu tiên cao nhất luôn chạy đầu tiên
5.35 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
QUAN HỆ GIỮA ĐỘ ƯU TIÊN VÀ ĐỘ DÀI LÁT THỜI GIAN
5.36 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
DANH SÁCH CÁC NHIỆM VỤ ĐƯỢC CHỈ SỐ 
TƯƠNG ỨNG VỚI ĐỘ ƯU TIÊN
5.37 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
ĐÁNH GIÁ THUẬT TOÁN
„ Mô hình quyết định: lấy một khối công việc định trước đặc biệt và xác
định hiệu năng của mỗi thuật toán đối với khối công việc
„ Mô hình xếp hàng
„ Thực thi
5.38 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
5.15
End of Chapter 5
5.40 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
5.08
5.41 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
In-5.7
5.42 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
In-5.8
5.43 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
In-5.9
5.44 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
Dispatch Latency