On 03/20/2013 10:41 PM, Raymond Jennings wrote: > On Wed, Mar 20, 2013 at 2:03 PM, <Valdis.Kletnieks@xxxxxx> wrote: >> On Thu, 21 Mar 2013 02:24:23 +0700, Mulyadi Santosa said: >> >>> pardon me for any possible sillyness, but what happen if there are >>> incoming I/O operation at very nearby sectors (or perhaps at the same >>> sector?)? I suppose, the elevator will prioritize them first over the >>> rest? (i.e starving will happen...) > This is actually why I proposed to enforce forward progress by only > looking for further requests in one direction at a time. > > Suppose you have requests at sectors 1, 4, 5, and 6 > > You dispatch sectors 1, 4, and 5, leaving the head parked at 5 and the > direction as ascending. > > But suddenly, just before you get a chance to dispatch for sector 6, > sector 4 gets busy again. > > I'm not proposing going back to sector 4. It's behind us and (as you > indicated) we could starve sector 6 indefinitely. > > So instead, because sector 4 is on the wrong side of our present head > position, it is ignored and we keep marching forward, and then we hit > sector 6 and dispatch it. > > Once we hit sector 6 and dispatch it, we do a u-turn and start > descending. That's when we pick up sector 4 again. > > When we're going up, we ignore what's below us, and when we're going > down we ignore what is above us. > > We only switch directions when there's nothing in front of us the way > we were going. In theory, given that disk capacity is itself finite, > so too is the amount of time one has to wait before getting reached by > the elevator. > > Anyway, does this clarification answer your concerns about starvation? > >> And this, my friends, is why elevators aren't as easy to do as the average >> undergrad might hope - it's a lot harder to balance fairness and throughput >> across all the corner cases than you might think. It gets really fun >> when you have (for example) a 'find' command moving the heads all over >> the disk while another process is trying to do large amounts of streaming >> I/O. And then you'll get some idiot process that insists on doing the >> occasional fsync() or syncfs() call. Yes, it's almost always *all* >> corner cases, it's very rare (unless you're an embedded system like a Tivo) >> that all your I/O is one flavor that is easily handled by a simple elevator. > In my case I'm just concerned with raw total system throughput. > > I called it "BFQ" for a reason. It sounds to me like the LOOK disk scheduling algorithm from 1970? Or do I miss something? _______________________________________________ Kernelnewbies mailing list Kernelnewbies@xxxxxxxxxxxxxxxxx http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
