c进程调度算法

A. 急求 程序代码 c/c++ 操作系统中的 处理机调度算法

#include <iostream>

#include <stdio.h>

#include <string>

//#include <windows.h>

using namespace std;

//hyugtyftydrtdtrdrrtrdrt

struct Node

{

string name;//进程（作业）名称

int arriveTime;//到达时间

int ServerTime;//服务时间

int leftTime;//the left time

Node *link;//指向下一个节点的指针

};

class CProcess

{

public:

CProcess();//构造函数

~CProcess();//析构函数

const CProcess &operator =(const CProcess& p);//重载赋值操作符

void insertNode(string &na,int& at,int& st);//插入新元素（at由小到大）到链表合适的位置

void sort();//按照服务时间由大到小排序

bool isEmpty();//判断是否为空

void destroy();//销毁

int length();//求出链表长度

void print();//打印出元素

void FCFS();//先到先服务

void SJF();//短进程(作业)优先

void RR(int& q);//时间片轮转

void priority();//优先权调度

protected:

Node *first;

Node *last;

};

const CProcess& CProcess::operator=(const CProcess& p)

{

Node *newNode;

Node *Current;

if(this!=&p)//避免自己给自己赋值

{

if(first!=NULL)//如果链表不为空

destroy();

if(p.first==NULL)

{//如果要拷贝的对象为空

this->first = NULL;

this->last = NULL;

}

else

{

Current = p.first;

first= new Node;

first->name=Current->name;//

first->arriveTime=Current->arriveTime;

first->ServerTime=Current->ServerTime;

first->link =NULL;

last =first;

Current = Current->link;

while(Current!=NULL)

{

newNode = new Node;

newNode->name=Current->name;

newNode->arriveTime=Current->arriveTime;

newNode->ServerTime=Current->ServerTime;

newNode->link=NULL;

last->link=newNode;

last=newNode;

Current = Current->link;

}

}

}

return *this;

}

CProcess::CProcess()

{//构造函数

first=NULL;

last=NULL;

}

CProcess::~CProcess()

{

Node *temp;

while(first!=NULL)

{

temp=first;

first=first->link;

delete temp;

}

last=NULL;

}

void CProcess::insertNode(string &na,int& at,int& st)

{//按照到达时间升序排序

Node *Current;

Node *trailCurrent;//指向Current的前一个节点

Node *newNode;

bool found;

newNode = new Node;//建立一个新节点

newNode->name=na;

newNode->arriveTime=at;

newNode->ServerTime=st;

newNode->link=NULL;//

if(first==NULL)//如果第一个节点为空（如果是第一次插入元素）

first=newNode;//将新节点赋给第一个节点

else

{//如果不是第一次

Current =first;

found = false;

while(Current!=NULL && !found)

{

if(Current->arriveTime >= at)

found = true;

else

{

trailCurrent = Current;

Current = Current->link;

}

}

if(Current==first)

{

newNode->link = first;

first = newNode;

}

else

{

trailCurrent->link = newNode;

newNode->link = Current;

}

}

}

int CProcess::length()

{

int count =0;//声明变量，并初始化为0（用来记录长度）

Node *Current;

Current = first;

while(Current!=NULL)//当前节点不为空，记录值自加，一直向后遍历,

{

count++;

Current = Current->link;

}

return count;//返回长度

}

void CProcess::sort()//按照服务时间，升序排列

{//冒泡排序

string sname;

int at;

int st;

Node *Current;//指向当前节点

Node *trailCurrent;//指向当前节点的前一个节点

for(trailCurrent=first->link;trailCurrent!=NULL;trailCurrent=trailCurrent->link)//控制条件有问题

{

for(Current=trailCurrent->link;Current!=NULL;Current=Current->link)//控制条件有问题

{

if(trailCurrent->ServerTime > Current->ServerTime)

{

sname=trailCurrent->name;

at=trailCurrent->arriveTime;

st=trailCurrent->ServerTime;

trailCurrent->name=Current->name;

trailCurrent->arriveTime=Current->arriveTime;

trailCurrent->ServerTime=Current->ServerTime;

Current->name=sname;

Current->arriveTime=at;

Current->ServerTime=st;

}

}

}

}

bool CProcess::isEmpty()//判断是否为空

{

return (first==NULL);//如果第一个节点为空，返回值

}

void CProcess::print()

{

Node *Current;

Current = first->link;//头节点赋给当前节点

while(Current!=NULL)//当前节点不为空，一直向后遍历打印

{

cout<<Current->name<<" ";

cout<<Current->arriveTime<<" ";

cout<<Current->ServerTime<<"\n";

Current = Current->link;

}

}

void CProcess::destroy()

{

Node *temp;//定义一个临时指针变量

while(first!=NULL)

{

temp=first;

first=first->link;

delete temp;

}

last=NULL;

}

void CProcess::FCFS()//先到先服务

{

Node *Current;

int T0=0;//完成时间

int T1=0;//周转时间

Current = first->link;//头节点赋给当前节点

while(Current!=NULL)

{

if(T0 < Current->arriveTime)

{

T0=Current->arriveTime+Current->ServerTime;

T1=T0-Current->arriveTime;

cout<<Current->name<<"\t";//打印出进程名

cout<<T0<<"\t";//打印出完成时间

cout<<T1<<"\n";//打印出周转时间

Current = Current->link;

}

else

{

T0=Current->ServerTime+T0;

T1=T0-Current->arriveTime;//周转时间等于，完成时间 - 到达时间

cout<<Current->name<<"\t";//打印出进程名

cout<<T0<<"\t";//打印出完成时间

cout<<T1<<"\n";//打印出周转时间

Current = Current->link;

}

}

}

void CProcess::SJF()//短进程(作业)优先

{

//首先执行第一个到达的作业

Node *Current;

int T0=0;//完成时间

int T1=0;//周转时间

T0=first->link->ServerTime+T0;

T1=T0-first->link->arriveTime;

cout<<first->link->name<<"\t";

cout<<T0<<"\t";//打印出完成时间

cout<<T1<<"\n";//打印出周转时间

first->link=first->link->link;//删除

//执行剩下的

sort();//对剩下的排序

Current = first->link;//头节点赋给当前节点

while(Current!=NULL)

{

if(T0 < Current->arriveTime)

{

T0=Current->arriveTime+Current->ServerTime;

T1=T0-Current->arriveTime;

cout<<Current->name<<"\t";//打印出进程名

cout<<T0<<"\t";//打印出完成时间

cout<<T1<<"\n";//打印出周转时间

Current = Current->link;

}

else

{

T0=Current->ServerTime+T0;

T1=T0-Current->arriveTime;//周转时间等于，完成时间 - 到达时间

cout<<Current->name<<"\t";//打印出进程名

cout<<T0<<"\t";//打印出完成时间

cout<<T1<<"\n";//打印出周转时间

Current = Current->link;

}

}

}

void CProcess::RR(int& q)//时间片轮转

{

cout<<"时间片轮转操作完成！\n";

}

void CProcess::priority()//优先权调度

{

cout<<"优先权操作完成！\n";

}

void main()

{

CProcess p0,p1,p2,p3,p4;

int at,st;

string na;

int judge=1;//控制退出程序

int choice;//控制选择操作

while(judge)

{

cout<<"********************************************************\n";

cout<<"****** 说明：本程序适用于单道进程（作业） ******\n";

cout<<"******** 请选择您的操作 ***************\n";

cout<<"*********输入相应的数字，按下（Enter）键！**************\n";

cout<<"************* 5.录入信息 ************\n";

cout<<"************* 1.先到先服务 ************\n";

cout<<"************* 2.短进程（作业）优先 ************\n";

cout<<"************* 3.时间片轮转 ************\n";

cout<<"************* 4.优先权(静态)调度 ************\n";

cout<<"************* 0.退出程序 ************\n";

cout<<"********************************************************\n";

cin>>choice;

switch(choice)

{

case 0:

judge=0;

break;

case 5:

cout<<"请输入信息以“end”结束输入！\n";

cout<<"进程名 到达时间 服务时间"<<endl;

while(na.compare("end"))//如果相等则会返回0

{

p0.insertNode(na,at,st);

cin>>na>>at>>st;

}

cout<<"录入成功，目前的信息为：\n";

cout<<"进程名 到达时间 服务时间"<<endl;

p0.print();

break;

case 1://先到先服务

p1=p0;//拷贝一份

if(p1.isEmpty())

{

cout<<"请先录入信息\n";

break;

}

else

{

cout<<"先到先服务\n";

cout<<"进程名 完成时间 周转时间\n";

p1.FCFS();

break;

}

case 2://短作业优先

p2=p0;//拷贝一份

//p2.sort();

//p2.print();

if(p2.isEmpty())

{

cout<<"请先录入信息\n";

break;

}

else

{

cout<<"短作业优先\n";

cout<<"进程名 完成时间 周转时间\n";

p2.SJF();

break;

}

case 3://时间片轮转

p3=p0;//拷贝一份

int q;

if(p3.isEmpty())

{

cout<<"请先录入信息\n";

break;

}

else

{

cout<<"请输入时间片大小";

cin>>q;

cout<<"时间片轮转\n";

cout<<"进程名 完成时间 周转时间\n";

p3.RR(q);

break;

}

case 4://优先权

p4=p0;//拷贝一份

if(p4.isEmpty())

{

cout<<"请先录入信息\n";

break;

}

else

{

cout<<"时间片轮转\n";

cout<<"进程名 完成时间 周转时间\n";

p4.priority();

break;

}

default:

cout<<"请选择目录中的选项！\n";

break;

}

}

return;

}

B. 2018-06-09

一、常见的批处理作业调度算法

1.先来先服务调度算法（FCFS）:就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满意，因为短作业等待处理的时间可能比实际运行时间长得多。

2.短作业优先调度算法(SPF): 就是优先调度并处理短作业，所谓短是指作业的运行时间短。而在作业未投入运行时，并不能知道它实际的运行时间的长短，因此需要用户在提交作业时同时提交作业运行时间的估计值。

3.最高响应比优先算法(HRN)：FCFS可能造成短作业用户不满，SPF可能使得长作业用户不满，于是提出HRN，选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。

4. 基于优先数调度算法(HPF)：每一个作业规定一个表示该作业优先级别的整数，当需要将新的作业由输入井调入内存处理时，优先选择优先数最高的作业。

5.均衡调度算法，即多级队列调度算法

基本概念：

  作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)

  作业平均周转时间(T)＝周转时间/作业个数

  作业带权周转时间（Wi）＝周转时间/运行时间

  响应比＝（等待时间＋运行时间）/运行时间

二、进程调度算法

1.先进先出算法(FIFO)：按照进程进入就绪队列的先后次序来选择。即每当进入进程调度，总是把就绪队列的队首进程投入运行。

2. 时间片轮转算法(RR)：分时系统的一种调度算法。轮转的基本思想是，将CPU的处理时间划分成一个个的时间片，就绪队列中的进程轮流运行一个时间片。当时间片结束时，就强迫进程让出CPU，该进程进入就绪队列，等待下一次调度，同时，进程调度又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。

3. 最高优先级算法(HPF)：进程调度每次将处理机分配给具有最高优先级的就绪进程。最高优先级算法可与不同的CPU方式结合形成可抢占式最高优先级算法和不可抢占式最高优先级算法。

4. 多级队列反馈法：几种调度算法的结合形式多级队列方式。

三、空闲分区分配算法

\1. 首先适应算法：当接到内存申请时，查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配。此算法简单，可以快速做出分配决定。

2. 最佳适应算法：当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲区，将其进行分割并分配。此算法最节约空间，因为它尽量不分割到大的空闲区，其缺点是可能会形成很多很小的空闲分区，称为“碎片”。

3. 最坏适应算法：当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。该算法的优点是避免形成碎片，而缺点是分割了大的空闲区后，在遇到较大的程序申请内存时，无法满足的可能性较大。

四、虚拟页式存储管理中的页面置换算法

1.理想页面置换算法(OPT)：这是一种理想的算法，在实际中不可能实现。该算法的思想是：发生缺页时，选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

2.先进先出页面置换算法(FIFO)：选择最先进入内存的页面予以淘汰。

3. 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。

4.最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。

三、磁盘调度

1.先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置

2.最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题

3.扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。

4.循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。

对一个进程来说,一个重要的指标是它执行所需要的时间. 从进程提交到进程完成的时间间隔为周转时间.也就是等待进入内存的时间,在就绪队列中等待的时间,在 CPU中执行的时间和I/O操作的时间的总和.

例1.设一个系统中有5个进程，它们的到达时间和服务时间如下，A的到达时间为0，服务时间为3；B的到达时间为2，服务时间为6；C的到达时间为4，服务时间为4；D的到达时间为6，服务时间为5；E的 到达时间为8，服务时间为2，忽略1/0以及其他开销时间，若分别按先来先服务（fFCFS）进行CPU调度，其平均周转时间为？

10.2

6.4

8.6

4.5

先来先服务调度算法

进程名  到达时间 服务时间  开始执行时间  完成时间  周转时间

A              0              3                0                3                3

B              2              6                3                9                7

C              4              4                9                13              9

D              6              5                13              18              12

E              8              2                18              20              12

周转时间 = 完成时间 - 到达时间

平均周转时间 = 所有进程周转时间 / 进程数 = （3+7+9+12+12）/ 5 = 8.6

单道批处理系统中有4个作业，J1的提交时间8.0，运行时间为2.0；J2的提交时间8.6，运行时间为0.6；J3提交时间8.8，运行时间为0.2；J4的提交时间9.0，运行时间为0.5。在采用响应比高者优先调度算法时，其平均周转时间为T为（）小时？

2.5

1.8

1.975

2.675

周转时间=作业完成时间-作业提交时间

响应比=（作业等待时间+作业执行时间）/作业执行时间

当提交J1时，只有J1作业，执行J1，J1的周转时间为2，此时时间为10.

J2、J3、J4提交时，由于正在执行J1，因此等待。

当J1执行完毕（此时时间为10），J2、J3、J4的等待时间分别为：1.4,1.2,1，

其响应比分别为：1.4/0.6+1=3.33    1.2/0.2+1=7      1/0.5+1=3，因此执行J3，J3的周转时间为1.2+0.2=1.4

当J3执行完毕（此时时间为10.2），J2和J4的等待时间分别为1.6,1.2，

其响应比分别为：1.6/0.6+1=3.66      1.2/0.5+1=3.4，因此执行J2，J2的周转时间为1.6+0.6=2.2

执行J2完毕后时间为10.8，接下来执行J4，执行完后时时间为11.3，J4的周转时间为2.3

于是平均周转时间为（2+1.4+2.2+2.3）/4=1.975

如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。

例3、

现有4个同时到达的作业J1,J2,J3和J4,它们的执行时间分别是3小时,5小时,7小时,9小时系统按单道方式运行且采用短作业优先算法,则平均周转时间是()小时

12.5

24

19

6

作业到达时间执行时间开始时间完成时间周转时间

J103033

J20 5388

J30781515

J409152424

平均周转时间（3+8+15+24）/4=12.5 

有4个进程A,B,C,D,设它们依次进入就绪队列，因相差时间很短可视为同时到达。4个进程按轮转法分别运行11,7,2,和4个时间单位，设时间片为1。四个进程的平均周转时间为 （）？

15.25

16.25

16.75

17.25

17.75

18.25

A:1  4  4  3  3  2  2  2  1  1  1  共24

B:2  4  4  3  3  2  2                  共20

C:3  4                                      共7

D:4  4  3  3                              共14

字母后面的数字为等待的时间加运行时间

平均周转时间为（24+20+7+14）/4=16.25

例5、假设系统按单值方式运行且采用最短作业优先算法，有J1,J2,J3,J4共4个作业同时到达，则以下哪几种情况下的平均周转时间为10分钟?

执行时间J1:1分钟 J2:5分钟 J3:9分钟 J4:13分钟

执行时间J1:1分钟 J2:4分钟 J3:7分钟 J4:10分钟

执行时间J1:2分钟 J2:4分钟 J3:6分钟 J4:8分钟

执行时间J1:3分钟 J2:6分钟 J3:9分钟 J4:12分钟

首先，短作业优先则短时间的作业利用资源，其余的作业等待

根据平均周转时间概念，将所有作业"等待时间"加上"运行时间"除以"作业数量"即可得到平均周转时间

A： (J1执行1分钟 + J2等待1分钟 + J2执行5分钟 + J3等待6分钟 + J3执行9分钟 + J4等待15分钟 + J4执行13分钟) / 4  = 50/4 = 12.5

B：  (J1执行1分钟 + J2等待1分钟 + J2执行4分钟 + J3等待5分钟 + J3执行7分钟 + J4等待12分钟 + J4执行10分钟) / 4  = 40/4 = 10

C： (J1执行2分钟 + J2等待2分钟 + J2执行4分钟 + J3等待6分钟 + J3执行6分钟 + J4等待12分钟 + J4执行8分钟) / 4    = 40/4 = 10

D：  (J1执行3分钟 + J2等待3分钟 + J2执行6分钟 + J3等待9分钟 + J3执行9分钟 + J4等待18分钟 + J4执行12分钟) / 4  = 50/4 = 12.5

例6、假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。  表1 进程到达和需要服务时间  进程    到达时间    服务时间  A          0            3  B          2            6  C          4            4  D          6            5  E          8            2

表2 进程的完成时间和周转时间

                  进程                  A      B        C      D      E        平均

  FCFS          完成时间      3      9      13      18      20 

                周转时间            3      7        9      12      12      8.6

            带权周转时间      1.00 1.17  2.25  2.40    6.00      2.56

  SPF(非抢占)  完成时间    3      9      15      20      11 

                周转时间            3      7      11      14      3        7.6

            带权周转时间      1.00  1.17  1.75    2.80    1.50    1.84

  SPF(抢占)    完成时间    3      15      8      20      10 

                周转时间            3      13      4      14      2        7.2

            带权周转时间      1.00  2.16  1.00  2.80  1.00    1.59

例7、假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：    作业  进入系统时间    估计运行时间/分钟      1            8:00                40      2            8:20                30      3            8:30                12      4            9:00                18

      5            9:10                5

如果应用先来先服务和应用最短作业优先的作业调度算法，试将下面表格填写完整。

(1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。

    作业  进入系统时间  估计运行时间/分钟  开始时间  结束时间  周转时间/分钟

    1        8:00            40            8：00    8：40        40

    2        8:20            30            8：40    9：10        50

    3        8:30            12            9：10    9：22        52

    4        9:00            18            9：22    9：40        40

    5        9:10            5              9：40    9：45        35

作业平均周转时间T= 43.4  217

2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。    作业  进入系统时间  估计运行时间/分钟  开始时间  结束时间  周转时间/分钟    1        8:00            40              8：00    8：40          40    2        8:20            30              8：52    9：22          62    3        8:30            12              8：40    8：52          22    4        9:00            18              9：27    9：45          45    5        9:10            5              9：22    9：27          17作业平均周转时间T= 37.2  186

CPU和两台输入/输出设备(I1,I2)多道程序设计环境下,同时有三个作业J1,J2,J3进行,这三个作业

使用CPU和输入/输出设备的顺序和时间如下所示:

J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)

J2:I1(25ms);CPU(30ms);I2(35ms)

J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);

假定CPU,I1,I2都能并行工作,J1的优先级最高,J2次之,J3优先级最低,优先级高的作业可以抢占优先级低的作业的CPU,但不能抢占I1,I2,作业从J3开始到完成需要多少时间?

C. ）用C语言（或其它语言，如Java）编程实现对N个进程采用某种进程调度算法（如动态优先权调度

公众：类PrivilegeProcess {
公共静态无效的主要（字串[] args）{

MyQueue的MyQueue的新MyQueue的（）;/ /声明队列

印刷电路板[PCB = {新的PCB（001 ，8,1），新的PCB（002,7,9），新的PCB（003,3,8），新的PCB（004,1,7），新的PCB（005,7,4）};
> PCB段=新的PCB（）;

（INT I = 0; <pcb.length; + +）{/ /初始化先进行排序，选择排序这里使用的是高优先级的一线队

（J =我; <pcb.length; J + +）{

（PCB [I]。特权<PCB [J]。特权）{

段= PCB [1];

PCB [I] = PCB [J];

PCB [J] =段;

}

}

}

体系。通过out.println（“入队后第一时间的进程的顺序：”）;

（INT I = 0; <pcb.length; + +）{

的System.out调用println（第一次入队＃程序名称：“+ PCB [我]。名称+ totaltime：”+ PCB [I]。totaltime +“的”特权“+ PCB [我]。特权）; }

（）;

myqueue.start（PCB）;

}

}

类MyQueue的{

INT指数= 0;

PCB [] PC =新的PCB [5];

PCB [] PC1 =新的PCB [4];

PCB温度=新的PCB（） BR />公共无效排队（PCB工艺）{/ /排队算法

（指数== 5）{

（“出界！”）;

返回

}

PC [索引] =进程;

指数+ +;

}

公共：PCB DEQUEUE（）{/ /出队算法（索引== 0）

返回空;

（INT I = 0; <pc1.length; + +）{

PC1 [I] = PC [ +1];

}

指数 -

温度= PC [0];

（INT I = 0; <pc1.length; + +）{ BR /> PC [I] = PC1 [I];

}

回报条件;

}

公共无效启动（PCB [] PC）{/ /进程表算法

（PC [0]。isNotFinish ==真| | PC [1 isNotFinish ==真| | PC [2 isNotFinish ==真| | PC [3]。时isNotFinish ==真| | PC [4]。isNotFinish ==）{

/ / *注：| |运算符都是假的，所有的表达式结果为假，否则真

（INT I = 0; <PC长度; + +）{

PC [I]。运行（这一点）; />} 的System.out.println（）;

（INT I = 0; <pc.length; + +）{/ /处理每个运行一次运行的时间片的长度重新排序优先一旦

（J =我; <pc.length; J + +）{

如果（PC [I]特权<PC [J]。特权）{

温度= PC [I];

PC [I] = PC [J];

PC [J] =温度;

}

}

}

}

}

}

类PCB {/ /声明过程级

和int名，totaltime ，运行时特权;

布尔isNotFinish的;

公众PCB（）{

}

公开PCB（名称，诠释totaltime特权）{

this.name =的名称;/ /进程名

this.totaltime = totaltime ;/ /

this.privilege =特权;/ /总时间优先 this.runtime = 2 ;/ /时间片值是2

this.isNotFinish =真;/ /是否执行完成

（“初始值：程序名称：”+名+“totaltime：”+ totaltime +“特权”+特权）;

System.out的。调用println（）;

}

MyQueue的MQ公共无效的run（）{/ /处理的基础上实施的时间片算法

（totalTime> 1）{ totaltime =运行;/ /总时间大于1，总时间=总时间 - 时间片

特权 -

（“程序名称：”+姓名+“ remaintime：“+ +”特权“+特权）; totaltime

的} else if（totaltime == 1）{

totaltime - ;/ /总时间为1时，执行时间为1
>特权 -

（“程序名称：”+姓名+“remaintime：”+ totaltime +“特权”+特权）;

}其他{

isNotFinish =假;/ / 0，将isNotFinish标志设置为假

}

如果（isNotFinish ==真）{br mq.deQueue（）;

mq.enQueue（本）;

}

}
}

D. 用C语言编写并调试一个模拟的进程调度程序，采用“简单时间片轮转法”调度算法对五个进程进行调度。

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

struct PCB {
char NAME[10]; /*进程名*/
int ROUND; /*进程轮转时间片*/
int REACHTIME; /*进程到达时间*/
int CPUTIME; /*进程占用CPU时间*/
int COUNT; /*计数器*/
int NEEDTIME; /*进程完成还要的CPU时间*/
char STATE; /*进程的状态*/
struct PCB *NEXT; /*链指针*/
};

struct LINK { /*PCB的链结构*/
struct PCB *RUN; /*当前运行进程指针*/
struct PCB *READY; /*就绪队列头指针*/
struct PCB *TAIL; /*就绪队列尾指针*/
struct PCB *FINISH; /*完成队列头指针*/
};

void INIT(LINK *); /*对PCB的链结构初始化*/
void INSERT(LINK *); /*将执行了一个单位时间片数且还未完成的进程的PCB插到就绪队列的队尾*/
void FIRSTIN(LINK *); /*将就绪队列中的第一个进程投入运行*/
void PRINT(LINK *); /*打印每执行一个时间片后的所有进程的状态*/
void PR(PCB *); /*打印一个进程的状态*/
int CREATE(LINK *,int); /*创建新的进程*/
void ROUNDSCH(LINK *); /*按时间片轮转法调度进程*/

void main() {
LINK pcbs;
int i;
INIT(&pcbs);
i=0;
printf("创建5个进程\n\n");
while(i<5) {
if(CREATE(&pcbs,i+1)==1) {
printf("进程已创建\n\n");
i++;
}
else
printf("进程创建失败\n\n");
}
FIRSTIN(&pcbs);
ROUNDSCH(&pcbs);
}

void ROUNDSCH(LINK *p) {
PCB *pcb;
while(p->RUN!=NULL) {
pcb=(PCB *)malloc(sizeof(PCB));
strcpy(pcb->NAME,p->RUN->NAME);
pcb->ROUND=p->RUN->ROUND;
pcb->REACHTIME=p->RUN->REACHTIME;
pcb->CPUTIME=p->RUN->CPUTIME;
pcb->COUNT=p->RUN->COUNT;
pcb->NEEDTIME=p->RUN->NEEDTIME;
pcb->STATE=p->RUN->STATE;
pcb->NEXT=p->RUN->NEXT;
pcb->CPUTIME++;
pcb->NEEDTIME--;
pcb->COUNT++;
if(pcb->NEEDTIME==0) {
pcb->NEXT=p->FINISH->NEXT;
p->FINISH->NEXT=pcb;
pcb->STATE='F';
p->RUN=NULL;
if(p->READY!=p->TAIL)
FIRSTIN(p);
}
else {
p->RUN=pcb;
if(pcb->COUNT==pcb->ROUND) {
pcb->COUNT=0;
if(p->READY!=p->TAIL) {
pcb->STATE='W';
INSERT(p);
FIRSTIN(p);
}
}
}
PRINT(p);
}
}

void INIT(LINK *p) {
p->RUN=NULL;
p->TAIL=p->READY=(PCB *)malloc(sizeof(PCB));
p->READY->NEXT=NULL;
p->FINISH=(PCB *)malloc(sizeof(PCB));
p->FINISH->NEXT=NULL;
}

int CREATE(LINK *p,int n) {
PCB *pcb,*q;
pcb=(PCB *)malloc(sizeof(PCB));
flushall();
printf("请输入第%d个进程的名称：\n",n);
gets(pcb->NAME);
printf("请输入第%d个进程的轮转时间片数：\n",n);
scanf("%d",&(pcb->ROUND));
printf("请输入第%d个进程的到达时间：\n",n);
scanf("%d",&(pcb->REACHTIME));
pcb->CPUTIME=0;
pcb->COUNT=0;
printf("请输入第%d个进程需运行的时间片数：\n",n);
scanf("%d",&(pcb->NEEDTIME));
pcb->STATE='W';
pcb->NEXT=NULL;
if(strcmp(pcb->NAME,"")==0||pcb->ROUND<=0||pcb->NEEDTIME<=0) /*输入错误*/
return 0;
q=p->READY;
while(q->NEXT!=NULL&&q->NEXT->REACHTIME<=pcb->REACHTIME)
q=q->NEXT;
pcb->NEXT=q->NEXT;
q->NEXT=pcb;
if(pcb->NEXT==NULL)
p->TAIL=pcb;
return 1;
}

void FIRSTIN(LINK *p) {
PCB *q;
q=p->READY->NEXT;
p->READY->NEXT=q->NEXT;
q->NEXT=NULL;
if(p->READY->NEXT==NULL)
p->TAIL=p->READY;
q->STATE='R';
p->RUN=q;
}

void INSERT(LINK *p) {
PCB *pcb;
pcb=(PCB *)malloc(sizeof(PCB));
strcpy(pcb->NAME,p->RUN->NAME);
pcb->ROUND=p->RUN->ROUND;
pcb->REACHTIME=p->RUN->REACHTIME;
pcb->CPUTIME=p->RUN->CPUTIME;
pcb->COUNT=p->RUN->COUNT;
pcb->NEEDTIME=p->RUN->NEEDTIME;
pcb->STATE=p->RUN->STATE;
pcb->NEXT=p->RUN->NEXT;
p->TAIL->NEXT=pcb;
p->TAIL=pcb;
p->RUN=NULL;
pcb->STATE='W';
}

void PRINT(LINK *p) {
PCB *pcb;
printf("执行一个时间片后的所有进程的状态：\n\n");
if(p->RUN!=NULL)
PR(p->RUN);
if(p->READY!=p->TAIL) {
pcb=p->READY->NEXT;
while(pcb!=NULL) {
PR(pcb);
pcb=pcb->NEXT;
}
}
pcb=p->FINISH->NEXT;
while(pcb!=NULL) {
PR(pcb);
pcb=pcb->NEXT;
}
}

void PR(PCB *p) {
printf("进程名：%s\n",p->NAME);
printf("进程轮转时间片：%d\n",p->ROUND);
printf("进程到达时间：%d\n",p->REACHTIME);
printf("进程占用CPU时间：%d\n",p->CPUTIME);
printf("计数器：%d\n",p->COUNT);
printf("进程完成还要的CPU时间：%d\n",p->NEEDTIME);
printf("进程的状态：%c\n\n",p->STATE);
}

E. c语言，单处理机进程调度，时间片轮转

//参考一下
#include<stdio.h>
#include<stdlib.h>

#defineCPU_TIME50//CPU时间片

structmission//单个任务的结构体
{
charname[20];//任务名称
intfinished;//任务是否已完成,完成为1,未完成为0
intneed_time;//任务总共需要的CPU时间
intfinished_time;//任务已经执行的CPU时间
};

intwork_mission=5;//未完成任务计数

structmissions[5]={{"one",0,100,0},//假设有5个任务
{"two",0,380,0},
{"three",0,200,0},
{"four",0,440,0},
{"five",0,230,0}
};

intmove_mission(intflag)//任务排序
{
if(work_mission==0)
{
return1;
}
structmissiontemp;
temp=s[0];
inti;

if(flag==1)
{
for(i=1;i<work_mission+1;i++)
{
s[i-1]=s[i];
}
s[work_mission]=temp;
}
else
{
for(i=1;i<work_mission;i++)
{
s[i-1]=s[i];
}
s[work_mission-1]=temp;
}


return0;
}
intmain(intargc,char*argv[]){
structmissiontemp;
intfinished=0;
intcpu_time_count=0;
while(finished==0)
{
printf(" 第%d个CPU时间片即将执行 ",cpu_time_count/CPU_TIME+1);
printf(" 当前任务队列(即将执行下面第一行任务,执行后将任务移到队列末尾):CPU已用时:%d ",cpu_time_count);
inti;
for(i=0;i<5;i++)
{
printf("任务名称:%5s是否已完成:%d需时间:%03d已执行时间:%03d已完成:%03.2f%% ",s[i].name,s[i].finished,s[i].need_time,s[i].finished_time,100*((float)s[i].finished_time/(float)s[i].need_time));
}
if(s[0].finished==1)
{
finished=1;
break;
}
if((s[0].need_time-s[0].finished_time)>CPU_TIME)
{
s[0].finished_time+=CPU_TIME;
cpu_time_count+=CPU_TIME;
finished=move_mission(0);
}
else
{
cpu_time_count+=(s[0].need_time-s[0].finished_time);
s[0].finished_time=s[0].need_time;
s[0].finished=1;
work_mission-=1;
finished=move_mission(1);
}
}
printf(" 当前任务队列(全部执行完毕):CPU用时:%d ",cpu_time_count);
inti;
for(i=0;i<5;i++)
{
printf("任务名称:%5s是否已完成:%d需时间:%03d已执行时间:%03d已完成:%03.2f%% ",s[i].name,s[i].finished,s[i].need_time,s[i].finished_time,100*((float)s[i].finished_time/(float)s[i].need_time));
}
printf(" 总共用了CPU时间:%d",cpu_time_count);
return0;
}

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

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

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

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

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

1. 实时CPU调度算法分类

各种实时操作系统的实时调度算法可以分为如下三种类别[Wang99][Gopalan01]：基于优先级的调度算法（Priority-driven scheling-PD）、基于CPU使用比例的共享式的调度算法（Share-driven scheling-SD）、以及基于时间的进程调度算法（Time-driven scheling-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：作业在运行期间所要使用的资源的多少；

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