Bài giảng Lập lịch biểu cpu cpuscheduling
Mô hình quyếtđịnh: lấymộtkhốicôngviệcđịnh trướcđặcbiệtvàxác định hiệunăng củamỗithuật toánđốivớikhốicôngviệc Mô hình xếp hàng Thựcthi
Bạn đang xem trước 20 trang tài liệu Bài giảng Lập lịch biểu cpu cpuscheduling, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CHƯƠNG 4: LẬP LỊCH BIỂU CPU
CPU Scheduling
5.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
NỘI DUNG
Các khái niệm cơ sở
Các tiêu chuẩn lập lịch biểu
Các thuật toán lập lịch biểu
Lập lịch biểu đa processors
Lập lịch biểu thời gian thực (Real-Time Scheduling)
Các ví dụ HĐH
Đánh giá thuật toán
5.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
CÁC KHÁI NIỆM CƠ SỞ
Sử dụng CPU cực đại nhận được bởi đa chương
Chu kỳ CPU-I/O (CPU–I/O Burst Cycle) – sự thực hiện quá trình
gồm chu kỳ thực hiện CPU và chờ I/O
Sự phân tán CPU burst
5.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
DÃY LUÂN PHIÊN CÁC CHU KỲ CPU VÀ CHU
KỲ I/O
5.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
BIỂU ĐỒ THỜI GIAN CHU KỲ CPU
5.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
BỘ ĐỊNH THỜI CPU
Chọn trong các quá trình sẵn sàng một quá trình và cấp CPU cho
nó
Quyết dịnh lập lịch biểu CPU xảy ra khi một quá trình :
1. Chuyển từ trạng thái running sang trạng thái waiting
2. Chuyển từ trạng thái running sang trạng thái ready
3. Chuyển từ trạng thái waiting sang trạng thái ready
4. Kết thúc
Lập lịch biểu cho 1 và 4 là không trưng dụng (nonpreemptive)
Lập lịch biểu còn lại là trưng dụng (preemptive)
5.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
BỘ ĐIỀU VẬN
Module điều vận chuyển điều khiển CPU cho quá trình được chọn
bởi bộ định thời ngắn hạn, bao gồm:
z Chuyển ngữ cảnh
z Chuyển sang phương thúc user
z Nhảy đến vị trí đúng trong chương trình người dùng để bắt đầu
lại chương trình này
Tiềm ẩn điều vận (Dispatch latency) – thời gian bộ điều vận ngưng
một quá trình và khởi động một quá trình khác
5.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
CÁC TIÊU CHUẨN LẬP LỊCH BIỂU
Sự sử dụng CPU: Làm cho CPU bận rộn như có thể
Năng lực truyền qua (throughput): số quá trình hoàn tất sự
thực hiện của chúng trong một đơn vị thời gian
Thời gian quay vòng (Turnaround time) – lượng thời gian
thực hiện một quá trình
Thời gian chờ (Waiting time) – lượng thời gian một quá
trình phải chờ trong hàng đợi ready
Thời gian đáp ứng (Response time) – lượng thời gian từ
khi một yêu cầu được đệ trình đến khi đáp ứng đầu tiên
được sinh ra
5.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005
CÁC TIÊU CHUẨN TỐI ƯU
Max sự sử dụng CPU
Max throughput
Min turnaround 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
Các file đính kèm theo tài liệu này:
- ch4_cpu_scheduling_7652.pdf