Solution to Critical-Section Problem o A solution to the Critical-Section problem must satisfy: Mutual Exclusion(互斥： If process Pi is executing in its CS,no other processes can be executing in their CSes. ②Progres5(空闲让进)： If no process is executing in its CS and there exist some processes that wish to enter their CSes,the selection of the processes that will enter the CS next cannot be postponed indefinitely Bounded Waiting(有限等待)： A bound must exist on the number of times that other processes are allowed to enter their CSes after a process has made a request to enter its CS and before that request is granted Assume that each process executes at a nonzero speed No assumption concerning relative speed of the N processes 陈话兰xlanchen@ustc.edu:cn http/staff.uO1174O1 Operating System操作系统原理 March29,201913/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Critical-Section Problem A solution to the Critical-Section problem must satisfy: 1 Mutual Exclusion (互斥): If process Pi is executing in its CS, no other processes can be executing in their CSes. 2 Progress (空闲让进): If no process is executing in its CS and there exist some processes that wish to enter their CSes, the selection of the processes that will enter the CS next cannot be postponed indefinitely 3 Bounded Waiting (有限等待): A bound must exist on the number of times that other processes are allowed to enter their CSes after a process has made a request to enter its CS and before that request is granted ⋆ Assume that each process executes at a nonzero speed ⋆ No assumption concerning relative speed of the N processes 陈香兰 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 13 / 57
Outline 3】 Peterson's Solution 口1⊙生年12月00 东香兰xanchen@ustc.edu.cn http:/staff..u011740i:Operating System操作系统原理斐 March29,201914/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 3 Peterson’s Solution 陈香兰 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 14 / 57
Overview o Peterson's Solution: A classic software-based solution,only two processes are concerned o Assume that the LOAD and STORE instructions are atomic; that is,cannot be interrupted. o Algorithms 1~3 are not satisfied o Perterson's Solution is correct 口18走卡11月00 陈话兰xlanchen@ustc.edu.cn http/staff.u0117401 Operating System操作系统原理斐 March29,201915/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Overview Peterson’s Solution: A classic software-based solution, only two processes are concerned Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted. Algorithms 1~3 are not satisfied Perterson’s 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 15 / 57
Algorithm 1 o Let the two threads share a common integer value turn volatile int turn=0;/initially turn=0 turn =i=Ti can enter its CS T Analysis: Do( o?Mutual execution:√ while(turn!=i) ●？Progress: ;∥do nothing CRITICAL SECTION turn j; REMAINDER SECTION )while(1); 口18，走卡11月00 陈适兰xlanchen@ustc.edu.cn http:/staf.u01174O1:Operating System操作系统原理 March29,201916/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm 1 Let the two threads share a common integer value turn volatile int turn=0; // initially turn = 0 ▶ turn = i ⇒ Ti can enter its CS Ti Do { while (turn!=i) ; // do nothing CRITICAL SECTION turn = j; REMAINDER SECTION } while(1); Analysis: ? Mutual execution: √ ? Progress: × 陈香兰 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 16 / 57
Algorithm 2 o Replace the shared variable turn with a shared array: volatile boolean flag[2]; Initially flag[o]flag[1]false; flag[i]true Ti want to enter its CS,and enter its CS Ti Analysis: do( o?Progress:v While (flag[j]) o Mutual execution:x ;l∥do nothing When flag[o]and flag[1]changes from flag[i]true; false to true almost at the same time, CRITICAL SECTION they enter the CS at the same time Flag[i]=flase; REMAINDER SECTION while(1); 口1回走1,2月Q0 陈适兰xlanchen@ustc.edu.cn http:/staf.u01174O1:Operating System操作系统原理 March29,201917/57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm 2 Replace the shared variable turn with a shared array: volatile boolean flag[2]; ▶ Initially flag[0] = flag[1] = false; ▶ flag[i] = true ⇒ Ti want to enter its CS, and enter its CS Ti do { While (flag[j]) ; // do nothing flag[i] = true; CRITICAL SECTION Flag[i]=flase; REMAINDER SECTION } while(1); Analysis: ? Progress: √ ? Mutual execution: × When flag[0] and flag[1] changes from false to true almost at the same time, they enter the CS at the same time 陈香兰 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 17 / 57