操作系统第2部分进程死锁及经典问题30409

《操作系统第2部分进程死锁及经典问题30409》由会员分享，可在线阅读，更多相关《操作系统第2部分进程死锁及经典问题30409（126页珍藏版）》请在文档大全上搜索。

1、经典进程互斥与同步问题经典进程互斥与同步问题 生产者/消费者问题 读者/写者问题 哲学家就餐问题2.6 2.6 生产者生产者/ /消费者问题消费者问题3生产者/消费者问题 有一个或多个生产者生产某种类型的数据（记录、字符），并放置在缓冲区中 有一个或多个消费者从缓冲区中取数据，每次取一项 每次只能有一个代理（生产者或消费者）可以访问缓冲区 假设缓冲区是无限的 生产者、消费者的过程为：4producer:while (true) /* produce item v */bin = v;in+; 生产者生产者/消费者问题5consumer:while (true) while (in = out)

2、 /*do nothing */;w = bout;out+; /* consume item w */消费者生产者/消费者问题6生产者/消费者问题 指针in和out初始化指向缓冲区的第一个存储单元。 生产者通过in指针向存储单元存放数据，一次存放一条数据，且in指针向后移一个位置。 消费者从缓冲区中逐条取走数据，一次取一条数据，相应的存储单元变为“空”。每取走一条数据，out指针向后移一个存储单元位置。 试想，如果不控制生产者与消费者，将会产生什么结果？ 生产者和消费者可能同时进入缓冲区，甚至可能同时读/写一个存储单元，将导致执行结果不确定。 这显然是不允许的。必须使生产者和消费者互斥进入缓

3、冲区。即，某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其它任何生产者。10生产者/消费者问题 使用二元信号量来实现 缓冲区数量无限 整型变量n（=in-out）：缓冲区中的项数 信号量s：缓冲区访问互斥 信号量delay：消费者在空缓冲区时的等待队列 代码如下：11 是否正确？ 可能会产生什么问题？ 见P155 表5.4(下页)应该阻塞应该阻塞而没有阻塞而没有阻塞少执行了一个少执行了一个semWaitB(delay)13解决办法一：?14解决办法二：增加增加一个一个辅助辅助变量变量15生产者/消费者问题 使用信号量来实现 缓冲区数量无限 信号量n：缓冲区中项目个数 信号

4、量s：缓冲区访问权限 代码如下：16生产者/消费者问题17缓冲区的数量有限，为nproducer:while (true) /* produce item v */while (in + 1) % n = out) /* do nothing */;bin = v;in = (in + 1) % n生产者/消费者问题18缓冲区的数量有限，为nconsumer:while (true) while (in = out)/* do nothing */;w = bout;out = (out + 1) % n;/* consume item w */生产者/消费者问题19缓冲区的数量有限，为缓冲区

5、的数量有限，为n生产者/消费者问题20生产者/消费者问题 使用信号量来实现 缓冲区数量有限（=sizeofbuffer） 信号量n：缓冲区中项目个数 信号量s：缓冲区访问权限 信号量e：缓冲区中空闲空间的数量 代码如下：利用信号量实现生产者利用信号量实现生产者/消费者同步与互斥消费者同步与互斥(a) 生产者生产者(b) 消费者消费者无无阻塞阻塞等待资源等待资源被唤醒被唤醒否否被唤醒被唤醒是 否 有 数是 否 有 数据单元据单元消费数据消费数据是否是否可用可用取一条数据取一条数据有有是是归还使用权归还使用权空单元加空单元加1唤醒一个生产者唤醒一个生产者阻塞阻塞等待资源等待资源阻塞阻塞等待使用权等

6、待使用权被唤醒被唤醒否否被唤醒被唤醒是否有空是否有空存储单元存储单元生产一条数据生产一条数据是否是否可用可用有有存入一条数据存入一条数据归还使用权归还使用权是是数据单元加数据单元加1唤醒一个消费者唤醒一个消费者图图 生产者生产者/消费者执行流程图消费者执行流程图无无阻塞阻塞等待使用权等待使用权注意注意1. 进程应该先申请资源信号量，再申请互斥信号量，顺序不能颠倒。2. 对任何信号量的semWait与semSignal操作必须配对。同一进程中的多对semWait与semSignal语句只能嵌套，不能交叉。3. 对同一个信号量的semWait与semSignal可以不在同一个进程中。4. semW

7、ait与semSignal语句不能颠倒顺序，semWait语句一定先于semSignal语句。 允许多个读者进程可以同时读数据； 不允许多个写者进程同时写数据，即只能互斥写数据； 若有写者进程正在写数据，则不允许读者进程读数据。 当一个读者正在读数据时，另一个读者也需要读数据，应允许第二个读者进入，同理第三个及随后更多的读者都被允许进入。 现在假设一个写者到来，由于写操作是排他的，所以它不能访问数据，需要阻塞等待。如果一直都有新的读者陆续到来，写者的写操作将被严重推迟。 该方法称为“读者优先”。即，一旦有读者正在读数据，允许多个读者同时进入读数据，只有当全部读者退出，才允许写者进入写数据。用信

8、号量实现的具体过程见图读读进进程程具具有有优优先先权权 写进程具有优先权写进程具有优先权34管程使用信号的管程 semWait、semSignal可能分布于整个程序中，难以控制 管程（Monitor）是一个程序设计语言结构，它提供与信号量同样的功能，但更易于操作 管程是一个软件模块 一个或多个过程 一个初始化序列 局部数据35使用信号的管程 主要特点： 局部数据只能被管程的过程访问，任何外部过程都不能访问 一个进程通过调用管程的一个过程进入管程 在任何时候，只能有一个进程在管程中执行，调用管程的任何其它进程都要被挂起，以等待进程变为可用管程中的数据变量每次只能被一个进程访问到互斥36 管程通过

9、使用条件变量提供对同步的支持 条件变量包含在管程中 只能在管程中被访问 两个操作条件变量的函数： cwait（c）：调用进程的执行在条件c上挂起，管程现在可被另一个进程使用 csignal（c）：恢复在cwait之后为某条件而挂起的进程的执行（选一）。 与信号量的semWait、semSignal不同 如果在管程中的一个进程发信号，但没有在这个条件变量上等待的任务，则该信号丢失使用信号的管程37图图5.15 管程的结构管程的结构csignal唤醒唤醒csignal唤醒唤醒使用信号的管程38 使用管程解决生产者/消费者问题 缓冲区的数量为N在管程中定义使用信号的管程39管程代码 条件变量：not

10、full、notempty使用信号的管程40 与信号量比较 管程 管程负责互斥 程序员负责同步 把适当的cwait和csignal放在管程中 信号量 程序员负责互斥 程序员负责同步使用信号的管程2.9 2.9 互斥与同步解决方法之五互斥与同步解决方法之五消息传递消息传递发送进程发送进程接收进程接收进程邮件服务器邮件服务器接收进程接收进程发送进程发送进程终端用户终端用户邮件邮件邮件邮件发送进程发送进程接收进程接收进程邮件服务器邮件服务器接收进程接收进程发送进程发送进程终端用户终端用户邮件邮件图图 电子邮件的发送与接收过程电子邮件的发送与接收过程43消息传递 通过消息实现互斥与同步 两个消息原语：

11、send (destination, message)receive (source, message)44同步 发送者执行send原语 接受者执行receive原因 发送者和执行者阻塞或不阻塞 排列组合22=4种 send阻塞、receive阻塞 send阻塞、receive不阻塞 send不阻塞、receive阻塞 send不阻塞、receive不阻塞 是否全部可行？会产生什么问题？45寻址 直接寻址 send原语包括目标进程ID receive原语事先知道源进程ID receive原语通过source参数知道源进程ID46 间接寻址 消息发送到临时保存这些消息的队列组成的一个共享数据结构