Các Thuật Toán Lập Lịch - Những Kiến Thức Về Hệ điều Hành - 123doc

3.2.3.1. Chiến lược FIFO

- Nguyên tắc: CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình được đưa vào hệ thống sớm nhất. Đây là thuật toán điều phối theo nguyên tắc độc quyền. Một khi CPU được cấp phát cho tiến trình, CPU chỉ được tiến trình tự nguyện giải phóng khi kết thúc xử lý hay khi có một yêu cầu nhập/xuất.

Hình 3.2.3.1-1. Điều phối FIFO

Ví dụ :

Tiến trình Thời điểm vào RL Thời gian xử lý

P1 0 24

P2 1 3

P3 2 3

Thứ tự cấp phát CPU cho các tiến trình là :

P1 P2 P3

0 24 27 30

Thời gian chờ đợi được xử lý là 0 đối với P1, (24 -1) với P2 và (24+3- 2) với P3. Thời gian chờ trung bình là (0+23+25)/3 = 16 milisecondes.

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.

3.2.3.2. Lập lịch xoay vòng (Round Robin)

- 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 sử dụng CPU gọi là quantum (lượng tử thời gian). Đâ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 3.2.3.2-1. Lập lịch Round Robin

Tiến trình Thời điểm vào RL Thời gian xử lý

P1 0 24

P2 1 3

P3 2 3

Nếu sử dụng quantum là 4 milisecondes, thứ tự cấp phát CPU sẽ là :

P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

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.

3.2.3.3. Lập lịch với độ ưu tiên

- 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. Độ ư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)

Tiến trình Thời điểm vào RL Độ ưu tiên Thời gian xử lý

P1 0 3 24

P2 1 1 3

P3 2 2 3

Sử dụng thuật giải độc quyền, thứ tự cấp phát CPU như sau:

P1 P2 P3

0 24 27 30

Sử dụng thuật giải không độc quyền, thứ tự cấp phát CPU như sau:

0 1 4 7 30

3.2.3.4. Chiến lược công việc ngắn nhất (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ý.

Ví dụ:

Tiến trình Thời điểm vào RL Thời gian xử lý

P1 0 6

P2 1 8

P3 2 4

P4 3 2

Sử dụng thuật giải SJF độc quyền, thứ tự cấp phát CPU như sau:

P1 P4 P3 P2

0 6 8 12 30

Sử dụng thuật giải SJF không độc quyền, thứ tự cấp phát CPU như sau:

P1 P4 P1 P3 P2

0 3 5 8 12 20

- Nguyê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 3.2.3.5-2. Điều phối Multilevel Feedback

3.2.3.6. Chiến lược lập lịch Xổ số (Lottery)

- Nguyên tắc: Ý tưởng chính của giải thuật là phát hành một số vé số và phân phối cho các tiến trình trong hệ thống. Khi đến thời điểm ra quyết định điều phối, sẽ tiến hành chọn 1 vé "trúng giải", tiến trình nào sỡ hữu vé này sẽ được nhận CPU(chọn ngẫu nhiên)

CHƯƠNG 4 TRUYỀN THÔNG VÀ ĐỒNG BỘ TIẾN TRÌNH