Необходимость свопинга

Три основных состояния процессов, описанные в предыдущем разделе (готовый, выполняющийся и блокированный), позволяют смоделировать поведение процессов и получить представление о реализации операционной системы. Многие операцион­ные системы разработаны на основе только этих трех состояний.

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

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

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

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

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

Если в модель поведения процессов ввести описанный свопинг, то нам придется ввести и новое состояние — состояние приостановленного процесса (рис. 3.6,а). Когда все процессы в основной памяти находятся в блокирован­ном состоянии, операционная система может приостановить один из процессов, переведя его в приостановленное состояние и сбросив на диск. Освобо­дившееся в основной памяти пространство можно будет использовать для за­грузки другого процесса.

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

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

Это следует учесть при разработке операционной системы. Мы имеем дело с двумя независимыми ситуациями: ожидает ли процесс какого-либо события (т.е. блокирован он или нет), и выгружен ли процесс из основной памяти (т.е. приос­тановлен он или нет). Чтобы учесть 2x2 возможных комбинации, нужны четыре перечисленных ниже состояния.

• Готовый. Процесс, который находится в основной памяти и готов к выполнению.

• Блокированный. Процесс, находящийся в основной памяти и ожидающий какого-то события.

• Блокированный/Приостановленный. Процесс, находящийся во вторичной памяти (на диске) и ожидающий какого-то события.

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

Перед тем как составлять диаграмму переходов состояний, в которой учитываются два новых приостановленных состояния, следует упомянуть еще одно обстоятельство. До сих пор мы не учитывали существование виртуальной памя­ти; считалось, что процесс находится либо полностью в основной памяти, либо полностью вне ее. При наличии виртуальной памяти появляется возможность выполнять процесс, который загружен в основную память лишь частично. Если происходит обращение к отсутствующему в основной памяти адресу процесса, эта часть процесса может быть загружена. Казалось бы, использование виртуальной памяти избавляет от необходимости явного свопинга, потому что любой нужный адрес любого процесса можно перенести в основную память или из нее с помощью аппаратного обеспечения процессора, управляющего памятью. Однако, как мы увидим в главе 8, "Виртуальная память", при наличии достаточно боль­шого количества активных процессов, которые полностью или частично нахо­дятся в основной памяти, производительность виртуальной памяти может ока­заться недостаточной. Поэтому даже при наличии виртуальной памяти операци­онной системе время от времени требуется явно и полностью выгружать процессы из основной памяти ради повышения общей производительности.

А теперь рассмотрим модель переходов состояний, представленную на рис. 3.6,6 (пунктирными линиями показаны переходы, которые возможны, но не являются обязательными). Среди новых переходов наиболее важными являются следующие:

• Блокированный —> Блокированный/Приостановленный. Если к выполнению не готов ни один процесс, то по крайней мере один блокированный процесс выгружается из памяти, чтобы освободить место для другого процесса, который не является блокированным. Этот переход можно выполнять и при наличии гото­вых к выполнению процессов, если операционная система определит, что для выполняющегося в настоящее время процесса или процесса, управление к ко­торому перейдет в ближайшее время, нужно увеличить объем основной памяти для обеспечения адекватной производительности.

• Блокированный/Приостановленный —> Готовый/Приостановленный. Процесс в состоянии блокированного приостановленного переходит в состояние готового к выполнению приостановленного процесса, если происходит событие, которого ожидал этот процесс. Заметим, что для такого перехода операционная система должна иметь доступ к информации о состоянии приостановленных процессов.

• Готовый/Приостановленный —> Готовый. Когда в основной памяти нет готовых к выполнению процессов, операционной системе для продолжения вычислений требуется загрузить процесс в память. Может случиться и так, что у готового к выполнению приостановленного процесса окажется более высокий приоритет, чем у любого другого из готовых к выполнению процессов. В такой ситуации разработчик операционной системы может решить, что важнее обеспечить приоритет процесса, чем минимизировать свопинг.

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

Кроме того, заслуживают рассмотрения и другие переходы.

• Новый —> Готовый/Приостановленный и Новый —> Готовый. После создания нового процесса этот процесс может быть добавлен либо в очередь готовых к выполнению, либо в очередь готовых к выполнению приостановленных процессов. В любом из этих случаев операционная система должна создать таблицы для управления процессом и выделить ему адресное пространство. Лучше выполнить эти действия на ранних этапах, чтобы иметь больший запас неблокированных процессов. Однако если придерживаться этой стратегии, то в основной памяти может не хватить места для нового процесса. По этой причине предусмотрен переход нового процесса в состояние приостановленного готового к выполнению. С другой стороны, создание процесса в "последний момент" приводит к уменьшению непроизводительных затрат и позволяет операционной системе выполнять свои обязанности по созданию процессов даже тогда, когда она переполнена блокированными процессами.

• Блокированный/Приостановленный —> Блокированный. На первый взгляд может показаться, что учитывать такой переход бессмысленно. Зачем, в конце концов, загружать в память процесс, который не готов к выполнению? Однако рассмотрим такой сценарий: завершился некоторый процесс, освободив при этом определенную часть основной памяти. В очереди заблокированных приостановленных процессов находится процесс, приоритет ко­торого выше, чем у любого процесса из очереди готовых к выполнению, но приостановленных процессов. Кроме того, операционная система располагает аргументами в пользу того, что довольно скоро произойдет событие, которое снимет блокировку с этого высокоприоритетного процесса. При таких обстоятельствах резонно отдать предпочтение блокированному процессу перед готовыми к выполнению, загрузив в основную память именно его.

• Выполняющийся —> Готовый/Приостановленный. Обычно выполняющийся процесс, у которого вышло отведенное ему время, переходит в состояние готового к выполнению. Однако при наличии процесса с более высоким при­оритетом, который находился в очереди блокированных приостановленных процессов и только что был разблокирован, операционная система может отдать предпочтение именно ему. Чтобы освободить часть основной памяти, она может перевести выполняющийся процесс непосредственно в состояние готового к выполнению приостановленного процесса.

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