---
# System prepended metadata

title: Chapter 07：Scheduler

---

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。
&emsp; 1. System Timer
&emsp; 2. Scheduler
&emsp; 3. Lock
&emsp; 4. printk
&emsp; 5. Assert
&emsp; 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>

![截圖 2025-10-30 晚上8.19.11](https://hackmd.io/_uploads/rkVydAxJWx.png)






# System Timer (8253)
>[!Note] Block Diagram
>Reference: [Intel 8253](https://en.wikipedia.org/wiki/Intel_8253)
![截圖 2025-10-23 上午8.32.08](https://hackmd.io/_uploads/rysiDewAex.png)

| 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
>![0](https://hackmd.io/_uploads/H1IZwePAlx.png)
>![1](https://hackmd.io/_uploads/HkefwgDRgx.png)
>![2](https://hackmd.io/_uploads/r1HfDlwCxx.png)
>![3](https://hackmd.io/_uploads/rycGPgDAxg.png)
>![4](https://hackmd.io/_uploads/SyyQDxDRlg.png)
>![5](https://hackmd.io/_uploads/HJXXPewRxg.png)
>![截圖 2025-10-23 上午8.50.03](https://hackmd.io/_uploads/Hyi0sxPRge.png)
> 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)
>![upload_aaec1849ec81af6e5fba02adce60c411](https://hackmd.io/_uploads/HymKUePCgl.png)
>For 0x43 Mode register:
>![upload_e348db18b7cdeaf4e97396fef0e2cf10](https://hackmd.io/_uploads/SkLALewRgl.png)
>![截圖 2025-10-23 上午8.56.54](https://hackmd.io/_uploads/rywu6lPAee.png)
🧩 詳細說明
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
![截圖 2025-10-28 凌晨1.20.20](https://hackmd.io/_uploads/SkXb5mpRgl.png)







# Scheduler
>[!Note] Process Control Block (PCB)
>![截圖 2025-10-31 凌晨3.40.29](https://hackmd.io/_uploads/ryWukrbkWx.png)
>Reference: [Linux task_struct](https://docs.huihoo.com/doxygen/linux/kernel/3.7/include_2linux_2sched_8h_source.html#l01190)

>[!Note] Calling Convention
>![截圖 2025-10-25 凌晨3.52.05](https://hackmd.io/_uploads/rkQbKItRge.png)
>![截圖 2025-10-25 凌晨3.52.51](https://hackmd.io/_uploads/SyQ4F8FRlg.png)
> > esp 我們會使用 `task_struct` 來保存。

>[!Note] 中斷時 EFLAGS 的變化
>![截圖 2025-10-27 下午4.18.54](https://hackmd.io/_uploads/HysZijh0gl.png)

>[!Note] 切換 PCB 時，Stack 的變化
>準備換上的 thread 只有這三種 stack 狀態：
>* Interrupt triggered: 之前因為中斷觸發而被換下的。
>* Initial State: 從未被執行過的。
>* Function call: 透過執行 `schedule()`而被換下的。
>![截圖 2025-10-31 凌晨3.44.36](https://hackmd.io/_uploads/SJSSgHbybx.png)

>[!Note] Interrupt status
>![截圖 2025-11-01 凌晨1.42.58](https://hackmd.io/_uploads/ryAHS_fkbe.png)

>[!Note] Thread 的 state diagram
>![截圖 2025-10-31 晚上10.34.02](https://hackmd.io/_uploads/ByjbtBMk-x.png)

>[!Note] Round-Robin Scheduling
>![截圖 2025-10-27 晚上11.31.29](https://hackmd.io/_uploads/BJ7txM6Aex.png)

>[!Note] Typedef Function pointer
>![截圖 2025-10-28 下午2.05.10](https://hackmd.io/_uploads/BysraRTAxe.png)

>[!Note] x86 CPU instruction: hlt
>![截圖 2025-10-28 下午4.16.44](https://hackmd.io/_uploads/r1VmngA0gg.png)

>[!Note] Thread should call kthread_exit
>![截圖 2025-10-28 下午6.23.15](https://hackmd.io/_uploads/rkUhtz00eg.png)

>[!Caution] 我們沒有處理直接 return 的 case。

## Source Code
https://github.com/srhuang/a-os/commit/cf4f1f6d2c2608e1210e96fa6f0b0f8ccdd06175

## Compile
```
make all
```

## Put on hard disk
```
sh gen.sh
```

## Checkpoint
![截圖 2025-10-31 凌晨4.23.14](https://hackmd.io/_uploads/BJDUtSZJZe.png)

General Protection Exception
![截圖 2025-10-31 凌晨4.22.13](https://hackmd.io/_uploads/BkqzYSZJbx.png)








# 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
>![截圖 2025-11-01 下午2.24.11](https://hackmd.io/_uploads/B1v3P7QyZx.png)
>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：忙等鎖被釋放
>![截圖 2025-10-29 下午5.04.31](https://hackmd.io/_uploads/H1v4KvJkZl.png)

>[!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
![截圖 2025-11-01 凌晨2.40.28](https://hackmd.io/_uploads/H1LpftfJ-l.png)

test Semaphore
![截圖 2025-11-01 凌晨2.41.51](https://hackmd.io/_uploads/BkoMXYfJWl.png)









# printk
>[!Note] Linux `printk()`
![截圖 2025-11-01 下午4.12.14](https://hackmd.io/_uploads/HyGW-SQJbl.png)

>[!Note] Variable Argument (VA)
>![截圖 2025-11-01 下午4.19.35](https://hackmd.io/_uploads/SkmCMSm1Wx.png)

## Source Code
https://github.com/srhuang/a-os/commit/4814469d10b66e8b3346f87653c7de68e6e34447

## Compile

```
make all
```

## Put on hard disk

```
sh gen.sh
```

## Checkpoint
![截圖 2025-11-01 下午4.47.12](https://hackmd.io/_uploads/Hk2mFrQybl.png)

test concurrency
![截圖 2025-11-01 下午4.46.00](https://hackmd.io/_uploads/SJYlKSXkWg.png)








# Assert
![截圖 2025-11-01 下午5.16.44](https://hackmd.io/_uploads/r1FGgU7kZx.png)

>[!Note] C Preprocessor get information
>![截圖 2025-11-01 下午5.35.49](https://hackmd.io/_uploads/r1Yi4ImJWe.png)


## Source Code
https://github.com/srhuang/a-os/commit/bd98de43d1115ef251c0a2389ecd913067da67d4

## Compile

```
make all
```

## Put on hard disk

```
sh gen.sh
```

## Checkpoint
![截圖 2025-11-01 下午5.14.42](https://hackmd.io/_uploads/BJ-syUXk-e.png)










# 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
![截圖 2025-11-01 下午5.51.19](https://hackmd.io/_uploads/r1pNd8QJ-e.png)

without lock protection
![截圖 2025-11-01 下午5.55.19](https://hackmd.io/_uploads/SyUmFUXyZe.png)

