Lý thuyết hệ điều hành - Chương 3

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

219
lượt xem 35
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài toán định thời Các thuật ngữ Mục tiêu định thời Tiêu chí để định thời Tiêu chuẩn đánh gia Các giải thuật định thời. Định thời hạn chót FIFO SJF, SRT RR HRRN Hàng đa mức hồi tiếp.Phân chia thời gian thực thi cho các quá trình đồng thời trong hệ thống sao cho các quá trình kết thúc và kết thúc nhanh nhất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lý thuyết hệ điều hành - Chương 3

Chương 3 ĐỊNH THỜI BỘ XỬ LÝ Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. -1- HCM
CHƯƠNG 3 : ĐỊNH THỜI BỘ XỬ LÝ Bài toán định thời  Các thuật ngữ  Mục tiêu định thời  Tiêu chí để định thời  Tiêu chuẩn đánh gia  Các giải thuật định thời  Định thời hạn chót – FIFO – SJF, SRT – RR – HRRN – Hàng đa mức hồi tiếp – Bài tập  -2- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
BÀI TOÁN ĐỊNH THỜI Định nghĩa :  Phân chia thời gian thực thi cho các quá trình đồng – thời trong hệ thống sao cho các quá trình kết thúc và kết thúc nhanh nhất. Cấp độ định thời  Cấp cao (high-level) – Cấp trung (intermediate-level) – Cấp thấp (low-level) – -3- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
CÁC THUẬT NGỮ  CPU burst  I/O burst  Time slice / Quantum  Interval Timer  Các kiểu định thời non-preemptive – preemptive – -4- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
MỤC TIÊU ĐỊNH THỜI Công bằng 1. Tăng hiệu suất tối đa 2. Cực đại số người dùng tương tác 3. Có thể dự đoán trước 4. Phí tổn ít 5. Cân đối việc sử dụng tài nguyên 6. Tránh trì hoãn vô hạn định (dùng độ ưu tiên) 7. Ưu tiên quá trình giữ tài nguyên quan trọng 8. Phục vụ tốt các quá trình có hướng thuận lợi 9. Điều phối tối ưu khi tải không cân đối 10. -5- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
TIÊU CHÍ ĐỂ ĐỊNH THỜI Mức độ dùng I/O (I/O boundness) 1. Mức độ dùng CPU (CPU boundness) 2. Đặc tính quá trình : batch, interactive,real-time… 3. Độ khẩn cấp của quá trình 4. Độ ưu tiên của quá trình 5. Tần suất gây lỗi tham khảo trang (page fault) 6. Tần suất bị giành CPU 7. Thời gian được CPU phục vụ từ khi tạo ra 8. Thời gian chạy còn lại của quá trình 9. -6- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
TIÊU CHUẨN ĐÁNH GIÁ GIẢI THUẬT ĐỊNH THỜI Độ lợi CPU (CPU utilization) 1. Thông lượng (throughput) 2. Thời gian xử lý (turnaround time) 3. Thời gian đợi (waiting time) 4. Thời gian đáp ứng (response time) 5. -7- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
BỘ ĐỊNH THỜI VÀ BỘ ĐIỀU VẬN Bộ định thời quá trình (scheduler)  Chọn lựa quá trình cho CPU phục vụ – Hoạt động vào những thời điểm – 1. Khi quá trình running  ready 2. Khi quá trình từ running  blocked 3. Khi quá trình từ blocked  ready 4. Khi có quá trình kết thúc Bộ điều vận (dispatcher)  Chuyển điều khiển CPU sang cho quá trình. – Thực hiện bước chuyển ngữ cảnh: – Chuyển ngữ cảnh sang cấp người dùng  Nhảy sang vị trí thích hợp của quá trình và thực thi  -8- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
BỘ ĐỊNH THỜI QUÁ TRÌNH Low-level scheduler High-level scheduler enter end JOB QUEUE CPU READY QUEUE I/O WAITING QUEUE -9- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
MỘT SỐ GIẢI THUẬT ĐỊNH THỜI Định thời hạn chót (Deadline Scheduling) 1. FIFO (First In First Out) 2. SJF (Shortest Job First) 3. SRT (Shortest Remaining Time) 4. RR (Round Robin) 5. HRRN (Highest Response Ratio Next) 6. Hàng đa mức hồi tiếp 7. (Multilevel Feedback Queue) -10- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
ĐỊNH THỜI HẠN CHÓT (Deadline Scheduling) Còn gọi là real-time scheduling  Hard real-time – Soft real-time – Định thời sao cho các quá trình được thực thi theo một  bảng thời gian xác định trước Mục đích : hoàn thành tác vụ kịp lúc  Ứng dụng : công nghiệp, viễn thông, quân sự…  Rất phức tạp  Chỉ có giải thuật cho từng hệ thống cụ thể  -11- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
FIFO (First In First Out) Còn gọi là FCFS (First Come First Served)   Xét định thời quá trình theo thời gian đến hàng đợi ready của quá trình  Quá trình vào trước sẽ được phục vụ trước  Định thời theo kiểu non-preemptive Processor -12- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ 1 : GIẢI THUẬT FIFO Thời gian thực thi (giây) Quá trình Thứ tự đến  P1, P2, P3 P1 24  Thứ tự thực hiện P2 5 P1 P2  P3 P3 2 P1 P2 P3 0 24 31 29 -13- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ 1 : GIẢI THUẬT FIFO Thời gian xử lý (turnaround time)  P1: 24s P2: 29s P3: 31s Thời gian xử lý trung bình  (24+29+31)/3 = 28s Thời gian đợi (waiting time)  P1: 0s P2: 24s P3: 29s Thời gian đợi trung bình  (0+24+29)/3=17.67s Nếu thứ tự đến các quá trình là P3  P2  P1 thì sao ?  Nhận xét  -14- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
SJF (Shortest Job First ) Định thời theo kiểu non-premptive  Quá trình có thời gian xử lý nhỏ nhất sẽ được xử lý  trước Việc định thời được thực hiện sau khi có quá trình  kết thúc Min time Processor -15- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ 2 : GIẢI THUẬT SJF Định thời  P1P3P2 Thời gian đến Thời gian thực thi Quá trình (giây) P1 0 7 Tính các thông số ?  P2 1 4 P3 5 2 Định thời lại So sánh với  P1 P2 P3 định thời theo FIFO ? P1 P3 P2 Nhược điểm ? 0 7 9 13  -16- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
SRT (Shortest Remaining Time) Định thời theo kiểu pre-emptive  Quá trình có thời gian xử lý còn lại nhỏ nhất sẽ được  xử lý trước Việc định thời được thực hiện ngay cả khi có quá  trình đến hệ thống Min remaining time Processor -17- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ 3 : GIẢI THUẬT SRT Định thời :  P1P2P3P1 Thời gian đến Thời gian thực thi Quá trình (giây) P1 0 7 Tính các thông số ?  P2 3 2 P3 5 2 So sánh với SJF ?  Định thời lại P1 P2 P3 P1 P2 P3 P1 Nhược điểm ?  -18- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
RR(Round Robin) Định thời theo kiểu pre-emptive  Quá trình chỉ được chiếm CPU trong khoảng thời gian  q (quantum time). Nếu trong khoảng thời gian đó quá trình chưa kết thúc thì nó trả CPU lại cho Hệ điều hành và quay về cuối hàng đợi Ready. q Processor -19- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ 4 : GIẢI THUẬT RR Tính các thông số ?  Thời gian đến Thời gian thực thi Quá trình Cho t_switch = 0 (giây) P1 0 7 P2 3 2 Nhận xét  P3 5 2 P1 P2 P3 0 3 5 7 Định thời Round robin với Quantum time là 1 giây -20- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM