Bài giảng Lập trình hệ điều hành: Chương 4 - Hà Duy Anh

Bài giảng "Lập trình 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ật. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Lập trình hệ điều hành: Chương 4 - Hà Duy AnhKhoa 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 CPU1. Các khái niệm2. Các giải thuật định thời3. Định thời trong hệ thống có nhiều bộ xử lý4. Đánh giá giải thuật9/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ợp9/19/2013 4 Chương 4: Định thời CPU9/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ác9/19/2013 7 Chương 4: Định thời CPU1. 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ểu9/19/2013 9 Chương 4: Định thời CPU1. First-Come, First-Served2. Shortest-Job-First3. Priority4. Round-Robin5. Hàng đợi đa cấp6. Hàng đợi phản hồi đa cấp9/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 = 179/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ấ ...