华南操作系统大作业

“计算机操作系统”

目录。1 题目要求 1

2 设计思想 1

3 数据定义 2

4 处理流程 3

5 源程序 6

6 运行结果 15

7 设计体会 22

动态内存分区分配方式模拟。

假设初始态下，可用内存空间为640k，并有下列请求序列，请分别用首次适应算法和最佳适应算法为作业分配和**内存块，并显示出每次分配和**后的空闲分区链的情况来以及内存占用情况图。

作业1申请130k

作业2申请60k

作业3申请100k

作业2释放60k

作业4申请200k

作业3释放100k

作业1释放130k

作业5申请140k

作业6申请60k

作业7申请50k

作业6释放60k

根据题目要求，要用首次适应算法和最佳适应算法分别实现内存的动态分区，因此先介绍一下这两种算法的基本思想：

首次适应算法中，空闲分区链是按地址递增的次序链接的，当要分配内存空间时，就查表，在各空闲分区中查找满足大小要求的可用块，只要找到第一个足以满足要求的空间就停止查找，并把它分配出去，如果该空闲空间与所需空间大小一样，则将该分区的状态改为1，即已被分配，若还有剩余，则将剩余空间重新划为一个空闲分区，有新的起始地址，状态为0。

最佳适应算法的空闲链是按照空闲块的大小为序、按增量方式排列的，即小块在前，大块在后，它在满足需要的前提下，尽量分配最小的空闲块，这样每次查找分配时第一次找到的能满足要求的必然的最佳的，若空闲空间大小与要分配的大小相差不多时，可直接将其状态改为1即可，若有剩余，则将剩余空闲空间重新划分为一个空闲区，并根据空闲区的大小对链表进行重新排序。

首次适应算法的**过程相对简单，因为分区链是按照地址顺序链接的，因此释放内存时只需要判断要释放的分区前后是否也为空闲区，然后根据情况看是要跟前边或后边或前后都合并为一个大的空闲区，如果前后分区都已分配，则直接将该分区状态改为0即可。

最佳适应算法**时，因为它的分区链是按照空间大小排列的，因此不仅要看要释放分区前后是否为空闲，还要判断其地址是否前后相接，若地址不相接，则即使要释放分区前后均为空闲区，也不能进行合并，而且每次释放后要根据释放空间的大小对链表进行重新排序。

动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示：

struct memory

struct memory *former; /前向指针。

int address;//分区起始地址

int num;//作业号

int size;//分配内存大小

int state;//状态字

struct memory *next; /后向指针。

前向指针和后向指针分别用于与当前分区的前后分区相链接，address用于说明当前分区的起始地址，状态字为0时表示当前分区空闲，为1时表示已分配，num为分配的作业号，size表示分配的内存大小。

详细流程图见图5.1.1，其中各个条件分别为：

p1: ptr->next==null

p2: ptr->size>=assign->size

p3: current!=null

p4: current->size>=assign->size&¤t->state==0

p5: ptr->size>=assign->size

p6: (ptr->next)->next!=null&&is_optimist==true

详细流程图见图5.1.2

若为首先适应算法**，则各条件分别为：

p1: current!=null

p2: current->state==1&¤t->num==i

p3: current==null

p4: current->next==null

p5: previous->state==0

p6: (current->next)->next==null

p7: previous->state==0&&(current->next)->state==0

p8: (current->next)->state==0

p9: is_optimist=true

若为最佳适应算法，则各条件分别为：

p1: current!=null

p2: current->state==1&¤t->num==i

p3: current==null

p4: current->next==null

p5: previous->state==0&&(previous->address+previous->size)==current->addr

ess)p6: (current->next)->next==null

p7: previous->state==0&&(current->next)->state==0&&(previous->address+pr

evious->size)==current->address)&¤t->size+current->address)==current->next)->address)

p8:(current->next)->state==0&&(current->size+current->address)==current->next)->address)

程序如下所示：

#include

#include <>

using namespace std;

struct memory

struct memory *former; /前向指针。

int address;//地址

int num;//作业号

int size;//分配内存大小

int state;//状态0表示空闲1表示已分配

struct memory *next; /后向指针。

typedef struct memory memory;

memory *mem;

const int size_min=10;//内存允许的最小空闲块的大小

bool is_optimist;//判断是否是最佳适应算法

void init();初始化内存块。

void exec();执行相应算法。

void f_f(int); 依次初始化每个作业，并根据相应算法对作业分配内存。

void alloc(memory *,memory *)分配内存算法（包括两种不同算法）

void free(memory *,int);/首次适应算法**内存。

void free_optimist(memory *,int); 最佳适应算法**内存。

void sort(memory *)对内存链进行排序

void insert(memory *,memory *)按空间大小将作业顺序插入到内存链。

void print(memory *)打印内存链

void main()

//主函数。

int i=0;

while(1)

if(i==2)

else if(i==0)

void init()

//初始化内存容量。

mem=new memory;

mem->size=640;

mem->former=0;

mem->next=0;

void exec()

//执行算法。

while(1)

else if(k==0)

//回滚到选择算法的步骤。

void f_f(int i)

//依次初始化每个作业，并根据相应算法对作业分配内存。

int work=作业序列，i从1开始（与作业号对应），因此从第一个开始存放作业值，第0个值为0，不是作业。

memory *running;

running=(memory *)malloc(sizeof(memory));

if(running!=null)

华南操作系统大作业

操作系统大作业a

操作系统大作业a

操作系统大作业

其他用户还读了