Ctrl+K

MIT 6.828 操作系统课程系列8 Locks#

#

多个cpu同时独立运行，分享物理内存，分享各种数据。
比如kalloc分配内存，比如cpu挑选可运行的进程，都是操作全局数据，如果不处理，数据完全混乱。

锁提供一个互斥的机制，确保同一时刻最多只有一个cpu拿着这把锁。下一个cpu必须等这个cpu释放才能拿到。
这样能确保资源不会同时被多个cpu操作。

锁的坏处是可能降低效率。

spinlock流程#

void
acquire(struct spinlock *lk) // does not work!
{
    for(;;) {
        if(lk->locked == 0) {
            lk->locked = 1;
            break;
        }
    }
}

这个是想当然的代码。不同cpu有可能同时跑到lk->locked == 0这个代码，造成同时获得锁。
必须要把lk->locked == 0判断和lk->locked = 1做成原子。

riscv提供了相应的指令amoswap r, a。见riscv-spec 8.4。
把地址a和寄存器r中的数据交换。保证其原子性，不会有其他cpu插足。

__sync_lock_test_and_set是gcc内置的函数，会最终走这个原子操作。

struct spinlock {
    uint locked;       // 是否使用中

    // For debugging:
    char *name;        
    struct cpu *cpu;   // 拿着锁的cpu
};

struct cpu {
    struct proc *proc;          // The process running on this cpu, or null.
    struct context context;     // swtch() here to enter scheduler().
    int noff;                   // Depth of push_off() nesting.
    int intena;                 // Were interrupts enabled before push_off()?
};


void
push_off(void)
{
    int old = intr_get();    // 中断是否打开

    intr_off();              // 关闭中断
    if(mycpu()->noff == 0)
        mycpu()->intena = old;  // 记录第一次的中断状态
    mycpu()->noff += 1;         // push次数++
}

void
pop_off(void)
{
    struct cpu *c = mycpu();
    if(intr_get())                             // 原则上中断不应该为开启状态
        panic("pop_off - interruptible");
    if(c->noff < 1)                            // 没配对
        panic("pop_off");
    c->noff -= 1;                              // 计数--
    if(c->noff == 0 && c->intena)              // 中断恢复到初始状态
        intr_on();
}


int
holding(struct spinlock *lk)
{
    int r;
    r = (lk->locked && lk->cpu == mycpu()); // 我是否已经拿着锁
    return r;
}


void
acquire(struct spinlock *lk)
{
    // 关中断
    push_off(); // disable interrupts to avoid deadlock.

    // 不允许重复acquire
    if(holding(lk))
        panic("acquire");

    // On RISC-V, sync_lock_test_and_set turns into an atomic swap:
    //   a5 = 1
    //   s1 = &lk->locked
    //   amoswap.w.aq a5, a5, (s1)

    // 原子操作。设置lk->locked为1。
    // 返回值为被交换前的lk->locked值。不停循环。
    // 如果老值是0，说明是我把0变成了1，是我得到了锁，往下走。
    // 如果老值是1，说明是别人抢先设置成了1，我没有获得锁，继续循环。
    // 谁把0变成1就获得锁
    while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;

    // Tell the C compiler and the processor to not move loads or stores
    // past this point, to ensure that the critical section's memory
    // references happen strictly after the lock is acquired.
    // On RISC-V, this emits a fence instruction.

    // 编译器和硬件可能会进行优化，重新安排内存操作指令的顺序。
    // 在这种极度敏感的节点，顺序的变化可能造成严重后果。
    // __sync_synchronize是memory barrier。确保其前后的指令不会被重新安排到barrier对面。
    // 即规定了一个边界。保证前边的指令一定在前边执行。后边的一定在后边执行。

    // https://en.wikipedia.org/wiki/Memory_barrier
    // https://stackoverflow.com/questions/286629/what-is-a-memory-fence
    // https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/Documentation/memory-barriers.txt?id=HEAD

    // riscv上使用fence相关指令实现
    
    __sync_synchronize();

    // Record info about lock acquisition for holding() and debugging.
    lk->cpu = mycpu();
}



void
release(struct spinlock *lk)
{
    // 如果不是我拿着锁就不允许解锁
    if(!holding(lk))
        panic("release");

    lk->cpu = 0;

    // Tell the C compiler and the CPU to not move loads or stores
    // past this point, to ensure that all the stores in the critical
    // section are visible to other CPUs before the lock is released,
    // and that loads in the critical section occur strictly before
    // the lock is released.
    // On RISC-V, this emits a fence instruction.
    __sync_synchronize();

    // Release the lock, equivalent to lk->locked = 0.
    // This code doesn't use a C assignment, since the C standard
    // implies that an assignment might be implemented with
    // multiple store instructions.
    // On RISC-V, sync_lock_release turns into an atomic swap:
    //   s1 = &lk->locked
    //   amoswap.w zero, zero, (s1)

    // 用amoswap把lk->locked置为0解锁
    __sync_lock_release(&lk->locked);

    pop_off();
}

写代码#

Memory allocator#

  • kernel内存分配默认只有一个全局的list。要改造成每个cpu一个list。

  • 需要完全理解kalloc.c，把kmem/kfree/kalloc改造成按cpu独立操作。

  • 如果某个cpu的内存不够，直接从别的cpu那儿拿空闲的内存。

  • 需要关/开中断，因为timer中断会造成yield，进程可能切换到别的cpu执行，造成数据错乱。

Buffer cache#

没完全懂它的意思。貌似也是要改造成尽量少用锁。
懒得纠结它的大坨说明，直接无脑用hash把block分散在一系列bcache bucket中完事儿。也能通过测试。

On this page