第章进程和处理器管理 1进程 2进程控制 3线程 4进程互斥和同步 5进程间通信 6死锁问题 7处理器调度 8调度算法 9 Windows2000线程调度
第3章 进程和处理器管理 1 进程 2 进程控制 3 线程 4 进程互斥和同步 5 进程间通信 6 死锁问题 7 处理器调度 8 调度算法 9 windows2000/xp线程调度
程序的顺序执行和并发执行 1程序的顺序执行 其执行过程可以描述为 Repeat IR←M[pc」 pC←pC+1 K EXecute(instruction in IR)) Until CPU halt 程序的顺序执行特点: 程序执行的顺序性: °程序执行的封闭性 程序结果的可再现性
程序的顺序执行和并发执行 • 1. 程序的顺序执行 其执行过程可以描述为: • Repeat IR ← M [pc] • pc ← pc+1 • 〈 Execute (instruction in IR)〉 • Until CPU halt 程序的顺序执行特点: • 程序执行的顺序性: • 程序执行的封闭性: • 程序结果的可再现性:
顺序执行的特征 顺序性:按照程序结构所指定的次序(可能有分支或循 环 封闭性:独占全部资源,讲算机的状态只由于该程序的控 制逻辑所决定 可再现性:初始条作相同则结果相同。如:可通过空指令 控制时间关系。 并发执行的特征 间断(异步)性:"走走停停",一个程序可能走到中途停下 来,失去原有的时序关系; 失去封闭性:共享资源,受其他程序的控制逻辑的影响。 如:一个程序写到存储器中的数据可能被另一个程序修 改,失去原有的不变特征。 失去可再现性:失去封闭性一>失去可再现性;外界环境 在程序的两次执行期间发生变化,失去原有的可重复特
• 顺序执行的特征 – 顺序性:按照程序结构所指定的次序(可能有分支或循 环) – 封闭性:独占全部资源,计算机的状态只由于该程序的控 制逻辑所决定 – 可再现性:初始条件相同则结果相同。如:可通过空指令 控制时间关系。 • 并发执行的特征 – 间断(异步)性:"走走停停" ,一个程序可能走到中途停下 来,失去原有的时序关系; – 失去封闭性:共享资源,受其他程序的控制逻辑的 程序的控制逻辑的影响。 如:一个程序写到存储器中的数据可能被另一个程序修 改,失去原有的不变特征。 – 失去可再现性:失去封闭性 ->失去可再现性;外界环境 在程序的两次执行期间发生变化,失去原有的可重复特 征
begin integer N; N:=0 cobegin program A begin L1: N:=N+1 goto L1 end
begin integer N; N:=0; cobegin program A: begin L1: ······; N:=N+1; goto L1; end;
program B begin L2;… print(N); N:=0; goto L2, end coend end
program B: begin L2: ······; print(N); N:=0; goto L2; end; coend; end;
程序A和B是并发执行的,它们根 据运行环境的情况按照各自独立的速 度运行。由于它们共享一个变量N, 而N的值是由这两个程序共同确定 的。所以一个程序的执行结果,与它 和另一个程序的相对执行速度有密切 的关系
程序A和B是并发执行的,它们根 据运行环境的情况按照各自独立的速 度运行。由于它们共享一个变量N, 而N的值是由这两个程序共同确定 的。所以一个程序的执行结果,与它 和另一个程序的相对执行速度有密切 的关系
程序的并发执行 作业11c1Hp 作业2 12 H C2H7P2 作业3 : 13Hc3 +P3 时 t1 t2 t3 t4 t5 ≥间
程序的并发执行 作业1 I1 C1 P1 作业2 作业3 I2 C2 P2 I3 C3 P3 时 间 t1 t2 t3 t4 t5
多道程序系统的执行环境 并发环境:在一定时间内物理机器上有两个 或两个以上的程序同处于开始运行但尚未结 束的状态,并且次序不是事先确定的 并发执行的特征 间断(异步)性:"走走停停",一个程序可能走到中 途停下来,失去原有的时序关系; 失去封闭性:共享资源,受其他程序的控制逻辑 的影响。如:一个程序写到存储器中的数据可能 被另一个程序修改,失去原有的不变特征。 失去可再现性:失去封闭性一>失去可再现性;外 界环境在程序的两次执行期间发生变化,失去原 有的可重复特征
多道程序系统的执行环境 并发环境: 在一定时间内物理机器上有两个 或两个以上的程序同处于开始运行但尚未结 束的状态,并且次序不是事先确定的 • 并发执行的特征 – 间断(异步)性:"走走停停" ,一个程序可能走到中 途停下来,失去原有的时序关系; – 失去封闭性:共享资源,受其他程序的控制逻辑 的影响。如:一个程序写到存储器中的数据可能 被另一个程序修改,失去原有的不变特征。 – 失去可再现性:失去封闭性 ->失去可再现性;外 界环境在程序的两次执行期间发生变化,失去原 有的可重复特征
1966年 Bernstein提出了可以并发执行的条件 (这里没有考虑执行速度的影响。 将程序中任一语句Si划分为两个变量的集合 R(S)和WS)。其中 R(S)={ala2..am}表示S在执行期间所有引 用变量的集合; W(Si)={b1b2….bn}表示S在执行期间要改变 值的全部变量; R(S)nWS2)={$} ②W(S)nR(S2)={5} ③W(S)∩W(S2)={∮ 同时成立,则语句S和S2是可以并发执行的
1966年Bernstein 提出了可以并发执行的条件: (这里没有考虑执行速度的影响。) • 将程序中任一语句Si划分为两个变量的集合 R(Si)和W(Si)。其中 • R(Si)={a1 a2 … am}表示Si在执行期间所有引 用变量的集合; • W(Si)={b1 b2 … bn}表示Si在执行期间要改变 值的全部变量; ① R(S1)∩ W(S2)={∮}, ② W(S1)∩ R(S2)={∮}, ③ W(S1)∩ W(S2)={∮} 同时成立,则语句S1和S2是可以并发执行的
例有四条语句 SLa=x+ S2:b=Z+1 S3: c=a-b S4 W=C+1 能否并发执行?
例 有四条语句 S1:a=x+y S2:b=Z+1 S3:c=a-b S4:w=c+1 能否并发执行?