Trong các hệ thống phân tán hoặc xử lý đa luồng (Multi-threading), việc thực hiện thao tác khóa toàn bộ danh sách (Global Lock) trên Linked List gây ra nút thắt cổ chai hiệu năng nghiêm trọng. Làm thế nào để áp dụng kỹ thuật Hand-over-Hand Locking (Lock Coupling) cho Linked List một cách an toàn?

Question

Accepted Answer

Bản chất vấn đề
Khi nhiều luồng cùng thao tác trên một Linked List, việc dùng một Mutex duy nhất cho toàn bộ danh sách sẽ làm mất đi tính song song. Hand-over-Hand Locking cho phép nhiều luồng duyệt qua danh sách cùng một lúc bằng cách chỉ khóa từng node riêng lẻ. Luồng hiện tại giữ khóa của node tiền nhiệm, sau đó lấy khóa của node hiện tại, và chỉ thả khóa của node tiền nhiệm khi đã chuyển thành công sang node tiếp theo.
Cơ chế hoạt động

Luồng bắt đầu bằng việc khóa node head.
Tiến hành kiểm tra giá trị trên node head.
Nếu cần chuyển sang node tiếp theo (next), luồng tiến hành khóa node next trước khi mở khóa node hiện tại.
Lặp lại quy trình cho đến khi tìm thấy node mục tiêu.

Thách thức và Lưu ý Enterprise

Deadlock Risk: Thứ tự khóa luôn phải tuân theo chiều từ head đi xuống (hướng xuôi). Không được phép khóa ngược từ dưới lên trừ khi sử dụng thuật toán phức tạp hơn.
Overhead: Việc gọi liên tục các hàm cấp thấp như pthread_mutex_lock hoặc ReentrantLock tạo ra chi phí chuyển đổi ngữ cảnh (Context Switching). Do đó, kỹ thuật này chỉ thực sự hiệu quả khi danh sách rất dài và thời gian xử lý trên mỗi node lớn.

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi linked lists liên quan cùng chủ đề