Что значит количество потоков в процессоре. Процессы и потоки

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

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

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

Как и в системе UNIX, процессы представляют собой контейнеры для ресур­сов. У каждого процесса есть 4-гигабайтное адресное пространство, в котором пользователь занимает нижние 2 Гбайт (в версиях Windows 2000 Advanced Server и Datacenter Server этот размер может быть по желанию увеличен до 3 Гбайт), а операционная система занимает остальную его часть. Таким образом, операци­онная система присутствует в адресном пространстве каждого процесса, хотя она и защищена от изменений с помощью аппаратного блока управления памятью MMU. У процесса есть идентификатор процесса, один или несколько потоков, список дескрипторов (управляемых в режиме ядра) и маркер доступа, хранящий информацию защиты. Процессы создаются с помощью вызова Win32, который принимает на входе имя исполняемого файла, определяющего начальное содер­жимое адресного пространства, и создает первый поток.

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

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

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

Помимо нормальных потоков, работающих в процессах пользователя, в опера­ционной системе Windows 2000 есть множество процессов-демонов, не связанных ни с каким пользовательским процессом (они ассоциированы со специальной си­стемой или простаивающими процессами). Некоторые демоны выполняют адми­нистративные задачи, как, например, запись «грязных» (модифицированных) страниц на диск, тогда как другие формируют пул, и ими могут пользоваться компоненты исполняющей системы или драйверы, которым нужно выполнить какие-либо асинхронные за­дачи в фоновом режиме. Переключение потоков в операционной системе Windows 2000 занимает до­вольно много времени, так как для этого необходимо переключение в режим ядра, а затем возврат в режим пользователя. Для предоставления сильно облегченного псевдопараллелизма в Windows 2000 используются волокна, подобные потокам, но планируемые в пространстве пользователя создавшей их программой (или ее системой поддержки исполнения). У каждого потока может быть несколько воло­кон, так же как у процесса может быть несколько потоков, с той разницей, что когда волокно логически блокируется, оно помещается в очередь блокированных волокон, после чего для работы выбирается другое волокно в контексте того же потока. Операционная система не знает о смене волокон, так как все тот же поток продолжает работу. Так как операционная система ничего не знает о волокнах, то с ними, в отличие от заданий, процессов и потоков, не связаны объекты испол­няющей системы. Для управления волокнами нет и настоящих системных вызо­вов. Однако для этого есть вызовы Win32 API. Они относятся к тем вызовам Win32 API, которые не обращаются к системным вызовам.

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

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

  • Tutorial

В этой статье я попытаюсь описать терминологию, используемую для описания систем, способных исполнять несколько программ параллельно, то есть многоядерных, многопроцессорных, многопоточных. Разные виды параллелизма в ЦПУ IA-32 появлялись в разное время и в несколько непоследовательном порядке. Во всём этом довольно легко запутаться, особенно учитывая, что операционные системы заботливо прячут детали от не слишком искушённых прикладных программ.

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

Предупреждение о знаках ®, ™, в статье

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

Процессор

Конечно же, самый древний, чаще всего используемый и неоднозначный термин - это «процессор».

В современном мире процессор - это то (package), что мы покупаем в красивой Retail коробке или не очень красивом OEM-пакетике. Неделимая сущность, вставляемая в разъём (socket) на материнской плате. Даже если никакого разъёма нет и снять его нельзя, то есть если он намертво припаян, это один чип.

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

Поддержка нескольких центральных процессоров в одной системе требует многочисленных изменений в её дизайне. Как минимум, необходимо обеспечить их физическое подключение (предусмотреть несколько сокетов на материнской плате), решить вопросы идентификации процессоров (см. далее в этой статье, а также мою предыдущую заметку), согласования доступов к памяти и доставки прерываний (контроллер прерываний должен уметь маршрутизировать прерывания на несколько процессоров) и, конечно же, поддержки со стороны операционной системы. Я, к сожалению, не смог найти документального упоминания момента создания первой многопроцессорной системы на процессорах Intel, однако Википедия утверждает , что Sequent Computer Systems поставляла их уже в 1987 году, используя процессоры Intel 80386. Широко распространённой поддержка же нескольких чипов в одной системе становится доступной, начиная с Intel® Pentium.

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


К взлёту готов! Intel® Desktop Board D5400XS

Ядро

Исторически многоядерность в Intel IA-32 появилась позже Intel® HyperThreading, однако в логической иерархии она идёт следующей.

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

Первые многоядерные процессоры IA-32 от Intel были представлены в 2005 году. С тех пор среднее число ядер в серверных, десктопных, а ныне и мобильных платформах неуклонно растёт.

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


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

Гиперпоток

До примерно 2002 года единственный способ получить систему IA-32, способную параллельно исполнять две или более программы, состоял в использовании именно многопроцессорных систем. В Intel® Pentium® 4, а также линейке Xeon с кодовым именем Foster (Netburst) была представлена новая технология - гипертреды или гиперпотоки, - Intel® HyperThreading (далее HT).

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

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

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

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

Другая ситуация наблюдается на типичных задачах, выполняемых на видеоускорителях. Поэтому для этих архитектур характерно использование техники SMT с бóльшим числом потоков. Так как сопроцессоры Intel® Xeon Phi (представленные в 2010 году) идеологически и генеалогически довольно близки к видеокартам, на них может быть четыре гиперпотока на каждом ядре - уникальная для IA-32 конфигурация.

Логический процессор

Из трёх описанных «уровней» параллелизма (процессоры, ядра, гиперпотоки) в конкретной системе могут отсутствовать некоторые или даже все. На это влияют настройки BIOS (многоядерность и многопоточность отключаются независимо), особенности микроархитектуры (например, HT отсутствовал в Intel® Core™ Duo, но был возвращён с выпуском Nehalem) и события при работе системы (многопроцессорные сервера могут выключать отказавшие процессоры в случае обнаружения неисправностей и продолжать «лететь» на оставшихся). Каким образом этот многоуровневый зоопарк параллелизма виден операционной системе и, в конечном счёте, прикладным приложениям?

Далее для удобства обозначим количества процессоров, ядер и потоков в некоторой системе тройкой (x , y , z ), где x - это число процессоров, y - число ядер в каждом процессоре, а z - число гиперпотоков в каждом ядре. Далее я буду называть эту тройку топологией - устоявшийся термин, мало что имеющий с разделом математики. Произведение p = xyz определяет число сущностей, именуемых логическими процессорами системы. Оно определяет полное число независимых контекстов прикладных процессов в системе с общей памятью, исполняющихся параллельно, которые операционная система вынуждена учитывать. Я говорю «вынуждена», потому что она не может управлять порядком исполнения двух процессов, находящихся на различных логических процессорах. Это относится в том числе к гиперпотокам: хотя они и работают «последовательно» на одном ядре, конкретный порядок диктуется аппаратурой и недоступен для наблюдения или управления программам.

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


Windows Task Manager показывает 8 логических процессоров; но сколько это в процессорах, ядрах и гиперпотоках?


Linux top показывает 4 логических процессора.

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

Программное определение топологии

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

Информация о топологии системы в целом, а также положении каждого логического процессора в IA-32 доступна с помощью инструкции CPUID. С момента появления первых многопроцессорных систем схема идентификации логических процессоров несколько раз расширялась. К настоящему моменту её части содержатся в листах 1, 4 и 11 CPUID. Какой из листов следует смотреть, можно определить из следующей блок-схемы, взятой из статьи :

Я не буду здесь утомлять всеми подробностями отдельных частей этого алгоритма. Если возникнет интерес, то этому можно посвятить следующую часть этой статьи. Отошлю интересующегося читателя к , в которой этот вопрос разбирается максимально подробно. Здесь же я сначала кратко опишу, что такое APIC и как он связан с топологией. Затем рассмотрим работу с листом 0xB (одиннадцать в десятичном счислении), который на настоящий момент является последним словом в «апикостроении».

APIC ID
Local APIC (advanced programmable interrupt controller) - это устройство (ныне входящее в состав процессора), отвечающее за работу с прерываниями, приходящими к конкретному логическому процессору. Свой собственный APIC есть у каждого логического процессора. И каждый из них в системе должен иметь уникальное значение APIC ID. Это число используется контроллерами прерываний для адресации при доставке сообщений, а всеми остальными (например, операционной системой) - для идентификации логических процессоров. Спецификация на этот контроллер прерываний эволюционировала, пройдя от микросхемы Intel 8259 PIC через Dual PIC, APIC и xAPIC к x2APIC .

В настоящий момент ширина числа, хранящегося в APIC ID, достигла полных 32 бит, хотя в прошлом оно было ограничено 16, а ещё раньше - только 8 битами. Нынче остатки старых дней раскиданы по всему CPUID, однако в CPUID.0xB.EDX возвращаются все 32 бита APIC ID. На каждом логическом процессоре, независимо исполняющем инструкцию CPUID, возвращаться будет своё значение.

Выяснение родственных связей
Значение APIC ID само по себе ничего не говорит о топологии. Чтобы узнать, какие два логических процессора находятся внутри одного физического (т.е. являются «братьями» гипертредами), какие два - внутри одного процессора, а какие оказались и вовсе в разных процессорах, надо сравнить их значения APIC ID. В зависимости от степени родства некоторые их биты будут совпадать. Эта информация содержится в подлистьях CPUID.0xB, которые кодируются с помощью операнда в ECX. Каждый из них описывает положение битового поля одного из уровней топологии в EAX (точнее, число бит, которые нужно сдвинуть в APIC ID вправо, чтобы убрать нижние уровни топологии), а также тип этого уровня - гиперпоток, ядро или процессор, - в ECX.

У логических процессоров, находящихся внутри одного ядра, будут совпадать все биты APIC ID, кроме принадлежащих полю SMT. Для логических процессоров, находящихся в одном процессоре, - все биты, кроме полей Core и SMT. Поскольку число подлистов у CPUID.0xB может расти, данная схема позволит поддержать описание топологий и с бóльшим числом уровней, если в будущем возникнет необходимость. Более того, можно будет ввести промежуточные уровни между уже существующими.

Важное следствие из организации данной схемы заключается в том, что в наборе всех APIC ID всех логических процессоров системы могут быть «дыры», т.е. они не будут идти последовательно. Например, во многоядерном процессоре с выключенным HT все APIC ID могут оказаться чётными, так как младший бит, отвечающий за кодирование номера гиперпотока, будет всегда нулевым.

Отмечу, что CPUID.0xB - не единственный источник информации о логических процессорах, доступный операционной системе. Список всех процессоров, доступный ей, вместе с их значениями APIC ID, кодируется в таблице MADT ACPI .

Операционные системы и топология

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

В Linux информация о топологии содержится в псевдофайле /proc/cpuinfo , а также выводе команды dmidecode . В примере ниже я фильтрую содержимое cpuinfo на некоторой четырёхядерной системе без HT, оставляя только записи, относящиеся к топологии:

Скрытый текст

ggg@shadowbox:~$ cat /proc/cpuinfo |grep "processor\|physical\ id\|siblings\|core\|cores\|apicid" processor: 0 physical id: 0 siblings: 4 core id: 0 cpu cores: 2 apicid: 0 initial apicid: 0 processor: 1 physical id: 0 siblings: 4 core id: 0 cpu cores: 2 apicid: 1 initial apicid: 1 processor: 2 physical id: 0 siblings: 4 core id: 1 cpu cores: 2 apicid: 2 initial apicid: 2 processor: 3 physical id: 0 siblings: 4 core id: 1 cpu cores: 2 apicid: 3 initial apicid: 3

В FreeBSD топология сообщается через механизм sysctl в переменной kern.sched.topology_spec в виде XML:

Скрытый текст

user@host:~$ sysctl kern.sched.topology_spec kern.sched.topology_spec: 0, 1, 2, 3, 4, 5, 6, 7 0, 1, 2, 3, 4, 5, 6, 7 0, 1 THREAD groupSMT group 2, 3 THREAD groupSMT group 4, 5 THREAD groupSMT group 6, 7 THREAD groupSMT group

В MS Windows 8 сведения о топологии можно увидеть в диспетчере задач Task Manager.

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

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

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

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

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

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

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

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

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

Существует три основных состояния процесса: "готов", "выполняется", "блокирован".

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примерами описателей процесса являются блок управления задачей (Task Control Block – ТСВ) в OS/360, управляющий блок процесса (Process Control Block – РСВ) в OS/2, дескриптор процесса в UNIX, объект-процесс (object-process) в Windows NT.

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

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

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

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

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

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

■ определение момента времени для смены выполняемого процесса;

■ выбор процесса на выполнение из очереди готовых процессов;

■ переключение контекстов "старого" и "нового" процессов.

Первые две задачи решаются программными средствами, а последняя – в значительной степени аппаратно.

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

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

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

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

■ процесс перешел в состояние "ожидание";

■ исчерпан квант процессорного времени, отведенный данному процессу.

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

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

В алгоритмах, основанных на приоритетах, используется понятие "приоритет" процесса.

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

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

Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты.

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

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

Существует два основных типа процедур планирования процессов: вытесняющие (preemptive) и невытесняющие (non-preemptive).

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

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

Понятия "preemptive" и "nοn-preemptive" иногда отождествляют с понятиями приоритетных и бесприоритетных дисциплин, что совершенно неверно, а также с понятиями абсолютных и относительных приоритетов, что неверно отчасти. Вытесняющая и невытесняющая многозадачность – более широкие понятия, чем типы приоритетности. Приоритеты задач могут как использоваться, так и не использоваться и при вытесняющих, и при невытесняющих способах планирования. Так, в случае использования приоритетов дисциплина относительных приоритетов может быть отнесена к классу систем с невытесняющей многозадачностью, а дисциплина абсолютных приоритетов – к классу систем с вытесняющей многозадачностью. Бесприоритетная дисциплина планирования, основанная на выделении равных квантов времени для всех задач, относится к вытесняющим алгоритмам.

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

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

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

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

Однако почти во всех современных ОС, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая многозадачность. В последнее время дошла очередь и до ОС класса настольных систем. Возможно, в связи с этим вытесняющую многозадачность часто называют истинной.

4.1 Процессы

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

Процесс (задача) - программа, находящаяся в режиме выполнения.

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

Адресное пространство содержит:

    саму программу

    данные к программе

    стек программы

С каждым процессом связывается набор регистров, например:

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

    указатель стека

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

Некоторые поля таблицы:

Управление процессом

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

Управление файлами

Регистры

Счетчик команд

Указатель стека

Состояние процесса

Приоритет

Параметры планирования

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

Родительский процесс

Группа процесса

Время начала процесса

Использованное процессорное время

Указатель на текстовый сегмент

Указатель на сегмент данных

Указатель на сегмент стека

Корневой каталог

Рабочий каталог

Дескрипторы файла

Идентификатор пользователя

Идентификатор группы

4.1.2 Модель процесса

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

Рассмотрим схему с четырьмя работающими программами.

В каждый момент времени активен только один процесс

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

4.1.3 Создание процесса

Три основных события, приводящие к созданию процессов (вызов fork или CreateProcess ):

    Работающий процесс подает системный вызов на создание процесса

    Запрос пользователя на создание процесса

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

В UNIX каждому процессу присваивается идентификатор процесса (PID - Process IDentifier)

4.1.4 Завершение процесса

Четыре события, приводящие к остановке процесса (вызов exit или ExitProcess ):

    Плановое завершение (окончание выполнения)

    Плановый выход по известной ошибке (например, отсутствие файла)

    Выход по неисправимой ошибке (ошибка в программе)

    Уничтожение другим процессом

Таким образом, приостановленный процесс состоит из собственного адресного пространства, обычно называемого образом памяти (core image ), и компонентов таблицы процессов (в числе компонентов и его регистры).

4.1.5 Иерархия процессов

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

В таком случае в UNIX существует и прародитель всех процессов - процесс init .

Дерево процессов для систем UNIX

4.1.6 Состояние процессов

Три состояния процесса:

    Выполнение (занимает процессор)

    Готовность (процесс временно приостановлен, чтобы позволить выполняться другому процессу)

    Ожидание (процесс не может быть запущен по своим внутренним причинам, например, ожидая операции ввода/вывода)

Возможные переходы между состояниями.

1. Процесс блокируется, ожидая входных данных

2. Планировщик выбирает другой процесс

3. Планировщик выбирает этот процесс

4. Поступили входные данные

Переходы 2 и 3 вызываются планировщиком процессов операционной системы, так что сами процессы даже не знают о этих переходах. С точки зрения самих процессов есть два состояния выполнения и ожидания.

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

4.2 Потоки (нити, облегченный процесс)

4.2.1 Понятие потока

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

4.2.2 Модель потока

С каждым потоком связывается:

    Счетчик выполнения команд

    Регистры для текущих переменных

    Состояние

Потоки делят между собой элементы своего процесса:

    Адресное пространство

    Глобальные переменные

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

  • Семафоры

    Статистическую информацию.

В остальном модель идентична модели процессов.

В POSIX и Windows есть поддержка потоков на уровне ядра.

4.2.3 Преимущества использования потоков

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

    Быстрота создания потока, по сравнению с процессом, примерно в 100 раз.

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

4.2.4 Реализация потоков в пространстве пользователя, ядра и смешанное

B - потоки в пространстве ядра

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

Преимущества случая А :

    Такую многопоточность можно реализовать на ядре не поддерживающим многопоточность

    Более быстрое переключение, создание и завершение потоков

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

Недостатки случая А :

    Отсутствие прерывания по таймеру внутри одного процесса

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

    Сложность реализации