Chọn thăm dò hay ngắt từ ngân sách sự kiện

Bạn đang nối luồng sự kiện của thiết bị với một tác vụ phần mềm. Thăm dò mỗi mười nhịp nghe có vẻ ít tốn công, còn ngắt có vẻ phản hồi ngay. Cả hai mô tả đều chưa cho biết khi nào công việc hoàn tất. Trình xử lý ngắt có thể phải chờ các lượt trước; một lần thăm dò có thể gom nhiều sự kiện nhưng chỉ trả chi phí kiểm tra một lần. Trước khi lựa chọn, bạn cần biết cách sự kiện đến, ngân sách xử lý và định nghĩa của hoàn tất.

Bài này dùng các nhịp thời gian nguyên và chi phí CPU giả định. Đây không phải phép đo vi điều khiển, độ trễ ngắt Linux hay thông lượng mạng. Mô hình so sánh lịch thăm dò cố định với hàng đợi ngắt lý tưởng, rồi dùng một cơ chế Linux có thật để giải thích vì sao hệ thống thực tế thường kết hợp thông báo và thăm dò.

Xác định công việc trước khi chọn cách thông báo

Giả sử sự kiện đến trong khoảng đóng [0, H]. Mỗi sự kiện cần Cs nhịp CPU để xử lý. Tác vụ thăm dò kiểm tra tại P, 2P, ... H, trả Cp nhịp mỗi lần kể cả khi không có sự kiện. Không có lần kiểm tra ban đầu tại thời điểm 0. Mỗi lần kiểm tra lấy toàn bộ sự kiện đã đến nhưng chưa được gom, rồi xử lý lô đó theo thứ tự đến. Sự kiện có thời điểm đúng bằng nhịp lấy mẫu được tính vào lần kiểm tra ấy. Sự kiện đến trong lúc CPU đang kiểm tra hoặc xử lý lô sẽ chờ lần lấy mẫu tiếp theo.

Phương án ngắt trả Ci nhịp chi phí phụ cho từng sự kiện, rồi thực hiện cùng lượng xử lý Cs. Thông báo đến tức thời, không bị mất và được xếp hàng theo thứ tự đến. Một tác vụ duy nhất xử lý không bị ngắt ngang. Đây là các giả định mạnh có chủ đích: mô hình không có che ngắt, gộp thông báo, mất sự kiện, hàng đợi hữu hạn, ảnh hưởng của ưu tiên hay công việc CPU khác.

Phương án thăm dò còn có một giới hạn đầu vào: mọi lô phải thỏa Cp + batch_size * Cs <= P. Điều này áp dụng cả cho lô rỗng và lô cuối. Mỗi lượt vì vậy kết thúc trước hoặc đúng lúc lấy mẫu kế tiếp theo lịch. Chương trình từ chối lô quá tải; nó không âm thầm dời thời điểm lấy mẫu hay tự nhận là mô phỏng hàng đợi bão hòa. Nếu hai thời điểm trùng nhau, lô trước hoàn tất rồi mới lấy mẫu tiếp. Thiết kế thực tế có thể xếp hàng, loại bỏ, điều tiết hoặc đổi chính sách thăm dò.

Khoảng quan sát dùng để chọn các sự kiện đến, không phải hạn chót tuyệt đối cho toàn bộ xử lý. Lần thăm dò cuối tại H có thể kết thúc sau H; hàng đợi ngắt cũng được xử lý hết sau sự kiện cuối đã chọn. Hãy tính cả phần công việc ở cuối này. Chỉ lấy tổng công việc hoàn chỉnh chia cho H chưa đủ để tính mức sử dụng CPU bên trong khoảng quan sát hữu hạn.

Chạy hai lịch có cùng số sự kiện

Dùng H = 40, P = 10, Cp = 1, Ci = 3 và Cs = 2. Bốn sự kiện cách nhau đến tại các nhịp 1, 11, 21 và 31. Lần thăm dò đầu lấy mẫu tại 10, mất một nhịp kiểm tra và hai nhịp xử lý, nên hoàn tất sự kiện đầu tại 13. Tương tự, các lần hoàn tất tiếp theo là 23, 33 và 43. Mỗi sự kiện mất mười hai nhịp từ khi đến đến khi hoàn tất.

Tác vụ xử lý ngắt đang rảnh bắt đầu sự kiện đầu tại nhịp 1 và hoàn tất tại 6. Năm nhịp công việc của nó kết thúc trước sự kiện cách quãng kế tiếp. Cả bốn độ trễ hoàn tất đều bằng năm nhịp. Chỉ số độ trễ này tốt hơn, nhưng lượng công việc CPU lớn hơn: thăm dò dùng bốn nhịp kiểm tra cộng tám nhịp xử lý, còn ngắt dùng mười hai nhịp chi phí phụ cộng tám nhịp xử lý.

Bây giờ cho cả bốn sự kiện cùng đến tại nhịp 1. Số sự kiện và tổng chi phí CPU không đổi. Thăm dò hoàn tất chúng tại 13, 15, 17 và 19; hàng đợi ngắt hoàn tất tại 6, 11, 16 và 21. Ngắt hoàn tất sự kiện đầu sớm hơn, nhưng thăm dò hoàn tất sự kiện cuối sớm hơn. Nguyên nhân là cả lô chỉ trả một lần kiểm tra, trong khi từng sự kiện ngắt đều trả chi phí phụ. Kết quả không chứng minh thăm dò luôn có độ trễ tốt hơn. Nó cho thấy chỉ biết tốc độ sự kiện trung bình thì không thể dựng lại thời điểm hoàn tất của một đợt sự kiện dồn đến.

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

Chương trình Python dưới đây lưu toàn bộ dãy thời điểm đến hữu hạn một lần. Nó kiểm tra từng thời điểm ban đầu có đúng kiểu số nguyên tích hợp hay không, giữ nguyên các sự kiện đồng thời và từ chối dãy có thời điểm sau nhỏ hơn thời điểm trước. Mỗi bản ghi thăm dò trả về gồm nhịp lấy mẫu, kích thước lô và thời điểm kết thúc toàn bộ công việc của lượt kiểm tra. Tất cả kết quả đều là mô phỏng.

def compare(arrivals, horizon=40, period=10, poll_cost=1,
            irq_cost=3, service=2):
    values = (horizon, period, poll_cost, irq_cost, service)
    if any(type(x) is not int for x in values):
        raise ValueError('all parameters must be built-in integers')
    if horizon <= 0 or period <= 0 or horizon % period:
        raise ValueError('horizon must be a positive multiple of period')
    if poll_cost < 0 or irq_cost < 0 or service <= 0:
        raise ValueError('invalid CPU costs')
    times = tuple(arrivals)
    if any(type(t) is not int or not 0 <= t <= horizon for t in times):
        raise ValueError('arrival outside the closed observation interval')
    if any(a > b for a, b in zip(times, times[1:])):
        raise ValueError('arrivals must be nondecreasing')
    groups = {tick: [] for tick in range(period, horizon+1, period)}
    for index, arrival in enumerate(times):
        tick = max(period, ((arrival+period-1)//period)*period)
        groups[tick].append(index)
    if any(poll_cost+len(group)*service > period
           for group in groups.values()):
        raise ValueError('poll batch does not fit the declared period')
    polling, polls = [None]*len(times), []
    for tick, group in groups.items():
        finish = tick + poll_cost
        for index in group:
            finish += service
            polling[index] = finish
        polls.append((tick, len(group), finish))
    interrupt, finish = [], 0
    for arrival in times:
        finish = max(arrival, finish) + irq_cost + service
        interrupt.append(finish)
    return dict(arrivals=times, polling=tuple(polling),
                interrupt=tuple(interrupt), polls=tuple(polls),
                polling_work=len(groups)*poll_cost+len(times)*service,
                interrupt_work=len(times)*(irq_cost+service))

spaced = (1, 11, 21, 31)
burst = (1, 1, 1, 1)
for name, times in (('spaced', spaced), ('burst', burst)):
    result = compare(times)
    print(name, result['polling'], result['interrupt'],
          result['polling_work'], result['interrupt_work'])
    print('completion delay:',
          tuple(end-start for start, end in zip(times, result['polling'])),
          tuple(end-start for start, end in zip(times, result['interrupt'])))
assert compare(())['polling_work'] == 4
assert compare(())['interrupt_work'] == 0
assert compare((1,))['polling_work'] == 6
assert compare((1,))['interrupt_work'] == 5
assert compare(spaced, period=5)['polling'] == (8, 18, 28, 38)
assert compare(spaced, period=5)['polling_work'] == 16

Kết quả in ra là:

spaced (13, 23, 33, 43) (6, 16, 26, 36) 12 20
completion delay: (12, 12, 12, 12) (5, 5, 5, 5)
burst (13, 15, 17, 19) (6, 11, 16, 21) 12 20
completion delay: (12, 14, 16, 18) (5, 10, 15, 20)

Với hàng đợi ngắt, mỗi thời điểm hoàn tất là max(arrival, previous_finish) + Ci + Cs. Phép lấy giá trị lớn hơn là cần thiết. Nếu chỉ dùng arrival thay cho max(arrival, previous_finish), nhiều sự kiện đồng thời có thể chiếm cùng một CPU trong cùng khoảng thời gian. Với thăm dò, nhịp lấy mẫu sau khi làm tròn phải ít nhất bằng P; quy tắc này xử lý sự kiện tại thời điểm 0 mà không tự thêm một lần kiểm tra ngoài hợp đồng.

Tìm ngưỡng đổi chiều về công việc CPU

Gọi N là số sự kiện và K = H / P là số lần kiểm tra. Trong mô hình này, công việc thăm dò bằng K * Cp + N * Cs; công việc ngắt bằng N * (Ci + Cs). Khi lấy hiệu, chi phí xử lý chung triệt tiêu. Thăm dò dùng ít công việc CPU hơn khi K * Cp < N * Ci.

Với bốn lần kiểm tra, mỗi lần một nhịp và mỗi ngắt ba nhịp chi phí phụ, ngưỡng đổi chiều nằm giữa một và hai sự kiện. Khi không có sự kiện, thăm dò dùng bốn nhịp còn tác vụ ngắt lý tưởng không dùng nhịp nào. Với một sự kiện, tổng lần lượt là sáu và năm. Với hai sự kiện, tổng là tám và mười. Các lựa chọn tham số khác có thể tạo kết quả bằng nhau; công việc bằng nhau không có nghĩa lịch hoàn tất cũng bằng nhau.

Điều kiện chấp nhận lô vẫn quan trọng. Số sự kiện lớn không tự làm cho lịch thăm dò hợp lệ. Năm sự kiện đồng thời trong ví dụ cần mười một nhịp ở một lần kiểm tra, vượt chu kỳ mười nhịp. Hàm từ chối trường hợp ấy. Không thể chỉ dùng công thức chi phí để khẳng định một lịch bị từ chối đáp ứng hạn phản hồi.

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

Rút ngắn chu kỳ và tính đủ chi phí

Với bốn sự kiện cách quãng, đổi P từ mười thành năm cho các thời điểm hoàn tất 8, 18, 28 và 38. Độ trễ hoàn tất giảm từ mười hai xuống bảy nhịp, còn công việc kiểm tra tăng gấp đôi từ bốn lên tám. Tổng công việc thăm dò tăng từ mười hai lên mười sáu nhịp. Kết quả ngắt không đổi vì mô hình của nó không dùng P.

Phép so sánh cụ thể này vẫn hợp lệ vì mỗi lần kiểm tra có sự kiện dùng ba nhịp. Đổi P thành hai thì không hợp lệ: chỉ một sự kiện cũng cần ba nhịp kiểm tra và xử lý. Mô hình từ chối đầu vào ấy. Vòng lặp quay liên tục hoặc tác vụ lên lịch lần kiểm tra kế sau khi hoàn tất cần hợp đồng khác; giảm chu kỳ này xuống dưới chi phí của lô không mô tả được hai cách đó.

Cũng cần tách độ trễ phát hiện khỏi độ trễ hoàn tất. Sự kiện tại nhịp 10 được lấy mẫu ngay ở lần thăm dò ấy, nhưng vẫn cần kiểm tra và xử lý. Trong lô nhiều sự kiện, các sự kiện sau còn chờ xử lý trước đó. Nếu yêu cầu là xác nhận thiết bị trong một hạn nhất định, hoàn tất tác vụ ứng dụng có thể là mốc không phù hợp. Hãy xác định hành động quan sát được nào được tính trước khi thu thập phép đo.

Vì sao đường xử lý ngắt thực tế lại dẫn tới thăm dò

Tài liệu IRQ chung của Linux tách chi tiết bộ điều khiển ngắt, xử lý luồng ngắt và hành động của trình điều khiển thiết bị. Những kiểu xử lý luồng khác nhau đã cho thấy không nên hiểu mỗi ngắt là một thao tác thiết bị đã hoàn tất. Mô hình trên không biểu diễn thao tác xác nhận hay che ngắt của bộ điều khiển.

Mạng Linux cung cấp một thiết kế kết hợp cụ thể. Tài liệu NAPI mô tả thông báo ngắt đưa phương thức thăm dò vào lịch chạy; phương thức này xử lý công việc sẵn có theo ngân sách nhận. Các ngắt liên quan cần tiếp tục bị che trong lúc thăm dò hoạt động, rồi được mở lại khi hoàn tất thăm dò. Tài liệu cũng mô tả thăm dò chủ động có thể gọi phương thức ấy mà không có ngắt trước đó. Ngân sách nhận của NAPI không phải giới hạn chung cho mọi phần công việc hoàn tất truyền; ngân sách nhận bằng 0 còn có các ràng buộc riêng. Những chi tiết này quan trọng khi chuyển một lô trong mô hình khái niệm thành trình điều khiển thực tế.

Vì vậy, một ngắt cho mỗi gói tin là giả định cần kiểm tra, không phải sự thật để chép vào ước lượng. Gộp thông báo có thể giảm chi phí ngắt; chờ lâu hơn có thể tăng độ trễ; hết ngân sách có thể đòi hỏi thăm dò thêm. Hai lịch lý tưởng trong bài hữu ích làm mốc so sánh, nhưng không lịch nào triển khai NAPI hay dự đoán độ trễ ở phần đuôi phân bố đã đo của trình điều khiển.

Trong bài tập tiếp theo, giữ nguyên mọi chi phí đã công bố và so sánh các thời điểm đến 9, 10 và 11, trước tiên riêng lẻ rồi cùng nhau. Giải thích lần thăm dò nào lấy từng sự kiện và vì sao cùng thời điểm phát hiện chưa chắc cùng thời điểm hoàn tất. Sau đó đặt năm sự kiện tại nhịp 1 và giải thích việc từ chối. Một thí nghiệm tiếp theo hữu ích sẽ ghi riêng thời điểm đến, phát hiện và hoàn tất, đếm lần kiểm tra rỗng và thông báo ngắt, đồng thời tính cả kết quả khi quá tải. Kết luận nên áp dụng cho hàng đợi, chính sách lập lịch và tải đã thử, thay vì chỉ cho hai từ “thăm dò” và “ngắt”.