第3章 处理机管理

3.1 作业调度

3.1.1 调度级别（P74）

 * 调度：选出待分派的作业或进程。

 * 调度级别：

 (1)高级调度：

    主要功能是根据一定的算法，从输入的一批作业中选出若干个作业，

    分配必要的资源，如内存、外设等，为它建立相应的用户作业进程

    和为其服务的系统进程（如输入、输出进程），

    最后把它们的程序和数据调入内存，

    等待进程调度程序对其执行调度，

    并在作业完成后作善后处理工作。

 (2)中级调度：

   主要功能是为了使内存中同时存放的进程数目不至于太多，

   有时就需要把某些进程从内存中移到外存上，

   以减少多道程序的数目，为此设立了中级调度。

(3)低级调度：

      主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。

 * 进程调度程序：执行低级调度功能的程序。

3.1.2 作业状态（P75）

 (1)提交状态：被用户向系统提交的作业所处的状态。

 (2)后备状态：用户作业经输入设备送入输入井中存放，

    等待进入内存时所处的状态。

 (3)执行状态：作业分配到所需的资源，被调入内存，

    并且在处理机（CPU）上执行相应的程序时所处的状态。

 (4)完成状态：作业完成了计算任务，准备退出系统时的作业状态。

3.1.3 作业调度

 1.作业控制块JCB（P75）

   作业控制块的内容：

   资源要求（运算时间、内存量、外设）、资源使用情况、……。

 2.作业调度的功能（P76）

  * 作业调度的任务：

    完成作业转换（后备状态—执行状态—完成状态）。

  * 作业调度的功能：

  (1)记录系统中各个作业的情况：分配的资源和作业状态等。

  (2)按照某种调度算法从后备作业队列中挑选作业。

  (3)为选中的作业分配内存和外设等资源。

  (4)为选中的作业建立相应的进程。

  (5)作业后进行善后处理工作，如输出信息收回资源。

 * 合理搭配作业：CPU繁忙型作业（科学计算）、

   I/O繁忙型作业（数据处理）、内存繁忙型作业（递归计算）。

3.2 进程调度

3.2.1 进程调度的功能和时机

 (1)进程调度的功能（P77）

    保存现场：程序计数器、通用寄存器的内容；

    挑选进程：从就绪队列中选出进程；

    恢复现场：把CPU控制权交给进程，接续断点运行。

 (2)进程调度的时机（P78）

    完成任务、等待资源、运行到时、发现标志。

3.2.2 两级调度模型（P78）

 1.作业调度：

  * 宏观调度，它所选择的作业只是具有获得处理机的资格，

   但尚未占有处理机，不能立即在其上实际运行。

  * 从外存的后备队列中选择一批作业调入内存，

   为它们创建进程，这些进程被送入就绪队列。

 2.进程调度：

  * 微观调度，它动态地把处理机实际地分配给所选择的进程，

   使之真正活动起来。

   另外，进程调度相当频繁，而作业调度执行次数一般很少。

  * 从就绪队列中选出一个进程来，并把它的状态改为运行态，

    把CPU分配给它。

    当运行进程要等待某一事件时，

    就让出CPU，进入相应的阻塞队列；并进行进程调度。

    运行进程完成后，由作业调度进行善后处理工作。

3.3 调度性能的评价

3.3.1 选择调度算法时应考虑的主要因素（P79）

  所用算法应保证实现系统的设计目标。网络系统应使得用户和程序

  能方便、有效地利用网络中的分布式资源）；

  使每个进程能公平地共享CPU；均衡使用资源；

  兼顾响应时间和资源利用率；基于相对优先级，但避免无限延期；

  系统开销不应太大。

3.3.2 调度性能评价准则（P80）

 1.CPU利用率：轻负荷系统40%，重负荷系统90%。

 2.吞吐量：单位时间内CPU完成作业的数量。

 3.周转时间：从作业提交到作业完成的时间间隔。

   周转时间：Ti = 完成时刻tci-提交时刻tsi

   平均周转时间：T = n个作业时间和/n

   带权周转时间：W = 周转时间T/实际运行时间R

   平均带权周转时间 W = n个作业带权周转时间和/n

 4.就绪等待时间：作业在就绪队列中的等待时间。

 5.响应时间：从提交第一个请求到产生第一个响应所用的时间。

3.4 常用调度算法

3.4.1 先来先服务法（P81）

 * 先来先服务FCFS(First Come-First Serviced)

   作业调度：把后备作业队头调入内存，分配相应的资源，

   创建进程，然后把进程放入就绪队列。

   进程调度：使就绪队列中最先进入的进程得到CPU并运行。

 * FCFS调度算法示意图(P82)

 * FCFS调度算法性能：有利长作业，不利短作业。

3.4.2 时间片轮转法（P83）

 * 时间片轮转法RR：用于分时系统中的进程调度。

 * 时间片轮转法进程运行情况

   进程A，B，C，D运行时间分别为12，5，3，6。

 * 时间片轮转调度算法的性能（P84）

 * 选择时间片长短考虑的因素：

   进程数目一定时，系统的响应时间长要求时间片长；

   系统要求的响应时间一定时，

   就绪队列进程的数目多要求时间片短；

   进程的转换时间t应小于（时间片q/10）。

3.4.3 优先级法（P84）

 * 进程获得CPU的使用权的处理方式：

   非抢占式优先级法、抢占式优先级法。

 * 确定进程优先级的方式：

   静态方式：创建进程时，由内部决定或由外部标准设置。

   动态方式：运行的进程占用CPU时间长，则优先级下降；

             在就绪队列中用户进程等待CPU时间长，则优先级上升。

3.4.4 其它调度算法简介（P86）

 1.短作业优先法（SJF）

 2.最短剩余时间优先法：

   就绪队列中的进程需要的运行时间比

   当前运行的进程所需剩余时间短时，则调换出当前进程。

 3.多级队列法：

   前台作业的进程可用轮转法调度，

   后台作业的进程可用FCFS方法调度。

 4.多级队列反馈法：应用于UNIX系统、Windows NT。

3.5 UNIX常用调度命令及命令执行过程

3.5.1 UNIX系统中的进程调度（P87）

 1.调度时机

   核心进程调度的时机：

   进程调用sleep程序；进程终止；进程从系统调用返回到用户态；

   核心处理完中断。

 2.调度算法

   进程调度算法由swtch程序实现。

   调度进程的算法：

   输入：无

   输出：无

   {

     if(当前进程不是0#进程)

      { 保存当前进程的环境变量

        恢复0#进程的运行环境

      }

     while(没有进程被选中执行)

      {

       for(所有在就绪队列中的进程)

           选出优先级最高且在内存的一个进程；

       if(没有合适进程可以执行)

          机器作空转；

      }

      从就绪队列中移出该选中进程；

      恢复选中进程的现场，令其投入运行；

    }

 * 核心改动进程优先级的方式：

   对核心进程设置优先数，设置原则取决于进程睡眠的原因；

   对用户态进程计算优先数。

 * 进程优先级的级别（P89）

 * 用衰减函数调整当前进程使用CPU的时间值：

   decay(p_cpu)=p_cpu/2   //p_cpu 当前进程使用CPU的时间值

 * [内存就绪]状态进程优先数的计算：

   优先数 =（“当前CPU使用值”/2）+分界优先数

例如：进程A、B优先数的变化

3.5.2 UNIX常用调度命令（P90）

 1.nohup命令

   功能：忽略挂起(hangup)和退出(quit)的方式执行命令。

   格式：nohup command [arguments]

   例如：$ nohup find / -name exam.txt -print > f1 &

           后台运行find，查找exam.txt，定向到f1。

 2.at命令

   功能：指定命令执行时间。

   格式：at time command

   例如：

     $ at 15:00 oct 20

       指定时间、月日。

     mail -s "Happy Birthday!" lms

     发送邮件，标题，姓名：林木森

     按<Ctrl>D，屏幕显示：

     job 862960800.a    at Wed Oct 20 15:00:00 CST 2002

     作业ID号，at提交(.a)，星期，月日，时间，      年。

 3.batch命令

   功能：提交作业。

   例如：

    $ batch

    find / -name exam.txt -print

    job 862961540.b at Thu Nov 18 14:30:00 CST 2002

    batch提交的作业(.b)

 4.jobs命令

   功能：显示后台作业。

   例如：

    $ jobs

    [2]       +        Running tar tv3 * &

    作业序号，优先级，运行状态。

 5.fg命令

   功能：把作业移到前台。

   格式：fg [job…]

   例如：

    $ jobs

    [2] + Running tar tv3 * &

    [1] - Running find / -name README -print > logfile&

    $ fg % find

      把find作业移前台，% 分隔符。

 6.bg命令

   功能：把作业移到后台。

   格式：bg [job…]

   例如：$ bg %cc

3.5.3 shell 命令执行过程（P92）

 * shell：解释并执行用户输入的命令。

   用户与操作系统之间的界面（外壳），用户通过外壳操作内核。

 * 终端用户进程执行shell解释程序的过程：

   读键入的命令—>判断命令的对错—>创建子进程—>

   等待子进程完成—>子进程运行—>子进程终止—>

   父进程运行—>发提示符$。

自测题（P95）

  2.高级调度与低级调度的主要功能是什么？

   为什么要引入中级调度？（P74、P278）

 7.作业调度与进程调度之间有什么差别？

   二者间如何协调工作？（P278）

 9.简述FCFS、RR和优先级调度算法的实现思想。（P81、P279）

 12.简述一条shell命令在UNIX系统中的实现过程。（P92、P281）