Coding semaphores

[Candy]

@Candy: In fact you're speaking of a kind of "local" atomicity.

Yes and no. The atomicity is local, for as far as possible. There is a single operation that does require kernel help, that is blocking without allowing a moment of rest.

However I don't see the point here, maybe I am missing something. Since CLI/STI are not really required for semaphore (you could use spinning loops to avoid it, and that's how it works on multiprocessor systems), You could use semaphore at any level you like without any kernel code.

For a perfect semaphore (since a semaphore is only for security, it's useless unless perfect) you need to be sure that it works perfectly every possible way. If there is a way to bypass the semaphore, it will be used some time.

For user code, it's very inefficient to switch to the kernel and use a kernel-bound semaphore function. Using a userlevel semaphore function is a lot more efficient. The CLI/STI idea was only to make sure the cpu doesn't interrupt you in your semaphore modifying operation, so that every other thread would spin for a while. It's not required in any way, only a performance enhancement.

You CAN NOT block a thread using a kernel call if you're trying to take a semaphore in between. This is not perfect.

When an interrupt would occur during the short period of time that you have decided that you can not down the semaphore, and before you have called the kernel-block function, you'd be in state of limbo. If another thread was started at that point, and raised the semaphore, signalling all waiting threads (not you!), then letting you at it again, you block yourself and wait indefinitely for the semaphore that is there, but that you do not see.

However You will need some "system managed" semaphores for shared resources. But there again it may be implemented using a user task (aka server in my microkernel).

Could you be more precise ? Or explain, because I feel like I am missing something important.

I don't see why you would have to use a system-managed semaphore for a shared resource. In the case where you trust both sides (IE, you made them or something), you can use the userlevel function. In case of no trust, you cannot trust that the other will leave any objects intact, so you have to protect it all with a kernel interface anyway. In the paradoxal situation that you would have a shared object where you do trust the object not to be modified, but cannot risk the semaphore to be wrong, you have a point with a kernel-level semaphore. The only place I see this is shared memory between user programs, with a kernel semaphore that counts the usage.

But in that case, the entire map call is kernel bound, so you're in kernel anyway.

AFAIK we have two different types of semaphores, the kernel-level and the user-level. Those at kernel level can always be trusted to be right, are for kernel use only and protect kernel and user level things. Those at user level can always be trusted to be right, are for user use only, have kernel support for the atomic block and protect user level things.

[Candy]

Code: Select all

void Semaphore::p() {
   // this is to ensure atomic operation
   AutoLock _(SysLock::instance());
   if(--m_Value < 0) {
      block();
   }
}
void Semaphore::v() {
   // this is to ensure atomic operation
   AutoLock _(SysLock::instance());
   if(++m_Value <= 0) {
      unblock();
   }
}

AutoLock is a class which ensure no interrupts until it is deconstructed (goes out of scope), so this works very nicely. you can assume block/unblock add/remove threads from a block list and mark them as runnable/blocked, etc.

Theoretically, yes. Practically, only on uniprocessors. If you'd modify autolock to actually take a mutex (or something), shared by all processors on that kernel code, it's good.

Note that you lower the semaphore below zero, and then leave it there, so your implementation strictly speaking is not semaphores, but it works 100% the same.

now assuming i had proper dec_and_test and inc_and_test functions (using lock, etc), could i not implement these like this:

Code: Select all

void Semaphore::p() {
   if(dec_and_testl(&m_Value)) {
      block();
   }
}

void Semaphore::v() {
   if(inc_and_testle(&m_Value)) {
      unblock();
   }
}

the logic to decide to block or unblock is atomic (and that's the point where semaphores are vulnerable i beleive, so i think it would work assuming that block and unblock are atomic when modifying the threads and modifying the lists.

this way, the only time you need to truely goto kernel space is when you are block/unblocking..

is this correct?

Yes and no. What happens if the code where this is in is interrupted between the dec_and_test1 and the block()? By, for example, a thread executing the second function, seeing there is no thread waiting (signal does not signal threads that aren't blocked yet), and then your thread comes again, blocking itself while the semaphore is there.

[edit] why can't I post twice within 15 seconds? Then at least make the board accept my messages! [/edit]

[proxy]

Theoretically, yes. Practically, only on uniprocessors. If you'd modify autolock to actually take a mutex (or something), shared by all processors on that kernel code, it's good.

Note that you lower the semaphore below zero, and then leave it there, so your implementation strictly speaking is not semaphores, but it works 100% the same.

yea, right now i am trageting uniproccessor only, but what is nice is that i have abstracted all that locking out to a "SysLock" class (note that's what gets passed to AutoLock) so I just need to modify that to make it smp friendly

also as for the semaphore implementation, that's the way i learned it when i was in school. Also, my operating systems book (i forget the name, but it has 3 dinosaurs drinking coffee on the cover) demonstrates it this way (i think)..oh well, so long as it funcitons right

Yes and no. What happens if the code where this is in is interrupted between the dec_and_test1 and the block()? By, for example, a thread executing the second function, seeing there is no thread waiting (signal does not signal threads that aren't blocked yet), and then your thread comes again, blocking itself while the semaphore is there.

ahh, good point, well there goes my "fast semaphores" then on to my next speedup idea. thanks for the corrections

proxy