Банкирын алгоритм

Нөөц хуваарилах графын алгоритмыг төрөл бүрийн нөөцийн олон тохиолдлуудтай нөөц хуваарилах системд ашиглах тийм ч тохиромжтой биш. Харин түгжрэлээс зайлсхийх алгоритм нь иймэрхүү системд тохиромжтой. Гэвч нөөц хуваарилах графын системээс үр дүн багатай бөгөөд энэ алгоритмыг өөрөөр “Банкирын алгоритм” гэж нэрлэдэг. Нөөц хуваарилах Банкирын алгоритм нь түгжрэлээс зайлсхийхэд хэрэглэгддэг. Энэ нэрийг сонгосон шалтгаан гэвэл банк нь боломжит бэлэн мөнгөөр бүх хэрэглэгчдийнхээ шаардлагыг хангаж чаддаггүй учраас төсвийг хангахын тулд банкны эрэлтийн системд ашигладаг. Системд шинэ процесс орж ирэхэд хэрэгцээтэй төрөл бүрийн нөөцийн тохиолдлуудын хамгийн их тоог зарлах ёстой. Энэ тоо нь систем дэх нөөцүүдийн нийт тоог хэтрүүлэхгүй. Хэрэглэгч нөөцүүдийн тохиргоонд хүсэлт гаргахад систем эдгээр нөөцүүдийн хуваарилалтыг чиглүүлж аюулгүй төлөвт системийг орхино. Төсөвт нөөцлөгдсөн бол процесс хангалттай нөөц зарим процессоос чөлөөлөх хүртэл хүлээдэг.

Хэрэв биелбэл нөөц зарцуулагддаг, эсрэг тохиолдолд процесс өөр процесс хангалттай нөөц хэвлэхийг зөвшөөрөхийг хүлээх шаардлагатай. Төрөл бүрийн өгөгдлийн бүтцүүд банкирын алгоритмыг хэрэгжүүлэхийг дэмждэг. Энэ өгөгдлийн бүтцүүд нь нөөц зарцуулалтын системийн мужийг кодоор шифрлэдэг (кодлодог). Систем дэх процессын тоог n, нөөцийн төрлийн тоог m гэж тэмдэглэе.

• Available (Боломжит). А векторын m урт нь нөөц бүрийн боломжит тоог илэрхийлнэ. Хэрэв Available[j] нь k- тай тэнцүү үед Rj –д k тохиолдол боломжтой.

• Max (Хамгийн их). n x m матриц процессыг хамгийн их хэрэгцээтэй тодорхойлсон.Хэрэв Max[i][j] тэнцүү k үед P процесс хамгийн ихдээ k тохиолдол гаргаж өгдөг.
• Allocation (Зарцуулалт). n x m матриц нь процесст байрласан тухайн төрөл аргын тоог тодорхойлдог. Хэрэв Allocation[i][j] тэнцүү k үед процесс Pi нь Rj төрөлд k тохиолдол гаргаж өгдөг.
• Need (Шаардлага). n x m матриц нь процесст байрласан тухайн төрөл аргын тоог тодорхойлдог. Хэрэв Need [i][j] тэнцүү k үед процесс Pi нь биелэхэд Rj төрөлд k-аас олон тохиолдол гаргаж өгдөг.

Need [i][j] = Max[i][j] - Allocation [i][j] гэдгийг анхаарна уу.

Өгөгдлийн бүтэц нь хэмжээ болон утгаа өөрчилж байдаг. Банкирын алгоритмыг хялбарханаар илэрхийлэхэд дараах тэмдэглэгээг бататгах хэрэгтэй. Х,Ү векторууд n урттай. Х≤Ү Х[i] ≤Ү[i] i=1,2,3,….n . Жишээ нь: Хэрэв Х{1,7,3,2} ба Y{0,3,2,1} үед Y≤ X , Y<X хэрэв Y≤X Y≠X Бид Allocation Need матрицын мөр бүрт векторооор нь хандах боломжтой ба Allocation, Need –ээд хамааруулж болдог. Allocation вектор нь Pi процесст гаргаж өгдөг аргыг тодорхойлдог. Needi вектор нь Pi процесс биелэхийг хүссэн нэмэлт арга.

Аюулгүй байдлын алгоритм

Хайлтаас гадуур болон үйлдлийн систем нь аюулгүй мужид байрладаггүй алгоритмыг илэрхийлэх боломжтой. Энэ алгоритм нь дараах байдлаар тодоррхойлогдоно:

Дээрхи алгоритм нь аюулгүй мужид байгаа ч гэсэн n x m үйлдлийг тодорхойлох дараалалыг шаарддаг.

Хүсэлтийн алгоритм

Хүсэлт нь аюулгүйгээр олгогдсон тохиолдлын алгоритмыг тодорхойлъё. Request; нь Р процессын хүсэлтийн вектор гэж үзье. Хэрэв Request;[j] == k үед Рi процесс нь Ri төрлийн k тохиолдол болно. Процесс Р; -ээр хийгдсэн хүсэлт байвал дараах үйлдлүүдийг хийнэ: