Процессы называются параллельными, если они существуют одновременно. Параллельные процессы могут работать совершенно независимо друг от друга или они могут быть асинхронными – это значит им необходимо периодически синхронизироваться и взаимодействовать. Для иллюстрации параллельных асинхронных процессов применяется нотация аналогичная той, которая применяется в языках параллельного программирования Модула, Ада и т. п. Параллельная обработка Параллельное выполнение нескольких программ заманчиво, как один из вариантов повышения быстродействия, и как следствие – производительности ОС. Многопроцессорные вычислительные комплексы (суперкомпьютеры) дают основание надеяться на внедрение мультипроцессорных систем в персональные компьютеры, и в результате – на развитие основных концепций параллельного программирования и создание соответствующего программного обеспечения. Здесь встречаются принципиальные трудности: - сложность определения фрагментов будущих программ, возможных быть распараллеленными; - трудность отладки таких программ. Т.к. после предположительного исправления ошибки трудно восстановить последовательность событий, на которых эта ошибка проявилась впервые. Поэтому нельзя утверждать с уверенностью, что данная ошибка устранена. - трудность доказательства корректности параллельных программ по сравнению с последовательными программами. Взаимоисключение Пусть имеется многотерминальная система разделения времени, в которой пользователи вводят текстовые данные. Каждый пользователь использует один терминал. Ввод очередной строки заканчивается нажатие на клавишу Enter. Необходимо вести постоянный учет общего количества строк, введенных пользователями с начала работы системы. Предполагается, что контроль каждого терминала ведется при помощи отдельного процесса. Сигналом к увеличению на 1 глобальной переменной STROKWWEDENYH – служит ввод сигнала Enter с соответствующего терминала. Пусть каждый процесс имеет в своем составе копию кода: mov ax, STROKWWEDENYH inc ax mov STROKWWEDENYH, ax Пусть в данный момент глобальная переменная STROKWWEDENYH имеет значение 21687. Пусть один процесс успевает выполнить только первые две команды mov ax, STROKWWEDENYH inc ax После чего в регистре ax (аккумуляторе) будет 21688. Затем этот процесс ввиду истечения отведенного ему кванта времени уступает процессор другому процессу. Второй процесс выполняет теперь все три команды, устанавливая значение STROKWWEDENYH=21688. Далее 2-й процесс возвращает управление 1-ому процессу, который возобновляет свое выполнение с команды mov STROKWWEDENYH, ax и также помещает значение 21688 в STROKWWEDENYH. Т.о., из-за не координированного доступа к разделяемой переменной STROKWWEDENYH – потеряли одну строку. Эту задачу можно решить, если каждому процессу предоставить монопольное исключительное право доступа к переменной STROKWWEDENYH. Когда один процесс увеличивает эту разделяемую переменную, всем остальным процессам, которым нужно было бы также, нарастить значение STROKWWEDENYH в то же самое время – придется ждать. А когда данный процесс закончит свое использование переменной, будет разрешено продолжать работу одному из процессов, находящихся в состоянии ожидания. Т. о. каждый процесс, обращающийся к разделяемым данным, исключает для других процессов возможность одновременного с ним обращения к данным. Это называется взаимоисключением. Когда процесс производит обращение к разделяемым данным, то говорят, что он находится на своем критическом участке. Применение примитивов взаимоисключения для управления взимодействием процессами program взаимоисключение; var строквведенных: целое; procedure процессодин; while истина do begin взятиеследующейстрокитерминала; входвзаимоисключения; строквведенных:=строквведенных + 1; выходвзаимоисключения; обработкастроки end; procedure процессдва; while истина do begin взятиеследующейстрокитерминала; входвзаимоисключения; строквведенных:=строквведенных + 1; выходвзаимоисключения; обработкастроки end; begin строквведенных:=0; parbegin процессодин; процессдва parend end.
Для простоты полагаем, что взаимодействуют два параллельных процесса. Управлять n процессами – значительно сложнее. Две конструкции входвзаимоисключения и выходвзаимоисключения обрамляют критические участки в каждом из процессов. Эти операторы называются примитивы взаимоисключения. Внутри этого участка обеспечен монопольный доступ к переменной СТРОКВВЕДЕННЫХ. Если один из процессов находится внутри своего критического участка, а другой процесс пытается войти в этот же участок, то он переводится в состояние ожидания, пока первый процесс не выполнит выходвзаимоисключения. Только после этого первый процесс сможет войти в свой критический участок. Операторные скобки parbegin оператор 1; оператор 2; ………….. оператор n parend служат для синтаксического оформления параллельно выполняющихся процессов в рамках программы, где они употреблены. Оператор parbegin указывает, что последовательное течение программы должно быть разделено на несколько параллельно выполняемых последовательностей (цепочек управления). В данном случае на n отдельных самостоятельных цепочек - по одной для каждого внутреннего оператора для данной конструкции. Оператор parend указывает, что вышеперечисленные параллельно выполняемые цепочки должны слиться воедино и должно возобновиться последовательное выполнение программы. Если процессодин и процессдва выполняют входвзаимоисключения одновременно, то одному из них случайным образом будет разрешено продолжать работу, а другому – остается ждать. Реализация примитивов взаимоисключения (общие замечания). Для реализации примитивов взаимоисключения «входвзаимоисключения» (код входа взаимоисключения) и «выходвзаимоисключения» (код выхода взаимоисключения) необходимо, чтобы соблюдались следующие четыре правила: 1. Задача д. б. решена чисто программным способом на ЭВМ (компьютере), не имеющей специальных команд взаимоисключения. Каждая команда машинного языка выполняется, как неделимая операция, т. е. каждая ______8начатая команда завершается без прерывания ее. Будем считать, что в случае одновременных попыток нескольких процессоров обратиться к одному и тому же элементу данных возможные конфликты разрешаются аппаратно при помощи схемы защитной блокировки памяти. Эта схема распараллеливает конфликтующие обращения к памяти со стороны отдельных процессоров, выстраивая их в очередь, т. е., разрешая производить только одно обращение в каждый конкретный момент времени. Предполагается, что эти отдельные обращения обслуживаются в случайном порядке. 2. Не должно быть никаких предположений об относительных скоростях выполнения асинхронных параллельных процессов. 3. Процессы, находящиеся вне своих критических участков, не могут препятствовать другим процессам входить в их собственные критические участки. 4. Не должно быть бесконечного откладывания момента входа процессов в их критические участки. Неплохие реализации программных механизмов взаимоисключения предложил голландский математик Деккер. Существенно улучшил этот алгоритм Э. Дейкстра.
