Block-STM trong xử lí song song

Block-STM là một thuật toán song song sử dụng optimistic concurrency control để xử lý giao dịch đồng thời trong hệ thống bộ nhớ dùng chia sẻ (shared-memory systems), phổ biến trong hệ thống đa luồng (multi-threaded systems). Thuật toán này xuất hiện trong lĩnh vực Transactional Memory — đặc biệt là Software Transactional Memory (STM).

🧠 Tóm tắt ý tưởng của Block-STM

• Optimistic: các giao dịch (transactions) chạy đồng thời, không khóa tài nguyên từ đầu.
• Validation & Commit: sau khi thực hiện, mỗi giao dịch sẽ được kiểm tra (validate) xem có bị xung đột không, rồi mới cam kết (commit).
• Block-STM chia các giao dịch theo epoch (khoảng thời gian ngắn), và ưu tiên commit những giao dịch không có xung đột.

📐 Biểu diễn Toán học

Giả sử ta có:

• Một tập các transaction:

  $$T = \{T_1, T_2, ..., T_n\}$$

• Mỗi transaction ( T_i ) thực hiện:

  • Tập đọc: ( R_i )
  • Tập ghi: ( W_i )

🎯 Điều kiện không xung đột giữa 2 transaction ( T_i ) và ( T_j ):

$$W_i \cap W_j = \emptyset \\ W_i \cap R_j = \emptyset \\ R_i \cap W_j = \emptyset$$

Nếu tất cả các điều kiện này thỏa mãn → ( T_i ) và ( T_j ) có thể chạy song song mà không xung đột.

🧮 Ví dụ cách tính với 3 transaction

Giả sử có:

• Biến chung: x, y, z

• Giao dịch:

  T1: Read(x), Write(y)
  T2: Read(y), Write(z)
  T3: Read(z), Write(x)
  

➕ Tập đọc/ghi:

• ( R_1 = {x}, W_1 = {y} )
• ( R_2 = {y}, W_2 = {z} )
• ( R_3 = {z}, W_3 = {x} )

➕ Kiểm tra xung đột:

• ( T1 ) vs ( T2 ):
  ( W_1 \cap R_2 = {y} \Rightarrow ) có xung đột
  → Không thể song song

• ( T2 ) vs ( T3 ):
  ( W_2 \cap R_3 = {z} \Rightarrow ) có xung đột
  → Không thể song song

• ( T1 ) vs ( T3 ):
  ( R_1 \cap W_3 = {x} \Rightarrow ) có xung đột
  → Không thể song song

✅ Kết luận:

Cả 3 transaction có liên hệ tuần hoàn (circular conflict). Block-STM sẽ phải chia thành nhiều epoch (hoặc batch) để tuần tự commit, tránh xung đột.

📊 Biểu đồ Epoch Execution

Epoch 1: T1 Epoch 2: T2 Epoch 3: T3

🚀 So sánh với khóa (locking)

🧠 Ứng dụng thực tế

Block-STM thường dùng trong:

• Runtime của ngôn ngữ có hỗ trợ STM (Haskell, Clojure…)
• Multi-threaded simulations
• Game engines (xử lý vật lý, AI hành vi song song)
• Blockchain (xử lý smart contract song song như trong Aptos, Sui...)