Cтраница 2
Из замечания 1.4 следует, что задачи 2.2, г), д), з) остаются ЛФ-труднымп в сильном - смысле и при разрешении прерываний процесса обслуживания требований. [16]
Из замечания 1.4 ( см. § 1 данной главы) следует, что задачи 5.1, а) - з) остаются JVP-трудными в сильном смысле и при разрешении прерываний процесса обслуживания требований. [17]
В силу замечания 2.2 ( см. § 2 данной главы) из ЛТ-труд-ности в сильном смысле задач 4.1, 4.3, а) - д) следует, что при разрешении прерываний процесса обслуживания требования в целочисленные моменты времени эти задачи остаются АФ-трудпыми в сильном смысле и при замене условия tii ( i 1, п) условием: tf - целые числа. [18]
Теорема 1.2. Если М 2, dt d, i СЯ G ( N0) и F ( x) - неубывающая е-квазивогнутая ( при х 0) функция, то существует оптимальное расписание без прерываний процесса обслуживания требований. [19]
Пусть в задачах 2.1, г), 2.4, г), 3.2, 4.3, в), усло-вие tt 1 ( i 1, п) заменено условием: Ь - целые числа, и допускаются прерывания процесса обслуживания требования в целочисленные моменты времени. Тогда, в силу замечания 2.2, задачи о существовании допустимого относительно заданных директивных сроков расписания, соответствующие полученным задачам, являются ЛФ-труднымн в сильном смысле. [20]
Задача 1.2. Обслуживающая система состоит из одного прибора. Прерывания процесса обслуживания требования не допускаются. [21]
Обслуживание требования i е N может быть выполнено любым из приборов и требует t единиц времени. Прерывания процесса обслуживания требования не допускаются. Каждая компонента связности G представляет собой входящее дерево. [22]
Обслуживание требования i е N может быть осуществлено любым из приборов в течение tf единиц времени. Прерывания процесса обслуживания требования не допускаются. Каждая компонента связности G представляет собой выходящее дерево. [23]
Все требования поступают в очередь на обслуживание одновременно. В процессе обслуживания требований разрешены прерывания. Предполагается, что прерывания не сопряжены с временными затратами и число прерываний конечно. [24]
Один из возможных способов уменьшения числа непроизводительных передач информации между ОЗУ и ВЗУ состоит в том, что при - квантовании приоритетного обслуживания требований каждому уровню приоритета ставится в соответствие своя величина кванта времени, причем с увеличением номера уровня величина кванта возрастает. В процессе обслуживания требований осуществляется перемещение их из одной очереди в другую. Если выполнение некоторой программы при предоставлении ей очередного кванта не завершено, соответствующее этой программе требование перемещается в конец очереди, принадлежащей следующему уровню приоритета с большим номером. Следовательно, требования с большим временем обслуживания получают большие значения квантов. Передвижение требования из одной очереди в другую, связанное с увеличением суммарного времени ожидания обслуживания, происходит до определенного момента. Если время ожидания требования в очереди превышает некоторую величину Т, то это требование перемещается в конец очереди, принадлежащей следующему уровню приоритета с меньшим номером. [25]
Это такие дисциплины, в которых одни требования на основании каких-то признаков получают преимущество ( приоритет) в выборе на обслуживание перед другими. Если же прерывание процесса обслуживания требований не допускается, то в этом случае можно говорить о СМО с относительными приоритетами. Например, в междугородной телефонной станции срочные разговоры получают преимущество ( обладают более высоким приоритетом) перед обычными междугородными разговорами. [26]
Обслуживание требования i e N может быть начато не раньше, чем в момент времени di 5 0, и должно осуществляться в течение tt0 единиц времени. Если противное не оговорено, то прерывания процесса обслуживания требования не допускаются. Каждому i е N сопоставлено число а ( 0 и директивный срок Df О, к которому желательно завершить обслуживание требования i. [27]
Если d di l, i - 1, и, то расписание s, очевидно, не содержит прерываний. Поэтому условия (2.4) и (2.6) являются необходимыми и достаточными условиями обслуживания требований одним прибором в заданные сроки и в случае, когда запрещены прерывания процесса обслуживания требований. [28]
Таким образом, задача 4.1 является Л Р - трудной в сильном смысле. Из замечания 1.4 ( см. § 1 данной главы) следует, что задача 4.1 остается ЖР-трудной в сильном смысле и при разрешении прерываний процесса обслуживания требования. [29]
Замечание 2.2. Рассмотрим класс задач, в которых моменты dt поступления требований в обслуживающую систему и длительности ti их обслуживания - целые числа. Пусть задачи А ж В из этого класса различаются лишь тем, что в задаче А все длительности tt 1 либо ti s ( 0, 1 п прерывания процесса обслуживания требования запрещены, а в задаче В значения ti могут быть различными и разрешены прерывания, но только в целочисленные моменты времени. Тогда очевидно, что существует как полиномиальное, так и псевдополиномиалъное сведение задачи А к задаче В. [30]