📄 http:^^www.cs.wisc.edu^~cs537-1^scheduling.html
字号:
Date: Tue, 05 Nov 1996 20:56:52 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Thu, 31 Oct 1996 21:38:53 GMTContent-length: 45007<html><head><title>CS 537 - Processes, Part III (Implementation) </title></head><body bgcolor="#ffffff"><h1>CS 537<br>Lecture Notes<br>Processes and Synchronization, Part III<br>Implementation of Processes</h1><hr><h2>Contents</h2><ul><li><!WA0><a href="#monitor_impl"> Implementing Monitors </a><li><!WA1><a href="#semaphore_impl"> Implementing Semaphores </a><li><!WA2><a href="#cs_impl"> Implementing Critical Sections </a><li><!WA3><a href="#short_term_sched"> Short-term Scheduling </a><hr><hr></ul><hr><h2> Implementing Processes </h2><p>We presented processes from the ``user's'' point of view bottom-up:starting with the process concept, then introducing semaphores asa way of synchronizing processes, and finally adding a higher-levelsynchronization facility in the form of monitors.We will now explain how to implement these things in the opposite order,starting with monitors, and finishing with the mechanism for makingprocesses run.<p>Tanenbaum makes a big deal out of showing that various synchronizationprimitives are equivalent to each other (Section 2.2.9).While this is true, it kind of misses the point.It is easy to implement semaphores with monitors (as you saw in thefirst part of Project 2), but that's not theway it usually works. Normally, semaphores (or something very likethem) are implemented using lower level facilities, and then theyare used to implement monitors.<a name="monitor_impl"> <h3> Implementing Monitors </h3> </a><p>Assuming that all we have is semaphores, and we would rather have monitors.We will assume that our semaphores have an extra operation, beyond the thestandards operations <samp><font color="0f0fff">up</font></samp> and <samp><font color="0f0fff">down</font></samp>:If <samp><font color="0f0fff">s</font></samp> is a semaphore, <samp><font color="0f0fff">s.awaited()</font></samp> returns <samp><font color="0f0fff">true</font></samp> ifany processes are currently waiting for the semaphore.This feature is not normally provided with semaphores because a racecondition limits its usefulness:By the time <samp><font color="0f0fff">s.awaited()</font></samp> returns <samp><font color="0f0fff">true</font></samp>, some other process may havedone <samp><font color="0f0fff">s.up()</font></samp>, making it <samp><font color="0f0fff">false</font></samp>.It so happens that this is not a problem for the way we will use semaphoresto implement monitors.<p>Since monitors are a language feature, they are implemented with thehelp of a compiler.In response to the keywords <samp><font color="0f0fff">monitor</font></samp>, <samp><font color="0f0fff">condition</font></samp>, <samp><font color="0f0fff">signal</font></samp>,<samp><font color="0f0fff">wait</font></samp>, and <samp><font color="0f0fff">notify</font></samp>, the compiler inserts little bits of codehere and there in the program.We will not worry about how the compiler manages to do that, but onlyconcern ourselves with what the code is and how it works.<p>The <samp><font color="0f0fff">monitor</font></samp> keyword says that there should be mutual exclusionbetween the methods of the <samp><font color="0f0fff">monitor</font></samp> class (the effect is similar tomaking every method a <samp><font color="0f0fff">synchronized</font></samp> method in Java).Thus the compiler creates a semaphore <samp><font color="0f0fff">mutex</font></samp> initialized to 1 and adds<pre><font color="0f0fff"> muxtex.down();</font></pre>to the head of each method. It also adds a chunk of code that wecall <samp><font color="0f0fff">exit</font></samp> (described below) to each place where a method may return--atthe end of the procedure, at each <samp><font color="0f0fff">return</font></samp> statement, at each point wherean exception may be thrown, at each place where a <samp><font color="0f0fff">goto</font></samp> might leave theprocedure (if the language has <samp><font color="0f0fff">goto</font></samp>s), etc. Finding all these returnpoints can be tricky in complicated procedures, which is why we want thecompiler to help us out.<p>When a process <samp><font color="0f0fff">signals</font></samp> or <samp><font color="0f0fff">notifies</font></samp> a condition variableon which some other process is waiting, we have a problem:We can't both of the processes immediately continue, since that wouldviolate the cardinal rule that there may never be more than one processactive in methods of the same monitor object at the same time.Thus we must block one of the processes: the signaller in the caseof <samp><font color="0f0fff">signal</font></samp> and the waiter in the case of <samp><font color="0f0fff">notify</font></samp>We call this semaphore <samp><font color="0f0fff">highPriority</font></samp> since processes blocked onit are given preference over processes blocked on <samp><font color="0f0fff">mutex</font></samp> tryingto get in ``form the outside.''The <samp><font color="0f0fff">highPriority</font></samp> semaphore is initialized to zero.<p>Each <samp><font color="0f0fff">condition</font></samp> variable <samp><font color="0f0fff">c</font></samp> becomes a semaphore <samp><font color="0f0fff">c_sem</font></samp>initialized to zero, and <samp><font color="0f0fff">c.wait()</font></samp> becomes<pre><font color="0f0fff"> if (highPriority.awaited()) highPriority.up(); else mutex.up(); c_sem.down();</font></pre>Before a process blocks on a condition variable, it lets some otherprocess go ahead, preferably one waiting on the <samp><font color="0f0fff">highPriority</font></samp>semaphore.<p>The operation <samp><font color="0f0fff">c.signal()</font></samp> becomes<pre><font color="0f0fff"> if (c_sem.awaited()) { c_sem.up(); highPriority.down(); }</font></pre>Notice that a <samp><font color="0f0fff">signal</font></samp> of a <samp><font color="0f0fff">condition</font></samp> that is not awaited hasno effect, and that a <samp><font color="0f0fff">signal</font></samp> of a <samp><font color="0f0fff">condition</font></samp> that is awaitedimmediately blocks the signaller.<p>Finally, the code for <samp><font color="0f0fff">exit</font></samp> which is placed at every return point, is<pre><font color="0f0fff"> if (highPriority.awaited()) highPriority.up(); else mutex.up();</font></pre>Note that this is the same code as for <samp><font color="0f0fff">c.wait()</font></samp>, except for thefinal <samp><font color="0f0fff">c_sem.down()</font></samp>.<p>In systems that use <samp><font color="0f0fff">notify</font></samp> (such as Java), <samp><font color="0f0fff">c.notify()</font></samp> isreplaced by<pre><font color="0f0fff"> if (c_sem.awaited() c_sem.up();</font></pre>In these systems, the code for <samp><font color="0f0fff">c.wait()</font></samp> also has to be modifiedto wait on the <samp><font color="0f0fff">highPriority</font></samp> semaphore after getting the semaphoreassociated with the condition:<pre><font color="0f0fff"> if (highPriority.awaited()) highPriority.up(); else mutex.up(); c_sem.down(); highPriority.down();</font></pre>No system offers both <samp><font color="0f0fff">signal</font></samp> and <samp><font color="0f0fff">notify</font></samp>.<p>This generic implementation of monitors can be optimized in special cases.First, note that a process that exits the monitor immediately afterdoing a <samp><font color="0f0fff">signal</font></samp> need not wait on the <samp><font color="0f0fff">highPriority</font></samp> semaphore.This turns out to be a very common occurrence, so it's worth optimizingfor this special case.If <samp><font color="0f0fff">signal</font></samp> is <em>only</em> allowed just before a return, the implementation can be further simplified:See Fig 2-16 on page 53 of Tanenbaum.Finally, note that we do not use the full generality of semaphores inthis implementation of monitors.The semaphore <samp><font color="0f0fff">mutex</font></samp> only takes on the values 0 and 1 (it is aso-called <em>binary semaphore</em>) and the other semaphores neverhave any value other than zero.<a name="semaphore_impl"> <h3> Implementing Semaphores </h3> </a><p>A simple-minded attempt to implement semaphores might look like this:<pre><font color="0f0fff"> class Semaphore { private int value; Semaphore(int v) { value = v; } public void down() { while (value == 0) {} value--; } public void up() { value++; } }</font></pre>There are two things wrong with this solution:First, as we have seen before, attempts to manipulate a shared variable withoutsynchronization can lead to incorrect results, evenif the manipulation is as simple as <samp><font color="0f0fff">value++</font></samp>.If we had monitors, we could make the modifications of <samp><font color="0f0fff">value</font></samp> atomicby making the class into a <samp><font color="0f0fff">monitor</font></samp> (or by making each method<samp><font color="0f0fff">synchronized</font></samp>), but remember that monitors are implemented withsemaphores, so we have to implement semaphores with something even moreprimitive.For now, we will assume that we have <em>critical sections</em>:If we bracket a section of code with <samp><font color="0f0fff">begin_cs</font></samp> and <samp><font color="0f0fff">end_cs</font></samp>,<pre><font color="0f0fff"> begin_cs do something; end_cs</font></pre>the code will execute atomically, as if it were protected by a semaphore<pre><font color="0f0fff"> mutex.down(); do something; mutex.up();</font></pre>where <samp><font color="0f0fff">mutex</font></samp> is a semaphore initialized to 1.Of course, we can't actually use a semaphore to implement semaphores!We will show how to implement <samp><font color="0f0fff">begin_cs</font></samp> and <samp><font color="0f0fff">end_cs</font></samp> in thenext section.<p>The other problem with our implementation of semaphores is that itincludes a <em>busy wait</em>.While <samp><font color="0f0fff">Semaphore.down()</font></samp> is waiting for <samp><font color="0f0fff">value</font></samp> to becomenon-zero, it is looping, continuously testing the value.Even if the waiting process is running on its own CPU, this busy waitingmay slow down other processes, since it is repeatedly accessing shared memory,thus interfering with accesses to that memory by other CPU's (a shared memoryunit can only respond to one CPU at a time).If there is only one CPU, the problem is even worse:Because the process calling <samp><font color="0f0fff">down()</font></samp> is running, another process thatwants to call <samp><font color="0f0fff">up()</font></samp> may not get a chance to run.What we need is some way to put a process to sleep.If we had semaphores, we could use a semaphore, but once again, we needsomething more primitive.<p>For now, let us assume that there is a data structure called a <samp><font color="0f0fff">PCB</font></samp>(short for ``Process Control Block'') that contains information about aprocess, and a procedure <samp><font color="0f0fff">swap_process</font></samp> that takes a pointer to a PCB asan argument.When <samp><font color="0f0fff">swap_process(pcb)</font></samp> is called, state of the currently running process(the one that called <samp><font color="0f0fff">swap_process</font></samp>) is saved in <samp><font color="0f0fff">pcb</font></samp> and the CPUstarts running the process whose state was previously stored in <samp><font color="0f0fff">pcb</font></samp>instead.Given <samp><font color="0f0fff">begin_cs</font></samp>, <samp><font color="0f0fff">end_cs</font></samp>, and <samp><font color="0f0fff">swap_process</font></samp>, thecomplete implementation of semaphores is quite simple (but very subtle!).<pre><font color="0f0fff"> class Semaphore { private PCB_queue waiters; // processes waiting for this Semaphore private int value; // if negative, number of waiters static PCB_queue ready_list; // list of all processes ready to run Semaphore(int v) { value = v; } public void down() { begin_cs value--; if (value < 0) { // The current process must wait // Find some other process to run. The ready_list must // be non-empty or there is a global deadlock. PCB pcb = ready_list.dequeue(); swap_process(pcb); // Now pcb contains the state of the process that called // down(), and the currently running process is some // other process. waiters.enqueue(pcb); } end_cs } public void up() { begin_cs value++; if (value <= 0) { // The value was previously negative, so there is // some process waiting. We must wake it up. PCB pcb = waiters.dequeue(); ready_list.enqueue(pcb); } end_cs } } // Semaphore</font></pre>The implementation of <samp><font color="0f0fff">swap_process</font></samp> is ``magic'':<pre><font color="0f0fff"> /* This procedure is probably really written in assembly language, * but we will describe it in Java. Assume the CPU's current * stack-pointer register is accessible as "SP". */ void swap_process(PCB pcb) { int new_sp = pcb.saved_sp; pcb.saved_sp = SP; SP = new_sp; }</font></pre>As we mentioned<!WA4><a href="http://www.cs.wisc.edu/~cs537-1/processes.html#using_what">earlier</a>,each process has its own <em>stack</em> with a <em>stack frame</em> foreach procedure that process has called but not yet completed.Each stack frame contains, at the very least, enough informationto implement a return from the procedure:the address of the instruction that called the procedure, and a pointerto the caller's stack frame.Each CPU devotes one of its registers (call it <samp><font color="0f0fff">SP</font></samp>) to point tothe current stack frame of the process it is currently running.When the CPU encounters a <samp><font color="0f0fff">return</font></samp> statement, it reloads itsSP and PC (program counter) registers from the stack frame.An approximate description in pseudo-Java might be something like this.<pre><font color="0f0fff"> class StackFrame { int callers_SP; int callers_PC; } StackFrame SP; // the current stack pointer // Here's how to do a "return" instruction_address return_point = SP.callers_PC; SP = SP.callers_SP; goto return_point;</font></pre>(of course, there isn't really a <samp><font color="0f0fff">goto</font></samp> statement in Java, and thiswould all be done in the hardware or a sequence of assembly languagestatements).<p>Suppose process <samp><font color="0f0fff">P0</font></samp> calls <samp><font color="0f0fff">swap_process(pcb)</font></samp>, where<samp><font color="0f0fff">pcb.saved_sp</font></samp> points to a stack frame representing a call of<samp><font color="0f0fff">swap_process</font></samp> by some other process <samp><font color="0f0fff">P1</font></samp>.The call to <samp><font color="0f0fff">swap_process</font></samp> creates a frame on <samp><font color="0f0fff">P0</font></samp>'s stackand makes <samp><font color="0f0fff">SP</font></samp> point to it.⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -