Difficulties of multiprogramming techniques 。与单道相比，在多道系统中，进程之间的运行随着调度的发生而 具有无序性，那么 How to ensure correct concurrent? o Related theory: Conditions of the concurrent execution of program ~Theoretical model:Precedence graph(前趋图) Analysis on the serial execution of programs based on precedence graph Analysis on the concurrent execution of programs based on precedence graph 口⊙卡生年12月0C 陈话兰xlanchen@ustc.edu:cn http:/staff.u0117401.Operating System计算机原理与道 March27,20198/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Difficulties of multiprogramming techniques 与单道相比，在多道系统中，进程之间的运行随着调度的发生而 具有无序性，那么 ▶ How to ensure correct concurrent? Related theory: ▶ Conditions of the concurrent execution of program ▶ Theoretical model: Precedence graph (前趋图) ▶ Analysis on the serial execution of programs based on precedence graph ▶ Analysis on the concurrent execution of programs based on precedence graph 陈香兰 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 8 / 88
Precedence Graph(前趋图) ●Goal: 准确的描述语句、程序段、进程之间的执行次序 Definition Precedence graph(前趋图)is a Directed Acyclic Graph(有向无环 图，DAG) ·Node(结点)： 一个执行单元（如一条语句、一个程序段或进程）》 。Edge(边，directed edge(有向边)： The precedence relation(前趋关系)"→" →={(P,)1P必须在P开始执行前执行完} 口1回年走1,2月Q0 陈话兰xlanchen@ustc.edu:cn http/staff.u01174O1 Operating System计算机原理与 March27,20199/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Precedence Graph (前趋图) Goal： 准确的描述语句、程序段、进程之间的执行次序 Definition Precedence graph (前趋图) is a Directed Acyclic Graph (有向无环 图, DAG). Node(结点)： 一个执行单元（如一条语句、一个程序段或进程） Edge(边, directed edge(有向边))： The precedence relation (前趋关系)“→”， →= {(Pi , Pj ) | Pi必须在Pj开始执行前执行完} 陈香兰 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 9 / 88
Precedence Graph(前趋图) of(P,P)e→，then Pi→P Here, P:is called the predecessor(前趋)ofP,and Pi the subsequent(后继)ofP; ●没有前趋的结点称为初始结点(initial node) ●没有后继的结点称为终止结点(final node) ●结点上使用一个权值(weight)表示 该结点所含的程序量或结点的执行时间 口”1回年4注年年至年2月Q0 陈话兰xlanchen@ustc.edu:cn http:/staff.u0117401.Operating System计算机原理与道 March27,20199/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Precedence Graph (前趋图) If ( Pi , Pj ) ∈→, then Pi → Pj Here, Pi is called the predecessor(前趋) of Pj , and Pj the subsequent(后继) of Pi 没有前趋的结点称为初始结点（initial node） 没有后继的结点称为终止结点（final node） 结点上使用一个权值（weight）表示 该结点所含的程序量或结点的执行时间 陈香兰 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 9 / 88
Precedence Graph(前趋图) Example: 2 5 8 6 1 3 9 口1回年走1,2月Q0 东香兰xlanchen@ustc,edu.cn http:/staff..u0117401:Operating System计算机原理与i March27,20199/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Precedence Graph (前趋图) Example: 1 2 3 4 5 6 7 8 9 陈香兰 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 9 / 88
Outline 多道程序技术和程序并发执行的条件 。多道程序技术的难点 o Serial execution of programs(程序的顺序执行) 。Concurrent execution of programs(程序的并发执行) 口1⊙生年12月00 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System计算机原理与道 March27.201910/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 1 多道程序技术和程序并发执行的条件 多道程序技术的难点 Serial execution of programs (程序的顺序执行) Concurrent execution of programs (程序的并发执行) 陈香兰 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 10 / 88