OSDev.org

That depends on the multiprocessing architecture. In Symetrical Multiprocessing, which is what is being discussed here (and is the most common approach for multiprocessing in a single motherboard system) the processors share memory and have equal access to the entire memory space and peripherals.

Other designs work differently, and there are many different variations. For example, in centralized multiprocessing or co-processing, there is a single primary processor which uses the other processors to perform tasks on it's behalf; co-processing can be homogenous, in which the CPUs are of the same type, or heterogeneous, with specialized co-processors performing as single focused task. Technically speaking, most single-CPU PCs these days fall into the category of heterogeneous co-processing, as they use specialized GPU and DSP processors for video and audio, but since the co-processors are rarely programmed directly, they are usually treated a single-processor systems.

Non-Uniform Memory Access (NUMA) is similar to SMP, except that each processor has it's own 'local' memory as well as the shared memory; for each processor, accessing it's own local memory is faster than accessing the shared memory. Some NUMA designs allow processors to access other processors' local memory directly, but at an even higher overhead than for shared memory, while other require that the data be transferred to shared memory in order to be accessed by more than one processor.

In parallel processing or multithread processing, CPUs not only share memory, they can share a single program, each processor performing a single thread of execution for the whole. In most systems today, this would be managed in the OS software rather than in hardware, though there are some special-purpose parallel systems in existence such as the infamous 'DES Killer', a computer designed in 1998 to decrypt DES-encrypted messages in a matter of hours (this was done to demonstrate the weakness of the algorithm; not surprisingly, the National Bureau of Standards introduced the AES encryption algorithm shortly afterwards).

All of these designs are what are called 'tightly-coupled' multiprocessing; 'loosely-coupled' designs, such as clustering or distributed processing, do not share memory, and in fact can be completely separate systems. Distributed processing is a general term for networked systems running under a shared operating system, though it is also applied to distributed projects such as SETI@home. Clustering is distributed processing (in the first sense) among a group of physically proximate, closely networked (and usually homogenous) systems.

Comments and corrections welcome.

That is, in general, how semaphores or mutexes are implemented. Task A acquires mutex M and enters the code section protected by it. A short time later, task B attempts to acquire mutex M. Task B cannot procede while task A is in M. If M were a spinlock, B would waste time on the processor spinning the whole rest of its timeslice, and any subsequent timeslices it received. But since M is not a spinlock but a properly implemented mutex, instead B is immediately removed from the run queue, and not scheduled for processor time until A releases M. When A does release M, it causes an immediate task switch to B, so it may immediately proceed into the critical section it's been waiting for. If M were a spinlock, B would not be immediately woken up when A released it, since the scheduler has no information on who is spinning or why.

For certain short and sweet bits of code, a proper mutex or semaphore may be overkill, but in general, anything more than a couple lines of code needing protection should be protected by a mutex or semaphore, and not be disabling interrupts and using a spinlock if it can be avoided. Spinning is bad. It shouldn't be done except in circumstances where you know for sure it would take longer to switch tasks than it would take to simply spin and wait. Spinlocks certainly shouldn't be used to protect any section of code whose execution time isn't O(1).

Thanks for all the help. I think I understand most of this now.

Pete

PS Anyone know where Tim's been recently?

so i'm implementing my spinlock and was wondering if this is a proper implementation:

(assume m_Lock is initialized to 0)



assuming test_and_set is implemented as so



is this generally correct?

HI,



Yes

You may wish to add the PAUSE instruction to "acquire()" though - to prevent one logical CPU from slowing down other logical CPUs within the same physical CPU/chip.


Cheers,

Brendan

glad to see it is on target, i have a question about this sleep. I realize that the lock/xchg instructions will slow down the other processors as it will temporarily have to be lock-step for that one instruction. So my question is how do you recomend I implement a sleep? Are we talking the type that would involve a context switch cause I'm a bit undecided as to whether or not it would break things (the other threads would have interrupts enabled in there context, but so long as they dont touch the spinlock protected resource it shoudl be fine anyway).

thoughts?

proxy

Hi,



"PAUSE" is an actual CPU instruction (similar to "NOP"). It was introduced with Pentium 4 processors, but it's backward compatible with all IA-32 processors as it's coded as a "REP NOP" (which won't actually repeat on older CPUS because NOP wasn't originally meant to).

From Intel's reference manual:


There's also more information about it's benefits when used in conjunction with hyper-threading in "7.7.6.1. USE THE PAUSE INSTRUCTION IN SPIN-WAIT LOOPS"

To avoid any delays when acquiring a lock that is free (the most common case) I tend to do something like:



Rather than



This second version will always execute "pause" at least once, while the first won't...

Cheers,

Brendan

Cute. It should also be noted that the behavior of REP before any other non-string instruction produces "undefined behavior", according to Intel. In fact, I think it generally does nothing, but I wouldn't bet any money of the fact...

If you're into obfuscating your code, NOP can also be expressed as XCHG AX,AX (which also encodes to 0x90), so PAUSE becomes REP XCHG AX,AX.

Of course, if you actually do this, you should be taken out back and shot...

That piece of code I don't quite get, how could EAX be different to itself? It would have to be changed while being compared which is impossible as far as I know ???

Hi,



The "test eax,eax" instruction isn't the same as "cmp eax,eax". It's a shorter version of "test eax,0xFFFFFFFF", or an alternative to "cmp eax,0".

Basically, the code loops until the value stored at "[lock]" is zero while also setting the value at [lock] to 1. If another CPU already has the lock it won't return zero. If the other CPU frees the lock (using "mov dword [lock],0" for e.g.) then the "xchg [lock],eax" part will atomically set the value to non-zero and read the value zero, which ends the loop.

I prefer using the "BTS" (bit test and set) instruction for spinloops:



It's functionally equivelent, but an instruction shorter (although optimizing delay loops could be considered a sign of insanity).


Cheers,

Brendan

Ah, a good example of reading something how you want to read it rather than how it really is. It might just be me, but the BTS version seems easier to understand from just looking at it rather than having to think (it's nice to have at least one thing that doesn't require too much thought). Also, yes, optimising delay loops is a possible sign of insanity, however writing an OS is a much bigger sign

Resurrection of a old thread, but shouldn't that last jump instruction read jnc instead of jc, Brendan?

Hi,



No - it's the first "jc" that is wrong!

It should be:


An even better way would be:


This version doesn't repeatedly lock the bus when the spinlock is under heavy contention...


[EDIT - added everything below here]

To unlock the lock, you'd only need to use:



Which doesn't need a lock prefix, but please note that the "lock" variable must be aligned.

Also, to minimize cache thrashing you should define the "lock" variable like this:



This makes sure that the lock exists in its own cache line, which is not shared by anything else. It can also waste a lot of RAM if you've got a lot of locks.

I'd advise some serious contemplation if you wanted to reduce the amount of wasted RAM - imagine 2 or more CPUs trying to acquire the lock while a third CPU is trying to do something with data in the same cache line (cache misses everywhere and a huge amount of bus traffic).

For similar reasons, it is usually not a good idea to use the same variable for multiple locks (e.g. bit 0 for lock A, bit 1 for lock B, bit 2 for lock C, etc).


Cheers,

Brendan

Sorry to resurrect this (very) old thread, but just a quick question. Does you second improved example there suffer the same "jc instead of jnc" problem as the original or is it an intentional change in this case?

Hi,



Cut & paste is a curse sometimes....

The second example should be:



Of course macros are more fun...



And checking for mistakes can be a good idea too:




Cheers,

Brendan