# XV6 A simple, Unix-like Teaching Operating System Chapter 4

---

> [TOC]

---

## Chapter 4 Locking

---

### Race conditions
- 以一個例子說明鎖的用意：

  struct list{
    int data;
    struct list *next;
    };

    struct list *list = 0;

    void
    insert(int data)
    {
        struct list *l;
        l = malloc(sizeof *l);
        l->data = data;
        l->next = list;
        list = l;
    }


    struct list *list = 0;
    struct lock listlock;

    void
    insert(int data)
    {
        struct list *l;
           acquire(&listlock);
        l = malloc(sizeof *l);
        l->data = data;
        l->next = list;
        list = l;
           release(&listlock);
    }

### Code: Locks
### - Structure

// Mutual exclusion lock.
    struct spinlock {
    uint locked;        // Is the lock held?

    // For debugging:
    char *name;         // Name of lock.
    struct cpu *cpu;    // The cpu holding the lock.
    uint pcs[10];       // The call stack (an array of program counters)
                        // that locked the lock.
};

### - acquire()

// Acquire the lock.
// Loops (spins) until the lock is acquired.
// Holding a lock for a long time may cause
// other CPUs to waste time spinning to acquire it.
void
acquire(struct spinlock *lk)
{
    pushcli(); // disable interrupts to avoid deadlock.
    if(holding(lk))
        panic("acquire");

    // The xchg is atomic.
    // It also serializes, so that reads after acquire are not
    // reordered before it. 
    while(xchg(&lk->locked, 1) != 0)
    ;

    // Record info about lock acquisition for debugging.
    lk->cpu = cpu;
    getcallerpcs(&lk, lk->pcs);
}

:::warning
xchg，一個 automic 指令，交換了內存中的一個 ward 和一個寄存器的值。如果 xchg 返回0，這時循環可以停止了。
:::

### - pushcli() / popcli()

// Pushcli/popcli are like cli/sti except that they are matched:
// it takes two popcli to undo two pushcli.  Also, if interrupts
// are off, then pushcli, popcli leaves them off.

void
pushcli(void)
{
    int eflags;

    eflags = readeflags();
    cli();
    if(cpu->ncli++ == 0)
    cpu->intena = eflags & FL_IF;
}

void
popcli(void)
{
    if(readeflags()&FL_IF)
    panic("popcli - interruptible");
    if(--cpu->ncli < 0)
    panic("popcli");
    if(cpu->ncli == 0 && cpu->intena)
    sti();
}

### - holding()

// Check whether this cpu is holding the lock.
int
holding(struct spinlock *lock)
{
    return lock->locked && lock->cpu == cpu;
}

### - getcallerpcs()

// Record the current call stack in pcs[] by following the %ebp chain.
void
getcallerpcs(void *v, uint pcs[])
{
    uint *ebp;
    int i;

    ebp = (uint*)v - 2;
    for(i = 0; i < 10; i++){
        if(ebp == 0 || ebp < (uint*)KERNBASE || ebp == (uint*)0xffffffff)
            break;
        pcs[i] = ebp[1];     // saved %eip
        ebp = (uint*)ebp[0]; // saved %ebp
    }
    for(; i < 10; i++)
        pcs[i] = 0;
}

---

### Code: Using locks
- 由於 Lock 會使別人不能進行操作，所以數量不能太多。
- 使用 Lcok 的難點在於使用時機
1. 當一個CPU 正在寫一個變量，而同時另一個 CPU 可能 R/W 該變量時，需要用鎖防止兩個操作重疊。
2. 當用鎖保護不變量時，如果不變量涉及到多個數據結構，通常每個數據結構都需要用一個單獨的鎖保護起來，這樣才能維持不變量。

---

### Deadlock and lock ordering
- 如果一段代碼要使用多個鎖，那麼必須要注意代碼每次運行都要以相同的順序獲得鎖，否則就有死鎖的危險。
- Deadlock
- 死鎖是指兩個或兩個以上的進程在執行過程中，由於競爭資源或者由於彼此通信而造成的一種阻塞的現象，若無外力作用，它們都將無法推進下去。此時稱系統處於死鎖狀態或系統產生了死鎖，這些永遠在互相等待的進程稱為死鎖進程。

---

### Interrupt handlers

- 在程式碼中已呼叫一個鎖，在中斷中又呼叫。
- 假設 iderw 持有 idelock ，然後中斷發生，開始運行 ideintr。ideintr會試圖獲得 idelock，但卻發現 idelock 已經被獲得了，於是就等著它被釋放。
- xv6 解決方法
- acquire在嘗試獲得鎖之前調用了 pushcli，release 則在釋放鎖後調用了 popcli。pushcli 和 popcli 不僅包裝了cli 和 sti，它們還做了計數工作，這樣就需要調用兩次 popcli 來抵消兩次 pushcli；這樣，如果代碼中獲得了兩個鎖，那麼只有當兩個鎖都被釋放後中斷才會被允許。

---

### Instruction and memory ordering
略。

---

### Limitations of spin-locks
- 當 function 以及其內部呼叫的 function 都需要同一個鎖時，他們不需確定他們的關係，例如呼叫我的人是不是已經拿這個鎖了。

---