CFS抢占式调度可能出现无限循环调度问题

[shilei-massclouds]

问题现象

OSCamp下的u_7_0、u_6_0、u_6_1的日志级别从Info改为Trace之后，有一定概率出现下面的输出后无限循环。在WSL+Qemu环境下出现的概率较高，物理机+Qemu环境下概率低。

日志分析

当前ArceOS在启用CFS抢占式调度后，时钟中断的响应流程。如下

通过增加trace日志，看出第3阶段（蓝线）占时钟触发间隔（红线）的大部分时间，留给任务执行的时间为0，
导致所有的时间都消耗在任务切换上，而任务没有执行机会。

可能的解决方法

共三种，但是倾向第3种。

从当前现象看，CFS调度不应该给出允许调度的pending, 因为当前任务就没有获得运行时间。

后面的设想

参考Linux CFS的机制，在解决问题的情况下，尽可能少改动。
后面需要考虑：
1）多个任务的情况
2）SMP的情况

[hky1999]

@equation314

[shilei-massclouds]

对该问题的总结描述

时钟中断处理开始时，预定下一次时钟触发的时间，间隔周期是一个预先配置的参数。也就是说，在未来的
某个已经确定的时间点上，时钟中断将再次发生。
下次时钟中断发生之前，需要完成的工作有2+1项（2项无条件，1项有条件）：

1. 由调度器检查当前任务是否可以被抢占，可抢占时设置pending标志。
2. 中断处理完成时要开抢占，此时如果pending已经置位，则执行任务切换，重置当前任务指针。
3. 恢复当前任务，执行任务逻辑。
   总结：上述3项工作分享下次时钟中断前的总时间，这个时间是固定的。假如第1和第2项实际消耗的时间总和
   已经接近甚至超过总时间，那么第3项工作 - 任务处理逻辑，将没有时间执行。如此，进入下一次时钟中断的
   处理周期，重复上述过程。由于实际任务得不到执行机会，系统状态无法推进，整体陷入死循环。

解决问题的考虑

在CFS策略下，每个任务都至少应当获得一定的实际执行时间。在当前任务获得执行时间前，它不应该被抢占。
具体来说：上述第1项中，调度器能够检查出当前任务是否真正获得了一定的执行时间片，该时间>0；
在此之前，它不应该被置为 可抢占，那么第2项就不会被执行，避免了无意义的切换。
单就本问题来说，原因就是第2项工作因trace日志输出导致耗时较长，占用了总时间，并且它还是个无效动作。
优化上述策略后，本问题就可以被解决。

[shilei-massclouds]

关于CFS - task_tick检查机制的改进

修改scheduler中的cfs调度的task_tick这个检查机制。
当前的处理方式是：即使就绪队列为空，还要一直走到switch切换的前夕，发现prev_task_ptr == next_task_ptr时才放弃。
修改后的流程是：当就绪队列为空时，task_tick就直接返回false，这样就不会设置pending，也就越过了enable_preempt中的无意义的调度处理流程。

     fn task_tick(&mut self, current: &Self::SchedItem) -> bool {
         current.task_tick();
+        if self.ready_queue.is_empty() {
+            return false;
+        }
         self.min_vruntime.is_none()
             || current.get_vruntime() > self.min_vruntime.as_mut().unwrap().load(Ordering::Acquire)
     }

这种无效调度的情况在目前的测试用例中经常出现，即就绪队列为空，而其它任务都在waitq中，只有一个当前任务经常处于运行状态。
这样修改之后，很多无意义的调度被跳过（包括那几条耗时的trace日志），无限循环调度的问题概率明显降低了。
这个修改在SMP情况下没有问题，在每个CPU上，都有自己独立的当前任务和就绪队列，这个修改只是优化了CPU内部二者之间的切换，对现有机制没有负面影响。

[shilei-massclouds]

关于任务运行时间的度量方式和修改尝试

ArceOS-CFS调度是一种简化。每个时钟中断是一个tick，ArceOS-CFS假定这个tick代表的时间资源会全部分配给CurrentTask。但是实际上这个tick的时间周期还会分配给中断处理和后续可能的任务调度切换，这些部分消耗的时间在某些情况下是不可忽略的。简单的示意图是：

即，tick大致是个固定值(有时会延长一个周期)，中断处理和后续可能的任务调度切换的消耗时间会挤占任务实际执行时间，极端情况下，任务实际执行时间几乎完全被挤占。所以实际运行中，在每个tick中，当前任务获得的实际运行时间是不均匀的，只是CFS在记账时自己认为“公平”的分配给当前任务一个完整的tick时间。
当前测试发现的问题：开启Trace日志级别时，任务调度切换过程中输出日志的耗时过长，可能挤占任务实际运行的时间，导致任务可能只得到很少的运行时间或几乎未得到运行时间，就被切换出去了。
未来ArceOS完整支持中断后可能出现的情况：在一个tick周期之内，可能随机发生多个外部设备中断（时钟中断之外的各种类型），那它们同样可能挤占任务的实际执行时间，导致不公平。
修改的基本思路是：每个tick周期中统计当前任务实际运行的时间，然后不断累积，当该累积时间超过一个固定值之后，task_tick才会返回true，表示可以被调度。然后把累积值清零，重复上面的过程。对于如何统计当前任务实际运行的时间，没有想到好的办法，目前想到一个间接办法，累加一个tick周期中所有中断的总时间，然后用tick总时间 减去 中断消耗的总时间，就是当前任务在本tick周期中实际运行的时间。
基于此，尝试做了一个修改：

1. 在axhal的handle_irq中，度量一次中断消耗的总时间，大致像这样：

 #[register_trap_handler(IRQ)]
 fn handler_irq(irq_num: usize) -> bool {
+    const TICK_TIME: u64 =
+        crate::time::NANOS_PER_SEC / axconfig::TICKS_PER_SEC as u64;
+
     let guard = kernel_guard::NoPreempt::new();
+    let start_ns = crate::time::monotonic_time_nanos();
     dispatch_irq(irq_num);
     drop(guard); // rescheduling may occur when preemption is re-enabled.
+    let end_ns = crate::time::monotonic_time_nanos();
+    trace!("Duration for handling irq: {}", (end_ns - start_ns) * 100 / TICK_TIME);
+    call_interface!(StatIf::trace_irq_duration, start_ns, end_ns);
+
     true
 }

这样的目的是，所有类型的中断都可以被统计在内，包括Timer中断本身。另外可以看到，drop(guard)可能导致的任务切换也被统计在内，因为它也不属于任务时间运行的时间。
2) 由于层次关系，需要用crate_interface把每次中断的消耗时间传递给axruntime或axtask组件，使得该值可以被累加到当前任务上。在scheduler::CFSTask增加成员来记录中断累计值，如下：

pub struct CFSTask<T> {
     delta: AtomicIsize,
     nice: AtomicIsize,
     id: AtomicIsize,
+    irq_time: AtomicIsize,
+    delta_in_a_tick: AtomicIsize,
 }

irq_time就是累计的中断消耗时间，它在每个tick结束时需要被清零。在清零之前，需要用Tick总时间减去它，再累加到delta_in_a_tick。
delta_in_a_tick才是跨tick的累加值，它代表了一个任务实际获得的运行时间(跨tick)。
3) 改造task_tick，不是简单的自加delta，而是判断delta_in_a_tick是否已经超过一个固定值，超过时才自加delta，然后清零delta_in_a_tick。

修改后的整体评价：虽然可以更准确的实现公平性，也可以一定程度上解决开启Trace级别导致的问题，但是似乎过于复杂了，可能有点得不偿失，暂时不提交pr。后面考虑更合适的相对简单的方案，把当前方案作为参照。