Phương pháp lập lịch SJF ưu tiên
|
Show
This site uses cookies. By continuing, you agree to their use. Learn more, including how to control cookies. Xin chào mọi người, nối tiếp seri về kinh nghiệm IT: https://huongtlu.wordpress.com//kinh-nghiem-it/ bài viết này mình chia sẻ về 3 thuật toán chính liên quan tại bài viết: https://huongtlu.wordpress.com/2020/06/26/huong-dan-tu-hoc-de-do-chung-chi-fe-fundamental-it-engineer-bai-6/ Đây là 3 thuật toán liên quan tới xử lý tiến trình trong hệ điều hành máy tính. Đề thi FE (Fundamental IT Engineer) các năm gần đây mình thấy đa số đều có ít nhất 1 câu liên quan tới các thuật toán này. Ngoài ra còn có 1 số thuật toán khác như: Round Robin, … Theo dõi list bài học luyên thi FE (Fundamental IT Engineer): TẠI ĐÂY XEM VIDEO HƯỚNG DẪN:
Bài tập kiểm traQuiz 1: Below is the list of processes, P1, P2, P3, and P4, and their burst time for CPU scheduling algorithms. Which of the following combinations is the average waiting time in millisecond for a First-Come, First-Serve (FCFS) scheduling and Shortest-Job-First (SJF) scheduling given that the process arrives in the order P1, P2, P3, and P4, and the latency can be ignored. Note that the burst time is the actual time required to complete a process. Hường TLU Follow me on social media  4. Các thuật toán lập lịchMục tiêu:Nắm được các giải pháp lập lịch mà hệ điều hành thực hiện nhằm điều phối các quá trình được thực hiện trên CPU. 4.1. First Come First Served (FCFS)Tiến trình nào có yêu cầu sử dụng CPU trước thì sẽ được thực hiện trước. Ưu điểm là thuật thoán đơn giản nhất Nhược điểm la hiệu quả thuật toán phụ thuộc vào thứ tự của các tiến trình trong hàng đợi.
Hình 4.2 .hàng đợi FCFS Giả sử có 3 tiến trình P1 , P2 , P3 với thời gian thực hiện tương ứng là 24ms, 3ms, 6ms
Giả sử ba tiến trình xếp hàng theo thứ tự P1, P2, P3 Thời gian chờ các tiến trình là: P1chờ 0ms, P2 chờ 24ms, P3 chờ 27ms Thời gian chờ trung bình: (0+24+27)/3=17ms Thời gian chờ trung bình không đạt cực tiểu, và biến đổi đáng kể đối với các giá trị về thời gian yêu cầu xử lý và thứ tự khác nhau của các tiến trình trong danh sách sẵn sàng. Có thể xảy ra hiện tượng tích lũy thời gian chờ, khi các tất cả các tiến trình (có thể có yêu cầu thời gian ngắn) phải chờ đợi một tiến trình có yêu cầu thời gian dài kết thúc xử lý. Giải thuật này đặc biệt không phù hợp với các hệ phân chia thời gian, trong các hệ này, cần cho phép mỗi tiến trình được cấp phát CPU đều đặn trong từng khoảng thời gian. 4.2. Shortest Job First (SJF)Nguyên tắc : Đây là một trường hợp đặc biệt của giải thuật điều phối với độ ưu tiên. Trong giải thuật này, độ ưu tiên p được gán cho mỗi tiến trình là nghịch đảo của thời gian xử lý t mà tiến trình yêu cầu : p = 1/t. Khi CPU được tự do, nó sẽ được cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc- tiến trình ngắn nhất. Giải thuật này cũng có thể độc quyền hay không độc quyền. Sự chọn lựa xảy ra khi có một tiến trình mới được đưa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lý. Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý. Giải thuật SJF không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý. Nếu hai tiến trình có cùng thời gian sử dụng CPU, tiến trình đến trước sẽ đựơc yêu cầu CPU trước. Ví dụ :
Sử dụng thuật giải SJF độc quyền, thứ tự cấp phát CPU như sau:
Sử dụng thuật giải SJF không độc quyền, thứ tự cấp phát CPU như sau:
Thảo luận : Giải thuật này cho phép đạt được thời gian chờ trung bình cực tiểu. Khó khăn thực sự của giải thuật SJF là không thể biết được thời gian yêu cầu chu kỳ CPU tiếp theo? Chỉ có thể dự đoán giá trị này theo cách tiếp cận sau : gọi tn là độ dài của thời gian xử lý lần thứ n, t n+1 là giá trị dự đoán cho lần xử lý tiếp theo. Với hy vọng giá trị dự đoán sẽ gần giống với các giá trị trước đó, có thể sử dụng công thức: t n+1 = a tn + (1-a )t n Trong công thức này,tn chứa đựng thông tin gần nhất ; t n chứa đựng các thông tin quá khứ được tích lũy. Tham số a ( 0 <= a <= 1) kiểm soát trọng số của hiện tại gần hay quá khứ ảnh hưởng đến công thức dự đoán.
4.3. Shortest Remain Time (SRT)Nguyên tắc : Mỗi tiến trình được gán cho một độ ưu tiên tương ứng, tiến trình có độ ưu tiên cao nhất sẽ được chọn để cấp phát CPU đầu tiên. Các tiến trình có độ ưu tiên bằng nhau thì tiến trình nào đến trước thì sẽ được cấp trước. Độ ưu tiên có thể được định nghĩa nội tại hay nhờ vào các yếu tố bên ngoài. Độ ưu tiên nội tại sử dụng các đại lượng có thể đo lường để tính toán độ ưu tiên của tiến trình, ví dụ các giới hạn thời gian, nhu cầu bộ nhớ…Độ ưu tiên cũng có thể được gán từ bên ngoài dựa vào các tiêu chuẩn do hệ điều hành như tầm quan trọng của tiến trình, loại người sử dụng sỡ hữu tiến trình… Giải thuật điều phối với độ ưu tiên có thể theo nguyên tắc độc quyền hay không độc quyền. Khi một tiến trình được đưa vào danh sách các tiến trình sẵn sàng, độ ưu tiên của nó được so sánh với độ ưu tiên của tiến trình hiện hành đang xử lý. Giải thuật điều phối với độ ưu tiên và không độc quyền sẽ thu hồi CPU từ tiến trình hiện hành để cấp phát cho tiến trình mới nếu độ ưu tiên của tiến trình này cao hơn tiến trình hiện hành. Một giải thuật độc quyền sẽ chỉ đơn giản chèn tiến trình mới vào danh sách sẵn sàng, và tiến trình hiện hành vẫn tiếp tục xử lý hết thời gian dành cho nó. Ví dụ : (độ ưu tiên 1 > độ ưu tiên 2> độ ưu tiên 3)
Sử dụng thuật giải độc quyền, thứ tự cấp phát CPU như sau :
Sử dụng thuật giải không độc quyền, thứ tự cấp phát CPU như sau :
Thảo luận : Tình trạng ‘đói CPU’ (starvation) là một vấn đề chính yếu của các giải thuật sử dụng độ ưu tiên. Các giải thuật này có thể để các tiến trình có độ ưu tiên thấp chờ đọi CPU vô hạn ! Để ngăn cản các tiến trình có độ ưu tiên cao chiếm dụng CPU vô thời hạn, bộ điều phối sẽ giảm dần độ ưu tiên của các tiến trình này sau mỗi ngắt đồng hồ. Nếu độ ưu tiên của tiến trình này giảm xuống thấp hơn tiến trình có độ ưu tiên cao thứ nhì, sẽ xảy ra sự chuyển đổi quyền sử dụng CPU.Quá trình này gọi là sự ‘lão hóa’ tiến trình. 4.4. Round Robin (RR)Nguyên tắc : Danh sách sẵn sàng được xử lý như một danh sách vòng, bộ điều phối lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian tối đa sử dụng CPU cho trước gọi là quantum. Tiến trình đến trước thì được cấp phát CPU trước. Đây là một giải thuật điều phối không độc quyền : khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách. Nếu tiến trình bị khóa hay kết thúc trước khi sử dụng hết thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình khác. Khi tiến trình tiêu thụ hết thời gian CPU dành cho nó mà chưa hoàn tất, tiến trình được đưa trở lại vào cuối danh sách sẵn sàng để đợi được cấp CPU trong lượt kế tiếp. V í dụ : Hình 4.3 Điều phối Round Robin
Nếu sử dụng quantum là 4 milisecondes, thứ tự cấp phát CPU sẽ là
Thời gian chờ đợi trung bình sẽ là (0+6+3+5)/3 = 4.66 milisecondes. Nếu có n tiến trình trong danh sách sẵn sàng và sử dụng quantum q, thì mỗi tiến trình sẽ được cấp phát CPU 1/n trong từng khoảng thời gian q. Mỗi tiến trình sẽ không phải đợi quá (n-1)q đơn vị thời gian trước khi nhận được CPU cho lượt kế tiếp. Vấn đề đáng quan tâm đối với giải thuật RR là độ dài của quantum. Nếu thời lượng quantum quá bé sẽ phát sinh quá nhiều sự chuyển đổi giữa các tiến trình và khiến cho việc sử dụng CPU kém hiệu quả. Nhưng nếu sử dụng quantum quá lớn sẽ làm tăng thời gian hồi đáp và giảm khả năng tương tác của hệ thống.
4.5. Multi Level Queue (MLQ)Để phân lớp các quá trình đang trong trạng thái chuẩn bị và chọn lựa quá trình chuyển sang trạng thái sử dụng có thể sử dụng các thông tin được cho bằng người tạo ra quá trình đó và các thông tin nhận được trong việc điều phối các quá trình. Các thông tin này có thể là:
Với hệ thống tổ chức trang bộ nhớ, tiện lợi nhất là sử dụng một số dòng xếp hàng khác nhau để phân biệt các quá trình ở trạng thái đặt/tách trang với các quá trình chờ đợi sự kết thúc vào/ra.
4.6. Multi Level Feedback Queues (MLFQ)N guyên tắc : Ý tưởng chính của giải thuật là phân lớp các tiến trình tùy theo độ ưu tiên của chúng để có cách thức điều phối thích hợp cho từng nhóm. Danh sách sẵn sàng được phân tách thành các danh sách riêng biệt theo cấp độ ưu tiên, mỗi danh sách bao gồm các tiến trình có cùng độ ưu tiên và được áp dụng một giải thuật điều phối thích hợp để điều phối. Ngoài ra, còn có một giải thuật điều phối giữa các nhóm, thường giải thuật này là giải thuật không độc quyền và sử dụng độ ưu tiên cố định.Một tiến trình thuộc về danh sách ở cấp ưu tiên i sẽ chỉ được cấp phát CPU khi các danh sách ở cấp ưu tiên lớn hơn i đã trống. Hình 4.4 Điều phối nhiều cấp ưu tiên Thông thường, một tiến trình sẽ được gán vĩnh viễn với một danh sách ở cấp ưu tiên i khi nó được đưa vào hệ thống. Các tiến trình không di chuyển giữa các danh sách. Cách tổ chức này sẽ làm giảm chi phí điều phối, nhưng lại thiếu linh động và có thể dẫn đến tình trạng ‘đói CPU’ cho các tiến trình thuộc về những danh sách có độ ưu tiên thấp. Do vậy có thể xây dựng giải thuật điều phối nhiều cấp ưu tiên và xoay vòng. Giải thuật này sẽ chuyển dần một tiến trình từ danh sách có độ ưu tiên cao xuống danh sách có độ ưu tiên thấp hơn sau mỗi lần sử dụng CPU. Cũng vậy, một tiến trình chờ quá lâu trong các danh sách có độ ưu tiên thấp cũng có thể được chuyển dần lên các danh sách có độ ưu tiên cao hơn. Khi xây dựng một giải thuật điều phối nhiều cấp ưu tiên và xoay vòng cần quyếtđịnh các tham số : Số lượng các cấp ưu tiên Giải thuật điều phối cho từng danh sách ứng với một cấp ưu tiên. Phương pháp xác định thời điểm di chuyển một tiến trình lên danh sách có độ ưu tiên cao hơn. Phương pháp xác định thời điểm di chuyển một tiến trình lên danh sách có độ ưu tiên thấp hơn. P hương pháp sử dụng để xác định một tiến trình mới được đưa vào hệ thống sẽ thuộc danh sách ứng với độ tiên nào. Hình 4.5 Điều phối Multilevel Feedback
Каталог: mydata -> giaoan tải về 0.76 Mb. Chia sẻ với bạn bè của bạn:
|
