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

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

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

Lập lịch trước

Trong Lập kế hoạch ưu tiên, các nhiệm vụ hầu hết được giao với mức độ ưu tiên của chúng. Đôi khi điều quan trọng là phải chạy 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 khác, ngay cả khi tác vụ có mức độ ưu tiên thấp hơn vẫn đang chạy. Nhiệm vụ có mức độ ưu tiên thấp hơn sẽ được giữ trong một thời gian và tiếp tục lại khi nhiệm 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 loại phương pháp lập lịch này, CPU đã được phân bổ cho một quy trình cụ thể. Quá trình giữ cho CPU bận rộn sẽ giải phóng CPU bằng cách chuyển ngữ cảnh hoặc kết thúc. Đây là phương pháp duy nhất có thể được sử dụng cho các nền tảng phần cứng khác nhau. Đó là bởi vì nó không cần phần cứng đặc biệt (ví dụ: bộ hẹn giờ) như lập lịch ưu tiên.

Khi nào việc lập kế hoạch là Ưu tiên hay Không ưu tiên?

Để xác định xem việc lập lịch trình 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. Quá trình cụ thể chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng.
3. Quá trình cụ thể chuyển từ trạng thái chờ sang trạng thái sẵn sàng.
4. Quá trình kết thúc việc thực hiện và chấm dứt.

Chỉ áp dụng điều kiện 1 và 4, việc lập lịch được gọi là không ưu tiên.

Tất cả các lịch trình khác đều được ưu tiên.

Thuật ngữ lập kế hoạch CPU quan trọng

• Thời gian bùng nổ/Thời gian thực hiện: Đó là thời gian mà tiến trình yêu cầu để hoàn thành việc thực thi. Nó còn được gọi là thời gian chạy.
• Thời gian đến: khi một tiến trình đi vào trạng thái sẵn sàng
• Thời gian kết thúc: khi quá 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ể hiện diện đồng thời trong bộ nhớ.
• Việc làm: Nó là một loại chương trình không có bất kỳ loại tương tác nào của người dùng.
• User: Nó là một loại chương trình có sự tương tác của người dùng.
• Quá trình: Nó là tài liệu tham khảo đượ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 việc thực hiện quy trình, luân phiên giữa hoạt động của CPU và I/O. Thời gian của CPU thường ngắn hơn thời gian 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:Việ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 bận rộn nhất có thể. Nó có thể dao động từ 0 đến 100 phần trăm. Tuy nhiên, đối với RTOS, nó có thể dao động từ 40% đối với hệ thống cấp thấp và 90% đối với hệ thống cấp cao.

Throughput: Số lượng quy trình hoàn thành quá trình thực hiện của chúng trên một đơn vị thời gian được biết đến Thông lượng. Vì vậy, khi CPU bận thực thi tiến trình, lúc đó công việc đang được thực hiện và công việc hoàn thành trên 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à lượng mà tiến trình cụ thể cần đợi trong hàng đợi sẵn sàng.

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

Thời gian quay vòng: Thời gian quay vòng là khoảng thời gian để thực hiện một quy trình cụ thể. Đó là phép tính tổng thời gian chờ để vào bộ nhớ, chờ trong hàng đợi và thực thi trên CPU. Khoảng thời gian từ khi gửi quy trình đến khi hoàn thành là thời gian quay vòng.

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 hệ điều hành đa chương trình đều sử dụng một số dạng bộ hẹn giờ để ngăn quá trình buộc hệ thống mãi mãi.

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

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

Các chức năng được thực hiện bởi Dispatcher:

• Chuyển đổi ngữ cảnh
• 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 thuật toán lập lịch CPU

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

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

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

Khi tiến trình đi 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 rảnh, nó sẽ được gán cho tiến trình ở đầu hàng đợi.

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

• Nó cung cấp thuật toán lập lịch trình không ưu tiên và ư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

Hình thức đầy đủ của SRT là Thời gian còn lại ngắn nhất. Nó còn được gọi là lập kế hoạch ưu tiên SJF. Trong phương pháp này, quy trình sẽ được phân bổ cho nhiệm vụ gần hoàn thành nhất. Phương pháp này ngăn không cho một quy trình trạng thái sẵn sàng mới hơn giữ quá trình hoàn thành của một quy trình cũ hơn.

Đặc điểm của phương pháp lập kế hoạch SRT

• Phương pháp này chủ yếu được áp dụng trong môi trường hàng loạt, trong đó các công việc ngắn cần được ưu tiên.
• Đây không phải là phương pháp lý tưởng để triển khai nó trong một hệ thống dùng chung nơi không xác định được thời gian CPU cần thiết.
• Liên kết với mỗi tiến trình theo độ dài của chu kỳ CPU tiếp theo của nó. Vì vậy, hệ điều hành đó sử dụng các độ dài này, giúp lên lịch cho quá trình với thời gian 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 là một phương pháp lập lịch trình dựa trên mức độ ưu tiên. Trong phương pháp này, người lập lịch sẽ chọn các tác vụ để thực hiện theo mức độ ưu tiên.

Lập kế hoạch ưu tiên cũng giúp HĐH thực hiện các nhiệm vụ ưu tiên. Các quy trình có mức độ ưu tiên cao hơn sẽ được thực hiện trước, trong khi các công việc có mức độ ưu tiên bằng nhau sẽ được thực hiện trên cơ sở vòng tròn hoặc FCFS. Mức độ ưu tiên có thể được quyết định dựa trên yêu cầu về bộ nhớ, yêu cầu về thời gian, v.v.

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

Round robin là thuật toán lập lịch lâu đời nhất 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 quay vòng, trong đó mỗi người lần lượt nhận được phần bằng nhau của một thứ gì đó. Nó chủ yếu được sử dụng để lập lịch các thuật toán trong đa nhiệm. Phương pháp thuật toán này giúp thực hiện các quy trình không bị đói.

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

• Round robin là một mô hình kết hợp được điều khiển bằng đồng hồ
• Khoảng thời gian phải ở mức tối thiểu, được chỉ định cho một tác vụ cụ thể cần được xử lý. Tuy nhiên, nó có thể khác nhau đối với các quy trình khác nhau.
• Đây là một hệ thống thời gian thực đáp ứng sự kiện trong một giới hạn thời gian cụ thể.

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

SJF là một dạng đầy đủ của (Công việc ngắn nhất trước) là một thuật toán lập lịch trong đó quy trình có thời gian thực hiện ngắn nhất sẽ được chọn để thực hiện tiếp theo. Phương pháp lập kế hoạch này có thể được ưu tiên hoặc không được ưu tiên. Nó làm 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

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

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

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

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

Đặc điểm của lập kế hoạch hàng đợi nhiều cấp

• Nhiều hàng đợi nên được duy trì cho các quy trình có một số đặc điểm.
• Mỗi hàng đợi có thể có các thuật toán lập lịch riêng.
• Ưu tiên được đưa ra cho mỗi hàng đợi.

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 CPU tối đa có thể đạt được bằng cách lập trình đa chương trình.
• Các tiến trình sẽ được thực thi đang ở trong hàng đợi sẵn sàng.

Tổng kết

• Lập lịch CPU là một 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 bị tạm dừng.
• Trong Lập kế hoạch ưu tiên, các nhiệm vụ hầu hết được giao với mức độ ưu tiên của chúng.
• Trong phương pháp lập lịch không ưu tiên, CPU đã được phân bổ cho một quy trình cụ thể.
• Thời gian bùng nổ là thời gian cần thiết để quá trình thực hiện hoàn tất. Nó còn được gọi là thời gian chạy.
• Việ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 bận rộn nhất có thể.
• Số lượng quy trình hoàn thành quá trình thực hiện của chúng trên một đơn vị thời gian được biết đến Thông lượng.
• Thời gian chờ là lượng mà một tiến trình cụ thể cần phải đợi trong hàng đợi sẵn sàng.
• Đó là khoảng thời gian mà yêu cầu được gửi cho đến khi có phản hồi đầu tiên.
• Thời gian quay vòng là lượng thời gian để thực hiện một quy trình cụ thể.
• 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.
• Bộ điều phối là một mô-đun cung cấp khả năng điều khiển CPU cho quy trình.
• Sáu loại thuật toán lập lịch trình quy trình là: Đế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 (SJF), 3) Thời gian còn lại ngắn nhất, 4) Lập kế hoạch ưu tiên, 5) Lập kế hoạch vòng tròn, 6) Lập kế hoạch xếp hàng đa cấp .
• Trong tạp chí Phương pháp đến trước phục vụ trước, quá trình yêu cầu CPU sẽ được phân bổ CPU trước.
• Trong Thời gian còn lại ngắn nhất, quy trình sẽ được phân bổ cho nhiệm vụ gần hoàn thành nhất.
• Trong Lập kế hoạch ưu tiên, người lập lịch sẽ chọn các nhiệm vụ để thực hiện theo mức độ ưu tiên.
• Lập lịch quay vòng hoạt động dựa trên nguyên tắc mỗi người lần lượt nhận được một phần bằng nhau về một thứ gì đó.
• Trong công việc Ngắn nhất trước tiên, nên chọn thời gian thực hiện ngắn nhất để thực hiện tiếp theo.
• Phương pháp lập lịch đa cấp tách 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 hàng đợi dựa trên một thuộc tính cụ thể.
• CPU sử dụng lập lịch để cải thiện hiệu quả của nó.