OS Lab: Simulation of Dynamic Partition Allocation | Notes / CS基础

This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

MOOC link: Operating System Principles A super interesting dynamic partition allocation simulation — definitely try coding it yourself! The code approach comes from the school’s MOOC, rewritten with minor modifications. The core logic remains unchanged, and no exception handling is included.

I. Experiment Objective

Understand the data structures and allocation algorithms used in dynamic partition allocation, and further deepen the understanding of dynamic partition storage management and its implementation process.

II. Experiment Requirements

(1) Implement the dynamic partition allocation process alloc() and the deallocation process free() using the First Fit algorithm in C language. Free partitions are managed through a free partition chain; during memory allocation, the system prioritizes using the lower end of the free area. (2) Assume the initial available memory space is 640KB, with the following request sequence:

Job 1 requests 130KB
Job 2 releases 60KB
Job 3 requests 100KB
Job 2 releases 60KB
Job 4 requests 200KB
Job 3 releases 100KB
Job 1 releases 130KB
Job 5 requests 140KB
Job 6 requests 60KB
Job 7 requests 50KB
Job 6 releases 60KB.

Use the First Fit algorithm for memory block allocation and deallocation. Display the free memory partition chain status after each allocation and deallocation.

III. Experiment Content

1. Data Structures

Define the request sequence struct, where num represents the job number, state represents whether the job requests or releases space, and len represents the size of space the job requests or releases.

//定义请求序列结构体
struct Allocquery {
    int num;
    char state;  //a表示申请(apply)，f表示释放（free）
    int len;    //长度
    Allocquery(int n = 0, char s = 'f', int l = 0):num(n), state(s), len(l){}
} alocq[MaxNum];

Define the memory allocation queue struct, where flag being 0 indicates the memory block is free, and other values represent the corresponding job. For example, 1 indicates Job 1 is stored there. firstadd represents the starting address of the memory block, and len represents the size of the memory block.

//定义内存分配队列
struct Freequery {
    int flag;   //0表示空闲，其他数值表示相应作业
    int firstadd;   //起始地址
    int len;        //占有长度
    Freequery(int f = 0, int fi = 0, int l = 0) : flag(f), firstadd(fi), len(l) {}
} freeq[MaxNum];

2. Initialization

Read from file. The in.txt content is the job request queue as required: “1 a 130” means Job 1 requests 130KB of space.

1 a 130

2 f 60

3 a 100

2 f 60

4 a 200

3 f 100

1 f 130

5 a 140

6 a 60

7 a 50

6 f 60

Define constants

const string InputFileName = "in.txt";
const string OutputFileName = "out.txt";
const int MaxNum = 11;

First initialize the job request sequence using C++ file streams to initialize each job request.

//初始化作业请求序列
void initAlocq() {
    ifstream infp(InputFileName, ios::in);
    int index = 0;
    while(!infp.eof() && index < MaxNum) {
        int num;
        stringstream ss;
        infp >> alocq[index].num >> alocq[index].state >> alocq[index].len;
        ++index;
    }
    infp.close();
}

Then initialize the memory space. Note that in the Freequery constructor, the default parameter len is initially 0, meaning if len is 0 the memory block does not exist, which can serve as the loop termination condition. So we initially set freeq[0]‘s length to the entire memory space size.

void initFreeq() {
    freeq[0].flag = 0, freeq[0].firstadd = 0, freeq[0].len = 640;
}

3. Main Program

Execute operations for each job request and display the results in the file out.txt. Freetotal represents the number of free memory blocks (initially 1). first_alg is the First Fit algorithm, with parameters being the request block, current free block count, and memory allocation queue.

void Run() {
    ofstream outfp(OutputFileName, ios::out);
    int Freetotal = 1;
    //对每次作业请求执行操作，显示执行结果
    for(int i = 0; i < MaxNum; ++i ) {
        first_alg(alocq[i], Freetotal, freeq);
        outfp << "序列" << i+1 <<  ":作业" << alocq[i].num;
        if(alocq[i].state == 'a') outfp << "申请" << alocq[i].len << "K\n";
        else outfp << "释放" << alocq[i].len << "K\n";
        outfp << "Now total free blocks:" << Freetotal << endl;
        outfp << "IDNum\taddress\t\tlength"<< endl;
        for(int j = 0 ; freeq[j].len != 0; ++j) {
            outfp << "  " << freeq[j].flag << "\t\t   "
                << freeq[j].firstadd << "\t\t  "
                << freeq[j].len << endl;
        }
        outfp << "--------------------------------------------------\n" << endl;

    }
    outfp.close();
}
int main() {
    initAlocq();
    initFreeq();
    Run();
    return 0;
}

First Fit Algorithm, with parameters being the request block, current free block count, and memory allocation queue.

Function declaration:

void first_alg(Allocquery nowaloc, int &ptotal, Freequery *pfreeq);

First determine whether it is a space request or release. If requesting space, traverse all memory blocks. Only when a memory block pfreeq[i] is unallocated and its size is greater than or equal to the requested space, allocate that block to the job and merge free blocks. The detailed merging method is shown in the comments. If releasing space, find the block to be released and free it, then merge adjacent free areas.

//首次适应算法
//参数为请求块、当前空块个数、内存具体使用情况
void first_alg(Allocquery nowaloc, int &ptotal, Freequery *pfreeq){
    Freequery temp;
    Freequery temp_f1, temp_f2;
    if(nowaloc.state == 'a') {
        //申请空间
        for(int i = 0; i < MaxNum; ++i) {
            //该内存块空闲 且空间足以分给该作业
            if(pfreeq[i].flag == 0 && pfreeq[i].len >= nowaloc.len) {
                temp.flag = pfreeq[i].flag;
                temp.firstadd = pfreeq[i].firstadd+nowaloc.len; //首地址下移
                temp.len = pfreeq[i].len-nowaloc.len;           //剩余空间长度
                //找到的空块长度正好等于请求块，则立刻分配
                pfreeq[i].flag = nowaloc.num;
                pfreeq[i].len = nowaloc.len;
                if(pfreeq[i+1].len == 0) {
                    //找到的空块正好是全部剩余空间
                    pfreeq[i+1] = temp;
                } else if (pfreeq[i+1].firstadd != temp.firstadd){
                    //前后被占用，空块在中间，且长度大于请求块
                    temp_f1 = temp;
                    temp_f2 = pfreeq[i+1];
                    int j;
                    for(j = i+1; pfreeq[j].len != 0; ++j) {
                        pfreeq[j] = temp_f1;
                        temp_f1 = temp_f2;
                        temp_f2 = pfreeq[j+1];
                    }
                    pfreeq[j] = temp_f1;
                }
                break;
            }
        }
    } else {
        //释放空间
        for(int i = 0; i < MaxNum; ++i) {
            if(pfreeq[i].flag == nowaloc.num) {
                //找到待回收的块
                if(i > 0 && pfreeq[i-1].flag == 0 && pfreeq[i+1].flag == 0) {
                    //前后都为空块，且回收块的首地址不是0
                    pfreeq[i-1].len = pfreeq[i-1].len + nowaloc.len + pfreeq[i+1].len;
                    for(int j = i; pfreeq[j].len != 0; ++j) {
                            //三块合并后队列变化
                        pfreeq[j] = pfreeq[j+2];
                    }
                } else if(i > 0 && pfreeq[i-1].flag == 0) {
                        //前为空块,后不为空块，且不是首块
                        pfreeq[i-1].len = pfreeq[i-1].len + nowaloc.len;
                        for(int j = i; pfreeq[j].len != 0; ++j) {
                            //两块合并后队列变化
                            pfreeq[j] = pfreeq[j+1];
                        }
                } else if(pfreeq[i+1].flag == 0) {
                    //后为空块
                    pfreeq[i].flag = 0;
                    pfreeq[i].len = nowaloc.len + pfreeq[i+1].len;
                    for(int j = i+1; pfreeq[j].len != 0; ++j) {
                        pfreeq[j] = pfreeq[j+1];
                    }
                } else {
                    //前后都不空
                    pfreeq[i].flag = 0;
                }
            }
        }
    }
    int fnum = 0;   //统计空闲块
    for(int i = 0; pfreeq[i].len != 0; ++i)
        if(pfreeq[i].flag == 0) ++fnum;
    ptotal = fnum;
}

IV. Experiment Results

V. Complete Code

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
using namespace std;
const string InputFileName = "in.txt";
const string OutputFileName = "out.txt";
const int MaxNum = 11;
//定义请求序列结构体
struct Allocquery {
    int num;
    char state;  //a表示申请(apply)，f表示释放（free）
    int len;    //长度
    Allocquery(int n = 0, char s = 'f', int l = 0):num(n), state(s), len(l){}
} alocq[MaxNum];
//定义内存分配队列
struct Freequery {
    int flag;   //0表示空闲，其他数值表示相应作业
    int firstadd;   //起始地址
    int len;        //占有长度
    Freequery(int f = 0, int fi = 0, int l = 0) : flag(f), firstadd(fi), len(l) {}
} freeq[MaxNum];

//首次适应算法
//参数为请求块、当前空块个数、内存分配队列
void first_alg(Allocquery nowaloc, int &ptotal, Freequery *pfreeq);

//初始化作业请求序列
void initAlocq() {
    ifstream infp(InputFileName, ios::in);
    int index = 0;
    while(!infp.eof() && index < MaxNum) {
        int num;
        stringstream ss;
        infp >> alocq[index].num >> alocq[index].state >> alocq[index].len;
        //cout << alocq[index].num << ' ' << alocq[index].state << ' ' << alocq[index].len << endl;
        ++index;
    }
    infp.close();
}
//初始化内存空间
void initFreeq() {
    freeq[0].flag = 0, freeq[0].firstadd = 0, freeq[0].len = 640;
}
void Run() {
    ofstream outfp(OutputFileName, ios::out);
    int Freetotal = 1;
    //对每次作业请求执行操作，显示执行结果
    for(int i = 0; i < MaxNum; ++i ) {
        first_alg(alocq[i], Freetotal, freeq);
        outfp << "序列" << i+1 <<  ":作业" << alocq[i].num;
        if(alocq[i].state == 'a') outfp << "申请" << alocq[i].len << "K\n";
        else outfp << "释放" << alocq[i].len << "K\n";
        outfp << "Now total free blocks:" << Freetotal << endl;
        outfp << "IDNum\taddress\t\tlength"<< endl;
        for(int j = 0 ; freeq[j].len != 0; ++j) {
            outfp << "  " << freeq[j].flag << "\t\t   "
                << freeq[j].firstadd << "\t\t  "
                << freeq[j].len << endl;
        }
        outfp << "--------------------------------------------------\n" << endl;

    }
    outfp.close();
}
int main() {
    initAlocq();
    initFreeq();
    Run();
    return 0;
}
//首次适应算法
//参数为请求块、当前空块个数、内存具体使用情况
void first_alg(Allocquery nowaloc, int &ptotal, Freequery *pfreeq){
    Freequery temp;
    Freequery temp_f1, temp_f2;
    if(nowaloc.state == 'a') {
        //申请空间
        for(int i = 0; i < MaxNum; ++i) {
            //该内存块空闲 且空间足以分给该作业
            if(pfreeq[i].flag == 0 && pfreeq[i].len >= nowaloc.len) {
                temp.flag = pfreeq[i].flag;
                temp.firstadd = pfreeq[i].firstadd+nowaloc.len; //首地址下移
                temp.len = pfreeq[i].len-nowaloc.len;           //剩余空间长度
                //找到的空块长度正好等于请求块，则立刻分配
                pfreeq[i].flag = nowaloc.num;
                pfreeq[i].len = nowaloc.len;
                if(pfreeq[i+1].len == 0) {
                    //找到的空块正好是全部剩余空间
                    pfreeq[i+1] = temp;
                } else if (pfreeq[i+1].firstadd != temp.firstadd){
                    //前后被占用，空块在中间，且长度大于请求块
                    temp_f1 = temp;
                    temp_f2 = pfreeq[i+1];
                    int j;
                    for(j = i+1; pfreeq[j].len != 0; ++j) {
                        pfreeq[j] = temp_f1;
                        temp_f1 = temp_f2;
                        temp_f2 = pfreeq[j+1];
                    }
                    pfreeq[j] = temp_f1;
                }
                break;
            }
        }
    } else {
        //释放空间
        for(int i = 0; i < MaxNum; ++i) {
            if(pfreeq[i].flag == nowaloc.num) {
                //找到待回收的块
                if(i > 0 && pfreeq[i-1].flag == 0 && pfreeq[i+1].flag == 0) {
                    //前后都为空块，且回收块的首地址不是0
                    pfreeq[i-1].len = pfreeq[i-1].len + nowaloc.len + pfreeq[i+1].len;
                    for(int j = i; pfreeq[j].len != 0; ++j) {
                            //三块合并后队列变化
                        pfreeq[j] = pfreeq[j+2];
                    }
                } else if(i > 0 && pfreeq[i-1].flag == 0) {
                        //前为空块,后不为空块，且不是首块
                        pfreeq[i-1].len = pfreeq[i-1].len + nowaloc.len;
                        for(int j = i; pfreeq[j].len != 0; ++j) {
                            //两块合并后队列变化
                            pfreeq[j] = pfreeq[j+1];
                        }
                } else if(pfreeq[i+1].flag == 0) {
                    //后为空块
                    pfreeq[i].flag = 0;
                    pfreeq[i].len = nowaloc.len + pfreeq[i+1].len;
                    for(int j = i+1; pfreeq[j].len != 0; ++j) {
                        pfreeq[j] = pfreeq[j+1];
                    }
                } else {
                    //前后都不空
                    pfreeq[i].flag = 0;
                }
            }
        }
    }
    int fnum = 0;   //统计空闲块
    for(int i = 0; pfreeq[i].len != 0; ++i)
        if(pfreeq[i].flag == 0) ++fnum;
    ptotal = fnum;
}