首次适应算法(FF)和循环首次适应算法(NF)

原文：https://blog.****.net/acm_yuuji/article/details/50410483

FF和NF算法都是基于顺序搜索的动态分区分配算法，在内存中检索一块分区分配给作业。如果空间大小合适则分配，如果找不到空间则等待。

FF算法按地址递增从头扫描空闲分区，如果找到空闲分区大小>=作业大小则分配。如果扫描完空闲分区表都没有找到分区，则分配失败。

NF算法和FF算法类似，但是NF算法每次分配都会记录下位置，下次分配的时候从记录的位置开始，循环扫描一遍空闲分区。

注：回收分区的算法写的和书上不太一样，书上是分配过后把分区从空闲分区链中移除，我是直接分配然后状态为设置为false，所以可能不太一样。

首次适应算法(FF)和循环首次适应算法(NF)

[cpp]view plain copy
//公共模块，负责定义结构体，初始化，显示结果，回收  
//BlockJob.h  
#ifndef BLOCKJOB_H_  
#define BLOCKJOB_H_  
  
#include <vector>  
  
const int MINSIZE = 10;     //最小不可分割分区大小  
  
                            //空闲分区  
typedef struct block  
{  
    int start;  //开始地址  
    int size;   //大小  
    bool state; //分区状态 true:空闲 false:占用  
}block;  
  
//作业  
typedef struct job  
{  
    int size;   //作业大小  
    int start;  //分配的分区首址  
    int BlockSize;  //分配空闲分区的大小（可能大于作业大小）  
};  
  
//初始化空闲分区与作业  
void init(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
//显示结果  
void show(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
//回收分区  
void recycle(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
#endif  
  
//BlockJob.cpp  
#include "BlockJob.h"  
#include <iostream>  
#include <iomanip>  
  
//初始化空闲分区与作业  
void init(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    std::cout << "输入空闲分区数: ";  
    int num;  
    std::cin >> num;  
  
    std::cout << "输入空闲分区的起始地址与大小: \n";  
    block temp;  
    for (int i = 0; i < num; ++i)  
    {  
        std::cin >> temp.start >> temp.size;  
        temp.state = true;  
        BlockList.push_back(temp);  
    }  
  
    std::cout << "输入作业数: ";  
    std::cin >> num;  
    std::cout << "输入作业的大小: \n";  
    job tempj;  
    for (int i = 0; i < num; ++i)  
    {  
        std::cin >> tempj.size;  
        tempj.BlockSize = 0;  
        tempj.start = 0;  
        JobList.push_back(tempj);  
    }  
}  
  
//显示结果  
void show(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    using std::setw;  
    std::cout.setf(std::ios_base::left);  
  
    std::cout << "空闲分区表: \n";  
    std::cout << setw(10) << "分区号" << setw(10) << "分区大小" << setw(10) << "分区始址" << setw(10) << "状态" << std::endl;  
    int num = 0;  
    for (std::vector<block>::iterator it = BlockList.begin(); it != BlockList.end(); ++it, ++num)  
        std::cout << setw(10) << num << setw(10) << (*it).size << setw(10) << (*it).start << setw(10) << (((*it).state == true) ? "空闲" : "占用") << std::endl;  
  
    std::cout << "作业信息: \n";  
    std::cout << setw(10) << "作业号" << setw(10) << "作业大小" << setw(10) << "分区大小" << setw(10) << "分区始址" << std::endl;  
    num = 0;  
    for (std::vector<job>::iterator it = JobList.begin(); it != JobList.end(); ++it, ++num)  
        std::cout << setw(10) << num << setw(10) << (*it).size << setw(10) << (*it).BlockSize << setw(10) << (*it).start << std::endl;  
}  
  
//回收分区  
void recycle(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    std::cout << "输入回收分区的首址: ";  
    int start;  
    std::cin >> start;  
  
    for (std::vector<block>::iterator it = BlockList.begin(); it != BlockList.end(); ++it)  
    {  
        //找到要回收的分区  
        if (start == (*it).start)  
        {  
            //与前一个分区邻接  
            if (it != BlockList.begin() && (*(it - 1)).start + (*(it - 1)).size == (*it).start)  
            {  
                //与后一个分区邻接  
                if (it != BlockList.end() - 1 && (*it).start + (*it).size == (*(it + 1)).start)  
                {  
                    //将前一块分区，要回收的分区，后一块分区合并  
                    (*(it - 1)).size += (*it).size + (*(it + 1)).size;  
                    (*(it - 1)).state = true;  
                    BlockList.erase(it);  
                    BlockList.erase(it);  
                }  
                else    //不与后一个分区邻接  
                {  
                    //将此分区与前一个分区合并  
                    (*(it - 1)).size += (*it).size;  
                    (*(it - 1)).state = true;  
                    BlockList.erase(it);  
                }  
            }  
            else if(it != BlockList.end()-1 && (*it).start +(*it).size == (*(it+1)).start)  //不与前一个分区邻接，与后一个分区邻接  
            {  
                //将此分区与后一个分区合并  
                (*it).size += (*(it + 1)).size;  
                (*it).state = true;  
                BlockList.erase(it + 1);  
            }  
            else    //都不邻接  
            {  
                (*it).state = true;  
            }  
            break;  
        }  
    }  
  
    for (std::vector<job>::iterator it = JobList.begin(); it != JobList.end(); ++it)  
    {  
        if ((*it).start == start)  
        {  
            (*it).BlockSize = (*it).start = 0;  
            break;  
        }  
    }  
}  

[cpp]view plain copy
//FF.cpp  
#include "BlockJob.h"  
  
//FF算法  
void FF(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
int main()  
{  
    std::vector<block> BlockList;  
    std::vector<job> JobList;  
  
    //初始化空闲分区与作业  
    init(BlockList, JobList);  
  
    //FF算法  
    FF(BlockList, JobList);  
  
    //显示结果  
    show(BlockList, JobList);  
  
    //回收分区  
    recycle(BlockList, JobList);  
  
    //显示结果  
    show(BlockList, JobList);  
  
    return 0;  
}  
  
//FF算法  
void FF(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    for (std::vector<job>::iterator ItJob = JobList.begin(); ItJob != JobList.end(); ++ItJob)  
    {  
        for (std::vector<block>::iterator ItBlock = BlockList.begin(); ItBlock != BlockList.end(); ++ItBlock)  
        {  
            //分区未被使用且能够装下作业  
            if ((*ItBlock).state && (*ItBlock).size >= (*ItJob).size)  
            {  
                if ((*ItBlock).size - (*ItJob).size > MINSIZE)   //剩余空间还可以继续分配  
                {  
                    (*ItBlock).state = false;  
  
                    //修改作业信息，分配空间  
                    (*ItJob).start = (*ItBlock).start;  
                    (*ItJob).BlockSize = (*ItJob).size;  
  
                    //添加新表项  
                    block NewBlock;  
                    NewBlock.start = (*ItBlock).start + (*ItJob).size;  
                    NewBlock.size = (*ItBlock).size - (*ItJob).size;  
                    NewBlock.state = true;  
                    (*ItBlock).size = (*ItJob).size;  
                    BlockList.insert(ItBlock + 1, NewBlock);  
  
                }  
                else        //剩余空间不可分配，全部分配给此作业  
                {  
                    (*ItBlock).state = false;  
  
                    //修改作业信息，分配空间  
                    (*ItJob).start = (*ItBlock).start;  
                    (*ItJob).BlockSize = (*ItBlock).size;  
                }  
  
                break;  
            }  
        }  
    }  
}  

[cpp]view plain copy
//NF.cpp  
#include "BlockJob.h"  
  
//NF算法  
void NF(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
int main()  
{  
    std::vector<block> BlockList;  
    std::vector<job> JobList;  
  
    //初始化空闲分区与作业  
    init(BlockList, JobList);  
  
    //NF算法  
    NF(BlockList, JobList);  
  
    //显示结果  
    show(BlockList, JobList);  
  
    //回收分区  
    recycle(BlockList, JobList);  
  
    //显示结果  
    show(BlockList, JobList);  
  
    return 0;  
}  
  
//NF算法  
void NF(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    int pos = 0;        //上一次查找的位置  
  
    for (std::vector<job>::iterator ItJob = JobList.begin(); ItJob != JobList.end(); ++ItJob)  
    {  
        std::vector<block>::iterator ItBlock = BlockList.begin() + pos;  
        do {  
            //分区未被使用且能够装下作业  
            if ((*ItBlock).state && (*ItBlock).size >= (*ItJob).size)  
            {  
                pos = &(*ItBlock) - &BlockList[0];  //记录此次分配位置  
                if ((*ItBlock).size - (*ItJob).size > MINSIZE)   //剩余空间还可以继续分配  
                {  
                    (*ItBlock).state = false;  
  
                    //修改作业信息，分配空间  
                    (*ItJob).start = (*ItBlock).start;  
                    (*ItJob).BlockSize = (*ItJob).size;  
  
                    //添加新表项  
                    block NewBlock;  
                    NewBlock.start = (*ItBlock).start + (*ItJob).size;  
                    NewBlock.size = (*ItBlock).size - (*ItJob).size;  
                    NewBlock.state = true;  
                    (*ItBlock).size = (*ItJob).size;  
                    BlockList.insert(ItBlock + 1, NewBlock);  
  
                }  
                else        //剩余空间不可分配，全部分配给此作业  
                {  
                    (*ItBlock).state = false;  
  
                    //修改作业信息，分配空间  
                    (*ItJob).start = (*ItBlock).start;  
                    (*ItJob).BlockSize = (*ItBlock).size;  
                }  
  
                break;  
            }  
  
            ++ItBlock;  
            if (ItBlock == BlockList.end())  
                ItBlock = BlockList.begin();  
        } while (pos != &(*ItBlock) - &BlockList[0]);  
    }  
}  

FF和NF算法都是基于顺序搜索的动态分区分配算法，在内存中检索一块分区分配给作业。如果空间大小合适则分配，如果找不到空间则等待。

FF算法按地址递增从头扫描空闲分区，如果找到空闲分区大小>=作业大小则分配。如果扫描完空闲分区表都没有找到分区，则分配失败。

NF算法和FF算法类似，但是NF算法每次分配都会记录下位置，下次分配的时候从记录的位置开始，循环扫描一遍空闲分区。

注：回收分区的算法写的和书上不太一样，书上是分配过后把分区从空闲分区链中移除，我是直接分配然后状态为设置为false，所以可能不太一样。

首次适应算法(FF)和循环首次适应算法(NF)

[cpp]view plain copy
//公共模块，负责定义结构体，初始化，显示结果，回收  
//BlockJob.h  
#ifndef BLOCKJOB_H_  
#define BLOCKJOB_H_  
  
#include <vector>  
  
const int MINSIZE = 10;     //最小不可分割分区大小  
  
                            //空闲分区  
typedef struct block  
{  
    int start;  //开始地址  
    int size;   //大小  
    bool state; //分区状态 true:空闲 false:占用  
}block;  
  
//作业  
typedef struct job  
{  
    int size;   //作业大小  
    int start;  //分配的分区首址  
    int BlockSize;  //分配空闲分区的大小（可能大于作业大小）  
};  
  
//初始化空闲分区与作业  
void init(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
//显示结果  
void show(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
//回收分区  
void recycle(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
#endif  
  
//BlockJob.cpp  
#include "BlockJob.h"  
#include <iostream>  
#include <iomanip>  
  
//初始化空闲分区与作业  
void init(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    std::cout << "输入空闲分区数: ";  
    int num;  
    std::cin >> num;  
  
    std::cout << "输入空闲分区的起始地址与大小: \n";  
    block temp;  
    for (int i = 0; i < num; ++i)  
    {  
        std::cin >> temp.start >> temp.size;  
        temp.state = true;  
        BlockList.push_back(temp);  
    }  
  
    std::cout << "输入作业数: ";  
    std::cin >> num;  
    std::cout << "输入作业的大小: \n";  
    job tempj;  
    for (int i = 0; i < num; ++i)  
    {  
        std::cin >> tempj.size;  
        tempj.BlockSize = 0;  
        tempj.start = 0;  
        JobList.push_back(tempj);  
    }  
}  
  
//显示结果  
void show(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    using std::setw;  
    std::cout.setf(std::ios_base::left);  
  
    std::cout << "空闲分区表: \n";  
    std::cout << setw(10) << "分区号" << setw(10) << "分区大小" << setw(10) << "分区始址" << setw(10) << "状态" << std::endl;  
    int num = 0;  
    for (std::vector<block>::iterator it = BlockList.begin(); it != BlockList.end(); ++it, ++num)  
        std::cout << setw(10) << num << setw(10) << (*it).size << setw(10) << (*it).start << setw(10) << (((*it).state == true) ? "空闲" : "占用") << std::endl;  
  
    std::cout << "作业信息: \n";  
    std::cout << setw(10) << "作业号" << setw(10) << "作业大小" << setw(10) << "分区大小" << setw(10) << "分区始址" << std::endl;  
    num = 0;  
    for (std::vector<job>::iterator it = JobList.begin(); it != JobList.end(); ++it, ++num)  
        std::cout << setw(10) << num << setw(10) << (*it).size << setw(10) << (*it).BlockSize << setw(10) << (*it).start << std::endl;  
}  
  
//回收分区  
void recycle(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    std::cout << "输入回收分区的首址: ";  
    int start;  
    std::cin >> start;  
  
    for (std::vector<block>::iterator it = BlockList.begin(); it != BlockList.end(); ++it)  
    {  
        //找到要回收的分区  
        if (start == (*it).start)  
        {  
            //与前一个分区邻接  
            if (it != BlockList.begin() && (*(it - 1)).start + (*(it - 1)).size == (*it).start)  
            {  
                //与后一个分区邻接  
                if (it != BlockList.end() - 1 && (*it).start + (*it).size == (*(it + 1)).start)  
                {  
                    //将前一块分区，要回收的分区，后一块分区合并  
                    (*(it - 1)).size += (*it).size + (*(it + 1)).size;  
                    (*(it - 1)).state = true;  
                    BlockList.erase(it);  
                    BlockList.erase(it);  
                }  
                else    //不与后一个分区邻接  
                {  
                    //将此分区与前一个分区合并  
                    (*(it - 1)).size += (*it).size;  
                    (*(it - 1)).state = true;  
                    BlockList.erase(it);  
                }  
            }  
            else if(it != BlockList.end()-1 && (*it).start +(*it).size == (*(it+1)).start)  //不与前一个分区邻接，与后一个分区邻接  
            {  
                //将此分区与后一个分区合并  
                (*it).size += (*(it + 1)).size;  
                (*it).state = true;  
                BlockList.erase(it + 1);  
            }  
            else    //都不邻接  
            {  
                (*it).state = true;  
            }  
            break;  
        }  
    }  
  
    for (std::vector<job>::iterator it = JobList.begin(); it != JobList.end(); ++it)  
    {  
        if ((*it).start == start)  
        {  
            (*it).BlockSize = (*it).start = 0;  
            break;  
        }  
    }  
}  

[cpp]view plain copy
//FF.cpp  
#include "BlockJob.h"  
  
//FF算法  
void FF(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
int main()  
{  
    std::vector<block> BlockList;  
    std::vector<job> JobList;  
  
    //初始化空闲分区与作业  
    init(BlockList, JobList);  
  
    //FF算法  
    FF(BlockList, JobList);  
  
    //显示结果  
    show(BlockList, JobList);  
  
    //回收分区  
    recycle(BlockList, JobList);  
  
    //显示结果  
    show(BlockList, JobList);  
  
    return 0;  
}  
  
//FF算法  
void FF(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    for (std::vector<job>::iterator ItJob = JobList.begin(); ItJob != JobList.end(); ++ItJob)  
    {  
        for (std::vector<block>::iterator ItBlock = BlockList.begin(); ItBlock != BlockList.end(); ++ItBlock)  
        {  
            //分区未被使用且能够装下作业  
            if ((*ItBlock).state && (*ItBlock).size >= (*ItJob).size)  
            {  
                if ((*ItBlock).size - (*ItJob).size > MINSIZE)   //剩余空间还可以继续分配  
                {  
                    (*ItBlock).state = false;  
  
                    //修改作业信息，分配空间  
                    (*ItJob).start = (*ItBlock).start;  
                    (*ItJob).BlockSize = (*ItJob).size;  
  
                    //添加新表项  
                    block NewBlock;  
                    NewBlock.start = (*ItBlock).start + (*ItJob).size;  
                    NewBlock.size = (*ItBlock).size - (*ItJob).size;  
                    NewBlock.state = true;  
                    (*ItBlock).size = (*ItJob).size;  
                    BlockList.insert(ItBlock + 1, NewBlock);  
  
                }  
                else        //剩余空间不可分配，全部分配给此作业  
                {  
                    (*ItBlock).state = false;  
  
                    //修改作业信息，分配空间  
                    (*ItJob).start = (*ItBlock).start;  
                    (*ItJob).BlockSize = (*ItBlock).size;  
                }  
  
                break;  
            }  
        }  
    }  
}  

[cpp]view plain copy
//NF.cpp  
#include "BlockJob.h"  
  
//NF算法  
void NF(std::vector<block> &BlockList, std::vector<job> &JobList);  
  
int main()  
{  
    std::vector<block> BlockList;  
    std::vector<job> JobList;  
  
    //初始化空闲分区与作业  
    init(BlockList, JobList);  
  
    //NF算法  
    NF(BlockList, JobList);  
  
    //显示结果  
    show(BlockList, JobList);  
  
    //回收分区  
    recycle(BlockList, JobList);  
  
    //显示结果  
    show(BlockList, JobList);  
  
    return 0;  
}  
  
//NF算法  
void NF(std::vector<block> &BlockList, std::vector<job> &JobList)  
{  
    int pos = 0;        //上一次查找的位置  
  
    for (std::vector<job>::iterator ItJob = JobList.begin(); ItJob != JobList.end(); ++ItJob)  
    {  
        std::vector<block>::iterator ItBlock = BlockList.begin() + pos;  
        do {  
            //分区未被使用且能够装下作业  
            if ((*ItBlock).state && (*ItBlock).size >= (*ItJob).size)  
            {  
                pos = &(*ItBlock) - &BlockList[0];  //记录此次分配位置  
                if ((*ItBlock).size - (*ItJob).size > MINSIZE)   //剩余空间还可以继续分配  
                {  
                    (*ItBlock).state = false;  
  
                    //修改作业信息，分配空间  
                    (*ItJob).start = (*ItBlock).start;  
                    (*ItJob).BlockSize = (*ItJob).size;  
  
                    //添加新表项  
                    block NewBlock;  
                    NewBlock.start = (*ItBlock).start + (*ItJob).size;  
                    NewBlock.size = (*ItBlock).size - (*ItJob).size;  
                    NewBlock.state = true;  
                    (*ItBlock).size = (*ItJob).size;  
                    BlockList.insert(ItBlock + 1, NewBlock);  
  
                }  
                else        //剩余空间不可分配，全部分配给此作业  
                {  
                    (*ItBlock).state = false;  
  
                    //修改作业信息，分配空间  
                    (*ItJob).start = (*ItBlock).start;  
                    (*ItJob).BlockSize = (*ItBlock).size;  
                }  
  
                break;  
            }  
  
            ++ItBlock;  
            if (ItBlock == BlockList.end())  
                ItBlock = BlockList.begin();  
        } while (pos != &(*ItBlock) - &BlockList[0]);  
    }  
}  

首次适应算法(FF)和循环首次适应算法(NF)

首次适应算法(FF)和循环首次适应算法(NF)

相关推荐