OSDev.org

Hi!

My operating system doesn't have multi-tasking or dynamic memory allocation by design. By limiting myself I must figure out alternative methods to solve problems. This is just for fun so I don't need to hear what a bad idea it is. Anyway.

One thing I would like to implement is pipes like let's say running ls | cat. Because this is monotasking I can't go about this in the normal way. My idea was to map both programs and the pipe in the same virtual address space so they basically can be viewed as one single program. Then what happens is that ls starts outputing characters to the pipe. When all output is written or the buffer is full it will run some sort of sync() method that starts the program in the recieving end, in this case cat, that starts processing the input from the pipe. When complete cat exits and control is transfered back to ls that will either repeat the same action over again if there is more to write or exit if everything has been written.

What do you think of this approach? The thing I particulary like is that there isn't any kernel interaction once the programs are up and running which saves some overhead from switching back and forth between processes.

You could buffer the output from the first program and then, when it terminates, you dump that buffer into the second program as input.

Yo:

A POSIXly correct implementation dictates that all programs in the pipeline run in parallel and not in sequence.

Each pipe in the sequence is an allocated buffer for output. Your implementation of stdio must support the idea of writing to a pipe, which is essentially a buffer, and it must support reading from a pipe, which is essentially sleeping until a program has written to the same pipe (buffer) it has been attached to for reading. Along with this, don't forget the standard caveats: the program can redirect its stdout, etc.

--All the best
gravaera

gravaera wrote:A POSIXly correct implementation dictates that all programs in the pipeline run in parallel and not in sequence.

So your response basically equates to "You can't do that! POSIX doesn't allow it!" However, nobody said anything about POSIX.

Anyway, I agree with ucosty's solution, it's functionally equivalent. According to bewing, that's how DOS did it. The bigger question though is how to do something like this without dynamic memory allocation, I would think.

There is nothing POSIXy in the concept of a pipe. POSIX pipes are POSIXy, the idea of a channel between two processes/threads/what have you is not.

Behind the scenes you could easily implement a statically sized ring buffer for the transfer of data, killing the first process if it writes too much data. Alternatively, you could use temporary files on disk if you have support for that (which can be done without dynamic allocation too).

The best solution is to implement dynamic memory allocation and use a resizable ring buffer, and then use ucosty's solution . Monotasking simplifies this a lot, but also adds the caveat of not yet having a destination process for the buffer. Nothing that should be too hard to design around though.

The fact that you are not using dynamic mem allocation puts you in a box.
So, alternately, you could have a predetermined temp file on physical media, write the output of program 1 to the tempfile, rewind the tempfile, start program 2, and direct the temp file to the input.

From the DJGPP library sources:

quok wrote:

gravaera wrote:A POSIXly correct implementation dictates that all programs in the pipeline run in parallel and not in sequence.

So your response basically equates to "You can't do that! POSIX doesn't allow it!" However, nobody said anything about POSIX.

Anyway, I agree with ucosty's solution, it's functionally equivalent. According to bewing, that's how DOS did it. The bigger question though is how to do something like this without dynamic memory allocation, I would think.

Or rather, "The expected behaviour of a pipe is X, and the simplest, scalable way to implement it at first glance is Y": rather than simply saying, "you could use a buffer and run each program in sequence", I preferred to correctly explain the pipe, and a technically correct way to implement it: run them all at once and have them all outputting to linked buffers with the reader sleeping on the buffer when there's no data. And functionally equivalent is not the same as behaviourally correct. Whatever the OP's plans are, at least one person giving a good view of how to get it done "the wholesome" way is certainly useful.

And you can't really depreciate my answer by trying to say it's too "hard to do": DOS is a very old OS, and I doubt that modern UNIXes would break the model and run the programs one by one. To achieve the "correct" behaviour scalably, it would be best done with the readers sleeping on the buffers and reading until they get an EOF. That it's a more complex answer doesn't make it less correct, and in fact my answer is, in the end, more complete: I have explained to the OP how the more complex implementation would work; whether or not he decides to use that suggested model is up to him. But trying to shield him from the complex implementation and thinking that "he's probably to dumb to get it, or too lazy to do it" will just make him get a hazy picture of the whole thing rather than the full picture he needs in order to decide how much of that full picture he's willing to implement.

pcmattman wrote:... and use a resizable ring buffer...

Actually it doesn't even need to be a dynamically resizable one: last time I read about the internals of pipes, the article mentioned that Linux uses a fixed buffer size of 32KB. Makes things easier, assuming you can cause the reader to sleep when the ring buffer has been read to the end and the writer still hasn't posted EOF (or quit).

--All the best,
gravaera

It's "jiggle the quotes" time.

gravaera wrote:A POSIXly correct implementation dictates that all programs in the pipeline run in parallel and not in sequence.

quok wrote:However, nobody said anything about POSIX.

gravaera wrote:And you can't really depreciate my answer by trying to say it's too "hard to do": DOS is a very old OS, and I doubt that modern UNIXes would break the model and run the programs one by one.

quok wrote:However, nobody said anything about POSIX.

gravaera wrote:...trying to shield [Jezze] from the complex implementation and thinking that "he's probably to dumb to get it, or too lazy to do it" will just make him get a hazy picture of the whole thing rather than the full picture he needs in order to decide how much of that full picture he's willing to implement.

Jezze wrote:My operating system doesn't have multi-tasking or dynamic memory allocation by design.

Hi:

I'm not sure why this is becoming such a huge tussle, but you really don't need multitasking to set up the sleeping on the buffers. Difference between a multitasking kernel and a single tasking kernel is that the multitasking kernel doesn't use a timer interrupt to pre-empt tasks and give the appearance of multiple tasks running at once via timeslice assignment.

Processes A and B are linked in a pipe. You use a fixed buffer size of 32KB for the pipe that links them. Process A has 64KB of data in all that it will eventually write to the pipe. After the first 32KB of data is written, you sleep process A, then wake process B and wait until it reads all of what's been written to the buffer so far, then you sleep process B, much like I suggested above. Then you wake process A, and have it continue writing, and so on ad infinitum.

This is not in any way a multitasking solution and in fact it solves both problems: writing to a fixed buffer (no dynamic memory allocation) and the lack of multitasking to make it appear as if all the programs are running at once. You start all the processes at once, link them via the pipes, then you alternate between them as needed. No timer IRQ.

Again, I don't see why everyone seems so eager to try to get one up on my answer

--All the best
gravaera

gravaera wrote:This is not in any way a multitasking solution and in fact it solves both problems: writing to a fixed buffer (no dynamic memory allocation) and the lack of multitasking to make it appear as if all the programs are running at once. You start all the processes at once, link them via the pipes, then you alternate between them as needed. No timer IRQ.

So you'd switch between 'tasks' using the buffer write as a trigger? Sounds like an odd form of cooperative multitasking.

Yo:

I'm going to quote the OP, then gracefully exit this ruckus:

The OP wrote: ...My idea was to map both programs and the pipe in the same virtual address space so they basically can be viewed as one single program. Then what happens is that ls starts outputing characters to the pipe. When all output is written or the buffer is full it will run some sort of sync() method that starts the program in the recieving end, in this case cat, that starts processing the input from the pipe. When complete cat exits and control is transfered back to ls that will either repeat the same action over again if there is more to write or exit if everything has been written...

Silly me, sticking to giving complete answers and trying to help solve problems. Apparently keeping egos safe is more important than giving correct answers. I mean, wow.

EDIT: In retrospect, it would appear that it was probably my signature that fueled some of that, although I've had that song quote up there for quite some time. For anyone reading this topic later on, my signature was the following quote:

"Talk nah. Talk nah! You can't talk? You boast and you brag so much, and as I start fi talk you want me hush? Well you talk." -- Prophet Benjamin, "Talk Na"

That may or may not have contributed to the unusual reactions I got here. I haven't posted much (or at all) of late, so people probably wouldn't have seen that signature beforehand in another topic, and may have interpreted it as some form of obstinacy or something. Signature changed.

/me is scratching his head.

I'm not at all sure who has been misunderstanding whom in which way.

I am also not sure how the OP intends to have virtual address spaces with multiple process images in them including control transfer and not having multitasking in some way.

I am absolutely sure I have no idea why there were hurt feelings at the end.

Great feedback everyone!

I agree that ucosty's idea is much more intuitive so I will go with that. I do have the possibility to add pre-allocated tempfiles that I can use as a ring buffer so when thinking about it I pretty much have the solution available to me with only a few lines of code.

Solar yes I didn't think it through. Only way that I could merge programs together in the same virtual memory space would be (i think) to leave them as relocatable object files similar to how kernel modules work which is not at all what I want.

On a side note I actually like the idea of having triggers for certain file events. Linux uses inotify for exactly that. I could, before starting ls, set a trigger that fires an event when my tempfile either becomes full or is closed. The routine handling the event would then starts cat with stdin set to the newly filled tempfile.

@gravaera: Why this disscussion went weird was because I wasn't asking what a pipe was. I already know what it is and how it works. If I hadn't known what a pipe was and asked you about it I would have been very happy about the replies you gave. So you must understand that when you started explaining POSIX pipes no one really understood why since my OS obviously isn't POSIX-compatible because I have decided to NOT USE multi-tasking. It is not because it is too hard. It is because I don't want to use it. Therefor how pipes work in a typically UNIX system is irrelevant. So the critizism you recieved wasn't against you trying to teach me about pipes but rather the fact that you kept talking about something other than what this thread was about. I am also pretty sure your signature have not offended anyone and this only added more confusion to an already confused state.