动态高优先权优先调度算法

发布网友发布时间：2022-05-06 18:39

共2个回答

热心网友时间：2023-10-15 11:12

动态高优先权优先调度算法：

动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。

算法代码模拟实现：

#include<stdio.h>
#include<stdlib.h>
#define N 6

// 待插入就绪队列的进程数据
int id[N]    = { 0,  1,
2,  3,  4,
5 };
int priority[N] = { 9, 38, 17,
2,  7, 18 };
int cpuTime[N]  = { 0,
0,  0,  0,
0,  0 };
int allTime[N]  = { 3,
2,  3,  6,
1,  3 };

//********************************
//
//  模拟进程/PCB数据结构
//
//********************************

//
枚举进程的状态：就绪、执行、阻塞、完成
enum STATE { Ready, Run, Block, Finish
};

// 建立PCB结构体
struct PCB {
  int id;           // 标志数
  int priority;        // 优先数
  int cpuTime;         //
已占CPU时间
  int allTime;         //
还需占CPU时间
  int blockTime;        // 已被阻塞的时间
  STATE state;         //
进程状态
  PCB *pre;          //
PCB的前指针
  PCB *nxt;          //
PCB的后指针
};

//********************************
//
//  模拟进程队列
//
//********************************

// 进程入列
void queQush(PCB *process, PCB
*queHead)
{
  process->pre = NULL;
  process->nxt =
queHead->nxt;
  if(queHead->nxt != NULL) {
    // 非第一个入列
    queHead->nxt->pre =
process;
  }
  queHead->nxt = process;
}

// 进程出列
void quePop(PCB *process, PCB
*queHead)
{
  if(process->pre != NULL) {
    // 不是头节点
    process->pre->nxt =
process->nxt;
  }
else {
    queHead->nxt =
process->nxt;
  }
  if(process->nxt != NULL) {
    // 不是尾节点
    process->nxt->pre =
process->pre;
  }
  //
清空进程指针
  process->pre = process->nxt =
NULL;
}

// 查看队列里进程的信息
void queWalk(PCB *queHead)
{
  PCB *pro = queHead->nxt;
  if(pro == NULL) {
    printf("(无进程)\n");
    return;
  }
  while(pro != NULL)
  {
    printf("id:%d,
pri:%d,  alltime:%d\n",
pro->id,
      pro->priority,
pro->allTime);
    pro =
pro->nxt;
  }
}

//********************************
//
//  模拟就绪队列
//
//********************************

int readyQueNum;         // 就绪队列的进程数量
PCB readyQueHead;        //
就绪队列的头部
PCB *readyMaxProcess;      // 就绪队列中优先级最高的进程

// 进程插入到就绪队列
void readyQueQush(PCB
*process)
{
  readyQueNum ++;
  process->state = Ready;
  queQush(process, &readyQueHead);
}

// 优先级最高的进程出列
PCB* readyQuePop()
{
  readyQueNum --;
  quePop(readyMaxProcess,
&readyQueHead);
  return readyMaxProcess;
}

// 每个时间片，更新就绪队列里进程的信息
void readyQueUpdate()
{
  int maxPriority = -1;
  PCB *pro = readyQueHead.nxt;
  if(pro == NULL){
    // 就绪队列没有进程
    readyMaxProcess =
NULL;
    return;
  }
  while(pro != NULL)
  {
    pro->priority
++;
    if(pro->priority > maxPriority)
{
      maxPriority =
pro->priority;
      readyMaxProcess = pro;
    }
    pro =
pro->nxt;
  }
}

// 返回就绪队列最高优先级的值
int readyMaxPriority()
{
  return readyMaxProcess->priority;
}

// 查看就绪队列里进程的信息
void readyQueWalk()
{
  printf("就绪队列里的进程信息为：\n");
  queWalk(&readyQueHead);
}

//********************************
//
//  模拟阻塞队列
//
//********************************

#define EndBlockTime 3
     // 进程最长被阻塞时间

int blockQueNum;         // 阻塞队列的进程数量
PCB blockQueHead;        //
阻塞队列的头部
PCB *blockMaxProcess;      // 阻塞队列中优先级最高的进程

// 进程插入到阻塞队列
void blockQueQush(PCB
*process)
{
  blockQueNum ++;
  process->blockTime = 0;
  process->state = Block;
  queQush(process, &blockQueHead);
}

// 优先级最高的进程出列
PCB* blockQuePop()
{
  blockQueNum --;
  quePop(blockMaxProcess,
&blockQueHead);
  return blockMaxProcess;
}

// 每个时间片，更新阻塞队列里进程的信息
void blockQueUpdate()
{
  int maxPriority = -1;
  PCB *pro = blockQueHead.nxt;
  while(pro != NULL)
  {
    pro->blockTime
++;
    if(pro->blockTime >= EndBlockTime)
{
      PCB *process = pro;
      pro = pro->nxt;
      // 阻塞时间到，调入就绪队列
      blockQueNum --;
      quePop(process,
&blockQueHead);
      readyQueQush(process);
    } else
if(pro->priority > maxPriority)
{
      // 更新阻塞队列里优先级最高的进程指针
      maxPriority =
pro->priority;
      blockMaxProcess = pro;
      pro = pro->nxt;
    }
  }
}

// 查看阻塞队列里进程的信息
void blockQueWalk()
{
  printf("阻塞队列里的进程信息为：\n");
  queWalk(&blockQueHead);
}

//********************************
//
//  模拟动态优先权的进程调度
//
//********************************

// 初始化数据
void initData()
{
  //
初始化就绪队列和阻塞队列
  readyQueNum = blockQueNum = 0;
  readyMaxProcess = blockMaxProcess = NULL;
  readyQueHead.pre = readyQueHead.nxt = NULL;
  blockQueHead.pre = blockQueHead.nxt = NULL;

  //
初始化进程进入就绪队列
  int i, maxPriority = -1;
  for(i = 0; i < N; i
++)
  {
    // 分配一个PCB的内存空间
    PCB *pro = (PCB
*)malloc(sizeof(PCB));
    // 给当前的PCB赋值
    pro->id
    = id[i];
    pro->priority
= priority[i];
    pro->cpuTime
= cpuTime[i];
    pro->allTime
= allTime[i];
    pro->blockTime
= 0;
    if(pro->allTime > 0) {
      // 插入到就绪队列中
      readyQueQush(pro);
      // 更新就绪队列优先级最高的进程指针
      if(pro->priority >
maxPriority) {
        maxPriority = pro->priority;
        readyMaxProcess = pro;
      }
    }
  }
}

// 模拟cpu执行1个时间片的操作
void cpuWord(PCB
*cpuProcess)
{
  cpuProcess->priority -= 3;
  if(cpuProcess->priority < 0)
{
    cpuProcess->priority = 0;
  }
  cpuProcess->cpuTime ++;
  cpuProcess->allTime --;
  //
显示正执行进程的信息：
  printf("CPU正执行的进程信息为：\n");
  printf("id:M,  pri:M,
alltime:M\n",
cpuProcess->id,
    cpuProcess->priority,
cpuProcess->allTime);
}

int main()
{
  int timeSlice  = 0;     //
模拟时间片
  int cpuBusy   = 0;
    // 模拟cpu状态
  PCB *cpuProcess = NULL;    // 当前在cpu执行的进程
  //
初始化数据
  initData();
  //
模拟进程调度
  while(1)
  {
    if(readyQueNum == 0
&& blockQueNum == 0
&& cpuBusy == 0) {
      // 就绪队列、阻塞队列和cpu无进程，退出
      break;
    }
    //printf("\n%d %d",
readyQueNum, blockQueNum);
    if(cpuBusy == 0)
{
      // cpu空闲，选择一个进程进入cpu
      if(readyQueNum > 0)
{
        //
选择绪队列优先级最高的进程
        cpuProcess
= readyQuePop();
      } else {
        //
就绪队列没有进程，改为选择阻塞队列优先级最高的进程
        cpuProcess
= blockQuePop();
      }
      cpuProcess->cpuTime =
0;
      cpuProcess->state =
Run;
      cpuBusy = 1;
    }
    timeSlice ++;
    printf("\n第%d个时间片后：\n",
timeSlice);
    //
模拟cpu执行1个时间片的操作
    cpuWord(cpuProcess);
    if(cpuProcess->allTime == 0) {
      cpuProcess->state =
Finish;
      // 释放已完成进程的PCB
      free(cpuProcess);
      cpuBusy = 0;
    }
    //
更新就绪队列和阻塞队列里的进程信息
    blockQueUpdate();
    readyQueUpdate();
    //
查看就绪队列和阻塞队列的进程信息
    readyQueWalk();
    blockQueWalk();
    if(cpuBusy == 1
&& readyQueNum >0
&&
      cpuProcess->priority
< readyMaxPriority()) {
      // 需抢占cpu，当前执行的进程调入阻塞队列
      blockQueQush(cpuProcess);
      cpuProcess = readyQuePop();
    }
  }
  printf("\n模拟进程调度算法结束\n");
  return 0;
}

热心网友时间：2023-10-15 11:12

在百度文库里有样例的
http://wenku.baidu.com/view/1aee3f5e3b3567ec102d8aa2.html

参考资料：http://wenku.baidu.com/view/1aee3f5e3b3567ec102d8aa2.html

热心网友时间：2023-10-15 11:12

动态高优先权优先调度算法：

算法代码模拟实现：

热心网友时间：2023-10-15 11:12

在百度文库里有样例的
http://wenku.baidu.com/view/1aee3f5e3b3567ec102d8aa2.html

参考资料：http://wenku.baidu.com/view/1aee3f5e3b3567ec102d8aa2.html