Что такое вычислительный процесс в информатике

Что такое вычислительный процесс в информатике

Содержание раздела Учебник по инфоматике

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

Следование (последовательность двух или более операций);

Ветвление (выбор направления);

Повторение (цикл «до» и цикл «пока»);

Заметим при этом, что две последние структуры можно реализовать, используя структуру типа ветвление. Таким образом, любой вычислительный процесс может быть представлен как комбинация трёх элементарных алгоритмических структур. Соответственно, вычислительные процессы, выполняемые на ЭВМ по заданной программе, можно разделить на три основных вида:

1.линейные;
2.ветвящиеся;
3.циклические

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

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

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

В организации цикла можно выделить следующие этапы:

подготовка (инициализация) цикла (И);

выполнение вычислений цикла (тело цикла) (Т);

модификация параметров (М);

проверка условия окончания цикла (У).

Порядок выполнения этих этапов, например, Т и М, может изменяться. В зависимости от расположения проверки условия окончания цикла различают циклы с нижним и верхним окончаниями. Для цикла с нижним окончанием тело цикла выполняется как минимум один раз, так как сначала производятся вычисления, а затем проверяется условие выхода из цикла.

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

Цикл называется детерминированным, если число повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.

Источник

Понятия вычислительного процесса и ресурса.

Вычислительный процесс − это процесс выполнения программы совместно с ее данными на процессоре (редактирование текста, трансляция, выполнение какой-либо программы).

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

На начальном этапе программирования ВС ресурсами считались: процессорное время, память, команды ввода-вывода, периферийные устройства. С расширением понятия объекта расширилось и понятие ресурса.

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

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

Для более полного понимания понятия процесса и ресурса невозможно обойти такое понятие, как мультипрограммирование. Цель мультипрограммирования – повысить быстродействие ВС в целом. В первых ВС, созданных на принципах Дж. Неймана, все подсистемы и устройства ЭВМ управлялись только центральным процессором (ЦП). Выполнение любой программы прерывалось, например, операциями ввода-вывода. Ввод в состав ВС контроллеров позволил распараллелить ввод-вывод и вычисления. Но ЦП всё равно простаивал в ожидании ввода-вывода очередной порции данных. Поэтому был предложен мультипрограммный режим, суть которого состоит в выполнении различных действий в одно и то же время. Т.е. для одной задачи делаются вычисления, для другой – ввод, для третьей – вывод и т.д. С ростом загрузки ресурсов растет и время выполнения каждой задачи, или другими словами, мультипрограммирование повышает пропускную способность системы, но замедляет работу по каждой задаче за счет затрат времени на ожидание освобождения ресурса.

Ресурс задаче может быть выделен если:

1) ресурс свободен и на него нет запроса от задачи с более высоким приоритетом.

2) текущий и предыдущие запросы позволяют использовать ресурс совместно, то ресурс делится.

3) ресурс используется задачей более низкого приоритета, то ресурс временно отбирается.

Если условие выполнено, то задача выполняется с выделенным ресурсом, а если нет, то задача ставится в очередь к ресурсу и переводится в режим ожидания.

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

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

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

Ещё один вид ресурсов − это программные модули. Выделяют, как важнейший ресурс, системные модули. Среди них − однократно используемые (неделимый ресурс) – модули загрузки ОС и многократно используемые (разделяемый ресурс) − утилиты, подпрограммы. Многократно используемые делятся на:

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

• Непривилегированные модули, они работают в обычном режиме (с включенной системой прерываний). Они не являются разделяемыми ресурсами.

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

• Повторно-входимые (re-entrance), они подобны предыдущим, но их выполнение нельзя прервать.

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

Источник

Процесс (информатика)

Проце́сс — выполнение пассивных инструкций компьютерной программы на процессоре ЭВМ. Стандарт ISO 9000:2000 Definitions определяет процесс как совокупность взаимосвязанных и взаимодействующих действий, преобразующих входящие данные в исходящие.

Компьютерная программа сама по себе это только пассивная совокупность инструкций, в то время как процесс — это непосредственное выполнение этих инструкций.

Часто процессом называют выполняющуюся программу и все её элементы: адресное пространство, глобальные переменные, регистры, стек, открытые файлы и т. д.

Создание процесса

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

Завершение процесса

Минимум 2 этапа завершения:

Причины завершения процесса:

Литература

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

Полезное

Смотреть что такое «Процесс (информатика)» в других словарях:

Процесс — По теме Процесс должна быть отдельная статья, а не страница разрешения неоднозначностей. После создания основной статьи страницу разрешения неоднозначностей, если в ней будет необходимость, переименуйте в Процесс (значения). Содержание 1… … Википедия

Процесс — (Process) Определение процесса, виды и типы процессов Информация об определении процесса, виды и типы процессов Содержание Содержание Определение Исторический Бизнес процесс Тепловой процесс Адиабатический процесс Изохорный процесс Изобарный… … Энциклопедия инвестора

Информатика — (ср. нем. Informatik, англ. Information technology, фр. Informatique, англ. computer science компьютерная наука в США, англ. computing science вычислительная наука в Великобритании) наука о способах… … Википедия

Процесс разработки программного обеспечения — Разработка программного обеспечения Процесс разработки ПО Шаги процесса Анализ • Проектирование • Программирование • … Википедия

Естественная информатика — это научное направление, изучающее процессы обработки информации, протекающие в природе, мозге и человеческом обществе. Она опирается на такие классические научные направления, как теории эволюции, морфогенеза и биологии развития, системные… … Википедия

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

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

Дерусификация (информатика) — У этого термина существуют и другие значения, см. Дерусификация. Дерусификация, применительно к программному обеспечению процесс восстановления оригинального языка некачественно переведённой на русский язык (русифицированной) программы. В… … Википедия

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

Источник

Основные виды вычислительных процессов

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

Аспекты операционных систем (история • список)
Ядро

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ИНСТИТУТ СОВРЕМЕННЫХ ТЕХНОЛОГИЙ И ЭКОНОМИКИ

Факультет современных технологий

по дисциплине «Информатика»

Выполнил (а): Студент факультета ЗО и ОЗ

Договорная форма обучения

Проверила: Ст. преподаватель Василенко П.А.

1. Основные виды вычислительных процессов

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.

Основными свойствами алгоритма являются:

1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;

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

3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;

4. дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

Алгоритм должен быть формализован по некоторым правилам посредством конкретных изобразительных средств. К ним относятся следующие способы записи алгоритмов: словесный, формульно-словесный, графический, язык операторных схем, алгоритмический язык.

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

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

При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:

o последовательность двух или более операций;

o выбор направления;

Любой вычислительный процесс может быть представлен как комбинация этих элементарных алгоритмических структур. Соответственно, вычислительные процессы, выполняемые на ЭВМ по заданной программе, можно разделить на три основных вида:

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

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

Рис.1. Линейные вычислительные процессы

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

Рис. 2. Ветвящийся вычислительный процесс

Рис. 3. Циклические процессы

Цикл называется детерминированным, если число повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.

Задание 1. Задачи по теме «Содержательный подход к измерению информации»

1. В библиотеке 16 стеллажей. На каждом стеллаже по 8 полок. Библиотекарь сказала Оле, что интересующая ее книга, находится на 3 стеллаже, на 2-ой сверху полке. Какое количество информации получила Оля?

Решение. По формуле Хартли

Н=1оg 2 N = 1оg 2 (16*8)=1оg 2 128= 1оg 2 7 = 7 бит

2. В корзине 8 шаров. Все шары разного цвета. Сколько информации несет сообщение о том, что из корзины достали красный шар?

Н=1оg 2 8 = 1оg 2 =1оg 2 23 = 3 битa

Задание 2. Задачи по теме «Позиционные системы счисления. Арифметические операции»

1. Перевести данное число из десятичной системы счисления вдвоичную, восьмеричную и шестнадцатеричную системы счисления.

2. Перевести данное число в десятичную систему счисления.

4. Выполнить вычитание.

5. Выполнить умножение.

Примечание. В заданиях 3-5 проверять правильность вычислений переводом исходных данных и результатов в десятичную систему счисления.

Источник

Понятия вычислительного процесса и ресурса

Понятие «вычислительный процесс» (или просто – процесс) является одним из основных при рассмотрении операционных систем. Под процессом обычно понимается последовательность операций при выполнении программы или ее части в совокупности с используемыми данными. В общем случае процесс и программа представляют собой разные понятия. Програм­ма– это план действий, а процесс – это само действие, поэтому понятие процесса включает программный код, данные, содержимое стека, содержимое адресного и других регистров процессора. Таким образом, для одной программы могут быть созданы не­сколько процессов в том случае, если с помощью одной программы в центральном процессоре (central processor unit – CPU) вычислительной машины выполняется несколько несовпадающих последовательностей команд.

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

По генеалогическому признаку различают порождающие и порож­денныепроцессы.

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

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

По месту развития процессы делятся на внутренние(реализуются на центральном процессоре) и внешние(реализуются на внешних процессорах).

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

По связности различают процессы:

а) взаимосвязанные – имеющие какую-то связь (простран­ственно-временную, управляющую, информационную);

б) изолированные – слабо связанные;

в) информационно-независимые – использующие совмест­ные ресурсы, но имеющие собственные информационные базы;

г) взаимодействующие – имеющие информационные связи и раз­деляющие общие структуры данных;

д) взаимосвязанные по ресурсам;

е) конкурирующие.

Порядок взаимосвязи процессов определяетсяправилами синхро­низации. Процессы могут находиться в отношении:

а) предшествования – когда один процесс всегда находится в активном состо­янии раньше, чем другой;

б) приоритетности – когда процесс может быть переведен в ак­тивное состояние только в том случае, если в состоянии готовности нет процессов с более высоким приоритетом, или если свобо­ден процессор, или если на процессоре реализуется процесс с меньшим приоритетом;

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

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

Определение концепции процесса преследует цель выработать механизмы распре­деления и управления так называемыми «ресурсами», которые также относятся к числу важнейших понятий ОС.

Ресурс – это любой потребляемый (расходуемый) объект. По запа­сам ресурсы подразделяются на исчерпаемые и неисчерпаемые. По­требители ресурсов – процессы. Ресурс – это средство вычисли-тельной машины или вычислительной системы, которое может быть выделено процессу на определенный интервал времени.

Ресурсы классифицируются по следующим свойствам:

а) по признаку реальности – на физические и виртуальные(последние только в отдельных свойствах схожи с физическими ресурсами);

б) по возможности расширения свойств – на эластичные и жесткие (не допускающие расширяемости);

в) по степени активности – на пассивные и активные(способные выполнять действия по отношению к другим ресурсам);

г) по времени существования – на постоянные (доступные на протяжении всего времени существования процесса, а также до и после его работы) и временные;

д) по степени важности – на основныеивторостепенные(допускающие альтернативное развитие процесса);

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

ж) по структуре – на со­ставныеипростые (которые не содержат составных элементов и могут находиться только в одном из двух состояний: «доступен» или «занят»);

з) по характеру использования– на потребляе­мые и воспроизводимые(допускающие многократное использо­вание и освобожде-ние), а также – на ис­пользуемые последовательнои ис­пользуемые параллельно(использующиеся несколькими процессами);

и) по форме реализации – на жесткие(не допускающие копи­рования) и мягкие(допускающие тиражирование и в свою очередь подразделяющиеся на программные и информационные ресурсы).

Примерами ресурсов являются некоторые аппартные устройства ВМ (процессоры, запоминающие устройства, устройства ввода-вывода) или некоторые наборы информации (в частности, совокупности записей определенной структуры – так называемые «файлы»).

Планирование процессов

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

За время своего существования процесс многократно изменяет свое состояние. Обычно различают следующие состояния процесса:

• новый(процесс только что создан);

• готовый(процесс ожидает освобождения CPU);

• выполняемый(команды программы выполняются в CPU);

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

• завершенный (процесс завершил свою работу).

Переход из одного состояния в другое не может выполняться произвольным образом. Каждый процесс представлен в операционной системе набором данных, называемых «таблица управления процессом» или сокращенно – ТУП (process control block – РСВ). В ТУП процесс описывается набором значе­ний и параметров, характе-ризующих его текущее состояние и ис­пользуемых операционной системой для управления прохождением процесса через ВМ.

Распределение процессов между имеющимися ресурсами носит название «планирование процессов».

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

Одним из методов планирования процессов, ориентированных на эффективную загрузку ресурсов, является метод очередей ресурсов. Новые процессы находятся во входной очереди, часто называемой очередью работ – заданий. Входная очередь располагается во внешней памяти, во входной очереди процессы ожидают освобождения ресурса – адресного про­странства основной памяти. Готовые к выполнению процессы располагаются в основной па­мяти и связаны очередью готовых процессов. Процессы в этой очере­ди ожидают освобождения ресурса «процессорное время». Выделение процессу процессорного времени производится многократно с целью достижения внешнего эффекта как бы «одновременного» выполнения нескольких программ. Такой механизм называется диспетчеризацией.

Процесс в состоянии ожидания, например, завершения операции ввода-вы­вода находится в одной из очередей к оборудованию ввода-вывода. Таким образом при прохождении через ВМ процесс мигрирует между различными очередями под управлением программы, которая назы­вается «планировщик» (scheduler).

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

Планирование процессов включает в себя решение следующих задач:

1) определение момента времени для смены выполняемого процесса;

2) выбор процесса на выполнение из очереди готовых процессов;

3) переключение контекстов «старого» и «нового» процессов.

Первые две задачи решаются программными средствами, а последняя – в значительной степени аппаратно.

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

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит в следующих случаях:

– процесс завершился и покинул систему;

– процесс перешел в состояние «ожидание»;

– исчерпан квант процессорного времени, отведенный данному процессу.

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

Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. Очередь готовых процессов может быть организована циклически по правилу FCFS (First Come First Served – «первым пришел – первым обслужен»), часто называемого правилом FIFO (First In First Out – «первым вошел – первым вышел»), или по правилу стека LCFS (Last Come First Served – «последним пришел – первым обслужен»), имеющего также наименование правила LIFO (Last In First Out – «последним вошел – первым вышел»).

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

Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты.

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

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

Существует два основных типа процедур планирования процессов – вытесняющие (preemptive) и невытесняющие (non-preemptive).

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

Вытесняющая многозадачность (preemptive multitasking) – это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком операционной системы, а не самой активной задачей.

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

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

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

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

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

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

Одними из основных движущих сил, изменяющих состояния процессов, являются определенные системные события, называемые «прерываниями».

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

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

Механизм обработки прерываний независимо от архитектуры ВМ включает следующие основные этапы-шаги:

1. Установление факта прерывания (прием сигнала на преры-вание) и иденти­фикация прерывания (в операционных системах иногда осуществляется по­вторно на шаге 4).

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

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

4. Сохранение информации о прерванной программе, которую не удалось спа­сти на шаге 2 с помощью действий аппаратуры. В некоторых ВМ предусматривается запоминание довольно большого объема информации о состоянии прерванного процесса.

5. Обработка прерывания. Эта работа может быть выполнена той же подпро­граммой, которой было передано управление на шаге 3, но в ОС чаще всего она реализуется путем последующего вызова соответствующей подпрограммы.

6. Восстановление информации, относящейся к прерванному процессу (этап, обратный шагу 4).

7. Возврат в прерванную программу.

Шаги 1–3 реализуются аппаратно, а шаги 4–7 – программно.

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

Итак, главные функции механизма прерываний:

– распознавание или классификация прерываний;

– передача управления соответственно обработчику прерываний;

– корректное возвращение к прерванной программе.

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

Прерывания, возникающие при работе ВМ, можно разде­лить на два основных класса: внешние (их иногда называют асинхронными) и внутренние (синхронные).

Внешние прерывания вызываются асинхронными событиями, которые происхо­дят вне прерываемого процесса, например:

– прерывания от таймера;

– прерывания от внешних устройств (прерывания по вводу-вы-воду);

– прерывания по нарушению питания;

– прерывания от другого процессора или другой ВМ.

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

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

– при наличии в поле кода операции незадействованной двоич-ной комбинации;

– при делении на нуль;

– при переполнении или исчезновении порядка;

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

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

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

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

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

Программное управление специальными регистрами маски (так называемое маскирование сиг­налов прерывания) позволяет реализо-вать различные дисциплины обслужива­ния, такие как:

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

2) дисциплина обслужива­ния с абсолютными приоритетами, то есть всегда обслуживается прерывание с наивысшим приоритетом. Для реализации этого режима необходимо на вре­мя обработки прерывания замаскировать все запросы с более низким приори­тетом. При этом возможно многоуровневое прерывание, то есть прерывание программ обработки прерываний. Число уровней прерывания в этом режиме изменяется и зависит от приоритета запроса;

3) дисциплина обслужива­ния по принципу стека (дисциплина LCFS или, по-другому, LIFO), то есть когда запросы с более низким приоритетом могут прерывать обработку прерывания с более вы­соким приоритетом. Для этого необходимо не накладывать маски ни на один сигнал прерывания и не выключать систему прерываний.

Следует особо отметить, что для правильной реализации последних двух дисци­плин нужно обеспечить полное маскирование системы прерываний при выпол­нении шагов 1–4 и 6–7. Это необходимо для того, чтобы не потерять запрос и правильно его обслужить. Многоуровневое прерывание должно происходить на этапе собственно обработки прерывания, а не на этапе перехода с одного процес­са на другой.

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

Как уже было сказано, при появлении запроса на прерывание система прерываний идентифицирует сигнал и, если прерывания разрешены, управление передается на соответствующую подпрограмму обработки прерывания. В подпро­грамме обработки прерывания имеются две служебные секции. Это первая секция, в которой осуществляется сохранение контекста прерванной задачи, не сохраненного на шаге 2, и последняя, заключительная секция, в которой, наоборот, осуществляется восстановление контекста. Для того, чтобы система прерываний не среагировала повторно на сигнал запроса на прерывание, она обычно автоматически «закрывает» (отключает) прерывания, поэтому необ­ходимо потом в подпрограмме обработки прерываний вновь включать систему прерываний. Установка рассмотренных режимов обработки прерываний (с отно­сительными и абсолютными приоритетами, по дисциплине LCFS) осуществляется в конце первой секции подпрограмм обработки прерываний. Таким образом, на время вы­полнения центральной секции (в случае работы в режимах с абсолютными при­оритетами) прерывания разрешены. На время работы заключительной секции подпрограммы обработки прерывания система прерываний должна быть отключена и после восстановления контекста вновь включена. Поскольку эти действия необходимо выполнять практически в каждой подпрограмме обра­ботки прерываний, во многих операционных системах первые секции подпро­грамм обработки прерываний выделяются в специальный системный программ­ный модуль, называемый супервизором прерываний.

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

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

Источник