linux-kerneloperating-systemkernelsemaphoremicrokernel

how to implement semaphore without DI/EI, TS and CS instructions


I am reading the operating systems book by Milan Milenkovic (http://books.google.co.in/books?id=wbvHuTfiQkoC&printsec=frontcover#v=onepage&q&f=false). From this i understood how semaphore can be implemented using the following assembly instructions :

 1)Enable/Disable interrupts
 2)Test & Set instruction
 3)Compare & swap instruction

I want to know if there is some other way of semaphore implementation as well, other than using the 3 assembly instructions above. Any help will be greatly appreciated. Thanks.


Solution

  • You need to make your "check if the semaphore is set; if it isn't, set it, and tell me the previous state" operation atomic. If you wanted to implement a semaphore on a processor that has none of your 3 instructions, you could probably build some hardware around it. So, yes, there are other ways, depending on how far you want to go. If it's not in your processor, build it somewhere else.

    But for a practial answer: there's only 2 ways to do it. Either use something that makes a chain of multiple operations atomic (which is what enabling/disabling interrupts does, except NMI can't be disabled, and disabling interrupts on one core won't help you in a multicore environment), or use a processor feature that does the "check if the semaphore is set; if it isn't, set it, and tell me the previous state" thing atomically. Looking at it this way, your methods 2) and 3) aren't really different.