操作系统实验报告

实验一: 进程调度算法

学 生：

学 号：

学 院：

系 别：

专 业：

实验时间：

报告时间：

一、实验内容

按优先数调度算法实现处理器调度。 二、实验目的

在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。

三、实验原理

设计一个按优先数调度算法实现处理器调度的程序。

(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：

其中，进程名——作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。

指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。

要求运行时间——假设进程需要运行的单位时间数。

优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。 状态——可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。

(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。

(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例：

队首标志

K2

K3

K4

K5

(4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：

优先数-1 要求运行时间-1

来模拟进程的一次运行。

提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。

(5) 进程运行一次后，若要求运行时间?0，则再将它加入队列（按优先数大小插入，且

置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。

(6) 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。

(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。

(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。

四、算法流程图

五、源程序及注释

#include<iostream.h>

class PCB //PCB类，包含time、range、state、next指针

{

public:

void In(char *n,int t,int r);

PCB()

{

}

PCB(PCB *p) //复制PCB

{

strcpy(name,p->name);

next=p->next;

time=p->time;

range=p->range;

state=p->state;

}

void Red() //模拟进程运行状态

{

time--;

range--;

if(!time)

state=0;

}

void print() //输出当前PCB内容

{

cout<<name<<"\t"<<time<<"\t"<<range<<"\t"<<state<<endl;

}

char name[10]; //进程名称

PCB *next; //用于链表的指针

int time; //用于记录进程运行时间

int range; //用于记录优先值

int state; //用于判断该进程是否运行结束

};

void PCB::In(char *n,int t,int r) //初始化PDB对象

{

strcpy(name,n);

time=t;

range=r;

next=NULL;

if(t>0)

state=1;

else

state=0;

}

void Pri_Li(PCB *head) //用于输出每一次运行的结果

{

if(head)

{

cout<<"进程队列为：";

for(;head;head=head->next)

cout<<head->name<<",";

}

else

cout<<"进程已全部运行完毕。"<<endl;

cout<<endl;

}

void Grp(PCB *&head,PCB * p,int num)//用于队列的排序，num为当前队列中存在的指针个数

{

int ii=num;

if(p->state) //当该对象为新进程是，插入队列 { if(!num) { head=p; (head)->next=NULL; } else { PCB *tp=head; PCB *tp2=head; for(;num>0;num--) { if(p->range > tp->range && ii==num)//位于头部插入 { p->next=head; head=p; break; } else if(p->range > tp->range)//位于中间插入 { p->next=tp; tp2->next=p; break; } else { tp2=tp; tp=tp->next; } } if(!num && !tp)//位于尾部插入 { tp2->next=p; } } } else //当该对象是已完成进程时，从队列中除去 { PCB *tp=head; int tem=num; for(PCB *tp2=tp;num>0;num--,tp=tp->next) {

if(!strcmp(p->name,tp->name) && tem==num)

{

head=head->next;

break;

}

else if(!strcmp(p->name,tp->name))

{

tp2->next=tp->next;

break;

}

else

tp2=tp;

}

}

}

int Pro(PCB *&p,int sum) //模拟进程运行，并重新排序队列

{

PCB *k,*pk;

int i;

for(;sum;)

{

k=p;

p->Red();

cout<<"此次运行了进程"<<p->name<<"剩余时间"<<p->time<<"权值"<<p->range<<endl;

if(!k->state)

{

Grp(p,k,sum);

sum--;

}

else if(sum==1)

continue;

else

{

pk=k=k->next;

for(i=sum-1;i>0;i--)

{

if(p->range>=k->range && i==sum-1)//ok

{

break;

}

else if(p->range>=k->range)

{

pk->next=p;

p=p->next;

pk->next->next=k;

break;

}

pk=k;

k=k->next;

}

if(!i && !k)

{

pk->next=p;

p=p->next;

pk->next->next=NULL;

}

}

Pri_Li(p);

}

}

int main()

{

int num,sum,t,r;

char n[10];

cout<<"这是一个模拟系统加权进程调度程序"<<endl <<"请输入总的进程数：";

cin>>sum;

PCB *PP[sum];

PCB *head;

for(int i=0;i<sum;i++)

{

PP[i]=new PCB;

cout<<"请输入进程名称、进程运行时间、进程优先数："; cin>>n;

cin>>t;

cin>>r;

PP[i]->In(n,t,r);

num=i;

Grp(head,PP[i],num);

}

Pro(head,sum);

getchar();

return 0;

}

六、打印的程序运行时初值和运行结果

七、实验小结

由于理论课的局限性，让我不能很好地理解操作系统的一些算法思路，虽然只是模仿个别思想而做成的这个小程序，但是我从中不但明白了OS程序员们对进程调度的思想，还更好地加深和理解了指针的内层含义，而不是单单地抽象概念。而且C++的程序联系地实在是太少，这同样是一次很好的锻炼。由于不是很顺手，这次试验总共花了我4个多小时，但是其中的乐趣让我忘了午饭同样每一次debug并一步步排除错误后我感到很欣慰，因为我知道，我又成长了。

 

第二篇：时间片轮转RR进程调度算法(华侨大学)

《操作系统》实验二内实验报告

作者：mo唏

【实验题目】：时间片轮转RR进程调度算法

【实验目的】

通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。

【实验内容】

问题描述：

设计程序模拟进程的时间片轮转RR调度过程。假设有n个进程分别在T₁, … ,T_n时刻到达系统，它们需要的服务时间分别为S₁, … ,S_n。分别利用不同的时间片大小q，采用时间片轮转RR进程调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。

程序要求如下：

1）进程个数n；每个进程的到达时间T₁, … ,T_n和服务时间S₁, … ,S_n；输入时间片大小q。

2）要求时间片轮转法RR调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；

3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；

4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。

[ 源程序 ]

程序结构:

Process.java

package com.RoundRobin;

/**

 * 功能：

 * 定义进程类

 * method:

 * 进程按到达时间排序

 * 进程 RR 时间片轮转法

 * @author Rain

 *

 */

class Process {

       private String name; //进程名

       private int arriveTime;       //到达时间

       private int serviceTime;     //服务时间

       private int finishTime;              //完成时间

       private int roundTime;              //周转时间

       private double weightroundTime;          //带权周转时间

       private double aveweightroundTime;    //     平均带权周转时间

       private double averoundTime; //平均带权周转时间

       private int temp;

       private boolean isAction;

       public Process() {

              name = "";

              arriveTime = 0;

              serviceTime = 0;

              finishTime = 0;

              roundTime = 0;

              weightroundTime = 0;

              averoundTime = 0;

              aveweightroundTime = 0;

              temp = 0;

              isAction = false;

       }

       public void setName(String name) {

              this.name = name;

       }

       public void setArriveTime(int arriveTime) {

              this.arriveTime = arriveTime;

       }

       public void setServiceTime(int serviceTime) {

              this.serviceTime = serviceTime;

              this.temp = serviceTime;

       }

       public void sort(Process[] a) { //对进程进行排序

              for (int j = 1; j < a.length; j++) {

                     Process b = a[j];

                     int temp = a[j].arriveTime;

                     int jj = j - 1;

                     while (jj >= 0) {

                            if (temp < a[jj].arriveTime) {

                                   a[jj + 1] = a[jj];

                                   jj--;

                            } else

                                   break;

                     }

                     a[jj + 1] = b;

              }//for

       }//sort

       /**

        *

        * @param a

        * @param q

        * 时间片轮转算法

        */

       public void RR(Process[] a, int q) {

              Queue aQueue = new Queue();

              aQueue.enqueue(0);

              int j;

              int i = 1;

              int time = a[0].finishTime;

              int count = 0;

              for (int m = 0; m < a.length; m++)

                     count += a[m].serviceTime;

              int temp = -1;

              while (!aQueue.isEmpty()) {

                     a[aQueue.front()].temp = a[aQueue.front()].temp - q;

                     if (a[aQueue.front()].temp >= 0) {

                            System.out.print("第"+time);

                            time = q + time;

                            a[aQueue.front()].finishTime = time;

                            System.out.println("到" + a[aQueue.front()].finishTime + "时间刻"+"进程"

                                          + a[aQueue.front()].name+"在运行");

                     }

                     if (a[aQueue.front()].temp < 0) {

                            System.out.print("第"+time);

                            time = a[aQueue.front()].temp + q + time;

                            a[aQueue.front()].finishTime = time;

                            System.out.println("到" + a[aQueue.front()].finishTime + "时间刻" + "进程"

                                          + a[aQueue.front()].name + "在运行");

                            a[aQueue.front()].temp = 0;

                     }

                     for (j = i; j < a.length; j++) {

                            if (a[j].arriveTime <= time) {

                                   a[j].isAction = true;

                                   aQueue.enqueue(j);

                                i++;

                            }

                            else continue;}   

                     if (a[aQueue.front()].temp== 0){

                               a[aQueue.front()].finishTime = time;

                                   if(aQueue.isEmpty() != true)

                                   {

                                          aQueue.dequeue();

                                   }

                                   }

                            else 

                            {

                                   temp=aQueue.front();

                                   aQueue.dequeue();

                                   aQueue.enqueue(temp);

                                   }

                                   }

              for(int jj=0; jj<a.length; jj++)

              {

                     a[jj].roundTime = a[jj].finishTime - a[jj].arriveTime;

                     a[jj].weightroundTime = (double)a[jj].roundTime / a[jj].serviceTime;

                     a[0].aveweightroundTime += a[jj].weightroundTime;

                     a[0].averoundTime += a[jj].roundTime;

              }

              a[0].aveweightroundTime = a[0].aveweightroundTime / a.length;

              a[0].averoundTime = a[0].averoundTime / a.length;

             

       }//RR

      

              /**

               * 打印结果

               * @param a

               *               

               *  */

       public void print(Process[] a) {

              System.out.println("进程名" + " " + "到达时间" + " " + "服务时间" + " " + "完成时间"

                            + " " + "周转时间" + " " + "带权周转时间");

              //DecimalFormat df = new DecimalFormat("#.00");

              for (int ii = 0; ii < a.length; ii++) {

                     System.out.println("  " + a[ii].name + "      " + a[ii].arriveTime

                                   + "       " + a[ii].serviceTime + "      "

                                   + a[ii].finishTime + "       " + a[ii].roundTime

                                   + "        " + Math.floor( a[ii].weightroundTime*100+0.5 )/100 );

              }

              System.out.println("RR算法的平均周转时间为：" + Math.floor( a[0].averoundTime*100+0.5 )/100 );

              System.out.println("RR算法的平均带权周转时间："

                            + Math.floor( a[0].aveweightroundTime*100 + 0.5 )/100 );

       }//print

}

Queue.java

package com.RoundRobin;

import java.util.NoSuchElementException;

/**

 * 自定义队列来存储进程

 * 通过数组来实现队列

*

*/

class Queue {

       // 字段

       public static int[] data;

       // 队列的元素个数

       protected int size;

       // 队列头

       protected int head;

       // 队列尾

       public static int tail;

       // 无参数构造函数

       public Queue() {

              final int INITIAL_LENGTH = 100;

              data = new int[INITIAL_LENGTH];

              size = 0;

              head = 0;

              tail = -1;

       }

       // 队列元素个数方法

       public int size() {

              return size;

       }

       public boolean isEmpty() {

              return size == 0;

       }

       // 得到队列头元素

       public int front() {

              if (size == 0)

                     throw new NoSuchElementException();

              else return data[head];

       }

       // 进入队列enqueue()方法

       public void enqueue(int obj) {

              // 此时队列已经满

              if (size == data.length) {

                     int[] oldData = data;

                     data = new int[data.length * 2];

                     if(head == 0)

                     System.arraycopy(oldData, head, data, 0, oldData.length - head);

                     if (head > 0)

                            System.arraycopy(oldData, 0, data, head + 1, tail + 1);

                     head = 0;

                     tail = oldData.length - 1;

              }

              tail = (tail + 1) % data.length;

              size++;

              data[tail] = obj;

       }

       // 队列的元素出队

       public int dequeue() {

              if (size == 0)

                     throw new NoSuchElementException();

              int ele = data[head];

              // 循环队列

              //head++;

              head = (head + 1) % data.length;

              size--;

              return ele;

       }

}

RR.java

package com.RoundRobin;

import java.io.*;

import java.util.Scanner;

import com.RoundRobin.Process ;

public class RR {

       /**

        * @param args

        */

       public static void main(String[] args) {

              // TODO Auto-generated method stub

              System.out.println("\n--------模拟操作系统进程调度---- 时间片轮转法-----");

              int i = 0;

              String[] S1 = new String[20];

              try {

                     FileReader aFileReader = new FileReader("data.txt");

                     BufferedReader in = new BufferedReader(aFileReader);

                     String s = null;

                     while ((s = in.readLine()) != null) {

                            S1[i] = s;

                            i++;

                     }

                     aFileReader.close();

                     in.close();

              } catch (IOException ioe) {

                     System.out.println( ioe.getMessage() );

              }

             

              int choice=-1;

              while( true )

              {

                     System.out.println(" 1.开始或继续：");

                     System.out.println(" 0.退出。");

                     System.out.print(" 请输入选择：");

                     try{

                            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

                            String inputString = in.readLine();

                            choice = Integer.valueOf(inputString);

                            if(0 == choice){

                                   //System.exit(0);

                                   break ;

                            }

                            if(1 == choice){ 

                                   Process[] a = new Process[i];

                                   for (int ii = 0; ii < i; ii++) {

                                          a[ii] = new Process();

                                          String[] temp = S1[ii].split(" ");

                                          int j = 0;

                                          a[ii].setName( temp[j] );

                                          a[ii].setArriveTime( Integer.parseInt( temp[j + 1] ) );

                                          a[ii].setServiceTime( Integer.parseInt( temp[j + 2] ) );

                            }

                            Process test = new Process();

                         test.sort(a);

                            System.out.print("请输入时间片的大小：");

                            Scanner reader=new Scanner(System.in);

                            int q = reader.nextInt();

                            if( q <= 0 ){

                                   System.out.println("输入不合法！");

                                   break;

                            }

                            test.RR(a, q);

                            test.print(a);

                                  

                            }

                     }

                     catch (Exception e) {

                            // TODO: handle exception

                            System.out.println("输入有误！");

                     }//catch

                    

              }//while

             

       }//main end

}//class end 

 [ 程序运行效果 ]

接下图↓