SW316 Лаб/ажил 3

Лабораторийн ажил 3

Сэдэв: Нөөцийн төлөөх өрсөлдөөн

Хугацаа: IV/10-11

Оноо: 4 хүртэл оноо

Бодлогын нөхцөл: Деккерийн алгоритмуудыг загварчлах

Бодогын өгөгдөл: Системд 2 загвар байгаа гэж үзнэ. Процессуудын юу хийхийг оюутан өөрөө шийднэ.

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

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

Нэгэн жишээ авч үеье.
Доор бичсэн гараас утга аваад, дэлгэцэнд хэвлэх echo функцийг P1, P2 процессууд хамтран эзэмшиж байгаа гэж үзье. (echo функц нь нөөц мөн үү?)
void echo {
chin=getchar();
chout=chin;
putchar(chout); }

Алгоритм 5.1 echo процедур

Энэ функцийг 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 процесс үйл ажиллагаагаа дуусгав

Алгоритм 5.2 Солбицлын асуудал

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

chin=getchar();

Р1 процесс түр завсарлав
Р2 процесс ажиллаж эхлэв
echo нөөцийг Р1 процесс эзэмшиж байгаа тухай тэмдэглэсэн тул уг нөөцийг эзэмшилгүйгээр үйл ажиллагааг үргэлжлүүлье
Энд ямарваа нэгэн үйлдэл хийхгүй
Р2 процесс түр завсарлав
Р1 процесс үргэлжлүүлэн ажиллав
echo нөөцийг Р1 процесс (өөрөө) эзэмшиж байгаа тухай тэмдэглэсэн тул үйл ажиллагаагаа үргэлжлүүлье

chout=chin;
putchar(chout); //100 утгыг гаргана

echo нөөцийг Р1 эзэмшиж байгаа тухай тэмдэглэлээ арилгалаа
Р1 процесс үйл ажиллагаагаа дуусгав
Р2 процесс үргэлжлүүлэн ажиллав
echo нөөцийг өөр хэн ч эзэмшээгүй тул уг нөөцийг Р2 процесс эзэмшиж байгаа тухай тэмдэглээд үйл ажиллагаагаа үргэлжлүүлье

chin=getchar(); //chin=120 болсон
chout=chin;
putchar(chout); //120 утгыг гаргана

Р2 процесс үйл ажиллагаагаа дуусгав

Алгоритм 5.3 Солбицлын асуудлыг шийдсэн нь

Систем дэх процессууд бусад процессуудын талаар ямар ч мэдээлэлгүй байх ба зөвхөн өөрт шаардлагатай нөөцийн төлөө бусадтай өрсөлдөх хэлбэрээр ажиллана.Өөрөөр хэлбэл процесс бүр өөрийн шаардлагыг хангахын төлөө л ажиллана. Энэ тохиолдолд системд доорхи асуудлууд үүсч болно.
- Солбицол (mutual exclusion,mutex) – Нэг процессын эзэмшиж буй нөөцийг өөр нэгэн процесс эзэмшихийг хүсч болно. Энэ тохиолдолд дээр дурьдсантай адил асуудал үүсч болно. Энэ асуудлыг эгзэгтэй муж (critical section) хэмээх ойлголтыг хэрэглэн шийддэг.
- Түгжрэл (deadlock) – Р1 процесс ажиллахын тулд R1 ба R2 нөөцийг өгсөн дарааллаар эзэмших ёстой. Харин Р2 процесс R2 ба R1 нөөцийг өгсөн дарааллаар эзэмших ёстой байг. Энэ тохиолдолд Р1 процессR1 нөөцийг эзэмшсэний дараа Р2 процесс R2 нөөцийг эзэмшсэн байг. Цааш аль ч процесс ажиллаж чадахгүй. Учир нь Р1 процесс ажиллахын тулд R2 нөөц хэрэгтэй. Харин Р2 процесс ажиллахын тулд R1 нөөц хэрэгтэй. Харин шаардлагатай нөөцүүдийг эзэмших боломжгүй ба R1 нөөц нь Р1 процесс ажиллаж дууссаны дараа чөлөөлөгдөнө. Харин R2 нөөц нь Р12 процесс ажиллаж дууссаны дараа чөлөөлөгдөнө. Гэтэл аль ч процесс шаардлагатай нөөцгүйн улмаас цаашид ажиллаж чадахгүй байгаа билээ.
- Гачигдал (starvation) – Р1, Р2 ба Р3 процессууд R нөөцийг эзэмшихийн төлөө өрсөлдөж байг. Р1ба Р3 процессууд нь ямар нэгэн шалтгаанаа R нөөцийг ээлжлэн эзэмшсээр Р2 процесст уг нөөцийг эзэмших боломж олгохгүй байснаар Р2 цааш хэвийн ажиллахад хүндрэл үүсч гачигдалд орж байна.

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

- Деккерийн алгоритм – Деккерийн алгоримтыг хоёр л процессын хувьд авч үзэх ба ерөнхий тохиолдолд авч үзэх нь хоёр процесстой тохиолдолтой ижил юм.
I хувилбар
Анхны хувилбарт санах ойн нэг мужид нэгэн зэрэг зөвхөн нэг л процесс хандаж болох техник хангамжийн чанарыг үндэслэн ажилладаг байсан. Өөрөөр хэлбэл процесс бүр эгзэгтэй мужид орох (нөөцийг дангаар эзэмших эрхээ олж авах) ээлжээ хүлээдэг. Аль нэг процесс эгзэгтэй муждаа ажиллаж дуусаад дараагийн процесст эгзэгтэй мужид орох эрхийг нь олгодог. Үүнийг алгоритмад turn хувьсагч зааж өгнө.
turn хувьсагчийн утгатай процессын дугаар тохирч байвал л уг процесс эгзэгтэй муждаа ажиллах ба харин тохирохгүй бол завгүй-хүлээлт болно. Процесс эгзэгтэй муждаа ажиллаж дуусаад дараа нь turn хувьсагчийн утгыг өөрчилнө. (Алгоритм 5.12) Жишээ: turn=0 байж байгаад turn=1 болгоно гэсэн үг. Ингэснээр 1 дугаартай процесс эгзэгтэй муждаа орох эрхтэй болно.
Var turn 0..1;
process0 //À ïðîöåññ ãýå
…
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;
...



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


II хувилбарын дутагдлууд
• Процесс эгзэгтэй муждаа орохоос өмнөхөн flag утгаа true болгоод тасарвал бусад процесс эгзэгтэй мужид орж чадахгүй
• Хэд хэдэн процесс эгзэгтэй мужид орох боломжтой.
• Процесс бүр бусдын төлөвийг мэдэж болох боловч өөрчилж болохгүй .
• Процесс эгзэгтэй муждаа орохын тулд бусдыг шалгана.

III алгоритм
II алгоритмын хувилбарт хэд, хэдэн процесс нэгэн зэрэг эгзэгтэй муждаа байх боломжтой байсан. Энэ асуудлыг III хувилбарт шийдсэн.

PROCESS0 PROCESS1
. . . . . .
flag[0]:=true; flag[1]:=true;
while flag[1] do { nothing }; while flag[0] do {nothing};
<Эгзэгтэй муж> <Эгзэгтэй муж>
flag[0]:=false; flag[1] :=false;
. . . . . .

Бусад процессыг шалгахаасаа өмнө эгзэгтэй мужид орох флагаа тогтоож байна.
Флаг тогтоогдсон байхад өөр процесс эгзэгтэй мужид байгаа нь тогтоогдвол тэр процесс эгзэгтэй мужийг чөлөөлтөл процесс түр хүлээнэ.
Түгжрэл үүсэх магадлалтай . Хоёр процесс зэрэг флагаа тогтоогоод эгзэгтэй мужид орвол нэг нэгийгээ эгзэгтэй мужийг чөлөөлөхийг хүлээн түгжигдэнэ.

PROCESS0
flag[0]=true;
PROCESS1
flag[1]=true;
PROCESS0
while flag[1] do {nothing};
PROCESS1
while flag[0] do {nothing};
Эндээ харахад III хувилбар нь түгжрэлд хүргэж болох юм.

IV хувилбар
• Өмнөх хувилбаруудад процесс бүр зөвхөн өөрийгөө л эгзэгтэй мужид байх цорын ганц эрхтэй гэж үзэж байснаас түгжрэл үүсч байсан.
• Иймээс өөрийн флагаа тогтоогоод бусдыг шалгаж, хэрэв өөр нэгэн процесс эгзэгтэй муждаа байвал түүнийг гартал нь хүлээх арга.

PROCESS 0 PROCESS 1
flag[0]=true; flag[1]=true;
while flag[1] do while flag[0] do
begin begin
flag[0]=false; flag[1]=false;
<Түр хүлээх> <Түр хүлээх>
flag[0]=true; flag[0]=true;
end; end;
<Эгзэгтэй муж> <Эгзэгтэй муж>
flag[0]=false; flag[1]=false;

Процесс бүр өөрсдийн флагаа тогтоогоод , дараа нь бие биенийхээ флагийг шалгаад эргээд өөрийн флагийг тэглэх тохиолдол гарч болзошгүй . Энэ нь удаан үргэлжлэхгүй. Өөрөөр хэлбэл энэ нь түгжрэлийн байдал биш, үл ойлголцох байдал юм.

PROCESS0
flag[0]=true
PROCESS1
flag[1]=true
PROCESS0
flag[1]=true эсэхийг шалгах
PROCESS1
flag[0]=true эсэхийг шалгах
PROCESS0
flag[0]=false болгох
PROCESS1
flag[1]=false болгох ………..

Нэгдсэн алгоритм
Деккерийн алгоритмууд нь өмнөх алгоритмуудаа сайжруулан зохиогдож байсан ч үл ойлголцлын асуудлыг үүсгэж байсан. Иймээс илүү сайжруулсан өмнөх дутагдлуудыг шийдсэн алгоритмыг гаргасан бөгөөд үүнийг Нэгдсэн буюу Үндсэн алгоритм гэж нэрлэсэн.
Алгоритмын үндсэн санаа нь:
Аль нэг процесс эгзэгтэй мужид орох флагаа тогтоогоод бусад процессын флагийг шалгахад өөр ямар ч процесс эгзэгтэй муждаа байхгүй бол уг процесс эгзэгтэй муждаа шууд орно.
Эсрэг тохиолдолд “гуравдагч” хүчин зүйл буюу turn хувьсагчид хандана. Хэрэв turn хувьсагч нь өөрөөс нь өөр процесс эгзэгтэй мужид байх ёстойг зааж байвал өөрийн флагын утгыг худал болгоод, завгүй-хүлээлтийн төлөвт орох ба эсрэг тохиолдолд эгзэгтэй муж руугаа шууд орно.
За одоо алгоритмынхаа псевдо кодтой танилцъя
Var flag: array[0..1] of boolean;
turn: 0..1;
procedure P0;
begin
repeat
flag[0]:=true;
while flag[1] do if turn=1 then
begin
flag[0]:=false;
while turn=1 do {nothing};
flag[0]:=true;
end;
<Эгзэгтэй муж>;
turn:=1; flag[0]:=false;
<Бусад үйлдэл>
forever
end;
procedure P1;
. . .
end;

Begin
flag[0]:=false;
flag[1]:=false;
turn:=1;
parbegin
P0; P1;
parend;
end;

Тайлбар:
Та бүхэн <эгзэгтэй муж> гэсэн ойлголтыг өөр өөрсдийнхөө хийсвэрлэж төлөөлүүлж болно.М Жишээ нь: нэг хувьсагч байдаг ч юм уу.....