Bài giảng Lập lịch cho cpu

Chương III LẬP LỊCH CHO CPU Mục tiêu Giúp sinh viên nắm được tầm quan trọng của “giờ CPU”, các phương pháp, các thuật toán lập lịch ccho CPU của hệ điều hành nhằm đáp ứng yêu cầu phục vụ của các tiến trình. Biết được công cụ để CPU có thể điều khiển hoạt động của các tiến trình một cách chính xác. Nội dung Các khái niệm về giờ CPU. Các thuật toán lập lịch cho CPU. Khái niệm về ngắt và phương pháp xử lý ngắt của hệ điều hành. I. CÁC KHÁI NIỆM CƠ BẢN I.1. Khái niệm giờ CPU Thời gian mà CPU phục vụ cho tiến trình gọi là giờ CPU. Mỗi thời điểm nhất định, chỉ có một tiến trình được phân phối giờ CPU để hoạt động. I.2. Khái niệm lập lịch cho CPU Hệ thống thường tổ chức các từ trạng thái để ghi nhận tình trạng sử dụng tài nguyên và trạng thái tiến trình. Các từ trạng thái được tổ chức như sau: I.2. Khái niệm lập lịch cho CPU Lập lịch cho CPU là tổ chức một hàng đợi các tiến trình sẵn sàng để phân phối giờ CPU cho chúng dựa trên độ ưu tiên của các tiến trình sao cho hiệu suất sử dụng CPU là tối ưu nhất. Mỗi tiến trình ở trạng thái sẵn sàng được gắn một thứ tự ưu tiên dựa vào các yếu tố sau: Thời điểm hình thành tiến trình, thời gian thực hiện tiến trình, thời gian kết thúc tiến trình. I.3. Các phương pháp lập lịch và yếu tố đánh giá Các phương pháp lập lịch thường được áp dụng là: Long-term Scheduler: Áp dụng với những tiến trình đã được lập danh sách và Spool. Short-term Scheduler: Áp dụng với nhứng tiến trình mà mã nguồn của nó đã được đẩy vào bộ nhớ trong. I.3. Các phương pháp lập lịch và yếu tố đánh giá Các yếu tố để đánh giá các PP lập lịch: Sự công bằng CPU: Dù đến sớm hay muộn, tiến trình đều phải được phân phối giờ CPU. Tận dựng giờ CPU: TG vô ích càng ít càng tốt Tổng TG thực hiện tiến trình: Thời gian tiến trình chờ được xử lý: Thời gian đáp ứng: Tính từ khi có yêu cầu giờ CPU đến khi được đáp ứng. II. Các Thuật toán lập lịchII.1. First Come First Served (FCFS) Mọi tiến trình được phục vụ theo trình tự xuất hiện cho đến khí nó kết thúc hoặc bị ngắt. Ưu điểm: Giờ CPU không bị phân phối lại, chi phí tổ chức thực hiện thấp. Nhược điểm: Thời gian trung bình chờ phục vụ của các tiến trình là như nhau. Do đó: Thời gian trung bình sẽ tăng vô hạn, độ phát tán thời gian thực hiện tiến trình tăng thì TG chờ trung bình tăng, khi có tiến trình dài tiến trình khác phải chờ lâu hơn. Ví dụ Thời gian trung bình phải chờ là 51/3=17 II.2. Shortest Job First (SJF) Tiến trình nào tổng thời gian thực hiện ngắn hơn sẽ được phụ vụ trước. TG chờ trung bình là 9/3=3 II.2. Shortest Job First (SJF) Ưu điểm: TG chờ TB ngắn, nhanh chóng loại bỏ các tiến trình ngắn-> số lượng tiến trình trong hàng đợi ít. Nhược điểm: Phải thực hiện phân phối lại giờ CPU khi có một tiến trình mới xuất hiện ngắn hơn tiến trình dang thực hiện. II.3. Shortest Remain Time (SRT) Dựa vào thời gian để thực hiện nốt tiến trình, TG này=Tổng thời gian thực hiện tiến trình – TG đã thực hiện. TG thực hiện nốt tiến trình ngắn nhất sẽ dược phục vụ trước. Do vậy phải thường xuyên cập nhập thời gian thực hiện tiến trình và phân bổ lại giờ CPU. II.4. Round Robin (RR) Mỗi tiến trình được phân bố một lượng thời gian thực hiện (time quantum). Sau khoảng thời gian đó, nếu tiến trình chưa kết thúc thì nó được chuyển về cuối hàng đợi. Hàng đợi của các tiến trình được tổ chức theo vòng tròn và các tiến trình luôn đảm bảo được phục vụ. Nếu tiến trình mới được hình thành, nó được đưa vào hàng đợi ở vị trí được phục vụ ngay. Các tiến trình đều có đồ ưu tiên như nhau. II.4. Round Robin (RR) Ưu điểm: Cho phép hệ thống ưu tiên những tiến trình ngắn nhưng không gây tổn hại cho các tiến trình dài. Nhược điểm: Thường xuyên phải phân phối lại giờ CPU, do vậy thời gian chờ trung bình lớn. Ví dụ TG chờ TB=17/3=5,66 II.5. Multi Level Queue (MLQ) Dựa vào thông tin do người sử dụng cung cấp và kết quả phân tích của hệ thống để phân chia độ ưu tiên cho các tiến trình. II.5. Multi Level Queue (MLQ) Trên thực tế, cách tổ chức 2 hàng đợi được sử dụng phổ biến: Một cho các tiến trình trao đổi vào ra nhiều Một cho các tiến trình thực hiện tính toán nhiều. Các tiến trình ở hàng đợi thứ nhất được ưu tiên cao hơn vì phải chờ kết quả I/O nêu không sử dụng hết hiệu suất giờ CPU. II.6. Multi Level Feedback Queues(MLFQ) Hệ thống tổ chức nhiều hàng đợi. Mỗi hàng có độ ưu tiên và cách thức tổ chức thực hiện khác nhau. Các TT có thể chuyển đổi từ hàng đợi này sang hàng khác. II.6. Multi Level Feedback Queues(MLFQ) Các yếu tố cần chú ý: Số lượng hàng đợi sao cho hợp lý. Chọn thuật toán thích hợp cho mỗi hàng đợi. Tiêu chuẩn và cách thức hạ mức một tiến trình. Tiêu chuẩn và cách thức nâng mức một tiến trình. Tiêu chuẩn và cách thức chỉ định một tiến trình mới phát sinh vào hàng đợi nào. III. Ngắt