Hành trình dài để triển khai “preemption lười” trong bộ lập lịch CPU của Linux

• Nhân Linux từ lâu duy trì nhiều chế độ preemption để đánh đổi giữa throughput và thời gian phản hồi, và bộ bản vá mới của Peter Zijlstra đã làm cuộc thảo luận về preemption lười (PREEMPT_LAZY) sôi nổi trở lại
• Các chế độ hiện có PREEMPT_NONE, PREEMPT_VOLUNTARY, PREEMPT_FULL, PREEMPT_RT khác nhau ở phạm vi cho phép preemption; preemption càng thường xuyên thì độ phản hồi có thể càng tốt, nhưng gây áp lực lớn hơn lên throughput và tranh chấp khóa
• PREEMPT_LAZY dùng cờ TIF_NEED_RESCHED_LAZY để biểu thị “cần lập lịch lại, nhưng không phải ngay lập tức”, và trì hoãn phần lớn việc preemption cho đến timer tick
• Về dài hạn, hướng đi là giảm các chế độ preemption không thời gian thực xuống còn PREEMPT_LAZY và PREEMPT_FULL, đồng thời loại bỏ hầu hết các lời gọi cond_resched() rải rác trong nhân
• Bộ bản vá hiện tại vẫn cần được ổn định thêm, rà soát các điểm gọi và kiểm thử hiệu năng; trong các thử nghiệm ban đầu, throughput của PREEMPT_LAZY hơi thấp hơn PREEMPT_VOLUNTARY

---

Các chế độ preemption hiện có của nhân Linux

• Nhân hiện cung cấp nhiều chế độ preemption để điều chỉnh khi nào một tác vụ đang chạy có thể bị tác vụ khác giành CPU
  • PREEMPT_NONE: chế độ đơn giản nhất, chỉ cho phép preemption khi tác vụ đang chạy đã dùng hết time slice
  • PREEMPT_VOLUNTARY: chế độ bổ sung nhiều điểm trong nhân nơi có thể preempt khi cần
  • PREEMPT_FULL: chế độ cho phép preemption ở gần như mọi điểm, trừ những đoạn mà nhân chặn lại như khi đang giữ spinlock
  • PREEMPT_RT: chế độ ưu tiên preemption hơn hầu hết mọi thứ, và khiến cả phần lớn mã đang giữ spinlock cũng có thể bị preempt
• Mức preemption cao giúp hệ thống phản ứng nhanh hơn với các sự kiện như di chuyển chuột hay một tín hiệu bất thường sắp xảy ra trong lò phản ứng
• Đổi lại, preemption thường xuyên có thể làm giảm throughput tổng thể của các tác vụ nặng CPU chạy lâu và làm tăng tranh chấp khóa
• Nhiều bản phân phối build nhân với chế độ giả PREEMPT_DYNAMIC
  • Có thể chọn một trong ba chế độ không thời gian thực nói trên khi khởi động
  • Giá trị mặc định là PREEMPT_VOLUNTARY
  • Trên hệ thống đã mount debugfs, có thể xem chế độ hiện tại tại /sys/kernel/debug/sched/preempt

Vì sao cần cond_resched()

• PREEMPT_NONE và PREEMPT_VOLUNTARY không cho phép preemption tùy ý khi đang thực thi mã nhân
• Nếu một công việc dài tiếp diễn bên trong nhân, ngay cả trên hệ thống không đặt độ trễ tối thiểu lên hàng đầu cũng có thể phát sinh độ trễ quá mức
• Để tránh điều này, các lời gọi cond_resched() đã được thêm vào nhiều nơi trong những vòng lặp chạy lâu
  • Mỗi lời gọi là một điểm preemption tự nguyện bổ sung
  • Hoạt động cả trong chế độ PREEMPT_NONE
  • Trong nhân có hàng trăm lời gọi như vậy
• Cách làm này là một heuristic chỉ hoạt động tại những vị trí mà nhà phát triển đã đặt vào
  • Có thể có các lời gọi không cần thiết
  • Cũng có thể thiếu lời gọi ở những nơi cần thiết
  • Việc quyết định lập lịch bị phân tán khắp mã nhân

Cơ chế cốt lõi của preemption lười

• Khi nhân quyết định liệu tác vụ hiện tại có thể bị preempt hay không, nó xem xét nhiều biến cùng lúc
• Trong số đó, TIF_NEED_RESCHED là cờ cho biết một tác vụ có độ ưu tiên cao hơn đang chờ quyền truy cập CPU
  • Khi một tác vụ ưu tiên cao được đánh thức, cờ này có thể được đặt trên tác vụ đang chạy hiện tại
  • Nếu không có cờ này, nhân không cần preempt tác vụ hiện tại
• Nhân kiểm tra TIF_NEED_RESCHED tại nhiều điểm để có thể preempt tác vụ hiện tại
  • Timer tick của bộ lập lịch
  • Khi trở về user space sau một system call
  • Khi hoàn tất interrupt handler
  • Lời gọi cond_resched()
• Bản vá preemption lười bổ sung cờ mới TIF_NEED_RESCHED_LAZY
  • Nghĩa là cần lập lịch lại, nhưng không nhất thiết phải thực hiện ngay
  • Trong chế độ PREEMPT_LAZY, phần lớn sự kiện sẽ đặt cờ mới này thay vì TIF_NEED_RESCHED
• Tại các điểm quay từ nhân về user space, chỉ cần một trong hai cờ được đặt là sẽ dẫn tới lời gọi bộ lập lịch
• Tại các điểm preemption tự nguyện và đường quay về sau ngắt, chỉ TIF_NEED_RESCHED được kiểm tra

Sự đánh đổi mà PREEMPT_LAZY tạo ra

• Trong PREEMPT_LAZY, phần lớn sự kiện bên trong nhân không preempt tác vụ hiện tại ngay lập tức
• Thay vào đó, timer tick handler kiểm tra xem TIF_NEED_RESCHED_LAZY có được đặt hay không
  • Nếu có, nó cũng đặt TIF_NEED_RESCHED
  • Kết quả là tác vụ đang chạy có thể bị preempt
• Thông thường, tác vụ sẽ chạy trong khoảng thời gian gần với time slice của mình, trừ khi tự nguyện nhường CPU
  • Hành vi này được kỳ vọng mang lại throughput tốt
• Với thay đổi này, PREEMPT_LAZY cũng có thể chạy với preemption trong nhân hầu như luôn được bật, giống như PREEMPT_FULL
  • Có thể preempt bất cứ lúc nào nếu bộ đếm preemption cho phép
  • Nếu không bị điều kiện khác ngăn lại, cả mã nhân chạy lâu cũng có thể bị preempt
• Trong các trường hợp thực sự cần preemption ngay, nó sẽ không bị trì hoãn
  • Ví dụ, nếu một tác vụ thời gian thực trở nên có thể chạy do kết quả xử lý ngắt, TIF_NEED_RESCHED sẽ được đặt
  • Khi đó, preemption sẽ diễn ra gần như ngay lập tức mà không chờ timer tick
• Nếu chỉ TIF_NEED_RESCHED_LAZY được đặt thì preemption sẽ không xảy ra
  • Vì vậy nhân PREEMPT_LAZY ít có khả năng preempt tác vụ đang chạy hơn nhiều so với nhân PREEMPT_FULL

Những việc còn lại trước khi loại bỏ cond_resched()

• Mục tiêu dài hạn là giảm các chế độ preemption không thời gian thực xuống còn hai chế độ
  • PREEMPT_LAZY
  • PREEMPT_FULL
• PREEMPT_LAZY nằm giữa PREEMPT_NONE và PREEMPT_VOLUNTARY, và dự kiến sẽ thay thế cả hai
• Khi preemption gần như có thể xảy ra ở mọi nơi, nhu cầu bổ sung riêng các điểm preemption tự nguyện tại những điểm cụ thể sẽ giảm đi
• Hiện các lời gọi cond_resched() vẫn còn tồn tại
  • Chúng cần thiết chừng nào PREEMPT_NONE và PREEMPT_VOLUNTARY còn tồn tại
  • Chúng cũng giúp tránh phát sinh vấn đề trong quá trình ổn định preemption lười
• Trong bộ bản vá hiện tại, cond_resched() chỉ kiểm tra TIF_NEED_RESCHED
  • Vì vậy trong PREEMPT_VOLUNTARY hoặc PREEMPT_NONE, nhiều tình huống trước đây sẽ preempt ngay có thể bị trì hoãn
• Steve Rostedt đã hỏi liệu việc giữ nguyên ý nghĩa cũ của cond_resched(), đặc biệt trong PREEMPT_VOLUNTARY, có thể giúp quá trình chuyển đổi dễ hơn hay không
• Thomas Gleixner cho rằng lựa chọn chỉ kiểm tra TIF_NEED_RESCHED là đúng
  • Vì nó buộc phải rà soát tất cả các lời gọi cond_resched()
  • Những lời gọi không cần kiểm tra bit lazy có thể được loại bỏ khi áp dụng PREEMPT_LAZY
  • Những lời gọi cần kiểm tra bit lazy sẽ phải được giữ lại
• Gleixner dự đoán chỉ dưới 5% số lời gọi cond_resched() cần kiểm tra TIF_NEED_RESCHED_LAZY
• Trước khi quá trình chuyển đổi hoàn tất, cần rà soát hàng trăm lời gọi cond_resched() và loại bỏ phần lớn trong số đó
• Một bộ bản vá riêng của Ankur Arora xử lý một số chi tiết liên quan
• Cũng cần kiểm thử hiệu năng trên diện rộng
  • Trong thử nghiệm ban đầu của Mike Galbraith, throughput của preemption lười hơi thấp hơn PREEMPT_VOLUNTARY

Mục tiêu cuối cùng

• Nhờ công việc về preemption lười, nhân có thể trở nên nhỏ gọn và đơn giản hơn một chút
• Mục tiêu là một nhân cung cấp độ trễ có thể dự đoán được mà không cần rải các lời gọi liên quan đến bộ lập lịch khắp mã nguồn
• Cách tiếp cận hiện tại có vẻ là một giải pháp tốt hơn, nhưng để đạt tới trạng thái đó vẫn cần thêm thời gian

[GN⁺]

Các ý kiến trên Hacker News

• Có vẻ đầy hứa hẹn. Vì đây là hướng vừa đơn giản hóa vừa cải thiện hiện trạng, giống như EEVDF, nên khó mà tốt hơn thế

• Tôi thắc mắc tại sao mức độ preemption lại không phải là thuộc tính của một sự kiện cụ thể mà là một chế độ toàn cục. Một số sự kiện cần được xử lý với độ trễ thấp hơn các sự kiện khác

  • Để đánh giá mức ưu tiên của một sự kiện thì trước hết cần thời gian CPU. Chỉ sau khi ngắt tiến trình đang chạy trên CPU hiện tại mới có thể thực hiện việc đánh giá đó
    Vì vậy, mức ưu tiên cao nhất mà một sự kiện có thể có cũng bị giới hạn bởi lát thời gian mà chương trình có thể nhận được ngắn đến đâu trước khi trải qua chuyển ngữ cảnh. Để phản hồi ổn định với độ trễ thấp cho bất kỳ loại sự kiện nào, mọi chương trình ngốn CPU đều luôn phải trả chi phí hiệu năng, dù sự kiện đó hiếm đến mức nào
  • Ở đây có hai khái niệm dễ bị nhầm lẫn. Một là thời điểm một tiến trình có thể bị preempt, và hai là liệu nó có thực sự bị preempt hay không
    Các điểm preemption tiềm năng là thuộc tính của bộ lập lịch, và đó cũng là thứ đang được bàn ở đây như một chế độ toàn cục. Càng có nhiều điểm preemption thì tất nhiên khả năng tiến trình bị preempt vào thời điểm bất tiện càng tăng, nhưng đồng thời cũng có nhiều cơ hội hơn để phản ánh đúng mức ưu tiên. Mức preemption mà câu hỏi nói tới, tức mức ưu tiên do bộ lập lịch trao, đúng là thuộc tính của tiến trình và cũng có thể cấu hình được. Bộ lập lịch mặc định của Linux cũng cấp lát thời gian lớn hơn cho các tiến trình có mức ưu tiên và cố gắng preempt các tiến trình khác ít hơn
  • PREEMPT_VOLUNTARY được mô tả trong bài viết ở một mức nào đó là một nỗ lực theo hướng đó, và giờ có thể xem là đang bị loại bỏ
  • Bản vá này phần nào đảm nhiệm vai trò đó. Theo https://lwn.net/ml/all/[e-mail]...:
    SCHED_IDLE, SCHED_BATCH, SCHED_NORMAL/OTHER dùng preemption trì hoãn, còn FIFO, RR, DEADLINE dùng hành vi Full hiện có
  • Một hệ thống như vậy rất có thể tạo ra cuộc tranh giành giữa các chương trình, chương trình nào cũng đòi mức ưu tiên vì cho rằng mình quan trọng. Thực tế thì nhiều khả năng các công ty lớn sẽ tận dụng nó để mang lại trải nghiệm người dùng “tốt hơn”
    Vì vậy, việc giảm tối thiểu số ứng dụng đang chạy, hoặc kiểm soát thủ công những khoảnh khắc ngắn mà phần lớn người dùng gặp phải, lại quan trọng hơn. Đôi khi các tác vụ ngốn CPU cũng có khả năng là mã tệ hơn là sử dụng tài nguyên thực sự hiệu quả. Trong game thì phải ưu tiên hiệu năng, nhưng cần một sự cân bằng tinh tế để không làm hệ thống khựng lại khi đa nhiệm. Dù sao thì cơ chế này chủ yếu dành cho tác vụ nhàn rỗi, nên có vẻ không cần tự động hóa quá mức ngoài việc cung cấp một lệnh đơn giản để người dùng bật/tắt nhiều hành vi trong script

• Bài viết nói “trong kernel hiện tại có bốn chế độ điều chỉnh thời điểm một tác vụ có thể bị preempt vì một tác vụ khác”, tôi thắc mắc đây là nói về tác vụ kernel hay bao gồm cả tác vụ người dùng

  • Đây là nói về mã kernel. Mã user space thì luôn có thể bị preempt

• Tôi không tìm thấy số liệu trong luồng liên quan nơi bản vá được đăng. Tôi tò mò liệu đã có benchmark ban đầu nào cho thấy tiềm năng thực tế của thay đổi này chưa

  • Có ở đoạn áp chót của bài viết
    Bài viết nói cần kiểm thử hiệu năng trên diện rộng, Mike Galbraith đã bắt đầu công việc ban đầu, và kết quả cho thấy thông lượng của preemption trì hoãn thấp hơn PREEMPT_VOLUNTARY một chút
  • Tôi thắc mắc những thứ như thế này nên benchmark thế nào. Chạy nhiều tiến trình đồng thời rồi sắp xếp theo tổng thời gian chạy, hay phải đo thời gian chờ của từng tiến trình

• Tôi thắc mắc bộ lập lịch được ghép chặt với phần mã còn lại của kernel đến mức nào
  Ví dụ, nếu muốn đơn giản hóa mạnh bộ lập lịch cho các ứng dụng tính toán khoa học hoàn toàn không quan tâm tới preemption, thì có thể làm một cách sạch sẽ và mô-đun không? Có lợi ích thực tế nào không

  • Nếu muốn chạy một tập tiến trình với mức preemption thấp nhất có thể, chẳng hạn trong môi trường HPC, cách mạnh nhất là đặt một số core làm CPU cô lập, khởi động lại, rồi dùng taskset để đưa trực tiếp tác vụ lên đó
    Tuy nhiên khi đó bạn phải gán tác vụ vào CPU thật sự thủ công, và cũng dễ xảy ra tình huống mọi tác vụ lại chạy nhầm CPU. Cách tiêu chuẩn là đặt interrupt mask để interrupt không đi vào CPU “làm việc”, và dùng cpuset để chỉ một cgroup cụ thể được chạy trong cpuset đã cho
  • Trên một hệ thống sạch, gần như không có daemon, nếu căn chỉnh ứng dụng thành một luồng hệ điều hành cho mỗi luồng CPU và đặt CPU affinity để nó không di chuyển, thì có thể đạt khoảng 95%
    Vì run queue sẽ rất ngắn, nên bộ lập lịch làm gì cũng có ảnh hưởng khá nhỏ. Nếu ứng dụng không làm nhiều I/O thì cũng không có nhiều interrupt. Nếu dùng được kernel tickless, tôi không biết ngày nay nó vẫn là tùy chọn riêng hay đã là mặc định, thì trong thời gian dài có thể gần như không có interrupt
  • Lần cuối tôi xem thì nó được tách biệt tốt một cách đáng ngạc nhiên
    Tuy nhiên lý do để đơn giản hóa mạnh là để tránh lỗi, chứ hiệu năng đạt được so với bộ lập lịch mặc định được cấu hình tốt thì không nhiều. Có nhiều tùy chọn cấu hình, nhưng phía đó cũng không có nhiều lỗi. Nếu đơn giản hóa một cách ngây thơ thì phần lớn là mất hiệu năng hơn là được. Nếu chạy hệ thống không tương tác, thay đổi dễ nhất là tăng hạn ngạch thời gian của tiến trình
  • Tôi sẽ chỉ dùng RT Linux. Nó có bộ lập lịch mặc định riêng, kernel scheduler chạy như tác vụ nhàn rỗi, và tác vụ thời gian thực có mức ưu tiên cao hơn mọi thứ