Bài giảng Hệ điều hành: Chương 4 - Hà Duy An (ĐH Cần Thơ)

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

63
lượt xem 7
download

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

Bài giảng "Hệ điều hành - Chương 4: Định thời CPU" cung cấp cho người học các kiến thức: Các khái niệm, các giải thuật định thời, định thời trong hệ thống có nhiều bộ xử lý, đánh giá giải thu. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Hệ điều hành: Chương 4 - Hà Duy An (ĐH Cần Thơ)

Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ Giảng viên: Hà Duy An 9/19/2013 1 Chương 4: Định thời CPU
1. Các khái niệm 2. Các giải thuật định thời 3. Định thời trong hệ thống có nhiều bộ xử lý 4. Đánh giá giải thuật 9/19/2013 2 Chương 4: Định thời CPU
• Kỹ thuật đa chương giúp việc sử dụng CPU đạt hiệu quả cao nhất. • Chu kỳ CPU-I/O o Sự thực thi của tiến trình bao gồm nhiều chu kỳ CPU-I/O o Một chu kỳ CPU-I/O bao gồm chu kỳ thực thi CPU (CPU burst) và theo sau bởi chu kỳ chờ đợi vào/ra (I/O burst). => Việc phân phối chu kỳ CPU-I/O là một đặt điểm quan trọng để chọn lựa giải thuật định thời phù hợp 9/19/2013 4 Chương 4: Định thời CPU
9/19/2013 5 Chương 4: Định thời CPU
• Bộ định thời CPU hay bộ định thời ngắn kỳ (Short-term scheduler) chọn một trong các tiến trình trong hàng đợi sẵn sàng và cấp phát CPU cho nó thực thi o Hàng đợi có thể được sắp xếp theo nhiều cách • Quyết định định thời xảy ra khi một tiến trình: 1. Chuyển từ trạng thái đang chạy sang trạng thái chờ đợi 2. Chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng 3. Chuyển từ trạng thái chờ đợi sang sẵn sàng 4. Kết thúc • Định thời không trưng dụng (nonpreemptive): tiến trình sẽ giữ CPU và chỉ giải phóng CPU khi nó cần (trường hợp 1 và 4) • Định thời trưng dụng (preempty): các trường hợp 2 và 3; Vấn đề: o Tiến trình đang cập nhật dữ liệu chia sẽ chung? o Tiến trình đang xử lý trong chế độ nhân (kernel mode)? o Không thể bỏ qua tất cả các ngắt? 9/19/2013 6 Chương 4: Định thời CPU
• Bộ điều phối (Dispatcher): Có nhiệm vụ trao quyền điều khiển CPU cho tiến trình được chọn bởi bộ định thời CPU, công việc này bao gồm: o Chuyển ngữ cảnh o Chuyển sang chế độ người dùng o Nhảy tới vị trí thích hợp trong chương trình người dùng để khởi động lại chương trình đó • Bộ điều phối cần nhanh nhất có thể. • Độ trễ điều phối (Dispatch Latency): thời gian Dispatcher cần để ngưng một tiến trình và khởi động một tiến trình khác 9/19/2013 7 Chương 4: Định thời CPU
1. Hiệu suất sử dụng CPU: giữ CPU luôn bận nhiều nhất có thể. 2. Thông lượng (Throughput): số lượng tiến trình hoàn thành trên một đơn vị thời gian. 3. Thời gian xoay vòng (Turnaround time): là khoảng thời gian từ khi một tiến trình được khởi tạo đến khi nó hoàn thành. Nó là tổng các khoảng thời gian chờ đợi để đưa vào bộ nhớ, chờ trong hàng đợi sẵn sàng, thời gian thực thi trên CPU và thực hiện các xử lý I/O. 4. Thời gian chờ đợi (Waiting time): tổng thời gian trong trong hàng đợi sẵn sàng (ready queue). 5. Thời gian đáp ứng (Response time): 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 xuất hiện (dùng cho môi trường chia thời gian). 9/19/2013 8 Chương 4: Định thời CPU
• Việc đánh giá giải thuật định thời được kiểm tra thông qua khả năng tối ưu hóa các tiêu chí đinh thời của nó: o Hiệu suất sử dụng CPU tối đa o Thông lượng tối đa o Thời gian xoay vòng tối thiểu o Thời gian chờ đợi tối thiểu o Thời gian đáp ứng tối thiểu 9/19/2013 9 Chương 4: Định thời CPU
1. First-Come, First-Served 2. Shortest-Job-First 3. Priority 4. Round-Robin 5. Hàng đợi đa cấp 6. Hàng đợi phản hồi đa cấp 9/19/2013 11 Chương 4: Định thời CPU
Tiến Trình TG sử dụng CPU P1 24 P2 3 P3 3 • Giả sử các tiến trình xuất hiện theo thứ tự P1, P2, P3. Biểu đồ Gantt cho lịch biểu là: P1 P2 P3 0 24 27 30 • Thời gian chờ đợi: P1 = 0; P2 = 24; P3 = 27 • Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17 9/19/2013 12 Chương 4: Định thời CPU
• Giả sử các tiến trình xuất hiện theo thứ tự P2, P3, P1. Biểu đồ Gantt cho lịch biểu là: P2 P3 P1 0 3 6 30 • Thời gian chờ đợi: P1= 6; P2 = 0; P3 = 3 • Thời gian chờ đợi trung bình: (6 + 0 + 3)/3 = 3 • Tốt hơn nhiều so với trường hợp trước. • Tác động nối đuôi: tiến trình ngắn nằm sau tiến trình dài. • FCFS là giải thuật định thời không trưng dụng, không thích hợp cho hệ thống chia thời gian. 9/19/2013 13 Chương 4: Định thời CPU
• Kết hợp với mỗi tiến trình độ dài thời gian mà nó sẽ sử dụng CPU lần kế tiếp. Khi CPU rãnh, nó sẽ được cấp cho tiến trình có thời gian sử dụng CPU lần kế tiếp ngắn nhất. • Có hai cách thức thực hiện giải thuật: o Không trưng dụng: một khi CPU được giao cho một tiến trình, nó không thể bị trưng dụng để giao cho tiến trình khác có thời gian ngắn hơn cho đến khi tiến trình này sử dụng CPU xong. o Trưng dụng: nếu một tiến trình mới đến có thời gian sử dụng CPU ngắn hơn thời gian thực thi còn lại của tiến trình đang chạy, thì ưu tiên giao CPU cho tiến trình mới đến. Cách thức này được gọi là Shortest-Remaining-Time-First (SRTF). • SJF là tối ưu – nó tạo ra thời gian chờ đợi trung bình ngắn nhất. 9/19/2013 14 Chương 4: Định thời CPU
Tiến trình TG đến TG sử dụng CPU P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (không trưng dụng) P1 P3 P2 P4 0 3 7 8 12 16 • Thời gian chờ đợi trung bình = (0 + 6 + 3 + 7)/4 = 4 9/19/2013 15 Chương 4: Định thời CPU
Tiến trình TG đến TG sử dụng CPU P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (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 = (9 + 1 + 0 +2)/4 = 3 • Bài Tập 9/19/2013 16 Chương 4: Định thời CPU
• Chỉ có thể ước lượng độ dài – có thể tương tự như lần sử dụng trước đó. • Độ dài ước lượng được tính toán dựa trên chiều dài thời gian sử dụng CPU lần trước đó, sử dụng công thức trung bình mũ: 1. t n  thôøi gian söû duïng CPU thöïc teá laàn thöù n 2.  n 1  öôùc löôïng thôøi gian söû duïng CPU laàn thöù n  1 3.  , 0    1 4. Ñònh nghóa :  n 1   t n  (1   ) n • Thông thường α = ½ 9/19/2013 17 Chương 4: Định thời CPU
9/19/2013 18 Chương 4: Định thời CPU
• α =0 o τn+1 = τn o Không tính đến thời gian sử dụng CPU gần nhất • α =1 o τn+1 = tn o Chỉ tính đến thời gian sử dụng CPU thực gần nhất • α =1/2, lịch sử quá khứ và gần đây có trọng số tương đương. • Nếu mở rộng công thức, ta có: τn+1 = α tn+(1 - α) α tn-1 + … +(1 - α )j+1 α tn-j + … +(1 - α )n+1τ0 • Vì α và (1- α) nhỏ hơn hay bằng 1, mỗi số hạng tiếp theo có trọng số nhỏ hơn số hạng trước đó. 9/19/2013 19 Chương 4: Định thời CPU
• Một chỉ số ưu tiên được gán cho mỗi tiến trình • CPU sẽ được cấp cho tiến trình có độ ưu tiên cao nhất, nghĩa là chỉ số ưu tiên nhỏ nhất (smallest integer ≡ highest priority). • Có thể trưng dụng hoặc không trưng dụng • SJF là một trường hợp của định thời ưu tiên, trong đó độ ưu tiên là thời gian ước tính sử dụng CPU lần kế tiếp. • Vấn đề đói CPU (starvation): các tiến trình có độ ưu tiên thấp có khả năng không bao giờ được thực thi. • Giải pháp: đặt thời hạn (aging) – khi thời gian trôi đi, độ ưu tiên của tiến trình càng tăng theo. 9/19/2013 20 Chương 4: Định thời CPU