Такой алгоритм выбора процесса осуществляет невытесняющее планирование . Процесс, получивший в свое распоряжение процессор, занимает его до истечения текущего CPU burst . После этого для выполнения выбирается новый процесс из начала очереди.
Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков. Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса p 0 , p 1 и p 2 , для которых известны времена их очередных CPU burst . Эти времена приведены в таблице 3.1. в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst , что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь.
Если процессы расположены в очереди процессов, готовых к исполнению, в порядке p 0 , p 1 , p 2 , то картина их выполнения выглядит так, как показано на рисунке 3.2 . Первым для выполнения выбирается процесс p 0 , который получает процессор на все время своего CPU burst , т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс p 1 , он занимает процессор на 4 единицы времени. И, наконец, возможность работать получает процесс p 2 . Время ожидания для процесса p 0 составляет 0 единиц времени, для процесса p 1 – 13 единиц, для процесса p 2 – 13 + 4 = 17 единиц. Таким образом, среднее время ожидания в этом случае – (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса p 0 составляет 13 единиц времени, для процесса p 1 – 13 + 4 = 17 единиц, для процесса p 2 – 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.
Рис.
3.2.
Если те же самые процессы расположены в порядке p 2 , p 1 , p 0 , то картина их выполнения будет соответствовать рисунку 3.3 . Время ожидания для процесса p 0 равняется 5 единицам времени, для процесса p 1 – 1 единице, для процесса p 2 – 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае. Полное время выполнения для процесса p 0 получается равным 18 единицам времени, для процесса p 1 – 5 единицам, для процесса p 2 – 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 8 единиц времени, что почти в 2 раза меньше, чем при первой расстановке процессов.
Рис. 3.3.
Как мы видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным CPU burst , то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени – слишком большим получается среднее время отклика в интерактивных процессах .
Round Robin (RR)
Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin ( Round Robin – это вид детской карусели в США) или сокращенно RR . По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования . Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени , обычно 10 – 100 миллисекунд (см. рис. 3.4.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.
Рис. 3.4.
Реализуется такой алгоритм так же, как и предыдущий, с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени . При выполнении процесса возможны два варианта.
- Время непрерывного использования процессора, необходимое процессу (остаток текущего CPU burst ), меньше или равно продолжительности кванта времени . Тогда процесс по своей воле освобождает процессор до истечения кванта времени , на исполнение поступает новый процесс из начала очереди, и таймер начинает отсчет кванта заново.
- Продолжительность остатка текущего CPU burst процесса больше, чем квант времени . Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале.
Рассмотрим предыдущий пример с порядком процессов p 0 , p 1 , p 2 и величиной кванта времени равной 4 . Выполнение этих процессов иллюстрируется таблицей 3.2 . Обозначение "И" используется в ней для процесса, находящегося в состоянии исполнение, обозначение "Г" – для процессов в состоянии готовность, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1 .
| Время | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| p 0 | И | И | И | И | Г | Г | Г | Г | Г | И | И | И | И | И | И | И | И | И |
| p 1 | Г | Г | Г | Г | И | И | И | И | ||||||||||
| p 2 | Г | Г | Г | Г | Г | Г | Г | Г | И |
Первым для исполнения выбирается процесс p 0 . Продолжительность его CPU burst больше, чем величина кванта времени , и поэтому процесс исполняется до истечения кванта , т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид p 1 , p 2 , p 0 . Следующим начинает выполняться процесс p 1 . Время его исполнения совпадает с величиной выделенного кванта , поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов, p 2 и p 0 . Процессор выделяется процессу p 2 . Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу p 0 – единственному не закончившему к этому моменту свою работу. Время ожидания для процесса p 0 (количество символов "Г" в соответствующей строке) составляет 5 единиц времени, для процесса p 1 – 4 единицы времени, для процесса p 2 – 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса p 0 (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса p 1 – 8 единиц, для процесса p 2 – 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицы времени.
Легко увидеть, что среднее время ожидания и среднее полное время выполнения для обратного порядка процессов не отличаются от соответствующих времен для алгоритма FCFS и составляют 2 и 8 единиц времени соответственно.
Для начала как уже известно существуют ГОСТы, которые строго описывают сами блок-схемы и их построение, соединения (ГОСТ 19.701–90, ГОСТ 19.002–80, ГОСТ 19.003–80 ). Основные элементы схем алгоритма представлены в таблице 1.1.
Таблица 1.1 – Основные элементы схем алгоритмов
Продолжения таблицы 1.1.
Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).Продолжения таблицы 1.1.
Продолжения таблицы 1.1.
Продолжения таблицы 1.1.
Данные элементы удобно создавать и соединять в специализированных программах, которых существует множество, в том числе бесплатных. Как это сделать в Visio?
Если вкратце, то Visio позволяет рисовать различные схемы (бизнес процессы, алгоритмы, планы зданий и т.д.) при помощи готовых и создаваемых фигур. В нашем случае в качестве фигур выступают основные элементы схемы алгоритма.
В качестве примера нарисуем алгоритм для простой программы – нахождению вещественных корней квадратного уравнения для заданных значений коэффициентов a, b и с.
Напомним, что решение осуществляется через дискриминант
При корней два, и они вычисляются по формуле
При корень один (в некоторых контекстах говорят также о двух равных или совпадающих корнях), кратности 2:
При вещественных корней нет.
Особенностью данного алгоритма будет разветвляющийся процесс при проверке дискриминанта квадратного уравнения на условие D<0.
Алгоритм описания процессов
Рисунок 11 – Алгоритм описания процессов
Литература
1. Обеспечение качества обучения государственных и муниципальных служащих Российской Федерации. Выпуск 11. Инструктивно-методические материалы. Часть 1. Практические рекомендации по выбору типовой модели системы управления качеством образования. – М.: РАГС, 2006. – с.:38-44.
2. ГОСТ Р ИСО 9000-2001 Системы менеджмента качества. Основные положения и словарь.
3. Репин В.В., Елиферов В.Г. Процессный подход к управлению. Моделирование бизнес-процессов. – 3-е изд., испр. – М.: РИА «Стандарты и качество», 2005г. – с.: 305-314, ил. – (Серия «Практический менеджмент»).
4. http://slovar.plib.ru/ Толковый словарь Ожегова.
Приложение 1
Пример заполнения реестра типовых процессов и видов деятельности ОУ
| № п/п | Наименование вида деятельности или процесса | Иден. № | |
| Основные процессы | |||
| 1.1 | Маркетинговые исследования рынка научных, образовательных услуг и рынка труда | ||
| 1.2 | Проектирование и разработка образовательных программ | ||
| 1.3 | Довузовская подготовка и прием студентов | ||
| 1.4 | Реализация основных образовательных программ | ||
| 1.5 | Воспитательная и внеучебная работа с обучаемыми | ||
| 1.6 | Проектирование и реализация программ дополнительного образования | ||
| 1.7 | Подготовка кадров высшей квалификации (аспирантура, докторантура) | ||
| 1.8 | Научно-исследовательская и инновационная деятельность | ||
| Вспомогательные процессы | |||
| 2.1 | Бухгалтерско-финансовое обеспечение научно-образовательного процесса | ||
| 2.2 | Кадровое обеспечение | ||
| 2.3 | Закупки и взаимодействие с поставщиками материальных ресурсов | ||
| 2.4 | Управление образовательной средой | ||
| 2.5 | Издательская деятельность | ||
| 2.6 | Библиотечное и информационное обслуживание | ||
| 2.7 | Управление инфраструктурой и производственной средой | ||
| 2.8 | Обеспечение безопасности жизнедеятельности | ||
| 2.9 | Социальная поддержка студентов и сотрудников ОУ |
Приложение 2
Пример заполнения таблицы 2 «Спецификация процесса»
| 1. Наименование процесс | Научно-исследовательская деятельность (НИД) | |||
| 2. Цель процесса | Создание условий для реализации научно-исследовательской деятельности студентов и преподавателей | |||
| 3. Владелец процесса | Проректор по научно-исследовательской работе | |||
| 4. Входы процесса | Поставщик входа – процесс(ы), предоставляющий(ие) вход | |||
| 4.1 Аспиранты, докторанты. | Процесс управления докторантуры и аспирантуры | |||
| 4.2 Соискатели | Процесс управления докторантуры и аспирантуры; Внешний поставщик | |||
| 4.3 Студенты | Учебный процесс | |||
| 4.4 Данные маркетинговых исследований (требования потребителей) | Маркетинг и планирование набора | |||
| 5. Выходы процесса | Потребитель выхода – процесс(ы), использующий(ие) выход | |||
| 5.1 Статьи, изобретения | Учебный процесс; Отдел интеллектуальной собственности; Процесс управления докторантуры и аспирантуры; Библиотечное и информационное обслуживание; Внешний потребитель* и др. | |||
| 5.2 Дипломы, гранты | Учебный процесс, Процесс управления финансовым обеспечением; Внешний потребитель и др. | |||
| 5.3 Защитившие кандидатские, докторские диссертации | ||||
| 5.4 Научные школы | Учебный процесс; Научно-исследовательская деятельность; Внешний потребитель и др. | |||
| 6. Управляющая документация | 6.1 Программа развития подразделения | |||
| 6.2 Внутренние нормативные документы | ||||
| 6.3 Инструкция по организации научной и научно- технической деятельности, осуществляемой за счет собственных средств ТГУ с приложениями и др. | ||||
| 7. Механизмы процесса | 7.1 Персонал | |||
| 7.2 Финансы | ||||
| 7.3 Орг. техника | ||||
| 7.4 Библиотека и др. | ||||
| 8. Показатели процесса, ед. изм. | Норматив | Частота измерения | Метод расчета показателя | |
| 8.1 Процент ППС с учеными степенями и (или) учеными званиями, % | Не менее 60 | ежегодно | (Количество ППС с уч.степенями и званиями / Общ. количество ППС)*100 | |
| 8.2 Процент докторов наук и профессоров, % | Не менее 10 | ежегодно | (Кол-во докторов наук и профессоров / Общее количество ППС)*100 | |
| 8.3 Объем НИР на единицу ППС, тыс. руб. | За 5 лет – не менее 18 | ежегодно | … и др. | |
Всеобщий менеджмент качества (Total Quality Management – TQM) - интегрированный метод менеджмента, целиком ориентирующий деятельность организации на полную удовлетворенность потребителей (внешних и внутренних), сотрудников и общества в целом, охватывающий все процессы организации, вовлекающий в деятельность по непрерывному улучшению качества всех ее сотрудников и направленный на достижение долговременного успеха и стабильности функционирования организации.
Потребитель (согласно ГОСТ Р ИСО 9000-2005) – организация или лицо, получающие продукцию. Примеры: клиент, заказчик, конечный пользователь, розничный торговец, покупатель, студент и др.
Продукция (согласно ГОСТ Р ИСО 9000-2005) – результат процесса, т.е. результат совокупности взаимосвязанных или взаимодействующих видов деятельности, преобразующих входы в выходы.
Результативность
Эффективность (согласно ГОСТ Р ИСО 9000-2005) - степень реализации запланированной деятельности и достижения запланированных результатов.
Внутренний потребитель – потребитель, находящийся в организации и, в ходе своей деятельности, использующий результаты (выходы) предыдущего процесса.
Внешний потребитель – потребитель, находящийся за пределами организации и использующий результат (выход) процесса.
Алгоритм процессов, проходящих при сварке электродами с покрытием, представлен в виде схемы на рис. 1.27. Так, при сварке электродами с покрытием А создается газовая защита из СО и Н2 при распаде крахмала. Кроме того, в результате распада при нагревании гематита Fe2O3 выделяется кислород, связывающий водород в нерастворимое соединение ОН. Кислород также окисляет металл. Одновременно с раскислением идет процесс рафинирования марганцем, происходят ошлаковка продуктов раскисления и их вытеснение из шва.
Алгоритм процесса прослеживания за траекториями молекул достаточно прост.
Алгоритм процесса вытеснения при моделировании III метода состоит из следующих основных процедур.
Алгоритм процесса загрузки и обслуживания заявки на каждом элементе ТК следующий. В результате прерывания обслуживания или в результате поступления заявки согласно заданному алгоритму приоритетного обслуживания (первым пришел - первым обслужен) определяется заявка, подлежащая обслуживанию.
Алгоритм процесса смешивания состоит из следующих этапов: наполнить резервуар первой краской; наполнить резервуар второй краской; закончить подачу, если замкнут переключатель Резервуар полный; оставить насос включенным, если пусковой переключатель открыт; начать цикл нагревания и смешивания; включить двигатель смесителя и вентиль пара; выпустить готовую краску из резервуара; подсчитать циклы включения смесителя.
Алгоритм процесса согласования исходных данных ЭК (рис. 7 - 2) включает в себя модельное мысленное построение структуры ЭК и оценку возможностей данной структуры при достижении поставленной цели.
Алгоритм процесса оптимизации значений определяющих параметров и выбора оптимальных управлений в системе построен на основании направленного изменения ограничивающего множества Q. Действительно, изменяя Q, можно изменять множество возможных управлений, вводя в него новые, более эффективные управления или исключая управления, использование которых нецелесообразно из-за низкой эффективности.
Поясним алгоритм процесса вычислений.
Разработка алгоритма процессов, для которых требуется знание соответствующих уравнений, начальных и ограничительных условий, характеристик и постоянных материалов, представляет большой объем работы и охватывает широкое поле деятельности. Однако использование - математических машин возможно при условии, что существует замкнутая система уравнений, точно отражающих реальность. Если, например, ппед-положить, что процесс линейный, а в действительности он нелинейный, пли если не учитываются второстепенные явления, как-то: неравномерность температуры воздуха и звукопоглощающих - материалов, когда имеются потоки теплого воздуха, то только эксперименты непосредственно на исследуемом объекте, или хотя бы на физической модели, могут обеспечить получение физических данных, необходимых для познания процесса. Есть основание полагать, что в ближайшее время начнется использование математических машин для моделирования акустических процессов.
В соответствии с алгоритмом процесса, выбранным критерием оптимизации и технологическими ограничениями машина рассчитывает оптимальные значения управляющих воздействий, которые поступают в виде сигналов на исполнительные механизмы.
На рис. 6.3 представлен алгоритм процесса одномерной оптимизации методом золотого сечения. В результате выполнения алгоритма выдается оптимальное значение проектного параметра х, в качестве которого принимается середина последнего интервала неопределенности.
На рис. 61 приведен алгоритм процесса отработки долот в зоне сопоставимости. В качестве примера рассматривается наиболее употребляемое в настоящее время на практике трехшаро-шечное долото с симметричным расположением шарошек.
Планирование процессов включает в себя решение следующих задач:
определение момента времени для смены выполняемого процесса;
выбор процесса на выполнение из очереди готовых процессов;
переключение контекстов "старого" и "нового" процессов.
Первые две задачи решаются программными средствами, а последняя в значительной степени аппаратно. Существует множество различных алгоритмов планирования процессов, по разному решающих вышеперечисленные задачи, преследующих различные цели и обеспечивающих различное качество мультипрограммирования. Среди этого множества алгоритмов рассмотрим подробнее две группы наиболее часто встречающихся алгоритмов: алгоритмы, основанные на квантовании, и алгоритмы, основанные на приоритетах.
В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:
- процесс завершился и покинул систему,
- произошла ошибка,
- процесс перешел в состояние ОЖИДАНИЕ,
- исчерпан квант процессорного времени, отведенный данному процессу.
Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Граф состояний процесса, изображенный на рисунке 2.1, соответствует алгоритму планирования, основанному на квантовании. Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По разному может быть организована очередь готовых процессов: циклически, по правилу "первый пришел - первый обслужился" (FIFO) или по правилу "последний пришел - первый обслужился" (LIFO). Другая группа алгоритмов использует понятие "приоритет" процесса. Приоритет - это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности. На рисунке 2 показаны графы состояний процесса для алгоритмов с относительными (а) и абсолютными (б) приоритетами.
Рис.1. Граф состояний процесса в многозадачной среде
(а) с относительными приоритетами; (б)с абсолютными приоритетами
Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетами процессов.
