Это я пишу на темы, которые, я думаю, составляют информатику 101. Я надеюсь, что это может быть полезно для людей. Итак, без лишних слов, давайте начнем с операционных систем.
Что такое операционная система?
Операционная система выполняет две функции:
(1) распределитель ресурсов, то есть управляет всеми ресурсами компьютера. Он решает между конфликтующими запросами на эффективное и добросовестное использование ресурсов.
(2) программа управления, то есть контролирует выполнение программ, чтобы предотвратить ошибки и ненадлежащее использование ресурсов. компьютер.
Как правило, операционная система также состоит из двух основных компонентов: ядро, которое является ядром ОС и контролирует все в системе, и оболочку (например, CMD), которая это интерфейс для доступа к службам, предоставляемым ОС.
Для более глубокого визуального понимания операционных систем вы можете посмотреть это видео CrashCourse здесь. В противном случае, давайте перейдем к процессам и планированию.
Процессы и планирование
Что такое процесс?
Люди повторяют, что процесс «это просто выполняемая программа». Процесс — это экземпляр запущенной программы. Наглядный пример процессов можно увидеть, например, в мониторе активности MacOS:
Если вы откроете свой собственный, вы увидите, что программное обеспечение на самом деле может иметь несколько процессов. Процесс в целом имеет образ исполняемого машинного кода, связанного с программой, некоторую память, дескрипторы ресурсов, выделенных для процесса, атрибуты безопасности, такие как процесс владельца и разрешений, а также состояния процессора.
Когда процесс выполняется, он меняет состояния. Чтобы обеспечить максимальную производительность, ОС должна понимать состояние всех этих процессов и иметь возможность разумно создавать новые, переключаться между ними, приостанавливать их, приостанавливать и т. д.
Программа – это пассивный объект, хранящийся на диске (в виде исполняемого файла). Процесс активен.
Программа становится процессом, когда исполняемые файлы загружаются в память. Выполнение программы происходит через оболочку (будь то графический интерфейс, например, щелчок мышью или что-то еще).
Слово «память» здесь ключевое.
Процесс владеет ресурсами.
Стек используется для локальных переменных, а куча используется для динамического выделения памяти. Для более подробного объяснения.
Для краткого объяснения того, что означает стек и куча. Джефф Хилл пишет:
- стек — это память, выделенная в качестве рабочего пространства для потока выполнения. При вызове функции в верхней части стека резервируется блок для локальных переменных и некоторых учетных данных. Когда эта функция возвращается, блок становится неиспользуемым и может быть использован при следующем вызове функции. Стек всегда резервируется в порядке LIFO (последний пришел — первый вышел); последний зарезервированный блок всегда является следующим освобождаемым блоком. Это упрощает отслеживание стека; освобождение блока из стека — это не что иное, как корректировка одного указателя.
- куча — это память, выделенная для динамического выделения. В отличие от стека, для выделения и освобождения блоков из кучи не существует обязательного шаблона; вы можете выделить блок в любое время и освободить его в любое время. Это значительно усложняет отслеживание того, какие части кучи выделены или свободны в любой момент времени; существует множество настраиваемых распределителей кучи, позволяющих настроить производительность кучи для различных шаблонов использования.
Каждый поток получает стек, в то время как обычно для приложения существует только одна куча (хотя нередко бывает несколько куч для разных типов распределения).
Стек управляется и оптимизируется процессором довольно близко. Однако важно отметить, что когда функция существует, все ее переменные извлекаются из стека (и, следовательно, теряются навсегда). Куча не так жестко управляется процессором. Это свободно плавающая область памяти (и она больше), поэтому она полезна, если вам нужно выделить большой блок памяти (например, большой массив или большую структуру), и вам нужно хранить эту переменную вокруг долгое время (как глобальный). Но вы должны управлять памятью, т. е. вы отвечаете за выделение и освобождение переменных. Если вы не освободите () свою память (освобождая ее, когда она вам больше не нужна), в программе возникнет утечка памяти. Это означает, что память в куче по-прежнему будет выделена (и не будет доступна другим процессам).
Почему это важно?
Чтобы операционная система выполняла свою работу должным образом и максимизировала производительность, операционная система управляет блоком управления процессом (PCB), который помогает ей эффективно управлять различными процессами, сохраняя текущее состояние в печатной плате, переключаясь между их и перезагрузка определенных процессов позже
Плата содержит информацию, связанную с каждым процессом.
- Состояние процесса: выполняется, ожидает и т. д.
- Счетчик программ: расположение инструкции для следующего выполнения
- Регистры ЦП: содержимое всех регистров, ориентированных на процессы. Информация о планировании ЦП: приоритеты, указатели очередей планирования.
- Информация об управлении памятью: память, выделенная процессу
- Учетная информация: использование ЦП, время, прошедшее с момента запуска, ограничения по времени
- Информация о состоянии ввода-вывода: устройства ввода-вывода, выделенные для процесса, список открытых файлов
Как операционная переключается между различными процессами?
Операционная система изменяет запущенный процесс с помощью переключения контекста. Когда ЦП переключается на другой процесс, система должна сохранить состояние старого процесса и загрузить сохраненное состояние для нового процесса с помощью переключения контекста. Контекст процесса представлен на плате.
Однако переключение контекста занимает немного времени. Это время переключения контекста является накладным, когда система не выполняет никакой полезной работы при переключении. Чем сложнее операционная система и печатная плата, тем дольше происходит переключение контекста. [Время зависит от аппаратной поддержки; некоторое оборудование предоставляет несколько наборов регистров на ЦП, что означает, что несколько контекстов могут быть загружены одновременно].
Переключение контекста имеет накладные расходы. Зачем переключать контекст?
Переключение контекста позволяет создать иллюзию одновременной работы нескольких приложений даже на одном процессоре. Это позволяет запускать несколько процессов на машине. Вы можете запускать несколько приложений, не закрывая их, например. запуск Chrome одновременно со Spotify.
Переключение контекста позволяет выполнять больше работы: процессы, связанные с вводом-выводом, могут выполняться одновременно с процессами, связанными с процессором. Большинству процессов в любом случае требуются только короткие пакеты ЦП, поэтому переключение между несколькими — хорошее решение.
Планирование процесса
Планировщик процессов выбирает один из доступных процессов для следующего выполнения на ЦП. Он поддерживает очередь планирования процессов:
Существует очередь заданий, в которую входят все процессы в системе, процессы в очереди готовности (набор всех процессов, находящихся в основной памяти, готовых и ожидающих выполнения) и очередь устройств (набор процессов, ожидающих устройства ввода-вывода).
Планирование можно разбить на два отдельных этапа: долгосрочный и краткосрочный.
- Долгосрочный планировщик (планировщик заданий): выбирает, какие процессы следует поставить в очередь готовности; он вызывается нечасто (секунды, минуты), что может быть медленным; и определяет, сколько процессов может выполняться одновременно (контролирует степень мультипрограммирования).
- Краткосрочный планировщик (планировщик ЦП): выбирает, какой процесс должен выполняться следующим, и выделяет ЦП. Иногда единственный планировщик в системе. Краткосрочный планировщик вызывается часто (миллисекунды), поэтому должен быть быстрым.
Процессы могут быть описаны как:
- Процесс, связанный с вводом-выводом — тратит больше времени на ввод-вывод, чем на вычисления, много коротких всплесков ЦП
- Процесс с привязкой к ЦП — тратит больше времени на вычисления; несколько очень длинных всплесков ЦП
Все запускается в готовой очереди при добавлении долгосрочным планировщиком, выполняется на ЦП в течение некоторого времени, а затем перемещается в другие очереди по мере необходимости. Долгосрочный планировщик стремится к хорошему сочетанию процессов.
Максимальная загрузка ЦП достигается при многозадачности. Представленный выше цикл ЦП-ввод-вывод состоит из цикла выполнения ЦП и ожидания ввода-вывода, за которым следует пакет ввода-вывода. Распределение всплесков ЦП является основной проблемой.
Краткосрочный планировщик выбирает процессы из очереди готовности и выделяет ЦП одному из них. Очередь может быть упорядочена различными способами.
Решения о планировании ЦП могут приниматься, когда процесс:
1. Переключение из рабочего состояния в состояние ожидания
2. Переключение из рабочего состояния в состояние готовности
3. Переключение с ожидания на готовность
4. Завершает
Планирование под номерами 1 и 4 является неупреждающим
Все остальные планирования являются упреждающими (рассмотрите возможность доступа к общим данным; рассмотрите вытеснение в режиме ядра; рассмотрите прерывания, возникающие во время важных операций ОС)
Алгоритмы планирования ЦП (краткосрочный планировщик)
Эффективные алгоритмы планирования ЦП необходимы для эффективного использования ЦП и быстродействия операционной системы.
Различные алгоритмы лучше подходят для разных типов процессов в зависимости от продолжительности (привязка к ЦП/привязка к вводу-выводу).
Критерии производительности алгоритма планирования
- Использование ЦП: процент времени, в течение которого ЦП выполняет процесс.
- Время ожидания: общее время ожидания процесса в очереди готовности.
- Время обработки: время между поступлением процесса в очередь готовности и завершением его выполнения.
- Время отклика: время между прибытием процесса и получением первого ответа (зависит от того, сколько времени требуется процессу, чтобы дать ответ, для этого может не потребоваться его завершение).
- Пропускная способность: количество процессов, выполненных в единицу времени (явно зависит от продолжительности процесса).
Мы также можем запросить среднее (среднее) время ожидания/обработки/ответа или общее (сумма) время ожидания/ время обработки/ответа или максимальное/минимальное время ожидания/обработки/ответа для набора процессов.
Алгоритмы планирования
Обслуживание в порядке живой очереди (FCFS)
Планируется, что первый процесс, который придет первым, будет запущен первым.
Преимущества алгоритма FCFS:
+ простой
+ только одно переключение контекста
Недостатки алгоритма FCFS:
- среднее время ожидания обычно низкое.
- среднее время ожидания сильно варьируется: зависит от порядка поступления процессов.
- Процессы, привязанные к ЦП, могут нагружать ЦП ( представьте себе систему с одним процессом, привязанным к ЦП, и множеством процессов, связанных с вводом-выводом)
Самая короткая работа сначала (SJF)
Свяжите с каждым процессом длину его следующего пакета ЦП. Используйте эти длины, чтобы запланировать процесс с кратчайшим временем. SJF оптимален — дает минимальное среднее время ожидания для заданного набора процессов.
Трудность заключается в том, чтобы узнать длину следующего запроса ЦП… возможно, спросить пользователя?
Кратчайшее оставшееся время сначала (SRTF)
Алгоритм кратчайшего оставшегося времени — это упреждающий алгоритм кратчайшего задания в первую очередь.
Преимущества алгоритма SJF:
+ Коротким процессам не нужно ждать завершения длинных процессов перед выполнением (особенно если используется упреждающее планирование). То есть процессы, привязанные к ЦП, не могут перегружать ЦП.
+ Максимизирует пропускную способность (для этого представьте себе очередь, в которую постоянно поступают процессы).
+ Среднее время ожидания меньше (для того же набора процессов), так как ни один процесс не ожидает завершения дольше всего.
Недостатки алгоритма SJF:
− Риск голодания для длинных процессов; или, как вариант, длительное время ожидания.
— Несколько переключений контекста для каждого процесса, если они упреждающие.
— Можем ли мы надежно оценить продолжительность процесса до его выполнения?
— Накладные расходы при вставке процессов в отсортированную очередь.
Приоритетное планирование
Свяжите приоритет с каждым процессом. С каждым процессом связан номер приоритета (целое число). Чем меньше число, тем выше приоритет. Сначала запланируйте процесс с наивысшим приоритетом.
Приоритетное планирование может быть упреждающим или неупреждающим.
SRTF — это особый случай приоритетного планирования, когда приоритет равен оставшемуся времени выполнения процесса.
- Проблема заключается в зависании — процессы с низким приоритетом могут никогда не выполняться.
- Решение заключается в старении — с течением времени увеличивайте приоритет процесса.
Преимущества приоритетного планирования:
+ Короткое время ожидания для высокоприоритетных процессов (например, интерактивных пользовательских программ).
+ Пользователи (или администратор) имеют некоторый контроль над планировщиком.
+ Сроки можно соблюсти, если дать процессам высокий приоритет.
Недостатки приоритетного планирования:
− Риск голодания для процессов с низким приоритетом; или, как вариант, длительное время ожидания. [хотя риск голодания можно уменьшить, используя схему старения: постепенно повышайте приоритет процесса с течением времени]
— несколько переключений контекста для каждого процесса, если он упреждающий.
— Накладные расходы при вставке процессов в отсортированную очередь.
Круговое планирование (RR)
Алгоритм циклического планирования имеет квант времени: продолжительность времени, в течение которого каждый процесс может работать (обычно 10–100 мс). Когда процесс выполняется в течение этого промежутка времени, он вытесняется, и может быть запланирован другой процесс из очереди готовности.
Производительность зависит от q:
- Если q большое, циклический алгоритм имеет тенденцию к принципу "первым пришел - первым обслужен";
- Если q мало, накладные расходы на переключение контекста становятся значительными.
- Эвристика эффективности: следует выбирать квант, превышающий 80% всплесков ЦП.
Преимущества циклического алгоритма:
+ Нет голодания.
+ Каждый процесс должен ждать не более (n-1) * q единиц времени, прежде чем начать выполнение.
+ Справедливое распределение ЦП между процессами.
Недостатки алгоритма циклического перебора:
− Плохое среднее время отклика
− Время ожидания зависит от количества процессов, а не от приоритета.
— особенно большое количество переключений контекста для каждого процесса, поэтому большие накладные расходы;
— Трудно уложиться в сроки, потому что время ожидания обычно велико.
Планирование многоуровневой очереди
Идея состоит в том, чтобы разделить очередь готовности на несколько очередей: каждый процесс назначается определенной очереди; каждая очередь имеет другой алгоритм планирования. Готовая очередь разделена на отдельные очереди, например: основной (интерактивный) и фоновый (пакетный). Процесс постоянно находится в заданной очереди.
Каждая очередь имеет собственный алгоритм планирования:
передний план — RR
задний план — FCFS
Также должен быть алгоритм планирования для выбора между очередями. Обычно это упреждающий приоритет с фиксированным приоритетом. Иногда передний план может иметь абсолютный приоритет; фоновые процессы запускаются только тогда, когда очередь переднего плана пуста.
Планирование должно выполняться между очередями: планирование с фиксированным приоритетом; (т. е. обслуживать всех с переднего плана, а затем с заднего). Возможность голодания.
Итак, мы используем квант времени — каждая очередь получает определенное количество процессорного времени, которое она может распределить между своими процессами; т. е. 80% на передний план в RR и 20% на фон в FCFS.
Если процессы можно разделить на группы, мы можем использовать многоуровневое планирование очередей: 1 конечное количество приоритетов, по одной очереди на каждый уровень приоритета; — напр. 2 очередь для процессов переднего плана (например, веб-браузер) и одна для фоновых процессов (например, дефрагментация диска).
Разные потребности во времени отклика => разные потребности в расписании.
Планирование многоуровневой очереди обратной связи
Подобно многоуровневому планированию очередей, но процессы могут перемещаться между очередями.
Старение может быть реализовано в приоритетном планировании. В дополнение к очередям и алгоритмам их планирования для многоуровневого планирования очередей нам нужны:
— механизм принятия решения о том, когда продвигать процессы
— механизм принятия решения о том, когда понижать процессы
— механизм для принятия решения о том, к какой очереди процесс присоединится изначально.
Давайте рассмотрим пример:
Здесь есть три очереди:
Q0: RR с квантом времени 8 миллисекунд/единицы времени
Q1: Квантом времени RR 16 миллисекунд/единицы времени
Q2: FCFS
Все новые задания попадают в верхнюю очередь (RR q=8). Если он не завершается через 8 миллисекунд выполнения, они переходят к следующему (RR q = 16); • Если через 16 миллисекунд выполнения все еще не завершено, перейти к последней очереди, в которой работает FCFS.
Приоритетное планирование может быть введено. Создайте n очередей, по одной на каждый уровень приоритета; очереди с более высоким приоритетом получают больше процессорного времени. Каждый процесс входит в очередь, соответствующую его приоритету. После того, как процесс находится в системе в течение некоторого времени, его приоритет повышается, так что он перемещается в очередь с более высоким приоритетом.
Многопроцессорное планирование
ОС может иметь несколько процессоров, используемых для распределения нагрузки на процессоры. Эта проблема может быть сложной, если ЦП имеют разные возможности (поэтому только определенные задания могут выполняться на определенных ЦП).
Существует 2 варианта многопроцессорного планирования:
Асимметричная многопроцессорность (один процессор управляет всем планированием)
При асимметричной многопроцессорной обработке один процессор принимает все решения по планированию, обрабатывает ввод-вывод и другие действия системы.
Остальные процессоры выполняют только пользовательский код.
Потребность в совместном использовании данных снижается, поскольку только один процессор обрабатывает все системные процессы.
Симметричная многопроцессорность (каждый процессор сам себя планирует)
Все основные современные ОС поддерживают симметричную многопроцессорность. В симметричной многопроцессорной обработке каждый процессор выполняет собственное планирование.
Может быть одна очередь готовности или очередь для каждого процессора. Что бы ни использовалось, каждый процессор выбирает процесс для выполнения из очереди готовности.
Для эффективного использования ЦП (высокая загрузка) требуется балансировка нагрузки для равномерного распределения. Для этого есть два подхода:
• Пуш-миграция: определенный процесс регулярно проверяет нагрузку на каждый процессор и перераспределяет ожидающие процессы.
• Миграция по запросу: неиспользуемый процессор извлекает ожидающее задание из очереди занятого процессора.
Многопроцессорность использует несколько (физических) ЦП для параллельного выполнения процессов.
Гиперпоточность (также известная как Симметричная многопоточность) позволяет то же самое, но с использованием нескольких логических процессоры.
Логические процессоры совместно используют аппаратное обеспечение ЦП (кэш, шины и т. д.) и несут ответственность за собственную обработку прерываний. Логические процессоры создают впечатление, что вместо одного процессора 2: они могут выполнять вычисления с плавающей запятой для одного процесса и выполнять арифметические/логические вычисления для другого.
