Категории планирования

 

Федеральное государственное образовательное учреждения высшего профессионального образования

Национальный исследовательский технологический университет

«МИСиС»

Институт ИТАСУ

Кафедра Автоматизации

Контрольная работа

по дисциплине «Операционные системы и среды»

На тему: Категории планирования

Выполнил:

Гиря А.М.

Проверил:

Ухаров А.С.

Москва 2013 г.

Содержание

Планирование

.Введение в планирование

.Понятие «процесс» и «поток»

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

.Категории планирования

.Категории алгоритмов планирования

.Задачи алгоритма планирования

.Планирование в пакетных системах

.Планирование в интерактивных системах

.Планирование в системах реального времени

Описание программы

Список используемой литературы

планирование алгоритм процесс пакетная система

Планирование

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

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

1.Введение в планирование

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

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

Во-вторых, с годами компьютеры стали работать настолько быстрее, что центральный процессор практически перестал быть дефицитным ресурсом. Поэтому на простых персональных компьютерах планирование не играет особой роли.

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

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

2. Понятия «процесс» и «поток»

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

Очевидно, что любая работа вычислительной системы заключается в выполнении некоторой программы. Поэтому и с процессом, и с потоком связывается определенный программный код, который для этих целей оформляется в виде исполняемого модуля. Чтобы этот программный код мог быть выполнен, его необходимо загрузить в оперативную память, возможно, выделить некоторое место на диске для хранения данных, предоставить доступ к устройствам ввода-вывода, например к последовательному порту для получения данных по подключенному к этому порту модему; и т. д. В ходе выполнения программе может также понадобиться доступ к информационным ресурсам, например файлам, портам TCP/UPD, семафорам. И, конечно же, невозможно выполнение программы без предоставления ей процессорного времени, то есть времени, в течение которого процессор выполняет коды данной программы. В операционных системах, где существуют и процессы, и потоки, процесс рассматривается операционной системой как заявка на потребление всех видов ресурсов, кроме одного - процессорного времени. Этот последний важнейший ресурс распределяется операционной системой между другими единицами работы - потоками, которые и получили свое название благодаря тому, что они представляют собой последовательности (потоки выполнения) команд. В простейшем случае процесс состоит из одного потока, и именно таким образом трактовалось понятие «процесс» до середины 80-х годов (например, в ранних версиях UNIX) и в таком же виде оно сохранилось в некоторых современных ОС. В таких системах понятие «поток» полностью поглощается понятием «процесс», то есть остается только одна единица работы и потребления ресурсов - процесс. Мультипрограммирование осуществляется в таких ОС на уровне процессов. Для того чтобы процессы не могли вмешаться в распределение ресурсов, а также не могли повредить коды и данные друг друга, важнейшей задачей ОС является изоляция одного процесса от другого. Для этого операционная система обеспечивает каждый процесс отдельным виртуальным адресным пространством, так что ни один процесс не может получить прямого доступа к командам и данным другого процесса.

3.Планирование процессов и потоков

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

4. Категории планирования

Если аппаратный таймер обеспечивает периодические прерывания с частотой 50 или 60 Гц или с какой-нибудь другой частотой, планировщик должен принимать решения при каждом прерывании по таймеру или при каждом k-том прерывании. По реакции на прерывания по таймеру алгоритмы планирования можно разделить на две категории. Неприоритетный алгоритм планирования выбирает запускаемый процесс, а затем просто дает ему возможность выполняться до тех пор, пока он не заблокируется, или до тех пор, пока он добровольно не освободит центральный процессор. В результате во время прерываний по таймеру решения приниматься не будут. После завершения обработки прерывания по таймеру работу возобновит ранее запущенный процессор, если только какой-нибудь процесс более высокого уровня не ожидал только что истекшей задержки во времени.

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

5. Категории алгоритмов планирования

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

)пакетную;

2)интерактивную;

)реального времени;

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

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

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

6. Задачи алгоритма планирования

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

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

все системы (равнодоступность, принуждение к определенной политике, баланс);

пакетные системы (производительность, оборотное время, использование центрального процессора);

интерактивные системы (время отклика, пропорциональность);

системы реального времени (соблюдение предельных сроков, предсказуемость).

7. Планирование в пакетных системах

1.Первым пришел - первым обслужен

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

.Сначала самое короткое задание

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

.Приоритет наименьшему времени выполнения

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

8. Планирование в интерактивных системах

1.Циклическое планирование

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

.Приоритетное планирование

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

9. Планирование в системах реального времени

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

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

Описание программы

ВАРИАНТ 3. МОДЕЛЬ ОБСЛУЖИВАНИЯ ПРОЦЕССОВ С АБСОЛЮТНЫМИ ПРИОРИТТЕТАМИ ОБСЛУЖИВАНИЯ И ЗАДАННЫМ КВАНТОМ ВРЕМЕНИ.

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

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

Исходные данные:

-величина кванта времени (Tкв = 1);

поток заявок на выполнение процессов (имя заявки (name), время поступления (t0), приоритет (Pr), время исполнения(T)).

Программа:.cs

using System;System.Collections.Generic;System.Linq;System.Windows.Forms;WindowsFormsApplication1

{

static class Program

{

/// <summary>

/// Главная точка входа для приложения.

/// </summary>

[STAThread]void Main()

{.EnableVisualStyles();.SetCompatibleTextRenderingDefault(false);.Run(new Form1());

}

}

}

Form1.cs

using System;System.Collections.Generic;System.IO;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;WindowsFormsApplication1

{partial class Form1 : Form

{Form1()

{();

}void Form1_Load(object sender, EventArgs e)

{

}void button1_Click(object sender, EventArgs e)

{.Clear();

//Считывание из файлаa = new StreamReader(@"d:\Kursovaya.txt");line;[,] tabl = new string[5, 4];(int i = 0; i < 5; i++)

{= a.ReadLine();[] koord = line.Split(',');(int j = 0; j < 4; j++)

{[i, j] = koord[j];

}

}

//Вывод в richTextBox1(int i = 0; i < 5; i++)

{.AppendText(" ");(int j = 0; j < 4; j++)

{.AppendText(tabl[i, j] + " ");

}.AppendText("\n\n");

}

//.Text = tabl[0, 0];.Text = tabl[1, 0];.Text = tabl[2, 0];.Text = tabl[3, 0];.Text = tabl[4, 0];.Visible = true;.Width = 660;.Height = 336;

}void Form1_Paint_1(object sender, PaintEventArgs e)

{g = e.Graphics;xc = 320; yc = 279;

//определение начала новой системы координат.TranslateTransform(xc, yc);

//вычерчивание осей координат

g.DrawLine(new Pen(Color.Yellow, 5.0f),

this.Width, 0, this.Width, 0);.DrawLine(new Pen(Color.Yellow, 5.0f),

, -this.Height, 0, this.Height);

//Шкалирование(int i = 0; i < 315; i+=15)

{(i % 25 != 0)

{.DrawLine(new Pen(Color.Yellow, 1.5f), i, 5, i, -279);

}

{.DrawLine(new Pen(Color.Yellow, 3f), i, 10, i, -279);

}

}

//Описание значений цветов для процессов.DrawLine(new Pen(Color.Green, 3f), -157, -30, -127, -30);

g.DrawLine(new Pen(Color.Red, 3f), -157, -43, -127, -43);.DrawLine(new Pen(Color.Black, 3f), -157, -57, -127, -57);

//График(label1.Visible == true)

{(int i = 0; i > -200; i -= 40)

{(i == 0)

{.DrawLine(new Pen(Color.Red, 3f), 15, -45 + i, 150, -45 + i);.DrawLine(new Pen(Color.Black, 3f), 150, -45 + i, 180, -45 + i);.DrawLine(new Pen(Color.Black, 3f), -5, -45 + i, 15, -45 + i);

}(i == -40)

{.DrawLine(new Pen(Color.Green, 3f), -5, -45 + i, 15, -45 + i);.DrawLine(new Pen(Color.Black, 3f), 15, -45 + i, 45, -45 + i);

}(i == -80)

{.DrawLine(new Pen(Color.Green, 3f), -5, -45 + i, 30, -45 + i);.DrawLine(new Pen(Color.Red, 3f), 30, -45 + i, 45, -45 + i);.DrawLine(new Pen(Color.Black, 3f), 45, -45 + i, 60, -45 + i);.DrawLine(new Pen(Color.Red, 3f), 60, -45 + i, 105, -45 + i);.DrawLine(new Pen(Color.Black, 3f), 105, -45 + i, 150, -45 + i);

}(i == -120)

{.DrawLine(new Pen(Color.Green, 3f), -5, -45 + i, 45, -45 + i);.DrawLine(new Pen(Color.Red, 3f), 45, -45 + i, 60, -45 + i);.DrawLine(new Pen(Color.Black, 3f), 60, -45 + i, 75, -45 + i);

}(i == -160)

{.DrawLine(new Pen(Color.Green, 3f), -5, -45 + i, 60, -45 + i);.DrawLine(new Pen(Color.Red, 3f), 60, -45 + i, 75, -45 + i);.DrawLine(new Pen(Color.Black, 3f), 75, -45 + i, 105, -45 + i);

}

}

}

}void richTextBox1_TextChanged(object sender, EventArgs e)

{

}void label9_Click(object sender, EventArgs e)

{

}

}

}

Принтскрин ввода данных

Принтскрин выполненной программы

Список используемой литературы

1. Назаров С.В., Широков А.И. Многопользовательские операционные системы. - М.: Изд. дом МИСиС, 2010. 194 стр.

. Таненбаум Э. Современные операционные системы. Изд-е 4. СПб.: Питер, 2010.

. Гордеев А.В. Операционные системы: Учебник для вузов. 2-е изд. - СПб.: Питер, 2007. - 416 с.: ил.

Федеральное государственное образовательное учреждения высшего профессионального образования Национальный исследовательский технологический университет &#

Больше работ по теме: