PROBABILISTIC MODEL OF EVALUATION OF THE OPERATOR FACTORS OF THE HIGH RELIABLE COMPUTER SYSTEMS WITH RESERVE
Abstract and keywords
Abstract (English):
The mathematical model of functioning computer systems (CS) with reserve is constructed. Factors to efficien-cy, allowing value of effective functioning CS, are calculated, both at moment of time, and on gap.

Keywords:
Distributed computer systems, structural redundancy, reliability.
Text
Publication text (PDF): Read Download

 

Хорошевский Виктор Гаврилович – член-кор­респондент Российской академии наук, профессор, доктор технических наук, заслуженный деятель науки РФ, заведующий Лабораторией вычислительных систем Института физики полупроводников им.    А.В. Ржанова СО РАН, заведующий кафедрой «Вы­числительные системы» ФБГОУ ВПО «Сибирский государственный университет телекоммуникаций и информатики».

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

Широко известны работы В.Г. Хорошевского по архитектуре и проектированию распределенных ВС с программируемой структурой. Он является веду­щим разработчиком первых в мире распределенных ВС с программируемой структурой «Минск-222» (МРП СССР, 1965) и управляющей системы (1967). Данные ВС позволили отработать инструментарий параллельного программирования, предвосхитивший появление Message Passing Interface (MPI).

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

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

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

На июнь 2012 года первое место в списке TOP500 лучших суперкомпьютеров мира принадлежит США, суперкомпьютер Sequoia-BlueGene с числом ядер 1572864, пиковым быстродействием 20,132 p (petaflops, петафлопс, 1p = 1015 операций с плаваю­щей запятой в секунду); второе перешло к Японии, Computer SPARC64, число ядер 705024, быстродей­ствие 11,280 p; на пятом – Китай, Tianhe-1A-NUDTYHMPP, 186368, 4,7 p; на двадцать втором – Россия, «Ломоносов» (МГУ), 78660, 1,7 p.

 

______________________

*Работа выполнена при поддержке Совета по грантам Президента РФ (грант № НШ-2175.2012.9), РФФИ                   (грант № 12-07-00145) и Министерства образования и науки РФ в рамках реализации Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы (грант № 2012-1.1-12-000-1005-018).

 

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

1) обеспечение отказоустойчивого функциониро­вания большемасштабных ВС, насчитывающих в своем составе более миллиона компонентов;

2) эффективное использование ресурсов таких сложных комплексов по обработке информации;

3) анализ существующих и разработка новых, бо­лее перспективных архитектур ВС;

4) совершенствование инструментов параллель­ного мультипрограммирования распределенных ВС.

В США существуют национальные программы. Американцы считают, что создание суперкомпьюте­ров осуществляется исключительно в интересах на­циональной безопасности (!). И производящую ком­панию Cray правительство США эффективно под­держивает. Так, например, проект Cray X1 получил финансовую поддержку от нескольких организаций правительства США, включая NSA – агентство на­циональной безопасности. Первый вариант проекта уже создан, и с 2002 года осуществляются поставки Cray X1. Их производительность в диапазоне 1,5–50 триллионов операций в секунду.

Если обратиться к истории, то созданная Cray-1 (1976) конвейерная система обладала быстродейст­вием 160 мегафлопс (160 миллионов операций с пла­вающей запятой в секунду). И она, в самом деле, была «большой» – это 12 клинообразных стоек, имеющих высоту 1,96 м и расположенных по дуге в 270° внутри окружности диаметром 2,63 м; ее цена была 5–9 млн долларов (в зависимости от конфигу­рации).

Cray-1 – одна из самых лучших систем суперком­пьютеров своего времени. Это сейчас она кажется громоздкой, так как теперь компьютер с быстродей­ствием на порядок большей производительностью размещается в одном кристалле. Фактически Cray «присутствует» в каждом персональном компьютере. В подобные машины «вмонтирован» конвейерный способ обработки информации. Совершен переход с макроуровня на микроуровень, то есть архитектура суперкомпьютера 70-х годов прошлого столетия реа­лизована в виде кристалла площадью в несколько десятков квадратных миллиметров. Современный суперкомпьютер является не чем иным, как множе­ством связных кристаллов (коллективом вычислите­лей).

Создание и развитие ЭВМ связывают с именем Джона фон Неймана, который в 40–50-е годы про­шлого столетия создал концептуальную машину, по существу дела, имитирующую работу человека, за­нятого расчетами. Созданная в США на основе принципов Дж. фон Неймана ЭВМ EDVAC (1944–1950), а также независимо построенная в СССР под руководством С. Лебедева машина МЭСМ (1948–1951) по архитектурным возможностям и техниче­ским характеристикам были приблизительно близки. В эти машины был заложен последовательный спо­соб обработки информации. Однако последователь­ные ЭВМ уже в 60-х годах прошлого века не могли удовлетворить все потребности в вычислениях.

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

Второй подход, который также зародился в 1960-х годах, основывался на использовании единого уст­ройства управления и множества взаимосвязанных одинаковых «простых» процессоров, называемого матрицей. В результате такого параллелизма можно было достичь сколь угодно большой производитель­ности. Классикой здесь явилась разработка амери­канской матричной системы ILLIAC-IV (прообраз Internet). В те же годы у нас в стране (в частности, в Сибирском отделении Академии наук СССР) был предложен более перспективный подход к построе­нию вычислительных систем. Принцип такой: еди­ного ресурса, единого управления нет. Имеется кол­лектив равноправных взаимосвязанных вычислите­лей, способных решать сложную задачу, представ­ленную в параллельном виде.

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

Иначе говоря, функционирование ЭВМ основы­вается на имитации работы вычислителя (человека, занимающегося расчетами), а ВС – коллективов вы­числителей.

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

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

Инициаторами работ в области параллельных вы­числительных технологий в Сибирском отделении были академики М.А. Лаврентьев и С.Л. Соболев. Кстати, Михаил Алексеевич много труда положил и для создания первой ЭВМ в СССР. Фундаменталь­ный вклад в данное направление в 70-х и 80-х годах прошлого века внесли академики Н.Н. Яненко и Г.И. Марчук.

Непосредственным руководителем работ в Ин­ституте математики СО АН СССР в 60-х годах XX века был специалист по вычислительной технике Э.В. Евреинов. Его первая работа в соавторстве с Ю.Г. Косаревым о возможности построения ВС вы­сокой производительности опередила американские публикации в данной области примерно на полгода. Под руководством Э.В. Евреинова создаются первые ВС: «Минск-222» (1965–1966) и управляющая вы­числительная система для автоматизации научных исследований (1964–1967). К началу 1970-х годов за­вершается формирование концепции ВС с програм­мируемой структурой как средств обработки инфор­мации, основанных на модели коллектива вычисли­телей.

Начиная с 1970-х годов теоретические и проект­ные работы в Сибирском отделении АН СССР по ВС с программируемой структурой ведутся под руково­дством чл.-корр. РАН В.Г. Хорошевского. Эти ра­боты из академической сферы распространяются в промышленность, создается ряд систем: МИНИ­МАКС (1975), СУММА (1976), МИКРОС-1 (1986), МИКРОС-2 (1992), МИКРОС-Т (1996). В 1978 году издательством «Наука» публикуется монография Э.В. Евреинова и В.Г. Хорошевского «Однородные вычислительные системы».

Следует заметить, что, когда строят компьютер или суперкомпьютер (параллельную ВС), никто не ссылается на авторов первых идей, а американцы признают и популяризируют только свои разработки. Мы, создав распределенную ВС «Минск-222», на шесть лет опередили американскую разработку ILLIAC-IV [1].

Почему же у нас в научных кругах так устойчивы пессимистические настроения о том, что нам нико­гда не догнать ни Америку, ни Европу по части ЭВМ, не говоря уже о микроэлектронике? Мы никак не отстаем ни от американцев, ни от европейцев в области параллельных вычислительных технологий. Системы, сделанные для обороны и для космоса, до сих пор работают. В науке, в теории мы никогда не отставали, а по многим направлениям IT лидировали и не теряли своих позиций. Вопрос в другом – в тех­нологии микроэлектронного производства и недос­татке финансирования. В свое время произошло от­ставание в микроэлектронике. Но направления, ко­торые мы развиваем, не предъявляют высоких тре­бований к микроэлектронике. Мы имеем большие достижения в ряде разделов IT, которые на Западе стали разрабатываться заметно позже. Можно при­вести пример из теории структур (топологии) ВС: как соединить большое число процессоров между собой? Каждый с каждым, практически нонсенс, нельзя. Оригинальный подход и решения получены школой В.Г. Хорошевского. Не только предложены специальные графы для описания масштабируемых структур ВС, но и построены каталоги оптимальных структур (обеспечивающие, в частности, живучесть ВС). Это, например, относится к диофантовым структурам, которые были определены и исследо­ваны еще в начале 1970-х годов (названы в честь древнегреческого математика из Александрии Дио­фанта – III век н.э.). Примерно через 10 лет появи­лись подобные американские работы. Свои графы они назвали «циркулянтными» [2].

В 60-х годах прошлого столетия основателями нашей школы (Э.В. Евреинов, Ю.Г. Косарев) была разработана методика крупноблочного распаралле­ливания сложных задач. На системе «Минск-222» были отработаны инструментарий и, в частности, схемы обмена информацией между ветвями парал­лельной программы. На Западе только в 1990-х годах получает широкое внедрение эквивалентный инст­рументарий MPI (Message Passing Interface) – биб­лиотека функций для поддержки параллельных про­цессов. Эти средства необходимы для организации работы ВС в монопрограммном режиме (когда все ресурсы системы используются для решения одной сложной задачи, представленной в параллельной форме).

Современные ВС состоят из огромного количе­ства процессоров (до полутора миллионов). Их ре­сурсы должны эффективно использоваться и при од­новременном решении множества задач различной сложности (когда для каждой из них не требуется вся система). Речь идет о параллельном мультипрограм­мировании. Первые оригинальные методы и алго­ритмы оптимизации функционирования распреде­ленных ВС в мультипрограммных режимах были созданы нами еще в 1960-х и 1970-х годах. Но вос­требованными они оказались только сейчас. А ре­зультаты по надежности и живучести распределен­ных ВС? Мы продолжаем активно работать в этой области. Это относится и к другим математическим школам.

Модное слово «кластер» широко используется в науке: в биологии, физике, химии. А в вычислитель­ной технике это синоним параллельной вычисли­тельной системы. Само понятие введено в научный оборот американской фирмой DEC (Digital Equip­ment Corporation). Как строят кластеры и в чем ори­гинальность системы, созданной совместно Лабора­торией вычислительных систем ИФП СО РАН и Центром параллельных вычислительных технологий СибГУТИ?

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

Кластер, разработанный в лаборатории ВС ИФП, имеет свои особенности. Программируемость струк­туры – важнейший принцип, который делает ВС ар­хитектурно универсальной, позволяет адаптировать ее к конкретной области применения. Система «Минск-222», созданная в 1965 году коллективом лаборатории ИМ СО РАН СССР совместно с КБ за­вода им. С. Орджоникидзе (г. Минск), была первой в мире ВС с программируемой структурой. Все после­дующие разработки (выполненные совместно с ра­дио- и электронной промышленностью) также обла­дали этим свойством. Система МИКРОС, по сути, послужила прототипом для первой модели отечест­венных суперкомпьютеров семейства МВС-1000 (руководитель работ – академик В. Левин, НИИ «Квант», г. Москва). Последняя разработка – наш кластер. Он программно реконфигурируем, допус­кает масштабирование и является пространственно распределенным. Система обладает способностью самодиагностики – ищет неисправные ресурсы, ре­конфигурируется и пользователю выдает тот ресурс, который ему необходим. Это эквивалентно подходу в электроэнергетике. Когда вы включаете в розетку какой-либо прибор, то не интересуетесь, откуда вы­дана электрическая энергия. Так же и здесь – с лю­бого узла кластера можно получить необходимую мощность для решения задачи. Это называют grid-подходом. Существуют определенные технологии, стандартизация. Кластер – это параллельная система, но он может работать и как обычная сеть. Каждый компьютер может эксплуатироваться как в автоном­ном режиме, так и в качестве одного из узлов кла­стера. Кластеры объединяют, и их множество со­ставляет мультикластер. Такие системы – распреде­ленные по управлению и в пространстве. Их быстро­действие растет пропорционально увеличению числа машин.

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

Эта ВС включает в себя кластер Лаборатории вы­числительных систем и несколько кластеров Сиб­ГУТИ. Центр параллельных вычислительных техно­логий постоянно развивает ВС, наращивает аппара­турные и программные средства. Эта ВС использу­ется для моделирования сложных проблем. Для нас же ВС – это инструмент для моделирования проблем анализа и организации функционирования распреде­ленных систем обработки информации: как органи­зовать огромные суперсистемы пространственно распределенных вычислительных ресурсов, чтобы они были эффективны. Здесь допустимы любые ар­хитектуры. Уже есть средства, которые учитывают все ресурсы и оптимизируют их использование во всех режимах. Применяется весь арсенал соответст­вующих разделов математики: и континуальные, и дискретные модели, и динамическое, и стохастиче­ское программирование, и теория массового обслу­живания, и теория игр.

В СО РАН под руководством академика А. Алек­сеева работает Совет по супервычислениям. В его функции входит и формирование суперкомпьютера в Сибирском отделении АН. Сейчас 128-процессорный фрагмент отечественной системы МВС-1000 уста­новлен в ИВМиМГ (Институт вычислительной ма­тематики и математической геофизики). На данной конфигурации уже можно моделировать сложные проблемы. Имеется доступ к ресурсам Межведомст­венного суперкомпьютерного центра, находящегося в Москве. Но ни в Москве, ни в Новосибирске пока не могут быть решены суперсложные задачи, пред­ставленные в параллельной форме; вычислительные возможности наших суперкомпьютеров достаточно скромны (см. TOP500). Поэтому единственный вы­ход – создание пространственно распределенных систем. Такой подход позволяет объединить колос­сальные вычислительные ресурсы и не связан со значительными финансовыми затратами.

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

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

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

 

Введение

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

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

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

 

Объекты и методы исследований

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

Итак, объектом исследования является резерв (структурная избыточность), исследовав состояния которого мы постараемся получить оценки для пока­зателей функционирования данной ВС. Исследова­ния будем проводить в рамках теории массового об­служивания [2–5].

 

Постановка задачи

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

Построение модели основано на следующих до­пущениях: 1) так как n << N, система высокона­дежна, выход из строя любой из ЭМ подчиняется экспоненциальному закону, то можно считать, что поток отказов генерируется бесконечным источни­ком излучения, образуя пуассоновский процесс с ин­тенсивностью ; 2) восстановление любого числа  ЭМ осуществляется в соответствии с экспоненциальным законом распределения с общей интенсивностью . После восстановления ЭМ вклю­чается в основную подсистему ВС. О термино­логии: ЭМ – требование, а восстановление – обслу­живание.

 

Математическая модель

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

Система дифференциальных уравнений имеет вид

 

 (1)

 

с начальными условиями

 

,             (2)

 

и условием нормировки

 

, .                  (3)

 

Преобразуем последнее уравнение системы (1) с учетом условия (3):

 

.

 

Решение этого уравнения при начальных усло­виях (2) записывается в виде

 

.                   (4)

 

Далее, при , получаем

 

            (5)

 

Аналогично вышеизложенному получаем, что

 

   (6)

 

Решение (4)–(6) для уравнений системы (1) по­зволяет оценить скорость вхождения системы в ста­ционарный режим.

Если система функционирует достаточно долго, то для вероятностей  достаточно иметь реше­ние для стационарного режима , тогда решение системы (1) примет вид

 

, , .

 

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

 

.                        (7)

 

Зададим доверительную вероятность g того, что ВС находится в состоянии высокой производитель­ности, тогда . Логарифмируя (7), находим

 

,

 

где  – среднее число элементов, составляющих ре­зерв; [x] – целая часть числа x.

В табл. 1 приведен пример зависимости среднего числа ЭМ структурной избыточности от числа ЭМ в ВС при заданной надежности.

 

Таблица 1

 

 

а) ;

 N

l

5

22

  188

3

5

22

 

 

б) ;

 N

l

4

15

  123

2

4

15

 

 

Из таблиц следует, что, например (табл. 1б), при числе ЭМ в ВС  структурная избыточность не превышает 0,15 % от общего числа ЭМ в ВС и  ч-1.

 

Оценка вероятности нахождения ВС в состоя­нии низкой производительности в течение вре­мени

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

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

Так как в модели рассматривается стационарный режим функционирования ВС, то  (в точке ,  имеет разрыв). Учитывая, что все потоки простейшие, то вероятность того, что за время t откажут k ЭМ:

 

.

 

Таким образом, имеем одноканальную систему массового обслуживания M/M/1, глубоко исследован­ную многими авторами [3–6], из которой при  следует, что

 

.               (8)

 

Рис. 1 иллюстрирует зависимость функции  от времени t при ,  1/ч,  1/ч, . Из рисунка следует, что при  ре­зультаты хорошо согласуются с ранее полученными в табл. 1.

 

Описание: Prob_low_productivities

 

Рис. 1. Зависимость функции  от времени :   1/ч;  1/ч

 

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

В самом деле, вернемся к формуле (8). При увели­чении n вероятность входа ВС в состояние низкой производительности уменьшается. С другой стороны, если она в него вошла, то время выхода ВС из этого состояния будет зависеть от величины  и не зависеть от n, то есть в этом случае модель бессильна.

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

 

.

 

Но , тогда

 

.                  (9)

 

Пусть , . Из формулы (4) следует, что для повышения эффективности функционирова­ния ВС следует увеличить . Из (7) и (8) следует, что при фиксированном и больших D вероятность вы­хода ВС из состояния низкой производительности ве­лика при малом t. Если n фиксировано и D мало, то из (8) следует, что необходимо увеличить значение D, то есть увеличить производительность ВУ.

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

 

Заключение

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

 

References

1. Evreinov, E.V. Odnorodnye vychislitel'nye sistemy / E.V. Evreinov, V.G. Horoshevskiy. - Novosibirsk: Nauka, 1978. - 318 s.

2. Horoshevskiy, V.G. Arhitektura vychislitel'nyh sistem / V.G. Horoshevskiy. - M.: MGTU im. Baumana, 2008. - 520 s.

3. Gnedenko, B.V. Vvedenie v teoriyu massovogo obsluzhivaniya / B.V. Gnedenko, I.N. Kovalenko. - M.: Editorial URSS, 2005. - 400 s.

4. Kleynrok, L. Vychislitel'nye sistemy s ocheredyami / L. Kleynrok. - M.: Mir, 1979. - 600 s.

5. Saati, T.L. Elementy teorii massovogo obsluzhivaniya i ee prilozheniya / T.L. Saati. - M.: Knizhnyy dom «LIB-ROKOM», 2010. - 520 s.

6. Koks, D.R. Teoriya vosstanovleniya / D.R. Koks, V.L. Smit; pod red. Yu.K. Belyaeva. - M.: Sov. radio, 1967. - 312 s.


Login or Create
* Forgot password?