khóa vùng chứa và khả năng hiển thị miễn phí

Question

Tôi đã nhìn thấy một số cài đặt ngăn xếp miễn phí của ngăn xếp ... Câu hỏi của tôi liên quan đến khả năng hiển thị chứ không phải nguyên tử. Ví dụ làm các yếu tố (không con trỏ) của khóa ngăn xếp miễn phí phải có nhiều nhất 64bit? Tôi nghĩ vậy, bởi vì bạn không thể bảo đảm khả năng hiển thị. Ví dụ thực tế: cấu trúc này có thể được chèn và xóa an toàn khỏi thùng chứa không có khóa

struct person 
{ 
    string name; 
    uint32_t age; 
} 

EDIT: một số người bị nhầm lẫn bởi câu hỏi. Để giải thích một chút: nếu nhà văn đẩy người vào ngăn xếp, người đọc nhận được nó, nó có đảm bảo rằng người đọc thấy (bộ nhớ khả năng hiển thị) đúng nội dung của người đó.

Answer 1

Tôi có thể sai, nhưng tôi nghĩ câu hỏi là không chính xác.

Hướng dẫn nguyên tử đối phó thường với dữ liệu độ dài con trỏ đơn; nhiều nhất, với hai chiều dài con trỏ có giá trị của dữ liệu.

Cấu trúc điển hình không thể được thao tác nguyên tử vì nó quá lớn.

Vì vậy, ngăn xếp không khóa sẽ chỉ và sẽ điều khiển con trỏ đến các phần tử (AFAIK cần phải căn chỉnh trên các đường biên độ dài con trỏ - Tôi biết không có nền tảng nào trong trường hợp này).

Answer 2

Có cấu trúc có thể được sử dụng. Bởi vì tất cả những gì bạn cần cho cấu trúc dữ liệu không có khóa là một số cách cập nhật nguyên tử một giá trị duy nhất đại diện cho các bên trong của cấu trúc. Kích thước của phần tử hoặc trọng tải sẽ không có bất kỳ tác động nào đến bản chất không có khóa của nó.

Theo tôi được biết, một cấu trúc dữ liệu lock-free sẽ làm việc như vậy:

1. Sao chép dữ liệu
2. Sửa đổi các dữ liệu
3. nguyên tử kiểm tra xem các đối tượng ban đầu đã được chưa sửa đổi và cập nhật nó
4. Nếu không lặp lại từ đầu

Vì vậy, miễn là bước thứ ba có thể được thực hiện nguyên tử tất cả đều tốt.

Làm cho các yếu tố tự cập nhật nguyên tử sẽ không cung cấp cho bạn bất kỳ lợi ích nào do vùng chứa phải quản lý chúng theo nhóm chung.

Answer 3

Lưu ý: Vui lòng đánh dấu câu trả lời này là đúng nếu bạn thực sự thử nghiệm phương pháp này.

thiệu về câu hỏi của bạn cho dù dưới đây struct được chèn một cách an toàn và gỡ bỏ khỏi thùng miễn phí khóa:

struct person 
{ 
    string name; 
    uint32_t age; 
} 

chuỗi Multi-byte của bất kỳ chiều dài có thể được chèn một cách an toàn/bị xóa khỏi thùng miễn phí khóa nếu bạn sử dụng một mã hóa dự phòng. Giả sử rằng chúng ta đã có các chỉ dẫn nguyên tử để thao tác 4 byte tại một thời điểm (32 bit). Trong trường hợp đó, chúng ta có thể mã hóa các lĩnh vực uint32_t age như vậy:

struct age_t 
{ 
    uint32_t age_low; 
    uint32_t age_high; 
} 

Trường age_low lưu trữ các bit thấp (ví dụ, với mức thấp nhất 16 bit) của 32-bit uint32_t age. Trường age_high lưu trữ các bit cao còn lại.Về mặt lý thuyết :

struct age_t 
{ 
    uint16_t age_low; 
    uint16_t id_low; 
    uint16_t age_high; 
    uint16_t id_high; 
} 

Các trường id_low và id_high nên chứa một ID xác định các nhà văn.

Đọc được thực hiện dưới dạng hai lần đọc 32 bit nguyên tử và thành công nếu tất cả các phần id_ tương đương với nhau. Nếu nó không thành công, hoạt động đọc cần được khởi động lại.

Bản ghi được thực hiện dưới dạng hai bản ghi 32 bit nguyên tử và được theo sau bởi giá trị đọc của toàn bộ giá trị age_t. Ghi thành công nếu: đọc được đề cập trong câu trước thành công và các ID được đọc tương đương với các ID viết.

Giới thiệu về giá trị string: nguyên tắc giống nhau. Bạn chỉ cần tìm ra cách tách giá trị nhị phân của nó tương tự như cách giá trị age được chia nhỏ. Tương tự đối với việc đọc/ghi toàn bộ cấu trúc person.

Answer 4

Tôi phải thừa nhận việc được một chút bối rối bởi câu hỏi bản thân mình ...

Khóa miễn phí dữ liệu cấu trúc tồn tại bằng cách thao tác con trỏ (kích thước máy & liên kết) đến nút. Các nút đó sau đó chứa "nội dung" thực của cấu trúc dữ liệu không khóa của bạn. Nội dung đó có thể có bất kỳ kích thước tùy ý nào bạn muốn, vì vậy cấu trúc của bạn có thể được đặt ở đó. Nút thông thường cho cấu trúc dữ liệu không có khóa trông giống như sau:

struct Node {ATOMIC_PTR tiếp theo; Nội dung; }

nơi nội dung có thể là bất kỳ nội dung nào bạn muốn, con trỏ tới bộ nhớ chứa nội dung nào đó hoặc bộ nhớ trực tiếp chứa nội dung nào đó. Khả năng hiển thị ở đây không phải là vấn đề, vì khi sửa đổi cấu trúc dữ liệu không có khóa của bạn, trước tiên bạn sẽ cấp phát một nút mới, sau đó điền nó với nội dung mong muốn và cuối cùng sử dụng các hoạt động nguyên tử để đặt các con trỏ liên quan khác nhau. Vì đó là điều cuối cùng bạn làm, và những hoạt động đó thường liên quan đến các rào cản bộ nhớ để đảm bảo độ nhớt và trật tự, bạn ổn.

Answer 5

Thùng chứa an toàn chủ đề (không khóa hoặc có khóa cho vấn đề đó) giải quyết sự an toàn của danh mục/vật chứa không phải là sự an toàn của các vật phẩm bạn đưa vào thùng chứa. Vì vậy, ngăn xếp không khóa sẽ đảm bảo push và pop là an toàn và không có khóa nhưng nếu bạn có hai luồng khác nhau chứa con trỏ đến cùng một cá thể struct (ví dụ: chuỗi được đẩy vào ngăn xếp vẫn giữ được trình quét và chủ đề bật stack), bạn sẽ phải sử dụng một số biện pháp thread-an toàn khác để đảm bảo các cấu trúc nhất quán

Answer 6

Theo của QnA khác trên SO,

• Does Interlocked.CompareExchange use a memory barrier?
• question about lock free queues

mọi lệnh liên kết x86 (bao gồm CAS) ngụ ý một hàng rào bộ nhớ đầy đủ. Vì vậy, ít nhất là trên x86, chúng ta không cần phải quan tâm đến khả năng hiển thị của các thành phần của các thùng chứa không có khóa (giả sử rằng chúng sử dụng CAS.)

Answer 7

Người ta có thể triển khai thực hiện an toàn luồng dequeue cho các phần tử dữ liệu có kích thước tùy ý nếu các phần tử không phải được lưu trữ trong ngăn xếp hoặc hàng đợi theo bất kỳ thứ tự cụ thể nào và nếu sử dụng hàng đợi an toàn để giữ các chỉ mục của các mặt hàng không được phân bổ, cũng như một dequeue thread-an toàn để giữ các chỉ số của các khe dữ liệu mà giữ các mặt hàng enqueued/xếp chồng lên nhau. Viết một mục vào dequeue sẽ kéo kéo một số từ hàng đợi "không được phân bổ", ghi dữ liệu mong muốn vào khe đó, và sau đó enqueueing chỉ số của số đó trong dequeue "chính". Tìm nạp một mục sẽ yêu cầu kéo số của nó từ cồn "chính", sao chép nó ở nơi khác, và sau đó enqueueing số đó trong hàng đợi "unallocated slots". Một báo trước với cách tiếp cận này là nó trong khi nó có thể "không có khóa" như một sợi mà các quầy hàng không thể tự ý trì hoãn tiến trình của các luồng khác, một luồng được trả về khoảng thời gian nó thu được chỉ mục khe từ một hàng đợi và thời gian nó lưu trữ trong hàng đợi khác có thể khiến một vùng mảng không thể sử dụng được trong một khoảng thời gian tùy ý. Ngược lại, một số việc triển khai hàng đợi hoặc xếp hàng chờ đợi được sử dụng với các kiểu dữ liệu nhỏ hơn không có giới hạn đó. Một luồng có thể biến mất khỏi sự tồn tại trong khi đọc hoặc viết, và hệ thống sẽ ở trong trạng thái hợp lệ biểu thị rằng đọc hoặc viết hoàn thành, hoặc ở trạng thái hợp lệ cho biết nó chưa bao giờ bắt đầu.