Петерсоны алгоритм

Петерсоны алгоритм нь анх 1981 онд Gary L. Peterson өөрийн нэрээр нэрлэж зохиосон билээ. Энэ нь бусад алгоритмыг бодвол энгийн ба 2 процессыг 1 нөөцөөр хосолсон маягаар ажиллуулдагаараа давуу талтай. Алгоритм нь flag болон turn гэсэн 2 хувьсагчтай.

Жишээ код

P0 болон P1 нь Процесс, flag[n] нь үнэн, худал гэсэн утга оруулна. n нь хэддэх процессыг заана.

[[

2 Процесс

bool flag[0] = {false};
bool flag[1] = {false};
int turn;

P0:      flag[0] = true;
P0_gate: turn = 1;
         while (flag[1] == true && turn == 1)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[0] = false;

P1:      flag[1] = true;
P1_gate: turn = 0;
         while (flag[0] == true && turn == 0)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[1] = false;

Орчин үеийн компьютерийн архитектуруудын чиг хандлага нь үндсэн машин хэлний ачааллах, хадгалах гэх мэт командад ажилладаг учир, Петерсоны шийдэл нь архитектурд яг зөв ажиллах баталгааг өгч чадахгүй. Гэсэн хэдий ч Петерсоны шийдэл нь зарим нарийн төвөгтэй байдлыг програм хангамжийн загварт татан оруулж зурагласан байдаг ба эгзэгтэй асуудлыг шийдэх сайн алгоритмын тайлбараар хангадаг. Петерсоны шийдэл нь critical section ба remainder section хоёр процессоор хязгаарлагдана. Процессууд нь P0, Pi дугаарлагдана. Одоогоор Pi байх үед, бид бусад процессыг Pj гэж тэмдэглэнэ. Энд j=1-i байна. Петерсоны шийдэлд хоёр процессын хооронд хоёр өгөгдөл солилцох шаарлагатай байдаг.

                            Int turn;
                            Boolean flag[2];

Turn хувьсагч зарлагдахад critical section-д орно. Хэрэв turn==i бол процесс Pi нь critical secion-г гүйцэтгэхийг зөвшөөрнө. Flag массивыг процесс critical section-д нэвтрэхэд бэлэн болсон үед тэмдэглэнэ. Жишээлбэл, flag[i] нь үнэн бол, Pi нь critical section-д нэвтрэхэд бэлэн болсоныг илтгэж байна. Процесс Pi critical section-д нэвтрэхэд flag[i] үнэн болох бөгөөд j утгыг олгоно. Хэрэв хоёр процесс яг нэг цагт ижил орж ирвэл I, ба J – г ижил цагт хоёуланг нь олгоно.