上期的笔记，浏览快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);
#endifProPCB.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;
}二、模拟银行家算法
介绍
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);
#endifchainlist.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
#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;
}四、模拟基本分页存储
介绍
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为空，说明链表循环结束，也没有到第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
#ifndef _List_h_
#define _List_h_
#include "Data.h"
//******* 链表 *******//
Status InitLinkList(LinkList *L);
void PCBAssign(PCBType *e1, PCBType e2);
Status GetElemt_L(LinkList L,int i,PCBType *e);
Status ListInsert_L(LinkList L,PCBType e);
Status ListDelete_L(LinkList L,int i,PCBType *e);
//****** 动态顺序表 ******//
void PartiAssign(PartiType *e1, PartiType e2);
Status InitList_Sq(SqList *L);
Status ListInsert_Sq(SqList *L,int i,PartiType e);
Status ListDelete_Sq(SqList *L,int i,PartiType *e);
#endifMemoryManage.h
#ifndef _MemoryManage_h_
#define _MemoryManage_h_
#include "List.h"
//***** PCB链表操作 *****//
Status InsertProcess(LinkList Q,PCBType e);
Status DeleteProsess(LinkList Q,int i,PCBType *e);
//***** 分区表操作 *****//
Status InsertTable(SqList *L, int i, PartiType e);
Status DeleteTable(SqList *L, int i, PartiType *e);
int SelectPart(PCB* pPCB, SqList *pPartTable, AllocatStrategy AS);
int MallocMemory(PCB *pe, SqList *pPartTable,int i);
void SearchSpace(PCBList PCBdata, SqList *partTable, AllocatStrategy AS);
void FreeMemory(int pos, SqList *pPartTable);
void InitAllocation(PCBList PCBdata, PartTable *partTable, AllocatStrategy AS);
void PrintProQueue(LinkList L);
void PrintPartTable(PartTable L);
#endif实现
list.c
#include "List.h"
Status InitLinkList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(LNode));
strcpy((*L)->data.Name, "");
(*L)->Next = NULL;
return OK;
}
void PCBAssign(PCBType *e1, PCBType e2)
{
strcpy(e1->Name,e2.Name);
e1->DistbutSt = e2.DistbutSt;
e1->MemorySize = e2.MemorySize;
e1->StartAddress = e2.StartAddress;
}
Status GetElemt_L(LinkList L,int i,PCBType *e)
{
LinkList p = L->Next; //指向第j个结点
int j = 1; //从第一个开始往后找
while ( p && j < i ) //p不为空且j < i
{
p = p->Next;
++j;
} //p为空，说明链表循环结束，也没有到第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;
}
#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;
}