有时，多个线程对公共资源的同时访问会出现问题。想解决竞争条件，必须将临界区内的代码看作是一个整体来实行。
举一个生活中的小例子：
想象现在你现在和其他很多人共用同一个澡堂，你现在想美美地洗个五个时辰的澡然后睡觉。但是每过一个时辰，就会有管理人员叫你：“那谁，差不多了吧，该换个人洗了”。
怎么办？你想了想，解决这个问题有两种方法。
方法一：把管理人员囚禁起来。假装没听到，该干嘛干嘛。
方法二：命令其他等着洗澡的人把自己噶了，这样就没人跟你抢了。换一个人还是你。

仔细思索一下，方法一有点不道德了。明明你只是想霸占澡堂而已，你却要把管理人员监禁起来，这样其他需要管理人员的地方不就没法正常工作了么。这太自私了，不行。
相比之下，方法二就好得多。只有妄图打扰你洗澡的相关人员没了。其他的人，比如说吃饭的、搬砖的人的正常生活没有被打扰。
大不了洗完了之后，让那些死掉的人打场复活赛，把赢的人复活重新加入等洗澡队列里，其他人继续原地在地府等待就行了。

好了，例子就此结束。借助上面的例子可以发明一个出一个信号量的东西。

struct semaphore {
    uint_8 value;
    struct list wait_list;
};

信号量是一个概念层面的东西：
它是一个自然数。获取它使它减一，释放它使它加一
当它等于0的时候（即无可用信号时），此时再获取会堵塞；

void sema_down(struct semaphore* sema)
{
    enum intr_status old_status = intr_disable();
    struct task_struct* cur = (struct task_struct*)running_thread();
    while (sema->value == 0){
        // 检查问题
        if (elem_find(&sema->wait_list,&cur->wait_tag)) {
            PANIC("adding repeatedly to semaphore wait list");
        }
        // 向wait_list添加元素并阻塞
        list_append(&sema->wait_list,&cur->wait_tag);
        thread_block(TASK_BLOCKED);
    }
    sema->value--;
    intr_set_status(old_status);
}

所谓堵塞，其实就是把自己给从就绪队列中摘下来。这样CPU就没有机会宠幸到它。运行时本来就不再就绪队列中，所以到时候只要改变状态，换下个线程来执行 就行。

void thread_block(enum task_status stat)
{
    enum intr_status old_status = intr_disable();
    struct task_struct* cur = (struct task_struct*)running_thread();
    cur->status = stat;
    schedule();
    intr_set_status(old_status);
}

当信号量从无到有的时候，会唤醒那些沉睡的线程。而唤醒，就是把堵塞的线程重新加入就绪队列。
所以信号量需要一个数据结构来记录那些正处于堵塞状态的线程们 (wait_list)。在sema_down时记录因信号量堵塞的线程，在sema_up时移除。

void sema_up(struct semaphore* sema)
{
    enum intr_status old_status = intr_disable();
    if (!list_empty(&sema->wait_list))
    {
        struct list_elm* b_tag = list_pop(&sema->wait_list);
        struct task_struct* b_pcb = \
        mem2entry(struct task_struct,b_tag,wait_tag);
        thread_unblock(b_pcb);
    }
    sema->value++;
    intr_set_status(old_status);
}

锁的实质就是一个封装的二元信号量。
额外还有锁的持有者和重复申请次数，避免在已经加锁的情况下再次加锁造成死锁的情况。

struct lock {
    struct task_struct* holder;
    struct semaphore sema;
    uint_32 acquire_nr;
};

void lock_acquire(struct lock* lk)
{
    if (lk->holder != running_thread()) {
        sema_down(&lk->sema);
        lk->holder = running_thread();
        lk->acquire_nr = 1;
    } else {
        lk->acquire_nr++;
    }
}

void lock_release(struct lock* lk)
{
    ASSERT(lk->acquire_nr != 0);
    if (lk->holder != running_thread()){
        PANIC("can't release the block that doesn't belong to you");
    }
    if (lk->acquire_nr == 1) {
        lk->acquire_nr = 0;
        lk->holder = NULL;  //得放在sema_up前面
        sema_up(&lk->sema);
    } else {
        lk->acquire_nr--;
    }
}

编写键盘驱动

按下时产生通码，放开时产生断码。一般来说，断码=通码+0x80。
一个键盘在按着控制键和不按控制键下存在不同的行为。这里定义一些全局变量指代这些控制键的状态。

static Bool ctrl_l_status,ctrl_r_status,ctrl_status;
static Bool shift_l_status,shift_r_status,shift_status;
static Bool alt_l_status,alt_r_status,alt_status;
static Bool ext_status,caps_lock_status;

左Ctrl和右Ctrl只要由一个按着，那么 ctrl_status 就是true，其他那几个控制键也是如此。更新的时候等于左Ctrl的状态与右Ctrl的状态相或。

static void code_swistat(uint_16 code,uint_8 val)
{
    if      (code == ctrl_l_make)  ctrl_l_status  = val;
    else if (code == ctrl_r_make)  ctrl_r_status  = val;
    else if (code == shift_l_make) shift_l_status = val;
    else if (code == shift_r_make) shift_r_status = val;
    else if (code == alt_l_make)   alt_l_status   = val;
    else if (code == alt_r_make)   alt_r_status   = val;
}

static void updatestat(void)
{
    ctrl_status  = ctrl_l_status | ctrl_r_status;
    shift_status = shift_l_status | shift_r_status;
    alt_l_status = alt_l_status | alt_r_status;
}

同样一个按键打印出不同的字符，肉眼可见的例子是按下shift后字符键的大小写变化，以及上方数字键的变化。这一类的变化是受shift和CapsLk两个键共同影响的。
我们可以定义一个二元数组，记录按键所代表的符号。

static char keymap[][2]= {
    {0,0},
    {esc,esc},
    .......省略.......
    {' ',' '},
    {caps_lock_char,caps_lock_char},
};

再为其额外定义一个变量，它的值由shift和CapsLK两个键所影响。

    Bool shift = 0;
.........省略...........
        if (IS_DOUBLECHAR(scancode)) {
            shift = shift_status;            
        } else {
            shift = shift_status ^ caps_lock_status;
        }
.........省略...........

最终的代码：

static void intr_keyboard_handler(void)
{
    uint_16 scancode;
    scancode = inb(KDB_BUF_PORT);
    if (scancode == 0xe0){
        ext_status = 1;
        return ;
    }
    if (ext_status == 1)
    {
        scancode = (0xe0<<8 | scancode);
        ext_status = 0;
    }

    Bool shift = 0;
    Bool breakcode = scancode&0x80;
    if (breakcode)
    {
        uint_8 makecode = scancode & 0xff7f;
        code_swistat(makecode,0);
        updatestat();
        return ;
    }
    else if ((scancode>0 && scancode<0x3b) || \
             (scancode == ctrl_r_make)     || \
             (scancode == alt_r_make)) 
    {
        if (IS_DOUBLECHAR(scancode)) {
            shift = shift_status;            
        } else {
            shift = shift_status ^ caps_lock_status;
        }

        // 输出可输出字符后返回
        uint_8 index = scancode;
        char cur_char = keymap[index][shift];
        if (cur_char) {
            if (!ioq_full(&kbd_buf)){
                put_char(cur_char);
                ioq_putchar(&kbd_buf,cur_char);
            }
            return ;
        }

        // 如果是控制字符就相应地改变状态
        code_swistat(scancode,1);
        updatestat();
        if (scancode == caps_make)
            caps_lock_status = !caps_lock_status;
    }
    else
    {
        put_str("unknown char\n");
    }
}

环形缓冲区

顾名思义，一个tail走着走着走回来了的缓冲区。

struct ioqueue {
    char buf[BUFSIZE];
    struct task_struct* producer;
    struct task_struct* consumer;
    struct lock lock;
    uint_32 head;
    uint_32 tail;
};
// 这个next_pos是“环形”的核心
static uint_32 next_pos(uint_32 pos) {
    return (pos+1)%BUFSIZE;
}

头尾指针相等的时候为空。尾的下一个是头时为满。因此实际存储的空间比总空间少1。

Bool ioq_empty(struct ioqueue* ioq) {
    return (ioq->head == ioq->tail);
}
Bool ioq_full(struct ioqueue* ioq) {
    return (next_pos(ioq->tail) == ioq->head);
}

当缓冲区空的时候，让 consumer 进行等待。需要记录下consumer是哪位以便下次唤醒。

char ioq_getchar(struct ioqueue* ioq)
{
    ASSERT(get_intr_status() == INTR_OFF);
    while (ioq_empty(ioq)){
        lock_acquire(&ioq->lock);
        ioq_wait(&ioq->consumer);
        lock_release(&ioq->lock);
    }
    
    char ret_char = ioq->buf[ioq->tail];
    ioq->tail = next_pos(ioq->tail);
    if (ioq->producer) {
        wakeup(&ioq->producer);
    }
    return ret_char;
}

static void ioq_wait(struct task_struct** waiter)
{
    ASSERT(waiter!=NULL);
    *waiter = running_thread();
    thread_block(TASK_BLOCKED);
}

即使目前是关了中断的状态，ioq_wait()前面的lock_acquire()和lock_release()应该也是需要的。
因为ioq_wait()的时候，会调用thread_block()，这时会手动地更换到下一个线程。就拿消费者举例好了，假设有一个在因为ioq_empty()等待，这时它的下一位继任者若也刚好是一位饥肠辘辘的消费者，那么它就会覆盖ioq->consumer。
但如果上了锁的话，下一个消费者走到ioq_empty()的时候就会在lock_acuire()的地方阻塞住。
ioq_putchar 与 ioq_getchar 道理类似

void ioq_putchar(struct ioqueue* ioq,char val)
{
    ASSERT(get_intr_status() == INTR_OFF);
    while (ioq_full(ioq)){
        lock_acquire(&ioq->lock);
        ioq_wait(&ioq->producer);
        lock_release(&ioq->lock);
    }

    ioq->buf[ioq->head] = val;
    ioq->head = next_pos(ioq->head);
    if (ioq->consumer) {
        wakeup(&ioq->consumer);
    }
}