Page 94 - 6571
P. 94

(наприклад  циклічні  блокування  або  алгоритм  розриву  вузла).
                  Наприклад, нехай CSenter – протокол входу критичної секції, a
                  CSexit  -  відповідний  протокол  виходу.  Тоді  в  програмі  з

                  лістингу  11  інструкцію  «витягти  і  скласти»  можна  замінити
                  наступною послідовністю операторів:

                        CSenter;
                          turn[i] = number;
                          number = number+1;
                        CSexit;

                        Такий  підхід  виглядає  незвичайним,  але  на  практиці  він
                  працює  добре,  особливо  якщо  для  реалізації  протоколів  входу  і

                  виходу  доступна  інструкція  типу  «перевірити-встановити».  При
                  виконанні           інструкції         «перевірити-встановити»                  процеси
                  отримують  номери,  що  не  обов’язково  відповідають  порядку,  в
                  якому  вони  намагаються  це  зробити,  і  теоретично  процес  може

                  зациклитися  назавжди.  Але  з  дуже  високою  ймовірністю  кожен
                  процес  отримає  номер,  і  більшість  номерів  будуть  обрані  в
                  порядку  їх  зростання.  Основна  причина  виникнення  затримок  в

                  алгоритмі квитка – це очікування, поки значення змінної next не
                  стане рівним значенню turn[i].


                        11.3 Алгоритм поліклініки


                        Алгоритм квитка можна безпосередньо реалізувати на маши-

                  нах, що мають підтримку операції типу «витягти і скласти». Як-
                  що така інструкція недоступна, то можна виконати моделювання
                  її алгоритму роботи. Але для цього потрібен ще один протокол

                  критичної секції, і рішення не обов’язково буде мати властивість
                  справедливості. Представлений тут алгоритм поліклініки, подіб-
                  ний алгоритму квитка. Він забезпечує справедливість планування
                  і не вимагає спеціальних машинних інструкцій. Проте, він склад-
                  ніший для практичної реалізації, ніж алгоритм квитка.

                        Згідно  алгоритму  квитка  кожен  відвідувач  отримує
                  унікальний номер і очікує, поки значення змінної next не стане
                  рівним цьому номеру. Алгоритм поліклініки використовує трохи

                  інший підхід. Заходячи в поліклініку, відвідувач дивиться на всіх
                  інших  і  вибирає  номер,  який  більший  усіх  інших  вибраних
                  номерів.  Усі  відвідувачі  повинні  чекати,  поки  не  назвуть  їх
                  номер.  Як  і  в  алгоритмі  квитка,  наступним  обслуговується

                                                              93
   89   90   91   92   93   94   95   96   97   98   99