Mở đầu
Việc đồng bộ hóa dữ liệu là một trong những thách thức quan trọng nhất khi phát triển hệ điều hành. Khi nhiều luồng thực thi hoặc ngắt có thể truy cập đồng thời vào cùng một vùng nhớ, chúng ta cần các cơ chế để đảm bảo tính toàn vẹn của dữ liệu. Trong thực tế, các kỹ thuật phổ biến bao gồm: biến nguyên tử, điều khiển ngắt, khóa quay và đèn hiệu.
I. Bài toán mẫu
Xem xét tình huống sau đây: một hàm xử lý ngắt và một hàm luồng cùng thực hiện thao tác tăng giá trị trên một biến toàn cục. Đoạn mã nguồn minh họa như sau:
int dem = 0;
void xu_ly_ngat() {
dem++;
}
void ham_luong() {
dem++;
}
Khi trình biên dịch xử lý lệnh dem++, nó thường phân tách thành ba lệnh assembly riêng biệt:
- Tải giá trị của
demvào thanh ghi - Tăng giá trị thanh ghi lên 1
- Ghi giá trị từ thanh ghi trở lại bộ nhớ
Vấn đề phát sinh khi luồng chính đang thực hiện lệnh thứ hai, ngắt xảy ra và hàm xử lý ngắt chiếm quyền CPU. Khi ngắt hoàn tất và CPU quay lại thực hiện tiếp, lệnh thứ ba của luồng chính sẽ ghi đè kết quả, dẫn đến mất dữ liệu.
Để giải quyết tình huống này, có hai hướng tiếp cận chính. Thứ nhất là biến thao tác dem++ thành một hoạt động nguyên tử, không thể chia cắt. Thứ hai là kiểm soát ngắt bằng cách tắt ngắt trước khi thực hiện và bật lại sau khi hoàn tất.
II. Hoạt động nguyên tử
Kiến trúc x86 cung cấp sẵn nhiều lệnh nguyên tử như atomic add, atomic subtract, atomic read và atomic write. Chúng ta có thể tận dụng các lệnh này bằng cách sử dụng inline assembly trong C.
Ngôn ngữ C hiện đại cho phép nhúng mã assembly thông qua cú pháp __asm__ __volatile__. Dưới đây là một triển khai hoàn chỉnh của kiểu dữ liệu nguyên tử:
// Cấu trúc biểu diễn biến nguyên tử
typedef struct {
volatile int gia_tri; // volatile ngăn trình biên dịch tối ưu hóa
} nguyen_tu_t;
// Đọc giá trị nguyên tử
static inline int doc_nguyen_tu(const nguyen_tu_t *v) {
return *(volatile int *)&v->gia_tri;
}
// Ghi giá trị nguyên tử
static inline void ghi_nguyen_tu(nguyen_tu_t *v, int gia_tri) {
v->gia_tri = gia_tri;
}
// Cộng nguyên tử một số nguyên
static inline void cong_nguyen_tu(int gia_tri, nguyen_tu_t *v) {
__asm__ __volatile__(
"lock; addl %1, %0"
: "+m" (v->gia_tri)
: "ir" (gia_tri)
);
}
// Trừ nguyên tử một số nguyên
static inline void tru_nguyen_tu(int gia_tri, nguyen_tu_t *v) {
__asm__ __volatile__(
"lock; subl %1, %0"
: "+m" (v->gia_tri)
: "ir" (gia_tri)
);
}
// Tăng 1 nguyên tử
static inline void tang_nguyen_tu(nguyen_tu_t *v) {
__asm__ __volatile__("lock; incl %0" : "+m" (v->gia_tri));
}
// Giảm 1 nguyên tử
static inline void giam_nguyen_tu(nguyen_tu_t *v) {
__asm__ __volatile__("lock; decl %0" : "+m" (v->gia_tri));
}
Tiền tố lock trong các lệnh addl, subl, incl, decl là yếu tố then chốt. Khi được sử dụng, tiền tố này khóa bus dữ liệu, ngăn các CPU khác thay đổi giá trị tại địa chỉ bộ nhớ đang được thao tác. Điều này đảm bảo tính nguyên tử của lệnh.
Cú pháp nhúng assembly của GCC bao gồm bốn thành phần chính: mã assembly thực tế, danh sách đầu ra cho phép GCC xử lý biến C trong assembly, danh sách đầu vào để đưa giá trị C vào assembly, và danh sách hư hỏng để thông báo cho GCC về các thanh ghi bị ảnh hưởng.
Xem xét hàm cong_nguyen_tu làm ví dụ: phần lock; addl %1, %0 là mã assembly với các placeholder %0 và %1. Phần :+m" (v->gia_tri) khai báo đầu ra liên kết với bộ nhớ, còn phần : "ir" (gia_tri) khai báo đầu vào là số nguyên hoặc thanh ghi.
Sau khi có các hàm nguyên tử, đoạn mã nguồn ban đầu trở nên an toàn bất kể ngắt xảy ra ở thời điểm nào:
nguyen_tu_t dem = {0};
void xu_ly_ngat() {
tang_nguyen_tu(&dem);
}
void ham_luong() {
tang_nguyen_tu(&dem);
}
III. Điều khiển ngắt
Hoạt động nguyên tử phù hợp với các biến đơn lẻ như số nguyên. Tuy nhiên, cấu trúc dữ liệu của hệ điều hành thường phức tạp hơn nhiều, đòi hỏi cơ chế bảo vệ khác.
Trên kiến trúc x86, hai lệnh cli và sti được sử dụng để tắt và bật ngắt tương ứng. Chúng tác động trực tiếp vào bit IF (bit 9) của thanh ghi EFLAGS, quyết định liệu CPU có phản hồi tín hiệu ngắt hay không. Các lệnh này yêu cầu quyền Ring0 để thực thi.
Để xử lý đúng trong các hàm lồng nhau, chúng ta cần lưu và khôi phục trạng thái EFLAGS thay vì đơn giản bật hoặc tắt ngắt:
typedef unsigned int trang_thai_cpu;
// Lưu trạng thái và tắt ngắt
static inline void luu_trang_thai_tat_ngat(trang_thai_cpu *tt) {
__asm__ __volatile__(
"pushfl \n\t"
"cli \n\t"
"popl %0"
: "=m"(*tt)
:
: "memory"
);
}
// Khôi phục trạng thái và bật ngắt
static inline void khoi_phuc_trang_thai_bat_ngat(trang_thai_cpu *tt) {
__asm__ __volatile__(
"pushl %0 \n\t"
"popfl"
:
: "m"(*tt)
: "memory"
);
}
Lệnh pushfl đẩy giá trị EFLAGS vào stack, popfl khôi phục từ stack. Cách tiếp cận này đảm bảo rằng trạng thái ngắt được khôi phục chính xác như trước khi hàm được gọi, bất kể mức lồng ghép.
IV. Khóa quay
Cơ chế điều khiển ngắt chỉ hiệu quả với hệ thống đơn lõi. Với CPU đa lõi, ngắt từ một lõi khác vẫn có thể truy cập tài nguyên được bảo vệ, đòi hỏi cơ chế đồng bộ hóa mạnh mẽ hơn.
Khóa quay hoạt động dựa trên nguyên tắc: đọc biến khóa, nếu chưa khóa thì thực hiện khóa và trả về thành công; nếu đã khóa thì tiếp tục vòng lặp kiểm tra, do đó có tên gọi "quay" (spin). Để thuật toán hoạt động chính xác, các thao tác đọc, kiểm tra và khóa phải được thực hiện nguyên tử.
Kiến trúc x86 cung cấp lệnh xchg (exchange) cho phép hoán đổi giữa thanh ghi và vùng nhớ một cách nguyên tử. Lệnh này không bị gián đoạn bởi các CPU khác, là nền tảng cho việc triển khai khóa quay:
// Cấu trúc khóa quay
typedef struct {
volatile unsigned int trang_thai_khoa;
} khoa_quay_t;
// Khởi tạo khóa
static inline void khoi_khoa_quay(khoa_quay_t *khoa) {
khoa->trang_thai_khoa = 0;
}
// Thao tác khóa
static inline void khoa_quay_han che_ngat(khoa_quay_t *khoa, trang_thai_cpu *tt) {
__asm__ __volatile__(
"pushfq \n\t"
"cli \n\t"
"popq %0 \n\t"
"1: \n\t"
"lock; xchg %1, %2 \n\t"
"cmp $0, %1 \n\t"
"jne 2f \n\t"
"jmp 3f \n\t"
"2: \n\t"
"cmp $0, %2 \n\t"
"jne 2b \n\t"
"jmp 1b \n\t"
"3: \n\t"
: "=m"(*tt)
: "r"(1), "m"(*khoa)
);
}
// Thao tác mở khóa
static inline void mo_khoa_quay_bat_ngat(khoa_quay_t *khoa, trang_thai_cpu *tt) {
__asm__ __volatile__(
"mov $0, %0 \n\t"
"pushq %1 \n\t"
"popfq \n\t"
:
: "m"(*khoa), "m"(*tt)
);
}
Trong đoạn mã trên, xchg %1, %2 hoán đổi giá trị 1 từ thanh ghi với giá trị tại địa chỉ bộ nhớ. Nếu bộ nhớ chứa 0, sau hoán đổi nó sẽ chứa 1 (khóa thành công). Vòng lặp kiểm tra liên tục cho đến khi khóa được giải phóng, đảm bảo tính nguyên tử.
V. Đèn hiệu
Ba cơ chế trên không phù hợp với tình huống chờ đợi kéo dài. Khi tài nguyên không sẵn sàng ngay lập tức, việc liên tục kiểm tra (như trong khóa quay) gây lãng phí CPU. Đèn hiệu giải quyết vấn đề này bằng cách cho phép CPU chuyển sang tác vụ khác trong khi chờ.
Quy trình sử dụng đèn hiệu bao gồm ba bước chính. Đầu tiên, tiến hành yêu cầu đèn hiệu bằng cách khóa khóa quay bảo vệ chính nó, giảm biến đếm và kiểm tra. Nếu biến đếm nhỏ hơn 0, luồng được đưa vào danh sách chờ và lên lịch thực thi luồng khác. Ngược lại, đèn hiệu được coi là đã sở hữu thành công.
Tiếp theo, luồng thực hiện các thao tác trên tài nguyên được bảo vệ. Cuối cùng, giải phóng đèn hiệu bằng cách khóa khóa quay, tăng biến đếm và kiểm tra. Nếu giá trị lớn hơn 0, tiến hành đánh thức các luồng đang chờ.
Triển khai chi tiết như sau:
// Cấu trúc đèn hiệu
typedef struct {
khoa_quay_t khoa_bao_ve;
int so_luong;
danh_sach_cho danh_sach_cho;
} den_hieu_t;
// Yêu cầu đèn hiệu
void yeu_cau_den_hieu(den_hieu_t *dh) {
trang_thai_cpu trang_thai;
buoc_lap:
khoa_quay_han_che_ngat(&dh->khoa_bao_ve, &trang_thai);
if (dh->so_luong < 1) {
// Đưa luồng vào danh sách chờ
them_vao_cho(&dh->danhsach_cho);
khoa_quay_mo(&dh->khoa_bao_ve, &trang_thai);
chuyen_luong(); // Lên lịch luồng khác
goto buoc_lap; // Khi được đánh thức, thử lại
}
dh->so_luong--;
khoa_quay_mo(&dh->khoa_bao_ve, &trang_thai);
}
// Giải phóng đèn hiệu
void giai_phong_den_hieu(den_hieu_t *dh) {
trang_thai_cpu trang_thai;
khoa_quay_han_che_ngat(&dh->khoa_bao_ve, &trang_thai);
dh->so_luong++;
if (dh->so_luong < 1) {
// Lỗi cấu trúc dữ liệu
khoa_quay_mo(&dh->khoa_bao_ve, &trang_thai);
treo_he_thong("Loi giai phong den hieu");
}
// Đánh thức tất cả luồng đang chờ
thuc_tat_ca_cho(&dh->danhsach_cho);
khoa_quay_mo(&dh->khoa_bao_ve, &trang_thai);
kiem_tra_lap_lich();
}
Đèn hiệu hoạt động theo mô hình "nhiều người dùng, dùng xong trả lại". Các tiến trình cạnh tranh để sở hữu đèn hiệu; tiến trình không đạt được sẽ vào danh sách chờ, giải phóng CPU cho tác vụ khác. Sau khi hoàn tất, tiến trình giải phóng đèn hiệu và đánh thức các tiến trình đang chờ để chúng tiếp tục cạnh tranh.
Kết luận, việc lựa chọn cơ chế đồng bộ hóa phù hợp phụ thuộc vào đặc điểm của tình huống sử dụng: hoạt động nguyên tử cho các biến đơn giản, điều khiển ngắt cho vùng quan trọng trên hệ thống đơn lõi, khóa quay cho thời gian chờ ngắn trên hệ thống đa lõi, và đèn hiệu cho thời gian chờ dài với nhiều tiến trình.