介绍

data.h

#ifndef _Data_h_ #define _Data_h_  #include <stdio.h> #include <stdlib.h> #include <string.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 TotalMemory   512 //KB   typedef enum  {  Unallocated, Allocated }DistributState, PartitionSt;  typedef enum {  FirstPriority, BestAdapt }AllocatStrategy;   typedef struct  {  char Name[NAME_MAXSIZE]; //进程名  int MemorySize;    //内存大小  int StartAddress;   //内存起始地址  DistributState DistbutSt; //分配状态 }PCB;  typedef struct Node {  PCBType data;  struct Node * Next;   }LNode, *LinkList, *PCBList;   //  typedef struct {        //分区号用数组下标代替  int PartitionSize;  int PartStartAddr;  char Name[NAME_MAXSIZE];//如果是空的，则分区空闲 }PartitionInfo;  typedef struct {  PartiType *elem;  int listsize;  //表容量  int length;   //元素数 }SqList, PartTable;  //分区表  #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(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);  #endif

#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); int MallocMemory(PCB *pe, SqList *pPartTable, int pos); void SearchSpace(PCBList PCBdata, SqList partTable); void FreeMemory(int pos, SqList *pPartTable); void InitAllocation(PCBList PCBdata, PartTable partTable); 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中删除第i个元素，并用e返回其值
Status ListDelete_Sq(SqList *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(e, *p);							 //将被删除元素的值赋给e （待定）
	q = L->elem + L->length-1;					 //移动到表尾元素的位置
	for (++p;p<=q;++p)
		PartiAssign((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(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)
{
	int i,Start;
	if(pPCB->MemorySize <= 16)
		Start = 0;
	else if(pPCB->MemorySize <= 32)
		Start = 1;
	else if(pPCB->MemorySize <= 64)
		Start = 2;
	else if(pPCB->MemorySize <= 128)
		Start = 3;
	else if(pPCB->MemorySize <= 256)
		Start = 4;
	else
	{
		printf("内存过大，无法装入!\n");
		return ERROR;
	}

	for (i = Start; i < pPartTable->length; ++i)
		if(!strcmp(pPartTable->elem[i].Name, ""))
			return i + 1;
	return ERROR;
}

//i传递的是下标
int MallocMemory(PCB *pe, SqList *pPartTable,int i)
{
	///   以下需要补充    /
	pe->DistbutSt = Allocated;
	pe->StartAddress = pPartTable->elem[i].PartStartAddr;
	strcpy(pPartTable->elem[i].Name, pe->Name);

	return OK;
}

/**
 * PCBdata：表示PCB链
 * partTable：分区表
 * 将每一个PCB取出，查找是否有合适的分区可以分配给他，如果有分配，如果没有不分配
 */ 
void InitAllocation(PCBList PCBdata, PartTable partTable)
{
	///   以下需要补充    /
	PCBList L = PCBdata->Next;
	int pos;

	while(L){
		pos = SelectPart(&L->data, &partTable);
		if(pos == 0) {
			printf("无法为%s进程分配空间！！！\n", L->data.Name);
		} else {
			L->data.DistbutSt = Allocated;
			L->data.StartAddress = partTable.elem[pos-1].PartStartAddr;
			strcpy(partTable.elem[pos-1].Name, L->data.Name);
		}
		L = L->Next;
	}
	//SearchSpace(PCBdata, partTable);
}

void FreeMemory(int pos, SqList *pPartTable)
{
	///   以下需要补充    /
	strcpy(pPartTable->elem[pos].Name, "");
}


void SearchSpace(PCBList PCBdata, SqList partTable)
{
	int pos;
	LNode *p;
	p = PCBdata->Next;
	while (p)
	{
		if(p->data.DistbutSt == Unallocated)
		{
			pos = SelectPart(&(p->data), &partTable);//从1开始
			if(pos)
			{
				MallocMemory(&(p->data), &partTable, pos - 1);
				break;
			}
		}
		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 固定分区分配
* 分配策略：
* ①离队首最近，能够装入该分区的进程；
* ②搜索能够装入该分区最大的进程。
*/

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, Unallocated };
	se.PartStartAddr = 16;
	se.PartitionSize = 16;
	InsertTable(pPartdata, 1, se);

	se.PartStartAddr = 32;
	se.PartitionSize = 32;
	InsertTable(pPartdata, 2, se);

	se.PartStartAddr = 64;
	se.PartitionSize = 64;
	InsertTable(pPartdata, 3, se);

	se.PartStartAddr = 128;
	se.PartitionSize = 128;
	InsertTable(pPartdata, 4, se);

	se.PartStartAddr = 256;
	se.PartitionSize = 256;
	InsertTable(pPartdata, 5, 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 tmp;
	PCBType *pcb = NULL;
	LNode *p; 
	PCBList pl = NULL;
	int tpos = 0;
	int startAddress;

	int i, size, pos, j;

	InitList_Sq(&partTable);
	SetFixedZone(&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("%d",&choice);
		
		//printf("haha");
		switch (choice)
		{
		///   以下需要补充    /
		case 1:
			printf("要结束的进程名：");
			scanf("%s", PcbName);
			//找到指定进程的位置,
			pl = PCBdata->Next;
			startAddress = -1;
			tpos = 0;

			while(pl){
				tpos++;
				if(!strcmp(pl->data.Name, PcbName) && pl->data.DistbutSt == Allocated){
					startAddress = pl->data.StartAddress;
					break;
				}
				pl = pl->Next;
			}

			if(startAddress == -1){
				printf("进程不存在！！！\n");
				break;
			}

			//删除进程
			DeleteProsess(PCBdata, tpos, &tmp);

			//根据起始地址找到要回收的分区
			for(j = 0; j < partTable.length; ++j){
				if(partTable.elem[j].PartStartAddr == startAddress){
					tpos = j;
					break;
				}
			}

			//回收内存
			FreeMemory(tpos, &partTable);

			//重新检查是否可以为其他进程分配
			SearchSpace(PCBdata, partTable);
			break;
		case 2:
			printf("请输入添加的进程名和所占分区的大小：");
			scanf("%s %d", PcbName, &size);

			strcpy(PCBe.Name, PcbName);
			PCBe.MemorySize = size;
			PCBe.DistbutSt = Unallocated;
			PCBe.StartAddress = 0;
			InsertProcess(PCBdata, PCBe);
			SearchSpace(PCBdata, partTable);
			break;
		case 3:
			exit(0);
			break;
		}
		PrintProQueue(PCBdata);
		PrintPartTable(partTable);
		system("pause");
	}

	return 0;
}