Особенности алгоритмов управления ресурсами

Особенности алгоритмов управления ресурсами

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

Особенности аппаратных платформ

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

Особенности областей использования

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

Особенности методов построения

К таким базовым концепциям относятся: Способы построения ядра системы - монолитное ядро или микроядерный подход. Большинство ОС использует…

Реализация процессов

Внутреннее устройство процессов в ОС Windows

Блок управления процессом (PCB) реализован в виде набора связанных структур, главная из которых называется блоком процесса EPROCESS. Соответственно,… Рис. 5.2. Управляющие структуры данных процесса

Проблемы межпроцессного взаимодействия

Проблема разбивается на три пункта:

§ обмен информацией между процессами,

§ недопущение конфликтных ситуаций,

§ согласование действий процессов.

Последние две проблемы можно объединить в одну и назвать ее «Синхронизация».

Обмен информацией между процессами

§ Сигнальные. Передается минимальное количество информации – один бит, "да" или "нет". Используются, как правило, для извещения… § Канальные. «Общение» процессов происходит через линии связи, предоставленные… § Разделяемая память. Два или более процессов могут совместно использовать некоторую область адресного пространства.…

Сигналы

При получении сигнала исполнение процесса приостанавливается и запускается специальная подпрограмма — обработчик сигнала. Обработчики сигналов могут… У сигнала есть только одна характеристика, несущая информацию — его номер… § SIGINT (2) — Сигнал передается активному приложению при нажатии сочетания Ctrl+C, по умолчанию завершает процесс. …

Каналы

Канал — поток данных между двумя или несколькими процессами, имеющий интерфейс, аналогичный чтению или записи в файл. Каналы бывают одно- и двунаправленными. В UNIX каналы, как и многие другие системные объекты, представлены в виде файлов, вся работа с ними производится через базовый файловый интерфейс — открытие и закрытие файла, чтение и запись данных и т. п. В этом смысле каналы можно представлять в виде специализированных файлов, которые не хранят информацию, а лишь накапливают её до следующей операции чтения из канала другим процессом, образуя очередь.

По умолчанию в UNIX каждому процессу при запуске ставится в соответствие три открытых файла: стандартного ввода, стандартного вывода и стандартного вывода для ошибок. С помощью средств командной строки такие потоки для разных процессов могут быть объединены так, что, к примеру, вывод одного процесса будет подаваться на ввод другого. То есть процесс работает с тремя потоками данных одинаково вне зависимости от того, обычные это файлы или же кананлы. В более общем смысле такие потоки называют неименованными каналами. Канал создаётся по запросу и существует только в ходе работы двух процессов, другие процессы в системе не могут обратиться к этому каналу. Если процесс на одной из сторон канала завершается и закрывает канал, другому процессу посылается специальный сигнал — SIGPIPE.

Другой вид каналов в UNIX — именованные каналы — представляют собой особый тип файлов. Эти файлы располагаются в файловой системе и могут быть открыты любым процессом. Одни процессы записывают данные в канал, другие — читают из него, данные продвигаются по каналу в порядке очереди (FIFO).

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

Вызов POSIX — pipe().

Разделяемая память

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

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

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

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

Вызовы POSIX — shmem(), mmap().

Почтовые ящики

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

Мониторы Хоара

Монитор – это пассивный набор разделяемых переменных и повторно входимых процедур доступа к ним, которым процессы пользуются в режиме разделения,… Рассмотрим, например, некоторый ресурс, который выделяет соответствующий… Таким образом, монитор – это механизм организации параллелизма, который содержит как данные, так и процедуры,…

Реализация в Windows

В Windows определен список событий, которые приводят к перепланированию потоков: · создание и завершение потока; · выделенный потоку квант исчерпан;

Управление памятью

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

Типы адресов

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

Методы распределения памяти без использования дискового пространства

 

Методы распределения памяти без использования дискового пространства

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

 

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

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

 

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

 

Распределение памяти разделами переменной величины

В этом случае память машины не делится заранее на разделы. Сначала вся память свободна. Каждой вновь поступающей задаче выделяется необходимая ей память. Если достаточный объем памяти отсутствует, то задача не принимается на выполнение и стоит в очереди.

Перемещаемые разделы

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

 

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

 

Понятие виртуальной памяти

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

Страничное распределение

  Виртуальное адресное пространство каждого процесса делится на части…  

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

 

Сегментное распределение

  Сегментное распределение

Странично-сегментное распределение

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

Вызов удаленных процедур (RPC)

Концепция удаленного вызова процедур

Характерными чертами вызова локальных процедур являются: Асимметричность, то есть одна из взаимодействующих сторон является инициатором; … Реализация удаленных вызовов существенно сложнее реализации вызовов локальных… Кроме того, существует ряд проблем, связанных с неоднородностью языков программирования и операционных сред: структуры…

Базовые операции RPC

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

count=read (fd,buf,nbytes);

где fd - целое число,
buf - массив символов,
nbytes - целое число.

Чтобы осуществить вызов, вызывающая процедура заталкивает параметры в стек в обратном порядке (рисунок 3.1). После того, как вызов read выполнен, он помещает возвращаемое значение в регистр, перемещает адрес возврата и возвращает управление вызывающей процедуре, которая выбирает параметры из стека, возвращая его в исходное состояние. Заметим, что в языке С параметры могут вызываться или по ссылке (by name), или по значению (by value). По отношению к вызываемой процедуре параметры-значения являются инициализируемыми локальными переменными. Вызываемая процедура может изменить их, и это не повлияет на значение оригиналов этих переменных в вызывающей процедуре.

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

Существует также другой механизм передачи параметров, который не используется в языке С. Он называется call-by-copy/restore и состоит в необходимости копирования вызывающей программой переменных в стек в виде значений, а затем копирования назад после выполнения вызова поверх оригинальных значений вызывающей процедуры.

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

Рис. 3.1. а) Стек до выполнения вызова read;
б) Стек во время выполнения процедуры;
в) Стек после возврата в вызывающую программу

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

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

Этапы выполнения RPC

Рис. 3.2. Remote Procedure Call Когда ядро получает управление, оно переключает контексты, сохраняет регистры процессора и карту памяти (дескрипторы…

Вызов стаба

Подготовить буфер

Упаковать параметры

Заполнить поле заголовка

Вычислить контрольную сумму в сообщении

Прерывание к ядру

Очередь пакета на выполнение

Передача сообщения контроллеру по шине QBUS

Время передачи по сети Ethernet

Получить пакет от контроллера

Процедура обработки прерывания

Вычисление контрольной суммы

Переключение контекста в пространство пользователя

Выполнение серверного стаба

 

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

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

Алгоритм синхронизации логических часов

Введем для двух произвольных событий отношение "случилось до". Выражение a R b читается "a случилось до b" и означает, что все… Ставится задача создания такого механизма ведения времени, который бы для… Рассмотрим алгоритм решения этой задачи, который предложил Lamport. Для отметок времени в нем используются события. На…

Алгоритмы взаимного исключения

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

Распределенный алгоритм

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

Алгоритм Token Ring

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

Неделимые транзакции

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

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

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

Различные способы организации вычислительного процесса с использованием нитей

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

Вопросы реализации нитей

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

Нити и RPC

Идея заключается в следующем. Когда стартует серверная нить S, то она экспортирует свой интерфейс, сообщая о нем ядру. Интерфейс определяет, какие… Этот метод имеет несколько преимуществ по сравнению с обычным RPC. Во-первых,…