Vấn đề với lock

Là một lập trình viên từng làm việc với phần mềm đa nhiệm ( multi thread ), lock chắc chắn không hề xa lạ với bạn. Khi nhiều thread cùng làm việc với một dữ liệu chung (shared data structure) thì chúng ta cần có một cơ chế để chỉ cho phép một thread duy nhất truy cập và sửa đổi dữ liệu đó, và cơ chế phổ biến nhất chình là lock.
Việc tranh chấp lock gọi là Lock contention. Lock contention chính là điểm mấu chốt dẫn đến hiệu năng không được như mong muốn khi lập trình song song.
Mặc dù lock là một kĩ thuật rất phổ biến và không tránh khỏi trong hầu hết các bài toán nhưng làm việc tốt với các kĩ thuật lock là không hề dễ dàng và dễ dẫn đến các sai lầm, trong đó phổ biến nhất là các lập trình viên có xu hướng lock quá cần thiết dẫn đến giảm hiệu năng của ứng dụng, cũng như mắc phải các sai lầm về logic dẫn đến deadlock hay là thread chết đói do không có tài nguyên về CPU (starvation).
Dưới đây chúng ta hãy thử duyệt qua một vài điểm yếu nữa của việc sử dụng lock:

Dead lock và Priority inversion

Dead lock là chuyện xảy ra khi 2 ứng dụng đợi tài nguyên lẫn nhau dẫn đến looip vô tận.
Priority inversion là khi một process có độ ưu tiên thấp lại lock một tài nguyên thuộc về một process có độ ưu tiên cao hơn -> không có tôn ti trật tự.

Convoying problem

Convoying dịch ra là 'hộ tống', nói về vấn đề gặp phải khi một loạt process phụ thuộc chung vào một tài nguyên nhưng process chạy chậm nhất lại lanh chanh giữ lock đầu tiên, khiến cho những thằng nhanh hơn lại phải chờ.

Async-signal safety

Vấn đề này thường liên quan đến lập trình hệ thống, khi mà một hàm hệ thống (system call) có thể bị ở trạng thái gián đoạn (interrupt) bởi một signal nào đó như sigkill hay sighup. Vậy điều gì xẩy ra khi bạn có một hàm handler cho sigkill mà đang khi đang execute hàm đó thì một sigkill khác lại được gửi đến :scream: . Bạn sẽ nghĩ ngay đến việc lock lại xử lý handler này, tuy nhiên việc đó sẽ gây ra deadlock ngay lập tức (immediate deadlock), bởi bản thân hàm đó sẽ cố để lấy cái lock mà chính bản thân nó đang giữ. Một operation gọi là Async-Signal-Safe khi mà nó đảm bảo không làm phiền đến các operation khác khi mà chúng đang bị gián đoạn, tuy nhiên vô cùng đáng buồn là malloc với free lại không nằm trong list đó :(.

Bạn có thể tìm hiểu thêm tại https://docs.oracle.com/cd/E19455-01/806-5257/gen-26/index.html

Về lock free programming

Lock free programming là gì?

Lockless programming is a way to safely share changing data between multiple threads without the cost of acquiring and releasing locks.

Như cái tên của nó, lock free (hay lockless) là các kĩ thuật lập trình song song trên đó tài nguyên có thể được chia sẻ, thay đổi một cách an toàn mà không cần khởi tạo hay release lock, cũng như sử dụng bất kì kĩ thuật lock khác như semaphore hay mutex..

Là một kĩ thuật hướng đến sự hoàn hảo trong multi thread programming, lock free là một kĩ thuật rất khó, và không thể thực hiện được nếu thiếu sự hỗ trợ của hardware.

Một trong những paper lâu đời và nổi tiếng về kĩ thuật lập trình lock free là của Leslie Lamport (Turing award holder) những năm 1977 với tựa đề là "Concurrent Reading and Writing":
https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf

Bài báo nói về một cấu trúc dữ liệu cho lock free gọi là non-blocking buffer cũng như những giới hạn của cấu trúc đó.

Để tiếp cận với lock free programming, thì việc thiết kế một giải thuật tổng quát cho mọi vấn đề là một điều rất khó (vì có quá nhiều edge case có thể xẩy ra trong lập trình song song, mà mỗi edge case lại mang một đặc trưng mà khó có thể tổng quát hoá được).

Như đã nói ở trên, lock free cần sự hỗ trợ của hardware, thông qua các phép toán cơ bản (primitive) đơn giản mà hardware hỗ trợ .Các phép toán này còn gọi là Atomic operation (hay gọi là các thao tác "nguyên tử", tức là không thể chia nhỏ hơn được nữa). Một thread không thể quan sát được một hành động diễn ra giữa chừng (half-complete) nhờ có các phép toán đó. Một số ví dụ về các phép toán đó như là CAS (Compare and set), LL/CS (Load linked, store condition), MCAS (Multi-word CAS), CAS2, CAS/N.

Compare and Set nghĩa là phép toán mà trước khi thay đổi một biến số nào đó thì CPU sẽ phải so sánh nó với giá trị trước khi hàm CAS được gọi, nếu giá trị khác nhau (đã bị thay đổi bởi một thread khác) thì sẽ không cho phép thực hiện phép thay đổi đó.

Ngoài ra thay vì thiết kế một giải thuật tổng quan (general algorithm), thì thường các nhà thiết kế giải thuật sẽ thiết kế các cấu trúc dữ liệu lock free (lock-free data structures) thay thế. Và các giải thuật chỉ cần dựa trên các cấu trúc dữ liệu này thì cũng đã giải quyết được kha khá các bài toán song song. Dưới đây chúng ta sẽ thử xem qua một vài cấu trúc dữ liệu:

1. Lock-free stack (LIFO queue)

class Node {  
  Node * next;
  int data;
};
Node * head;  

Push operation:

void push(int t) {  
  Node* node = new Node(t);
  do {
     node->next = head;
  } while (!cas(&head, node, node->next));
}

Pop operation

bool pop(int& t) {  
   Node* current = head;
   while(current) {
     if(cas(&head, current->next, current)) {
       t = current->data;
       return true;
     }
     current = head;
   }
   return false;
}

Ở đây cas(*Node x, *Node oldValue, *Node newValue) có nghĩa set biến X bằng newValue và so sánh với oldValue để phán đoán việc thay đổi giá trị. Bạn có thể thấy cấu trúc dữ liệu lock free chỉ đơn thuần áp dụng các phép toán atomic kết hợp với vòng lặp while.

2. Lock-free linked list

Lock free linked list là một ví dụ rất tốt để chứng minh về vấn đề hiệu năng của việc sử dụng lock hay không sử dụng lock. Với linked list thì đôi khi bạn sẽ phải traverse một quãng đường dài (để tìm kiếm một phần tử chẳng hạn). Nếu sử dụng lock thông thường thì bạn sẽ phải lock toàn bộ list khi cần traverse!! (nghe đã thấy hiệu năng thấp). Implementation của phần này khá phức tạp do liên quan đến cả thao tác delete nên các bạn có thể tham khảo thêm ở đây: http://people.csail.mit.edu/bushl2/rpi/project_web/page5.html

Ngoài ra có một paper khá nổi tiếng về lock free linked list với tiêu đề「A Pragmatic Implementation of
Non-Blocking Linked-Lists」
https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf

ABA problem

Với lock free sử dụng atomic operationoperation sẽ xẩy ra một hiện tượng rất thú vị gọi là ABA, hiện tượng đó được diễn giải như dưới đây:

  • Thread 1 nhìn vào một biến chia sẻ X và định thay đổi nó. Lúc thread 1 nhìn thì X có giá trị là A.
  • Thread 1 tính toán một vài thứ thú vị dựa trên sự thật là X có giá trị là A
  • Thread 2 chạy, biến đổi X thành giá trị là B.
  • Thread 1 gọi CompareAndSet nhìn thấy giá trị X đã bị đổi, sau đó retry.
  • Thread 2 thay đổi lại giá trị X là A
  • Thread 1 thực hiện lại và thành công với CompareAndSet

Vấn đề ở đây chính là việc Thread 1 "tưởng" là mình đã Set thành công khi biến X không bị thay đổi từ bên ngoài nhưng thực ra X đã bị thay đổi mà Thread 1 không hề biết. Khi lock free stack gặp phải vấn đề này, thì sẽ có khả năng bạn gọi pop 2 lần trên cùng một node và sẽ bị segfault.

Trên wiki có một ví dụ rất dễ hiểu về ABA

John is waiting in his car at a red traffic light with his children. His children start fighting with each other while waiting, and he leans back to scold them. Once their fighting stops, John checks the light again and notices that it's still red. However, while he was focusing on his children, the light had changed to green, and then back again. John doesn't think the light ever changed, but the people waiting behind him are very mad and honking their horns now.

Bạn có thể tìm hiểu thêm về ABA thông qua google: https://www.google.co.jp/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=aba%20problem%20stack

hay là wiki:
https://en.wikipedia.org/wiki/ABA_problem

Để vượt qua vấn đề này thì chúng ta có thể thêm một biến là "update count" dựa vào khái niệm "doubleword CAS" (cần sự hỗ trợ phần cứng)

Chú ý và kết luận

  • Lock free không phải là thuốc chữa cho bài toán tranh chấp tài nguyên. Việc nhiều thread cùng tranh chấp một tài nguyên vẫn có thể xẩy ra, chỉ khác là ở tần suất thấp hơn, và được giải quyết tốt hơn (về mặt giải thuật + sự hỗ trợ về phần cứng). Starvation (chết đói) , hay là hiện tượng khi một vài thread không nhận được resource đủ để chạy vẫn có thể xảy ra.
  • Để áp dụng lock free thì bạn cần
    • Bài toán đủ đơn giản
    • Bạn tự nghĩ ra được một thuật toán lock free để áp dụng cho một vài trường hợp hẹp.
  • Lock-free khác với Wait-free. Wait free cũng là một từ khoá quan trọng trong lập trình song song. Wait free là:
    • Mỗi một thao tác sẽ hoàn thành trong một số hữu hạn bước
    • Wait free bao hàm lock free (nhưng không có nghĩa ngược lại)
    • Wait free là một bài toán còn khó hơn lock free, chúng ta sẽ tham khảo
  • Lock free sẽ làm tăng hiệu năng cho ứng dụng nhưng cũng không hề để làm đúng đắn (ABA là một ví dụ)

Tham khảo