2
$\begingroup$

How does one implement mutex on a single processor system without using spinlock mechanism. Mutex is to be implemented in user space (for any user level library like pthread lib for example).

$\endgroup$
3
$\begingroup$

It is impossible to implement a mutex completely in userspace unless you have special CPU instruction that could simulate a semaphore or a lock (some "test and increment if true" instruction). pthread in Linux goes through the kernel to implement the mutex.

$\endgroup$
  • $\begingroup$ Are you suggesting I use some kind of atomic test and set instruction? But will that not be basically a spin lock? $\endgroup$ – CodeWithPride Feb 9 '15 at 21:18
  • $\begingroup$ No, if you test and fail, the running thread can go to sleep and wake up when the lock is released (i.e. you need a list of blocked threads in your mutex). Then the other threads can compete to grab the lock, again, everybody who fails goes to sleep. $\endgroup$ – randomsurfer_123 Feb 10 '15 at 17:04
  • $\begingroup$ Here's an implementation of a semaphore from NachOS: web.ics.purdue.edu/~cs354/Nachos/class_semaphore.html, as mentioned above - its done in kernel space, disabling interrupts. $\endgroup$ – randomsurfer_123 Feb 10 '15 at 17:07
  • $\begingroup$ I got what you are trying to say, thanks. $\endgroup$ – CodeWithPride Feb 11 '15 at 3:53
2
$\begingroup$

On a single processor system a spin lock won't work at all. There's only one processor so if that one processor tries to acquire a locked mutex, it will start spinning, and there will be no other processor available to unlock the mutex. The processor will be stuck spinning forever.

Rather on a single processor system one needs to use two other techniques. First, if the mutex is supposed to protect some data structure during interrupt handlers, then you achieve mutual exclusion simply by turning off interrupts during the critical section.

For mutexes used for "normal" threads when a thread (let's call it "A") tries to acquire a mutex and finds it locked, it calls into the scheduler which selects some other thread(s) to run for a while before retrying to run thread A. This can actually be viewed as a form of spinning (test the lock, find it busy, call the scheduler to run some other thread, eventually come back to me, test the lock again, and so on ...). So a slightly more sophisticated approach is to associate a queue with each mutex. When thread A tries to acquire the mutex and finds it locked, it places itself on the queue associated with the mutex, then calls the scheduler, which selects some other thread(s) to run for a while. Eventually one of those other threads unlocks the mutex. At that point the thread that unlocked the mutex removes thread A from the queue and places thread A in the schedulers "ready-to-run" list. Eventually the scheduler will decide to run thread A again, thread A will again try to acquire the mutex, and (unless someone else has locked the mutex in the meantime) will find it unlocked this time.

$\endgroup$
  • $\begingroup$ I understand what you are saying, bt the limitations I have is I dont have access to kernel resources, meaning I dont have the luxury to enable disable interrupts or decide the scheduling (scheduling is done by kernel and I dont have control on it). Only thing I can do is deschedule my current running thread. $\endgroup$ – CodeWithPride Feb 9 '15 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.