Thiết kế cấu trúc dữ liệu an toàn chủ đề

Question

Tôi phải thiết kế cấu trúc dữ liệu được sử dụng trong môi trường nhiều luồng. API cơ bản rất đơn giản: chèn phần tử, loại bỏ phần tử, truy lục phần tử, kiểm tra phần tử đó tồn tại. Việc triển khai cấu trúc sử dụng khóa ẩn để đảm bảo nguyên tử của một cuộc gọi API duy nhất. Sau khi tôi thực hiện điều này nó trở nên rõ ràng, rằng những gì tôi thực sự cần là atomicity trên một số cuộc gọi API. Ví dụ, nếu một người gọi cần phải kiểm tra sự tồn tại của một phần tử trước khi cố gắng để chèn nó anh ta không thể làm điều đó nguyên tử ngay cả khi mỗi API cuộc gọi duy nhất là nguyên tử:

if(!data_structure.exists(element)) { 
    data_structure.insert(element); 
} 

Ví dụ có phần vụng về, nhưng điểm cơ bản là chúng ta không thể tin tưởng kết quả của cuộc gọi "tồn tại" nữa sau khi chúng ta trở về từ ngữ cảnh nguyên tử (hội đồng được tạo ra rõ ràng cho thấy một cơ hội nhỏ của chuyển đổi ngữ cảnh giữa hai cuộc gọi).

Điều tôi hiện có trong đầu để giải quyết vấn đề này là để lộ khóa thông qua API công khai của cấu trúc dữ liệu. Bằng cách này, khách hàng sẽ phải khóa mọi thứ một cách rõ ràng, nhưng ít nhất họ sẽ không phải tự tạo khóa của mình. Có một giải pháp phổ biến hơn cho các loại vấn đề này không? Và miễn là chúng tôi đang ở đó, bạn có thể tư vấn cho một số tài liệu tốt về thiết kế an toàn thread?

EDIT: Tôi có một ví dụ tốt hơn. Giả sử rằng truy xuất phần tử trả về một tham chiếu hoặc một con trỏ đến phần tử được lưu trữ và không phải là bản sao của nó. Làm thế nào người gọi có thể được bảo vệ để sử dụng một cách an toàn con trỏ này \ tham khảo sau khi cuộc gọi trả về? Nếu bạn nghĩ rằng không trả lại bản sao là một vấn đề, thì hãy nghĩ về các bản sao sâu, tức là các đối tượng cũng nên sao chép các đối tượng khác mà chúng trỏ đến nội bộ.

Cảm ơn bạn.

Answer 1

Bạn cung cấp cơ chế khóa ngoài (xấu) hoặc thiết kế lại API, như putIfAbsent. Cách tiếp cận thứ hai là ví dụ được sử dụng cho concurrent data-structures.

của Java, và khi nói đến các loại bộ sưu tập cơ bản như vậy, bạn nên kiểm tra xem ngôn ngữ bạn chọn có cung cấp ngôn ngữ chuẩn trong thư viện chuẩn hay không.

[sửa] Để làm rõ: khóa bên ngoài là xấu cho người dùng của lớp, vì nó giới thiệu một nguồn lỗi tiềm ẩn khác. Có, đôi khi, khi cân nhắc hiệu suất thực sự trở nên tồi tệ hơn đối với cấu trúc dữ liệu đồng thời so với cấu trúc bên ngoài, nhưng những trường hợp này hiếm, và sau đó chúng thường chỉ có thể được giải quyết/tối ưu hóa bởi những người có kiến ​​thức/kinh nghiệm nhiều hơn tôi.

Một, có thể quan trọng, gợi ý hiệu suất được tìm thấy trong Will's answer bên dưới. [/ edit]

[edit2] Với ví dụ mới của bạn: Về cơ bản bạn nên cố gắng giữ đồng bộ hóa bộ sưu tập và các phần tử được phân tách càng nhiều càng tốt. Nếu tuổi thọ của các phần tử bị ràng buộc với sự hiện diện của nó trong một bộ sưu tập, bạn sẽ gặp vấn đề; khi sử dụng GC, loại sự cố này thực sự trở nên đơn giản hơn. Nếu không, bạn sẽ phải sử dụng một loại proxy thay vì các phần tử thô để có trong bộ sưu tập; trong trường hợp đơn giản nhất cho C++, bạn sẽ đi và sử dụng boost::shared_ptr, sử dụng số đếm nguyên tử. Chèn tuyên bố từ chối trách nhiệm hiệu suất thông thường tại đây. Khi bạn đang sử dụng C++ (như tôi nghi ngờ khi bạn nói về con trỏ và tài liệu tham khảo), sự kết hợp của boost::shared_ptr và boost::make_shared sẽ đủ trong một thời gian. [/ edit2]

Answer 2

Điều gì về việc chuyển séc hiện tại sang phương thức .insert()? Một khách hàng gọi nó và nếu nó trả về false bạn biết rằng đã xảy ra sự cố.Giống như những gì malloc() làm trong đồng bằng cũ C - trở về NULL nếu không thành công, thiết lập ERRNO.

Rõ ràng bạn cũng có thể trở lại là một ngoại lệ, hoặc một thể hiện của một đối tượng, và làm phức tạp cuộc sống của bạn lên từ đó ..

Nhưng làm ơn, đừng dựa vào thiết lập ổ khóa riêng của họ sử dụng.

Answer 3

Đôi khi nó đắt tiền để tạo thành phần tử được chèn vào. Trong những tình huống này, bạn không thể thực sự tạo ra các đối tượng có thể đã tồn tại chỉ trong trường hợp chúng thực hiện.

Phương pháp insertIfAbsent() để trả về 'con trỏ' bị khóa - nó chèn một trình giữ chỗ vào cấu trúc bên trong sao cho không có chuỗi nào khác có thể tin rằng nó không có, nhưng không chèn đối tượng mới. Trình giữ chỗ có thể chứa một khóa để các luồng khác muốn truy cập phần tử cụ thể đó phải đợi cho nó được chèn vào.

Trong ngôn ngữ RAII như C++, bạn có thể sử dụng lớp ngăn xếp thông minh để gói gọn con trỏ được trả về sao cho nó tự động cuộn lại nếu mã gọi không cam kết. Trong Java của nó một chút chậm hơn với phương pháp finalize(), nhưng vẫn có thể làm việc.

Một cách tiếp cận khác là để người gọi tạo đối tượng không có mặt, nhưng đôi khi thất bại khi chèn thực tế nếu chuỗi khác đã 'thắng cuộc đua'. Đây là cách, ví dụ, cập nhật memcache được thực hiện. Nó có thể hoạt động rất tốt.

Answer 4

Trước hết, bạn nên thực sự tách mối quan tâm của mình. Bạn có hai điều cần lo lắng về:

1. Cơ sở hạ tầng và phương pháp của nó.
2. Đồng bộ hóa luồng.

Tôi khuyên bạn nên sử dụng giao diện hoặc lớp cơ sở ảo đại diện cho loại cơ sở hạ tầng bạn đang triển khai. Tạo một thực hiện đơn giản mà không làm bất kỳ khóa nào cả. Sau đó, tạo một triển khai thứ hai để kết thúc triển khai đầu tiên và thêm khóa trên đầu trang của nó. Điều này sẽ cho phép triển khai hiệu quả hơn khi không cần khóa và sẽ đơn giản hóa mã của bạn.

Dường như bạn đang triển khai một số loại từ điển. Một điều bạn có thể làm là cung cấp các phương thức có ngữ nghĩa tương đương với câu lệnh kết hợp. Ví dụ: setdefault là một hàm hợp lý để cung cấp điều đó sẽ đặt giá trị chỉ khi khóa tương ứng không tồn tại trong từ điển.

Nói cách khác, đề xuất của tôi là tìm ra kết hợp các phương thức thường được sử dụng cùng nhau và chỉ cần tạo các phương thức API thực hiện kết hợp các phép toán đó một cách nguyên tử.

Answer 5

Trong kiểu thời trang RAII, bạn có thể tạo đối tượng accessor/handle (không biết nó được gọi như thế nào, có thể tồn tại một mẫu này), ví dụ: a Danh sách:

template <typename T> 
class List { 
    friend class ListHandle<T>; 
    // private methods use NO locking 
    bool _exists(const T& e) { ... } 
    void _insert(const T& e) { ... } 
    void _lock(); 
    void _unlock(); 
public: 
    // public methods use internal locking and just wrap the private methods 
    bool exists(const T& e) { 
     raii_lock l; 
     return _exists(e); 
    } 
    void insert(const T& e) { 
     raii_lock l; 
     _insert(e); 
    } 
    ... 
}; 

template <typename T> 
class ListHandle { 
    List<T>& list; 
public: 
    ListHandle(List<T>& l) : list(l) { 
     list._lock(); 
    } 
    ~ListHandle() { 
     list._unlock(); 
    } 
    bool exists(const T& e) { return list._exists(e); } 
    void insert(const T& e) { list._insert(e); } 
}; 


List<int> list; 

void foo() { 
    ListHandle<int> hndl(list); // locks the list as long as it exists 
    if(hndl.exists(element)) { 
     hndl.insert(element); 
    } 
    // list is unlocked here (ListHandle destructor) 
} 

Bạn sao chép (hoặc thậm chí ba lần) giao diện công cộng, nhưng bạn cung cấp cho người dùng lựa chọn giữa khóa bên ngoài và an toàn và thoải mái ở bất cứ đâu.