To jest pierwszy wpis czyli aktualna treść poradnika. Jeżeli ktoś coś mądrego doda, wykryje błąd, itp. to treść może się zmienić.
Zainteresowanych dyskusją, dzięki której jest tak dobry, zapraszam do przeczytania dalszych wpisów.

Jeżeli tu jesteś to powinieneś znać słowa takie jak zmienna lokalna, zmienna globalna, lista, przetwarzanie współbieżne, problem wzajemnego wykluczania, sekcja krytyczna, itp.
Tu nie ma po prostu na to miejsca.
Oto linki do stron, gdzie można sprawdzić co znaczy dane słowo:
https://en.scratch-wiki.info/wiki/Variable niestety po angielsku, ale wyszukiwarka na pewno znajdzie definicję po polsku
https://pl.wikipedia.org/wiki/Problem_wzajemnego_wykluczania#Rozwi%C4%85zania_programowe

Ameryki nie odkryłem - przedstawiam jedynie moją wiedzę na dany temat oraz mój pomysł na implementację. Jeśli znasz lepszy sposób/algorytm/implementację, to daj znać, a z ciekawością go poznam.

Wielkie podziękowania dla:
https://scratch.mit.edu/users/AANNTTOONNII/ za poświęcony czas na znalezienie błędów a przede wszystkim za zrozumienie tematyki i podzielenie się swoją wiedzą.




Wprowadzenie
Scratch umożliwia stworzenie klonów - maksymalnie 300 w 1 projekcie.

sklonuj [tego duszka]

Niestety ta komenda działa anonimowo, czyli tworzy się dokładna kopia skryptów i zmiennych tego duszka. Gdyby po sklonowaniu zaistniała potrzeba, żeby np. jakiś konkretny klon zachował się inaczej, to normalnie jest to niemożliwe, bo przy klonowaniu nie otrzymujemy takiego narzędzia jak np. wskaźnik na klona.
Np. gdyby klon chciał “widzieć” jakie klony są w pobliżu, to potrzebuje oczu, czyli wglądu do zmiennej, która będzie zawierać informacje o wszystkich klonach.

Taką wygodną zmienną jest np. lista.
Lista ma elementy o nr od 1 do n, gdzie n należy do zbioru liczb naturalnych > 0
Jeżeli nadamy klonowi nr = pozycji elementu na liście, to będzie wiadomo, że zawartość elementu dotyczy tego klona.
Przykład:
lista_imion:
1. Wacek
2. Jacek
3. Pankracek

Każdy klon ma taki sam kod,

powiedz (połącz [Jestem ] i (element (klon_id) z [lista_imion] :: list))

więc jeśli będzie się przedstawiał i ma zmienną klon_id = 2 to powie “”Jestem Jacek"

Tablic w scratchu nie ma, więc trzeba zrobić tyle list ile atrybutów ma mieć klon - może być nawet lista z komendami dla klona - czego tylko dusza zapragnie.
Oczywiście jak już wspomniałem jest ograniczenie do 300 klonów na projekt, więc być może jest też ograniczenie do ilości list. W chmurze wogóle nie można używać list.


Kiedy tylko 1 duszek tworzy klony
Sytuacja jest prosta, co pokazuje poniższy skrypt:

główny duszek:

powtórz (10) razy
zmień [cnt] o (1)
dodaj [0] do [lista_imion]
sklonuj [tego duszka]
end

klon:

kiedy zaczynam jako klon
powiedz [mam już cnt takie jak rodzic]
ustaw [clone_ID] na (cnt)

Polecenie powiedz jest komentarzem.
Ustawiać clone_id nie trzeba, bo zmienna cnt jest lokalną zmienną klona. Tzn. że inny duszek/klon już mu jej nie może zmienić. Ale jest to wskazane, na wypadek gdybyśmy chcieli w jakimś innym skrypcie klona ją użyć np. do zrobienia klona z klona.
A przecież wtedy zmiana cnt oznaczałaby zmianę id czyli nasz klon przestał by być Jackiem i to w wyniku błędu. Warto nazywać czytelnie zmienne i nie bać się je tworzyć - tym bardziej jeśli używane są rzadko i nie obciążą zasobów.
I tu się kończy zabawa w łatwe klonowanie.




Kiedy każdy klon/duszek może stworzyć klona
Każdy duszek i każdy jego klon może w dowolnym momencie sklonować siebie lub innego duszka, o ile nie przekroczymy limitu klonów.
Wyobraźmy sobie, że mamy listę i nagle 2 lub więcej duszków/klonów postanawia się sklonować. Naraz kilka duszków spróbuje nadać sobie klon_id, mimo, że nie mają o sobie pojęcia - nie wiedzą ile inne klony stworzyły klonów.
Będą próbowały się zapisać na listę, która musi być dla nich wszystkich widoczna i dostępna do zapisu, czyli musi być zmienną globalną. Musi być w Scratchu o ile wiem. W innych językach programowania można tego uniknąć.

Najpierw odrobina teorii.

Problem wzajemnego wykluczania
Przetwarzanie współbieżne to działanie 2 lub więcej procesów/skryptów działających naraz na współdzielonych danych(zasobach). W naszym przypadku współdzielonym zasobem jest długość listy. Długość się zmienia podczas dodawania lub usuwania elementów listy.
Kiedy klony spróbują dostać się do wspólnego zasobu w naszym przypadku zmiennej długość, może wystąpić problem.

Wyobraźmy sobie, że tworzę szybko 2 klony. Oba próbują się zapisać na lista_imion : każdy z nich wykonuje zestaw komend:

dodaj [imię] do [lista_imion]
ustaw [clone_ID] na (długość [lista_imion] :: list)

Co się stanie jeśli ich komendy się zazębią?
Załóżmy że lista była pusta.
1-szy klon doda “Wacek” do listy - lista ma długość 1
2-gi klon doda “Jacek” do listy - lista ma długość 2
1-szy klon ustawi swój id na 2
2-gi klon ustawi swój id na 2
BŁĄD - 2 klony mają taki sam id tzn. że będą zmieniać ten sam element listy w przyszłości.

Rozwiązanie
Możliwość wystąpienia jednoczesnego dostępu w tym wypadku do zmiennej długość_listy, rodzi problem wzajemnego wykluczania, czyli jak sprawić, żeby tylko 1 proces/klon dodał się do listy i ustawił swój id na jej długość, zanim ulegnie ona zmianie.
Czyli żeby nie było takiego zazębiania jak w przykładzie powyżej.
Ważne jest żeby zadbać o to wykluczanie, ponieważ inaczej wartość zmiennej będzie nieprzewidywalna, a to oznacza możliwość błędnego działania naszego projektu.

Ważne też jest, żeby zapewnić wszystkim procesom, które chcą się dodać do listy, prędzej czy później dostęp do niej. To się nazywa uczciwością i może być ona słabsza lub mocniejsza.
Kiedy nie ma wcale uczciwości, to mówimy, że może wystąpić zagłodzenie procesu/klona.

Zagłodzenie to taka sytuacja, kiedy proces/klon nigdy nie dostanie się do chronionego zasobu, czyli zmiennej wspólnej. W naszej sytuacji, kiedy dany klon nigdy nie mógłby się dodać do listy.

Sekcja krytyczna to takie miejsce w programie, gdzie następuje dostęp do współdzielonego zasobu, czyli w naszym przypadku do zmiennej długość lista_imion.


Informatyka zna już takie przypadki i np. istnieje rozwiązanie tego problemu pod nazwą Algorytm piekarniany
https://pl.wikipedia.org/wiki/Algorytm_piekarniany

Ja osobiście zmodyfikowałem i zaimplementowałem ten algorytm dla scratcha. Mam nadzieję, że prawidłowo bo wykorzystałem tylko 2 informacje:
- procesy/klony mają wziąć numerek
- procesy/klony mają stać w kolejce dopóki nie będą pierwsze w kolejce
Do tego przeczytałem o wykorzystywaniu kolejek procesów do realizacji uczciwości.

Dzięki gotowym listom w scratchu, algorytm wydaje się banalny w porównaniu z algorytmem piekarnianym z linku.
Do nadawania numerków użyłem listę ze scratcha. Nazwałem ją FIFO. Ona ustala kolejność oraz blokuje dostęp do sekcji krytycznej.

FIFO, czyli first in - first out (pierwszy wchodzi - pierwszy wychodzi). Ta lista zapewnia rozwiązanie 2 problemów:

1. wzajemnego wykluczania - tylko 1-szy klon na liście FIFO może dodawać elementy do innych list (zmieniać ich długość) i czytać ich długość dopóki nie zwolni dostępu dla kolejnego klona
To tak jak w piekarni może kupować tylko 1 klient naraz a reszta czeka w kolejce.

2. zagłodzenia - które tu nie wystąpi, ponieważ klony są ustawione na liście FIFO czyli każdy zostanie obsłużony w kolejności w jakiej się udało im zapisać do FIFO.


Żeby klon stanął w kolejce musi się dodać do listy FIFO. Ale jak ma stwierdzić, że jest pierwszy na liście? Musi dodać jakiś unikalny element do listy, a potem sprawdzić czy taki element jest pierwszy.
Wykorzystam fakt, że każdy klon ma swojego rodzica czyli duszka lub klona, który go stworzył. Klon stworzony przez rodzica niech się nazywa dziecko.

Na początku zawsze jest tylko 1 duszek o numerze klon_id = 0
Wszystkie mają ten sam kod czyli stworzą numery tak samo.

Czyli gdyby do klon_id rodzica dodać nr dziecka, to powstanie unikalny id potrzebny klonowi, żeby sprawdzić czy jest pierwszy w FIFO.
duszek 0 tworzy klony od 1 do n czyli o numerach 01, 02, 03, itd.
klon 01 tworzy klony od 1 do n czyli o numerach 011, 012, 013, itd.
klon 02 tworzy klony o numerach od 1 do n czyli o numerach 021, 022, 023, itd.
.
.
.
klon 011 - ups chyba nastąpił błąd, bo klon 01 stworzył dziecko o nr 011

Dodam myślnik żeby tego uniknąć. Czyli tak
duszek 0 tworzy klony od 1 do n czyli o numerach 0-1, 0-2, 0-3, itd.
klon 0-1 tworzy klony od 1 do n czyli o numerach 0-1-1, 0-1-2, 0-1-3, itd.
klon 0-2 tworzy klony o numerach od 1 do n czyli o numerach 0-2-1, 0-2-2, 0-2-3, itd.
.
.
.
klon 0-11

Ok teraz np. klon 0-1-1 może dodać element 0-1-1 do FIFO i sprawdzić kiedy 1-szy element będzie równy 0-1-1
Wówczas może wejść do sekcji krytycznej, czyli dodać element do lista_imion i ustawić klon_id na długość lista_imion.
Kiedy to zrobi może wyjść z sekcji krytycznej po prostu usuwając swój element z listy FIFO.
Kolejny klon z pozycji drugiej, automatycznie wejdzie na pozycję 1-szą, itd.


Przykładowe rozwiązanie
Żeby było trudniej wszystkie klony i duszek klonują się po wciśnięciu spacji - większa szansa, że coś pójdzie nie tak.
To rozwiązanie można skopiować i użyć za każdym razem gdy wiele klonów/duszków/skryptów, próbuje zmieniać jedną wspólną zmienną. Użyj wyobraźni.

kod rodzica:

kiedy wciśnięto klawisz [spacja]
zmień [liczba_moich_klonów] o (1)]
ustaw [nr_dziecka] na (połącz [mój_ID] i (połącz [-] i [liczba_moich_klonów]))
sklonuj [tego duszka]

kod dziecka

kiedy zaczynam jako klon
ustaw [FIFO_ID] na [nr_dziecka]
dodaj [FIFO_ID] do [lista FIFO]
czekaj aż <(element (1) z [lista FIFO] :: list) = [FIFO_ID]>

ostatnie polecenie sprawdza czy można wejść do sekcji krytycznej

początek sekcji krytycznej:

dodaj [Jacek] do [lista_imion]
ustaw [klon_id] na (długość [lista_imion] :: list)

koniec sekcji krytycznej

Uwaga - jeśli chodzi o problem wzajemnego wykluczania, liczy się tylko FIFO_ID i kolejka FIFO do zapewnienia uczciwości. W sekcji krytycznej pobieramy sobie drugi identyfikator klon_id, ale to tylko dlatego, że nam się przyda później. Nie jest on elementem algorytmu piekarnianego. Nie będzie służył do dostępu do sekcji krytycznej.

zwalniamy teraz dostęp do sekcji krytycznej czyli

usuń (1) z [lista FIFO]

Gotowa implementacja
To by było na tyle. Zaimplementowałem to rozwiązanie i udostępniłem gdyby ktoś potrzebował takich klonów i chciał zobaczyć czy to faktycznie działa i jak.
Są powstawiane polecenia czekaj, żeby było można zauważyć FIFO_ID i liczby elementów na listach po każdym kliknięciu. Jest też dodatkowy duszek-czarodziej, który sprawdza, czy przypadkiem nie doszło do błędu.
Błąd to sytuacja, kiedy jakiś element listy_vx jest równy 0, co oznacza, że:
- żaden klon/duszek nie zmienia tego elementu -> czyli nie ma duszka/klona o takim numerze -> czyli nie ma ciągłości numeracji, a to sugeruje błąd wzajemnego wykluczania.

https://scratch.mit.edu/projects/495463577

Planuję zrobić coś w stylu sztucznego życia czyli symulacji np. kopiec mrówek i stąd ten pomysł. Gdyby ktoś spotkał lepsze rozwiązanie będę wdzięczny za informację z linkiem.
Z góry dziękuję za polubienia i serduszka i nie zapomnijcie poinformować w projekcie, że pomogłem.
W razie gdybyście zauważyli jakieś błędy to nie wahajcie się pisać.

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

Fajny poradnik. IPC to nie łatwy dział informatyki, a w scratchu trzeba mierzyć się z takimi problemami cały czas! To niesamowite, że dzieci potrafią wymyślić tutaj rozwiązania nad którymi studenci informatyki też musieliby się nieźle nagłowić. Tutaj lista moich zastrzeżeń do twojego poradnika:

AndrzejL1 wrote:

Niestety ta komenda działa anonimowo, czyli tworzy się dokładna kopia skryptów i zmiennych tego duszka. Gdyby zaistniała potrzeba, żeby np. jakiś konkretny klon zachował się inaczej, to normalnie jest to niemożliwe, bo przy klonowaniu nie otrzymujemy takiego narzędzia jak np. wskaźnik na klona.

Dlaczego? Wskaźnik na klona jest nam niepotrzebny. Skoro możemy numerować klony to możemy też nadać komunikat przeznaczony tylko dla konkretnego klona.

AndrzejL1 wrote:

Każdy klon potrzebuje unikalnego identyfikatora. Zmienna stoper wygląda na najbezpieczniejszą

Dla mnie ona w ogóle nie wygląda na bezpieczną. Dwa fragmenty skryptów nadające duszkowi ID mogą zostać wykonane tak szybko, że czas pomiędzy nimi będzie mniejszy niż najmniejsza jednostka mierzona przez stoper scratcha. To jest chyba niemożliwe w trybie normalnym, ale jak najbardziej możliwe w trybie turbo.

Pomijając już aspekty techniczne takie rozwiązanie jest po prostu niewygodne. Nie znamy wtedy ID naszych klonów. Lepiej numerować je po kolei. Wtedy jeśli wiemy, że mamy np. 10 klonów to mają one numery od 0 do 9, a więc znamy ID każdego z nich. Przy implementacji tego rozwiązania, w celu uniknięcia hazardu nie możesz oczywiście użyć algorytmu Petersona (bo klony nie mają jeszcze ID), ale możesz użyć mutex'ów:

główny duszek:

powtórz (10) razy
ustaw [mutex v] na [1]
sklonuj [siebie v]
czekaj aż <(mutex) = [0]>
end

klon:

kiedy zaczynam jako klon
ustaw [id v] na [cnt]
zmień [cnt v] o (1)
ustaw [mutex v] na [0]

Duszek zna swój identyfikator, który jest równy jego pozycji na listach. Czyli Klon o id =3 wie, że może zmieniać tylko element 3-ci w listach. Za to już czytać może wszystkie elementy. Listy przy tworzeniu ustawiamy jako zmienne globalne, więc trzeba pilnować, żeby klon zmieniał tylko swój element listy.

Chwila, chwila. A nie, że ID klona to miałbyć czas jego powstania? Poza tym dlaczego chcesz dodawać nowe miejsca do listy w pętli inicjalizującej klona? Dlaczego tak komplikujesz sprawę? Nie jest prościej na początku dodać do listy n wejść równych zero i potem traktować ją jak tablicę?

Problem współbieżności

Nie ma czegoś takiego jak problem współbieżności. Twój algorytm rozwiązuje problem wzajemnego wykluczenia.

Programowanie współbieżne to działanie 2 lub więcej procesów/skryptów naraz.

Programowanie to proces pisania programu.

Kiedy próbują dostać się do wspólnego zasobu w naszym przypadku zmiennej listowej, może wystąpić problem.

A masz na myśli jakiś konkretny problem? Musiałeś źle zrozumieć cel stosowania tego algorytmu. Ma on rację bytu w przypadku kiedy w regionie krytycznym modyfikujemy jakieś liczniki, albo inne dane, które po prostu mogą się zepsuć jeżeli dwa wątki myślą, że są jedynm wątkiem, który uzyskuje do nich dostęp, ale nie w przypadku tablicy współrzędnych, w której dane modyfikujemy 30 razy na sekundę i za każdym razem są to bardzo podobne liczby. Co się stanie jeżeli wystąpi hazard i przez przypadek odczytamy obecną współrzędną x duszka i jego współrzędną y sprzed 1/30 sekundy? Nic?

Wymyśliłem sobie dodatkową listę FIFO, czyli first in - first out. Ta lista zapewni rozwiązanie 2 problemów

Czym są te problemy? Wyjaśnij je, podaj przykłady.

3. Lista to bardzo uczciwe rozwiązanie.

A to co? Trzeci problem?

Teraz oprogramowanie sekcji krytycznej:

Czym jest sekcja krytyczna? Napisałeś to gdzieś?

Dodałem duszka czarodzieja, który pokazuje jak można zmieniać dowolny parametr dowolnego klona. Można też wysyłać mu bardziej skomplikowane komendy - np. dodać listę ghost_mode i wpisując odpowiedni nr zmieniać kompletnie jego zachowanie.

Jeszcze chcę dodać jakiegoś duszka np. wodopój, do którego by się starały dostać klony, ale naraz mogłyby być tylko 2 klony przy wodopoju. To by pokazało jak ta współbieżność działa w takim przypadku.
Pojawiają się moim zdaniem 2 kolejne sekcje krytyczne:
- pierwsza to dostęp do zmiennej przechowującej liczbę klonów przy wodopoju (współzawodniczą wszystkie klony, oprócz tych które są przy wodopoju)
- druga to dostęp do ilości wody w wodopoju (współzawodniczą 1 lub 2 klony oraz sam wodopój. Klony zmniejszają ilość wody, a wodopój ją uzupełnia.

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

AANNTTOONNII wrote:

Fajny poradnik. IPC to nie łatwy dział informatyki, a w scratchu trzeba mierzyć się z takimi problemami cały czas! To niesamowite, że dzieci potrafią wymyślić tutaj rozwiązania nad którymi studenci informatyki też musieliby się nieźle nagłowić. Tutaj lista moich zastrzeżeń do twojego poradnika:

Dzięki za zainteresowanie AANNTTOONNII - spróbuję po koleji odpowiadać, bo sporo tego - zacznę od tego, że dzieckiem nie jestem - jak napisałem w profilu zająłem się scratchem, żeby pomóc znajomym dzieciom, a przy okazji jak już tu jestem to staram się coś interesującego mnie zrobić.

AANNTTOONNII wrote:

Dlaczego? Wskaźnik na klona jest nam niepotrzebny. Skoro możemy numerować klony to możemy też nadać komunikat przeznaczony tylko dla konkretnego klona.

Wydaje mi się, że wskaźnik na klona, jest potrzebny, bo to by załatwiało kwestię indywidualizacji raz na zawsze. Ale skoro go nie ma w scratchu, to robię numerację i do tego listę poprzez którą się z danym klonem komunikujemy.
Sama numeracja nie wystarczy.

AANNTTOONNII wrote:

Dla mnie ona w ogóle nie wygląda na bezpieczną. Dwa fragmenty skryptów nadające duszkowi ID mogą zostać wykonane tak szybko, że czas pomiędzy nimi będzie mniejszy niż najmniejsza jednostka mierzona przez stoper scratcha. To jest chyba niemożliwe w trybie normalnym, ale jak najbardziej możliwe w trybie turbo.

Pomijając już aspekty techniczne takie rozwiązanie jest po prostu niewygodne. Nie znamy wtedy ID naszych klonów. Lepiej numerować je po kolei. Wtedy jeśli wiemy, że mamy np. 10 klonów to mają one numery od 0 do 9, a więc znamy ID każdego z nich. Przy implementacji tego rozwiązania, w celu uniknięcia hazardu nie możesz oczywiście użyć algorytmu Petersona (bo klony nie mają jeszcze ID), ale możesz użyć mutex'ów:

główny duszek:

powtórz (10) razy
ustaw [mutex v] na [1]
sklonuj [siebie v]
czekaj aż <(mutex) = [0]>
end

klon:

kiedy zaczynam jako klon
ustaw [id v] na [cnt]
zmień [cnt v] o (1)
ustaw [mutex v] na [0]

Ciekawe, że te mutexy, to tak naprawdę flagi-semafory, tylko, że po pierwsze tutaj nie ma problemu wzajemnego wykluczania, bo tylko 1 duszek główny generuje klony. Kiedy klon wykorzysta zmienną cnt, to ustawia mutex, co uruchamia kolejne klonowanie.
To w ogóle chyba niepotrzebne. W tej sytuacji wystarczy zmieniać w duszku głównym cnt i klonować. Klon rodzi się z gotowym cnt. I nie trzeba mutexa używać. czyli tak:

główny duszek:

powtórz (10) razy
zmień [cnt] o (1)
sklonuj [siebie v]
end

klon:

kiedy zaczynam jako klon
powiedz [mam już cnt takie jak rodzic]

Zwróć uwagę, że u mnie tylko 1 klon powstał na początku z głównego duszka. Pozostałe klony powstają z klonów - próbowałem klikać szybko i działy się cuda, gdy nie było FIFO. Nie dałem rady tak szybko klikać, żeby uzyskać takie same 2 wartości stopera w FIFO. Nie wiem kto kliknie którego klona i ile razy i dlatego nie wyobrażam sobie innej wartości lepszej od stopera.

AANNTTOONNII wrote:

Duszek zna swój identyfikator, który jest równy jego pozycji na listach. Czyli Klon o id =3 wie, że może zmieniać tylko element 3-ci w listach. Za to już czytać może wszystkie elementy. Listy przy tworzeniu ustawiamy jako zmienne globalne, więc trzeba pilnować, żeby klon zmieniał tylko swój element listy.

Chwila, chwila. A nie, że ID klona to miałbyć czas jego powstania? Poza tym dlaczego chcesz dodawać nowe miejsca do listy w pętli inicjalizującej klona? Dlaczego tak komplikujesz sprawę? Nie jest prościej na początku dodać do listy n wejść równych zero i potem traktować ją jak tablicę?

No właśnie nie wiem ile wejść miałbym dać, skoro nie wiem ile klonów powstanie w trakcie gry.
Tu nie chodzi o czas powstania - został użyty tylko jako unikalny id na liście FIFO. Identyfikatory powstają gdy dany klon ma prawo dostępu do zmiennej długość

AANNTTOONNII wrote:

Problem współbieżności

Nie ma czegoś takiego jak problem współbieżności. Twój algorytm rozwiązuje problem wzajemnego wykluczenia.

Programowanie współbieżne to działanie 2 lub więcej procesów/skryptów naraz.

Programowanie to proces pisania programu.

Święta prawda - do poprawki

AANNTTOONNII wrote:

Kiedy próbują dostać się do wspólnego zasobu w naszym przypadku zmiennej listowej, może wystąpić problem.

A masz na myśli jakiś konkretny problem? Musiałeś źle zrozumieć cel stosowania tego algorytmu. Ma on rację bytu w przypadku kiedy w regionie krytycznym modyfikujemy jakieś liczniki, albo inne dane, które po prostu mogą się zepsuć jeżeli dwa wątki myślą, że są jedynm wątkiem, który uzyskuje do nich dostęp, ale nie w przypadku tablicy współrzędnych, w której dane modyfikujemy 30 razy na sekundę i za każdym razem są to bardzo podobne liczby. Co się stanie jeżeli wystąpi hazard i przez przypadek odczytamy obecną współrzędną x duszka i jego współrzędną y sprzed 1/30 sekundy? Nic?

No tu chodzi tylko o dodawanie do listy kolejnego klona. Potem już nie ma problemu. Powtórzę - chodzi o zmienną długość listy. Było opisane wcześniej to zjawisko.

AANNTTOONNII wrote:

3. Lista to bardzo uczciwe rozwiązanie.

A to co? Trzeci problem?

fakt - zaraz zmienię

AANNTTOONNII wrote:

Czym jest sekcja krytyczna? Napisałeś to gdzieś?

Podałem link do wiki, ale faktycznie warto to napisać.

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

Przypominam, bo nikt tu nie wspomniał o tym, o zmiennych tylko dla duszka i ich zachowaniu dla klonów.
Aż sam się dziwię, że tak mało osób o tym wie.Dlaczego ten kod działa? Sam nie wiem, wiem tyle, że działa i nigdy mnie nie zawiódł, nawet na mocnych projektach przy maksymalnej ilosci klonow.
na screenac zmienna id jest zmienna tylko dla duszka



W ten sposob kazdy z klonow ma wlasne id, bez zadnego problemu, chociaż sprawie można sie przyjrzeć, jak dokładnie to działa.
Sprawa oczywiście komplikuje się tutaj, gdyż w 1 bloku w ‘gdy zaczynam jako klon’ ustawiamy zmienną dla klona ‘id’ na zmienną id globalną, a na pewno tak zdaję się być. Problem w tym, że ta zmienna, według kodu, powinna być dla klona, ale scratch interpretuje ją jako globalną i dlatego własnie ten kod działa. Zawsze myślałem, że zmienna ta staje się dla klona, wtedy, kiedy po raz pierwszy ją “nadpiszemy”, do tego czasu jest ona globalna, ale nie wiem.

Jak tak kombinuję z tymi klonami, to scratch zdaje się działać tak:
Gdy tworzymy nowego klona, to scratch kopiuje niejako, wszystkie zmienne dla duszka i robi je tylko dla tego klona.
Zatem ten mój kod u góry, nie jest idealny, gdyż można zupełnie wyrzucić blok ‘ ustaw id na (id) ’

W wiki jest dokładnie napisane, że klony są dokładną kopią rodzica (duszka głównego lub innego klona). W momencie klonowania dokładnie są kopiowane zmienne. Zmienne lokalne i dostępne dla wszystkich klonów są takie same czyli mają taką samą wartość. Ale od tej pory czyli od momentu sklonowania może je zmieniać tylko dany klon.
P.S.
Jeszcze sobie przypomniałem, że polecenie

usuń tego klona

działa też chyba na duszka głównego - tzn. usuwać go nie usunie, ale być może zatrzyma skrypty. Stosowałem coś takiego jak nie mogłem opanować liczby klonów w mojej gierce World of Tank ale to były początki moje w scratchu.
Nie da się tego użyć normalnie, bo lubi być na końcu skryptu. Ale np. można tak:

jeżeli <> to
usuń tego klona
end

Jak już wspominałem w poście powyżej, to są proste sprawy. Weź mój projekt i usuń FIFO a zostaw klonowanie na klikanie. Jeśli zrobisz tak, żeby wszystkie klony miały kolejne id od 1 do liczby klonów to bym chętnie to zobaczył. Szczególnie jak się szybko klika na klona. Próbowałem też liczyć klony i też cuda się działy.,ale może to wina tej apki scratch, którą właśnie odinstalowałem.

Nadal uważam, że to nie sztuka zrobić ustaloną liczbę klonów - ale przecież gry na tym często polegają, że nie wiemy co się wydarzy. Po to np. sprawdza się czy gracz wpisał liczbę a nie literę, że nie wiadomo co wpisze.

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

MentolMen wrote:

Jak tak kombinuję z tymi klonami, to scratch zdaje się działać tak:
Gdy tworzymy nowego klona, to scratch kopiuje niejako, wszystkie zmienne dla duszka i robi je tylko dla tego klona.
Zatem ten mój kod u góry, nie jest idealny, gdyż można zupełnie wyrzucić blok ‘ ustaw id na (id) ’

Masz rację - można wyrzucić - tak jak zrobiłem odpowiadając AANNTTOONNII

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

Przykład tego co się zdarzy po kliknięciu klona.
Mamy na ekranie 3 klony - każdy z nr czyli 1, 2 i3.
Nie wiem jak szybko po kliknięciu zostanie zrobione klonowanie.
Klikam 2x tego z nr 1 - powstają 2 klony - gdyby brały numery z 1-ki, to by powstały klony 2 i 3 czyli już by były złe numerki.
Można oczywiście globalną zmienna liczba_klonów ale to wspólny zasób, czyli sekcja krytyczna, czyli nie wyjdziie.

To co proponował AANNTTOONNII czyli mutex to super sprawa, ale nie wiem czy nie działa tylko na 2 procesy(klony). Do nieznanej ilości chyba najlepszy będzie algorytm piekarniany.i tak na oko mój na taki wygląda.
Czyli tak - chcesz dodać się do list klonów to bierzesz numerek (stoper), stajesz w kolejce FIFO. Jak będziesz pierwszy w kolejce to idziesz do okienka, zapisujesz się na listy klonów i wyrzucasz numerek do kosza.
https://pl.wikipedia.org/wiki/Algorytm_piekarniany

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

Pora spać
Na koniec dodam, że ten algorytm jest uniwersalny moim zdaniem, bo nieważne ile powstanie klonów z klonów i w jakiej kolejności. Oczywiście są jakieś ograniczenia sprzętowe co do ilości, itp.
Ja np. myślałem, o mrówkach - niby królowa robi klony, ale one jeszcze walczą, giną lub umierają z głodu lub zatrucia. Po jakimś czasie byłoby sporo martwych pozycji na listach, aż w końcu by się zapełniły. A dzięki temu algorytmowi, można dodać również usuwanie z list martwych mrówek.
A jakby stworzyć symulację stworzeń, które rozmnażają się w parach? Nie wiadomo ile ich powstanie i ile będą mieć potomstwa.

A kolejka FIFO może zostać użyta nawet bez klonów w dowolnej gierce, gdzie co najmniej 2 duszki próbują zmieniać wartość jakiejś zmiennej.
Mam nadzieję, że chociaż jeden scratcher kiedyś z tych moich wypocin skorzysta

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

AANNTTOONNII wrote:

Dla mnie ona w ogóle nie wygląda na bezpieczną. Dwa fragmenty skryptów nadające duszkowi ID mogą zostać wykonane tak szybko, że czas pomiędzy nimi będzie mniejszy niż najmniejsza jednostka mierzona przez stoper scratcha. To jest chyba niemożliwe w trybie normalnym, ale jak najbardziej możliwe w trybie turbo.

AANNTTOONNII dałeś mi do myślenia.
Obudziłem się i wymyśliłem alternatywę dla stopera.

Faktycznie każdy klon skądś się bierze. Czyli jakby istnieje drzewo klonów - pniem jest duszek główny.
FIFO oczywiście zostaje, ale nadal potrzebny jest unikalny identyfikator do tej kolejki, żeby klon wiedział, kiedy jest na 1-szym miejscu w FIFO.
Jakby użyć mutexa inaczej - niech id to będzie string pamiętający skąd pochodzi klon.
duszek główny ma domyślnie id = 0
Kiedy tworzy klony to wie ile ich stworzył i nadaje im numerki 01, 02, 03, i tak dalej.
Każdy z klonów klikniętych robi oczywiście to samo, czyli kliknięty klon 02, będzie tworzyć klony 021, 022, 023, itd.
kod rodzica:

zmień [liczba _moich_klonów] o (1)]
ustaw [nr_dziecka] na [(połącz (mój_ID) i [liczba _moich_klonów])]
sklonuj [tego duszka]

kod dziecka

kiedy zaczynam jako klon
ustaw [mój_id] na [nr_dziecka]

Nie wiem czy to ma sens - zrobię remiks projektu czy to w ogóle zadziała.

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

AndrzejL1 wrote:

To w ogóle chyba niepotrzebne. W tej sytuacji wystarczy zmieniać w duszku głównym cnt i klonować. Klon rodzi się z gotowym cnt. I nie trzeba mutexa używać. czyli tak:

Jest potrzebne. Przerwanie może nastąpić pomiędzy

kiedy zaczynam jako klon

a

ustaw [ID v] na (cnt)

I dwa klony będą miały to samo ID. Wydaje mi się, że najlepszy jest jednak sposób, który podał MentolMen, a o którego istnieniu nie miałem wcześniej pojęcia.

AANNTTOONNII dałeś mi do myślenia.
Obudziłem się i wymyśliłem alternatywę dla stopera.

Nie, nie, nie! To jest tak samo zły sposób jak używanie licznika. Oczywiście, że przerwanie może wystąpić jeszcze przed ustawieniem swojego numeru, ale po inkrementacji licznika. Użyj sposobu MentulMena. Tylko pamiętaj żeby wyjaśnić czym są zmienne lokalne.

AANNTTOONNII wrote:

AndrzejL1 wrote:

To w ogóle chyba niepotrzebne. W tej sytuacji wystarczy zmieniać w duszku głównym cnt i klonować. Klon rodzi się z gotowym cnt. I nie trzeba mutexa używać. czyli tak:

Jest potrzebne. Przerwanie może nastąpić pomiędzy

kiedy zaczynam jako klon

a

ustaw [ID v] na (cnt)

I dwa klony będą miały to samo ID. Wydaje mi się, że najlepszy jest jednak sposób, który podał MentolMen, a o którego istnieniu nie miałem wcześniej pojęcia.

Jesteś pewien? Jakim cudem 2 klony będą mieć 2 takie same cnt, skoro tylko główny duszek je zmienia i nadaje i to jest jego zmienna lokalna?

AANNTTOONNII dla mnie naprawdę jesteś gość, bo rozumiesz o czym piszę i pomagasz bardzo. Jednak jakoś nie mogę zrozumieć co się może wydarzyć pomiędzy tymi blokami. Nawet jakby było 1000 przerwań to i tak, każdy klon dostanie prawidłowy numer, bo on już w ma ten numer przed wydaniem komendy sklonuj. Tylko sobie go przepisuje ze zmiennej lokalnej do innej zmiennej lokalnej. Nikt inny nie tworzy tego klona, nikt nie zmieni zmiennych duszka przed sklonowaniem. Tylko ten duszek to robi, a to właśnie żadna współbieżność czyli brak problemu wzajemnego wykluczania.

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

AANNTTOONNII wrote:

AANNTTOONNII dałeś mi do myślenia.
Obudziłem się i wymyśliłem alternatywę dla stopera.

Nie, nie, nie! To jest tak samo zły sposób jak używanie licznika. Oczywiście, że przerwanie może wystąpić jeszcze przed ustawieniem swojego numeru, ale po inkrementacji licznika. Użyj sposobu MentulMena. Tylko pamiętaj żeby wyjaśnić czym są zmienne lokalne.

Wykryłem, że nazewnictwo będzie się powtarzać czyli
- klon 01 stworzy klona 011 (pierwsze dziecko)
- oraz klon 0 stworzy klona 011 (jedenaste dziecko)
Żeby tak nie było, oddzielę numerki np. minusem czyli
- klon 0-1 stworzy klona 0-1-1,
- oraz klon 0 stworzy klona 0-11
Teraz nie ma bata, żeby to nie było unikalne.

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

AndrzejL1 wrote:

AANNTTOONNII wrote:

Dla mnie ona w ogóle nie wygląda na bezpieczną. Dwa fragmenty skryptów nadające duszkowi ID mogą zostać wykonane tak szybko, że czas pomiędzy nimi będzie mniejszy niż najmniejsza jednostka mierzona przez stoper scratcha. To jest chyba niemożliwe w trybie normalnym, ale jak najbardziej możliwe w trybie turbo.

Pomijając już aspekty techniczne takie rozwiązanie jest po prostu niewygodne. Nie znamy wtedy ID naszych klonów. Lepiej numerować je po kolei. Wtedy jeśli wiemy, że mamy np. 10 klonów to mają one numery od 0 do 9, a więc znamy ID każdego z nich. Przy implementacji tego rozwiązania, w celu uniknięcia hazardu nie możesz oczywiście użyć algorytmu Petersona (bo klony nie mają jeszcze ID), ale możesz użyć mutex'ów:

główny duszek:

powtórz (10) razy
ustaw [mutex v] na [1]
sklonuj [siebie v]
czekaj aż <(mutex) = [0]>
end

klon:

kiedy zaczynam jako klon
ustaw [id v] na [cnt]
zmień [cnt v] o (1)
ustaw [mutex v] na [0]

Ciekawe, że te mutexy, to tak naprawdę flagi-semafory, tylko, że po pierwsze tutaj nie ma problemu wzajemnego wykluczania, bo tylko 1 duszek główny generuje klony. Kiedy klon wykorzysta zmienną cnt, to ustawia mutex, co uruchamia kolejne klonowanie.
To w ogóle chyba niepotrzebne. W tej sytuacji wystarczy zmieniać w duszku głównym cnt i klonować. Klon rodzi się z gotowym cnt. I nie trzeba mutexa używać. czyli tak:

główny duszek:

powtórz (10) razy
zmień [cnt] o (1)
sklonuj [siebie v]
end

klon:

kiedy zaczynam jako klon
powiedz [mam już cnt takie jak rodzic]

Zwróć uwagę, że u mnie tylko 1 klon powstał na początku z głównego duszka. Pozostałe klony powstają z klonów - próbowałem klikać szybko i działy się cuda, gdy nie było FIFO. Nie dałem rady tak szybko klikać, żeby uzyskać takie same 2 wartości stopera w FIFO. Nie wiem kto kliknie którego klona i ile razy i dlatego nie wyobrażam sobie innej wartości lepszej od stopera.

Jak ci odpisałem na twój wpis, to podałem sposób dokładnie taki sam jak MentuiMen po poprawce. To działa - ale tylko jak jeden duszek się klonuje raz lub wiele razy.

Kiedy klony robią klony, też może to działać, dzięki temu id co teraz wymyśliłem np. 0-11-2
Ale żeby te klony zapisać na jednej liście i nadać im kolejne id równe pozycji elementu w liście, to trzeba je przepuścić przez kolejkę FIFO. Muszą być 2 identyfikatory:

- Pierwszy żeby klon mógł się odnaleźć na liście FIFO jako jedyny. Lista FIFO to mutex i zarazem sprawiedliwy dostęp do mutexa. Ten id jest niewygodny do adresowania elementów w listach i dlatego dodałem drugi, dokładnie taki jak numeracja elementów w listach. Gdybym wiedział ile powstanie klonów to z góry bym je stworzył i używał tylko drugiego identyfikatora (patrz niżej).

- Drugi żeby wiedział, który element list klonów jest jego (np. pozycja, prędkość, kolor, imię, ilość paliwa, komunikaty, polecenia, itd na ile wyobraźnia pozwoli) Listy klonów nie są w sekcji krytycznej - jedynie w momencie dopisywania się klona do list, trzeba chronić, żeby w tym samym czasie inny klon się nie dopisywał.

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

Jak ci odpisałem na twój wpis, to podałem sposób dokładnie taki sam jak MentuiMen po poprawce. To działa - ale tylko jak jeden duszek się klonuje raz lub wiele razy.

Masz rację. Źle cię zrozumiałem, myślałem, że używasz zmiennej zwykłej, a nie lokalnej.

Kiedy klony robią klony, też może to działać, dzięki temu id co teraz wymyśliłem np. 0-11-2
Ale żeby te klony zapisać na jednej liście i nadać im kolejne id równe pozycji elementu w liście, to trzeba je przepuścić przez kolejkę FIFO. Muszą być 2 identyfikatory:

Zwróć uwagę, że w większości przypadków i tak chcesz wiedzieć, z których klonów wywodzi się dany klon więc rozwiązanie z innym sposobem zapisu jest bardzo sensownym rozwiązaniem.

W przypadku kiedy jednak chcesz nadawać klonom kolejne numery to FIFO jest jednym z możliwych rozwiązań. Ale nie jedynym. Możemy ulepszyć rozwiązania MentolMena wprowadzając zmienną, która mówi, który klon ma prawo teraz przydzielać numery:

zwykły duszek (ten, który się klonuje):

definiuj sklonuj_mnie
ustaw [proszący v] na (moje_ID)
nadaj [chcę nadawać numery v] i czekaj
jeżeli <nie <(przydzielający) = (moje_ID)>> to
sklonuj_mnie :: custom
zatrzymaj [ten skrypt v]
end
...
ustaw [przydzielający v] na [0]

specjalny duszek (jest tylko jeden taki):

kiedy otrzymam [chcę nadawać numery v]
zatrzymaj [inne skrypty v] :: stack
czekaj aż <(przydzielający) = [0]>
ustaw [przydzielający v] na (proszący)

Dzięki AANNTTOONNI za zrozumienie.
Moje rozwiązanie z FIFO działa pięknie, przejrzyście i ma tylko 2 komendy. Żaden duszek, nie czeka na zapis, bo zapisywany jest od razu w kolejkę w momencie zgłoszenia. Po co mam kombinować takie trudne rozwiązanie, kiedy kolejka jest w scratch gotowa? No ale to kwestia gustu.
A przy n-procesach algorytm piekarniany działa bezbłędnie. Nie wymyślę tutaj lepszego algorytmu, bo za cienki jestem.

Zróbmy tak - teraz zmienię projekt tak, że zastąpię stoper moim wymyślonym id i zmienię, żeby po wciśnięciu spacji duszek się klonował.
Zrobię widoczne zmienne i klon będzie robił tylko 2 rzeczy, jak powstanie zapisze się na listę klonów z wartościami 0. Potem zmieni wszystkie wartości swoje z 0 na 1. Jeżeli na listach klonów po wciśnięciu spacji znajdzie się jakiś element o wartości 0 to będzie dowód, że jakiś klon się zapisał na złą pozycję (np. 2 klony mają to samo clone_id).
Czarodziej sprawdzi i powie czy znalazł taki element na listach. Ciekawe co powie przy 10 tys. klonów, bo z każdą spacją będzie ich 2x więcej chyba

Jeżeli okaże się, że, że przy dużej liczbie klonów występują błędy to mój poradnik jest do skasowania jak sądzę.
Dam tu link, a ty weźmiesz mój projekt i wytniesz FIFO i wstawisz rozwiązanie mutex czy MentolMena i podeślesz link.
Sprawdzę i jeżeli to zadziała to szacun i zacznę kminić jakim cudem.
(Sorki ale już widzę, że 10 tys. klonów będzie zapisywać jedną zmienną globalną proszący, a tylko 1 uzyska pozwolenie (zmienna przydzielający). Duża szansa, że jakiś duszek nigdy nie będzie mieć szczęścia. Nie wspomnę o tysiącach niepotrzebnych operacji. Zapisywanie zmiennej proszący będzie głównym zajęciem duszków.)

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

https://scratch.mit.edu/projects/492827061

Okazało się, że problem wzajemnego wykluczania nie istnieje - przynajmniej dla 300 klonów. Można samemu sprawdzić, bo być może jednak coś teraz sknociłem.
Podgląd na listy dowodzi, że clony mają unikalne clone_ID i działają na swoich elementach
Być może problem wyniknął z tego, że aplikacja Scratch zainstalowana na komputerze, działała niepoprawnie i wykazywała błędy w dodawaniu do list. Stąd moja próba wyeliminowania tego.

Dlaczego można dodać tylko 300 elementów do listy? 300 klonów to sporo, jednak czuję niesmak…

say [Łatwiej zrobić projekt, niż wymyślić jak ma wyglądać podpis]

1. Oczywiście, że problem istnieje. Jeśli klonujesz się dostatecznie szybko (np. automatycznie). Jeśli klonujesz klikając to prawdopodobieństwo hazardu jest zerowe (scratch robi w trybie zwykłym 30 operacji na sekundę), a człowiek umie klikać 6-8 razy na sekundę. Z resztą sam hazard jest czymś niezwykle rzadkim i nie powinieneś podejmować takich pohopnych wniosków z jednej obserwacji… To, że widziałeś program raz, dwa razy, albo nawet milion razy działający to nie znaczy, że nie ma w nim buga.

2. Podałem tylko alternatywne rozwiązanie bo napisałeś, że twoje jest jedyne, ale nie implementuj go. Rozwiązanie z kolejką jest najlepsze.

3. W scratchu jest limit klonów, który wynosi 300. Nie da się zrobić ich więcej.