南通大学

操作系统课程设计报告

学院：计算机科学与技术学院

班级：

学号

姓名：

指导老师

课设时间：2013.7.3~2013.7.5

一．   实验目的

操作系统是计算机系统的一个重要系统软件。我们在本课程的实验过程中，了解实际操作系统的工作过程，在实践中加深对操作系统原理的理解，在模拟计算机操作系统的基础上，利用代码实现操作系统的处理机调度算法，页面替换算法，磁盘移动臂算法，银行家算法最终的集成，在界面上进行各算法的实现。

二．   概要设计

在多道程序运行环境下，进程数目一般多于处理机数目，使得进程要通过竞争来使用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行，分配处理机的任务是由进程调度程序完成的。一个进程被创建后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。进程调度的算法有多种，常用的有优先级调度算法、先来先服务算法、时间片轮转算法。这里我们主要实现的是先来先服务算法和优先级调度算法。

1.     处理机调度算法

（1）       设计一个结构体，用于抽象进程的各种属性，其中包括进程标志符，进程优先级，cpu时间统计，运行所需时间，进程状态。

（2）       再设计一个结构体，用于模拟就绪队列，其具体方法采用链表形式。

（3）       对于先到先服务算法，判断就绪队列中每个进程的进程号，根据进程号的顺序依次给进程分配CPU，直到所有进程执行完毕为止

（4）       对于优先度调度算法，首先根据所有进程的有限度，依次按照其优先度的大小按照降序排序的方式依次插入就绪队列，每当一个进程获得CPU并执行时，优先级降低2，每运行一次 CPU时间增加4，当所获得的CPU时间大于或者等于其所需的CPU时间时，进程执行完毕，否则变换就绪队列中进程顺序，使之保持进程优先级按降序排序。

（5）       每个进程获得CPU时间并执行完毕之后，打印出进程队列中的信息，以便查看就绪队列中的进程信息。

2.页面替换算法

(1)在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。 

(2) 一个好的页面置换算法，应该有较低的页面更换频率。  

假设分给一作业的物理块数为3 ，页面数为20个。 页面号为(20个)： 

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1  

先进先出(FIFO)置换算法的思路

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。  

最近久未使用(LRU)置换算法的思路

最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。 

最佳（OPT）置换算法的思路

其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，

采用最佳算法，通常可保证获得最低的缺页率。

3.移动臂算法

磁盘调度的目标是使磁盘的平均寻道时间最少。也正因为这样，我们有必要对各算法进行模拟，进而比较、分析、了解。

本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对最短寻道时间优先（SSTF）、先来先服务（FCFS）等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。

4.银行家算法

当某个进程提出资源请求时，假定先分配给它，之后调用系统安全性检查算法，进行系统安全性检查。若系统安全，假分配变为真分配。否则作废假分配，让进程等待

（1）如果Requesti＜or =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。

（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：

   Available=Available-Request[i];

    Allocation=Allocation+Request;

Need=Need-Request;

(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

三.详细设计

1处理机调度

进程的数据结构如下：

struct PCB

   {char name[20]; //进程名

    int arrivetime; //进程到达时间

    int runtime;    //估计运行时间

    int grade;      //进程的优先级（优先数越低，优先级越高）

    PCB *next;      //链表指针

};

主函数main()调用各个子函数实现本程序的功能如：数据初始化input（），输出此刻的进程状态，时间片轮转法process-RR（）。

子函数的说明如下：

初始化就绪队列

void process::input(int l)//建立进程的函数

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

     {PCB *n=new PCB;

      cout<<"\n输入第"<<i+1<<"个进程名:";

      cin>>n->name;

      cout<<"       到达时间:";

      cin>>n->arrivetime;

      cout<<"       运行时间:";

      cin>>n->runtime;

      if(l==3) cout<<"                 优先级:",cin>>n->grade;

      else n->grade=0;

      head=Sort_Insert_arrivetime(head,n);

      }

}

输出运行中的进程信息

先来先服务调度算法

void process::process_FCFS()//先来先服务算法

{   int start_time,k=0;

    while(head)

        {while(current<head->arrivetime) current++;

         run=head;

         if(!k)

            {cout<<"当时间为"<<current;

             start_time=head->arrivetime;}

         else start_time=current;

         cout<<","<<run->name<<"进程开始"<<endl;

         while(current<start_time+run->runtime) current++;

         cout<<"当时间为"<<current<<","<<run->name<<"进程结束";

         run->runtime=0;

         head=head->next;

         Delete_process();

         if(head&&current>=head->arrivetime) k=1;

         else {cout<<'\n';k=0;}

         }

输出运行中的进程信息

时间片轮转法

void process::process_RR()//时间片轮算法

{   for(int k=0;head||run;k=0)

        {if(!run&&head)

            {while(current<head->arrivetime) current++;

             Set_Run();

             cout<<"当时间为"<<current<<","<<run->name<<"进程开始"<<endl;

             }

         run->runtime--,current++;

         if(run->runtime==0)

            {cout<<"当时间为"<<current<<","<<run->name<<"进程结束";

             Delete_process();

             if(head&&current==head->arrivetime) k=1;

             else {cout<<'\n';

                   if(!run&&!head) break;}

             }

         if(head==NULL||(head&&current<head->arrivetime))

             if(run&&run->next) function1();

         if(head&&current==head->arrivetime)

             {if(!k&&run&&run->next) function1();

              if(run) function2();

              else Set_Run();

              if(!k) cout<<"当时间为"<<current;

              cout<<","<<run->name<<"进程开始"<<endl;

              }

         }

输出运行中的进程信息

优先级调度算法

void process::process_Grade()//按优先级调度

{   for(int k=0;head||run;k=0)

        {if(!run&&head)

            {while(current<head->arrivetime) current++;

             Set_Run();

             cout<<"当时间为"<<current<<","<<run->name<<"进程开始"<<endl;

             }

         run->runtime--,current++,run->grade++;

         if(run->runtime==0)

            {cout<<"当时间为"<<current<<","<<run->name<<"进程结束";

             Delete_process();

             if(head&&current>=head->arrivetime) k=1;

             else {cout<<'\n';

                   if(!run&&!head) break;}

             }

          if(!head||current<head->arrivetime)

             if(run&&run->next&&run->grade>run->next->grade) function3();  

          if(head&&current>=head->arrivetime)

            {if(!run)

               {Set_Run();cout<<","<<run->name<<"进程开始"<<endl;}

             else

               {if(run->next&&run->grade>run->next->grade) function3();

                if(head->grade>=run->grade)

                  {if(k) cout<<'\n';}

                else

                  {function2();

                   if(!k) cout<<"当时间为"<<current;

                   cout<<","<<run->name<<"进程开始"<<endl;

                   }

                 }

              }

          }

2.  页面替换算法

（1）输入数据，存入数组。

void DataInput()

{

 cout<<"请输入物理块数：";

 cin>>M;

 while(M > BlockNum) // 大于数据个数

 {

  cout<<"物理块数超过预定值，请重新输入：";

  cin>>M;

 }

 cout<<"请输入页面的个数：";

 cin>>N;

 while(N > DataMax) // 大于数据个数

 {

  cout<<"页面个数超过预定值，请重新输入：";

  cin>>N;

 }

 cout<<"请输入页面访问序列："<<endl;

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

  cin>>Data[i];

}

先进先出算法

void FIFO()

{

 int i,j;

 bool find;

 int point;

 int temp; // 临时变量

 ChangeTimes = 0;

 for(j=0;j<M;j++)

  for(i=0;i<N;i++)

   DataShowEnable[j][i] = false;  // 初始化为false，表示没有要显示的数据

 

 for(i=0;i<M;i++)

 {

   count[i] = 0; //  大于等于BlockNum，表示块中没有数据，或需被替换掉

        // 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1，

       // 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段

 }

 for(i=0;i<N;i++) // 对有所数据操作

 {

  // 增加count

  for(j=0;j<M;j++)

   count[j]++;

  find = false; // 表示块中有没有该数据

  for(j=0;j<M;j++)

  {

   if( Block[j] == Data[i] )

   {

    find = true;

   }

  }

  if( find ) continue; // 块中有该数据，判断下一个数据

  // 块中没有该数据

  ChangeTimes++; // 缺页次数++ 

 

  if( (i+1) > M ) // 因为i是从0开始记，而M指的是个数，从1开始，所以i+1

  {

   //获得要替换的块指针

   temp = 0;

   for(j=0;j<M;j++)

   {

    if( temp < count[j] )

    {

     temp = count[j];

     point = j; // 获得离的最远的指针

    }

   }

  }

  else point = i;

  // 替换

  Block[point] = Data[i];

 

  count[point] = 0; // 更新计数值

 

  // 保存要显示的数据

  for(j=0;j<M;j++)

  {

   DataShow[j][i] = Block[j];

   DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据

  }

 }

 // 输出信息

 cout<< endl;

 cout<<"FIFO => "<< endl;

 DataOutput();

}

最佳页面算法

void Optimal()

{

 int i,j,k;

 bool find;

 int point;

 int temp; // 临时变量，比较离的最远的时候用

 ChangeTimes = 0;

 for(j=0;j<M;j++)

  for(i=0;i<N;i++)

   DataShowEnable[j][i] = false;  // 初始化为false，表示没有要显示的数据

// for(i=0;i<M;i++)

// {

  // count[i] = 0 ; //

// }

 for(i=0;i<N;i++) // 对有所数据操作

 {

  find = false; // 表示块中有没有该数据

  for(j=0;j<M;j++)

  {

   if( Block[j] == Data[i] )

    find = true;

  }

  if( find ) continue; // 块中有该数据，判断下一个数据

  // 块中没有该数据，最优算法

  ChangeTimes++; // 缺页次数++ 

  for(j=0;j<M;j++)

  {

   // 找到下一个值的位置

   find = false;

   for( k =i;k<N;k++)

   {

    if( Block[j] == Data[k] )

    {

     find = true;

     count[j] = k;

     break;

    }

   }

   if( !find ) count[j] = N;

  }

  if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1

  {

   //获得要替换的块指针

   temp = 0;

   for(j=0;j<M;j++)

   {

    if( temp < count[j] )

    {

     temp = count[j];

     point = j; // 获得离的最远的指针

    }

   }

  }

  else point = i;

  // 替换

  Block[point] = Data[i];

 

  // 保存要显示的数据

  for(j=0;j<M;j++)

  {

   DataShow[j][i] = Block[j];

   DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据

  }

 }

 // 输出信息

 cout<< endl;

 cout<<"Optimal => "<< endl;

 DataOutput();

}

最近最少使用算法

void LRU()

{

 int i,j;

 bool find;

 int point;

 int temp; // 临时变量

 ChangeTimes = 0;

 for(j=0;j<M;j++)

  for(i=0;i<N;i++)

   DataShowEnable[j][i] = false;  // 初始化为false，表示没有要显示的数据

 for(i=0;i<M;i++)

 {

   count[i] = 0 ;

 }

 for(i=0;i<N;i++) // 对有所数据操作

 {

  // 增加count

  for(j=0;j<M;j++)

   count[j]++;

  find = false; // 表示块中有没有该数据

  for(j=0;j<M;j++)

  {

   if( Block[j] == Data[i] )

   {

    count[j] = 0;

    find = true;

   }

  }

  if( find ) continue; // 块中有该数据，判断下一个数据

  // 块中没有该数据

  ChangeTimes++; // 缺页次数++ 

  if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1

  {

   //获得要替换的块指针

   temp = 0;

   for(j=0;j<M;j++)

   {

    if( temp < count[j] )

    {

     temp = count[j];

     point = j; // 获得离的最远的指针

    }

   }

  }

  else point = i;

  // 替换

  Block[point] = Data[i];

  count[point] = 0;

 

  // 保存要显示的数据

  for(j=0;j<M;j++)

  {

   DataShow[j][i] = Block[j];

   DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据

  }

 }

 // 输出信息

 cout<< endl;

 cout<<"LRU => "<< endl;

 DataOutput();

}

3.  移动臂调度算法

（1）结构体和布尔函数

struct disk

{

    int a_number;

    int b_number;

    int c_number;

};

bool sortBy_a_number ( const disk &s1 , const disk &s2 )

{

    return s1.a_number < s2.a_number ;

}

bool sortBy_b_number ( const disk &s1 , const disk &s2 )

{

    return s1.b_number < s2.b_number ;

}

bool sortBy_c_number ( const disk &s1 , const disk &s2 )

{

    return s1.c_number < s2.c_number ;

}

（2）先来先服务算法

void fcfs()

{

    int N, count = 0, base = 0;

    cout<<"先来先服务算法\n";

    cerr << "请输入个数： N == " << endl;

    cin >> N;

    vector<disk> records(N);

    cerr << "请输入：柱面  磁道号  物理块号 " << endl;

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

    {

        cin >> records[i].a_number >> records[i].b_number >> records[i].c_number;

    }

    cerr << "顺序是：" << endl;

    for (int i2 = 0; i2 < N; ++i2)

    {

        cout << records[i2].a_number << '\t' << records[i2].b_number << '\t' << records[i2].c_number << endl;

        count += abs(records[i2].a_number - base);

        base = records[i2].a_number;

    }

    cout << "采用 FCFS 的移臂是：" << count << endl;

}

（3）最短查找时间算法

void shortseektime()

{

    int N, count = 0, base = 0;

    cout<<"最短查询时间算法\n";

    cerr << "请输入个数： N == " ;

    cin >> N;

    vector<disk> records(N);

    cerr << "请输入：柱面  磁道号  物理块号 " << endl;

    for (vector<disk>::size_type i = 0; i < records.size(); ++i)

    {

        cin >> records[i].a_number >> records[i].b_number >> records[i].c_number;

    }

    stable_sort (records.begin(), records.end(), sortBy_a_number );

    vector<disk>::iterator idex = records.begin();

    for (vector<disk>::iterator iter = records.begin(); iter != records.end(); ++iter)

    {

        if ( (*iter).a_number != (*idex).a_number)

        {

            stable_sort(idex, iter, sortBy_b_number);

            idex = iter;

        }

    }

    idex = records.begin();

    for (vector<disk>::iterator iter2 = records.begin(); iter2 != records.end(); ++iter2)

    {

        if ( (*iter).b_number != (*idex).b_number)

        {

            stable_sort(idex, iter2, sortBy_c_number);

            idex = iter;

        }

    }

    cerr << "\n运行结果是：" << endl;

    for (vector<disk>::size_type i1 = 0; i1 < records.size(); ++i1)

    {

        cout << records[i1].a_number << '\t' << records[i1].b_number << '\t' << records[i1].c_number << endl;

        count += abs(records[i1].a_number - base);

        base = records[i1].a_number;

    }

    cout << "采用 最短查找时间优先 的移臂是：" << count << endl;

}

（4）扫描算法

void sortfun()

{

    int N, count = 0, base; // distance 表示当前磁头移动方向

    cout<<"    扫描算法\n";

    cerr << "请输入个数： N == " ;

    cin >> N;

    vector<disk> records(N), note;

    cerr << "请输入：柱面  磁道号  物理块号 " << endl;

    for (vector<disk>::size_type i = 0; i < records.size(); ++i)

    {

        cin >> records[i].a_number >> records[i].b_number >> records[i].c_number;

    }

    sort(records);

    disk start;

    cerr << "请设定磁头初始位置 柱面号 磁道号 物理快号" << endl;

    cin >> start.a_number >> start.b_number >> start.c_number;

    base = start.a_number;

    int distance;

    cerr << "请设定当前磁头移动方向（向外从大到小为 1, 向内从小到大为 0）" << endl;

    cin >> distance;

    cerr << "\n运行结果是：" << endl;

    vector<disk>::iterator _idex;

    for ( _idex = records.begin(); _idex != records.end(); ++_idex)            // 定位当前磁头

    {

        if ((*_idex).a_number >= start.a_number && (*_idex).b_number >= start.b_number && (*_idex).c_number >= start.c_number)

        {

             break;

        }

    }

   

    if (distance == 0)  // 以下是：向内运行，磁道变大 distance == 0 的情况

    {

        output_r (_idex, records.end(), base, count);

        output_l (records.begin(), _idex, base, count);

    }

    else   // 以下是：向外运行，磁道变小 distance == 1 的情况

    {

        output_l (records.begin(), _idex, base, count);

        output_r (_idex, records.end(), base, count);

    }

    cout << "采用 扫描算法 的移臂是：" << count << endl;

}

银行家算法

当某个进程提出资源请求时，假定先分配给它，之后调用系统安全性检查算法，进行系统安全性检查。若系统安全，假分配变为真分配。否则作废假分配，让进程等待

（1）有进程释放资源时，判断是否能唤醒等待资源的进程

void wakeup(vector<pcb> &pgrp, int available){

    vector<pcb>::iterator p;

    for( p = pgrp.begin() ; p != pgrp.end() ; p++ ){

        if( p -> p_stat == TASK_WAITING ){

            if( p -> p_apply <= available )

                p -> p_stat = TASK_RUNNING;

        }

    }

}

（2）检查系统中是否所有进程都运行结束

bool isFinished( vector<pcb> & pgrp ){

    vector<pcb>::iterator p;

    for( p = pgrp.begin() ; p != pgrp.end() ; p++ )

        if( p -> p_stat != TASK_SUCCEED )

            return false;

    return true;

}

（3）检查系统是否出于安全状态的算法

bool isSafeState(vector<pcb> &pgrp, int available){

    vector<pcb>::iterator p;

    bool _isSafe = true;

    （4）初始化设为false

    for( p = pgrp.begin() ; p != pgrp.end() ; p++ ){

        if( p -> p_stat != TASK_SUCCEED )

            p -> p_issuc = false;

    }

  （5）检查是否所有进程都能被设置成安全标志

    for( p = pgrp.begin() ; p != pgrp.end() ; p++ ){

        if( p -> p_issuc == true )

            continue;

        if( ( p -> p_require - p -> p_occupy ) > available )

            continue;

        else{

            p -> p_issuc = true;

            available += p -> p_occupy;

            p = pgrp.begin();

            continue;

        }

    }

  （6）检查是否有进程没有被设置成安全标志

    for( p = pgrp.begin() ; p != pgrp.end() ; p++ ){

        if( p -> p_issuc == true )

            continue;

        //如果有，则置该标志为false

        else{

           _isSafe = false;

           break;

        }

    }

    return _isSafe;

}

（7）从申请资源的进程队列中获取第一个运行进程

vector<pcb>::iterator getFirstaRunningProcess( vector<pcb> & pgrp ){

    vector<pcb>::iterator p;

    for( p = pgrp.begin() ; p != pgrp.end() ; p++ ){

        if( p -> p_stat == TASK_RUNNING ){

            return p;

        }

    }

    return pgrp.end();

}

（8）输入进程的当前申请量

void readApply( vector<pcb>::iterator  proc ){

    cout << endl << "请输入进程" << proc -> p_pid << "的当前申请量\t";

    ff << endl << "请输入进程" << proc -> p_pid << "的当前申请量\t";

    cin >> proc -> p_apply;

    ff << proc -> p_apply << endl;

    while( proc -> p_apply > proc ->p_require -  proc -> p_occupy ){

        cout << endl << "超出真实需要！" << endl;

        ff << endl << "超出真实需要！" << endl;

        cout << endl << "重新输入进程" << proc -> p_pid << "的当前申请量\t";

        ff << endl << "重新输入进程" << proc -> p_pid << "的当前申请量\t";

        cin >> proc -> p_apply;

        ff << proc -> p_apply << endl;

    }

}

四.运行结果

（1）主界面

（2）处理机调度

（3）页面替换算法

（4）移动臂调度算法

（6）   银行家算法

五．实验总结

整个设计中最麻烦的就是整个程序模块的划分和各模块之间连接设计，编程中经常犯想当然的错误，编程中出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查。。

通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，才能提高自己实践能力.通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。