ciekawy problem do rozwiazania (dlugie)
Masz problem? Zapytaj na forum elektroda.pl
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: ciekawy problem do rozwiazania (dlugie)
Date: Mon, 18 Sep 2000 21:00:02 +0200
Mam problem do rozwiązania. Wydał mi się on na tyle interesujący, że
postanowiłem o nim napisać.
Dotyczy on oprogramowania mikrokontrolera, który odbierane dane z sieci
komputerowej zapamiętuje je i przetwarza.
Odbierane są komunikaty z innych sterowników (powiedzmy ok. 100-200 na
sekundę).
Każdy z nich zawiera 2 bajty danych i identyfikator określający rodzaj
przesyłanych danych (ponad 60000 możliwych rodzajów komunikatów)
1. Komunikaty należy zapamiętać do późniejszego przetworzenia.
2. Odebrane komunikaty ważne są tylko jakiś czas (około 10 sekund)
3. Nowy komunikat musi zastąpić stary o tym samym numerze.
4. Zwykle odbierane jest tylko kilkaset rodzajów komunikatów, ale nie można
przewidzieć które to będą.
5. Sterownik nie dysponuje pamięcią w której możnaby pomieścić wszystkie
możliwe komunikaty.
6. Moc obliczeniowa procesora też nie jest zbyt duża, a do tego wykonuje
dziesiątki innych zadań.
Należy znaleźć metodę zapamiętania odbieranych komunikatów, napisać
procedurę zapisującą odebrany komunikat i
procedurę odczytu ważnych komunikatów o zadanym identyfikatorze.
Mam nadzieję, że problem opisałem dość jasno.
Pozdrawiam, Piotrek
Date: Mon, 18 Sep 2000 21:55:10 +0200
From: "Jacek D." <koperacja_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Czy te komunikaty od sterownikow sa przesylane po I2C ?
Należy znaleźć metodę zapamiętania odbieranych komunikatów,
czy chcesz optymalizowac ilosc pamieci ?
napisać
procedurę zapisującą odebrany komunikat i
procedurę odczytu ważnych komunikatów o zadanym identyfikatorze.
Mam nadzieję, że problem opisałem dość jasno.
ale na czym polega problem ?
Piszesz program, ktory to realizuje.
Ilosc pamieci daj max
a procesor daj szybszy.
Jacek
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Mon, 18 Sep 2000 22:11:32 +0200
Czy te komunikaty od sterownikow sa przesylane po I2C ?
Nie, po magistrali CANBUS
Piszesz program, ktory to realizuje.
Ilosc pamieci daj max
a procesor daj szybszy.
Dzieki za taka rade. Tak naprawde to problem juz dawno rozwiazalem, niestety
sterowniki wymagaja zmudnej konfiguracji i chcialbym tego uniknac.
Wymiana procesora nie wchodzi w gre, jest to SAB80C166 (40MHz)
Ram 128KB+ FLASH 128KB.
Jak latwo policzyc zapamietanie takiej ilosci komunikatow musialoby zajac
minimum
120KB na same dane, a gdzie informacja o czasie waznosci??
Ramu moge poswiecic powiedzny 16KB, wiecej raczej nie.
Problem przedstawilem dlatego, by zaczecic Was do poglowkowania
Cos smutno ostatnio na tych listach.
Przypuszczam, ze moj problem daloby sie rozwiazac stosujac jakies
algorytmy umozliwiajace szybkie przeszukiwanie
Piotr
From: "oberek" <oberek_at_nospam_box43.gnet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Mon, 18 Sep 2000 22:30:52 +0200
"peters" <peters_at_nospam_poczta.onet.pl> wrote in message
news:8q5ssb$sha$1_at_nospam_news.tpi.pl...
Czy te komunikaty od sterownikow sa przesylane po I2C ?
Nie, po magistrali CANBUS
Piszesz program, ktory to realizuje.
Ilosc pamieci daj max
a procesor daj szybszy.
Dzieki za taka rade. Tak naprawde to problem juz dawno rozwiazalem,
niestety
sterowniki wymagaja zmudnej konfiguracji i chcialbym tego uniknac.
Wymiana procesora nie wchodzi w gre, jest to SAB80C166 (40MHz)
Ram 128KB+ FLASH 128KB.
Jak latwo policzyc zapamietanie takiej ilosci komunikatow musialoby zajac
minimum
120KB na same dane, a gdzie informacja o czasie waznosci??
Ramu moge poswiecic powiedzny 16KB, wiecej raczej nie.
Problem przedstawilem dlatego, by zaczecic Was do poglowkowania
Cos smutno ostatnio na tych listach.
RZECZYWISCIE!!! SMUTNO OSTATNIO NA TEJ LIŚCIE BO WIĘCEJ JEST PYTAŃ NIŻ
ODPOWIEDZI :(
Przypuszczam, ze moj problem daloby sie rozwiazac stosujac jakies
algorytmy umozliwiajace szybkie przeszukiwanie
Piotr
From: "Andy" <anok_at_nospam_ceti.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Tue, 19 Sep 2000 01:30:11 +0200
peters napisał(a) w wiadomości: <8q5om9$m1p$1_at_nospam_news.tpi.pl>...
Mam problem do rozwiązania. Wydał mi się on na tyle interesujący, że
postanowiłem o nim napisać.
Dotyczy on oprogramowania mikrokontrolera, który odbierane dane z sieci
komputerowej zapamiętuje je i przetwarza.
Odbierane są komunikaty z innych sterowników (powiedzmy ok. 100-200 na
sekundę).
Każdy z nich zawiera 2 bajty danych i identyfikator określający rodzaj
przesyłanych danych (ponad 60000 możliwych rodzajów komunikatów)
1. Komunikaty należy zapamiętać do późniejszego przetworzenia.
2. Odebrane komunikaty ważne są tylko jakiś czas (około 10 sekund)
...
nie wiem czy dobrze zrozumialem
cos mi sie zdaje, ze w tych zalozeniach czegos brakuje
jesli nie to widze to tak:
np. 200 kom/sek, waznosc 10 sek
czyli w jednym momencie maksymalnie jest
waznych 2000 komunikatow
wiec
mozna je zapamietywac w buforze okreznym
dlugosc komunikatu 2 bajty danych + 2 bajty identyfikator
(mozna rozroznic 65536 komunikatow)
= 4 bajty
wiec wystarczajaca dlugosc bufora 2000 komunikatow x 4 bajty
= 8000 bajtow
a wiec wystarczy 8KB (8192 bajty) na bufor
3. Nowy komunikat musi zastąpić stary o tym samym numerze.
Czy to musi zrobic procedura zapisujaca do bufora ?
Jesli nie to procedura odczytujaca (wyszukujaca) komunikat
w buforze wybierze ten, ktory bedzie nowszy
jesli bufor wyobrazic sobie jako okrag
a index zapisu porusza sie zgodnie z ruchem wskazowek zegara
i w buforze znajdzie sie kilka komunikatow o tym samym
identyfikatorze to najnowszy jest ten, ktory jest najblizej
za indeksem
czyli najblizej indeksu poruszajac sie przeciwnie do ruchu wskazowek
4. Zwykle odbierane jest tylko kilkaset rodzajów komunikatów, ale nie można
przewidzieć które to będą.
5. Sterownik nie dysponuje pamięcią w której możnaby pomieścić wszystkie
możliwe komunikaty.
6. Moc obliczeniowa procesora też nie jest zbyt duża, a do tego wykonuje
dziesiątki innych zadań.
byc moze o czyms zapomnialem
Andrzej
Date: Tue, 19 Sep 2000 01:57:36 +0200
From: "Jacek D." <koperacja_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
(ponad 60000 możliwych rodzajów komunikatów)
jesli bufor wyobrazic sobie jako okrag
a czemu nie jako stos ?
a index zapisu porusza sie zgodnie z ruchem wskazowek zegara
i w buforze znajdzie sie kilka komunikatow o tym samym
identyfikatorze to najnowszy jest ten, ktory jest najblizej
za indeksem
czyli najblizej indeksu poruszajac sie przeciwnie do ruchu wskazowek
ok, bufor ma dlugosc T = 10 + 10 sek.
bufor 10 sek typu stos na wygasajace komunikaty
+ bufor 10 sek typu stos na odliczanie timeoutow
ale moze byc oczywiscie ten okrag.
Troche inteligencji i szybkiego wyszukiwania mozna dodac po
uszczegolowieniu problemu.
Znajomy napisal taki program dla monitoringu kilkudziesieciu centralek
alarmowych.
Kazda wysyla okreslony zbior komunikatow + identyfikacje.
Monitoring czyta te komunikaty, archiwizuje i weryfikuje
a gdy otrzymuje sygnal alarmu to raz jeszcze odpytuje centralke
i podejmuje czynnosci przewidziane procedura obslugi zdarzenia.
Jacek
From: jfox_at_nospam_friko6.onet.pl (J.F.)
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: 19 Sep 2000 15:10:47 GMT
On Tue, 19 Sep 2000 01:57:36 +0200, Jacek D. <koperacja_at_nospam_poczta.onet.pl> wrote:
(ponad 60000 możliwych rodzajów komunikatów)
jesli bufor wyobrazic sobie jako okrag
a czemu nie jako stos ?
Bo stos jest niewygodny jesli chodzi o usuwanie starych :-)
J.
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Tue, 19 Sep 2000 17:54:30 +0200
Bo stos jest niewygodny jesli chodzi o usuwanie starych :-)
Dokladnie tak :) Nie napisalem przeciez, ze wszystkie komunikaty zostana
pobrane
przez procedure odczytu. Znaczna ich czesc moze w ogole nie byc
wykorzystana.
Piotr
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Tue, 19 Sep 2000 17:19:27 +0200
Niestety nie takie to proste na jakie wyglada.
1. Juz problemem jest obliczanie samych timeoutow.
Nasuwaja mi sie dwie metody. W pierwszej mozemy razem z danymi zapamietywac
czas ich nadejscia, powiedzmy w ms od startu systemu. Procedura odczytu
ignorowalaby
starsze dane. Co jednak będzie, gdy licznik się przepełni? Zbyt długi
zajmuje pamięć.
Można wszystkie dane zaopatrzyć w pola odliczania czasu, których wartość w
osobnym wštku będzie się
zmniejszać do zera (0=timeout).
2. System powinien zachowac sie dobrze w przypadku gdy jedno z urzadzen
przysle mu duzo komunikatow jednego typu. Jesli bedzie sie je zapamietywało
jak leca, to zabraknie pamieci dla innych komunikatow.
Rozsadnym rozwiazaniem byloby od razu zastepowanie nieaktualnych
komunikatow.
3. Przeszukiwanie calej pamieci przez procedure zapisu lub odczytu jest zbyt
kosztowne czasowo.
Potrzeba jakiegos sprytnego mechanizmu wspomagajšcego dotarcie do
poszukiwanych danych.
Piotr
Date: Tue, 19 Sep 2000 21:59:45 +0200
From: "Jacek D." <koperacja_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Potrzeba jakiegos sprytnego mechanizmu wspomagajšcego dotarcie do
poszukiwanych danych.
To moze wrocmy do konkretow.
Ten kto ma ten problem niech go dokladniej opisze i skonkretyzuje
a rozwiazanie zrobimy na liscie.
Chyba ze to teoretyczny problem w stylu.
Komunikatow milion
Urzadzen milion
A jedno urzadzenie moze wysylac na sekunde 100.000
a pamieci tyle co kot naplakal, a procesor wolniutki.
Przeciez sa jakies warunki brzegowe i skoro pamieci za malo, procesor za
wolny, algorytm wyszkiwania i deletowania timeoutow niewydajny,
to znaczy ze problem jest realny
i chetnie go rozwiaze, gdy otrzymam wiecej konkretow i cos na zachete
;-)
Jacek
From: jfox_at_nospam_friko6.onet.pl (J.F.)
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Tue, 19 Sep 2000 19:20:26 GMT
On Mon, 18 Sep 2000 21:00:02 +0200, peters wrote:
Odbierane są komunikaty z innych sterowników (powiedzmy ok. 100-200/s) [...]
Innymi slowy masz problem z baz danych :-)
Propozycja 1 - klasyczny bufor kolowy. Proste zapisywanie, proste
usuwanie przestarzalych, nie ma zastepowania starego nowym - ale
to wydaje sie niekonieczne, pracochlonne wyszukiwanie.
Jesli wyszukiwanie nie przeszkadza - uznac za zrobione :-)
A jesli nie - to cie czeka analiza i kombinowanie znanych rozwiazan
-)
Kilkanascie buforow kolowych i rozrzut pomiedzy nie funkcja haszujaca
wydaje sie dosc dobrym pomyslem.
J.
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Tue, 19 Sep 2000 21:45:41 +0200
Propozycja 1 - klasyczny bufor kolowy. Proste zapisywanie, proste
usuwanie przestarzalych, nie ma zastepowania starego nowym - ale
to wydaje sie niekonieczne, pracochlonne wyszukiwanie.
Jesli wyszukiwanie nie przeszkadza - uznac za zrobione :-)
Oczywiście jest to rozwiązanie nie do przyjęcia.
Kilkanascie buforow kolowych i rozrzut pomiedzy nie funkcja haszujaca
wydaje sie dosc dobrym pomyslem.
Nie znam terminologii informatycznej. Czy mam rozumieć, że powinienem
pogrupować przychodzące komunikaty w grupy tak dobrane by w miarę
równomiernie wypełniacz bufory kolowe?
Jesli Cie dobrze zrozumialem, to pomysl wart jest przemyslenia.
Co bedzie jak zle podziele na grupy? Czy mozna dzielic na grupy
automatycznie?
Piotr
Date: Tue, 19 Sep 2000 22:03:29 +0200
From: "Jacek D." <koperacja_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Jesli Cie dobrze zrozumialem, to pomysl wart jest przemyslenia.
Co bedzie jak zle podziele na grupy? Czy mozna dzielic na grupy
automatycznie?
Nic nie bedzie dopoki nie podasz konkretow.
Skoncz z abstrakcja.
Bo opis problemu jest taki,
ze w miejscie jest kilka skrzyzowan a po drodze A do B w chwili T
moze przejezdac do 20 samochodow, ale moze i wiecej a moze i 1000
ale wlasnie 1000 nie moze bo droga ich nie pomiesci, chyba ze pojada z
predkoscia 1000 km/godz.
Tak wiec jedynie ty znasz warunkibrzegowe i graniczne
i jak je podasz to problem zostanie prosto rozwiazany.
Jacek
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Tue, 19 Sep 2000 22:42:38 +0200
Nic nie bedzie dopoki nie podasz konkretow.
Skoncz z abstrakcja.
Juz wyjasniam.
Problem nie jest abstrakcyjny.
Pojedynczy sterownik zbudowany jest na procesorze SAB80C166,128KB RAM +
128KBFLASH,
posiada kilkadziesiat wejsc-wyjsc i realizuje skomplikowany algorytm
sterowania.
Sterowniki pracuja w sieci opartej na magistrali CANBUS.
Kazdy sterownik posiada swoj numer 1..240 i moze wysylac na magistrale do
256 rodzajow komunikatow
o swoim stanie (zaleznie od konfiguracji).
Inne sterowniki odbieraja te komunikaty, czesc z nich wykorzystuja we
wlasnym programie,
czesc z nich jest retransmitowana przez RS232 do innych urzadzen.
Rozwiazanie obecne wymaga wypelniania tabeli rezerwujacej pamiec na
komunikaty od poszczegolnych sterownikow. W kolejnych wersjach
oprogramowania chcialbym tego uniknac.
W tej chwili wykorzystuje pamiec na max. 1024 komunikaty i niechcialbym tej
pamieci zwiekszac.
Mam nadzieje, ze troche lepiej naswietlilem problem
Piotr
Date: Tue, 19 Sep 2000 22:53:22 +0200
From: "Jacek D." <koperacja_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
W tej chwili wykorzystuje pamiec na max. 1024 komunikaty i niechcialbym tej
pamieci zwiekszac.
Czyli jednak znasz te warunki brzegowe i wiesz, ze
komunikatow bedzie nie wiecej niz 1024 w ciagu 10 sekund.
Jacek
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Tue, 19 Sep 2000 23:05:33 +0200
Czyli jednak znasz te warunki brzegowe i wiesz, ze
komunikatow bedzie nie wiecej niz 1024 w ciagu 10 sekund.
Nie, to nie tak. W tej chwili przechowuje komunikaty statycznie w tabeli.
Kazdy komunikat na swoim miejscu. Zakladam np, ze sterownik nr 1 wysyla
komunikaty 0..9
(rezerwuje na sztywno 10 miejsc w pamieci), sterownik 2 wysyla 1 komunikat,
itd..
Projektujac konkretna aplikacje wiem co i w jakich ilosciach bede wysylal,
ale konfiguracja jest pracochlonna.
Liczba 1024 nie ma nic wspolnego z szyboscia z jaka odbieram komunikaty.
Piotr
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Wed, 20 Sep 2000 15:47:23 +0200
Czyli jednak znasz te warunki brzegowe i wiesz, ze
komunikatow bedzie nie wiecej niz 1024 w ciagu 10 sekund.
Czy Jacek D. to przypadkiem nie Expert? :))
From: jfox_at_nospam_friko6.onet.pl (J.F.)
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: 22 Sep 2000 09:01:31 GMT
On Tue, 19 Sep 2000 22:42:38 +0200, peters <peters_at_nospam_poczta.onet.pl> wrote:
Juz wyjasniam. Problem nie jest abstrakcyjny.
Pojedynczy sterownik zbudowany jest na procesorze SAB80C166,128KB RAM +
128KBFLASH,
posiada kilkadziesiat wejsc-wyjsc i realizuje skomplikowany algorytm
sterowania. Sterowniki pracuja w sieci opartej na magistrali CANBUS.
Kazdy sterownik posiada swoj numer 1..240 i moze wysylac na magistrale do
256 rodzajow komunikatow o swoim stanie (zaleznie od konfiguracji).
Hm, jak na moj gust, to jesli on czyms steruje to musi wiedziec
czym i na czym sie opierac. Musisz wiec dokladnie skonfigurowac
jakie zdarzenia cie interesuja, a ktore ignorujesz.
No chyba ze to jakis logger, albo na wypadek zmiany w programie chcesz
znac stan biezacy nowo obslugiwanych urzadzen.
Poza tym zachodzi pytanie jaki jest algorytm sterowania.
Dosc naturalne wydaje sie reagowanie na komunikat w momencie jego
nadejscia. No chyba ze masz procedure sterowania odpalana cyklicznie
w petli/przerwaniu i ona korzysta z zapamietanego stanu urzadzenia.
Wtedy z kolei mozesz okreslic czy i ile mocy obliczeniowej Ci brakuje ..
Rozwiazanie obecne wymaga wypelniania tabeli rezerwujacej pamiec na
komunikaty od poszczegolnych sterownikow. W kolejnych wersjach
oprogramowania chcialbym tego uniknac.
W tej chwili wykorzystuje pamiec na max. 1024 komunikaty i niechcialbym tej
pamieci zwiekszac.
Zaraz zaraz - tak czy inaczej potrzebujesz pamiec na te dane. Moze mniej,
moze wiecej, ale potrzebujesz.
Mam nadzieje, ze troche lepiej naswietlilem problem
Nie do konca :-)
Rozumiem ze przyjscie danego komunikatu uniewaznia stary.
A jak jest z czasem "przeterminowania" komunikatu? Trzeba je kasowac
po pewnym czasie, czy urzadzenie jak juz wysyla to wysyla je cyklicznie
[komunikat jest typu "stan papieru w drukarce: jest" rozsylany co 5s,
czy jednorazowy "zabraklo papieru" ? ]
J.
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Fri, 22 Sep 2000 11:39:25 +0200
Hm, jak na moj gust, to jesli on czyms steruje to musi wiedziec
czym i na czym sie opierac. Musisz wiec dokladnie skonfigurowac
jakie zdarzenia cie interesuja, a ktore ignorujesz.
To prawda. Jak steruje, to wiem co mi jest potrzebne. Ale gdy dolacze
przez port szeregowy komputer, ktory pyta o zapamietane dane to musze
miec w pamieci wszystkie, ktore przychodza.
No chyba ze masz procedure sterowania odpalana cyklicznie
w petli/przerwaniu i ona korzysta z zapamietanego stanu urzadzenia.
Wtedy z kolei mozesz okreslic czy i ile mocy obliczeniowej Ci brakuje ..
To rodzaj sterownika swobodnie programowalnego.
Im mniej mocy procesora wykorzystam na takie sprawy jak odbior komunikatow
tym bardziej skomplikowane zadania bedzie mozna w nim zaprogramowac.
Rozumiem ze przyjscie danego komunikatu uniewaznia stary.
A jak jest z czasem "przeterminowania" komunikatu? Trzeba je kasowac
po pewnym czasie, czy urzadzenie jak juz wysyla to wysyla je cyklicznie
[komunikat jest typu "stan papieru w drukarce: jest" rozsylany co 5s,
czy jednorazowy "zabraklo papieru" ? ]
Komunikaty sa wysylane caly czas. Jak dane urzadzenie ma wysylac 10 to
wysyla
je na okraglo tylko w miare powoli. Jak cos sie zmieni to wysyla komunikat
natychmiast.
Ufff, skomplikowany problem i trudno od razu wszystko wyjasnic
Piotr
From: jfox_at_nospam_friko6.onet.pl (J.F.)
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Thu, 21 Sep 2000 19:38:13 GMT
On Tue, 19 Sep 2000 21:45:41 +0200, peters wrote:
Propozycja 1 - klasyczny bufor kolowy. Proste zapisywanie, proste
usuwanie przestarzalych, nie ma zastepowania starego nowym - ale
to wydaje sie niekonieczne, pracochlonne wyszukiwanie.
Jesli wyszukiwanie nie przeszkadza - uznac za zrobione :-)
Oczywiście jest to rozwiązanie nie do przyjęcia.
O - nie znam docelowego zastosowania [zdanie egzaminu ? ],
ale nie szafowalbym tym "nie do przyjecia". Moze wyszukiwanie wcale
nie jest takie czeste i moze byc pracochlonne? Moze procesorka starczy
na to wyszukiwanie..
Kilkanascie buforow kolowych i rozrzut pomiedzy nie funkcja haszujaca
wydaje sie dosc dobrym pomyslem.
Czy mam rozumieć, że powinienem pogrupować przychodzące komunikaty w grupy tak
dobrane by w miarę równomiernie wypełniacz bufory kolowe?
Dokladnie o to chodzi. Jako ze bufory krotsze to i wyszukianie w
jednym z nich szybsze ..
Co bedzie jak zle podziele na grupy?
No coz - w jednych grupach bedziesz pamietal godziny danych, a w
innych moze nawet sekunda sie nie zmiesci ..
Czy mozna dzielic na grupy automatycznie?
To jest wlasnie zadanie funkcji haszujacej. Na podstawie
identyfikatora komunikatu musi wyliczyc ona nr grupy - na tyle przy
tym "chaotycznie" zeby jak najrownomierniej rozrzucic.
Prostym typem moze byc np wziasc reszte z dzielenia identyfikatora
przez np 13 [wlasnie pierwsza, a nie 10 czy 16]. Ktokolwiek tam
przydziela identyfikatory ma pewnie jakies zasady i przydziela
seriami, np 100, 101, 102, 200, 201, 202, 300, ... czy
110, 120, 510,520, 530, 1010, ... a modulo 13 ladnie to podzieli na 13
kupek ..
J.
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Thu, 21 Sep 2000 21:55:53 +0200
Propozycja 1 - klasyczny bufor kolowy. Proste zapisywanie, proste
Oczywiście jest to rozwiązanie nie do przyjęcia.
O - nie znam docelowego zastosowania [zdanie egzaminu ? ],
ale nie szafowalbym tym "nie do przyjecia". Moze wyszukiwanie wcale
nie jest takie czeste i moze byc pracochlonne? Moze procesorka starczy
na to wyszukiwanie..
Juz napsalem nieco o zastosowaniu tego sterownika. Problem moze faktycznie
wygladac na czysto teoretyczny, ale setki pracujacych juz urzadzen to nie
teoria :)
Kilkanascie buforow kolowych i rozrzut pomiedzy nie funkcja haszujaca
wydaje sie dosc dobrym pomyslem.
Pomysl mi sie na poczatku spodobal, ale potem zmienilem zdanie.
Po co stosowac w ogole jakies bufory okrezne? To tylko strata pamieci.
Chyba zdecydowanie lepiej bedzie jak funkcja mieszajaca od razu wskaze
pojedyncza komorke do zapisu komunikatu. A gdy ona bedzie juz zajeta mozna
zastosowac algorytm, ktory bedzie probowal zapisywac do innych komorek.
Majac pewne dane o przychodzacych komunikatach mozna to rozwiazanie
zasymulowac najpierw na PCcie
Piotr
P.S. Co myslicie o zastosowaniu drzewa do przechowywania komunikatow?
From: jfox_at_nospam_friko6.onet.pl (J.F.)
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: 22 Sep 2000 10:04:42 GMT
On Thu, 21 Sep 2000 21:55:53 +0200, peters <peters_at_nospam_poczta.onet.pl> wrote:
Kilkanascie buforow kolowych i rozrzut pomiedzy nie funkcja haszujaca
wydaje sie dosc dobrym pomyslem.
Pomysl mi sie na poczatku spodobal, ale potem zmienilem zdanie.
Po co stosowac w ogole jakies bufory okrezne? To tylko strata pamieci.
Ale wtedy w naturalny sposob masz zrealizowane usuwanie starych komunikatow.
Poza tym strata pamieci nie jest wcale taka duza - no chyba ze tobie
komunikat sie uniewaznia zaraz jak nadejdzie jego nowa tresc, a predkosc
rozsylania jest rozna. O ile dobrze zrozumialem to u ciebie tak niestety
jest?
Chyba zdecydowanie lepiej bedzie jak funkcja mieszajaca od razu wskaze
pojedyncza komorke do zapisu komunikatu. A gdy ona bedzie juz zajeta mozna
zastosowac algorytm, ktory bedzie probowal zapisywac do innych komorek.
Tak - jesli problem masz taki jak powyzej to byloby to sensowniejsze.
Tylko jest jeden malutki problemik do przemyslenia - ile jest tych
alternatywnych lokalizacji, bo troche ich musi byc zeby uchronic
sie od zajetosci, a z drugiej strony zeby zatrzymac przeszukiwanie
nieistniejacego po jakims sensownym czasie - no chyba ze jak piszesz
jest to zjawisko rzadkie.
Nastepny problem to usuwanie przestarzalych - znow trzeba jakis czas
nadejscia pamietac, co pewien czas wszystkie przelatywac i
zaznaczac jako puste.
Przy tych zalozeniach to koncepcja drzewa nie jest taka zla, i warta
przemyslenia. A moze podejsc do problemu najzupelniej klasycznie: listy ?
Urzadzen masz do 240. Jedna tablica wskaznikow z pozycja dla kazdego
urzadzenia [tu ewentualnie tablice mozna mniejsza i zapamietywac tylko
obslugiwane urzadzenia, albo i ja zrealizowac lista, drzewem ].
Wskaznik wskazuje pierwszy komunikat z listy, ten nastepny
itd. Przy kilkunastu komunikatach na sterownik wyszukiwanie bedzie
blyskawiczne - tyle ze tracisz dodatkowe dwa bajty na adres nastepnego ...
w zasadzie to nawet jeden bajt - z komunikatu mozesz nr urzadzenia
usunac. A jesli zmieniajac tresc przestawisz komunikat na pierwsze miejsce
na liscie - to i latwo znalezc przestarzale..
J.
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Fri, 22 Sep 2000 12:25:21 +0200
Ale wtedy w naturalny sposob masz zrealizowane usuwanie starych
komunikatow.
Poza tym strata pamieci nie jest wcale taka duza - no chyba ze tobie
komunikat sie uniewaznia zaraz jak nadejdzie jego nowa tresc, a predkosc
rozsylania jest rozna. O ile dobrze zrozumialem to u ciebie tak niestety
jest?
Komunikat stary jest zastrepowany nowym, Po 10 sekundach gdy nie nadejdzie
nowy
stary tez traci waznosc
Przy tych zalozeniach to koncepcja drzewa nie jest taka zla, i warta
przemyslenia. A moze podejsc do problemu najzupelniej klasycznie: listy ?
Urzadzen masz do 240. Jedna tablica wskaznikow z pozycja dla kazdego
urzadzenia [tu ewentualnie tablice mozna mniejsza i zapamietywac tylko
obslugiwane urzadzenia, albo i ja zrealizowac lista, drzewem ].
Wskaznik wskazuje pierwszy komunikat z listy, ten nastepny
itd. Przy kilkunastu komunikatach na sterownik wyszukiwanie bedzie
blyskawiczne - tyle ze tracisz dodatkowe dwa bajty na adres nastepnego ...
w zasadzie to nawet jeden bajt - z komunikatu mozesz nr urzadzenia
usunac. A jesli zmieniajac tresc przestawisz komunikat na pierwsze miejsce
na liscie - to i latwo znalezc przestarzale..
J.
Myslalem juz o tym, ale jest jeden problem. Fragmentacja pamieci :))
Nalezaloby opracowac procedure, ktora usuwa dziury po niewaznych
komunikatach i przesuwa wszystko do gory. Chyba, ze bedziemy martwic sie
o to dopiero po nadejsciu komunikatu, ktorego jeszcze nigdy nie bylo
i bedziemy przeszukiwac wtedy cala tablice by odnalezc pierwsze wolne
miejsce.
Piotr
From: Ireneusz Niemczyk <i.niemczyk_at_nospam_multispedytor.com.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Wed, 20 Sep 2000 10:14:33 +0200
Kilkanascie buforow kolowych i rozrzut pomiedzy nie funkcja haszujaca
wydaje sie dosc dobrym pomyslem.
J.
Auć......max 16k ramu i do tego f#.....? to będzie boleć....(przy dezynsekcji)
;)
--
PZD, Irek.N. (ALIAS)
From: Jacek Niezgoda <jacek_at_nospam_pegaz.bptnet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Wed, 20 Sep 2000 14:56:12 +0200
Wiadomość napisana przez: peters:
Mam problem do rozwiązania. Wydał mi się on na tyle interesujący, że
postanowiłem o nim napisać.
Dotyczy on oprogramowania mikrokontrolera, który odbierane dane z sieci
komputerowej zapamiętuje je i przetwarza.
Odbierane są komunikaty z innych sterowników (powiedzmy ok. 100-200 na
sekundę).
Każdy z nich zawiera 2 bajty danych i identyfikator określający rodzaj
przesyłanych danych (ponad 60000 możliwych rodzajów komunikatów)
1. Komunikaty należy zapamiętać do późniejszego przetworzenia.
2. Odebrane komunikaty ważne są tylko jakiś czas (około 10 sekund)
3. Nowy komunikat musi zastąpić stary o tym samym numerze.
4. Zwykle odbierane jest tylko kilkaset rodzajów komunikatów, ale nie można
przewidzieć które to będą.
5. Sterownik nie dysponuje pamięcią w której możnaby pomieścić wszystkie
możliwe komunikaty.
6. Moc obliczeniowa procesora też nie jest zbyt duża, a do tego wykonuje
dziesiątki innych zadań.
Należy znaleźć metodę zapamiętania odbieranych komunikatów, napisać
procedurę zapisującą odebrany komunikat i
procedurę odczytu ważnych komunikatów o zadanym identyfikatorze.
Ciekawy problem, który można uogólnić i sprowadzić do problemu programów, które
mają do dyspozycji mało pamięci i mało czasu (wolny procesor). Swego czasu
ukazała się na rynku bardzo ciekawa książka pt. "Perełki oprogramowania"
pokazująca, że problem trywialny przestaje takim być gdy brakuje pamięci i
czasu. Są też przykłady jak można sobie z tym poradzić (algorytmy, algorytmy,
algorytmy).
Szczerze polecam tę lekturę.
Jacek Niezgoda
From: "Bartek Dajewski" <bartek_at_nospam_tradiss.com.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Wed, 20 Sep 2000 17:08:51 +0200
Cześć,
peters napisał(a) w wiadomości: <8q5om9$m1p$1_at_nospam_news.tpi.pl>...
[...]
Odbierane są komunikaty z innych sterowników (powiedzmy ok. 100-200 na
sekundę).
Każdy z nich zawiera 2 bajty danych i identyfikator określający rodzaj
przesyłanych danych (ponad 60000 możliwych rodzajów komunikatów)
1. Komunikaty należy zapamiętać do późniejszego przetworzenia.
2. Odebrane komunikaty ważne są tylko jakiś czas (około 10 sekund)
3. Nowy komunikat musi zastąpić stary o tym samym numerze.
4. Zwykle odbierane jest tylko kilkaset rodzajów komunikatów, ale nie można
przewidzieć które to będą.
5. Sterownik nie dysponuje pamięcią w której możnaby pomieścić wszystkie
możliwe komunikaty.
6. Moc obliczeniowa procesora też nie jest zbyt duża, a do tego wykonuje
dziesiątki innych zadań.
Moim zdaniem masz dwa wyjścia: bufor cykliczny i wszystkie komunikaty (tak
jak pisał Andy) albo funkcja haszująca (patrz list J.F.). Prostsze w
realizacji jest pierwsze rozwiązanie.
Długotrwałe wyszukiwanie? Chyba nie, skoro masz 80186/40MHz to jesteś w
stanie ca. 13 tys razy przeszukać całą tablicę komunikatów w ciągu sekundy
(w przypadku pesymistycznym; średnio dwa razy tyle przy pełnym buforze).
Wszystko zależy od tego jak często będziesz odszukiwał komunikaty.
Timeout? Zapamiętuj czas w sekundach a nie w ms - wtedy wystarczy Ci
jeden bajt i problemu nie ma. Nie zmniejszaj wszystkich czasów w osobnym
wątku! Po prostu po odnalezieniu komunikatu sprawdź, czy bieżący_czas -
czas_komunikatu <= 10. "Przekręcenie licznika" nie wpłynie na wynik.
Przykład: powiedzmy, że komunikad przyszedł w 252 sekundzie, a sprawdzasz go
8 sekund póżniej, czyli w 260 sekundzie od staru systemu. Wtedy
czas_komunikatu = 252 a beżący_czas = 4 (260 modulo 256). Z odejmowania 4 -
252 wyjdzie Ci 8, bo -248 zapisane na jednym bajcie daje właśnie 8.
Piszesz, że nie pomieszczą się wszystkie komunikaty, ale mnie (i
Andy'emu też) wychodzi inaczej. Jeżeli rzeczywiście jest ich 100-200/sek to
muszą się pomieścić. Jeden komunikat = 5 bajtów (dwa bajty na dane, dwa na
ID i jeden na czas) czyli 10000 bajtów = jest OK ("Ramu moge poswiecic
powiedzmy 16KB").
Metoda z funkcją mieszającą da Ci prawdopodobnie lepsze wykorzystanie
czasu i pamięci, ale program jest znacznie bardziej skomplikowany. Musisz
przewidzieć sytuację, że funkcja zwróci Ci adres komórki już zajętej a
jeszcze nie nadającej się do ponownego wykorzystania.
---
Pdozdrawiam :-)
Bartek
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Wed, 20 Sep 2000 19:01:59 +0200
Moim zdaniem masz dwa wyjścia: bufor cykliczny i wszystkie komunikaty (tak
jak pisał Andy) albo funkcja haszująca (patrz list J.F.). Prostsze w
realizacji jest pierwsze rozwiązanie.
Długotrwałe wyszukiwanie? Chyba nie, skoro masz 80186/40MHz to jesteś
w
stanie ca. 13 tys razy przeszukać całą tablicę komunikatów w ciągu sekundy
(w przypadku pesymistycznym; średnio dwa razy tyle przy pełnym buforze).
Wszystko zależy od tego jak często będziesz odszukiwał komunikaty.
Mam procesor 166 a nie 186. Jak juz napisalem system jednoczesnie musi
sterowac
roznymi urzadzeniami w czsie rzeczywistym. Jesli przyjmiemy, ze czas
potrzebny
na przeszukanie jednej komorki tablicy wynosi 1 mikrosekunde to przeszukanie
calej
tablicy (1000 elementow) zajmie az 1 ms. Juz sam odczyt kilkuset
komunikatow
w ciagu sekundy moze pochlonac 20% czasu procesora!!!
Timeout? Zapamiętuj czas w sekundach a nie w ms - wtedy wystarczy Ci
jeden bajt i problemu nie ma. Nie zmniejszaj wszystkich czasów w osobnym
wątku! Po prostu po odnalezieniu komunikatu sprawdź, czy bieżący_czas -
czas_komunikatu <= 10. "Przekręcenie licznika" nie wpłynie na wynik.
Przykład: powiedzmy, że komunikad przyszedł w 252 sekundzie, a sprawdzasz
go
8 sekund póżniej, czyli w 260 sekundzie od staru systemu. Wtedy
czas_komunikatu = 252 a beżący_czas = 4 (260 modulo 256). Z odejmowania
4 -
252 wyjdzie Ci 8, bo -248 zapisane na jednym bajcie daje właśnie 8.
Nie do konca tak. Jesli przyjmiemy, ze nie zastepujemy w buforze starych
komunikatow
a dopisujemy nowe, to co sie stanie gdy przyjda dwa komunikaty o tym samym
identyfikatorze,
o roznej tresci, ale w tej samej sekundzie? Skad procedura odczytu bedzie
wiedziala ktory wybrac?
Ponadto pamietanie czasu przyjscia komunikatu wymusza napisanie chodzacej w
osobnym watku
procedury uniewazniania komunikatow. W przeciwnym razie komunikat, ktorego
nie odczytano
po 256 sekundach znow stalby sie wazny :)) Ale taka procedura to zaden
problem, bo wywolywana
nawet co kilkadziesiat sekund
Piszesz, że nie pomieszczą się wszystkie komunikaty, ale mnie (i
Andy'emu też) wychodzi inaczej. Jeżeli rzeczywiście jest ich 100-200/sek
to
muszą się pomieścić. Jeden komunikat = 5 bajtów (dwa bajty na dane, dwa na
ID i jeden na czas) czyli 10000 bajtów = jest OK ("Ramu moge poswiecic
powiedzmy 16KB").
W normalnych warunkach istotnie powinny sie miescic. Ale co bedzie jak
ktores z urzadzen
zglupieje i zacznie nadawac komunikaty czesciej? (nie napisalem, ze podczas
zmiany stanu
wysylane sa komunikaty poza kolejnoscia) Wtedy caly bufor zapelnilby sie
niewaznymi
komunikatami od jednego sterownika
Metoda z funkcją mieszającą da Ci prawdopodobnie lepsze wykorzystanie
czasu i pamięci, ale program jest znacznie bardziej skomplikowany. Musisz
przewidzieć sytuację, że funkcja zwróci Ci adres komórki już zajętej a
jeszcze nie nadającej się do ponownego wykorzystania.
Czy moglbys w kilku zdaniach opisac ta metode? Nie jestem informatykiem.
Piotr
From: "Bartek Dajewski" <bartek_at_nospam_tradiss.com.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Thu, 21 Sep 2000 14:05:34 +0200
Cześć,
peters napisał(a) w wiadomości: <8qaqh0$cac$1_at_nospam_news.tpi.pl>...
[...]
Mam procesor 166 a nie 186.
Fakt - moja pomyłka.
[...]
przeszukanie jednej komorki tablicy wynosi 1 mikrosekunde to przeszukanie
calej
tablicy (1000 elementow) zajmie az 1 ms. Juz sam odczyt kilkuset
komunikatow
w ciagu sekundy moze pochlonac 20% czasu procesora!!!
Chyba czegoś nie zrozumiałem. Cała tablica powinna mieć 2000 a nie 1000
komórek. Co prawda średni czas odczytu (odnalezienia komunikatu) będzie na
pewno mniejszy niż 2ms i można go (moim zdaniem) ostrożnie oszacować na
połowę tego czasu czyli 1ms.
Timeout? Zapamiętuj czas w sekundach a nie w ms - wtedy wystarczy Ci
jeden bajt i problemu nie ma.
[...]
Nie do konca tak. Jesli przyjmiemy, ze nie zastepujemy w buforze starych
komunikatow
a dopisujemy nowe, to co sie stanie gdy przyjda dwa komunikaty o tym samym
identyfikatorze,
o roznej tresci, ale w tej samej sekundzie? Skad procedura odczytu bedzie
wiedziala ktory wybrac?
Ostatni czyli znajdujący się "bliżej" aktualnego końca bufora. Wystarczy
przeszukiwać bufor od najnowszych do najstarszych - pierwszy znaleziony jest
właściwy, pod warunkiem, że nie jest "za stary".
Ponadto pamietanie czasu przyjscia komunikatu wymusza napisanie chodzacej w
osobnym watku
procedury uniewazniania komunikatow. W przeciwnym razie komunikat, ktorego
nie odczytano
po 256 sekundach znow stalby sie wazny :))
Zaraz, zaraz. Jak to po 256 sekundach?! Przecież po takim czasie komunikat
zostanie dawno zamazany przez następne. Napisałeś, że jest ich 100-200/sek,
więc przy buforze na 2000 komunikatów czas życia każdego z nich jest od 10
do 20 sekund. Żeby jakiś komunikat przetrwał dłużej niż 256 sekund, ich
częstość musiałaby spaść poniżej 8/sek.
Ale taka procedura to zaden
problem, bo wywolywana
nawet co kilkadziesiat sekund
Prawda.
muszą się pomieścić. Jeden komunikat = 5 bajtów (dwa bajty na dane, [...]
W normalnych warunkach istotnie powinny sie miescic. Ale co bedzie jak
ktores z urzadzen
zglupieje i zacznie nadawac komunikaty czesciej? (nie napisalem, ze podczas
zmiany stanu
wysylane sa komunikaty poza kolejnoscia) Wtedy caly bufor zapelnilby sie
niewaznymi
komunikatami od jednego sterownika
To zmienia założenia (100-200/sek). Może da się jakoś szybko wykryć, że
urządzenie zgłupiało i w ogóle ignorować komunikaty od niego.
Metoda z funkcją mieszającą da Ci prawdopodobnie lepsze wykorzystanie
czasu i pamięci, ale program jest znacznie bardziej skomplikowany. Musisz
przewidzieć sytuację, że funkcja zwróci Ci adres komórki już zajętej a
jeszcze nie nadającej się do ponownego wykorzystania.
Czy moglbys w kilku zdaniach opisac ta metode? Nie jestem informatykiem.
Funkcja mieszająca (albo inaczej haszująca) to takie coś, co z liczby
wejściowej mieszczącej się np. w dużym zakresie da Ci liczbę należącą do
mniejszego zakresu. Nie ma uniwersalnej metody tworzenia takich funkcji.
Ogólnie chodzi o to, żeby rezultat funkcji dał jak największy "rozrzut",
czyli, żeby prawdopodobieństwo otrzymania tego samego rezultatu dla różnych
danych wejściowych było jak najmniejsze. Jak z tego widać, treść dobrze
dobranej funkcji musi zależeć od rozkładu danych wejściowych, ale można dość
dobre rezultaty osiągnąć dla przypadku ogólnego. Najprostsza funkcja dla
Twojego problemu to może być np. xor starszego i młodszego bajtu
identyfikatora komunikatu. W efekcie otrzymujesz jednobajtowy adres komórki,
pod który trzeba spróbować zapisać komunikat. Spróbować, bo najpierw musisz
sprawdzić, czy komórka nie jest zajęta przez inny komunikat, który też "ma
do niej prawo". Jeżeli tak, to umieszczasz komunikat np. w osobnym buforze,
w którym nie obowiązuje już funkcja mieszająca. Przy udanym dobraniu funkcji
wielkość tego bufora będzie nieduża, więc i wyszukiwanie w nim wystarczająco
szybkie.
Nie mam wielkiego doświadczenia w dobieraniu funkcji mieszających, ale
jak opiszesz różne możliwe zakresy adresów sterowników i numerów
komunikatów, które w praktyce mogą się zdarzać, to spróbuję coś wykombinować
(albo ktoś inny - o większym doświadczeniu).
---
Pozdrawiam :-)
Bartek
From: "Bartek Dajewski" <bartek_at_nospam_tradiss.com.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Thu, 21 Sep 2000 14:58:17 +0200
Cześć,
peters napisał(a) w wiadomości: <8qaqh0$cac$1_at_nospam_news.tpi.pl>...
Metoda z funkcją mieszającą da Ci prawdopodobnie lepsze
wykorzystanie
Czy moglbys w kilku zdaniach opisac ta metode? Nie jestem informatykiem.
Zobacz też:
(adresy wpisane w kolejności odnajdywania, a więc przypadkowej)
<http://pckurier.pl/praxis/artykuly/grubicki_piotr/tablice/>
<http://www.autoobjects.com/Home/Teaching/CmpE_126 CmpE126_Lectures/Hashing
/hashing.html>
<http://www.dei.unipd.it/~melo/bible/concepts/documents/Hash_addressing.html
<http://www.dei.unipd.it/~melo/bible/concepts/documents/Collision_handling_m
ethods.html>
<http://hissa.nist.gov/dads/HTML/hashtab.html>
lub ogólnie: poszukaj hasła "funkcja mieszająca" albo "hashing table",
"hashing function". Znajdziesz dużo - jest co czytać. Zwróć uwagę na problem
kolizji.
---
Pozdrawiam :-)
Bartek
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Thu, 21 Sep 2000 15:20:52 +0200
Chyba czegoś nie zrozumiałem. Cała tablica powinna mieć 2000 a nie 1000
komórek. Co prawda średni czas odczytu (odnalezienia komunikatu) będzie na
pewno mniejszy niż 2ms i można go (moim zdaniem) ostrożnie oszacować na
połowę tego czasu czyli 1ms.
Nie ma sensu sie spierac o ms. I tak za dlugo :)
Ostatni czyli znajdujący się "bliżej" aktualnego końca bufora. Wystarczy
przeszukiwać bufor od najnowszych do najstarszych - pierwszy znaleziony
jest
właściwy, pod warunkiem, że nie jest "za stary".
Tu sie zgodze, nie pomyslalem o tym
Zaraz, zaraz. Jak to po 256 sekundach?! Przecież po takim czasie komunikat
zostanie dawno zamazany przez następne. Napisałeś, że jest ich
100-200/sek,
więc przy buforze na 2000 komunikatów czas życia każdego z nich jest od 10
do 20 sekund. Żeby jakiś komunikat przetrwał dłużej niż 256 sekund, ich
częstość musiałaby spaść poniżej 8/sek.
Fakt, napisalem 100-200 na sekunde. Zazwyczaj tak jest, ale nie zawsze.
To zmienia założenia (100-200/sek). Może da się jakoś szybko wykryć, że
urządzenie zgłupiało i w ogóle ignorować komunikaty od niego.
Nie, nie mozna. Zazwyczaj poza kolejnoscia wysyla sie wlasnie wazne
informacje. Dlatego raczej sklanialbym sie ku rozwiazaniu w ktorym od razu
zastepuje sie
stare komunikaty.Pozwoli to zaoszczedzic pamiec.
Kolega z pracy podsunal mi pewna mysl:
odebrane dane przechowywac w strukturze drzewa (zaimplementowanego w
taklicy).
Nie wspomnialem o jednej z cech przychodzacych komunikatow.
Jezeli komunikat zostanie odebrany, to prawdopodobnie bedzie juz odbierany
caly czas. Oznacza to, ze jesli odbieramy dane od powiedzmy sterownika nr 5,
a ono jest
skonfigurowane by nadawalo 16 komunikatow, to te komunikaty bedzie nadawac
cyklicznie przez
caly czas.Chyba, ze zostanie wylaczone, ulegnie uszkodzeniu lub zostanie
przeprogramowane.
Raz utworzone drzewo rzadko byloby przebudowywane!!
Nie mam wielkiego doświadczenia w dobieraniu funkcji mieszających, ale
jak opiszesz różne możliwe zakresy adresów sterowników i numerów
komunikatów, które w praktyce mogą się zdarzać, to spróbuję coś
wykombinować
Juz rozumiem. Mysle, ze sam bym cos dobral. Mam jednak watpliwosci co do
skutecznosci tej metody.
Piotr
From: jfox_at_nospam_friko6.onet.pl (J.F.)
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Thu, 21 Sep 2000 22:45:53 GMT
On Thu, 21 Sep 2000 15:20:52 +0200, peters wrote:
[...]Dlatego raczej sklanialbym sie ku rozwiazaniu w ktorym od razu
zastepuje sie stare komunikaty.Pozwoli to zaoszczedzic pamiec.
pewna mysl: odebrane dane przechowywac w strukturze drzewa (zaimplementowanego w
tablicy).
Drzewo do wyszukiwania jest dobre, ale do usuwania przestarzalych
komunikatow kiepskie. A takie utworzone w tablicy jest malo elastyczne
na etapie dodawania danych. Trzeba poza tym dbac o balansowanie przy
tworzeniu, bo moze sie okazac liniowe.
Bardzo podobna idea to po prostu posortowana tablica. Wyszukiwanie
przeszukiwaniem binarnym, tyle ze przy dodawaniu trzeba przesuwac
tablice, a to kosztuje czas..
Nie wspomnialem o jednej z cech przychodzacych komunikatow.
Jezeli komunikat zostanie odebrany, to prawdopodobnie bedzie juz odbierany
caly czas.
Raczej ocen jakie jest prawdopodobienstwo ze jednak zniknie a pojawi
sie nowy. Bo od tego zalezy czy konieczne jest usuwanie przestarzalych
czy nie - np w instrukcji pisze ze czasem nalezy nacisnac reset,
najlepiej przy dodaniu nowego urzadzenia ..
J.
From: "Bartek Dajewski" <bartek_at_nospam_tradiss.com.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Fri, 22 Sep 2000 09:43:05 +0200
Cześć,
peters napisał(a) w wiadomości: <8qd273$lrf$1_at_nospam_news.tpi.pl>...
[...]
Zazwyczaj poza kolejnoscia wysyla sie wlasnie wazne
informacje. Dlatego raczej sklanialbym sie ku rozwiazaniu w ktorym od razu
zastepuje sie
stare komunikaty.Pozwoli to zaoszczedzic pamiec.
A może dodać dwa komunikaty do listy wysyłanych przez sterownik. Nie byłyby
one przechowywane w buforze, tylko od razu realizowane, a oznaczałyby: 1 -
informacje o aktualnej konfiguracji sterownika (liczbie lub lepiej zakresie
możliwych komunikatów) i 2 - pytanie o konfigurację. Każdy sterownik
wysyłałby go zaraz po starcie i po przeprogramowaniu. To pozwoliłoby
pozostałym sterownikom zarezerwować dla niego dokładnie tyle miejsca ile
potrzeba. W pamięci byłoby tyle buforów ile jest w systemie nadajników, a
wielkość każdego z nich byłaby dopasowana do konkretnego sterownika. Efekt:
pamięć wykorzystana optymalnie. Dodatkowo, jeżeli można założyć, że zbiór
komunikatów wysyłanych przez każdy sterownik jest zawsze złożony z kolejnych
liczb (nie ma "dziur" w numeracji), to masz natychmiastowy dostęp do komórki
dedykowanej dla komunikatu (kilka rozkazów procesora).
Kolega z pracy podsunal mi pewna mysl:
odebrane dane przechowywac w strukturze drzewa (zaimplementowanego w
tablicy).
Odradzam. Patrz list J.F. o przechowywaniu, równoważeniu i usuwaniu z
drzewa.
Nie wspomnialem o jednej z cech przychodzacych komunikatow.
Jezeli komunikat zostanie odebrany, to prawdopodobnie bedzie juz odbierany
caly czas. Oznacza to, ze jesli odbieramy dane od powiedzmy sterownika nr
5,
a ono jest
skonfigurowane by nadawalo 16 komunikatow, to te komunikaty bedzie nadawac
cyklicznie przez
caly czas.Chyba, ze zostanie wylaczone, ulegnie uszkodzeniu lub zostanie
przeprogramowane.
Tym bardziej warto rozważyć możliwość dodania komunikatu o aktualnej
konfiguracji nadajnika.
Nie mam wielkiego doświadczenia w dobieraniu funkcji mieszających, ale
[...]
Juz rozumiem. Mysle, ze sam bym cos dobral. Mam jednak watpliwosci co do
skutecznosci tej metody.
Niesłusznie. Metoda jest bardzo szeroko stosowana jako jeden z
wysokowydajnych sposobów przechowywania / wyszukiwania danych.
---
Pozdrawiam :-)
Bartek
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Fri, 22 Sep 2000 10:06:01 +0200
A może dodać dwa komunikaty do listy wysyłanych przez sterownik. Nie
byłyby
one przechowywane w buforze, tylko od razu realizowane, a oznaczałyby: 1 -
Nie wchodzi to w gre. Protokoł transmisji juz od dawna zatwierdzony,
urzadzenia produkowane przez kilka roznych firm.
Kolega z pracy podsunal mi pewna mysl:
odebrane dane przechowywac w strukturze drzewa (zaimplementowanego w
tablicy).
Odradzam. Patrz list J.F. o przechowywaniu, równoważeniu i usuwaniu z
drzewa.
Napisalem, ze przewaznie jak raz odbierze sie jakis komunikat to bedzie on
przychodzil zawsze.
A to chyba zmienia postac rzeczy. Raz utworzone drzewo pozostaloby
praktycznie niezmienne!!
Podsumowujac, najprostrzym rozwiazaniem wydaje mi sie funkcja mieszajaca i
jeden bufor. Mo to jednak wade, musimy w buforze pamietac numery sterownikow
i
komunikatow Marnujemy w ten sposob sporo pamieci. Na dokladke algorytm
bedzie dzialal
efektywnie tylko wtedy, gdy stosunkowo rzadko bedzie dochodzilo do
konfliktow.
Wolnej pamieci wiec musi byc sporo.
A o drzewach musze sobie poczytac :)
Piotr
From: "Bartek Dajewski" <bartek_at_nospam_tradiss.com.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Fri, 22 Sep 2000 13:41:25 +0200
Cześć,
peters napisał(a) w wiadomości: <8qf45j$g2j$1_at_nospam_news.tpi.pl>...
A może dodać dwa komunikaty do listy wysyłanych przez sterownik. Nie
byłyby
one przechowywane w buforze, tylko od razu realizowane, a oznaczałyby:
1 -
Nie wchodzi to w gre. Protokoł transmisji juz od dawna zatwierdzony,
urzadzenia produkowane przez kilka roznych firm.
Szkoda. Ale w takim razie można napisać taki algorytm, który sam
dopasowywałby rozmiar bufora na podstawie otrzymywanych komunikatów. Trzeba
by podzielić cały dostępny bufor na różnej wielkości obszary dla
poszczególnych nadawców. Wielkość każdego obszaru na starcie byłaby 0 i
zwiększała się w miarę przychodzenia kolejnych komunikatów. Każdy obszar
pamiętałby swoją długość i minimalny numer komunikatu jaki odebrał, a
położenie komórki w ramach obszaru byłoby o tę liczbę pomniejszone. Zaraz po
starcie system zachowywałby się raczej fatalnie, bo prawie po każdym
komunikacie następowałaby reorganizacja pamięci, ale po chwili sytuacja
stałaby się stabilna i nie zmieniała aż do zmiany konfiguracji któregoś
sterownika. Poza długością każdego obszaru trzeba jeszcze pamiętać ich
początki dla wszystkich nadawców no i oczywiście łączną długość bufora co
razem daje narzut 1026 bajtów, a całą resztę przeznaczasz na dane.
[...]
Podsumowujac, najprostrzym rozwiazaniem wydaje mi sie funkcja mieszajaca i
jeden bufor. Mo to jednak wade, musimy w buforze pamietac numery
sterownikow
i
komunikatow Marnujemy w ten sposob sporo pamieci. Na dokladke algorytm
bedzie dzialal
efektywnie tylko wtedy, gdy stosunkowo rzadko bedzie dochodzilo do
konfliktow.
To już zależy od funkcji mieszającej, czyli wszystko w Twoich rękach (i
głowie:-)
Wolnej pamieci wiec musi byc sporo.
Nie więcej niż przy drzewie. Przy wykorzystaniu drzewa też musisz pamiętać
numer nadawcy a dodatkowo jeszcze połączenie z sąsiednimi węzłami.
A o drzewach musze sobie poczytac :)
Polecam
<http://www.site.uottawa.ca/ftppub/courses/Winter/csi2131/sec11.html>. Jest
tam o B-drzewach i o stronicowanych B-drzewach. Te ostatnie są co prawda
szczególnie przydatne w danych plikowych, ale dla Ciebie też mają zaletę.
Łatwiejsze jest ich równoważenie przy dodawaniu / usuwaniu węzłów.
Oczywiście nic za darmo - prostsze (kosztujące mniej czasu) równoważenie
jest okupione bardziej rozrzutnym wykorzystywaniem pamięci: dostępna pamięć
jest efektywnie wypełniona w 50-100%. Wiem, że usuwanie występuje bardzo
rzadko, ale weź pod uwagę, że jeśli system ma chodzić 24h/d, to trzeba to
uwzględnić, żeby np. po dwóch tygodniach nie zaczęły się mu pogarszać
parametry pracy albo się wręcz nie zapchał.
---
Pozdrawiam :-)
Bartek
Date: Fri, 22 Sep 2000 15:49:30 +0200
From: Jan =?iso-8859-2?Q?Rudzi=F1ski?= <janekr_at_nospam_astercity.net>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Cześć wszystkim
peters wrote:
[...]
A o drzewach musze sobie poczytac :)
Nawet konkretnie zaproponuję: Aho, Hopcroft, Ullman "Projektowanie i
analiza algorytmów komputerowych", PWN 1983.
Piotr
--
Pozdrowienia
Janek http://www.astercity.net/~janekr
Niech mnie diabli porwą!
Niech diabli porwą? To się da zrobić...
From: jfox_at_nospam_friko6.onet.pl (J.F.)
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Thu, 21 Sep 2000 22:45:53 GMT
On Wed, 20 Sep 2000 19:01:59 +0200, peters wrote:
Mam procesor 166 a nie 186. Jak juz napisalem system jednoczesnie musi
sterowac roznymi urzadzeniami w czsie rzeczywistym. Jesli przyjmiemy, ze czas
potrzebny na przeszukanie jednej komorki tablicy wynosi 1 mikrosekunde to
przeszukanie calej tablicy (1000 elementow) zajmie az 1 ms. Juz sam odczyt kilkuset
komunikatow w ciagu sekundy moze pochlonac 20% czasu procesora!!!
No i co z tego ?
Po to sie daje procesor zeby pracowal a nie czekal :-)
No chyba ze tych 80% nie starcza na sterowanie [... kup szybszy
procek]. Albo ten czas przeszukiwania jest dla Ciebie kladacy ..
Nie do konca tak. Jesli przyjmiemy, ze nie zastepujemy w buforze starych
komunikatow a dopisujemy nowe, to co sie stanie gdy przyjda dwa komunikaty
o tym samym identyfikatorze, o roznej tresci, ale w tej samej sekundzie?
Szukasz "od poczatku" bufora [kolowego]. Najpierw znajdziesz ostatni
[najmlodszy], reszty nie szukasz ...
Ponadto pamietanie czasu przyjscia komunikatu wymusza napisanie chodzacej w
osobnym watku procedury uniewazniania komunikatow. W przeciwnym razie komunikat,
ktorego nie odczytano po 256 sekundach znow stalby sie wazny :))
Tak sie zwykle pisze buforki kolowe ze stary usuwa jak nowy przychodzi
- a dokladniej nowy wpisuje na miejsce starego. Nigdy nie odczytasz
dwa razy tego samego. No i skad 256s ? Jesli juz to tysieczny
komunikat...
Jeżeli rzeczywiście jest ich 100-200/sek to
muszą się pomieścić. Jeden komunikat = 5 bajtów (dwa bajty na dane, dwa na
ID i jeden na czas) czyli 10000 bajtów = jest OK
W normalnych warunkach istotnie powinny sie miescic. Ale co bedzie jak
ktores z urzadzen zglupieje i zacznie nadawac komunikaty czesciej? (
Traktujesz to jako sytuacje normalna, obslugujesz wszystkie komunikaty
i nie przejmujesz sie krotkim czasem. Albo "to nie moj problem tylko
Stacha, ma nie wysylac" albo "Bylo kupic wersje 64KB".
No chyba ze zalozenia sa troche inne niz pisales ...
J.
From: Tomasz Slodkowicz <slodki_at_nospam_elf.ii.uj.edu.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: 22 Sep 2000 11:44:06 GMT
In pl.comp.programming peters <peters_at_nospam_poczta.onet.pl> wrote:
Odbierane są komunikaty z innych sterowników (powiedzmy ok. 100-200 na
sekundę).
Każdy z nich zawiera 2 bajty danych i identyfikator określający rodzaj
przesyłanych danych (ponad 60000 możliwych rodzajów komunikatów)
1. Komunikaty należy zapamiętać do późniejszego przetworzenia.
2. Odebrane komunikaty ważne są tylko jakiś czas (około 10 sekund)
3. Nowy komunikat musi zastąpić stary o tym samym numerze.
4. Zwykle odbierane jest tylko kilkaset rodzajów komunikatów, ale nie można
przewidzieć które to będą.
5. Sterownik nie dysponuje pamięcią w której możnaby pomieścić wszystkie
możliwe komunikaty.
6. Moc obliczeniowa procesora też nie jest zbyt duża, a do tego wykonuje
dziesiątki innych zadań.
Należy znaleźć metodę zapamiętania odbieranych komunikatów, napisać
procedurę zapisującą odebrany komunikat i
procedurę odczytu ważnych komunikatów o zadanym identyfikatorze.
Stosujesz statyczna tablice mieszajaca, dodajac do 4 bajtow danych 1 bajt
znacznika czasu odebrania, daje to 200*10s*5B=10000 bajtow. Czyli dla
tablicy mieszajacej o rozmiarze 16KB daje to srednio ok 60% wypelnienia,
czyli calkiem niezle.
Starych komunikatow nie kasujesz, tylko przy okazji wyszukiwania sprawdzasz
znacznik czasu przegladanych danych i znakujesz jako nieuzywane. Pamietaj o
stosowaniu w tablicy mieszajacej znacznikow EMPTY i REMOVED.
Czas dostepu do danych jest prawie natychmiastowy, zastepowanie komunikatow
robi sie samo. Trzeba pamietac o takims skonstruowaniu funkcji mieszajacej,
aby latwo i szybko ja liczyc.
Oczywiscie gdy wzrosnie czestotliwosc pojawiania sie komunikatow nastapi
spadek wydajnosci az do zablokowania tablicy. Ale to oczywiste, ze w
usalonej pamieci nie obsluzysz dowolnie wysokiej liczby komunikatow
niezaleznie od algorytmu.
Przyjmujac optymalne wypelnienie tablicy mieszajacej do powiedzmy 85%,
mozesz oszacowac zapotrzebowanie na pamiec w zaleznosci od czestotliwosci
pojawiania sie komunikatow:
8KB - efektywna praca do 139kom/sek, blad przy 163kom/sek
16KB - 278kom/sek, 327kom/sek
32KB - 557kom/sek, 655kom/sek.
Oczywiscie nie mowie o wydajnosci procesora lecz wykorzystaniu pamieci.
Polecam zrobienie sobie przerwy w pracy i zaglebienie sie w teorii (lekturze
nt. struktur i algorytmow).
Tomek
--
Tomasz Slodkowicz Institute of Computer Science
Jagiellonian University, Cracow, Poland
e-mail: slodki_at_nospam_ii.uj.edu.pl http://2510045548/~slodki
From: "peters" <peters_at_nospam_poczta.onet.pl>
Subject: Re: ciekawy problem do rozwiazania (dlugie)
Date: Sun, 24 Sep 2000 23:14:36 +0200
Dzieki za wszelki uwagi i propozycje.
Za jakis miesiac zabiore sie za pisanie. Jak skoncze to sie pochwale. :)
Piotr
P.S. Specjalne podziekowania dla Experta za jego swiatle wskazowki i rady