第三章进程管理-1

第三章进程管理-1内容摘要：

tion 把程序当中具有共享资源并且对共享资源进行操作的这段程序 ,或者说在进程中涉及到临界资源的程序段叫做临界区 . a=a+1 print(a) a=a1 print(a) P1 P2 P3 If a0 a=a+1。 Else a=a1。 第三章 进 程 管 理 2020/11/17 40 程序段 1 程序段 2 程序段 3 共享变量 第三章 进 程 管 理 2020/11/17 41 使用临界区的原则 有空让进 :当临界区中无进程时 ,任何有权使用临界区的进程可进入 无空等待 :不允许两个以上的进程同时进入临界区 . 多中选一 :当没有进程在临界区 ,而同时有多个进程要求进入临界区 , 只能让其中一个进入临界区 ,其他进程必须等待 . 有限等待 :任何进入临界区的进程要求在有限的时间内得到满足 . 让权等待 :处于等待状态的进程应该放弃占用 CPU,以便使得其他进程 有机会得到 CPU的使用权 . 第三章 进 程 管 理 2020/11/17 42 进程互斥的两种解决方法 .由竞争各方平等协商 .引人一进程管理者 ,由管理者来协调竞争各方对互斥资源的使用 . 具体办法 : 硬件 (当一个进程进入临界区 ,就屏蔽所有中断 ) 软件 (用编程解决 ,但常常忙等待 ) 第三章 进 程 管 理 2020/11/17 43 进程互斥的软件方法  通过平等协商方式实现进程互斥的最初方法是软件方法 .  软件方法 [1]: While(free) free=true。 free=false。 临界区 free:表示临界区标志 true:有进程在临界区 false:无进程在临界区 (初值 )  其基本思路：是在进入临界区检查和设置一些标志，如果已有进程在临界 区，则在进入区通过循环检查进行等待；在退出区修改标志。  问题：设置什么标志和如何检查标志。 第三章 进 程 管 理 2020/11/17 44  软件方法 [2]: While( not turn)。 Turn=false 临界区 turn: true表示 P进入临界区 false表示 Q进程临界区 P: While( turn)。 Turn=true 临界区 Q: 第三章 进 程 管 理 2020/11/17 45  软件方法 [3]: Pturn=true。 While( qturn)。 Pturn=false 临界区 Pturn,qturn:初值为 false P进入临界区的条件 :pturn ∧ not qturn Q进入临界区的条件 :not Pturn ∧ qturn P: Qturn=true。 While (pturn) Qturn=false 临界区 Q: 第三章 进 程 管 理 2020/11/17 46 例 : 进行修改 ... while (flag[1])。 flag[0]=true。 临界区。 flag[0]=false。 进程 1 ... while (flag[0])。 flag[1]=true。 临界区。 flag[1]=false。 falg[0] flag[1] ... while (flag[1])。 临界区。 flag[0]=false。 ... while (flag[0])。 临界区。 flag[1]=false。 再进行修改 flag[1]=true。 flag[0]=true。 第三章 进 程 管 理 2020/11/17 47 ... flag[0]=true。 while (flag[1]) begin flag[0]=false。 wait(5)。 flag[0]=true。 end 临界区。 flag[0]=false。 ... flag[1]=true。 while (flag[0]) begin flag[1]=false。 wait(5)。 flag[1]=true。 end 临界区。 flag[1]=false。 第三章 进 程 管 理 2020/11/17 48  软件方法 [4]:Dekker算法 Pturn,qturn:初值为 false P进入临界区的条件 :pturn ∧ not qturn Q进入临界区的条件 :not Pturn ∧ qturn Turn:枚举类型 ,初值任意 第三章 进 程 管 理 2020/11/17 49 While (true) { pturn=true。 while( qturn) { if (turn==2) { pturn=false。 while(turn==2)。 pturn=true。 } } turn=2。 pturn=false。 } 临界区 P: While (true) { qturn=true。 while( pturn) { if (turn==2) { qturn=false。 while(turn==1)。 qturn=true。 } } turn=1。 qturn=false。 } 临界区 Q: 第三章 进 程 管 理 2020/11/17 50 软件解决的缺点 :  忙等待  实现过于复杂 ,需要高的编程技巧 .  Peterson算法 pturn=true。 turn=2。 while( qturnamp。 amp。 turn=2)。 Pturn=false 临界区 P: Qturn=true。 Turn=1。 while (pturnamp。 amp。 turn=1)。 Qturn=false 临界区 Q: 第三章 进 程 管 理 2020/11/17 51 硬件办法 [1]  boolean Ts(boolean *lock) { boolean old。 old=*lock。 *lock=true。 return(old)。 } while Ts (*lock)。 临界区 lock=false。 “测试并设置”指令 第三章 进 程 管 理 2020/11/17 52 硬件办法 [2] Void swap(int *a,int *b) { int temp temp=*a。 *a=*b。 *b=temp。 } key=true。 Do { swap(*lock,key)。 } while(key)。 临界区 lock=false。 “交换”指令 第三章 进 程 管 理 2020/11/17 53 硬件办法 [3] “开关中断”指令 进入临界区前执行：执行“关中断”指令 离开临界区后执行：执行“开中断”指令 第三章 进 程 管 理 2020/11/17 54 进程的同步机制 信号量及 同步机制 信号量及 管程 条件临界域 路径表达式等 (用于集中式系统中 ) 同步机制应满足的基本要求 1. 描述能力 — 必须能够详细描述出进程间这种相互配合以及相互矛盾的关系 . 2. 可以实现 — 实现起来方便 ,这种机制在一定的机制或一定的语言上要能够实施 . 3. 效率高 — 不然的话 ,它会降低系统的并行能力和并行程度 . 4. 使用方便 第三章 进 程 管 理 2020/11/17 55 信号量 (semaphore) 是一个数据结构。 严格说来 它是一个整型变量 ,能够刻画一定程序的状态 . .信号量 (semaphore)的定义 struc semaphore { int value。 pointer_pcb queue。 } .信号量说明 Semaphore s。 第三章 进 程 管 理 2020/11/17 56 信号量 ① 互斥的信号量 : ② 同步的信号量 : 信号量的物理意义 ① S0:S表示可用资源的个数 . ② S=0:S表示无资源使用 ,也无等待进程 . ③ S0: 表示等待队列中进程的个数 S 问题 :信号量的初值不能为负 ,为什么 ? 第三章 进 程 管 理 2020/11/17 57 原语 :primitive or aic action  是由若干机器指令构成的完成某种特定功能的一段程序 ,具有不可 分割性 .即原语的执行必须是连续的 ,在执行过程中不允许被中断 . 原语实现 :开关中断 1. 必须置一次且只能设一次初值 2. 初值不能为负数 3. 修改信号量的值只能由 . 信号量的使用原则 : 第三章 进 程 管 理 2020/11/17 58 / *原语  P(s)  { =。  if (0)  { 该进程状态置为等待态  将该进程的 PCB插入相应的等待队列未尾。  }  }  V(s)  { =+1。  if (=0)  { 唤醒相应等待队列  改变其状态为就绪态 .  并将其插入就绪队列 .  }  } 第三章 进 程 管 理 2020/11/17 59 P(mutex) V(mutex) 临界区 P(mutex) V(mutex) 临界区 P(mutex) V(mutex) 临界区 P1 P2 P3 用 第三章 进 程 管 理 2020/11/17 60 A和 B共享一台打印机 A进程 B进程 … 打印 … 互斥的例子 : P(s) V(s) … 打印 … P(s) V(s) S=1 第三章 进 程 管 理 2020/11/17 61 互斥的例子 : 2. 4个进程 A、 B、 C、 D共享 2台打印机 A进程 B进程 C进程 B进程 初值 : S=2。