处理机调度之进程调度
3.3进程调度
3.3.1进程调度的任务、机制和方式
1.进程调度任务
- 任务:分派CPU
- 主要过程:
- 1、保存处理机的现场信息
- 2、按某种算法选取进程
- 3、把处理器分配给新进程
2、进程调度机制
3、进程调度的方式
(1)非抢占方式
可能引发进程调度的因素可归结为:
- 1、正在执行的进程,因发生某事件而使其无法再继续运行
- 2、正在执行的进程,因提出I/O请求而暂停执行
- 3、在进程通信或同步过程中,执行了某种原语操作,如BLock原语。
- 优点:实现简单、系统开销小、适用于大多数的批处理系统。
- 缺点:及时性差。
(2)抢占方式
- 抢占必须遵守的原则
- 1、优先权原则:允许优先级高的新进程,抢占当前进程的处理机;
- 2、短进程优先原则:新到的短进程,可以抢占当前长进程的处理机;
- 3、时间片原则:正在执行的进程的一个时间片用完后,便停止该进程的执行而重新进行调度。
3.3.2轮转调度算法(RR算法)
1、轮转调度算法的基本原理
- 系统将所有的就绪进程按FCFS策略,排成一个就绪队列。
- 系统每隔一定时间,便产生一次中断,去**进程调度程序进行调度,把CPU分配给队首进程。
- 一个时间片后,又把处理机分配给就绪队列中新的队首进程。
2、进程切换时机
- 进程运行结束
- 时间片到
- 运行进程阻塞
3、时间片大小的确定
- 时间片太小,意味着会频繁地执行进程调度,实施进程上下文切换,这无疑会增加系统开销。
- 时间片太长、RR算法便退化为FCFS算法,无法满足短作业和交互式用户的需求
- 一个较为可取的时间片大小,略大于一次典型的交互所需的时间,使大多数交互式进程,能在一个时间片内完成,从而可以获得很小的响应时间。
时间片大小对响应时间的影响
4、RR算法优缺点
- 算法主要针对分时系统
- 对用户的响应及时、快速
- 时间片片的长度确定比较困难
- 进程切换开销比较大
3.3.3优先级调度算法
把处理机分配给就绪队列中优先级最高的进程。
1、优先级调度算法的类型
- (1)非抢占式优先级调度算法
- (2)抢占式优先级调度算法
2、优先级的类型
静态优先级
- 优先级通过一个整数来表示。
- 依据:进程类型、进程对资源的需求、用户要求。
动态优先级
- 是指在进程创建之初,先赋予一个优先级。
- 然后其值随进程的推进,或等待时间增加而改变,以便获得更好的性能。
3.3.4多级反馈队列调度算法
★算法思想
- 将就绪队列分为N级,每个队列不同的时间片;
- 队列级别越高,时间片越短,级别越低,时间片越长;
- 最后一级采用时间片轮转,其他队列采用先进先出;
- 系统从第一级调度,当第一级为空时,系统转向第二个队列,…当运行进程用完一个时间片,放弃CPU时,进入下一级队列;
- 等待进程被唤醒时,进入原来的就绪队列;
- 当进程第一次就绪时,进入第一级队列。
★算法要点
- 系统中设置多个就绪队列;
- 每个就绪队列分配给不同时间片,优先级高的为第一级队列,时间片最小,随着队列级别的降低,时间片加大;
- 各个队列按照先进先出调度算法;
- 一个新进程就绪后进入第一级队列;
- 进程由于等待而放弃CPU后,进入等待队列,一旦等待的事件发生,则回到原来的就绪队列;
- 当有一个优先级更高的进程就绪时,可以抢占CPU,被抢占进程回到原来一级就绪队列末尾;
- 当第一级队列空时,就去调度第二级队列,如此类推;
- 当时间片到后,进程放弃CPU,回到下一级队列。
★算法的性能
- ⑴终端型用户:由于终端型用户提交的作业多属于交互型作业,通常较小,系统只要能使这些作业在第一队列规定的时间片内完成,便可使终端型用户感到满意。
- ⑵短批处理作业用户:如果可在第一队列中执行完成,便获得与终端型作业一样的响应时间。对于稍长的短作业,也只需在第二和第三队列各执行一时间片完成,其周转时间仍然较短。
- ⑶长批处理作业用户:将依次在第1,2,…,n个队列中运行,然后再按轮转方式运行,用户不必担心其作业长期得不到处理。
3.3.5基于公平原则的调度算法
1.保证调度算法
保证调度算法向用户所做出的是明确的性能保证。
2.公平分享调度算法
在该调度算法中,调度的公平性主要是针对用户,使所有用户能获得相同的处理机时间,或所要求的时间比例。
然而调度又是以进程为基本单位。为此,必须考虑到每一个用户所拥有的进程数目。