【OS学习笔记】处理器管理——单处理器调度算法 / 线程

常用调度算法

一、先来先服务（FCFS）

二、短作业/短进程优先（SJF/SPF)

三、时间片轮转（RR）

时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。

四、高响应比优先（HRRF）

高响应比优先调度算法的基本思想是把CPU分配给就绪队列中响应比最高的进程。
高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。
该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：
响应比 =（等待时间+要求服务时间）/ 要求服务时间,即RR=（w+s）/s=1+w/s，因此响应比一定是大于1的。

五、优先级调度

既可用于高级调度，又可用于低级调度，还可用于实时系统。当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行。当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。

优先级

1.静态优先级：静态优先级是在创建进程时确定进程的优先级，并且规定它在进程的整个运行期间保持不变。

2.动态优先级：动态优先级是在创建进程时赋予该进程一个初始优先级，然后其优先级随着进程的执行情况的变化而改变，以便获得更好的调度性能。

在采用优先级法的低级调度中，分为抢占式和非抢占式

非抢占式优先级算法
在这种调度方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就能一直执行下去，直至完成；或因等待某事件的发生使该进程不得不放弃处理机时，系统才能将处理机分配给另一个优先级高的就绪进程。
抢占式优先级算法
在这种调度方式下，进程调度程序把处理机分配给当时优先级最高的就绪进程，使之执行。一旦出现了另一个优先级更高的就绪进程时，进程调度程序就停止正在执行的进程，将处理机分配给新出现的优先级最高的就绪进程。

六、多级反馈队列调度（MLFQ）

多级反馈队列调度算法为就绪状态的进程设置多个队列，第1级队列优先度最高，但时间片最小，以下各级队列优先度依次降低而时间片依次增加。各级队列均按先来先服务的原则排序。

优点
1、短进程优先处理。
2、系统开销不大。
3、对分时系统来说，交互型请求通常能在第一队列中完成。
缺点
如果优先级高的队列一直不为空，优先级较低的队列中的进程可能长时间无法得到运行，即会导致饥饿的发生。

七、实时调度

基本要求是保证计算机在规定的时间内对外部事件的请求做出响应。

实时调度和非实时调度的区别：

线程

线程的引入

线程是为了弥补进程的缺陷而提出并使用的。

进程在一个时段内只能做一件事。

线程

线程可以理解为CPU调度和执行的最小单元。

1 进程内的一个执行单元。
2 进程内的一个可独立调度的实体。
3 线程是进程中一个相对独立的控制流程序。
4 线程是执行的上下文。

属性

1.线程属于轻型实体，基本不拥有系统资源，只拥有为保证其运行必不可少的资源。

例如，只有一个线程控制块（TCB）、程序计数器（PC）、一组寄存器和堆栈等。
2.线程是独立调度和分派的基本单位，是能够独立运行的基本单位。
3.同一个进程中的所有线程共享该进程的全部资源。
4.线程并发执行程度高，同一进程的多个线程可以并发执行，多个进程的多个线程也可并发执行。

线程和传统进程的比较

相似之处

1.二者都有标识符（ID）、一组寄存器、状态、优先级及所要遵循的调度策略。
2.进程控制块(PCB)，线程控制块（TCB）。
3.进程中的线程共享该进程的资源，进程中的子进程也共享该进程的资源；线程和子线程的创建者可以对线程和子线程实施某些控制。

差异

1.传统进程除了是调度和分派的基本单位以外，还是资源分配的基本单位。而引入线程的操作系统中，线程只是调度和分派的基本单位。
2.线程并发执行的程度高于传统进程并发执行的程度。
3.线程的创建和撤销时空开销小于进程，切换时间小于进程。
4.
5.一个线程的数据可以直接被属于同一个进程的其他线程所使用，因此数据传递既方便又快捷。