上期的笔记，浏览快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;
-
}
二、模拟银行家算法
介绍
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
-
#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);
-
-
#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
-
#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
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 "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;
-
}
转载：https://blog.csdn.net/hebtu666/article/details/115171870
查看评论