介绍
data.h
#ifndef _Data_h_ #define _Data_h_ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define LIST_INIT_SIZE 10 #define LISTINCREMENT 2 #define true 1 #define false 0 #define PCBType PCB #define Status int #define OK 1 #define ERROR 0 #define NAME_MAXSIZE 20 #define PCB_Num 5 #define LIST_INITSIZE 10 #define PartiType PartitionInfo #define BlockNumType PageData //分页信息 #define TotalMemory 512 //KB #define PageSize 16 //通常为1 ~ 8KB //过程中申请内存的大小[16， 256]KB 256 / 8 = 32页 typedef enum { Unallocated, Allocated }DistributState, PartitionSt; typedef struct { //分区号用数组下标代替 int PartStartAddr; char Name[NAME_MAXSIZE];//如果是空的，则分区空闲 }PartitionInfo; typedef struct { PartitionInfo *elem; int listsize; //表容量 int length; //元素数 }SqList_f, PartTable; //分区使用说明表 typedef struct { int BlockNum; //块号 DistributState DistbutSt; //分配状态 }PageData; typedef struct { PageData *elem; int listsize; int length; }SqList_y, PageTable; //页表 typedef struct { char Name[NAME_MAXSIZE]; //进程名 int MemorySize; //内存大小 PageTable *pPagetable; //页表指针 }PCB; typedef struct Node { PCBType data; struct Node * Next; }LNode, *LinkList, *PCBList; #endif 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_f(PartiType *e1, PartiType e2); Status InitList_f(SqList_f *L); Status ListInsert_f(SqList_f *L,int i,PartiType e); Status ListDelete_f(SqList_f *L,int i,PartiType *e); //****** 页表 ******// void PartiAssign_y(BlockNumType *e1, BlockNumType e2); Status InitList_y(SqList_y **L); Status ListInsert_y(SqList_y *L,int i,BlockNumType e); Status ListDelete_y(SqList_y *L,int i,BlockNumType *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_f(SqList_f *L, int i, PartiType e); ///删除分区表元素 Status DeleteTable_f(SqList_f *L, int i, PartiType *e); //****** 页 表 操 作 ******// ///插入页面元素 Status InsertTable_y(SqList_y *L, int i, BlockNumType e); ///删除页面元素 Status DeleteTable_y(SqList_y *L, int i, BlockNumType *e); Status LoadPages(PageTable *L, int size); Status MallocMemory(PCB *pe, SqList_f *pPartTable, int *arr); Status SelectPart(PCB* pPCB, SqList_f *pPartTable,int *arr); void SearchSpace(PCBList PCBdata, SqList_f *partTable); void FreeMemory(int *arr, int len, SqList_f *pPartTable); void InitAllocation(PCBList PCBdata, PartTable *partTable); void PrintProQueue(LinkList L); void PrintPartTable(PartTable L); #endif实现
#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->MemorySize = e2.MemorySize; e1->pPagetable = e2.pPagetable; } 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_f(PartiType *e1, PartiType e2) { e1->PartStartAddr = e2.PartStartAddr; strcpy(e1->Name, e2.Name); } Status InitList_fSqList_f *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中第i个位置之前插入新的元素e
Status ListInsert_f(SqList_f *L,int i,PartiType e)
{
//在顺序线性表L中第i个位置之前插入新的元素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_f((p+1),*p); //插入位置及之后的元素右移
PartiAssign_f(q ,e); //插入e
L->length++;
return OK;
}
//在顺序线性表L中删除第i个元素，并用e返回其值
Status ListDelete_f(SqList_f *L,int i,PartiType *e)
{
//在顺序线性表L中删除第i个元素，并用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_f(e, *p); //将被删除元素的值赋给e （待定）
q = L->elem + L->length-1; //移动到表尾元素的位置
for (++p;p<=q;++p)
PartiAssign_f((p-1), *p); //被删除元素之后的元素左移
L->length--;
return OK;
}
//****** 页表 ******//
void PartiAssign_y(BlockNumType *e1, BlockNumType e2)
{
(*e1).BlockNum = e2.BlockNum;
(*e1).DistbutSt = e2.DistbutSt;
}
Status InitList_y(SqList_y **L)
{
//构造一个空的线性表L
(*L) = (PageTable *)malloc(sizeof(PageTable));//不可缺少
(*L)->elem = (BlockNumType *)malloc((LIST_INIT_SIZE)*sizeof(BlockNumType));
if(!(*L)->elem) return ERROR; //存储分配失败
(*L)->length = 0; //空表长度为0
(*L)->listsize = LIST_INIT_SIZE; //初始存储的容量
return OK;
}
//在顺序线性表L中第i个位置之前插入新的元素e
Status ListInsert_y(SqList_y *L,int i,BlockNumType e)
{
//在顺序线性表L中第i个位置之前插入新的元素e
//i的合法值为1 <= i <= ListLength_Sq(L)+1
BlockNumType *q, *p, *newbase;
if(i < 1 || i > L->length + 1 ) return ERROR; //i值不合法
if(L->length >= L->listsize){ //当前存储空间已满，增加分配
newbase = (BlockNumType *)realloc(L->elem
,(L->listsize + LISTINCREMENT)*sizeof(BlockNumType));
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_y((p+1),*p); //插入位置及之后的元素右移
PartiAssign_y(q ,e); //插入e
L->length++;
return OK;
}
//在顺序线性表L中删除第i个元素，并用e返回其值
Status ListDelete_y(SqList_y *L,int i,BlockNumType *e)
{
//在顺序线性表L中删除第i个元素，并用e返回其值
//i的合法值为1 <= i <= ListLength_Sq(L)
BlockNumType *p,*q;
if((i < 1) || (i > L->length))
return ERROR; //i值不合法
p = &(L->elem[i-1]); //p为被删除元素的位置
PartiAssign_y(e, *p); //将被删除元素的值赋给e （待定）
q = L->elem + L->length-1; //移动到表尾元素的位置
for (++p;p<=q;++p)
PartiAssign_y((p-1), *p); //被删除元素之后的元素左移
L->length--;
return OK;
}memorymanage.c
#include "MemoryManage.h"
//***** 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_f(SqList_f *L, int i, PartiType e)
{
return ListInsert_f(L,i, e);
}
Status DeleteTable_f(SqList_f *L, int i, PartiType *e)
{
return ListDelete_f(L, i, e);
}
//***** 页表操作 *****//
Status InsertTable_y(SqList_y *L, int i, BlockNumType e)
{
return ListInsert_y(L,i, e);
}
Status DeleteTable_y(SqList_y *L, int i, BlockNumType *e)
{
return ListDelete_y(L, i, e);
}
Status LoadPages(PageTable *L, int size)
{
int i, pageNum = ceil( size * 1.0 / PageSize) ;
PageData e = {-1, Unallocated};
for (i = 0; i < pageNum; i++)
{
if(!InsertTable_y(L, L->length + 1, e))
return ERROR;
}
return OK;;
}
//若返回0，则代表错误
Status SelectPart(PCB* pPCB, SqList_f *pPartTable,int *arr)
{
/ 以下补充 /
int i = 0, j = 0;
while(i < pPCB->pPagetable->length && j < pPartTable->length){
if(pPCB->pPagetable->elem[i].DistbutSt == Unallocated){
if(!strcmp(pPartTable->elem[j].Name, "")){
arr[i] = j;
++i;
++j;
} else {
++j;
}
} else {
++i;
}
}
if(i == pPCB->pPagetable->length){
return OK;
}
return ERROR;
}
Status MallocMemory(PCB *pe, SqList_f *pPartTable, int *arr)
{
int i, pageNum ;
以下补充 /
for(i = 0; i < pe->pPagetable->length; ++i){
if(pe->pPagetable->elem[i].DistbutSt == Unallocated){
pe->pPagetable->elem[i].BlockNum = arr[i];
pe->pPagetable->elem[i].DistbutSt = Allocated;
strcpy(pPartTable->elem[arr[i]].Name, pe->Name);
}
}
return ERROR;
}
void InitAllocation(PCBList PCBdata, PartTable *pPartTable)
{
LNode *p;
int pos, arr[20] = {0};
p = PCBdata->Next;
while (p)
{
if(p->data.pPagetable->elem[0].DistbutSt == Unallocated)
{
if(SelectPart(&(p->data), pPartTable, arr))
{
MallocMemory(&(p->data), pPartTable, arr);
}
}
p = p->Next;
}
}
//该释放进程只在结束进程时用到，因此不用管进程信息
void FreeMemory(int *arr, int len, SqList_f *pPartTable)
{
int i;
以下补充 /
for(i = 0; i < len; ++i){
strcpy(pPartTable->elem[arr[i]].Name, "");
}
}
void SearchSpace(PCBList PCBdata, SqList_f *partTable)
{
int pos, arr[20] = {0};
LNode *p;
p = PCBdata->Next;
while (p)
{
if(p->data.pPagetable->elem[0].DistbutSt == Unallocated)
{
if(SelectPart(&(p->data), partTable, arr))
{
MallocMemory(&(p->data), partTable, arr);
}
}
p = p->Next;
}
}
void PrintProQueue(LinkList L)
{
int i = 0;
L = L->Next;
while(L)
{
printf(" -----------------------------\n");
printf("|进程名 | 申请大小 |\n");
printf("| %s | %4d |\n", L->data.Name, L->data.MemorySize);
printf("%s页表信息如下：\n| 页号 | 块号 | 是否分配 |\n", L->data.Name);
for (i = 0; i < L->data.pPagetable->length; i++)
printf("| %4d | %4d | %4s |\n", i , L->data.pPagetable->elem[i].BlockNum,
L->data.pPagetable->elem[i].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 , L.elem[i].PartStartAddr, PageSize , strcmp(L.elem[i].Name, "") ? L.elem[i].Name :"否");
printf(" ----------------------------------------\n");
}main
#include "MemoryManage.h"
/* 实验08 基本分页 */
void InputPCBData(PCBList * pPCBdata)
{
PCBType e = {
{0}, 0, NULL};
strcpy(e.Name,"P1");
e.MemorySize = 16;
InitList_y(&(e.pPagetable));
LoadPages(e.pPagetable, e.MemorySize);
InsertProcess(*pPCBdata,e);
strcpy(e.Name,"P2");
e.MemorySize = 32;
InitList_y(&(e.pPagetable));
LoadPages(e.pPagetable, e.MemorySize);
InsertProcess(*pPCBdata,e);
strcpy(e.Name,"P3");
e.MemorySize = 48;
InitList_y(&(e.pPagetable));
LoadPages(e.pPagetable, e.MemorySize);
InsertProcess(*pPCBdata,e);
strcpy(e.Name,"P4");
e.MemorySize = 96;
InitList_y(&(e.pPagetable));
LoadPages(e.pPagetable, e.MemorySize);
InsertProcess(*pPCBdata,e);
strcpy(e.Name,"P5");
e.MemorySize = 100;
InitList_y(&(e.pPagetable));
LoadPages(e.pPagetable, e.MemorySize);
InsertProcess(*pPCBdata,e);
}
void SettingPage(PartTable * pPartdata)
{
PartiType se = {0, {0}};
int Num = (512 - 16) / PageSize , i;
for (i = 0; i < Num; ++i)
{
se.PartStartAddr = 16 + i * PageSize;
InsertTable_f(pPartdata, i + 1, se);
}
}
//0 - 15Kb 操作系统占用 总大小512KB
int main(void)
{
PCBList PCBdata; //PCBdata里面存放原始PCB数据
PartTable partTable; //分区表
char PcbName[NAME_MAXSIZE] = {0}, choice;
PCBType PCBe = {
{0}, 0, NULL};
PartiType Parte = {0, 0};
PCBType *pcb = NULL;
LNode *p;
int i, size, pos, arr[20] = {0}, k = 0;
InitList_f(&partTable);
SettingPage(&partTable);
InitLinkList(&PCBdata);
InputPCBData(&PCBdata);
InitAllocation(PCBdata, &partTable);
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);
k = 0;
for(i = 0; i < partTable.length; i++)
{
if(!strcmp(PcbName, partTable.elem[i].Name))
{
arr[k++] = i;
}
}
FreeMemory(arr, k, &partTable);
SearchSpace(PCBdata, &partTable);
break;
case '2':
printf("请输入添加的进程名，进程所占内存大小:");
scanf("%s%d",PcbName , &size);
strcpy(PCBe.Name, PcbName);
PCBe.MemorySize = size;
InitList_y(&(PCBe.pPagetable));
LoadPages(PCBe.pPagetable, PCBe.MemorySize);
if(SelectPart(&(PCBe), &partTable, arr))
MallocMemory(&(PCBe), &partTable, arr);
InsertProcess(PCBdata, PCBe);
break;
case '3':
return 0;
default:
printf("选择项输入错误，重新选择！\n");
break;
}
PrintProQueue(PCBdata);
PrintPartTable(partTable);
system("pause");
}
return 0;
}