大工13春《操作系统概论》辅导资料八
大工13春《操作系统概论》辅导资料八主 题：第五章并行性：互斥和同步（第1—3节）
学习时间：2013年5月20日－5月26日
内 容：
第五章并行性：互斥和同步
这周我们将学习第五章中的第1—3节，下面整理出的理念框架供同学们学习。
第一节 概论
1、计算机技术的发展，推动了操作系统技术的发展。
1）多道程序设计
在主存中同时存放多道程序，使其同时处于运行状态，并行（并发）执行；
2）多处理器系统
计算机系统由多个处理器组成，多个进程或线程在多个处理器上运行；
3）分布式处理系统
计算机系统由多台计算机构成，具有分散性和通信要求，进程和线程可分布在各台计算机上运行。
2、计算机系统的复杂性增大了程序设计的复杂性。
系统的观点：提高计算机系统的效率；
用户的观点：可靠、速度、易用性。
3、多道程序系统（多进程，多线程）引发的问题：
进程间对系统资源的共享；
进程间对系统资源的竞争；
进程间的相互制约等等。
4、进程间关系的三种类型：
1）进程间互相协同合作—通信问题；
2）进程间的资源（软资源）共享—互斥和死锁问题；
3）进程间的资源（硬资源）竞争—互斥和死锁问题。
5、多道程序系统进程和OS的关系：
6、顺序程序设计的特点
1）什么叫顺序程序设计
依照一定的逻辑顺序编制程序和组织程序运行，顺序主要是指相继地处理一个个的事件。 例如：依照事件的顺序，因果的顺序等。
例：作业的顺序处理：
输入作业1─>计算操作─>输出结果─>输入作业2……
2）顺序处理的特点
① 程序的顺序性：每个操作都在上一个操作结束后进行。
② 程序环境的封闭性：程序环境指程序赖以执行的条件，如：主存空间、寄存器、PSW等，所以：顺序处理时执行的程序独占全部系统资源；程序运行的环境及其改变由程序自己确定。
③ 程序执行结果的确定性，结果与执行的速度、时间无关。
例如：程序段1执行──间歇──－程序段2执行
④ 计算的可再现性，相同的初始条件运行同一程序时，所得的结果相同。
注意：顺序程序的性质决定了程序间不可能产生交叉及逻辑破坏。
7、并行程序设计
1）并行程序设计的概念
并行的目的是提高运行的速度及处理能力（吞吐能力），并行程序设计是考虑各种并行性的程序设计。现代计算机系统内的并行有如下几种可能：
① 硬设备间的并行（主要指外部设备间，外设同CPU间的并行）
②多道作业间的并行（软件并发）
多CPU系统作业间的并行：
上述指：CPU间并行（硬件），作业间并行（软件），同道作业中各作业步间的并行（或进程间的并行），例如：两个不相干的矩阵运算。
2）程序并行性的表示方法（以进程并行为例）
有向图表示：
3）并行程序设计的特点
并行语言表示：
parbegin
P1；P2；……；Pn
parend
①由parbegin,和parend括起，P1，…等为并行进程；
②Pi等为独立的进程，实现某个特定的功能。
第二节临界段
1、同步：（Synchronism）
有协作关系的（并发）进程间要不断调整它们的相对速度，即指两个事件的发生有时序关系，例如执行的先后顺序。所以无法预知进程的进展速度，则必须进行协调，称为同步。
2、互斥
资源的排他性使用而产生进程的互斥。或称：多个进程间要互斥的使用临界资源（Critical Resources）。临界资源：一次仅允许一个进程使用的资源，或称不能共享的资源。例如：打印机；A进程占有，则必须使用完后，其他进程方可使用。
注意：互斥也是一种特殊的同步关系，或者说：同步是一种特殊的互斥。
3、临界段的定义：
进程中访问共享变量的代码段称为临界段。
4、临界段的特点：
1）在不同的代码段中
2）共享同一变量
3）临界段是一程序段
5、临界段的互斥要求（满足下述要求才能解决互斥问题）
1）、在共享一个临界资源的进程中，每次只允许一个进程处于它的临界段中；
2）、若有多个进程同时要求进入它们的临界段，应在有限的时间内让其中之一进入临界段，而不应互相阻塞；
3）、进程只能在临界段内逗留有限时间；
4）、不应使要求进入临界段的进程无限期的等待；
5）、在临界段外的进程不可阻止其他进程进入临界段；
6）、在解决临界段问题时，进程进展的相对速度，处理机的个数是无法预期的。
第三节互斥
一、互斥的软件算法
解决的方法有多种，设有两个进程Pi、Pj互斥。则：
1、解法1：标志位法
用设标志位flag=True标志它正在执行临界段
=False标志它未执行临界段
算法描述：
解法的问题：
当两个进程的标志位最初都为false，这时刚好两个进程同时都想进入临界段，并且同时发现对方的标志位为false，于是两个进程同时进入了各自的临界段。违背了临界段设计原则（1）。
2、解法2：指针法（令牌法）
设立进程进入临界段的指针，如：变量turn，当turn＝i时，表示准许Pi进入临界段。
算法描述：
解法的问题：
强制两个进程以交替的次序进入临界段，如果Pi进程的处理器速度快，或者进程Pj的其它代码部分很长，进程Pi在进程Pj尚未进入临界段前再次要求进入临界段，尽管此时临界段为空（无进程处于临界段中），进程Pi也无法进入临界段，造成临界资源使用效率低。
3、解法3：修改的设标志位法,解法1未能表明自己想进入临界段的意愿。
修正如下：
算法描述：
解法的问题：
若两个进程同时想进入临界段，于是把各自的标志位置为true，并且同时检测对方的状态，发现对方也想进入临界段（或已在临界段中），于是互相“谦让”而阻塞了自己，谁也进不了临界段，从而违背了临界段设计原则（2）。
4、解法4：Dekker法（正确的解法）
每个进程设一个标志位，当该位为True时表示它要进入临界段，再设指针turn（令牌），指示那个进程进入临界段。
二、互斥的硬件方法
临界段产生的原因：
1）多机系统时，可能在一个CPU执行一条指令的中间（两个存储访问周期之间）另一个CPU上运行的进程修改了共用变量（产生了互斥现象）。
2）单机系统时，修改一个共用变量要几条指令（2－3条），当在这几条指令之间有中断发生时，则出现了临界段问题。
1、中断屏蔽方法
单处理器系统中，中断的发生可能引发进程的切换，则可能破坏临界段的使用条件，用屏蔽中断的方法使进程的临界段执行过程不被破坏。
问题：限制了处理器交叉执行程序的能力；多处理器系统不能保证互斥。
2、硬件指令方法
若能在一条指令中，即在一个存储周期内完成对变量的访问，则可避免发生临界段问题。
解决临界段问题的两种硬件指令：
1）TS（Test-and-Set）检测和设置指令（两功能一次完成）
2）SWAP交换指令（交换两个字的内容）
硬件指令实现互斥：
为每个临界段或其它互斥资源设置一个布尔变量lock，其值为false表示临界段未被使用，反之则正在被使用，用TS或者Swap进行lock的检测。
小结：硬件指令实现互斥的优缺点：
缺点：
等待进入临界段的进程需频繁检测lock
进程的此种状态称为：忙等待，该状态时浪费处理机时间。
优点：
适用于单或多处理机系统；
简单、有效；
适用于多重临界段情况。
填空题
1、在操作系统中，信号量表示资源，其值（）。
A、只能进行加减乘除运算来改变
B、进行任意的算术运算来改变
C、只能进行布尔型运算来改变
D、仅能用初始化和P、V操作来改变
2、在解决进程间同步和互斥机制中，有一种机制是用一个标志来代表某种资源的状态，该标志称为（）。
A、共享变量 B、flag C、信号量 D、整型变量
3、下列哪一个问题只包含进程互斥问题？（）。
A、田径场上的接力比赛
B、两个进程都要使用打印机
C、一个生产者和一个消费者通过一个缓冲区传递产品
D、公共汽车上司机和售票员的协作
4、下列哪种方法不能实现进程之间的通信？（）。
A、共享文件 B、数据库 C、全局变量 D、共享内存
5、我们把在一段时间内，只允许一个进程访问的资源，称为临界资源，因此，我们可以得到下列论述，下列正确的一条论述是（）。
A、对临界资源是不能实现资源共享的
B、对临界资源，应采取互斥访问方式来实现共享
C、为临界资源配上相应的设备控制块后，便能被共享
D、对临界资源应采取同时访问方式，来实现共享
参考答案：
1-5 DCBCB
页:
[1]