课件文稿助教

计算机操作助教 赵玉 按什么原则分配CPU何时分配CPU 调度的类型与调度算实时系统中的多处理 处理机管理的工作是对CPU 高级中级低级 接纳多接纳那 内外存交换：又称为“中级调度”。从器资源的角接。 非抢占抢占优先

用户该进程多半会出状至中断处理 在进程（上下文）中切换的用新把进程移至合适的队列-就绪更新被选中进程的从被选中进程中重装入CPU上下 ，就绪队列和阻塞队列中等待，结果输出等－批处外存等待时间、就绪等待时间、CPUI/O平均周转时间、带权平均周转时间 优先 作业在时间上可以。如：在2小时内完成4个作处理机利用率：－－大中型 易于执行开 不可抢一旦，直到该进程自己因调用原语操作或等待I/O因而进入阻塞状态，或时间片用完时才让，重新进抢占式 先来先服务(FCFS,FirstComeFirstService)当前作业或进程占用CPU出让CPU（非抢占方式）有利于CPU繁忙的作业，不利于I/O繁忙的作 短作业优先(SJF,ShortestJob又称为“短进程优先”SPN(ShortestProcessNext)； 优点提高缺点对长 。 过短完，上下文切换次数增加，响应)*q A04B13C25D32E44 ABCD0123443524A 平均周转时间＝ EAB 平均周转时间＝ ABCD01234352 优先级算法(Priority ）用户要求（紧迫程度 多少 MultipleFeedback)O不必估计进程的执行时间，动态 。最终采用最大时间片来执行，减少调度为适应一个进程在不同时间段的运行特点，I/O 调度算FCFS,RoundRobin周转时–长作业时：T(FCFS)<T(响应比)<T(RR)（运行时间是主要因素–短作业时：T(RR)<T(响应比)<T(FCFS)（等待时间是主要因素 采用抢 时间片Rate非抢占基于时立即抢

m

Ci Rate- 任务起始时间执行时间周期截止时间014411222288EarliestDeadline 任务起始时间执行时间周期截止时间050与单处注重整体运行效率（而不是个别处理机的利用率多处理 OS数据结构时的互斥（对于享内存系统调度单 主－从，并分派进程给从处理机执处 按控制方式，SMP 静态分配(staticassignment)：每个CPU，进程从开始执行到完成，都在同一个CPU缺点动态分配(dynamicassignment)：各个CPU采用一个公共就 自调度(self-scheduling)：各个CPU要对就绪队列的数据结构进行互斥控制。是最常用变型：MachOS中局部和全局就绪队列相结合，其中局部 瓶颈低效线程切 成组调度(gang一组处理机上执行，在处理机时也同时对 processorassignment)。 传统UNIX馈队列算法，进程优先级分为优先级和用户优先 调度由0号进程完成（始终在态执行）。时机进程由态转入用户态时：在每次执行代码之w或pauxit 于当前进程时，设置该标识。在wakeup,setrun,setpri（设runin空间换入一个外存就绪runout 在UNIXSystemV中：进程优先数：P_priP_CPU2+PUSER+P_nice+NZERO系统设置部分：PUSER和NZERO数的阈值，分别为25和–新创建进程的P_CPU值为0，因而具有较高的优先 进行处理。优先级分为可中断和不可中断 分三个检查是否作上下文切换（runrun标志）和是否允许作上下文切换（对的各种数据结构的操作都已经完成，处于正确的状态）。如果允许作。恢复 Linux中实现了三种进程调度策SCHED_OTHERSCHED_RR。轮转（RoundRobin）方式执行的实时进 行队列，而是通过权重的不同计算以及其他的一些队列操作，在一个运行队列中实现这三种不同的调度。发生进程调度时，调度程序要在运行队列中选择一个最值得运行的进程来执行，这个进程便是通选择的。权重越大的进程越优，而对于相同权重的 调度策略为SCHD_调度策略为SCHED_FIFO的进程，在时间片到，调度程序并不改变该进程在运行队列中的位 程继承了父进程的优先级。prort过系统调用sys_setpriority（sys_nicesys_setpriority取代）系统为每个进程预定的priority为（include/linux/sched.h），200ms prioity来反映其优先级（可执rt_pioity1~99，一般进程rt_prortr_pioitysetschedue coune，直至0。由于时count 计数器counersys_idle()时，将counter值置为-100。 在进程运行期间，每次发生时钟中断时，counter值减，直至为0contcont 调度的类型（如调度单位的不同级别，时间，不同的OS），性能实时调度：调度算 死锁发生竞争资并发执行的顺序 资源：CPU，内存非 资源：磁带机 临时性资 竞争临 P2:Rel(R1)P2:P2:Req(R1)P2:P1:Req(R1)P1:Req(R2)P1:Req(R1) ：进程已经占用的资源，不会被强 预防死避免死检测死解除死 互斥：设备请求和保持 申请所有资资源浪运行延 ：增加系统开环路等待：影响资源利 在分配如不） 安全状态：系统存在一个序列<p1,p2,..pn>不安全状 进可534292 进可524293银行家算法（Dijkstra, 当一个顾客 的最大需求量不超过银行家现 时可接纳顾顾客可以分期，但总 过最大需求当银行家现有的不能满足顾客尚需的数额时，对顾客的可推迟支付，但总能使顾客在有限的时间里得到贷当顾客得到所需的全部所有；安全性（能否支持顾客借款，直到全部归还安全时 ；否则，暂 可利用资源向量最大需求矩阵分配矩阵需求矩阵5processesPthroughP3resourcetypes(10instances),B(5instances),andC(7ABABABABAB0175332032309021220043Thecontentofthematrix.NeedisdefinedtobeMax–Allocation.ABP074P112P260P301P443

AllocationMaxABABAB0175332032309021220043

33537474104105Thesystemisinasafestatesincethesequence<P1,P3,P4,P2,P0>satisfiessafetycriteria.CheckthatRequestAvailable(thatis,(1,0,2)AABABAB0174233002306021010043Executingsafetyalgorithmshowsthatsequence<PP,PPPsatisfiessa