Đề tài Lập lịch CPU

BÀI TẬP LỚN Đề tài: Lập lịch CPU Nhóm thực hiện: Nguyễn Thị Ngọc Huyên Nguyễn Thị Huyền Chu Thanh Hương Phạm Văn Hưởng Trần Đăng Khoa Mục tiêu Hiểu được - Tại sao cần phải lập lịch cho CPU - Các tiêu chí của lập lịch - Một số giải thuật của lập lịch Nội dung I/ Các khái niệm cơ bản II/ Các tiêu chuẩn lập lịch III/ Các giải thuật lập lịch IV/ Lập lịch multiprocessor V/ Lập lịch thời gian thực VI/ Lựa chọn giải thuật VII/ Ngắt I/ Các khái niệm cơ bản Khái niệm giờ CPU Chu kỳ sử dụng CPU-I/O Bộ định thời CPU Định thời biểu trưng dụng 1 Khái niệm giờ CPU Giờ CPU là thời gian mà CPU phục vụ cho tiến trình hoạt động. Tại 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/ Các khái niệm cơ bản Khái niệm giờ CPU Chu kỳ sử dụng CPU-I/O Bộ định thời CPU Định thời biểu trưng dụng Bộ phân phát 2/ Chu kỳ sử dụng CPU-I/O I/ Các khái niệm cơ bản Khái niệm giờ CPU Chu kỳ sử dụng CPU-I/O Bộ định thời CPU Định thời biểu trưng dụng Bộ phân phát 3/ Bộ định thời CPU Mỗi khị CPU rỗi, HĐH cần chọn trong số các tiến trình đã sẵn sàng thực hiện trong bộ nhớ (ready queue), và phân phối CPU cho một trong số đó. Tiến trình được thực hiện bởi trình lập ngắn chu kỳ (short-temr scheduler, CPU scheduler) I/ Các khái niệm cơ bản Khái niệm giờ CPU Chu kỳ sử dụng CPU-I/O Bộ định thời CPU Định thời biểu trưng dụng 4.Bộ định thời biểu trưng dụng Các quyết định lập lịch CPU có thể xảy khi một tiến trình: Chuyển từ trạng thái chạy sang trạng thái chờ Chuyển từ trạng thái chạy sang trạng thái sẵn sàng Chuyển từ trạng thái đợi sang trạng thái sẵn sàng Kết thúc Lập lịch CPU khi 1 và 4 không được ưu tiên trước: Không có sự lựa chọn: phải chọn một tiến trình mới để thực hiện Khi một tiến trình được phân phối CPU, nó sử dụng CPU cho đến khi giải phóng CPU bằng cách kết thúc hoặc chuyển sang trạng thái chờ Các tiến trình sẵn sàng nhường điều khiển của CPU 4.Bộ định thời biểu trưng dụng Lập lịch CPU khi 2 và 3 được ưu tiên trước: - 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. 4.Bộ định thời biểu trưng dụng Nội dung I/ Các khái niệm cơ bản II/ Các tiêu chuẩn lập lịch III/ Các giải thuật lập lịch IV/ Lập lịch multiprocessor V/ Lập lịch thời gian thực VI/ Lựa chọn giải thuật VII/ Ngắt II.Các tiêu chuẩn lập lịch CPU utilization (việc sử dụng CPU) Throughput (thông lượng) Turnaround time (thời gian hoàn thành) Waiting time (thời gian chờ) Responsen time (thời gian đáp ứng) Nội dung I/ Các khái niệm cơ bản II/ Các tiêu chuẩn lập lịch III/ Các giải thuật lập lịch IV/ Lập lịch multiprocessor V/ Lập lịch thời gian thực VI/ Lựa chọn giải thuật VII/ Ngắt III.Các giải thuật lập lịch 1.Định thời đến trước được phục vụ trước (firt-come,first-served) 2.Định thời biểu công việc ngắn nhất trước (shortest-job-first). 3.Định thời theo độ ưu tiên. 4.Định thời luân phiên. 5.Định thời biểu với hàng đợi nhiều cấp. 6.Định hàng đợi phản hồi đa cấp. 1.Định thời đến trước phục vụ trước Thuật toán: Độ ưu tiên phục vụ tiến trình dựa vào thời điểm hình thành tiến trình Mọi tiến trình đều được phục vụ theo trình tự xuất hiện cho đến khi 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 sẽ tăng vô hạn khi hệ thống tiếp cận tới hạn khả năng phục vụ của mình. Nếu thời gian thực hiện tiến trình tăng thì thời gian chờ đợi trung bình sẽ tăng theo Khi có tiến trình dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn Vd: Cho dãy tiến trình với thời gian phục vụ tương ứng: 1.Định thời đến trước phục vụ trước Nếu các quá trình đến theo thứ tự P1,P2,P3 và đc phục vụ theo thứ tự FCFS, chúng ta nhận được kết quả: Thời gian chờ của các tiến trình: P1 = 0; P2 = 24; P3 = 27 Thời gian chờ trung bình: (0 + 24 + 27)/3 = 17 1.Định thời đến trước phục vụ trước Nếu các tiến trình đến theo thứ tự: P2 , P3 , P1 . Biểu đồ Gantt của lập lịch như sau: Thời gian chờ đợi các tiến trinh: P1=6;P2=0;P3=3 Thời gian chờ đợi TB: (6+0+3)/3=3 1.Định thời đến trước phục vụ trước III.Các giải thuật lập lịch 1.Định thời đến trước được phục vụ trước (firt-come,first-served) 2.Định thời biểu công việc ngắn nhất trước (shortest-job-first) 3.Định thời theo độ ưu tiên 4.Định thời luân phiên 5.Định thời biểu với hàng đợi nhiều cấp 6.Định hàng đợi phản hồi đa cấp 2.Định thời biểu công việc ngắn trước phục vụ trước Thuật toán: Thứ tự ưu tiên thực hiện tiến trình dựa vào tổng thời gian thực hiện tiến trình Ưu điểm Thời gian chờ đợi trung bình của các thuật toán ngắn hơn so với FCFS Nhanh chóng loại bỏ các tiến trình ngắn Giảm số lượng tiến trình trong hàng đợi Nhược điểm:Chế độ phân phối lại giờ CPU được áp dụng trong trường hợp ngắt các tiến trình có thể không hợp lý - Gắn với mỗi tiến trình là thời gian sử dụng CPU tiếp sau của nó. Thời gian này được sử dụng để lập lịch các tiến trình với thời gain ngắn nhất. Có hai phương pháp: Không ưu tiên trước. Có ưu tiên trước. 2.Định thời biểu công việc ngắn trước phục vụ trước Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (non-preemptive) Ví dụ SJF không ưu tiên trước Thời gian chờ đợi của tiến trình: P1=0; P2=6; P3=3; P4=7 Thời gian chờ đợi trung bình: (0+6+3+7)/4 =4 Ví dụ SJF có ưu tiên trước Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (preemptive) Thời gian chờ đợi TB = (9 + 1 + 0 +2)/4 = 3 Xác định thời gian sử dụng CPU tiếp sau Không thể biết chính xác thời gian sử dụng CPU tiếp sau của tiến trình Có thể đoán giá trị xấp xỉ của nó dựa vào thời gian sử dụng CPU trước đó và sử dụng công thức đêị quy: Minh họa khi =1/2 và 0 =10 III.Các giải thuật lập lịch 1.Định thời đến trước được phục vụ trước (firt-come,first-served) 2.Định thời biểu công việc ngắn nhất trước (shortest-job-first) 3.Định thời theo độ ưu tiên 4.Định thời luân phiên 5.Định thời biểu với hàng đợi nhiều cấp 6.Định hàng đợi phản hồi đa cấp 3.Bộ định thời mức ưu tiên Một số tiến trình được gắn một số ưu tiên CPU được phân phối cho tiến trình có mức ưu tiên cao nhất (có số ưu tiên nhỏ nhất ) SJF là trường hợp riêng của lập lịch theo mức ưu tiên: mức ưu tiên chính là thời gian sử dụng CPU tiếp sau dự đoán được. Vấn đề gặp phải là: những tiến trình có mức ưu tiên thấp có thể ko bao giờ được thực hiện. Giải pháp: kỹ thuật tăng mức ưu tiên của các tiến trình chờ đợi lâu trong hệ thống. Ví dụ Quá trình Thời gian xử lý Độ ưu tiên P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 Thời gian chờ TB: (0+1+6+16+18)/5=8,2 3.Bộ định thời mức ưu tiên III.Các giải thuật lập lịch 1.Định thời đến trước được phục vụ trước (firt-come,first-served) 2.Định thời biểu công việc ngắn nhất trước (shortest-job-first) 3.Định thời theo độ ưu tiên 4.Định thời luân phiên 5.Định thời biểu với hàng đợi nhiều cấp 6.Định hàng đợi phản hồi đa cấp 4.Định thời luân phiên (Round-Robin (RR)) Mỗi tiến trình sử dụng một lượng nhỏ thời gian của CPU, thường là 10-100ms. Sau đó nó được ưu tiên đưa vào cuối của hàng đợi. Hàng đợi được tổ chức dạng FIFO(FCFS) Nếu tiến trình có thời gian sử dụng CPUq  bộ định thời sẽ đếm lùi và gây mất HĐH kkhi nó =0. Việc chuyển ngữ cảnh được thực hiện và tiến trình hiện tại được đưa xuống cuối hàng đợi để nhường CPU cho tiến trình kế tiếp. Quan hệ giữa q và hiệu năng Nếu q lớn tương tự như FCFS Nếu q nhỏ  số lần chuyển ngữ cảnh càng nhiều, làm giảm hiệu năng. 4.Định thời luân phiên (Round-Robin (RR)) Hiển thị cách thời gian hoàn thành biến đổi theo định mức thời gian. 4.Định thời luân phiên(Round-Robin (RR)) Ưu điểm: - Cho phép hệ thống ưu tiên những tiến trình ngắn ( vì nó kết thúc sớm) - 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 - Thời gian chờ đợi trung bình có thể lớn hơn so với FCFS - Chú ý: Nên chọn giá trị q cho thích hợp 4.Định thời luân phiên (Round-Robin (RR)) Vd: xét vd trên và giá trị time quantum q=4 Ta có sơ đồ grant biểu thị thứ tự ưu tiên thực hiện các tiến trình như sau: Từ sơ đồ ta thấy thời gian chờ của các tiến trình là : P1=6, p2=4, p3= 7 →thời gian chờ đợi trung bình của các tiến trình là : ( 6+4+7)/3=5.66 4 0 10 7 18 14 26 22 30 4.Định thời luân phiên (Round-Robin (RR)) III.Các giải thuật lập lịch 1.Định thời đến trước được phục vụ trước (firt-come,first-served) 2.Định thời biểu công việc ngắn nhất trước (shortest-job-first). 3.Định thời theo độ ưu tiên. 4.Định thời luân phiên. 5.Định thời biểu với hàng đợi nhiều cấp. 6.Định hàng đợi phản hồi đa cấp. 5.Định thời với hàng đợi nhiều cấp Được chia thành nhiều hàng đợi riêng lẻ: -chạy ở chế độ giao tiếp (foreground hay interactive) -chạy ở chế độ nền hay ạng bó(background hay batch) Mỗi hàng đợi có giải thuật lập lịch riêng: - foreground -RR - background –FCFC Phải có sự lập lịch giữa các hàng đợi: -lập lịch với mức ưu tiên cố định -paahn chia thời gian: mỗi hàng đợi nhạn được một lượng thời gain CPU nào đó mà nó có thể lập lịch các tiến trình của nó. 5.Định thời với hàng đợi nhiều cấp Nhược điểm : Khi có một tiến trình ở mức cao hơn cần thực hiện thì hệ thống phải ngắt tiến trình ở các mức thấp hơn để phục vụ tiến trình ở mức cao không sử dụng hết hiệu suất giờ CPU đựơc phân bổ Các tiến trình ở hàng đợi thứ hai hoạt động tính toán dựa trên nền của các tiến trình ở mức thứ nhất Sau khi thực hiện, tiến trình ở mức nào phải quay trở về mức đó nếu chưa kết thúc. 5.Định thời với hàng đợi nhiều cấp III.Các giải thuật lập lịch 1.Định thời đến trước được phục vụ trước (firt-come,first-served) 2.Định thời biểu công việc ngắn nhất trước (shortest-job-first). 3.Định thời theo độ ưu tiên. 4.Định thời luân phiên. 5.Định thời biểu với hàng đợi nhiều cấp. 6.Định hàng đợi phản hồi đa cấp. 6.Lập lịch đa mức hàng đợi thông tin phản hồi Một tiến trình có thể di chuyển giữa các hàng đợi. Trình lập lịch đa mức hàng đợi thông tin phản hồi được xác định bởi các tham số sau: - Số lượng hàng đợi - Giải thuật đinh thời cho mỗi hàng đợi - Phương pháp được dùng để các định khi nâng cấp một quá trình tới hàng đợi có độ ưu tiên cao hơn. - Phương pháp được dùng để các định khi nào chuyển một quá trình tới hàng đợi có đọ ưu tiên thấp hơn. - Phương pháp được dùng để xác định hàng đợi nào một quá trình sẽ đi vào và khi nòa qua trình đó cần phục vụ. Các hàng đợi phản hồi nhiều cấp: 6.Lập lịch đa mức hàng đợi thông tin phản hồi Nội dung I/ Các khái niệm cơ bản II/ Các tiêu chuẩn lập lịch III/ Các giải thuật lập lịch IV/ Lập lịch multiprocessor V/ Lập lịch thời gian thực VI/ Lựa chọn giải thuật VII/ Ngắt IV.Lập lịch multiprocessor (định thời biểu đa bộ sử lý) Lập lịch Cpu khi có nhiều bộ xử lý (processor) sẽ phức tạp hơn nhiều. Các loại proceessor trong multiprocessor: - Đồng nhất (homogeneous): tất cả có cùng cấu trúc. - Không đồng nhất (heterogeneous): một số tiến trình có thể ko tương thích với kiến trúc của CPU. Cân bằng tải (load balancing/sharing): một ready queue cho tất cả các processor, CPU nhàn rỗi được gán cho tiến trình đầu queue. Đa sử lý ko đối xứng –asymmetric multiprocessing: -chỉ có một processor truy nhập các cấu trúc dữ liệu hệ thống, làm giảm sự cần thiết bảo vệ dữ liệu chia sẻ. Nội dung I/ Các khái niệm cơ bản II/ Các tiêu chuẩn lập lịch III/ Các giải thuật lập lịch IV/ Lập lịch multiprocessor V/ Lập lịch thời gian thực VI/ Lựa chọn giải thuật VII/Ngắt V.Lập lịch theo thời gian thực Được chia làm hai loại: Hệ thồng thời thực cứng (hardware real-time systems) được yêu cầu để hoàn thành một tác vụ tới hạn trong lượng thời gian được đảm bảo.Khi tiến trình được gửi đến với lệnh cho biết thời gian cần thiết của nó,trình lập lịch có thể chấp nhận và đảm bảo nó kết thúc đúng thời hạn hoặc từ chối tiến trình Tính toán thời gian thực mềm (soft rsal_time computing) ít nghiêm khắc hơn.Nó yêu cầu các tiến trình tới hạn nhận độ ưu tiên cao hơn các qua trình khác.Có thể phân phối tài nguyên ko hợp lý,thời gain trễ, lâu hơn  phải cẩn thận trong thiết kế trình lập lịch và các khía cạnh liên quan của HĐH: - lập lịch có ưu tiên, có tiến trình thời gian thực có mức ưu tiên cao nhất. - trễ điều vận phải nhỏ. Nội dung I/ Các khái niệm cơ bản II/ Các tiêu chuẩn lập lịch III/ Các giải thuật lập lịch IV/ Lập lịch multiprocessor V/ Lập lịch thời gian thực VI/ Lựa chọn giải thuật VII/ Ngắt VI.Lựa chọn giải thuật. Chọn giải thuật lập lịch CPU nào cho hệ thống cụ thể? Trước tiên xác sử dụng tiêu chuẩn nào? 1 Phân tích hiệu năng của từng giải thuật đối với các tiến trình. 2 Sử dụng chuẩn hàng đợi: Công thức Little: n =  x w n: độ dài queue trung bình w: thời gian chờ đợi trng bình trong queue : tốc độ đến queue của tiến trình (số tiến trình/giây) 3 Mô phỏng: lập trình mô hình hệ thống để đánh giá 4 Thực hiện: đặt giải thuật cụ thể trong hệ thống thực để đánh giá Nội dung I/ Các khái niệm cơ bản II/ Các tiêu chuẩn lập lịch III/ Các giải thuật lập lịch IV/ Lập lịch multiprocessor V/ Lập lịch thời gian thực VI/ Lựa chọn giải thuật VII/ Ngắt VII.Ngắt. 1.Khái niệm ngắt 2. Phân loại ngắt 3.Quy trình sử lý ngắt 1.Khái niệm ngắt. Ngắt là phương tiện để các thiết bị thông báo cho CPU biết việc thay đổi trạng thái của mình từ góc độ CPU, ngắt là việc ngừng đột xuất việc thực hiện một tiến trình để chuyển sang thực hiện một tiến trình khác khi có một sự kiện nào đó sảy ra → Ngắt là công cụ để chuyển điều khiển tới một tiến trình khác mà tiến trình hiện tại không biết. 2.Phân loại ngắt. Ngắt được chia làm 2 loại: Ngắt trong: Là ngắt gây ra bởi các sự kiện liên quan đến hoạt động của CPU. Vd như sự kiện tràn ô nhớ, thực hiện phép chia cho 0, mã lệnh sai… Ngắt ngoài: Là ngắt gây ra bởi các sự kiện bên ngoài tiến trình đang thực hiện Vd: tín hiệu đồng hồ, ngắt vào/ra... 3.Quy trình xử lý ngắt Quy trình chung của xử lý ngắt: - Ghi nhận đặc trưng của sự kiện gây ra ngắt vào ô nhớ quy định. - Ghi nhận trạng thái của tiến trình bị ngắt ( bộ đếm chương trình, nội dung các thanh ghi, chế độ làm việc…). - Chuyển địa chỉ chương trình xử lý ngắt vào thanh ghi địa chỉ lệnh của CPU. - Thực hiện chương trình xử lý sự kiện - Khôi phục lại tiến trình bị ngắt. Đề bài : Cho dãy tiến trình với thời gian thực hiện tương ứng như sau: process Thời gian xử lý p1 10 P2 2 P3 7 P4 1 P5 5 a. Vẽ sơ đồ Grant theo các thuật toán FCFS, SJF, RR ( q=2)? b. Tính thời gian chờ đợi trung bình của các thuật toán. Thuật toán nào có thời gian chờ đợi trung bình ngắn nhất? Bài tập ứng dụng Lời giải: Sơ đồ Grant Thuật toán FCFS Thật toán SJF 19 12 10 25 20 0 1 3 8 15 25 0 Bài tập ứng dụng Thuật toán RR 2 4 6 7 9 11 13 15 17 19 20 22 23 25 0 b. Thời gian chờ đợi trung bình của mỗi thuật toán: Thuật toán FCFS: p1= 0 , p2= 10, p3=12, p4= 19, p5= 20 → thời gian chờ trung bình : ( 0+10+12+19+20)/5=12,2 Bài tập ứng dụng Thuật toán SJF p4=0, p2=1, p5=3, p3=8, p1=15 → thời gian chờ đợi trung bình là: ( 15+1+8+0+3)/5=5,4 Thuật toán RR p1=16, p2=2, p3=16, p4=6, p5=15 →thời gian chờ đợi trung bình là: ( 16+2+16+6+15)/5=11 Như vậy thuật toán SJF có thời gian chờ đợi trung bình thấp nhất. Bài tập ứng dụng