WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

 

На правах рукописи

ТОРМАСОВ Александр Геннадьевич

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

Специальность 05.13.18 математическое моделирование,
численные методы и комплексы программ

Автореферат
диссертации на соискание ученой степени
доктора физико-математических наук

Москва – 2008

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)

Официальные оппоненты:

доктор технических наук, профессор

Семенихин Сергей Владимирович

Институт электронных управляющих машин

доктор физико-математических наук, профессор

Семёнов Виталий Адольфович

Институт системного программирования РАН

доктор физико-математических наук, профессор

Серебряков Владимир Алексеевич

Вычислительный центр имени А.А. Дородницына РАН

Ведущая организация:

Институт автоматизации проектирования РАН

Защита состоится 27 июня 2008 года в 10-00 часов на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан _____________________________ 2008 года.

Ученый секретарь диссертационного совета Д 212.156.05

кандидат физико-математических наук        Федько О.С.

Актуальность темы

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

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

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

Такие интенсивно развивающиеся в последние годы направления исследований, как GRID, Internet2, Web 2.0/3.0, реализация поддержки во всех современных ОС технологий аппаратной виртуализации компаний Intel и AMD подтверждают актуальность темы диссертационного исследования в области математического моделирования средств управления ресурсами и данными в распределенных и виртуализованных средах.

Цель работы и объект исследования

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

Задачи исследования:

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

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

Методы исследования

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

Научная новизна

В работе впервые предложены:

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

Теоретическая и практическая значимость

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

Результаты работы внедрены в крупных компаниях – производителях ПО (SWsoft/Parallels, Acronis – в этих компаниях совокупно работает более 1000 инженеров). На основании разработок диссертанта создана новая отрасль индустрии ПО – «виртуализация ОС». ПО, включающее в себя алгоритмы, разработанные диссертантом, установлено у более чем 700,000 потребителей в 125 странах на 17000 серверах (технология Virtuozzo®).

По результатам работы получено 14 патентов США и подано более 80 заявок на патенты США. Эти патенты являются международными объектами интеллектуальной собственности в странах, входящих в World Patent Organization, в том числе в России. Результаты работы могут быть использованы в учебном процессе при подготовке специалистов в области ОС, виртуализации и распределенных сред.

Публикации и апробация результатов работы

По теме диссертации опубликовано 54 работа, из них 11 статей [1-11] - в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК РФ для публикации материалов докторских диссертаций, 7 публикаций в сборниках трудов международных конгрессов, симпозиумов, конференций [21,25,26,30,33,36,41]. В работах, опубликованных с соавторами, личный вклад соискателя приведен после списка публикаций в конце автореферата.

Результаты работ по диссертации докладывались и обсуждались на многочисленных научно-исследовательских семинарах и конференциях, основные из них: «Ottawa Linux Symposium» (Оттава, Канада, 2000); VE on PC 2001 Virtual Environment on a PC Cluster Workshop 2001 Protvino (Протвино, Россия, 2001); научный семинар кафедры вычислительной математики МФТИ (Москва, 1989-1999); научный семинар кафедры информационных технологий Лундского университета, (Лунд, Швеция 2002); научный семинар по теории кодирования ИППИ РАН (Москва, 2002); научный семинар Института Системного Программирования РАН (Москва, 2005); научный семинар Вычислительного Центра РАН под руководством акад. А.А. Петрова (Москва, 2008); Перспективы систем информатики - Шестая международная конференция памяти академика А.П. Ершова (Новосибирск, 2006), Международная конференция “Математика, компьютер, образование” (Москва, 2001); Международная научно-практическая конференция по программированию компании Microsoft (Москва, 2003); XL - XLIX ежегодные научные конференции Московского физико-технического института (Москва-Долгопрудный, 1997-2007гг) и др.

Структура и объем работы

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

Общий объем работы составляет 285 страниц машинописного текста.

Содержание работы

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

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

Принципиальным отличием предложенного подхода от подхода Grid является вопрос о централизованности. Grid подразумевает идею VO – virtual organization, централизованность управления и системы безопасности, а также рассматривает преимущественно исполнение «большой» задачи на множестве вычислителей. Предложенный автором подход рассматривает в качестве нагрузки исполнение «потока» небольших задач на множестве разнородных коммуницирующих вычислителей и принципиально не содержит администрирующего центра и системы выдачи полномочий.

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

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

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

Мобильность вычислительных ресурсов - вычислительные ресурсы должны прозрачным образом «следовать» за пользователем - перемещаться между физическими носителями;

Мобильность данных – они, так же как и вычислительные ресурсы, должны «следовать» за пользователем и иметь возможность перемещаться от одного физического носителя к другому;

Независимость сетевого доступа от внешних параметров, когда доступ к сети и сетевым источникам практически не зависит от состояния внешней среды.

Для осуществления требования мобильности на уровне процессов операционной системы автором предложено использовать новую модель виртуализации операционной системы – виртуализацию на уровне пространства имен объектов внутри ядра ОС. Она предполагает изоляцию «виртуальных сред» (ВС - являющихся основным понятием модели и представляющим собой группу процессов-потребителей ресурсов ОС) путем иерархического разделения имен между разными средами. Имена объектов одной среды существуют только внутри собственного виртуального пространства, и не существует технических средств воздействовать (открыть, удалить и т.д.) на объекты другой среды. Более подробно предложенная технология описана в [35,39,40,42,49,52,54].

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

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

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

Промышленная реализация технологии для основных коммерческих ОС (технология Virtuozzo® компании Parallels - для Microsoft Windows, Linux, Unix) подтвердила, что уровень накладных расходов по сравнению с виртуальными машинами оказался в 3-10 раз ниже из за высокой эффективности разделения ресурсов ядром ОС и управления ресурсами.

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

Саморегулируемая виртуальная вычислительная среда.

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

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

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

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

Каждый файл предлагается хранить в виде некоторого набора частей (кусков), количество которых может меняться во времени. Всегда в любой момент времени для существующих в системе n частей выполняется условие, что из любых k кусков можно полностью собрать файл – (n,k)-схема хранения данных. Это условие будем называть далее условием избыточности. Размер каждого куска порядка 1/k от размера хранящегося файла (с точностью до округления). Количество кусков файла, содержащихся в системе - n, может меняться в зависимости от ее конфигурации, от количества компьютеров в ней, интенсивности работы с данным файлом и т.д. Причем, при изменении числа n уже существующие куски никак не изменяются.

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

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

Рис. 1.Обработка запроса пользователя для k­=­3.

На рисунке показано работа запроса на чтение файла при k=3. Для удовлетворения запроса пользователь будет получать k “ближайших” с точки зрения загрузки в данный момент сети и пропускной способности каналов связи.

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

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

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

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

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

Один из вариантов модели «саморегулирующейся» организации серверов, предложенный автором работы, использует введенную метрику над сетью, в которой расположены наши серверы. Она отражает сетевое «расстояние» от одного сервера до другого, например, в качестве подобной метрики может выступать время отклика от одного сервера к другому или реальная производительность канала между ними. Организуем серверы в группы таким образом, что расстояние между любой парой по указанной метрике не более некоторого заранее фиксированного порога. Размер группы не должен быть большим и обычно составляет несколько серверов (типичное значение 5-10 – см рис. 2).

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

Рис. 2. Пример объединения серверов в группы.

Автором работы описана технология реализации системы (включая протоколы обмена, способ хранения и представления данных, метод реализации предложенной системы безопасности и др), подробно описанная в диссертационной работе и работах [1,3,4,10,17,23].

Решения задач по организации алгоритмов сборки-разборки

В предыдущем разделе была вкратце описана идеология хранения данных, базирующаяся на (n,k) схеме (по-видимому, впервые предложена М.Рабином в 1989 и, независимо, автором работы в то же время). В представленной работе предложены эффективные алгоритмы сборки и разборки данных, которые можно использовать для организации хранилища.

Для организации вычислений рассматриваются операции над полями Галуа размером N=2n. Стандартное представление такого поля - многочлены степени не выше n-1, коэффициенты которых - элементы поля GF(2) остатков от деления на 2 (то есть 0 или 1). Используя факт существования генератора поля p и наличие логарифма в поле, можно свести умножение к сложению, а деление к вычитанию. Для больших значений n (более 16) операции над большими числами сводятся к операциям над числами в поле GF(216) – например, одно умножение в GF(232) можно выразить через 5 умножений в GF(216) [12].

Рассмотрим k-мерное пространство векторов L над полем P. Каждый элемент этого пространства - это k элементов поля P. Теперь каждый файл можно представить в виде последовательности векторов из L. Пусть есть файл f, который представляет собой последовательность векторов l1, l2, … lm  из L. И пусть есть набор Е из n векторов из L: Е={е1,e2,… en}. Причем этот набор такой, что любые k из них образуют базис в L. Тогда каждому вектору еi из E  можно поставить в соответствие часть (l1 ,ei) , ( l2 , ei) , …  ( lm , ei) , где (lj ,ei) - скалярное произведение векторов lj и ei. Скалярное произведение любых двух векторов из L  есть элемент из P. Поэтому размер такого куска равен n бит. Размер же исходного файла равен (m×kn) бит. Т. е. размер каждой из полученных частей равен m×n, то есть 1/k от размера самого файла.

Пусть у нас есть теперь произвольные k частей из построенного набора. Обозначим вектора, которым соответствуют части, через ε1, ε2,… εk, а сами части через Ε1, Ε2,… Εk,  По условию набора Е, эти вектора образуют базис в L. Поэтому матрица А размером k×k, строки которой - вектора ε1, ε2,… εk , имеет обратную, которую мы обозначим через A-1. Тогда Ali - столбец, состоящий из i-тых элементов всех кусков. Обозначим такой столбец через Si. Т.е. для любого i⊂[1,m]:  li=A-1Si. , т.е. из этих частей можно восстановить исходный файл.

Итак, для решения задачи нам осталось просто указать алгоритм построения набора векторов, любые k из которого образуют базис. Для каждого ненулевого элемента p поля P строим вектор (1,p,p2, … pk). Таким образом, мы можем построить N-1 вектор. Любые k из них образуют базис - детерминант образуемой ими матрицы - определитель Вандермонда, который равен нулю только, когда некоторые из знаменателей прогрессий совпадают. Указанным способом мы легко строим набор из N-1 векторов, любые k из которых образуют базис. Для того, чтобы описать вектор, по которому построена часть, достаточно задать знаменатель прогрессии, который занимает n бит.

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

В диссертационной работе проведены оценки количества операций, необходимых для работы алгоритмов – например, оценено, что для 1­мб данных и k=5 требуется приблизительно 171 000 000 тактов. Экспериментальная реализация подтверждает данный результат.

Используя SIMD расширения процессора (команды SSE), удалось достичь высоких скоростей сборки-разборки. Например, для системы на базе 2 x Intel P6 3GHz и (n,k)=(10,3) были получена скорость сборки 628 MB/sec для «оптимальных» и 157 MB/sec для остальных кусков в поле 24, и 326/120 MB/sec в поле 28.

Принципы представления данных в децентрализованном хранилище

Автором работы предложены следующие новые принципы:

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

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

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

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

. Система безопасности базируется на «декларируемых» полномочиях, то есть клиент хранилища перед началом работы декларирует наличие каких либо полномочий, на основании которых и происходит дальнейшая работа.

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

Топология и организация взаимодействия серверов

Предложенная автором [1,3] технология организации распределенной среды (далее обозначается как система) предлагает использовать набор серверов.

Все компьютеры в глобальной сети можно разбить на три группы:

  • компьютеры, на которых функционирует распределенное хранилище
  • компьютеры, с которых пользователи осуществляют доступ к хранилищу
  • остальные компьютеры

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

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

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

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

Определение  BlockID – идентификатор блока в файле

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

Определение SliceID – идентификатор слайса в блоке. Одновременно является и задающим вектором для данного слайса

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

Определение TransactionID – идентификатор транзакции. В состав входит время начала транзакции – пригоден для упорядочения транзакций.

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

Рис. 3.  Содержимое файла и сборка покрытия

Отметим, что в покрытие входят не только блоки, TID которых равен заданному. На рис. 3 изображено покрытие файла, соответствующее транзакции TID3: при записи транзакции TID2 был изменен второй блок файла, при записи TID3 - третий. По оси Х отложены «координаты» внутри файла, или Bid – block id, представляющий собой диапазон байт, упорядоченный по возрастанию.

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

Для обеспечения расширяемости, переносимости и защищенности системы автором предлагается использовать принцип активной директории, описанный в [1]. Суть его заключается в том, что в отличие от обычной директории, которая представляют собой файл с данными о своем содержимом, активная директорий состоит из файла с содержимым самой директории (обычный файл нашей системы), и из файлов с исполняемым кодом для разных платформ. Файл с кодом для конкретной платформы и является, собственно, директорным сервером на ней. Для старта корневой директории (root) используется договоренность о том, что файл с содержимым root-директории имеет идентификатор (Fid) 0. Он же является «корневой точкой доверия» - «root of trust» для системы контроля доступа хранилища.

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

Алгоритм упорядочения идентификаторов относительно числа

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

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

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

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

Соответствие предложенного метода набору требований.

Отметим, что в предложенной системе акцент делается на возможностях хранения данных, а не собственно вычислений. В качестве «облегченного» варианта вычислителей предложены «активные» директорные сервисы, которые содержат свой код и данные внутри хранилища, но собираются и запускаются на любом сервере, который запросил файл из обслуживающейся этим директорным сервисом директории. В принципе, возможно запустить в качестве директорного сервиса или вообще «вычислительной компоненты системы» виртуальную машину или виртуальную среду, например, полный эмулятор компьютера Parallels VM, Java JVM или VE (виртуальный изолированный сервер) технологии Virtuozzo® компании Parallels [47,48]. Тем не менее, система полностью функциональна в виде хранилища данных и без использования виртуальных машин.

В работе рассматривается и анализируется вопрос соответствия предложенной вычислительной среды и системы хранения данных сформулированным требованиям, в предположении использования виртуальных сред или машин для вычислений, и использования (n,k)-схемы для управления данными. Делается вывод о соответствии большинству требований, и предложения по использованию соответствующих технических средств и технологий для улучшения системы, например, технологии создания защищенных виртуальных машин Intel Trusted Execution Technology – TXT / AMD SVM.

Имитационная математическая модель поиска данных

В работе [10] получено выражение для продолжительности поиска кусков, необходимых для сборки блока некоторого файла, точнее распределение этого времени, как случайной величины, при нескольких меняющихся параметрах: центрального узла, на котором запускается процедура сборки, и расположения кусков собираемого блока файла. На основании полученного выражения построена имитационная модель, и проведены тестовые расчеты, подтвердившие корректность модели. Например, для тестовой сети в 20 узлов с довольно высокой вероятностью недоступности сервера 0.1, время поиска данных с вероятностью 0.8 укладывается в диапазон от 1.5 до 3 секунд.

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

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

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

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

В хранилище возможно два типа доступа к файлам: запись и чтение. Для контроля доступа типа «запись» используется электронная цифровая подпись (ЭЦП), для контроля доступа типа «чтение» используется шифрование с открытым ключом. Базовые свойства системы хранилища, существенные для построения математических моделей контроля доступа, можно сформулировать в виде следующих определений (О) и аксиом (А):

А1. Компьютеры могут взаимодействовать друг с другом через каналы связи.

А2. Существует дерево директорий для преобразования пути к файлу в числовой идентификатор файла (Fid). Содержимое директории хранится как файл.

А3. (Отказоустойчивость) части файла хранятся на различных серверах.

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

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

О2. Пусть  - некоторый пользователь. ЭВМ с установленной на ней ОС называется компьютером пользователя , если одновременно выполнено:

  1. соответствует некоторому пользователю “user” операционной системы;
  2. Субъекты, порождаемые от имени “user”, могут совершать криптографические преобразования с использованием секретных ключей пользователя ;
  3. Невозможен не санкционированный доступ к объектам пользователя “user”.

А4. Для каждого пользователя  существует его «компьютер пользователя».

Автор постулирует существование защищенной ПЭВМ для каждого пользователя системы.

А5. На компьютере пользователя есть некоторая априорная и корректная информация, необходимая для работы системы и обеспечения контроля доступа.

Такой информацией, в частности, является идентификатор корневой директории и открытый ключ для проверки ЭЦП корневой директории.

А6. По идентификатору  любого пользователя системы можно получить соответствующие  открытые ключи.

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

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

Математическая модель контроля доступа, названная «анонимной»

В математической модели контроля доступа, названной анонимной, после изменений файлов нельзя сказать, кто из пользователей, которым была разрешена запись, в действительности записал измененные файлы в систему. Доступ к файлу определяется списком контроля доступа (ACL – access control list), в котором открытыми ключами пользователей зашифрованы соответствующие ключи доступа к файлу. Список контроля доступа хранится в директорной записи, соответствующей данному файлу. Более детально и формально технология организации и доказательства корректности изложена в [3,30].

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

Файл хранится как совокупность транзакций. Блоки каждой транзакции шифруются при помощи «ключа транзакции» («ключа сессии») симметричной криптосистемы, который генерируется заново для каждой транзакции. Зашифрованные блоки транзакции делятся на (n,k)-части. Для контроля целостности блоков транзакции в нулевой блок помещается список значений хэш-функции от шифротекстов данных блоков. Кроме этого, он содержит зашифрованный открытым ключом ключ транзакции. Служебный блок подписывается ЭЦП. Нулевой блок хранится в открытом (незашифрованном) виде.

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

Директории предназначены для сопоставления текстового пути к файлу и Fid. Содержимое директории хранится в виде файла. Файл директории состоит из записей вида: «FileName—Fid—ACL», то есть списки контроля доступа для файлов хранятся в директорных записях для данного файла. Каждая запись представляет из себя отдельный блок файла директории, что способствует «атомарности» операций добавления/удаления директорных записей. Директорные записи (блоки), добавленные/модифицированные в результате одной транзакции, зашифрованы на ключе данной транзакции.Схема хранения ACL в директориях и доказательство корректности приводятся в [3].

В работе доказаны положения (леммы – Л), обосновывающие безопасность системы в рамках сделанных предположений:

Л1 Для доступа на чтение к содержимому файла необходимо и достаточно, чтобы у пользователя было «право на чтение файла».

Л2 «Право на запись в файл» не дает «права на чтение».

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

Л4 если у пользователя нет «права записи в директорию», содержащую файл, то «право на чтение» не дает «права на запись» в файл.

Право создания файла фактически есть право на запись в директорию, в которую помещается файл.

Л5 Для того, чтобы удалить файл необходимо и достаточно иметь «право на запись в директорию», где находится файл.

Л6 Для того, чтобы дать другому пользователю «право чтения» (текущей и последующих транзакций) файла, необходимо и достаточно одновременно:

•        иметь «право на чтение» данного файла или знать его содержимое;

•        иметь «право на запись в директорию», содержащую файл.

Л7 Для того, чтобы при неизменных ключах доступа к файлу дать другому пользователю «право на запись данного файла», необходимо и достаточно:

•        иметь «право на запись» этого файла; и

•        иметь «право на запись в директорию», содержащую файл

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

Для сделанных предположений в работе доказывается теорема (Т)

Т1. В модели 1 предписания пользователя о способе доступа выполняются.

Аналогичные утверждения и теоремы доказаны и для другой модели с введенным понятием собственника файла, близкой к традиционным моделям безопасности, применяемых в коммерческих ОС и центрах данных [3,31].

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

Как уже отмечалось, при создании вычислительной среды одним из чрезвычайно существенных факторов, определяющих возможность ее практического применения, является эффективный контроль за распределением ресурсов системы между потребителями. Обычно это все описывается в терминах «уровня сервиса» - Service Level Agreement (SLA), который содержит описание долей ресурсов (в абсолютных или относительных единицах), и условия, при которых потребитель будет получать эти ресурсы.

Автором предложено и проанализировано несколько математических моделей, которые могут быть использованы для построения систем управления вычислительными ресурсами - как в распределенной среде, так и автономно. Некоторые из этих моделей (в частности, предложенная автором модель группового наложенного управления) были внедрены и использованы как часть технологии виртуализации операционных систем Virtuozzo® [47,48].

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

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

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

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

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

Пусть управление называется наложенным, если оно:

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

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

Пусть функция потребления – зависимость потребления процессом одного или нескольких ресурсов от времени. Пусть в операционной системе существуют N процессов, и каждому из них соответствует желаемая функция потребления (которая может быть задана в виде вектора) Ri(t*), где i – порядковый номер процесса в системе, t* - собственное время процесса. Собственное время процесса совпадает с физическим временем в системе, если нет конкурентных задач (с точностью до операций ввода-вывода). Будем считать, что желаемая функция потребления каждого ресурса принимает в данный момент времени:

1 – процесс потребляет дополнительную единицу ресурса

0 -  процесс не потребляет дополнительную единицу

-1 – процесс освобождает занятую единицу ресурса.

То есть ,  и пусть - та же самая функция, но t -  реальное (физическое, системное) время, в котором процесс получал ресурсы. В общем случае . Рассмотрим преобразование t=Fi(t*), которое фактически «растягивает» временную ось («растяжение» происходит, поскольку рассматриваемому процессу процессорное время может быть не предоставлено в «желаемый» им момент времени). Пусть - та же самая функция R, но t** - идеальное время при котором идеально выполняется наложенное нами ограничение (например, гарантия доли процессорного времени). Назовем эту функцию функцией идеального потребления с идеальной функцией t**=Si(t*).

Будем считать критерием качества управления отклонение функции идеального потребления от функции фактического потребления. Тогда нашу задачу можно сформулировать следующим образом – при каких предположениях о поведении Ri(t*) выполняется условие , где a – допустимая погрешность управления, а подынтегральная функция имеет смысл меры вектора отклонения от идеального. В работе [15] выводятся интегральные уравнения для оценки компонент погрешности, вводится мера и обосновывается тот факт, что определяющим фактором стабильности нашего управления является функция DRi(Fi(t*)), которая, фактически, описывает специфику потребления ОС и связанные с ним эффекты. Доказывается, что можно достичь приемлемой точности наложенного управления путем наложения некоторого набора требований к поведению функции потребления и оценивая некоторые параметры процесса. Для невозобновляемых и частично возобновляемых ресурсов обосновано управление путем:

  • ограничения скорости потребления ресурсов – мягкий способ (за скорость потребления, фактически, отвечает коэффициент dFi(t*)/dt*) ,
  • запрещая потреблять ресурсы – жесткий способ (в данном случае это означает, что R*(t)­­R(t)).

В работe [15] рассмотрено приложение полученной абстрактной модели к ресурсу – «доле CPU», предложен алгоритм наложенного управления и оценена его точность. Результат проведенных измерений, подтверждает сделанные в модели предположения.

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

  • Все задачи в группе потребляют один и тот же ресурс
  • Задачи можно объединить по признаку (принадлежности пользователю).
  • Ресурс потребляется только одной задачей группы (для любого t).

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

Математическая модель потребления вычислительных ресурсов

Автором в [2] предложена новая математическая модель потребления ресурсов операционной системы, использующая систему дифференциальных и алгебраических уравнений (примеры решения таких систем для гиперболических уравнений в частных производных рассмотрены в [7-9,10,11]). Модель может быть использована для исследования как процесса микро-планирования на уровне планировщика ОС, так и на уровне макро планирования общего прохождения потока процессов через компьютерную систему, в том числе распределенной системы разной степени связности, и может быть использована при анализе работы предложенной виртуализованной распределенной среды.

Модельными переменными выбраны время t и расстояние x.

Переменная времени t традиционно описывает переход системы от прошлого к будущему. Переменная х является аналогом «внутреннего времени» процесса или нити исполнения. По сути своей оно изменяется только тогда, когда процесс получил долю процессора и описывает решение задачи, имея размерность «количества команд». Физический смысл x: продвижение решения задачи от начала к концу (доля решения). Максимальная скорость, с которой может выполняться «поток исполнения» («скорость звука») ограничена максимальной производительностью процессора – числом операций в секунду, которые он может исполнять. Планирование «потоков исполнения» ОС можно рассматривать как некую среднюю «скорость» передвижения. Абсолютное значение х соответствует текущей стадии выполненного процесса и меняется для каждой задачи от 0 до Xmax.

Введем величины – вектор плотности ресурсов, размерностью [ресурс/операции]. Его компоненты означает удельную плотность какого либо ресурса в точке (x,t), и u(x,t) – скорость «потока исполнения», т.е. скорость выполнения команд, или скорость продвижения по внутреннему времени, размерностью [операции/секунды], – вектор потока ресурсов [ресурс/секунды].в точке х где выполнение не дошло до этой стадии равно 0.

Рассмотрим в качестве примера ресурса долю CPU. Обозначим долю CPU, которую должен получить данный «поток исполнения» на данном процессоре T(x,t) исходя из внутренней потребности и разрешенной доли потребления (если ее поддерживает планировщик ОС), и реально полученную долю CPU D(x,t). Плотность ресурса определим как долю CPU, которая в момент времени t и долю выполненной работы x была получена «потоком исполнения». Пусть Pmax - максимальная производительность CPU. Производная потока вдоль х представляет собой изменение полученной доли ресурсов в процессе его исполнения. В наших переменных можно считать D(x,t)Pmax=u(x,t).

Запишем «закон сохранения массы» или уравнение неразрывности в форме


Здесь f1(x,t) описывает поведение «источника» массы. Если вспомнить, что по сути своей есть удельная доля использованного CPU, то фактически f1(x,t) представляет собой функцию «желаемого уровня потребления» ресурсов в дифференциальной форме – то, что предоставил задаче планировщик системы по ее запросу, с учетом уровня SLA и отклонений от него.

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

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

Имеет смысл выделить несколько частных случаев, на которых можно рассмотреть поведение «усредненного планировщика», который при прочих равных условиях стремится скомпенсировать  разность между желаемой долей ресурсов каждой нити исполнения T(x,t) и полученной долей D(x,t). Это можно считать «давлением», определяющим изменение потока ресурсов. Пример описания планировщика в рамках модели приведен в [2].

В рамках модели естественным образом вводятся две независимые функции f1(x,t) и f2(x,t), описывающие внутреннюю потребность в ресурсе алгоритма «потока исполнения» и выделение ресурса планировщиком ОС.

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

Pcmax(x,­t)= Pmax ­­ DN ­/­TN,

где индекс N относится к сетевой полосе пропускания. Не возобновляемые ресурсы можно описать в основном алгебраическими формулами типа i­=­i(x,t).

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

Общая система уравнений для j-го потока и i-го ресурса выглядит как

Si(x,t) требуемый уровень потребления ресурса без учета ограничений, Tmax(x,t) текущее ограничение планировщиком, λ, μ - параметры планировщика.

Решать предложенные уравнения возможно при помощи стандартных методов – например, при помощи монотонных сеточно-характеристических схем [8], которые были использованы автором работы для решения задач моделирования в [7-9,10,11,24]. Модельные расчеты были проведены по одношаговому явному методу типа Рунге-Кутты, где начальные и граничные значения i 0; u(x,0)=1 для x [0,1], для n потоков с весом W* для соответствующего ресурса, , и расчет велся, пока .

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

Основные результаты работы

  1. Предложены принципы функционирования качественно нового поколения средств размещения и управления ресурсами и данными как децентрализованной распределенной саморегулирующейся виртуализованной мобильной среды, являющейся совокупностью вычислительных ресурсов и хранилищ данных, объединенных коммуникационной инфраструктурой.
  2. Поставлена и решена задача разработки нового подхода к виртуализации, который может быть использован как способ обеспечения мобильности приложений в виртуализованной среде.
  3. Разработана система математических и имитационных моделей, а также алгоритмов и методов управления ресурсами, необходимых для функционирования предложенной виртуализованной распределенной среды, в том числе модель группового наложенного управления ресурсами и модель представления вычислительных ресурсов и способа их потребления.
  4. Поставлена и решена задача создания математических моделей сред распределенного отказоустойчивого хранения данных с регулируемой степенью избыточности, использующих предложенный принцип хранения с регулируемой избыточностью - (n,k)-схему хранения данных.
  5. Разработаны принципы функционирования распределенной среды с открытой коммуникационной инфраструктурой и возможностью переноса защиты с серверов и коммуникаций на клиентские узлы путем использования предложенной математической модели интегрированной системы контроля доступа, базирующейся на понятии «декларируемых» полномочий.

Список работ, опубликованных по теме диссертации

Статьи из Перечня  ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК Минобрнауки РФ:

  1. Тормасов А.Г., Нижник Е.И. Математическое моделирование производительности файловой системы NTFS при нагрузке типа «запись дисковых данных» // Вестник НГУ. Серия: Инф. технологии – 2007. - т. 5, вып. 2 - c. 67-77.
  2. Тормасов А.Г. Модель потребления ресурсов вычислительной системой // Вестник НГУ. Серия: Инф. технологии - 2006. т. 4., вып. 1 - с. 63-72.
  3. Тормасов А.Г., Обернихин В.А. Схема контроля доступа для распределенной одноранговой файловой системы (TorFS). // Безопасность информационных технологий - 2005. - № 3. — с. 68-74.
  4. Тормасов А.Г., Хасин М.А., Пахомов Ю.И. Обеспечение отказоустойчивости в распределенных средах // Программирование – 2001. - № 5. - с. 26-34.
  5. Тормасов А.Г., Иванов В.Д.,  Петров И.Б., Пашутин Р.А., Холодов А.С. Сеточно – характеристический метод расчета процессов динамического деформирования на нерегулярных расчетных сетках // Мат. моделирование - 1999. т.11, № 7. - с. 118-127.
  6. Тормасов А.Г., Петров И.Б. Численное исследование косого соударения жесткого шарика с двухслойной упругопластической плитой // Мат. моделирование – 1992. т.4, № 3.— с.20-27.
  7. Тормасов А.Г., Петров И.Б., Холодов А.С. Об использовании гибридизированных сеточно-характеристических схем для численного решения трехмерных задач динамики деформируемого твердого тела // Журнал вычислительной математики и матем. физ. – 1990. - т. 30, № 8. — с. 1237-1244.
  8. Тормасов А.Г., Петров И.Б. О численном исследовании трехмерных задач обтекания волнами сжатия препятствия или полости в упругопластическом полупространстве // Докл. АН СССР – 1990. - т. 314, № 4. — с. 817-820.
  9. Тормасов А. Г., Петров И.Б. , Холодов А.С. О численном изучении нестационарных процессов в деформируемых средах многослойной структуры // Изв. АН СССР сер. МТТ – 1989. - № 4. — c. 89-95.
  10. Тормасов А.Г., Петров И.Б. О численном решение пространственных задач соударения // Изв. АН СССР; сер. МТТ - 1990. - № 1 — с. 58-72.
  11. Тормасов А.Г., Жуков Д.В. Петров И.Б. Численное и экспериментальное изучение разрушения твердых тел в жидкости // Изв. АН СССР; сер. МТТ – 1991. - № 3 - с. 183-190.

Материалы и тезисы конференций, статьи в научных  сборниках и журналах:

  1. Tormasov A. G., Khasin M. A., Pakhomov Yu. I. Ensuring Fault-Tolerance in Distributed Media // Programming and Comp. Software – 2001. - № 27(5) - p. 245-251.
  2. Тормасов А.Г. Классификация требований к сервисам по размещению, хранению и управлению ресурсами и данными // Пробл. выч. математики, мат. моделирования и информатики: Сб. науч. тр. / МЗ Пресс - М., 2006. — с. 282-293.
  3. Тормасов А.Г., Петров В.А. Доставка информации пользователю в распределенных системах // Пробл. выч. математики, мат. моделирования и информатики: Сб. науч. тр. / МЗ Пресс - М., 2006. — с. 156-194.
  4. Тормасов А.Г., И.В. Луковников, К.С. Коротаев Наложенное управление ресурсами ОС // Пробл. выч. математики, мат. моделирования и информатики: Сб. науч. тр. /МЗ Пресс - М., 2006. — с. 195-211.
  5. Тормасов А.Г., Кобец А.Л., Луковников В.В, Модель управления группами потоков ввода/вывода с заданной точностью// Модел. процессов обработки информации: Сб. науч. тр./Моск. физ.-тех. ин-т. - М., 2007. – с. 272—275.
  6. Тормасов А.Г., Петров В.А. Расчет времени поиска в распределенной системе, использующей N-k схему при хранении // Процессы и методы обработки информации: Сб. науч. тр./Моск. физ.-тех. ин-т. - М., 2005. — с. 68-76.
  7. Тормасов А.Г., Нижник Е.И. Обзор проблем тестирования производительности файловых систем // Проблемы выч. математики, математического моделирования и информатики: Сб. науч. тр. /МЗ Пресс - М., 2006. — с. 89-113.
  8. Тормасов А.Г., Нижник Е.И. Тестирование производительности файловых систем на основе прогнозирующей модели // Пробл. выч. матем., мат. моделирования и информатики: Сб. науч. тр. / МЗ Пресс - М., 2006. — с. 114-135.
  9. Тормасов А.Г., Емельянов П.В., Коротаев К.С., Луковников И.В. Основные проблемы обеспечения точности управления при наложенном управлении ресурсами в современных операционных системах // Процессы и методы обработки информации: Сб. науч. тр. /Моск. физ.-тех. инст. - 2006. — с. 237-242.
  10. Белоусов С. М., Тормасов А. Г. Задачи по распределению ресурсов операционной системы с учетом возможности взаимного перераспределения пулов. // Перспективы систем информатики. Шестая международная конференция памяти акад. А.П. Ершова. Сб. тр. конф. Новосибирск - 2006. - с. 35-38.
  11. Тормасов А.Г., Нижник Е.И. Проблемы тестирования производительности Web-сервера на основе прогнозирующей модели // Процессы и методы обработки информации: Сб. науч. тр. /Моск. физ.-тех. инст. –М., 2006. — с. 249-257.
  12. Тормасов А.Г., Хасин М.А., Пахомов Ю.И Модель распределенного хранения данных с регулируемой избыточностью // Электронный журнал Исследовано в России - 2001. - № 035/010315 — с. 355-364.
  13. Тормасов А., Петров И. Численное изучение волновых процессов в слоистых средах // Сб. Методы мат. модел. и обр. инф., МФТИ - М., 1987. - с. 101-105.
  14. Tormasov A. G., Ivanov V.D. Pashutin R.A. Petrov I.B. A new object-oriented package for scientific computation // Int. Open Workshop «Actual Problems of Computational Mechanics Parallel Modeling» (IOW95) - 1995.— p. 23.
  15. Tormasov A. G., Ivanov V.D. Korutnic S.A. Petrov I.B. A program package for solving system  hyperbolic equations in 2-D domain of complex form with many unconnected boundaries. // Int. Open Workshop «Actual Problems of Computational Mechanics Parallel Modeling»  (IOW 95) – 1995.— p. 24.
  16. Тормасов А.Г., Иванов В.Д. Пашутин Р.А. Петров И.Б. Объектно-ориентированный подход в создании сред поддержки сложных вычислений // Тезисы Юб. научной конф. /МФТИ. - Долгопрудный, 1996. — с. 106.
  17. Тормасов А.Г., Иванов B.Д. Пашутин Р.А. Петров И.Б. Использование объектно-ориентированного подхода для решения задачи численного моделирования взаимодействия упругопластических тел // Совр. Пробл. фундаментальной и прикладной физики и математики. Юб. научн. конф. МФТИ – 1997. — с. 73.
  18. Тормасов А.Г., Жуков Д.В., Петров И.Б. Численное и экспериментальное изучение разрушения твердых тел в жидкости // Информатика и медицина. - М.: Наука. 1997. — с. 156-167.
  19. Tormasov A. G., Khasine М. Providing Availability of Internet Resources with Adjustable Redundancy // VE on PC 2001 Virtual Environment on a PC Cluster Workshop 2001 Protvino -2001. — с. 127-137.
  20. Тормасов А.Г., Обернихин В.А. Контроль доступа с протоколированием изменений в распределенной децентрализованной файловой системе (TorFS) // Электронный журнал Исследовано в России - 2004. - № 203 — с. 2156-2165.
  21. Тормасов А.Г., Протасов С. С. , Белоусов С. М. Архитектура и особенности функционирования современных операционных систем // Объединенный научный журнал - 2004 г., 24 (116) — с. 78-83.
  22. Тормасов А.Г., Хасин М.А. Математическая модель хранения данных на слабосвязанных серверах // Междунар. конференция “Математика, компьютер, образование”,  сборник научных трудов. Ч. 1. - Москва, Прогресс-традиция, 2001. - с. 168-176.
  23. Тормасов А.Г. Виртуализация ОС // Открытые системы - 2002. -№ 1— с.27-32.
  24. Тормасов А.Г., Протасов С. С. , Белоусов С. М., Использование виртуальных сред для предоставления услуг по размещению ресурсов в глобальной сети // Объединенный научный журнал - 2004 г., № 24 (116) — с. 74-78.
  25. Тормасов А. Г. Классификация требований к сервисам по размещению, хранению и управлению ресурсами и данными. // Перспективы систем информатики. Шестая международная конференция памяти академика А.П. Ершова. Сборник трудов конференции - Новосибирск - 2006. - с. 98-101.
  26. Тормасов А.Г. Среда для сборки многоплатформных программ // Открытые системы – 2002. -№ 09 — с. 19-21.
  27. Тормасов А.Г. Виртуализационные технологии и их возможности // BYTE/Рос. – 2005. - № 5 – с. 35-45.
  28. Тормасов А.Г.,  Николаев А.Н. Технология виртуализации ОС на предприятиях // BYTE/Рос. - 2006. - № 5 – с. 37-51.
  29. Тормасов А.Г., Протасов С. С., Белоусов С. М. Прошлое, настоящее и будущее: развитие архитектуры и принципов создания операционных систем // Объединенный научный журнал - 2004 г.,- № 24 (116) — с. 83-86.
  30. Тормасов А.Г.  Виртуализация сервисов по размещению, хранению и управлению ресурсами и данными // Технологии Microsoft в научных исследованиях и высшем образовании. Межд. науч.-практ. конф. по программированию (Академические Дни). – 2003. - http://research.microsoft.com/collaboration/university/europe/Events/
    AcademicDays/CISRussia/2003/content.aspx?03 – 36 c.
  31. Тормасов А.Г.,  Николаев А.Н. Виртуализация сегодня: задачи, проблемы, технологии, решения // PCWeek/RE, - 2006. - № 27 с. 12-14.
  32. Tormasov A. G., Kuznetsov A.N. TCP/IP options for high-performance data transmission // Builder.com – 2002. -http://builder.com.com/5100-6372_14-1050878.html – 4 p.
  33. Tormasov A. G., Kuznetsov A.N. Use sendfile() to optimize data transfer // Builder.com  – 2002. -http://builder.com.com/5100-6372_14-1044112.html – 4 p.
  34. Tormasov A. G., Kuznetsov A.N., Plant A. Take advantage of TCP/IP options to optimize data transmission // Builder.com – 2002. - http://builder.com.com/5100-6372_14-1050771.html -3 p.
  35. Tormasov A., Khassine M., Beloussov S., Protassov S. Fault tolerant storage system and method using a network of servers // Патент – 2005. - № 6,961,868 (США) — 12 p.
  36. Tormasov A., Beloussov S., Tsypliaev M., Lyadvinsky M. System and method for using file system snapshots for online data backup // Патент – 2006. - № 7,047,380 (США) - 27 p.
  37. Tormasov A., Beloussov S., Protassov S., Lunev D., Pudgorodsky Y. Hosting service providing platform system and method // Патент – 2006. - № 7,076,633 (США) — 13 p.
  38. Tormasov A., Beloussov S., Protassov S., Lunev D., Pudgorodsky Y. Virtual computing environment // Патент – 2006. - № 7,099,948 (США) — 8 p.
  39. Tormasov A., Beloussov S., Protassov S., Pudgorodsky Y. Distributed network data storage system and method // Патент – 2007. - № 7,209,973 (США) — 17 p.
  40. Tormasov A., Beloussov S., Protassov S., Method of implementation of data storage quota // Патент – 2008. - № 7,325,017 (США) — 16 p.
  41. Tormasov A., Beloussov, Protassov, System, method and computer program product for multi-level file-sharing by concurrent users // Патент – 2008. - № 7,328,225 (США) — 25 p.
  42. Tormasov A., Beloussov S., Tsypliaev M., Lyadvinsky M. System and method for online data migration // Патент – 2007. - № 7,281,104 (США) — 17 p.
  43. Tormasov A., Beloussov S., Protassov S., Pudgorodsky Y. Common template file system tree for virtual environments and virtual servers // Патент – 2007. - № 7,222,132 (США) — 6 p.

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

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

[4,8,12,23] – мат. модель производительности файловой системы; [3,31] – принцип построения децентрализованной системы безопасности без центра авторизации, требования к ней, мат. модель, доказательства безопасности; [7,10,12,30,33,50] – принцип использования (n,k)-технологии и алгоритмы хранения данных для обеспечения отказоустойчивости распределенной системы и способы реализации; [5,6,11,14-18,25-29] - адаптация вычислительных схем разного типа для численного решения многомерных гиперболических уравнений для сложных моделей сред и сложной геометрии расчетной области; [1, 20] – имитационная модель пересылки информации на графе и ее применение для оценки времени поиска; [21,22,24] – математическая модель и алгоритм наложенного группового управления ресурсами; [35,39,40,42,49,52,54] - типы и модели виртуализации, области ее применения, методы создания виртуальных сред; [43-45] - методика построения оптимальных высокоскоростных сетевых соединений; [46,48] – метод и технология организации распределенных хранилищ; [47,53] – технология онлайн миграции данных и процессов в виртуализованных средах; [51] – технология наложенного управления ресурсами ОС.

ТОРМАСОВ Александр Геннадьевич

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

Автореферат

Подписано в печать 24.03.08. Формат 60х90/16.

Усл. печ. л. 2.1. Тираж 100 экз. Заказ №37.

Московский физико-технический институт
(государственный университет)

Печать на аппарате Rex-Rotary Copy Printer 1280. НИЧ МФТИ.

141700, г. Долгопрудный, Московская обл., Институтский пер., 9
тел.: (095) 4088430, факс: (095) 5766582






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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