第五拿并行性:互斥和同步 第5章并行性:互斥和同步 5,1引论 ■5,2临界段 ■53互压 ■5.4信号量 55管程 5.6进程间的通信
第五章 并行性：互斥和同步 第5章 并行性：互斥和同步 ◼ 5.1 引论 ◼ 5.2 临界段 ◼ 5.3 互斥 ◼ 5.4 信号量 ◼ 5.5 管程 ◼ 5.6 进程间的通信
第五拿并行性:互斥和同步 5.1引论 ■多道程序设计的出现对计算机系统产生 了极大的影响,推动了操作系统技术的 发展 ■并行的进程之间由于争用资源、互相通 信、互相制约而产生了互斥、同步和通 信问题是本章解决的重点内容,也是本 课程的重点内容
第五章 并行性：互斥和同步 5.1 引论 ◼ 多道程序设计的出现对计算机系统产生 了极大的影响，推动了操作系统技术的 发展 ◼ 并行的进程之间由于争用资源、互相通 信、互相制约而产生了互斥、同步和通 信问题是本章解决的重点内容，也是本 课程的重点内容
第五拿并行性:互斥和同步 5.1引论 多道程序系统中存在的进程之间有三种典型的 关系: 进程之间相互协作,直接知道对方的存在,直到对 方的名字(如进程之间的调用) ■进程之间通过共享间接知道对方的存在,但并不知 道对方的名字(如共享同一变量或文件) 进程之间晚全部知道对方的存在,但因为竞争资源 而形成制约关系(如争用CPU、内存或硬盘等)
第五章 并行性：互斥和同步 5.1 引论 ◼ 多道程序系统中存在的进程之间有三种典型的 关系： ◼ 进程之间相互协作，直接知道对方的存在，直到对 方的名字（如进程之间的调用） ◼ 进程之间通过共享间接知道对方的存在，但并不知 道对方的名字（如共享同一变量或文件） ◼ 进程之间晚全部知道对方的存在，但因为竞争资源 而形成制约关系（如争用CPU、内存或硬盘等）
第五拿并行性:互斥和同步 进程的交互关系:可以按照相互感知的程度来分类 相互感知的程度交互关系 个进程对其他进程潜在的控制问题 的影响 相互不感知(完全不了竞争 (competition)个进程的操作对其他互斥,死锁(可释放的资 解其它进程的存在) 进程的结果无影响源),饥饿 间接感知(双方都与第通过共享进行协作个进程的结果依赖于互斥,死锁(可释放的资 三方交互,如共享资 从其他进程获得的信息源),饥饿,数据一致性 源) 直接感知(双方直接交通过通信进行协作一个进程的结果依赖于死锁,饥饿 互,如通信) 从其他进程获得的信息 互斥,指多个进程不能同时使用同一个资源; 死锁,指多个进程互不相让,都得不到足够的资源; 饥饿,指一个进程一直得不到资源(其他进程可能轮流占用资源)
第五章 并行性：互斥和同步 进程的交互关系：可以按照相互感知的程度来分类 相互感知的程度 交互关系 一个进程对其他进程 的影响 潜在的控制问题 相互不感知(完全不了 解其它进程的存在) 竞争(competition) 一个进程的操作对其他 进程的结果无影响 互斥，死锁（可释放的资 源），饥饿 间接感知(双方都与第 三方交互，如共享资 源) 通过共享进行协作 一个进程的结果依赖于 从其他进程获得的信息 互斥，死锁（可释放的资 源），饥饿，数据一致性 直接感知(双方直接交 互，如通信) 通过通信进行协作 一个进程的结果依赖于 从其他进程获得的信息 死锁，饥饿 互斥，指多个进程不能同时使用同一个资源； 死锁，指多个进程互不相让，都得不到足够的资源； 饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）
第五章并行性:互斥和同步 个飞机订票系统,两个终端,运行T1、T2进 程 ad(刈); Read( x) f X1 then f X1 then x-x-1; write(X) write(X) 共享变量的修改冲突
第五章 并行性：互斥和同步 一个飞机订票系统，两个终端，运行T 1、T 2进 程 T1 : T2: ... ... Read( x) ; Read( x) ; i f x>=1 t hen i f x>=1 t hen x: =x- 1; x: =x- 1; wri t e( x) ; wri t e( x) ; ... ... 共享变量的修改冲突
第五拿并行性:互斥和同步 5.2临界段 设X初始值为10 设X初始值为10 T1. Read(X TlRead(X) T1. if x>=1 then T2. Read(x /=10 Tl.if x>=1 then /x=10 T1x=x-1 XEX T1wrte(X)∥/×=9 T2. Read(X) T1. write(X)∥X=9 T2, if x>=1 then T2 ifx>=l then x=10 T2,X=X-1 T2.x=x-1 T2wrte(X)∥/×=8 T2. write(X)∥X=9
第五章 并行性：互斥和同步 5.2 临界段 设X初始值为10 T1.Read(X) T1.if x>=1 then //x=10 T1.x=x-1 T1.write(X) // X=9 T2.Read(X) T2.if x>=1 then T2.x=x-1 T2.write(X) // X=8 设X初始值为10 T1.Read(X) T2.Read(X) T1.if x>=1 then //x=10 T1.x=x-1 T1.write(X) // X=9 T2.if x>=1 then //x=10 T2.x=x-1 T2.write(X) // X=9
第五拿并行性:互斥和同步 et copV put t g 有3个进程:get,copy和put,它们对4个存储区域f、S、t和g进 行操作 操作顺序冲突
第五章 并行性：互斥和同步 get copy put f s t g 有3个进程：get, copy和put，它们对4个存储区域f、s、t和g进 行操作。 操作顺序冲突
第五拿并行性:互斥和同步 g py p f st g 结果 初始状态|34,m22(1,2) g, C,p 4 ···5 33(1,2,3)正确 BPc45…mn33(1.22)错误 C,g,p 4 ···5 32(1,2,2)错误 g45…,mn32(1.2.2)错误 pcg4.5…m32(1.2.2)错误 pe|45m33a122)错误
第五章 并行性：互斥和同步 get copy put f s t g f s t g 结果 初始状态 3,4,...,m 2 2 (1,2) g,c,p 4,5,...,m 3 3 (1,2,3) 正确 g,p,c 4,5,...,m 3 3 (1,2,2) 错误 c,g,p 4,5,...,m 3 2 (1,2,2) 错误 c,p,g 4,5,...,m 3 2 (1,2,2) 错误 p,c,g 4,5,...,m 3 2 (1,2,2) 错误 p,g,c 4,5,...,m 3 3 (1,2,2) 错误
第五拿并行性:互斥和同步 5.2临界段 临界资源( Critical resource):在系统中每 只能一个(有限个)进程访问的资源, 如打印机、磁带机等。临界资源访问控 制是进程同步的基本问题 临界段( Critical section):每个进程中访 临界资源的那段代码叫临界段
第五章 并行性：互斥和同步 5.2 临界段 ◼ 临界资源(Critical Resource) ：在系统中每次 只能一个（有限个）进程访问的资源， 如打印机、磁带机等。临界资源访问控 制是进程同步的基本问题。 ◼ 临界段(Critical section):每个进程中访问 临界资源的那段代码叫临界段
第五拿并行性:互斥和同步 5.2临界段 进程使用临界段的原则 如果临界资源空闲,在共享同一个临界资源的进程中, 每次只允许一个进程进入自己的临界段; 如有多个进程同时要求进入临界段,应在有限时间内 允许其中一个进程进入临界段,不能互相阻塞; 进程在临界段内只能停留有限的时间; ■应保证进程能够在有限时间内进入临界段; 处于临界段之外的进程不能阻止其它进程进入临界段; 如果进程不能进入临界段,应立即释放CPU,进入阻 塞状态
第五章 并行性：互斥和同步 5.2 临界段 ◼ 进程使用临界段的原则 ◼ 如果临界资源空闲，在共享同一个临界资源的进程中， 每次只允许一个进程进入自己的临界段； ◼ 如有多个进程同时要求进入临界段，应在有限时间内 允许其中一个进程进入临界段，不能互相阻塞； ◼ 进程在临界段内只能停留有限的时间； ◼ 应保证进程能够在有限时间内进入临界段； ◼ 处于临界段之外的进程不能阻止其它进程进入临界段； ◼ 如果进程不能进入临界段，应立即释放CPU，进入阻 塞状态