Создание процессов и потоков

Создание процессов и потоков

Дескриптор процесса

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

Состояние потока

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

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

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

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

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

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

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

1. Понятие «процесс» и «поток»

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

В чем же состоят принципиальные отличия в понятиях «процесс» и «поток»?

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

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

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

 

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

 

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

Элементы процесса                                  Элементы потока

Адресное пространство                                 Счетчик команд

Глобальные переменные                                        Регистры

Открытые файлы                                           Стек

Дочерние процессы                                                Состояние

Необработанные аварийные сигналы

Сигналы и их обработчики

Информация об использовании ресурсов

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

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

В простейшем случае процесс состоит из одного потока.

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

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

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

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

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

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

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

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

Создание процессов и потоков

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

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

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

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

Пример: создание процессов в ОС UNIX System V Release 4.

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

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

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

Дескриптор процесса

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

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

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

· тип процесса, который определяет для супервизора некоторые правила предоставления ресурсов;

· приоритет процесса, в соответствии с которым супервизор предоставляет ресурсы;

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

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

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

· место (или его адрес) для организации общения с другими процессами;

· параметры времени запуска (момент времени, когда процесс должен активизироваться, и периодичность этой процедуры);

· в случае отсутствия системы управления файлами адрес задачи на диске в ее исходном состоянии и адрес на диске, куда она выгружается из оперативной памяти, если её вытесняет другая задача.

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

В некоторых операционных системах количество описателей определяется жестко и заранее (на этапе генерации варианта операционной системы или в конфигурационном файле, который используется при загрузке ОС), в других по мере необходимости система может выделять участки памяти под новые описатели. В ныне широко распространенных системах Windows NT/2000/XP количество описателей нигде в явном виде не задается. Это переменная величина, и она определяется самой операционной системой. Однако посмотреть на текущее количество таких описателей можно. Если, работая в Windows NT/2000/XP, нажать одновременно комбинацию клавиш Ctrl+Alt+Del, появится окно Диспетчера задач. На вкладке Быстродействие этой программы мы увидим поле с названием «Всего дескрипторов» и соответствующее число.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим те, которые признаны наиболее эффективными и до сих пор имеют применение.

 

Рис. 2. Дисциплины диспетчеризации

 

В концепции приоритетов имеем следующие варианты:

q приоритет, присвоенный задаче, является величиной постоянной;

q приоритет изменяется в течение времени решения задачи (динамический приоритет).

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

Ü Самой простой в реализации является дисциплина FCFS (First Come First Served – первым пришел, первым обслужен), согласно которой задачи обслуживаются «в порядке очереди», то есть в порядке появления. Те задачи, которые были заблокированы в процессе работы (попали в какое-либо из состояний ожидания, например из-за операции ввода-вывода), после перехода в состояние готовности вновь ставятся в эту очередь готовности. К достоинству этой дисциплины прежде всего можно отнести простоту реализации и малые расходы системных ресурсов на формирование очереди задач. Однако эта дисциплина приводит к тому, что пр увеличении загрузки вычислительной системы растет и среднее время ожидания обслуживания, причем короткие задания (требующие небольших затрат машинного времени) вынуждены ожидать столько же, сколько трудоёмкие задания.

Избежать этого недостатка позволяют дисциплины SJN и SRT.

Ü Дисциплина обслуживания SJN (Shortest Job Next – следующим выполняется самое короткое задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. Задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операции ввода-вывода), вновь попадали в конец очереди готовых к выполнению наравне с вновь поступающими. Это приводило к тому, что задания, которым требовалось очень много времени для своего завершения, вынуждены были ожидать процессор наравне с длительными работами, что не всегда хорошо.

Ü Дисциплина обслуживания SRT (Shortest Remaining Time) – следующим будет выполняться задание, которому осталось меньше всего выполняться на процессоре.

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

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

 

 

 

Рис. 3. Карусельная дисциплина диспетчеризации

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

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

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

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

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

Ü Итак, диспетчеризация без перераспределения процессорного времени, то есть не вытесняющая (non-preemptive multitasking), или кооперативная многозадачность (cooperative multitasking), - это такой способ диспетчеризации задач, при котором активная задача выполняется до тех пор, пока она сама, что называется «по собственной инициативе», не отдаст управление диспетчеру задач для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс или поток дисциплины обслуживания FCFS, SJN, SRT относятся к не вытесняющим.

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

Дисциплина RR и многие другие, построенные на её основе, относятся к вытесняющим.

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

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

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

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

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

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

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

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

1) состояние аппаратуры компьютера в момент прерывания потока:

– значение счетчика команд;

– содержимое регистров общего назначения;

– режим работы процессора;

– флаги;

– маски прерываний и другие параметры.

2) параметры операционной среды:

– ссылки на открытые файлы;

– данные о незавершенных операциях ввода–вывода;

– коды ошибок выполняемых данным потоком системных вызовов и т.д.

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

1) сохранение контекста текущего потока, который следует сменить;

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

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

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

§ по возможности заканчивать вычисления (вычислительные процессы) в том же самом порядке, в котором они были начаты;

§ отдавать предпочтение более коротким вычислительным задачам;

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

 

Состояние потока

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

1) выполнение – активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

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

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

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

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

 

Порядок выполнения: A, B, E, D, C

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

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

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

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

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

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

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

Почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT/2000 и др.), реализованы вытесняющие алгоритмы планирования потоков (процессов).