OSDev.org

The spinlock as it is now is pretty much useless in user space because of you can get a context switch inside the lock and then have unpleasant side effects due to that like priority inversion. In kernel space the spinlock is however often used and this always in conjunction together with disabling the interrupts. In kernel space this is often an acceptable solution and does not block interrupts for too long if used correctly on simple data structures.

I've seen that some processor manufacturers have implemented transactional memory like Intel TSX. The HW complexity of implementing this is probably pretty high. There have also been some studies that many lockless algorithms perform worse than the non-lockless version and just taking the lock. Also many processor designers refuse to go beyond the CAS and not even implementing a DCAS.

One question is how to enable the spinlock for the user space world as it is a simple but quite versatile if we can get it to work. So what I would think of is adding a functionality in the processor that allows user space processes to disable the interrupts for X amount of instructions ahead. The amount of allowed instructions allowed can be defined by the operating system by configuring the CPU. Each CPU could just have machine status register that counts the number of instructions inside the lock which is part of the context and of course cannot be altered by user processes. If X amount of instructions are reached inside the lock, a processor exception happens and the OS needs to decide what to do.

Have you seen such functionality in any more unusual ISAs? Do you see any pitfalls in with this functionality?

There are better ways to achieve that: First implement futexes. Implement a thread-local wantToLock variable. Before trying to acquire a spinlock a thread writes the lock's address into wantToLock. It then spins on the spinlock. When the scheduler resumes a thread it checks the thread's wantToLock variable. If it is non-zero it performs a futex-wait on that lock (and does not schedule the thread). When the scheduler suspends a thread that holds a spinlock it sets a ownerSuspended flag inside the lock. Threads that try to acquire the lock check for this flag and do a futex-wait if it is set (instead of spinning).

There are a few more details and optimizations you need to take care of but this general concept should work.

You do not have to know the number of required instructions in advance and the approach can be implemented on any architecture. The only disadvantage is that futex-wakes are required when a thread is interrupted while spinning. That should be rare though (otherwise spinlocks are not the right tool for the job anyways).

A futex is basically a semaphore with one part working in user space and one part in kernel space. Of course if no collision it will be very fast but if a collision happens you will have a long scheduler circus head of you delaying the the block threads (which means more unnecessary trenching in the kernel scheduler spending those cycles). Also you have still the possibility to be preemted inside the lock thus delaying those poor waiting threads even longer.

I more or less already have one of those semaphores in my OS and they work well for locking primitives where semaphores are suitable. However, for those quick spinlocks I still would like to have an all user space only solution without involving the kernel at all (unless they misbehave).

Read my post again. I'm not suggesting plain futexes. I'm suggesting a scheme where even short contention does not involve the kernel. The kernel is only invoked for long contention.

Well, ok semi-involving the kernel then. So you suggested if the thread holding the lock was suspended the lock sends the waiters into suspend as well.

Ok, this solves the problem with preemption inside the lock but with a possible penalty.

Hi, I'm doing really similar to your suggestion in your first post in my OS:
In my OS , my threads can acquire a " non preemptive" status . however, they must yield or block before a certain amount of time. Or else, they will get a "non-Preemption fault" signal.
You can use this signal to make your thread sleep on a futex.

Hi,

For 80x86; I'd recommend having a look at the "protected mode virtual interrupts" feature.

This feature (if you use it as a scheduler hint) means that if a user-space thread does "CLI" it clears the CPU's VIF (Virtual Interrupt Flag). When the kernel thinks it might want to do a task switch it checks VIF and decides if it should do the task switch or postpone the task switch, and if the task switch is being postponed the kernel can set VIP (Virtual Interrupt Pending). When user-space thread does "STI" it sets the VIF and causes an exception if VIP was set; and the scheduler uses that exception to do the task switch that was postponed.


Cheers,

Brendan