Алгоритми синхронізації

Для коректної взаємодії процесів недостатньо одних організаційних зусиль операційної системи. Необхідні певні внутрішні зміни в поведінці процесів . Далі розглянемо питання, пов'язані з такими змінами.

Припустимо , що надійний зв'язок процесів організована , і вони вміють обмінюватися інформацією. Чи потрібно нам робити ще які-небудь дії для організації правильного рішення задачі взаємодіючими процесами ? Чи потрібно змінювати їх внутрішнє поведінку? Роз'яснення цих питань і присвячена дана лекція.

Interleaving , race сcodition і взаимоисключения

Давайте тимчасово відвернемося від операційних систем , процесів і ниток виконання і поговоримо про деякі « активностях ». Пол активностями ми будемо розуміти послідовне виконання ряду дій , спрямованих на досягнення певної мети. Активності можуть мати місце в програмному та технічному забезпеченні , у звичайній діяльності людей і тварин. Ми будемо розбивати активності на деякі неподільні , або атомарні , операції . Наприклад , активність « приготування бутерброда » можна розбити на наступні атомарні операції:

1 ) Відрізати скиби хліба.

2 ) Відрізати скибочку ковбаси.

3 ) Намазати скибочку хліба маслом.

4 ) Покласти скибочку ковбаси на підготовлену скибочку хліба. Неподільні операції можуть мати внутрішні невидимі дії

(взяти батон хліба в ліву руку , взяти ніж в праву руку , провести відрізання ) . Ми ж називаємо їх неподільними тому, що вважаємо виконуваними за раз , без переривання діяльності .

Нехай є дві дії

Р: а Ь с

Q: d e f

де а, Ь, с, d, е, f - атомарні операції. При послідовному виконанні активностей ми отримуємо таку послідовність атомарних дій:

РQ: а Ь c d e f

Що станеться при виконанні цих дій псевдопараллельно, в режимі поділу часу? Дії можуть розслоїтися на неподільні операції з різним чергуванням, тобто може статися те, що в англійській мові прийнято називати словом iterleaving. Можливі варіанти чергування:

а Ь з d e f

а Ь d c e f

a Ь d e c f

а Ь а е f c

а b d з e f

..........

d e f a b c