# Process Synchronization(同步)
## Background
* 並發訪問共享數據可能會導致數據不一致
* 維護數據一致性需要機制來保證協作process的有序執行

## Consumer & Producer 問題
* 判斷緩衝區是空還是滿
* 以前：使用 in、out 位置
* 現在：使用 counter


* counter + + 用機器語言實現

    move ax, counter
    add ax, 1
    move counter, ax

* counter - - 用機器語言實現

    move bx, counter
    sub bx, 1
    move counter, bx

## Instruction Interleaving


* 這樣的穿插情形counter可能4、5、6，但實際上要是5

* 在這個示例中，由於Consumer和Producer共享了一個變數counter，且沒有 synchronized 機制，可能會導致**race condition**，進而產生錯誤的結果。

* 要解決這個問題，需要使用 synchronized 機制來確保Consumer和Producer對共享變數的存取是安全的，避免Race Condition和未預期的行為。

**Race Condition**：Consumer和Producer同時訪問 counter 變數，導致不正確的計數。在 producer 還沒有更新 counter 之前，consumer 就可能已經讀取了不正確的計數值。這會導致資源共享的不一致性。

## Race Condition

Race Condition：multi-thread 或 multi-process 環境中常見的一種情況，當兩個或多個thread（或process）同時訪問共享資源，且至少有一個thread（或process）在修改資源的情況下，可能導致不可預測的結果。

Race Condition 可能導致程式的行為不符合預期，甚至可能引發錯誤或不穩定的情況。

共享數據的最終值取決於哪個process最後完成

* 為了防止Race Condition，並發process必須 synchronized
* 在單 processor 機器上，我們可以禁用 interrupt 或使用non-preemptive CPU scheduling
* 通常被描述為 **Critical-Section Problem**

## The Critical-Section Problem
* 目的：processes 合作的協議
* 問題描述：
* N個 processes 正在競爭使用一些共享數據
* 每個 process 都有一個代碼段，稱為critical section ，在其中訪問共享數據
* 確保當一個 process 在其critical section 執行時，不允許其他 processes 在其critical section 執行
* 一般常見 critical section 的架構如下


`entry section`： process 開始執行，進入這個區域。在進入 CS 之前， process 會在這個區域進行某些設置和準備工作。

`critical section`：process 在這個區域執行需要保護的操作，確保不會與其他 process 同時進入該區域，即需要互斥訪問的共享資源。

`exit section`： process 在執行完 CS 的操作後，進入這個區域。在離開 CS 之前， process 會進行某些清理和恢復工作。

`remainder section`： process 在離開 CS 後，進入這個區域。在這個區域 process 可以執行其他非關鍵操作，例如等待下一次進入 CS 的機會。

## Critical Section Requirements

**Critical Section(CS)**：是指在 multi-thread 或 multi-process 環境中，需要保護的一段程式碼區域，該區域訪問共享資源，且在同一時間只能有一個 thread （或 process）進入，以避免 Race Condition 和確保資源的正確訪問。

Critical Section 通常是對共享變數、資料結構或共享資源進行讀取、寫入、更新等操作的程式碼片段。

1. mutually exclusive：在某個時間點只能有一個process或thread訪問共享資源。

* 例如：如果process P 在其 CS 中執行，則其他 process 不能在其 CS 中執行

2. Progress：是指系統中的每個執行體都能夠在合理的時間內進展，而不會無限期地被阻塞。

* 例如：如果其 CS 中沒有process正在執行，並且存在一些希望enter其 CS 的process，則這些process不能無限期推遲

3. Bounded Waiting：是指在獲取共享資源時，執行體等待的次數是有限的。這是為了防止某個執行體無限期地被其他執行體擱置，從而保證所有執行體都有機會訪問共享資源。
* 例如：在process請求enter其 CS 後，其他process被允許 enter其 CS 的次數必須存在限制

### Algorithm for Two Processes

* 只有 2 個 process，P₀ 和 P₁
* 共享變數
* int turn； // initially turn = 0
* turn = i ⇒ P_i，可以enter其 Critical Section


對於P₀

while (1) {
    while (turn == 1);  // 等待 P1 的回合結束
    // 進入 P0 的CS
    // 執行CS的程式碼
    turn = 1;  // 將 turn 設為 1，讓 P1 進入CS
    // 離開CS
}

對於P₁

while (1) {
    while (turn == 0);  // 等待 P0 的回合結束
    // 進入 P1 的 CS
    // 執行 CS 的程式碼
    turn = 0;  // 將 turn 設為 0，讓 P0 進入 CS
    // 離開 CS
}

## Proof of Peterson's Solution
1. mutually exclusive：

如果 P₀，CS → `flag[1]== false || turn == 0`
如果 P₁，CS → `flag[0] == false || turn == 1`
* 假設兩個 processes 都在CS → `flag[0] == flag[1] == true`
→ turn == 0 為 P₀ enter，turn==1 為 P₁ enter
* 然而，“turn” 將為 0 或 1，因為它的值將為兩個 processes 設置，但只有一個值會持續
* 所以，P₀，P₁，不能同時在CS！


* 當其中一個 processor （例如 P0）進入 CS 時，另一個 processor （例如 P1）不能同時進入 CS 。

* 這樣可以確保在任何給定的時間，只有一個 processor 能夠在 CS 內執行，從而避免 Race Codition 和不一致性。

* 通過適當的 Synchronization ，可以實現這種 mutually exclusive，以確保資源的正確共享和操作。

接上圖

2. Progress （例如，P₀ wishes to enter its CS):

1. 如果 P₀ 未就緒flag[1] = false → P₀ 可以 enter
2. 如果兩者都就緒 flag[0] = flag[1] == true 如果 trun = 0 則 P₀ enter ，否則 P₁ enter
> 無論哪種情況，某些 waiting process 都可以 enter CS！

* 確保"Progress" 是設計和實現 Synchronizatio n時的重要目標之一。它確保了系統的公平性和正常運行，避免了一些可能導致系統無法進行下去的極端情況。

3. Bounded waiting (e.g., P₀ wishes to enter its CS):

1. 一旦 P₁ 退出CS → flag[1]==false → P₀ 可以 enter
2. 如果 P₁ 退出CS && 重置 flag[1]=true
→turn==0 （覆蓋 P₀ 設置）→ P₀ 可 enter
> P₀不會無限期地等待！

## Bakery Algorithm (n processes)

核心思想是，每個thread或 processor 都被賦予一個號碼（類似於取號的方式），並且在進入臨界區之前，它們必須等待號碼輪到自己。

當號碼比較小的thread或 processor 可以進入 CS 時，其他thread則必須等待。

* 在進入其CS 之前，每個 process 都會收到一個#
* 擁有最小#的人進入CS
* 編號方案始終以非降序生成#； 即 1,2,3,3,4,5,5,5
* 如果 process P 和 P, 收到相同的 #，如果 i < j，則首先為 P, 提供服務

符號：
> (a, b) < (c, d) 如果 a < c 或如果 a ==c && b < d


* 為什麼修改num時無法比較？
* Without locking...

1. 設5為當前最大數
2. 如果P1和P4一起取數，但P4先於P1完成
>P1=0； P4=6， P4將進入CS
3. P1取號後
> P1-P4-6 P1也將進入CS！！！

* With locking...
> P4必須等待P1取完號
>> P1和P4在比較之前都會有新的數字“6”

## Pthread Lock/Mutex Routines

Mutex 的主要目的是確保同一時間內只有一個 thread 能夠訪問被鎖住的區域（CS），從而避免race codition 和確保資源的一致性。

使用 Mutex 時需要謹慎，確保在合適的地方加鎖和解鎖，以避免 deadlock 和其他同步問題。

* 要使用mutex，必須將其聲明為 pthread_mutex_t 類型並使用 pthread_mutex_init() 進行初始化
* 使用 pthread_mutex_destory() 銷毀 mutex
* 然後可以使用 pthread_mutex_lock() 和 pthread_mutex_unlock() 保護臨界區


## Condition Variables (CV)

它們通常與 Mutex 一起使用，以實現更複雜的同步需求，例如等待特定條件的滿足或通知其他 thread 發生了某些事件。

* Condition Variables 代表一個條件，符合該條件時可以觸發 thread 執行某些動作
* 三種 CV 的操作
* wait() : 直到其他 thread 呼叫 signal()/broadcast()，thread 處於等待狀態
* signal() : 喚醒一個等待中的 thread
* broadcast() : 喚醒所有等待中的 thread
* 在 Pthread 中，CV type 為 `pthread_cond_t`
* 使用 `pthread_cond_init()` 來初始化
* `pthread_cond_wait (&theCV, &somelock)`
* `pthread_cond_signal (&theCV)`
* `pthread_cond_broadcast (&theCV)`


## ThreadPool Implementation

* ThreadPool 是一種 multi-thread 技術，用於管理和重複使用 thread ，以處理多個任務。它可以提高應用程式的效率和性能，並允許在一個固定的 thread 集合中執行多個任務，而不需要為每個任務都創建一個新的 thread 。


`void (*function)(void)`：這是一個指向函數的指針，表示要執行的任務。這個函數不接受任何參數，也不返回任何值。這種指針可用於存儲任意的函數，以供 ThreadPool 執行。
`void *argument`：這是一個指向 void 的指針，用於存儲傳遞給任務函數的參數。由於這是一個通用的指針，可以用於傳遞任何類型的數據。


`pthread_mutex_t lock`：一個 mutex ，用於保護 ThreadPool 的訪問，確保同一時間只有一個 thread 可以修改 ThreadPool 的狀態。

`pthread_cond_t notify`：一個 CV ，用於通知等待在 ThreadPool 上的 thread ，當有新任務加入或 ThreadPool 關閉時，可以使用這個 CV 進行通知。

`pthread_t threads`：一個 thread 陣列，用於存放 ThreadPool 中的 thread 。

`threadpool_task_t queue`：一個存放任務的陣列，用於存放提交給 ThreadPool 的任務。

`int thread_count`：表示 ThreadPool 中的 thread 數量。

`int queue_size`：表示任務 queue 的大小。

`int head` 和 `int tail`：分別表示任務 queue 的頭部和尾部索引，用於管理 queue 中的任務。

`int count`：表示當前任務 queue 中的任務數量。

`int shutdown`：標誌位，表示 ThreadPool 是否已關閉。

`int started`：標誌位，表示 ThreadPool 是否已啟動。


`static void *threadpool_thread(void *threadpool)`：這是一個 thread 函數，接受一個指向 ThreadPool 結構的指標 threadpool 作為參數。它的返回值是 `void *`，因為 thread 函數的返回值通常是 `void *`。

`threadpool_t *pool = (threadpool_t *)threadpool;`：將 threadpool 轉換為 threadpool_t 結構的指針，以便在 thread 函數中使用 ThreadPool 的成員。

`threadpool_task_t task;`：創建一個 threadpool_task_t 變數，用於存放要執行的任務。

進入無限循環 `for(;;)`，表示 thread 會一直執行。

`pthread_mutex_lock(&(pool->lock));`：鎖定 mutex ，以確保 thread 安全。

`while((pool->count == 0) && (pool->shutdown))`：在等待條件變數上等待，直到有任務可執行或 ThreadPool 被關閉。如果 queue 中沒有任務且 ThreadPool 被關閉，則等待。

從任務 queue 中取出一個任務，並將相關資訊複製到 `task` 變數。

更新 queue 的頭部索引，並減少 queue 中任務的數量。

`pthread_mutex_unlock(&(pool->lock));`：解鎖 mutex 。

執行任務的函數，並傳遞任務的參數。

## Atomic Test And Set
atomic：不能被interrupt。

Atomic Test And Set 是一個用於確保多個 thread 或多個 process 在並發情況下安全地執行操作的同步 atomic 操作。

它的主要目的是確保在進行某些操作時，只有一個 thread 或 process 能夠成功地設置一個共享的 boolean 變數，避免了 race condition。


* `TestAndSet` 函數的實現與之前的描述一致。它確保在同一時間只有一個 process 可以將 `lock` 設置為 `TRUE`，並返回之前的狀態。

* P0 和 P1 兩個 process 的主循環，都包含一個 while 循環，用來等待 `lock` 變為 `FALSE`，以確保其他 process 已經離開 CS 。這個循環稱為 busy-waiting ，因為它會持續檢查 `lock` 直到可以進入 CS 為止。

* 一旦 `TestAndSet(lock)` 返回 `FALSE`，表示 CS 目前未被其他 process 佔用，當前 process 可以進入 CS ，執行一些關鍵的操作。

* 在 CS 的操作完成後，將 `lock` 設置為 `FALSE`，表示 CS 已經釋放，其他 process 可以進入。

* `remainder section` 是在 CS 之外執行的一些其他操作。

* `while (1)`; 是一個無限循環，確保這兩個 process 持續地進行上述步驟。

雖然這段程式碼確保了 CS 的互斥同步，但它存在一個問題，

在這個程式碼中，每個 process 使用 busy-waiting 方式來等待 `lock` 變為 `FALSE`，以進入 CS 。這種方式可能導致一個 process 在等待時無法進入 CS ，而其他 process 持續地訪問 lock，導致無法 Bounded Waiting 。
## Atomic Swap
Atomic Swap 是一種同步 Atomic 操作，用於交換兩個變數的值，同時保證操作是 Atomic，不會被中斷。這種操作在多 thread 或多 process 環境中特別有用，可以確保交換的過程不會受到 race condition 的影響。


* 在 `do { ` 循環中，P0 process 首先將 `key0` 設置為 `TRUE`，表示它希望進入 CS 。然後，它進入一個 `while` 循環，只有在 `key0` 變為 `FALSE` 時才會退出，這就意味著只有在另一個 process 將 `key0` 設置為 `FALSE` 時，P0 才會繼續執行。

* 在 `Swap (lock, key0);` 操作中，`P0` 使用 Atomic Swap 交換 `lock` 和 `key0` 的值。這確保了操作的 Atomic，使得只有一個 process 可以成功進行 Swap 操作。

*　一旦 `key0` 變為 `FALSE`，表示 P0 可以進入 CS ，並執行關鍵的操作。

* 在關鍵區域完成後，P0 將 `lock` 設置為 `FALSE`，表示 CS 已經釋放。

* `while (1);` 是一個無限循環，確保 P0 持續地進行上述步驟。

* P1 process 的部分也是類似的，用來實現與 P0 相同的互斥同步機制。
## Semaphores
* Samaphores 是一個通用的同步處理工具，其紀錄某個資源有多少 units 可以去使用
* 若 # of record = 1 --> binary semaphore, mutex lock
* 若 # of record > 1 --> counting semaphore
* 利用兩個 atomic 函數 wait & signal 來存取


* wait(S)：當一個 process 或 thread 需要訪問共享資源時，它會執行 wait(S) 操作。如果信號量的值大於零，表示資源可用，該 process 可以繼續執行並減少信號量的值。如果信號量的值為零或負值，表示資源已經被佔用， process 需要等待。

* signal(S)：當一個 process 或 thread 完成對共享資源的訪問時，它會執行 signal(S) 操作，將信號量的值增加。這表示資源已經被釋放，其他 process 可以進行訪問。

## Non-busy waiting Implementation

* Semaphore 是一個有 queue 的結構體，包含 Semaphore 的值以及有哪些 Processes 等待被執行


`int value`：這是信號量的計數值。在初始化時，它被設置為 0。計數型信號量可以有正值、零值和負值，表示資源的可用性狀態。

`struct process *L`：這是一個指向 process （或 PCB，Process Control Block）隊列的指針。該隊列用於存儲等待中的 process ，即等待資源的 process 。當資源不可用時， process 將被加入到此隊列中。

* wait() 和 signal()
* 使用系統調用：block() 和wakeup()
* 必須以 atomically execute


**這種方式使用了「sleep 和 wakeup 」的機制。當資源不可用時， process 會進入睡眠狀態，等待資源的釋放。這樣可以避免浪費CPU資源，因為 process 只會在資源可用時被喚醒，而不會持續檢查。**

## Cooperation Synchronization
* P1執行S1； P2執行S2
* S2僅在S1完成後執行
* Implementation:
* shared var:
* semaphore sync; // initially sync = 0


常見的問題如下：

1. Bounded-Buffer (Producer-Consumer) Problem
2. Reader-Writers Problem
3. Dining-Philosopher Problem

## Reader-Writers Problem

問題的目標是確保對共享資源的訪問是安全和有效的，同時保證 reader 之間可以同時訪問，而 writer 之間和 reader 之間必須進行互斥。

* 標準在處理 I/O 會遇到的問題
* 一組共享數據對象
* 一組process
* reader process（讀取共享對象）
* writer process（更新共享對象）

* 涉及優先級的不同變化
* first RW problem : 除非 writer 正在更新共享對象，否則 reader 不會一直等待
* 只要確定 writer 有 access 的獨佔權即可，不關心 reader 要等多久，或要做什麼事情。可能造成 writer 一直被其他 reader 插隊，永遠無法獲取訪問的機會
* second RW problem : 一旦 writer 準備好，它就會在共享對像被釋放後立即執行更新
* 不只要確定 writer 的 access 權限，另外當 writer 在準備好且訪問時，writer 的優先性必須高於 reader ，不可有新的 reader 進來插隊
#### First Reader-Writer Algorithm

// mutual exclusion for write 
semaphore wrt=1
// mutual exclusion for readcount
semaphore mutex=1
int readcount=0;

// writer
Writer(){
    while(TRUE){
        wait(wrt); // 等待 writer 信號量，保證只有一個 writer 能夠訪問
        // Writer Code（ writer 的操作在這裡）
        signal(wrt); // 釋放 writer 信號量，允許其他 writer 訪問
    }
}

// reader
Reader(){
    while(TRUE){
        wait(mutex); // 等待互斥鎖，保證 reader 數量的操作是原子的
        readcount++;
        if(readcount == 1)
            wait(wrt); // 當第一個 reader 進入時，等待 writer 信號量，阻止 writer 訪問
        signal(mutex); // 釋放互斥鎖

        // Reader Code（ reader 的操作在這裡）

        wait(mutex); // 等待互斥鎖，保證 reader 數量的操作是原子的
        readcount--;
        if(readcount == 0)
            signal(wrt); // 當最後一個 reader 離開時，釋放 writer 信號量，允許 writer 訪問
        signal(mutex); // 釋放互斥鎖
    }
}

* writer 部分：
* 進入 writer 代碼區域前，等待 writer 信號量 wrt。
* 進入 writer 代碼區域，執行 writer 的操作。
* 完成 writer 操作後，釋放 writer 信號量 wrt，允許其他 writer 進入。
* reader 部分：
* 進入 reader 代碼區域前，等待互斥鎖 mutex。
* 增加 reader 數量（readcount）。
* 如果是第一個 reader 進入，則等待 writer 信號量 wrt，阻止 writer 訪問。
* 釋放互斥鎖 mutex，允許其他 reader 進入。
* 執行 reader 的操作（在 "Reader Code" 區域內）。
* 進入 reader 代碼區域前，再次等待互斥鎖 mutex。
* 減少 reader 數量。
* 如果是最後一個 reader 離開，則釋放 writer 信號量 wrt，允許 writer 訪問。
* 釋放互斥鎖 mutex。

* 透過信號量 wrt， writer 確保同一時間只有一個 writer 能夠進行寫操作，以避免 race condition 。
* 透過信號量 mutex，確保 reader 數量的操作是 atomic ，避免多個 reader 同時修改 readcount。
* 當第一個 reader 進入時，它會等待 wrt 信號量，從而阻止 writer 進行訪問，確保 reader - writer 優先策略。
* 當最後一個 reader 離開時，它會釋放 wrt 信號量，允許 writer 進行訪問，確保 writer 的訪問權限。

## Dining-Philosopher Problem

* 5 個人坐在 5 張椅子上，且有 5 根筷子
* 每個人只會思考或是吃飯
* 思考時與剩下 4 個人沒有互動
* 每個人要用餐需要兩根筷子
* 一個人 1 次只能拿 1 根筷子
* 吃完飯後，將兩根筷子都放下

* deadlock problem
> 一根筷子作為一根信號量
* starvation problem


## Monitor
是一種用於同步多線程或多 process 程序的高階同步機制。它提供了一種結構化的方式來組織共享資源的訪問，以避免 race condition、 deadlock 和其他同步問題。

動機：
* 雖然信號量提供了方便有效的同步機制，但其正確性取決於程序員

* 所有訪問共享數據對象的 process 必須以正確的順序和正確的位置執行 wait() 和 signal()
> 這可能不是真的，因為誠實的編程錯誤或不合作的程序員
>>"誠實的程式設計錯誤" 是指由於程式設計師無意中犯下的錯誤，而不是故意地惡意操作程式碼。


### Monitor --- 高級語言構造
* monitor type的表示包括
* declarations of variables，其值定義類型實例的狀態
* 實現類型操作的過程/函數
* monitor type 類似於OOP語言中的 class
* monitor 內的過程只能訪問局部變量和形式參數
* monitor 的局部變量只能由局部過程使用
* 但是，monitor 確保 monitor 內一次只能有一個 process 處於活動狀態
* 類似的想法被納入許多程序中。
* 語言：並發 pascal、C# 和 Java

### Monitor Condition Variables
* 為了允許 process 在 monitor 內等待，必須聲明一個條件變量，如下所示條件x，y；
* 條件變量只能與 wait() 和 signal() 操作一起使用
* x.wait(); 意味著調用此操作的 process 被掛起，直到另一個 process 調用
* x.signal(); 恰好恢復一個掛起的 process。如果沒有 process 被掛起，那麼signal操作沒有效果
（相反，signal 總是改變 semaphores 的狀態）

## Dining Philosophers Example

monitor dp {
    enum {thinking, hungry, eating} state[5]; // 當前狀態
    condition self[5]; // 如果不能獲取筷子，延遲吃飯
    void pickup(int i) // 拿起筷子
    void putdown(int i) // 放下筷子
    void test(int i) // 嘗試進食
    void init() {
        for (int i = 0; i < 5; i++)
            state[i] = thinking;
    }
}

void pickup(int i) {                
    state[i] = hungry;                  
    test(i); // 嘗試進食               
    if (state[i] != eating)                  
        // 等待進食                   
        self[i].wait();             
}            

void putdown(int i) {
    state[i] = thinking;
    // 檢查鄰座是否在等待進食
    test((i+4) % 5); 
    test((i+1) % 5);
}
// 嘗試讓 Pi 吃東西（如果它餓了）
void test(int i) {
    if ( (state[(i + 4) % 5] != eating) &&(state[(i + 1) % 5] != eating) 
        && (state[i] == hungry) ) {
    // 沒有鄰居在吃飯，Pi 餓了
        state[i] = eating;
        self[i].signal(); 
    // 如果 Pi waited，則恢復它
  　// 如果 Pi 沒有 waited，則沒有影響
    }
} 

這段程式碼是關於經典的「Dining-Philosopher Problem」的一種解法，使用了一個 monitor 來實現。

* enum {thinking, hungry, eating} state[5];：定義了一個 enum 來表示哲學家的三種狀態

* void pickup(int i)：這是當一位哲學家想要拿起筷子時呼叫的函數。

* state[i] = hungry：將該哲學家的狀態設置為饑餓。
* test(i)：調用 test 函數來嘗試進餐。
* if (state[i] != eating)：如果哲學家不能進餐（因為他的鄰座哲學家正在進餐），則進入等待狀態。
* self[i].wait();：通過等待 self[i] 的條件變數，暫停該哲學家的執行，直到被其他哲學家喚醒。
* void putdown(int i)：這是當一位哲學家放下筷子時呼叫的函數。

* state[i] = thinking：將該哲學家的狀態設置為思考。
* test((i+4) % 5); 和 test((i+1) % 5);：調用 test 函數來檢查左右鄰座的哲學家是否可以進餐，從而喚醒可能在等待的哲學家。
* void test(int i)：這個函數用於檢查一位哲學家是否可以進餐，如果可以，則讓他進餐。

* state[i] = eating;：將該哲學家的狀態設置為進食。
* test(int i)檢查相鄰的兩位哲學家是否都不在進食，並且該哲學家處於 "hungry" 狀態
* 如果滿足條件，將該哲學家的狀態設為 "eating"，並通過 self[i].signal() 喚醒等待的哲學家。

## Atomic Transactions
### System Model
* Transactions：執行單個邏輯功能的指令（或多個指令）的集合
* Atomic Transactions：操作作為單個邏輯工作單元發生，可以完全發生，也可以根本不發生
* Atomic Transactions 是數據庫系統特別關注的問題
* 對在 OS 中使用數據庫技術有濃厚的興趣

### File I/O 示例

* transaction 是一系列的 read and write操作
* 由 commit （transaction successful）或 abort （transaction failed）使操作終止
* Aborted transaction 必須 rolled back 以撤消其執行的任何更改
* 確保該屬性是系統責任的一部分

### Log-Based Recovery
* 記錄有關 transaction 所有修改的 stable storage 信息

* Stable storage：存儲數據永不丟失
* Write-ahead logging：每條日誌記錄描述transaction 寫入操作
* Transaction name
* Data item name
* Old & new values
* Special events: <T_i starts>, <T_i commits>
* Log 用來重建被改動資料的原始狀態
* 利用 undo(Ti) 及 redo(Ti) 來復原資料
### Checkpoints
* 發生故障時，必須查閱日誌以確定必須重新執行哪些事務

* 搜索過程非常耗時
* 並非所有交易都需要重做
* 使用 checkpoints 來減少上述開銷
* 將所有日誌記錄輸出到 stable storage
* 將所有修改數據輸出到 stable storage
* 輸出一條日誌記錄 < checkpoint >到 stable storage