Quartz 🪬

Dekker's Algorithm

2 min read

Thuật toán Dekker là một thuật toán giúp đồng bộ hóa tiến trình (Synchronization).

Giả sử có hai tiến trình và đang tranh chấp tài nguyên.

Dùng một biến turn cho biết tiến trình nào được phép vào critical section (CS). Khởi tạo giá trị ban đầu là 0:

int turn = 0; // shared data

Nếu turn = i thì tiến trình sẽ được phép tiến vào CS. Ngược lại, tiến trình đó sẽ phải chờ. Sau khi thoát khỏi CS thì phải gán lại giá trị turn cho tiến trình khác.

Đoạn code triển khai thuật toán Dekker cho P0:

// Process P0
do {
	while(turn != 0);
	// critical section
	turn = 1;
	// remainer section
} while(1);

Đoạn code triển khai thuật toán Dekker cho P1:

// Process P1
do {
	while(turn != 1);
	// critical section
	turn = 0;
	// remainer section
} while(1);

Giải pháp này thỏa mãn điều kiện mutual exclusion nhưng lại không thỏa điều kiện progress (xem thêm Synchronization).

Giả sử hoàn thành CS, gán lại turn = 1 và tiến vào RS nhưng lại ở luôn trong đó. Tiến trình khi vào được CS, gán lại turn = 0 và hoàn thành RS thì sẽ không thể tiếp tục truy cập CS một lần nữa do turn = 0 và tiến trình vẫn còn đang ngủ rất say sưa ở trong RS.

Nói cách khác, một tiến trình cần phải chờ tiến trình khác gán lại giá trị turn thì nó mới có thể truy cập CS. Trong trường hợp này, chờ nhưng không phản hồi mặc dù không nằm ở bên trong CS, điều này dẫn đến việc vi phạm điều kiện progress.

Later later

Backlinks