Putting threads to sleep using semaphores

[uma]

I have a sleep function where each thread is put to sleep using busy wait. I want to now use semaphores instead of busy wait. How do i make a thread block using semaphores for a certain amount of time ?

[max]

I have a sleep function where each thread is put to sleep using busy wait. I want to now use semaphores instead of busy wait. How do i make a thread block using semaphores for a certain amount of time ?

Are you really doing "busy waiting" in the sense of letting it do other stuff while its waiting or are you while(locked)-looping with yields?

Generally you make a thread sleep by taking it out of the scheduling list/skipping it when scheduling. You could for example have a bool for each semaphore in your kernel space, remember what semaphore the task is waiting for and when scheduling you check the value, if its set skip the task.

[dansmahajan]

How do i make a thread block using semaphores for a certain amount of time ?

Ultimate goal of semaphore is mutual exclusion i.e no more than one task should have access to a particular resource, then why you want to have a time constraint on it ??
Moreover if you want to block a process for a certain time then why you want to use semaphore, you could make a process sleep by implementing a sorted/ordered list of sleeping tasks in kernel. This is the way how I've implemented process sleep function.

[Gigasoft]

A semaphore is a perfectly fine way of implementing a sleep function. The obvious, but naive method of setting a timer and blocking the thread, and resuming the thread when the timer expires, may lead to race conditions if you are not careful. For example, consider that the thread might become preempted after the timer is set, but before it blocks, with the timer expiring before the thread gets a chance to block.

To implement sleeping using a semaphore and a timer, you initialize the semaphore and set the timer, then wait on the semaphore. When the timer expires, the semaphore should be released.

As for how to actually implement semaphores, it's a bit tricky, especially on MP systems. On x86, the XADD, XCHG and CMPXCHG instructions will be your friend. When waiting on a semaphore, you want to be sure that the semaphore hasn't been already released, and you need to manage a list of which threads are waiting for each semaphore, while taking into account that another thread may be accessing the same data at any time.

[Brendan]

Hi,

I have a sleep function where each thread is put to sleep using busy wait. I want to now use semaphores instead of busy wait. How do i make a thread block using semaphores for a certain amount of time ?

Somewhere in your scheduler you will have code to determine which task to give CPU time to next. This code must not choose any task that is blocked for any reason.

Your scheduler will use some sort of data structure/s (maybe a list or queue of tasks, maybe some sort of tree, maybe multiple queues, whatever). If these data structures include tasks that are blocked, then scheduler has to check if task/s are blocked or not and skip them if they are. A more efficient way is to avoid that, and only put tasks that are not blocked in the scheduler's data structures, so that the scheduler doesn't need to check if a task is blocked or not.

Now...

Currently you want a thread to block for an amount of time. Sooner or later you'll want a thread to block waiting for some sort of IPC (message, pipe, whatever), or waiting for IO (a file, a network connection, etc). Then you might want something like "block until a debugger running in a different process says to unblock", or "block until virtual memory manager gets a page from swap space".

Basically; there's many reasons for a task to block. Waiting for a mutex or semaphore is just another reason to block, but it has nothing to do with any of the other reasons.

Also, at some point you will need to combine the "reasons for blocking" in various ways. There are 2 ways that they may be combined - either you're waiting for any one of a group of reasons (e.g. "wait until network packet arrives or a time-out expires, whichever happens first"); or you're waiting for all of a group of reasons (e.g. "wait until network packet arrives and a certain amount of time has passed, and don't unblock until both have happened").

Let's consider "waiting for all of a group of reasons" first (as it's easier). Please note that this includes a "group of 1 reason" (e.g. waiting for time to pass and nothing else). Now, imagine if each task has a set of flags; where each flag represents a different reason for blocking - one flag for "waiting for time", one flag for "waiting for data from swap", one flag for "waiting for IO", etc. If you want to wait for "all of a group of reasons" you set the flag for each reason, then various things (e.g. the timer, the file system, whatever) clear the flags when each of the things happens, and when all flags are clear the task isn't waiting for anything anymore.

With this in mind your scheduler can have 2 functions - one to set "reasons for blocking" flags and one to clear them. These 2 functions take care of the blocking/unblocking. For example:

Code: Select all

void setBlockedFlags(thread_data *thread, uint32_t flags) {
    if(thread->blockedFlags == 0) {
        // Thread wasn't blocked before, so it has to be removed from data structures that the
        //   scheduler uses to keep track of "ready to run" tasks here.
    }
    thread->blockedFlags |= flags;
}

Code: Select all

void clearBlockedFlags(thread_data *thread, uint32_t flags) {
    if(thread->blockedFlags == 0) {
        return;        // Thread wasn't blocked so do nothing
    }
    thread->blockedFlags &= ~flags;
    if(thread->blockedFlags == 0) {
        // Thread is now unblocked, so it has to be added to the data structures that the
        //   scheduler uses to keep track of "ready to run" tasks here.
    }
}

With this in mind, your "sleep()" function may add the task to a list of tasks waiting for time and do "setBlockedFlags(thread, WAITING_FOR_TIME);". Eventually (when the time has passed) your timer code would remove the task from the list of tasks waiting for time and do "clearBlockedFlags(thread, WAITING_FOR_TIME);".

That only leaves "waiting for one of a group of reasons". This isn't that hard to add - the code might look a little like this:

Code: Select all

void setBlockedFlags(thread_data *thread, uint32_t allFlags, uint32_t anyFlags) {
    if(anyFlags != 0) {
        thread->blockedForAnyFlags = anyFlags;
        allFlags |= BLOCKED_FOR_ANY_MASTER_FLAG;
    }
    if(thread->blockedForAllFlags == 0) {
        // Thread wasn't blocked before, so it has to be removed from data structures that the
        //   scheduler uses to keep track of "ready to run" tasks here.
    }
    thread->blockedFlags |= allFlags;
}

Code: Select all

void clearBlockedFlags(thread_data *thread, uint32_t flags) {
    if( (thread->blockedForAnyFlags & flags) != 0) {
        // One of the "blocked for any" flags is being unset, so they all get unset
        thread->blockedForAnyFlags = 0;
        // And the master flag needs to be unset too
        flags |= BLOCKED_FOR_ANY_MASTER_FLAG;
    }
    if(thread->blockedFlags == 0) {
        return;        // Thread wasn't blocked so do nothing
    }
    thread->blockedFlags &= ~flags;
    if(thread->blockedFlags == 0) {
        // Thread is now unblocked, so it has to be added to the data structures that the
        //   scheduler uses to keep track of "ready to run" tasks here.
    }
}

This actually allows some "combinations of combinations". For a random example, it could easily handle "block until debugger says it's OK to continue AND mutex is acquired AND (networking packet arrives OR time-out expires)".


Cheers,

Brendan

[AndrewAPrice]

A spinning lock is useful in a SMP setup, but in a single CPU setup you may as well put the thread to sleep because the lock isn't going to unlock itself while it's "spinning" as other processes/threads holding that lock won't be releasing then as it's not their time slice.

[Gigasoft]

A spinning lock is useful in a SMP setup, but in a single CPU setup you may as well put the thread to sleep because the lock isn't going to unlock itself while it's "spinning" as other processes/threads holding that lock won't be releasing then as it's not their time slice.

A semaphore may be protected by a spinlock, but you can not protect a semaphore with another semaphore. That won't work. If you need to lock the semaphore structure while initiating a wait, interrupts should be disabled, or you'll have a problem if an interrupt handler tries to release the semaphore in the middle of your wait function.