Спросить
Войти
Научно-образовательный журнал для студентов и преподавателей «StudNet» №10/2020
РАСЧЕТ ХАРАКТЕРИСТИК ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С РАЗДЕЛЕНИЕМ ПРОЦЕССОРОВ
CALCULATION OF CHARACTERISTICS OF COMPUTING SYSTEMS WITH
SEPARATION OF PROCESSORS
УДК 519.872.8
Варданян Аветик Оганнесович, студент 4 курс, факультет «Кибернетика» МИРЭА - Российский технологический университет, Россия, г. Москва
Vardanyan Avetik Ogannesovich, avet-privet@mail.ru
Аннотация
Актуальность предлагаемого исследования обусловлена широким использованием систем массового обслуживания (СМО) с разделением процессоров во многих отраслях науки и техники, компьютерных сетях, многопоточных процессорах, различных организационных системах.
В статье рассматриваются такие характеристики как среднее время пребывания заявок в СМО с разделением процессоров.
Статья посвящена СМО с разделением процессоров с 1 и 2 приборами.
С этой целью в результате выполнения работы разработана программа, моделирующая работу СМО с разделением процессоров для расчета указанных выше характеристик с различными значениями интенсивностей входных потоков и интенсивностей обслуживания.
Annotation
The relevance of the proposed research is due to the widespread use of queuing systems (QS) with separation of processors in many branches of science and
technology, computer networks, multi-threaded processors, and various organizational systems.
The article discusses such characteristics as the average residence time of applications in the QS with separation of processors.
The article is devoted to the QS with the separation of processors with 1 and 2 devices.
For this purpose, as a result of the work, a program has been developed that simulates the operation of the QS with the separation of processors for calculating the above characteristics with different values of the intensities of the input flows and the rates of service.
Рассмотрим однопроцессорные вычислительные системы с разделением процессоров.
В ВС один процессор и нет ограничений на очередь. Входной поток заданий в ВС является простейшим, длительности интервалов между последовательно приходящими в ВС заданиями распределены либо по показательному, либо по эрланговскому закону распределения третьего порядка с параметром X. Время выполнения каждого задания процессором распределено либо по показательному, либо по эрланговскому закону распределения третьего порядка с параметром Процессор может одновременно выполнять не более N заданий, равномерно разделяя между ними время. Остальные задания находятся в очереди.
Состояние СМО с разделением процессора характеризуется количеством заданий j, находящихся в момент события в СМО. Событием в развитии СМО является переход из одного состояния в другое. События могут быть двух типов:
появится задание, распределено по показательному или эрланговскому закону третьего порядка с параметром X. Время выполнения задания распределено по показательному или эрланговскому закону третьего порядка с параметром
Изложим принцип работы данной системы для первых 3 событий. Как сообщалось ранее, события могут быть двух типов: 1 - появление в ВС нового задания, 2 - завершение выполнения одного из заданий. Если после события типа 1 в ВС стало n заданий и n меньше или равно N, то с момента появления нового задания процессор будет одновременно выполнять n заданий. Если после события типа 1 число заданий в ВС стало больше N, то процессор продолжит одновременно выполнять N заданий, а новое задание станет в очередь типа FIFO. Если после события типа 2 в ВС осталось n заданий и n меньше N (т.е. нет очереди), то число одновременно выполняемых процессором заданий уменьшилось на 1, стало равно n. Если до события типа 2 в ВС была очередь, то после события первое задание из очереди начнет выполняться, число заданий в очереди уменьшится на 1, а число одновременно выполняемых процессором заданий останется равным N.
В момент времени t=0 состояние ВС n(0)=0 и определяется случайным образом в соответствии с показательным (эрланговским) законом распределения с параметром X время, через которое в ВС появится первое задание Ъоб(1)=в(1). Одновременно определяется случайным образом в соответствии с показательным (эрланговским) законом распределения с параметром ^ время выполнения первого задания W^l), а также в соответствии с показательным (эрланговским) законом распределения с параметром X время, через которое в СМО появится следующее (второе) задание W(1). Первое событие имеет тип 1. После события 1 ВС будет находиться в состоянии п(^о6(1))=1. Если W^Wl), то в момент Ъоб(2)=Ъоб(1^вып(1) ВС будет находиться в состоянии п(^о6(2))=0, событие 2 будет иметь тип 2, W(2)=t^(1)-t^!). Если ^1)>ож(1), то в момент Ъоб(2)=Ъоб(1)+^ж(1) ВС будет находиться в
состоянии п(^об(2))=2, событие 2 будет иметь тип 1, т.е. в ВС появится второе задание, для которого определяется случайным образом в соответствии с показательным (эрланговским) законом распределения с параметром ц время выполнения второго задания ^Ьт(2), в этот же момент определяется случайным образом в соответствии с показательным (эрланговским) законом распределения с параметром X время, через которое в ВС появится следующее задание ^ж(2). С момента Ъоб(2) процессор будет одновременно выполнять 2 задания, оставшееся время выполнения задания 1 после события 2 будет равно ^ст(2Д)=2*(^ып(1)-1:ож(1)), оставшееся время выполнения задания 2 после события 2 будет равно ит(2,2)=2%ып(2). Пусть tмин(2)=min{tост(2,1),tост(2,2)}. Если (2), то событие 3 будет иметь тип 1. Если tмин(2)<tож(2), то событие 3 будет иметь тип 2.
Теперь рассмотрим двухпроцессорные вычислительные системы с разделением процессоров.
В ВС два процессора и нет ограничений на очередь. Входной поток заданий в ВС является простейшим, длительности интервалов между последовательно приходящими в ВС заданиями распределены по показательному (эрланговскому) закону с параметром X. Время выполнения каждого задания первым процессором распределено по показательному (эрланговскому) закону с параметром Время выполнения каждого задания первым процессором распределено по показательному (эрланговскому) закону с параметром Процессоры могут одновременно выполнять не более 5 заданий, равномерно разделяя между ними время. Остальные задания находятся в очереди.
Состояние ВС (Е3|Е3|2) с разделением процессоров в каждый момент времени t характеризуется числами (kl(t);k2(t);r(t)), где - количество заданий в первом процессоре, k2(t) - количество заданий во втором процессоре, г(:) -количество заданий в очереди. Максимально возможное число заданий в каждом процессоре N=5. Сначала задания поступают в процессоры поочередно: 1-ое задание в первый процессор, 2-ое задание во второй процессор. Затем
пришедшее в ВС задание поступает в тот процессор, где меньше заданий. При равенстве числа заданий - в первый процессор. Если в каждом процессоре по N заданий, то пришедшее в ВС задание становится в очередь. События могут быть трех типов: 1 - появление в ВС нового задания, 2 - завершение выполнения одного из заданий на первом процессоре, 3 - завершение выполнения одного из заданий на втором процессоре.
Изложим принцип работы данной системы. Если после события типа 1 в ВС стало n заданий и n меньше или равно N, то с момента появления нового задания процессор будет одновременно выполнять n заданий. Если после события типа 1 число заданий в ВС стало больше N, то процессор продолжит одновременно выполнять N заданий, а новое задание станет в очередь типа FIFO. Если после события типа 2 в ВС осталось n заданий и n меньше N (т.е. нет очереди), то число одновременно выполняемых процессором заданий уменьшилось на 1, стало равно n. Если до события типа 2 в ВС была очередь, то после события первое задание из очереди начнет выполняться, число заданий в очереди уменьшится на 1, а число одновременно выполняемых процессором заданий останется равным N.
В момент времени t=0 состояние ВС (k1(0);k2(0);r(0))=(0,0,0) и определяется случайным образом в соответствии с показательным (эрланговским) законом распределения с параметром X время, через которое в ВС появится первое задание Ъоб(1)=*(1). В момент времени Ъоб(1) состояние ВС станет (k^t^Q^^t^WMt«^^^)^ ,0,0). После прихода в ВС очередного задания сразу же определяется случайным образом в соответствии с показательным (эрланговским) законом распределения с параметром X время, через которое в ВС появится следующее задание. В момент поступления задания в процессор с номером m определяется случайным образом в соответствии с показательным (эрланговским) законом распределения с параметром нормативное время выполнения этого задания. Нормативное время выполнения задания - время выполнения задания при условии, что в процессоре нет других заданий. При поступлении нового задания в процессор или завершении
выполнения одного из заданий в процессоре оставшееся время выполнения каждого оставшегося в процессоре задания пересчитывается пропорционально числу заданий в процессоре. В момент времени ^об(1) наступления события l происходит сравнение времени, через которое в ВС появится следующее задание tj, времени ^мин.об,1), через которое завершится выполнение одного из заданий на процессоре 1, и времени ^мин.об,2), через которое завершится выполнение одного из заданий на процессоре 2. Если tз меньше, то следующее событие (1+1) будет иметь тип Typ(1)=1 и Ъоб(1+1)=соб(1)+ tз. Если t(мин.об,1) меньше, то следующее событие (1+1) будет иметь тип Typ(1)=2 и ^об(1+1)=:соб(1)+ t(мин.об,1). Если t(мин.об,2) меньше, то следующее событие (1+1) будет иметь тип Typ(1)=3 и Ъоб(1+1)=Ъоб(1)+ ^мин.об,2).
Literature
I. Adam and J. Resing. Queuing systems // Department of Mathematics and Computer Science, Eindhoven University of Technology. - 2015. - C. 23-54.
