搭建网站是什么工作,南阳关键词优化,wordpress固定连接如何设置,商城网站开发网1 背景
1.1 上下文切换:
切换CPU的当前任务, 从一个进程/线程到另一个保存当前进程/线程在PCB/TCB中的执行上下文(CPU状态)读取下一个进程/线程的上下文
1.2 CPU调度:
从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程调度程序: 挑选进程/线程的内核函数(通过…1 背景
1.1 上下文切换:
切换CPU的当前任务, 从一个进程/线程到另一个保存当前进程/线程在PCB/TCB中的执行上下文(CPU状态)读取下一个进程/线程的上下文
1.2 CPU调度:
从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程调度程序: 挑选进程/线程的内核函数(通过一些调度策略)什么时候进行调度?
1.3 内核运行调度程序的条件(满足一条即可):
一个进程从运行状态切换到等待状态一个进程被终结了
1.4 抢占式调度
大部分时候应用程序在运行的过程中是以用户态进程的形式存在的, 一旦启动了一个进程之后, 就会存在两种情况, 可抢占和不可抢占:
不可抢占:
调度程序必须等待事件结束
可以抢占:
调度程序在中断被相应后执行当前的进程从运行切换到就绪, 或者一个进程从等待切换到就绪当前运行的进程可以被换出
是否可以抢占: 当一个用户进程执行系统调用, 如果系统调用在内核中不会导致这个进程处于等待状态, 这个调用正常返回会返回到发起这个系统调用的进程继续执行, 即不会在内核中发生抢占现象, 称为内核的不可抢占. 如果系统调用期间, 内核切换到了别的进程执行, 那么返回到用户态会返回到另一个用户进程, 称为内核的可抢占.
2 调度原则
2.1 调度策略
2.2 程序执行模型
程序在CPU突发和I/O中交替:
每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU在时间分片机制下, 线程可能在结束当前CPU突发前被迫放弃CPU
2.3 比较调度算法的准则
CPU使用率: CPU处于忙状态所占时间的百分比吞吐量: 在单位时间内完成的进程数量周转时间: 一个进程从初始化到结束等待时间: 进程在就绪队列中的总时间响应时间: 从一个请求被提交到产生第一次响应所花费的总时间
评价快慢的一些指标:
传输文件时的高带宽玩游戏时的低延迟这两个因素是独立的
2.4 吞吐量VS延迟
调度算法的目标:
减少响应时间: 从而及时处理用户的输出并且尽快将输出提供给用户减少平均响应时间的波动: 在交互系统中, 可预测性比高差异低平均更重要增加吞吐量, 体现在两个方面: 1. 减少开销(操作系统开销, 上下文切换). 2. 系统资源的高效利用(CPU, I/O设备)减少等待时间: 减少每个进程的等待时间.
低延迟调度增加了交互式表现, 如果移动了鼠标, 但是屏幕中的光标却没动, 体验就会很差. 但是操作系统需要保证吞吐量不受影响, 想要结束长时间的编程, 所以操作系统必须不时进行调整, 即使存在许多交互任务. 吞吐量是操作系统的计算带宽, 响应时间是操作系统的计算延迟.
2.5 公平的目标
调度算法需要确立一个公平的目标, 不过这个怎么定义呢? 比如保证每个进程占用相同的CPU时间, 但是这样的话一个用户比其他用户运行更多进程怎么办. 比如保证每个进程都等待相同的时间, 公平通常会增加平均响应时间.
3 调度算法
3.1 FCFS
FCFS: 先来先服务, 即如果进程在执行中阻塞, 队列中的下一个进程会得到CPU
举例:
假设有三个任务P1, P2, P3, 执行时间分别是12, 3, 3.
首先, 当任务到达顺序为P1, P2, P3时, 如图:当任务到达顺序为P2, P3, P1时, 如图:FCFS特点: 优点: 简单 缺点: 平均等待时间波动较大花费时间少的任务可能排在花费时间长的任务后面可能导致I/O和CPU之间的重叠处理(CPU密集型进程会导致I/O设备闲置时, I/O密集型进程也在等待)3.2 SPN(SJF) SRT
SPN(SJF) SRT: 短进程优先(短作业优先), 短剩余时间优先, 选择下一个最短的进程, 按照预测的完成时间来将任务入队.
可以是可抢占的或者不可抢占的:
可抢占, 又叫Shortest-Remaining-Time(SRT: 最短剩余时间), 执行程序可打断, 并根据剩余执行时间重新确定优先级不可抢占, 执行程序不可打断
这种方法的平均等待时间是最小的.
缺点:
可能导致饥饿连续的短任务流会使长任务饥饿短任务可用时的任何长任务的CPU时间都会增加平均等待时间需要预知未来(预测等待时间算法)怎么预估下一个CPU突发的持续时间简单的解决方法: 询问用户如果用户欺骗就杀死进程如果用户不知道怎么办3.3 HRRN
HRRN: 最高响应比优先, 在SPN调度的基础上改进, 不可抢占, 关注进程等待了多长时间, 防止无限期推迟
相应比:
R (w s) / s
w: waiting time: 等待时间s: service time: 执行时间
3.4 Round Robin
Round Robin: 轮循, 使用时间切片和抢占来轮流执行任务, 在叫作量子, 或者时间切片的离散单元中分配处理器, 时间片结束时, 切换到下一个准备好的进程.
特点:
花销: 额外的上下文切换时间量子太大的话: 等待时间就会过长, 极限情况退化成FCFS时间量子太小的话: 反映迅速, 但是...吞吐量由于大量的上下文切换开销受到影响
目标:
选择一个合适的时间量子经验规则: 维持上下文切换开销处于1%以内
3.5 Multilevel Feedback Queue
Multilevel Feedback Queue: 多级反馈队列, 优先级队列中的轮循
就绪队列被划分成独立的队列(比如: 前台/交互, 后台/批处理)每个队列拥有自己的调度策略(比如: 前台RR, 后台FCFS),调度必须在队列间进行
但是进程的执行过程进程的特点会发生变化, 根据这个问题可以有如下设计:
一个进程可以在不同的队列中移动例如: n级优先级 - 优先级调度在所有级别中, RR在每个级别中:时间量子大小随优先级级别增加而增加如果任务在当前的时间量子中没有完成, 则降到下一个优先级3.6 Fair Share Scheduling
Fair Share Scheduling: 公平共享调度
FSS控制用户对系统资源的访问
一些用户组比其他用户组更重要保证不重要的组无法垄断资源未使用的资源按照每个组所分配的资源的比例来分配没有打到资源使用率目标的组获得更高的优先级
3.7 调度算法评价
确定性建模: 确定一个工作量, 然后计算每个算法的表现队列模型: 用来处理随机工作负责的数学方法实现/模拟:建立一个允许算法运行实际数据的系统最灵活/具有一般性4 实时调度
4.1 实时系统
定义:
正确性依赖于其时间和功能两方面的一种操作系统.
性能指标:
时间约束的及时性(deadlines)速度和平均性能相对不重要
主要特性:
时间约束的可预测性
分类:
强实时系统: 需要在保证的时间内完成重要的任务, 必须完成弱实时系统: 要求重要的进程优先级更高, 尽量完成, 并非必须
一些术语:
任务(工作单元): 一次计算, 一次文件读取, 一次信息传递等等属性: 取得进展所需要的资源, 实时参数周期任务任务有规律的重复周期p inter-release time (0 p)执行周期e 最大执行时间(0 e p)使用率U e / p硬时限如果错过了最后期限, 可能会发生灾难性或非常严重的后果必须验证: 在最坏的情况下是否也能满足时限保证确定性软时限 理想情况下, 时限应该被最大满足. 如果有时限没有被满足, 那么就相应地降低要求尽最大努力去满足 满足实时性要求的调度算法设计:
决定实时任务执行的顺序静态优先级调度动态优先级调度
4.2 可调度性
4.3 单调速率(RM)调度
最佳静态优先级调度通过周期安排优先级周期越短优先级越高执行周期最短的任务
4.4 截止日期最早优先(EDF)
最佳的动态优先级调度Deadline越早优先级越高执行Deadline最早的任务
5 多处理器调度
多处理器的CPU调度更加复杂
多个相同的单处理器组成一个多处理器优点: 负载共享
对称多处理器(SMP)
每个处理器运行自己的调度程序需要在调度程序中同步
6 优先级反转
可以发生在任何基于优先级的可抢占的调度机制中, 当系统内的环境强制使高优先级任务等待低优先级任务时发生.
发生原因(图示):
假设此时操作系统中有三个优先级不同的进程, 低优先级进程, 高优先级进程和中优先级进程. 在时刻先开始运行(此时优先级较高的另外两个进程还没开始运行):在时刻开始访问某个共享资源:在时刻, 未对访问完毕时, 开始跑了, 于是被抢占:在时刻需要访问此时被占用的, 由于被抢占, 所以其占用的还没有释放, 所以开始等待的释放而被挂起, 从而继续执行(此时正在使用):在时刻还未使用完之前, 开始执行, 这样又被抢占, 于是开始执行:直到时刻执行完毕, 然后继续执行, 继续访问:时刻使用完之后, 释放了, 然后开始使用, 直至执行完毕:
优先级反转的持续时间取决于其他不相关任务的不可预测的行为, 如以上例子, 的执行时间被以及影响.
解决办法:
低优先级任务继承高优先级任务的优先级依赖于他们共享的资源. 如以上例子, 在访问时由于此时正在被所占用, 所以的优先级会动态得到提升至和相同(因为被占用的原因), 使得不被抢占.优先级天花板优先级天花板: 资源的优先级和所有可以锁定该资源的任务中优先级最高的那个任务的优先级相同, 如以上例子, 的优先级跟的优先级相同.除非优先级高于系统中所有被锁定的资源的优先级上线, 否则任务尝试执行临界区的时候会被阻塞. 如以上例子, 占用执行时, 除非再来一个进程的优先级高于此时资源的优先级, 也就是的优先级, 也就是的优先级, 其可以抢占CPU执行, 否则就会被阻塞, 也就是过来时会被阻塞.持有最高优先级上限信号量的任务, 会继承被该锁所阻塞的任务的优先级.
