- 本书首先简单介绍了操作系统,根据我的理解操作系统就是硬件和软件的桥梁,对于硬件(比如
CPU,内存,硬盘,IO设备等),操作系统把硬件的各种资源进行抽象,也就是书中所讲述的虚拟化(接下来的讨论一般来说都是针对于单CPU的情况),比如CPU只有一个但是需要同时运行多个程序,那么操作系统就使用时分复用的方式在一个很小的时间片段内执行不同的程序这就造成了CPU同时执行多个程序的假象,在比如对于内存资源,不同的程序运行的时候就算使用了某种特定的方法使得程序中的某些变量的地址一样,但是对于这个变量的操作却不会相互干扰,这里操作系统对于内存做了虚拟化,制造了单个程序独享内存的假象;另外由于CPU同时执行多个程序,所以这就会引发并发的问题,并发的问题在我的理解下就是软件层面的问题,比如多个线程同时访问一个共享变量;最后操作系统还需要持续存储它保存的数据,操作系统必须持久化的保存数据,所以这里就会设计文件系统等,这一个特点成为持久化
- 接下来,讲述了进程的抽象概念,进程就是运行起来的程序,
CPU通过把程序加载道内存中对于程序进行运行,这一个过程中回首先加载代码片段和数据片段(现代操作系统倾向于懒加载,需要数据才会加载),之后回初始化程序运行时栈和堆并且进行一系列初始化任务
- 之后介绍了进程的状态(注意就绪是没有调度到这一个进程,运行是调度到了这一个进程)
- 接下来介绍了与进程有关的各种
API , 这就不多说了
- 下面的一些中主要讲述了
CPU如何运行一个进程,首先提到了不受限制的运行,这就会导致用户进程可以访问系统的所有资源,所以引出了用户模式和内核模式的概念,但是当用户有时候需要访问系统资源(比如接受网络包,存储文件时),就需要转换到内核模式进行调用,所以这里引出了System call的概念,系统调用本来是普通的C库函数,但是其中利用汇编加入了trap指令得以让CPU陷入内核模式,从而执行各种操作,这里操作系统启动时加载陷阱表记录着遇到怎样的trap需要执行那一种操作
- 接下来就引出了上下文切换的概念,也就是在不同的进程之间进程切换,在此之前还讲述了操作系统如何获得执行权,主要时通过时钟中断的方式,之后加少了保存和恢复上下文的方式,操作系统需要进行调度时,首先把各种寄存器的值存储在该进程的内核栈中(比如
PCB中,PCB中就有存储者各种寄存器的结构体),同时将需要被调度的进程的内核栈中存储的寄存器的值加载道物理寄存器中并且执行该进程,比如相关指令如下:
- 在讨论完
CPU如何进行进程的切换(上下文切换)之后,书中着重讲述了进程的调度方式
- 考虑如下指标: 周期性: 也就是所有进程执行完毕之后的平均时间,响应时间: 表示进程从开始运行到被调度的时间
- 首先是
FIFO(先进先执行的原则): 也就是首先到达的进程首先执行,但是这一种调度方案使得如果一个执行时间比较长的进程首先执行就会拖慢后面的进程的执行时间
- 之后是
SJF(最短任务优先): 也就是首先执行需要时间最短的任务,虽然这一种调度方式在所有进程同时开始的时候是最优的,但是如果出现了时间长的进程首先被加载到内存中,由于这一种调度方式是非抢占性的,所以这一个进程就会拖慢后面的进程
- 之后引出了抢占式的最短任务优先(
STCF),和上面相比,如果一个长任务来到的时候就会被后面到来的任务抢占执行从而停止被调度
- 另外考虑了响应性,引出了轮询
RR的调度方式也就是进行时分复用,分出时间片来执行不同的进程,注意RR中的时间片段需要是时钟的周期的倍数从而保证可以正常利用中断进行模式的切换,另外选择时间片长度的一个方式就是考虑上下文切换的开销,但是即使选择了合适的时间片还是回使得周期时间过长
- 接下来考虑
IO操作等需要阻塞进程的操作和进程运行时间的不可知性,引入了通过历史预测从而完成调度的一种算法==MLFQ(多级反馈队列)==,在MLFQ中分出不同优先级别的队列,CPU优先执行优先级别高的队列中的任务并且轮询执行相同队列中的任务,同时在一个时间片内执行某一个任务之后使得它的优先级别下降但是如果在这一个期间有任务主动释放CPU(表示阻塞),那么优先级别不会改变,但是这就会产生那些长任务的"饥饿问题",所以又引出了提升优先级别的方法,最后为了防止某一些进程长时间占用优先级别,有引入了执行份额的方式,所以最终的调度策略如下:
- 如果
A的优先级别>B的优先级别,运行A
- 如果
A的优先级别=B的优先级别,轮询运行A和B
- 工作进入系统被放在优先级别最高的队列中
- 一旦工作用完了在某一层中的(无论中间放弃过多少次
CPU)都会降低优先级别
- 经过一段时间
S,就将系统中所有工作重新加入到最高的优先级队列中(boost)
- 最后引入了按照份额的调度方式: 引出了彩票调度和步长调度的方式,彩票调度每一段时间进行一次抽奖活动,抽到对应彩票的进程被调度,并且进程可以利用自己的货币给子任务分配彩票,抽奖时这些彩票转换为全局彩票,步长调度则是为每一进程设置步长,每一次调度完某一个进程就会给这一个进程的行程值加上步长,最后调度最小行程的进程,这一种算法保证了在很短的一个时间内实现份额的加权分配,但是当有进程需要被插入时这一个算法却难以找到合适的行程初始值,彩票调度虽然对于插入的进程的处理相对容易,但是却难以确定每一个进程的彩票数量,这两种调度方式使用很少,主要是使用
MLFQ调度策略
- 另外书中还拓展将了多处理器的调度机制,首先多处理器相对于单处理器还会出现如下的问题: 缓存的一致性,也就是所有的进程都公用一个内存,如果一个进程更新缓存中的数据就会导致内存中的数据没有及时的更新(这是由于
CPU使用回写的方式,知道该缓存中的内容被驱逐的时候才会写入到内存中),但是此时其他的CPU也是公用这一个内存,所以如果再一次读取这一个数据读取到的就是旧值,导致了缓存的一致性问题,一种可能的解决方法就是利用监控内存的访问,通过总线窥探所有缓存和内存的总线来发现内存访问,如果发现该数据被修改,就会使得缓存中的本地副本作废;第二个问题就是同步问题,也就是多线程操作同样一个共享数据时引发的并发安全问题,解决方式就是加锁,但是这会拖慢CPU执行的速度;另外一个问题就是缓存亲和性的问题,也就是说如果一个进程在某一个CPU上面运行的时候,CPU回缓存进程的许多状态,所以这一个进程下一次在这一个进程上面运行的时候就可以运行的更快,但是如果在多CPU的系统中也会面对这一个问题; 从而引出了多处理器进程调度的方式:
SQMS 简单的把所有进程放入到一个列表中,每一个CPU并行执行队列中的每一个进程,这一种调度方式会产生两个问题: 锁导致CPU执行速率被拖慢,另外一个问题就是缓存亲和性的下降,后者解决方式的就是可以牺牲某一个进程的缓存亲和性从而使得其他的CPU的大量时间执行同样一个进程,但是对于这一个被牺牲进程的调度又成为了新的问题MQMS 为每一个CPU配置队列,单个CPU执行自己队列中的操作,这样随着CPU的增加,队列的数量增加,锁和缓存的竞争就会减小,同时保证了缓存的亲和性,另外一个问题就是负载均衡的问题,如果一个队列中的任务被执行完毕那么就会导致这一个CPU处理空闲或者这一个队列中的任务占用CPU执行的大部分时间,解决方式就是工作窃取,也就是工作少的队列从工作多的队列中窃取任务(先天牛马圣体),从而保证了负载均衡,但是这里的窃取间隔时间又回成为新的问题