Algorithm 3 o flag[i]true Ti is hoping to enter its CS T do{ flag[i]true; While(flag[j]);//do nothing CRITICAL SECTION Flag[i]=flase; REMAINDER SECTION while(1); Analysis: o Progress(x)and Bounded waiting(x) When flag[o]and flag[1]changes from false to true almost at the same time,both processes cannot enter the CS(forever) 口1回年走1,2月Q0 东香兰xanchen@ustc.edu.cn http:/staff..u011740i:Operating System操作系统原理号 March29,201918/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm 3 flag[i] = true ⇒ Ti is hoping to enter its CS Ti do { flag[i] = true; While (flag[j]) ; // do nothing CRITICAL SECTION Flag[i]=flase; REMAINDER SECTION } while(1); Analysis: Progress (×) and Bounded waiting (×) When flag[0] and flag[1] changes from false to true almost at the same time, both processes cannot enter the CS (forever) 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 18 / 57
Peterson's Solution o Combining the key ideas of algorithm 1 2. Algorithm for Process Pi while(true){ flag[i]TRUE; The two processes share two turn =j; variables: int turn; while(flag(j]&turn =j) ;/∥do nothing Boolean flag[2] CRITICAL SECTION flag[i]=FALSE; REMAINDER SECTION This solution is correct. 口1⊙，注，1,2月00 东香兰xlanchen@ustc,edu.cn http:/staff..u011740i:Operating System操作系统原理 March29,201919/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Peterson’s Solution Combining the key ideas of algorithm 1 & 2. The two processes share two variables: int turn; Boolean flag[2] Algorithm for Process Pi while (true) { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j) ; // do nothing CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION } This solution is correct. 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 19 / 57
Outline Synchronization Hardware o TestAndSet Instruction Swap Instruction 口18，走卡11月00 陈话兰xlanchen@ustc.edu:cn http:/staff.uO11740i.Operating System操作系统原理斐 March29,201920/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 4 Synchronization Hardware TestAndSet Instruction Swap Instruction 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 20 / 57
Synchronization Hardware o Generally,any solution to the CS problem requires a LOCK a process acquires a lock before entering a CS releases the lock when it exits the CS do( acquire lock critical section release lock remainder section }while (TRUE); CSes are protected by locks Race conditions are prevented 口”1@，注卡”至年200 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理斐 March29,201921/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Synchronization Hardware Generally, any solution to the CS problem requires a LOCK ▶ a process ⋆ acquires a lock before entering a CS ⋆ releases the lock when it exits the CS do { acquire lock critical section release lock remainder section }while (TRUE); ▶ CSes are protected by locks ▶ Race conditions are prevented 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 21 / 57
Synchronization Hardware o Many systems provide hardware support for CS code Uniprocessors-could disable interrupts Current code would execute without preemption do disable interrupt critical section enable interrupt remainder section }while (TRUE); Generally too inefficient on multiprocessor systems,OSes using this not broadly scalable Modern machines therefore provide special atomic hardware instructions Atomic non-interruptable TestAndSet() Swap() 口”1@：注，至，2月Q0 陈话兰xlanchen@ustc.edu.cn http/staff.u0117401 Operating System操作系统原理斐 March29,201921/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Synchronization Hardware Many systems provide hardware support for CS code ▶ Uniprocessors – could disable interrupts ⋆ Current code would execute without preemption do { disable interrupt critical section enable interrupt remainder section }while (TRUE); ⋆ Generally too inefficient on multiprocessor systems, OSes using this not broadly scalable ▶ Modern machines therefore provide special atomic hardware instructions Atomic = non-interruptable ⋆ TestAndSet() ⋆ Swap() 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 29, 2019 21 / 57