atmos/kernel/
scheduler.rs

1//! # 優先度ベースのプリエンプティブ・ラウンドロビン・スケジューラ
2//!
3//! このモジュールは、各CPUコアごとに独立したランキューを持つ（Per-Core SMP）、優先度ベースのプリエンプティブ・ラウンドロビン・スケジューラの実装を提供します。
4//! EL1カーネルスレッドとEL0ユーザープロセスの両方のマルチプロセス環境をサポートしています。
5
6#![allow(dead_code)]
7#![allow(static_mut_refs)]
8extern crate alloc;
9use alloc::vec::Vec;
10use core::sync::atomic::{AtomicUsize, Ordering};
11use spin::Mutex;
12
13extern "C" {
14    fn switch_context(from_sp: *mut usize, to_sp: usize);
15    fn enter_userspace(user_entry: usize, user_sp: usize, kernel_sp: usize);
16}
17
18/// プロセスの状態を表す列挙型。
19#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub enum ProcessState {
21    /// 実行中
22    Running,
23    /// 実行可能状態
24    Ready,
25    /// 待機状態 (スリープ等)
26    Waiting,
27    /// 終了状態
28    Terminated,
29}
30
31/// プロセスのスケジュール優先度を表す列挙型。
32#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
33pub enum Priority {
34    /// 低優先度
35    Low = 0,
36    /// 通常優先度
37    Normal = 1,
38    /// 高優先度
39    High = 2,
40}
41
42/// プロセス制御ブロック (PCB)。プロセスのメタデータ、実行コンテキスト、スタック情報を保持します。
43pub struct Process {
44    /// 一意のプロセスID (PID)
45    pub id: usize,
46    /// デバッグ用のプロセス名
47    pub name: &'static str,
48    /// 現在のプロセスの状態
49    pub state: ProcessState,
50    /// プロセスのスケジュール優先度
51    pub priority: Priority,
52    /// 保存されたスタックポインタの値 (コンテキストスイッチ時に書き換えられる)
53    pub stack_ptr: usize,
54    /// プロセスのスタックメモリ領域 (EL1スレッド用またはEL0ユーザースタック用)
55    pub stack_mem: Vec<u8>,
56    /// `Waiting` 状態時の残りの待機チック数
57    pub wait_ticks: usize,
58    /// プロセスに割り当てられたTTBR0ページテーブルの物理アドレス
59    pub page_table_phys_addr: u64,
60    /// 飢餓防止のための優先度スコアに加算されるカウント
61    pub starvation_count: usize,
62    /// カーネル空間 (EL1) で動作するか、ユーザー空間 (EL0) で動作するかのフラグ (true: EL1, false: EL0)
63    pub is_kernel: bool,
64    /// EL0プロセスのエントリポイント
65    pub user_entry: usize,
66    /// EL0プロセスのユーザースタックポインタ
67    pub user_stack_ptr: usize,
68    /// EL0プロセスがトラップした際に使用するEL1カーネルスタック
69    pub kernel_stack: Vec<u8>,
70    /// 残りのタイムスライス (チック数)
71    pub time_slice: usize,
72    /// 再スケジュールが必要であることを示すフラグ
73    pub need_resched: bool,
74}
75
76/// 各コアで動作するプロセスのランキュー構造体。
77pub struct CoreRunqueue {
78    /// キューに含まれるプロセスのリスト
79    pub processes: Vec<Process>,
80    /// 現在実行中のプロセスのインデックス
81    pub current_idx: Option<usize>,
82}
83
84/// 次に割り当てるべきプロセスIDを管理するアトミックカウンタ。
85static NEXT_PID: AtomicUsize = AtomicUsize::new(1);
86
87/// 各コア固有のランキュー (Per-Core Runqueues)。
88/// 各コアが独立してランキューに対する排他制御（Mutex）を行います。
89static RUNQUEUES: [Mutex<Option<CoreRunqueue>>; 4] = [
90    Mutex::new(None),
91    Mutex::new(None),
92    Mutex::new(None),
93    Mutex::new(None),
94];
95
96/// 終了したプロセスの「墓場」。
97/// `exit()` は現在実行中のプロセスのカーネルスタック上で動作するため、
98/// その場で `Process` をドロップすると自身のスタックを解放してしまい、Use-After-Free が発生します。
99/// そのため、一度この墓場領域に退避させ、別のプロセスへのコンテキストスイッチが行われた後
100///（そのスタックから外れた後）に、`reap_zombies()` を通じて安全にメモリを解放します。
101static ZOMBIES: [Mutex<Vec<Process>>; 4] = [
102    Mutex::new(Vec::new()),
103    Mutex::new(Vec::new()),
104    Mutex::new(Vec::new()),
105    Mutex::new(Vec::new()),
106];
107
108/// 現在のスタックポインタ (SP) の値を取得します。
109#[inline]
110fn current_sp() -> usize {
111    let sp: usize;
112    unsafe {
113        core::arch::asm!("mov {}, sp", out(reg) sp);
114    }
115    sp
116}
117
118// --- プリエンプティブ・スケジューリング制御用カウンタ・ヘルパー ---
119
120/// 各コアごとのプリエンプション禁止カウンタ。
121/// `preempt_count == 0` の時のみプリエンプション（強制タスク切り替え）が許可されます。
122static PREEMPT_COUNTS: [AtomicUsize; 4] = [
123    AtomicUsize::new(0),
124    AtomicUsize::new(0),
125    AtomicUsize::new(0),
126    AtomicUsize::new(0),
127];
128
129/// 現在のコアのプリエンプションを一時的に禁止します（カウントをインクリメント）。
130pub fn preempt_disable() {
131    let cid = core_id();
132    PREEMPT_COUNTS[cid].fetch_add(1, Ordering::SeqCst);
133}
134
135/// プリエンプション禁止を解除します（カウントをデクリメント）。
136/// カウントが `0` に戻り、かつ再スケジュール要求（`need_resched`）があれば即座に切り替えを実行します。
137pub fn preempt_enable() {
138    let cid = core_id();
139    let old = PREEMPT_COUNTS[cid].fetch_sub(1, Ordering::SeqCst);
140    if old == 1 {
141        // preempt_count が 0 に戻り、再スケジュールが必要なら yield_now()
142        if should_preempt() {
143            yield_now();
144        }
145    }
146}
147
148/// 現在のコアでプリエンプションが許可されている（preempt_count == 0）かを判定します。
149pub fn is_preempt_enabled() -> bool {
150    let cid = core_id();
151    PREEMPT_COUNTS[cid].load(Ordering::SeqCst) == 0
152}
153
154/// 現在のコアでプリエンプション（強制切り替え）を実行すべき状態かを判定します。
155pub fn should_preempt() -> bool {
156    if !is_preempt_enabled() {
157        return false;
158    }
159    let cid = core_id();
160    // RUNQUEUES に対するデッドロックを防ぐため try_lock を使用
161    if let Some(rq_lock) = RUNQUEUES[cid].try_lock() {
162        if let Some(rq) = rq_lock.as_ref() {
163            if let Some(idx) = rq.current_idx {
164                if idx < rq.processes.len() {
165                    return rq.processes[idx].need_resched;
166                }
167            }
168        }
169    }
170    false
171}
172
173/// タイマー割り込み（Tick）から毎チック呼び出され、プロセスの残りタイムスライスを管理します。
174pub fn scheduler_tick() {
175    let cid = core_id();
176    // preempt_disable であってもタイムスライス自体はデクリメントします。
177    // (実際のプリエンプションは preempt_enable または割り込み出口まで保留されます)
178    // 【2026-08-25 バグ修正】ここは `lock()` で**待って**いた。
179    //
180    // この関数はタイマ割り込みから呼ばれる（`interrupt.rs`）。
181    // ところがスレッド側は `RUNQUEUES[cid]` を割り込み許可のまま
182    // 取る箇所が 12 ある（`spawn`、`yield_now` の一部、`sleep` など）。
183    // そのスレッドを同じコアのタイマ割り込みが叩くと、
184    // ハンドラは自分が中断させた相手の持つロックを待つことになり、
185    // **そのコアが永久に固まる**（割り込み出口へ戻れないので、
186    // 相手が解放する機会も来ない）。
187    //
188    // 取り逃した 1 tick はタイムスライスの数え落としにすぎず、
189    // 次の tick で数え直される。**待たずに諦めるのが正しい。**
190    //
191    // 同じ理由で `should_preempt` とパニックハンドラ用の 3 関数は
192    // 既に `try_lock` を使っている。ここだけ作法が違っていた。
193    let Some(mut rq_lock) = RUNQUEUES[cid].try_lock() else {
194        return;
195    };
196    if let Some(rq) = rq_lock.as_mut() {
197        if let Some(idx) = rq.current_idx {
198            if idx < rq.processes.len() {
199                let p = &mut rq.processes[idx];
200                if p.id != 0 && p.name != "idle_core" {
201                    if p.time_slice > 0 {
202                        p.time_slice -= 1;
203                    }
204                    if p.time_slice == 0 {
205                        p.need_resched = true;
206                    }
207                }
208            }
209        }
210    }
211}
212
213/// 指定されたスタックポインタ (SP) が、メモリ領域に含まれるかを判定します。
214fn stack_contains(mem: &[u8], sp: usize) -> bool {
215    let base = mem.as_ptr() as usize;
216    sp >= base && sp < base + mem.len()
217}
218
219/// 現在のスタックポインタ (SP) がそのスタック上に存在しないゾンビプロセス（終了済みプロセス）を解放します。
220/// まだスタックが使用中のプロセス（exit直後の自分自身など）は、次回以降のクリーンアップに持ち越します。
221fn reap_zombies(cid: usize) {
222    let sp = current_sp();
223    let mut z = ZOMBIES[cid].lock();
224    z.retain(|p| stack_contains(&p.kernel_stack, sp) || stack_contains(&p.stack_mem, sp));
225}
226
227/// 現在実行中のCPUコアのID (0〜3) を取得します。
228/// `mpidr_el1` レジスタからアフィニティレベル0を取得します。
229#[inline]
230pub fn core_id() -> usize {
231    let mpidr: u64;
232    unsafe {
233        core::arch::asm!("mrs {}, mpidr_el1", out(reg) mpidr);
234    }
235    (mpidr & 0xFF) as usize
236}
237
238/// スケジューラの初期化処理。
239/// 起動コア (Core 0) 用の初期プロセス `kernel_main` を登録し、他のコアのランキューを空で初期化します。
240pub fn init() {
241    let current_ttbr0: u64;
242    unsafe {
243        core::arch::asm!("mrs {}, ttbr0_el1", out(reg) current_ttbr0);
244    }
245
246    let mut rq0 = RUNQUEUES[0].lock();
247    let processes = alloc::vec![Process {
248        id: 0,
249        name: "kernel_main",
250        state: ProcessState::Running,
251        priority: Priority::High,
252        stack_ptr: 0,
253        stack_mem: Vec::new(),
254        wait_ticks: 0,
255        page_table_phys_addr: current_ttbr0,
256        starvation_count: 0,
257        is_kernel: true,
258        user_entry: 0,
259        user_stack_ptr: 0,
260        kernel_stack: Vec::new(),
261        time_slice: 10,
262        need_resched: false,
263    }];
264
265    *rq0 = Some(CoreRunqueue {
266        processes,
267        current_idx: Some(0),
268    });
269
270    for i in 1..4 {
271        let mut rq = RUNQUEUES[i].lock();
272        *rq = Some(CoreRunqueue {
273            processes: Vec::new(),
274            current_idx: None,
275        });
276    }
277}
278
279/// カーネル空間 (EL1) で実行される新しいプロセス (カーネルスレッド) を生成し、
280/// ロードバランシングに基づいてプロセス数が最も少ないコアのランキューに登録します。
281///
282/// # 引数
283/// * `entry` - プロセスのメイン処理となる関数へのポインタ
284/// * `priority` - スケジュール優先度
285/// * `name` - プロセスの識別名
286///
287/// # 戻り値
288/// 生成されたプロセスの PID。OOMなどのメモリ不足により起動できなかった場合は `0` を返します。
289pub fn spawn(entry: fn(), priority: Priority, name: &'static str) -> usize {
290    let pid = NEXT_PID.fetch_add(1, Ordering::SeqCst);
291
292    let stack_size = 1024 * 1024;
293
294    // 空きヒープ容量をチェックし、OOMによるパニックを防ぐ
295    let (used, total) = crate::kernel::allocator::get_heap_stats();
296    let free = total.saturating_sub(used);
297    if free < stack_size + 16 * 1024 {
298        crate::println!("[scheduler] WARNING: Insufficient heap memory to spawn process '{}' (Free: {} KB, Need: {} KB)", name, free / 1024, stack_size / 1024);
299        return 0;
300    }
301
302    let stack_mem = alloc::vec![0u8; stack_size];
303
304    let stack_top = stack_mem.as_ptr() as usize + stack_size;
305    let aligned_top = stack_top & !0xF;
306    let initial_sp = aligned_top - 240;
307
308    let sp_ptr = initial_sp as *mut usize;
309    unsafe {
310        for j in 0..10 {
311            sp_ptr.add(j).write_volatile(0);
312        }
313        sp_ptr.add(10).write_volatile(0);
314        sp_ptr.add(11).write_volatile(entry as usize);
315    }
316
317    let pt_addr = crate::kernel::mmu::create_process_page_table();
318
319    let new_proc = Process {
320        id: pid,
321        name,
322        state: ProcessState::Ready,
323        priority,
324        stack_ptr: initial_sp,
325        stack_mem,
326        wait_ticks: 0,
327        page_table_phys_addr: pt_addr,
328        starvation_count: 0,
329        is_kernel: true,
330        user_entry: 0,
331        user_stack_ptr: 0,
332        kernel_stack: Vec::new(),
333        time_slice: 10,
334        need_resched: false,
335    };
336
337    // ロードバランサ: 最もプロセス数が少ないコアのRunqueueを探す
338    let mut best_core = 0;
339    let mut min_procs = usize::MAX;
340
341    // ロックを1つずつ順番にとって確認 (同時ロックは避ける)
342    for i in 0..4 {
343        let rq_opt = RUNQUEUES[i].lock();
344        if let Some(rq) = rq_opt.as_ref() {
345            let count = rq.processes.len();
346            if count < min_procs {
347                min_procs = count;
348                best_core = i;
349            }
350        }
351    }
352
353    // 選ばれたコアのキューにタスクを追加
354    let mut rq_lock = RUNQUEUES[best_core].lock();
355    if let Some(rq) = rq_lock.as_mut() {
356        rq.processes.push(new_proc);
357        crate::debug!(
358            "[SCHED] Spawned process '{}' (PID: {}, Priority: {:?}) onto Core {}",
359            name,
360            pid,
361            priority,
362            best_core
363        );
364    }
365
366    pid
367}
368
369/// 特定のコアをターゲットにしてカーネルプロセス (カーネルスレッド) を生成します。
370///
371/// # 引数
372/// * `entry` - プロセスのエントリポイント
373/// * `priority` - 優先度
374/// * `name` - プロセス名
375/// * `target_core` - 生成先のCPUコアのインデックス
376///
377/// # 戻り値
378/// 生成されたプロセスの PID。OOMなどのメモリ不足により起動できなかった場合は `0` を返します。
379pub fn spawn_on_core(
380    entry: fn(),
381    priority: Priority,
382    name: &'static str,
383    target_core: usize,
384) -> usize {
385    let pid = NEXT_PID.fetch_add(1, Ordering::SeqCst);
386
387    let stack_size = 1024 * 1024;
388
389    // 空きヒープ容量をチェックし、OOMによるパニックを防ぐ
390    let (used, total) = crate::kernel::allocator::get_heap_stats();
391    let free = total.saturating_sub(used);
392    if free < stack_size + 16 * 1024 {
393        crate::println!("[scheduler] WARNING: Insufficient heap memory to spawn process '{}' (Free: {} KB, Need: {} KB)", name, free / 1024, stack_size / 1024);
394        return 0;
395    }
396
397    let stack_mem = alloc::vec![0u8; stack_size];
398
399    let stack_top = stack_mem.as_ptr() as usize + stack_size;
400    let aligned_top = stack_top & !0xF;
401    let initial_sp = aligned_top - 240;
402
403    let sp_ptr = initial_sp as *mut usize;
404    unsafe {
405        for j in 0..10 {
406            sp_ptr.add(j).write_volatile(0);
407        }
408        sp_ptr.add(10).write_volatile(0);
409        sp_ptr.add(11).write_volatile(entry as usize);
410    }
411
412    let pt_addr = crate::kernel::mmu::create_process_page_table();
413
414    let new_proc = Process {
415        id: pid,
416        name,
417        state: ProcessState::Ready,
418        priority,
419        stack_ptr: initial_sp,
420        stack_mem,
421        wait_ticks: 0,
422        page_table_phys_addr: pt_addr,
423        starvation_count: 0,
424        is_kernel: true,
425        user_entry: 0,
426        user_stack_ptr: 0,
427        kernel_stack: Vec::new(),
428        time_slice: 10,
429        need_resched: false,
430    };
431
432    let core = target_core.min(3);
433    let mut rq_lock = RUNQUEUES[core].lock();
434    if let Some(rq) = rq_lock.as_mut() {
435        rq.processes.push(new_proc);
436        crate::debug!(
437            "[SCHED] Spawned process '{}' (PID: {}, Priority: {:?}) onto Core {}",
438            name,
439            pid,
440            priority,
441            core
442        );
443    }
444
445    pid
446}
447
448/// コンテキストスイッチで最初に起動するトランポリン関数。
449/// レジスタ `x19` からエントリポイント、`x20` から引数を受け取り、対象の関数を実行します。
450/// 実行が終了したスレッドは、`exit()` を呼び出して自身を終了させます。
451extern "C" fn trampoline() {
452    let entry_ptr: usize;
453    let arg: usize;
454    unsafe {
455        core::arch::asm!(
456            "mov {}, x19",
457            "mov {}, x20",
458            out(reg) entry_ptr,
459            out(reg) arg,
460        );
461        let entry: fn(usize) = core::mem::transmute(entry_ptr);
462        entry(arg);
463    }
464    exit();
465}
466
467/// 引数 `usize` を1つ取るカーネルプロセス (カーネルスレッド) を生成し、
468/// ロードバランシングに基づいてプロセス数が最も少ないコアのランキューに登録します。
469///
470/// # 引数
471/// * `entry` - 引数を1つ取る関数のポインタ
472/// * `arg` - 関数に渡される引数
473/// * `priority` - 優先度
474/// * `name` - プロセス名
475///
476/// # 戻り値
477/// 生成されたプロセスの PID。OOMなどのメモリ不足により起動できなかった場合は `0` を返します。
478pub fn spawn_with_arg(
479    entry: fn(usize),
480    arg: usize,
481    priority: Priority,
482    name: &'static str,
483) -> usize {
484    let pid = NEXT_PID.fetch_add(1, Ordering::SeqCst);
485
486    let stack_size = 1024 * 1024;
487
488    // 空きヒープ容量をチェックし、OOMによるパニックを防ぐ
489    let (used, total) = crate::kernel::allocator::get_heap_stats();
490    let free = total.saturating_sub(used);
491    if free < stack_size + 16 * 1024 {
492        crate::println!("[scheduler] WARNING: Insufficient heap memory to spawn process '{}' (Free: {} KB, Need: {} KB)", name, free / 1024, stack_size / 1024);
493        return 0;
494    }
495
496    let stack_mem = alloc::vec![0u8; stack_size];
497
498    let stack_top = stack_mem.as_ptr() as usize + stack_size;
499    let aligned_top = stack_top & !0xF;
500    let initial_sp = aligned_top - 240; // 240バイトフレームに対応
501
502    let sp_ptr = initial_sp as *mut usize;
503    unsafe {
504        // x19: entry_ptr, x20: arg
505        sp_ptr.add(0).write_volatile(entry as usize); // x19
506        sp_ptr.add(1).write_volatile(arg); // x20
507
508        for j in 2..10 {
509            sp_ptr.add(j).write_volatile(0);
510        }
511        sp_ptr.add(10).write_volatile(0); // lr (x30) -> (switch_context内では使われないがアラインメントのため)
512        sp_ptr
513            .add(11)
514            .write_volatile(trampoline as *const () as usize); // pc (x30)
515    }
516
517    let pt_addr = crate::kernel::mmu::create_process_page_table();
518
519    let new_proc = Process {
520        id: pid,
521        name,
522        state: ProcessState::Ready,
523        priority,
524        stack_ptr: initial_sp,
525        stack_mem,
526        wait_ticks: 0,
527        page_table_phys_addr: pt_addr,
528        starvation_count: 0,
529        is_kernel: true,
530        user_entry: 0,
531        user_stack_ptr: 0,
532        kernel_stack: Vec::new(),
533        time_slice: 10,
534        need_resched: false,
535    };
536
537    let mut best_core = 0;
538    let mut min_procs = usize::MAX;
539    for i in 0..4 {
540        let rq_opt = RUNQUEUES[i].lock();
541        if let Some(rq) = rq_opt.as_ref() {
542            let count = rq.processes.len();
543            if count < min_procs {
544                min_procs = count;
545                best_core = i;
546            }
547        }
548    }
549
550    let mut rq_lock = RUNQUEUES[best_core].lock();
551    if let Some(rq) = rq_lock.as_mut() {
552        rq.processes.push(new_proc);
553        crate::debug!(
554            "[SCHED] Spawned process '{}' with arg (PID: {}, Core {})",
555            name,
556            pid,
557            best_core
558        );
559    }
560
561    pid
562}
563
564/// コアと引数 `usize` を指定してカーネルプロセス (カーネルスレッド) を生成し、
565/// 対象コアのランキューに登録します。
566pub fn spawn_with_arg_on_core(
567    entry: fn(usize),
568    arg: usize,
569    priority: Priority,
570    name: &'static str,
571    target_core: usize,
572) -> usize {
573    let pid = NEXT_PID.fetch_add(1, Ordering::SeqCst);
574
575    let stack_size = 1024 * 1024;
576
577    // 空きヒープ容量をチェックし、OOMによるパニックを防ぐ
578    let (used, total) = crate::kernel::allocator::get_heap_stats();
579    let free = total.saturating_sub(used);
580    if free < stack_size + 16 * 1024 {
581        crate::println!("[scheduler] WARNING: Insufficient heap memory to spawn process '{}' (Free: {} KB, Need: {} KB)", name, free / 1024, stack_size / 1024);
582        return 0;
583    }
584
585    let stack_mem = alloc::vec![0u8; stack_size];
586
587    let stack_top = stack_mem.as_ptr() as usize + stack_size;
588    let aligned_top = stack_top & !0xF;
589    let initial_sp = aligned_top - 240; // 240バイトフレームに対応
590
591    let sp_ptr = initial_sp as *mut usize;
592    unsafe {
593        // x19: entry_ptr, x20: arg
594        sp_ptr.add(0).write_volatile(entry as usize); // x19
595        sp_ptr.add(1).write_volatile(arg); // x20
596
597        for j in 2..10 {
598            sp_ptr.add(j).write_volatile(0);
599        }
600        sp_ptr.add(10).write_volatile(0); // lr (x30)
601        sp_ptr
602            .add(11)
603            .write_volatile(trampoline as *const () as usize); // pc (x30)
604    }
605
606    let pt_addr = crate::kernel::mmu::create_process_page_table();
607
608    let new_proc = Process {
609        id: pid,
610        name,
611        state: ProcessState::Ready,
612        priority,
613        stack_ptr: initial_sp,
614        stack_mem,
615        wait_ticks: 0,
616        page_table_phys_addr: pt_addr,
617        starvation_count: 0,
618        is_kernel: true,
619        user_entry: 0,
620        user_stack_ptr: 0,
621        kernel_stack: Vec::new(),
622        time_slice: 10,
623        need_resched: false,
624    };
625
626    let core = target_core.min(3);
627    let mut rq_lock = RUNQUEUES[core].lock();
628    if let Some(rq) = rq_lock.as_mut() {
629        rq.processes.push(new_proc);
630        crate::debug!(
631            "[SCHED] Spawned process '{}' with arg (PID: {}, Core {})",
632            name,
633            pid,
634            core
635        );
636    }
637
638    pid
639}
640
641/// 指定した PID を持つプロセスの TTBR0 ページテーブル物理アドレスを取得します。
642///
643/// # 引数
644/// * `pid` - 対象プロセスの ID
645///
646/// # 戻り値
647/// プロセスのページテーブル物理アドレス。プロセスが見つからない場合は `None` を返します。
648pub fn get_process_page_table(pid: usize) -> Option<u64> {
649    for i in 0..4 {
650        let rq_opt = RUNQUEUES[i].lock();
651        if let Some(rq) = rq_opt.as_ref() {
652            for p in &rq.processes {
653                if p.id == pid {
654                    return Some(p.page_table_phys_addr);
655                }
656            }
657        }
658    }
659    None
660}
661
662/// 現在の CPU コアで実行されているプロセスの TTBR0 ページテーブル物理アドレスを取得します。
663///
664/// # 戻り値
665/// 現在プロセスのページテーブル物理アドレス。プロセスが存在しない場合は `None` を返します。
666pub fn get_current_page_table() -> Option<u64> {
667    let cid = core_id();
668    let rq_opt = RUNQUEUES[cid].lock();
669    if let Some(rq) = rq_opt.as_ref() {
670        if let Some(idx) = rq.current_idx {
671            return Some(rq.processes[idx].page_table_phys_addr);
672        }
673    }
674    None
675}
676
677/// 定期的に呼び出され（タイマー割り込みなど）、待機状態 (Waiting) にあるプロセスのチック数を更新し、
678/// 必要に応じて `schedule()` を実行してコンテキストスイッチを行います。
679pub fn tick() {
680    let cid = core_id();
681    {
682        let mut rq_opt = RUNQUEUES[cid].lock();
683        if let Some(rq) = rq_opt.as_mut() {
684            for p in &mut rq.processes {
685                if p.state == ProcessState::Waiting {
686                    if p.wait_ticks > 0 {
687                        p.wait_ticks -= 1;
688                    }
689                    if p.wait_ticks == 0 {
690                        p.state = ProcessState::Ready;
691                    }
692                }
693            }
694        }
695    }
696    schedule();
697}
698
699/// 待機状態 (Waiting) にある全プロセスの待ち時間チック数をデクリメントします。
700/// チック数が0になったプロセスは実行可能状態 (Ready) に戻ります。
701pub fn decrement_wait_ticks() {
702    let cid = core_id();
703    let mut rq_opt = RUNQUEUES[cid].lock();
704    if let Some(rq) = rq_opt.as_mut() {
705        for p in &mut rq.processes {
706            if p.state == ProcessState::Waiting {
707                if p.wait_ticks > 0 {
708                    p.wait_ticks -= 1;
709                }
710                if p.wait_ticks == 0 {
711                    p.state = ProcessState::Ready;
712                }
713            }
714        }
715    }
716}
717
718/// 指定した期間（タイマーチック数）だけ、呼び出し元のプロセスを待機状態 (Waiting) に移行させます。
719///
720/// # 引数
721/// * `ticks` - 待機させるチック数。0 の場合は即時に戻ります。
722pub fn sleep(ticks: usize) {
723    if ticks == 0 {
724        return;
725    }
726    crate::kernel::interrupt::disable_interrupts();
727
728    let cid = core_id();
729    {
730        let mut rq_opt = RUNQUEUES[cid].lock();
731        if let Some(rq) = rq_opt.as_mut() {
732            if let Some(idx) = rq.current_idx {
733                let curr = &mut rq.processes[idx];
734                curr.state = ProcessState::Waiting;
735                curr.wait_ticks = ticks;
736            }
737        }
738    }
739
740    yield_now();
741    crate::kernel::interrupt::enable_interrupts();
742}
743
744/// 呼び出し元のプロセスを一時的に実行可能状態 (Ready) に戻し、即座に再スケジュールを実行して
745/// CPUを他のプロセスに譲ります（コオペラティブ・マルチタスク）。
746pub fn yield_now() {
747    crate::kernel::interrupt::disable_interrupts();
748    schedule();
749    crate::kernel::interrupt::enable_interrupts();
750}
751
752/// スケジューリングのコア処理。
753/// 飢餓防止（starvation_count）を考慮した、優先度ベースのプリエンプティブ・ラウンドロビンアルゴリズムを適用し、
754/// 最もスコアの高い Ready 状態のプロセスを選択してコンテキストスイッチを行います。
755pub(crate) fn schedule() {
756    let cid = core_id();
757    // 別プロセスへ切替済みで、もうそのスタック上に居ない墓場プロセスをここで解放する。
758    reap_zombies(cid);
759    let mut rq_opt = RUNQUEUES[cid].lock();
760    let Some(rq) = rq_opt.as_mut() else {
761        return;
762    };
763    if rq.processes.is_empty() {
764        return;
765    }
766
767    let old_idx = rq.current_idx;
768
769    if let Some(idx) = old_idx {
770        if rq.processes[idx].state == ProcessState::Running {
771            rq.processes[idx].state = ProcessState::Ready;
772        }
773    }
774
775    let mut best_idx = None;
776    let mut best_score = 0;
777
778    let num_proc = rq.processes.len();
779    let start_idx = old_idx.unwrap_or(0);
780
781    /*
782    if num_proc >= 3 {
783        crate::println!("--- SCHEDULER DEBUG (Core {}) ---", cid);
784        for p in &rq.processes {
785            crate::println!("  Proc '{}' (PID {}), State: {:?}, Pri: {:?}, Starve: {}, PT: 0x{:x}, Score: {}",
786                p.name, p.id, p.state, p.priority, p.starvation_count, p.page_table_phys_addr,
787                (p.priority as usize * 10) + p.starvation_count);
788        }
789    }
790    */
791
792    for i in 1..=num_proc {
793        let idx = (start_idx + i) % num_proc;
794        let p = &mut rq.processes[idx];
795        if p.state == ProcessState::Ready {
796            // 基本優先度 (Low=0, Normal=10, High=20) に待機回数を加算
797            let score = (p.priority as usize * 10).saturating_add(p.starvation_count);
798            if best_idx.is_none() || score > best_score {
799                best_idx = Some(idx);
800                best_score = score;
801            }
802            // Readyのプロセスは一律でstarvation_countをインクリメント（飽和加算で安全化）
803            p.starvation_count = p.starvation_count.saturating_add(1);
804        }
805    }
806
807    if let Some(new_idx) = best_idx {
808        rq.processes[new_idx].starvation_count = 0; // 選ばれたらリセット
809        rq.processes[new_idx].state = ProcessState::Running;
810        rq.processes[new_idx].time_slice = 10;      // タイムスライスを10チックに補充
811        rq.processes[new_idx].need_resched = false; // 再スケジュール要求をクリア
812        rq.current_idx = Some(new_idx);
813
814        let new_pt = rq.processes[new_idx].page_table_phys_addr;
815
816        if let Some(o_idx) = old_idx {
817            if o_idx != new_idx {
818                let old_sp_ptr = &mut rq.processes[o_idx].stack_ptr as *mut usize;
819                let new_sp = rq.processes[new_idx].stack_ptr;
820                drop(rq_opt);
821
822                unsafe {
823                    let cur_pt: u64;
824                    core::arch::asm!("mrs {}, ttbr0_el1", out(reg) cur_pt);
825                    if cur_pt != new_pt {
826                        core::arch::asm!(
827                            "msr ttbr0_el1, {}",
828                            "isb",
829                            "tlbi vmalle1is",
830                            "dsb sy",
831                            "isb",
832                            in(reg) new_pt
833                        );
834                    }
835                    switch_context(old_sp_ptr, new_sp);
836                }
837            }
838        } else {
839            // Core 1-3 first switch
840            let mut dummy_sp: usize = 0;
841            let new_sp = rq.processes[new_idx].stack_ptr;
842            drop(rq_opt);
843            unsafe {
844                let cur_pt: u64;
845                core::arch::asm!("mrs {}, ttbr0_el1", out(reg) cur_pt);
846                if cur_pt != new_pt {
847                    core::arch::asm!(
848                        "msr ttbr0_el1, {}",
849                        "isb",
850                        "tlbi vmalle1is",
851                        "dsb sy",
852                        "isb",
853                        in(reg) new_pt
854                    );
855                }
856                switch_context(&mut dummy_sp as *mut usize, new_sp);
857            }
858        }
859    } else {
860        if let Some(o_idx) = old_idx {
861            if rq.processes[o_idx].state == ProcessState::Ready {
862                rq.processes[o_idx].state = ProcessState::Running;
863                rq.processes[o_idx].time_slice = 10;      // 継続実行時もタイムスライスを補充
864                rq.processes[o_idx].need_resched = false;
865            } else {
866                rq.current_idx = None;
867            }
868        }
869    }
870}
871
872/// 呼び出し元のプロセスを終了させます。
873///
874/// 自身のプロセススタック上でドロップ処理を行うと、スタック領域自体が解放されて
875/// Use-After-Free などのパニックを引き起こすため、一旦 `ZOMBIES` にプロセスを退避し、
876/// 別のプロセスにコンテキストスイッチした後に `reap_zombies` を用いて遅延解放させます。
877pub fn exit() -> ! {
878    crate::kernel::interrupt::disable_interrupts();
879    let cid = core_id();
880    {
881        let mut rq_opt = RUNQUEUES[cid].lock();
882        if let Some(rq) = rq_opt.as_mut() {
883            if let Some(idx) = rq.current_idx {
884                // remove() でその場ドロップすると、今実行中の自身のカーネルスタックを
885                // 解放してしまう (use-after-free)。墓場へ退避してドロップを遅延する。
886                let dead = rq.processes.remove(idx);
887                crate::info!(
888                    "[SCHED] Process '{}' (PID: {}) exited on core {}.",
889                    dead.name,
890                    dead.id,
891                    cid
892                );
893                ZOMBIES[cid].lock().push(dead);
894                rq.current_idx = None;
895            }
896        }
897    }
898
899    schedule();
900
901    loop {
902        unsafe {
903            core::arch::asm!("wfe");
904        }
905    }
906}
907
908/// ユーザー空間 (EL0) で動作する新しいユーザープロセスを生成し、
909/// ロードバランシングに基づいてプロセス数が最も少ないコアのランキューに登録します。
910///
911/// # 引数
912/// * `entry` - ユーザープロセスのエントリポイント関数
913/// * `priority` - スケジュール優先度
914/// * `name` - プロセスの識別名
915///
916/// # 戻り値
917/// 生成されたプロセスの PID
918pub fn spawn_user(entry: fn(), priority: Priority, name: &'static str) -> usize {
919    let pid = NEXT_PID.fetch_add(1, Ordering::SeqCst);
920
921    // ユーザースタック (EL0 で使用する SP_EL0)
922    let user_stack_size = 256 * 1024;
923    let user_stack_mem = alloc::vec![0u8; user_stack_size];
924    let user_stack_top = user_stack_mem.as_ptr() as usize + user_stack_size;
925    let user_sp = user_stack_top & !0xF;
926
927    // カーネルスタック (EL0→EL1 トラップ時に使用する SP_EL1)
928    let kernel_stack_size = 64 * 1024;
929    let kernel_stack_mem = alloc::vec![0u8; kernel_stack_size];
930
931    // カーネルスレッドとしての初期スタック (user_trampoline を実行するためのもの)
932    // switch_context で user_trampoline に飛ぶ
933    let trampoline_stack_size = 32 * 1024;
934    let trampoline_stack_mem = alloc::vec![0u8; trampoline_stack_size];
935    let trampoline_stack_top = trampoline_stack_mem.as_ptr() as usize + trampoline_stack_size;
936    let aligned_top = trampoline_stack_top & !0xF;
937    let initial_sp = aligned_top - 240;
938
939    let sp_ptr = initial_sp as *mut usize;
940    unsafe {
941        // x19 = user_entry, x20 = user_sp, x21 = kernel_stack_top
942        let kernel_stack_top = kernel_stack_mem.as_ptr() as usize + kernel_stack_size;
943        sp_ptr.add(0).write_volatile(entry as usize); // x19: user_entry
944        sp_ptr.add(1).write_volatile(user_sp); // x20: user_sp
945        sp_ptr.add(2).write_volatile(kernel_stack_top & !0xF); // x21: kernel_stack_top
946        for j in 3..10 {
947            sp_ptr.add(j).write_volatile(0);
948        }
949        sp_ptr.add(10).write_volatile(0); // x29
950        sp_ptr
951            .add(11)
952            .write_volatile(user_trampoline as *const () as usize); // x30 (ret先)
953    }
954
955    let pt_addr = crate::kernel::mmu::create_user_page_table();
956
957    let new_proc = Process {
958        id: pid,
959        name,
960        state: ProcessState::Ready,
961        priority,
962        stack_ptr: initial_sp,
963        stack_mem: user_stack_mem, // ユーザースタックのメモリを保持
964        wait_ticks: 0,
965        page_table_phys_addr: pt_addr,
966        starvation_count: 0,
967        is_kernel: false,
968        user_entry: entry as usize,
969        user_stack_ptr: user_sp,
970        kernel_stack: kernel_stack_mem,
971        time_slice: 10,
972        need_resched: false,
973    };
974
975    // ロードバランサ
976    let mut best_core = 0;
977    let mut min_procs = usize::MAX;
978    for i in 0..4 {
979        let rq_opt = RUNQUEUES[i].lock();
980        if let Some(rq) = rq_opt.as_ref() {
981            let count = rq.processes.len();
982            if count < min_procs {
983                min_procs = count;
984                best_core = i;
985            }
986        }
987    }
988
989    let mut rq_lock = RUNQUEUES[best_core].lock();
990    if let Some(rq) = rq_lock.as_mut() {
991        rq.processes.push(new_proc);
992        crate::debug!(
993            "[SCHED] Spawned USER process '{}' (PID: {}, Priority: {:?}) onto Core {} [EL0]",
994            name,
995            pid,
996            priority,
997            best_core
998        );
999    }
1000
1001    // トランポリン用スタックメモリを解放されないようリーク (プロセス終了時に回収)
1002    core::mem::forget(trampoline_stack_mem);
1003
1004    pid
1005}
1006
1007/// ユーザープロセスのトランポリン関数。
1008/// `switch_context` から `ret` で呼ばれ、`SP_EL1` をカーネルスタックに、
1009/// `SP_EL0` をユーザースタックに設定した上で、`enter_userspace` を用いて EL0 に降下します。
1010extern "C" fn user_trampoline() {
1011    let user_entry: usize;
1012    let user_sp: usize;
1013    let kernel_sp: usize;
1014    unsafe {
1015        core::arch::asm!(
1016            "mov {}, x19",
1017            "mov {}, x20",
1018            "mov {}, x21",
1019            out(reg) user_entry,
1020            out(reg) user_sp,
1021            out(reg) kernel_sp,
1022        );
1023    }
1024
1025    crate::info!(
1026        "[SCHED] Entering EL0 (entry=0x{:x}, user_sp=0x{:x}, kernel_sp=0x{:x})",
1027        user_entry,
1028        user_sp,
1029        kernel_sp
1030    );
1031
1032    // 割り込みを有効化してから EL0 に降下
1033    crate::kernel::interrupt::enable_interrupts();
1034
1035    // enter_userspace は eret で EL0 に降下するので、ここには戻らない
1036    unsafe {
1037        enter_userspace(user_entry, user_sp, kernel_sp);
1038    }
1039
1040    // ここには到達しないはずだが、万一のためのフォールバック
1041    crate::error!("[SCHED] ERROR - returned from enter_userspace!");
1042    exit();
1043}
1044
1045/// 指定したコアをターゲットにして、ユーザー空間 (EL0) で動作するユーザープロセスを生成します。
1046///
1047/// # 引数
1048/// * `entry` - ユーザープロセスのエントリポイント関数
1049/// * `priority` - スケジュール優先度
1050/// * `name` - プロセスの識別名
1051/// * `target_core` - ターゲットとなる CPU コアのインデックス
1052///
1053/// # 戻り値
1054/// 生成されたプロセスの PID
1055pub fn spawn_user_on_core(
1056    entry: fn(),
1057    priority: Priority,
1058    name: &'static str,
1059    target_core: usize,
1060) -> usize {
1061    let pid = NEXT_PID.fetch_add(1, Ordering::SeqCst);
1062
1063    // ユーザースタック (EL0 で使用する SP_EL0)
1064    let user_stack_size = 256 * 1024;
1065    let user_stack_mem = alloc::vec![0u8; user_stack_size];
1066    let user_stack_top = user_stack_mem.as_ptr() as usize + user_stack_size;
1067    let user_sp = user_stack_top & !0xF;
1068
1069    // カーネルスタック (EL0→EL1 トラップ時に使用する SP_EL1)
1070    let kernel_stack_size = 64 * 1024;
1071    let kernel_stack_mem = alloc::vec![0u8; kernel_stack_size];
1072
1073    // カーネルスレッドとしての初期スタック (user_trampoline を実行するためのもの)
1074    let trampoline_stack_size = 32 * 1024;
1075    let trampoline_stack_mem = alloc::vec![0u8; trampoline_stack_size];
1076    let trampoline_stack_top = trampoline_stack_mem.as_ptr() as usize + trampoline_stack_size;
1077    let aligned_top = trampoline_stack_top & !0xF;
1078    let initial_sp = aligned_top - 240;
1079
1080    let sp_ptr = initial_sp as *mut usize;
1081    unsafe {
1082        let kernel_stack_top = kernel_stack_mem.as_ptr() as usize + kernel_stack_size;
1083        sp_ptr.add(0).write_volatile(entry as usize); // x19: user_entry
1084        sp_ptr.add(1).write_volatile(user_sp); // x20: user_sp
1085        sp_ptr.add(2).write_volatile(kernel_stack_top & !0xF); // x21: kernel_stack_top
1086        for j in 3..10 {
1087            sp_ptr.add(j).write_volatile(0);
1088        }
1089        sp_ptr.add(10).write_volatile(0); // x29
1090        sp_ptr
1091            .add(11)
1092            .write_volatile(user_trampoline as *const () as usize); // x30 (ret先)
1093    }
1094
1095    let pt_addr = crate::kernel::mmu::create_user_page_table();
1096
1097    let new_proc = Process {
1098        id: pid,
1099        name,
1100        state: ProcessState::Ready,
1101        priority,
1102        stack_ptr: initial_sp,
1103        stack_mem: user_stack_mem,
1104        wait_ticks: 0,
1105        page_table_phys_addr: pt_addr,
1106        starvation_count: 0,
1107        is_kernel: false,
1108        user_entry: entry as usize,
1109        user_stack_ptr: user_sp,
1110        kernel_stack: kernel_stack_mem,
1111        time_slice: 10,
1112        need_resched: false,
1113    };
1114
1115    let core = target_core.min(3);
1116    let mut rq_lock = RUNQUEUES[core].lock();
1117    if let Some(rq) = rq_lock.as_mut() {
1118        rq.processes.push(new_proc);
1119        crate::debug!(
1120            "[SCHED] Spawned USER process '{}' (PID: {}, Priority: {:?}) onto Core {} [EL0]",
1121            name,
1122            pid,
1123            priority,
1124            core
1125        );
1126    }
1127
1128    // トランポリン用スタックメモリをリーク
1129    core::mem::forget(trampoline_stack_mem);
1130
1131    pid
1132}
1133
1134/// アイドルプロセス (`idle_core`) を特定のコアに登録し、そのコアの初期プロセスとします。
1135pub fn register_idle_process(core_id: usize) {
1136    let current_ttbr0: u64;
1137    unsafe {
1138        core::arch::asm!("mrs {}, ttbr0_el1", out(reg) current_ttbr0);
1139    }
1140
1141    let mut rq_lock = RUNQUEUES[core_id].lock();
1142    if let Some(rq) = rq_lock.as_mut() {
1143        rq.processes.push(Process {
1144            id: 0,
1145            name: "idle_core",
1146            state: ProcessState::Running,
1147            priority: Priority::Low,
1148            stack_ptr: 0,
1149            stack_mem: Vec::new(),
1150            wait_ticks: 0,
1151            page_table_phys_addr: current_ttbr0,
1152            starvation_count: 0,
1153            is_kernel: true,
1154            user_entry: 0,
1155            user_stack_ptr: 0,
1156            kernel_stack: Vec::new(),
1157            time_slice: 10,
1158            need_resched: false,
1159        });
1160        rq.current_idx = Some(0);
1161    }
1162}
1163
1164/// パニックハンドラ等から、現在のプロセスが主要なシステムプロセス（PID 0 または gui_shell など）であるかどうかを判定します。
1165/// デッドロックを防ぐため、try_lock を使用します。
1166pub fn is_current_process_critical() -> bool {
1167    let cid = core_id();
1168    if let Some(rq_lock) = RUNQUEUES[cid].try_lock() {
1169        if let Some(rq) = rq_lock.as_ref() {
1170            if let Some(idx) = rq.current_idx {
1171                if idx < rq.processes.len() {
1172                    let p = &rq.processes[idx];
1173                    // PID 0 (kernel_main / idle), もしくは gui_shell (シェル) をクリティカルとみなす
1174                    return p.id == 0 || p.name == "gui_shell" || p.name == "idle_core";
1175                }
1176            }
1177        }
1178    }
1179    // ロックが取得できなかった場合は、主要プロセスがランキュー操作中等だったと推測されるため、
1180    // 安全側に倒してクリティカル（OS全体を停止）と判断する
1181    true
1182}
1183
1184/// 現在実行中のプロセスの名前を取得します。
1185/// try_lock が失敗した場合は None を返します。
1186pub fn get_current_process_name() -> Option<&'static str> {
1187    let cid = core_id();
1188    if let Some(rq_lock) = RUNQUEUES[cid].try_lock() {
1189        if let Some(rq) = rq_lock.as_ref() {
1190            if let Some(idx) = rq.current_idx {
1191                if idx < rq.processes.len() {
1192                    return Some(rq.processes[idx].name);
1193                }
1194            }
1195        }
1196    }
1197    None
1198}
1199
1200/// 現在実行中のプロセスのPIDを取得します。
1201/// try_lock が失敗した場合は None を返します。
1202pub fn get_current_process_id() -> Option<usize> {
1203    let cid = core_id();
1204    if let Some(rq_lock) = RUNQUEUES[cid].try_lock() {
1205        if let Some(rq) = rq_lock.as_ref() {
1206            if let Some(idx) = rq.current_idx {
1207                if idx < rq.processes.len() {
1208                    return Some(rq.processes[idx].id);
1209                }
1210            }
1211        }
1212    }
1213    None
1214}
atmos/kernel/scheduler.rs

atmos/kernel/
scheduler.rs
