русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Параллельное выполнение процессов. Формулировка задачи «производитель-потребитель» и методы ее решения

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

Основной задачей управления параллельным выполнением является задача  взаимного  исключения  (mutual  exclusion,  сокращенно  - mutex):  два процесса не могут выполнять одновременный  доступ  к разделяемым  ресурсам.  Взаимное  исключение является расширением задачи транзактивности на любые ресурсы. Если процессор одновременно получает два запроса, то он выполняет их последовательно. Каждая процессорная команда имеет свойства транзакции: она или выполняется полностью,  или вообще не выполняется. Задача семафоров использует блокировку ожидающего процесса - перевод его из списка процессов, планируемых  на выполнение (готовых) в список ожидающих (заблокированных). Этим экономится процессорное время, в противном случае попусту  растрачиваемое в занятом ожидании, а затраты сводятся к переключению процессов.

Такая возможность обеспечивается:

а).введением специальных целочисленных общих переменных, которые называются семафорами (semaphore);

б). добавлением к набору элементарных  действий,  из  которых строятся процессы,  операций над семафорами: V-операции и P-операции. V-операция есть  операция с одним операндом,  который должен быть семафором.

Выполнение операции состоит в  увеличении значения     аргумента на 1, это действие должно быть атомарным. P-операция есть  операция с одним операндом,  который должен быть     семафором. Выполнение операции состоит в  уменьшении значения     аргумента на 1,  если только это действие не приведет к отрицательному значению операнда. Выполнение P-операции, то есть, принятие решение о том,  что момент является  подходящим  для уменьшения  аргумента,  и  последующее  его уменьшение должно быть атомарным. Атомарность P-операции  и  является  потенциальной задержкой: если процесс пытается выполнить P-операцию над семафором,  значение которого в данный момент нулевое,  данная P-операция не может завершиться пока другой процесс не выполнить V-операцию  над этим семафором.

Несколько процессов могут начать одновременно P-операцию над одним и тем же семафором.  Тогда при установке семафора в 1 только одна из P-операций завершится, какая именно - мы обсудим позже. Защита разделяемых  ресурсов  теперь выглядит следующим образом. Каждый ресурс защищается своим  семафором, значение которого может быть 1 - свободен или 0 - занят. 

Процесс, выполняющий доступ к ресурсу,  инициирует P-операцию.  Если ресурс  занят - процесс задерживается в своей P-операции до освобождения ресурса.  Когда ресурс освобождается, P-операция процесса завершается и процесс занимает ресурс. При освобождении ресурса процесс выполняет V-операцию. "Производители-потребители". Пусть мы  имеем два циклических процесса,  которые мы назовем "производитель" и "потребитель".  Производитель в каждой итерации своего цикла вырабатывает (производит) порцию информации, которую он помещает в общий для обоих процессов  буфер. 

Предположим  для начала,  что  емкость  буфера неограничена. Потребитель в каждой итерации своего цикла выбирает из буфера порцию информации, выработанную производителем,  и обрабатывает (потребляет) ее.  Задача состоит в синхронизации действий производителя и потребителя  таким образом, чтобы не допустить потерь и искажений информации, во-первых, и голодания процессов, во-вторых.

Решение достигается при помощи единственного общего семафора, играющего роль счетчика числа порций в буфере. Исходное значение семафора 0. Производитель каждую итерацию своего цикла заканчивает V-операцией, увеличивающей значение счетчика. Потребитель каждую свою итерацию начинает P-операцией. Если буфер пуст, то потребитель задержится в своей P-операции до появления в буфере очередной порции. Таким образом, если потребитель работает быстрее производителя,  он  будет  время  от времени простаивать,  если производитель работает быстрее - в буфере будут накапливаться порции.

В реальных задачах такого рода (например, кольцевой буферизации, рассмотренной нами в главе 6) буфер всегда  имеет  некоторую конечную емкость. Если производитель работает быстрее, то при заполнении буфера он должен приостанавливаться, ожидая освобождения места в   буфере.  Это  легко  обеспечить,  введя  новый  семафор, выполняющий роль счетчика свободных мест в буфере.

Просмотров: 8755

Вернуться в оглавление:Шпаргалки по компьютеру




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.