ос и с. ОСиС. 1. Классификация программного обеспечения
 Скачать 2.7 Mb.
|
Листинг 2. Окончание процедуры инициализации ядра Linuxif (execute_command) execve(execute_command,argv_init, envp_init); execve(”/sbin/init”,argv_init,envp_init); execve(”/etc/init”,argv_init,envp_init); execve(”/bin/init”,argv_init,envp_init); execve(”/bin/sh”,argv_init,envp_init); panic(”No init found. Try passing init= option to kernel.”);} Первый процесс в системе запускается при инициализации ядра. Пожалуй, даже человеку, не умеющему программировать, достаточно будет взглянуть на конец процедуры инициализации ядра Linux (см. листинг 2), чтобы понять, как определяется выполняемая в этом процессе программа: вначале делается попытка «переключить» процесс на файл, указанный в командной строке ядра (есть и такая...), потом на файлы /sbin/init, /etc/init, /bin/init и напоследок на /bin/sh. Смерть процесса Рассмотрев рождение процесса, логично будет обсудить и его смерть. Когда процесс закончит работу (нормально или аварийно), он уничтожается, освобождая все использовавшиеся им ресурсы компьютера. Обратимся еще раз к примеру, рассмотренному выше. Когда мы нажатием Если родительский процесс по какой-то причине завершится раньше дочернего, последний становится «сиротой» (orphaned process). «Сироты» автоматически «усыновляются» программой init, выполняющейся в процессе с номером 1, которая и принимает сигнал об их завершении. Если же потомок уже завершил работу, а предок не готов принять от системы сигнал об этом событии, то потомок не исчезает полностью, а превращается в «зомби» (zombie); в поле Stat такие процессы помечаются буквой Z. Зомби не занимает процессорного времени, но строка в таблице процессов остается, и соответствующие структуры ядра не освобождаются. После завершения родительского процесса «осиротевший» зомби на короткое время также становится потомком init, после чего уже «окончательно умирает». Наконец, процесс может надолго впасть в «сон», который не удается прервать: в поле Stat это обозначается буквой D. Процесс, находящийся в таком состоянии, не реагирует на системные запросы и может быть уничтожен только перезагрузкой системы. О сигналах Постойте, но ведь приглашение командного интерпретатора появилось и тогда, когда мы нажали Сигналы посылаются одними процессами другим с помощью команды, которая носит устрашающее название kill, хотя в общем случае никого не убивает. Все зависит от конкретного сигнала, и практически любой сигнал при необходимости может быть процессом проигнорирован. Исключение составляют KILL, который «без разговоров» уничтожает процесс, и STOP, который его аналогичным образом останавливает. Правила о том, какой процесс какому имеет право послать сигнал, достаточно сложны. Суперпользователь, очевидно, может посылать сигналы любым процессам, а обычный пользователь — только своим, но здесь есть масса тонкостей: например, нельзя послать сигнал CONT (продолжить выполнение остановленного процесса) своему же процессу, запущенному в другой сессии. Работа с нитями требует особой техники, поскольку одни сигналы должны «доводиться до сведения» всех нитей, а другие — посылаться индивидуально. В Linux 2.2 это делалось путем довольно хитрых манипуляций со специальной нитью, единственным назначением которой было управление другими нитями. В версии 2.4 ядро может следить за нитями за счет нового флага CLONE_PARENT (таким образом, если одна нить породит другую и закончит работу, то порожденная нить не останется «сиротой») и нескольких специальных правил доставки сигналов, так что надобность в специальной нити отпала. Компьютерная демонология Демоном (daemon) в Unix (и в Linux) называется процесс, предназначенный для работы в фоновом режиме без терминала и выполняющий какие-либо действия для других процессов (не обязательно на вашей машине). Обычно демоны тихо занимаются своим делом, и вспоминают о них только в случае каких-либо неполадок в их работе: например, демону начинает недоставать места, и он посылает пользователю сообщение об этом, или демон перестает работать, и вам звонит босс с вопросом, почему у него принтер опять не печатает и когда это прекратится... На многих машинах демоны, обслуживающие процессы других компьютеров, нужны достаточно редко, так что держать их в памяти постоянно загруженными и транжирить на это ресурсы системы нерационально. Для управления их работой был создан супердемон, которого зовут вовсе не Вельзевулом (в компьютерных демонах вообще мало «демонического» — они ближе демонам Максвелла), а куда скромнее — inetd (что, как вы догадались, является сокращением от Internet daemon). В конфигурационном файле inetd (/etc/inetd.conf) записано, какой демон обслуживает обращения к какому сервису Internet. Обычно с помощью inetd вызываются программы pop3d, imap4d, ftpd, telnetd (предоставляю читателю определить, какие именно сервисы они обслуживают) и некоторые другие. Эти программы не являются постоянно активными, а значит, не могут считаться демонами в строгом смысле слова, но поскольку они порождаются «полноценным» демоном, их все равно так называют. Продвинутые средства общения Процессы посылают друг другу сигналы, передают данные через неименованные и именованные каналы, а также «гнезда». Все это замечательно, но как быть, если один процесс должен передавать другому огромные объемы информации и притом быстро (это нужно, например, при воспроизведении видео)? Могут ли процессы, адресные пространства которых строго разделены, каким-либо образом получить в совместное пользование часть памяти? Да, с помощью временных файлов. Для передачи обширных массивов данных между процессами служит системный вызов mmap, представляющий собой довольно неожиданное применение страничной виртуальной памяти. Он позволяет, грубо говоря, сказать: «я хочу обращаться к такому-то участку такого-то файла как к оперативной памяти». Данные, которые процесс читает из указанной области памяти, по мере надобности считываются из файла, а те, которые он туда пишет, когда-нибудь попадут на диск. Но процесс сам не работает с диском, этим занимается ядро. Если два процесса обращаются таким образом к одному и тому же участку одного и того же файла, данные будут переданы непосредственно от одного процесса к другому. Конечно, периодически ядро сбрасывает данные на диск. В некоторых случаях это полезно, но когда mmap обеспечивает только общение процессов между собой, обмен с диском лишь замедляет работу. Для процессов, имеющих общего предка, можно использовать флаг MAP_ANONYMOUS, указывающий, что данные не должны попадать в файл (дескриптор файла тогда никак не используется и может быть любым). Вызов mmap применяется также для «загрузки в память» исполняемых файлов и библиотек, так что если программа использует 25 библиотек общим объемом во много десятков мегабайт, это вовсе не значит, что она и в памяти будет занимать такое же количество мегабайт. С помощью временных файлов можно, кроме того, синхронизировать работу процессов, используя возможности системы, предназначенные для работы с рекомендательными (advisory) блокировками файлов. Это позволяют сделать системные вызовы fcntl и его более быстрый и простой вариант flock. Иногда создавать временные файлы нежелательно, поэтому в Linux включены также функции для общения процессов из Unix SVR4 (Unix System V Release 4). Это shmget — создание области памяти для общения процессов, semget — создание семафора, msgget — создание очереди сообщений. В версии 2.4 к ним добавились еще более мощные функции mq_open, shm_open из SUS2 (Single Unix Specification Version 2). Получение информации о процессах Для работы с информацией о процессах, которую выводят на терминал программы ps и top, в Linux используется достаточно необычный механизм: особая файловая система procfs. В большинстве дистрибутивов она монтируется при запуске системы как каталог /proc. Данные о процессе с номером 1 (обычно это /sbin/init) содержатся в подкаталоге /proc/1, о процессе с номером 364 — в /proc/364, и т. д. Все файлы, открытые процессом, представлены в виде символических ссылок в каталоге /proc/ /fd, а ссылка на корневой каталог процесса хранится как /proc/ /root. Со временем у файловой системы procfs появились и другие функции. Например, командой echo 100000 > /proc/sys/fs/file-max суперпользователь может определить, что в системе разрешается открыть до 100 000 файлов, а команда echo 0 > /proc/sys/kernel/cap-bound отнимет у всех процессов в системе все дополнительные права, т. е. фактически лишит систему понятия «суперпользователь». Полезную информацию позволяет получить программа lsof, которая выдает список всех файлов, используемых сейчас процессами, включая каталоги, занятые потому, что какой-либо процесс использует их в качестве текущего или корневого; разделяемые библиотеки, загруженные в память; и т. д. В следующей статье мы поговорим о командном интерпретаторе, его роли в системе и вообще о том, как из отдельных процессов и файлов складывается нечто единое. 14. Семафоры Поддержка системы UNIX в многопроцессорной конфигурации может включать в себя разбиение ядра системы на критические участки, параллельное выполнение которых на нескольких процессорах не допускается. Такие системы предназначались для работы на машинах AT&T 3B20A и IBM 370, для разбиения ядра использовались семафоры (см. [Bach 84]). Нижеследующие рассуждения помогают понять суть данной особенности. При ближайшем рассмотрении сразу же возникают два вопроса: как использовать семафоры и где определить критические участки. Если при выполнении критического участка программы процесс приостанавливается, для защиты участка от посягательств со стороны других процессов алгоритмы работы ядра однопроцессорной системы UNIX используют блокировку. Механизм установления блокировки: выполнять пока (блокировка установлена) /* операция проверки */ приостановиться (до снятия блокировки); установить блокировку; механизм снятия блокировки: снять блокировку; вывести из состояния приостанова все процессы, приостановленные в результате блокировки;  Рисунок 12.5. Конкуренция за установку блокировки в многопроцессорных системах Блокировки такого рода охватывают некоторые критические участки, но не работают в многопроцессорных системах, что видно из Рисунка 12.5. Предположим, что блокировка снята и что два процесса на разных процессорах одновременно пытаются проверить ее наличие и установить ее. В момент t они обнаруживают снятие блокировки, устанавливают ее вновь, вступают в критический участок и создают опасность нарушения целостности структур данных ядра. В условии одновременности имеется отклонение: механизм не сработает, если перед тем, как процесс выполняет операцию проверки, ни один другой процесс не выполнил операцию установления блокировки. Если, например, после обнаружения снятия блокировки процессор A обрабатывает прерывание и в этот момент процессор B выполняет проверку и устанавливает блокировку, по выходе из прерывания процессор A так же установит блокировку. Чтобы предотвратить возникновение подобной ситуации, нужно сделать так, чтобы процедура блокирования была неделимой: проверку наличия блокировки и ее установку следует объединить в одну операцию, чтобы в каждый момент времени с блокировкой имел дело только один процесс. Определение семафоров Семафор представляет собой обрабатываемый ядром целочисленный объект, для которого определены следующие элементарные (неделимые) операции: Инициализация семафора, в результате которой семафору присваивается неотрицательное значение; Операция типа P, уменьшающая значение семафора. Если значение семафора опускается ниже нулевой отметки, выполняющий операцию процесс приостанавливает свою работу; Операция типа V, увеличивающая значение семафора. Если значение семафора в результате операции становится больше или равно 0, один из процессов, приостановленных во время выполнения операции P, выходит из состояния приостанова; Условная операция типа P, сокращенно CP (conditional P), уменьшающая значение семафора и возвращающая логическое значение "истина" в том случае, когда значение семафора остается положительным. Если в результате операции значение семафора должно стать отрицательным или нулевым, никаких действий над ним не производится и операция возвращает логическое значение "ложь". Реализация семафоров Дийкстра [Dijkstra 65] показал, что семафоры можно реализовать без использования специальных машинных инструкций. На Рисунке 12.6 представлены реализующие семафоры функции, написанные на языке Си. Функция Pprim блокирует семафор по результатам проверки значений, содержащихся в массиве val; каждый процессор в системе управляет значением одного элемента массива. Прежде чем заблокировать семафор, процессор проверяет, не заблокирован ли уже семафор другими процессорами (соответствующие им элементы в массиве val тогда имеют значения, равные 2), а также не предпринимаются ли попытки в данный момент заблокировать семафор со стороны процессоров с более низким кодом идентификации (соответствующие им элементы имеют значения, равные 1). Если любое из условий выполняется, процессор переустанавливает значение своего элемента в 1 и повторяет попытку. Когда функция Pprim открывает внешний цикл, переменная цикла имеет значение, на единицу превышающее код идентификации того процессора, который использовал ресурс последним, тем самым гарантируется, что ни один из процессоров не может монопольно завладеть ресурсом (в качестве доказательства сошлемся на [Dijkstra 65] и [Coffman 73]). Функция Vprim освобождает семафор и открывает для других процессоров возможность получения исключительного доступа к ресурсу путем очистки соответствующего текущему процессору элемента в массиве val и перенастройки значения lastid. Чтобы защитить ресурс, следует выполнить следующий набор команд: Pprim(семафор); команды использования ресурса; Vprim(семафор); В большинстве машин имеется набор элементарных (неделимых) инструкций, реализующих операцию блокирования более дешевыми средствами, ибо циклы, входящие в функцию Pprim, работают медленно и снижают производительность системы. Так, например, в машинах серии IBM 370 поддерживается инструкция compare and swap (сравнить и переставить), в машине AT&T 3B20 - инструкция read and clear (прочитать и очистить). При выполнении инструкции read and clear процессор считывает содержимое ячейки памяти, очищает ее (сбрасывает в 0) и по результатам сравнения первоначального содержимого с 0 устанавливает код завершения инструкции. Если ту же инструкцию над той же ячейкой параллельно выполняет еще один процессор, один из двух процессоров прочитает первоначальное содержимое, а другой - 0: неделимость операции гарантируется аппаратным путем. Таким образом, за счет использования данной инструкции функцию Pprim можно было бы реализовать менее сложными средствами (Рисунок 12.7). Процесс повторяет инструкцию read and clear в цикле до тех пор, пока не будет считано значение, отличное от нуля. Начальное значение компоненты семафора, связанной с блокировкой, должно быть равно 1. Как таковую, данную семафорную конструкцию нельзя реализовать в составе ядра операционной системы, поскольку работающий с ней процесс не выходит из цикла, пока не достигнет своей цели. Если семафор используется для блокирования структуры данных, процесс, обнаружив семафор заблокированным, приостанавливает свое выполнение, чтобы ядро имело возможность переключиться на контекст другого процесса и выполнить другую полезную работу. С помощью функций Pprim и Vprim можно реализовать более сложный набор семафорных операций.
Рисунок 12.6. Реализация семафорной блокировки на Си Для начала дадим определение семафора как структуры, состоящей из поля блокировки (управляющего доступом к семафору), значения семафора и очереди процессов, приостановленных по семафору. Поле блокировки содержит информацию, открывающую во время выполнения операций типа P и V доступ к другим полям структуры только одному процессу. По завершении операции значение поля сбрасывается. Это значение определяет, разрешен ли процессу доступ к критическому участку, защищаемому семафором. В начале выполнения алгоритма операции P (Рисунок 12.8) ядро с помощью функции Pprim предоставляет процессу право исключительного доступа к семафору и уменьшает значение семафора. Если семафор имеет неотрицательное значение, текущий процесс получает доступ к критическому участку. По завершении работы процесс сбрасывает блокировку семафора (с помощью функции Vprim), открывая доступ к семафору для других процессов, и возвращает признак успешного завершения. Если же в результате уменьшения значение семафора становится отрицательным, ядро приостанавливает выполнение процесса, используя алгоритм, подобный алгоритму sleep : основываясь на значении приоритета, ядро проверяет поступившие сигналы, включает текущий процесс в список приостановленных процессов, в котором последние представлены в порядке поступления, и выполняет переключение контекста. Операция V (Рисунок 12.9) получает исключительный доступ к семафору через функцию Pprim и увеличивает значение семафора. Если очередь приостановленных по семафору процессов непуста, ядро выбирает из нее первый процесс и переводит его в состояние "готовности к запуску".
Рисунок 12.6. Реализация семафорной блокировки на Си (продолжение) Операции P и V по своему действию похожи на функции sleep и wakeup. Главное различие между ними состоит в том, что семафор является структурой данных, тогда как используемый функциями sleep и wakeup адрес представляет собой всего лишь число. Если начальное значение семафора - нулевое, при выполнении операции P над семафором процесс всегда приостанавливается, поэтому операция P может заменять функцию sleep. Операция V, тем не менее, выводит из состояния приостанова только один процесс, тогда как однопроцессорная функция wakeup возобновляет все процессы, приостановленные по адресу, связанному с событием. С точки зрения семантики использование функции wakeup означает: данное системное условие более не удовлетворяется, следовательно, все приостановленные по условию процессы должны выйти из состояния приостанова. Так, например, процессы, приостановленные в связи с занятостью буфера, не должны дальше пребывать в этом состоянии, если буфер больше не используется, поэтому они возобновляются ядром. Еще один пример: если несколько процессов выводят данные на терминал с помощью функции write, терминальный драйвер может перевести их в состояние приостанова в связи с невозможностью обработки больших объемов информации. Позже, когда драйвер будет готов к приему следующей порции данных, он возобновит все приостановленные им процессы. Использование операций P и V в тех случаях, когда устанавливающие блокировку процессы получают доступ к ресурсу поочередно, а все остальные процессы - в порядке поступления запросов, является более предпочтительным. В сравнении с однопроцессорной процедурой блокирования (sleep-lock) данная схема обычно выигрывает, так как если при наступлении события все процессы возобновляются, большинство из них может вновь наткнуться на блокировку и снова перейти в состояние приостанова. С другой стороны, в тех случаях, когда требуется вывести из состояния приостанова все процессы одновременно, использование операций P и V представляет известную сложность.
Рисунок 12.7. Операции над семафором, использующие инструкцию read and clear Если операция возвращает значение семафора, является ли она эквивалентной функции wakeup? while (value(semaphore) < 0) V(semaphore); Если вмешательства со стороны других процессов нет, ядро повторяет цикл до тех пор, пока значение семафора не станет больше или равно 0, ибо это означает, что в состоянии приостанова по семафору нет больше ни одного процесса. Тем не менее, нельзя исключить и такую возможность, что сразу после того, как процесс A при тестировании семафора на одноименном процессоре обнаружил нулевое значение семафора, процесс B на своем процессоре выполняет операцию P, уменьшая значение семафора до -1 (Рисунок 12.10). Процесс A продолжит свое выполнение, думая, что им возобновлены все приостановленные по семафору процессы. Таким образом, цикл выполнения операции не дает гарантии возобновления всех приостановленных процессов, поскольку он не является элементарным.
Рисунок 12.8. Алгоритм выполнения операции P Рассмотрим еще один феномен, связанный с использованием семафоров в однопроцессорной системе. Предположим, что два процесса, A и B, конкурируют за семафор. Процесс A обнаруживает, что семафор свободен и что процесс B приостановлен; значение семафора равно -1. Когда с помощью операции V процесс A освобождает семафор, он выводит тем самым процесс B из состояния приостанова и вновь делает значение семафора нулевым. Теперь предположим, что процесс A, по-прежнему выполняясь в режиме ядра, пытается снова заблокировать семафор. Производя операцию P, процесс приостановится, поскольку семафор имеет нулевое значение, несмотря на то, что ресурс пока свободен. Системе придется "раскошелиться" на дополнительное переключение контекста. С другой стороны, если бы блокировка была реализована на основе однопроцессорной схемы (sleep-lock), процесс A получил бы право на повторное использование ресурса, поскольку за это время ни один из процессов не смог бы заблокировать его. Для этого случая схема sleep-lock более подходит, чем схема с использованием семафоров.
Рисунок 12.9. Алгоритм выполнения операции V Когда блокируются сразу несколько семафоров, очередность блокирования должна исключать возникновение тупиковых ситуаций. В качестве примера рассмотрим два семафора, A и B, и два алгоритма, требующих одновременной блокировки семафоров. Если бы алгоритмы устанавливали блокировку на семафоры в обратном порядке, как следует из Рисунка 12.11, последовало бы возникновение тупиковой ситуации; процесс A на одноименном процессоре захватывает семафор SA, в то время как процесс B на своем процессоре захватывает семафор SB. Процесс A пытается захватить и семафор SB, но в результате операции P переходит в состояние приостанова, поскольку значение семафора SB не превышает 0. То же самое происходит с процессом B, когда последний пытается захватить семафор SA. Ни тот, ни другой процессы продолжаться уже не могут. Для предотвращения возникновения подобных ситуаций используются соответствующие алгоритмы обнаружения опасности взаимной блокировки, устанавливающие наличие опасной ситуации и ликвидирующие ее. Тем не менее, использование таких алгоритмов "утяжеляет" ядро. Поскольку число ситуаций, в которых процесс должен одновременно захватывать несколько семафоров, довольно ограничено, легче было бы реализовать алгоритмы, предупреждающие возникновение тупиковых ситуаций еще до того, как они будут иметь место. Если, к примеру, какой-то набор семафоров всегда блокируется в одном и том же порядке, тупиковая ситуация никогда не возникнет. Но в том случае, когда захвата семафоров в обратном порядке избежать не удается, операция CP предотвратит возникновение тупиковой ситуации (см. Рисунок 12.12): если операция завершится неудачно, процесс B освободит свои ресурсы, дабы избежать взаимной блокировки, и позже запустит алгоритм на выполнение повторно, скорее всего тогда, когда процесс A завершит работу с ресурсом. Чтобы предупредить одновременное обращение процессов к ресурсу, программа обработки прерываний, казалось бы, могла воспользоваться семафором, но из-за того, что она не может приостанавливать свою работу, использовать операцию P в этой программе нельзя. Вместо этого можно использовать "циклическую блокировку" (spin lock) и не переходить в состояние приостанова, как в следующем примере:  Рисунок 12.10. Неудачное имитация функции wakeup при использовании операции V  Рисунок 12.11. Возникновение тупиковой ситуации из-за смены очередности блокирования  Рисунок 12.12. Использование операции P условного типа для предотвращения взаимной блокировки Операция повторяется в цикле до тех пор, пока значение семафора не превысит 0; программа обработки прерываний не приостанавливается и цикл завершается только тогда, когда значение семафора станет положительным, после чего это значение будет уменьшено операцией CP. Чтобы предотвратить ситуацию взаимной блокировки, ядру нужно запретить все прерывания, выполняющие "циклическую блокировку". Иначе выполнение процесса, захватившего семафор, будет прервано еще до того, как он сможет освободить семафор; если программа обработки прерываний попытается захватить этот семафор, используя "циклическую блокировку", ядро заблокирует само себя. В качестве примера обратимся к Рисунку 12.13. В момент возникновения прерывания значение семафора не превышает 0, поэтому результатом выполнения операции CP всегда будет "ложь". Проблема решается путем запрещения всех прерываний на то время, пока семафор захвачен процессом.  Рисунок 12.13. Взаимная блокировка при выполнении программы обработки прерывания |