Append_to_queue

Добавление q к очереди sem_pending объекта sma. Это компактная реализация; она обычно выглядит примерно так:

q->prev = sma->last; if (sma->sem_pending) /* He пуст? */ sma->sem_pending_last->next = q; else sma->sem_pending = q; sma->sem_pending_last = q; q->next = NULL;

Истинным преимуществом реализации, применяемой в ядре, является то, что в ней удалось избежать потенциально дорогостоящего ветвления. Эта более эффективная реализация отчасти стало возможной благодаря тому, что переменная sem_pending_last стала указателем на указатель на узел очереди, а не просто указателем на узел очереди.

Count_semncnt

Функция count_semncnt вызывается из строки для реализации команды GETNCNT в функции sys_semctl. Ее задача состоит в подсчете числа задач, которые заблокированы и ждут приобретения семафора.

Этот цикл выполняется для каждой ожидающей операции в каждой задаче, ожидающей в очереди ожидания объекта sma. Цикл наращивает значение semncnt каждый раз, когда находит подходящую операцию— ту, которая пытается занять указанный семафор и у которой не установлен флажок IPC_NOWAIT.

Count_semzcnt

Функция count_semzcnt вызывается из строки для реализации команды GETZCNT в функции sys_semctl. Она почти полностью аналогична функции count_semncnt, за исключением того, что она подсчитывает задачи, ожидающие достижения данным семафором значения 0 (то есть количество задач, ждущих, когда данный семафор станет доступным). Поэтому единственным отличием является строка , где выполняется проверка равенства значения переменной нулю вместо проверки того, что это значение меньше нуля.

Findkey

Функция findkey находит очередь сообщений с данным ключом от имени функции sys_msgget (вызов находится в строке ).

Начинается цикл по всем слотам, которые могут заняты в msgque. Значение max_msqid позволяет отслеживать наивысший занятый элемент массива в msgque; оно используется здесь и сопровождается с помощью функций newque и freeque, которые вскоре будут рассмотрены. Без параметра max_msqid пришлось бы проходить в этом цикле по всем MSGMNI (128) элементам msgque, даже если, скажем, используются первые5.

Если текущий элемент массива имеет значение IPC_NOID, то здесь создается очередь сообщений. Очередь сообщений может иметь искомый ключ, поэтому функция findkey ожидает полного создания очереди. (Она может перейти в это состояние, когда вызов функции kmalloc в строке переводит процесс в состояние ожидания.)

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

Если совпадающий ключ найден, будет возвращен соответствующий индекс массива.

Если цикл был выполнен до конца и не найден соответствующий ключ, возвращается –1 в качестве сигнала об отказе.

Freeque

Описание функции freeque, которая удаляет очередь и освобождает соответствующий вход msgque, позволяет подвести черту под обсуждением данной реализации очереди сообщений ядра.

Если освобождаемый вход msgque представляет собой используемый вход с наибольшим индексом, функция freeque уменьшает значение max_msqid в наибольшей возможной степени. После этого цикла max_msqid снова представляет собой индекс максимального используемого входа msgque или 0, если все входы являются неиспользуемыми. Обратите внимание, что если max_msqid имеет значение 0, то массив msgque либо пуст, либо содержит только один вход.

Элемент массива msgque отмечен как неиспользуемый, хотя объект struct msqid_ds еще не освобожден (функция freeque все еще содержит указатель на объект struct msqid_ds в переменной msq).

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

Вызов функции schedule (строка , описанной в ) для предоставления активизированным процессам шанса на выполнение. Интересно, что активизированные процессы могут пока не получить процессорного времени, поскольку текущий процесс может иметь более низкое значение параметра goodness (более высокий приоритет). Однако, если это произойдет, то вновь активизированные процессы просто не будут удалены из соответствующих им очередей ожидания; функция freeque обнаружит это, продолжая проходить по циклу, и попытается снова активизировать процессы. В конечном итоге, процесс, выполняющий функцию freeque, исчерпает отведенное ему время и уступит место другим процессам. Тем не менее, с учетом всех обстоятельств, может быть лучше явно устанавливать флажок SCHED_YIELD текущего процесса (строка ) до того, как он вызовет schedule, чтобы предоставить другим процессам лучшие условия доступа к процессору.

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

Insert_attach

Эта короткая функция просто добавляет область VMA к списку областей VMA, подключенных к данному объекту struct shmid_kernel. Обратите внимание, что область VMA подключается с начала этого списка, поскольку порядок не играет роли и проще всего выполнить это действие именно так. В ином случае, пришлось бы отдельно отслеживать начало и конец списка attaches.

Killseg

Эта функция представляет собой аналог функций freeque и freeary. Ее программная реализация в основном аналогична этим функциям, но несколько ее средств заслуживают отдельного упоминания.

Если программа killseg вызывается с индексом незанятого элемента shm_segs, она выводит предупреждающее сообщение и немедленно выполняет возврат. Ни в одном из ее аналогов нет подобного кода.

Если член shm_pages данного входа имеет значение NULL, то где-то есть логическая ошибка. Это значит, что был не полностью построен объект struct shmid_kernel, или он был уничтожен, но не удален из массива, или возникло какое-то подобное «невероятное» состояние.

Освобождение страниц, распределенных для данной таблицы страниц.

Если в таблице страниц нет отображения для этой страницы, то для освобождения этого входа ничего не нужно делать.

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

В ином случае, она находится в области подкачки, и освобождается и удаляется оттуда.

Освобождение самой таблицы страниц.

Краткий обзор очереди сообщений

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

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

msgget. Неудачное имя (которое буквально означает «получить сообщение»); можно подумать, что это — команда на получение ждущего сообщения, но это не так. Вызывающая программа выдает ключ очереди сообщений, a msgget возвращает идентификатор либо существующей очереди с этим ключом, если таковая имеется, либо новую очередь сообщений с этим ключом, если таковой не было. Поэтому функция msgget позволяет получить не сообщение, а идентификатор, который однозначно обозначает очередь сообщений.

msgsnd. Посылает сообщение в очередь сообщений.

msgrcv. Принимает сообщение из очереди сообщений.

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

Msg_init

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

Однако цикл, который устанавливает входы msgque в значение IPC_UNUSED, необходим. Значение IPC_UNUSED, не рассматриваемое в этой книге, принято равным –1 (соответственно, приведенной к void*ndash;*); оно представляет неиспользуемую очередь сообщений. Еще одним специальным значением, которое может принять вход msgque, но только временно, на время создания очереди сообщений, является значение IPC_NOID (также не рассматриваемое в этой книге).

Msgque

Центральной структурой данных в реализации очереди сообщений является msgque — массив указателей на объекты struct msqid_ds. Существует всего MSGMNI таких указателей (эта величина установлена равной 128 с помощью директивы #define в строке ), что соответствует 128 очередям сообщений. Но почему бы просто не использовать массив объектов struct msqid_ds вместо массива указателей? Одной из причин этого является экономия места: вместо массива из 128 56-байтовых структур (7168 байтов или ровно 7 Кб) для msgque применяется массив из 128 4-байтовых указателей (512 байтов). В обычном случае, когда применяется ряд очередей сообщений, это позволяет сэкономить несколько килобайтов. В наихудшем случае, когда распределены все очереди сообщений, максимальный расход составляет 512 байтов. Единственным реальным недостатком является дополнительный уровень разадресации, что приводит к небольшому снижению быстродействия.

Зависимость между основными структурами данных очереди сообщений показана на рис. 9.1.

Рис. 9.1. Структуры данных очереди сообщений

Newque

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

Проходит в цикле через msgque в поиске неиспользуемого входа. Если таковой будет найден, он будет отмечен значением IPC_NOID и управление перейдет на метку found в строке .

Если цикл завершится без обнаружения неиспользуемого входа, это значит, что массив msgque заполнен. Функция newque возвращает ошибку ENOSPC, которая указывает на то, что в таблице не осталось места.

Распределяет объект struct msqid_ds, который будет представлять новую очередь.

Если распределение окончится неудачей, этот вход msgque снова устанавливается в IPC_UNUSED.

Активизируются все процессы findkey, которые были переведены в состояние ожидания после встречи IPC_NOID.

Инициализация новой очереди.

Если эта очередь была сформирована вслед за наивысшим ранее используемым слотом в msgque, функция newque соответствующим образом увеличивает параметр max_msqid.

Устанавливает новую очередь в msgque.

Активизация всех процессов findkey, которые могли ожидать окончания инициализации этой очереди.

Возвращает порядковый номер и индекс массива msgque. (He мешало бы создать небольшой набор макрокоманд для выполнения этого кодирования и последующего декодирования.) Как ни странно, порядковый номер здесь не наращивается; это происходит в функции freeque, которая рассматривается ниже. Если подумать, это решение имеет смысл. Вам не нужен уникальный порядковый номер для каждой очереди — вам нужен только другой порядковый номер при каждом повторном использовании элемента msgque, чтобы данное сочетание индекса массива и порядкового номера больше не могло повториться. Индекс массива не может быть повторно использован до тех пор, пока очередь, установленная здесь, не будет освобождена, поэтому наращивание порядкового номера можно отложить до этого момента.

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

Newseg

Данная функция является аналогом функций newque и newary. Она распределяет и инициализирует объект struct shmid_kernel, а затем устанавливает его в массив shm_segs.

Распределение «таблицы страниц». Если бы эта программная реализация была построена по аналогии с другими механизмами межпроцессного взаимодействия, то эта память была бы распределена сразу после объекта struct shmid_kernel полностью в составе единственного большого распределения. Однако память для объекта struct shmid_kernel распределяется функцией kmalloc (в невыгружаемой памяти ядра), а «таблица страниц» распределяется функцией vmalloc (в выгружаемой памяти).

Инициализация распределенного входа, начиная с обнуления таблицы страниц.

Очереди сообщений

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

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

Эта архитектура является несложной для реализации и, при условии правильного подбора объемов работы, запрашиваемых каждым сообщением, может обеспечить весьма эффективное использование процессоров компьютера. (Заметим также, что планировщик вряд ли будет выполнять слишком большой объем работы, поэтому на процессоре планировщика оставшуюся часть времени может занять еще один рабочий процесс.) Таким образом, очереди сообщений можно использовать в качестве разновидности удаленного вызова процедур (RPC — remote procedure calling) низкого уровня.

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

Prepend_to_queue

Вставляет q перед очередью sem_pending объекта sma. Поскольку sem_pending это не указатель на указатель, эта реализация имеет, по существу, такую же форму, как и рассмотренная ранее наивная реализация.

Разделяемая память

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

Разделяемая память по своему быстродействию намного превосходит два других механизма взаимодействия между процессами, рассматриваемые в этой главе, и она проще в использовании: процесс после ее приобретения рассматривает ее просто как обычную память. Изменения, записанные в разделяемую память одним процессом, сразу же становятся очевидными для всех других процессов— они могут просто выполнить чтение через указатель, который указывает на пространство разделяемой памяти, а там, как по взмаху волшебной палочки, уже находится новое значение. Однако в разделяемой памяти типа System V нет встроенного способа обеспечения взаимного исключения: может оказаться, что один процесс пишет по данному адресу в области разделяемой памяти одновременно с тем, как другой процесс читает по тому же адресу, в результате чего программа чтения получает противоречивые данные. Эта проблема наиболее серьезна для компьютеров с симметричной мультипроцессорной архитектурой, но она может возникать и на однопроцессорных компьютерах: например, когда программа записи потеряет управление и перейдет в неактивное состояние в ходе записи какой-то крупной структуры в пространство разделяемой памяти, а программа чтения выполнит чтение из разделяемой памяти до того, как программа записи получит возможность закончить запись.

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

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

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

В коде ядра области разделяемой памяти называются сегментами, то есть применяется та же терминология, которая иногда ошибочно применяется к областям VMA. Только для того, чтобы предотвратить какую-либо путаницу, отметим, что это — неформальное применение данного слова; оно не относится к сегментам, поддерживаемым на уровне аппаратного обеспечения (MMU), которые описаны в . Автор будет и далее использовать термин «область», чтобы избежать этой путаницы.

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

Real_msgrcv

Функция real_msgrcv, аналогично real_msgsnd, реализует системный вызов msgrcv. Параметр msgtyp несет большую смысловую нагрузку, как описано в развернутом комментарии, который начинается в строке . Именно здесь применяется поле msg_type объекта struct msg: в этой функции оно сравнивается с параметром msgtyp.

Функция real_msgrcv аналогична функции real_msgsnd также тем, что ее вызов происходит внутри пары lock_kernel/unlock_kernel в строке .

Извлекает индекс msgque из msgid и проверяет, что по этому индексу находится допустимый вход.

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

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

Эта последовательность if/else позволяет выбрать сообщение из очереди. Первый случай проще всего: он просто захватывает первое сообщение в очереди, если оно имеется, устанавливая значение nmsg либо равным NULL, либо равным указателю на первый элемент очереди.

Параметр msgtyp положителен и бит MSG_EXCEPT (строка ) в структуре msgflg установлен. Функция real_msgrcv проходит по очереди, отыскивая первый вход, тип которого не соответствует msgtyp.

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

Параметр msgtyp отрицателен. Функция real_msgrcv отыскивает сообщение с наименьшим значением члена msg_type, если это значение также меньше абсолютного значения msgtyp. Обратите внимание, что поскольку в строке в качестве сравнения используется <, а не <=, предпочтение отдается первому сообщению в очереди. Это не только удобно (такое строгое соблюдение принципов организации последовательной очереди, по-видимому, вполне оправдано), но также чуть более эффективно, поскольку при этом приходится выполнять меньше операций присваивания. Если бы в качестве сравнения применялось <=, то появление каждого подходящего значения влекло бы за собой присваивание.

Если к этому моменту какое- либо сообщение удовлетворяет заданным критериям, nmsg указывает на него. В ином случае, nmsg содержит NULL.

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

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

Более распространенный способ записи этого иногда немного медленнее, но в среднем, вероятно, может оказаться быстрее:

if (msgsz > nmsg->msg_ts) msgsz = nmsg->msg_ts;

Удаляет выбранное сообщение из очереди. Очередь — это односвязный, а не двухсвязный список, поэтому, если удаляемое сообщение — не первое в очереди, функция real_msgrcv должна вначале пройти в цикле по очереди, чтобы найти предыдущий узел в очереди.

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

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

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



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

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

Обеспечивает удаление единственного узла очереди.

Обновляет статистику очереди сообщений.

Активизирует все процессы, ожидающие записи к эту очередь сообщений, то есть все процессы, которые были переведены в состояние ожидания функцией real_msgsnd.

Копирует сообщение в пространство пользователя и освобождает узел очереди (заголовок и тело).

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

Ни одно сообщение не соответствовало критериям вызывающей программы. Дальнейшие действия зависят от вызывающей программы: если в вызывающей программе установлен бит IPC_NOWAIT структуры msgflg, то функция real_msgrcv может немедленно возвратить сообщение об отказе.

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

Эта точка никогда не будет достигнута, но транслятор об этом не знает. Поэтому здесь находится фиктивный оператор return только для выполнения требований gcc.

Real_msgsnd

Функция real_msgsnd реализует содержательную часть функции sys_msgsnd, системного вызова msgsnd. Это нарушение принятого в ядре соглашения об именовании «реализующих функций» системных вызовов с префиксом «do_».

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

Как известно, в ядре такие проблемы в основном решаются с помощью переменных с кодом возврата и операторов goto. Принятый в sys_msgsnd способ проще, но он может не сработать в некоторых случаях. Например, рассмотрим, что произойдет, если функция должна будет получить несколько ресурсов и к некоторым из них она должна будет обратиться, только если все предшествующие ресурсы были успешно получены. Примитивное решение по принципу расширения функции sys_msgsnd потребовало бы создания множества функций, примерно так, как показано ниже:

void f1(void) { if (acquire_resource1()) { f2(); release_resource1(); } }

void f2(void) { if (acquire_resource2()) {] f3(); release_resource2(); } }

void f3(void) { if (acquire_resource3()) { /* ... здесь выполняется настоящая работа ... */ release_resource3(); } }

Эта конструкция быстро становится громоздкой и поэтому она в ядре не применяется.

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

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

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

Хранимый порядковый номер в очереди сообщений должен соответствовать номеру, закодированному в параметре msqid. Идея состоит в том, что одно лишь обнаружение очереди сообщений по правильному индексу массива не означает, что это— та очередь сообщений, которая нужна вызывающей программе. С того момента, как вызывающая программа получила свою ссылку на эту очередь, очередь сообщений, находившаяся первоначально по этому индексу, могла быть удалена и на ее месте создана новая. 16-разрядный порядковый номер постоянно наращивается, поэтому новая очередь по тому же индексу будет иметь порядковый номер, отличный от первоначального. (Если только не случилось так, что в этот промежуток времени было создано еще 65535 новых очередей, что весьма маловероятно, или создано еще 131071 новых очередей, что еще более маловероятно, и т.д. Однако, как описано далее в этой главе, в действительности не так все просто.) Во всяком случае, если порядковые номера не совпадают, функция real_msgsnd возвращает ошибку EIDRM в качестве указания на то, что очередь сообщений, нужная для вызывающей программы, была удалена.

Проверка того, что вызывающая программа имеет разрешение на запись в очередь сообщений. Аналогичная система рассматривается более подробно в ; пока достаточно отметить, что применяется система, полностью аналогичная проверке прав доступа к файлам Unix.

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



В очереди нет свободного места. Если в структуре msgflg установлен бит IPC_NOWAIT, вызывающая программа не должна ждать, пока это случится, поэтому возвращается ошибка EAGAIN.

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

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

Распределение достаточного пространства как для заголовка очереди сообщений (объект struct msg), так и для тела сообщения; как было упомянуто ранее, тело сообщения будет записано непосредственно после заголовка сообщения. Значение msg_spot заголовка будет указывать на место сразу после заголовка, где должно находиться тело сообщения.

Копирует тело сообщения из пространства пользователя.

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

Несмотря на это, создается впечатление, что здесь возможна ошибка. А что, если очередь сообщений будет уничтожена и по тому же индексу массива будет развернута другая очередь сообщений, прежде чем текущий процесс достигает этой точки? Это не может произойти на однопроцессорном компьютере, поскольку функция freeque, которая уничтожает очереди сообщений (строка ), активизирует все процессы, ждущие в очереди, перед ее уничтожением и не перейдет эту точку, пока не закончит свою работу функция real_msgsnd (функция freeque рассматривается далее в этой главе).

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

Если бы это произошло, значение msgque[id] не равнялось бы IPC_UNUSED или IPC_NOID, но память, на которую указывает msq, была бы освобождена функцией freeque, поэтому в строке происходила бы разадресация недействительного указателя.

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

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

Remove_attach

Эта функция удаляет область VMA из списка, подключенного к данному объекту shmid_kernel. Интересной особенностью этой функции является то, что она не зависит от своего параметра shp: указатель на список attaches параметра shp был записан в первой области VMA в списке в строке , а процедура обновления списка является одинаковой, независимо от того, является ли область VMA первой в списке (если это так, то обновляется также соответствующий список attaches).

Remove_from_queue

Последней примитивной операцией над очередями struct sem_queue является именно эта, в которой выполняется удаление узла из очереди.

Частично удаляет q из очереди путем изменения указателя next предыдущего узла очереди.

Обновляет также указатель prev следующего узла, если он есть, или sma->sem_pending_last, если это— последний узел в очереди. Обратите внимание, что нет явного кода для удаления единственного узла очереди; вам следует выделить время, чтобы разобраться в том, почему и этот случай работает, если вы еще этого не сделали.

Устанавливает указатель prev удаленного узла в NULL, чтобы код в строках и позволял эффективно обнаружить, находится ли все еще в очереди этот узел.

Sem_exit

Функция sem_exit не имеет аналога в программной реализации очереди сообщений. Она выполняет все операции отмены, установленные процессом для автоматического выполнения во время его выхода. Поэтому она вызывается во время выхода процесса (в строке ).

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

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

Если семафоры, соответствующие этой структуре отмены, были освобождены, цикл просто продолжается. Поле semid объекта struct sem_undo может быть установлено в –1 функцией freeary, которая рассматривается далее в этой главе.

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

Во многом аналогично удалению сообщения из середины очереди сообщений, этот цикл проходит по списку sma объектов struct sem_undo для поиска объекта, предшествующего тому, который должен быть удален. Когда он будет найден, функция sem_exit переходит вперед на метку found в строке .

Если структура отмены не была найдена в списке sma, что-то происходит не так. Функция sem_exit выводит предупреждающее сообщение и останавливает внешний цикл. Эта реакция кажется немного преувеличенной, поскольку могут еще оставаться другие структуры отмены, которые можно было бы обработать и освободить. Ведь, найдя одно гнилое яблоко, мы не выбрасываем весь ящик. Тем не менее, это «невозможный» случай, один из тех, которые (могут быть вызваны только логической ошибкой в ядре. Автор предполагает, что в основе этого поведения лежит принцип, что после обнаружения подобной ошибки нельзя доверять и оставшимся данным.

В списке sma была найдена структура отмены и переменная unp указывает на указатель на ее предшественника. Переменная un удалена из очереди.

Все корректировки семафоров в этой структуре отмены выполнены.

Как всегда, происходит вызов функции update_queue на тот случай, если операции, выполненные этой функцией, создали условия для активизации какого-то ждущего процесса.

Были обработаны все объекты struct sem_undo или в строке была обнаружена ошибка и выход из цикла произошел преждевременно. Так или иначе, очередь sem_undo текущего процесса устанавливается в NULL и функция выполняет возврат.

Семафоры

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

В простейшем случае семафор — это единственный ключ, который висит на гвозде рядом с запертой дверью. Чтобы пройти через дверь, нужно снять ключ с гвоздя; вы также обязаны снова повесить ключ на гвоздь, выйдя из комнаты. Если ключа не будет на месте, когда вы подойдете к двери, вам придется ждать до тех пор, пока тот, кто его взял, не повесит его на место, при условии, что вы твердо решили пройти через эту дверь. Иначе, вы можете сразу же уйти, если ключа нет на месте.

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

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

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

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

Программные реализации семафора и очереди сообщений настолько подобны, что нет нужды описывать функции sem_init (строка ), findkey (строка ), sys_semget (строка ), newary (строка ) и freeary (строка ), поскольку они почти полностью повторяют свои аналоги в реализации очереди сообщений.

Shm_close

Функция shm_close, которая является противоположной функции shm_open, отключает область VMA от области разделяемой памяти, к которой она подключена. Хотя есть и другие места, где ядро вызывает операцию закрытия области VMA, по-видимому, строка является единственным таким местом, где это может окончиться вызовом функции shm_close. Это часть функции exit_mmap (строка ) и она обычно достигается функцией mmput (строка ), которая вызывается из функции __exit_mm (строка ), которая вызывается из функции do_exit (строка ), рассматриваемой в . Отметим, что есть и другие пути к функции shm_close, и один из них мы вскоре рассмотрим.

Извлечение индекса shm_segs из члена vm_pte области VMA, а затем отключение области VMA от данной области. Этот индекс не нужно проверять на соответствие диапазону по тем же причинам, как и в функции shm_open. Отметим также, что функция shm_close не проверяет, находится ли допустимый вход shm_segs по указанному индексу. Для функции remove_attach это не имеет значение, поскольку, как было показано выше, она даже не зависит от своего параметра shp. Но в последней части функции shm_close предполагается, что остальная программная реализация разделяемой памяти разработана и применяется правильно, так что этот «невозможный» случай действительно не произойдет.

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

Уменьшение числа ссылок области и, возможно, также ее освобождение.

Shm_open

Функцию shm_open можно считать облегченным вариантом функции sys_shmat (строка ). Она подключает переданную ей область VMA к области разделяемой памяти. Область VMA, переданная в качестве параметра, была скопирована из той, которая уже подключена к целевой области, поэтому сама область VMA уже заполнена правильно; работа функции shm_open в основном сводится только к выполнению подключения.

Как сказано в комментарии перед функцией shm_open, эта функция вызывается из функции do_fork (строка ), которая рассматривается в . Точнее, эта функция вызывается из строки в функции dup_mmap (строка ). Функция dup_mmap, в свою очередь, вызывается из строки функции copy_mm (строка ); a copy_mm вызывается из строки , которая находится в функции do_fork.

Извлечение индекса shm_segs из члена vm_pte данной области VMA, а затем проверка того, что здесь находится допустимый вход. Обратите внимание, что этот индекс не нужно проверять на соответствие диапазону, поскольку поразрядная операция AND, применяемая к величине SHM_ID_MASK (строка ),заставляет его находиться в диапазоне.

Подключает область VMA к данной области и обновляет статистическую информацию данной области.

Struct msg

Объект struct msg представляет единственное сообщение, ожидающее в очереди. Он имеет следующие члены:

msg_next. Указывает на следующее сообщение в очереди или содержит NULL, если это — последнее сообщение в очереди.

msg_type. Определяемый пользователем код типа; его применение рассматривается далее в этой главе в описании процесса получения сообщений.

msg_spot. Указывает на начало содержимого сообщения. Как будет показано ниже, пространство для сообщения всегда распределяется непосредственно над самим объектом struct msg, поэтому msg_spot всегда указывает на адрес, расположенный сразу после конца объекта struct msg.

msg_stime. Содержит данные о времени отправки сообщения. Поскольку сообщения хранятся в порядке очереди (FIFO — first-in, first-out), сообщения в очереди характеризуются монотонно возрастающими значениями msg_stime.

msg_ts. Содержит данные о размере сообщения («ts» — это сокращение от «text size», но сообщение не обязано быть текстом, предназначенным для восприятия человеком). Максимальный размер сообщения соответствует величине MSGMAX, которая установлена директивой #define равной 4056 байтам в строке . Можно предположить, что эта величина принята равной 4 Кб (4096 байтам) минус размер объекта struct msg. Но размер этого объекта составляет только 20 байтов, поэтому назначение еще 20 байтов остается неизвестным.

Struct msqid_ds

Объект msqid_ds представляет единственную очередь сообщений. Он имеет следующие члены:

msg_perm. Содержит информацию о том, каким процессам необходимо предоставить разрешение читать и писать в этой очереди сообщений.

msg_first и msg_last. Указывает на первое и последнее сообщения в очереди.

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

msg_ctime. Время последнего изменения состояния в очереди: время ее создания или время последней установки одного из ее параметров с использованием системного вызова msgctl.

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

rwait. Аналогичным образом, обычно сообщения можно немедленно прочитать из очереди сообщений. А если в очереди нет сообщений? Опять-таки, процессы получают право сделать выбор: они могут либо снова вернуть себе контроль (получив код ошибки, сигнализирующий о неудаче в получении сообщения), либо перейти в состояние ожидания и ждать поступления сообщения.

msg_cbytes. Общее число байтов, содержащихся в настоящее время во всех сообщениях в очереди.

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

msg_qbytes. Максимальное число байтов, которое разрешено использовать для хранения всех сообщений в очереди; msg_cbytes сравнивается с msg_qbytes для определения того, есть ли еще место для нового сообщения. Значение msg_qbytes принято по умолчанию равным MSGMNB, однако этот предел может быть увеличен динамически пользователем с соответствующими правами.

Величина MSGMNB установлена директивой #define равной 16384 байтам в строке . Существуют четыре причины применения такого низкого предела. Во-первых, на практике обычно редко возникает необходимость включать так много информации в конкретное сообщение, поэтому данный предел не является слишком ограничительным. Во-вторых, если отправители сообщений будут забегать слишком далеко вперед по сравнению с получателями сообщений, то, вероятно, нет никакого смысла позволять им и дальше работать в таком же темпе; они получают возможность на время остановиться, чтобы позволить получателям справиться с полученным заданием. В-третьих, этот предел в 16 Кб на очередь может в принципе быть умножен на 128 очередей, что составляет в сумме 2 Мб.

Но основной причиной установки такого предела является предотвращение описанной выше атаки по принципу «отказа в обслуживании». Однако ничто не мешает приложениям посылать сообщения нулевой длины (т.е. пустые) сообщения. Эти сообщения не будут отражаться на величине msg_qbytes, а для заголовков сообщений все еще будет распределяться память, поэтому возможность атаки по принципу «отказа в обслуживании» все еще сохраняется. Один из способов решения этой проблемы состоит в наложении независимого предела на число сообщений, которым разрешено находиться в очереди; вторым решением является вычитание из msg_qbytes размера всего сообщения, включая заголовки. Третье решение, безусловно, состоит в запрещении пустых сообщений, но это привело бы к нарушению совместимости.

msg_lspid и msg_lrpid. Идентификаторы процессов последнего отправителя сообщения и последнего получателя сообщения.

Struct sem

Объект struct sem представляет отдельный семафор. Он имеет два члена:

semval. Если он равен 0 или положительному числу, semval + 1 обозначает число ключей, которые все еще висят на гвозде у двери семафора. Если он равен отрицательному числу, его абсолютное значение на единицу больше числа процессов, ожидающих доступа к семафору. Семафоры являются двоичными по умолчанию, но их можно сделать счетными с использованием функции sys_semctl (строка ); максимальное значение семафора — SEMVMX (это значение установлено равным 32767 директивой #define в строке ).

sempid. Хранит идентификатор последнего процесса, который должен оперировать с семафором.

Struct sem_queue

Объект struct sem_queue представляет собой узел в очереди ожидающих операций в отдельном объекте struct semid_ds. Он имеет следующие члены:

next и prev. Следующий и предыдущий узлы в очереди. Как и в случае с sem_pending_last, prev — это указатель на указатель на предыдущий узел. Далее в этой главе описано, почему prev никогда не принимает значение NULL; в вырожденном случае, когда очередь пуста, prev указывает на next.

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

undo. Массив операций, которые позволяют отменять операции, реализованные объектами sops; иными словами, это — противоположность sops.

pid. Идентификатор процесса, который пытается выполнить операции, представленные в этом узле очереди.

status. Регистрирует способ активизации ожидающего процесса.

sma. Указывает обратно на объект struct semid_ds, в чьей очереди sem_pending находится данный объект struct sem_queue.

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

nsops. Длина массива sops.

alter. Указывает, будут ли эти операции воздействовать на любой из семафоров в наборе. Может показаться, что это значение всегда должно быть истинным, но нужно учитывать, что ожидание достижения семафором значения 0 (то есть ожидание его освобождения) не воздействует на сам семафор.

Struct sem_undo

Объект struct sem_undo содержит достаточный объем информации для отмены отдельной операции над семафором. Если процесс выполняет операцию над семафором с установленным флажком SEM_UNDO, создается объект struct sem_undo, позволяющий отменить эту операцию. Все операции отмены, регламентируемые списком объектов struct sem_undo процесса, выполняются после выхода процесса. Читатели, знакомые с шаблонами проектирования, могут узнать в этом экземпляр шаблона Command.

Это средство позволяет процессу гарантировать автоматическую очистку ресурсов после себя, независимо от того, как произойдет его выход; таким образом, процесс не сможет случайно оставить другие процессы в состоянии бесконечного ожидания освобождения семафора, которое не сможет никогда произойти. (Может также возникнуть ситуация, что процесс приобретет семафор, а затем войдет в бесконечный цикл, но в задачу ядра не входит защита от такой ситуации; в этом случае реализовано намерение предоставить процессам возможность действовать правильно, а не вынуждать их действовать именно так.) Объект struct sem_undo имеет следующие члены:

proc_next. Указывает на следующий объект struct sem_undo в списке объектов struct sem_undo владеющего ими процесса.

id_next. Указывает на следующий объект struct sem_undo в списке объектов struct sem_undo, связанных с набором семафоров. Да, вы не ошиблись: один и тот же объект struct sem_undo находится в двух списках одновременно. Далее в этой главе показано, как они оба используются.

semid. Указывает вход semary, к которому принадлежит этот объект struct sem_undo.

semadj. Массив корректировок, которые должны быть выполнены над каждым семафором в наборе семафоров, связанном с этим объектом struct sem_undo. Семафоры, о которых в этой структуре нет дополнительной информации, содержат в этом массиве 0 — корректировка не предусмотрена.

Struct sembuf

Объект struct sembuf представляет отдельную операцию, которая должна быть выполнена над семафором. Он имеет следующие члены:

sem_num. Индекс массива семафоров, к которым относится эта операция в массиве sem_base объекта struct semid_ds. Поскольку объект struct sembuf составляет часть объекта struct sem_queue, и объект struct sem_queue содержит информацию о том, с каким объектом struct semid_ds он связан, никогда не возникает путаница в отношении того, для какого массива семафоров объекта struct semid_ds предназначена эта операция. В иных случаях, массив объектов struct sembuf спарен с индексом массива semary, который также подразумевает массив семафоров.

sem_op. Операция над семафором, которая должна быть выполнена. Обычно она принимает значение –1, 0 или 1; –1 означает занятие семафора (снятие ключа с гвоздя), 1 означает освобождение семафора (возвращение ключа на гвоздь) и 0 означает ожидание возврата значения семафора к 0. Однако могут также применяться значения, отличные от этих, и они просто расшифровываются как занятие или освобождение большего числа значений семафора, то есть снятие или возврат большего числа ключей на гвоздь. (Слова «занять» и «освободить» могут выглядеть немного непривычными в этом контексте, но не беспокойтесь об этом; это общепринятая терминология для семафоров.)

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

На рис.9.2 показаны взаимосвязи между этими структурами данных.

Рис. 9.2. Структуры данных для семафоров

Struct semid_ds

Объект struct semid_ds представляет собой аналог объекта struct msqid_ds: он отслеживает всю информацию об отдельном семафоре и очереди операций, которые должны быть выполнены над ним. Ниже перечислены члены этого объекта, которые имеют интересные отличия от соответствующих членов объекта struct msqid_ds:

sem_base. Указывает на массив объектов struct sem, иными словами, на массив семафоров. Так же как отдельный объект struct msqid_ds может содержать много сообщений, отдельный объект struct semid_ds может содержать несколько семафоров; все семафоры одного массива обычно называют набором семафоров. Однако, в отличие от очередей сообщений, число семафоров, отслеживаемых одним объектом struct semid_ds, не изменяется в течение срока его существования. Этот массив имеет постоянный размер. Максимальная длина этого массива— SEMMSL, и эта величина установлена равной 32 директивой #define в строке . Фактическая длина массива регистрируется в члене sem_nsems объекта struct semid_ds.

sem_pending. Отслеживает очередь групп операций с семафором, находящихся в состоянии ожидания. Как и следовало ожидать, операции с семафором выполняются немедленно, если это возможно, поэтому узлы добавляются к этой очереди, только если операция должна ждать. Это примерно равнозначно членам rwait и wwait объекта struct msqid_ds.

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

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

Struct shmid_ds

Немного нарушая сложившийся подход, разработчики ядра создали тип данных struct shmid_ds не в качестве структуры данных ядра для отслеживания областей разделяемой памяти. Вместо этого, struct shmid_ds содержит основную часть этой информации, все остальное размещается в объекте struct shmid_kernel, рассматриваемом ниже. Следующие члены объекта struct shmid_ds отличаются от соответствующих членов его аналогов:

shm_segz. Размер данной области разделяемой памяти в байтах (а не страницах).

shm_nattch. Число задач, «подключенных» к этой области, если пользоваться сложившейся терминологией, иными словами, число задач, использующих эту область разделяемой памяти. Этот член представляет собой счетчик ссылок.

shm_unused, shm_unused2 и shm_unused3. Как и можно было предположить по их именам, эти члены больше не используются в данной реализации; по-видимому, их единственное назначение состоит в обеспечении неизменного размера данной структуры для обратной совместимости.

Struct shmid_kernel

Объект struct shmid_kernel существует как средство отделения «закрытой» информации, относящейся к разделяемой памяти, от «общедоступной» информации. Части объекта struct shmid_ds, к которым можно предоставить доступ пользовательским приложениям, остаются в объекте struct shmid_ds, a закрытая информация, связанная с ядром, размещается в объекте struct shmid_kernel. Пользовательские приложения должны иметь возможность передавать объект struct shmid_ds системному вызову shmctl, поэтому они должны иметь доступ к определению этого объекта, а закрытые подробности реализации, относящиеся к ядру, не должны быть выставлены на всеобщее обозрение в определении этого объекта. В ином случае, изменение реализации ядра может привести к нарушению работы приложения. Объект struct shmid_kernel имеет следующие члены:

u. Объект struct shmid_ds, то есть общедоступная часть данных.

shm_npages. Размер области разделяемой памяти в страницах. Это просто значение члена shm_segsz этого объекта, деленное на PAGE_SIZE (строка ).

shm_pages. «Таблица страниц», которая отслеживает страницы, распределенные для этой области разделяемой памяти; здесь слова «таблица страниц» заключены в кавычки, поскольку это не настоящая таблица страниц, поддерживаемая на аппаратном уровне, как было описано в предыдущей главе. Однако она выполняет такую же работу.

attaches. Связанный список областей VMA, которые отображают данную область разделяемой памяти от имени соответствующих им процессов. Области VMA описаны в .

Sys_msgctl

Можно смело утверждать, что sys_msgctl — самая большая функция в реализации очереди сообщений. Это отчасти связано с тем, что она выполняет множество различных действий, аналогично ioctl, и реализует набор слабо связанных функциональных средств. (Кстати, не обвиняйте в этой неразберихе разработчиков Linux; они просто обеспечили совместимость с уродливым проектом System V.) Параметр msqid содержит имя очереди сообщений, а cmd сообщает, что должна сделать с этой очередью функция sys_msgctl. Как вскоре станет очевидно, параметр buf может потребоваться или не потребоваться, в зависимости от cmd, и его назначение меняется от случая к случаю, даже когда он используется.

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

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

Все явные константы, которые определяют применяемые по умолчанию пределы данной реализации очереди сообщений, копируются через объект типа struct msginfo (строка ). Включается небольшая дополнительная информация, если в качестве cmd применялась MSG_INFO, а не IPC_INFO, как показано, начиная со строки , но во всем остальном эти два случая идентичны.

Обратите внимание, что буфер вызывающей программы, buf, был объявлен как указатель на объект другого типа, struct msqid_ds. Это не имеет значения. Копирование выполняется с помощью функции copy_to_user (строка ), для которой типы параметров не имеют значения, но она активизирует ошибку, получив запрос на запись в недоступную память. Если вызывающая программа предоставит указатель на достаточно большое пространство, функция sys_msgctl скопирует туда затребованные данные; за определение правильного типа (или хотя бы размера) отвечает вызывающая программа.

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

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

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

Кстати, отметим, что команда MSG_STAT предполагает, что msqid включает только индекс msgque и не содержит порядкового номера.

Вызывающая программа прошла все проверки. Функция sys_msgctl копирует затребованную информацию во временную переменную, а затем копирует временную переменную обратно через буфер вызывающей программы.

Возвращает «полный» идентификатор, в котором теперь закодирован порядковый номер (это выполняется в строке ).

Осталось три случая: IPC_SET, IPC_STAT и IPC_RMID. В отличие от рассмотренных ранее случаев, которые были полностью отработаны внутри этого переключателя, последние три выполняются здесь только частично. Первый из них, IPC_SET, предусматривает просто проверку того, что буфер, предоставленный пользователем, не равен NULL, a затем копирует его в переменную tbuf для последующей обработки далее в этой функции. (Отметим, что присваивание значения переменной err в строке вслед за копированием является лишним: переменной err будет снова присвоено значение в строке перед ее использованием.)



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

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

Выполнение оставшейся части команды IPC_STAT. Если пользователь имеет разрешение читать из очереди, функция sys_msgctl копирует статистическую информацию в буфер вызывающей программы. Если вам кажется, что это в значительной степени напоминает основную часть описанного раннее случая MSG_STAT, то вы правы. Единственным различием между этими двумя случаями является то, что MSG_STAT ожидает «неполный» msqid, как было показано выше, a IPC_STAT ожидает «полный» (то есть включающий порядковый номер).

Копирует статистические данные в пространство пользователя. Эти три строки выполнялись бы чуть быстрее, если бы были перезаписаны следующим образом:

err = 0 ; if (copy_to_user(buf, &tbuf, sizeof(*buf))) err = -EFAULT;

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

if (copy_to_user(buf, &tbuf, sizeof(*buf))) { err = -EFAULT; goto out; } err = id;

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

if (copy_to_user (buf, &tbuf, sizeof(*buf))) err = -EFAULT; else err = 0;

или

err = copy_to_user (buf, &buf, sizeof(*buf)) ? -EFAULT : 0 ;

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



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

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

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

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

Вызывающей программе нужно позволить выполнить эту операцию, поэтому выбранные параметры установлены из буфера tbuf, предоставленного вызывающей программой.

Команда IPC_RMID означает удаление указанной очереди: не только сообщений в ней, но и самой очереди. Если вызывающая программа владеет очередью или имеет возможность CAP_SYS_ADMIN, очередь освобождается с помощью вызова функции freeque (строка ).

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

case IPC_RMID: break; /* Еще нечего делать. */ default: err = -EINVAL; goto out; break; /* He достигнуто. */



Это привело бы к изменению поведения функции. Если бы вызывающая программа предоставила недопустимое значение и cmd, и msqid, она получила бы ошибку, отличную от той, которую получает сейчас: после этого изменения недопустимое значение cmd было бы обнаружено раньше недопустимого значения msqid. Однако документация к msgctl не обещает ни той, ни иной реакции, поэтому мы должны быть вправе внести это изменение. Результатом явилось бы незначительное ускорение случая с недопустимым значением cmd.

Однако, отметим, что это решение, к сожалению, требует введения пустого случая IPC_RMID в первом переключателе. Без этого функция неправильно отбросила бы IPC_RMID как неверное значение cmd. Эта дополнительная ветка case замедляет обработку, не намного, но замедляет, при нормальных условиях, в которых cmd имеет допустимое значение. К тому же, как вы знаете, ускорение выполнения редкого случая за счет обычного почти никогда не бывает хорошим решением. Поэтому лучше оставить все, как еcть.

Sys_msgget

Поскольку структура управления функции sys_msgget проще по сравнению с sys_msgsnd и sys_msgrcv, нет необходимости переводить весь код функции sys_msgget в отдельную вспомогательную функцию. Однако она имеет свои собственные вспомогательные функции, которые рассматриваются далее в этой главе.

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

Специальный ключ IPC_PRIVATE (код его объявления здесь не приведен, но его значение равно 0) говорит о том, что вызывающая программа требует создать новую очередь, независимо от того, существуют ли другие очереди сообщений с таким же ключом. В этом случае просто сразу же создается очередь с использованием функции newque (строка ), которая будет описана ниже.

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

Это утверждение может показаться преувеличенным, но имена временных файлов создают во многом аналогичную проблему— вам просто остается надеяться, что в других приложениях не будет выбрана такая же схема именования. Однако на практике эта проблема возникает редко: тип key_t с помощью typedef просто установлен в int, поэтому существует более 4-х миллиардов возможных значений на 32-разрядном компьютере и свыше 9 квинтиллионов — на 64-разрядном компьютере. Такой огромный размер пространства ключей позволяет уменьшить вероятность случайного столкновения. К тому же, схема прав доступа способствует дополнительному уменьшению вероятности возникновения проблем, даже если возникает случайное совпадение ключей очереди сообщений или имен файлов.

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

При более внимательном изучении здесь обнаруживаются две разные проблемы. Для приложения обычно не важно, каким будет имя его временного файла, при условии, что оно не конфликтует с именем существующего файла. Но приложение, как правило, должно знать заранее, каким будет ключ его очереди сообщений, чтобы другие приложения, которые хотят послать в нее сообщения, знали, в какую очередь их посылать. Если приложение выбирает ключ очереди сообщений динамически, оно должно иметь способ сообщить другим приложениям этот выбранный ключ. (Оно может с таким же успехом передавать вместо ключа параметр msqid.) А если рассматриваемые приложения уже имеют способ посылать друг другу сообщения наподобие этого, то для чего им тогда нужны очереди сообщений?

Следовательно, эта проблема, вероятно, не стоит выеденного яйца. Приложение, которое требует получения уникального ключа для очереди общего пользования, но не накладывает слишком жестких ограничений на то, каким будет этот ключ, может получить его, просто попытавшись применить ключ 1 (помните, что 0 — это ключ IPC_PRIVATE), а затем пробуя последовательные значения ключа одно за другим, пока не добьется успеха — это потребует немного больше работы, но в действительности вряд ли понадобится.

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

Если ключ не используется, sys_msgget может создать очередь. Если бит IPC_CREAT не установлен, возвращается ошибка ENOENT; в ином случае, функция newque (строка ) создает очередь.

Ключ используется. Если в вызывающей программе установлены оба бита, IPC_CREAT и IPC_EXCL, то ей в этом случае нужно было получить ошибку и она ее получает. (Это было специально сделано в виде полного аналога битов O_CREAT и O_EXCL функции open.)



Кстати, трудно сказать, выполнялась бы проверка if быстрее, если бы она была записана либо в этой, либо в следующей эквивалентной форме:

} else if (msgflg & (IPC_CREAT | IPC_EXCL) == (IPC_CREAT | IPC_EXCL)) {

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

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

В возвращаемом значении закодированы порядковый номер и индекс msgque. Оно становится параметром msgid, который вызывающая программа передаст функциям sys_msgsnd, sys_msgrcv и sys_msgctl.

Эта схема кодирования имеет две важных особенности. Более очевидная особенность состоит в том, как обеспечивается раздельное хранение части с порядковым номером и части с индексом массива: поскольку id — это индекс массива в msgque, он может только принимать значения, достигающие (но не включающие) MSGMNI, число элементов в msgque. Поэтому после умножения порядкового номера на это значение младшие биты остаются свободными для хранения id — это своего рода система счисления по основанию MSGMNI.

Отметим также, что возвращаемое значение никогда не может быть отрицательным — это важно, поскольку эта реализация библиотеки С может предусматривать интерпретацию возвращаемого отрицательного значения как ошибки. Поскольку значение MSGMNI в настоящее время установлено равным 128, индекс массива занимает младшие 7 битов возвращаемого значения. Порядковые номера занимают 16 битов, поэтому в результате этого присваивания в 1 могут быть установлены только младшие 23 бита переменной ret, а все старшие биты равны 0. Поэтому, в частности, знаковый разряд равен 0, так что переменная ret может быть только положительной или равной 0.

Итак, вычисления выполнены и теперь возвращается значение ret.

Sys_semctl

Функция sys_semctl, которая реализует системный вызов semctl, имеет много общего с функцией sys_msgctl. Поэтому здесь мы опишем только интересные различия, в частности, те команды sys_semctl, которые не имеют аналогов в sys_msgctl.

Команды GETVAL, GETPID, GETNCNT, GETZCNT и SETVAL оперируют с отдельными семафорами, а не с наборами семафоров, поэтому в этих случаях нужно вначале проверить соответствие диапазону предоставленного параметра. Если semnum находится в диапазоне, переменная curr становится указателем на соответствующий семафор.

Почти такой же набор команд — GETVAL, GETPID, GETNCNT и GETZCNT — предусматривает чтение или вычисление одного фрагмента информации о семафоре. Эта работа выполняется здесь. Обратите внимание, что верхние биты члена sempid обнуляются по маске в строке ; позже мы покажем, для чего это нужно.

Команда GETALL представляет собой запрос на получение всех значений всех семафоров в этом наборе семафоров. Как и во многих других командах, вся работа по ее выполнению не сосредоточена в одном месте; вскоре мы опишем остальное.

Команда SETVAL устанавливает семафор в заданное значение, безусловно, в заданных пределах. Опять-таки, в данный момент выполняется только часть работы, в основном, проверка диапазона.

Команда SETALL — это обобщение SETVAL; она устанавливает значения всех семафоров в этом наборе. Как и в SETVAL, в данный момент выполняется только работа по настройке, например, проверка диапазона.

Здесь начинается остальная часть программной реализации команды GETALL.

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

Копирует значения семафоров в локальный массив sem_io, а затем копирует их оттуда в пространство пользователя.

Остальная часть работы по выполнению команды SETVAL начинается здесь.

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

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

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

Все значения семафоров установлены в значения, предоставленные вызывающей программой.

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

Sys_semop

Функция sys_semop реализует системный вызов semop. Функция sys_semop не имеет прямого эквивалента в программной реализации очереди сообщений, и является аналогом функции sys_msgsnd, sys_msgrcv, или их обеих, в зависимости от того, под каким углом она рассматривается. Как бы то ни было, ее назначение состоит в выполнении одной или нескольких операций над одним или несколькими семафорами. Она пытается выполнять все операции атомарно (то есть без прерывания). Если она не может выполнить их все, она не будет выполнять ни одной из них.

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

Проверка допустимости параметров. Отметим, в частности, что значение nsops ограничено SEMOPM, максимальным числом операций над семафорами, которые можно попытаться выполнить за один раз. Это значение установлено равным 32 директивой #define в строке .

Копирует описание затребованных операций из пространства пользователя во временный буфер, sops.

Проверка наличия входа в указанной позиции массива. Можно видеть, что эквивалентом массива msgque в программной реализации очереди сообщений является semary (строка ). Отметим также, что индекс массива и порядковый номер упакованы в параметре semid таким же способом, который применялся в программной реализации очереди сообщений. Здесь, безусловно, применяется немного другая константа, SEMMNI, значение которой установлено равным 128 (и случайно совпадает со значением MSGMNI) директивой #define в строке .

Начинается цикл по всем указанным операциям. В нем вначале выполняется проверка того, не находится ли номер семафора, заданный в этой операции, вне диапазона, и если это так, он отбрасывается. Любопытно, что при неудачном завершении здесь возвращается ошибка EFBIG (которая означает, что «файл слишком велик»), а не ошибка EINVAL («недопустимый параметр»). Однако это соответствует документации.

Подсчет числа операций, для которых установлен флажок SEM_UNDO. Однако переменная undos просто применяется в качестве флажка: важно только знать, отличается ли она от 0, поэтому присвоение ей 1 (или любого другого ненулевого значения), если выполнено это условие, будет иметь одинаковый эффект. Тем не менее, версия ядра немного быстрее. А поскольку внешний цикл повторяется не более SEMOPM раз, значения undos не могут наращиваться так много раз, чтобы эта целочисленная переменная переполнилась и снова установилась в0.

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

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

Проверка того, что процесс имеет разрешение на выполнение указанных операций с семафорами. Если переменная alter имеет истинное значение, то процесс изменяет семафоры и поэтому должен иметь разрешение на запись; в ином случае, он только ожидает, пока значения одного или нескольких семафоров не установятся в 0, поэтому он просто нуждается в разрешении на чтение.



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

Процесс еще не имеет набора операций отмены для данного набора семафоров, поэтому распределяется новый набор. В соответствии с принятой практикой, которую мы уже рассматривали на примере программной реализации очереди сообщений, пространство для корректировок отмены (массив semadj) распределяется непосредственно за самим объектом struct sem_undo в составе того же распределения памяти. После этого происходит заполнение объекта struct sem_undo.

В рассматриваемом наборе операций нет операций отмены, поэтому переменная un просто устанавливается в NULL.

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

Функция try_atomic_semop возвращает 0 в случае успеха и отрицательное значение — при возникновении ошибки. В любом из этих случаев управление переходит вперед на строку .

В ином случае, функция try_atomic_semop возвращает положительное значение. Оно указывает, что операции нельзя было выполнить прямо сейчас, но процесс собирается ждать, а затем предпринять еще оцну попытку. Для начала заполняется локальный объект struct sem_queue.

Узлы, представляющие операции, которые изменят значения семафоров, размещены в конце очереди; все узлы, представляющие операции, которые ожидают достижения нуля значениями семафоров, размещаются в начале. Почему так происходит, мы покажем при описании функции update_queue (строка ) далее в этой главе.



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

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

Переходит в состояние ожидания до тех пор, пока не возникнет прерывание от сигнала или пока появится какая-то причина для выполнения повторной попытки.

Если процесс был активизирован функцией update_queue, поскольку у него теперь есть шанс добиться успеха, он повторяет операции.

Удаляет этот процесс из очереди процессов, ждущих возможности изменить набор семафоров.

Если этот набор операций изменил очередь, он мог создать условия, появления которых ждут какие-то другие процессы. Функция sys_semop вызывает update_queue, чтобы она нашла и активизировала такие процессы.

Sys_shmat

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

Дальнейшее нам уже немного знакомо: с учетом настройки функция sys_shmat начинает прорабатывать адрес, по которому эта область разделяемой памяти должна появиться в пространстве памяти вызывающего процесса. Вначале она проверяет адрес, переданный вызывающей программой. Если он равен NULL и флажок SHM_REMAP не установлен (см. строку ), запрос должен быть отвергнут, поскольку чтение или запись по адресу NULL являются недопустимыми.

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

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

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

Обратите внимание, что здесь для определения пригодности адреса используется значение SHMLBA (строка ), а не PAGE_SIZE (строка ). Однако можно видеть, что значение SHMLBA директивой #define установлено равным PAGE_SIZE, поэтому не имеет значение, какое из них здесь используется.

Но если значения SHMLBA и PAGE_SIZE одинаковы, то почему бы не убрать одно из них? Ответ состоит в том, что значение SHMLBA равно PAGE_SIZE на большинстве платформ, но не на всех. В архитектуре MIPS величина PAGE_SIZE равна 4Кб и в системе Linux значение SHMLBA определено директивой #define равным огромному числу 0x40000 (256 Кб), причем в комментарии указано, что такое большое значение было выбрано в качестве соответствия интерфейсу ABI (Application Binary Interface) компании SGI для компьютеров на основе MIPS. Однако в описании интерфейса ABI версий 2 и 3 для MIPS явно сказано, что значение SHMLBA «может принимать разные значения в соответствующих реализациях», поэтому непонятно, почему разработчики ядра предположили, что от них потребуют придерживаться величины в 256 Кб. Возможно, это значение требовалось для самой первой версии ABI, но автор просмотрел все предыдущие версии ABI, вплоть до 1.2, и не нашел такого требования.

Кроме того, в системе SPARC-64 значение SHMLBA вдвое превышает PAGE_SIZE; к сожалению, в коде нет объяснения причин этого различия.

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

Проверка того, что блок памяти размером len, начинающийся с выбранного адреса, поместится в допустимом пространстве памяти процесса. (Значение len вычисляется на несколько строк раньше, в строке .) Эта проверка явно необходима, если вызывающая программа передает подходящий адрес и, на первый взгляд, она также, видимо, нужна, когда функция sys_shmat выбирает адрес с использованием функции get_unmapped_area. Функция get_unmapped_area выполняет аналогичную проверку, но переданный ей размер области, член shm_segsz объекта struct shmid_ds, не обязательно совпадает со значением len, поскольку len является кратным величине PAGE_SIZE, a shm_segsz может не быть таковым.



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

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

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

Если вызывающая программа не имеет разрешения на использование этой области памяти, данный системный вызов завершается неудачей. Если в качестве параметра передан флажок SHM_RDONLY (только чтение), вызывающая программа нуждается только в разрешении на чтение; в ином случае, вызывающая программа нуждается в разрешении и на чтение, и на запись.

Заполнение новой области VMA. В частности, отметим, что ее член vm_ops инициализируется в значение указателя на shm_vm_ops (строка ), как описано в .

Увеличение числа ссылок на эту область, чтобы она не была преждевременно уничтожена.

Вызов функции shm_map (строка ) для отображения страниц разделяемой памяти на пространство памяти процесса. Если она терпит неудачу, то отменяет выполненные действия, уменьшая число ссылок, уничтожая область, если это была ее первая и единственная ссылка, и освобождая саму область VMA.



Обратите внимание, что область VMA не обязательно будет освобождена, даже если это последняя ссылка; эта область должна быть также отмечена флажком SHM_DEST (строка ). Флажок SHM_DEST может находиться среди флажков, установленных вызывающей программой; он может быть также установлен позже в ветви IPC_RMID функции sys_shmctl — см. строку . Благодаря этому, область разделяемой памяти может пережить все подключенные к ней процессы. Это может оказаться полезным по тем же причинам, по которым иногда может быть полезен неуничтоженный файл контрольной точки, находящийся где-то на диске: может применяться продолжительный процесс, который работает несколько часов каждую ночь, оставляя свои результаты в области разделяемой памяти, которая продолжает существовать даже после того, как текущий фрагмент работы процесса был выполнен. На следующую ночь процесс может продолжить свою работу точно с того места, где он ее прекратил, просто подключившись к этой сохранившейся области разделяемой памяти. (Безусловно, поскольку области разделяемой памяти в отличие от файлов исчезают при выключении компьютера, этот подход не применим для работы, результаты которой нельзя терять.)

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

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

Sys_shmctl

Функция sys_shmctl, безусловно, является аналогом функций sys_msgctl и sys_semctl и имеет с ними много общего. Здесь рассматриваются только две команды, относящиеся к управлению разделяемой памятью.

Команда SHM_UNLOCK обратна SHM_LOCK, оператор case которой показан в строке . Команда SHM_LOCK позволяет процессу с достаточными возможностями заблокировать целую область в физической памяти и предотвратить ее выгрузку на диск. Команда SHM_UNLOCK разблокирует заблокированную область, так что содержащиеся в ней страницы снова становятся доступными для свопинга. В обоих этих случаях выполняется не слишком много работы: в них только выполняется проверка того, что вызывающая программа имеет соответствующие возможности, а также того, что область, которая должна быть разблокирована, в настоящее время заблокирована (или наоборот), а затем установка или очистка соответствующего бита режима. Но это все, что должно быть сделано и результат появляется в функции shm_swap (строка ).

Обратите внимание, что существует отдельная возможность блокировки и разблокировки разделяемой памяти, CAP_IPC_LOCK (строка ).

Sys_shmdt

Функция sys_shmdt, которая является противоположной функции sys_shmat, отключает процесс от области разделяемой памяти.

Начинает выполнение итераций по всем областям VMA, представляющим память процесса.

Если область VMA представляет область разделяемой памяти (для определения этого предусмотрена элегантная проверка содержимого ее члена vm_ops) и область VMA начинается с целевого адреса, то нужно отменить отображение этой области VMA.

Функция do_munmap (строка ) вызывает функцию unmap_fixup (строка ), которая (не сразу) вызывает функцию shm_close в строке . Функции do_munmap и unmap_fixup описаны в .

Sys_shmget

Это, безусловно, аналог функций sys_msgget и sys_semget. Единственным новым средством является применяемое в этой функции приобретение и освобождение семафора объекта struct mm_struct данного процесса. Это семафор ядра, который не следует путать с семафором типа SystemV; семафоры ядра рассматриваются в .

Try_atomic_semop

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

Начинается цикл по всем переданным операциям с проверкой каждой из них по очереди.

Значение sem_op, равное 0, означает, что вызывающая программа должна ждать, пока значение curr->semval не достигнет 0. Следовательно, если значение curr->semval не равно 0, вызывающая программа должна заблокироваться, а это значит, что эти операции нельзя будет выполнить атомарно, или без прерываний (поскольку, пока этот процесс заблокирован, будет выполняться другая работа).

Идентификатор процесса PID вызывающей программы временно записан в нижние 16 битов объекта curr->sempid; предыдущее значение идентификатор процесса перемещается на это время в верхние 16 битов.

Выполняется корректировка curr->semval в соответствии с запросом, находящемся в sem_op, опять-таки, временно. Проверка sem_op на принадлежность к диапазону не выполняется ни здесь, ни в вызывающих эту операцию программах, но выполняется проверка принадлежности результата операции к диапазону в коде, расположенном непосредственно под этим. Это может иногда приводить к неожиданным последствиям при значениях sem_op, которые либо слишком велики, либо слишком малы, и поэтому вызывают переполнение semval с потерей первых значащих цифр.

Если установлен флажок SEM_UNDO этой операции, указывающий, что операция должна быть автоматически отменена после выхода процесса, то обновляется соответствующая структура undo. Обратите внимание, что это подразумевает, что значение un отлично от NULL; за проверку того, что это действительно так, отвечает вызывающая программа.

Проверка принадлежности к диапазону нового значения semval.

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

Метка out_of_range достигается, если операция слишком увеличила бы значение semval. Код под этой меткой просто подготавливает к возврату ошибку ERANGE, а затем переходит вперед к коду отмены.

Метка would_block достигается, если процессу пришлось бы ждать семафор либо потому, что ему пришлось бы ждать достижения семафором значения 0, либо потому, что операция не смогла приобрести семафор немедленно. Если вызывающая программа не намеревается ждать в этом случае, возвращается ошибка EAGAIN. В ином случае, функция возвращает 1 в качестве указания, что вызывающей программе нужно перейти в состояние ожидания.

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

Очевидная часть этой строки говорит о том, что в ней восстанавливаются нижние 16 битов значения curr->sempid из значения, которое было временно отложено в строке . Неочевидная часть состоит в том, что верхние 16 битов (здесь предполагается наличие 32-разрядной платформы) не обязательно заполняются нулями: в стандарте С преднамеренно оставлено на усмотрение компилятора право выбора — заполнять ли освободившиеся биты нулями или копией знакового бита. На практике компилятор применяет здесь самую быструю команду основополагающего компьютера и это иногда приводит к выбору одного из этих способов, а иногда — другого. (Именно поэтому в стандарте С не отдано предпочтение ни одному из них.) В результате, все верхние биты могут быть установлены в 0 или 1, и поэтому все биты, кроме нижних 16, заполняются по маске нулями в строке .

Update_queue

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

Если флажок состояния этого узла был уже поднят в предыдущем вызове функции update_queue, процесс, связанный с этим узлом, еще не имел шанса удалить себя из этой очереди. Функция выполняет возврат, чтобы дать другому процессу шанс выполнить свои ожидающие операции и отключить себя от очереди.

Проверка того, может ли теперь быть выполнен текущий набор ожидающих операций. В качестве последнего параметра передается q->alter, чтобы изменяющиеся операции были автоматически отменены в случае их успешного выполнения. Это связано с тем, что процесс сам будет предпринимать попытки выполнения операций, а они не должны быть выполнены дважды.

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

Если набор операций включает некоторые изменяющиеся операции, поднимается флажок q->status, чтобы процесс мог определить, что он активизирован в связи с тем, что он теперь может быть успешно выполнен; он попытается выполнить операции и удалить себя из очереди. Проверка флажка выполняется в строке , как было описано выше.

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

В ином случае, возникла ошибка. Код ошибки сохраняется в переменной q->status и этот узел очереди удаляется.

Атомарные операции

В параллельной среде некоторые действия должны выполняться атомарно, то есть без какой-либо возможности прерывания. Эти операции должны быть неделимыми, какими в свое время считались атомы.

В качестве примера рассмотрим подсчет ссылок. Если вы хотите отказаться от своей доли в разделяемом ресурсе и узнать, владеет ли им кто-то еще, вы уменьшите счетчик этого разделяемого ресурса и проверите его на равенство нулю. Типичная последовательность действий может начинаться со следующего:

Процессор загружает текущее значение счетчика (скажем, 2) в один из своих регистров.

Процессор уменьшает это значение в своем регистре; теперь оно равно 1.

Процессор записывает новое значение (1) обратно в память.

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

В однопроцессорных системах этот сценарий не вызывает особого беспокойства (за исключением некоторых случаев). Но в симметричных мультипроцессорных системах картина совершенно иная: а что будет, если окажется, что другой процессор выполняет ту же работу и в то же время? Наихудший случай выглядит примерно так:

Процессор А загружает текущее число (2) в один из своих регистров.

Процессор В загружает текущее число (2) в один из своих регистров.

Процессор А уменьшает значение в своем регистре; теперь оно равно 1.

Процессор В уменьшает значение в своем регистре; теперь оно равно 1.

Процессор А записывает новое значение (1) обратно в память.

Процессор В записывает новое значение (1) обратно в память.

Процессор А решает, что поскольку значение равно 1, этот разделяемый объект используется каким-то другим процессом, поэтому не освобождает его.

Процессор В решает, что поскольку значение равно 1, этот разделяемый объект использует какой-то другой процесс, поэтому не освобождает его.

Число ссылок в памяти теперь должно быть равно 0, но вместо этого, оно равно 1. Оба процесса удалили свои ссылки на разделяемый объект, но ни один из них его не освободил.

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

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

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

Процессор А проверяет это значение в своем регистре и обнаруживает, что оно равно 0. (Если нет, он осуществляет последующие попытки, повторяя их до тех пор, пока в регистре не появится 0.)

Процессор А записывает 1 обратно в специальное место в памяти.

Процессор А обращается к защищенному числу ссылок.

Процессор А записывает 0 обратно в специальное место в памяти.

Да... Это выглядит неприятно знакомым. Ничто не может предотвратить такого развития событий:

Процессор А загружает значение из специального места в памяти в один из своих регистров.

Процессор В загружает значение из специального места в памяти в один из своих регистров.

Процессор А проверяет значение в одном из своих регистров и обнаруживает, что оно равно 0.

Процессор В проверяет значение в одном из своих регистров и обнаруживает, что оно равно 0.

Процессор А записывает 1 обратно в специальное место в памяти.

Процессор В записывает 1 обратно в специальное место в памяти.



Процессор А обращается к защищенному числу ссылок.

Процессор В обращается к защищенному числу ссылок.

Процессор А записывает 0 обратно в специальное место в памяти.

Процессор В записывает 0 обратно в специальное место в памяти.

Но, может, для защиты специального места в памяти, которое должно защищать первоначальное место в памяти, можно использовать еще одно специальное место в памяти...

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

Па платформе х86 именно такую помощь предоставляет команда lock. (Точнее, lock — это скорее префикс, а не отдельная команда, но для наших целей эта разница не имеет значения.) Команда lock блокирует шину памяти (по меньшей мере, для указанного адреса назначения) на время выполнения следующей команды. Поскольку платформа х86 позволяет уменьшать значение прямо в памяти, без необходимости его явного предварительного чтения в регистр, мы имеем все необходимое для реализации атомарного уменьшения: нам достаточно заблокировать шину памяти, а затем немедленно выполнить команду decl с этим адресом в памяти.

Функция atomic_dec (строка ) выполняет именно это для платформы х86. Версия макрокоманды LOCK, которая определена директивой #define в строке для симметричной мультипроцессорной системы, развертывается в команду lock. (Версия для однопроцессорной системы, которая определена директивой #define двумя строками ниже, просто пуста, поскольку единственный процессор не нуждается в защите от других процессоров, и блокировка шины памяти будет напрасной тратой времени.) Теперь можно применять перед встроенным ассемблерным кодом макрокоманду LOCK и блокировать следующую команду для версий ядра симметричной мультипроцессорной системы. Если процессор В вызовет функцию atomic_dec в то время, как блокировка процессора А находится в действии, процессор В автоматически перейдет в состояние ожидания до тех пор, пока процессор А не удалит блокировку. Это успех!



Да, почти. Первоначальная проблема еще не совсем решена. Задача состояла не только в атомарном уменьшении числа ссылок, но также и в определении того, равно ли результирующее значение 0. Теперь мы может выполнять атомарное уменьшение, но что, если другой процессор успеет проскочить между этим уменьшением и проверкой результата?

К счастью, решение этой части проблемы не требует специализированной помощи процессора. Будучи заблокированной или нет, команда decl в архитектуре х86 всегда устанавливает флажок Zero процессора, если результат равен 0, и этот флажок является собственной принадлежностью процессора, поэтому никакой другой процессор не может повлиять на него между частью операций, связанной с уменьшением, и частью операций, связанной с проверкой. В соответствии с этим, в функции atomic_dec_and_test (строка ) выполняется блокированное уменьшение, как и раньше, а затем устанавливается значение локальной переменной с на основании значения флажка Zero процессора. Эта функция возвращает ненулевое (истинное) значение, если результат после уменьшения стал равен 0.

Функции atomic_dec, atomic_dec_and_test, а также другие функции, которые определены в том же файле, оперируют с объектами типа atomic_t (строка ). Объект atomic_t, как и макрокоманда LOCK, имеет разные определения для однопроцессорной системы и симметричной мультипроцессорной системы, и здесь разница состоит в том, что в случае симметричной мультипроцессорной системы введен спецификатор типа volatile, который указывает транслятору gcc, чтобы он не делал некоторых предположений относительно отмеченной переменной (например, не предполагал, что ее можно безопасно хранить в регистре).

Кстати, есть сведения, что все макрокоманды __atomic_fool_gcc, которые разбросаны по этому коду, больше не нужны; они применялись для обхода ошибки в выработке объектного кода в ранних версиях gcc.

Блокировка в цикле

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

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

Переменная блокировки в цикле, в которой выполняется проверка и установка бита, всегда имеет тип spinlock_t (строка ). Применяется только самый младший бит объекта spinlock_t; он равен 0, если блокировка доступна, и 1, если она занята. Блокировка в цикле в ее объявлении инициализируется в значение SPIN_LOCK_UNLOCKED (строка ); иначе, ее можно инициализировать с помощью функции spin_lock_init (строка ). В обоих этих случаях член блокировки spinlock_t устанавливается в 0, то есть он разблокирован.

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

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

Блокировка в цикле для чтения/записи

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

По такому же принципу, который применялся в блокировках в цикле на основе объекта типа spinlock_t, блокировки в цикле для чтения/записи представлены объектом типа rwlock_t (строка ), который может быть инициализирован в объявлении с помощью RW_LOCK_UNLOCKED (строка ). Макрокомандами самого низкого уровня, предназначенными для работы с rwlock_t, являются read_lock, read_unlock, write_lock и write_unlock; они рассматриваются в настоящем разделе. Все макрокоманды, которые будут описаны вслед за этими макрокомандами, и которые строятся на их основе, станут вполне понятными после изучения этих первых четырех макрокоманд.

В комментарии в строке указано, что член lock объекта rwlock_t имеет отрицательное значение, если какой-то процесс владеет блокировкой записи. Он равен 0, если нет ни процессов чтения, ни процессов записи, и положителен, если есть процессы чтения, но нет процессов записи; в этом случае значение lock показывает число процессов чтения.

Cli и sti

Как было описано в , макрокоманды cli и sti применяются, соответственно, для запрещения и разрешения прерываний. В однопроцессорной системе каждая из них сводится к единственной команде cli или sti. Этого недостаточно для симметричной мультипроцессорной системы, в которой нужно не только запретить прерывания для данного локального процессора, но также временно исключить возможность обработки прерываний на всех других процессорах. Поэтому в симметричной мультипроцессорной системе макрокоманды cli и sti становятся вызовами функций __global_cli и __global_sti.

Down

Операция down уменьшает величину count семафора. Можно было надеяться, что ее реализация будет столь же элементарной, как и само это понятие, но увы, жизнь не настолько проста.

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

У читателя может возникнуть вопрос: может ли произойти антипереполнение величины count? He может: процесс после уменьшения величины count всегда переходит в состояние ожидания, поэтому каждый конкретный процесс может захватить одновременно только один семафор, и в запасе есть еще намного больше отрицательных значений величины типа int по сравнению с числом процессов.

Если знаковый разряд установлен, семафор отрицателен. Это значит, что значение count было равным 0 или отрицательным непосредственно перед тем, как было уменьшено, поэтому процесс не сумел получить семафор и должен перейти в состояние ожидания до тех пор, пока семафор не станет доступным. Реализация этого потребовала применения в следующих нескольких строках многих хитростей. Команда js выполняет переход, если знаковый разряд установлен (то есть, если результат команды decl был отрицателен), и 2f обозначает цель перехода. Здесь 2f — не шестнадцатиричное значение, а специальный синтаксис ассемблера GNU: 2 означает переход к локальному символу «2», a f — поиск этого символа впереди. (2b означало бы поиск самого последнего локального символа «2» сзади.) Этот локальный символ находится в строке .

Ветвление не выполнено, поэтому процесс получил семафор. Это фактически конец функции down, несмотря на то, что он так не выглядит. Это вскоре станет ясно.

Одной из самых сложных для понимания частей функции down является директива .section, находящаяся непосредственно перед адресатом перехода, которая указывает, что следующий код нужно собрать в отдельной секции ядра: в секции под названием .text.lock. Данная секция будет размещаться в памяти и рассматриваться как выполнимая программа. Это указано флажком ах — строкой, которая следует за именем секции; обратите внимание, что этот флажок ах не имеет ничего общего с регистром АХ процессора х86. В результате ассемблер перемещает команды в строках и из секции down, в которой они находятся, в другую секцию выполнимого кода ядра, поэтому объектный код, вырабатываемый на основе этих строк, не является физически смежным с кодом, вырабатываемом на основе предыдущих строк. Вот почему строка представляет собой конец функции down.

Это адресат перехода, достигаемый, если нельзя было получить семафор. Команда pushl $1b (ее можно также записать и без знака $) не помещает в стек шестнадцатиричное значение 1b — это была бы команда pushl S0x1b. Вместо этого, данное значение 1b представляет собой тот же синтаксис ассемблера GNU, с которым мы ранее встретились в случае применения 2f: он указывает на адрес команды, в данном случае — на адрес первой локальной метки «1», которая встретится при поиске в обратном направлении. Таким образом, эта команда помещает в стек адрес строки ; данный адрес станет адресом возврата, чтобы после последующего перехода ход выполнения вернулся к концу функции down.

Переход отсюда к функции __down_failed (не включена в эту книгу). Эта функция сохраняет несколько регистров в стеке и вызывает функцию __down (строка ), которая будет описана ниже, для выполнения работы по ожиданию семафора. После возврата из функции __down функция __down_failed возвращается к down, которая также выполняет возврат. Функция __down не выполняет возврат до тех пор, пока процесс не приобретет семафор; в результате, когда бы ни произошел возврат из функции down, процесс имеет семафор, независимо от того, получил ли он его немедленно или должен был ждать.

Назначение директивы ассемблера .previous не описано в документации, но она должна означать возвращение к предыдущей секции и прекращение действия директивы .section в строке .

DOWN_HEAD

Эта макрокоманда просто переводит задачу tsk (которая была объявлена в макрокоманде DOWN_VAR) в состояние, указанное параметром task_state, а затем добавляет tsk к очереди заданий, ждущих семафора. И наконец, она начинает бесконечный цикл; размещенные в цикле функции __down и __down_interruptible прервут этот цикл, когда будут готовы выйти.

Down_interruptible

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

Первым отличием является то, что функция down_interruptible возвращает значение типа int для указания того, получила ли она семафор или была остановлена каким-то сигналом. Возвращаемое значение (которое представлено переменной result) равно 0 в первом случае и отрицательно— в последнем. Это частично выполняется в строке , где переменная result обнуляется, если функция приобрела семафор без ожидания.

Вторым отличием является то, что функция down_interruptible переходит на функцию __down_failed_interruptible (не включена в эту книгу), а не на функцию __down_failed. Следуя принципам, применяемым в функции __down_failed, __down_failed_interruptible просто корректирует несколько регистров и вызывает функцию __down_interruptible (строка ), которая будет описана ниже. Отметим, что адрес возврата, установленный для функции __down_failed_interruptible, строка , следует за командой xorl, которая обнуляет переменную result в том случае, если семафор был приобретен сразу же. Возвращаемое значение функции __down_interruptible будет скопировано в переменную result.

Функция __down_interruptible, по существу, аналогична функции __down, за исключением того, что она разрешает прерывания по сигналу.

Следовательно, функция waking_non_zero_interruptible (не рассматривается) вызывается при захвате семафора. Она возвращает 0, если ей не удалось захватить семафор, возвращает 1, если она его получила, или –EINTR, если она была прервана каким-то сигналом. В первом случае цикл продолжается.

В ином случае, функция __down_interruptible выходит, возвращая 0 (а не 1), если она получила семафор, или –EINTR, если была прервана.

DOWN_TAIL

Эта макрокоманда начинается со связанной с окончанием цикла по переводу задачи tsk снова в состояние task_state в ходе подготовки к повторной попытке захватить семафор.

Произошел выход из этого цикла; задача tsk либо приобрела семафор, либо была прервана каким-то сигналом (только в функции __down_interruptible). Так или иначе, задача готова продолжить выполнение и больше не ждет семафора, поэтому она снова переводится в состояние TASK_RUNNING и извлекается из очереди ожидания семафора.

Down_trylock

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

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

DOWN_VAR

Это первая из трех макрокоманд, где размещен некоторый код, общий для функций __down и __down_interruptible. В ней просто объявлено несколько переменных.

__Global_cli

Копирует регистр EFLAGS процессора в локальную переменную flags.

Флажок Interrupts Enabled в архитектуре х86— это девятый бит регистра EFLAGS, что позволяет понять определение EFLAG_IF_SHIFT в строке . Эта переменная применяется для проверки того, были ли прерывания уже отменены, и в этом случае больше ничего не нужно делать для их отмены.

Запрещает прерывания на этом процессоре.

Если этот процессор еще не обрабатывает запрос на прерывание, функция __global_cli вызывает функцию get_irqlock (строка ) для приобретения глобальной блокировки прерываний. Если процессор уже обрабатывает какой-то запрос на прерывание, то он уже владеет глобальной блокировкой прерываний, как будет показано ниже.

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

__Global_sti

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

Снова разрешает прерывания на этом процессоре.

Irq_enter

Вызов функции hardirq_enter (строка ) для атомарного увеличения как глобального счетчика прерываний, так и локального счетчика прерываний для этого процессора. Она регистрирует тот факт, что данный процессор обрабатывает запрос на прерывание.

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

Irq_enter и irq_exit

В мельком упоминались однопроцессорные версии этих функций. Область кода, заключенная внутри пары irq_enter/irq_exit, является атомарной по отношению к любой другой подобной области; она также является атомарной по отношению к парам cli/sti.

Irq_exit

Эта функция просто переходит к функции hardirq_exit (строка ), которая является обратной функции hardirq_enter. Кстати отметим, что и в функции irq_enter, и в функции irq_exit параметр irq игнорируется, по крайней мере, в архитектуре х86.

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

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

Lock_kernel

Эта довольно простая функция приобретает глобальную блокировку ядра; при этом, внутри любой пары lock_kernel/unlock_kernel должен находиться самое большее один процессор. В однопроцессорной системе это, безусловно, была бы пустая команда.

Член lock_depth процесса первоначально был равен –1 (см. строку ). Когда это значение меньше 0 (если оно меньше 0, оно всегда равно –1), процесс не владеет блокировкой ядра; если оно больше или равно 0, он владеет блокировкой ядра. Поэтому единственный процесс может вызвать функцию lock_kernel, затем, не достигнув unlock_kernel, может вызвать другую функцию, которая также вызовет функцию lock_kernel. В этом случае процессу просто будет немедленно предоставлена блокировка ядра, а это именно то, что нам требуется. Поэтому, если после увеличения значения lock_depth процесса оно становится равным 0, процесс перед этим не владел блокировкой. Поэтому в данном случае функция приобретает блокировку в цикле, kernel_flag (строка ).

Lock_kernel и unlock_kernel

Эти функции имеют также версии, относящиеся к архитектуре х86; здесь рассматриваются только универсальные версии.

Понятия и примитивы параллельного программирования

Компьютер с симметричной мультипроцессорной архитектурой, в котором установлено два процессора, очевидно, простейшая из всех возможных параллельных конфигураций, но даже простейшая конфигурация открывает широкую область новых проблем; говорят, что иногда легче пасти стаю кошек, чем добиться гармоничной совместной работы двух одинаковых процессоров. К счастью, на эту тему существует широкий и хорошо изученный фонд научных исследований, проводимых, по меньшей мере, в течение последних 30 лет. (Это довольно продолжительное время, если учесть, что первые электронно-цифровые ЭВМ были созданы только около 50 лет тому назад.) Мы можем значительно упростить свою работу, если перед изучением того, как поддержка симметричной мультипроцессорной обработки влияет на код ядра, дадим обзор некоторых теоретических понятий, на которых основана эта поддержка.

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

Проверка и установка

Классическим параллельным примитивом является проверка и установка. Операция проверки и установки атомарно читает значение из какого-то места в памяти и записывает в него новое значение, возвращая старое. Как правило, в этом месте может находиться 0 или 1, и новым значением, которое записывает операция проверки и установки является 1, то есть «установка». Противоположностью операции проверки и установки является операция проверки и очистки, которая выполняет то же, за исключением того, что записывает 0 вместо 1. Некоторые варианты операции проверки и установки могут записывать либо 1, либо 0, поэтому две операции, проверка и установка или проверка и очистка, сводятся к одной операции только с разными операндами.

Примитив проверки и установки позволяет реализовать любые другие операции, предназначенные для параллельного выполнения. (И действительно, на некоторых процессорах в качестве параллельного примитива предусмотрена только проверка и установка.) Например, проверка и установка может применяться для защиты счетчика ссылок в предыдущем примере. Мы пытались применить аналогичный метод: прочитать значение из места в памяти, проверить, равняется ли оно 0 и если да, записать 1 и перейти на этап доступа к защищенному значению. Эта попытка оказалось неудачной не потому, что была логически не обоснована, а потому, что не было способа реализовать ее атомарно. При наличии атомарного примитива проверки и установки мы можем превратить decl в атомарную команду без применения команды lock.

Однако проверка и установка имеет свои недостатки:

Это примитив низкого уровня. Если предусмотрен только он, на его основе придется реализовать все другие примитивы.

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

Команда lock процессора х86 позволяет упростить реализацию примитивов более высокого уровня, но в архитектуре х86 можно также применять атомарную проверку и установку. Самый прямолинейный способ состоит в применении команды lock в сочетании с btsl (bit-test-and-set — поразрядная проверка и установка). Такой подход применяется в блокировках в цикле, которые рассматриваются далее в этой главе.

Еще одним способом реализации проверки и установки в архитектуре х86 является применение предусмотренной в ней команды xchg (exchange — обмен), которая автоматически трактуется процессором х86, как если бы ей предшествовала команда lock, во всяком случае, когда один из ее операндов находится в памяти.

Команда xchg является более универсальной по сравнению с сочетанием lock/btsl, поскольку она позволяет обменивать одновременно 8, 16 или 32 бита, а не просто 1 бит.

Кроме одного применения в коде arch/i386/kernel/entry.S, в ядре команда xchg скрыта за макрокомандой xchg (строка ), которая, в свою очередь, реализована на основе функции __xchg (строка ). Это сделано для того, чтобы в коде ядра макрокоманду xchg можно было использовать в части кода, независимой от архитектуры; на каждой платформе предусмотрена собственная эквивалентная реализация этой макрокоманды.

Интересно, что макрокоманда xchg является основой еще одной макрокоманды, tas (test-and-set, проверка и установка, строка ). Однако эта макрокоманда в коде ядра нигде не используется.

В ядре макрокоманда xchg иногда применяется для выполнения простой проверки и установки (но не обязательно для повторного прохода по циклу до тех пор, пока блокировка не станет доступной, как в строке ), а также применяется для других целей (как в строке ).

Read_lock

Начинает работу с атомарного увеличения значения члена lock объекта rwlock_t. Это рискованная операция и она может быть отменена.

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

Имеется процесс записи. Макрокоманда read_lock отменяет результат увеличения в строке .

Циклическое повторение в ожидании, когда член lock объекта rwlock_t станет равным 0 или положительным.

Переход назад к строке для повторной попытки.

Release

Часть функции release, не связанная с симметричной мультипроцессорной системой, рассматривалась в , а здесь процесс-зомби отправляется в могилу и освобождается его объект struct task_struct.

Проверка того, владеет ли процесс процессором. (Процессор, которым владеет этот процесс, мог еще не успеть очистить этот флажок; это вскоре будет сделано.) Если нет, функция release выходит из цикла и приступает, как обычно, к освобождению объекта struct task_struct.

Иначе функция release ждет очистки флажка has_cpu процесса. Когда это произойдет, функция release снова повторит свою попытку. Это внешне странная ситуация (процесс уничтожен, но владеет процессором) встречается действительно редко, но не является невероятной. Процесс мог быть уничтожен на одном процессоре, который еще не нашел времени, чтобы очистить флажок has_cpu, a родитель данного процесса проверяет значение этого флажка с другого процессора.

Reschedule_idle

Функция reschedule_idle вызывается из функции wake_up_process, когда активизируемый процесс (идентификатор которого передается функции reschedule_idle в качестве параметра р) уже не находится в очереди выполнения. Функция пытается запланировать вновь активизированный процесс на другой процессор (холостой).

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

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

Как уже упоминалось при описании функции schedule, член avg_slice процесса представляет собой взвешенную среднюю оценку потребления им процессорного времени, поэтому эта величина позволяет узнать, существует ли вероятность того, что определенный процесс будет непрерывно использовать процессор в течение относительно длительного времени, если он продолжит работу. Если нет, то этот процесс, вероятно, связан со вводом/выводом, во всяком случае он, по-видимому, не связан с интенсивным использованием процессора. Поскольку цель состоит в повышении общей пропускной способности за счет максимального распараллеливания, предоставление этому процессу, не связанному с использованием большого количества процессорного времени, другого процессора для его работы, вероятно, не имеет смысла.

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

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

Reschedule_idle_slow

Функция reschedule_idle_slow, как сказано в этих комментариях, пытается найти холостой процессор для размещения на нем процесса с идентификатором р. Алгоритм основан на том наблюдении, что первые n входов массива заданий представляют собой холостые системные процессы, по одному на каждый из n процессоров компьютера. Холостые процессы работают тогда (и только тогда), когда ни один другой процесс на данном процессоре не хочет получить к нему доступ. Холостой процесс обычно переводит процессор в режим ожидания с малым потреблением энергии с помощью команды hlt, если это возможно. Следовательно, просмотр в цикле первых n процессов в массиве задач— это все, что требуется для поиска холостого процессора, если он существует. Функция reschedule_idle_slow просто опрашивает каждый холостой процесс, выполняется ли он в настоящее время; если да, то процессор, на котором он работает, должен быть холостым и поэтому должен быть хорошим кандидатом для размещения на нем процесса р.

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

Устанавливает локальные переменные. Здесь best_cpu представляет собой процессор, на котором сейчас работает процесс р; это — «наилучший» процессор, поскольку, если процесс р останется здесь, то не придется промывать кэш или нести другие издержки, a this_cpu обозначает процессор, на котором работает функция reschedule_idle_slow.

Переменные idle и tsk проходят по массиву задач, a target_tsk представляет собой последний найденный работающий холостой процесс (или NULL, если такового нет).

Переменная i инициализируется функцией smp_num_cpus (которая была вызвана за n итераций перед этим) и ведет обратный отсчет при каждой итерации.

Если установлен флажок has_cpu этой холостой задачи, она активно работает на своем процессоре (мы будем называть его «целевым процессором»). Если нет, то целевой процессор занят какой-то другой задачей, поэтому он не является холостым и функция reschedule_idle_slow не будет пытаться запланировать процесс р на него. Здесь проявляется оборотная сторона проблемы, упомянутой перед этим: тот факт, что процессор сейчас не является холостым, не означает, что вскоре на нем не закончат свою работу все его процессы и не сделают его холостым. Но функция reschedule_idle_slow не имеет способа узнать об этом, поэтому она вполне может предполагать, что целевой процессор на какое-то время будет занят. Во всяком случае, вполне вероятно, что так оно и будет, и даже если случится иное, то достаточно скоро на этот процессор, который только что стал холостым, будут запланированы какие-то другие процессы.

Однако, если целевой процессор является текущим процессором, он будет пропущен. Такое решение кажется неожиданным, но так или иначе это — «невероятный» случай: счетчик холостого процесса является отрицательным, поэтому проверка в строке должна была заранее предотвратить возможность достижения настоящей функцией данной точки.

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



Здесь функция reschedule_idle_slow проверяет, является ли холостым процессор, на котором работает процесс р. Если только что найденный холостой процессор является именно тем процессором, на котором уже размещен процесс р, функция переходит вперед к метке send (строка ), чтобы запланировать процесс р на этот процессор.

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

Если в этом цикле обнаружены какие-либо холостые процессоры, холостая задача процессора отмечается для перепланирования и функция smp_send_reschedule (строка ) посылает на этот процессор прерывание IPI, чтобы он перепланировал свои процессы.

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

Schedule

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

Вычисление величины промежутка времени, который истек с того момента, как функция schedule была запланирована на выполнение на этом процессоре, и регистрация текущего числа циклов на следующий раз, когда это снова произойдет. (Переменная schedule_data— это часть предназначенного для каждого процессора массива aligned_data, который определен в строке .)

Член avg_slice процесса (строка ) следит за тем, как долго процесс в среднем владел процессором в течение срока своего существования. Но это не простое среднее, а взвешенное среднее, в котором недавнее поведение процесса влияет на результаты намного сильнее, чем его поведение в отдаленном прошлом. (Поскольку настоящие компьютеры обладают конечной точностью, часть, относящаяся к «отдаленному прошлому», в конечном итоге приближается к нулю, когда прошлое становится достаточно отдаленным.) Этот член используется в функции reschedule_idle (строка , которая рассматривается ниже) в качестве одного из оснований для принятия решения о том, направлять ли процесс на другой процессор. Поэтому он не нужен и не вычисляется для однопроцессорного случая.

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

При переключении контекста функция schedule регистрирует процесс, который теряет доступ к данному процессору; это нужно для работы функции __schedule_tail, которая рассматривается ниже.

__Schedule_tail

Если задача, которая только что потеряла доступ к процессору, изменила свое состояние (это описано в предыдущем комментарии), она отмечается для дальнейшего перепланирования.

Поскольку ядро отключилось от этого процесса, он больше не имеет доступа к данному процессору и этот факт регистрируется.

Семафоры

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

Теперь вы, наверное, представляете себе, как можно построить семафоры с применением либо проверки и установки, для двоичных («одноключевых») семафоров, либо с применением такой функция, как atomic_dec_and_test, для счетных семафоров. Именно это и применяется в ядре: в нем семафоры представлены целыми числами, а функции down (строка ) и up (строка ), в числе прочих, служат для уменьшения и увеличения этого целого. Как будет вскоре показано, основополагающий код уменьшения и увеличения значений целочисленных переменных аналогичен тому, который применяется в atomic_dec_and_test и подобных функциях.

В качестве исторической справки отметим, что впервые понятие семафора формализовал голландский ученый Эдсгер Дийкстра (Edsger Dijkstra), поэтому фундаментальные операции над семафорами названы по-голландски— Proberen и Verhogen, которые обычно сокращенно обозначают Р и V. Эти слова переводятся как «проверка» (что означает проверку того, доступен ли ключ и взятие его, если да) и «приращение» (возвращение ключа снова на гвоздь). Эти первые буквы стали источником терминов «procure» (приобрести) и «vacate» (освободить), которые были введены в предыдущей главе. Однако в ядре Linux эта традиция нарушена и соответствующие операции получили названия down и up.

В ядре для представления семафоров используется очень простой тип: struct semaphore, который определен в строке . Он имеет только три члена:

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

Макрокоманда sema_init (строка ) позволяет инициализировать count с установкой в любое значение, поэтому семафоры ядра могут быть двоичными (если величина count инициализирована значением 1) или счетными (если предусмотрено какое-то другое положительное начальное значение). Весь код семафора ядра полностью поддерживает и двоичные, и счетные семафоры, и первый тип семафора является просто особым случаем последнего. Однако на практике величина count всегда инициализируется значением 1, поэтому семафоры ядра всегда являются двоичными. Тем не менее, ничто не препятствует применению разработчиками счетных семафоров в будущем.

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

waking. Используется временно в течение и после операции up; эта величина устанавливается в 1, если up освобождает семафор, и в 0 — в ином случае.

wait. Очередь процессов, которые должны были быть приостановлены в ожидании, пока этот семафор не станет снова доступным.

Send_IPI_single

Функция send_IPI_single посылает одно прерывание IPI (interprocessor interrupt — это принятое в компании Intel сокращение для межпроцессорного прерывания) на указанный процессор назначения. В этот момент ядро взаимодействует с локальным контроллером APIC процессора-отправителя на довольно низком уровне.

Получение содержимого верхней половины регистра команды прерывания (ICR — Interrupt Command Register) — регистра, через который запрограммирован локальный контроллер APIC, но с полем назначения, установленным в dest. Несмотря на использование «2» в функции __prepare_ICR2 (строка ), в процессоре фактически имеется один ICR, а не два. Но это 64-разрядный регистр, который принято рассматривать в ядре как два 32-разрядных регистра, поэтому в коде ядра «ICR» означает младшие 32 бита регистра, a «ICR2» — старшие 32 бита. Поле регистра ICR с обозначением процессора назначения, которое нужно установить, находится в старших 32 битах, то есть в ICR2.

Запись измененной информации обратно в ICR. В ICR теперь содержится информация о процессоре назначения.

Вызов функции __prepare_ICR (строка ) для установки вектора прерываний, который нужно послать в процессор назначения. (Обратите внимание: ничто не препятствует тому, чтобы процессором назначения был текущий процессор, поскольку ICR вполне способен послать любое прерывание IPI в свой собственный процессор. Однако автор не может придумать ни одной причины, по какой это может потребоваться.)

Отправляет прерывание, записывая новую конфигурацию ICR.

Smp_local_timer_interrupt

Эта функция является применяемым в симметричной мультипроцессорной системе аналогом функции update_process_times (строка ), применяемой только в однопроцессорных системах. Она выполняет все, что выполняет update_process_times (обновляет статистическую информацию процесса и ядра об использовании процессора), а также кое-что еще. Необычно то, что мультипроцессорная версия этих средств не была введена в однопроцессорную функцию, а была создана полностью отдельная функция такого же назначения. После изучения этой функции легко понять, почему было сделано именно так: она настолько отличается от однопроцессорной версии, что попытка объединить две версии для разных архитектур была бы бессмысленной. Функция smp_local_timer_interrupt может быть вызвана из двух мест:

Из функции smp_apic_timer_interrupt (строка ), которая вырабатывает прерывание от таймера для симметричной мультипроцессорной системы. Ее настройка выполняется в строке с использованием макрокоманды BUILD_SMP_TIMER_INTERRUPT, которая определена директивой #define в строке .

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

В этом функции update_process_times и smp_local_timer_interrupt имеют много общего: они обе вызывают функцию update_one_process для выполнения работы по обновлению статистической информации об использовании процессора отдельным процессом.

Уменьшает значение счетчика процесса (его динамический приоритет), отмечая его для перепланирования, если он исчерпан.

Обновление статистической информации ядра. Как и в функции update_process_times, время, израсходованное в режиме пользователя, будет отнесено либо к отсчету в ядре «времени пребывания в режиме с высоким значением nice» (с низким приоритетом), либо к отсчету обычного времени пользователя, в зависимости от того, находился ли приоритет данного процесса ниже DEF_PRIORITY.

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

Smp_send_reschedule

Эта однострочная функция, применение которой показано далее в этой главе, просто посылает прерывание на целевой процессор, идентификатор которого задан в качестве параметра. Она вызывает функцию send_IPI_single (строка ) с указанием идентификатора процессора и вектора RESCHEDULE_VECTOR. Вектор RESCHEDULE_VECTOR, наряду с другими векторами прерываний процессора, объявлен директивой #define в блоке, который начинается в строке .

Softirq_trylock

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

Проверка и установка бита 0 переменной global_bh_count. Хотя ее имя может вызывать другие ассоциации, переменная global_bh_count всегда равна либо 0, либо 1, поскольку может работать самое большее одна «нижняя половина». Во всяком случае, если переменная global_bh_count уже равна 1, это значит, что уже работает какая-то «нижняя половина», поэтому управление переходит к концу функции.

Если также доступна блокировка global_bh_lock, то на этом процессоре могут выполняться «нижние половины». Это аналогично системе с двумя блокировками, которая используется в однопроцессорном случае.

Функция softirq_trylock не смогла приобрести блокировку global_bh_lock, поэтому она отменяет свои действия.

Spin_lock_string

Эта макрокоманда имеет код, общий для всех макрокоманд блокировки примитива блокировки в цикле. Она также используется в предназначенных для архитектуры х86 версиях функций lock_kernel и unlock_kernel (которые не включены в эту книгу, хотя их универсальные версии — включены; см. строки и ).

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

При успешном завершении этой операции управление передается дальше; в ином случае, в макрокоманде spin_lock_string выполняется переход вперед к строке (команда btsl помещает старое значение бита во флажок Carry процессора, и поэтому здесь применяется команда jc). Это тот же прием, с которым мы уже встречались три раза: цель перехода находится в отдельной секции ядра.

Команда стоит в жестком цикле, повторно проверяя младший бит блокировки в цикле. Обратите внимание, что команды btsl и testb интерпретируют свой первый операнд по-разному: для btsl это — битовая позиция, а для testb — битовая маска. Следовательно, в строке происходит проверка того же бита, который макрокоманда spin_lock_string пыталась (и не смогла) установить в строке , даже несмотря на то, что в первом случае используется операнд $0, а во втором — операнд $1.

Бит был очищен, поэтому макрокоманда spin_lock_string должна выполнить еще одну попытку его захватить. Она переходит назад к строке . Этот код можно было бы упростить только до двух команд и префикса lock:

1: lock ; btsl $0, %0 jc 1b

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

Spin_unlock_string

Тривиальный случай: просто сброс бита блокировки примитива блокировки в цикле.

Unlock_kernel

Аналогичным образом, если уничтожение блокировки ядра приводит к уменьшению значения lock_depth ниже нуля, это значит, что процесс выходит из последней пары lock_kernel/unlock_kernel, в которой он находился. В этом случае должна быть разблокирована блокировка kernel_flag, чтобы ядро могли заблокировать другие процессы. Проверка знакового разряда результата (то есть применение «< 0», а не «== –1») заставляет транслятор gcc выработать немного более эффективный код и кроме этого, возможно, заставляет ядро корректно обрабатывать ситуацию при появлении несбалансированных пар lock_kernel/unlock_kernel (или не обрабатывать, в зависимости от принятого сценария).

Up

Мы подробно рассмотрели, что происходит, когда ядро пытается приобрести семафор, а также что происходит, когда это не удается. Теперь настало время рассмотреть другую сторону этого уравнения: что происходит при освобождении семафора. Эта часть сравнительно проста.

Атомарное увеличение значения count семафора.

Если результат— меньше или равен 0, какой-то процесс ждет активизации. Функция up переходит вперед к строке .

В функции up применяется такой же прием, как и в функции down: все последующие действия выполняются в отдельной секции ядра, а не в самой функции up. Адрес конца функции up помещается в стек и функция up переходит к функции __up_wakeup (не рассматривается). Она выполняет такие же манипуляции с регистрами, как и в функции __down_failed, и вызывает функцию __up, которая рассматривается ниже.

Функция __up отвечает за активизацию всех процессов, ждущих данный семафор.

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

Используется макрокоманда wake_up (строка ), которая просто вызывает функцию __wake_up (строка ) для активизации всех ждущих процессов.

Усовершенствованные программируемые контроллеры прерываний и связь между процессорами

Спецификация мультипроцессорной обработки компании Intel основана на использовании усовершенствованных программируемых контроллеров прерываний (APIC— Advanced Programmable Interrupt Controller). Процессоры взаимодействуют друг с другом, посылая друг другу прерывания. Подключив к прерываниям запросы на выполнение действий, процессоры могут до определенной степени управлять работой друг друга. Каждый процессор имеет свой собственный APIC (называемый локальным контроллером APIC для данного процессора) и имеется также единственный контроллер APIC ввода/вывода, который обрабатывает прерывания, поступающие от устройств ввода/вывода. В обычной мультипроцессорной системе Intel контроллер APIC ввода/вывода занимает место микросхемы контроллера прерываний, которая мельком упоминалась в .

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

Влияние SMP на планирование

Функция schedule (строка ) является функцией планировщика ядра и была рассмотрена очень подробно в . Версия schedule для симметричной мультипроцессорной системы имеет два основных отличия от версии для однопроцессорной системы:

Блок кода, начинающийся со строки в самой функции schedule, который вычисляет некоторую информацию, необходимую в другом месте.

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

__Wake_up

Как описано в , функция __wake_up активизирует все процессы в переданной ей очереди ожиданий, если они находятся в одном из состояний, предусмотренных параметром mode. При вызове из функции wake_up она активизирует все, что находится в состояниях TASK_UNINTERRUPTIBLE или TASK_INTERRUPTIBLE; при вызове из функции wake_up_interruptible (строка ), она активизирует только задачи, находящиеся в состоянии TASK_INTERRUPTIBLE.

Процессы активизированы функцией wake_up_process (строка ), которая была кратко описана выше и будет рассмотрена более подробно далее в этой главе.

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

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

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

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

Write_lock

Выдача сигнала о том, что какой-то процесс хочет приобрести блокировку записи: проверка и установка знакового бита блокировки для обеспечения отрицательного значения члена lock.

Если знаковый бит уже установлен, какой-то еще процесс владеет блокировкой записи; макрокоманда write_lock переходит вперед к строке (которая, как и прежде, находится в другой секции ядра).

Больше никто не пытался получать блокировку записи, но процессы чтения все еще могут существовать. Поскольку знаковый бит установлен, никакой иной процесс чтения не сможет приобрести эту блокировку чтения, но макрокоманда write_lock все еще обязана ждать, пока не исчезнут все прочие существующие процессы чтения. Она начинает работу с проверки того, установлен ли какой-либо из 31 бита в младших разрядах, что может служить свидетельством того, что значение lock перед этим было положительным. Если нет, то значение lock перед инверсией знакового бита было равно 0, а это значит, что нет процессов чтения, следовательно, данный процесс записи может безопасно продолжить свою работу, поэтому управление просто переходит дальше. Однако, если среди 31 бита в младших разрядах был установлен хоть один бит, это значит, что имеются процессы чтения, поэтому макрокоманда write_lock переходит к строке , чтобы там ожидать завершения их работы.

Данный процесс является единственным процессом записи, но есть еще процессы чтения. Макрокоманда write_lock на данный момент очищает знаковый бит (она снова захватит его позднее). Любопытно отметить, что эти манипуляции со знаковым битом не нарушают правильности операций процессов чтения с членом lock. Рассмотрим в качестве примера приведенную ниже последовательность событий:

Два процесса чтения увеличивают значение lock; теперь шестнадцатиричное значение lock равно 0x00000002.

Потенциальный процесс записи устанавливает знаковый бит; теперь lock имеет значение 0x80000002.

Один из процессов чтения уходит; теперь lock имеет значение 0x80000001.

Процесс записи обнаруживает, что не все оставшиеся биты равны 0; это значит, что есть еще процессы чтения. Таким образом, процесс записи все еще не может приобрести блокировку записи и поэтому очищает знаковый бит; теперь значение lock равно 0x00000001.

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

Циклическое выполнение в ожидании, пока значение счетчика не упадет до 0, то есть в ожидании, пока не уйдут все процессы чтения. В действительности, нулевое значение показывает, что не только ушли все процессы чтения, но и никто иной еще не приобрел блокировку записи.

По-видимому, ушли все процессы чтения и записи; макрокоманда write_lock начинает все сначала и снова захватывает блокировку записи.

---

---