Kolejki to bardzo fajna rzecz dopóki zasada jej działania opiera się na znanych i przetartych już wcześniej rozwiązaniach. Problem pojawia się, gdy istnieje potrzeba specyficznego jej zastosowania. Takim przykładem może być kolejka sprawiedliwego odświeżania (tak ją sobie roboczo nazwałem).
O co konkretnie chodzi?
Wyobraźmy sobie skrypt działający w tle, który ma za zadanie odświeżać co jakiś czas informacje konkretnego procesu. Musimy również zadbać, aby odświeżanie wszystkich zadań występowało w równych odstępach czasu - powiedzmy co 15minut, niezależnie od ilości zadań w kolejce.
Sprawa pozornie wydaje się być prosta, ale jak o to zadbać, gdy wykonanie fragmentu programu odpowiedzialnego za aktualizację zadania nie ma ściśle określonego czasu lub kolejka jest na tyle długa bądź krótka, że kolejny cykl odświeżania nastąpi za wcześnie lub za późno. Reasumując, cykl odświezania może nastąpić dla niego po upływie zarówno 7 minut jak i 25 minut.
Przypadek idealny
Najbardziej optymalnym wariantem jest 15 zadań, które wykonują się równo jedną minutę. Wtedy nie ma najmniejszego problemu, gdyż każde z zadań zostanie wykonane co 15 minut.
Za dużo lub za mało zadań
Nie jest jednak nigdzie powiedziane, że zadań musi być dokładnie 15. Nawet zakładając, że każde z nich wykona się dokładnie w jedną minutę, kolejka zacznie powtarzać się za wcześnie lub za późno - nie gwarantując nam 15-minutowego cyklu odświeżania.
Łatwo zauważyć, że w przypadku trzynastu zadań pośpieszymy się z cyklem o dwie minuty, natomiast z szesnastoma zadaniami, każde z nich będzie miało jednominutowe opoźnienie.
Coś mnie zatrzymało / pogoniło
Sprawa jeszcze bardziej się komplikuje, gdy zadanie wykona się w czasie krótszym lub dłuższym niż deklarowana minuta. Nie dość, że pełny cykl nie zakończy się w wyznaczonych 15 minutach - to każde z zadań może wykonać się w pełnym przebiegu wcześniej lub później. Totalny chaos!
Planowane zadania
Pierwsze co musimy zrobić, to wyznaczyć maksymalny czas, potrzebny na wykonanie pojedynczego zadania. Załóżmy, że jest to typowo 30 sekund. Oczywiście może zdarzyć się, że zadanie zostanie wykonane w czasie krótszym lub dłuższym. Dlatego dajmy sobie zapas w postaci kolejnych 30 sekund. Tak więc, dopuszczalny
przedział czasowy na pojedyńcze zadanie wyniesie 60 sekund.
Jeśli chcemy, aby pełny cykl wynosił 15 minut (900sekund), musimy obliczyć ile zadań możemy bezpiecznie wpuścić do naszej kolejki. Obliczając 900:60 wychodzi nam okrągłe 15 zadań w kolejce. Sprawa jest już nieco prostsza - każde zadanie musi zacząć się o pełnej minucie, niezależnie od tego, ile trwało poprzednie zadanie.
Obliczenie czasu do odczekania po wykonaniu zadania jest banalnie proste 60-(czas trwania zadania). Sprawa nieco komplikuje się, gdy dane zadanie z jakiegoś powodu przekroczy limit jednej minuty. Cykl nie będzie trwał piętnastu minut, a kolejne zadania będą spoźnione względem zaplanowanych przedziałów.
Można temu zaradzić poprzez natychmiastowe wykonanie kolejnego zadania i skrócenie czasu oczekiwania na kolejne zadanie, niezależnie od tego, jak krócej ono trwało względem dopuszcalnych 60 sekund.
Analogicznie postępujemy, gdy krytyczne zadania następują zaraz po sobie, a czasy opóźnień sumują się.
Wszystko jasne - czas wprawić to w ruch
Stworzymy sobie testową, 30-sekundową kolejkę z maksymalnym czasem 5 sekund na pojedyńcze zadanie. Symulacją będzie funkcja randomSleep() zatrzymująca losowo działanie na czas od 1 do 6 sekund, aby sprawdzić ją również w warunkach przekorczenia dopuszczalnego czasu.
<?php
require_once 'fairRefreshQueue.php';
function randomSleep()
{
}
// 30 sekundowa kolejka, maksymalny czas na zadanie 5 sekund
$timeQueue = new FairRefreshQueue(30, 5, true);
for ($i = 1; $i <= $timeQueue->getMaxJobs(); $i++)
{
$timeQueue->addTask('randomSleep');
}
$timeQueue->run();
?>
Wyniki dwóch przebiegów kolejki:
- Start: Sekunda rozpoczęcia wykonywania zadania
- Except: Planowany czas rozpoczęcia wykonywania zadania
- Delay: Opóźnienie względem planowanego czasu rozpoczęcia wykonywania zadania
- Work: Czas wykonywania zadania
- Idle: Czas wolny
- Exceeded: Czas przekroczony powyżej 5 sekund
Job #1, Start: 0.000s, Expect: 0.000s, Delay 0.000s, Work: 1.900s, Idle: 3.100s
Job #2, Start: 5.000s, Expect: 5.000s, Delay 0.000s, Work: 5.300s, Exceeded: 0.300s
Job #3, Start: 10.301s, Expect: 10.000s, Delay 0.301s, Work: 5.500s, Exceeded: 0.500s
Job #4, Start: 15.801s, Expect: 15.000s, Delay 0.801s, Work: 1.400s, Idle: 2.799s
Job #5, Start: 20.000s, Expect: 20.000s, Delay 0.000s, Work: 4.600s, Idle: 0.399s
Job #6, Start: 25.000s, Expect: 25.000s, Delay 0.000s, Work: 3.300s, Idle: 1.700s
Job #1, Start: 30.000s, Expect: 30.000s, Delay 0.000s, Work: 4.400s, Idle: 0.599s
Job #2, Start: 35.000s, Expect: 35.000s, Delay 0.000s, Work: 1.200s, Idle: 3.799s
Job #3, Start: 40.000s, Expect: 40.000s, Delay 0.000s, Work: 2.600s, Idle: 2.399s
Job #4, Start: 45.000s, Expect: 45.000s, Delay 0.000s, Work: 5.700s, Exceeded: 0.700s
Job #5, Start: 50.701s, Expect: 50.000s, Delay 0.701s, Work: 1.900s, Idle: 2.399s
Job #6, Start: 55.000s, Expect: 55.000s, Delay 0.000s, Work: 3.700s, Idle: 1.299s
Jak widać, drugi przebieg cyklu pomimo opóźnień rozpoczął się w planowanym terminie, a wszystkie opóźnienia zostały wyrównane kosztem wolnego czasu pozostałych zadań.
Zobaczmy jeszcze wariant zapchania kolejki, narzucając kolejno czasy:
1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 1, 1, 2 sekundy
Wyniki:
Job #1, Start: 0.000s, Expect: 0.000s, Delay 0.000s, Work: 1.000s, Idle: 4.000s
Job #2, Start: 5.000s, Expect: 5.000s, Delay 0.000s, Work: 2.000s, Idle: 2.999s
Job #3, Start: 10.000s, Expect: 10.000s, Delay 0.000s, Work: 3.000s, Idle: 1.999s
Job #4, Start: 15.000s, Expect: 15.000s, Delay 0.000s, Work: 4.000s, Idle: 0.999s
Job #5, Start: 20.000s, Expect: 20.000s, Delay 0.000s, Work: 5.000s, Exceeded: 0.000s
Job #6, Start: 25.001s, Expect: 25.000s, Delay 0.001s, Work: 6.000s, Exceeded: 1.000s
Job #1, Start: 31.001s, Expect: 30.000s, Delay 1.001s, Work: 7.000s, Exceeded: 2.000s
Job #2, Start: 38.001s, Expect: 35.000s, Delay 3.001s, Work: 8.000s, Exceeded: 3.000s
Job #3, Start: 46.002s, Expect: 40.000s, Delay 6.002s, Work: 7.000s, Exceeded: 2.000s
Job #4, Start: 53.002s, Expect: 45.000s, Delay 8.002s, Work: 6.000s, Exceeded: 1.000s
Job #5, Start: 59.002s, Expect: 50.000s, Delay 9.002s, Work: 5.000s, Exceeded: 0.000s
Job #6, Start: 64.003s, Expect: 55.000s, Delay 9.003s, Work: 4.000s, No idle
Job #1, Start: 68.003s, Expect: 60.000s, Delay 8.003s, Work: 3.000s, No idle
Job #2, Start: 71.003s, Expect: 65.000s, Delay 6.003s, Work: 2.000s, No idle
Job #3, Start: 73.004s, Expect: 70.000s, Delay 3.004s, Work: 1.000s, Idle: 0.996s
Job #4, Start: 75.000s, Expect: 75.000s, Delay 0.000s, Work: 1.000s, Idle: 4.000s
Job #5, Start: 80.000s, Expect: 80.000s, Delay 0.000s, Work: 1.000s, Idle: 4.000s
Job #6, Start: 85.000s, Expect: 85.000s, Delay 0.000s, Work: 2.000s, Idle: 2.999s
Zapychanie kolejki następuje wraz z 6 zadaniem, a opóźnienie nawarstwia się wraz z kolejnymi zadaniami. Kiedy jednak sytuacja się zmienia i pozostaje czas wolny, zostaje on wykorzystany do wyrównania kolejki do pierwotnego stanu.
Podsumowanie
Całkiem możliwe, że wynalazłem koło na nowo. Wychodzę jednak z założenia, że komuś może się ten opis przydać. Ja natomiast miałem wielką frajdę w rozgryzieniu tego problemu samodzielnie :)
Żrodełka do pobrania tutaj: fairrefreshqueue.tar.gz
Skomentuj
Ekspertyza sądowa pamięci BS Sport
unfa / 10 maj 2012 / 11:33
7 dni temu.
Kryminał informatyczny - i to z życia wzięty oraz mający miejsce w polskich realiach! Cud miód! :D A poważniej: nie ...