MODERN
`OPERATING SYSTEMS
`
`SECOND EDITION
`
`ANDREW S. TANENBAUM
`
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`Prentice
`Hall
`
`~
`
`PRENTICE HALL
`UPPER SADDLE RIVER, NEW JERSEY 07458
`
`Page 1 of 79
`
`Mercedes Exhibit 1027
`
`

`
`Library of Congress Cataloging-in-'Publication Data
`Tanenbaum, Andrew S.
`Modern operating systems / Andrew S. Tanenbaum.--2nd ed.
`p.
`em.
`Includes bibliographical references and index.
`ISBN 0-13-031358-0
`1.0perating systems
`
`(Computers)
`
`I. Title
`
`QA76.76.063 T359 2001
`005.4'3--dc21
`
`Vice President and Editorial Director, ECS: Marda Horton
`Publisher: Alan Apt
`Associate Editor: Toni D. Holm
`Editorial Assistant: Amy K. Todd
`Vice President and Director of Production and Manufacturing, ESM: David W. Riccardi
`Executive Managing Editor: Vince O'Brien
`Managing Editor: David A. George
`Senior Production Editor: Camille Trentacoste
`Director of Creative Services: Paul Belfanti
`Creative Director: Carole Anson
`Art Director: Heather Scott
`Cover Art: Don Martinetti
`Cover Design: Joseph Sengotta
`Assistant to Art Director: John Christiana
`Interior Illustration: Patricia Gutierrez
`Interior Design and Typesetting; Cover Illustration Concept: Andrew S. Tanenbaum
`Manufacturing Manager: Trudy Pisciotti
`Manufacturing Buyer: Pat Brown
`Marketing Manager: Jennie Burger
`
`Upper Saddle River. New Jersey 07458
`
`• © 2001 by Prentice-Hall, Inc,
`
`The authors 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 authors and pub(cid:173)
`lisher make no warranty of any kind, expressed or implied, with regard to these programs or to the documentation
`contained in this book. The authors and publisher shall not be liable in any event for incidental or consequential dam(cid:173)
`ages in connection with, or arising out of, the furnishing, performance. or use of these programs,
`
`Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks
`and registered trademarks. Where those designations appear in this book, and Prentice Hall and the authors were
`aware of a trademark claim, the designations have been plinted in initial caps or all caps, All product names mentioned
`remain trademarks or registered trademarks of their respective owners,
`
`All rights reserved. No part of this book may be reproduced, in any form or by any means.
`without permission in writing from the publisher.
`
`Printed in the United States of America
`
`10987654321
`
`ISBN 0-13-031358-0
`
`Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall Canada Inc,. Toronto
`Prentice-Hall Hispanoamericana, S,A., Mexico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc" Tokyo
`Pearson Education Asia Pte. Ltd" Singapore
`Editora Prentice-Hall do Brasil, Ltda" Rio de Janeiro
`
`Page 2 of 79
`
`

`
`2
`
`PROCESSES AND THREADS
`
`We are now about to embark on a detailed study of how operating systems are
`designed and constructed. The most central concept in any operating system is
`the process: an abstraction of a running program. Everything else hinges on this
`concept, and it is important that the operating system designer (and student) have
`a thorough understanding of what a process is as early as possible.
`
`2.1 PROCESSES
`
`All modem computers can do several things at the same time. While running
`a user program, a computer can also be reading from a disk and outputting text to
`a screen or printer.
`In a multiprogramming system, the CPU also switches from
`program to program, running each for tens or hundreds of milliseconds. While,
`strictly speaking, at any instant of time, the CPU is running only one program, in
`the course of I second, it may work on several programs, thus giving the users the
`illusion of parallelism. Sometimes people speak of pseudoparallelism in this
`context, to contrast it with the true hardware parallelism of multiprocessor sys(cid:173)
`tems (which have two or more CPUs sharing the same physical memory). Keep(cid:173)
`ing track of multiple, parallel activities is hard for people to do. Therefore, oper(cid:173)
`ating system designers over the years have evolved a conceptual model (sequen(cid:173)
`tial processes) that makes parallelism easier to deal with. That model, its uses,
`and some of its consequences form the subject of this chapter.
`
`71
`
`Page 3 of 79
`
`

`
`72
`
`PROCESSES AND THREADS
`
`CHAP. 2
`
`2.1.1 The Process Model
`
`In this model, all the runnable software on the computer, sometimes including
`the operating system, is organized into a number of sequential processes, or just
`processes for short. A process is just an executing program, including the current
`values of the program counter, registers, and variables. Conceptually, each proc(cid:173)
`ess has its own virtual CPU. In reality, of course, the real CPU switches back and
`forth from process to process, but to understand the system, it is much easier to
`think about a collection of processes running in (pseudo) parallel, than to try to
`keep track of how the CPU switches from program to program. This rapid
`switching back and forth is called multiprogramming, as we saw in Chap. 1.
`In Fig. 2-1 (a) we see a computer multiprogramming four programs in
`memory.
`In Fig. 2-1(b) we see four processes, each with its own flow of control
`(i.e., its own logical program counter), and each one running independently of the
`other ones. Of course, there is only one physical program counter, so when each
`process runs, its logical program counter is loaded into the real program counter.
`When it is finished for the time being, the physical program counter is saved in
`the process'
`logical program counter in memory.
`In Fig. 2-1 (c) we see that
`viewed over a long enough time interval, all the processes have made progress,
`but at any given instant only one process is actually running.
`
`One program counter
`
`Process
`cr-__A---j switch
`B
`
`Four program counters
`
`gJ D
`Ql
`12 c
`a. B
`
`A
`
`Dt
`
`(b)
`
`Time ---
`
`(c)
`
`Dc
`
`(a)
`
`(b) Conceptual model of
`Figure 2-1. (a) Multiprogramming of four programs.
`four independent, sequential processes. (c) Only one program is active at once.
`
`the rate at
`With the CPU switching back and forth among the processes,
`which a process performs its computation will not be uniform and probably not
`even reproducible if the same processes are run again. Thus, processes must not
`be programmed with built-in assumptions about timing. Consider, for example,
`an I/O process that starts a streamer tape to restore backed up files, executes an
`idle loop 10,000 times to let it get up to speed, and then issues a command to read
`the first record.
`If the CPU decides to switch to another process during the idle
`loop, the tape process might not run again until after the first record was already
`past the read head. When a process has critical real-time requirements like this,
`
`Page 4 of 79
`
`

`
`SEC. 2.\
`
`PROCESSES
`
`73
`
`that is, particular events must occur within a specified number of milliseconds,
`special measures must be taken to ensure that they do occur. Normally, however,
`most processes are not affected by the underlying multiprogramming of the CPU
`or the relative speeds of different processes.
`The difference between a process and a program is subtle, but crucial. An
`analogy make help here. Consider a culinary-minded computer scientist who is
`baking a birthday cake for his daughter. He has a birthday cake recipe and a
`kitchen well stocked with all the input: flour, eggs, sugar, extract of vanilla, and
`so on. In this analogy, the recipe is the program (i.e., an algorithm expressed in
`some suitable notation), the computer scientist is the processor (CPU), and the
`cake ingredients are the input data. The process is the activity consisting of our
`baker reading the recipe, fetching the ingredients, and baking the cake.
`Now imagine that the computer scientist's son comes running in crying, say(cid:173)
`ing that he has been stung by a bee. The computer scientist records where he was
`in the recipe (the state of the current process is saved), gets out a first aid book,
`and begins following the directions in it. Here we see the processor being
`switched from one process (baking) to a higher-priority process (administering
`medical care), each having a different program (recipe versus first aid book).
`When the bee sting has been taken care of, the computer scientist goes back to his
`cake, continuing at the point where he left off.
`It has a pro(cid:173)
`The key idea here is that a process is an activity of some kind.
`gram, input, output, and a state. A single processor may be shared among several
`processes, with some scheduling algorithm being used to determine when to stop
`work on one process and service a different one.
`
`2.1.2 Process Creation
`
`Operating systems need some way to make sure all the necessary processes
`exist.
`In very simple systems, or in systems designed for running only a single
`application (e.g., the controller in a microwave oven), it may be possible to have
`all the processes that will ever be needed be present when the system comes up.
`In general-purpose systems, however, some way is needed to create and terminate
`processes as needed during operation. We will now look at some of the issues.
`There are four principal events that cause processes to be created:
`
`1. System initialization.
`
`2. Execution of a process creation system call by a running process.
`
`3. A user request to create a new process.
`
`4.
`
`Initiation of a batch job.
`
`When an operating system is booted,
`typically several processes are created.
`Some of these are foreground processes,
`that
`is, processes that
`interact with
`
`Page 5 of 79
`
`

`
`74
`
`PROCESSES AND THREADS
`
`CHAP. 2
`
`(human) users and perform work for them. Others are background processes,
`which are not associated with particular users, but instead have some specific
`function. For example, one background process may be designed to accept
`incoming email, sleeping most of the day but suddenly springing to life when
`email arrives. Another background process may be designed to accept incoming
`requests for Web pages hosted on that machine, waking up when a request arrives
`to service the request. Processes that stay in the background to handle some
`activity such as email.Webpages.news.printing. and so on are called daemons.
`Large systems commonly have dozens of them.
`In UNIX, the ps program can be
`used to list the running processes.
`In Windows 95/98/Me, typing CTRL-ALT(cid:173)
`DEL once shows what's running.
`In Windows 2000, the task manager is used.
`In addition to the processes created at boot time, new processes can be created
`afterward as well. Often a running process will issue system calls to create one or
`more new processes to help it do its job. Creating new processes is particularly
`useful when the work to be done can easily be formulated in terms of several
`related, but otherwise independent interacting processes. For example, if a large
`amount of data is being fetched over a network for subsequent processing, it may
`be convenient to create one process to fetch the data and put them in a shared
`buffer while a second process removes the data items and processes them. On a
`multiprocessor, allowing each process to run on a different CPU may also make
`the job go faster.
`[n interactive systems, users can start a program by typing a command or
`(double) clicking an icon. Taking either of these actions starts a new process and
`runs the selected program in it. In command-based UNIX systems running X Win(cid:173)
`dows, the new process takes over the window in which it was started.
`In Micro(cid:173)
`soft Windows, when a process is started it does not have a window, but it can
`create one (or more) and most do. In both systems, users may have multiple win(cid:173)
`dows open at once, each running some process. Using the mouse, the user can
`select a window and interact with the process, for example, providing input when
`needed.
`The last situation in which processes are created applies only to the batch sys(cid:173)
`tems found on large mainframes. Here users can submit batch jobs to the system
`(possibly remotely). When the operating system decides that it has the resources
`to run another job, it creates a new process and runs the next job from the input
`queue in it.
`Technically, in all these cases, a new process is created by having an existing
`process execute a process creation system call. That process may be a running
`user process, a system process invoked from the keyboard or mouse, or a batch
`manager process. What that process does is execute a system call to create the
`new process. This system call tells the operating system to create a new process
`and indicates, directly or indirectly, which program to run in it.
`In UNIX, there is only one system call to create a new process: fork. This call
`creates an exact clone of the calling process. After the fork, the two processes, the
`
`Page 6 of 79
`
`

`
`SEC. 2.1
`
`PROCESSES
`
`75
`
`parent and the child, have the same memory image, the same environment strings,
`and the same open files. That is all there is. Usually, the child process then exe(cid:173)
`cutes execve or a similar system call to change its memory image and run a new
`program. For example, when a user types a command, say, sort, to the shell, the
`shell forks off a child process and the child executes sort. The reason for this
`two-step process is to allow the child to manipulate its file descriptors after the
`fork but before the execve to accomplish redirection of standard input, standard
`output, and standard error.
`In Windows, in contrast, a single Win32 function call, CreateProcess, han(cid:173)
`dles both process creation and loading the correct program into the new process.
`This call has 10 parameters, which include the program to be executed, the com(cid:173)
`mand line parameters to feed that program, various security attributes, bits that
`control whether open files are inherited, priority information, a specification of
`the window to be created for the process (if any), and a pointer to a structure in
`In
`which information about the newly created process is returned to the caller.
`addition to CreateProcess, Win32 has about 100 other functions for managing
`and synchronizing processes and related topics.
`In both UNIX and Windows, after a process is created, both the parent and
`child have their own distinct address spaces.
`If either process changes a word in
`its address space, the change is not visible to the other process.
`In UNIX, the
`child's initial address space is a copy of the parent's, but there are two distinct
`address spaces involved; no writable memory is shared (some UNIX implementa(cid:173)
`It is,
`tions share the program text between the two since that cannot be modified).
`however, possible for a newly created process to share some of its creator's other
`resources, such as open files.
`In Windows, the parent's and child's address spaces
`are different from the start.
`
`2.1.3 Process Termination
`
`After a process has been created, it starts running and does whatever its job is.
`However, nothing lasts forever, not even processes. Sooner or later the new proc(cid:173)
`ess will terminate, usually due to one of the following conditions:
`
`1. Normal exit (voluntary).
`
`2. Error exit (voluntary).
`
`3. Fatal error (involuntary).
`
`4. Killed by another process (involuntary).
`
`Most processes terminate because they have done their work. When a com(cid:173)
`piler has compiled the program given to it, the compiler executes a system call to
`tell the operating system that it is finished. This call is exit in UNIX and ExitPro(cid:173)
`cess in Windows. Screen-oriented programs also support voluntary termination.
`
`Page 7 of 79
`
`

`
`76
`
`PROCESSES AND THREADS
`
`CHAP. 2
`
`Word processors, Internet browsers and similar programs always have an icon or
`menu item that the user can click to tell the process to remove any temporary files
`it has open and then terminate.
`The second reason for termination is that the process discovers a fatal error.
`For example, if a user types the command
`
`cc foo.c
`
`to compile the program foo.c and no such file exists, the compiler simply exits.
`Screen-oriented interactive processes generally do not exit when given bad
`parameters.
`Instead they pop up a dialog box and ask the user to try again.
`The third reason for termination is an error caused by the process, often due to
`a program bug. Examples include executing an illegal instruction, referencing
`In some systems (e.g., UNIX), a process
`nonexistent memory, or dividing by zero.
`can tell the operating system that it wishes to handle certain errors itself, in which
`case the process is signaled (interrupted) instead of terminated when one of the
`errors occurs.
`The fourth reason a process might terminate is that a process executes a sys(cid:173)
`tem call telling the operating system to kill some other process.
`In UNIX this call
`is kill. The corresponding Win32 function is TerminateProcess. In both cases, the
`In some systems,
`killer must have the necessary authorization to do in the killee.
`when a process terminates, either voluntarily or otherwise, all processes it created
`are immediately killed as well. Neither UNIX nor Windows works this way, how(cid:173)
`ever.
`
`2.1.4 Process Hierarchies
`
`In some systems, when a process creates another process, the parent process
`and child process continue to be associated in certain ways. The child process can
`itself create more processes, forming a process hierarchy. Note that unlike plants
`and animals that use sexual reproduction, a process has only one parent (but zero,
`one, two, or more children).
`In UNIX, a process and all of its children and further descendants together
`form a process group. When a user sends a signal from the keyboard, the signal is
`delivered to all members of the process group currently associated with the key(cid:173)
`board (usually all active processes that were created in the current window).
`Indi(cid:173)
`vidually, each process can catch the signal, ignore the signal, or take the default
`action, which is to be killed by the signal.
`As another example of where the process hierarchy plays a role, let us look at
`how UNIX initializes itself when it is started. A special process, called init, is
`present in the boot image. When it starts running, it reads a file telling how many
`terminals there are. Then it forks off one new process per terminal. These proc(cid:173)
`esses wait for someone to log in. If a login is successful, the login process exe(cid:173)
`cutes a shell to accept commands. These commands may start up more processes,
`
`Page 8 of 79
`
`

`
`SEC. 2.1
`
`PROCESSES
`
`77
`
`and so forth. Thus, all the processes in the whole system belong to a single tree,
`with init at the root.
`In contrast, Windows does not have any concept of a process hierarchy. All
`processes are equal. The only place where there is something like a process
`hierarchy is that when a process is created,
`the parent is given a special token
`(called a handle) that it can use to control the child. However, it is free to pass
`this token to some other process,
`thus invalidating the hierarchy. Processes in
`UNIX cannot disinherit their children.
`
`2.1.5 Process States
`
`Although each process is an independent entity, with its own program counter
`and internal state, processes often need to interact with other processes. One
`process may generate some output that another process uses as input.
`In the shell
`command
`
`cat chapter1 chapter2 chapter3 I grep tree
`
`the first process, running cat, concatenates and outputs three files. The second
`process, running grep, selects all lines containing the word "tree." Depending on
`the relative speeds of the two processes (which depends on both the relative com(cid:173)
`plexity of the programs and how much CPU time each one has had), it may hap(cid:173)
`It must then
`pen that grep is ready to run, but there is no input waiting for it.
`block until some input is available.
`When a process blocks, it does so because logically it cannot continue, typi(cid:173)
`It is also possible for
`cally because it is waiting for input that is not yet available.
`a process that is conceptually ready and able to run to be stopped because the
`operating system has decided to allocate the CPU to another process for a while.
`These two conditions are completely different.
`In the first case, the suspension is
`inherent in the problem (you cannot process the user's command line until it has
`it is a technicality of the system (not enough
`been typed).
`In the second case,
`CPUs to give each process its own private processor).
`In Fig. 2-2 we see a state
`diagram showing the three states a process may be in:
`
`I. Running (actually using the CPU at that instant).
`
`2. Ready (runnable; temporarily stopped to let another process run).
`
`3. Blocked (unable to run until some external event happens).
`
`In both cases the process is willing to
`Logically, the first two states are similar.
`run, only in the second one, there is temporarily no CPU available for it. The
`third state is different from the first two in that the process cannot run, even if the
`CPU has nothing else to do.
`Four transitions are possible among these three states, as shown. Transition 1
`occurs when a process discovers that it cannot continue.
`In some systems the
`
`Page 9 of 79
`
`

`
`78
`
`PROCESSES AND THREADS
`
`CHAP. 2
`
`1. Process blocks for input
`2. Scheduler picks another process
`3. Scheduler picks this process
`4. Input becomes available
`
`Figure 2-2. A process can be in running, blocked, or ready state. Transitions
`between these states are as shown.
`process must execute a system call, such as block or pause, to get into blocked
`state. In other systems, including UNIX, when a process reads from a pipe or spe(cid:173)
`cial file (e.g., a terminal) and there is no input available, the process is automati(cid:173)
`cally blocked.
`Transitions 2 and 3 are caused by the process scheduler, a part of the operat(cid:173)
`ing system, without the process even knowing about them. Transition 2 occurs
`when the scheduler decides that the running process has run long enough, and it is
`time to let another process have some CPU time. Transition 3 occurs when all the
`other processes have had their fair share and it is time for the first process to get
`the CPU to run again. The subject of scheduling, that is, deciding which process
`should run when and for how long, is an important one; we will look at it later in
`this chapter. Many algorithms have been devised to try to balance the competing
`demands of efficiency for the system as a whole and fairness to individual
`processes. We will study some of them later in this chapter.
`Transition 4 occurs when the external event for which a process was waiting
`(such as the arrival of some input) happens. If no other process is running at that
`instant, transition 3 will be triggered and the process will start running. Otherwise
`it may have to wait in ready state for a little while until the CPU is available and
`its tum comes.
`Using the process model, it becomes much easier to think about what is going
`on inside the system. Some of the processes run programs that carry out com(cid:173)
`mands typed in by a user. Other processes are part of the system and handle tasks
`such as carrying out requests for file services or managing the details of running a
`disk or a tape drive. When a disk interrupt occurs, the system makes a decision to
`stop running the current process and run the disk process, which was blocked
`waiting for that interrupt. Thus, instead of thinking about interrupts, we can think
`about user processes, disk processes, terminal processes, and so on, which block
`when they are waiting for something to happen. When the disk has been read or
`the character typed, the process waiting for it is unblocked and is eligible to run
`again.
`This view gives rise to the model shown in Fig. 2-3. Here the lowest level of
`the operating system is the scheduler, with a variety of processes on top of it. All
`the interrupt handling and details of actually starting and stopping processes are
`hidden away in what is here called the scheduler, which is actually not much
`
`Page 10 of 79
`
`

`
`SEC. 2.1
`
`PROCESSES
`
`79
`
`code. The rest of the operating system is nicely structured in process form. Few
`real systems are as nicely structured as this, however.
`
`0
`
`1
`
`Processes
`
`...
`
`Scheduler
`
`n-2 n-1
`
`Figure 2-3. The lowest layer of a process-structured operating system handles
`interrupts and scheduling. Above that layer are sequential processes.
`
`2.1.6 Implementation of Processes
`
`To implement the process model, the operating system maintains a table (an
`array of structures), called the process table, with one entry per process.
`(Some
`authors call these entries process control blocks.) This entry contains informa(cid:173)
`tion about the process' state, its program counter, stack pointer, memory alloca(cid:173)
`its accounting and scheduling information, and
`tion, the status of its open files,
`everything else about the process that must be saved when the process is switched
`from running to ready or blocked state so that it can be restarted later as if it had
`never been stopped.
`Figure 2-4 shows some of the more important fields in a typical system. The
`fields in the first column relate to process management. The other two columns
`relate to memory management and file management, respectively.
`It should be
`noted that precisely which fields the process table has is highly system dependent,
`but this figure gives a general idea of the kinds of information needed.
`Now that we have looked at the process table, it is possible to explain a little
`more about how the illusion of multiple sequential processes is maintained on a
`machine with one CPU and many I/O devices. Associated with each I/O device
`class (e.g., floppy disks, hard disks, timers, terminals) is a location (often near the
`It contains the address of the
`bottom of memory) called the interrupt vector.
`interrupt service procedure. Suppose that user process 3 is running when a disk
`interrupt occurs. User process 3's program counter, program status word, and
`possibly one or more registers are pushed onto the (current) stack by the interrupt
`hardware. The computer then jumps to the address specified in the disk interrupt
`vector. That is all the hardware does. From here on, it is up to the software, in
`particular, the interrupt service procedure.
`All interrupts start by saving the registers, often in the process table entry for
`the current process. Then the information pushed onto the stack by the interrupt is
`removed and the stack pointer is set to point to a temporary stack used by the
`
`Page 11 of 79
`
`

`
`80
`
`PROCESSES AND THREADS
`
`CHAP. 2
`
`Memory management
`Pointer to text segment
`Pointer to data segment
`Pointer to stack segment
`
`File management
`Root directory
`Working directory
`File descriptors
`User 10
`Group 10
`
`Process management
`Registers
`Program counter
`Program status word
`Stack pointer
`Process state
`Priority
`Scheduling parameters
`Process 10
`Parent process
`Process group
`Signals
`Time when process started
`CPU time used
`Children's CPU time
`Time of next alarm
`
`Figure 2-4. Some of the fields of a typical process table entry.
`process handler. Actions such as saving the registers and setting the stack pointer
`cannot even be expressed in high-level
`languages such as C, so they are per(cid:173)
`formed by a small assembly language routine, usually the same one for all inter(cid:173)
`rupts since the work of saving the registers is identical, no matter what the cause
`of the interrupt is.
`When this routine is finished, it calls a C procedure to do the rest of the work
`(We assume the operating system is written in C,
`for this specific interrupt type.
`the usual choice for all real operating systems.) When it has done its job, possibly
`making some process now ready, the scheduler is called to see who to run next.
`After that, control is passed back to the assembly language code to load up the
`registers and memory map for the now-current process and start it running. Inter(cid:173)
`rupt handling and scheduling are summarized in Fig. 2-5.
`It is worth noting that
`the details vary somewhat from system to system.
`
`1. Hardware stacks program counter, etc.
`2. Hardware loads new program counter from interrupt vector.
`3. Assembly language procedure saves registers.
`4. Assembly language procedure sets up new stack.
`5. C interrupt service runs (typically reads and buffers input).
`6. Scheduler decides which process is to run next.
`7. C procedure returns to the assembly code.
`8. Assembly language procedure starts up new current process.
`
`Figure 2-5. Skeleton of what
`when an interrupt occurs.
`
`the lowest
`
`level of the operating system does
`
`Page 12 of 79
`
`

`
`SEC. 2.1
`
`PROCESSES
`
`81
`
`2.2 THREADS
`
`In traditional operating systems, each process has an address space and a sin(cid:173)
`gle thread of control.
`In fact, that is almost the definition of a process. Neverthe(cid:173)
`less,
`there are frequently situations in which it is desirable to have multiple
`threads of control in the same address space running in quasi-parallel, as though
`they were separate processes (except for the shared address space).
`In the follow(cid:173)
`ing sections we will discuss these situations and their implications.
`
`2.2.1 The Thread Model
`
`The process model as we have discussed it thus far is based on two indepen(cid:173)
`dent concepts:
`resource grouping and execution. Sometimes it
`is useful
`to
`separate them; this is where threads come in.
`One way of looking at a process is that it is way to group related resources
`together. A process has an address space containing program text and data, as
`well as other resources. These resource may include open files, child processes,
`pending alarms, signal handlers, accounting information, and more. By putting
`them together in the form of a process, they can be managed more easily.
`The other concept a process has is a thread of execution, usually shortened to
`just thread. The thread has a program counter that keeps track of which instruc(cid:173)
`tion to execute next.
`It has registers, which hold its current working variables.
`It
`has a stack, which contains the execution history, with one frame for each pro(cid:173)
`cedure called but not yet returned from. Although a thread must execute in some
`process,
`the thread and its process are different concepts and can be treated
`separately. Processes are used to group resources together; threads are the entities
`scheduled for execution on the CPU.
`What threads add to the process model is to allow multiple executions to take
`place in the same process environment,
`to a large degree independent of one
`another. Having multiple threads running in parallel in one process is analogous
`to having multiple processes running in parallel in one computer.
`In the former
`case, the threads share an address space, open files, and other resources.
`In the
`latter case, processes share physical memory, disks, printers, and other resources.
`Because threads have some of the properties of processes, they are sometimes
`called lightweight processes. The term multithreading is also used to describe
`the situation of allowing multiple threads in the same process.
`In Fig. 2-6(a) we see three traditional processes. Each process has its own
`address space and a single thread of control.
`In contrast, in Fig. 2-6(b) we see a
`single process with three threads of control. Although in both cases we have three
`threads, in Fig. 2-6(a) each of them operates in a different address space, whereas
`in Fig. 2-6(b) all three of them share the same address space.
`When a multithreaded process is run on a single-CPU system, the threads take
`turns running.
`In Fig. 2-1, we saw how multiprogramming of processes works.
`
`Page 13 of 79
`
`

`
`82
`
`PROCESSES AND THREADS
`
`CHAP. 2
`
`Process 1
`
`Process 1
`
`Process 1
`
`Process
`
`User mspace ~
`
`Kernel {
`space
`
`Kernel
`
`(a)
`
`Thread
`
`Kernel
`
`(b)
`
`Figure 2-6. (a) Three processes each with one thread. (b) One process with
`three threads.
`
`By switching back and forth among multiple processes, the system gives the illu(cid:173)
`sion of separate sequential processes running in parallel. Multithreading works
`the same way. The CPU switches rapidly back and forth among the threads pro(cid:173)
`viding the illusion that the threads are running in parallel, albeit on a slower CPU
`than the real one. With three compute-bound threads in a process, the threads
`would appear to be running in parallel, each one on a CPU with one-third the
`speed of the real CPU.
`Different
`threads in a process are not quite as independent as different
`processes. All threads have exactly the same address space, which means that
`they also share the same global varia