Тема OS15асу. Диспетчеризация и синхронизация процессов. Планирование и выполнение процессов. Действия планировщика. Уровни планирования 1. Выбирается процесс с наивысшим приоритетом из находящихся в состояниях резервирования и готовность к выполнению. 2. Если таких процессов несколько, то выбирается тот, который дольше всех находится в очереди. 3. Если таких процессов нет, то ждём следующего прерывания по таймеру (тика). 4. Удаляем выбранный из очереди готовных к выполнению. 5. Переключение на контекст выбранного процесса. Диспечеризация процессов реализует политику разделения времени процессора среди всех процессов, функционирующих в системе, на основе их приоритетов. Приоритеты процессов выражаются целыми числами. Их значения сохраняются в поле p_pri структуры struct proc дескриптора процесса. Во всех версиях OS UNIX, кроме System V Release 4 (SVR4), принято, что приоритет процесса тем выше, чем меньше его численное значение (в SVR4 - наоборот). Процесс выбирается для обработки процессором из очереди диспетчера на основе их сравнения приоритетов. Методы назначения приоритета различны в фазе "система" и в фазе "пользователь". В фазе "система" приоритет процесса задается системной функцией sleep, которая вызывается для погружении процесса в состояние ожидания события при внутренней синхронизации процессов. При "пробуждении" процесса после наступления ожидаемого события системной функцией wakeup, процесс сохраняет установленный приоритет, пока он находится в фазе "система". Величина приоритета устанавливается в зависимости от события, ожидаемого процессом при погружении в состояния "сна", по глобальным параметрам диспетчера разделения времени как показано в следующей таблице. Таблица системных приоритетов Глобальный параметр Системный приоритет Событие, ожидаемое процессом PSWP 0 Своппинг PRIBIO 20 Блоко-ориенированный ввод-вывод PZERO 25 Уровень пробуждения сигналом PPIPE 26 Пустой/полный программный канал TTIPRI 28 Ввод с терминала TTOPRI 29 Вывод на терминал PWAIT 30 Вывод на терминал PSLEEP 39 Пауза в ожидании сигнала Глобальные параметры, определяющие значения системных приоритетов, задаются при генерации OS UNIX и подобраны таким образом, чтобы поддерживать равновесие в режиме разделения времени процессора. Глобальный параметр PZERO определяет границу между низкими и высокими приоритетами в фазе "система". Системный приоритет со значением больше PZERO считается низким, не превышающий PZERO - высоким. Процессы, погруженные в состояние "сна" с высоким приоритетом, не могут быть выведены из этого состояния каким-либо сигналом. Процессы в состоянии "сна" с низким приоритетом могут быть "разбужены" сигналом. Текущий и готовые к выполнению процессы сохраняют фиксированный приоритет, пока они находятся в фазе "система". После перехода в фазу "пользователь" приоритет процесса будет переопределен. В фазе "пользователь" приоритет процесса имеет 2 составляющие - пользовательскую и системную. Значения этих составляющих задают поля дескриптора процесса p_nice и p_cpu, соответственно. Полное значение приоритета в фазе "пользователь" устанавливается на основе определенной комбинации его составляющих в полях p_nice и p_cpu. Начальное значение пользовательской составляющей приоритета определяется константой NZERO, обычно равной 20. Пользовательская составляющая может быть изменена системным вызовом nice. Его аргумент определяет величину модификации поля p_nice и может задаваться в пределах от 0 до NZERO для непривилигированного процесса или в пределах от (-NZERO) до (+NZERO) для привилигированного процесса. Поскольку значение пользовательской составляющей приоритета наследуется при порождении процесса, то непривилигированный процесс может только уменьшить приоритет, полученный от предка. Привилигированный потомок может как уменьшить, так и увеличить свой приоритет относительно предка. Начальное значение системной составляющей приоритета (p_cpu) в фазе "пользователь" равно 0. Ее изменение зависит от времени использования процессора, т.е. времени, пока процесс остается текущим, работая в фазе "пользователь". Для формирования системной составляющей приоритета используются прерывания от аппаратного таймера. При частоте сети питания 50 Гц прерывания от таймера генерируются 50 раз в секунду. Каждое таймерное прерывание увеличивает значение поля p_cpu, т.е. уменьшает системную составляющую приоритета на 1. Результирующий приоритет процесса в фазе "пользователь" определяется по формуле: p_pri = (p_nice - NZERO) + (p_cpu/16) + PUSER Разность (p_nice - NZERO) учитывает модификацию пользовательской составляющей приоритета системным вызовом nice. Отношение (p_cpu/16) учитывает усредненное значение системной составляющей приоритета. Усреднение необходимо, так как неизвестно, какую часть таймерного интервала проработал процесс на момент очередного прерывания от таймера. Кроме того, нежелательно частое переключение процессора между процессами с близкими значениями приоритетов. В частности, для равноприоритетных процессов в фазе "пользователь" выбранная величина усреднения (1/16) гарантирует переключение процессора не ранее, чем через 16 таймерных интервалов (320 мс), когда отношение (p_cpu/16) увеличится на 1. Константа PUSER, по умолчанию равная 50, вводится для принудительного увеличения приоритета в фазе "пользователь" по отношению к приоритету в фазе "система". Это сделано с целью стимулировать переключение процессора на выполнение процессов в фазе "система", в частности, для ускорения доступа "разбуженных" процессов к ресурсам процессора. Для вычисления приоритета используется системная функция setpri, которой в качестве аргумента передается дескриптор процесса. Приоритет процесса, вычисленный функцией setpri, сравнивается с приоритетом текущего процесса, который сохраняет системная переменная curpri. Если приоритет какого-либо процесса из очереди диспетчера выше приоритета текущего, реализуется переключение процессора на более приоритетный процесс по схеме внутренней синхронизации процессов. Механизмы синхронизации процессов ОС UNIX имеет развитые средства межпроцессной синхронизации по данным и управлению. Для этих целей в ОС существуют следующие механизмы. -сигналы, Взаимное исключение - техника программирования, которая заключается в том, что в данный момент только одна программа (или подпрограмма) имеет право доступа к определенному ресурсу (например, к области памяти, порту ввода/вывода или файлу). Обычно реализуется с помощью семафоров - флагов, используемых программами для координации активности. Для синхронизации процессов на низком уровне используется достаточно простой механизм событий или сигналов.(В дальнейшем мы будем употреблять термин сигнал - наиболее часто встречающийся в современных операционных системах). Под сигналом понимается именованная структура данных состоящая из флага, принимающего значения (0,1), счетчика и очереди дескрипторов процессов, ожидающих установления флага в состояние 1. -семафоры, Различают несколько типов семафоров. Другим часто используемым механизмом синхронизации низкого уровня являются семафоры (semapfore). Под семафором понимается структура данных, включающая в себя специальный счетчик S и очередь процессов, ожидающих "зеленого" света семафора. Cчетчик двоичного семафора может принимать только значения {0,1} и во многом аналогичен механизму сигналов. Множественные мониторы используются для синхронизации многозначных ресурсов и отличаются тем, что счетчик семафора принимает значения в диапазоне целых чисел {0,N}. -программные каналы, -именованные программные каналы, -очереди сообщений, -сегменты разделяемой памяти, -специальные команды (write cu mail), -Средства межмашинного взаимодействия (uucp,tcp/ip,nfs,rfs). Синхронизация и передача сообщений В распределенных системах без общей памяти механизмы взаимодействия процессов естественным образом базируются на пересылке сообщений (messages passing). При этом предполагается, что для обмена информацией процесс-отправитель формирует сообщение, передавая его по логическому каналу(channel) процессу-приемщику. Именованные каналы создаются при помощи специальной функции CreateChan(chan). При этом каждая операция формирования и отправки send(chan,msg) приводит к копированию данных из локальной памяти процесса в канал и созданию нового сообщения. Сообщение представляет собой динамическую структуру данных, в которую кроме собственно данных входит и заголовок сообщения, содержащий PID, размер сообщения и другую идентифицирующую информацию. Процесс, принимающий сообщение при помощи функции receive(chan,mes) выбирает сообщение из канала и переписывает его тело в локальную память. Реализация этого механизма в ОС осуществляется при помощи виртуальных каналов обмена, реализуемых на основе протоколов TCP/IP. Ниже приведен механизм так называемого асинхронного обмена сообщениями, при которых процесс-писатель и процесс-читатель обмениваются через именованный канал chan1. В процессе-писатель осуществляет асинхронную запись в канал, а процесс-читатель читает сообщения из канала с нужной ему скоростью. Такая логика хороша в тех случаях когда, во-первых, ограничения на емкость канала не являются сколько-нибудь значимыми в контексте данной задачи, а логика ее не предполагает жесткой координации между процессами. Для синхронного обмена сообщениями в примитивы send и receive вводят дополнительный параметр - имя семафора или сигнала, при помощи которого осуществляется синхронизация. Операция send при этом устанавливает флаг равным 1, а операция receive сбрасывает его в ноль. Расставив соответствующим образом операции wait мы можем допиться синхронизации процессов. События и сигналы Для синхронизации процессов на низком уровне используется достаточно простой механизм событий или сигналов.(В дальнейшем мы будем употреблять термин сигнал - наиболее часто встречающийся в современных операционных системах). Под сигналом понимается именованная структура данных состоящая из флага, принимающего значения (0,1), счетчика и очереди дескрипторов процессов, ожидающих установления флага в состояние 1. Внутренняя синхронизация процессов Внутренняя синхронизация процессов основана на использовании аппарата событий для изменения состояний процессов в фазе "система". Состояние процесса отражает поле p_stat структуры struct proc дескритора процесса. Процесс может находиться в одном из следующих состояний в соответствии со значением поля p_stat: SONPROC - процесс выполняется, т.е. его инструкции обрабатываются процессором; SRUN - процесс готов к выполнению, но не обладает приоритетом, достаночным для использования ресурсов процессора; SSLEEP - процесс ожидает некоторое событие, до наступления которого он не претендует на ресурсы процессора; SZOMB - состояние промежуточного завершения, когда процесс не имеет образа в RAM, но сохраняет дескриптор в таблице процессов. Взаимосвязь состояний процесса средствами внутренней синхронизации иллюстрирует следующая схема. В каждый момент времени только один процесс может являться текущим, т.е. использовать ресурсы процессора и находиться в состоянии SONPROC. Другие процессы, обработка которых не блокирована ожиданием событий, находятся в состоянии SRUN. Их дескрипторы образуют очередь дипетчера dispq и связаны в таблице процессов посредством ссылочных полей p_link структуры struct proc. Механизм синхронизации обеспечивает переключение текущего процесса в очередь диспетчера (switch out), когда он уступает процессор другому процессу, который, соответственно, включается (switch in) на выполнение. Переключение процессов между состояниями SRUN и SONPROC обеспечивает системная функция pswtch на основе сравнения приоритетов. Процесс остается текущим пока его приоритет выше, чем у любого процесса в очереди диспетчера. Планирование приоритетов процессов, претендующих на ресурсы процессора, обеспечивает механизм диспечеризации процессов. Для управления переключением процессов ядро использует системные флаги вытеснения runrun и kprunrun. Флаг runrun уведомляет системную функцию pswtch, что она должна быть вызвана как только переключаемый процесс перейдет в фазу "пользователь". Блокировка переключения в фазе "система" необходима для гарантии целостности системных данных. Флаг kprunrun позволяет реализовать переключение в фазе "система", когда код текущего процесса достигает достигает некоторых разрешенных точек вытеснения в адресном пространстве ядра. Обычно при работе OS UNIX число "спящих" процессов в состоянии SSLEEP превышает число готовых к выполнению процессов в состоянии SRUN. Это объяняется наличием большого числа событий в реальной практике работы OS UNIX. Наиболее распространенная причина погружения процесса в "сон" связана с отработкой внешних прерываний от периферийных устройств. В частности, выполнение операций ввода-вывода не может быть реализовано параллельно с обработкой процессором кода программы процесса. Более высокий уровень приоритета конроллеров периферийных устройств, чем у процессора при выполнении программы процесса, заставляет последний переключаться на обработку внешних прерываний, переводя текущий процесс в состояние "сна" до завершения отработки прерывания. Поэтому увеличение числа "спящих" процессов характерно при интенсивном обмене с периферией, когда большое число процессов ожидает в состоянии SSLEEP наступления событий, связанных с завершением операций ввода-вывода, чтобы продолжить процессорную обработку своих данных. Кроме приоритетной обработки внешних прерываний события могут быть вызваны программными причинами. Например, выполнение процесса-предка может быть приостановлено системным вызовом wait до завершения процесса-потомка. В другом случае процесс "засыпает" при попытке чтения из пустого struct proc дескриптора процесса, когда он находится в состоянии SSLEEP. Более конкретно, идентификатор события есть адрес определенной системной таблицы или элемента таблицы, связанной с ожидаемым ресурсом. Например, если процесс-предок ожидает завершения потомка, то идентификатор события, с которым будет связано его пробуждение, есть адрес дескриптора процесса-потомка. Для погружения процесса в состояние "сна" используется системная функция sleep, которой в качестве аргументов передаются идентификатор события и приоритет процесса после пробуждения. После выполнения функции sleep поле состояния дескриптора текущего процесса принимает значение SSLEEP, в поле p_wchan заносится идентификатор события, в поле приоритета p_pri фиксируется величина приоритета после пробуждения, а сам дескриптор включается в очередь дескрипторов "спящих" процессов sleepq. Очередь "спящих" процессов sleepq имеет организацию, аналогичную очереди диспетчера dispq. При погружении в "сон" текущего процесса процессор переключается на обслуживание самого приоритетного процесса из очереди диспетчера или обработку внешнего прерывания. Для пробуждения процесса из состояния "сна", при наступления ожидаемого события, выполняется системная функция wakeup, аргументом которой является идентификатор объявленного события. При вызове функции wakeup все дескрипторы очереди "спящих" процессов sleepq, у которых значение поля p_wchan совпадает с аргументом функции wakeup, перемещаются в очередь диспетчера dispq для готовых к выполнению процессов. Если приоритет "разбуженного" процесса выше, чем у текущего, то он включается на обслуживание процессором по алгоритму, рассмотренному выше. Если в очереди "спящих" процессов нет процессов с идентификатором события, объявленным функцией wakeup, то "пробуждения" процессов не происходит. Последнее из состояний процесса, достижимых внутренней синхронизацией, есть состояние промежуточного завершения текущего процесса - SZOMB (состояние "зомби"). Состояние "зомби" имеет место, если процесс-потомок завершается по системному вызову exit или по сигналу до планируемой реализации системного вызова wait в процессе-предке. При этом образ завершившегося процесса освобождает адресное пространство, но его дескриптор временно сохраняется в таблице процессов, чтобы обеспечить корректную обработку системного вызова wait в процессе-предке. В заключении следует отметить, что рассмотренный механизм внутренней синхронизации обслуживает процессы в фазе "система". Для синхронизации процессов в фазе "пользователь" используется аппарат сигналов OS UNIX. Коллектив параллельно действующих программ представляет собой набор программ (процессов), способных взаимодействовать между собой, находясь одновременно в стадии выполнения. Это означает, что такие программы, во-первых, вызваны в оперативную память, активизированы и могут попеременно разделять по времени один или несколько центральных процессоров, а во-вторых, осуществлять между собой динамические (в процессе выполнения) взаимодействия, на базе которых производиться их синхронизация. Обычно взаимодействие между такими процессами производится путем передачи друг другу некоторых сообщений. Простейшей разновидностью такой архитектуры является конвейер, средства для организации которого имеются в операционной системе UNIX. Конвейер представляет собой последовательность программ, в которой стандартный вывод каждой программы, кроме самой последней, связан со стандартным вводом следующей программы этой последовательности. Конвейер обрабатывает некоторый поток сообщений. Каждое сообщение этого потока поступает на ввод первой программе, которая обработав его передает переработанное сообщение следующей программе, а сама начинает обработку очередного сообщения потока. Таким же образом действует каждая программа конвейера: получив сообщение от предшествующей программы и обработав его, она передает переработанное сообщение следующей программе, а последняя программа конвейера выводит результат работы всего конвейера (результирующее сообщение). Таким образом, в конвейере, состоящим из n программ, может одновременно находиться в обработке до n сообщений. Конечно, в силу того, что разные программы конвейера могут затратить на обработку очередных сообщений разные отрезки времени, необходимо обеспечить каким-либо образом синхронизацию этих процессов (некоторые процессы могут находиться в стадии ожидания либо возможности передать переработанное сообщение, либо возможности получить очередное сообщение). В более общем случае коллектив параллельно действующих программ может быть организован в систему с портами сообщений. Порт сообщений представляет собой программную подсистему, обслуживающую некоторую очередь сообщений: она может принимать на хранение от программы какое-либо сообщение, ставя его в очередь, и может выдавать очередное сообщение другой программе по ее требованию. Сообщение, переданное какой-либо программой некоторому порту, уже не будет принадлежать этой программе (и использовать ее ресурсы), но оно не будет принадлежать и никакой другой программе, пока в порядке очереди не будет передано какой-либо программе по ее запросу. Таким образом, программа, передающая сообщение не будет находиться в стадии ожидания пока программа, принимающая это сообщение, не будет готова его обрабатывать (если только не будет переполнен принимающий порт). Программные системы с портами сообщений могут быть как жесткой конфигурации, так и гибкой конфигурации. В системах с портами жесткой конфигурации с каждой программой могут быть жестко связаны один или несколько входных портов. Для передачи сообщения такая программа должна явно указать адрес передачи: имя программы и имя ее входного порта. В этом случае при изменении конфигурации системы придется корректировать используемые программы: изменять адреса передач сообщений. В системах с портами гибкой конфигурации с каждой программой связаны как входные, так и выходные виртуальные порты. Перед запуском такой системы должна производиться ее предварительная настройка с помощью специальной программной компоненты, осуществляющая совмещение каждого выходного виртуального порта с каким-либо входным виртуальным портом на основании информации, задаваемой пользователем. Тем самым при изменении конфигурации системы в этом случае не требуется какой-либо корректировки используемых программ - необходимые изменения должны быть отражены в информации для настройки. Однако в этом случае требуется иметь специальную программную компоненту, осуществляющую настройку системы. Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году. При разработке средств System V IPC семафоры вошли в их состав как неотъемлемая часть. Следует отметить, что набор операций над семафорами System V IPC отличается от классического набора операций {P, V}, предложенного Дейкстрой. Он включает три операции: - A(S, n) - увеличить значение семафора S на величину n; - D(S, n) - пока значение семафора S < n, процесс блокируется. Далее S = S - n; - Z(S) - процесс блокируется до тех пор, пока значение семафора S не станет 0. Изначально все IPC-семафоры инициируются нулевым значением. Классическая операция P(S) соответствует операция D(S,1), а классической операции V(S) соответствует операция A(S,1). Аналогом ненулевой инициализации семафоров Дейкстры значением n может служить выполнение операции A(S,n) сразу после создания семафора S, с обеспечением атомарности создания семафора и ее выполнения посредством другого семафора. Мы показали, что классические семафоры реализуются через семафоры System V IPC. Обратное не является верным. Используя операции P(S) и V(S), мы не сумеем реализовать операцию Z(S). IPC-семафоры являются составной частью средств System V IPC и средством связи с непрямой адресацией, требуют инициализации для организации взаимодействия процессов и специальных действий для освобождения системных ресурсов по его окончании. Пространством имен IPC-семафоров является множество значений ключа, генерируемых с помощью функции ftok(). Для совершения операций над семафорами системным вызовам в качестве параметра передаются IPC-дескрипторы семафоров, однозначно идентифицирующих их во всей вычислительной системе, а вся информация о семафорах располагается в адресном пространстве ядра операционной системы. Это позволяет организовывать через семафоры взаимодействие процессов, даже не находящихся в системе одновременно. Создание массива семафоров или доступ к уже существующему. Системный вызов semget() В целях экономии системных ресурсов операционная система UNIX позволяет создавать не по одному семафору для каждого конкретного значения ключа, а связывать с ключом целый массив семафоров (в Linux - до 500 семафоров в массиве, хотя это количество может быть уменьшено системным администратором). Для создания массива семафоров, ассоциированного с определенным ключом, или доступа по ключу к уже существующему массиву используется системный вызов semget(), являющийся аналогом системного вызова shmget() для разделяемой памяти, который возвращает значение IPC-дескриптора для этого массива. При этом применяются те же способы создания и доступа, что и для разделяемой памяти. Вновь созданные семафоры инициируются нулевым значением. Системный вызов semget() Прототип системного вызова #include #include #include int semget(key_t key, int nsems, int semflg); Системный вызов semget предназначен для выполнения операции доступа к массиву IPC-семафоров и, в случае ее успешного завершения, возвращает дескриптор System V IPC для этого массива (целое неотрицательное число, однозначно характеризующее массив семафоров внутри вычислительной системы и использующееся в дальнейшем для других операций с ним). Параметр key является ключом System V IPC для массива семафоров, т. е. фактически его именем из пространства имен System V IPC. В качестве значения этого параметра может использоваться значение ключа, полученное с помощью функции ftok(), или специальное значение IPC_PRIVATE. Использование значения IPC_PRIVATE всегда приводит к попытке создания нового массива семафоров с ключом, который не совпадает со значением ключа ни одного из уже существующих массивов и не может быть получен с помощью функции ftok() ни при одной комбинации ее параметров. Параметр nsems определяет количество семафоров в создаваемом или уже существующем массиве. В случае, если массив с указанным ключом уже имеется, но его размер не совпадает с указанным в параметре nsems, констатируется возникновение ошибки. Параметр semflg - флаги - играет роль только при создании нового массива семафоров и определяет права различных пользователей при доступе к массиву, а также необходимость создания нового массива и поведение системного вызова при попытке создания. Он является некоторой комбинацией (с помощью операции побитовое или - <|>) следующих предопределенных значений и восьмеричных прав доступа: IPC_CREAT - если массива для ключа не существует, он должен быть создан IPC_EXCL - применяется совместно с флагом IPC_CREAT. При совместном их использовании и существовании массива с указанным ключом, доступ к массиву не производится и констатируется ошибка, при этом переменная errno, описанная в файле , примет значение EEXIST 0400 - разрешено чтение для пользователя, создавшего массив 0200 - разрешена запись для пользователя, создавшего массив 0040 - разрешено чтение для группы пользователя, создавшего массив 0020 - разрешена запись для группы пользователя, создавшего массив 0004 - разрешено чтение для всех остальных пользователей 0002 - разрешена запись для всех остальных пользователей Вновь созданные семафоры инициируются нулевым значением. Системный вызов возвращает значение дескриптора System V IPC для массива семафоров при нормальном завершении и значение -1 при возникновении ошибки. Сообщения как средства синхронизации процессов Наиболее семантически нагруженным средством, входящим в System V IPC, являются очереди сообщений.О модели сообщений как о способе взаимодействия процессов через линии связи, в котором на передаваемую информацию накладывается определенная структура, так что процесс, принимающий данные, может четко определить, где заканчивается одна порция информации и начинается другая. Такая модель позволяет задействовать одну и ту же линию связи для передачи данных в двух направлениях между несколькими процессами. Мы также рассматривали возможность использования сообщений с встроенными механизмами взаимоисключения и блокировки при чтении из пустого буфера и записи в переполненный буфер для организации синхронизации процессов. Очереди сообщений в UNIX как составная часть System V IPC Так как очереди сообщений входят в состав средств System V IPC, для них верно все, что говорилось ранее об этих средствах в целом и уже знакомо нам. Очереди сообщений, как и семафоры, и разделяемая память, являются средством связи с непрямой адресацией, требуют инициализации для организации взаимодействия процессов и специальных действий для освобождения системных ресурсов по окончании взаимодействия. Пространством имен очередей сообщений является то же самое множество значений ключа, генерируемых с помощью функции ftok() (см. раздел <Пространство имен. Адресация в System V IPC. Функция ftok()>). Для выполнения примитивов send и receive, введенных в лекции 6, соответствующим системным вызовам в качестве параметра передаются IPC-дескрипторы очередей сообщений, однозначно идентифицирующих их во всей вычислительной системе. Очереди сообщений располагаются в адресном пространстве ядра операционной системы в виде однонаправленных списков и имеют ограничение по объему информации, хранящейся в каждой очереди. Каждый элемент списка представляет собой отдельное сообщение. Сообщения имеют атрибут, называемый типом сообщения. Выборка сообщений из очереди (выполнение примитива receive) может осуществляться тремя способами: - В порядке FIFO, независимо от типа сообщения. - В порядке FIFO для сообщений конкретного типа. Первым выбирается сообщение с минимальным типом, не превышающим некоторого заданного значения, пришедшее раньше других сообщений с тем же типом. Реализация примитивов send и receive обеспечивает скрытое от пользователя взаимоисключение во время помещения сообщения в очередь или его получения из очереди. Также она обеспечивает блокировку процесса при попытке выполнить примитив receive над пустой очередью или очередью, в которой отсутствуют сообщения запрошенного типа, или при попытке выполнить примитив send для очереди, в которой нет свободного места. Очереди сообщений, как и другие средства System V IPC, позволяют организовать взаимодействие процессов, не находящихся одновременно в вычислительной системе. Создание очереди сообщений или доступ к уже существующей. Системный вызов msgget() Для создания очереди сообщений, ассоциированной с определенным ключом, или доступа по ключу к уже существующей очереди используется системный вызов msgget(), являющийся аналогом системных вызовов shmget() для разделяемой памяти и semget() для массива семафоров, который возвращает значение IPC-дескриптора для этой очереди. При этом существуют те же способы создания и доступа, что и для разделяемой памяти или семафоров. Системный вызов msgget() Прототип системного вызова #include #include #include int msgget(key_t key, int msgflg); Системный вызов msgget предназначен для выполнения операции доступа к очереди сообщений и, в случае ее успешного завершения, возвращает дескриптор System V IPC для этой очереди (целое неотрицательное число, однозначно характеризующее очередь сообщений внутри вычислительной системы и использующееся в дальнейшем для других операций с ней). Параметр key является ключом System V IPC для очереди сообщений, т. е. фактически ее именем из пространства имен System V IPC. В качестве значения этого параметра может быть использовано значение ключа, полученное с помощью функции ftok(), или специальное значение IPC_PRIVATE. Использование значения IPC_PRIVATE всегда приводит к попытке создания новой очереди сообщений с ключом, который не совпадает со значением ключа ни одной из уже существующих очередей и не может быть получен с помощью функции ftok() ни при одной комбинации ее параметров. Параметр msgflg - флаги - играет роль только при создании новой очереди сообщений и определяет права различных пользователей при доступе к очереди, а также необходимость создания новой очереди и поведение системного вызова при попытке создания. Он является некоторой комбинацией (с помощью операции побитовое или - <|>) следующих предопределенных значений и восьмеричных прав доступа: IPC_CREAT - если очереди для указанного ключа не существует, она создается; IPC_EXCL - применяется совместно с флагом IPC_CREAT. При совместном их использовании и существовании массива с указанным ключом доступ к очереди не производится и констатируется ошибочная ситуация, при этом переменная errno, описанная в файле , примет значение EEXIST; 0400 - разрешено чтение для пользователя, создавшего очередь; 0200 - разрешена запись для пользователя, создавшего очередь; 0040 - разрешено чтение для группы пользователя, создавшего очередь; 0020 - разрешена запись для группы пользователя, создавшего очередь; 0004 - разрешено чтение для всех остальных пользователей; 0002 - разрешена запись для всех остальных пользователей; Очередь сообщений имеет ограничение по общему количеству хранимой информации, которое может быть изменено администратором системы. Текущее значение ограничения можно узнать с помощью команды ipcs -l Системный вызов возвращает значение дескриптора System V IPC для очереди сообщений при нормальном завершении и значение -1 при возникновении ошибки. Реализация примитивов send и receive. Системные вызовы msgsnd() и msgrcv() Для выполнения примитива send используется системный вызов msgsnd(), копирующий пользовательское сообщение в очередь сообщений, заданную IPC-дескриптором. При изучении описания этого вызова обратите особое внимание на следующие моменты: Тип данных struct msgbuf не является типом данных для пользовательских сообщений, а представляет собой лишь шаблон для создания таких типов. Пользователь сам должен создать структуру для своих сообщений, в которой первым полем должна быть переменная типа long, содержащая положительное значение типа сообщения. В качестве третьего параметра - длины сообщения - указывается не вся длина структуры данных, соответствующей сообщению, а только длина полезной информации, т. е. информации, располагающейся в структуре данных после типа сообщения. Это значение может быть и равным 0 в случае, когда вся полезная информация заключается в самом факте прихода сообщения (сообщение используется как сигнальное средство связи). В материалах семинаров мы, как правило, будем использовать нулевое значение флага системного вызова, которое приводит к блокировке процесса при отсутствии свободного места в очереди сообщений. Системный вызов msgsnd() #include #include #include int msgsnd(int msqid, struct msgbuf *ptr, int length, int flag); Системный вызов msgsnd предназначен для помещения сообщения в очередь сообщений, т. е. является реализацией примитива send. Параметр msqid является дескриптором System V IPC для очереди, в которую отправляется сообщение, т. е. значением, которое вернул системный вызов msgget() при создании очереди или при ее поиске по ключу. Структура struct msgbuf описана в файле как struct msgbuf {long mtype; char mtext[1];}; Она представляет собой некоторый шаблон структуры сообщения пользователя. Сообщение пользователя - это структура, первый элемент которой обязательно имеет тип long и содержит тип сообщения, а далее следует информативная часть теоретически произвольной длины (практически в Linux она ограничена размером 4080 байт и может быть еще уменьшена системным администратором), содержащая собственно суть сообщения. Например: struct mymsgbuf {long mtype; char mtext[1024];} mybuf; При этом информация вовсе не обязана быть текстовой, например: struct mymsgbuf {long mtype; struct {int iinfo;float finfo;} info;} mybuf; Тип сообщения должен быть строго положительным числом. Действительная длина полезной части информации (т. е. информации, расположенной в структуре после типа сообщения) должна быть передана системному вызову в качестве параметра length. Этот параметр может быть равен и 0, если вся полезная информация заключается в самом факте наличия сообщения. Системный вызов копирует сообщение, расположенное по адресу, на который указывает параметр ptr, в очередь сообщений, заданную дескриптором msqid. Параметр flag может принимать два значения: 0 и IPC_NOWAIT. Если значение флага равно 0, и в очереди не хватает места для того, чтобы поместить сообщение, то системный вызов блокируется до тех пор, пока не освободится место. При значении флага IPC_NOWAIT системный вызов в этой ситуации не блокируется, а констатирует возникновение ошибки с установлением значения переменной errno, описанной в файле , равным EAGAIN. Системный вызов возвращает значение 0 при нормальном завершении и значение -1 при возникновении ошибки. Примитив receive реализуется системным вызовом msgrcv(). При изучении описания этого вызова нужно обратить особое внимание на следующие моменты: - Тип данных struct msgbuf, как и для вызова msgsnd(), является лишь шаблоном для пользовательского типа данных. - Способ выбора сообщения задается нулевым, положительным или отрицательным значением параметра type. Точное значение типа выбранного сообщения можно определить из соответствующего поля структуры, в которую системный вызов скопирует сообщение. Системный вызов возвращает длину только полезной части скопированной информации, т. е. информации, расположенной в структуре после поля типа сообщения. Выбранное сообщение удаляется из очереди сообщений. В качестве параметра length указывается максимальная длина полезной части информации, которая может быть размещена в структуре, адресованной параметром ptr. Блокировка процесса в случае отсутствия в очереди сообщений с запрошенным типом и к ошибочной ситуации в случае, когда длина информативной части выбранного сообщения превышает длину, специфицированную в параметре length. Системный вызов msgrcv() #include #include #include int msgrcv(int msqid, struct msgbuf *ptr, int length, long type, int flag); Системный вызов msgrcv предназначен для получения сообщения из очереди сообщений, т. е. является реализацией примитива receive. Способ выборки Значение параметра type В порядке FIFO, независимо от типа сообщения 0 В порядке FIFO для сообщений с типом n n Первым выбирается сообщение с минимальным типом, не превышающим значения n, пришедшее ранее всех других сообщений с тем же типом -n Параметр msqid является дескриптором System V IPC для очереди, из которой должно быть получено сообщение, т. е. значением, которое вернул системный вызов msgget() при создании очереди или при ее поиске по ключу. Параметр type определяет способ выборки сообщения из очереди следующим образом. Структура struct msgbuf описана в файле как struct msgbuf {long mtype; char mtext[1];}; Она представляет собой некоторый шаблон структуры сообщения пользователя. Сообщение пользователя - это структура, первый элемент которой обязательно имеет тип long и содержит тип сообщения, а далее следует информативная часть теоретически произвольной длины (практически в Linux она ограничена размером 4080 байт и может быть еще уменьшена системным администратором), содержащая собственно суть сообщения. Например: struct mymsgbuf {long mtype; char mtext[1024];} mybuf; При этом информация вовсе не обязана быть текстовой, например: struct mymsgbuf {long mtype; struct {int iinfo; float finfo;} info;} mybuf; Параметр length должен содержать максимальную длину полезной части информации (т. е. информации, расположенной в структуре после типа сообщения), которая может быть размещена в сообщении. В случае удачи системный вызов копирует выбранное сообщение из очереди сообщений по адресу, указанному в параметре ptr, одновременно удаляя его из очереди сообщений. Параметр flag может принимать значение 0 или быть какой-либо комбинацией флагов IPC_NOWAIT и MSG_NOERROR. Если флаг IPC_NOWAIT не установлен и очередь сообщений пуста или в ней нет сообщений с заказанным типом, то системный вызов блокируется до появления запрошенного сообщения. При установлении флага IPC_NOWAIT системный вызов в этой ситуации не блокируется, а констатирует возникновение ошибки с установлением значения переменной errno, описанной в файле , равным EAGAIN. Если действительная длина полезной части информации в выбранном сообщении превышает значение, указанное в параметре length и флаг MSG_NOERROR не установлен, то выборка сообщения не производится, и фиксируется наличие ошибочной ситуации. Если флаг MSG_NOERROR установлен, то в этом случае ошибки не возникает, а сообщение копируется в сокращенном виде. Системный вызов возвращает при нормальном завершении действительную длину полезной части информации (т. е. информации, расположенной в структуре после типа сообщения), скопированной из очереди сообщений, и значение -1 при возникновении ошибки. Максимально возможная длина информативной части сообщения в операционной системе Linux составляет 4080 байт и может быть уменьшена при генерации системы. Текущее значение максимальной длины можно определить с помощью команды ipcs -l Удаление очереди сообщений из системы После завершения процессов, использовавших очередь сообщений, она не удаляется из системы автоматически, а продолжает сохраняться в системе вместе со всеми невостребованными сообщениями до тех пор, пока не будет выполнена специальная команда или специальный системный вызов. Для удаления очереди сообщений можно воспользоваться командой ipcrm, которая в этом случае примет вид: ipcrm msg Для получения IPC идентификатора очереди сообщений примените команду ipcs. Можно удалить очередь сообщений и с помощью системного вызова msgctl(). Этот вызов умеет выполнять и другие операции над очередью сообщений, но в рамках данного курса мы их рассматривать не будем. Если какой-либо процесс находился в состоянии ожидание при выполнении системного вызова msgrcv() или msgsnd() для удаляемой очереди, то он будет разблокирован, и системный вызов констатирует наличие ошибочной ситуации. Системный вызов msgctl() #include #include #include int msgctl(int msqid, int cmd, struct msqid_ds *buf); предназначен для получения информации об очереди сообщений, изменения ее атрибутов и удаления из системы. Данное описание не является полным описанием системного вызова, а ограничивается рамками текущего курса. Для изучения полного описания обращайтесь к UNIX Manual. Параметр msqid является дескриптором System V IPC для очереди сообщений, т. е. значением, которое вернул системный вызов msgget() при создании очереди или при ее поиске по ключу. В качестве параметра cmd передаются значение IPC_RMID - команду для удаления очереди сообщений с заданным идентификатором. Параметр buf для этой команды не используется, поэтому будем подставлять туда значение NULL. Системный вызов возвращает значение 0 при нормальном завершении и значение -1 при возникновении ошибки. Прогон примера с однонаправленной передачей текстовой информации Для иллюстрации сказанного рассмотрим две простые программы. Первая из этих программ посылает пять текстовых сообщений с типом 1 и одно сообщение нулевой длины с типом 255 второй программе. Вторая программа в цикле принимает сообщения любого типа в порядке FIFO и печатает их содержимое до тех пор, пока не получит сообщение с типом 255. Сообщение с типом 255 служит для нее сигналом к завершению работы и ликвидации очереди сообщений. Если перед запуском любой из программ очередь сообщений еще отсутствовала в системе, то программа создаст ее. Обратите внимание на использование сообщения с типом 255 в качестве сигнала прекращения работы второго процесса. Это сообщение имеет нулевую длину, так как его информативность исчерпывается самим фактом наличия сообщения. Листинг 1a. Программа 1a.c для иллюстрации работы с очередями сообщений. /* Программа 08-1a.c для иллюстрации работы с семафорами */ /* Эта программа получает доступ к одному системному семафору, ждет, пока его значение не станет больше или равным 1 после запусков программы 08-1b.c, а затем уменьшает его на 1*/ #include #include #include #include int main() { int semid; /* IPC дескриптор для массива IPC семафоров */ char pathname[] = "08-1a.c"; /* Имя файла, использующееся для генерации ключа. Файл с таким именем должен существовать в директории */ key_t key; /* IPC ключ */ struct sembuf mybuf; /* Структура для задания операции над семафором */ /* Генерируем IPC-ключ из имени файла 08-1a.c в текущей директории и номера экземпляра массива семафоров 0 */ if((key = ftok(pathname,0)) < 0) {printf("Can\'t generate key\n"); exit(-1);} /* Пытаемся получить доступ по ключу к массиву семафоров, если он существует, или создать его из одного семафора, если его еще не существует, с правами доступа read & write для всех пользователей */ if((semid = semget(key, 1, 0666 | IPC_CREAT)) < 0) {printf("Can\'t get semid\n"); exit(-1);} /* Выполним операцию D(semid1,1) для нашего массива семафоров. Для этого сначала заполним нашу структуру. Флаг, как обычно, полагаем равным 0. Наш массив семафоров состоит из одного семафора с номером 0. Код операции -1.*/ mybuf.sem_op = -1; mybuf.sem_flg = 0; mybuf.sem_num = 0; if(semop(semid, &mybuf, 1) < 0) {printf("Can\'t wait for condition\n"); exit(-1);} printf("Condition is present\n"); return 0; } Листинг 1b. Программа 1b.c для иллюстрации работы с очередями сообщений. /* Программа 08-1b.c для иллюстрации работы с семафорами */ /* Программа получает доступ к одному системному семафору и увеличивает на 1*/ #include #include #include #include int main() { int semid; /* IPC дескриптор для массива IPC семафоров */ char pathname[] = "08-1a.c"; /* Имя файла, использующееся для генерации ключа. Файл с таким именем должен существовать в текущей директории */ key_t key; /* IPC ключ */ struct sembuf mybuf; /* Структура для задания операции над семафором */ /* Генерируем IPC ключ из имени файла 08-1a.c в текущей директории и номера экземпляра массива семафоров 0 */ if((key = ftok(pathname,0)) < 0) {printf("Can\'t generate key\n"); exit(-1);} /* Пытаемся получить доступ по ключу к массиву семафоров, если он существует, или создать его из одного семафора, если его еще не существует, с правами доступа read & write для всех пользователей */ if((semid = semget(key, 1, 0666 | IPC_CREAT)) < 0) {printf("Can\'t get semid\n"); exit(-1);} /* Выполним операцию A(semid1,1) для нашего массива семафоров. Для этого сначала заполним нашу структуру. Флаг, как обычно, полагаем равным 0. Наш массив семафоров состоит из одного семафора с номером 0. Код операции 1.*/ mybuf.sem_op = 1; mybuf.sem_flg = 0; mybuf.sem_num = 0; if(semop(semid, &mybuf, 1) < 0) {printf("Can\'t wait for condition\n"); exit(-1);} printf("Condition is set\n"); return 0; } Использование очередей сообщений для синхронизации работы процессов Доказана эквивалентность очередей сообщений и семафоров в системах, где процессы могут использовать разделяемую память. В частности, было показано, как реализовать семафоры с помощью очередей сообщений. Для этого вводился специальный синхронизирующий процесс-сервер, обслуживающий переменные-счетчики для каждого семафора. Процессы-клиенты для выполнения операции над семафором посылали процессу-серверу запросы на выполнение операции и ожидали ответа для продолжения работы. Теперь мы знаем, как это можно сделать в операционной системе UNIX и как, следовательно, можно использовать очереди сообщений для организации взаимоисключений и взаимной синхронизации процессов. Задача повышенной сложности: реализуйте семафоры через очереди сообщений. Монитор - это синтетический механизм синхронизации доступа процессов к множественным ресурсам, объединяющий в себе как собственно данные, так и процедуры, собственно реализующие работу с ресурсом. В отдельные моменты времени к монитору может одновременно обращаться несколько процессов - однако после занятия монитором одного процесса все остальные должны ожидать его выхода из монитора. Все переменные монитора делятся на локальные (доступные только внутри процедур монитора) и глобальные (доступные всем процедурам монитора. Однако все они локализованы внутри монитора. Для синхронизации процессов внутри монитора, а также для выделения критических секций используются примитивы signal и wait или двоичные семафоры. Различие между семафорами и мониторами состоит в том, что монитор специфицирует действия над определенными критическими ресурсами и ограничивает действия над ними определенными операциями. Решение этих вопросов при помощи семафоров ложится полностью на пользователя. Рассмотрим пример реализации задачи "поставщик-потребитель" с использованием мониторов применительно к кольцевому буферу. В данном примере процессы "поставщик" и "потребитель" напрямую не взаимодействуют друг с другом. Они выступают в качестве клиентов сервера "монитор". monitor RBM L=1000; Var s1,s2: signal;/* s1- появились данные, s2 - освободилось место */ lb, lc, cur, fp, lp :int; buff: array[1..L] of byte; Begin Initsignal(s1); Initsignal(s2); lb:=L; lc:=0; cur:=1; fp:=1; lp:=1; Procedure read_buf(rec,n) var rec: array [] of byte; n,i: int; begin if (lc