Вычислительные процессы

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

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

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

Распределение времени между задачами. Сравнительно рано быстродействие компьютеров при счете существенно превысило скорости обмена с внешней средой (диск, а тем более магнитная лента или устройство ввода/вывода), и у компьютеров появилось свойство «многозадачности» (multitasking): многозадачная операционная система ведет одновременно несколько задач, предоставляя им по очереди «кванты времени» и прерывая выполнение задачи 1 по истечении кванта, а также, если эта задача запросила медленное действие обмена. При определении политики управления задачами в подобной операционной системе внимание разработчиков обращалось на создание достаточно простых правил переключения с задачи на задачу. В частности, были созданы системы динамически изменяющихся приоритетов задач.

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

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

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

Захват ресурсов. Сам термин Concurrent processes — конкурирующие процессы, который у нас обычно переводится параллельные процессы, показывает, что у процессов может идти борьба за что-то. Действительно, они нуждаются в одних и тех же ресурсах, и количество этих ресурсов ограничено. Для того чтобы процесс мог владеть захваченным ресурсом монопольно, используется специальный программный механизм, называемый семафором. Процесс может занять ресурс только, если семафор ресурса открыт. При захвате ресурса семафор закрывается, при освобождении открывается.

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