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

Голландын математикч Th.J.Dekker[1] процессуудын хамтран ажиллах үр дагаварын талаар бичиж үлдээсэн байдаг. Диккерийн алгоритм нь програмын нөхцөл дэхь харилцан үл зөвшөөрөх асуудлын нөхцлийг шийдвэрлэнэ. Дотор нь 4 хэсэгт хувааж үздэг.

Entry section(Эхний хэсэг) – Биелэгдэх кодыг бэлтгэж шийдвэрлэх хэсэг рүү явуулна.

Critical section[2](Шийдвэрлэх хэсэг) – Кодын дагалдах нөхцлийг биелүүлнэ.

Exit section(Гарах хэсэг) – Код биелэсний дараа гарах хэсэг рүү очно.

Remainder section(Үлдэгдэл хэсэг) – Кодын завсарлага. Энэ хэсэгт алдаагүй код байрлана.

Section

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

2 процессийн асуудал:

turn=i;

do

{

while ( turn != i); //if not i's turn , wait indefinately

// critical section

turn = j; //after i leaves critical section, lets j in

//remainder section

}

while (1);

//loop again

Солбицол

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

Солбицол (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 хэмээх нөөцийг ямарваа нэгэн процесс эзэмшиж эхлэхээс өмнө өөр хэн нэгэн эзэмшиж буй эсэхийг шалгадаг байх шаардлага тавьснаар шийдэж болно.

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

- Деккерийн

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

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

Деккерийн алгоримтыг хоёр л процессын хувьд авч үзэх ба ерөнхий тохиолдолд авч үзэх нь хоёр процесстой тохиолдолтой ижил юм. 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;
...

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

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