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 #[allow(dead_code)] 276 fn disable_sched_local(); 277 278 /// 在第一次开启调度之前，进行初始化工作。 279 /// 280 /// 注意区别于sched_init，这个函数只是做初始化时钟的工作等等。 281 fn initial_setup_sched_local() {} 282 } 283 284 /// ## PerCpu的运行队列，其中维护了各个调度器对应的rq 285 #[allow(dead_code)] 286 #[derive(Debug)] 287 pub struct CpuRunQueue { 288 lock: SpinLock<()>, 289 lock_on_who: AtomicUsize, 290 291 cpu: usize, 292 clock_task: u64, 293 clock: u64, 294 prev_irq_time: u64, 295 clock_updata_flags: ClockUpdataFlag, 296 297 /// 过载 298 overload: bool, 299 300 next_balance: u64, 301 302 /// 运行任务数 303 nr_running: usize, 304 305 /// 被阻塞的任务数量 306 nr_uninterruptible: usize, 307 308 /// 记录上次更新负载时间 309 cala_load_update: usize, 310 cala_load_active: usize, 311 312 /// CFS调度器 313 cfs: Arc<CfsRunQueue>, 314 315 clock_pelt: u64, 316 lost_idle_time: u64, 317 clock_idle: u64, 318 319 cfs_tasks: LinkedList<Arc<FairSchedEntity>>, 320 321 /// 最近一次的调度信息 322 sched_info: SchedInfo, 323 324 /// 当前在运行队列上执行的进程 325 current: Weak<ProcessControlBlock>, 326 327 idle: Weak<ProcessControlBlock>, 328 } 329 330 impl CpuRunQueue { 331 pub fn new(cpu: usize) -> Self { 332 Self { 333 lock: SpinLock::new(()), 334 lock_on_who: AtomicUsize::new(usize::MAX), 335 cpu, 336 clock_task: 0, 337 clock: 0, 338 prev_irq_time: 0, 339 clock_updata_flags: ClockUpdataFlag::empty(), 340 overload: false, 341 next_balance: 0, 342 nr_running: 0, 343 nr_uninterruptible: 0, 344 cala_load_update: (clock() + (5 * HZ + 1)) as usize, 345 cala_load_active: 0, 346 cfs: Arc::new(CfsRunQueue::new()), 347 clock_pelt: 0, 348 lost_idle_time: 0, 349 clock_idle: 0, 350 cfs_tasks: LinkedList::new(), 351 sched_info: SchedInfo::default(), 352 current: Weak::new(), 353 idle: Weak::new(), 354 } 355 } 356 357 /// 此函数只能在关中断的情况下使用！！！ 358 /// 获取到rq的可变引用，需要注意的是返回的第二个值需要确保其生命周期 359 /// 所以可以说这个函数是unsafe的，需要确保正确性 360 /// 在中断上下文，关中断的情况下，此函数是安全的 361 pub fn self_lock(&self) -> (&mut Self, Option<SpinLockGuard<()>>) { 362 if self.lock.is_locked() 363 && smp_get_processor_id().data() as usize == self.lock_on_who.load(Ordering::SeqCst) 364 { 365 // 在本cpu已上锁则可以直接拿 366 ( 367 unsafe { 368 (self as *const Self as usize as *mut Self) 369 .as_mut() 370 .unwrap() 371 }, 372 None, 373 ) 374 } else { 375 // 否则先上锁再拿 376 let guard = self.lock(); 377 ( 378 unsafe { 379 (self as *const Self as usize as *mut Self) 380 .as_mut() 381 .unwrap() 382 }, 383 Some(guard), 384 ) 385 } 386 } 387 388 fn lock(&self) -> SpinLockGuard<()> { 389 let guard = self.lock.lock_irqsave(); 390 391 // 更新在哪一个cpu上锁 392 self.lock_on_who 393 .store(smp_get_processor_id().data() as usize, Ordering::SeqCst); 394 395 guard 396 } 397 398 pub fn enqueue_task(&mut self, pcb: Arc<ProcessControlBlock>, flags: EnqueueFlag) { 399 if !flags.contains(EnqueueFlag::ENQUEUE_NOCLOCK) { 400 self.update_rq_clock(); 401 } 402 403 if !flags.contains(EnqueueFlag::ENQUEUE_RESTORE) { 404 let sched_info = pcb.sched_info().sched_stat.upgradeable_read_irqsave(); 405 if sched_info.last_queued == 0 { 406 sched_info.upgrade().last_queued = self.clock; 407 } 408 } 409 410 match pcb.sched_info().policy() { 411 SchedPolicy::CFS => CompletelyFairScheduler::enqueue(self, pcb, flags), 412 SchedPolicy::FIFO => todo!(), 413 SchedPolicy::RT => todo!(), 414 SchedPolicy::IDLE => IdleScheduler::enqueue(self, pcb, flags), 415 } 416 417 // TODO:https://code.dragonos.org.cn/xref/linux-6.6.21/kernel/sched/core.c#239 418 } 419 420 pub fn dequeue_task(&mut self, pcb: Arc<ProcessControlBlock>, flags: DequeueFlag) { 421 // TODO:sched_core 422 423 if !flags.contains(DequeueFlag::DEQUEUE_NOCLOCK) { 424 self.update_rq_clock() 425 } 426 427 if !flags.contains(DequeueFlag::DEQUEUE_SAVE) { 428 let sched_info = pcb.sched_info().sched_stat.upgradeable_read_irqsave(); 429 430 if sched_info.last_queued > 0 { 431 let delta = self.clock - sched_info.last_queued; 432 433 let mut sched_info = sched_info.upgrade(); 434 sched_info.last_queued = 0; 435 sched_info.run_delay += delta as usize; 436 437 self.sched_info.run_delay += delta as usize; 438 } 439 } 440 441 match pcb.sched_info().policy() { 442 SchedPolicy::CFS => CompletelyFairScheduler::dequeue(self, pcb, flags), 443 SchedPolicy::FIFO => todo!(), 444 SchedPolicy::RT => todo!(), 445 SchedPolicy::IDLE => IdleScheduler::dequeue(self, pcb, flags), 446 } 447 } 448 449 /// 启用一个任务，将加入队列 450 pub fn activate_task(&mut self, pcb: &Arc<ProcessControlBlock>, mut flags: EnqueueFlag) { 451 if *pcb.sched_info().on_rq.lock_irqsave() == OnRq::Migrating { 452 flags |= EnqueueFlag::ENQUEUE_MIGRATED; 453 } 454 455 if flags.contains(EnqueueFlag::ENQUEUE_MIGRATED) { 456 todo!() 457 } 458 459 self.enqueue_task(pcb.clone(), flags); 460 461 *pcb.sched_info().on_rq.lock_irqsave() = OnRq::Queued; 462 } 463 464 /// 检查对应的task是否可以抢占当前运行的task 465 #[allow(clippy::comparison_chain)] 466 pub fn check_preempt_currnet(&mut self, pcb: &Arc<ProcessControlBlock>, flags: WakeupFlags) { 467 if pcb.sched_info().policy() == self.current().sched_info().policy() { 468 match self.current().sched_info().policy() { 469 SchedPolicy::CFS => { 470 CompletelyFairScheduler::check_preempt_currnet(self, pcb, flags) 471 } 472 SchedPolicy::FIFO => todo!(), 473 SchedPolicy::RT => todo!(), 474 SchedPolicy::IDLE => IdleScheduler::check_preempt_currnet(self, pcb, flags), 475 } 476 } else if pcb.sched_info().policy() < self.current().sched_info().policy() { 477 // 调度优先级更高 478 self.resched_current(); 479 } 480 481 if *self.current().sched_info().on_rq.lock_irqsave() == OnRq::Queued 482 && self.current().flags().contains(ProcessFlags::NEED_SCHEDULE) 483 { 484 self.clock_updata_flags 485 .insert(ClockUpdataFlag::RQCF_REQ_SKIP); 486 } 487 } 488 489 /// 禁用一个任务，将离开队列 490 pub fn deactivate_task(&mut self, pcb: Arc<ProcessControlBlock>, flags: DequeueFlag) { 491 *pcb.sched_info().on_rq.lock_irqsave() = if flags.contains(DequeueFlag::DEQUEUE_SLEEP) { 492 OnRq::None 493 } else { 494 OnRq::Migrating 495 }; 496 497 self.dequeue_task(pcb, flags); 498 } 499 500 #[inline] 501 pub fn cfs_rq(&self) -> Arc<CfsRunQueue> { 502 self.cfs.clone() 503 } 504 505 /// 更新rq时钟 506 pub fn update_rq_clock(&mut self) { 507 // 需要跳过这次时钟更新 508 if self 509 .clock_updata_flags 510 .contains(ClockUpdataFlag::RQCF_ACT_SKIP) 511 { 512 return; 513 } 514 515 let clock = SchedClock::sched_clock_cpu(self.cpu); 516 if clock < self.clock { 517 return; 518 } 519 520 let delta = clock - self.clock; 521 self.clock += delta; 522 // error!("clock {}", self.clock); 523 self.update_rq_clock_task(delta); 524 } 525 526 /// 更新任务时钟 527 pub fn update_rq_clock_task(&mut self, mut delta: u64) { 528 let mut irq_delta = irq_time_read(self.cpu) - self.prev_irq_time; 529 // if self.cpu == 0 { 530 // error!( 531 // "cpu 0 delta {delta} irq_delta {} irq_time_read(self.cpu) {} self.prev_irq_time {}", 532 // irq_delta, 533 // irq_time_read(self.cpu), 534 // self.prev_irq_time 535 // ); 536 // } 537 compiler_fence(Ordering::SeqCst); 538 539 if irq_delta > delta { 540 irq_delta = delta; 541 } 542 543 self.prev_irq_time += irq_delta; 544 545 delta -= irq_delta; 546 547 // todo: psi? 548 549 // send_to_default_serial8250_port(format!("\n{delta}\n",).as_bytes()); 550 compiler_fence(Ordering::SeqCst); 551 self.clock_task += delta; 552 compiler_fence(Ordering::SeqCst); 553 // if self.cpu == 0 { 554 // error!("cpu {} clock_task {}", self.cpu, self.clock_task); 555 // } 556 // todo: pelt? 557 } 558 559 /// 计算当前进程中的可执行数量 560 fn calculate_load_fold_active(&mut self, adjust: usize) -> usize { 561 let mut nr_active = self.nr_running - adjust; 562 nr_active += self.nr_uninterruptible; 563 let mut delta = 0; 564 565 if nr_active != self.cala_load_active { 566 delta = nr_active - self.cala_load_active; 567 self.cala_load_active = nr_active; 568 } 569 570 delta 571 } 572 573 /// ## tick计算全局负载 574 pub fn calculate_global_load_tick(&mut self) { 575 if clock() < self.cala_load_update as u64 { 576 // 如果当前时间在上次更新时间之前，则直接返回 577 return; 578 } 579 580 let delta = self.calculate_load_fold_active(0); 581 582 if delta != 0 { 583 CALCULATE_LOAD_TASKS.fetch_add(delta, Ordering::SeqCst); 584 } 585 586 self.cala_load_update += LOAD_FREQ; 587 } 588 589 pub fn add_nr_running(&mut self, nr_running: usize) { 590 let prev = self.nr_running; 591 592 self.nr_running = prev + nr_running; 593 if prev < 2 && self.nr_running >= 2 && !self.overload { 594 self.overload = true; 595 } 596 } 597 598 pub fn sub_nr_running(&mut self, count: usize) { 599 self.nr_running -= count; 600 } 601 602 /// 在运行idle？ 603 pub fn sched_idle_rq(&self) -> bool { 604 return unlikely( 605 self.nr_running == self.cfs.idle_h_nr_running as usize && self.nr_running > 0, 606 ); 607 } 608 609 #[inline] 610 pub fn current(&self) -> Arc<ProcessControlBlock> { 611 self.current.upgrade().unwrap() 612 } 613 614 #[inline] 615 pub fn set_current(&mut self, pcb: Weak<ProcessControlBlock>) { 616 self.current = pcb; 617 } 618 619 #[inline] 620 pub fn set_idle(&mut self, pcb: Weak<ProcessControlBlock>) { 621 self.idle = pcb; 622 } 623 624 #[inline] 625 pub fn clock_task(&self) -> u64 { 626 self.clock_task 627 } 628 629 /// 重新调度当前进程 630 pub fn resched_current(&self) { 631 let current = self.current(); 632 633 // 又需要被调度？ 634 if unlikely(current.flags().contains(ProcessFlags::NEED_SCHEDULE)) { 635 return; 636 } 637 638 let cpu = self.cpu; 639 640 if cpu == smp_get_processor_id().data() as usize { 641 // assert!( 642 // Arc::ptr_eq(¤t, &ProcessManager::current_pcb()), 643 // "rq current name {} process current {}", 644 // current.basic().name().to_string(), 645 // ProcessManager::current_pcb().basic().name().to_string(), 646 // ); 647 // 设置需要调度 648 ProcessManager::current_pcb() 649 .flags() 650 .insert(ProcessFlags::NEED_SCHEDULE); 651 return; 652 } 653 654 // 向目标cpu发送重调度ipi 655 send_resched_ipi(ProcessorId::new(cpu as u32)); 656 } 657 658 /// 选择下一个task 659 pub fn pick_next_task(&mut self, prev: Arc<ProcessControlBlock>) -> Arc<ProcessControlBlock> { 660 if likely(prev.sched_info().policy() >= SchedPolicy::CFS) 661 && self.nr_running == self.cfs.h_nr_running as usize 662 { 663 let p = CompletelyFairScheduler::pick_next_task(self, Some(prev.clone())); 664 665 if let Some(pcb) = p.as_ref() { 666 return pcb.clone(); 667 } else { 668 // error!( 669 // "pick idle cfs rq {:?}", 670 // self.cfs_rq() 671 // .entities 672 // .iter() 673 // .map(|x| x.1.pid) 674 // .collect::<Vec<_>>() 675 // ); 676 match prev.sched_info().policy() { 677 SchedPolicy::FIFO => todo!(), 678 SchedPolicy::RT => todo!(), 679 SchedPolicy::CFS => CompletelyFairScheduler::put_prev_task(self, prev), 680 SchedPolicy::IDLE => IdleScheduler::put_prev_task(self, prev), 681 } 682 // 选择idle 683 return self.idle.upgrade().unwrap(); 684 } 685 } 686 687 todo!() 688 } 689 } 690 691 bitflags! { 692 pub struct SchedFeature:u32 { 693 /// 给予睡眠任务仅有 50% 的服务赤字。这意味着睡眠任务在被唤醒后会获得一定的服务，但不能过多地占用资源。 694 const GENTLE_FAIR_SLEEPERS = 1 << 0; 695 /// 将新任务排在前面，以避免已经运行的任务被饿死 696 const START_DEBIT = 1 << 1; 697 /// 在调度时优先选择上次唤醒的任务，因为它可能会访问之前唤醒的任务所使用的数据，从而提高缓存局部性。 698 const NEXT_BUDDY = 1 << 2; 699 /// 在调度时优先选择上次运行的任务，因为它可能会访问与之前运行的任务相同的数据，从而提高缓存局部性。 700 const LAST_BUDDY = 1 << 3; 701 /// 认为任务的伙伴（buddy）在缓存中是热点，减少缓存伙伴被迁移的可能性，从而提高缓存局部性。 702 const CACHE_HOT_BUDDY = 1 << 4; 703 /// 允许唤醒时抢占当前任务。 704 const WAKEUP_PREEMPTION = 1 << 5; 705 /// 基于任务未运行时间来减少 CPU 的容量。 706 const NONTASK_CAPACITY = 1 << 6; 707 /// 将远程唤醒排队到目标 CPU，并使用调度器 IPI 处理它们，以减少运行队列锁的争用。 708 const TTWU_QUEUE = 1 << 7; 709 /// 在唤醒时尝试限制对最后级联缓存（LLC）域的无谓扫描。 710 const SIS_UTIL = 1 << 8; 711 /// 在 RT（Real-Time）任务迁移时，通过发送 IPI 来减少 CPU 之间的锁竞争。 712 const RT_PUSH_IPI = 1 << 9; 713 /// 启用估计的 CPU 利用率功能，用于调度决策。 714 const UTIL_EST = 1 << 10; 715 const UTIL_EST_FASTUP = 1 << 11; 716 /// 启用备选调度周期 717 const ALT_PERIOD = 1 << 12; 718 /// 启用基本时间片 719 const BASE_SLICE = 1 << 13; 720 } 721 722 pub struct EnqueueFlag: u8 { 723 const ENQUEUE_WAKEUP = 0x01; 724 const ENQUEUE_RESTORE = 0x02; 725 const ENQUEUE_MOVE = 0x04; 726 const ENQUEUE_NOCLOCK = 0x08; 727 728 const ENQUEUE_MIGRATED = 0x40; 729 730 const ENQUEUE_INITIAL = 0x80; 731 } 732 733 pub struct DequeueFlag: u8 { 734 const DEQUEUE_SLEEP = 0x01; 735 const DEQUEUE_SAVE = 0x02; /* Matches ENQUEUE_RESTORE */ 736 const DEQUEUE_MOVE = 0x04; /* Matches ENQUEUE_MOVE */ 737 const DEQUEUE_NOCLOCK = 0x08; /* Matches ENQUEUE_NOCLOCK */ 738 } 739 740 pub struct WakeupFlags: u8 { 741 /* Wake flags. The first three directly map to some SD flag value */ 742 const WF_EXEC = 0x02; /* Wakeup after exec; maps to SD_BALANCE_EXEC */ 743 const WF_FORK = 0x04; /* Wakeup after fork; maps to SD_BALANCE_FORK */ 744 const WF_TTWU = 0x08; /* Wakeup; maps to SD_BALANCE_WAKE */ 745 746 const WF_SYNC = 0x10; /* Waker goes to sleep after wakeup */ 747 const WF_MIGRATED = 0x20; /* Internal use, task got migrated */ 748 const WF_CURRENT_CPU = 0x40; /* Prefer to move the wakee to the current CPU. */ 749 } 750 751 pub struct SchedMode: u8 { 752 /* 753 * Constants for the sched_mode argument of __schedule(). 754 * 755 * The mode argument allows RT enabled kernels to differentiate a 756 * preemption from blocking on an 'sleeping' spin/rwlock. Note that 757 * SM_MASK_PREEMPT for !RT has all bits set, which allows the compiler to 758 * optimize the AND operation out and just check for zero. 759 */ 760 /// 在调度过程中不会再次进入队列，即需要手动唤醒 761 const SM_NONE = 0x0; 762 /// 重新加入队列，即当前进程被抢占，需要时钟调度 763 const SM_PREEMPT = 0x1; 764 /// rt相关 765 const SM_RTLOCK_WAIT = 0x2; 766 /// 默认与SM_PREEMPT相同 767 const SM_MASK_PREEMPT = Self::SM_PREEMPT.bits; 768 } 769 } 770 771 #[derive(Copy, Clone, Debug, PartialEq)] 772 pub enum OnRq { 773 Queued, 774 Migrating, 775 None, 776 } 777 778 impl ProcessManager { 779 pub fn update_process_times(user_tick: bool) { 780 let pcb = Self::current_pcb(); 781 CpuTimeFunc::irqtime_account_process_tick(&pcb, user_tick, 1); 782 783 scheduler_tick(); 784 } 785 } 786 787 /// ## 时钟tick时调用此函数 788 pub fn scheduler_tick() { 789 fence(Ordering::SeqCst); 790 // 获取当前CPU索引 791 let cpu_idx = smp_get_processor_id().data() as usize; 792 793 // 获取当前CPU的请求队列 794 let rq = cpu_rq(cpu_idx); 795 796 let (rq, guard) = rq.self_lock(); 797 798 // 获取当前请求队列的当前请求 799 let current = rq.current(); 800 801 // 更新请求队列时钟 802 rq.update_rq_clock(); 803 804 match current.sched_info().policy() { 805 SchedPolicy::CFS => CompletelyFairScheduler::tick(rq, current, false), 806 SchedPolicy::FIFO => todo!(), 807 SchedPolicy::RT => todo!(), 808 SchedPolicy::IDLE => IdleScheduler::tick(rq, current, false), 809 } 810 811 rq.calculate_global_load_tick(); 812 813 drop(guard); 814 // TODO:处理负载均衡 815 } 816 817 /// ## 执行调度 818 /// 若preempt_count不为0则报错 819 #[inline] 820 pub fn schedule(sched_mod: SchedMode) { 821 let _guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 822 assert_eq!(ProcessManager::current_pcb().preempt_count(), 0); 823 __schedule(sched_mod); 824 } 825 826 /// ## 执行调度 827 /// 此函数与schedule的区别为，该函数不会检查preempt_count 828 /// 适用于时钟中断等场景 829 pub fn __schedule(sched_mod: SchedMode) { 830 let cpu = smp_get_processor_id().data() as usize; 831 let rq = cpu_rq(cpu); 832 833 let mut prev = rq.current(); 834 if let ProcessState::Exited(_) = prev.clone().sched_info().inner_lock_read_irqsave().state() { 835 // 从exit进的Schedule 836 prev = ProcessManager::current_pcb(); 837 } 838 839 // TODO: hrtick_clear(rq); 840 841 let (rq, _guard) = rq.self_lock(); 842 843 rq.clock_updata_flags = ClockUpdataFlag::from_bits_truncate(rq.clock_updata_flags.bits() << 1); 844 845 rq.update_rq_clock(); 846 rq.clock_updata_flags = ClockUpdataFlag::RQCF_UPDATE; 847 848 // kBUG!( 849 // "before cfs rq pcbs {:?}\nvruntimes {:?}\n", 850 // rq.cfs 851 // .entities 852 // .iter() 853 // .map(|x| { x.1.pcb().pid() }) 854 // .collect::<Vec<_>>(), 855 // rq.cfs 856 // .entities 857 // .iter() 858 // .map(|x| { x.1.vruntime }) 859 // .collect::<Vec<_>>(), 860 // ); 861 // warn!( 862 // "before cfs rq {:?} prev {:?}", 863 // rq.cfs 864 // .entities 865 // .iter() 866 // .map(|x| { x.1.pcb().pid() }) 867 // .collect::<Vec<_>>(), 868 // prev.pid() 869 // ); 870 871 // error!("prev pid {:?} {:?}", prev.pid(), prev.sched_info().policy()); 872 if !sched_mod.contains(SchedMode::SM_MASK_PREEMPT) 873 && prev.sched_info().policy() != SchedPolicy::IDLE 874 && prev.sched_info().inner_lock_read_irqsave().is_mark_sleep() 875 { 876 // warn!("deactivate_task prev {:?}", prev.pid()); 877 // TODO: 这里需要处理信号 878 // https://code.dragonos.org.cn/xref/linux-6.6.21/kernel/sched/core.c?r=&mo=172979&fi=6578#6630 879 rq.deactivate_task( 880 prev.clone(), 881 DequeueFlag::DEQUEUE_SLEEP | DequeueFlag::DEQUEUE_NOCLOCK, 882 ); 883 } 884 885 let next = rq.pick_next_task(prev.clone()); 886 887 // kBUG!( 888 // "after cfs rq pcbs {:?}\nvruntimes {:?}\n", 889 // rq.cfs 890 // .entities 891 // .iter() 892 // .map(|x| { x.1.pcb().pid() }) 893 // .collect::<Vec<_>>(), 894 // rq.cfs 895 // .entities 896 // .iter() 897 // .map(|x| { x.1.vruntime }) 898 // .collect::<Vec<_>>(), 899 // ); 900 901 // error!("next {:?}", next.pid()); 902 903 prev.flags().remove(ProcessFlags::NEED_SCHEDULE); 904 fence(Ordering::SeqCst); 905 if likely(!Arc::ptr_eq(&prev, &next)) { 906 rq.set_current(Arc::downgrade(&next)); 907 // warn!( 908 // "switch_process prev {:?} next {:?} sched_mode {sched_mod:?}", 909 // prev.pid(), 910 // next.pid() 911 // ); 912 913 // send_to_default_serial8250_port( 914 // format!( 915 // "switch_process prev {:?} next {:?} sched_mode {sched_mod:?}\n", 916 // prev.pid(), 917 // next.pid() 918 // ) 919 // .as_bytes(), 920 // ); 921 922 // CurrentApic.send_eoi(); 923 compiler_fence(Ordering::SeqCst); 924 925 unsafe { ProcessManager::switch_process(prev, next) }; 926 } else { 927 assert!( 928 Arc::ptr_eq(&ProcessManager::current_pcb(), &prev), 929 "{}", 930 ProcessManager::current_pcb().basic().name() 931 ); 932 } 933 } 934 935 pub fn sched_fork(pcb: &Arc<ProcessControlBlock>) -> Result<(), SystemError> { 936 let mut prio_guard = pcb.sched_info().prio_data.write_irqsave(); 937 let current = ProcessManager::current_pcb(); 938 939 prio_guard.prio = current.sched_info().prio_data.read_irqsave().normal_prio; 940 941 if PrioUtil::dl_prio(prio_guard.prio) { 942 return Err(SystemError::EAGAIN_OR_EWOULDBLOCK); 943 } else if PrioUtil::rt_prio(prio_guard.prio) { 944 let policy = &pcb.sched_info().sched_policy; 945 *policy.write_irqsave() = SchedPolicy::RT; 946 } else { 947 let policy = &pcb.sched_info().sched_policy; 948 *policy.write_irqsave() = SchedPolicy::CFS; 949 } 950 951 pcb.sched_info() 952 .sched_entity() 953 .force_mut() 954 .init_entity_runnable_average(); 955 956 Ok(()) 957 } 958 959 pub fn sched_cgroup_fork(pcb: &Arc<ProcessControlBlock>) { 960 __set_task_cpu(pcb, smp_get_processor_id()); 961 match pcb.sched_info().policy() { 962 SchedPolicy::RT => todo!(), 963 SchedPolicy::FIFO => todo!(), 964 SchedPolicy::CFS => CompletelyFairScheduler::task_fork(pcb.clone()), 965 SchedPolicy::IDLE => todo!(), 966 } 967 } 968 969 fn __set_task_cpu(pcb: &Arc<ProcessControlBlock>, cpu: ProcessorId) { 970 // TODO: Fixme There is not implement group sched; 971 let se = pcb.sched_info().sched_entity(); 972 let rq = cpu_rq(cpu.data() as usize); 973 se.force_mut().set_cfs(Arc::downgrade(&rq.cfs)); 974 } 975 976 #[inline(never)] 977 pub fn sched_init() { 978 // 初始化percpu变量 979 unsafe { 980 CPU_IRQ_TIME = Some(Vec::with_capacity(PerCpu::MAX_CPU_NUM as usize)); 981 CPU_IRQ_TIME 982 .as_mut() 983 .unwrap() 984 .resize_with(PerCpu::MAX_CPU_NUM as usize, || Box::leak(Box::default())); 985 986 let mut cpu_runqueue = Vec::with_capacity(PerCpu::MAX_CPU_NUM as usize); 987 for cpu in 0..PerCpu::MAX_CPU_NUM as usize { 988 let rq = Arc::new(CpuRunQueue::new(cpu)); 989 rq.cfs.force_mut().set_rq(Arc::downgrade(&rq)); 990 cpu_runqueue.push(rq); 991 } 992 993 CPU_RUNQUEUE.init(PerCpuVar::new(cpu_runqueue).unwrap()); 994 }; 995 } 996 997 #[inline] 998 pub fn send_resched_ipi(cpu: ProcessorId) { 999 send_ipi(IpiKind::KickCpu, IpiTarget::Specified(cpu)); 1000 } 1001