Synchronization 系统中只要存在并发进程,即使是单核系统 都需要同步操作 总体上存在两类同步操作问题: producer 生产者消费者问题:一个消费者进程必须 等待生产者进程产生数据 consumer 互斥问题( Mutual Exclusion):保证在一个 给定的时间内只有一个进程使用共享资源 (临界区) P1 P2 Shared Resource 2021/2/11 计算机体系结构
Synchronization 17 系统中只要存在并发进程，即使是单核系统 都需要同步操作 总体上存在两类同步操作问题: 生产者-消费者问题：一个 消费者进程必须 等待生产者进程产生数据 互斥问题（Mutual Exclusion）: 保证在一个 给定的时间内只有一个进程使用共享资源 （临界区） producer consumer Shared Resource P1 P2 2021/2/11 计算机体系结构
O A Producer-Consumer Example ta eaa Producer Consumer R tail R head R Producer posting Item x: Consumer Load rtail,(tail) Load rhead,(head) Store(Rtail),X spin: Load R stail,(tail R R+1 if rhead==Rtail goto spin tail Store(tail,rtail Load r,(rhead shearhead+1 Store(head), rhead process(r) 假设指令都是顺序执行的 Problems? 2021/2/11 计算机体系结构
A Producer-Consumer Example 2021/2/11 计算机体系结构 18 假设指令都是顺序执行的 Producer posting Item x: Load Rtail, (tail) Store (Rtail), x Rtail=Rtail+1 Store (tail), Rtail Consumer: Load Rhead, (head) spin: Load Rtail, (tail) if Rhead==Rtail goto spin Load R, (Rhead) Rhead=Rhead+1 Store (head), Rhead process(R) Producer Consumer tail head Rtail Rtail Rhead R Problems?
O A Producer-Consumer Example continued Producer posting item x Consumer Load Rtail,(tail) Load rhead,(head) IStore(rtail),X spin Load R taill Rtail=rtail +1 if rhead==Rtail goto spin sTore(tail),rtail Load R,(Ri head head Rhead+1 Can the tail pointer get updated Store(head), rhead before the item x is stored process (r) Programmer assumes that if 3 happens after 2, then 4 happens after 1. Problem sequences are 2,3,4,1 4,1,2,3 2021/2/11 计算机体系结构 19
A Producer-Consumer Example continued 2021/2/11 计算机体系结构 19 Producer posting Item x: Load Rtail, (tail) Store (Rtail), x Rtail=Rtail+1 Store (tail), Rtail Consumer: Load Rhead, (head) spin: Load Rtail, (tail) if Rhead==Rtail goto spin Load R, (Rhead) Rhead=Rhead+1 Store (head), Rhead process(R) Can the tail pointer get updated before the item x is stored? Programmer assumes that if 3 happens after 2, then 4 happens after 1. Problem sequences are: 2, 3, 4, 1 4, 1, 2, 3 1 2 3 4
Using Memory Fences ta head Produce Consumer Rtail R tail head Producer posting Item x: Consumer Load rtail,(tail) Load rhead,(head) Store(rtail,X spin Load Rtail(tail) Membarss if rhead==Rtail goto spin Rtail= rtail+1 Membarl Store(tail,rtail _oad R,(re head head=rhead+1 ensures that tail ptr ensures that r store(head), rhead is not updated before x has been stored not loaded befopEoceSS(R) x has been stored 2021/2/11 计算机体系结构
Using Memory Fences 2021/2/11 计算机体系结构 20 Producer posting Item x: Load Rtail, (tail) Store (Rtail), x MembarSS Rtail=Rtail+1 Store (tail), Rtail Consumer: Load Rhead, (head) spin: Load Rtail, (tail) if Rhead==Rtail goto spin MembarLL Load R, (Rhead) Rhead=Rhead+1 Store (head), Rhead process(R) Producer Consumer tail head Rtail Rtail Rhead R ensures that tail ptr is not updated before x has been stored ensures that R is not loaded before x has been stored