Sign in to follow this  
SirLuthor

Wait Functions & Sleep(...)

Recommended Posts

SirLuthor    364
Hello once again, kind people, as I intrude upon you once more to seek answers to questions that bang around in my skull! Avail me, and you shall have my undying gratitude. For the next few days, anyway... OK, so, here's the deal. I've been working and designing (well, trying to) some multi-threaded junk lately. That's all well and good. However, I have come to a problem/point of curiousity which I'd like an answer for. Let's imagine that I have a spate of atomic variable functions, utilizing inlined assembly (CMPXCHG). Now, with those as a basis, I then implement some useful classes such as a local resource lock, or a mutex on steriods, or something else. Now, here is where my curiosity comes in. I know Windows has a lot of built in waiting functions which can be used to wait on the good 'ol mutexes (mutices?) semaphores, events, etc., but if I had my own mutex class, I would need a suite of waiting functions for it. And to have a waiting function, there are a couple of important things that you need to have in them. Firstly, and probably most importantly, you have to be able to tell the operating system, in my case Windows (only), that the thread is waiting on a locked resource, and should switch to another thread. There is the ubiquitous Sleep() function, but I have heard more then it's fair share of bad things about it, such as there being no real way to tell how long it will be before the thread gets priority again, etc. So I kind of need a way to tell the Windows thread schedular that it can and indeed immediately should switch threads. Without a way to do that, I'm either doomed to using Sleep or simply trashing this idea, and going with the one outlined below. So that's one way of doing things. Alternately, I could reinvent the wheel in a really big way, and run everything in 2 threads, the main thread, and an extra thread. The main thread would then split into many fibers, which would be scheduled by the extra thread. And these fibers would function as 'threads' for my purposes, as well as allowing me more control over them. But then again, of course, this involved a whole lot of reinventing that I'd rather avoid if possible. So, insults, opinions, clever insights, and possibly, just maybe, an answer, would be greatly appreciated! Thanks again!

Share this post


Link to post
Share on other sites
iMalc    2466
I don't get it. Why would you want to drop down into assembly when you can simply use "Critical Sections"?
You can't effectively implement the mechanisms for dealing with thread waiting or scheduling etc. Only the operating system can do that. All the necessary stuff is already done by the OS for you to use. Many cases such as when a thread causes a page fault, already automatically give time to other threads.
If you don't want to reinvent stuff, then why are you trying to duplicate parts of the OS? Don't duplicate these, simply encapsulate them.

Just use Sleep when appropriate, and never mind the drama-queens that say otherwise.

Share this post


Link to post
Share on other sites
nmi    978
Basically there are two ways to wait for doing mutual exclusion.

1)
First one is busy waiting (using spinlocks), where a flag is polled via test&set/cmpxchg or something similar. This is used for very short critical sections, especially for multiprocessor systems. Here it is very unlikely that two threads want to aquire the thread at the same time. Care must be taken that the thread that aquired the lock is scheduled away while inside the lock, since then the waiting threads will eat up cpu time.
A possible implementation might look like this:


volatile bool locked = false;
...
// wait while locked, try to perform atomic test and set
// testandset() will set the flag to true and return the previous value
while (testandset(&locked))
{
// busy waiting on smp machine or
// yield to other thread on single processor machine
...
}
...
// critical section code
...
// free critical section
locked = false; // assignment should be atomic


To perform an atomic test&set operation, machine instructions like xchg, bts, cmpxchg or similar may be used. On some systems (i.e. most microcontrollers) such an operation may not be available. In this case the operation can be made atomic by locking interrupts. For x86 systems this method works fine.

One thing that will be problematic are multiprocessor systems with shared memory. Here the same memory location may be modified by more than one processor at the same time, resulting in undefined behavior if bts is used for instance. In this case locking the memory bus becomes necessary. The xchg instruction does this automatically. The result is that the code above will block memory accesses by other processors while doing busy waiting for the flag. This can prevented by a slight modification. Instead of doing test&set all the time, the loop waits until the section was free, then tries to atomically aquire the lock:


volatile bool locked = false;
...
while (1)
{
// wait until section was free
if (locked)
{
// for single processor system yield to next thread
...
// was locked, try again
continue;
}

// is free now, try to perform atomical test&set, lock the bus when doing this
if (testandset(&locked) == false)
{
// got the lock, break the loop
break;
}
}
...
// critical section code
...
// free critical section
locked = false; // assignment should be atomic


As you can see, things are not that easy. Windows provides functions for this that will do the right thing depending on which hardware your application runs on. On the other hand a custom solution may provide a faster implementation, especially when you can inline this assembler opcode. Since busy waiting is used for critical sections where chances are high (i.e. 99%) for the section to be free when trying to lock it.


2)
The second solution involves putting a thread to sleep while waiting for something to happen. This is used when waiting for user input, data read from a disk or similar. WaitForSingleObject() and the other functions are right for this task. Since putting a thread to sleep and waiting it up again needs some time when compared to spinlocks, it may slow things down when done very often or it may result in a high latency. For very short critical sections this would be the wrong choice.

Share this post


Link to post
Share on other sites
SirLuthor    364
@John Bolton: Yes, I was previously aware of those, however, if you peruse my post again, and perhaps take a moment or two to digest the information given, as well as the question asked, it would be awesome, as your answers, in general, are good ones [smile] I cannot use those wait functions, because they have to wait on a handle, and with a home-rolled local lock, or whatever, a handle is one of the things I do not have.

@iMalc: I am not against the use of critical sections. I don't believe I ever said that [grin] They have a place, and I assure, you they will be used where I feel they should be, but I don't actually see what that has to do with my question? But thanks anyway for the point of view, more of those are always welcome!

@nmi: Thanks man, that's a nice informative post there.. Albeit, not entirely new information to me, seeing as I did some of the foot slogging on this one before posting, but nice nonetheless. I'll have to look for some more info regarding atomic actions and multiprocessor systems...


Seems the general concensus is, don't reinvent, encapsulate [grin] I guess I'm always on the side that isn't the public opinion...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Quote:
Original post by iMalc
[...]You can't effectively implement the mechanisms for dealing with [...] waiting[...]
Sure you can, just not without using some OS constructs.
For custom mutexes/etc, one way to implement waiting would be create an Event object along with your custom mutex, and for the wait function do
while(!AttemptMutexAcquire()) WaitForSingleObject(MutexAvailableEvent);
Then modify the 'ReleaseMutex()' function to signal the event after it does the release.
Events are perfect for this cause, because that is essentially all they do. They were practically (if not actually) designed so user code can implement waits on custom conditions.

As for avoiding using the already-implemented CriticalSection or Mutex, the two possibilities are flexibility and efficiency. The locks that windows provides aren't very flexible, and from everything I've read they aren't very fast in the simple cases because there are some often-possible assumptions they don't make.

-Extrarius

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this