Понятия процесса и потока

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

В ряде ОС определены два типа работы. Более крупная единица – процесс, которая требует для своей реализации несколько более мелких работ, и эта более мелкая единица называется потоком.

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

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

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

Для этих целей в ряде современных ОС используется механизм многопоточной обработки. При этом вводится новая единица работы – поток выполнения, а понятие «процесс» в некоторой степени меняет смысл.

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

При управлении процессами ОС использует два основных типа информационных структур:

· дескриптор процесса;

· контекст процесса.

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

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

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

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

Контекст, так же как и дескриптор, доступен только программам ядра, т.е. находится в виртуальном адресном пространстве ОС.

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

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

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

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

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

Планирование потоков включает в себя решение двух задач:

· определение момента времени для смены текущего активного потока;

· выбор для выполнения потока из очереди готовых потоков.

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

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

Планирование может быть динамическим или статическим.

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

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

Планировщик называется статическим, если он принимает решения о планировании не во время работы системы, а заранее.

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

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

Контекст отражает:

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

· параметры операционной среды (ссылки на открытые файлы, данные о незавершенных операциях ввода-вывода, коды ошибок, выполняемых данным потоком системных вызовов и т.д.).

Диспетчеризация сводится к следующему:

· сохранение контекста текущего потока, который требуется сменить;

· загрузка контекста нового потока, выбранного в результате планирования;

· запуск нового потока на выполнение.

В мультипрограммной системе поток может находиться в одном из трех состояний:

· выполнение – выполняется процессором:

· ожидание – ждет осуществления некоторого события;

· готовность – имеет все необходимые для выполнения ресурсы, готов выполняться, но процессор занят выполнением другого потока.

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

 

Граф состояний потока в многозадачной среде можно представить как на рисунке:

 

 

«Вытеснение потока» означает прекращение его выполнения процессором, например, вследствие исчерпания отведенного для выполнения кванта времени.

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

 

Вытесняющие и невытесняющие алгоритмы планирования.

Все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие.

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

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

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

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

Почти все современные ОС, такие как UNIX, Windows NT/2000, OS-2, Windows 95/98 реализуют вытесняющие алгоритмы планирования потоков.

 

Алгоритмы планирования, основанные на квантовании.

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

Смена активного потока происходит, если:

· поток завершился и покинул систему;

· произошла ошибка;

· поток перешел в состояние ожидания;

· исчерпан квант процессорного времени.

 

Поток, исчерпавший свой квант, переводится в состояние готовности и ожидает в очереди. Граф состояний потока представлен на рисунке:

 

 

Кванты для потоков могут быть одинаковыми или различными.

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

 

Соответствующий граф состояний потока можно представить как:

 

Алгоритмы планирования, основанные на приоритетах.

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

В ОС Windows NT определено 32 уровня приоритетов и два класса потоков – потоки реального времени и потоки с переменными приоритетами.

Диапазон от 1 до 15 отведен для потоков с переменными приоритетами, а от 16 до 32 – для более критичных ко времени потоков реального времени.

Смешанные алгоритмы планирования.

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

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

Планирование в системах реального времени.

В системах реального времени главным критерием является обеспечение временных характеристик вычислительного процесса.

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

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

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

Моменты перепланировки.

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

· прерывание от таймера, сигнализирующее, что время, отведенное активной задаче, закончилось;

· активная задача выполнила системный вызов, связанный с запросом на ввод-вывод или на доступ к ресурсу, который в настоящий момент занят (например, файл данных);

· активная задача выполнила системный вызов, связанный с освобождением ресурса. Планировщик проверяет, не ожидает ли этот ресурс какая-либо задача. Если да, то задача переводится из состояния ожидания в состояние готовности и проверяется, имеет ли она наивысший приоритет. Если нет – возможна перепланировка;

· внешнее аппаратное прерывание. Оно сигнализирует о переводе соответствующей текущей задачи в очередь готовности и выполняется планировщик;

· внутреннее прерывание сообщает об ошибке в текущей задаче. Планировщик снимает задачу и выполняет перепланирование.

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