МОДЕЛИРОВАНИЕ РЕЖИМА РАБОТЫ С РАЗДЕЛЕНИЕМ ВРЕМЕНИ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ
Федеральное государственное образовательное учреждение
высшего образования
«Сарапульский политехнический институт»(филиал)
"Ижевский государственный технический университет имени М.Т.Калашникова"
УТВЕРЖДАЮ
Директор СПИ (филиала) ФГБОУ ВО
«ИжГТУ имени М.Т.Калашникова»
_____________ Т.А.Беркутова
"____"_____________ 20 г.
Методические рекомендации к лабораторным работам
Наименование дисциплины: Операционные системы
Направление подготовки:230100 Информатика и вычислительная техника
Профиль:Вычислительные машины, комплексы, системы и сети
Кафедра: Конструирование и производство радиоаппаратуры
СОЗДАНИЕ ПРОЦЕССОВ
Важнейшей частью операционной системы, непосредственно влияющей на функционирование вычислительной машины, является подсистема управления процессами. Процесс (или по-другому, задача) – абстракция, описывающая выполняющуюся программу [12, 14]. Для операционной системы процесс представляет собой единицу работы, заявку на потребление системных ресурсов. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресур-сами, поддерживает взаимодействие между процессами.
|
|
|
Состояние процессов
В многозадачной (многопроцессной) системе процесс может находиться в одном из трех основных состояний:
ВЫПОЛНЕНИЕ – активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;
ОЖИДАНИЕ – пассивное состояние процесса, процесс заблокиро-ван, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;
ГОТОВНОСТЬ – также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.
В ходе жизненного цикла каждый процесс переходит из одного состояния в другое в соответствии с алгоритмом планирования процессов, реа-лизуемым в данной операци-онной системе. Типичный граф состояний процесса пока-зан на рис. 4.1.
В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ – несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно "вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.
|
|
|
Для решения задания следует учитывать тот факт, что процесс проходит в течение цикла жизни следующие этапы:
1. Резервирование ресурсов, необходимых процессу.
2. Получение исходных данных.
3. Выполнение действия (работа процесса).
4. Выдача результата.
5. Освобождение ресурсов.
Контрольный пример
Возьмем задачу создания процесса сортировки неотсортированного множества. Работа процесса в этом случае состоит из следующих этапов:
|
|
|
1. Объявление массива для размещения множества и переменных, необходимых для проведения операций.
2. Заполнение массива случайными данными выбранного типа.
3. Сортировка.
4. Выдача результатов.
5. Если сортировка закончена идти к 6, иначе к 3.
6. Выгрузка процесса и освобождение памяти.
Соответственно такой постановке задачи была написана программа, реализующая сортировку массива тремя разными способами. Для обеспечения заметной разницы при работе параллельных процессов одновременно использовались следующие классические алгоритмы сортировки: метод «пузырька», сортировка перебором и алгоритм быстрой сортировки. Подробнее с методами сортировки можно ознакомиться в книге J.L.Bentley, R.Sedgewick «Быстрые алгоритмы сортировки и поиска строк». Приведенный пример реализован на языке программирования Delphi 6.0.
/* ЛИСТИНГ ПРОГРАММЫ */
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls, ComCtrls;
type
TForm1 = class(TForm)
GroupBox1: TGroupBox;
BubOut: TPaintBox;
GroupBox2: TGroupBox;
ChoOut: TPaintBox;
GroupBox3: TGroupBox;
ChaOut: TPaintBox;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Label1: TLabel;
Label2: TLabel;
Label4: TLabel;
Label3: TLabel;
Label6: TLabel;
Label5: TLabel;
Timer1: TTimer;
Button4: TButton;
GroupBox4: TGroupBox;
GroupBox5: TGroupBox;
|
|
|
TrackBar1: TTrackBar;
procedure Button4Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Timer1Timer(Sender: TObject);
procedure ToEndOfCycle(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure BoxRePaint(Sender: TObject);
procedure TrackBar1Change(Sender: TObject);
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
procedure KillArray;
procedure FillArray;
procedure BubbleSort;
procedure ChangeSort;
procedure ChooseSort;
procedure CheckArray;
public
{ Public declarations }
end;
var
Form1: TForm1;
f : integer;
start, bubble, change, choose : array [1..75] of integer;
steps, stbubble, stchange, stchoose : integer;
Paused, changesorted : boolean;
implementation
{$R *.dfm}
procedure TForm1.KillArray;
Begin
BubOut.Refresh;
BubOut.Canvas.Pen.Color := clNavy;
ChoOut.Refresh;
ChoOut.Canvas.Pen.Color := clNavy;
ChaOut.Refresh;
ChaOut.Canvas.Pen.Color := clNavy;
end;
procedure TForm1.CheckArray;
var Mess: string;
begin
for f := 1 to 75 do begin
if ((bubble[f] <> choose[f]) or (bubble[f] <> change[f])) then exit;
end;
timer1.Enabled := false;
Mess := 'Массив отсортирован тремя разными способами.'+#13#10;
Mess := Mess + ' Результаты сортировки: '+#13#10;
Mess := Mess + ' сотрировка методом пузырька: '+inttostr(stbubble)+' шагов;'+#13#10;
Mess := Mess + ' сотрировка перебором: '+inttostr(stchoose)+' шагов;'+#13#10;
Mess := Mess + ' быстрая сотрировка : '+inttostr(stchange)+' шагов.'+#13#10;
Mess := Mess + 'Программа создана для методического пособия'+#13#10;
Mess := Mess + 'по курсу "Операционные системы"';
KillArray;
FillArray;
MessageDlg(Mess,mtInformation,[mbOK],0);
GroupBox4.Enabled := false;
end;
procedure TForm1.Button4Click(Sender: TObject);
begin
Timer1.Enabled := false;
randomize;
for f := 1 to 75 do begin
start[f] := round (random (210));
end;
FormCreate(Self);
GroupBox4.Enabled := true;
end;
procedure TForm1.FillArray;
var i: integer;
begin
for i := 1 to 75 do begin
BubOut.Canvas.MoveTo(0,i*4-2);
BubOut.Canvas.LineTo(Bubble[i],i*4-2);
BubOut.Canvas.MoveTo(0,i*4-1);
BubOut.Canvas.LineTo(Bubble[i],i*4-1);
ChoOut.Canvas.MoveTo(0,i*4-2);
ChoOut.Canvas.LineTo(Choose[i],i*4-2);
ChoOut.Canvas.MoveTo(0,i*4-1);
ChoOut.Canvas.LineTo(Choose[i],i*4-1);
ChaOut.Canvas.MoveTo(0,i*4-2);
ChaOut.Canvas.LineTo(Change[i],i*4-2);
ChaOut.Canvas.MoveTo(0,i*4-1);
ChaOut.Canvas.LineTo(Change[i],i*4-1);
end;
end;
{ TBubbleSort}
procedure TForm1.BubbleSort;
var tbubble, I, J, T: Integer;
begin
for I := 75 downto 1 do
for J := 1 to 75-1 do begin
if Bubble[J] > Bubble[J + 1] then begin
inc(stbubble);
T := Bubble[J];
Bubble[J] := Bubble[J + 1];
Bubble[J+1] := T;
Label2.caption := inttostr(stbubble);
if steps = stbubble then exit;
end;
end;
if (steps = stbubble+1) then Timer1.Enabled := false;
CheckArray;
end;
procedure TForm1.ChooseSort;
var tchoose, I, J, T: Integer;
begin
for I := 1 to 75 - 1 do
for J := 75 downto I + 1 do begin
if Choose[I] > Choose[J] then begin
inc(stchoose);
T := Choose[I];
Choose[I] := Choose[J];
Choose[J] := T;
Label4.caption := inttostr(stchoose);
if steps = stchoose then exit;
end;
end;
if (steps = stchoose+1) then Timer1.Enabled := false;
end;
procedure TForm1.ChangeSort;
var tempo: integer;
breaked: boolean;
procedure QuickSort(iLo, iHi: Integer);
var Lo, Hi, Mid, T: Integer;
begin
//if stchange > 0 then exit;
if breaked then exit;
Lo := iLo;
Hi := iHi;
Mid:= Change[(Lo + Hi) div 2];
repeat
while Change[Lo] < Mid do
Inc(Lo);
while Change[Hi] > Mid do
Dec(Hi);
if Lo <= Hi then begin
T := Change[Lo];
Change[Lo] := Change[Hi];
Change[Hi] := T;
Inc(Lo);
Dec(Hi);
inc(stchange);
if steps = stchange then begin
breaked := true;
exit;
end;
end;
until Lo > Hi;
if Hi > iLo then QuickSort(iLo, Hi);
if Lo < iHi then QuickSort(Lo, iHi);
end;
begin
if changesorted then exit;
change := start;
stchange := 0;
breaked := false;
QuickSort(1, 75);
Label6.caption := inttostr(stchange);
if not breaked then begin
changesorted := true;
Timer1.Enabled := false;
end;
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
FormCreate(Self);
BubbleSort;
ChooseSort;
ChangeSort;
KillArray;
FillArray;
stchange := 0;
stchoose := 0;
stbubble := 0;
GroupBox4.Enabled := false;
end;
procedure TForm1.Timer1Timer(Sender: TObject);
begin
inc(steps);
ChangeSort;
ChooseSort;
BubbleSort;
KillArray;
FillArray;
end;
procedure TForm1.ToEndOfCycle(Sender: TObject);
begin
timer1.Enabled := true;
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
changesorted := false;
bubble := start;
choose := start;
change := start;
stchange := 0;
stchoose := 0;
stbubble := 0;
steps := 0;
Label2.caption := inttostr(stbubble);
Label4.caption := inttostr(stchoose);
Label6.caption := inttostr(stchange);
KillArray;
FillArray;
end;
procedure TForm1.BoxRePaint(Sender: TObject);
begin
FillArray;
end;
procedure TForm1.TrackBar1Change(Sender: TObject);
begin
timer1.Interval := TrackBar1.Position * 10;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
Timer1Timer(Self);
end;
end.
end;
end.
В программе имеется несколько режимов работы:
1. Пошаговая сортировка. Производится один шаг сортировки всеми способами, которые возможны. Данный режим работы программы очень удобен для объяснения принципов различных методов сортиров-ки.
2. До окончания алгоритма. Сортировка производится до полного упорядочивания массива по какому-либо способу. Этот режим удобен для наглядного определения наиболее быстрого способа сортировки.
3. Полная сортировка. Этот режим наиболее подходит для просмотра готовых результатов сортировки, поскольку не происходит графического отображения состояния массивов в промежуточных (неот-сортированных) состояниях.
В любом режиме работы программы по завершении всех алгорит-мов выдается информация о затраченном каждым алгоритмом сортиров-ки времени на свою работу (количество обменов, произведенных алгоритмом).
При запуске программы появляется окно приложения (рис. 1.2).
Рис. 1.2. Интерфейс программы
На нем размещены следующие элементы управления:
1. Кнопки выбора режима работы программы – размещаются в группе «Сортировка» (режимы работы программы были описаны выше).
2. Ползунок «Скорость сортировки». Служит для изменения ско-рости сортировки при режиме «До окончания алгоритма». По умолча-нию установлена минимальная скорость.
3. Кнопка «Генерировать новый массив». Создается новый массив для сортировки.
Кроме того, на форме расположены 3 прямоугольных области, в каждой из которых отображается текущее состояние массива, сортируемого по определенному алгоритму. Под каждой такой областью находится строка, которая указывает, сколько времени было затрачено для достижения текущего состояния массива.
При нажатии кнопки «Генерировать новый массив» случайным образом создается массив из 75 элементов, затем пользователь выбирает скорость и режим работы программы. По ходу работы графически отображается промежуточное состояние массивов в процессе сортировки (рис. 1.3).
Рис. 1.3. Состояние программы после генерации массива
При нажатии кнопки «Один шаг» (рис. 1.4) выполняется пошаговая сортировка массива. При работе процедур сортировки счетчик шагов для каждого метода проверяется на равенство с общей переменной счет-чика шагов. Если они равны, то процедура завершает работу, иначе – продолжает.
По нажатию кнопки «До окончания алгоритма» (рис. 1.5) действия, происходящие по нажатии кнопки «Один шаг», происходят уже незави-симо от пользователя, под управлением программы. При отработке какой-либо первой процедуры сортировки «вхолостую» таймер останав-ливается. Так достигается возможность отработки одного алгоритма, и пользователь может продолжить сортировку далее любым ему угодным способом.
Рис. 1.4. Пошаговый режим работы
Рис. 1.5. Режим работы «До окончания алгоритма»
Кнопка «Полная сортировка» позволяет сразу увидеть статистику того, как работает каждый алгоритм сортировки, сколько времени ему требуется (рис. 1.6).
Рис. 1.6. Результат окончательной сортировки массива всеми способами
Лабораторная работа № 1
Цель работы: разработать программу, осуществляющую создание процесса.
Результат: отчет о лабораторной работе и программа выполняющая создание процессов.
Список вариантов
| Вариант 1 | Обмен сообщениями между процессами |
| Вариант 2 | Управление запуском внешнего процесса (запуск программы) |
| Вариант 3 | Опрос состояния портов компьютера |
| Вариант 4 | Создание процесса сортировки неотсортированного множества |
| Вариант 5 | Решение математических уравнений |
| Вариант 6 | Генерация вращающейся трехмерной фигуры |
| Вариант 7 | Перемножение двух матриц |
| Вариант 8 | Поиск записи в файле, хранящемся на диске |
| Вариант 9 | Обратный отсчет произвольного значения |
| Вариант 10 | Генерация графического объекта, движущегося в пределах окна |
МОДЕЛИРОВАНИЕ РЕЖИМА РАБОТЫ С РАЗДЕЛЕНИЕМ ВРЕМЕНИ
Многозадачные ОС подразделяются на три типа в соответствии с использованными при их разработке критериями эффективности [5, 8, 11, 12, 14]:
- системы пакетной обработки (например, OC EC),
- системы разделения времени (UNIX, VMS),
- системы реального времени (QNX, RT/11).
Системы пакетной обработки предназначались для решения задач в основном вычислительного характера, не требующих быстрого получения результатов. Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, то есть решение максимального числа задач в единицу времени. Для достижения этой цели в системах пакетной обработки используется следующая схема функционирования: в начале работы формируется пакет заданий, где каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрог-раммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие отличающиеся требования к ресурсам так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины. Например, в мультипрограммной смеси желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом-выводом. Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, то есть выбирается "выгодное" задание. Следовательно, в таких ОС невозможно гарантировать выполнение того или иного задания в течение определенного периода времени. В системах пакетной обработки переключение процессора с выполнения одной задачи на выполнение другой происходит только в случае, если активная задача сама отказывается от обслуживания процессором, например, из-за необходи-мости выполнить операцию ввода-вывода. Поэтому одна задача может надолго занять процессор, что делает невозможным выполнение интерактивных задач. Таким образом, взаимодействие пользователя с вычислительной машиной, на которой установлена система пакетной обработки, сводится к тому, что он приносит задание, отдает его диспетчеру-оператору, а в конце дня после выполнения всего пакета заданий получает результат. Очевидно, что такой порядок снижает эффективность работы пользователя.
Системы разделения времени призваны исправить основной недостаток систем пакетной обработки – изоляцию пользователя-программиста от процесса выполнения его задач. Каждому пользователю системы разделения времени предоставляется терминал, с которого он может вести диалог со своей программой. Так как в системах разделения времени каждой задаче выделяется только квант процессорного времени, ни одна задача не занимает процессор надолго, и время ответа оказывается приемлемым. Если квант выбран достаточно небольшим, то у всех пользователей, одновременно работающих на одной и той же машине, складывается впечатление, что каждый из них единолично использует машину. Ясно, что системы разделения времени обладают меньшей пропускной способностью, чем системы пакетной обработки, так как на выполнение принимается каждая запущенная пользователем задача, а не та, которая "выгодна" системе, и, кроме того, имеются накладные расходы вычислительной мощности на более частое переключение процессора с задачи на задачу. Критерием эффективности систем разделения времени является не максимальная пропускная способность, а удобство и эффективность работы пользователя.
Системы реального времени применяются для управления различными техническими объектами, такими, например, как станок, спутник, научная экспериментальная установка или технологическими процессами, такими, как гальваническая линия, доменный процесс и т.п. Во всех этих случаях существует предельно допустимое время, в течение которого должна быть выполнена та или иная программа, управляющая объектом. В противном случае может произойти авария: спутник выйдет из зоны видимости; экспериментальные данные, поступающие с датчиков, будут потеряны; толщина гальванического покрытия не будет соответствовать норме. Таким образом, критерием эффективности для систем реального времени является их способность выдерживать заранее заданные интервалы времени между запуском программы и получением результата (управляющего воздействия). Это время называется временем реакции системы, а соответствующее свойство системы – реактивностью. Для этих систем мультипрограм-мная смесь представляет собой фиксированный набор заранее разра-ботанных программ, а выбор программы на выполнение осуществляется исходя из текущего состояния объекта или в соответствии с распи-санием плановых работ.
Некоторые операционные системы могут совмещать в себе свойства систем разных типов. Например, часть задач может выполняться в режиме пакетной обработки, а часть – в режиме реального времени или в режиме разделения времени. В таких случаях режим пакетной обработки часто называют фоновым режимом.
При разработке программ, имитирующих работу процессов в режиме разделения времени, необходимо учитывать, что цикл работы программы постоянно прерывается другими выполняемыми процессами. При этом алгоритм ее работы можно представить следующим образом:
1. Работа процесса 1.
2. Поступление запроса на прерывание от процесса 2.
3. Сохранение состояния процесса 1.
4. Восстановление состояния или инициализация процесса 2.
5. Работа процесса 2.
6. Сохранение состояния процесса 2.
7. Восстановление состояния процесса 1.
8. Продолжение работы процесса 1.
Дата добавления: 2018-04-15; просмотров: 421; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!