Overview 多道程序技术和程序并发执行的条件 Process Concept 3 Process Scheduling Operation on processes Interprocess Communication(进程间通信，IPC) 6 Example of IPC Systems Communication in C/S Systems 8 小结和作业 口1⊙生年12月00 陈香兰xlanchen@ustc.edu.cn http:/taf.u0117401:Operating System计算机u原理与道 March27,20193/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Overview 1 多道程序技术和程序并发执行的条件 2 Process Concept 3 Process Scheduling 4 Operation on processes 5 Interprocess Communication (进程间通信, IPC) 6 Example of IPC Systems 7 Communication in C/S Systems 8 小结和作业 陈香兰 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 3 / 88
Outline 多道程序技术和程序并发执行的条件 ●多道程序技术的难点 oSerial execution of programs(程序的顺序执行) o Concurrent execution of programs(程序的并发执行) 口1回年走1,2月Q0 陈话兰xlanchen@ustc.edu.cn http/staff.u0117401 Operating System计算机原理与道 March27,20194/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 4 / 88
Some easily confused terms o In our course: Program(程序：passive entity,usually a file containing a list of instructions stored on disk(often called an executable file). Tasks(任务：a general reference Jobs(作业：in batch system,user programs(and data)waiting to be loaded and executed Processes(进程：a program in execution o Usually,the term job and process are used interchangeably. 口1⊙生年12月0C 东香兰xlanchen@ustc,edu.cn http:/staff..u011740i:Operating System计算机原理与道 March27,20195/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Some easily confused terms In our course: ▶ Program(程序): passive entity, usually a file containing a list of instructions stored on disk (often called an executable file). ▶ Tasks(任务): a general reference ▶ Jobs(作业): in batch system, user programs (and data) waiting to be loaded and executed ▶ Processes(进程): a program in execution Usually, the term job and process are used interchangeably. 陈香兰 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 5 / 88
Outline 多道程序技术和程序并发执行的条件 ●多道程序技术的难点 o Serial execution of programs程序的顶序执行 。Concurrent execution of programs(程序的并发执行) 口1⊙生年12月00 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System计算机原理与道 March27,20196/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 6 / 88
Multiprogramming(多道程序techniques From Simple Batch system-Multiprogramming system Memory must be shared by multiple programs CPU must be multiplexing()by multiple programs 4 basic components: ●Process management ②Memory management 1/O system management file management 口1⊙生年12月0C 陈话兰xlanchen@ustc.edu.cn http/staff.u0117401 Operating System计算机原理与连 March27,20197/88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Multiprogramming(多道程序) techniques From Simple Batch system →Multiprogramming system ▶ Memory must be shared by multiple programs ▶ CPU must be multiplexing(复用) by multiple programs ▶ 4 basic components: 1 Process management 2 Memory management 3 I/O system management 4 file management 陈香兰 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 7 / 88
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