Implement lock for Shared Objects in MCS

[haminhcong]

Trong tuần này, em đã đọc semaphore của eventlet và đã thử nghiệm semaphore để lock một Shared Object được sử dụng chung giữa các request.

Khi sử dụng semaphore, thì em chỉ quan tâm tới 4 phương thức sau:

• Phương thức khởi tạo - Semaphore() : Khởi tạo một đối tượng semaphore(), xác định số lượng tối đa các process được đồng thời acquire bằng semaphore counter
• Phương thức acquire(): nếu semaphore counter < = 0, thì luồng thực thi của green thread x ngừng ở phương thức aquire và process chuyển sang thực hiện greenthread khác, green thread x chờ cho đến khi process thực thi nó và semaphore counter > 0 thì thực hiện: giảm semaphore counter đi 1 - lock Shared Object lại, sau đó nhảy vào thực hiện các câu lệnh phía sau acquire
• Phương thức release(): Tăng semaphore counter lên 1, nếu như trước khi tăng semaphore counter = 0 và có một số green thread trong process đang ngừng lại và chờ tại câu lệnh acquire() thì process tiến hành switch và chuyển sang thực thi thread đó - phương thức unlock Shared Object
• Phương thức locked(): Phương thức cho phép kiểm tra xem giá trị hiện tại của semaphore counter của Shared object này có >0 hay không, nếu locked() = True, tức là Shared Object đang bị khóa - object chung đang được green thread khác acquire, còn nếu mà locked() = False thì có nghĩa là Shared Object không bị khóa

Với mỗi một Shared Object, em khởi tạo một Semaphore(1) cho Object đó, để chỉ ra rằng trong một thời điểm chỉ có một thread được quyền thay đổi nội dung của Shared Object đó. Để thuận tiện, Semaphore cho Shared Object sẽ được tích hợp vào Shared Object như một thuộc tính của Shared Object, và xây dựng 4 phương thức ở phía trên trong Shared Object.

Trong đồ án của anh kiên, thì em nghĩ là có 2 phương án sau để sử dụng semaphore quản lý điều khiển việc các request truy cập và sử dụng Shared Object.

• Phương án 1, là với các request read (chỉ đọc Shared Object) thì em chỉ kiểm tra xem tài nguyên có đang bị lock hay không, nếu tài nguyên đang bị lock thì em đang tính là phản hồi cho người dùng tài nguyên mà người dùng muốn truy cập đang bị thay đổi, không thể truy cập vào thời điểm này.

Còn nếu là thao tác write ( làm thay đổi Shared Object) thì thực hiện lock Shared Object bằng phương thức acquire(), sử dụng va thay đổi Shared Object, sau khi thay đổi xong thì release() để unlock Shared Object.

Ưu điểm của việc sử dụng phương thức này, là khi phục vụ các request read (chiếm đa số) thì tài nguyên không bị lock - tức là hiệu năng tốt. Tuy nhiên nhược điểm của phương thức này là không đảm bảo tính nhất quán của dữ liệu trong một thread. Ví dụ trường hợp sau có thể xảy ra:

Trong một thời điểm, wsgi process của em đang phục vụ 2 request/greenthread 1 và 2, với các thao tác xử lý của 1 chỉ liên quan tới việc đọc Shared Object, còn thao tác xử lý của 2 thì thực hiện đọc/ghi Shared Object:

Với việc sử dụng phương án 1, thì chỉ có các request write lên shared Object mới lock lại, còn các thao tác read thì chỉ check trạng thái của shared Object xem shared Object có bị lock hay không.

Greenthread 1:

def green_thread_1(request):
    if not shared_object.locked(): # semaphore object đã được tích hợp sẵn vào shared_object
        x1 = shared_object
        # Do some work
        ....
        # Do some I/O method
        ....
        # Do some work
    if not shared_object.locked():
        x2  = shared_object
        ....

Greenthread 2:

def green_thread_1(request):
    shared_object.acquire()
        # do_some_work_on_shared Object
        # do_some_I/O
        # write_change_to_shared_object
    shared_object.release()

• Phương án 2, là cứ trước khi request - green thread sử dụng tài nguyên chung thì lock nó lại, kể cả read hay write, cho đến bao giờ request sử dụng xong tài nguyên chung thì mới release giải phóng.

Greenthread 1:

def green_thread_1(request):
    shared_object.acquire()
        x1 = shared_object
        # Do some work
        ....
        # Do some I/O method
        ....
        # Do some work
        x2  = shared_object
        ....
        # Do some work
   shared_object.release()
        # Do some work

Greenthread 2:

def green_thread_1(request):
    shared_object.acquire()
        # do_some_work_on_shared Object
        # do_some_I/O
        # write_change_to_shared_object
    shared_object.release()

2 phương án trên đều có ưu điểm và nhược điểm.

Với phương án 2, thì ưu điểm của nó là mình kiểm soát tài nguyên tốt hơn, đảm bảo được tính nhất quán của Shared Object trong suốt quá trình Shared Object đó được greenthread sử dụng - tức là trong khoảng thời gian green thread khóa và sử dụng Shared Object, thì hoặc là giá trị của Shared Object không đổi, hoặc là giá trị của Shared Object được thay đổi chỉ bởi chính green thread đó chứ không thể bị green thread khác thay đổi, trong khi green thread này vẫn đang khóa Shared Object .

Nhược điểm của phương án này là trong suốt thời gian nó sử dụng Shared Object, thì chỉ có mình nó được sử dụng Shared Object, và tất cả các green thread khác muốn sử dụng Shared Object này đều phải chờ tới bao giờ Shared Object được release mới được sử dụng. Trong khi như em nói, trong hệ thống của mình thì thao tác Read chiếm một tỉ trọng lớn hơn rất nhiều cho với thao tác Write, nên nếu dùng thao tác lock cứng này thì có lẽ hiệu năng của hệ thống sẽ giảm đi nhiều.

Với phương án 1, thi ưu điểm của nó là hiệu năng cao, vì các green thread chỉ thực hiện read sẽ không khóa Shared Object lại mà chỉ kiểm tra trạng thái của Shared Object đã là sẵn sàng phục vụ (không bị lock) không ? Do đó trong cùng 1 khoảng thời gian, có thể nhiều green thread cùng sử dụng Shared Object mà không phải chờ nhau.

Nhưng nhược điểm của phương án 1, là không đảm bảo rằng, giá trị của Shared Object luôn được đảm bảo là nhất quán, tức là giữa 2 lần greenthread đọc shared Object, Shared Object có thể bị thay đổi bởi 1 Green thread khác. Như trong phương án 1 của ví dụ mà em nêu ra, em giả sử rằng green thread 1 thực hiện trước. Lúc em gọi x1 = shared_object thì shared_object = 5. Nhưng sau đó em thực hiện I/O thì luồng điều khiển chuyển qua thực hiện green_thread 2, lúc này green thread 2 thay đổi giá trị của shared_object thành 9, rồi luồng điều khiển chuyển lại về green thread 1, thì khi câu lệnh x2 = shared_object được thực hiện thì x2 có giá trị là 9 - hay shared_object = 9. Rõ ràng là nếu như thế này thì rất khó để xử lý khi mà green thread không điều khiển được giá trị của shared_object, hay còn gọi là race condition

Thứ 2, là em chưa tìm ra giải pháp thích hợp để xử lý trường hợp if not shared_object.locked(): trả về false, lúc đấy không lẽ mình báo cho người dùng là tài nguyên mà người dùng muốn truy cập đang bị thay đổi, người dùng cần thử lại vào lúc khác ? Hoặc nếu như câu lệnh checklog ở green thread 1:

 if not shared_object.locked():
        x2  = shared_object

trả về false, tức là shared_object đang bị khóa thì xử lý thế nào, vì mình lỡ xử lý đoạn đầu của request rồi, không thể bỏ ngang chừng request như thế này được.

Như vậy, theo em thấy thì cả 2 phương án đều có cái hay và cái dở. Nếu nói về để đảm bảo an toàn nhất, thì có lẽ em lựa chọn phương án 2. Phương án 1 tạo ra quá nhiều race condition. Nhưng vấn đề là hiệu năng mà phương án 1 đem đến là quá lớn, vì như em nói là rất ít khi tài nguyên shared Object bị thay đổi trong quá trình hệ thống hoạt động. Nên em đang phân vẫn giữa cả 2 phương án.

Phương án 1 sẽ khả thi nếu như hệ thống chỉ đọc tài nguyên chia sẻ chung 1 lần, hoặc trong quá trình sử dụng tài nguyên chia sẻ chung hệ thống không phát sinh ra I/O.

Còn phương án 2 luôn là giải pháp dự phòng, vì phương án này luôn là phương án an toàn hơn phương án 1.

Phương thức xây dựng và sử dụng semaphore thì em hiểu như thế này, nhưng sử dụng semaphore như thế nào trong đồ án của anh Kiên thì thực sự là em phải hiểu xem anh Kiên dùng các shared variable như thế nào trong các phương thức phục vụ request của người dùng, thì mới chọn ra được giải pháp hợp lý hơn cả trong 2 giải pháp trên, hoặc là tạo ra một giải pháp sử dụng semaphore mới phù hợp với hệ thống cụ thể của anh Kiên xây dựng. Em nghĩ là công việc thiết kế cách sử dụng Shared Object của em gắn liền với mọi phương thức mà anh Kiên xây dựng và phải dựa trên đặc điểm sử dụng shared Object của các phương thức này, chứ còn em chịu, không làm độc lập được.

Hôm trước anh Kiên có nói là sử dụng Shared Object là cái Ring Dict, và em xây dựng semaphore để khóa cái RingDict lại, nhưng em nghĩ là không phải. RingDict nó là tài nguyênchia sẻ chung thật, nhưng thật ra là gom nhóm các ring lại với nhau để dễ tìm kiếm hơn, chứ Ring của account này độc lập và không liên quan tới Ring của account kia. Em nghĩ là các tài nguyên Shared Object mà mình phải sử dụng semaphore để thiết kế điều khiển truy cập ở đây là từng cái Ring của các account, vì một cái Ring của một account thì có thể được nhiều request sử dụng chung, tức là n ring thì em có n cái semaphore, mỗi cái ring sẽ có 1 cái semaphore riêng, quản lý việc truy cập cái ring đó, còn giữa các cái ring thì sẽ độc lập với nhau.

[hieulq]

@haminhcong nghĩ phức tạp quá, cách làm tốt nhất tới thới điểm này là phương án 1 của em, không ai dùng cách 2 nữa vì quá chậm. Thứ 2 là khi code, cần tổ chức code cho tốt để tránh race condition, việc thread1 acquire semaphore để gán cho x1 rồi lại nhảy sang thread2 rồi lại nhảy về thread1 là chuyện cần tránh. Greenthread nó đẻ ra là để user có thể control việc nhảy qua nhảy lại bất thình lình này. Thứ 3 là với mỗi shared object có thể đánh revision để tránh race condition toàn cục. Đọc thêm về CAS methodology ở [1]. Đọc thêm link [2] để thấy ứng dụng của CAS trong Nova và MariaDB. Thứ 4 là cần tổ chức code cho chuẩn, không có chuyện viết mỗi greenthread là 1 hàm như thế kia, em hình dung em đang code 1 web server/service thì làm gì có chuyện viết hàm thế kia được. Anh expect là em chỉ lấy ví dụ thôi.

[1]. https://en.wikipedia.org/wiki/Compare-and-swap [2]. http://www.joinfu.com/2015/01/understanding-reservations-concurrency-locking-in-nova/

@ntk148v đọc thêm cùng Công để nắm vững hơn lý thuyết nhé. Cái CAS có thể đưa vào đồ án, chém các thầy không hiểu gì đâu.