课 程 设 计
课程设计名称： 操作系统原理
专 业 班 级 ： 软件 1601
学 生 姓 名 ：
学 号 ：
指 导 教 师 ：
课程设计时间：
2
目录
1 需求分析 ........................................................ 3
2 概要设计 ........................................................ 3
总体结构 .......................................................... 3
数据结构.......................................................... 4
分区分配算法...................................................... 5
回收分区算法...................................................... 5
首次适应算法寻找分区位置.......................................... 6
循环首次适应算法寻找分区位置...................................... 7
最佳适应算法寻找分区位置.......................................... 7
最坏适应算法寻找分区位置.......................................... 7
绘制状态图算法.................................................... 8
程序界面.......................................................... 8
3 运行环境 ........................................................ 8
硬件环境.......................................................... 8
软件环境.......................................................... 9
4 开发工具和编程语言 .............................................. 9
5 详细设计 ........................................................ 9
链表初始化 ........................................................ 9
分配分区函数...................................................... 9
回收分区函数..................................................... 10
首次适应算法..................................................... 11
循环首次适应算法................................................. 12
最佳适应算法..................................................... 12
最坏适应算法..................................................... 13
分配状态显示图与表............................................... 13
输入分配回收序列控制函数......................................... 15
6 调试分析 ....................................................... 17
7 测试结果 ....................................................... 17
8 参考文献 ....................................................... 21
9 心得体会 ....................................................... 22
3
1 需求分析
用 C 语言实现采用循环首次适应算法的动态分区分配过程 alloc()和回收过
程 free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系
统优先使用空闲区低端的空间。采用循环首次适应算法进行内存块的分配和回
收，同时显示内存块分配和回收后空闲内存分区链的情况。
假设初始状态如下，可用的内存空间为 640KB，并按照下列的请求序列进行
内存的分配与回收：
作业 1 申请 130KB；作业 2 申请 60KB；作业 3 申请 100KB；作业 2 释放 60KB；
作业 4 申请 200 KB；作业 3 释放 100 KB；作业 1 释放 130 KB；作业 5 申请 140 KB；
作业 6 申请 60 KB；作业 7 申请 50KB；作业 6 释放 60 KB
基本功能：设计与实现动态分区分配的数据结构与算法。根据作业大小，对
空闲分区按照循环首次适应算法进行分配，回收分区时，按照回收算法进行合并
回收。分配、回收后显示空闲分区状态。
扩展功能：同时实现首次适应算法、最佳适应算法、最坏适应算法。通过绘
制分区状态图更直观地显示分配和回收过程，对比各种算法的差异和优劣。
2 概要设计
总体结构：
在 C 语言面向过程编程方法中，常用分层方法进行编程，降低各模块之间的
耦合度。在操作系统中，也用到了分层思想进行设计，每一步设计都建立在可靠
的基础上，这样易于扩充和维护系统。
在此次的课程设计中，同样也使用分层的方法，可以将各种算法很简单方便
的一起实现。最底层是基本的数据结构，用来存储分区的信息。上一层是分配分
区的函数 alloc()和回收分区的函数 free()。通过调用 alloc()和 free()函数可
以实现四种算法。通过图形展示算法可以直观地显示分配和回收过程。最上一层
是程序的界面，允许用户可以自由的对内存进行分配和回收，程序展示动态结果。
总体结构如图 1。
4
图 1 程序总体结构
数据结构：
在实际的操作系统中，分配出去的内存记录在进程控制块中，为了加快内存
的分配过程，动态分区最常采用的数据结构是空闲表或空闲链表，数据结构只记
录未分配的内存分区。为了降低模拟程序的复杂度，本模拟将分配出去的和未分
配出去的内存分区记录在同一个数据结构中，用一个标志表示是否已被分配。各
分区按地址递增次序排列。内存的分配和回收只要是对数据结构做插入和删除操
作，采用双向链表结构。
为 使 程 序 具 有 扩 展 性 灵 活 性 ， 分 区 大 小 采 用 宏 定 义 方 式 （ #define
MEMORY_SIZE 640），可修改分区的大小，展示在不同分区大小下的分配情况。
typedef struct SubAreaNode *SubAreaList;
struct SubAreaNode
{
int addr; //分区起始地址
int size; //分区大小
int stat; //分区状态 宏定义 ALLOCED 1 FREE 0
int pid; //已分配分区的进程 id
SubAreaList pre;
SubAreaList next;
};
SubAreaList head; //全局变量 分区链表首指针
SubAreaList nowList; //当前位置分区指针 用于循环首次适应算法
5
分区分配算法：
接口：int alloc(int pid, int psize, SubAreaList p);
在链表位置 p 处为编号为 pid，大小为 psize 的作业分配空间，链表 p 通过
各种查找空闲分区算法（首次适应、循环首次适应、最佳适应、最坏适应）提供。
返回本次分配成功与否。
算法流程图见图 2。
图 2 分区分配算法流程图
回收分区算法：
接口：int freeAlloc(int pid)；
释放 pid 进程的分区空间，重新插入到空闲分区链表。返回值为本次回收是
否成功。
回收时先遍历链表，找到进程 pid 所在的位置 p，如果存在，可能出现下面
四种情况之一：
1） 回收区与前一空闲分区相邻，此时应将回收区与前一分区合并。
2） 回收区与后一空闲分区相邻，此时应将回收区与后一分区合并。
