Bài giảng Nguyên lý hệ điều hành: Chương 5 - Phạm Quang Dũng

Chương này trang bị cho người học những hiểu biết về lập lịch CPU. Các nội dung chính được trình bày trong chương 5 gồm: Các khái niệm cơ bản, các tiêu chuẩn lập lịch, các giải thuật lập lịch, lập lịch multiprocessor, lập lịch thời gian thực, lựa chọn giải thuật. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Nguyên lý hệ điều hành: Chương 5 - Phạm Quang DũngNội dung chương 5BÀI GIẢNGNGUYÊN LÝ HỆ ĐIỀU HÀNHCác khái niệm cơ bảnCác tiêu chuẩn lập lịchChương 5: Lập lịch CPUCác giải thuật lập lịchPhạm Quang DũngBộ môn Khoa học máy tínhKhoa Công nghệ thông tinTrường Đại học Nông nghiệp Hà NộiWebsite: fita.hua.edu.vn/pqdungLập lịch multiprocessorLập lịch thời gian thựcLựa chọn giải thuậtBài giảng Nguyên lý Hệ điều hành5.1. Các khái niệm cơ bản5.2Phạm Quang Dũng ©2008Trình lập lịch CPU - CPU Schedulermulti-programming giúp đạt được sự sử dụng CPU tối đaChu kỳ sử dụng CPU–I/O (CPU–I/O Burst Cycle): Sự thực hiệntiến trình gồm một chu kỳ thực hiện của CPU và chờ vào-ra.Sự phân phối sử dụng CPU giúp lựa chọn giải thuật lập lịch CPUMỗi khi CPU rỗi, HĐH cần chọn trong số các tiến trình đã sẵnsàng thực hiện trong bộ nhớ (ready queue), và phân phối CPUcho một trong số đó.Tiến trình được thực hiện bởi trình lập lịch ngắn kỳ (short-termscheduler, CPU scheduler)Các quyết định lập lịch CPU có thể xảy ra khi một tiến trình:1. Chuyển từ trạng thái chạy sang trạng thái chờ (vd: I/O request)2. Chuyển từ trạng thái chạy sang trạng thái sẵn sàng (vd: khi mộtngắt xuất hiện)3. Chuyển từ trạng thái đợisang trạng thái sẵn sàng(vd: I/O hoàn thành)4. Kết thúcBài giảng Nguyên lý Hệ điều hành5.3Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành5.4Phạm Quang Dũng ©20081Preemptive/nonpreemptive SchedulingTrình điều vận - DispatcherLập lịch CPU khi 1 và 4 là không được ưu tiên trướcMôđun trình điều vận trao quyền điều khiển của CPU cho tiến(nonpreemptive):trình được lựa chọn bởi trình lập lịch CPU; các bước:Không có sự lựa chọn: phải chọn 1 tiến trình mới để thực hiện.chuyển ngữ cảnhKhi 1 tiến trình được phân phối CPU, nó sẽ sử dụng CPU cho đếnchuyển sang user modekhi nó giải phóng CPU bằng cách kết thúc hoặc chuyển sang trạngnhảy tới vị trí thích hợp trong chương trình của người sử dụng đểthái chờ.khởi động lại chương trình đóCác tiến trình sẵn sàng nhường điều khiển của CPU.Trễ điều vận (Dispatch latency) – thời gian cần thiết để trình điềuLập lịch khi 2 và 3 là được ưu tiên trước (preemptive)vận dừng một tiến trình và khởi động một tiến trình khác chạy.Khi 2: tiến trình đá bật CPU ra. Cần phải chọn tiến trình kế tiếp.Khi 3: tiến trình có thể đá bật tiến trình khác ra khỏi CPU.Bài giảng Nguyên lý Hệ điều hành5.5Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành5.2. Các tiêu chuẩn lập lịchMaxCPU utilization – giữ cho CPU càng bận càng tốt (0-100%)gianTurnaround time – tổng lượng thời gian để thực hiện một tiến trình:Mint/g chờ được đưa vào bộ nhớ + t/g chờ trong ready queue + t/g thựchiện bởi CPU + t/g thực hiện vào-raMinPhạm Quang Dũng ©20085.3. Các giải thuật lập lịchThroughput – số tiến trình được hoàn thành trong một đơn vị thờiMax5.6First Come, First Served (FCFS)Shortest Job First (SJF)PriorityRound Robin (RR)Multilevel QueueMultilevel Feedback-QueueWaiting time – lượng thời gian mà một tiến trình chờ đợi ở trongready queueMinResponse time – lượng thời gian tính từ khi có một yêu cầu đượcgửi đến khi có sự trả lời đầu tiên được phát ra, không phải là thờigian đưa ra kết quả của sự trả lời đó. → là tiêu chuẩn tốt.Bài giảng Nguyên lý Hệ điều hành5.7Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành5.8Phạm Quang Dũng ©20082Giải thuật FCFS (tiếp)1) Giải thuật First-Come, First-Served (FCFS)Giả thuậ First- Come, First(FCFS)Tiến trình nào yêu cầu CPU trước sẽ được phân phối CPU trước→ Giải thuật FCFS là không được ưu tiên trước.Là giải thuật đơn giản nhấtProcessBurst Time (thời gian sử dụng CPU, ms)24P1P233P3Giả định rằng các tiến trình đến theo thứ tự: P1, P2, P3 thìbiểu đồ Gantt (Gantt Chart) của lịch biểu như sau:P1P2024Biểu đồ Gantt của lịch biểu như sau:P20P33P1630Thời gian chờ đợi của các tiến trình: P1 = 6; P2 = 0;; P3 = 3Thời gian chờ đợi trung bình: (6 + 0 + 3)/3 = 3P327Giả định rằng các tiến trình đến theo thứ tự P2 , P3 , P1Tốt hơn nhiều so với trường hợp trướcConvoy effect (hiệu ứng hộ tống): tiến trình ngắn đứng sau tiếntrình dài, như là các xe máy đi sau xe buýt vậy.30Thời gian chờ đợi của các tiến trình: P1 = 0; P2 = 24; P3 = 27Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17Bài giảng Nguyên lý Hệ điều hành5.9Phạm Quang Dũng ©20082) Giải thuật Shortest-Job-First (SJF)5.10Bài giảng Nguyên lý Hệ điều hànhPhạm Quang Dũng ©2008Ví dụ SJF không ưu tiên trướcProcessArrival TimeBurst TimeThời gian này được sử dụng để lập lịch các tiến trình với thờiP10.07gian ngắn nhất.P22.04Hai phương pháp:P34.01P45.04Gắn với mỗi tiến trình là thời gian sử dụng CPU tiếp sau của nó.không ưu tiên trước (non-preemptive)– một tiến trình nếu sử dụngCPU thì không nhường cho tiến trình khác cho đến khi nó kết thúc.SJF (non-preempt ...