进程调度算法实验报告

A. 操作系统管理Linux 系统进程实验报告

什么是进程

比如：windows上安装的QQ，我们会将其称为QQ程序，那么当QQ运行之后，在任务管理器中，我们可以看到QQ程序在运行着，此时，我们称其为:QQ进程。

言简意赅总结：当我们运行一个程序，那么我们将该程序叫进程

注意：
1.当程序运行为进程后，系统会为该进程分配内存，以及运行的身份和权限。
2.在进程运行的过程中，服务器上回有各种状态来表示当前进程的指标信息。

进程是已启动的可执行程序的运行实例，进程有以下组成部分:

分配内存, 已分配内存的地址空间
安全属性, 进程的运行身份和权限
进程代码, 运行一个或多个的线程
进程状态, 进程运行后的多种状态
静态程序, 二进制文件, 静态/bin/ls, /usr/sbin/sshd
动态进程, 程序运行的过程, 有生命周期及运行状态

进程的运行环境，包括以下几个部分：

局部和全局变量
当前的调度上下文
分配给进程使用的系统资源，例如文件描述符、网络端口等
给进程分配对应的pid,ppid

程序和进程的区别

1.程序是数据和指令的集合，是一个静态的概念，比如/bin/ls、/bin/cp等二进制文件，同事程序可以长期存在系统中。

2.进程是一个程序的运行过程，是一个动态概念，进程是存在生命周期概念的，也就是说进程会随着程序的终止而销毁，不会永远在系统中存在。

进程的生命周期

程序运行时进程的状态关系:

1.当父进程接收到任务调度时，会通过fork派生子进程来处理，那么子进程会集成父进程的衣钵。
2.子进程在处理任务代码时，父进程会进入等待的状态...
3.如果子进程在处理任务过程中，父进程退出了，子进程没有退出，那么这些子进程就没有父进程来管理了，就变成了僵尸进程。
4.每个进程都会有自己的PID号，（process id）子进程则PPID

B. Linux系统的进程调度

Linux进程调度

1．调度方式

Linux系统的调度方式基本上采用“ 抢占式优先级 ”方式，当进程在用户模式下运行时，不管它是否自愿，核心在一定条件下（如该进程的时间片用完或等待I/O）可以暂时中止其运行，而调度其他进程运行。一旦进程切换到内核模式下运行时，就不受以上限制，而一直运行下去，仅在重新回到用户模式之前才会发生进程调度。

Linux系统中的调度基本上继承了UNIX系统的 以优先级为基础 的调度。也就是说，核心为系统中每个进程计算出一个优先级，该优先级反映了一个进程获得CPU使用权的资格，即高优先级的进程优先得到运行。核心从进程就绪队列中挑选一个优先级最高的进程，为其分配一个CPU时间片，令其投入运行。在运行过程中，当前进程的优先级随时间递减，这样就实现了“负反馈”作用，即经过一段时间之后，原来级别较低的进程就相对“提升”了级别，从而有机会得到运行。当所有进程的优先级都变为0（最低）时，就重新计算一次所有进程的优先级。

2．调度策略

Linux系统针对不同类别的进程提供了3种不同的调度策略，即SCHED_FIFO、SCHED_RR及SCHED_OTHER。其中，SCHED_FIFO适合于 短实时进程 ，它们对时间性要求比较强，而每次运行所需的时间比较短。一旦这种进程被调度且开始运行，就一直运行到自愿让出CPU或被优先级更高的进程抢占其执行权为止。

SCHED_RR对应“时间片轮转法”，适合于每次运行需要 较长时间的实时进程 。一个运行进程分配一个时间片（200 ms），当时间片用完后，CPU被另外进程抢占，而该进程被送回相同优先级队列的末尾，核心动态调整用户态进程的优先级。这样，一个进程从创建到完成任务后终止，需要经历多次反馈循环。当进程再次被调度运行时，它就从上次断点处开始继续执行。

SCHED_OTHER是传统的UNIX调度策略，适合于交互式的 分时进程 。这类进程的优先级取决于两个因素：一个是进程剩余时间配额，如果进程用完了配给的时间，则相应优先级降到0；另一个是进程的优先数nice，这是从UNIX系统沿袭下来的方法，优先数越小，其优先级越高。nice的取值范围是-20 19。用户可以利用nice命令设定进程的nice值。但一般用户只能设定正值，从而主动降低其优先级；只有特权用户才能把nice的值设置为负数。进程的优先级就是以上二者之和。

后台命令对应后台进程（又称后台作业）。后台进程的优先级低于任何交互（前台）进程的优先级。所以，只有当系统中当前不存在可运行的交互进程时，才调度后台进程运行。后台进程往往按批处理方式调度运行。

3．调度时机

核心进行进程调度的时机有以下5种情况：

（1）当前进程调用系统调用nanosleep( )或者pause( )，使自己进入睡眠状态，主动让出一段时间的CPU的使用权。

（2）进程终止，永久地放弃对CPU的使用。

（3）在时钟中断处理程序执行过程中，发现当前进程连续运行的时间过长。

（4）当唤醒一个睡眠进程时，发现被唤醒的进程比当前进程更有资格运行。

（5）一个进程通过执行系统调用来改变调度策略或者降低自身的优先级（如nice命令），从而引起立即调度。

4．调度算法

进程调度的算法应该比较简单，以便减少频繁调度时的系统开销。Linux执行进程调度时，首先查找所有在就绪队列中的进程，从中选出优先级最高且在内存的一个进程。如果队列中有实时进程，那么实时进程将优先运行。如果最需要运行的进程不是当前进程，那么当前进程就被挂起，并且保存它的现场—— 所涉及的一切机器状态，包括程序计数器和CPU寄存器等，然后为选中的进程恢复运行现场。

（二）Linux常用调度命令

· nohup命令

nohup命令的功能是以忽略挂起和退出的方式执行指定的命令。其命令格式是：

nohupcommand［arguments］

其中，command是所要执行的命令，arguments是指定命令的参数。

nohup命令告诉系统，command所代表的命令在执行过程中不受任何结束运行的信号（hangup和quit）的影响。例如，

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

find命令在后台运行。在用户注销后，它会继续运行：从根目录开始，查找名字是exam.txt的文件，结果被定向到文件f1中。

如果用户没有对输出进行重定向，则输出被附加到当前目录的nohup.out文件中。如果用户在当前目录中不具备写权限，则输出被定向到$HOME/nohup.out 中。

· at命令

at命令允许指定命令执行的时间。at命令的常用形式是：

attimecommand

其中，time是指定命令command在将来执行时的时间和日期。时间的指定方法有多种，用户可以使用绝对时间，也可以用相对时间。该指定命令将以作业形式在后台运行。例如：

$ at 15:00 Oct 20

回车后进入接收方式，接着键入以下命令：

mail -s "Happy Birthday!" liuzheny

按下D键，屏幕显示：

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

$

表明建立了一个作业，其作业ID号是862960800.a，运行作业的时间是1999年10月20日下午3:00，给liuzheny发一条标题为“Happy Birthday！”（生日快乐）的空白邮件。

利用 at-l 可以列出当前at队列中所有的作业。

利用 at-r 可以删除指定的作业。这些作业以前由at或batch命令调度。例如，

at-r862960797.a

将删除作业ID号是862960797.a的作业。其一般使用形式是：

at-rjob_id

注意，结尾是.a的作业ID号，表示这个作业是由at命令提交的；结尾是.b的作业ID号，表示这个作业是由batch命令提交的。

· batch命令

batch命令不带任何参数，它提交的作业的优先级比at命令提交的作业的优先级低。batch无法指定作业运行的时间。实际运行时间要看系统中已经提交的作业数量。如果系统中优先级较高的作业比较多，那么，batch提交的作业则需要等待；如果系统空闲，则运行batch提交的作业。例如，

$ batch

回车后进入接收方式，接着键入命令：

find / -name exam.txt -print

按下D。退出接收方式，屏幕显示：

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

表示find命令被batch作为一个作业提交给系统，作业ID号是862961540.b。如果系统当前空闲，这个作业被立即执行，其结果同样作为邮件发送给用户。

· jobs命令

jobs命令用来显示当前shell下正在运行哪些作业（即后台作业）。例如：

$ jobs

[2] + Running tar tv3 *&

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

$

其中，第一列方括号中的数字表示作业序号，它是由当前运行的shell分配的，而不是由操作系统统一分配的。在当前shell环境下，第一个后台作业的作业号为1，第二个作业的作业号为2，等等。

第二列中的“ ”号表示相应作业的优先级比“－”号对应作业的优先级高。

第三列表明作业状态，是否为运行、中断、等待输入或停止等。

最后列出的是创建当前这个作业所对应的命令行。

利用 jobs-l 形式，可以在作业号后显示出相应进程的PID。如果想只显示相应进程的PID，不显示其它信息，则使用 jobs-p 形式。

· fg命令

fg命令把指定的后台作业移到前台。其使用格式是：

fg [job…]

其中，参数job是一个或多个进程的PID，或者是命令名称或者作业号（前面要带有一个“%”号）。例如：

$ jobs

[2] + Running tar tv3 *&

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

$ fg %find

find / -name README -print > logfile

注意，显示的命令行末尾没有“&”符号。下面命令能产生同样的效果：

$ fg %1

这样，find命令对应的进程就在前台执行。当后台只有一个作业时，键入不带参数的fg命令，就能使相应进程移到前台。当有两个或更多的后台作业时，键入不带参数的fg，就把最后进入后台的进程首先移到前台。

· bg命令

bg命令可以把前台进程换到后台执行。其使用格式是：

bg [job…]

其中，job是一个或多个进程的PID、命令名称或者作业号，在参数前要带“%”号。例如，在cc（C编译命令）命令执行过程中，按下Z键，使这个作业挂起。然后键入以下命令：

$ bg %cc

该挂起的作业在后台重新开始执行。

C. 常见的调度算法总结

一、FCFS——先来先服务和短作业（进程）优先调度算法

1. 先来先服务调度算法。

先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度， 也可用于进程调度。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。由此可知，本算法适合于CPU繁忙型作业， 而不利于I/O繁忙型的作业（进程）。

2. 短作业（进程）优先调度算法。

短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，该算法既可用于作业调度， 也可用于进程调度。但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。

二、FPF高优先权优先调度算法

1. 优先权调度算法的类型。

为了照顾紧迫性作业，使之进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。 此算法常被用在批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度，还可以用于实时系统中。当其用于作业调度， 将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，此时， 又可以进一步把该算法分成以下两种：

1)非抢占式优先权算法

2)抢占式优先权调度算法（高性能计算机操作系统）

2. 优先权类型 。

对于最高优先权优先调度算法，其核心在于：它是使用静态优先权还是动态优先权， 以及如何确定进程的优先权。

3.动态优先权

高响应比优先调度算法为了弥补短作业优先算法的不足，我们引入动态优先权，使作业的优先等级随着等待时间的增加而以速率a提高。 该优先权变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间；即 =（响应时间）/要求服务时间

三、基于时间片的轮转调度算法

1.时间片轮转法。

时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。 当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。

2. 多级反馈队列调度算法

多级反馈队列调度算法多级反馈队列调度算法，不必事先知道各种进程所需要执行的时间，它是目前被公认的一种较好的进程调度算法。 其实施过程如下：

1) 设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中， 为每个进程所规定的执行时间片就越小。

2) 当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。 如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度…… 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。

3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；

仅当第1到第（ i-1 ）队列空时， 才会调度第i队列中的进程运行，并执行相应的时间片轮转。

4) 如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列， 则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。

D. 进程调度方案设计 实现一个基本动态优先级的调度算法

前两天做操作系统作业的时候学习了一下几种进程调度算法，在思考和讨论后，有了一些自己的想法，现在就写出来，跟大家讨论下。，或者说只有有限的CPU资源，当系统中有多个进程处于就绪状态，要竞争CPU资源时，操作系统就要负责完成如何分配资源的任务。在操作系统中，由调度程序来完成这一选择分配的工作，调度程序所使用的算法即是调度算法。调度算法需要考虑的指标主要有尽量保证CPU资源分配的公平性；按照一定策略强制执行算法调度；平衡整个计算机系统，尽量保持各个部分都处于忙碌状态。而根据系统各自不同的特点和要求，调度算法又有一些侧重点和目标不同，因此，算法按照系统差异主要分为三大类：批处理系统中的调度算法，代表调度算法有：先来迟轿斗先服务、最短作业优先、最短剩余时间优先。交互式系统中的调度算法，代表调度算法有：轮转调度、优先级调度、多级队列、最短进程优先、保证调度、彩票调度、公平分享调度。实时系统中的调度算法，代表调度算法有：速率单调调度、最早最终时限优先调度。下面就上述提到的调度算法中挑出几个进行重点分析：保证调度保证调度是指利用算法向用户做出明确的性能保证，然后尽力按照此保证实现CPU的资源分配。利用这种算法，就是定一个进程占用CPU的时间的标准，然后按照这个标准去比较实际占用CPU的时间，调度进程每次使离此标准最远的进程得到资源，不断满足离所保证的标准最远的进程，从而平衡资源分配满足这个标准的要求。保证调度算法的优点是：能很好的保证进程公平的CPU份额，当系统的特点是：进程的优先级没有太大悬殊，所制定的保证标准差异不大，各个进程对CPU的要求较为接近时，比如说系统要求n个进程中的每个进程都只占用1/n的CPU资源，利用保证调度可以很容易的实现稳定的CPU分配要求。但缺点是，这种情况太过理想，当系统的各个进程对CPU要求的紧急程度不同，所制定的保证较为复杂的时候，这个算法实现起来比较困难。彩票调度彩票调度这种算法的大意是指向进程提供各种系统资源如CPU资源的彩票，当系统需要做出调度决策时，随机抽出一张彩票，由此彩票的拥有者获得资源。在彩票调度系统中，如果有一个新的进程出现并得到一些彩票，那么在下一次的抽奖中，该进程会有同它持有彩票数量成正比例的机会赢得奖励。进程持有的彩票数量越多，则被抽中的可能性就越大。调度程序可以通过控制进程的彩票持有数量来进行调度。彩票调度有很多优点：首先，它很灵活，系统增加分给某个进程的彩票数量，就会大大增加它占用资源的可能性，可以说，彩票调度的反应是迅速的，而快速响应需求正是交互式系统的一个重要要求。其次，彩票调度算法中，进程可以交换彩票，这个特点可以更好的保证系统的平衡性，使其各个部分都尽可能的处于忙碌状态。而且利用彩票调度还可以解决许多别的算法很难解决的问题，例如可以根据特定的需要大致成比例的划分CPU的使用。速率单调调度速率单调调度算法是一种可适用于可抢占的周期性进程的经典静态实时调度算法。当实时系统中的进程满足：每个周期性进程必须在其周期内完成，且进程之间没有相互依赖的关系，每个进程在一次突发中需要相同的CPU时间量，非周期的进程都没有最终时限四个条件时，并且为了建模方便，我们假设进程抢占即刻发生没有系统码磨开销，可以考虑利用速率单调算法。速率单调调度算法是将进程的速率（按照进程周期所算出的每秒响应的次数）赋为优先级，则保证了优先级与进程速率成线性关系，这即是我们所说的速率单调。调度程序每次运行优先级最高的，只要优先级较高的程序需要运行，则立即抢占优先级低的进程，而优先级较低的进程必须等所有优先级高于它的进程结束后才能运行。速率单调调度算法可以保证系统中最关键的任务总是得到调度，但是缺点是其作为一种静态算法，灵活性不够好，当进程数变多，系统调度变得复杂时，可能不能较好的保证进程在周期内运行。最早最终时限优先调度最早最终时限优先调度算法是一个动态算法，不要求进程是周期性的，只要帆李一个进程需要CPU时间，它就宣布它的到来时间和最终时限。调度程序维持一个可运行的进程列表，按最终时限排序，每次调度一个最终时限最早的进程得到CPU 。当新进程就绪时，系统检查其最终时限是否在当前运行的进程结束之前，如果是，则抢占当前进程。由于是动态算法，最早最终优先调度的优点就是灵活，当进程数不超过负载时，资源分配更优，但也同样由于它的动态属性，进程的优先级都是在不断变化中的，所以也没有哪个进程是一定可以保证满足调度的，当进程数超过负载时，资源分配合理度会急速下降，所以不太稳定。

E. 操作系统的进程调度算法[总结]

操作系统的进程调度算法直接关系到用户的使用体验。

如果把用户的体验时间，引入到计算机里面，我们引入以下几个概念。

周转时间，指作业从提交系统开始，直到作业完成为止的时间间隔。包括：

是指作业周转时间与作业实际运行服务时间的比值。
平均周转时间和平均带权周转时间是衡量批处理系统调度算法的重要准则。

先来先服务调度算法（First Come First Served, FCFS）是最简单的调度算法，可以用于作业调度和进程调度。
按照作业进入系统后备作业队列的先后次序来挑选作业，加入就绪队列，等待执行。

FCFS是非抢占式的，易于实现，效率不高，性能不好.
有利于长作业（CPU繁忙性）而不利于短作业（I/O繁忙性）。

服务时间：作业需要运行的时间
完成时间 = 开始时间 + 服务时间
等待时间 = 开始时间 - 提交时间
周转时间 = 完成时间 - 提交时间
带权周转时间 = 周转时间 / 服务时间
响应比 = （等待时间 + 服务时间） / 服务时间 = 等待时间/服务时间 + 1

该算法每次从后备作业队列中挑选估计服务时间最短的一个或几个作业，
将他们调入内存，分配必要的资源，创建进程并放入就绪队列。
在进程调度中的原理类似。

SJF是非抢占式的，优先照顾短作业，具有很好的性能，降低平均等待时间，提高吞吐量。
但是不利于长作业，长作业可能一直处于等待状态，出现饥饿现象；
完全未考虑作业的优先紧迫程度，不能用于实时系统。

高响应比优先调度算法（Highest Reponse Ratio First, HRRF）是非抢占式的，主要用于作业调度。
基本思想：每次进行作业调度时，先计算后备作业队列中每个作业的响应比，挑选最高的作业投入系统运行。
响应比 = （等待时间 + 服务时间） / 服务时间 = 等待时间 / 服务时间 + 1

由响应比分析可知，该算法介于FCFS和SJF之间，但是每次需要计算每个作业的响应比，增加系统开销。