From owner-freebsd-smp@FreeBSD.ORG Tue Apr 18 00:03:56 2006 Return-Path: X-Original-To: smp@freebsd.org Delivered-To: freebsd-smp@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 2D45516A406; Tue, 18 Apr 2006 00:03:56 +0000 (UTC) (envelope-from tlambert2@mindspring.com) Received: from elasmtp-kukur.atl.sa.earthlink.net (elasmtp-kukur.atl.sa.earthlink.net [209.86.89.65]) by mx1.FreeBSD.org (Postfix) with ESMTP id 21EBD43D46; Tue, 18 Apr 2006 00:03:54 +0000 (GMT) (envelope-from tlambert2@mindspring.com) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=dk20050327; d=mindspring.com; b=dinjTO8y91sED8bypkTHIS+aI9DFOWWqPHjQ2q7OfJhJJiHVuuOibxXBWQOu/83l; h=Received:Message-ID:Date:From:Reply-To:To:Subject:Mime-Version:Content-Type:Content-Transfer-Encoding:X-Mailer:X-ELNK-Trace:X-Originating-IP; Received: from [209.86.224.28] (helo=mswamui-blood.atl.sa.earthlink.net) by elasmtp-kukur.atl.sa.earthlink.net with asmtp (Exim 4.34) id 1FVdhA-0008AZ-SI; Mon, 17 Apr 2006 20:03:52 -0400 Message-ID: <18400116.1145318632626.JavaMail.root@mswamui-blood.atl.sa.earthlink.net> Date: Mon, 17 Apr 2006 17:03:52 -0700 (GMT-07:00) From: Terry Lambert To: Surer Dink , Kris Kennaway , smp@freebsd.org, current@freebsd.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: EarthLink Zoo Mail 1.0 X-ELNK-Trace: b1a02af9316fbb217a47c185c03b154d40683398e744b8a4b11c7e29a110beee3e546ab6f01399b1a2d4e88014a4647c350badd9bab72f9c350badd9bab72f9c X-Originating-IP: 209.86.224.28 Cc: Subject: Re: Anomalous performance increase from mutex profiling X-BeenThere: freebsd-smp@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: Terry Lambert List-Id: FreeBSD SMP implementation group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 18 Apr 2006 00:03:56 -0000 >From: Surer Dink >Sent: Apr 17, 2006 11:12 AM >To: Kris Kennaway , smp@freebsd.org, current@freebsd.org >Subject: Re: Anomalous performance increase from mutex profiling > >On 4/17/06, Kris Kennaway wrote: >> On Mon, Apr 17, 2006 at 03:54:07AM -0400, Surer Dink wrote: >> > Please excuse if this is a stupid question - but might using MCS or >> > QOLB locks in this situation be useful? >> >> What are they? > >Mellor-Crummy Scott: >http://www.cs.rochester.edu/u/scott/papers/1991_ASPLOS_sync.pdf > >An overview comparing various possible optimizations for a few lock >types, including MCS and QOLB: >ftp://ftp.cs.utexas.edu/pub/dburger/papers/ISCA97_qolb.pdf > >I believe the QOLB proposal only suggested hardware modificaition for >performance improvement, but could be implemented entirely in software >- the overheads are high, but offer substantial performance benefit in >high contention situations. MCS is based on QOSB, however fully >implemented in software. > >There is also a proposal for changing lock to MCS dynamically, however >I have not read it: >ftp://ftp.cag.lcs.mit.edu/pub/papers/pdf/reactive.pdf Implementation under the GPL, including MCAS and other lockless algorithms is available here (unfortunately, GPL'ed): http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/ Note that there is no general implementation that does not require use of asembly language; e.g. the PPC does not have a CAS instruction, and it has a weak memory model which means you will need to use an explicit barrier in your implementation (Mac OS X/Darwin provide implementations of the necessary atomic operations in the header file as of the Tiger release). -- Terry