Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Разрешение конфликтов в компьютерных системах

# 08, август 2015
DOI: 10.7463/0815.0793623
Файл статьи: SE-BMSTU...o194.pdf (671.53Кб)
автор: Можаров Г. П.1

УДК 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.
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2022 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)