Операционные системы. Три простых элемента.

Ознакомился с книгой Операционные системы. Три простых элемента. профессоров информатики Висконсинского университета Ремзи и Андреа Арпачи-Дюссо.

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

Структура книги

Вся книга разбивает описание операционной системы на три крупные части:

  • Виртуализация
  • Конкурентность
  • Хранение

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

Виртуализация

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

Виртуализация процесса: неформально процесс - это исполняемая программа.
Машинное состояние - то из чего процесс непосредственно состоит и к чему имеет доступ (адресное пространство, специальные регистры - счетчик команд, указатель стека и пр.)

При загрузке процесса с диска, он также помещается в список процессов. Список процессов содержит информацию обо всех процессах в системе.

Основные API процессов:

  • fork() - используется для создания нового процесса. Дочерний процесс является почти точной копией своего родителя;
  • wait() - позволяет родительскому процессу ждать завершения потомка;
  • exec() - позволяет загружать код (и статические данные) из полученного файла и перезаписывает текущий сегмент кода. Таким образом, новый процесс не создается, вместо этого уже работающая программа преборазуется в другую работающую программу.

Контекстное переключение - ОС сохраняет регистры общего назначения, счетчика команд и указателя стека ядра текущего процесса, а затем восстанавливает все то же самое для процесса, который будет выполняться следующим.
Здесь хочу отметить интересную лекцию про планировщик Linux, где автор измеряет контекстное переключение threads и на его компьютере получает значение равное ~1 микросекунде (2016 год).

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

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

  • Правило 1 - если Приоритет(А) > Приоритет(B), то выполнять A;
  • Правило 2 - если Приоритет(А) = Приоритет (B), то применять к A и B алгоритм циклического планирования;
  • Правило 3 - когда задание поступает в систему, оно помещается в очередь с высшим приоритетом;
  • Правило 4 - после того как задание сзрасходовало свою квоту на данном уровне, его приоритет понижается, т.е. оно опускается вниз на одну очередь;
  • Правило 5 -по истечении некоторого времени S перемещать все присутствующие в системе задания в очередь с высшим приоритетом.

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

При реализации страничной организации используются:

  • Таблица страниц - структура данных, используемая для отображения виртуальных адресов (номеров виртуальных страниц) в физические (номера страничных рамок);
  • TLB - кэш трансляции адресов.

Конкурентность

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

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

mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, ox8049a1c

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

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

Решение состояния гонок, которое рассматривается в разделе “Конкурентность”, для атомарного выполнения команд - введение блокировок.
Блокировка - просто переменная, в ней хранится текущее состояние блокировки: свободна (разблокирована, доступна) либо захвачена (заблокирована, занята).
В стандарте POSIX для блокировок употребляется название mutex, поскольку они применяются для обеспечения взаимного исключения (mutual exclusion) потоков.
Конструируются реальные блокировки с помощью поддержки со стороны оборудования (в форме специальных атомарных команд: compare-and-swap или test-and-set) и с помощью поддержки операционной системы, чтобы убрать бесполезное переключение контекста между спящими потоками.

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

Для решения второй поставленной проблемы в главе “Конкурентность”, а именно создания механизма для правильного пробуждения спящего потока по условию, авторы описывают использование условной переменной. Это явная очередь, в которую поток может поместить себя, если в данный момент некоторое условие ложно и требуется ждать, когда оно станет истинным. Другой поток, изменив это условие, может пробудить один или несколько ожидающих его потоков. В языке Go это реализовано с помощью типа sync.Cond, который как и pthread_cond_t из языка Си реализовывает методы Signal(), Wait(), и по мимо них Broadcast().

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

int sem_wait(sem_t *s) {
    уменьшить значение семафора s на единицу
    ждать, если значение s отрицательно
}

int sem_post(sem_t *s) {
    увеличить значение семафора s на единицу
    если в очереди к семафору стоит один или более поток,
    разбудь один из них
}

В пакете x библиотеки Go есть готовая имплементация семафора с конфигурируемыми весами.

Последняя глава в разделе “Конкурентность”, не считая материала повышенной сложности про событийно-управляемую конкурентность, посвящена типичным ошибкам в конкурентных программах. Отвечая на поставленную проблему, авторы книги опирались на исследование “Learning from Mistakes - A comprehensive Study on Real World Concurrency Bug Characteristics” , в работе которой рассматриваются четыре крупных приложения с открытым исходным кодом: MySQL, Apache, Moziila, OpenOffice.
В данном исследование веделено два класса ошибок:
Первый класс ошибок - не связанный с взаимоблокировкой, а именно нарушение атомарности и нарушение порядка.
Нарушение атомарности: “нарушена желаемая сериализуемость нескольких операций доступа к памяти”, т.е. участок кода предполагается атомарным, но во время выполнения атомарность не обеспечивается. Решение - окружить доступ к разделяемой переменной блокировками.
Ошибка нарушения порядка: “изменен желаемый порядок выполнения двух (групп) операций доступа к памяти”, т.е. A должно выполняться раньше B, но этот порядок никак не обеспечен. Решение - использование условных переменных (или семафоров), т.е. нужно гарантировать ожидание потока, действия которого зависят от другого потока.

Второй класс ошибок - связан с взаимоблокировкой. Например, когда Поток 1 удерживает блокировку (L1) и ждет освобождения другой блокировки (L2), а в то же время Поток 2, удерживающий блокировку L2. ждёт освобождения L1.

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

  • взаимное исключение - потоки требуют монопольного контоля над необходимыми им ресурсами (напр. захватывают блокировку);
  • ожидание с удержанием - потоки удерживают выделенные им ресурсы и при этом ожидают выделения дополнительных ресурсов (напр. хотят захватить новые блокировки);
  • отсутствие вытеснения - ресурсы (напр. блокировки) невозможно насильно отобрать у потоков;
  • циклическое ожидание - существует замкнутая цепочка потоков - такая, что каждый поток удерживает один или несколько ресурсов, которые хочет получить следующий поток в цепочке. Решения:
  • полное упорядочение захвата блокировок или частичное упорядочение захвата;
  • захватывать блокировки атомарно;
  • использовать try lock mutex;
  • избегать взаимблокировок с помощью планирования - необходимо иметь глобальную информацию о том, какие блокировки могут затребовать различные потоки в ходе своего выполнения.

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

Хранение

Последний раздел книги “Хранение” начинается со знакомства с понятием устройства ввода-вывода и как операционная система с ним взаимодействует. В “классической” системе располагаются следующие элементы: Такая иерархическая структура определяется в первую очередь ценой и физикой. Чем шина быстрее, тем она должна быть короче, поэтому на высокоскоростной шине нет места для подключения устройств.
Правда, в современных системах все чаще используются специализированные наборы микросхем и более быстрые двухточечные соединения, например ниже показана упрощенная диаграмма микросхем Intel Z270.
Любое устройство ввода-вывода делится на два компонента: аппаратный интерфейс и внутреннюю структуру. На рисунке выше упрощенный интерфейс устройства состоит из регистра состояния, предназначенный для получения текущего состояния; регистр команд сообщает устройству, что нужно выполнить определенное действие; регистр данных служит для передачи данных устройству или получения данных от него.
Для взаимодействия CPU с устройствами ввода вывода есть две основные техники - опрос (polling), когда процессор регулярно проверяет, не появилось ли новое событие на устройстве. Либо когда процессор даёт команду устройству и ожидает генерации прерывания от него, которое будет обработано с помощью контроллера прерываний и таблицы обработчиков прерываний.

ОС фактически взаимодействует с устройствами с помощью двух методов: используя явные команды ввода-вывода, они определяют, как ОС должна записывать данные в регистры конкретного устройства, и потому позволяют строить описанные выше протоколы.
Второй способ называется ввод-вывод с отображением памяти. При таком подходе оборудование представляет регистры устройства так, будто они являются ячейками памяти. Для доступа к конкретному регистру ОС выполняет данные загрузки или сохранения, а оборудование переадресует команды устройству вместо основной памяти.
Также важной частью ОС является драйвера устройств (в Linux код различных драйверов занимает ~70% кодовой базы), которые позволяют инкапсулировать низкоуровневые детали взаимодействия и сделать всю остальную часть независимой от конкретных устройств.

После полного знакомства с абстракциями связанными с процессами (виртуализация CPU) и адресного пространства (виртуализация памяти) авторы добавляют ещё один кусочек в пазл виртуализации: систему долговременного хранения.
Первая ключевая абстракция систем хранения - файл. Файл - это просто массив байтов, каждый из которых можно прочитать или записать.
Вторая абстракция - каталог. Каталог, как и файл, имеет низкоуровневое имя - номер индексного дескриптора (inode number), но содержимое каталога весьма специфическое: список пар (имя элемента, номер индексного дескриптора).
При создании файла (вызов функции open()) мы получаем дескриптор файла - уникальное целое число, т.е. идентификатор открытого файла в процессе (в оперативной памяти. на уровне ОС и API) , используемое ОС для доступа к файлу. Дескриптор файла - это возможность, т.е. непрозрачный описатель, позволяющий выполнять определенные операции.

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

Биты полномочий файла - разделены на три группы: что разрешено владельцу файла, что разрешено членам группы и что разрешено всем (прочим). (rwxrwxrwx)

В книге при рассмотрении реализации файловой системы была выбрана vsfs (Very Simple File System) - очень простая файловая система, упрощенная версия файловой системы Unix.

Устройство данной простейшей файловой системы состоит из следующих элементов:

  • данные пользователя;
  • индексные дескрипторы;
  • битовая карта данных;
  • битовая карта индексных дескрипторов;
  • суперблок - информация о файловой системе.

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

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

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

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

  1. Логическое журналирование - записываются только метаданные операции (например: создать файл, переименовать, переместить);
  2. Физическое журналирование - записываются и метаданные и данные, которые должны быть записаны в файл. Медленнее, но гарантирует что даже содержимое файла будет сохранено в случае сбоя.

Практический пример:

1. Программа записывает данные в файл.
2. ОС буферизует эти данные.
3. ФС записывает в журнал операцию: "записать N байт в файл X по смещению Y".
4. Эти записи — это транзакция.
5. После успешной записи транзакции в журнал — выполняется "commit".
6. Только потом данные и метаданные записываются на диск.

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

Иллюстрации работы физического и логического журналов, на обоих рисунках время течёт сверху вниз:

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

Итоги

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

Создано: 15.08.2025
Книги
Назад ко всем постам