Page 1 of 1
Avoiding locking in Async IPC in a type safe memory safe OS
Posted: Thu Feb 25, 2010 11:11 pm
by Benk
Ok ,
I have a languaged based OS , think Singularity and am writing some IPC which is deeply asynconous.
At present when i send a message the receiver needs to do an interlocked call since the sender can send many messages to the receiver , the exception to this is if the receiver is waiting than there is no need to lock and a fixed slot can be used. Is there anyway to remove the Interlocked from the queue when say 1 Process (w 1 thread) is writing messages and a seperate process ( w 1 thread) is processing them ?
Processes are Single threaded and IPC is always from STP to STP (Single Threaded Process) via a pre established pipe ( that way i avoid connection costs and sending the sender and receiver in each message as well as checking the sender and receiver) Note STPs can create other STPS , pass in an object root and GC and manage them to give a Process with many thread mode but each thread has its own IPC.
Messages are immutable once created but can contain references to global immutable objects to send access to data you create an immutable wrapper.
Also there are parralels here with Message pump message driven UIs are there any pitfalls to look out for
?
Re: Avoiding locking in Async IPC in a type safe memory safe OS
Posted: Fri Feb 26, 2010 1:38 am
by Brendan
Hi,
For "avoiding locking" there's 2 classes of code. There's "lockless" algorithms which repeatedly retry until success (but can't guarantee that you won't retry millions of times due to contention), and there's "blockless" algorithms which don't need to retry (and do guarantee that all threads make progress, even if there is contention).
Lockless algorithms are a worthless joke. They're more complex than a boring spinlock and the resulting behaviour works out no better. It's possible to use an adaption of the
bakery algorithm with less overhead (less cache-line thrashing) and better behaviour (fairness). Basically given the choice between lockless code and code that uses a lock, use code that uses a lock (and then make sure the lock is a good lock).
Blockless algorithms are better than anything, but in most cases they're impossible to implement.
I'm not too sure I understand exactly what you're doing, but (in general) asynchronous messaging ends up being "message queues/FIFOs implemented as linked lists", where there's only really 2 operations - add stuff to the head of the queue, and remove stuff from the tail of the queue.
In your specific case (FIFO with a maximum of one reader and a maximum of one writer) a blockless algorithm is possible. The reader "owns" the "pointer to the head of the list" (and the writer never touches it), and the writer "owns" the "pointer to the last entry on the list" (and the reader never touches it). To ensure that both the "head" and "tail" pointers are always valid, the reader always leaves at least one old entry on the linked list. Rather than explaining it, here's some pseudo-code:
Code: Select all
typedef struct message {
struct message *next;
uint8_t data[];
} MESSAGE;
MESSAGE *head;
MESSAGE *tail;
MESSAGE *create_message_queue(void) {
MESSAGE *dummy_message;
dummy_message = malloc(sizeof(MESSAGE));
if(dummy_message != NULL) {
dummy_message->next = NULL;
head = dummy_message;
tail = dummy_message;
}
return dummy_message;
}
MESSAGE *get_message_from_queue(void) {
while( head->next == NULL ) {
/* tell scheduler not to give us CPU time until "head->next != NULL" */
}
head = head->next;
return head;
}
void put_message_on_queue(MESSAGE *new_message) {
new_message->next = NULL;
tail->next = new_message;
tail = new_message;
}
Cheers,
Brendan
Re: Avoiding locking in Async IPC in a type safe memory safe OS
Posted: Fri Feb 26, 2010 4:30 am
by Benk
Agree with you there the lockless algorthms are so tight you cant make changes and besides for IPC lock like this with process to process a spin lock will be just as effective ( since the wait time is so small and rarely is there contention). DOes anyone know a tricky way maybe with the schedular to not even have an interlock on a multi code ?
PS: I have pretty much decided on a spin lock just wanted to get some other oppinions
Re: Avoiding locking in Async IPC in a type safe memory safe OS
Posted: Fri Feb 26, 2010 5:10 am
by Combuster
Spinlocks are only useful on multiprocessor setups. Otherwise you just keep spinning for nothing since the other end doen't get CPU time and thus cannot release the lock in question. Add one wasted timeslice, or many with significant lock contention.
In the singleprocessor case, I don't agree with brendan - Lockfree algorithms, especially the standard transactional ones work better - if you get the timeslice you can just go in and make your commits, and when the slice gets back to the other thread, it will abort and retry, which is faster than the task switch you'd normally have. This advantage gets lost when you have heavy contention on multiprocessor, but then again heavy lock contention is an indication of design issues.
That said, reader-writer pipes are pretty easy to do with waitfree algorithms (using the head and tail pointers in a circular buffer), making the discussion on inferior implementations moot. With some modification, the same tactics work with single-reader multiple-writer buffers and even public mailboxes (multiple readers and writers, where there's only one reader for any single message). I wouldn't even think of using spinlocks here.
Re: Avoiding locking in Async IPC in a type safe memory safe OS
Posted: Fri Feb 26, 2010 5:53 am
by Brendan
Hi,
Combuster wrote:Spinlocks are only useful on multiprocessor setups. Otherwise you just keep spinning for nothing since the other end doen't get CPU time and thus cannot release the lock in question. Add one wasted timeslice, or many with significant lock contention.
In the singleprocessor case, I don't agree with brendan - Lockfree algorithms, especially the standard transactional ones work better - if you get the timeslice you can just go in and make your commits, and when the slice gets back to the other thread, it will abort and retry, which is faster than the task switch you'd normally have. This advantage gets lost when you have heavy contention on multiprocessor, but then again heavy lock contention is an indication of design issues.
You're talking about user-space, and I'm talking about kernel-space (where a kernel is able to disable IRQs and/or disabling task switches to prevent context switches from occurring while any sort of lock is held)...
Cheers,
Brendan
Re: Avoiding locking in Async IPC in a type safe memory safe OS
Posted: Sun Feb 28, 2010 6:03 pm
by Benk
Combuster wrote:Spinlocks are only useful on multiprocessor setups. Otherwise you just keep spinning for nothing since the other end doen't get CPU time and thus cannot release the lock in question. Add one wasted timeslice, or many with significant lock contention.
In the singleprocessor case, I don't agree with brendan - Lockfree algorithms, especially the standard transactional ones work better - if you get the timeslice you can just go in and make your commits, and when the slice gets back to the other thread, it will abort and retry, which is faster than the task switch you'd normally have. This advantage gets lost when you have heavy contention on multiprocessor, but then again heavy lock contention is an indication of design issues.
That said, reader-writer pipes are pretty easy to do with waitfree algorithms (using the head and tail pointers in a circular buffer), making the discussion on inferior implementations moot. With some modification, the same tactics work with single-reader multiple-writer buffers and even public mailboxes (multiple readers and writers, where there's only one reader for any single message). I wouldn't even think of using spinlocks here.
Only thing against this is waitfree methods normally require volatile pointers but spinlocks dont or am i wrong here
? Also if the task is very short - which it is in this case than the chance of a dispatch while the lock is held is very minimal and hence the chance to loose a time slice.
Re: Avoiding locking in Async IPC in a type safe memory safe OS
Posted: Sun Feb 28, 2010 10:22 pm
by Brendan
Hi,
Benk wrote:Only thing against this is waitfree methods normally require volatile pointers but spinlocks dont or am i wrong here
Most waitfree algorithms (including queue management) require volatile pointers.
Simple spinlocks don't require a pointer at all (they require a volatile variable), but simple spinlocks aren't as good as more complex spinlocks (e.g. something that minimises cache line trashing and has "fairness", but does require volatile pointers).
It's worse than that though - they need to be atomic operations ("volatile" alone isn't enough). In most cases high level languages don't support atomic operations so you'd need to use assembly language (or inline assembly).
Benk wrote:? Also if the task is very short - which it is in this case than the chance of a dispatch while the lock is held is very minimal and hence the chance to loose a time slice.
For one CPU under low/medium load the chance might be very minimal. For 64 CPUs under heavy load the chance might be extremely high.
Cheers,
Brendan
Re: Avoiding locking in Async IPC in a type safe memory safe OS
Posted: Mon Mar 01, 2010 12:53 am
by Benk
Thats one of the reasons i went with spinning locks its easier to make one that doesnt trash the cache , all the interlocked based algorithms i have seen thrash the cache because of the 2 volatile variables. I must say though almost every lockless queue alg. ends up spinning around the compare exchange anyway.