Spinlocks & Semaphores

[DarylD]

Okay, I have got my memory allocator working now, its allocating/freeing and coalescing. It looks like its working pretty well.

Now, the problem I am getting (which I knew I would) is I am not protecting data structures from being mashed by other threads or (in this case) interrupt routines.

So basically what is happening is this, code enters section and starts modifying my object list, interrupt occurs, interrupt routine then starts modifying the object list, result..clobbered data and page fault.

I know this is the cause, because if I wait until the idle loop before pressing a key (which triggers a message, which is created in the object list), everything is fine, *BUT*if I press a few keys quickly it gets clobbered.

I should add that I am only task switching every second to catch things like this.

So, spinlocks are a multiprocessor way of protecting critical regions, but can also be used on uniprocessor machines to protect regions (if the code is not allowed to be pre-empted during the critical region otherwise deadlocks will happen pretty quickly.)

So what I am asking is, is this the best way?? (From my understanding I could use semaphores but they would seem to be used for a different purpose, i.e. waiting on resources)

[Pype.Clicker]

you usually use a semaphore when you expect the waiting time to exceed the cost of a suspend ...
If you're on a uniprocessor system and want to get sure you won't be interrupted for a very short time slice (for instance, while updating a page table entry or something alike), the best way around is to disable temporarily interrupts.
As you cannot be preempted if the timer IRQ is blocked, a single "CLI" makes your update safe. On a multi-processor system, CLIing must be completed with a spinlock, but spinlocking on a single processor usually gives very bad results, because if the resource is currently used, your time slice will be waisted with busy-waiting.
The idea behind spinlocks is that *the thread that ownz the resource is actually running on a CPU* so your waiting time is bounded by the "resource holding time" (longest run in the critical section).

[Pype.Clicker]

and, btw, if you need some kind of reference implementation, you can get a look at clicker's koLib.share.sem for semaphores or kernel.sys.mutex for kernel (spin)locks.

[DarylD]

But could I use a spinlock on a uniprocessor? After all it won't do any harm, as long as I don't let the thread be interrupted while holding one (to stop a critical region blocking other threads)

If I use cli/sti within the spinlock code won't it work on uni or multiprocessors??

On a uniprocessor if I do it properly I won't have the processor spinning waiting for it to be released, it will just work like a critical section (surrounded by cli/sti)

I will look at your code, see if it gives some useful insight!

Daryl.

UPDATE: I have decided on a mechanism to use as follows:

Each major subsystem which will be accessed from multiple modules (i.e. object manager) will have its own lock/unlock function call, using spinlocks or semaphores as necessary.

I will only disable interrupts during the lock/unlock.

If any hardware interrupts occur, I will delay execution of the interrupt procedure until the lock has been released to avoid deadlocks.

Should do the trick!

(I will also use specific critical section/spin lock code as well, but for localised locks (i.e. inside a module))

[Slasher]

have you tried messge passing? it performs both process communication and critical section protection. (depends on your system design!)

[DarylD]

Well, my kernel does have a messaging subsystem, currently it is just used to send keypresses to the debugger (well, its not a debugger yet!)

To be honest, I coded in locks and now I am getting inexplicable freezes due to what I assume is deadlocking, I am not handling nested locks properly yet though.

I am also undecided on whether to allow task switches while locks are held. This is a problem on my kernel because everything is an object and a lock on the object manager will pretty much kill all kernel calls until it is released, so switching tasks while this is held will probably kill performance in the future.

Okay, how would message passing help with the critical section problem, you don't mean semaphores??

[Pype.Clicker]

have you tried messge passing? it performs both process communication and critical section protection. (depends on your system design!)

and how will you implement message passing if you don't have critical sections (or something alike) to prevent concurrent access to message queues ?

[Slasher]

hi,
Everything in my kernel at the moment is accessed through a SERVER-CLIENT model. If you want keys from the keyboard you send a message to the keyboard server, if you want memory just call the memory allocator, want the timer to perform a function after X seconds, send message to timer server, and the list goes on.
It's my understanding that this kind of approach would eliminate deadlocks.
I'm using a mailbox system and while accessing my queues, i disable ints for a VERY short Times (a few instructions)
I'm open to critisisms and suggestions of course

[Pype.Clicker]

hi,
Everything in my kernel at the moment is accessed through a SERVER-CLIENT model. If you want keys from the keyboard you send a message to the keyboard server, if you want memory just call the memory allocator, want the timer to perform a function after X seconds, send message to timer server, and the list goes on.

hmm, imho, you should draw a line somewhere. Sending a message to request memory allocation seems nonsense... it will lead to useless overhead, especially if the client and the server happen to be separate threads.

It's my understanding that this kind of approach would eliminate deadlocks.

Watch out: i've been myself using some message queue. Don't have a wait4post and wait4read in the same thread or you might be dead.

I'm using a mailbox system and while accessing my queues, i disable ints for a VERY short Times (a few instructions)
I'm open to critisisms and suggestions of course

What if you have multiprocessors ?

[Slasher]

hmm, imho, you should draw a line somewhere. Sending a message to request memory allocation seems nonsense... it will lead to useless overhead, especially if the client and the server happen to be separate threads.

Messages are not sent for MEMORY ALLOCATION (said so in the post above!

if you want memory, just call the memory allocator

i.e malloc,free)

Watch out: i've been myself using some message queue. Don't have a wait4post and wait4read in the same thread or you might be dead.

I haven't had problems so far with my message passing. Don't have a wait4read or etc. Just implemented a Send and Receive system.
Send is NON_BLOCKING so this avoid deadlocks - messages that are not fully delivered are queued at the mailbox and the sending process continues execution
Receive is BLOCKING so if a process does a receive and there are no messages waiting, it is queued at the mailbox waiting for the next message to arrive and another task is scheduled for execution.
From what i've described, is there still a change for deadlock with this system? :-\

What if you have multiprocessors ?

Haven't given multiprocessors too much thought. Have to perform some researh on them. But right now, i'm learning to WALK and not RUN so not too bothered ;D

[DarylD]

Right, sorry to bug the brains around here once more (Pype, df, Tim!) but I am trying to get this spinlock/semaphore synchronisation issue clear in my head before I start attacking my code again!

I am trying to make my code ready for the day I ever do SMP (or even have an SMP machine for that matter). Now in my kernel, pretty much everything is stored in an object list including threads/processes and the like, the only thing not in it is interrupt handlers and memory management information (for obvious reasons).

Now, I want to ensure that the object manager is only accessed by one task at a time. The thing is some of the code that accesses it can take a little while to execute, for example scanning the list. The problem is because the object list is so pervasive I could easily start creating deadlocks during task switches, for example task A locks the object manager while updating some data but before it releases the lock a timer interrupt occurs to start a task switch, *but* the threads are in the object list, hence dead-lock, which is what I am getting.

One solution to this is to prevent task switches while a lock is held, but then the kernel becomes non-preemptive in effect, not what I want if I can help it.

The other solution is to start breaking things out of the object list, maybe threads and processes, but I don't really want to do this either.

I don't really think semaphores should be used for this, but I also worry about disabling interrupts while the lock is held, because it may run several thousand instructions while searching the list.

So, basically what I am asking is, how would YOU do it?

Thanks in advance! :-\

[Slasher]

hi,
what if you try locking only the object or part of the object list that is being modified. That way, if an interrupt occurrs you can switch tasks but no process will be able to tamper with the object(s) already in use.
the only problem is you will now have to create a list per object where processes that desire to access it will be queued until they have access to it.

[DarylD]

It starts getting trickier doing that and it doesn't guarantee the list stays correct, but it might be a good idea I will look into it.