精华内容
下载资源
问答
  • 精品文档 课程设计报告 设计题目 内存的连续分配算法 班级 : 学号 姓名 指导老师 设计时间 摘要 精品文档 精品文档 1主要算法包括 固定分区分配动态分区分配伙伴算法可重定位分区分配 2 内容要求 1定义与算法相关的...
  • 课程设计报告 设计题目内存的连续分配算法 班级 : 学号 姓名 指导老师 设计时间 2012年8月 1 摘要 1主要算法包括 固定分区分配动态分区分配伙伴算法可重定位分区分配 2内容要求 1定义与算法相关的数据结构如PCB空闲...
  • 动态分区分配算法

    千次阅读 2019-06-21 21:40:30
    掌握动态分区分配方式中的数据结构、分配算法,针对不同的分配算法如何实现内存空间的分配与回收,必要时如何实现“紧凑”。

    1.实验步骤:

    主函数:一个菜单栏的形式,可以选择要执行的算法。
    首次适应算法:每次都从开始往后找满足条件的分区。
    循环首次适应算法:从前一次找到的地方往后继续找分区。
    最佳适应算法:先从小到大排序,找比前一个大后一个小的分区。

    2.算法描述:

    1.首次适应算法:该算法从空闲分区链首开始查找,直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存分配给请求者,余下的空闲分区仍留在空闲分区链中。
    2.循环首次适应算法:该算法是首次适应算法的变种。在分配内存空间时,不再每次从表头(链首)开始查找,而是从上次找到空闲区的下一个空闲开始查找,直到找到第一个能满足要求的的空闲区为止,并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。
    3.最佳适应算法: 该算法总是把既能满足要求,又是最小的空闲分区分配给作业。为了加速查找,该算法要求将所有的空闲区按其大小排序后,以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区,必然是最优的。孤立地看,该算法似乎是最优的,但事实上并不一定。因为每次分配后剩余的空间一定是最小的,在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序,这也带来了一定的开销。

    3.源代码:

    #include <iostream>
    #include <fstream>
    #include <string>
    using namespace std;
    struct info{
    	int quhao;	//区号 
    	int dress;	//起始地址 
    	int num;	//大小 
    	int free;	//是否空闲 
    	string name; //进程名 
    };
    info IN[100];	//原始内存分配表 
    int Kong[100];//空闲分区表 
    int Ready[100];//已分配分区表 
    
    //初始化分区 
    void init(){
    	Kong[0]=0;
    	ifstream fen("data.txt");
    //	从文件中导入内存分区表 
    	for(int i=0;i<5;i++){
    		fen>>IN[i].quhao>>IN[i].dress>>IN[i].num>>IN[i].free; 
    		Kong[i+1]=i; 
    		Kong[0]+=1;
    	}
    	fen.close();
    	cout<<"原始内存分区"<<endl;
    	cout<<"区号 地址 大小 空闲"<<endl;
    	for(int i=0;i<5;i++){
    		cout<<IN[i].quhao<<"    "<<IN[i].dress<<"   "<<IN[i].num<<"  "<<IN[i].free<<endl; 
    	} 
    }
    
    //显示空闲分区列表 
    void disp(){
    	cout<<"空闲分区列表"<<endl;
    	for(int i=0;i<5;i++){
    		if(IN[Kong[i+1]].free==1)
    			cout<<IN[i].quhao<<" "<<IN[i].num<<endl;
    	} 
    } 
    
    //内存紧凑
    void Jin(int n){
    	int free=0;
    	for(int i=0;i<5;i++){
    		free+=IN[Kong[i+1]].num;
    	}
    	if(free>=n){
    		cout<<"通过紧凑操作后可以进行分配"<<endl;
    	}
    } 
    
    //首次适应算法 
    void FirstFit(){
    	int n,i,flag=0;
    	string name;
    	init();	//初始化分区表 	
    //	请求进程,直到请求的进程大小为0时停止 
    	cout<<"请输入要申请的空间大小"<<endl;
    	cin>>n;
    	while(n){
    		cout<<"请输入进程名"<<endl;
    		cin>>name;
    //		从空闲列表开始向后面查找满足条件的内存区 
    		for(i=0;i<Kong[0];i++){
    			if(IN[Kong[i+1]].num>=n&&IN[Kong[i+1]].free==1){
    				IN[Kong[i+1]].name=name;
    				IN[Kong[i+1]].free=0;//不空闲 
    				IN[Kong[i+1]].num-=n;//减去空间大小 
    				cout<<"分配区号:"<<IN[Kong[i+1]].quhao<<endl;
    				flag=1;
    				break;
    			}
    		} 
    //		若找不到合适的内存区则输出报错信息 
    		if(flag==0){
    			cout<<"分配失败,没有合适的内存区"<<endl;
    		}
    		flag=0;
    		disp();	//显示现在空闲区的情况 
    		cout<<"请输入要申请的空间大小"<<endl;
    		cin>>n;
    	}
    	
    }
    
    
    //循环首次适应算法
    void NextFit() {
    	int n,i,flag=0;
    	int xian;//保存上个分配区间的地址 
    	string name;
    	init();
    	cout<<"请输入要申请的空间大小"<<endl;
    	cin>>n;
    	while(n){
    		cout<<"请输入进程名"<<endl;
    		cin>>name;
    //		从上次分配的区块开始分配 
    		for(i=xian;i<Kong[0];i++){
    			if(IN[Kong[i+1]].num>=n&&IN[Kong[i+1]].free==1){
    				IN[Kong[i+1]].name=name;
    				IN[Kong[i+1]].free=0;
    				IN[Kong[i+1]].num-=n;//减去空间大小 
    				cout<<"分配区号:"<<IN[Kong[i+1]].quhao<<endl;
    				xian=i;
    				flag=1;
    				break;
    			}
    		} 
    		if(flag==0){
    			for(i=0;i<xian;i++){
    				if(IN[Kong[i+1]].num>=n&&IN[Kong[i+1]].free==1){
    				IN[Kong[i+1]].name=name;
    				IN[Kong[i+1]].free=0;
    				IN[Kong[i+1]].num-=n;//减去空间大小 
    				cout<<"分配区号:"<<IN[Kong[i+1]].quhao<<endl;
    				xian=i;
    				flag=1;
    				break;
    			}
    			}
    		}
    		if(flag==0){
    			cout<<"内存分配失败"<<endl;
    		}
    		disp();
    		cout<<"请输入要申请的空间大小"<<endl;
    		cin>>n;
    	}
    }
    
    //	按大小从小到大排序 
    void sort(){
    	int i,j;
    	for(i=0;i<5;i++){
    		for(j=1;j<5-i;j++){
    			if(IN[Kong[j+1]].num<IN[Kong[j]].num){
    				swap(Kong[j+1],Kong[j]);
    			}
    		}
    	} 
    //	显示排序后信息
    	cout<<"排序后的结果:"<<endl;
    	cout<<"区号 地址 大小 空闲"<<endl;
    	for(int i=0;i<5;i++){
    		cout<<IN[Kong[i+1]].quhao<<"    "<<IN[Kong[i+1]].dress<<"   "<<IN[Kong[i+1]].num<<"  "<<IN[Kong[i+1]].free<<endl; 
    	} 	 
    } 
    
    //最佳适应算法
    void BestFit(){
    	int i,n,flag=0;
    	string name;
    	init();
    	sort();//给空闲分区按大小从小到大排序
    	cout<<"请输入要申请的空间大小"<<endl;
    	cin>>n;
    	while(n){
    		cout<<"请输入进程名"<<endl;
    		cin>>name;
    		if(IN[Kong[1]].num>=n){
    			IN[Kong[1]].name=name;
    			IN[Kong[1]].free=0;
    			IN[Kong[1]].num-=n;//减去空间大小 
    			cout<<"分配区号:0"<<endl; 
    			flag=1;
    		}
    		else{
    			for(i=1;i<Kong[0];i++){
    			if(IN[Kong[i+1]].num>=n&&IN[Kong[i]].num<n&&IN[Kong[i+1]].free==1){
    				IN[Kong[i+1]].name=name;
    				IN[Kong[i+1]].free=0;
    				IN[Kong[i+1]].num-=n;//减去空间大小 
    				cout<<"分配区号:"<<IN[Kong[i+1]].quhao<<endl;
    				flag=1;
    				break;
    			}
    		} 
    		}	
    //		若找不到合适的内存区则输出报错信息 
    		if(flag==0){
    			cout<<"分配失败,没有合适的内存区"<<endl;
    		}
    		flag=0;
    		disp();	//显示现在空闲区的情况 
    		cout<<"请输入要申请的空间大小"<<endl;
    		cin>>n;
    	}
    } 
    
    int main(){
    	int lx; //算法类型 
    	cout<<"请选择一种算法:"<<endl;
    	cout<<"1.首次适应算法"<<endl;
    	cout<<"2.循环首次适应算法"<<endl;
    	cout<<"3.最佳适应算法"<<endl;
    	cout<<"0.退出"<<endl;
    	cin>>lx;
    //	利用不同算法进行动态分区分配,直到输入为0 
    	while(lx){
    		switch(lx){
    		case 1:FirstFit();
    		case 2:NextFit();
    		case 3:BestFit();			
    		}
    		cout<<"请选择一种算法:" ;
    		cout<<"1.首次适应算法"<<endl;
    		cout<<"2.循环首次适应算法"<<endl;
    		cout<<"3.最佳适应算法"<<endl;
    		cout<<"0.退出"<<endl;
    		cin>>lx;
    	}
    	return 0;
    }
    
    展开全文
  • 在划分时,若剩余的内存小于等于minsize,则将整块内存分配给该进程不再进行划分。 根据菜单选择相应的操作: 1.初始化:输入内存的大小和阈值minsize,初始状态下空闲分区名字为“void”。 2.分配:输入申请进程的...

    内存分区分配–首次适应算法

    输入内存的大小和阈值minsize,按照首次适应算法进行连续的分区分配。在划分时,若剩余的内存小于等于minsize,则将整块内存分配给该进程不再进行划分。 根据菜单选择相应的操作:

    1.初始化:输入内存的大小和阈值minsize,初始状态下空闲分区名字为“void”。

    2.分配:输入申请进程的名字、大小。

    • 若可以分配,显示“分配成功!”;
    • 若剩余空间不足,显示不分配原因“剩余空间不足,不予分配。”;
    • 若剩余的空间通过紧凑技术,可以再分配,提示“是否通过紧凑技术,重新划分?(Y/N)”若选择“Y”,通过紧凑技术重新划分并分配,成功后,显示“分配成功!”若选择“N”,则输出“没有合适的剩余空间,不予分配。”

    3.回收:输入回收进程的名字,若有相邻空闲分区,需要合并,并输出“回收成功!”;若输入错误,提示“查无此分区!” 4.显示:显示当前内存的分配状态。

    0.退出

    其他:输出“输入错误,请重新输入。”

    输入格式:

    先进行初始化后,按照菜单进行相应的操作。

    输出格式:

    菜单只显示一次,按照相应的选择输出。

    输入样例1:

    在这里给出一组输入。例如:

    1
    1024 5
    4
    0
    

    输出样例1:

    在这里给出相应的输出。例如:

    1.初始化
    2.分配
    3.回收
    4.显示
    0.退出
    请选择:
    分区号 分区 起始地址 结束地址 大小 当前状态
    1 void 0 1023 1024 空闲
    

    输入样例2:

    在这里给出一组输入。例如:

    1
    1000 5
    2
    A 100
    2
    B 200
    2
    C 150
    2
    D 250
    2
    E 200
    2
    F 95
    4
    0
    

    输出样例2:

    在这里给出相应的输出。例如:

    1.初始化
    2.分配
    3.回收
    4.显示
    0.退出
    请选择:
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    分区号 分区 起始地址 结束地址 大小 当前状态
    1 A 0 99 100 已分配
    2 B 100 299 200 已分配
    3 C 300 449 150 已分配
    4 D 450 699 250 已分配
    5 E 700 899 200 已分配
    6 F 900 999 100 已分配
    

    输入样例3:

    在这里给出一组输入。例如:

    1
    1000 5
    2
    A 100
    2
    B 200
    2
    C 150
    2
    D 250
    2
    E 200
    2
    F 150
    4
    0
    

    输出样例3:

    在这里给出相应的输出。例如:

    1.初始化
    2.分配
    3.回收
    4.显示
    0.退出
    请选择:
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    剩余空间不足,不予分配。
    分区号 分区 起始地址 结束地址 大小 当前状态
    1 A 0 99 100 已分配
    2 B 100 299 200 已分配
    3 C 300 449 150 已分配
    4 D 450 699 250 已分配
    5 E 700 899 200 已分配
    6 void 900 999 100 空闲
    

    输入样例4:

    在这里给出一组输入。例如:

    1
    1000 5
    2
    A 100
    2
    B 200
    2
    C 150
    2
    D 250
    2
    E 200
    2
    F 150
    3
    A
    4
    0
    

    输出样例4:

    在这里给出相应的输出。例如:

    1.初始化
    2.分配
    3.回收
    4.显示
    0.退出
    请选择:
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    剩余空间不足,不予分配。
    回收成功!
    分区号 分区 起始地址 结束地址 大小 当前状态
    1 void 0 99 100 空闲
    2 B 100 299 200 已分配
    3 C 300 449 150 已分配
    4 D 450 699 250 已分配
    5 E 700 899 200 已分配
    6 void 900 999 100 空闲
    

    输入样例5:

    在这里给出一组输入。例如:

    1
    1000 5
    2
    A 100
    2
    B 200
    2
    C 150
    2
    D 250
    2
    E 200
    2
    F 150
    3
    A
    2
    X 150
    Y
    4
    0
    

    输出样例5:

    在这里给出相应的输出。例如:

    1.初始化
    2.分配
    3.回收
    4.显示
    0.退出
    请选择:
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    分配成功!
    剩余空间不足,不予分配。
    回收成功!
    是否通过紧凑技术,重新划分?(Y/N)
    分配成功!
    分区号 分区 起始地址 结束地址 大小 当前状态
    1 B 0 199 200 已分配
    2 C 200 349 150 已分配
    3 D 350 599 250 已分配
    4 E 600 799 200 已分配
    5 X 800 949 150 已分配
    6 void 950 999 50 空闲
    
    import java.awt.*;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Objects;
    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            int choice,merSize = 0,minSize = 0,merSizeStart = 0,resultNumber = 0;
            boolean flagTar;
            int requireSize = 0,flagNumber = -1;
            String proName,strTar;
            Scanner sc  = new Scanner(System.in);
            List<Part> parts = new ArrayList<>();
            System.out.println("1.初始化\n" + "2.分配\n" + "3.回收\n" + "4.显示\n" + "0.退出");
            System.out.println("请选择:");
            choice = sc.nextInt();
    
            while (choice!=0){
                switch (choice){
    
                    //初始化=>输入内存的大小和阈值minsize,初始状态下空闲分区名字为“void”。
                    case 1:
                        merSize = sc.nextInt();
                        minSize = sc.nextInt();
                        merSizeStart = merSize;
                        Part partStart = new Part(-3,"void",0,merSize-1,merSize,"空闲");
                        parts.add(partStart);
                        break;
    
                    //分配=>输入申请进程的名字、大小
                    case 2:
                        if("void".equals(parts.get(0).partName)&&parts.get(0).size == merSizeStart){
                            parts.remove(0);  //删除第一次的void分区
                        }
    
                        proName = sc.next();
                        requireSize = sc.nextInt();
    
                        flagTar = alloction(parts,merSize,minSize,proName,requireSize);
    
                        if (flagTar){
                            System.out.println("是否通过紧凑技术,重新划分?(Y/N)");
                            strTar = sc.next();
                            if (strTar.equals("N"))
                                System.out.println("没有合适的剩余空间,不予分配。");
                            else {
                                //直接进行紧凑分配
                                resultNumber = compact(parts,proName,requireSize,merSize,minSize);
                                System.out.println("分配成功!");
                            }
                        }
                        if(flagTar) merSize = resultNumber;
                        else if (merSize - requireSize <= minSize && merSize - requireSize >0) merSize = 0;
                        else if (merSize - requireSize >0&&resultNumber == 0)
                            merSize -=requireSize;
                        else if (resultNumber!=0)merSize  = resultNumber;
                        break;
    
                    //回收=>输入回收进程的名字,若有相邻空闲分区,需要合并,并输出“回收成功!”;若输入错误,提示“查无此分区!”
                    case 3:
                        int flag = -1;
                        proName = sc.next();
                        for (int i = 0; i < parts.size(); i++) {
                            if (proName.equals(parts.get(i).partName)) {
                                flag = i;
                                break;
                            }
                        }
                        if (flag != -1){
                            //进行内存回收
                            recovery(parts,flag);
                        } else
                            System.out.println("查无此分区!");
                        break;
    
                    //显示=>显示当前内存的分配状态。
                    case 4:
                        flagNumber = printList(parts,merSize,minSize,merSizeStart);
                        if (flagNumber != 0) merSize = flagNumber;
                        break;
    
                    default:
                        System.out.println("输入错误,请重新输入。");
                        break;
                }
                choice = sc.nextInt();
            }
    
        }
    
        //分区类Part
        static class Part{
            int partNumber;
            String partName;
            int startAddr,endAddr;
            int size;
            String state;
    
            public Part() {
            }
    
            public Part(int partNumber, String partName, int startAddr, int endAddr, int size, String state) {
                this.partNumber = partNumber;
                this.partName = partName;
                this.startAddr = startAddr;
                this.endAddr = endAddr;
                this.size = size;
                this.state = state;
            }
    
            public int getPartNumber() {
                return partNumber;
            }
    
            public void setPartNumber(int partNumber) {
                this.partNumber = partNumber;
            }
    
            public String getPartName() {
                return partName;
            }
    
            public void setPartName(String partName) {
                this.partName = partName;
            }
    
            public int getStartAddr() {
                return startAddr;
            }
    
            public void setStartAddr(int startAddr) {
                this.startAddr = startAddr;
            }
    
            public int getEndAddr() {
                return endAddr;
            }
    
            public void setEndAddr(int endAddr) {
                this.endAddr = endAddr;
            }
    
            public int getSize() {
                return size;
            }
    
            public void setSize(int size) {
                this.size = size;
            }
    
            public String getState() {
                return state;
            }
    
            public void setState(String state) {
                this.state = state;
            }
    
            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Part part = (Part) o;
                return partNumber == part.partNumber &&
                        startAddr == part.startAddr &&
                        endAddr == part.endAddr &&
                        size == part.size &&
                        Objects.equals(partName, part.partName) &&
                        Objects.equals(state, part.state);
            }
    
            @Override
            public int hashCode() {
    
                return Objects.hash(partNumber, partName, startAddr, endAddr, size, state);
            }
        }
    
        //分配函数
        public static boolean alloction(List<Part> parts,int merSize,int minSize,String proName,int requireSize){
    
            int restSpace = 0,tmp = 0,restSpace01 = 0;
            boolean flag = false,flagTmp = false,flag01 = false;
    
            for (int i = 0; i < parts.size(); i++) {
                if (parts.get(i).state.equals("空闲")&&parts.get(i).size >= requireSize){
                    tmp = i;
                    flagTmp = true;
                    break;
                }
                if (parts.get(i).state.equals("空闲"))
                    restSpace01+=parts.get(i).size;
            }
    
            if (flagTmp){
                if (parts.get(tmp).size - requireSize <= minSize){
                    parts.add(tmp,new Part(1,proName,parts.get(parts.size()-1).endAddr+1,
                            parts.get(parts.size()-1).endAddr+parts.get(tmp).size,parts.get(tmp).size,"已分配"));
                    parts.get(tmp+1).size = 0;
                } else{
                    parts.add(tmp,new Part(1,proName,parts.get(parts.size()-1).endAddr+1,
                            parts.get(parts.size()-1).endAddr+requireSize,requireSize,"已分配"));
                    parts.get(tmp+1).endAddr -= requireSize;
                    parts.get(tmp+1).size -= requireSize;
                }
                        if (parts.get(tmp+1).size == 0)
                                parts.remove(tmp+1);
                        //更新数据
                for (int i = 0; i < parts.size(); i++) {
                    if (i == 0){
                        parts.get(0).setStartAddr(0);
                        parts.get(0).setEndAddr(parts.get(0).size-1);
                    }else {
                        parts.get(i).startAddr = parts.get(i-1).endAddr + 1;
                        parts.get(i).endAddr = parts.get(i-1).endAddr + parts.get(i).size ;
                    }
                }
                System.out.println("分配成功!");
            }else if(restSpace01 >= requireSize){
                flag = true;
                flag01 = true;
            } else if(merSize >= requireSize&& flag01 == false){
                if (parts.size() == 0){
                    if(merSize-requireSize<=minSize)
                        parts.add(new Part(1,proName,0,merSize-1,merSize,"已分配"));
                    else
                        parts.add(new Part(1,proName,0,requireSize-1,requireSize,"已分配"));
                }
                else{
                    int startAddr = parts.get(parts.size()-1).size + parts.get(parts.size()-1).startAddr;
                    if (merSize-requireSize<=minSize){
                        parts.add(new Part(1,proName,startAddr,startAddr + merSize - 1,merSize,"已分配"));
                    }else
                        parts.add(new Part(1,proName,startAddr,startAddr + requireSize - 1,requireSize,"已分配"));
                }
                System.out.println("分配成功!");
            }else {
                //循环遍历parts数组,找出“空闲”的被回收的内存区域,再加上没有被分配的内存区域,是否够紧凑分配的
                for (Part part : parts) {
                    if("空闲".equals(part.state))
                        restSpace += part.size;
                }
                //空闲资源加上剩下没有被分配的空间是否大于需要的空间
                if (restSpace+merSize >= requireSize){
                    flag = true;
                }else{
                    System.out.println("剩余空间不足,不予分配。");
                }
            }
            return flag;
        }
    
        //紧凑分配
        public static int compact(List<Part> parts, String proName, int requireSize, int merSize,int minSize){
            int flag = 0,restSpace = 0;
    
            flag1:
            for (int i = 0; i < parts.size(); i++) {
                //可能会报错i+1数组越界,不过问题不大
                if (parts.get(i).state.equals("空闲") && i == 0 ){
                    parts.get(i+1).startAddr = 0;
                    parts.get(i+1).endAddr = parts.get(i+1).size-1;
                    merSize += parts.get(i).size;
                    if (merSize >= requireSize){
                        //partNumber赋值-1 一会儿作为标志删除对应的空闲区域
                        parts.get(0).partNumber = -1;
                        flag = 1;
                        i++;
                        continue flag1;
                    }
                }else if (parts.get(i).state.equals("空闲")){
                    //回收之后造成的碎片化
                    parts.get(i+1).startAddr = parts.get(i).startAddr;
                    parts.get(i+1).endAddr = parts.get(i).endAddr + parts.get(i+1).size ;
                    merSize += parts.get(i).size;
                    if (merSize >= requireSize){
                        parts.get(i).partNumber = -1;
                        flag =1;
                        i++;
                        continue flag1;
                    }
                }
            }
    
            //对刚才标记partNumber为-1的进程进行删除
            for (int i = 0; i < parts.size(); i++) {
                if (parts.get(i).partNumber == -1|| parts.get(i).state.equals("空闲")) {
                    //remove之后数组索引重新从0开始
                    parts.remove(i);
                    i--;
                }
            }
    
            //对各个内存进行更新
            for (int i = 0; i < parts.size(); i++) {
                if (i != 0){
                    parts.get(i).startAddr = parts.get(i-1).endAddr + 1;
                    parts.get(i).endAddr = parts.get(i).startAddr + parts.get(i).size -1;
                }
            }
            merSize -=requireSize;
            if(merSize <= minSize){
                parts.add(new Part(1,proName,parts.get(parts.size()-1).endAddr+1,
                        parts.get(parts.size()-1).endAddr+requireSize+merSize,requireSize+merSize,"已分配"));
                merSize = 0;
            }else
                //添加新的请求内存分区
                parts.add(new Part(1,proName,parts.get(parts.size()-1).endAddr+1,
                        parts.get(parts.size()-1).endAddr+requireSize,requireSize,"已分配"));
    
            return merSize;
        }
    
        //进行内存回收
        public static void recovery(List<Part> parts,int targetIndex){
            if(targetIndex == 0 && parts.size() == 1){
                parts.get(0).partName = "void";
                parts.get(0).state = "空闲";
            }else if (targetIndex == 0&&parts.get(targetIndex+1).state.equals("已分配")){
                parts.get(0).partName = "void";//开头结尾的判断
                parts.get(0).state = "空闲";
            }else if (targetIndex == 0&&parts.get(targetIndex+1).state.equals("空闲")){
                parts.get(targetIndex).partName = "void";
                parts.get(targetIndex).endAddr += parts.get(targetIndex+1).size;
                parts.get(targetIndex).size += parts.get(targetIndex+1).size;
                parts.remove(targetIndex+1);
            }
            else if (targetIndex == parts.size()-1&&parts.get(targetIndex-1).state.equals("已分配")){
                parts.get(targetIndex).partName = "void";
                parts.get(targetIndex).state = "空闲";
            }else if (targetIndex == parts.size()-1&&parts.get(targetIndex-1).state.equals("空闲")){
                parts.get(targetIndex-1).partName = "void";
                parts.get(targetIndex-1).endAddr += parts.get(targetIndex).size;
                parts.get(targetIndex-1).size += parts.get(targetIndex).size;
                parts.remove(targetIndex);
            }
            else if (parts.get(targetIndex-1).state.equals("空闲")&&parts.get(targetIndex+1).state.equals("已分配")){
                parts.get(targetIndex-1).partName = "void";
                parts.get(targetIndex-1).endAddr += parts.get(targetIndex).size;
                parts.get(targetIndex-1).size += parts.get(targetIndex).size;
                parts.remove(targetIndex);
            }else if (parts.get(targetIndex+1).state.equals("空闲")&&parts.get(targetIndex-1).state.equals("已分配")){
                parts.get(targetIndex).partName = "void";
                parts.get(targetIndex).endAddr += parts.get(targetIndex+1).size;
                parts.get(targetIndex).size += parts.get(targetIndex+1).size;
                parts.remove(targetIndex+1);
            }else if (parts.get(targetIndex-1).state.equals("空闲")&&parts.get(targetIndex+1).state.equals("空闲")){
                parts.get(targetIndex-1).partName = "void";
                parts.get(targetIndex-1).endAddr =  parts.get(targetIndex).size + parts.get(targetIndex+1).size + parts.get(targetIndex-1).endAddr;
                parts.get(targetIndex-1).size =  parts.get(targetIndex).size + parts.get(targetIndex+1).size + parts.get(targetIndex-1).size;
                parts.remove(targetIndex);
                parts.remove(targetIndex);
            }else {
                parts.get(targetIndex).partName = "void";
                parts.get(targetIndex).state = "空闲";
            }
    
            for (int i = 0; i < parts.size(); i++) {
                if (i != 0){
                    parts.get(i).startAddr = parts.get(i-1).endAddr + 1;
                    parts.get(i).endAddr = parts.get(i).startAddr + parts.get(i).size -1;
                }
            }
            System.out.println("回收成功!");
        }
    
        //打印函数
        public static int printList(List<Part> parts,int merSize,int minSize,int initMerSize){
            int flag = 0;
            for (Part part : parts) {
                initMerSize -= part.size;
            }
            merSize = initMerSize;
            //最后查看是否初始的内存资源分配完全
            if (merSize != 0&&parts.get(parts.size()-1).partNumber!=-3){
                if (parts.get(parts.size()-1).state.equals("空闲")){
                    parts.get(parts.size()-1).endAddr += merSize;
                    parts.get(parts.size()-1).size += merSize;
                }else
                    parts.add(new Part(1,"void",parts.get(parts.size()-1).endAddr+1,
                            parts.get(parts.size()-1).endAddr+merSize,merSize,"空闲"));
            }
    
            int i = 1;
            System.out.println("分区号 分区 起始地址 结束地址 大小 当前状态");
            for (Part part : parts) {
                System.out.println(i++ +" "+part.partName+" "+part.startAddr+" "+part.endAddr+" "+part.size+" "+part.state);
            }
            if(parts.size() != 1&&parts.get(parts.size()-1).state.equals("空闲"))
                flag = parts.remove(parts.size()-1).size;
            if (parts.size() == 1&&parts.get(0).state.equals("空闲")) flag = parts.get(0).size;
            return  flag;
        }
    }
    
    展开全文
  • 操作系统的课程设计报告...用C语言编写的程序,实现了可重定向动态分区分配算法,选取首次适应算法,实现紧凑功能,用单链表模拟内存状态。因为网上几乎没有紧凑功能的代码,所以自己写了,希望造福人类。可能有些小bug
  • 分配功能:要求至少使用两种算法,用户可以选择使用。 回收功能: 空闲块的合并:即紧凑功能,用以消除碎片。当做碎片整理时,需要跟踪分配的空间,修改其引用以保证引用的正确性。 显示当前内存的使用状态...
  • 用C++实现一个完整的(可变)动态分区管理器,包括分配,回收,分区碎片整理等。实现如下功能: 1.初始化功能:内存状态设置为初始状态。 2.分配功能:要求至少使用两种算法,用户可以选择使用...该算法分配和释放的
    用C++实现一个完整的(可变)动态分区管理器,包括分配,回收,分区碎片整理等。实现如下功能:
    

    1.初始化功能:内存状态设置为初始状态。
    2.分配功能:要求至少使用两种算法,用户可以选择使用。
    3.回收功能:
    4.空闲块的合并:即紧凑功能,用以消除碎片。当做碎片整理时,需要跟踪分配的空间,修改其引用以保证引用的正确性。
    5.显示当前内存的使用状态,可以使用表格或图形。
    实现分配功能的4种算法:
    1.最先匹配法(first-fit):按分区的先后次序,从头查找,找到符合要求的第一个分区。
    该算法的分配和释放的时间性能较好,较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分而产生较多小分区,每次分配时查找时间开销会增大。
    2.下次匹配法(next-fit):按分区的先后次序,从上次分配的分区开始查找(到最后分区时再回到开头),找到符合要求的第一个分区。
    该算法的分配和释放的时间性能较好,使空闲分区分布的更均匀,但较大的空闲分区不易保留。
    3.最佳分配法(best-fit):找打大小与要求相差最小的空闲区。
    从个别来看,外碎片较小,但从整体来看,会形成较多外碎片。较大的空闲分区可以保留。
    4.最坏匹配法(worst-fit):找到最大的空闲分区。
    基本不留下小空闲分区,但较大的空闲分区不被保留。

    展开全文
  • 思路:分配内存: 总是分配相邻的存储位置;  释放内存:若删除链表中的一个元素,导致存储位置中间空了一个,让数组的最后一个元素补上,并修改其prev和next值 代码: #include #include using namespace std...

    问题:双向链表的所有m个元素在存储器中保持紧凑,即在多数组表示中占用前m个下标

    思路:分配内存: 总是分配相邻的存储位置;

        释放内存:若删除链表中的一个元素,导致存储位置中间空了一个,让数组的最后一个元素补上,并修改其prev和next值

    代码:

    #include<iostream>
    #include <iomanip> 
    
    using namespace std;
    
    int n=15, f=-1, head=-1;//n为数组大小,f为目前已存值的下标,head为链表表头
    
    void Insert(int *key, int *next, int *prev, int x)
    {
    	if(f==n-1)//检测上溢
    		cout<<"overflow"<<endl;	
    	else
    	{
    		++f;
    		key[f]=x;
    		next[f]=head;     //对应x.next=head
    		if(head>=0)       //对应if(head!=NULL)
    			prev[head]=f; //对应head.prev=x
    		head=f;	          //对应head=x
    		prev[f]=-1;       //对应x.prev=NULL
    	}	
    } 
    
    void Delete(int *key, int *next, int *prev, int x)
    {
    	if(f==-1)//检测上溢
    	{
    		cout<<"underflow"<<endl;
    		return;
    	}
    	int i=0;
    	//找到元素i的位置
    	while(i<=f && key[i]!=x)
    		++i;
    	if(prev[i]!=-1)//删除i位置元素
    		next[prev[i]]=next[i];
    	if(next[i]!=-1)
    		prev[next[i]]=prev[i];
    	//将数组f位置元素补到i位置上
    	key[i]=key[f];//先将f位置上元素复制到i位置
    	prev[i]=prev[f];
        prev[i]=next[f];
    	if(prev[f]!=-1)//再修改prev元素的next值和next元素的prev值
    		next[prev[f]]=i;
    	if(next[f]!=-1)
    		prev[next[f]]=i;
    	--f;		
    }
    void Print(int *key, int *next, int *prev, int m)
    {
    	cout<<setw(8)<<"next:";
    	for(int t=0;t<m;t++)
    		cout<<setw(3)<<setiosflags(ios::right)<<next[t]<<" ";
    	cout<<endl;
    	cout<<setw(8)<<"key:";
    	for(int j=0;j<m;j++)
    		cout<<setw(3)<<setiosflags(ios::right)<<key[j]<<" ";
    	cout<<endl;
    	cout<<setw(8)<<"prev:";
    	for(int k=0;k<m;k++)
    		cout<<setw(3)<<setiosflags(ios::right)<<prev[k]<<" ";
    	cout<<endl;
    	
    }
    
    
    
    int main()
    {
    	int* key=new int[n];
    	int* prev=new int[n];
    	int* next=new int[n];
    	for(int i=0;i<10;i++)
    		Insert(key, next, prev, 2*i+11);
    	Print(key, next, prev, f+1);
    	Delete(key, next, prev, 17);
    	Print(key, next, prev, f+1);
    	delete[] key;
    	delete[] prev;
    	delete[] next;
    	return 0;
    }


    展开全文
  • [内存管理]内存池pool库

    千次阅读 2012-03-21 17:04:19
    如果之前学过操作系统的内存管理机制和内存分配算法等知识,那么就了解“内存池”的概念。 简单地说,内存池预先分配了一块大的内存空间,然后就可以在其中使用某种算法实现高效快速的自定制内存分配。 boost.pool...
  • 垃圾回收算法

    2020-06-24 15:30:18
    标记清除 先判断可以回收的对象,并标记 ... 一边释放空间,一边将未回收的对象内存空间,向前移动,让内存更加紧凑 优点:没有内存碎片 缺点:效率低,需要移动的时间。并且在整理过后,如果一些局部变量引用了改.
  • 3、在设计好的数据结构上设计一个主存分配算法(循环首次适应算法)。 4、在设计好的数据结构上设计一个主存回收算法。其中,若回收的分区有上邻空闲分区和(或)下邻空闲分区,要求合并为一个空闲分区登记在空闲...
  • 数据结构和算法

    2020-09-14 13:55:48
    文章目录数据结构数据结构分类数据结构操作算法 数据结构 ...但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N
  • 但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,扩容时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有...
  • 但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有数据以...
  • 但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有数据以...
  • 实现链式数据结构有两种方式,指针和数组,与指针相比较,采用数组方式,对内存的使用更加紧凑,但对链表的最大长度有所限制。 实现的思路是分别利用对象的prev,next字段表示前驱和后继对象的数组下标,另外将链表...
  • 这里的话因为接下来讲线性表之类...能动态分配内存;能方便地使用字符串;有效而方便地使用数组…… 掌握指针的应用,可以使程序简洁、紧凑、高效。很多人说指针很难 确实,但是指针难的不是其定义,而是其用法...
  • 文章目录算法框架LRU统计学习方法最小二乘法拟合曲线感知器KNearestNeighbors KNN朴素贝叶斯决策树逻辑回归提升方法BoostAdaboostEM...但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分
  • 文章目录 1.什么是叫做地址映射? 2.分别解释静态、动态分区和等长、异长分区,以及之间的联系。 3.说明并解释四种内存分配算法的特点。 4. 什么是碎片和紧凑? 资料参考
  • Boost库基础-pool库

    2020-03-24 20:39:21
    内存池预先分配了一块大的内存空间,然后就可以在其中使用某种算法实现高效快速的自定制内存分配。 boost.pool库基于简单分隔存储思想实现了一个快速、紧凑的内存池库,不仅能够管理大量的对象,还可以被使用做STL...
  • C/C++面试题总结

    2015-05-06 15:29:00
    程序内存分配4. unix多线程5. 哈希查找6. oop特点7. 素数(优化)8. 字符串掩膜操作(内存紧凑)9. 多边形相交10.孤儿进程与僵尸进程11.链表节点删除12.常用加密算法13.单例(设计模式)14.UML15.网络7层模型/各层...
  • 但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面
  • jdk-14_linux-x64_bin.rpm

    2020-03-30 09:57:57
    通过实现 NUMA-aware 内存分配,提升 G1 在大型机器上的性能。 349:JFR Event Streaming JFR 事件流 暴露 JDK Flight Recorder 数据以进行连续监视。 352:Non-Volatile Mapped Byte Buffers 非易失性...
  • 第11章 指针、链表和动态内存分配 第12章 多维数组 第13章 选择结构 第14章 循环结构 第15章 函数 第16章 文件 第17章 自加、自减、逗号和位操作符和条件表达式构成的选择结构 第18章 其他普量类型、变量的作用域、...
  • 在这一版本中,SQL 执行引擎引入新的内部数据表示方式 --- `Chunk`,一个结构中保存一批数据而不仅是一行数据,同一列的数据在内存中连续存放,使得内存使用更紧凑,这样带来了几点好处:1. 显著减小了内存消耗; 2....
  • ZLib :非常紧凑的数据流压缩库。 zlib-ng:用于“下一代”系统的zlib,将一些重要的优化进行嵌入式替换。 zstd:Zstandard-快速实时压缩算法。由Facebook开发。 ZZIPlib:提供ZIP归档的读权限。 并发性 并发...
  • read_config将为该val分配内存(malloc), 但是对于'b' 类型, ptr所指向的必须是已经 分配好的内存 两个重要的函数分别为: read_config, 参数为文件名, 一个struct NamVal *, 以及该struct NamVal的项数 free_config,...

空空如也

空空如也

1 2
收藏数 27
精华内容 10
关键字:

内存分配算法紧凑