<< Пред.           стр. 3 (из 8)           След. >>

Список литературы по разделу

  Еще раз подчеркнем, что любая система управления файлами не существу­ет сама по себе – она разработана для функционирования в конкретной ОС. То есть, для работы с файла­ми, организованными в соответствии с некоторой файловой системой, для каж­дой ОС должна быть разработана соответствующая система управления файлами. Эта система управления файлами будет работать только в той ОС, для которой она и создана. Но при этом она позволит работать с файлами, созданными с по­мощью системы управления файлами другой ОС и организованными в файловую систему по тем же основ­ным принципам.
  Для того чтобы можно было загрузить с магнитного диска собственно саму ОС, а уже с ее помощью и организовать работу той или иной системы управления файлами, были приняты специальные системные соглашения о структуре диска. Информация на магнитных дисках размещается и передается бло­ками. Каждый такой блок называется сектором (sector), секторы расположены на концентрических дорожках поверхности диска. Каждая дорожка (track) обра­зуется при вращении магнитного диска под зафиксированной в некотором пред­определенном положении магнитной головкой чтения-записи (head). Накопитель на жестких магнитных дисках (НЖМД) содержит один или более дисков. Обычно под термином «жесткий диск» понимают весь пакет магнитных дисков. Группы дорожек (треков) одного радиуса, расположенных на поверхностях разных маг­нитных дисков, образуют так называемые цилиндры (cylinder).
  Каждый сектор состоит из поля данных и поля служебной информации, ограни­чивающей и идентифицирующей его. Размер сектора (точнее – емкость поля данных) устанавливается контроллером или драйвером. Физический адрес сектора на магнитном диске определяется с помощью трех «координат», то есть представляется триадой [c–h–s], где с – номер цилиндра (дорожки на по­верхности диска), h – номер рабочей поверхности диска (магнитной го­ловки), s – номер сектора на дорожке. Номер цилиндра лежит в диапа­зоне 0 . . . С–1, где С – количество цилиндров. Номер рабочей поверхности диска находится в диапазоне 0 . . . Н–1, где Н – число магнитных головок в накопителе. Номер сектора на дорожке определяется в диапазоне 1 . . . S, где S – количество секторов на дорожке. Например, триада [1–0–2] адресует сектор 2 на рабочей поверхности 0 цилиндра 1.
  Обмен информацией между оперативной памятью и дисками физически осуществ­ляется только секторами. Вся совокупность физических секторов на НЖМД представляет его так называемую неформатированную емкость.
  Жесткий диск может быть разбит на несколько разделов (partition), которые затем могут использоваться либо одной ОС, либо различными ОС. Причем в каждом разделе может быть органи­зована своя файловая система. Однако для организации даже единственной файловой системы необходимо определить, по крайней мере, один раздел.
  Разделы диска могут быть двух типов – primary (обычно этот термин переводят как первичный) и extended (расширенный). При этом на диске обязательно должен быть по крайней мере один primary-раздел. Если primary-разделов несколько, то только один из них может быть активным. Именно загрузчику, расположенному в активном разделе, передается управление при включении ВМ и загрузке ОС.
  Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. До недавнего времени эти границы были весьма узкими. Современные файловые системы, как правило, поддерживают длинные символьные имена файлов. При переходе к длинным именам возникает проблема совместимости с ранее созданными приложениями, использующими короткие имена. Чтобы приложения могли обращаться к файлам в соответствии с принятыми ранее соглашениями, файловая система должна уметь предоставлять эквивалентные короткие имена (псевдонимы) файлам, имеющим длинные имена. Таким образом, одной из важных задач становится проблема генерации соответствующих коротких имен.
  Обычно разные файлы могут иметь одинаковые символьные имена. В этом случае файл однозначно идентифицируется так называемым составным именем, представляющем собой последовательность символьных имен каталогов. В некоторых системах одному и тому же файлу не может быть дано несколько разных имен, а в других такое ограничение отсутствует. В последнем случае операционная система присваивает файлу дополнительно уникальное имя, так, чтобы можно было установить взаимнооднозначное соответствие между файлом и его уникальным именем. Уникальное имя представляет собой числовой идентификатор и используется программами операционной системы.
  Файлы бывают разных типов: обычные файлы, специальные файлы, файлы-каталоги.
  Обычные файлы в свою очередь подразделяются на текстовые и двоичные. Текстовые файлы состоят из строк символов, представленных в ASCII-коде. Это могут быть документы, исходные тексты программ и т.п. Текстовые файлы можно прочитать на экране и распечатать на принтере. Двоичные файлы не используют ASCII-коды, они часто имеют сложную внутреннюю структуру, например, объектный код программы или архивный файл. Все операционные системы должны уметь распознавать хотя бы один тип файлов – их собственные исполняемые файлы.
  Специальные файлы – это файлы, ассоциированные с устройствами ввода-вывода, которые позволяют пользователю выполнять операции ввода-вывода, используя обычные команды записи в файл или чтения из файла. Эти команды обрабатываются вначале программами файловой системы, а затем на некотором этапе выполнения запроса преобразуются ОС в команды управления соответствующим устройством. Специальные файлы, так же как и устройства ввода-вывода, делятся на блок-ориентированные и байт-ориентированные.
  Каталог – это, с одной стороны, группа файлов, объединенных пользователем исходя из некоторых соображений (например, файлы, содержащие программы игр, или файлы, составляющие один программный пакет), а с другой стороны – это файл, содержащий системную информацию о группе файлов, его составляющих. В каталоге содержится список файлов, входящих в него, и устанавливается соответствие между файлами и их характеристиками (атрибутами).
  В разных файловых системах могут использоваться в качестве атрибутов файлов разные характеристики, такие, например, как информация о разрешенном доступе, пароль для доступа к файлу, владелец файла, создатель файла, признак «только для чтения», признак «скрытый файл», признак «системный файл», признак «архивный файл», признак «двоичный/символьный», признак «временный», признак блокировки, длина записи, указатель на ключевое поле в записи, длина ключа, время создания, время последнего доступа, время последнего изменения, текущий размер файла, максимальный размер файла.
  Каталоги могут непосредственно содержать значения характеристик файлов или ссылаться на таблицы, содержащие эти характеристики. Каталоги могут образовывать иерархическую структуру за счет того, что каталог более низкого уровня может входить в каталог более высокого уровня.
  Структурная организация каталогов может быть представлена в виде иерархического дерева или сети. Каталоги образуют дерево, если файлу разрешено входить только в один каталог, и сеть – если файл может входить сразу в несколько каталогов. Как и любой другой файл, каталог имеет символьное имя и однозначно идентифицируется составным именем, содержащим цепочку символьных имен всех каталогов, через которые проходит путь от корня до данного каталога.
  Программист имеет дело с логической организацией файла, представляя файл в виде определенным образом организованных логических записей. Логическая запись – это наименьший элемент данных, которым может оперировать программист при обмене с внешним устройством. Даже если физический обмен с устройством осуществляется большими единицами, операционная система обеспечивает программисту доступ к отдельной логической записи. Записи могут быть фиксированной длины или переменной длины. Записи могут быть расположены в файле последовательно (последовательная организация) или в более сложном порядке, с использованием так называемых индексных таблиц, позволяющих обеспечить быстрый доступ к отдельной логической записи (индексно-последовательная организация). Для идентификации записи может быть использовано специальное поле записи, называемое ключом.
  Физическая организация файла описывает правила расположения файла на устройстве внешней памяти, в частности, на диске. Файл состоит из физических записей – блоков. Блок (как уже было отмечено выше) – наименьшая единица данных, которой внешнее устройство обменивается с оперативной памятью. В некоторых ОС такая наименьшая единица обмена называется кластером. При этом кластер может состоять из нескольких блоков.
  Непрерывное размещение – простейший вариант физической организации, при котором файлу предоставляется последовательность блоков диска, образующих единый непрерывный участок дисковой памяти. Для задания адреса файла в этом случае достаточно указать только номер начального блока. Другое достоинство этого метода – простота. Но имеются и два существенных недостатка. Во-первых, во время создания файла заранее не известна его длина, а значит не известно, сколько памяти надо зарезервировать для этого файла, во-вторых, при таком порядке размещения неизбежно возникает фрагментация, и пространство на диске используется не эффективно, так как отдельные участки маленького размера (минимально 1 блок) могут остаться не используемыми.
  Другой способ физической организации файлов – размещение файлов в виде связанного списка блоков дисковой памяти. При таком способе в начале каждого блока содержится указатель на следующий блок. В этом случае адрес файла также может быть задан одним числом – номером первого блока. В отличие от предыдущего способа, каждый блок может быть присоединен в цепочку какого-либо файла, следовательно фрагментация отсутствует. Файл может изменяться во время своего существования, наращивая число блоков. Недостатком является сложность реализации доступа к произвольно заданному месту файла: например, для того, чтобы прочитать пятый по порядку блок файла, необходимо последовательно прочитать четыре первых блока, прослеживая цепочку номеров блоков. Кроме того, при этом способе количество данных файла, содержащихся в одном блоке, не равно степени числа 2 (одно слово израсходовано на номер следующего блока), а многие программы читают данные блоками, размер которых равен степени числа 2.
  Следующим способом физической организации файлов является использование так называемого связанного списка индексов. При этом с каждым блоком связывается некоторый элемент – индекс. Индексы располагаются в отдельной области диска. Если некоторый блок распределен некоторому файлу, то индекс этого блока содержит номер следующего блока данного файла. При такой физической организации сохраняются все достоинства предыдущего способа, но снимаются оба отмеченных недостатка: во-первых, для доступа к произвольному месту файла достаточно прочитать только блок индексов, отсчитать нужное количество блоков файла по цепочке и определить номер нужного блока, и, во-вторых, данные файла занимают блок целиком (за исключением последних блоков файла).
  Еще один способ физической организации файлов заключается в простом перечислении номеров кластеров (блоков), занимаемых данным файлом. Этот перечень и служит адресом файла. Недостаток такого способа в том, что длина адреса зависит от размера файла и для относительно большого файла может составить значительную величину. Достоинство же является высокая скорость доступа к произвольному кластеру (блоку) файла, так как в этом случае применяется прямая адресация, которая исключает просмотр цепочки указателей при поиске адреса произвольного кластера (блока) файла. Фрагментация на уровне кластеров (блоков) при этом способе отсутствует. В некоторых файловых системах для сокращения объема адресной информации прямой способ адресации сочетается с косвенным. При этом используется дерево таблиц кластеров.
  Рассмотрим понятие прав доступа к файлу. Определить права доступа к файлу – значит определить для каждого пользователя набор операций, которые он может применить к данному файлу. В разных файловых системах может быть определен свой список дифференцируемых операций доступа. Этот список может включать следующие операции: создание файла, уничтожение файла, открытие файла, закрытие файла, чтение файла, запись в файл, дополнение файла, поиск в файле, получение атрибутов файла, установление новых значений атрибутов, переименование, выполнение файла, чтение каталога и другие операции с файлами и каталогами.
  В файловых системах пользователи могут быть разделены на отдельные категории. Для всех пользователей одной категории определяются единые права доступа.
  Различают два основных подхода к определению прав доступа:
  1) избирательный доступ, когда для каждого файла и каждого пользователя сам владелец может определить допустимые операции;
  2) мандатный доступ, когда система наделяет пользователя определенными правами по отношению к каждому разделяемому ресурсу (в данном случае файлу) в зависимости от того, к какой группе пользователь отнесен.
  В некоторых файловых системах запросы к внешним устройствам, в которых адресация осуществляется блоками (диски, ленты), перехватываются промежуточным программным слоем – подсистемой буферизации. Подсистема буферизации представляет собой буферный пул, располагающийся в оперативной памяти, и комплекс программ, управляющих этим пулом. Каждый буфер пула имеет размер, равный одному блоку. При поступлении запроса на чтение некоторого блока подсистема буферизации просматривает свой буферный пул и, если находит требуемый блок, то копирует его в буфер запрашивающего процесса. Операция ввода-вывода считается выполненной, хотя физического обмена с устройством не происходило. Очевиден выигрыш во времени доступа к файлу. Если же нужный блок в буферном пуле отсутствует, то он считывается с устройства и одновременно с передачей запрашивающему процессу копируется в один из буферов подсистемы буферизации. При отсутствии свободного буфера на диск вытесняется наименее редко используемая информация. Таким образом, подсистема буферизации работает по принципу кэш-памяти.
  Функционирование любой файловой системы можно представить ой моделью, в которой каждый уровень предоставляет некоторый интерфейс (набор функций) вышележащему уровню, а сам, в свою очередь, для выполнения своей работы использует интерфейс нижележащего уровня.
  Задачей символьного уровня является определение по символьному имени файла его уникального имени. В файловых системах, в которых каждый файл может иметь только одно символьное имя, этот уровень отсутствует, так как символьное имя, присвоенное файлу пользователем, является одновременно уникальным и может быть использовано операционной системой. В других файловых системах, в которых один и тот же файл может иметь несколько символьных имен, на данном уровне просматривается цепочка каталогов для определения уникального имени файла.
  На следующем, базовом, уровне по уникальному имени файла определяются его характеристики: права доступа, адрес, размер и другие. Как уже было сказано, характеристики файла могут входить в состав каталога или храниться в отдельных таблицах. При открытии файла его характеристики перемещаются с диска в оперативную память, чтобы уменьшить среднее время доступа к файлу. В некоторых файловых системах при открытии файла вместе с его характеристиками в оперативную память перемещаются несколько первых блоков файла, содержащих данные.
  Следующим этапом реализации запроса к файлу является проверка прав доступа к нему. Для этого сравниваются полномочия пользователя или процесса, выдавших запрос, со списком разрешенных видов доступа к данному файлу. Если запрашиваемый вид доступа разрешен, то выполнение запроса продолжается, если нет, то выдается сообщение о нарушении прав доступа.
  На логическом уровне определяются координаты запрашиваемой логической записи в файле, то есть определяется, на каком расстоянии (в байтах) от начала файла находится требуемая логическая запись. При этом абстрагируются от физического расположения файла: он представляется в виде непрерывной последовательности байт. Алгоритм работы данного уровня зависит от логической организации файла.
  На физическом уровне файловая система определяет номер физического блока, который содержит требуемую логическую запись, и смещение логической записи в физическом блоке. Для решения этой задачи используются результаты работы логического уровня – смещение логической записи в файле, адрес файла на внешнем устройстве, а также сведения о физической организации файла, включая размер блока. Подчеркнем, что задача физического уровня решается независимо от того, как был логически организован файл. После определения номера физического блока, файловая система обращается к системе ввода-вывода для выполнения операции обмена с внешним устройством. В ответ на этот запрос в буфер файловой системы будет передан нужный блок, в котором на основании смещения, полученного при работе физического уровня, выбирается требуемая логическая запись.
  По сравнению с доступом к памяти, традиционный доступ к файлам представляется сложным и неудобным. По этой причине некоторые ОС обеспечивают отображение файлов в адресное пространство выполняемого процесса. Это выражается в появлении двух системных вызовов: «отобразить» и «отменить отображение». Первый вызов передает операционной системе в качестве параметров имя файла и виртуальный адрес, и ОС отображает указанный файл в виртуальное адресное пространство по указанному адресу. Отображение файлов лучше всего работает в системе, которая поддерживает сегментацию. В такой системе каждый файл может быть отображен в свой собственный сегмент. С этого момента процесс может копировать сегмент-источник в сегмент-приемник с помощью обычного программного цикла, использующего команды пересылки в памяти. После выполнения копирования процесс может выполнить вызов «отменить отображение» для удаления файла из адресного пространства, а затем завершиться. Выходной файл будет существовать на диске, как если бы он был создан обычным способом.
  Хотя отображение файлов исключает потребность в выполнении ввода-вывода и тем самым облегчает программирование, этот способ порождает и некоторые новые проблемы. Во-первых, для системы сложно узнать точную длину выходного файла. Проще указать наибольший номер записанной страницы, но нет способа узнать, сколько байт в этой странице было записано. Вторая проблема проявляется (потенциально), если один процесс отображает файл, а другой процесс открывает его для обычного файлового доступа. Если первый процесс изменяет страницу, то это изменение не будет отражено в файле на диске до тех пор, пока страница не будет вытеснена на диск. От системы в этом случае требуется поддержание согласованности данных файла для этих двух процессов. Третья проблема состоит в том, что файл может быть больше, чем сегмент, и даже больше, чем все виртуальное адресное пространство. Единственный способ ее решения состоит в реализации вызова «отобразить» таким образом, чтобы он мог отображать не весь файл, а его часть. Такая работа, очевидно, менее удобна, чем отображение целого файла.
  Разработчики ОС стремятся обеспечить пользователя возможностью работать сразу с несколькими файловыми системами. В новом понимании файловая система состоит из многих составляющих, в число которых входят и файловые системы в традиционном понимании. Современные файловые системы располагают так называемым переключателем файловых систем. Он обеспечивает интерфейс между запросами приложения и конкретной файловой системой, к которой обращается это приложение. Переключатель файловых систем преобразует запросы в формат, воспринимаемый следующим уровнем – уровнем файловых систем.
  Каждый компонент уровня файловых систем выполнен в виде драйвера соответствующей файловой системы и поддерживает определенную организацию файловой системы. Переключатель является единственным модулем, который может обращаться к драйверу файловой системы. Приложение не может обращаться к нему напрямую. Драйвер файловой системы может быть написан в виде, позволяющем сразу нескольким приложениям выполнять операции с файлами. Каждый драйвер файловой системы в процессе собственной инициализации регистрируется у переключателя, передавая ему таблицу точек входа, которые будут использоваться при последующих обращениях к файловой системе.
  Для выполнения своих функций драйверы файловых систем обращаются к подсистеме ввода-вывода, образующей следующий слой файловой системы новой архитектуры. Подсистема ввода-вывода – это составная часть файловой системы, которая отвечает за загрузку, инициализацию и управление всеми модулями низших уровней файловой системы. Обычно эти модули представляют собой драйверы портов, которые непосредственно занимаются работой с аппаратными средствами. Кроме этого подсистема ввода-вывода обеспечивает некоторый сервис драйверам файловой системы, что позволяет им осуществлять запросы к конкретным устройствам. Подсистема ввода-вывода должна постоянно присутствовать в памяти и организовывать совместную работу иерархии драйверов устройств. В эту иерархию могут входить драйверы устройств определенного типа (драйверы жестких дисков или накопителей на лентах); драйверы, которые перехватывают запросы к блочным устройствам и могут частично изменить поведение существующего драйвера этого устройства, например, зашифровать данные; драйверы портов, которые управляют конкретными адаптерами.
  Большое число уровней архитектуры файловой системы обеспечивает авторам драйверов устройств большую гибкость: драйвер может получить управление на любом этапе выполнения запроса – от вызова приложением функции, которая занимается работой с файлами, до того момента, когда работающий на самом низком уровне драйвер устройства начинает просматривать регистры контроллера. Многоуровневый механизм работы файловой системы реализован посредством цепочек вызова устройств. В ходе инициализации драйвер устройства может добавить себя к цепочке вызова некоторого устройства, определив при этом уровень последующего обращения. Подсистема ввода-вывода помещает адрес целевой функции в цепочку вызова устройства, используя заданный уровень для того, чтобы должным образом упорядочить цепочку. По мере выполнения запроса, подсистема ввода-вывода последовательно вызывает все функции, ранее помещенные в цепочку вызова. Внесенная в цепочку вызова процедура драйвера может передать запрос дальше – в измененном или в неизмененном виде – на следующий уровень, или, если это возможно, процедура может удовлетворить запрос, не передавая его дальше по цепочке.
 
 
 Резюме
 
  Функциями ОС по управлению памятью являются: отслеживание свободной и занятой памяти, выделение памяти процессам и освобождение памяти при завершении процессов, вытеснение процессов из оперативной памяти на диск и возвращение их в оперативную память, настройка адресов программы на конкретную область физической памяти.
  Для идентификации команд и переменных используются символьные имена (метки), виртуальные адреса и физические адреса.
  Самым простым способом управления оперативной памятью является разделение ее на несколько разделов фиксированной величины. При распределении памяти разделами переменной величины память ВМ заранее не делится на разделы и сначала вся оперативная память свободна. Каждому вновь поступающему процессу выделяется необходимая память.
  Эффективным методом управления памятью является применение механизма так называемой виртуальной памяти с использованием, например, дискового пространства. Наиболее распространенными способами реализации виртуальной памяти является страничное, сегментное и странично-сегментное распределение памяти, а также свопинг, когда некоторые процессы, находящиеся в состоянии ожидания, временно целиком выгружаются на диск.
  Память ВМ представляет собой иерархию запоминающих устройств, включающую внутренние регистры процессора, различные типы сверхоперативной, оперативной и постоянной памяти, внешнюю память на магнитных дисках и других типах устройств. Разные типы запоминающих устройств отличаются средним временем доступа и стоимостью хранения данных в расчете на один бит.
  Кэширование информации – это способ организации совместного функционирования двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения данных, который позволяет уменьшить среднее время доступа к данным за счет динамического копирования наиболее часто используемой информации из относительно более «медленного» ЗУ в более «быстрое» ЗУ (называемое кэш-памятью). Кэширование выполняется автоматически системными средствами.
 
  Одной из главных функций ОС является управление всеми устройствами ввода-вывода ВМ, а именно передача устройствам соответствующих команд, перехват прерываний, обработка ошибок, обеспечение интерфейса между устройствами ввода-вывода и остальной частью машины. Устройства ввода-вывода делятся на блок-ориентированные устройства (которые хранят информацию в блоках фиксированного размера и каждый блок имеет свой собственный адрес) и байт-ориентированные устройства (которые не адресуемы и не позволяют производить операцию поиска, а генерируют или потребляют последовательность байтов).
  Основная идея организации программного обеспечения ввода-вывода состоит в разбиении его на несколько уровней, причем нижние уровни обеспечивают экранирование особенностей аппаратуры от верхних, а те, в свою очередь, обеспечивают удобный интерфейс для пользователей. При этом ключевым принципом является как можно большая независимость программного обеспечения от конкретного типа устройства ввода-вывода. Весь зависимый от устройства программный код помещается в драйвер устройства. Каждый драйвер управляет устройствами одного типа или, может быть, одного класса.
  Устройства ввода-вывода могут быть разделяемыми, допускающими одновременный доступ нескольких пользователей к устройству (например, дисковые устройства), и выделенными, не допускающими одновременную работу с ними разными пользователями (например, устройства печати – принтеры).
  Для освобождения процессора от операций последовательного вывода данных из оперативной памяти или последовательного ввода в нее используется механизм прямого доступа внешних устройств к памяти – ПДП или DMA. При этом специальный контрол­лер DMA забирает у процессора управление локальной магистралью для выставления соответствующих сигналов за­писи информации в память или чтения информации из памяти на шины адреса, данных и управления. Контроллер DMA имеет несколько каналов DMA, которые мо­гут подключаться к различным устройствам ввода-вывода.
  Под файлом обычно понимают набор данных, организованных в виде совокупности записей одинаковой структуры. Для управления этими дан­ными создаются соответствующие системы управления файлами. Возможность иметь дело с логическим уровнем структуры данных и операций, выполняемых над ними в процессе их обработки, предоставляет файловая система. Файловая система – это набор спецификаций и соответствующее им про­граммное обеспечение, которые отвечают за создание, уничтожение, организацию, чтение, запись, модификацию и перемещение файловой информации, а также за управление доступом к файлам и за управление ресурсами, которые используют­ся файлами. Файлы идентифицируются символьными именами, которые дают им пользователи. При этом учитываются ограничения ОС как на используемые символы, так и на длину имени.
  Файлы подразделяются на обычные, специальные и файлы-каталоги. Обычные файлы в свою очередь подразделяются на текстовые и двоичные.
  Различают логическую и физическую организации файла. Логическая организация представляет файл в виде определенным образом организованных логических записей. Физическая организация файла описывает правила расположения файла на устройстве внешней памяти, в частности на диске.
  Информация на магнитных дисках размещается и передается бло­ками. В некоторых ОС такая наименьшая единица обмена называется кластером. При этом кластер может состоять из нескольких блоков.
  Наиболее известными способами физической организации файлов являются непрерывное размещение блоков данного файла на диске, размещение в виде связанного списка блоков дисковой памяти, использование связанного списка индексов, простое перечисление номеров блоков файла.
  В разных файловых системах может быть определен свой список прав доступа к файлам, то есть набор операций, которые пользователь может применить к данному файлу.
  Функционирование любой файловой системы можно представить многоуровневой моделью, в которой каждый уровень предоставляет некоторый интерфейс (набор функций) вышележащему уровню, а сам, в свою очередь, для выполнения своей работы использует интерфейс нижележащего уровня.
  Некоторые ОС обеспечивают отображение файлов в адресное пространство выполняемого процесса.
 
 
 
 
 Контрольные вопросы и задания
 
 Охарактеризуйте существующие методы управления оперативной памятью.
 Какие способы распределения виртуальной памяти чаще всего применяются, в чем их недостатки и преимущества?
 Укажите отличие блок-ориентированных устройств ввода-вывода от байт-ориентированных?
 В чем заключается смысл разбиения программного обеспечения ввода-вывода на несколько уровней?
 Приведите примеры разделяемых и выделенных устройств ввода-вывода.
 Опишите механизм прямого доступа устройств к памяти.
 Дайте определение понятиям «система управления файлами» и «файловая система».
 Какие функции в операционных системах выполняет система управления файлами?
 Опишите структуру магнитного диска.
 Дайте понятие логической организации файлов.
 Охарактеризуйте наиболее известные способы физической организации файлов.
 Какие уровни составляют многоуровневую модель функционирования файловой системы?
 3. Управление процессами и ресурсами в автономных многопроцессорных вычислительных машинах
 
 3.1. Реализация операционных систем многопроцессорных вычислительных машин
 
  В предыдущих разделах рассматривались вопросы реализации ОС, функционирующих на автономных (или так называемых «центра-лизованных») однопроцессорных ВМ. Для решения ряда сложных задач обработки информации спроектированы и практически используются многопроцессорные вычислительные машины (часто для краткости называемые «мультипроцессорами»), в которых устанавливается несколько центральных процессоров, имеющих полный доступ к общей разделяемой памяти. По своему основному содержанию операционные системы для таких многопроцессорных машин представляют собой обычные ОС, выполняющие традиционные функции по обработке системных вызовов, управлению памятью, обслуживанию файловой системы, управлению устройствами ввода-вывода. Главным отличием в реализации ОС для многопроцессорных ВМ является изменение содержания состояния процессов «выполнение». В этом состоянии может находиться не один процесс (как в однопроцессорных ВМ), а сразу несколько процессов, выполняющихся на разных процессорах многопроцессорной ВМ. Это требует более сложных алгоритмов планирования и синхронизации процессов, а также специфических методов организации и управления ресурсами в операционных системах для многопроцессорных ВМ.
  Возможны различные варианты организации операционных систем многопроцессорных машин.
  Простейший способ организации таких ОС состоит в том, чтобы статически разделить оперативную память по числу цент­ральных процессоров и дать каждому центральному процессору свою собственную память с собственной копией операционной системы. В результате N центральных процессоров будут работать как N независимых машин. В качестве оче­видного варианта оптимизации можно позволить всем центральным процессо­рам совместно использовать код операционной системы и хранить только ин­дивидуальные копии данных. Такая схема лучше, чем N независимых машин, так как она позволяет всем машинам совместно использовать набор дисков и других устройств ввода-вывода, а также обеспечивает гибкое совместное использование памяти. Например, если требуется запустить большую программу, одному из центральных процессоров может быть выделена большая порция памяти на время выполнения этой программы. Кроме того, процессы могут эффективно общаться друг с дру­гом, если одному процессу будет позволено писать данные в память, а другой про­цесс будет их считывать в этом месте. Но с точки зрения теории операционных систем наличие ОС у каждого центрального процессора является крайне примитивным подходом.
  Следует отметить следующие аспекты данной схемы.
  Во-первых, когда процесс обращается к системному вызову, системный вызов перехватывается и обрабатывается его собственным центральным процес­сором при помощи структур данных в таблицах операционной системы.
  Во-вторых, поскольку у каждой операционной системы есть свои собственные таблицы, у нее есть также и свой набор процессов, которые она сама планирует. Совместного использования процессов при этом нет. Если пользователь регистрируется на центральном процессоре 1, то и все его процессы работают на центральном процес­соре 1. В результате может случиться так, что центральный процессор 1 окажется загружен работой, тогда как центральный процессор 2 будет простаивать.
  В-третьих, совместного использования страниц также нет. Может случиться так, что у центрального процессора 2 много свободных страниц, в то время как центральный процессор 1 будет постоянно заниматься свопингом. При этом нет никакого способа занять свободные страницы у соседнего процессора, так как выделение памяти статически фиксировано.
  В-четвертых, (и этот аспект наиболее неприятен) если ОС поддерживавает буферный кэш недавно использованных дисковых блоков, то каждая операционная система будет выполнять это независимо от остальных. Таким образом, может случиться так, что некоторый блок диска будет присутствовать в нескольких буферах одновременно, причем в нескольких буферах сразу он может оказаться модифицированным, что приведет к порче данных на диске. Единственный способ избежать этого заключается в полном отказе от блочного кэша, что значительно снизит производительность системы.
  По причине приведенных выше соображений такая модель в настоящее время используется редко, хотя она применялась на первоначальном этапе становления многопроцессорных ВМ, когда преследовалась цель быстрого простого переноса существующих операционных систем на какой-либо новый мультипроцессор.
  При другом способе организации ОС для многопроцессорных ВМ используется всего одна копия операционной системы, работающая только на центральном процессоре 1. Все системные вызовы перенаправляются для обработки на центральный процессор 1. Центральный процессор 1 может также выполнять процессы пользователя, если у него будет оставаться для этого время. Такая схема называется «ведущий-ведомый», так как центральный процессор 1 является ведущим (или главным), а все остальные процессоры – или ведомыми (или подчиненными).
  Модель системы «ведущий-ведомый» позволяет решить большинство проблем первой модели. В этой модели используется единая структура дан­ных (например, один общий список или набор приоритетных списков), учитыва­ющая готовые процессы. Когда центральный процессор переходит в состояние простоя, он запрашивает у операционной системы процесс, который можно обра­батывать, и при наличии готовых процессов операционная система назначает этому процессору процесс. Поэтому при такой организации никогда не может случиться так, что один центральный процессор будет простаивать, в то время как другой центральный процессор перегружен. Страницы памяти могут динамически предоставляться всем процессам. Кроме того, в такой системе есть всего один общий буферный кэш блочных устройств, поэтому дискам не грозит порча данных, как в предыдущей модели при попытке использования блочного кэша.
  Недостаток этой модели состоит в том, что при большом количестве централь­ных процессоров «ведущий» может стать узким местом системы. Ведь ему приходится обрабатывать все системные вызовы от всех центральных процессоров. Следова­тельно, такая модель проста и работоспособна для небольших мультипроцессоров, но на машинах с относительно большим числом процессоров она будет работать крайне неэффективно.
  Третья модель, представляющая собой модель так называемых «симметричных мультипроцессоров» SMP (Symmetric Multiprocessor), позволяет устранить недостатки вышеописанной модели. Как и в предыдущей схеме, в данной модели в памяти находится всего одна копия операционной сис­темы, но выполнять ее может любой процессор. При системном вызове на цент­ральном процессоре, обратившемся к системе с системным вызовом, происходит прерывание с переходом в режим ядра и обработкой системного вызова. При этом модель обеспечивает динамический баланс процессов и памяти, поскольку в ней имеется всего один набор таблиц операционной системы. Она также позво­ляет избежать простоя системы, связанного с перегрузкой ведущего центрального процессора, так как в ней его нет. И все же данная модель имеет собственные проблемы. В частности, если код опе­рационной системы будет выполняться одновременно на двух или более центральных процессорах, произойдет «катастрофа» (например, если два центральных про­цессора одновременно берут один и тот же процесс для запуска или запраши­вают одну и ту же свободную страницу памяти).
  Простейший способ разреше­ния подобных проблем заключается в связывании мьютекса (то есть блокировки) с ОС, в результате чего вся система превращается в одну боль­шую критическую область. Когда центральный процессор хочет выполнять код операционной системы, он должен сначала получить мьютекс. Если мьютекс за­блокирован, процессор вынужден ждать. Таким образом, любой центральный про­цессор может выполнить код операционной системы, но в каждый момент време­ни только один из них будет делать это.
  Существенными недостатками такой модели при наличии уже более десяти центральных процессоров являются значительные по времени простои процессоров в длинных очередях в ожидании разрешения доступа к мьютексу. Эта проблема разрешается следующим образом. Так как многие части ОС независимы друг от друга (например, один центральный процессор может заниматься планированием, в то время как другой центральный процессор будет выполнять обращение к файловой системе, а третий обрабатывать страничное прерывание), возможно произвести «расщепление» операционной системы на неза­висимые критические области, не взаимодействующие друг с другом. В этом случае у каждой критической области есть свой мьютекс, поэтому только один центральный процес­сор может выполнять ее в каждый момент времени. Таким образом можно достичь большей степени распараллеливания. Однако может случиться, что некоторые таб­лицы, например таблица процессов, используются в нескольких критических облас­тях. Например, таблица процессов требуется для планирования, но также для выполнения системного вызова и для обработки сигналов. Тогда для каждой таблицы, исполь­зующейся несколькими критическими областями, назначается свой собственный мьютекс. В результате этого, в каждый момент времени каждая критическая область может вы­полняться только одним центральным процессором, а к каждой таблице может быть предоставлен доступ только одному центральному процессору.
  Подобная организация используется в большинстве современных многопроцессорных ВМ. Сложность написания ОС для таких машин заключается не в том, что программный код сильно отличается от обычной операци­онной системы. Самым сложным является расщепление операционной сис­темы на критические области, которые могут выполняться параллельно на разных центральных процессорах, не мешая друг другу даже косвенно. Кроме того, каж­дая таблица, используемая двумя и более критическими областями, должна быть отдельно защищена мьютексом, а все программы, пользующиеся этой таблицей, должны корректно использовать мьютекс. Следует также уделить особое внимание вопросу избежания взаимобло­кировок. Если двум критическим областям потребуются таблица А и таблица В, то рано или поздно возникнет взаимоблокировка, причину появления которой будет очень трудно определить. Теоретически всем таблицам можно поставить в соответствие целые числа и потребовать от всех критических областей запрашивать эти таблицы по порядку номеров. Такая стратегия позволяет избежать взаимоблокировок, но она требует от программиста детального исследования того, какие таблицы потребу­ются каждой критической области, чтобы запросить их в правильном порядке. При изменении программы критической области может потребо­ваться новая таблица, которая не была нужна ранее. Этот факт также должен быть корректно учтен программистом, чтобы избежать взаимоблокировок, выглядящих с точки зрения пользователя как «зависание» системы.
 3.2. Планирование и синхронизация в многопроцессорных вычислительных машинах
 
  На однопроцессорной ВМ планирование одномерно. Единственный вопрос, на который должен быть каждый раз получен ответ, – какой процесс должен быть запущен следующим? На мультипроцессоре планирование двумерно. Планировщик должен решить, какой процесс и на котором центральном процессоре запустить. Это дополнительное измерение существенно усложняет планирование процессов на многопроцессорных ВМ. Другой усложняющий фактор состоит в том, что в ряде случаев все процессы являются независимыми, тогда как в других случаях они формируют груп­пы.
  Рассмотрим планирование независимых процессов.
  Простейший алгоритм планирова­ния независимых процессов (или потоков) состоит в поддержании единой струк­туры данных для готовых процессов, возможно, просто списка, но скорее всего множества списков для процессов с различными приоритетами. Наличие единой структуры данных планирования, используемой всеми цент­ральными процессорами, обеспечивает процессорам режим разделения времени подобно тому, как это выполняется на однопроцессорной системе. Кроме того, та­кая организация позволяет автоматически балансировать нагрузку, то есть она исключает ситуацию, при которой один центральный процессор простаивает, в то время как другие процессоры перегружены. Два недостатка такой схемы представ­ляют собой, во-первых, потенциальный рост конкуренции за структуру данных планирования по мере увеличения числа центральных процессоров и, во-вторых, наличие обычных накладных расхо­дов на выполнение переключения контекста, когда процесс блокируется, ожидая выполнения операции ввода-вывода. Переключение контекста также может случиться, когда истекает квант времени про­цесса.
  Мультипроцессоры обладает рядом определенных свойств, которые отсутствуют в однопроцессорных ВМ. Например, на мультипроцессорax часто встречается удержание процессом спин-блокировки. При этом другие центральные процессоры, ждущие освобождения спин-блокировки, просто теряют время в циклах ожидания, пока этот процесс не будет запущен снова и не отпустит блокировку. В однопроцессорных ВМ спин-блокировка применяется редко. Поэтому если процесс, удерживающий мьютекс, блокируется и запускается другой процесс, то при попытке заполучить мьютекс второй процесс будет тут же блокирован, и много времени потеряно не будет.
  Чтобы решить данную проблему, в некоторых системах применяется так называемое «умное» планирование, при котором процесс, захватывающий спин-блокировку, устанавливает флаг, демонстрирующий, что он в данный момент обладает спин-блокировкой. Когда процесс освобождает спин-блокировку, он также очищает и флаг. Таким образом, планировщик не останавливает процесс, удерживающий спин-блокировку, а, напротив, дает ему еще немного времени, чтобы тот завершил выполнение критической области и отпустил мьютекс.
  Другая проблема, играющая важную роль в планировании, заключается в том факте, что хотя все центральные процессоры равны, но некоторые центральные процессоры как бы «равнее» других. В частности, когда процесс А достаточно долго работает на центральном процессоре K, кэш процессора K будет во многом заполнен блоками процесса А. Если процесс А должен быть снова вскоре запущен, его производительность может оказаться выше, если он будет запущен опять на центральном процессоре K, так как кэш процессора K может все еще содержать некоторые блоки процесса А. Наличие блоков в кэше увеличит частоту попаданий в кэш и, таким образом, увеличит скорость выполнения процесса. Кроме того, буфер ассоциативной памяти также может содержать «правильные» страницы памяти, что снизит количество прерываний из-за ошибок буфера. Некоторые мультипроцессорные ОС учитывают данные соображения и используют так называемое «родственное планирование». Основная идея этого метода заключается в приложении серьезных усилий для того, чтобы процесс был запущен на том же центральном процессоре, что и в прошлый раз. Один из способов реализации этого метода состоит в использовании двухуровневого алгоритмам планирования. В момент создания процесс назначается конкретному центральному процессору, например, наименее загруженному в данный момент. Такое назначение процессов процессорам представляет собой верхний уровень алгоритма. В результате каждый центральный процессор получает свой набор процессов. Действительное планирование процессов находится на нижнем уровне алгоритма. Оно выполняется отдельно каждым центральным процессором при помощи приоритетов или других средств. Старания удерживать процессы на одном и том же центральном процессоре максимизируют родственность кэша. Однако если у какого-либо центрального процессора нет работы, у загруженного работой процессора отнимается процесс и отдается ему.
  Двухуровневое планирование обладает тремя преимуществами. Во-первых, оно довольно равномерно распределяет нагрузку среди имеющихся центральных процессоров. Во-вторых, двухуровневое планирование по возможности использует преимущество родственности кэша. В-третьих, поскольку у каждого центрального процессора при таком варианте планирования есть свой собственный список свободных процессов, конкуренция за списки свободных процессов минимизируется, так как попытки использования списка другого процессора происходят относительно редко.
  Другой подход к планированию мультипроцессоров может быть использован, если процессы связаны друг с другом каким-либо способом. Часто также случается, что один процесс создает множество потоков, работающих совместно. Для нашего рассмотрения задание, состоящее из нескольких связанных процессов, или процесс, состоящий из нескольких потоков, представляют собой, по сути, одно и то же. Будем называть планируемые объекты потоками, но все сказанное здесь в равной мере справедливо и для процессов. Планирование нескольких потоков на нескольких центральных процессорах называется совместным использованием пространства или разделением пространства.
  Простейший алгоритм разделения пространства работает следующим образом. Предположим, что сразу создается целая группа связанных потоков. В момент их создания планировщик проверяет, есть ли свободные центральные процессоры по количеству создаваемых потоков. Если свободных процессоров достаточно, каж­дому потоку выделяется собственный центральный процессор (то есть работающий в однозадачном режи­ме), и все потоки запускаются. Если процессоров недо­статочно, ни один из потоков не запускается, пока не освободится достаточное количество центральных процессоров. Каждый поток выполняется на своем про­цессоре вплоть до завершения, после чего все центральные процессоры возвраща­ются в пул свободных процессоров. Если поток оказывается заблокированным операцией ввода-вывода, он продолжает удерживать центральный процессор, который простаивает до тех пор, пока поток не сможет продолжать свою работу. При появлении следующего пакета потоков применяется тот же алгоритм. В любой момент времени множество центральных процессоров статически раз­деляется па несколько подмножеств, на каждом из которых выполняются потоки одного процесса. Со временем, по мере завершения работы одних процессов и появления новых процессов, количество и размеры групп центральных процессоров изменяются.
  Очевидное преимущество разделения пространства заключается в устраненении многозадачности, что снижает накладные расходы по переключению контекста. Однако ее недостаток состоит в потерях времени при блокировке центральных процессоров. С целью устранения проблем описанного выше метода проводятся активные поиски алгоритмов, способных планировать одновременно в пространстве и времени, особенно для процессов, создающих большое количество потоков, которым, как правило, требуется возможность общения друг с другом. Известные разработки в этом направлении представляют собой достаточно сложные алгоритмы и их рассмотрение выходит за рамки данного учебного пособия.
  В многопроцессорных ВМ часто требуется синхронизация центральных процессоров, реализация которой в этом случае далеко не тривиальна.
  Если процесс в однопроцессорной ВМ обращается к системному вызову, ко­торый требует доступа к некой критической таблице, программа ядра может про­сто запретить прерывания, прежде чем обратиться к таблице. Однако на мульти­процессоре запрет прерывания повлияет только на один центральный процессор, выполнивший команду запрета прерываний. Остальные центральные процессоры продолжат свою работу и смогут получить доступ к критической таблице. Требу­ется специальный мьютекс-протокол, который будет выполняться всеми централь­ными процессорами, чтобы гарантировать работу взаимного исключения.
  Основой любого практического мьютекс-протокола является команда процессо­ра, позволяющая исследовать и изменить слово в памяти за одну операцию. Для этого можно использовать команду TSL (Test and Set Lock – проверить и установить блокировку), которая считывает слово памяти в регистр процессора. Одновременно она записывает 1 (или другое ненулевое значение) в слово памяти. Конечно, для выполнения операций чтения и записи памяти требуется два цикла шины. В однопроцессорной ВМ, поскольку одна команда процессора не мо­жет быть прервана на полпути, команда TSL работает должным образом. Для решения проблемы взаимного исключения в многопроцессорной ВМ команда TSL сначала должна блокировать шину, не допуская обращения к ней других центральных процессоров, затем выполнить оба обращения к памяти, после чего разблокировать шину. Как правило, для блоки­ровки шины сначала выполняется обычный запрос шины по стандартному прото­колу, затем устанавливается в 1 некая специальная линия шины. Пока эта линия шины установлена в 1, никакой другой центральный процессор не может получить к ней доступ. Такая команда может быть выполнена только на шине, у которой есть необходимые специальные линии и аппаратный протокол для их использования (современные шины обладают подобными свойствами). Если команда TSL корректно реализована и применяется, она гарантирует пра­вильную работу взаимного исключения. Однако подобный способ реализации взаимного исключения использует спин-блокировку, так как запрашивающий центральный процессор находится в цикле опроса блокировки с максимальной скоростью. Этот метод является не только тратой времени запрашивающего цент­рального процессора (или процессоров), но он также может накладывать значительную нагрузку на шину или память, существенно снижая скорость работы всех остальных центральных процессоров, пытающихся выполнять свою обычную работу.
  Наличие кэширования не устра­няет проблему конкуренции за шину. Теоретически, как только за­прашивающий центральный процессор прочитал слово блокировки, он должен по­лучить его копию в свой кэш. Пока ни один другой центральный процессор не предпринимает попыток использовать это слово, запрашивающий центральный процессор может работать с ним в своем кэше. Когда центральный процессор, владеющий словом блокировки, записывает в него 1, протокол кэша автомати­чески помечает как недействитель-ные все копии этого слова в удаленных кэшах, требуя получения правильных значений. Однако проблема заключается в том, что кэш оперирует блоками по 32 или 64 байт. Обычно слова, окружающие слово блокировки, нужны центральному процессору, удерживающему это слово. Поскольку команда TSL представляет собой запись (так как она модифицирует слово блокировки), ей требуется монопольный доступ к блоку кэша, содержащему слово блокировки. Таким образом, каждая команда TSL помечает блок кэша владельца блокировки как недействительный и получает при­ватную, эксклюзивную копию для запрашивающего центрального процессора. Как только владелец блокировки изменит слово, соседнее с блокировкой, блок кэша перемещается на его процессор. В результате весь блок кэша, содержащий слово блокировки, постоянно челночно перемещается от центрального про­цессора, удерживающего блокировку, к центральному процессору, пытающемуся ее получить. Все это создает довольно значительный и совершенно излишний трафик шины.
  Проблему можно было бы решить, если бы удалось избавиться от всех опера­ций записи, вызванных командой TSL запрашивающей стороны. Это можно сделать, если запрашивающая сторона сначала будет выполнять простую операцию чтения, чтобы убедиться, что мьютекс свободен. Только убедившись, что он свободен, цен­тральный процессор выполняет команду TSL, чтобы захватить его. В результате большинство операций опроса представляют собой операции чтения, а не опера­ции записи. Когда мьютекс считан, владелец выполняет операцию записи, для чего требуется монопольный доступ. При этом все остальные копии этого блока кэша объявляются недействительными. При следующей операции чтения запрашива­ющий центральный процессор перезагрузит этот блок кэша. При одновременном споре двух центральных процессоров за один и тот же мьютекс может случиться, что они одновременно увидят, что мьютекс свободен, и одновременно выполнят команду TSL. Ничего катастрофичного в этом случае не про­изойдет, так как выполнена будет только одна команда TSL и такая ситуация не приведет к состоянию состязания.
  Другой способ снижения шинного трафика заключается в использовании алгоритма так называемого двоичного экспоненциального отката, применяемого в сетевой технологии Ethernet. Вместо постоянного опроса, о чем было сказано ранее, между опросами может быть вставлен цикл задержки. Вначале задержка представляет собой одну команду. Если мьютекс занят, задержка удваивается, учетверяется и т.д. до некоторого мак­симального уровня. При низком уровне получается быстрая реакция при осво­бождении мьютекса, зато требуется больше обращений к шине для чтения бло­ка кэша. Высокий максимальный уровень позволяет уменьшить число лишних обращений к шине за счет более медленной реакции программы на освобождение мьютекса. Использование алгоритма двоичного экспоненциального отката не за­висит от применения операций чистого чтения перед командой TSL.
  Еще более эффективный способ заключается в том, чтобы каждому центральному про­цессору, желающему заполучить мьютекс, позволить опрашивать свою собствен­ную переменную блокировки. Во избежание конфликтов перемен­ная должна располагаться в не используемом для других целей блоке кэша. Работа алгоритма состоит в том, что центральный процессор, которому не удается запо­лучить мьютекс, захватывает переменную блокировки и присоединяется к концу списка центральных процессоров, ожидающих освобождения мьютекса. Когда цен­тральный процессор, удерживающий мьютекс, покидает критическую область, он освобождает приватную переменную, проверяемую первым центральным процес­сором в списке (в его собственном кэше). Тем самым следующий центральный процессор получает возможность войти в критическую область. Покинув крити­ческую область, этот процессор освобождает переменную блокировки, тестируе­мую следующим процессором и т.д. Хотя такой протокол несколько сложен (это необходимо, чтобы не допустить одновременного присоединения двух централь­ных процессоров к концу списка), однако его практическое применение достаточно результативно.
  До сих пор предполагалось, что центральный процессор, которому требуется мьютекс, просто ждет, пока тот не освободится, опрашивая его состояние посто­янно или периодически, либо присоединяясь к списку ожидающих процессоров. В некоторых случая альтернативы простому ожиданию нет. Например, какой-либо центральный процессор простаивает и ему нужен доступ к общему списку готовых процессов, чтобы выбрать оттуда процесс и запустить его. Если список готовых процессов заблокирован, простаивающему центральному процессору будет просто более нечем себя занять. Он должен ждать, пока список готовых процессов не освободится. Однако в некоторых случаях у процессора может быть выбор. Например, если какому-либо потоку на центральном процессоре потребуется доступ к блочному кэшу файловой системы, заблокированному в данный момент, центральный про­цессор может решить не ждать, а переключиться на другой поток. Вопрос приня­тия решения о том, ждать или переключиться на другой поток, в однопроцессорной ОС не возника­ет, так как опрос в цикле ни имеет смысла при отсутствии другого центрального процессора, способного освободить мьютекс. Если поток пытается получить мьютекс и ему это не удается, он всегда блокируется, чтобы дать возможность владельцу мьютекса работать и освободить мьютекс.
  Если допустить, что оба варианта (опрос в цикле и переключение потоков) вы­полнимы, возникает следующая ситуация. Циклический опрос напрямую расхо­дует процессорное время. Периодическая проверка состояния мьютекса не явля­ется продуктивной работой. Переключение процессов, однако, также расходует циклы процессора, так как для этого требуется сохранить текущее состояние пото­ка, получить мьютекс списка свободных процессов, выбрать из этого списка поток, загрузить его состояние и передать ему управление. Более того, кэш центрального процессора будет содержать не те блоки, поэтому после переключения потоков возможно много промахов кэша. Также вероятны ошибки TLB. Наконец, потре­буется переключение обратно на исходный поток, результатом которого снова бу­дут промахи кэша. Циклы процессора, потраченные на эти два переключения кон­текста, плюс промахи кэша представляют собой существенные накладные расходы.
  Одно из решений этой проблемы заключается в том, чтобы всегда использовать циклический оп­рос. Вторым подходом является использование только переключений. Третий ва­риант состоит в том, чтобы каждый раз принимать отдельное решение. В момент принятия решения не известно, что лучше – переключаться или ждать, но в лю­бой системе можно отследить активность процессов и затем проанализировать ее в автономном режиме. При этом можно сказать, какое решение было бы лучшим в том или ином случае и сколько процессорного времени было потрачено. Таким образом, ретроспективный алгоритм становится эталоном, относительно которо­го может измеряться эффективность реальных алгоритмов.
  Другим способом разрешения указанной проблемы является использование модели, в которой поток, не заполучивший мьютекс, какое-то время опрашивает состояние мьютекса в цикле. Если пороговое значение времени ожидания превышается, он переключается. В некоторых случаях пороговое зна­чение фиксировано, как правило, оно равно известному времени, требующемуся на переключение на другой поток и обратно. В других случаях эта величина меня­ется динамически, в зависимости от истории состояния ожидаемого мьютекса. Лучшие результаты достигаются тогда, когда система учитывает несколько по­следних интервалов ожидания и предполагает, что следующий интервал ожидания будет близок по величине к предыдущим.
 
 
 
 
 
 
 
 
 
 Резюме
 
  По своему основному содержанию операционные системы для многопроцессорных ВМ представляют собой обычные ОС, выполняющие традиционные функции по обработке системных вызовов, управлению памятью, обслуживанию файловой системы, управлению устройствами ввода-вывода. Главным отличием в реализации ОС для многопроцессорных ВМ является изменение содержания состояния «выполнение» процессов. В этом состоянии может находиться не один процесс (как в однопроцессорных ВМ), а сразу несколько процессов, выполняющихся на разных процессорах многопроцессорной ВМ.
  Простейший способ организации таких ОС состоит в том, чтобы статически разделить оперативную память по числу цент­ральных процессоров и дать каждому центральному процессору свою собственную память с собственной копией операционной системы. Такой примитивный подход обладает рядом существенных недостатков и в настоящее время используется редко, хотя широко применялся на первоначальном этапе становления многопроцессорных ВМ.
  При другом способе организации ОС для многопроцессорных ВМ используется всего одна копия операционной системы, работающая только на одном центральном процессоре, называемом «ведущим». Все системные вызовы перенаправляются для обработки на этот центральный процессор. Остальные процессоры в этой схеме – «ведомые». Такая модель системы позволяет решить большинство проблем предыдущего способа организации ОС, но ее недостаток состоит в том, что при относительно большом количестве централь­ных процессоров «ведущий» может стать узким местом всей системы.
  Устранить эти недостатки позволяет схема, при которой в памяти также находится всего одна копия ОС, но выполнять ее может любой процессор. Эта модель обеспечивает динамический баланс процессов и памяти, поскольку в ней имеется всего один набор таблиц ОС.
  Способ разреше­ния указанных выше проблем состоит в связывании мьютекса (то есть блокировки) с ОС, в результате чего вся система превращается в одну боль­шую критическую область. Эффективным механизмом также является «расщепление» ОС на неза­висимые критические области, не взаимодействующие друг с другом.
  Сложность планирования процессов в многопроцессорной ВМ заключается в том, что планировщик решает вопросы не только очередности запуска процессов на выполнение, но и выбора центрального процессора, на котором должен быть запущен тот или иной процесс. Другим фактором, усложняющим планирование, является то, что в ряде случаев все процессы являются независимыми, тогда как в других случаях они формируют груп­пы.
  Простейший алгоритм планирова­ния независимых процессов – поддержание единой струк­туры данных для готовых процессов.
  В многопроцессорных ВМ часто встречается удержание процессом спин-блокировки. Чтобы решить данную проблему, в некоторых системах планировщик не останавливает процесс, удерживающий спин-блокировку, а, напротив, дает ему еще немного времени, чтобы тот завершил выполнение критической области и отпустил мьютекс.
  Для увеличения скорости выполнения процессов применяется двухуровневый алгоритм планирования, удерживающий выполнение процессов на одном и том же центральном процессоре, что позволяет прежде всего использовать преимущество «родственности» содержимого кэш-памяти.
  При планировании процессов, связанных друг с другом каким-либо способом, используется алгоритм «совместного использования (или разделения) пространства».
  Для синхронизации центральных процессоров в многопроцессорных ВМ применяется специальный мьютекс-протокол, основой которого является команда процессо­ра TSL, позволяющая проверить и установить блокировку. Один из способов снижения существенного шинного трафика, неизбежно создаваемого командой TSL, заключается в использовании алгоритма двоичного экспоненциального отката, применяемого в сетевых технологиях. Более эффективный способ состоит в том, чтобы каждому центральному про­цессору, желающему заполучить мьютекс, позволить опрашивать свою собствен­ную переменную блокировки.
  Важной проблемой планирования и синхронизации процессов в многопроцессорных ВМ является решение вопроса ожидания освобождения мьютекса или переключения на другой поток. Одно из решений этой проблемы заключается в том, чтобы всегда использовать циклический оп­рос. Вторым подходом является использование только переключений. Третий ва­риант состоит в том, чтобы каждый раз принимать, по-возможности, наиболее эффективное решение.
 
 Контрольные вопросы и задания
 
 1. В чем заключается основное отличие в реализации ОС для многопроцессорных ВМ от ОС однопроцессорных ВМ?
 2. Охарактеризуйте особенности функционирования ОС многопроцессорных ВМ, организованных путем статического разделения оперативной памяти по числу цент­ральных процессоров и выделении каждому центральному процессору собственной копии ОС.
 3. Какими достоинствами и недостатками обладает способ организации ОС многопроцессорных ВМ по схеме «ведущий-ведомый»?
 4. Опишите механизмы преодоления проблем в модели реализации ОС многопроцессорных ВМ, позволяющей любому процессору выполнять процедуры единственной копии операционной сис­темы, находящейся в памяти.
 5. Какие факторы усложняют планирование процессов в многопроцессорных ВМ по сравнению с аналогичным планированием в однопроцессорных машинах?
 6. Какой механизм применяется для преодоления удержания процессом спин-блокировки?
 7. Представьте достоинства использования двухуровневого алгоритма планирования процессов в многопроцессорных ВМ.
 8. Опишите алгоритм «совместного использования пространства», его преимущества и недостатки.
 9. Каким образом выполняется синхронизация центральных процессоров в многопроцессорных ВМ?
 
 
 
 
 
 
 
 
 
 
 4. Управление процессами и ресурсами
 в многомашинных вычислительных системах
 
 4.1. Способы организации управления процессами
 и ресурсами в многомашинных вычислительных системах
 
  Одним из эффективнейших направлений развития вычислитель-ной техники стало построение так называемых многомашинных вычислительных систем (далее – ММВС). Принципиальным отличием ММВС от многопроцессорных ВМ является то, что каждая машина, входящая в состав ММВС, имеет свою собственную оперативную память. Всю совокупность ММВС обычно разделяют на два крайних по архитектуре класса, которые до сих пор не имеют общепринятого и устоявшегося наименования. Несмотря на отсутствие единой терминологии, один из этих классов чаще всего называют классом «многомашинных вычислительных систем сосредоточенного типа», а другой – классом «многомашинных вычислительных систем распределенного типа» или «распределенных вычислительных систем».
  Под ММВС сосредоточенного типа понимают многомодульную (или многоузловую) систему, каждый модуль которой включает центральный процессор, оперативную память, интерфейсное устройство и, возможно, дисковую память для свопинга. Такие модули обычно называют «вычислительными модулями». Все вычислительные модули, как правило, имеют общие периферийные устройства. Для связи отдельных модулей (узлов) используются выделенные интерфейсные линии. Вся система чаще всего располагается в одном помещении и администрируется одной организацией. Такие системы в свою очередь принято подразделять на два типа: «кластер­ные системы» (claster – гроздь), которые состоят из нескольких единиц или десятков (как правило, не более четырех десятков) модулей, и «массово-паралллельные вычислительные системы» или «массивно-параллельные системы» MPP (Massive parallel processing), которые включают более 100 единиц вычислительных модулей. Основными ком­понентами таких систем, то есть отдельными вычислительными модулями чаще всего являются «усеченные» варианты обычных ВМ.
  ММВС распределенного типа или распределенные вычислительные системы имеют существенное сходство с ММВС сосредоточенного типа в том, что в них также нет общей физической памяти, а у каждого узла есть своя па­мять. Но в отличие от ММВС сосредоточенного типа, узлы распределенной вычислительной системы связаны друг с другом не столь жестко. Кроме того, узел распределенной системы, как правило, представляет собой полноценную ВМ с полным набором пери­ферийных устройств. Узлы распределенной системы могут располагаться на значительном расстоянии друг от друга, в пределе, по всему миру, и администрироваться разными организациями. Наиболее ярким примером распределенной системы является Интернет. Распределенные вычислительные системы обычно называют вычислительными (или компьютерными) сетями.
  Важнейшим отличием ММВС от автономных (централизованных) ВМ является способ организации межпроцессной взаимосвязи. В автономных машинах связь между процессами, как правило, предполагает наличие общей разделяемой памяти. В ММВС (при отсутствии какой бы то ни было разделяемой памяти) основой межпроцессного взаимодействия может служить только передача по сети так называемых сообщений посредством некоторой коммуникационной среды. Сообщение представляет собой некоторый блок информации, отформатированный процессом-отправителем таким образом, чтобы он был понятен процессу-получателю.
  Итак, процессы на разных центральных процессорах ММВС общают­ся, отправляя друг другу сообщения. В своем простейшем виде этим обменом сооб­щениями явно занимаются процессы пользователя. Другими словами, операционная система предоставляет способ отправки и получения сообщения, а библиотечные процедуры обеспечивают доступность этих системных вызовов для пользователь­ских процессов.
  Таким образом, в самом простом случае системные средства обеспечения связи могут быть сведены к двум основным системным вызовам (примитивам): один – для отправки сообщения, другой – для получения сообщения. Соответствующие библиотечные процедуры могут иметь следующий формат:
  1) вызов для отправки сообщения send(dest, &mptr);
  2) вызов для получения сообщения receive(addr, &mptr).
  Первая процедура посылает сообщение, на которое указывает указатель mptr, процессу dest (идентификатор процесса) и блокирует вызывающий ее процесс до тех пор, пока сообщение не будет отправлено. Вторая процедура вызывает блоки­ровку процесса вплоть до получения сообщения. Когда сообщение приходит, оно копируется в буфер, на который указывает mptr, и процесс, вызвавший эту биб­лиотечную процедуру, разблокируется. Параметр addr указывает адрес, от кото­рого вызывающий процесс ожидает прихода сообщения.
  Отметим, что возможны различные варианты этих двух процедур и их параметров.
  Описанные выше вызовы представляют собой блокирующие вызовы (иногда на­зываемые синхронными вызовами). Когда процесс обращается к процедуре send, он указывает адресат и буфер, данные из которого следует послать указанному адресату. Пока сообщение посылается, передающий процесс блокирован (то есть приостановлен). Команда, следующая за обращением к процедуре send, не выпол­няется до тех пор, пока все сообщение не будет послано. Аналогично, обращение к процедуре receive не возвращает управления, пока сообщение не бу­дет получено целиком и положено в буфер, адрес которого указан в параметре. Процесс остается приостановленным, пока не прибудет сообщение, даже если на это уйдет несколько часов. В некоторых системах получатель может указать, от кого именно он ожидает прихода сообщения. В этом случае процесс будет блоки­рован, пока не прибудет сообщение от указанного отправителя.
  Альтернативу блокирующим вызовам составляют неблокирующие вызовы (иногда называемые асинхронными вызовами). Если процедура send является неблокирующей, то она возвращает управление вызывающему ее процессу прак­тически немедленно, прежде чем сообщение будет отправлено. Преимущество этой схемы состоит в том, что отправляющий процесс может продолжать вычисления параллельно с передачей сообщения, что позволяет избежать простоя централь­ного процессора (при условии, что других готовых к работе процессов нет). Выбор между блокирующим и неблокирующим примитивами обычно делается проекти­ровщиками системы (то есть, как правило, доступен либо один примитив, либо другой), хотя в некоторых системах бывают доступны оба примитива и право вы­бора предоставляется пользователю.
  Однако помимо преимущества высокой производительности, с неблокирующи­ми примитивами связана более сложная организация программы. Отправителю нельзя изменять содержимое буфера сообщения до тех пор, пока это сообщение не будет полностью отправлено. Более того, если у отправляющего процесса нет возможности узнать, что передача уже выполнена, то он никогда не будет уверен, можно ли уже пользоваться буфером.
 
  Возможны три метода решения этой проблемы. Первое решение заключается в копировании ядром сообщения в свой буфер, после чего процессу позволяется продолжать работу. С точки зрения отправителя эта схема аналогич­на блокирующему вызову, потому что как только отправитель получает управление, он может снова пользоваться буфером. Разумеется, сообщение еще не будет от­правлено, но отправителю это не мешает. Недостаток этого метода состоит в необ­ходимости копирования каждого исходящего сообщения из пространства пользо­вателя в буфер ядра. Во многих сетевых интерфейсах сообщение все равно будет скопировано в аппаратный буфер передачи, поэтому первое копирование пред­ставляет собой просто потерю времени. Лишняя операция копирования может существенно снизить производительность системы.
  Второе решение заключается в прерывании отправителя, когда сообщение будет отправлено, чтобы известить его об этом факте. В этом случае операции копиро­вания не требуется, что сохраняет время, но прерывания на уровне пользователя значительно усложняют программы и могут привести к внутренним конфликтам в программе, в результате чего такие программы будет почти невозможно отладить.
  Третье решение состоит в том, чтобы копировать содержимое буфера при за­писи. Буфер помечается как доступный только для чтения до тех пор, пока сооб­щение не будет отправлено. Если буфер используется повторно прежде, чем будет отправлено сообщение, создается копия буфера. Недостаток этого варианта за­ключается в том, что если только буферу не выделена целиком собственная страни­ца, операции записи с соседними переменными также будут вызывать копирова­ние страницы. Кроме того, потребуются дополнительные административные меры, так как теперь отправка сообщения неявно изменяет статус чтения-записи стра­ницы. Наконец, раньше или позже, страница опять может быть записана, что при­ведет к появлению еще одной копии страницы.
  Таким образом, у отправителя имеется следующий выбор:
  1. Блокирующая операция send (центральный процессор простаивает во вре­мя передачи сообщения).
  2. Неблокирующая операция send с копированием (время центрального про­цессора теряется на создание дополнительной копии).
  3. Неблокирующая операция send с прерыванием (усложняет программу).
  4. Копирование при записи (в конечном итоге требуется дополнительная опе­рация копирования).
  Первый вариант является лучшим, особенно при наличии нескольких потоков. Пока один поток блокирован, ожидая отправ­ки сообщения, остальные потоки могут продолжать работу. Для этого метода также не требуется буфера в ядре, а передача сообщения занимает меньше времени, если не требуется дополнительного копирования.
  Еще один способ заключается в том, что при прибытии сообщения в адресном пространстве получающего процесса создается новый поток. Такой поток называется всплывающим или временным потоком. Он выполняет заранее указанную процедуру, в качестве параметра которой передается указатель на прибывшее сообщение. После обработки сообщения этот процесс просто прекращает свое существование.
  Вариантом этой идеи является запуск программы получателя прямо в обработ­чике прерываний, что позволяет избежать создания временного потока. Чтобы еще ускорить эту схему, в само сообщение можно включить адрес обработ­чика, поэтому, когда оно прибудет, обработчик будет вызван с помощью всего не­скольких команд процессора. Большой выигрыш данной схемы заключается в том, что копирование вообще не нужно. Обработчик получает сообщение от интерфейс­ной платы и обрабатывает его на лету. Такая схема называется «активными сооб­щениями». Поскольку каждое сообщение содержит адрес обработчика, эта схема может работать только в том случае, когда отправители и получатели пол­ностью доверяют друг другу.
  В более сложной форме, чем рассмотрено выше, передача сообщений скрыта от пользовате­ля под видом вызова удаленной процедуры RPC (Remote Procedure Call).
  Идея вызова удаленных процедур состоит в расширении хорошо известного механизма передачи управления и данных внутри программы, выполняющейся на одной ВМ, на передачу управления и данных через коммуникационные каналы, связывающие разные ВМ. Другими словами, программам разрешается вызывать процедуры, расположенные на других ВМ. Когда процесс на ВМ 1 вызывает процедуру на ВМ 2, вызывающий процесс на ВМ 1 приостанавливается, а на ВМ 2 выполняется вызванная процедура. Информация между вызывающим процессом и вызываемой процедурой может передаваться через параметры, а также возвращаться в результате процедуры.
  Средства вызова удаленных процедур предназначены для облегчения организации распределенных вычислений. Наибольшая эффективность использования RPC достигается в тех приложениях, в которых существует интерактивная связь между удаленными компонентами с небольшим временем ответов и относительно малым количеством передаваемых данных. Такие приложения называют RPC-ориентированными.
  Реализация удаленных вызовов существенно сложнее реализации вызовов локальных процедур. Для вызова локальных процедур характерны асимметричность (то есть одна из взаимодействующих сторон является инициатором) и синхронность (то есть выполнение вызывающей процедуры приостанавливается с момента выдачи запроса и возобновляется только после возврата из вызываемой процедуры).
  При удаленных вызовах вызывающая и вызываемая процедуры выполняются на разных ВМ, следовательно они имеют разные адресные пространства, и это создает проблемы при передаче параметров и результатов, особенно если ВМ не идентичны. Так как RPC не может рассчитывать на разделяемую память, то это означает, что параметры RPC не должны содержать указателей на ячейки нестековой памяти и что значения параметров должны копироваться с одной ВМ на другую. Следующим отличием RPC от локального вызова является то, что он обязательно использует нижележащую систему связи, однако это не должно быть явно видно ни в определении процедур, ни в самих процедурах. Удаленность вносит также и дополнительные проблемы. Выполнение вызывающей программы и вызываемой локальной процедуры в одном ВМ реализуется в рамках единого процесса. Но в реализации RPC участвуют как минимум два процесса – по одному в каждой ВМ. В случае, если один из них аварийно завершится, могут возникнуть ситуации, при которых вызывающие процедуры будут безрезультатно ожидать ответа от удаленных процедур.
  Кроме того, существует ряд проблем, связанных с неоднородностью языков программирования и операционных сред: структуры данных и структуры вызова процедур, поддерживаемые в каком-либо одном языке программирования, не поддерживаются точно так же в других языках.
  Эти и некоторые другие проблемы решаются на основе реализации механизма «прозрачности» RPC: вызов удаленной процедуры должен выглядеть максимально похожим на вызов локальной процеду­ры и вызывающей процедуре не требуется знать, что вызываемая процедура находится на другой ВМ, и наоборот.
 
  Традиционно вызывающую процедуру называют клиентом, а вызываемую – сервером. В дальнейшем изложении будет использоваться именно эта терминология.
  RPC достигает прозрачности следующим путем. Когда вызываемая процедура действительно является удаленной, в библиотеку помещается вместо локальной процедуры другая версия процедуры, называемая клиентским стабом (stub – заглушка). Подобно оригинальной процедуре, стаб вызывается с использованием вызывающей последовательности, так же происходит прерывание при обращении к ядру. Только в отличие от оригинальной процедуры он не помещает параметры в регистры и не запрашивает у ядра данные, вместо этого он формирует сообщение для отправки ядру удаленной ВМ.
  Взаимодействие программных компонентов при выполнении удаленного вызова процедуры происходит следующим образом. После того, как клиентский стаб был вызван программой-клиентом, его первой задачей является заполнение буфера отправляемым сообщением. В некоторых системах клиентский стаб имеет единственный буфер фиксированной длины, заполняемый каждый раз с самого начала при поступлении каждого нового запроса. В других системах буфер сообщения представляет собой пул буферов для отдельных полей сообщения, причем некоторые из этих буферов уже заполнены. Этот метод особенно подходит для тех случаев, когда пакет имеет формат, состоящий из большого числа полей, но значения многих из этих полей не меняются от вызова к вызову. Затем параметры должны быть преобразованы в соответствующий формат и вставлены в буфер сообщения. К этому моменту сообщение готово к передаче, поэтому выполняется прерывание по вызову ядра. Когда ядро получает управление, оно переключает контексты, сохраняет регистры процессора и карту памяти (дескрипторы страниц), устанавливает новую карту памяти, которая будет использоваться для работы в режиме ядра. Поскольку контексты ядра и пользователя различаются, ядро должно точно скопировать сообщение в свое собственное адресное пространство (так, чтобы иметь к нему доступ, запомнить адрес назначения, и, возможно, другие поля заголовка), а также оно должно передать его сетевому интерфейсу. На этом завершается работа на клиентской стороне. Включается таймер передачи, и ядро может либо выполнять циклический опрос наличия ответа, либо передать управление планировщику, который выберет какой-либо другой процесс на выполнение. В первом случае ускоряется выполнение запроса, но отсутствует мультипрограммирование.
  На стороне сервера поступающие биты помещаются принимающей аппаратурой либо во встроенный буфер, либо в оперативную память. Когда вся информация будет получена, генерируется прерывание. Обработчик прерывания проверяет правильность данных пакета и определяет, какому стабу следует их передать. Если ни один из стабов не ожидает этот пакет, обработчик должен либо поместить его в буфер, либо вообще отказаться от него. Если имеется ожидающий стаб, то сообщение копируется ему. Наконец, выполняется переключение контекстов, в результате чего восстанавливаются регистры и карта памяти, принимая те значения, которые они имели в момент, когда стаб сделал вызов.
  После этого начинает работу серверный стаб. Он распаковывает параметры и помещает их соответствующим образом в стек. Когда все готово, выполняется вызов сервера. После выполнения процедуры сервер передает результаты клиенту. Для этого выполняются все описанные выше этапы, только в обратном порядке.
  В идеале RPC должен функционировать правильно и в случае отказов. Рассмотрим некоторые наиболее часто встречающиеся классы отказов и способы реакции системы на них.
  1. Клиент не может определить местонахождения сервера, например, в случае отказа нужного сервера, или из-за того, что программа клиента была скомпилирована давно и использовала старую версию интерфейса сервера. В этом случае в ответ на запрос клиента поступает сообщение, содержащее код ошибки.
  2. Потерян запрос от клиента к серверу. Самое простое решение – через определенное время повторить запрос.
  3. Потеряно ответное сообщение от сервера клиенту. Один из вариантов решения проблемы в этом случае – последовательная нумерация всех запросов клиентским ядром. Ядро сервера запоминает номер самого последнего запроса от каждого из клиентов, и при получении каждого запроса выполняет анализ: является ли этот запрос первичным или повторным.
  4. Сервер потерпел аварию после получения запроса. В данном случае имеет значение, когда произошел отказ – до или после выполнения операции. Но клиентское ядро не может распознать эти ситуации, для него известно только то, что время ответа истекло. Существует три подхода к решению этой проблемы:
  а) ждать до тех пор, пока сервер не перезагрузится, и пытаться выполнить операцию снова. Этот подход гарантирует, что RPC был выполнен до конца по крайней мере один раз, а возможно и более.
 
  б) сразу сообщить приложению об ошибке. Этот подход гарантирует, что RPC был выполнен не более одного раза.
  в) третий подход не гарантирует ничего. Когда сервер отказывает, клиенту не оказывается никакой поддержки. RPC может быть или не выполнен вообще, или выполнен много раз.
  Ни один из этих подходов не является особенно привлекательным. А идеальный вариант, который бы гарантировал ровно одно выполнение RPC, в общем случае не может быть реализован по принципиальным соображениям. Это может быть пояснено на следующем примере.
  Пусть удаленной операцией является печать некоторого текста, которая включает загрузку буфера принтера и установку одного бита в некотором управляющем регистре принтера, в результате которой принтер стартует. Авария сервера может произойти как за микросекунду до, так и за микросекунду после установки управляющего бита. Момент сбоя целиком определяет процедуру восстановления, но клиент о моменте сбоя узнать не может. В первом случае крах сервера ведет к краху клиента, и восстановление невозможно. Во втором случае действия по восстановлению системы выполнить и возможно, и необходимо.
  Следует подчеркнуть, что при реализации метода вызова удаленных процедур, клиентская процедура, написанная пользователем, выполняет «нормальный» (то есть локальный) процедурный вызов клиентского стаба. Так как клиентская процедура и клиентский стаб находятся в одном адресном пространстве, пара­метры передаются обычным образом. Аналогично, серверная процедура вызыва­ется процедурой в своем адресном пространстве. Таким образом, вместо выполне­ния с помощью процедур send и receive по сути операций ввода-вывода, в методе вызова удаленных процедур связь с удаленными объектами осуществляется при помощи имитации локальных процедурных вызовов.
 
 4.2. Понятия сетевой и распределенной операционных систем
 
  Операционные системы ММВС распределенного типа (то есть распределенных вычислительных систем – вычислительных сетей) обычно называют «сетевыми ОС». В вычислительных сетях есть узкоспециализированные правила, описывающие типы и фор­маты сообщений, которые могут посылаться в этих сетях, а также регламентирую­щие ответы на эти сообщения. Например, при некоторых обстоятельствах (скажем, перенос файла), когда сообщение посылается от источника адресату, адресат дол­жен послать в ответ подтверждение правильного приема сообщения. В другой си­туации подтверждения в ответ отправлять не требуется. Набор указанных правил, с помощью которых машины взаимодействуют в сети, назы­вается сетевым протоколом. Понятие протокола является фундаментальным понятием сетевых ОС, позволяющим определить и описать конкретные функции тех програмных частей операционных систем, которые отвечают за взаимодействие удаленных процессов.
  Сетевые средства связи обычно строятся по многослойному (многоуровневому) прин­ципу. Каждый уровень такой многослойной иерархии может взаимодейство­вать непосредственно только со своими вертикальными соседями, ру­ководствуясь четко закрепленными соглашениями – вертикальными протоколами, которые принято называть интерфейсами.
  Самым нижним уровнем в многослойных сетевых иерархиях является уровень, на котором реализуется реальная физическая связь между двумя узлами сети. Для обеспечения обмена физическими сигналами между двумя различными узлами сети необходимо, чтобы эти узлы поддерживали определенный протокол физического взаимодействия – горизонтальный протокол.
  На самом верхнем уровне находятся пользовательские процессы, которые инициируют обмен данными. Количество и функции промежуточных уровней варьируются от одной системы к другой. Все одинаковые уровни, лежащие выше физического, виртуально обмениваются данными посредством горизонтальных протоколов. Наличие такой виртуальной связи означает, что уровень N машины 2 должен получить ту же самую информацию, которая была отправлена уровнем N машины 1. Хотя в реальности эта информация должна была сначала дойти сверху вниз до уровня 1 машины 1, затем передана уровню 1 машины 2 и только после этого доставлена снизу вверх уровню N этой машины.
  Всю совокупность вертикальных и горизонтальных протоколов, достаточную для организации взаимодействия удаленных процессов в вычислительных сетях, принято называть семейством протоколов или стеком протоколов.
  Сети, построенные на основе разных стеков протоколов, могут быть объединены между собой с использованием вычислительных устройств, осуществляющих трансляцию из одного стека протоколов в другой.
  Наиболее совершенным и перспективным классом ОС являются так называемые распределенные операционные системы, которые сле­дует отличать от традиционных сетевых ОС. В сетевых операционных системах для того, чтобы задействовать ресурсы другой сетевой ВМ, пользователи должны знать о ее наличии и уметь это сделать. Каждая ВМ в сети работает под управлением своей локальной ОС, отличаю­щейся от ОС автономной ВМ наличием дополнительных сетевых средств (программной поддержкой сетевых интерфейсных устройств и механизмов доступа к удаленным ресурсам), но эти дополнения су­щественно не меняют структуру операционной системы.
  Распределенная система, напротив, внешне выглядит как обычная автономная система. Пользователь не знает и не должен знать, где его файлы хранятся (на локальной или удаленной ВМ), и где его про­граммы выполняются. Он может вообще не знать, подключена ли его ВМ к сети. Сетевые же операционные системы не создают ощущения работы с единой системой, которое характерно для распределенных ОС. Однако при этом внутреннее строение распределенной операци­онной системы имеет существенные отличия от автономных систем.
  В распределенных ОС к лежащей в основе системы вычислитель­ной сети должна быть добавлена некая общая модель, которая спо­собна превратить множество слабосвязанных ВМ в однородную «конструкцию», базирующуюся на единой концепции.
 
 4.3. Варианты реализации распределенных
 операционных сис­тем
 
  Наиболее удачным (по современным меркам) способом, с помо­щью которого распределенная система может достичь определенного уровня однородности, несмотря на различие аппаратного обеспече­ния отдельных объектов сети, является установка специального уровня программного обеспечения поверх сетевой операционной сис­темы. Этот уровень, называемый промежуточным программным обеспечением (а также связующим или посредническим программ­ным обеспечением), предназначен для того, чтобы скрыть ге­терогенность и распределенную природу базового набора ВМ. Промежуточное программное обеспечение предоставляет опре­деленные структуры данных и операции, позволяющие процессам и пользователям на значительно удаленных машинах однородно взаи­модействовать друг с другом.
  Один из типов такого программного обеспечения представляет собой промежуточное программное обеспечение, основанное на документах. Типичным представителем такого подхода является основная идея «Всемирной паутины» WWW (World Wide Web), которая заключается в том, что распределенная систе­ма должна выглядеть как гигантская коллекция документов, связанных гипер­ссылками.
  Другой подход состоит в том, чтобы придать распределенной системе вид огромной всемирной файловой системы. Использование модели файловой системы для распределенной системы озна­чает, что имеется единая глобальная файловая система с пользователями по все­му миру, способными читать и писать файлы, к которым у них есть доступ. Для связи процессов используется файловый обмен. Один процесс записывает данные в файл, а другой процесс считывает их оттуда. В этом случае возможно использование одной из следующих моделей: модели закачивания-скачивания и модели удаленного доступа. В первой модели чтобы получить доступ к файлу, процесс сначала считывает его с удаленного сервера, на котором хранится этот файл. Если для файла разрешено только чтение, то файл читается локально для более высокой производительности. Если файл должен быть записан, он записывается также локально. Когда процесс заканчивает работу с файлом, обновленный файл отправляется обратно на сервер. В модели удаленного доступа файл остается на сервере, а клиент посылает серверу команды для выполнения работы на месте. Преимущество модели закачивания-скачивания заключается в ее простоте и том факте, что перенос файла целиком эффективнее, чем перенос его по частям. К недостаткам данной модели относится необходимость наличия достаточно боль­шого объема памяти для хранения файла целиком локально. К тому же перенос файла целиком, когда требуется только его часть, представляет собой излишние расходы. Наконец, при наличии нескольких конкурирующих пользователей воз­никает проблема непротиворечивости файлов. Примером рассмотренного подхода является файловая система AFS (Andrew File System – файловая система, названная в честь спонсоров проекта ее разработки).
  В следующим подходе, связанном с использованием промежуточного программного обеспечения, предлагается называть все, что есть в системе, объектами. При этом объект – это набор переменных, объединенных вместе с набором процедур доступа к ним, на­зываемых методами. Процессам не разрешается получать доступ к переменным напрямую. Вместо этого они должны вызывать методы. Примером объектного промежуточного программного обеспечения является технология CORBA (Common Object Request Broker Architecture – архитектура распределенных объектных приложений). Технология CORBA представляет собой систему типа клиент-сервер, в которой клиентский процесс может осуществлять операции с объектами, расположенны­ми на серверах. Архитектура CORBA была разработана для неоднородной систе­мы, состоящей из разнообразных аппаратных платформ и операционных систем. Чтобы клиент на одной платформе мог вызвать сервер на другой платформе, между клиентом и сервером располага­ются специальные программные посредники.
  Еще одним известным подходом является использование промежуточного программного обеспечения, которое называется координационным. Пример этого подхода – новая система связи и синхронизации Linda. В системе Linda независимые процессы общаются через абстрак­тное пространство так называемых кортежей. Это пространство является глобальным по отно­шению ко всей системе, и процессы на любой ВМ могут вставлять кортежи в пространство кортежей или удалять их из него, независимо от того, как и где они хранятся. Для пользователя пространство кортежей выглядит как большая глобальная общая память.
  Другими примерами моделей, основанных на координации, являются модель «публикация-подписка» и система Jini.
  Модель «публикация-подписка» состоит из нескольких процессов, соединенных широковещательной сетью. Каждый процесс может производить информацию, потреблять информацию, а также делать то и другое. Когда у производителя информации есть новая информация, он рассылает ее всем по сети в виде кортежа. Это действие называется публикацией. Каждый кортеж содержит иерархически структурированную строку темы публикации с полями, разделенными точками. Процессы, которых интересуют определенные темы, могут подписаться на них. Чтобы подписаться на какую-либо тему, нужно сообщить ее специальному демону кортежей, работающему на той же ВМ, что и процесс. Демон кортежей на каждой ВМ копирует все рассылаемые кортежи в оперативную память. Затем он просматривает строку темы сообще­ния, чтобы определить, какие из процессов заинтересованы в получении этой информации, пересылая каждому такому процессу копию полученного сообщения. Кортежи также могут рассылаться по глобальным сетям.
  Система Jini состоит из большого количества самодостаточных Jini-устройств, каждое из которых предлагает другим устройствам одну услугу или несколько видов услуг. Jini-устройство может быть установлено в сеть и мгновенно начать предоставление услуг без сложных процедур установки. Отметим, что устройства устанавливаются не в ВМ, как в традиционном случае, а именно в сеть.
 Jini-устройство может быть не только ВМ, но также принтером, сотовым телефоном или другим уст­ройством с центральным процессором, оперативной памятью и соединением с сетью (возможно, беспроводным). Система Jini представляет собой свободную федерацию Jini-устройств, которые могут входить в систему и выходить из системы по своему желанию, без централизованного управления. Когда Jini-yстройство хочет присоединиться к федерации, оно передает по ло­кальной сети с помощью широковещания пакет с вопросом о наличии в данном районе службы поиска. Для нахождения службы поиска используется специаль­ный протокол обнаружения (один из нескольких собственных протоколов системы Jini). В качестве альтернативы новое Jini-устройство может ждать, пока не придет одно из периодически рассылаемых объявлений службы поиска. Если служба поиска видит, что новое устройство хочет зарегистрироваться, она посылает в ответ программу, выполняющую регистрацию. За­тем новое устройство исполняет полученную программу, связывающуюся со служ­бой поиска и регистрирующуюся в ней на некий установленный интервал времени, Пока не истек данный интервал времени, устройство может перерегистрировать­ся, если оно того пожелает. Такая схема означает, что Jini-устройство может поки­нуть систему, просто выключившись, и о существовании этого устройства систе­ма вскоре забудет. Таким образом, не требуется ни специальной процедуры выхода из системы, ни централизованного управления. Концепция регистрации на опре­деленный срок называется получением аренды. Обратим внимание, что поскольку программа регистрации устройства загру­жается в устройство по сети, эта программа может изменяться по мере развития системы, для чего не потребуется изменений аппаратного и программного обеспе­чения в самом устройстве.
  Более подробное изучение строения распределенных операционных систем выхо­дит за рамки данного учебного пособия.
  В заключении отметим, что в литературных публикациях, посвященных операционным системам, наблюдаются разные подходы к терминологии, касающейся ОС многомашинных вычислительных систем. Иногда все операционные системы, обеспечивающие функционирование ММВС (и, в частности, вычислительных сетей), называют распределенными, а иногда, наоборот, сетевыми. Для того, чтобы подчеркнуть те отличия между сетевыми и распределенными операционными системами, которые были рассмотрены в данном разделе, часто применяют термин «истинно распределенные» ОС, значение которого совпадает с принятой в настоящем учебном пособии трактовкой понятия распределенных операционных систем.
 
 Резюме
 
  Эффективным способом повышения производительности и надежности вычислительной техники является объединение отдельных автономных ВМ в многомашинные вычислительные системы.
  Различают два класса многомашинных вычислительных систем: ММВС сосредоточенного типа и ММВС распределенного типа (которые обычно называют распределенными вычислительными системами или вычислительными сетями).
  Существенным отличием ММВС от автономных (одно- или многопроцессорных) ВМ является то, что каждая машина, входящая в состав ММВС, имеет свою собственную оперативную память. Вследствии такого архитектурного построения механизмы организации межпроцессной взаимосвязи в ММВС и в автономных ВМ принципиально различны. В автономных машинах базой для взаимодействия процессов служит общая разделяемая память. В ММВС при отсутствии какой бы то ни было разделяемой памяти основой межпроцессного взаимодействия служит обмен физическими пакетами данных (так называемыми сообщениями) посредством некоторой коммуникационной среды.
  В наиболее простом варианте системные средства обеспечения связи могут быть сведены к двум основным системным вызовам (примитивам): один – для отправки сообщения, другой – для получения сообщения. Системные вызовы могут быть блокирующими (синхронными) или неблокирующими (асинхронными).
  В более сложной форме передача сообщений скрыта от пользовате­ля под видом вызова удаленной процедуры RPC. Идея вызова удаленных процедур состоит в расширении механизма передачи управления и данных внутри программы, выполняющейся на одной ВМ, на передачу управления и данных через коммуникационные каналы, связывающие разные ВМ.
  Операционные системы вычислительных сетей обычно называют сетевыми ОС. В вычислительных сетях есть узкоспециализированные правила, описывающие типы и фор­маты сообщений, которые могут посылаться в этих сетях, а также регламентирую­щие ответы на эти сообщения. Набор таких правил, с помощью которых машины взаимодействуют в сети, назы­вается протоколом. Понятие протокола является фундаментальным понятием сетевых ОС, позволяющим определить и описать конкретные функции тех програмных частей операционных систем, которые отвечают за взаимодействие удаленных процессов.
  Сетевые средства связи обычно строятся по многослойному (многоуровневому) прин­ципу. Каждый уровень такой многослойной иерархии может взаимодейство­вать непосредственно только со своими вертикальными соседями, ру­ководствуясь вертикальными протоколами, которые принято называть интерфейсами.
  Самым нижним уровнем в многослойных сетевых иерархиях является уровень, на котором реализуется реальная физическая связь между двумя узлами сети на основе горизонтального протокола физического взаимодействия. Все одинаковые уровни, лежащие выше физического, виртуально обмениваются данными посредством соответствующих горизонтальных протоколов.
  Всю совокупность вертикальных и горизонтальных протоколов, достаточную для организации взаимодействия удаленных процессов в вычислительных сетях, принято называть семейством протоколов или стеком протоколов. Сети, построенные на основе разных стеков протоколов, могут быть объединены между собой с использованием вычислительных устройств, осуществляющих трансляцию из одного стека протоколов в другой.
  Наиболее совершенным и перспективным классом ОС являются так называемые распределенные операционные системы. Распределенная система создает для пользователя полную иллюзию того, что он работает в обычной автономной системе.
  В распределенных ОС к лежащей в основе системы вычислитель­ной сети должна быть добавлена некая общая модель, которая спо­собна превратить множество слабосвязанных ВМ в однородную «конструкцию», базирующуюся на единой концепции.
  Одним из наиболее эффективных способов построения распределенных ОС является установка специального промежуточного уровня программного обеспечения поверх сетевой операционной сис­темы. Этот уровень предоставляет однородный уровень для взаимодействующих с ним приложений. Среди различных типов про­межуточного программного обеспечения следует выделить документное, файловое, объектное и координационное. Примерами промежуточного программного обеспече­ния служат такие системы, как WWW, AFS, CORBA, Linda, Jini.
 
 Контрольные вопросы и задания
 
 1. С какими целями ВМ объединяют в многомашинные вычислительные системы?
 2. Охарактеризуйте особенности построения и отличия ММВС сосредоточенного и распределенного типов.
 3. В чем важнейшее отличие ММВС от автономных (централизованных) ВМ?
 4. Посредством чего в ММВС осуществляется межпроцессное взаимодействие?
 5. Представьте основные системные вызовы для отправки и получения сообщений.
 6. Чем отличаются блокирующие (синхронные) системные вызовы от неблокирующих (асинхронных)?
 7. Какие проблемы возникают при организации программ с неблокирующи­ми примитивами и какие методы применяются для разрешения этих проблем?
 8. В чем заключается основная идея так называемого вызова удаленных процедур?
 9. Опишите механизмы реализации вызовов удаленных процедур.
 10. Охарактеризуйте наиболее часто встречающиеся классы отказов механизма вызова удаленных процедур и способы реакции системы на них.
 11. Дайте определение понятиям «сетевая операционная система» и «сетевой протокол».
 12. По какому прин­ципу строятся сетевые средства связи?
 13. Опишите основные функции вертикальных и горизонтальных протоколов.
 14. Что понимается под стеком протоколов вычислительной сети?
 15. В чем отличие распределенных операционных систем от традиционных сетевых ОС?
 16. Охарактеризуйте наиболее эффективные способы реализации распределенных операционных сис­тем.
 17. Приведите примеры практического построения разных типов про­межуточного программного обеспечения.
 5. Общие концепции разработки
  операционных систем
 
  5.1. Основные принципы построения операционных систем
  Одним из наиболее важных принципов построения ОС является принцип модульности. Под модулем операционной системы в общем случае понимают функционально законченный элемент системы, выполненный в соответствии с принятыми межмодульными интерфей­сами. По своему определению модуль предполагает возможность относительно легкой замены его на другой при наличии заданных интерфейсов. Способы обособления составных частей ОС в отдельные модули могут существенно различаться, но чаще всего разделение происходит именно по функциональному признаку. В зна­чительной степени разделение системы на модули определяется используемым методом проектирования ОС (снизу вверх или наоборот). Особо важное значение при построении ОС имеют реентерабельные программные модули, так как они позволяют более эффективно использовать ресурсы вычислительной системы (под реентерабельностью понимают свойство программы, позволяющее одновременно выполнять эту программу нескольким процессам). Достижение реентерабельности реализует­ся различными способами. В некоторых системах реентерабельность программы получают автоматически благодаря неизменяемости кодовых частей программ при исполнении (из-за особенностей системы команд машины), а также автома­тическому распределению регистров, автоматическому отделению кодовых час­тей программ от данных и помещению последних в системную область памяти. Естественно, что для этого необходима соответствующая аппаратная поддержка. В других случаях это достигается программистами за счет использования специ­альных системных модулей. Принцип модульности отражает технологические и эксплуатационные свойства системы. Наибольший эффект от его использования достижим в случае, когда принцип распространен одновременно на операционную систему, прикладные программы и аппаратуру.
  В ОС выделяется некоторая часть важных программных модулей, которые должны постоянно находиться в оперативной памяти для более эффективной организации вычис­лительного процесса. Эту часть в ОС называют ядром операционной системы, так как это действительно основа системы. При формировании состава ядра необходимо учитывать два про­тиворечивых требования. Во-первых, в состав ядра должны войти наиболее часто исполь­зуемые системные модули. Во-вторых, количество модулей должно быть таковым, чтобы объем памяти, занимаемый ядром, был бы не слишком большим. В состав ядра, как правило, входят модули управления системой прерываний, средства по переводу процессов из состояния выполнения в состояние ожидания, готовности и об­ратно, средства по распределению таких основных ресурсов, как оперативная память и процессор. Помимо программных модулей, входящих в состав ядра и постоянно располагающихся в оперативной памяти, может быть много других системных программных модулей, которые получили название транзитных. Транзитные программные модули операционной системы загружаются в оперативную память только при необходимости и в случае отсутствия свободного пространства могут быть замещены другими транзитными модулями. В качестве синонима термина «транзитный» иногда используется термин «диск-резидентный».
  Основное положение принципа генерируемости ОС определяет такой способ исходного пред­ставления центральной системной управляющей программы ОС (ее ядра и ос­новных компонентов, которые должны постоянно находиться в оперативной па­мяти), который позволял бы настраивать эту системную часть исходя из конкретной конфигурации конкретного вычислительного комплекса и круга решаемых задач. Эта процедура проводится редко, перед достаточно про­тяженным периодом эксплуатации ОС. Процесс генерации осуществляется с по­мощью специальной программы-генератора и соответствующего входного языка для этой программы, позволяющего описывать программные возможности сис­темы и конфигурацию машины. В результате генерации получается полная вер­сия ОС. Сгенерированная версия ОС представляет собой совокупность систем­ных наборов модулей и данных. Упомянутый выше принцип модульности положительно проявляется при гене­рации ОС. Он существенно упрощает настройку ОС на требуемую конфигура­цию вычислительного комплекса.
  Принцип функциональной избыточности учитывает возможность проведения одной и той же работы раз­личными средствами. В состав ОС может входить несколько модулей супервизора, управляющих тем или другим видом ресурса, несколько систем управления файлами, различные средства организации коммуникаций между вычисли-тельными процессами. Это позволяет пользователям быстро и наиболее адекватно адаптировать ОС к опре­деленной конфигурации вычислительного комплекса, обеспечить максимально эф­фективную загрузку технических средств и получить максимальную производительность при решении конкретного класса за­дач.
  Принцип виртуализации позволяет представить структуру системы в виде определенного набора планировщиков процессов и распределителей ресурсов (мониторов) и использовать единую централизован­ную схему распределения ресурсов. Наиболее естественным и законченным проявлением концепции виртуальности является понятие виртуальной машины. По сути, любая операционная система, являясь средством распределения ресурсов и организуя по определенным прави­лам управление процессами, скрывает от пользователя и его приложений реаль­ные аппаратные и иные ресурсы, заменяя их некоторой абстракцией. В результа­те пользователи видят и используют виртуальную машину как некое устройство, способное воспринимать их программы, написанные на определенном языке программирования, выполнять их и выдавать результаты. При таком языковом представлении пользователя совершенно не интересует реальная конфигурация вычислительного комплекса, способы эффективного использования его компонен­тов и подсистем. Он мыслит и работает в терминах используемого им языка и тех ресурсов, которые ему предоставляются в рамках виртуальной ма­шины. Обычно виртуальная машина, предоставляемая пользователю, воспроизводит ар­хитектуру реальной машины, но архитектурные элементы в таком представле­нии выступают с новыми или улучшенными характеристиками, часто упрощаю­щими работу с системой. Характеристики могут быть произвольными, но чаще всего пользователи желают иметь собственную «идеальную» по архитектурным характеристикам машину в следующем составе:
  1. Единообразная по логике работы память (виртуальная) практически неогра­ниченного объема. Организация работы с информацией в такой памяти производится в терминах обработки данных (в терминах работы с сегментами данных на уровне выбранного пользователем языка программи­рования);
  2. Произвольное количество процессоров (виртуальных), способных работать па­раллельно и взаимодействовать во время работы. Способы управления про­цессорами, в том числе синхронизация и информационные взаимодействия, реализованы и доступны пользователям на уровне используемого языка в терминах управления процессами;
  3. Произвольное количество внешних устройств (виртуальных), способных ра­ботать с памятью виртуальной машины параллельно или последовательно, асинхронно или синхронно по отношению к работе того или иного виртуаль­ного процессора, который инициирует работу этих устройств;
  4. Информация, передаваемая или хранимая на виртуальных устройствах, не ограничена допус­тимыми размерами. Доступ к такой информации осуществляется на основе либо последовательного, либо прямого способа доступа в терминах соответст­вующей системы управления файлами. Предусмотрено расширение инфор­мационных структур данных, хранимых на виртуальных устройствах.
  Степень приближения к «идеальной» виртуальной машине может быть большей или меньшей в каждом конкретном случае. Чем больше виртуальная машина, реализуемая средствами ОС на базе конкретной аппаратуры, приближена к «иде­альной», и, следовательно, чем больше ее архитек­турно-логические характеристики отличны от реально существующих, тем боль­ше степень виртуальности у полученной пользователем машины. Одним из аспектов виртуализации является организация возможности выполне­ния в данной ОС приложений, которые разрабатывались для других ОС. Други­ми словами, речь идет об организации нескольких операционных сред. Реализация этого принципа позволяет такой ОС иметь очень сильное преимущество перед аналогичными ОС, не имеющими такой воз­можности.

<< Пред.           стр. 3 (из 8)           След. >>

Список литературы по разделу