📄 page431.html
字号:
<HTML>
<HEAD>
<TITLE>Buddy System for Storage Management</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html7245" HREF="page432.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page432.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7243" HREF="page416.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page416.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7237" HREF="page430.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page430.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7247" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7248" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION0014400000000000000000">Buddy System for Storage Management</A></H1>
<A NAME="secheapbuddy"> </A>
<P>
The preceding sections describe two storage pool implementations
that both use a linear list to keep track of the free areas.
When the singly-linked list is used,
the linear list is kept sorted by address;
when the doubly-linked list is used,
the order of the areas in the list is essentially random.
<P>
Each time an area is to be reserved,
the free lists are searched in order to find
an area that is sufficiently large to satisfy the request.
Since there is no direct relationship between the size of an area
and its position in the free list,
the search has worst-case running time that is <I>O</I>(<I>l</I>),
where <I>l</I> is the length of the free list.
And in the worst case <I>l</I> is <I>O</I>(<I>n</I>),
where <I>n</I> is the number of blocks in the storage pool.
<P>
In this section we present a storage pool implementation,
called a <em>buddy system</em><A NAME=31615> </A>,
that uses more than one free list.
All of the areas in a given free list have the same size
and there is a separate free list for each available size of area.
As a result a suitable free area can be found quickly.
<P>
Given a storage pool of size <I>N</I> bytes,
we would require <I>N</I> free lists altogether if we were to
place no restriction the allowable size of an area.
This is clearly infeasible.
Instead we require that <I>N</I> is a power of two,
i.e., <IMG WIDTH=54 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline68165" SRC="img1765.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1765.gif" > for some positive integer <I>m</I>.
Furthermore, the size of each area in the pool
must also be a power of two.
As a result, we only need <I>m</I>+1 free lists,
since the allowed sizes of an area (in bytes) are
<P> <IMG WIDTH=309 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath68145" SRC="img1766.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1766.gif" ><P>
<P>
The key feature of a buddy system is that when a request is made
for an area of size <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58821" SRC="img179.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img179.gif" > for some <I>k</I> less than <I>m</I>,
we first look in the corresponding free list for an area with the correct size.
Notice that if there are no areas of size <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58821" SRC="img179.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img179.gif" > left,
we can obtain one by splitting an area of size <IMG WIDTH=30 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline68179" SRC="img1767.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1767.gif" > in two.
And if there are no areas of size <IMG WIDTH=30 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline68179" SRC="img1767.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1767.gif" > left,
we can obtain one of those by splitting an area of size <IMG WIDTH=30 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline68183" SRC="img1768.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1768.gif" > in two,
and so on.
<P>
The two areas obtained when a larger
area is split in two are called <em>buddies</em>.
Whenever an area is freed,
we check to see if its buddy is also free.
If an area of size <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58821" SRC="img179.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img179.gif" > and its buddy are both free,
they can be combined into a single area of size <IMG WIDTH=30 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline68179" SRC="img1767.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1767.gif" >.
<P>
Of course, the user does not always need an an amount of storage
that is exactly a power of two.
In those situations where it is not,
we shall allocate an amount of memory that is the smallest power of two
no less than the amount requested.
<P>
Figure <A HREF="page431.html#figpool3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page431.html#figpool3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows a memory map of
a storage pool managed using the buddy system.
The reserved areas in Figure <A HREF="page431.html#figpool3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page431.html#figpool3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> are exactly the same as those
shown in Figure <A HREF="page417.html#figpool1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page417.html#figpool1"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -