操作系统-处理机调度详解（调度层次及FCFS、SPF、RR等算法）

灰太狼 2022-10-21 11:52 481阅读 0赞

**目录**

调度层次

处理机调度算法

评价指标

非剥夺式/抢占式

非抢占式优先级调度算法

先来先服务（FCFS）

短进程优先（SPF）

响应比优先算法（HRRN）

剥夺式/抢占式

最短剩余时间优先（SRTN）

时间片轮转调度算法（RR）

抢占式优先级调度算法

多级反馈队列

HRRN的Go实现

设计

全部代码

结果

参考

--------------------

# 调度层次 #

1.**高级调度**（High Level Scheduling)高级调度又称长程调度或**作业调度**，它的调度对象是**作业**。主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。  
2.**低级调度**（Low Level Scheduling)低级调度又称为**进程调度**或短程调度，其所调度的对象是**进程**（或内核级线程）。其主要功能是，根据某种算法，**决定就绪队列中的哪个进程应获得处理机**，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。  
3.**中级调度**（Intermediate Scheduling)中级调度又称为**内存调度**。引入中级调度的主要目的是，**提高内存利用率和系统吞吐量**。为此，应把那些暂时不能运行的进程，调至外存等待，此时进程的状态称为就绪驻外存状态（或挂起状态）。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。

<table style="width:500px;">  调度层次对比  
 <thead> 
  <tr> 
   <th>级别</th> 
   <th>发生地</th> 
   <th>频率</th> 
   <th>对进程的影响</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>高级</td> 
   <td>外存-&gt;内存（面向作业）</td> 
   <td>最低</td> 
   <td>无-&gt;创建态-&gt;就绪态</td> 
  </tr> 
  <tr> 
   <td>中级</td> 
   <td>外存-&gt;内存（面向进程）</td> 
   <td>中等</td> 
   <td> <p>挂起态-&gt;就绪态</p> <p>（阻塞挂起-&gt;阻塞态）</p> </td> 
  </tr> 
  <tr> 
   <td>低级</td> 
   <td>内存-&gt;CPU</td> 
   <td>最高</td> 
   <td>就绪态-&gt;运行态</td> 
  </tr> 
 </tbody> 
</table>

# 处理机调度算法 #

我们以低级调度为例

进程调度的任务主要有：

*  **保存处理机的现场信息**。在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。
 *  **按某种算法选取进程**。调度程序按某种算法从就绪队列中选取一个进程，**将其状态改为运行状态**，并准备把处理机分配给它。
 *  **把处理器分配给进程**。由分派程序把处理器分配给该进程，此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它**从上次的断点处恢复运行。**

## 评价指标 ##

**CPU利用率**

使用时间/总时间

**系统吞吐量**

完成的进程/总时间

**周转时间**

*  周转时间=进程完成时间-进程提交时间
 *  平均周转时间=所有进程周转时间之和/进程数
 *  带权周转时间=进程周转时间/进程运行时间，带权周转时间>=1，越接近1，用户满意度越高
 *  平均带权周转时间=带权周转时间/进程数

**等待时间**

等待时间=周转时间-运行时间（等待I/O也算运行时间）

平均等待时间=等待时间/进程数

**响应时间**

用户提交请求到首次产生响应所用的时间。

## 非剥夺式/抢占式 ##

适合早期批处理操作系统

### 非抢占式优先级调度算法 ###

选择已到达的进程中，优先级最高的进行调度，若优先级相同，选择先到达的。

**例题**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][]

调度顺序：P1->P3->P2->P4

*  P1：0到达，运行7，7结束
 *  P2：2到达，运行4，12结束
 *  P3：4到达，运行1，8结束
 *  P4：5到达，运行4，16结束

周转时间

*  P1：7-0=7
 *  P2：12-2=10
 *  P3：8-4=4
 *  P4：16-5=11

平均周转时间：8

带权周转时间：

*  P1：7/7=1
 *  P2：10/4=2.5
 *  P3：4/1=4
 *  P4：11/4=2.75

平均带权周转时间：2.56

等待时间：

*  P1：7-7=0
 *  P2：10-4=6
 *  P3：4-1=3
 *  P4：11-4=7

平均等待时间：4

### 先来先服务（FCFS） ###

first come,first service，按照到达的先后顺序来调度

优点：公平，实现简单，不会导致饥饿

缺点：对运行时间长的进程有利，对运行时间短的进程不友好

**例题**

有如下进程，根据到达时间和运行时间，计算进程的周转时间、带权周转时间、等待时间，及对应平均时间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][]

*  P1：0到达，运行7，7结束
 *  P2：2到达，运行4，11结束
 *  P3：4到达，运行1，12结束
 *  P4：5到达，运行4，16结束

周转时间

*  P1：7-0=7
 *  P2：11-2=9
 *  P3：12-4=8
 *  P4：16-5=11

平均周转时间：8.75

带权周转时间：

*  P1：7/7=1
 *  P2：9/4=2.25
 *  P3：8/1=8
 *  P4：11/4=2.75

平均带权周转时间：3.5

等待时间：

*  P1：7-7=0
 *  P2：9-4=5
 *  P3：8-1=7
 *  P4：11-4=7

平均等待时间：4.75

### 短进程优先（SPF） ###

由于FCFS的缺点，于是提出了SPF。shortest process first，运行时间短的进程，优先级高。运行时间相同，先来的先运行。

优点：几乎同时到达的情况下，可以得到最短的平均周转时间和平均等待时间

缺点：对短作业有利，最长作业不友好，可能造成饥饿现象

**例题**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][]

还是上面那个，调度顺序P1->P3->P2->P4

*  P1：0到达，运行7，7结束
 *  P2：2到达，运行4，12结束
 *  P3：4到达，运行1，8结束
 *  P4：5到达，运行4，16结束

周转时间

*  P1：7-0=7
 *  P2：12-2=10
 *  P3：8-4=4
 *  P4：16-5=11

平均周转时间：8

带权周转时间：

*  P1：7/7=1
 *  P2：10/4=2.5
 *  P3：4/1=4
 *  P4：11/4=2.75

平均带权周转时间：2.56

等待时间：

*  P1：7-7=0
 *  P2：10-4=6
 *  P3：4-1=3
 *  P4：11-4=7

平均等待时间：4

### 响应比优先算法（HRRN） ###

考虑等待时间和运行时间，**综合了FCFS和SPF**，对于长作业，等待时间长，响应比增大，不会饥饿

响应比=（等待时间+运行时间）/运行时间，响应比>=1，越大越优先，关注进程结束时剩余各进程响应比

**例题**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][]

时刻表如下，绿色运行，黄色结束，括号内为响应比：

0：P1(7/7，7)

7：P3((3+1)/1=4)、P2((5+4)/4=2.25)、P4((2+4)/4=1.5)、P1

8：P2((6+4)/4=2.5)、P4((3+4)/4=1.75)、P3、P1

12：P4((7+4)/4=2.75)、P2、P3、P1

16：P4、P2、P3、P1

调度顺序：P1->P3->P2->P4

周转时间

*  P1：7-0=7
 *  P2：12-2=10
 *  P3：8-4=4
 *  P4：16-5=11

平均周转时间：8.75

带权周转时间：8

*  P1：7/7=1
 *  P2：10/4=2.5
 *  P3：4/1=4
 *  P4：11/4=2.75

平均带权周转时间：2.56

等待时间：

*  P1：7-7=0
 *  P2：10-4=6
 *  P3：4-1=3
 *  P4：11-4=7

平均等待时间：4.25

## 剥夺式/抢占式 ##

适合分时、实时操作系统

### 最短剩余时间优先（SRTN） ###

**例题**

Shortest Remaining Time Next，最短剩余时间优先，剩余时间相同，先到达的先运行。关注有**新进程到达时刻以及进程完成时刻**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][]

时刻表如下，绿色代表运行的，黄色代表结束的

0：P1(7)

2：P2(4)、P1(5)

4：P3(1)、P2(2)、P1(5)

5：P2(2)、P4(4)、P1(5)、P3(0)

7：P4(4)、P1(5)、P2(0)、P3(0)

11：P1(5)、P4(0)、P2(0)、P3(0)

16：P1(0)、P4(0)、P2(0)、P3(0)

调度顺序：P1->P2->P3->P2->P4->P1

*  P1：0到达，运行7，16结束
 *  P2：2到达，运行4，7结束
 *  P3：4到达，运行1，5结束
 *  P4：5到达，运行4，11结束

周转时间

*  P1：16-0=16
 *  P2：7-2=5
 *  P3：5-4=1
 *  P4：11-5=6

平均周转时间：7

带权周转时间：

*  P1：16/7=2.28
 *  P2：5/4=1.25
 *  P3：1/1=1
 *  P4：6/4=1.5

平均带权周转时间：1.5

等待时间：

*  P1：16-7=9
 *  P2：5-4=1
 *  P3：1-1=0
 *  P4：6-4=2

平均等待时间：3

### 时间片轮转调度算法（RR） ###

Round-Robin，就绪队列中，新到达的进程排在同时刻下处理机的进程后面。时间片未使用完，进程结束，主动释放CPU。

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。  
另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，\*系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][]

时间片为2

0：P1到达，P1运行

2：P2到达，P1运行一个时间片完毕，就绪队列为P2(4)、P1(5)，P2运行

4：P3到达，P2运行一个时间片完毕，就绪队列为P1(5)、P3(1)、P2(2)，P1运行

5：P4到达，就绪队列P3(1)、P2(2)、P4(4)

6：P1运行一个时间片完毕，就绪队列P3(1)、P2(2)、P4(4)、P1(3)，P3运行

7：**P3运行完毕**，就绪队列P2(2)、P4(4)、P1(3)，P2运行

9：**P2运行完毕**，就绪队列P4(4)、P1(3)，P4运行

11：P4运行一个时间片完毕，就绪队列P1(3)、P4(2)，P3运行

13：P3运行一个时间片完毕，就绪队列P4(2)、P1(1)，P4运行

15：**P4运行完毕**，就绪队列P1(1)，P1运行

16：**P1运行完毕**

调度顺序：P1->P2->P1->P3->P2->P4->P3->P4->P1

*  P1：0到达，运行7，首次运行时间0，16结束
 *  P2：2到达，运行4，首次运行时间2，9结束
 *  P3：4到达，运行1，首次运行时间6，7结束
 *  P4：5到达，运行4，首次运行时间9，15结束

响应时间：

*  P1：0-0=0
 *  P2：2-2=0
 *  P3：6-4=2
 *  P4：9-5=4

### 抢占式优先级调度算法 ###

实时操作系统用的更多，关注就绪队列改变（新到达进程优先级可能比正在运行的更高）和进程主动释放CPU的时刻

优点：优先级可实时动态调整，适用于实时操作系统，很灵活

缺点：有源源不断的高优先级进程到达，造成饥饿现象

*  系统进程优先级高于用户进程
 *  前台进程优先级高于后台进程
 *  操作系统更偏好I/O型进程（或称I/O繁忙型进程）

**例题**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][]

调度顺序：P1->P2->P3->P2->P4->P1

*  P1：0到达，运行7，16结束
 *  P2：2到达，运行4，7结束
 *  P3：4到达，运行1，5结束
 *  P4：5到达，运行4，11结束

时刻表如下：

0：P1到达，就绪队列：P1(7,1)，P1运行

2：P2到达，就绪队列：P2(4,2)，P2运行，P1(5,1)进入就绪队列

4：P3到达，就绪队列：P3(1,3)、P1(5,1)，P3运行，P2(2,2)进入就绪队列

5：P3运行完毕，P4到达，就绪队列：P2(2,2)、P4(4,2)、P1(5,1)，P2运行

7：P2运行完毕，就绪队列：P4(4,2)、P1(5,1)，P4运行

11：P4运行完毕，就绪队列：P1(5,1)，P1运行

16：P1运行完毕

响应时间：

*  P1：0-0=0
 *  P2：2-2=0
 *  P3：4-4=0
 *  P4：7-5=2

### 多级反馈队列 ###

前面的几个

设置多级就绪队列，各级队列**优先级从高到低**，**时间片从小到大**。新进程到达时先进入**第1级**队列，按**FCFS原则**排队等待被分配时间片。若**用完时间片进程还未结束**，则进程**进入下一级队列队尾**。如果此时已经在最下级的队列，则**重新放回最下级队列队尾**。只有**第k级队列为空时**，**才会为k+1级队头的进程分配时间片**。**被抢占处理机的进程**重新放回**原队列队尾**。

FCFS和SPF太过简单，我们就实现一个HRRN

# HRRN的Go实现 #

## 设计 ##

**进程结构体的设计**

// 进程
    type  Process struct{
    	Pid int      // 进程id
    	Pname string // 进程名
    	Runtime int  // 运行时间
    	Priority int // 优先数
    }

优先数没有用到，是为了以后想再实现其他算法时能够兼容一下。

**就绪队列节点的设计**

// 就绪队列节点
    type Node struct {
    	p *Process    // 进程
    	Arrtime int // 到达时间
    	Waittime int // 等待时间
    }

就绪队列清楚进程什么时候到达，等待了多久。队列就使用切片，如果使用C++实现，可以使用vector等stl。

**处理机的设计**

// 处理机
    type Processor struct {
    	p *Process
    }
    
    // 运行
    func (p *Processor) Run() bool {
    	println("running", p.p.Pname)
    	p.p.Runtime --
    	if p.p.Runtime == 0{
    		println(p.p.Pname,"finish")
    		p.p = nil // 进程移除内存
    		return true
    	}
    	return false
    }

处理机上面就是进程，有运行进程的功能，运行完毕将其移出内存。

## 全部代码 ##

package main
    
    import (
    	"fmt"
    )
    
    // 进程
    type  Process struct{
    	Pid int      // 进程id
    	Pname string // 进程名
    	Runtime int  // 运行时间
    	Priority int // 优先数
    }
    
    // 固定优先数进程创建
    func New(pid,runtime int,pname string) *Process {
    	return &Process{
    		Pid: pid,
    		Pname: pname,
    		Runtime: runtime,
    		Priority: 0,
    	}
    }
    
    // 就绪队列节点
    type Node struct {
    	p *Process    // 进程
    	Arrtime int // 到达时间
    	Waittime int // 等待时间
    }
    
    // 进程移除就绪队列
    func Pop(b *[]Node,index int){
    	//-----索引越界------
    	if index<0 || index>=len(*b){
    		return
    	}
    	//------前删-------
    	if index == 0{
    		*b = (*b)[1:]
    		return
    	}
    	//------尾删-------
    	if index == len(*b)-1{
    		*b = (*b)[:len(*b)-1]
    		return
    	}
    	//------中间删------
    	*b = append((*b)[0:index],(*b)[index+1:]...)
    	return
    }
    
    // 处理机
    type Processor struct {
    	p *Process
    }
    
    // 运行
    func (p *Processor) Run() bool {
    	println("running", p.p.Pname)
    	p.p.Runtime --
    	if p.p.Runtime == 0{
    		println(p.p.Pname,"finish")
    		p.p = nil // 进程移除内存
    		return true
    	}
    	return false
    }
    
    // 进程到达
    func ProcessCome(queue []Node, time int) []Node {
    	// 进程到达
    	if time == 0{
    		queue = append(queue, Node{
    			p: New(0,7,"P1"),
    			Arrtime: 0,
    		})
    		fmt.Printf("%d %s 到达\n",time,"P1")
    	}
    	if time == 2{
    		queue = append(queue, Node{
    			p: New(1,4,"P2"),
    			Arrtime: 2,
    		})
    		fmt.Printf("%d %s 到达\n",time,"P2")
    	}
    	if time == 4{
    		queue = append(queue,Node{
    			p: New(2,1,"P3"),
    			Arrtime: 4,
    		})
    		fmt.Printf("%d %s 到达\n",time,"P3")
    	}
    	if time == 5{
    		queue = append(queue, Node{
    			p: New(3,4,"P4"),
    			Arrtime: 5,
    		})
    		fmt.Printf("%d %s 到达\n",time,"P4")
    	}
    	return queue
    }
    
    // 从就绪队列选择进程分配给处理机
    func HRRN(queue []Node,p *Processor)  {
    	// 处理机上进程完成标志
    	finish := true
    	for time:=0;;time++{
    		queue = ProcessCome(queue,time)
    		println("queue 长度：",len(queue))
    		// 就绪队列和处理机中都没有进程，结束
    		if len(queue) == 0 && p.p == nil{
    			break
    		}
    		// 处理机上需要进程
    		if finish == true{
    			max := 0.0
    			index := -1
    			var runP Node
    			// 遍历就绪队列
    			for i,p := range queue{
    				//println(p.p.Pname,p.Waittime)
    				ratio := 1.0 + float64(p.Waittime)/float64(p.p.Runtime)
    				fmt.Printf("%s响应比%f\n",p.p.Pname,ratio)
    				if  ratio > max{
    					max = ratio
    					index = i
    					runP = p
    				}else if ratio < max{
    
    				}else {
    					// 响应比相同，先到达的先运行
    					if runP.Arrtime > p.Arrtime{
    						max = ratio
    						index = i
    						runP = p
    					}
    				}
    			}
    			// 就绪队列的进程放入处理机
    			p.p = runP.p
    			//就绪队列进程移除
    			Pop(&queue,index)
    		}
    		// 处理机运行进程
    		if p.p != nil{
    			finish = p.Run()
    		}
    		// 就绪队列进程等待时间增加
    		for i := range queue{
    			queue[i].Waittime ++
    		}
    	}
    	fmt.Println("就绪队列没有进程，处理机处于监听状态")
    }
    
    func main()  {
    	// 就绪队列
    	queue := make([]Node,0)
    	// 处理机
    	p := Processor{}
    	HRRN(queue,&p)
    }

## 结果 ##

> 0 P1 到达  
> queue 长度： 1  
> P1响应比1.000000  
> running P1  
> queue 长度： 0  
> running P1  
> 2 P2 到达  
> queue 长度： 1  
> running P1  
> queue 长度： 1  
> running P1  
> 4 P3 到达  
> queue 长度： 2  
> running P1  
> 5 P4 到达  
> queue 长度： 3  
> running P1  
> queue 长度： 3  
> running P1  
> P1 finish  
> queue 长度： 3  
> P2响应比2.250000  
> P3响应比4.000000  
> P4响应比1.500000  
> running P3  
> P3 finish  
> queue 长度： 2  
> P2响应比2.500000  
> P4响应比1.750000  
> running P2  
> queue 长度： 1  
> running P2  
> queue 长度： 1  
> running P2  
> queue 长度： 1  
> running P2  
> P2 finish  
> queue 长度： 1  
> P4响应比2.750000  
> running P4  
> queue 长度： 0  
> running P4  
> queue 长度： 0  
> running P4  
> queue 长度： 0  
> running P4  
> P4 finish  
> queue 长度： 0  
> 就绪队列没有进程，处理机处于监听状态

就绪队列和处理机都没有进程的话，处理机应处于监听状态而不是关闭，这里没有让用户输入进程的信息，而是放到了ProcessCome函数中，所以就直接结束程序了，毕竟只是为了熟悉算法嘛。算法的核心在于处理机上进程结束时选择响应比高的进程调度进处理机运行，响应比相同时，按到达时间，先来先服务。

# 参考 #

《计算机操作系统 汤小丹，汤小赢等》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221021/6d1d7a71fd9d4913a04723b5911561c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1]: /images/20221021/ebe69b3fff2d4cb9b2a483fa07d19fde.png