1 .\" Copyright (c) 1986 The Regents of the University of California.
2 .\" All rights reserved.
4 .\" Redistribution and use in source and binary forms, with or without
5 .\" modification, are permitted provided that the following conditions
7 .\" 1. Redistributions of source code must retain the above copyright
8 .\" notice, this list of conditions and the following disclaimer.
9 .\" 2. Redistributions in binary form must reproduce the above copyright
10 .\" notice, this list of conditions and the following disclaimer in the
11 .\" documentation and/or other materials provided with the distribution.
12 .\" 3. All advertising materials mentioning features or use of this software
13 .\" must display the following acknowledgement:
14 .\" This product includes software developed by the University of
15 .\" California, Berkeley and its contributors.
16 .\" 4. Neither the name of the University nor the names of its contributors
17 .\" may be used to endorse or promote products derived from this software
18 .\" without specific prior written permission.
20 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 .\" @(#)1.t 5.1 (Berkeley) 4/16/91
33 .\" $FreeBSD: src/share/doc/papers/newvm/1.t,v 1.6 1999/08/28 00:18:13 peter Exp $
34 .\" $DragonFly: src/share/doc/papers/newvm/1.t,v 1.2 2003/06/17 04:36:56 dillon Exp $
37 Motivations for a New Virtual Memory System
39 The virtual memory system distributed with Berkeley UNIX has served
40 its design goals admirably well over the ten years of its existence.
41 However the relentless advance of technology has begun to render it
43 This section of the paper describes the current design,
44 points out the current technological trends,
45 and attempts to define the new design considerations that should
46 be taken into account in a new virtual memory design.
48 Implementation of 4.3BSD virtual memory
50 All Berkeley Software Distributions through 4.3BSD
51 have used the same virtual memory design.
52 All processes, whether active or sleeping, have some amount of
53 virtual address space associated with them.
54 This virtual address space
55 is the combination of the amount of address space with which they initially
56 started plus any stack or heap expansions that they have made.
57 All requests for address space are allocated from available swap space
58 at the time that they are first made;
59 if there is insufficient swap space left to honor the allocation,
60 the system call requesting the address space fails synchronously.
61 Thus, the limit to available virtual memory is established by the
62 amount of swap space allocated to the system.
64 Memory pages are used in a sort of shell game to contain the
65 contents of recently accessed locations.
66 As a process first references a location
67 a new page is allocated and filled either with initialized data or
68 zeros (for new stack and break pages).
69 As the supply of free pages begins to run out, dirty pages are
70 pushed to the previously allocated swap space so that they can be reused
71 to contain newly faulted pages.
72 If a previously accessed page that has been pushed to swap is once
73 again used, a free page is reallocated and filled from the swap area
74 [Babaoglu79], [Someren84].
76 Design assumptions for 4.3BSD virtual memory
78 The design criteria for the current virtual memory implementation
80 At that time the cost of memory was about a thousand times greater per
81 byte than magnetic disks.
82 Most machines were used as centralized time sharing machines.
83 These machines had far more disk storage than they had memory
84 and given the cost tradeoff between memory and disk storage,
85 wanted to make maximal use of the memory even at the cost of
86 wasting some of the disk space or generating extra disk I/O.
88 The primary motivation for virtual memory was to allow the
89 system to run individual programs whose address space exceeded
90 the memory capacity of the machine.
91 Thus the virtual memory capability allowed programs to be run that
92 could not have been run on a swap based system.
93 Equally important in the large central timesharing environment
94 was the ability to allow the sum of the memory requirements of
95 all active processes to exceed the amount of physical memory on
97 The expected mode of operation for which the system was tuned
98 was to have the sum of active virtual memory be one and a half
99 to two times the physical memory on the machine.
101 At the time that the virtual memory system was designed,
102 most machines ran with little or no networking.
103 All the file systems were contained on disks that were
104 directly connected to the machine.
105 Similarly all the disk space devoted to swap space was also
107 Thus the speed and latency with which file systems could be accessed
108 were roughly equivalent to the speed and latency with which swap
109 space could be accessed.
110 Given the high cost of memory there was little incentive to have
111 the kernel keep track of the contents of the swap area once a process
112 exited since it could almost as easily and quickly be reread from the
117 In the ten years since the current virtual memory system was designed,
118 many technological advances have occurred.
119 One effect of the technological revolution is that the
120 micro-processor has become powerful enough to allow users to have their
121 own personal workstations.
122 Thus the computing environment is moving away from a purely centralized
123 time sharing model to an environment in which users have a
124 computer on their desk.
125 This workstation is linked through a network to a centralized
126 pool of machines that provide filing, computing, and spooling services.
127 The workstations tend to have a large quantity of memory,
128 but little or no disk space.
129 Because users do not want to be bothered with backing up their disks,
130 and because of the difficulty of having a centralized administration
131 backing up hundreds of small disks, these local disks are typically
132 used only for temporary storage and as swap space.
133 Long term storage is managed by the central file server.
135 Another major technical advance has been in all levels of storage capacity.
136 In the last ten years we have experienced a factor of four decrease in the
137 cost per byte of disk storage.
138 In this same period of time the cost per byte of memory has dropped
139 by a factor of a hundred!
140 Thus the cost per byte of memory compared to the cost per byte of disk is
141 approaching a difference of only about a factor of ten.
142 The effect of this change is that the way in which a machine is used
143 is beginning to change dramatically.
144 As the amount of physical memory on machines increases and the number of
145 users per machine decreases, the expected
146 mode of operation is changing from that of supporting more active virtual
147 memory than physical memory to that of having a surplus of memory that can
148 be used for other purposes.
150 Because many machines will have more physical memory than they do swap
151 space (with diskless workstations as an extreme example!),
152 it is no longer reasonable to limit the maximum virtual memory
153 to the amount of swap space as is done in the current design.
154 Consequently, the new design will allow the maximum virtual memory
155 to be the sum of physical memory plus swap space.
156 For machines with no swap space, the maximum virtual memory will
157 be governed by the amount of physical memory.
159 Another effect of the current technology is that the latency and overhead
160 associated with accessing the file system is considerably higher
161 since the access must be over the network
162 rather than to a locally-attached disk.
163 One use of the surplus memory would be to
164 maintain a cache of recently used files;
165 repeated uses of these files would require at most a verification from
166 the file server that the data was up to date.
167 Under the current design, file caching is done by the buffer pool,
168 while the free memory is maintained in a separate pool.
169 The new design should have only a single memory pool so that any
170 free memory can be used to cache recently accessed files.
172 Another portion of the memory will be used to keep track of the contents
173 of the blocks on any locally-attached swap space analogously
174 to the way that memory pages are handled.
175 Thus inactive swap blocks can also be used to cache less-recently-used
177 Since the swap disk is locally attached, it can be much more quickly
178 accessed than a remotely located file system.
179 This design allows the user to simply allocate their entire local disk
180 to swap space, thus allowing the system to decide what files should
181 be cached to maximize its usefulness.
182 This design has two major benefits.
183 It relieves the user of deciding what files
184 should be kept in a small local file system.
185 It also insures that all modified files are migrated back to the
186 file server in a timely fashion, thus eliminating the need to dump
187 the local disk or push the files manually.
191 This section outlines our new virtual memory interface as it is
192 currently envisioned.
193 The details of the system call interface are contained in Appendix A.
197 The virtual memory interface is designed to support both large,
198 sparse address spaces as well as small, densely-used address spaces.
199 In this context, ``small'' is an address space roughly the
200 size of the physical memory on the machine,
201 while ``large'' may extend up to the maximum addressability of the machine.
202 A process may divide its address space up into a number of regions.
203 Initially a process begins with four regions;
204 a shared read-only fill-on-demand region with its text,
205 a private fill-on-demand region for its initialized data,
206 a private zero-fill-on-demand region for its uninitialized data and heap,
207 and a private zero-fill-on-demand region for its stack.
208 In addition to these regions, a process may allocate new ones.
209 The regions may not overlap and the system may impose an alignment
210 constraint, but the size of the region should not be limited
211 beyond the constraints of the size of the virtual address space.
213 Each new region may be mapped either as private or shared.
214 When it is privately mapped, changes to the contents of the region
215 are not reflected to any other process that map the same region.
216 Regions may be mapped read-only or read-write.
217 As an example, a shared library would be implemented as two regions;
218 a shared read-only region for the text, and a private read-write
219 region for the global variables associated with the library.
221 A region may be allocated with one of several allocation strategies.
222 It may map some memory hardware on the machine such as a frame buffer.
223 Since the hardware is responsible for storing the data,
224 such regions must be exclusive use if they are privately mapped.
226 A region can map all or part of a file.
227 As the pages are first accessed, the region is filled in with the
228 appropriate part of the file.
229 If the region is mapped read-write and shared, changes to the
230 contents of the region are reflected back into the contents of the file.
231 If the region is read-write but private,
232 changes to the region are copied to a private page that is not
233 visible to other processes mapping the file,
234 and these modified pages are not reflected back to the file.
236 The final type of region is ``anonymous memory''.
237 Uninitialed data uses such a region, privately mapped;
238 it is zero-fill-on-demand and its contents are abandoned
239 when the last reference is dropped.
240 Unlike a region that is mapped from a file,
241 the contents of an anonymous region will never be read from or
242 written to a disk unless memory is short and part of the region
243 must be paged to a swap area.
244 If one of these regions is mapped shared,
245 then all processes see the changes in the region.
246 This difference has important performance considerations;
247 the overhead of reading, flushing, and possibly allocating a file
248 is much higher than simply zeroing memory.
250 If several processes wish to share a region,
251 then they must have some way of rendezvousing.
252 For a mapped file this is easy;
253 the name of the file is used as the rendezvous point.
254 However, processes may not need the semantics of mapped files
255 nor be willing to pay the overhead associated with them.
256 For anonymous memory they must use some other rendezvous point.
257 Our current interface allows processes to associate a
258 descriptor with a region, which it may then pass to other
259 processes that wish to attach to the region.
260 Such a descriptor may be bound into the UNIX file system
261 name space so that other processes can find it just as
262 they would with a mapped file.
264 Shared memory as high speed interprocess communication
266 The primary use envisioned for shared memory is to
267 provide a high speed interprocess communication (IPC) mechanism
268 between cooperating processes.
269 Existing IPC mechanisms (\fIi.e.\fP pipes, sockets, or streams)
270 require a system call to hand off a set
271 of data destined for another process, and another system call
272 by the recipient process to receive the data.
273 Even if the data can be transferred by remapping the data pages
274 to avoid a memory to memory copy, the overhead of doing the system
275 calls limits the throughput of all but the largest transfers.
276 Shared memory, by contrast, allows processes to share data at any
277 level of granularity without system intervention.
279 However, to maintain all but the simplest of data structures,
280 the processes must serialize their modifications to shared
281 data structures if they are to avoid corrupting them.
282 This serialization is typically done with semaphores.
283 Unfortunately, most implementations of semaphores are
284 done with system calls.
285 Thus processes are once again limited by the need to do two
286 system calls per transaction, one to lock the semaphore, the
287 second to release it.
288 The net effect is that the shared memory model provides little if
289 any improvement in interprocess bandwidth.
291 To achieve a significant improvement in interprocess bandwidth
292 requires a large decrease in the number of system calls needed to
293 achieve the interaction.
294 In profiling applications that use
295 serialization locks such as the UNIX kernel,
296 one typically finds that most locks are not contested.
297 Thus if one can find a way to avoid doing a system call in the case
298 in which a lock is not contested,
299 one would expect to be able to dramatically reduce the number
300 of system calls needed to achieve serialization.
302 In our design, cooperating processes manage their semaphores
303 in their own address space.
304 In the typical case, a process executes an atomic test-and-set instruction
305 to acquire a lock, finds it free, and thus is able to get it.
306 Only in the (rare) case where the lock is already set does the process
307 need to do a system call to wait for the lock to clear.
308 When a process is finished with a lock,
309 it can clear the lock itself.
310 Only if the ``WANT'' flag for the lock has been set is
311 it necessary for the process to do a system call to cause the other
312 process(es) to be awakened.
314 Another issue that must be considered is portability.
315 Some computers require access to special hardware to implement
316 atomic interprocessor test-and-set.
317 For such machines the setting and clearing of locks would
318 all have to be done with system calls;
319 applications could still use the same interface without change,
320 though they would tend to run slowly.
322 The other issue of compatibility is with System V's semaphore
324 Since the System V interface has been in existence for several years,
325 and applications have been built that depend on this interface,
326 it is important that this interface also be available.
327 Although the interface is based on system calls for both setting and
329 the same interface can be obtained using our interface without
330 system calls in most cases.
332 This implementation can be achieved as follows.
333 System V allows entire sets of semaphores to be set concurrently.
334 If any of the locks are unavailable, the process is put to sleep
335 until they all become available.
336 Under our paradigm, a single additional semaphore is defined
337 that serializes access to the set of semaphores being simulated.
338 Once obtained in the usual way, the set of semaphores can be
339 inspected to see if the desired ones are available.
340 If they are available, they are set, the guardian semaphore
341 is released and the process proceeds.
342 If one or more of the requested set is not available,
343 the guardian semaphore is released and the process selects an
344 unavailable semaphores for which to wait.
345 On being reawakened, the whole selection process must be repeated.
347 In all the above examples, there appears to be a race condition.
348 Between the time that the process finds that a semaphore is locked,
349 and the time that it manages to call the system to sleep on the
350 semaphore another process may unlock the semaphore and issue a wakeup call.
351 Luckily the race can be avoided.
352 The insight that is critical is that the process and the kernel agree
353 on the physical byte of memory that is being used for the semaphore.
354 The system call to put a process to sleep takes a pointer
355 to the desired semaphore as its argument so that once inside
356 the kernel, the kernel can repeat the test-and-set.
357 If the lock has cleared
358 (and possibly the wakeup issued) between the time that the process
359 did the test-and-set and eventually got into the sleep request system call,
360 then the kernel immediately resumes the process rather than putting
362 Thus the only problem to solve is how the kernel interlocks between testing
363 a semaphore and going to sleep;
364 this problem has already been solved on existing systems.
369 Babaoglu, O., and Joy, W.,
370 ``Data Structures Added in the Berkeley Virtual Memory Extensions
371 to the UNIX Operating System''
372 Computer Systems Research Group, Dept of EECS, University of California,
373 Berkeley, CA 94720, USA, November 1979.
376 ``Paging in Berkeley UNIX'',
377 Laboratorium voor schakeltechniek en techneik v.d.
378 informatieverwerkende machines,
379 Codenummer 051560-44(1984)01, February 1984.
projects / dragonfly.git / blob