Phương pháp miễn phí cuộc đua nhanh nhất để bỏ phiếu cho hàng đợi không khóa là gì?

Question

Giả sử chúng ta có một hàng đợi không có khóa đơn-người tiêu dùng-thread-đơn-sản xuất, và rằng nhà sản xuất có thể mất nhiều thời gian mà không tạo ra bất kỳ dữ liệu nào. Nó sẽ có lợi để cho phép người tiêu dùng ngủ khi không có gì trong hàng đợi (để tiết kiệm năng lượng và giải phóng CPU cho các quá trình/chủ đề khác). Nếu hàng đợi không khóa, cách đơn giản để giải quyết vấn đề này là phải tạo ra một chuỗi khóa, hãy thực hiện công việc của nó, báo hiệu biến điều kiện và mở khóa, và cho chuỗi đọc để khóa mutex, chờ trên biến điều kiện , đọc, sau đó mở khóa. Nhưng nếu chúng ta đang sử dụng một hàng đợi không khóa, sử dụng một mutex chính xác cùng một cách sẽ loại bỏ hiệu suất chúng ta thu được từ việc sử dụng một hàng đợi không khóa ở nơi đầu tiên.

Giải pháp ngây thơ là có nhà sản xuất sau mỗi lần chèn vào hàng đợi khóa mutex, báo hiệu biến điều kiện, sau đó mở khóa mutex, giữ công việc thực tế (chèn vào hàng đợi) hoàn toàn bên ngoài khóa và có người tiêu dùng làm tương tự, khóa mutex, chờ đợi trên biến điều kiện, mở khóa nó, kéo tất cả mọi thứ ra khỏi hàng đợi, sau đó lặp lại, giữ việc đọc hàng đợi bên ngoài khóa. Có một điều kiện chủng tộc ở đây mặc dù: giữa người đọc kéo ra khỏi hàng đợi và đi ngủ, nhà sản xuất có thể đã chèn một vật phẩm vào hàng đợi. Bây giờ người đọc sẽ đi ngủ, và có thể ở lại vô thời hạn cho đến khi người sản xuất chèn một vật phẩm khác và báo hiệu biến điều kiện một lần nữa. Điều này có nghĩa là đôi khi bạn có thể kết thúc với các mục cụ thể dường như mất một thời gian rất dài để đi qua hàng đợi. Nếu hàng đợi của bạn luôn hoạt động liên tục, điều này có thể không phải là vấn đề, nhưng nếu nó luôn hoạt động, bạn có thể quên hoàn toàn biến điều kiện.

AFAICT giải pháp là dành cho nhà sản xuất để hành xử giống như thể nó đang hoạt động với hàng đợi khóa thông thường. Nó sẽ khóa mutex, chèn vào hàng đợi không khóa, báo hiệu biến điều kiện, mở khóa. Tuy nhiên, người tiêu dùng nên hành xử khác nhau. Khi nó thức dậy, nó sẽ mở khóa mutex ngay lập tức thay vì chờ đợi cho đến khi nó đọc hàng đợi. Sau đó, nó sẽ kéo càng nhiều hàng đợi càng tốt và xử lý nó. Cuối cùng, chỉ khi người tiêu dùng nghĩ đến việc đi ngủ, nó có nên khóa mutex hay không, kiểm tra xem có bất kỳ dữ liệu nào không, sau đó nếu mở khóa và xử lý nó hoặc nếu không thì hãy đợi biến điều kiện. Bằng cách này, mutex được ít thường xuyên hơn so với hàng đợi có khóa, nhưng không có nguy cơ đi ngủ với dữ liệu vẫn còn trên hàng đợi.

Đây có phải là cách tốt nhất để làm điều đó không? Có lựa chọn thay thế nào không?

Note: Bằng 'nhanh nhất' Tôi thực sự có nghĩa là 'nhanh nhất mà không cống hiến một lõi để kiểm tra hàng đợi hơn và hơn,' nhưng điều đó sẽ không phù hợp trong tiêu đề; p

Một thay thế: Đi với các giải pháp ngây thơ, nhưng có người tiêu dùng chờ đợi trên biến điều kiện với một thời gian chờ tương ứng với độ trễ tối đa bạn sẵn sàng chịu đựng cho một mục đi qua hàng đợi. Nếu thời gian chờ mong muốn là khá ngắn mặc dù, nó có thể dưới thời gian chờ đợi tối thiểu cho hệ điều hành của bạn hoặc vẫn tiêu thụ quá nhiều CPU.

Answer 1

Tôi giả định rằng bạn đang sử dụng hàng đợi đơn người tiêu dùng đơn sản xuất không có khóa từ Dr Dobbs article - hoặc thứ gì đó tương tự - vì vậy tôi sẽ sử dụng thuật ngữ từ đó.

Trong trường hợp đó, câu trả lời đề nghị của bạn trong đoạn bắt đầu "AFAICT" là tốt, nhưng tôi nghĩ rằng nó có thể được tối ưu hóa hơi:

• Trong tiêu dùng - như bạn nói, khi người tiêu dùng đã cạn kiệt hàng đợi và đang xem xét việc ngủ (và chỉ sau đó), nó khóa mutex, kiểm tra lại hàng đợi và sau đó là
  • . khối trên biến điều kiện (phát hành mutex khi nó thức dậy để tìm một hàng đợi không trống, nat urally).
• Trong sản xuất:
  • Đầu tiên lấy một bản sao của last, gọi nó là saved_last
  • Thêm mục new_item như thường lệ, sau đó lấy một bản sao của con trỏ divider, gọi nó là saved_divider.
  • Nếu giá trị saved_divider bằng new_item, đối tượng bạn vừa chèn vào, khi đó đối tượng của bạn đã được tiêu thụ và công việc của bạn đã hoàn tất.
  • Nếu không, nếu giá trị saved_divider không bằng saved_last, thì bạn không cần đánh thức người tiêu dùng. Điều này là do:
    • Tại một thời gian nghiêm ngặt sau khi bạn thêm đối tượng mới, bạn biết rằng divider vẫn chưa đạt hoặc new_item hoặc saved_last
    • Kể từ khi bạn bắt đầu chèn, last đã chỉ có hai giá trị
    • Người tiêu dùng chỉ dừng lại khi divider bằng last
    • Vì vậy, người tiêu dùng vẫn phải tỉnh táo và sẽ tiếp cận vật phẩm mới của bạn trước khi đi ngủ.
  • Nếu không khóa mutex, báo hiệu condvar rồi nhả mutex. (Lấy mutex đây đảm bảo bạn không tín hiệu condar trong thời gian giữa người tiêu dùng nhận thấy hàng đợi rỗng, và thực sự chặn trên condvar.)

này đảm bảo rằng, trong trường hợp người tiêu dùng có xu hướng vẫn bận rộn, bạn tránh khóa các mutex khi bạn biết người tiêu dùng vẫn còn tỉnh táo (và không về để ngủ). Nó cũng giảm thiểu thời gian khi các mutex được tổ chức, để tiếp tục giảm khả năng tranh chấp.

Lời giải thích ở trên khá dài dòng (vì tôi muốn bao gồm giải thích lý do tại sao nó hoạt động, thay vì chỉ là thuật toán), nhưng mã kết quả từ nó phải khá đơn giản.

Tất nhiên điều đó thực sự đáng làm sẽ phụ thuộc vào rất nhiều thứ và tôi khuyên bạn nên đo lường xem hiệu suất có quan trọng với bạn hay không. Việc triển khai tốt các nguyên tố mutex/condvar trong nội bộ sử dụng các hoạt động nguyên tử trong hầu hết các trường hợp, vì vậy chúng thường chỉ thực hiện một cuộc gọi hạt nhân (bit đắt nhất!) Nếu cần - tức là nếu cần chặn, hoặc chắc chắn có chủ đề chờ đợi - do đó, thời gian được lưu bằng cách không gọi các chức năng mutex chỉ có thể lên tới phí của các cuộc gọi trong thư viện.