1 Операционные системы и оболочки Одинцов Игорь Олегович ст. преподаватель кафедры информатики весна 2006 Слайды можно взять на сайтах: и

2 Лекция 8 Процессы и алгоритмы работы с ними в сетевых и распределенных ОС (окончание) Память и алгоритмы работы с ней в централизованных ОС

3 План лекции Планирование и диспетчеризация процессов Иерархия классов памяти. Основная память Управление виртуальной памятью Сетевые и распределенные ОС Централизованные ОС

4 Что надо знать о процессах? Средства коммуникации Средства синхронизации Проблема тупиков Планирование ИзучилиИзучаем Изучаем сетевые и распределенные ОС

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

6 Разработка алгоритмов работы в модели рабочих станций Как определить простаивающую рабочую станцию? Как сообщить системе, что данная рабочая станция теперь не простаивает? Если на занятой нашим заданием удаленной рабочей станции начал работать пользователь, то что следует делать?

7 Как правило, в модели рабочей станции применяется идея координатора 1. Простаивающая рабочая станция должна сообщить координатору о том, что она не занята. Координатор поддерживает у себя информацию о незанятых рабочих станциях. 2. Процесс, желающий воспользоваться простаивающей рабочей станцией, обращается к координатору. 3. Если у координатора есть свободные рабочие станции, то он посылает заинтересованному процессу информацию о такой станции. 4. Процесс обращается к свободной рабочей станции с просьбой выделить ему ресурсы. На каждой рабочей станции есть менеджер, управляющий распределением ресурсов. 5. Менеджер рабочей станции обращается к координатору с просьбой удалить данную рабочую станцию из списка свободных. 6. Процесс выполняет установку окружения на удаленной рабочей станции. 7. Процесс запускает работу на удаленной рабочей станции. 8. Процесс выполняет работу на удаленной рабочей станции. 9. Процесс завершает работу на удаленной рабочей станции. 10. Процесс посылает координатору сообщение о завершении им работы на удаленной станции.

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

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

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

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

12 План лекции Планирование и диспетчеризация процессов Иерархия классов памяти. Основная память Управление виртуальной памятью Сетевые и распределенные ОС Централизованные ОС

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

14 Иерархия классов памяти В самом простейшем случае можно выделить основную память и внешнюю On-Chip Cache Registers Control Datapath Secondary Storage (Disk) Processor Main Memory (DRAM) Second Level Cache (SRAM) 1s 10,000,000s (10s ms) Доступ (ns): 10s-100s100s Gs Объем (bytes): Ks-MsMs Tertiary Storage (Tape) 10,000,000,000s (10s sec) Ts

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

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

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

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

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

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

21 Основные способы реализации отображения памяти Основные способы Без использования внешней памяти С использованием внешней памяти Оверлеи Свопинг Виртуальная память

22 Без использования внешней памяти Память разделяется только между программой и операционной системой

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

24 Свопинг Свопинг (swapping) разрешение системе вводить в память и выводить из нее задания целиком Свопер - планировщик, управляющий перемещением данных между памятью и диском Используется в системах разделения времени

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

26 Спасибо! Вопросы?

27 P.S. Экзаменационные вопросы: Планирование и диспетчеризация процессов Иерархия классов памяти. Основная память