Trong suốt chu trình sống, tiến trình chuyển đổi qua lại giữa các trạng thái ready, running và blocked. Bộ điều phối của hệ điều hành chịu trách nhiệm áp dụng một gỉai thuật điều phối thích hợp để chọn tiến trình thích hợp được sử dụng CPU, và bộ phân phối sẽ chuyển giao CPU cho tiến trình này. Các giải thuật điều phối thông dụng : FIFO, RoundRobin, điều phối với độ ưu tiên, SJF, Multilevel Feedback Câu hỏi cũng cố bài họcCác câu hỏi cần trả lời được sau bài học này : 1. Thông tin lưu trữ trong PCB và TCB ? 2. Tổ chức điều phối tiến trình ? 3. Phân tích ưu, khuyết của các chiến lược điều phối Bài tậpBài 1. Xét tập các tiến trình sau (với thời gian yêu cầu CPU và độ ưu tiên kèm theo) :  Giả sử các tiến trình cùng được đưa vào hệ thống tại thời điểm 0 a)Cho biết kết quả điều phối hoạt động của các tiến trình trên theo thuật toán FIFO; SJF; điều phối theo độ ưu tiên độc quyền (độ ưu tiên 1 > 2 > ...); và RR (quantum=2). b)Cho biết thời gian lưu lại trong hệ thống (turnaround time) của từng tiến trình trong từng thuật toán điều phối ở câu a. c)Cho biết thời gian chờ trong hệ thống (waiting time) của từng tiến trình trong từng thuật toán điều phối ở câu a. d)Thuật toán điều phối nào trong các thuật toán ở câu a cho thời gian chờ trung bình là cực tiểu ? Bài 2. Giả sử có các tiến trình sau trong hệ thống : Sử dụng nguyên tắc điều phối độc quyền và các thông tin có được tại thời điểm ra quyết định để trả lời các câu hỏi sau đây : a)Cho biết thời gian lưu lại trung bình trong hệ thống (turnaround time) của các tiến trình trong thuật toán điều phối FIFO. b)Cho biết thời gian lưu lại trung bình trong hệ thống (turnaround time) của các tiến trình trong thuật toán điều phối SJF. c)Thuật toán SJF dự định cải tiến sự thực hiện của hệ thống , nhưng lưu ý chúng ta phải chọn điều phối P1 tại thời điểm 0 vì không biết rằng sẽ có hai tiến trình ngắn hơn vào hệ thống sau đó . Thử tính thời gian lưu lại trung bình trong ệ thống nếu để CPU nhàn rỗi trong 1 đơn vị thời gian đầu tiên và sau đó sử dụng SJF để điều phối. Lưu ý P1 vàP2 sẽ phải chờ trong suốt thời gian nhàn rỗi này, do vậy thời gian chờ của chúng tăng lên. Thuật toán điều phối này được biết đến như điều phối dựa trên thông tin về tương lai. Bài 3. Phân biệt sự khác nhau trong cách tiếp cận để ưu tiên cho tiến trình ngắn trong các thuật toán điều phối sau :
b)RR c)Điều phối với độ ưu tiên đa cấp Bài 4. Cho biết hai ưu điểm chính của mô hình đa tiểu trình so với đa tiến trình. Mô tả một ứng dụng thích hợp vớ mô hình đa tiểu trình và một ứng dụng khác không thích hợp. Bài 5. Mô tả các xử lý hệ điều hành phải thực hiện khi chuyển đổi ngữ cảnh giữa : a)các tiến trình b)các tiểu trình Bài 6. Xác định thời lượng quantum q là một nhiệm vụ khó khăn. Giả sử chi phí trung bình cho một lần chuyển đổi ngữ cảnh là s, và thời gian trung bình một tiến trình hướng nhập xuất sử dụng CPU trước khi phát sinh một yêu cầu nhập xuất là t ( t>>s). Thảo luận các tác động đến sự thực hiện của hệ thống khi chọn q theo các quy tắc sau : a)q bất định b)q lớn hơn 0 1 ít c)q = s d)s < q < t e)q = t f)q > t Bài 7. Giả sử một hệ điều hành áp dụng giải thuật điều phối multilevel feedback với 5 mức ưu tiên (giảm dần). Thời lượng quantum dành cho hàng đợi cấp 1 là 0,5s. Mỗi hàng đợi cấp thấp hơn sẽ có thời lượng quantum dài gấp đôi hàng đợi ứng với mức ưu tiên cao hơn nó. Một tiến trình khi vào hệ thống sẽ được đưa vào hàng đợi mức cao nhất, và chuyển dần xuống các hàng đợi bên dưới sau mỗi lượt sử dụng CPU. Một tiến trình chỉ có thể bị thu hồi CPU khi đã sử dụng hết thời lượng quantum dành cho nó. Hệ thống có thể thực hiện các tác vụ xử lý theo lô hoặc tương tác, và mỗi tác vụ lại có thể hướng xử lý hay hướng nhập xuất. a)Giải thích tại sao hệ thống này hoạt động không hiệu quả ? b)Cần phải thay đổi (tối thiểu) như thế nào để hệ thống điều phối các tác vụ với những bản chất khác biệt như thế tốt hơn ? Trong môi trường đa chương, có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia thời gian là chuyển đổi CPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình xử lý. Để thực hiện được mục tiêu này, hệ điều hành phải lựa chọn tiến trình được xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối (chiến lược điều phối) thích hợp để thực hiện nhiệm vụ này nhằm đưa ra sự công bằng, tính hiệu quả, thời gian đáp ứng hợp lí, thời gian lưu lại trong hệ thống hợp lí. ƯU NHƯỢC ĐIỂM CÁC CHIẾN LƯỢC ĐIỀU PHỐI CPU ThS. Cao Thị Bích Liên, GV khoa Công nghệ thông tin
Trong bài viết này sẽ trình bày về chiến lược một hàng đợi nhiều tiến trình chờ phân phối xử lý. Trong chiến lược một hàng đợi này có 4 thuật toán chính FIFO, SJF, RR, Thuật toán ưu tiên.
Trong thuật toán này, độ ưu tiên phục vụ tiến trình căn cứ vào thời điểm hình thành tiến trình. Hàng đợi các tiến trình được tổ chức theo kiểu FIFO. 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.
Ví dụ: Tiến trình Thời điểm vào Thời gian xử lí P1 0 24 P2 1 3 P3 2 3 Thứ tự cấp phát tiến trình: Tiến trình P1 P2 P3 Thời điểm 0 24 27/30 Thời gian chờ trung bình: (0+23+25)/3=16 milliseconds.
Giải thuật định thời luân phiên (round-robin scheduling algorithm-RR) được thiết kế đặc biệt cho hệ thống chia sẻ thời gian. Tương tự như định thời FIFO nhưng sự trưng dụng CPU được thêm vào để chuyển CPU giữa các quá trình. Đơn vị thời gian nhỏ được gọi là định mức thời gian (time quantum) hay phần thời gian (time slice) được định nghĩa. Hàng đợi sẵn sàng được xem như một hàng đợi vòng. Bộ định thời CPU di chuyển vòng quanh hàng đợi sẵn sàng, cấp phát CPU tới mỗi quá trình có khoảng thời gian tối đa bằng một định mức thời gian. Để cài đặt định thời RR, chúng ta quản lý hàng đợi sẵn sàng như một hàng đợi FIFO của các quá trình. Các quá trình mới được thêm vào đuôi hàng đợi. Bộ định thời CPU chọn quá trình đầu tiên từ hàng đợi sẵn sàng, đặt bộ đếm thời gian để ngắt sau 1 định mức thời gian và gởi tới quá trình. Sau đó, một trong hai trường hợp sẽ xảy ra. Quá trình có 1chu kỳ CPU ít hơn 1 định mức thời gian. Trong trường hợp này, quá trình sẽ tự giải phóng. Sau đó, bộ định thời biểu sẽ xử lý quá trình tiếp theo trong hàng đợi sẵn sàng. Ngược lại, nếu chu kỳ CPU của quá trình đang chạy dài hơn 1 định mức thời gian thì độ đếm thời gian sẽ báo và gây ra một ngắt tới hệ điều hành. Chuyển đổi ngữ cảnh sẽ được thực thi và quá trình được đặt trở lại tại đuôi của hàng đợi sẵn sàng. Sau đó, bộ định thời biểu CPU sẽ chọn quá trình tiếp theo trong hàng đợi sẵn sàng.
Ví dụ: Tiến trình thời điểm vào thời gian xử lý P1 0 24 P2 1 3 P3 2 3 Quantum = 4 milliseconds Thì thứ tự cấp processor cho các tiến trình lần lượt là: Tiến trình P1 P2 P3 P1 P1 P1 P1 P1 P1 Thời điểm 0 4 7 10 14 18 22 26 30 Vậy thời gian chờ đợi trung bình sẽ là: (0+6+3+5)/3 = 4,67 milliseconds. Như vậy RR có thời gian chờ đợi trung bình nhỏ hơn so với FIFO
Một tiếp cận khác đối với việc định thời CPU là giải thuật định thời công việc ngắn nhất trước (shortest-job-first-SJF). Giải thuật này gán tới mỗi quá trình chiều dài của chu kỳ CPU tiếp theo cho quá trình sau đó. Khi CPU sẵn dùng, nó được gán tới quá trình có chu kỳ CPU kế tiếp ngắn nhất. Nếu hai quá trình có cùng chiều dài chu kỳ CPU kế tiếp, định thời FIFO được dùng. Chú ý rằng thuật ngữ phù hợp hơn là chu kỳ CPU kế tiếp ngắn nhất (shortest next CPU burst) vì định thời được thực hiện bằng cách xem xét chiều dài của chu kỳ CPU kế tiếp của quá trình hơn là toàn bộ chiều dài của nó. Chúng ta dùng thuật ngữ SJF vì hầu hết mọi người và mọi sách tham khảo tới nguyên lý của loại định thời biểu này như SJF.
Tương tự như SJF nhưng trong thuật toán này, độ ưu tiên thực hiện các tiến trình dựa vào thời gian cần thiết để thực hiện nốt tiến trình (bằng tổng thời gian trừ đi thời gian đã thực hiện). Như vậy, trong thuật toán này cần phải thường xuyên cập nhật thông tin về giời gian đã thực hiện của tiến trình. Đồng thời, chế độ phân bổ lại giờ CPU cũng phải được áp dụng nếu không sẽ làm mất tình ưu việc của thuật toán.
III. Kết luậnNhư vậy, tùy thuộc vào từng bài toán cụ thể ta có thể áp dụng chiến lược điều phối nào cho các tiến trình nhằm đưa lại thời gian chờ đợi để được xử lý của các tiến trình một cách nhanh nhất. |
