Trong môi trường tự nhiên đa chương, hoàn toàn có thể xảy ra trường hợp nhiều tiến trình đồng thời sẵn sàng chuẩn bị để giải quyết và xử lý. Mục tiêu của những hệ phân loại thời hạn là quy đổi CPU qua lại giữa những tiến trình một cách tiếp tục để nhiều người sử dụng hoàn toàn có thể tương tác cùng lúc với từng chương trình trong quy trình giải quyết và xử lý. Để triển khai được tiềm năng này, hệ điều hành phải lựa chọn tiến trình được giải quyết và xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối ( kế hoạch điều phối ) thích hợp để triển khai trách nhiệm này nhằm mục đích đưa ra sự công minh, tính hiệu suất cao, thời hạn cung ứng phải chăng, thời hạn lưu lại trong mạng lưới hệ thống phải chăng .
Ư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

1. Đặt vấn đề

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.

1. Nội dung nghiên cứu
2. First In First Out (FIFO)

Trong thuật toán này, độ ưu tiên Giao hàng tiến trình địa thế căn cứ vào thời gian hình thành tiến trình. Hàng đợi những tiến trình được tổ chức triển khai theo kiểu FIFO. Mọi tiến trình đều được ship hàng theo trình tự Open cho đến khi kết thúc hoặc bị ngắt .

• Ưu điểm của thuật toán này là giờ CPU không bị phân phối lại (không bị ngắt) và chi phí thực hiện thấp nhất (vì không phải thay đổi thứ tự ưu tiên phục vụ, thứ tự ưu tiên là thứ tự của tiến trình trong hàng đợi).
• Nhược điểm của thuật toán là thời gian trung bình chờ phục vụ của các tiến trình là như nhau (không kể tiến trình ngắn hay dài), do đó dẫn tới ba điểm sau:
• Thời gian chờ 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 độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ đợi trung bình cũng 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.

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ép 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 .

2. Round robin (RR)

Giải thuật định thời luân phiên ( round-robin scheduling algorithm-RR ) được phong cách thiết kế đặc biệt quan trọng cho mạng lưới hệ thống san sẻ thời hạn. 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 những quy trình. Đơn vị thời hạn nhỏ được gọi là định mức thời hạn ( time quantum ) hay phần thời hạn ( time slice ) được định nghĩa. Hàng đợi sẵn sàng chuẩn bị được xem như một hàng đợi vòng. Bộ định thời CPU vận động và di chuyển vòng quanh hàng đợi chuẩn bị sẵn sàng, cấp phép CPU tới mỗi quy trình có khoảng chừng thời hạn tối đa bằng một định mức thời hạn. Để thiết lập định thời RR, tất cả chúng ta quản trị hàng đợi sẵn sàng chuẩn bị như một hàng đợi FIFO của những quy trình. Các quy trình mới được thêm vào đuôi hàng đợi. Bộ định thời CPU chọn quy trình tiên phong từ hàng đợi sẵn sàng chuẩn bị, đặt bộ đếm thời hạn để ngắt sau 1 định mức thời hạn và gởi tới quy trình. Sau đó, một trong hai trường hợp sẽ xảy ra. Quá trình có 1 chu kỳ luân hồi CPU ít hơn 1 định mức thời hạn. Trong trường hợp này, quy trình sẽ tự giải phóng. Sau đó, bộ định thời biểu sẽ giải quyết và xử lý quy trình tiếp theo trong hàng đợi sẵn sàng chuẩn bị. Ngược lại, nếu chu kỳ luân hồi CPU của quy trình đang chạy dài hơn 1 định mức thời hạn thì độ đếm thời hạn 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à quy trình được đặt trở lại tại đuôi của hàng đợi sẵn sàng chuẩn bị. Sau đó, bộ định thời biểu CPU sẽ chọn quy trình tiếp theo trong hàng đợi sẵn sàng chuẩn bị .

• Ưu điểm:
• Các quá trình sẽ được luân phiên cho CPU xữ lý nên thời gian chờ đợi sẽ ít.
• Đối với các quá trình liên quan đến nhập xuất, IO, người dùng thì rất hiệu quả.
• Việc cài đặt không quá phức tạp
• Nhược điểm:
• Thời gian chờ đợi trung bình dưới chính sách RR thường là quá dài.
• Nếu thời gian định mức cho việc xữ lý quá lớn thì RR thành FIFO
• Nếu thời gian quá ngắn so với thời gian xữ lý của một tiến trình trong danh sách hàng đợi thì việc chờ đợi và xữ lý luân phiên sẽ nhiều.
  • Qui tắc là định mức thời gian nên dài hơn 80% chu kỳ CPU.

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 những 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 hạn chờ đón trung bình sẽ là : ( 0 + 6 + 3 + 5 ) / 3 = 4,67 milliseconds. Như vậy RR có thời hạn chờ đón trung bình nhỏ hơn so với FIFO

3. Shortest Job First (SJF)

Một tiếp cận khác so với việc định thời CPU là giải thuật định thời việc làm ngắn nhất trước ( shortest-job-first-SJF ). Giải thuật này gán tới mỗi quy trình chiều dài của chu kỳ luân hồi CPU tiếp theo cho quy trình sau đó. Khi CPU sẵn dùng, nó được gán tới quy trình có chu kỳ luân hồi CPU sau đó ngắn nhất. Nếu hai quy trình có cùng chiều dài chu kỳ luân hồi CPU tiếp nối, định thời FIFO được dùng. Chú ý rằng thuật ngữ tương thích hơn là chu kỳ luân hồi CPU tiếp nối ngắn nhất ( shortest next CPU burst ) vì định thời được thực thi bằng cách xem xét chiều dài của chu kỳ luân hồi CPU sau đó của quy trình hơn là hàng loạt 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 tìm hiểu thêm tới nguyên tắc của loại định thời biểu này như SJF .

• Ưu điểm:

• Giải thuật được xem là tối ưu, thời gian chờ đợi trung bình giảm
• Tận dụng hết năng lực của CPU
  • Nhược điểm:
• Cài đặt thuật toán phức tạp, tốn nhiều xữ lý cho quá trình quản lý.
• Mặc dù SJF là tối ưu nhưng nó không thể được cài đặt tại cấp định thời CPU ngắn vì không có cách nào để biết chiều dài chu kỳ CPU tiếp theo.
• Giải thuật SJF có thể trưng dụng hoặc không trưng dụng CPU, dẫn tới giải thuật này có nhiều dị bản khác nhau và sẽ tối ưu hay không tối ưu phụ thuộc vào trưng dụng CPU.

4. Shortest Remain Time (SRT)

Tương tự như SJF nhưng trong thuật toán này, độ ưu tiên thực thi những tiến trình dựa vào thời hạn thiết yếu để thực thi nốt tiến trình ( bằng tổng thời hạn trừ đi thời hạn đã thực thi ). Như vậy, trong thuật toán này cần phải tiếp tục update thông tin về giời gian đã triển khai của tiến trình. Đồng thời, chính sách phân chia lại giờ CPU cũng phải được vận dụng nếu không sẽ làm mất tình ưu việc của thuật toán .

• Ưu điểm:

• Thời gian chờ đợi, tồn tại trong hệ thống của mỗi tiến trình đều ngắn
• Thuật toán tối ưu nhất
  • Nhược điểm:
• Việc cài đặt thuật toán khá phức tạp
• Cần quản lý chặt chẽ việc điều phối các tiến trình
• Quản lý thời gian đến của mỗi tiến trình

III. Kết luận

Như 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.

C. Tài liệu tham khảo

[1]. Hồ Đắc Phương (2010), Nguyên lý hệ điều hành, NXB Giáo dục.
[2]. Từ Minh Phương (2013), Giáo trình hệ điều hành, NXB, Học viện công nghệ Bưu chính Viễn thông.
[3]. Nguyễn Kim Tuấn (2014), Giáo trình lý thuyết hệ điều hành, NXB ĐHQGHN.
[4]. Hà Quang Thụy (2009), Giáo trình Nguyên lý hệ điều hành, NXB Khoa học và kỹ thuật
[ 1 ]. Hồ Đắc Phương ( 2010 ), Nguyên lý hệ điều hành, NXB Giáo dục đào tạo. [ 2 ]. Từ Minh Phương ( 2013 ), Giáo trình hệ điều hành, NXB, Học viện công nghệ tiên tiến Bưu chính Viễn thông. [ 3 ]. Nguyễn Kim Tuấn ( năm trước ), Giáo trình triết lý hệ điều hành, NXB ĐHQGHN. [ 4 ]. Hà Quang Thụy ( 2009 ), Giáo trình Nguyên lý hệ điều hành, NXB Khoa học và kỹ thuật

 

Source: https://vh2.com.vn
Category : Ứng Dụng