Đồng Thời và Song Song¶

Đồng thời (concurrency) và song song (parallelism) là cách các chương trình thực hiện nhiều việc cùng lúc. File này bao gồm sự phân biệt giữa đồng thời và song song, các nguyên hữu đồng bộ hóa, các bài toán kinh điển về đồng thời, deadlock, cấu trúc dữ liệu không dùng khóa (lock-free), các mô hình lập trình song song, lập trình bất đồng bộ (async), và các định luật mở rộng (scaling laws) — những khái niệm nền tảng cho các máy chủ đa luồng, huấn luyện phân tán và mọi ứng dụng hiện đại.

Một lõi CPU đơn thực thi một chỉ thị tại một thời điểm. Nhưng các hệ thống hiện đại có 8, 64, thậm chí hàng ngàn lõi (GPU). Và ngay cả trên một lõi đơn, ta vẫn muốn xử lý nhiều tác vụ: tải một file trong khi render giao diện và xử lý đầu vào của người dùng. Đồng thời và song song là hai chiến lược để quản lý nhiều hoạt động.

Đồng Thời so với Song Song¶

Đồng thời xen kẽ các tác vụ trên một lõi; song song chạy các tác vụ cùng lúc trên nhiều lõi

Đồng thời là về việc quản lý nhiều tác vụ. Các tác vụ tiến triển bằng cách xen kẽ: tác vụ A chạy một chút, rồi tác vụ B, rồi quay lại A. Trên một lõi đơn, đồng thời tạo ra ảo giác về việc thực thi đồng thời. Các tác vụ không thực sự đồng thời; chúng thay phiên nhau.
Song song là về việc thực thi nhiều tác vụ cùng một lúc. Với \(n\) lõi, \(n\) tác vụ có thể thực sự chạy cùng thời điểm. Song song đòi hỏi nhiều đơn vị thực thi phần cứng.
Một phép so sánh: đồng thời giống như một đầu bếp luân phiên giữa thái rau và khuấy nồi. Song song là hai đầu bếp, mỗi người làm một việc cùng lúc. Một hệ thống có thể đồng thời nhưng không song song (một lõi, các tác vụ xen kẽ), song song nhưng không đồng thời (nhiều lõi chạy các chương trình độc lập không tương tác), hoặc cả hai (nhiều lõi chạy các tác vụ xen kẽ có tương tác).
Trong ML, đồng thời xuất hiện trong việc tải dữ liệu (đắp ứng tiền xử lý dữ liệu với tính toán GPU), trong khi song song xuất hiện trong huấn luyện phân tán (nhiều GPU tính gradient cùng lúc, chương 6).

Các Nguyên Hủu Đồng Bộ Hóa¶

Khi nhiều luồng chia sẻ dữ liệu, đồng bộ hóa ngăn chặn điều kiện đua (race condition). Điều kiện đua xảy ra khi kết quả phụ thuộc vào thứ tự không thể đoán trước của việc thực thi luồng.
Xét hai luồng cùng tăng một bộ đếm dùng chung: counter += 1. Thực tế đây là ba thao tác: (1) đọc counter, (2) cộng 1, (3) ghi counter. Nếu cả hai luồng cùng đọc một giá trị (ví dụ 5), cả hai cộng 1, và cả hai ghi 6, bộ đếm kết thúc ở 6 thay vì 7 đúng. Một lần tăng bj mất.
Một mutex (khóa loại trừ lẫn nhau) đảm bảo chỉ một luồng truy cập một vùng tới hạn (critical section) tại một thời điểm. Một luồng chiếm khóa trước khi vào vùng tới hạn và giải phóng nó sau khi xong. Bất kỳ luồng nào khác cố gắng chiếm một khóa đang bị giữ sẽ bị chặn cho đến khi nó được giải phóng.

lock.acquire()
counter += 1      # chỉ một luồng tại đây tại một thời điểm
lock.release()

Mutex đúng đắn nhưng đưa vào sự tranh chấp (contention): nếu nhiều luồng tranh nhau cùng một khóa, chúng mất thời gian chờ đợi thay vì tính toán. Điều này giới hạn khả năng mở rộng. Trường hợp cực đoan, khi mọi luồng đều muốn cùng một khóa, toàn bộ chương trình bị tuần tự hóa.
Một semaphore (bộ đếm tín hiệu) tổng quát hóa một mutex. Một semaphore đếm duy trì một bộ đếm: wait() giảm bộ đếm (chặn nếu nó sẽ xuống âm), và signal() tăng nó lên. Một semaphore khởi tạo bằng 1 hoạt động như một mutex. Một semaphore khởi tạo bằng \(n\) cho phép tối đa \(n\) luồng vào vùng tới hạn cùng lúc (hữu ích cho các bể tài nguyên như kết nối cơ sở dữ liệu).
Một biến điều kiện (condition variable) cho phép một luồng chờ cho đến khi một điều kiện cụ thể được thỏa mãn. Luồng giải phóng một khóa, chờ trên biến điều kiện, và được đánh thức khi một luồng khác phát tín hiệu cho điều kiện đó. Điều này tránh việc busy-waiting (kiểm tra lặp đi lặp lại một điều kiện trong vòng lặp, lãng phí CPU).
Một monitor (bộ giám sát) gói một mutex cùng với các biến điều kiện và dữ liệu dùng chung thành một abstraction duy nhất. Từ khóa synchronized của Java và threading.Condition của Python hiện thực ngữ nghĩa giống monitor.
Khóa đọc-ghi (read-write locks) phân biệt giữa người đọc (có thể chia sẻ truy cập, vì việc đọc không sửa đổi dữ liệu) và người viết (cần quyền truy cập độc quyền). Nhiều người đọc có thể giữ khóa cùng lúc, nhưng một người viết chặn tất cả người đọc và người viết khác. Điều này tối ưu khi các lượt đọc vượt xa các lượt viết (ví dụ, một mô hình được cache phục vụ dự đoán).

Các Bài Toán Đồng Thời Kinh Điển¶

Nhà sản xuất - người tiêu thụ (Producer-Consumer) (bộ đệm giới hạn): các nhà sản xuất sinh ra các mục và đặt chúng vào một bộ đệm có kích thước cố định; người tiêu thụ lấy các mục ra. Các thách thức: nhà sản xuất phải chờ khi bộ đệm đầy, người tiêu thụ phải chờ khi bộ đệm rỗng, và cả hai phải tránh làm hỏng bộ đệm.
Giải pháp dùng hai semaphore (một đếm các ô trống, một đếm các ô đã đầy) cộng với một mutex cho chính bộ đệm. Đây là mẫu (pattern) đằng sau hầu hết các hàng đợi thông điệp, hệ thống ghi log và pipeline dữ liệu.
Người đọc - người viết (Readers-Writers): nhiều người đọc có thể đọc cùng lúc, nhưng người viết cần quyền truy cập độc quyền. Thách thức là sự công bằng: nếu người đọc cứ đến liên tục, người viết có thể bj đói (không bao giờ được truy cập). Các giải pháp ưu tiên hoặc người đọc, hoặc người viết, hoặc xen kẽ một cách công bằng.
Các nhà triết học dùng bữa (Dining Philosophers): năm nhà triết học ngồi quanh một cái bàn với năm cái dĩa ở giữa. Mỗi người cần hai cái dĩa để ăn. Nếu cả năm cùng nhặt dĩa bên trái lên đồng thời, không ai có thể nhặt dĩa bên phải và tất cả đều đói (deadlock). Các giải pháp bao gồm: nhặt cả hai dĩa một cách nguyên tử, tạo bất đối xứng (một nhà triết học nhặt dĩa bên phải trước), hoặc dùng một người phục vụ (semaphore giới hạn số người ăn tối đa là 4).

Deadlock¶

Deadlock (khóa cứng) xảy ra khi một tập hợp các luồng đều đang chờ một tài nguyên do một luồng khác trong tập hợp nắm giữ, tạo thành một chu trình phụ thuộc. Không ai có thể tiếp tục.

Deadlock: Luồng A giữ Lock 1 và muốn Lock 2, Luồng B giữ Lock 2 và muốn Lock 1 — chờ vòng tròn

Bốn điều kiện cần thiết cho deadlock (tất cả phải cùng xảy ra cùng lúc):
1. Loại trừ lẫn nhau (Mutual exclusion): tài nguyên chỉ có thể do một luồng nắm giữ.
2. Nắm giữ và chờ (Hold and wait): một luồng nắm giữ một tài nguyên trong khi chờ một tài nguyên khác.
3. Không tiền chiếm (No preemption): tài nguyên không thể bj cưỡng đoạt từ một luồng.
4. Chờ vòng tròn (Circular wait): tồn tại một chu trình trong đồ thị chờ (wait-for graph).
Phòng tránh deadlock (Deadlock prevention) phá vỡ một trong bốn điều kiện:
- Loại bỏ chờ vòng tròn: áp đặt một thứ tự toàn phần lên các tài nguyên. Mọi luồng đều chiếm các tài nguyên theo cùng một thứ tự. Nếu mọi luồng luôn chiếm khóa A trước khóa B, một chu trình là không thể.
- Loại bỏ nắm giữ và chờ: yêu cầu các luồng yêu cầu tất cả tài nguyên cùng một lúc (nguyên tử).
Tránh deadlock (Deadlock avoidance) quyết định động liệu việc cấp phát một yêu cầu tài nguyên có thể dẫn đến deadlock hay không. Thuật toán của người cho vay (Banker's algorithm) duy trì nhu cầu tối đa có thể có của mỗi luồng và chỉ cấp phát những yêu cầu để lại hệ thống ở trạng thái "an toàn" (một trạng thái mà mọi luồng đều có thể hoàn thành cuối cùng). Thuật toán có độ phức tạp \(O(n^2 m)\) cho mỗi yêu cầu (\(n\) luồng, \(m\) loại tài nguyên), quá đắt cho hầu hết các hệ thống thực tế.
Phát hiện deadlock (Deadlock detection) để deadlock xảy ra, sau đó phát hiện chúng (bằng cách tìm các chu trình trong đồ thị chờ) và phục hồi (bằng cách giết một luồng hoặc rollback một giao dịch).
Trong thực tế, hầu hết các hệ thống dùng phòng tránh (thứ tự tài nguyên) cho các trường hợp phổ biến và phát hiện cho các trường hợp hiếm gặp. Hệ thống cơ sở dữ liệu là ví dụ kinh điển: chúng phát hiện deadlock giữa các giao dịch và hủy bỏ một giao dịch để phá vỡ chu trình.

Cấu Trúc Dữ Liệu Không Dùng Khóa và Không Chờ¶

Khóa đưa vào sự tranh chấp, sự đảo ngược độ ưu tiên (priority inversion), và nguy cơ deadlock. Các cấu trúc dữ liệu không dùng khóa (lock-free) hoàn toàn tránh dùng khóa, sử dụng các thao tác nguyên tử (atomic operations) do phần cứng cung cấp.
Thao tác nguyên tử then chốt là Compare-And-Swap (CAS): nguyên tử kiểm tra xem một vị trí bộ nhớ có giá trị kỳ vọng hay không, và nếu có, thay thế nó bằng một giá trị mới. Trong mã giả:

CAS(address, expected, new_value):
    if *address == expected:
        *address = new_value
        return true
    else:
        return false

CAS được hiện thực như một lệnh phần cứng đơn, vì vậy nó nguyên tử ngay cả khi không dùng khóa. Các thuật toán lock-free dùng CAS trong một vòng lặp thử lại: đọc giá trị hiện tại, tính giá trị mới, cố gắng CAS. Nếu một luồng khác đã sửa đổi giá trị trong lúc đó, CAS thất bại và luồng thử lại.
Lock-free: ít nhất một luồng tiến triển trong một số hữu hạn các bước (không thể có deadlock, nhưng các luồng riêng lẻ có thể thử lại vô hạn dưới sự tranh chấp).
Wait-free: mọi luồng đều tiến triển trong một số bước bị giới hạn (đảm bảo mạnh nhất, nhưng khó đạt được nhất).
Các ngăn xếp (stack), hàng đợi (queue) và bảng băm (hash map) lock-free được dùng rộng rãi trong các hệ thống hiệu năng cao. ConcurrentHashMap của Java và các thao tác nguyên tử của Go được xây dựng dựa trên CAS.

Các Mô Hình Lập Trình Song Song¶

Song song bộ nhớ dùng chung (Shared memory): tất cả các luồng truy cập cùng một không gian bộ nhớ. Việc đồng bộ hóa là trách nhiệm của lập trình viên. OpenMP cung cấp các chỉ thị tiền xử lý (compiler directives) để song song hóa các vòng lặp:

#pragma omp parallel for
for (int i = 0; i < n; i++) {
    result[i] = compute(data[i]);
}

Trình biên dịch chia các lần lặp vòng lặp cho các lõi có sẵn. OpenMP hiệu quả cho các khối lượng công việc dữ liệu-song-song (cùng một phép toán trên nhiều điểm dữ liệu) và được dùng rộng rãi trong tính toán khoa học.
Song song truyền thông điệp (Message passing): mỗi tiến trình có bộ nhớ riêng của nó. Giao tiếp xảy ra bằng cách gửi và nhận các thông điệp. MPI (Message Passing Interface) là tiêu chuẩn cho tính toán phân tán trên các nút (nodes):

MPI_Send(data, count, MPI_FLOAT, dest, tag, MPI_COMM_WORLD);
MPI_Recv(data, count, MPI_FLOAT, src, tag, MPI_COMM_WORLD, &status);

MPI mở rộng đến hàng ngàn nút vì không có trạng thái dùng chung để đồng bộ hóa. Học sâu phân tán (chương 6) dùng các thao tác tập thể (collective operations) như MPI_AllReduce (ring all-reduce) để đồng bộ hóa gradient giữa các GPU.
Song song GPU theo mô hình SIMT (Single Instruction, Multiple Threads — Một lệnh, nhiều luồng): hàng ngàn luồng thực thi cùng một chỉ thị trên các dữ liệu khác nhau. Điều này hoàn hảo cho các phép toán ma trận (chương 2), nơi cùng một phép nhân-cộng được áp dụng cho mọi phần tử. Chúng ta sẽ tìm hiểu lập trình GPU chi tiết hơn ở một chương sau.

Lập Trình Bất Đồng Bộ và Hướng Sự Kiện¶

Không phải mọi tính đồng thời đều cần luồng. Lập trình bất đồng bộ (asynchronous) xử lý nhiều tác vụ bound-by-I/O với một luồng đơn dùng một vòng lặp sự kiện (event loop).
Vòng lặp sự kiện duy trì một hàng đợi các tác vụ. Khi một tác vụ cần chờ I/O (phản hồi mạng, đọc file), nó đăng ký một callback và nhường quyền điều khiển. Vòng lặp sự kiện nhặt tác vụ sẵn sàng tiếp theo. Khi I/O hoàn tất, callback được đưa vào hàng đợi và cuối cùng được thực thi. Không có luồng nào bj chặn trong lúc chờ.
Coroutine (luồng đồng thời nhẹ) là các hàm có thể tạm dừng và tiếp tục. Cú pháp async/await (Python, JavaScript, Rust) làm cho coroutine trông giống như mã tuần tự bình thường:

async def fetch_data(url):
    response = await http_get(url)  # tạm dừng ở đây, event loop chạy các tác vụ khác
    return process(response)         # tiếp tục khi phản hồi đến

Từ khóa await tạm dừng coroutine và trả quyền điều khiển về cho vòng lặp sự kiện. Khi thao tác được await hoàn tất, coroutine tiếp tục từ chỗ nó đã dừng lại. Đây là đa nhiệm hợp tác (cooperative multitasking): các coroutine tự nguyện nhường quyền, không giống như đa nhiệm tiền chiếm (preemptive multitasking) nơi hệ điều hành buộc phải chuyển đổi luồng.
Async là lý tưởng cho các khối lượng công việc bound-by-I/O với nhiều kết nối đồng thời (máy chủ web xử lý hàng ngàn client). Nó không phù hợp cho công việc bound-by-CPU (vòng lặp sự kiện đơn luồng không thể tận dụng nhiều lõi). Đối với công việc bound-by-CPU, hãy dùng luồng hoặc tiến trình.
Global Interpreter Lock (GIL) của Python ngăn cản sự song song thực sự với luồng: chỉ một luồng có thể thực thi bytecode Python tại một thời điểm. Đây là lý do Python dùng multiprocessing (các tiến trình riêng biệt, mỗi cái có trình thông dịch riêng) cho song song CPU, và async cho đồng thời I/O. GIL đang được loại bỏ trong Python 3.13+ (Python không có GIL — free-threaded Python), điều này sẽ cho phép song song đa luồng thực sự.

Các Định Luật Mở Rộng¶

Định luật Amdahl mô tả tốc độ tăng (speedup) lý thuyết từ việc song song hóa một chương trình. Nếu một phân đoạn \(p\) của chương trình có thể song song hóa và phần còn lại \(1 - p\) là tuần tự (serial):

\[\text{Speedup}(n) = \frac{1}{(1-p) + \frac{p}{n}}\]

Định luật Amdahl: phân đoạn tuần tự giới hạn tốc độ tăng tối đa — 10% tuần tự nghĩa là tối đa 10x, bất kể bao nhiêu lõi

với \(n\) là số bộ xử lý. Khi \(n \to \infty\), tốc độ tăng tối đa tiến tới \(\frac{1}{1-p}\). Nếu 95% chương trình là song song, tốc độ tăng tối đa là \(\frac{1}{0.05} = 20\times\), bất kể bạn thêm bao nhiêu lõi. Phần tuần tự là nút thắt cổ chai.
Điều này có những hệ quả sâu sắc cho ML: nếu việc tải dữ liệu chiếm 10% thời gian huấn luyện và là tuần tự, việc thêm nhiều GPU nhiều nhất chỉ có thể tăng tốc huấn luyện lên 10x. Nút thắt cổ chai 10% tuần tự giới hạn tất cả (đây là lý do pipeline dữ liệu hiệu quả và việc đắp ứng tính toán với I/O lại quan trọng, chương 6).
Định luật Gustafson đưa ra một góc nhìn lạc quan hơn. Thay vì cố định kích thước bài toán và thêm bộ xử lý, nó cố định tổng thời gian và hỏi có thể làm được bao nhiêu công việc hơn. Nếu phần song song mở rộng theo kích thước bài toán:

\[\text{Speedup}(n) = 1 - p + p \cdot n\]

Điều này là tuyến tính theo \(n\). Lập luận: với nhiều bộ xử lý hơn, chúng ta giải quyết các bài toán lớn hơn, chứ không phải giải cùng một bài toán nhanh hơn. Trong ML, điều này tương ứng với việc tăng kích thước batch khi có nhiều GPU hơn (mở rộng yếu — weak scaling) thay vì giữ nguyên kích thước batch (mở rộng mạnh — strong scaling).

Bài Tập Lập Trình (dùng CoLab hoặc notebook)¶

Minh họa một điều kiện đua. Hai luồng tăng một bộ đếm dùng chung mà không đồng bộ hóa và quan sát các cập nhật bj mất.

import threading

counter = 0

def increment(n):
    global counter
    for _ in range(n):
        counter += 1  # KHÔNG nguyên tử: đọc, cộng, ghi

threads = [threading.Thread(target=increment, args=(100000,)) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()

print(f"Expected: {4 * 100000}")
print(f"Actual:   {counter}")
print(f"Lost updates: {4 * 100000 - counter}")

Sửa điều kiện đua bằng một khóa và đo lường chi phí.

import threading
import time

lock = threading.Lock()
counter = 0

def increment_locked(n):
    global counter
    for _ in range(n):
        with lock:
            counter += 1

start = time.time()
threads = [threading.Thread(target=increment_locked, args=(100000,)) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
elapsed = time.time() - start

print(f"Counter: {counter} (correct: {4 * 100000})")
print(f"Time with lock: {elapsed:.3f}s")

Trực quan hóa định luật Amdahl. Vẽ đồ thị tốc độ tăng so với số bộ xử lý cho các phân đoạn song song khác nhau.

import jax.numpy as jnp
import matplotlib.pyplot as plt

n_procs = jnp.arange(1, 65)

for p, color in [(0.5, "#e74c3c"), (0.9, "#f39c12"), (0.95, "#27ae60"), (0.99, "#3498db")]:
    speedup = 1 / ((1 - p) + p / n_procs)
    plt.plot(n_procs, speedup, color=color, linewidth=2, label=f"p={p}")
    # Đường tốc độ tăng tối đa
    plt.axhline(1 / (1 - p), color=color, linestyle="--", alpha=0.3)

plt.xlabel("Number of processors")
plt.ylabel("Speedup")
plt.title("Amdahl's Law: Serial Fraction Limits Speedup")
plt.legend()
plt.grid(True)
plt.show()