📄 http:^^www.cs.wisc.edu^~cs537-1^processes.html
字号:
Date: Tue, 05 Nov 1996 20:57:02 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Thu, 31 Oct 1996 21:38:53 GMTContent-length: 42275<html><head><title>CS 537 - Processes</title></head><body bgcolor="#ffffff"><h1>CS 537<br>Lecture Notes<br>Processes and Synchronization</h1><hr><h2>Contents</h2><ul><li><!WA0><!WA0><!WA0><!WA0><!WA0><a href="#using"> Using Processes </a><li><!WA1><!WA1><!WA1><!WA1><!WA1><a href="#using_what"> What is a Process? </a><li><!WA2><!WA2><!WA2><!WA2><!WA2><a href="#using_why"> Why Use Processes </a><li><!WA3><!WA3><!WA3><!WA3><!WA3><a href="#using_create"> Creating Processes </a><li><!WA4><!WA4><!WA4><!WA4><!WA4><a href="#using_states"> Process States </a><li><!WA5><!WA5><!WA5><!WA5><!WA5><a href="#using_sync"> Synchronization </a><ul><li><!WA6><!WA6><!WA6><!WA6><!WA6><a href="#race_conditions"> Race Conditions </a><li><!WA7><!WA7><!WA7><!WA7><!WA7><a href="#semaphores"> Semaphores </a><li><!WA8><!WA8><!WA8><!WA8><!WA8><a href="#bounded_buffer"> The Bounded Buffer Problem </a><li><!WA9><!WA9><!WA9><!WA9><!WA9><a href="#dining_philosophers">The Dining Philosophers </a><li><!WA10><!WA10><!WA10><!WA10><!WA10><a href="#monitors">Monitors </a><li><!WA11><!WA11><!WA11><!WA11><!WA11><a href="#messages"> Messages </a></ul></ul><hr><p>Tanenbaum mixes a presentation of the features of processes of interestto programmers creating concurrent programs with discussion of techniquesfor implementing them. The result is (at least to me) confusing.I will attempt to first present processes and associated features from theuser's point of view with as little concern as possible for questions abouthow they are implemented, and then turn to the question of implementingprocesses.<a name="using"> <h2> Using Processes </h2> </a><a name="using_what"> <h3> What is a Process? </h3> </a>A process is a ``little bug'' that crawls around on the program executingthe instructions it sees there.Normally (in so-called <em>sequential</em> programs) there is exactly oneprocess per program, but in <em>concurrent</em> programs, there may beseveral processes executing the same program.The details of what constitutes a ``process'' differ from system to system.The main difference is the amount of <em>private state</em> associated witheach process.Each process has its own <em>program counter</em>, the registerthat tells it where it is in the program.It also needs a place to store the return address when it calls a subroutine,so that two processes executing the same subroutine called from differentplaces can return to the correct calling points.Since subroutines can call other subroutines, each process needs its own<em>stack</em> of return addresses.<p>Processes with very little private memory are called <em>threads</em>or <em>light-weight processes</em>.At a minimum, each thread needs a program counter and a place tostore a stack of return addreses; all other values could be stored inmemory shared by all threads.At the other extreme, each process could have its own private memoryspace, sharing only the read-only program text with other processes.This essentially the way a Unix process works.Other points along the spectrum are possible.One common approach is to put the local variables of procedures on thesame private stack as the return addresses, but let all global variablesbe shared between processes.A stack <em>frame</em> holds all the local variables of a procedure, togetherwith an indication of where to return to when the procedure returns, andan indication of where the calling procedure's stack frame is stored.Java follows this approach.It has no global variables, but threads all share the same <em>heap</em>.The heap is the region of memory used to allocate objects in response to<samp><font color="0f0fff">new</font></samp>.In short, variables declared in procedures are local to threads,but objects are all shared.Of course, a thread can only ``see'' an object if it can reach that objectfrom its ``base'' object (the one containing its <samp><font color="0f0fff">run</font></samp> method, orfrom one of its local variables.<pre><font color="0f0fff"> class Foo implements Runnable { Object obj1, obj2; Foo(Object a) { obj1 = a; } public void run() { Object obj3 = new Object(); obj2 = new Object(); for(int i = 0; i < 1000; i++) // do something } } class Bar { static public void main(String args[]) { Object obj4 = new Object(); Runnable foo1 = new Foo(obj4); Thread t1 = new Thread(foo1); Runnable foo2 = new Foo(obj4); Thread t2 = new Thread(foo2); t1.start(); t2.start(); // so something here } }</font></pre>There are three treads in this program, the main thread and two childthreads created by it.Each child thread has its own stack frame for <samp><font color="0f0fff">Foo.run()</font></samp>,with space for <samp><font color="0f0fff">obj3</font></samp> and <samp><font color="0f0fff">i</font></samp>.Thus there are two copies of the variable <samp><font color="0f0fff">obj3</font></samp>, each of whichpoints to a different instance of <samp><font color="0f0fff">Object</font></samp>.Those objects are in the shared heap, but since one thread has noway of getting to the object created by the other thread, these objectsare effectively private.Similary, the objects pointed to by <samp><font color="0f0fff">obj2</font></samp> are effectively private.But both copies of <samp><font color="0f0fff">obj1</font></samp> and the copy of <samp><font color="0f0fff">obj4</font></samp> in the mainthread all point to the same (shared) object.<p>Other names sometimes used for processes are <em>job</em> or <em>task</em>.<p>It is possible to combine threads with processes in the same system.For example, when you run Java under Unix, each Java program is run ina separate Unix process.Unix processes share very little with each other, but the Java threadsin one Unix process share everything but their private stacks.<a name="using_why"> <h3> Why Use Processes </h3> </a><p>Processes are basically just a programming convenience, but in some settingsthey are such a great convenience, it would be nearly impossible to writethe program without them.A process allows you to write a single thread of code to get some taskdone, without worrying about the possibilty that it may have to wait forsomething to happen along the way.Examples:<dl><dt>A server providing services to others.<dd>One thread for each client.<dt>A timesharing system.<dd>One thread for each logged-in user.<dt>A real-time control computer controlling a factory.<dd>One thread for each device that needs monitoring.<dt>Networking.<dd>One thread for each connection.</dl><a name="using_create"> <h3> Creating Processes </h3> </a><p>When a new process is created, it needs to know where to start executing.In Java, a thread is given an object when it is created.When it is started, it starts execution at the beginning of the <samp><font color="0f0fff">run</font></samp>method of that object.In Unix, a new process is started with the <samp><font color="0f0fff">fork()</font></samp> command.It starts execution at the statement immediately following the <samp><font color="0f0fff">fork()</font></samp>call.After the call, both the parent (the process that called <samp><font color="0f0fff">fork()</font></samp>)and the child are both executing at the same point in the program.The child is given its own memory space, which is initialized with<em>an exactly copy</em> of the memory space (globals, stack, heap objects)of the parent.Thus the child looks like an exact clone of the parent, and indeed, it'shard to tell them apart.The only difference is that <samp><font color="0f0fff">fork()</font></samp> returns 0 in the child, but anon-zero value in the parent.<pre><font color="0f0fff"> char *str; main() { int j; str = "the main program "; j = f(); cout << str << j << endl; } void f() { int k; k = fork(); if (k == 0) { str = "the child has value "; return 10; } else { str = "the parent has value "; return 39; } }</font></pre>This program starts with one process executing <samp><font color="0f0fff">main()</font></samp>.This process calls <samp><font color="0f0fff">f()</font></samp>, and inside <samp><font color="0f0fff">f()</font></samp> it calls <samp><font color="0f0fff">fork()</font></samp>.Two processes appear to return from <samp><font color="0f0fff">fork()</font></samp>, a <em>parent</em> anda <em>child</em> process.Each has its own copy of the global global variable <samp><font color="0f0fff">str</font></samp> and itsown copy of the stack, which contains a frame for <samp><font color="0f0fff">main</font></samp> withvariable <samp><font color="0f0fff">j</font></samp> and a frame for <samp><font color="0f0fff">f</font></samp> with variable <samp><font color="0f0fff">k</font></samp>.After the return from <samp><font color="0f0fff">fork</font></samp> the parent sets its copy of <samp><font color="0f0fff">k</font></samp> toa non-zero value, while the child sets its copy of <samp><font color="0f0fff">k</font></samp> to zero.Each process then assigns a different string to its copy of the global <samp><font color="0f0fff">str</font></samp>and returns a different value, which is assigned to the process' own copy of<samp><font color="0f0fff">j</font></samp>.Two lines are printed:<pre><font color="0f0fff"> the parent has value 39 the child has value 10</font></pre>(actually, the lines might be intermingled).<a name="using_states"> <h3> Process States </h3> </a>Once a process is started, it is either <em>runnable</em> or <em>blocked</em>.It can become blocked by doing something that explicitly blocks itself (such as<samp><font color="0f0fff">wait()</font></samp>) or by doing something that implicitly block it (such as a <samp><font color="0f0fff">read()</font></samp> request).In some systems, it is also possible for one process to block anther (e.g.,<samp><font color="0f0fff">Thread.suspend()</font></samp> in Java).A runnable process is either <em>ready</em> or <em>running</em>.There can only be as many running processes as there are CPUs. One of theresponsibilities of the operating system, called <em>short-term scheduling</em>is to switch processes between <em>ready</em> and <em>running</em> state.<a name="using_sync"> <h3> Synchronization </h3> </a><a name="race_conditions"> <h4> Race Conditions </h4> </a>Consider the following extremely simple procedure<pre><font color="0f0fff"> void deposit(int amount) { balance += amount; }</font></pre>(where we assume that <samp><font color="0f0fff">balance</font></samp> is a shared variable.If two processes try to call <samp><font color="0f0fff">deposit</font></samp> concurrently, something very badcan happen.The single statment <samp><font color="0f0fff">balance += amount</font></samp> is really implmented, on mostcomputers, buy a sequence of instructions such as<pre><font color="0f0fff"> Load Reg, balance Add Reg, amount Store Reg, balance</font></pre>Suppose process P1 calls <samp><font color="0f0fff">deposit(10)</font></samp> and process P2 calls <samp><font color="0f0fff">deposit(20)</font></samp>.If one completes before the other starts, the combined effect is toadd 30 to the balance, as desired.However, suppose the calls happen at exactly the same time, and theexecutions are interleaved. Suppose the initial balance is 100, andthe two processes run on different CPUs.One possible result is<pre><font color="0f0fff"> P1 loads 100 into its register P2 loads 100 into its register P1 adds 10 to its register, giving 110 P2 adds 20 to its register, giving 120 P1 stores 110 in balance P2 stores 120 in balance</font></pre>and the net effect is to add only 20 tot he balance!<p>This kind of bug, which only occurs under certain timing conditions, iscalled a <em>race condition</em>.It is an extremely difficult kind of bug to track down (since itmay disappear when you try to debug it) and may be nearlyimpossible to detect from testing (since it may occur only extremely rarely).The only way to deal with race conditions is through very carefulcoding.To avoid these kinds of problems, systems that support processes alwayscontain constructs called<em>synchronization primatives</em>.<a name="semaphores"> <h4> Semaphores </h4> </a><p>One of the earliest and simplest synchronization primitives is the<em>semaphore</em>.We will consider later how semaphores are implemented, but for nowwe can treat them like a Java object that hides an integer value andonly allows three operations:initialization to a specified value,increment,ordecrement.<!WA12><!WA12><!WA12><!WA12><!WA12><a href="#footnote"><sup>1</sup></a><pre><font color="0f0fff"> class Semaphore { private int value; public Semaphore(int v) { value = v; } public void up() { /* ... */ } public void down() { /* ... */ }; }</font></pre>There is no operation to read the current value!There two bits of ``magic'' that make this seemingly useless class extremelyuseful:<ol>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -