Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!lll-lcc!unisoft!paul
From: paul@unisoft.UUCP (Paul Campbell)
Newsgroups: comp.unix.wizards
Subject: Re: bflush algorithm
Message-ID: <164@unisoft.UUCP>
Date: Mon, 17-Nov-86 17:18:06 EST
Article-I.D.: unisoft.164
Posted: Mon Nov 17 17:18:06 1986
Date-Received: Mon, 17-Nov-86 22:13:01 EST
References: <245@miduet.gec-mi-at.co.uk>
Reply-To: paul@unisoft.UUCP (Paul Campbell)
Organization: UniSoft Systems; Berkeley, CA
Lines: 37

In article <245@miduet.gec-mi-at.co.uk> jgh@gec-mi-at.co.uk (Jeremy Harris) writes:
>
>After bflush finds a delayed-write block and asynch-writes it, it scans again
>from the start of the freelist. 
>
>I assume this is for safety in case some other process inserts a delayed-write
>block on the freelist, but who will do this?
>Jeremy Harris	jgh@gec-mi-at.co.uk	...!mcvax!ukc!hrc63!miduet!jgh

You are correct .... this is real inefficient and seems to be quadratic in the
number of buffers. Unfortunatly your fix may NOT fix the problem. It depends on
the drivers in your system. You see it is quite allowable for a driver's
strategy routine to sleep, thus causing a process switch. Granted that most
don't, and in fact only one that I have ever seen did (not written here).

	A much better solution is a two staged buffer search, create a local
array of buffer pointers (say 40 odd). Now search through the free list for
delayed write candidates and put them in the array until either you reach the
end of the list or the array is full.  If the array was empty then you are done
otherwise go back through the array reexamining each buffer to see if it still
needs to be written (if not ignore it) and if required write it. Now go back and
through the freelist and fill another array. This way instead of making
1 pass through the free list for each one of N delayed write buffers (all done
at high slp and chances are these are at the end of the freelist) you make
N/(40 odd) passes. I guess you choose the array size from an estimate of the
percentage DELAYED write buffers in your cache and the cache size.

	The later V.2/V.3 kernels don't suffer from this problem as badly due
to the process that ages buffers and trickles them out over time rather than
all at once during a sync().

	By the way the original code is quite valid if one makes the assumption
that your system only has a small number of buffers (say ~20). 


		Paul Campbell
		..!ucbvax!unisoft!paul