Операційні системи

 

 

Мікропроцесори

 

Після того, як з’явилась система I386, в архітектурі Були закладені основи роботи в віртуальній пам’яті.

 

 

Критерії ефективності:

1.      максимально завантажити обладнання обчислювального комплексу.

 

 

В пакет включаються:

–  вимоги до ресурсів;

–  програма;

–  дані.
Пакети накопичуються в ОС і вона, використовуючи критерій ефективності 1, виконує обробку пакету.

2. Діалоговий режим  - надання послуг користувачам.
   
   

 

 

Тривіальна модель виконання задачі

 

Нехай є множина комірок пам’яті різних типів. Комірка пам’яті певного типу приймає діапазон значень. Як стан програми будемо мати елемент:
 [<C1, M1>, <C2, M2>, … ] – простір виконання задачі,  де Ci – ім’я комірки, Mi – поточне значення певного типу.

Якщо є дві задачі, адресний простір яких перетинається, то це взаємодія двох задач через пам’ять.

f: простір  простір – функція що і є наша програма.
В технологіях ОС для опису ресурсів використовуються дескриптори (таблиці). З

довільною задачею, що функціонує в середовищі ОС, пов’язується дескриптор задачі. Формат дескриптора залежить від типу ОС.

Дескриптор неявно (за рахунок посилок) описує всі ресурси, що виділені в задачі.
Елементи дескриптора задач:

 

Стан задачі:

1)      Активна

2)      готова до виконання

3)      затримана

 

„Кругообіг” задачі  ( по відношенню до CPU )

 

Пояснення:

1.      Активна задача переходить в чергу затриманих в зв’язку з виконанням операції вводу/виводу.

2.      По завершенню виконання операції вводу/виводу задача переходить в чергу готових до виконання.

3.      У момент, коли виконується подія  (1), з черги готових до виконання процесору призначається наступна задача

4.      У задачі примусово відбирають процесор. Наприклад, по закінчені кванту часу.

 

Задачі та під задачі

 

У випадку,  коли адресний простір декількох задач співпадає, можна вести мову про дерево задач

 .

A- головна задача, C,D,E,F – підзадачі задачі A.

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

На рівні ОС існують методи, які дають:

–    метод створити задачу

–        метод знищити задачу

 

Приклад

Дві задачі функціонують в просторі, простори перетинаються.

 

Яким буде значення комірки після деякого часу t?

 

 

Правила роботи з критичними ресурсами:

1.      Якщо декілька задач спробують одночасно модифікувати критичний ресурс, то допускається лише одна.

2.      В довільний момент часу в критичному сегменті по відношенню до даного ресурсу, повинно знаходитись не більш однієї задачі.

3.      Нескінчений час очікування виконання критичного сегменту блокується.

Після виконання 2х критичних сегментів .

 

Програмування критичних сегментів

 

Розглянемо програму

void f1(){…}
void f2(){…}

 

 

main()                //f1 та f2 виконуються одночасно.
{parbegin
f1();f2();

parend;}

 

int count=0;   //критичний ресурс
int iter=1        //черга першої задачі

void f1()

{while(iter==2)…;

//критичний сегмент

count++;

iter=2;              //тепер черга другої задачі

}

 

void f2()

{while(iter==1)…;

//критичний сегмент

count++;

iter=1;             //тепер черга першої задачі

}

 

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

 

 

@ лекція 2 ( 21.02.03 )

Алгоритм Деккера.

(взаємодія через пам’ять)

 

Ця схема взаємодії враховує наявність двох процесорів CPU і вони мають різну швидкість.

Недоліки алгоритму:

1.      Наведений алгоритм актуальний лише для взаємодії двох задач.(Існує модифікація алгоритму Деккера для багатьох задач)

2.      Процес програмування взаємодії досить складний.

 

int C1=0, C2=0;                     // побажання

int queue = 1;                          // чия черга

 

void f1 (void) {

C1 = 1;                                // встановити побажання

while ( C2 = = 1 )

   if ( queue = = 2 )

   {C1 = 0;                           // зняти побажання

     while ( queue = = 2)  ;     // цикл

     C1 = 1;}

// критичний сегмент

. . .

// кінець критичного сегменту

С1 = 0;                                   // зняти побажання

queue = 2;      }

 

void f2 (void){

C2 = 1;                                // встановити побажання

while ( C1 = = 1 )

   if ( queue = = 1 )

   {C2 = 0;                           // зняти побажання

     while ( queue = = 1)   ;    // цикл

     C2 = 1;}

// критичний сегмент

. . .

// кінець критичного сегменту

C2 = 0;                                   // зняти побажання

queue = 1;      }

 

main ()  {  parbegin

                          f1();           // якщо f1 та  f2 працюють разом, то ця схема коректна і враховує

             f2();                взаємодію двох потоків на СРU з різними швидкостями.                      

      parend }

Схема:

 

 f1          f2

 

Апаратні засоби взаємодії.

 

                    

 int global = 0;

void  f1(void) {

int local;

while (1)                      //цикл взаємодії

{ local = 1;

    while (local)   test_and_set(local, global);

// критичний сегмент

. . .

// кінець критичного сегменту

global = 0;}

                     }

main () { parbegin

                                        

                parend   }

 

 

 

Схема:

f1          f1        f1

 

Недоліки:

1.      Потрібно знати специфіку test_and_set

2.      Якщо N потоків, то понижується ефективність обчислювальної установки.

 

P- ,V- операції Дейкстра.

 

 

 

 

 

 

 

    Ресурс: друкарський

    пристрій

           А                                          В                                     С

 

Задача “ постачальник – споживач ”.

 

 

 

 Семафор:

SEMAFOR  IN_BUF( N );

SEMAFOR  OUT_BUF( N );

DATA BUFFER[ N ];  //буферний пул

void  постачальник (void) {

 int  ind_in_buf = 0;

while (1) { P( IN_BUF );

// критичний сегмент, наповнення елементів даних

. . .

//кінець критичного сегмента

                V( OUT_BUF );

ind_in_buf  = ( ind_in_buf + 1 )  % N;   }}

void споживач (void)  {

int  ind_out_buf = 0;

while (1)  { P( OUT_BUF );

// обробка даних з буферного пула

. . .

// кінець

    V( IN_BUF );

ind_out_buf  = ( ind_out_buf + 1 ) % N;  }}

main () { parbegin

       постачальник ();

       споживая();

      parend;  }

 

Недоліки семафору Дейкстра:

1.      Оскільки семафори є даними, що належать головній задачі, їх можна несанкціоновано змінити.

2.      Реально семафорів не існує.

 

Монітори ресурсів

 

 

 

 

Умови виконання моніторe співпадають з умовами виконання критичного сегменту.

 

 

 

 

 

Для роботи з моніторами ресурсів запропоновано дві функції:

WAIT (<ім’я_черги_ресурса>)

SIGNAL (<ім’я_черги_ресурса >)

Ці операції допустимі в моніторах.

 

   Семантика WAIT: задача, котра видала WAIT призупиняється. Управління отримує ядро операційної системи, яке відповідає за планування задач для CPU.

 

Семантика SIGNAL: по цій команді з черги задач, затриманих відносно даного ресурсу одна задача переходить в чергу готових до виконання. Та задача, що видала SIGNAL продовжує працювати.

 

 

 

 

 

 

 

@ лекція 3 ( 28.02.03 )

Задача “Читачі – письменники”

 

Модельна задача в теорії керування файловою системою. Розглянемо підхід, який передбачає наявність двох черг, окремо для читачів та письменників.

Існує інша модель, коли черга для читачів та письменників одна.

Правила роботи :

-         якщо “читач в залі” маємо вільний вхід для інших читачів;

-         якщо “письменник в залі” – обидві черги блокуються;

-         письменник запрошує до зали читача після завершення своєї роботи.

 

Опишемо програмну реалізацію цієї схеми.

 

class Reader_Writer {Queue Q_Reader;

Queue Q_Writer;

 int R_count;

 bool W_count;}

Reader_Writer(){Q_Reader(NULL);Q_Writer(NULL);R_count = 0;W_count = false}

begin_Reader(){ if (W_count) wait (Q_Reader); R_count++; signal(Q_Reader);}

end_Reader(){ R_count--; if (!R_count) signal(Q_Reader); else signal(Q_Writer);}

begin_Writer(){if (R_count)!!W_count wait(Q_Writer); W_count = true;}

end_Writer(){ W_count = false; if (Q_Reader != NULL) signal(Q_Reader);

else signal(Q_Writer);}

Реалізація монітора

 

В більшості ОС монітори реалізовані через апарат програмних переривань (машинна команда INT).

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

wait – передає керування ядру ОС, яке активізує нову задачу, змінює контекст, (wait – функція ядра ), та зберігає існуючий контекст.

signal – не завжди продовження роботи задачі, що викликала цю функцію, бо враховується приорітет тієї задачі, що переноситься до черги готових до виконання.

 

Семафори для принтера та модема – двійкові.

Умови виникнення тупиків :

-         динамічний захват ресурсів (що є властивістю ОС);

-         наявність циклічних ланцюгів очікування.

( на малюнку: Пр – принтер, Мо – модель ).

 

Алгоритм банкіра. (спроба подолання проблеми тупиків)

 

 

Нехай в системі наявні  одиниць ресурсу А, та  - потреба -ї задачі в ресурсі А ,  - кількість одиниць ресурсу А, що надані -й задачі. Таким чином вільного ресурсу А : . Перспективні потреби -ї задачі- в майбутньому. Припускається, що  та . За таких умов маємо наступну умову стабільності стану : , якщо ж умова порушується, то стан є нестійким. Якщо умова (1) в часі істина, то тупик не можливий, інакше існує потенційна можливість виникнення тупика.

 

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

 

Способи боротьби з тупиками

-         прогнозування;

-         наявність моніторів контролю над завантаженням ресурсів;

-         дії оператора (адміністратора)

а) примусове динамічне керування ресурсами;

б) перезавантаження ОС.

 

@лекція 4 ( 7.03.03 )

 

Ресурси:

Пам’ять ЕОМ – менеджер( супервізор ) пам’яті.

Файли – логічна система вводу-виводу.

Процесор – диспетчер( супервізор ) задач.

 

 

 

Приклад    

В MS-DOS:

                                           300k                                                    20k              200k

         ядро ОС                                                                           драйвер                                                          BIOS

                                                                                              клавіатури

Завантажити >350k не можемо.

Тоді спроектуємо модуль так:

=110k

ОС з режимом оверлей має дві взаємопов’язані компоненти:

1)      редактор міжмодульних зв’язків, який підтримує можливість побудови оверлеїв

2)      функція виборки( завантаження ) оверлейного модуля.

 

 

Приклад

Таким чином, якщо ми маємо *.ехе простої структури з режимом оверлей(1)

  таблиця управління оверлей-модулем

 

Дії компілятора при компіляції виклику функції:

   код               адрес функції

   операції

 

Структура *.obj -– модуля

 

1. коментар: – хто виконав компіляцію

                              – дані для утиліти MAKE ( імена *.h – файлів та дати )

2. таблиця зовнішніх імен модуля:

–        ім’я функції

–        її глобальні дані

3. Код функції
4.  Таблиця модифікації коду функції( в ній указане зміщення комірок, що потрібно модифікувати ).

 

                Редактор міжмодульних зв’язків( LINKER )

               cos.obj – головний модуль

Головний модуль отримує перше управління. В головному модулі знаходяться пролог та епілог Сі-програми.

 

Приклад

Якщо є глобальні змінні, то потрібно виконати конструктор( в пролозі ) та деструктор( в епілозі ).

            Лінкер працює в два етапи( два перегляди ):

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

Виконується операція першого перегляду.

Ім.’я функції	Довжина( об’єм ) коду функції	Зміщення
cos.obj MAIN.obj STRLEN.obj	10k 8k 1k	0 10k 18k
…	…	…

Переглянувши, дізнаємось об’єм ехе-файла :    19k

Другий перегляд( компоновка ехе-файла ): лінкер переглядає таблицю, отриману на першому етапі, зчитує obj-файли та об’єднує в єдиний файл. Будує таблицю настройки

ехе-файла. При об’єднанні obj- в ехе-файл в місцях виклику  функції виконується модифікація коду.

             0               виклик strlen                                                        strlen                                      

MAIN 

–під час компіляції

– зв’язуємось з strlen

 

В результуючий ехе-файл заноситься вся інформація щодо модифікованих комірок(

розділ 4 obj-модуля ). Тобто ехе-файл має вигляд:

0     cos                 main                    strlen                                     таблиця модифікації ехе-файла

                              19k                                                      ( дані з розділу 4 *.obj -файлів )

 

 

Завантаження ехе-файла в ОП

 

ОС завантажує ехе-файл в ОП та виконує модифікації комірок згідно списка з

розділу 4.

Значення кожної комірки = попереднє значення + абсолютний адрес завантаження модуля

в ОП.

0                      40k                                         58k

   ядро ОС                              19k 

                                                               виклик strlen:     

                                                                                   

                                                                                        

@ лекція 5 ( 14.03.03 )

Подивимось, як виконується оверлейний модуль.

       *.ехе

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

Додатково операційній системі додається таблиця управління оверлейною структурою. Програмний код, що завантажується в оперативну пам’ять модифікується таким чином, що в місцях виклику функції, що перевантажується, вставляється програмне переривання по виконанню overlay – loader’a.

При виклику функції А попадаємо в ядро ОС, яке має overlay – loader. Там дивимось, чи є в пам’яті функція А.  Якщо так, то в таблиці управління її поточним станом є 1, якщо ні – 0. Якщо ні, то дивимось її адрес і динамічно завантажкємо функцію А. Функція А виконує обробку і передає управління ОС, а ОС в свою чергу програмі.

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

Якщо функція В викликається з того ж місця, що й функція А, то супервізор ставить поточний стан для А – 0 (він враховує, що А та В перетинаються).

 

 

 

 

 

 

 

Віртуальна пам’ять.

 

Адресний простір Віртуальної пам’яті завжди більший за адресний простір оперативної пам’ті.

В моделі  віртуальної пам’яті задіяні 2 механізми:

1. механізи прямої адресації;
2. механізм пов’язаний з НЖМД.

 

Віртуальний адрес.

 

В архітектурі сучасних ЕОМ віртуальний адрес складається з двох компонент:

1. база;
2. зміщення.

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

Під час компіляції програми (функції), компілятор присвоює лічильнику баз початкове значення 0. Під час завантаження програми ЕОМ, ОС присвоює регістрам точки завантаження в ОП програм та даних. База з’являється під час завантаження, а зміщення при компіляціїї. Це дає реальний адрес.

В моделі віртуальної пам’яті реальний адрес, що формується на основі машинної команди, трактується як віртуальний адрес. Частину віртуального простору займає ядро ОС.

 Розробники архітектури запропонували декілька стратегій реалізації віртуальної пам’яті:

-         сегментна;

-         сторінкова;

-         змішана(сегментно - сторінкова).

 

 

 

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

Пам’ять: по швидкодії КЕШ 2-го рівня переважає оперативну пам’ять.

Потрібно, щоб апаратура ЕОМ код програми автоматично переписувала в КЕШ.

За рахунок цього програма виконується швидше.

КЕШ 1-го рівня – це пам’ять процесору (64К).

 

Трансляція віртуального адресу (сторінкова стратегія)

 

Об’єм віртуальної пам’яті, що виділяється для кожної задачі фіксований (і, наприклад в архітектурі Intel(P4) дорівнює 2Гб). В архітектурі ЕОМ існує об’єкт – регулярна таблиця сторінок задачі.

 

Колонка 1:  Значення:

0 – сторінка на НЖМД;

1 – сторінка в ОП.

Колонка 2: Атрибути сторінки (характеристики для ядра ОС):

                        RO – read-only;

                        RW – read-write;

                        E – execute (сторінка з програмним кодом);

                        D – data (сторінка з даними).

Колонка 3: Значення:

                        0 – пам’ять не виділена механізмом MALLOC;

                        1 –  пам’ять виділена механізмом MALLOC.

Колонка 4: Значення:

– коли сторінка на НЖМД, її адрес знаходиться в swap-файлі;

– коли сторінка знаходиться в ОП, то її адрес теж в ОП.

 

В середовищі ОС існують таблиці трансляції по кількості задач, що в даний момент знаходяться в ОП. Регістр таблиці сторінок задачі вказує на таблицю трансляції активної задачі. Таблиця трансляції завантажується в КЕШ 1-го рівня.

В момент коли змінюється активна задача, ОС перевантажує регістр таблиці сторінок задачі та завантажує в КЕШ нову таблицю. Зміна значення регістру таблиці сторінок та перевантаження таблиці трансляції виконуються однією машинною командою – заміна контексту задачі (виконується за 100-ні тактів базової частоти процесора).

Якщо в момент трансляції віртуального адресу ми попадаємо на сторінку, що знаходиться на НЖМД, то виникає апаратне переривання – відсутня сторінка в ОП.

Тут спрацьовує механізм ОС.

 

Реакція ОС на переривання ”відсутня сторінка в ОП”.

 

1. ОС завантажує сторінку в ОП на порожнє місце;
2. модифікує таблицю трансляції сторінки (адрес + колонка1);
3. передає управління задачі, що викликає переривання.

 

Як з’ясувати де знаходиться порожнє місце?

Для ідентифікації сторінки, що є зайнятою чи вільною ОС веде спеціальний вектор вільних сторінок, в якому зайняті сторінки позначаються як 1, а вільні як 0.

Якщо відсутня вільна сторінка, ОС повинна попередити про вивантаження деякої сторінки з ОП.

 

 

 

 

 

 

 

@ лекція 6 ( 21.03.03 )

 

Стратегія робочої множини сторінок

 

ОС по кожній сторінці ОП веде лічильник.

• На початку значення лічильника рівне 0
• через квант часу  ОС визначає ті сторінки, що є активними і збільшує значення лічильника для активних сторінок.
• При визначенні сторінки, яку необхідно вивантажити ОС вибирає сторінку з найменшим значенням лічильника.
• Через час , - фіксоване, ОС встановлює значення лічильника, які більше порогового значення, в порогове значення

1) серед сторінок, які знаходяться в ОП, є множина сторінок, які не можна вивантажити

2) є системні задачі, які теж не можна вивантажити

3) є прикладні задачі, які теж не можна вивантажити

 

Задачі реального часу та ядро ОС

 

• Ядро ОС апріорі зафіксоване в реальній пам’яті
• Існують системні задачі (драйвери), які вимагають фіксації в реальній ОП
• Існують прикладні задачі(real time), які теж необхідно фіксувати в реальній пам’яті

Для фіксування в реальній памяті задачі існують відповідні API

 

Алгоритми управління ресурсами CPU

 

·       

...

Управління CPU на основі апарату переривань.
Управління CPU  на основі апарату переривань є неефективним.

Наприклад  

виконання задачі, що не вимагає довгий час переривань, тому програма може тривати довгий час

 

 

·        Управління CPU на основі квантування часу
В архітектурі сучасних ЕОМ існує декілька лічильників часу (таймер, інтервальний таймер).

 

      Інтервальний таймер відліковує проміжки часу(фіксовані проміжки часу(Intel) і    

      довільний(IBM mainframe)) Інтервальний таймер видає переривання коли   

      значення  часу дорівнює „0”
     Як системні так і прикладні задачі можуть виставляти до ОС запити на інтервал

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

      вибирає найменше значення часу, що встановлено на даний момент в ОС. Цей

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

      котрої значення інтервалу таймеру = 0, активується

 

·        Управління CPU на основі пріоритету

 

1.      Черга готових до виконання задач відсортована по пріоритету. При зміні контексту, ОС повертає задачу, що відпрацювала свій квант часу (коли вона не

      затримана), в чергу готових до виконання задач з урахуванням пріоритету.

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

прикладні задачі.

 

·        Управління CPU на основі динамічного пріоритету
В момент запуску задачі, динамічні та статичні задачі мають однаковий пріоритет. В момент перепланування CPU динамічний пріоритет зростає на певне значення (на мал.: +5). Задача, в якої забрали CPU, вставляється в чергу готових до виконання з урахуванням її статичного пріоритету.

·        Управління CPU з урахуванням підзадач прикладної задачі  

Прихована комірка зшиває список навпаки
В середовищі ОС з підзадачами (потоками) пріоритет підзадачі не перевищує пріоритет основної задачі.

Наприклад

100 мсек , що надається головній задачі, розподіляється з урахуванням її підзадач.

·        Реально в середовищі ОС існує єдиний список (або черга) задач. Цей список ієрархічний( на першому рівні – головна задача ).

·        Серед елементів цього списку є TCB(Task Kontrol Block)-блоки затриманих задач.

 

 

 

@ лекція 7 ( 28.03.03 )

Підсистема вводу / виводу

 

 

 

                                                                

                                                               

 

 

 

 

 

 

Пристрій управління ( на малюнку П/У ) враховує специфіку кінцевого пристрою.

 

 

 

 

 

 

 

 

 

  Стандартизація інтерфейсу:

-         стандарт ISA : Intel

-         стандарт MCA ( мікро канальна архітектура ): IBM, Apple

 

 Контролер НЖМД :

- стандартний IDE-контролер

Алгоритм роботи  IDE-контролеру:

-   вибрати циліндр;

-   відшукати початок;

-   пропустити (n-1) сектор

-   прочитати n-й сектор

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

 

Для глобалізації дії IDE-контролера розробили SCSI-контролер.

 

SCSI-контролер :

      CPU не виконує ніякої обробки, лише подає команди.

               LUN (logic unit number): пристрій отримує дані, декодує і виконує.

Робота контролера в тому, що потрібно передати дані до „лунки” LUN.

 

 

 

 

 

 

 

Переглядаємо лунки до певного номера. Власне комп’ютеру відповідає LUN0.

 

SCSI-контролер в 5 разів швидше IDE-контролера. Але потрібно було забезпечити надійдість. Було запропоновано RAID-контролер.

 

RAID-контролер [0,1,2,3,4,5] – режими роботи

-         автоматично дублював диски

-         технологія ланцюжкового запису даних на n накопичувачах ( n>2 ) (якщо з трьох один диск вилітає, все зберігається)

 

Режим роботи RAID-контролера

Як правило, RAID – контролер будується як спеціфлізований комп’ютер (в нього має бути процессор, має досить великий об’єм ОП)

 

Компоненти підсистеми вводу/виводу

 

-         BIOS – базова система вводу/виводу, поставлена з ПЕОМ

-         фізична система вводу/виводу – базується на BIOS

-         Логічна система вводу/виводу:

1.      логічний диск / том;

2.      каталог;

3.      файл;

4.      операції вводу/виводу в межах файла.

Файл в ОС інтерпретуються як ресурси.

оpen() – регіструє файл як ресурс ОС.

 

 

 

 

 

Задача А                                                                                        

                 

 

 

 

 

 

 

 

 

В ОС типу MS-DOS максимальна кількість файлів, які можна відкрити як ресурс, фіксована і описується в файлі  confic.sys як:

                                                        file =  ...

                                                        buffer = ...  .

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

 

Виконання операції виводу на накопичувач

 

                список блоків

 

 

 

 

 

 

 

 

 

 

В момент роботи мультизадачної ОС формується множина записів для виводу на накопичувач. Кожен запис має свою адресу на накопичувачі(абсолютну чи відносну).

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

При переході з доріжки на доріжку, ОС повинна визначити “правильний” напрямок. Це пов’язано з часом. Існують стратегії переміщення головки зчитування по поверхні.

 

Стратегії переміщення головки зчитування по поверхні НЖМД:

-         переміщення   min доріжка « max доріжка ( ОС Novel )

-         переміщення по принципу мінімального відхилення від поточного стану

@лекція 8 ( 4.04.03 )

Теорія та практика розробки мовних процесорів

( транслятор та інтерпретатор )

 

 

 

 

 

Блочна структура мовного процесора (транслятора).

 

 

 

 

 

 

 

 

 

 

 

Мови програмування :

-         прагматичний аспект;  ( І )

-         семантичний аспект;    ( ІІ)

-         синтаксичний аспект.   (ІІІ)

І – визначає область адекватного використання мови програмування, а саме

     визначає на які задачі орієнтована мова програмування.

ІІ – конкретизує прагматичний аспект, а саме визначає базові типи даних та

      операції над ними, способи побудови структур даних(об’єктів) та способи

      побудови “складних” програм на основі простих.

ІІІ – визначає форму нотації семантичних понять( наприклад розробили мову

        аналогічну Pascal – Ломоносов, в якій інтерпретація: „Начало - Конец” )

 

Лексичний аналізатор.

Вхід – текст (послідовність літер), вихід – текст (послідовність лексем).

 

 

В теорії кількість лексем необмежена, але кількість класів лексем – скічченна.

Класи лексем :

-         зарезервовані слова ( int, if, double, sizeof, …);

-         ідентифікатори;

-         числові та літерні константи;

-         коди операцій (>, >>, >>=);

-         незначущі елементи ( прогалина, табуляція тощо);

-         коментарі

 

Синтаксичний аналізатор.

Вхід – текст (послідовність лексем),

Вихід(структурований) – так + синтаксична структура

                                                ні + синтаксичні помилки.

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

 

 

Семантичний аналізатор.

Вхід – синтаксична структура, вихід –семантична структура.

 

Блок оптимізації.

Вхід – семантичний терм, вихід –семантично еквівалентний даному терм.

 

 

Критерії оптимізації

– оптимізація об’єму коду

– оптимізація

 

Генератор вихідного коду.

Вхід – семантичний терм, вихід – вихідна (об’єктна) програма.