Eksklüziv Giriş 2

Keçən il qarşılıqlı istisna protokollarını öyrəndikdən sonra indi daha çətin bir problemlə qarşılaşırsınız. Böyük bir müəssisə sisteminiz var və burada bir neçə paralel proses işləyir. Sistem bir neçə müxtəlif resursdan ibarətdir — verilənlər bazaları, mesaj növbələri və s. Hər bir paralel proses eyni anda iki resursla işləyir. Məsələn, bir proses müəyyən bir verilənlər bazasından işi mesaj növbəsinə köçürə bilər, başqa bir proses isə mesaj növbəsindən işi götürüb, işi icra edib nəticəni başqa bir mesaj növbəsinə yerləşdirə bilər və s.

Bütün resurslar qarşılıqlı istisna protokolları, başqa sözlə locklar vasitəsilə paralel girişdən qorunur. Məsələn, müəyyən bir verilənlər bazasına daxil olmaq üçün proses həmin verilənlər bazasının kilidini (lock) əldə edir, işi yerinə yetirir və sonra kilidi azad edir. Eyni anda iki proses eyni kilidi tuta bilməz (bu, qarşılıqlı istisna xüsusiyyətidir). Buna görə, bir proses nə vaxtsa bir kilidi əldə etməyə çalışarsa və bu kilid başqa bir proses tərəfindən tutulubsa, o, gözləyir.

Resurslarla P və Q işləyən bir prosesin əsas döngüsü aşağıdakı kimidir:

"' loop forever

DoSomeNonCriticalWork()

P.lock()

Q.lock()

WorkWithResourcesPandQ()

Q.unlock()

P.unlock()

end loop "'

Resursların kilidlərinin əldə edilməsi ardıcıllığı vacibdir. Tutaq ki, c prosesi P.lock() üzərindən P kilidini əldə edib və indi Q.lock() əməliyyatında Q kilidini gözləyir. Bu o deməkdir ki, Q kilidi başqa bir d prosesi tərəfindən tutulub. Əgər d prosesi işləyirsə (gözləmirsə), bu zaman gözləmə zəncirinin uzunluğu $1$-ə bərabərdir. Əgər d artıq Q kilidini əldə edib, indi başqa bir R kilidini gözləyirsə və bu R kilidi işləyən e prosesindədirsə, bu zaman gözləmə zənciri $2$ uzunluqdadır və s. Əgər bu gözləmə zəncirində hər hansı bir proses c tərəfindən artıq tutulmuş olan P kilidini gözləyirsə, gözləmə zənciri sonsuz olur və sistem deadlock vəziyyətinə düşür.

Bu məsələdə biz yalnız birinci kilidlərini tutan və ikinci kilidi gözləyən proseslərin yaranan ardıcıllıqlarını — yəni alternativ gözləmə zənciri adlandırılan zəncirləri nəzərə alırıq. Formal tərifi belədir:

Uzunluğu $n$ (n \ge 0) olan alternativ gözləmə zənciri R_i (0 \le i \le n+1) resursları və müxtəlif c_i (0 \le i \le n) proseslərindən ibarət növbə ilə düzülmüş ardıcıllıqdır: R_0\ c_0\ R_1\ c_1\ \dots R_n\ c_n\ R_{n+1}, burada hər c_i prosesi R_i və R_{i+1} resurslarının kilidini bu ardıcıllıqla əldə edir. Alternativ gözləmə zənciri, R_0 = R_{n+1} olarsa, deadlock vəziyyəti sayılır.

Sizə hər bir prosesin işlədiyi resursların cütləri verilir. Tapşırığınız — hər proses üçün resursların kilidlərinin hansı ardıcıllıqla əldə edilməli olduğunu müəyyən etməkdir ki, sistemdə heç vaxt deadlock olmasın və ən uzun alternativ gözləmə zəncirinin uzunluğu mümkün olan ən az qiymətə bərabər olsun.