unit 6-87%.htm

卡耐基梅隆大学ssd6系统级程序设计教材

style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>Trap instructions are most commonly used to implement <i>system calls</i>,
the requests for services that an application makes to the operating system.
System calls are slow because they change address spaces and check parameters.
Program designers can minimize the overhead of system calls by trying to
perform a large amount of work per call. This is especially true for input and
output: if every read or write transfers a large amount of data to be
processed, then the relative overhead of the system calls will be small. If
only a few bytes are transferred per call, then the program may spend more time
on the calling overhead than on processing the data.<o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>Another efficiency measure is to eliminate polling. To poll is to
repeatedly test whether some condition has become true. For example, a process
might run every few milliseconds and test whether any input is available and
whether it is time to produce some output. Polling can be wasteful because it
may take a number of system calls to wake up, read the time, test for input,
etc.<o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>To avoid the need for polling, operating systems always provide
mechanisms for applications to wait for various events, including the
availability of input data and the passage of time. A good example of this is
the Unix select() call. In Unix, every input (file, network socket, mouse,
keyboard, etc.) is represented by a number called the <i>file descriptor</i>.
To invoke select(), you pass in a set of file descriptors and a timeout value.
The caller then &quot;blocks&quot; (that is, pauses) until <i>any</i> file has
data available or until the timeout expires, whichever comes first. In this
way, the application can block until there is actual work to do. This is
sometimes called <i>event-driven programming.</i><o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>In summary, each application executes in its own address space, allowing
most instructions to run at full speed without the danger that errors will
affect other applications or crash the operating system. To interact with the
operating system, typically to perform input/output operations, applications
make system calls using a hardware-supported trap instruction. Because system
calls must switch address spaces and check parameters carefully, system calls
are much more expensive than ordinary procedure calls. Programmers can reduce
the overhead of system calls for input and output by transferring relatively
large amounts of data with each call.<o:p></o:p></span></p>

<p class=MsoNormal align=left style='margin-top:12.0pt;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:10.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>&copy; Copyright 1999-2005 iCarnegie, Inc. All rights reserved.<o:p></o:p></span></p>

<b><span lang=EN-US style='font-size:18.0pt;font-family:SimSun;mso-bidi-font-family:
SimSun;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:
AR-SA'><br clear=all style='page-break-before:always'>
</span></b>

<h2><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>6.1.3 Context Switching<o:p></o:p></span></h2>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>In time-sharing, each running instance of a program is called a process.
The hardware processor executes the instructions and manipulates the data of
one process for a period of time. Then, the entire state of the processor for
that process is carefully saved. The state information that is saved includes
the address of the next instruction to be executed and the values of all
registers. Then, after other processes have been run for awhile, the saved
register values of the first process are restored and the execution of that
process resumes.<o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>The act of saving and restoring all of the processor state for one
process and restoring the state for another is called a <i>context switch</i>.
Even though context switches are supported in part by hardware, they are
expensive operations because many values are read and written, and because
control passes first to the operating system and then to another process.<o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>Context switches are made after a process has run for some period of
time. A context switch can also occur if a process performs an input/output
operation that takes time to complete. Rather than just waiting for the I/O to
complete, the operating system runs some other process in the meantime.<o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>You may wonder how an I/O can complete if the processor is running
another process. Often, hardware devices such as network and disk interfaces
can perform time-consuming operations without direct support from the
processor. They typically <i>interrupt</i> the processor when the operation
completes. (An interrupt is a &quot;lightweight&quot; context switch that saves
a few critical registers and calls an <i>interrupt handler</i> subroutine in
the operating system to deal with the interrupting hardware. An interrupt is
much like a trap, described earlier, except that an interrupt can occur at any
time, whereas the time at which a trap occurs is determined by the compiler.)<o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>Processes can be in several states. The process that is being executed
is in the <i>running state</i>. Any processes that are ready to run but not
running are in the <i>ready state</i>. Finally, any process that is
blocked-because it's waiting for I/O completion, a signal from another process,
or a timed wakeup-is in the <i>suspended</i> state. The typical state
transitions are shown in the following diagram:<o:p></o:p></span></p>

<p class=MsoNormal align=center style='text-align:center;mso-pagination:widow-orphan'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><!--[if gte vml 1]><v:shape id="_x0000_i1026" type="#_x0000_t75" alt="Transition states"
 style='width:383.25pt;height:183pt'>
 <v:imagedata src="Unit%206_files/image002.jpg" o:href="http://www.icarnegie.com/content/SSD/SSD6/2.0/normal/pg-os-interaction/pg-time-sharing/pg-context-switching/states.jpg"/>
</v:shape><![endif]--><![if !vml]><img border=0 width=511 height=244
src="Unit%206_files/image002.jpg" alt="Transition states" v:shapes="_x0000_i1026"><![endif]><o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-outline-level:3'><b><span
lang=EN-US style='font-size:13.5pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>Scheduling<o:p></o:p></span></b></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>When a context switch occurs, the operating system has an opportunity to
select which process will run next. All sorts of criteria can be used for this
selection. The simplest scheme is called &quot;round robin,&quot; which means
the ready processes are run in some fixed, cyclical order. Each process gets
its fair share of the CPU.<o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>Sometimes, processes have priorities and the process with the highest
priority is run next. This is useful for favoring important or time-critical
processes over background tasks. Some schedulers try to optimize throughput by
noticing processing patterns. Schedulers on uniprocessors sometimes favor
processes that run for short times and then block on an I/O operation. (This strategy
might keep I/O devices busier.) Schedulers can also try to avoid too much
virtual memory paging. Schedulers on multiprocessors (computers with more than
one CPU) sometimes try to schedule cooperating or communicating processes at
the same time for better performance. The list of possible scheduling
strategies is much longer than we have space to describe.<o:p></o:p></span></p>

<p class=MsoNormal align=left style='margin-top:12.0pt;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:10.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>&copy; Copyright 1999-2005 iCarnegie, Inc. All rights reserved.<o:p></o:p></span></p>

<b><span lang=EN-US style='font-size:18.0pt;font-family:SimSun;mso-bidi-font-family:
SimSun;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:
AR-SA'><br clear=all style='page-break-before:always'>
</span></b>

<h2><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>6.2 Threads<o:p></o:p></span></h2>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l1 level1 lfo5;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>&middot;<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:ContentByName('pg-threads-and-processes');">6.2.1 Threads vs.
Processes</a> <o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l1 level1 lfo5;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>&middot;<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:ContentByName('pg-thread-use');">6.2.2 Applications of Threads</a>
<o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l1 level1 lfo5;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>&middot;<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:ContentByName('pg-reentrant-code');">6.2.3 Reentrant Code</a> <o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l1 level1 lfo5;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>&middot;<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:ContentByName('pg-synchronous-access');">6.2.4 Concurrent Data
Access</a> <o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l1 level1 lfo5;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>&middot;<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:ContentByName('pg-scheduling');">6.2.5 Scheduling Effects</a> <o:p></o:p></span></p>

<p class=MsoNormal align=left style='margin-top:12.0pt;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:10.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>&copy; Copyright 1999-2005 iCarnegie, Inc. All rights reserved.<o:p></o:p></span></p>

<h2><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>6.2.1 Threads vs. Processes<o:p></o:p></span></h2>

<p><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>Processes are ideal for running independent programs
but sometimes we want to use multiple processes in a single program. For
example, in a mail program, one process can retrieve and deliver mail (often a
slow activity) while another process manages the user interface (which should
be quick and responsive). While it is possible to use full-scale processes with
separate address spaces, it is often more convenient to share a single address
space among multiple process-like entities called <i>threads</i>. A thread is
essentially the same as a process except that threads share a single virtual
address space. (This definition is not completely standard-for example, some
operating systems allow multiple processes to share an address space.)<o:p></o:p></span></p>

<p><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>There are a few advantages to threads, at least in
some applications. First, there is considerable cost to creating a virtual
address space and changing address spaces with each context switch. Threads can
eliminate the need to change address spaces after a context switch. Secondly,
and perhaps more importantly, due to the fact that threads share memory, they
can share data much more easily. For example, an image-processing program that
wants to filter a large image in the background can simply point the background
thread at the image. This is much simpler than saving the image to a file or
exchanging the image data via inter-process messages.<o:p></o:p></span></p>

<p class=footer><span lang=EN-US style='font-family:"Times New Roman";
color:black;mso-ansi-language:EN-US'>&copy; Copyright 1999-2005 iCarnegie, Inc.
All rights reserved.<o:p></o:p></span></p>

<b><span lang=EN-US style='font-size:18.0pt;font-family:SimSun;mso-bidi-font-family:
SimSun;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:
AR-SA'><br clear=all style='page-break-before:always'>
</span></b>

<h2><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>6.2.2 Applications of Threads<o:p></o:p></span></h2>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l5 level1 lfo6;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>&middot;<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="http://www.icarnegie.com/content/SSD/SSD6/2.0/normal/pg-os-interaction/pg-threads/pg-thread-use/pg-thread-use.html#bg#bg">Background
Processing</a> <o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l5 level1 lfo6;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>&middot;<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="http://www.icarnegie.com/content/SSD/SSD6/2.0/normal/pg-os-interaction/pg-threads/pg-thread-use/pg-thread-use.html#async#async">Asynchronous
I/O</a> <o:p></o:p></span></p>

<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l5 level1 lfo6;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-