程序并发执行时的特征 1间断性 。并发程序"执行-暂停执行-执行 2失去封闭性 ·由于资源共享，程序间可能出现相互影响的现象 3不可再现性 。原因同上。 例：P1,P2,P3共享变量N。设某时刻N=n P1:N:=N+1; P2:print(N); P3:N:=0 P1:N:=N+1; P2:print(N); P2:print(N); P2:print(N); P3:N:=0 P1:N:=N+1: P3:N:=0 P1:N:=N+1; P3:N:=0: N依次为n+1;n+1;0 N依次为n;0;1 N依次为n;n+1;0 东香兰xlanchen@ustc,edu.cn http:/staff..u011740i:Operating System计算机原理与i March 27,2019 16/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 程序并发执行时的特征 1 间断性 并发程序“执行－暂停执行－执行” 2 失去封闭性 由于资源共享，程序间可能出现相互影响的现象 3 不可再现性 原因同上。 例：P1,P2,P3共享变量N。设某时刻N＝n P1: N:=N+1; P2: print(N); P3: N:=0; P1: N:=N+1; P2: print(N); P3: N:=0; N依次为n＋1；n＋1；0 P2: print(N); P3: N:=0; P1: N:=N+1; N依次为n；0；1 P2: print(N); P1: N:=N+1; P3: N:=0; N依次为n；n＋1；0 陈香兰 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 27, 2019 16 / 88
程序并发执行的条件(Bernstein's conditions) 。必须防止“不可再现性”。为使并发程序的执行保持“可再现 性”，引入并发执行的条件。 ·思路：分析程序或语句的输入信息和输出信息，考察它们的相关性 Definitions,notation and terminology: ★读集R(P),表示程序即在执行时需要参考的所有变量的集合 ★写集W(P),表示程序p在执行期间要改变的所有变量的集合 1966,Bernstein:if programs pi and p2 meet the following conditions,they can be executed concurrently,and have reproducibility(可再现性) If process pi writes to a memory cell Mi,then no process pi can read the cell Mi. If process p;read from a memory cell Mi,then no process pi can write to the cell Mi. If process pi writes to a memory cell Mi,then no process pi can write to the cell Mi. R(p1)∩W(P2UR(p2)∩W(p)UW(P1)∩W(P2)=a 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System计机原理与i March27.201917/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 程序并发执行的条件(Bernstein’s conditions) 必须防止“不可再现性”。 为使并发程序的执行保持“可再现 性”，引入并发执行的条件。 ▶ 思路：分析程序或语句的输入信息和输出信息，考察它们的相关性 ▶ Definitions, notation and terminology: ⋆ 读集R (pi)，表示程序pi在执行时需要参考的所有变量的集合 ⋆ 写集W (pi)，表示程序pi在执行期间要改变的所有变量的集合 ▶ 1966, Bernstein: if programs p1 and p2 meet the following conditions, they can be executed concurrently, and have reproducibility (可再现性) 1 If process pi writes to a memory cell Mi , then no process pj can read the cell Mi . 2 If process pi read from a memory cell Mi , then no process pj can write to the cell Mi . 3 If process pi writes to a memory cell Mi , then no process pj can write to the cell Mi . R (p1) ∩W(p2) ∪ R (p2) ∩W(p1) ∪W(p1) ∩W(p2) = ∅ 陈香兰 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 27, 2019 17 / 88
Outline ②Process Concept 。the Processes Process State oProcess Control Block(PCB) 口1⊙生年12月00 陈话兰xlanchen@ustc.edu.cn http/staff.u0117401:Operating System计算机原理与达 March27.201918/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 2 Process Concept the Processes Process State Process Control Block (PCB) 陈香兰 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 27, 2019 18 / 88
Outline ②Process Concept o the Processes Process State o Process Control Block (PCB) 口1⊙生年12月0C 陈话兰xlanchen@ustc.edu:cn http:/staff.u011740i.Operating System计算机原理与达 March27.201919/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 2 Process Concept the Processes Process State Process Control Block (PCB) 陈香兰 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 27, 2019 19 / 88
the processes 。进程需要使用某种方法加以描述，原因 ○进程运行的间断性，要求在进程暂停运行时记录该程序的现场， 以便下次能正确的继续运行 ②资源的共享，要求能够记录进程对资源的共享情况 ③为保证程序“正确”的并发执行，必须将进程看成某种对象， 对其进行描述并加以控制 口1⊙生年12月0C 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System计算机原理与道 March27,201920/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . the processes 进程需要使用某种方法加以描述，原因 1 进程运行的间断性，要求在进程暂停运行时记录该程序的现场， 以便下次能正确的继续运行 2 资源的共享，要求能够记录进程对资源的共享情况 3 为保证程序“正确”的并发执行，必须将进程看成某种对象， 对其进行描述并加以控制 陈香兰 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 27, 2019 20 / 88