Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 64
Текст из файла (страница 64)
Однако неследует путать конвейеры с очередями сообщений; последние реализуются иначеи имеют другие возможности.Конвейер имеет определенный размер1, который не может превышать 64 Кбайт иработает циклически. Вспомните реализацию очереди на массивах, когда имеютсяуказатели начала и конца очереди, которые перемещаются циклически по массиву.То есть имеется некий массив и два указателя: один показывает на первый элемент(указатель на начало — head), а второй — на последний (указатель на конец — tail).В начальный момент оба указателя равны нулю. Добавление самого первого элемента в пустую очередь приводит к тому, что указатели на начало и на конец принимают значение, равное 1 (в массиве появляется первый элемент).
В последующем добавление нового элемента вызывает изменение значения второго указателя,поскольку он отмечает расположение именно последнего элемента очереди. Чтен и е (и удаление) элемента (читается и удаляется всегда первый элемент из созданной очереди) приводит к необходимости модифицировать значение указателя на ее начало. В результате операций записи (добавления) и чтения (удаления)элементов в массиве, моделирующем очередь элементов, указатели будут перемещаться от начала массива к его концу.
При достижении указателем значения индекса последнего элемента массива значение указателя вновь становится единичным (если при этом не произошло переполнение массива, то есть количествоэлементов в очереди не стало большим числа элементов в массиве). Можно сказать, что мы как бы замыкаем массив в кольцо, организуя круговое перемещениеуказателей на начало и на конец, которые отслеживают первый и последний элементы в очереди. Сказанное иллюстрирует рис. 7.4. Именно так функционируетконвейер.Как информационная структура конвейер описывается идентификатором, размером и двумя указателями. Конвейеры представляют собой системный ресурс.
Чтобыначать работу с конвейером, процесс сначала должен заказать его у операционнойсистемы и получить в свое распоряжение. Процессы, знающие идентификатор конВеНера, могут через него обмениваться данными.Механизм конвейеров, впервые введенный в UNIX-системах, имеет максимальный размер 64 Кбайт,оскольку в 16-разрядных мини-ЭВМ, для которых создавалась эта ОС, нельзя было иметь массивванных большего размера.244Глава 7. Организация параллельных взаимодействующих вычислениеААУказатель на началоУказатель на конецI—^Указатель на конец—йУказатель на началоРис. 7.4.
Организация очереди в массивеВ качестве иллюстрации приведем основные системные запросы для работы с конвейерами, которые имеются в API OS/2.•Функция создания конвейера:OosCreatePipe (SReadHandle, &WriteHandle. PipeSize):Здесь ReadHandle — дескриптор чтения из конвейера, Write На nd le —дескриптор записи в конвейер, PipeSize — размер конвейера.•Функция чтения из конвейера:"DosRead (SReadHandle. (PVOID)&Inform. sizeof(Inform), SBytesRead):Здесь ReadHandle — дескриптор чтения из конвейера, Inform — переменнаялюбого типа, sizeof(Inform) — размер переменной Inform, BytesRead —количество прочитанных байтов.
Данная функция при обращении кпустому конвейеру будет ожидать, пока в нем не появится информациядля чтения.•Функция записи в конвейер:DosWrite (SWriteHandle, (PVOID)SInform. sizeof(Inform). SBytesWrite):Здесь WriteHandle — дескриптор записи в конвейер, BytesWrite — количествозаписанных байтов.Читать из конвейера может только тот процесс, который знает идентификатор соответствующего конвейера. При работе с конвейером данные непосредственнопомещаются в него. Еще раз отметим, что из-за ограничения на размер конвейерапрограммисты сталкиваются и с ограничениями на размеры передаваемых черезнего сообщений.Очереди сообщенийОчереди (queues) сообщений предлагают более удобный метод связи между взаимодействующими процессами по сравнению с каналами, но в своей реализаЦИони сложнее. С помощью очередей также можно из одной или нескольких задачнезависимым образом посылать сообщения некоторой задаче-приемнику.
При это*только процесс-приемник может читать и удалять сообщения из очереди, а проконвейеры и очереди сообщений24Эцессы-клиенты имеют право лишь помещать в очередь свои сообщения. Такимобразом, очередь работает только в одном направлении. Если же необходимадвухсторонняя связь, то можно создать две очереди.работа с очередями сообщений отличается от работы с конвейерами.
Во-первых,ереди сообщений предоставляют возможность использовать несколько дисципоЧлин обработки сообщений:р FIFO — сообщение, записанное первым, будет первым и прочитано;• LIFO — сообщение, записанное последним, будет прочитано первым;р приоритетный доступ — сообщения читаются с учетом их приоритетов;р произвольный доступ — сообщения читаются в произвольном порядке.Тогда как канал обеспечивает только дисциплину FIFO.Во-вторых, если при чтении сообщения оно удаляется из конвейера, то при чтениисообщения из очереди этого не происходит, и сообщение при желании может бытьпрочитано несколько раз.В-третьих, в очередях присутствуют не непосредственно сами сообщения, а только их адреса в памяти и размер.
Эта информация размещается системой в сегменте памяти, доступном для всех задач, общающихся с помощью данной очереди.Каждый процесс, использующий очередь, должен предварительно получить разрешение на доступ в общий сегмент памяти с помощью системных запросов API,ибо очередь — это системный механизм, и для работы с ним требуются системныересурсы и, соответственно, обращение к самой ОС. Во время чтения из очередизадача-приемник пользуется следующей информацией:Q идентификатор процесса (Process Identifier, PID), который передал сообщение;• адрес и длина переданного сообщения;• признак необходимости ждать, если очередь пуста;• приоритет переданного сообщения;• номер освобождаемого семафора, когда сообщение передается в очередь.Наконец, приведем перечень основных функций, управляющих работой очереди(без подробного описания передаваемых параметров, поскольку в различных ОСобращения к этим функциям могут существенно различаться):QCreateQueue — создание новой очереди;QOpenQueue — открытие существующей очереди;аReadQueue — чтение и удаление сообщения из очереди;uPeekQueue — чтение сообщения без его последующего удаления из очереди;WriteQueue — добавление сообщения в очередь;CbseQueue — завершение использования очереди;Q purgeQue ue — удаление из очереди всех сообщений;UueryQueue — определение числа элементов в очереди.246Глава 7.
Организация параллельных взаимодействующих вычисленийКонтрольные вопросы и задачи1. Какие последовательные вычислительные процессы мы называем параллельными и почему? Какие параллельные процессы называются независимымиа какие — взаимодействующими?2. Изложите алгоритм Деккера, позволяющий разрешить проблему взаимногоисключения путем использования одной только блокировки памяти.3.
Объясните, как действует команда проверки и установки. Расскажите о работе команд BTS и BTR, которые имеются в процессорах с архитектурой ia32.4. Расскажите о семафорах Дейкстры. Чем обеспечивается взаимное исключение при выполнении примитивов Р и V?5. Изложите, как могут быть реализованы семафорные примитивы для мультипроцессорной системы?6. Что такое мыотекс?7. Изложите алгоритм решения задачи «поставщик-потребитель» при использовании семафоров Дейкстры.8.
Изложите алгоритм решения задачи «читатели-писатели» при использовании семафоров Дейкстры.9. Что такое «монитор Хоара»? Приведите пример такого монитора.10. Что представляют собой почтовые ящики?11. Что представляют собой конвейеры (программные каналы)?12. Что представляют собой очереди сообщений? Чем отличаются очереди сообщений от почтовых ящиков?Глава 8. Проблема тупикови методы борьбы с нимиРассмотрим одну из самых серьезных и трудноразрешимых проблем, возникающих при организации мультипрограммного режима работы, — проблему тупикови основные подходы при борьбе с ними.
В этой главе представлены некоторыемодели параллельных вычислительных процессов, позволяющие проводить иханализ в аспекте корректного решения указанных проблем.Понятие тупиковой ситуациипри выполнении параллельныхвычислительных процессов*»При организации параллельного выполнения нескольких вычислительных процессов одной из главных функций операционной системы является решение сложной задачи корректного распределения ресурсов между выполняющимися процессами и обеспечение последних средствами взаимной синхронизации и обменаданными.При параллельном исполнении процессов могут возникать тупиковые ситуации,когда два или более процесса блокируют друг друга, вынуждая ожидать наступления события, связанного с освобождением ресурса. Самым простым является случай, когда каждый из двух процессов ожидает ресурс, занятый другим процессом.Из-за такого ожидания ни один из процессов не может продолжить исполнениеи освободить в конечном итоге ресурс, необходимый другому процессу.
Эта ситуация называется тупиком, дедлоком (dead lock 1 ), или клинчем. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ждетсобытия, которое никогда не произойдет. Тупики чаще всего возникают из-за конкуренции несвязанных параллельных процессов за ресурсы вычислительной системы, но иногда к тупикам приводят и ошибки программирования взаимодействующих вычислений.Uead lock (англ.) — смертельное объятие.248Глава 8. Проблема тупиков и методы борьбы с нимцПри рассмотрении проблемы тупиков целесообразно понятие ресурсов системыобобщить и разделить их все на два класса:Q повторно используемые (Reusable Resource, RR), или системные (System Resource, SR), ресурсы;•потребляемые, или расходуемые, ресурсы (Consumable Resource, CR).Системные ресурсы (SR) есть конечное множество идентичных единиц некоторого вида ресурсов, обладающих следующими свойствами [54]:•число единиц ресурса в системе неизменно;•каждая единица ресурса либо доступна, либо выделена одному и только одному процессу (разделение отсутствует или не принимается во внимание, так какне оказывает влияния на распределение ресурсов, а значит, и на возникновениетупиковой ситуации);•процесс может освободить единицу ресурса (сделать ее доступной), только еслион ранее получил эту единицу, то есть никакой процесс не может оказыватьвлияние на ресурс, если этот ресурс ему не принадлежит.Данное определение выделяет существенные для изучения проблемы тупика свойства системных ресурсов, к которым мы относим компоненты аппаратуры, такиекак основная память, вспомогательная (внешняя) память, периферийные устройства и, возможно, процессоры, а также программное и информационное обеспечение, такое как файлы данных, таблицы и «разрешение войти в критическую секцию».Расходуемые ресурсы (CR) отличаются от ресурсов типа SR в нескольких важныхотношениях [17].Q Число доступных единиц некоторого ресурса типа CR изменяется по мере того,как выполняющимися процессами они расходуются (приобретаются) и освобождаются (производятся).
В общем случае число единиц расходуемых ресурсовявляется потенциально неограниченным, поскольку некий процесс «производитель» может достаточно долго увеличивать число единиц ресурса, освобождая одну или более единиц, которые он «создал».Q Процесс «потребитель» уменьшает число единиц ресурса, сначала запрашиваяи затем приобретая (потребляя) одну или более единиц. Единицы ресурса, которые приобретены, в общем случае не возвращаются ресурсу, а потребляются(расходуются). Эти свойства потребляемых ресурсов присущи многим синхронизирующим сигналам, сообщениям и данным, порождаемым как аппаратурой,так и программным обеспечением, и могут рассматриваться как ресурсы типаCR при изучении тупиков. В их число входят: прерывания от таймера и устройств ввода-вывода; сигналы синхронизации процессов; сообщения, содержащие запросы на различные виды обслуживания или данные, а также соответствующие ответы.Для исследования параллельных процессов и, в частности, проблемы тупиков былоразработано несколько моделей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
