Conference publications

Abstracts

XIII conference

Моделирование взаимных блокировок процессов в мультипрограмных вычислениях

Васильев В.А., Засов В.А., Тарабардин М.А.

Самарская государственная академия путей сообщения, Электротехнический ф-т, каф. Автоматизированные системы обработки , информации и управления, Россия, 443066, г. Самара, ул. Свободы 2а,

Предотвращение взаимоблокировок (тупиков) является актуальной задачей, решение которой позволяет повысить надежность функционирования мультипрограммных вычислительных систем (ВС). Предлагается программная система, позволяющая моделировать алгоритмы обнаружения, предотвращения и устранения взаимоблокировок вычислительных процессов. При моделировании ВС задается структурами данных, описывающих вычислительные процессы Р, а также векторами существующих E, доступных А, матрицами R и С запрашиваемых и распределенных ресурсов соответственно.

В простых случаях, когда в ВС имеются в наличии по одному ресурсу каждого типа, для обнаружения взаимоблокировок используется алгоритм определения циклов в направленных графах, которыми описываются вычислительные процессы и ресурсы системы.

В более сложных случаях, при наличии нескольких ресурсов каждого типа, для обнаружения взаимоблокировок используется алгоритм сравнения векторов A доступных и R запрашиваемых ресурсов с проверкой справедливости равенства [1]

, где i и j – индексы процессов и ресурсов соответственно.

Такие проверки могут осуществляться либо при каждом запросе ресурсов, либо с определенным периодом, определяемым степенью загрузки процессора.

Для моделирования вариантов распределения ресурсов, позволяющих избегать взаимоблокировок вычислительных процессов, в системе использован алгоритм Дейкстры (алгоритм банкира) [2].

Предлагаемая система моделирования эффективно применяется при изучении организации вычислительных процессов мультипрограммных и мультипроцессорных ВС различных классов.

При обнаружении взаимных блокировок система позволяет моделировать различные способы восстановления ВС – за счет принудительной выгрузки или уничтожения ресурсов, восстановление через откат ВС.

Литература.

1.Танненбаум Э. Современные операционные системы. – СПб.: Питер, 2002. – 1040 с.

2.Столлингс В. Операционные системы. Внутреннее устройство и принципы проектирования. – М.: Изд. Дом «Вильямс», 2002. – 848 с.