From owner-freebsd-hackers@FreeBSD.ORG Fri Jan 30 07:02:24 2004 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id D114516A4CE; Fri, 30 Jan 2004 07:02:24 -0800 (PST) Received: from ftp.bjpu.edu.cn (ftp.bjpu.edu.cn [202.112.78.5]) by mx1.FreeBSD.org (Postfix) with ESMTP id 1015043D2D; Fri, 30 Jan 2004 07:02:20 -0800 (PST) (envelope-from junsu@delphij.net) Received: by ftp.bjpu.edu.cn (Postfix, from userid 426) id D90DA5358; Fri, 30 Jan 2004 23:02:17 +0800 (CST) Received: from beastie.frontfree.net (beastie.frontfree.net [218.107.145.7]) by ftp.bjpu.edu.cn (Postfix) with ESMTP id 6C3955299; Fri, 30 Jan 2004 23:02:17 +0800 (CST) Received: by beastie.frontfree.net (Postfix, from userid 426) id A600511B8E; Fri, 30 Jan 2004 23:02:15 +0800 (CST) Received: from shasujunmv (unknown [211.161.222.86]) (using TLSv1 with cipher RC4-MD5 (128/128 bits)) (No client certificate requested) by beastie.frontfree.net (Postfix) with ESMTP id 932C311799; Fri, 30 Jan 2004 23:02:14 +0800 (CST) Message-ID: <01bd01c3e742$093d83b0$56dea1d3@shasujunmv> From: "Jun Su" To: "David Schultz" , "Xin LI" References: <20040129134121.GB53644@frontfree.net> <20040129200442.GA52780@VARK.homeunix.com> Date: Fri, 30 Jan 2004 23:02:08 +0800 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2800.1158 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165 X-Mailman-Approved-At: Sat, 31 Jan 2004 05:14:17 -0800 cc: hackers@FreeBSD.ORG cc: Olivier Houchard cc: current@FreeBSD.ORG cc: John Baldwin Subject: Re: Call for testers: New PID allocator patch for -CURRENT X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 30 Jan 2004 15:02:25 -0000 ----- Original Message ----- From: "David Schultz" To: "Xin LI" Cc: ; ; Sent: Friday, January 30, 2004 4:04 AM Subject: Re: Call for testers: New PID allocator patch for -CURRENT > On Thu, Jan 29, 2004, Xin LI wrote: > > Greetings, everyone > > > > A friend of mine has ported NetBSD's new PID allocation[1] code to FreeBSD, > > you can obtain the patch here: > > > > http://www.arbornet.org/~junsu/pid.diff > > > > Some of you may be already aware of this for he has posted[2] this to both > > current@ and hackers@ last September. > > > > Currently the patchset has been updated to make it applicable to -HEAD. > > > > A number of problems were found and fixed after the first post with many > > from the FreeBSD community, and we think it's time to post it again and, > > if you are interested, please give it a chance to run on your own (test) > > box. > > Thanks for the reminder. Your patch uses a very clever idea. I > messed around with the original patch in your PR a few months ago. > It would take more work to prove that your proposed patch improves > performance[1] and is a good approach, and to review and clean up > the implementation. For instance, it isn't immediately obvious > that the accelerated pid reuse is acceptable, so that needs to be > looked into further[2]. I don't have the time at the moment to go > over the patch with a fine-toothed comb, and jhb@ could do a > better job than me anyway if he has time, but I wanted to let you > know that it's floating around on at least one person's TODO list. Thank you for your great feedback. Olivier Houchard contacted to me about this patch. He also worked on this patch before. I am sorry I didn't mentioned him in the first email. > > Some low-hanging fruit: The patch needs to be cleaned up to > conform to style(9). It also changes the meaning of PID_MAX and > fails to enforce a 5-digit limit on pids. PID_MAX is now a initial value for the max pid value. When the concurrent process number is large than PID_MAX. We will assign PID_MAX *2 to pid_max. For 5-digit limit, I think I need add this type of check into the patch. > > > [1] That shouldn't be hard, given that the present algorithm takes > O(N) amortized time in the worst case, and can examine as many > as PID_MAX^2 pids if the number of processes in the system is > close to PID_MAX. > I think this algorithms for proc_alloc, pfind and zpfind are all O(1). The worst situation is that it reaches PID_MAX. In this situation, we need expand our pidtbl. This may bring some delay. However, this situation will only occurs few times. If a machine need 1000 concurrent process, it will only need a 2 ^ 10 slots process table. From the original 2 ^ 5 table, we need only 5 times to expend the table. > [2] Many systems have a high enough fork rate that pids recycle > every few minutes or hours with the present algorithm. These > systems don't necessarily have lots of processes running at any > given time, so the table (and thus the cycle length) in your > patch could remain relatively small if I'm interpreting the > code correctly. I think the code would have to be changed to > prevent reuse from happening too quickly in wall time. Reusing the proc slot doesn't mean reusing the pid. Everytime we reuse a proc slot, we will add pidtbl_mask to the pid. We reuse the pid when the pid reach the max_pid. Therefore if a user wants, he can increase the max_pid to a larger number to increase the period that the pid is not be reused. I will add a sysctl to allow user to adjust max_pid. > _______________________________________________ > freebsd-current@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-current > To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org" > >