操作系统——pcb模拟.txt

该程序使用tc2.0编译

操作系统--PCB模拟(动态优先调用与动态内存分配) 
#include <time.h>
#include <dos.h>
#include <math.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <graphics.h>


#define ESC  0x1b
#define ENTER 0x0d
#define BACKSPACE 8
#define TRUE 1
#define FALSE 0
typedef unsigned UINT;
/*每隔TIME秒就变换一次优先级*/
#define TIME 5
/*系统的总内存容量(BYTE)，暂定为32KB*/
#define TOTALMEM (UINT)((UINT)1024*(UINT)32)
/*系统本身占用内存大小(BYTE)，暂定为2KB*/
#define SYSMEM  (UINT)(2048)
/*系统后备空闲进程占用内存大小(BYTE)，暂定为1KB*/
#define IDLEMEM  (UINT)(1024)

 

/*多道系统数据结构*/
/****************************************************************/
enum _ProcStatus/*进程状态枚举*/
{
 READY =0,/*就绪*/
 RUN,/*执行中*/
 SUSPEND,/*挂起*/
};
typedef enum _ProcStatus ProcStatus;
/****************************************************************/
enum _MemStatus/*内存分区块状态枚举*/
{
 IDLE =0,/*空闲中*/
 INUSE,/*使用中*/
};
typedef enum _MemStatus MemStatus;
/****************************************************************/
struct _MemBlock/*内存分区块结构*/
{
 UINT Offset;/*起始地址*/
 UINT Size;/*内存块大小(以BYTE为单位)*/
 MemStatus Sts;/*内存分区块使用状态*/
 struct _MemBlock *Next;/*内存块列表中下一个内存块*/
};
typedef struct _MemBlock MemBlock;
/****************************************************************/
struct _Pcb/*进程结构*/
{
 int  PID;/*进程ID，ID为负数的进程为系统后备队列的作业*/
 int  Time;/*进程运行需要的时间*/
 int  Prior;/*进程的优先级，越大越优先*/
 ProcStatus  Sts;/*状态*/
 MemBlock  *Mem;/*所使用的内存块*/
 struct _Pcb *Next;/*指向本进程队列中下个进程的PCB*/
};
typedef struct _Pcb PCB;
/****************************************************************/
struct _Batch/*多道处理中的道结构*/
{
 PCB  *pcb;/*该道当前正在处理的进程*/
 struct _Batch *Next;/*下一道*/
};
typedef struct _Batch Batch;
/****************************************************************/
/*系统相关全局变量*/
PCB *ProcQueue = NULL;/*进程链表，按优先级从大到小排列*/
MemBlock *MemTable = NULL;/*内存分区表，按起始地址从小到大排序*/
MemBlock *SysMem = NULL;/*系统本身占用的内存分区*/
Batch *BatchQueue = NULL;/*系统多道链表*/
/****************************************************************/

 


/*动态优先权抢占式调度算法及相关函数声明*/
/****************************************************************/
int InitBatchs(int n);/*初始化多道系统，n为道数*/
int InsertProc(int prior, int time, UINT size);/*向进程链表中按优先级大小插入一个新进程*/
int InsertIDLE();/*向进程队列中加入后备进程，当系统空闲时将被调入*/
int SortProcQueue();/*将进程链表按优先级从大到小排列*/
int AddBatch();/*增加系统道数*/
int DeleteBatch();/*减少系统道数*/
int UnSuspendProc(int id);/*解除ID为id的进程的挂起状态*/
int UpdateBatchs();/*多道系统根据进程链表进行更新，并将执行完毕的进程删除*/
int PassSeconds(int n);/*系统经过n秒后计算数据并进行优先级调度*/
/****************************************************************/
/*可变大小内存分区算法及相关函数声明*/
/****************************************************************/
int InitMem();/*初始化内存分区表，sysmemsize是系统占据的内存大小*/
MemBlock* ApplyMem(UINT size);/*进程向系统申请内存*/
int ReleaseMem(MemBlock* mem);/*进程pcb结束要求释放内存*/
int MergeMem();/*整理内存表，相邻的空闲分区将归并为一份*/
/****************************************************************/

 


/*各函数的定义*/
/****************************************************************/
int InitBatchs(int n)
{
 int i;
 for (i=0; i<n; ++i)
 {
  if (!AddBatch()) return FALSE;
 }
 return (UpdateBatchs());
}

int InsertProc(int prior, int time, UINT size)
{
 static int sysid = 0;/*该系统已经加入过多少进程，此值将是新进程的ID*/
 PCB *last,*now,*pcb;
 MemBlock *mem;
 if (prior<=0 || time<=0 || size<=0) return FALSE;
 mem = ApplyMem(size);
 if (mem == NULL) return FALSE;
 pcb = (PCB*)malloc(sizeof(PCB));
 if (pcb == NULL) return FALSE;
 pcb->Prior = prior;
 pcb->Time = time;
 pcb->PID = (++sysid);
 pcb->Sts = READY;
 pcb->Mem = mem;
 if (ProcQueue == NULL)/*如果进程队列为空*/
 {
  ProcQueue = pcb;
  pcb->Next = NULL;
  return TRUE;
 }
 last = ProcQueue;
 now = last->Next;

 if (pcb->Prior > last->Prior)/*pcb将排在队头*/
 {
  pcb->Next = ProcQueue;
  ProcQueue = pcb;
  return TRUE;
 }
 while ((now != NULL) && (pcb->Prior < now->Prior))/*寻找插入位置*/
 {
  last = now;
  now = last->Next;
 }
 last->Next = pcb;
 pcb->Next = now;
 return TRUE;
}

int InsertIDLE()
{
 PCB *now = ProcQueue;
 MemBlock *mem = ApplyMem(IDLEMEM);
 PCB *idle;
 if (mem==NULL)
  return FALSE;
 idle = (PCB*)malloc(sizeof(PCB));
 if (idle==NULL)
  return FALSE;

 idle->PID = -1;
 idle->Prior = -1;
 idle->Sts = SUSPEND;
 idle->Time = -1;
 idle->Next = NULL;
 idle->Mem = mem;
 if (ProcQueue == NULL)
 {
  ProcQueue = idle;
  return TRUE;
 }
 while(now->Next != NULL)
 {
  now = now->Next;
 }
 now->Next = idle;
 return TRUE;
}

int SortProcQueue()
{ /*冒泡排序*/
 PCB *last, *now;
 int b = FALSE;/*上次遍历是否无交换产生*/
 if (ProcQueue==NULL || ProcQueue->Next==NULL)/*如果链表中无进程或只有一个进程*/
  return FALSE;
 while (!b)
 {
  b = TRUE;
  last=ProcQueue;
  now=last->Next;
  if (last->Prior < now->Prior)
  {
   ProcQueue = now;
   last->Next = now->Next;
   now->Next = last;
   b = FALSE;
   last = ProcQueue;
   now = last->Next;
  }
  while (now->Next!=NULL)
  {
   if ((now->Prior)<(now->Next->Prior))
   {
    last->Next = now->Next;
    now->Next = now->Next->Next;
    last->Next->Next = now;
    b = FALSE;
   }
   else
    last = last->Next;
   now = last->Next;
  }
 }
 return TRUE;
}

int AddBatch()
{
 Batch *bt = (Batch*)malloc(sizeof(Batch));
 if (bt==NULL) return FALSE;
 bt->Next = BatchQueue;
 BatchQueue = bt;
 bt->pcb = NULL;
 return (InsertIDLE());
}

int DeleteBatch()
{
 Batch *bt = BatchQueue;
 PCB *last, *now;
 if (BatchQueue==NULL || BatchQueue->Next==NULL)/*如果只剩最后一道则不删除*/
  return FALSE;
 if (ProcQueue==NULL || ProcQueue->Next==NULL)/*如果只有最后一个后备空闲进程*/
  return FALSE;/**/
 last = ProcQueue;
 now = last->Next;
 while (now->Next != NULL)/*查找到最后一个进程，该进程必定是后备空闲进程*/
 {
  last = now;
  now = last->Next;
 }
 if (now==NULL || now->PID>=0)/*未查找到后备进程*/
  return FALSE;/**/
 ReleaseMem(now->Mem);/*释放进程的内存*/
 free(now);
 last->Next = NULL;
 BatchQueue = BatchQueue->Next;
 free(bt);
 return TRUE;
}

int UnSuspendProc(int id)
{
 PCB *now = ProcQueue;
 if (id<=0) return FALSE;
 if (ProcQueue==NULL) return FALSE;
 while (now != NULL)
 {
  if (now->PID == id)
  {
   now->Sts = READY;
   return TRUE;
  }
  now = now->Next;
 }
 return FALSE;
}

int UpdateBatchs()
{
 Batch *bt = BatchQueue;
 PCB *last = ProcQueue, *now;
 while (bt != NULL)
 {
  bt->pcb = NULL;
  bt = bt->Next;
 }
 if (ProcQueue == NULL) return TRUE;
 while (last->Sts==RUN && last->PID>=0 && last->Time<=0)
 {
  ProcQueue = ProcQueue->Next;
  ReleaseMem(last->Mem);
  free(last);
  last = ProcQueue;
 }
 now = last->Next;
 while (now != NULL)
 {
  if (now->Sts==RUN && now->PID>=0 && now->Time<=0)/*如果该进程是运行中的一般进程并已执行完毕*/
  {
   last->Next = now->Next;
   ReleaseMem(now->Mem);
   free(now);
  }
  else
   last = last->Next;
  now = last->Next;
 }
 bt = BatchQueue;
 now = ProcQueue;
 while (bt != NULL && now != NULL)
 {
  bt->pcb = now;
  now->Sts = RUN;
  bt = bt->Next;
  now = now->Next;
 }
 while (now != NULL)
 {
  if (now->Sts == RUN)
  {
   now->Sts = SUSPEND;
  }
  now = now->Next;
 }
 return TRUE;
}

int PassSeconds(int n)
{
 static int time = 0;
 int i=0, ProcEnd = FALSE;
 PCB *pcb = ProcQueue;
 Batch *bt = BatchQueue;
 if (bt == NULL) return FALSE;
 time += n;
 if (time>=TIME)
 {
  i = time/TIME;/*经过多少时间段*/
  time = time%TIME;
 }
 while (bt != NULL)/*更新进程运行时间*/
 {
  if (bt->pcb->PID>=0)
  {
   bt->pcb->Time -= n;
   if (bt->pcb->Time <= 0)/*进程结束*/
   {
    ProcEnd = TRUE;
   }
  }
  bt = bt->Next;
 }
 if (i > 0)
 {
  while (pcb != NULL)/*更新进程优先权（动态优先权）*/
  {
   if (pcb->Sts == RUN && pcb->PID>=0)/*运行的进程优先权降低*/
   {
    pcb->Prior -= i;
    if (pcb->Prior < 0)
     pcb->Prior = 0;
   }
   else if (pcb->Sts == SUSPEND && pcb->PID>=0)/*挂起的进程优先权升高*/
    pcb->Prior += i;
   pcb = pcb->Next;
  }
 }
 if (i>0)
  SortProcQueue();/*如果优先级有变动则重新排序*/
 if (ProcEnd || i>0)
 {
  UpdateBatchs();/*更新多道进程*/
 }
 return TRUE;
}
/****************************************************************/
int InitMem()
{
 MemTable = (MemBlock*)malloc(sizeof(MemBlock));/*初始化为只有一个分区*/
 if (MemTable==NULL)
  return FALSE;
 MemTable->Offset = 0;
 MemTable->Size = TOTALMEM;
 MemTable->Sts = IDLE;
 MemTable->Next = NULL;
 SysMem = ApplyMem(SYSMEM);/*申请系统本身占用的内存*/
 if (SysMem == NULL)
 {
  free(MemTable);
  return FALSE;
 }
 return TRUE;
}

MemBlock* ApplyMem(UINT size)
{
 MemBlock *mem = NULL, *last,*now;
 if (MemTable == NULL)
  return NULL;
 last = MemTable;
 now = last->Next;
 if (last->Sts == IDLE)/*如果第一分区是空闲的*/
 {
  if (last->Size > size)/*该分区可以分出空间*/
  {
   mem = (MemBlock*)malloc(sizeof(MemBlock));
   if (mem == NULL) return NULL;
   mem->Next = last;
   mem->Offset = last->Offset;
   mem->Size = size;
   mem->Sts = INUSE;
   last->Offset = mem->Offset+mem->Size;
   last->Size = last->Size-size;
   MemTable = mem;
   return mem;
  }
  else if (last->Size == size)
  {
   mem = last;
   mem->Sts = INUSE;
   MemTable = mem;
   return mem;
  }
 }
 while (now != NULL)/*在分区表中查找可分配内存的空闲分区*/
 {
  if (now->Sts == IDLE)
  {
   if (now->Size > size)
   {
    mem = (MemBlock*)malloc(sizeof(MemBlock));
    mem->Offset = now->Offset;
    mem->Size = size;
    mem->Next = now;
    mem->Sts = INUSE;
    last->Next = mem;
    now->Offset = mem->Offset+mem->Size;
    now->Size = now->Size-size;
    return mem;
   }
   else if (now->Size == size)
   {
    mem = last;