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

Мультипроцессорные системы.

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

Простейшая мультипроцессорная система.

                                                                        _линии

                                                                          _связи

В этой структуре посылка запроса от ЦП_i к ЦП_к – единственный способ получения доступа одного процессора к ресурсам другого. Эта мультипроцессорная система со слабосвязанными процессорами. Основной функцией такой ОС является управление сообщениями и их расшифровка. Сообщения принимаются соответствующей частью ОС, работающей с данным процессором, и эта система блокирует активные процессы и передаёт свой процесс в качестве ресурса другому процессору. Есть системы с сильно связанными процессорами:

                                                                                 Процессорный блок

А)  

       Б)

Структура  а)  master-slave (главный-подчиненный).

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

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

Структура  б)  симметричный.

 В этой структуре любой процессор может выполнять любую функцию ОС. Все процессоры равноправны. Неисправность одного

процессора не приводит к выходу из строя всей системы. Различные части ОС могут выполняться различными процессорами, которые

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

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

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

1)  Отношение предшествования (порождающие и порожденные процессы);

2)  Отношение приоритетности;

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

Реализация синхронизирующих правил осуществляется с помощью механизмов синхронизации, которых к данному времени разработано много и реализация которых обычно имеет параллельно-аппаратную форму. Эти механизмы выполняют двоякую роль:

1)  Они обеспечивают способ упорядочивания развития процессов;

2)  Они обеспечивают взаимодействие между процессами.

Типичные задачи синхронизации:

1)  Задача взаимного исключения;

2)  Производитель-потребитель;

3)  Читатели-писатели;

4)  «Обедающие философы» - задача распределения пересекаю-щихся ресурсов.

1) Задача взаимного исключения.

Нужно согласовать работу N>2 параллельных процессов при использовании некоторого критического ресурса при следующих требованиях:

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

n  критические области не имеют приоритетов в отношении друг к другу;

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

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

n  относительные скорости процессов неизвестны и производны;

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

2)Задача производитель-потребитель.

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

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

Требования:

--выполнить требования взаимного исключения по отношению к критическому ресурсу;

--учитывать состояние обобщенной области памяти.

Механические управления

3)Задача читатели-писатели.

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

Процессы «читатели» могут считывать информацию из этой области одновременно. Наиболее широко распространённый метод решения этой задачи – установка приоритетов для «читателей».

4)Задача «Обедающие философы».

Пусть х, у, z – параллельные процессы.

Р₁ – устройство ввода;

Р₂ – печатающее устройство;

Р₃ – накопитель на магнитном диске;

Для активного состояния процесса Х требуется Р₁  и  Р₂ , для У - Р₂  и Р₃ , для Z - Р₁  и Р₃. Скорости развития процессов – произвольная.

Возникают две ситуации:

1)  «тупиковая», когда ни один из процессов не может получить ресурса;

2)  «голодание», когда один процесс блокируется на неопределённое время.

Семафорная техника синхронизации и упорядочивания процессов.

В 1955 году Дейкстра ввёл понятие «семафорная техника». Дейкстер реализовал это программно.

Все виды решения задач синхронизации базируются на двух примитивах: P и V.

Примитив Р ставится впереди критической области, а V – в конце критической области. В каждом процессе они есть. Эти примитивы неделимы и взаимно исключают друг друга. Они основаны на использовании семафоров.

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

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