Процессы - Morozov-5F/operational-system-docs GitHub Wiki

Процесс – экземпляр выполняемой программы, включая текущие значения счетчика команд, регистров и переменных. Концептуально, у процесса есть свой (виртуальный) ЦП. Процесс – это своего рода действие. У него есть программа, входные и выходные данные и состояние. Два экземпляра одной программы – разные процессы.

Есть четыре основных события, приводящих к созданию процессов:

1. Инициализация системы.
2. Выполнение работающим процессом системного вызова, предназначенного для создания процесса.
3. Запрос пользователя на создание нового процесса.
4. Инициация пакетного задания.

Процессы завершаются в силу следующих обстоятельств:

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

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

В UNIX процесс, все его дочерние процессы и более отдаленные потомки образуют группу процессов. К примеру, сигнал с клавиатуры достигает каждого процесса в группе и каждый процесс волен интерпретировать его по-своему. Ещё пример – процесс начальной загрузки компьютера init, который запускает остальные процессы в системе.

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

Существует три состояния процесса:

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

Диаграмма переходов между состояниями:

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

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

Смена процессов происходит по прерыванию. Это может быть прерывание от таймера или устройства ввода-вывода.

Схема работы низшего уровня ОС при возникновения прерывания:

1. Оборудование помещает в стек счетчик команд и т. п.
2. Оборудование загружает новый счетчик команд из вектора прерывания.
3. Процедура на ассемблере сохраняет регистры.
4. Процедура на ассемблере устанавливает указатель на новый стек.
5. Запускается процедура на языке C, обслуживающая прерывание (как правило, она считывает входные данные и помещает их в буфер).
6. Планировщик принимает решение, какой процесс запускать следующим.
7. Процедура на языке C возвращает управление ассемблерному коду.
8. Процедура на ассемблере запускает новый текущий процесс.

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

Предположим, что процесс проводит часть своего времени p в ожидании завершения операций ввода-вывода. При одновременном присутствии в памяти n процессов вероятность того, что все n процессов ожидают завершения ввода- вывода (в случае чего процессор простаивает), равна p^n. Тогда время задействования процессора вычисляется по формуле:

Время задействования ценрального процессора = 1 − p^n.

Параметр n называется степенью многозадачности.

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

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

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

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

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

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

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

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

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

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

1. Обработка сигналов – какой поток должен обрабатывать сигнал, посланный процессу?
2. Что будет при разветвлении многопоточного процесса – будет ли у него несколько потоков, или же только один?

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

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

Межпроцессорное решает следующие проблемы:

1. Как один процесс может передавать информацию другому процессу?
2. Как несколько процессов могут работать совместно без создания помех?
3. Как определить правильную последовательность работы процессов?

Эти вопросы (кроме первого, он решается просто, благодаря общему адресному пространству) применимы и к потокам.

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

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

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

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

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

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

send(destination, &message);
receive(source, &message);

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

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

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

Существует два типа процессов:

1. Ограниченные скоростью работы ввода-вывода (те, которые много с ним работают).
2. Ограниченные скоростью вычислений.

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

1. При создании дочернего процесса, какой из них запускать?
2. Какой процесс из готовых выполнить, если выполняемый процесс завершился?
3. Какой процесс выбрать при блокировании выполняемого процесса на семафоре и при ожидании ввода-вывода?
4. После ввода-вывода, какой процесс запускать (тот, который ждал ввода-вывода или другой)?
5. Какой процесс выбирать при прерывании от системного таймера (по очереди – неприориетный алгоритм, или по приоритету процесса – приоритетный)?

Рассмотрим три типа систем:

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

Общие задачи:

1. Равнодоступность — предоставление каждому процессу справедливой доли времени центрального процессора.
2. Принуждение к определенной политике — наблюдение за выполнением установленной политики.
3. Баланс — поддержка загруженности всех составных частей системы.

Для пакетных систем:

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

Для интерактивных систем:

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

Для систем реального времени:

• соблюдение предельных сроков — предотвращение потери данных;
• предсказуемость — предотвращение ухудшения качества в мультимедийных системах.

1. Первым пришел – первым ушел
2. Сначала самое короткое задание. Нужно знать заранее время выполнения задания.
3. Приоритет наименьшему времени выполнения. Приоритетная версия предыдущего алгоритма.

1. Циклическое планирование. Всем процессам выделяется квант времени, в течение которого процесс выполняется. Переключение идет по кругу.
2. Приоритетное планирование. Обеспечить приоритетность процессов различным пользователям. Выполнения получают задания с наивысшим приоритетом.
3. Лотерейное планирование. Каждому процессу выдается “лотерейный билет”. При выигрыше процесс получает некоторое количество времени на исполнение. Приоритетная версия – процессам с большим приоритетом давать больше лотерейных билетов для увеличения шанса выигрыша.

Есть два вида таких систем – жёсткие (выход за рамки отклика недопустим) и гибкие (выход за временные рамки нежелателен, но допустим);

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

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