Деккерийн алгоритм

Чөлөөт нэвтэрхий толь — Википедиагаас
Jump to navigation Jump to search

Солбицол[засварлах | edit source]

Нөөцийн төлөөх өрсөлдөөний үед гарч ирэх солбицол, синхрончлол гэсэн хоёр ойлголт хоорондоо ялгаатай ойлголтууд юм. Солбицлын асуудал нь хамтран эзэмшиж буй өгөгдөл рүү зэрэгцээ ажиллаж буй процессууд нэгэн зэрэг хандах үед үүсдэг. Харин синхрончлолын асуудал нь ямар нэг нөхцлөөр процессуудыг ажиллах, түр зогсох үйлдлийг зохицуулах үед үүсдэг. Өөрөөр хэлбэл эдгээр асуудлууд нь процессууд хоорондоо харилцан ажиллаж байхад үүсдэг.

Солбицол (mutual exclusion,mutex) – Нэг процессын эзэмшиж буй нөөцийг өөр нэгэн процесс эзэмшихийг хүсч болно. Энэ тохиолдолд дээр 
дурьдсантай адил асуудал үүсч болно. Энэ асуудлыг эгзэгтэй муж (critical section) хэмээх ойлголтыг хэрэглэн шийддэг.

Олон тооны процесс зэрэгцээ ажиллаж байх явцад ямар нэг нөөцийг ашиглах хэд хэдэн хүсэлт нэгэн зэрэг ирж болно. Энэ тохиолдолд хүсэлтүүдийг зохицуулах хэрэгтэй. Гэвч ихэнх үйлдлийн систем жинхэнэ утгаараа зэрэгцээ ажиллагаатай бус харин зүгээр л зэрэгцээ ажиллаж буй сэтгэгдэл төрүүлдэг билээ.Энэ тохиолдолд нөөцийн төлөөх өрсөлдөөн үүсэхгүй мэт боловч үнэндээ тийм биш юм.

Солбицолын асуудал дээр жишээ авч үзье: Доор бичсэн гараас утга аваад, дэлгэцэнд хэвлэх echo функцийг P1, P2 процессууд хамтран эзэмшиж байгаа гэж үзье.

void echo {
chin=getchar();
chout=chin;
putchar(chout); }

Энэ функцийг P1, P2 процессууд дуудсан байг. P1 процесс ажиллахдаа утгыг chin хувьсагчид уншаад түр завсарласан. Харин P2 процесс нь ажиллахдаа echo функцийг бүтнээр ажиллуулсан гэж үзье. Дараа нь P1 процесс өөрийн ээлжинд ажиллаж эхлээд chout хувьсагчид chin хувьсагчийн утгыг оноогоод дараа нь chout хувьсагчийн утгыг гаргана. Гэтэл урьд нь P2 процессын үр дүнд chin утга өөрчлөгдсөн тул хүссэн утгыг гаргахгүй.

P1 процесс ажиллаж байна
chin=getchar(); // chin=100 болсон гэж үзье
Р1 процесс түр завсарлав.
Р2 процесс ажиллаж эхлэв.
chin=getchar(); //chin=120 болсон гэж үзье
chout=chin;
putchar(chout); //120 утгыг хэвлэв
P2 процесс үйл ажиллагаагаа дуусгав
Р1 процесс үргэлжлүүлэн ажиллав
chout=chin
putchar(chout); //120 утгыг гаргав
P1 процесс үйл ажиллагаагаа дуусгав

Дээрх жишээнд Р1 процесс 120 утга гаргаж байна. гэтэл анх Р1 процесс ажиллахдаа 100 утгыг гаднаас авсан. Энэ асуудлыг шийдэхдээ echo хэмээх нөөцийг ямарваа нэгэн процесс эзэмшиж эхлэхээс өмнө өөр хэн нэгэн эзэмшиж буй эсэхийг шалгадаг байх шаардлага тавьснаар шийдэж болно.

Програм хангамжид тулгуурласан шийдэл буюу солбицлын асуудлыг шийдэх алгоритмуудаас хамгийн өргөн тархсан нь

- Деккерийн

- Петерсоны алгоритмууд юм.

Деккерийн алгоримт[засварлах | edit source]

Деккерийн алгоримтыг хоёр л процессын хувьд авч үзэх ба ерөнхий тохиолдолд авч үзэх нь хоёр процесстой тохиолдолтой ижил юм. File:EWD1303diagram3.png I хувилбар : Санах ойн нэг мужид нэгэн зэрэг зөвхөн нэг л процесс хандаж болох техник хангамжийн чанарыг үндэслэн ажилладаг. Өөрөөр хэлбэл процесс бүр эгзэгтэй мужид орох ээлжээ хүлээдэг. Аль нэг процесс эгзэгтэй муждаа ажиллаж дуусаад дараагийн процесст эгзэгтэй мужид орох эрхийг нь олгодог. Үүнийг алгоритмд turn хувьсагч зааж өгнө. Turn хувьсагчийн утгатай процессын дугаар тохирч байвал л уг процесс эгзэгтэй муждаа ажиллах ба харин тохирохгүй бол завгүй хүлээлт болно. Процесс эгзэгтэй муждаа ажиллаж дуусаад дараа нь turn хувьсагчийн утгыг өөрчилнө.

Деккерийн алгорим
Var turn 0..1;
..........................
process0 //А процесс гэе
…
While turn!=0 do {nothing};
<Эгзэгтэй муж>
turn=1
end;
..........................
process 1 //Б процесс гэе
….
While turn!=1 do {nothing};
<Эгзэгтэй муж>
turn=0
end;
.............................
Begin
parbegin
process0;
process1;
parend;
End.

II хувилбар : Деккерийн алгоритмын I хувилбарт өөр ямар нэгэн процесс эгзэгтэй мужид байхгүй байгаа эсэхээс үл хамааран процесс эгзэгтэй мужид орох боломжгүй болох тохиолдол гарна. Иймээс процесс бүр өөрийн төдийгүй, бусад процессын төлвийг мэдэх хэрэгтэй. Үүний тулд системд байгаа процесс бүрийн төлвийн мэдээллийг хадгалах хэрэгтэй.

Var flag:array[0..1] of boolean;
PROCESS 0
...
While flag[1] do {nothing};
flag[0]=true;
<эгзэгтэй муж>;
flag[0]=false;
...

Энэ аргын үед үүсэх хүндрэлүүд

  • Завгүй хүлээлт
  • Процессуудын хурдны зөрөө
  • Гачигдал

Ашигласан материал[засварлах | edit source]