Централизованный алгоритм  

Централизованный алгоритм

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

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

36) Синхронизация в многопроцессорных системах. Распределенные алгоритмы синхронизации. Выбор координатора.

37) Миграция процессов. Процедура и концепции миграции процессов.

Миграция процессов представляет собой перенос процесса с одного процессора на другой. Этот перенос может потребоваться при отказе или перегрузке процессора или процессорного узла. Возможность исполнения процесса на любом процессоре дает множество преимуществ:

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

2. Возможность миграции процессов повышает отказоустойчивость

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

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

Для того чтобы выполнить миграцию процессов эти процессы должны обладать рядом свойств:

1. Мигрирующий процесс должен быть прозрачным



2. Процессы должны иметь возможность миграции между разными архитектурами в распределенных системах

3. Система должна быть масштабируемой

4. Информация о состоянии процесса должна храниться в платформо – независимом формате

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

38) Миграция процессов. Стратегии миграции процессов.

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



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

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

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

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

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

39)Архитектура операционной системы Android .

· Система Android – это многопользовательская Linux-система, в которой каждое приложение работает с правами уникального пользователя. В Android реализована характерная для Unix-подобных ОС система базовой безопасности и управления доступом, в которой

а) все в системе является файлом, который обязательно принадлежит какому-то пользователю (имеет соответствующий User ID, UID) и

б) любой процесс в системе обязательно работает с правами какого-то пользователя (тоже имеет свой UID); сопоставляя UID'ы процесса и файла, система безопасности Unix разрешает или запрещает запрашиваемую процессом операцию с конкретным файлом.

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

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

· По умолчанию, каждое приложение выполняется в собственном процессе Linux. Android создает процесс, когда требуется выполнить какой-либо из компонентов приложения, и уничтожает процесс, когда он больше не нужен или когда система должна предоставить память другим приложениям.

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

компонентную модель Android в виде некоторой иерархии, то в самом низу, как самая фундаментальная и базовая составляющая, будет располагаться ядро операционной системы. Часто компонентную модель ещё называют программным стеком. Действительно, это определение тут уместно, потому что речь идет о наборе программных продуктов, которые работают вместе для получения итогового результата. Действия в этой модели выполняются последовательно, и уровни иерархии также последовательно взаимодействуют между собой. Как известно, Андроид основан на несколько урезанном ядре ОС Linux и поэтому на этом уровне мы можем видеть именно его (версии 2.6.x). Оно обеспечивает функционирование системы и отвечает за безопасность, управление памятью, энергосистемой и процессами, а также предоставляет сетевой стек и модель драйверов.Ядро также действует как уровень абстракции между аппаратным обеспечением и программным стеком.

· Приложения (Applications): Android поставляется с набором основных приложений, включающих в себя клиент электронной почты, календарь, карты, браузер, программу для управления контактами и другие. Все эти приложения написаны с использованием программирования Java.

· Фреймворк: Предоставляя открытую платформу для разработки, Android дает разработчикам возможность создавать мощные и инновационные приложения. Разработчики могут использовать самые современные аппаратные средства, получать информацию о текущем местоположении, запускать фоновые службы, устанавливать сигнализацию, добавлять уведомления в строке состояния, и многое, многое другое. Разработчики имеют полный доступ к тем же API, которые используются при создании встроенных приложений. Архитектура Android спроектирована для упрощения повторного использования программных компонентов, любое приложение может «опубликовать» свои функциональные возможности, а любые другие приложения могут затем использовать эти возможности (с учетом ограничений безопасности, налагаемых фреймворком). Этот же механизм позволяет пользователям при необходимости заменять программные компоненты. Фреймворк включает в себя набор сервисов и систем, лежащих в основе всех приложений:

· Богатый и расширяемый набор представлений(View), которые могут быть использованы для создания приложений, включая списки(ListView), текстовые поля(TextView), кнопки(Button) и даже встраиваемые веб-браузер(WebView) и карты (MapView).

· Контент-провайдеры(Content Providers), которые позволяют приложениям получать доступ к данным из других приложений (например, контактов), либо делиться своими данными.

· Менеджер ресурсов(Resource Manager), обеспечивающий доступ к ресурсам, не являющимся программным кодом, таким, как локализованные строки(strings), графические ресурсы(drawable) и файлы разметки(Layouts).

· Менеджер уведомлений(Notification Manager), который позволяет всем приложениям отображать пользовательские уведомления в строке состояния мобильного устройства.

· Менеджер «Активностей»(Activity Manager), который управляет жизненным циклом приложений и предоставляет возможности переключения между различными «Активностями».

· Библиотеки: Android включает в себя набор библиотек C/C++, используемых различными компонентами системы. Фреймворк предоставляет разработчикам возможности всех этих библиотек. Ниже описаны некоторые из основных библиотек:

· Системная библиотека C (libc) – основанная на коде libc, заимствованном из BSD, реализация стандартной системной библиотеки, оптимизированная для мобильных устройств на базе ядра Linux.

· Медиа-библиотека – основанная на базе фреймворка OpenCore корпорации PacketVideo, библиотека обеспечивает работу со многими популярными форматами аудио, видео и изображений.

· SurfaceManager – управляет доступом к подсистеме отображения и обеспечивает «бесшовное» наложение 2D- и 3D-графики из нескольких приложений .

· LibWebCore – современный движок, используемый как встроенным в Android веб-браузером, так и компонентами внутри приложений (WebView).

· SGL – основной механизм для отображения двумерной графики.

· 3D-библиотеки – реализуют API, основанный на OpenGL ES API; эти библиотеки используют либо аппаратное ускорение 3D-графики (при наличии аппаратного акселератора) или встроенный оптимизированный программный растеризатор трехмерной графики.

· FreeType – обеспечивает растровый и векторный рендеринг шрифтов

· SQLite – мощный и легкий механизм реляционной СУБД, доступный для всех приложений.

· Рабочая среда (runtime environment, RTE):

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

· Каждое приложение Android выполняется в собственном процессе, со своим собственным экземпляром виртуальной машины Dalvik. ВМ Dalvik была спроектирована и написана таким образом, чтобы внутри мобильного устройства могли эффективно работать несколько виртуальных машин. Виртуальная машина Dalvik может выполнять программы в исполняемом формате DEX (Dalvik Executable). Данный формат оптимизирован для использования минимального объема памяти. Исполняемый файл с расширением .dex создается путем компиляции классов Java с помощью инструмента dx, входящего в состав Android SDK. При использовании IDE Eclipse и плагина ADT (Android Development Tools) компиляция классов Java в формат .dex происходит автоматически.

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

Ядро Linux: Android использует Linux версии 2.6 для предоставления основных системных сервисов, таких как обеспечение безопасности, управление памятью, управление процессами, сетевой стек и работа с драйверами. Ядро также выступает как дополнительный уровень абстракции между аппаратным обеспечением мобильного устройства и остальной частью программного стека.

40) Архитектура операционной системы QNX.

QNX - это зарегистрированная торговая марка фирмы QNX Software Systems, Canada. Фирма основана в 1980 году. В то же время QNX - это операционная система (ОС) стандарта POSIX (англ. Portable operating system interface for Unix — переносимый интерфейс операционных систем Unix), которая позволяет обеспечить на персональном компьютере распределенную обработку данных в реальном масштабе времени. ОС QNX обладает такими возможностями, которые в настоящее время недостижимы для стандартных UNIX-систем.

QNX стала первой коммерческой операционной системой, которая позволила использовать передачу сообщений в качестве основного средства взаимодействия между процессами (IPC англ. Inter-Process Communication). Мощность, простота и элегантность QNX достигается благодаря построению всей системы на базе технологии IPC с передачей сообщений. Разделение задач по приоритетам, быстрое обслуживание прерываний и технология IPC, используемые в системе, делают эту ОС идеальной для применения в системах управления, работающих в реальном масштабе времени.

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

1Архитектура ОС QNX

Рисунок 2 – Структура ОС QNX

В QNX ядро имеет очень маленький размер (7 Кбайт) и выполняет две основные функции:

1. Передача сообщений. Доставка сообщений от одного процесса к другому во всей операционной системе ;

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

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

1.2 Состав операционной системы QNX

1) Администратор задач (Process Manager). Отвечает за распределение памяти, запуск и окончание задач в системе.

2) Администратор периферийных устройств (Device Manager). Управляет всей периферией: консолью, терминалами, модемами, принтерами, виртуальными терминалами (окнами). Он взаимодействует с драйверами этих устройств, также являющимися отдельными задачами. Администратор периферийных устройств отвечает за такие вспомогательные функции, как вывод эха на экран, стирание и восстановление строк и т.д. Добавление нового драйвера никак не отражается на функционировании системы, так как драйвер любого устройства в QNX является обыкновенным процессом.

3) Администратор файловой системы (Filesystem Manager). Осуществляет поддержку файловой системы.

4) Сетевой Администратор (Network Manager). Обеспечивает коммуникации в сети. Его сервис необходим для передачи сообщений между процессами, действующими на разных узлах сети.

QNX поддерживает 32 уровня приоритетов для задач и три метода диспетчеризации: FIFO, round-robin, adaptive (с понижением приоритетов).

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

В городе Оттава-Карлетон (Канада) на базе операционной системы QNX разработана система управления движением городского транспорта муниципалитета города (RMOC - Regional Municipality of Ottawa-Calerton).

системы слежения за автомобилями - Teletrac, полностью разработанной на базе ОС QNX.


4489106096336168.html
4489170116273166.html
    PR.RU™