Modo corretto di svincolare gli spazi con priorità più elevate con una rimozione filettata

1

Sto sviluppando un sistema produttore / consumatore con tre deque s (ciascuno per un livello di priorità, da massimo a min); il primo deque ha la priorità maggiore, quindi deve essere letto prima degli altri: una volta vuoto, verranno pubblicati altri deque s.

Il mio codice è qualcosa del tipo:

// this is the class associated to a deque
class DequeEntity {
    public:
        bool remove(Elem& elem); // simple RAII methods for inserting
        void insert(Elem info);     // and removing in this deque
        size_t size() const { return q.size(); }
        bool isEmpty() { return q.empty(); }
    private:
        std::mutex m;
        std::condition_variable write, read;
        std::deque<Elem> q;
};

// this class contains the three deques
class DequeManager {
    public:
        void insert(Elem e);
        void remove(void); // <--- this is my real struggle
        void printQueues(void);
        void startRemoverThread(void); // start removerThread; called once

    private:
        std::thread removerThread;
        std::array<DequeEntity, 3> deques;
};

Questo è il codice di bool DequeEntity::remove(Elem& elem)

bool DequeEntity::remove(Elem& elem) {
    std::unique_lock<std::mutex> lck(m);
    if (read.wait_for(lck, std::chrono::milliseconds(1000), 
        [this]() { return q.size() > 0; })) {
        try {
            elem = std::move(q.front());
            q.pop_front();
        } catch (const std::exception& e) {
            debug_red(e.what());
            return false;
        }
        write.notify_one();
        return true;
    }
    else {
        // timeout expired, failed to retrieve element from deque
        return false;
    }
}

Questo è il codice (pseudo) di void DequeManager::remove(void)

void DequeManager::remove(void) {
    Elem elem;

    while (true) {
        numQueue = 0;
        for (auto &q : deques) {
            if (q.remove(elem)) {
                // do stuff with elem
                // if there's more to read, go ahead
                while (q.size() > 0) {
                    Elem elem;
                    if (q.remove(elem)) {
                        // do stuff with elem
                    } else {
                        // failed to get another element;
                        // go on next deque
                        break;                      
                    }
                }
            }
        }
    }
}

DequeManager::remove(void) loop su tre deques , leggi tutti gli elementi (se ce ne sono) dal primo deque , poi continua a emettere il secondo deque , e lo stesso accade per il terzo.

Ho pensato che si trattasse di un'implementazione decente di priorità, ma mi sbagliavo: mi è stato detto che la priorità non è solo di emettere deque s con priorità più alta, ma rimuoverli sempre per primi, indipendentemente dagli altri.

Ad esempio, leggo solo tutti gli elementi del primo deque , quindi passiamo al secondo; durante l'emulazione, i nuovi elementi vengono inseriti nel primo deque : il mio metodo DequeManager::remove() corrente esegue il loop su tutto deque s, ma per prima cosa svuotare il secondo deque (che era eravamo ancora), il terzo e infine iniziare di nuovo il ciclo, rimuovendo gli elementi appena inseriti.

Ma questo non è quello che dovrebbe fare: anche se si rimuove dal secondo deque e i nuovi elementi sono inseriti nel primo, il thread di rimozione dovrebbe interrompere la rimozione da deque 2 , leggere gli elementi appena inseriti in deque 1 e (se deque 1 è effettivamente vuoto), ricomincia a vuoto deque 2 .

Questo è qualcosa che non avrei mai pensato, quindi devo ripensare alla strategia di rimozione (quindi il mio void DequeManager::remove(void) ): come può un thread interrompere la lettura di deque 2 , iniziare a leggere deque 1 e una volta finito tornare a% codice%? Non riesco a pensare a un modo per farlo con solo deque 2 e due mutex per ogni condition_variable : DequeEntity ha un normale ciclo DequeManager::remove , e non posso andare da for a deque 2 e quindi indietro deque 1 (o deque2 o deque 3 -> deque 2 -> deque 3 ). Ho faticato su questo per giorni, vorresti condividere con me alcuni consigli su come affrontare questo tipo di priorità?

    
posta elmazzun 28.07.2016 - 16:28
fonte

1 risposta

4

Stai pensando troppo al problema.

Ciò che in realtà desideri è recuperare un elemento dalla coda con la priorità più alta che ha un elemento disponibile. Una volta elaborato quell'elemento, tornerai all'inizio e guarderai di nuovo in ognuna delle code che hanno un elemento successivo per te.

void DequeManager::remove(void) {
    Elem elem;

    while (true) {
        numQueue = 0;
        for (auto &q : deques) {
            if (q.remove(elem)) {
                // do stuff with elem

                break; /* we have processed our element, so start 
                          looking in queues again in priority order */
            }
        }
    }
}

Il break nell'istruzione if assicurerà che finché ci sono elementi nella prima coda (più alta quota), solo questi elementi vengono elaborati.
Una volta che la coda più alta è vuota, è possibile prendere un elemento dalla seconda coda (e così via per priorità più basse).
Una volta che un elemento è stato elaborato, tutte le code con priorità più alta vengono ricontrollate (in ordine di priorità) se qualcosa è arrivato nel frattempo per assicurarsi che gli elementi della coda con priorità più alta vengano elaborati per primi .

    
risposta data 29.07.2016 - 13:27
fonte

Leggi altre domande sui tag