call back queue thread safe while ensuring low wait times

During interview this was asked: design callback queue thread-safe while guaranteeing low wait times have some kind of fairness. There are multiple threads which registers call back function for different events. Maintaining registered call back function is easy as we can maintain event to call back function/s. I am not sure what is right way of solving this problem. I am thinking we can have lock for this data structure which keeps mapping of event to callback. Any thread my lock mutex and update mapping information. I am not so sure about wait time part of question. Also how do we notify, basically if event is received in main thread, shall we notify call back functions from main thread directly or signal by using message. I went through this post C++11 thread-safe queue where they are talking about thread safe queue but it does not fit in to this case.