`
`Microsoft Corp. Exhibit 1055
`
`

`

`OPERATING
`SYSTEM
`CONCEPTS
`
`Fifth Edition
`
`
`
`Abraham Silberschatz
`
`Bell Labs
`
`Peter Baer Galvin
`
`Corporate Technologies, Inc.
`
`
`
`Aw ADDISON-WESLEY
`An imprint of Addison Wesley Longinan, lnc.
`
`Reading, Massachusetts 0 Harlow, England 0 Menlo Park, California
`Berkeley, California O Don Mills, Ontario 0 Sydney
`Bonn 0 Amsterdam 0 Tokyo 0 Mexico City
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`Editor—In-Chief: Lynne Doran Cote
`Acquisitions Editor: Maite Suarez-Rivas
`Associate Editor: Deborah Lafierty
`Production Editor: Patricia A. O. Unuban
`Design Editor: Alwyn R. Velasquez
`Manufacturing Coordinator: Indy Sullivan
`\
`Cover Illustration: Susan Cyr
`
`Access the latest information about Addison-Wesley titles from our World Wide
`Web site: http: / /www.awl.com/ cseng
`
`Many of the designations used by manufacturers and sellers to distinguish their
`products are claimed as trademarks. Where those designations appear in this
`book, and the publisher was aware of a trademark claim, the designations have
`been printed in initial caps or in all caps.
`
`The programs and applications presented in this book have been included for
`their instructional value. They have been tested with care but are not guaran-
`teed for any particular purpose. Neither the publisher or the author offers any
`warranties or representations, nor do they accept any liabilities with respect to
`the programs or applications.
`
`Reprinted with corrections, February 1998.
`
`Copyright © 1998 by Addison Wesley Longman, Inc.
`
`All rights reserved. No part of this publication may be reproduced, or stored in
`a database or retrieval system, or transmitted in any form or by any means,
`electronic, mechanical, photocopying, recording, or any other media embodi-
`ments now know or hereafter to become known, without the prior written per-
`mission of the publisher. Printed in the United States of America.
`
`Library of Congress Cataloging-in-Publication Data
`
`Silberschatz, Abraham.
`Operating system concepts / Abraham Silberschatz, Peter Galvin. —
`5th ed.
`
`p. cm
`Includes bibliographical references and index.
`ISBN 0-201-59113—8
`
`1. Operating systems (Computers) I. Galvin, Peter B.
`QA76.76.063S5583 1998
`
`II. Title.
`
`005.4, 3—dc21
`
`ISBN 0-201-59113-8
`3 4 5 6 7 8 910 MA 01009998
`
`97-28556
`CIP
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`Chapter 4
`
` PROCESSES
`
`
`
`Early computer systems allowed only one program to be executed at a time.
`This program had complete control of the system, and had access to all of the
`system’s resources. Current-day computer systems allow multiple programs
`to be loaded into memory and to be executed concurrently. This evolution
`required firmer control and more compartmentalization of the various pro-
`grams. These needs resulted in the notion of a process, which is a program in
`execution. A process is the unit of work in a modern time-sharing system.
`The more complex the operating system, the more it is expected to do on
`behalf of its users. Although its main concern is the execution of user programs,
`it also needs to take care of various system tasks that are better left outside the
`kernel itself. A system therefore consists of a collection of processes: Operating-
`system processes executing system code, and user processes executing user
`code. All these processes can potentially execute concurrently, with the CPU
`(or CPUs) multiplexed among them. By switching the CPU between processes,
`the operating system can make the computer more productive.
`
`4.1 l Process Concept
`
`One hindrance to the discussion of operating systems is the question of What to
`call all the CPU activities. A batch system executes jobs, whereas a time-shared
`system has user programs, or tasks. Even on a single-user system, such as MS-DOS
`and Macintosh OS, a user may be able to run several programs at one time: one
`interactive and several batch programs. Even if the user can execute only one
`
`Microsoft Corp. Exhibit 1635
`
`Microsoft Corp. Exhibit 1055
`
`

`

`90
`
`Chapter 4 Processes
`
`program at a time, the operating system may need to support its own internal
`programmed activities, such as spooling. In many respects, all of these activities
`are similar, so we call all of them processes.
`The terms job and process are used almost interchangeably in this text.
`Although we personally prefer the term process, much of operating—system
`theory and terminology was developed during a time when the major activity
`of operating systems was job processing.
`It would be misleading to avoid
`the use of commonly accepted terms that include the word job (such as job
`scheduling) simply because the term process has superseded it.
`
`4.1.1 The Process
`
`Informally, a process is a program in execution. The execution of a process must
`progress in a sequential fashion. That is, at any time, at most one instruction is
`executed on behalf of the process.
`A process is more than the program code (sometimes known as the text
`section).
`It also includes the current activity, as represented by the value of
`the program counter and the contents of the processor’s registers. A process
`generally also includes the process stack, containing temporary data (such as
`subroutine parameters, return addresses, and temporary variables), and a data
`section containing global variables.
`We emphasize that a program by itself is not a process; a program is a
`passive entity, such as the contents of a file stored on disk, whereas a process
`is an active entity, with a program counter specifying the next instruction to
`execute and a set of associated resources.
`Although two processes may be associated with the same program, they
`are nevertheless considered two separate execution sequences. For instance,
`several users may be running copies of the mail program, or the same user may
`invoke many copies of the editor program. Each of these is a separate process,
`and, although the text sections are equivalent, the data sections will vary. It is
`
`
` admitted interrupt terminated
`
`
`
`
`
`
`I/O or event wait
`
`
`running
`-—._
`
`
`
`Figure 4.1 Diagram of process state.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`4.1 Process Concept
`
`91
`
`also common to have a process that spawns many processes as it runs. This
`issue will be further discussed in Section 4.4.
`
`4.1.2 Process State
`
`As a process executes, it changes state. The state of a process is defined in part by
`the current activity of that process. Each process may be in one of the following
`states:
`
`0 New: The process is being created.
`
`0 Running: Instructions are being executed.
`
`0 Waiting: The process is waiting for some event to occur (such as an I/O
`completion or reception of a signal).
`
`0 Ready: The process is waiting to be assigned to a processor.
`
`0 Terminated: The process has finished execution.
`
`These names are arbitrary, and vary between operating systems. The states
`that they represent are found on all systems, however. Certain operating
`systems also distinguish among more finely delineating process states.
`It is
`important to realize that only one process can be running on any processor at
`any instant. Many processes may be ready and waiting, however. The state
`diagram corresponding to these states is presented in Figure 4.1.
`
`4.1.3 Process Control Block
`
`Each process is represented in the operating system by a process control block
`(PCB)—also called a task control block. A PCB is shown in Figure 4.2. It con-
`
`
`
`
`
`
`.
`0 nt
`
`r
`
`process
`
`
`
`process number
`program counter
`
`list of open files
`
`
`
`
`
`
`Figure 4.2
`
`Process control block.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`92
`
`Chapter 4 Processes
`
`tains many pieces of information associated with a specific process, including
`these:
`
`0 Process state: The state may be new, ready, running, waiting, halted, and
`so on.
`
`0 Program counter: The counter indicates the address of the next instruction
`to be executed for this process.
`
`0 CPU registers: The registers vary in number and type, depending on the
`computer architecture. They include accumulators, index registers, stack
`pointers, and general-purpose registers, plus any condition—code informa-
`tion. Along with the program counter, this state information must be saved
`when an interrupt occurs, to allow the process to be continued correctly
`afterward (Figure 4.3).
`
`0 CPU scheduling information: This information includes a process prior-
`ity, pointers to scheduling queues, and any other scheduling parameters.
`(Chapter 5 describes process scheduling.)
`
`o Memory-management information: This information may include such
`information as the value of the base and limit registers, the page tables, or
`the segment tables depending on the memory system used by the operating
`system (Chapter 8).
`
`process PC
`
`executing
`
`operating system
`interrupt or system call
`
`process P1
`
`‘
`
`save state into PCBD
`
`f Idle
`
`
`
`J
`
`idle
`
`executing
`
`idle
`
`reload state from PCB1
`
`interrupt or system call
`
`save state into PCB1
`
`
`
`reload state from PCBo
`
`executing
`
`Figure 4.3 Diagram showing CPU switch from process to process.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`4.2 Process Scheduling
`
`93
`
`0 Accounting information: This information includes the amount of CPU
`and real time used, time limits, account numbers, job or process numbers,
`and so on.
`
`0 I/O status information: The information includes the list of I/O devices
`(such as tape drives) allocated to this process, a list of open files, and so on.
`
`The PCB simply serves as the repository for any information that may vary from
`process to process.
`
`4.2 l Process Scheduling
`
`The objective of multiprogramming is to have some process running at all times,
`to maximize CPU utilization. The objective of time sharing is to switch the CPU
`among processes so frequently that users can interact with each program while
`it is running. For a uniprocessor system, there will never be more than one
`running process. If there are more processes, the rest will have to wait until the
`CPU is free and can be rescheduled.
`
`4.2.1 Scheduling Queues
`
`As processes enter the system, they are put into a job queue. This queue consists
`of all processes in the system. The processes that are residing in main memory
`and are ready and waiting to execute are kept on a list called the ready queue.
`This queue is generally stored as a linked list. A ready-queue header will
`contain pointers to the first and last PCBs in the list. Each PCB has a pointer
`field that points to the next process in the ready queue.
`There are also other queues in the system. When a process is allocated the
`CPU, it executes for awhile and eventually quits, is interrupted, or waits for the
`occurrence of a particular event, such as the completion of an I/O request. In
`the case of an I/O request, such a request may be to a dedicated tape drive,
`or to a shared device, such as a disk. Since there are many processes in the
`system, the disk may be busy with the I/O request of some other process. The
`process therefore may have to wait for the disk. The list of processes waiting for
`a particular I/O device is called a device queue. Each device has its own device
`queue (Figure 4.4).
`A common representation for a discussion of process scheduling is a queue-
`ing diagram, such as that in Figure 4.5 (on page 95). Each rectangular box
`represents a queue. Two types of queues are present: the ready queue and a
`set of device queues. The circles represent the resources that serve the queues,
`and the arrows indicate the flow of processes in the system.
`A new process is initially put in the ready queue. It waits in the ready queue
`until it is selected for execution (or dispatched) and is given the CPU. Once the
`process is allocated the CPU and is executing, one of several events could occur:
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`94
`
`Chapter 4 Processes
`
`queue header
`
`PCB7
`
`ready
`
`mag
`tape
`unit 0
`
`
`
`
`
`head
`
`"
`_
`
`P082
`— -
`
`tape
`unit 1
`
`.
`tall
`
`
`PCB
`PCB
`PCB
`3
`14
`>6
`
`_
`
`disk
`unit 0
`
`terminal
`unit 0
`
`
`
`head
`tail
`
`PCB5
`
`
`
`
`
`Figure 4.4 The ready queue and various I/O device queues.
`
`o The process could issue an I/O request, and then be placed in an I/O queue.
`o The process could create a new subprocess and wait for its termination.
`o The process could be removed forcibly from the CPU, as a result of an
`interrupt, and be put back in the ready queue.
`
`In the first two cases, the process eventually switches from the waiting state to
`the ready state, and is then put back in the ready queue. A process continues
`this cycle until it terminates, at which time it is removed from all queues and
`has its PCB and resources deallocated.
`
`4.2.2 Schedulers
`
`A process migrates between the various scheduling queues throughout its
`lifetime. The operating system must select, for scheduling purposes, processes
`from these queues in some fashion. The selection process is carried out by the
`appropriate scheduler.
`In a batch system, there are often more processes submitted than can be
`executed immediately. These processes are spooled to a mass—storage device
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`4.2 Process Scheduling
`
`95
`
`
`
`|/O request
`
`
`time slice
`
`expired
`_I
`
`child
`\H executes
`
`|'
`
`«
`
`
`interrupt
`I occurs
`
`fork a
`
`child
`
`.-___
`
`|
`
`
`
`waitforan
`l
`
`
`interrupt J
`
`Figure 4.5 Queueing-diagram representation of process scheduling.
`
`(typically a disk), where they are kept for later execution. The long-term
`scheduler (or job scheduler) selects processes from this pool and loads them into
`memory for execution. The short-term scheduler (or CPU scheduler) selects from
`among the processes that are ready to execute, and allocates the CPU to one of
`them.
`
`The primary distinction between these two schedulers is the frequency
`of their execution. The short-term scheduler must select a new process for
`the CPU quite frequently. A process may execute for only a few milliseconds
`before waiting for an I/O request. Often, the short-term scheduler executes
`at least once every 100 milliseconds. Because of the short duration of time
`between executions, the short-term scheduler must be very fast. If it takes 10
`milliseconds to decide to execute a process for 100 milliseconds, then 10/(100
`+ 10) = 9 percent of the CPU is being used (wasted) simply for scheduling the
`work.
`
`The long-term scheduler, on the other hand, executes much less frequently.
`There may be minutes between the creation of new processes in the system.
`The long-term scheduler controls the degree ofmultiprogrumming (the number of
`processes in memory). If the degree of multiprogramming is stable, then the
`average rate of process creation must be equal to the average departure rate of
`processes leaving the system. Thus, the long-term scheduler may need to be
`invoked only when a process leaves the system. Because of the longer interval
`between executions, the long-term scheduler can afford to take more time to
`decide which process should be selected for execution.
`In
`It is important that the long-term scheduler make a careful selection.
`general, most processes can be described as either I/O bound or CPU bound.
`An I/O—bound process is one that spends more of its time doing I/0 than it spends
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`96
`
`Chapter 4 Processes
`
`doing computations. A CPU—bound process, on the other hand, is one that gener-
`ates I/O requests infrequently, using more of its time doing computation than
`an I/O-bound process uses. It is important that the long—term scheduler select
`a good process mix of I/O—bound and CPU—bound processes.
`If all processes
`are 1/0 bound, the ready queue will almost always be empty, and the short-
`term scheduler will have little to do. If all processes are CPU bound, the I/O
`waiting queue will almost always be empty, devices will go unused, and again
`the system will be unbalanced. The system with the best performance will have
`a combination of CPU-bound and I/O—bound processes.
`On some systems, the long-term scheduler may be absent or minimal. For
`example, time-sharing systems often have no long—term scheduler, but simply
`put every new process in memory for the short-term scheduler. The stability
`of these systems depends either on a physical limitation (such as the number
`of available terminals) or on the self-adjusting nature of human users.
`If the
`performance declines to unacceptable levels, some users will simply quit, and
`will do something else.
`Some operating systems, such as time—sharing systems, may introduce an
`additional, intermediate level of scheduling. This medium-term scheduler is
`diagrammed in Figure 4.6. The key idea behind a medium-term scheduler
`is that sometimes it can be advantageous to remove processes from memory
`(and from active contention for the CPU), and thus to reduce the degree of
`multiprogramming. At some later time, the process can be reintroduced into
`memory and its execution can be continued where it left off. This scheme
`is called swapping. The process is swapped out and swapped in later by the
`medium-term scheduler. Swapping may be necessary to improve the process
`mix, or because a change in memory requirements has overcommitted available
`memory, requiring memory to be freed up. Swapping is discussed in more
`detail in Chapter 8.
`
` swap in
`swap out
`partially executed
`swapped-out processes
`
`
`—m_
`
`ready queue
`
`
`
`I/O waiting
`queues
`
`I
`
`end
`
`Figure 4.6 Addition of medium—term scheduling to the queueing diagram.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`4.3 Operation on Processes
`
`97
`
`4.2.3 Context Switch
`
`Switching the CPU to another process requires saving the state of the old process
`and loading the saved state for the new process. This task is known as a
`context switch. Context-switch time is pure overhead, because the system does
`no useful work while switching.
`Its speed varies from machine to machine,
`depending on the memory speed, the number of registers which must be
`copied, and the existence of special instructions (such as a single instruction
`to load or store all registers). Typically, the speed ranges from 1 to 1000
`microseconds.
`
`Context-switch times are highly dependent on hardware support. For
`instance, some processors (such as the DECSYSTEM-ZO) provide multiple sets
`of registers. A context switch simply includes changing the pointer to the
`current register set. Of course, if there are more active processes than there are
`register sets, the system resorts to copying register data to and from memory,
`as before. Also, the more complex the operating system, the more work must
`be done during a context switch. As we shall see in Chapter 8, advanced
`memory-management techniques may require extra data to be switched with
`each context. For instance, the address space of the current process must be
`preserved as the space of the next task is prepared for use. How the address
`space is preserved, and the amount of work needed to do it, depend on the
`memory-management method of the operating system. As we shall see in
`Section 4.5, context switching has become such a performance bottleneck that
`new structures (threads) are being used to avoid it whenever possible.
`
`4.3 l Operation on Processes
`
`The processes in the system can execute concurrently, and must be created and
`deleted dynamically. Thus, the operating system must provide a mechanism
`for process creation and termination.
`
`4.3.1 Process Creation
`
`A process may create several new processes, Via a create-process system call,
`during the course of execution. The creating process is called a parent process,
`whereas the new processes are called the children of that process. Each of these
`new processes may in turn create other processes, forming a tree of processes
`(Figure 4.7).
`In general, a process will need certain resources (CPU time, memory, files,
`I/O devices) to accomplish its task. When a process creates a subprocess, the
`subprocess may be able to obtain its resources directly from the operating
`system, or it may be constrained to a subset of the resources of the parent
`process. The parent may have to partition its resources among its children,
`or it may be able to share some resources (such as memory or files) among
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`98
`
`Chapter 4 Processes
`
`
`
`
`
`Figure 4.7 A tree of processes on a typical UNIX system.
`
`several of its children. Restricting a child process to a subset of the parent’s
`resources prevents any process from overloading the system by creating too
`many subprocesses.
`In addition to the various physical and logical resources that a process
`obtains when it is created, initialization data (input) may be passed along by
`the parent process to the child process. For example, consider a process whose
`function is to display the status of a file, say P1, on the screen of a terminal.
`When it is created, it will get, as an input from its parent process, the name of the
`file F1, and it will execute using that datum to obtain the desired information.
`It may also get the name of the output device. Some operating systems pass
`resources to child processes. On such a system, the new process may get two
`open files, F1 and the terminal device, and may just need to transfer the datum
`between the two.
`When a process creates a new process, two possibilities exist in terms of
`execution:
`
`o The parent continues to execute concurrently With its children.
`
`0 The parent waits until some or all of its children have terminated.
`
`There are also two possibilities in terms of the address space of the new process:
`
`0 The child process is a duplicate of the parent process.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`4.3 Operation on Processes
`
`99
`
`o The child process has a program loaded into it.
`
`To illustrate these different implementations, let us consider the UNIX operating
`system. In UNIX, each process is identified by its process identifier, which is a
`unique integer. A new process is created by the fork system call. The new
`process consists of a copy of the address space of the original process. This
`mechanism allows the parent process to communicate easily with its child
`process. Both processes (the parent and the child) continue execution at the
`instruction after the fork with one difference: The return code for the fork is
`zero for the new (child) process, whereas the (nonzero) process identifier of the
`child is returned to the parent.
`Typically, the execve system call is used after a fork by one of the two
`processes to replace the process’ memory space with a new program. The
`execve system call loads a binary file into memory (destroying the memory
`image of the program containing the execve system call) and starts its execution.
`In this manner, the two processes are able to communicate, and then to go their
`separate ways. The parent can then create more children, or, if it has nothing
`else to do while the child runs, it can issue a wait system call to move itself off
`the ready queue until the termination of the child.
`The DEC VMS operating system, in contrast, creates a new process, loads
`a specified program into that process, and starts it running. The Microsoft
`Windows NT operating system supports both models:
`the parent’s address
`space may be duplicated, or the parent may specify the name of a program
`for the operating system to load into the address space of the new process.
`
`4.3.2 Process Termination
`
`A process terminates when it finishes executing its last statement and asks the
`operating system to delete it by using the exit system call. At that point, the
`process may return data (output) to its parent process (via the wait system call).
`All of the resources of the process, including physical and virtual memory, open
`files, and I/O buffers, are deallocated by the operating system.
`There are additional circumstances when termination occurs. A process
`can cause the termination of another process via an appropriate system call (for
`example, abort). Usually, such a system call can be invoked by only the parent
`of the process that is to be terminated. Otherwise, users could arbitrarily kill
`each other’s jobs. Note that a parent needs to know the identities of its children.
`Thus, when one process creates a new process, the identity of the newly created
`process is passed to the parent.
`A parent may terminate the execution of one of its children for a variety of
`reasons, such as:
`
`o The child has exceeded its usage of some of the resources it has been
`allocated.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`100
`
`Chapter 4 Processes
`
`o The task assigned to the child is no longer required.
`
`0 The parent is exiting, and the operating system does not allow a child to
`continue if its parent terminates.
`
`To determine the first case, the parent must have a mechanism to inspect the
`state of its children.
`Many systems, including VMS, do not allow a child to exist if its parent
`has terminated.
`In such systems, if a process terminates (either normally or
`abnormally), then all its children must also be terminated. This phenomenon
`is referred to as cascading termination and is normally initiated by the operating
`system.
`To illustrate process execution and termination, let us consider again the
`UNIX system. In UNIX, a process may terminate by using the exit system call,
`and its parent process may wait for that event by using the wait system call.
`The wait system call returns the process identifier of a terminated child, so that
`the parent can tell which of the possibly many children has terminated. If the
`parent terminates, however, all the children are terminated by the operating
`system. Without a parent, UNIX does not know to whom to report the activities
`of a child.
`
`4.4 I Cooperating Processes
`
`The concurrent processes executing in the operating system may be either
`independent processes or cooperating processes. A process is independent if
`it cannot affect or be affected by the other processes executing in the system.
`Clearly, any process that does not share any data (temporary or persistent) with
`any other process is independent. On the other hand, a process is cooperating if it
`can affect or be affected by the other processes executing in the system. Clearly,
`any process that shares data with other processes is a cooperating process.
`There are several reasons for providing an environment that allows process
`cooperation:
`
`0 Information sharing: Since several users may be interested in the same
`piece of information (for instance, a shared file), we must provide an
`environment to allow concurrent access to these types of resources.
`
`0 Computation speedup: If we want a particular task to run faster, we must
`break it into subtasks, each of which will be executing in parallel with the
`others. Notice that such a speedup can be achieved only if the computer
`has multiple processing elements (such as CPUs or I/O channels).
`
`0 Modularity: We may want to construct the system in a modular fashion,
`dividing the system functions into separate processes, as was discussed in
`Chapter 3.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`4.4 Cooperating Processes
`
`101
`
`0 Convenience: Even an individual user may have many tasks to work on at
`one time. For instance, a user may be editing, printing, and compiling in
`parallel.
`
`Concurrent execution that requires cooperation among the processes requires
`mechanisms to allow processes to communicate with each other (Section 4.6),
`and to synchronize their actions (Chapter 6).
`let us consider the
`To illustrate the concept of cooperating processes,
`producer—consumer problem, which is a common paradigm for cooperating
`processes. A producer process produces information that is consumed by a
`consumer process. For example, a print program produces characters that are
`consumed by the printer driver. A compiler may produce assembly code, which
`is consumed by an assembler. The assembler, in turn, may produce object
`modules, which are consumed by the loader.
`To allow producer and consumer processes to run concurrently, we must
`have available a buffer of items that can be filled by the producer and emptied
`by the consumer. A producer can produce one item while the consumer is
`consuming another item. The producer and consumer must be synchronized,
`so that the consumer does not try to consume an item that has not yet been
`produced. In this situation, the consumer must wait until an item is produced.
`The unbounded-bufler producer—consumer problem places no practical limit
`on the size of the buffer. The consumer may have to wait for new items, but
`the producer can always produce new items. The bounded-bufler producer—
`consumer problem assumes that there is a fixed buffer size. In this case, the
`consumer must wait if the buffer is empty and the producer must wait if the
`buffer is full.
`
`The buffer may be either provided by the operating system through the
`use of IPC (Section 4.6), or explicitly coded by the application programmer
`with the use of shared memory. Let us illustrate a shared-memory solution
`to the bounded-buffer problem. The producer and consumer processes share
`the following variables:
`
`var 11;
`
`;
`type item =
`var bufi‘er: array [0..11—1] of item;
`in, out: 0..11—1;
`
`with the variables in and out initialized to the value 0. The shared buffer is
`implemented as a circular array with two logical pointers:
`in and out. The
`variable in points to the next free position in the buffer; out points to the first
`full position in the buffer. The buffer is empty when in = out; the buffer is full
`when in + 1 mod n = out.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`102
`
`Chapter 4 Processes
`
`The code for the producer and consumer processes follows. The no-op
`is a do-nothing instruction. Thus, while condition do no-op simply tests the
`condition repetitively until it becomes false.
`The producer process has a local variable nextp, in which the new item to
`be produced is stored:
`
`repeat
`
`produce an item in nextp
`
`while in+1 mod n = out do no—op;
`
`buflerfin] := nextp;
`in := in+1 mod 11;
`
`until false;
`
`The consumer process has a local variable nextc,
`consumed is stored:
`
`in which the item to be
`
`repeat
`while in = out do no—op;
`nextc := buffeflout];
`out := out+1 mod n;
`
`consume the item in nextc
`
`until false;
`
`This scheme allows at most 11—1 items in the buffer at the same time. We leave
`it as an exercise for you to provide a solution where n items can be in the buffer
`at the same time.
`
`In Chapter 6, we shall discuss in great detail how synchronization among
`cooperating processes can be implemented effectively in a shared-memory
`environment.
`
`4.5 I Threads
`
`Recall that a process is defined by the resources it uses and by the location
`at which it is executing. There are many instances, however, in which it
`would be useful for resources to be shared and accessed concurrently. This
`situation is similar to the case where a fork system call is invoked with a new
`program counter, or thread of control, executing within the same address space.
`This concept is so useful that several new operating systems are providing a
`mechanism to support it through a thread facility.
`
`Microsoft Corp. Exhibit 1055
`
`Microsoft Corp. Exhibit 1055
`
`

`

`4.5 Threads
`
`103
`
`4.5.1 Thread Structure
`
`A thread, sometimes called a lightweight process (LWP), is a basic unit of CPU
`utilization, and consists of a program counter, a register set, and a stack space.
`It shares with peer threads its code section, data section, and operating-system
`resources such as open files and signals, collectively known as a task. A
`traditional or heavyweight process is equal to a task with one thread. A task
`does nothing if no threads are in it, and a thread must be in exactly one
`task. The extensive sharing makes CPU switching among peer threads and
`the creation of threads inexpensive, compared with context switches among
`heavyweight processes. Although a thread context switch still requires a
`register set switch, no memory-management—related work need be done. Like
`any parallel processing environment, multithreading a process may introduce
`concurrency control problems that require the use of critical sections or locks.
`Also, some systems implement user-level
`threads in user-level libraries,
`rather than via system calls, so thread switching does not need to call the oper-
`ating system, and to cause an interrupt to the kernel. Switching between user-
`level threads can be done independently of the operating system and, therefore,
`very quickly. Thus, blocking a thread and switching to another thread is a
`reasonable solution to the problem of how a server can handle many requests
`efficiently. User—level threa