(1)进程调度算法

2020-12-09  本文已影响0人  hedgehog1112

也称 CPU 调度算法:CPU空闲时,操作系统给内存中「就绪」进程分配 CPU

1、什么时候会发生CPU调度?进程从 运行 转到 1等待 / 2就绪 / 4终止 状态,3等待就绪

    1 和 4 「非抢占式」:完成当前运行,才让cpu

    2 和 3 「抢占式调度」:可被打断,把 CPU 让出。分时间片、优先权、短作业优先原则

    ps:2 通常是时间片,时间片到了就中断,抢占运行进程,从而占CPU

2、调度算法影响等待时间(就绪队列中等调度时间总和),不影响进程用 CPU 和 I/O 时间

3、常见调度算法:1先来先服务、2最短作业优先、3高响应比优先、4时间片轮转、5最高优先级、6多级反馈队列

一、先来先服务调度算法(First Come First Severd, FCFS )

最简单,非抢占式:选最先进队列的进程,运行到进程退出或被阻塞,从队列中选第一个接着运行

ps:但当长作业先运行,短作业等待时间长,不利于短作业

适用:CPU 繁忙型作业系统,不适用: I/O 繁忙型作业系统

二、最短作业优先调度算法(Shortest Job First, SJF)

运行时间最短进程,提高吞吐量

对长作业不利,造成极端,长作业长期不会被运行

三、高响应比优先调度算法((Highest Response Ratio Next, HRRN))

权衡长短作业:计算「响应比优先级」,把最高进程投入运行

公式说明:

    「等待时间」相同,「要求服务时间」越短「响应比」越高短作业易被选中

    「要求的服务时间相同,「等待时间」越长,「响应比」就越高兼顾长作业,因响应比随等待时间增加而提高,等待足够长,响应便升高,获得运行的机会

四、时间片轮转调度算法

使用最广,最古老、简单、公平且的算法

1、每个进程被分配一个时间片(Quantum),允许该时间段运行

    时间片用完,进程还运行,把进程从 CPU 释放,CPU 分配出去

    时间片结束前结束,CPU 立即切换

2、时间片长度很关键:太短过多进程上下文切换,降低CPU效率;太长对短作业响应时间变长;通常 20ms~50ms折中值。

五、最高优先级调度算法(Highest Priority First,HPF)

多用户系统,希望调度有优先级,选最高运行

    1、静态优先级:创建进程时,确定优先级,不会变

    2、动态优先级:根据动态变化调整,如果运行时间增加则降低优先级,就绪队列等待时间增加,升高,就是随时间推移增加等待进程优先级

两种处理分,非抢占式和抢占式。

缺点,低优先级永不运行

六、多级反馈队列调度算法(Multilevel Feedback Queue)

「时间片轮转算法」和「最高优先级算法」综合和发展。

 多级:多个队列,优先级高到低,优先级越高时间片越短

 反馈:新优先级高加进来,立刻停止当前运行

如何工作

    1)新进程,放到第一级队列末尾先来先服务排队等待被调度,

    2)第一级队列时间片内没运行完转第二级队列末尾

    3)运行时,有新高,停止运行,移入原队列末尾

    4)短作业可能在一级很快被处理完。长作业,一级处理不完转移,虽然等待时间变长,但运行时间更长

兼顾了长短作业,同时有较好响应时间

https://mp.weixin.qq.com/s/JWj6_BF9Xc84kQcyx6Nf_g

上一篇下一篇

猜你喜欢

热点阅读