Відкрити головне меню

Алгоритми реального часу

Алгоритми реального часу - алгоритми, що працюють в реальному часі, основна мета яких є обробляти дані по мірі їх надходження незалежно від їх обсягу: таким чином, вони повинні відповідати вимогам швидкості дії і ефективності. Вбудовані алгоритми повинні давати можливість застосовувати їх в пристроях невеликого розміру і з обмеженим обсягом пам'яті. Отже, вони повинні бути надзвичайно ефективними і використовувати наявне обладнання з максимальною вигодою[1].Для цього необхідно проводити роботу на декількох рівнях:

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

Основною задачею в побудові алгоритмів реального часу є "Задача кешування".

Задача кешування (Paging Problem).Редагувати

Є два види пам'яті - дискова, більша за об'ємом, але повільна, і кеш, швидка, але дуже мала. Вся пам'ять розбита на блоки. Нехай в кеш-пам'яті k блоків, а на диску, відповідно, набагато більше. До нас поступають запити на ті чи інші блоки, і ми повинні відразу ж їх обробити. Є два варіанти: або цей блок вже є в кеші, або його там немає. Якщо він в кеші є, то в цьому випадку ми майже не витрачаємо час. I тоді час роботи алгоритму можна вимірювати кількістю звернень до вінчестера. Алгоритми відрізняються один від одного реакцією на запити відсутніх в кеші блоків. Зрозуміло, що ми повинні блок, на який йде запит довантажити в кеш, не зрозуміло тільки, який з уже присутніх там блоків ми повинні для цього вивантажити. Звичайно, хотілося б вивантажити "непотрібний" блок, але оскільки ми обробляємо запити в реальному часі, ми не знаємо, який блок нам буде потрібний в подальшому. Постає й інше питання: як порівняти, який алгоритм найкращий [2].

Нехай   - алгоритм, а   - послідовність запитів. Час обробки послідовності запитів алгоритмів   - це кількість звернень до диску. Нехай   - якийсь оптимальний алгоритм. Тоді алгоритм   називається  -оптимальним (c-competitive), якщо для будь-якого  :      . Де,   - константа відносно  , але вона може залежати від k інших параметрів. Але це виконується - для детермінованих алгоритмів, для ймовірнісних, розглядається не час, а її математичне очікування. Будемо розглядати випадок, коли   - ймовірнісний online алгоритм, а   - детермінований offline алгоритм ("oblivious adversary"), тобто він заздалегідь всю знає послідовність запитів  .

Алгоритм Marker.Редагувати

Елементи кешу позначаються 0 або 1. Час роботи поділяється на періоди. На початку кожного періоду всі елементи кешу позначені 0. Приходить запит. Якщо це запит на блок, який вже є в кеші, то він позначається 1. Якщо запитують елемент, якого немає в кеші, то ми випадковим чином вибираємо з непомічених (тобто помічених 0) блок, куди ми будемо довантажувати необхідний. Довантаживши, ми помічаємо його 1. Рано чи пізно у нас не залишиться блоків, помічених 0. У цьому стані ми можемо працювати, поки у нас запитують блоки, що знаходяться в кеші. Як тільки надійде запит на елемент, що не міститься в кеші, ми обнулив всі позначки і почнемо новий період.

Алгоритм Work Function Algorithm.Редагувати

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

Задача про офіціантів (k-server problem)Редагувати

Узагальнимо задачу кешування. Нехай у нас є деякий метричний простір з метрикою  , точки якого ми будемо розглядати як столики, і   офіціантів, тобто деяка підмножина   точок цього простору. Час від часу зі столиків надходять замовлення. Формально, замовлення — це координати столика. Замовлення потрібно обслуговувати, тобто треба вибрати одного з офіціантів і перемістити його в дану точку простору. Довжиною такого переміщення буде відстань між вихідною та кінцевою його точками. Кожен офіціант в кожен момент часу знаходиться біля якогось столика, і стан (конфігурація) системи описується множиною координат столиків, біля яких в даний момент знаходяться офіціанти. Тобто стан   — це мультимножина (множина з кратними елементами), яка складається з   точок простору. Назавжди зафіксуємо початковий стан   нашої системи. Нехай   =   — послідовність замовлень. Тоді робоча функція  , що зіставляє стану  , найменшу відстань обслуговування   з початкового стану  , в стан  . (Відстань обслуговування — це сума відстаней, пройдених всіма офіціантами, причому найменший шлях визначається за допомогою оптимального offline алгоритму, якому відоме  ).[2]

ПриміткиРедагувати