Việc lập lịch cho CPU là tiến trình chuyển từ trạng thái
|
Trong các hệ thống lập trình đơn như MS DOS, khi một tiến trình chờ bất kỳ hoạt động I / O nào được thực hiện, CPU vẫn là thần tượng. Đây là một khoản phí lớn vì nó lãng phí thời gian và gây ra vấn đề chết đói. Tuy nhiên, trong hệ thống Đa chương trình, CPU không ở trạng thái nghỉ trong thời gian chờ của Quy trình và nó bắt đầu thực hiện các quy trình khác. Hệ điều hành phải xác định quá trình CPU sẽ được cung cấp. Show
Trong các hệ thống Đa chương trình, Hệ điều hành lập lịch trình cho các quá trình trên CPU để sử dụng nó tối đa và thủ tục này được gọi là lập lịch cho CPU . Hệ điều hành sử dụng các thuật toán lập lịch khác nhau để lập lịch cho các quá trình. Các bài viết liên quan: Đây là một nhiệm vụ của bộ lập lịch ngắn hạn để lập lịch cho CPU về số lượng quy trình có trong Nhóm công việc. Bất cứ khi nào quá trình đang chạy yêu cầu một số hoạt động IO thì bộ lập lịch ngắn hạn sẽ lưu bối cảnh hiện tại của quá trình (còn được gọi là PCB) và thay đổi trạng thái của nó từ đang chạy sang chờ. Trong thời gian, tiến trình ở trạng thái chờ đợi; bộ lập lịch ngắn hạn chọn một quá trình khác từ hàng đợi sẵn sàng và chỉ định CPU cho quá trình này. Thủ tục này được gọi là chuyển đổi ngữ cảnh . Xem thêm Priority Scheduling trong Hệ điều hành Những gì được lưu trong Khối Kiểm soát Quy trình?Hệ điều hành duy trì một khối điều khiển quy trình trong suốt thời gian tồn tại của quy trình. Khối điều khiển quá trình bị xóa khi quá trình bị kết thúc hoặc bị giết. Có thông tin sau được lưu trong khối điều khiển quy trình và sẽ thay đổi theo trạng thái của quy trình. Tại sao chúng ta cần Lập lịch trình?Trong Đa chương trình, nếu bộ lập lịch dài hạn chọn nhiều quá trình ràng buộc I / O hơn thì phần lớn thời gian, CPU vẫn là thần tượng. Nhiệm vụ của Hệ điều hành là tối ưu hóa việc sử dụng tài nguyên. Nếu hầu hết các tiến trình đang chạy thay đổi trạng thái của chúng từ đang chạy sang chờ thì có thể luôn có khả năng xảy ra bế tắc trong hệ thống. Do đó, để giảm thiểu chi phí này, HĐH cần lên lịch các công việc để có được việc sử dụng CPU tối ưu và tránh khả năng bị deadlock. Xem thêm Thuật toán Shortest Remaining Time First (SRTF) Các thuật toán lập lịch trìnhCó nhiều thuật toán khác nhau được Hệ điều hành sử dụng để lập lịch các quá trình trên bộ xử lý một cách hiệu quả. Mục đích của thuật toán lập lịch trình
Có các thuật toán sau đây có thể được sử dụng để lập lịch trình công việc. Đây là thuật toán đơn giản nhất để thực hiện. Quá trình với thời gian đến tối thiểu sẽ nhận được CPU đầu tiên. Thời gian đến càng ít, quá trình nhận được CPU càng sớm. Đây là kiểu lập kế hoạch không ưu tiên. Xem thêm Lập lịch FCFS trong Operating System Trong thuật toán lập lịch Round Robin, Hệ điều hành xác định một lượng tử thời gian (lát cắt). Tất cả các quá trình sẽ được thực thi theo cách tuần hoàn. Mỗi tiến trình sẽ lấy CPU trong một khoảng thời gian nhỏ (gọi là lượng tử thời gian) và sau đó quay trở lại hàng đợi sẵn sàng để chờ đến lượt tiếp theo của nó. Đây là một kiểu lập kế hoạch phủ đầu.
Công việc có thời gian bùng nổ ngắn nhất sẽ nhận được CPU đầu tiên. Thời gian bùng nổ càng ít, quá trình lấy CPU càng sớm. Đây là kiểu lập kế hoạch không ưu tiên.
Đó là hình thức phủ đầu của SJF. Trong thuật toán này, Hệ điều hành lên lịch Công việc theo thời gian thực hiện còn lại.
Trong thuật toán này, mức độ ưu tiên sẽ được chỉ định cho mỗi quá trình. Mức độ ưu tiên càng cao thì tiến trình nhận được CPU càng sớm. Nếu mức độ ưu tiên của hai quy trình là như nhau thì chúng sẽ được sắp xếp theo thời gian đến.
Trong Thuật toán lập lịch này, quy trình có tỷ lệ phản hồi cao nhất sẽ được lên lịch tiếp theo. Điều này làm giảm tình trạng đói trong hệ thống. Xem thêm Lập lịch Highest Response Ratio Next (HRRN) trong hệ điều hành Trong bài viết trước mình đã giới thiệu sơ lược về định nghĩa, đặc điểm và phân loại tiến trình, ở bài viết này, mình xin tiếp tục trình bày về vấn đề quan trọng đó là điều phối tiến trình trong hệ điều hành. Các trạng thái của tiến trìnhTrạng thái của tiến trình tại một thời điểm được xác định bởi hoạt động hiện thời của tiến trình tại thời điếm đó. Trong quá trình sống một tiến trình thay đổi trạng thái do nhiều nguyên nhân như: phải chờ một sự kiện nào đó xảy ra ,hay đợi một thao tác nhập xuất hoàn tất, buộc phải dừng hoạt động do hết thời gian xử lý…… Tại một thời điểm một tiến trình có thể nhận một trong các trạng thái sau đây: * Mới tạo(new): tiến trình đang được tạo lập * Running: các chỉ thị của tiến trình đang được xử lý. * Blocked: tiến trình chờ được cấp phát tài nguyên,hay chờ một sự kiện xảy ra. * Ready(ready): tiến trình chờ được cấp phát CPU để xử lý. * Waiting (đợi): tiến trình phải dừng vì thiếu tài nguyên hoặc chờ một sự kiện nào đó. * Kết thúc(halt) : tiến trình hoàn tất xử lý Các trạng thái của tiến trình được biểu diễn qua sơ đồ sau:  Mục đíchSự công bằng: Các tiến trình chia sẻ CPU một cách công bằng,không có tiến trình nào phải chờ đợi vô hạn để được cấp phát CPU. Tính hiệu quả: Hệ thống phải tận dụng được CPU 100% thời gian.(thời gian chờ trung bình ngắn). Thời gian đáp ứng hợp lý: Cực tiểu hóa thời gian hồi đáp cho các tương tác của người sử dụng. Thời gian lưu lại trong hệ thống: Cực tiểu hóa thời gian hoàn tất các ác vụ xử lý. Thông lượng tối đa: Cực đại hóa số công việc được xử lý trong một đơn vị thời gian . Tuy nhiên thường không thể thỏa mãn tất cả các mục tiêu kể trên vì bản thân chúng có sự mâu thuẩn nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó. Cơ chế điều phối độc quyềnNguyên lý: Cơ chế này cho phép một tiến trình khi nhận được CPU sẽ có quyền đọc chiếm CPU đến khi hoàn tất xử lý hoặc tự giải phóng CPU.Khi đó quyết định điều phối sẻ xảy ra các trường hợp sau. • Tiến trình chuyển từ trạng thái running --> blockit • Kết thúc tiến trình. Các giải thuật độc quyền dễ cài đặt thuật toán.Tuy nhiên lại không thích hợp cho hệ thống tổng quát nhiều người dùng.Vì nếu cho tiến trình thời gian chiếm giử CPU tùy ý thì sẻ ngăn cản quá trình xử lý của các tiến trình còn lại. Cơ chế điều phối không độc quyền.Ngược với nguyên lý độc quyền ,điều phối theo nguyên lý không đọc quyền cho phép tạm dừng hoạt động của tiến trình đang sẵn sang xử lý.Khi một tiến trình nhận CPU nó vấn được sử dụng CPU cho đến khi hoàn tất hoặc tự nguyện giải phóng CPU,nhưng một tiến trình khác có độ ưu tiên cao hơn có thể dành quyền sử dụng CPU của tiến trình ban đầu.Như vậy tiến trình có thể dừng hoạt động bắt cứ lúc nào mà không được báo trước để tiến trình khác xử lý.Các quyết định điều phối xảy ra khi: • Tiến trình chuyển từ trạng thái running --> blocked. • Một tiến trình chờ trạng thái xử lý. • Chuyển từ trạng thái chờ(blocked) --> ready. • Khi một tiến trình kết thúc. Các thuật toán điều phối theo nguyên tắc không đọc quyến ngăn cản tình trạng một tiến trình đọc chiếm CPU. Trong bài viết sau mình 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 Mr.NaraLậ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 |
