模拟固定分区分配

痛定思痛。 2023-05-29 05:11 16阅读 0赞

# 介绍 #

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为空，说明链表循环结束，也没有到第i个结点   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中第i个位置之前插入新的元素e
    Status ListInsert_Sq(SqList *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((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;
    }