Підготувати звіт. Захистити його.

(Зауваження. Пропоновані імена компонентів, проектів, модулів, класів і методів - лише варіант, що реалізує гарний стиль програмування).

У ході роботи може знадобитися звернутися до додаткових джерел. При роботі в Delphi можуть виявитися корисними наступні матеріали: [7, с. 50-59], [8, с. 21-60], [9, с. 32-73]. Про системний таймер докладніше див. в [4, с. 70-71], [5, с. 367-372].

Індивідуальні завдання

Загальна частина. Необхідно додати в проект компонентів класу TTimer (добавить инфу в теорию по TTimer) для автоматизації инкремента лічильника часу (тобто  ходу часу). (Довідкові відомості по використанню компонента TTimer див. у довідковій системі Delphi). На форму додати кнопку BtnAuto для запуску автоинкремента поля FTime і кнопку останова BtnStop (або одну кнопку «Старт/Стоп»).

1. Доповнити клас TMyTimer методом ClearTime. Додати кнопку скидання часу.

26. Запрограмувати при повторному натисканні на кнопку автоинкремента прискорення автоматичного ходу часу.

27. Додати на форму рядок уведення Edit для завдання інтервалу системного такту в миллисекундах.

28. Перейменувати кнопку «Stop» в «Slow». Запрограмувати при натисканні на цю кнопку вповільнення автоматичного ходу часу.

29. Замість пари кнопок використовувати одну кнопку, що забезпечує пуск/останов автоматичного ходу часу (по черзі).

30. Доповнити клас TMyTimer методом SetTime. Додати на форму однорядкове поле EdtSet, а також кнопку BtnSet для примусової установки поточного значення FTime.

31. Додати кнопку «фіксувати» (BtnFix) і мітку (Label) для висновку номера такту, на якому відбулося її натискання.

32. Запрограмувати при повторному натисканні на кнопку BtnAuto запуск зворотного відліку часу (без негативних значень і антипереповнення).

33. Додати на форму однорядкове поле (Edit) EdtK для завдання коефіцієнта (множника) для інтервалу системного такту (від 1 до 100). (Забезпечити контроль уведення в EdtK тільки чисел).

34. На кожному 10-м такті виводити в додаткову мітку (Label) LblMes напис « N-Й десяток», де N - номер десятка.

35. Доповнити клас TMyTimer методом SetTime. Через кожні N тактів виконувати автоматичне скидання поточного значення поля FTime.

36. Доповнити клас TMyTimer методом ClearTime. Створити додаткове поле FMax таймера. Через кожні FMax тактів виконувати обнуління поля FTime (виклик методу ClearTime таймера).

37. (*) Доповнити клас TMyTimer можливістю встановити «будильник» і викликати певну користувачем функцію при його спрацьовуванні.

Приклад проекту

// Текст головного модуля

unit UMain;

interface

uses

UTimer, Windows, Messages, SysUtils, Variants, Classes,

Graphics, Controls, Forms, Dialogs, StdCtrls,

ExtCtrls;

type

TFrmMain = class(TForm) // інтерфейс класу форми

BtnIncTick: TButton;

LblTick: TLabel;

SystemTimer: TTimer;

BtnAutoInc: TButton;

Edit1: TEdit;

Label2: TLabel;

procedure BtnIncTickClick(Sender: TObject);

procedure FormActivate(Sender: TObject);

procedure BtnAutoIncClick(Sender: TObject);

procedure SystemTimerTimer(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

FrmMain: TFrmMain;

MyTimer1: TMyTimer;

implementation

{$R *.dfm}

procedure TFrmMain.FormActivate(Sender: TObject);

begin

MyTimer1 := TMyTimer.Create;

LblTick.Caption := IntToStr(MyTimer1.Time);

end;

procedure TFrmMain.BtnIncTickClick(Sender: TObject);

begin

MyTimer1.IncTime;

MyTimer1.ViewTime(LblTick);

// Label1.Caption := IntToStr(MyTimer1.Time);

end;

procedure TFrmMain.BtnAutoIncClick(Sender: TObject);

begin

SystemTimer.Enabled := True;

end;

procedure TFrmMain.SystemTimerTimer(Sender: TObject);

begin

MyTimer1.IncTime;

MyTimer1.ViewTime(LblTick);

end;

end.

// Текст модуля UTimer

unit UTimer;

interface

uses SysUtils, StdCtrls;

type

TMyTimer = class(TObject)

Time: Integer;

function GetTime: Integer;

procedure IncTime;

procedure ViewTime(l:Tlabel);

end;

implementation

function TMyTimer.GetTime;

begin

Result := Time;

end;

procedure TMyTimer.IncTime;

begin

Inc(Time);

end;

procedure TMyTimer.ViewTime;

begin

L.Caption := InttoStr(Time)

end;

end.

Форма додатка:

Контрольні питання

1. Які файли входять до складу проекту Delphi і яке їхнє призначення?

38. Яка структура модуля проекту Delphi?

39. Що таке клас в ОО-Програмуванні? Опис і реалізація класу в Delphi.

40. Як створити об'єкт класу, звернутися до полів і методів об'єкта?

41. Коли досягається гарна інкапсуляція об'єктів?

42. Як забезпечити видимість елементів одного модуля (наприклад, UTimer) для іншого (наприклад, UMain)?

43. Як метод класу TMyTimer одержує доступ до необхідним йому компонентам, описаним у головному модулі UMain?

44. Які функції виконує програмний таймер в операційній системі?

45. Якими полями й методами володіє клас таймера TMyTimer і яке їхнє призначення?

46. Яким образом можна автоматизувати хід часу в розроблювальній моделі ОС?

47. Які основні можливості стандартного компонента TTimer в Delphi?

48. Де в проекті Delphi доцільно розмістити код створення класу таймера (TMyTimer).

49. Як реалізувати можливість автоматичного ходу часу в самому класі TMyTimer?

Лабораторна робота №2.

Тема: Повторення структур даних, використовуваних у моделі ОС. Моделювання простої черги.

Ціль

Згадати (освоїти) принципи структури «черга». Усвідомити роль черги в ОС.

Закріпити навички роботи із многомодульными объектно-ориентированными проектами Delphi. Навчитися працювати з покажчиками й памятью, що можна динамічно виділювати та звільнювати.

Загальне завдання

На основі проекту з таймером реалізувати клас черги для елементів типу TElement = Integer у вигляді зв'язного списку або динамічного масиву.

Вимоги до проекту

Проект повинен містити 3 модулі: для класів форми, таймера й черги. Клас черги TMyQueue містить наступні поля:

• Голова

• Хвіст,

і методи:

• Додати елемент;

• Витягти елемент;

• Очистити черга;

• Перевірити на порожнечу;

• Відобразити на формі (Memo).

На формі (як мінімум):

• кнопка (Button) IncTime,

• мітка (Label) для лічильника часу (з попереднього проекту);

• многострочное поле (Memo) для черги (MemQueue),

• рядок уведення (Edit) EdtEument що додається/ елемента черги, що витягається,

• кнопки «Додати» (BtnAdd), «Витягти» (BtnGet), «Очистити» (BtnClear)

(Назвати об'єкти - компонента відповідно)

Короткі теоретичні відомості

Черга – динамічна структура даних, доступ до якої здійснюється за принципом «Перший увійшов – перший вийшов» (FIFO). Останній елемент, що ввійшов у чергу, називається хвостом, а перший елемент на виході - головою. Черга можна реалізувати у вигляді зв'язкового стека за допомогою покажчиків або у вигляді динамічного масиву.

При реалізації у вигляді зв'язного списку кожний елемент (вузол) являє собою запис (Record) із двох полів: змістовне значення елемента й покажчик на наступний елемент. Самі елементи можуть займати несуміжні ділянки пам'яті. Щораз при додаванні нового елемента необхідно виділяти комірку пам'яті за допомогою стандартної процедури New, а при витягу елемента із черги звільнити відповідний осередок процедурою Dispose.

При реалізації у вигляді динамічного масиву елементи черги представлені своїми значеннями в елементах масиву, які розташовуються суміжно в пам'яті (один за іншим). При оголошенні масиву не вказується його розмір. Перед кожним додаванням нового елемента його довжина задається (збільшується) стандартною процедурою SetLength. При витягу елемента з такої черги необхідно одержати значення нульового елемента масиву, а потім виконати зрушення наступних елементів до початку масиву в циклі, після чого зменшити довжину масиву на один за допомогою SetLength. Тривалість цієї операції при кожному витягу елемента робить реалізацію простою чергою у вигляді динамічного масиву менш ефективної.

В ОС черзі використовуються для організації впорядкованого зберігання процесів, що очікують звільнення ресурсу, завдань на печатку та ін.

Типовий порядок виконання й рекомендації

1. Підготувати папку для нового проекту.

50. Відкрити в Delphi проект лабораторної роботи № 1 з таймером і зберегти його в підготовленій папці під новим ім'ям (наприклад, PrjQueue).

51. Додати на форму компонента Edit, Memo і 3 кнопки (Button) для роботи із чергою.

52. Створити новий модуль UQueue і в ньому тип TElement = Integer, TNode як запис із полями типу TElement і ^TNode, а також заготівлю (інтерфейс) класу TMyQueue з полями:

Head: ^TNode;

Tail: ^TNode;

і методами:

AddElement(e: TElement);

GetElement(): TElement;

Cleare();

IsEmpty(): Boolean;

ViewQueue(m: TMemo);

В оброблювач події OnActivate форми додати оператор створення об'єкта черги.

53. Реалізувати методи черги;

54. Створити й реалізувати оброблювачі натискання на кнопки керування чергою, зв'язавши їх з методами об'єкта - черги.

55. Скомпілювати проект. Перевірити й налагодити його роботу. Оформити протокол.

Зауваження. Налагодження, загалом кажучи, доцільно робити в міру реалізації нових блоків коду (методів). У загальному випадку, якщо робота одних блоків залежить від інших, ще не реалізованих, їх доцільно заміняти тимчасовими «заглушками», що приймають дані й повертають підготовлені заздалегідь дані замість отриманих. Це дозволяє перевірити правильність загального алгоритму функціонування додатка або методу.

При виконанні даної роботи можуть придадуться додаткові джерела інформації: про реалізацію списків в Delphi див. в [10, с. 31-60], про реалізацію черг в Delphi - в [10, с. 65-71].

Індивідуальні завдання

1. Забезпечити автоматизацію додавання елемента з однорядкового поля EdtElement у чергу через N тактів таймера. N задається в окремому однорядковому полі EdtN. Режим автоматичного додавання включати за допомогою спеціального прапорця (CheckBox) CBAuto.

56. Забезпечити автоматизацію витягу елемента із черги в EdtElement через кожні N тактів (N задається в окремому однорядковому полі EdtN). Режим автоматичного витягу включати за допомогою спеціального прапорця (CheckBox) CBAuto.

57. Створити два об'єкти-черги Q1 і Q2, а також два відповідних многострочных поля MemQueue1 і MemQueue2. При натисканні кнопки BtnAdd елементи з рядка уведення EdtElement поміщати по черзі в Q1 і Q2. Витягати елементи з Q1 і Q2 також по черзі.

58. Створити однорядкове поле EdtGet для елемента, що витягається із черги. Через кожні 10 тактів таймера автоматично витягати елемент із черги в EdtGet і поміщати в чергу елемент із EdtElement.

59. На кожному 10-м такті таймера автоматично поміщати значення з EdtElement у чергу й автоматично заповнювати EdtElement новим випадковим значенням. При натисканні на кнопку BtnAdd додавати елемент із EdtElement у чергу й очищати поле EdtElement.

60. Доповнити клас таймера методом SetTime. При витягу елемента із черги виконувати установку поточного часу таймера значенням елемента, що витягається.

61. При додаванні нового елемента в чергу його значення брати рівним поточному значенню поля FTime. Помістити на форму прапорець (CheckBox), що включає режим автоматичного додавання нового елемента в чергу.

62. Помістити на форму прапорець (CheckBox) CBRound, що включає наступний режим функціонування черги: витягається элемент, що, автоматично попадає у хвіст черги.

63. Помістити на форму однорядкове поле EdtGet для елементів, що витягаються із черги. Забезпечити автоматичний витяг елемента із черги, якщо поле EdtGet порожньо, а також автоматичне очищення поля EdtGet на кожному 10-м такті таймера.

64. Помістити на форму однорядкове поле EdtGet для елементів, що витягаються із черги. На кожному такті таймера зменшувати значення поля EdtGet на 1. Коли воно стає рівним 0, автоматично витягати елемент із черги (якщо вона не порожня).

65. Додати на форму перемикач (RadioGroup) RGAction, що задає одне із трьох автоматично виконуваних дій: додавання елемента, витяг або очищення черги (плюс один перемикач для відключення автоматичного режиму). Автоматична дія виконується через кожні 10 тактів таймера.

66. Змінити тип елемента черги з Integer на String. У поле EdtElement допускати уведення тільки латинських символів. По натисканні клавіші Enter автоматично додавати елемент у чергу й очищати EdtElement.

67. (*) Доповнити клас черги полем FMax, що задає максимальну кількість елементів черги, а також методом IsFull перевірки черги на повноту. Доповнити наявний метод AddElement перевіркою на заповнювання черги перед приміщенням елемента.

Приклад проекту

У даному прикладі проект побудований на основі проекту з лабораторної роботи 1. Модуль UTimer не перетерпів змін. Тому далі приводиться текст модулів форми й черги. Черга реалізована у вигляді динамічного зв'язного списку.

// Головний модуль (модуль головної форми)

unit UMain;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls,

Forms, Dialogs, StdCtrls, IdTrivialFTPBase,

UTimer, UQueue;

type

TFrmMain = class(TForm)

BtnIncTick: TButton;

LblTime: TLabel;

LblTimer: TLabel;

GBQueue: TGroupBox;

EdtNode: TEdit;

LblEdtNode: TLabel;

MemQueue: TMemo;

LblAllQueue: TLabel;

BtnAddElement: TButton;

BtnTakeOut: TButton;

BtnClearQueue: TButton;

LblTakedElement: TLabel;

EdtTakenElement: TEdit;

procedure BtnIncTickClick(Sender: TObject);

procedure FormActivate(Sender: TObject);

procedure BtnAddElementClick(Sender: TObject);

procedure BtnTakeOutClick(Sender: TObject);

procedure BtnClearQueueClick(Sender: TObject);

end;

var

FrmMain: TFrmMain;

MyTimer: TMyTimer;

Queue1: TMyQueue;

implementation

{$R *.dfm}

procedure TFrmMain.FormActivate(Sender: TObject);

begin

MyTimer := TMyTimer.Create;

MyTimer.View(LblTime);

Queue1 := TMyQueue.Create;

end;

procedure TFrmMain.BtnIncTickClick(Sender: TObject);

begin

MyTimer.IncTime;

MyTimer.View(LblTime);

// LblTime.Caption := IntToStr(TMyTimer.time);

end;

procedure TFrmMain.BtnAddElementClick(Sender: TObject);

begin

if EdtNode.Text <> '' then

begin

Queue1.QAdd(StrToInt(EdtNode.Text));

Queue1.View(MemQueue);

end;

end;

procedure TFrmMain.BtnTakeOutClick(Sender: TObject);

var

A: Integer;

begin

if not Queue1.QEmpty then

begin

Queue1.QDel(A);

EdtTakenElement.Text := IntToStr(A);

Queue1.View(MemQueue);

end;

end;

procedure TFrmMain.BtnClearQueueClick(Sender: TObject);

begin

Queue1.QClear;

Queue1.View(MemQueue);

end;

end.

// Модуль черги

unit UQueue;

interface

uses

StdCtrls, SysUtils;//, process;

type

TElement = Integer;

TLinkNode = ^TNode; // покажчик на вузол (елемент) черги

TNode = record // сам вузол - комбінація значення й посилання на наступний

P: TElement;

Next: TLinkNode;

end;

TMyQueue = class {(TObject) } // клас Черга

_out: TLinkNode; // покажчик на перший елемент у черзі (голова)

_in: TLinkNode; // покажчик на останній елемент у черзі (хвіст)

{фактично, наш об'єкт-черга - лише пари покажчиків,

а дані зберігаються як локальні динамічні змінні функції QAdd}

constructor Create;

destructor Destroy;

function QEmpty: Boolean; // чи порожня

procedure QClear; // очищення

procedure QAdd(PCB: TElement); // додавання елемента

procedure QDel(var PCB: TElement); // видалення (витяг) елемента

procedure View(M: TMemo);

end;

implementation

{ TMyQueue }

constructor TMyQueue.Create;

begin

_in := nil; // голова = хвіст = ознака кінця

_out := nil

end;

destructor TMyQueue.Destroy;

begin

QClear

end;

procedure TMyQueue.QAdd(PCB: TElement);

var R: TLinkNode; // уводимо локальну змінну-покажчик

begin

New(R); // створення осередку черги як динамічної змінної

R^.P := PCB; // вхід процедури записуємо в осередок (значення)

R^.Next := nil; // посилання на наступний - ознаку кінця

if qEmpty then // якщо черга порожня,

begin

_in := R; // те додається элемент, щоМ, - перший і останній

_out := R // (голова = хвіст = елемент)

end

else // якщо не порожня,

begin

_in^.Next := R; // у тек. хвоста покажчик наступного -

// на додається элемент, щоМ,

_in := R // а тепер значення нового хвоста = елемент

end;

end;

procedure TMyQueue.QClear;

var R: TElement;

begin

while not QEmpty do QDel(R);

_out := nil

end;

procedure TMyQueue.QDel(var PCB: TElement); // витяг тек. голови

var R: TLinkNode;

begin

R := _out; // привласнюємо тимчасовий змінної тек. голову

if not QEmpty then // якщо черга не порожня,

begin

PCB := R^.P; // привласнюємо входу значення тек. голови,

_out := _out^.Next; // а нова голова = наступний елемент

// (по указ-лю старої голови на наступний)

Dispose(R) // видалення дин. змінної й звільнення пам'яті

end;

if _out = nil then

_in := nil;

end;

function TMyQueue.QEmpty: Boolean;

begin

QEmpty := _out = nil; // порівняння з ознакою кінця й повернення рез-та

end;

procedure TMyQueue.View(M: TMemo);

var Cur: TLinkNode;

begin

Cur := _out;

M.Clear;

while Cur <> nil do

begin

M.Lines.Add(IntToStr(Cur.P));

Cur := Cur.Next;

end;

end;

end.

Зовнішній вигляд форми додатка:

Контрольні питання

1. Як створити клас на основі існуючого класу?

68. Спадкоємцем якого класу є клас, при створенні якого клас-предок не вказується? Якими властивостями володіє створюваний у такий спосіб клас?

69. Що таке черга? У чому її подібність і розходження в порівнянні зі стеком?

70. Для чого використовуються черги в системному ПО?

71. Які основні способи реалізації черги в Delphi? Які їхні переваги й недоліки?

72. Які поля й методи розробленого класу черги в моделі ОС?

73. Яка логіка функціонування методу додавання елемента в класі черги?

74. Яка логіка функціонування методу витягу елемента в класі черги?

75. Яка логіка функціонування методів перевірки черги на порожнечу й очищення черги?

76. Які класи Delphi можна (доцільно) використовувати в якості батьківських для класу черги?

77. Які методи на додаток до наявним теоретично може знадобитися додати в клас черги?

78. Наскільки доцільне використання класу TList в Delphi для реалізації черги?

Лабораторна робота №3.

Тема: Моделювання черги із пріоритетами.

Ціль

Засвоїти принципи структури «черга із пріоритетами», а також необхідність її використання в ОС. Відробити методику створення й використання підкласів, а також перевизначення батьківських методів.

Загальне завдання

На основі проекту попередньої лабораторної роботи (з таймером і чергою) створити проект, у якому реалізувати клас черги із пріоритетами (мінімум два - високий і низький). Елементи з високим пріоритетом повинні витягати із черги перш, ніж елементи з низьким пріоритетом. Налагодити й продемонструвати роботу проекту.

Вимоги до проекту

Проект повинен містити мінімум 3 модулі: для класів форми, таймера й черги пріоритетів. Тип елемента повинен являти собою запис, що включає поле пріоритету.

Клас черги TMyQueuePriority повинне містити ті ж поля й методи, що й колишній клас черги (TMyQueue).

Склад компонентів форми: на додаток до наявних елементів необхідно додати однорядкове поле (Edit) для пріоритету елемента (EdtPrior).

Короткі теоретичні відомості

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

Черги пріоритетів часто використовуються в операційних системах при плануванні процесів, створюючи передумови для більше гнучкого керування ресурсами.

Існують два підходи до організації черги пріоритетів:

а) Черга не впорядкована. Новий елемент завжди міститься в кінець черги. При видаленні елементів із черги шукається перший поступивший з елементів з найвищим пріоритетом. При такій організації черги спрощується вставка нового елемента, але утрудняється вибірка елемента, що вимагає виконання пошуку (по всій черзі в загальному випадку).

б) Черга впорядкована. Новий елемент міститься відразу на своє місце. Із черги завжди віддаляється перший елемент (голова). При такій організації черги спрощується вибірка елемента, але утрудняється вставка нового елемента (вставка у відсортований список вимагає перегляду в середньому половини елементів списку).

Типовий порядок виконання й рекомендації

Типовий порядок виконання даної роботи принципово не відрізняється від порядку виконання попередніх робіт. Крім того, окремі його кроки можуть залежати від індивідуального варіанта завдання або переваг студента. Наприклад, можна створити додатковий модуль для класу черги із пріоритетами або ж модифікувати існуючий модуль і клас. Можна створювати новий клас черги із пріоритетами як самостійний або ж зв'язаний спадкуванням із класом звичайної черги. Будемо думати, що до даного моменту студент уже досить освоївся із середовищем Delphi, щоб самостійно приймати подібні рішення в необхідних випадках.

Як уже вказувалося вище, рекомендується підтримувати проект у працездатному стані практично із самого початку роботи, виконуючи налагодження після внесення кожного блоку коду. Це істотно спрощує загальне завдання налагодження, що у випадку наявності помилок у великому обсязі неперевіреного коду може стати непід'ємної.

При виконанні даної роботи можуть придадуться додаткові джерела інформації: про реалізацію черг із пріоритетами в Delphi див. в [10, с. 71-73], про сортування - в [10, с. 222-255], про пошук - в [10, с. 257-270].

Індивідуальні завдання

1. Реалізувати впорядковану чергу із пріоритетами «низький», «середній» і «високий» ( типу, щоперераховується,).

2. Реалізувати неупорядковану чергу із пріоритетами «низький», «середній» і «високий» ( типу, щоперераховується,). Забезпечити часткове впорядкування черги через кожні 10 тактів таймера.

3. Реалізувати впорядковану чергу із пріоритетами від 0 (найнижчий) до 9 (найвищий).

79. Реалізувати неупорядковану чергу із пріоритетами від 0 (найнижчий) до 9 (найвищий).

80. Реалізувати впорядковану чергу із пріоритетами False (низький) і True (високий).

81. Реалізувати неупорядковану чергу із пріоритетами False (низький) і True (високий). Додати метод сортування черги й кнопку його виклику.

82. Реалізувати впорядковану чергу із пріоритетами від 0 (найвищий) до 15 (найнижчий).

83. Реалізувати неупорядковану чергу із пріоритетами від 0 (найвищий) до 15 (найнижчий).

84. Реалізувати впорядковану чергу із пріоритетами від -5 (найнижчий) до +5 (найвищий).

85. Реалізувати неупорядковану чергу із пріоритетами від -5 (найнижчий) до +5 (найвищий).

Приклад

Наведений нижче вихідний текст демонструє приклад реалізації черги пріоритетів процедурним способом. (При рішенні індивідуального завдання необхідно використовувати объектно-ориентированный підхід).

type

celltype = record

element: processtype;

next: ^celltype

end;

processtype = record

id: integer;

priority: integer

end;

PRIORITYQUEUE = ^celltype;

{ осередок указує на заголовок списку }

procedure initial ( Р: integer ) ;

{initial указує процесу з ідентифікатором Р місце в черзі}

var

process: processtype;

begin

process.id:= P;

process.priority:= - currenttime;

INSERT (process, WAITING)

end; { initial }

function DELETEMIN ( var A: PRIORITYQUEUE ):^celltype;

var

current: ^celltype;

{ указує на осередок, що буде перевірена наступної }

lowpriority: integer;

{ містить раніше знайдений найменший пріоритет }

prewlnner: ^celltype;

{ указує на осередок, що містить елемент

с найменшим пріоритетом }

begin

if A^.next = nil then

error('Не можна знайти мінімум у порожньому списку') else

begin

lowpriority:= р(A^.next^.element);

{ функція р повертає пріоритет першого елемента. Відзначимо, що А вказує на осередок заголовка, що не містить елемента }

prewinner:= A;

current:= A^.next;

while current^.next <> nil do

begin

{ порівняння поточного найменшого пріоритету із пріоритетом наступного елемента }

if р(current^.next^. element)<lowpriority then

begin

prewinner:= current;

lowpriority:= p(current^.next^.element)

end;

current:= current^.next

end;

DELETEMIN := prewinner^ .next;

{ повертає покажчик на знайдений елемент }

prewinne^.next:= prewinner^.next^.next

{ видаляє знайдений елемент зі списку }

End;

end; { DELETEMIN }

Контрольні питання

1. Що таке поліморфізм об'єктів? Як він реалізується засобами Delphi?

2. Для чого використовуються пріоритети в ОС?

3. Які існують алгоритми сортування неупорядкованого списку? Які з них найбільш застосовні до завдання даної лабораторної роботи й чому?

4. Які існують алгоритми пошуку в неупорядкованому списку? Які з них найбільш застосовні до завдання даної лабораторної роботи й чому?

5. Чи є в Delphi засобу сортування елементів?

6. Які принципові відмінності процедурного й объектно-ориентированного підходів до розробки програмного забезпечення?

Лабораторна робота №4.

Тема: Моделювання процесу й черги процесів.

Ціль

Добре засвоїти поняття процесу, перелік його характеристик і станів у типовий ОС. Продовжити придбання навичок розвитку проекту в Delphi включенням додаткових класів і модулів.

Загальне завдання

Доробити проект лабораторної роботи №3 шляхом включення в нього додаткового модуля процесу, що містить опис класу процесу. Додати на форму кнопку створення об'єкта-процесу з характеристиками, зазначеними на формі. Налагодити функціонування черги процесів. Намалювати діаграму станів процесу.

Вимоги до проекту

Проект повинен містити модулі головної форми, таймера, черги й процесу (UProcess). Клас процесу (TProcess) повинен мати наступні поля:

• PID (ідентифікаційний номер процесу)

• ім'я процесу (строкового типу)

• пріоритет процесу

• необхідний час виконання на CPU (процесорі)

• необхідний час виконання в зовнішньому ресурсі

• час прибуття в систему

• відпрацьований час на CPU

• відпрацьований час у зовнішньому ресурсі

• стан процесу ( типу, щоперераховується,)

і методами:

• конструктор

• процедура висновку характеристик процесу на форму

• функція повернення ознаки завершення роботи на CPU

• процедура підвищення часу знаходження процесу на CPU

• процедура підвищення часу знаходження в зовнішньому ресурсі

Клас черги елементів перетворити в чергу процесів.

На форму необхідно додати однорядкові поля (типу Edit) для розміщення характеристик процесу, а також кнопки створення й видалення об'єкта-процесу. Створюється процес, для якого визначені всі вихідні дані на формі, у тому числі ще не зайнятий PID. Після натискання на кнопку «Створити процес» процес позначається на формі як «новий». При додаванні процесу в чергу необхідно перевіряти коректність уведених даних. процес, Що Потрапив у чергу, міняє свій стан «новий» на «готов». Багатострочне поле (Memo) відображення вмісту черги розширити для розміщення в ньому всіх характеристик процесів.

Логіка функціонування на початковому етапі (на додаток до наявної логіки функціонування): користувач задає характеристики процесу на формі; процеси під час відсутності ресурсів не виконуються, однак вибудовуються в чергу в міру їхнього додавання. При витягу процесу із черги його характеристики відображаються на формі (старі значення, якщо вони існують, заміщаються новими), при цьому процес позначається як «виконующийся».

Створені класи повинні бути добре инкапсулировани, тобто кожний клас повинен розроблятися й модифікуватися по можливості незалежно від реалізації інших класів і користувальницького інтерфейсу.

Короткі теоретичні відомості

Поняття процесу є одним з найважливіших у СПО, оскільки вся корисна робота обчислювальної системи зводиться до виконання процесів.

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

ОС ураховує процеси по їхніх унікальних ідентифікаторах PID.

Процеси як об'єкти характеризуються рядом властивостей, одним їх яким є стан (властивості перераховані вище у вимогах до проекту). Основні типові стани процесу:

• «новий» - процес тільки що створений і поки не розміщений у чергах і не займає ресурсів;

• «готовий до виконання» («очікує CPU») - процес поміщений у чергу до процесора й очікує його звільнення;

• «очікує зовнішній ресурс» - процес поміщений у чергу до зовнішнього ресурсу й очікує його звільнення;

• «виконується» – займає CPU, тобто  процесор виконує команди процесу;

• «займає зовнішній ресурс» - зовнішній ресурс виконує команди процесу.

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

Часто використовуваним способом відобразити стану процесу є так звана діаграма станів процесу. На ній зображуються прямокутними блоками стану або елементи архітектури системи, з якими безпосередньо зв'язані ці стани, а стрілками - переходи зі стану в стан. Приклад діаграми станів з архітектурними блоками системи зображений на малюнку 1:

М алюнок 1 – Проста діаграма станів процесу

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

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

Типовий порядок виконання й рекомендації

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

У нашім випадку процес може перебувати в станах «відображається на формі» і «у черзі». Стану «відображається на формі» зіставимо стану «новий» і «виконується», а стану «у черзі» - стан «готовий до виконання».

При виконанні даної роботи можуть придадуться додаткові джерела інформації: про процеси й потоки докладніше див. в [1, с. 24-37], [2, с. 25-42], [4, с. 96-106], [5, с. 97-125].

Індивідуальні завдання

1. Створити окремі компоненти для процесів у станах «новий» і «готовий». Забезпечити імітацію виконання процесів: на кожному такті таймера збільшувати на 1 поле «відпрацьований час на CPU». Коли воно досягає значення «необхідний час виконання на CPU», автоматично видалити відповідний об'єкт-процес і зробити автоматичний витяг наступного процесу із черги.

2. Створити код автоматичного створення нового процесу з випадковими значеннями характеристик. Виконувати даний код через рівні (із заданням значення інтервалу) проміжки часу.

3. Створити код автоматичного створення нового процесу з випадковими значеннями характеристик. Виконувати даний код через випадкові проміжки часу.

4. Створити черга процесів як підклас простої черги.

5. Створити неупорядковану чергу процесів. Додати метод сортування черги за заданим критерієм процесу, а також кнопку його виклику.

6. По натисканні на кнопку «Створити процес» при відсутності характеристик у відповідних полях згенерувати їхнім випадковим образом.

Приклад

Приклад тексту модуля процесу:

unit UProcess;

interface

uses SysUtils, StdCtrls, UTimer;

type

TProcess = class

name: string[10]; // ім'я процесу

pid: word; // ідентифікаційний номер процесу

burstTime: word; // інтервал безперервного виконання на СР

arrivalTime: word;// такт створення процесу

CPUTime: word; // реальний час безперервної роботи на ЦП

status: (ready, wait, run, runR); // стан процесу

constructor create(t: timer; curPID: word);

// установлює початкові значення параметрів процесу

procedure view(m: TMemo); // відображає дані про процес

// виконується перевірка завершення роботи СР

function finished: outto;

// збільшення на 1 такт часу роботи на СР

procedure incCPUTime;

end;

implementation

constructor TProcess.create;

begin

pid := curPID;

name := 'P' + inttostr(pid);

arrivalTime := t.getTime;

status := ready;

burstTime := random(7)+1;

cpuTime := 0;

end;

procedure TProcess.view(m: TMemo);

begin

// с нового рядка додаються наступні дані про процес

m.ReadOnly := true;

m.lines.Clear;

m.lines.Add('Process '+name);

m.lines.Add('pid= '+inttostr(pid));

m.lines.Add('Arrival time '+inttostr(arrivalTime));

m.lines.Add('Burst time '+inttostr(burstTime));

if status = ready then

m.lines.add('Ready')

else

if status = wait then

m.lines.add('Waiting')

else

m.lines.add('Running ' + inttostr(CPUTime)) ;

end;

function TProcess.finished: outto;

var res: byte;

begin

if burstTime = CPUtime then

begin

if status = run then

begin

// куди піде процес після СР - випадкова подія

res := random(2); // (0, 1)

if res = 1 then // якщо "1"

begin

result := toR1; // те на ресурс1

status := ready; // приймає стан "готовий до роботи"

// випадковим образом генерується необх. час роботи на ресурсі

burstTime := random(12) + 1;

CPUtime := 0; // реальний час роботи = 0

end

else

begin // якщо "0", те залишає систему

result := terminated;

end;

end

else

begin

burstTime := random(8)+1;

status := ready;

result := toCPU;

end;

end

else

result := none;

end;

procedure TProcess.incCPUTime;

begin

inc(CPUTime);

end;

end.

Контрольні питання

1. Що таке процес?

2. Які типові характеристики процесу в ОС?

3. Які характеристики процесу можуть використовуватися на практиці для призначення процесу певного пріоритету?

4. Що таке динамічне підвищення пріоритету процесу? На якій підставі воно може виконуватися?

5. Які типові стани процесу в ОС?

6. Що являє собою діаграма станів процесу?

7. Що таке шаблони класів і як їх можна використовувати при створенні черги процесів.

Лабораторна робота №5. Тема: Моделювання ресурсів cpu і зовнішніх пристроїв.

Ціль

Ясно зрозуміти роль об'єктів-ресурсів в ОС, їхні характерні властивості, принципи їхньої взаємодії з іншими об'єктами ОС. Освоїти способи їхнього моделювання в середовищі Delphi. Удосконалити навички створення добре инкапсулірованих класів.

Загальне завдання

На основі проекту попередньої лабораторної роботи створити проект, що включає модуль і клас ресурсу, об'єктами якого стануть центральний процесор (CPU) і зовнішній ресурс (наприклад, периферійний пристрій висновку). За допомогою моделей даних ресурсів розробити й налагодити імітацію виконання процесів на ресурсах. (Якщо в базовому проекті є імітація виконання процесу, перенести відповідні елементи логіки в клас ресурсу).

Вимоги до проекту

Проект повинен містити модулі головної форми, таймера, черги, процесу й ресурсу (UResource).

У модулі ресурсу повинне розміщатися опис класу ресурсу (TResource), в інтерфейс якого входять:

поля:

• ім'я ресурсу (строкового типу)

• стан ресурсу (вільний / зайнятий)

• поточний процес (класу TProcess, що виконується на ресурсі)

методи:

• конструктор (із вхідним параметром «ім'я ресурсу»);

• процедура View висновку на форму (в Memo) властивостей процесу, що виконується;

• функція GetStatus одержання стану ресурсу;

• процедура LoadProcess завантаження на ресурс нового процесу (P: TProcess);

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

Короткі теоретичні відомості

Поняття ресурсу, як і процесу, є одним з основних у СПЗ. У широкому розумінні до ресурсів ставляться будь-які об'єкти, що розподіляються в системі. Крім властивості расподілу (спільності використання) ресурси звичайно володіють також властивостями відносної стабільності, повторного використування й недостатності (зухвалої конкуренції з боку процесів-споживачів). Ресурси в системі можна класифікувати в такий спосіб:

- неподільні (зовнішні повільні пристрої);

- поділювані:

- використовувані одночасно (пам'ять);

- використовувані псевдопаралельно (процесор).

Крім CPU, основної пам'яті й периферійних пристроїв до ресурсів звичайно відносять також поділювані канали уведення-виведення, поділювані простори адрес (ліній, осередків), наприклад, простір портів уведення- виведення, системні таблиці враховуються в ОС об'єктів (наприклад, таблиці дескрипторів процесів, відкритих файлів, вікон), буферы повідомлень та ін.

Дана робота присвячена моделюванню ресурсів, не використовуваних одночасно (CPU, периферія). Для таких ресурсів характерною властивістю є їхній поточний стан (вільний / зайнятий). Для організації псевдопаралельного використання може здійснюватися примусове витиснення процесів після закінчення кванта системного часу. При цьому стан «вільний» для ресурсу виявляється транзитним (тобто, ресурс у ньому не затримується), і він відразу знову виявляється в стані «зайнятий».

Ресурси залежно від своєї природи можуть мати різні характеристики. Для ресурсів, не використовуваних одночасно, загальними характеристиками є

• продуктивність, що оцінює кількість операцій за період реального часу,

• пропускна здатність (кількість виконаних завдань в одиницю машинного часу під час відсутності простоїв),

• поточна й середня завантаженість із урахуванням простоїв ресурсу.

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

У даній роботі термін «процес займає ресурс» може замінятися терміном «процес виконується на ресурсі» (або «у ресурсі»). Це пов'язане з тим, що тут моделюються ресурси, здатні виконувати команди процесів, що дозволяє говорити про виконання процесів за допомогою ресурсів.

Типовий порядок виконання й рекомендації

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

При виконанні даної роботи можуть придадуться додаткові джерела інформації: про ресурси докладніше див. в [1, с. 24, с. 44-47], [2, с. 25, с. 42-45], [5, с. 185-187].

Індивідуальні завдання

Загальна частина. З огляду на відмінні риси ресурсів CPU і периферійного пристрою, створити для CPU окремий клас як спадкоємець загального класу TResource.

1. Реалізувати витиснення процесів на CPU, задаючи величину кванта за допомогою окремого однорядкового поля уведення на формі.

2. Забезпечити відображення на формі статистичної інформації про використання ресурсу: пропускної здатності, завантаженості та ін.

3. (*) Додати на форму кнопку створення нового екземпляра ресурсу. Після натискання на неї створюється новий об'єкт-ресурс, а на формі відображаються компоненти для створеного ресурсу. Надалі процеси із загальної черги можуть попадати на створений ресурс, якщо він вільний.

Приклад

Приклад тексту модуля ресурсу:

unit UResource;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics,

Controls, Forms, Dialogs, StdCtrls, UProcess;

type

Tresource = class

name: string[20]; // ім'я ресурсу

status: resourceStatus; // стан ресурсу

curProc: TProcess; // процес, що перебуває на СР

constructor create(nm: string);

procedure view(m: Tmemo); // висновок інформації про ресурс у мемо

function getStatus: resourceStatus; // повернення значення статусу

// завантаження тек. процесу на ресурс

procedure loadProcess(p: TProcess);

end;

implementation

constructor Tresource.create;

begin

status := rFree; // при створенні ресурсу його стан - вільний

name := nm;

end;

procedure Tresource.view;

var

str: string[10];

begin

m.lines.clear;

if status = rBusy then // якщо стан = зайнятий

curProc.view(m); // тоді, у мемо записується ім'я процесу

// дописуються рядки ресурс + його ім'я

m.lines.insert(1, 'Resource' + name);

if status = rBusy then

str := 'Busy' // ресурс зайнятий

else

str := 'Free'; // або вільний

m.lines.insert(2,'Status' + str);

end;

function Tresource.getStatus;

begin

result := status;

end;

procedure Tresource.loadProcess;

begin

// при завантаженні процесу сост. ресурсу стає «зайнятий»

status := rBusy;

curProc := p;

curProc.CPUtime := 0;

curProc.status := run;

end;

end.

Контрольні питання

1. Які об’єкти відносяться в ОС до ресурсів?

2. Якими властивостями володіють ресурси?

3. Для ресурсів якого типу характерний поточний стан вільний або зайнятий?

4. Що таке пропускна здатність ресурсу? В яких одиницях вона виміряється?

5. Яким чином задається ім’я ресурсів в розробленій програмі?

В який момент часу і при яких умовах відбувається завантаження нового процесу на ресурс?

Лабораторна робота №6.

Тема: Моделювання планувальника процесів.

Ціль

Закріпити теоретичні знання про планування процесів. У процесі практичної роботи довідатися особливості моделювання об'єкта-планувальника в середовищі Delphi.

Загальне завдання

На основі проекту попередньої лабораторної роботи створити проект, що включає у вигляді класів моделі таймера, процесу, ресурсу, черги процесів і планувальника процесів. Керування процесами (перевірку ресурсів на зайнятість, завантаження процесів на ресурси й звільнення останніх) перенести в клас планувальника. Реалізувати метод простого планування FCFS.

Вимоги до проекту

Модель планувальника оформити у вигляді класу TScheduler, описаного в окремому модулі UScheduler. Інтерфейс класу планувальника:

поля:

• об'єкт - процесор;

• об'єкт - зовнішній ресурс;

• черга до процесора;

• черга до зовнішнього ресурсу;

методи:

• конструктор;

• обробити новий такт (робить зміни в системі на кожному новому такті).

Саме в методі обробки нового такту повинна бути закладена логіка реалізованої дисципліни планування процесів.

Зауваження. Однієї з особливостей розроблювальних проектів всіх попередніх лабораторних робіт є розміщення системних об'єктів (таймер, черга процесів, ресурси), коду їхнього створення, виклику їхніх методів у тексті модуля головної форми, а саме - в оброблювачах подій. Дана особливість є свого роду відхиленням від принципів ОО-Проектування (які рекомендують розмежовувати логіку й інтерфейс додатка), а також певною невідповідністю між моделлю й структурою типовий ОС (оскільки в ОС завдання планування процесів покладені на окремий об'єкт - планувальник процесів). З метою усунути в максимально можливому ступені ця невідповідність саме й рекомендуються системні об'єкти - таймер, черга процесів, ресурси -, а також логікові керування процесами (перевірку ресурсів на зайнятість, витяг процесів із черг, завантаження процесів на ресурси й звільнення останніх) перенести в клас планувальника.

Короткі теоретичні відомості

Основною метою об'єкта-планувальника в даній роботі є реалізація певної дисципліни (методу) планування процесів. Планування процесів містить у собі рішення наступних завдань:

• визначення моменту часу для зміни виконуваного процесу;

• вибір процесу в черзі готових процесів для його постановки на виконання;

• перемикання контекстів процесів, що поміняють один одного на процесорі.

Перші два завдання вирішуються, в основному, програмними засобами, а остання - у значній мірі апаратно.

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

Алгоритми планування, що реалізують однозадачность, є більше простими, оскільки не припускають переривання роботи процесу (тобто перемикання на інший процес) до його остаточного завершення. Проте, в однозадачних ОС може допускатися одночасне знаходження в пам'яті декількох процесів, один із яких викликає інші, припиняючи на час їхньої роботи своє виконання.

Алгоритми, що реалізують багатозадачність (мультипрограмність, багатопроцесність), розділяються на що не витісняють і витісняють. При не витіснюючей многозадачности активний процес виконується доти, поки він сам, за власною ініціативою, не віддасть керування планувальникові операційної системи для того, щоб той вибрав із черги інший, готовий до виконання процес. При витісннюючей многозадачности рішення про перемикання процесора з виконання одного процесу на виконання іншого приймається планувальником операційної системи, а не самим активним завданням.

Метод планування FCFS (First Come – First Served) є найбільш простим однозадачным методом планування процесів, що працюють за принципом «перший прийшов – перший обслужений». При цьому процеси виконуються безупинно (крім апаратних переривань) у порядку їхнього надходження в систему. Довгі завдання можуть надовго загальмувати систему, при цьому інші процеси будуть, фактично, «заморожені», а користувачі, їх що запустили – довго очікувати їхнього завершення (тобто, великий час очікування).

Планування за принципом SJF (Shortest Job — First (Served)) «найкоротше завдання – першим (обслуговується)») являє собою інший однозадачний алгоритм, відповідно до якого наступної для виконання вибирається процес, що очікує, з мінімальним оцінним робочим часом, що залишається до завершення (свого роду пріоритет). Це дозволяє зменшити час очікування для коротких завдань, але збільшує його для довгих.

Ще один простий метод планування процесів полягає в тому, що процесор надається тому процесу, що має найвищий пріоритет (певний у вигляді числової характеристики у властивостях процесу). Даний принцип називається HPF («Highest Priority – First (Served)», «найвищий пріоритет – першим (обслуговується)»). Якщо витиснення не допускається, то процес із найвищим пріоритетом виконується доти, поки не скінчиться або не заблокує сам себе. При цьому якщо в чергу надходить процес із більше високим пріоритетом, чим у поточного процесу, що виконується, то він повинен чекати, поки поточний процес не звільнить процесор. Якщо витиснення дозволене, то з появою процесу з більше високим пріоритетом поточний процес переривається й керування переходить до знову прибулого процесу. Витиснутий процес вертається в чергу готових процесів. У правилі найвищого пріоритету компоненти пріоритету, застосування витисненні й організація черги є вільними параметрами реалізації.

Значно знизити час очікування дозволяють алгоритми реалізації багатозадачності. З них методи з витисненням є більше стабільними, тому що гарантують виділення процесорного часу всім процесам навіть у випадку запуску процесів, що некоректно використовують CPU.

Простий алгоритм із витисненням, круговорот (RR «Round Robin»), не використовує інформації про пріоритети. Перший процес із черги готових процесів одержує квант процесорного часу, а потім відправляється знову в кінець черги.

Комбінований варіант – круговорот (витиснення) із пріоритетами. Пріоритетні процеси можуть не тільки менше очікувати процесор у черзі готових процесів, але й довше його займати (тобто, використовувати більші по величині кванти часу).

Типовий порядок виконання й рекомендації

У наявний проект Delphi необхідно включити новий модуль UScheduler планувальника процесів, у ньому описати інтерфейс класу TScheduler і реалізувати оголошені методи.

Завершивши опис класу, необхідно доповнити головну форму компонентом, що наочно демонструє поточний розподіл пам'яті, і зв'язати з ним функціонування створеного класу TMemory.

При виконанні даної роботи можуть придадуться додаткові джерела інформації: про планування процесів докладніше див. в [1, с. 51-66], [2, с. 50-71], [4, с. 96-123].

Приклад

Приклад тексту модуля планувальника процесів:

unit UScheduler; // планувальник розподілу завдань на СР

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics,

Controls, Forms, Dialogs, StdCtrls, UQueue, UResource, UProcess;

type

Tscheduler = class

cpu: Tresource; // один з ресурсів – cpu

q: TQueueCPU; // черга до СР

r1: Tresource; // ресурс R1 (зовнішньому ресурсу)

r1q: TQueueCPU; // черга до R1

constructor create;

procedure newtakt; //перехід на новий такт

end;

implementation

constructor Tscheduler.create;

begin

cpu := Tresource.create('CPU'); // при створенні планувальника

q := TQueueCPU.create; // створюємо всі ресурси - CPU, R1 і черги

r1 := TResource.create('R1');

r1q := TQueueCPU.create;

end;

procedure Tscheduler.newtakt;

var temp: TProcess;

reason: outto;

begin

if (cpu.getStatus=rBusy) then

begin

// перевірка чи завершився процес на процесорі

// і куди він піде далі..

reason := cpu.curProc.finished;

case reason of

terminated:

begin

cpu.status := rFree; //..на завершення (залишає систему)

// в memo - ім'я процесу

form1.Memo10.lines.add(cpu.curProc.name);

cpu.curProc.destroy; // процес знищуємо

end;

toR1:

begin

cpu.status := rFree; // ..піде на ресурс1

r1q.qAdd(cpu.curProc); // додаємо в чергу до ресурсу1

end;

// не завершився - збільшуємо час його роботи на процесорі на 1

none:

cpu.curProc.incCPUTime;

end;

end;

if (cpu.getStatus=rFree) and not q.qEmpty then

//якщо CPU звільнився...

begin // якщо не порожня черга..

// витягаємо черговий процес із черги до СР по методу FCFS

q.qDel(temp);

cpu.loadProcess(temp); // завантажуємо його на процесор

cpu.status := rBusy; // стан процесора стає "зайнятий"

end ;

// для R1 всі дії аналогічні діям процесів на СР

if r1.getStatus=rBusy then

begin

reason := r1.curProc.finished;

case reason of

tocpu: begin

q.qAdd(r1.curProc);

r1.status := rFree;

end;

toR1: begin

1.status := rFree;

q.qAdd(r1.curProc);

end;

none:

r1.curProc.incCPUTime;

end;

end;

if (r1.getStatus=rFree) and not r1q.qEmpty then

begin

r1q.qDel(temp);

r1.loadProcess(temp);

r1.status := rBusy;

temp.status := runr;

end;

end;

end.

Лабораторна робота №7.

Тема: Моделювання основної пам'яті.

Ціль

Систематизувати знання про планування пам'яті в ОС. Відробити методику моделювання планувальника пам'яті засобами Delphi.

Загальне завдання

Доповнити проект попередньої лабораторної роботи модулем UMemory з описом класу планувальника пам'яті. Інтегрувати поводження класу планувальника пам'яті із загальним поводженням системи.

Вимоги до проекту

Проект повинен містити додатковий модуль UMemory з описом класу планувальника пам'яті TMemory. Пам'ять повинна бути представлена або у вигляді масиву, або, що більш прийнятно, у вигляді списку вільних областей.

Короткі теоретичні відомості

Пам'ять є найважливішим ресурсом, що вимагає ретельного керування з боку мультипрограмної операційної системи. Розподілу підлягає вся оперативна пам'ять, не зайнята операційною системою. Звичайно ОС розташовується в самих молодших адресах, однак може займати й самі старші адреси. Функціями ОС по керуванню пам'яттю є:

• відстеження вільної й зайнятої пам'яті,

• виділення пам'яті процесам і звільнення пам'яті при завершенні процесів, витиснення процесів з оперативної пам'яті на диск, коли розміри основної пам'яті не достатні для розміщення в ній всіх процесів, і повернення їх в оперативну пам'ять, коли в ній звільняється місце,

• настроювання адрес програми на конкретну область фізичної пам'яті.

Методи розміщення процесів в основній пам'яті стосовно розташування ділянок пам'яті, виділених для процесу, ділять на два класи:

• методи суміжного розміщення;

• методи несуміжного розміщення.

Суміжне розміщення є найпростішим і припускає, що в пам'яті, починаючи з деякої початкової адреси, виділяється одна безперервна ділянка адресного простору.

При несуміжному розміщенні програма розбивається на кілька частин, які розташовуються в різних, не обов'язково суміжних ділянках адресного простору.

Розглянемо спочатку деякі методи суміжного розміщення.

Розподіл пам'яті фіксованими розділами

Найпростішим способом керування оперативною пам'яттю є поділ її на кілька розділів фіксованої величини. Це може бути виконане вручну оператором під час старту системи або під час її генерації. Чергове завдання, що надійшло на виконання, міститься або в загальну чергу, або в чергу до деякого розділу.

Підсистема керування пам'яттю в цьому випадку виконує наступні завдання:

• порівнюючи розмір програми, що надійшла на виконання, і вільних розділів, вибирає підходящий розділ,

• здійснює завантаження програми й настроювання адрес.

При очевидній перевазі - простоті реалізації - даний метод має істотний недолік - твердість. Тому що в кожному розділі може виконуватися тільки одна програма, то рівень мультипрограмування заздалегідь обмежений числом розділів незалежно від того, який розмір мають програми. Навіть якщо програма має невеликий обсяг, вона буде займати весь розділ, що приводить до неефективного використання пам'яті. З іншого боку, навіть якщо обсяг оперативної пам'яті машини дозволяє виконати деяку програму, розбивку пам'яті на розділи не дозволяє зробити цього.

Розподіл пам'яті розділами змінної величини

У цьому випадку пам'ять машини не ділиться заздалегідь на розділи. Спочатку вся пам'ять вільна. Кожній знову вступник завданню виділяється необхідна їй пам'ять. Якщо достатній обсяг пам'яті відсутній, то завдання не приймається на виконання й коштують у черзі. Після завершення завдання пам'ять звільняється, і на це місце може бути завантажене інше завдання. Таким чином, у довільний момент часу оперативна пам'ять являє собою випадкову послідовність зайнятих і вільних ділянок (розділів) довільного розміру.

Завданнями операційної системи при реалізації даного методу керування пам'яттю є:

• ведення таблиць вільних і зайнятих областей, у яких вказуються початкові адреси й розміри ділянок пам'яті,

• при надходженні нового завдання - аналіз запиту, перегляд таблиці вільних областей і вибір роздягнула, розмір якого достатній для розміщення завдання, що надійшло,

• завантаження завдання у виділений їй розділ і коректування таблиць вільних і зайнятих областей,

• після завершення завдання коректування таблиць вільних і зайнятих областей.

Вибір завдання може здійснюватися за різними правилами, таким, наприклад, як "перший розділ, що попасся, достатнього розміру", або "розділ, що має найменший достатній розмір", або "розділ, що має найбільший достатній розмір". Всі ці правила мають свої переваги й недоліки.

У порівнянні з методом розподілу пам'яті фіксованими розділами даний метод має набагато більшу гнучкість, але йому властивий дуже серйозний недолік – фрагментація пам'яті. Фрагментація - це наявність великої кількості несуміжних ділянок вільної пам'яті маленького розміру (фрагментів). Розмір фрагментів настільки малий, що жодна зі знову вступників програм не може поміститися в жодному з ділянок, хоча сумарний обсяг фрагментів може скласти значну величину, що набагато перевищує необхідний обсяг пам'яті.

До методів несуміжного розміщення ставляться сегментна, сторінкова й сегментно-сторінкова організація пам'яті.

Типовий порядок виконання й рекомендації

У наявний проект Delphi необхідно включити новий модуль UMemory планувальника процесів, потім додати в нього опис інтерфейсу класу TMemory і реалізувати оголошені методи.

Завершивши опис класу, необхідно доповнити головну форму компонентом, що наочно демонструє поточний розподіл пам'яті, і зв'язати з ним функціонування створеного класу TMemory.

При виконанні даної роботи можуть придадуться додаткові джерела інформації: про планування пам'яті докладніше див. в [1, с. 67-87], [2, с. 72-99], [4, с. 162-198], [5, с. 217-298].

Приклад

Нижче приводиться приклад модуля найпростішого планувальника пам'яті.

unit UMemory;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ExtCtrls, StdCtrls, UTimer, Process;

type

TMemory = class

Razmer: integer; // поточний розмір (максимум 128 осередків)

stat:(busy, fre); // поточний статус

constructor Create;

procedure Add(p: TProcess);

procedure Get(p: TProcess);

procedure Clean;

end;

implementation

constructor TMemory.Create;

begin

Razmer:=0;

stat:=fre;

end;

procedure TMemory.Add(p:TProcess);

var

TekRazm: integer;

begin

TekRazm := 128 - Razmer;

if p.NeeDMem<=TekRazm then

Razmer := Razmer + p.NeeDMem

else

begin

stat := busy;

ShowMessage('У вас недостатньо пам'яті на цей процес');

exit;

end;

end;

procedure TMemory.Get(p:TProcess);

begin

Razmer := Razmer - p.NeeDMem;

stat := fre;

end;

procedure TMemory.Clean;

begin

Razmer := 0;

stat := fre;

end;

end.

Висновок

Завершуючи цикл лабораторних робіт, слід зазначити, що розроблений у результаті їхнього виконання комплексний проект дозволяє студентам не тільки, так сказати, «зсередини» подивитися на структуру типовий ОС, але й випробувати її поводження при різних зовнішніх умовах.

Даний цикл лабораторних робіт дозволяє студентам впритул підійти до виконання наступної великої курсової роботи з курсу СПЗ. Оскільки основи методики моделювання ОС у курсовій роботі ті ж, що й у розглянутих лабораторних роботах, студенти можуть використовувати проект останньої лабораторної роботи як база для розробки проекту курсової роботи.

Список літератури ,що рекомендується

Крім вхідних в інформаційний пакет дисципліни матеріалів (конспект лекцій, методичні вказівки по виконанню курсової роботи та посібник до самостійної роботи.) рекомендуються до використання нижченаведені літературні джерела.

Література по спо

1. Гордєєв А. В. Молчанов А. Ю. Системне програмне забезпечення (підручник для вузів).- Спб.: Питер, 2003.- 736 с.

2. Гордєєв А. В. Операційні системи, 2-е изд.- Спб.: Питер, 2004.- 736 с.

3. Коропів В. Е., Ковзанів К. А. Введення в операційні системи / Під ред. В. П. Іванникова.- М., 2002.

4. Олифер В. Г., Олифер Н. А. Мережні операційні системи.- Спб.: Питер, 2002.- 544 с.

5. Таненбаум Э. С. Сучасні операційні системи, 2-е изд.- Спб.: Питер, 2002.- 1040 с.

Література по Delphi

6. Бакнелл Дж. Фундаментальні алгоритми й структури даних в Delphi.- Спб.: Диасофтюп, 2003.

7. Боровский А. Н. Програмування в Delphi 2005.- Спб.: Бхв-Петербург, 2005.- 448 с.

8. Гофман В. Э., Хомоненко А. Д. Delphi 6.- Спб.: БХВ, 2001.- 1146 с.

9. Кэнту М. Delphi 7: Для професіоналів.- Спб.: Питер, 2004.- 1101 с.

10. Стивенс Р. Delphi. Готові алгоритми, 2-е изд.- М.: ДМК Пресс, 2004.- 384 с.

11. Калверт Ч. Стильовий стандарт оформлення коду в Delphi.- www.citforum.ru.

Додаток

Приклад оформлення звіту по лабораторній роботі

Т итульний аркуш:

МІНІСТЕРСТВО УТВОРЕННЯ Й НАУКИ УКРАЇНИ

ОДЕСЬКА ДЕРЖАВНА АКАДЕМІЯ ХОЛОДУ

ФАКУЛЬТЕТ ИНФОРМАЦИОНЫХ ТЕХНОЛОГІЙ

Протокол

лабораторної роботи № 1

по дисципліні «Системне програмне забезпечення»

Тема: «Моделювання системного таймера»

Виконала:

студентка гр. 356

Іванова Н. Ю.

Варіант - 12

Прийняв:

Неновий А. Л.

Одеса 2007

Наступні аркуші:

Загальне завдання на лабораторну роботу: Розробити засобами Delphi модель системного таймера відповідно до вимог до проекту.

Індивідуальне завдання на лабораторну роботу: Доповнити клас TMyTimer можливістю встановити «будильник» і викликати певну користувачем функцію при його спрацьовуванні.

Рішення

Вихідний текст модуля головної форми:

// Текст головного модуля

unit UMain;

interface

uses

UTimer, Windows, Messages, SysUtils, Variants, Classes,

Graphics, Controls, Forms, Dialogs, StdCtrls,

ExtCtrls;

type

TFrmMain = class(TForm) // інтерфейс класу форми

BtnIncTick: TButton;

LblTick: TLabel;

SystemTimer: TTimer;

BtnAutoInc: TButton;

Edit1: TEdit;

Label2: TLabel;

procedure BtnIncTickClick(Sender: TObject);

procedure FormActivate(Sender: TObject);

procedure BtnAutoIncClick(Sender: TObject);

procedure SystemTimerTimer(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

FrmMain: TFrmMain;

MyTimer1: TMyTimer;

implementation

{$R *.dfm}

procedure TFrmMain.FormActivate(Sender: TObject);

begin

MyTimer1 := TMyTimer.Create;

LblTick.Caption := IntToStr(MyTimer1.Time);

end;

procedure TFrmMain.BtnIncTickClick(Sender: TObject);

begin

MyTimer1.IncTime;

MyTimer1.ViewTime(LblTick);

// Label1.Caption := IntToStr(MyTimer1.Time);

end;

procedure TFrmMain.BtnAutoIncClick(Sender: TObject);

begin

SystemTimer.Enabled := True;

end;

procedure TFrmMain.SystemTimerTimer(Sender: TObject);

begin

MyTimer1.IncTime;

MyTimer1.ViewTime(LblTick);

end;

end.

Вихідний текст модуля таймера:

// Текст модуля UTimer

unit UTimer;

interface

uses SysUtils, StdCtrls;

type

TMyTimer = class(TObject)

Time: Integer;

function GetTime: Integer;

procedure IncTime;

procedure ViewTime(l:Tlabel);

end;

implementation

function TMyTimer.GetTime;

begin

Result := Time;

end;

procedure TMyTimer.IncTime;

begin

Inc(Time);

end;

procedure TMyTimer.ViewTime;

begin

L.Caption := InttoStr(Time)

end;

end.

Ф орма додатка:

Висновки.

У результаті виконання лабораторної роботи отриманий многомодульный проект Delphi, що включає модель системного таймера. Робота виконана відповідно до індивідуального завдання. Дотримано вимоги до проекту, принципи объектно-ориентированного проектування. Вихідний текст програми оформлений у відповідності зі стильовим стандартом оформлення коду Delphi. У ході роботи були поглиблені знання про системний таймер, його ролі в операційній системі. Створений проект може бути використаний як основу розробки проектів наступних лабораторних робіт.

Ненов Олексій Леонідович

Симоненко Олена Олександрівна

Колумба Ірина Вікторовна

СИСТЕМНЕ ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ

Підписано до друку ХХ.ХХ.2008 р. Формат 6084 1/16.

Усл. печ. аркуш. х,х. Тираж х экз.

Надруковано видавничий центром ОГАХ.

65082, Одеса, вул. Дворянська, 1/3

55