АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов

При организации параллельного выполнения нескольких процессов одной из главных функций операционной системы является решение сложной задачи кор­ректного распределения ресурсов между выполняющимися процессами и обес­печение последних средствами взаимной синхронизации и обмена данными.

При параллельном исполнении процессов могут возникать ситуации, при кото­рых два или более процесса все время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ожидает ре­сурс, занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжить исполнение и освободить в конечном итоге ресурс, необхо­димый другому процессу. Эта тупиковая ситуация называется дедлоком*, тупи­ком или клинчем. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ждет события, которое никогда не произойдет. Ту­пики чаще всего возникают из-за конкуренции несвязанных параллельных про­цессов за ресурсы вычислительной системы, но иногда к тупикам приводят и ошибки программирования.

¹ Dead lock — смертельное объятие.

При рассмотрении проблемы тупиков целесообразно понятие ресурсов системы обобщить и разделить их все на два класса — повторно используемые (или сис­темные) ресурсы (типа RR или SR — reusable resource или system resource) и по­требляемые (или расходуемые) ресурсы (типа CR — consumable resource).

Повторно используемый ресурс (SR) есть конечное множество идентичных еди­ниц со следующими свойствами [92]:

Q число единиц ресурса постоянно;

Q каждая единица ресурса или доступна, или распределена одному и только од­ному процессу (разделение либо отсутствует, либо не принимается во внима­ние, так как не оказывает влияния на распределение ресурсов, а значит, и на возникновение тупиковой ситуации);

Q процесс может освободить единицу ресурса (сделать ее доступной), только если он ранее получил эту единицу, то есть никакой процесс не может оказы­вать какое-либо влияние ни на один ресурс, если он ему не принадлежит.

Данное определение выделяет существенные для изучения проблемы тупика свойства обычных системных ресурсов, к которым мы относим такие компонен­ты аппаратуры, как основная память, вспомогательная (внешняя) память, пери­ферийные устройства и, возможно, процессоры, а также программное и инфор­мационное обеспечение, такое как файлы данных, таблицы и «разрешение войти в критическую секцию».

Расходуемый ресурс (CR) отличается от ресурса типа SR в нескольких важных отношениях [37]:

Q число доступных единиц некоторого ресурса типа CR изменяется по мере того, как приобретаются (расходуются) и освобождаются (производятся) от­дельные их элементы выполняющимися процессами, и такое число единиц ресурса является потенциально неограниченным; процесс «производитель» увеличивает число единиц ресурса, освобождая одну или более единиц, кото­рые он «создал»;

Q процесс «потребитель» уменьшает число единиц ресурса, сначала запрашивая и затем приобретая (потребляя) одну или более единиц. Единицы ресурса, которые приобретены, в общем случае не возвращаются ресурсу, а потребля­ются (расходуются). Эти свойства потребляемых ресурсов присущи многим синхронизирующим сигналам, сообщениям и данным, порождаемым как ап­паратурой, так и программным обеспечением, и могут рассматриваться как ресурсы типа CR при изучении тупиков. В их число входят: прерывания от таймера и устройств ввода/вывода; сигналы синхронизации процессов; сооб­щения, содержащие запросы на различные виды обслуживания или данные, а также соответствующие ответы.

Для исследования параллельных процессов и, в частности, проблемы тупиков было разработано несколько моделей. Одной из них является модель повторно используемых ресурсов Холта [92]. Согласно этой модели система представляет­ся как набор (множество) процессов и набор ресурсов, причем каждый из ресур­сов состоит из фиксированного числа единиц. Любой процесс может изменять

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

В графической форме процессы и ресурсы представляются квадратами и круж­ками соответственно. Каждый кружок содержит некоторое количество маркеров (фишек) в соответствии с существующим количеством единиц этого ресурса. Дуга, указывающая из «процесса» на «ресурс», означает запрос одной единицы этого ресурса. Дуга, указывающая из «ресурса» на «процесс», представляет выделение ресурса процессу. Поскольку каждая единица любого ресурса типа SR может быть выделена одновременно не более чем одному процессу, то число дуг, исхо­дящих из ресурса к различным процессам, не может превышать общего числа единиц этого ресурса. Такая модель называется графом повторно используемых ресурсов.

Одно из состояний примера системы из двух процессов с ресурсами типа SR представлено на рис. 7.1.

Пусть процесс Р1 запрашивает две единицы ресурса R1 и одну единицу ресур­са R2. Процессу Р2 принадлежат две единицы ресурса R1 и ему нужна одна еди­ница R2. Предположим, что процесс Р1 получил бы теперь запрошенную им единицу R2. Если принято правило, по которому процесс должен получить все запрошенные им ресурсы, прежде чем освободить хотя бы один из них, то удов­летворение запроса Р1 приведет к тупиковой ситуации: Р1 не сможет продол­житься до тех пор, пока Р2 не освободит единицу ресурса R1, а процесс Р2 не сможет продолжиться до тех пор, пока Р1 не освободит единицу R2. Причиной этого дедлока являются неупорядоченные попытки процессов войти в критиче­ский интервал, связанный с выделением соответствующей единицы ресурса.

Дата добавления: 2015-01-18 | Просмотры: 1203 | Нарушение авторских прав