📄 5-4.htm
字号:
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>printf</span></span><span
class=GramE>(</span>“<span class=SpellE>sbrk</span>: % X -- % X \n” , cp, cp + <span
class=SpellE>nu</span> * <span class=SpellE>sizeof</span>(Header) ) ;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>if</span> (cp = = (char *) -1) <span style='mso-tab-count:
4'> </span>/*
no space at all */<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>return</span> NULL;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>up</span> = (Header * ) cp;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>up</span> -> <span class=SpellE>s.size</span> = <span
class=SpellE>nu</span>;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>Free(</span>up + 1) ;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>return</span> <span class=SpellE>free_list</span>;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span>}<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><o:p> </o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span>/* Free</span><span
style='font-size:9.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>：</span><span class=GramE><span
lang=EN-US style='font-size:9.0pt'>put</span></span><span lang=EN-US
style='font-size:9.0pt'> block <span class=SpellE>ap</span> in Free list */<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span><span
class=GramE>void</span> Free(void * <span class=SpellE>ap</span>)<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span>{<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span>Header * <span class=SpellE>bp</span>, *p;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>bp</span></span> = (Header * ) <span
class=SpellE>ap</span> – 1;<span style='mso-tab-count:6'> </span>/*
point to block header */<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>for</span> (p = <span class=SpellE>free_list</span>;
!(<span class=SpellE>bp</span> > p && <span class=SpellE>bp</span>
< p -> <span class=SpellE>s.next</span>) ; p = p -> <span
class=SpellE>s.next</span>)<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'>
</span><span class=GramE>if</span> ( p > = p -> <span class=SpellE>s.next</span>
&& (<span class=SpellE>bp</span> > p || <span class=SpellE>bp</span>
< p -> <span class=SpellE>s.next</span> ) )<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>break</span>;<span style='mso-tab-count:5'> </span>/*
freed block at start or end of arena */<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>if</span> (<span class=SpellE>bp</span> + <span
class=SpellE>bp</span> -> <span class=SpellE>s.size</span> = = p -> <span
class=SpellE>s.next</span> ) {<span style='mso-tab-count:2'> </span><span
style='mso-spacerun:yes'> </span><span style='mso-tab-count:1'> </span>/*
join to upper <span class=SpellE>nbr</span> */<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>bp</span></span> -> <span
class=SpellE>s.size</span> + = p -> <span class=SpellE>s.next</span> -> <span
class=SpellE>s.size</span>;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>bp</span></span> -> <span
class=SpellE>s.next</span> = p -> <span class=SpellE>s.next</span> -> <span
class=SpellE>s.next</span>;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span>}<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>else</span><o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>bp</span></span> -> <span
class=SpellE>s.next</span> = p -> <span class=SpellE>s.next</span>;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>if</span> (p+ p -> <span class=SpellE>s.size</span>
= = <span class=SpellE>bp</span>) {<span style='mso-tab-count:5'> </span>/*
join to lower <span class=SpellE>nbr</span> */<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>p</span> -> <span class=SpellE>s.size</span> + = <span
class=SpellE>bp</span> -> <span class=SpellE>s.size</span>;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>p</span> -> <span class=SpellE>s.next</span> = <span
class=SpellE>bp</span> -> <span class=SpellE>s.next</span>;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span>}<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>else</span><o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>p</span> -> <span class=SpellE>s.next</span> = <span
class=SpellE>bp</span>;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE>free_list</span> = p;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span>}<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><o:p> </o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span><span
class=GramE>void</span> <span class=SpellE>printlist</span>(void)<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span>{<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span>Header *p;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>int</span></span> <span
class=SpellE>i</span> = 0;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>printf</span></span><span
class=GramE>(</span>“base: %X, <span class=SpellE>base.next</span>: %X, <span
class=SpellE>base.next.next</span>: %X, free: %x\n” , &base,<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE>base.s.next</span>, <span class=SpellE>base.s.next</span>
-> <span class=SpellE>s.next</span>, <span class=SpellE>free_list</span><span
class=GramE>) ;</span><o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>for</span> (p = &base; p -> <span class=SpellE>s.next</span>
!= <span class=SpellE>free_list</span>; p = -> <span class=SpellE>s.next</span>
) {<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>i</span></span>++;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>printf</span></span><span
class=GramE>(</span>“block %d, size = %d” , I, p -> <span class=SpellE>s.size</span>)
;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>if</span> (p > <span class=SpellE>free_list</span>)<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>printf</span></span><span
class=GramE>(</span>“used!\n” ) ;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=GramE>else</span><o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span><span class=SpellE><span class=GramE>printf</span></span><span
class=GramE>(</span>“free!\n”) ;<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'>
</span>}<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:9.0pt'><span
style='mso-spacerun:yes'> </span>}<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:21.0pt'><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>当请求分配内存时，扫描自由存储块链表，直到找到一个足够大的可供分配的内存块，<span
class=GramE>若找到</span>的块大小正好等于所请求的大小时，就把这一块从自由链表中取下来，返回给申请者。<span class=GramE>若找到</span>的块太大，即对其分割，并将一块大小适合的空间返回给申请者，余下的部分返回链表。若找不到足够大的块，就通过调用</span><span
class=SpellE><span lang=EN-US>morecore</span></span><span lang=EN-US>() </span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>函数从操作系统区请求另外一块足够大的内存区域，并把它链接到<span class=GramE>自由块</span>链表中，然后再继续搜索。</span></p>
<p class=MsoNormal style='text-indent:21.0pt'><span class=SpellE><span
lang=EN-US style='color:black'>morecore</span></span><span lang=EN-US
style='color:black'>()</span><span lang=EN-US> </span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>函数从操作系统得到存储空间，在</span><span
lang=EN-US>Linux</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>中，通过系统调用</span><span class=SpellE><span
lang=EN-US>sbrk</span></span><span lang=EN-US>(n) </span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>向操作系统申请</span><span lang=EN-US>n</span><span class=GramE><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>个</span></span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>字节的存储空间，返回值为申请到的存储空间的起始地址。由于要求系统分配存储空间是一个代价较大的操作，故通常一次申请一个较大的内存空间，需要时再将其分割。</span></p>
<p class=MsoNormal style='text-indent:21.0pt'><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>释放存储块也要搜索自由链表，目的是找到适当的位置将要释放的块插进去，如果被释放的块的任何一边与链表中的某一块邻接，即对其进行合并操作，直到没有可合并的邻接块为止，这样可防止存储空间变得过于零碎。</span><span
lang=EN-US>Linux</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>正是通过采用所谓的</span><span lang=EN-US>Buddy</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>算法防止存储空间由于内存空间的频繁分配和回收而变得过于零碎。</span></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -