36251

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

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-09-23

51 KB

19 чел.

PAGE  3

37.Процессы. Задачи синхронизации. Задача взаимного исключения, задача «Производитель-потребитель», задача «Читатели-писатели».

Процессы

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

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

На уровне долгосрочного планирования объектами управления являются не отдельные процессы, а некоторые их объединения, рассматриваемые как единое целое, объединенное единым функциональным назначением. Такие объекты в различных ОС называют по разному, например - задание, задача, работа, и т.п. Задача планировщика при этом - предоставить работе (задаче, заданию) некоторую виртуальную машину, имеющую в своем составе необходимые для выполнения работы компоненты (процессор, оперативную и внешнюю память, и т.п.).

На уровне краткосрочного планирования объектом управления являются процессы, которые выступают как потребители либо центрального процессора, если речь идет о внутренних процессах, либо других процессоров для внешних процессов. Необходимо отметить два важнейших свойства выполнения работ ОС на уровне краткосрочного планирования. Во-первых, причины, обусловливающие порождение и окончание процессов и отрабатываемые на этом уровне, являются внутренними. Другими словами, заявки или требования на порождение и уничтожение процессов поступают либо от процессов, управляемых на данном уровне, либо с уровня долгосрочного планирования. Во-вторых, особенностью стратегии распределения процессора на данном уровне, которую часто называют диспетчеризацией, является необходимость многократного распределения единственного процессора (за исключением многопроцессорных вычислительных систем) для каждого из планируемых процессов на интервалах их существования для достижения необходимого эффекта мультипрограммирования. Именно поэтому планирование распределения времени процессора в отношении каждого процесса называют краткосрочным.

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

Ранее нами были определены основные отношения типа:

отношение предшествования,

отношение приоритетности,

отношение взаимного исключения.

Эти отношения и определяют существо синхронизирующих правил. Реализация синхронизирующих правил осуществляется с помощью механизмов (средств) синхронизации. Такие механизмы весьма многочисленны по способам реализации, отличаются степенью эффективности и областями использования в различных ОС и будут рассмотрены в последующих разделах.

Особенности каждого конкретного взаимодействия между двумя или более параллельными процессами определяются задачей синхронизации. Количество различных задач синхронизации неограниченно. Однако некоторые из них являются типичными. К ним относятся: взаимное исключение, производители-потребители, читатели-писатели, обедающие философы и т.д. Большинство задач в реальных ОС по согласованию параллельных процессов можно ре шить либо с помощью этих типовых задач, либо с помощью их модификаций.

Задача взаимного исключения. Это фундаментальная по своему назначению задача. Любая ОС, управляющая параллельными процессами, должна обеспечить тот или иной вариант реализации ее решения. Необходимо согласовать работу n>1 параллельных процессов при использовании некоторого критического ресурса таким образом, чтобы удовлетворить следующим требованиям:

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

критические области не должны иметь приоритеты в отношении друг друга

остановка какого-либо процесса вне его критической области не должна влиять на дальнейшую работу процессов по использованию критического ресурса

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

относительные скорости развития процессов неизвестны и произвольны

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

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

Задача "Производитель-потребитель". Имеется большое число вариантов постановки и решения такой задачи в рамках конкретных ОС. Наиболее простой случай, когда взаимодействуют два процесса с жестко распределенными между ними функциями. Один процесс вырабатывает сообщения, предназначенные для восприятия и обработки другим процессом. Процесс, вырабатывающий сообщения, называют производителем, а воспринимающий сообщения — потребителем. Процессы взаимодействуют через некоторую обобщенную область памяти, которая по смыслу является критическим ресурсом. В эту область процесс-производитель должен помещать очередное сообщение (в простейшем случае предполагается, что область способна хранить только одно сообщение и сообщения фиксированной длины), а процесс-потребитель должен считывать очередное сообщение. Необходимо согласовать работы двух процессов при одностороннем (в простейшем случае) обмене сообщениями по мере развития процессов таким образом, чтобы удовлетворить следующим требованиям:

выполнять требования задачи взаимного исключения по отношению к критическому ресурсу — обобщенной памяти для хранения сообщения

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

Попытка процесса-производителя поместить очередное сообщение в область, из которой не было считано предыдущее сообщение процессом-потребителем, должна быть блокирована. Процесс-производитель должен быть либо оповещен о невозможности помещения сообщения, либо переведен в состояние ожидания возможности поместить очередное сообщение через некоторое время в область памяти, по мере ее освобождения. Аналогично должна быть блокирована попытка процесса-потребителя считать сообщение из области в ситуации, когда процесс-производитель не поместил туда очередного сообщения. Возможны также несколько вариантов реакции на данную ситуацию — сообщение о невозможности считывания либо перевод процесса-потребителя в состояние ожидания поступления очередного сообщения. Если используется вариант с ожиданиями изменения состояния обобщенной области для хранения сообщения, необходимо обеспечить перевод ожидающих процессов в состояние готовности всякий раз, когда изменится состояние области. Либо процесс-производитель поместит очередное сообщение в область. Оно теперь может быть считано ожидающим процессом-потребителем. Либо процесс-потребитель считал очередное сообщение из области и обеспечил возможность ожидающему процессу-производителю послать очередное сообщение.

Множественность постановки задачи “производитель-потребитель” определяется тем, что число как процессов-потребителей, так и процессов-производителей может быть большим одного. Каждый из таких процессов может устанавливать не только одностороннюю, но и двустороннюю связь через одну и ту же обобщенную область или другие области. Области могут хранить не одно, а большее количество сообщений.

Задача "Читатели-писатели". Эта задача также имеет много вариантов. Наиболее характерная область использования этой задачи — при построении файловых систем ОС. В отношении некоторой области памяти, являющейся по смыслу критическим ресурсом для параллельных процессов, работающих с ней, выделяется два типа процессов.

Первый тип — процессы-читатели. Они считывают одновременно информацию из области, если это допускается при работе с конкретным устройством памяти.

Второй тип — процессы-писатели. Они записывают информацию в область и могут делать это, только исключая как друг друга, так и процессы-читатели, т. е. запись должна удовлетворяться на основе решения задачи взаимного исключения. Имеются различные варианты взаимодействия между процессами-писателями и процессами-читателями. Наиболее широко распространены следующие. Устанавливается приоритетность в использовании критического ресурса процессам-читателям. Если хотя бы один процесс-читатель пользуется ресурсом, то он закрыт для использования всем процессам-писателям и доступен для использования всем процессам-читателям. Во втором варианте, наоборот, больший приоритет у процессов-писателей. При появлении запроса от процесса-писателя необходимо закрыть ресурс для использования всем процессам-читателям, которые выдадут запрос позже него.

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

Пример. Пусть имеются три параллельных процесса X, Y, Z и три ресурса: Р1—устройство ввода с перфокарт; Р2—печатающее устройство, РЗ — накопитель на МД. Особенность развития процессов такова, что для пребывания процесса Х в активном состоянии ему требуется выделить одновременно ресурсы P1 и P2, для пребывания процесса Y в активном состоянии ему требуется выделить одновременно ресурсы P2 и РЗ, для пребывания процесса Z в активном состоянии ему требуется выделить одновременно ресурсы РЗ и P1.

Скорости развития процессов произвольны. Переходы из активного в другие состояния происходят в непредсказуемые моменты. Необходимо обеспечить максимально параллельное и правильное развитие процессов. Синхронизация в данном случае заключается в определенном упорядочении действий процессов по захвату ресурсов во избежание возможных блокировок одними процессами других. В данном случае возможны две опасности: возникновение тупиковой ситуации при распределении ресурсов и возникновение ситуации “голодания” в отношении некоторого процесса при распределении ресурса.

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

Нетрудно заметить, что вилки в данной “столовой ситуации” выступают в качестве пересекающихся ресурсов. Неприятная ситуация может возникнуть в случае, когда философы одновременно проголодаются и одновременно попытаются взять, например, свою левую вилку. В данном случае возникает тупиковая ситуация, так как никто из них не может, по условию начать есть, не имея второй вилки. Однако, вторая вилка может появиться для любого философа только от соседа справа, который в свою очередь ждет появления для себя вилки от своего соседа справа и одновременно не хочет положить свою левую вилку на стол и т. д. Вторая неприятная ситуация (голодание) может возникнуть уже в отношении не всех, а только одного процесса. В обществе философов такая ситуация возникает в случае заговора двух соседей слева и справа против философа, в отношении которого строятся козни. Каждый раз, когда последний желает утолить голод, заговорщики, опережая его, поочередно забирают вилки то слева, то справа от него. Такие согласованные действия злоумышленников приводят жертву к вынужденному голоданию, так как он никогда не может воспользоваться обеими вилками.

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

Множественность задач синхронизации объясняет большой набор средств синхронизации, с помощью которых эти задачи решаются. 


 

А также другие работы, которые могут Вас заинтересовать

83840. Хирургическая анатомия свода и основания черепа. Виллизиев круг, синусы твёрдой мозговой оболочки, черепные нервы, оболочки головного мозга 985.14 KB
  Виллизиев круг синусы твёрдой мозговой оболочки черепные нервы оболочки головного мозга. Принято выделять три черепные ямки: переднюю от внутренней поверхности чешуи лобной кости до крыльев и площадки основной кости среднюю область пирамид височных костей заднюю от спинки турецкого седла до задних граней пирамид височных костей и борозды поперечного синуса. Оболочки головного мозга Головной мозг окружен тремя оболочками: 1 мягкой непосредственно прилежащей к его поверхности; 2 паутинной образующей узкое пространство над...
83841. Трепанация черепа. Показания, техника выполнения, осложнения. Схема кранио-церебральной топографии Кренлейна 93.22 KB
  Локализация разрезов и костного дефекта определяется локализацией патологического процесса Показания: оперативный доступ при вмешательствах по поводу операбельных опухолей головного мозга мозговых грыж водянки мозга кисты мозга и пр Техника выполнения: 1. Осложнения: Кровотечение; Инфекция; Отек головного мозга; Повреждение мозга после чего может возникнуть: Изменения в памяти поведении мышлении речи; Проблемы со зрением; Проблемы с балансом; Проблемы кишечника и мочевого пузыря; Судороги; Паралич или слабость; Реакция...
83842. Первичная хирургическая обработка ран головы 48.42 KB
  При осмотре пациента с раной головы необходимо определить: 1 ее глубину 2 наличие в ране поврежденных артериальных сосудов 3 наличие или отсутствие повреждения костей свода черепа. Наличие или отсутствие костных повреждений необходимо уточнять не только при осмотре раны но и с использованием рентгенографии черепа и компьютерной томографии головы.
83843. Хирургическая анатомия лицевого и тройничного нерва. Разрез при гнойном паротите 50.26 KB
  Хирургическая анатомия лицевого нерва Лицевой нерв смешанный. Двигательная часть начинается от ядра лицевого нерва в Варолиевом мосту. У клеток двигательного ядра имеются многочисленные чувствительные коллатерали идущие из чувствительных ядер тройничного нерва.
83844. Кровеносные сосуды лица 50.02 KB
  Артерии Верхнечелюстная артерия является одной из двухконечных ветвей наружной сонной артерии. В первом отделе следующие ветви: 1 – глубокая ушная артерия разветвляется в коже наружного слухового прохода в барабанной перепонке и в капсуле височно – нижнечелюстного сустава; 2 – передняя барабанная артерия проникает через каменисто – барабанную щель к слизистой оболочке барабанной полости; 3 – нижняя альвеолярная артерия вхожи в канал нижней челюсти и отдаёт ветви к зубам и десне нижней челюсти; её конечная ветвь – подбородочная артерия...
83845. Клетчаточные пространства лица. Хирургическая тактика при флегмонах лица 52.56 KB
  выше линии соединяющей углы рта. VI Клетчаточные пространства под слизистой оболочкой мышцами и органами дна полости рта: Боковые клетчаточные пространства между языком и нижней челюстью В них окруженные клетчаткой располагаются подъязычные слюнные железы с большими выводными протоками. Гнойные процессы возникающие в межмышечных клетчаточных пространствах дна полости рта могут распространятся в пределах дна полости рта. Височноязычный промежуток сообщается с жировым телом щеки крылонебной ямкой а через круглое отверстие с полостью...
83846. Хирургическая тактика при флегмонах лица 54.42 KB
  Раскрытие и дренирование флегмон скуловой области. Раскрытие и дренирование флегмон височной области. В указанной области возможно возникновение поверхностной межапоневротической подапоневротической глубокой и разлитой флегмон. Поверхностная флегмона височной области образуется между кожей и собственной височной фасцией.
83847. Подчелюстная область, треугольник Пирогова. Перевязка язычной артерии, показания, техника выполнения 48.93 KB
  В пределах подчелюстной области залегают: подчелюстная слюнная железа лицевые артерия и вена подподбородочные артерия и вена подъязычный и челюстноподъязычный нервы лимфатические узлы и клетчатка окружающая эти образования. Последняя сообщается с клетчаткой подъязычной области крыловидночелюстного окологлоточного пространств боковой области лица и шеи. Подчелюстные лимфатические узлы являются регионарными узлами челюстнолицевой области полости рта. Треугольник Пирогова Треугольное пространство в боковой части надподъязычной...
83848. Коникотомия. Показания, техника выполнения, осложнения, их профилактика 116.46 KB
  Врач встав справа от больного указательным пальцем левой руки нащупывает бугорок перстневидного хряща и углубление между ним и нижним краем щитовидного хряща соответствующее расположению конической связки. Большим и средним пальцами левой руки фиксируют щитовидный хрящ натягивая кожу над хрящами гортани и смещая кзади грудиноключичнососцевидные мышцы с расположенными под ними шейными сосудистыми пучками второй палец находится между дугой перстневидного и нижним краем щитовидного хряща. Скальпелем проводят горизонтальный поперечный разрез...