DEC.BANKS@MARLBORO.DEC.COM@caip.RUTGERS.EDU (02/01/86)
From: Dawn Banks <DEC.BANKS@MARLBORO.DEC.COM> Perhaps some of my comments on AmigaDOS have been slightly misconstrued. When I compare AmigaDOS to OS-9, it's as constructive criticism, and not an announcement that AmigaDOS is no good because "it isn't OS-9". In any case, while I think that the Amiga software is pretty worth while, I also think that some properly placed constructive criticism may help make the product better in the future. Certainly, you could probably find as many misfeatures of OS-9 as exist in AmigaDOS, but overall, I think the Amiga could learn a few things about multitasking from OS-9. To reiterate my favorite feature of OS-9's multitasking: I think the way OS-9 handles multiple invokations of a task to cause much less overhead. On the 6809 version of OS-9 that I've used, all tasks are compiled as position independent code (an exceedingly easy thing to do on a 6809), with all "own" storage pointed to by the "U" register. Thus, when a program is loaded into memory, no relocation need be performed, and when the task is started, all that needs to be done is allocate the storage (which includes the stack), and point U and S at it (and the direct page register), fixup the internal OS-9 data structures, and start the task. Another invokation would simply allocate another storage area, and use the same code segment. All of this happens implicitly, without the programmer needing to make any special allowances. This provides the following features: * Running multiple copies of something doesn't cost you twice for the code segment. * locking a code segment into memory (by incrementing the use count) achieves precisely the same effect as putting it into RAM: on the Amiga, with the exception that when you run it, you aren't carrying around two copies of the program in ram, as you would be on the Amiga * Even if the segment isn't locked, running a second invokation happens a lot faster, because nothing needs to be read from disk. This happens more often than you might think, most notably with the OS-9 shell. * library segments can be shared (as with the Amiga), but nothing special needs to be done to declare them as libraries, which can save the programmer some time. What all of this boils down to is that (what I think is) the major failing of the Amiga is its resource utilization. Sure a 40 meg hard disk and 8M of RAM would certainly mask the problem, however, I'm still not sure why I should be finding myself running out of resources so often on a machine with 512K of ram and two 880K byte floppies. But, I still like the Amiga and its operating system A LOT. --------
hand@ncsu.UUCP (Steven Hand) (02/04/86)
Dawn Banks writes: >What all of this boils down to is that (what I think is) the major failing of >the Amiga is its resource utilization. Sure a 40 meg hard disk and 8M of >RAM would certainly mask the problem, however, I'm still not sure why I should >be finding myself running out of resources so often on a machine with 512K of >ram and two 880K byte floppies. I agree. A few years ago I used a PDP-11/60 with the RSX-11/M OS with 6-7 users and several background tasks, all on 128K MEMORY. Sure it had a hard disk and swapped tasks in and out of memory, but it shows what can be done with a professional OS. It's time for microcomputer OS's to catch up with what *was* state-of-the-art years ago. I think OS-9 would be great for the Amiga, but if you want to write your own quality OS for the Amiga, much of the work has ALREADY BEEN DONE and can be found in the book Operating System Design: The XINU Approach by Douglas Comer (Prentice-Hall) (XINU stands for "XINU is not UNIX"). This very readable book contains the *SOURCE CODE* for an entire hierarchically-structured OS with MANY features like: - True multitasking. Processes don't step on each other or crash the system. The resources of *killed* processes are reclaimed. Processes can SHARE CODE. Uses priorities and Round Robin scheduling. - Interprocess communication through two kinds of message passing. Ports. NETWORKING with hooks for remote file sharing, servers, and diskless nodes. - Interrupt-driven, device-independent I/O. Device drivers. Nice file system with ORDERED DISK SEEKS, pseudo-devices, indexed sequential access method. - Real-time clock, scheduled waits, semaphores (no busy waits). The book describes how all the routines work and gives the source code in C. It is all done in about 5800 lines of C and 650 lines of assembler, and runs in about 4000 bytes (!). You can get a MAGTAPE from the publisher with all this and a CROSS DEVELOPMENT SYSTEM that runs on VAX Berkeley UNIX 4.1 or 4.2. (Includes C compiler for LSI-11 microcomputer, linking loader, up/down-loaders, debugger, utilities). While the book describes an LSI-11 as the target, it mentions that students have ported XINU to the 68000. Maybe you can get the source for the 68000 version? Random thoughts... Maybe the best things about Amiga's OS (libraries, etc.) can be added to XINU. Since the book is readily available, this could be a group project. How about integrating the stuff from the Portable User Interface Library. Since it is copyright 1984, maybe more has been added to the OS that isn't mentioned in the book (CLI, spooler, etc.) The author is mentioned as working at Bell Labs... Are you on the net? What do you think? Actually there are many other OS's out there, maybe from other university projects. Lastly, this book could help the Commodore OS people make Amiga's OS better... are you listening? Disclaimer: I have only read the book, not actually used the OS.
jbs@mit-eddie.UUCP (02/04/86)
In article <2987@ncsu.UUCP> hand@ncsu.UUCP (Steven Hand) writes: >Dawn Banks writes: > >>What all of this boils down to is that (what I think is) the major failing of >>the Amiga is its resource utilization. Sure a 40 meg hard disk and 8M of >>RAM would certainly mask the problem, however, I'm still not sure why I should >>be finding myself running out of resources so often on a machine with 512K of >>ram and two 880K byte floppies. > >I agree. A few years ago I used a PDP-11/60 with the RSX-11/M OS with 6-7 >users and several background tasks, all on 128K MEMORY. Sure it had a hard >disk and swapped tasks in and out of memory, but it shows what can be done with >a professional OS. It's time for microcomputer OS's to catch up with what >*was* state-of-the-art years ago. > I think it is important to note however, that if you were to try this today, using the most recent version of RSX-11/M+, you will find that: 1) Many additional capibilities and "nicities" have been added. 2) The memory requirements have increased dramatically. 3) The CPU overhead has increased significantly. 4) Those same 6-7 users would find the system resources sufficiently depleted to make using the machine an unpleasant experience. 2-3 users would be much more reasonable. Don't forget also, that the 11/60 dosn't support graphics, windows, etc., etc., etc.... Operating systems involve real trade-offs. Don't fool yourself into believing that XINU, at 4K bytes, is the answer to this most complex problem. Jeff Siegal - MIT EECS
coatta@utcsri.UUCP (Terry Coatta) (02/05/86)
Although the full source code for XINU is given in the Comer book, it is of limited use. Many parts of the system would require a substantial amount of rewriting. For instance, the file system that Comer uses is completely flat, and restricted to a maximum of 26 files. Any useable version of XINU would have to have the entire set of file system routines rewritten. For the Amiga, there would also be massive amounts of code required to allow XINU to have a pretty visual interface, since Comer assumes "tty-like" terminals. Finally, I might add that XINU is not what I would refer to as good clean OS design (its alot better than some real OS code I've seen...) -- the use of interrupts, and system processes is fairly complex, and needlessly so (just look at the way a Thoth system deals with interrupts, which more or less just makes them look like messages delivered by another process).
cg@myrias.UUCP (Chris Gray) (02/05/86)
The 68000 can address +/- 32K from the program pointer (+/- 128 if an index register is also specified). All constant displacements are either 16 bits or 8 bits (no 32 bit ones - you have to put them in a register and use indexing to accomplish that). Thus, position independent code would be limited to 32K byte chunks. That's just not enough, given the code size of some programs we would want to run on our 8.5Meg Amigas. Also, the philosophy of Amigados is to allow scatter loading of programs, which can successfully load a program even if no single available chunk of memory is big enough for it. This also makes position independent code impossible. I haven't delved deeply into libraries, but they strike me as a way to get essentially the same benefits (shared code). If you want to lock some code into memory, just use it's library and don't do a 'CloseLibrary' before you exit - voila! The standard AmigaDos CLI takes essentially no time to load up since it's mostly (entirely?) in the Kickstart stuff. For most of what I do (writing programs), it is entirely sufficient. P.S. If you haven't tried running Wack, give it a try. It'll show you all sorts of neat things about the system. Chris Gray {sask,ubc-vision,ihnp4}!alberta!myrias!cg
breuel@h-sc1.UUCP (thomas breuel) (04/24/86)
A complaint, and two questions: I have philosophical problems with the AmigaDos file system. The file system appears to be optimised for finding a named entry quickly and for making directories small and cheap: the directories are hashed and do not contain the filenames. This means that for wildcard expansion and select-file-dialog-box'es, one block has to be read for each entry in a directory. An unrelated, but (philosophically) similar problem is the use of linear, linked blocks for file allocation tables. It appears that allocation blocks are not buffered, so that for each seek, Dos has to scan through the whole linked list on disk. Needless to say that this is dreadfully slow. The above two problems are compounded by the apparent lack of any attempts to allocate, say, all allocation blocks on the same track so that scanning through the allocation list may require many seeks. Now, even if the above statements are not entirely accurate, the fact remains that the AmigaDos file structure is, for practical purposes, too inefficient. It discourages seeks and discourages directory scans. Instead it gives some (doubtful) savings due to small directory sizes and simplicity of algorithms for seeks (read lazy programmers ?!). I'm not writing this purely because I disagree with the file system structure in some abstract manner, but because for several applications, this file system is almost unusable (e.g. picking characters out of a 700k Kanji font file). It should also be noted that a simple disk cache at the disk driver level is not necessarily going to improve matters. What is really needed is a way to instruct Dos to keep the allocation tables for a specific file in memory. Ultimately, I find that the current file system should be replaced with something more UN*X like (with name/inode pairs in directories, inodes, and links). I'm not saying this because I find the UN*X file system pleasing to the eye, but because it works, and because I can do an 'echo *' or 'ls' and don't have to wait for minutes. So, one question, you have seen already: I need a workaround to access random parts of a large file quickly. I would greatly prefer not to split the file up... (and that wouldn't necessarily help anyhow). The other question is: how are the ROM Kernel and AmigaDos actually glued together? Where and when is each part of the OS loaded? Are there hooks for user file system code (e.g. to implement a remote file system)? Pointers to the documentation or straight answers would be appreciated. Thomas.
mwm@ucbopal.berkeley.edu (Mike (I'll be mellow when I'm dead) Meyer) (04/27/86)
In article <1076@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes: >A complaint, and two questions: > >I have philosophical problems with the AmigaDos file system. >The file system appears to be optimised for finding a named entry >quickly and for making directories small and cheap: the directories >are hashed and do not contain the filenames. This means that for >wildcard expansion and select-file-dialog-box'es, one block has >to be read for each entry in a directory. True, the AmigaDOS file structure looses on globs. However: >I can do an 'echo *' or 'ls' and don't have to wait for minutes. Minutes? How about a couple of seconds/file. That's closer to what I get. For ~20 files, AmigaDOS runs about half the speed of Unix. But Unix is running on an RA81 and AmigaDOS is running on a floppy. If you want to do ls -l (AmigaDOS list), Unix gets extra block reads to get inodes, but AmigaDOS has the same number of reads as with a dir. >An unrelated, but (philosophically) similar problem is the use >of linear, linked blocks for file allocation tables. I'm not quite sure what you're referring to - the linked list of of data blocks, or the linked list of blocks with pointers to data blocks. The second one is what's important, and it resembles Unix, except Unix has a funky multi-level tree. For files with one or three allocation blocks, AmigaDOS and Unix both need either one or three disk references. For two allocation blocks, AmigaDOS needs two disk references, and Unix needs three. For things beyond three allocation blocks, AmigaDOS needs one reference per block, and Unix uses three or four (depending on Unix flavor) for all of them. Of course, some Unixes go to linked lists of lists of allocation blocks. However, with 1K blocks, any file small enough to fit on a floppy will fit in two or three blocks. >It appears that allocation blocks are not buffered, so that for >each seek, Dos has to scan through the whole linked list on disk. >Needless to say that this is dreadfully slow. Yeah - all two or three blocks. Some caching is done, though. At the end of this article, you'll find a program that times calls to Seek (the capitalization is correct - I used the AmigaDOS calls, not the stdio calls). The timings look flat, and suggest that the allocation blocks are cached, to some degree or another. The trackdisk buffer also shows up. It appears that doing a seek takes ~30 ticks, at least the second time you look in that area of the file (and I used a 700K+ file). But play with it yourself. of course, seeks *DO* seem somewhat slow. Someone oughta play with it some more (but I'm not gonna). Interestingly, the Read after the Seek always runs in zero ticks. This indicates something wrong - the system shouldn't do any physical IO for a seek until a Read or Write follows it. Even CP/M-80 got that right (at least, the BIOSes I wrote did). >The above two problems are compounded by the apparent lack of any >attempts to allocate, say, all allocation blocks on the same track >so that scanning through the allocation list may require many seeks. Actually, you want something like the 4BSD fast file system - trying to put blocks at the correct interleave on the same track/cylinder. Since the allocation blocks aren't used very often in normal use (see 'A Trace-Driven Analysis of the Unix 4.2 BSD File System' in the 10th SOSP), doing that with allocation blocks isn't suited to a multi-tasking system. The apparent caching of the allocation blocks when they are read in is probably optimal. >Now, even if the above statements are not entirely accurate Well, it looks to me like the one about seeks is flat wrong. The comment about doing globbing is true; I still can't figure out why they used globbing so heavily in the WorkBench. >the fact >remains that the AmigaDos file structure is, for practical purposes, >too inefficient. I hadn't noticed. But I use deep, narrow trees, so directory searching isn't murderous for me (the Browser has problems when I try to look at other peoples disk, with fat trees). >It discourages seeks and discourages directory scans. >Instead it gives some (doubtful) savings due to small directory sizes >and simplicity of algorithms for seeks (read lazy programmers ?!). Sorry, but the AmigaDOS file system is probably less space effecient that Unix. You add one block for file header, then put the name and link information in each block in the file. The savings in the directory are neglible compared to this. >I'm not writing this purely because I disagree with the file system >structure in some abstract manner, but because for several applications, >this file system is almost unusable (e.g. picking characters out of >a 700k Kanji font file). Give me a file system, I'll give you an application for which it's almost unusable. Doing high-quality DBM kills most systems that grew out of the Multics OS family. >It should also be noted that a simple disk cache at the disk driver >level is not necessarily going to improve matters. What is really needed >is a way to instruct Dos to keep the allocation tables for a specific >file in memory. No, you need a GOOD disk caching system - comparable to 4BSD, and better than the System V cache. The way AmigaDOS handles (or mishandles) memory management makes this nontrivial. I hope to take a crack at it sometime this year. >Ultimately, I find that the current file system should be replaced >with something more UN*X like (with name/inode pairs in directories, >inodes, and links). I'm not saying this because I find the UN*X >file system pleasing to the eye, but because it works, and because No, NO, NO! Going to an ilist with name/inode pairs DOUBLES the number of disk accesses to open a file by name! It also makes the file system less robust - a hit on the ilist is fatal to Unix, but the AmigaDOS file system can theoretically be recovered from any single-block hit. The AmigaDOS file system is theoretically faster than the Unix file system for most operations, the major exception being searching a directory. It trades space and links for robustness. On a home machine, this is a win - *IF* there's a tool for rebuilding broken disks. I understand that MetaComCo has one; why don't we have it? >So, one question, you have seen already: I need a workaround to access >random parts of a large file quickly. I would greatly prefer not to split >the file up... (and that wouldn't necessarily help anyhow). I suggest you use the same solution that people who need fast disk access on Unix used. Use the raw disk. There are examples of using the trackdisk driver floating around on the net; using that makes doing your seeks easy: divide the byte number you want by the number of bytes per track, and go read the track it's on. There's no way to make it go faster, except buying faster disks. <mike /* * seektest - a quick test to see if the time to seek to a byte is * flat, or if it gets longer as you go farther into the file. */ #include <exec/types.h> #include <stdio.h> #include <libraries/dos.h> static long file ; void do_seek(int), do_read(int), done(int, char *) ; void main(argc, argv) char **argv; { struct DateStamp How_Long, Time_Function() ; int whereto ; if (argc < 2) done(20, "usage: seektest <file>") ; if ((file = Open(argv[1], MODE_OLDFILE)) == 0) done(20, "can't open input file") ; for (;;) { printf("? ") ; scanf("%d\n", &whereto) ; if (whereto == 0) done(0, "exit") ; Seek(file, 0, OFFSET_BEGINING) ; How_Long = Time_Function(do_seek, whereto) ; printf("Seek took %5d ticks\n", How_Long . ds_Tick) ; How_Long = Time_Function(do_read, 0) ; printf("Read took %5d ticks\n", How_Long . ds_Tick) ; } } /* * Time_Function - just return a DateStamp saying how long it took * to call the given function with the given argument */ struct DateStamp Time_Function(function, argument) void (*function)(int); int argument; { struct DateStamp start, end, diff ; DateStamp(&start) ; (*function)(argument) ; DateStamp(&end) ; diff . ds_Tick = end . ds_Tick - start . ds_Tick ; if (diff . ds_Tick < 0) { diff . ds_Tick += (60 * TICKS_PER_SECOND) ; --(end . ds_Minute) ; } diff . ds_Minute = end . ds_Minute - start . ds_Minute ; if (diff . ds_Minute < 0) { diff . ds_Minute += (24 * 60) ; --(end . ds_Days) ; } diff . ds_Days = end . ds_Days - start . ds_Days ; return diff ; } /* * do_seek - seek to where in (global) file. */ void do_seek(where) int where; { if (Seek(file, where, OFFSET_BEGINING) < 0) done(20, "Seek failed") ; } /* * do_read - get one byte from the (global) file, and throw it away. */ void do_read(shit) int shit; { int junk ; if (Read(file, &junk, 1) < 0) done(20, "Read failed") ; } /* * done - just exit, no problems. */ void done(how, why) int how; char *why; { fprintf(stderr, "seektest: %s\n", why) ; exit(how) ; }
daveh@cbmvax.UUCP (04/29/86)
In article <1076@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes: >A complaint, and two questions: > >I have philosophical problems with the AmigaDos file system. >The file system appears to be optimised for finding a named entry >quickly and for making directories small and cheap: the directories >are hashed and do not contain the filenames. This means that for >wildcard expansion and select-file-dialog-box'es, one block has >to be read for each entry in a directory. Cheap directories are important on a small-disk machine. And at least this method allows for essentially unlimited directory sizes, unlike other DOS systems popular on microcomputers today. >I'm not writing this purely because I disagree with the file system >structure in some abstract manner, but because for several applications, >this file system is almost unusable (e.g. picking characters out of >a 700k Kanji font file). > >It should also be noted that a simple disk cache at the disk driver >level is not necessarily going to improve matters. What is really needed >is a way to instruct Dos to keep the allocation tables for a specific >file in memory. > >Ultimately, I find that the current file system should be replaced >with something more UN*X like (with name/inode pairs in directories, >inodes, and links). I'm not saying this because I find the UN*X >file system pleasing to the eye, but because it works, and because >I can do an 'echo *' or 'ls' and don't have to wait for minutes. Though, really, when was the last time you hacked on lots of UN*X stuff on a micro with 3 1/2" floppies. Most of the VAX or SUN machines would run even AmigaDOS style directories quite a bit faster. >So, one question, you have seen already: I need a workaround to access >random parts of a large file quickly. I would greatly prefer not to split >the file up... (and that wouldn't necessarily help anyhow). > >The other question is: how are the ROM Kernel and AmigaDos actually >glued together? Where and when is each part of the OS loaded? >Are there hooks for user file system code (e.g. to implement a remote >file system)? Pointers to the documentation or straight answers >would be appreciated. > > Thomas. You could directly access below AmigaDOS, which is also the answer to your last question as well. The ROM Kernal supports a disk-loaded device, called "trackdisk.device", as the low-level disk interface. Going any lower would put you at in direct contact with the hardware, which is something you really don't want. Anyway, the trackdisk device allows read or write of any 512 byte block in the disk, and the RKM gives examples of accessing this in terms of linear blocks, or in terms of track, sector, and disk side. In any case, AmigaDOS builds on top of this, assigning specific values to certain longwords in every 512 byte block. The AmigaDOS Technical Reference Manual (from the developer's kit) is a good pointer to the way DOS organizes directory, file, and data blocks out on the disk. Last weekend I saw a consumer version of this book, called the AmigaDOS Reference Guide, or something like that, in Walden Books in the Deptford Mall in NJ. The book actually contained the developers' AmigaDOS User's Manual, the Developers' Manual, and the AmigaDOS Technical Reference Guide. For a specialized application, its certainly possible to go below the DOS level, and it might even be reasonable to write your data in a DOS compatible format, but where you have control over which blocks get allocated in which order, to perhaps facilitate faster reading of your files. -- Dave Haynie {caip,inhp4,allegra,seismo}!cbmvax!daveh "There, beyond the bounds of your weak imagination Lie the noble towers of my city, bright and gold" -Genesis
cc1@ucla-cs.ARPA (Michael Gersten) (04/29/86)
In article <160@cbmvax.cbmvax.cbm.UUCP> daveh@cbmvax.UUCP (Dave Haynie) writes: >In article <1076@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes: >>A complaint, and two questions: >> >>I have philosophical problems with the AmigaDos file system. >>The file system appears to be optimised for finding a named entry >>quickly and for making directories small and cheap: the directories >>are hashed and do not contain the filenames. This means that for >>wildcard expansion and select-file-dialog-box'es, one block has >>to be read for each entry in a directory. > >Cheap directories are important on a small-disk machine. And at least this >method allows for essentially unlimited directory sizes, unlike other DOS >systems popular on microcomputers today. > *** THOSE ARE NOT CHEAP DIRECTORIES *** They are VERY expensive. 512 bytes per file entry, plus another 512 for the directory itself. My model 1 (it is NOT trash-dos) needs only 32 bytes per file (plus one for hash byte); it can support directories with no more space needed. (But it does, like unix, has only a fixed number of 'inodes' (fde's, file directory entries. Max of 224. And no, it has no directory support, but no more space would be needed.) Now, here's a real question. Take a typical AmigaDos disk, and a typical Unix file system, and a typical ms-dos disk. Compare the % overhead on each, where overhead is defined as space used - data (in bytes) ------------------ space used and compare. My guess is that Amiga will come out with a high overhead. disclaimer | ihnp4!ucla-cs!cc1 | Michael Gersten | Joke: 412 -- Views expressed here may not be those of the Computer Club, UCLA, or anyone.
breuel@h-sc1.UUCP (thomas breuel) (04/30/86)
Before getting into a closer, point by point discussion (see next article), let me re-phrase my questions about AmigaDOS: -- how can I implement a custom file system? Can I write a 'File Handler Process' (mentioned in the AmigaDOS Technical Reference Manual)? Where is this documented in detail? -- how can I get fast seeks on a file? I don't require blinding speed, but delays in the second range for seeks on long files are just unacceptable. One solution, albeit a dirty hack, is to re-implement the file handler with sufficient buffering in my application. Needless to say that I am reluctant to do this. The kind of solution I would hope for is that there is a way to instruct the file system handler to buffer larger chunks of the block allocation table for a particular file. The fact that seeks are extremely slow is also (presumably) the reason why Manx ln and ALINK are so slow (but this is just a guess). If this problem isn't fixed in future releases of the system, I predict that there will be problems with getting database applications to work at acceptable speeds on the Amiga. Any help and pointers to the documentation would be appreciated (i.e. page references in the technical documentation). Thomas. PS: these are by no means my only questions about AmigaDOS, but they are, at the moment, the most important ones.
jamesp@tekla.UUCP (James Perkins) (04/30/86)
In article <1076@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes: >A complaint, and two questions: > >I have philosophical problems with the AmigaDos file system. >The file system appears to be optimised for finding a named entry >quickly and for making directories small and cheap: the directories >are hashed and do not contain the filenames. This means that for > > Thomas. Thomas goes on to say we should eventually replace the AmigaDOS file system with something more UN*X-like. I do not disagree with you at all, Thomas, but I can think of a possible quick hack to speed up getting a directory listing from the shell, or matching wildcards. This idea comes from a fls 'fast ls' program on our VAX BSD UN*X system here at work. I am assuming that AmigaDOS keeps "last modified dates" for each file and each directory, and that the "last modified date" of the directory is updated only when the directory contents change. (DISCLAIMER: I do not own an AMIGA [yet], nor have I perused the refernce manuals in any great detail, so I may be speaking completely out of my a**.) It would require a "get_file_names(matchstring)" routine which expects to find a 'lsfile' in each directory, which contains all the names of the files in the directory. 1: If there is no lsfile present in the directory to be listed, it would build a new one by polling all the files in the directory for thier filenames. Then one would 2: compare the last modified date of the 'lsfile' to the last modified date of the directory -- if the directory was newer than the lsfile, a new lsfile would be generated by getting the filenames out of each file; then proceed to step 3: the contents of lsfile is a list of all filenames in the directory -- now get_file_names() searches this list with whatever pattern(s) you give it, and returns a pointer to some static list of the filenames found. This will be slow each time you add or delete files in each directory, as it has to rebuild the list of filenames, but relatively fast if the directory contents are static. This would make it possible to browse through the directories (oh, what's over there) instead of dreading each list. In all reality, of course, this is just a hacked-up logical addition to the directory structure, and if the filename data were stored IN the directories, then there would not be a need to maintain a seperate database of names. Still, having a "name database" could allow scans of the directory's contents be MUCH faster, having to only open 2 files in the optimal case, instead of 20 or 30. -- _|_ James T. Perkins __|__ |___| |\ Terror |___| |___| | \ on the tektronix!orstcs!jamesp |___| |___| | \ high tektronix!dadla!jamesp _|___| |___| |___\ seas /...\_____|___|____\_/ 4635 S.W. Hillside Drive \ o o o o o o o / Portland, Oregon 97221 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
breuel@h-sc1.UUCP (thomas breuel) (04/30/86)
||I can do an 'echo *' or 'ls' and don't have to wait for minutes. | |Minutes? How about a couple of seconds/file. That's closer to what I get. |For ~20 files, AmigaDOS runs about half the speed of Unix. But Unix is |running on an RA81 and AmigaDOS is running on a floppy. It can take quite some time to list all the files in a directory, into the 60 sec range for some of the disks I have. ||It appears that allocation blocks are not buffered, so that for ||each seek, Dos has to scan through the whole linked list on disk. ||Needless to say that this is dreadfully slow. | |Yeah - all two or three blocks. Some caching is done, though. At the end of |this article, you'll find a program that times calls to Seek (the |capitalization is correct - I used the AmigaDOS calls, not the stdio calls). |The timings look flat, and suggest that the allocation blocks are cached, to |some degree or another. The trackdisk buffer also shows up. It appears that |doing a seek takes ~30 ticks, at least the second time you look in that area |of the file (and I used a 700K+ file). But play with it yourself. of |course, seeks *DO* seem somewhat slow. Someone oughta play with it some more |(but I'm not gonna). Seeking through the two or three linearly linked allocation blocks on disk can be excrutiatingly slow, however, if you have to do it for every seek, and if they are scattered. This seems to be the case for several of my disks. I can assure you that in several cases I had a strong dependence of seek time on position in the file, i.e. very fast seeks for the beginning, and long delays for seeks near the end of the file. Some arithmetic (correct me if I'm wrong): a file header block or a file list block contains 72 block pointers, which represent 36k of data in a file. For a 720k file, the allocation table can therefore grow to 20 blocks. For a search through a linear chain of blocks, this is not insignificant anymore. |The comment |about doing globbing is true; I still can't figure out why they used |globbing so heavily in the WorkBench. It's because people like me forget their filenames so often :-). A very large percentage of my CLI commands are dir's (on UN*X, ls's). Likewise, most people probably prefer to be shown a dialog box listing all available files, ready for click selection, to a string dialog box. |Sorry, but the AmigaDOS file system is probably less space effecient that |Unix. You add one block for file header, then put the name and link |information in each block in the file. The savings in the directory are |neglible compared to this. Well, the only savings are that a new, virgin directory costs nothing. Nothing (other than speed on hashed directory searches) can really be gained by moving the name from the directory into the inode, since the amount of information about each file is still the same. ||Ultimately, I find that the current file system should be replaced ||with something more UN*X like (with name/inode pairs in directories, ||inodes, and links). I'm not saying this because I find the UN*X ||file system pleasing to the eye, but because it works, and because | |No, NO, NO! Going to an ilist with name/inode pairs DOUBLES the number of |disk accesses to open a file by name! It also makes the file system less |robust - a hit on the ilist is fatal to Unix, but the AmigaDOS file system |can theoretically be recovered from any single-block hit. The AmigaDOS file |system is theoretically faster than the Unix file system for most |operations, the major exception being searching a directory. It trades space |and links for robustness. On a home machine, this is a win - *IF* there's a |tool for rebuilding broken disks. I understand that MetaComCo has one; why |don't we have it? I was not suggesting a file system *identical* to UN*X. But there are other alternatives. Again, I personally favour the idea of tree-like allocation tables (because it makes truely random accesses affordable). Also, it can actually help save space greatly if it allows for small 'seedling' files (just one allocated block) like ProDos. I believe that the loss of efficiency in 'open' by putting names back into directories is tolerable. Furthermore, for large directories, the name/inode-pair directory wins over the hash/bucket-list directory again. If done carefully, the only thing that is lost in terms of recoverability is that you may not be able to recover a file's name. Otherwise, such a file system can be as robust as the current Amiga file system. Thanks for replying, and I hope people aren't bored by this discussion. Thomas.
bruceb@amiga.UUCP (Bruce Barrett) (05/05/86)
In article <1082@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes: >[..] >-- how can I get fast seeks on a file? [..] > Thomas. > >PS: these are by no means my only questions about AmigaDOS, but they >are, at the moment, the most important ones. The seeks within files larger than 37576 bytes can be very slow, especially if you use OFSET_BEGINNING. OFFSET_CURRENT turns out to be much better, but still not blinding. This will be greatly improved in the next release. Hope this helps. --Bruce Barrett. --C-A, SW QA
bobp@amiga.UUCP (Robert S. Pariseau) (05/05/86)
V1.2 of the system software (now in testing with developers) fixes a bug which made random access disk I/O run ridiculously slow. Sigh.....
peter@baylor.UUCP (Peter da Silva) (05/07/86)
> Cheap directories are important on a small-disk machine. And at least this > method allows for essentially unlimited directory sizes, unlike other DOS > systems popular on microcomputers today. I don't know of any DOS that doesn't allow unlimited directory sizes, and I don't understand the advantage of leaving the file name out of the directory, if that is in fact occurring, since space has to be allocated for it anyway. I do think that giving each icon a seperate file is a mistake, since it makes folder displays unbearable slow. Why not do what the Integrated Solutions system does (more or less) and put all the icons in a folder in a single file in that directory? -- -- Peter da Silva -- UUCP: ...!shell!{baylor,graffiti}!peter; MCI: PDASILVA; CIS: 70216,1076
mwm@ucbopal.berkeley.edu (Mike (I'll be mellow when I'm dead) Meyer) (05/07/86)
In article <1084@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes: >It can take quite some time to list all the files in a directory, >into the 60 sec range for some of the disks I have. You must have some LARGE directories. The worst case I can find is fish disk #13, with 106 files and 6 directories, which takes less than 32 seconds to list. My c: directory (with 49 files) takes less than 12 seconds to list. Assuming that things are linear, I've gotta conclude that you've got directories with over 200 files in them. Even my junk directory on Unix isn't that bad (yet). >Seeking through the two or three linearly linked allocation blocks >on disk can be excrutiatingly slow, however, if you have to do >it for every seek, and if they are scattered. This seems to be the >case for several of my disks. I can assure you that in several cases >I had a strong dependence of seek time on position in the file, i.e. >very fast seeks for the beginning, and long delays for seeks near the >end of the file. Hmmm. I definitely saw no such correspondence. Seeks after the first took ~30 ticks no matter where in the 700K+ file they were, the first seek taking between 1.5 and 2.5 times that long, again seemingly position independent. I started with a fresh disk, so that there should be little or no fragmentation of the disk. If you didn't do that, you might try copying your data base to a freshly formatted disk, and seeing how long it takes. >Some arithmetic (correct me if I'm wrong): a file header block >or a file list block contains 72 block pointers, which represent >36k of data in a file. For a 720k file, the allocation table >can therefore grow to 20 blocks. For a search through a linear >chain of blocks, this is not insignificant anymore. You're right - I goofed. For some reason, I was thinking of 1K blocks, so each allocation block gets you 200 pointers for about 200K. Sorry. >|The comment >|about doing globbing is true; I still can't figure out why they used >|globbing so heavily in the WorkBench. > >It's because people like me forget their filenames so often :-). >A very large percentage of my CLI commands are dir's (on UN*X, >ls's). Likewise, most people probably prefer to be shown a dialog >box listing all available files, ready for click selection, to >a string dialog box. No, that's why *YOU* use globbing so heavily, not why the workbench does (opening *.info when you open a window). I don't run dir's and/or ls's all that often - but I use file completion a lot :-). >I was not suggesting a file system *identical* to UN*X. But there are >other alternatives. Again, I personally favour the idea of tree-like >allocation tables (because it makes truely random accesses affordable). >Also, it can actually help save space greatly if it allows for small >'seedling' files (just one allocated block) like ProDos. Tree-like allocation tables can be a good thing. Allowing both shouldn't be hard; it's got to be easier than the blocks/frags stuff that 4BSD does. Dynamically switching from a "linked list" of two to a log-tree when you hit three would probably be a good thing, if you're going to do both anyway (anyone at C/A listening?). >I believe that the loss of efficiency in 'open' by putting names back >into directories is tolerable. Putting names back in directories would cut the number of file entries per directory block by a factor of 8. It'd also require a redesign of the file system from the ground up, as you've gotta throw away the hashing and replace it by something else - say a linear search of the blocks in the directory, one block per 9 directory entries (roughly). >Furthermore, for large directories, >the name/inode-pair directory wins over the hash/bucket-list directory >again. If done carefully, the only thing that is lost in terms of >recoverability is that you may not be able to recover a file's name. >Otherwise, such a file system can be as robust as the current Amiga file >system. Hmmm - I'm beginning to suspect that we're using the same term for different things. Let me take time out to briefly describe the Unix tree structure, so that I know we're using the same terminology. The heart of the Unix directory tree is the ilist. This is a set of blocks at fixed locations on the file system, usually at the front (front of each cylinder group for 4BSD). Each inode in the ilist contains *all* information pertinent to a file - owner, size, status bits, pointers to blocks of data. A directory is a list of names and inode numbers, the inode number being the index into the ilist. Given this, it's obvious that an open looks like a loop that does: "search directory for name, and get inode number associated with name" "Go get block with that inode in it, so we'll have a list of blocks for the next directory" From this, it's obvious that directories with name/inode pairs in them take 2 disk accesses per element in the path. AmigaDOS takes 1 disk access per element in the path (both cases assuming that directories are "small", and ignoring the the overhead to get the file once you've find it). Putting names back in the directory will just make the definition of "small" directories much smaller. On the other hand, going to name/inode pairs in the directory gets you back to 2 disk accesses per path element. Worse yet, you either make the ilist a linked list (in which case, you'll learn what SLOW really means), or it lives in a known location on disk, meaning that a lost ilist block is a catastrophe. You could probably make the name/inode organization as robust as the AmigaDOS organization by following the same file header/block header structure. BTW, you can loose file names if you loose the file header in AmigaDOS. I think that's the worst case, though. Finally, the contention that large directories win with inode/name organizations - I disagree. Here's where the AmigaDOS caching finally comes in. Let's assume that a "small" directory requires one block on Unix, and has no collisions on AmigaDOS. For convenience, assume that "small" directories are the same size on both systems, and have N file entries (N for AmigaDOS is 72 (right?); for Unix, it's 32 for v7oid systems, a minimax of 42 on 4BSD, and probably one of 32/64/128 on sysV). Then access to a file in a small directory is the same on both systems - 1 disk access. For a directory that's got M*N entries, it's M/2 (average) on Unix to search the directory blocks - *not counting the overhead to search the allocation table*; and M/2 (average) on AmigaDOS to search the hash chain for that entry - NO EXTRA OVERHEAD. So AmigaDOS wins by an (over)head :-). Of course, for listing the files in the directory, AmigaDOS still has one block/file, plus the directory. Unix keeps getting N files names/block (again ignoring overhead). File system design - like the rest of OS design - is non-trivial, and correct solutions for one application/environment aren't correct - or even usuable - for another application/environment. The Unix OS on an Amiga, implemented roughly like the AmigaDOS file system is implemented (no caching!), would be a total disaster for almost anything. The AmigaDOS file system isn't perfect for the Amiga environment, and some of the Unix ideas would be an improvement (the log-tree allocation table and soft links ('aliases' under AOS, I think) just to start). But I have to agree with Matt Dillon that what the AmigaDOS file system needs most is disk caching. <mike
wagner@utcs.uucp (Michael Wagner) (05/08/86)
Several mentions have been made now of V1.2. Would it be possible to get a good, authoritative list of what did and didn't go into V1.2, including new features and bug fixes? Presumably, now that 1.2 is in beta test, this information is relatively firm, and can be spoken about freely. I think a lot of people would appreciate that sort of information. Oh, and, of course, we'd all like to know when 1.2 would be available to the general public. Michael
bruceb@amiga.UUCP (Bruce Barrett) (05/09/86)
In article <636@baylor.UUCP> peter@baylor.UUCP (Peter da Silva) writes: >> Cheap directories are important on a small-disk machine. And at least this >> method allows for essentially unlimited directory sizes, unlike other DOS >> systems popular on microcomputers today. > >I don't know of any DOS that doesn't allow unlimited directory sizes, [...] Apple-][ DOS (not Prodos), TRS-DOS, CP/M, MS-DOS (setable, but finite) >I do think that giving each icon a seperate file is a mistake, since it makes >folder displays unbearable slow. Why not do what the Integrated Solutions >system does (more or less) and put all the icons in a folder in a single file >in that directory? One reason might be that you could not just use CLI file copies to move your files arround. The copy program(s) would have to keep track of and update (insert, change, delete) the Icon file for every file copy. --Bruce Barrett
brent@orsvax1.UUCP (Brent Chivers) (05/09/86)
> I don't know of any DOS that doesn't allow unlimited directory sizes,
According to the VIC-1541 Single Drive Floppy Disk User's Manual
(the drive used by the Commodore 64 and VIC-20):
Figure 1.1 Specifications
STORAGE Directory Entries 144 per diskette
Tables 5.2 and 5.3 show the directory structure as a linked list, so
I guess the limiting factor (if the manual is correct) must be in the
1541's internal ROM DOS code routines.
(I've never come anywere near the 144-file limit on a 170K disk. :-)
--
Brent Chivers allegra!princeton!orsvax1!brent or perhaps
ORS Automation, Inc seismo!caip!topaz!pyrnj!orsvax1!brent
440 Wall St Phone 609-924-1667
Princeton, NJ 08540 FAX 609-924-2413
USA TELEX 4944924 ORSIN
-------------
Disclaimer: Our business is vision, but my views are my own.
daveh@cbmvax.cbm.UUCP (Dave Haynie) (05/12/86)
In article <636@baylor.UUCP> peter@baylor.UUCP (Peter da Silva) writes: >I don't know of any DOS that doesn't allow unlimited directory sizes... CP/M, MS-DOS, and GEMDOS to start with. -- Dave Haynie {caip,inhp4,allegra,seismo}!cbmvax!daveh "There, beyond the bounds of your weak imagination Lie the noble towers of my city, bright and gold" -Genesis
peter@baylor.UUCP (Peter da Silva) (05/15/86)
> In article <636@baylor.UUCP> peter@baylor.UUCP (Peter da Silva) writes: > >> Cheap directories are important on a small-disk machine. And at least this > >> method allows for essentially unlimited directory sizes, unlike other DOS > >> systems popular on microcomputers today. > > > >I don't know of any DOS that doesn't allow unlimited directory sizes, [...] > Apple-][ DOS (not Prodos), TRS-DOS, CP/M, MS-DOS (setable, but finite) OK, I don't know any serious DOS that allows (not even supports) multitasking that doesn't allow infinite directory sizes. MS-DOS directories, other than the root directory, can grow like any other file to any size you want. The other DOS-es you mention are jokes... (so is MS-DOS, really). The real competitors of AmigaDOS, and what you should be comparing it with, are the likes of UNIX and OS/9. And UNIX directories are just as cheap as yours. As any number of people have mentioned: you have to put the file name *somewhere*. > >I do think that giving each icon a seperate file is a mistake, since it makes > >folder displays unbearable slow. Why not do what the Integrated Solutions > >system does (more or less) and put all the icons in a folder in a single file > >in that directory? > One reason might be that you could not just use CLI file copies > to move your files arround. The copy program(s) would have to keep track > of and update (insert, change, delete) the Icon file for every file copy. They have to keep track of the .info files, don't they? You mean you have to go back & move the .info files as well? And then change them with your .info editor if you changed the file name? Hey... the Amiga is a great machine, and I lust after it. I just think that there are several places in the system where you didn't really look at the wealth of existing solutions to a problem like "how do I find a file" before doing it your own way. Since the O/S interface and implementation seem to be fairly loosely coupled it should be possible to change things like this without breaking existing software. So why not just fix it and have done with it, instead of making excuses? Just putting the filename in the directory should do wonders for the speed of icon display... -- -- Peter da Silva -- UUCP: ...!shell!{baylor,graffiti}!peter; MCI: PDASILVA; CIS: 70216,1076