Алгоритм для обчислення власного часу процесу. Планування (обчислення) - Scheduling (computing) технічний директор центру інноваційних технологій і рішень «Інфосистеми Джет»
Вступ
Мета практикуму по організації виробництва - розширити і поглибити теоретичні знання, прищепити необхідні навички для вирішення найбільш часто зустрічаються на практиці завдань з питань організації та планування виробництва.
У практикум включені завдання з основних розділів курсу. На початку кожної теми подано короткі методичні вказівки і теоретичні відомості, типові завдання з рішеннями і завдання для самостійного рішення.
Наявність в кожній темі методичних вказівок і коротких теоретичних відомостей дозволяє використовувати даний практикум при заочній формі навчання.
розрахунок тривалості виробничого циклу
Як показник ефективності виробничого процесуслужить тривалість виробничого циклу.
Виробничий цикл- період перебування предметів праці в процесі виробництва з моменту запуску сировини і до моменту випуску готової продукції.
Виробничий цикл складається з робочого часу,протягом якого витрачається робочий працю, і часу перерв. Перерви в залежності від їхніх причин можуть бути поділені:
1) на природніабо технологічні - вони обумовлені природою продукту;
2) організаційні(Перерви між змінами).
Тривалість виробничого циклу складається з наступних складових:
Т циклу = tтих + tїсть + tтр + tк.к. + tм.о. + tм.ц.
де tтих- час технологічних операцій;
t їсть -час природних процесів (сушіння, охолодження і т.д.);
t тр -час транспортування предметів праці;
t к.к. -час контролю якості;
t М.О -час міжопераційного пролежування;
t м.ц. -час пролежування на міжцехових складах;
(tтри tк.к. можна поєднати з tМ.О).
Розрахунок тривалості виробничого циклу залежить від типу виробництва. У масовому виробництві тривалість виробничого циклу визначається часом перебування виробу на потоці, тобто
Т циклу = tв · М,
де tв- такт випуску;
М- кількість робочих місць.
під тактом випускуслід розуміти проміжок часу між випуском одного виготовленого вироби і наступного за ним вироби.
Такт випуску визначається за формулою
t в = Т еф / В,
де Т еф- ефективний фонд часу робітника за розрахунковий період (зміну, добу, рік);
В- обсяг випуску за той же період (у натуральних одиницях).
Приклад: Т см = 8 годин = 480 хв; Т пер = 30 хв; → Т еф = 480 - - 30 = 450 хв.
В = 225 шт; → tв = 450/225 = 2 хв.
В серійному виробництві, Де обробка ведеться партіями, тривалість технологічного циклу визначається не на одиницю продукції, а на всю партію. Причому в залежності від способу запуску партії у виробництво ми отримуємо різну тривалість циклу. Існує три способи руху виробів у виробництві: послідовний, паралельний та змішаний (послідовно-паралельний).
I. при послідовномупереміщенні деталей кожна наступна операція починається тільки після того, як закінчиться попередня. Тривалість циклу при послідовному русі деталей буде дорівнює:
де n - кількість деталей оброблюваної партії;
t штi- штучна норма часу на операцію;
C i- число робочих місць на i-й операції;
m- число операцій технологічного процесу.
Дана партія виробів, що складається з 5 штук. Партія пропускається послідовно через 4 операції; тривалість першої операції - 10 хв, другий - 20 хв, третьої - 10 хв, четвертої - 30 хв (рис. 1).
Малюнок 1
Тциклу = Тпісл = 5 · (10 + 20 + 10 + 30) = 350 хв.
Послідовний спосіб руху деталей має ту перевагу, що він забезпечує роботу обладнання без простоїв. Але його недолік полягає в тому, що тривалість виробничого циклу в цьому випадку найбільша. Крім того, створюються значні запаси деталей у робочих місць, що вимагає додаткових виробничих площ.
II. при паралельномурусі партії окремі деталі не затримують у робочих місць, а поштучно передають на наступну операцію негайно, не чекаючи того, коли закінчиться обробка всієї партії. Таким чином, при паралельному русі партії деталей на кожному робочому місці одночасно виробляються різні операції над різними деталями однієї і тієї ж партії.
Тривалість обробки партії при паралельному русі виробів різко скорочується:
дл .
де n n- кількість деталей в передавальної партії(Транспортної партії), тобто кількість виробів, одночасно передаються від однієї операції до іншої;
Дл.- найбільш тривалий операційний цикл.
При паралельному запуску партії виробів обробка деталей всієї партії ведеться безперервно лише на тих робочих місцях, де довгі операції слідують за короткими. У тих випадках, коли короткі операції слідують за довгими, тобто більш тривалими (в нашому прикладі - третя операція), виконання цих операцій відбувається безперервно, тобто простоює обладнання. Тут партію деталей не можна обробляти відразу, без затримок, так як цього не дозволяє попередня (довга) операція.
У нашому прикладі: n= 5, t 1 = 10; t 2 = 20; t 3 = 10; t 4 = 30; з= 1.
Тпар = 1 · (10 + 20 + 10 + 30) + (5-1) · 30 = 70 + 120 = 190 хв.
Розглянемо схему паралельного руху деталей (рис. 2):
малюнок 2
III. Щоб ліквідувати перерви в обробці окремих деталей партії на всіх операціях, застосовують паралельно-послідовнийабо змішанийспосіб запуску, при якому деталі (після їх обробки) передаються на наступну операцію поштучно, або у вигляді «транспортних» здолав (по кілька штук) з таким розрахунком, щоб виконання операцій не переривалося ні на одному робочому місці. У змішаному способі від послідовного береться безперервність обробки, а від паралельного - перехід деталі від операції до операції відразу після її обробки. При змішаному способі запуску у виробництво тривалість циклу визначається за формулою
кор .
де кор. - найбільш короткий операційний цикл (з кожної пари суміжних операцій);
m-1 – число поєднань.
Якщо наступна операція є більш тривалою, ніж попередня, або дорівнює їй за часом, то запуск на цю операцію проводиться поштучно, відразу після обробки першої деталі на попередньої операції. Якщо, навпаки, наступна операція є коротшою, ніж попередня, то при поштучної передачі тут виникають перерви. Щоб їх не допустити, необхідно накопичити транспортний заділ такого обсягу, який достатній для забезпечення роботи на наступній операції. Щоб практично знайти цю точку на графіку, необхідно передати останню деталь партії і відкласти вправо тривалість її виконання. Час обробки всіх інших деталей партії відкладається на графіку вліво. Початок обробки першої деталі показує той момент, коли транспортний заділ з попередньої операції повинен бути переданий на дану операцію.
Якщо суміжні операції є однаковими за тривалістю, то за коротку або довгу приймається лише одна з них (рис. 3).
малюнок 3
Тостан-пар = 5 · (10 + 20 + 10 + 30) - (5-1) · (10 + 10 + 10) = 350-120 = 230 хв.
Основними шляхами скорочення тривалості виробничого циклу є:
1) Зниження трудомісткості виготовлення продукції за рахунок вдосконалення технологічності продукції, що виготовляється конструкції, використання ЕОМ, впровадження передових технологічних процесів.
2) Раціональна організація трудових процесів, Пристрій і обслуговування робочих місць на основі спеціалізації і кооперування, широкої механізації і автоматизації виробництва.
3) Скорочення різних планованих і непланованих перерв на роботі на основі раціонального використання принципів наукової організаціївиробничого процесу.
4) Прискорення течії реакцій в результаті підвищення тиску, температур, переходу на безперервний процес і т.д.
5) Удосконалення процесів транспортування, складування і контролю і поєднання їх в часі з процесом обробки і збірки.
Скорочення тривалості виробничого циклу є однією з серйозних завдань організації виробництва, тому що позначається на оборотності оборотних коштів, Зниженні витрат праці, зменшенні складських приміщень, потреби в транспорті і т.д.
завдання
1 Визначити тривалість циклу обробки 50 деталей при послідовному, паралельному і послідовно-паралельному видах руху в процесі виробництва. Процес обробки деталей складається з п'яти операцій, тривалість яких відповідно складає, хв: t 1 =2; t 2 =3; t 3 =4; t 4 =1; t 5 = 3. Друга операція виконується на двох верстатах, а кожна з інших на одному. Величина передавальної партії 4 штуки.
2 Визначити тривалість циклу обробки 50 деталей при послідовному, паралельному і послідовно-паралельному видах руху в процесі виробництва. Процес обробки деталей складається з чотирьох операцій, тривалість яких відповідно складає, хв: t 1 =1; t 2 =4; t 3 =2; t 4 = 6. Четверта операція виконується на двох верстатах, а кожна з інших на одному. Величина передавальної партії - 5 штук.
3 Партія деталей в 200 штук обробляється при паралельно-послідовному русі її в процесі виробництва. Процес обробки деталей складається з шести операцій, тривалість яких відповідно складає, хв: t 1 =8; t 2 =3; t 3 =27; t 4 =6; t 5 =4; t 6 = 20. Третя операція виконується на трьох верстатах, шоста на двох, а кожна з інших операцій - на одному верстаті. Визначити, як зміниться тривалість циклу обробки партії деталей, якщо паралельно-послідовний варіант руху в виробництві замінити паралельним. Величина передавальної партії - 20 штук.
4 Партія деталей в 300 штук обробляється при паралельно-послідовному русі її в процесі виробництва. Процес обробки деталей складається з семи операцій, тривалість яких відповідно складає, хв: t 1 =4; t 2 =5; t 3 =7; t 4 =3; t 5 =4; t 6 =5; t 7 = 6. Кожна операція виконується на одному верстаті. Передавальний партія - 30 штук. В результаті поліпшення технології виробництва тривалість третьої операції скоротилася на 3 хв, сьомий - на 2 хв. Визначити, як змінюється цикл обробки партії деталей.
5 Дана партія заготовок, що складається з 5 штук. Партія пропускається через 4 операції: тривалість першої - 10 хв, другий - 20 хв, третьої - 10 хв, четвертої - 30 хв. Визначити тривалість циклу аналітичним і графічним способами при послідовному русі.
6 Дана партія заготовок, що складається з чотирьох штук. Партія пропускається через 4 операції: тривалість першої - 5 хв, другий - 10 хв, третьої - 5 хв, четвертої - 15 хв. Визначити тривалість циклу аналітичним і графічним способами при паралельному русі.
7 Дана партія заготовок, що складається з 5 штук. Партія пропускається через 4 операції: тривалість першої - 10 хв, другий - 20 хв, третьої - 10 хв, четвертої - 30 хв. Визначити тривалість циклу аналітичним і графічним способами при послідовно-паралельному русі.
8 Визначити тривалість технологічного циклу обробки партії виробів з 180 шт. при паралельному і послідовному варіантах її руху. Побудувати графіки процесу обробки. Величина передавальної партії - 30 шт. Норми часу і кількість робочих місць на операціях наступні.
Все, про що було розказано в декількох попередніх розділах, більшою мірою орієнтується на проведення подальших досліджень з проблеми свого часу процесу і в значно меншій мірі на практичні застосування. Заповнюючи цю прогалину, викладемо один із способів обчислення власного часу процесу на підставі статистичних даних про його еволюції.
Розглянемо одновимірний процес, стан якого характеризується дійсної змінної х. Припустимо, що спостереження за динамікою процесу виконуються в астрономічному часу t, так що t = t k і x = x k, k = 1, ..., п - фіксовані моменти спостереження і відповідні їм значення станів процесу. Існує безліч різноманітних математичних методів, що дозволяють побудувати такі криві, які або проходять через точки (t k, Xk), або «найкращим o6paзом» наближаються до них. Отримувані при цьому функції x = x (t) породжують, в нашій свідомості враження, що даний процес залежить від механічного руху небесних тіл і, отже, його стан виражається через астрономічний час t. З таким висновком можна було б вважатися; якщо не виникали б постійні труднощі при спробах прогнозуванні подальшого перебігу процесу. Для великого числа різноманітних процесів, які не мають прямого відношення до механічних рухів небесних тіл, одержувані за допомогою функції x = x (t) теоретичні передбачення за межами інтервалу спостереження починають значно відхилятися від подальших експериментальних даних. Причину розбіжності теорії і експерименту зазвичай намагаються пояснити невдало підібраним методом обробки, проте суть справи може бути і не в цьому.
Будь-яке нас процес протікає у Всесвіті. Він, безумовно, «відчуває» на собі вплив руху небесних тіл. Однак Це вплив може виявитися «нежестким», невизначених. Це, зокрема, може виявлятися в тому, що на певних інтервалах течії астрономічного часу стан процесу залишається незмінним. Згадаймо у зв'язку з цим наведений раніше приклад із замкнутим порожнім приміщенням, ізольованим від зовнішнього світу. Впустимо в приміщення всього лише одну живу муху. Протягом декількох днів зміни в стані системи «приміщення - муха» будуть залежати від переміщень мухи, оскільки змін в стані приміщення очікувати не доводиться. Разом з тим важко уявити, що поведінка мухи жорстко пов'язано з ходом астрономічного часу.
Зробивши такий довгий відступ, перейдемо до опису алгоритму для підрахунку власного часу процесу.
У цьому алгоритмі як натуральну заходи часу вибирається одиниця обчислення локальних максимумів. Крім того, беруться до уваги можливі ділянки стаціонарного стану процесу, на яких, як зазначалося раніше, власний час зупиняється. Оскільки про ідентичності двох станів можна говорити тільки в межах точності вимірювань, то в подальшому використовується деяке позитивне число е - припустима помилка вимірів.
Отже, вхідними даними для алгоритму є натуральне число п, позитивне число 8, масиви (tk) і (x k), k = 1, ..., п. Для зручності програмування алгоритм представлений у вигляді чотирьох послідовно виконуваних модулів.
Модуль 1,використовуючи дані п, е, tk), (xk), формує в загальному випадку нові масиви 7 = (7 + X = (X t) і цілком конкретний супутній масив Р = (?), де 1 = 1, ..., т, причому т<Сп. Основное назначение этого модуля -- выявление в массиве x k) последовательностей идентичных состояний процесса, сохранение первых элементов в таких последовательностях и удаление всех остальных и, наконец, уменьшение по определенному, правилу исходного интервала наблюдения от t до на сумму тех промежутков времени, в которых процесс протекает стационарно.
Модуль 1 включає в себе наступні процедури:
р: = 1, т: = 0, k: = 1.
В п.п. 1, 2 вводяться лічильники з конкретними початковими значеннями:
В п.п. 3, 4 відбувається збільшення значень лічильників на 1.
Перевірити умова k ^ n. Якщо воно виконано, то перейти до п. 6, в іншому випадку до п. 11.
Перевірити нерівність x k --x k = е. Якщо воно має місце, то перейти до п. 7, інакше до п. 9.
7. tii = ti - (tkl - tk), i = k1, ..., п.
Ця процедура означає, що якщо значення Xk і Xk 1 невиразні в межах помилки, то всі моменти часу, починаючи з tk, зменшуються на величину tki-tk.
р = р. Повернутися до п. 4.
Tv = t k; X v: = x k; p = p v = v + l., тобто відбувається формування елементів масивів Т, X, Р і присвоєння чергового значення v.
- 10. Прийняти (t k, ..., t n І (Xk, - Х п) в якості вихідних масивів розмірності п - k 1 + 1 і потім повернутися до п. 2.
- 11. Видати на друк m, (T), (Х,) і (Р,), де i = l, ..., т. Кінець.
Пояснимо сенс елементів супутнього масиву Р. З попереднього тексту випливає, що значення pk дорівнює кількості тих елементів масиву (xk), які безпосередньо, слідують за, і відрізняються від x pi + ... +, +, менше ніж на е. Відзначимо також, що pi + ... + pm = n.
Приклад 1. Дано: п = 20, (/ *) = (2, 4, 7, 10, 12, 13, 15, 17, 20, 22, 24, 25,
- 27, 30, 32, 33, 34, 35, 36) і (х,) = (4, 4, 6, 6, 6, 3, 2, 4, 3, 3, 3, 2, 2, 4, 5 , 5,
- 5, 4, 3), див. Рис. 9, а.
В результаті виконання модуля 1 виходить т = 11,
(Г) = (2, 3, 4, 6, 8, 11, 1-2, 15, 17, 18, 19); (Х,) = (4, 6, 3, 2, 4, 3, 2, 4,5,4,3)
і (д.) = (2, 4, 1, 1, 1,3, 2, 1,3, 1, 1), див. рис. 9, б.
Модуль 2.Вхідними даними для нього є натуральне число т, а також масиви (7 + (X L), = 1, ..., т. Цей модуль в масиві (TJ виявляє моменти часу [ТМ а], 1 = 1 m (ml Приклад 2. Значення т, (Т ь) і (X,] запозичуються з попереднього прикладу. Після виконання модуля 2 виходять ml = 3, m2 = 8, (Щ,) = (3, 8, 17), (Т *) = (3, 4, 6, 8, 11, 12, 15, 17), див. також рис. 9, б. Модуль 3.Вхідні дані ml, m2, (ТМ п), 1 = 1, ..., ml, (Г *), / 2 = 1, ..., ГП2. Цей модуль призначений для побудови масиву (т (-р) за формулою Де ТВ 6 [ТМП, TMn + i] Мінлива т є власний час, породжене зміною змінної х. Його натуральної мірою є одиниця обчислення локальних максимумів. Приклад 3. Вихідні дані для Т 2) ті ж, що значень ml, m2 ITM, і в прикладі 2.. Після відповідних обчислень отримаємо И = (0; 0,2; 0,6; 1;
1,33; 1,78; 2). Модуль 4.Формує видачу результатів шляхом встановлення відповідності між значеннями т і елементами х з масиву (xk). Приклад 4. На основі даних прикладів 2 і 3 видається наступний результат, див. Рис. 9, в: т: 0; 0,2; 0,6; 1; 1,33; 1,44; х: 6; 3; 2; 4; 3Т 0 2; Таким чином, розглянутий алгоритм дозволяє виробити поняття власного часу процесу на основі зафіксованої за астрономічною шкалою часу інформації про зміну стану процесу. Цілком зрозуміло, що можна скористатися і іншими алгоритмами, заснованими, наприклад, на обчисленні послідовності локальних мінімумів або ж змішаною послідовності, що складається з локальних максимумів і мінімумів. При обробці експериментальних даних випливає, ймовірно, відчувати різні варіанти. Якщо з яких-небудь причин експериментатор зупинив свій вибір на одному з конкретних власних часів і отримав при цьому масиви (Т4 і (xk), то на наступному етапі йому належить скористатися будь-якими математичними методами для апроксимації експериментальних точок (т *, х) деякої наближеною світової лінією процесу х = х (т). Екстраполюючи цю лінію за межі вихідного проміжку спостережень, він може видавати прогнози про подальше протікання процесу. Цікаво згадати про обчислювальному експерименті, що призначався для оцінки перспективності застосування запропонованого алгоритму. В якості експериментального матеріалу були обрані дані про річні стоках р. Вахш (Таджикистан) за 40 попередніх років. За цей же проміжок часу були взяті відомості про динаміку числа Вольфа - найбільш уживаного інтегрального індексу сонячної активності. Останнє було покладено в основу розробки власного часу процесу сонячної активності. До нового часу була перетворена інформація про витрати р. Вахш і потім на проміжку спостереження видана теоретична залежність витрати води у вигляді функції від власного часу сонячної активності. Характерна особливість отриманого графіка - майже періодичне поведінку максимальних і мінімальних витрат. Величини витрат, однак, не залишаються постійними. (Час від роботи стає включено до тих пір, поки не буде завершено в разі періодичної діяльності, або поки система не відповідає і руками першого виходу користувача в разі інтерактивної діяльності); або максимізація справедливості(Рівна кількість часу процесора для кожного процесу, або в більш загальному плані відповідних моментів часу відповідно до пріоритетом і робочим навантаженням кожного процесу). На практиці ці цілі часто суперечать (наприклад, пропускна здатність в порівнянні з затримкою), таким чином, надасть права здійснювати відповідний компроміс. Перевага вимірюється будь - якої однієї з проблем, згаданих вище, в залежності від потреб і завдань користувача. У AIX версії 4 є три можливе значення для політики планування потоків: Нитки в першу чергу представляє інтерес для додатків, які в даний час складаються з декількох асинхронних процесів. Ці додатки можуть накласти легку навантаження на систему, якщо перетвориться в багатопотоковому структуру. AIX 5 реалізує наступні політики планування: FIFO, кругової і справедливий кругової. Політика FIFO складається з трьох різних реалізацій: ФІФО, FIFO2 і FIFO3. Кругла політика малинівки називається SCHED_RR в AIX і справедливий кругової називаються SCHED_OTHER. Brain Fuck Scheduler (BFS), також створений Колівас, є альтернативою CFS. FreeBSD використовує багаторівневу чергу зворотного зв'язку з пріоритетами в діапазоні 0-255. 0-63 зарезервовані для переривань, 64-127 для верхньої половини ядра, 128-159 в режимі реального часу потоків користувачів, 160-223 для поділу часу потоків користувачів, і 224-255 для дозвільних ниток користувача. Крім того, як Linux, він використовує активну настройку черги, але він також має святкую чергу. Версією попереднього алгоритму з перемиканнями є алгоритм найменшого часу, що залишився виконання. Відповідно до цього алгоритмом планувальник кожен раз вибирає процес з найменшим часом, що залишився виконання. У цьому випадку також необхідно заздалегідь знати час виконання завдань. Коли надходить нове завдання, її повне час виконання порівнюється з часом, що залишився виконання поточного завдання. Якщо час виконання нового завдання менше, поточний процес призупиняється і управління передається новому завданні. Ця схема дозволяє швидко обслуговувати короткі запити. трирівневе планування Системи пакетної обробки дозволяють реалізувати трирівневу планування, як показано на малюнку. У міру надходження в систему нові завдання спочатку поміщаються в чергу, що зберігається на диску. впускний планувальник доступу
вибирає завдання і передає його системі. Решта завдання залишаються в черзі. Як тільки завдання потрапило в систему, для нього буде створено відповідний процес, і він може тут же вступити в боротьбу за доступ до процесора. Проте можлива ситуація, коли процесів занадто багато і вони всі в пам'яті не поміщаються, тоді деякі з них будуть вивантажені на диск. Другий рівень планування визначає, які процеси можна зберігати в пам'яті, а які - на диску. цим займається планувальник пам'яті
. Планувальник пам'яті періодично переглядає процеси, що знаходяться на диску, щоб вирішити, який з них перемістити в пам'ять. Серед критеріїв, які використовуються планувальником, є наступні: 1. Скільки часу пройшло з тих пір, як процес був вивантажений на диск або завантажений з диска? 2. Скільки часу процес уже використовував процесор? 3. Який розмір процесу (маленькі процеси не заважають)? 4. Яка важливість процесу? Третій рівень планування відповідає за доступ процесів, що знаходяться в стані готовності, до процесора. Коли йде розмова про «Завдання за розкладом», зазвичай мається на увазі саме планувальник процесора
. Цим планувальником використовується будь-який відповідний до ситуації алгоритм, як з перериванням, так і без. Деякі з цих алгоритмів ми вже розглянули, а з іншими ще ознайомимося. Планування в інтерактивних системах. Циклічне планування. Одним з найбільш старих, простих, справедливих і часто використовуваних є алгоритм циклічного планування. Кожному процесу надається деякий інтервал часу процесора, так званий квант часу. Якщо до кінця кванта часу процес все ще працює, він переривається, а управління передається іншому процесу. Зрозуміло, якщо процес блокується або припиняє роботу раніше, перехід управління відбувається в цей момент. Реалізація циклічного планування проста. Планувальником потрібно всього лише підтримувати список процесів в стані готовності. Коли процес вичерпав свій ліміт часу, він відправляється в кінець списку. Єдиним цікавим моментом цього алгоритму є довжина кванта. Перемикання з одного процесу на інший займає деякий час - необхідно зберегти і завантажити регістри і карти пам'яті, оновити таблиці і списки, зберегти і перезавантажити кеш пам'яті і т. П. Висновок можна сформулювати наступним чином: занадто малий квант приведе до частого перемикання процесів і невеликий ефективності, але занадто великий квант може привести до повільного реагування на короткі інтерактивні запити. Значення кванта близько 2 0 -5 0 мс часто є розумним компромісом. Пріоритетне планування. У циклічному алгоритмі планування є важливе припущення про те, що всі процеси рівнозначні. У ситуації комп'ютера з великим числом користувачів це може бути не так. Наприклад, в університеті насамперед повинні обслуговуватися декани, потім професора, секретарі, прибиральниці і лише потім студенти. Необхідність брати до уваги подібні зовнішні чинники призводить до пріоритетного планування. Основна ідея проста: кожному процесу привласнюється пріоритет, і управління передається готовому до роботи процесу з найвищим пріоритетом. Кілька черг. Один з перших пріоритетних планувальників був реалізований в системі CTSS (compatible time-shared system - сумісна система з поділом часу) Основний проблемою системи CTSS було занадто повільне перемикання процесів, оскільки в пам'яті комп'ютера IBM 7094 міг перебувати тільки один процес. Кожне перемикання означало вивантаження з поточною діяльністю на диск і зчитування нового процесу з диска. Розробники CTSS швидко зметикували, що ефективність буде вище, якщо процесам, обмеженим можливостями процесора, виділяти більший квант часу, ніж якщо надавати їм невеликі кванти, але часто. З одного боку, це зменшить кількість перекачек з пам'яті на диск, а з іншого - призведе до погіршення часу відгуку, як ми вже бачили. В результаті було розроблено рішення з класами пріоритетів. Процесам класу з вищим пріоритетом виділявся один квант, процесам наступного класу - два кванта, наступного - чотири кванта і т. Д. Коли процес використовував весь відведений йому час, він переміщався на клас нижче. Як приклад розглянемо процес, якому необхідно робити обчислення протягом 100 квантів. Спочатку йому буде надано один квант, потім він буде перекачано на диск. Наступного разу йому дістанеться 2 кванта, потім 4, 8,16, 32, 64, хоча з 64 він використовує тільки 37. У цьому випадку знадобиться всього 7 перекачек (включаючи початкову завантаження) замість 100, які знадобилися б при використанні циклічного алгоритму. Крім цього, у міру занурення в черзі пріоритетів процес буде все рідше запускатися, надаючи процесор більш коротким процесам. "Найкоротший процес - наступний" Оскільки алгоритм «Найкоротша задача - перша» мінімізує середнє оборотне час в системах пакетної обробки, хотілося б використовувати його і в інтерактивних системах. До певної міри це можливо. Інтерактивні процеси найчастіше йдуть схемою «очікування команди, виконання команди, очікування команди, виконання команди ...» Якщо розглядати виконання кожної команди як окреме завдання, можна мінімізувати загальну середню час відгуку, запускаючи першої найкоротшу завдання. Єдина проблема полягає в тому, щоб зрозуміти, який з очікують процесів найкоротший. Один з методів ґрунтується на оцінці довжини процесу, що базується на попередньому поведінці процесу. При цьому запускається процес, у якого оцінене час найменше. Припустимо, що передбачуваний час виконання команди одно Т 0 і передбачуваний час наступного запуску одно Т 1. Можна поліпшити оцінку часу, взявши зважену суму цих часів аТ 0 + (1 - а) Т 1. Вибираючи відповідне значення а, ми можемо змусити алгоритм оцінки швидко забувати про попередні запусках або, навпаки, пам'ятати про них протягом довгого часу. Взявши а = 1/2, ми отримаємо серію оцінок: Т 0, Т 0/2 + Т 1/2, Т 0/4 + Т 1/4 + Т 2/2, Т 0/8 + Т 1/8 + Т 2/4 + T 3/2. Після трьох запусків вага Т 0 в оцінці зменшиться до 1/8. Метод оцінки наступного значення серії через зважене середнє попереднього значення і попередньої оцінки часто називають старінням. Цей метод можна застосовувати в багатьох ситуаціях, де необхідна оцінка за попередніми значеннями. Найпростіше реалізувати старіння при а = 1/2. На кожному кроці потрібно всього лише додати до поточної оцінки нового значення і розділити суму навпіл (зсунувши вправо на 1 біт). Гарантоване планування. Принципово інший підхід до планування є надання користувачам реальних обіцянок і потім їх виконання. Ось одна обіцянка, яке легко вимовити й легко виконати: якщо разом з вами процесором користуються n користувачів, вам буде надано 1 / n потужності процесора. І в системі з одним користувачем і n запущеними процесорами кожному дістанеться 1 / n циклів процесора. Щоб виконати цю обіцянку, система повинна відстежувати розподіл процесора між процесами з моменту створення кожного процесу. Потім система розраховує кількість ресурсів процесора, на яке процес має право, наприклад час з моменту створення, поділене на n. Тепер можна порахувати відношення часу, наданого процесу, до часу, на яке він має право. Отримане значення 0,5 означає, що процесу виділили тільки половину покладеного, а 2,0 означає, що процесу дісталося в два рази більше, ніж належить. Потім запускається процес, у якого цей показник найменше, поки воно не стане більше, ніж у його найближчого сусіда. Лотерейне планування. В основі алгоритму лежить роздача процесам лотерейних квитків на доступ до різних ресурсів, в тому числі і до процесора. Коли планувальником необхідно прийняти рішення, вибирається випадковим чином лотерейний квиток, і його володар отримує доступ до ресурсу. Що стосується доступу до процесора, «лотерея» може відбуватися 50 разів в секунду, і переможець отримує 20 мс часу процесора. Більш важливим процесам можна роздати додаткові квитки, щоб збільшити ймовірність виграшу. Якщо всього 100 квитків і 20 з них знаходяться у одного процесу, то йому дістанеться 20% часу процесора. На відміну від пріоритетного планувальника, в якому дуже важко оцінити, що означає, скажімо, пріоритет 40, в лотерейному плануванні все очевидно. Кожен процес отримає відсоток ресурсів, приблизно рівний відсотку наявних у нього квитків. Лотерейне планування характеризується кількома цікавими властивостями. Наприклад, якщо при створенні процесу дістається кілька квитків, то вже в наступній лотереї його шанси на виграш пропорційні кількості квитків. Взаємодіючі процеси можуть при необхідності обмінюватися квитками. Так, якщо клієнтський процес посилає повідомлення серверному процесу і потім блокується, він може передати всі свої квитки серверного процесу, щоб збільшити шанс запуску сервера. Коли серверний процес закінчує роботу, він може повернути всі квитки назад. Справедливе планування. До цього часу ми припускали, що кожен процес управляється незалежно від того, хто його господар. Тому якщо користувач 1 створить 9 процесів, а користувач 2 - 1 процес, то з використанням циклічного планування або в разі рівних пріоритетів користувачеві 1 дістанеться 90% процесора, а користувачеві 2 всього 10. Щоб уникнути подібних ситуацій, деякі системи звертають увагу на господаря процесу перед плануванням. У такій моделі кожному користувачеві дістається деяка частка процесора, і планувальник вибирає процес відповідно до цим фактом. Якщо в нашому прикладі кожному з користувачів було обіцяно по 50% процесора, то їм дістанеться по 50% процесора, незалежно від кількості процесів. Планування в системах реального часу. У системах реального часу істотну роль грає час. Найчастіше одне або кілька зовнішніх фізичних пристроїв генерують вхідні сигнали, і комп'ютер повинен адекватно на них реагувати протягом заданого проміжку часу. Системи реального часу діляться на жорсткі системи реального часу
, Що означає наявність жорстких термінів для кожного завдання (в них обов'язково треба укладатися), і гнучкі системи реального часу
, В яких порушення тимчасового графіка небажані, але допустимі. В обох випадках реалізується поділ програми на кілька процесів, кожен з яких передбачуваний. Ці процеси найчастіше бувають короткими і завершують свою роботу протягом секунди. Коли з'являється зовнішній сигнал, саме планувальник повинен забезпечити дотримання графіка. Зовнішні події, на які система повинна реагувати, можна розділити на періодичні(Що виникають через регулярні інтервали часу) і неперіодичні(Що виникають непередбачено). Можлива наявність кількох періодичних потоків подій, які система повинна обробляти. Залежно від часу, що витрачається на обробку кожного з подій, може виявитися, що система не в змозі своєчасно обробити всі події. Схожа інформація. Найчастіше розробники, особливо недосвідчені, губляться, коли їх просять визначити терміни виконання завдань. Однак вміння планувати - дуже корисний і потрібний навик, який допомагає не тільки в роботі, але і в житті. Ми вирішили дізнатися у експертів, як навчитися правильно планувати і здавати проекти вчасно. Короткі висновки можна подивитися в кінці статті. Розробнику зазвичай потрібно врахувати відразу кілька параметрів, щоб оцінити час виконання завдання: Щоб навчитися адекватно оцінювати терміни роботи, потрібно постійно практикуватися. На початку своєї роботи я робив саме так: оцінював час на виконання будь-якої входить завдання, навіть якщо цього ніхто не вимагав, а потім дивився, наскільки точно вдалося потрапити в свою оцінку. У процесі виконання завдання відзначав, що насамперед займають більше часу. Якщо щось сильно збільшувало термін, запам'ятовував цей момент і враховував його в наступних оцінках. До об'єктивній оцінці часу, потрібного чисто на роботу, слід додавати невеликий запас для покриття форс-мажорних ситуацій. Його часто оцінюють у відсотках від виконання основного завдання, але у всіх він різний: хтось додає 20% часу, хтось - 10%, а хтось - 50%. Корисно також аналізувати причини зривів термінів після кожного серйозного порушення дедлайну. Якщо не вистачило кваліфікації, потрібно попрацювати над своїми слабкими місцями. Якщо проблема була організаційної - зрозуміти, що завадило нормально працювати. підвищити Знизити Методиками оцінки трудомісткості проекту, включаючи тривалість робіт і окремих завдань, присвячена велика кількість статей. Однак до сих пір це є причиною виникнення конфліктів як всередині проектної команди, так і при спілкуванні з замовником. Основний помічник в оцінці - досвід. Спробуйте якось зіставити нову задачу з уже зробленими. Якщо ви робите звіт, подивіться, скільки по часу зайняв схожий звіт в минулому. Якщо ви робите щось нове, спробуйте розбити на окремі розділи і оцінити їх. Якщо завдання зовсім нова, виділіть час на вивчення (ще краще - узгодьте цей час з тим, хто ставить завдання). Зверніть увагу на супутні етапи - якщо потрібно розробити сервіс, то в оцінку необхідно включити також і юніт-тестування (а може, і не тільки юніт), певний час займе підготовка тестових даних. Слід продумати інтеграцію з іншими сервісами і т. Д. Закладіть час на виправлення дефектів, які ви знайдете самостійно або за допомогою тестувальників. Багато часу може витікати в «непомітні» завдання. Наприклад, є оцінка по розробці і є оцінка по тестуванню, але передача артефакту на тестування може бути пов'язана з розгортанням стендів. Тому важливо подумки собі уявити весь процес, щоб нічого не упустити. Після визначення трудомісткості необхідно включити нові роботи в календар, не забувши про інші завдання та активності, які йдуть паралельно. І не забувайте, що плани не приносять користі, але планування безцінне. Вчіться вчасно коригувати плани, тримати в курсі всіх зацікавлених і своєчасно ескаліровать, щоб провалені терміни не виявилися ні для кого несподіванкою. підвищити Знизити Питання, на яке неможливо відповісти в короткій формі. Якби це було просто, то проблеми порушення термінів не існувало б. Щоб зробити терміни закінчення розробки більш передбачуваними, треба спочатку зрозуміти причини, по якій програмісти постійно помиляються. Перша причина - більшість завдань, які робить програміст, є в тій чи іншій мірі унікальними. Тобто, швидше за все, програміст буде робити подібну задачу в перший раз. Він недостатньо добре уявляє, скільки займе ця робота. Якщо це програміст з солідним досвідом і йому доводилося виконувати це завдання, його оцінка буде ближче до реальності. Вдамося до простої аналогії - якщо ви ніколи не копали канави, ви не можете точно сказати, скільки часу у вас займе викопати траншею 30 см шириною, 60 см глибиною і 20 метрів довжиною. Якщо ви раніше копали, оцінка часу роботи у вас буде набагато ближче до фактичної тривалості роботи. Друга причина - програмісти за своєю природою оптимісти. Тобто, розглядаючи задачу, підбираючи для неї варіант реалізації, даючи оцінку доопрацюванням, розробник очікує, що все буде працювати так, як він припускає. І не думає про ті проблеми, що йому зустрінуться на шляху. Найчастіше він і не може їх передбачити. Наприклад, є завдання, яке програміст може реалізувати, використовуючи сторонню open-source програмну бібліотеку. На етапі оцінки він знайшов її в інтернеті, прочитав її опис - вона йому підходить. І він навіть вірно оцінив обсяг своєї роботи, щоб вбудувати використання цієї бібліотеки. Але він зовсім не передбачив, що в оточенні його програмного продукту в цій бібліотеці виникне помилка. Розробнику доведеться не тільки вмонтувати використання бібліотеки в свій код, але і виправити помилку в самій бібліотеці. А ще часто розробник не передбачає час на виправлення своїх помилок. Як показує статистика, тестування і виправлення помилок може займати близько 50% від часу, що було витрачено на кодинг. Цифра залежить від кваліфікації розробника, оточення, використовуваних практик розробки (наприклад, юніт тести істотно цей час скорочують і підсумкова тривалість / трудомісткість завдання по розробці виходить менше). Якщо повернутися до аналогії з землекопів, то землекоп не припускав, що у нього зламається лопата і доведеться витратити дві години пошуки нового держака. Третя причина - непередбачувані вимоги. У жодній області матеріального виробництва, з якими так люблять порівнювати замовники розробку ПО, немає такого потоку нових вимог. Уявіть собі пасаж землекопа, який викопав 19 метрів з 20 і почув від замовника побажання, щоб канава йшла не по прямій, а змійкою з довжиною плеча 97 сантиметрів. Як з усім цим боротися і як жити в умовах подібної невизначеності? Зменшуючи невизначеність і закладаючи резерв часу. Найпростіший спосіб привести свої очікування ближче до реальності - це використовувати жартівливе емпіричне правило «Пі». Отримавши оцінку від розробника (за термінами або трудомісткості), треба помножити її на число Пі (= 3,14159). Чим досвідченіший розробник робив оцінку, тим менше може бути цей коефіцієнт. Обов'язковою є практика декомпозиції вихідної задачі до маленьких завдань розміром не більше 4 годин. Чим детальніше виконана декомпозиція, тим вище шанси, що оцінка виявиться близька до фактичної трудомісткості / тривалості. Якщо підвести короткий «разом», то щоб правильно визначити терміни виконання роботи, корисні будуть такі дії: Ну, і пам'ятати, що якщо факт перевищує вашу оцінку на 30% - то це дуже хороший результат. підвищити Знизити Для максимально точної оцінки потрібен досвід реальної розробки, причому саме в конкретній галузі. Але є і загальні правила, які допоможуть уникнути помилок в плануванні і проблем при здачі роботи замовнику. Я б описав ці правила так. По-перше, потрібно зрозуміти завдання. Це начебто очевидно і не відноситься безпосередньо до оцінки термінів, але насправді це ключовий момент. Навіть в серйозних великих проектах одним з основних чинників невдачі і затягування термінів є проблема у визначенні вимог. У початківців розробників, на жаль, це серйозна проблема - не читають ТЗ або читають і розуміють дуже вибірково (з десяти пунктів запам'ятали і виконали п'ять, а про решту згадали вже при здачі результату). Зрозуміло, що неправильно зрозумілу задачу неможливо правильно реалізувати в термін. Далі - оцінити саме час на розробку. Особливість програмування в тому, що не буває абсолютно однакових завдань. Це робить нашу роботу цікавіше, але оцінку термінів - складніше. Тут добре працює декомпозиція, тобто поділ складної унікальної завдання на послідовність маленьких знайомих подзадач. А кожну з них вже можна оцінити в годиннику досить адекватно. Складемо оцінки подзадач - і отримаємо оцінку всієї завдання. Як правило, така оцінка включає в себе тільки витрати безпосередньо на кодування. Це, безумовно, найважливіша частина розробки, але далеко не єдина (а часто - і не сама об'ємна). Повне виконання завдання включає в себе ще читання і прояснення ТЗ, зустрічі з колегами або замовником, налагодження і тестування, складання документації, здачу результату (демонстрацію замовнику і можливі переробки за його зауважень). Скільки саме часу у вас піде на ці дії, підкаже тільки досвід. На перших порах важливо, як мінімум, не забути їх врахувати в розрахунках, а приблизну оцінку часу можна запитати у більш досвідчених колег. Отже, ми беремо оцінку трудовитрат на кодування, додаємо оцінку витрат на додаткові роботи - і отримуємо шукану оцінку часу на виконання завдання. Але і це ще не все! Потрібно позначити плановану дату завершення завдання. Помилкою буде просто взяти і поділити трудовитрати (в годинах) на 8 годин і додати до поточної дати. У реальній практиці розробник ніколи (ну ладно, майже ніколи) не працює 100% часу над одним конкретним завданням. У вас обов'язково буде йти час на інші роботи - важливі, але не пов'язані безпосередньо з головною. Наприклад, допомога колегам, навчання, складання звітів і т.п. Зазвичай при плануванні вважають, що безпосередньо на роботу над поточним проектом іде 60-70% робочого часу. Додатково треба врахувати ще можливі затримки, які не дадуть вам безперервно працювати над завданням. Наприклад, якщо для цього вам потрібно взаємодіяти з іншими людьми (колегами, замовниками), то враховуйте їх зайнятість, графік роботи і т.п. Ось основні правила, які, на мій погляд, допоможуть розробнику уникнути проблем в оцінці і дотриманні термінів. Крім цього, ключовим є накопичення власного досвіду як в реалізації завдань, так і в горизонтальній осі. Наприклад, дуже корисно після завершення завдання порівнювати свою первісну оцінку з фактичними термінами і робити висновки на майбутнє. І, звичайно, варто вивчити чужий досвід. Я б порекомендував по темі книги С. Макконнелла «Скільки коштує програмний проект» і С. Архіпенкова «Лекції з управління програмними проектами». підвищити Знизити При оцінці і плануванні термінів необхідно: підвищити Знизити У нашій компанії планування завдань завжди проходить кілька етапів. На стороні бізнесу ми формулюємо 5-6 стратегічних цілей на рік. Це високорівневі завдання, наприклад підвищити будь-якої параметр на стільки-то відсотків. Далі різні підрозділи компанії формують бізнес-завдання на всі команди ІТ. Терміни по цим завданням отримують первинну грубу оцінку, яка часто формується всіма учасниками команди - менеджером, аналітиком, розробником і тестувальником. Отримавши цю оцінку, бізнес пріорітезірует завдання, з огляду на стратегічні цілі компанії. У цьому допомагають наскрізні стратегічні цілі, з ними стає очевидно, що всі ми працюємо на якийсь спільну справу, немає такої ситуації, коли хтось тягне тільки в свою сторону. З точно оцінених за термінами завдань ми збираємо спринти. У деяких команд вони квартальні, у деяких - місячні. Кільком завданням, за попередньою оцінкою потрапляють в наступний спринт, команди дають точну оцінку. Великі завдання розбиваються на більш низькорівневі, за кожну з яких відповідає конкретний виконавець, саме він і дає точну оцінку. На даному етапі важливо не забувати додавати запас часу на виправлення багів, адже не помиляється тільки той, хто нічого не робить. Це прекрасно розуміють і Product Owner, і бізнес-замовники. При цьому необхідний запас часу повинен бути адекватним: ніхто не зрозуміє розробника, який поставить простого завдання надто довгий термін виконання, його попросять обґрунтувати рішення. Найскладніше - пояснити бізнесу, навіщо потрібен час на рефакторинг. Ми вдячні нашій компанії за те, що періодично нам це вдається, адже в кінцевому рахунку рефакторинг веде до полегшення інфраструктури і наведення порядку в коді, що підвищує стабільність системи і може істотно прискорити розробку нових функцій. Іноді помилки в оцінці все ж виникають. Відділу розробки в великих компаніях з розвиненою інфраструктурою повністю уникнути цього, на мій погляд, неможливо. В даному випадку важливо, щоб розробник вчасно інформував про те, що відбувається свого менеджера, а той, у свою чергу, встиг попередити бізнес і щось «переграти» в загальних планах компанії. У такому режимі працювати набагато більш правильно, ніж судорожно намагатися зробити за 3 дня то, що займає 5, а потім потонути у великій кількості помилок, що виникли через подібну поспіху. підвищити Знизити Правильна відповідь на обидві частини питання [як навчитися правильно планувати і здавати проект вчасно - ред.] - досвід. Інших шляхів «пізнання Дзена» не існує. Відповідно до теорії прийняття рішень, скільки-небудь точні висновки можна будувати тільки на основі аналізу ряду вже наявних даних. І чим більше цих даних - тим точніше підсумковий прогноз і оцінка. Говорячи словами Герберта Шоу: «Досвід - це школа, в якій людина дізнається, яким дурнем він був раніше». Звідси випливає досить простий висновок: якщо у програміста вже є корелює з поставленим завданням досвід - він може спертися на нього, якщо немає - на досвід «колег по цеху». Далі потрібно розуміти, що пряме планування термінів - завдання, з якою люди справляються дуже і дуже погано, особливо в розробці. При оцінці термінів здачі хорошою практикою вважається введення «поправочних коефіцієнтів» на вихідну оцінку. Дана метрика може коливатися в інтервалі від 1,5 до 3, в залежності від досвіду розробника і сукупності ступенів невизначеності завдань, що вирішуються в рамках проекту. підвищити Знизити При визначенні термінів важливо враховувати багато факторів. Наприклад досвід роботи. Наскільки чітко ви уявляєте собі обсяг майбутніх робіт? Чи робили раніше щось подібне? Зрозуміло, що чим більше досвіду, тим швидше робота буде виконана. Чималу роль у визначенні термінів грає грамотно складене технічне завдання. З цим в нашій сфері справи йдуть дуже туго. Часто клієнт сам не знає, чого хоче, тому я раджу витратити зайвий день-два, але добитися від клієнта чіткого уявлення про бажаний результат. Важливо, щоб це подання було обопільним. І тільки після цього можна починати обговорювати суму і терміни. Також завжди закладайте ризики. Новачкам я рекомендую передбачувані терміни виконання множити на два. Адже краще здати проект раніше термінів і вирости як фахівець в очах замовника, ніж здати пізніше і зіпсувати свою репутацію. підвищити Знизити Загальна рекомендація - розробнику необхідно навчитися правильно декомпозировать завдання, завжди шукати можливі підводні камені, спиратися на власний досвід і не забувати вчасно попереджати замовників і колег, якщо в названі терміни завдання вирішити не виходить. Вибудувати чіткий план набагато складніше, ніж визначити термін виконання окремо взятої задачі. При цьому важливо не тільки здати проект вчасно, але і зробити так, щоб розроблена вами система коректно вирішувала завдання бізнесу. Тут ІТ-командам допомагають різні методології розробки ПО: від RUP і MSF до SCRUM та інших Agile-форматів. Вибір інструментів досить великий, і багато наших замовників хочуть заздалегідь розуміти, як ми будемо з ними працювати в проекті, яких принципів ми дотримуємося. До слова, тема Agile сьогодні стає близька і бізнесу, і навіть в окремих проектах держсектору, оскільки принципи цієї методології дозволяють реалізовувати проекти дуже швидко, керуючи очікуваннями замовника на кожній ітерації. Наприклад, в Agile-команді практично не буває тривалих обговорень з замовником. Забудьте про десятки сторінок з описом непотрібних технічних деталей, наприклад, про швидкість появи списку. Дайте замовнику можливість спробувати проміжну версію системи, тоді і розуміти один одного вам стане набагато простіше. Agile-команда все планує разом і визначає оптимальний рівень трудовитрат, які знадобляться для вирішення того чи іншого завдання. Наприклад, одна з технік називається «Poker Planning», де кожен учасник анонімно дає свою оцінку необхідних трудовитрат по конкретному завданні. Після цього команда визначає середня вага завдання в story points або людино-годинах і розподіляє справи за принципом «кому що подобається». При цьому щодня команда збирається на 15-хвилинний мітинг, коли кожен за пару хвилин розповідає про статуси своїх поточних завдань, в тому числі повідомляє про виниклі труднощі. Виявлену проблему команда швидко усуває, тому і замовник дивиться на черговий етап роботи програміста максимально оперативно. Розробники не затягують з термінами виконання завдань через небажання зайвий раз смикати команду або марних спроб розібратися самостійно, вбиваючи дорогоцінний час. До речі, на таких міні-статусах у розробників з'являється бажання проявити себе з кращого боку, показати, що ти відповідально підходиш до роботи. Це реально мотивує і самодісціплінірует.
OS / 360 і наступники
AIX
Linux
Linux 2.4
FreeBSD
, технічний директор центру інноваційних технологій і рішень «Інфосистеми Джет»
Якщо повернутися до виділення резерву - це час має бути виділено в кінці проекту. Погана практика робити резерв і включати його для кожного завдання. Закон Паркінсона «Робота заповнює весь час, відпущений на неї» виконується неухильно.