本 涉及 領域 尤其是一 高 的先 先 算法。

背景 水

□ 在 上升 休 用程序 我們 合遇到一介 那就是內 的 和釋放的 頻繁的 和釋放內 合 出現內 碎片 而增加 不 定因素。

3] 、 A等 終端的 非常 由于 終端的貨源的限制 且內 使用頻率很高 如何 頻繁 和釋放內 的 而提高手 等內 受限 上 用的 定性 是人們一直 的 。

4] 目前 于 、 A等 終端的內 分配方法主要有 是固定 度的內 分配策略 另一 是可 度的內 分配策略。

5] 于固定 度的內 分配策略 方法是先把內 分力 又 分力大小相等的內 例如第一介 的內 32 第二 的內 64 等 用戶 一定大小的內 各 內 找到不小于一定大小的 內 所在的 中提取一介內 分配 用戶 用戶釋放內 再 將 內 其所在的 。 方法的 是 如果滿足余 內 的內 用完 則內 。 即使其它 有更大的內 也不合分配 用戶。 使得內 得不到充分利用而造成浪費。

6] 于可 的內 分配策略 方法將 的內 以 表的形式排列 用 戶 一定大小的內 就 表的 搜索 內 若 內 小于一定大小 則 搜索 直到找到足 大小的 內 分配 用戶 用戶釋放內 就將釋放的內 放在 表的尾部。 方法有明 的 。 由于在 、 A等終端中 內 的分配 釋放非常頻繁 而且存在大量 小內 的分配。 使用 方法 一段 同的污 小 內 將散布在 內 必然 生大量的內 碎片 然 有很多 余內 用戶 即 不到 造成內 浪費 甚至 崩潰。

7] 于此 有必要提出一 的方法以克服現有 水的缺陷。

內容

8] 本 所要 的 水河 在于克服現有 水中頻繁的 和釋放內 合

出現內 碎片的 。

9] 本 提供 高 的先 先 方法 其特 在于 包 括如下步驟

10] 步驟一、 建立一介 內 內 是 內存中 若干內 內 由 由尾部建立管理數 由內 成一介

11] 步驟二、 用戶 清大小 b e.e 的內 依 順序判斷 前內 是 否滿足余 是則 步驟 否則 步驟

12] 步驟三、 向 滿足余 的 前內 b e.e 在 內 尾部建 立相 的管理數 管理數 占用固定大小的字

13] 步驟 、 判斷下一介內 是否滿足余 是則 步驟 否則 判 斷下一介內 是否滿足余 直到所有內 均不滿足余 。

14] 算法我們 的解 頻繁 和釋放內 的 而提高手 等內 受限 上 用的 定性 15] 1力本 內 的示意

16] 2力本內 A 的 示意

17] 3 中第一 往第一介內 A 1000 20 的示意18] 4 內 A第二 1600 的數 40 的示意

19] 5力本 方法流程 。

休 方式

20] 合 1至 5 明本 休 。

21] 1所示 首先建立一介內 100 內 由4 內 b _bo c )A、 B、 C、 其中 內 容量均力64 然 將 4 64 的內 b _boc ) 成一介 的 其中 各 內 內部是 的64 內 而 A、 B、 C、 之同可以 也可以不 。 如下方先建立一些 的 C晤言 令

22] S c b _boc /*內

23]

24] S c b _boc ex /* 向下一介內

25] pos 操作管理數 地址

26] pos 操作管理數 地址

27] }

28] S c b _poo *內

29]

30] S c b _boc Sa 內 化

S c b _boc * boc 內 淺出

32] S c b _boc W boc /*內

33] }

34] 1中內 A所示 建立的內 A容量力64 b 內 的起始位置

(或者 是 部位置) 始存儲 而在 存儲 的同 在內 A的 尾部分 4 的 同 于管理數 管理數 出所 存儲 的存 儲的 和存儲 的 直到內 A內 容量不能滿足需求 例如 第 一 存儲 在內 A的 部位置 分配存儲 同 于存儲第 一數 而在內 A的尾部分 4 同 于存儲第一數 管理數 在第 二 存儲 第一 存儲 同的末尾作力第二 存儲 的起始位 置 在內 A的尾部仍然 4 同 于存儲第一管理數 和第二管理 數 。 同 內 B、 C、 每一 存儲 同 也分別在內 的尾 部分 4 的 同 于管理數 。 尋找內 的順序依照 順序 即A C A A滿足內 需求 A 如果A不滿足則看B是 否滿足 如果是 則 B 依 。

35] 吹向b _boc 入儲存 的大小都不一致 所以我們 汞 存儲 的大小 在 我們利用 b boc 的尾部作力 反向 即 內 的尾部 保存管理數 管理數 保存 內 的大小和保 存的位置我們將 反向 你力管理數 反向 的 你力管 理數 的 管理數 的 即上 所占用的4 字 。

36] 以下先 往 的

37] 參照 1 的 100包含的內 A、 B、 C、 的 同 全部力空 b _poo- _boc b _poo- w b>c b _poo >sa 即 內 A內的 和 都 化。 此 內 b _boc 的w p s和 pos都 0。

38] 在 前 我們先 判斷 的 前內 A的數 大 b e.e 判 斷方法如下

39] (b e.e <64 (w pos (pos) +W pos (e ) )-4) ( )

40] 可以

41] Ese

42] 不可以

43] 其中w pos 操作 的管理數 4 包括 2 于 汞 w pos ( os) 和2 于 汞 w pos (e ) W pos ( pos) +W pos (e ) 的是將 和數 相加。

44] 更好地稅 的 如 2所示 第一 往 b _poo1中 我們找到第一介b _b c 即內 A 內 的w pos _pos 0所措 位置均是內 A尾部的起始位置 中10是 pos所措位置 102是w pos所措 位置 b _b c是新的 先通 公式 (1) 先判斷內 A的

w pos w pos (Pos) w pos

(e ) 都 0 因此第一 存入 b e e 滿足的余 是

45] b e.e <64 (w pos (pos) +W pos (e ) ) 4

46] b e.e <64 0+0)

47] 我們在64 W pos 4的地方 汞存入 存放的 起始位置 (或者 是 起始位置) 和 。 存入 存放的 即 存入 在內 中

0 同 w pos將 4 即 4 pos 是0。 48] 3所示 內 A第一 1000 的數 20 的示意 。 由于是 操作 因此的 操作管理數 pos不 101所示仍然 0 而 操作管理數 w pos地址10 4 此 管理數 30包括字市 于 汞 w pos ( os) 301 量力0 和2 于 汞 w pos (e ) 302 1000。 另外 201是 20的起始位置 即w pos ( os) 301所 措的 202是 20的 位置。

49] 在上 第一 第二 1600 依然是依 公式 (1) 先判斷內 A 不 同 即如果64 的 占用的 同 即w pos所措 的w pos (Pos) +W pos (e ) 此 w pos (Pos) 0 W pos (e ) 1000 再 管理數 需要占用的 同4 如果大于第二

則 可以 否則直接跳到下一介b _boc 中 。 第二 判斷余 如下

50] b e.e <64 0+1000) 4

51] 由于第二 的數 大小 1600<64 0+1000) 4 因此可以 。

52] 4所示 內 A第二 1600 的數 40 的示意 。 由于是 操作 因此的 操作管理數 pos不 101所示仍然 0 而 操作管理數 w pos地址102再 4 8 此 管理數 50包括2字市 于 汞 w po s ( os) 301 量力1000 和2 于 汞 w pos (e ) 302 1600。 另外 202是第一 20的 位置同 是 第二 40的起始位置 即w pos ( os) 501所措的 。 此 建立 管理數 30和50 管理數 30和50只 4 但w pos的值 8 即 向第二 管理數 。

53] 以后第三 的判斷余 如下

54] b e.e <64 (w pos (pos) +W pos (e ) ) 4

55] b e.e <64 1000+6000) 4

56] 依 直到內 A不能存入 則依 內 B、 C、

內 A 不再 。

57] 和 相反 需要先找到 前的b _boc 即b _poo > b oc 然 淺出 pos的值 第一 pos的值 0 我們 64 4的位 置 pos和e 參照 1 我們淺出的pos 0 e 000 即告 我們 內 的 量力0的地方 100 bye即可 同 pos由0 4 第二 pos的值 4 我們 64 4的位置 pos Pos)和「 pos e ) 參照 4 我們淺出的 pos Pos) 1000 pos e ) 1600 即告 我們 內 的 量力1000的地方 1600 bye即可 同 pos由4 8 依此

。

58] 上 可以看出本 用的是一 先 先出的數 方法。 以上 步驟一中內 可以由4 的內 其中 內 的大小可以自 又。

59] 由此我們看出 算法很巧妙的利用b _b c 的尾部的的內存空同 保存 b e的位置和 而省去 頻繁 和釋放內 的工作 加強 的 定性。

60] 以上 力本 的較佳 而已 不用以限制本 凡在本 的 精神和原則之內所作的任何修改、 等同替換和 等 包含在本 的保 之內。