Chapter 4 Locking

四資工三甲 B10415013 張耿豪

(一) 背景與原理

xv6 執行於多處理器上。因處理器們共用實體記憶體並使用裡面的資料結構，可能會造成一顆處理器要讀資料時，另一顆正在更新資料的狀況，不論是在單核或多核上執行都可能發生。因此，xv6建立了Lock機制來防止處理器之間相互干擾。

Lock保證了同一時間只有一顆CPU能持有Lock，且持有Lock的CPU才能存取資料，確保資料結構。

以下說明為何需要Lock:

















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;
}

以上程式碼在單獨執行下是沒有問題的。但若兩個CPU同時執行insert，如上圖所示，會形成兩個list next node；而在執行第16行時，CPU1會把CPU2回傳的list結果給覆蓋過，CPU2執行後的資料因而流失。此狀況稱為Race Condition。

最常見的解決方法就是使用Lock。以下為簡單範例。














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);
}

在acquire與release之間的指令稱為critical section，而listlock保障了list的資料結構。

(二) 流程圖

xv6有兩種locks: slpin-locks和sleep-locks。

(三) 代碼解釋

Spin-locks

spinlock.h(資料結構):









struct spinlock {
uint locked; // 是否lock，locked =0為否，1為是。

// For debugging:
char *name; // lock的命名.
struct cpu *cpu; // 哪個CPU持有Lock.
uint pcs[10]; // 呼叫stack
//
};










struct cpu {
    uchar apicid; // 本地的APIC ID
    struct context *scheduler; // swtch() 進入scheduler
    struct taskstate ts; // 由x86去找interrupt的stack
    struct segdesc gdt[NSEGS]; // x86 全域 descriptor table
    volatile uint started; // 紀錄CPU是否開始運作
    int ncli; // pushcli 套疊的深度.
    int intena; // 在pushcli之前interrupts是否啟用?
    struct proc *proc; // 在CPU上執行的process或沒有
};







struct context {
    uint edi;
    uint esi;
    uint ebx;
    uint ebp;
    uint eip;
};


















enum procstate { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE }; //宣告porcess state狀態

//
struct proc {
    uint sz; // process memory 的大小(bytes)
    pde_t* pgdir; // Page table
    char *kstack; // 指向process kernel stack的bottom
    enum procstate state; // Process state
    int pid; // Process ID
    struct proc *parent; // 父process
    struct trapframe *tf; // Trap frame for 當前systemcall
    struct context *context; // swtch()執行 process
    void *chan; // 非0, sleeping on chan
    int killed; // 非0, 表示已被清除
    struct file *ofile[NOFILE]; // 開啟檔案
    struct inode *cwd; // 當前目錄
    char name[16]; // Process 名稱 (debugging)
};

spinlock.c:








#include "types.h" //所需資料庫
#include "defs.h"
#include "param.h"
#include "x86.h"
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "spinlock.h"







void acquire(struct spinlock*); //function宣告
void getcallerpcs(void*, uint*);
int holding(struct spinlock*);
void initlock(struct spinlock*, char*);
void release(struct spinlock*);
void pushcli(void);
void popcli(void);

initlock:







void
initlock(struct spinlock *lk, char *name) //lock初始化
{
    lk−>name = name;
    lk−>locked = 0;
    lk−>cpu = 0;
}

acquire:
























// Acquire the lock.
// loop直到取得lock。
// 會使其他CPU等待
//
void
acquire(struct spinlock *lk)
{
     pushcli(); // 關掉中斷功能以避免鎖死
     if(holding(lk))
         panic("acquire");
    
     // 判斷lock是否被其他CPU持有，1表示需等待，0則表示沒有可以獲取的lock
     while(xchg(&lk−>locked, 1) != 0)
     ;
    
     // 告訴compiler和processor不要存取，以確保在取得lock之後才做記憶體參考
     // 
     // 
     __sync_synchronize();
    
     // 紀錄lock狀態for debugging
     lk−>cpu = mycpu(); //紀錄CPU
     getcallerpcs(&lk, lk−>pcs);
}

release:























void
release(struct spinlock *lk)
{
    if(!holding(lk)) //若CPU沒有lock
         panic("release"); //回傳訊息
    
    lk−>pcs[0] = 0; //若CPU有lock，初始化
    lk−>cpu = 0;
    
    // 告訴compiler和processor不要存取，以確保在取得lock之後才做記憶體參考
    // 
    // 
    // 
    // 
    __sync_synchronize();

    // 雖然release動作為lk->loacked=0，但在OS裡操作方法不同
    // 以組合語言方式
    // 
    asm volatile("movl $0, %0" : "+m" (lk−>locked) : );
    
    popcli();
}

getcallerpcs:

















// 紀錄目前在pcs[]的call stack。
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]; // 儲存 %eip
        ebp = (uint*)ebp[0]; // 儲存 %ebp
    }
    for(; i < 10; i++)
        pcs[i] = 0;
}

holding:






// 檢查這個CPU是否有這個lock。
int
holding(struct spinlock *lock)
{
    return lock−>locked && lock−>cpu == mycpu();
}

pushcli:











void
pushcli(void) //關閉中斷功能
{
    int eflags;

    eflags = readeflags(); //取得flags
    cli();
    if(mycpu()−>ncli == 0) //若為0，改變中斷功能的狀態
        mycpu()−>intena = eflags & FL_IF; 
    mycpu()−>ncli += 1;
}

popcli:










void
popcli(void) //判斷回傳訊息及開啟中斷功能
{
    if(readeflags()&FL_IF)
        panic("popcli − interruptible");
    if(−−mycpu()−>ncli < 0)
        panic("popcli");
    if(mycpu()−>ncli == 0 && mycpu()−>intena)
        sti();
}

Sleep-locks

sleeplock.h(資料結構):








struct sleeplock {
uint locked; // 是否lock，locked=0為否，1為是。
struct spinlock lk; // spinlock 保護sleep lock

// For debugging:
char *name; // lock名字.
int pid; // 哪個Process 持有lock
};

sleeplock.c:









#include "types.h" //所需資料庫
#include "defs.h"
#include "param.h"
#include "x86.h"
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "spinlock.h"
#include "sleeplock.h"




void acquiresleep(struct sleeplock*); //function宣告
void releasesleep(struct sleeplock*);
int holdingsleep(struct sleeplock*);
void initsleeplock(struct sleeplock*, char*);

initsleeplock:








void
initsleeplock(struct sleeplock *lk, char *name) //sleeplock初始化
{
    initlock(&lk−>lk, "sleep lock"); //lock初始化
    lk−>name = name;
    lk−>locked = 0;
    lk−>pid = 0;
}

acquiresleep:











void
acquiresleep(struct sleeplock *lk)
{
    acquire(&lk−>lk); //取得lock
    while (lk−>locked) { //若locked = 1
        sleep(lk, &lk−>lk); //睡眠
    }
    lk−>locked = 1; //若locked = 0，設為1
    lk−>pid = myproc()−>pid; //紀錄process
    release(&lk−>lk); //釋放lock
}

releasesleep:









void
releasesleep(struct sleeplock *lk)
{
    acquire(&lk−>lk); //取得lock
    lk−>locked = 0; //初始化lock
    lk−>pid = 0;
    wakeup(lk); //喚醒
    release(&lk−>lk); //釋放lock
}

holdingsleep:










int
holdingsleep(struct sleeplock *lk) 
{
    int r;

    acquire(&lk−>lk); //取得lock
    r = lk−>locked; //紀錄locked狀態
    release(&lk−>lk); //釋放lock
    return r; //回傳紀錄的值
}

sleep:





































// 喚醒時重新獲取lock.
void
sleep(void *chan, struct spinlock *lk)
{
    struct proc *p = myproc(); // 宣告型態為proc的指標p
    
    if(p == 0) // 若p為0，回傳sleep訊息
        panic("sleep");
    
    if(lk == 0) // 若lk為0，回傳訊息
        panic("sleep without lk");
    
    // 需持有ptable.lock來改變p->state及呼叫sched
    // 
    // 
    // 
    // 
    // 
    if(lk != &ptable.lock){
        acquire(&ptable.lock); // 取得ptable.lock
        release(lk); //釋放lk
    }
    // 睡眠
    p−>chan = chan;
    p−>state = SLEEPING;
    
    sched();
    
    // 還原
    p−>chan = 0
    
    // 重新取得原本的lock
    if(lk != &ptable.lock){
        release(&ptable.lock); // 釋放ptable.lock
        acquire(lk); // 取得原本lock
    }
}

wakeup:








//喚醒所有程序
void
wakeup(void *chan)
{
    acquire(&ptable.lock);
    wakeup1(chan);
    release(&ptable.lock);
}

wakeup1:











// 喚醒所有程序
// 需持有ptable lock
static void
wakeup1(void *chan)
{
    struct proc *p; //宣告型態為proc的指標p
    
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
        if(p−>state == SLEEPING && p−>chan == chan)
            p−>state = RUNNABLE;
}

Chapter 4 Locking

四資工三甲 B10415013 張耿豪

(一) 背景與原理

(二) 流程圖

(三) 代碼解釋

Spin-locks

spinlock.h(資料結構):

spinlock.c:

initlock:

acquire:

release:

getcallerpcs:

holding:

pushcli:

popcli:

Sleep-locks

sleeplock.h(資料結構):

sleeplock.c:

initsleeplock:

acquiresleep:

releasesleep:

holdingsleep:

sleep:

wakeup:

wakeup1: