操作系統--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;