实验三 存储器管理（含虚拟存储器）
存储器管理（含虚拟存储器）
本例为哈工大威海操作系统实验三，具体实验要求
一、实验目的
1．掌握内存管理的基本方法和分区法内存分配的基本原理。
2．学会Ubuntu或者windows操作系统下使用高级语言函数和系统调用进行编程的方法。
3．利用高级语言设计实现分区法内存分配算法。
4．验证无虚存的存储管理机制。
二、实验要求
1．学生应完成如下章节的学习：进程和线程、调度、存储管理。
2．使用高级语言编程，调用相关系统调用进行设计实现。
三、实验内容
1．创建空闲存储管理表和模拟内存。
2．设计并实现一个内存分配程序，分配策略可以分别采用最先适应算法、最佳适应算法和最坏适应算法等，并评价不同分配算法的优劣。
3．提供一个用户界面，利用它用户可输入不同的分配策略。
4．进程向内存管理程序发出申请、释放指定数量的内存请求，内存管理程序调用对应函数，响应请求。
四、实验方案指导
该实验方案由以下几个关键设计项目组成。
1．设计实现一个空闲分区表。
2．设计实现模拟内存。
考虑实现的便利，本方案不访问真正的内存。定义一个字符数组char mm[mem_size]或使用Linux系统调用mm=malloc(mem_size)，用来模拟内存。
利用指针对模拟内存进行访问。
3．设计一组管理物理内存空间的函数。用户接口由以下三个函数组成：
voidmm_request(int n)
申请n个字节的内存空间。如申请成功，则返回所分配空间的首地址；如不能满足申请，则返回空值。
void mm_release(voidp)
释放先前申请的内存。如果释放的内存与空闲区相邻，则合并为一个大空闲区；如果与空闲区不相邻，则成为一个单独的空闲区。
void*mm_init(int mem_size)
内存初始化。返回mm指针指向的空闲区。
4．设计实现不同策略的内存分配程序。
对于采用不同分配策略的内存管理程序，从以下两个方面进行调度程序性能的比对：内存利用率以及找到一个合适的分配空间所需查找的步骤。
设置一个模拟实验。分别构建一个随机生成的请求与释放队列。释放队列中的操作总是得到满足，队列总为空；请求队列的操作能否被满足，取决于空闲区能否满足申请的空间大小。若不能满足，则该操作在队列中等待相应释放操作唤醒。请求队列采用FIFO管理，以避免饥饿现象的发生。
内存管理程序应对内存初始化，随机设定内存空间的占有、空闲情况，随机设定申请和释放的操作队列。调用释放操作开始运行，调用申请操作，如能满足，则分配空间，否则等待释放操作唤醒。
下面给出一个模拟内存管理的程序框架（伪码形式）。可对性能数据指标进行统计。
for(i=0;i<sim_step;i++){ /设定模拟程序执行次数/
do{ /循环调用请求操作，直到请求不成功/
get size n of next request; /设定请求空间大小/
mm_request(n); /调用请求操作/
}while(request successful); /请求成功，循环继续/
record memory utilization; /统计内存使用率/
select block p to be release; /释放某空间p/
release§; /调用释放操作/
｝
以上程序由主循环控制固定次数的模拟步骤。每次循环，程序完成如下处理步骤：内循环尽可能多地满足内存请求，请求内存大小值随机生成。一旦请求失败，挂起内存管理程序，直至释放操作被执行。此时进行系统内存利用率的统计、计算，随机挑选一个内存分配空间完成释放操作。本次主循环执行完毕，开始下一次循环。
需要在程序中完成以下设计：确定请求分配空间大小，统计性能数据，选择一个内存区释放。
Excel类
package com.company;
public class Excel {
private int num;
private int size;
private int addr;
private String status;
public void setStatus(String status) {
this.status = status;
}
public String getStatus() {
return status;
}
public void setAddr(int addr) {
this.addr = addr;
}
public int getAddr() {
return addr;
}
public int getNum() {
return num;
}
public int getSize() {
return size;
}
public void setNum(int num) {
this.num = num;
}
public void setSize(int size) {
this.size = size;
}
public Excel(int num,int size,int addr,String status){
this.addr=addr;
this.num=num;
this.size=size;
this.status=status;
}
public void input(Excel excel){
this.num=excel.getNum();
this.size=excel.getSize();
this.addr=excel.getAddr();
this.status=excel.getStatus();
}
}
MBC类
package com.company;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
public class MCB {
private int[] mm;
private ArrayList<Excel> chart=new ArrayList<Excel>();
private Random r=new Random();
private Queue<Integer> queue=new LinkedList();
private boolean request1(int n){//最先适应算法
boolean flag=false;
for(int i=0;i<chart.size();i++){
if(chart.get(i).getStatus().equals("free")&&chart.get(i).getSize()>n){
chart.get(i).setStatus("allocated");
for(int j=chart.get(i).getAddr();j<(chart.get(i).getAddr()+n);j++){
mm[j]=1;
}
flag=true;
}
}
return flag;
}
private boolean request2(int n){//最佳适应算法
boolean flag=false;
int max=10000;
int j=10000;
for(int i=0;i<chart.size();i++){
if(chart.get(i).getStatus().equals("free")&&chart.get(i).getSize()>n&&max>chart.get(i).getSize()-n){
max=chart.get(i).getSize()-n;
j=i;
}
}
if(j!=10000){
chart.get(j).setStatus("allocated");
for(int k=chart.get(j).getAddr();k<(chart.get(j).getAddr()+n);k++){
mm[k]=1;
}
flag=true;
}
return flag;
}
private void release(int num) {
for (int i = 0; i < chart.size(); i++) {
if (chart.get(i).getNum() == num) {
if (i == 0) {
if (chart.get(i + 1).getStatus().equals("free")) {
chart.get(i).setStatus("free");
chart.get(i).setSize(chart.get(i).getSize() + chart.get(i + 1).getSize());
for (int j = i + 2; j < chart.size(); j++) {
chart.get(j).setNum(j - 1);
}
for (int j = chart.get(i).getAddr(); j < chart.get(i).getSize(); j++) {
mm[j] = 0;
}
} else {
chart.get(i).setStatus("free");
for (int j = chart.get(i).getAddr(); j < chart.get(i).getSize(); j++) {
mm[j] = 0;
}
}
} else if (i == (chart.size() - 1)) {
if (chart.get(i - 1).getStatus().equals("free")) {
chart.get(i - 1).setSize(chart.get(i).getSize() + chart.get(i - 1).getSize());
chart.remove(i);
for (int j = chart.get(i - 1).getAddr(); j < chart.get(i - 1).getSize(); j++) {
mm[j] = 0;
}
} else {
chart.get(i).setStatus("free");
for (int j = chart.get(i).getAddr(); j < chart.get(i).getSize(); j++) {
mm[j] = 0;
}
}
} else {
if (chart.get(i + 1).getStatus().equals("free") && chart.get(i - 1).getStatus().equals("free")) {
chart.get(i - 1).setSize(chart.get(i).getSize() + chart.get(i + 1).getSize() + chart.get(i - 1).getSize());
for (int j = i + 2; j < chart.size(); j++) {
chart.get(j).setNum(j - 1);
}
for (int j = chart.get(i - 1).getAddr(); j < chart.get(i - 1).getSize(); j++) {
mm[j] = 0;
}
} else if (chart.get(i + 1).getStatus().equals("free")) {
chart.get(i).setStatus("free");
chart.get(i).setSize(chart.get(i).getSize() + chart.get(i + 1).getSize());
for (int j = i + 2; j < chart.size(); j++) {
chart.get(j).setNum(j - 1);
}
for (int j = chart.get(i).getAddr(); j < chart.get(i).getSize(); j++) {
mm[j] = 0;
}
} else if (chart.get(i - 1).getStatus().equals("free")) {
chart.get(i - 1).setSize(chart.get(i).getSize() + chart.get(i - 1).getSize());
chart.remove(i);
for (int j = i + 1; j < chart.size(); j++) {
chart.get(j).setNum(j - 1);
}
for (int j = chart.get(i - 1).getAddr(); j < chart.get(i - 1).getSize(); j++) {
mm[j] = 0;
}
} else {
chart.get(i).setStatus("free");
for (int j = chart.get(i).getAddr(); j < chart.get(i).getSize(); j++) {
mm[j] = 0;
}
}
chart.get(i).setStatus("free");
for (int j = chart.get(i).getAddr(); j < chart.get(i).getSize(); j++) {
mm[j] = 0;
}
}
}
}
}
private void init(int mm_size){
int length=mm_size;
int addr=0;
for(int i=0;i<19;i++){
int ran = r.nextInt(92);
Excel excel = new Excel(i,ran,addr,"free");
length-=ran;
addr+=ran;
chart.add(excel);
if(length==0){
break;
}
}
if(length!=0){
Excel excel=new Excel(19,length,addr,"free");
chart.add(excel);
}
for(int i=0;i<chart.size();i++){
System.out.println("序号:"+chart.get(i).getNum()+" 首地址："+chart.get(i).getAddr()+" 长度："+chart.get(i).getSize());
}System.out.println("----------------");
mm=new int[mm_size];
for(int i=0;i<mm_size;i++){
mm[i]=0;
}
}
public void run(){
int mm_size=1000;
init(mm_size);
Random random=new Random();
int n;
boolean flag;
int sum=0;
for(int i=0;i<30;i++){
do{
if(queue.size()==0) {
n = random.nextInt(200);
flag = request2(n);
System.out.println("申请长度为 "+n+" 的空间");
if (!flag) {
System.out.println("申请失败，请求入队，等待释放资源后申请");
queue.offer(n);
}else{
System.out.println("申请成功");
}
}else {
Integer integer=queue.poll();
n=integer.intValue();
flag = request2(n);
System.out.println("请求队列中的第一个请求："+n);
if (!flag) {
System.out.println("队列中的第一个请求未得到满足，该请求入队");
queue.offer(n);
}else{
System.out.println("申请成功");
}
}
}while(flag);
for(int j=0;j<mm_size;j++){
if (mm[j]==1) {
sum++;
}
}
double result=(double)sum/(double)mm_size;
System.out.println("内存使用率为"+result*100+"%");
sum=0;
int num=random.nextInt(chart.size());
release(num);
System.out.println("释放第 "+num+" 个资源");
System.out.println("--------------------");
}
}
}
Main类
package com.company;
public class Main {
public static void main(String[] args) {
MCB mcb=new MCB();
mcb.run();
}
}