OSDev.org

I was wondering if someone could explain the necessary steps in thread-safing my kernel.
E.g.:
- What to do if multiple processes want to read from the same disk at once?
- What are spinlocks, when do I use them, and how?
- Same with deadlocks?
- What other steps do I need look into to thread-safe my kernel?

Hi!

- What to do if multiple processes want to read from the same disk at once?

Have a queue of sequential disk accesses. Each process spins until it's request is satisfied (out of cache or from the disk).

- What are spinlocks, when do I use them, and how?

Spinlocks are an implementation of mutual exclusion. I can't write an x86 one off the top of my head right now but they usually use the 'compare and exchange' instruction (in SMP, with the LOCK prefix)
It usually goes something like: is_the_lock_free() would be a function (all of this is usually in ASM) or instruction that can tell if the lock is free and then lock it itself for our use all before any other process can lock it. This requirement is called 'atomicity', and usually means that the function must comprise of exactly one CPU instruction.

Example, if the function is not atomic (note this is in C, you'd have to translate it to asm): Now, imagine that the lock is free. We do the 'if' test and come back true. Then we get preempted and another process gets the lock. We get executed again and execute the get_lock() function. This would overwrite whatever is in the lock already (can sometimes be more than just a boolean value) and we would be under the assumption that we have the lock, where we don't.

For that reason the 'if' and 'get' statements must be done together as an atomic set of operations. The x86 provides a cmpxchng instruction for this.

Spinlocks are used whenever mutual exclusion is required.

- Same with deadlocks?

Deadlock is different. Let's take an example.

Process P has resource A. Process Q has resource B.
Process P requires resource B to complete execution, however process Q requires resource A to complete execution (they both require both resources but have locked one each).

What we have there is called 'deadlock'. Neither process can progress. There are four things needed to avoid deadlock, and for the life of me I can't remember what they are. I know one is to avoid starvation, can't remember the rest. Combuster is an academic type, maybe he'll know (at work now so haven't got time to grep the internet).

- What other steps do I need look into to thread-safe my kernel?

Are you using multiple cores/processors or not?

I recommend you to read these pdf's:

http://www.osdever.net/tutorials/pdf/spinlocks_1.pdf
http://www.osdever.net/tutorials/pdf/spinlocks_2.pdf
http://www.osdever.net/tutorials/pdf/spinlocks_3.pdf

Thanks for the fast replies.

JamesM wrote:Are you using multiple cores/processors or not?

Not currently, but it might be on my to-do list in the future.

For every data structure that could possible be modified by two threads at once you need to protect it with a mutex/semaphore. Inside of the kernel you must also absolutely prevent deadlocks. Outside of kernel mode they are not as critical, you could always just close the offending processes. One way to avoid a deadlock is too force threads to always lock the data structures in the same order. Of course there are other ways too but I'll leave them up to you.

One of the classic ways to try and detect deadlock is to use phases. This is used by Sun's NFS and some other transactional algorithms.

A process starts by being in the 'locking phase'. He can lock anything he wants, but must lock everything he wants before doing any processing. Once he has done the processing, he releases the locks.

Or, a slightly different way (algorithm is slightly different), a process cannot gain another lock once it has released one (note that this is per-transaction, not over the entire life of the process!).

This way, although deadlock can occur (Deadlock only needs one of the four things I tried and failed to remember above to be lacking, so it damned difficult to prevent), transactions can be killed safely because no processing would have taken place.

I've found two other methods that also kind of suit the applications at hand:

For each lock, when acquiring it, add all the locks you have already to its collection, plus all the locks that those locks can be locked within. If any lock ends up having itself in its collection, you have a probable deadlock. This is based on the postulate that all the locks form a partial order <=> there is no possibility for deadlock. This method however, can be implemented and gives information what can go wrong. It does require you to thoroughly test all code paths and then check all collections. You can use a transitive closure to check for loops.

The second idea was to explicitly require a particular order in locks. The problem here is what you do when you try to lock a lock that is not in the right order - do you fail, warn and lock anyway or unlock the existing lock, lock this and then lock the other again? The first is obviously undesirable (maintenance heavy), the second doesn't help much and the third negates the point of locks.

I think I'm going for my first idea - just check whether you can form a loop in the first place. It can still warn you for deadlocks everytime you do a lock (check for myself in the transitive closure of my children) but it doesn't help against race conditions.