Path: utzoo!dciem!nrcaer!sce!graham
From: graham@sce.carleton.ca (Doug Graham)
Newsgroups: comp.os.minix
Subject: Re: An FS idea - good or bad?
Message-ID: <884@sce.carleton.ca>
Date: 25 Jul 90 07:18:57 GMT
References: <1766@ccadfa.adfa.oz.au>
Organization: Carleton Univerity, Ottawa, Canada
Lines: 78

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.