文档介绍：课程设计：最先适应算法
设计1 动态异长分区存分配与去配算法的设计-最先适应算法
设计目的
理解存储管理的功能，掌握动态异长分区存管理中的最先适应算法。
设计要求
本设计要求模拟最先适应算法的分配算法和回收算法。
设计步骤
数据结构分析
空闲区域首址
空闲区域长度
…
…
addr
size
…
…
图1-1 空闲区域表
为了实现存储资源的分配和回收，操作系统需要记录存资源使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。为此一般需要两个表，一个为分配表, 另外一个为空闲区域表。前者记录已经分配的区域, 后者记录着所有当前未被进程占用的空闲区域, 如图1-1所示。
显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的操作系统中，这些区域登记在进程的PCB中。而PCB中除了关于存资源的信息外，还有其它大量信息。
由于本设计是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的存空间，如图1-2所示。
线程名称
驻留区始址
驻留区大小
a
0
10
b
20
20
……
……
……
图1-2 线程驻留区表
同时，需要一表来记录各个线程对存的请求信息，如图1-3所示。
线程名称
请求大小(KB)
预计驻留时间( 秒)
thread_1
20
4
thread_2
10
5
……
……
……
图1-3 存申请表
算法分析
对于存储申请命令, 选取满足申请长度要求且起始地址最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分的长度为原长度与分配长度之差, 将其仍记录于空闲区域表中。
回收时，按回收区的首地址查询空闲区表，若有与回收区相临的空闲区，则将其合并到相临区中，否则，把回收区按照地址从低到高的顺序插入到空闲区域表的适当位置。
设计并分析测试数据
假设初始存布局如图1-4，图中的起始地址以及大小都以KB来衡量。
起始地址
0
10
20
40
70
80
85
145
160
180
占用者
a
b
c
d
e
大 小
10
10
20
30
10
5
60
15
20
20
图1-4初始存布局
由图1-4可见，初始时共有五个线程驻留在存，它们是a,b,c,d,e，线程驻留区表如图1-5；还有五个空闲区，空闲区域表如图
1-6。
假设现在有三个线程提出存申请，申请情况见图1-7。经过分析我们得到在每种分配算法下这三个线程所申请到的存情况。图1-8是最先适应算法分配情况。
线程名称
驻留区始址
驻留区大小
a
0
10
b
20
20
c
70
10
d
85
60
e
160
20
图1-5 线程驻留区表
空闲区首址
空闲区长度
10
10
40
30
80
5
145
15
180
20
图1- 6 空闲区域表
线程名称
驻留区始址
驻留区大小
a
0
10
b
20
20
c
70
10
d
85
60
e
160
20
thread_1
40
20
thread_2
10
10
thread_3
60
5
图1-8 最先适应算法线程驻留区表
线程名称
请求大小
(KB)
预计驻留
时间( 秒)
thread_1
20
4
thread_2
10
5
thread_3
5
6
图1-7 内存申请表
程序设计
程序包含两个文件，，。在头文件中定义了宏、数据结构、全局变量、函数声明，源程序中含有各个函数的实现。
在头文件中，结构体FREEAREA、REQUIRE_MEMORY、THREAD_RESIDENCE_MEMORY分别对应于图1-1、图1-2、图1-3中的一行，不同之处是为了构成链表在三个结构体中都有前向指针。数组init