进程间调度
当计算机系统是多道程序设计系统时，通常就会有多个进程或者线程同时竞争CPU。只要有两个或者多个进程处于就绪状态，这种情况就会发生。如果此时只有一个CPU可用，那么就必须选择下一个要运行的进程。
在操作系统中完成选择工作的这一部分称为调度程序，该程序使用的算法称为调度算法。
一、何时调度
- 在创建一个新进程后，需要决定是运行父进程还是运行子进程。
- 在一个进程退出时必须做出调度决策。
- 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。
- 在一个I/O中断发生时，必须做出调度决策。
- 在分时系统中，当一个时钟中断发生时。
二、调度算法
1.先来先服务FCFS(first-come first-served)
这是最简单的调度算法,按先后顺序调度。
- 按照作业提交或进程变为就绪状态的先后次序,分派CPU;
- 当前作业或进程占用CPU,直到执行完或阻塞,才出让CPU(非抢占方式)。
- 在作业或进程唤醒后(如I/O完成),并不立即恢复执行,通常等到当前作业或进程出让CPU。最简单的算法。
FCFS的特点
- 比较有利于长作业,而不利于短作业。
- 有利于CPU繁忙的作业,不利于I/O繁忙的作业。
2.最短作业优先SJF(shortest job first)
这是对FCFS算法的改进，目的是为了缩短平均周转时间。
对预计执行时间短的作业(进程)优先分派处理机。通常后来的短作业不抢先正在执行的作业。
SJF的特点
优点:
- 比FCFS改善平均周转时间和平均带权周转时间,缩短作业的等待时间;
- 提高系统的吞吐量;
缺点:
- 对长作业非常不利,可能长时间得不到执行;
- 未能依据作业的紧迫程度来划分执行的优先级;
- 难以准确估计作业(进程)的执行时间,从而影响调度性能。
3.轮转调度
一种最古老、最简单、最公平且使用最广的算法是轮转调度。每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段内运行。
- 如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程。
- 如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换。
时间片长度变化的影响
- 过长->退化为FCFS算法,进程在一个时间片内都执行完,响应时间长。
- 过短->用户的一次请求需要多个时间片才能处理完,上下文切换次数增加,响应时间长。
时间片长度的确定
- 系统的响应时间: T(响应时间) = N(进程数目) * q(时间片)
- 就绪进程的数目: 数目越多,时间片越小
- 系统的处理能力: 应当使用户输入通常在一个时间片内能处理完,否则使响应时间,平均周转时间和平均带权周转时间延长。
4.优先级调度
基本思想：每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。
优先级又被分为静态优先级和动态优先级。
静态优先级
创建进程时就确定,直到进程终止前都不改变。通常是一个整数。依据:
- 进程类型(系统进程优先级较高)
- 对资源的需求(对CPU和内存需求较少的进程,优先级较高)
- 用户要求(紧迫程度和付费多少)
动态优先级
在创建进程时赋予的优先级,在进程运行过程中可以自动改变,以便获得更好的调度性能。如:
- 在就绪队列中,等待时间延长则优先级提高,从而使优先级较低的进程在等待足够的时间后,其优先级提高到可被调度执行;
- 进程每执行一个时间片 就降低其优先级 从而一个进程持续执行时,其优先级降低到出让CPU。
三、线程调度
当若干进程都有多个线程时，就存在两个层次的并行：线程和进程。
在这样的系统中调度处理有本质差别，这取决于所支持的是用户级线程还是内核级线程（或者两者都支持）。
用户级线程
因为内核不知道有线程的存在，所以内核还是像以前一样操作，选取一个进程，假设为A，并给予A以时间片控制。A中的线程调度程序决定哪个线程运行，假设为A1。
由于多道线程并不存在时钟中断，所以这个线程可以随意运行多长时间，如果该线程用完了进程的所有时间片，内核就会选择另外一个进程运行。
在进程A终于又一次运行时，线程A1会接着运行。该线程会继续耗费A进程的所有时间，直到它完成工作。并且这种行为不会影响到其他的进程。
现在考虑A线程每次CPU计算的工作比较少的情况，例如在50ms的时间片里有5ms的计算工作。于是，每个线程运行一会儿，然后把CPU交回给线程调度程序。
这样在内核切换到进程B之前，就会有序列A1,A2,A3,A1,A2,A3,A1,A2,A3,A1。如下图所示。
内核级线程
内核选取一个特定的线程运行，它不用考虑该线程属于哪个进程（如果有必要它也可以这样做）。内核对被选择的线程赋予一个时间片，如果超出了时间片就会强行挂起这个线程。
一个线程在50ms的时间片内，5ms之后被阻塞，在30ms的时间段中，线程的顺序会是A1,B1,A2,B2,A3,B3。如下图所示。
用户级线程和内核级线程之间的差别在于性能。
用户级线程的线程切换需要少量的机器指令；
内核级线程需要完整的上下文切换，修改内存印象，使高速缓存失效，这导致了若干数量级的延迟。
另一方面，在使用内核级线程时，一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。