Глава 2
Процессы и потоки

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

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

Рис. 2.1. Четыре программы в многозадачном режиме (а); принципиальная модель четырех независимых последовательных процессов (б); в каждый момент времени активна только одна программа (в)

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

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

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

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

1. Инициализация системы.
2. Выполнение изданного работающим процессом системного запроса на создание процесса.
3. Запрос пользователя на создание процесса.
4. Инициирование пакетного задания.

Обычно при загрузке операционной системы создаются несколько процессов. Некоторые из них являются высокоприоритетными процессами, то есть обеспечивающими взаимодействие с пользователем и выполняющими заданную работу. Остальные процессы являются фоновыми, они не связаны с конкретными пользователями, но выполняют особые функции. Например, один фоновый процесс может быть предназначен для обработки приходящей на компьютер почты, активизируясь только по мере появления писем. Другой фоновый процесс может обрабатывать запросы к web-страницам, расположенным на компьютере, и активизироваться для обслуживания полученного запроса. Фоновые процессы, связанные с электронной почтой, web-страницами, новостями, выводом на печать и т. п., называются демонами. В больших системах насчитываются десятки демонов. В UNIX для вывода списка запущенных процессов используется программа ps. В Windows 95/98/Ме достаточно нажать CTRL-ALT-DEL, а в Windows 2000 можно воспользоваться диспетчером задач, вызываемым этой же комбинацией трех клавиш.

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

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

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

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

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

В Windows же вызов всего одной функции CreateProcess интерфейса Win32 управляет и созданием процесса, и запуском в нем нужной программы. У этой функции 10 параметров: программа, которую нужно запустить, параметры командной строки этой программы, различные атрибуты защиты, биты, управляющие наследованием открытых файлов, приоритеты, спецификация окна, которое следует открыть для процесса, и указатель на структуру, в которой информация о созданном процессе возвращается вызывающей программе. Кроме CreateProcess в Win32 есть около 100 функций для управления процессами и их синхронизации.

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

1. Обычный выход (преднамеренно).
2. Выход по ошибке (преднамеренно).
3. Выход по неисправимой ошибке (непреднамеренно).
4. Уничтожение другим процессом (непреднамеренно).

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

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

cc foo.c 

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

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

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

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

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

cat chapterl chapter2 chapter3 | grep tree 

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

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

1. Работающий (в этот конкретный момент использующий процессор).
2. Готовый к работе (процесс временно приостановлен, чтобы позволить выполняться другому процессу).
3. Заблокированный (процесс не может быть запущен прежде, чем произойдет некое внешнее событие).

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

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

Как показано на рис. 2.2, между этими тремя состояниями возможны четыре перехода. Переход 1 происходит, когда процесс обнаруживает, что продолжение работы невозможно. В некоторых системах процесс должен выполнить системный запрос, например block или pause, чтобы оказаться в заблокированном состоянии. В других системах, как в UNIX, процесс автоматически блокируется, если при считывании из канала или специального файла (предположим, терминала) входные данные не были обнаружены.

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

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

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

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

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

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

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

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

Таблица 2.1. Некоторые поля типичного элемента таблицы процессов

Управление процессом		Управление памятью		Управление файлами
Регистры Счетчик команд Слово состояния программы Указатель стека Состояние процесса Приоритет Параметры планирования Идентификатор процесса Родительский процесс Группа процесса Сигналы Время начала процесса Использованное процессорное время Процессорное время дочернего процесса Время следующего аварийного сигнала		Указатель на текстовый сегмент Указатель на сегмент данных Указатель на сегмент стека		Корневой каталог Рабочий каталог Дескрипторы файла Идентификатор пользователя Идентификатор группы

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

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

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

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

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

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

Рис. 2.4. Три процесса с одиночными потоками управления (а); один процесс с тремя потоками управления (б)

Различные потоки в одном процессе не так независимы, как различные процессы. У всех потоков одно и то же адресное пространство, что означает совместное использование глобальных переменных. Поскольку любой поток имеет доступ к любому адресу ячейки памяти в адресном пространстве процесса, один поток может считывать, записывать или даже стирать информацию из стека другого потока. Защиты не существует, поскольку (1) это невозможно и (2) это ненужно. В отличие от различных процессов, которые могут быть инициированы различными пользователями и преследовать несовместимые цели, один процесс всегда запущен одним пользователем, и потоки созданы таким образом, чтобы работать совместно, не мешая друг другу. Как показано в табл. 2.3, потоки разделяют не только адресное пространство, но и открытые файлы, дочерние процессы, сигналы и т. п. Таким образом, ситуацию на рис. 2.4, а следует использовать в случае абсолютно несвязанных процессов, тогда как схема на рис. 2.4, б будет уместна, когда потоки выполняют совместно одну работу.

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

Элементы процесса		Элементы потока
Адресное пространство Глобальные переменные Открытые файлы Дочерние процессы Необработанные аварийные сигналы Сигналы и их обработчики Информация об использовании ресурсов		Счетчик команд Регистры Стек Состояние

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

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

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

Рис. 2.5. У каждого потока свой собственный стек

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

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

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

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

Но что произойдет, если поток родительского процесса будет блокирован вызовом read с клавиатуры, а у дочернего процесса столько же потоков, сколько у родительского? Будут ли теперь блокированы два потока - один из родительского процесса, другой из дочернего? И если с клавиатуры поступит строка, получат ли оба потока ее копию? Или только один - тогда какой? Эта же проблема возникает при работе с открытыми сетевыми соединениями.

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

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

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

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

И наконец, концепция потоков полезна в системах с несколькими процессорами, где возможен настоящий параллелизм. Мы еще вернемся к этой теме в главе 8.

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

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

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

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

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

Рис. 2.6. Текстовый редактор с тремя потоками

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

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

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

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

Рис. 2.7. Многопоточный web-сервер

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

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

Приблизительный набросок программы представлен на рис. 2.8. Здесь и в дальнейшем TRUE предполагается константой, равной 1. Переменные buf и page являются структурами, подходящими соответственно для хранения запроса и web-страницы.

while(TRUE) { get_next_request(&buf) handoff_work(&buf); } а

while(TRUE) { wait_for_work(&buf) look_for_page_in_cache(&buf, &page) if(page_not_in_cache(&page)) read_page_from_disk(&buf, &page) return_page(&page); } б

Рис. 2.8. Приблизительный набросок программы для рис. 2.7: поток диспетчера (а); рабочий поток (б)

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

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

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

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

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

Таблица 2.4. Три способа конструирования сервера

Модель		Характеристики
Потоки		Параллелизм, системные запросы с блокировкой
Процесс с одним потоком		Нет параллелизма, системные запросы с блокировкой
Конечный автомат		Параллелизм, системные запросы без блокировки, прерывания

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

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

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

Подобные реализации имеют в своей основе одинаковую общую схему, представленную на рис. 2.9, а. Потоки работают поверх системы поддержки исполнения программ, которая является набором процедур, управляющих потоками. С четырьмя из них мы уже знакомы: thread_create, thread_exit, thread_wait и thread_yield, но обычно их больше.

Рис. 2.9. Пакет потоков в пространстве пользователя (а); пакет потоков, управляемый ядром (б)

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

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

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

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

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

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

Оказалось, что существует альтернатива, если имеется возможность узнавать заранее, последует ли за запросом блокировка. В некоторых версиях UNIX есть системный запрос select, позволяющий узнать о наличии или отсутствии блокировки у последующего запроса read. При наличии такого системного запроса библиотечную процедуру read можно заменить новой, сначала выполняющей запрос select, а потом запрос read, если за ним не последует блокировки. Если блокировка должна произойти, то запрос не выполняется и запускается другой поток. В следующий момент, когда система поддержки исполнения программ получит управление, она может проверить еще раз, последует ли за запросом read блокировка. Такой подход требует перезаписи части библиотеки системных запросов, неэффективен и не отличается изяществом, но выбор не так уж велик. Код, который помещается вокруг системного запроса для проверки на блокировку, называется чехлом (jacket) или упаковкой (wrapper).

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

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

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

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

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

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

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

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

Рис. 2.10. Мультиплексирование потоков пользователя в потоках ядра

Многие исследователи старались совместить преимущества реализации потоков на уровне ядра (простота реализации) и реализации потоков на уровне пользователя (высокая производительность). Ниже мы рассмотрим один из таких подходов, разработанный Андерсоном [12], который называется активацией планировщика. Соответствующие разработки описаны в [104, 296].

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

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

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

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

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

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

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

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

Рис. 2.11. Создание нового потока по прибытии сообщения: до прибытия сообщения (а); после прибытия сообщения (б)

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

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

В качестве примера рассмотрим переменную еггпо в UNIX. Если процесс (или поток) выполняет неудачный системный запрос, код ошибки записывается в errno. На рис. 2.12 поток 1 выполняет системный запрос access, чтобы узнать, имеет ли он разрешение на доступ к конкретному файлу. Операционная система возвращает ответ в глобальной переменной errno. После этого управление возвращается к потоку 1. Однако прежде, чем у него появляется возможность считать значение еггпо, планировщик решает, что поток 1 уже достаточно попользовался процессором и пора переключиться на поток 2. Поток 2 выполняет запрос open, завершающийся неудачей, в результате чего значение errno изменяется и предыдущее значение теряется. После того как поток 1 вновь получит управление, он прочитает неверное значение errno, и дальнейшие его действия будут неправильными.

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

Рис. 2.12. Конфликт между потоками при использовании глобальной переменной

Рис. 2.13. У потоков могут быть собственные глобальные переменные

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

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

create_global("bufptr"); 

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

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

set_global("bufptr",&buf); 

Этот запрос сохраняет значение указателя в участке памяти, созданном запросом create_global. Запрос на чтение может выглядеть как

bufptr=read_global("bufptr"); 

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

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

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

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

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

Другие сигналы, такие как прерывание с клавиатуры, не связаны с потоками. Кто должен их перехватывать? Один назначенный поток? Все потоки? Специально созданный всплывающий поток? Что случится, если один поток изменит обработчик сигнала, не сообщив об этом остальным потокам? А что если один поток хочет перехватить определенный сигнал (например, CTRL+C с клавиатуры), а другому потоку этот сигнал нужен, чтобы прервать процесс? Подобная ситуация может возникнуть, если один или более потоков пользуются стандартными библиотечными процедурами, а остальные - процедурами, написанными пользователем. Эти потоки абсолютно несовместимы. Вообще говоря, управлять сигналами даже в нопоточной среде достаточно сложно. При переходе к многопоточному окружению обработка сигналов проще не становится.

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

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

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

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

Представьте, что каталог спулера состоит из большого числа сегментов, пронумерованных 0, 1, 2, ..., в каждом их которых может храниться имя файла. Также есть две совместно используемые переменные: out, указывающая на следующий файл для печати, и in, указывающая на следующий свободный сегмент. Эти две переменные можно хранить в одном файле (состоящем из двух слов), доступном всем процессам. Пусть в данный момент сегменты с 0 по 3 пусты (эти файлы уже напечатаны), а сегменты с 4 по 6 заняты (эти файлы ждут своей очереди на печать). Более или менее одновременно процессы Аи В решают поставить файл в очередь на печать. Описанная ситуация схематически изображена на рис. 2.14.

Рис. 2.14. Два процесса хотят одновременно получить доступ к совместно используемой памяти

В соответствии с законом Мерфи (он звучит примерно так: "Если что-то плохое может случиться, оно непременно случится") возможна следующая ситуация. Процесс А считывает значение (7) переменной in и сохраняет его в локальной переменной next_free_slot. После этого происходит прерывание по таймеру, и процессор переключается на процесс В. Процесс В, в свою очередь, считывает значение переменной in и сохраняет его (опять 7) в своей локальной переменной next_free_slot. В данный момент оба процесса считают, что следующий свободный сегмент - седьмой.

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

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

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

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

1. Два процесса не должны одновременно находиться в критических областях.
2. В программе не должно быть предположений о скорости или количестве процессоров.
3. Процесс, находящийся вне критической области, не может блокировать другие процессы.
4. Невозможна ситуация, в которой процесс вечно ждет попадания в критическую область.

В абстрактном виде требуемое поведение процессов представлено на рис. 2.15. Процесс А попадает в критическую область в момент времени T₁. Чуть позже, в момент времени Т₂, процесс В пытается попасть в критическую область, но ему это не удается, поскольку в критической области уже находится процесс A, а два процесса не должны одновременно находиться в критических областях. Поэтому процесс В временно приостанавливается, до наступления момента времени Т₃, когда процесс А выходит из критической области. В момент времени T₄ процесс В также покидает критическую область, и мы возвращаемся в исходное состояние, когда ни одного процесса в критической области не было.

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

Запрещение прерываний

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

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

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

Переменные блокировки

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

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

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

Строгое чередование

Третий метод реализации взаимного исключения иллюстрирован на рис. 2.16. Этот фрагмент программного кода, как и многие другие в этой книге, написан на С. Язык С был выбран, поскольку практически все существующие операционные системы написаны на С (или C++), а не на Java, Modula 3, Pascal и т. п. Язык С обладает всеми необходимыми свойствами для написания операционных систем: это мощный, эффективный и предсказуемый язык программирования. Язык Java, например, не является предсказуемым, поскольку у программы, написанной на нем, может в критический момент закончиться свободная память и она вызовет "сборщика мусора" в исключительно неподходящее время. В случае С это невозможно, поскольку в С процедура "сбора мусора" в принципе отсутствует. Сравнительный анализ С, C++, Java и еще четырех языков представлен в [268].

while(TRUE) { while(turn!=0) /*loop*/; critical_region(); turn=1; noncritical_region(); } a

while(TRUE) { while(turn!=0) /*loop*/; critical_region(); turn=0; noncritical_region (); ) б

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

На рис. 2.16 целая переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Вначале процесс 0 проверяет значение turn, считывает 0 и входит в критическую область. Процесс 1 также проверяет значение turn, считывает 0 и после этого входит в цикл, непрерывно проверяя, когда же значение turn будет равно 1. Постоянная проверка значения переменной в ожидании некоторого значения называется активным ожиданием. Подобного способа следует избегать, поскольку он является бесцельной тратой времени процессора. Активное ожидание используется только в случае, когда есть уверенность в небольшом времени ожидания. Блокировка, использующая активное ожидание, называется спин-блокировкой.

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

Неожиданно процесс 0 завершает работу вне критической области и возвращается к началу цикла. Но войти в критическую область он не может, поскольку значение turn равно 1 и процесс 1 находится вне критической области. Процесс 0 зависнет в своем цикле while, ожидая, пока процесс 1 изменит значение turn на 0.

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

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

Алгоритм Петерсона

Датский математик Деккер (Т. Dekker) был первым, кто разработал программное решение проблемы взаимного исключения, не требующее строгого чередования. Подробное изложение алгоритма можно найти в [46].

В 1981 году Петерсон (G. L. Peterson) разработал существенно более простой алгоритм взаимного исключения. С этого момента алгоритм Деккера стал считаться устаревшим. Алгоритм Петерсона, представленный в листинге 2.1, состоит из двух процедур, написанных на ANSI С, что предполагает необходимость прототипов для всех определяемых и используемых функций. В целях экономии места мы не будем приводить прототипы для этого и последующих примеров.

Листинг 2.1. Решение Петерсона для взаимного исключения 

#define FALSE 0 
#define TRUE 1 
#define N 2                        /* Количество процессов */ 
int turn;                          /* Чья сейчас очередь? */ 
int interested[N];                 /* Все переменные изначально равны О (FALSE) */ 
void enter_region(int process)     /* Процесс 0 или 1 */ 
{ 
      int other;                   /* Номер второго процесса */ 
      other = 1 - process;         /* Противоположный процесс */ 
      interested[process] = TRUE;  /* Индикатор интереса*/ 
      turn = process;              /* Установка флага*/ 
      while (turn == process && interested[other] = TRUE)  /* Пустой оператор */; 
} 
void leave_region(int process)     /* process: процесс, покидающий критическую область */ 
{ 
      interested[process] = FALSE; /* Индикатор выхода из критической области */ 
} 

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

Рассмотрим работу алгоритма более подробно. Исходно оба процесса находятся вне критических областей. Процесс 0 вызывает enter_region, задает элементы массива и устанавливает переменную turn равной 0. Поскольку процесс 1 не заинтересован в попадании в критическую область, процедура возвращается. Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested[0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region, чтобы покинуть критическую область.

Представьте, что оба процесса вызвали enter_region практически одновременно. Оба сохранят свои номера в turn. Сохранится номер того процесса, который был вторым, а предыдущий номер будет утерян. Предположим, что вторым был процесс 1, так что значение turn равно 1. Когда оба процесса дойдут до оператора while, процесс 0 войдет в критическую область, а процесс 1 останется в цикле и будет ждать, пока процесс 0 выйдет из критической области.

Команда TSL

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

TSL RX,LOCK 

(Test and Set Lock - проверить и заблокировать), которая действует следующим образом. В регистр RX считывается содержимое слова памяти lock, а в ячейке памяти lock сохраняется некоторое ненулевое значение. Гарантируется, что операция считывания слова и сохранения неделима - другой процесс не может обратиться к слову в памяти, пока команда не выполнена. Процессор, выполняющий команду TSL, блокирует шину памяти, чтобы остальные процессоры не могли обратиться к памяти.

Воспользуемся командой TSL. Пусть совместно используемая переменная lock управляет доступом к разделенной памяти. Если значение переменной lock равно 0, любой процесс может изменить его на 1 и обратиться к разделенной памяти, и затем изменить его обратно на 0, пользуясь обычной командой move.

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

Листинг 2.2. Вход и выход из критической области с помощью команды TSL 

enter_region; 
       TSL REGISTER,LOCK   | значение lock копируется в регистр, значение переменной  
                             устанавливается равным 1 
       GMP REGISTER,#0     | Старое значение lock сравнивается с нулем 
       JNE enter_region    | Если оно ненулевое, значит, блокировка уже была установлена. 
                             поэтому цикл завершается 
       RET                 | Возврат к вызывающей программе, процесс вошел в критическую 
                             область 
1eave_region: 
       MOVE LOCK,#0        | Сохранение 0 в переменной lock 
       RET 

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

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

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

Проблема производителя и потребителя

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

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

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

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

Листинг 2.3. Проблема производителя и потребителя с неустранимым состоянием соревнования 

#define N 100                   /* Максимальное количество элементов в буфере */ 
int. count = 0;                 /* Текущее количество элементов в буфере */ 
void producer(void) 
{ 
   int item: 
   while (TRUE) {               /* Повторять вечно */ 
      item = produce_item();    /* Сформировать следующий элемент */ 
      if (count == N) sleep();  /* Если буфер полон, уйти в состояние ожидания */ 
      insert_item(item);        /* Поместить элемент в буфер */ 
      count = count + 1;        /* Увеличить количество элементов в буфере */ 
      if (count == 1) wakeup(consumer); /* Был ли буфер пуст? */ 
   } 
} 
void consumer(void) 
{ 
   int item; 
   while (TRUE) {                /* Повторять вечно */ 
      if (count == 0) sleep();   /* Если буфер пуст, уйти в состояние ожидания */ 
      item = remove_item();      /* Забрать элемент из буфера */ 
      count = count - 1;         /* Уменьшить счетчик элементов в буфере */ 
      if (count == N - 1) wakeup(producer); /* Был ли буфер полон? */ 
      consume_item(item);        /* Отправить элемент на печать */ 

   }
}

Для описания на языке С системных вызовов sleep и wakeup мы представили их в виде вызовов библиотечных процедур. В стандартной библиотеке С их нет, но они будут доступны в любой системе, в которой присутствуют такие системные вызовы. Процедуры insert_item и remove_item помещают элементы в буфер и извлекают их оттуда.

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

Но потребитель не был в состоянии ожидания, так что сигнал активизации пропал впустую. Когда управление перейдет к потребителю, он вернется к считанному когда-то значению count, обнаружит, что оно равно 0, и уйдет в состояние ожидания. Рано или поздно производитель наполнит буфер и также уйдет в состояние ожидания. Оба процесса так и останутся в этом состоянии.

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

В 1965 году Дейкстра (Е. W. Dijkstra) предложил использовать целую переменную для подсчета сигналов запуска, сохраненных на будущее [96]. Им был предложен новый тип переменных, так называемые семафоры, значение которых может быть нулем (в случае отсутствия сохраненных сигналов активизации) или некоторым положительным числом, соответствующим количеству отложенных активизирующих сигналов.

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

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

В оригинале Дейкстра использовал вместо down и up обозначения Р и V соответственно. Мы не будем в дальнейшем использовать оригинальные обозначения, поскольку тем, кто не знает датского языка, эти обозначения ничего не говорят (да и тем, кто знает язык, говорят немного). Впервые обозначения down и up появились в языке Algol 68.

Решение проблемы производителя и потребителя с помощью семафоров

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

Листинг 2.4. Проблема производителя и потребителя с семафорами 

#define N 100                 /* количество сегментов в буфере */ 
typedef int semaphore;        /* семафоры - особый вид целочисленных переменных */ 
semaphore mutex = 1;          /* контроль доступа в критическую область */ 
semaphore empty = N;          /* число пустых сегментов буфера */ 
semaphore full = 0;           /* число полных сегментов буфера */ 
void producer(void) 
{ 
    int item; 
    while (TRUE) {             /* TRUE - константа, равная 1*/ 
        item = produce_item(); /* создать данные, помещаемые в буфер */ 
        down(&empty);          /* уменьшить счетчик пустых сегментов буфера */ 
        down(&mutex);          /* вход в критическую область */ 
        insert_item(item);     /* поместить в буфер новый элемент */ 
        up(&mutex);            /* выход из критической области */ 
        up(&full);             /* увеличить счетчик полных сегментов буфера */ 
    }
}
void consumer(void) 
{
    int item; 
    while (TRUE) {             /* бесконечный цикл */ 
        down(&full);           /* уменьшить числа полных сегментов буфера */ 
        down(&mutex);          /* вход в критическую область */ 
        item = remove_item();  /* удалить элемент из буфера */ 
        up(&mutex);            /* выход из критической области */ 
        up(&empty);            /* увеличить счетчик пустых сегментов буфера */ 
        consume_item(item);    /* обработка элемента */ 
    }
}

В представленном решении используются три семафора: один для подсчета заполненных сегментов буфера (full), другой для подсчета пустых сегментов (empty), а третий предназначен для исключения одновременного доступа к буферу производителя и потребителя (mutex). Значение счетчика full исходно равно нулю, счетчик empty равен числу сегментов в буфере, a mutex равен 1. Семафоры, исходное значение которых равно 1, используемые для исключения одновременного нахождения в критической области двух процессов, называются двоичными семафорами. Взаимное исключение обеспечивается, если каждый процесс выполняет операцию down перед входом в критическую область и up после выхода из нее.

Теперь, когда у нас есть примитивы межпроцессного взаимодействия, вернемся к последовательности прерываний, показанной в табл. 2.2. В системах, использующих семафоры, естественным способом скрыть прерывание будет связать с каждым устройством ввода-вывода семафор, исходно равный нулю. Сразу после запуска устройства ввода-вывода управляющий процесс выполняет операцию down на соответствующем семафоре, тем самым входя в состояние блокировки. В случае прерывания обработчик прерывания выполняет up на соответствующем семафоре, переводя процесс в состояние готовности. В такой модели пятый шаг в табл. 2.2 заключается в выполнении up на семафоре устройства, чтобы следующим шагом планировщик смог запустить программу, управляющую устройством. Разумеется, если в этот момент несколько процессов находятся в состоянии готовности, планировщик может выбрать другой, более значимый процесс. Мы рассмотрим некоторые алгоритмы планирования позже в этой главе.

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

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

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

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

Мьютексы легко реализовать в пользовательском пространстве, если доступна команда TSL. Код программы для процедур mutex_lock и mutex_unlock в случае потоков на уровне пользователя представлен в листинге 2.5.

Листинг 2.5. Реализация mutex_lock и mutex_unlock 

mutex_lock: 
     TSL REGISTER,MUTEX | Старое значение мьютекса копируется в регистр; 
                        | устанавливается новое значение 1 
     CMP REGISTER,#0    | Сравнение старого значения с нулем 
     JZE ok             | Если старое значение было нулем, мьютекс не был 
                        | блокирован. Возврат 
     CALL thread_yield  | Мьютекс занят, управление передается другому потоку
     JMP mutex_lock     | Повторить попытку позже
ok:  RET                | Возврат, вход в критическую область
mutex_unlock: 
     MOVE MUTEX,#0      | Устанавливается значение мьютекса 0 
     RET | Возврат 

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

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

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

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

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

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

Межпроцессное взаимодействие с применением семафоров выглядит довольно просто, не правда ли? Эта простота кажущаяся. Взгляните внимательнее на порядок выполнения процедур down перед помещением или удалением элементов из буфера в листинге 2.4. Представьте себе, что две процедуры down в программе производителя поменялись местами, так что значение mutex было уменьшено раньше, чем empty. Если буфер был заполнен, производитель блокируется, установив mutex на 0. Соответственно, в следующий раз, когда потребитель обратится к буферу, он выполнит down с переменной mutex, равной 0, и тоже заблокируется. Оба процесса заблокированы навсегда. Эта неприятная ситуация называется взаимоблокировкой, и мы вернемся к ней в главе 3.

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

Чтобы упростить написание программ, в 1974 году Хоар (Hoare) [155] и Бринч Хансен (Brinch Hansen) [43] предложили примитив синхронизации более высокого уровня, называемый монитором. Их предложения несколько отличались друг от друга, как мы увидим дальше. Монитор - набор процедур, переменных и других структур данных, объединенных в особый модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора. В листинге 2.6 представлен монитор, написанный на воображаемом языке Pidgin Pascal.

Листинг 2.6. Монитор 

monitor example 
       integer i; 
       condition с; 

       procedure producer(); 
       .
       .
       .
       end;

       procedure consumer();
       .
       .
       .
       end;
       end monitor; 

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

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

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

Решение заключается во введении переменных состояния и двух операций, wait и signal. Когда процедура монитора обнаруживает, что она не в состоянии продолжать работу (например, производитель выясняет, что буфер заполнен), она выполняет операцию wait на какой-либо переменной состояния, скажем, full. Это приводит к блокировке вызывающего процесса и позволяет другому процессу войти в монитор.

Другой процесс, в нашем примере потребитель может активизировать ожидающего напарника, например, выполнив операцию signal на той