Zadanie z synchronizacji wielu wątków

Mam takie zadanie:

Jest most o długości d i nośności w. Na niego będą wjeżdżać auta, a każde z nich ma być reprezentowane przez osobny wątek, auta mają swoją wagę i długość. Pojazdy przed wjazdem mają się kolejkować (wszystkich nie może być więcej niż 25), przy odpowiednich warunkach wjeżdżać na most (musi być wolne miejsce i nie można przekroczyć nośności), poruszać się po nim (nie można wyprzedzać, auta jada tylko w jedna stronę oraz z tego mostu zjeżdżać i kończyć swój żywot. Mogą być to metody enter(), move() i exit() klasy Samochod.

Proszę o pomoc, bo nawet nie jestem w stanie stworzyć konceptu, na razie pomysł miałem taki.
Klasa Bridge (przechowuje wszystkie zmienne związane z mostem, wie ile jest aktualnie pojazdów sume ich mas itd)
Klasa Car dziedziczącą po Thread (osobne watki reprezentujace auta, kazdy z nich ma dostep do Bridge ktory jest jeden i probuje z nim się komunikować)
Klasa BridgeSimulation która jest nadrzędna, generuje watki i dodaje je do kolejek.

no i tak, generujemy wątki i dajemy je do BlockedQueue z ograniczonym rozmiarem do 25
Gdy wątek jest pierwszyw kolejce odpalamy go poprzez .start()
Próbuje wjechać na most, gdy jest to możliwe to na niego wjeżdza //enter()
Przemieszcza sie po nim nie wjezdzajac w inne auta //move()
gdy dojedzie do konca to umiera //exit()

Gdy próbowałem robic ten kod, uzywać synchornized to kończyło się tak, że albo nic nie wjeżdzało na most, albo przesuwało się jedno auto a dopiero potem kolejne, nie mam też pojecia jak zrobić tak, żeby kilka auto przejeżdżało po moscie, patrzac na siebie czy ze soba nie koliduja. (można np. zrobic tablice i sprawdzac pozycje, ale nie wiem jak synchornizować te wątki)

Współbieżność to jedna z najtrudniejszych rzeczy do ogarnięcia jaką znam w programowaniu. Nie wiem czy jest sens to robić na wątkach.

Też nie widzę sensu tego robić na wątkach, niestety to zadanie na studia :(

No to jeśli dobrze rozumiem to zadanie, to ten "most" ma symbolizować kolejkę thread-safe, do której "wjazd" ma tylko określona liczba wątków (określona na podstawie tych dwóch liczb, czyli długość i waga).

Spodziewam się że jeśli samochody to mają być wątki, to widzę to tak:

• Albo wszystkie wątki startują od razu (np 1000 wątków się odpala od razu), wszystkie próbują coś wsadzić do kolejki, ale tylko 25 pierwszych z nich da radę pozostałe będą blocked dopóki miejsce w kolejce się nie zwolni
• Albo tak jak mówisz, że wątki domyślnie nie są odpalone, i dopiero jak jest miejsce w nich to odpalasz .start().

W ogóle to zadanie jest jakoś dziwnie napisane.

Nawet nie do końca jest jasne co ten program ma robić na tak na prawdę- no dobra, ma mieć wątki które wołają jakieś metody enter(), move() ale co te metody niby mają robić? Tylko się wywołać i nic?

Brzmi ciężko.

Pytanie - skąd wiadomo w którą stronę samochód jedzie? W sensie zakładając układ współrzędnych, i że samochód jest obecnie na polu (x,y) = (2,3), to na jakie pola może się poruszyć?

Myślę, że pierwsze co bym zrobił to mając dane o obecnych współrzędnych samochodu (2,3), oznaczył każde potencjalne pole, na które ten samochód może się poruszyć (czyli np (3,3), (1,3), (2,4), (2,2)) jako "ostrzeżone" dla reszty, albo przynajmniej już na takie, które miałoby w sobie locka (owy "synchronized" - obejmujący jedynie takie "pole z ostrzeżeniem").

EDIT:
Dobra, nie doczytałem że to most, czyli poruszamy się tylko w jednym wymiarze. No to lekka modyfikacja tego co napisałem wyżej.

Riddle napisał(a):

Nawet nie do końca jest jasne co ten program ma robić na tak na prawdę- no dobra, ma mieć wątki które wołają jakieś metody enter(), move() ale co te metody niby mają robić? Tylko się wywołać i nic?

metoda enter() ma wprowadzać na most, a move() symuloawć przemieszczanie się po nim

Zadanie prawie spoko, poza jednym zdaniem dla mnie:
Przemieszcza sie po nim nie wjezdzajac w inne auta //move()

Jak można wjechać w inne auto przy tak podanym zadaniu?

To jest moja pafraza zadania, żeby były same konkrety, bo w oryginale jest lanie wody i jeszcze fragmenty o wizualizacji

Bo widzę dwie możliwości - prosta: auto jest albo przed mostem, albo na moście i za mostem. bardziej skomplikowana: auto znajduje się w jakimś punkcie p długości mostu.

Suchy702 napisał(a):

Gdy próbowałem robic ten kod, uzywać synchornized

synchronized to jest uproszczony lock zero jedynkowy: albo coś ma zasób albo nie. W tym wypadku chcesz użyć https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Semaphore.html . permits to jest maksymalna dopuszczalna masa mostu.

Suchy702 napisał(a):

Próbuje wjechać na most, gdy jest to możliwe to na niego wjeżdza //enter()

Gdy próbowałem robic ten kod, uzywać synchornized to kończyło się tak, że albo nic nie wjeżdzało na most, albo przesuwało się jedno auto a dopiero potem kolejne, nie mam też pojecia jak zrobić tak, żeby kilka auto przejeżdżało po moscie, patrzac na siebie czy ze soba nie koliduja. (można np. zrobic tablice i sprawdzac pozycje, ale nie wiem jak synchornizować te wątki)

a jak sprawdzasz czy jest możliwy ten wjazd na most?

Popełniłem taki kod:

package MultiThreading;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

class Bridge {
    private int length;
    private int capacity;
    private int currentLoad;
    private char[] bridgeState;

    public Bridge(int length, int capacity) {
        this.length = length;
        this.capacity = capacity;
        this.currentLoad = 0;
        this.bridgeState = new char[length];
        initializeBridgeState();
    }

    private void initializeBridgeState() {
        for (int i = 0; i < length; i++) {
            bridgeState[i] = '*';
        }
    }

    public boolean canGo(Car car){
        return currentLoad + car.getWeight() <= capacity && bridgeState[0] == '*';
    }

    public char getPosStatus(int idx){
        return bridgeState[idx];
    }

    public void changePosStatus(int idx, char ch){
        bridgeState[idx] = ch;
    }

    public boolean passedBridge(int position){
        return position == length-1;
    }

    public void displayBridgeState() {
        System.out.println(bridgeState);
    }
}

class Car extends Thread {
    private Bridge bridge;
    private int weight;
    private char name;
    private int position;

    public Car(Bridge bridge, int weight, char name) {
        this.bridge = bridge;
        this.weight = weight;
        this.name = name;
        this.position = 0;
    }

    public int getWeight() {
        return weight;
    }

    private boolean canMove(){
        return bridge.getPosStatus(position+1) == '*';
    }

    public void move(){
        if (canMove()){
            bridge.changePosStatus(position, '*');
            bridge.changePosStatus(position+1, name);
            bridge.displayBridgeState();
        }
    }

    @Override
    public void run() {
        System.out.println("Wlasnie wjechal pojazd: " + name);
        while (!bridge.passedBridge(position)) {
            move();
        }
    }
}

public class BridgeSimulation {
    public static void main(String[] args) {
        Bridge bridge = new Bridge(10, 200);
        BlockingQueue<Car> queue = new LinkedBlockingQueue<>(25);

        for (int i = 0; i < 5; i++){
            queue.add(new Car(bridge, 1, (char) ('a' + i)));
        }

        while (!queue.isEmpty()){
            if (bridge.canGo(queue.peek())){
                Car actCar = queue.poll();
                assert actCar != null;
                actCar.start();
            }

        }
    }
}

Dostaje takie wyjscie, za kazdym razem kolejnosc jest inna:

Wlasnie wjechal pojazd: b
Wlasnie wjechal pojazd: e
Wlasnie wjechal pojazd: c
Wlasnie wjechal pojazd: d
Wlasnie wjechal pojazd: a
*b********

Dlaczego watki wygladaja jakby nie uruchamialy sie po kolei? I jak zrobic zeby robily to wlasnie po kolei.
tylko jedno auto sie poruszylo i stoi w miejscu, nie jedzie dalej, dlaczego?

Dla uproszczenia dlugosc kazdego samochodu to 1, waga tak samo wiec nie gra roli

a dlaczego miałyby działać po kolei skoro to są osobne wątki?

Po dodaniu sleep(100) w

        //glowna petla
        while (!queue.isEmpty()){
            sleep(100);
            if (bridge.canGo(queue.peek())){
                Car actCar = queue.poll();
                assert actCar != null;
                actCar.start();
            }
        }

    //run w klasie Car
    @Override
    public void run() {
        System.out.println("Wlasnie wjechal pojazd: " + name);
        while (!bridge.passedBridge(position)) {
            move();
            try {
                sleep(100); // Dodatkowe oczekiwanie dla czytelności wyjścia
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

auta zaczynaja uruchamiac sie po kolei, natomiast dalej dochodzi tylko do jednego przesuniecia

Wlasnie wjechal pojazd: a
*a********
Wlasnie wjechal pojazd: b
Wlasnie wjechal pojazd: c
Wlasnie wjechal pojazd: d
Wlasnie wjechal pojazd: e

@Suchy702: Ale to nie ma sensu, bo to jest normalne w wątkach że one się nie uruchomią po kolei - na tym polega współbieżność. Z resztą, co to miałoby znaczyć "po kolei", przecież kod wątkach działa równocześnie.

Wątki nie są trzymane w queue, która kolejka może być czytana od tyłu lub od przodu jako lifo i fifo, wtedy by się uruchamiały jeden po drugim.

Ale w systemie operacyjnym są przetrzymywane w red black tree, więc jak dajesz syscall utworzenia thread, czyli clone, to wtedy dodajesz do samo balansującego drzewa, jak jakaś inna aplikacja zrobi wątek czy uruchomi proces to znowu przebiega balans drzewa na podstawie wag.
To jest też nazywane na linuxie completly fair scheduling.

Różnie może się te drzewo zbalansować i potem jest dequeue z tego drzewa, balansowane jest na podstawie wag, kernelowe thready są wyżej w rankingu i nie ma rozróżnienia między procesami i wątkami.

Żeby jako tako synchronizację zrobić, wykorzystałeś sleep, który działa w miarę bo poczekałeś aż wystartuje wątek pierwszy i dopiero następny utworzyłeś itp.

Można też jakieś tricki ze state machine zrobić i mutexami, gdzie wątek robi mutexa, ale jak nie jest maszyna stanów na jego wątku to odblokowuje i idzie czekać, a jak jest to blokuje, wykonuje swoje modyfikując uwspólnione struktury danych, inkrementuje maszynę stanów do następnego pojazdu i wychodzi.
Ale to też problemów dużo rodzi, bo nawet dokładnej treści zadania nie wiadomo, aczkolwiek możesz też to jakoś wykorzystać.

Będziesz musiał na pewno trochę pokombinować, używaj to co masz od semafor, mutexów, atomic operations, czy samych struktur thread safe, coś wymyślisz.

Spróbuj private volatile char[] bridgestate. Prawdopodobnie dochodzi do hoisting na głównej petli. Ale jak usuniesz sleep to i tak pojawią się znowu problemy. Może semafor z 25 uprawnieniami i atomic reference do stanu mostu jako record(zapis i odczyt).

Szczerze mówiąc, to zadanie brzmi jak typowy problem semaforowy, gdzie procesy (auta) walczą o dostęp do zasobów (waga i miejsce na moście). Ja bym podszedł do tego w sten sposób żeby rozszerzyć (skomponować) klasę z java.util.concurrent.Semaphore i przeciążyć metody acquire() i release().