duality.ps.ps

国外开发的著名分布式操作系统mach的有关代码文章

63 W( on one of the pages which both clients have been reading.  Since)64 W
7200 29368 MT
(the writer's kernel already has)
19 W( the data page to satisfy the fault, it makes a)18 W
/Times-Italic SF
37356 XM
(pager_data_unlock)SH
/Times-Roman SF
45401 XM
(call on X, asking that)18 W
7200 30745 MT
(write permission be granted.  Before allowing write permission, the shared memory server must)
26 W( invalidate all of the)27 W
7200 32122 MT
(other uses of this page; it does so using the)82 W
/Times-Italic SF
25408 XM
(pager_flush_request)SH
/Times-Roman SF
33962 XM
(call. Once)
414 W( all readers have been invalidated,)
82 W( the)81 W
7200 33499 MT
(server grants write access to the first client using)SH
/Times-Italic SF
26946 XM
(pager_data_lock)SH
/Times-Roman SF
33973 XM
(with no lock.)SH
12 /Times-Bold AF
7200 37183 MT
(5. Implementation Details)SH
10 /Times-Roman AF
8200 38560 MT
(Four basic data structures are used within the Mach kernel to implement the external)
200 W( memory management)201 W
7200 39937 MT
(interface:)SH
/Times-Italic SF
11476 XM
(address maps)SH
/Times-Roman SF
(,)SH
/Times-Italic SF
17448 XM
(memory object)SH
/Times-Roman SF
23613 XM
(structures,)SH
/Times-Italic SF
28001 XM
(resident page)SH
/Times-Roman SF
33667 XM
(structures, and a set of)SH
/Times-Italic SF
42887 XM
(pageout queues)SH
/Times-Roman SF
(.)SH
11 /Times-Bold AF
7200 43554 MT
(5.1. Address Maps)SH
10 /Times-Roman AF
8200 44931 MT
(As in Accent, a task)62 W
/Times-Italic SF
16786 XM
(address map)61 W
/Times-Roman SF
22241 XM
(is a directory mapping each of many valid address ranges to a memory object)61 W
7200 46308 MT
(and offset within that memory object.  Additional information stored for each range includes protection)
250 W( and)251 W
7200 47685 MT
(inheritance information.)SH
8200 50164 MT
(To account for sharing)
73 W( through inheritance, Mach address maps are two-level.  A task address space consists of)72 W
7200 51541 MT
(one top-level address map; instead of references to memory objects directly, address map entries refer to)
101 W( second-)102 W
7200 52918 MT
(level)SH
/Times-Italic SF
9494 XM
(sharing maps)100 W
/Times-Roman SF
(. Changes)
450 W( in per-task attributes, such as protection and inheritance, are)
100 W( stored in the top-level)99 W
7200 54295 MT
(map. Changes)
419 W( to the virtual memory represented by a map entry are reflected in the sharing map; for example, a)85 W
/Times-Italic SF
7200 55672 MT
(vm_write)SH
/Times-Roman SF
11180 XM
(operation into a)
8 W( region shared by more than one task would take place in the sharing map referenced by all)7 W
7200 57049 MT
(of their task maps.)SH
8200 59528 MT
(It is then the second-level)
130 W( sharing maps that refer to memory object structures.  As an optimization, top-level)131 W
7200 60905 MT
(maps may contain direct references to memory object structures if no sharing has taken place.)SH
8200 63384 MT
(When a)182 W
/Times-Italic SF
11896 XM
(vm_allocate_with_pager)SH
/Times-Roman SF
22272 XM
(call is processed, the Mach kernel)
182 W( looks up the given memory object port,)181 W
7200 64761 MT
(attempting to find an associated internal memory object structure; if none exists,)
39 W( a new internal structure is created,)40 W
7200 66138 MT
(and the)68 W
/Times-Italic SF
10502 XM
(pager_init)SH
/Times-Roman SF
14987 XM
(call performed.  Once)
68 W( a memory object structure is found, it is inserted into the \050top-level\051 task)67 W
10800 50 7200 69428 UL
6 SS 
8000 70767 MT
(9)SH
8 SS 
8300 71076 MT
(The choice to prevent writing is made here to simplify the example.  It may be more practical to allow)
12 W( the first client write access, and then to)13 W
7200 72000 MT
(revoke it later.)SH
ES
%%Page: 12 13
BS
0 SI
10 /Times-Roman AF
30100 4286 MT
(12)SH
7200 7886 MT
(address map.  Note that the sharing)
105 W( semantics are different than in the inheritance case in that no sharing map is)106 W
7200 9263 MT
(involved; an attempt to)5 W
/Times-Italic SF
16720 XM
(vm_write)SH
/Times-Roman SF
20697 XM
(one mapping of the memory object would merely replace that mapping, rather)
5 W( than)4 W
7200 10640 MT
(reflecting it in other tasks that have also mapped that memory object.)SH
11 /Times-Bold AF
7200 14257 MT
(5.2. Virtual Memory Object Structures)SH
10 /Times-Roman AF
8200 15634 MT
(An internal)12 W
/Times-Italic SF
13001 XM
(memory object)12 W
/Times-Roman SF
19190 XM
(structure is)
12 W( kept for each memory object used in an address map \050or for which the data)13 W
7200 17011 MT
(manager has advised that)
55 W( caching is permitted\051.  Components of this structure include the ports used to refer to the)54 W
7200 18388 MT
(memory object, its size, the number of address map references to the object,)
51 W( and whether the kernel is permitted to)52 W
7200 19765 MT
(cache the memory object when no address map references remain.)SH
8200 22244 MT
(A list of resident page structures is attached to the object in order)
21 W( to expediently release the pages associated with)20 W
7200 23621 MT
(an object when it is destroyed.)SH
11 /Times-Bold AF
7200 27238 MT
(5.3. Resident Memory Structures)SH
10 /Times-Roman AF
8200 28615 MT
(Each)SH
/Times-Italic SF
10632 XM
(resident page)183 W
/Times-Roman SF
16664 XM
(structure corresponds to a page of physical memory, and vice)
183 W( versa.  The resident page)184 W
7200 29992 MT
(structure records the memory object and offset into the object, along with the access)
75 W( permitted to that page by the)74 W
7200 31369 MT
(data manager.  Reference and)
65 W( modification information provided by the hardware is also saved here.  An interface)66 W
7200 32746 MT
(providing fast resident page lookup by memory object and offset \050)11 W
/Times-Italic SF
(virtual to physical table)11 W
/Times-Roman SF
(\051 is)
11 W( implemented as a hash)10 W
7200 34123 MT
(table chained through the resident page structures.)SH
11 /Times-Bold AF
7200 37740 MT
(5.4. Page Replacement Queues)SH
10 /Times-Roman AF
8200 39117 MT
(Page replacement uses several)176 W
/Times-Italic SF
21289 XM
(pageout queues)176 W
/Times-Roman SF
28140 XM
(linked through the resident page structures.)
176 W( An)603 W
/Times-Italic SF
48797 XM
(active)SH
/Times-Roman SF
51612 XM
(queue)SH
7200 40494 MT
(contains all of)
8 W( the pages currently in use, in least-recently-used order.  An)7 W
/Times-Italic SF
37092 XM
(inactive)SH
/Times-Roman SF
40515 XM
(queue is used to hold pages being)7 W
7200 41871 MT
(prepared for pageout.  Pages not caching any data are kept on a)SH
/Times-Italic SF
32748 XM
(free)SH
/Times-Roman SF
34553 XM
(queue.)SH
11 /Times-Bold AF
7200 45488 MT
(5.5. Fault Handling)SH
10 /Times-Roman AF
8200 46865 MT
(The Mach page fault handler is the)
80 W( hub of the Mach virtual memory system.  The kernel fault handler is called)81 W
7200 48242 MT
(when the hardware tries to)
122 W( reference a page for which there no valid mapping or for which there is a protection)121 W
7200 49619 MT
(violation. The)
250 W( fault handler has several responsibilities:)SH
/Symbol SF
8990 51072 MT
(\267)SH
/Times-Italic SF
9700 XM
(validity and protection)22 W
/Times-Roman SF
19127 XM
(- The)
22 W( kernel determines whether the faulting thread has the desired access to the)23 W
9700 52177 MT
(address, by performing a lookup)
30 W( in its task's address map.  This lookup also results in a memory object)29 W
9700 53282 MT
(and offset.)SH
/Symbol SF
8990 55040 MT
(\267)SH
/Times-Italic SF
9700 XM
(page lookup)122 W
/Times-Roman SF
15110 XM
(- The kernel attempts to find an entry for a cached page in the)123 W
/Times-Italic SF
41770 XM
(virtual to physical)123 W
/Times-Roman SF
49667 XM
(hash)SH
9700 56145 MT
(table; if the page is not present, the kernel must request the data from the data manager.)SH
/Symbol SF
8990 57903 MT
(\267)SH
/Times-Italic SF
9700 XM
(copy-on-write)SH
/Times-Roman SF
15644 XM
(- Once the page has been located, the kernel determines)
84 W( if a copy-on-write operation is)83 W
9700 59008 MT
(needed. If)
392 W( the task desires write permission and the page has not yet been copied, then a new page is)71 W
9700 60113 MT
(created as a copy of the original.  If necessary, the kernel also creates a new shadow object.)SH
/Symbol SF
8990 61871 MT
(\267)SH
/Times-Italic SF
9700 XM
(hardware validation)36 W
/Times-Roman SF
18217 XM
(- Finally, the kernel informs the hardware physical map module of the new virtual)35 W
9700 62976 MT
(to physical mapping.)SH
8200 65455 MT
(With the exception of the hardware validation, all)
183 W( of these steps are implemented in a machine-independent)184 W
7200 66832 MT
(fashion.)SH
ES
%%Page: 13 14
BS
0 SI
10 /Times-Roman AF
30100 4286 MT
(13)SH
12 /Times-Bold AF
7200 8004 MT
(6. The Problems of External Memory Management)SH
11 SS 
7200 11621 MT
(6.1. Types of Memory Failures)SH
10 /Times-Roman AF
8200 12998 MT
(While the functionality of external)
233 W( memory management can be a powerful tool in the hands of a careful)232 W
7200 14375 MT
(application, it can also raise several robustness and security problems if improperly used.  Some of the problems are:)SH
/Symbol SF
8990 15828 MT
(\267)SH
/Times-Italic SF
9700 XM
(Data manager doesn't return data)124 W
/Times-Roman SF
(. Threads)
498 W( may now become blocked waiting for data supplied)
124 W( by)125 W
9700 16933 MT
(another user task,)
229 W( which does not respond promptly.  The tight interconnection between IPC and)228 W
9700 18038 MT
(memory management makes it difficult \050or merely)
81 W( expensive\051 to determine whether the source of any)82 W
9700 19143 MT
(memory is hostile prior to attempting to access that memory.)SH
/Symbol SF
8990 20901 MT
(\267)SH
/Times-Italic SF
9700 XM
(Data manager fails to free flushed)
10 W( data)9 W
/Times-Roman SF
(. A)
268 W( data manager may wreak havok with the pageout process by)9 W
9700 22006 MT
(failing to promptly release memory following pageout of dirty pages.)SH
/Symbol SF
8990 23764 MT
(\267)SH
/Times-Italic SF
9700 XM
(Data manager floods the cache)83 W
/Times-Roman SF
(. This)
416 W( is rather similar in nature)
83 W( to a data manager which fails to free)84 W
9700 24869 MT
(data, but is easier to detect and prevent.)SH
/Symbol SF
8990 26627 MT
(\267)SH
/Times-Italic SF
9700 XM
(Data manager changes data)13 W
/Times-Roman SF
(. A)
276 W( malicious data manager may change)
13 W( the value of its data on each cache)12 W
9700 27732 MT
(refresh. While)
802 W( this is an advantage for shared memory applications, it is a serious problem)
276 W( to)277 W
9700 28837 MT
(applications which receive \050virtual copied\051 data in a message.)SH
/Symbol SF
8990 30595 MT
(\267)SH
/Times-Italic SF
9700 XM
(Data manager backs its own data)62 W
/Times-Roman SF
(. Deadlock)
374 W( may occur if a data manager becomes blocked in)
62 W( a page)61 W
9700 31700 MT
(fault waiting for data which it provides.)SH
8200 34179 MT
(Fortunately, there are several techniques that minimize these potential problems:)SH
/Symbol SF
8990 35632 MT
(\267)SH
/Times-Roman SF
9700 XM
(A task may use the)15 W
/Times-Italic SF
17635 XM
(vm_regions)SH
/Times-Roman SF
22566 XM
(call to obtain information about)
15 W( the makeup of its address space.  While)16 W
9700 36737 MT
(this enables a task to avoid deadlock on memory it provides, it does not prevent two or more tasks)
19 W( from)18 W
9700 37842 MT
(deadlocking on memory provided by the others.)SH
/Symbol SF
8990 39600 MT
(\267)SH
/Times-Roman SF
9700 XM
(The use of multiple threads to handle data)
6 W( requests also aids in deadlock prevention; one thread within a)7 W
9700 40705 MT
(task may service a data request for another thread in that task.)SH
/Symbol SF
8990 42463 MT
(\267)SH
/Times-Roman SF
9700 XM
(Server tasks which cannot tolerate changing data, or which must ensure that all of)
38 W( the necessary data is)37 W
9700 43568 MT
(available, may use a separate thread to copy that data to safe memory before proceeding.)SH
11 /Times-Bold AF
7200 47185 MT
(6.2. Handling Memory Failures)SH
10 SS 
7200 50015 MT
(6.2.1. Analogy to Communication Failure)SH
/Times-Roman SF
8200 51392 MT
(The potential problems)
57 W( associated with external data managers are strongly analogous to communication failure.)58 W
7200 52769 MT
(This is actually not surprising since external data managers)
117 W( are implemente