【南京大学操作系统(蒋岩炎)】（三）理解并发程序执行

南京大学操作系统(蒋岩炎)】（三）理解并发程序执行"/>

【南京大学操作系统(蒋岩炎)】（三）理解并发程序执行

文章目录

• 互斥算法
• • Peterson 算法
• 并发控制 ：互斥（自选锁、互斥锁、futex）
• • • 互斥 (mutual exclusion)，“互相排斥”
  • 问题的思考
  • 自旋锁的实现
  • • x86 原子操作：LOCK 指令前缀
    • 用 xchg 实现互斥 (自旋锁)
    • 旧的x86原子操作
    • MESI（缓存一致性）
    • RISC
    • Compare-and-Swap 的 LR/SC 实现
  • 互斥锁的实现
  • • 自旋锁的缺陷
    • Scalability
    • 使用场景
    • 互斥锁 (Mutex Lock)
  • Futex = Spin + Mutex
  • • Spin VS Mutex
    • Futex: Fast Userspace muTexes
  • 总结

前言

我目前正在学jyy的操作系统，该文章为我的笔记。
学习链接 ： 链接点击跳转

互斥算法

• 只用内存的读写 写一个 lock()和 unlock()
• 山寨的lock 失败的原因 ： 不能保证原子的一致性

Peterson 算法

• 实现的是一个内存共享模型

• 想象成一个真实的物理空间
  

• 
  

• 这也证明了为什么 要贴上对方的名字 +

• take-away
• 状态机
  
• 尽可能的去实现model checker 判断程序的正确性

并发控制 ：互斥（自选锁、互斥锁、futex）

• Q:如何在多处理器上实现互斥？？？
  回顾
  并发编程
  理解并发的工具
  线程 = 人 (大脑能完成局部存储和计算)
  共享内存 = 物理世界 (物理世界天生并行)
  一切都是状态机

互斥 (mutual exclusion)，“互相排斥”

实现 lock_t 数据结构和 lock/unlock API:

typedef struct {...
} lock_t;
void lock(lock_t *lk);
void unlock(lock_t *lk);
//一把 “排他性” 的锁——对于锁对象 lk
//如果某个线程持有锁，则其他线程的 lock 不能返回

问题的思考

• 由于软件无法解决的lock ，因为软件的主要部分是计算
• 实现lock还需要系统有一个裁决机制
  
• 如果把 内敛汇编的 lock 去掉的话 ， 则会出错

自旋锁的实现

x86 原子操作：LOCK 指令前缀

• 例子：[sum-atomic.c](
• Atomic exchange (load + store)
• C++的 stdayomic.h
  
  

用 xchg 实现互斥 (自旋锁)

• 例子 ： 每次去厕所门口都需要exchange 只有在在上厕所的人身上才有钥匙
  

• 所有的lock的指令 都可以保证 lock指令的书写顺序 （多线程上）

• 下一条 指令执行之前 可以看到它上一条指令所有的事情

• 所有的指令都不能越过原子指令(上一lock指令前执行的全部指令)
  

旧的x86原子操作

• 当俩个cpu处理共享一个内存
• 上锁 加上lock汇编指令前缀
• 但是存在负担 1byte 代价大

MESI（缓存一致性）

• 但现在有 共享缓存锁 : 保证缓存的一致性
• MESI
  

RISC

Compare-and-Swap 的 LR/SC 实现

互斥锁的实现

自旋锁的缺陷

• 如果一个进程拿了一把钥匙，其他的进程都要等待，如果进程多的话，那浪费可想而知
• 达到了 多线程比单线程还慢

Scalability

使用场景

互斥锁 (Mutex Lock)

• C语言只负责计算的部分 ， 剩下的全部交给操作系统
  
  sum-scalability.c

Futex = Spin + Mutex

Spin VS Mutex

Futex: Fast Userspace muTexes

• gdb 调试 set scheduler-locking on, info threads, thread X (待完成 ，暂时功底不够)
• vim 替换操作
  

总结