A Unix shell

What you are building

A shell is the program that reads what you type and starts other programs. Every window with a prompt in it is one. It is not a privileged part of the machine. It has no permission your own programs lack, and underneath the decades of convenience a real one carries, it is a short loop around three requests to the operating system. The part of the operating system that is always in memory, and that owns the disk, the screen and the keyboard, is called the kernel. A request to the kernel is called a system call. This build is that loop, written by you, running real programs on your own machine.

The code is a page or two, and it cannot live in a browser, because a page is not allowed to start programs on your computer. Write it in Python or in C. Both give you these calls under the names used here, and both also offer a ready-made function that runs a whole command for you. That function is built out of the calls below, so reaching for it would leave you with nothing built. If you have never written a program at all, start with Writing an Application and come back.

The teal nodes are working milestones. The three magenta nodes mark places where the current design is insufficient; each names the missing idea and links to the lesson that develops it.

Project milestones

1. Print a prompt, read one line, and print it back.

   A loop: print a prompt, wait for a line, print that line back, go round again, and stop when the line is exit. Nothing is started yet. Press Enter on an empty line and it should prompt again without complaining.

2. Turn one line into a command and its arguments.

   Split the line on spaces. Then check the awkward ones: extra spaces between the words, and spaces at the front. A line of nothing but spaces has to come out as no words at all, rather than as one empty word.

3. You have the words, and nothing runs the program.

   There is no call that means "start this program". What you find instead is a call that throws away the program you are running and loads a different one in its place. Try it. The first command works perfectly and your prompt never comes back, because the shell that was going to print it is not there any more.

   What you need

   Two calls, used as a pair. fork makes a second process that is a copy of the one you are in, and then returns in both of them. The original is told the copy's number and the copy is told zero. That single difference is the only way either of them can tell which it is. exec keeps the process and replaces the program inside it. The copy is the one that calls exec, so the original is still there to print the next prompt.

   step 4fork, and the two answers step 5exec, and the same process
4. One command runs, finishes, and the prompt comes back.

   Type ls and the file names appear, then your prompt. Then type a name that does not exist: you should get one message from one shell. If two prompts start fighting over what you type, the copy carried on being a shell after its exec failed, and the fix is one line.

5. An ampersand, and the prompt comes back before the job does.

   sleep 5 & hands you the prompt at once and finishes five seconds later while you type something else. Print the child's process number when you start it, because you are about to need it.

6. The finished background jobs never go away.

   Run sleep 1 & and wait. A process list still shows a row for it, marked Z or defunct, and every background command you type adds another one. Keep going and you reach the limit on how many processes you are allowed to have. Then nothing will start at all.

   What you need

   A finished child does not vanish. The kernel keeps its row, holding one number: the exit status, the small number a program hands back to say whether it worked. A row like that is called a zombie, and collecting it is called reaping. The call that collects one is wait. A shell needs the form of it that answers "nobody has finished yet" straight away, rather than sleeping until somebody does, because it has to carry on reading your typing.

   step 6Building a shell
7. Nothing is left behind after a hundred jobs.

   Before each prompt, collect whatever has finished and print a line naming the job and its exit status. Start a hundred background jobs, wait, and look at the process list: no leftover rows, and your shell still starts things.

8. You want ls | wc -l and there is nowhere for the output to go.

   You can run ls, and you can run wc, which counts the lines it is given. Nothing you have joins the two. The obvious attempt is to catch what the first one printed and hand it to the second as an argument. That fails twice over. Your shell never sees the output, because it went to the terminal rather than to you. And even if it had, the second program could not start until the first had finished.

   What you need

   A program reads and writes through numbered slots and cannot find out where they lead. Slot 0 is where it reads, slot 1 is where it writes, and one of those numbers is called a file descriptor. A pipe is a pair of them joined by a small buffer inside the kernel: what goes into the write end comes out of the read end, in order. Two rules make the rest work. Opening something always takes the lowest free number and the slots survive exec. So in the gap between fork and exec you rearrange the child's slots. Point that same rearranging at a file instead of a pipe and you have redirection.

   step 7Descriptors, redirection, pipes
9. Two programs joined, both running at once.

   ls | wc -l prints a number that matches the number of files, and both processes are in the table at the same time. Leave one end of the pipe open in the shell by mistake and the right-hand program waits for ever. That is how you find out that closing the ends you are not using was load-bearing.

10. Output into a file, and input out of one.

    ls > out.txt puts the listing in the file and prints nothing. >> adds to the end instead of replacing. wc -l < out.txt reads the file as though you had typed it. The programs are unchanged and none of them was told anything.

11. cat notes.txt | wc -l > count.txt & works.

    One line, two children, one pipe, one file, and a prompt back immediately. Leave the shell open and use it for an hour: that is the build finished. It is the same loop the window you normally type into is running.

Review the shell in four passes

You have something working. Now go round again. Each pass asks a question the last one was allowed to ignore, and none of them makes you start over.

Course links for each pass

Each of those three later passes has a step behind it, in the same course. Take them when you want them and not before.

1. Getting both halves of a pipeline to run at the same time.
   Make it fast

   One processor runs one program at a time, so the overlap is not really overlap. A timer interrupts the processor hundreds of times a second and the scheduler hands it to the next process in its list. A write into a full pipe puts the writer to sleep until the reader takes something out. So a pipeline runs at the speed of its slowest program, and no arrangement of yours can beat that.

   step 11The timer, and taking turns
2. Collecting a child in the middle of your own loop.
   Make it correct

   Finished children get collected by something the kernel can run between any two of your own lines. So your list of jobs is read and changed by two pieces of code that know nothing about each other. When the answer depends on which of them gets there first, that is a race. The fix is a lock: one shared marker only one of them can hold, so only one is ever part way through the list.

   step 12Two processors, one counter
3. A command dying badly, and the shell still being there.
   Make it survive

   Your shell lives through a child that crashes because neither of them can reach into the other's memory. That separation is enforced by a bit inside the processor, not by good manners. In user mode the instructions that touch hardware or another process refuse to run, so everything a program wants done it has to ask the kernel for. The exit status you collect is the only thing that comes back.

   step 1What the kernel does for you

Related projects and courses

Starting other processes and deciding what their input and output are attached to is a shape that turns up all over the machine. A build tool does it. A web server handing work to its workers does it. So does the program that starts everything else when your machine switches on, with these same calls. The build after this one puts the programs on separate machines, where a message can be lost and a machine can stop, and keeps the service answering anyway.

All builds or read Build-a-Unix straight through, which builds this shell inside the page and then goes on to files, memory and how a machine takes turns between programs.