В параллельных вычислительном , живучести относится к набору свойств параллельных систем , которые требуют систем к прогрессу макияжа , несмотря на то , что его одновременно исполняющим компоненты ( «процессы») , возможно , придется «по очереди» в критических секциях , части программы которые не могут одновременно выполняться несколькими процессами. [1] Гарантии живучести - важные свойства операционных систем и распределенных систем . [2]
В более общем смысле свойство живучести утверждает, что «в конечном итоге произойдет что-то хорошее», в отличие от свойства безопасности, которое гласит, что «что-то плохое не происходит». Если свойство безопасности нарушено, всегда существует конечное выполнение, которое показывает нарушение (возникновение «плохого» события), но свойство живучести не может быть нарушено при конечном выполнении распределенной системы, потому что «хорошее» событие все еще может произойти в немного позже. Конечная согласованность - это пример свойства живучести. [3] Все свойства линейного времени могут быть выражены как пересечение свойств безопасности и живучести. [4]В то время как нарушение данного свойства безопасности допускает наличие ограниченного свидетеля, нарушение свойств живучести может быть труднее установить, поскольку конечный свидетель не может использоваться в качестве доказательства. [5]
Формы жизни
Признаны несколько форм жизни. Следующие из них определены в терминах многопроцессорной системы, в которой есть критическая секция, защищенная каким-либо устройством взаимного исключения (мьютексом). Предполагается, что все процессы правильно используют мьютекс; прогресс определяется как завершение выполнения критического раздела.
- Свобода от тупика - это форма жизни, хотя и слабая. Рассмотрим систему с множеством процессов и одной критической секцией, защищенной каким-либо устройством взаимного исключения . О такой системе говорят, что она свободна от тупиков, если, когда группа процессов конкурирует за доступ к критическому разделу в какой-то момент времени, какой-то процесс в конечном итоге прогрессирует в более поздний момент времени. Этот процесс не обязательно должен принадлежать к вышеупомянутой группе; он мог получить доступ раньше или даже позже. [6]
- Свобода от голода (или «конечный обход») является более надежной гарантией жизнеспособности, чем свобода от тупика. В нем говорится, что все процессы, соперничающие за доступ к критической области, в конечном итоге достигают прогресса. Любая система без голодания также безблокировочная. [6]
- Еще более сильным является требование ограниченного обхода. Это означает, что если n процессов конкурируют за доступ к критической области, то каждый процесс прогрессирует после того, как его обойдут не более f ( n ) раз другие процессы для некоторой функции f . [6]
Живучесть и безопасность
По мнению Б. Альперна, отсутствие тупиков - это свойство безопасности . [7] Альперн предполагает, что состояния системы могут быть разделены между состояниями, в которых имеется тупик (красные состояния), и состояниями, в которых тупик не существует (зеленые состояния). Свойство, которое гласит, что система всегда остается в зеленом состоянии (или, альтернативно, что система никогда не достигает красного состояния), является свойством безопасности. Однако, если невозможно различить зеленое и красное состояния, свойство, которое говорит о том, что в конечном итоге один из процессов в системе будет развиваться, является свойством жизнеспособности.
Формальное различие
Различие между безопасностью и живучестью можно формально установить с помощью предиката , где относится ко времени. Позволятьбыть моментом времени, начиная с которого оцениваются свойства живучести и безопасности. В приведенных ниже примерах пусть быть процессом (или потоком), который нужно гарантировать, что он свободен от тупиковых ситуаций.
Безопасность:
Пример: средства " находится в состоянии тупика во время ".
Живучесть:
Пример: средства " перестает ждать вовремя ".
Ограниченный объезд и ограниченный обгон
Также стоит отметить, что разница между свойством живучести ограниченного объезда и свойством безопасности ограниченного обгона тонкая. Свобода голода вместе с ограниченным обгоном подразумевает ограниченный объезд (т. Е. Хотя ограниченный объезд классифицируется как свойство живучести, в действительности это сочетание свойства живучести и свойства безопасности). Ограниченный обгон означает, что после того, как помеченный процесс заявляет о своей заинтересованности во входе в критическую секцию, каждый другой процесс будет обгонять помеченный процесс ограниченное количество раз, прежде чем помеченный процесс войдет в критическую секцию. Обратите внимание, что если отмеченному процессу никогда не предоставляется разрешение на вход в его критическую секцию, ограниченный обгон все еще может сохраняться. Следовательно, ограниченный обгон сам по себе не является свойством живучести. В системе с тупиком ограниченный обгон выполняется тривиально, поскольку ни один процесс не догоняет другой, а ограниченный обход - нет. [8]
Смотрите также
Рекомендации
- ^ Лампорт, L. (1977). «Доказательство правильности многопроцессорных программ». IEEE Transactions по разработке программного обеспечения (2): 125–143. CiteSeerX 10.1.1.137.9454 . DOI : 10.1109 / TSE.1977.229904 .
- ^ Луис Родригес, Кристиан Кашен; Рашид Геррауи (2010). Введение в надежное и безопасное распределенное программирование (2-е изд.). Берлин: Springer Berlin. С. 22–24. ISBN 978-3-642-15259-7.
- ^ Bailis, P .; Годси, А. (2013). «Возможная согласованность сегодня: ограничения, расширения и не только» . Очередь . 11 (3): 20. DOI : 10,1145 / 2460276,2462076 .
- ^ Alpern, B .; Шнайдер, Ф. Б. (1987). «Признание безопасности и живучести». Распределенные вычисления . 2 (3): 117. CiteSeerX 10.1.1.20.5470 . DOI : 10.1007 / BF01782772 .
- ^ Гауда, Мохамед Г. (1993). «Проверка протокола - это просто: учебное пособие». Компьютерные сети и системы ISDN . 25 (9): 969–980. DOI : 10.1016 / 0169-7552 (93) 90094-к .
- ^ а б в Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы . Springer Science & Business Media. С. 10–11. ISBN 978-3642320262.
- ^ Альперн, Б. (1985). «Определяя живость». Письма об обработке информации . 21 (4): 181–185. DOI : 10.1016 / 0020-0190 (85) 90056-0 .
- ^ Фанг, Ю. (2006). Живучесть невидимыми инвариантами . Международная конференция по формальным методам для сетевых и распределенных систем . Конспект лекций по информатике. 4229 . С. 356–371. DOI : 10.1007 / 11888116_26 . ISBN 978-3-540-46219-4.