Ексклюзивний доступ 2

Вивчивши протоколи взаємного виключення на минулорічному конкурсі, ви тепер стикаєтеся з більш складною проблемою. У вас є велика корпоративна система з кількома одночасно працюючими процесами. Система містить кілька різних ресурсів — бази даних, черги повідомлень тощо. Кожен процес одночасно працює з двома ресурсами. Наприклад, один процес може переміщати завдання з певної бази даних у чергу повідомлень, інший процес може брати завдання з черги повідомлень, виконувати його і розміщати результат в іншу чергу повідомлень тощо.

Всі ресурси захищені від одночасного доступу протоколами взаємного виключення, також відомими як блокування. Наприклад, щоб отримати доступ до певної бази даних, процес отримує блокування цієї бази, виконує свою роботу і потім звільняє блокування. Жодні два процеси не можуть одночасно володіти одним і тим самим блокуванням (це властивість взаємного виключення). Отже, процес, який намагається отримати блокування, очікує, якщо це блокування вже зайняте іншим процесом.

Головний цикл процесу, який працює з ресурсами P та Q, виглядає наступним чином:

loop forever
    DoSomeNonCriticalWork()
    P.lock()
    Q.lock()
    WorkWithResourcesPandQ()
    Q.unlock()
    P.unlock()
end loop

Порядок, у якому отримуються блокування для ресурсів P та Q, є важливим. Нехай процес c отримав блокування P за допомогою P.lock() і очікує блокування Q у Q.lock(). Це означає, що блокування Q отримане іншим процесом d. Якщо процес d працює (не очікує), то існує ланцюг очікування довжиною $1$. Якщо d отримав блокування Q і тепер очікує ще одне блокування R, яке отримане працюючим процесом e, то ланцюг очікування має довжину $2$, і так далі. Якщо якийсь процес у цьому ланцюгу очікування очікує блокування P, яке вже отримане процесом c, то ланцюг очікування має нескінченну довжину, і система переходить у стан взаємоблокування (deadlock).

У цій задачі нас цікавлять лише чергуючі ланцюги очікування, коли процеси володіють своїми першими блокуваннями і очікують других. Формально:

Чергуючий ланцюг очікування довжини $n$ (n \ge 0) — це чергуюча послідовність ресурсів R_i (0 \le i \le n+1) і різних процесів c_i (0 \le i \le n): R_0\ c_0\ R_1\ c_1\ \dots R_n\ c_n\ R_{n+1}, де процес c_i отримує блокування для ресурсів R_i та R_{i+1} саме в такому порядку. Чергуючий ланцюг очікування є deadlock-ом, коли R_0 = R_{n+1}.

Вам дано набір ресурсів, з якими працює кожен процес. Ваше завдання — визначити порядок, у якому кожен процес має отримувати блокування для своїх ресурсів так, щоб система ніколи не переходила у стан deadlock, а також мінімізувати максимальну можливу довжину будь-якого чергуючого ланцюга очікування.