第4章__处理机调度.ppt

对于调度策略①来说，因为调度必须在时间片到来时才能发生，实时进程必须等待占有处理机的进程执行到时间片结束时才能获得处理机。因此，这种方法不能用作实时调度。同理， ②也不能用作实时调度，因为高优先级的实时进程，只有在当前执行进程自动让出处理机之后，才能获得处理机。 基于优先级的固定点抢先式调度方式与基于优先级的随时抢先式调度策略是实时系统的主要调度策略。基于优先级的固定点抢先式调度方式与优先级+时间片轮转调度方式有相似之处，其主要区别在于允许抢先的固定点间隔要比时间片小得多，并保证能满足所有硬实时的处理时限。 4.6.2 实时调度算法的分类 静态表调度算法 静态优先级调度算法 动态分析调度算法 尽力而为调度算法 静态表调度算法（Static table-driven scheduling） 适用于周期性的实时应用。通过对所有周期性任务的分析预测（到达时间、运行时间、结束时间、任务间的优先关系），事先确定一个固定的调度方案。这种方法的特点是有效但不灵活。 静态优先级调度算法（Static priority-driven scheduling） 把通用的优先级调度算法用于实时系统，但优先级的确定是通过静态分析（运行时间、到达频率）完成的。 动态分析调度算法（Dynamic planning-based scheduling） 在任务下达后执行前进行调度分析，要求满足实时性要求。 尽力而为调度算法 开销小，易实现，但不一定满足实时性要求。 4.6.3 时限调度算法与频率单调调度算法 是一种以满足用户要求的时限为调度原则的算法， 在实时系统中的用户要求时限有两种，即处理时限和处 理结束时限。时限调度算法可以用任一种。 1、时限调度算法所需要的相关信息有以下几种： （1）任务就绪时间或时间到达时间 （2）开始时限：指处理机必须开始对任务进行处理的时 限； （3）完成时限：指任务必须完成的时限； （4）处理时间：完成相关任务所需占用处理机的时间 （5）资源要求 （6）优先级 2、基本思想： 按用户的时限要求顺序设置优先级，优先级高者占 据处理机，也即时限要求最近的任务优先占有处理机。 3、例： 设实时系统从两个不同的数据源DA和DB周期性地 收集数据并进行处理，其中DA的时限要求以30毫秒为 周期，DB的时限要求以75毫秒为周期。设DA所需处理 时限为15毫秒，DB所需处理时限为38毫秒，则与DA、 DB有关进程的事件发生时限（就绪时限），执行时限 及结束时限如下： 进程 事件发生时限 执行时限 结束时限 DA（1） 0 15 30 DA（2） 30 15 60 DA（3） 60 15 90 …… …… …… …… DB（1） 0 38 75 DB（2） 75 38 150 DB（3） 150 38 225 …… …… …… …… 各进程的调度顺序和相对时间如下图所示： DA(1) DA(2) DA(3) DA(4) DB(1) DB(1) DB(1) DB(2) 15 30 45 60 75 90 105 130 t 如上图，在开始时，DA（1）和DB（1）的结束时 限比较，结果DA（1）的结束时限最近，从而调度进 程DA（1）执行。DA（1）的实际结束是为15，小于30 的时限要求。紧接着，进程DB（1）被调度执行。在 执行时间为30ms时，进程DA（2）进入就绪状态。由 于DA（2）的结束时限为60，近于DB（10的结束时限 75，从而DB（1）被DA（2）抢先。DA（2）的实际 结束时间为45，小于要求时限60。 在DA（2）结束之后，DB（1）再次占有处理机继 续执行，当DB（1）执行实现为60ms时，进程DA（3） 进入就绪状态。但是，由于DA（3）的结束时限为90 ，远于DB(1)的结束时限75，从而DB（1）继续执行。 频率单调调度算法 基本原理 使用的充分条件 线性优先级调度算法 （1）设置一个后备队列，接纳新创建进程，后备队列中最前面的进程，在一定的情况下，进入服务队列；（2）两个队列内部按照FCFS方式排列；（3）为每个进程定义可变的优先级； 优先级的变化规则： 进程在后备队列中时，优先级增长速度较快 P(t)=a×(t-t0) 其中t0为到达后备队列的时刻 在服务队列中时，增长较慢 P(t)= a×(t1-t0)+b×(t-t1) 升迁规则： 当后备队列中第一个进程的优先级超过了服务队列中最后一个进程