Thuật toán không chặn – Wikipedia

Posted on by lordneo

Trong khoa học máy tính, một thuật toán được gọi là không chặn nếu thất bại hoặc đình chỉ bất kỳ luồng nào có thể gây ra lỗi hoặc đình chỉ một luồng khác; [1] đối với một số thao tác, các thuật toán này cung cấp một giải pháp thay thế hữu ích cho thực hiện chặn truyền thống. Thuật toán không chặn là không khóa nếu có tiến trình toàn hệ thống được đảm bảo và không phải chờ đợi nếu cũng có tiến trình trên mỗi luồng được đảm bảo.

Từ "không chặn" theo truyền thống được sử dụng để mô tả các mạng viễn thông có thể định tuyến kết nối thông qua một bộ rơle "mà không phải sắp xếp lại các cuộc gọi hiện tại", xem Mạng Clos. Ngoài ra, nếu tổng đài điện thoại "không bị lỗi, nó luôn có thể thực hiện kết nối", hãy xem công tắc mở rộng tối thiểu không chặn.

Động lực [ chỉnh sửa ]

Cách tiếp cận truyền thống để lập trình đa luồng là sử dụng khóa để đồng bộ hóa quyền truy cập vào tài nguyên được chia sẻ. Các nguyên hàm đồng bộ hóa như mutexes, semaphores và các phần quan trọng là tất cả các cơ chế mà một lập trình viên có thể đảm bảo rằng các phần mã nhất định không thực thi đồng thời, nếu làm như vậy sẽ làm hỏng cấu trúc bộ nhớ chia sẻ. Nếu một luồng cố gắng để có được một khóa đã được giữ bởi một luồng khác, thì luồng sẽ chặn cho đến khi khóa được tự do.

Chặn một chuỗi có thể là không mong muốn vì nhiều lý do. Một lý do rõ ràng là trong khi luồng bị chặn, nó không thể thực hiện được bất cứ điều gì: nếu luồng bị chặn đã thực hiện một nhiệm vụ ưu tiên cao hoặc thời gian thực, thì việc dừng tiến trình của nó là rất không mong muốn.

Các vấn đề khác ít rõ ràng hơn. Ví dụ, một số tương tác nhất định giữa các khóa có thể dẫn đến các điều kiện lỗi như bế tắc, livelock và đảo ngược ưu tiên. Sử dụng khóa cũng liên quan đến sự đánh đổi giữa khóa hạt thô, có thể làm giảm đáng kể cơ hội song song và khóa hạt mịn, đòi hỏi thiết kế cẩn thận hơn, tăng khóa trên cao và dễ bị lỗi hơn.

Không giống như các thuật toán chặn, các thuật toán không chặn không gặp phải những nhược điểm này, và ngoài ra, nó an toàn để sử dụng trong các trình xử lý ngắt: mặc dù có thể nối lại luồng xử lý trước, nhưng vẫn có thể thực hiện được. Ngược lại, các cấu trúc dữ liệu toàn cầu được bảo vệ bằng loại trừ lẫn nhau không thể được truy cập một cách an toàn trong trình xử lý ngắt, vì luồng được ưu tiên có thể là khóa giữ – nhưng điều này có thể được khắc phục dễ dàng bằng cách che giấu yêu cầu ngắt trong phần quan trọng [2] .

Một cấu trúc dữ liệu không khóa có thể được sử dụng để cải thiện hiệu suất. Cấu trúc dữ liệu không khóa giúp tăng lượng thời gian thực hiện song song thay vì thực hiện nối tiếp, cải thiện hiệu năng trên bộ xử lý đa lõi, bởi vì không cần phải truy cập vào cấu trúc dữ liệu dùng chung để duy trì mạch lạc. [3]

[ chỉnh sửa ]

Với một vài ngoại lệ, thuật toán không chặn sử dụng các nguyên hàm đọc-sửa đổi-ghi nguyên tử mà phần cứng phải cung cấp, trong đó đáng chú ý nhất là so sánh và trao đổi (CAS). Các phần quan trọng hầu như luôn được thực hiện bằng cách sử dụng các giao diện tiêu chuẩn trên các nguyên thủy này (trong trường hợp chung, các phần quan trọng sẽ bị chặn, ngay cả khi được thực hiện với các nguyên thủy này). Cho đến gần đây, tất cả các thuật toán không chặn phải được viết "nguyên bản" với các nguyên hàm cơ bản để đạt được hiệu suất chấp nhận được. Tuy nhiên, lĩnh vực bộ nhớ giao dịch phần mềm mới nổi hứa hẹn những tóm tắt tiêu chuẩn để viết mã không chặn hiệu quả. [4] [5]

Nhiều nghiên cứu cũng đã được thực hiện trong việc cung cấp cơ bản cấu trúc dữ liệu như ngăn xếp, hàng đợi, bộ và bảng băm. Điều này cho phép các chương trình dễ dàng trao đổi dữ liệu giữa các luồng không đồng bộ.

Ngoài ra, một số cấu trúc dữ liệu không chặn đủ yếu để được thực hiện mà không có nguyên thủy nguyên tử đặc biệt. Những ngoại lệ này bao gồm:

  • Bộ đệm vòng một trình đọc một lần đọc FIFO, với kích thước chia đều cho một trong các loại số nguyên không dấu có sẵn, có thể được thực hiện một cách vô điều kiện chỉ bằng cách sử dụng hàng rào bộ nhớ
  • Cập nhật đọc-sao chép với một nhà văn duy nhất và bất kỳ số lượng độc giả. (Các độc giả không phải chờ đợi; nhà văn thường không có khóa, cho đến khi cần lấy lại bộ nhớ).
  • Đọc-sao chép-cập nhật với nhiều nhà văn và bất kỳ số lượng độc giả nào. (Các độc giả không phải chờ đợi; nhiều người viết thường tuần tự hóa với một khóa và không bị cản trở).

Một số thư viện trong nội bộ sử dụng các kỹ thuật không khóa, [6][7][8] nhưng rất khó để viết mã không khóa chính xác. [9][10][11][12]

Chờ đợi tự do [ chỉnh sửa ]

Chờ đợi tự do là sự bảo đảm không ngăn chặn mạnh mẽ nhất của tiến trình, kết hợp thông lượng toàn hệ thống được bảo đảm với tự do chết đói. Thuật toán không phải chờ nếu mọi thao tác bị ràng buộc về số bước mà thuật toán sẽ thực hiện trước khi hoạt động hoàn tất. [13] Thuộc tính này rất quan trọng đối với các hệ thống thời gian thực và luôn luôn tốt khi có chi phí hiệu năng không quá cao

Nó đã được chỉ ra vào những năm 1980 [14] rằng tất cả các thuật toán có thể được thực hiện miễn phí, và nhiều biến đổi từ mã nối tiếp, được gọi là các cấu trúc phổ quát đã được chứng minh. Tuy nhiên, hiệu suất kết quả không phù hợp với các thiết kế chặn thậm chí ngây thơ. Một số bài báo đã cải thiện hiệu suất của các công trình phổ quát, tuy nhiên, hiệu suất của chúng thấp hơn nhiều so với các thiết kế chặn.

Một số bài báo đã điều tra về khó khăn trong việc tạo ra các thuật toán chờ đợi. Ví dụ, người ta đã chỉ ra [15] rằng các nguyên tử có điều kiện có sẵn rộng rãi CAS và LL / SC, không thể cung cấp việc triển khai không có đói cho nhiều cấu trúc dữ liệu phổ biến mà không có chi phí bộ nhớ tăng theo số lượng chủ đề.

Nhưng trong thực tế, các giới hạn dưới này không tạo ra rào cản thực sự khi chi tiêu một dòng bộ đệm hoặc hạt đặt trước độc quyền (tối đa 2 KB cho ARM) của mỗi luồng trong bộ nhớ dùng chung không được coi là quá tốn kém cho các hệ thống thực tế (thông thường số lượng cửa hàng yêu cầu một cách hợp lý là một từ, nhưng các hoạt động CAS vật lý trên cùng một dòng bộ đệm sẽ va chạm và các hoạt động LL / SC trong cùng một hạt đặt trước độc quyền sẽ va chạm, do đó, số lượng cửa hàng yêu cầu về mặt vật lý [ trích dẫn cần thiết ] là lớn hơn).

Thuật toán chờ miễn phí rất hiếm cho đến năm 2011, cả trong nghiên cứu và thực tế. Tuy nhiên, vào năm 2011, Kogan và Petrank [16] đã trình bày một tòa nhà xếp hàng chờ miễn phí trên nguyên thủy CAS, thường có sẵn trên phần cứng phổ biến. Công trình của họ đã mở rộng hàng đợi không khóa của Michael và Scott, [17] một hàng đợi hiệu quả thường được sử dụng trong thực tế. Một bài báo tiếp theo của Kogan và Petrank [18] đã cung cấp một phương pháp để làm cho các thuật toán chờ đợi nhanh chóng và sử dụng phương pháp này để thực hiện hàng đợi chờ thực tế nhanh như đối tác không khóa của nó. Một bài báo tiếp theo của Timnat và Petrank [19] đã cung cấp một cơ chế tự động để tạo các cấu trúc dữ liệu không phải chờ đợi từ các khóa không khóa. Do đó, triển khai chờ miễn phí hiện có sẵn cho nhiều cấu trúc dữ liệu.

Tự do khóa [ chỉnh sửa ]

Tự do khóa cho phép các luồng riêng lẻ chết đói nhưng đảm bảo thông lượng trên toàn hệ thống. Một thuật toán không bị khóa nếu, khi các luồng chương trình được chạy trong một thời gian đủ dài, ít nhất một trong các luồng tạo ra tiến độ (đối với một số định nghĩa hợp lý của tiến độ). Tất cả các thuật toán chờ miễn phí là khóa miễn phí.

Đặc biệt, nếu một luồng bị treo, thuật toán không khóa đảm bảo rằng các luồng còn lại vẫn có thể đạt được tiến bộ. Do đó, nếu hai luồng có thể tranh nhau cho cùng một khóa mutex hoặc spinlock, thì thuật toán là chứ không phải không khóa. (Nếu chúng tôi tạm dừng một luồng giữ khóa, thì luồng thứ hai sẽ chặn.)

Một thuật toán không bị khóa nếu hoạt động thường xuyên bởi một số bộ xử lý sẽ thành công trong một số bước hữu hạn. Ví dụ, nếu bộ xử lý N đang cố gắng thực hiện một thao tác, một số quy trình N sẽ thành công trong việc hoàn thành thao tác trong một số bước hữu hạn và các bước khác có thể thất bại và thử lại thất bại. Sự khác biệt giữa chờ miễn phí và không khóa là hoạt động không chờ đợi của mỗi quy trình được đảm bảo thành công trong một số bước hữu hạn, bất kể các bộ xử lý khác.

Nói chung, thuật toán không khóa có thể chạy theo bốn giai đoạn: hoàn thành thao tác của chính mình, hỗ trợ thao tác cản trở, hủy bỏ thao tác cản trở và chờ đợi. Hoàn thành hoạt động của một người rất phức tạp bởi khả năng hỗ trợ và phá thai đồng thời, nhưng luôn luôn là con đường nhanh nhất để hoàn thành.

Quyết định về thời điểm hỗ trợ, hủy bỏ hoặc chờ đợi khi gặp phải sự cản trở là trách nhiệm của người quản lý tranh chấp . Điều này có thể rất đơn giản (hỗ trợ các hoạt động ưu tiên cao hơn, hủy bỏ các ưu tiên thấp hơn) hoặc có thể được tối ưu hóa hơn để đạt được thông lượng tốt hơn hoặc giảm độ trễ của các hoạt động ưu tiên.

Hỗ trợ đồng thời chính xác thường là phần phức tạp nhất của thuật toán không khóa và thường rất tốn kém khi thực hiện: không chỉ luồng hỗ trợ bị chậm mà nhờ vào cơ chế của bộ nhớ dùng chung, luồng được hỗ trợ sẽ được chậm quá, nếu nó vẫn chạy

Tự do cản trở [ chỉnh sửa ]

Tự do cản trở là bảo đảm tiến trình không chặn tự nhiên yếu nhất. Một thuật toán không bị cản trở nếu tại bất kỳ thời điểm nào, một luồng duy nhất được thực hiện trong sự cô lập (tức là, với tất cả các luồng bị tắc nghẽn) cho một số bước bị ràng buộc sẽ hoàn thành hoạt động của nó. [13] Tất cả các thuật toán không khóa đều không có vật cản.

Yêu cầu tự do tắc nghẽn chỉ có thể hủy bỏ mọi hoạt động đã hoàn thành một phần và các thay đổi đã được khôi phục. Việc bỏ hỗ trợ đồng thời thường có thể dẫn đến các thuật toán đơn giản hơn nhiều, dễ xác nhận hơn. Ngăn chặn hệ thống liên tục khóa trực tiếp là nhiệm vụ của người quản lý ganh đua.

Một số thuật toán không có vật cản sử dụng một cặp "dấu nhất quán" trong cấu trúc dữ liệu. Các quá trình đọc cấu trúc dữ liệu trước tiên đọc một điểm đánh dấu nhất quán, sau đó đọc dữ liệu liên quan vào bộ đệm bên trong, sau đó đọc điểm đánh dấu khác và sau đó so sánh các điểm đánh dấu. Dữ liệu phù hợp nếu hai điểm đánh dấu giống hệt nhau. Các điểm đánh dấu có thể không giống nhau khi quá trình đọc bị gián đoạn bởi một quá trình khác cập nhật cấu trúc dữ liệu. Trong trường hợp như vậy, quá trình loại bỏ dữ liệu trong bộ đệm nội bộ và thử lại.

"Không chặn" đã được sử dụng như một từ đồng nghĩa với "không khóa" trong tài liệu cho đến khi giới thiệu tự do tắc nghẽn vào năm 2003. [20]

Xem thêm [ chỉnh sửa ] [19659055] Tài liệu tham khảo [ chỉnh sửa ]

  1. ^ Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Đồng thời Java trong thực tế . Thượng Yên River, NJ: Addison-Wesley. tr. 41. ISBN YAM321349606.
  2. ^ Butler W. Lampson; David D. Redell (tháng 2 năm 1980). "Kinh nghiệm với quy trình và màn hình ở Mesa". Truyền thông của ACM . 23 (2): 105 Tiết 117. CiteSeerX 10.1.1.142.5765 . doi: 10.1145 / 358818.358824.
  3. ^ Guillaume Marçais và Carl Kingsford. "Một cách tiếp cận nhanh, không khóa để đếm song song hiệu quả sự xuất hiện của k-mers". Tin sinh học (2011) 27 (6): 764-770. doi: 10.1093 / tin sinh học / btr011 "Bộ đếm sứa mer".
  4. ^ Harris, Tim; Fraser, Keir (26 tháng 11 năm 2003). "Hỗ trợ ngôn ngữ cho các giao dịch nhẹ" (PDF) . Thông báo ACM SIGPLAN . 38 (11): 388. doi: 10.1145 / 949343.949340.
  5. ^ Harris, Tim; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (15 tháng 61717, 2005). "Giao dịch bộ nhớ tổng hợp". Thủ tục tố tụng của Hội nghị chuyên đề ACM SIGPLAN năm 2005 về các nguyên tắc và thực hành lập trình song song, PPoPP '05: Chicago, Illinois . New York, NY: Báo chí ACM. trang 48 đỉnh60. ISBN 1-59593-080-9.
  6. ^ libcds – Thư viện C ++ của các thùng chứa không khóa và lược đồ phục hồi bộ nhớ an toàn
  7. ^ liblfds – Một thư viện cấu trúc dữ liệu không khóa, được viết bằng C
  8. ^ Bộ đồng thời – Thư viện AC để thiết kế và triển khai hệ thống không chặn
  9. ^ Herb Sutter. "Mã không khóa: Một cảm giác an toàn sai lầm".
  10. ^ Herb Sutter. "Viết mã không khóa: Một hàng đợi được sửa chữa".
  11. ^ Herb Sutter. "Viết một hàng đợi đồng thời tổng quát".
  12. ^ Herb Sutter. "Rắc rối với ổ khóa".
  13. ^ a b Anthony Williams. "An toàn: tắt: Làm thế nào để không tự bắn vào chân mình bằng nguyên tử C ++". 2015. tr. 20.
  14. ^ Herlihy, Maurice P. (1988). Kết quả không thể thực hiện và phổ quát cho đồng bộ hóa chờ đợi . Proc. Symp ACM hàng năm lần thứ 7. về nguyên tắc tính toán phân tán. trang 276 vang290. doi: 10.1145 / 62546.62593. Sđt 0-89791-277-2.
  15. ^ Phù, Đức tin; Hendler, Daniel; Chết tiệt, Niết bàn (2004). Về điểm yếu cố hữu của các nguyên thủy đồng bộ hóa có điều kiện . Proc. Nguyên tắc ACM Symp.on hàng năm lần thứ 23 của Điện toán phân tán (PODC). trang 80 bóng87. doi: 10.1145 / 1011767.1011780. Sđd 1-58113-802-4.
  16. ^ Kogan, Alex; Petrank, Erez (2011). Hàng đợi chờ miễn phí với nhiều enqueuers và dequeuers . Proc. Symp ACIG SIGPLAN lần thứ 16. về nguyên tắc và thực hành lập trình song song (PPOPP). trang 223 vang234. doi: 10.1145 / 1941553.1941585. Sê-ri 980-1-4503-0119-0.
  17. ^ Michael, Maged; Scott, Michael (1996). Các thuật toán xếp hàng đồng thời đơn giản, nhanh chóng và thực tế không chặn và chặn . Proc. Triệu chứng ACM hàng năm lần thứ 15. về Nguyên tắc tính toán phân tán (PODC). trang 267 bóng275. doi: 10.1145 / 248052.248106. Sđt 0-89791-800-2.
  18. ^ Kogan, Alex; Petrank, Erez (2012). Phương pháp tạo cấu trúc dữ liệu chờ nhanh . Proc. Biểu tượng ACM SIGPLAN lần thứ 17. về nguyên tắc và thực hành lập trình song song (PPOPP). tr 141 141150. doi: 10.1145 / 2145816.2145835. Sê-ri 980-1-4503-1160-1.
  19. ^ Timnat, Shahar; Petrank, Erez (2014). Một mô phỏng chờ miễn phí thực tế cho các cấu trúc dữ liệu không khóa . Proc. Biểu tượng ACM SIGPLAN lần thứ 17. về nguyên tắc và thực hành lập trình song song (PPOPP). trang 357 doi: 10.1145 / 2692916.2555261. Sê-ri 980-1-4503-2656-8.
  20. ^ Herlihy, M.; Luchangco, V.; Moir, M. (2003). Đồng bộ hóa miễn phí tắc nghẽn: Hàng đợi hai đầu làm ví dụ (PDF) . Hội nghị quốc tế lần thứ 23 về hệ thống máy tính phân tán. tr. 522.

Liên kết ngoài [ chỉnh sửa ]