操作系统实验报告
题目：存储管理算法设计
院系：计算机科学与工程学院
班级：
姓名：
学号：
一、实验题目
存储管理算法设计
二、实验日期
20##年11月3日
三、实验目的与要求
1、通过本实验，帮助学生理解存储管理的功能，掌握动态异长分区的存储分配与回收算法。
2、常用的动态异长分区的分配算法有：最先适应算法、最佳适应算法和最坏适应算法；要求选择任意一种算法，设计相应的数据结构，模拟内存空间的分配和回收。实验报告中给出程序中使用的数据结构及流程图。
四、实验环境
RedHat LINUX 6.0
五、实验内容
流程图：
六、实验结果与分析
七、实验心得与体会
通过本次实验，了解并掌握了操作系统的存储管理算法的运行机理，以及常用的三种算法最佳适应算法、最先适应算法及最坏适应算法的基本思想；并通过对程序代码的调试过程，更加深刻理解了操作系统是怎么进行存储管理的。
八、实验程序代码
头文件variable_partition.h
#include <unistd.h>
#include <curses.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
#include <string.h>
#include <semaphore.h>
#define MAX_THREAD 3
#define BF_initialize_require_memory_list FF_initialize_require_memory_list
#define WF_initialize_require_memory_list FF_initialize_require_memory_list
#define BF_initialize_thread_residence_memory_list
FF_initialize_thread_residence_memory_list
#define WF_initialize_thread_residence_memory_list
FF_initialize_thread_residence_memory_list
#define WF_delete_freearea_list FF_delete_freearea_list
#define BF_delete_freearea_list FF_delete_freearea_list
#define WF_delete_require_memory_list FF_delete_require_memory_list
#define BF_delete_require_memory_list FF_delete_require_memory_list
#define WF_delete_thread_residence_memory_list
FF_delete_thread_residence_memory_list
#define BF_delete_thread_residence_memory_list
FF_delete_thread_residence_memory_list
typedef struct freearea{
struct freearea *next;
int start_address;
int size;
}FREEAREA;
typedef struct require_memory{
struct require_memory *next;
char thread_name[10];
int size;
int duration;
}REQUIRE_MEMORY;
typedef struct thread_residence_memory{
struct thread_residence_memory *next;
char thread_name[10];
int start_address;
int size;
}THREAD_RESIDENCE_MEMORY;
FREEAREA init_free_area_table[5]={
{NULL,10,10},
{NULL,40,30},
{NULL,80,5},
{NULL,145,15},
{NULL,180,20}
};
REQUIRE_MEMORY init_thread_require_memory_table[3]={
{NULL,"thread_1",20,4},
{NULL,"thread_2",10,5},
{NULL,"thread_3",5,6}
};
THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table[5]={
{NULL,"a",0,10},
{NULL,"b",20,20},
{NULL,"c",70,10},
{NULL,"d",85,60},
{NULL,"e",160,20}
};
FREEAREA *p_free_area_list=NULL;
REQUIRE_MEMORY *p_thread_require_memory_queue=NULL;
THREAD_RESIDENCE_MEMORY *p_thread_residence_memory_list=NULL;
THREAD_RESIDENCE_MEMORY *tail_thread_residence_memory_list=NULL;
pthread_mutex_t CS_THREAD_MEMORY_LIST;
pthread_mutex_t CS_SCREEN;
pthread_mutex_t CS_FREEAREA_LIST;
pthread_t h_thread[MAX_THREAD];
sem_t thread_end[MAX_THREAD];
void display_thread_residence_memory_list();
FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num);
void FF_delete_freearea_list();
REQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,
int num);
void FF_delete_require_memory_list();
THREAD_RESIDENCE_MEMORY *FF_initialize_thread_residence_memory_list
(
THREAD_RESIDENCE_MEMORY *init_table,
int num
);
void FF_delete_thread_residence_memory_list();
void* FF_thread(void *data);
int FF_require_memory(int size);
void FF_release_memory(int start_address,int size);
void FF();
void* BF_thread(void *data);
int BF_require_memory(int size);
void BF_release_memory(int start_address,int size);
void BF_insert_freearea(FREEAREA *free_node);
void BF();
void BF_initialize_freearea_list(FREEAREA *init_table,int num);
void* WF_thread(void *data);
void WF_insert_freearea(FREEAREA *free_node);
void WF_initialize_freearea_list(FREEAREA *init_table,int num);
int WF_require_memory(int size);
void WF_release_memory(int start_address,int size);
void WF();
源文件variable_partition.cpp
#include "variable_partition.h"
int main(int argc,char *argv[]){
char select;
bool end=false;
initscr();
while(!end){
clear();
refresh();
printw("|-----------------------------------|\n");
printw("| 1:first fit allocation |\n");
printw("| 2:best fit allocation |\n");
printw("| 3:worst fit allocation |\n");
printw("| 4:exit |\n");
printw("|-----------------------------------|\n");
printw("select a function(1~4):");
do{
select=(char)getch();
}while(select!='1'&&select!='2'&&select!='3'&&select!='4');
clear();
refresh();
switch(select){
case '1':
FF();
break;
case '2':
BF();
break;
case '3':
WF();
break;
case '4':
end=true;
}
printw("\nPress any key to return to main menu.");
refresh();
getch();
}
endwin();
return 0;
}
void display_thread_residence_memory_list(){
THREAD_RESIDENCE_MEMORY *p;
p=p_thread_residence_memory_list;
int i=13;
move(10,0);
printw("|-------------------|--------------------|------------------|\n");
printw("| thread_name | start_address(kB) | size(KB) |\n");
printw("|-------------------|--------------------|------------------|\n");
while(p!=NULL){
move(i,0);
printw("| %s",p->thread_name);
move(i,20);
printw("| %d",p->start_address);
move(i,41);
printw("| %d",p->size);
move(i,60);
printw("|\n");
p=p->next;
i++;
};
move(i,0);
printw("|-------------------|--------------------|------------------|\n\n");
refresh();
}
FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num){
FREEAREA *temp;
FREEAREA *head=NULL;
FREEAREA *tail=NULL;
int i;
for(i=0;i<num;i++){
temp=(FREEAREA *)malloc(sizeof(FREEAREA));
temp->start_address=init_table[i].start_address;
temp->size=init_table[i].size;
temp->next=NULL;
if(head==NULL)
head=tail=temp;
else{
tail->next=temp;
tail=tail->next;
}
};
return head;
}
void FF_delete_freearea_list(){
FREEAREA *temp;
temp=p_free_area_list;
while(temp!=NULL){
temp=p_free_area_list->next;
free(p_free_area_list);
p_free_area_list=temp;
}
p_free_area_list=NULL;
}
REQUIRE_MEMORY *
FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,int num)
{
REQUIRE_MEMORY *temp;
REQUIRE_MEMORY *head=NULL;
REQUIRE_MEMORY *tail=NULL;
int i;
for(i=0;i<num;i++){
temp=(REQUIRE_MEMORY *)malloc(sizeof(REQUIRE_MEMORY));
strcpy(temp->thread_name,init_table[i].thread_name);
temp->size=init_table[i].size;
temp->duration=init_table[i].duration;
temp->next=NULL;
if(head==NULL)
head=tail=temp;
else{
tail->next=temp;
tail=tail->next;
}
};
return head;
}
void FF_delete_require_memory_list(){
REQUIRE_MEMORY *temp;
temp=p_thread_require_memory_queue;
while(temp!=NULL){
temp=p_thread_require_memory_queue->next;
free(p_thread_require_memory_queue);
p_thread_require_memory_queue=temp;
}
p_thread_require_memory_queue=NULL;
}
THREAD_RESIDENCE_MEMORY
*FF_initialize_thread_residence_memory_list
(THREAD_RESIDENCE_MEMORY *init_table,int num)
{
THREAD_RESIDENCE_MEMORY *temp;
THREAD_RESIDENCE_MEMORY *head=NULL;
THREAD_RESIDENCE_MEMORY *tail=NULL;
int i;
for(i=0;i<num;i++){
temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
strcpy(temp->thread_name,init_table[i].thread_name);
temp->start_address=init_table[i].start_address;
temp->size=init_table[i].size;
temp->next=NULL;
if(head==NULL)
head=tail=temp;
else{
tail->next=temp;
tail=tail->next;
}
};
tail_thread_residence_memory_list=tail;
return head;
}
void FF_delete_thread_residence_memory_list(){
THREAD_RESIDENCE_MEMORY *temp=p_thread_residence_memory_list;
temp=p_thread_residence_memory_list;
while(temp!=NULL){
temp=p_thread_residence_memory_list->next;
free(p_thread_residence_memory_list);
p_thread_residence_memory_list=temp;
}
p_thread_residence_memory_list=NULL;
}
void* FF_thread(void *data){
int start_address=-1;
int i=(((REQUIRE_MEMORY *)(data))->thread_name)[7]-49;
THREAD_RESIDENCE_MEMORY *temp;
pthread_mutex_lock(&CS_SCREEN);
printw("create thread:%s\n",((REQUIRE_MEMORY *)(data))->thread_name);
refresh();
pthread_mutex_unlock(&CS_SCREEN);
while(1){
start_address=FF_require_memory(((REQUIRE_MEMORY *)(data))->size);
if(start_address>=0)
break;
else
sleep(1);
}
temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name);
temp->start_address=start_address;
temp->size=((REQUIRE_MEMORY *)(data))->size;
temp->next=NULL;
pthread_mutex_lock(&CS_THREAD_MEMORY_LIST);
tail_thread_residence_memory_list->next=temp;
tail_thread_residence_memory_list=tail_thread_residence_memory_list->next;
pthread_mutex_unlock(&CS_THREAD_MEMORY_LIST);
sleep(((REQUIRE_MEMORY *)(data))->duration);
FF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size);
sem_post(&thread_end[i]);
return 0;
}
int FF_require_memory(int size){
int start_address=-1;
FREEAREA *p;
FREEAREA *p_next;
pthread_mutex_lock(&CS_FREEAREA_LIST);
p=p_next=p_free_area_list;
while(p_next!=NULL){
if(size==p_next->size){
start_address=p_next->start_address;
if(p_next==p_free_area_list)
p_free_area_list=p_next->next;
else
p->next=p_next->next;
free(p_next);
break;
}
else
if(size<p_next->size){
start_address=p_next->start_address;
p_next->start_address+=size;
p_next->size-=size;
break;
}
else
{
p=p_next;
p_next=p_next->next;
}
}
pthread_mutex_unlock(&CS_FREEAREA_LIST);
return start_address;
}
void FF_release_memory(int start_address,int size){
pthread_mutex_lock(&CS_FREEAREA_LIST);
pthread_mutex_unlock(&CS_FREEAREA_LIST);
}
void FF(){
int i=0;
int j=0;
REQUIRE_MEMORY *p;
for(j=0;j<MAX_THREAD;j++){
sem_init(&thread_end[j],0,0);
}
pthread_mutex_init(&CS_THREAD_MEMORY_LIST,NULL);
pthread_mutex_init(&CS_FREEAREA_LIST,NULL);
pthread_mutex_init(&CS_SCREEN,NULL);
printw("First Fit\n");
refresh();
p_free_area_list=FF_initialize_freearea_list(init_free_area_table,5);
p_thread_require_memory_queue
=FF_initialize_require_memory_list(init_thread_require_memory_table,3);
p_thread_residence_memory_list
=FF_initialize_thread_residence_memory_list
(init_thread_residence_memory_table,5);
p=p_thread_require_memory_queue;
while(p!=NULL){
pthread_create(&h_thread[i],NULL,FF_thread,p);
i++;
p=p->next;
};
for(j=0;j<MAX_THREAD;j++){
sem_wait(&thread_end[j]);
}
pthread_mutex_lock(&CS_SCREEN);
printw("after all threads have finished:\n");
refresh();
display_thread_residence_memory_list();
pthread_mutex_unlock(&CS_SCREEN);
FF_delete_freearea_list();
FF_delete_require_memory_list();
FF_delete_thread_residence_memory_list();
for(j=0;j<MAX_THREAD;j++){
sem_destroy(&thread_end[j]);
}
getch();
printw("\n");
refresh();
}