Computer Systems
`
`A PROGRAMMER'S
`PERSPECTIVE
`
`r v y "
`/
`
`L
`
`/ II
`
`fcj-Sa
`
`|
`
`jaBi
`i
`
`I—r^LJL
`
`/
`
`K Ms
`s
`
`A
`
`si»c
`
`&
`
`Google - Exhibit 1023, cover
`
`

`
`I I i
`
`1
`
`I
`
`1i
`i
`
`ii11m■
`
`1
`
`1
`1
`
`1
`
`11I■
`
`| 1
`
`wm
`
`Library of Congress Catalogjng-in-Publication Data
`Bryant, Randal E.,
`Computer Systems / Randal E. Bryant and David R. O’Hallaron
`p, cm.
`Includes bibliographical references and index.
`ISBN 0-13-034074-X
`I. 0‘Hallaron, David R.
`1. Computer Systems.
`TA177.4.S85 2003
`658,15~dc2t
`
`2001038726
`
`Vice President and Editorial Director, ECS: Marcia Horton
`Acquisitions Editor: Eric Frank
`Editorial Assistant: Delores J. Mars
`_
`Vice President and Director of Production and Manufacturing, ESM: David VK Riccardi
`Executive Managing Editor: Vince O’Brien
`Managing Editor: David A. George
`Production Editor: Rose Kernan
`Director of Creative Services: Paul Belfanti
`Creative Director: Carole Anson
`Art Director/Cover Designer: Jon Boylan
`Art Editor: Xiaohong Zhu
`Manufacturing Manager: Trudy Pisciotti
`Manufacturing Buyer: Lisa McDowell
`Marketing Manager: Holly Stark
`
`'
`
`Pratt ico
`Hall
`
`© 2003 by Randal E. Bryant and David R. O’Hallaron
`Pearson Education, Inc.
`Upper Saddle River, New Jersey 07458
`
`All rights reserved. No part of this book may be reproduced, in any format or by any means, without permission in
`writing from the publisher.
`
`The author and publisher of this book have used their best efforts in preparing this book. These efforts include the
`development, research, and testing of the theories and programs to determine their effectiveness. The author and
`publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation
`contained in this book. The author and publisher shall not be liable in any event for incidental or consequential
`damages in connection with, or arising out of, the furnishing, performance, or use of these programs.
`
`Printed in the United States of America
`10 98765432
`ISBN 0-13-D3M07M-X
`Pearson Education Ltd., London .
`Pearson Education Australia Pty. Limited, Sydney
`Pearson Education Singapore, Pte, Ltd.
`Pearson Education North Asia Ltd., Hong Kong
`Pearson Education Canada, Inc., Toronto
`Pearson Education de Mexico, S.A. de C.V.
`Pearson Education—Japan, Tokyo
`Pearson Education Malaysia, Pte. Ltd.
`Pearson Education, Inc., Upper Saddle River, New Jersey
`
`Google - Exhibit 1023, page i
`
`

`
`594 Chapter 8 Exceptional Control Flow
`
`Ill
`
`8.2 Processes
`Exceptions provide the basic building blocks that allow the operating system
`provide the notion of a process, one of themost profound and successful ideas
`computer science.
`When we run a program on a modern system, we are presented with fha
`illusion that our program is the only one currently running in the system. Or
`program appears to have exclusive use of both the processor and the memog
`The processor appears to execute the instructions in our program, one after Hi
`other, without interruption. Finally, the code and data of our program appear*
`be the only objects in the system’s memory. These illusions are provided to us l|
`the notion of a process.
`The classic definition of a process is an instance of a program in execution
`Each program in the. system runs in the context of some process. The conter
`consists of the state that the program needs to run correctly. This state includf
`i(si
`the program’s code and data stored in memory, its stack, the contents of its gcr.eni
`purpose registers, its program counter, environment variables, and the set of ops;
`file descriptors.
`Each time a user runs a program by typing the name of an executable objec
`file to the shell, the shell creates a new process and then runs the executabli: obis;
`file in the context of this new process. Application programs can also create net
`processes and run either their own code or other applications in the context of ±>
`■
`new process.
`A detailed discussion of how operating systems implement processes L
`ESI
`yond our scope. Instead, we will focus on the key abstractions that a prooal
`provides to the application:
`
`• An independent logical control flow that provides the illusion that our p^|
`gram has exclusive use of the processor.
`• A private address space that provides the illusion that our program zz
`exclusive use of the memory system.
`Let’s look more closely at these abstractions.
`
`8.2.1 Logical Control Flow
`A process provides each program with the illusion that it has exclusive use oi dt
`processor, even though many other programs are typically running on the s>>:=3
`If we were to use a debugger to single step the execution of our program, we w mi
`observe a series of program counter (PC) values that corresponded exclus..
`instructions contained in our program’s executable object file or in shared objer
`linked into our program dynamically at run time. This sequence of PC v.iJu j*
`known as a logical control flow.
`Consider a system that runs three processes, as shown in Figure 8.10. if
`single physical control flow of the processor is partitioned into three logical j:~. .
`one for each process. Each vertical line represents a portion of the logical •in *.
`a process. In the example, process A runs for a while,'followed by B, whicii r_r
`||
`
`"gjre 8.10
`Logical control flc
`Accesses provide <
`;-o.-|rarn with the
`sfjat it has exclusiv
`[of the processor. I
`Jwtical bar repress
`cc.'i.ion of the logi
`Ecrntrol flow for a
`
`completion. (
`r.i’aliy, C is able
`The key poi
`Each process e>
`feaspended) whi
`jjsontext of one o
`The only evidei
`feapsed time of
`rrpears to perk
`•:cr program. I
`Execution of oi
`.xcmiory locatic
`In general,
`Art the logical
`zi any other p:
`mterproces
`memory, and s<
`Any proce
`. acurrent p
`example, in Fi|
`xe other hand
`?■ tnecutes befor
`| The notioi
`it
`Each
`Tvcs- slice. Thu
`
`Privati
`
`ijjrocess als<
`. tie system
`me is the s<
`a± p;ogram
`■t a byte of
`sacral be re;
`l Although
`Lee is diffei
`
`Google - Exhibit 1023, page 594
`
`

`
`Figure 8.10
`Logical control flows,
`Piocesses provide each
`program with the illusion
`p. that it has exclusive use
`of the processor. Each
`|,v vertical bar represents a
`portion of the logical
`control flow for a process.
`
`Time
`
`Process A
`
`Process B Process C
`
`Section 8.2 Processes 595
`
`[:::::
`
`to completion. C then runs for awhile, followed by A, which runs to completion,
`j Finally, C is able to run to completion.
`The key point in Figure 8.10 is that processes take turns using the processor.
`Finch process executes a portion of its flow and then is preempted (temporarily
`suspended) while other processes take their tupns. To a program running in the
`context of one of these processes, it appears to have exclusive use of the Drocessor,
`Tne only evidence to the contrary is that if we were to precisely measure the
`elapsed time of each instruction (see Chapter 9), we would notice that the CPU
`appears to periodically stall between the execution of some of the instructions in
`our program. However, each time the processor stalls, it subsequently resumes
`execution of our program without any change to the contents of the program’s
`memory locations or registers.
`In general, each logical flow is independent of any other flow in the sense
`that the logical flows associated with different processes do not affect the states
`of any other processes. The only exception to this rule occurs when processes
`use interprocess communication (IPC) mechanisms such as pipes, sockets, shared
`| memory, and semaphores to explicitly interact with each other.
`Any process whose logical flow overlaps in time with another flow is called
`a concurrent process, and the two processes are said to run concurrently. For
`^example, in Figure 8.10, processes A and B run concurrently, as do A and C. On
`■ the other hand, B and C do not run concurrently because the last instruction of B
`executes before the first instruction of C.
`, '
`, The notion of processes taking turns with other processes is known as mulii-
`zzsking. Each time period that a process executes a portion of its flow is called a
`dmc slice. Thus, multitasking is also referred to as time slicing.
`
`;
`
`$.2.2 Private Address Space
`
`A process also provides each program with the illusion that it has exclusive use
`of the system’s address space. On a machine with n -bit addresses, the address
`ispace is the set of 2" possible addresses, 0, 1, ..., 2" - 1. A process provides
`|saeh program with its own private address space. This space is private in the sense
`that a byte of memory associated with a particular address in the space cannot in
`general be read or written by any other process.
`§T Although the contents of the memory associated with each private address
`space is different in general, each such space has the same general organization.
`
`Google - Exhibit 1023, page 595
`
`V
`
`|||I
`
`I
`
`il§|
`
`■ ■
`
`mmm
`::
`WM
`
`Xf.
`
`i -
`
`■ri
`US
`
`

`
`t
`
`Pi:!!
`i:
`IfIS­
`IS
`Is
`*
`
`596 Chapter 8 Exceptional Control Flow
`
`Figure 8.11
`. Process address space.
`
`oxffffffff
`Kernel Virtual memory
`-(code, data, heap, stack).. .
`
`QxcOOQOOOO
`
`User stack
`(created at run time)
`
`t
`
`Memory
`invisible to
`user code
`
`%esp (stack pointer)
`
`0x40000000
`
`* _____
`: Memory-mapped region for .
`.........shared libraries '
`t
`. Run-time heap
`'.(created by toaiioc)
`; Read/write segment
`• (.a&ta,.bse)
`Read-only segment
`( <rit, .Cex*', /jksS*!-")!
`0x08048000
`i ^
`«
`o
`
`brk
`
`„ Loaded from the
`” executable file
`
`For example, Figure 8.11 shows the organization of the address space for a Linux
`process. The bottom three-fourths of the address space is reserved for the user
`program, with the usual text, data, heap, and stack segments. The top quarter
`of the address space is reserved for the kernel. This portion of the address space
`contains the code, data, and stack that the kernel uses when it executes instructions
`on behalf of the process (e.g., when the application program executes a system
`call).
`
`8.23 User and Kernel'Modes
`In order for the operating system kernel to provide an airtight process abstraction,
`the processor must provide a mechanism that restricts the instructions that an
`application can execute, as well as the portions of the address space that it can
`access.
`Processors typically provide this capability with a mode bit in some control
`register that characterizes the privileges that the process currently enjoys. When
`the mode bit is set, the process is running in kernel mode (sometimes called su­
`pervisor mode). A process running in kernel mode can execute any instruction in
`the instruction set and access any memory location in the system.
`When the mode bit is not set, the process is running in user mode. A process |
`in user mode is not allowed to execute privileged instructions that do things such
`as halt the processor, change the mode bit, or initiate an I/O operation. Nor is it
`allowed to directly reference code or data in the kernel area of the address space.
`Any such attempt results in a fatal protection fault. User programs must instead
`access kernel code and data indirectly via the system call interface.
`
`m
`
`m
`
`A
`the prc
`an inte
`control
`user m
`the ap{
`user nr
`Lit
`that all
`The /p
`hierarc
`use the
`type (/
`(/proc
`
`8.2.4
`The op
`of exce
`anism i:
`Section
`Th<
`that thf
`of objei
`prograr
`data str
`table th
`contain
`At
`preemp
`decisior
`schedul
`has scht
`it preen
`a mechi
`process,
`(3) pass
`A c
`behalf o
`occur, tl
`process,
`opt to pi
`data to <*
`an expli>
`call does
`return o
`
`Google - Exhibit 1023, page 596
`
`

`
`Section 8.2 Processes 597
`
`A process running application code is initially in user mode. The only way for
`the process to change from user mode to kernel mode is via an exception such as
`an interrupt, a fault, or a trapping system call. When the exception occurs, and
`control passes to the exception handler, the processor changes the mode from
`user mode to kernel mode. The handler runs in kernel mode. When it returns to
`the application code, the processor changes the mode from kernel mode back to
`user mode.
`Linux and Solaris provide a clever mechanism, called the /proc filesystem,
`that allows user mode processes to access the contents of kernel data structures.
`Tire /proc filesystem exports the contents of many kernel data structures as a
`hierarchy of ASCII files that can read by user programs. For example, you can
`use the Linux /proc filesystem to find out general system attributes such as CPU
`type (/proc/epuinfo), or the memory segments used by a particular process
`(/proc/<process id>/maps).
`Z.
`
`wm
`
`8.2.4 Context Switches
`The operating system kernel implements multitasking using a higher level form
`of exceptional control flow known as a context switch. The context switch mech­
`anism is built on top of the lower level exception mechanism that we discussed in
`Section 8.1.
`.
`The kernel maintains a context for each process. The context is the state
`that the kernel needs to restart a preempted process. It consists of the values
`of objects such as the general purpose registers, the floating-point registers, the
`program counter, user’s stack, status registers, kernel’s stack, and various kernel
`data structures such as a page table that characterizes the address space, a process
`fable that contains information about the current process, and a file table that
`contains information about the files that the process has opened.
`At certain points during the execution of a process, the kernel can decide to
`preempt the current process and restart a previously preempted process. This
`decision is known as scheduling and is handled by code in thb kernel called the
`scheduler. When the kernel selects a new process to run, we say that the kernel
`has scheduled that process. After the kernel has scheduled a new process to run,
`it preempts the current process and transfers control to the new process using
`a mechanism called a context switch that (1) saves the context of the current
`process, (2) restores the saved context of some previously preempted process, and
`(3) passes control to this newly restored process.
`A context switch can occur while the kernel is executing a system call on
`behalf of the user. If the system call blocks because it is waiting for some event to
`occur, then the kernel can put the current process to sleep and switch to another
`process. For example, if a read system call requires a disk access, the kernel can
`opt to perform a context switch and run another process instead of waiting for the
`data to arrive from the disk. Another example is the sleep system call, which is
`an explicit request to put the calling process to sleep. In general, even if a system
`call does not block, the kernel can deride to perform a context switch rather than
`return control to the calling process.
`
`i Linux
`he user
`quarter
`;s space
`-uctions
`system
`
`raction,
`that an
`at it can
`
`control
`s. When
`ailed in­
`action in
`
`. process
`ngs such
`Nor is i!
`:ss space,
`t instead
`
`Google - Exhibit 1023, page 597
`
`

`
`83 Sy:
`
`Unixsysti
`they want
`new proc
`syscall
`Cprc
`described
`sirable to
`conveniei
`per fund
`system cs
`program,
`and their
`Whei
`-1 and s-
`grammer
`checking
`here is h<
`
`1 if (
`
`>
`
`2 34
`
`
`
`The str
`with a pa
`the folio'
`
`i voic
`2 {
`
`34 5
`
` }
`
`Given th
`
`if
`
`i2 W
`
`e can :
`given ba
`ments, b
`function
`here is tl
`
`598 Chapter 8 Exceptional Control Flow
`
`Time
`
`read
`
`Disk interrupt
`Return
`from read
`
`Process A ! Process B
`
`i
`
`1
`
`! <f
`
`User code
`} Context
`Kernel code
`„„ , ysercode^
`______ _Kernel code }
`User code
`
`Context
`switch
`
`switch
`
`Figure 8.12 Anatomy of a process context switch.
`
`A context switch can also occur as a result of an interrupt. For example, all
`systems have some mechanism for generating periodic timer interrupts, typically
`every 1 ms or 10 ms. Each time a timer interrupt occurs, the kernel can decide
`that the current process has run long enough and switch to a new process.
`Figure 8.12 shows an example of context switching between a pair of processes
`A and B. In this example, initially process A is running in user mode until it traps
`to the kernel by executing a read system call. The trap handler in the kernel
`requests a DMA transfer from the disk controller and arranges for the disk to
`interrupt the processor after the disk controller has finished transferring the data
`from disk to memory.
`The disk will take a relatively long time to fetch the data (on the order of
`tens of milliseconds), so instead of waiting and doing nothing in the interim, the
`kernel performs a context switch from process A to B. Note that before the switch,
`the kernel is executing instructions in user mode on behalf of process A. During
`the first part of the switch, the kernel is executing instructions in kernel mode on
`behalf of process A. Then at some point it begins executing instructions (still in
`kernel mode) on behalf of process B. And after the switch, the kernel is executing
`instructions in user mode on Behalf of process B.
`Process B then runs for a while in user mode until the disk sends an interrupt
`to signal that data has been transferred from disk to memory. The kernel decides
`that process B has run long enough and performs a context switch from process
`B to A, returning control in process A to the instruction immediately following
`the read system call. Process A continues to run until the next exception occurs,
`and so on.
`
`Aside: Cache pollution and exceptional control flow.
`In general, hardware cache memories do not interact well with exceptional control flows such as interrupts
`and context switches. If the current process is interrupted briefly by an interrupt, then the cache is cold
`for the interrupt handier. If the handler accesses enough items from main memory/ then the cache will
`also be cold for the interrupted process when it resumes. In this case we say that the handler has pM/nfed
`the cache. A similar phenomenon occurs with context switches. When a process resumes after a context
`switch, The cache is cold for the application program and must be warmed up again.
`
`Google - Exhibit 1023, page 598
`
`

`
`'mk
`gi
`
`H
`■
`*
`1
`■
`
`n
`
`» Stopped
`uled. A}
`TIN, or i
`CONT si
`of softwt
`„ Terminer.
`Bated fo:
`to termii
`the exi'
`
`#include <
`
`void exit!
`
`Theexil
`other way to;
`A parem
`function.
`
`600 Chapter 8 Exceptional Control Flow
`
`1 pid_t Fork(void)
`2
`{
`pid_t pid;
`3
`4
`if ((pid = fork!5} < 0)
`unix_error("Fork error");
`return pid;
`
`56
`
`7
`8 }
`Given this wrapper, our call to fork shrinks to a single compact line;
`1 pid = Fork{);
`We will use error-handling wrappers throughout the remainder of this book. They
`allow us to keep our code examples concise, without giving you the mistaken
`impression that it is permissible to ignore error checking. Note that when we
`discuss system-level Timctions in the text, we will always refer to them by their
`lowercase base names, rather than by their uppercase wrapper names.
`See Appendix B for a discussion of Unix error handling and the error-handling
`wrappers used throughout this book. The wrappers are defined in a file called
`csapp. c, and their prototypes are defined in a header file called csapp. h. For
`your reference, Appendix B provides the sources for these files.
`
`Wm
`
`Returns; PID of either the caller or the parent
`The getpid and getppid routines return an integer value of type pid_t,
`which on Linux systems is defined in types. h as an int.
`8.4.2 Creating and Terminating Processes
`From a programmer’s perspective, we can think of a process as being in one of |
`three states:
`.
`® Running. The process is either executing on the CPU, or is waiting to be
`executed and will eventually be scheduled.
`
`Google - Exhibit 1023, page 600
`
`#include
`^include
`
`pid_t for
`
`)
`
`.
`fa
`■fy."
`
`’■
`8.4 Process Control
`Unix provides a number of system calls for manipulating processes from C pro- jH
`grams. This section describes the important functions and gives examples of how ||
`they are used.
`'
`The nets
`‘
`•ip. The child g<
`8.4.1 Obtaining Process ID's
`address spa-
`Wm
`Each process has a unique positive (nonzero) process ID (PID). The getpid
`mm The child a:
`function returns the PID of the calling process. Hie getppid function returns
`which mear
`the PID of its parent (i.e., the process that created the calling process).
`when it call
`newly creat
`The fc
`once but ^
`newly creai
`the child, f
`the return
`executing i
`Figure
`create a ch
`both the p;
`Similarly, t
`When
`unix> . /
`parent;
`child ;
`
`#include <unistd.h>
`#include <sys/types.h>
`
`pid_t getpid(void);
`pid_t getppid(void);
`
`

`
`Section 8.4 Process Control 601
`
`• Stopped. The execution of the process is suspended and will not be sched­
`uled. A process stops as a result of receiving a SIGSTOP, SIGTSTP, SIGT-
`TIN, or SIGTTOU signal, and it remains stopped until it receives a SIG-
`CONT signal, at which point is becomes running again. (A signal is a form
`of software interrupt that is described in detail in Section 8.5.)
`• Terminated. The process is stopped permanently. A process becomes termi­
`nated for one of three reasons: (1) receiving a signal whose default action is
`to terminate the process; (2) returning from the main routine; or (3) calling
`the exit function.
`
`#include <stdlib.h>
`void exit(int status);
`
`This function does not return
`;
`' ' «
`The exit function terminates the process withffiexitstatus of status. (The
`5
`j. other way to set the exit status is to return an integer value from the main routine.)
`A parent process creates a new running child process by calling the fork
`function.
`
`S
`
`^include <unistd.h>
`^include <sys/types.h>
`pid__t fork (void) ;
`
`Returns; 0 to child, PID of child to parent, -1 on error
`
`:
`
`The newly created child process is almost, but not quite, identical to the parent.
`The child gets an identical (but separate) copy of the parent’s user-level virtual
`address space, including the text, data, and bss segments, heap, and user stack.
`The child also gets identical copies of any of the parent’s open file descriptors,
`which means the child can read and write any files that were open in the parent
`when it called fork. The most significant difference between.the parent and the
`newly created child is that they have different PIDs. . v!
`The fork function is interesting (and often confusing) because it is called
`once but it returns twice: once in the calling process (the parent), and once in the
`newly created child process. In the parent, fork returns the PID of the child. In
`' the child, fork returns a value of 0. Since the PID of the child is always nonzero,
`the return value provides an unambiguous way to tell whether the program is
`executing in the parent or the child.
`Figure 8.13 shows a simple example of a parent process that uses fork to
`create a child process. When the fork call returns in line 8, x has a value of 1 in
`both the parent and child. The child increments and prints its copy of x in line 10.
`Similarly, the parent decrements and.-prints its copy of x in line 15.
`When we run the program on our Unix system, we get the following result:
`unix> ./fork
`parent; x=0
`child : x=2
`
`:. They
`.staken
`xen we
`«y their
`
`mdling
`; called
`,h. For
`
`C pro­
`of how
`
`retpid
`returns
`
`a parent
`
`pid-t,
`
`\ one of
`
`3g to be
`
`Google - Exhibit 1023, page 601
`
`

`
`no
`ha
`pr
`. Sh
`an
`all
`is i
`ou
`
`i
`
`When yt
`the proc
`executes
`the exec
`n
`For
`'t; generate
`|/- creates a
`f ■ these cal
`Now
`| ■ from Fig
`.md chil<
`tour proi
`§' lines.
`Con
`three tin
`isre S.14(
`program
`
`l Practii
` Considi
`
`I■
`
`X #ir
`! 2
`3
`4
`i 5
`J
`
`int
`{
`
`67
`
`89
`
`j 10
`H }
`
`602 Chapter 8 Exceptional Control Flow
`
`#include "csapp'.h”
`
`code/ecf/fork.c
`
`1
`2
`3
`4
`5
`6
`7
`
`89
`
`int main{)
`{
`pxd_t pid;
`int x = 1;
`pid = Fork{);
`/* child V
`if (pid == 0) {
`printf (“child : x=%d\n“, ++x) ;
`exit (0)
`
`}
`
`/* parent''*/
`printf(“parent: x=%d\n", —x);
`'exit(0);
`
`10
`ii
`12
`13
`14
`15
`16
`17 }
`
`Figure 8.13 Using fork to create a new process.
`
`There are some subtle aspects to this simple example:
`
`code/ecf/fork c
`
`*
`
`i§S
`
`* Call once, return twice. The fork function is called once by the parent, but
`it returns twice—once to the parent and once to the newly created child. J
`This is fairly straightforward for programs that create a single child. Bui
`programs with multiple instances of fork can be confusing and need to
`reasoned about carefully.
`• Concurrent execution. The parent and the child are separate processes that J
`run concurrently. The instructions in their logical control flows can be inter- J
`leaved by the kernel in’ an arbitrary way. When we run the program on our ,.|
`system, the parent process completes its print f statement first, followed by
`the child. However, on another system the reverse might be true. In generi
`as programmers we can never make assumptions about the interleaving i
`the instructions in different processes.
`» Duplicate but separate address spaces. If we could halt both the parent <'".d
`the child immediately after the fork function returned in each process, v ■
`would see that the address space of each process is identical. Each process
`has the same user stack, the same local variable values, the same heap, ■
`same global variable values, and the same code. Thus, in our example pro­
`gram, local variable x has a value of 1 in both the parent and the child wli„u
`the fork function returns in line 8. However, since the parent and the cluld I
`are separate processes, they each have their own private address spaces. \
`subsequent changes that a parent or child makes to x are private and iuc
`
`I
`
`Google - Exhibit 1023, page 602
`
`

`
`Section 8.4 Process Control 603
`
`not reflected in the memory of the other process. This is why the variable x
`has different values in the parent and child when they call their respective
`printf statements.
`• Shared files. When we run the example program, we notice that both parent
`and child print their output on the screen. The reason is that the child inherits
`all of the parent’s open files. When the parent calls fork, the stdout file
`is open and directed to the screen. The child inherits this file and thus its
`output is also directed to the screen.
`
`When you are first learning about the fork function, it is often helpful to sketch
`the process graph, where each horizontal arrow corresponds to a process that
`executes instructions from left to right, and each vertical arrow corresponds to
`the execution of a fork function.
`For example, how many lines of output would the program in Figure 8.14(a)
`generate? Figure 8.14(b) shows the corresponding process graph. The parent
`creates a child when it executes the first (and only) fork in the program. Each of
`these calls printf once, so the program prints two output lines.
`Now what if we were to call f ork twice, as shown in Figure 8.14(c)? As we see
`from Figure 8.14(d), the parent calls fork to create a child, and then the parent
`and child each call fork, which results in two more processes. Thus, there
`are
`four processes, each of which calls printf, so the program generates four output
`lines.
`Continuing this line of thought, what would happen if we were to call fork
`three times, as in Figure 8.14(e)? As we see from the process graph in Fig-
`ure
`8.14(f), there are a total of eight processes. Each process calls printf, so the
`program produces eight output lines.
`-
`
`Practice Prohlpm 8.1
`Consider the following program:
`
`code/ecf/forkprobO.c
`
`#incluae "csapp.h"
`int main <)
`{
`int x = 1;
`if (Forkf) == 0)
`printf("printf1: x=%d\n", ++x);
`printf("print£2: x=%d\n", — x);
`exi t (0) ;
`'
`
`code/ecf/forkprobO.c
`
`Google - Exhibit 1023, page 603
`
`123
`
`
`4
`
`5 6
`
`7891
`
`0
`11 }
`
`:f/fork.c
`
`:f/fork.c
`
`ent, but
`d child.
`!d. But
`:d to be
`
`ses that
`>e inter-
`i on our
`wed by
`general,
`wing of
`
`ent and
`cess, we
`process
`eap, the
`pie pro-
`id when
`he child
`es. Any
`and are
`
`

`
`——■I
`
`Section 13.1 Concurrent Programming With Processes 849
`
`Applications that use application-level concurrency are known as concurrent pro­
`grams. Modem operating systems provide three basic approaches for building
`concurrent programs:
`
`a Processes. With this approach, each logical control flow is a process that
`is scheduled and maintained by the kernel. Since processes have separate
`virtual address spaces, flows that want to communicate with each other must
`use some kind of explicit interprocess communication (IPC) mechanism.
`• I/O multiplexing. This is a form of concurrent programming where appli­
`cations explicitly schedule their own logical flows in the context of a single
`process. Logical flows are modeled as state machines that the main program
`explicitly transitions from state to state as a result of data arriving on file
`descriptors. Since the program is a single process, all flows share the same
`address space.
`v L
`» Threads. Threads are logical flows that ruh in the context of a single process
`and are scheduled by the kernel. You can think of threads as a hybrid of
`the other two approaches, scheduled by the kernel like process flows, and
`sharing the same virtual address space like I/O multiplexing flows.
`
`' This chapter investigates these different concurrent programming techniques. To
`keep our discussion concrete, we will work with the same motivating application
`throughout—a concurrent version of the iterative echo server from Section 12.4.9.
`
`13.1 Concurrent Programming With Processes
`
`The simplest way to build a concurrent program is with processes, using familiar
`functions such as fork, exec, and waitpid. For example, a natural approach for
`building a concurrent server is to accept client connection requests in the parent,
`and then create a new child process to service each new client.
`To see how this might work, suppose we have two clients'and a server that is
`listening for connection requests on a listening descriptor (say 3). Now suppose
`that the server accepts a connection request from client 1 and returns a connected
`descriptor (say 4), as shown in Figure 13.1.
`
`Client 1
`
`Connection
`>•.... request
`•••-.
`—
`
`clientfd
`
`listen£d(3)
`
`Server
`
`conn£d{4)
`
`Client 2
`clientfd
`Figure 13.1 Step V. Server accepts
`connection request from client.
`
`Google - Exhibit 1023, page 849
`
`overlap
`at many
`rocesses.
`
`that the
`not just
`grams as
`ations to
`program
`rrency is
`
`i a single
`executing
`multiple
`. simultc
`flows can
`nportani
`
`to arrive
`I busy by
`rrency in
`
`nand the
`icy might
`iem win­
`time the
`meurrent
`
`, use eon-
`;her oper-
`ic storage
`by defer-
`r priority.
`
`s that ■■
`oneclii nt
`ier clii
`■usands c
`ny service
`at ere ■
`to serv..
`lopolk
`
`I
`
`■
`
`

`
`850 Chapter 13 Concurrent Programming
`
`Data
`transfers
`
`Child 1
`connfd{4) .,
`
`listenfd{3)
`c
`
`Server
`
`Client 1
`
`clientfd
`
`Client 2
`
`clientfd
`Figure 13.2 Step 2: Server forks a
`child process to service the client.
`
`After accepting the connection request, the server forks a child, which gets a
`complete copy of the server’s descriptor table. The child closes its copy of listening
`descriptor 3, and the parent closes its copy of connected descriptor 4, since they
`are no longer needed. This gives us the situation in Figure 13.2, where the child
`process is busy servicing the client.
`Since the connected descriptors in the parent and child each point to the
`same file table entry, it is crucial for the parent to close its copy of the connected
`descriptor. Otherwise, the file table entry for connected descriptor 4 will never
`be released, and the resulting memory leak will eventually consume the available
`memory and crash the system.
`Now, suppose that after the parent creates the child for client 1, it accepts a
`new connection request from client 2 and returns a new connected descriptor (say
`5), as shown in Figure 13.3.
`The parent then forks another child, which begins servicing its client using
`connected descriptor 5, as shown tin Figure 13.4. At this point, the parent is
`waiting for the next connection request and the two children are servicing their
`respective clients concurrently."
`
`i
`
`t
`
`Data
`transfers
`
`Child 1
`
`connfdU)
`
`Client 1
`
`clientfd
`
`Client 2
`
`Connection
`request
`
`listenfcM3)
`
`Server
`
`connfd{5)
`
`clientfd
`Figure 133 Step 3: Server accepts
`another connection request
`
`Client 1
`cli
`
`Client 2
`
`cli.
`
`Figure 13.
`other chih
`
`13.1.1
`Figure 13.
`Thee
`points of i
`. First
`SIG<
`sigm
`sign;
`mult
`• Seco
`nfd
`impc
`tor t<
`• Final
`conn
`child
`
`13.1.2 P
`Processes)
`children: F
`address sp;
`possible fo
`process, wi
`On the
`to share st
`(interproce
`
`Google - Exhibit 1023, page 850
`
`

`
`Section 13.1 Concurrent Programming With Processes 851
`
`Client 1
`
`clientfd
`
`Data
`transfers
`
`Child 1
`conn£d(4)
`
`listened E3)
`Server
`
`■
`
`||
`
`Client 2
`clientfd
`
`Data
`transfers
`
`I
`
`Child 2
`connfd(5)
`Figure 13.4 Step 4: Server forks an­
`other child to service the new client.
`
`13.1.1 A Concurrent Serv