超硬核！学霸把操作系统经典算法给敲完了！要知行合一

清疚 2022-11-12 13:52 163阅读 0赞

> 上期的笔记，浏览快1万了，既然关注的人很多，那就发出来承诺过的算法全模拟，希望帮到你们。

[上期的操作系统学霸笔记，考试复习面试全靠它][Link 1]

# 一、模拟进程调度 #

## 功能 ##

data.h

#ifndef _Data_h_
    #define _Data_h_
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define ElemType PCB
    #define Status int
    #define OK		1
    #define	ERROR	0
    #define TimeSlice	1
    #define Infinity 10 //INT_MAX
    
    
    #define NAME_MAXSIZE 20
    typedef enum 
    {
        Ready,Running,Block
    }ProState;
    
    typedef enum 
    {
        FCFS, SPF		//先来先服务，短进程优先
    }PriorityRule;
    
    typedef struct 
    {
        char Name[NAME_MAXSIZE];	//进程名
        int Priority;				//优先数
        int ArrivalTime;			//到达时间		以时间片为单位
        int NeedRunningTime;		//运行时间		以时间片为单位
        int StartTime;				//开始执行时间
        int FinishTime;				//完成时间
        int TimeUsedCPU;			//已用CPU时间		以时间片为单位
        ProState ProcessState;		//进程状态
    }PCB;
    
    typedef struct Node
    {
        ElemType data;
        struct Node * Next;		
    }LNode,*LinkList;
    
    
    
    #endif

ChainList.h

#ifndef _ChainList_h_
    #define _ChainList_h_
    
    #include "Data.h"
    
    //功能：链表初始化
    Status Init(LinkList *L);
    
    //功能：赋值运算，将e2赋值给e1
    void Assignment(ElemType *e1, ElemType e2);
    
    //功能：获取第i个结点元素
    Status GetElemt_L(LinkList L,int i,ElemType *e);
    
    //功能：链表根据优先级插入元素
    Status ListInsert_L(LinkList L,ElemType e);
    
    //功能：链表删除头结点
    Status ListDelete_L(LinkList L,ElemType *e);
    
    
    #endif

ProPCB.h

#ifndef _ProPCB_h_
    #define _ProPCB_h_
    
    #include "ChainList.h"
    
    //功能：将e插入链表Q
    Status GetProcess(LinkList Q,ElemType e);		//上就绪队列
    
    //功能：根据不同的优先级规则，返回优先数
    int GetPriority(ElemType *e, PriorityRule PR);  //根据不同的规则PR 设置优先数
    
    //功能：将链表Q的头结点数据放到e指向的内存，并删除
    Status OutProsess(LinkList Q,ElemType *e);	    //下就绪队列
    
    //功能：CPU运行pcb指向的进程，并输出所有进行进程状态
    Status CPURunPro(LinkList Q, PCB *pcb);	        //CPU运行PCB
    
    //功能：打印所有PCB信息
    void PrintProQueue(LinkList Q, PCB *pcb);		//打印运行后PCB信息
    
    //功能：当一个进程结束，打印进程信息
    void PrintProResult(PCB *pcb);
    
    #endif

## 实现 ##

#include "ChainList.h"
    
    extern int CPUUsedTime;
    
    //功能：链表初始化
    Status Init(LinkList *L)
    {
        *L = (LinkList)malloc(sizeof(LNode));
        (*L)->data.NeedRunningTime = -1;
        (*L)->Next = NULL;
        return OK;
    }
    
    //功能：赋值运算，将e2赋值给e1
    void Assignment(ElemType *e1, ElemType e2)
    {
        e1->ArrivalTime = e2.ArrivalTime;
        strcpy(e1->Name,e2.Name);
        e1->Priority = e2.Priority;
        e1->ProcessState = e2.ProcessState;
        e1->FinishTime = e2.FinishTime;
        e1->StartTime = e2.StartTime;
        e1->NeedRunningTime = e2.NeedRunningTime;
        e1->TimeUsedCPU = e2.TimeUsedCPU;
    }
    
    
    
    //链表中按照优先级：从大到小排序插入
    Status ListInsert_L(LinkList L,ElemType e)	//这样修改应该不对 p = *L出错
    {
        LinkList p = L->Next, pre = L, s;
        while (p && e.Priority <= p->data.Priority)	
        {
            pre = p;
            p = p->Next;
        }
        s = (LinkList)malloc(sizeof(LNode));
        Assignment(&s->data, e);
        s->Next = pre->Next;
        pre->Next = s;
        return OK;
    }
    //链表中头部删除
    Status ListDelete_L(LinkList L,ElemType *e)
    {
        LinkList p = L, q;
        q = p->Next;
        if(!q)
            return ERROR;
        p->Next = q->Next;
        Assignment(e, q->data);
        free(q);
        return OK;
    }

#include "ProPCB.h"
    
    extern int CPUUsedTime;
    
    //功能：将e插入链表Q
    Status GetProcess(LinkList Q,ElemType e)
    {
        return ListInsert_L(Q, e);
    }
    
    //功能：根据不同的优先级规则，返回优先数
    int GetPriority(ElemType *e, PriorityRule PR)
    {
        if(PR == FCFS)
            return Infinity - e->ArrivalTime;
        else if(PR == SPF)
            return Infinity - e->NeedRunningTime;
        else
            printf("GetPriority Function ERROR!\n");
        return ERROR;
    }
    
    //功能：将链表Q的头结点数据放到e指向的内存，并删除
    Status OutProsess(LinkList Q,ElemType *e)
    {
        return ListDelete_L(Q ,e);
    }
    
    //上一次CPU运行时间增加1个时间片
    Status CPURunPro(LinkList Q,PCB *pcb)
    {
        if(pcb->StartTime == -1)
            pcb->StartTime = CPUUsedTime;
        pcb->ProcessState = Running;
        //PrintProQueue(Q, pcb);
        pcb->TimeUsedCPU += TimeSlice;
    
        return OK;
    }
    
    //功能：打印所有PCB信息
    void PrintProQueue(LinkList Q, PCB *pcb)
    {
        LinkList p = Q->Next;
       
        printf("进程名  优先数  到达时间  运行时间  已用CPU时间  完成时间  进程状态\n");
        if(pcb)
            printf(" %4s     %2d      %4d      %4d     %3d(+1)       %3d        %4s  \n",
            pcb->Name,pcb->Priority,pcb->ArrivalTime,pcb->NeedRunningTime,
            pcb->TimeUsedCPU, pcb->FinishTime,pcb->ProcessState == Ready ? "就绪" : "运行");
        while (p)
        {
            printf(" %4s     %2d      %4d      %4d     %3d           %3d        %4s  \n",
                p->data.Name,p->data.Priority,p->data.ArrivalTime,p->data.NeedRunningTime,
                p->data.TimeUsedCPU,p->data.FinishTime, p->data.ProcessState == Ready ? "就绪" : "运行");
            p = p->Next;
        }
        printf("-------------------------------------------------------------------------------\n");
    }
    
    //功能：当一个进程结束，打印进程信息
    void PrintProResult(PCB *pcb)
    {
        printf("进程名  到达时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转时间 进程状态\n");
        if(pcb)
            printf(" %2s     %3d      %4d        %4d      %3d     %4d       %5.2lf       %4s  \n",
            pcb->Name,pcb->ArrivalTime,pcb->NeedRunningTime,pcb->StartTime,pcb->FinishTime,
            pcb->FinishTime-pcb->ArrivalTime,((pcb->FinishTime - pcb->ArrivalTime)*1.0)/pcb->NeedRunningTime,"完成");
    
        printf("-------------------------------------------------------------------------------\n");
    }

main：

#include "ProPCB.h"
    
    /****************************
    *  实验01: 非抢占式静态优先权	*
    *  ① 优先权始终保持不变		*
    *  ② 一旦进入CPU便运行到结束	*
    *  ③ FCFS只考虑到达时间进CPU	*
    *  ④ SPF认为到达时间相同		*
    ****************************/
    
    int CPUUsedTime = 0;
    
    void InputData(LinkList * pPCBdata, PriorityRule PR)
    {
        ElemType e = {
       {0},-1,-1,-1,-1,-1,0,Ready};
        e.ArrivalTime = 0;
        e.ProcessState = Ready;
        e.TimeUsedCPU = 0;
        strcpy(e.Name,"A");
        e.NeedRunningTime = 1;
        e.Priority = GetPriority(&e, PR);
        if(PR == SPF)   e.ArrivalTime = 0;
        GetProcess(*pPCBdata,e);
    
        e.ArrivalTime = 1;
        e.ProcessState = Ready;
        e.TimeUsedCPU = 0;
        strcpy(e.Name,"B");
        e.NeedRunningTime = 100;
        e.Priority = GetPriority(&e, PR);
        if(PR == SPF)   e.ArrivalTime = 0;
        GetProcess(*pPCBdata,e);
    
        e.ArrivalTime = 2;
        e.ProcessState = Ready;
        e.TimeUsedCPU = 0;
        strcpy(e.Name,"C");
        e.NeedRunningTime = 1;
        e.Priority = GetPriority(&e, PR);
        if(PR == SPF)   e.ArrivalTime = 0;
        GetProcess(*pPCBdata,e);
    
        e.ArrivalTime = 3;
        e.ProcessState = Ready;
        e.TimeUsedCPU = 0;
        strcpy(e.Name,"D");
        e.NeedRunningTime = 100;
        e.Priority = GetPriority(&e, PR);
        if(PR == SPF)   e.ArrivalTime = 0;
        GetProcess(*pPCBdata,e);
    
    }
    
    //void InputData1(LinkList * pPCBdata, PriorityRule PR)
    //{
    //    ElemType e = {
       {0},-1,-1,-1,-1,-1,0,Ready};
    //    e.ArrivalTime = 0;
    //    e.ProcessState = Ready;
    //    e.TimeUsedCPU = 0;
    //    strcpy(e.Name,"A");
    //    e.NeedRunningTime = 4;
    //    e.Priority = GetPriority(&e, PR);
    //    if(PR == SPF)   e.ArrivalTime = 0;
    //    GetProcess(*pPCBdata,e);
    //
    //    e.ArrivalTime = 1;
    //    e.ProcessState = Ready;
    //    e.TimeUsedCPU = 0;
    //    strcpy(e.Name,"B");
    //    e.NeedRunningTime = 3;
    //    e.Priority = GetPriority(&e, PR);
    //    if(PR == SPF)   e.ArrivalTime = 0;
    //    GetProcess(*pPCBdata,e);
    //
    //    e.ArrivalTime = 2;
    //    e.ProcessState = Ready;
    //    e.TimeUsedCPU = 0;
    //    strcpy(e.Name,"C");
    //    e.NeedRunningTime = 5;
    //    e.Priority = GetPriority(&e, PR);
    //    if(PR == SPF)   e.ArrivalTime = 0;
    //    GetProcess(*pPCBdata,e);
    //
    //    e.ArrivalTime = 3;
    //    e.ProcessState = Ready;
    //    e.TimeUsedCPU = 0;
    //    strcpy(e.Name,"D");
    //    e.NeedRunningTime = 2;
    //    e.Priority = GetPriority(&e, PR);
    //    if(PR == SPF)   e.ArrivalTime = 0;
    //    GetProcess(*pPCBdata,e);
    //
    //    e.ArrivalTime = 4;
    //    e.ProcessState = Ready;
    //    e.TimeUsedCPU = 0;
    //    strcpy(e.Name,"E");
    //    e.NeedRunningTime = 4;
    //    e.Priority = GetPriority(&e, PR);
    //    if(PR == SPF)   e.ArrivalTime = 0;
    //    GetProcess(*pPCBdata,e);
    //}
    
    
    int main(void)
    {
        LinkList PCBQueue;	//InitPCBdata里面存放PCB初始数据
        ElemType e = {
       {0},-1,-1,-1,-1,-1,0,Ready};
        ElemType *pcb = NULL;
        PriorityRule PR;
        PR = FCFS;	   //   SPF    or   FCFS
        //***********    初始化就绪队列    *************//
        Init(&PCBQueue);
        InputData(&PCBQueue, PR);
        printf("初始数据如下：\n");
        PrintProQueue(PCBQueue, pcb);
    
        //***********    进程根据优先级上CPU    *************//
        printf("\n进程运行信息如下：\n");
        while (OutProsess(PCBQueue, &e))
        {
            //一次性运行完毕
            while(e.TimeUsedCPU < e.NeedRunningTime)	//上完CPU的进程是否完毕
            {
                CPURunPro(PCBQueue, &e);		        //上CPU
                ++CPUUsedTime;					        //CPU时间增加
            }
        //***********    当进程执行完毕时打印输出    *************//
            e.FinishTime = CPUUsedTime;
            PrintProResult(&e);
        }
    
    	getchar();
        return 0;
    }

# 二、模拟银行家算法 #

## 介绍 ##

![20191104145857576.png][]

data.h

#ifndef _Data_h_
    #define _Data_h_
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define ElemType PCB
    #define Status int
    #define true				1
    #define false				0
    #define OK					1
    #define	ERROR				0
    #define RESOURCE_NUM		3
    #define	MAX_RESOURCE_A_NUM	10
    #define	MAX_RESOURCE_B_NUM	5
    #define	MAX_RESOURCE_C_NUM	7
    #define NAME_MAXSIZE		20
    #define PCB_Num 5
    typedef struct{
    	int MaxNum[RESOURCE_NUM];			//需要每项资源个数
    	int AllocationNum[RESOURCE_NUM];	//已占用每项资源个数
    	int NeedNum[RESOURCE_NUM];			//还需要的每项资源个数
    }ResourceList;
    
    typedef struct 
    {
    	char Name[NAME_MAXSIZE];			//进程名
    	ResourceList resList;				//资源清单
    }PCB;
    
    typedef struct Node
    {
    	ElemType data;
    	struct Node * Next;		
    }LNode,*LinkList;
    
    #endif

chainlist.h

#ifndef _ChainList_h_
    #define _ChainList_h_
    
    #include "Data.h"
    
    Status Init(LinkList *L);
    void Assignment(ElemType *e1, ElemType e2);
    Status ListInsert_L(LinkList L,ElemType e);
    
    #endif

## 实现 ##

ProPCB.h

#ifndef _ProPCB_h_
    #define _ProPCB_h_
    
    #include "ChainList.h"
    #include <string.h>
    //上队列
    Status GetProcess(LinkList Q,ElemType e);		
    //银行家算法
    Status BankerAlgorithm(int *Allocation, int *Request,int i, int *Need, int *Available);
    //安全性检测算法
    Status SecurityCheck(int *Allocation,int *Need, int *Available);
    //分配资源
    Status AllocateResource(LinkList PCBdata , int pos , int *Request);
    //获取资源矩阵
    void GetMatrixData(LinkList PCBdata,int *Max,int *Allocation,int *Need,int *Available);
    //打印进程资源信息
    void PrintProQueue(LinkList L, int *A);
    //得到指定PCB名的位置
    void GetPos(LinkList L, char *name, int len, int *pos);
    //对当前的请求进行预分配
    void PreGrant(int* Allocation, int *Request,int pos,int *Need, int *Available);
    //正式分配算法
    void GrantSource(LinkList L, int *Request, int pos, int *Available);
    
    #endif

chainlist.c

#include "ChainList.h"
    extern int CPUUsedTime;
    Status Init(LinkList *L)
    {
    	*L = (LinkList)malloc(sizeof(LNode));
    	strcpy((*L)->data.Name, "");
    	(*L)->Next = NULL;
    	return OK;
    }
    
    void Assignment(ElemType *e1, ElemType e2)
    {
    	int i = 0;
    	strcpy(e1->Name,e2.Name);
    	for(i = 0; i < RESOURCE_NUM; ++i)
    	{
    		e1->resList.AllocationNum[i] = e2.resList.AllocationNum[i];
    		e1->resList.MaxNum[i] = e2.resList.MaxNum[i];
    		e1->resList.NeedNum[i] = e2.resList.NeedNum[i];
    	}
    }
    
    Status ListInsert_L(LinkList L,ElemType e)	//这样修改应该不对 p = *L出错
    {
    	LinkList p = L, s;
    	while (p->Next)	
    		p = p->Next;
    	s = (LinkList)malloc(sizeof(LNode));
    	Assignment(&s->data, e);
    	s->Next = p->Next;
    	p->Next = s;
    	return OK;
    }

ProPCB.c

#include "ProPCB.h"
    
    Status GetProcess(LinkList Q,ElemType e)
    {
    	return ListInsert_L(Q, e);
    }
    
    Status AllocateResource(LinkList PCBdata , int pos , int *Request)
    {
    	int i = 1;
    	LNode *p = PCBdata->Next;
    	
    	while (p && i < pos)
    	{
    		p = p->Next;
    		++i;
    	}
    	if(!p || i > pos)
    		return ERROR;
    	for (i = 0; i < RESOURCE_NUM; ++i)
    	{
    		p->data.resList.AllocationNum[i] += Request[i];
    		p->data.resList.NeedNum[i] -= Request[i];
    	}
    	return OK;
    }
    void GetMatrixData(LinkList PCBdata,int *Max,int *Allocation,int *Need,int *Available)
    {
    	LNode *p;
    	int i, j, c = RESOURCE_NUM;
    	Available[0] = Available[1] = Available[2] = 0;
    	for(p = PCBdata->Next, i = 0; p; p = p->Next, ++i)
    	{
    		for(j = 0; j < RESOURCE_NUM; ++j)
    		{
    			Max[i * c + j] = p->data.resList.MaxNum[j];
    			Allocation[i * c + j] = p->data.resList.AllocationNum[j];
    			Need[i * c + j] = p->data.resList.NeedNum[j];
    		}
    		Available[0] += Allocation[i * c + 0];
    		Available[1] += Allocation[i * c + 1];
    		Available[2] += Allocation[i * c + 2];
    	}
    	Available[0] =  MAX_RESOURCE_A_NUM - Available[0];
    	Available[1] =  MAX_RESOURCE_B_NUM - Available[1];
    	Available[2] =  MAX_RESOURCE_C_NUM - Available[2];
    }
    
    
    void PrintProQueue(LinkList L,int *available)
    {
    	int i = 0;
    	L = L->Next;
    	printf(" -------------------------------------------------------------\n");
    	printf("|进程名 |     Max    |  Allocation |    Need    |  Available  |\n");
    	printf("|       |  A   B   C |  A   B   C  | A   B   C  |  A   B   C  |\n");
    	while(L)
    	{
    		printf("|  %s   |  %d   %d   %d |  %d   %d   %d  | %d   %d   %d  |  %d   %d   %d  |\n",
    			L->data.Name, L->data.resList.MaxNum[0], L->data.resList.MaxNum[1], L->data.resList.MaxNum[2],
    			L->data.resList.AllocationNum[0],L->data.resList.AllocationNum[1],L->data.resList.AllocationNum[2],
    			L->data.resList.NeedNum[0],L->data.resList.NeedNum[1],L->data.resList.NeedNum[2],
    			available[0], available[1], available[2]);
    		L = L->Next;
    	}
    	printf(" -------------------------------------------------------------\n");
    
    }
    
    //安全性检测算法
    Status SecurityCheck(int *Allocation,int *Need, int *Available)
    {
    	/ 以下补充  //
    	int work[RESOURCE_NUM];
    	int Finish[PCB_Num];
    	int k, i, j, t, f;
    	int flag;
    
    	//初始化工作向量和标记数组
    	memcpy(work, Available, sizeof work);
    	memset(Finish, 0, sizeof Finish);
    
    	//最多检测PCB_Num次
    	for(k = 0; k < PCB_Num; ++k){
    		flag = 0;
    		for(i = 0; i < PCB_Num; ++i){
    			//已经被访问
    			if(Finish[i]){
    				continue;
    			}
    
    			//检测是否所有资源都能被分配
    			for(j = 0; j < RESOURCE_NUM; ++j){
    				if(!(Need[i * 3 + j] <= work[j])){
    					break;
    				}
    			}
    
    			//可以满足，回收
    			if(j == RESOURCE_NUM){
    				for(t = 0; t < RESOURCE_NUM; ++t){
    					work[t] += Allocation[i * 3 + t];
    				}
    				Finish[i] = 1;
    				flag = 1;
    				break;
    			}
    		}
    
    		//为进行分配，跳出循环
    		if(!flag){
    			break;
    		}
    	}
    
    	for(f = 0; f < PCB_Num; ++f){
    		//只要有一个进程不满足，跳出循环
    		if(!Finish[f]){
    			return ERROR;
    		}
    	}
    
    	return OK;
    }
    
    //银行家算法
    Status BankerAlgorithm(int* Allocation, int *Request,int pos,int *Need, int *Available)
    {
    	/ 以下补充  //
    	int i;
    	//检查请求的是否大于需要的
    	for(i = 0; i < RESOURCE_NUM; ++i){
    		if(Request[i] > Need[pos*3 + i]){
    			return ERROR;
    		}
    	}
    
    	//检查请求的是否大于可分配的
    	for(i = 0; i < RESOURCE_NUM; ++i){
    		if(Request[i] > Available[i]){
    			return ERROR;
    		}
    	}
    
    	//进行预分配
    	PreGrant(Allocation, Request, pos, Need, Available);
    
    	//进行安全性检测
    	if(!SecurityCheck(Allocation, Need, Available)){
    		return ERROR;
    	}
    
    	return OK;
    }
    
    //根据PCB的名字得到该PCB在链表中的位置
    void GetPos(LinkList L, char *name, int len, int *pos)
    {
    	LinkList p = L->Next;
    	char PcbName[NAME_MAXSIZE];
    	memcpy(PcbName, name, (len + 1) * sizeof(char));
    	(*pos) = 0;
    
    	while(p){
    		if(strcmp(p->data.Name, PcbName)){
    			(*pos)++;
    			p = p->Next;
    		} else {
    			break;
    		}
    	}
    }
    
    //预分配算法
    void PreGrant(int* Allocation, int *Request,int pos,int *Need, int *Available){
    	int i;
    	//1. Need减去请求的
    	for(i = 0; i < RESOURCE_NUM; ++i){
    		Need[pos*3 + i] -= Request[i];
    	}
    
    	//2. Available减去请求的
    	for(i = 0; i < RESOURCE_NUM; ++i){
    		Available[i] -= Request[i];
    	}
    
    	//3. Allocation加上请求的
    	for(i = 0; i < RESOURCE_NUM; ++i){
    		Allocation[pos*3 + i] += Request[i];
    	}
    }
    
    /**
     * 1.首先对请求资源的进程进行分配资源
     * 2.如果给该进程分配资源之后，该进程所需的资源等于已经得到的资源，那么对其拥有的资源进行回收
     */
    
    //正式分配算法,pos从0开始标记
    void GrantSource(LinkList L, int *Request, int pos, int *Available){
    	LinkList p = L->Next;
    	int tag = 0;
    	int i;
    	int flag = 0;
    
    	if(tag < pos && NULL != p){
    		p = p->Next;
    		tag++;
    	}
    
    	if(p){
    		//已获得的加上请求的
    		for(i = 0; i < RESOURCE_NUM; ++i){
    			p->data.resList.AllocationNum[i] += Request[i];
    		}
    		
    		//还需要的减去请求的
    		for(i = 0; i < RESOURCE_NUM; ++i){
    			p->data.resList.NeedNum[i] -= Request[i];
    		}
    
    		//可利用的减去请求的
    		for(i = 0; i < RESOURCE_NUM; ++i){
    			Available[i] -= Request[i];
    		}
    
    		//如果进行分配之后该进程最大所需资源数目等于已获得的资源数目，则对资源进行回收
    		flag = 0;
    		for(i = 0; i < RESOURCE_NUM; ++i){
    			if(p->data.resList.AllocationNum[i] != p->data.resList.MaxNum[i]){
    				flag = 1;
    				break;
    			}
    		}
    
    		if(!flag){
    			for(i = 0; i < RESOURCE_NUM; ++i){
    				Available[i] += p->data.resList.AllocationNum[i];
    			}
    		}
    	}
    }

main

#include "ProPCB.h"
    
    void InputData(LinkList * pPCBdata)
    {
    	ElemType e = {
       {0},{
       {0},{0},{0}}};
    	strcpy(e.Name,"P0");
    	e.resList.MaxNum[0] = 7;	e.resList.MaxNum[1] = 5;	e.resList.MaxNum[2] = 3;
    	e.resList.AllocationNum[0] = 0;
    	e.resList.AllocationNum[1] = 1;
    	e.resList.AllocationNum[2] = 0;
    	e.resList.NeedNum[0] = 7;	e.resList.NeedNum[1] = 4;	e.resList.NeedNum[2] = 3;	
    	GetProcess(*pPCBdata,e);
    
    	strcpy(e.Name,"P1");
    	e.resList.MaxNum[0] = 3;	e.resList.MaxNum[1] = 2;	e.resList.MaxNum[2] = 2;
    	e.resList.AllocationNum[0] = 2;
    	e.resList.AllocationNum[1] = 0;
    	e.resList.AllocationNum[2] = 0;
    	e.resList.NeedNum[0] = 1;	e.resList.NeedNum[1] = 2;	e.resList.NeedNum[2] = 2;	
    	GetProcess(*pPCBdata,e);
    
    	strcpy(e.Name,"P2");
    	e.resList.MaxNum[0] = 9;	e.resList.MaxNum[1] = 0;	e.resList.MaxNum[2] = 2;
    	e.resList.AllocationNum[0] = 3;
    	e.resList.AllocationNum[1] = 0;
    	e.resList.AllocationNum[2] = 2;
    	e.resList.NeedNum[0] = 6;	e.resList.NeedNum[1] = 0;	e.resList.NeedNum[2] = 0;	
    	GetProcess(*pPCBdata,e);
    
    	strcpy(e.Name,"P3");
    	e.resList.MaxNum[0] = 2;	e.resList.MaxNum[1] = 2;	e.resList.MaxNum[2] = 2;
    	e.resList.AllocationNum[0] = 2;
    	e.resList.AllocationNum[1] = 1;
    	e.resList.AllocationNum[2] = 1;
    	e.resList.NeedNum[0] = 0;	e.resList.NeedNum[1] = 1;	e.resList.NeedNum[2] = 1;	
    	GetProcess(*pPCBdata,e);
    
    	strcpy(e.Name,"P4");
    	e.resList.MaxNum[0] = 4;	e.resList.MaxNum[1] = 3;	e.resList.MaxNum[2] = 3;
    	e.resList.AllocationNum[0] = 0;
    	e.resList.AllocationNum[1] = 0;
    	e.resList.AllocationNum[2] = 2;
    	e.resList.NeedNum[0] = 4;	e.resList.NeedNum[1] = 3;	e.resList.NeedNum[2] = 1;	
    	GetProcess(*pPCBdata,e);
    }
    int main(void)
    {
    	LinkList PCBdata;	//PCBdata里面存放原始数据
    	ElemType e = {
       {0},{
       {0},{0},{0}}};
    
    	char PcbName[NAME_MAXSIZE], chioce;
    	int Max[PCB_Num][RESOURCE_NUM] = {0}, Allocation[PCB_Num][RESOURCE_NUM] = {0};
    	int Need[PCB_Num][RESOURCE_NUM] = {0}, Available[RESOURCE_NUM] = {0};
    	int Request[RESOURCE_NUM] = {0}, pos = 0;
    	LNode *p = NULL;
    	int i;
    
    	/ 以下补充  //
    	
    	//初始化就绪队列
    	Init(&PCBdata);
    
    	//数据输入
    	InputData(&PCBdata);
    
    	while(1){
    		//获取所有PCB中的资源信息
    		GetMatrixData(PCBdata, *Max, *Allocation, *Need, Available);
    
    		//打印当前系统的状态
    		PrintProQueue(PCBdata, Available);
    		
    		//接受请求
    		printf("请输入申请资源的进程名，资源A,资源B,资源C申请量（空格隔开）：");
    		scanf("%s", PcbName);
    		for(i = 0; i < RESOURCE_NUM; ++i){
    			scanf("%d", &Request[i]);
    		}
    
    		//获取相应的PCB在链表中的位置
    		GetPos(PCBdata, PcbName, strlen(PcbName), &pos);
    
    		//跑银行家算法，根据返回值的状态判断是否安全，
    		//如果安全，进行正式分配，否则仅仅打印不安全信息
    		if(BankerAlgorithm(*Allocation, Request, pos, *Need, Available)){
    			//正式分配资源
    			GrantSource(PCBdata, Request, pos, Available);
    
    			//分配完成后，打印资源的信息
    			GetMatrixData(PCBdata, *Max, *Allocation, *Need, Available);
    			PrintProQueue(PCBdata, Available);
    			printf("请安任意键继续. . . ");
    			getchar();
    			getchar();
    		} else {
    			printf("不安全，不可分配！\n");
    		}
    	}
    
    	return 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

### 实现 ###

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;
    }

# 四、模拟基本分页存储 #

### 介绍 ###

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);
    
    #endif

memorymanage.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为空，说明链表循环结束，也没有到第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_f(PartiType *e1, PartiType e2)
    {
    	e1->PartStartAddr = e2.PartStartAddr;
    	strcpy(e1->Name, e2.Name);
    }
    
    Status InitList_f(SqList_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;
    }

# 五、模拟动态分区分配 #

### 介绍 ###

list.h

MemoryManage.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 "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;
    }

#  #

[Link 1]: https://fantianzuo.blog.csdn.net/article/details/115091251
[20191104145857576.png]: /images/20221022/ef1b9101df1a49baa96f112f2c2ce0c6.png