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(¤t, &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