Håller helt med Elgot, du bör nog fundera igenom om det inte är så att du tänkt lite fel i designen om det finns ett sådant krav.
Det sagt, det finns helt klart fall när du vill upprätthålla en strikt FIFO-ordning kring ett lås. Vanligaste anledningen är att man vill garantera att ingen tråd får vänta väldigt länge eller kanske till och med för evigt.
Realtid OS har därför alltid semaphorer eller liknande där man kan specificera att trådar/taskar ska släppas vidare i samma ordning som de försökte ta semaphoren. "Vanliga" OS som Windows/Linux har typiskt inte någon sådan garanti på sina motsvarigheter, i fallet Linux så råkar s.k. spinlocks faktiskt vara sådana att de garanterar FIFO-ordning på x86 då man kunde göra detta utan att det kostade prestanda.
I C++11 har man lagt till en rad funktioner i standardbiblioteket för att hantera atomära variabler, lås, mutex, trådar etc. Så skrev ihop en lösning bara för att känna lite mer på C++11 funktionerna, är ett "hack" men den garanterar i alla fall att trådar kommer producera arbete i den ordning som de kör första raden inuti produce(), en rad som körs _innan_ man försöker ta låset som skyddar arbetskön.
#include <atomic>
#include <condition_variable>
#include <cstdint>
#include <iostream>
#include <memory>
#include <mutex>
#include <queue>
#include <thread>
#include <vector>
// work_t represent some work entity that can be produced/consumed
typedef std::string work_t;
// Ticket to ensure FIFO ordering of waiting tasks
typedef uint32_t ticket_t;
// Next free ticket, can be taken without holding 'mtx'
std::atomic<ticket_t> ticket;
// Mutex protecting the state of the consumer-producer queue
std::mutex mtx;
// work queue
std::queue<std::shared_ptr<work_t> > work_q;
// Ticket number that is next to be servered
ticket_t now_serving;
// Condition that is signaled when the next ticket is up for service
std::condition_variable cnd;
void produce(std::shared_ptr<work_t> work)
{
// Fetch a ticket before grabbing the mutex
ticket_t my_ticket = ticket.fetch_add(1);
std::unique_lock<std::mutex> lock(mtx);
// Wait until it is my turn, this line will check if the predicate
// holds, if it does not hold then _atomically_ release the mutex
// and wait for the condition variable to be signaled at which
// point the check is re-done. The mutex is again locked when
// running the statment following this statement.
cnd.wait(lock, [=]() { return my_ticket == now_serving; });
// Queue the work
work_q.push(work);
// I'm done, can now serve the next in line
now_serving++;
// Must notify all waiting tasks, only the one with the right
// ticket will proceed.
cnd.notify_all();
}
std::shared_ptr<work_t> consume()
{
std::unique_lock<std::mutex> lock(mtx);
// Block until there is something to be consumed
cnd.wait(lock, []() { return !work_q.empty(); });
auto work = work_q.front();
// Why does not pop() return the element in C++???
work_q.pop();
// Needed if this thread cut the line before the next producer
cnd.notify_all();
return work;
}
std::shared_ptr<work_t> make_work(std::string s)
{
return std::make_shared<work_t>(s);
}
int main()
{
std::shared_ptr<work_t> work;
std::vector<std::thread> threads;
std::vector<std::string> prod{"A", "B", "C", "D"};
for (auto p: prod)
threads.emplace_back([=]() { produce(make_work(p)); });
for (int i = prod.size(); i > 0; i--)
std::cout << *consume() << std::endl;
for (auto &t: threads)
t.join();
}
Dold text
Noter att det inte finns någon garanti för att utskriften alltid blir A,B,C,D. Ordningen blir den ordning som producerartrådarna råkar anropa produce() vilket visar på att värdet i detta fall för strikt FIFO-ordning i just produce() inte har något större värde i sig.
Edit: men i.o.f.s. så garanterar detta att ingen tråd får vänta för evigt på att köa sitt arbete...
