reader writer semaphores
in [Unix Programming]
|
From: John Kelly on 30 Jun 2010 12:08 On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern <william(a)wilbur.25thandClement.com> wrote: >flock() will be slower because it's a pure kernel interface, whereas the >fast-path for semaphore and mutex implementations can be done all in >userspace. Updating a semaphore must be an atomic operation. How can two unrelated user tasks compete for the same semaphore, without help from the kernel? -- Web mail, POP3, and SMTP http://www.beewyz.com/freeaccounts.php
From: William Ahern on 30 Jun 2010 14:28 John Kelly <jak(a)isp2dial.com> wrote: > On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern > <william(a)wilbur.25thandClement.com> wrote: > >flock() will be slower because it's a pure kernel interface, whereas the > >fast-path for semaphore and mutex implementations can be done all in > >userspace. > Updating a semaphore must be an atomic operation. How can two unrelated > user tasks compete for the same semaphore, without help from the kernel? Using shared memory. They'd need help from the kernel, certainly, specifically ensuring that the relevant page has the proper characteristics for mutually visible atomic operations. For example, BSDs provide the MAP_HASSEMAPHORE flag to mmap(2), and Linux specifies PROT_SEM for mprotect(2).
From: William Ahern on 30 Jun 2010 14:30 John Kelly <jak(a)isp2dial.com> wrote: > On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern > <william(a)wilbur.25thandClement.com> wrote: > >flock() will be slower because it's a pure kernel interface, whereas the > >fast-path for semaphore and mutex implementations can be done all in > >userspace. > > > >Now, perhaps if someone reimplemented Linux's flock() with a vsyscall.... > I thought a vsyscall was just a faster interface to a syscall. Is that > what you mean? I believe vsyscalls operate on a kernel-shared data structure, but on second thought it may just be shared read-only.
From: John Kelly on 30 Jun 2010 17:52 On Wed, 30 Jun 2010 11:28:57 -0700, William Ahern <william(a)wilbur.25thandClement.com> wrote: >John Kelly <jak(a)isp2dial.com> wrote: >> On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern >> <william(a)wilbur.25thandClement.com> wrote: > >> >flock() will be slower because it's a pure kernel interface, whereas the >> >fast-path for semaphore and mutex implementations can be done all in >> >userspace. > >> Updating a semaphore must be an atomic operation. How can two unrelated >> user tasks compete for the same semaphore, without help from the kernel? > >Using shared memory. They'd need help from the kernel, certainly, >specifically ensuring that the relevant page has the proper characteristics >for mutually visible atomic operations. For example, BSDs provide the >MAP_HASSEMAPHORE flag to mmap(2), and Linux specifies PROT_SEM for >mprotect(2). I found this: * * * http://en.wikipedia.org/wiki/Mutual_exclusion In a computer in which several processors share memory, an indivisible test-and-set of a flag could be used in a tight loop to wait until the other processor clears the flag. The test-and-set performs both operations without releasing the memory bus to another processor. When the code leaves the critical section, it clears the flag. This is called a "spinlock" or "busy-wait." And this: http://en.wikipedia.org/wiki/Test-and-set A lock can be built using an atomic test-and-set instruction as follows: function Lock(boolean *lock) { while (test_and_set (lock) == 1) ; } The calling process obtains the lock if the old value was 0. It spins writing 1 to the variable until this occurs. * * * I never thought of using an assembly language spinlock from user space. Seems like that would avoid kernel calls altogether, whether "fast-path" or not. -- Web mail, POP3, and SMTP http://www.beewyz.com/freeaccounts.php
From: John Kelly on 30 Jun 2010 18:18
On Wed, 30 Jun 2010 21:52:29 +0000, John Kelly <jak(a)isp2dial.com> wrote: >I never thought of using an assembly language spinlock from user space. >Seems like that would avoid kernel calls altogether, whether "fast-path" >or not. Hmm ... What if process A grabs the lock, starts working his critical section, and along comes process B who spins, waiting to get the lock. And what if B has higher priority than A? A starves, B spins, but can't get the lock, because A can't complete his critical section while B hogs the CPU. -- Web mail, POP3, and SMTP http://www.beewyz.com/freeaccounts.php |