Operating System Concepts ——chapter 6——CPU Scheduling

迷南。 2021-11-11 05:50 186阅读 0赞

调度算法目标：  
通过多道程序设计来获得尽可能大的CPU利用率。

基本算法：

### FCFS ###

first come, first server  
看起来很公平，但是并不一定合理。  
容易导致短作业进程等待时间过长。

### SJF ###

shortest job first  
选择执行时间最短的优先执行

#### 非抢占式 ####

如果一个作业已经在执行了，即使有执行时间更短的作业到达，依然保持已经在执行的作业，不进行抢占。

#### 抢占式 ####

如果一个作业已经在执行了，如果有执行时间更短的作业到达，则执行时间更短的作业被执行。

**等待时间=结束时刻-执行时间-到达时刻**

**怎么知道作业下次执行时间是多少？**  
指数平均法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMxNTY3MzM1_size_16_color_FFFFFF_t_70]

### priority scheduling ###

每个进程都被赋予一个优先级。优先级越高越先执行。  
SJF是优先级调度的一种

缺点：  
infinite blocking(饥饿)  
解决办法：  
aging.  
动态优先级，等待时间越长，优先级越高。

### Round-Robin scheduling ###

时间片轮转。一般每个时间片为10-100ms。

相比SJF，RR算法时间片会小一些，但是有更好的实时响应。

### multilevel queue ###

ready queue is partitioned int separate queues:  
forground(interactive)  
background(batch)  
Each queue has its own scheduling algorithm:  
foreground – RR  
background – FCFS

### multilevel feedback queue ###

a process can move between the various queues.  
比如随着CPU的使用变化可以在I/O-bound 队列和CPU-bound中切换。  
例如：  
3 queues:  
Q0– RR with time quantum 8 milliseconds  
Q1– RR time quantum 16 milliseconds  
Q2– FCFS  
Scheduling：  
Lower-priority processes cannot be executed only higher-priority queue is empty  
A new job enters queue Q0which is servedFCFS  
When it gains CPU, job receives 8 milliseconds  
If not finish in 8 milliseconds, moved to queue Q1.  
At Q1 job is again served FCFS and receives 16 additional milliseconds  
If it still does not complete, it is preempted and moved to queue Q2.

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMxNTY3MzM1_size_16_color_FFFFFF_t_70]: /images/20211109/d19f173b75fa41159184a3071faf5b98.png