作業系統 CH4 Locking

概要

CPU必須避免正在執行的程序與其他執行的程序互相干擾。舉例來說，在IDE磁碟中，磁碟的driver會將未完成的磁碟要求以Link-List的方式記錄，而同時也會有新的要求加入。

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

上為一般演算法Link-List插入連結的程式碼，但在多工處理的情況下，有可能會同時有兩個的程序同時呼叫到insert function。這樣當兩個程序同時執行為第8行後，兩個程序的l->next將會指向同一個list，而到第9行較晚執行的程序會直接將先執行程序的List覆蓋過去，而這樣的現象成為競爭條件(Race Condition)。因此我們將透過Lock產生互斥(mutual exclusion)，讓同一時間只會有一個CPU在執行insert function。

Locking

流程圖：

資料結構

struct spinlock {
uint locked; //判斷是否有被佔有(佔有:1，未佔有:0)

char *name; //lock名稱
struct cpu *cpu; //佔有lock的CPU
uint pcs[10]; // 調用呼叫程序的stack
};

code：

void acquire(struct spinlock *lk)
{
    pushcli(); // 禁止中斷的程序，避免deadlock
    if(holding(lk)) //判斷CPU是否已有lock
        panic("acquire");

    while(xchg(&lk−>locked, 1) != 0);//如果沒有CPU佔用則獲得lock，有的話則會在迴圈等待lock釋出

    __sync_synchronize();//避免程序被重新排序
    lk−>cpu = mycpu();//紀錄現在佔有lock的CPU
    getcallerpcs(&lk, lk−>pcs);//紀錄現在的call stack
}

void release(struct spinlock *lk)
{
    if(!holding(lk))//判斷CPU是否已release
        panic("release");

    lk−>pcs[0] = 0;//釋出lock
    lk−>cpu = 0;//紀錄初始化

    __sync_synchronize();//避免程序被重新排序
    asm volatile("movl $0, %0" : "+m" (lk−>locked) : );
    popcli();//關閉pushcli
}

Lock問題

當我們在程序中使用很多的lock，有可能會導致互鎖（deadlock）。舉例來說，假設程序A先後需要lock a & b，程序B先後需要lock b & a。這樣萬一同時間程序A獲得lock a，程序B獲得lock b，這樣程序A和程序B會佔有對方要的lock永遠要不到需要的lock。

除了上述的狀況外，Deadlock也很容易發生在一中斷處理的程序和另一個正在運行的程序卡在同一個function中的lock。因此在這裡使用了pushcli去禁止中斷的程序取得lock，並在release時在popcli解開限制。

然而在少部分的程序為了效率需要長時間的持有lock，而過程中可會有程序需要lock才能維持系統。此時可使用acquiresleep來解決這個問題，他將不會禁止中斷的程序取得lock。所以在設計時必須依照各不同的程序去選擇合適的acquire lock方法。

struct sleeplock {
    uint locked; //判斷是否有被佔有(佔有:1，未佔有:0)
    struct spinlock lk; //會被長時間持有的loc
    char *name; // lock的名稱
    int pid;
} 

void acquiresleep(struct sleeplock *lk)
{
    acquire(&lk−>lk);//將lock給予程序
    while (lk−>locked) {
        sleep(lk, &lk−>lk);
    }
    lk−>locked = 1;
    lk−>pid = myproc()−>pid;
    release(&lk−>lk);
}

void sleep(void *chan, struct spinlock *lk)
{
    struct proc *p = myproc();

    if(p == 0)//判斷是否已經sleep
        panic("sleep");
    if(lk == 0)//判斷是否為sleeplock
        panic("sleep without lk");
    //將lock給予新的程序
    if(lk != &ptable.lock){
        acquire(&ptable.lock);
        release(lk);
    }
    // sleep.
    p−>chan = chan;
    p−>state = SLEEPING;
    sched();
    p−>chan = 0;
 
    //將lock還給原本的程序
    if(lk != &ptable.lock){
        release(&ptable.lock);
        acquire(lk);
    }
}

除了deadlock的問題外，有時compiler會為了更好的效率會改變程序執行的順序，但在有lock的情況下必須要避免這樣的狀況(以防deadlock)，因此透過sync_synchronize避免程序被重新排序。

結論

lock能夠提供一個系統中類似於優先權份配的效果，但同時也因為其自身的性質而有所限制。在xv6中其實並沒有使用過度繁雜的lock，僅使用在些較為特定的地方（多為硬碟讀寫方面）。因此在使用lock的同時必須考量到其對於其他程序的影響程度以及是否能夠達到所想要的效率。