Xem mẫu
- TRƯỜNG ĐH ĐỒNG THÁP
KHOA SP TOÁN - TIN
Bài giảng
ĐIỀU ĐỘ CÁC TIẾN TRÌNH
Gỉang viên : Nguyễn Thị Thùy Linh
Email: nttlinh@dthu.edu.vn
- NỘI DUNG
1. Các khái niệm.
2. Tiêu chí cho việc lập lịch biểu.
3. Các giải thuật lập lịch biểu.
4. Lập lịch biểu đa xử lý.
5. Lập lịch biểu thời gian thực.
6. Đánh giá giải thuật.
2
- Các khái niệm
Kỹ thuật đa chương giúp cho việc sử dụng CPU đạt
hiệu năng cao nhất.
Chu kỳ CPU + chờ đợi I/O, sự thực thi của 1 quá
trình bao gồm một chu kỳ là: sử dụng CPU để thực thi
và chờ đợi I/O.
Sự phân bố sử dụng CPU.
3
- Bộ định thời CPU
Chọn một trong số các quá trình sẵn sàng trong bộ
nhớ và giao CPU cho nó thực thi.
Quyết định lập lịch biểu cho CPU diễn ra khi một quá
trình:
Chuyển từ trạng thái Running sang trạng thái Waiting.
Chuyển từ trạng thái Running sang trạng thái Ready.
Chuyển từ trạng thái Waiting sang trạng thái Ready.
Kết thúc
Việc lập lịch biểu theo kiểu như trên được gọi là
không ưu tiên.
Tất cả giải pháp lập lịch biểu khác gọi là có ưu tiên 4
- Dispatcher
Module dispatcher giao cho CPU một quá trình được
chọn ra bởi bộ lập lịch biểu ngắn kỳ, bao gồm:
Chuyển ngữ cảnh.
Chuyển sang chế độ người dùng
Nhảy tới vị trí của chương trình người dùng để khởi động
lại chương trình đó.
Độ trễ dispatch, là thời gian một dispatcher bỏ ra để
ngưng một quá trình và khởi động một quá trình khác
5
- Dispatcher (tt)
6
- Tiêu chí cho việc lập lịch biểu
Hiệu suất sử dụng CPU, nghĩa là giữ CPU luôn bận
rộn nếu có thể.
Năng lực truyền qua (Throughput), là số lượng quá
trình hoàn thành việc thực thi trên mỗi đơn vị thời gian
Thời gian xoay vòng (hoàn lại,hòan thành) –
Turnaround time, là lượng thời gian thực thi một quá
trình=Thời gian chờ đợi để được tải vào bộ nhớ +
Chờ đợi trong hàng đợi sẵn sàng +
Thực thi bởi CPU và thao tác vào ra
Thời gian chờ đợi: lượng thời gian một tiến trình đã
bỏ ra khi nằm trong hàng đợi sẵn sàng 7
- Tiêu chí cho việc lập lịch biểu (tt)
Thời gian đáp ứng: lượng thời gian từ lúc một yêu
cầu được đệ trình cho đến khi tín hiệu trả lời đầu tiên
được sản sinh (môi trường chia thời gian).
8
- Tiêu chí tối ưu hóa
Hiệu suất sử dụng CPU tối đa.
Năng lực truyền qua tối đa.
Thời gian xoay vòng tối thiểu.
Thời gian chờ đợi tối thiểu.
Thời gian đáp ứng tối thiểu.
9
- Giải thuật First – Come, First – Served (FCFS)
Process Thg sử dụng CPU
(ms)
P1 24
P2 3
P3 3
Giả sử các quá trình xuất hiện theo thứ tự: P1, P2, P3,
biểu đồ Gantt cho việc sắp lịch biểu là
P1 P2 P3
0 24 27 30
Thời gian chờ của P1 = 0ms, P2 = 24ms, P3 = 27ms
Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17ms 10
- Giải thuật FCFS (tt)
Giả sử các quá trình xuất hiện theo thứ tự: P2, P3, P1,
biểu đồ Gantt cho việc sắp lịch biểu là
P2 P3 P1
0 3 6 30
Thời gian chờ của P1 =6ms, P2 = 0ms, P3 = 3ms
Cải thiện được đáng kể so với trường hợp trước
Tránh “tác động nối đuôi”: quá trình ngắn nằm sau
quá trình dài
11
- Giải thuật Shortest – Job – First (SJF)
Kết hợp với mỗi quá trình độ dài thời gian mà nó sẽ sử dụng
CPU lần kế tiếp. Sử dụng độ dài này để lập lịch trình cho quá
trình với thời gian ngắn nhất.
Có hai phương thức thực hiện giải thuật:
Không trưng dụng (độc quyền): một CPU khi được giao
cho một quá trình, nó không thể bị lấy lại để giao cho quá
trình khác có thời gian ngắn hơn (ưu tiên hơn) đến khi quá
trình này sử dụng CPU xong.
Trưng dụng (không độc quyền): nếu một quá trình mới
đến có thời gian sử dụng CPU ngắn hơn thời gian thực
hiện còn lại của quá trình đang thực hiện (có độ ưu tiên cao
hơn), thì giao CPU cho quá trình mới đến.
SJF là tối ưu nhất vì nó tạo ra thời gian chờ đợi trung bình12
ngắn nhất.
- Giải thuật SJF không trưng dụng
Process Thời điểm đến Thg sử dụng
CPU(ms)
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
Theo SJF (không trưng dụng)
P1 P3 P2 P4
0 7 8 12 16
Thời gian chờ đợi trung bình: (0 + 6 + 3 + 7)/4 = 4ms
13
- Giải thuật SJF có trưng dụng
Process Thời điểm đến Thg sử dụng
CPU(ms)
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
Theo SJF có trưng dụng
P1 P2 P3 P2 P4 P1
0 2 4 5 7 11 16
Thời gian chờ đợi trung bình:
((0 + 9) + (0 + 1) + 0 + 2) / 4 = 3ms 14
- Xác định độ dài thời gian sử dụng CPU kế tiếp
Chỉ có thể ước lượng độ dài.
Độ dài ước lượng được tính dựa trên độ dài thời gian sử dụng CPU
lần trước đó, theo công thức TB số mũ:
1. tn là thời gian sử dụng CPU thực tế lần thứ n.
2. T n + 1 là thời gian sử dụng CPU lần thứ n + 1
3. , 0
- Lập lịch biểu theo kiểu có ưu tiên
Một chỉ số ưu tiên được gán cho mỗi quá trình.
CPU sẽ được cấp cho quá trình nào có độ ưu tiên
cao nhất (nghĩa là có chỉ số ưu tiên thấp nhất). Cách
này có thể sử dụng hình thức: Trưng dụng hoặc không
Trưng dụng.
SJF là kiểu lập lịch biểu có ưu tiên, nơi mà độ ưu
tiên là thời gian ước tính sử dụng CPU lần trước đó.
Vấn đề Statvation (chết đói) sẽ xảy ra đối với những
quá trình có độ ưu tiên thấp.
Giải pháp: đặt thời hạn cho quá trình, khi thời hạn
trôi đi thì độ ưu tiên cũng tăng theo. 16
- Giải thuật ưu tiên không trưng dụng
Process Thời điểm đến Thg sử dụng ưu tiên
CPU(ms)
P1 0.0 7 2
P2 2.0 4 1
P3 4.0 1 3
P4 5.0 4 1
Theo u tien (ưu tiên không trưng dụng)
P1 P2 P4 P3
0 7 11 15 16
Thời gian chờ đợi trung bình = (0+5+11+6)/4=5,5ms
17
- Giải thuật Ưư tiên trưng dụng
Process Thời điểm đến Thg sử dụng ưu tiên
CPU(ms)
P1 0.0 7 2
P2 2.0 4 1
P3 4.0 1 3
P4 5.0 4 1
Theo u tien (ưu tiên trưng dụng)
P1 P2 P4 P1 P3
0 2 6 10 15 16
Thời gian chờ đợi trung bình =(8+0+11+1)/4=5,0ms
18
- Giải thuật Round Robin (RR)
Mỗi quá trình sẽ được CPU phục vụ một đơn vị thời
gian nhỏ (thông thường là từ 10 – 100 ms). Sau
khoảng thời gian này CPU sẽ được giao cho quá trình
khác.
Nếu quá trình đang nằm trong hàng đợi Ready và
phổ thời gian của nó là q, thì mỗi quá trình sẽ nhận
được 1/n tổng thời gian của CPU, thời gian phục vụ
của CPU tối đa là q không có quá trình nào đợi quá
(n – 1)q.
Hiệu năng:
q lớn FIFO
q nhỏ q đủ lớn, do ta quan tâm đến thời gian chuyển 19
ngữ cảnh, nếu không thời gian phí tổn sẽ cao.
- Round Robin (tt)
Process Thời điểm đến Thg sử dụng CPU
P1 0.0 7
P2 3.0 14
P3 6.0 3
P1 P2 P3 P3 P1 P2
arrives arrives arrives terminates terminates terminates
P1 2 1 2 1 2 3 1 2 3 1 2 3 2
20
nguon tai.lieu . vn
