Лекция 5. Понятия процесса и потока. Ние процессов и потоков. Типы планирования процессора. Тупики. Методы взаимодействия процессов
 Скачать 429.57 Kb.
|
|
разблокирование процесса. После возникновения в системе какого-либо события операционной системе нужно точно определить, какое именно событие произошло. Затем операционная система проверяет, находился ли некоторый процесс в состоянии ожидание для данного события, и если находился, переводит его в состояние готовность, выполняя необходимые действия, связанные с наступлением события (инициализация операции ввода-вывода для очередного ожидающего процесса и т. п.). Переключение контекста процесса До сих пор мы рассматривали операции над процессами изолированно, независимо друг от друга. В действительности же деятельность мультипрограммной операционной системы состоит из цепочек операций, выполняемых над различными процессами, и сопровождается переключением процессора с одного процесса на другой. Для корректного переключения процессора с одного процесса на другой необходимо сохранить контекст исполнявшегося процесса и восстановить контекст процесса, на который будет переключен процессор. Такая процедура сохранения/восстановления работоспособности процессов называется переключением контекста. Время, затраченное на переключение контекста, не используется вычислительной системой для совершения полезной работы и представляет собой накладные расходы, снижающие производительность системы. Оно меняется от машины к машине и обычно колеблется в диапазоне от 1 до 1000 микросекунд. Существенно сократить накладные расходы в современных операционных системах позволяет расширенная модель процессов, включающая в себя понятие threads of execution (нити исполнения или просто нити). Иерархия процессов В UNIX системах заложена жесткая иерархия процессов. Каждый новый процесс, созданный системным вызовом, является дочерним к предыдущему процессу. Дочернему процессу достаются от родительского процесса переменные, регистры и т.п. Как только родительские данные скопированы, последующие изменения в одном из процессов не влияют на другой, но процессы помнят о том, кто является родительским. В таком случае в UNIX существует и прародитель всех процессов - процесс init.  Рис. 5.1. Дерево процессов для систем UNIX В Windows не существует понятия иерархии процессов. Хотя можно задать специальный маркер родительскому процессу, позволяющий контролировать дочерний процесс. Состояние процессов При исполнении процесс может изменять свое состояние следующим образом: новый (new) - процесс создается операционной системой, но еще не начал выполняться; исполняемый (running) - исполняются команды процесса на процессоре или процессорах компьютерной системы под управлением операционной системы; ожидающий (waiting) - процесс ожидает наступления некоторого события, например, завершения ввода-вывода. В состоянии ожидания процесс не занимает процессор; готовый к выполнению (ready) - процесс ожидает получения ресурсов процессора для его исполнения. В состояние готовности к выполнению процесс попадает обычно либо при его создании, либо после завершения ввода-вывода (из состояния ожидания); завершенный (terminated) - исполнение процесса завершено.  Рис.5.2. Возможные переходы между состояниями. На серверах для ускорения ответа на запрос клиента, часто загружают несколько процессов в режим ожидания. Как только сервер получит запрос, процесс переходит из состояния ожидания в состояние выполнения. Этот переход выполняется намного быстрее, чем запуск нового процесса. Планирование процессов и потоков Одной из основных подсистем мультипрограммной операционной системы, непосредственно влияющей на функционирование вычислительной машины, является подсистема управления процессами и потоками, которая занимается: их созданием и уничтожением; поддержанием взаимодействия между ними; распределением процессорного времени между несколькими одновременно существующими в системе процессами и потоками; синхронизацией процессов (согласование скоростей потоков также очень важно для предотвращения эффекта «гонок» - когда несколько потоков пытаются изменить один и тот же файл, взаимных блокировок или других коллизий, которые возникают при совместном использовании ресурсов), обеспечением процессов необходимыми ресурсами; освобождением выделенных ресурсов (закрываются все файлы, с которыми работал процесс, освобождаются области оперативной памяти, отведенные под коды, данные и системные информационные структуры процесса, выполняется коррекция всевозможных очередей операционной системы и списков ресурсов, в которых имелись ссылки на завершаемый процесс). С точки зрения обеспечения ресурсами операционная система выполняет следующие функции и задачи: назначает процессу ресурсы в единоличное пользование или в совместное пользование с другими процессами; выделяет ресурсы процессу при его создании или динамически по запросам во время выполнения; обеспечивает ресурсами процесс на все время его жизни или только на определенный период; обеспечивает взаимодействие с другими подсистемами операционной системы, ответственными за управление ресурсами (подсистема управления памятью, подсистема ввода-вывода, файловая система). Диспетчеризация процессов. Стратегии диспетчеризации процессов Имеется пять основных критериев диспетчеризации процессора, которые так или иначе должны учитываться системой: использование процессора (CPU utilization) – поддержание его в режиме занятости максимально возможный период времени. Критерий оптимизации: максимизация данного показателя; пропускная способность системы (throughput) – (среднее) число процессов, завершающих свое выполнение за единицу времени. Критерий оптимизации: максимизация; время обработки процесса (turnaround time) – время, необходимое для исполнения какого-либо процесса. Критерий оптимизации: минимизация; время ожидания (waiting time) – время, которое процесс ждет в очереди процессов, готовых к выполнению. Критерий оптимизации: минимизация; время ответа (response time) – время, требуемое от момента первого запроса до первого ответа. Критерий оптимизации: минимизация. Существуют следующие стратегии диспетчеризации процессов: стратегия First Come First Served (обслуживание в порядке поступления) – наиболее простая стратегия диспетчеризации, при которой ресурсы процессора предоставляются процессам в порядке их поступления (ввода) в систему, независимо от потребляемых ими ресурсов, в частности, от заявленного процессом времени, требуемого для его выполнения; стратегия Shortest Job First (SJF, обслуживание самого короткого задания первым) – стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь наиболее короткому процессу из имеющихся в системе процессов. В данном случае с каждым процессом связывается длина его очередного периода активности. Эта длина используется для того, чтобы первым обслужить самый короткий процесс. Возможны две схемы применения данной стратегии: без прерывания процессов – пока процессу предоставляется процессор, он не может быть прерван, пока не истечет его квант времени; с прерыванием процессов – если приходит новый процесс, время активности которого меньше, чем оставшееся время активного процесса, - прервать активный процесс. Эта схема известна под названием Shortest Remaining Time First (SRTF); диспетчеризация по приоритетам (приоритетное планирование). При данной стратегии с каждым процессом связывается его приоритет (целое число). Процессор выделяется процессу с наивысшим приоритетом. Данная стратегия, как и предыдущая, имеет варианты с прерыванием и без прерывания. Более того, стратегию SJF можно рассматривать как диспетчеризацию по приоритетам, в которой приоритетом является очередное время активности. При диспетчеризации по приоритетам возникает проблема голодания (starvation) - ситуации, когда процессы с низким приоритетом могут никогда не исполниться и бесконечно ждать. Традиционным способом решение данной проблемы в операционных системах является учет возраста процесса (aging): c течением времени приоритет процесса повышается системой; стратегия Round Robin (RR, круговая система, «карусельная» стратегия) – это предоставление всем процессам по очереди одинаковых квантов времени. При данной стратегии каждый процесс получает небольшой квант процессорного времени, обычно – 10-100 миллисекунд. После того, как это время закончено, процесс прерывается и помещается в конец очереди готовых процессов; планирование с использование многоуровневой очереди (Multilevel queue scheduling) - разработано для ситуации, когда процессы можно легко разбить на несколько групп (например, интерактивные и фоновые - пакетные). В каждой из очередей находится процессы с одинаковыми свойствами, а каждая отдельная очередь может иметь свою стратегию планирования. Ни один процесс с более низким приоритетом не может быть запущен, пока не выполнятся процессы во всех очередях в более высокими приоритетами; планирование с использование многоуровневой очереди с обратными связями (Multilevel feedback queue scheduling). Стратегия предполагает, что процессы могут перемещаться между очередями. Она является универсальной и сочетает в себе свойства всех рассмотренных ранее стратегий. Планирование и диспетчеризация потоков На протяжении существования процесса выполнение его потоков может быть многократно прервано и продолжено. Переход от выполнения одного потока к другому осуществляется в результате планирования и диспетчеризации. Работа по определению того, в какой момент необходимо прервать выполнение текущего активного потока и какому потоку предоставить возможность выполняться, называется планированием. Планирование потоков осуществляется на основе информации, хранящейся в описателях процессов и потоков. При планировании могут приниматься во внимание приоритет потоков, время их ожидания в очереди, накопленное время выполнения, интенсивность обращений к вводу-выводу и другие факторы. Операционная система планирует выполнение потоков независимо от того, принадлежат ли они одному или разным процессам. Планирование потоков включает в себя решение двух задач: определение момента времени для смены текущего активного потока; выбор для выполнения потока из очереди готовых потоков. Существует множество различных алгоритмов планирования потоков. Алгоритмы планирования могут преследовать различные цели и обеспечивать разное качество мультипрограммирования. В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line), то есть решения принимаются во время работы системы на основе анализа текущей ситуации. Операционная система работает в условиях неопределенности — потоки и процессы появляются в случайные моменты времени и также непредсказуемо завершаются. Динамические планировщики могут гибко приспосабливаться к изменяющейся ситуации и не используют никаких предположений о мультипрограммной смеси. Другой тип планирования — статический — может быть использован в специализированных системах, в которых весь набор одновременно выполняемых задач определен заранее, например, в системах реального времени. Планировщик называется статическим (или предварительным планировщиком), если он принимает решения о планировании не во время работы системы, а заранее (off-line). Результатом работы статического планировщика является таблица, называемая расписанием, в которой указывается, какому потоку/процессу, когда и на какое время должен быть предоставлен процессор. Для построения расписания планировщику нужны как можно более полные предварительные знания о характеристиках набора задач, например о максимальном времени выполнения каждой задачи, ограничениях предшествования, ограничениях по взаимному исключению, предельным срокам и т. д. Диспетчеризация заключается в реализации найденного в результате планирования (динамического или статистического) решения, то есть в переключении процессора с одного потока на другой. Прежде чем прервать выполнение потока операционная система запоминает его контекст, чтобы впоследствии использовать эту информацию для последующего возобновления выполнения данного потока. Контекст содержит: значение счетчика команд содержимое регистров общего назначения режим работы процессора флаги маски прерываний ссылки на открытые файлы данные о незавершенных операциях ввода-вывода коды ошибок выполняемых данным потоком системных вызовов и т. д. Диспетчеризация сводится к следующему: сохранение контекста текущего потока, который требуется сменить; загрузка контекста нового потока, выбранного в результате планирования; запуск нового потока на выполнение. Поскольку операция переключения контекстов существенно влияет на производительность вычислительной системы, программные модули операционной системы выполняют диспетчеризацию потоков совместно с аппаратными средствами процессора. Состояния потока Операционная система выполняет планирование потоков, принимая во внимание их состояние. В мультипрограммной системе поток может находиться в одном из трех основных состояний: выполнение — активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором; ожидание — пассивное состояние потока, находясь в котором, поток заблокирован по своим внутренним причинам (ждет осуществления некоторого события, например завершения операции ввода-вывода, получения сообщения от другого потока или освобождения какого-либо необходимого ему ресурса); готовность — также пассивное состояние потока, но в этом случае поток заблокирован в связи с внешним по отношению к нему обстоятельством (имеет все требуемые для него ресурсы, готов выполняться, однако процессор занят выполнением другого потока). Состояния выполнения и ожидания могут быть отнесены и к задачам, выполняющимся в однопрограммном режиме, а вот состояние готовности характерно только для режима мультипрограммирования. В течение своей жизни каждый поток переходит из одного состояния в другое (в соответствии с алгоритмом планирования потоков, принятым в данной операционной системе). В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в каждом из состояний ожидания и готовности — несколько потоков. Эти потоки образуют очереди соответственно ожидающих и готовых потоков. Очереди потоков организуются путем объединения в списки описателей отдельных потоков. Таким образом, каждый описатель потока содержит, по крайней мере, один указатель на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать потоки, переводить потоки из одного состояния в другое. Вытесняющие и не вытесняющие алгоритмы планирования Все множество алгоритмов планирования можно разделить на два класса: вытесняющие алгоритмы; не вытесняющие алгоритмы. Не вытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам не отдаст управление операционной системе для того, чтобы она выбрала из очереди другой готовый к выполнению поток. Вытесняющие (preemptive) алгоритмы — это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается операционной системой, а не активной задачей. Основным различием между вытесняющими и не вытесняющими алгоритмами является степень централизации механизма по планированию потоков. Поэтому разработчики приложений для операционной среды с не вытесняющей многозадачностью вынуждены, возлагая на себя часть функций планировщика, создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Однако распределение функций планирования потоков между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент возвращения управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждого цикла выполнения использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит данные. Существенным преимуществом не вытесняющего планирования является более высокая скорость переключения с потока на поток. |