Boost logo

Boost Users :

Subject: Re: [Boost-users] [Thread] Writer/Reader strange scheduling
From: Ovanes Markarian (om_boost_at_[hidden])
Date: 2010-08-11 12:08:33

On Tue, Aug 10, 2010 at 6:03 PM, Stefan Strasser <strasser_at_[hidden]>wrote:

> [...]

> That was clear to me, still I think, I don't know who fault is, having a
>> reader
>> waiting and then being scheduled is a waste :D
>> I guess I'll write one my self.
> don't you need OS support for this kind of scheduling?
> I guess you can write a mutex in userspace that only "preserves order", but
> as long as you still want threads to be scheduled based on workload/time
> slices Í think you need an OS scheduler supporting shared mutexes to improve
> this situation.
Actually, I think you don't need OS scheduler support. Rethinking of that
idiom might help. Imagine, you have tasks to be executed by a thread pool.
What you get from the thread pool are the futures to the task execution. If
so you only need to write a scheduler how the tasks are re-arranged in the
thread-pool-queue after being enqued. It might become more difficult or even
impossible to do some kind of pre-emption, e.g. what should happen if some
task (with 'lower prio' or 'higher id') was enqued in the wrong order and
started the execution. Now the task which should execute before was enqued.
What do you do? Preempt? It might be impossible to preempt the lower-prio
task. The only possibility I can imagine is to introduce explicit check
points in the task itself and pause the execution when signalled and let the
higher prio task run. Even if it is possible, the low prio task must free
shared resources, like mutex-es, since otherwise there might happen a
priority inversion or even deadlock.

In you special case you can do smth' like: Introduce 2 priority queues:
Q1 for the reading tasks
Q2 for the writing tasks

Using reader-writer-lock, you are able to execute as many reader as there
are thread in the pool or only one writer. Now the logic is:

A: if Q2 is empty execute all reading tasks that are possible from Q1
B: if Q2 is !empty compare heads of Q1 and Q2. If Q1 has reader with lesser
id execute all reading tasks that possible, otherwise execute a single
writing task and goto point A.

This is simplified logic, since you have to ensure that no readers else are
running, if you are going to execute a wirter and that no reads are
scheduled if writer is pending.

That's it.


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at