Lập lịch CPU là gì?
Lập lịch CPU là một quá trình xác định quá trình nào sẽ sở hữu CPU để thực thi trong khi một quá trình khác đang bị tạm dừng. 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 không hoạt động, hệ điều hành ít nhất chọn một trong các quy trình có sẵn trong hàng đợi sẵn sàng để thực thi. Quá trình lựa chọn sẽ được thực hiện bởi bộ lập lịch CPU. Nó chọn một trong các quá trình trong bộ nhớ đã sẵn sàng để thực thi.
Trong hướng dẫn lập lịch CPU này, bạn sẽ học:
- Lập lịch CPU là gì?
- Các loại lập lịch CPU
- Các thuật ngữ lập lịch quan trọng của CPU
- Tiêu chí lập lịch CPU
- Bộ hẹn giờ khoảng
- Điều phối viên là gì?
- Các loại thuật toán lập lịch CPU
- Đến trước thì phục vụ trước
- Thời gian còn lại ngắn nhất
- Lập kế hoạch dựa trên mức độ ưu tiên
- Lập lịch vòng tròn
- Công việc ngắn nhất đầu tiên
- Lập lịch hàng đợi nhiều cấp độ
- Mục đích của thuật toán lập lịch trình
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 trước, các nhiệm vụ chủ yếu đượ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 được giữ 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 dự phòng trước
Trong loại phương pháp lập lịch này, CPU đã được cấp phát cho một quá 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 đổi 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ộ đếm thời gian) như lập lịch trước.
Khi nào thì lên lịch là Ưu tiên hay Không ưu tiên?
Để xác định xem lập lịch là ưu tiên hay không ưu tiên, hãy xem xét bốn thông số sau:
- Một tiến trình chuyển từ trạng thái đang chạy sang trạng thái chờ.
- Quy trình cụ thể chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng.
- Quy trình cụ thể chuyển từ trạng thái chờ sang trạng thái sẵn sàng.
- Quá trình đã hoàn tất quá trình thực thi và kết thúc.
Chỉ áp dụng các điều kiện 1 và 4, việc lập kế hoạch được gọi là không ưu tiên.
Tất cả các lịch trình khác đều được đặt trước.
Các thuật ngữ lập lịch quan trọng của CPU
- Burst Time / Execution Time: Là khoảng thời gian mà quy trình yêu cầu để 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: khi một quy 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ể có trong bộ nhớ cùng một lúc.
- Công việc: 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.
- Người dùng: Nó là một loại chương trình có sự tương tác của người dùng.
- Quy trình: Là tham chiếu được sử dụng cho cả công việc và người dùng.
- Chu kỳ cụm CPU / IO: Đặc trưng cho quá trình thực thi, 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: Sử dụng CPU là nhiệm vụ chính trong đó 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ể nằm trong khoảng từ 0 đến 100 phần trăm. Tuy nhiên, đối với RTOS, nó có thể nằm trong khoảng từ 40% đối với hệ thống cấp thấp và 90% đối với hệ thống cấp cao.
Thông lượng: Số lượng quá trình kết thúc quá trình thực thi trên một đơn vị thời gian được biết đến là Thông lượng. Vì vậy, khi CPU đang bận thực hiện tiến trình, tại thời điểm đó, công việc đang được thực hiện và công việc đượ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ờ đợi: Thời gian chờ đợi là một khoảng thời gian mà quy trình cụ thể cần phải chờ đợi trong hàng đợi sẵn sàng.
Thời gian phản hồi: Là khoảng thời gian mà yêu cầu được gửi cho đến khi phản hồi đầu tiên được tạo.
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ể. Nó là phép tính tổng thời gian chờ vào bộ nhớ, đợi trong hàng đợi và thực thi trên CPU. Khoảng thời gian giữa thời gian gửi quy trình đến thời điểm hoàn thành là thời gian quay vòng.
Bộ hẹn giờ khoảng
Ngắt hẹn giờ là một phương pháp có liên quan mật thiết đến quyền ưu tiên. Khi một quy trình nhất định được phân bổ CPU, một bộ đếm thời gian có thể được đặt thành một khoảng thời gian cụ thể. Cả ngắt bộ hẹn giờ và chế độ ưu tiên đều buộc một quá trình trả lại CPU trước khi quá trình nổ CPU hoàn tất.
Hầu hết các hệ điều hành đa lập trình sử dụng một số dạng bộ đếm thời gian để ngăn một quá trình buộc hệ thống mãi mãi.
Điều phối viên là gì?
Nó là một mô-đun cung cấp quyền kiểm soát của CPU đối với quá trình. Dispatcher phải nhanh để nó có thể chạy trên mọi công tắc ngữ cảnh. Độ trễ của công văn là khoảng thời gian cần thiết của bộ lập lịch CPU để dừng một quá trình và bắt đầu một quá trình khác.
Các chức năng do Điều phối viên thực hiện:
- Chuyển đổi ngữ cảnh
- Chuyển sang chế độ người dùng
- Di chuyển đến vị trí chính xác 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 quy trình
- Đến trước phục vụ trước (FCFS)
- Lập kế hoạch cho công việc ngắn nhất (SJF)
- Thời gian còn lại ngắn nhất
- Lên lịch ưu tiên
- Lên lịch Round Robin
- Lập lịch hàng đợi đa cấp
Đến trước thì phục vụ trước
First Come First Serve là hình thức đầy đủ của FCFS. Đâ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, quá trình yêu cầu CPU sẽ được cấp phát CPU đầu 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 quá trình) của nó được liên kết với phần đuôi của hàng đợi. Vì vậy, khi CPU trở nên trống, nó nên đượ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 không ưu tiên và ưu tiên trước.
- Công việc luôn được thực hiện trên cơ sở ai đến trước được phục vụ trước
- Nó rất dễ thực hiện và sử dụng.
- Tuy nhiên, phương pháp này hiệu quả kém, thời gian chờ đợi chung là khá cao.
Thời gian còn lại ngắn nhất
Dạng đầ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 lịch trước SJF. Trong phương pháp này, tiến trình sẽ được phân bổ cho nhiệm vụ gần nhất với việc hoàn thành của nó. Phương pháp này ngăn quá trình trạng thái sẵn sàng mới hơn giữ quá trình hoàn thành quá 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 hàng loạt, nơi ưu tiên các công việc ngắn hạn.
- Đây không phải là một phương pháp lý tưởng để thực hiện nó trong một hệ thống chia sẻ mà thời gian CPU cần thiết là không xác định.
- Liên kết với mỗi quá trình khi độ dài của lần nổ 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ập lịch 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ập 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, bộ lập lịch biểu chọn các tác vụ để làm việc theo mức độ ưu tiên.
Việc lập lịch ưu tiên cũng giúp HĐH liên quan đến các nhiệm vụ ưu tiên. Các quy trình có mức độ ưu tiên cao hơn nên được thực hiện đầu tiên, trong khi các công việc có mức độ ưu tiên ngang nhau được thực hiện theo 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 lịch vòng tròn
Round robin là thuật toán lập lịch biểu lâu đời nhất, đơn giản nhất. Tên của thuật toán này xuất phát từ nguyên tắc vòng tròn, 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 cho các thuật toán lập lịch 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ị chết đói.
Đặc điểm của lập lịch vòng tròn
- Round robin là một mô hình hybrid được điều khiển bằng đồng hồ
- Phần thời gian phải là tối thiểu, được chỉ định cho một tác vụ cụ thể sẽ được xử lý. Tuy nhiên, nó có thể khác nhau đối với các quy trình khác nhau.
- Đó là một hệ thống thời gian thực phản hồi 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 đó quá 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ể là ưu tiên hoặc không ưu tiên. Nó làm giảm đáng kể thời gian chờ đợi trung bình cho các quy 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, quá 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 hiện trước.
- Nó được thực hiện với chính sách không phủ đầu.
- Phương pháp thuật toán này hữu ích cho quá trình xử lý kiểu hàng loạt, trong đó việc chờ đợi các 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, nê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 lị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 quá trình được gán cho một hàng đợi dựa trên một thuộc tính cụ thể của quá trình, như mức độ ưu tiên của quá trình, kích thước của bộ nhớ, v.v.
Tuy nhiên, đây không phải là một thuật toán hệ điều hành 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 công việc.
Đặc điểm của lập lị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 biệt.
- Các ư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 trình
Dưới đây là những lý do để 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ổ tài nguyên giữa các quy trình cạnh tranh.
- Việc sử dụng CPU tối đa có thể đạt được với đa lập trình.
- Các quy trình sẽ được thực hiện ở trong hàng đợi sẵn sàng.
Tóm lược:
- Lập lịch CPU là một quá trình xác định quá trình nào sẽ sở hữu CPU để thực thi trong khi một quá trình khác đang bị tạm dừng.
- Trong Lập lịch trước, các nhiệm vụ chủ yếu đượ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 cấp phát cho một quy trình cụ thể.
- Burst time là khoảng thời gian cần thiết để quá trình hoàn tất việc thực thi. Nó còn được gọi là thời gian chạy.
- Sử dụng CPU là nhiệm vụ chính trong đó 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 các quy trình hoàn thành việc thực thi của chúng trên một đơn vị thời gian được biết đến là Thông lượng.
- Thời gian chờ đợi là một khoảng thời gian mà quy 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 phản hồi đầu tiên được tạo ra.
- Thời gian quay vòng là khoảng thời gian để thực hiện một quy trình cụ thể.
- Ngắt bộ hẹn giờ là một phương pháp có liên quan chặt chẽ đến quyền ưu tiên,
- Điều phối viên là một mô-đun cung cấp quyền kiểm soát của CPU đối với quá trình.
- Sáu loại thuật toán lập lịch trình là:
- Lần đến trước phục vụ trước (FCFS), 2) Lập kế hoạch ngắn nhất cho công việc đầu 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 lịch vòng tròn 6) Lập lịch hàng đợi đa cấp
- Trong phương thức First Come First Serve, quá trình yêu cầu CPU nhận được phân bổ CPU đầu tiên.
- 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 với việc hoàn thành nhất.
- Trong, Lập lịch ưu tiên, bộ lập lịch chọn các nhiệm vụ để làm việc theo mức độ ưu tiên.
- Trong đó, lập lịch Vòng tròn này hoạt động theo nguyên tắc, 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ì đó
- Trong công việc ngắn nhất, thời gian thực hiện ngắn nhất nên được chọn để thực hiện tiếp theo
- Trong lập lịch Đa cấp, phương thức tách hàng đợi sẵn sàng thành các 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 cho một 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ó.