2 Вида планирования:

1. Оптимизация по времени поиска цилиндра

2. Оптимизация по времени поиска записи на дорожке

Цели и критерии планирования.

Критерии:

1. Пропускная способность

2. Среднее время ответа на запрос

3. Разброс (дисперсия) времени ответа

Цели:

1. Максимизировать

2. Минимизировать

3. Минимизировать

на множестве запросов.

Стратегии оптимизации поиска цилиндра:

1. FCFS – обслуживание в порядке поступления.

Метод справедливый ( имеет хорошие значения).

и при больших нагрузках неудовлетворительны.

Используется в настольных системах при малых нагрузках.

2. SSTF – Shortest Seek Time First.

С наименьшим временем поиска – первый.

(между следующим запросом и текущим положением) минимальный.

и имеют лучшие значения.

велика.

Обращения к МД имеют тенденцию концентрироваться о области текущего расположения МГ.

Результат – запросы, далеко отстоящие от центра концентрации, игнорируются.

Используются в системах пакетной обработки.

Плохо подходит для интерактивных систем.

3. SCAN – сканирование.

Каретка с МГ движется от внешнего цилиндра к внутреннему, затем обратно, обслуживая запросы по пути следования.

– высокая

– низкая

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

Возможно бесконечное откладывание.

4. N-Step-SCAN

Модификация SCAN

Каретка с МГ движется туда-сюда, но обслуживаются запросы, накопленные к моменту изменения направления движения.

– высокая

– низкая

– мала (нет бесконечного откладывания запросов)

Но имеет место дискриминация крайних дорожек (цилиндров), т.к. разворот может произойти раньше.

5. C-SCAN – циклическое сканирование

Рабочий ход только в одном направлении, затем резко переходим к началу (либо к первому запросу).

Исключает дискриминацию крайних цилиндров.

Возможна модификация (In-Step-C-SCAN).

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

Оптимизация по времени поиска записи – SLTF (Shortest Latency Time First). Запросы упорядочиваются в соответствии с угловым положением секторов, на которых расположены записи. Аналог SSTF.

Конфигурирование ВС.

Возможные узкие места:

1. Недостаточная мощность контроллера. => Перераспределение МД

2. Недостаточная пропускная способность отдельного канала. => Переключение части контроллеров на другие каналы.

Организация в/в и файловые системы.

Файл – физическое представление информации о совокупности объектов.

Файл состоит из записей. Свойства объектов кодируются в полях наших записей.

Система управления файлами (СУФ) – часть ОС, реализующая работу с файлами.

Должна обеспечивать:

1. Эффективное распределение внешней памяти.

2. Гибкий доступ к данным.

3. Максимальную маскировку механизмов реализации СУФ от пользователей (скрывается специфика внешних устройств).

4. Максимальная независимость от типа ЭВМ и ОС.

5. Возможность совместного использования общих файлов.

6. Безопасность и целостность файлов (информации).

7. Эффективная работа с файлами (согласование работы по скоростям – буферизация и кэширование).

Именование объектов (файлов).

Пользователи создают свои пространства имен для разделяемых файлов.

Имя файла определяет функцию отображения адресов в объекты внутри файла.

СУФ хранит управляющую информация о файлах в справочниках.

Содержание справочника:

1. Пользовательское имя файла.

2. Уникальный идентификатор файла.

3. Местоположение файла.

4. Тип доступа к объектам, разрешенный пользователем.

5. Дата последнего использования.

6. Дата создания файла.

7. Частота использования.

Обращение к записям файла:

1. По имени файла находим UID.

2. Определяется местоположение файла.

3. Реализуется доступ к записям.

4. Генерация команд в/в.

СУФ имеет многоуровневую структуру:

1. Система в/в – нижний уровень.

Система в/в (СВВ) – реализует специфику работы с конкретным внешним устройством (ВУ).

Составляющие:

1. Иерархическая система каналов.

2. Устройства управления внешними устройствами.

3. Устройства в/в.

4. Программы канала, управляющие в/в.

Реализует:

1. Стандартную связь ЦП и аппаратуры в/в.

2. Управление внешними устройствами с помощью асинхронным процессов.

3. Контроль ошибок.

4. Локализация на своем уровне специфики работы с ВУ.

2. Базисная система управления файлами (UID – местоположение).

   1. Осуществляет преобразование UID в местоположение.

   2. Реализует команду расчленения файла на более мелкие подфайлы.

   3. Размещение файлов в пределах тома.

3. Логическая СУФ (имя – UID).

Реализует команды:

1. Создать файл (имя, размер, имя тома).

2. Уничтожить файл (имя).

3. Открыть файл (имя).

4. Закрыть файл (имя).

5. Читать запись (имя, что читать, сколько читать, куда читать)

6. Писать запись (имя, что, сколько, куда)

4. Методы доступа к объектам файла.

Логические методы, которые могут отличаться от физической реализации.

Характеристики:

1. Тип синхронизации

   1. Пользовательская

Базисные МД.

Команды:

1. read

2. write

3. check (для синхронизации)

1. Системная

С очередями.

Команды:

1. put

2. get

Возможна буферизация записей (при чтении/записи).

2. Тип доступа

   1. Последовательный

Прямые (адрес блока/записи)

Задача пользователя – правильно интерпретировать блок.

2. Произвольный

5. СУБД – расширение СУФ.

Принципы оценки производительности систем.

Различают 3 цели исследования производительности:

1. Оценка для выбора ВС среди альтернатив для приобретения.

2. Планирование производительности – оценка производительности разрабатываемой ВС (компонента ВС) (Проектирование с заданной производительностью)

3. Контроль производительности – сбор и накопление данных о работе имеющейся ВС для прогноза влияния на производительность каких-то планируемых изменений.

В общем случае для оценки производительности необходимо:

1. Предсказать характер прикладных задач, решаемых на ВС.

2. Предсказать нагрузку на ВС.

Возможные направления использования результатов оценки:

1. Наилучшее конфигурирование ВС.

2. Подбор стратегий управления ресурсами ВС.

3. Настройка параметров ВС на требования пользователей.

Показатели производительности:

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

2. Время ответа – время от момента ввода некоторых данных с клавиатуры до момента начала ответа – для диалоговых систем.

3. Время реакции системы – время от момента ввода данных до момента выделения времени ЦП – для систем реального времени.

4. Дисперсия времени ответа/времени реакции – мера разброса от среднего – мера предсказуемости.

5. Пропускная способность – количество задач/запросов/транзакций в единицу времени.

6. Загрузка ресурсов ВС – неоднозначный показатель – для дорогих устройств.

Методы оценки производительности:

1. Измерение элементарных времен – измерение аппаратной производительности – количество команд в единицу времени.

2. Измерение времени выполнения смеси команд – в зависимости от характера задач смесь различна.

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

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

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

6. Аналитические модели – математическая формализация процесса решения задач – позволяют быстро и наглядно увидеть плюсы и минусы ВС.

Этапы моделирования:

1. Анализ системы

2. Формализация (идеализация объекта) – решаем вопрос об адекватности

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

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

Среди аналитических моделей различают:

1. Вероятностные модели (событийные) – дерево исходов поведения системы

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

3. Конвейерные модели

Модели взаимно дополняют друг друга.

7. Имитационное моделирование ВС – позволяет исследовать трудно формализуемые моменты при аналитическом моделировании.

Все эти методы позволяют выявить:

1. Узкие места системы

2. Насыщение ресурсов

Различают пиковую и реальную производительность.

Пиковая достигается при:

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

2. Все операнды выбираются из КЭШа первого уровня.

3. Все команды выбираются из КЭШа команд первого уровня.

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

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

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

3. Проблема интерпретации оценок (правильное истолкование результатов тестирования).

Существует 3 группы тестов:

1. Тесты производителей средств вычислительной техники (СВТ)

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

#Тест ICOMP – сравнение ВС с архитектурой x86 (Intel, AMD, IBM)

2. Стандартные тесты

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

#Тест Linpack (Джек Донгарра) – тест сравнивает многопроцессорные ВС при решении научных задач

ТОП-500

#SPEC (Standard Performance Evaluation Corporation) – группа экспертов от различных производителей средств вычислительной техники

#TPC (Transaction Processing Performance Council) – тестирование класса задач обработки данных в ИС.

3. Пользовательские тесты

Учитывают конкретную специфику применения ВС.

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

ПТ применяются для выбора ВС и ПО для решения определенных прикладных задач.

Тест Linpack.

Параметры теста:

1. Размерность задачи (порядок матрицы – 100x100, 1000x1000)

2. Точность вычислений (формат значений элементов матрицы) – одинарная, двойная

3. Способ компиляции (с оптимизацией/без оптимизации)

4. Применение/нет оптимизирующей библиотеки специальных функций.

Тест SPEC.

1989, 1992, 1995, 1998, 2000,…

Включает 2 тестовых набора:

1. Сint – целочисленная арифметика

2. Cfp – арифметика с плавающей точкой

Оба набора включают в себя несколько программ (n и m), написанных либо на C, либо на Fortran.

Cint:

1. Задача из теории сетей.

2. Интерпретатор языка Lisp.

3. Задача логического проектирования.

4. Утилита упаковки текстов.

5. Компилятор языка C.

6. Операции со строками и столбцами электронной таблицы.

7. …

N

Индекс быстродействия SPECratioI(i) = время выполнения i задачи на ВС.

Cint = среднее геометрическое всех индексов.

Cfp:

1. Программа схемного проектирования

2. Программа моделирования термодинамики ядерного реактора (методом Монте-Карло)

3. Задачи квантовой химии и физики

4. Решение уравнений Максвела

5. Решение уравнений Навье-Стокса

6. …

M

Индекс вычисляется так же (SPECrationFp(i)).

Тест TPC.

Используется при оценке производительности при работе с БД.

Различают тесты TPC-A, B, C, D

Оценка – соотношение стоимость (заданного периода эксплуатации)/производительность (max число транзакций в единицу времени).

Тесты отличаются характером задач.

TPC-A – оценивает задачи, в которых используются транзакции типа «дебет-кредит» (задача «операционный зал»).

TPC-B – похож на A (использует те же транзакции), но стоимость не включает стоимость конечных терминалов.

TPC-C – задачи OLTP (On-line Transaction Processing) – функционирование нескольких филиалов банка/множества складов, на которых имеется K участков, каждый участок имеет множество клиентов (1000-10000), каждый склад имеет на участках более 10000 наименований товаров. Операции агрегирования, селекции и т.д.

TPC-D – позволяет оценивать эффективность систем поддержки принятия решений. Поддерживает операции соединения, селекции, агрегирования, сортировки.

Аналитическая отчетность.

WebStore

Позволяют оценивать эффективность веб-ориентированных сервисов.

И еще очень-очень много тестов…

Защита объектов ОС.

Механизмы защиты различны для различных частей ОС.

:

1. Аутентификация – идентифицирует субъект

2. Авторизация – что может делать субъект

3. Аудит – что сделано

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

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

2 проблемы защиты:

1. Эффективность защиты

2. Эффективность доступа

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

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

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

Адресный механизм объектов в ОЗУ – ворота к данным.

Стены и ворота для файлов – система управления файлов.

Способы возведения стен:

1. Права доступа – описываются в механизмах адресации объектов ОЗУ (СУФ)

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

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

Реализация защиты

Часто реализуется с помощью мониторов защиты. Можно реализовать монитор для каждого объекта. МЗ реализуется для классов сходных объектов.

Домены и возможности

В ОС различают:

• Активные субъекты

• Пассивные объекты

Субъект может превратиться в объект (возможность смены ролей).

Обычно субъекты получают права в отношении некоторых субъектов.

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

Субъект:

• Админ ОС | Домен 1

• Простой смертный | Домен 2

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

Описание статуса защиты

Множество доменов

Множество объектов

Описание статуса:

1. Статус защиты – отображение

– атрибуты доступа к некоторому объекту в конкретном домене.

2. Если отображение к объекту зависит только от имен и , то описать статус можно с помощью матрицы.

Матричная модель менее гибкая, чем отображение.

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

Основная проблема – расширение и сужение прав доступа.

Идея реализации – сделать из доменов объекты и обращаться с ними соответствующим образом.

Надо добавить дополнительные атрибуты для управления содержанием доменов.

1. Управление доменом

2. Владелец объекта

3. Признак копирования прав доступа

Правила изменения статуса защиты:

Правила расширения:

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

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

Правила сужения:

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

4. Домен может удалить атрибуты доступа из элемента , если домен имеет атрибут владелец по отношению к объекту и домен не имеет защищенного доступа к объекту .

Дополнительно необходимо:

1. Обеспечить связь субъектов и доменов.

2. Обеспечить возможность перемещения субъектов от домена к домену.

3. Обеспечить возможность создания новых доменов.

4. Обеспечить возможность удаления ненужных объектов, доменов из описания статуса защиты.

Схемы реализации защиты.

Требования к схеме:

1. Необходимо минимизировать накладные расходы.

2. Рационально использовать ресурс памяти.

3. Гибкость описания (доступ, деформация).

Схемы:

1. Таблица описания защиты

Минус – имеет большие размеры.

Операции в таблице – объединение объектов или доменов в группы.

2. Списки возможностей – множество списков строк, в одной строке – все объекты, принадлежащие конкретному домену.

3. Списки управления доступом – множество списков столбцов.

4. Механизм «Замок-Ключ»

Криптосистема.

Все объекты доступны, но в зашифрованном виде.

2 преобразования – шифрование и дешифрование.

Шифрование с 1 ключом – DES

Шифрование с 2 ключами – RSA

Криптоустойчивость – сохранение свойств секретности при известном алгоритме и тексте.

Повторяющиеся группы ОТ – будут наверняка повторяться в ШТ.

Для устранения используется метод сцепления.

Шифрование с 2-мя ключами (открытыми ключами):

– большое число

s – публичный ключ

t – секретный ключ

Многопроцессорные ВС.

Количество потоков данные (один, много).

Количество потоков команд (один, много).

MIMD (Multi instructions multi data).

Связь с ОП:

1. С сильной связью (SMP)

2. Со слабой связью (MPP, вычислительные кластеры)

Модель программирования.

1. UMA – Unified Memory Access

Все операнды и команды равноудалены от всех ЦП

Модель UMA – при разработке приложения не нужно заботиться о том, где расположены данные и команды.

SMP, CHP, CC-NUMA.

2. NUMA – Non UMA – неоднородный доступ к памяти.

Распределение по узлам. Ближняя и дальняя память. Отличаются временем доступа.

Разработка приложения зависит от расположения данных.

MPP, вычислительные кластеры, средства программирования MPI

SMP:

Многоуровневая память.

Механизмы обеспечения когерентности – одинаковость различных копий 1 экземпляра данных.

MPP:

«рисунок»

CMP – Cellular Multi Processing

CMP – Chip MP (многоядерный процессор)

CC-NUMA (Cache Coherent NUMA)

Для ускорения доступа к объектам все данные кэшируются => многоуровневая система памяти.

КЭШ:

1. Общий/раздельный

2. Со сквозной и обратной записью

3. КПО, ПАК, МАК

SMP, CMP, CC-NUMA, COMA (Cache only memory access)

Протоколы когерентности могут быть реализованы:

1. Явно (программист)

2. Аппаратно

3. Аппаратно-программная реализация

Реализация многоуровневой памяти в многопроцессорных ВС характеризуется следующими признаками:

1. Способ реализации протокола когерентности

2. Типы разделяемых объектов многоуровневой памяти (слово, кэш-строка, страница, сегмент)

3. Модель состоятельности – определяет последовательности доступа к памяти (SRSW, MRSW, MRMW)

4. Политика обеспечения когерентности

   1. Модификация

   2. Объявление несостоятельности

5. Управление распределением памяти и размещением данных

Модели состоятельности памяти.

1. Строгая модель состоятельности – каждая операция возвращает последнее значение.

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

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

4. Свободная модель – уточняет слабую, вводятся скобки, в рамках которых осуществляется синхронизированная обработка (acquire и release).

   1. Неторопливо-свободная – в рамках нее модификация разделяемой памяти откладывается до непосредственного обращения к памяти (при открывании синхронной скобки).

   2. Нетерпеливо-свободная – модификация происходит во время закрытия синхронного доступа.

Реализация когерентности:

• Явная – программная

• Неявная – аппаратная

Методы реализации когерентности для сосредоточенной памяти.

Когерентность реализуется между ОЗУ и ближайшим к ОЗУ КЭШем.

Необходим механизм слежения за операциями процессора над данными.

Протокол MESI (Modified, Exclusive, Shared, Invalid) – состояния строк кэша.

M – строка КЭШа модифицирована и доступна к чтению и записи только в данном процессоре.

E – строка, которая была монопольно скопирована, доступна в данном ЦП и ОЗУ.

S – строка, которая была множественно скопирована в несколько ЦП, она доступна для чтения и записи в данном процессоре, в других процессорах и в ОЗУ.

I – строка, невозможная к использованию.

Для управления режимом доступа используется бит WT – бит Write Through (1 – сквозная запись, 0 – обратная запись)

Изменения состояния строк КЭШа при выполнения чтения и записи.

Табличка

Заполнение КЭШа только при промахе чтения

При промахе записи транзакция записи реализует изменение в ОЗУ.

Сигнал управления состояний строк других процессоров.

INV = { 0, 1 }

Табличка

Реализация механизма когерентности с распределенной памятью:

CC-NUMA, CMP, COMA (единое адресное пространство)

При промахе в кэш исходного узла инициируется запрос к резидентной памяти – памяти с адресуемым объектом.

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

Запись:

1. Измененная строка некоторым ЦП посылается в резидентную память (узел).

2. Резидентный узел посылает измененную строку всем узлам, разделяющим строку (для изменения содержимого КЭШей).

3. Резидентный узел ожидает подтверждения от узлов о доставке изменений.

4. Резидентный узел разрешает продолжение вычислений узлу, выполнившему вычисление.

Очень трудоемкий алгоритм.

Более совершенный алгоритм DASH.

Протокол когерентности DASH для распределения памяти.

Каждая резидентная строка ОЗУ имеет 3 глобальных состояния:

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

2. RS – удаленно-разделенная – копии строки имеются в удаленных узлах.

3. RM – удаленно-измененная – строка изменена операцией записи в нерезидентном узле.

Локальные состояния строк КЭШа (3 штуки):

1. NU – невозможная к использованию.

2. S – разделяемая – строка КЭШа не изменена и ее копии имеются в других узлах.

3. M – измененная – строка изменена операцией записи в данном узле.

Чтение:

1. Чтение из своего кэша при локальном состоянии S/M

2. При промахе чтения или локальном состоянии NU – посылается запрос «Промах чтения» в резидентный узел.

При глобальном состоянии NC/RS копия строки посылается в запрашиваемый узел.

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

Все узлы, разделяющие строку КЭШа, организуют список.

<рисунок>

Право записи имеет головной узел.

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

Запись:

1. При локальном состоянии M вычисления продолжаются сразу после выполнения операции записи.

2. При локальном состоянии NU/S операция записи начинается с посылки в резидентный узел запроса на захват строки в исключительное пользование. Ожидается подтверждение о переводе локального состояния строки в состояние NU (во всех узлах списка).

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

<таблица>

Применение явной когерентности обусловлено:

1. Слишком большим временем реализации.

2. Слишком высокие аппаратные затраты на реализацию.

SCI – кэши в узлах строятся на памяти резидентного узла (и кэширует удаленную память)

<у Арсентия>

Средства виртуализации ВС.

Аппаратные – доменная архитектура многопроцессорных ВС – SMP архитектура (IBM, HP).

Доменная архитектура допускает разбиение ВС на системные разделы.

Системный раздел (один или несколько серверов-лезвий) содержит:

1. Свое подмножество ЦП.

2. Собственный объем оперативной памяти.

3. Ввод/вывод.

4. Собственный экземпляр ОС.

Плюсы:

• Изоляция ошибок (ОС, приложений) и пределах СР.

• Отсутствие конкуренции за ресурсы между СР.

• Упрощение управления системой ВС. Снижение эксплуатационных расходов.

• Упрощение масштабирования серверных платформ (возможна кластеризация приложений).

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

Разбиение на системные разделы:

• Статически – до запуска ОС.

• Динамически – во время работы ОС.

Разбиение на прикладные разделы на уровне ОС включает:

• Свой набор ЦП.

• Свой объем ОЗУ.

• Свой ввод/вывод.

для достижения QoS для приложения.

Системный раздел может быть разбит на несколько прикладных.

Следующий уровень виртуализации (разбиения) – разбиение на классы пользователей/приложений.

Ограничения на использование ресурсов:

1. Объем виртуальной памяти.

2. Пропускная способность сетевого соединения.

3. Объем дисковой памяти.

Мультипроцессорные ОС.

Для многопроцессорных ВС с UMA-моделью (SMP, CC-NUMA, CMP).

Центральная проблема – взаимодействие.