天津理工大学操作系统存储器的分配与回收算法实现实验报告

实验报告学院（系）名称：计算机与通信工程学院【实验过程记录（源程序、测试用例、测试结果及心得体会等）】源程序:MemoryBlock.java://内存块类，包含各种操作public class MemoryBlock {static final int BLOCK_SIZE = 4096;private int baseBlock; //内存块基地址private int blockNum; //大小private boolean inUse; //是否已分配private MemoryBlock prev, next;public MemoryBlock(int blockNum) {this.baseBlock = 0;this.blockNum = blockNum;inUse = false;prev = null;next = null;}public MemoryBlock(int base, int blockNum) {this.baseBlock = base;this.blockNum = blockNum;inUse = false;prev = null;next = null;}public int getBlockNum() {return blockNum;}public void setBlockNum(int blockNum) {this.blockNum = blockNum;}public MemoryBlock getPrev() {return prev;}public void setPrev(MemoryBlock prev) {this.prev = prev;public MemoryBlock getNext() {return next;}public void setNext(MemoryBlock next) {this.next = next;}public boolean inUse() {return inUse;}public void setUse() {inUse = true;}public void free() {inUse = false;}public int getBaseBlock() {return baseBlock;}public void setBaseBlock(int baseBlock) { this.baseBlock = baseBlock;}//分配内存块，如果可分配，则返回剩余内存块public MemoryBlock allocate(int blockNum) { if(this.blockNum - blockNum>0) {int newBase = baseBlock + blockNum;int newBlock = this.blockNum-blockNum;this.blockNum = blockNum;setUse();return new MemoryBlock(newBase, newBlock);}else if(this.blockNum - blockNum ==0) {this.blockNum = 0;}return null;}//判断内存块是否能合并public boolean merge(MemoryBlock memBlock) {if(baseBlock+blockNum==memBlock.getBaseBlock()) {setBlockNum(blockNum+memBlock.blockNum);memBlock.setBaseBlock(0);memBlock.setBlockNum(0);return true;}elsereturn false;}@Overridepublic String toString() {String inUse = null;if(inUse())inUse = "已分配";else inUse = "未分配";return"内存块 [基地址=" + baseBlock + ", 大小=" + blockNum +", " + inUse + "]";}}MemoryTable.java://虚类MemTable，提供内存链表的各种基本方法public abstract class MemoryTable {//MemoryBlock链表表头protected MemoryBlock memList;public MemoryTable(int blockNum) {memList = new MemoryBlock(0, blockNum);}//把newBlock插入到memBlock前面public void insertBefore(MemoryBlock memBlock, MemoryBlock newBlock){if(memBlock.getPrev() != null)memBlock.getPrev().setNext(newBlock);if(memList == memBlock)memList = newBlock;newBlock.setPrev(memBlock.getPrev());newBlock.setNext(memBlock);memBlock.setPrev(newBlock);}//在memBlock后插入newBlockpublic void insert(MemoryBlock memBlock, MemoryBlock newBlock) { if(memBlock.getNext() != null)memBlock.getNext().setPrev(newBlock);newBlock.setNext(memBlock.getNext());memBlock.setNext(newBlock);newBlock.setPrev(memBlock);}//删除块的连接关系，但不释放块public void remove(MemoryBlock memBlock) {if(memBlock == memList)memList = memBlock.getNext();if(memBlock.getNext()!=null)memBlock.getNext().setPrev(memBlock.getPrev());if(memBlock.getPrev()!=null)memBlock.getPrev().setNext(memBlock.getNext());}public void print() {MemoryBlock memBlock = memList;int i=0;while(memBlock != null) {System.out.print(i+" ");System.out.println(memBlock);i++;memBlock = memBlock.getNext();}}//合并邻接的空闲内存public void merge(MemoryBlock newBlock) {MemoryBlock memBlock = memList;while(memBlock != null) {if(!memBlock.inUse()) {if(memBlock.merge(newBlock)) {memBlock.setBlockNum( memBlock.getBlockNum() +newBlock.getBlockNum());remove(newBlock);break;}if(newBlock.merge(memBlock)) {newBlock.setBlockNum( newBlock.getBlockNum() + memBlock.getBlockNum());break;}}memBlock = memBlock.getNext();}}//分配内存（抽象函数）public abstract boolean allocate(int blockNum);//释放内存（抽象函数）public abstract boolean free(int baseBlock);}FirstFit.java:public class FirstFit extends MemoryTable{public FirstFit(int blockNum) {super(blockNum);}@Overridepublic boolean allocate(int blockNum) {MemoryBlock memBlock = memList;while(memBlock!=null) {if(!memBlock.inUse()) {if(memBlock.getBlockNum()>blockNum) {MemoryBlock newBlock = memBlock.allocate(blockNum);insert(memBlock, newBlock);return true;}else if(memBlock.getBlockNum()==blockNum) {memBlock.setUse();}}memBlock = memBlock.getNext();}return false;}//分配内存（类内使用）void freeMemory(MemoryBlock freeBlock) {MemoryBlock prev = freeBlock.getPrev();MemoryBlock next = freeBlock.getNext();freeBlock.free();while(!prev.inUse() && (prev.merge(freeBlock))) {prev.setBlockNum( prev.getBlockNum() +freeBlock.getBlockNum());remove(freeBlock);freeBlock = prev;if(freeBlock.getPrev()!=null)prev = freeBlock.getPrev();else return;}}if(freeBlock.getNext()!=null) {while(!next.inUse() && (freeBlock.merge(next))) {freeBlock.setBlockNum ( next.getBlockNum() +freeBlock.getBlockNum());remove(next);freeBlock = next;if(freeBlock.getNext()!=null)next = freeBlock.getNext();else return;}}}@Overridepublic boolean free(int baseBlock) {MemoryBlock memBlock = memList;while(memBlock != null) {if(memBlock.getBaseBlock() == baseBlock) {freeMemory(memBlock);return true;}memBlock = memBlock.getNext();}return false;}}BestFit.java:public class BestFit extends MemoryTable {private MemoryBlock usedMemory;public BestFit(int blockNum) {super(blockNum);usedMemory = null;}@Overridepublic boolean allocate(int blockNum) {MemoryBlock memBlock = memList;MemoryBlock minBlock = null;for(;memBlock!=null; memBlock = memBlock.getNext()) { if(!memBlock.inUse()&&(memBlock.getBlockNum()>=blockNum)) { minBlock = memBlock;break;}}if(minBlock != null) {remove(minBlock);if(minBlock.getBlockNum()!=blockNum) {MemoryBlock newBlock = minBlock.allocate(blockNum);insertUnused(newBlock);}insertUsed(minBlock);return true;}elsereturn false;}boolean freeMemory(MemoryBlock freeBlock) {if(freeBlock != null) {freeBlock.free();removeUsed(freeBlock);insertUnused(freeBlock);return true;}return false;}@Overridepublic boolean free(int baseBlock) {MemoryBlock memBlock = usedMemory;while(memBlock != null) {if(memBlock.getBaseBlock() == baseBlock) {freeMemory(memBlock);merge(memBlock);return true;}memBlock = memBlock.getNext();return false;}//在已分配链表删除public void removeUsed(MemoryBlock memBlock) {if(memBlock == usedMemory)usedMemory = memBlock.getNext();if(memBlock.getNext()!=null)memBlock.getNext().setPrev(memBlock.getPrev());if(memBlock.getPrev()!=null)memBlock.getPrev().setNext(memBlock.getNext());}//插入未分配链表void insertUnused(MemoryBlock newBlock) {if(memList == null)memList = newBlock;else {MemoryBlock memBlock = memList;MemoryBlock preBlock = null;while(memBlock!=null) {if(newBlock.getBlockNum()<=memBlock.getBlockNum()) { insertBefore(memBlock, newBlock);return;}preBlock = memBlock;memBlock = memBlock.getNext();}insert(preBlock, newBlock);}}//插入已分配链表void insertUsed(MemoryBlock newBlock) {if(usedMemory == null)usedMemory = newBlock;else {MemoryBlock memBlock = usedMemory;while(memBlock.getNext() != null)memBlock = memBlock.getNext();memBlock.setNext(newBlock);newBlock.setPrev(memBlock);}}public void print() {super.print();MemoryBlock memBlock = usedMemory;int i=0;while(memBlock != null) {System.out.print(i+" ");System.out.println(memBlock);i++;memBlock = memBlock.getNext();}}}WorstFit.java:public class WorstFit extends MemoryTable {//已分配链表private MemoryBlock usedMemory;public WorstFit(int blockNum) {super(blockNum);usedMemory = null;}@Overridepublic boolean allocate(int blockNum) {MemoryBlock maxBlock = memList;if(maxBlock.getBlockNum()<blockNum)return false;remove(maxBlock);if(maxBlock.getBlockNum()!=blockNum) {MemoryBlock newBlock = maxBlock.allocate(blockNum);insertUnused(newBlock);}insertUsed(maxBlock);return true;}boolean freeMemory(MemoryBlock freeBlock) {if(freeBlock != null) {freeBlock.free();removeUsed(freeBlock);insertUnused(freeBlock);}return false;}@Overridepublic boolean free(int baseBlock) {//已分配链表MemoryBlock memBlock = usedMemory;while(memBlock != null) {if(memBlock.getBaseBlock() == baseBlock) {freeMemory(memBlock);merge(memBlock);return true;}memBlock = memBlock.getNext();}return false;}public void removeUsed(MemoryBlock memBlock) {if(memBlock == usedMemory)usedMemory = memBlock.getNext();if(memBlock.getNext()!=null)memBlock.getNext().setPrev(memBlock.getPrev());if(memBlock.getPrev()!=null)memBlock.getPrev().setNext(memBlock.getNext());}void insertUnused(MemoryBlock newBlock) {if(memList == null)memList = newBlock;else {MemoryBlock memBlock = memList;MemoryBlock preBlock = null;while(memBlock!=null) {if(newBlock.getBlockNum()>=memBlock.getBlockNum()) { insertBefore(memBlock, newBlock);return;}preBlock = memBlock;memBlock = memBlock.getNext();}insert(preBlock, newBlock);}}void insertUsed(MemoryBlock newBlock) {if(usedMemory == null)usedMemory = newBlock;else {MemoryBlock memBlock = usedMemory;while(memBlock.getNext() != null)memBlock = memBlock.getNext();memBlock.setNext(newBlock);newBlock.setPrev(memBlock);}}public void print() {super.print();MemoryBlock memBlock = usedMemory;int i=0;while(memBlock != null) {System.out.print(i+" ");System.out.println(memBlock);i++;memBlock = memBlock.getNext();}}}测试用例:Main.java:public class Main {public static void main(String[] args) {testFirstFit();System.out.println();testBestFit();System.out.println();testWorstFit();}public static void testFirstFit() {MemoryTable mem = new FirstFit(1024);System.out.println("测试首次适应法:");mem.allocate(512);mem.allocate(256);mem.allocate(128);mem.print();mem.free(512);mem.free(768);mem.print();}public static void testBestFit() {MemoryTable mem = new BestFit(1024);System.out.println("测试最佳适应法:");mem.allocate(1);mem.allocate(2);mem.allocate(3);mem.print();mem.free(0);mem.free(1);mem.print();}public static void testWorstFit() {MemoryTable mem = new WorstFit(1024);System.out.println("测试最坏适应法:");mem.allocate(1);mem.allocate(2);mem.allocate(3);mem.print();mem.free(0);mem.free(3);mem.print();}}测试结果:测试首次适应法:分配 512 内存分配 256 内存分配 128 内存内存单元:0 内存块 [基地址=0, 大小=512, 已分配]1 内存块 [基地址=512, 大小=256, 已分配]2 内存块 [基地址=768, 大小=128, 已分配]3 内存块 [基地址=896, 大小=128, 未分配]释放 512 处内存释放 768 处内存内存单元:0 内存块 [基地址=0, 大小=512, 已分配]1 内存块 [基地址=512, 大小=512, 未分配]测试最佳适应法:分配 1 内存分配 2 内存分配 3 内存内存单元:0 内存块 [基地址=6, 大小=1018, 未分配]0 内存块 [基地址=0, 大小=1, 已分配]1 内存块 [基地址=1, 大小=2, 已分配]2 内存块 [基地址=3, 大小=3, 已分配]释放 0 处内存释放 1 处内存内存单元:0 内存块 [基地址=0, 大小=3, 未分配]1 内存块 [基地址=6, 大小=1018, 未分配]0 内存块 [基地址=3, 大小=3, 已分配]测试最坏适应法:分配 1 内存分配 2 内存分配 3 内存内存单元:0 内存块 [基地址=6, 大小=1018, 未分配]0 内存块 [基地址=0, 大小=1, 已分配]1 内存块 [基地址=1, 大小=2, 已分配]2 内存块 [基地址=3, 大小=3, 已分配]释放 0 处内存释放 3 处内存内存单元:0 内存块 [基地址=3, 大小=1021, 未分配]1 内存块 [基地址=0, 大小=1, 未分配]0 内存块 [基地址=1, 大小=2, 已分配]心得体会:1.使用类来进行一些方法的重用2.释放内存时，根据不同的分配方法进行相邻的内存合并3.链表应根据具体情况优化从而简化代码。

实验二主存储器空间的分配和回收一、实验题目：模拟在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。

二、实验目的：主存的分配和回收的实现与主存储器的管理方式有关，通过本实习理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。

三、实验内容：一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。

当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。

当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。

四、程序中使用的数据结构及符号说明：五、程序流程图：六、程序源代码：#include <stdlib.h>#include <stdio.h>typedef int datatype;typedef struct node{datatype pageNum,blockNum;struct node *next;}linknode;typedef linknode *linklist;linklist creatlinklist(int n)/*尾插法创建带头结点的单链表*/{linklist head,r,s;int x,y,i=0;head=r=(linklist)malloc(sizeof(linknode));printf("\n请分别输入页表的页号及块号（-1表示空）：\n");printf("\n页号| 块号\n");while (i<n){scanf("%d %d",&x,&y);s=(linklist)malloc(sizeof(linknode));s->pageNum=x;s->blockNum=y;r->next=s;r=s;i++;}r->next=NULL;return head;}void init(int g[100][100],int N)/*初始化位示图，将值全置为零，0表示空闲状态*/{int i,j;for(i=0;i<100;i++){for(j=0;j<100;j++){g[i][j]=0; //全置为零}}g[N+1][0]=N*N; //在数组最后一个数的后面设置一个空间用来存放剩余空闲块数}linklist Init(linklist head,int g[100][100],int n,int N){linklist p;int i,j;p=head->next;if(n<=g[N+1][0]) //首先判断作业的页数是否小于等于位示图剩余空闲块的个数{while(p){i=p->blockNum/N;j=p->blockNum%N;g[i][j]=1;g[N+1][0]--;p=p->next;}}return head;}printStr(int g[100][100],int N)/*打印位示图*/{int i,j;printf("\n此时位示图为：\n");printf("\n ");for(i=0;i<N;i++){printf(" ");printf("%d",i);}printf("\n");for(i=0;i<N;i++){printf("%d",i);for(j=0;j<N;j++){printf(" ");printf("%d",g[i][j]);}printf("\n");}printf("\n");}void print(linklist head)/*输出带头结点的单链表*/{linklist p;p=head->next;printf("\n该页表为:\n");printf("\n");printf("\n 页号| 块号\n");while(p){printf("%11d%7d\n",p->pageNum,p->blockNum);p=p->next;}printf("\n");}linklist Dis(linklist head,int g[100][100],int n,int N){linklist p;int i,j;p=head->next;if(n<=g[N+1][0]) //首先判断作业的页数是否小于等于位示图剩余空闲块的个数{while(p){for(i=0;i<N;i++){for(j=0;j<N;j++){if(g[i][j]==0){p->blockNum=N*i+j; //将对应块号记录到页表g[i][j]=1; //将块置1，表示已被占用g[N+1][0]--; //剩余空闲块减1break; //跳出循环，进行下一个页的分配}}break; //跳出循环}p=p->next; //下一个页进行分配}return head;}}linklist Recy(linklist head,int g[100][100],int n,int N)/*回收已经完成的页*/ {int i,j;linklist p;p=head->next;while(p&&p->pageNum!=n) //找出要回收的页号{p=p->next;}if(p) //找到{i=p->blockNum/N;j=p->blockNum%N;g[i][j]=0; //将该块置0，表空闲状态g[N+1][0]++;p->blockNum=-1; //页表中对应的块号为空，置成-1}return head;}void main(){int m,n,N;int x,y,a,b,t;int graph[100][100];linklist head,Head;printf("\n*****分页式存储管理分配及回收算法*****\n");printf("\n请输入位示图字长：");scanf("%d",&N);printf("\n请输入已占用内存作业的页数：");scanf("%d",&m);head=creatlinklist(m);init(graph,N);head=Init(head,graph,m,N);printStr(graph,N);printf("\n当前空闲块数为：%d",graph[N+1][0]);printf("\n\n现在进行作业分配：\n");printf("\n请输入需要分配的作业的页数：");scanf("%d",&n);Head=creatlinklist(n);Head=Dis(Head,graph,n,N);print(Head);printStr(graph,N);printf("\n当前空闲块数为：%d",graph[N+1][0]);printf("\n\n您是否想回收已完成的页，“是”请按1，“否”请按0：");scanf("%d",&x);if(x) //判断是否要回收{printf("\n请输入您要回收的页号：");scanf("%d %d %d %d",&y,&a,&b,&t);head=Recy(head,graph,y,N);head=Recy(head,graph,a,N);head=Recy(head,graph,b,N);head=Recy(head,graph,t,N);printStr(graph,N);}printf("\n当前空闲块数为：%d",graph[N+1][0]);printf("\n");}七、运行结果：实习小结：本次实验是自己花了很多的时间去琢磨去尝试才完成的，虽然还不是很完美，但是在设计的过程中自己在对编程方面的逻辑思维得到了很好的锻炼。

实验二存储器的分配与回收算法实现一、实验目的1.学习存储器的分配与回收算法；2.实现动态存储管理的相关算法。

二、实验原理在计算机系统中，存储器是一项重要的资源。

为了有效地利用存储器资源，需要设计合理的存储器管理算法来进行存储器的分配与回收。

常用的存储器管理算法有以下几种：1. 首次适应算法（First Fit）：分配内存时从链表的头部开始查找第一个满足要求的空闲内存单元。

2. 最佳适应算法（Best Fit）：分配内存时从整个链表中找到最小的满足要求的空闲内存单元。

3. 最坏适应算法（Worst Fit）：分配内存时从整个链表中找到最大的满足要求的空闲内存单元。

4. 循环首次适应算法（Next Fit）：分配内存时从上一次分配结束的位置开始查找第一个满足要求的空闲内存单元。

5. 最近最少使用策略（Least Recently Used, LRU）：当内存不足时，将最近最久未使用的页面置换出去。

6.先进先出策略（FIFO）：将最先进入缓冲区的页面置换出去。

三、实验步骤1.首先，我们需要定义一个数据结构来表示存储器块，该数据结构包含以下字段：-起始地址：表示该存储器块的起始地址；-大小：表示该存储器块的大小；-状态：表示该存储器块的使用状态（空闲/已分配）；-下一存储器块地址：指向链表中下一个存储器块的地址。

2.然后，创建一个链表来表示存储器块的集合，链表的每个节点表示一个存储器块。

3. 实现首次适应算法（First Fit）：-遍历链表，找到第一个大小大于等于所需内存的空闲存储器块；-将该存储器块标记为已分配，并更新链表中该存储器块的状态；-如果找不到满足要求的存储器块，则表示存储器不足，分配失败。

4. 实现最佳适应算法（Best Fit）：-遍历链表，找到大小最小的满足要求的空闲存储器块；-将该存储器块标记为已分配，并更新链表中该存储器块的状态；-如果找不到满足要求的存储器块，则表示存储器不足，分配失败。

实验四操作系统存储管理实验报告一、实验目的本次实验的主要目的是深入理解操作系统中存储管理的基本原理和方法，通过实际操作和观察，掌握内存分配与回收、页面置换算法等关键概念，并能够分析和解决存储管理中可能出现的问题。

二、实验环境本次实验在装有 Windows 操作系统的计算机上进行，使用了 Visual Studio 等编程工具和相关的调试环境。

三、实验内容（一）内存分配与回收算法实现1、首次适应算法首次适应算法从内存的起始位置开始查找，找到第一个能够满足需求的空闲分区进行分配。

在实现过程中，我们通过建立一个空闲分区链表来管理内存空间，每次分配时从表头开始查找。

2、最佳适应算法最佳适应算法会选择能够满足需求且大小最小的空闲分区进行分配。

为了实现该算法，在空闲分区链表中，分区按照大小从小到大的顺序排列，这样在查找时能够快速找到最合适的分区。

3、最坏适应算法最坏适应算法则选择最大的空闲分区进行分配。

同样通过对空闲分区链表的排序和查找来实现。

（二）页面置换算法模拟1、先进先出（FIFO）页面置换算法FIFO 算法按照页面进入内存的先后顺序进行置换，即先进入内存的页面先被置换出去。

在模拟过程中，使用一个队列来记录页面的进入顺序。

2、最近最久未使用（LRU）页面置换算法LRU 算法根据页面最近被使用的时间来决定置换顺序，最近最久未使用的页面将被置换。

通过为每个页面设置一个时间戳来记录其最近使用的时间，从而实现置换策略。

3、时钟（Clock）页面置换算法Clock 算法使用一个环形链表来模拟内存中的页面，通过指针的移动和页面的访问标志来决定置换页面。

四、实验步骤（一）内存分配与回收算法的实现步骤1、初始化内存空间，创建空闲分区链表，并为每个分区设置起始地址、大小和状态等信息。

2、对于首次适应算法，从链表表头开始遍历，找到第一个大小满足需求的空闲分区，进行分配，并修改分区的状态和大小。

3、对于最佳适应算法，在遍历链表时，选择大小最接近需求的空闲分区进行分配，并对链表进行相应的调整。

西安邮电大学（计算机学院）课内实验报告实验名称：内存分配与回收专业名称：计算机科学与技术班级：计科1503学生姓名：***学号（8位）：********指导教师：***实验日期：2016年5月23日---2016年6月6日一. 实验目的及实验环境1.实验目的掌握内存分配FF，BF，WF策略及实现的思路；掌握内存回收过程及实现思路；实现内存的申请、释放的管理程序，调试运行，总结程序设计中出现的问题并找出原因，写出实验报告。

2.实验环境（1）硬件CPU：I7-6500内存：8G显示器：笔记本显示器硬盘空间：1TB（2）软件虚拟机名称及版本：Vmware操作系统名称及版本：Ubuntu Kylin 16.04编译器：gcc二. 实验内容1、实验前准备工作阅读参考资料，掌握操作系统内存管理的过程，并熟悉FF，BF，WF内存分配策略以及内存回收策略。

2、实验内容根据下发ppt内容，内存分配与回收程序要求完成如下功能，具体详细设计要求见ppt。

1 -Set memory size (default=1024)//设置内存大小2 - Select memory allocation algorithm//选择内存分配算法FF、BF、WF3 - New process//创建新进程，分配内存4 - Terminate a process//终止进程，回收内存5 - Display memory usage//显示内存当前使用情况0 – Exit//程序退出三．方案设计1．功能模块图及解释2．核心数据结构及解释struct free_block_type //空闲块{int size;int start_addr;struct free_block_type *next;};struct allocated_block //已分配的内存块{int pid;int size;int start_addr;char process_name[PROCESS_NAME_LEN];struct allocated_block *next;}；1.Set memory size (default=1024):这个模块是用来设置内存大小的，从键盘获取一个数字，并将它赋值给内存大小；若没有设置，则默认内存的大小为1024。

《操作系统》存储管理实验报告操作系统是计算机系统中最基础、最核心的软件之一，负责管理计算机硬件资源和提供资源的分配与调度。

而存储管理是操作系统中的重要组成部分，它负责管理计算机的内存，包括内存的分配、回收、保护等操作。

本文将针对存储管理进行实验，并撰写实验报告。

本次实验主要涉及以下内容：内存的分配与回收、内存的保护。

实验过程中，我首先根据操作系统的要求，设计了相应的算法用于内存的分配与回收。

并通过编写程序，验证了算法的正确性。

随后，我进一步研究了内存的保护机制，通过设置访问权限位和访问控制表，实现了对内存的合理保护。

在内存的分配与回收方面，我设计了一种简单的算法，首次适应算法。

具体实现如下：首先，将内存分为若干个块，每个块的大小为固定值。

当需要分配内存时，首先遍历内存块列表，找到第一个大小合适的块，将其分配给进程。

当进程终止时，将其占用的内存块回收，以便后续进程使用。

通过编写程序进行测试，结果表明该算法能够正确地进行内存的分配与回收。

在内存的保护方面，我采用了访问权限位和访问控制表的方式进行。

具体实现如下：首先，为每个进程分配一组访问权限位，记录了该进程能够访问的内存区域。

同时，设置一个访问控制表，记录了每个内存块的权限。

当进程访问一些内存块时，首先检查该进程的访问权限位，再与访问控制表中的权限进行比较，以确定该进程是否有权限访问该内存块。

通过编写程序进行测试，证明了该机制能够有效地保护内存。

总结来说，本次实验主要涉及了操作系统中的存储管理部分，包括内存的分配与回收、内存的保护。

通过设计算法和编写程序，我成功地实现了这些功能，并验证了其正确性。

通过本次实验，我进一步加深了对操作系统存储管理的理解，提高了编程和设计的能力。

计算机操作系统实验报告实验二实验题目：存储器管理系别：计算机科学与技术系班级：姓名：学号：2一、实验目的深入理解动态分区存储管理方式下的内存空间的分配与回收。

二、实验内容编写程序完成动态分区存储管理方式下的内存分配和回收的实现。

具体内容包括：确定用来管理内存当前使用情况的数据结构；采用首次适应算法完成内存空间的分配；分情况对作业进行回收；编写主函数对所做工作进行测试。

三、实验原理分配：动态分区存储管理方式把内存除OS占用区域外的空间看作一个大的空闲区。

当作业要求装入内存时，根据作业需要内存空间的大小查询内存中各个空闲区，当从内存中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业要求划出一个分区装入该作业。

回收：作业执行完后，它所占用的内存空间被收回，成为一个空闲区。

如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。

四、实验方法实现动态分区的分配与回收，主要考虑三个问题：第一、设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域(利用结构体类型数组来保存数据)；第二、在设计的数据表格基础上设计内存分配算法（采用首次适应算法找合适的分区（对空闲分区表进行排序），分配时要考虑碎片问题）；第三、在设计的数据表格基础上设计内存回收算法（分四种情况进行回收（上邻、下邻、上下邻和无相邻分区）。

五、实验步骤第一，设计记录内存使用情况的数据表格●已分配分区表：起始地址、长度、标志（0表示“空表项”，1表示“已分配”）●空闲分区表：起始地址、长度、标志（0表示“空表项”，1表示“未分配”）struct used_table {float address; //已分分区起始地址float length; //已分分区长度，单位为字节int flag; //已分配表区登记栏标志，用0表示空栏目，char zuoyename;}; //已分配区表Struct free_table[ {float address; //空闲分区起始地址float length; //空闲分区长度，单位为字节int flag; //空闲分区表登记栏目用0表示空栏目，1表示未配}; //空闲分区表第二，在设计的表格上进行内存分配●首次适应算法：为作业分配内存，要求每次找到一个起始地址最小的适合作业的分区（按起始地址递增排序）。

操作系统实验四报告-主存空间分配和回收(含源码)计算机学院计算机科学与技术专业班学号姓名教师评定_________________实验题目主存空间的分配和回收一、实验目的熟悉主存的分配与回收。

理解在不同的存储管理方式下，如何实现主存空间的分配与回收。

掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。

二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。

所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。

所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。

可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。

当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。

随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。

实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。

同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。

同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。

三、实验主要仪器设备和材料实验环境硬件环境：IBM-PC或兼容机软件环境：VC++ 6.0四、实验原理及设计分析某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。

（作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB）当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时间的运行后，作业2运行完毕，释放所占内存。

操作系统实验报告存储器的分配与回收算法实现姓名：学号：班级：.一、实验名称及要求1、实验名称：存储器的分配与回收算法实现2、实验要求：学生应正确地设计有关的数据结构与各个功能模块，画出程序的流程图，编写程序，程序执行结果应正确。

3、实验方式：学生通过实验室的微机上机，实际调试程序。

4、实验环境：Windows操作系统环境下的个人微机Ｃ或Ｃ＋＋程序设计语言二、实验内容1本实验是模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。

2采用最先适应法、最佳适应法、最坏适应法分配主存空间。

3当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。

若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。

4当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。

5运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。

三、实验程序#include <iostream.h>#include <malloc.h>#include <stdlib.h>typedef struct FreeLink{//定义自由链struct FreeLink *prior;char name;int start;int size;.bool flag;struct FreeLink *next;}* ptr,*head;head top;ptr p;void print(){//将内存分配情况打印到屏幕上p=top;cout<<"************************内存分配情况表************************"<<endl;cout<<"区号\t\t"<<"起始位置\t"<<"区间长度\t"<<"区间状态\t"<<endl;do{cout<<p->name<<"\t\t"<<p->start<<"\t\t"<<p->size<<"\t\t";if(p->flag==false){cout<<"空闲"<<endl;}else{cout<<"已占用"<<endl;}p=p->next;}while(p!=NULL);}void clear(){//结束操作时清空“内存”以备其他操作do{p=top;top=top->next;free(p);}while(top!=NULL);}void asc(ptr &p){//最佳适应法的内存分配函数int min;ptr op;FreeLink *fl=(FreeLink *)malloc(sizeof(FreeLink));cout<<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<"请输入要分配内存的大小"<<endl;cin>>fl->size;min=256;fl->flag=true;do{if(p->flag==false&&p->size<=min&&p->size>=fl->size){ min=p->size;op=p;}p=p->next;}while(p!=NULL);if(op->size>fl->size){fl->start=op->start;op->start=fl->start+fl->size;op->size=op->size-fl->size;fl->next=op;fl->prior=op->prior;op->prior->next=fl;op->prior=fl;goto flag1;}if(op->size==fl->size){op->flag=fl->flag;op->name=fl->name;free(fl);goto flag1;}cout<<"内存过小，分配失败！"<<endl;goto flag2;flag1: cout<<"分配成功！"<<endl;flag2: ;}void dec(ptr &p){//最坏适应法的内存分配函数int max;ptr op;FreeLink *fl=(FreeLink *)malloc(sizeof(FreeLink));cout<<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<"请输入要分配内存的大小"<<endl;cin>>fl->size;max=fl->size;fl->flag=true;do{if(p->flag==false&&p->size>=max){max=p->size;op=p;}p=p->next;}while(p!=NULL);if(op->size>fl->size){fl->start=op->start;op->start=fl->start+fl->size;op->size=op->size-fl->size;fl->next=op;fl->prior=op->prior;op->prior->next=fl;op->prior=fl;goto flag3;}if(op->size==fl->size){op->flag=fl->flag;op->name=fl->name;free(fl);goto flag3;}cout<<"内存过小，分配失败！"<<endl;goto flag4;flag3: cout<<"分配成功！"<<endl;flag4: ;}void splice(ptr &p){//若被操作的内存有相邻空闲区则将空闲区拼接合并int x;if(p->prior->flag==false&&p->next->flag==false)x=1;if((p->prior->flag==false&&p->next->flag==true)||(p->prior->flag==false&& p->next==NULL))x=2;if((p->prior->flag==true&&p->next->flag==false)||(p->prior==NULL&&p->next ->flag==false))x=3;if((p->prior->flag==true&&p->next->flag==true)||(p->prior==NULL&&p->next->flag==true)||(p->prior->flag==true&&p->next==NULL))x=4;switch(x){case 1:p->next->prior=p->prior;p->prior->next=p->next;p->prior->size=p->prior->size+p->size+p->next->size;p->prior->next=p->next->next;if(p->next->next!=NULL)p->next->next->prior=p->next->prior;free(p->next);free(p);break;case 2:if(p->next==NULL){p->prior->next=p->next;}else{p->next->prior=p->prior;p->prior->next=p->next;}p->prior->size=p->prior->size+p->size;free(p);break;case 3:if(p->prior==NULL){top=p->next;p->next->prior=NULL;p->next->start=p->start;p->next->size=p->next->size+p->size;}else{p->next->prior=p->prior;p->prior->next=p->next;p->next->start=p->start;p->next->size=p->next->size+p->size;}free(p);break;case 4:p->name='@';p->flag=false;break;}}void allocate(ptr &p){//最先适应法的内存分配函数FreeLink *fl=(FreeLink *)malloc(sizeof(FreeLink));cout<<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<"请输入要分配内存的大小"<<endl;cin>>fl->size;fl->flag=true;do{if(p->flag==false&&p->size>fl->size){fl->start=p->start;p->start=fl->start+fl->size;p->size=p->size-fl->size;fl->next=p;fl->prior=p->prior;p->prior->next=fl;p->prior=fl;goto a;}if(p->flag==false&&p->size==fl->size){p->flag=fl->flag;p->name=fl->name;free(fl);goto a;}p=p->next;}while(p!=NULL);cout<<"内存过小，分配失败！"<<endl;goto b;a: cout<<"分配成功！"<<endl;b: ;}void recover(ptr &p){//内存回收函数char n = ' ';cout<<"请输入要回收的内存对应的进程名";cin>>n;do{if(p->flag==true&&p->name==n){splice(p);goto c;}p=p->next;}while(p!=NULL);cout<<"内存并未分配给对应进程，回收失败！"<<endl;goto d; c: cout<<"内存回收成功！"<<endl;d: ;}int ffa(){//最先适应法char choice=' ';print();ptr pcb=(FreeLink *)malloc(sizeof(FreeLink));pcb->next=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块名"<<endl;cin>>pcb->name;cout<<"请输入要分配内存的大小"<<endl; goto f;e: cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl; f: cin>>pcb->size;if(pcb->size>256) goto e;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next->start+=top->size;print();while(true){do{p=top->next;cout<<"请从下列选项中进行选择"<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout<<"3.结束操作"<<endl;cout<<"请输入你的选择";cin>>choice;}while(choice!='1'&&choice!='2'&&choice!='3');switch(choice){case '1':allocate(p);print();break;case '2':recover(p);print();break;case '3':clear();return 0;break;}}}int bfa(){//最佳适应法char choice=' ';print();ptr pcb=(FreeLink *)malloc(sizeof(FreeLink));pcb->next=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块名"<<endl;cin>>pcb->name;cout<<"请输入要分配内存的大小"<<endl; goto h;g: cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl; h: cin>>pcb->size;if(pcb->size>256) goto g;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next->start+=top->size;print();while(true){do{p=top->next;cout<<"请从下列选项中进行选择"<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout<<"3.结束操作"<<endl;cout<<"请输入你的选择";cin>>choice;}while(choice!='1'&&choice!='2'&&choice!='3');switch(choice){case '1':asc(p);print();break;case '2':recover(p);print();break;case '3':clear();return 0;break;}}}int wfa(){//最坏适应法char choice=' ';print();ptr pcb=(FreeLink *)malloc(sizeof(FreeLink));pcb->next=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块名"<<endl;cin>>pcb->name;cout<<"请输入要分配内存的大小"<<endl; goto j;i: cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl; j: cin>>pcb->size;if(pcb->size>256) goto i;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next->start+=top->size;print();while(true){do{p=top->next;cout<<"请从下列选项中进行选择"<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout<<"3.结束操作"<<endl;cout<<"请输入你的选择";cin>>choice;}while(choice!='1'&&choice!='2'&&choice!='3');switch(choice){case '1':dec(p);print();break;case '2':recover(p);print();break;case '3':clear();return 0;break;}}}int main(){//主函数char choice = ' ';ptr free=(FreeLink *)malloc(sizeof(FreeLink));top=free;top->name='@';top->start=0;top->size=256;top->flag=false;top->prior=NULL;top->next=NULL;cout<<"***************Memory allocation and recovery algorithm***************"<<endl;cout<<"************************存储器的分配与回收算法************************"<<endl;while(true){do{cout<<"请从下列选项中进行选择"<<endl;cout<<"1.最先适应算法"<<endl;cout<<"2.最优适应算法"<<endl;cout<<"3.最坏适应算法"<<endl;cout<<"4.退出"<<endl;cout<<"请输入你的选择";cin>>choice;}while(choice!='1'&&choice!='2'&&choice!='3'&&choice!='4');switch(choice){case '1':ffa();break;case '2':bfa();break;case '3':wfa();break;case '4':return 0;break;}}}四、实验结果最先适应法最佳适应法最坏适应法五．实验总结知道了存储器的分配与回收算法实现方法，采用最先适应法、最佳适应法、最坏适应法分配主存空间。