ugpete@sunybcs (Peter Theobald) (02/13/88)
<Line Eater Motel. Line eaters check in.... but they don't check out!>
AmigaDos should sort disk requests by track. This way if three processes
ask for three different files scattered all over the disk, instead of
jumping around like a Tasmianian Devil getting blocks from first one
file, then the other then back to the first, AmigaDos would load in the
blocks on the tracks currently nearest the read head. Then it would move
the head to the next track with requested data on it, etc... It could
continue this process sweeping the head back and forth across the disk
picking up what is needed, wasting the least amount of time.
This would eliminate thrashing, and would speed up disk accesses
to boot! I think this is similar to what a clone of Peter da Silva meant by
single-threading loadSegs.
How major a change in AmigaDog is this?
-Pete
Peter Theobald SUNY/Buffalo Computer Science
internet: ugpete@cs.buffalo.edu bitnet: ugpete@sunybcs.BITNET
uucp: ..!{ames,boulder,decvax,rutgers}!sunybcs!ugpete
csnet: ugpete@buffalo.CSNETrichard@gryphon.CTS.COM (Richard Sexton) (02/13/88)
In article <8504@sunybcs.UUCP> ugpete@sunybcs.UUCP (Peter Theobald) writes: > >AmigaDos should sort disk requests by track. This way if three processes >ask for three different files scattered all over the disk, instead of >jumping around like a Tasmianian Devil getting blocks from first one >file, then the other then back to the first, AmigaDos would load in the >blocks on the tracks currently nearest the read head. Then it would move >the head to the next track with requested data on it, etc... It could >continue this process sweeping the head back and forth across the disk >picking up what is needed, wasting the least amount of time. > This would eliminate thrashing, and would speed up disk accesses >to boot! I think this is similar to what a clone of Peter da Silva meant by >single-threading loadSegs. > How major a change in AmigaDog is this? > This may not be as much of a gain as it would seem on first impression. I've seen quite a few cases where two processes were getting lots of tracks from opposing ends of the disk. It's horrible. -- "He tried to do his best, but he could not" richard@gryphon.CTS.COM {ihnp4!scgvaxd!cadovax, rutgers!marque, codas!ddsw1} gryphon!richard
bmacintyre@watsol.waterloo.edu (Blair MacIntyre) (02/16/88)
In article <8504@sunybcs.UUCP> ugpete@sunybcs.UUCP (Peter Theobald) writes: ><Line Eater Motel. Line eaters check in.... but they don't check out!> > >AmigaDos should sort disk requests by track. This way if three processes >ask for three different files scattered all over the disk, instead of >jumping around like a Tasmianian Devil getting blocks from first one >file, then the other then back to the first, AmigaDos would load in the >blocks on the tracks currently nearest the read head. Then it would move >the head to the next track with requested data on it, etc... It could >continue this process sweeping the head back and forth across the disk >picking up what is needed, wasting the least amount of time. > This would eliminate thrashing, and would speed up disk accesses >to boot! I think this is similar to what a clone of Peter da Silva meant by >single-threading loadSegs. > How major a change in AmigaDog is this? Unfortunately, this scheme could cause starvation ( ie. a certain read request doesn't get serviced because it's on the opposite end of the disk ) not to mention problems with syncronizing reads and writes if you start using a selection order other than first-come-first-serve. Nice thought, though. :-) Blair -- ===========================================================================///= Blair MacIntyre (bmacintyre@watsol.waterloo.edu) ( Long live the Amiga!! )/// University of Waterloo, Center for the New Oxford English Dictionary \\\/// =======================================================================\XX/====
stroyan@hpfcdc.HP.COM (Mike Stroyan) (02/17/88)
>>AmigaDos should sort disk requests by track. This way if three processes >>ask for three different files scattered all over the disk, instead of >>jumping around like a Tasmianian Devil getting blocks from first one >>file, then the other then back to the first, AmigaDos would load in the >>blocks on the tracks currently nearest the read head. > >Unfortunately, this scheme could cause starvation ( ie. a certain read >request doesn't get serviced because it's on the opposite end of the >disk ) not to mention problems with syncronizing reads and writes if you >start using a selection order other than first-come-first-serve. An elevator algorithm doesn't produce starvation. First the head sweeps to the right, servicing the closest request in that direction. When there are no more requests to the right, the head sweeps to the left, servicing the closest requests in that direction until it again runs out of requests. There are no problems with synchronizing reads and writes as long as requests on the same track and block are performed in a first-come-first-serve order. Of course if one process is making synchronous read and write requests all over the disk, then only disk cacheing can save you. Mike Stroyan, [hplabs!]hpfcla!stroyan
ugpete@sunybcs (Peter Theobald) (02/18/88)
< This sure looks like line-eater food to me! > In article <3247@watcgl.waterloo.edu> bmacintyre@watsol.waterloo.edu (Blair MacIntyre) writes: >In article <8504@sunybcs.UUCP> ugpete@sunybcs.UUCP (Peter Theobald) writes: >> >>AmigaDos should sort disk requests by track. This way if three processes >>ask for three different files scattered all over the disk, instead of >>jumping around like a Tasmianian Devil getting blocks from first one >>file, then the other then back to the first, AmigaDos would load in the >>blocks on the tracks currently nearest the read head. >Unfortunately, this scheme could cause starvation ( ie. a certain read >request doesn't get serviced because it's on the opposite end of the >disk ) not to mention problems with syncronizing reads and writes if you >start using a selection order other than first-come-first-serve. >Blair No, that wouldn't cause starvation. The disk would service every request on cylinders 0 - 79 in that order, and then service every request on tracks 79 - 0 in that order (or however # of cylinders there are). This process would repeat until there are no more requests. A request cannot be starved because it must at most wait for the head to travel to one extreme and back. -Pete Peter Theobald SUNY/Buffalo Computer Science internet: ugpete@cs.buffalo.edu bitnet: ugpete@sunybcs.BITNET uucp: ..!{ames,boulder,decvax,rutgers}!sunybcs!ugpete csnet: ugpete@buffalo.CSNET
bryan@mothra.cs.utexas.edu (Bryan Bayerdorffer) (02/18/88)
In article <3247@watcgl.waterloo.edu> bmacintyre@watsol.waterloo.edu (Blair MacIntyre) writes: =-In article <8504@sunybcs.UUCP> ugpete@sunybcs.UUCP (Peter Theobald) writes: =-><Line Eater Motel. Line eaters check in.... but they don't check out!> =-> =->AmigaDos should sort disk requests by track. This way if three processes =->ask for three different files scattered all over the disk, instead of =->jumping around like a Tasmianian Devil getting blocks from first one =->file, then the other then back to the first, AmigaDos would load in the =->blocks on the tracks currently nearest the read head. Then it would move =->the head to the next track with requested data on it, etc... It could =->continue this process sweeping the head back and forth across the disk =->picking up what is needed, wasting the least amount of time. =-> This would eliminate thrashing, and would speed up disk accesses =->to boot! I think this is similar to what a clone of Peter da Silva meant by =->single-threading loadSegs. =-> How major a change in AmigaDog is this? =- =-Unfortunately, this scheme could cause starvation ( ie. a certain read =-request doesn't get serviced because it's on the opposite end of the =-disk ) Have we forgotten our disk-scheduling algorithms from undergraduate OS class, hmm? :-) :-) To prevent starvation and still get near-optimal performance, one uses SCAN, aka the elevator algorithm. Here, the head travels in one direction all the time, filling the next closest request, until it gets to the innermost (outermost) track, or until there are no more requests in that direction. Then it does the same thing in the other direction--just like an elevator. If you don't want to favor requests that come in just before the head turns around in their direction over those that "just missed the elevator" a long time ago, then you use CSCAN, in which the head seeks quickly to one end of the disk after each traversal, so that passes are always in only one direction. Think of the disk as a torus, or of an elevator that wraps around from the basement to the roof. My guess is though, that (as always), access to the root block would get in the way of this algorithm, and the performance wouldn't improve much. The mainframe solution to this is to keep directory and data information on separate drives, but I don't think that AmigaDoze (can you say 'zzzz', little cloud?) has that luxury, especially with floppies. =-not to mention problems with syncronizing reads and writes if you =-start using a selection order other than first-come-first-serve. Huh? Could you explain this? ______________________________________________________________________________ /_____/_____/_____/_____/_____/_____/_____/_____/_____/_____/_____/_____/_____/ |_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____| _No dark sarcasm in the classroom|_____|_____|_____|_____|_____|_____|_____|___ |____Teachers leave the kids alone__|_____|_____|bryan@mothra.cs.utexas.edu___| ___|_____|_____|_____|___{ihnp4,seismo,...}!ut-sally!mothra.cs.utexas.edu!bryan |_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|
steveb@cbmvax.UUCP (Steve Beats) (02/18/88)
In article <8626@sunybcs.UUCP> ugpete@joey.UUCP (Peter Theobald) writes: >< This sure looks like line-eater food to me! > > > >In article <3247@watcgl.waterloo.edu> bmacintyre@watsol.waterloo.edu (Blair MacIntyre) writes: >>In article <8504@sunybcs.UUCP> ugpete@sunybcs.UUCP (Peter Theobald) writes: >>> >>>AmigaDos should sort disk requests by track. This way if three processes >>>ask for three different files scattered all over the disk, instead of >>>jumping around like a Tasmianian Devil getting blocks from first one >>>file, then the other then back to the first, AmigaDos would load in the >>>blocks on the tracks currently nearest the read head. > >>Unfortunately, this scheme could cause starvation ( ie. a certain read >>request doesn't get serviced because it's on the opposite end of the >>disk ) not to mention problems with syncronizing reads and writes if you >>start using a selection order other than first-come-first-serve. > >>Blair > >No, that wouldn't cause starvation. The disk would service every request on >cylinders 0 - 79 in that order, and then service every request on tracks >79 - 0 in that order (or however # of cylinders there are). This process >would repeat until there are no more requests. A request cannot be starved >because it must at most wait for the head to travel to one extreme and back. > > -Pete > >Peter Theobald SUNY/Buffalo Computer Science No, that scheme wouldn't work either. I tried putting access sorting into FFS and backed out of it again because it didn't help. FFS solves thrashing problems by doing large, consecutive reads as large, consecutive reads and doesn't split them into separate block requests to the disk driver. If you had two processes accessing oldFS, the requests would come in to the driver as single block transfers from opposite ends of the disk anyway. You would automatically be servicing requests in 0-79/79-0 order. Let me take this opportunity to suggest that ALL file read and write requests be done in the largest increments possible. This ain't going to gain you much under the current FS but you're going to be ready to take advantage of FFS when it hits the streets. A second caveat, try not to do requests from odd addresses! Although both OldFS and FFS support this, you are going to get the MOST inefficient response from both systems if you do it. Cache buffers are used when the requested transfer address is odd and since these buffers are allocated on even boundaries, it is nescessary to BYTE COPY all the data to or from the user buffer. Now I'm not saying that everyone should start using half meg buffers, but keep 'em reasonable, say around 16K at least. Steve
cmcmanis%pepper@Sun.COM (Chuck McManis) (02/19/88)
In article <8626@sunybcs.UUCP> ugpete@joey.UUCP (Peter Theobald) writes: |>No, that wouldn't cause starvation. The disk would service every request on |>cylinders 0 - 79 in that order, and then service every request on tracks |>79 - 0 in that order (or however # of cylinders there are). This process |>would repeat until there are no more requests. A request cannot be starved |>because it must at most wait for the head to travel to one extreme and back. But if the algorithim is not to smart then a program banging on track 79 will affect the read latency time of the program that is trying to read track 0. Probably not killer but it does add an artifact to the scheduling algorithim and make programs with scattered data run slower than programs with localized data. --Chuck McManis uucp: {anywhere}!sun!cmcmanis BIX: cmcmanis ARPAnet: cmcmanis@sun.com These opinions are my own and no one elses, but you knew that didn't you.
devilbis@csd4.milw.wisc.edu (Vilbiss Warren C De) (02/19/88)
(message being posted by Mike Shawaluk) In article <33989UH2@PSUVM> UH2@PSUVM.BITNET (Lee Sailer) writes: >In article <8626@sunybcs.UUCP>, ugpete@sunybcs (Peter Theobald) says: >> >>In article <3247@watcgl.waterloo.edu> bmacintyre@watsol.waterloo.edu (Blair MacIntyre) writes: >>>In article <8504@sunybcs.UUCP> ugpete@sunybcs.UUCP (Peter Theobald) writes: >>>> >>>> <lots of stuff about disk thrashing> Hey, guys, I'm no expert on the subject of optimized disk seeking algorithms, but it seems to me that a half-way decent disk caching program would just about eliminate the majority of the thrashing that everyone's been talking about! For example, two programs are each trying to read from tracks 5 and 75 respectively; when the first read takes place from track 5, the entire track would go in the cache; then the second program goes to track 75 & reads. Then, when program #1 wants data from track 5 again, it gets it out of the cache, and the head doesn't have to move! Now, I will be the first to admit that there are a few holes in my example that need plugging; for example, these two programs probably aren't going to be reading JUST tracks 5 and 75, but possiblu several tracks each, and they aren't going to be necessarily in contiguous order. Also, my example only covers reading files, not writing, which is another case altogether. But, anyone out there who's ever used FACC or FACC II will atest to the improvements in floppy disk performance that are achieved. All in all, the best $21.00 (from Abel) that I've spent on my Amy so far! - Mike Shawaluk {sorry, no fancy signature yet!} order. Also, the
dillon@CORY.BERKELEY.EDU (Matt Dillon) (02/20/88)
Using the 'reading from two files simultaniously' example... AmigaDOS, from what I can tell, not only requests blocks one at a time, but also queues only one request per file handle at a time. So no matter which track seeking scheme you use, the trackdisk will always be getting just two requests simultaniously for two widely separated tracks, and no further requests until it has completed at least one of the two (at which point is begins processing the second one before the next request after the completed first one is issued). Now let me see if I can turn that into a tongue twister. The trackdisk's track seeks to seek to Ami's request but Ami's request seeks to seek the trackdisk's track just one block per track per handle. -Matt
peter@nuchat.UUCP (Peter da Silva) (02/21/88)
In article <8504@sunybcs.UUCP>, ugpete@sunybcs (Peter Theobald) writes: > AmigaDos should sort disk requests by track... > This would eliminate thrashing, and would speed up disk accesses > to boot! I think this is similar to what a clone of Peter da Silva meant by > single-threading loadSegs. Alas, this wouldn't help. Here's what would happen. Proc a: loading a file that's on tracks 10 and 11. Proc b: ditto for 20 and 21 Proc c: ditto for 30 and 31 All procs do their first requests. Proc a gets its block back, and requests the next block. Meanwhile disk is heading out to satisfy procs b and c. Proc b gets its block back, and requests the next block. Meanwhile disk is heading out to satisfy c. Proc c gets its block back, and requests the next block. Meanwhile disk is heading back to satisfy procs a and b. Proc b gets its block back, and requests the next block. Meanwhile disk is heading back to satisfy proc a. Proc a gets its block back, and requests the next block. Meanwhile disk is heading out to satisfy procs b and c. The problem is that ALL requests for ALL files aren't out there at the same time. What would help would be a few track buffers. Executable files tend to be pretty contiguous, so: All procs do their first requests. Proc a gets its block back, and requests the next block. Meanwhile disk is heading out to satisfy procs b and c. However the next 10 requests from proc A will be satisfied from the track cache. Proc a finally requests a block on another track... Proc b gets its block back, and requests the next block. Meanwhile disk is heading out to satisfy c. However the next 10 requests from proc B will be satisfied from the track cache. Proc c gets its block back, and requests the next block. Meanwhile disk is heading back to satisfy procs a and b. However the next 10 requests from proc C will be satisfied from the track cache... Still shuffling, but 11 times as fast. -- -- a clone of Peter (have you hugged your wolf today) da Silva `-_-' -- normally ...!hoptoad!academ!uhnix1!sugar!peter U -- Disclaimer: These aren't mere opinions... these are *values*.
ajk@goanna.oz (Alan Kent) (02/24/88)
> An elevator algorithm doesn't produce starvation.
One point that seems to be missed here is that the elevator algorithm
works well for large multi-user systems where there maybe 30 disk requests
pending in the queue, but for an amiga with only 2 or maybe 3 requests,
it doesnt really help that much.
Alan Kentterry@wsccs.UUCP (terry) (02/27/88)
In article <8504@sunybcs.UUCP>, ugpete@sunybcs (Peter Theobald) writes: > AmigaDos should sort disk requests by track. This way if three processes > ask for three different files scattered all over the disk, instead of > jumping around like a Tasmianian Devil getting blocks from first one > file, then the other then back to the first, AmigaDos would load in the > blocks on the tracks currently nearest the read head. Good idea. That way if the head is in position 0 and someone requests block 1 and someone else requests block 5 an someone requests block 79, I can wait forever for it to get to 79. Example: [cli-1] copy df0: df1: all [cli-2] run program-that-opens-ralph-the-file-begining-on-df0:-track-79 While I agree that the seek optimization algorythm needs work, it doesn't need that. A better method (if you had ram) would be to cache the sectors on either edge (some reasonable number) and then spend most of your time flitting around in the center. A floating cache, perhaps the 10 most frequently accessed tracks, as determined by a track access count table with timer entries to preserve 'freshness', could also be used. Writes could be flushed when absolutely necessary or when the head went over a track on it's way to another track that wasn't in cache. This would solve the biggest problem (writes) that occurs with FaccII. Unfortunately, to impliment any nifty-save-me-time algorythm, you have to make mountable disks unmountable or at least "forced-flushable" with a user command such as 'sync' under UNIX. Unfortunately, most modern computers can't tell when you are reaching for the drive door to remove a disk, yet :-). Agreed, however, that something SHOULD be done. I hate the ST people telling me 'my drives faster than yours'... with their new format toys, an ST can do 800+ K on a disk too, and it's still fast. My Leading edge at work is faster, and it's *OLD*. DO SOMETHING COMMODORE! PS: I would write one myself, but I'm afraid that since Commodore doesn't advertise in the US except inside magazines dedicated to the machines that the reader already has, I wouldn't be able to sell enough to make it worth my while... A placed-ly high source in MicroSoft says that's why they're not porting Xenix to it, and the ST is too low end. | Terry Lambert UUCP: ...!decvax!utah-cs!century!terry | | @ Century Software or : ...utah-cs!uplherc!sp7040!obie!wsccs!terry | | SLC, Utah | | These opinions are not my companies, but if you find them | | useful, send a $20.00 donation to Brisbane Australia... | | '...Hep me, Hep me! I bin hip-mow-tized' - David Letterman |