Linux进程调度模拟3

/*模拟LINUX进程调度双队列实现静态优先级算法和时间片轮转算法，当进程时间
片用完时主动释放CPU的控制权运行队列里的进程放到睡眠队列里，让低优先级进
程先运行,当一轮调度用完时重新分配时间片，从睡眠队列里唤醒睡眠的队列*/

 

//在下一个版本中将入互斥锁，动态优先级以及优先级逆转

#include
#include
#include

#define NUM 6

#define RUN  1
#define SLEEP  0
#define READY  2

#define DEG_SCHEDULE

struct TaskStruct
{
 int PcbName ;  /*进程名字*/
 int ReqCount;    /*进程应该执行计数*/
 int RunTime;     /*进程实际执行时间数*/
 int Prority;    /*进程静态优先级*/
 int DynamicPrority; /*进程动态优先级*/
 int PcbStatus;   /*进程状态*/
 int PcbTime;     /*进程分配时间片*/
 struct TaskStruct *prev;
 struct TaskStruct *next;
};

struct RunQueue  /*CPU调度运行队列*/
{
 struct  TaskStruct *PointerHead; /*指向运行进程链表头*/
 int PcbNumber;    /*CPU每次调度计数器*/
};

struct SleepQueue /*CPU调度睡眠队列*/
{
 struct  TaskStruct *PointerHead; /*指向睡眠进程链表头*/
};

static int CpuHandler(void);
 

void InitPcb(struct  TaskStruct *pcb);

static int Schedule(struct RunQueue *queue,struct SleepQueue *queue_t);

int main(void)
{

 CpuHandler(); /*进入CPU调度*/

 return 0;
}

 

static int CpuHandler(void)
{
 int i,ret;
 struct  TaskStruct *Newpcb,*p;
 struct RunQueue *NewRunQueue;
 struct SleepQueue *NewSleepQueue;
 int a[4][4] = {{1,1,0,1},{2,2,0,2},{3,3,0,3},{4,4,0,4}};

/*运行队列初始化*/
 NewRunQueue = (struct RunQueue *)malloc(sizeof(struct RunQueue));
 NewRunQueue->PointerHead = NULL;
 NewRunQueue->PcbNumber = 10;

/*睡眠队列初始化*/
 NewSleepQueue = (struct SleepQueue *)malloc(sizeof(struct SleepQueue));
 NewSleepQueue->PointerHead = NULL;

 for(i = 0; i < 4;i++) /*进程初始化*/
 {
  Newpcb = (struct  TaskStruct *)malloc(sizeof(struct  TaskStruct));
  Newpcb->PcbName       = a[i][0];
  Newpcb->ReqCount      = a[i][1];
  Newpcb->RunTime     = a[i][2];
  Newpcb->Prority    = a[i][3];
  Newpcb->PcbStatus     = READY;

  InitPcb(Newpcb);
  
  if(NewRunQueue->PointerHead == NULL) /*进程队列初始化假设进程初始化时全入运行队列*/
  {
   NewRunQueue->PointerHead = Newpcb;
  }else{
   p->next = Newpcb;
   Newpcb->prev = p;
  }
  
  p =  Newpcb;
  NewRunQueue->PcbNumber++;
 }

 Schedule(NewRunQueue,NewSleepQueue);/*进程调度*/

 return 0;
}

 

void InitPcb(struct  TaskStruct *pcb)/*进程初始化*/
{
 pcb->prev = NULL; 
 pcb->next = NULL;

}

static int Schedule(struct RunQueue *queue,struct SleepQueue *sleepqueue) /*进程调度*/
{
 struct TaskStruct *pcb,*CurrRun,*pcb1;
 int i,CpuScheduleTme = 10; /*模拟一次调度用的总时间片，可以自己调整*/

 CurrRun = queue->PointerHead;

  /*进入调度时给进程分配时间片*/
 for(pcb = queue->PointerHead; pcb != NULL; pcb = pcb->next)
 {
//  if(pcb->PcbTime  == 0)
//  {
//   pcb->Prority +=4;
//  }
  pcb->PcbTime = 3;
 }

 
 while(queue->PointerHead != NULL) /**/
 {

  for(pcb = queue->PointerHead; pcb != NULL; pcb = pcb->next)
  {
   if(pcb == queue->PointerHead)
   {
    CurrRun = pcb;
   }else{
    if(CurrRun->Prority < pcb->Prority)
     CurrRun = pcb;    
   }
   CurrRun->PcbStatus = RUN;
  }
  CpuScheduleTme--;
  CurrRun->ReqCount--;
  CurrRun->PcbTime--;
  
  

#ifdef DEG_SCHEDULE  
  printf("present process  = %d CurrRun->ReqCount = %d\n",CurrRun->PcbName,CurrRun->ReqCount);
#endif
#if 1
  if(CurrRun->PcbTime == 0)
  {
 #ifdef DEG_SCHEDULE  
   printf("%d enter sleep status!\n",CurrRun->PcbName);
 #endif 
   CurrRun->PcbStatus = SLEEP;
   CurrRun->Prority -=2; /*进程惩罚性降优先级处理*/
   if(CurrRun == queue->PointerHead)/*将当前进程踢出运行队列*/
   {
    queue->PointerHead = CurrRun->next;
   }else if (CurrRun->next != NULL){
    CurrRun->prev->next = CurrRun->next;
    CurrRun->next->prev = CurrRun->prev;
   }else{
    CurrRun->prev->next = NULL;
   }
   
   if(sleepqueue->PointerHead == NULL) /*当前进程加入到睡眠队列*/
   {
    sleepqueue->PointerHead = CurrRun;
    CurrRun->next = NULL;
   }else{
    for(pcb1 = sleepqueue->PointerHead; pcb != NULL; pcb1 = pcb1->next)    
    {
     pcb1->next = CurrRun;
     CurrRun->prev = pcb1;
     CurrRun->next = NULL;
    }
   }
//   printf("%d enter sleep status!\n",CurrRun->PcbName);
  }
#endif  
  if(CurrRun->ReqCount == 0)
  {
   if(CurrRun == queue->PointerHead)
   {
    queue->PointerHead = CurrRun->next;
   }else if (CurrRun->next != NULL){
    CurrRun->prev->next = CurrRun->next;
    CurrRun->next->prev = CurrRun->prev;
   }else{
    CurrRun->prev->next = NULL;
   }   
   printf("Run process name = %d  Reqcount = %d Sechedule count = %d\n",CurrRun->PcbName,CurrRun->ReqCount,CpuScheduleTme);
  }
  
  if(CpuScheduleTme == 0)/*一次调度时间片用完后重新调度*/
  {
   printf("re-schedule!\n");
   Schedule(queue,sleepqueue);
  }
 }

 

    CurrRun = sleepqueue->PointerHead;

   
    if (CpuScheduleTme != 0)/*如果运行队列里的任务都完成CPU调度睡眠队列里的进程*/
    {
        for(pcb1 = sleepqueue->PointerHead; pcb1 != NULL; pcb1 = pcb1->next)
        {
            if(pcb1 == queue->PointerHead)
   {
    CurrRun = pcb1;
   }else{
    if(CurrRun->Prority < pcb1->Prority)
     CurrRun = pcb1;    
   }
   CurrRun->PcbStatus = RUN;
  }
  CpuScheduleTme--;
  CurrRun->ReqCount--;
  CurrRun->PcbTime--;

#ifdef DEG_SCHEDULE  
  printf("present process  = %d CurrRun->ReqCount = %d\n",CurrRun->PcbName,CurrRun->ReqCount);
#endif
       
        CpuScheduleTme--;

        if(CpuScheduleTme == 0)
        {
            return 0;
        }

    }
   
 return 0;
}