From owner-freebsd-arch Sun Sep 24 12:50:16 2000 Delivered-To: freebsd-arch@freebsd.org Received: from berserker.bsdi.com (berserker.twistedbit.com [199.79.183.1]) by hub.freebsd.org (Postfix) with ESMTP id 821F637B422; Sun, 24 Sep 2000 12:50:08 -0700 (PDT) Received: from berserker.bsdi.com (cp@LOCALHOST [127.0.0.1]) by berserker.bsdi.com (8.9.3/8.9.3) with ESMTP id NAA25438; Sun, 24 Sep 2000 13:48:45 -0600 (MDT) Message-Id: <200009241948.NAA25438@berserker.bsdi.com> To: Greg Lehey Cc: Archie Cobbs , Brian Somers , Joerg Micheel , Matthew Jacob , Frank Mayhar , John Baldwin , Mark Murray , FreeBSD-arch@freebsd.org Subject: Re: Mutexes and semaphores (was: cvs commit: src/sys/conf files src/sys/sys random.h src/sys/dev/randomdev hash.c hash.h harvest.c randomdev.c yarrow.c yarro) In-reply-to: Your message of "Sun, 24 Sep 2000 15:42:16 +0930." <20000924154216.D512@wantadilla.lemis.com> From: Chuck Paterson Date: Sun, 24 Sep 2000 13:48:45 -0600 Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG First a general comment. The main reason to not hold a mutex across an async event is not because it won't work, but because it means that we loose the ability to detect dead locks. If process A holds mutex bar during a wait for async event, such as msleep(), then it becomes a requirment that the process which is going to wake up process A doesn't block on mutex foo, or have any dependencies even many removed on something that requires mutex bar. Greg Lehey wrote on: Sun, 24 Sep 2000 15:42:16 +0930 }On Saturday, 23 September 2000 at 21:02:49 -0600, Chuck Paterson wrote: }> }>> Once you have the spin lock primitive, you can easily build }>> semaphores, sleep queues, etc. A semaphore is just a counter plus }>> a sleep queue -- all protected by the spin lock. }>> }>> A MUTEX is just a sepaphore whose initial count is 1. }>> }>> ?? }> }> In general this might be true, but in specific it isn't. } }As you know, I used to say exactly the same thing as Archie, but I've }realized that this implied count of 1 causes a couple of important }differences. I'm still working on a clearer definition, but what I've }seen so far is: } }1. Because "mutexes" (I really hate this term; I wish I could find a } better one) only have an implied count of one, they can also have } the concept of an owner, which we use. } }2. Because the mutex has an owner, only the owner can release it. } }3. The mutex can also be "recursive" (it's really iterative, I } suppose): the owner can take it several times. The only reason } for this appears to be sloppy coding, but in the short term I } think we're agreed that we can't dispose of that. } I have to disagree with item 3. Take the simple situation of function a() needing lock foo and function b() needing lock foo. If b() is some times called from a() and sometimes not then the recursiveness of foo is saving state. The same state will have to be passed explicitly and tested b() in either case, all that is really done is providing an automatic way of passing this state in, and saving a few cycles because we don't have to set up a variable and pass it in. }One thing that I don't think is important is the duration of }ownership. We currently use mutexes for short periods of time, which }is why we have the spin version. } }At Tandem, we only used semaphores, but they always had a count of 1, }so they were effectively very close to our mutexes. They didn't allow }recursion, which is the Right Thing in a system designed from the }ground up, but they also didn't have owners. One of the most frequent }complicated problems we had were system hangs (deadlocks), and we }frequently couldn't figure out who had done what and why. Having }owners is a great debug aid. } }> The sleep version of mutexs have no spin lock. Spin locks are more }> expensive than the mutices currently in FreeBSD and BSD/OS. In }> order to acquire a spin locks interrupts must be blocked, which }> isn't the case for mutices which are not contested. } }If we can expect that the mutex will, on average, be freed in less }time than it would take to schedule a new process, spin locks can be a }better alternative. Otherwise we wouldn't need them at all. } I think the previous graph is an over simplification. In general the following is closer to metric for your suggestion is: POC percentage of acquisitons which have a conflict CCS average cost of context switch AHT average hold time SLS how much is saved acquiring a sleep lock instead of a spin lock if ((CCS - (AHT / 2) * POC > SLS) use spin lock In the future when we have smarter code in the case where we have a conflict then the percentage of time we pay the CCS will drop. The place where spin locks are required is where a context switch is not permissible. }Anyway, this doesn't directly relate to semaphores. We have the basic }issue of atomicity, which in general can be handled without spin }locks, and that would apply to semaphores just as much as to mutexes. } }Greg }-- }Finger grog@lemis.com for PGP public key }See complete headers for address and phone numbers Chuck To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message