Задача 1 от брой 10/2004 - ПАРТИ - Анализ

Първата задача в Конкурса програмиране тази година е представител на широк кръг от задачи за планиране на процеси. Тези задачи разглеждат процеси (работи) които трябва да бъдат изпълнени (извършени) на един или няколко процесора (работни места) и имат различни оптимизационни цели – необходим брой процесори, време за изпълнение, време на бездействие на процесорите, време за чакане и др. Процесите могат да бъдат взаимно зависими – започването на изпълнението на един процес да изисква приключването на друг, да са динамични – не всички процеси са предварително известни, да имат различна важност (ценност или приоритет) и др.

В нашата задача процесите са независими, статични (известни предварително) и еднакво важни, и целта е сумарното време на чакане на процесите да е минимално. За чакане на един процес се брои времето от появата (времето за пристигане в орбита на кораб) до започване на изпълнението му (момента когато корабът започва да каца). Всеки процес има две характеристики – време на поява и време за изпълнение. Ако някоя от тях беше константна – еднаква за всички процеси – то решението щеше да е лесно.

Ако всички процеси имат еднакво време на поява, то е очевидно (и лесно може да се докаже), че процесите трябва да бъдат изпълнявани в нарастваш ред според времето им за изпълнение. Например, ако имаме само два процеса А и В с време на поява 1 и време за изпълнение съответно 5 и 50, и налице е само един процесор, то ако изпълним първо А общото време за чакане ще е 5, а ако изпълним първо В общото време за чакане ще е 50.

Ако пък всички процеси имат еднакво време за изпълнение, то процесите трябва да бъдат изпълнявани в реда на появата им, защото няма полза един процес, който може да бъде изпълнен да изчаква  друг след като няма разлика във времето им за изпълнение и само би се увеличило общото време за чакане. А когато са се натрупали много процеси чакащи за изпълнение, то за нас няма значение който ще изпълним по-напред и затова редът в който са се появили е една напълно приемлива наредба за изпълнението им.

Поглеждайки тестовете примери, с които е извършена проверката ще забележим, че първите четири от тях реализират точно тези два лесни случая. Интересен е резултатът на Александър Андонов – ако програмата му не даваше грешка по време на изпълнението на тези четири тестови примери, вероятно той щеше да заеме първото място. Решението отстъпва реално само в един тест на решението на Васил Поповски, който реализира генетичен алгоритъм. Използването на такъв алгоритъм се среща рядко на програмистки състезания с алгоритмичен характер, но резултатът в случая е задоволителен – най-добър общ резултат на първите шест тестови примера и 5-то място в класирането.

Една възможна идея за решение е „симулация” на времето. Имаме таймер с начална стойност 0. На всяка стъпки той се увеличава с едно, след това в списъка на чакащите процеси се добавят процесите, които се появяват в този момент, след това в списъка на свободните процесори се добавят тези които приключват обработката на процес в този момент и накрая на свободните процесори даваме да се обработват чакащите процеси. Ако има повече чакащи процеси отколкото свободни процесори, то логично е да изберем тези които ще се изпълняват за по-кратко време. Така обаче не се възползваме от това, че процесите са статични и при следният кратък пример – един процесор, два процеса с време на поява 1 и 2 и съответни времена за изпълнение 50 и 5 – се вижда, че решението може да направи доста лошо планиране и в конкретния пример да се получи общо време за чакане 49 вместо 7.

Идея използваща статичността на процесите е на пример тази, реализираща планирани в ред на възможно най-ранно завършване. Първо определяме да се изпълни процеса който може да завърши най-рано. След това следващият процес който може да завърши най-рано от останалите и т.н. Това се реализира лесно за един процесор и лесно се обобщава за N процесора. Внимателният читател вероятно е забелязал, че гореизложените случаи, когато едната от характеристиките на процесите е константа се решават правилно от алгоритъм използващ планиране с най-ранно завършване. Решение реализиращо тази идея би имало приблизително 86.5 точки, ако беше включено в класирането.

Разбира се, една програма може да реализира няколко алгоритъма и да се изведе отговорът на този даващ най-доброто решение за текущия тестов пример или да се реализира изчерпващо решение използващо таймер. Комбинация между тези две идеи също е възможна.

Първите три места в класирането от задача 1 са заети от Иван Пешев, Кирил Минков и Борис Даскалов съответно 99.19, 99.02 и 98.98 точки. Разликата между тях е минимална и единствено те са успели да съберат над 90 точки, което показва, че всеки от тях е успял да намери успешен път към реализирането на добро решение на задачата. Надяваме се, че те ще откликнат на поканата да споделят своите идеи за решение, които ще можете да намерите на сайта на Конкурса – http://konkurs.musala.com . Все пак, победителят е само един и това е Иван Пешев.

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.