wkt@rodos2.cs.adfa.oz.au (Warren Toomey) (07/24/90)
I have had some ideas about alleviating the FS's single-threadedness, so
could someone please explain where I've gone wrong.
Assume the FS doesn't block on a read/write to a device task, but just
sends the request to the task, marks the block in the cache as `in transit',
saves the user's request info somewhere [as extra fields in the cache?],
and goes back to the main loop.
Eventually, the FS will receive a reply from a device task, and then it
can reply to the requesting process that has been blocked all the time.
At this point, it can note that the device task is now `waiting for a
request'.
The problem is of course, what should the FS do if it needs to send a request
to a device task that _isn't_ `waiting for a request'? If it does so, it will
block.
One alternative is to store a queue of outgoing read/write requests, and
this queue can even be reordered to improve efficiency at the device level.
However, this queue is probably static. What should be done if the queue
of device requests fills up, and no device tasks have replied yet?
Throwing away user requests is not a good idea.
Can anybody suggest ways around this problem? Or is it just a bad idea?!
Cheers,
Warren Toomey VK2XWT, chocolated.
Deep in the bowels of ADFA Comp Science.
`Shut up Nick - jem'bp@palmetto.cis.ufl.edu (Brian Pane) (07/24/90)
In article <1766@ccadfa.adfa.oz.au> wkt@rodos2.cs.adfa.oz.au (Warren Toomey) writes: >I have had some ideas about alleviating the FS's single-threadedness, so > [...] >One alternative is to store a queue of outgoing read/write requests, and >this queue can even be reordered to improve efficiency at the device level. >However, this queue is probably static. What should be done if the queue >of device requests fills up, and no device tasks have replied yet? >Throwing away user requests is not a good idea. > >Can anybody suggest ways around this problem? How about implementing the file system as two processes: one which accepts requests from user processes (but blocks when there is no room in the queue) and another that sends requests to the device driver (and wakes up the first when the full queue becomes empty)? Or, you might be able to do this with only one process, which accepts messages from anywhere if there is room for more user requests in the queue but only from device drivers if there isn't. -Brian Pane ------------------------------------------------------------------------- Brian Pane University of Florida Department of Computer Science bp@beach.cis.ufl.edu Class of 1991 "If you can keep your expectations |#ifdef OFFENDED_ANYONE tiny, you'll get through life |# include "disclaimer.h" without being so whiny" - Matt Groening |#endif -------------------------------------------------------------------------
graham@sce.carleton.ca (Doug Graham) (07/25/90)
In article <1766@ccadfa.adfa.oz.au> wkt@rodos2.cs.adfa.oz.au (Warren Toomey) writes: > Assume the FS doesn't block on a read/write to a device task, but just > sends the request to the task, marks the block in the cache as `in transit', > saves the user's request info somewhere [as extra fields in the cache?], > and goes back to the main loop. > > Eventually, the FS will receive a reply from a device task, and then it > can reply to the requesting process that has been blocked all the time. > At this point, it can note that the device task is now `waiting for a > request'. The problem with this approach is that FS will generally not simply reply to the user process when the I/O completes. It must resume the call at the place it left off when the I/O was initiated. For example, here is a paraphrased version of "advance". This routine takes a directory inode, and a filename, and looks up the filename in the directory, returning the inode of the file if it is found. I've removed a lot of stuff for brevity. struct inode *advance(struct inode *dir_inode, char *filename) { * inode_number = search_dir(dir_inode, filename); * new_inode = get_inode(inode_number) return (new_inode); } ino_t search_dir(struct inode *dir_inode, char *filename) { foreach logical_block in dir_inode { * physical_block = read_map(logical_block) * block = get_block(physical_block) foreach entry in block if (entry.name == filename) return (entry.inode_number) } return (NOT_FOUND) } The lines marked with asterisks, are places where blocking may occur. There are at least two problems with your approach. Firstly, each of the "*" lines would have to have extra if's wrapped around them to check if the subordinate call returned E_BLOCKED (or whatever). If this was the case, the caller would have to stash any local state (this means local variables, and the program counter, or state variable that can be used later in a switch, or goto, to restore the program counter) in a static data structure, so that it can be resumed later, and then return E_BLOCKED to *it's* caller immediately. This continues until you get back to the main processing loop. The second problem, is resuming the call once the I/O has completed. Somehow, you must descend the same set of procedures down to the point where the blockage occurred, restoring the local state as you go, and then resume the call. There are variations on this theme, but they are all quite messy and/or force you to write your code in a strange way. Using threads is a much more elegant solution, because all the necessary state is preserved automatically on the stack of the thread. > The problem is of course, what should the FS do if it needs to send a request > to a device task that _isn't_ `waiting for a request'? If it does so, it will > block. > > One alternative is to store a queue of outgoing read/write requests, and > this queue can even be reordered to improve efficiency at the device level. > However, this queue is probably static. What should be done if the queue > of device requests fills up, and no device tasks have replied yet? > Throwing away user requests is not a good idea. This finite queue size is really not a problem. Since each user task can have at most one I/O request pending at a time, the size of the queue can be bounded by the maximum number of processes, or NR_PROCS. In fact, the logical place to store the pending request information, is in the "fproc" table, which already has the correct size. A pointer could be added to the fproc structure to allow the threading of pending requests into a linked list. This would allow the next request to be found without searching the entire table. About reordering the queue in FS, to improve the efficiency at the device level: FS is probably not the right place to do this. This is very device specific, and belongs in the device drivers. ---- Doug.
ghelmer@dsuvax.uucp (Guy Helmer) (07/25/90)
In <1766@ccadfa.adfa.oz.au> wkt@rodos2.cs.adfa.oz.au (Warren Toomey) writes: >Assume the FS doesn't block on a read/write to a device task, but just >sends the request to the task, marks the block in the cache as `in transit', >saves the user's request info somewhere [as extra fields in the cache?], >and goes back to the main loop. Sounds like an interesting idea. >Eventually, the FS will receive a reply from a device task, and then it >can reply to the requesting process that has been blocked all the time. >At this point, it can note that the device task is now `waiting for a >request'. I assume there will be some mechanism for a "timeout" if a device doesn't reply. >The problem is of course, what should the FS do if it needs to send a request >to a device task that _isn't_ `waiting for a request'? If it does so, it will >block. A queue of even two entries would make much better use of machine resources than the current FS, especially if processes are generating requests for multiple devices. >One alternative is to store a queue of outgoing read/write requests, and >this queue can even be reordered to improve efficiency at the device level. >However, this queue is probably static. What should be done if the queue >of device requests fills up, and no device tasks have replied yet? >Throwing away user requests is not a good idea. If the queue fills up, make FS block and wait for a device to either respond or timeout. I'll bet the user will notice if it happens frequently, and he/she can tweak the size of the queue. Another option could be to throw away the request and return an error. The user would notice that real fast :-). >Can anybody suggest ways around this problem? Or is it just a bad idea?! > Warren Toomey VK2XWT, chocolated. > Deep in the bowels of ADFA Comp Science. > `Shut up Nick - jem' This shouldn't require too much hacking to implement. Any takers? -- Guy Helmer ...!bigtex!loft386!dsuvax!ghelmer DSU Computing Services dsuvax!ghelmer@cs.utexas.edu, helmer@sdnet.bitnet Small is beautiful, but looks aren't everything...
adrie@philica.ica.philips.nl (Adrie Koolen) (07/25/90)
In article <1766@ccadfa.adfa.oz.au> wkt@rodos2.cs.adfa.oz.au (Warren Toomey) writes: >Assume the FS doesn't block on a read/write to a device task, but just >sends the request to the task, marks the block in the cache as `in transit', >saves the user's request info somewhere [as extra fields in the cache?], >and goes back to the main loop. > >Eventually, the FS will receive a reply from a device task, and then it >can reply to the requesting process that has been blocked all the time. >At this point, it can note that the device task is now `waiting for a >request'. Not messages, the FS sends to tasks, are sent on behalf of user processes. The FS has also to read/write inode and zone bit-maps, the inode table, directories and (double) indirect blocks. It would be nice if the FS would only block on these `administration blocks', and not on real data blocks. But that way, when you issue a copy of many files to floppy, the FS can slow down the system just as easilly. What state should be stored when the FS does a request for an administration block? Where should it be stored? How do you return to an execution thread of the FS? longjmp? A stated FS asks for a lot of rewriting. I think that most people are waiting for someone to post an easy and short solution, which can be patched quickly. I think that those people can wait long. A multi-threaded FS, with one FS code + data segment, but several (say 5) FS process entries in the kernel tables (proc[]), will not be the most beautiful solution but still an effective solution with not that many changes. Adrie Koolen (adrie@ica.philips.nl) Philips Innovation Centre Aachen
ghelmer@dsuvax.uucp (Guy Helmer) (07/26/90)
In <1990Jul25.133131.3289@dsuvax.uucp> ghelmer@dsuvax.uucp (Guy Helmer) writes: >In <1766@ccadfa.adfa.oz.au> wkt@rodos2.cs.adfa.oz.au (Warren Toomey) writes: >> [Non-blocking FS suggestion...] >>One alternative is to store a queue of outgoing read/write requests, and >>this queue can even be reordered to improve efficiency at the device level. >>However, this queue is probably static. What should be done if the queue >>of device requests fills up, and no device tasks have replied yet? >>Throwing away user requests is not a good idea. >If the queue fills up, make FS block and wait for a device to either >respond or timeout. I'll bet the user will notice if it happens frequently, >and he/she can tweak the size of the queue. I thought of something while I was on the road today --- if the queue size is set to NR_PROCS (number of user processes allowed, I believe), every user process in the system could generate I/O requests and FS would never have to block while waiting for an unused queue slot. -- Guy Helmer ...!bigtex!loft386!dsuvax!ghelmer DSU Computing Services dsuvax!ghelmer@cs.utexas.edu, helmer@sdnet.bitnet Small is beautiful, but looks aren't everything...
sccowan@watmsg.uwaterloo.ca (S. Crispin Cowan) (07/26/90)
wkt@rodos2.cs.adfa.oz.au (Warren Toomey) writes: [describes an administator FS task] >Eventually, the FS will receive a reply from a device task, and then it >can reply to the requesting process that has been blocked all the time. >At this point, it can note that the device task is now `waiting for a >request'. >The problem is of course, what should the FS do if it needs to send a request >to a device task that _isn't_ `waiting for a request'? If it does so, it will >block. What you're looking for here is the concept of a 'courier' task. A courier is just a small task that you hand an asynchronous request to, and let the courier block, instead of blocking the file system. Courier tasks can be thought of as user-managed buffers: a task becomes a thread of execution wrapped around a data structure. >Can anybody suggest ways around this problem? Or is it just a bad idea?! Check out the following paper, where Gentleman describes this kind of administrator task. This is a really good paper, and should be considered essential reading for anyone seriously interested in using tasks in this way. @article ( gen81, title = "{Message Passing Between Sequential Processes: the Reply Primitive and the Administrator Concept}", author = "W. Morven Gentleman", journal = "Software --- Practice and Experience", year = 1981, volume = 11, pages = "435-466", ) Crispin ----- (S.) Crispin Cowan, CS grad student, University of Waterloo Work: DC3548, x3934, watmath!watmsg!sccowan, sccowan@watmsg.waterloo.edu Home: 60 Overlea Drive, Kitchener, N2M 1T1, 570-2517 Quote: "You can have peace. Or you can have freedom. Don't ever count on having both at once." --Lazarus Long "You can't separate peace from freedom because no one can be at peace unless he has his freedom." --Malcolm X
hyc@math.lsa.umich.edu (Howard Chu) (07/28/90)
In article <1990Jul25.133131.3289@dsuvax.uucp> ghelmer@dsuvax.uucp (Guy Helmer) writes: %In <1766@ccadfa.adfa.oz.au> wkt@rodos2.cs.adfa.oz.au (Warren Toomey) writes: %>Eventually, the FS will receive a reply from a device task, and then it %>can reply to the requesting process that has been blocked all the time. %>At this point, it can note that the device task is now `waiting for a %>request'. % %I assume there will be some mechanism for a "timeout" if a device doesn't %reply. Don't need anything special here, do you? After all, what would the current FS normally do, besides sit blocked.... -- -- Howard Chu @ University of Michigan one million data bits stored on a chip, one million bits per chip if one of those data bits happens to flip, one million data bits stored on the chip...
peter@ficc.ferranti.com (Peter da Silva) (07/31/90)
In article <884@sce.carleton.ca> graham@sce.carleton.ca (Doug Graham) writes: > This finite queue size is really not a problem. Since each user task > can have at most one I/O request pending at a time, I would advise against designing around this assumption, if you want to support 1003.x later on. 1003.4 certainly requires multiple outstanding requests, and it's handy for networking. -- Peter da Silva. `-_-' +1 713 274 5180. 'U` <peter@ficc.ferranti.com>
inst182@tuvie (Inst.f.Techn.Informatik) (08/02/90)
adrie@philica.ica.philips.nl (Adrie Koolen) writes: >A stated FS asks for a lot of rewriting. I think that most people are >waiting for someone to post an easy and short solution, which can be >patched quickly. I think that those people can wait long. A multi-threaded >FS, with one FS code + data segment, but several (say 5) FS process entries >in the kernel tables (proc[]), will not be the most beautiful solution >but still an effective solution with not that many changes. Good idea, and if you could make all those nasty global variables [You see, I had a look at the (1.3) sources since I made the naive remark that writing a stated FS wouldn't be hard to write] in the FS local, all you would need is an extra stack for each thread (You need this anyway) so that the threads can't disturb each other. All those stacks would have to be in a single 64k segment with the data segment (if you still need global data), but that should not be too much of a problem. Another idea: It should be possible to have just one FS thread sitting around all the time waiting for requests. Each time it receives a request it spawns a thread to handle the request and waits for the next request. If it cannot spawn the thread (Proc table full, out of memory, ...) it should handle the request itself, thus blocking any further requests. What do you think ? | _ | Peter J. Holzer | Think of it | | |_|_) | Technische Universitaet Wien | as evolution | | | | | hp@vmars.tuwien.ac.at | in action! | | __/ | ...!uunet!mcsun!tuvie!vmars!hp | Tony Rand |
graham@sce.carleton.ca (Doug Graham) (08/03/90)
In article <P._4+3@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >> This finite queue size is really not a problem. Since each user task >> can have at most one I/O request pending at a time, > >I would advise against designing around this assumption, if you want to >support 1003.x later on. 1003.4 certainly requires multiple outstanding >requests, and it's handy for networking. Damn! Caught with my pants down. I rushed out and ordered a copy of 1003.4, but probably won't get it for 2 weeks or so. In the meantime, could you summarize in a paragraph or two, how it requires that a process may have multiple outstanding requests. Is this really going to be a problem? It's obvious that a process can only have a single *sychronous* request pending, and I think these are the ones that cause the problems. -- Doug.
peter@ficc.ferranti.com (Peter da Silva) (08/09/90)
In article <887@sce.carleton.ca> graham@sce.carleton.ca (Doug Graham) writes: > Damn! Caught with my pants down. I rushed out and ordered a copy > of 1003.4, but probably won't get it for 2 weeks or so. In the meantime, > could you summarize in a paragraph or two, how it requires that > a process may have multiple outstanding requests. Section 11, asynchronous Input and Output. "The asynchronous I/O mechanism will allow a single process to perform I/O simultaneously to a single file multiple times or to multiple files multiple times". Now you might not want to do real-time in MINIX, but I'm sticking to AmigaOS until Minix provides all the facilities of AmigaOS... including most of what's covered by P1003.4. -- Peter da Silva. `-_-' +1 713 274 5180. 'U` <peter@ficc.ferranti.com>