From owner-freebsd-arch Wed May 17 13:29:28 2000 Delivered-To: freebsd-arch@freebsd.org Received: from finch-post-12.mail.demon.net (finch-post-12.mail.demon.net [194.217.242.41]) by hub.freebsd.org (Postfix) with ESMTP id 6B65E37BFC9; Wed, 17 May 2000 13:29:22 -0700 (PDT) (envelope-from dfr@nlsystems.com) Received: from nlsys.demon.co.uk ([158.152.125.33] helo=herring.nlsystems.com) by finch-post-12.mail.demon.net with esmtp (Exim 2.12 #1) id 12sARL-000LlV-0C; Wed, 17 May 2000 20:29:12 +0000 Received: from salmon.nlsystems.com (salmon.nlsystems.com [10.0.0.3]) by herring.nlsystems.com (8.9.3/8.8.8) with ESMTP id VAA26580; Wed, 17 May 2000 21:33:57 +0100 (BST) (envelope-from dfr@nlsystems.com) Date: Wed, 17 May 2000 21:33:17 +0100 (BST) From: Doug Rabson To: Terry Lambert Cc: Mike Smith , Nick Hibma , arch@FreeBSD.ORG Subject: Re: A new api for asynchronous task execution In-Reply-To: <200005171745.KAA06412@usr05.primenet.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG On Wed, 17 May 2000, Terry Lambert wrote: > > I do hope to be able to replace at least some of these pieces. I like the > > idea of a priority sorted list of tasks, probably using a priority field > > in struct task. > > Bletch. > > This is a job best handled by managing insertion order, rather than > by way of an explicit sort. Insertion order also keeps the structure > both small and generic. > > > > As Chuck noted, a queue name will be useful for initialising SMP mutexes > > so I'll add that to taskqueue_init(). It should be easy to leverage that > > into something like taskqueue_find(). > > I dislike the idea of explicit kernel mutex queues, as opposed to > resource queues. > > The problem you run into is the inability to perform deadlock > avoidance, which you would normally do by implying an edge between > the top of the hierarchy into which you are inserting and the > location into which you wish to insert (such an algorithm is order > N+1 based on depth N and doing a reverse traversal in an attempt to > detect a Hamiltonian cyclye introduced by the implication of the > edge; short of caching the edge node, which would give you order N, > but cost significantly, this is about the best possible algorithm > you can get). The BSD/OS mutex code includes a compile-time-selected debugging feature which automatically detects locking hierarchy violations. Anyway, using a mutex here doesn't add to locking complexity since the mutex would be exited before calling the task's callback and re-entered after. -- Doug Rabson Mail: dfr@nlsystems.com Nonlinear Systems Ltd. Phone: +44 20 8442 9037 To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message