0.4 Điều khiển cạnh tranh  (Page 12/13)

Sơ đồ phòng ngừa deadlock khác là áp đặt một thứ tự bộ phận trên tất cả các hạng mục dữ liệu và yêu cầu một giao dịch chốt một hạng mục dữ liệu theo thứ tự được xác định bởi thứ tự bộ phận này.

Cách tiếp cận thứ hai để phòng ngừa deadlock là sử dụng ưu tiên và cuộn lại quá trình. Với ưu tiên, một giao dịch T2 yêu cầu một chốt bị giữ bởi giao dịch T1 , chốt đã cấp cho T1 có thể bị lấy lại và cấp chgo T2 , T1 bị cuộn lại. Để điều khiển ưu tiên, ta gán một tem thời gian duy nhất cho mỗi giao dịch. Hệ thống sử dụng các tem thời gian này để quyết định một giao dịch phải chờ hay cuộn lại. Việc chốt vẫn được sử dụng để điều khiển cạnh tranh. Nếu một giao dịch bị cuộn lại, nó vẫn giữ tem thời gian cũ của nó khi tái khởi động. Hai sơ đồ phòng ngừa deadlock sử dụng tem thời gian khác nhau được đề nghị:

1. Sơ đồ Wait-Die dựa trên kỹ thuật không ưu tiên. Khi giao dịch Ti yêu cầu một hạng mục dữ liệu bị chiếm bởi Tj , Ti được phép chờ chỉ nếu nó có tem thời gian nhỏ hơn của Tj nếu không Ti bị cuộn lại (die).
2. Sơ đồ Wound-Wait dựa trên kỹ thuật ưu tiên. Khi giao dịch Ti yêu cầu một hạng mục dữ liệu hiện đang bị giữ bởi Tj , Ti được phép chờ chỉ nếu nó có tem thời gian lớn hơn của Tj , nếu không Tj bị cuộn lại (Wounded).

Một điều quan trọng là phải đảm bảo rằng, mỗi khi giao dịch bị cuộn lại, nó không bị chết đói (starvation) có nghĩa là nó sẽ không bị cuộn lại lần nữa và được phép tiến triển.

Cả hai sơ đồ Wound-Wait và Wait-Die đều tránh được sự chết đói: tại một thời điểm, có một giao dịch với tem thời gian nhỏ nhất. Giao dịch này không thể bị yêu cầu cuộn lại trong cả hai sơ đồ. Do tem thời gian luôn tăng và do các giao dịch không được gán tem thời gian mới khi chúng bị cuộn lại, một giao dịch bị cuộn lại sẽ có tem thời gian nhỏ nhất (vào thời gian sau) và sẽ không bị cuộn lại lần nữa.

Tuy nhiên, có những khác nhau lớn trong cách thức hoạt động của hai sơ đồ:

• Trong sơ đồ Wait-Die, một giao dịch già hơn phải chờ một giao dịch trẻ hơn giải phóng hạng mục dữ liệu. Như vậy, giao dịch già hơn có xu hướng bị chờ nhiều hơn. Ngược lại, trong sơ đồ Wound-Wait, một giao dịch già hơn không bao giờ phải chờ một giao dịch trẻ hơn.
• Trong sơ đồ Wait-Die, nếu một giao dịch Ti chết và bị cuộn lại vì nó đòi hỏi một hạng mục dữ liệu bị giữ bởi giao dịch Tj , khi đó Ti có thể phải tái phát ra cùng dãy các yêu cầu khi nó khởi động lại. Nếu hạng mục dữ liệu vẫn bị chiếm bởi Tj , Ti bị chết lần nữa. Như vậy, Ti có thể bị chết vài lần trước khi tậu được hạng mục dữ liệu cần thiết. Trong sơ đồ Wound-Wait, Giao dịch Ti bị thương và bị cuộn lại do Tj yêu cầu hạng mục dữ liệu nó chiếm giữ. Khi Ti khởi động lại, và yêu cầu hạng mục dữ liệu, bây giờ, đang bị Tj giữ, Ti chờ. Như vậy, có ít cuộn lại hơn trong sơ đồ Wound-Wait.

Một vấn đề nổi trội đối với cả hai sơ đồ là có những cuộn lại không cần thiết vẫn xảy ra.

Sơ đồ dựa trên timeout

Một cách tiếp cận khác để quản lý deadlock được dựa trên lock timeout. Trong cách tiếp cận này, một giao dịch đã yêu cầu một chốt phải chờ nhiều nhất một khoảng thời gian xác định. Nếu chốt không được cấp trong khoảng thời gian này, giao dịch được gọi là mãn kỳ (time out), giao dịch tự cuộn lại và khởi động lại. Nếu có một deadlock, một hoặc một vài giao dịch dính líu đến deadlock sẽ time out và cuộn lại, để các giao dịch khác tiến triển. Sơ đồ này nằm trung gian giữa phòng ngừa deadlock và phát hiện và khôi phục deadlock.