itmo_conspects

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

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

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

Лекция 1. Ранние операционные системы

Операционная система - сложная композиция подсистем. Рассмотрим историю возникновения механизмов операционной системы.

Однако зачем нам операционная система и как мы пришли к ее возникновению?

Физик Джон фон Нейман, изучая численные методы решения уравнений на ЭВМ, пришел к такой архитектуре:

Архитектура фон Неймана

и сформулировал принципы его архитектуры:

  1. Однородность памяти: и инструкции, и данные хранятся в одной ячейке памяти RAM (Random Access Memory)

  2. Линейность памяти: байты расположены последовательно

  3. Двоичное кодирование: и инструкции, и данные кодируются в двоичном виде

  4. Программное управление: регистр IP (Instruction Pointer - указатель на текущую программу) определяет, какая команда выполнится следующей - никто внешне не управляет программой, поэтому говорят “поток команд”. Программа останавливается, когда наткнется на инструкцию “Останов” либо на инструкцию, выполнение которой невозможно

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

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

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

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

Распределение ресурсов вычислительным процессам имеет бекграунд из истории общества: если давать все ресурсы сильным, то слабые вымрут, разнообразие исчезнет. Если все раздавать одинаковое количество ресурсов, то конкуренция исчезнет. Поэтому зарождается понятие “государства”, которое задает правила и гарантирует их соблюдение. Операционная система, монополизируя власть и насилие, является абстракцией между пользователями и ПО+АО

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

Первым этапом развития были программы-диспетчеры.

Диспетчеры

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

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

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

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

Архитектура фон Неймана

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

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

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

Архитектура фон Неймана

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

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

В тривиальном случае “прерываем” может быть поменянный битик в ОЗУ, который отслеживается процессором

Теперь рассмотрим “однопрограммную пакетную обработку”

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

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

Второй этап: Мультипрограммные операционные системы

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

Появляется проблема: как управлять ресурсами процессора? Вследствие этого диспетчер начинает обрастать дополнительным функционалом

Лекция 2. Мультипрограммность

Мультипрограммные операционные системы

Дальше появляется потребность больше чем в одной программе в вычислительной машине

Давайте расположим все программы последовательно в оперативной памяти.

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

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

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

Такое переключение процессов называется диспетчеризацией.

Но как решать, когда нужно переключать диспетчеризацию?

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

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

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

picture

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

picture

Вторая проблема - как делить оперативную память между процессами

Решением до сих пор является виртуальная память

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

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

Третьей проблемой стала проблема защиты памяти.

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

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

Но тогда ломается линковка - подпрограммы не могут узнать свои параметры. Поэтому создается костыль - привилегированный режим

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

Теперь при вызове подпрограммы происходит это:

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

Системный вызов (system call, syscall) - обращение пользовательской программы к ядру операционной системы с просьбой выполнить привилегированную операцию или предоставить некоторый системный ресурс

Четвертая проблема - задача планирования ресурсов

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

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

Пятая проблема - универсальный доступ к хранилищу

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

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

Шестая проблема - обеспечение коммуникации между программами

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

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

В 1963 году был создан суперкомпьютер B5000, в которой присутствовала операционная система MCP (Main Control Program)

Начинается 3 этап развития - сетевые операционные системы

Сетевые операционные системы

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

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

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

picture

Здесь 1 верхний пик - это 1 бит, однако для надежности можно сделать, например, 4 пика на 1 бит. Такая модуляция называется амплитудной (Amplitude Modulation, AM)

Другой вариант - менять частоту при постоянной амплитуде. Получаем частотную модуляцию (Frequency Modulation, FM):

picture

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

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

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

Четвертым этапом стало появление универсальных операционных систем

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

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

Лекция 3. История Unix и других универсальных ОС

Четвертый этап начался с потребности создания универсальной операционной системы

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

Специалисты в компании AT&T в лаборатории Bell Labs в конце 60-ых совместно с Массачусетским институтом технологий, разрабатывая суперкомпьютер, написали операционную систему Multics (Multiplexed Information and Computing Service).

После этого с целью разработки универсальной системы Кен Томпсон, Деннис Ритчи и Брайан Керниган разрабатывают операционную систему UNICS (Uniplexed Information and Computing Service). Позднее название меняется на созвучное Unix.

Unix Edition 1 выходит в 3 ноября 1971 года и была написана на ассемблере. Далее на основе этой операционной системы был создан язык B, интерпретатор которого был написан на ассемблере. После этого ядро Unix переписывается на B, выходит Edition 2 в 1972 году.

Используя язык B, они пишут компилятор языка C, который встраивается в Edition 2. Используя язык C операционная система Unix опять переписывается и компилируется в Unix Edition 3

В 1979 выходит Edition 7 с Bourne Shell (или просто Shell) - предком современного Bash

В 1985 выходит последняя публичная редакция Edition 8

Эти ранние версии Unix теперь известны как Research Unix

По антимонопольному соглашению, заключенному в 1956 году между Департаментом юстиции США и AT&T, AT&T не могла заниматься никаким другим бизнесом, кроме бизнеса в сфере телекоммуникаций. Поэтому в 1974 году код Unix попадает в Университет Калифорнии в Беркли, где в конце 1970-ых Билл Джой разрабатывает форк BSD (Berkeley Software Distribution). Позднее из нее выходят FreeBSD, NetBSD, OpenBSD, Dragonfly BSD и другие.

Именно с выхода BSD появляется лицензия BSD License, которая не ставила никаких ограничений в использовании лицензированного ее ПО

Параллельно с этим в Bell Labs разрабатывают коммерческие версии Unix. В 1977 году выходит Programmer’s Workbench (PWB/Unix). Незадолго до распада Bell System выходит Unix System V в 1983 году. Другие компании лицензируют ее и появляются:

Другой технический университет, Стэнфордский, решил заиметь свою операционную систему, создает свое коммерческое предприятие Stanford University Networks (SUN, позднее Sun Microsystems), и на основе BSD создается SunOS в 1982

Стэнфорд решает заново переписать код, используя код коммерческой Unix System V - появляется Solaris. До наших времен дожил его потомок OpenSolaris

Также Microsoft создают свой форк BSD и Research Unix в 1980, называют Xenix

В конце 80-ых в Америке начались компьютеризация и рассвет операционных систем. Как правило это все были форки BSD, рассчитанные на обычного потребителя.

В это время в 1985 появляется компания NeXT Computer, основанная очень небезызвестной личностью. В 1989 выходит их операционная система NeXTSTEP, Apple поглощает NeXT в 1997, преобразует NeXTSTEP в открытую операционную систему Darwin, которая по сей день развивается и является основой для macOS (ранее Mac OS X и OS X)

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

Лицензии того времени приводили к тому, что open-source код можно было сделать проприетарным

В 1983 году в Массачусетском институте технологий профессор Ричард Столлман становится идеологом движения за свободное программное обеспечение. Он выпускает манифест свободного программного обеспечения, в которого написаны 4 свободы свободного ПО:

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

Чтобы регулировать интеллектуальную собственность, появились понятия авторского права и копирайта - запрет что-либо делать с собственностью без явного разрешения автора

Ричард Столлман придумывает копилефт - понятие, означающее, что проект, использующий код с копилефтной лицензией, должен наследовать ее, таким образом оставаясь в общественной собственности. Создается лицензия GPL (General Public License)

Чтобы создать поистине открытую систему, создается проект GNU (рекурсивный акроним от Gnu is Not Unix). Для этого пишется с нуля компилятор GCC (GNU C Compiler), переписываются все библиотеки. Все, что ему оставалось сделать, - ядро будущей ОС

В Хельсинском университете студент Линус Торвальдс увлекается операционными системами. Через знакомых он получает книгу Эндрю Таненбаума. В то время он создал Minix - микроядерная Unix-подобная система, которая использовалась в обучении проектирования ОС. В своих книгах он пропагандирует, что монолитная архитектура и x86 - это тупиковые идеи.

Весь код своей операционной системы Линус пишет с нуля, вдохновляясь на Minix. Эта операционная система распространяется по европейским университетам, а потом попадает и в MIT к Таненбауму.
Эндрю Таненбаум в новостной группе по операционным системам говорит, что Linux устарел. В ходе спора Столлман узнает о Линусе и пишет письмо ему, приглашая в его команду GNU. В ходе этого операционная система получает название GNU / Linux

Linux начинает свое развитие и появляются многочисленные дистрибутивы

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

Microsoft распространяли свою операционную систему MS-DOS через набор дискет и книжечку, как ими пользоваться.

Apple в это время начинает развитие оконного интерфейса. После этого в Linux создает X Window System

Microsoft создают оболочку, отрисовывающую оконный интерфейс, для DOS и называют ее Windows. В Windows 3.1 появляется сетевой интерфейс

Microsoft приняли решение, что графическая оболочка должна быть интегрирована в ядро системы - появляется Windows 95.

В это время в 1993 выходит Windows NT 3.1 Advanced Server. К выходу Windows 2000 появилось разделение на клиентские (Workstation) и серверные (Server) системы

Из Windows 2000 Workstation появились Windows XP, Windows 7, Windows 10, Windows 11. А серверные Windows развивались отдельно: Windows 2003 Server, Windows 2008 Server, Windows 2012 Server и так далее

оси

Лекция 4. Архитектура ОС, часть 1

Архитектура ПО очень схожа с архитектурой зданий и домом - поиск компромиссов

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

Яркий пример - собор Саграда Фамилия в Барселоне. Взявшийся за него в конце XIX века архитектор Антонио Гауди, придумавший уникальные архитектурные решения (в частности, подгонка каждого каменного блока), не успел его достроить, из-за чего он почти сто лет как не достроен

Сейчас выделяют 5 уровней архитектур:

На этой лекции будет разбираться функциональная архитектура

Функциональная архитектура

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

Выделим метафункции ОС:

  1. Управление разработкой и исполнением пользовательского ПО

    1. Высокоуровневый API для разработки ПО

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

    2. Управление исполнением программы

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

    3. Обнаружение и обработка ошибок

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

    4. Высокоуровневый доступ к устройствам ввода-вывода

      Это работа компьютерных мышек, клавиатур, веб-камер, принтеров и т.п.

    5. Управление хранилищем

      Пример: имеем диск с файловой системой NTFS (или EXT4) и флешка с FAT32. Нужно перенести каталог с файлам. Хранилища у нас с совсем разными структурами, поэтому ОС нужно уметь работать с ними прозрачно

    6. Мониторинг использования ресурсов

      Чтобы операционной системе построить график использования процессора, нужно использовать этот же самый процессор

  2. Оптимизация использования ресурсов

    1. Механизм для решения многокритериальных задач

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

      • всегда занятой процессор
      • всегда занятая память
      • всегда занятой диск

      И другие компоненты. Для этого используют суперкритерий (другое название свертка):

      supercritiria

      Здесь k_i - критерий оптимальности использования какого-то ресурса, а α, β, γ - веса этих критериев. Цель - максимизировать k с крышечкой. Далее алгоритм думает, как распределять ресурсы

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

      conditional supercritiria

    2. Цикл Деминга (Цикл PDCA)

      Цикл PDCA состоит в следующем:

      PDCA Cycle

      • Plan - планирование действия
      • Do - действие
      • Check - проверка текущего состояния
      • Act (или Adjuct) - корректировка направления

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

  3. Поддержка администрирования и эксплуатации

    1. Диагностика - средства, которые в автономическом режиме прогнозируют и анализируют отказ компонентов

    2. Восстановление - автоматизация восстановления

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

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

    1. Обновление - архитектурно должны быть заложены механизмы обновления ОС

    2. Кастомизация - способность изменять функционал под требуемые нужды (например, изменение ядра)

Лекция 5. Архитектура ОС, часть 2

Информационная архитектура

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

  1. Управление процессами

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

    Управление процессами строится на двух объектах: дескриптор процесса (или PCB, Process Control Block) и очередь

    Дескриптор хранит информацию

    • об идентификации процесса (PID - Process ID, UID - User ID, PPID - Parent Process ID и другие)
    • о ресурсах (выделенные странички в памяти, сокеты и другие)
    • об истории (для использования планировщиком)

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

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

    Очередь

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

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

    Управление памятью же стоит на виртуальной памяти и защите памяти

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

    Защита памяти - это управление правами доступа к некоторым участкам памяти для процессов

  3. Управление файлами

    Файловую систему представляют две сущности: файл и каталог

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

    В Windows же каталог и файл - отдельные сущности, а в Linux все - это файл.

    В Linux файл может храниться в двух каталогах одновременно - файл определяется при помощи идентификатор, называемого айнодом, и в Linux можно создать два файла с разными именами и в разных каталогах с одним айнодом (по сути жесткая ссылка)

  4. Управление внешними устройствами

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

    Лет 20 назад драйвера вручную линковали с ядром, а затем его компилировали

    Потом в Microsoft, входя в игровую индустрию с разнообразными контроллерами, захотело сделать драйверы более удобными. Такая фича стала называться “Plug-And-Play”: при подключении устройство отправляло по проводу свой идентификатор, операционная система считывала его, из своей базы данных доставало нужный драйвер и включало его

  5. Защита данных и администрирования

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

  6. Пользовательский интерфейс

    В качестве пользовательского интерфейса выступают CLI и GUI

    CLI (Command Line Interface) - интерфейс командной строки. GUI (Graphical User Interface) - графический интерфейс пользователя

    В Linux основным является CLI, а в Windows - GUI в качестве нативного для ядра

Системная архитектура

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

Код ядра:

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

Поэтому со временем выработалось 5 принципов построения архитектуры ОС:

  1. Модульная организация кода
  2. Функциональная избыточность - закладываем больше функционала, чем нужно обычному пользователю
  3. Функциональная избирательность - возможность это все отключать
  4. Параметрическая универсальность - не хардкодить константы
  5. Иерархическая вычислительная система

Лекция 6. Архитектура ОС, часть 3

Основная проблема, стоящая перед системной архитектурой, - какой код вносить в ядро и какой код выносить

Первая концепция, которая появилась, - монолитная архитектура ядра

Монолитная архитектура

В “монолите” выделяют 3 слоя:

  1. Главная программа принимает системные вызовы. Главная программа знает, какой процесс его вызвал, что за системный вызов и аргументы вызова, а после передает вызов в нужный сервис
  2. Сервисы выполняют определенный вызов, используя утилиты. Если сервис не может совершить операцию (например, мало оперативной памяти), то вызов передается обратно в главную программу
  3. Утилиты - часть ядра, задействующая аппаратное обеспечение (по факту драйвера)

monolith

После этого появилась многослойная монолитная архитектура

Многослойная монолитная архитектура

В многослойной монолитной архитектуре слоев стало больше:

  1. Аппаратное обеспечение
  2. Аппаратная поддержка ядра определяется чипсетом и кодом в микроконтроллерах на материнской плате
  3. Машинно-зависимые модули (HAL - Hardware Abstraction Layer, драйвера или модули ядра) абстрагируют код ядра от аппаратного обеспечения
  4. Базовые механизмы ядра - базовые детерминированные алгоритмы
  5. Менеджер ресурсов - стохастические алгоритмы, принимающие решения по организации ресурсов
  6. Системные вызовы и API

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

multilayermonolith

Ядро становилось все больше и больше, а оперативная память не увеличивалась такими большими темпами - поэтому ядро стало занимать все большую часть памяти

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

Появляется микроядерная архитектура

Микроядерная архитектура

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

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

microkernel

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

processes

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

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

Другие архитектуры

Модульная архитектура

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

modules

Собирают биолога, математика и физика и просят их придумать что-нибудь, чтобы всегда выигрывать на бегах. Через месяц они снова собираются и рассказывают «о проделанной работе». Биолог:
— За месяц я вывел породу лошадей, которые отличаются необыкновенной скоростью и почти всегда выигрывают. Для того, чтобы довести ее до ума мне нужно еще пару месяцев.
Математик:
— Я почти разработал теорию, которая описывает вероятность выиграша в каждом конкретном забеге, теперь мне еще нужно примерно полгода, $1000 и помощник для того чтобы проверить ее на практике, а также снизить статистические погрешности.
Физик:
— Для того, чтобы продолжить работу мне нужен $1000000, хорошо укомплектованная лаборатория, штат сотрудников и еще где-то лет десять. Но зато у меня уже готова теория победы жидкого сферического коня в вакууме.

Наноядерная архитектура

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

Наноядерная архитектура применяется в системах виртуализации

Экзоядерная архитектура

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

Гибридная архитектура

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

Лекция 7. Процессы

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

Процесс (Process) - совокупность набора исполняемых команд, ассоциированных с ним ресурсов и контекста исполнения, находящиеся под управлением операционной системы

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

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

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

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

Исполнение потоков регулируется механизмами вытесняющей многозадачности

По факту процесс в Linux является потоком, а процесс - контейнером ресурсов

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

Со временем появилось понятие легковесного потока

Легковесный поток (Flyweight Thread или Fiber) - набор исполняемых команд в контексте управления некоторого потока

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

После этого появлется понятие задания/контрольной группы. Они задают ограничения ресурсов для группы процессов

Объект задания (Job) в Windows - именуемый, защищаемый, совместно используемый объект, управляющий атрибутами процессов, связанных с ними (например, размер рабочего набора и приоритет процесса или завершение всех процессов, связанных с заданием) (*тык*)

Контрольная группа (cgroup) в Linux - группа процессов, для которой механизмами ядра наложена изоляция и установлены ограничения на некоторые вычислительные ресурсы (*тык*)

a

Что должна уметь подсистема управления процессов:

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

Также процесс должен порождаться другим процессом. В Linux процессы образуют дерево процессов, на самом деле даже два. В одном дереве корень - это процесс с PID = 1, а второе - PID = 2

Второй процесс - это так называемый [KThreadD], от Kernel Thread Daemon. Это демон (фоновый процесс, общение с которым возможно через сигналы или сокеты), от которого порождаются потоки ядра

Первый процесс - это процесс init или systemD. От первого процесса порождаются все другие процессы

Сами первый и второй процессы являются детьми процесса с PID = 0 - но по факту такого процесса не существует

a

В Linux процессы порождаются клонированием через системные вызовы fork и exec*:

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

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

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

Но что, если родитель завершает свою работу, когда его ребенок живой? Тогда процесс становится осиротевшим - его родителем теперь становится init/systemD

Но если родитель не может прочитать код выхода своего ребенка (например, если он приостановлен), то ребенок становится зомби-процессом. Зомби-процессы опасны тем, что занимают строчку в таблице процессов, а ее размер ограничен (в Linux 2^16). Если зомби-процессы заполонили все свободные места, то случается так называемый зомби-апокалипсис - состояние, когда зомби-процессов настолько много, что нельзя создать новый

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

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

Лекция 8. Управление процессами

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

Тогда можем сразу выделить два состояния процесса: “ожидание” и “исполнение”

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

a

Такая модель получила название двухуровневой (Two-State Process Model)

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

Поэтому состояние ожидание разделилось на “готовность” (Ready или Runnable) и “ожидание ввода/вывода” (Wait)

В переходе из “готовности” в исполнение есть одна очередь, а из “ожидания ввода/вывода” несколько очередей для разных устройств ввода/вывода. Из “ожидания ввода/вывода” процесс переходит в готовность

a

Такая трехуровневая система (Three-State Process Model) реализована в каждой операционной системе. Заметим, что операционная система не может инициализировать дальнейшую работу процесса, который ждет ввод/вывод, иначе сломается поток управления. Поэтому “ожидание ввода/вывода” называет непрерываемым сном (Disk Sleep или Uninterruptable Sleep)

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

Для этого сделали новое состояние - “сон” (или прерываемый сон, Interruptable Sleep)

a

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

После этого появилось состояние “остановлен”. В него попадают процессы, которые получили сигнал SIGSTOP (этот сигнал, наряду с SIGKILL, является сигналом, для которого нельзя переопределить обработчик)

Из состояния “остановлен” можно выйти только при сигнале SIGCONT в готовность. Запущенный в терминале процесс можно перевести в остановленное состояние, если нажать Ctrl+Z

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

a

Также нам нужно состояние для завершения процесса. В Unix и Unix-like любой процесс перед завершением переходит в “зомби-состояния” (Zombie). В Windows он переходит в состояние “завершение” (Terminated), в ходе которого операционная система высвобождает ресурсы процесса

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

a

Все выше указанные состояния используются для диспетчеризации процессов

Для планирования процессов в операционных системах используют 4 уровня планирования:

Краткосрочный уровень используется прямо в диспетчеризации процессов. В нем задача выбрать следующий для исполнений процесс (то есть определить, что делать в следующую ~1 мс)

Уровень очередей ввода и вывода используется для планирования процессов внутри состояния ожидания ввода/вывода

Для среднесрочного уровня добавляются два состояния “готовность вне RAM” и “ожидание ввода/вывода вне RAM” (также их называют Suspended and Ready, Suspended and Waiting, Swapped out and Ready, Swapped out and Waiting)

Если у процесс низкий приоритет и из “готовности” он доберется в “исполнение” через долгое время (порядка минут), то его целесообразнее перенести в файл подкачки. Таким образом, освобождается память для более быстрых процессов. Также до и после состояний “готовность вне RAM” и “ожидание ввода/вывода вне RAM” стоят синхронизированные очереди процессов

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

Пятерку “готовность”, “исполнение”, “ожидание”, “рождение”, “завершение” называют пятиуровневой моделью (Five-State Process Model)

a

Помимо них, в Windows используются состояния Standby (в нем процессы непосредственно перед исполнением) и Transition (в нем процессы, стек ядра которых были выгружены из памяти), а состояние Wait является более обширным понятием

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

This site is open source. Improve this page.