操作系统进程控制与调度模拟设计

操作系统进程调度算法模拟~

第一部分： 实时调度算法介绍

对于什么是实时系统，POSIX 1003.b作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个由Donald Gillies提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。

实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。

一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于CPU和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论，然后研究普通的 Linux操作系统的进程调度以及各种实时Linux系统为了支持实时特性对普通Linux系统所做的改进。最后分析了将Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时Linux是如何解决这些问题的。

1. 实时CPU调度算法分类

各种实时操作系统的实时调度算法可以分为如下三种类别[Wang99][Gopalan01]：基于优先级的调度算法（Priority-driven scheduling-PD）、基于CPU使用比例的共享式的调度算法（Share-driven scheduling-SD）、以及基于时间的进程调度算法（Time-driven scheduling-TD），下面对这三种调度算法逐一进行介绍。

1.1. 基于优先级的调度算法

基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型[Krishna01][Wang99]：

静态优先级调度算法：

这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级。

动态优先级调度算法：

这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。在实时调度算法中， EDF算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个任务根据它们的截止期限（Deadline）来分配优先级，具有最近的截止期限的任务具有最高的优先级。

1.2. 基于比例共享调度算法

虽然基于优先级的调度算法简单而有效，但这种调度算法提供的是一种硬实时的调度，在很多情况下并不适合使用这种调度算法：比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用，使用一种比例共享式的资源调度算法（SD算法）更为适合。

比例共享调度算法指基于CPU使用比例的共享式的调度算法，其基本思想就是按照一定的权重（比例）对一组需要调度的任务进行调度，让它们的执行时间与它们的权重完全成正比。

我们可以通过两种方法来实现比例共享调度算法[Nieh01]：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是逐次调度就绪队列中的各个进程投入运行，但根据分配的权重调节分配个每个进程的运行时间片。

比例共享调度算法可以分为以下几个类别：轮转法、公平共享、公平队列、彩票调度法（Lottery）等。

比例共享调度算法的一个问题就是它没有定义任何优先级的概念；所有的任务都根据它们申请的比例共享CPU资源，当系统处于过载状态时，所有的任务的执行都会按比例地变慢。所以为了保证系统中实时进程能够获得一定的CPU处理时间，一般采用一种动态调节进程权重的方法。

1.3. 基于时间的进程调度算法

对于那些具有稳定、已知输入的简单系统，可以使用时间驱动（Time-driven:TD）的调度算法，它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段，在明确系统中所有的处理情况下，对于各个任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。

这种调度算法的优点是任务的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现有任务需要被执行而CPU却保持空闲的情况。

2. 通用Linux系统中的CPU调度

通用Linux系统支持实时和非实时两种进程，实时进程相对于普通进程具有绝对的优先级。对应地，实时进程采用SCHED_FIFO或者SCHED_RR调度策略，普通的进程采用SCHED_OTHER调度策略。

在调度算法的实现上，Linux中的每个任务有四个与调度相关的参数，它们是rt_priority、policy、priority（nice）、counter。调度程序根据这四个参数进行进程调度。

在SCHED_OTHER 调度策略中，调度器总是选择那个priority+counter值最大的进程来调度执行。从逻辑上分析，SCHED_OTHER调度策略存在着调度周期（epoch），在每一个调度周期中，一个进程的priority和counter值的大小影响了当前时刻应该调度哪一个进程来执行，其中 priority是一个固定不变的值，在进程创建时就已经确定，它代表了该进程的优先级，也代表这该进程在每一个调度周期中能够得到的时间片的多少； counter是一个动态变化的值，它反映了一个进程在当前的调度周期中还剩下的时间片。在每一个调度周期的开始，priority的值被赋给 counter，然后每次该进程被调度执行时，counter值都减少。当counter值为零时，该进程用完自己在本调度周期中的时间片，不再参与本调度周期的进程调度。当所有进程的时间片都用完时，一个调度周期结束，然后周而复始。另外可以看出Linux系统中的调度周期不是静态的，它是一个动态变化的量，比如处于可运行状态的进程的多少和它们priority值都可以影响一个epoch的长短。值得注意的一点是，在2.4以上的内核中， priority被nice所取代，但二者作用类似。

可见SCHED_OTHER调度策略本质上是一种比例共享的调度策略，它的这种设计方法能够保证进程调度时的公平性--一个低优先级的进程在每一个epoch中也会得到自己应得的那些CPU执行时间，另外它也提供了不同进程的优先级区分，具有高priority值的进程能够获得更多的执行时间。

对于实时进程来说，它们使用的是基于实时优先级rt_priority的优先级调度策略，但根据不同的调度策略，同一实时优先级的进程之间的调度方法有所不同：

SCHED_FIFO：不同的进程根据静态优先级进行排队，然后在同一优先级的队列中，谁先准备好运行就先调度谁，并且正在运行的进程不会被终止直到以下情况发生：1.被有更高优先级的进程所强占CPU；2.自己因为资源请求而阻塞；3.自己主动放弃CPU（调用sched_yield）；

SCHED_RR：这种调度策略跟上面的SCHED_FIFO一模一样，除了它给每个进程分配一个时间片，时间片到了正在执行的进程就放弃执行；时间片的长度可以通过sched_rr_get_interval调用得到；

由于Linux系统本身是一个面向桌面的系统，所以将它应用于实时应用中时存在如下的一些问题：

Linux系统中的调度单位为10ms，所以它不能够提供精确的定时；

当一个进程调用系统调用进入内核态运行时，它是不可被抢占的；

Linux内核实现中使用了大量的封中断操作会造成中断的丢失；

由于使用虚拟内存技术，当发生页出错时，需要从硬盘中读取交换数据，但硬盘读写由于存储位置的随机性会导致随机的读写时间，这在某些情况下会影响一些实时任务的截止期限；

虽然Linux进程调度也支持实时优先级，但缺乏有效的实时任务的调度机制和调度算法；它的网络子系统的协议处理和其它设备的中断处理都没有与它对应的进程的调度关联起来，并且它们自身也没有明确的调度机制；

3. 各种实时Linux系统

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大学（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，为了在Linux系统中提供对于硬实时的支持，它实现了一个微内核的小的实时操作系统（我们也称之为RT-Linux的实时子系统），而将普通Linux系统作为一个该操作系统中的一个低优先级的任务来运行。另外普通Linux系统中的任务可以通过FIFO和实时任务进行通信。RT-Linux的框架如图 1所示：


图 1 RT-Linux结构


RT -Linux的关键技术是通过软件来模拟硬件的中断控制器。当Linux系统要封锁CPU的中断时时，RT-Linux中的实时子系统会截取到这个请求，把它记录下来，而实际上并不真正封锁硬件中断，这样就避免了由于封中断所造成的系统在一段时间没有响应的情况，从而提高了实时性。当有硬件中断到来时， RT-Linux截取该中断，并判断是否有实时子系统中的中断例程来处理还是传递给普通的Linux内核进行处理。另外，普通Linux系统中的最小定时精度由系统中的实时时钟的频率决定，一般Linux系统将该时钟设置为每秒来100个时钟中断，所以Linux系统中一般的定时精度为 10ms，即时钟周期是10ms，而RT-Linux通过将系统的实时时钟设置为单次触发状态，可以提供十几个微秒级的调度粒度。

RT-Linux实时子系统中的任务调度可以采用RM、EDF等优先级驱动的算法，也可以采用其他调度算法。

RT -Linux对于那些在重负荷下工作的专有系统来说，确实是一个不错的选择，但他仅仅提供了对于CPU资源的调度；并且实时系统和普通Linux系统关系不是十分密切，这样的话，开发人员不能充分利用Linux系统中已经实现的功能，如协议栈等。所以RT-Linux适合与工业控制等实时任务功能简单，并且有硬实时要求的环境中，但如果要应用与多媒体处理中还需要做大量的工作。

意大利的RTAI( Real-Time Application Interface )源于RT-Linux，它在设计思想上和RT-Linux完全相同。它当初设计目的是为了解决RT-Linux难于在不同Linux版本之间难于移植的问题，为此，RTAI在 Linux 上定义了一个实时硬件抽象层，实时任务通过这个抽象层提供的接口和Linux系统进行交互，这样在给Linux内核中增加实时支持时可以尽可能少地修改 Linux的内核源代码。

3.2. Kurt-Linux

Kurt -Linux由Kansas大学开发，它可以提供微秒级的实时精度[KurtWeb] [Srinivasan]。不同于RT-Linux单独实现一个实时内核的做法，Kurt -Linux是在通用Linux系统的基础上实现的，它也是第一个可以使用普通Linux系统调用的基于Linux的实时系统。

Kurt-Linux将系统分为三种状态：正常态、实时态和混合态，在正常态时它采用普通的Linux的调度策略，在实时态只运行实时任务，在混合态实时和非实时任务都可以执行；实时态可以用于对于实时性要求比较严格的情况。

为了提高Linux系统的实时特性，必须提高系统所支持的时钟精度。但如果仅仅简单地提高时钟频率，会引起调度负载的增加，从而严重降低系统的性能。为了解决这个矛盾， Kurt-Linux采用UTIME所使用的提高Linux系统中的时钟精度的方法[UTIMEWeb]：它将时钟芯片设置为单次触发状态（One shot mode），即每次给时钟芯片设置一个超时时间，然后到该超时事件发生时在时钟中断处理程序中再次根据需要给时钟芯片设置一个超时时间。它的基本思想是一个精确的定时意味着我们需要时钟中断在我们需要的一个比较精确的时间发生，但并非一定需要系统时钟频率达到此精度。它利用CPU的时钟计数器TSC (Time Stamp Counter)来提供精度可达CPU主频的时间精度。

对于实时任务的调度，Kurt-Linux采用基于时间（TD）的静态的实时CPU调度算法。实时任务在设计阶段就需要明确地说明它们实时事件要发生的时间。这种调度算法对于那些循环执行的任务能够取得较好的调度效果。

Kurt -Linux相对于RT-Linux的一个优点就是可以使用Linux系统自身的系统调用，它本来被设计用于提供对硬实时的支持，但由于它在实现上只是简单的将Linux调度器用一个简单的时间驱动的调度器所取代，所以它的实时进程的调度很容易受到其它非实时任务的影响，从而在有的情况下会发生实时任务的截止期限不能满足的情况，所以也被称作严格实时系统（Firm Real-time）。目前基于Kurt-Linux的应用有：ARTS（ATM Reference Traffic System）、多媒体播放软件等。另外Kurt-Linux所采用的这种方法需要频繁地对时钟芯片进行编程设置。

3.3. RED-Linux

RED -Linux是加州大学Irvine分校开发的实时Linux系统[REDWeb][ Wang99]，它将对实时调度的支持和Linux很好地实现在同一个操作系统内核中。它同时支持三种类型的调度算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

为了提高系统的调度粒度，RED-Linux从RT-Linux那儿借鉴了软件模拟中断管理器的机制，并且提高了时钟中断频率。当有硬件中断到来时，RED-Linux的中断模拟程序仅仅是简单地将到来的中断放到一个队列中进行排队，并不执行真正的中断处理程序。

另外为了解决Linux进程在内核态不能被抢占的问题， RED-Linux在Linux内核的很多函数中插入了抢占点原语，使得进程在内核态时，也可以在一定程度上被抢占。通过这种方法提高了内核的实时特性。

RED-Linux的设计目标就是提供一个可以支持各种调度算法的通用的调度框架，该系统给每个任务增加了如下几项属性，并将它们作为进程调度的依据：

Priority：作业的优先级；

Start-Time：作业的开始时间；

Finish-Time：作业的结束时间；

Budget：作业在运行期间所要使用的资源的多少；

通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些属性值，几乎可以实现所有的调度算法。这样的话，可以将三种不同的调度算法无缝、统一地结合到了一起。

给，已经编译运行通过了，简单写的：

#include
#include
#include

/*********************以下是全局数据结构和变量***********************/
/*PCB 结构*/
struct PCB{
int pname;
int pri;
int runtime;
int waittime;
struct PCB *next;
}pcb[7];

/* 运行指针*/
struct PCB *running;

/*高优先级就绪队列头指针*/
struct PCB *Hready;

/*低优先级队列头指针*/
struct PCB *Lready;

/*等待队列头指针*/
struct PCB *wait;

int sig=0;


/**************************以下是函数说明****************************/
/*利用循环实现延迟*/
void delay();

/*模拟进程3－9*/
void proc(struct PCB *running);

/*将node插入到head所指示的队列的尾部*/
void InsertIntoQueueTail(struct PCB ** head,struct PCB *node);

/*进程调度函数*/
int proc_switch();

/*进程等待函数*/
void proc_wait();

/*进程唤醒函数*/
int proc_wakeup();


/************************以下是函数定义及注释************************/
/*主函数*/
main()
{
int i;
/*初始化，创建进程3－9，置低优先级，等待时间为0，
依次插入低优先级队列*/
for(i = 0;i < 7;i++){
pcb[i].pname = i+3;
pcb[i].pri = 0;
pcb[i].waittime = 0;
InsertIntoQueueTail(&Lready,&pcb[i]);
}
/*等待队列和高优先级队列为空*/
wait = NULL;
Hready=NULL;

printf("
The process_switch begin:
");
/*模拟进程调度开始*/
for(;;)
{
switch(sig){
case 0:/*无进程等待调度，打印信息并返回*/
if(!proc_switch())
{
printf("No Process to run,press any key to return:
");
getchar();
}
break;
case 1:proc_wait();
break;
case 3:
case 4:
case 5:
case 6:
case 7:
case 8:
case 9:proc(running);
break;
default:printf("
error!");
exit(-1);
}
}
}

/*功能：延迟一个时间片*/
/*入口参数：无*/
/*出口参数：无*/
void delay()
{
int i,j;
for(i=0;i<20000;i++)
for(j=0;j<10000;j++)
{
}
}

/*功能：进程3－9*/
/*入口参数：运行指针*/
/*出口参数：无*/
void proc(struct PCB * running)
{
int i;
srand( (unsigned)time( NULL ) );
/*显示当前运行的进程的id*/
printf("
Now Process %d is running
",running->pname);
/*当前进程执行running->runtime个时间片*/
for(i=running->runtime;i>0;i--){
/*显示剩余的时间片*/
printf("%d time slice(s) left
",i);
/*延迟*/
delay();
proc_wakeup();
/*产生一个1到1000的随机数，若该随机数小余100，当前进程等待，*/
if((rand()%1000+1)<100){
printf("Process %d begins to wait.
",running->pname);
sig=1;
return;
}
}
/*显示时间片耗尽，进程转为低优先级就绪状态*/
printf("Time slices for process %d exhausted.
",running->pname);
InsertIntoQueueTail(&Hready,running);
sig=0;
return;

}
/*功能：将一个节点插入队列尾部*/
/*入口参数：队列头指针地址head，待插入结点node*/
/*出口参数：无*/
void InsertIntoQueueTail(struct PCB **head,struct PCB *node)
{
struct PCB *p;
node->next=NULL;
/*被插入队列为空*/
if(*head==NULL){
*head=node;
return;
}
/*被插入队列不为空*/
else{
p=*head;
/*找到队列的最后一个结点*/
while(p->next!=NULL) p=p->next;
p->next=node;
}
}

/*功能：进程调度*/
/*入口参数：无*/
/*出口参数：若调度成功，返回1，否则返回0*/

int proc_switch()
{
/*若高优先级就绪队列和低优先级就绪队列均为空，则循环执行进程唤醒*/
while(Hready == NULL && Lready == NULL)
if(!proc_wakeup()) return 0;

/*若高优先级就绪队列非空，则执行其第一个进程，分配2个时间片*/
if(Hready != NULL){
running = Hready;
Hready = Hready -> next;
running->runtime = 2;
}
/*若高优先级就绪队列为空，则执行低优先级就绪队列的第一个进程，
分配5个时间片*/
else{
running = Lready;
Lready=Lready -> next;
running -> runtime = 5;
}
/*别调度进程的id赋给sig*/
sig = running -> pname;
return 1;
}

/*功能：进程等待。将当前运行进程置高优先级，等待时间为20，
插入等待队列尾部*/
/*入口参数：无*/
/*出口参数：无*/
void proc_wait()
{
struct PCB *p;
running->pri=1;
running->waittime=20;
InsertIntoQueueTail(&wait,running);
sig=0;
return;
}

/*功能：进程唤醒*/
/*入口参数：无*/
/*出口参数：若等待队列为空，则返回0，否则返回1*/
int proc_wakeup()
{
struct PCB *p,*last,*MoveToReady;
p = wait;
/*等待队列为空，返回0*/
if(p == NULL) return 0;

/*延迟*/
delay();
/*等待队列中每个进程的等待时间减1*/
while(p != NULL){
p -> waittime -= 1;
p=p->next;
}
p=wait;
/*从等待队列中摘除等待时间为0的进程，插入到高优先级就绪队列的尾部*/
while(p!=NULL){
if(p -> waittime == 0){
MoveToReady = p;
if (p == wait)
wait = p->next;
else
last -> next = p->next;
p = p -> next;
InsertIntoQueueTail(&Hready,MoveToReady);
}
else{

p = p -> next;
}
}
sig =0;
return 1;
}

你要代码么？这个就能用，是C＋＋做的。我的课程设计，呵呵
/*
* 进程调度实验
* 本程序提供了以下几种进程调度方法
* 1、时间片轮询法
* 2、可强占优先法
* 3、非抢占算法
*
*/

#include <iostream.h>
#include <string.h>
#include <fstream.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int proc;
int piece;
//完成状态
#define FINISH 0
//运行状态
#define RUNNING 1
//就绪状态
#define READY 2
//io状态
#define IO 3
//等待IO
#define WAIT 4
//定义PCB结构
typedef struct tagPCBS{
// 编号
long pid;
// 进程名
char pname[10];
// 状态
int pstate;
// 总时间
int pneedtime;
// 开始时间
int piostarttime;
// 需要时间
int pioneedtime;
// 当前时间
int ptime;
// 优先级
int priority;
} pcbs, *ppcbs ;

class pcbnode;
//队列结点
class pcbnode
{
public:
pcbs *pcb;
pcbnode *link;
pcbnode();
~pcbnode();
int run();//运行操作
int runend();//运行结束
void runio();//IO操作
int ioend();//io结束
int insertnode(pcbnode *p,pcbnode *q);//在q后插入结点p
int deletenode(pcbnode *p,pcbnode *q);//删除p结点，q为p的前驱
int addnode(pcbnode *p);//增加结点
int pcbnode::isio();//是否开始IO
} ;

pcbnode::pcbnode(){
pcb = 0;
link = 0;}

pcbnode::~pcbnode()
{
if( link )
delete link;
if( pcb )
pcb->pstate = FINISH;
}

int pcbnode::run()
{
pcb->pstate = RUNNING ;
++ pcb->ptime ;
//优先级降低
pcb->priority -- ;
return 0;
}

int pcbnode::runend()
{
return ( pcb->pneedtime <= pcb->ptime ) ;
}

int pcbnode::isio()
{
return ( (pcb->piostarttime == pcb->ptime) && (pcb->pioneedtime > 0) ) ;
}

int pcbnode::ioend()
{
return ( (pcb->pioneedtime) <= 0 ) ;
}

void pcbnode::runio()
{
pcb->pstate = IO;
--(pcb->pioneedtime);
}

int pcbnode::addnode( pcbnode *p )
{
pcbnode *q;
q = this;
p->pcb->pstate = READY;
while( q->link )
q = q->link;
q->link = p;
return 0;
}

int pcbnode::insertnode( pcbnode *p,pcbnode *q )
{
p->link = q->link;
q->link = p;
return 0;
}

int pcbnode::deletenode( pcbnode *p, pcbnode *q )
{
q->link = p->link;
p->link = 0;
return 0;
}

int randInt( int seed )
{
int r;
r = rand();
while ( (r > seed) || ( r < 0 ) )
r = rand();
return r;
}

void newpcb( pcbs *pcb, int order )

//随机生成进程
{
char buf[10] ;
pcb->pid = order ;
strcpy( pcb->pname, "proc" ) ;
itoa( order, buf, 10 ) ;
strcat( pcb->pname, buf ) ;
pcb->pneedtime = randInt( 10 ) ;
pcb->piostarttime = randInt( pcb->pneedtime ) ;
pcb->pioneedtime = randInt( 10 ) ;
pcb->ptime = 0 ;
pcb->priority = randInt( 10 ) ;
}

void pprint( pcbs *pcb, int count )
{
int i ;
// 打印进程状态
cout<<"进程号|进程名|状态|需求量|系统分配|需要分配|运行时间|优先级"<<endl ;
for( i = 0 ; i < count ; i ++ )
{
cout<<pcb[i].pid<<'\t'<< pcb[i].pname<<'\t' ;
switch( pcb[i].pstate )
{
case IO :
cout<<"IO" ;
break;
case RUNNING:
cout<<"运行中";
break;
case READY:
cout<<"就绪";
break;
case FINISH:
cout<<"完成";
break;
case WAIT:
cout<<"等待";
break;
}
cout<<'\t'<<pcb[i].pneedtime ;
cout<<'\t'<<pcb[i].piostarttime<<'\t'<<pcb[i].pioneedtime<<'\t'<<pcb[i].ptime ;
cout<<'\t'<<pcb[i].priority ;
cout<< endl ;
}
cout<<"---------------------------------------------"<<endl ;

}

//时间片轮循法
/*
* 每执行一次，cpu时间加1， 还需时间减1
* 每次执行时间片指定次数
* 时间片执行完毕排到就绪队列尾部
*/
void poll(pcbs * pcb, int pcbsnum)
{
pcbnode running, ready, blocked ;
pcbnode *p ;
pcbnode *q ;
cout<<"输入时间片长度："<<endl;
cin>>piece;
int i ;
/* 将进程表中的进程加到就绪队列中 */
for( i = 0 ; i < pcbsnum ; i++ )
{
p = new pcbnode ;
p->pcb = pcb + i ;
ready.addnode( p ) ;
}

//开始调度
while( ready.link || running.link || blocked.link )
{
/*
* 判断正在运行的进程是否要进行IO
* 是则将其送到IO队列否则
* 将正在运行的进程送到就绪队列中
*/
if( running.link )
{
//需要IO?
if( running.link->isio() )
{
blocked.addnode(running.link) ;
running.link->pcb->pstate = WAIT ;
}
//运行结束?
else if ( running.link->runend() )
{
p = running.link ;
running.link = 0 ;
delete p ;
}
//调度
else
{
ready.addnode(running.link) ;
running.link->pcb->pstate = READY ;
}
running.link = 0;
}
/*
* 将就绪队列的首结点送入运行队列
*/
q = &ready;
p = ready.link;
if( ready.link )
{
ready.deletenode( p, q ) ;
running.addnode( p ) ;
p->pcb->pstate=RUNNING ;
}

/*
* 将处理完IO的进程送到就绪队列
*/
p = blocked.link;
q = &blocked;
if( p )
{
int r;
r = p->ioend();
if( r )
{
blocked.deletenode( p, q ) ;
ready.addnode( p ) ;
p = q->link ;
}
}

/*
* 运行进程,运行时间为时间片指定长度
*/
int j = piece;

while( j-- )
{
p = running.link ;
q = &running ;
if( p )
{
//is IO start?
if( !(p->isio()) )
p->run();//RUN
}
/*
* IO
*/
p = blocked.link;
q = &blocked;
if (p)
p->runio();
//print proc state
pprint(pcb, pcbsnum);
}
}
}

//可抢占的优先调度
/*
* 从就绪队列中取出最优先的进程送到运行队列
* 每运行一次，正在运行的进程优先数减1，等待的进程优先数加1
* 如果就绪队列中的最大优先数进程的优先数大于正在运行的优先数，
* 则运行的进程让出cpu,排到就绪队列的尾部，将最大优先数的进程送进
* 运行队列。
*/
void priority( pcbs * pcb, int pcbsnum )
{
pcbnode running, ready, blocked ;
pcbnode *p, *f, *front ;
pcbnode *q ;
int i ;
/*将进程表中的进程加到就绪队列中*/
for ( i = 0 ; i < pcbsnum ; i ++ )
{
p = new pcbnode ;
p->pcb = pcb + i ;
ready.addnode( p ) ;
}

while( ready.link || running.link || blocked.link )
{
//判断将运行队列中的进程是否要io或结束
if( running.link )
{
//需要IO?
if( running.link->isio() )
{
blocked.addnode( running.link ) ;
running.link->pcb->pstate = WAIT ;
running.link = 0 ;
}
//运行结束?
else if( running.link->runend() )
{
p = running.link;
running.link = 0;
delete p;
}
}

//寻找最大的一个优先级
p = ready.link;
q = p ;
f = &ready ;
front = f ;
if( p )
{
int maxpri = p->pcb->priority ;
while( p )
{
if( p->pcb->priority > maxpri )
{
maxpri = p->pcb->priority ;
front = f;
q = p;
}
f = p;
p = p->link;
}
}

//如果最大优先级大于正在运行的优先级则强占cpu
p = running.link;
if( q )
{
if (p)
{
if( p->pcb->priority < q->pcb->priority )
{
ready.addnode(p);
running.deletenode( p, &running ) ;
p->pcb->pstate = READY ;
running.addnode( q ) ;
ready.deletenode( q, front ) ;
q->pcb->pstate = RUNNING ;
}
}
else
{
running.addnode( q ) ;
ready.deletenode( q, front ) ;
q->pcb->pstate = RUNNING ;
}
}
/*
* 将处理完IO的进程送到就绪队列
*/
p = blocked.link;
q = &blocked;
if( p )
{
int r;
r = p->ioend();
if( r )
{
blocked.deletenode( p, q ) ;
ready.addnode( p ) ;
p=q->link;
}
}
// 运行进程
p = running.link ;
q = &running ;
if( p )
{
//is IO start?
if( !(p->isio()) )
p->run() ; //RUN
}
// 进行IO
p = blocked.link;
q = &blocked;
if( p )
p->runio() ;
//动态计算就绪队列优先级
p = ready.link;
while( p )
{
(p->pcb->priority) ++ ;
p = p->link;
}
//print proc state
pprint(pcb, pcbsnum);
}
}
/*

//普通的优先调度
/*
* 从就绪队列中取出最优先的进程送到运行队列
* 如果运行结束或要执行IO再重新调度
*/
void generalpriority(pcbs * pcb, int pcbsnum)
{
pcbnode running,ready,blocked;
pcbnode *p,*f,*front;
pcbnode *q;
int i ;
// 将进程表中的进程加到就绪队列中
for( i=0 ; i < pcbsnum ; i ++ )
{
p = new pcbnode ;
p->pcb = pcb+i;
ready.addnode( p ) ;
}
while( ready.link || running.link || blocked.link )
{
//判断将运行队列中的进程是否要io或结束
if( running.link )
{//需要IO?
if( running.link->isio() )
{
blocked.addnode( running.link ) ;
running.link->pcb->pstate = WAIT ;
running.link = 0 ;
}
//运行结束?
else if( running.link->runend() )
{
p = running.link;
running.link = 0;
delete p;
}
}

if( !running.link )
{
//当运行队列为空
//寻找最大的一个优先级
p = ready.link;
q = p;
f = &ready;
front = f;
if( p )
{
int maxpri = p->pcb->priority;
while( p )
{
if( p->pcb->priority > maxpri )
{
maxpri = p->pcb->priority;
front = f;
q = p;
}
f = p ;
p = p->link;
}
}
p = running.link;
if( q )
{
running.addnode(q) ;
ready.deletenode(q, front);
q->pcb->pstate = RUNNING ;
}
}
//将处理完IO的进程送到就绪队列
p = blocked.link;
q = &blocked;
if( p )
{
int r ;
r = p->ioend();
if( r )
{
blocked.deletenode(p, q) ;
ready.addnode(p);
p=q->link ;
}
}
//运行进程
p = running.link;
q = &running;
if( p )
{
//is IO start?
if( !(p->isio()) )
p->run() ; //RUN
}
// 进行IO
p = blocked.link;
q = &blocked;
if( p )
p->runio();
//print proc state
pprint( pcb, pcbsnum ) ;
}
}
void main()
{

pcbs *pcblist;//进程表
cout<<"请输入数据个数："<<endl;
cin>>proc;
int i ;
remove("result.txt");
pcblist = new pcbs[proc]; // 为进程表分配空间
for( i = 0 ; i < proc ; i ++ )
newpcb(pcblist+i, i);//产生进程
pprint(pcblist, proc);
cout<<"************时间片轮转法调度************"<<endl;
poll(pcblist, proc);//轮循法调度
cout<<endl<<endl<<endl;
cout<<"************非抢占调度************"<<endl;
generalpriority(pcblist,proc);//非抢占
cout<<endl<<endl<<endl;
cout<<"************可抢占优先法调度************"<<endl;
priority(pcblist, proc);//可抢占优先法
delete pcblist;//释放进程空间

}

---

沧州市19850304679： 进程调度的模拟 - ？
貂星欣桂： 操作系统课程设计吧建议自己做不然自己会后悔的//设计一个有 N个进程并发运行的进程调度程序,进程调度算法 :最高优先数优先的调度算法 .本实验模拟在单处理机环境下处理机的调度,了解处理机调度的过程.#include ＂iostream.h＂#...

沧州市19850304679： 进程调度算法模拟程序设计 - ？
貂星欣桂： public class PrivilegeProcess { public static void main(String[] args) { MyQueue myqueue = new MyQueue();//声明队列 PCB[] pcb = {new PCB(001,8,1),new PCB(002,7,9),new PCB(003,3,8),new PCB(004,1,7),new PCB(005,7,4)}; PCB para = ...

沧州市19850304679： 如何用c#模拟操作系统的进程调度 - ？
貂星欣桂： System.Diagnostics.Process.GetProcesses(string 机器名);//获取该机器的所有进程 System.Diagnostics.Process.Start(string filename);//运行新的程序 System.Diagnostics.Process.GetProcessesByName(进程名称).Kill();//结束某个进程 在C#里面对应系统进程的操作基本就这些了.在Diagnostics命名空间里面有很多关于系统的操作,你自己在看看MSDN研究一下吧

沧州市19850304679： 进程调度模拟算法,发到邮箱tangyan - bfsu@163.com实验一:进程调度模拟算法【题目名称】 进程调度模拟算法【实验目的】1.掌握进程的描述. 2.熟悉进... - ？
貂星欣桂：[答案] #include ＂stdio.h＂ #include #include #define getpch(type) (type*)malloc(sizeof(type)) #define NULL 0 struct pcb { /* 定义进程控制块PCB */ char name[10]; char state; int super; int ntime; int rtime; struct pcb* link; }*ready=NULL,*p; typedef struct pcb ...

沧州市19850304679： 设计一个按优先数调度算法实现处理器调度的程序.(1) 假定系统有五个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的格式为:进程名指针... - ？
貂星欣桂：[答案] #include //提供atoi()函数 #include //提供clrscr()函数 #define M 10 //字符串大小常量 #define N 3 //进程数常量 #define SLOT 2typedef struct node{ char name[M]; int prio; //优先级 int round...

沧州市19850304679： 用C语言完成进程调度算法的模拟 - ？
貂星欣桂： 多级反馈队列调度算法是一种CPU处理机调度算法,UNIX操作系统采取的便是这种调度算法. 多级反馈队列调度算法即能使高优先级的作业得到响应又能使短作业(进程)迅速完成.(对比一下FCFS与高优先响应比调度算法的缺陷). 多级...

沧州市19850304679： 进程调度策略？
貂星欣桂： 我看别人回答的一个帖子说的还可以,帮你贴过来吧 http://zhidao.baidu.com/question/5661119.html?si=2 首先硬件机制上如何保证操作系统的内核调度进程可以一定的时机可以获得CPU,来进行进程调度.? 通常我们会在软件层次上找答案.其实...

沧州市19850304679： 用java实现一个模拟操作系统内核运行的程序.(1)进程控制:其中包括进程创建与撤销 - ？
貂星欣桂： 在编写Java程序时,有时候需要在Java程序中执行另外一个程序. 1、启动程序Java提供了两种方法用来启动其它程序: (1)使用Runtime的exec()方法 (2)使用ProcessBuilder的start()方法 不管在哪种操作系统下,程序具有基本类...

沧州市19850304679： 进程调度模拟程序 - ？
貂星欣桂： #include<windows.h>#include<iostream.h>#include<string.h>#define P_NUM 3 //进程数#define P_TIME 1//时间片长度#define MIN -9999 enum state //进程状态 { ready, //就绪 run, //执行 wait, //阻塞 finish //完成 }; class Pcb { public: static ...

沧州市19850304679： 假设初始状态为:有n个进程处于就绪状态,有M个进程处于阻塞状态.采用轮转法进程调度算法进行调度(调度 - ？
貂星欣桂： 假设初始状态为:有n个进程处于就绪状态,有M个进程处于阻塞状态.采用轮转法操作系统教程 Linux和Windows操作系统远程互访的方法[9月13日]· 删除Ubuntu