НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o194.pdf (671.53Кб)

УДК 519.21

1 Россия,  МГТУ им. Н.Э. Баумана

Конфликтной ситуацией в компьютерных системах (КС) называется явление, возни-кающее при мультидоступе процессов к общим ресурсам, когда ни один из процессов, вовлеченных в эту ситуацию, не может продолжаться из-за ожидания определенных ресурсов, захваченных другими процессами, которые, в свою очередь, находятся в аналогичном положении. Конфликтная ситуация имеет и иное название  тупик, что достаточно чётко отражается на состоянии КС.
Поиск практически применимых алгоритмов разрешения тупиковых ситуаций имеет большое прикладное значение для обеспечения информационной безопасности вычисли-тельного процесса и в этой связи представленная статья посвящена решению важной и актуальной задаче.
Серьёзность ситуации зависит от типов процессов, находящихся в тупике, от типов используемых ресурсов, числа процессов и многих других факторов.
Недостаток метода предотвращения тупиковых ситуаций, используемого во многих современных операционных системах и основанного на предварительном планировании необходимых процессу ресурсов, очевиден  время ожидания может оказаться чрезмерно большим. Метод предотвращения с прерыванием работы процесса и освобождением его ресурсов очень специфичен и малоэффективен, когда имеется множество разнотипных ресурсов, запрашиваемых динамически. Недостаток ещё одного метода, предотвращаю-щего тупика путём упорядочения ресурсов, заключается в ограничении возможных последовательностей запросов на ресурсы.
Иной способ «борьбы» с тупиками  недопущение тупиковых ситуаций. Предполагается прогнозирование появления тупиковых ситуаций в будущем. Известные методы, ос-нованные на определении и недопущении состояний, при которых могут возникать тупи-ки. При этом используется предварительная информация о том, какие ресурсы может за-просить процесс во время выполнения. Прежде чем выделить свободный ресурс процес-су, осуществляется проверка на условие «безопасности» состояния. Состояние является «безопасным», если выделение ресурса процессу не может привести к появлению тупико-вых ситуаций в будущем. Иначе состояние считается «опасным», и выделение ресурса откладывается. Очевидный недостаток недопущения тупиковых ситуаций заключается в необходимости иметь априорную информацию о будущих потребностях в ресурсах, а это не всегда возможно.
Один из способов «борьбы» с тупиковыми ситуациями при отсутствии априорной информации о потребностях процесса в ресурсах  обнаружение тупиков. Обнаружение тупиковых ситуаций (еще не приводящее к их разрешению)  это периодическое использование алгоритма, который проверяет текущее распределение ресурсов с целью указания того, существует ли тупиковая  ситуация, и если существует, то  какие процессы в  неё вовлечены.
Цель работы состоит в том, чтобы разработать методы и алгоритмы, позволяющие минимизировать потери из-за тупиковых ситуаций в КС за счёт использования оптималь-ной стратегии разрешения конфликтов. Предлагаемый подход особенно эффективен для устранения тупиков в управляющих КС, набор программ которых фиксирован.
Разработана и предложена эффективная стратегия управления информационными процессами в многопроцессорных КС, обнаруживающая и запрещающая тупиковые си-туации в компьютерных системах. Стратегия базируется на предоставлении неделимых ресурсов вычислительным процессам так, чтобы минимизировать потери из-за конфлик-тов. В статье исследуется многокритериальная задача предоставления неделимых ресур-сов процессам, причём принцип оптимальности выражается известным бинарным отно-шением на множестве средних векторов штрафов за конфликты по каждому из ресурсов. Показано, что совместное использование аппарата теории выбора и классического аппарата позволяет более эффективно решать задачу ликвидации тупиков. Отличительной особенностью предлагаемых эффективных методов и алгоритмов ликвидации тупиков является возможность использования их при разработке и эксплуатации многопроцессорных КС, работающих в реальном масштабе времени. Приведенный в статье пример демонстрирует работоспособность и перспективность предлагаемых метода и алгоритма разрешения тупиковых ситуаций в многопроцессорных КС.
Предложенные метод и алгоритм обеспечивает уменьшение среднего числа конфлик-тов в КС на 30-40%.

1. Андреев А.М., Можаров Г.П., Сюзев В.В. Многопроцессорные вычислительные системы: теоретический анализ, математические модели и применение. М.: Изд-во МГТУ им. Н.Э. Баумана, 2011. 334 с.
2. Королёв В.Ю., Бенинг В.Е., Шоргин С.Я. Математические основы теории риска. 2-е изд., перераб. и доп. М.: ФИЗМАТЛИТ, 2011. 620 с.
3. Ногин В.Д. Принятие решений при многих критериях. СПб.: Изд-во «ЮТАС», 2007. 104 с.
4. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. 2-е изд. испр. и доп. М.: ФИЗМАТЛИТ, 2007. 256 с.
5. Ногин В.Д. Введение в оптимальное управление. СПб.: Изд-во «ЮТАС», 2008. 92 с.
6. Райгородский А.М. Вероятность и алгебра в комбинаторике. М.: МЦНМО , 2011. 48 с.
7. Райгородский А.М. Теория вероятностей и комбинаторная геометрия // Математика в задачах: сб. ст. М.: МЦНМО , 2009. С. 381-384.
8. Ширяев А.Н. Вероятностно-статистические методы в теории принятия решений. М.: ФМОП, МЦНМО, 2011. 144 с.
9. Eggemann N., Noble S.D. The clustering coefficient of a scale-free random graph // Discrete Applied Mathematics. 2011. Vol. 159, no. 3. P. 953-965. DOI:10.1016/j.dam.2011.02.003
10. Kolountzakis M.N., Miller G.L., Peng R., Tsourakakis Ch.E. Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning // Internet Mathematics. 2011. Vol. 8, no. 1. P. 161-185.
11. Peskir G., Shiryaev A. Optimal stopping and free-boundary problems. Basel: Birkhäuser, 2006. 500 p.