|
References
[B+00] “Hoard: A Scalable Memory Allocator for Multithreaded Applications”
Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson
ASPLOS-IX, November 2000
Berger and company’s excellent allocator for multiprocessor systems. Beyond just being a fun paper,
also used in practice!
[B94] “The Slab Allocator: An Object-Caching Kernel Memory Allocator”
Jeff Bonwick
USENIX ’94
A cool paper about how to build an allocator for an operating system kernel, and a great example of how
to specialize for particular common object sizes.
[E06] “A Scalable Concurrent malloc(3) Implementation for FreeBSD”
Jason Evans
http://people.freebsd.org/˜jasone/jemalloc/bsdcan2006/jemalloc.pdf
April 2006
A detailed look at how to build a real modern allocator for use in multiprocessors. The “jemalloc”
allocator is in widespread use today, within FreeBSD, NetBSD, Mozilla Firefox, and within Facebook.
[K65] “A Fast Storage Allocator”
Kenneth C. Knowlton
Communications of the ACM, Volume 8, Number 10, October 1965
The common reference for buddy allocation. Random strange fact: Knuth gives credit for the idea to not
to Knowlton but to Harry Markowitz, a Nobel-prize winning economist. Another strange fact: Knuth
communicates all of his emails via a secretary; he doesn’t send email himself, rather he tells his secretary
what email to send and then the secretary does the work of emailing. Last Knuth fact: he created TeX,
the tool used to typeset this book. It is an amazing piece of software
4
.
[W+95] “Dynamic Storage Allocation: A Survey and Critical Review”
Paul R. Wilson, Mark S. Johnstone, Michael Neely, David Boles
International Workshop on Memory Management
Kinross, Scotland, September 1995
An excellent and far-reaching survey of many facets of memory allocation. Far too much detail to go
into in this tiny chapter!
4
Actually we use LaTeX, which is based on Lamport’s additions to TeX, but close enough.
O
PERATING
S
YSTEMS
[V
ERSION
0.80]
WWW
.
OSTEP
.
ORG
18
Paging: Introduction
Remember our goal: to virtualize memory. Segmentation (a generaliza-
tion of dynamic relocation) helped us do this, but has some problems; in
particular, managing free space becomes quite a pain as memory becomes
fragmented and segmentation is not as flexible as we might like. Is there
a better solution?
T
HE
C
RUX
:
H
OW
T
O
V
IRTUALIZE
M
EMORY
W
ITHOUT
S
EGMENTS
How can we virtualize memory in a way as to avoid the problems of
segmentation? What are the basic techniques? How do we make those
techniques work well?
Thus comes along the idea of paging, which goes back to the earliest
of computer systems, namely the Atlas [KE+62,L78]. Instead of splitting
up our address space into three logical segments (each of variable size),
we split up our address space into fixed-sized units we call a page. Here
in Figure
18.1
an example of a tiny address space, only 64 bytes total in
size, with 16 byte pages (real address spaces are much bigger, of course,
commonly 32 bits and thus 4-GB of address space, or even 64 bits). We’ll
use tiny examples to make them easier to digest (at first).
64
48
32
16
0
(page 3)
(page 2)
(page 1)
(page 0 of the address space)
Figure 18.1: A Simple 64-byte Address Space
169
170
P
AGING
: I
NTRODUCTION
128
112
96
80
64
48
32
16
0
page frame 7
page frame 6
page frame 5
page frame 4
page frame 3
page frame 2
page frame 1
page frame 0 of physical memory
reserved for OS
(unused)
page 3 of AS
page 0 of AS
(unused)
page 2 of AS
(unused)
page 1 of AS
Figure 18.2: 64-Byte Address Space Placed In Physical Memory
Thus, we have an address space that is split into four pages (0 through
3). With paging, physical memory is also split into some number of pages
as well; we sometimes will call each page of physical memory a page
frame
. For an example, let’s examine Figure
18.2
.
Paging, as we will see, has a number of advantages over our previous
approaches. Probably the most important improvement will be flexibility:
with a fully-developed paging approach, the system will be able to sup-
port the abstraction of an address space effectively, regardless of how the
processes uses the address space; we won’t, for example, have to make
assumptions about how the heap and stack grow and how they are used.
Another advantage is the simplicity of free-space management that pag-
ing affords. For example, when the OS wishes to place our tiny 64-byte
address space from above into our 8-page physical memory, it simply
finds four free pages; perhaps the OS keeps a free list of all free pages for
this, and just grabs the first four free pages off of this list. In the exam-
ple above, the OS has placed virtual page 0 of the address space (AS) in
physical page 3, virtual page 1 of the AS on physical page 7, page 2 on
page 5, and page 3 on page 2.
To record where each virtual page of the address space is placed in
physical memory, the operating system keeps a per-process data structure
known as a page table. The major role of the page table is to store address
Do'stlaringiz bilan baham: | 
