大工13春《操作系统概论》第五章辅导资料
大工13春《操作系统概论》第五章辅导资料主 题：第五章并行性：互斥和同步（第4—6节）
学习时间：2013年5月27日－6月2日
内 容：
第五章并行性：互斥和同步
这周我们将学习第五章中的第4—6节，下面整理出的理念框架供同学们学习。
第四节 信号量
一、基本思想
用信号量控制对共享资源的使用，即：解决进程间的同步和互斥。
二、信号量
定义：信号量是一整型变量，其值是一整数，对其可有三种操作：
1）可被初始化为非负整数；
2）Wait操作：将信号量值减一，若该值为负，则执行wait操作的进程等待；
3）Signal操作：将信号量值增一，若该值为非正，则执行signal操作的进程唤醒一个等待的进程。
三、信号量及同步原语
信号量的种类：
1）二元信号量：仅允许取值0，1（常用于互斥）
2）一般信号量：值取非负整数（dijkstra提出），常用于同步。
进程对信号量的wait操作可改变进程的状态：
-阻塞等待：进入阻塞队列；
-忙等待：在CPU上等待。
1、阻塞等待方式(进程在wait操作后的状态），把等待的进程放入与S信号量有关的等待队列。
2、忙等待方式（等待时间不长时）
1）信号量为整型变量，可为一般信号量或二元信号量。
2）一般信号量时的同步原语（原语的功能描述）
Wait（S）：while S<=0 DO skip 当S<=0时不断询问。
S：＝S－1； 取一个资源用。
Signal（S）：S：＝S＋1； 释放一个资源。
3）二元信号量的同步原语（原语的功能描述）
Wait B(S): While S=0 do skip;
S:= S-1;
Signal B(S):
S:=S+1;
3、信号量的操作的一般意义
设S为信号量，则：
wait（S）操作：
当S>0，S-1=>S，表示取一可用资源。
S<=0，S-1=>S，
若S值为负，无可用资源，进程等待。
signal（S）操作：S＋1=>S，
表示释放了一个可用资源
四、同步原语的不可分割性
信号量本身即是各进程的共享变量，所以对信号量的操作应该是互斥的。
信号量上的同步原语应该是原子的操作：
-保证进程互斥的使用同步原语；
-原语操作是一整体，不可分割。
解决的方法：
1、软件互斥算法—不是好方法(复杂)；
2、硬件关中断—适用于单处理机系统(有副作用)；
3、硬件指令方法—多处理机系统；
4、硬件和固件直接实现同步原语—现代操作系统方法
硬件指令实现互斥的同步原语（忙等待的一般信号量）：
wait(s):
While TS(lock) do skip;/上锁
While S<=0 do skip;
S:=S-1;
lock:=false; /开锁
signal(s):
While TS(lock) do skip; /上锁
S:=S+1;/同步原语代码
lock:=false; /开锁
五、用信号量实现进程间的互斥
1、用wait和signal原语实现同步和互斥
设mutex为互斥信号量，作为临界段的锁，可用单位数为1，所以，当mutex<0时，表示有进程等待进入临界段。
同步机构主要有两方面的用途：用信号量来实现进程间的同步--时序关系，互斥--临界段问题。
2、信号量作为进程阻塞及唤醒机构
即指：等待某事件时，阻塞自己（Wait）。外部事件结束后，唤醒进程（Signal）。
1）资源的分配和释放
设立信号量表示该资源的数量，所以有
wait操作：当信号量>0时，分配资源
信号量<=0时，表示资源已用光，阻塞进程
signal操作：释放资源
2）进程间的协调（同步）
例如：
A进程等待B进程执行结果，需先阻塞自己（同步）。
实现的方法：设一信号量S，A、B进程对其进行操作。
设信号量S＝0，则
A进程： B进程：
…… ……
进行计算； 进行计算；
wait（S）；阻塞自己 signal（S）；唤醒进程A
继续计算； ……
五生产者和消费者问题
并发进程的同步和互斥问题的一般形式。
生产者：产生可使用资源，如数据等。
消费者：使用资源，如取数据等。
例如：进程向缓冲区送数据：生产者。
进程自缓冲区取数据：消费者。
生产者与消费者之间应满足如下条件：
同步条件：
消费者取数据时，有界缓冲区中至少有一个是满的；
生产者送数据时，有界缓冲区中至少有一个是空的。
互斥条件：（当有多个生产者和消费者时）
有两个临界资源：满缓冲区指针：C
空缓冲区指针：P
对它们应互斥操作！
用wait和signal操作解决上述问题：
设信号量 E：空缓冲区资源信号量
F：满缓冲区资源信号量
Mutex：互斥信号量
同步过程描述（互斥信号量的操作出现在同一进程中同步信号量的操作出现在不同的进程中）：
var E, F: Semaphore;设信号量
mutex:binary Semaphore; 互斥信号量
Procedure producer
begin
repeat
生产数据；
Wait（E）； 取一个空缓冲区，E－1
Wait（Mutex）； 对空指针进行操作，互斥
“分给空缓冲区并调整指针P的临界段”；
Signal（Mutex）； 分配、调整完，出临界段
“向缓冲区装入数据”
Signal（F）； 满缓冲区数＋1，表示多了一个可用资源
forever
end
Consumeres（诸消费者进程）
begin
repeat
Wait（F）； 取数据，满缓冲区资源信号量－1
Wait（Mutex）； 对满指针进行操作，互斥
“分给缓冲区并调整指针C的临界段”；
Signal（Mutex）； 调整完，出临界段
“从缓冲区取出数据”；
Signal（E）；空缓冲区信号量＋1，增加一个空缓冲区
“消耗或处理数据”；
forever
end
主函数
Begin (*main program*) /主程序
F:=0; E:=n; mutex:=1; /信号量初始化
parbegin /并发程序开始
producer1; /各生产者进程
……
producern;
consumer1; /各消费者进程
……
consumerm;
parend /并发程序结束
end /程序结束
注意：
1、wait和signal操作成对出现
2、互斥信号量的wait和signal操作出现在同一进程中
3、同步信号量的wait和signal操作出现在不同进程中
4、wait和signal操作的顺序不能颠倒
六阅读者/写入者问题
条件：无写进程访问共享数据集时，阅读者可访问，否则等待。（不考虑阅读者和写入者同时要求访问共享数据集时，优先照顾写入者的情况）
算法描述：
var mutex, wrt：Semaphore; 定义两个信号量
mutex：访问readcount(读者数)的互斥信号量
wrt：写操作互斥信号量
readcount：integer；读者数，对阅读者是共享变量
mutex：＝wrt：＝1；初值信号量
readcount：＝0；读者数初值为0
parbegin 并行进程
Readeri：
begin 读进程i
Wait（mutex）； 将对读者计数，互斥
（其他读者勿进）入临界段
readcount：＝readcount＋1；读者数加1（计数）
if readcount＝1 then wait（wrt）；
若有读者，则不可同时写，若
有写入者，则读者等待于wrt
Signal（mutex）；读者计数结束，出临界段
读数据集操作；
Wait（mutex）；读结束，进入互斥
要进行变量readcount的操作
readcount：＝readcount－1；
读者数－1（一个读者读完）
if readcount＝0 then signal（wrt）；
若读者为0，可以写入了
Signal（mutex）； 退出临界段
end
Writeri：写入者进程
begin
Wait（wrt）；
要进行写操作，互斥，若有读者，则等待于wrt
写数据集；若无读者，写操作
Signal（wrt）；写完，出临界段
end
parend
注：当多个读者要进行读操作时，但此时正在进行写操作，则只有一个读者在wrt上等待，其他n-1个在mutex上等待。
第五节 管程的概念
各种解决互斥方法的缺点（如测试,wait和signal等）：
1）临界段的操作由用户实现，用户负担重
2）wait和signal操作在用户程序中，系统无法控制
3）当用户用错wait和signal操作时，可能产生死锁
解决的方法：管程。
一、管程的定义
将分散在用户进程中的临界段集中起来进行管理，为每一个共享资源设立一个秘书，秘书每次只允许一个来访者进入，这种秘书的概念称为管程（Monitor）。
1、管程分为两部分：
1）局部于该管程的数据结构──共享变量
2）局部于该管程对上述数据结构进行操作的若干个过程
2、管程的特性：
1）局部于管程的数据只能被局部于管程内的过程所访问；
2）一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
3）每次仅允许一个进程在管程内执行某个局部过程，其他进程阻塞。
二、用管程实现同步
1、用管程实现同步，需在管程内增加实现同步的设施。
-可使需要挂起的进程（在管程内的进程）挂起阻塞并离开管程；
-可使条件满足了的阻塞进程重新进入管程运行。
2、管程内支持同步的部分
-局限于管程并仅能从管程内进行访问的若干条件变量；
-在条件变量上操作的两个函数过程。
3、生产者与消费者问题的管程解决方法
图1 管程的结构
第六节 进程间的通讯
一、进程通信的实现
进程间为协同工作而必须进行信息的传递（或称消息的传递）称为进程间的通讯。
低级通讯原语：用于交换少量信息，如：信号量操作
高级通讯原语：用于进程大量信息
1、进程间通讯的两种方法：
a）直接通讯：进程直接发消息给进程。
b) 间接通讯：通过信箱进程通讯，信箱是双方约定的。
2、进程通信的实现
实例：一对多点通信（直接通信的一种方式）：
1）一个接收者，阻塞等待接收；
2）多个发送者，不阻塞。
a) 同步机制与数据结构
2）消息队列
--处于公用存储区；
--消息缓冲区链接成队；
--头指针放入接收者进程的PCB。
3）同步机制
--实现对消息队列的互斥访问；
--需设置信号量（互斥，等待）；
--信号量放入接收者进程的PCB。
2、通信原语
send和receive
二、间接通信方式
进程间通过信箱进行通信，信箱实际上就是一个消息队列。
1、间接通信的主要模式
一对一：两个进程间建立私用通信连接；
一对多：对同组进程的广播方式；
多对一：C/S模式下客户进程与服务器进程间通信。
2、信箱
静态信箱：
对进程而言是固定的，如端口方式（一对一方式）；
动态信箱：
进程与信箱动态链接，系统提供相应的原语。
三、其他通信模式
1、非阻塞发送，阻塞接收；
2、非阻塞发送，非阻塞接收；
3、阻塞发送，阻塞接收。
选择题
1、两个或多个活动在同一给定的时间间隔中进行称为（）。
A、并行
B、共享
C、并发
D、异步
2、任何两个并发进程之间（）。
A、一定存在互斥关系
B、一定存在同步关系
C、一定彼此独立无关
D、可能存在同步或互斥关系
3、若不采用进程同步或互斥机制，则多个进程的并发执行可能会导致进程运行结果不确定，这是由于（）而引起的。
A、内存不足
B、资源共享
C、请求I/O
D、多个进程对应于同一个程序
4、两个旅行社甲和乙为旅客到某航空公司订飞机票，形成互斥的资源是（）。
A、飞机票 B、旅行社 C、航空公司 D、旅行社和航空公司
5、实现进程之间同步与异步的通信工具为（）。
A、P、V操作
B、信箱通信
C、消息缓冲
D、高级通信
参考答案
1-5CDBAA
页:
[1]