Mutex và hàng đợi công việc có giới hạn

Mutex bảo vệ hàng đợi công việc có giới hạn khi nó giữ được quan hệ giữa các trường trạng thái. Khóa riêng từng lần truy cập mảng vẫn có thể để đầu đọc, đầu ghi và số phần tử lệch nhau. Nếu đang triển khai bộ đệm vòng, bạn nên viết bất biến của hàng đợi trước khi chọn chỗ bắt đầu và kết thúc vùng khóa.

Dùng hàng đợi chứa tối đa ba công việc dạng số nguyên. head chỉ ô sẽ lấy tiếp theo, tail chỉ ô sẽ ghi tiếp theo, còn count cho biết số công việc hiện có. Mô hình giả định nhiều bên thêm và lấy công việc, cùng dùng một mutex. Mỗi thao tác hoặc hoàn tất dưới khóa đó, hoặc giữ nguyên hàng đợi.

Chương về khóa của OSTEP giải thích loại trừ tương hỗ trong vùng tới hạn. Chương về lỗi đồng thời còn cho thấy bảo vệ từng truy cập riêng có thể bỏ sót yêu cầu nguyên tử ở phạm vi rộng hơn.

Theo dõi một vòng quay của các chỉ số

Ban đầu hàng đợi rỗng: head, tail và count đều bằng không. Thêm công việc 10 vào ô không, chuyển tail sang một và tăng count lên một. Thêm công việc 20 vào ô một; tail thành hai và count thành hai.

Lấy một công việc trả về 10 ở ô không, chuyển head sang một và giảm count còn một. Thêm 30 vào ô hai. Tăng tail theo modulo ba làm nó quay về không. Cuối cùng thêm 40 vào ô không; tail thành một và count thành ba.

Thao tác	Head	Tail	Count	Thứ tự logic
Rỗng	0	0	0	Rỗng
Thêm 10, 20	0	2	2	10, 20
Lấy một	1	2	1	20
Thêm 30	1	0	2	20, 30
Thêm 40	1	1	3	20, 30, 40

Head và tail bằng nhau cả khi rỗng lẫn khi đầy. Count giải quyết sự nhập nhằng trong cách biểu diễn này. Triển khai khác có thể luôn để trống một ô hoặc giữ cờ đầy riêng, nhưng khi đó cần bất biến khác.

Mở ảnh kích thước đầy đủ ↗

Mảng vật lý cuối cùng chứa 40, 20 và 30 theo thứ tự chỉ số. Thứ tự lấy logic lại là 20, 30 và 40. Một lệnh in phục vụ gỡ lỗi theo chỉ số tăng dần có thể mô tả sai hàng đợi nếu không bắt đầu từ head và dùng count.

Chọn đúng ranh giới vùng tới hạn

Một lần thêm phải kiểm tra count nhỏ hơn sức chứa, ghi phần tử, tăng tail rồi tăng count khi vẫn giữ cùng mutex. Nếu nhả khóa ngay sau kiểm tra sức chứa, bên thêm khác có thể dùng ô trống cuối trước khi bên đầu kịp ghi.

Tương tự, lấy phần tử phải kiểm tra không rỗng, đọc phần tử, tăng head và giảm count dưới khóa. Trả kết quả thất bại khi rỗng là một hợp đồng API. Đợi đến khi có việc là hợp đồng khác; việc đợi cần cơ chế phối hợp nhả mutex để bên thêm có thể tiến hành.

Bất biến gồm 0 <= count <= capacity và các chỉ số nằm trong phạm vi hợp lệ. Nó còn gồm quan hệ thứ tự giữa những ô đang có dữ liệu và head. Count không vượt giới hạn vẫn chưa đủ nếu hai bên thêm ghi đè cùng ô hoặc tail tiến lên trước khi ô có phần tử hợp lệ.

Một cách rà soát là tìm điểm tuyến tính hóa: thời điểm trong quá trình chạy mà có thể coi thao tác đã có hiệu lực. Trong thiết kế dùng khóa này, bước chuyển được bảo vệ cho phép chọn điểm ấy vì thao tác hàng đợi khác không quan sát được các trường đang thay đổi dở. Việc chọn đúng một lệnh cụ thể ít quan trọng hơn chứng minh các bên gọi nhìn thấy một thứ tự tuần tự hợp lệ.

Không giữ khóa trong công việc có thời gian khó kiểm soát

Bên xử lý thường nên lấy công việc khi giữ mutex, nhả mutex, rồi mới chạy công việc. Gọi callback tùy ý trong vùng tới hạn làm mọi bên thêm và lấy đều phải đợi. Callback còn có thể gọi ngược vào hàng đợi rồi cố lấy lại chính mutex không đệ quy đó.

Di chuyển một đối tượng công việc phức tạp có thể ném ngoại lệ trong một số ngôn ngữ và thiết kế kiểu. Hàng đợi phải xác định việc di chuyển thất bại sẽ giữ nguyên phần tử, loại nó ra, hay kích hoạt quy tắc khôi phục khác. Công việc số nguyên làm ví dụ dễ theo dõi, nhưng không loại bỏ câu hỏi về ngoại lệ khi viết container tổng quát.

Phạm vi giữ khóa cũng cần nhất quán. Guard hoặc cơ chế dọn dẹp có cấu trúc giảm nguy cơ nhánh lỗi trả về khi vẫn giữ mutex. Nếu hàng đợi lưu tham chiếu tới công việc do nơi khác sở hữu, phải ghi rõ đối tượng ấy cần sống bao lâu sau khi được thêm.

Loại trừ tương hỗ không hứa công bằng

Mutex ngăn truy cập đồng thời vào vùng được bảo vệ. Nó không nhất thiết bảo đảm cấp khóa theo FIFO hoặc giới hạn thời gian đợi cho từng luồng. Một bên thêm có thể liên tục thua cuộc lấy khóa trong lúc những luồng khác vẫn tiến triển. Nếu ứng dụng cần công bằng hay thời hạn, hãy đánh giá yêu cầu ấy riêng.

Một mutex cũng tuần tự hóa phần cập nhật sổ sách của hàng đợi. Điều đó có thể chấp nhận được khi thời gian chạy công việc chiếm phần lớn chi phí. Thay bằng hàng đợi đồng thời phức tạp hơn chỉ hữu ích nếu hàng đợi thực sự là nút thắt và thiết kế mới giữ đúng ngữ nghĩa cần thiết, bao gồm đóng hàng đợi và thu hồi bộ nhớ.

Kiểm tra quay vòng chỉ số, chuyển rỗng sang có dữ liệu, chuyển sang đầy, xen kẽ thêm và lấy, rồi nhiều vòng hoàn chỉnh. Sau đó mới tăng tải đồng thời và kiểm tra mỗi công việc được chấp nhận xuất hiện đúng một lần. Giữ lại kiểm thử tuần tự: tính đồng thời không bào chữa được phép tăng tail vốn đã sai với một luồng.

Chạy hợp đồng tuần tự trước

Triển khai Python này đặt mỗi lần kiểm tra và cập nhật trong một phạm vi khóa. Nó dùng tham chiếu đối tượng thông thường làm công việc. Ví dụ kiểm tra vòng quay phía trên, từ chối thêm khi đầy và phân biệt kết quả rỗng với phần tử thật có giá trị None. Chạy toàn bộ như một script Python độc lập.

from threading import Lock

class Ring:
    def __init__(self, capacity):
        if type(capacity) is not int or capacity <= 0:
            raise ValueError("capacity must be a positive integer")
        self._slots = [None] * capacity
        self._head = self._tail = self._count = 0
        self._lock = Lock()

    def try_put(self, item):
        with self._lock:
            if self._count == len(self._slots):
                return False
            self._slots[self._tail] = item
            self._tail = (self._tail + 1) % len(self._slots)
            self._count += 1
            return True

    def try_get(self):
        with self._lock:
            if self._count == 0:
                return False, None
            item = self._slots[self._head]
            self._slots[self._head] = None
            self._head = (self._head + 1) % len(self._slots)
            self._count -= 1
            return True, item

    def snapshot(self):
        with self._lock:
            size = len(self._slots)
            return [self._slots[(self._head + i) % size]
                    for i in range(self._count)]

queue = Ring(3)
assert queue.try_put(10) and queue.try_put(20)
assert queue.try_get() == (True, 10)
assert queue.try_put(30) and queue.try_put(40)
assert queue.snapshot() == [20, 30, 40]
assert not queue.try_put(50)
assert [queue.try_get() for _ in range(3)] == [
    (True, 20), (True, 30), (True, 40)
]
assert queue.try_get() == (False, None)
assert queue.try_put(None)
assert queue.try_get() == (True, None)

Tên try_put có nghĩa hàng đợi đầy sẽ trả về ngay sau khi lấy được mutex; nó không hứa rằng lấy mutex không phải đợi. Luồng khác vẫn có thể đang giữ khóa. Tương tự, try_get trả cờ thành công riêng để phân biệt rỗng với None thực sự đã được đưa vào. Snapshot tạo danh sách bên ngoài mới trong khi giữ khóa, nhưng không nhân bản những đối tượng mà danh sách tham chiếu tới. Bên gọi sửa một đối tượng công việc dùng chung vẫn cần quy tắc sở hữu.

Mở ảnh kích thước đầy đủ ↗

Hình thứ hai tách hai cách triển khai API. Ở bản sai, A kiểm tra count bằng hai, nhả khóa, rồi dùng câu trả lời cũ sau khi B tăng count lên ba. Ở bản được bảo vệ, bên nào lấy khóa sau sẽ thấy ba và trả false mà không đụng tới ô nào. Kết quả thao tác phụ thuộc trạng thái tại quyết định được bảo vệ, không phải một quan sát trước đó nằm ngoài bước chuyển.

Để luyện tập, so sánh bộ đệm vòng với danh sách tham chiếu đơn giản trên một chuỗi lệnh thêm và lấy. Chỉ chấp nhận thêm khi độ dài danh sách còn dưới sức chứa; nếu không, yêu cầu false và snapshot không đổi. Khi lấy thành công, kiểm tra đúng đối tượng đầu danh sách theo danh tính, không chỉ bằng giá trị. Thử sức chứa một: head và tail bằng nhau sau mọi thao tác, nên thiết kế đoán rỗng từ hai chỉ số ấy sẽ sai ngay.

Sau khi hợp đồng tuần tự đạt yêu cầu, chạy nhiều bên thêm với mã công việc duy nhất và kiểm tra các lần lấy hoàn tất chứa đúng một bản của mỗi công việc đã được chấp nhận. Một lần chạy hữu hạn có thể lộ phần tử mất hoặc trùng, nhưng không chứng minh an toàn cho mọi lịch luồng. Lập luận rà soát vẫn dựa vào cùng quy tắc mutex, bất biến tại ranh giới thao tác và giao thức đóng giữ hàng đợi tồn tại cho đến khi mọi bên gọi kết thúc.