第10章目标程序运行时的组织.ppt

* * * 首次满足法（时间优先）：只要在空闲块链表中找到满足需要的一块，就进行分配。如果该块很大，则按申请的大小进行分割，剩余的块仍留在空闲块链表中；如果该块不很大，比如说，比申请的块大不了几个字节，则整块分配出去，以免使空闲链表中留下许多无用的小碎块。 最优满足法（空间优先）：将空闲块链表中一个不小于申请块且最接近于申请块的空闲块分配给用户，则系统在分配前首先要对空闲块链表从头至尾描一遍，然后从中找出一块不小于申请块且最接近于申请块的空闲块分配，在用最优满足法进行分配时，为避免每次分配都要扫描整个链表，通常将空闲块链表空间的大小从小到大排序。这样，只要找到第一块大小申请块的空闲块即可进行分配。当然，在回收时变需将释放在空闲块插入到链表的适当位置上去。 ②③① 最差满足法（时间优先）：将空闲块表中不小于申请块且是最大的空闲的一部全分配给用户。此时的空闲块链表按空闲的块的大小从大到小排序。这样每次分配无需查找，只需从链表中删除第一个结点，并将其中一部分分配给用户，而其它部分作为一个新的结点插入到空闲块表的适当置上去。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 用Display表的方案 主程序---P---Q---R d[2] d[1] d[0] Q 的 活动记录 P 的 活动记录 主程序的 活动记录 display sp top （3） R 的 活动记录 Q 的 活动记录 P 的 活动记录 主程序的 活动记录 d[1] d[0] display top sp （4） DISPLAY表的维护和建立 DISPLAY表d 运行栈 0 主程活动记录地址 1 R活动记录地址 ... 当过程的层次为n，它的 display为n+1个值。 一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。 全局DISPLAY地址 0 老 SP 1 返回地址 2 全局 DISPLAY 地址 3 参数个数 4 形式单元 . . . d DISPLAY . . . 简单变量 数组内情向量 临时变量 分程序结构 Procedure A(m,n); integer m,n; B1:begin real z; array B[m:n]; B2:begin real d, e; L3: 2 end; B4:begin array C[1:m]; 1 B5:begin real e; L6: 5 4 end; end; L8:end; 分程序结构的存储分配方案 处理分程序结构存储分配方案的一种简单办法是，把分程序看成 “无名无参过 程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。 一则，每逢进入 一个分程序，就照样建立连接数据和DISPLAY表,这是不必要的。 二则 ，当从内层分程序向外层转移时，可能同时要结束若干个分程序。  按照过程处理办法，意味着必须一层一