Компьютерные системы

4. Многоядерность:

         Многоядерные компьютеры, конечно, не панацея, но "подвесить" многоядерный компьютер существенно сложнее. А суть такого процессора состоит в том, что он действительно имеет несколько "ядер", каждое из которых может выполнять вычисления независимо от других. Тем самым, один процесс может загрузить только одно ядро, а остальные останутся свободными. Зачем вам нужен многоядерный компьютер? Ну вот как раз, чтобы он меньше вис. Для этого хватит двух ядер. А как же программа использует все эти ядра, если один процесс может загружать только одно ядро? Автоматически - никак. Об этом должен позаботиться разработчик. Как это делается? А запускается несколько процессов, которые обмениваются друг с другом данными. Это - особый раздел программирования, так называемое параллельное программирование, зачастую более сложное, чем обычное.

Идея перехода на многоядерные процессоры стала овладевать умами  масс специалистов в области ИТ совсем недавно, примерно начиная с 2005 года, но на самом деле она далеко не так нова. Еще в далекие 60-е годы преимущества нескольких процессорных ядер перед одним обосновал Сеймур Крей, затем он реализовал свой замысел в суперкомпьютере CDC 6600. Но в силу консервативности взглядов проектировщиков, вызванных технологическими ограничениями (например, компьютерные платы собирались навесным монтажом из триодов, конденсаторов, сопротивлений и прочих дискретных компонентов), дальнейшего развития этот подход к проектированию центрального процессорного устройства не получил.

За возрождение многоядерности на современном технологическом уровне, как и за многие другие новации, мы должны быть благодарны инженерам корпорации Digital Equipment. Именно здесь во второй половине 90-х всерьез, на промышленном уровне, задумались о многоядерности в процессорах; это произошло при переходе процессора от Alpha 21164 (EV5) к Alpha 21264 (EV6). Тогда исследователям из DEC удалось установить две важные закономерности, распространяющиеся на процессоры. Во-первых, оказалось, что для линейного роста производительности монолитных (одноядерных) процессоров требуется обеспечить квадратичный рост числа транзисторов. Во-вторых, как следствие, также нелинейно (хотя и трудно сказать, как именно) возрастет сложность проектирования. Элементарное рассуждение подсказывает, что суммирование производительности нескольких ядер даст ту же совокупную производительность, что и одно ядро при меньшем числе транзисторов. Вопрос в том, как объединить мощности отдельных ядер, в этом состоит коренная проблема многоядерности. Реакцией DEC на обнаруженные проблемы стал проект Piranha, предполагавший создание 8-ядерного процессора, где каждое ядро должно было иметь отдельную кэш-память для команд и данных, для совместной работы процессоры объединялись коммутатором. Однако после перехода в ведение Compaq проект Piranha был похоронен, процессор так и не был реализован.

Низкая эффективность  использования транзисторов, когда  большая их часть отдается схемам управления и существенно меньшая — выполнению собственно арифметических и логических операций, и, как следствие, высокое энергопотребление, стали главным тормозом на пути дальнейшего развития монолитных процессоров. Весьма наглядной иллюстрацией происходящего стало явление, получившее название «разрыв Мура» (The Moore’s gap). Сложность проектирования увеличивает время проектирования некоторых наиболее сложных процессоров до неприемлемых значений; в некоторых случаях период проектирования затягивается больше чем на десятилетие. Характерный пример — прогноз выпуска серверов архитектуры IA-64. На пороге третьего тысячелетия перспектива серверного процессора казалась многим очевидной; будущая монополия Itanium (тогда проект еще назывался Merced) не вызывала сомнения, открытым оставался лишь вопрос о времени ее появления. Практические же результаты оказались столь скромными, что дали основания скептикам с издевкой называть процессор не иначе как Itanic. Рынок серверов инерционнее рынка рабочих станций, поэтому, чтобы увидеть будущее, стоит смотреть на изменения, происходящие во втором сегменте. Примерно три-четыре года назад исчезли рабочие станции на Itanium, это явный знак судьбы этого процессора.

Параллельно с проектом Piranha группа исследователей из Стэндфордского университета во главе с Кунле Олокотуном работала над «многоголовым процессором» Hydra, весьма образно названным именем чудовища, с которым сражался Геракл. В качестве ядра использовался процессор MIPFS 4600. Работа (заметим, спонсировавшаяся агентством DARPA) дала хорошие результаты. Как обычно бывает в таких случаях, проект перевели на коммерческую основу, создали небольшую фирму Afara, которую возглавил тот же Олокотун. Впоследствии, проявив изрядную прозорливость, причем в далеко не самые простые для себя времена, Sun Mirosystems купила эту компанию и, заменив ядро MIPFS 4600 на UltraSPARC II и увеличив число ядер вдвое, выпустила экспериментальный процессор Niagara, получивший в серии наименование UltraSPARC T1.

Успеху Niagara способствовало и то, что в Sun велась собственная разработка двухъядерного процессора MAJC 5200, где каждое ядро способно обрабатывать четыре потока команд. Процессор UltraSPARC T1 является конвергенцией Hydra и MAJC 5200.

Процессоры SPARC вообще и UltraSPARC T1 в частности являются суперскалярными, а в Power от IBM еще используется метод внеочередного исполнения. Первым процессором с двумя ядрами стал Power4 (два ядра Power3), за ним последовал Power5, а на горизонте тоже двухъядерный Power6. Может показаться странным, но у IBM разработки многоядерных процессоров заметно связаны с производством игр. Так, процессор Xenon предназначен для игровой консоли, которая, как предполагается, придет на смену Xbox 360, он будет иметь три ядра PowerPC, где каждое ядро будет поддерживать два симметричных аппаратных потока. Другой проект, Cell, включает двухпотоковое ядро SMT Power и восемь ядер, которые называют синергетическими процессорными элементами (Synergistic Processing Element, SPE), работающими по принципу SIMD. Основное ядро Power выполняет команды из системы команд PowerPC, поддерживая специализированную систему команд SPE. С очевидным опозданием свои предложения сделали корпорации AMD и Intel: борьба на многоядерном поле стала и для производителей процессоров архитектуры x86 одним из самых актуальных вопросов сегодняшнего дня.

8. Что такое векторизация?

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

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

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

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

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

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

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

16.   Основные особенности несимметричных  мультипроцессорных систем:

           В  несимметричной  мультипроцессорной системе типа CC-NUMA:

• оперативная память является логически общей (с единым адресным пространством), но физически распределенной. Это означает, что отдельные части оперативной памяти физически закреплены за каждым процессором.
• каждому  процессору системы доступна любая ячейка оперативной памяти командами Load и Store;
• время доступа процессора в локальную (т.е., закрепленную за данным процессором) область  оперативной памяти и в «чужие» области (т.е. области оперативной памяти, закрепленные за другими процессорами)  различно;
• по способу выполнения функций операционной системы каждый процессор может выполнять любые процедуры операционной системы, в том числе и по управлению вводом-выводом;
• все процессоры идентичные.

Типичная структура  несимметричной МВС приведена на рис. 1.

     Рис. 1 – Типичная структура несимметричной МВС

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

         Узлы могут состоять из небольшого числа (2-8) процессоров, соединенных между собой какой-либо высокоскоростной подсистемой коммутации. Соединение узлов между собой, как правило, осуществляется более медленной (по сравнению с подсистемой коммутации процессоров в узле) подсистемой коммутации. Количество процессоров в узле не очень существенно для понимания того, как МВС работает, поэтому в дальнейшем будем предполагать, что в узле имеется один процессор. Рассмотрим, каким же образом обеспечивается обращение в оперативную память при выполнении команд Load и Store. В МВС имеется одно адресное пространство, распространяемое на все узлы. Реальный (не виртуальный) адрес 0 для каждого процессора в любом узле соответствует адресу 0 в локальной оперативной памяти узла 0; реальный адрес 1 для всей системы  - это адрес 1 в узле 0 и т.д., пока не будет использована вся оперативной память узла 0. Затем происходит переход к оперативной памяти узла 1, затем узла 2 и т.д. Если команда, например,  Load  обращается к ячейке оперативной памяти с адресом, попадающим в локальную память узла, то выполнение команды традиционно. Проверяется наличие данных в кэше первого уровня. При удачном исходе происходит быстрое обращение. Если же информация в кэше первого уровня отсутствует, то происходит обращение к кэшу второго уровня. При удачном обращении время получения данных несколько больше по сравнению с удачным обращением в кэш первого уровня, но значительно меньше, чем время обращения в оперативную память. При неудачном поиске информации в кэш-памятях всех уровней, происходит обращение в локальную память узла. В каждом узле имеется специальная аппаратура (назовем ее условно модуль удаленных обращений – МУО), которая обеспечивает  получение данных из «чужого» узла, причем этот «чужой» узел может быть расположен достаточно далеко от запрашивающего узла.

            Рассмотрим пример выполнения в узле А команды Load с адресом М, который принадлежит пространству адресов локальной оперативной памяти узла В. В этом случае МУО узлов А и В должны выполнить следующую последовательность действий:

МУО узла А:

- по старшим разрядам адреса определяет номер «чужого» узла В;

- формирует обращение  к МУО этого «чужого» узла В;

- выдает обращение в подсистему коммутации узлов;

МУО узла В:

- принимает заявку;

- читает данные из локальной оперативной памяти узла В;

- формирует ответное сообщение с запрошенными данными;

- передает сообщение в подсистему коммутации узлов;

МУО узла А принимает данные и выдает необходимую порцию в процессор узла А.

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

     Ключевым вопросом является то, насколько "неоднородна" NUMA или CC-NUMA-МВС? Например, если для чтения данных  из другого узла требуется только на 10% большее время, то это, практически, несущественно. В этом случае все будут относиться к системе как к симметричной МВС, и разработанные для  симметричных МВС программы будут выполняться достаточно хорошо.

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

    Как правило, NUMA МВС не выдерживают правила 1.1. Например:

 МВС серии Origin 2000 компании Silicon Graphics обеспечивали замедление в 2-3 раза;

 МВС NUMA-Q компании Sequent давали  замедление в 7,5 раз и даже больше при сильной загрузке;

 МВС  NUMALiiNE компании Data General давала еще большее замедление, чем NUMA-Q.

          При такой разнице в скорости доступа к оперативной памяти для обеспечения должной эффективности в NUMA МВС следует позаботиться о правильном расположении требуемых данных. Чтобы этого добиться, нужно соответствующим образом модифицировать операционную систему. Например, такая операционная система при запросе из программы блока оперативной памяти выделяет оперативную память в узле, в котором выполняется эта программа, так, что когда процессор ищет соответствующие данные, то находит их в своем собственном узле. Аналогичным образом должны быть изменены подсистемы (включая СУБД), осуществляющие собственное планирование и распределение оперативной памяти (что и сделали  СУБД Oracle и Informix). Такие изменения позволяют эффективно выполнять в системах с структурой NUMA приложения, разработанные для симметричных МВС, без потребности изменения кода.

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

       В современных несимметричных МВС связи между процессорами и удаленными оперативными памятями реализуют либо через прямые связи (например, как это реализовано в МВС на базе процессоров Opteron), либо с помощью неблокирующихся коммутаторов (например, как в МВС на базе процессоров Power 4, Power 5, либо в МВС Superdome 2  на базе процессоров Itanium 2).

24. Проблема миграции:

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

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

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

36. Структуры  мультипроцессорных  систем с современными  процессорами Оpteron:

Эволюция серверных  процессоров  фирмы AMD  показана  на рис. 2.

Рис. 2 - Эволюция серверных процессоров фирмы AMD 

Основные  особенности процессоров  линии  Opteron - Barcelona,   Shanghai, Istanbul, Magny-Cours:

Barcelona - первый процессор,  реализованный с истинно  четырёхъядерной структурой,  когда все четыре ядра реализованы в одном кристалле. Упрощенная структура четырехядерного процессора Barcelona  приведена на рис. 3.

Основные особенности:

• реализован с использованием 65 нм технологического процесса; 
• имел - интегрированный двухканальный контроллер оперативной памяти стандарта DDR2;
• до трех контроллеров Hyper Transport;
• 64 Кбайт кэша данных и 64 Кбайт кэша инструкций L1 для каждого ядра, 512 Кбайт кэша L2 на каждое ядро;
• общий распределённый кэш L3 – 2 Мбайт   на 4 ядра. 

Рис. 3. - Упрощенная структура четырехядерного процессора Barcelona

Процессоры Shanghai - дальнейшим развитием процессоров линии Opteron  были четырехядерные процессоры   Shanghai. Структура этих процессоров аналогична структуре процессоров Barcelona.

 Основные отличия:

- реализован с использованием 45 нм технологического процесса;

- увеличенный кэш L3 до  6 Мбайт.

Процессор Istanbul - это 6-ти ядерный процессор, реализованный в одном кристалле. Все другие параметры такие же как и у процессора Shanghai.

Реализованная  в процессоре технология HT Assist, обеспечивает (рис. 4)  оптимизацию потоков данных между процессорными ядрами. Механизм действия технологии выглядит следующим образом. Когда одному кристаллу многопроцессорной системы необходимо обработать определенный массив данных, то сначала проводится процедура проверки, не присутствует ли необходимая информация в кэш-памяти ядер соседних процессоров. Если дан отрицательный ответ, то осуществляется чтение данных из оперативной памяти. В случае МВС, оснащенной сразу четырьмя процессорами, для проведения подобной проверки может потребоваться до десяти транзакций. Технология HT Assist как раз и призвана снизить их количество до минимума - каждый из процессоров теперь "знает", куда необходимо обратиться за порцией необходимых данных, и максимальное число транзакций снижается до двух. Разумеется, приходится занимать определенный объем кэш-памяти под хранение сервисной информации - в случае HT Assist для этого выделяется 1 Мб кэш-памяти третьего уровня для каждого из процессоров. Но повышение производительности системы вполне оправдывает затраченные средства.

Рис. 4 - Преимущества технологии HT Assist.

Примеры  структур несимметричных МВС с процессорами линии Opteron Barcelona,    Shanghai, Istambul

Процессоры линии Opteron Barcelona,   Shanghai,  Istambul с тройным интерфейсом HyperTransport позволяют создавать несимметричные  4-х и 8-ми сокетные вычислительные системы. Пример четырехсокетной вычислительной системы с процессорами Barcelona приведен на рис. 5,  а 8-ми сокетной  – на рис. 6.

Рис. 5. – 4-х сокетная (16-ти ядерная) вычислительная система на базе процессоров Barcelona

Рис. 6. -  Структура 8-ми сокетной вычислительной системы

46.   Требования, которые предъявляются к кластерам  високой готовности :

Обобщенная структура  кластера высокой производительности (на примере структуры кластера МВС 1000М) приведена на рис. 7.

Рис. 7. – Обобщенная структура кластера высокой производительности МВС 1000М

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

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

Управляющая вычислительная система принимает задания от пользователей, планирует их выполнение  на вычислительных узлах, обеспечивает ввод-вывод данных. Для этих целей в ее составе, как правило, имеются необходимые подсистемы. Она соединяется с вычислительными узлами специальными сетями (Gigabit Ethernet и Fast  Ethernet в приведенном на рис. 7 примере).

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

Вычислительные  узлы в кластере соединяются:

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

с управляющей  вычислительной системой:

коммуникационной  сетью второго ранга. Ее производительность, как правило, в несколько раз  меньше производительности коммуникационной сети первого ранга;

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

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

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

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

57.    Свойства простейшего потока заявок:     

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

Простейший  поток обладает следующими свойствами:

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

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

Простейший  поток  обладает следующими свойствами:

а) сумма независимых ординарных потоков с интенсивностями

( =1 ….M) сходится к простейшему потоку с интенсивностью

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

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

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

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