Bài 45.326 phút đọc
Deadlock và cách tránh
Sau bài này bạn sẽ làm được
- Tạo deadlock có chủ ý và giải thích bốn điều kiện
- Sửa bằng cách khoá theo cùng thứ tự
- Kể các cách phòng tránh khác
- Chẩn đoán deadlock bằng gdb
Mutex giải quyết race condition, nhưng tạo ra một vấn đề mới: hai luồng chờ nhau mãi mãi. Đó là deadlock, và nó gây treo hoàn toàn. Bài này tạo một deadlock, giải thích vì sao, rồi phá vỡ nó bằng một quy tắc đơn giản.
#Deadlock
dl.c, deadlock có chủ ý
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
static pthread_mutex_t m1 = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;
static void *t1(void *a) {
(void)a;
pthread_mutex_lock(&m1); printf("t1 giu m1\n"); usleep(100000);
printf("t1 cho m2...\n"); pthread_mutex_lock(&m2); /* cho m2 */
pthread_mutex_unlock(&m2); pthread_mutex_unlock(&m1);
return NULL;
}
static void *t2(void *a) {
(void)a;
pthread_mutex_lock(&m2); printf("t2 giu m2\n"); usleep(100000);
printf("t2 cho m1...\n"); pthread_mutex_lock(&m1); /* cho m1 */
pthread_mutex_unlock(&m1); pthread_mutex_unlock(&m2);
return NULL;
}
int main(void) {
pthread_t a, b;
pthread_create(&a, NULL, t1, NULL);
pthread_create(&b, NULL, t2, NULL);
pthread_join(a, NULL);
pthread_join(b, NULL);
printf("xong\n");
return 0;
}terminal
gcc -O2 -pthread dl.c -o dl.exe
# Chay voi timeout 3 giay: chuong trinh TREO
timeout 3 ./dl.exe
t1 giu m1 t2 giu m2 t1 cho m2... t2 cho m1...
echo $?
124
#Bốn điều kiện Coffman
Deadlock
Tình trạng mà hai hay nhiều luồng chờ nhau mãi mãi, không luồng nào tiếp tục được. Xảy ra khi và chỉ khi cả bốn điều kiện Coffman cùng đúng. Phá vỡ bất kỳ một điều kiện là ngăn được deadlock.
| # | Điều kiện | Trong ví dụ |
|---|---|---|
| 1 | Loại trừ lẫn nhau: tài nguyên không chia sẻ được | Mutex chỉ một luồng giữ |
| 2 | Giữ và chờ: giữ cái này, chờ cái khác | t1 giữ m1, chờ m2 |
| 3 | Không tước đoạt: không cưỡng chế lấy lại được | Không ai giật mutex của luồng khác |
| 4 | Chờ vòng tròn: A chờ B, B chờ A | t1 chờ m2 (t2 giữ), t2 chờ m1 (t1 giữ) |
#Sửa: cùng thứ tự
Khoá ngược thứ tự
void *t1(void *a) {
pthread_mutex_lock(&m1); /* t1: m1 truoc */
pthread_mutex_lock(&m2); /* m2 sau */
...
}
void *t2(void *a) {
pthread_mutex_lock(&m2); /* t2: m2 truoc <- NGUOC */
pthread_mutex_lock(&m1); /* m1 sau */
...
}
/* t1 giu m1 cho m2, t2 giu m2 cho m1 -> cho vong tron -> deadlock */
Khoá cùng thứ tự
void *t1(void *a) {
pthread_mutex_lock(&m1); /* m1 truoc */
pthread_mutex_lock(&m2); /* m2 sau */
...
}
void *t2(void *a) {
pthread_mutex_lock(&m1); /* m1 truoc <- CUNG thu tu */
pthread_mutex_lock(&m2); /* m2 sau */
...
}
/* Ca hai luong luon khoa m1 truoc m2. Neu t1 giu m1, t2 phai cho
m1 truoc khi cham m2, nen khong co vong tron. Khong deadlock. */
#Cách phòng tránh khác
| Cách | Phá điều kiện | Đánh đổi |
|---|---|---|
| Khoá cùng thứ tự | Chờ vòng tròn | Phải biết mọi thứ tự trước, đơn giản nhất |
| trylock rồi lùi | Giữ và chờ | Nếu không lấy được cái thứ hai, thả cái đầu và thử lại |
| Đặt thời gian chờ | Giữ và chờ | pthread_mutex_timedlock, bỏ cuộc sau timeout |
| Chỉ dùng một khoá | Chờ vòng tròn | Đơn giản nhưng giảm song song |
trylock rồi lùi
/* Neu khong the bao dam thu tu (thu tu khoa tuy luc chay), dung
trylock: lay cai dau, THU lay cai sau; neu that bai, THA cai
dau va thu lai tu dau. */
for (;;) {
pthread_mutex_lock(&m1);
if (pthread_mutex_trylock(&m2) == 0)
break; /* lay duoc ca hai, tiep tuc */
pthread_mutex_unlock(&m1); /* khong lay duoc m2 -> tha m1 */
/* thu lai, co the them mot luong nghi ngau nhien de tranh
hai luong cu tha va thu mai (livelock) */
}
/* ... vung toi han ... */
pthread_mutex_unlock(&m2);
pthread_mutex_unlock(&m1);
/* trylock pha dieu kien "giu va cho": luong khong GIU m1 trong
khi CHO m2. Neu khong lay duoc m2 ngay, no tha m1 luon. Nen
khong co vong tron.
Nhuoc diem: co the "livelock" (hai luong cu tha va thu qua lai
ma khong ai tien) neu khong them yeu to ngau nhien. */#Chẩn đoán bằng gdb
terminal
# Chuong trinh treo. Gan gdb vao xem no ket o dau
gdb -p $(pgrep dl)
(gdb)
info threads
Id Target Id Frame * 1 Thread ... main pthread_join 2 Thread ... t1 __lll_lock_wait <- dang cho khoa 3 Thread ... t2 __lll_lock_wait <- dang cho khoa
thread apply all bt
Thread 3 (t2): #0 __lll_lock_wait #1 pthread_mutex_lock (m1) <- t2 cho m1 #2 t2 at dl.c:17 Thread 2 (t1): #0 __lll_lock_wait #1 pthread_mutex_lock (m2) <- t1 cho m2 #2 t1 at dl.c:10
Tự làm thử
- Chạy
dl.cvà xác nhận nó treo với mã thoát timeout. - Sửa bằng cách khoá cùng thứ tự và xác nhận nó chạy xong.
- Viết hàm chuyển tiền giữa hai tài khoản với lock hierarchy theo địa chỉ.
- Cài
trylockrồi lùi và giải thích nó phá điều kiện nào. - Gắn
gdbvào một chương trình deadlock và dùngthread apply all bttìm chỗ kẹt. - Kể bốn điều kiện Coffman và với mỗi cách phòng tránh, nói nó phá điều kiện nào.
Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.
Tóm tắt
- Deadlock: hai luồng chờ nhau mãi; chương trình treo hoàn toàn, không cần sanitizer để thấy.
- Xảy ra khi cả bốn điều kiện Coffman cùng đúng; phá một là đủ ngăn.
- Cách phổ biến nhất: luôn khoá theo cùng thứ tự, phá vỡ chờ vòng tròn.
- Lock hierarchy đánh số khoá và khoá tăng dần;
trylockrồi lùi phá điều kiện giữ và chờ. gdbvớiinfo threadsvàbtchỉ ra chỗ kẹt; TSan bắt race chứ không bắt deadlock.