Semaphore with a timeout

[proxy]

My OS is generally coming along nicely, and one thing that I want to implement now is the ability to block, but with a timeout. One of my major API pet-peeves is when a function can block, but there is no way to specify a timeout. (linux wait() comes to mind as particularly annoying). So I would like to get this right before implementing most of my system calls.
Currently, my scheduling design is as follows:

there is an array of run-lists, (one for each priority level).
when a thread becomes blocked, it is NOT queued into a run-list. Instead it is expected to be held in some semaphores wait queue.
to wake a thread, the semaphore marks the thread as runnable and en-queue's it into one of the scheduler's run-lists.

This works great, and is efficient since the scheduler doesn't need to even look at blocked threads. But it makes the idea of implementing a timeout a little less obvious.

So, thoughts about timeouts:

Clearly each scheduler tick (or some fixed interval), the scheduler needs to test blocked threads to see if enough time has passed that they need to wake up.
But my scheduler doesn't have an explicit list of blocked threads. Even if it did, Threads don't have any knowledge of which semaphore (if any) is "holding it". So I would need to add some extra data to threads.

I could implement things this way:

Threads would have a pointer to a semaphore which asked it to block, or null if it is runnable.
When a semaphore blocks with a timeout, the scheduler will put the thread into a special "sleepers" list, which gets checked routinely (no need to specially threat threads that block forever)
if the scheduler sees a thread that needs to be woken up, it gets the owning semaphore from it, removes the thread from its list, marks the thread as runnable and finally put it into the runqueue.

While I believe this would work, It doesn't strike me as a very clean or efficient design. So I was wondering how (if any of you have) you guys have implemented blocking with a timeout.

[gerryg400]

Your idea of the scheduler not knowing or caring about blocked threads is good. Stick with that. Whenever a thread is to block on a semaphore with a timeout you should create a timer object and queue that in your timer queue. The timer will contain a reference the the thread. When the timer expires grab the thread from the semaphore queue and schedule it to run. No need to periodically do anything other than check for expired timers. (which you probably do anyway).

[Owen]

Create a structure of blocked threads (Preferably using fields in the thread structure), sorted by wakeup time (Some sort of ordered tree might be a good data structure here). Each scheduler tick, the scheduler looks at this queue, and walks through it in order looking at the desired wakeup time. If that time has expired, then it wakes the thread; otherwise, it is done and can stop looking

[Gigasoft]

In my OS, blocking with a timeout is trivial, since timers normally release a semaphore when they expire (as one of several options), and it is possible to wait for multiple semaphores at once, which is something you'll probably need sooner or later anyway.

[Brendan]

Hi,

I normally give each thread a set of "reasons why it's blocked" flags. Then I implement functions to set and clear these flags, sort of like this:

Code: Select all

setBlockedFlag(uint32_t flags) {
    currentlyRunningThread->blockedFlags = flags;
    findSomeOtherThreadToRun();
}

clearBlockedFlags(threadID threadID, uint32_t flags) {
    threadInfoThing *threadInfo;

    threadInfo = getThreadInfo(threadID);
    if(threadInfo->blockedFlags == 0) return;  // Thread wasn't blocked anyway
    threadInfo->blockedFlags &= ~flags;        // Clear the relevant flags
    if(threadInfo->blockedFlags == 0) {
        // Thread was unblocked
        if( this thread's priority is higher than the currently running thread's priority ) {
            // Preempt currently running thread
            switchImmediatelyToThread(threadID);
        } else {
            // Add the unblocked thread to the scheduler's ready to run queue
            addToReadyToRunQueue(threadID);
        }
    }
}

Once this is done I can define any flags I want. I could set several flags and block until only one of those things have happened (where each thing clears all the flags and the thread unblocks as soon as any of the things happen); or I could set several flags and block until several things have all happened (where each thing clears one flag, and the thread remains blocked until all flags have been cleared).

For example, I might have:

• a "BLOCKED_SLEEP" flag
• a "BLOCKED_SEMAPHORE" flag
• a "BLOCKED_SEMAPHORE_TIMEOUT" flag

In this case, the kernel's timer would do "clearBlockedFlags(threadID, BLOCKED_SLEEP | BLOCKED_SEMAPHORE_TIMEOUT)", and the kernel's semaphore code would do "clearBlockedFlags(threadID, BLOCKED_SEMAPHORE | BLOCKED_SEMAPHORE_TIMEOUT)".

The kernel's "sleep()" code would do "setBlockedFlag(BLOCKED_SLEEP)" which means that the only thing that will unblock the thread is the kernel's timer.

The kernel's "get semaphore without timeout" code would do "setBlockedFlag(BLOCKED_SEMAPHORE)" which means that the only thing that will unblock the thread is the semaphore.

The kernel's "get semaphore with timeout" code would do "setBlockedFlag(BLOCKED_SEMAPHORE_TIMEOUT)" which means that either the timer or the semaphore code will cause the thread to be unblocked.

Then (if I wanted to) I could have a "get semaphore and wait" function that does "setBlockedFlag(BLOCKED_SEMAPHORE | BLOCKED_SLEEP)", where a task will block until both things have happened (and won't unblock when only one of the things has happened).

The main benefit here is that you don't need to touch any of the scheduler's code to add new flags.


Cheers,

Brendan