目录

• 课程名：操作系统原理及Linux应用
• • 内容/作用：设计/实验/作业/练习
  • 学习：基于Linux的处理机调度高优先权算法
  • 一、前言
  • 二、环境与设备
  • 三、原理
  • 四、内容
  • 五、总结与分析

课程名：操作系统原理及Linux应用

内容/作用：设计/实验/作业/练习

学习：基于Linux的处理机调度高优先权算法

一、前言

1. 了解Linux下Emacs编辑器的使用方法，掌握各种常用的键盘操作命令；
2. 理解并掌握处理机调度算法。

二、环境与设备

1.软件：虚拟机VMware
2.环境：Linux系统环境

三、原理

   在采用多道系统的设计程序中，往往有若干进程同时处于就绪状态。当就绪状态进程数大于处理机数时，就必须按照某种策略来决定哪些进程优先占用处理机。本实验模拟在单处理机情况下处理机调度。

1、优先调度算法实现处理机的调度：
设计思路：
   1)每个进程用一个进程控制块PCB来代表，进程控制块包括进程名(进程的标识)、指针(按优先数的大小把进程连成队列，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针为"0")、要求运行时间、优先数、状态(就绪、结束)；
   2)每次运行处理机调度程序前，为每个进程确定它的"优先数"和"要求运行时间"；
   3)把给定的进程按优先数的大小连成队列，用一单元指出队首进程；
   4)每模拟执行一次进程，优先数减一，要求运行时间减一；
   5)如果要求运行的时间>=0，再将它加入队列（按优先数的大小插入，重置队首标志）；如果要求运行的时间=0，那么把它的状态修改为结束，且退出队列；
   6)若就绪队列不为空，重复上述，直到所有的进程都结束；
   7)程序有显示和打印语句，每次运行后显示变化。

2、按时间片轮转法实现处理机调度：
设计思路：
   1)每个进程用一个进程控制块PCB来代表，进程控制块包括进程名(进程的标识)、指针(把进程连成循环队列，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址)、已运行时间、状态(就绪、结束)；
   2)每次运行处理机调度程序前，为每个进程确定它的"要求运行时间"；
   3)用指针把给定的进程按顺序排成循环队列，用另一标志单元记录轮到的进程；
   4)每模拟运行一次进程，已运行时间加一；
   5)进程运行一次后，把该进程控制块的指针值送到标志单元，以指示下一个轮到的进程。若该进程要求运行时间≠已运行时间，未执行结束，待到下一轮再执行；若要求运行时间=已运行时间，状态改为结束，退出队列；
   6)若就绪队列不为空，重复步骤四和五；
   7)程序有显示和打印语句，每次运行后显示变化。

四、内容

   1、优先数调度算法：

#include
#include
#include
typedef struct node
{char name[10]; /*进程名*/int prio; /*优先数*/int cputime; /*占用cpu时间*/int needtime; /*要求运行时间*/char state; /*状态*/struct node *next; /*指针*/
}PCB;PCB *ready,*run,*finish; /*就绪 执行 结束指针*/
int N;void prt() /*输出函数，可以方便看到进程执行的演示*/
{PCB *p;printf(" NAME CPUTIME NEEDTIME PRIORITY STATUS\n");if(run!=NULL) 
{
printf("Run:\n");printf(" %-10s%-10d%-10d%-10d %c\n",run->name,run->cputime,run->needtime,run->prio,run->state); /*输出执行的进程的信息*/}p=ready;if(p!=NULL) printf("Ready:\n");while(p!=NULL){printf(" %-10s%-10d%-10d%-10d %c\n",p->name,p->cputime,p->needtime,p->prio,p->state); /*输出就绪进程的信息*/p=p->next;}p=finish;if(p!=NULL) printf("Finish:\n");while(p!=NULL){printf(" %-10s%-10d%-10d%-10d %c\n",p->name,p->cputime,p->needtime,p->prio,p->state); /*输出结束队列的信息*/p=p->next;}getchar();
} /*使用getchar()函数可以让输出时停留画面，等待人按回车继续*/void insert(PCB *q) /*插入新进程，把进程按优先数大小排序*/
{PCB *p1,*s,*r;int b;s=q; /*指针s指向新要插入的进程*/p1=ready; /*指针p1指向原来的进程队列的队首*/r=p1; /*使用指针r是指向p1前面的进程*/b=1;while((p1!=NULL)&&b)if(p1->prio>=s->prio) { r=p1; p1=p1->next; } /*新进程的优先数小，则p1*/else b=0; /*指向下一个进程继续比*/if(r!=p1) { r->next=s; s->next=p1; } /*新进程找到位置，插在r和p1之间*/else { s->next=p1; ready=s; }
} /*新进程的优先数最大，插在队首，并修改就绪队首ready指针*/void create()
{PCB *p;int i;ready=NULL; run=NULL; finish=NULL;printf("Please enter the name and time and priority of PCB:\n");for(i=0;ip=malloc(sizeof(PCB)); /*为新进程开辟空间*/scanf("%s",p->name); /*输入进程名*/scanf("%d",&p->needtime); /*输入进程要求运行时间*/scanf("%d",&p->prio); /*输入进程优先数*/p->cputime=0;p->state='W'; /*表示就绪队列中未在队首先执行，但也是就绪状态*/if (ready!=NULL) insert(p); /*就绪队首不为NULL，插入新进程*/else { p->next=ready; ready=p; }} /*否则先插在NULL前*/printf(" Display is going to start: \n");printf("***********************************************\n");prt();run=ready; /*队列排好，run指向就绪队列队首*/ready=ready->next; /*ready指向下一个进程，这样当进程执行时如果优先数小于其他的进程，应该先进行优先数最大的进程*/run->state='R';
} /*队首进程的状态为就绪*/void prio()
{while(run!=NULL){run->cputime=run->cputime+1; /*运行一次cpu占用时间加一*/run->needtime=run->needtime-1; /*运行一次要求运行时间减一*/run->prio=run->prio-1; /*运行一次优先数减一*/if(run->needtime==0) /*若要求运行时间为0时*/{run->next=finish; /*退出队列*/finish=run; /*finish为结束进程的队列 */run->state='E'; /*修改状态为结束*/run=NULL; /*释放run指针*/if (ready!=NULL) /*创建新就绪队列的头指针*/{ run=ready; run->state='R'; ready=ready->next; }}else if((ready!=NULL)&&(run->prio < ready->prio))/*队首进程的优先数比它下一个小，且下一个进程不为NULL时执行*/{run->state='W';run->next=NULL; /*队首进程退出进程队列*/insert(run); /*在进程队列中重新插入原来的队首进程*/run=ready; /*重新置就绪队列的头指针*/run->state='R';ready=ready->next;}prt();}
}void main()
{printf("Please enter the total number of PCB:\n");scanf("%d",&N);create(); /*模拟创建进程，并输入相关信息*/prio();
} /*优先数调度算法*/

五、总结与分析

   思路：先主函数输入要进行调度的进程数，然后调用函数create(),把进程的信息输入，再调用函数insert(),把输入的函数按照优先数的大小排成链表，然后调用函数prio()实现优先数调度。