OSDev.org

Posted: **Fri Aug 25, 2006 2:11 pm**

hi,

sorry for just opening another thread about that topic, but I don't think that this fits within the other thread...
is it possible to implement mutexes/semaphores in userspace? I have read about this idee some time ago, but I could not find an implementation of them, so I tried to come up with my own. But I couldn't come up with an implementation that seemed to be right. My latest implementation of a mutex looks like this:

Code: Select all

class mutex
{
public:
   inline mutex(bool locked=false)
      : mAtom(locked ? 0 : 1){}
   inline void lock()
   {
      while (true)
      {
         if (mAtom.compare_and_exchange(1, 0)return;
         mLock.lock();
         mList.push_back(getThreadId());
         mLock.unlock();
         suspendThread(0);
      }
   }
   inline void unlock()
   {
      mAtom = 1;
      mLock.lock();
      if (mList.size() != 0)
      {
         resumeThread(mList.back());
         mList.pop_back();
      }
      mLock.unlock();
   }
private:
   atom mAtom;
   spinlock mLock;
   std::vector<unsigned long> mList;
};

I think the implementation details of atom & spinlock aren't that important, so I leave them ou here. What is important is the problem that I can see:
If one thread (which trying to lock the mutex) is interrupted right before it can suspend itself and then the other thread (which has the mutex) calls resumeThread(...) with the right threadid. Then the other will never be woken up.
Is there anything you could think of, that could solve this problem (without adding other syscalls to the kernel)? If not, what syscalls do I have to add (I still want to do most things in userspace though, although I will add a kernel api for mutex & semaphores)?

Another question: Is it acceptable to disable all interrupts within a microkernel? I'm quite unsure about that.

Thanks in advance!

Posted: **Fri Aug 25, 2006 3:54 pm**

You need to have some data associated with the suspend operation, so that the kernel can check it atomically before putting the thread to sleep. In the Linux kernel, this would be current->state; however, it's a little more complicated in user space.

A simple way to do it with POSIX syscalls would be to use a signal as the associated data; the blocker does a sigwait, and the caller sends a signal to wake up the blocking thread. If the signal gets sent before the sigwait is called, then the sigwait does not block.

Another way (if you don't have or don't want to use signals) is to have the kernel check the lock word or a blocking state word itself. For the latter, it wouild basically go like this:

1. Thread A sees that the lock is held.
2. Thread A queues a blocking state object on the list, initialized to BLOCKED.
3. Thread B preempts A.
4. Thread B releases the lock, and sees that there are blockers.
5. Thread B sets the blocking state object to UNBLOCKED.
6. Thread B calls the kernel to wake the thread (though in this case it hasn't yet suspended, so this is a no-op).
7. Thread A resumes, and calls the kernel to block on the state object.
8. The kernel sees that it has been set to UNBLOCKED already, and returns without blocking thread A.

You'd need to make sure to pin the page containing the data that is shared between userspace and the kernel, so that you can atomically check it without worrying about page faults (though the page only needs to be pinned while a block syscall is in progress).

As for disabling interrupts, if you mean from inside the microkernel, then it's probably unavoidable in certain places, but shouldn't be done excessively (just as in any other type of kernel). If you mean from userspace servers, that would generally be a bad thing.

OSDev.org

userspace mutex/semaphore

userspace mutex/semaphore

Re:userspace mutex/semaphore