进程的三种状态：

1、等待态：等待某个事件的完成；

2、就绪态：等待系统分配处理器以便运行

3、运行态：占有处理器正在运行

 

三种状态的转化：

运行态到等待态：往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的；

等待态到就绪态：等待的条件已经满足，只需要分配到处理器后就能运行；

就绪态到运行态：系统按某种策略选中就绪队列中的一个进程占用处理器；

运行态到就绪态：由于外界原因是运行状态的进程让出处理器，例如有更高优先级的进程来抢占处理器，或时间片（时间片是系统分配给程序的运行时间）用完。

 

调度方式：

剥夺方式：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给他的处理机，将之分配给其他进程，剥夺原则有：优先权原则、短进程优先原则、时间片原则。

非剥夺方式：分配程序一旦吧处理机分配给某进程后便让他一直运行下去，知道进程完成或发生事件而阻塞时，才把处理机分配给另一个进程。

 

进程调度算法有：

1、先来先服务调度算法（FCFS，first come first served）：谁第一个排队，谁就先被执行，在它执行过程中，不会中断它；

2、短作业优先调度算法（SJF，shortest job first）：对预计执行时间短的进程有限分配处理机，通常后来的短进程不会抢先正在执行的进程；对长进程非常不利，可能长时间得不到执行。

3、最高响应比优先法（HRRN，highest response radio next）：对于FCFS和SJF的平衡，FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF只考虑了执行时间而未考虑等待时间的长短，因此两种算法在某种极端的情况下会带来某些不便。HRRN通过综合这两种情况算出响应比R，根据响应比完成调度。优点：长作业也有机会投入运行，缺点：每次调度前要计算响应比。

4、时间片轮转法（RR，Round-Robin）：采用剥夺方式，每个进程被分配一个时间段，按照在队列中的顺序交替执行；不利于处理紧急作业。

5、多级反馈队列（multilevel feedback queue）: UNIX使用这种调度算法；进程在进入待调度的队列等待时，首先进入优先级最高的Q1中等待；首先调度优先级高的队列中的进程。若高优先级队列中已经没有调度的进程，则调度次优先级队列的进程；同一队列中的各个进程按照时间片轮转调度；在低优先级队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（剥夺）。

 

多级反馈队列算法实例：

假设3个反馈队列Q1，Q2，Q3，时间片分别是2、4、8

三个进程J1，J2，J3，到达时刻为0，1，3；需要执行时间为3，2，1个时间片

0、时刻0，J1进入Q1，执行一个时间片J1(1)，到达时刻1；

1、时刻1，J2到达进入Q2，等待，J1(1)在Q1中执行一个时间片，得到J1(2)，Q1时间片用完，到达时刻2；

2、时刻2，J1(2)进入Q2等待，J2开始在Q2中执行一个时间片得到J2(1)，到达时刻3；

3、时刻3，J3到达，因为此时Q1为空，所以进入Q1等待，但此时J2(1)在Q2中还在执行，J2(1)在Q2中执行一个时间片，得到J2(2)，完成J2，到达时刻4；

4、时刻4，此时Q1中是未执行的J3，Q2中是J1(2)，所以J3再Q1中执行一个时间片得到J3(1)，完成J3，到达时刻5；

5、时刻5、J1(2)在Q2中执行一个时间片，得到J1(3)，完成。