ch5.htm

汤子瀛《操作系统》电子教案

    <p><font color="#FFFFFF"><span lang="EN-US">2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．分区大小不等</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">二、内存分配</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
    </o:p>
    </span></font></p>
    <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">分区使用表。表项包含有每个分区的起始地址、大小及状态</span><span lang="EN-US">(</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">是否已分配</span><span lang="EN-US">)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">。</span></font></p>
    <p><font color="#FFFFFF"><span lang="EN-US">&nbsp;</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">5．2．3<span style="mso-spacerun: yes">&nbsp; 
    </span>动态分区分配<o:p>
    </o:p>
    </span></font></p>
    <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">动态分区分配是根据进程的实际需要，动态地为之分配连续的内存空间。在实现可变分区分配存储管理方式时，必须解决下述三个问题：</font></span></p>
    <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）分区分配中所用的数据结构；</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）分区的分配算法；</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">3</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）分区的分配和回收操作。</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">—、分区分配中的数据结构</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
    </o:p>
    </span></font></p>
    <p><font color="#FFFFFF"><span lang="EN-US">1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．空闲分区表</span></font></p>
    <p><font color="#FFFFFF"><span lang="EN-US">2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．空闲分区链</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">二、分区分配算法</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
    </o:p>
    </span></font></p>
    <p><span lang="EN-US" style="mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">1．首次适应算法FF<o:p>
    </o:p>
    </font></span></p>
    <p><font color="#FFFFFF"><span lang="EN-US">2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．循环首次适应算法</span></font></p>
    <p><font color="#FFFFFF"><span lang="EN-US">3</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．最佳适应算法</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">三、分区分配操作</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
    </o:p>
    </span></font></p>
    <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">在动态分区存储管理方式中，主要的操作是分配和回收内存。</font></span></p>
    <p><font color="#FFFFFF"><span lang="EN-US">1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．分配内存</span></font></p>
    <p><font color="#FFFFFF"><span lang="EN-US">2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．回收内存</span></font></p>
    <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链中找到相应的插入点，此时可能出现以下四种情况之一：</font></span></p>
    <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）回收区与插入点的前一个分区</span><span lang="EN-US">F1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">相邻接。</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）回收分区与插入点的后一分区</span><span lang="EN-US">F2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">相邻接。</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">3</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）回收区同时与插入点的前、后两个分区邻接。</span></font></p>
    <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">4</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）回收区既不与</span><span lang="EN-US">F1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">邻接，也不与</span><span lang="EN-US">F2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">邻接。</span></font></p>
    <p><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font color="#FFFFFF">5．2．4 
    动态重定位分区分配<o:p>
    </o:p>
    </font></span></p>
    <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">一、紧凑</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
    </o:p>
    </span></font></p>
    <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">不能被利用的小分区称为“零头”或“碎片”。</font></span></p>
    <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">通过移动，把多个分散的小分区拼接成大分区的方法被称为“拼接”或“紧凑”。</font></span></p>
    <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">二、动态重定位</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
    </o:p>
    </span></font></p>
    <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">三、动态重定位分区分配算法</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
    </o:p>
    </span></font></p>
    　</td>
  </tr>
  <tr>
    <td width="100%" align="left" height="53" colspan="2">
      <p style="TEXT-ALIGN: center" align="center"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font color="#FFFFFF"><a name="ch53"></a>5．3<span style="mso-spacerun: yes">&nbsp; 
      </span>对换<o:p>
      </o:p>
      </font></span></p>
      <p><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font color="#FFFFFF">5．3．1 
      多道程序环境下的对换<o:p>
      </o:p>
      </font></span></p>
      <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">所谓“对换”，是指把内存中暂不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。对换是提高内存利用率的有效措施。</font></span></p>
      <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">如果对换是以整个进程为单位，便称之为“整体对换”或“进程对换”；如果对换是以“页”或“段”为单位进行，则分别称之为“页面对换”或“分段对换”，又统称为“部分对换”</font></span></p>
      <p><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font color="#FFFFFF">5．3．2 
      对换空间的管理<o:p>
      </o:p>
      </font></span></p>
      <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">在具有对换功能的</span><span lang="EN-US">OS</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">中，通常把外存分为文件区和对换区。</span></font></p>
      <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">由于对对换区的分配，是采用连续分配方式，因而对对换区空间的分配与回收，与动态分区方式时内存的分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法和最佳适应算法。具体的分配操作也与图</span><span lang="EN-US">5</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">—</span><span lang="EN-US">9</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">中的操作相同。对换区的回收操作也可分为下述四种情况，即：</span></font></p>
      <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）回收区与插入点的前一分区</span><span lang="EN-US">F1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">相邻接；</span></font></p>
      <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）回收区与插人点的后一分区</span><span lang="EN-US">F2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">相邻接；</span></font></p>
      <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">3</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）回收区还同时与</span><span lang="EN-US">F1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">和</span><span lang="EN-US">F2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">二个分区相邻接；</span></font></p>
      <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">4</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）回收区的前、后没有与之相邻接的空闲分区。</span></font></p>
      <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">对这几种情况的处理方法也与动态分区分配时的方法相同。</font></span></p>
      <p><font color="#FFFFFF"><span lang="EN-US">&nbsp;</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">5．3．3 
      进程的换出与换入<o:p>
      </o:p>
      </span></font></p>
      <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">一、进程的换出</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
      </o:p>
      </span></font></p>
      <p><font color="#FFFFFF"><span lang="EN-US">1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．选出被换出的进程</span></font></p>
      <p><font color="#FFFFFF"><span lang="EN-US">2</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">．换出过程</span></font></p>
      <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">二、进程的换入</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
      </o:p>
      </span></font></p>
      <p>　</td>
  </tr>
  <tr>
    <td width="114%" align="left" height="51" colspan="2">
      <p style="TEXT-ALIGN: center" align="center"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font color="#FFFFFF"><a name="ch54"></a>5．4<span style="mso-spacerun: yes">&nbsp; 
      </span>分页存储管理方式<o:p>
      </o:p>
      </font></span></p>
      <p><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font color="#FFFFFF">5．4．1 
      分页存储管理的基本方法<o:p>
      </o:p>
      </font></span></p>
      <p><font color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">一、页面和物理块</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
      </o:p>
      </span></font></p>
      <p><font color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">在分页存储管理方式中，将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。相应地，内存空间也分成与页相同大小的若干个存储块，或称为物理块或页框（</span><span lang="EN-US">frame</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）。由于进程的最后一页经常装不满一块，而形成不可利用的碎片，称为“页内碎片”。</span></font></p>
      <p><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">在分页存储管理方式中的地址结构如下：</font></span></p>
      <div align="center">
        <table style="BORDER-RIGHT: medium none; BORDER-TOP: medium none; BORDER-LEFT: medium none; BORDER-BOTTOM: medium none; BORDER-COLLAPSE: collapse; mso-border-alt: solid windowtext .5pt; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt" cellSpacing="0" cellPadding="0" border="1">
          <tbody>
            <tr>
              <td style="BORDER-RIGHT: windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 0.5pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 0.5pt solid; WIDTH: 117.65pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid" vAlign="top" width="157">
                <p style="TEXT-ALIGN: center" align="center"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">页号</font></span></p>
              </td>
              <td style="BORDER-RIGHT: windowtext 0.5pt solid; PADDING-RIGHT: 5.4pt; BORDER-TOP: windowtext 0.5pt solid; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; WIDTH: 80.35pt; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid; mso-border-left-alt: solid windowtext .5pt" vAlign="top" width="107">
                <p style="TEXT-ALIGN: center" align="center"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF">页内地址</font></span></p>
              </td>
            </tr>
          </tbody>
        </table>
      </div>
      <p style="TEXT-ALIGN: center" align="center"><span lang="EN-US"><font color="#FFFFFF">31<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      </span>12 11<span style="mso-spacerun: yes">&nbsp;&nbsp; 
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>0</font></span></p>