Iston respublikasi axborot texnologiyalari va aloqlalarini rivojlanish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

Klassik misol - Dijkstraning o'zaro istisnosi
O'z-o'zini barqarorlashtiruvchi algoritmlarning eng aniq va eng yorqin misollaridan biri allaqachon klassik, Dijkstra tomonidan nashr etilgan n jarayonlar halqasida o'zaro istisno
1974 yilda. Mahalliy shtatlarning K soni sonidan kam bo'lmasligini talab qiladi jarayonlar.
Dijkstra imtiyoz tushunchasini kiritdi. Imtiyoz berilgan narsaga ruxsat beradi harakatni amalga oshirish jarayoni (ya'ni, uning mahalliy holatini o'zgartirish, muhim bo'limga kiring). Qonuniy (global) tizim holati quyidagi xususiyatlarga javob berishi kerak:
1. Tizimda kamida bitta imtiyoz bo'lishi kerak.
2. Cheksiz vaqt davomida har bir jarayon cheksiz ko'p marta imtiyoz olishi kerak.
Ringda bitta alohida jarayon P0 mavjud. U teng va bir xil harakat qiladigan boshqa n-1 (P1 - Pn-1) jarayonlaridan farqli qoidalarga amal qiladi. Berilgan jarayonning joriy mahalliy holati Pi l i holat o‘zgaruvchisi bilan ifodalanadi. Algoritm halqadagi har bir jarayonga chap qo'shnisining holat o'zgaruvchisining qiymatini bilish imkonini beradigan har qanday aloqa modelini nazarda tutadi (1≤i≤n-1 uchun l i-1 va P0 uchun ln-1), masalan. umumiy o'zgaruvchilar aloqa modeli*) (link-registrlar).
Mana Dijkstra algoritmi:

1-rasmda K=3 bo‘lgan 3 ta jarayondan iborat halqada ushbu algoritmning namunali bajarilishi ko‘rsatilgan. E'tibor bering, taxmin qilingan dastlabki holat tufayli uchala jarayon ham imtiyozga ega bo'ladi (P0 jarayoni l0 = ln-1 shartini qondiradi, P1 jarayoni: l1 ≠ l0 va P2 jarayoni: l2 ≠ l1), shuning uchun har uchalasi ham o'zlarining muhim bo'limlariga kiradi va 1-bosqichda ularning holatini o'zgartirish. Bu global davlat, shubhasiz, o'zaro istisno nuqtai nazaridan qonuniy emas. Keyin, yana bir bor, ularning barchasi imtiyozga ega bo'ladi - 2-bosqichga (boshqa noqonuniy global davlat) olib keladi. Endi l0 = ln-1 sharti buzilgan - P0 jarayoni o'zining kritik qismiga kira olmaydi, lekin P1 va P2 hali ham mumkin (shuning uchun faqat P1 va P2 3-bosqichda o'z holatini o'zgartiradi; yangi davlat hali ham noqonuniy). 3-bosqichdan keyin konfiguratsiyada faqat P2 imtiyozga ega - tizim bir qator huquqiy holatlarga yaqinlashdi. Bundan buyon faqat bitta jarayon imtiyozga ega bo'ladi. Imtiyoz ringda soat yo'nalishi bo'yicha aylanadi - masalan. 4-bosqichda: P1 dan P2 gacha, keyingi P2 dan P0 gacha va hokazo.
Ko'rinib turibdiki, ushbu algoritm O(n2) erishishdan oldin tizim qadamlari
huquqiy global davlat. Mumkin bo'lgan mahalliy shtatlarning kerakli soni K halqa o'lchamiga bog'liq va munosabatni qondirishi kerak: K≥n