Note: Reading these lecture notes is not a substitute for watching thelecture. I frequently go off script, and you are responsible for understandingeverything I talk about in lecture unless I specify otherwise.
The fork() syscall
The fork() syscall creates a new copy of the current process. We refer to thecurrent process as the parent process, and the new copy as the childprocess.
You can sort of think of fork() as a fork in the road of assemblyinstructions, where the parent process continues down one path and the childprocess continues down anotherâŚ
Return value of fork: distinguishing between the child and the parent
Keep in mind that fork almost perfectly copies the calling process: allvariables are copied, all file descriptors are copied, and fork() returns tothe exact same place in the program in both processes. How is a programsupposed to know if it is the original/parent process or the clone/child? If wewant one of the processes to do one thing and the other process to do somethingelse, how do we make that happen?
This is accomplished via the return value of fork:
fork()returns 0 to the child process to indicate that it is the child. Ifthe child wants to figure out its own PID, it can callgetpid(), and if thechild wants to figure out the parent processâs PID, it can callgetppid().fork()returns the child processâs PID (a positive number) to the parent.This is the only way the parent can find out the childâs PID; there is noâget child process PIDâ system call, since the parent canfork()any numberof children, and that would make such a syscall complicated. The parent can,of course, get its own PID by callinggetpid().fork()returns -1 on error, just like any other syscall. This usually meansthat there exist too many processes, and the kernel is refusing to createmore.
Dragons ahead đâ ď¸
Beware of programs that make runaway fork() calls. For example, this is oneof the worst programs to run:
int main() { while (true) { fork(); }}This program is known as a forkbomb. It creates a child process; then, boththe parent and the child create child processes (resulting in 4 processestotal); then, all of those processes create child processes (resulting in 8processes total), so on, until your machine runs out of processes, everyprocess is stuck in an infinite while loop, and your computer grinds to ahalt.
This might look like an obviously bad idea, but itâs not hard to accidentallycode slightly less-bad versions of this. You should be careful whenever callingfork() to look at what the child process might do, and ensure it terminatesproperly without accidentally creating more child processes. For example,consider this well-intentioned but buggy code:
1int main() { 2 load some huge string to be processed 3 while (stringHasMoreLines()) { 4 processNextLine(); 5 } 6} 7 8void processNextLine() { 9 if (fork() == 0) {10 Do some parallel processing in the child11 }12 Do some parallel processing in the parent13}This code has an accidental sort of forkbomb: after each child process is donedoing the parallel processing on line 10, it will continue out of the ifstatement, do the parallel processing that only the parent will do, and then,even worse, it will return from processNextLine back to the while loop online 3 and fork a grandchild process. That grandchild process will do thesame, on and on, until every process has gone through every line in the stringbuffer. This can create big problems.
To avoid this, itâs important to place an exit(0) call after line 10 so thatthe child does not continue past that point.
Viewing processes
When multiprocess code does not do what you expect, it is often helpful to tryto get an idea of what the code is doing instead. To view processes runningon your computer, you can run ps aux:
USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMANDroot 1 0.0 0.0 170116 9560 ? Ss May22 9:49 /sbin/initroot 2 0.0 0.0 0 0 ? S May22 0:02 [kthreadd]root 3 0.0 0.0 0 0 ? I< May22 0:00 [rcu_gp]root 4 0.0 0.0 0 0 ? I< May22 0:00 [rcu_par_gp]root 6 0.0 0.0 0 0 ? I< May22 0:00 [kworker/0:0H-kblockd]root 9 0.0 0.0 0 0 ? I< May22 0:00 [mm_percpu_wq]root 10 0.0 0.0 0 0 ? S May22 0:17 [ksoftirqd/0]root 11 0.0 0.0 0 0 ? I May22 46:59 [rcu_sched]<many more entries>If youâre working on a shared computer like myth, it may be helpful to usegrep to filter the output, showing only your processes, and maybe also onlyfiltering for the program you want to inspect:
ps aux | grep yourUsername | grep programFor example, I can start sleep in one terminal, then open another terminalSSHed to the same myth machine (e.g. ssh mythXX.stanford.edu, where XX isthe same number as the first terminal), and list the process info:
đ ps aux | grep rebs | grep sleeprebs 1128862 0.0 0.0 8076 596 pts/6 S+ 22:04 0:00 sleep 100rebs 1128868 0.0 0.0 8900 676 pts/1 S+ 22:04 0:00 grep --color=auto --exclude-dir=.bzr --exclude-dir=CVS --exclude-dir=.git --exclude-dir=.hg --exclude-dir=.svn sleep(Youâll need to ignore the second line; thatâs grep itself that turned up inthe search results.)
ps has a bunch of custom fields you can display if you want more info. For example:
đ ps o pid,ppid,pgid,stat,user,command -p $(pgrep -u $USER sleep) PID PPID PGID STAT USER COMMAND1128862 1128820 1128862 S+ rebs sleepOne thing that can sometimes come in handy is to use pstree to show the treeof parent/child processes:
đ pstree -psa $(pgrep -u $USER sleep)systemd,1 ââsshd,846 ââsshd,1126881 ââsshd,1126930 ââzsh,1128820 ââsleep,1129081 100Scheduling
Consider the following program, which prints a letter, forks, and continues theloop:
You might reasonably guess that the program outputs the following:
abbccccddddddddHowever, the order is not necessarily preserved. I get a different ordering ofthe letters every time, but this is one example output:
abcbdcdcddcddddThis is the effect of the process scheduler at work. The above code creates8 processes, but we may only have 2 CPU cores with which to run thoseprocesses. In order to provide the illusion of running many processessimultaneously, the operating system scheduler does the following:
- A process is allowed to run on a particular CPU core. After some shortinterval â a handful of microseconds â the OS pauses the process, copiesthe contents of registers into a process struct, and adds that datastructure to a queue of running processes, called the ready queue.
- The OS then selects another process from the ready queue, loads the savedregisters back into the CPU, and resumes execution of that process as if ithad never stopped.
- Occasionally, a process needs to wait for something (e.g. it calls
sleep,or it waits for a network request to come in, or it waits for a differentprocess to do something). In this case, the process is removed from the readyqueue and is instead moved to the blocked set. From there, the processisnât considered for scheduling. (Eventually, it is moved from the blockedset back to the ready queue when the thing it was waiting for is ready.) Wewill talk more about these situations in the next few lectures.
Note that the ready queue isnât a simple ordered queue; we may havehigh-priority processes that should get more CPU time. The scheduler employs asophisticated algorithm to balance the needs of various processes, and, as aresult, processes may not run in the order you expect them to. You are nevergiven any guarantees about process scheduling, other than the fact that yourprocess will be scheduled and will be executed eventually.
Viewing process state
ps also displays the state of a process in the STAT(E) column:
Rmeans the process is either on the CPU or is in the ready queue, ready torun.DorSmean the process is in the blocked set, waiting for something tohappen.
In the ps example output from earlier, you might notice that sleep was inthe S state, since it was waiting for a timer to elapse.
Basics of synchronization: the waitpid syscall
The waitpid system call can be used to wait until a particular child processis finished executing. (Itâs actually a more versatile syscall than that, andwe will discuss that in a moment, but letâs keep it simple for now.)
In the following code, a process forks, and then the parent process waits forthe child to exit:
Note: waitpid can only be called on direct child processes (not parentprocesses, or grandchild processes, or anything else).
Synchronization puzzle
What are the possible outputs of this program?
Getting the return code from a process
The number returned from main is the return code or exit status code of aprocess. We can pass a second argument to waitpid to get information aboutthe child processâs execution, including its return code:
int main(int argc, char *argv[]) { pid_t pid = fork(); if (pid == 0) { // Child process sleep(1); printf("CHILD: Child process exiting...\n"); return 0; } // Parent process printf("PARENT: Waiting for child process...\n"); int status; waitpid(pid, &status, 0); if (WIFEXITED(status)) { printf("PARENT: Child process exited with return code %d!\n", WEXITSTATUS(status)); } else { printf("PARENT: Child process terminated abnormally!\n"); } return 0;}We can now modify the return 0; of the child code to return some othernumber, or even to segfault (in which case, WIFEXITED(status) will returnfalse).
Calling waitpid without a specific child PID
You can call waitpid passing -1 instead of a childâs PID, and it will waitfor any child process to finish (and subsequently return the PID of thatprocess). If there are no child processes remaining, waitpid returns -1 andsets the global variable errno to ECHILD (to be specific about the âerrorcondition.â It can return -1 for other reasons, such as passing an invalid 3rdargument.)
This example creates several processes without keeping track of their PIDs,then calls waitpid until the parent has no more child processes that ithasnât already called waitpid on:
This calls waitpid a total of 9 times (it returns child PIDs 8 times, thenreturns -1 to indicate that there are no remaining children).
When -1 is passed as the first argument, waitpid returns children in asomewhat arbitrary order. If several child processes have exited by the timeyou call waitpid, it will choose an arbitrary child from that set. Otherwise,if you call waitpid before any child processes have stopped, it will wait forat least one of the running children to exit.
waitpid and scheduling
To be clear, waitpid does not influence the scheduling of processes.Calling waitpid on a process does not tell the OS, âhey, I am waiting on thisprocess, so please give it higher priority.â It simply blocks the parentprocess until the specified child process has finished executing.
waitpid is not optional!
When a process exits, the kernel does not immediately free all of the memorythat was being used for that process; although many resources can be freed(e.g. the file descriptor table or the virtual memory page table), the processstruct is still kept around so that the parent process can eventually get exitinformation via waitpid. When a process has exited but has not yet beenwaited on by the parent, it is called a zombie process: the process is dead,but it still exists, and still counts towards the maximum number of processesthat can be run. Itâs very important for the parent to call waitpid to âreapâthe zombies.
In this way, fork() is kind of like malloc (it is allocating a process) andwaitpid() is kind of like free (it is freeing a process). Every fork()call should be paired with a waitpid().
Lifecycle of a process
Job control
Processes start, cycle on/off the CPU, and eventually terminate, but they canalso be paused at arbitrary points by job control signals. This is usefulin a variety of circ*mstances: for example, maybe youâre running a long,CPU-intense program, and you want to pause it so you can quickly run some quickCPU-intense program. Or, as another example, Mac OS will send âpauseâ signalsto programs when it starts running out of (physical) memory, prompting you toclose some apps before resuming them. Job control is sometimes even usedprogrammatically to synchronize between processes; for example, Process A willpause itself to wait for Process B to catch up, and then Process B will signalProcess A to continue when itâs ready.
Weâll talk more about signals next week, so donât worry much about the detailsof how this works, but in summary, you can send SIGSTOP to pause a processand SIGCONT to continue the process.
On the command line:
# Pause PID 1234kill -STOP 1234# Resume PID 1234kill -CONT 1234Or, programmatically:
# Pause PID 1234kill(1234, SIGSTOP);# Resume PID 1234kill(1234, SIGCONT);Job control and waitpid
waitpid can also be used to observe when a program changes job controlstates (e.g. stops or continues due to SIGSTOP or SIGCONT). This isaccomplished through the third flags parameter:
- Specifying
WUNTRACEDwill causewaitpidto return information aboutprocesses that have terminated or stopped. (Itâs not a great name in myopinion, but has some historical legacy behind it.) - Specifying
WCONTINUEDwill causewaitpidto return information aboutprocesses that have terminated or continued. - Specifying
WUNTRACED | WCONTINUEDwill cause waitpid to return informationabout any state change: it will return when a process stops, continues, orterminates/exits.
