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

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

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

Ядро - это ядро ​​операционной системы; он действует как уровень абстракции между ресурсами (такими как ЦП, ОЗУ и устройства ввода-вывода) и процессами / приложениями, которые их используют. Ядро обрабатывает управление ресурсами, так что программистам это не нужно, но программисты могут получить доступ к функциям ядра с помощью системных вызовов. В этом суть операционных систем.

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

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

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

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

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

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

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

Закон Амдала гласит, что потенциальное ускорение за счет распараллеливания для системы составляет 1 / ((1-p) + (p / n)), где n - количество процессоров, а p - пропорция система, которую можно распараллелить. По мере того, как вы добавляете все больше и больше процессоров, максимальное ускорение начинает приближаться к 1 / (1-p). Конечно, из-за накладных расходов на добавление дополнительных процессоров эта верхняя граница труднодостижима.

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

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

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

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

Наименее недавно использованные (LRU) - очень простой алгоритм замены страниц; просто замените страницу, которая использовалась не так давно. Это неэффективно, так как требует от системы записи каждого использования страницы. Вместо этого LRU часто аппроксимируется алгоритмом «второго шанса».

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

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

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

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

Контроллер прямого доступа к памяти (DMA) может улучшить производительность всей системы, минуя ЦП и передавая данные напрямую между устройствами ввода-вывода и памятью. Еще один способ повысить производительность ввода-вывода - использовать буферизацию. Буфер, известный как «спул», может использоваться процессами для приема или передачи данных ввода-вывода. Затем устройства считывают данные из буфера в своем собственном темпе, не позволяя медленным устройствам замедлять процессы ЦП. Это также полезно для таких устройств, как принтеры, к которым обращаются несколько процессов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Помимо отслеживания распределения файловых блоков, мы также хотели бы отслеживать свободные блоки для быстрого доступа и распределения. Простое решение - представить все блоки в файловой системе с помощью битового вектора, где 1 означает занятые, а 0 - свободные. Это занимает мало места. Другое решение - рассматривать свободные блоки как связанный список, чтобы каждый свободный блок имел ссылку на следующий. Однако это замедляет обход. Более быстрое решение - разделить блоки свободного пространства на группы размера n, где первый блок является индексным блоком, а другие (n-1) блоки пусты. Индексный блок имеет n указателей - по одному для каждого из других блоков в группе и по одному для индексного блока следующей группы. По сути, мы можем перемещаться по n блокам за раз вместо того, чтобы перемещаться по блокам. Это намного быстрее.

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

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

Однако зеркалирование по-прежнему стоит дорого, даже при использовании дешевого оборудования. Может быть дешевле использовать интеллектуальные методы для повышения скорости и избыточности. Одним из примеров является чередование, метод, при котором последовательные сегменты битов разделяются или «чередуются» на нескольких дисках. Затем данные в полосе могут быть одновременно прочитаны со всех дисков, что приведет к увеличению скорости чтения в n раз. Это позволяет увеличить скорость чтения, аналогичную зеркалированию, без необходимости в дополнительном пространстве для хранения или увеличения времени записи. Самым большим недостатком чередования дисков является то, что оно сильно затрудняет избыточность - потеря любого диска приведет к потере всех данных в системе, если не используется такой метод восстановления данных, как четность.

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

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