Việc lập lịch cho CPU CPU Scheduling là tiến trình chuyển từ trạng thái nào sang trạng thái nào
|
Show
 NộI Dung:
Sự khác biệt chính - Lập lịch công việc so với Lập lịch CPUTiến trình là một chương trình đang được thực thi. Có nhiều tiến trình chạy song song trong một hệ thống máy tính. Điều quan trọng là tối đa hóa việc sử dụng CPU. Hệ điều hành có thể làm cho máy tính hoạt động hiệu quả bằng cách chuyển đổi CPU giữa các tiến trình. Để sử dụng CPU tối đa, điều quan trọng là phải chạy một số quy trình mọi lúc. Các quy trình sẽ thực thi được đặt trong hàng đợi sẵn sàng. Lập kế hoạch công việc là cơ chế để chọn quy trình phải được đưa vào hàng đợi sẵn sàng. Lập lịch cho CPU là cơ chế để chọn tiến trình phải được thực hiện tiếp theo và phân bổ CPU cho tiến trình đó. Đó là sự khác biệt chính giữa Lập lịch công việc và Lập lịch CPU. Lập lịch công việc được gọi là lập lịch dài hạn trong khi lập lịch CPU được gọi là lập lịch ngắn hạn. Việc lập kế hoạch công việc được thực hiện bởi người lập lịch công việc hoặc người lập lịch dài hạn. Việc lập lịch CPU được thực hiện bởi bộ lập lịch CPU hoặc bộ lập lịch ngắn hạn. 1. Tổng quan và sự khác biệt chính 2. Lên lịch công việc là gì 3. Lập lịch CPU là gì 4. Điểm giống nhau giữa Lập lịch công việc và Lập lịch CPU 5. So sánh song song - Lập lịch công việc và Lập lịch CPU ở dạng bảng 6. Tóm tắt Lên lịch công việc là gì?Có thể có nhiều quy trình trong hệ thống cùng một lúc. Có thể không thực hiện chúng đúng hạn. Do đó, các quy trình đó được đặt trong bộ nhớ hoặc nhóm công việc để chúng có thể được thực thi sau này. Lập lịch công việc là cơ chế để chọn các quy trình từ bộ lưu trữ này và đưa chúng vào hàng đợi sẵn sàng. Nhiệm vụ này được thực hiện bởi người lập lịch công việc hoặc người lập lịch dài hạn. Nói chung, việc gọi ra Trình lập lịch dài hạn cần có thời gian. Có thể mất vài giây hoặc vài phút. Tần số tỉ lệ nghịch với thời gian. Do đó, tần suất của Bộ lập lịch công việc để chọn một quy trình từ nhóm công việc là tối thiểu so với bộ lập lịch ngắn hạn. Một mục tiêu chính của lập trình đa chương trình là duy trì chạy các quy trình mọi lúc để sử dụng CPU tối đa. Vì vậy, cơ chế lập lịch công việc kiểm soát mức độ đa chương trình. Nó cũng ảnh hưởng đến quá trình chuyển đổi trạng thái. Quá trình chuyển từ trạng thái mới sang trạng thái sẵn sàng do lên lịch công việc hoặc lập lịch dài hạn. Lập lịch CPU là gì?Theo Lịch trình công việc, có một số quy trình có sẵn trong hàng đợi công việc. Lập lịch cho CPU là cơ chế để chọn tiến trình phải được thực hiện tiếp theo và phân bổ CPU cho tiến trình đó. Tác vụ này được thực hiện bởi Bộ lập lịch CPU hoặc bộ lập lịch ngắn hạn. Nó gọi khi các sự kiện như khi đồng hồ ngắt, I / O ngắt và các cuộc gọi Hệ điều hành xảy ra. Nói chung, bộ lập lịch CPU thường xuyên được gọi. Thời gian dành cho lập lịch CPU tính bằng mili giây, vì vậy tần suất gọi cao hơn so với bộ lập lịch công việc. Nói chung, bộ lập lịch CPU có quyền kiểm soát tối thiểu mức độ đa chương trình hơn bộ lập lịch công việc. Nó cũng ảnh hưởng đến quá trình chuyển đổi trạng thái. Quá trình đạt đến trạng thái đang chạy từ trạng thái sẵn sàng do Lập lịch CPU hoặc lập lịch ngắn hạn. Sự giống nhau giữa Lập lịch công việc và Lập lịch CPU là gì?
Sự khác biệt giữa Lập lịch công việc và Lập lịch CPU là gì?
Tóm lược -Lập lịch công việc so với Lập lịch CPUCó nhiều quy trình trong một hệ thống máy tính. Một chương trình đang thực thi được gọi là một quá trình. Cần phải chạy một quá trình luôn luôn để tối đa hóa việc sử dụng CPU. Lập lịch công việc và Lập lịch CPU được liên kết với việc thực hiện quy trình. Lập kế hoạch công việc là cơ chế để chọn quy trình phải được đưa vào hàng đợi sẵn sàng. Lập lịch cho CPU là cơ chế để chọn tiến trình phải được thực hiện tiếp theo và phân bổ CPU cho tiến trình đó. Đó là sự khác biệt giữa Lập lịch công việc và Lập lịch CPU. Lập lịch tiến trình là một trong những công việc quan trọng của tiến trình: đánh giá và sắp xếp xem tiến trình nào chạy trước, tiến trình nào chạy sau, chạy trong thời gian bao lâu (timeslice) hoặc có nên dừng tiến trình hiện tại để thực thi tiến trình khác mà nó thấy quan trọng hơn. Mục đích của việc này là đảm bảo các tiến trình yêu cầu đều được thực thi lần lượt mà vẫn đem lại trải nghiệm tốt cho người dùng. Trong hệ điều hành Linux, lập lịch được tiến hành bởi Linux kernel dựa trên việc phân loại và và xem xét tính chất, quá trình hoạt động của từng tiến trình. Phân loại tiến trìnhĐể lập lịch cho tiến trình, việc đầu tiên là phải phân loại được các tiến trình trong hệ thống, từ đó mới đưa ra quyết định hợp lý cho các loại tiến trình. Linux phân loại tiến trình dựa theo đặc điểm hoạt động của tiến trình theo một trong hai loại: I/O-Bound process và Processor-Bound process. I/O-Bound process: là tiến trình sử dụng phần lớn thời gian cho việc chờ các hoạt động input/output (chờ client socket gửi data hoặc chờ dữ liệu nhập từ bàn phím). Điển hình cho các tiến trình dạng I/O-Bound như các ứng dụng graphic user interface (GUI), vì chúng dành phần lớn thời gian để chờ người dùng nhập dữ liệu từ bàn phím hoặc chuột. Processor-Bound process: là tiến trình sử dụng phần lớn thời gian của CPU để thực thi mã lệnh. Ví dụ cho loại tiến trình này là các chương trình compile source code như gcc, g++... Với các tiến trình lọai này, hệ điều hành có xu hướng không chạy chúng quá thường xuyên (vì chúng không hoặc rất ít chờ các hoạt động I/O) nhưng mỗi lần chạy với thời gian dài hơn. Cách phân loại trên dựa vào đặc điểm và lịch sử hoạt động của tiến trình. Vì vậy một tiến trình có thể là I/O-bound hoặc là processor-bound, hoặc trong từng thời điểm có thể là I/O-bound hoặc Processor-bound. Trong quá trình phát triển, Linux kernel hỗ trợ tiến trình real-time, vì vậy trong cuốn Understanding Linux Kernel, tiến trình được phân loại như sau: Real-time Process (Tiến trình real-time): là các tiến trình yêu cầu đáp ứng lập lịch một cách nghiêm ngặt để đảm bảo xử lý và tốc độ phản hồi ở mức độ thời gian thực. Ví dụ của tiến trình real-time như các phần mềm liên quan đến xử lý phanh tự động hoặc túi khi của xe hơi, các phần mềm chỉ đường…Các tiến trình này cần được Linux kernel “đối xử” ưu tiên khi lập lịch như: độ ưu tiên cao hơn và có thể giành quyền thực thi với bất kỳ tiến trình khác có độ ưu tiên thấp, không bị các tiến trình ưu tiên thấp giành quyền trừ khi nó tự “nhả” CPU. Normal Process (Tiến trình thường): là các tiến trình không đòi tốc độ phản hồi real-time, nên có độ ưu tiên thấp hơn tất cả các tiến trình real-time trong hệ thống. Một normal process được chia thành 2 loại sau:
Trong hệ điều hành Linux, việc phân loại các tiến trình được dựa theo hệ số ưu tiên Process priority của mỗi tiến trình. Process priorityLập lịch theo chỉ số ưu tiên của tiến trình (priority-base) là một phương pháp phổ biến ở các hệ điều hành, bao gồm cả hệ điều hành Linux. Theo đó mỗi tiến trình sẽ có hệ số priority khác nhau, hệ điều hành căn cứ vào priority để đánh gía xem tiến trình nào “xứng đáng” được chạy tiếp theo và thời gian cấp cho tiến trình đó là bao lâu. Tuy nhiên, mỗi hệ điều hành khác nhau cũng sử dụng hệ số process-priority theo cách khác nhau Về cơ bản, tiến trình nào có priority cao hơn sẽ được chạy trước, các tiến trình có độ ưu tiên bằng nhau được lập lịch chia sẻ thời gian với nhau tùy vào chính sách lập lịch của mỗi tiến trình. Hệ điều hành Linux cung cấp 2 loại priority: nice value cho các normal process và real-time priority cho các real-time process. Nice valueMỗi tiến trình có một thuộc tính là nice value, nằm trong khoảng từ -20 (ưu tiên cao nhất) đến 19 (ưu tiên thấp nhất), nice value mặc định của mỗi tiến trình là 0. Mặc dù nice value được áp dụng cho các hệ điều hành Unix, nhưng mức độ ảnh hưởng của nice value trên mỗi hệ điều hành không giống nhau tùy thuộc vào từng giải thuật lập lịch. Ví dụ với hệ điều hành Mac OS X, nice value dùng để quyết định thời gian cố định được cấp (timeslice) cho mỗi tiến trình. Với Linux, nice value không quyết định timeslice cố định cho một tiến trình, mà là một trọng số ảnh hưởng đến timeslice, nghĩa nice value càng nhỏ (priority cao) thì timeslice được cấp cho tiến trình càng lớn. Real-time priorityReal-time priority được dùng cho real-time process và có dải từ 0 (độ ưu tiên cao nhất) đến 99 (độ ưu tiên thấp nhất). Trong Linux, tiến trình real-time có priority thấp hơn (độ ưu tiên cao hơn) sẽ được chạy trước. Lưu ý rằng 2 khái niệm nice value và real-time priority trên là thuật ngữ của user space, trong khi lập lịch lại là 1 subsystem của Linux kernel. Linux kernel sử dụng một bảng process priority duy nhất từ 0-139; trong đó priorty từ 0-99 cho real-time process và từ 100-139 ứng với nice value từ -20 đến 19 cho normal process. Cụ thể như hình vẽ dưới đây: Hình 1. Process priority trong Linux kernel Như vậy ta thấy rằng, real-time process luôn luôn có hệ số priority thấp hơn (độ ưu tiên cao hơn) normal process và hiển nhiên sẽ được lập lịch ưu tiên so với normal process. Trong các phần sau của bài viết, để đồng nhất chúng ta sẽ dùng độ ưu tiên của tiến trình với quy chuẩn: hệ số priority thấp hơn đồng nghĩa với độ ưu tiên cao hơn. Các thông số priority của tiến trình có thể được kiểm tra bằng câu lệnh “top”, cụ thể như sau:
Hình 2. Linux process priority bằng câu lệnh “top” Trong hình vẽ trên, cột PR là process priority, NI là nice value của tiến trình. Tiến trình với PR ký hiệu “rt” là real-time process, ta thấy hiển nhiên rằng đó đều là các tiến trình rất quan trọng của Linux như watchdog, migration…Lưu ý rằng giá trị priority trong cột PR là giá trị trên góc nhìn của user, giá trị này được tính bằng công thức sau: PR = 20 + NI Để map priority với kernel, ta dùng công thức sau: Kernel priority = 100 + 20 +NI Xét ví dụ của tiến trình kthreadd, nice value NI = 0 (nice value mặc định) tương ứng với priority PR = 20 và Kernel priority = 120 (kernel priority mặc định) đúng với khoảng giá trị ở hình 1. Scheduling PolicyCơ chế lập lịch cho tiến trình của Linux được thực hiện bởi 2 thông số ứng với mỗi tiến trình: process priority và scheduling policy. Scheduling policy giúp hệ điều hành quyết định xem tiến trình được chạy bao lâu và khi nào phải nhường quyền chạy cho tiến trình khác. Hệ điều hành Linux có các scheduling policy cho việc hỗ trợ lập lịch cho real-time process gồm SCHED_FIFO, SCHED_RR; cho normal process: SCHED_NORMAL, SCHED_IDLE và SCHED_BATCH. Scheduling policy cho real-time processSCHED_RR (round-robin)Với cơ chế SCHED_RR, các tiến trình chạy tuân theo cơ chế round-robin (time-sharing): mỗi tiến trình được cấp một khoảng thời gian (hay khe thời gian) cố định được gọi là time slice. Khi một tiến trình chạy, nó sẽ chiếm giữ CPU cho đến khi xảy ra một trong các sự kiện sau:
Với trường hợp 1 và 2 ở trên, tiến trình sau khi bị mất quyền chiếm giữ CPU sẽ bị đẩy vào cuối của queue với cùng các tiến trình cùng priority khác. Với trường hợp 4, tiến trình bị chiếm quyền được đẩy vào đầu của queue, sau khi tiến trình độ ưu tiên cao hơn chạy hết time slice, nó sẽ tiếp tục thực thi cho đến khi đi hết time slice của mình. SCHED_FIFO (first in- first out)Chính sách SCHED_FIFO khác SCHED_RR ở điểm là không sử dụng time slice. Theo đó tiến trình đang chiếm dụng CPU sẽ tiếp tục chạy cho đến khi có một trong các sự kiện sau:
Trong trường hợp 1, tiến trình sau khi bị chiếm quyền sẽ bị đẩy vào cuối queue của các tiến trình cùng priority. Với trường hợp 3, tiến trình bị chiếm quyền được đẩy vào đầu của queue, sau khi tiến trình có độ ưu tiên cao hơn dừng chiếm dụng CPU, nó sẽ tiếp tục thực thi. Như vậy, tổng kết với 2 scheduling policy SCHED_RR và SCHEF_FIFO cho real-time process, tiến trình đang chạy bị chiếm quyền trong các trường hợp sau:
Scheduling policy cho normal processSCHED_NORMALTrong tiêu chuẩn Posix, SCHED_NORMAL còn được gọi là SCHED_OTHER, là scheduling policy mặc định cho các tiến trình không đòi hỏi cơ chế real-time (normal process). SCHED_NORMAL policy tuân thủ cơ chế hoạt động chia sẻ thời gian (time-sharing) round-robin tương tự chính sách SCHED_RR. Điểm khác biệt là SCHED_NORMAL không fix cứng time slice cho mỗi tiến trình mà độ dài time slice của tiến trình thay đổi theo tính toán của bộ lập lịch của Linux kernel. Cụ thể, time slice sẽ phụ thuộc vào 2 yếu tố: nice value (nice value càng thấp (ví dụ -20) thì time slice càng cao) và thời gian chờ của tiến trình (tiến trình ở trạng thái runable mà đang chờ đến lượt chạy càng lâu thì time slice càng nhiều). Cơ chế tính time slice này đảm bảo độ công bằng (fair) giữa tất cả các normal process trong hệ thống. SCHED_BATCHScheduling policy SCHED_BATCH được đưa vào Linux kerne từ version 2.6.16, có thể dùng để lập lịch cho các batch process. Chính sách này tương tự như SCHED_NORMAL, chỉ khác một điểm là các tiến trình SCHED_BATCH sẽ ít được đánh thức để xem xét lập lịch hơn các tiến trình SCHED_NORMAL. SCHED_IDLEScheduling policy SCHED_IDLE được đưa vào Linux kernel từ version 2.6.23. Chính sách lập lịch này cũng tương tự như policy SCHED_NORMAL nhưng làm cho tiến trình có độ ưu tiên (tương đương với nice value) rất thấp. Nice value không có ý nghĩa gì với policy này. Có thể nói các tiến trình có scheduling policy này có độ ưu tiên thấp hơn các tiến trình SCHED_NORMAL thông thường, nó chỉ được lập lịch khi không còn normal process nào yêu cầu chạy. Lập lịch trong Hệ điều hành LinuxCác phần trên của bài viết đã giải thích các khái niệm cơ bản cho việc lập lịch cho các tiến trình. Bây giờ chúng ta sẽ tìm hiểu cụ thể Linux sử dụng các khái niệm trên cho việc lập lịch như thế nào. Như đã nói ở các phần trên, Linux chia các tiến trình làm 2 loại: real-time process và normal process. Cơ chế lập lịch cho các tiến trình real-time (priority từ 0 đến 99) dựa theo tham số priority khá rõ ràng. Với normal process, cơ chế lập lịch phức tạp hơn và có khác nhau đôi chút phụ thuộc vào bộ lập lịch được áp dụng trong Linux kernel. Bộ lập lịch chung cho các normal process hiện nay trong Linux là Completely Fair Scheduler (CFS), đây là chính sách mặc định được triển khai trên Linux kernel từ version 2.6.23. Trong Linux kernel, process scheduler hoạt động như một module, ở đặc điểm nó cho phép nhiều scheduling policy cùng tồn tại với các loại tiến trình khác nhau. Trong scheduling module của Linux có một vòng lặp với từng tiến trình để xét xem nó thuộc schedule class nào, việc xét duyệt dựa vào process priority. Với các tiến trình có priority từ 0 đến 99 sẽ thuộc real-time schedule class, cơ chế lập lịch là SCHED_RR hoặc SCHED_FIFO. Với các tiến trình có priority từ 100-140 sẽ thuộc CFS schedule class, với cơ chế lập lịch là SCHED_NORMAL hoặc SCHED_BATCH hoặc SCHED_IDLE. Kết luậnSau bài học này, chúng ta nắm được các khái niệm cơ bản của process scheduling, một trong những công việc quan trọng của bất kỳ hệ điều hành nào nhằm hướng đến phục vụ đa tiến trình và đảm bảo performance của hệ thống. Hệ điều hành Linux lập lịch theo cơ chế priority base với ưu điểm là phân loại được độ quan trọng của các tiến trình, qua đó hỗ trợ được các tiến trình đòi hỏi real-time. Cơ chế lập lịch mặc định với các normal process hiện nay của Linux là Completely Fair Scheduler được áp dụng chính thức từ version 2.6.23 đã khắc phục được nhiều nhược điểm về tính công bằng (fair) so với các cơ chế trước đó. Trong bài học sau chúng ta sẽ tìm hiểu cách Linux sử dụng và quản lý thread. Tài liệu tham khảoLinux Programming Interface-Michael Kerrisk – Chapter 35 Mastering Linux Kernel Development : A kernel developer’s reference manual – Raghu Bharadwaj – Chapter 2 Linux kernel development-Robert Love- Chapter 4 https://www.youtube.com/watch?v=vF3KKMI3_1s&t=361s |
