Computer Systems: A Programmer's Perspective Chương 12 · Concurrent Programming

Chương 12 · Lập trình đồng thời Chapter 12 · Concurrent Programming

Làm nhiều việc cùng lúc — ba cách dựng, một bài toán khó đồng bộ Khi máy làm nhiều việc một lúc, và vì sao phải cẩn thận Doing many things at once — three ways to build it, one hard problem to synchronize

Bryant và O'Hallaron mở đầu bằng một ý đã gặp ở Chương 8: các luồng điều khiển logic là đồng thời (concurrent) nếu chúng chồng lấn nhau về thời gian. Đến đây tính đồng thời không còn chỉ là chuyện của nhân hệ điều hành — nó trở thành công cụ cho chính chương trình ứng dụng: phục vụ nhiều máy khách mạng, tương tác với con người, giấu độ trễ của thiết bị I/O chậm, và tính toán song song trên máy nhiều lõi.1 Hệ điều hành hiện đại cung cấp ba cách dựng chương trình đồng thời: tiến trình (processes), dồn kênh I/O (I/O multiplexing), và luồng (threads).1

Một chương trình "đồng thời" là chương trình làm nhiều việc chồng lấn nhau về thời gian — ví dụ một máy chủ phục vụ nhiều người cùng lúc, hay một ứng dụng vừa in tài liệu vừa cho bạn kéo cửa sổ. Sách giới thiệu ba cách để viết kiểu chương trình này: dùng nhiều tiến trình, dùng một mẹo gọi là dồn kênh I/O, và dùng luồng. Nhớ nhé: "đồng thời" nghĩa là nhiều việc gối đầu nhau, và có ba cách dựng nó.

Bryant and O'Hallaron open with an idea from Chapter 8: logical control flows are concurrent if they overlap in time. By now concurrency is no longer just a kernel mechanism — it becomes a tool for application programs themselves: servicing multiple network clients, interacting with humans, hiding the latency of slow I/O devices, and computing in parallel on multi-core machines.1 Modern operating systems provide three basic approaches for building concurrent programs: processes, I/O multiplexing, and threads.1

Điểm tổ chức tinh tế: cả chương dùng một ứng dụng dẫn dắt xuyên suốt — một phiên bản đồng thời của máy chủ echo lặp đã gặp ở Chương 11 — rồi lần lượt dựng lại nó bằng cả ba cách để so sánh trực tiếp ưu–nhược.1 Tiến trình có không gian địa chỉ riêng nên an toàn nhưng phải dùng cơ chế liên lạc liên tiến trình (IPC) để chia sẻ dữ liệu và tốn chi phí điều khiển cao; dồn kênh I/O chạy trong một tiến trình duy nhất, dễ chia sẻ dữ liệu và gỡ lỗi nhưng mã phức tạp hơn và khó tận dụng đa lõi; luồng là thể lai — được nhân lập lịch như tiến trình nhưng chia sẻ cả không gian địa chỉ như dồn kênh I/O.1 Nửa sau của chương chuyển sang vấn đề thật sự khó: một khi các luồng chia sẻ dữ liệu, việc đồng bộ truy cập trở thành bài toán nền tảng — và đó là lúc cờ hiệu, tranh chấp và khoá chết bước vào.1

Luận đề của chương: tính đồng thời là công cụ mạnh của ứng dụng, dựng được bằng ba cách — tiến trình, dồn kênh I/O, luồng — mỗi cách một kiểu đánh đổi; nhưng ngay khi các luồng điều khiển chia sẻ dữ liệu, đồng bộ hoá trở thành bài toán cốt lõi, và cờ hiệu (semaphore) với hai thao tác P/V là công cụ kinh điển để giải nó một cách đúng đắn.1

Ý chính: có ba cách để máy làm nhiều việc một lúc, mỗi cách được–mất khác nhau. Nhưng khi nhiều việc cùng động vào một dữ liệu, ta phải "xếp hàng" cho ngay ngắn, nếu không kết quả sẽ sai. Nhớ nhé: làm song song thì dễ, chia sẻ dữ liệu cho đúng mới khó.

The chapter's thesis: concurrency is a powerful application-level tool, buildable in three ways — processes, I/O multiplexing, threads — each with its own trade-offs; but the moment control flows share data, synchronization becomes the central problem, and the semaphore, with its two P/V operations, is the classic tool for solving it correctly.1

Cụm khái niệm 01 Concept cluster 01

Ba cách dựng một chương trình đồng thời Ba cách để một chương trình làm nhiều việc cùng lúc Three ways to build a concurrent program

Để so sánh công bằng, cả chương dùng chung một ứng dụng: máy chủ echo đồng thời. Với tiến trình, máy chủ dùng fork để tạo một tiến trình con phục vụ mỗi máy khách; với dồn kênh I/O, nó dùng select để một tiến trình duy nhất chờ nhiều sự kiện I/O; với luồng, nó tạo một luồng ngang hàng cho mỗi kết nối.15

Để dễ so sánh, sách lấy đúng một ví dụ: một máy chủ nhận tin rồi "vọng lại" cho nhiều người cùng lúc. Cách 1 là đẻ ra một tiến trình con phục vụ mỗi người. Cách 2 là một tiến trình khéo léo chờ "ai cần gì thì làm nấy". Cách 3 là tạo nhiều luồng trong cùng một tiến trình. Nhớ nhé: cùng một bài toán, ba cách giải, mỗi cách một kiểu được–mất.

For a fair comparison, the whole chapter uses one application: a concurrent echo server. With processes, the server uses fork to create a child process to service each client; with I/O multiplexing, it uses select so a single process can wait on many I/O events; with threads, it creates a peer thread for each connection.15

Định nghĩa. Một luồng (thread) là một luồng điều khiển logic chạy trong ngữ cảnh của một tiến trình. Mỗi luồng có ngữ cảnh luồng (thread context) riêng: một mã định danh luồng nguyên duy nhất (TID), ngăn xếp, con trỏ ngăn xếp, bộ đếm chương trình, các thanh ghi và cờ điều kiện. Nhưng mọi luồng trong một tiến trình dùng chung toàn bộ không gian địa chỉ ảo của tiến trình đó — mã, dữ liệu, heap, thư viện dùng chung, và tệp đang mở.1

Nói đơn giản. "Luồng" là một mạch công việc chạy bên trong một tiến trình. Mỗi luồng có ngăn xếp riêng, nhưng tất cả luồng dùng chung bộ nhớ của tiến trình. Nhớ nhé: các luồng ở chung nhà (bộ nhớ) nhưng mỗi đứa có bàn làm việc riêng (ngăn xếp).

Definition. A thread is a logical control flow that runs in the context of a process. Each thread has its own thread context: a unique integer thread ID (TID), stack, stack pointer, program counter, registers, and condition codes. But all threads in a process share the entire virtual address space — code, data, heap, shared libraries, and open files.1

processes: Fork() / exec / waitpid
I/O mux: select(n, &read_set, …)
threads: Pthread_create / _join
  Pthread_detach / _self

tiến trình: fork
dồn kênh: select
luồng: pthread_create

processes: Fork() / exec / waitpid
I/O mux: select(n, &read_set, …)
threads: Pthread_create / _join
  Pthread_detach / _self

  1. processes

    Tiến trình — cách đơn giản nhất, cách ly nhất Tiến trình — mỗi việc một "căn phòng" riêng Processes — the simplest, most isolated way

    Cách đơn giản nhất để dựng một máy chủ đồng thời là fork một tiến trình con cho mỗi máy khách. Vì máy chủ chạy lâu dài, nó phải có một bộ xử lý SIGCHLD để thu hồi các tiến trình con zombie; do tín hiệu trong Linux không được xếp hàng, bộ xử lý phải sẵn sàng thu hồi nhiều zombie một lượt bằng waitpid trong vòng lặp.1 Cả cha và con đều phải đóng bản sao connfd của mình, nếu không bộ đếm tham chiếu không về 0 và sinh rò rỉ bộ nhớ.1

    Dễ nhất: mỗi khi có khách mới, máy chủ "đẻ" ra một tiến trình con để lo riêng cho khách đó. Nhưng máy chủ chạy mãi nên phải nhớ dọn xác các con đã xong việc, và cả cha lẫn con đều phải đóng kết nối của mình. Nhớ nhé: đẻ con thì phải nhớ dọn dẹp, kẻo máy đầy rác.

    The simplest way to build a concurrent server is to fork a child process for each client. Because servers run for long periods, the server must install a SIGCHLD handler to reap zombie children; since Linux signals are not queued, the handler must be prepared to reap multiple zombies at once with waitpid in a loop.1 Both parent and child must close their copy of connfd, or the reference count never reaches zero and memory leaks.1

    Bạn gặp nó ở đâuWhere you meet it Mô hình tiến trình-mỗi-kết-nối từng là xương sống của nhiều máy chủ Unix cổ điển (ví dụ các dịch vụ chạy qua inetd). Nhiều máy chủ đời đầu chạy đúng kiểu này: một khách, một tiến trình. The process-per-connection model was the backbone of many classic Unix servers (for example, services run via inetd).

    Ưu điểm của tiến trình

    Không gian địa chỉ riêng là một lợi thế: một tiến trình không thể vô tình ghi đè bộ nhớ ảo của tiến trình khác, loại bỏ cả một lớp lỗi khó hiểu.1

    Nhược điểm của tiến trình

    Chính vì tách biệt, muốn chia sẻ trạng thái phải dùng cơ chế liên lạc liên tiến trình (IPC) tường minh; và thiết kế dựa trên tiến trình thường chậm hơn vì chi phí điều khiển tiến trình và IPC cao.1

  2. I/O multiplexing

    Dồn kênh I/O — một tiến trình, nhiều máy trạng thái Dồn kênh I/O — một tiến trình tự xoay vòng I/O multiplexing — one process, many state machines

    Ý tưởng: dùng hàm select để yêu cầu nhân tạm treo tiến trình, chỉ trả quyền điều khiển lại khi một hoặc nhiều sự kiện I/O đã xảy ra trên một tập mô tả (descriptor set).15 Các luồng logic được mô hình hoá thành máy trạng thái (state machine): khi một mô tả kết nối sẵn sàng đọc, máy chủ thực hiện bước chuyển tương ứng. Vì cả chương trình là một tiến trình duy nhất, mọi luồng chia sẻ chung không gian địa chỉ.1

    Thay vì đẻ nhiều tiến trình, một tiến trình dùng một "người gác cổng" tên là select: nó ngồi chờ, ai (kết nối nào) có dữ liệu đến thì mới xử lý người đó. Nhờ vậy chỉ cần một tiến trình mà vẫn lo được nhiều khách. Nhớ nhé: một tiến trình, một người gác cổng, phục vụ ai sẵn sàng trước.

    The idea: use the select function to ask the kernel to suspend the process, returning control only after one or more I/O events have occurred on a descriptor set.15 Logical flows are modeled as state machines: when a connected descriptor is ready for reading, the server executes the corresponding transition. Because the whole program is a single process, every flow shares the same address space.1

    Bạn gặp nó ở đâuWhere you meet it Các máy chủ hiệu năng cao hiện đại như Node.js, nginx và Tornado dùng lập trình hướng sự kiện dựa trên dồn kênh I/O, chủ yếu vì lợi thế hiệu năng so với tiến trình và luồng.1 Nhiều máy chủ web nhanh ngày nay (Node.js, nginx) hoạt động đúng theo kiểu này. Modern high-performance servers such as Node.js, nginx, and Tornado use event-driven programming based on I/O multiplexing, mainly for its performance advantage over processes and threads.1

    Được: kiểm soát và hiệu quả

    Lập trình viên nắm nhiều quyền kiểm soát hơn (ví dụ ưu tiên một số máy khách); chạy trong một tiến trình nên dễ chia sẻ dữ liệu và gỡ lỗi như chương trình tuần tự bằng gdb; và thường hiệu quả hơn vì không tốn chuyển ngữ cảnh tiến trình.1

    Mất: phức tạp và không dùng được đa lõi

    Nhược điểm lớn là độ phức tạp của mã: máy chủ hướng sự kiện trong ví dụ cần nhiều mã gấp ba lần bản dựa trên tiến trình, và càng phức tạp khi độ hạt (granularity) của đồng thời càng nhỏ. Thiết kế hướng sự kiện cũng không tận dụng được đầy đủ bộ xử lý đa lõi.1

  3. threads (Pthreads)

    Luồng — thể lai, do nhân lập lịch mà vẫn chia sẻ bộ nhớ Luồng — kết hợp cái hay của hai cách trên Threads — a hybrid, kernel-scheduled yet memory-sharing

    Luồng kết hợp phẩm chất của hai cách kia: như tiến trình, chúng được nhân lập lịch tự động và được nhân biết đến qua một mã định danh nguyên; như dồn kênh I/O, nhiều luồng chạy trong ngữ cảnh một tiến trình và chia sẻ toàn bộ không gian địa chỉ.1 Pthreads (POSIX threads) là giao diện chuẩn để thao tác luồng từ C, được thông qua năm 1995 và có trên mọi hệ Linux; nó định nghĩa khoảng 60 hàm.12

    Luồng là kiểu "hai trong một": được hệ điều hành tự xếp lịch như tiến trình, nhưng lại dùng chung bộ nhớ như cách dồn kênh. Người ta điều khiển luồng bằng một bộ hàm chuẩn tên là Pthreads. Nhớ nhé: luồng vừa được nhân lo giúp, vừa dùng chung bộ nhớ — tiện nhưng dễ giẫm chân nhau.

    Threads combine qualities of the other two: like processes they are scheduled automatically by the kernel and known to it by an integer ID; like I/O multiplexing, multiple threads run in the context of one process and share the entire address space.1 Pthreads (POSIX threads) is the standard interface for manipulating threads from C, adopted in 1995 and available on all Linux systems; it defines about 60 functions.12

    Bạn gặp nó ở đâuWhere you meet it Mỗi khi bạn gọi pthread_create để tạo một luồng ngang hàng, rồi pthread_join để chờ nó kết thúc, hay pthread_detach để nó tự thu hồi tài nguyên khi xong.12 Khi một chương trình tạo thêm "nhánh" chạy song song bên trong chính nó. Every time you call pthread_create to spawn a peer thread, then pthread_join to wait for it, or pthread_detach so it reclaims its own resources when done.12

    Một cạm bẫy ngay từ đầu

    Trong máy chủ echo dựa trên luồng, truyền trực tiếp địa chỉ của biến connfd cục bộ cho luồng mới sẽ tạo một tranh chấp (race) giữa lệnh gán trong luồng ngang hàng và lệnh accept kế tiếp trong luồng chính; sách cấp phát động một khối riêng cho mỗi mô tả để tránh.1

    Thu hồi để tránh rò rỉ

    Luồng mặc định là có thể gộp (joinable); để tránh rò rỉ bộ nhớ, mỗi luồng joinable phải được thu hồi tường minh bằng pthread_join hoặc tự tách ra bằng pthread_detach.12

Cụm khái niệm 02 Concept cluster 02

Biến chia sẻ và đồng bộ hoá luồng bằng cờ hiệu Dữ liệu dùng chung, và cách "xếp hàng" cho đúng Shared variables and synchronizing threads with semaphores

Mô hình bộ nhớ của luồng không hoàn toàn gọn gàng. Các thanh ghi không bao giờ được chia sẻ, còn bộ nhớ ảo thì luôn được chia sẻ. Một biến là chia sẻ (shared) khi và chỉ khi có nhiều hơn một luồng tham chiếu tới một thể hiện của nó.1 Biến toàn cục và biến tĩnh cục bộ chỉ có một thể hiện trong vùng đọc/ghi, nên dễ bị chia sẻ; biến tự động cục bộ nằm trên ngăn xếp riêng của từng luồng.1

Trong một tiến trình nhiều luồng, biến toàn cục giống như một cái bảng chung ai cũng thấy và sửa được. Biến cục bộ thì giống tờ giấy nháp riêng của mỗi luồng. Rắc rối xảy ra khi nhiều luồng cùng sửa cái bảng chung. Nhớ nhé: bảng chung (biến toàn cục) là chỗ dễ sinh chuyện nhất.

The threads memory model is not entirely clean. Registers are never shared, while virtual memory is always shared. A variable is shared if and only if more than one thread references one of its instances.1 Global and local static variables have a single instance in the read/write area, so they are easily shared; local automatic variables live on each thread's private stack.1

Định nghĩa. Một cờ hiệu (semaphore) s là một biến toàn cục mang giá trị nguyên không âm, chỉ được thao tác bởi hai phép đặc biệt. P(s): nếu s khác 0 thì giảm s và trả về ngay; nếu s bằng 0 thì treo luồng cho tới khi s khác 0, rồi một phép V khởi động lại nó. V(s): tăng s thêm 1; nếu có luồng đang chờ thì khởi động lại đúng một luồng để nó hoàn tất phép P.13

Nói đơn giản. Cờ hiệu như một chiếc chìa khoá phòng: ai lấy được chìa (phép P) mới vào phòng sửa dữ liệu, xong thì trả chìa (phép V) cho người sau. Nếu hết chìa thì phải đứng chờ. Nhớ nhé: có chìa mới được vào, trả chìa thì người khác mới tới lượt.

Definition. A semaphore s is a global variable holding a nonnegative integer, manipulated only by two special operations. P(s): if s is nonzero, decrement s and return immediately; if s is zero, suspend the thread until s becomes nonzero, whereupon a V restarts it. V(s): increment s by 1; if any thread is waiting, restart exactly one so it can complete its P.13

P(s) ≡ sem_wait(&s)
V(s) ≡ sem_post(&s)
Sem_init(&mutex, 0, 1); // mutex=1
for(…){ P(&mutex); cnt++; V(&mutex); }

P = lấy chìa (sem_wait)
V = trả chìa (sem_post)
bọc chỗ sửa dữ liệu bằng P…V

P(s) ≡ sem_wait(&s)
V(s) ≡ sem_post(&s)
Sem_init(&mutex, 0, 1); // mutex=1
for(…){ P(&mutex); cnt++; V(&mutex); }

  1. shared variable

    Biến chia sẻ — ranh giới quyết định an toàn Biến chia sẻ — thứ nhiều luồng cùng động vào Shared variable — the line that decides safety

    Để biết một biến trong C có bị chia sẻ không, ta hỏi: mô hình bộ nhớ của luồng là gì, biến được ánh xạ vào bộ nhớ ra sao, và có mấy luồng tham chiếu tới nó. Một biến tự động cục bộ có thể bị chia sẻ nếu một luồng nắm được con trỏ tới nó; còn biến toàn cục thì chỉ có một thể hiện duy nhất cho mọi luồng.1

    Muốn biết một biến có bị dùng chung không, hãy đếm xem có mấy luồng đụng tới nó. Biến toàn cục gần như luôn bị chung; biến cục bộ thường là của riêng, trừ khi bạn lỡ đưa địa chỉ của nó cho luồng khác. Nhớ nhé: đếm số luồng đụng vào — từ hai trở lên là biến chia sẻ.

    To decide whether a C variable is shared, ask: what is the threads memory model, how is the variable mapped to memory, and how many threads reference it. A local automatic variable can be shared if a thread obtains a pointer to it; a global variable has a single instance for all threads.1

    Bạn gặp nó ở đâuWhere you meet it Mỗi khi bạn khai báo một biến đếm hay một cấu trúc trạng thái toàn cục rồi để nhiều luồng cùng cập nhật — đó là biến chia sẻ cần được bảo vệ. Khi một biến đếm chung bị nhiều luồng cùng tăng lên. Every time you declare a global counter or shared state struct that several threads update — that is a shared variable needing protection.
  2. race on badcnt.c

    Lỗi đồng bộ — cùng mã, mỗi lần một kết quả Thiếu đồng bộ — kết quả sai và khác nhau mỗi lần A sync error — same code, a different answer each run

    Chương trình badcnt.c tạo hai luồng, mỗi luồng tăng một biến đếm chung cnt đúng niters lần, nên ta kỳ vọng giá trị cuối là 2 × niters. Nhưng khi chạy, nó không chỉ cho kết quả sai mà còn khác nhau mỗi lần — ví dụ với niters = 1.000.000, ba lần chạy cho BOOM! cnt=1445085, rồi 1915220, rồi 1404746.1 Nguyên nhân: lệnh cnt++ thực ra là ba bước máy (nạp, tăng, lưu) có thể bị đan xen giữa hai luồng theo thứ tự không an toàn.1

    Hai luồng cùng đếm, mỗi luồng cộng một triệu, lẽ ra phải ra hai triệu. Nhưng kết quả vừa sai vừa đổi mỗi lần chạy, vì "cộng 1" thật ra gồm ba bước nhỏ, và hai luồng chen ngang nhau giữa các bước đó. Nhớ nhé: "cộng 1" không phải một bước liền mạch — chen ngang là hỏng.

    The badcnt.c program creates two threads, each incrementing a shared counter cnt exactly niters times, so we expect a final value of 2 × niters. But when run, it not only gives wrong answers, it gives different answers each time — for example, with niters = 1,000,000, three runs printed BOOM! cnt=1445085, then 1915220, then 1404746.1 The cause: cnt++ is really three machine steps (load, update, store) that can interleave between the two threads in an unsafe order.1

    Bạn gặp nó ở đâuWhere you meet it Mỗi khi một bộ đếm, bộ nhớ đệm hay sổ cái dùng chung cho ra con số "gần đúng nhưng cứ chạy lại là lệch" — đó là dấu hiệu kinh điển của truy cập không được đồng bộ. Khi một con số thống kê cứ chạy lại là ra kết quả khác một chút — rất đáng ngờ. Whenever a shared counter, cache, or ledger yields a number that is "close but shifts every rerun" — the classic sign of unsynchronized access.

    Năm phần của vòng lặp

    Sách chia mã vòng lặp cho luồng i thành năm phần: đầu vòng (Hi), nạp cnt (Li), cập nhật (Ui), lưu lại (Si), cuối vòng (Ti). Chỉ L, U, S đụng tới biến chia sẻ; một số thứ tự đan xen cho kết quả đúng, số khác thì không.1

    Đồ thị tiến trình

    Giao của hai vùng tới hạn (critical region) tạo thành một vùng không an toàn (unsafe region). Một quỹ đạo thực thi là an toàn khi và chỉ khi nó né được vùng này.1

  3. P / V · mutex

    Cờ hiệu và mutex — loại trừ lẫn nhau cho đúng Cờ hiệu — chiếc chìa khoá giữ cho đúng lượt Semaphores and mutexes — mutual exclusion done right

    Edsger Dijkstra, người tiên phong của lập trình đồng thời, đề xuất cờ hiệu cùng hai phép P và V (từ tiếng Hà Lan proberen — thử, và verhogen — tăng).13 Để sửa badcnt.c, ta khai báo một cờ hiệu mutex khởi tạo bằng 1 rồi bọc cnt++ giữa P(&mutex) và V(&mutex); cờ hiệu dùng kiểu này gọi là cờ hiệu nhị phân (binary semaphore) hay mutex. Bản vá goodcnt cho kết quả đúng mỗi lần: OK cnt=2000000.14

    Cách sửa: đặt một chiếc chìa khoá (mutex) cho biến đếm. Luồng nào muốn sửa phải lấy chìa (P) trước và trả chìa (V) sau. Nhờ vậy mỗi lúc chỉ một luồng được sửa, và kết quả luôn đúng là hai triệu. Nhớ nhé: khoá chỗ sửa dữ liệu lại bằng P…V thì kết quả mới chắc chắn đúng.

    Edsger Dijkstra, a pioneer of concurrent programming, proposed the semaphore with its two operations P and V (from the Dutch proberen, to test, and verhogen, to increment).13 To fix badcnt.c, declare a semaphore mutex initialized to 1 and wrap cnt++ between P(&mutex) and V(&mutex); a semaphore used this way is a binary semaphore, or mutex. The fixed goodcnt gives the right answer every time: OK cnt=2000000.14

    Bạn gặp nó ở đâuWhere you meet it Trong POSIX, P là sem_wait và V là sem_post, khởi tạo bằng sem_init; mọi khoá (lock) bảo vệ vùng tới hạn trong lập trình luồng đều là hậu duệ của ý tưởng này.14 Mọi "khoá" trong lập trình nhiều luồng ngày nay đều bắt nguồn từ ý tưởng cờ hiệu này. In POSIX, P is sem_wait and V is sem_post, initialized by sem_init; every lock protecting a critical region in threaded code descends from this idea.14

    Bất biến cờ hiệu

    Định nghĩa của P và V bảo đảm một cờ hiệu đã khởi tạo đúng không bao giờ mang giá trị âm — tính chất gọi là bất biến cờ hiệu (semaphore invariant). Nó tạo ra một vùng cấm (forbidden region) bao quanh vùng không an toàn, khiến không quỹ đạo khả thi nào chạm được vào đó.1

    Không chỉ loại trừ lẫn nhau

    Ngoài loại trừ lẫn nhau, cờ hiệu còn dùng để lập lịch truy cập tài nguyên chung — ví dụ bộ đệm giới hạn trong hệ sản xuất–tiêu thụ (producer-consumer) và đối tượng chung trong hệ đọc–ghi (readers-writers).1

Cụm khái niệm 03 Concept cluster 03

Dùng luồng để song song hoá, và các vấn đề đồng thời khác Chạy nhanh hơn nhờ nhiều lõi, và những cạm bẫy còn lại Using threads for parallelism, and other concurrency issues

Trên máy nhiều lõi, một chương trình được chia thành các luồng độc lập có thể chạy song song (in parallel) thay vì đan xen, nên nhanh hơn. Sách minh hoạ bằng bài toán cộng một dãy số: bản psum-mutex dùng mutex bảo vệ một biến tổng chung chạy rất chậm; psum-array cho mỗi luồng ghi vào một ô mảng riêng; còn psum-local dồn tổng vào một biến cục bộ — mỗi bước cải tiến nhanh lên cả một bậc độ lớn.1

Máy nhiều lõi cho phép chia việc ra làm cùng lúc, nên nhanh hơn. Nhưng cách chia rất quan trọng: nếu các luồng cứ phải tranh nhau một chỗ nhớ chung thì chậm; nếu mỗi luồng làm trên chỗ riêng rồi mới gộp lại thì nhanh hơn hẳn. Nhớ nhé: chia việc khéo thì nhanh, bắt các luồng tranh nhau thì chậm.

On multi-core machines, a program split into independent threads can run in parallel rather than interleaved, so it runs faster. The book illustrates with summing a sequence: psum-mutex, which guards a shared sum with a mutex, runs very slowly; psum-array has each thread write its own array slot; and psum-local accumulates into a local variable — each step an order-of-magnitude speedup.1

Định nghĩa. Tăng tốc (speedup) của một chương trình song song chạy trên p lõi là Sp = T1 / Tp, với Tk là thời gian chạy trên k lõi. Nếu T1 là thời gian của bản tuần tự thì Sp là tăng tốc tuyệt đối; nếu là bản song song chạy trên một lõi thì là tăng tốc tương đối. Hiệu suất (efficiency) là Ep = Sp / p, thường ghi theo phần trăm.1

Nói đơn giản. "Tăng tốc" đo xem chương trình nhanh lên mấy lần khi thêm lõi; "hiệu suất" đo xem mỗi lõi được dùng hiệu quả tới đâu. Nhớ nhé: thêm lõi chưa chắc nhanh gấp đôi — còn tuỳ hiệu suất.

Definition. The speedup of a parallel program on p cores is Sp = T1 / Tp, where Tk is the running time on k cores. If T1 is the sequential version's time, Sp is absolute speedup; if the one-core parallel version's, it is relative speedup. Efficiency is Ep = Sp / p, usually reported as a percentage.1

psum-local, 4 lõi, n=2³¹:
luồng  1   2   4   8  16
Tp 1.06 .54 .28 .29 .30
Sp   1 1.9 3.8 3.7 3.5

4 lõi: nhanh dần tới 4 luồng
rồi chững lại và hơi chậm đi

psum-local, 4 cores, n=2³¹:
thr  1   2   4   8  16
Tp 1.06 .54 .28 .29 .30
Sp   1 1.9 3.8 3.7 3.5

  1. speedup & efficiency

    Tăng tốc có giới hạn — bốn lõi, bốn luồng là đẹp Thêm lõi chỉ nhanh tới một mức Speedup has limits — four cores, four threads is the sweet spot

    Đo psum-local cộng dãy 2³¹ phần tử trên hệ bốn lõi, thời gian giảm gần như tuyến tính tới bốn luồng rồi chững lại và hơi tăng: với 1/2/4/8/16 luồng, thời gian là 1.06/0.54/0.28/0.29/0.30 giây, tăng tốc 1/1.9/3.8/3.7/3.5, và hiệu suất 100%/98%/95%/91%/88%.1 Qua mốc bốn luồng, mỗi lõi phải chạy hơn một luồng nên chi phí chuyển ngữ cảnh làm chậm lại — vì vậy chương trình song song thường được viết để mỗi lõi chạy đúng một luồng.1

    Trên máy bốn lõi, càng thêm luồng càng nhanh — nhưng chỉ tới bốn luồng. Quá đó, các luồng phải chia nhau lõi và tốn công đổi qua đổi lại, nên không nhanh thêm, thậm chí chậm đi chút. Nhớ nhé: số luồng tốt nhất thường bằng số lõi.

    Measuring psum-local summing 2³¹ elements on a four-core system, time drops nearly linearly up to four threads, then levels off and rises slightly: for 1/2/4/8/16 threads the times are 1.06/0.54/0.28/0.29/0.30 seconds, speedups 1/1.9/3.8/3.7/3.5, and efficiencies 100%/98%/95%/91%/88%.1 Beyond four threads, each core runs more than one thread, so context-switching overhead slows things down — which is why parallel programs are often written so each core runs exactly one thread.1

    Bạn gặp nó ở đâuWhere you meet it Khi bạn tăng số luồng của một tác vụ tính toán mà thấy đồ thị thời gian "gãy" đúng tại số lõi vật lý của máy. Khi thêm luồng mà chương trình không nhanh thêm nữa — thường là đã chạm trần số lõi. When you raise the thread count of a compute task and the time curve bends right at the machine's physical core count.

    Mạnh và yếu

    Cách đo ở trên là mở rộng mạnh (strong scaling): cố định khối lượng công việc. Còn mở rộng yếu (weak scaling) tăng cả kích thước bài toán theo số lõi, giữ công việc trên mỗi lõi không đổi — thường phản ánh thực tế khoa học tính toán sát hơn.1

    Tại sao thiết kế quan trọng

    Ba bản psum cho thấy thay đổi nhỏ trong mã tác động lớn tới hiệu năng: dùng mutex cho một biến chung chậm hơn hàng bậc so với dồn vào biến cục bộ rồi mới gộp.1

  2. thread safety

    An toàn luồng — bốn lớp hàm không an toàn An toàn luồng — bốn kiểu hàm dễ gây lỗi Thread safety — four classes of unsafe functions

    Một hàm là an toàn luồng (thread-safe) nếu luôn cho kết quả đúng khi bị nhiều luồng gọi lặp lại. Sách nêu bốn lớp hàm không an toàn: (1) không bảo vệ biến chia sẻ; (2) giữ trạng thái qua nhiều lần gọi (như rand); (3) trả con trỏ tới một biến tĩnh (như ctime, gethostbyname); và (4) gọi một hàm không an toàn khác.1 Linux cung cấp phiên bản tái nhập (reentrant) cho hầu hết, tên kết thúc bằng hậu tố _r — ví dụ rand_r, ctime_r, strtok_r.1

    Một hàm "an toàn luồng" là hàm dùng được bởi nhiều luồng mà vẫn ra kết quả đúng. Có bốn kiểu hàm dễ gây lỗi khi chạy đa luồng. Nhiều hàm Linux có bản "an toàn" tên kết thúc bằng _r để thay thế. Nhớ nhé: gặp đa luồng, ưu tiên các hàm có đuôi _r.

    A function is thread-safe if it always produces correct results when called repeatedly from multiple threads. The book identifies four classes of unsafe functions: (1) those that fail to protect shared variables; (2) those that keep state across invocations (like rand); (3) those that return a pointer to a static variable (like ctime, gethostbyname); and (4) those that call an unsafe function.1 Linux provides reentrant versions of most, named with an _r suffix — e.g. rand_r, ctime_r, strtok_r.1

    Bạn gặp nó ở đâuWhere you meet it Khi một hàm thư viện cũ như gethostbyname cho kết quả bị "tráo" trong chương trình đa luồng vì nó trả con trỏ tới một biến tĩnh dùng chung. Khi một hàm cũ cho kết quả lẫn lộn giữa các luồng — hãy đổi sang bản đuôi _r. When an old library function like gethostbyname returns silently overwritten results in a threaded program because it points into a shared static variable.

    Tái nhập là tập con

    Các hàm tái nhập (reentrant) không tham chiếu bất kỳ dữ liệu chia sẻ nào khi bị nhiều luồng gọi; chúng là tập con đúng của các hàm an toàn luồng và thường hiệu quả hơn vì không cần thao tác đồng bộ.1

    Mẹo khoá-và-chép

    Với hàm lớp 3 khó sửa, có thể dùng kỹ thuật khoá-và-chép (lock-and-copy): bọc lời gọi bằng mutex, chép kết quả sang vùng riêng rồi mở khoá — như hàm bọc ctime_ts trong sách.1

  3. races & deadlocks

    Tranh chấp và khoá chết — hai lỗi khó tái hiện nhất Tranh chấp và khoá chết — lỗi lúc có lúc không Races & deadlocks — the hardest bugs to reproduce

    Một tranh chấp (race) xảy ra khi tính đúng đắn của chương trình phụ thuộc vào việc luồng này tới một điểm trước luồng kia; nó thường do giả định sai về thứ tự lập lịch. Chương trình race.c truyền cho mỗi luồng con một con trỏ tới biến đếm vòng lặp dùng chung, nên mỗi luồng có thể đọc nhầm mã định danh.1 Một khoá chết (deadlock) là khi một nhóm luồng bị chặn, chờ một điều kiện không bao giờ thành — thường vì các vùng cấm của hai cờ hiệu chồng lên nhau.1

    "Tranh chấp" là lỗi do hai luồng chạy nhanh chậm khác nhau, lúc đúng lúc sai. "Khoá chết" là khi các luồng cùng đứng chờ nhau mãi mà không ai nhường, nên treo luôn. Cả hai đều rất khó bắt vì chạy lại chưa chắc đã tái hiện. Nhớ nhé: lỗi lúc có lúc không thường là tranh chấp hoặc khoá chết.

    A race occurs when a program's correctness depends on one thread reaching a point before another; it usually stems from a wrong assumption about scheduling. The race.c program passes each peer thread a pointer to the shared loop counter, so a thread may read the wrong ID.1 A deadlock is when a collection of threads is blocked, waiting for a condition that will never be true — often because two semaphores' forbidden regions overlap.1

    Bạn gặp nó ở đâuWhere you meet it Khi một chương trình đa luồng chạy đúng cả nghìn lần rồi bỗng treo, hoặc chạy ngon trên máy này nhưng treo trên máy khác — dấu hiệu kinh điển của tranh chấp hoặc khoá chết. Khi chương trình thỉnh thoảng mới treo, hoặc chỉ treo trên một máy nào đó. When a threaded program runs correctly a thousand times then hangs, or works on one machine but deadlocks on another — classic signs of a race or deadlock.

    Quy tắc xếp thứ tự mutex

    Với cờ hiệu nhị phân dùng loại trừ lẫn nhau, có một quy tắc đơn giản và hiệu quả: cho một thứ tự toàn phần trên mọi mutex, chương trình không khoá chết nếu mỗi luồng lấy các mutex theo đúng thứ tự đó và trả theo thứ tự ngược lại.1

    Vì sao khó gỡ

    Khoá chết đặc biệt khó vì không phải lúc nào cũng dự đoán được: một số quỹ đạo may mắn né được vùng khoá chết, số khác rơi vào và không thoát ra được; lỗi thường không lặp lại vì mỗi lần chạy có quỹ đạo khác nhau.1

Ba ngộ nhận thường gặp Three common misconceptions

“Dùng luồng thì đương nhiên nhanh gấp số lõi” “Threads automatically give speedup equal to the core count”

Ngộ nhận: cứ thêm luồng là nhanh thêm tương ứng.

Thực tế: trên hệ bốn lõi, psum-local chỉ tăng tốc tới ~3.8× ở bốn luồng rồi chững và giảm nhẹ; quá số lõi, chi phí chuyển ngữ cảnh làm chậm lại.1

Myth: more threads always mean proportionally more speed.

Reality: on a four-core system, psum-local speeds up only ~3.8× at four threads, then levels off and dips; beyond the core count, context-switch overhead slows it.1

“Biến toàn cục dùng chung là được, khỏi khoá” “Sharing a global variable is fine without a lock”

Ngộ nhận: nhiều luồng cùng tăng một biến đếm thì vẫn ra đúng tổng.

Thực tế: badcnt.c cho kết quả sai và khác nhau mỗi lần (ví dụ 1445085, 1915220, 1404746) vì cnt++ không phải thao tác liền mạch; phải bọc bằng P/V.1

Myth: several threads incrementing a counter still sum correctly.

Reality: badcnt.c gives wrong, run-to-run-different answers (e.g. 1445085, 1915220, 1404746) because cnt++ is not atomic; it must be wrapped in P/V.1

“An toàn luồng và tái nhập là một” “Thread-safe and reentrant mean the same thing”

Ngộ nhận: hai thuật ngữ dùng thay cho nhau được.

Thực tế: hàm tái nhập là tập con đúng của hàm an toàn luồng — chúng không tham chiếu dữ liệu chia sẻ nào, nên hiệu quả hơn mà không cần đồng bộ.1

Myth: the two terms are interchangeable.

Reality: reentrant functions are a proper subset of thread-safe ones — they reference no shared data at all, so they are more efficient and need no synchronization.1

Tự kiểm Self-check

Năm câu hỏi để biết bạn đã nắm lập trình đồng thời Năm câu hỏi kiểm tra nhanh Five questions to check you grasped concurrent programming

Trả lời được những câu này nghĩa là bạn đã hiểu ba cách dựng chương trình đồng thời và bài toán đồng bộ nằm ở trung tâm của chúng.

Nếu trả lời được, nghĩa là bạn đã hiểu chương này.

Answering these means you understood the three ways to build concurrent programs and the synchronization problem at their core.

  1. Kể ba cách dựng một chương trình đồng thời, và nêu một ưu, một nhược của mỗi cách.

    Gợi ý sâu hơn: vì sao luồng được coi là thể lai của tiến trình và dồn kênh I/O?

  2. Khi nào một biến trong chương trình đa luồng được coi là “chia sẻ”? Biến toàn cục và biến tự động cục bộ khác nhau thế nào về chuyện này?

    Gợi ý sâu hơn: thanh ghi và bộ nhớ ảo, cái nào luôn chia sẻ, cái nào không bao giờ?

  3. Vì sao badcnt.c cho kết quả sai và khác nhau mỗi lần? Dùng cờ hiệu sửa nó ra sao?

    Gợi ý sâu hơn: ba bước máy nào của cnt++ có thể bị đan xen không an toàn?

  4. Hai thao tác P và V làm gì? “Cờ hiệu nhị phân” hay “mutex” là gì?

    Gợi ý sâu hơn: bất biến cờ hiệu bảo đảm điều gì, và vì sao nó tạo ra vùng cấm?

  5. Trên hệ bốn lõi, vì sao tăng tốc của psum-local chững lại sau bốn luồng? Phân biệt tranh chấp và khoá chết.

    Gợi ý sâu hơn: quy tắc xếp thứ tự mutex giúp tránh khoá chết như thế nào?

  1. Kể ba cách để một chương trình làm nhiều việc cùng lúc.

  2. Biến “dùng chung” trong chương trình nhiều luồng là gì? Vì sao nó dễ sinh lỗi?

  3. Vì sao hai luồng cùng đếm lại ra kết quả sai? Cách sửa là gì?

  4. Cái “chìa khoá” (mutex) giúp gì cho dữ liệu dùng chung?

  5. Thêm nhiều luồng có luôn làm chương trình nhanh hơn không? Vì sao?

  1. Name the three ways to build a concurrent program, with one pro and one con of each.

  2. When is a variable in a threaded program “shared”? How do globals and local automatics differ here?

  3. Why does badcnt.c give wrong, run-to-run-different answers? How do semaphores fix it?

  4. What do the P and V operations do? What is a “binary semaphore” or “mutex”?

  5. On a four-core system, why does psum-local's speedup level off after four threads? Distinguish a race from a deadlock.

Khép lại chương Closing the chapter

Một chương trình đồng thời là tập các luồng điều khiển chồng lấn thời gian, dựng được bằng tiến trình, dồn kênh I/O, hoặc luồng; nhưng bất kể cơ chế nào, đồng bộ truy cập dữ liệu chia sẻ mới là bài toán khó cốt lõi — và cờ hiệu với hai phép P/V là công cụ kinh điển để giải nó đúng đắn.1

Máy có ba cách làm nhiều việc một lúc, nhưng chia sẻ dữ liệu cho đúng mới là phần khó. Hãy nhớ dùng khoá khi nhiều luồng động vào cùng một chỗ. Nhớ nhé: làm song song thì dễ, đồng bộ cho đúng mới là nghề.

A concurrent program is a set of control flows that overlap in time, buildable with processes, I/O multiplexing, or threads; but regardless of mechanism, synchronizing access to shared data is the hard, central problem — and the semaphore, with its P/V operations, is the classic tool for solving it correctly.1