rr算法时间片2

1. 进程调度算法

FCFS调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS原则处理。

FCFS调度算法的特点是算法简单，但效率低； 对长作业比较有利，但对短作业不利（相对SJF和高响应比）；

FCFS调度算法有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

​ 短作业优先调度算法是一个非抢占策略，他的原则是下一次选择预计处理时间最短的进程，因此短进程将会越过长作业，跳至队列头。该算法即可用于作业调度，也可用于进程调度。 但是他对长作业不利，不能保证紧迫性作业（进程）被及时处理，作业的长短只是被估算出来的。

缺点：

该算法对长作业不利，SJF调度算法中长作业的周转时间会增加。更严重的是，如果有一长作业进入系统的后备队列，由于调度程序总是优先调度那些 (即使是后进来的）短作业，将导致长作业长期不被调度（“饥饿”现象，注意区分“死锁”。后者是系统环形等待，前者是调度策略问题）。

该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。

由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

SJF调度算法的平均等待时间、平均周转时间最少。

高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。

该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：

响应比 =（等待时间+要求服务时间）/ 要求服务时间,即RR=（w+s）/s=1+w/s，因此 响应比一定是大于等于1的。

短作业与先后次序的兼顾，且不会使长作业长期得不到服务。

响应比计算系统开销，增加系统开销。

高响应比优先调度算法适合批处理系统，主要用于作业调度。

为了实现 RR 调度，我们将就绪队列视为进程的 FIFO 队列。新进程添加到就绪队列的尾部。CPU 调度程序从就绪队列中选择第一个进程，将定时器设置在一个时间片后中断，最后分派这个进程。

接下来，有两种情况可能发生。进程可能只需少于时间片的 CPU 执行。对于这种情况，进程本身会自动释放 CPU。调度程序接着处理就绪队列的下一个进程。否则，如果当前运行进程的 CPU 执行大于一个时间片，那么定时器会中断，进而中断操作系统。然后，进行上下文切换，再将进程加到就绪队列的尾部，接着 CPU 调度程序会选择就绪队列内的下一个进程。

采用 RR 策略的平均等待时间通常较长。

在 RR 调度算法中，没有进程被连续分配超过一个时间片的 CPU（除非它是唯一可运行的进程）。如果进程的 CPU 执行超过一个时间片，那么该进程会被抢占，并被放回到就绪队列。因此， RR调度算法是抢占的。

算法描述

1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。

2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，当且仅当在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。

3、对于同一个队列中的各个进程，按照FCFS分配时间片调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。

4、在最后一个队列QN中的各个进程，按照时间片轮转分配时间片调度。

5、在低优先级的队列中的进程在运行时，又有新到达的作业，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。换而言之，任何时刻，只有当第1~i-1队列全部为空时，才会去执行第i队列的进程（抢占式）。特别说明，当再度运行到当前队列的该进程时，仅分配上次还未完成的时间片，不再分配该队列对应的完整时间片。

2. 处理机调度可以分为

在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。
1.处理机调度的功能
一般情况下，当占用处理机的进程因为某种请求得不到满足二不得不放弃CPU进入等待状态时，或者当时间片到，系统不得不将CPU分配给就绪队列中另以进程的时候，都要引起处理机调度。除此之外，进程正常结束、中断处理等也可能引起处理机的调度。因此，处理机调度是操作系统核心的重要组成部分，它的主要功能如下：
（1）记住进程的状态，如进程名称、指令计数器、程序状态寄存器以及所有通用寄存器等现场信息，将这些信息记录在相应的进程控制块中。
（2）根据一定的算法，决定哪个进程能获得处理机，以及占用多长时间。
（3）收回处理机，即正在执行的进程因为时间片用完或因为某种原因不能再执行的时候，保存该进程的现场，并收回处理机。
处理机调度的功能中，很重要的一项就是根据一定算法，从就绪队列中选出一个进程占用CPU运行。可见，算法是处理机调度的关键。
2.处理机调度的性能准则
处理机调度，有许多不问的调度算法，不同的调度算法具有不同的特性。因此，再介绍算法之前，先介绍衡量一个算法的基本准则。
衡量喝比较调度算法性能优劣主要有一下几个因素：
（1）CPU利用率。CPU是计算机系统中最重要的资源，所以应尽可能使CPU保持忙，使这一资源利用率最高。
（2）吞吐量。CPU运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的昨夜树木来描述的，这就叫吞吐量。
（3）周转时间。指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。
（4）等待时间。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常简单的考察等待时间。
（5）响应时间。指从作业提交到系统作出相应所经过的时间。在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即相应时间。从用户观点看，相应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。
3.处理机调度算法
1）先来先服调度算法（FIFO）
这是最简单的处理机调度算法，其基本思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先费培处理机运行。一旦一个进程占有了处理机，它就一直运行下去，知道该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。
从表面上看，FIFO算法对所有作业都是公平的，并且一个作业的等待时间时可能预先估计的。但实际上这种算法是不利于小作业的，因为当一个大作业先进入就绪队列时，就会使其后的许多小作业等待很长的时间。这对小作业来说，等待时间可能要远远超出它运行的时间。
先来先服算法简单，易于程序实现，但它性能较差，在实际运行的操作系统中，很少单独使用，它常常配合其他调度算法一起使用。
2）时间片轮转调度算法（RR）
时间片轮转调度算法的基本思想是：对就绪队列中的每一进程部分配一个时间片，时间片的长度q一般从10ms-1100ms不等。把就绪队列堪称时一个环状结构，调度程序按时间片长度q轮流电镀就绪队列中的每一进程，使每一进程都有机会获得相同长度的时间占用处理机运行。
时间片轮转调度算法在分时系统中，时一种既简单又有效的调度策略。一个分时系统又许多中断。中断用户在各自的中断设备上同时使用计算机。如果某个中断用户的程序长时间的暂用处理机，那么其他中断用户的请求就不能得到即使相应。一般说来，中断用户提出请求后，能在几秒钟内得到相应也就感到满意了。采用时间片轮转算法，可以使系统即使的相应各中断用户的请求。
时间片轮转调度算法的性能极大的以来于时间片长度q的取值，如果时间片过大。则RR算法就退化为FIFO算法了；反之，如果时间片过小，那么，处理机在各进程之间频繁转接，处理机时间开销变得很大，而提供给用户程序的时间将大大减少。

3. C语言编程实现时间片轮转算法，尽量写得简单易懂，谢谢

#include<stdlib.h>
#define MAX 5 //进程数量
#define RR 2 //时间片大小

/*时间片轮转算法*/

struct pro
{
int num;
int arriveTime;
int burst;
int rt; //记录进程被运行的次数
struct pro *next;
};

int TOTALTIME; //记录所有进程的总时间

//函数声明
struct pro* creatList();
void insert(struct pro *head,struct pro *s);
struct pro* searchByAT(struct pro *head,int AT);
void del(struct pro* p);
int getCount(struct pro *head,int time);
struct pro* searchEnd(struct pro *head);
void move(struct pro *headF,struct pro *headT,int n);

struct pro* creatList() //创建链表，按照进程的到达时间排列,记录所有进程的信息
{
struct pro* head=(struct pro*)malloc(sizeof(struct pro));
head->next=NULL;
struct pro* s;
int i;
TOTALTIME=0;
for(i=0;i<MAX;i++)
{
s=(struct pro*)malloc(sizeof(struct pro));
printf("请输入进程名:\n");
scanf("%d",&(s->num));
printf("请输入到达时间:\n");
scanf("%d",&(s->arriveTime));
printf("请输入运行时间:\n");
scanf("%d",&(s->burst));
TOTALTIME+=s->burst; //计算总时间
s->rt=1; //rt的初始值为1
s->next=NULL;
insert(head,s);
}
return head; //到达队列中的进程按照其到达时间的先后顺序排列
}

void insert(struct pro *head,struct pro *s) //插入节点
{
struct pro *p=searchByAT(head,s->arriveTime);
s->next=p->next;
p->next=s;
return;
}

struct pro* searchByAT(struct pro *head,int AT) //查找第一个到达时间大于等于AT的节点，返回其前一个指针
{
struct pro *p,*q;
p=head;
q=head->next;
while(q!=NULL&&q->arriveTime<=AT)
{
p=q;
q=q->next;
}
return p;
}

void del(struct pro* p) //删除p的下一个节点
{
struct pro *tmp;
tmp=p->next;
p->next=tmp->next;
free(tmp);
return;
}

int getCount(struct pro *head,int time) //察看在time之前到达但未移动到运行队列的进程数量
{
int count=0;
struct pro *s,*t;
s=head;
t=s->next;
while(t!=NULL&&t->arriveTime<=time)
{
s=t;
t=t->next;
count++; //count记录当前时刻到达的进程数
}
return count;
}

struct pro* searchEnd(struct pro *head) //查找并返回循坏队列的尾节点的前一个节点
{
struct pro *p,*q;
p=head;
q=head->next;
while(q->next!=head)
{
p=q;
q=q->next;
}
return p;
}

void move(struct pro *headF,struct pro *headT,int n) //将headF后的n个节点移动到循环队列headT中
{
struct pro *r,*s,*t;
s=headF;
t=s->next;
r=t; //r记录要移动的第一个节点
while(n>1)
{
t=t->next;
n--;
}
s->next=t->next; //以上完成从原队列中摘除相关节点,r,t分别为第一个和最后一个节点
s=searchEnd(headT);
t->next=s->next;
s->next=r;
}

void run(struct pro *head)
{
int time=0; //记录当前时间
int newarrive;//新到达进程数
struct pro *runhead=(struct pro*)malloc(sizeof(struct pro));
runhead->next=runhead; //创建新的循环链表，存放当前就绪队列中的进程
struct pro *p,*q;
p=runhead;
q=p->next; //q记录当前应当运行的进程
while(time<=TOTALTIME)
{
newarrive=getCount(head,time);
if(newarrive>0)
move(head,runhead,newarrive); //将head后的newarrive个节点移动到runhead队列中
if(runhead->next==runhead) //就绪队列中没有进程
time++;
else if(q==runhead)
{
p=q;
q=q->next;
}
else
{
printf("进程名:%d\n",q->num);
printf("到达时间:%d\n",q->arriveTime);
if(q->rt==1)
printf("响应时间:%d\n",time-q->arriveTime);
else
printf("第%d次运行开始时间:%d\n",q->rt,time);
if(q->burst<=RR)
{
time+=q->burst;
printf("第%d次运行结束时间:%d\n",q->rt,time);
printf("周转时间:%d\n",time-q->arriveTime);
printf("************************************\n");
struct pro *tmp=q;
q=q->next;
p->next=q;
free(tmp);
}
else //q->burst>RR
{
time+=RR;
printf("第%d次运行结束时间:%d\n",q->rt,time);
printf("************************************\n");
q->burst-=RR;
q->rt++;
p=q;
q=q->next;
}
}
}
}

void main()
{
struct pro *head=creatList();
printf("当前时间片大小为:%d\n",RR);
run(head);
}

4. 模拟短作业优先算法、时间片轮转算法（RR）和优先数算法的执行情况

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define LENsizeof(struct job)

struct job
{
char name[2];
int cometime;
int runtime;
int priority;
int finishtime;
int state;
struct job *next;
};

void readtxt();
void SJF();
void (structjob *,struct job *);
void RR(int);
void FPF();
void print1(structjob *);
void print2(structjob *);

int n=0;
struct job*head=NULL;
struct job*end=NULL;
FILE*fp=NULL;

void main()
{
if((fp=fopen("JOB1.txt","rb"))==NULL){
printf("can not find file\n");
exit(0);
}
while(!feof(fp)){
readtxt();
}
fclose(fp);

int x,y;
printf("请选择进程调度算法：\n");
printf("1.短作业优先算法 2.时间片轮转算法 3.优先数算法\n");
printf("选择序号：");
scanf("%d",&x);
if((x!=1)&&(x!=2)&&(x!=3))printf("序号不存在！\n");
else{
switch(x){
case 1: SJF(); break;
case 2: {
printf("输入时间片：");
scanf("%d",&y);
RR(y);
break;
}
case 3: FPF(); break;
}
}
}

void readtxt(){
struct job *p1;
p1=(struct job *)malloc(LEN);
fscanf(fp,"%s %d %d%d",(*p1).name,&((*p1).cometime),&((*p1).runtime),&((*p1).priority));
(*p1).state=0;
(*p1).finishtime=0;
if(n==0){
head=p1;
end=p1;
(*end).next=NULL;
n++;
}
else{
(*end).next=p1;
end=p1;
(*end).next=NULL;
n++;
}
}

void SJF(){
struct job *shead,*send,*p1,*p2,*p;
int i,j,curtime;
p1=head;
for(i=0;i<n;i++){
if((*p1).cometime==0) break;
else p1=(*p1).next;
}
p2=(*p1).next;
for(i=i+1;i<n;i++){
if(((*p2).cometime==0)&&((*p2).runtime<(*p1).runtime)){p1=p2;p2=(*p2).next;}
else p2=(*p2).next;
}
(*p1).state=1;
curtime=(*p1).runtime;
(*p1).finishtime=curtime;
p=(struct job *)malloc(LEN);
(p,p1);
shead=p;
send=p;
for(j=0;j<n-1;j++){
p1=head;
for(i=0;i<n;i++){
if(((*p1).cometime<=curtime)&&((*p1).state!=1))break;
else p1=(*p1).next;
}
p2=(*p1).next;
for(i=i+1;i<n;i++){
if(((*p2).cometime<=curtime)&&((*p2).runtime<(*p1).runtime)&&((*p2).state!=1))
{p1=p2;p2=(*p2).next;}
else p2=(*p2).next;
}
(*p1).state=1;
curtime=(*p1).runtime+curtime;
(*p1).finishtime=curtime;
p=(struct job *)malloc(LEN);
(p,p1);
(*send).next=p;
send=p;
}
(*send).next=NULL;
printf("%s\n","短作业优先算法执行结果：");
printf("%s\n","进程执行顺序 周转时间");
print1(shead);
}

void RR(intpertime){
structjob *rhead,*rend,*rrhead,*rrend,*p1,*p2,*p;
int i,curtime=0,m=0,temp1=0,temp2;
while(m!=n){
p1=head;
temp2=temp1;
for(i=0;i<n;i++){
if(((*p1).cometime<=curtime)&&((*p1).runtime!=0)&&((*p1).state!=1)){temp1++;break;}
else p1=(*p1).next;
}
if(p1!=NULL){
p2=(*p1).next;
for(i=i+1;i<n;i++){
if((((*p2).cometime<(*p1).cometime)&&((*p2).runtime!=0)&&((*p2).state!=1))||
(((*p2).cometime==(*p1).cometime)&&((*p2).priority<(*p1).priority)&&((*p2).runtime!=0)&&((*p2).state!=1)))
{p1=p2;p2=(*p2).next;}
else p2=(*p2).next;
}
}

if(temp2!=temp1){
(*p1).state=1;
p=(struct job *)malloc(LEN);
(p,p1);
if(temp1==1) {rhead=p;rend=p;}
else{
(*rend).next=p;
rend=(*rend).next;
}
}
else{
if((temp1==1)&&(m==0)){
curtime+=pertime;
(*rhead).runtime-=pertime;
if((*rhead).runtime<=0){
curtime+=(*rhead).runtime;
(*rhead).runtime=0;
(*rhead).finishtime=curtime;
m++;
temp1--;
}
p=(struct job *)malloc(LEN);
(p,rhead);
rrhead=p;
rrend=p;
}
else{
if(strcmp((*rhead).name,(*rrend).name)==0){
(*rend).next=rhead;
rend=rhead;
rhead=(*rhead).next;
curtime+=pertime;
(*rhead).runtime-=pertime;
if((*rhead).runtime<=0){
curtime+=(*rhead).runtime;
(*rhead).runtime=0;
(*rhead).finishtime=curtime;
m++;
temp1--;
p=(struct job *)malloc(LEN);
(p,rhead);
(*rrend).next=p;
rrend=(*rrend).next;
rhead=(*rhead).next;
}
else{
p=(struct job*)malloc(LEN);
(p,rhead);
(*rrend).next=p;
rrend=(*rrend).next;
(*rend).next=rhead;
rend=rhead;
rhead=(*rhead).next;
(*rend).next=NULL;
}

}
else{
curtime+=pertime;
(*rhead).runtime-=pertime;
if((*rhead).runtime<=0){
curtime+=(*rhead).runtime;
(*rhead).runtime=0;
(*rhead).finishtime=curtime;
m++;
temp1--;
p=(struct job *)malloc(LEN);
(p,rhead);
(*rrend).next=p;
rrend=(*rrend).next;
rhead=(*rhead).next;
}
else{
p=(struct job*)malloc(LEN);
(p,rhead);
(*rrend).next=p;
rrend=(*rrend).next;
(*rend).next=rhead;
rend=rhead;
rhead=(*rhead).next;
(*rend).next=NULL;
}
}
}
}
}
(*rrend).next=NULL;
printf("%s%d%s\n","时间片轮转算法执行结果(时间片",pertime,")：");
print2(rrhead);
}

void FPF(){
structjob *fhead,*fend,*p1,*p2,*p;
int i,j,curtime;
p1=head;
for(i=0;i<n;i++){
if((*p1).cometime==0) break;
else p1=(*p1).next;
}
p2=(*p1).next;
for(i=i+1;i<n;i++){
if(((*p2).cometime==0)&&((*p2).priority<(*p1).priority)){p1=p2;p2=(*p2).next;}
else p2=(*p2).next;
}
(*p1).state=1;
curtime=(*p1).runtime;
(*p1).finishtime=curtime;
p=(struct job *)malloc(LEN);
(p,p1);
fhead=p;
fend=p;
for(j=0;j<n-1;j++){
p1=head;
for(i=0;i<n;i++){
if(((*p1).cometime<=curtime)&&((*p1).state!=1))break;
else p1=(*p1).next;
}
p2=(*p1).next;
for(i=i+1;i<n;i++){
if(((*p2).cometime<=curtime)&&((*p2).priority<(*p1).priority)&&((*p2).state!=1))
{p1=p2;p2=(*p2).next;}
else p2=(*p2).next;
}
(*p1).state=1;
curtime=(*p1).runtime+curtime;
(*p1).finishtime=curtime;
p=(struct job *)malloc(LEN);
(p,p1);
(*fend).next=p;
fend=p;
}
(*fend).next=NULL;
printf("%s\n","最高优先权优先算法执行结果(非抢占方式)：");
printf("%s\n","进程执行顺序 周转时间");
print1(fhead);
}

void (structjob *p,struct job *p1){
strcpy((*p).name,(*p1).name);
(*p).cometime=(*p1).cometime;
(*p).runtime=(*p1).runtime;
(*p).priority=(*p1).priority;
(*p).finishtime=(*p1).finishtime;
(*p).state=(*p1).state;
}

void print1(structjob *p){
while(p!=NULL){
printf("%-14s%d\n",(*p).name,(*p).finishtime-(*p).cometime);
p=(*p).next;
}
}

void print2(structjob *p){
struct job *head;
head=p;
printf("%s\n","进程执行顺序");
while(head!=NULL){
printf("%3s",(*head).name);
head=(*head).next;
}
printf("\n%s\n","进程周转时间");
head=p;
while(head!=NULL){
if(((*head).finishtime-(*head).cometime)>0)
printf("%-4s%d\n",(*head).name,(*head).finishtime-(*head).cometime);
head=(*head).next;
}
}

网上找的，自己看着办

5. 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开始到完成需要多少时间?

6. 在时间片轮转调度中,如果一个进程在一个时间片内就已经运行结束,那剩下的时间片时间怎么利用

如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。结束的进程会从运行队列中清除，剩下的时间片随进程结构的清除而清除，并不影响到其他进程的调度。

时间片由操作系统内核的调度程序分配给每个进程。首先，内核会给每个进程分配相等的初始时间片，然后每个进程轮番地执行相应的时间，当所有进程都处于时间片耗尽的状态时，内核会重新为每个进程计算并分配时间片，如此往复。

在每个进程的task_struct结构中有以下四项：policy、priority、counter、rt_priority。这四项是选择进程的依据。其中，policy是进程的调度策略，用来区分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程(包括实时和普通)的静态优先级。

counter是进程剩余的时间片，它的起始值就是priority的值；由于counter在后面计算一个处于可运行状态的进程值得运行的程度goodness时起重要作用，因此，counter也可以看作是进程的动态优先级。rt_priority是实时进程特有的，用于实时进程间的选择。

(6)rr算法时间片2扩展阅读：

时间片长度的影响：

时间片轮转调度中特别需要关注的是时间片的长度。从一个进程切换到另一个进程是需要一定时间的--保存和装入寄存器值及内存映像，更新各种表格和队列等。

假如进程切换(process switch) - 有时称为上下文切换(context switch)，需要5毫秒，再假设时间片设为20毫秒，则在做完20毫秒有用的工作之后，CPU将花费5毫秒来进行进程切换。CPU时间的20%被浪费在了管理开销上。

为了提高CPU效率，我们可以将时间片设为500毫秒。假设所有其他进程都用足它们的时间片的话，最后一个不幸的进程不得不等待5秒钟才获得运行机会。多数用户无法忍受一条简短命令要5秒钟才能做出响应。同样的问题在一台支持多道程序的个人计算机上也会发生。

结论可以归结如下：时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应变差。

7. 操作系统中关于时间片轮转调度算法！大家帮解答下！

时间片第一级1s，第二级2s，第三级4s...优先级第一级>第二级>第三级...首先A进入第一级执行1s，进入第二级，由于此时B还没有到达，所以A在第二级执行2s，完成，此时是第3s。B第2s已进入第一级，此时回到第一级B执行1s进入第二级，4s的时候c进入第一级，C执行1s进入第二级排在B的后面。此时候为5S，D没有到达，第一级没有进程，所以第二级B执行2S，进入第三级，此时为7S，D已进入第一级，D执行一S，转入第二级排在C后面，8S，E进入第一级，执行一S，进入第二级，排在D后面。第一级没有进程，第二级的C执行2S，进入第三级，D执行2s进入第三级，E执行1S完成，此时是14S。第二级没有进程，由第三级的D开始，执行3S完成，此时是17S，C执行1S完成，此时是18S，D执行2S完成，此时是20S。所以答案是，3，17，18，20，14

8. 考虑一种RR(时间片轮转)调度算法的变种,算法中就绪队列中存放的是指向各个进程控

#include “stdio.h”
#define running 1 // 用running表示进程处于运行态
#define aready 2 // 用aready表示进程处于就绪态
#define blocking 3 // 用blocking表示进程处于阻塞态
#define sometime 5 // 用sometime表示时间片大小
#define n 10 //假定系统允许进程个数为n
struct
{
int name; //进程标识符
int status; //进程状态
int ax,bx,cx,dx ; //进程现场信息，通用寄存器内容
int pc ; //进程现场信息，程序计数器内容
int psw; //进程现场信息，程序状态字内容
int next; //下一个进程控制块的位置
}pcbarea[n]; //模拟进程控制块区域的数组
int PSW, AX,BX,CX,DX , PC ,TIME ; //模拟寄存器
int run; //定义指向正在运行进程的进程控制块的指针
struct
{
int head;
int tail;
}ready; //定义就绪队列的头指针head和尾指针tail
int pfree; //定义指向空闲进程控制块队列的指针

scheling( ) //进程调度函数
{
int i;
if (ready.head==-1) //空闲进程控制块队列为空，退出
{
printf(“无就绪进程\n”);
return;
}
i=ready.head; //就绪队列头指针赋给i
ready.head=pcbarea[ready.head].next; //就绪队列头指针后移
if(ready.head==-1) ready.tail=-1; //就绪队列为空，修正尾指针ready.tail
pcbarea[i].status=running; //修改进程控制块状态
TIME=sometime; //设置相对时钟寄存器
//恢复该进程现场信息
AX=pcbarea[run].ax;
BX=pcbarea[run].bx;
CX=pcbarea[run].cx;
DX=pcbarea[run].dx;
PC=pcbarea[run].pc;
PSW=pcbarea[run].psw;
run=i;
}//进程调度函数结束

create(int x) //进程创建函数
{
int i;
if(pfree==-1) //空闲进程控制块队列为空
{
printf(“无空闲进程控制块，进程创建失败\n”);
return;
}
i=pfree; //取空闲进程控制块队列的第一个
pfree=pcbarea[pfree].next; // pfree后移
//填写该进程控制块的内容
pcbarea[i].name=x;
pcbarea[i].status=aready;
pcbarea[i].ax=x;
pcbarea[i].bx=x;
pcbarea[i].cx=x;
pcbarea[i].dx=x;
pcbarea[i].pc=x;
pcbarea[i].psw=x;
if (ready.head!=-1) //就绪队列不为空时，挂入就绪队列的方式
{
pcbarea[ready.tail].next=i;
ready.tail=i;
pcbarea[ready.tail].next=-1;
}
else //就绪队列为空时，挂入就绪队列的方式
{
ready.head=i;
ready.tail=i;
pcbarea[ready.tail].next=-1;
}
}//进程创建函数结束

main()
{ //系统初始化
int num,i,j;
run=ready.head=ready.tail =-1;
pfree=0;
for(j=0;j<n-1;j++)
pcbarea[j].next=j+1;
pcbarea[n-1].next=-1;
printf(“输入进程编号（避免编号冲突，以负数输入结束，最多可以创建10个进程）：\n”);
scanf(“%d”,num);
while(num>=0)
{
create(num) ;
scanf(“%d”,num) ;
}
scheling(); //进程调度
if(run!=-1)
{
printf(“进程标识符 进程状态 寄存器内容：ax bx cx dx pc psw:\n”);
printf(“%8d%10d%3d%3d%3d%3d%3d%3d\n”, pcbarea[run].name, pcbarea[run].status, pcbarea[run].ax, pcbarea[run].bx, pcbarea[run].cx, pcbarea[run].dx, pcbarea[run].pc, pcbarea[run].psw);
}
}//main()结束
我用的是vc++6.0的，你可以试试，有不懂得在和我交流吧