Chapter 07：Scheduler
===
:::info
我們終於要來挑戰作業系統的大魔王了：scheduler。
Interrupt handler、system timer 都是為了排程器做準備，基本上作業系統是靠中斷觸發排程，因此困難的點在於，必須對於 x86 CPU 指令有深入的了解，有很多 CPU 指令背後隱含著對於 stack 的操作。
Race condition 是作業系統的最大難題之一，相對應的解法就是使用 lock。隨著 lock 的實作，我們終於可以完成最終版的 print log: ==printk==。最後，補上之前 memory management 的一塊拼圖：==lock==，避免共享資源 bitmap 在 concurrency 環境下造成 race condition。
  1. System Timer
  2. Scheduler
  3. Lock
  4. printk
  5. Assert
  6. Memory Management with Lock
:::
>[time=Tue, Oct 21, 2025 11:22 PM]
---
https://youtu.be/IA7ZcrEQSYo
<iframe width="560" height="315" src="https://www.youtube.com/embed/IA7ZcrEQSYo?si=Tl0sxBLke_KD4FjL" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
# System Timer (8253)
>[!Note] Block Diagram
>Reference: [Intel 8253](https://en.wikipedia.org/wiki/Intel_8253)
| Counter | 用途 | 輸出接線 | 頻率範例 | 現代狀況 |
| ------- | ----------------- | ------------------ | -------------- | ---------------------------- |
| 0 | 系統時鐘（System Tick） | IRQ0（8259A） | 18.2 Hz | ✅ 仍使用（早期），現被 HPET / LAPIC 取代 |
| 1 | DRAM Refresh | DMA 控制器 | 約 15 µs 週期 | ❌ 已淘汰 |
| 2 | PC Speaker 音調 | Port 61h / Speaker | 20 Hz – 20 kHz | ✅ 可選用 |
==我們這邊使用 counter 0 system timer。==
>[!Note] Operating Mode
>
>
>
>
>
>
>
> Software Trigger: Mode 0, 2, 3, 4
> Hardware Trigger: Mode 1, 5
==我們使用 Mode 2 來產生 system timer。==
>[!Note] Programming
>Reference: [OSDev wiki](https://wiki.osdev.org/Programmable_Interval_Timer)
>
>For 0x43 Mode register:
>
>
🧩 詳細說明
1️⃣ Latch Command（00）
這不是寫入模式，而是**讀取計數值**的一種方式。當 CPU 想知道目前計數器剩下多少時，可以先送出此命令，將當前值「鎖存」到一個暫存器中，再去讀取。不會中斷計數進行。
🧠 用途：在不中斷定時器運作的情況下讀出目前剩餘值。
2️⃣ LSB Only（01）
只寫入或讀取 16 位元計數值的低 8 位。適用於只需要 8-bit 精度的情況（較少見）。
3️⃣ MSB Only（10）
只寫入或讀取 高 8 位。通常也較少單獨使用，因為完整計數需要 16 位。
4️⃣ LSB then MSB（11）
最常用的方式。CPU 寫入時：先寫入低位元組，再寫入高位元組。CPU 讀取時：先讀低位元組，再讀高位元組。這樣可以支援完整的 16-bit 計數值（0~65535）。
🧠 用途：幾乎所有的實際應用（例如 Linux 設定 PIT）都使用這個模式。
## Source Code
https://github.com/srhuang/a-os/commit/1327f81af19e7a0c54f38373cf6f9fe2faa5ec5f
## Compile
```
make all
```
## Put on hard disk
```
sh gen.sh
```
## Checkpoint
# Scheduler
>[!Note] Process Control Block (PCB)
>
>Reference: [Linux task_struct](https://docs.huihoo.com/doxygen/linux/kernel/3.7/include_2linux_2sched_8h_source.html#l01190)
>[!Note] Calling Convention
>
>
> > esp 我們會使用 `task_struct` 來保存。
>[!Note] 中斷時 EFLAGS 的變化
>
>[!Note] 切換 PCB 時，Stack 的變化
>準備換上的 thread 只有這三種 stack 狀態：
>* Interrupt triggered: 之前因為中斷觸發而被換下的。
>* Initial State: 從未被執行過的。
>* Function call: 透過執行 `schedule()`而被換下的。
>
>[!Note] Interrupt status
>
>[!Note] Thread 的 state diagram
>
>[!Note] Round-Robin Scheduling
>
>[!Note] Typedef Function pointer
>
>[!Note] x86 CPU instruction: hlt
>
>[!Note] Thread should call kthread_exit
>
>[!Caution] 我們沒有處理直接 return 的 case。
## Source Code
https://github.com/srhuang/a-os/commit/cf4f1f6d2c2608e1210e96fa6f0b0f8ccdd06175
## Compile
```
make all
```
## Put on hard disk
```
sh gen.sh
```
## Checkpoint
General Protection Exception
# Lock
>[!Note] Race Condition 三要素
>* Shared Resource（共享資源）
>* Concurrency（並行性）
>* Uncontrolled Access（非同步化存取 / 缺乏互斥）
>[!Note] 解決 Race Condition 的方法需滿足三條件
>* Mutual Exclusion (互斥)
>* Progress（不可有 deadlock）
>* Bounded Waiting (有限的等待時間)
>[!Note] Deadlock 發生的四個必要條件
>* Mutual Exclusion（互斥條件）
>* Hold and Wait（占有且等待）
>* No Preemption（不可搶奪）
>* Circular Wait（循環等待）
>[!Note] Spinlock by using xchg
>
>Example in a spinlock:
>In a common use case for xchg in a spinlock, the instruction is used to test if a lock is available and acquire it if it is. You load a register with 1 (representing a locked state) and use xchg to swap it with the memory address of the lock.
>* If the memory location was 0 (unlocked), the xchg swaps the 0 into the register. Your code sees the 0, knows the lock was free, and the lock is now acquired. The loop ends.
>* If the memory location was already 1 (locked), the xchg swaps the 1 into the register. Your code sees the 1 and knows the lock was already in use, so it continues looping until the lock is released and can be acquired.
```c=
while (1) { // 外層 while
if (!xchg(&lock->slock, 1)) // 原子交換，嘗試取得鎖
break; // 成功拿到鎖，離開
while (lock->slock) // 內層 while
cpu_relax(); // 忙等，等待鎖釋放
}
```
>[!Note] spinlock 為何需要兩個 while loop
>1. 外層 while：無限嘗試搶鎖
>2. 內層 while：忙等鎖被釋放
>
>[!Note] 三個基本 Lock 的比較
| 行為 | Spinlock | Mutex | Semaphore |
| --------- | ----------- | --------- | --------- |
| 鎖住時行為 | 自旋忙等 | 睡眠等待 | 睡眠等待 |
| 中斷安全 | ✅ 可用於中斷上下文 | ❌ 不可 | ❌ 通常不可 |
| 使用 CPU 時間 | 高（忙等） | 低 | 低 |
| 臨界區長度 | 短 | 中～長 | 中～長 |
| 是否公平 | ❌ 不一定 | ✅ 通常公平 | ✅ 可設定 |
| 典型用途 | 驅動程式、短期共享變數 | 系統呼叫、檔案系統 | 緩衝區、資源池控制 |
## Source Code
https://github.com/srhuang/a-os/commit/1fc7e4c180cc4d59fd057c188262d5471f2d045a
>[!Warning] Bug Fix
>https://github.com/srhuang/a-os/commit/9b76b31ae3b73a704f4593090298aa38b947e873
## Compile
```
make all
```
## Put on hard disk
```
sh gen.sh
```
## Checkpoint
test Mutex
test Semaphore
# printk
>[!Note] Linux `printk()`
>[!Note] Variable Argument (VA)
>
## Source Code
https://github.com/srhuang/a-os/commit/4814469d10b66e8b3346f87653c7de68e6e34447
## Compile
```
make all
```
## Put on hard disk
```
sh gen.sh
```
## Checkpoint
test concurrency
# Assert
>[!Note] C Preprocessor get information
>
## Source Code
https://github.com/srhuang/a-os/commit/bd98de43d1115ef251c0a2389ecd913067da67d4
## Compile
```
make all
```
## Put on hard disk
```
sh gen.sh
```
## Checkpoint
# Memory mgmt. with Lock
* Physical address pool
* Virtual address pool
* Memory block descriptor
* Page table
## Source Code
https://github.com/srhuang/a-os/commit/7cc788b348055a0272938ec996fb41a5868c07e0
## Compile
```
make all
```
## Put on hard disk
```
sh gen.sh
```
## Checkpoint
without lock protection
Sign in with Wallet
Connect another wallet