reeder@reed.UUCP (Doug Reeder) (03/11/90)
IMHO, the best way to implement pipes is as follows: start the last
program, and let it run along until it requests a character from the
standard input from the OS. The OS then starts up the next to last program,
and lets it run untill it sends a character to standard output (by making an
OS call) The OS then switches back to the last program. If the next to last
program requests a character from the standard input, the OS switches to the
previous program, and runs it until it gets a character, and so on back
through the chain. The advantage of this system is that you never have to
interrupt a program (an important considerations on IIe's and +'s, which
lack vertical blanking interrpts). The disadavantage is that you have to
make a context shift for every character, unless you have multi-character
reads and writes, which would be an excellent thing to have anyway. You
ought to be able to make syscalls like the ProDOS READ and WRITE and NEWLINE
anyway.
Most often, pipes are used with filter programs, i.e. ones that take
the input and transform it in some way (e.g. break lines longer than 80
characters, format it for a particular kind of printer, pass on only lines
that contain a pattern). Filter programs can be written which run under
present shells, by inserting themselves in the output stream, as in the
following (hypothetical) example:
PRINT CHR$(4);"PR#1"
PRINT CHR$(4);"FORMAT,F3,A9" :REM BASIC.SYSTEM external command
PRINT "Ladies and gentlemen, I stand before you to stand behind you, to tell
you something I know nothing of..."
...
PRINT CHR$(4);"NOFORMAT" :REM BASIC.SYSTEM external command
PRINT CHR$(4);"PR#0"
If your shell suppports I/O redirection in an easy-to-use fashion, you
can manually pipe things:
fold infile >midfile (send output to midfile)
print <midfile (get input from midfile)
--
Doug Reeder USENET: ...!tektronix!reed!reeder
from ARPA: tektronix!reed!reeder@berkeley.EDU BITNET: reeder@reed.BITNET
the Little Mermaid on materialism:
I just don't see how a world that makes such wonderful things ... could be bad!fadden@cory.Berkeley.EDU (Andy McFadden) (03/12/90)
In article <14398@reed.UUCP> reeder@reed.UUCP (Doug Reeder) writes: > > IMHO, the best way to implement pipes is as follows: start the last >program, and let it run along until it requests a character from the >standard input from the OS. The OS then starts up the next to last program, >and lets it run untill it sends a character to standard output (by making an [snip] >lack vertical blanking interrpts). The disadavantage is that you have to >make a context shift for every character, unless you have multi-character >reads and writes, which would be an excellent thing to have anyway. You >ought to be able to make syscalls like the ProDOS READ and WRITE and NEWLINE >anyway. There's an easy way around this, called buffer hysteresis. If a reader outpaces a writer, then a buffer will never get full. If a writer outpaces a reader, then the buffer will always be full. This means that we will be performing needless context switches to processes which can't do anything. An easy thing way to deal with this is to wait until the buffer is full, and then leave the writer sleeping until it is only half full (the reverse condition leaves the reader sleeping from the time the buffer is empty to the time it is half full). The biggest problem is handling situations where a writer sends a few bytes and then stops. The buffer must be periodically flushed because of this. A more insidious problem involves a circular pipe, but that is rather uncommon. >Doug Reeder USENET: ...!tektronix!reed!reeder -- fadden@cory.berkeley.edu (Andy McFadden) ...!ucbvax!cory!fadden
madd@world.std.com (jim frost) (03/13/90)
reeder@reed.UUCP (Doug Reeder) writes: > IMHO, the best way to implement pipes is as follows: start the last >program, and let it run along until it requests a character from the >standard input from the OS. The OS then starts up the next to last program, >and lets it run untill it sends a character to standard output (by making an >OS call) The OS then switches back to the last program. If the next to last >program requests a character from the standard input, the OS switches to the >previous program, and runs it until it gets a character, and so on back >through the chain. The advantage of this system is that you never have to >interrupt a program This is a poorer technique as it degrades immediately into the traditional buffer-output-until-buffer-full-or-done technique, and additionally requires all processes to be active at one time for at least some of the processing. Consider that in a pipe not much is going to be done until there is input from somewhere. Each of the processes along the pipe depends on its supplier for that input, back to the head process of that pipe. Your technique would require backtracking to that head process before meaningful processing could commence, at which time the data would flow back along the pipe in exactly the same manner in which it does in traditional piping schemes. You've gained nothing, since your technique degraded immediately to the traditional. What have you lost? At the start, all processes along the pipe *must* be active before any data goes through it. For a long pipe this will be a lot of resources. In the traditional method, adjusting the buffer size can reduce the number of processes which must be active. In the degenerate case, where the buffer size is infinite, only one process at a time needs to be active. This degenerate case is what's used in MS-DOS and some other single-tasking OS's -- you write all the output to disk then start the next process in the pipe using the disk file as input. Happy hacking, jim frost saber software jimf@saber.com
reeder@reed.UUCP (Doug Reeder) (03/20/90)
In article <1990Mar13.022324.19402@world.std.com> madd@world.std.com (jim frost) writes: _reeder@reed.UUCP (Doug Reeder) writes: __ IMHO, the best way to implement pipes is as follows: _ _This is a poorer technique as it degrades immediately into the _traditional buffer-output-until-buffer-full-or-done technique, and _additionally requires all processes to be active at one time for at _least some of the processing. Apaarantly it was not clear that when the first process outputs to the second, the OS immediately switches to the second process, and when the second sends output, the OS switches to the third, so you only need to go back through the chain untill you get some output. This technique gets information to the end as quickly as possible, where you often have a human waiting around to see what comes out. Also, if a process does not read until end-of-file, the information it doesn't use is never generated. It does require all processes be active, but if you can't have all of them active, you're almost better off running the first all the way through, sending its output to a file, then running the second, and so on. _You've gained nothing, since your technique degraded immediately to _the traditional. On the contrary, you gain something quite important: you never need to interrupt a process, which is quite important on the IIe and other machines which don't have regularly scheduled interrupts. Furthermore, you needn't worry about processes which take a long time to generate their next output, as all final output that could possible be generated already has been, i.e. all the processes after the time-consuming one cannot proceed without the information the time-consuming one is generating. Thus you can write a ProDOS shell that does real pipes, if you can get all the appropriate commands in memory at once. (You'll need relocatable external commands.) Pipes and few programs that run in the background, such as print spoolers and file transfer would provide most of the features, IMHO, that people want from an Apple II Unix. -- Doug Reeder USENET: ...!tektronix!reed!reeder from ARPA: tektronix!reed!reeder@berkeley.EDU BITNET: reeder@reed.BITNET the Little Mermaid on materialism: I just don't see how a world that makes such wonderful things ... could be bad!
toth@tellab5.tellabs.com (Joseph G. Toth Jr.) (03/23/90)
First of all - in order to provide multi-tasking (which is refered to in the articles), the OS/Shell would have to work using interrupts. Most owners of Apples (][, ][+ //e - The //c includes a mouse interface which can generate timing interrupts) don't have clocks or mouse controllers to provide the timing interrupts required to provide multi-tasking. Second - in order to make any gains provided by task switching, all I/O to disk, etc. would require new hardware to allow interrupting I/O control and/or DMA. Since there has been no uniformity to restrictions regarding the use of interrupts in the past (DMA requires use of interrupt lines) almost all current I/O device drivers (hardware and software) would have to be scrapped. References: <6673@hydra.gatech.EDU> <1990Mar5.234421.396@world.std.com> <14461@reed.UUCP> In article <14461@reed.UUCP>, reeder@reed.UUCP (Doug Reeder) writes: > In article <1990Mar13.022324.19402@world.std.com> madd@world.std.com (jim frost) writes: > _reeder@reed.UUCP (Doug Reeder) writes: > __ IMHO, the best way to implement pipes is as follows: > _ > _This is a poorer technique as it degrades immediately into the > _traditional buffer-output-until-buffer-full-or-done technique, and > _additionally requires all processes to be active at one time for at > _least some of the processing. > > Apaarantly it was not clear that when the first process outputs to the > second, the OS immediately switches to the second process, and when the > second sends output, the OS switches to the third, so you only need to go > back through the chain untill you get some output. This technique gets > information to the end as quickly as possible, where you often have a human > waiting around to see what comes out. Also, if a process does not read > until end-of-file, the information it doesn't use is never generated. In the ProDOS environment, and with all currently available hardware, the switching of tasks and the OS/Shell determining which level has output for the next program will not get the output to the user faster... All that overhead in the OS/Shell is simply that; added OVERHEAD. It would actually take longer than the simple method stated next. > It does require all processes be active, but if you can't have all of > them active, you're almost better off running the first all the way through, > sending its output to a file, then running the second, and so on. > _You've gained nothing, since your technique degraded immediately to > _the traditional. > On the contrary, you gain something quite important: you never need to > interrupt a process, which is quite important on the IIe and other machines > which don't have regularly scheduled interrupts. Furthermore, you needn't > worry about processes which take a long time to generate their next output, > as all final output that could possible be generated already has been, i.e. > all the processes after the time-consuming one cannot proceed without the > information the time-consuming one is generating. The point of pipes is to get an output from a sequence of operations.. On a single user system the amount of code executed by the series of programs remains constant. Therefore, any added overhead that is performed in selecting which task executes simply because some output is availabe is simply that: ADDED OVERHEAD. And that overhead will ADD to the time it takes to complete the desired series of operations used to obtain an output, not decrease it. Simply using a RAMdisk for intermediate storage of information would make piping data at least tolerable. > Thus you can write a ProDOS shell that does real pipes, if you can get > all the appropriate commands in memory at once. (You'll need relocatable > external commands.) Pipes and few programs that run in the background, such > as print spoolers and file transfer would provide most of the features, > IMHO, that people want from an Apple II Unix. On this last point; I Agree, whole-heartedly. > -- > Doug Reeder USENET: ...!tektronix!reed!reeder -- ------------------------------------------------+--------------------- Maybe I shouldn't have done it, sarcasm is so | Joseph G. Toth Jr. seldom understood. Don't FLAME on me, please. | uunet!tellab5!toth
gt4662b@prism.gatech.EDU (BRANHAM,JOSEPH FRANKLIN) (03/24/90)
In article <2284@tellab5.tellabs.com>, toth@tellab5.tellabs.com (Joseph G. Toth Jr.) writes: > First of all - in order to provide multi-tasking (which is refered to in > the articles), the OS/Shell would have to work using interrupts. Most > owners of Apples (][, ][+ //e - The //c includes a mouse interface which > can generate timing interrupts) don't have clocks or mouse controllers > to provide the timing interrupts required to provide multi-tasking. > This is probably pretty irrelevant to the discussion at hand, but I recently bought my father a copy of Geos for the Apple //e //+. I didn't look at the documentation overly much, but the program requires the use of interrupts. In fact, for the //e user without a mouse card, a tiny little interrupt handler which plugs into slot 7 is provided. It had about 4 generic LS chips on it and looks like it could be built for about $20 from scratch. -- <------------------------------------------------------------------------------> < FRANK BRANHAM | "I exist; therefore I am." > < Georgia Institute of Technology | -The Patchwork Quilt > < Internet: gt4662b@prism.gatech.edu | by August Derleth >
toddpw@tybalt.caltech.edu (Todd P. Whitesel) (03/24/90)
toth@tellab5.tellabs.com (Joseph G. Toth Jr.) writes: >First of all - in order to provide multi-tasking (which is refered to in > the articles), the OS/Shell would have to work using interrupts. Most > owners of Apples (][, ][+ //e - The //c includes a mouse interface which > can generate timing interrupts) don't have clocks or mouse controllers > to provide the timing interrupts required to provide multi-tasking. 1. Only true pre-emptive multitasking requires interrupts. Cooperative multitasking (a la Multifinder on the Mac) does not use interrupts to decide when to change contexts. It would not be that hard to write a cooperative multitasking system on ANY machine provided the O/S is smart enough to provide the necessary intercommunication (pipes) and to be able to load more than one program at once. 2. Cards which many people have that could be pressed into interrupt service: Mockingboard (two 6522's) and compatibles (AE Phasor, etc.) Apple Cat II modem (30 hz interrupt, also see Serial Cards below) Serial Cards or any card which allows transmit interrupts Note that the serial card needs to be dedicated to interrupt generation. If you have one but aren't using it then you can just leave the serial port connected to nothing and it will transmit characters at 300 baud out into the void while your interrupt driver transmits another character and goes on about its business. (I know, it's a kludge. But it would work if it were really that important. On 6502's it's much easier to use something that does _not_ do a full CPU context switch because the stack and ZP are fixed. With a 65802/65816 your entire CPU state is in the registers, and life is much easier. Except nobody's bothered to write one yet that I know of.) >Second - in order to make any gains provided by task switching, all I/O to > disk, etc. would require new hardware to allow interrupting I/O control > and/or DMA. Since there has been no uniformity to restrictions regarding > the use of interrupts in the past (DMA requires use of interrupt lines) > almost all current I/O device drivers (hardware and software) would have > to be scrapped. To clarify here: what you're trying to get across is that all currently existing drivers were designed without the possibility of multitasking in mind. So what? When a process makes an I/O request it is satisfied even if it effectively halts the system for a second or two. Nobody said anything about full real-time performance here. (Granted it'd be nice.) DMA does not require interrupts -- the driver could and probably does just poll a bit until DMA is finished -- but interrupts do simplify things. They prevent your driver from having to wait for the DMA to finish which is what I believe you were referring to. This could and should be exploited by a multitasking system but as you said the drivers would have to be rewritten -- which I would do anyway. Queuing of I/O requests and all that. (Which might gobble some memory but come on! how many people who'd want these features still have only 128K?) Todd Whitesel toddpw @ tybalt.caltech.edu
toth@tellab5.tellabs.com (Joseph G. Toth Jr.) (03/24/90)
In article <2284@tellab5.tellabs.com>, toth@tellab5.tellabs.com (Joseph G. Toth Jr.) writes: > > > > Apaarantly it was not clear that when the first process outputs to the > > second, the OS immediately switches to the second process, and when the > > second sends output, the OS switches to the third, so you only need to go > > back through the chain untill you get some output. This technique gets > > information to the end as quickly as possible, where you often have a human > > waiting around to see what comes out. Also, if a process does not read > > until end-of-file, the information it doesn't use is never generated. > > In the ProDOS environment, and with all currently available hardware, the > switching of tasks and the OS/Shell determining which level has output > for the next program will not get the output to the user faster... > All that overhead in the OS/Shell is simply that; added OVERHEAD. > It would actually take longer than the simple method stated next. After getting home, I thought about what I wrote here.. While what I stated true in the cases of output dumped to a file; output dumped to a printer would begin sooner than by waiting till all processes before the printer are completer by passing intermediate files as RAMdisk files. I am assuming that the last process that received output from its predecessor initiates the backward search for output by its request for more input. Practicality must still be issues (usable memory, processor speed, managability, implementation effort, and time). The feature would be very nice; but how valuable is it; how much time should be spent in developing the fastest feature vs. how much time does it really save for the user (and, are those savings really meaningful). Most users have slow DMP devices for hardcopy (if they had high speed printer, they would probably also have a more powerful computer), so saving a couple minutes on a 20 minute printing job (a few seconds on a 3 minute print, etc.) would seem to make the effort impractical. I feel that the feature is nice, but, considering the user market and target for implementation; IMHO the simplest solution is best. -- ------------------------------------------------+--------------------- Maybe I shouldn't have done it, sarcasm is so | Joseph G. Toth Jr. seldom understood. Don't FLAME on me, please. | uunet!tellab5!toth
m.tiernan@pro-angmar.UUCP (Michael Tiernan) (03/25/90)
In-Reply-To: message from alphalpha!toddpw@tybalt.caltech.edu
> DMA does not require interrupts ......
Literally no, but yes it does require an interrupt of sorts. The DMA request
is handled (inside the CPU) in the same frame of mind as an interrupt is, when
the CPU sees it, it finishes what it's doing (6502's wait till the end of a
read or a write and 65c02's go in the middle of a write) and relenquishes the
data, address, and control buss to the requester and waits for the DMA line to
return to continue processing.
<< MCT >>
GEnie : M.Tiernan
AppleLinkPE : M Tiernan, BCS Mike, or MichaelT34
Internet : pro-angmar!m.tiernan@alphalpha.com
UUCP : ...!uunet!alphalpha!pro-angmar!m.tiernan
"And the sweating of their souls will not wash the blood from their hands."
- Phil Ochsmadd@world.std.com (jim frost) (03/25/90)
reeder@reed.UUCP (Doug Reeder) writes: > Apaarantly it was not clear that when the first process outputs to the >second, the OS immediately switches to the second process, and when the >second sends output, the OS switches to the third, so you only need to go >back through the chain untill you get some output. Typically this is all the way to the first process. >This technique gets >information to the end as quickly as possible, where you often have a human >waiting around to see what comes out. So make the buffer size smaller and get the same results with "traditional" techniques. > On the contrary, you gain something quite important: you never need to >interrupt a process, which is quite important on the IIe and other machines >which don't have regularly scheduled interrupts. You interrupt processes a LOT, once for every task switch. It's not a preemptive interrupt, so you don't need a timer, but it's an interrupt nonetheless. Nonpreemptive switching is pretty common. >Furthermore, you needn't >worry about processes which take a long time to generate their next output, There ain't no such thing as a free lunch. That program is going to take a long time with your scheme too. jim frost saber software jimf@saber.com
madd@world.std.com (jim frost) (03/25/90)
toth@tellab5.tellabs.com (Joseph G. Toth Jr.) writes: >First of all - in order to provide multi-tasking (which is refered to in > the articles), the OS/Shell would have to work using interrupts. No it wouldn't. Using a timer to reschedule processes is called "preemptive scheduling". When a process explicitly or implicitly gives up control so that a task switch can take place it's called "non-preemptive scheduling". The Mac multifinder uses the latter (it's not the first example of non-preemptive scheduling, but it's a familiar one that works pretty well). Most of the time non-preemptive OS's do task switching during system calls, which are very frequent in most interactive systems (such as the Mac). >Second - in order to make any gains provided by task switching, all I/O to > disk, etc. would require new hardware to allow interrupting I/O control > and/or DMA. No, although it certainly would help if you didn't have to sit around waiting for I/O all the time. Again, look at the Macintosh multifinder. Smarter hardware improves throughput (that's why the IBM 3090 has such fast I/O -- whole computers are used as periferals). All of these things are well covered in most operating systems texts; this stuff has been around for awhile. Also note that with some compiler help you can do protected memory on the 6502 by emulating indirect memory references and non-relative fetch, store, and jump functions. Slow, but possible. Happy hacking, jim frost saber software jimf@saber.com
johnte@microsoft.UUCP (John TERRANOVA) (03/25/90)
In article <1990Mar23.200426.28446@spectre.ccsf.caltech.edu> toddpw@tybalt.caltech.edu (Todd P. Whitesel) writes: >toth@tellab5.tellabs.com (Joseph G. Toth Jr.) writes: > >>First of all - in order to provide multi-tasking (which is refered to in >> the articles), the OS/Shell would have to work using interrupts. Most >> owners of Apples (][, ][+ //e - The //c includes a mouse interface which >> can generate timing interrupts) don't have clocks or mouse controllers >> to provide the timing interrupts required to provide multi-tasking. > >1. Only true pre-emptive multitasking requires interrupts. Cooperative > multitasking (a la Multifinder on the Mac) does not use interrupts to > decide when to change contexts. It would not be that hard to write a > cooperative multitasking system on ANY machine provided the O/S is > smart enough to provide the necessary intercommunication (pipes) and > to be able to load more than one program at once. Let me offer this definition of pre-emptive multitasking: The ability to execute more than one program at a time such that all programs get CPU time and no process(es) can prevent any other process(es) from getting control of the processor. The processes take turns controlling the processor. When the processes start ending, each remaining process gets more CPU time per unit real time. By this definition MultiFinder is not a pre-emptive multitasking system. Also by this definition interrupts are NOT required. All you need is some way for the OS/Shell to be able to decide it is time to task-switch and do the task-switch. A p-code system would be ideal for this. The 'time-slice' that a process has to run before being switched out would be a count of p-code instructions to execute. After the interpreter interprets some number of instructions, it switches tasks. This p-code system can also provide memory protection. If processes are allocated memory on a page basis then any memory access (read/ write and code or data) can be checked by the interpreter against a page table for validity. Another virtue of this hypothetical p-code system would be page- swapping. Since the code needs to be relocatable start it at memory location $0000. Which would be virtual page $00, byte $00. Using a page table, look up the physical page number for virtual page $00. If the physical page number is invalid, then load those 256 bytes from disk. I'll even give some code for the main loop of the interpreter (this code is not meant to be final code, but rather an idea of what the real code may look like): topOfLoop: lda timeLeft ;some zero-page location bne 1 ;keep going if time not expired jmp NextJob ;task-switch and jmp back to topOfLoop @1 dea sta timeLeft ldy vpage ;get virtual page number lda (currPageTable),y ; get phys page num from page table bne 2 jsr LoadPage ;page not in mem, so go get it @2 sta pc+1 ;store page number part of pc lda (pc) ;load the opcode inc pc ;bump up pc (using the vpage, not phys page) bne 3 inc vpage @3 asl tax jmp (jmpTable),x ;proc must end with jmp topOfLoop The last three instructions group the opcodes into 128 pairs. The pairs differ only in the high bit. The asl allows us to index into a jump table of words (2 bytes) rather than bytes. It is up to the code jmp'ed to to discern between the two opcodes by checking the carry flag. I have found that for simplicity, generation of the pcode may want to ensure that an entire instruction (1 byte opcode, >= 0 args) is on the same page so that checking for page faults during execution of instructions is not necessary - the eternal time-space trade off. So. Waddaya think? Is this pcode-multitasking-virtual memory system feasible? I think the key is a good pcode language. Anybody wanna write it? -----------------------+----------------------------+------------------------- John Terranova | What the Hell do I know? | I speak/type for me johnte@microsoft.uucp | I come from Waunakee! | and no one else. -----------------------+----------------------------+------------------------- "You look so good; you feel good, too. When they see you shake it, baby everybody's gonna pay attention to you and you and you." --Gerard, Shake It