os CH5 CPU Scheduling
CH5 CPU Scheduling
明确一点：非抢占式没有时间片的概念，因为基本每次都是运行完当前的进程（？但是抢占式的就需要时间片的概念，也就是说每次运行这么一个时间片之后，操作系统根据调度算法决定下一个跑哪一个进程
但事实上，在所有的例子中，抢占式的一般是多个进程先后到达，但是非抢占式是一开始都同时到的情况
5.1 Basic Concepts
首先回忆一下进程不同状态的概念：
CPU调度算法需要在一系列就绪态的线程/进程中选择最合适的来分配CPU资源
CPU的三级调度如下:
高级是从外存到内存，分配PCB 中级是在内存紧张的时候，换出一些到外存等待 低级是cpu调度，为某个进程分配处理机
理解一下非抢占式和抢占式；非抢占式会在运行完或者阻塞的时候才给别人cpu
调度时候做的事情：切换上下文，切换到用户模式（和合适的位置）重新启动， （运行到就绪说明时间片到了）
5.2 Scheduling Criteria（调度准则）
也就是一系列衡量调度算法好坏的指标
turnaround time：一个进程从提交给系统到完成的时间（周转时间） turnaround time = termination time – arrival time. 也就是说，从提交这些进程的时间开始到各个进程完成的时间 response time：提出请求到响应的时间 waiting time：在就绪队列中等待的时间
面向系统的准则：throughput（单位时间运行的进程数量） CPU utilization：CPU使用率（要尽可能忙碌）
同时，算法还要执行快、易于实现
综合来看，有如下考量：
5.3 Scheduling Algorithms
5.3.1 First-Come, First-Served (FCFS) Scheduling
先来先服务调度，顾名思义，就是谁先来就先服务谁
按照就绪队列排队的顺序，每次从就绪队列中取最新的进程进行执行
这是一个非抢占式算法
理解一下为什么不利于I/O繁忙型：比如说有很多的I/O操作，那么执行I/O会使得当前进程放弃CPU资源，然后I/O完成之后需要重新到队尾排队
看下面的一个例子：
容易发现，不同的进程来的顺序如果不一样，那么平均waiting turnaround时间也会不同
容易看出，这个的缺点是如果花费时间长的被安排在前面，后面的短任务不得不等待很长时间
5.3.2 Shortest-Job-First (SJF) Scheduling 短作业优先
短作业优先算法有两个版本： 1. 非抢占式：那么就是每次取一个最短的，跑完之后，在就绪队列中拿出最短的执行 2. 抢占式：又称为Shortest-Remaining-Time-First (SRTF)第一次之后，每次执行完一个时间片t，比方说现在的剩余cpu时间为a，那么看剩下的就绪队列里面有没有剩余时间小于a的，去给它执行一个时间片。
对于一组给定的进程，这个算法一定能有最低的平均等待时间
长度相等的，应该先到的先上 
这里理解一下抢占式：也就是说，每一个新到了都要衡量一下是否要替换（这里没有特定的时间片） 以及等待时间的计算：就是从到来之后，当前的不在执行等着别的跑的时间
但是，由于我们根本运行时不知道下一个进程的长度，所以实际操作起来会很复杂，开销也很大；实际中会使用估算的算法来解决，如图：
以及会产生饥饿现象：有长进程会永远调度不到
5.3.3 Priority Scheduling
优先级算法会让优先级最高的算法先执行；上面的SJF是这种算法的一个特例（也就是时间优先级） 这里对于优先级进行下面的规定：
这也有抢占式和非抢占式两种版本 重点看一下比较复杂的抢占式版本：
这自然会带来饥饿问题；解决方法是动态优先级，随着等待时间的延长相应提升优先级
5.3.4 Round-Robin Scheduling 时间片轮转调度
在先来先服务（FCFS）的基础上，增加了时间片概念，并且按照时间片顺序执行进程；如果一个时间片执行完没有结束，那么就换下一个执行 
时间片越小，响应时间越小，但是switch的成本越大
要保证平均周转时间大小合适，最好是让80%的进程长度小于时间片即可
5.3.5 多级队列调度
这个说的是，不同类型的类型需要不同的策略，因此把进程按照属性分为多个就绪队列，然后根据不同的算法实现队列间的调度，比如说看下面这个例子：
为了避免有些队列出现饥饿的情况，会采用队列之间先分配时间片，采用RR调度，然后每一个队列中自己选择内部如何调度
5.3.6 Multilevel Feedback Queue Scheduling（多级反馈队列算法）
就是一个多层次的，最上层优先级最高，但是获得的时间片最短；每次从最上面的开始先执行，FCFS，如果没有执行完，放到下一级的队尾，依此类推，从上到下一层一层执行；同时有高优先级的到来必须让其先执行
理解一下这个内容：
以及最后关注一下这个题目：
交互型进程就是多使用I/O的进程，批处理就是多使用cpu的进程
以及注意带权周转时间：周转时间除以cpu运行时间的平均值
参考一下这个例子
再注意一下这个题目：这里的三道作业相当于是说，被拿到我内存中的作业同时只能有三个
以及接下来介绍一下windows和linux实际使用的调度算法