Лекции по "Операционные системы"

     В таком случае достаточно изменить значения базовых регистров и программа  даже не узнает, что загружена с  другого адреса. Именно так происходит загрузка com-файлов в системе MS DOS. Система выделяет свободную память, настраивает для программы базовые регистры DS и CS, которые называются сегментными, и передает управление на стартовый адрес. 

Позиционно-независимый  код

     Другой  способ относительной адресации - когда адрес получается сложением адресного поля команды и адреса самой этой команды - значения счетчика команд. Код, в котором используется только такая адресация можно загружать с любого адреса без перенастройки. Такой код называется позиционно-независимым (position-independent).

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

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

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

Оверлеи (перекрытия)

   Еще более интересный способ загрузки программы - это оверлейная загрузка (over-lay, лежащий сверху) или, перекрытие. Смысл оверлея состоит в том, чтобы не загружать программу в память целиком, а разбить ее на несколько модулей и помещать их в память по мере необходимости. При этом на одни и те же адреса в различные моменты времени будут отображены разные модули.

   Такой способ особенно актуален при небольшом объеме оперативной памяти.

   Следует отметить что оверлеи - это не то же самое, что виртуальная память (о которой будет рассказано дальше). Оверлеи позволяют отображать большое  количество объектов в ограниченное адресное пространство, а виртуальная память - отображать большое адресное пространство в ограниченную оперативную память.

   Для управления оверлеями существует специальная  процедура, менеджер перекрытий (overlay manager), которая знает, какой модуль куда загружен и при необходимости подгружает с диска то, что не было загружено. Вместо вызова функции вызывается эта процедура, которая находит нужную функцию и либо загружает ее с диска либо передает ей управление. Перед каждой ссылкой на оверлейные данные необходимо выполнять аналогичную процедуру, что намного увеличивает и замедляет программу. Иногда такие действия возлагаются на программиста (Win16, ранние Mac OS), иногда на компилятор, но чаще всего оверлейные данные не используют, а используют только оверлейный код.

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

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

Сборка  программ

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

   В большинстве современных языков программирования программа состоит  из отдельных слабо связанных  модулей. Как правило, каждому такому модулю соответствует отдельный  файл исходного текста. Эти файлы независимо обрабатываются языковым процессором (компилятором), и для каждого из них генерируется отдельный файл, называемый объектным модулем. Затем запускается программа, называемая редактором связей, компоновщиком или линкером (linker), которая формирует из заданных объектных модулей цельную программу.

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

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

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

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

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

   Типичный  объектный модуль содержит следующие  структуры данных:

• Таблицу перемещений, т.е. таблицу ссылок на перемещаемые объекты внутри модуля.
• Таблицу ссылок на внешние объекты. Иногда это называется таблицей или списком импорта.
• Таблицу объектов, определенных в этом модуле, на которые можно ссылаться из других модулей. В некоторых случаях ее называют списком экспорта. Иногда таблицы экспорта и импорта объединяют и называют все это таблицей глобальных символов. В этом случае для каждого символа приходится указывать, определен он в данном модуле или нет, а если определен, то как.
• Различную служебную информацию, такую как имя модуля, программу, которая ее создала (например, «gcc compiled»).
• Отладочную информацию.
• Собственно код и данные модуля.

Как правило, код и данные разбиты  на именованные секции (их также называют сегментами). В готовой программе весь код или данные, описанный в разных модулях, но принадлежащий к одной секции, собирается вместе. Например, в системах семейства Unix программы, написанные на языке C, состоят, как минимум, из трех программных секций:

text - исполняемый код (современные компиляторы иногда помещают в эту секцию и данные, описанные как const).

data - статически инициализированные  данные.

bss - неинициализированные  данные 

Объектные библиотеки

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

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

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

 

   Линкер  обычно собирает в программу все  объектные модули, которые были ему  заданы, даже если на этот модуль не было ни одной ссылки. С библиотечными  модулями он ведет себя несколько иначе.

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

Сборка  в момент загрузки

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

   Главное преимущество состоит в том, что  если мы загружаем несколько программ, использующих одну и ту же библиотеку, мы можем настроить их на работу с одной копией кода библиотеки, таким образом, сэкономив память. Примером такой сборки является широко используемая в windows и OS/2 технология DLL (на самом деле, DLL обеспечивает сборку не только в момент загрузки, но и после нее - возможность подключить дополнительный модуль к уже загруженной программе).

   Сборка  при загрузке замедляет процесс  загрузки программы, но упрощает, с  одной стороны, разделение кода, а  с другой стороны - разработку программ.

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

Динамические  библиотеки

   В windows и OS/2 используется именно такой способ загрузки. Исполняемый модуль в этих системах содержит ссылки на другие модули, называемые DLL (Dynamic-Link Library, динамически подключаемая библиотека). Фактически, каждый модуль в этих системах обязан содержать хотя бы одну ссылку на DLL, т.к. интерфейс к системным вызовам в этих ОС также реализован в виде DLL.

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

   Главное достоинство DLL состоит в том, что  модуль (как основной, так и библиотечный), может выбирать различные библиотеки, подгружая их уже после своей  собственной загрузки. При этом нет даже строгого ограничения на совместимость этих библиотек по вызовам (две библиотеки совместимы по вызовам, если они имеют одинаковые точки входа с одинаковым смыслом): загрузчик предоставляет возможность посмотреть список глобальных символов, определенных в библиотеке и получить указатель на каждый символ, обратившись к нему по имени. Однако загрузчик не сообщает количество и типы параметров функций и типы переменных, а тем более, что они означают. Эту информацию надо получать из других источников. При использовании C++, для DLL, как правило, создают header-файл (.h) или специальный def-файл, где перечислены и прокомментированы все экспортируемые функции и переменные библиотеки. В def-файле можно также указать специальные функции инициализации и терминации. Эти функции могут запускаться как при первой загрузке библиотеки (INITGLOBAL), так и при подключении библиотеки очередной программой (INITINSTANCE). Можно также управлять разделением сегмента данных DLL - применять общий сегмент данных для всех программ, использующих библиотеку, или создать свою копию для каждой программы. В случае если библиотека реализует COM-объект, его описание можно получить из списка зарегистрированных в системе COM-объектов (хранящегося в реестре).

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

   DLL являются удобным средством разделения  кода и создания отдельно загружаемых  программных модулей, но их  использование сопряжено с рядом  проблем. Одной из таких проблем является слежение за версией этого кода. Например, предположим, в системе одновременно загружены 30 программ, использующих библиотеку libc.dll. При этом десять из них разрабатывались и тестировались с версией 1.0, 5 - с версией 1.5 и 15 с версией 1.5a. Рассчитывать на устойчивую работу вех тридцати программ можно только при условии, что все три версии библиотеки полностью совместимы снизу вверх, причем не только по набору вызовов и их параметров, но и по точной семантике каждого из этого вызовов. Последнее требование иногда называют bug-for-bug compatibility (совместимость по ошибкам).

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

Разделяемый код в системах семейства Windows

   Особенно  остро проблема контроля версий библиотек  стоит в системах семейства windows, где принято помещать в дистрибутивы прикладных программ все потенциально разделяемые модули, которые этой программе могут потребоваться. При этом каждое приложение считает своим долгом поместить свои разделяемые модули в SYSTEM32 (в Windows NT/2000/XP это заодно приводит к тому, что установка таких программ требует администраторских привилегий). Средств же контроля над версиями и расположением DLL практически не предоставляется.

   В лучшем случае установочная программа  просто предлагает заменить уже существующую DLL, а деинсталлятор просто предупреждает, что удаляемые библиотеки могут  использоваться другими приложениями. Наличие реестра COM-объектов, не решает проблемы, т.к. большая часть приложений пока использует обычные DLL. Часть такого «разделяемого» кода, вообще никому не нужна кроме самого приложения, установившего его.

   В результате, когда, например, после установки MS Project 2000 перестает работать MS Office 2000, это в порядке вещей, а конфликты между приложениями различных разработчиков или разных «поколений» считаются неизбежными. Установить в одной системе и использовать две версии одного продукта часто просто невозможно.

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

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

 

Загрузка  самой ОС

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

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

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

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

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

   На  машинах фирмы Sun в качестве консольного монитора используется интерпретатор языка Forth. На ранних моделях IBM PC в ПЗУ был прошит интерпретатор BASIC.

   Чтобы загрузочный монитор смог что  бы то ни было загрузить, он должен уметь  проинициализировать устройство, с  которого предполагается загрузка, и считать с него загружаемый код. Поэтому загрузочный монитор обязан содержать модуль, способный управлять загрузочным устройством. Например, типичный BIOS PC-совместимого компьютера содержит модули управления гибкими дисками и жестким диском с интерфейсом Seagate 506 (в современных компьютерах это обычно интерфейс EIDE, конструктивно отличающийся от Seagate 506, но программно совместимый с ним сверху вниз). Кроме того, во многих системах установлена ПЗУ на платах контроллеров дополнительных устройств, содержащее программный модуль, способный проинициализировать устройство и произвести загрузку с него.

   Как правило, сервисы загрузочного монитора доступны загружаемой системе. Так, модуль управления дисками BIOS PC-совместимых  компьютеров предоставляет функции считывания и записи отдельных секторов диска. Доступ к функциям ПЗУ позволяет значительно сократить код первичного загрузчика ОС, и, нередко, сделать его независимым от устройства.

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

   Размер  первичного загрузчика ограничен чаще всего размером сектора на диске, т.е. 512 байтами. Если файловая система  имеет сложную структуру, иногда первичному загрузчику приходится считывать  вторичный, размер которого может быть намного больше. Из-за большего размера этот загрузчик намного умнее и может разобраться в структурах файловой системы. В некоторых случаях используются и третичные загрузчики. Такое последовательно исполнение втягивающих друг друга загрузчиков возрастающей сложности называется бутстрапом (bootstrap), что можно перевести как «втягивание себя за шнурки от ботинок».

   В случае нескольких установленных ОС, загрузчик может обеспечить выбор  загружаемой операционной системы  или загрузку операционной системы  с определенными параметрами (safe mode и т.п.).

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

   Проще всего происходит загрузка систем, ядро которых вместе со всеми дополнительными модулями (драйверами устройств, файловых систем и др.) собрано в единый загрузочный модуль. Например, в системах семейства Unix, ядро так и называется unix (в FreeBSD - vmunix, в Linux - vmlinux, или, в случае упакованного ядра, vmlinuz).

   При переконфигурации системы, добавления или удаления драйверов и других модулей необходима пересборка ядра, которая может производиться  либо стандартными системными редакторами  связей, либо специальными утилитами  генерации системы. Для такой пересборки в поставку системы должны входить либо исходные тексты (как у Linux и BSD), либо объектные модули ядра. Сборка ядра из объектных модулей на современных системах занимает не более нескольких минут. Полная перекомпиляция ядра из исходных текстов, разумеется, продолжается существенно дольше.

   Большинство современных ОС используют более  сложную форму загрузки, при которой  дополнительные модули подгружаются уже  после старта самого ядра. В терминах предыдущих разделов это называется «сборка в момент загрузки». Список модулей, которые необходимо загрузить, а также параметры настройки ядра, собраны в специальном файле или нескольких файлах. У DOS и OS/2 это config.sys, у win32 - реестр (registry).

 

3. Параллелизм с точки зрения программиста
0. Основные понятия и определения

   Как уже отмечалось, в многозадачной  ОС может быть загружено несколько  задач или процессов. В рамках одного процесса может «параллельно» (в случае одного процессора - псевдопараллельно) выполняться несколько нитей или потоков (threads) управления. С каждым процессом связан хотя бы один поток, который называется главным или основным потоком (main thread) приложения

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

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

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

   Интервал, в течение которого модификация  нарушает целостность разделяемого объекта, называется критической секцией. Если в течение этого интервала, к разделяемому объекту обратится другой поток, полагающийся на целостность этого объекта, то возникнет так называемая ошибка соревнования (race error). Задача написания корректной многопоточной программы, таким образом, может решаться двумя способами: либо исключением критических секций из всех используемых алгоритмов, либо обеспечением гарантии того, что никакие две нити никогда одновременно не войдут в критическую секцию, связанную с одним и тем же разделяемым объектом.

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

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

   Группа  операций модификации разделяемой  структуры данных, которая происходит неделимо, не прерываясь никакими другими  операциями с той же структурой данных называется транзакцией. Транзакции широко применяются в СУБД. Как правило, с базой данных параллельно работает множество клиентов, т.е. база данных является большим разделяемым объектом. Несколько запросов к базе объединяются в транзакцию, во время выполнения которой другие запросы ждут ее завершения.

   Программный модуль, внутри которого имеется хотя бы одна критическая секция, для  которой не обеспечено взаимное исключение, называется небезопасным для потоков (thread-unsafe) или нереентерабельным (not re-enterable). Вызов процедур такого модуля из различных потоков приведет к ошибкам соревнования и допустим лишь при условии, что вызывающая программа реализует взаимное исключение самостоятельно. Модуль, в котором таких секций нет или который сам обеспечивает взаимное исключение для них, называется реентерабельным (re-enterable - позволяющий повторное вхождение), безопасным для потоков (thread-safe) или реентрантным (reentrant). 

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

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

   int f; // 0- свободно, 1 – занято

   void thread1()

   {

         while(1) do

         {

               while (f); // Ждем пока критическая секция освободится

               f = 1;

               CriticalSection1();

               f = 0;

         }

   }

   void thread2()

   {

         while(1) do

         {

               while (f); // Ждем пока критическая секция освободится

               f = 1;

               CriticalSection2();

               f = 0;

         }

   }

   Может показаться, что все будет работать и CriticalSection1() и CriticalSection2() никогда не будут запущены одновременно. Однако это не так. В результате параллельной работы потоков может возникнуть следующая ситуация:

1. Начальное значение f = 0 (свободно)
2. В первом потоке произошла проверка while(f) и, поскольку f = 0, управление передается следующей команде.
3. Во втором потоке произошла проверка while(f) и, поскольку f = 0 (первый поток еще не успел присвоить f = 1), управление также передается следующей команде.
4. f = 1 в первом потоке
5. f = 1 во втором потоке
6. Выполняются CriticalSection1() и CriticalSection2(), т.е. возникает race error.

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

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

   На  практике, для решения проблемы работы с переменными в многопроцессных  конфигурациях, большинство современных  процессоров предоставляют аппаратные примитивы взаимоисключения - средства, позволяющие процессору монопольно захватить шину и выполнить несколько операций над памятью. Реализации этих примитивов различны у разных процессоров. Например, у x86 это специальный код операции, префикс захвата шины, который сам по себе не совершает никаких действий, но зато исполняет следующую за ним операцию в монопольном режиме. Благодаря этому можно одновременно получить старое значение флаговой переменной и установить новое командой (xchg). Если память модифицируется только одним процессором, исполняющим программу, префикс блокировки шины не нужен. Если процессоров (или других захватчиков шины) в системе несколько, префикс гарантирует взаимоисключение и для модификаций флага с их стороны.

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

Мертвые и живые блокировки

   Если  механизмы взаимоисключения используются для доступа к нескольким различным ресурсам, может возникнуть специфическая проблема, называемая мертвой блокировкой (dead lock).

   Например, если Thread1 и Thread2 обращаются к ресурсам A и B, следующим образом: Thread1 сначала  монопольно обращается к ресурсу A (Lock(A)), а  затем - монопольно обращается к ресурсу B (Lock(B)), а Thread2 - наоборот, сначала к ресурсу B, а потом к A, и если получится так, что порядок выполнения этих операций будет такой:

   Thread1.Lock(A)

   Thread2.Lock(B)

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

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

   Если  программа будет реагировать  на это сообщение повторной попыткой захвата ресурса (в цикле), возникнет  так называемая живая блокировка (live lock). Это еще хуже, чем мертвая блокировка, т.к. повторные попытки получить доступ к ресурсу будут тратить ресурсы процессора.

   Единственно правильная реакция на получение  сообщения о мертвой блокировка - это освободить все занятые потоком ресурсы и подождать в течение случайного промежутка времени.

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

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

   Еще один вариант решения состоит  в предоставлении возможности объединить примитивы и/или операции над  ними в группы. При этом программа может выполнить операцию захвата ресурсов A и B единой командой, во время исполнения которой никакая другая программа не может получить доступ к этим переменным.  Групповая операция выполняется как транзакция. Если хотя бы одна из операций группы приводит к ожиданию, все предыдущие ресурсы освобождаются.

   Ожидание  с освобождением ресурсов, впрочем, порождает ряд более специфических  проблем. Рассмотрим одну из них: потоку 1 нужны ресурсы A и B, которые он разделяет, соответственно с нитями 2 и 3. Если поток 1 захватывает ресурсы в соответствии с предложенным способом (освобождая их при неудачной попытке захвата), возможен такой сценарий исполнения нитей 2 и 3, при котором нить 1 не получит доступа к ресурсам никогда. Если же 2 и 3 сцеплены по каким-то другим ресурсам, это может привести к мертвой блокировке. Общего решения задачи разрешения блокировок и родственных им ситуаций при взаимоисключении доступа ко многим ресурсам на сегодня не предложено.

   Классическим  примером блокировок является “проблема голодного философа”, описанная Дейкстрой. Пять философов сидят вокруг круглого стола, на котором стоит блюдо спагетти. Спагетти они едят двумя вилками. Вилок на столе тоже 5 (они лежат между философами).

   Каждый  философ в течение случайного промежутка времени размышляет, а затем пытается взять лежащие рядом с ним вилки. Если ему это удается (обе вилки свободны), он начинает есть спагетти. Есть он также переменный промежуток времени, после этого откладывает вилки и вновь погружается в размышления.

   Если  одна из вилок занята, то можно придумать несколько вариантов действий философа.

1. Философ берет вилку и не отпускает ее, пока не поест

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

2. Вилки пронумерованы, и философ всегда сначала берет вилку с меньшим номером

Это означает, что 4 философа берут сначала  правую, а потом левую вилку, а 5-ый наоборот – сначала левую, а  потом правую. В этом случае блокировок не будет, но 5-ый философ будет в среднем ждать своих вилок дольше, чем остальные и будет недоедать.

3. Философ берет вилки тогда и только тогда, когда они доступны обе одновременно

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

Примитивы синхронизации

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

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

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

     Пример (Ошибка потерянного пробуждения (lost wake-up bug): 

     bool Busy;// true, если вошли в критическую секцию («занято»)

     void thread1()

     {

           bool MyFlag;

           while (true)

           {

                 MyFlag = true;

     testandset(MyFlag, Busy); // атомарно меняет местами MyFlag и Busy

                              // tmp = Busy; Busy = MyFlag; MyFlag = tmp;

                  // В этом промежутке  может быть получен сигнал  пробуждения

                  // (Busy может принять значение false, а в MyFlag это не отразится).

                  if (MyFlag) pause(); // pause ждет, пока Busy не примет значения false

                  RunCriticalSection(); // критическая секция

                  Busy = false; // Здесь подается сигнал пробуждения

     }

     } 

     void main()

     {

     Busy = false; // ресурс свободен

     // предпожим, что запускаем эти два метода в параллельных потоках

     thread1();

     thread1(); 
 } 

   Оператор  pause() ждет пока ему прийдет сообщение что Busy стала false. Но он не проверяет значение Busy в цикле, т.к. в таком случае поток не будет стоять, а будет занимать процессор работой. В результате может возникнуть ситуация, когда пробуждающий сигнал поступит в промежутке между операторами testandset и pause, поток его не получит и уснет навсегда. Т.е. Busy станет равным false (другой поток поменяет это значение), но на MyFlag это не отразится, т.к. мы уже прошли testandset. В результате поток приостановится с помощью pause и будет ждать пока Busy не станет равной false, хотя она и так уже false. Такая ошибка называется ошибкой потерянного пробуждения (lost wakeup bug).

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

Семафоры

   Семафор Дейкстры представляет собой целочисленную переменную, с которой ассоциирована очередь ожидающих нитей. Если значение переменной больше или равно 1  (семафор открыт), нить проходит через семафор успешно и вычитает из значения переменной 1. Если переменная равна 0 (семафор закрыт) нить останавливается и становится в очередь.

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

   Наиболее  простым случаем семафора является двоичный семафор. Начальное значение переменной такого семафора равно 1, и вообще она может принимать только значения 1 и 0. Двоичный семафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только один поток.

   Семафоры  общего вида могут принимать любые неотрицательные значения. В современной литературе такие семафоры называют семафорами-счетчиками (counting semaphore). Это соответствует случаю, когда несколько потоков может работать с объектом одновременно, или когда объект состоит из нескольких независимых, но равноценных частей - например, несколько одинаковых принтеров. При работе с такими семафорами часто разрешают процессам вычитать и добавлять к флаговой переменной значения, большие единицы. Это соответствует захвату/освобождению нескольких частей ресурса.

   Во  многих современных книгах и операционных системах семафорами называются только семафоры общего вида, двоичные же семафоры носят название мутекс (mutex - от MUTual EXclusion, взаимное исключение). Операции над мутексом называются захватом (aquire), соответствующим входу в критическую секцию и освобождением (release), соответствующим выходы из нее.

   Многие  ОС предоставляют для синхронизации  семафоры Дейкстры или похожие на них механизмы.

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

Захват  участков файлов

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

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

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

Мониторы  и серверы транзакций

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

   В случае СУБД решение состоит в  создании сервера БД или сервера транзакций, который вместо примитивов захвата участков файлов или таблиц предоставляет пользователям понятие транзакции.

   Если  пользовательская сессия объявила начало транзакции, изменения, которые она  вносит в таблицы, непосредственно  в таблицах не отражаются, и другие сессии, которые обращаются к вовлеченным в транзакцию данным получают их исходные значения. Завершив модификацию, пользовательская сессия может либо применить их (commit), либо сделать откат (rollback).

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

   Современные серверы СУБД представляют собой  сложные программные комплексы, которые, кроме собственно «развязки» транзакций предоставляют сложные  сервисы оптимизации запросов, индексации и кэширования данных.

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

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

Системы, управляемые событиями

   В середине 70-х годов появилась  новая архитектура многозадачных  систем - системы, управляемые событиями (event-driven systems).

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

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

   Впервые эта архитектура была реализована  в экспериментальных настольных компьютерах Alto, разработанных в 1973 году в исследовательском центре PARC фирмы Xerox. Целью эксперимента было создание операционной среды, удобной  для создания интерактивных программ с динамическим пользовательским интерфейсом.

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

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

   Все сообщения о событиях помещаются в очередь сообщений в порядке из возникновения.

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

   Рассмотрим  объект графического интерфейса, например меню. При нажатии на кнопку мыши в области этого меню вызывается обработчик события. Он разбирается, какой из пунктов меню был выбран, и посылает соответствующее командное сообщение объекту, с которым ассоциировано меню. Этот объект, в свою очередь, может послать командные сообщения каким-то другим объектам. Например, если была выбрана команда File-Open, меню передаст обработчику основного окна приложения сообщение fileopen, а тот, в свою очередь, может передать команду Open объекту, отвечающему за отрисовку и обработку файлового диалога.

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

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

   Управление  событиями позволяет относительно легко разрабатывать динамичные пользовательские интерфейсы, привычные  для пользователей современных  графических оболочек.

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

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

   Графические интерфейсы первого поколения - Mac OS и Win16 - реализовывали синхронную обработку  сообщений, а когда обработчик задумывался  надолго, рисовали неотъемлемый атрибут этих систем - курсор мыши в форме песочных часов.

   Несколько более совершенную архитектуру  предлагают оконная подсистема OS/2, Presentation Manager (PM). PM также реализует  синхронную стратегию обработки  сообщений (менеджер событий всегда ждет завершения очередного обработчика), но в системе, помимо менеджера событий, могут существовать и другие потоки. Если обработка события требует длительных вычислений или других действий (например, обращения к внешним устройствам или к сети), рекомендуется создать для этого отдельный поток и продолжить обработку асинхронно. Если же приложение этого не сделает (например, обработчик события просто зациклится или заснет на семафоре), системная очередь сообщений будет заблокирована и ни одно из графических приложений не сможет работать. Современные PM предоставляют в этом случае возможность отцепить зависшее приложение от очереди или даже принудительно завершить его.

   Асинхронные очереди сообщений представляют Win32 и оконная система X Window. Впрочем, и при асинхронной очереди, надолго «задумавшийся» обработчик событий тоже малоприятное зрелище, ведь он не может перерисовать собственное окно, поэтому передвижение других окон по экрану порождает любопытные спецэффекты.

   Большинство реальных приложений для современных  ОС, имеющих пользовательский интерфейс, таким образом, имеют двух- или более слойную архитектуру. При этом архитектура ближайшего к пользователю слоя (frontend), как правило, тяготеет к событийно-управляемой, а следующие слои (backend) обычно состоят из более традиционных взаимодействующих параллельно исполняющихся потоков. 

 

4. Реализация  многозадачности  на однопроцессорных компьютерах

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

   Таким образом, многозадачность (multitask) было бы правильнее называть многопоточностью (multithreading). Сейчас сложилась такая  терминология: Говоря о реализации параллельного выполнения кода на уровне операционной системы, употребляют термин многозадачность (например, Windows - многозадачная операционная система). Это связано с тем, что большинство программ не создают дополнительных потоков, а весь код исполняется в основном потоке.  Когда говорят о программе, которая порождает дополнительные потоки (т.е. в случае процесса, состоящего из нескольких потоков), и о поддержке потоков языком программирования, употребляют термин многопоточность.

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

Кооперативная многозадачность

   Самой простой реализацией многозадачной  системы была бы библиотека подпрограмм, которая определяет следующие объекты  и процедуры:

• struct Thread - Дескриптор потока - некоторая структура, описывающая поток.
• Thread* ThreadCreate(void (*ThreadBody)(void)) - Создать поток, исполняющий функцию ThreadBody.
• void ThreadSwitch() Эта функция приостанавливает текущий поток и активизирует очередной, готовый к исполнению.
• void ThreadExit() Прекращает исполнение текущего потока.

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

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

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

   Функция ThreadSwitch называется диспетчером или планировщиком (sheduler) и ведет себя следующим образом:

1. Она сохраняет указатель стека текущего потока в ее дескрипторе и восстанавливает указатель стека из дескриптора следующего активного потока.
2. Затем она передает управление на следующий активный поток.
3. Текущий поток остается активным и через некоторое время снова получит управление.
4. При выходе из функции ThreadSwitch (по оператору return), она автоматически возвращает управление в то место, из которого она была вызвана в этом потоке, потому что адрес возврата сохраняется в стеке.

 

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

   Дескрипторы потоков хранятся в очереди, называемой очередью потоков (thread queue) или очередью процессов. Дескриптор потока содержит указатель на следующий активный поток, а система хранит указатели на дескриптор текущего потока (начало очереди) и на конец очереди. При этом ThreadSwitch переставляет текущий поток в конец очереди, а текущим делает следующий за ней в очереди. Все вновь активизируемые нити также ставятся в конец очереди. Такая очередь используется практически во всех многозадачных ОС. Кроме того, очереди потоков используются и при организации очередей ожидания различных событий, например, при реализации семафоров Дейкстры.

   Многозадачность, основанная на принципе переключения по инициативе активного потока, называется кооперативной многозадачностью. Такая многозадачность используется в Windows 3.x, с помощью системного вызова GetNextEvent.

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

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

   Но  такая система обладает серьезными недостатками. Во-первых, необходимость включать в программу вызовы ThreadSwitch, усложняет программу и приводит к проблемам с переносимостью на другую платформу. Во-вторых, поток может захватить управление и никому не отдавать его, просто не вызывая ThreadSwitch. Если программа «зависнет», то это приведет к остановке всей системы. В-третьих, кооперативная ОС не получает выигрыша от многопроцессорности.

Вытесняющая многозадачность

   Вышеописанное подводит к идее вызывать ThreadSwitch не из пользовательской программы, а каким-то иным способом. Например, поручить вызов такой функции прерыванию от системного таймера. Тогда мы получим следующую схему:

• Каждому потоку выделяется квант времени:
• Если поток не освободил процессор в течение своего кванта, его переставляют в конец очереди. При этом все готовые к исполнению потоки более или менее равномерно получают управление.

Этот  механизм, называемый разделением времени (time slicing), реализован практически во всех современных ОС. Общим названием для всех методов переключения потоков по инициативе системы является термин вытесняющая (preemptive) многозадачность. Таким образом, вытесняющая многозадачность противопоставляется кооперативной, в которой переключение происходит только по инициативе самой задачи. Разделение времени является частным случаем вытесняющей многозадачности. В системах с приоритетами, вытеснение текущей задачи происходит не только по сигналам таймера, но и в случае, когда по каким-то причинам (чаще всего из-за внешнего события) активизируется процесс, с приоритетом выше, чем у текущего.

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

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

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

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

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

   Планировщик должен полностью сохранять контекст процесса. Это значительно усложняет жизнь разработчикам процессоров: добавив процессору лишний регистр, мы рискуем потерять совместимость со всеми ОС, реализующими вытесняющую многозадачность. Именно поэтому, в частности, процессоры SPARC и x86 реализуют мультимедийные расширения систем команд (групповые операции над 8-битными целыми числами), такие как MMX, с использованием уже существующих регистров, а не дополнительных регистров.

   Как правило, оказывается неудобным  сохранять контекст именно в стеке. Тогда его сохраняют в какой-то другой области памяти, чаще всего в дескрипторе потока. Многие процессоры имеют специальные команды сохранения и загрузки контекста. Для реализации вытеснения достаточно сохранить контекст текущего потока и загрузить контекст следующего активного потока из очереди. Необходимо предоставить также и функцию переключения потоков по собственной инициативе, аналогичную ThreadSwitch или точнее DeactivateThread (приостановка выполнения потока).

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

   Вытесняющий планировщик с разделением времени  ненамного сложнее кооперативного планировщика. 

Планировщики  с приоритетами

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

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

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

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

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

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

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

   Часто приоритеты делят на классы приоритетов, разрешая потокам изменять свой приоритет только в пределах своего класса. 

Монолитные  системы и системы  с микроядром

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

   Три основные группы потоков, исполняющихся  в режиме ядра, - это:

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

   Далее мы будем называть последние две  категории потоков, соответственно, пользовательскими и системными.

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

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

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

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

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

   Впрочем, если не требуется реальное время и не стоит задача обеспечить равномерное распределение системных потоков между процессорами многопроцессорной машины, монолитное ядро вполне приемлемо. Большинство систем семейств Unix (кроме System V R4) и Win32, OS/2 и ряд других систем общего назначения более или менее успешно ее используют.

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

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

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

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

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

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

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

   Во  многих современных ОС широко применяется  взаимодействие драйверов с остальной  системой посредством очередей запросов (или событий). Такое взаимодействие отчасти стирает различия между синхронными и полностью асинхронным межмодульным взаимодействием.

 

5. Управление оперативной памятью

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

Открытая  память

   Самый простой вариант управления памятью - отсутствие диспетчера памяти и возможность  загружать в системе только один процесс. Именно так работают CP/M и RT-11 SJ (Single-Job - однозадачная). В этих системах программы загружаются с фиксированного адреса PROG_START. В CP/M это 0x100; в RT-11 - 01000. По адресам от 0 до начала программы находятся векторы прерываний, а в RT-11 - также и стек программы. Операционная система размещается в старших адресах памяти. Адрес SYS_START, с которого она начинается, зависит от количества памяти у машины и от конфигурации ОС.

   В этом случае управление памятью со стороны системы состоит в  том, что загрузчик проверяет, поместится ли загружаемый модуль в пространство от PROG_START до SYS_START. Если объем памяти, который использует программа, не будет меняться во время ее исполнения, то на этом все управление и заканчивается.

   Однако  программа может использовать динамическое управление памяти (new, malloc или подобные процедуры). В этом случае уже сама программа должна следить за тем, чтобы не залезать в системные адреса. Как правило, динамическая память начинает размещаться с адреса PROG_END = PROG_START + PROG_SIZE. PROG_SIZE в данном случае обозначает полный размер программы, т.е. размер ее кода, статических данных и области, выделенной под стек.

   Функция malloc() поддерживает некоторую структуру  данных, следящую за тем, какие блоки  памяти из уже выделенных были освобождены. При каждом новом запросе она сначала ищет блок подходящего размера в своей структуре данных и, только когда этот поиск завершится неудачей, просит новый участок памяти у системы. Для этого используется переменная, которая в языке C называется brk_addr.

   Изначально  эта переменная равна PROG_END, ее значение увеличивается при выделении новых блоков, но в некоторых случаях может и уменьшаться. Это происходит, когда программа освобождает блок, который заканчивается на текущем значении brk_addr. 

Алгоритмы динамического управления памятью

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

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

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

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

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

   В стандартных библиотечных функциях языков высокого уровня, таких как malloc/free/realloc в C, new/dispose в Pascal и т.д., как правило, используются алгоритмы, рассчитанные на наиболее общий случай: программа запрашивает блоки случайного размера в случайном порядке и освобождает их также случайным образом.

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

   Есть  алгоритмы, в которых память выделяется фиксированными блоками, например, по 32 байта. В таком алгоритме вышеописанная проблема (когда свободные области слишком малы) не возникает, но возникает другая проблема. Если нужно выделить 15 или 47 байт, то 17 байт на блок окажутся потеряны. Это называется внутренней фрагментацией.

   Чем больше размер единицы выделения, тем  меньше грозит фрагментация внешняя, и  тем большие потери обеспечивает фрагментация внутренняя. В результате внутренней и внешней фрагментации теряется примерно 50% памяти.

   Обычно  все свободные блоки объединяются в двунаправленный связанный список (двунаправленный - чтобы можно было легко извлекать блок из середины списка).

   Поиск в списке может вестись тремя  способами: до нахождения первого подходящего (first fit) блока, до блока, размер которого ближе всего к заданному - наиболее подходящего (best fit), и до нахождения самого большого блока, наименее подходящего (worst fit).

   Использование стратегии worst fit имеет смысл только в сочетании с сортировкой  списка по убыванию размера. Это может  ускорить выделение памяти, т.к. всегда берется первый блок, а если он недостаточно велик, мы с чистой совестью можем сообщить, что свободной памяти нет, но при этом возникают проблемы при освобождении блоков.

   На  практике стратегия worst fit используется при размещении пространства в файловых системах, например в HPFS.

   Чаще  всего применяют несортированный  список и best fit. Для нахождения наиболее подходящего нужно просматривать весь список, в то время как первый подходящий может оказаться в любом месте, и среднее время поиска будет меньше.

   В общем случае best fit увеличивает фрагментацию памяти. Действительно если мы нашли  блок с размером больше заданного, мы должны отделить «хвост» и пометить его как новый свободный блок. В случае best fit размер этого «хвоста» будет маленьким, и мы в итоге получим большое количество мелких блоков, которые невозможно объединить, так как пространство между ними занято.

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

   При использовании first fit с линейным двунаправленным  списком возникает специфическая  проблема. Если каждый раз просматривать список с одного и того же места, то большие блоки, расположенные ближе к началу будут чаще удаляться. Соответственно, мелкие блоки будут скапливаться в начале списка, что увеличит среднее время поиска. Простой способ борьбы с этим явлением состоит в том, чтобы просматривать список то в одном направлении, то в другом. Более радикальный и еще более простой метод заключается в следующем: список делается кольцевым, и каждый поиск начинается с того места, где мы остановились в прошлый раз. В это же место добавляются освободившиеся блоки. В результате список очень эффективно перемешивается и никакой «антисортировки» не возникает.

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

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

   Предположим, что мы освобождаем блок с адресом addr. Считаем, что addr имеет тип word*, и при добавлении к нему целых чисел результирующий адрес будет отсчитываться в словах, как в языке C. Для того чтобы проверить, свободен ли сосед перед ним, мы должны посмотреть слово с адресом addr - 2. Если оно отрицательно, то сосед занят,  и мы должны оставить его в покое. Если же оно положительно, то мы можем легко определить адрес начала этого блока как addr - addr[-2].

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

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

     Итак, наилучшим из известных универсальных алгоритмов динамического распределения памяти является алгоритм парных меток с объединением свободных блоков в двунаправленный кольцевой список и поиском по принципу first fit. Этот алгоритм обеспечивает приемлемую производительность почти для всех стратегий распределения памяти, используемых в прикладных программах.

   Алгоритм  парных меток был предложен Дональдом Кнутом в начале 60-х. В третьем издании его классической книги, этот алгоритм приводится под названием «освобождения с дескрипторами границ». В современных системах используются и более сложные структуры дескрипторов, но всегда ставится задача обеспечить поиск соседей блока по адресному пространству за фиксированное время. Практически все современные программы динамического выделения памяти используют аналоги алгоритмов парных меток. Другие известные подходы либо просто хуже, либо проявляют свои преимущества только в специальных случаях.

   Как уже отмечалось выше, алгоритмы выделения памяти становятся проще и лучше, если выделяются блоки нескольких фиксированных размеров. Широкое применение нашел алгоритм, который ограничивает размеры блоков степенями числа 2 (начиная, например, с 512 байт. Т.е. блоки будут 512 Байт, 1 кб, 2 кб и т.д. до какой-нибудь верхней границы). Свободные блоки определенного размера объединяются в отдельные списки (по 512 байт, по 1 кб и т.д.). Такая стратегия называется алгоритмом близнецов.

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

Сборка  мусора

   Явное освобождение динамически выделенной памяти применяется во многих системах программирования, но оно имеет серьезный  недостаток: если программист по какой-то причине не освобождает выделенные блоки, память будет теряться. Эта ошибка, называемая утечкой памяти (memory leak), особенно неприятна в программах, которые длительное время работают без перезапуска - подсистемах ядра ОС, постоянно запущенных сервисах или серверных приложениях. Дополнительная неприятность состоит в том, что медленные утечки могут привести к заметным потерям памяти лишь при многодневной или даже многомесячной непрерывной эксплуатации системы, поэтому их сложно обнаружить при тестировании.

   Некоторые системы программирования используют специальный метод освобождения динамической памяти, называемый сборкой мусора (garbage collection). Этот метод состоит в том, что ненужные блоки памяти не освобождаются явным образом. Вместо этого используется некоторый более или менее изощренный алгоритм, следящий за тем, какие блоки еще нужны, а какие - уже нет.

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

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

Открытая  память (продолжение)

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

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

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

   Так, например, процедура управления памятью MS DOS рассчитана на случай, когда программы выгружаются из памяти только в порядке, обратном тому, в каком они туда загружались (на практике, они могут выгружаться и в другом порядке, но это явно запрещено в документации и часто приводит к проблемам). Это позволяет свести управление памятью к стеку.

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

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

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

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

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

   В этих системах предполагается, что  пользовательские программы не сохраняют  указателей на динамически выделенные блоки памяти. Вместо этого каждый такой блок идентифицируется целочисленным дескриптором (handle). Когда программа непосредственно обращается к данным в блоке, она выполняет системный вызов GlobalLock. Этот вызов возвращает текущий адрес блока. Пока программа не исполнит вызов GlobalUnlock, система не пытается изменить адрес блока. Если же блок не заперт, система считает себя вправе передвигать его по памяти или даже сбрасывать на диск.

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

   Использование дескрипторов сильно усложняет программирование вообще и в особенности перенос ПО из систем, использующих линейное адресное пространство. Все указатели на динамические структуры данных в программе нужно заменить дескрипторами, а каждое обращение к таким структурам необходимо окружить вызовами GlobalLock/GlobalUnlock, которые:

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

При этом, как правило, приходится заниматься оптимизацией использования handler’ов.

   Наиболее  опасной ошибкой является вынос указателя на динамическую структуру за пределы скобок GlobalLock/GlobalUnlock. Эту ошибку очень сложно обнаружить при тестировании, т.к. она появляется, только если система пыталась передвигать блоки в промежутках между обращениями. Иными словами, ошибка может проявлять или не проявлять себя в зависимости от набора приложений, исполняющихся в системе, и от характера деятельности этих приложений.

   Не  случайно фирма Microsoft полностью отказалась от управления памятью с помощью handler’ов в Windows 95, в которой реализована почти полноценная виртуальная память. Mac OS 10, построенная на ядре BSD Unix, также имеет страничную виртуальную память и никогда не перемещает блоки памяти, адресуемые дескрипторами. 

Системы с базовой виртуальной адресацией

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

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

   Как правило, машины, использующие базовую  адресацию, имеют два регистра. Один из регистров задает базу для адресов (BASE), второй устанавливает верхний  предел (DATUM). Если адрес выходит за границу, установленную значением DATUM, возникает исключительная ситуация (exception) ошибочной адресации. Как правило, это приводит к тому, что система принудительно завершает работу программы.

   Эти два регистра решают сразу две  важные проблемы.

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

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

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

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

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

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

   Протокол  общения прикладной программы с  системой состоит в следующем: программа помещается параметры вызова в оговоренное место - в регистры общего назначения или в стек - и исполняет SYSCALL. Одним из параметров передается и код системного вызова. Диспетчер вызовов анализирует допустимость параметров и передает управление соответствующей процедуре ядра, которая и выполняет требуемую операцию (или не выполняет, если у пользователя не хватает полномочий). Затем процедура помещает в оговоренное место (чаще всего в регистры или стек) возвращаемые значения и передает управление диспетчеру или вызывает SYSRET самостоятельно.

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

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

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

 

6. Сегментная и страничная виртуальная память

   В системах с сегментной и страничной адресацией виртуальный адрес имеет сложную структуру. Она разбит на два битовых поля: селектор страницы (сегмента) и смещение в нем. Физический адрес получается сложением адреса начала страницы (который берется из дескриптора страницы) и смещения. Адресное пространство оказывается состоящим из дискретных блоков. Если все эти блоки имеют фиксированную длину и образуют вместе непрерывное пространство, они называются страницами. Если длина каждого блока может задаваться, а неиспользуемым частям блоков соответствуют «дыры» в виртуальном адресном пространстве, такие блоки называют сегментами. Как правило, один сегмент соответствует коду или данным одного модуля программы. Со страницей или сегментом могут быть ассоциированы права чтения, записи и исполнения, которые также хранятся в дескрипторе.

   Такая адресация реализуется аппаратно. Процессор имеет специальное  устройство, называемое диспетчером памяти или УУП (Устройство Управления Памятью, MMU - Memory Management Unit).

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

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

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

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

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

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

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

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

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

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

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

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

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

Сегменты, страницы и системные  вызовы

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

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

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

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

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

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

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

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

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

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

Взаимно недоверяющие подсистемы

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

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

   Например, при исполнении системного вызова int read(int file, void* buf, size_t size) программа должна передать системе мандат на право  записи в буфер buf размером size байт. При этом буфер будет отображен в адресное пространство подсистемы ввода/вывода, но эта подсистема не получит права записи в остальное адресное пространство нашей задачи. Впрочем, этот подход имеет две проблемы.

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

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

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

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

Разделяемые библиотеки

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

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

   Использование разделяемых библиотек и/или DLL (в  данном случае разница между ними не принципиальна) предполагает ту или иную форму сборки в момент загрузки: исполняемый модуль имеет неразрешенные адресные ссылки и имена библиотек, которые ему нужны. При загрузке эти библиотеки подгружаются и ссылки разрешаются. Проблема здесь в том, что при подгрузке библиотеки ее нужно переместить, перенастроив абсолютные адресные ссылки в ее коде и данных. Если в разных процессах библиотека будет настроена на разные адреса, она уже не будет разделяемой. Если разделяемые библиотеки могут иметь неразрешенные ссылки на другие библиотеки, проблема только усугубляется: перемещаемым ссылкам добавляются еще и внешние.

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

   Более приемлемое решение этой проблемы реализовано  в OS/2 2.x и Win32. Идея состоит в том, чтобы  выделить область адресов под  загрузку DLL и отображать эту область  в адресные пространства всех процессов. Таким образом, все DLL, загруженные в системе, видны всем.

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

   Менее очевидный, но более серьезный недостаток состоит в том, что эта архитектура  не позволяет двум приложениям одновременно использовать две разные, но одноименные DLL, например, две разные версии стандартной библиотеки языка C. Поэтому либо мы вынуждены требовать от всех разделяемых библиотек абсолютной (bug-for-bug) совместимости с версий, либо признать, что далеко не каждая смесь прикладных программ будет работоспособна.

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

Страничный  обмен

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

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

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

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

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

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

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

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

   Можно также удалять то, что дольше всего  находится в памяти. Это называется алгоритмом FIFO (first in, first out, первый вошел, первый вышел). Видно, что это уже чуть сложнее случайного удаления - нужно запоминать, когда мы что загружали.

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

   Наиболее  справедливым будет удалять тот  объект, к которому дольше всего  не было обращений в прошлом LRU (Least Recently Used). Такой подход требует набора сведений обо всех обращениях. Например, диспетчер памяти должен поддерживать в дескрипторе каждой страницы счетчик обращений, и при каждой операции чтения или записи над этой страницей увеличивать этот счетчик на единицу. Это требует довольно больших накладных расходов.

   Интересным  приближением к алгоритму LRU является так называемый clock-алгоритм, применяемый  во многих современных ОС, в том  числе в системах семейства Unix. Он состоит в следующем.

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

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

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

 

7. Драйверы внешних устройств

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

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

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

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

Например, в большинстве аппаратных реализаций последовательного порта RS232 передача байта состоит из четырех шагов: записи значения в регистр данных, записи команды «передавать» в регистр  команды, ожидания прерывания по концу передачи и проверки успешности передачи путем считывания статусного регистра устройства. Нарушение последовательности шагов может приводить к неприятным последствиям – например, перезапись регистра данных после подачи команды, но до завершения передачи, может привести к остановке передачи или, что еще хуже, передаче искаженных данных.

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

Функции драйверов

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

Основные  функции драйвера:

1. Инициализация драйвера

Эта функция вызывается при загрузке модуля. Драйвер должен зарезервировать все необходимые ему системные ресурсы и проинициализировать собственные глобальные переменные. Инициализация устройства на этом этапе не происходит.

2. Поиск устройства в системе

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

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

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

4. Уничтожение копии драйвера конкретного устройства.

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

5. Деинициализация драйвера

Драйвер обязан освободить все ресурсы, которые  он занял на этапе инициализации  модуля, а также все ресурсы, занятые им во время работы на уровне модуля (т.к. остальные ресурсы освобождаются предыдущей функцией).

Остальные функции зависят от типа драйвера.

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

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

Многоуровневые  драйверы

   В некоторых случаях драйвер не может осуществлять управление устройством  полностью самостоятельно или это  неудобно. Например, мышь может быть подключена к COM-порту, к PS/2 или к USB, клавиатура к PS/2 или USB. Делать драйверы для всех возможных комбинаций нецелеобразно, поэтому в таких случаях используют многоуровневые драйверы, т.е. делают драйверы для портов  и драйвер для устройства, который с ними взаимодействует.

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

Загрузка  драйверов

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

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

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

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

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

Архитектура драйвера

   Типичный  протокол работы с внешним устройством  состоит из:

1. Анализа запроса
2. Передачи команды устройству
3. Ожидания прерывания по завершении этой команды
4. Анализа результатов операции
5. Формирования ответа внешнему устройству

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

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

   Обработку запроса к драйверу можно разделить  на три фазы:

1. Предобработка
2. Исполнение запроса
3. Постобработка

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

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

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

   Самым простым механизмом работы с драйвером является синхронный ввод-вывод, когда функции драйвера просто вызываются. Так, например, работают драйверы в MS DOS и ряде других однозадачных систем.

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

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

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

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

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

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

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

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

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

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

Сервисы ядра, доступные драйверам

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

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

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

   Еще одно важное различие состоит в том, что, исполняя системный вызов, программисту не надо заботиться о его реентерабельности: ядро либо обеспечивает подлинную реентерабельность, либо создает иллюзию реентерабельности благодаря тому, что исполняется с более высоким приоритетом, чем все пользовательские программы. Напротив, доступные драйверам сервисы ядра делятся на две группы – те сервисы, которые можно вызывать из обработчиков прерываний и те, которые нельзя.

   Сервисы, доступные для обработчиков прерываний, должны удовлетворять двум требованиям: они должны быть реентерабельными и завершаться за гарантированное время. Например, выделение памяти может потребовать сборки мусора или даже поиска жертвы для удаления в адресных пространствах пользовательских задач. Кроме того, выделение памяти требует работы с разделяемым ресурсом (пулом памяти ядра) и его достаточно сложно реализовать реентерабельным образом.

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

   Поэтому обработчикам прерываний очень редко  разрешают запрашивать память.

   Драйверам как правило предоставляются  сервисы следующих категорий:

• Взаимодействие с конфигурацией системы – доступ к данным средств автоконфигурации и, кроме того, регистрация драйвера и управляемых им устройств в системе.
• Сбор и сохранение статистики.
• Запросы на выделение и освобождение системных ресурсов, в первую очередь памяти.
• Примитивы межпоточного взаимодействия – между потоками самого драйвера, между драйвером и другими потоками ядра и, наконец, между драйвером и потоками пользовательского процесса.
• Таймеры (используемые при сборе статистики, а также чтобы можно было определить, что устройство подозрительно долго не отвечает).
• Передача данных из пользовательского адресного пространства и обратно и другие операции над пользовательским адресным пространством.
• Сервисные функции.

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

• Каждое устройство имеет фиксированные адреса регистров. Системная шина либо генерирует исключение по отсутствию адресуемого устройства, либо при чтении с несуществующего адреса возвращает фиксированное значение (чаще всего 0 или 0xFFFFFFFF). Во втором случае достаточно, чтобы один из регистров устройства после включения питания обязательно содержал значение отличающееся от этого фиксированного. Драйвер обращается к регистрам этого устройства, и, прочитав правильное значение и не получив при этом ошибки шины, может сделать вывод, что устройство присутствует. Устройства, у которых нет драйверов, таким способом не могут быть обнаружены, но ОС все равно не сможет с ними работать. Этот метод плох тем, что трудно применим при большом числе изготовителей периферийных устройств и самих этих устройств – конфликты между адресами устройств различных изготовителей практически неизбежен.
• Каждое устройство имеет ПЗУ, которое отображается на адреса системной шины. После запуска загрузочный монитор сканирует все возможные адреса таких ПЗУ и исполняет найденный в них код. Этот код регистрирует устройство в конфигурационной базе данных загрузочного монитора. ОС после загрузки обращается к этой базе. Данные метод плох тем, что применим, только если устройства подключаются к системам с совместимыми процессорами.
• Каждое устройство содержит набор конфигурационных регистров, которые содержат уникальный идентификатор устройства и, возможно, сведения о его конфигурации. Сканирование этих регистров может осуществляться как самой системой, так и загрузочным монитором. Этот метод лишен недостатков двух предыдущих и широко применяется в большинстве современных периферийных шин, например в PCI.

 

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

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

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