同步与锁

数据竞争

count 自增

1. 无锁
2. 有锁

汇编指令执行简述

add $0x1,%edx
inc $edx

组成原理 / 体系结构

x86 汇编 CPU 执行流程分析

1. Fetch Instruction 取指令
2. Decode Instruction 解码
3. Memory Access 访问内存
4. Execute 执行
5. Write Back 回写
6. 每个操作 一个指令周期
7. 流水线 pipeline

count = 4

t3: count=4 t4: count=5 CPU1 写入 t5: count=5 CPU2 写入 t6: count=5 …

    t: 0   1   2   3   4   5   6
       -----------------------------
CPU1:  |F  |   |   |   |   |   |   |
       |   |D  |   |   |   |   |   |
       |   |   |M/4|   |   |   |   |
       |   |   |   |E/5|   |   |   |
       |   |   |   |   |W/5|   |   |
       |   |   |   |   |   |   |   |
       -----------------------------
CPU2:  |   |F  |   |   |   |   |   |
       |   |   |D  |   |   |   |   |
       |   |   |   |M/4|   |   |   |
       |   |   |   |   |E/5|   |   |
       |   |   |   |   |   |W/5|   |
       |   |   |   |   |   |   |   |
       -----------------------------

• 指令不是原子的
• lock 在 x86 原子
• atomic instruction

  lock addl $0x1,0x0(%eax)
      

  lock

    t: 0   1   2   3   4   5   6
       -----------------------------
CPU1:  |F  |   |   |   |   |   |   |
       |   |D  |   |   |   |   |   |
       |   |   |M/4|   |   |   |   |
       |   |   |   |E/5|   |   |   |
       |   |   |   |   |W/5|   |   |
       |   |   |   |   |   |   |   |
       -----------------------------
CPU2:  |   |   |   |   |   |F  |   |   |   |   |   |
       |   |   |   |   |   |   |D  |   |   |   |   |
       |   |   |   |   |   |   |   |M/4|   |   |   |
       |   |   |   |   |   |   |   |   |E/5|   |   |
       |   |   |   |   |   |   |   |   |   |W/5|   |
       |   |   |   |   |   |   |   |   |   |   |   |
       -----------------------------

Spin Lock 自旋锁

../../study/os/xv6-public/spinlock.h

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

rg -n initlock $PWD | sort

/data/gitana/study/os/xv6-public/bio.c:43:  initlock(&bcache.lock, "bcache");
/data/gitana/study/os/xv6-public/console.c:289:  initlock(&cons.lock, "console");
/data/gitana/study/os/xv6-public/defs.h:130:void            initlock(struct spinlock*, char*);
/data/gitana/study/os/xv6-public/file.c:22:  initlock(&ftable.lock, "ftable");
/data/gitana/study/os/xv6-public/fs.c:176:  initlock(&icache.lock, "icache");
/data/gitana/study/os/xv6-public/ide.c:55:  initlock(&idelock, "ide");
/data/gitana/study/os/xv6-public/kalloc.c:34:  initlock(&kmem.lock, "kmem");
/data/gitana/study/os/xv6-public/log.c:60:  initlock(&log.lock, "log");
/data/gitana/study/os/xv6-public/pipe.c:37:  initlock(&p->lock, "pipe");
/data/gitana/study/os/xv6-public/proc.c:26:  initlock(&ptable.lock, "ptable");
/data/gitana/study/os/xv6-public/sleeplock.c:16:  initlock(&lk->lk, "sleep lock");
/data/gitana/study/os/xv6-public/spinlock.c:13:initlock(struct spinlock *lk, char *name)
/data/gitana/study/os/xv6-public/trap.c:26:  initlock(&tickslock, "time");

1. acquire 获取锁
   • CAS: Compare And Swap
   • xchg: lock; xchgl %0, %1
   • pushcli() 关中断
2. release 释放锁
   • popcli() 开中断