操作系统原理学习笔记(十三)-进程调度

操作系统原理学习笔记目录

书上的英文标识有点不统一,有的是首字母大写,有的是小写,
我不太清楚这两者有什么区别,但为了整体格式统一,我统一改成了大写。
当然,如果这种书写方式有问题,麻烦告知一下,谢谢。

进程调度的任务

  1. 保存处理机的现场信息。
  2. 按某种算法选取进程。
  3. 把处理机分配给进程。

进程调度机制

  • 排队器:将新出现的就绪状态插入响应的就绪队列。
  • 分派器:将进程从就绪队列中取出,并进行上下文切换。
  • 上下文切换器:保存当前进程上下文,将新进程上下文装入处理机的寄存器中。
    上下文切换需要执行大量指令,为了提高效率,通过移动寄存器指针的硬件实现方式进行上下文切换。

进程调度方式

早期OS使用非抢占方式,但因难以满足交互式作业与实时任务的需求,引入了抢占方式。

  • 非抢占方式(Nonoreemptive Mode):处理机分配给进程后,除非进程完成、出现I/O请求、被阻塞,进程将一直进行下去。
  • 抢占方式(Preemotive):根据不同原则,OS将当前进程处理机分配给新进程。

主要原则:

  • 优先权原则:高优先级抢占低优先级进程处理机。
  • 短进程优先原则:新进程若运行时间更短,则抢占当前进程处理机。
  • 时间片原则:进程当前时间片结束后,停止当前进程,重新进行调度。

轮转调度算法(Round Robin, RR)

本算法于P101有图解。

最简单且最常用的算法,让每个就绪队列中每个进程仅运行一个时间片,若就绪队列有n个进程,则每个进程将获得大约1/n的处理机时间。

基本原理

根据FCFS原则,将所有就绪进程排成一个就绪队列,每隔一段时间(如30ms)产生一次中断,进程调度程序调度,将CPU分配给队首进程。时间片结束,调入下个队首进程。

进程切换时机
  • 时间片未用完,进程结束,提前激活进程调度程序,并删除当前进程。
  • 时间片用完,进程未结束,将进程切至对尾。
时间片大小的确定

能完成大多任务。

优先级调度算法

优先级调度算法的类型
  • 非抢占式优先级调度算法:优先级的比较发生在切换进程时。
  • 抢占式优先级调度算法:优先级的比较发生在切换进程与出现更高优先级进程时。
优先级的类型
  • 静态优先级:进程创建时确定,运行时保持。
    用某一范围内的整数表示,例如0~255中的整数,这个整数被称为优先数。
    根据进程类型、进程对资源需求、用户要求来确定。
  • 动态优先级:根据算法的不同改变优先级,
    如随着优先级时间减少的抢占式调度,或根据进入就绪队列的次序确定的FCFS算法。

多队列调度算法

根据需求不同,将进程放入不同就绪队列,公认性能良好的算法。

多级反馈队列调度算法(Multileved Feedback Queue)

调度机制
  1. 设置多个就绪队列,每个队列不同优先级,第一队列优先级最高,时间片最短,随后队列优先级降低,时间片增加。
  2. 每个队列采用FCFS算法,进程进入内存,放入第一队列对尾,其时间片用完后,若未完成,则放入第二队列对尾。
  3. 队列间按优先级调度。
调度算法的性能
  • 终端型用户作业一般属于交互型作业,在短时间内能完成,只要第一队列时间片足够运行完成作业,则性能良好。
  • 短作业大多在第一队列能完成,即便没有,也能在二三队列完成。
  • 长批处理作业会随着运行次数的增加,而获得更长的时间片。

基于公平原则的调度算法

保证调度算法

算法在P104页有较为详细的步骤,个人总结了一下,思想还是很简单的。

相同类型的进程获得相同时间片。
跟踪进程自创建到现在的时间C,进程获得处理机的时间R,
则进程获得处理机的时间比率为N=R/C,
为N最低的进程分配处理机,直到其N不再是最低。

公平分享调度算法

每个用户获得相同处理机时间,或所要求的时间比例。

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注