2. Характеристики вихідних потоків інформації
Стосовно системи передачі даних СКС є джерелом інформації й визначає момент видачі повідомлень.
Можливі три схеми визначення моментів видачі повідомлень.
У першій схемі повідомлення формується за даними, отриманими результаті обробки вхідної інформації від джерел тільки за умови звільнення системи передачі даних (СПД) від переданого раніше повідомлення. При цьому СПД очікує на протязі часу, необхідного для обробки даних і формування вихідного повідомлення, що знижує реальну пропускну здатність СПД.
По другій схемі є накопичувач на одне повідомлення, крім того, що видається в цей момент. Цей накопичувач повинен бути заповнений підготовленим повідомленням у довільний момент часу в межах інтервалу часу передачі попереднього повідомлення.
Повна асинхронність досягається в третій схемі. У цій схемі повідомлення для СПД формується в процесі обробки вхідної інформації незалежно від моментів видачі повідомлень у СПД. Підготовлені повідомлення зберігаються в буферній пам'яті й видаються в міру звільнення СПД. Також схема дозволяє в ряді випадків, особливо при значному часі підготовки повідомлень, найбільш повно використовувати пропускну здатність СПД. При цьому, якщо час обробки кожного повідомлення багато менше інтервалів між повідомленнями, то СКС можна розглядати як джерело інформації з характеристиками потоку, близькими до потоку повідомлень, що надходять у СКС від зовнішніх об'єктів.
Однією з найбільш правдоподібних гіпотез у не детермінованих випадках формування вихідних повідомлень є гіпотеза про ерланговський розподіл моментів надходження повідомлень у буферну пам'ять для наступної видачі споживачам.
У ряді випадків можна запустити апроксимацію процесу видачі повідомлень у буферну пам'ять пуассоновським розподілом.
Час передачі одного повідомлення з СКС найчастіше характеризують як постійний, тому що обсяги переданих повідомлень зручно робити фіксованими. Однак зустрічаються системи зі змінним обсягом повідомлень, а відповідно, і з випадковим інформаційним потоком.
3. Диспетчерські програми операційної системи
Найбільш важливу роль у СКС у загальному випадку грає програма-диспетчер операційної системи, що задовольняє заявки на включення інших програм ОС, а також функціональних алгоритмів і включає на виконання відповідні програми.
Найпоширенішими диспетчерами обслуговування заявок в алгоритмах диспетчеризації є:
• обслуговування заявок у порядку надходження;
• пріоритетне обслуговування без переривання обчислень (відносні пріоритети);
• пріоритетне обслуговування з перериванням обчислень (абсолютні пріоритети).
Перераховані дисципліни можуть також мати деякі різновиди, що відрізняються режимом обслуговування заявок кожного типу:
• одиночне обслуговування (обслуговується тільки одна заявка даного типу);
• обслуговування з обмеженням по часу або по числу заявок, що обслуговуються послідовно, даного типу;
• обслуговування з повною ліквідацією черги заявок даного типу.
Крім того, пріоритет програм може бути як фіксованим, так і динамічним (тобто, що змінюється в процесі роботи залежно від ситуації в обчислювальному процесі).
Які ж найпоширеніші способи організації програми-диспетчера.
Нагадаю, що стратегія планування визначає, які процеси ми плануємо до виконання для того, щоб досягти поставленої мети.
Відомо досить багато стратегій визначення процесу, якому треба віддати процесор. Найбільш поширеними є такі стратегії:
по можливості завершити процеси у тому ж порядку, у якому вони були розпочаті;
віддати перевагу більш коротким за часом виконання процесам;
надати усім користувачам (тобто процесам) однакові послуги щодо часу очікування у відповідних чергах;
Усі дисципліни диспетчеризації, незважаючи на їх велику різноманітність, можна поділити на 2 великі класи: безпріоритетні та пріоритетні.
При безпріоритетному обслуговуванні вибір процесу на виконання визначається у деякому наперед встановленому порядку (скажімо визначеному планувальником) без урахування їх значимості та часових обмежень.
При реалізації пріоритетних дисциплін окремим процесам надається переважне право на використання.
Перелік та класифікацію дисциплін обслуговування можна показати на малюнку:
Про пріоритети треба запам’ятати таке:
пріоритет процесу може бути постійним;
пріоритет процесу може бути змінним при його виконанні.
Слід завжди пам’ятати, що використання динамічних пріоритетів потребує додаткових витрат на обчислення пріоритетів у конкретний час, тому у більшості випадків реального часу використовуються методи диспетчеризації на основі фіксованих пріоритетів.
Розглянемо деякі найбільш типові дисципліни диспетчеризації.
Найпростішою є дисципліна FCFS(first come – first served), тобто обслуговування в порядку черги. Ті процеси, що були заблоковані у процесі виконання (скажімо чекають завершення вводу-виводу) стають у чергу готовності перед тими процесами, які ще не починали виконуватись. Тобто створюється дві черги: одна з нових процесів, друга – з процесів, що вже виконувались, але перейшли в режим очікування. Такий підхід дозволяє реалізувати тезу про завершення процесів у порядку їх виникнення. Ця дисципліна не потребує втручання у хід виконання процесів, перерозподілу процесорного часу не відбувається.
Графічно цю дисципліну можна показати на малюнку:
Достоїнствами цієї дисципліни є простота реалізації та мала втрата системних ресурсів на формування черги процесів.
Однак, недолік полягає в тому, що при збільшенні завантаження обчислювальної системи зростає середній час очікування обслуговування, причому невеликі за часом виконання процеси мають очікувати стільки, як і великі завдання.
Цей недолік нівелюють дисципліни SJN та SRT.
Дисципліна SJN (shortest job next) означає: слідуючим буде виконуватись найкоротше завдання. Ясно, що для цього диспетчер має порівнювати заявлений на виконання час та час фактичного виконання, та у випадку перевищення по даному параметру процес має бути поставлений у кінець черги, або може використовуватись інша система штрафів.
Дисципліна SJNвизначає, що є тільки одна черга завдань, готових для виконання. Завдання, які були тимчасово заблоковані, знову стають у кінець черги з новими процесами.
Це теж призводить до того, що процеси, яким потрібно мало часу для виконання, в решті-решт теж вимушені очікувати процесор поряд з довгими процесами.
Для викорінення цього недоліку була запропонована дисципліна SRT (shortest remaining time), слідуюче завдання потребує для завершення найменше часу.
Дисципліна обслуговування RRпередбачає, що кожний процес отримує процесорний час частками (квантами). Після закінчення кванту процес знімається з процесора. Процесор передається іншому процесу. Процес, що був знятий з виконання, стає у чергу процесів, готових до виконання. Ця дисципліна проілюстрована на малюнку:
Її ще називають карусельною дисципліною диспетчеризації (round roling). Для оптимальної оботи системи необхідно вибрати закон, за яким кванти часу надаються процесам.
Величина кванту визначається як компроміс між бажаним часом реакції системи на запити користувачів та накладеними витратами на часту заміну контексту процесів.
Нагадаю, що при невитісняючому плануванні диспетчеризація виконується без перерозподілу часу процесора. Дисципліни FCFS, SJN, SRT відносяться до невитісняючих.
Для порівняння різних алгоритмів диспетчеризації використовуються слідуючі критерії:
завантаженість процесора. Вона змінюється від 2-3% у персональному комп’ютері до 90-100% для сильно завантажених серверів;
пропускна здатність. Вона вимірюється числом процесів, які можуть виконуватись в одиницю часу;
час обороту (turnaroundtime).Для деяких процесів важливим критерієм є повний час виконання, тобто інтервал від моменту появи процесу у черзі до моменту його завершення;
час очікування. Під цим розуміють сумарний час знаходження процесу у черзі готових процесів;
час відгуку (responsetime). Цей критерій важливий для інтерактивних програм. Під ним вважається час відгуку, або час, який проходить від моменту постановки процесу у чергу до моменту першого звернення до терміналу.
Треба відмітити, що правильне визначення планування процесів сильно впливає на продуктивність усієї системи.
Головними причинами, що призводять до зменшення продуктивності, є:
накладні витрати на переключення процесора (сюди відносять переключення контекстів, переміщення сторінок віртуальної пам’яті, зміну даних у КЕШ і т.п.)
переключення на інший процес, якщо попередній виконує критичну секцію. У цьому випадку втрати найбільші.