From owner-freebsd-hackers  Tue Jan  5 15:03:37 1999
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Received: (from majordom@localhost)
          by hub.freebsd.org (8.8.8/8.8.8) id PAA26637
          for freebsd-hackers-outgoing; Tue, 5 Jan 1999 15:03:37 -0800 (PST)
          (envelope-from owner-freebsd-hackers@FreeBSD.ORG)
Received: from apollo.backplane.com (apollo.backplane.com [209.157.86.2])
          by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id PAA26629
          for <hackers@FreeBSD.ORG>; Tue, 5 Jan 1999 15:03:36 -0800 (PST)
          (envelope-from dillon@apollo.backplane.com)
Received: (from dillon@localhost)
	by apollo.backplane.com (8.9.1/8.9.1) id PAA98165;
	Tue, 5 Jan 1999 15:03:03 -0800 (PST)
	(envelope-from dillon)
Date: Tue, 5 Jan 1999 15:03:03 -0800 (PST)
From: Matthew Dillon <dillon@apollo.backplane.com>
Message-Id: <199901052303.PAA98165@apollo.backplane.com>
To: Terry Lambert <tlambert@primenet.com>
Cc: bright@hotjobs.com (Alfred Perlstein), tlambert@primenet.com,
        wes@softweyr.com, hackers@FreeBSD.ORG
Subject: Re: question about re-entrancy.
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG


:I think the best way of thinking of the problem is an analogy
:that someone told me years ago:
:
:Think of the CPU's in an SMP system as spiders crawling over
:the code; the more CPU's, the more spiders.
:
:Most of the code is black; it doesn't matter how many spiders
:are crawling ove it at the same time.  Some spots in the code are
:red, where global lists or singular objects are being manipulated.
:
:These are weak spots in the code that can only support the weight
:of one spider at a time.  Maybe they are a result of weak spots
:in the hardware (e.g., you can't have multiple CPU's issuing
:INB/OUTB commands such that the agregate rate exceeds the ability
:of the bus).
:
:Think of how you would design an OS to minimise the percentage of
:red vs. black.  At the same time, don't make it do that the only
:...

    This is a really good analogy, with one change:  The problem with
    the red zones is not so much that only one spider can go through
    it at a time, but of the pipelining that is achievable when you
    have to go through a red zone.  The inability to pipeline inherently
    limits the number of processors you can run through the code 
    'simultaniously'... as long as you do not stall the pipeline,
    you are ok.

    So if you a section of code that does this (each letter designates a
    fine granularity lock surrounding a section of code):

	A B C D E 

    You can usually assume infinite scaleability (even though it isn't
    really infinite).  While it is true that one processor will stall for
    a short period when two try to get A, this tends to have a synchronizing
    effect so the NEXT time the two processors call A, they will tend to do 
    it pre-synchronized and neither will stall (or they will not stall as 
    long).

    The actual 'virtual' size of the pipeline depends on how various 
    subsystems within the kernel interact with each other.

    The main design rule you want to follow to minimize the impact of
    the locks is to avoid 'loops' in the pipeline.  A loop --- like the
    lock sequence: 

	A B C A D E 
	     
    In which A loops, creates a major stall situation.  If you follow
    the pipelining rule, you generally do not have to worry about the
    scaleability of fine-granularity locks.

						-Matt

    Matthew Dillon  Engineering, HiWay Technologies, Inc. & BEST Internet 
                    Communications & God knows what else.
    <dillon@backplane.com> (Please include original email in any response)    

To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message