介绍
list.h
#ifndef _List_h_ #define _List_h_ #include "Data.h" //******* 链表 *******// Status InitLinkList(LinkList *L); void PCBAssign(PCBType *e1, PCBType e2); Status GetElemt_L(LinkList L,int i,PCBType *e); Status ListInsert_L(LinkList L,PCBType e); Status ListDelete_L(LinkList L,int i,PCBType *e); //****** 动态顺序表 ******// void PartiAssign(PartiType *e1, PartiType e2); Status InitList_Sq(SqList *L); Status ListInsert_Sq(SqList *L,int i,PartiType e); Status ListDelete_Sq(SqList *L,int i,PartiType *e); #endifMemoryManage.h
#ifndef _MemoryManage_h_ #define _MemoryManage_h_ #include "List.h" //***** PCB链表操作 *****// Status InsertProcess(LinkList Q,PCBType e); Status DeleteProsess(LinkList Q,int i,PCBType *e); //***** 分区表操作 *****// Status InsertTable(SqList *L, int i, PartiType e); Status DeleteTable(SqList *L, int i, PartiType *e); int SelectPart(PCB* pPCB, SqList *pPartTable, AllocatStrategy AS); int MallocMemory(PCB *pe, SqList *pPartTable,int i); void SearchSpace(PCBList PCBdata, SqList *partTable, AllocatStrategy AS); void FreeMemory(int pos, SqList *pPartTable); void InitAllocation(PCBList PCBdata, PartTable *partTable, AllocatStrategy AS); void PrintProQueue(LinkList L); void PrintPartTable(PartTable L); #endif实现
list.c
#include "List.h" Status InitLinkList(LinkList *L) { *L = (LinkList)malloc(sizeof(LNode)); strcpy((*L)->data.Name, ""); (*L)->Next = NULL; return OK; } void PCBAssign(PCBType *e1, PCBType e2) { strcpy(e1->Name,e2.Name); e1->DistbutSt = e2.DistbutSt; e1->MemorySize = e2.MemorySize; e1->StartAddress = e2.StartAddress; } Status GetElemt_L(LinkList L,int i,PCBType *e) { LinkList p = L->Next; //指向第j个结点 int j = 1; //从第一个开始往后找 while ( p && j < i ) //p不为空且j < i { p = p->Next; j; } //p为空，说明链表循环结束了，没有达到第一个结点 j==i if (!p || j > i) //因为这里对i 没有做判断 如果 i==0 或 负数 条件成立 //对于 i == j == 1 在这种情况下，不需要循环正好 返回 { return ERROR; } *e = p->data; //通过寻址改变 地址内存中元素的值 return OK; } //链表按优先级插入:从大到小排序 Status ListInsert_L(LinkList L,PCBType e) ///这样的修改应该是错误的 p = *L出错 { LinkList p = L, s; while (p->Next) p = p->Next; s = (LinkList)malloc(sizeof(LNode)); PCBAssign(&s->data, e); s->Next = p->Next; p->Next = s; return OK; } 删除链表中的头部 Status ListDelete_L(LinkList L,int i,PCBType *e) { LinkList p = L, q; int j = 0; while (p->Next && j < i-1) { p = p->Next; j; } if(!p->Next || j > i - 1) return ERROR; q = p->Next; p->Next = q->Next; PCBAssign(e, q->data); free(q); return OK; } // 初始化 /// void PartiAssign(PartiType *e1, PartiType e2) { e1->PartitionSize = e2.PartitionSize; e1->PartStartAddr = e2.PartStartAddr; strcpy(e1->Name, e2.Name); } Status InitList_Sq(SqList *L) { ///构建空的线性表L L->elem = (PartiType *)malloc((LIST_INIT_SIZE)*sizeof(PartiType)); if(!L->elem) return ERROR; //存储分配失败 L->length = 0; ///空表长度为0 L->listsize = LIST_INIT_SIZE; //初始存储的容量 return OK; } ///在顺序线性表L的第一个位置插入新元素之前e Status ListInsert_Sq(SqList *L,int i,PartiType e) { ///在顺序线性表L的第一个位置插入新元素之前e //i的合法值为1 <= i <= ListLength_Sq(L) 1 PartiType *q, *p, *newbase; if(i < 1 || i > L->length 1 ) return ERROR; //i值不合法 if(L->length >= L->listsize){ ///当前存储空间已满，增加分配 newbase = (PartiType *)realloc(L->elem ,(L->listsize LISTINCREMENT)*sizeof(PartiType)); if(!newbase) return ERROR; //存储分配失败 L->elem = newbase; //新基址 L->listsize = LISTINCREMENT; //增加存储容量 } q = &(L->elem[i - 1]); //q为插入位置 for(p = &(L->elem[L->length-1]);p >= q; --p) PartiAssign((p 1),*p); ////插入位置后续元素右移 PartiAssign(q ,e); //插入e L->length ; return OK; } ///在顺序线性表L中删除第一个元素，并用e返回其值 Status ListDelete_Sq(SqList *L,int i,PartiType *e) { ///在顺序线性表L中删除第一个元素，并用e返回其值 //i的合法值为1 <= i <= ListLength_Sq(L) PartiType *p,*q; if((i < 1) || (i > L->length)) return ERROR; //i值不合法 p = &(L->elem[i-1]); //p被删除元素的位置 PartiAssign(e, *p); ///将被删除元素的值赋予e （待定） q = L->elem L->length-1; ////移动到表尾元素的位置 for ( p;p<=q; p) PartiAssign((p-1), *p); ///元素被删除后左移 L->length--; return OK; } #include "MemoryManage.h" extern int CF_i; //***** PCB链表操作 *****// Status InsertProcess(LinkList Q,PCBType e) { return ListInsert_L(Q, e); } Status DeleteProsess(LinkList Q,int i,PCBType *e) { return ListDelete_L(Q ,i,e); }
//***** 分区表操作 *****//
Status InsertTable(SqList *L, int i, PartiType e)
{
return ListInsert_Sq(L,i, e);
}
Status DeleteTable(SqList *L, int i, PartiType *e)
{
return ListDelete_Sq(L, i, e);
}
//返回第几个内存块，从1开始，若返回0，则代表错误
int SelectPart(PCB* pPCB, SqList *pPartTable,AllocatStrategy AS)
{
int i;
int BestArr[20] = {0}, k = 0, min = 500, min_i = -1;
if(AS == FirstPriority)
{
for (i = 0; i < pPartTable->length; ++i)
if(!strcmp(pPartTable->elem[i].Name, "") && pPartTable->elem[i].PartitionSize >= pPCB->MemorySize)
return i + 1;
}else if(AS == BestAdapt)
{
以下补充 /
for(i = 0; i < pPartTable->length; ++i){
if(!strcmp(pPartTable->elem[i].Name, "") && pPartTable->elem[i].PartitionSize >= pPCB->MemorySize)
if(pPartTable->elem[i].PartitionSize - pPCB->MemorySize < min){
min = pPartTable->elem[i].PartitionSize - pPCB->MemorySize;
min_i = i;
}
}
return min_i+1;
}else if(AS == CycleFirst)
{
int flag = 0;
以下补充 /
for(i = CF_i; i < pPartTable->length; i = (i+1)%(pPartTable->length)){
if(!strcmp(pPartTable->elem[i].Name, "") && pPartTable->elem[i].PartitionSize >= pPCB->MemorySize){
CF_i = (i+1)%pPartTable->length;
return i + 1;
}
if(flag && i == CF_i){
break;
}
if(i == CF_i){
flag = 1;
}
}
return 0;
}else
{
printf("算法选择有误！\n");
}
return ERROR;
}
//通过SelectPart查找是否存在可以分配的分区，在main函数中进行调用本方法进行内存的分配
int MallocMemory(PCB *pe, SqList *pPartTable,int i)
{
PartiType se = {0, 0, {0}};
以下补充 /
//修改PCB
pe->DistbutSt = Allocated;
pe->StartAddress = pPartTable->elem[i].PartStartAddr;
if(pPartTable->elem[i].PartitionSize == pe->MemorySize){
strcpy(pPartTable->elem[i].Name, pe->Name);
} else {
//修改分区使用说明表
strcpy(pPartTable->elem[i].Name, "");
pPartTable->elem[i].PartitionSize -= pe->MemorySize;
pPartTable->elem[i].PartStartAddr += pe->MemorySize;
//新建一个表目, 并插入分区表使用说明表
strcpy(se.Name, pe->Name);
se.PartitionSize = pe->MemorySize;
se.PartStartAddr = pe->StartAddress;
InsertTable(pPartTable, i+1, se);
}
return OK;
}
void InitAllocation(PCBList PCBdata, PartTable *pPartTable,AllocatStrategy AS)
{
LNode *p;
int pos;
p = PCBdata->Next;
while (p)
{
if(p->data.DistbutSt == Unallocated)
{
pos = SelectPart(&(p->data), pPartTable, AS);//从1开始
if(pos)
{
MallocMemory( &(p->data), pPartTable, pos - 1);
}
}
p = p->Next;
}
}
//回收指定位置的内存空间
void FreeMemory(int pos, SqList *pPartTable)//没考虑 pos为0情况，没考虑删除后修改起始地址情况
{
PartiType se = {0, 0, {0}};
int flag = 0;
以下补充 /
if(pos != pPartTable->length-1){
//为后一块分配
if(!strcmp(pPartTable->elem[pos+1].Name, "")){
strcpy(pPartTable->elem[pos].Name, "");
pPartTable->elem[pos].PartitionSize += pPartTable->elem[pos+1].PartitionSize;
strcpy(se.Name, pPartTable->elem[pos+1].Name);
se.PartitionSize = pPartTable->elem[pos+1].PartitionSize;
se.PartStartAddr = pPartTable->elem[pos+1].PartStartAddr;
DeleteTable(pPartTable, pos+1, &se);
flag = 1;
}
}
if(pos != 0){
//为前一块分配
if(!strcmp(pPartTable->elem[pos-1].Name, "")){
strcpy(pPartTable->elem[pos-1].Name, "");
pPartTable->elem[pos-1].PartitionSize += pPartTable->elem[pos].PartitionSize;
strcpy(se.Name, pPartTable->elem[pos-1].Name);
se.PartitionSize = pPartTable->elem[pos-1].PartitionSize;
se.PartStartAddr = pPartTable->elem[pos-1].PartStartAddr;
DeleteTable(pPartTable, pos-1, &se);
flag = 1;
}
}
if(!flag){
strcpy(pPartTable->elem[pos].Name, "");
}
}
void SearchSpace(PCBList PCBdata, SqList *partTable, AllocatStrategy AS)
{
int pos;
LNode *p;
p = PCBdata->Next;
while (p)
{
if(p->data.DistbutSt == Unallocated)
{
pos = SelectPart(&(p->data), partTable, AS);//从1开始
if(pos)
{
MallocMemory(&(p->data), partTable, pos - 1);
}
}
p = p->Next;
}
}
void PrintProQueue(LinkList L)
{
int i = 0;
L = L->Next;
printf(" ----------------------------------------\n");
printf("|进程名 | 起始位置 | 申请大小 | 是否分配 |\n");
while(L)
{
printf("| %s | %4d | %4d | %4s |\n",
L->data.Name, L->data.StartAddress, L->data.MemorySize, L->data.DistbutSt == Allocated? "是" : "否");
L = L->Next;
}
printf(" ----------------------------------------\n");
}
void PrintPartTable(PartTable L)
{
int i = 0, j = 0;
printf(" ----------------------------------------\n");
printf("|分区号 | 起始位置 | 分区大小 | 是否分配 |\n");
for (i = 0; i < L.length; ++i)
printf("| %2d | %4d | %4d | %4s |\n",
i + 1 , L.elem[i].PartStartAddr, L.elem[i].PartitionSize , strcmp(L.elem[i].Name, "") ? L.elem[i].Name :"否");
printf(" ----------------------------------------\n");
}main
#include "MemoryManage.h"
/*实验06 动态分区分配
*/
int CF_i;
void InputPCBData(PCBList * pPCBdata)
{
PCBType e = {
{0}, 0, 0, Unallocated};
strcpy(e.Name,"P1");
e.MemorySize = 16;
InsertProcess(*pPCBdata,e);
strcpy(e.Name,"P2");
e.MemorySize = 32;
InsertProcess(*pPCBdata,e);
strcpy(e.Name,"P3");
e.MemorySize = 48;
InsertProcess(*pPCBdata,e);
strcpy(e.Name,"P4");
e.MemorySize = 96;
InsertProcess(*pPCBdata,e);
strcpy(e.Name,"P5");
e.MemorySize = 100;
InsertProcess(*pPCBdata,e);
}
void SetFixedZone(PartTable * pPartdata)
{
PartiType se = {0, 0, {0}};
se.PartStartAddr = 16;
se.PartitionSize = 512 - 16;
strcpy(se.Name, "");
InsertTable(pPartdata, 1, se);
}
//0 - 15Kb 操作系统占用 总大小512KB
int main(void)
{
PCBList PCBdata; //PCBdata里面存放原始PCB数据
PartTable partTable; //分区表
char PcbName[NAME_MAXSIZE] = {0}, choice;
PCBType PCBe = {
{0}, 0, 0, Unallocated};
PartiType Parte = {0, 0};
PCBType *pcb = NULL;
LNode *p;
AllocatStrategy AS = CycleFirst; //FirstPriority, BestAdapt, CycleFirst
//AllocatStrategy AS = BestAdapt;
int i, size, pos;
//分区表
InitList_Sq(&partTable);
SetFixedZone(&partTable);
//进程表
InitLinkList(&PCBdata);
InputPCBData(&PCBdata);
//初始化
InitAllocation(PCBdata, &partTable, AS);
CF_i = 0;
PrintProQueue(PCBdata);
PrintPartTable(partTable);
while(true)
{
system("cls");
PrintProQueue(PCBdata);
PrintPartTable(partTable);
printf(" ================================================\n");
printf("| 1.结 束 进 程 |\n");
printf("| 2.添 加 进 程 |\n");
printf("| 3.退 出 系 统 |\n");
printf(" ================================================\n");
printf("请选择:");
fflush(stdin);
scanf("%c",&choice);
switch (choice)
{
case '1':
printf("要结束的进程名:");
scanf("%s",PcbName);
for (p = PCBdata->Next, i = 1; p && strcmp(PcbName, p->data.Name); i++, p = p->Next);
if(!p)
{
printf("进程名输入错误!\n");
break;
}
DeleteProsess(PCBdata, i, &PCBe);
for(i = 0; i < partTable.length; i++)
{
if(!strcmp(PcbName, partTable.elem[i].Name))
{
FreeMemory(i ,&partTable);
break;
}
}
SearchSpace( PCBdata, &partTable, AS);
break;
case '2':
printf("请输入添加的进程名，进程所占内存大小:");
scanf("%s%d",PcbName , &size);
PCBe.DistbutSt = Unallocated;
PCBe.StartAddress = 0;
strcpy(PCBe.Name, PcbName);
PCBe.MemorySize = size;
pos = SelectPart(&(PCBe), &partTable, AS);//从1开始
if(pos)
MallocMemory(&(PCBe), &partTable, pos - 1);
InsertProcess(PCBdata, PCBe);
break;
case '3':
return 0;
default:
printf("选择项输入错误，重新选择！\n");
break;
}
PrintProQueue(PCBdata);
PrintPartTable(partTable);
system("pause");
}
return 0;
}