10.14489/vkit.2016.05.pp.034-040

DOI: 10.14489/vkit.2016.05.pp.034-040

Колесов Н. В., Грузликов А. М., Скородумов Ю. М., Толмачева М. В.
СМЕШАННОЕ ПЛАНИРОВАНИЕ ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ
(c. 34-40)

Аннотация. Рассмотрены вопросы планирования заданий в распределенных системах реального времени типа job shop. Показано применение алгоритма планирования вычислительного процесса в данных системах, который представляет собой комбинацию двух подходов – сетевого упорядочивания и (flow shop)-планирования. Для (flow shop)-планирования применен разработанный эффективный эвристический алгоритм, основанный на понятии разрешимого класса систем, для которого существует оптимальный алгоритм планирования линейной сложности. Представлен класс (job shop)-систем, когда возможна незначительная модификация алгоритмов (flow shop)-планирования.

Ключевые слова: планирование заданий; система реального времени; разрешимый класс вычислительных систем; сетевое упорядочивание.

Kolesov N. V., Gruzlikov A. M., Skorodumov Yu. M., Tolmacheva M. V.
MIXED JOB SCHEDULING IN DISTRIBUTED REAL TIME SYSTEMS
(pp. 34-40)

Abstract. Job scheduling in a distributed real-time systems of general form is considered. It is assumed that a single job consists of a number of tasks connected within certain precedence constraints according to acyclic directed graph. It is considered that some tasks of the jobs are assigned to the processors according to the flow shop scheduling model while other tasks assignment does not correspond to that model. The paper proposes a mixed scheduling algorithm based on a combination of two wellknown approaches: network scheduling and approach based on the concept of solvable classes of systems. The first approach uses the concept of critical path of the job to allocate its tasks to the processors, and the task execution ordering corresponds to the precedence constraints. The second approach is based on the previously presented flow shop scheduling algorithm for the known solvable classes. There are several solvable classes of distributed computing systems for which simple optimal scheduling algorithms exist. Thus the paper considers certain type of job shop systems for which lightly modified flow shop scheduling algorithms can be used.

Keywords: Job scheduling; Real-time system; Solvable class of systems; Network scheduling.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Н. В. Колесов (Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики; ГНЦ РФ АО «Концерн «Центральный научно-исследовательский институт «Электроприбор», Санкт-Петербург) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
А. М. Грузликов, Ю. М. Скородумов, М. В. Толмачева (ГНЦ РФ АО «Концерн «Центральный научно-исследовательский институт «Электроприбор», Санкт-Петербург)

Eng

N. V. Kolesov (Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics; State Research Center of the Russian Federation Concern CSRI Elektropribor, JSC, Saint-Petersburg) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
A. M. Gruzlikov, Yu. M. Skorodumov, M. V. Tolmacheva (State Research Center of the Russian Federation Concern CSRI Elektropribor, JSC, Saint-Petersburg)

+ - Библиографический список (References) Click to collapse

Рус

1. Колесов Н. В., Толмачева М. В., Юхта П. В. Планирование вычислительного процесса в многопроцессорных системах при заданных для решаемых задач директивных сроках // Вестник компьютерных и информационных технологий. 2009. № 6. С. 31 – 37.
2. Зорин Д. А., Костенко В. А. Алгоритм синтеза архитектуры вычислительной системы реального времени с учетом требований к надежности // Изв. РАН. Теория и системы управления. 2012. № 2. С. 124 – 131.
3. Burkard R. E., Dell’Amico M., Martello S. Assignment Problems. Philadelphia: Society for Industrial and Applied Mathematics, 2009. 382 р.
4. Liu J. W.-S. Real-Time Systems. Englewood Cliffs, NJ.: Prentice Hall, 2000. 600 p.
5. Cottet F., Kaiser J., Delacroix J., Mammeri Z. Scheduling in Real-Time Systems (Hardback). UK: John Wiley & Sons Ltd, 2002. 282 р.
6. Drozdowski M. Scheduling for Parallel Processing (Computer Communications and Networks). London: Springer – Verlag, 2009. 395 р.
7. Колесов Н. В., Толмачева М. В., Юхта П. В. Системы реального времени. Планирование, анализ, диагностирование. СПб.: Изд-во ГНЦ РФ ОАО «Концерн ЦНИИ «Электроприбор», 2014. 185 с.
8. Колесов Н. В., Толмачева М. В., Юхта П. В. Планирование вычислительного процесса в распределенных системах реального времени с неопределенными длительностями решения задач // Изв. РАН. Теория и системы управления. 2012. № 4. С. 39 – 50.
9. Bettati R., Liu J. W.-S. End-to-End Scheduling to Meet Deadlines in Distributed Systems // Proc. of the 12th Intern. Conf. on Distributed Computing Systems, Yokohama, Japan, June 1992. P. 452 – 459.
10. Altenbernd P., Hansson H. The Slack Method: A New Method for Static Allocation of Hard Real-Time Tasks // Real-Time Systems. 1998. V. 15, № 2. P. 103 – 130.
11. Колесов Н. В., Скородумов Ю. М., Толмачева М. В. Комбинированный алгоритм планирования заданий в распределенных системах реального времени // Материалы 8-й Всерос. мультиконф. по проблемам управления (МКПУ-2015). с. Дивноморское, Геленджик, Россия, 28 сент. – 3 окт. 2015 г. Ростов н/Д, 2015. Т. 3. С. 28 – 31.

Eng

1. Kolesov N. V., Tolmacheva M. V., Iukhta P. V. (2009). Computational processes planning in multiprocessor systems for tasks with specified deadlines. Vestnik komp'iuternykh i informatsionnykh tekhnologii, (6), pp. 31-37.
2. Zorin D. A., Kostenko V. A. (2012). The algorithm of architecture synthesis for computing real-time system to meet the requirements for reliability. Izvestiia RAN. Teoriia i sistemy upravleniia, (2), pp. 124-131.
3. Burkard R. E., Dell’Amico M., Martello S. (2009). Assignment problems. Philadelphia: Society for industrial and applied mathematics.
4. Liu J. W.-S. (2000). Real-time systems. Englewood Cliffs, NJ.: Prentice Hall.
5. Cottet F., Kaiser J., Delacroix J., Mammeri Z. (2002). Scheduling in real-time systems (Hardback). UK: John Wiley & Sons Ltd.
6. Drozdowski M. (2009). Scheduling for parallel processing (Computer Communications and Networks). London: Springer – Verlag.
7. Kolesov N. V., Tolmacheva M. V., Iukhta P. V. (2014). Real-time systems. Planning, analysis, diagnostics. St. Peterburg: Izdatel'stvo GNTs RF OJSC «Kontsern TsNII «Elektropribor»
8. Kolesov N. V., Tolmacheva M. V., Iukhta P. V. (2012). Planning of the computational process in distributed real-time systems with uncertain long-term solution of problems. Izvestiia RAN. Teoriia i sistemy upravleniia, (4), pp. 39-50.
9. Bettati R., Liu J. W.-S. (1992). End-to-end scheduling to meet deadlines in distributed systems. Proc. of the 12th Intern. Conf. on Distributed Computing Systems, Yokohama, Japan, June 1992, pp. 452-459.
10. Altenbernd P., Hansson H. (1998). The slack method: a new method for static allocation of hard real-time tasks. Real-Time Systems, 15(2), pp. 103-130. doi: 10.1023/A:1008092427865
11. Kolesov N. V., Skorodumov Iu. M., Tolmacheva M. V. (2015). Combined scheduling algorithm in distributed real-time systems. Proceedings of the 8th All-Russian multiconference on management problems (MKPU-2015). Divnomorskoye Village, Gelendzhik, Russia, 28 September – 3 October 2015. Rostov-on-Don, 2015, Vol. 3. pp. 28-31.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2016.05.pp.034-040}

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2016.05.pp.034-040}