Lập lịch CPU Algorithms in Operahệ thống ting

Lập lịch CPU là gì?

Lập lịch CPU Lập lịch CPU là quá trình xác định tiến trình nào sẽ sở hữu CPU để thực thi trong khi một tiến trình khác đang chờ. Nhiệm vụ chính của lập lịch CPU là đảm bảo rằng bất cứ khi nào CPU rảnh rỗi, hệ điều hành sẽ chọn ít nhất một trong các tiến trình có sẵn trong hàng đợi sẵn sàng để thực thi. Quá trình lựa chọn được thực hiện bởi bộ lập lịch CPU, bộ này sẽ chọn một trong các tiến trình trong bộ nhớ đang sẵn sàng để thực thi.

Các loại lập lịch CPU

Dưới đây là hai loại phương pháp lập lịch:

Lập lịch trước

Trong lập lịch ưu tiên, các tác vụ thường được gán theo mức độ ưu tiên của chúng. Đôi khi, việc thực thi một tác vụ có mức độ ưu tiên cao hơn trước một tác vụ có mức độ ưu tiên thấp hơn là rất quan trọng, ngay cả khi tác vụ có mức độ ưu tiên thấp hơn vẫn đang chạy. Tác vụ có mức độ ưu tiên thấp hơn sẽ tạm dừng trong một thời gian và tiếp tục khi tác vụ có mức độ ưu tiên cao hơn hoàn thành việc thực thi.

Lập kế hoạch không ưu tiên

Trong phương pháp lập lịch này, CPU được phân bổ cho một tiến trình cụ thể. Tiến trình nào chiếm dụng CPU nhiều nhất sẽ giải phóng CPU bằng cách chuyển đổi ngữ cảnh hoặc kết thúc. Đây là phương pháp duy nhất có thể sử dụng trên nhiều nền tảng phần cứng khác nhau, vì nó không cần phần cứng đặc biệt (ví dụ: bộ đếm thời gian) như lập lịch ưu tiên.

Khi nào thì lập lịch là ưu tiên và khi nào thì không ưu tiên?

Để xác định xem việc lập lịch là ưu tiên hay không ưu tiên, hãy xem xét bốn tham số sau:

1. Một tiến trình chuyển từ trạng thái đang chạy sang trạng thái chờ.
2. Một quy trình cụ thể chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng.
3. Một quy trình cụ thể chuyển từ trạng thái chờ sang trạng thái sẵn sàng.
4. Một tiến trình hoàn tất quá trình thực thi và kết thúc.

Nếu chỉ có điều kiện 1 và 4 được đáp ứng, việc lập lịch được gọi là không ưu tiên. Tất cả các trường hợp lập lịch khác đều là ưu tiên.

Các thuật ngữ quan trọng về lập lịch CPU

• Thời gian bùng nổ/Thời gian thực hiện: Thời gian cần thiết để một tiến trình hoàn tất quá trình thực thi. Nó còn được gọi là thời gian chạy.
• Thời gian đến: Thời điểm một tiến trình chuyển sang trạng thái sẵn sàng.
• Thời gian kết thúc: Thời điểm một tiến trình hoàn tất và thoát khỏi hệ thống.
• Đa chương trình: Một số chương trình có thể cùng tồn tại trong bộ nhớ tại một thời điểm.
• Việc làm: Một loại chương trình không có bất kỳ sự tương tác nào với người dùng.
• User: Một loại chương trình có tính tương tác với người dùng.
• Quá trình: Mã tham chiếu được sử dụng cho cả công việc và người dùng.
• Chu kỳ bùng nổ CPU/IO: Đặc trưng cho quá trình thực thi, trong đó hoạt động của CPU và I/O được luân phiên. Thời gian xử lý của CPU thường ngắn hơn thời gian xử lý của I/O.

Tiêu chí lập lịch CPU

Thuật toán lập lịch CPU cố gắng tối đa hóa và giảm thiểu những điều sau:

Tối đa hóa

Sử dụng CPU: Mức độ sử dụng CPU là nhiệm vụ chính mà hệ điều hành cần đảm bảo rằng CPU luôn hoạt động ở mức tối đa. Mức độ này có thể dao động từ 0 đến 100%. Tuy nhiên, đối với hệ điều hành thời gian thực (RTOS), nó có thể dao động từ 40% đối với hệ thống cấp thấp đến 90% đối với hệ thống cấp cao.

Throughput: Thông lượng là số lượng các tiến trình hoàn thành quá trình thực thi trong một đơn vị thời gian. Vì vậy, khi CPU đang bận thực thi một tiến trình, công việc đang được thực hiện, và công việc hoàn thành trong một đơn vị thời gian được gọi là thông lượng.

Giảm thiểu

Thời gian chờ: Thời gian chờ là khoảng thời gian mà một tiến trình cụ thể phải đợi trong hàng đợi sẵn sàng.

Thời gian đáp ứng: Đó là khoảng thời gian từ khi yêu cầu được gửi đi cho đến khi nhận được phản hồi đầu tiên.

Thời gian quay vòng: Thời gian hoàn thành là khoảng thời gian cần thiết để thực thi một quy trình cụ thể. Đó là tổng thời gian chờ đợi để được đưa vào bộ nhớ, chờ đợi trong hàng đợi và thực thi trên CPU. Khoảng thời gian giữa lúc gửi quy trình và lúc hoàn thành được gọi là thời gian hoàn thành.

Bộ hẹn giờ khoảng

Ngắt bộ định thời là một phương pháp có liên quan chặt chẽ đến quyền ưu tiên. Khi một quy trình nhất định được phân bổ CPU, bộ hẹn giờ có thể được đặt thành một khoảng thời gian được chỉ định. Cả việc ngắt bộ đếm thời gian và quyền ưu tiên đều buộc một tiến trình phải trả lại CPU trước khi đợt CPU của nó hoàn tất.

Hầu hết các hệ điều hành đa chương trình đều sử dụng một dạng bộ hẹn giờ nào đó để ngăn một tiến trình chiếm dụng hệ thống vĩnh viễn.

Người điều phối là gì?

Bộ điều phối là một mô-đun cung cấp quyền điều khiển CPU cho tiến trình. Bộ điều phối cần phải nhanh để có thể hoạt động trên mọi lần chuyển đổi ngữ cảnh. Độ trễ điều phối là khoảng thời gian cần thiết để bộ lập lịch CPU dừng một tiến trình và khởi động một tiến trình khác.

Các chức năng do người điều phối thực hiện:

• Chuyển đổi ngữ cảnh.
• Đang chuyển sang chế độ người dùng.
• Di chuyển đến đúng vị trí trong chương trình mới được tải.

Các loại lập lịch CPU Algorithms

Chủ yếu có sáu loại thuật toán lập lịch xử lý:

1. Đến trước phục vụ trước (FCFS)
2. Lập kế hoạch công việc ngắn nhất trước tiên (SJF)
3. Thời gian còn lại ngắn nhất
4. Lên lịch ưu tiên
5. Lập kế hoạch vòng tròn
6. Lập lịch xếp hàng đa cấp

Lập kế hoạch Algorithms

Đến trước thì phục vụ trước

FCFS là viết tắt của Đến trước thì phục vụ trướcĐây là thuật toán lập lịch CPU dễ nhất và đơn giản nhất. Trong loại thuật toán này, tiến trình yêu cầu CPU sẽ được cấp phát CPU trước. Phương pháp lập lịch này có thể được quản lý bằng hàng đợi FIFO.

Khi một tiến trình vào hàng đợi sẵn sàng, PCB (Khối điều khiển tiến trình) của nó được liên kết với phần cuối của hàng đợi. Vì vậy, khi CPU trở nên rảnh rỗi, nó sẽ được gán cho tiến trình ở đầu hàng đợi.

Đặc điểm của phương pháp FCFS

• Đây là thuật toán lập lịch không ưu tiên.
• Công việc luôn được thực hiện theo nguyên tắc ai đến trước được phục vụ trước.
• Nó rất dễ dàng để thực hiện và sử dụng.
• Tuy nhiên, phương pháp này có hiệu suất kém và thời gian chờ đợi chung khá cao.

Thời gian còn lại ngắn nhất

SRT là viết tắt của Shortest Remaining Time (Thời gian còn lại ngắn nhất). Nó còn được biết đến với tên gọi lập lịch ưu tiên SJF. Trong phương pháp này, tiến trình sẽ được phân bổ cho tác vụ gần hoàn thành nhất. Phương pháp này ngăn chặn một tiến trình ở trạng thái sẵn sàng mới hơn làm trì hoãn việc hoàn thành của một tiến trình cũ hơn.

Đặc điểm của phương pháp lập lịch SRT

• Phương pháp này chủ yếu được áp dụng trong môi trường xử lý theo lô, nơi cần ưu tiên các tác vụ ngắn.
• Đây không phải là phương pháp lý tưởng để triển khai trong một hệ thống dùng chung khi thời gian xử lý CPU cần thiết chưa được xác định.
• Mỗi tiến trình được liên kết với độ dài của khoảng thời gian sử dụng CPU tiếp theo, vì vậy hệ điều hành sử dụng các độ dài này để lên lịch cho tiến trình có thời gian thực thi ngắn nhất có thể.

Lập kế hoạch dựa trên mức độ ưu tiên

Lên lịch ưu tiên Đây là phương pháp lập lịch các tiến trình dựa trên mức độ ưu tiên. Trong phương pháp này, bộ lập lịch sẽ chọn các tác vụ để thực hiện theo thứ tự ưu tiên của chúng.

Lập lịch ưu tiên cũng giúp hệ điều hành thực hiện việc phân công ưu tiên. Các tiến trình có ưu tiên cao hơn sẽ được thực hiện trước, trong khi các tác vụ có cùng mức ưu tiên sẽ được thực hiện theo kiểu vòng tròn hoặc FCFS (First Come First First - đến trước được phục vụ trước). Mức độ ưu tiên có thể được quyết định dựa trên yêu cầu về bộ nhớ, thời gian và các yếu tố khác.

Lập kế hoạch vòng tròn

Đấu vòng tròn Đây là một trong những thuật toán lập lịch lâu đời và đơn giản nhất. Tên của thuật toán này xuất phát từ nguyên tắc luân phiên (round-robin), trong đó mỗi người lần lượt nhận được một phần bằng nhau của một thứ gì đó. Nó chủ yếu được sử dụng để lập lịch trong các hệ thống đa nhiệm. Phương pháp này giúp đạt được việc thực thi các tiến trình mà không bị "đói" tài nguyên.

Đặc điểm của lập kế hoạch Round-Robin

• Round robin là một mô hình lai hoạt động dựa trên xung nhịp.
• Thời gian dành riêng cho mỗi tác vụ cụ thể cần được xử lý nên ở mức tối thiểu. Tuy nhiên, thời gian này có thể khác nhau đối với các quy trình khác nhau.
• Nó hoạt động như một hệ thống chia sẻ thời gian, phản hồi cho từng tiến trình trong một khoảng thời gian giới hạn cụ thể.

Công việc ngắn nhất đầu tiên

SJF (Shortest Job First) là một thuật toán lập lịch trong đó tiến trình có thời gian thực thi ngắn nhất được chọn để thực thi tiếp theo. Phương pháp lập lịch này có thể là ưu tiên hoặc không ưu tiên. Nó giúp giảm đáng kể thời gian chờ trung bình cho các tiến trình khác đang chờ thực thi.

Đặc điểm của lập kế hoạch SJF

• Mỗi công việc đều gắn liền với một khoảng thời gian hoàn thành nhất định.
• Trong phương pháp này, khi CPU rảnh, tiến trình hoặc tác vụ tiếp theo có thời gian hoàn thành ngắn nhất sẽ được thực thi trước.
• Nó được triển khai với chính sách không ưu tiên.
• Thuật toán này hữu ích cho việc xử lý theo lô, trong đó việc chờ đợi các tác vụ hoàn thành không phải là vấn đề quan trọng.
• Nó giúp cải thiện hiệu suất công việc bằng cách thực hiện các công việc ngắn hơn trước, những công việc này thường có thời gian hoàn thành ngắn hơn.

Lập kế hoạch hàng đợi nhiều cấp

Thuật toán này chia hàng đợi sẵn sàng thành nhiều hàng đợi riêng biệt. Trong phương pháp này, các tiến trình được gán vào một hàng đợi dựa trên một thuộc tính cụ thể của tiến trình, chẳng hạn như độ ưu tiên của tiến trình, kích thước bộ nhớ, v.v.

Tuy nhiên, đây không phải là một thuật toán lập lịch độc lập, vì nó cần sử dụng các loại thuật toán khác để lập lịch cho các công việc.

Đặc điểm của việc lập lịch hàng đợi nhiều cấp

• Nên duy trì nhiều hàng đợi cho các quy trình có đặc điểm chung.
• Mỗi hàng đợi có thể có thuật toán lập lịch riêng biệt.
• Mỗi hàng đợi được gán một mức độ ưu tiên nhất định.

Mục đích của thuật toán lập lịch

Dưới đây là những lý do nên sử dụng thuật toán lập lịch:

• CPU sử dụng lập lịch để cải thiện hiệu quả của nó.
• Nó giúp bạn phân bổ nguồn lực giữa các quy trình cạnh tranh.
• Việc sử dụng đa chương trình giúp tối ưu hóa hiệu năng CPU.
• Các tiến trình cần được thực thi sẽ được giữ trong hàng đợi sẵn sàng.

Câu Hỏi Thường Gặp