Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I like the command query separation pattern (from OOSC / Eiffel - basically you either return a value or you change the state of the class - but not both). This makes reasoning about the class easier and it is easier to write exception safe classes.

Now, with multi threading, I run into a major problem: the separation of the query and the command basically invalidates the result from the query as anything can happen between those 2.

So my question is: how do you handle command query separation in an multi-threaded environment?


Clarification example:

A stack with command query separation would have the following methods:

  • push (command)
  • pop (command - but does not return a value)
  • top (query - returns the value)
  • empty (query)

The problem here is - I can get empty as status, but then I can not rely on top really retrieving an element since between the call of empty and the call of top, the stack might have been emptied. Same goes for pop & top. If I get an item using top, I can not be sure that the item that I pop is the same.

This can be solved using external locks - but that's not exactly what I call threadsafe design.

share|improve this question
    
locks: if you only query get the read lock if you also command do a writelock –  ratchet freak Apr 3 '12 at 8:25
    
as far as I can tell, you can not rely on empty either - since nothing stops other threads from pushing something to stack after you invoked empty –  gnat Apr 3 '12 at 12:03

4 Answers 4

up vote 3 down vote accepted

With multithreading, you just can't separate queries and commands, unless you have an external lock which serializes calls.

The usual approach looks like this:

// query + command
// moves value at top into external thread-local storage `value`
// may fail and return `false`
bool ThreadSafeStack::try_pop(Value& value) 
{
    lock_guard guard(m_lock); // or `using(m_lock)`, `with m_lock:`

    if (m_stack.empty())
       return false;

    value = m_stack.top();
    m_stack.pop();
    return true;
}

But, you can use a hack: you can turn value into a member of the class.
Assume you have a data structure like this:

struct StackAndLock {
   Stack stack;
   Mutex lock;
}; 

Then you can create a ThreadSafeStack class:

class ThreadSafeStack
{
    Stack& m_stack;
    Mutex& m_lock;

    Value m_value;
public:
    ThreadSafeStack(StackAndLock& stackAndLock);

    void push(Value value); // command
    bool try_pop() // command, may fail
    {
        ...
        m_value = m_stack.top();
    }
    Value get_last() { return m_value; } // query
    bool empty(); // query
};

So you have one shared StackAndLock object, and multiple ThreadSafeStack objects, one per thread:

void thread_proc(StackAndLock& bundle)
{
     ThreadSafeStack stack(bundle);

     ...
     if (stack.try_pop())
     {
         ... stack.get_last() ...
     }
}

I can't say that it's such a great idea, but definitely it is Command-Query separation.

share|improve this answer
    
saving value inside doesn't work as well since between try_pop() and get_last() someone else could have called try_pop(). What might work is saving the value associated with a thread-id from the calling thread. This guarantees at least that you get the value from your try_pop() call. I'm not sure whether it's a great idea as well - but at least it's close. To be totally on the csq side, try_pop should throw an exception the error case instead of an error code (true / false) but that's hairsplitting. –  Tobias Langner Apr 4 '12 at 10:03
    
who is that "someone else"? please read it again, every thread has its own ThreadSafeStack, it's not shared across multiple threads. –  Abyx Apr 4 '12 at 11:33
    
sorry - I overread this. But if you have one stack per thread, you don't need a threadsafe stack. The main reason of having thread safe data structures is that different theads can access them safely to exchange data. –  Tobias Langner Apr 5 '12 at 5:11
    
@TobiasLangner, no, you still don't get the point. There is StackAndLock which contains actual stack object, and ThreadSafeStack which provides thread-safe access to that stack. Thus, different threads access one shared Stack object via their local ThreadSafeStack objects. –  Abyx Apr 5 '12 at 8:29
    
now I understand your solution. Thank you. –  Tobias Langner Apr 11 '12 at 14:50

Your comments have helped. I'll try a new perspective. New answer has two parts: 1. Some commands must return success or failure. I understand that traditionally commands should not return values, but things get really awkward if you don't allow at least a boolean success result. 2. Documentation. You must explain to users of your API that a value returned from a query simply means that value existed at the time of the query, and it may have been invalidated immediately after the query. Thus a query can be considered an absolute fact about the past, but only a hint about the future.

For the stack example, the API might look like,

  • push(value) (command, always succeeds)
  • pop(value) (command, succeeds if value could be popped)
  • top() (query, returns two things: top value and empty boolean. value is undefined if empty = true)

That's not a conventional pop command, but a pop command with no value specified or with no success result would be pointless. It would be a command to make a change to the stack without the caller having any way to know for sure what change, if any, was made. Also, top() must return some status about whether there was a top value.

Your implementation of the API is responsible for data synchronization. "External" locking (I wasn't appreciating what you meant by external before) is not required by users of your API. In your implementation, you can use whatever synchronization is available to you in your language.

share|improve this answer

Short answer is use synchronization for all access to shared data.

Locks allow synchronization and using locks is a threadsafe design. It's not a design that does the locking for you or that prevents errors in your locking code, but it is a design that allows you to write correct multithreaded code.

Note that synchronization isn't just needed to sequence commands. A query can return a corrupt value, or a command can corrupt your data structure. In a multithreaded situation, all accesses to shared data should be synchronized. Locking is a valid way to do this and Aybx's StackAndLock struct is a standard technique. There are lower-level techniques, such as CAS, but even with locks, you have to write code that uses the locks correctly. Higher level techniques involve using libraries (or better yet, languages) that implement things like STM, Actors, CSP, or other sorts of message passing.

share|improve this answer
    
no - I think you miss the whole point here. With CQS it is not trivial to write a class that is safe to be used from different threads. Doing the locking from the outside is not a good idea, because someone will mess it up. –  Tobias Langner Apr 11 '12 at 14:52

there are 2 main approaches

  1. external read/write locks as I said in the comments

  2. "failable" commands like the classic CompareAndSwap

    bool CaS(from,to){
        if(from==state){
            state=to;
            return true;
        }
        return false;
    }
    

    however this can result very large functions for non-trivial problem flow

share|improve this answer
    
external locks are not threadsafe design and what I'm searching is the best design to handle 2 without getting hard to understand code or an interface that is hard to handle correctly. –  Tobias Langner Apr 3 '12 at 9:23
    
you can have the operation throw exceptions when the lock isn't held when called but that doesn't solve much –  ratchet freak Apr 3 '12 at 9:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.