Quartz 🪬

Peterson's Algorithm

3 min read

Thuật toán này tương tự như thuật toán Dekker (Dekker’s Algorithm) nhưng cần sử dụng thêm một mảng interest để lưu mong muốn truy cập vào CS của các tiến trình.

Xét tiến trình i, các bước triển khai giải pháp như sau:

  1. Khởi tạo các biến chia sẻ (turn và interest).
  2. Tiến trình thể hiện mong muốn truy cập vào CS của nó bằng cách gán interest[i] = true và đồng thời trao cho tiến trình j khác một cơ hội để có thể truy cập CS.
  3. Nếu tiến trình j có mong muốn truy cập CS (interest[j] = true) và biến turn = j thì tiến trình i sẽ cần phải chờ đến khi nào một trong hai điều kiện này có giá trị là false.
  4. Sau khi vào CS và thoát ra khỏi CS, tiến trình i cần phải gán lại interest[i] = false cho biết rằng nó không còn muốn truy cập vào CS nữa.

Giả sử có hai tiến trình là P0 và P1. Khai báo hai biến chia sẻ turn và interest:

int turn = 0;
bool interest[2] = [false, false];

Xét đoạn code triển khai giải pháp Peterson của tiến trình P0:

do {
	interest[0] = true; // P0 wants in
	turn = 1; // P0 gives a chance to P1
 
	while (interest[1] && turn == 1) // Wait if P1 wants to enter the critical section and it's not my turn
	{
		// busy waiting
	}
 
	// critical section
	// ...
	// end critical section
 
	interest[0] = false; // P0 no longer wants in
 
	// remainder section
} while(1);

Có các trường hợp sau, với điều kiện là interest[0] = true:

  1. Nếu interest[1] = true và turn = 1: tiến trình P0 cần phải chờ, tiến trình P1 được phép truy cập vào CS.
  2. Nếu interest[1] = true và turn = 0: tiến trình P0 được phép truy cập vào CS, tiến trình P1 cần phải chờ.
  3. Nếu interest[1] = false và turn = 0: tiến trình P0 được phép truy cập vào CS.
  4. Nếu interest[1] = false và turn = 1: tiến trình P0 được phép truy cập vào CS.

Có thể thấy ở trường hợp 4, mặc dù không phải lượt của tiến trình P0 nhưng nếu P1 không muốn vào CS thì P0 vẫn có thể truy cập vào CS. Cách làm này giải quyết được vấn đề của thuật toán Dekker.

Nói cách khác, nếu một tiến trình có nhu cầu vào CS thì nó sẽ không bị ngăn cản bởi các tiến trình khác đang ở trong RS.

Backlinks