xref: /DragonOS/kernel/src/sched/mod.rs (revision 7401bec5e3c42015399a46e29c370abe7c7388b5)
1 pub mod clock;
2 pub mod completion;
3 pub mod cputime;
4 pub mod fair;
5 pub mod idle;
6 pub mod pelt;
7 pub mod prio;
8 pub mod syscall;
9 
10 use core::{
11     intrinsics::{likely, unlikely},
12     sync::atomic::{compiler_fence, fence, AtomicUsize, Ordering},
13 };
14 
15 use alloc::{
16     boxed::Box,
17     collections::LinkedList,
18     sync::{Arc, Weak},
19     vec::Vec,
20 };
21 use system_error::SystemError;
22 
23 use crate::{
24     arch::{interrupt::ipi::send_ipi, CurrentIrqArch},
25     exception::{
26         ipi::{IpiKind, IpiTarget},
27         InterruptArch,
28     },
29     libs::{
30         lazy_init::Lazy,
31         spinlock::{SpinLock, SpinLockGuard},
32     },
33     mm::percpu::{PerCpu, PerCpuVar},
34     process::{ProcessControlBlock, ProcessFlags, ProcessManager, ProcessState, SchedInfo},
35     sched::idle::IdleScheduler,
36     smp::{core::smp_get_processor_id, cpu::ProcessorId},
37     time::{clocksource::HZ, timer::clock},
38 };
39 
40 use self::{
41     clock::{ClockUpdataFlag, SchedClock},
42     cputime::{irq_time_read, CpuTimeFunc, IrqTime},
43     fair::{CfsRunQueue, CompletelyFairScheduler, FairSchedEntity},
44     prio::PrioUtil,
45 };
46 
47 static mut CPU_IRQ_TIME: Option<Vec<&'static mut IrqTime>> = None;
48 
49 // 这里虽然rq是percpu的,但是在负载均衡的时候需要修改对端cpu的rq,所以仍需加锁
50 static CPU_RUNQUEUE: Lazy<PerCpuVar<Arc<CpuRunQueue>>> = PerCpuVar::define_lazy();
51 
52 /// 用于记录系统中所有 CPU 的可执行进程数量的总和。
53 static CALCULATE_LOAD_TASKS: AtomicUsize = AtomicUsize::new(0);
54 
55 const LOAD_FREQ: usize = HZ as usize * 5 + 1;
56 
57 pub const SCHED_FIXEDPOINT_SHIFT: u64 = 10;
58 #[allow(dead_code)]
59 pub const SCHED_FIXEDPOINT_SCALE: u64 = 1 << SCHED_FIXEDPOINT_SHIFT;
60 #[allow(dead_code)]
61 pub const SCHED_CAPACITY_SHIFT: u64 = SCHED_FIXEDPOINT_SHIFT;
62 #[allow(dead_code)]
63 pub const SCHED_CAPACITY_SCALE: u64 = 1 << SCHED_CAPACITY_SHIFT;
64 
65 #[inline]
66 pub fn cpu_irq_time(cpu: usize) -> &'static mut IrqTime {
67     unsafe { CPU_IRQ_TIME.as_mut().unwrap()[cpu] }
68 }
69 
70 #[inline]
71 pub fn cpu_rq(cpu: usize) -> Arc<CpuRunQueue> {
72     CPU_RUNQUEUE.ensure();
73     unsafe {
74         CPU_RUNQUEUE
75             .get()
76             .force_get(ProcessorId::new(cpu as u32))
77             .clone()
78     }
79 }
80 
81 lazy_static! {
82     pub static ref SCHED_FEATURES: SchedFeature = SchedFeature::GENTLE_FAIR_SLEEPERS
83         | SchedFeature::START_DEBIT
84         | SchedFeature::LAST_BUDDY
85         | SchedFeature::CACHE_HOT_BUDDY
86         | SchedFeature::WAKEUP_PREEMPTION
87         | SchedFeature::NONTASK_CAPACITY
88         | SchedFeature::TTWU_QUEUE
89         | SchedFeature::SIS_UTIL
90         | SchedFeature::RT_PUSH_IPI
91         | SchedFeature::ALT_PERIOD
92         | SchedFeature::BASE_SLICE
93         | SchedFeature::UTIL_EST
94         | SchedFeature::UTIL_EST_FASTUP;
95 }
96 
97 pub trait Scheduler {
98     /// ## 加入当任务进入可运行状态时调用。它将调度实体(任务)放到红黑树中,增加nr_running变量的值。
99     fn enqueue(rq: &mut CpuRunQueue, pcb: Arc<ProcessControlBlock>, flags: EnqueueFlag);
100 
101     /// ## 当任务不再可运行时被调用,对应的调度实体被移出红黑树。它减少nr_running变量的值。
102     fn dequeue(rq: &mut CpuRunQueue, pcb: Arc<ProcessControlBlock>, flags: DequeueFlag);
103 
104     /// ## 主动让出cpu,这个函数的行为基本上是出队,紧接着入队
105     fn yield_task(rq: &mut CpuRunQueue);
106 
107     /// ## 检查进入可运行状态的任务能否抢占当前正在运行的任务
108     fn check_preempt_currnet(
109         rq: &mut CpuRunQueue,
110         pcb: &Arc<ProcessControlBlock>,
111         flags: WakeupFlags,
112     );
113 
114     /// ## 选择接下来最适合运行的任务
115     fn pick_task(rq: &mut CpuRunQueue) -> Option<Arc<ProcessControlBlock>>;
116 
117     /// ## 选择接下来最适合运行的任务
118     fn pick_next_task(
119         rq: &mut CpuRunQueue,
120         pcb: Option<Arc<ProcessControlBlock>>,
121     ) -> Option<Arc<ProcessControlBlock>>;
122 
123     /// ## 被时间滴答函数调用,它可能导致进程切换。驱动了运行时抢占。
124     fn tick(rq: &mut CpuRunQueue, pcb: Arc<ProcessControlBlock>, queued: bool);
125 
126     /// ## 在进程fork时,如需加入cfs,则调用
127     fn task_fork(pcb: Arc<ProcessControlBlock>);
128 
129     fn put_prev_task(rq: &mut CpuRunQueue, prev: Arc<ProcessControlBlock>);
130 }
131 
132 /// 调度策略
133 #[allow(dead_code)]
134 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
135 pub enum SchedPolicy {
136     /// 实时进程
137     RT,
138     /// 先进先出调度
139     FIFO,
140     /// 完全公平调度
141     CFS,
142     /// IDLE
143     IDLE,
144 }
145 
146 #[allow(dead_code)]
147 pub struct TaskGroup {
148     /// CFS管理的调度实体,percpu的
149     entitys: Vec<Arc<FairSchedEntity>>,
150     /// 每个CPU的CFS运行队列
151     cfs: Vec<Arc<CfsRunQueue>>,
152     /// 父节点
153     parent: Option<Arc<TaskGroup>>,
154 
155     shares: u64,
156 }
157 
158 #[derive(Debug, Default)]
159 pub struct LoadWeight {
160     /// 负载权重
161     pub weight: u64,
162     /// weight的倒数,方便计算
163     pub inv_weight: u32,
164 }
165 
166 impl LoadWeight {
167     /// 用于限制权重在一个合适的区域内
168     pub const SCHED_FIXEDPOINT_SHIFT: u32 = 10;
169 
170     pub const WMULT_SHIFT: u32 = 32;
171     pub const WMULT_CONST: u32 = !0;
172 
173     pub const NICE_0_LOAD_SHIFT: u32 = Self::SCHED_FIXEDPOINT_SHIFT + Self::SCHED_FIXEDPOINT_SHIFT;
174 
175     pub fn update_load_add(&mut self, inc: u64) {
176         self.weight += inc;
177         self.inv_weight = 0;
178     }
179 
180     pub fn update_load_sub(&mut self, dec: u64) {
181         self.weight -= dec;
182         self.inv_weight = 0;
183     }
184 
185     pub fn update_load_set(&mut self, weight: u64) {
186         self.weight = weight;
187         self.inv_weight = 0;
188     }
189 
190     /// ## 更新负载权重的倒数
191     pub fn update_inv_weight(&mut self) {
192         // 已经更新
193         if likely(self.inv_weight != 0) {
194             return;
195         }
196 
197         let w = Self::scale_load_down(self.weight);
198 
199         if unlikely(w >= Self::WMULT_CONST as u64) {
200             // 高位有数据
201             self.inv_weight = 1;
202         } else if unlikely(w == 0) {
203             // 倒数去最大
204             self.inv_weight = Self::WMULT_CONST;
205         } else {
206             // 计算倒数
207             self.inv_weight = Self::WMULT_CONST / w as u32;
208         }
209     }
210 
211     /// ## 计算任务的执行时间差
212     ///
213     /// 计算公式:(delta_exec * (weight * self.inv_weight)) >> WMULT_SHIFT
214     pub fn calculate_delta(&mut self, delta_exec: u64, weight: u64) -> u64 {
215         // 降低精度
216         let mut fact = Self::scale_load_down(weight);
217 
218         // 记录fact高32位
219         let mut fact_hi = (fact >> 32) as u32;
220         // 用于恢复
221         let mut shift = Self::WMULT_SHIFT;
222 
223         self.update_inv_weight();
224 
225         if unlikely(fact_hi != 0) {
226             // 这里表示高32位还有数据
227             // 需要计算最高位,然后继续调整fact
228             let fs = 32 - fact_hi.leading_zeros();
229             shift -= fs;
230 
231             // 确保高32位全为0
232             fact >>= fs;
233         }
234 
235         // 这里确定了fact已经在32位内
236         fact *= self.inv_weight as u64;
237 
238         fact_hi = (fact >> 32) as u32;
239 
240         if fact_hi != 0 {
241             // 这里表示高32位还有数据
242             // 需要计算最高位,然后继续调整fact
243             let fs = 32 - fact_hi.leading_zeros();
244             shift -= fs;
245 
246             // 确保高32位全为0
247             fact >>= fs;
248         }
249 
250         return ((delta_exec as u128 * fact as u128) >> shift) as u64;
251     }
252 
253     /// ## 将负载权重缩小到到一个小的范围中计算,相当于减小精度计算
254     pub const fn scale_load_down(mut weight: u64) -> u64 {
255         if weight != 0 {
256             weight >>= Self::SCHED_FIXEDPOINT_SHIFT;
257 
258             if weight < 2 {
259                 weight = 2;
260             }
261         }
262         weight
263     }
264 
265     #[allow(dead_code)]
266     pub const fn scale_load(weight: u64) -> u64 {
267         weight << Self::SCHED_FIXEDPOINT_SHIFT
268     }
269 }
270 
271 pub trait SchedArch {
272     /// 开启当前核心的调度
273     fn enable_sched_local();
274     /// 关闭当前核心的调度
275     fn disable_sched_local();
276 
277     /// 在第一次开启调度之前,进行初始化工作。
278     ///
279     /// 注意区别于sched_init,这个函数只是做初始化时钟的工作等等。
280     fn initial_setup_sched_local() {}
281 }
282 
283 /// ## PerCpu的运行队列,其中维护了各个调度器对应的rq
284 #[allow(dead_code)]
285 #[derive(Debug)]
286 pub struct CpuRunQueue {
287     lock: SpinLock<()>,
288     lock_on_who: AtomicUsize,
289 
290     cpu: usize,
291     clock_task: u64,
292     clock: u64,
293     prev_irq_time: u64,
294     clock_updata_flags: ClockUpdataFlag,
295 
296     /// 过载
297     overload: bool,
298 
299     next_balance: u64,
300 
301     /// 运行任务数
302     nr_running: usize,
303 
304     /// 被阻塞的任务数量
305     nr_uninterruptible: usize,
306 
307     /// 记录上次更新负载时间
308     cala_load_update: usize,
309     cala_load_active: usize,
310 
311     /// CFS调度器
312     cfs: Arc<CfsRunQueue>,
313 
314     clock_pelt: u64,
315     lost_idle_time: u64,
316     clock_idle: u64,
317 
318     cfs_tasks: LinkedList<Arc<FairSchedEntity>>,
319 
320     /// 最近一次的调度信息
321     sched_info: SchedInfo,
322 
323     /// 当前在运行队列上执行的进程
324     current: Weak<ProcessControlBlock>,
325 
326     idle: Weak<ProcessControlBlock>,
327 }
328 
329 impl CpuRunQueue {
330     pub fn new(cpu: usize) -> Self {
331         Self {
332             lock: SpinLock::new(()),
333             lock_on_who: AtomicUsize::new(usize::MAX),
334             cpu,
335             clock_task: 0,
336             clock: 0,
337             prev_irq_time: 0,
338             clock_updata_flags: ClockUpdataFlag::empty(),
339             overload: false,
340             next_balance: 0,
341             nr_running: 0,
342             nr_uninterruptible: 0,
343             cala_load_update: (clock() + (5 * HZ + 1)) as usize,
344             cala_load_active: 0,
345             cfs: Arc::new(CfsRunQueue::new()),
346             clock_pelt: 0,
347             lost_idle_time: 0,
348             clock_idle: 0,
349             cfs_tasks: LinkedList::new(),
350             sched_info: SchedInfo::default(),
351             current: Weak::new(),
352             idle: Weak::new(),
353         }
354     }
355 
356     /// 此函数只能在关中断的情况下使用!!!
357     /// 获取到rq的可变引用,需要注意的是返回的第二个值需要确保其生命周期
358     /// 所以可以说这个函数是unsafe的,需要确保正确性
359     /// 在中断上下文,关中断的情况下,此函数是安全的
360     pub fn self_lock(&self) -> (&mut Self, Option<SpinLockGuard<()>>) {
361         if self.lock.is_locked()
362             && smp_get_processor_id().data() as usize == self.lock_on_who.load(Ordering::SeqCst)
363         {
364             // 在本cpu已上锁则可以直接拿
365             (
366                 unsafe { &mut *(self as *const Self as usize as *mut Self) },
367                 None,
368             )
369         } else {
370             // 否则先上锁再拿
371             let guard = self.lock();
372             (
373                 unsafe { &mut *(self as *const Self as usize as *mut Self) },
374                 Some(guard),
375             )
376         }
377     }
378 
379     fn lock(&self) -> SpinLockGuard<()> {
380         let guard = self.lock.lock_irqsave();
381 
382         // 更新在哪一个cpu上锁
383         self.lock_on_who
384             .store(smp_get_processor_id().data() as usize, Ordering::SeqCst);
385 
386         guard
387     }
388 
389     pub fn enqueue_task(&mut self, pcb: Arc<ProcessControlBlock>, flags: EnqueueFlag) {
390         if !flags.contains(EnqueueFlag::ENQUEUE_NOCLOCK) {
391             self.update_rq_clock();
392         }
393 
394         if !flags.contains(EnqueueFlag::ENQUEUE_RESTORE) {
395             let sched_info = pcb.sched_info().sched_stat.upgradeable_read_irqsave();
396             if sched_info.last_queued == 0 {
397                 sched_info.upgrade().last_queued = self.clock;
398             }
399         }
400 
401         match pcb.sched_info().policy() {
402             SchedPolicy::CFS => CompletelyFairScheduler::enqueue(self, pcb, flags),
403             SchedPolicy::FIFO => todo!(),
404             SchedPolicy::RT => todo!(),
405             SchedPolicy::IDLE => IdleScheduler::enqueue(self, pcb, flags),
406         }
407 
408         // TODO:https://code.dragonos.org.cn/xref/linux-6.6.21/kernel/sched/core.c#239
409     }
410 
411     pub fn dequeue_task(&mut self, pcb: Arc<ProcessControlBlock>, flags: DequeueFlag) {
412         // TODO:sched_core
413 
414         if !flags.contains(DequeueFlag::DEQUEUE_NOCLOCK) {
415             self.update_rq_clock()
416         }
417 
418         if !flags.contains(DequeueFlag::DEQUEUE_SAVE) {
419             let sched_info = pcb.sched_info().sched_stat.upgradeable_read_irqsave();
420 
421             if sched_info.last_queued > 0 {
422                 let delta = self.clock - sched_info.last_queued;
423 
424                 let mut sched_info = sched_info.upgrade();
425                 sched_info.last_queued = 0;
426                 sched_info.run_delay += delta as usize;
427 
428                 self.sched_info.run_delay += delta as usize;
429             }
430         }
431 
432         match pcb.sched_info().policy() {
433             SchedPolicy::CFS => CompletelyFairScheduler::dequeue(self, pcb, flags),
434             SchedPolicy::FIFO => todo!(),
435             SchedPolicy::RT => todo!(),
436             SchedPolicy::IDLE => IdleScheduler::dequeue(self, pcb, flags),
437         }
438     }
439 
440     /// 启用一个任务,将加入队列
441     pub fn activate_task(&mut self, pcb: &Arc<ProcessControlBlock>, mut flags: EnqueueFlag) {
442         if *pcb.sched_info().on_rq.lock_irqsave() == OnRq::Migrating {
443             flags |= EnqueueFlag::ENQUEUE_MIGRATED;
444         }
445 
446         if flags.contains(EnqueueFlag::ENQUEUE_MIGRATED) {
447             todo!()
448         }
449 
450         self.enqueue_task(pcb.clone(), flags);
451 
452         *pcb.sched_info().on_rq.lock_irqsave() = OnRq::Queued;
453     }
454 
455     /// 检查对应的task是否可以抢占当前运行的task
456     #[allow(clippy::comparison_chain)]
457     pub fn check_preempt_currnet(&mut self, pcb: &Arc<ProcessControlBlock>, flags: WakeupFlags) {
458         if pcb.sched_info().policy() == self.current().sched_info().policy() {
459             match self.current().sched_info().policy() {
460                 SchedPolicy::CFS => {
461                     CompletelyFairScheduler::check_preempt_currnet(self, pcb, flags)
462                 }
463                 SchedPolicy::FIFO => todo!(),
464                 SchedPolicy::RT => todo!(),
465                 SchedPolicy::IDLE => IdleScheduler::check_preempt_currnet(self, pcb, flags),
466             }
467         } else if pcb.sched_info().policy() < self.current().sched_info().policy() {
468             // 调度优先级更高
469             self.resched_current();
470         }
471 
472         if *self.current().sched_info().on_rq.lock_irqsave() == OnRq::Queued
473             && self.current().flags().contains(ProcessFlags::NEED_SCHEDULE)
474         {
475             self.clock_updata_flags
476                 .insert(ClockUpdataFlag::RQCF_REQ_SKIP);
477         }
478     }
479 
480     /// 禁用一个任务,将离开队列
481     pub fn deactivate_task(&mut self, pcb: Arc<ProcessControlBlock>, flags: DequeueFlag) {
482         *pcb.sched_info().on_rq.lock_irqsave() = if flags.contains(DequeueFlag::DEQUEUE_SLEEP) {
483             OnRq::None
484         } else {
485             OnRq::Migrating
486         };
487 
488         self.dequeue_task(pcb, flags);
489     }
490 
491     #[inline]
492     pub fn cfs_rq(&self) -> Arc<CfsRunQueue> {
493         self.cfs.clone()
494     }
495 
496     /// 更新rq时钟
497     pub fn update_rq_clock(&mut self) {
498         // 需要跳过这次时钟更新
499         if self
500             .clock_updata_flags
501             .contains(ClockUpdataFlag::RQCF_ACT_SKIP)
502         {
503             return;
504         }
505 
506         let clock = SchedClock::sched_clock_cpu(self.cpu);
507         if clock < self.clock {
508             return;
509         }
510 
511         let delta = clock - self.clock;
512         self.clock += delta;
513         // kerror!("clock {}", self.clock);
514         self.update_rq_clock_task(delta);
515     }
516 
517     /// 更新任务时钟
518     pub fn update_rq_clock_task(&mut self, mut delta: u64) {
519         let mut irq_delta = irq_time_read(self.cpu) - self.prev_irq_time;
520         // if self.cpu == 0 {
521         //     kerror!(
522         //         "cpu 0 delta {delta} irq_delta {} irq_time_read(self.cpu) {} self.prev_irq_time {}",
523         //         irq_delta,
524         //         irq_time_read(self.cpu),
525         //         self.prev_irq_time
526         //     );
527         // }
528         compiler_fence(Ordering::SeqCst);
529 
530         if irq_delta > delta {
531             irq_delta = delta;
532         }
533 
534         self.prev_irq_time += irq_delta;
535 
536         delta -= irq_delta;
537 
538         // todo: psi?
539 
540         // send_to_default_serial8250_port(format!("\n{delta}\n",).as_bytes());
541         compiler_fence(Ordering::SeqCst);
542         self.clock_task += delta;
543         compiler_fence(Ordering::SeqCst);
544         // if self.cpu == 0 {
545         //     kerror!("cpu {} clock_task {}", self.cpu, self.clock_task);
546         // }
547         // todo: pelt?
548     }
549 
550     /// 计算当前进程中的可执行数量
551     fn calculate_load_fold_active(&mut self, adjust: usize) -> usize {
552         let mut nr_active = self.nr_running - adjust;
553         nr_active += self.nr_uninterruptible;
554         let mut delta = 0;
555 
556         if nr_active != self.cala_load_active {
557             delta = nr_active - self.cala_load_active;
558             self.cala_load_active = nr_active;
559         }
560 
561         delta
562     }
563 
564     /// ## tick计算全局负载
565     pub fn calculate_global_load_tick(&mut self) {
566         if clock() < self.cala_load_update as u64 {
567             // 如果当前时间在上次更新时间之前,则直接返回
568             return;
569         }
570 
571         let delta = self.calculate_load_fold_active(0);
572 
573         if delta != 0 {
574             CALCULATE_LOAD_TASKS.fetch_add(delta, Ordering::SeqCst);
575         }
576 
577         self.cala_load_update += LOAD_FREQ;
578     }
579 
580     pub fn add_nr_running(&mut self, nr_running: usize) {
581         let prev = self.nr_running;
582 
583         self.nr_running = prev + nr_running;
584         if prev < 2 && self.nr_running >= 2 && !self.overload {
585             self.overload = true;
586         }
587     }
588 
589     pub fn sub_nr_running(&mut self, count: usize) {
590         self.nr_running -= count;
591     }
592 
593     /// 在运行idle?
594     pub fn sched_idle_rq(&self) -> bool {
595         return unlikely(
596             self.nr_running == self.cfs.idle_h_nr_running as usize && self.nr_running > 0,
597         );
598     }
599 
600     #[inline]
601     pub fn current(&self) -> Arc<ProcessControlBlock> {
602         self.current.upgrade().unwrap()
603     }
604 
605     #[inline]
606     pub fn set_current(&mut self, pcb: Weak<ProcessControlBlock>) {
607         self.current = pcb;
608     }
609 
610     #[inline]
611     pub fn set_idle(&mut self, pcb: Weak<ProcessControlBlock>) {
612         self.idle = pcb;
613     }
614 
615     #[inline]
616     pub fn clock_task(&self) -> u64 {
617         self.clock_task
618     }
619 
620     /// 重新调度当前进程
621     pub fn resched_current(&self) {
622         let current = self.current();
623 
624         // 又需要被调度?
625         if unlikely(current.flags().contains(ProcessFlags::NEED_SCHEDULE)) {
626             return;
627         }
628 
629         let cpu = self.cpu;
630 
631         if cpu == smp_get_processor_id().data() as usize {
632             // assert!(
633             //     Arc::ptr_eq(&current, &ProcessManager::current_pcb()),
634             //     "rq current name {} process current {}",
635             //     current.basic().name().to_string(),
636             //     ProcessManager::current_pcb().basic().name().to_string(),
637             // );
638             // 设置需要调度
639             ProcessManager::current_pcb()
640                 .flags()
641                 .insert(ProcessFlags::NEED_SCHEDULE);
642             return;
643         }
644 
645         // 向目标cpu发送重调度ipi
646         send_resched_ipi(ProcessorId::new(cpu as u32));
647     }
648 
649     /// 选择下一个task
650     pub fn pick_next_task(&mut self, prev: Arc<ProcessControlBlock>) -> Arc<ProcessControlBlock> {
651         if likely(prev.sched_info().policy() >= SchedPolicy::CFS)
652             && self.nr_running == self.cfs.h_nr_running as usize
653         {
654             let p = CompletelyFairScheduler::pick_next_task(self, Some(prev.clone()));
655 
656             if let Some(pcb) = p.as_ref() {
657                 return pcb.clone();
658             } else {
659                 // kerror!(
660                 //     "pick idle cfs rq {:?}",
661                 //     self.cfs_rq()
662                 //         .entities
663                 //         .iter()
664                 //         .map(|x| x.1.pid)
665                 //         .collect::<Vec<_>>()
666                 // );
667                 match prev.sched_info().policy() {
668                     SchedPolicy::FIFO => todo!(),
669                     SchedPolicy::RT => todo!(),
670                     SchedPolicy::CFS => CompletelyFairScheduler::put_prev_task(self, prev),
671                     SchedPolicy::IDLE => IdleScheduler::put_prev_task(self, prev),
672                 }
673                 // 选择idle
674                 return self.idle.upgrade().unwrap();
675             }
676         }
677 
678         todo!()
679     }
680 }
681 
682 bitflags! {
683     pub struct SchedFeature:u32 {
684         /// 给予睡眠任务仅有 50% 的服务赤字。这意味着睡眠任务在被唤醒后会获得一定的服务,但不能过多地占用资源。
685         const GENTLE_FAIR_SLEEPERS = 1 << 0;
686         /// 将新任务排在前面,以避免已经运行的任务被饿死
687         const START_DEBIT = 1 << 1;
688         /// 在调度时优先选择上次唤醒的任务,因为它可能会访问之前唤醒的任务所使用的数据,从而提高缓存局部性。
689         const NEXT_BUDDY = 1 << 2;
690         /// 在调度时优先选择上次运行的任务,因为它可能会访问与之前运行的任务相同的数据,从而提高缓存局部性。
691         const LAST_BUDDY = 1 << 3;
692         /// 认为任务的伙伴(buddy)在缓存中是热点,减少缓存伙伴被迁移的可能性,从而提高缓存局部性。
693         const CACHE_HOT_BUDDY = 1 << 4;
694         /// 允许唤醒时抢占当前任务。
695         const WAKEUP_PREEMPTION = 1 << 5;
696         /// 基于任务未运行时间来减少 CPU 的容量。
697         const NONTASK_CAPACITY = 1 << 6;
698         /// 将远程唤醒排队到目标 CPU,并使用调度器 IPI 处理它们,以减少运行队列锁的争用。
699         const TTWU_QUEUE = 1 << 7;
700         /// 在唤醒时尝试限制对最后级联缓存(LLC)域的无谓扫描。
701         const SIS_UTIL = 1 << 8;
702         /// 在 RT(Real-Time)任务迁移时,通过发送 IPI 来减少 CPU 之间的锁竞争。
703         const RT_PUSH_IPI = 1 << 9;
704         /// 启用估计的 CPU 利用率功能,用于调度决策。
705         const UTIL_EST = 1 << 10;
706         const UTIL_EST_FASTUP = 1 << 11;
707         /// 启用备选调度周期
708         const ALT_PERIOD = 1 << 12;
709         /// 启用基本时间片
710         const BASE_SLICE = 1 << 13;
711     }
712 
713     pub struct EnqueueFlag: u8 {
714         const ENQUEUE_WAKEUP	= 0x01;
715         const ENQUEUE_RESTORE	= 0x02;
716         const ENQUEUE_MOVE	= 0x04;
717         const ENQUEUE_NOCLOCK	= 0x08;
718 
719         const ENQUEUE_MIGRATED	= 0x40;
720 
721         const ENQUEUE_INITIAL	= 0x80;
722     }
723 
724     pub struct DequeueFlag: u8 {
725         const DEQUEUE_SLEEP		= 0x01;
726         const DEQUEUE_SAVE		= 0x02; /* Matches ENQUEUE_RESTORE */
727         const DEQUEUE_MOVE		= 0x04; /* Matches ENQUEUE_MOVE */
728         const DEQUEUE_NOCLOCK		= 0x08; /* Matches ENQUEUE_NOCLOCK */
729     }
730 
731     pub struct WakeupFlags: u8 {
732         /* Wake flags. The first three directly map to some SD flag value */
733         const WF_EXEC         = 0x02; /* Wakeup after exec; maps to SD_BALANCE_EXEC */
734         const WF_FORK         = 0x04; /* Wakeup after fork; maps to SD_BALANCE_FORK */
735         const WF_TTWU         = 0x08; /* Wakeup;            maps to SD_BALANCE_WAKE */
736 
737         const WF_SYNC         = 0x10; /* Waker goes to sleep after wakeup */
738         const WF_MIGRATED     = 0x20; /* Internal use, task got migrated */
739         const WF_CURRENT_CPU  = 0x40; /* Prefer to move the wakee to the current CPU. */
740     }
741 
742     pub struct SchedMode: u8 {
743         /*
744         * Constants for the sched_mode argument of __schedule().
745         *
746         * The mode argument allows RT enabled kernels to differentiate a
747         * preemption from blocking on an 'sleeping' spin/rwlock. Note that
748         * SM_MASK_PREEMPT for !RT has all bits set, which allows the compiler to
749         * optimize the AND operation out and just check for zero.
750         */
751         /// 在调度过程中不会再次进入队列,即需要手动唤醒
752         const SM_NONE			= 0x0;
753         /// 重新加入队列,即当前进程被抢占,需要时钟调度
754         const SM_PREEMPT		= 0x1;
755         /// rt相关
756         const SM_RTLOCK_WAIT		= 0x2;
757         /// 默认与SM_PREEMPT相同
758         const SM_MASK_PREEMPT	= Self::SM_PREEMPT.bits;
759     }
760 }
761 
762 #[derive(Copy, Clone, Debug, PartialEq)]
763 pub enum OnRq {
764     Queued,
765     Migrating,
766     None,
767 }
768 
769 impl ProcessManager {
770     pub fn update_process_times(user_tick: bool) {
771         let pcb = Self::current_pcb();
772         CpuTimeFunc::irqtime_account_process_tick(&pcb, user_tick, 1);
773 
774         scheduler_tick();
775     }
776 }
777 
778 /// ## 时钟tick时调用此函数
779 pub fn scheduler_tick() {
780     fence(Ordering::SeqCst);
781     // 获取当前CPU索引
782     let cpu_idx = smp_get_processor_id().data() as usize;
783 
784     // 获取当前CPU的请求队列
785     let rq = cpu_rq(cpu_idx);
786 
787     let (rq, guard) = rq.self_lock();
788 
789     // 获取当前请求队列的当前请求
790     let current = rq.current();
791 
792     // 更新请求队列时钟
793     rq.update_rq_clock();
794 
795     match current.sched_info().policy() {
796         SchedPolicy::CFS => CompletelyFairScheduler::tick(rq, current, false),
797         SchedPolicy::FIFO => todo!(),
798         SchedPolicy::RT => todo!(),
799         SchedPolicy::IDLE => IdleScheduler::tick(rq, current, false),
800     }
801 
802     rq.calculate_global_load_tick();
803 
804     drop(guard);
805     // TODO:处理负载均衡
806 }
807 
808 /// ## 执行调度
809 /// 若preempt_count不为0则报错
810 #[inline]
811 pub fn schedule(sched_mod: SchedMode) {
812     let _guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
813     assert_eq!(ProcessManager::current_pcb().preempt_count(), 0);
814     __schedule(sched_mod);
815 }
816 
817 /// ## 执行调度
818 /// 此函数与schedule的区别为,该函数不会检查preempt_count
819 /// 适用于时钟中断等场景
820 pub fn __schedule(sched_mod: SchedMode) {
821     let cpu = smp_get_processor_id().data() as usize;
822     let rq = cpu_rq(cpu);
823 
824     let mut prev = rq.current();
825     if let ProcessState::Exited(_) = prev.clone().sched_info().inner_lock_read_irqsave().state() {
826         // 从exit进的Schedule
827         prev = ProcessManager::current_pcb();
828     }
829 
830     // TODO: hrtick_clear(rq);
831 
832     let (rq, _guard) = rq.self_lock();
833 
834     rq.clock_updata_flags = ClockUpdataFlag::from_bits_truncate(rq.clock_updata_flags.bits() << 1);
835 
836     rq.update_rq_clock();
837     rq.clock_updata_flags = ClockUpdataFlag::RQCF_UPDATE;
838 
839     // kBUG!(
840     //     "before cfs rq pcbs {:?}\nvruntimes {:?}\n",
841     //     rq.cfs
842     //         .entities
843     //         .iter()
844     //         .map(|x| { x.1.pcb().pid() })
845     //         .collect::<Vec<_>>(),
846     //     rq.cfs
847     //         .entities
848     //         .iter()
849     //         .map(|x| { x.1.vruntime })
850     //         .collect::<Vec<_>>(),
851     // );
852     // kwarn!(
853     //     "before cfs rq {:?} prev {:?}",
854     //     rq.cfs
855     //         .entities
856     //         .iter()
857     //         .map(|x| { x.1.pcb().pid() })
858     //         .collect::<Vec<_>>(),
859     //     prev.pid()
860     // );
861 
862     // kerror!("prev pid {:?} {:?}", prev.pid(), prev.sched_info().policy());
863     if !sched_mod.contains(SchedMode::SM_MASK_PREEMPT)
864         && prev.sched_info().policy() != SchedPolicy::IDLE
865         && prev.sched_info().inner_lock_read_irqsave().is_mark_sleep()
866     {
867         // kwarn!("deactivate_task prev {:?}", prev.pid());
868         // TODO: 这里需要处理信号
869         // https://code.dragonos.org.cn/xref/linux-6.6.21/kernel/sched/core.c?r=&mo=172979&fi=6578#6630
870         rq.deactivate_task(
871             prev.clone(),
872             DequeueFlag::DEQUEUE_SLEEP | DequeueFlag::DEQUEUE_NOCLOCK,
873         );
874     }
875 
876     let next = rq.pick_next_task(prev.clone());
877 
878     // kBUG!(
879     //     "after cfs rq pcbs {:?}\nvruntimes {:?}\n",
880     //     rq.cfs
881     //         .entities
882     //         .iter()
883     //         .map(|x| { x.1.pcb().pid() })
884     //         .collect::<Vec<_>>(),
885     //     rq.cfs
886     //         .entities
887     //         .iter()
888     //         .map(|x| { x.1.vruntime })
889     //         .collect::<Vec<_>>(),
890     // );
891 
892     // kerror!("next {:?}", next.pid());
893 
894     prev.flags().remove(ProcessFlags::NEED_SCHEDULE);
895     fence(Ordering::SeqCst);
896     if likely(!Arc::ptr_eq(&prev, &next)) {
897         rq.set_current(Arc::downgrade(&next));
898         // kwarn!(
899         //     "switch_process prev {:?} next {:?} sched_mode {sched_mod:?}",
900         //     prev.pid(),
901         //     next.pid()
902         // );
903 
904         // send_to_default_serial8250_port(
905         //     format!(
906         //         "switch_process prev {:?} next {:?} sched_mode {sched_mod:?}\n",
907         //         prev.pid(),
908         //         next.pid()
909         //     )
910         //     .as_bytes(),
911         // );
912 
913         // CurrentApic.send_eoi();
914         compiler_fence(Ordering::SeqCst);
915 
916         unsafe { ProcessManager::switch_process(prev, next) };
917     } else {
918         assert!(
919             Arc::ptr_eq(&ProcessManager::current_pcb(), &prev),
920             "{}",
921             ProcessManager::current_pcb().basic().name()
922         );
923     }
924 }
925 
926 pub fn sched_fork(pcb: &Arc<ProcessControlBlock>) -> Result<(), SystemError> {
927     let mut prio_guard = pcb.sched_info().prio_data.write_irqsave();
928     let current = ProcessManager::current_pcb();
929 
930     prio_guard.prio = current.sched_info().prio_data.read_irqsave().normal_prio;
931 
932     if PrioUtil::dl_prio(prio_guard.prio) {
933         return Err(SystemError::EAGAIN_OR_EWOULDBLOCK);
934     } else if PrioUtil::rt_prio(prio_guard.prio) {
935         let policy = &pcb.sched_info().sched_policy;
936         *policy.write_irqsave() = SchedPolicy::RT;
937     } else {
938         let policy = &pcb.sched_info().sched_policy;
939         *policy.write_irqsave() = SchedPolicy::CFS;
940     }
941 
942     pcb.sched_info()
943         .sched_entity()
944         .force_mut()
945         .init_entity_runnable_average();
946 
947     Ok(())
948 }
949 
950 pub fn sched_cgroup_fork(pcb: &Arc<ProcessControlBlock>) {
951     __set_task_cpu(pcb, smp_get_processor_id());
952     match pcb.sched_info().policy() {
953         SchedPolicy::RT => todo!(),
954         SchedPolicy::FIFO => todo!(),
955         SchedPolicy::CFS => CompletelyFairScheduler::task_fork(pcb.clone()),
956         SchedPolicy::IDLE => todo!(),
957     }
958 }
959 
960 fn __set_task_cpu(pcb: &Arc<ProcessControlBlock>, cpu: ProcessorId) {
961     // TODO: Fixme There is not implement group sched;
962     let se = pcb.sched_info().sched_entity();
963     let rq = cpu_rq(cpu.data() as usize);
964     se.force_mut().set_cfs(Arc::downgrade(&rq.cfs));
965 }
966 
967 #[inline(never)]
968 pub fn sched_init() {
969     // 初始化percpu变量
970     unsafe {
971         CPU_IRQ_TIME = Some(Vec::with_capacity(PerCpu::MAX_CPU_NUM as usize));
972         CPU_IRQ_TIME
973             .as_mut()
974             .unwrap()
975             .resize_with(PerCpu::MAX_CPU_NUM as usize, || Box::leak(Box::default()));
976 
977         let mut cpu_runqueue = Vec::with_capacity(PerCpu::MAX_CPU_NUM as usize);
978         for cpu in 0..PerCpu::MAX_CPU_NUM as usize {
979             let rq = Arc::new(CpuRunQueue::new(cpu));
980             rq.cfs.force_mut().set_rq(Arc::downgrade(&rq));
981             cpu_runqueue.push(rq);
982         }
983 
984         CPU_RUNQUEUE.init(PerCpuVar::new(cpu_runqueue).unwrap());
985     };
986 }
987 
988 #[inline]
989 pub fn send_resched_ipi(cpu: ProcessorId) {
990     send_ipi(IpiKind::KickCpu, IpiTarget::Specified(cpu));
991 }
992