How to ensure that the messages will be enqueued in chronological order on multithreaded Asio io_service?

If you use a strand, the order is guaranteed to be the order in which you post the operations to the strand.

Of course, if there is some kind of "correct ordering" between threads that post then you have to synchronize the posting between them, that's your application domain.

Here's a modernized, simplified take on your MyUserConnection class with a self-contained server test program:

Live On Coliru

#include <boost/asio.hpp>
#include <boost/asio/ssl.hpp>
#include <deque>
#include <iostream>
#include <mutex>

namespace asio = boost::asio;
namespace ssl  = asio::ssl;
using asio::ip::tcp;
using boost::system::error_code;
using SslSocket = ssl::stream<tcp::socket>;

class MyUserConnection : public std::enable_shared_from_this<MyUserConnection> {
  public:
    MyUserConnection(SslSocket&& socket) : socket_(std::move(socket)) {}

    void start() {
        std::cerr << "Handshake initiated" << std::endl;
        socket_.async_handshake(ssl::stream_base::handshake_type::server,
                                [self = shared_from_this()](error_code ec) {
                                    std::cerr << "Handshake complete" << std::endl;
                                });
    }

    void sendMessage(std::string msg) {
        post(socket_.get_executor(),
             [self = shared_from_this(), msg = std::move(msg)]() {
                 self->queueMessage(msg);
             });
    }

  private:
    void queueMessage(std::string msg) {
        outbox_.push_back(std::move(msg));
        if (outbox_.size() == 1)
            sendLoop();
    }

    void sendLoop() {
        std::cerr << "Sendloop " << outbox_.size() << std::endl;
        if (outbox_.empty())
            return;

        asio::async_write( //
            socket_, asio::buffer(outbox_.front()),
            [this, self = shared_from_this()](error_code ec, std::size_t) {
                if (!ec) {
                    outbox_.pop_front();
                    sendLoop();
                } else {
                    end();
                }
            });
    }

    void end() {}

    SslSocket                socket_;
    std::deque<std::string>  outbox_;
};

int main() {
    asio::thread_pool ioc;
    ssl::context      ctx(ssl::context::sslv23_server);
    ctx.set_password_callback([](auto...) { return "test"; });
    ctx.use_certificate_file("server.pem", ssl::context::file_format::pem);
    ctx.use_private_key_file("server.pem", ssl::context::file_format::pem);
    ctx.use_tmp_dh_file("dh2048.pem");

    tcp::acceptor a(ioc, {{}, 8989u});

    for (;;) {
        auto s = a.accept(make_strand(ioc.get_executor()));
        std::cerr << "accepted " << s.remote_endpoint() << std::endl;
        auto sess = make_shared<MyUserConnection>(SslSocket(std::move(s), ctx));
        sess->start();
        for(int i = 0; i<30; ++i) {
            post(ioc, [sess, i] {
                std::string msg = "message #" + std::to_string(i) + "\n";
                {
                    static std::mutex mx;
                    // Lock so console output is guaranteed in the same order
                    // as the sendMessage call
                    std::lock_guard lk(mx);
                    std::cout << "Sending " << msg << std::flush;
                    sess->sendMessage(std::move(msg));
                }
            });
        }

        break; // for online demo
    }

    ioc.join();
}

If you run it a few times, you will see that

• the order in which the threads post is not deterministic (that's up to the kernel scheduling)
• the order in which messages are sent (and received) is exactly the order in which they are posted.

See live demo runs on my machine:

On a multi core or even on a single core preemptive OS, you cannot truly feed messages into a queue in strictly chronological order. Even if you use a mutex to synchronize write access to the queue, the strict order is no longer guaranteed once multiple writers wait on the mutex and the mutex becomes free. At best, the order, in which the waiting write threads acquire the mutex, is implementation dependent (OS code dependent), but it is best to assume it is just random.

With that being said, the strict chronological order is a matter of definition in the first place. To explain that, imagine your PC has some digital output bits (1 for each writer thread) and you connected a logic analyzer to those bits.... and imagine, you pick some spot in the code, where you toggle such a respective bit in your enqueue function. Even if that bit toggle takes place just one assembly instruction prior to acquiring the mutex, it is possible, that the order had been changed, while the writer code approached that point. You could also set it to other arbirtrary points prior (e.g. when you enter the enqueue function). But then, the same reasoning applies. Hence, the strict chronological order is in itself a matter of definition.

There is an analogy to a case, where a CPUs interrupt controller has multiple inputs and you tried to build a system which processes those interrupts in strictly chronological order. Even if all interrupt inputs were signaled exactly at the same moment (a switch, pulling them all to signaled state simultaneously), some order would occur (e.g. caused by hardware logic or just by noise at the input pins or by the systems interrupt dispatcher function (some CPUs (e.g. MIPS 4102) have a single interrupt vector and assembly code checks the possible interrupt sources and dispatches to dedicated interrupt handlers).

This analogy helps see the pattern: It comes down to asynchronous inputs on a synchronous system. Which is a notoriously hard problem in itself.

So, the best you could possibly do, is to make a suitable definition of your applications "strict ordering" and live with it.

Then, to avoid violations of your definition, you could use a priority queue instead of a normal FIFO data type and use as priority some atomic counter:

• At your chosen point in the code, atomically read and increment the counter. This is your messages sequence number.
• Assemble your message and enqueue it into the priority queue, using your sequence number as priority.

Another possible approach is to define a notion of "simultaneous", which is detectable on the other side of the queue (and thus, the reader cannot assume strict ordering for a set of "simultaneous" messages). This could be implemented by reading some high frequency tick count and all those messages, which have the same "time stamp" are to be considered simultaneous on reader side.