Оболочка и утилиты системы UNIX

У многих версий системы UNIX имеется графический интерфейс пользователя, схожий с популярными интерфейсами, примененными на компьютере Macintosh и впоследствии в системе Windows. Однако истинные программисты до сих пор предпочитают интерфейс командной строки, называемый оболочкой (shell). По­добный интерфейс значительно быстрее в использовании, существенно мощнее и проще расширяется. Ниже будет кратко описана так называемая оболочка Бурна (sh).

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

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

Программа вроде оболочки не должна открывать терминал, чтобы прочитать с него или вывести на него строку. Вместо этого запускаемые программы автома­тически получают доступ к файлу, называемому стандартным устройством вво­да (standard input), и к файлу, называемому стандартным устройством вывода (standard output), а также к файлу, называемому стандартным уст­ройство для вывода сообщений об ошибках (standard error). По умолчанию всем трем устрой­ствам соответствует терминал, то есть клавиатура для ввода и экран для вывода. Многие программы в системе UNIX читают данные со стандартного устройства ввода и пишут на стандартное устройство вывода. Стандартные ввод и вывод также можно перенаправить, что является очень полезным свойством. Для этого используются символы «<» и «>» соответственно. Разрешается их одновременное использование в одной командной строке. Программа, считывающая данные со стандартного устройства ввода, выполняющая определенную обработку этих данных и записывающая результат в поток стандартного вывода, называется фильтром.

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

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

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

Пользовательский интерфейс UNIX состоит не только из оболочки, но также из большого числа стандартных обслуживающих программ, называемых также утили­тами. К ним относятся команды управления файлами и каталогами, фильтры, средства разработки программ (такие как текстовые редакторы и компи­ляторы), текстовые процессоры, программы системного администрирования и другие программы. Стандарт POSIX 1003.2 определяет синтаксис и семантику менее 100 из этих программ, в основном относящихся к первым трем категориям. Идея стандарти­зации данных программ заключается в том, чтобы можно было писать сценарии оболочки, которые работали бы на всех системах UNIX. Помимо этих стандарт­ных утилит, существует множество других прикладных программ, таких как web-браузеры, программы просмотра изображений и т. д.

Структура ядра системы UNIX

Нижний уровень ядра состоит из драйверов устройств и процедуры диспетче­ризации процессов. Все драйверы системы UNIX делятся на два класса: драйверы символьных устройств и драйверы блочных устройств. Основное различие между этими двумя классами устройств заключается в том, что на блочных устройствах разрешается операция поиска, а на символьных нет. Технически сетевые устрой­ства представляют собой символьные устройства, но они обрабатываются по-ино­му, поэтому их правильнее выделить в отдельный класс. Диспетчеризация процессов производится при возникновении прерывания. При этом низкоуровневая программа останавливает выполнение ра­ботающего процесса, сохраняет его состояние в таблице процессов ядра и запус­кает соответствующий драйвер. Кроме того, диспетчеризация процессов произво­дится также, когда ядро завершает свою работу и наступает время для того, чтобы снова запустить процесс пользователя. Программа диспетчеризации процессов написана на ассемблере и представляет собой отдельную от процедуры планирования программу.

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

Сетевое программное обеспечение часто бывает модульным, с поддержкой мно­жества различных устройств и протоколов. Уровень выше сетевых драйверов вы­полняет своего рода функции маршрутизации, гарантируя, что правильный пакет направляется правильному устройству или блоку управления протоколами. Боль­шинство систем UNIX содержат в своем ядре полноценный маршрутизатор Ин­тернета, и хотя его производительность ниже, чем у аппаратного маршрутизатора, эта программа появилась раньше современных аппаратных маршрутизаторов. Над уровнем маршрутизации располагается стек протоколов, обязательно включая протоколы IP и TCP, но также иногда и некоторые дополнительные протоколы. Над сетевыми протоколами располагается интерфейс сокетов, позволяющий про­граммам создавать сокеты для отдельных сетей и протоколов. Для использования сокетов пользовательские программы получают дескрипторы файлов.

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

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

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

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

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

Процессы в UNIX

Основные понятия

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

В операционной системе UNIX посредством системного вызова fork создается точная копия исходного процесса (так называемого родительского процесса). Новый процесс называется дочерним процессом. У ро­дительского и у дочернего процессов есть свои собственные образы памяти. Если родительский процесс впоследствии изменяет какие-либо свои переменные, из­менения остаются невидимыми для дочернего процесса, и наоборот.

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

У родительского процесса может быть много дочерних процессов. Поскольку у дочерних процессов также могут быть до­черние процессы, исходный процесс может создать целое дерево детей, внуков, правнуков и т. д.

В системе UNIX процессы могут общаться друг с другом с помощью разно­видности обмена сообщениями. Можно создать канал между двумя процессами, в который один процесс может писать поток байтов, а другой процесс может его читать. Эти каналы иногда называют трубами. Синхронизация процессов дости­гается путем блокирования процесса при попытке прочитать данные из пустого канала. Когда данные появляются в канале, процесс разблокируется.

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

Сигналы в UNIX используются и для других целей. Например, если процесс выполняет вычисления с плавающей точкой и непреднамеренно делит число на 0, он получает сигнал исключения при выпол­нении операции с плавающей точкой. Сигналы UNIX описываются стандартом POSIX. В большинстве систем UNIX также имеются дополни­тельные сигналы, но программы, использующие их, могут оказаться непереноси­мыми на другие версии UNIX.

В первых версиях системы UNIX понятия потоков не существовало. После введения этого понятия и возможности управления потоками были стандартизированы соответствующие системные вызовы в виде части стандарта POSIX – P1003.1c.

В исходном варианте стандарта POSIX не указывается, должны ли потоки реализовываться в про­странстве ядра или в пространстве пользователя. Преимущество потоков в пользо­вательском пространстве состоит в том, что они легко реализуются без необходи­мости изменения ядра, а переключение потоков осуществляется очень эффективно. Недостаток потоков в пространстве пользователя заключается в том, что если один из потоков заблокируется (например, на операции ввода-вывода, семафоре или страничном прерывании), все потоки процесса блокируются. Ядро полагает, что существует только один поток, и не передает управление процессу потока, пока блокировка не снимется. Таким образом, системные вызовы, определенные в части стан­дарта P1003.1c были подобраны так, чтобы потоки могли быть реализова­ны любым способом. До тех пор, пока пользовательские программы четко придер­живаются семантики стандарта POSIX – P1003.1c, оба способа реализации работают корректно. Когда используется системная реализация потоков, они явля­ются настоящими системными вызовами. При использовании потоков на уровне пользователя они полностью реализуются в динамической библиотеке в простран­стве пользователя.

Синхронизация потоков может осуществляться при помощи мьютексов. Как правило, мьютекс охраняет какой-либо ресурс, например буфер, совместно исполь­зуемый двумя потоками. Чтобы гарантировать, что только один поток в каж­дый момент времени имеет доступ к общему ресурсу, предполагается, что потокиблокируют (захватывают) мьютекс перед обращением к ресурсу и разблокируют (отпускают) его, когда ресурс им более не нужен. До тех пор пока потоки со­блюдают данный протокол, состояния состязания можно избежать. Напомним, что название мьютекс (mutex) образовано от английских слов mutual exclusion – взаимное исключение, так как мьютексы по­добны двоичным семафорам, то есть семафорам, способным принимать только зна­чения 0 и 1. Таким образом мьютекс может находиться в одном из двух состояний: блокированный и разблокированный. Поток может заблокировать мьютекс с помощью системного вызова. Если мьютекс уже заблокирован, то поток, обратившийся к этому вызову, блокируется. Когда поток, захвативший мьютекс, выполнил свою работу в критической области, он должен освободить мьютекс, обратившись к соответствующему системному вызову.

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

Реализация процессов в UNIX

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

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

Информация в таблице процессов подразделяется на следующие категории:

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

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

3. Сигналы. Маски, указывающие, какие сигналы игнорируются, какие пере­хватываются, какие временно заблокированы, а какие находятся в процессе доставки.

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

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

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

1. Машинные регистры. Когда происходит прерывание с пере-ключением в ре­жим ядра, машинные регистры (включая регистры с плавающей точкой) сохраняются здесь.

2. Состояние системного вызова. Информация о текущем системном вызове, включая параметры и результаты.

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

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

5. Стек ядра. Фиксированный стек для использования процессом в режиме ядра.

Рассмотрим подробне, как в системе UNIX создаются процессы. Когда выполняется системный вызов fork, вызываю­щий процесс обращается в ядро и ищет свободную ячейку в таблице процессов, в которую можно записать данные о дочернем процессе. Если свободная ячейка находится, системный вызов копирует туда информацию из ячейки родительского процесса. Затем он выделяет память для сегментов данных и для стека дочернего процесса, куда копируются соответствующие сегменты родительского процесса. Структура пользователя (которая часто хранится вместе с сегментом стека) копи­руется вместе со стеком. Программный сегмент может либо копироваться, либо использоваться совместно, если он доступен только для чтения. Начиная с этого момента дочерний процесс может быть запущен.

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

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

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

Затем следует создать и заполнить новое адресное пространство. Если си­стемой поддерживается отображение файлов на адресное пространство памяти, как, например, в System V, BSD и в большинстве других версий UNIX, то таблицы страниц настраиваются следующим образом: в них указывается, что страниц в па­мяти нет, кроме, возможно, одной страницы со стеком, а содержимое адресного пространства может подгружаться из исполняемого файла на диске. Когда новый процесс начинает работу, он немедленно вызывает страничное прерывание, в ре­зультате которого первая страница программы подгружается с диска. Таким обра­зом, ничего не нужно загружать заранее, что позволяет быстро запускать про­граммы, а в память загружать только те страницы, которые действительно нужны программам. Наконец, в стек копируются аргументы и строки окружения, сигна­лы сбрасываются, а все регистры устанавливаются на ноль. С этого момента новая команда начинает исполнение.

Реализация потоков зависит от того, поддерживаются они ядром или нет. Если потоки ядром не поддерживаются, как, например, в 4BSD, реализация потоков целиком осуществляется в библиотеке, загружающейся в пространстве пользователя.

Планирование в системе UNIX

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

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

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

Раз в секунду приоритет каждого процесса пересчитывается по формуле, со­стоящей из суммы трех компонентов. Первой составляющей этой формулы является параметр использования центрального процессора, представляющий собой среднее значение тиков (прерываний) таймера в секунду, которые процесс работал в тече­ние последних нескольких секунд. При каждом тике таймера счет­чик использования центрального процессора в таблице процессов увеличивается на единицу. Этот счетчик в конце концов добавляется к приоритету процесса, увеличивая тем самым числовое значение его приоритета (что соответствует бо­лее низкому приоритету), в результате чего процесс попадает в менее приоритет­ную очередь. Однако в UNIX процесс не находится в конце очереди бесконечно долго, и величина параметра использования центрального процессора со временем уменьша­ется. В различных версиях UNIX это уменьшение выполняется по-разному. Один из способов состоит в том, что к этому параметру прибавляется полученное число тиков, после чего сумма делится на два. Такой алгоритм учитывает самое последнее значение числа тиков с весовым коэффициентом 1/2, предшествующее ему – с весовым коэффициентом 1/4 и т. д. Алгоритм взвешивания очень быстр, так как состоит из всего одной операции сложения и одного сдвига, но также применяются и другие схемы взвешивания.

Второй составляющей формулы является так называемый параметр nice. Его значение по умолчанию рав­но 0, но допустимый диапазон значений, как правило, составляет от -20 до +20. Процесс может установить значение nice в диапазоне от 0 до 20 с помощью систем­ного вызова. Только системный администратор может запросить обслуживание с более высоким приоритетом (то есть значения nice от -20 до -1).

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

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

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

1. Потоки реального времени, обслуживаемые по алгоритму FIFO.

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

3. Потоки разделения времени.

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

У каждого потока есть приоритет планирования. Значение по умолчанию рав­но 20, но оно может быть изменено при помощи специального системного вызова, вычитающего некоторое значение в диапа­зоне от -20 до +19 из 20. Поэтому возможные значения приоритетов попадают в промежуток от 1 до 40. Цель алгоритма планирования состоит в том, чтобы обеспечить грубое пропорциональ­ное соответствие качества обслуживания приоритету (то есть чем выше приори­тет, тем меньше должно быть время отклика и тем большая доля процессорного времени достанется процессу).

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

7.3. Управление памятью в UNIX

Основные понятия

У каждого процесса в системе UNIX есть адресное пространство, состоящее из трех сегментов: текста (программы), данных и стека. Текстовый (программный) сегмент содержит машинные команды, образующие исполняемый код программы. Он создается компилятором и ассемблером при трансляции программы, написанной на языке высокого уровня, в машинный код. Как правило, тексто­вый сегмент разрешен только для чтения. Текстовый сегмент не изменяется ни в размерах, ни по своему содержанию.

Сегмент данных содержит переменные, строки, массивы и другие данные про­граммы. Он состоит из двух частей: инициализированных данных и неинициали­зированных данных. По историческим причинам вторая часть называется BSS (Bulk Storage System – запоминающее устройство большой емкости или массовое запоминающее устройств). Инициализированная часть сегмента данных содержит переменные и константы компилятора, значения которых должны быть заданы при запуске программы. Например, на языке С можно объявить символьную строку и в то же время за­дать ее значение, то есть проинициализировать ее. Когда программа запускается, она предполагает, что в этой строке уже содержится некий осмысленный текст. Чтобы реализовать это, компилятор назначает строке определенное место в адрес­ном пространстве и гарантирует, что в момент запуска программы по этому адресу будет располагаться соответствующая строка. С точки зрения операционной сис­темы, инициализированные данные не отличаются от текста программы – тот и другой сегменты содержат сформированные компилятором последовательности битов, загружаемые в память при запуске программы.

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